diff options
Diffstat (limited to 'miasm/expression')
| -rw-r--r-- | miasm/expression/expression.py | 194 | ||||
| -rw-r--r-- | miasm/expression/expression_eval_abstract.py | 28 | ||||
| -rw-r--r-- | miasm/expression/expression_helper.py | 111 |
3 files changed, 126 insertions, 207 deletions
diff --git a/miasm/expression/expression.py b/miasm/expression/expression.py index 10b5ff8e..235a79b8 100644 --- a/miasm/expression/expression.py +++ b/miasm/expression/expression.py @@ -150,13 +150,11 @@ class ExprInt(Expr): def get_size(self): return 8*self.arg.nbytes def reload_expr(self, g = {}): + if self in g: + return g[self] return ExprInt(self.arg) def __contains__(self, e): return self == e - def replace_expr(self, g = {}): - if self in g: - return g[self] - return self def __eq__(self, a): if not isinstance(a, ExprInt): return False @@ -187,15 +185,8 @@ class ExprId(Expr): return g[self] else: return ExprId(self.name, self.size) - if self in g: - return g[self] - return self def __contains__(self, e): return self == e - def replace_expr(self, g = {}): - if self in g: - return g[self] - return self def __eq__(self, a): if not isinstance(a, ExprId): return False @@ -220,10 +211,10 @@ class ExprAff(Expr): #if dst is slice=> replace with id make composed src if isinstance(dst, ExprSlice): self.dst = dst.arg - rest = [ExprSliceTo(ExprSlice(dst.arg, *r), *r) for r in slice_rest(dst.arg.size, dst.start, dst.stop)] - all_a = [(dst.start, ExprSliceTo(src, dst.start, dst.stop))]+ [(x.start, x) for x in rest] - all_a.sort() - self.src = ExprCompose([x[1] for x in all_a]) + rest = [(ExprSlice(dst.arg, r[0], r[1]), r[0], r[1]) for r in slice_rest(dst.arg.size, dst.start, dst.stop)] + all_a = [(src, dst.start, dst.stop)] + rest + all_a.sort(key=lambda x:x[1]) + self.src = ExprCompose(all_a) else: self.dst, self.src = dst,src def __str__(self): @@ -241,21 +232,11 @@ class ExprAff(Expr): def reload_expr(self, g = {}): if self in g: return g[self] - dst = self.dst - if isinstance(dst, Expr): - dst = self.dst.reload_expr(g) - src = self.src - if isinstance(src, Expr): - src = self.src.reload_expr(g) + dst = self.dst.reload_expr(g) + src = self.src.reload_expr(g) return ExprAff(dst, src ) def __contains__(self, e): return self == e or self.src.__contains__(e) or self.dst.__contains__(e) - def replace_expr(self, g = {}): - if self in g: - return g[self] - dst = self.dst.replace_expr(g) - src = self.src.replace_expr(g) - return ExprAff(dst, src) def __eq__(self, a): if not isinstance(a, ExprAff): return False @@ -271,7 +252,7 @@ class ExprAff(Expr): raise ValueError("get mod slice not on expraff slice", str(self)) modified_s = [] for x in self.src.args: - if not isinstance(x.arg, ExprSlice) or x.arg.arg != dst or x.start != x.arg.start or x.stop != x.arg.stop: + if not isinstance(x[0], ExprSlice) or x[0].arg != dst or x[1] != x[0].start or x[2] != x[0].stop: modified_s.append(x) return modified_s def canonize(self): @@ -293,23 +274,10 @@ class ExprCond(Expr): def reload_expr(self, g = {}): if self in g: return g[self] - src1 = self.src1 - if isinstance(src1, Expr): - src1 = self.src1.reload_expr(g) - src2 = self.src2 - if isinstance(src2, Expr): - src2 = self.src2.reload_expr(g) - cond = self.cond - if isinstance(cond, Expr): - cond = self.cond.reload_expr(g) - return ExprCond(cond, src1, src2 ) - def replace_expr(self, g = {}): - if self in g: - return g[self] - cond = self.cond.replace_expr(g) - src1 = self.src1.replace_expr(g) - src2 = self.src2.replace_expr(g) - return ExprCond(cond, src1, src2 ) + cond = self.cond.reload_expr(g) + src1 = self.src1.reload_expr(g) + src2 = self.src2.reload_expr(g) + return ExprCond(cond, src1, src2) def __contains__(self, e): return self == e or self.cond.__contains__(e) or self.src1.__contains__(e) or self.src2.__contains__(e) def __eq__(self, a): @@ -346,20 +314,13 @@ class ExprMem(Expr): def reload_expr(self, g = {}): if self in g: return g[self] - arg = self.arg + arg = self.arg.reload_expr(g) segm = self.segm - if isinstance(arg, Expr): - arg = self.arg.reload_expr(g) if isinstance(segm, Expr): segm = self.segm.reload_expr(g) - return ExprMem(arg, self.size, segm) + return ExprMem(arg, self.size, self.segm) def __contains__(self, e): return self == e or self.arg.__contains__(e) - def replace_expr(self, g = {}): - if self in g: - return g[self] - arg = self.arg.replace_expr(g) - return ExprMem(arg, self.size, self.segm) def __eq__(self, a): if not isinstance(a, ExprMem): return False @@ -400,10 +361,7 @@ class ExprOp(Expr): return g[self] args = [] for a in self.args: - if isinstance(a, Expr): - args.append(a.reload_expr(g)) - else: - args.append(a) + args.append(a.reload_expr(g)) return ExprOp(self.op, *args ) def __contains__(self, e): if self == e: @@ -412,13 +370,6 @@ class ExprOp(Expr): if a.__contains__(e): return True return False - def replace_expr(self, g = {}): - if self in g: - return g[self] - args = [] - for a in self.args: - args.append(a.replace_expr(g)) - return ExprOp(self.op, *args ) def __eq__(self, a): if not isinstance(a, ExprOp): return False @@ -580,6 +531,8 @@ class ExprSlice(Expr): def get_size(self): return self.stop-self.start def reload_expr(self, g = {}): + if self in g: + return g[self] arg = self.arg.reload_expr(g) return ExprSlice(arg, self.start, self.stop ) def __contains__(self, e): @@ -589,11 +542,6 @@ class ExprSlice(Expr): if a.__contains__(e): return True return False - def replace_expr(self, g = {}): - if self in g: - return g[self] - arg = self.arg.replace_expr(g) - return ExprSlice(arg, self.start, self.stop ) def __eq__(self, a): if not isinstance(a, ExprSlice): return False @@ -608,79 +556,34 @@ class ExprSlice(Expr): self.start, self.stop) -class ExprSliceTo(Expr): - def __init__(self, arg, start, stop): - self.arg, self.start, self.stop = arg, start, stop - def __str__(self): - return "%s_to[%d:%d]"%(str(self.arg), self.start, self.stop) - def get_r(self, mem_read=False): - return self.arg.get_r(mem_read) - def get_w(self): - return self.arg.get_w() - def get_size(self): - return self.stop-self.start - def reload_expr(self, g = {}): - if isinstance(self.arg, Expr): - arg = self.arg.reload_expr(g) - else: - arg = self.arg - return ExprSliceTo(arg, self.start, self.stop ) - def __contains__(self, e): - return self == e or self.arg.__contains__(e) - def replace_expr(self, g = {}): - if self in g: - return g[self] - arg = self.arg.replace_expr(g) - return ExprSliceTo(arg, self.start, self.stop) - def __eq__(self, a): - if not isinstance(a, ExprSliceTo): - return False - return self.arg == a.arg and self.start == a.start and self.stop == a.stop - def __hash__(self): - return hash(self.arg)^hash(self.start)^hash(self.stop) - def toC(self): - # XXX gen mask in python for 64 bit & 32 bit compat - return "((%s & (0xFFFFFFFF>>(32-%d))) << %d)"%(self.arg.toC(), self.stop-self.start, self.start) - def canonize(self): - return ExprSliceTo(self.arg.canonize(), - self.start, - self.stop) class ExprCompose(Expr): def __init__(self, args): self.args = args def __str__(self): - return '('+', '.join([str(x) for x in self.args])+')' + return '('+', '.join(['%s,%d,%d'%(str(x[0]), x[1], x[2]) for x in self.args])+')' def get_r(self, mem_read=False): - return reduce(lambda x,y:x.union(y.get_r(mem_read)), self.args, set()) + return reduce(lambda x,y:x.union(y[0].get_r(mem_read)), self.args, set()) def get_w(self): - return reduce(lambda x,y:x.union(y.get_r(mem_read)), self.args, set()) + return reduce(lambda x,y:x.union(y[0].get_r(mem_read)), self.args, set()) def get_size(self): - return max([x.stop for x in self.args]) - min([x.start for x in self.args]) + return max([x[2] for x in self.args]) - min([x[1] for x in self.args]) def reload_expr(self, g = {}): if self in g: return g[self] args = [] for a in self.args: - if isinstance(a, Expr): - args.append(a.reload_expr(g)) - else: - args.append(a) + args.append(a[0].reload_expr(g), a[1], a[2]) return ExprCompose(args ) def __contains__(self, e): if self == e: return True for a in self.args: - if a.__contains__(e): + if a == e: + return True + if a[0].__contains__(e): return True return False - def replace_expr(self, g = {}): - if self in g: - return g[self] - args = [] - for a in self.args: - args.append(a.replace_expr(g)) - return ExprCompose(args ) def __eq__(self, a): if not isinstance(a, ExprCompose): return False @@ -693,13 +596,22 @@ class ExprCompose(Expr): def __hash__(self): h = 0 for a in self.args: - h^=hash(a) + h^=hash(a[0])^hash(a[1])^hash(a[2]) return h def toC(self): - out = ' | '.join([x.toC() for x in self.args]) + out = [] + # XXX check mask for 64 bit & 32 bit compat + for x in self.args: + o.append("((%s & %X) << %d)"%(x[0].toC(), + (1<<(x[2]-x[1]))-1, + x[1])) + out = ' | '.join(out) return '('+out+')' def canonize(self): - return ExprCompose(canonize_expr_list([x.canonize() for x in self.args])) + o = [] + for x in self.args: + o.append((x[0].canonize(), x[1], x[2])) + return ExprCompose(canonize_expr_list_compose(o)) class set_expr: def __init__(self, l = []): @@ -751,14 +663,22 @@ expr_order_dict = {ExprId: 1, ExprMem: 3, ExprOp: 4, ExprSlice: 5, - ExprSliceTo: 6, ExprCompose: 7, ExprInt: 8, } -def compare_exprs_list(l1_e, l2_e): - for i in xrange(min(len(l1_e, l2_e))): - x = expr_compare(l1_e[i], l2_e[i]) +def compare_exprs_compose(e1, e2): + # sort by start bit address, then expr then stop but address + x = cmp(e1[1], e2[1]) + if x: return x + x = compare_exprs(e1[0], e2[0]) + if x: return x + x = cmp(e1[2], e2[2]) + return x + +def compare_expr_list_compose(l1_e, l2_e): + for i in xrange(min(len(l1_e), len(l2_e))): + x = compare_exprs_compose(l1_e, l2_e) if x: return x return cmp(len(l1_e), len(l2_e)) @@ -803,15 +723,8 @@ def compare_exprs(e1, e2): if x: return x x = cmp(e1.stop, e2.stop) return x - elif c1 == ExprSliceTo: - x = compare_exprs(e1.arg, e2.arg) - if x: return x - x = cmp(e1.start, e2.start) - if x: return x - x = cmp(e1.stop, e2.stop) - return x elif c1 == ExprCompose: - return compare_exprs_list(e1.arg, e2.arg) + return compare_expr_list_compose(e1.args, e2.args) raise ValueError("not imppl %r %r"%(e1, e2)) @@ -820,3 +733,8 @@ def canonize_expr_list(l): l = l[:] l.sort(cmp=compare_exprs) return l + +def canonize_expr_list_compose(l): + l = l[:] + l.sort(cmp=compare_exprs_compose) + return l diff --git a/miasm/expression/expression_eval_abstract.py b/miasm/expression/expression_eval_abstract.py index 809c72fd..5e2d397b 100644 --- a/miasm/expression/expression_eval_abstract.py +++ b/miasm/expression/expression_eval_abstract.py @@ -599,13 +599,13 @@ class eval_abs: m = min(a.get_size(), x.get_size()-off*8) ee = ExprSlice(self.pool[x], off*8, off*8 + m) ee = expr_simp(ee) - out.append(ExprSliceTo(ee, off_base, off_base+ee.get_size())) + out.append((ee, off_base, off_base+ee.get_size())) off_base += ee.get_size() else: m = min(a.get_size()+off*8, x.get_size()) ee = ExprSlice(self.pool[x], 0, m) ee = expr_simp(ee) - out.append(ExprSliceTo(ee, off_base, off_base+ee.get_size())) + out.append((ee, off_base, off_base+ee.get_size())) off_base += ee.get_size() if out: ee = ExprSlice(ExprCompose(out), 0, a.get_size()) @@ -636,7 +636,7 @@ class eval_abs: else: diff_size = rest val = self.pool[v][0:diff_size] - val = ExprSliceTo(val, ptr_index, ptr_index+diff_size) + val = (val, ptr_index, ptr_index+diff_size) out.append(val) ptr_index+=diff_size rest -= diff_size @@ -738,7 +738,7 @@ class eval_abs: if not is_int and is_int_cond!=1: - uu = ExprCompose([ExprSliceTo(a, e.args[i].start, e.args[i].stop) for i, a in enumerate(args)]) + uu = ExprCompose([(a, e.args[i][1], e.args[i][2]) for i, a in enumerate(args)]) return uu if not is_int: @@ -749,15 +749,15 @@ class eval_abs: if isinstance(args[i], ExprInt): a = args[i].arg - mask = (1<<(e.args[i].stop-e.args[i].start))-1 + mask = (1<<(e.args[i][2]-e.args[i][1]))-1 a&=mask - a<<=e.args[i].start - total_bit+=e.args[i].stop-e.args[i].start + a<<=e.args[i][1] + total_bit+=e.args[i][2]-e.args[i][1] rez|=a else: a = args[i] - mask = (1<<(e.args[i].stop-e.args[i].start))-1 - total_bit+=e.args[i].stop-e.args[i].start + mask = (1<<(e.args[i][2]-e.args[i][1]))-1 + total_bit+=e.args[i][2]-e.args[i][1] mycond, mysrc1, mysrc2 = a.cond, a.src1.arg&mask, a.src2.arg&mask cond_i = i @@ -767,7 +767,9 @@ class eval_abs: if total_bit in tab_uintsize: - return self.eval_expr(ExprCond(mycond, ExprInt(tab_uintsize[total_bit](mysrc1)), ExprInt(tab_uintsize[total_bit](mysrc2))), eval_cache) + return self.eval_expr(ExprCond(mycond, + ExprInt(tab_uintsize[total_bit](mysrc1)), + ExprInt(tab_uintsize[total_bit](mysrc2))), eval_cache) else: raise 'cannot return non rounb bytes rez! %X %X'%(total_bit, rez) @@ -777,10 +779,10 @@ class eval_abs: total_bit = 0 for i in xrange(len(e.args)): a = args[i].arg - mask = (1<<(e.args[i].stop-e.args[i].start))-1 + mask = (1<<(e.args[i][2]-e.args[i][1]))-1 a&=mask - a<<=e.args[i].start - total_bit+=e.args[i].stop-e.args[i].start + a<<=e.args[i][1] + total_bit+=e.args[i][2]-e.args[i][1] rez|=a if total_bit in tab_uintsize: return ExprInt(tab_uintsize[total_bit](rez)) diff --git a/miasm/expression/expression_helper.py b/miasm/expression/expression_helper.py index 324c1ca8..8cf422bb 100644 --- a/miasm/expression/expression_helper.py +++ b/miasm/expression/expression_helper.py @@ -39,56 +39,53 @@ def merge_sliceto_slice(args): non_slice = {} sources_int = {} for a in args: - if isinstance(a.arg, ExprInt): + if isinstance(a[0], ExprInt): #sources_int[a.start] = a # copy ExprInt because we will inplace modify arg just below # /!\ TODO XXX never ever modify inplace args... - sources_int[a.start] = ExprSliceTo(ExprInt(a.arg.arg.__class__(a.arg.arg)), a.start, a.stop) - elif isinstance(a.arg, ExprSlice): - if not a.arg.arg in sources: - sources[a.arg.arg] = [] - sources[a.arg.arg].append(a) + sources_int[a[1]] = (ExprInt(a[0].arg.__class__(a[0].arg)), + a[1], + a[2]) + elif isinstance(a[0], ExprSlice): + if not a[0].arg in sources: + sources[a[0].arg] = [] + sources[a[0].arg].append(a) else: - non_slice[a.start] = a + non_slice[a[1]] = a #find max stop to determine size max_size = None for a in args: - if max_size == None or max_size < a.stop: - max_size = a.stop - - + if max_size == None or max_size < a[2]: + max_size = a[2] #first simplify all num slices - final_sources = [] sorted_s = [] for x in sources_int.values(): #mask int - v = x.arg.arg & ((1<<(x.stop-x.start))-1) - x.arg.arg = v - sorted_s.append((x.start, x)) + v = x[0].arg & ((1<<(x[2]-x[1]))-1) + x[0].arg = v + sorted_s.append((x[1], x)) sorted_s.sort() - while sorted_s: + while sorted_s: start, v = sorted_s.pop() - out = expr_replace(v, {}) - - + out = e.reload_expr() while sorted_s: - if sorted_s[-1][1].stop != start: + if sorted_s[-1][1][2] != start: break - start = sorted_s[-1][1].start + start = sorted_s[-1][1][1] - a = uint64((int(out.arg.arg) << (out.start - start )) + sorted_s[-1][1].arg.arg) + a = uint64((int(out[0].arg) << (out[1] - start )) + sorted_s[-1][1][0].arg) out.arg = ExprInt(uint32(a)) sorted_s.pop() - out.start = start + out[1] = start out_type = tab_size_int[max_size] - out.arg.arg = out_type(out.arg.arg) + out[0].arg = out_type(out[0].arg) final_sources.append((start, out)) final_sources_int = final_sources @@ -100,21 +97,21 @@ def merge_sliceto_slice(args): final_sources = [] sorted_s = [] for x in args: - sorted_s.append((x.start, x)) + sorted_s.append((x[1], x)) sorted_s.sort() while sorted_s: start, v = sorted_s.pop() - out = expr_replace(v, {}) + out = v[0].reload_expr(), v[1], v[2] while sorted_s: - if sorted_s[-1][1].stop != start: + if sorted_s[-1][1][2] != start: break - if sorted_s[-1][1].arg.stop != out.arg.start: + if sorted_s[-1][1][0].stop != out[0].start: break - start = sorted_s[-1][1].start - out.arg.start = sorted_s[-1][1].arg.start + start = sorted_s[-1][1][1] + out[0].start = sorted_s[-1][1][0].start sorted_s.pop() - out.start = start + out = out[0], start, out[2] final_sources.append((start, out)) @@ -457,7 +454,7 @@ def expr_simp_w(e): #! (compose a b c) => (compose !a !b !c) if op == '!' and isinstance(args[0], ExprCompose): - args = [ExprSliceTo(ExprOp('!', x.arg), x.start, x.stop) for x in args[0].args] + args = [(ExprOp('!', x.arg), x[1], x[2]) for x in args[0].args] new_e = ExprCompose(args) return expr_simp(new_e) #!a[0:X] => (!a)[0:X] @@ -526,8 +523,8 @@ def expr_simp_w(e): return expr_simp(new_e) elif isinstance(arg, ExprCompose): for a in arg.args: - if a.start <= e.start and a.stop>=e.stop: - new_e = a.arg[e.start-a.start:e.stop-a.start] + if a[1] <= e.start and a[2]>=e.stop: + new_e = a[0][e.start-a[1]:e.stop-a[1]] new_e = expr_simp(new_e) return new_e elif isinstance(arg, ExprOp) and e.start == 0: @@ -538,7 +535,7 @@ def expr_simp_w(e): elif isinstance(arg, ExprMem) and e.start == 0 and arg.size == e.stop: e = expr_simp(arg) return e - #XXXX hum, is it safe? + #XXXX todo hum, is it safe? elif isinstance(arg, ExprMem) and e.start == 0 and arg.size > e.stop and e.stop %8 == 0: e = expr_simp(ExprMem(e.arg.arg, size = e.stop)) return e @@ -547,6 +544,8 @@ def expr_simp_w(e): return ExprSlice(arg, e.start, e.stop) + """ + XXX todo move to exprcompose elif isinstance(e, ExprSliceTo): if isinstance(e.arg, ExprTop): return ExprTop() @@ -563,9 +562,10 @@ def expr_simp_w(e): return ExprSliceTo(expr_simp(e.arg), e.start, e.stop) + """ elif isinstance(e, ExprCompose): #(.., a_to[x:y], a[:]_to[y:z], ..) => (.., a[x:z], ..) - e = ExprCompose([expr_simp(x) for x in e.args]) + e = ExprCompose([(expr_simp(x[0]), x[1], x[2]) for x in e.args]) args = [] i = -1 simp = False @@ -574,19 +574,21 @@ def expr_simp_w(e): if not args: args.append(e.args[i]) continue - if args[-1].stop != e.args[i].start: + if args[-1][2] != e.args[i][1]: continue - if not isinstance(e.args[i].arg, ExprSlice): + if not isinstance(e.args[i][0], ExprSlice): continue - if isinstance(args[-1].arg, ExprSlice): + if isinstance(args[-1][0], ExprSlice): a = args[-1] else: - a = ExprSliceTo(ExprSlice(args[-1].arg, 0, args[-1].arg.get_size()), args[-1].start, args[-1].stop) - if a.arg.arg != e.args[i].arg.arg: + a = (ExprSlice(args[-1][0], 0, args[-1][0].get_size()), + args[-1][1], + args[-1][2]) + if a[0].arg != e.args[i][0].arg: continue - if a.stop != e.args[i].start: + if a[2] != e.args[i][1]: continue - args[-1] = ExprSliceTo(e.args[i].arg.arg, a.start, e.args[i].stop) + args[-1] = (e.args[i][0].arg, a[1], e.args[i][2]) simp = True if simp: @@ -609,26 +611,24 @@ def expr_simp_w(e): args = merge_sliceto_slice(e.args) if len(args) == 1: a = args[0] - if isinstance(a.arg, ExprInt): - if a.arg.get_size() != a.stop: - print a, a.arg.get_size(), a.stop - raise ValueError("cast in compose!", e) - return a.arg - - uu = expr_simp(a.arg) + if isinstance(a[0], ExprInt): + if a[0].get_size() != a[2]: + print a, a[0].get_size(), a[2] + raise ValueError("todo cast in compose!", e) + return a[0] + uu = expr_simp(a[0][:e.get_size()]) return uu if len(args) != len(e.args): return expr_simp(ExprCompose(args)) else: return ExprCompose(args) - else: raise 'bad expr' def expr_cmp(e1, e2): return str(e1) == str(e2) - +""" #replace id by another in expr def expr_replace(e, repl): if isinstance(e, ExprInt): @@ -647,12 +647,11 @@ def expr_replace(e, repl): return ExprOp(e.op, *[expr_replace(x, repl) for x in e.args]) elif isinstance(e, ExprSlice): return ExprSlice(expr_replace(e.arg, repl), e.start, e.stop) - elif isinstance(e, ExprSliceTo): - return ExprSliceTo(expr_replace(e.arg, repl), e.start, e.stop) elif isinstance(e, ExprCompose): - return ExprCompose([expr_replace(x, repl) for x in e.args]) + return ExprCompose([(expr_replace(x[0], repl), x[1], x[2]) for x in e.args]) else: - raise 'bad expr' + raise ValueError('bad expr', e) +""" |