<commit_before>require 'metasm/decode'
require 'metasm/parse_c'

module Metasm
class Decompiler
	# TODO add methods to C::CExpr
	AssignOp = [:'=', :'+=', :'-=', :'*=', :'/=', :'%=', :'^=', :'&=', :'|=', :'>>=', :'<<=', :'++', :'--']

	attr_accessor :dasm, :c_parser

	def initialize(dasm, cp = dasm.c_parser)
		@dasm = dasm
		@c_parser = cp || @dasm.cpu.new_cparser
	end

	# decompile recursively function from an entrypoint, then perform global optimisation (static vars, ...)
	# should be called once after everything is decompiled (global optimizations may bring bad results otherwise)
	# use decompile_func for incremental decompilation
	# returns the c_parser
	def decompile(*entry)
		entry.each { |f| decompile_func(f) }
		optimize_global
		@c_parser
	end

	# decompile a function, decompiling subfunctions as needed
	# may return :restart, which means that the decompilation should restart from the entrypoint (and bubble up) (eg a new codepath is found which may changes dependency in blocks etc)
	def decompile_func(entry)
		entry = @dasm.normalize entry
		return if not @dasm.decoded[entry]

		# create a new toplevel function to hold our code
		func = C::Variable.new
		func.name = @dasm.auto_label_at(entry, 'func')
		func.type = C::Function.new C::BaseType.new(:int)
		if @c_parser.toplevel.symbol[func.name]
			if not @c_parser.toplevel.statements.grep(C::Declaration).find { |decl| decl.var.name == func.name }
				# recursive dependency: declare prototype
				@c_parser.toplevel.statements << C::Declaration.new(func)
			end
			return
		end
		@c_parser.toplevel.symbol[func.name] = func
		puts "decompiling #{Expression[entry]}" if $VERBOSE

		while catch(:restart) { do_decompile_func(entry, func) } == :restart
			retval = :restart
		end

		@c_parser.toplevel.statements << C::Declaration.new(func)

		retval
	end

	def do_decompile_func(entry, func)
		# TODO check ABI conformance between func start&end (saved regs, stack offset, __declspec, ...)
		# TODO handle jmp tables

		# find decodedinstruction blocks constituing the function
		# TODO merge sequencial blocks with useless jmp (poeut) to improve dependency graph later
		myblocks = listblocks_func(entry)

		# [esp+8] => [:frameptr-12]
		makestackvars entry, myblocks.map { |b, to| @dasm.decoded[b].block }

		# find registry dependencies between blocks
		deps = @dasm.cpu.decompile_func_finddeps(self, myblocks)

		scope = func.initializer = C::Block.new(@c_parser.toplevel)
		# di blocks => raw c statements, declare variables
		@dasm.cpu.decompile_blocks(self, myblocks, deps, scope)

		# goto bla ; bla: goto blo => goto blo ;; goto bla ; bla: return => return
		simplify_goto(scope)

		# infer variable types
		decompile_c_types(scope)

		# cleanup C
		optimize(scope)

		# make function prototype with local arg_XX
		args = []
		decl = []
		scope.statements.delete_if { |sm|
			next if not sm.kind_of? C::Declaration
			case sm.var.name
			when /^arg_(.*)/
				args << sm.var
			else
				decl << sm
			end
			true
		}
		# reorder declarations
		scope.statements[0, 0] = decl.sort_by { |sm| sm.var.name =~ /^var_(.*)/ ? $1.to_i(16) : -1 }

		# ensure arglist has no hole (create&add unreferenced args)
		func.type.args = []
		argoff = varname_to_stackoff('arg_0')
		args.sort_by { |sm| sm.name[/arg_([0-9a-f]+)/i, 1].to_i(16) }.each { |a|
			# XXX misalignment ?
			curoff = varname_to_stackoff(a.name)
			while curoff > argoff
				wantarg = C::Variable.new
				wantarg.name = stackoff_to_varname(argoff).to_s
				wantarg.type = C::BaseType.new(:int)
				wantarg.attributes = ['unused']
				func.type.args << wantarg
				scope.symbol[wantarg.name] = wantarg
				argoff += @dasm.cpu.size/8
			end
			func.type.args << a
			argoff += @dasm.cpu.size/8
		}

		# change if() goto to if, if/else, while
		decompile_controlseq(scope)

		optimize_vars(scope)

		optimize_ctrl(scope)

		case ret = scope.statements.last
		when C::CExpression; puts "no return at end of func" if $VERBOSE
		when C::Return
			if not ret.value
				scope.statements.pop
			else
				v = ret.value
				v = v.rexpr if v.kind_of? C::CExpression and not v.op and (v.rexpr.kind_of? C::CExpression or v.rexpr.kind_of? C::Variable)
				func.type.type = v.type
			end
		end
	end

	def new_global_var(addr, type)
		return if not type.pointer?

		# TODO check overlap with alreadydefined globals

		ptype = type.untypedef.type
		name = case tsz = @c_parser.sizeof(nil, ptype)
		when 1; 'byte'
		when 2; 'word'
		when 4; 'dword'
		else 'global'
		end
		name = @dasm.auto_label_at(addr, name)

		if not var = @c_parser.toplevel.symbol[name]
			var = C::Variable.new
			var.name = name
			var.type = C::Array.new(ptype)
			@c_parser.toplevel.symbol[var.name] = var
			@c_parser.toplevel.statements << C::Declaration.new(var)
			if s = @dasm.get_section_at(name) and s[0].ptr < s[0].length and [1, 2, 4].include? tsz
				# XXX initializer = all data til next defined thing (after unaliasing)
				var.initializer = [C::CExpression[s[0].decode_imm("u#{tsz*8}".to_sym, @dasm.cpu.endianness), ptype]]
			end
		end

		# TODO patch existing references to addr ? (or would they have already triggered new_global_var?)

		# return the object to use to replace the raw addr
		var
	end

	# return an array of [address of block start, list of block to]]
	# decompile subfunctions
	def listblocks_func(entry)
		@autofuncs ||= []
		blocks = []
		entry = dasm.normalize entry
		todo = [entry]
		while a = todo.pop
			next if blocks.find { |aa, at| aa == a }
			next if not di = @dasm.decoded[a]
			next if not di.kind_of? DecodedInstruction
			blocks << [a, []]
			di.block.each_to { |ta, type|
				next if type == :indirect
				ta = dasm.normalize ta
				if type != :subfuncret and not @dasm.function[ta] and
						(not @dasm.function[entry] or @autofuncs.include? entry) and
						di.block.list.last.opcode.props[:saveip]
					# possible noreturn function
					# XXX call $+5; pop eax
					@autofuncs << ta
					@dasm.function[ta] = DecodedFunction.new
					puts "autofunc #{Expression[ta]}" if $VERBOSE
				end
				
				if @dasm.function[ta] and type != :subfuncret
					f = dasm.auto_label_at(ta, 'func')
					ta = dasm.normalize($1) if f =~ /^thunk_(.*)/
					ret = decompile_func(ta) if ta != entry
					throw :restart, :restart if ret == :restart
				else
					@dasm.auto_label_at(ta, 'label') if blocks.find { |aa, at| aa == ta }
					blocks.last[1] |= [ta]
					todo << ta
				end
			}
		end
		blocks
	end

	# backtraces an expression from addr
	# returns an integer, a label name, or an Expression
	# XXX '(GetProcAddr("foo"))()' should not decompile to 'foo()'
	def backtrace_target(expr, addr)
		if n = @dasm.backtrace(expr, addr).first
			n = Expression[n].reduce_rec
			n = @dasm.prog_binding.index(n) || n
			n = $1 if n.kind_of? ::String and n =~ /^thunk_(.*)/
			n
		end
	end

	# patches instruction's backtrace_binding to replace things referring to a static stack offset from func start by :frameptr+off
	def makestackvars(funcstart, blocks)
		blockstart = nil
		tovar = lambda { |di, e, i_s|
			case e
			when Expression; Expression[tovar[di, e.lexpr, i_s], e.op, tovar[di, e.rexpr, i_s]].reduce
			when Indirection; Indirection[tovar[di, e.target, i_s], e.len]
			when :frameptr; e
			when ::Symbol
				vals = @dasm.backtrace(e, di.address, :snapshot_addr => blockstart, :include_start => i_s)
				# backtrace only to blockstart first
				if vals.length == 1 and ee = vals.first and ee.kind_of? Expression and (ee == Expression[:frameptr] or
						(ee.lexpr == :frameptr and ee.op == :+ and ee.rexpr.kind_of? ::Integer) or
						(not ee.lexpr and ee.op == :+ and ee.rexpr.kind_of? Indirection and eep = ee.rexpr.pointer and
						(eep == Expression[:frameptr] or (eep.lexpr == :frameptr and eep.op == :+ and eep.rexpr.kind_of? ::Integer))))
					ee
				else
				# fallback on full run (could restart from blockstart with ee, but may reevaluate addr_binding..
				vals = @dasm.backtrace(e, di.address, :snapshot_addr => funcstart, :include_start => i_s)
				if vals.length == 1 and ee = vals.first and ee.kind_of? Expression and (ee == Expression[:frameptr] or
						(ee.lexpr == :frameptr and ee.op == :+ and ee.rexpr.kind_of? ::Integer))
 					ee
				else e
				end
				end
			else e
			end
		}

		# must not change bt_bindings until everything is backtracked
		repl_bind = {}	# di => bt_bd

		@dasm.cpu.decompile_makestackvars(@dasm, funcstart, blocks) { |block|
			block.list.each { |di|
				bd = di.backtrace_binding ||= @dasm.cpu.get_backtrace_binding(di)
				newbd = repl_bind[di] = {}
				bd.each { |k, v|
					k = tovar[di, k, true] if k.kind_of? Indirection
					next if k == Expression[:frameptr] or (k.kind_of? Expression and k.lexpr == :frameptr and k.op == :+ and k.rexpr.kind_of? ::Integer)
					newbd[k] = tovar[di, v, false]
				}
			}
		}

		repl_bind.each { |di, bd| di.backtrace_binding = bd }<commit_msg>decompile: cache backtrace for stackoff<commit_after>require 'metasm/decode'
