class Metasm::E

handle immediate values, and arbitrary arithmetic/logic expression involving variables boolean values are treated as in C : true is 1, false is 0 TODO replace type with size => bits + type => [:signed/:unsigned/:any/:floating] TODO handle floats TODO ternary operator ?

Constants

INT_MAX
INT_MIN
INT_SIZE
NEG_OP
NOSQ1
OP_PRIO

key = operator, value = hash regrouping operators of lower precedence

Unknown

Attributes

lexpr[RW]

the lefthandside expression (nil for unary expressions)

op[RW]

the operator (symbol)

rexpr[RW]

the righthandside expression

Public Class Methods

[](l, op=nil, r=nil) click to toggle source

alternative constructor in operands order, and allows nesting using sub-arrays ex: Expression[[:-, 42], :*, [1, :+, [4, :*, 7]]] with a single argument, return it if already an Expression, else construct a new one (using unary +/-)

# File metasm/main.rb, line 363
def self.[](l, op=nil, r=nil)
        if not r      # need to shift args
                if not op
                        raise ArgumentError, 'invalid Expression[nil]' if not l
                        return l if l.kind_of? Expression
                        if l.kind_of?(::Numeric) and l < 0
                                r = -l
                                op = :'-'
                        else
                                r = l
                                op = :'+'
                        end
                else
                        r = op
                        op = l
                end
                l = nil
        else
                l = self[*l] if l.kind_of?(::Array)
        end
        r = self[*r] if r.kind_of?(::Array)
        new(op, r, l)
end
decode_imm(str, type, endianness, off=0) click to toggle source

decodes an immediate from a raw binary string type may be a length in bytes, interpreted as unsigned, or an expression type (eg :u32) endianness is either an endianness or an object than responds to endianness

# File metasm/decode.rb, line 174
def self.decode_imm(str, type, endianness, off=0)
        type = INT_SIZE.keys.find { |k| k.to_s[0] == ?a and INT_SIZE[k] == 8*type } if type.kind_of? ::Integer
        endianness = endianness.endianness if not endianness.kind_of? ::Symbol
        str = str[off, INT_SIZE[type]/8].to_s
        str = str.reverse if endianness == :little
        val = str.unpack('C*').inject(0) { |val_, b| (val_ << 8) | b }
        val = make_signed(val, INT_SIZE[type]) if type.to_s[0] == ?i
        val
end
Also aliased as: decode_immediate
decode_immediate(str, type, endianness, off=0)
Alias for: decode_imm
encode_imm(val, type, endianness, backtrace=nil) click to toggle source
# File metasm/encode.rb, line 294
def encode_imm(val, type, endianness, backtrace=nil)
        type = INT_SIZE.keys.find { |k| k.to_s[0] == ?a and INT_SIZE[k] == 8*type } if type.kind_of? ::Integer
        endianness = endianness.endianness if not endianness.kind_of? ::Symbol
        raise "unsupported endianness #{endianness.inspect}" unless [:big, :little].include? endianness
        raise(EncodeError, "immediate overflow #{type.inspect} #{Expression[val]} #{(Backtrace::backtrace_str(backtrace) if backtrace)}") if not in_range?(val, type)
        s = (0...INT_SIZE[type]/8).map { |i| (val >> (8*i)) & 0xff }.pack('C*')
        endianness != :little ? s.reverse : s
end
Also aliased as: encode_immediate
encode_immediate(val, type, endianness, backtrace=nil)
Alias for: encode_imm
in_range?(val, type) click to toggle source

checks if a given Expression/Integer is in the type range returns true if it is, false if it overflows, and nil if cannot be determined (eg unresolved variable)

# File metasm/main.rb, line 389
def self.in_range?(val, type)
        val = val.reduce if val.kind_of?(self)
        return unless val.kind_of?(::Numeric)

        if INT_MIN[type]
                val == val.to_i and
                val >= INT_MIN[type] and val <= INT_MAX[type]
        end
end
make_signed(val, bitlength) click to toggle source

casts an unsigned value to a two-complement signed if the sign bit is set

# File metasm/main.rb, line 400
def self.make_signed(val, bitlength)
        case val
        when Integer
                val = val - (1 << bitlength) if val > 0 and val >> (bitlength - 1) == 1
        when Expression
                val = Expression[val, :-, [(1<<bitlength), :*, [[val, :>>, (bitlength-1)], :==, 1]]]
        end
        val
end
new(op, rexpr, lexpr) click to toggle source

basic constructor XXX funny args order, you should use Expression[] instead

# File metasm/main.rb, line 419
def initialize(op, rexpr, lexpr)
        raise ArgumentError, "Expression: invalid arg order: #{[lexpr, op, rexpr].inspect}" if not op.kind_of?(::Symbol)
        @op = op
        @lexpr = lexpr
        @rexpr = rexpr
end
parse(lexer) click to toggle source

for boolean operators, true is 1 (or anything != 0), false is 0

# File metasm/parse.rb, line 757
def parse(lexer)
        lexer = Preprocessor.new(lexer) if lexer.kind_of?(::String)

        opstack = []
        stack = []

        return if not e = parse_value(lexer)

        stack << e

        while op = readop(lexer)
                nil while ntok = lexer.readtok and (ntok.type == :space or ntok.type == :eol)
                lexer.unreadtok ntok
                until opstack.empty? or OP_PRIO[op.value][opstack.last]
                        stack << new(opstack.pop, stack.pop, stack.pop)
                end

                opstack << op.value

                raise op, 'need rhs' if not e = parse_value(lexer)

                stack << e
        end

        until opstack.empty?
                stack << new(opstack.pop, stack.pop, stack.pop)
        end

        Expression[stack.first]
