BFM-decomp/docs/wiki/The-dedup-engine.md

The dedup engine — one source per unique function

Rewritten at Phase 35 (2026-09-08) for the shared-source model. The macro-era page — bodies as DEFINE_func_…() macros in one 8.8 MB header, propagated by dedup_propagate.py — is in this page's history; the tools it named are under tools/sunset/.

The fact it is built on

The game's code is not in the executable. It is in the resident engine blob and in the location overlays streamed from the disc, and the overlays are position-locked: every one loads verbatim to the same slot, 0x80128158, with no relocation (proven in Phase 3 against a live RAM image). So a shared engine function has the same address and, almost always, the same bytes in every overlay that contains it: func_80144B9C in ov_SC01_077 is the same function as func_80144B9C in ov_SC06_018. Match it once and it is matched everywhere — up to 141 copies for one crack. That was Gen2's economic engine. Gen3's first phase turned the same fact into a readability invariant: a unique function has exactly one source.

The shape: written once, instantiated by an include at each site

This is sotn-decomp's shape, verified from its tree before we adopted it (stage code lives once as plain C under src/st/<name>.h; each stage overlay carries a small .c that #includes it at that stage's link position). Ours:

src/shared/
  engine_prelude.h        # what every overlay/module TU includes at line 2 (the types header and the ENGINE_SHB line)
  engine_types.h          # the shared struct/typedef layer (tools/build_engine_types.py owns it)
  ov/    func_80128EA8.h · func_80150000__2905b55f.h · func_8012AAAC__t6631232b.h   # the overlay slot 0x80128158
  slot_800CAE08/ … slot_801EF468/   # the module slots, one directory per address space
  main/  func_80037004.h            # the one intra-binary, name-parameterized share (clearTbl40)

• One plain-C header per shared body, a pure fragment: the definition, its own externs and comments, no includes of its own, no include guard (a second include of a fixed-name header is the loud duplicate-definition error we want). The file is named by the address, with a stable suffix (__<h8> of the byte hash, __t<h8> of the text hash) only where one address hosts more than one body fleet-wide — both predicates are on immutable ROM data, so names never move when a later body appears.
• Each member site is one line, #include "../shared/ov/func_80128EA8.h", at the position the private copy held. The translation unit keeps its own declarations: what the body sees at file scope is that unit's environment, exactly as a private copy would.
• The parameterized form for a body shared across different addresses: #define SHARED_FN func_80037334 / #include "shared/main/func_80037004.h" / #undef SHARED_FN, the header defining void SHARED_FN(void) {…}. One worked example exists (clearTbl40); the names phase applies the form to the deferred cross-address classes.

Why an include and not a separate object: a macro (and now a header) expands at the site, so its externs become declarations at that line and later functions rely on them; a separate compiled object would delete thousands of declaration lines and cannot place a body interleaved between local ones. Probe P1 proved the include form byte-neutral at the object level before anything moved (three bodies, identical .o files, identical relocations).

The three tiers of "the same function"

