cpp_permuter

Brute-forces source permutations of a single C++ function until its compiled code matches a target object, or gets closer to it. It is built for matching decompilation projects such as gta2_re (MSVC 6).

cpp_permuter is heavily inspired by Simon Lindholm's decomp-permuter, which does the same for C. It borrows decomp-permuter's design wholesale: random and exhaustive search, weighted randomization passes, PERM_* macros, an objdump-based scorer, and outputs with a score and a diff. It is a separate implementation, written in C++, for C++ code compiled by MSVC. Like decomp-permuter, it is released under the MIT license.

How it works:

1. Find the function in the .cpp and parse its body into statements, declarations and expressions.
2. Make candidates by applying mutation passes (reorder local saves, inline a local, move declarations in and out of blocks, swap operands, invert an if, ...). Optionally do the same to the inline helpers the function calls.
3. Splice each candidate back into the file, compile it with your compile command, and disassemble the function from the object with llvm-objdump.
4. Score it against the target: 0 means identical, lower is closer. Improvements are written to the output directory.

Getting it

Download a release from the Releases page: cpp_permuter-linux-x64 and cpp_permuter-windows-x64 (the Windows one needs no Visual C++ redistributable). Pushing a tag such as v1.0.0 publishes one, after the CI builds and tests pass. Every CI run also keeps the binaries as artifacts for 90 days on the Actions page.

Or build from source:

Building

Needs CMake 3.16+ and a C++17 compiler: GCC or clang on Linux, MSVC (or MinGW) on Windows. Scoring also needs llvm-objdump on PATH. On Windows it comes with the LLVM installer.

Windows runs natively. Commands go through cmd.exe, so use examples/gta2/compile.cmd there. Where symlinks aren't allowed (no Developer Mode), the mirror uses hard links or copies instead. CI builds and tests on Linux and Windows.

cmake -S . -B build -G Ninja      # or leave out -G for make
cmake --build build
ctest --test-dir build            # unit and integration tests (see Tests below)

Usage

cpp_permuter -s Source/PedGroup.cpp -f PedGroup::PromoteMemberToLeader_4C9680 \
    -c 'examples/gta2/compile.sh {src} {obj}' \
    -t Scripts/asm/PedGroup.cpp.obj \
    -m exhaustive -p reorder_saves -j 4

option	meaning
-s/--source	the .cpp holding the function
-f/--function	Class::Method, Method, Class::Class, Class::~Class
-c/--compile	compile command. {src} is the candidate source, {obj} the object it must write, {dir} the candidate's directory, {root} the mirror's root (see below)
-t/--target-obj	object file holding the target code
--symbol, --target-symbol	symbol names, if the guess from --function is wrong (MSVC ?Name@Class@@..., Itanium, or C)
--score-cmd	score with your own command instead ({obj}, {src}). It must print the score (0 = match) as the last number in its output. The output is kept as score_output.txt with each improvement, so a scorer can print its own asm diff
--op-alias OP=NAME	for named_op: operator OP (*, +, ..., neg) also exists as the method NAME. Repeatable
--ignore-reloc-names	compare relocated operands without their symbol names, and treat absolute addresses as symbols. Use this when the target came from raw exe asm
-m exhaustive	try every candidate the selected passes and combos produce. --depth N chains N of them, --max-candidates caps the count
-m random	(default) apply 1..--max-mutations random passes or combos, starting from the base or from the best so far. Runs until a match, -n compiles, or Ctrl-C
-p a,b	passes to use (default: all). -p can be repeated. a+b combines passes, see below
-j N	parallel compiles
--dry-run	print the candidates as diffs without compiling. A quick check of what a pass would do
--show-ast	print how the function was parsed
--show-base-diff	print the target/base asm alignment before starting
--config FILE	key = value lines, same keys as the long options. Handy for one config per function
--keep-going	keep searching after an exact match
--keep-prob P	random: start from the best candidate so far with probability P, else from the base (default 0.5)
--weight NAME=N	random: how often a pass or combo (as written in -p) is picked; 0 never
--keep-ties	also write candidates that tie the best score (different ways to the same code)
--only-if-below N	only write candidates scoring below N
--base-only	compile and score the unmodified function, print the score, exit
--show-timings	where the time went: permuting, writing, compiling, scoring
-p none	no passes: only the PERM_* macros (see below)
-I DIR	where to find headers for --inline-callees/--also, besides each file's own directory. The compiler's include paths stay in your compile command
--inline-callees, --also [FILE:]NAME	also permute inline helpers the function calls, see below
--check-parse FILE...	parse every function in the files and run every pass on each; see Tests
--resume	carry on from the checkpoint in the output directory, see Resuming a run
--extern-globals	also try the function's globals declared the other way (definition vs extern), see Globals defined in the same file
--calling-conventions	also try the function and its callees with another calling convention, see Calling conventions