end
parse_intfloat(lexer, tok) click to toggle source

parses an integer/a float, sets its tok.value, consumes&aggregate necessary following tokens (point, mantissa..) handles $/$$ special asm label name XXX for binary, use _ delimiter or 0b prefix, or start with 0 : 1b may conflict with backward local anonymous label reference

# File metasm/parse.rb, line 671
def parse_intfloat(lexer, tok)
        if not tok.value and tok.raw == '$'
                l = lexer.program.cursource.last
                if not l.kind_of? Label
                        l = Label.new(lexer.program.new_label('instr_start'))
                        l.backtrace = tok.backtrace
                        lexer.program.cursource << l
                end
                tok.value = l.name
        elsif not tok.value and tok.raw == '$$'
                l = lexer.program.cursource.first
                if not l.kind_of? Label
                        l = Label.new(lexer.program.new_label('section_start'))
                        l.backtrace = tok.backtrace
                        lexer.program.cursource.unshift l
                end
                tok.value = l.name
        elsif not tok.value and tok.raw == '$_'
                tok.value = lexer.program.locallabels_fwd('endinstr')
        elsif not tok.value and tok.raw =~ /^([1-9][0-9]*)([fb])$/
                case $2
                when 'b'; tok.value = lexer.program.locallabels_bkw($1)     # may fallback to binary parser
                when 'f'; tok.value = lexer.program.locallabels_fwd($1)
                end
        end

        parse_num_value(lexer, tok)
end
parse_num_value(lexer, tok) click to toggle source

parses floats/hex into tok.value, returns nothing does not parse unary operators (-/+/~)

# File metasm/parse.rb, line 558
def parse_num_value(lexer, tok)
        if not tok.value and tok.raw =~ /^[a-f][0-9a-f]*h$/i
                # warn on variable name like ffffh
                puts "W: Parser: you may want to add a leading 0 to #{tok.raw.inspect} at #{tok.backtrace[-2]}:#{tok.backtrace[-1]}" if $VERBOSE
        end

        return if tok.value
        return if tok.raw[0] != ?. and !(?0..?9).include? tok.raw[0]

        case tr = tok.raw.downcase
        when /^0b([01][01_]*)$/, /^([01][01_]*)b$/
                tok.value = $1.to_i(2)

        when /^(0[0-7][0-7_]*)$/
                tok.value = $1.to_i(8)

        when /^([0-9][a-f0-9_]*)h$/
                tok.value = $1.to_i(16)

        when /^0x([a-f0-9][a-f0-9_]*)(u?l?l?|l?l?u?|p([0-9][0-9_]*[fl]?)?)$/, '0x'
                tok.value = $1.to_i(16) if $1
                ntok = lexer.readtok

                # check for C99 hex float
                if not tr.include? 'p' and ntok and ntok.type == :punct and ntok.raw == '.'
                        if not nntok = lexer.readtok or nntok.type != :string
                                lexer.unreadtok nntok
                                lexer.unreadtok ntok
                                return
                        end
                        # read all pre-mantissa
                        tok.raw << ntok.raw
                        ntok = nntok
                        tok.raw << ntok.raw if ntok
                        raise tok, 'invalid hex float' if not ntok or ntok.type != :string or ntok.raw !~ /^[0-9a-f_]*p([0-9][0-9_]*[fl]?)?$/i
                        raise tok, 'invalid hex float' if tok.raw.delete('_').downcase[0,4] == '0x.p'      # no digits
                        ntok = lexer.readtok
                end

                if not tok.raw.downcase.include? 'p'
                        # standard hex
                        lexer.unreadtok ntok
                else
                        if tok.raw.downcase[-1] == ?p
                                # read signed mantissa
                                tok.raw << ntok.raw if ntok
                                raise tok, 'invalid hex float' if not ntok or ntok.type == :punct or (ntok.raw != '+' and ntok.raw != '-')
                                ntok = lexer.readtok
                                tok.raw << ntok.raw if ntok
                                raise tok, 'invalid hex float' if not ntok or ntok.type != :string or ntok.raw !~ /^[0-9][0-9_]*[fl]?$/i
                        end

                        raise tok, 'internal error' if not tok.raw.delete('_').downcase =~ /^0x([0-9a-f]*)(?:\.([0-9a-f]*))?p([+-]?[0-9]+)[fl]?$/
                        b1, b2, b3 = $1.to_i(16), $2, $3.to_i
                        b2 = b2.to_i(16) if b2
                        tok.value = b1.to_f
                        # tok.value += 1/b2.to_f # TODO
                        puts "W: unhandled hex float #{tok.raw}" if $VERBOSE and b2 and b2 != 0
                        tok.value *= 2**b3
                        puts "hex float: #{tok.raw} => #{tok.value}" if $DEBUG
                end

        when /^([0-9][0-9_]*)(u?l?l?|l?l?u?|e([0-9][0-9_]*[fl]?)?)$/, '.'
                tok.value = $1.to_i if $1
                ntok = lexer.readtok
                if tok.raw == '.' and (not ntok or ntok.type != :string)
                        lexer.unreadtok ntok
                        return
                end

                if not tr.include? 'e' and tr != '.' and ntok and ntok.type == :punct and ntok.raw == '.'
                        if not nntok = lexer.readtok or nntok.type != :string
                                lexer.unreadtok nntok
                                lexer.unreadtok ntok
                                return
                        end
                        # read upto '.'
                        tok.raw << ntok.raw
                        ntok = nntok
                end

                if not tok.raw.downcase.include? 'e' and tok.raw[-1] == ?.
                        # read fractional part
                        tok.raw << ntok.raw if ntok
                        raise tok, 'bad float' if not ntok or ntok.type != :string or ntok.raw !~ /^[0-9_]*(e[0-9_]*)?[fl]?$/i
                        ntok = lexer.readtok
                end

                if tok.raw.downcase[-1] == ?e
                        # read signed exponent
                        tok.raw << ntok.raw if ntok
                        raise tok, 'bad float' if not ntok or ntok.type != :punct or (ntok.raw != '+' and ntok.raw != '-')
                        ntok = lexer.readtok
                        tok.raw << ntok.raw if ntok
                        raise tok, 'bad float' if not ntok or ntok.type != :string or ntok.raw !~ /^[0-9][0-9_]*[fl]?$/i
                        ntok = lexer.readtok
                end

                lexer.unreadtok ntok

                if tok.raw.delete('_').downcase =~ /^(?:(?:[0-9]+\.[0-9]*|\.[0-9]+)(?:e[+-]?[0-9]+)?|[0-9]+e[+-]?[0-9]+)[fl]?$/i
                        tok.value = tok.raw.to_f
                else
                        raise tok, 'internal error' if tok.raw =~ /[e.]/i
                end

        else raise tok, 'invalid numeric constant'
        end