tier	keyed on	what one group means	how C1 checks it
h_exact	the raw bytes at one address	identical function, identical bytes, in every member	every member's signature hash equals the group's
h_text	the normalized source text at one address (Phase 35 T5b)	identical C whose bytes vary per binary — the original per-overlay builds compiled it under different declaration environments, and each of our units carries its own	every member's signature hash equals the hash recorded for that member
h_norm	the bytes with relocations normalized out	a structural family (Gen2's remap tier); candidate-only	byte-confirmed per member

.run/sig.<alias>.jsonl is regenerated by make sig-* (tools/sig_image.py). The registry, config/dedup.us.yaml, binds one source to its members in a shorthand form (one vram and name for every member) or the verbose one (per-member entries, which is where an h_text member's own hash lives). It is edited by text, never dumped: a YAML round-trip once decimalized every address and deleted every comment while every gate stayed green.

The tool: share_body.py

tools/share_body.py is the permanent successor of the macro-era dedup_propagate / dedup_extend. Per class: the exemplar is the private copy whose normalized text the most copies share (tie → a pin-free copy → the shortest; printed with every share); its definition lines become the header (an asm-label alias body gets its own __asm__ binding); every private copy becomes the include at its position, edits applied bottom-up per unit; the registry gains the group. The gate, per batch: every touched binary (a twin with its primary) has its objects snapshotted, make check BINARY=<b> runs and is read by exit code, every object is compared; a red binary is bisected class by class from an in-memory snapshot of the unit's text, the culprit's copies stay private and the class is ledgered in config/dedup_exceptions.tsv with the compiler's first real diagnostic and a reason code (TU-CONFLICT, GATE-REJECT, PARSE-ERROR, SYMBOL-NAME, …). "Shared" is printed only from the gate's success line; the clean fleet run follows every batch. It runs on a committed tree, one batch per invocation (tools/share_body_cycle.sh drives the batches unattended, committing each), and has --reexemplar (a registered class whose header carries a minority spelling is rewritten from the majority text, its includers re-gated first) and --repair-registry (a listed member whose site is still private is delisted; an including-but-unlisted member is listed — both derived from the census, matched on binary and address).

Four defects the tool had on its first day, each found by its own gate and each now a rule of its shape: the failure cause was read from the word "error" (gcc 2.7.2 prints errors without it — 254 rejections read "Error 33"); files were restored with git checkout, which wiped the previous batch's uncommitted shares; a twin's instance resolves to its primary's unit and the same edit queued twice swallowed the following function; the registry was extended with every planned member before the gate had spoken.

The invariant, and the gate that holds it

S1 — one source per unique function: every same-address class with two or more instances is a registry group with the include at every member, or twin-covered (the five identical-payload overlay pairs build from one source directory), or a ledgered exception with its measured reason. tools/share_census.py derives it from the 218 signature files and the source: every instance resolves to exactly one form (a definition, an include, a parameterized include, a stub, a verbatim body); 0 or 2 forms is a coverage defect. make tools-health runs its self-test (an in-memory fixture of every verdict) and then --check --strict-macros --strict-text, read by exit code. --strict-text is the second, sig-blind oracle: the same normalized definition text at the same address in two units is a violation regardless of what the byte join thinks. It earned its keep on the first run — it found 38 functions (2,030 copies) the byte tier could never class, which became the h_text tier.

tools/dedup_integrate.py --check validates the registry: C1 (every member's current signature equals its recorded hash), C2a′ (the source defines the function it names), C2c (one source under src/shared/, defining exactly one function), C2d (every member's site is an include of that source — a surviving private copy is the registry running ahead of the source). The negative control is on record: one member's include reverted to its private copy made the census exit 1 naming the class and C2d name the member.

Where it stands (Phase 35, derived 2026-09-08 by tools/share_census.py --check and tools/progress.py --fleet; re-derive, never copy)

• 10,180 same-address classes, 10,180 satisfied: 3,507 twin-covered, 51 ledgered (50 declaration conflicts in the late-onboarded overlays, for the types phase; 1 byte-variant body), 3,801 cross-address classes deferred to the names phase; 0 violations.
• 3,173 registry groups (2,220 at the phase's open), 262,573 instances; 103,015 function bodies written once in C; 160 duplicate copies remain in the 51 ledgered classes; 1,668 same-address copies of 381 tiny bodies (empty functions, two-instruction accessors) sit inside the deferred cross-address classes — the names phase's parameterized form is their shape.
• The macro header and its 5,147 define lines are gone; 0 DEFINE_func_ sites under src/; the fleet's clean rebuild fell from 157 s to 84 s wall (the 8.8 MB header no longer preprocessed by 3,818 units).

Honesty rules the engine imposes

• A share writes N binaries after verifying each; the fleet run from clean follows every batch (R22).
• A group is keyed by integer address and hash, never by name (R48); a listed member is a member whose site shares — the registry never runs ahead of the source (C2d).
• A tool that restores files restores from its own snapshot, never from git checkout on a tree it did not commit.
• make audit-binaries asserts every binary is a full citizen of every consumer — signature set, registry, the shared prelude, reports, twin citizenship (R36).