class Metasm::Decompiler::CGraph

converts C code to a graph of cexprs (nodes = cexprs, edges = codepaths) returns a CGraph

Attributes

block[RW]

exprs: label => [exprs], to: label => [labels], block: label => are exprs in a block (vs If#test), start: 1st label

exprs[RW]

exprs: label => [exprs], to: label => [labels], block: label => are exprs in a block (vs If#test), start: 1st label

from_optim[RW]

exprs: label => [exprs], to: label => [labels], block: label => are exprs in a block (vs If#test), start: 1st label

start[RW]

exprs: label => [exprs], to: label => [labels], block: label => are exprs in a block (vs If#test), start: 1st label

to[RW]

exprs: label => [exprs], to: label => [labels], block: label => are exprs in a block (vs If#test), start: 1st label

to_optim[RW]

exprs: label => [exprs], to: label => [labels], block: label => are exprs in a block (vs If#test), start: 1st label

Public Class Methods

new() click to toggle source
# 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

build(stmt) click to toggle source
# File metasm/decompile.rb, line 2025
def build(stmt)
        @start = @anon_label
        to_graph(stmt, @start, nil, nil, nil)
        optimize
        self
end
exprs_var() click to toggle source

varname => { label => [list of indices of @exprs referencing varname] }

# File metasm/decompile.rb, line 2108
def exprs_var
        @exprs_var ||= init_exprs_var
end
get_expr_vars(e) click to toggle source

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
init_exprs_var() click to toggle source

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
invalidate(label=nil) click to toggle source

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() click to toggle source

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
to_graph(stmt, l_cur, l_after, l_cont, l_break) click to toggle source

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
update_exprs_var(label) click to toggle source

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