end
parse_string(str, &b) click to toggle source

parse an expression in a string

# File metasm/parse.rb, line 804
def parse_string(str, &b)
        parse(Preprocessor.new(str), &b)
end
parse_string!(str, &b) click to toggle source

parse an expression in a string updates the string to point after the parsed expression

# File metasm/parse.rb, line 790
def parse_string!(str, &b)
        pp = Preprocessor.new(str)

        e = parse(pp, &b)

        # update arg
        len = pp.pos
        pp.queue.each { |t| len -= t.raw.length }
        str[0, len] = ''

        e
end
parse_value(lexer) click to toggle source

returns the next value from lexer (parenthesised expression, immediate, variable, unary operators)

# File metasm/parse.rb, line 701
def parse_value(lexer)
        nil while tok = lexer.readtok and tok.type == :space
        return if not tok
        case tok.type
        when :string
                # ignores the 'offset' word if followed by a string
                if not tok.value and tok.raw.downcase == 'offset'
                        nil while ntok = lexer.readtok and ntok.type == :space
                        if ntok.type == :string; tok = ntok
                        else lexer.unreadtok ntok
                        end
                end
                parse_intfloat(lexer, tok)
                val = tok.value || tok.raw
        when :quoted
                if tok.raw[0] != ?'
                        lexer.unreadtok tok
                        return
                end
                s = tok.value || tok.raw[1..-2]     # raise tok, 'need ppcessing !'
                s = s.reverse if lexer.respond_to? :program and lexer.program and lexer.program.cpu and lexer.program.cpu.endianness == :little
                val = s.unpack('C*').inject(0) { |sum, c| (sum << 8) | c }
        when :punct
                case tok.raw
                when '('
                        nil while ntok = lexer.readtok and (ntok.type == :space or ntok.type == :eol)
                        lexer.unreadtok ntok
                        val = parse(lexer)
                        nil while ntok = lexer.readtok and (ntok.type == :space or ntok.type == :eol)
                        raise tok, "syntax error, no ) found after #{val.inspect}, got #{ntok.inspect}" if not ntok or ntok.type != :punct or ntok.raw != ')'
                when '!', '+', '-', '~'
                        nil while ntok = lexer.readtok and (ntok.type == :space or ntok.type == :eol)
                        lexer.unreadtok ntok
                        raise tok, 'need expression after unary operator' if not val = parse_value(lexer)
                        val = Expression[tok.raw.to_sym, val]
                when '.'
                        parse_intfloat(lexer, tok)
                        if not tok.value
                                lexer.unreadtok tok
                                return
                        end
                        val = tok.value
                else
                        lexer.unreadtok tok
                        return
                end
        else
                lexer.unreadtok tok
                return
        end
        nil while tok = lexer.readtok and tok.type == :space
        lexer.unreadtok tok
        val
end
readop(lexer) click to toggle source

reads an operator from the lexer, returns the corresponding symbol or nil

# File metasm/parse.rb, line 503
def readop(lexer)
        if not tok = lexer.readtok or tok.type != :punct
                lexer.unreadtok tok
                return
        end

        if tok.value
                if OP_PRIO[tok.value]
                        return tok
                else
                        lexer.unreadtok tok
                        return
                end
        end

        op = tok
        case op.raw
        # may be followed by itself or '='
        when '>', '<'
                if ntok = lexer.readtok and ntok.type == :punct and (ntok.raw == op.raw or ntok.raw == '=')
                        op = op.dup
                        op.raw << ntok.raw
                else
                        lexer.unreadtok ntok
                end
        # may be followed by itself
        when '|', '&'
                if ntok = lexer.readtok and ntok.type == :punct and ntok.raw == op.raw
                        op = op.dup
                        op.raw << ntok.raw
                else
                        lexer.unreadtok ntok
                end
        # must be followed by '='
        when '!', '='
                if not ntok = lexer.readtok or ntok.type != :punct and ntok.raw != '='
                        lexer.unreadtok ntok
                        lexer.unreadtok tok
                        return
                end
                op = op.dup
                op.raw << ntok.raw
        # ok
        when '^', '+', '-', '*', '/', '%'
        # unknown
        else
                lexer.unreadtok tok
                return
        end
        op.value = op.raw.to_sym
        op
end
reduce_lambda(&b) click to toggle source

reduce_lambda is a callback called after the standard reduction procedure for custom algorithms the lambda may return a new expression or nil (to keep the old expr) exemple: lambda { |e| e.lexpr if e.kind_of? Expression and e.op == :& and e.rexpr == 0xffff_ffff } returns old lambda