Each improvement goes to permuter_out/output-<score>-<n>/:

• function.cpp: the permuted function (and any helper that changed).
• source.cpp: the whole file.
• <header>.hpp: each header that changed, when helpers were permuted.
• diff.txt: what changed.
• asm_diff.txt: target and candidate asm aligned side by side.
• score_output.txt: with --score-cmd, what the score command printed.

The exit status is 0 if a match was found and 3 if not.

Resuming a run

Every run keeps a checkpoint in its output directory (checkpoint.txt, checkpoint_best.txt and checkpoint_seen.txt), written every couple of seconds and on exit, Ctrl-C included. Run again with the same options plus --resume to carry on where it stopped:

cpp_permuter -s Ped.cpp -f Ped::Foo_123456 -c '...' --score-cmd '...' -j 4 -n 2000
# stopped, or out of time: the next 2000
cpp_permuter -s Ped.cpp -f Ped::Foo_123456 -c '...' --score-cmd '...' -j 4 -n 2000 --resume

• Candidates are numbered in the order they are generated. In random mode, candidate n is made from its own random generator, seeded from the run's seed and n (the seed is printed at the start and kept in the checkpoint, so --seed isn't needed to resume). With -j 1 a seed always gives the same candidates in the same order. With more jobs a candidate can also depend on which improvements had landed when it was made (--keep-prob), but a resumed run still starts at the first candidate that wasn't scored and skips every one already tried.
• Exhaustive mode's order doesn't depend on the scores: a resumed run replays the earlier candidates without compiling them and continues with exactly the ones that weren't scored.
• The checkpoint records a key made from the function's source, the mode, -p, --weight, --op-alias, --depth, --max-mutations and --keep-prob. --resume refuses a checkpoint whose key differs (the source changed, or other passes), since its numbering would mean different candidates. -j, -n, --max-candidates and the output options can change between runs.
• -n counts the compiles of this run; the totals carry over. --max-candidates counts from the start of the search. Output directories keep numbering after the earlier run's.

Candidates are compiled in a mirror of the source's directory under permuter_out/.work/w<N>/, one per worker. The mirror is built from symlinks to every entry, plus real copies of the files the permuter edits. Your files are never written to. File names stay the same, and every #include "..." resolves inside the mirror, so an edited header is the one that every file includes. --mirror-root DIR mirrors a larger tree when the edited files aren't all under the source's directory.

Inline helpers

VC6 inlines small helpers (getters, Fix16::Abs, Max, ...) into their callers, so a function can be off only because a helper is written differently. The permuter can work on those too:

--inline-callees            # the inline functions this function calls
--also fix16.hpp:Max        # a particular function, by file (relative to . or the source)
--also Fix16::Max           # ... or looked up in the source and the headers it includes
--list-regions              # print what would be permuted, then exit

--inline-callees looks for definitions of the called names in these places:

• the headers the source reaches through #include "..." (searched in the including file's directory, then in -I dirs);
• the source itself, for functions marked inline.

