diff options
| -rw-r--r-- | miasm2/arch/x86/sem.py | 43 | ||||
| -rw-r--r-- | miasm2/expression/simplifications.py | 535 | ||||
| -rw-r--r-- | miasm2/expression/simplifications_common.py | 503 | ||||
| -rw-r--r-- | miasm2/expression/simplifications_cond.py | 217 | ||||
| -rw-r--r-- | test/expression/simplifications.py | 33 |
5 files changed, 796 insertions, 535 deletions
diff --git a/miasm2/arch/x86/sem.py b/miasm2/arch/x86/sem.py index 4b8a357b..f85a6bcf 100644 --- a/miasm2/arch/x86/sem.py +++ b/miasm2/arch/x86/sem.py @@ -314,10 +314,22 @@ def l_test(ir, instr, a, b): return None, e, [] + +def get_shift(a, b): + # b.size must match a + b = b.zeroExtend(a.size) + if a.size == 64: + shift = b & ExprInt_from(b, 0x3f) + else: + shift = b & ExprInt_from(b, 0x1f) + shift = expr_simp(shift) + return shift + + def l_rol(ir, instr, a, b): e = [] - b = b.zeroExtend(a.size) - c = ExprOp('<<<', a, b) + shifter = get_shift(a, b) + c = ExprOp('<<<', a, shifter) new_cf = c[:1] e.append(ExprAff(cf, new_cf)) @@ -329,8 +341,8 @@ def l_rol(ir, instr, a, b): def l_ror(ir, instr, a, b): e = [] - b = b.zeroExtend(a.size) - c = ExprOp('>>>', a, b) + shifter = get_shift(a, b) + c = ExprOp('>>>', a, shifter) e.append(ExprAff(cf, c.msb())) # hack (only valid if b=1): when count == 1: a = msb-1(dest) @@ -341,9 +353,9 @@ def l_ror(ir, instr, a, b): def rcl(ir, instr, a, b): e = [] - b = b.zeroExtend(a.size) - c = ExprOp('<<<c_rez', a, b, cf.zeroExtend(a.size)) - new_cf = ExprOp('<<<c_cf', a, b, cf.zeroExtend(a.size))[:1] + shifter = get_shift(a, b) + c = ExprOp('<<<c_rez', a, shifter, cf.zeroExtend(a.size)) + new_cf = ExprOp('<<<c_cf', a, shifter, cf.zeroExtend(a.size))[:1] e.append(ExprAff(cf, new_cf)) # hack (only valid if b=1) @@ -354,9 +366,9 @@ def rcl(ir, instr, a, b): def rcr(ir, instr, a, b): e = [] - b = b.zeroExtend(a.size) - c = ExprOp('>>>c_rez', a, b, cf.zeroExtend(a.size)) - new_cf = ExprOp('>>>c_cf', a, b, cf.zeroExtend(a.size))[:1] + shifter = get_shift(a, b) + c = ExprOp('>>>c_rez', a, shifter, cf.zeroExtend(a.size)) + new_cf = ExprOp('>>>c_cf', a, shifter, cf.zeroExtend(a.size))[:1] e.append(ExprAff(cf, new_cf)) # hack (only valid if b=1) @@ -366,17 +378,6 @@ def rcr(ir, instr, a, b): return None, e, [] -def get_shift(a, b): - # b.size must match a - b = b.zeroExtend(a.size) - if a.size == 64: - shift = b & ExprInt_from(b, 0x3f) - else: - shift = b & ExprInt_from(b, 0x1f) - shift = expr_simp(shift) - return shift - - def sar(ir, instr, a, b): shifter = get_shift(a, b) diff --git a/miasm2/expression/simplifications.py b/miasm2/expression/simplifications.py index 756df880..d633cf3e 100644 --- a/miasm2/expression/simplifications.py +++ b/miasm2/expression/simplifications.py @@ -1,511 +1,11 @@ -# -# Simplification methods library # -# - -from miasm2.expression.expression import * -from miasm2.expression.expression_helper import * - -# Common passes -# ------------- - - -def simp_cst_propagation(e_s, e): - """This passe includes: - - Constant folding - - Common logical identities - - Common binary identities - """ - - # merge associatif op - if not isinstance(e, ExprOp): - return e - args = list(e.args) - op = e.op - # simpl integer manip - # int OP int => int - - # TODO: <<< >>> << >> may be architecture dependant!! - if op in op_propag_cst: - while (len(args) >= 2 and - isinstance(args[-1], ExprInt) and - isinstance(args[-2], ExprInt)): - i2 = args.pop() - i1 = args.pop() - if op == '+': - o = i1.arg + i2.arg - elif op == '*': - o = i1.arg * i2.arg - elif op == '^': - o = i1.arg ^ i2.arg - elif op == '&': - o = i1.arg & i2.arg - elif op == '|': - o = i1.arg | i2.arg - elif op == '>>': - o = i1.arg >> i2.arg - elif op == '<<': - o = i1.arg << i2.arg - elif op == 'a>>': - x1 = mod_size2int[i1.arg.size](i1.arg) - x2 = mod_size2int[i2.arg.size](i2.arg) - o = mod_size2uint[i1.arg.size](x1 >> x2) - elif op == '>>>': - rounds = i2.arg % i1.size - o = i1.arg >> rounds | i1.arg << (i1.size - rounds) - elif op == '<<<': - rounds = i2.arg % i1.size - o = i1.arg << rounds | i1.arg >> (i1.size - rounds) - elif op == '/': - o = i1.arg / i2.arg - elif op == '%': - o = i1.arg % i2.arg - elif op == 'idiv': - assert(i2.arg) - x1 = mod_size2int[i1.arg.size](i1.arg) - x2 = mod_size2int[i2.arg.size](i2.arg) - o = mod_size2uint[i1.arg.size](x1 / x2) - elif op == 'irem': - assert(i2.arg) - x1 = mod_size2int[i1.arg.size](i1.arg) - x2 = mod_size2int[i2.arg.size](i2.arg) - o = mod_size2uint[i1.arg.size](x1 % x2) - - o = ExprInt_fromsize(i1.size, o) - args.append(o) - - # bsf(int) => int - if op == "bsf" and isinstance(args[0], ExprInt) and args[0].arg != 0: - i = 0 - while args[0].arg & (1 << i) == 0: - i += 1 - return ExprInt_from(args[0], i) - - # bsr(int) => int - if op == "bsr" and isinstance(args[0], ExprInt) and args[0].arg != 0: - i = args[0].size - 1 - while args[0].arg & (1 << i) == 0: - i -= 1 - return ExprInt_from(args[0], i) - - # -(-(A)) => A - if op == '-' and len(args) == 1 and isinstance(args[0], ExprOp) and \ - args[0].op == '-' and len(args[0].args) == 1: - return args[0].args[0] - - # -(int) => -int - if op == '-' and len(args) == 1 and isinstance(args[0], ExprInt): - return ExprInt(-args[0].arg) - # A op 0 =>A - if op in ['+', '-', '|', "^", "<<", ">>", "<<<", ">>>"] and len(args) > 1: - if isinstance(args[-1], ExprInt) and args[-1].arg == 0: - args.pop() - # A * 1 =>A - if op == "*" and len(args) > 1: - if isinstance(args[-1], ExprInt) and args[-1].arg == 1: - args.pop() - - # for cannon form - # A * -1 => - A - if op == "*" and len(args) > 1: - if (isinstance(args[-1], ExprInt) and - args[-1].arg == (1 << args[-1].size) - 1): - args.pop() - args[-1] = - args[-1] - - # op A => A - if op in ['+', '*', '^', '&', '|', '>>', '<<', - 'a>>', '<<<', '>>>', 'idiv', 'irem'] and len(args) == 1: - return args[0] - - # A-B => A + (-B) - if op == '-' and len(args) > 1: - if len(args) > 2: - raise ValueError( - 'sanity check fail on expr -: should have one or 2 args ' + - '%r %s' % (e, e)) - return ExprOp('+', args[0], -args[1]) - - # A op 0 => 0 - if op in ['&', "*"] and isinstance(args[1], ExprInt) and args[1].arg == 0: - return ExprInt_from(e, 0) - - # - (A + B +...) => -A + -B + -C - if (op == '-' and - len(args) == 1 and - isinstance(args[0], ExprOp) and - args[0].op == '+'): - args = [-a for a in args[0].args] - e = ExprOp('+', *args) - return e - - # -(a?int1:int2) => (a?-int1:-int2) - if (op == '-' and - len(args) == 1 and - isinstance(args[0], ExprCond) and - isinstance(args[0].src1, ExprInt) and - isinstance(args[0].src2, ExprInt)): - i1 = args[0].src1 - i2 = args[0].src2 - i1 = ExprInt_from(i1, -i1.arg) - i2 = ExprInt_from(i2, -i2.arg) - return ExprCond(args[0].cond, i1, i2) - - i = 0 - while i < len(args) - 1: - j = i + 1 - while j < len(args): - # A ^ A => 0 - if op == '^' and args[i] == args[j]: - args[i] = ExprInt_from(args[i], 0) - del(args[j]) - continue - # A + (- A) => 0 - if op == '+' and isinstance(args[j], ExprOp) and args[j].op == "-": - if len(args[j].args) == 1 and args[i] == args[j].args[0]: - args[i] = ExprInt_from(args[i], 0) - del(args[j]) - continue - # (- A) + A => 0 - if op == '+' and isinstance(args[i], ExprOp) and args[i].op == "-": - if len(args[i].args) == 1 and args[j] == args[i].args[0]: - args[i] = ExprInt_from(args[i], 0) - del(args[j]) - continue - # A | A => A - if op == '|' and args[i] == args[j]: - del(args[j]) - continue - # A & A => A - if op == '&' and args[i] == args[j]: - del(args[j]) - continue - j += 1 - i += 1 - - if op in ['|', '&', '%', '/'] and len(args) == 1: - return args[0] - - # A <<< A.size => A - if (op in ['<<<', '>>>'] and - isinstance(args[1], ExprInt) and - args[1].arg == args[0].size): - return args[0] - - # A <<< X <<< Y => A <<< (X+Y) (ou <<< >>>) - if (op in ['<<<', '>>>'] and - isinstance(args[0], ExprOp) and - args[0].op in ['<<<', '>>>']): - op1 = op - op2 = args[0].op - if op1 == op2: - op = op1 - args1 = args[0].args[1] + args[1] - else: - op = op2 - args1 = args[0].args[1] - args[1] - - args0 = args[0].args[0] - args = [args0, args1] - - # ((A & A.mask) - if op == "&" and args[-1] == e.mask: - return ExprOp('&', *args[:-1]) - - # ((A | A.mask) - if op == "|" and args[-1] == e.mask: - return args[-1] - - # ! (!X + int) => X - int - # TODO - - # ((A & mask) >> shift) whith mask < 2**shift => 0 - if (op == ">>" and - isinstance(args[1], ExprInt) and - isinstance(args[0], ExprOp) and args[0].op == "&"): - if (isinstance(args[0].args[1], ExprInt) and - 2 ** args[1].arg >= args[0].args[1].arg): - return ExprInt_from(args[0], 0) - - # int == int => 0 or 1 - if (op == '==' and - isinstance(args[0], ExprInt) and - isinstance(args[1], ExprInt)): - if args[0].arg == args[1].arg: - return ExprInt_from(args[0], 1) - else: - return ExprInt_from(args[0], 0) - #(A|int == 0) => 0 with int != 0 - if op == '==' and isinstance(args[1], ExprInt) and args[1].arg == 0: - if isinstance(args[0], ExprOp) and args[0].op == '|' and\ - isinstance(args[0].args[1], ExprInt) and \ - args[0].args[1].arg != 0: - return ExprInt_from(args[0], 0) - - # parity(int) => int - if op == 'parity' and isinstance(args[0], ExprInt): - return ExprInt1(parity(args[0].arg)) - - # (-a) * b * (-c) * (-d) => (-a) * b * c * d - if op == "*" and len(args) > 1: - new_args = [] - counter = 0 - for a in args: - if isinstance(a, ExprOp) and a.op == '-' and len(a.args) == 1: - new_args.append(a.args[0]) - counter += 1 - else: - new_args.append(a) - if counter % 2: - return -ExprOp(op, *new_args) - args = new_args - - return ExprOp(op, *args) - - -def simp_cond_op_int(e_s, e): - "Extract conditions from operations" - - if not isinstance(e, ExprOp): - return e - if not e.op in ["+", "|", "^", "&", "*", '<<', '>>', 'a>>']: - return e - if len(e.args) < 2: - return e - if not isinstance(e.args[-1], ExprInt): - return e - a_int = e.args[-1] - conds = [] - for a in e.args[:-1]: - if not isinstance(a, ExprCond): - return e - conds.append(a) - if not conds: - return e - c = conds.pop() - c = ExprCond(c.cond, - ExprOp(e.op, c.src1, a_int), - ExprOp(e.op, c.src2, a_int)) - conds.append(c) - new_e = ExprOp(e.op, *conds) - return new_e - - -def simp_cond_factor(e_s, e): - "Merge similar conditions" - if not isinstance(e, ExprOp): - return e - if not e.op in ["+", "|", "^", "&", "*", '<<', '>>', 'a>>']: - return e - if len(e.args) < 2: - return e - conds = {} - not_conds = [] - multi_cond = False - for a in e.args: - if not isinstance(a, ExprCond): - not_conds.append(a) - continue - c = a.cond - if not c in conds: - conds[c] = [] - else: - multi_cond = True - conds[c].append(a) - if not multi_cond: - return e - c_out = not_conds[:] - for c, vals in conds.items(): - new_src1 = [x.src1 for x in vals] - new_src2 = [x.src2 for x in vals] - src1 = e_s.expr_simp_wrapper(ExprOp(e.op, *new_src1)) - src2 = e_s.expr_simp_wrapper(ExprOp(e.op, *new_src2)) - c_out.append(ExprCond(c, src1, src2)) - - if len(c_out) == 1: - new_e = c_out[0] - else: - new_e = ExprOp(e.op, *c_out) - return new_e - - -def simp_slice(e_s, e): - "Slice optimization" - - # slice(A, 0, a.size) => A - if e.start == 0 and e.stop == e.arg.size: - return e.arg - # Slice(int) => int - elif isinstance(e.arg, ExprInt): - total_bit = e.stop - e.start - mask = (1 << (e.stop - e.start)) - 1 - return ExprInt_fromsize(total_bit, (e.arg.arg >> e.start) & mask) - # Slice(Slice(A, x), y) => Slice(A, z) - elif isinstance(e.arg, ExprSlice): - if e.stop - e.start > e.arg.stop - e.arg.start: - raise ValueError('slice in slice: getting more val', str(e)) - - new_e = ExprSlice(e.arg.arg, e.start + e.arg.start, - e.start + e.arg.start + (e.stop - e.start)) - return new_e - # Slice(Compose(A), x) => Slice(A, y) - elif isinstance(e.arg, ExprCompose): - for a in e.arg.args: - if a[1] <= e.start and a[2] >= e.stop: - new_e = a[0][e.start - a[1]:e.stop - a[1]] - return new_e - # ExprMem(x, size)[:A] => ExprMem(x, a) - # XXXX todo hum, is it safe? - elif (isinstance(e.arg, ExprMem) and - e.start == 0 and - e.arg.size > e.stop and e.stop % 8 == 0): - e = ExprMem(e.arg.arg, size=e.stop) - return e - # distributivity of slice and & - # (a & int)[x:y] => 0 if int[x:y] == 0 - elif (isinstance(e.arg, ExprOp) and - e.arg.op == "&" and - isinstance(e.arg.args[-1], ExprInt)): - tmp = e_s.expr_simp_wrapper(e.arg.args[-1][e.start:e.stop]) - if isinstance(tmp, ExprInt) and tmp.arg == 0: - return tmp - # distributivity of slice and exprcond - # (a?int1:int2)[x:y] => (a?int1[x:y]:int2[x:y]) - elif (isinstance(e.arg, ExprCond) and - isinstance(e.arg.src1, ExprInt) and - isinstance(e.arg.src2, ExprInt)): - src1 = e.arg.src1[e.start:e.stop] - src2 = e.arg.src2[e.start:e.stop] - e = ExprCond(e.arg.cond, src1, src2) - - # (a * int)[0:y] => (a[0:y] * int[0:y]) - elif (isinstance(e.arg, ExprOp) and - e.arg.op == "*" and - isinstance(e.arg.args[-1], ExprInt)): - args = [e_s.expr_simp_wrapper(a[e.start:e.stop]) for a in e.arg.args] - e = ExprOp(e.arg.op, *args) - - return e - - -def simp_compose(e_s, e): - "Commons simplification on ExprCompose" - args = merge_sliceto_slice(e.args) - out = [] - # compose of compose - for a in args: - if isinstance(a[0], ExprCompose): - for x, start, stop in a[0].args: - out.append((x, start + a[1], stop + a[1])) - else: - out.append(a) - args = out - # Compose(a) with a.size = compose.size => a - if len(args) == 1 and args[0][1] == 0 and args[0][2] == e.size: - return args[0][0] - - # {(X[X.size-z, 0, z), (0, z, X.size)} => (X >> x) - if (len(args) == 2 and - isinstance(args[1][0], ExprInt) and - args[1][0].arg == 0): - a1 = args[0] - a2 = args[1] - if (isinstance(a1[0], ExprSlice) and - a1[1] == 0 and a1[0].stop == a1[0].arg.size): - if a2[1] == a1[0].size and a2[2] == a1[0].arg.size: - new_e = a1[0].arg >> ExprInt_fromsize( - a1[0].arg.size, a1[0].start) - return new_e - - # Compose with ExprCond with integers for src1/src2 and intergers => - # propagage integers - # {XXX?(0x0,0x1)?(0x0,0x1),0,8, 0x0,8,32} => XXX?(int1, int2) - - ok = True - expr_cond = None - expr_ints = [] - for i, a in enumerate(args): - if not is_int_or_cond_src_int(a[0]): - ok = False - break - expr_ints.append(a) - if isinstance(a[0], ExprCond): - if expr_cond is not None: - ok = False - expr_cond = i - cond = a[0] - - if ok and expr_cond is not None: - src1 = [] - src2 = [] - for i, a in enumerate(expr_ints): - if i == expr_cond: - src1.append((a[0].src1, a[1], a[2])) - src2.append((a[0].src2, a[1], a[2])) - else: - src1.append(a) - src2.append(a) - src1 = e_s.apply_simp(ExprCompose(src1)) - src2 = e_s.apply_simp(ExprCompose(src2)) - if isinstance(src1, ExprInt) and isinstance(src2, ExprInt): - return ExprCond(cond.cond, src1, src2) - return ExprCompose(args) - - -def simp_cond(e_s, e): - "Common simplifications on ExprCond" - if not isinstance(e, ExprCond): - return e - # eval exprcond src1/src2 with satifiable/unsatisfiable condition - # propagation - if (not isinstance(e.cond, ExprInt)) and e.cond.size == 1: - src1 = e.src1.replace_expr({e.cond: ExprInt1(1)}) - src2 = e.src2.replace_expr({e.cond: ExprInt1(0)}) - if src1 != e.src1 or src2 != e.src2: - return ExprCond(e.cond, src1, src2) - - # -A ? B:C => A ? B:C - if (isinstance(e.cond, ExprOp) and - e.cond.op == '-' and - len(e.cond.args) == 1): - e = ExprCond(e.cond.args[0], e.src1, e.src2) - # a?x:x - elif e.src1 == e.src2: - e = e.src1 - # int ? A:B => A or B - elif isinstance(e.cond, ExprInt): - if e.cond.arg == 0: - e = e.src2 - else: - e = e.src1 - # a?(a?b:c):x => a?b:x - elif isinstance(e.src1, ExprCond) and e.cond == e.src1.cond: - e = ExprCond(e.cond, e.src1.src1, e.src2) - # a?x:(a?b:c) => a?x:c - elif isinstance(e.src2, ExprCond) and e.cond == e.src2.cond: - e = ExprCond(e.cond, e.src1, e.src2.src2) - # a|int ? b:c => b with int != 0 - elif (isinstance(e.cond, ExprOp) and - e.cond.op == '|' and - isinstance(e.cond.args[1], ExprInt) and - e.cond.args[1].arg != 0): - return e.src1 - - # (C?int1:int2)?(A:B) => - elif (isinstance(e.cond, ExprCond) and - isinstance(e.cond.src1, ExprInt) and - isinstance(e.cond.src2, ExprInt)): - int1 = e.cond.src1.arg.arg - int2 = e.cond.src2.arg.arg - if int1 and int2: - e = e.src1 - elif int1 == 0 and int2 == 0: - e = e.src2 - elif int1 == 0 and int2: - e = ExprCond(e.cond.cond, e.src2, e.src1) - elif int1 and int2 == 0: - e = ExprCond(e.cond.cond, e.src1, e.src2) - return e +# # +# Simplification methods library # +# # +from miasm2.expression import simplifications_common +from miasm2.expression import simplifications_cond +from miasm2.expression.expression_helper import fast_unify +import miasm2.expression.expression as m2_expr # Expression Simplifier # --------------------- @@ -524,17 +24,26 @@ class ExpressionSimplifier(object): # Common passes PASS_COMMONS = { - m2_expr.ExprOp: [simp_cst_propagation, - simp_cond_op_int, - simp_cond_factor], - m2_expr.ExprSlice: [simp_slice], - m2_expr.ExprCompose: [simp_compose], - m2_expr.ExprCond: [simp_cond], + m2_expr.ExprOp: [simplifications_common.simp_cst_propagation, + simplifications_common.simp_cond_op_int, + simplifications_common.simp_cond_factor], + m2_expr.ExprSlice: [simplifications_common.simp_slice], + m2_expr.ExprCompose: [simplifications_common.simp_compose], + m2_expr.ExprCond: [simplifications_common.simp_cond], } # Heavy passes PASS_HEAVY = {} + # Cond passes + PASS_COND = {m2_expr.ExprSlice: [simplifications_cond.expr_simp_inf_signed, + simplifications_cond.expr_simp_inf_unsigned_inversed], + m2_expr.ExprOp: [simplifications_cond.exec_inf_unsigned, + simplifications_cond.exec_inf_signed, + simplifications_cond.expr_simp_inverse], + } + + def __init__(self): self.expr_simp_cb = {} diff --git a/miasm2/expression/simplifications_common.py b/miasm2/expression/simplifications_common.py new file mode 100644 index 00000000..c907fe84 --- /dev/null +++ b/miasm2/expression/simplifications_common.py @@ -0,0 +1,503 @@ +# ----------------------------- # +# Common simplifications passes # +# ----------------------------- # + + +from miasm2.expression.expression import * +from miasm2.expression.expression_helper import * + + +def simp_cst_propagation(e_s, e): + """This passe includes: + - Constant folding + - Common logical identities + - Common binary identities + """ + + # merge associatif op + if not isinstance(e, ExprOp): + return e + args = list(e.args) + op = e.op + # simpl integer manip + # int OP int => int + # TODO: <<< >>> << >> are architecture dependant + if op in op_propag_cst: + while (len(args) >= 2 and + isinstance(args[-1], ExprInt) and + isinstance(args[-2], ExprInt)): + i2 = args.pop() + i1 = args.pop() + if op == '+': + o = i1.arg + i2.arg + elif op == '*': + o = i1.arg * i2.arg + elif op == '^': + o = i1.arg ^ i2.arg + elif op == '&': + o = i1.arg & i2.arg + elif op == '|': + o = i1.arg | i2.arg + elif op == '>>': + o = i1.arg >> i2.arg + elif op == '<<': + o = i1.arg << i2.arg + elif op == 'a>>': + x1 = mod_size2int[i1.arg.size](i1.arg) + x2 = mod_size2int[i2.arg.size](i2.arg) + o = mod_size2uint[i1.arg.size](x1 >> x2) + elif op == '>>>': + rounds = i2.arg + o = i1.arg >> i2.arg | i1.arg << (i1.size - i2.arg) + elif op == '<<<': + o = i1.arg << i2.arg | i1.arg >> (i1.size - i2.arg) + elif op == '/': + o = i1.arg / i2.arg + elif op == '%': + o = i1.arg % i2.arg + elif op == 'idiv': + assert(i2.arg) + x1 = mod_size2int[i1.arg.size](i1.arg) + x2 = mod_size2int[i2.arg.size](i2.arg) + o = mod_size2uint[i1.arg.size](x1 / x2) + elif op == 'irem': + assert(i2.arg) + x1 = mod_size2int[i1.arg.size](i1.arg) + x2 = mod_size2int[i2.arg.size](i2.arg) + o = mod_size2uint[i1.arg.size](x1 % x2) + + o = ExprInt_fromsize(i1.size, o) + args.append(o) + + # bsf(int) => int + if op == "bsf" and isinstance(args[0], ExprInt) and args[0].arg != 0: + i = 0 + while args[0].arg & (1 << i) == 0: + i += 1 + return ExprInt_from(args[0], i) + + # bsr(int) => int + if op == "bsr" and isinstance(args[0], ExprInt) and args[0].arg != 0: + i = args[0].size - 1 + while args[0].arg & (1 << i) == 0: + i -= 1 + return ExprInt_from(args[0], i) + + # -(-(A)) => A + if op == '-' and len(args) == 1 and isinstance(args[0], ExprOp) and \ + args[0].op == '-' and len(args[0].args) == 1: + return args[0].args[0] + + # -(int) => -int + if op == '-' and len(args) == 1 and isinstance(args[0], ExprInt): + return ExprInt(-args[0].arg) + # A op 0 =>A + if op in ['+', '-', '|', "^", "<<", ">>", "<<<", ">>>"] and len(args) > 1: + if isinstance(args[-1], ExprInt) and args[-1].arg == 0: + args.pop() + # A * 1 =>A + if op == "*" and len(args) > 1: + if isinstance(args[-1], ExprInt) and args[-1].arg == 1: + args.pop() + + # for cannon form + # A * -1 => - A + if op == "*" and len(args) > 1: + if (isinstance(args[-1], ExprInt) and + args[-1].arg == (1 << args[-1].size) - 1): + args.pop() + args[-1] = - args[-1] + + # op A => A + if op in ['+', '*', '^', '&', '|', '>>', '<<', + 'a>>', '<<<', '>>>', 'idiv', 'irem'] and len(args) == 1: + return args[0] + + # A-B => A + (-B) + if op == '-' and len(args) > 1: + if len(args) > 2: + raise ValueError( + 'sanity check fail on expr -: should have one or 2 args ' + + '%r %s' % (e, e)) + return ExprOp('+', args[0], -args[1]) + + # A op 0 => 0 + if op in ['&', "*"] and isinstance(args[1], ExprInt) and args[1].arg == 0: + return ExprInt_from(e, 0) + + # - (A + B +...) => -A + -B + -C + if (op == '-' and + len(args) == 1 and + isinstance(args[0], ExprOp) and + args[0].op == '+'): + args = [-a for a in args[0].args] + e = ExprOp('+', *args) + return e + + # -(a?int1:int2) => (a?-int1:-int2) + if (op == '-' and + len(args) == 1 and + isinstance(args[0], ExprCond) and + isinstance(args[0].src1, ExprInt) and + isinstance(args[0].src2, ExprInt)): + i1 = args[0].src1 + i2 = args[0].src2 + i1 = ExprInt_from(i1, -i1.arg) + i2 = ExprInt_from(i2, -i2.arg) + return ExprCond(args[0].cond, i1, i2) + + i = 0 + while i < len(args) - 1: + j = i + 1 + while j < len(args): + # A ^ A => 0 + if op == '^' and args[i] == args[j]: + args[i] = ExprInt_from(args[i], 0) + del(args[j]) + continue + # A + (- A) => 0 + if op == '+' and isinstance(args[j], ExprOp) and args[j].op == "-": + if len(args[j].args) == 1 and args[i] == args[j].args[0]: + args[i] = ExprInt_from(args[i], 0) + del(args[j]) + continue + # (- A) + A => 0 + if op == '+' and isinstance(args[i], ExprOp) and args[i].op == "-": + if len(args[i].args) == 1 and args[j] == args[i].args[0]: + args[i] = ExprInt_from(args[i], 0) + del(args[j]) + continue + # A | A => A + if op == '|' and args[i] == args[j]: + del(args[j]) + continue + # A & A => A + if op == '&' and args[i] == args[j]: + del(args[j]) + continue + j += 1 + i += 1 + + if op in ['|', '&', '%', '/'] and len(args) == 1: + return args[0] + + # A <<< A.size => A + if (op in ['<<<', '>>>'] and + isinstance(args[1], ExprInt) and + args[1].arg == args[0].size): + return args[0] + + # A <<< X <<< Y => A <<< (X+Y) (ou <<< >>>) + if (op in ['<<<', '>>>'] and + isinstance(args[0], ExprOp) and + args[0].op in ['<<<', '>>>']): + op1 = op + op2 = args[0].op + if op1 == op2: + op = op1 + args1 = args[0].args[1] + args[1] + else: + op = op2 + args1 = args[0].args[1] - args[1] + + args0 = args[0].args[0] + args = [args0, args1] + + # ((A & A.mask) + if op == "&" and args[-1] == e.mask: + return ExprOp('&', *args[:-1]) + + # ((A | A.mask) + if op == "|" and args[-1] == e.mask: + return args[-1] + + # ! (!X + int) => X - int + # TODO + + # ((A & mask) >> shift) whith mask < 2**shift => 0 + if (op == ">>" and + isinstance(args[1], ExprInt) and + isinstance(args[0], ExprOp) and args[0].op == "&"): + if (isinstance(args[0].args[1], ExprInt) and + 2 ** args[1].arg >= args[0].args[1].arg): + return ExprInt_from(args[0], 0) + + # int == int => 0 or 1 + if (op == '==' and + isinstance(args[0], ExprInt) and + isinstance(args[1], ExprInt)): + if args[0].arg == args[1].arg: + return ExprInt_from(args[0], 1) + else: + return ExprInt_from(args[0], 0) + #(A|int == 0) => 0 with int != 0 + if op == '==' and isinstance(args[1], ExprInt) and args[1].arg == 0: + if isinstance(args[0], ExprOp) and args[0].op == '|' and\ + isinstance(args[0].args[1], ExprInt) and \ + args[0].args[1].arg != 0: + return ExprInt_from(args[0], 0) + + # parity(int) => int + if op == 'parity' and isinstance(args[0], ExprInt): + return ExprInt1(parity(args[0].arg)) + + # (-a) * b * (-c) * (-d) => (-a) * b * c * d + if op == "*" and len(args) > 1: + new_args = [] + counter = 0 + for a in args: + if isinstance(a, ExprOp) and a.op == '-' and len(a.args) == 1: + new_args.append(a.args[0]) + counter += 1 + else: + new_args.append(a) + if counter % 2: + return -ExprOp(op, *new_args) + args = new_args + + return ExprOp(op, *args) + + +def simp_cond_op_int(e_s, e): + "Extract conditions from operations" + + if not isinstance(e, ExprOp): + return e + if not e.op in ["+", "|", "^", "&", "*", '<<', '>>', 'a>>']: + return e + if len(e.args) < 2: + return e + if not isinstance(e.args[-1], ExprInt): + return e + a_int = e.args[-1] + conds = [] + for a in e.args[:-1]: + if not isinstance(a, ExprCond): + return e + conds.append(a) + if not conds: + return e + c = conds.pop() + c = ExprCond(c.cond, + ExprOp(e.op, c.src1, a_int), + ExprOp(e.op, c.src2, a_int)) + conds.append(c) + new_e = ExprOp(e.op, *conds) + return new_e + + +def simp_cond_factor(e_s, e): + "Merge similar conditions" + if not isinstance(e, ExprOp): + return e + if not e.op in ["+", "|", "^", "&", "*", '<<', '>>', 'a>>']: + return e + if len(e.args) < 2: + return e + conds = {} + not_conds = [] + multi_cond = False + for a in e.args: + if not isinstance(a, ExprCond): + not_conds.append(a) + continue + c = a.cond + if not c in conds: + conds[c] = [] + else: + multi_cond = True + conds[c].append(a) + if not multi_cond: + return e + c_out = not_conds[:] + for c, vals in conds.items(): + new_src1 = [x.src1 for x in vals] + new_src2 = [x.src2 for x in vals] + src1 = e_s.expr_simp_wrapper(ExprOp(e.op, *new_src1)) + src2 = e_s.expr_simp_wrapper(ExprOp(e.op, *new_src2)) + c_out.append(ExprCond(c, src1, src2)) + + if len(c_out) == 1: + new_e = c_out[0] + else: + new_e = ExprOp(e.op, *c_out) + return new_e + + +def simp_slice(e_s, e): + "Slice optimization" + + # slice(A, 0, a.size) => A + if e.start == 0 and e.stop == e.arg.size: + return e.arg + # Slice(int) => int + elif isinstance(e.arg, ExprInt): + total_bit = e.stop - e.start + mask = (1 << (e.stop - e.start)) - 1 + return ExprInt_fromsize(total_bit, (e.arg.arg >> e.start) & mask) + # Slice(Slice(A, x), y) => Slice(A, z) + elif isinstance(e.arg, ExprSlice): + if e.stop - e.start > e.arg.stop - e.arg.start: + raise ValueError('slice in slice: getting more val', str(e)) + + new_e = ExprSlice(e.arg.arg, e.start + e.arg.start, + e.start + e.arg.start + (e.stop - e.start)) + return new_e + # Slice(Compose(A), x) => Slice(A, y) + elif isinstance(e.arg, ExprCompose): + for a in e.arg.args: + if a[1] <= e.start and a[2] >= e.stop: + new_e = a[0][e.start - a[1]:e.stop - a[1]] + return new_e + # ExprMem(x, size)[:A] => ExprMem(x, a) + # XXXX todo hum, is it safe? + elif (isinstance(e.arg, ExprMem) and + e.start == 0 and + e.arg.size > e.stop and e.stop % 8 == 0): + e = ExprMem(e.arg.arg, size=e.stop) + return e + # distributivity of slice and & + # (a & int)[x:y] => 0 if int[x:y] == 0 + elif (isinstance(e.arg, ExprOp) and + e.arg.op == "&" and + isinstance(e.arg.args[-1], ExprInt)): + tmp = e_s.expr_simp_wrapper(e.arg.args[-1][e.start:e.stop]) + if isinstance(tmp, ExprInt) and tmp.arg == 0: + return tmp + # distributivity of slice and exprcond + # (a?int1:int2)[x:y] => (a?int1[x:y]:int2[x:y]) + elif (isinstance(e.arg, ExprCond) and + isinstance(e.arg.src1, ExprInt) and + isinstance(e.arg.src2, ExprInt)): + src1 = e.arg.src1[e.start:e.stop] + src2 = e.arg.src2[e.start:e.stop] + e = ExprCond(e.arg.cond, src1, src2) + + # (a * int)[0:y] => (a[0:y] * int[0:y]) + elif (isinstance(e.arg, ExprOp) and + e.arg.op == "*" and + isinstance(e.arg.args[-1], ExprInt)): + args = [e_s.expr_simp_wrapper(a[e.start:e.stop]) for a in e.arg.args] + e = ExprOp(e.arg.op, *args) + + return e + + +def simp_compose(e_s, e): + "Commons simplification on ExprCompose" + args = merge_sliceto_slice(e.args) + out = [] + # compose of compose + for a in args: + if isinstance(a[0], ExprCompose): + for x, start, stop in a[0].args: + out.append((x, start + a[1], stop + a[1])) + else: + out.append(a) + args = out + # Compose(a) with a.size = compose.size => a + if len(args) == 1 and args[0][1] == 0 and args[0][2] == e.size: + return args[0][0] + + # {(X[X.size-z, 0, z), (0, z, X.size)} => (X >> x) + if (len(args) == 2 and + isinstance(args[1][0], ExprInt) and + args[1][0].arg == 0): + a1 = args[0] + a2 = args[1] + if (isinstance(a1[0], ExprSlice) and + a1[1] == 0 and a1[0].stop == a1[0].arg.size): + if a2[1] == a1[0].size and a2[2] == a1[0].arg.size: + new_e = a1[0].arg >> ExprInt_fromsize( + a1[0].arg.size, a1[0].start) + return new_e + + # Compose with ExprCond with integers for src1/src2 and intergers => + # propagage integers + # {XXX?(0x0,0x1)?(0x0,0x1),0,8, 0x0,8,32} => XXX?(int1, int2) + + ok = True + expr_cond = None + expr_ints = [] + for i, a in enumerate(args): + if not is_int_or_cond_src_int(a[0]): + ok = False + break + expr_ints.append(a) + if isinstance(a[0], ExprCond): + if expr_cond is not None: + ok = False + expr_cond = i + cond = a[0] + + if ok and expr_cond is not None: + src1 = [] + src2 = [] + for i, a in enumerate(expr_ints): + if i == expr_cond: + src1.append((a[0].src1, a[1], a[2])) + src2.append((a[0].src2, a[1], a[2])) + else: + src1.append(a) + src2.append(a) + src1 = e_s.apply_simp(ExprCompose(src1)) + src2 = e_s.apply_simp(ExprCompose(src2)) + if isinstance(src1, ExprInt) and isinstance(src2, ExprInt): + return ExprCond(cond.cond, src1, src2) + return ExprCompose(args) + + +def simp_cond(e_s, e): + "Common simplifications on ExprCond" + if not isinstance(e, ExprCond): + return e + # eval exprcond src1/src2 with satifiable/unsatisfiable condition + # propagation + if (not isinstance(e.cond, ExprInt)) and e.cond.size == 1: + src1 = e.src1.replace_expr({e.cond: ExprInt1(1)}) + src2 = e.src2.replace_expr({e.cond: ExprInt1(0)}) + if src1 != e.src1 or src2 != e.src2: + return ExprCond(e.cond, src1, src2) + + # -A ? B:C => A ? B:C + if (isinstance(e.cond, ExprOp) and + e.cond.op == '-' and + len(e.cond.args) == 1): + e = ExprCond(e.cond.args[0], e.src1, e.src2) + # a?x:x + elif e.src1 == e.src2: + e = e.src1 + # int ? A:B => A or B + elif isinstance(e.cond, ExprInt): + if e.cond.arg == 0: + e = e.src2 + else: + e = e.src1 + # a?(a?b:c):x => a?b:x + elif isinstance(e.src1, ExprCond) and e.cond == e.src1.cond: + e = ExprCond(e.cond, e.src1.src1, e.src2) + # a?x:(a?b:c) => a?x:c + elif isinstance(e.src2, ExprCond) and e.cond == e.src2.cond: + e = ExprCond(e.cond, e.src1, e.src2.src2) + # a|int ? b:c => b with int != 0 + elif (isinstance(e.cond, ExprOp) and + e.cond.op == '|' and + isinstance(e.cond.args[1], ExprInt) and + e.cond.args[1].arg != 0): + return e.src1 + + # (C?int1:int2)?(A:B) => + elif (isinstance(e.cond, ExprCond) and + isinstance(e.cond.src1, ExprInt) and + isinstance(e.cond.src2, ExprInt)): + int1 = e.cond.src1.arg.arg + int2 = e.cond.src2.arg.arg + if int1 and int2: + e = e.src1 + elif int1 == 0 and int2 == 0: + e = e.src2 + elif int1 == 0 and int2: + e = ExprCond(e.cond.cond, e.src2, e.src1) + elif int1 and int2 == 0: + e = ExprCond(e.cond.cond, e.src1, e.src2) + return e diff --git a/miasm2/expression/simplifications_cond.py b/miasm2/expression/simplifications_cond.py new file mode 100644 index 00000000..ee23f6db --- /dev/null +++ b/miasm2/expression/simplifications_cond.py @@ -0,0 +1,217 @@ +################################################################################ +# +# By choice, Miasm2 does not handle comparaison as a single operation, but with +# operations corresponding to comparaison computation. +# One may want to detect those comparaison; this library is designed to add them +# in Miasm2 engine thanks to : +# - Conditions computation in ExprOp +# - Simplifications to catch known condition forms +# +# Conditions currently supported : +# <u, <s +# +# Authors : Fabrice DESCLAUX (CEA/DAM), Camille MOUGEY (CEA/DAM) +# +################################################################################ + +import itertools +import miasm2.expression.expression as m2_expr + +# Define tokens +TOK_INF = "<" +TOK_INF_SIGNED = TOK_INF + "s" +TOK_INF_UNSIGNED = TOK_INF + "u" +TOK_INF_EQUAL = "<=" +TOK_INF_EQUAL_SIGNED = TOK_INF_EQUAL + "s" +TOK_INF_EQUAL_UNSIGNED = TOK_INF_EQUAL + "u" +TOK_EQUAL = "==" +TOK_POS = "pos" +TOK_POS_STRICT = "Spos" + +# Jokers for expression matching + +jok1 = m2_expr.ExprId("jok1") +jok2 = m2_expr.ExprId("jok2") +jok3 = m2_expr.ExprId("jok3") +jok_small = m2_expr.ExprId("jok_small", 1) + + +# Constructors + +def __ExprOp_cond(op, arg1, arg2): + "Return an ExprOp standing for arg1 op arg2 with size to 1" + ec = m2_expr.ExprOp(op, arg1, arg2) + ec._size = 1 + return ec + + +def ExprOp_inf_signed(arg1, arg2): + "Return an ExprOp standing for arg1 <s arg2" + return __ExprOp_cond(TOK_INF_SIGNED, arg1, arg2) + + +def ExprOp_inf_unsigned(arg1, arg2): + "Return an ExprOp standing for arg1 <s arg2" + return __ExprOp_cond(TOK_INF_UNSIGNED, arg1, arg2) + + +# Catching conditions forms + +def __check_msb(e): + """If @e stand for the most significant bit of its arg, return the arg; + False otherwise""" + + if not isinstance(e, m2_expr.ExprSlice): + return False + + arg = e.arg + if e.start != (arg.size - 1) or e.stop != arg.size: + return False + + return arg + +def __MatchExprWrap(e, to_match, jok_list): + "Wrapper around MatchExpr to canonize pattern" + + to_match = to_match.canonize() + + r = m2_expr.MatchExpr(e, to_match, jok_list) + if r is False: + return False + + if r == {}: + return False + + return r + +def expr_simp_inf_signed(expr_simp, e): + "((x - y) ^ ((x ^ y) & ((x - y) ^ x))) [31:32] == x <s y" + + arg = __check_msb(e) + if arg is False: + return e + + # We want jok3 = jok1 - jok2 + to_match = jok3 ^ ((jok1 ^ jok2) & (jok3 ^ jok1)) + r = __MatchExprWrap(arg, + to_match, + [jok1, jok2, jok3]) + + if r is False: + return e + + new_j3 = expr_simp(r[jok3]) + sub = expr_simp(r[jok1] - r[jok2]) + + if new_j3 == sub: + return ExprOp_inf_signed(r[jok1], r[jok2]) + else: + return e + +def expr_simp_inf_unsigned_inversed(expr_simp, e): + "((x - y) ^ ((x ^ y) & ((x - y) ^ x))) ^ x ^ y [31:32] == x <u y" + + arg = __check_msb(e) + if arg is False: + return e + + # We want jok3 = jok1 - jok2 + to_match = jok3 ^ ((jok1 ^ jok2) & (jok3 ^ jok1)) ^ jok1 ^ jok2 + r = __MatchExprWrap(arg, + to_match, + [jok1, jok2, jok3]) + + if r is False: + return e + + new_j3 = expr_simp(r[jok3]) + sub = expr_simp(r[jok1] - r[jok2]) + + if new_j3 == sub: + return ExprOp_inf_unsigned(r[jok1], r[jok2]) + else: + return e + +def expr_simp_inverse(expr_simp, e): + """(x <u y) ^ ((x ^ y) [31:32]) == x <s y, + (x <s y) ^ ((x ^ y) [31:32]) == x <u y""" + + to_match = (ExprOp_inf_unsigned(jok1, jok2) ^ jok_small) + r = __MatchExprWrap(e, + to_match, + [jok1, jok2, jok_small]) + + # Check for 2 symetric cases + if r is False: + to_match = (ExprOp_inf_signed(jok1, jok2) ^ jok_small) + r = __MatchExprWrap(e, + to_match, + [jok1, jok2, jok_small]) + + if r is False: + return e + cur_sig = TOK_INF_SIGNED + else: + cur_sig = TOK_INF_UNSIGNED + + + arg = __check_msb(r[jok_small]) + if arg is False: + return e + + if not isinstance(arg, m2_expr.ExprOp) or arg.op != "^": + return e + + op_args = arg.args + if len(op_args) != 2: + return e + + if r[jok1] not in op_args or r[jok2] not in op_args: + return e + + if cur_sig == TOK_INF_UNSIGNED: + return ExprOp_inf_signed(r[jok1], r[jok2]) + else: + return ExprOp_inf_unsigned(r[jok1], r[jok2]) + + +# Compute conditions + +def exec_inf_unsigned(expr_simp, e): + "Compute x <u y" + if e.op != TOK_INF_UNSIGNED: + return e + + arg1, arg2 = e.args + + if isinstance(arg1, m2_expr.ExprInt) and isinstance(arg2, m2_expr.ExprInt): + return m2_expr.ExprInt1(1) if (arg1.arg < arg2.arg) else m2_expr.ExprInt1(0) + else: + return e + + +def __comp_signed(arg1, arg2): + """Return ExprInt1(1) if arg1 <s arg2 else ExprInt1(0) + @arg1, @arg2: ExprInt""" + + val1 = arg1.arg + if val1 >> (arg1.size - 1) == 1: + val1 = - (arg1.mask.arg ^ val1 + 1) + + val2 = arg2.arg + if val2 >> (arg2.size - 1) == 1: + val2 = - (arg2.mask.arg ^ val2 + 1) + + return m2_expr.ExprInt1(1) if (val1 < val2) else m2_expr.ExprInt1(0) + +def exec_inf_signed(expr_simp, e): + "Compute x <s y" + if e.op != TOK_INF_SIGNED: + return e + + arg1, arg2 = e.args + + if isinstance(arg1, m2_expr.ExprInt) and isinstance(arg2, m2_expr.ExprInt): + return __comp_signed(arg1, arg2) + else: + return e diff --git a/test/expression/simplifications.py b/test/expression/simplifications.py index 19f43d6e..ac6b796d 100644 --- a/test/expression/simplifications.py +++ b/test/expression/simplifications.py @@ -3,7 +3,8 @@ # from pdb import pm from miasm2.expression.expression import * -from miasm2.expression.simplifications import expr_simp +from miasm2.expression.simplifications import expr_simp, ExpressionSimplifier +from miasm2.expression.simplifications_cond import ExprOp_inf_signed, ExprOp_inf_unsigned # Define example objects a = ExprId('a') @@ -173,6 +174,36 @@ for e, e_check in to_test[:]: raise ValueError( 'bug in expr_simp simp(%s) is %s and should be %s' % (e, e_new, e_check)) +# Test conds + +to_test = [ + (((a - b) ^ ((a ^ b) & ((a - b) ^ a))).msb(), + ExprOp_inf_signed(a, b)), + ((((a - b) ^ ((a ^ b) & ((a - b) ^ a))) ^ a ^ b).msb(), + ExprOp_inf_unsigned(a, b)), + (ExprOp_inf_unsigned(ExprInt32(-1), ExprInt32(3)), ExprInt1(0)), + (ExprOp_inf_signed(ExprInt32(-1), ExprInt32(3)), ExprInt1(1)), + (ExprOp_inf_unsigned(a, b) ^ (a ^ b).msb(), ExprOp_inf_signed(a, b)), + (ExprOp_inf_signed(a, b) ^ (a ^ b).msb(), ExprOp_inf_unsigned(a, b)), +] + +expr_simp_cond = ExpressionSimplifier() +expr_simp.enable_passes(ExpressionSimplifier.PASS_COND) + + +for e, e_check in to_test[:]: + # + print "#" * 80 + e_check = expr_simp(e_check) + # print str(e), str(e_check) + e_new = expr_simp(e) + print "original: ", str(e), "new: ", str(e_new) + rez = e_new == e_check + if not rez: + raise ValueError( + 'bug in expr_simp simp(%s) is %s and should be %s' % (e, e_new, e_check)) + + x = ExprId('x') y = ExprId('y') |