# File metasm/main.rb, line 484
def self.reduce_lambda(&b)
        old = @@reduce_lambda
        @@reduce_lambda = b if block_given?
        old
end
reduce_lambda=(p) click to toggle source
# File metasm/main.rb, line 489
def self.reduce_lambda=(p)
        @@reduce_lambda = p
end
reduce_op() click to toggle source
# File metasm/main.rb, line 586
def self.reduce_op
        @@reduce_op
end

Public Instance Methods

==(o) click to toggle source

recursive check of equity using #== will not match 1+2 and 2+1

# File metasm/main.rb, line 428
def ==(o)
        # shortcircuit recursion
        o.object_id == object_id or (o.kind_of?(Expression) and @op == o.op and @lexpr == o.lexpr and @rexpr == o.rexpr)
end
Also aliased as: eql?
bind(binding = {}) click to toggle source

returns a new Expression with all variables found in the binding replaced with their value does not check the binding's key class except for numeric calls lexpr/rexpr bind if they respond_to? it

# File metasm/main.rb, line 442
def bind(binding = {})
        if binding[self]
                return binding[self].dup
        end

        l = @lexpr
        r = @rexpr
        if l and binding[l]
                raise "internal error - bound #{l.inspect}" if l.kind_of?(::Numeric)
                l = binding[l]
        elsif l.kind_of? ExpressionType
                l = l.bind(binding)
        end
        if r and binding[r]
                raise "internal error - bound #{r.inspect}" if r.kind_of?(::Numeric)
                r = binding[r]
        elsif r.kind_of? ExpressionType
                r = r.bind(binding)
        end
        Expression.new(@op, r, l)
end
bind!(binding = {}) click to toggle source

bind in place (replace self.lexpr/self.rexpr with the binding value) only recurse with Expressions (does not use respond_to?)

# File metasm/main.rb, line 466
def bind!(binding = {})
        if @lexpr.kind_of?(Expression)
                @lexpr.bind!(binding)
        elsif @lexpr
                @lexpr = binding[@lexpr] || @lexpr
        end
        if @rexpr.kind_of?(Expression)
                @rexpr.bind!(binding)
        elsif @rexpr
                @rexpr = binding[@rexpr] || @rexpr
        end
        self
end
complexity() click to toggle source

returns the complexity of the expression (number of externals +1 per indirection)

# File metasm/decode.rb, line 98
def complexity
        case @lexpr
        when ExpressionType; @lexpr.complexity
        when nil, ::Numeric; 0
        else 1
        end +
        case @rexpr
        when ExpressionType; @rexpr.complexity
        when nil, ::Numeric; 0
        else 1
        end
end
encode(type, endianness, backtrace=nil) click to toggle source
# File metasm/encode.rb, line 277
def encode(type, endianness, backtrace=nil)
        case val = reduce
        when Integer; EncodedData.new Expression.encode_imm(val, type, endianness, backtrace)
        else
                str = case INT_SIZE[type]
                      when  8; "\0"
                      when 16; "\0\0"
                      when 32; "\0\0\0\0"
                      when 64; "\0\0\0\0\0\0\0\0"
                      else [0].pack('C')*(INT_SIZE[type]/8)
                      end
                str = str.force_encoding('BINARY') if str.respond_to?(:force_encoding)
                EncodedData.new(str, :reloc => {0 => Relocation.new(self, type, endianness, backtrace)})
        end
end
eql?(o)
Alias for: ==
expr_externals(include_exprs=false) click to toggle source

returns the externals that appears in the expression, does not walk through other ExpressionType

# File metasm/main.rb, line 924
def expr_externals(include_exprs=false)
        a = []
        [@rexpr, @lexpr].each { |e|
                case e
                when Expression; a.concat e.expr_externals(include_exprs)
                when nil, ::Numeric; a
                when ExpressionType; include_exprs ? a << e : a
                else a << e
                end
        }
        a
end
expr_indirections() click to toggle source
# File metasm/decode.rb, line 111
def expr_indirections
        ret = case @lexpr
        when Indirection; [@lexpr]
        when ExpressionType; @lexpr.expr_indirections
        else []
        end
        case @rexpr
        when Indirection; ret << @rexpr
        when ExpressionType; ret.concat @rexpr.expr_indirections
        else ret
        end
end
externals() click to toggle source

returns the array of non-numeric members of the expression if a variables appears 3 times, it will be present 3 times in the returned array

# File metasm/main.rb, line 911
def externals
        a = []
        [@rexpr, @lexpr].each { |e|
                case e
                when ExpressionType; a.concat e.externals
                when nil, ::Numeric; a
                else a << e
                end
        }
        a
end
hash() click to toggle source

make it useable as Hash key (see +==+)

# File metasm/main.rb, line 434
def hash
        (@lexpr.hash + @op.hash + @rexpr.hash) & 0x7fff_ffff
end
inspect() click to toggle source
# File metasm/main.rb, line 937
def inspect
        "Expression[#{@lexpr.inspect.sub(/^Expression/, '') + ', ' if @lexpr}#{@op.inspect + ', ' if @lexpr or @op != :+}#{@rexpr.inspect.sub(/^Expression/, '')}]"
end
match(target, *vars) click to toggle source

a pattern-matching method Expression[42, :+, 28].match(Expression['any', :+, 28], 'any') => {'any' => 42} Expression[42, :+, 28].match(Expression['any', :+, 'any'], 'any') => false Expression[42, :+, 42].match(Expression['any', :+, 'any'], 'any') => {'any' => 42} vars can match anything except nil