Overloads whose parameter count can't fit any call are skipped. The first definition of every name is taken before any second overload, up to --max-callees (default 8).

Every pass then also works on those helpers. Half of the random mutations go to the target function, and exhaustive mode tries every pass on every function. Only the target function is scored. When a candidate matches, the output has the changed headers next to source.cpp.

Globals defined in the same file

VC6 can code a read of a global differently depending on whether the file being compiled defines it or only declares it extern. In gta2_re, a 2-byte global defined in the same file got 32-bit loads, and the original's 16-bit loads came back once its definition moved to another file. --extern-globals lets the permuter try that:

cpp_permuter ... --extern-globals

• Each global the function names gets its own region, holding its declaration line in the source file.
  • A definition (DEFINE_GLOBAL...(type, name, ...)) can become EXTERN_GLOBAL(type, name); (EXTERN_GLOBAL_ARRAY(type, name, size); for arrays).
  • An extern declaration can become its definition, copied from another .cpp in the source's directory.
• --global-macros DEFINE=EXTERN names other macros with the same argument layout. The default is gta2_re's DEFINE_GLOBAL=EXTERN_GLOBAL.
• Exhaustive mode tries each switch on its own. Random mode switches a global in one mutation in eight.
• Only the candidate's own object is compiled and scored, so a missing definition doesn't matter. If a switch wins, move the definition by hand: to another .cpp for an extern, or into this file for a definition.

Calling conventions

