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
Constants
- INT_MAX
- INT_MIN
- INT_SIZE
- NEG_OP
- NOSQ1
- OP_PRIO
key = operator, value = hash regrouping operators of lower precedence
- Unknown
Attributes
the lefthandside expression (nil for unary expressions)
the operator (symbol)
the righthandside expression
Public Class Methods
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 359 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
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 168 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
# File metasm/encode.rb, line 288 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
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 385 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
casts an unsigned value to a two-complement signed if the sign bit is set
# File metasm/main.rb, line 396 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
basic constructor XXX funny args order, you should use +Expression[]+ instead
# File metasm/main.rb, line 415 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
for boolean operators, true is 1 (or anything != 0), false is 0
# File metasm/parse.rb, line 748 def parse(lexer) 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
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 662 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
parses floats/hex into tok.value, returns nothing does not parse unary operators (-/+/~)
# File metasm/parse.rb, line 549 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 an expression in a string
# File metasm/parse.rb, line 793 def parse_string(str, &b) parse(Preprocessor.new(str), &b) end
parse an expression in a string updates the string to point after the parsed expression
# File metasm/parse.rb, line 779 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
returns the next value from lexer (parenthesised expression, immediate, variable, unary operators)
# File metasm/parse.rb, line 692 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
reads an operator from the lexer, returns the corresponding symbol or nil
# File metasm/parse.rb, line 494 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 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 480 def self.reduce_lambda(&b) old = @@reduce_lambda @@reduce_lambda = b if block_given? old end
# File metasm/main.rb, line 485 def self.reduce_lambda=(p) @@reduce_lambda = p end
# File metasm/main.rb, line 584 def self.reduce_op @@reduce_op end
Public Instance Methods
recursive check of equity using #== will not match 1+2 and 2+1
# File metasm/main.rb, line 424 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
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 438 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 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 462 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
returns the complexity of the expression (number of externals +1 per indirection)
# File metasm/decode.rb, line 92 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
# File metasm/encode.rb, line 271 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
returns the externals that appears in the expression, does not walk through other ExpressionType
# File metasm/main.rb, line 920 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
# File metasm/decode.rb, line 105 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
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 907 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
make it useable as Hash key (see +==+)
# File metasm/main.rb, line 430 def hash (@lexpr.hash + @op.hash + @rexpr.hash) & 0x7fff_ffff end
# File metasm/main.rb, line 933 def inspect "Expression[#{@lexpr.inspect.sub(/^Expression/, '') + ', ' if @lexpr}#{@op.inspect + ', ' if @lexpr or @op != :+}#{@rexpr.inspect.sub(/^Expression/, '')}]" end
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 885 def match(target, *vars) match_rec(target, vars.inject({}) { |h, v| h.update v => nil }) end
# File metasm/main.rb, line 889 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
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, it will temporarily overwrite
the global @@reduce_lambda XXX THIS IS NOT THREADSAFE
# File metasm/main.rb, line 494 def reduce(&b) old_rp, @@reduce_lambda = @@reduce_lambda, b if b case e = reduce_rec when Expression, Numeric; e else Expression[e] end ensure @@reduce_lambda = old_rp if b end
# File metasm/main.rb, line 776 def reduce_op_and(l, r) 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 elsif l.kind_of?(Expression) and l.op == :&; Expression[l.lexpr, :&, [l.rexpr, :&, r]].reduce_rec 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 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 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 else Expression[l, :&, r] end when :| # rol/ror composition reduce_rec_composerol l, r else Expression[l, :&, r] end end end
# File metasm/main.rb, line 648 def reduce_op_andand(l, r) if l == 0 # shortcircuit eval 0 elsif l == 1 Expression[r, :'!=', 0].reduce_rec elsif r == 0 0 # XXX l could be a special ExprType with sideeffects ? end end
# File metasm/main.rb, line 864 def reduce_op_div(l, r) 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 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 end end
# File metasm/main.rb, line 707 def reduce_op_eql(l, r) 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 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 elsif l.rexpr.kind_of?(::Integer) Expression[l.lexpr, :==, -l.rexpr].reduce_rec end end end
# File metasm/main.rb, line 628 def reduce_op_minus(l, r) 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 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 end end
# File metasm/main.rb, line 873 def reduce_op_mod(l, r) if r.kind_of?(Integer) and r != 0 and (r & (r-1) == 0) Expression[l, :&, r-1].reduce_rec end end
# File metasm/main.rb, line 722 def reduce_op_neq(l, r) if l == r; 0 end end
# File metasm/main.rb, line 701 def reduce_op_not(l, r) if r.kind_of? Expression and nop = NEG_OP[r.op] Expression[r.lexpr, nop, r.rexpr].reduce_rec end end
# File metasm/main.rb, line 838 def reduce_op_or(l, r) 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 elsif l.kind_of? Expression and l.op == :| # (a|b)|c => a|(b|c) Expression[l.lexpr, :|, [l.rexpr, :|, r]].reduce_rec 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 end end
# File metasm/main.rb, line 658 def reduce_op_oror(l, r) if l.kind_of?(::Numeric) and l != 0 # shortcircuit eval 1 elsif l == 0 Expression[r, :'!=', 0].reduce_rec elsif r == 0 Expression[l, :'!=', 0].reduce_rec end end
# File metasm/main.rb, line 588 def reduce_op_plus(l, r) 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 else # 1+a => a+1 Expression[r, :+, l].reduce_rec end # (a+b)+foo => a+(b+foo) elsif l.kind_of? Expression and l.op == :+; Expression[l.lexpr, :+, [l.rexpr, :+, r]].reduce_rec 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 elsif l.kind_of? Expression and l.op == :- and not l.lexpr reduce_rec_add_rec(r, l.rexpr) 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 else reduce_rec_add_rec(r, Expression.new(:-, l, nil)) end end
# File metasm/main.rb, line 679 def reduce_op_shl(l, r) if l == 0; 0 elsif r == 0; l elsif l.kind_of? Expression and l.op == :<< Expression[l.lexpr, :<<, [l.rexpr, :+, r]].reduce_rec 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 elsif r > l.rexpr Expression[[l.lexpr, :<<, r-l.rexpr], :&, (-1 << r)].reduce_rec else Expression[[l.lexpr, :>>, l.rexpr-r], :&, (-1 << r)].reduce_rec 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 end end
# File metasm/main.rb, line 668 def reduce_op_shr(l, r) if l == 0; 0 elsif r == 0; l elsif l.kind_of? Expression and l.op == :>> Expression[l.lexpr, :>>, [l.rexpr, :+, r]].reduce_rec 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 end end
# File metasm/main.rb, line 853 def reduce_op_times(l, r) 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 elsif r.kind_of? Expression and r.op == :*; Expression[[l, :*, r.lexpr], :*, r.rexpr].reduce_rec 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 # 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 end end
# File metasm/main.rb, line 727 def reduce_op_xor(l, r) 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 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 else # 1^a => a^1 Expression[r, :^, l].reduce_rec end elsif l.kind_of? Expression and l.op == :^ # (a^b)^c => a^(b^c) Expression[l.lexpr, :^, [l.rexpr, :^, r]].reduce_rec 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 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 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 end end end
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 511 def reduce_rec l = @lexpr.kind_of?(ExpressionType) ? @lexpr.reduce_rec : @lexpr r = @rexpr.kind_of?(ExpressionType) ? @rexpr.reduce_rec : @rexpr if @@reduce_lambda l = @@reduce_lambda[l] || l if not @lexpr.kind_of? Expression r = @@reduce_lambda[r] || r if 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] 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 @@reduce_lambda and ret.kind_of? ExpressionType and newret = @@reduce_lambda[ret] and newret != ret if newret.kind_of? ExpressionType ret = newret.reduce_rec else ret = newret end end ret end
# File metasm/main.rb, line 614 def reduce_rec_add_rec(cur, neg_l) 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) Expression[newl, cur.op, cur.rexpr].reduce_rec elsif newr = reduce_rec_add_rec(cur.rexpr, neg_l) Expression[cur.lexpr, cur.op, newr].reduce_rec end end end
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 812 def reduce_rec_composerol(e, mask) 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 else Expression[e, :&, mask] end end
# 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
# 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