# File metasm/main.rb, line 889
def match(target, *vars)
        match_rec(target, vars.inject({}) { |h, v| h.update v => nil })
end
match_rec(target, vars) click to toggle source
# File metasm/main.rb, line 893
def match_rec(target, vars)
        return false if not target.kind_of? Expression
        [target.lexpr, target.op, target.rexpr].zip([@lexpr, @op, @rexpr]) { |targ, exp|
                if targ and vars[targ]
                        return false if exp != vars[targ]
                elsif targ and vars.has_key? targ
                        vars[targ] = exp
                elsif targ.kind_of? ExpressionType
                        return false if not exp.kind_of? ExpressionType or not exp.match_rec(targ, vars)
                else
                        return false if targ != exp
                end
        }
        vars
end
reduce(&cb) click to toggle source

returns a simplified copy of self can return an Expression or a Numeric, may return self see reduce_rec for simplifications description if given a block, will use it instead of @@reduce_lambda

# File metasm/main.rb, line 498
def reduce(&cb)
        cb ||= @@reduce_lambda
        case e = reduce_rec(cb)
        when Expression, Numeric; e
        else Expression[e]
        end
end
reduce_op_and(l, r, cb) click to toggle source
# File metasm/main.rb, line 778
def reduce_op_and(l, r, cb)
        if l == 0 or r == 0; 0
        elsif r == 1 and l.kind_of?(Expression) and [:'==', :'!=', :<, :>, :<=, :>=].include?(l.op)
                l
        elsif l == r; l
        elsif l.kind_of?(Integer); Expression[r, :&, l].reduce_rec(cb)
        elsif l.kind_of?(Expression) and l.op == :&; Expression[l.lexpr, :&, [l.rexpr, :&, r]].reduce_rec(cb)
        elsif l.kind_of?(Expression) and [:|, :^].include?(l.op) and r.kind_of?(Integer) and (l.op == :| or (r & (r+1)) != 0)
                # (a ^| b) & i => (a&i ^| b&i)
                Expression[[l.lexpr, :&, r], l.op, [l.rexpr, :&, r]].reduce_rec(cb)
        elsif r.kind_of?(::Integer) and l.kind_of?(ExpressionType) and r == l.max_bits_mask
                l
        elsif r.kind_of?(::Integer) and l.kind_of?(Expression) and (r & (r+1)) == 0
                # foo & 0xffff
                case l.op
                when :+, :^
                        if l.lexpr.kind_of?(Expression) and l.lexpr.op == :& and
                                l.lexpr.rexpr.kind_of?(::Integer) and l.lexpr.rexpr & r == r
                                # ((a&m) + b) & m  =>  (a+b) & m
                                Expression[[l.lexpr.lexpr, l.op, l.rexpr], :&, r].reduce_rec(cb)
                        elsif l.rexpr.kind_of?(Expression) and l.rexpr.op == :& and
                                l.rexpr.rexpr.kind_of?(::Integer) and l.rexpr.rexpr & r == r
                                # (a + (b&m)) & m  =>  (a+b) & m
                                Expression[[l.lexpr, l.op, l.rexpr.lexpr], :&, r].reduce_rec(cb)
                        else
                                Expression[l, :&, r]
                        end
                when :|
                        # rol/ror composition
                        reduce_rec_composerol(l, r, cb)
                else
                        Expression[l, :&, r]
                end
        end
end
reduce_op_andand(l, r, cb) click to toggle source
# File metasm/main.rb, line 650
def reduce_op_andand(l, r, cb)
        if l == 0     # shortcircuit eval
                0
        elsif l == 1
                Expression[r, :'!=', 0].reduce_rec(cb)
        elsif r == 0
                0    # XXX l could be a special ExprType with sideeffects ?
        end
end
reduce_op_div(l, r, cb) click to toggle source
# File metasm/main.rb, line 868
def reduce_op_div(l, r, cb)
        if r == 0
        elsif r.kind_of? Integer and l.kind_of? Expression and l.op == :+ and l.rexpr.kind_of? Integer and l.rexpr % r == 0
                Expression[[l.lexpr, :/, r], :+, l.rexpr/r].reduce_rec(cb)
        elsif r.kind_of? Integer and l.kind_of? Expression and l.op == :* and l.lexpr % r == 0
                Expression[l.lexpr/r, :*, l.rexpr].reduce_rec(cb)
        end
end
reduce_op_eql(l, r, cb) click to toggle source
# File metasm/main.rb, line 709
def reduce_op_eql(l, r, cb)
        if l == r; 1
        elsif r == 0 and l.kind_of? Expression and nop = NEG_OP[l.op]
                Expression[l.lexpr, nop, l.rexpr].reduce_rec(cb)
        elsif r == 1 and l.kind_of? Expression and NEG_OP[l.op]
                l
        elsif r == 0 and l.kind_of? Expression and l.op == :+
                if l.rexpr.kind_of? Expression and l.rexpr.op == :- and not l.rexpr.lexpr
                        Expression[l.lexpr, :==, l.rexpr.rexpr].reduce_rec(cb)
                elsif l.rexpr.kind_of?(::Integer)
                        Expression[l.lexpr, :==, -l.rexpr].reduce_rec(cb)
                end
        end