A free or static function's calling convention changes more than its calls: in a __cdecl function VC6's scheduler gives the instructions after a call no call-clobber latency, so even a function without parameters schedules differently as __stdcall (gta2_re's keybrd_0x204::GetLayout_4D6000 and SetWindowedMode_5D9510 matched that way). With

cpp_permuter ... --calling-conventions

the function and every function it calls get a region per declaration line in the source and the headers it includes: the text between the return type and the name. A candidate gives all the declarations of one function the same choice of none, __cdecl, __stdcall or __fastcall. Exhaustive mode tries each function and convention on its own; random mode switches one in one mutation in eight. Declarations split over lines, or after other code on their line, aren't found.

PERM macros

When you already know the alternatives, write them into the function, as with decomp-permuter:

void PedGroup::f(u8 idx)
{
    PERM_LINESWAP(
    Weapon_30* a = field_2C_ped_leader->field_170_selected_weapon;
    Weapon_30* b = field_4_ped_list[idx]->field_170_selected_weapon;
    )
    field_23C = PERM_GENERAL(99, 100);
    if (PERM_GENERAL(x == 0, !x)) g();
}

macro	expands to
PERM_GENERAL(a, b, ...)	one of a, b, ...
PERM_LINESWAP(lines)	the non-blank lines in any order
PERM_INT(lo, hi)	an integer from lo to hi
PERM_ONCE([key,] code)	code at exactly one of the places that use key
PERM_VAR(a, b), PERM_VAR(a)	set, and read, the meta-variable a
PERM_RANDOMIZE(code)	code, and turns the passes on
PERM_FORCE_SAMELINE(code)	code on one line
PERM_IGNORE(code)	code, with no macros expanded inside
PERM_PRETEND(code)	nothing

Arguments split at top-level commas, and (,) is a literal comma. Macros can be nested.

Exhaustive mode tries every expansion, and random mode picks one at random. As in decomp-permuter, a function with macros is only permuted through them, unless it uses PERM_RANDOMIZE or you pass -p. In that case the passes run on top of each expansion, over the whole function (not just inside the PERM_RANDOMIZE region). Macros are supported in the target function only.

Combining passes

A function is often off in more than one way: the saves are in the wrong order and an if is the wrong way round. A single pass can't fix both, so passes can be combined:

-p reorder_saves,invert_if         # each pass on its own: 23 + 4 candidates
-p reorder_saves+invert_if         # a combo: 23 + 4 + 23*4 = 119 candidates
-p reorder_saves -p invert_if+swap_operands   # -p can be repeated

In exhaustive mode, a combo a+b+c tries every variant of every pass in it, and every in-order chain of them: a, b, c, a then b, a then c, b then c, and a then b then c. In random mode a combo applies one mutation from each of its passes. --depth N chains whole passes or combos too: -p reorder_saves -p invert_if --depth 2 reaches the same candidates as the combo above, plus each pass applied twice.

Passes

cpp_permuter --list-passes prints these. docs/passes.md shows each one on an example function, generated from the passes themselves (cpp_permuter --pass-examples).

pass	what it does
reorder_saves	Runs of consecutive "local saves" (declarations, or assignments to locals, that don't call or store) in every order that keeps dependencies. Four independent saves give 23 new orders (the PedGroup::PromoteMemberToLeader_4C9680 quirk)
move_stmt	Move one statement up or down past neighbours it doesn't depend on. Field loads and stores are assumed not to alias; locals and calls are respected
inline_local	Remove a local by putting its initializer into its uses, plainly and with a cast to the local's type. A local that is never used is dropped
sink_decl	Move a declaration into the innermost block that holds all its uses, or to just before its first use
hoist_decl	Move a declaration to the top of its block or of the function, splitting T x = e; into T x; plus x = e;. Also offers one candidate that hoists every declaration at once (C89 style)
merge_decl	T x; ... x = e; becomes T x = e; at the assignment
swap_operands	a + b becomes b + a, for + * & | ^ == !=
flip_compare	a < b becomes b > a
invert_if	if (c) A else B becomes if (!c) B else A, negating comparisons directly
ternary	x = c ? a : b and return c ? a : b become if/else (and an early-return form), and back
compound_assign	x = x op y and x op= y, both ways
bool_return	return a <= b; and if (a <= b) return true; return false; (also with else, and with 1/0), both ways
ternary_arg	f(c ? a : b); and if (c) f(a); else f(b);, both ways. Going back, two branches that differ in one sub-expression become one statement with a ternary
switch_if	if (x == K) S else D and switch (x) { case K: S break; default: D }, both ways (the one-case switch quirk)
early_return	if (c) { ...; return; } else { B } and if (c) { ...; return; } B, both ways (also break, continue, goto)
branch_dup	Move a statement that both branches start or end with out of the if, or copy the statement before or after an if/else into both branches
cond_split	if (a && b) S and if (a) { if (b) S }, both ways
explicit_compare	if (x) and if (x != 0), if (!x) and if (x == 0), in conditions
negate_const	x - 4 and x + -4, x -= 4 and x += -4 (the sub vs add -N quirk)
loop_form	for (i; c; s) B and i; while (c) { B s; }, while (c) and for (; c;)
reassociate	a + b + c and a + (b + c), for + * & | ^
inequalities	x > 4 and x >= 5, x < 4 and x <= 3, for integer constants (VC6 picks the cmp constant and jump from it)
chain_assign	a = v; b = v; and a = b = v; (or b = v; a = b;), which decides the register that holds v
scope_block	Wrap a declaration and the statements using it in a { } block, or take a nested block apart (VC6 shares stack slots between blocks)
local_type	Change a local's integer type: s32, u32, s16, u16, s8, u8 (or int/unsigned/short/char..., or DWORD/WORD/BYTE...)
locals_to_array	Consecutive locals of one type become one array, in order or back to front (stack slot order)
reorder_cases	Reorder a switch's case groups (case bodies are laid out in source order). A last group without break gets one when it moves
split_case_labels	case 1: case 2: S and case 1: S case 2: S, both ways (one jump table entry per case vs a byte index table)
use_getter	p->field_1AC_cam.x and p->get_cam_x(), both ways, using the inline getters found in the source and the headers it includes
temp_for_expr	Compute a cast, a local or *p into a new local first (u8 tmp = (u8)p->a; g(tmp);). Types come from the declarations; also "copy through a local to get a spill"
named_op	a * b and a.Multiply_408680(b), -a and a.Negate_4086A0(), both ways, for the operators given with --op-alias OP=NAME (neg for unary minus). Calling the named out-of-line version decides whether VC6 inlines that use of the operator, which also changes what else it inlines (the inline budget)
cast_operand	Cast an operand of / % >> < > <= >= + - * == != to u32, s32, u16, s16, u8 or s8, or drop or change an integer cast there: div vs idiv, shr vs sar, jb vs jl, byte adds. Operands that are non-integer locals or calls are left alone
remove_stmt	Remove an expression statement (low weight)

decomp-permuter passes left out because they rely on IDO behaviour that VC6 /O2 folds away: perm_xor_zero, perm_mult_zero, perm_add_mask, perm_dummy_comma_expr, perm_factor_mult/shift, perm_float_literal, perm_sameline, perm_pad_var_decl, perm_add_self_assignment and perm_duplicate_assignment.

The passes aim to keep behaviour the same, but they don't prove it. For example they assume that two different fields don't alias. That is fine here, because a candidate that matches the target byte for byte is correct by construction. A rewrite that changes behaviour just won't match.

The parser

This is not a full C++ front end, and that is deliberate. It works on the unpreprocessed source and only rewrites the body of the target function. Everything else in the file stays byte-identical, so candidates go through cl.exe with the original includes and macros. Inside the body it recognises statements, local declarations and expressions. Anything it can't classify (__asm, unknown macros, local types) becomes a fixed barrier that is never moved across. If it misreads something, that candidate fails to compile and is skipped.

Running clang on the whole file instead would mean the code has to compile under clang. MSVC 6 code with its own headers, __asm and naked marker functions doesn't, and clang's error recovery drops the very declarations we want to move.

On gta2_re (--check-parse Source/*.cpp Source/*.hpp):

• all 4,235 functions in 231 files parse;
• 2 of 53,552 expressions are not understood (a decltype cast and a function-pointer cast);
• 4 statements stay barriers (a typedef, two using namespace, a local struct);
• every candidate that every pass produces parses back.

Speed

--show-timings on VC6 under wine, PedGroup.cpp, 4 workers:

stage	per candidate
permute (parse, mutate, splice)	0.5 ms
write the mirror files	1 ms
compile	600 ms; 355 ms with precompiled headers
score (llvm-objdump plus diff)	32 ms

The permuter keeps the original file and each function's byte range. A mutation only re-lexes the function, and each candidate is spliced into in-memory copies, so practically all the time is spent in the compiler.

examples/gta2/compile.sh and compile.cmd use VC6 precompiled headers (/YX, one .pch per worker), which halves the compile time. The code is identical to a normal compile for every function in PedGroup.cpp. The mirror only rewrites files whose content changed, so the .pch stays valid. While headers are being permuted, the permuter sets PERMUTER_NO_PCH=1: VC6 checks the .pch by timestamp, and missed header edits made within the same second.

Stripping the other functions out of the file (decomp-permuter's strip_other_fns.py) would only save another 10%, and it changed the code of 1 of PedGroup's 38 functions, so it isn't offered.

Scoring

The function is disassembled with llvm-objdump -d -r --disassemble-symbols=<sym>. Before comparing:

• relocated operands are replaced with their symbol;
• branch targets become instruction indices, so a size change upstream doesn't change every jump;
• <...> annotations are stripped.

Target and candidate are then aligned with an edit distance. Penalties: 10 for a register difference, 50 for other operand differences, 60 for a moved instruction, 100 for an insertion or a deletion. The weights are the same idea as decomp-permuter's.

Tests

ctest --test-dir build runs four suites. CI runs unit and integration on Linux and Windows.

unit (tests/tests.cpp) covers:

• the lexer and the parser, including listing every definition in a file;
• the effects analysis;
• every pass, in both directions where it has two;
• the PERM_* macro expander;
• that docs/passes.md is what the passes produce today;
• pass combos;
• the scorer;
• finding inline callees;
• the mirror, including a source tree made of symlinks.

integration (tests/integration/run.sh) needs clang and llvm-objdump. It uses clang's i686 MSVC target at -O0, where statement order and expression shape show up directly in the code. Each case has a base/ directory that is wrong in some way, and a target/ directory that the target object is built from: main.cpp, plus any headers. The permuter must match the target, and where it should, give back exactly the target sources. Negative controls run without the pass under test (usually: with every other pass) and must not match, which shows the match comes from that pass. The cases are:

• var_reorder: local saves out of order.
• combo: saves out of order plus an inverted if. Single passes fail and the combo matches.
• inline_local: a local the original didn't have.
• ops: swapped operands.
• One case for each of bool_return, ternary_arg, switch_if, branch_dup, cond_split, negate_const, reassociate, inequalities, chain_assign, local_type, locals_to_array, reorder_cases, split_case_labels, use_getter, temp_for_expr and remove_stmt.
• perm_macros: PERM_LINESWAP and PERM_GENERAL. All 17 expansions are tried, and without the macros (-p none) there's no match.
• inline_callee: the function is right, but the __forceinline helper in its header isn't. It is found by --inline-callees, --also NAME and --also FILE:NAME. Without them there is no match.

early_return, explicit_compare, loop_form and scope_block compile identically at clang -O0, so only the unit tests cover them.

gta2_parse (tests/integration/gta2_parse.sh) runs --check-parse over every gta2_re source and header. It fails if any of these happen:

• a function doesn't parse;
• a candidate doesn't parse back, or is a no-op;
• more than 0.1% of expressions, or more than 10 statements, aren't understood.

vc6 (tests/integration/vc6.sh) uses real MSVC 6 under wine, on gta2_re functions that already match, so VC6's code for them is the original game's code. Each case breaks a function the way a decompiler might, and checks that the permuter recovers the exact original source. A control without the needed pass must not match. It works in a symlinked copy of Source/ and never modifies the checkout. The cases are:

• PedGroup::PromoteMemberToLeader_4C9680: the four weapon saves in three different orders; and the saves out of order plus an inverted if, which only the combo fixes.
• PedGroup::RemovePed_4C9970: ternary_arg, the if/else around a call (from matching_quirks.md).
• sound_obj::IsTrainOrBoxcar_57F120: bool_return (from matching_quirks.md).
• Particle_4C::UpdateShortAnim_state_37_53B580: switch_if.
• Fix16::Max with its comparison mirrored, and Fix16::Abs written as a ternary, in fix16.hpp, as inlined into PedGroup functions. They are recovered through --inline-callees and --also; permuting only the calling function doesn't match.
• PedGroup::IsLeaderCloseToTargetCar_4CAD40: use_getter, with get_cam_y() written out as the field it reads. Two sources match here: the original, and one that reads the car's x through Car_BC::get_x_41E430() instead. VC6 compiles both to the same code.
• PedGroup::sub_4C9150: inequalities (< 0x28 written as <= 0x27).
• PERM_LINESWAP around the scrambled weapon saves.
• 60 random candidates from every pass on RemovePed: at most 10% may fail to compile. None did.

Some rewrites turned out to make no difference to VC6, so they have no VC6 case:

• inverting Fix16::Abs's if, and its early-return form;
• reordering the cases of the switches tried;
• u8 instead of s32 for a loop counter.

Clang at -O0 covers those passes instead.

gta2_parse and vc6 need GTA2_RE set to a gta2_re checkout, and vc6 also needs wine. Without them they are reported as skipped.

gta2_re

examples/gta2/ has a VC6-under-wine compile script and a walkthrough. See examples/gta2/README.md.