require 'metasm/parse_c'

module Metasm
class Decompiler
	# TODO add methods to C::CExpr
	AssignOp = [:'=', :'+=', :'-=', :'*=', :'/=', :'%=', :'^=', :'&=', :'|=', :'>>=', :'<<=', :'++', :'--']

	attr_accessor :dasm, :c_parser

	def initialize(dasm, cp = dasm.c_parser)
		@dasm = dasm
		@c_parser = cp || @dasm.cpu.new_cparser
	end

	# decompile recursively function from an entrypoint, then perform global optimisation (static vars, ...)
	# should be called once after everything is decompiled (global optimizations may bring bad results otherwise)
	# use decompile_func for incremental decompilation
	# returns the c_parser
	def decompile(*entry)
		entry.each { |f| decompile_func(f) }
		optimize_global
		@c_parser
	end

	# decompile a function, decompiling subfunctions as needed
	# may return :restart, which means that the decompilation should restart from the entrypoint (and bubble up) (eg a new codepath is found which may changes dependency in blocks etc)
	def decompile_func(entry)
		entry = @dasm.normalize entry
		return if not @dasm.decoded[entry]

		# create a new toplevel function to hold our code
		func = C::Variable.new
		func.name = @dasm.auto_label_at(entry, 'func')
		func.type = C::Function.new C::BaseType.new(:int)
		if @c_parser.toplevel.symbol[func.name]
			if not @c_parser.toplevel.statements.grep(C::Declaration).find { |decl| decl.var.name == func.name }
				# recursive dependency: declare prototype
				@c_parser.toplevel.statements << C::Declaration.new(func)
			end
			return
		end
		@c_parser.toplevel.symbol[func.name] = func
		puts "decompiling #{Expression[entry]}" if $VERBOSE

		while catch(:restart) { do_decompile_func(entry, func) } == :restart
			retval = :restart
		end

		@c_parser.toplevel.statements << C::Declaration.new(func)

		retval
	end

	def do_decompile_func(entry, func)
		# TODO check ABI conformance between func start&end (saved regs, stack offset, __declspec, ...)
		# TODO handle jmp tables

		# find decodedinstruction blocks constituing the function
		# TODO merge sequencial blocks with useless jmp (poeut) to improve dependency graph later
		myblocks = listblocks_func(entry)

		# [esp+8] => [:frameptr-12]
		makestackvars entry, myblocks.map { |b, to| @dasm.decoded[b].block }

		# find registry dependencies between blocks
		deps = @dasm.cpu.decompile_func_finddeps(self, myblocks)

		scope = func.initializer = C::Block.new(@c_parser.toplevel)
		# di blocks => raw c statements, declare variables
		@dasm.cpu.decompile_blocks(self, myblocks, deps, scope)

		# goto bla ; bla: goto blo => goto blo ;; goto bla ; bla: return => return
		simplify_goto(scope)

		# infer variable types
		decompile_c_types(scope)

		# cleanup C
		optimize(scope)

		# make function prototype with local arg_XX
		args = []
		decl = []
		scope.statements.delete_if { |sm|
			next if not sm.kind_of? C::Declaration
			case sm.var.name
			when /^arg_(.*)/
				args << sm.var
			else
				decl << sm
			end
			true
		}
		# reorder declarations
		scope.statements[0, 0] = decl.sort_by { |sm| sm.var.name =~ /^var_(.*)/ ? $1.to_i(16) : -1 }

		# ensure arglist has no hole (create&add unreferenced args)
		func.type.args = []
		argoff = varname_to_stackoff('arg_0')
		args.sort_by { |sm| sm.name[/arg_([0-9a-f]+)/i, 1].to_i(16) }.each { |a|
			# XXX misalignment ?
			curoff = varname_to_stackoff(a.name)
			while curoff > argoff
				wantarg = C::Variable.new
				wantarg.name = stackoff_to_varname(argoff).to_s
				wantarg.type = C::BaseType.new(:int)
				wantarg.attributes = ['unused']
				func.type.args << wantarg
				scope.symbol[wantarg.name] = wantarg
				argoff += @dasm.cpu.size/8
			end
			func.type.args << a
			argoff += @dasm.cpu.size/8
		}

		# change if() goto to if, if/else, while
		decompile_controlseq(scope)

		optimize_vars(scope)

		optimize_ctrl(scope)

		case ret = scope.statements.last
		when C::CExpression; puts "no return at end of func" if $VERBOSE
		when C::Return
			if not ret.value
				scope.statements.pop
			else
				v = ret.value
				v = v.rexpr if v.kind_of? C::CExpression and not v.op and (v.rexpr.kind_of? C::CExpression or v.rexpr.kind_of? C::Variable)
				func.type.type = v.type
			end
		end
	end

	def new_global_var(addr, type)
		return if not type.pointer?

		# TODO check overlap with alreadydefined globals

		ptype = type.untypedef.type
		name = case tsz = @c_parser.sizeof(nil, ptype)
		when 1; 'byte'
		when 2; 'word'
		when 4; 'dword'
		else 'global'
		end
		name = @dasm.auto_label_at(addr, name)

		if not var = @c_parser.toplevel.symbol[name]
			var = C::Variable.new
			var.name = name
			var.type = C::Array.new(ptype)
			@c_parser.toplevel.symbol[var.name] = var
			@c_parser.toplevel.statements << C::Declaration.new(var)
			if s = @dasm.get_section_at(name) and s[0].ptr < s[0].length and [1, 2, 4].include? tsz
				# XXX initializer = all data til next defined thing (after unaliasing)
				var.initializer = [C::CExpression[s[0].decode_imm("u#{tsz*8}".to_sym, @dasm.cpu.endianness), ptype]]
			end
		end

		# TODO patch existing references to addr ? (or would they have already triggered new_global_var?)

		# return the object to use to replace the raw addr
		var
	end

	# return an array of [address of block start, list of block to]]
	# decompile subfunctions
	def listblocks_func(entry)
		@autofuncs ||= []
		blocks = []
		entry = dasm.normalize entry
		todo = [entry]
		while a = todo.pop
			next if blocks.find { |aa, at| aa == a }
			next if not di = @dasm.decoded[a]
			next if not di.kind_of? DecodedInstruction
			blocks << [a, []]
			di.block.each_to { |ta, type|
				next if type == :indirect
				ta = dasm.normalize ta
				if type != :subfuncret and not @dasm.function[ta] and
						(not @dasm.function[entry] or @autofuncs.include? entry) and
						di.block.list.last.opcode.props[:saveip]
					# possible noreturn function
					# XXX call $+5; pop eax
					@autofuncs << ta
					@dasm.function[ta] = DecodedFunction.new
					puts "autofunc #{Expression[ta]}" if $VERBOSE
				end
				
				if @dasm.function[ta] and type != :subfuncret
					f = dasm.auto_label_at(ta, 'func')
					ta = dasm.normalize($1) if f =~ /^thunk_(.*)/
					ret = decompile_func(ta) if ta != entry
					throw :restart, :restart if ret == :restart
				else
					@dasm.auto_label_at(ta, 'label') if blocks.find { |aa, at| aa == ta }
					blocks.last[1] |= [ta]
					todo << ta
				end
			}
		end
		blocks
	end

	# backtraces an expression from addr
	# returns an integer, a label name, or an Expression
	# XXX '(GetProcAddr("foo"))()' should not decompile to 'foo()'
	def backtrace_target(expr, addr)
		if n = @dasm.backtrace(expr, addr).first
			n = Expression[n].reduce_rec
			n = @dasm.prog_binding.index(n) || n
			n = $1 if n.kind_of? ::String and n =~ /^thunk_(.*)/
			n
		end
	end

	# patches instruction's backtrace_binding to replace things referring to a static stack offset from func start by :frameptr+off
	def makestackvars(funcstart, blocks)
		blockstart = nil
		cache_di = nil
		cache = {}	# [i_s, e, type] => backtrace
		tovar = lambda { |di, e, i_s|
			case e
			when Expression; Expression[tovar[di, e.lexpr, i_s], e.op, tovar[di, e.rexpr, i_s]].reduce
			when Indirection; Indirection[tovar[di, e.target, i_s], e.len]
			when :frameptr; e
			when ::Symbol
				cache.clear if cache_di != di ; cache_di = di
				vals = cache[[e, i_s, 0]] ||= @dasm.backtrace(e, di.address, :snapshot_addr => blockstart, :include_start => i_s)
				# backtrace only to blockstart first
				if vals.length == 1 and ee = vals.first and ee.kind_of? Expression and (ee == Expression[:frameptr] or
						(ee.lexpr == :frameptr and ee.op == :+ and ee.rexpr.kind_of? ::Integer) or
						(not ee.lexpr and ee.op == :+ and ee.rexpr.kind_of? Indirection and eep = ee.rexpr.pointer and
						(eep == Expression[:frameptr] or (eep.lexpr == :frameptr and eep.op == :+ and eep.rexpr.kind_of? ::Integer))))
					ee
				else
				# fallback on full run (could restart from blockstart with ee, but may reevaluate addr_binding..
				vals = cache[[e, i_s, 1]] ||= @dasm.backtrace(e, di.address, :snapshot_addr => funcstart, :include_start => i_s)
				if vals.length == 1 and ee = vals.first and ee.kind_of? Expression and (ee == Expression[:frameptr] or
						(ee.lexpr == :frameptr and ee.op == :+ and ee.rexpr.kind_of? ::Integer))
 					ee
				else e
				end
				end
			else e
			end
		}

		# must not change bt_bindings until everything is backtracked
		repl_bind = {}	# di => bt_bd

		@dasm.cpu.decompile_makestackvars(@dasm, funcstart, blocks) { |block|
			block.list.each { |di|
				bd = di.backtrace_binding ||= @dasm.cpu.get_backtrace_binding(di)
				newbd = repl_bind[di] = {}
				bd.each { |k, v|
					k = tovar[di, k, true] if k.kind_of? Indirection
					next if k == Expression[:frameptr] or (k.kind_of? Expression and k.lexpr == :frameptr and k.op == :+ and k.rexpr.kind_of? ::Integer)
					newbd[k] = tovar[di, v, false]
				}
			}
		}

		repl_bind.each { |di, bd| di.backtrace_binding = bd }
{'fraction_non_alphanumeric': 0.13197544642857142, 'fraction_numerical': 0.003794642857142857, 'mean_word_length': 3.454635843897589, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 28, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6395017', 'n_tokens_mistral': 7425, 'n_tokens_neox': 6447, 'n_words': 1767}