end
reduce_op_minus(l, r, cb) click to toggle source
# File metasm/main.rb, line 630
def reduce_op_minus(l, r, cb)
        if l == :unknown or r == :unknown; :unknown
        elsif not l and r.kind_of? Expression and (r.op == :- or r.op == :+)
                if r.op == :- # no lexpr (reduced)
                        # -(-x) => x
                        r.rexpr
                else # :+ and lexpr (r is reduced)
                        # -(a+b) => (-a)+(-b)
                        Expression.new(:+, Expression.new(:-, r.rexpr, nil), Expression.new(:-, r.lexpr, nil)).reduce_rec(cb)
                end
        elsif l.kind_of? Expression and l.op == :+ and l.lexpr == r
                # shortcircuit for a common occurence [citation needed]
                # (a+b)-a
                l.rexpr
        elsif l
                # a-b => a+(-b)
                Expression[l, :+, [:-, r]].reduce_rec(cb)
        end
end
reduce_op_mod(l, r, cb) click to toggle source
# File metasm/main.rb, line 877
def reduce_op_mod(l, r, cb)
        if r.kind_of?(Integer) and r != 0 and (r & (r-1) == 0)
                Expression[l, :&, r-1].reduce_rec(cb)
        end
end
reduce_op_neq(l, r, cb) click to toggle source
# File metasm/main.rb, line 724
def reduce_op_neq(l, r, cb)
        if l == r; 0
        end
end
reduce_op_not(l, r, cb) click to toggle source
# File metasm/main.rb, line 703
def reduce_op_not(l, r, cb)
        if r.kind_of? Expression and nop = NEG_OP[r.op]
                Expression[r.lexpr, nop, r.rexpr].reduce_rec(cb)
        end
end
reduce_op_or(l, r, cb) click to toggle source
# File metasm/main.rb, line 842
def reduce_op_or(l, r, cb)
        if    l == 0; r
        elsif r == 0; l
        elsif l == -1 or r == -1; -1
        elsif l == r; l
        elsif l.kind_of? Integer; Expression[r, :|, l].reduce_rec(cb)
        elsif l.kind_of? Expression and l.op == :|
                # (a|b)|c => a|(b|c)
                Expression[l.lexpr, :|, [l.rexpr, :|, r]].reduce_rec(cb)
        elsif l.kind_of? Expression and l.op == :& and r.kind_of? Expression and r.op == :& and l.lexpr == r.lexpr
                # (a&b)|(a&c) => a&(b|c)
                Expression[l.lexpr, :&, [l.rexpr, :|, r.rexpr]].reduce_rec(cb)
        end
end
reduce_op_oror(l, r, cb) click to toggle source
# File metasm/main.rb, line 660
def reduce_op_oror(l, r, cb)
        if l.kind_of?(::Numeric) and l != 0   # shortcircuit eval
                1
        elsif l == 0
                Expression[r, :'!=', 0].reduce_rec(cb)
        elsif r == 0
                Expression[l, :'!=', 0].reduce_rec(cb)
        end
end
reduce_op_plus(l, r, cb) click to toggle source
# File metasm/main.rb, line 590
def reduce_op_plus(l, r, cb)
        if not l; r   # +x  => x
        elsif r == 0; l       # x+0 => x
        elsif l == :unknown or r == :unknown; :unknown
        elsif l.kind_of?(::Numeric)
                if r.kind_of? Expression and r.op == :+
                        # 1+(x+y) => x+(y+1)
                        Expression[r.lexpr, :+, [r.rexpr, :+, l]].reduce_rec(cb)
                else
                        # 1+a => a+1
                        Expression[r, :+, l].reduce_rec(cb)
                end
                # (a+b)+foo => a+(b+foo)
        elsif l.kind_of? Expression and l.op == :+; Expression[l.lexpr, :+, [l.rexpr, :+, r]].reduce_rec(cb)
        elsif l.kind_of? Expression and r.kind_of? Expression and l.op == :% and r.op == :% and l.rexpr.kind_of?(::Integer) and l.rexpr == r.rexpr
                Expression[[l.lexpr, :+, r.lexpr], :%, l.rexpr].reduce_rec(cb)
        elsif l.kind_of? Expression and l.op == :- and not l.lexpr
                reduce_rec_add_rec(r, l.rexpr, cb)
        elsif l.kind_of? Expression and r.kind_of? Expression and l.op == :& and r.op == :& and l.rexpr.kind_of?(::Integer) and r.rexpr.kind_of?(::Integer) and l.rexpr & r.rexpr == 0
                # (a&0xf0)+(b&0x0f) => (a&0xf0)|(b&0x0f)
                Expression[l, :|, r].reduce_rec(cb)
        else
                reduce_rec_add_rec(r, Expression.new(:-, l, nil), cb)
        end
end
reduce_op_shl(l, r, cb) click to toggle source
# File metasm/main.rb, line 681
def reduce_op_shl(l, r, cb)
        if l == 0; 0
        elsif r == 0; l
        elsif l.kind_of? Expression and l.op == :<<
                Expression[l.lexpr, :<<, [l.rexpr, :+, r]].reduce_rec(cb)
        elsif l.kind_of? Expression and l.op == :>> and r.kind_of? Integer and l.rexpr.kind_of? Integer
                # (a >> 1) << 1  ==  a & 0xfffffe
                if r == l.rexpr
                        Expression[l.lexpr, :&, (-1 << r)].reduce_rec(cb)
                elsif r > l.rexpr
                        Expression[[l.lexpr, :<<, r-l.rexpr], :&, (-1 << r)].reduce_rec(cb)
                else
                        Expression[[l.lexpr, :>>, l.rexpr-r], :&, (-1 << r)].reduce_rec(cb)
                end
        elsif r.kind_of?(::Integer) and l.kind_of?(Expression) and [:&, :|, :^].include?(l.op)
                # (a | b) << i => (a<<i | b<<i)
                Expression[[l.lexpr, :<<, r], l.op, [l.rexpr, :<<, r]].reduce_rec(cb)
        end
