class Metasm::Decompiler::CGraph
converts C
code to a graph of cexprs (nodes = cexprs, edges = codepaths) returns a CGraph
Attributes
exprs: label => [exprs], to: label => [labels], block: label => are exprs in a block (vs If#test), start: 1st label
exprs: label => [exprs], to: label => [labels], block: label => are exprs in a block (vs If#test), start: 1st label
exprs: label => [exprs], to: label => [labels], block: label => are exprs in a block (vs If#test), start: 1st label
exprs: label => [exprs], to: label => [labels], block: label => are exprs in a block (vs If#test), start: 1st label
exprs: label => [exprs], to: label => [labels], block: label => are exprs in a block (vs If#test), start: 1st label
exprs: label => [exprs], to: label => [labels], block: label => are exprs in a block (vs If#test), start: 1st label
Public Class Methods
# File metasm/decompile.rb, line 2017 def initialize @exprs = {} # label => [exprs] @to = {} # label => [labels] @block = {} # label => is label in a block? (vs If#test) @anon_label = 0 # when no label is there, use anon_label++ @exprs_var = nil # similar to @exprs, indexed by var name, lazy initialization end
Public Instance Methods
# File metasm/decompile.rb, line 2025 def build(stmt) @start = @anon_label to_graph(stmt, @start, nil, nil, nil) optimize self end
varname => { label => [list of indices of @exprs referencing varname] }
# File metasm/decompile.rb, line 2108 def exprs_var @exprs_var ||= init_exprs_var end
returns the list of variable names referenced by a CExpr
# File metasm/decompile.rb, line 2113 def get_expr_vars(e) case e when C::CExpression; get_expr_vars(e.lexpr) + get_expr_vars(e.rexpr) when ::Array; e.inject([]) { |a, ee| a.concat get_expr_vars(ee) } when C::Variable; [e.name] else; [] end end
initialize @exprs_var
# File metasm/decompile.rb, line 2123 def init_exprs_var @exprs_var = {} @exprs.each_key { |label| update_exprs_var(label) } @exprs_var end
invalidates one label (eg exprs were deleted) rebuilds @exprs_var if necessary
# File metasm/decompile.rb, line 2142 def invalidate(label=nil) if @exprs_var if label @exprs_var.each { |v, h| h.delete(label) } update_exprs_var(label) else @exprs_var = nil end end end
optimize graph
# File metasm/decompile.rb, line 2089 def optimize @to_optim = {} @to.each { |k, v| @to_optim[k] = v.uniq } @exprs.delete_if { |k, v| v == [] } @to_optim.delete_if { |k, v| if v.length == 1 and not @exprs[k] and v != [k] @to_optim.each_value { |t| if i = t.index(k) ; t[i] = v.first ; end } true elsif v.length == 0 and not @exprs[k] @to_optim.each_value { |t| t.delete k } true end } @from_optim = {} @to_optim.each { |k, v| v.each { |t| (@from_optim[t] ||= []) << k } } end
converts C
code to a graph of codepath of cexprs
# File metasm/decompile.rb, line 2033 def to_graph(stmt, l_cur, l_after, l_cont, l_break) case stmt when C::Label; @to[l_cur] = [stmt.name] ; @to[stmt.name] = [l_after] when C::Goto; @to[l_cur] = [stmt.target] when C::Continue; @to[l_cur] = [l_cont] when C::Break; @to[l_cur] = [l_break] when C::CExpression @exprs[l_cur] = [stmt] @to[l_cur] = [l_after] when C::Return @exprs[l_cur] = [stmt.value] if stmt.value @to[l_cur] = [] when C::Block to_graph(stmt.statements, l_cur, l_after, l_cont, l_break) when ::Array @exprs[l_cur] = [] @block[l_cur] = true stmt.each_with_index { |s, i| case s when C::Declaration when C::CExpression @exprs[l_cur] << s else l = @anon_label += 1 ll = @anon_label += 1 @to[l_cur] = [l] @block[l_cur] = true to_graph(stmt[i], l, ll, l_cont, l_break) l_cur = ll @exprs[l_cur] = [] end } @to[l_cur] = [l_after].compact when C::If @exprs[l_cur] = [stmt.test] lt = @anon_label += 1 to_graph(stmt.bthen, lt, l_after, l_cont, l_break) le = @anon_label += 1 to_graph(stmt.belse, le, l_after, l_cont, l_break) @to[l_cur] = [lt, le] when C::While, C::DoWhile la = @anon_label += 1 if stmt.kind_of?(C::DoWhile) lt, lb = la, l_cur else lt, lb = l_cur, la end @exprs[lt] = [stmt.test] @to[lt] = [lb, l_after] to_graph(stmt.body, lb, lt, lt, l_after) when C::Asm, nil; @to[l_cur] = [l_after] else puts "to_graph unhandled #{stmt.class}: #{stmt}" if $VERBOSE end end
populate one label of @exprs_var
# File metasm/decompile.rb, line 2130 def update_exprs_var(label) @exprs[label].each_with_index { |e, idx| get_expr_vars(e).uniq.each { |varname| @exprs_var[varname] ||= {} @exprs_var[varname][label] ||= [] @exprs_var[varname][label] << idx } } end