end
reduce_op_shr(l, r, cb) click to toggle source
# File metasm/main.rb, line 670
def reduce_op_shr(l, r, cb)
        if l == 0; 0
        elsif r == 0; l
        elsif l.kind_of? Expression and l.op == :>>
                Expression[l.lexpr, :>>, [l.rexpr, :+, r]].reduce_rec(cb)
        elsif r.kind_of? Integer and l.kind_of? Expression and [:&, :|, :^].include? l.op
                # (a | b) << i => (a<<i | b<<i)
                Expression[[l.lexpr, :>>, r], l.op, [l.rexpr, :>>, r]].reduce_rec(cb)
        end
end
reduce_op_times(l, r, cb) click to toggle source
# File metasm/main.rb, line 857
def reduce_op_times(l, r, cb)
        if    l == 0 or r == 0; 0
        elsif l == 1; r
        elsif r == 1; l
        elsif r.kind_of? Integer; Expression[r, :*, l].reduce_rec(cb)
        elsif r.kind_of? Expression and r.op == :*; Expression[[l, :*, r.lexpr], :*, r.rexpr].reduce_rec(cb)
        elsif l.kind_of? Integer and r.kind_of? Expression and r.op == :* and r.lexpr.kind_of? Integer; Expression[l*r.lexpr, :*, r.rexpr].reduce_rec(cb)     # XXX need & regsize..
        elsif l.kind_of? Integer and r.kind_of? Expression and r.op == :+ and r.rexpr.kind_of? Integer; Expression[[l, :*, r.lexpr], :+, l*r.rexpr].reduce_rec(cb)
        end
end
reduce_op_xor(l, r, cb) click to toggle source
# File metasm/main.rb, line 729
def reduce_op_xor(l, r, cb)
        if l == :unknown or r == :unknown; :unknown
        elsif l == 0; r
        elsif r == 0; l
        elsif l == r; 0
        elsif r == 1 and l.kind_of? Expression and NEG_OP[l.op]
                Expression[nil, :'!', l].reduce_rec(cb)
        elsif l.kind_of?(::Numeric)
                if r.kind_of? Expression and r.op == :^
                        # 1^(x^y) => x^(y^1)
                        Expression[r.lexpr, :^, [r.rexpr, :^, l]].reduce_rec(cb)
                else
                        # 1^a => a^1
                        Expression[r, :^, l].reduce_rec(cb)
                end
        elsif l.kind_of? Expression and l.op == :^
                # (a^b)^c => a^(b^c)
                Expression[l.lexpr, :^, [l.rexpr, :^, r]].reduce_rec(cb)
        elsif r.kind_of? Expression and r.op == :^
                if r.rexpr == l
                        # a^(a^b) => b
                        r.lexpr
                elsif r.lexpr == l
                        # a^(b^a) => b
                        r.rexpr
                else
                        # a^(b^(c^(a^d)))  =>  b^(a^(c^(a^d)))
                        # XXX ugly..
                        tr = r
                        found = false
                        while not found and tr.kind_of?(Expression) and tr.op == :^
                                found = true if tr.lexpr == l or tr.rexpr == l
                                tr = tr.rexpr
                        end
                        if found
                                Expression[r.lexpr, :^, [l, :^, r.rexpr]].reduce_rec(cb)
                        end
                end
        elsif l.kind_of?(Expression) and l.op == :& and l.rexpr.kind_of?(::Integer) and (l.rexpr & (l.rexpr+1)) == 0
                if r.kind_of?(::Integer) and r & l.rexpr == r
                        # (a&0xfff)^12 => (a^12)&0xfff
                        Expression[[l.lexpr, :^, r], :&, l.rexpr].reduce_rec(cb)
                elsif r.kind_of?(Expression) and r.op == :& and r.rexpr.kind_of?(::Integer) and r.rexpr == l.rexpr
                        # (a&0xfff)^(b&0xfff) => (a^b)&0xfff
                        Expression[[l.lexpr, :^, r.lexpr], :&, l.rexpr].reduce_rec(cb)
                end
        end
end
reduce_rec(cb = @@reduce_lambda) click to toggle source

resolves logic operations (true || false, etc) computes numeric operations (1 + 3) expands substractions to addition of the opposite reduces double-oppositions (-(-1) => 1) reduces addition of 0 and unary + canonicalize additions: put variables in the lhs, descend addition tree in the rhs => (a + (b + (c + 12))) make formal reduction if finds somewhere in addition tree (a) and (-a)

# File metasm/main.rb, line 513
def reduce_rec(cb = @@reduce_lambda)
        l = @lexpr.kind_of?(ExpressionType) ? @lexpr.reduce_rec(cb) : @lexpr
        r = @rexpr.kind_of?(ExpressionType) ? @rexpr.reduce_rec(cb) : @rexpr

        if cb
                l = cb[l] || l if l and not @lexpr.kind_of?(Expression)
                r = cb[r] || r if r and not @rexpr.kind_of?(Expression)
        end

        v =
        if r.kind_of?(::Numeric) and (not l or l.kind_of?(::Numeric))
                case @op
                when :+; l ? l + r : r
                when :-; l ? l - r : -r
                when :'!'; raise 'internal error' if l ; (r == 0) ? 1 : 0
                when :'~'; raise 'internal error' if l ; ~r
                when :'&&', :'||', :'>', :'<', :'>=', :'<=', :'==', :'!='
                        raise 'internal error' if not l
                        case @op
                        when :'&&'; (l != 0) && (r != 0)
                        when :'||'; (l != 0) || (r != 0)
                        when :'>' ; l > r
                        when :'>='; l >= r
                        when :'<' ; l < r
                        when :'<='; l <= r
                        when :'=='; l == r
                        when :'!='; l != r
                        end ? 1 : 0
                else
                        l.send(@op, r)
                end
        elsif rp = @@reduce_op[@op]
                rp[self, l, r, cb]
        end

        ret = case v
        when nil
                # no dup if no new value
                (r == :unknown or l == :unknown) ? :unknown :
                ((r == @rexpr and l == @lexpr) ? self : Expression.new(@op, r, l))
        when Expression
                (v.lexpr == :unknown or v.rexpr == :unknown) ? :unknown : v
        else v
        end
        if cb and ret.kind_of?(ExpressionType) and newret = cb[ret] and newret != ret
                if newret.kind_of?(ExpressionType)
                        ret = newret.reduce_rec(cb)
                else
                        ret = newret
                end
        end
        ret
end
reduce_rec_add_rec(cur, neg_l, cb) click to toggle source
# File metasm/main.rb, line 616
def reduce_rec_add_rec(cur, neg_l, cb)
        if neg_l == cur
                # -l found
                0
        elsif cur.kind_of?(Expression) and cur.op == :+
                # recurse
                if newl = reduce_rec_add_rec(cur.lexpr, neg_l, cb)
                        Expression[newl, cur.op, cur.rexpr].reduce_rec(cb)
                elsif newr = reduce_rec_add_rec(cur.rexpr, neg_l, cb)
                        Expression[cur.lexpr, cur.op, newr].reduce_rec(cb)
                end
        end
end
reduce_rec_composerol(e, mask, cb) click to toggle source

a check to see if an Expr is the composition of two rotations (rol eax, 4 ; rol eax, 6 => rol eax, 10) this is a bit too ugly to stay in the main reduce_rec body.

# File metasm/main.rb, line 816
def reduce_rec_composerol(e, mask, cb)
        m = Expression[['var', :sh_op, 'amt'], :|, ['var', :inv_sh_op, 'inv_amt']]
        if vars = e.match(m, 'var', :sh_op, 'amt', :inv_sh_op, 'inv_amt') and vars[:sh_op] == {:>> => :<<, :<< => :>>}[vars[:inv_sh_op]] and
           ((vars['amt'].kind_of?(::Integer) and  vars['inv_amt'].kind_of?(::Integer) and ampl = vars['amt'] + vars['inv_amt']) or
            (vars['amt'].kind_of? Expression and vars['amt'].op == :% and vars['amt'].rexpr.kind_of?(::Integer) and
             vars['inv_amt'].kind_of? Expression and vars['inv_amt'].op == :% and vars['amt'].rexpr == vars['inv_amt'].rexpr and ampl = vars['amt'].rexpr)) and
           mask == (1<<ampl)-1 and vars['var'].kind_of? Expression and        # it's a rotation

           vars['var'].op == :& and vars['var'].rexpr == mask and
          ivars = vars['var'].lexpr.match(m, 'var', :sh_op, 'amt', :inv_sh_op, 'inv_amt') and ivars[:sh_op] == {:>> => :<<, :<< => :>>}[ivars[:inv_sh_op]] and
           ((ivars['amt'].kind_of?(::Integer) and  ivars['inv_amt'].kind_of?(::Integer) and ampl = ivars['amt'] + ivars['inv_amt']) or
            (ivars['amt'].kind_of? Expression and ivars['amt'].op == :% and ivars['amt'].rexpr.kind_of?(::Integer) and
             ivars['inv_amt'].kind_of? Expression and ivars['inv_amt'].op == :% and ivars['amt'].rexpr == ivars['inv_amt'].rexpr and ampl = ivars['amt'].rexpr))
                if ivars[:sh_op] != vars[:sh_op]
                        # ensure the rotations are the same orientation
                        ivars[:sh_op], ivars[:inv_sh_op] = ivars[:inv_sh_op], ivars[:sh_op]
                        ivars['amt'],  ivars['inv_amt']  = ivars['inv_amt'],  ivars['amt']
                end
                amt = Expression[[vars['amt'], :+, ivars['amt']], :%, ampl]
                invamt = Expression[[vars['inv_amt'], :+, ivars['inv_amt']], :%, ampl]
                Expression[[[[ivars['var'], :&, mask], vars[:sh_op], amt], :|, [[ivars['var'], :&, mask], vars[:inv_sh_op], invamt]], :&, mask].reduce_rec(cb)
        else
                Expression[e, :&, mask]
        end
end
render() click to toggle source
# File metasm/render.rb, line 86
def render
        l = @lexpr.kind_of?(::Integer) ? render_integer(@lexpr) : @lexpr
        r = @rexpr.kind_of?(::Integer) ? render_integer(@rexpr) : @rexpr
        l = ['(', l, ')'] if @lexpr.kind_of?(Expression) and (not oa = NOSQ1[@op] or not oa.include?(@lexpr.op))
        r = ['(', r, ')'] if @rexpr.kind_of?(Expression) and (not oa = NOSQ2[@op] or not oa.include?(@rexpr.op))
        op = @op if l or @op != :+
        if op == :+
                r0 = [r].flatten.first
                r0 = r0.render.flatten.first while r0.kind_of? Renderable
                op = nil if (r0.kind_of?(::Integer) and r0 < 0) or (r0.kind_of?(::String) and r0[0] == ?-) or r0 == :-
        end
        [l, op, r].compact
end
render_integer(e) click to toggle source
# File metasm/render.rb, line 70
def render_integer(e)
        if e < 0
                neg = true
                e = -e
        end
        if e < 10; e = e.to_s
        else
                e = '%xh' % e
                e = '0' << e unless (?0..?9).include? e[0]
        end
        e = '-' << e if neg
        e
end