bitstream-re

name	bitstream-re
description	Black-box reverse engineering of FPGA configuration bitstreams (Altera Cyclone IV proven; method generalizes). Use when the user wants to map CRAM bits, build a codec, jailbreak a fitter whitelist, or hardware-verify a codec-generated bitstream on real silicon.

FPGA Bitstream Reverse Engineering — Playbook

Distilled from the EP4CE6 project (6,272→10,320 LE jailbreak silicon-validated on both axes — X=32 column AND Y=15 row; 731/731 bit-perfect across all 24 green-zone + jailbreak/edge islands; HW-verified end-to-end on AX301). Every step in here has been silicon-validated at least once; don't skip the verification steps just because the math looks clean.

Core principles

1. Pair-diff beats absolute analysis. Compile two designs that differ in exactly one thing (one LUT mask bit, one placement, one routing port) and XOR the RBFs. The diff isolates the bits you care about from the vendor's routing noise. Never try to parse an RBF from first principles when a diff will do.
2. Trust silicon, not datasheets. Pin maps, LAB grids, "non-LAB" column lists, and device LE counts in vendor docs are frequently wrong or intentionally misleading. Verify with a hardware probe before you build a model on top of them.
3. The vendor's fitter is a whitelist, not a hardware lock. If the same package ships as multiple SKUs, the cheaper SKU almost always has all of the expensive SKU's silicon, disabled only in the fitter. This is testable in minutes (see "Jailbreak probe").
4. Codec round-trip ≠ hardware safety. A codec that reads a cell and writes it back faithfully can still produce a bitstream that shorts a MUX on real silicon. Maintain a separate validate_safe_for_hardware() that classifies every touched structure against known-safe Quartus envelopes, and run it before every flash.
5. Negative results are deliverables. If a feature isn't in the input space (we spent two rounds proving the paired/alternating LI mode isn't a function of the routing key), document it and stop — don't quietly keep mining.
6. Always reach for the vendor's RBF as ground truth before patching the codec. When a codec-built bitstream doesn't behave on hardware, the natural reflex is to dig into the codec, the sig-cache, the FASM front-end. Resist it for 30 seconds: compile the same Verilog in Quartus and flash that. If Quartus's RBF doesn't blink either, your test design is wrong. If Quartus's RBF blinks but yours doesn't, byte-diff the two and look at where the cells live, not how many — Quartus may be using a primitive (carry chain, BRAM port, DSP cascade) that your front-end never emitted, putting the whole design in a different physical region of the die. We burned two days on a 24-bit counter chasing real-but-irrelevant LutCodec / sig-cache / phase-ordering bugs before flashing Quartus's counter_top.rbf and discovering it lived in CRAM cols 47-48 (carry chain) while ours lived in cols (4,18)/(4,19) (4-LE-per-bit ripple emulating +1 because nextpnr-generic doesn't model cout→cin direct wires). One vendor flash on day one would have closed the case in minutes.

Stage 1 — Infrastructure (build once, reuse forever)

• Headless compile driver. Shell out to the vendor's CLI (quartus_map → quartus_fit → quartus_asm → quartus_cpf for Altera). Parse the fit report for errors, clean the work dir between runs. ~4s per compile on Cyclone IV Lite.
• Binary diff engine. Byte-level diff of two RBFs of the same size, emit a list of (offset, old_byte, new_byte) tuples. Store in SQLite keyed on design metadata.
• Parameterized Verilog generator. Emit placements via set_location_assignment in QSF, primitives via cycloneive_lcell_comb (or the vendor's equivalent low-level cell). Do not rely on behavioral synthesis — it will optimize away your probe. Use (* keep = 1, preserve = 1 *) plus primitive instantiation.
• Known-good baseline. Compile an empty / minimal design once per (family, device, source-location). All diffs are against this zero.rbf. Cache it — it never changes as long as the placement anchor is stable.

Stage 2 — CRAM geometry (find the grid)

Goal: given a cell at logical (X, Y, N, feature), compute its byte offset and bit position.

1. Pick a feature that's easy to toggle from Verilog (LUT truth table is ideal — 16 bits of direct user control via lut_mask).
2. Pair-diff a single bit. Compile lut_mask=0x0000 vs lut_mask=0x8000. The diff tells you where minterm 15 lives.
3. Sweep the feature. Do all 16 minterms. XOR-linearity emerges: any mask is the XOR of its single-bit patterns.
4. Sweep X, then Y, then N. Look for invariant strides. Cyclone IV gave us: 7,350 bytes per LAB column, 210 bytes per Y pair, 48 bytes ctrl→data, slot/group encoding via (Y-2)%3 and (Y-2)//3.
5. Cross-validate at least one cell per column. If step 4's formula misses, you haven't found the right stride — go back to pair-diffing more X values.
6. Edge columns matter. Left-edge (X<8) and right-edge columns often use different base addresses; build a COLUMN_BASE[x] lookup table instead of assuming a uniform stride.

Stage 3 — Routing matrix (the hard part)

Routing wires are named by the vendor's STA tool. For Cyclone IV:

• Extract with report_timing -show_routing in a TCL script
• Wire names look like C4_X{x}_Y{y}_N{n}_I{i}, R4_..., LOCAL_INTERCONNECT_...
• Store every (src, dst, wire path) triple in SQLite as your routing corpus

For each wire type:

1. Collect multiple routes that share the wire — mine SQLite for every path using C4_X10_Y10_N0_I0, for example
2. Pair-diff two routes that differ only in that wire's presence. The common bits = the wire's CRAM cells
3. Baseline-diff mapper: for a candidate (X, I) combo, find which (byte, bit) positions are uniquely correlated with Y across the corpus. This is how the 44 C4 I≠0 mappings and 24 R4 I-index models were found. Audit what you mine: a 2026-04-08 mass audit of the EP4CE6 R4 table (Methods B+D against absolute route_cells.json) found 11/16 testable entries at <40% hit rate — mining results rot when the corpus shifts and the formula path becomes dead code behind a signature short-circuit. Periodically cross-check mined tables against a ground-truth absolute cell set, not just per-route differentials.
4. Expect per-wire-type address styles: C4/R4 have slot/group/group-indexed formulas; R24 has fixed per-wire bytes (no Y offset); LOCAL_INTERCONNECT lives in the self column not the prev column. Don't assume uniformity.

Stage 3b — Source-side routes (IOB → fabric, GCLK → LAB, etc.)

Source-side routes are structurally harder than wire-internal mining because the start of a route lives in a different fabric domain (pad ring / clock tree) than the end, so a single pair-diff mixes three contributions: the source's fabric-entry cells, the destination's MUX cells, and a shared skeleton that's invariant across both axes. Mining one (src, dst) pair and calling the whole delta "the route" gives you a bloated, non-reusable cell set. Instead, sweep both axes and decompose the delta by intersection:

1. Paired template, not single-LE: compile a two-LE design where one LE is the target (driven by the source pin) and the other is a fixed secondary LE driven by a fixed secondary pin. Subtract a zero variant where both LEs exist but neither routes from the pin. This cancels most of the vendor's placement overhead up front and makes the diff diff-able. The paired RBF itself is usable as a functional silicon design (HW-verified on EP4CE6 for iob_pair_E16_10_4_0_dataa.rbf driving KEY2→LED0), so you can flash the mining artifact directly to cross-check the template before trusting any downstream decomposition.
2. Sweep the source axis (pin A, pin B, pin C, …) with destination fixed → intersection over pins isolates pin_footprint(pin) (pin-specific, target-invariant) once universal_infra is subtracted.
3. Sweep the destination axis (LAB 1, LAB 2, …) with source fixed → intersection over destinations isolates universal_infra (pin- AND target-invariant). What's left per destination is pure_common(tgt) — pin-invariant, target-specific, i.e. the destination-dominated portion of the route.
4. Verify closure: raw_delta = universal_infra ∪ pin_footprint(pin) ∪ pure_common(tgt) ∪ residual. On EP4CE6 IOB→SLICE the residual is ≤2 cells per entry across 15 (pin × target) pairs — that's the "am I done?" check.
5. Sweep the secondary axis (fixed-secondary-pin-A vs fixed-secondary-pin-B) once to quantify how much of the skeleton is truly invariant vs. absorbed from your secondary pin choice. On EP4CE6, switching sec_src from A11 to M15 shifted 26 cells inside universal_infra but only moved 3-10 cells out of pure_common per target — i.e. most of the "universal" skeleton is secondary-source contamination, not chip-universal wiring. The refined pc(src_A) ∩ pc(src_B) is closer to a true R(IOB→target) but diminishing returns kick in fast.
6. Vendor canonicalization: single-input designs may get their input port rewritten by the synthesizer before placement — on EP4CE6 a 4-port sweep (dataa/datab/datac/datad) produced byte-identical deltas because Quartus canonicalizes to a single port-MUX form. Don't mine the port axis until you've got a multi-input template that actually exercises port diversity.
7. Baseline mismatch caveat: pure_common(tgt) is expressed relative to whatever baseline your zero template uses. If your real design's zero baseline is a different bitstream (e.g. a globally-routed baseline with clock pre-wired), you need either a single-LE template whose zero approximates that baseline, or a one-time bridge delta (nv_zero_global XOR iob_zero) to align the two frames.

Stage 4 — Codec + safety envelope

• RouteCodec.apply_switch(rbf, wire_name, state) — writes one wire on/off using the Stage 3 models
• LutCodec.write_tt(rbf, mask) — writes a LUT truth table. XOR-delta semantics: if your base already has bits set, compensate with mask = target ^ base_tt. This is a real footgun.
• validate_safe_for_hardware(rbf, zero) — classifies every touched LAB's local-interconnect pair pattern against the known-safe envelopes observed from real Quartus output. Raises on anything unknown. Must run before every flash.
• Round-trip test — read a Quartus RBF, replay every switch, re-read, compare. Zero dropped/hallucinated cells is table stakes.

Stage 5 — Bitstream finalization

The vendor almost certainly CRC-checks the configuration memory per frame. Check for frame CRC before flashing any codec-modified RBF or the FPGA will reject the load. Cyclone IV uses CRC-16/IBM (poly 0x8005, init 0xFE54, per-210-byte frame, frames 25..1751).

• Locate the CRC: flip one data bit in a known frame, flash, observe failure; then brute-force the algorithm over standard CRC-16 variants (~15 candidates) against known-good Quartus output.
• Implement a patch_rbf_crc() that recomputes all frame CRCs after codec writes.
• Mask CRC bytes in your read_switches() diff or they'll pollute the routing signal.

Stage 6 — Hardware verification (mandatory, not optional)

Every model, codec change, or bit discovery must be validated end-to-end on silicon before you trust it:

1. Build a minimal Verilog that exercises the feature (e.g. LED = LUT(K1,K2,K3,K4) with a known truth table)
2. Compile with Quartus → get quartus_rbf
3. Run your codec to reproduce the same bitstream → get codec_rbf
4. Diff: quartus_rbf vs codec_rbf should be zero in CRAM, differ only in CRC (which patch_rbf_crc then fixes)
5. Flash codec_rbf with openFPGALoader -c usb-blaster (or vendor equivalent)
6. Press keys, observe LED, match against expected truth table

If step 4 fails, your Stage 3/4 model is wrong. If step 6 fails but step 4 passed, your safety envelope is wrong (you wrote a physically unsafe bitstream) — do NOT retry, diagnose first.

Stage 7 — Jailbreak probe (when you suspect SKU rebinning)

If the same die ships as multiple SKUs in the same package, test whether the smaller SKU is just a software whitelist:

1. Byte-compare baseline RBFs across SKUs. Same Verilog, same pin constraints, different DEVICE=. If the RBFs are byte-identical → same physical die, pure fitter whitelist.

2. Coordinate legality probe. For each (X, Y) your small SKU claims doesn't exist, write a tiny jb.qsf with DEVICE = <big SKU> and set_location_assignment LCCOMB_X{x}_Y{y}_N0 -to "q", run quartus_fit, grep for "illegal location assignment" vs "Fitter was successful". Minutes per probe.

3. Block-column identity. Instantiate many altsyncram (M9K hint) + lpm_mult instances with VIRTUAL_PIN on all ports; let the fitter natural-place them; read M9K_X*_Y* / DSPMULT_X*_Y* placements from the fit report. That tells you which columns are RAM vs multiplier vs true non-fabric.

4. Dead-cell scan via XOR chain. Before trusting any newly-discovered LE, prove it's physically alive:

   chain[0] = K1 ^ K2;
   for each forbidden LE i:
       (* keep, preserve *) wire w_i;
       cycloneive_lcell_comb #(.lut_mask(16'hAAAA)) u_i (
           .dataa(chain[i]), .datab(0), .datac(0), .datad(0),
           .cin(0), .combout(w_i));
       assign chain[i+1] = w_i;
   LED = chain[N];
   

   Lock every u_i to its target LCCOMB_X{x}_Y{y}_N{n} in QSF. Healthy chain → LED = K1^K2. Any stuck-at, broken LUT, or dead routing breaks parity on at least one of the four key combinations. One bitstream validates up to ~1,800 cells in a single flash; bisect on failure.

5. Do NOT auto-enable the extended fabric in your codec until you've done Stage 3 for at least one new column and run a green-zone regression on a source in the jailbroken region. The model might hold, but "probably" isn't good enough for something that flashes to real silicon.

Stage 8 — Open-source toolchain integration

Once the codec and sig-cache are mature enough, build the full open-source flow:

1. Chipdb generator. Convert your project's routing corpus (sig-cache, geometry config) into a nextpnr-generic Python chipdb. Key design choices:

   • Pip cost hierarchy: sig-cache-backed pips get lowest cost so PathFinder prefers FASM-resolvable routes over abstract hops
   • Intra-LAB direct pips: bypass LOCAL track contention for carry chains and tight feedback
   • GCLK broadcast: dedicated global clock wire from IOB to every slice CLK (avoids clock competing for data bus)
   • Use --router router2 (PathFinder) not router1 — router1 can't explore multi-hop chains
   • Use --pre-pack to inject chipdb, NOT --run (which replaces the entire flow)

2. Yosys techmap. Map generic cells to your target primitives:

   • LUT4 → single-output combinational cell with INIT parameter
   • DFF → D/CLK/Q register cell
   • BRAM → M9K primitive with INIT attribute (if M9K codec is done)
   • Use read_verilog -lib prims.v to declare primitives without synthesizing them

3. np2fasm bridge. Convert nextpnr's placed-and-routed JSON to FASM directives:

   • Extract logical connectivity from cell connections + port_directions, not from abstract routing pips
   • For each (source_bel → sink_bel.port) arc, look up the sig-cache
   • Emit LUT, ROUTE, and M9K.INIT directives that fasm2rbf already parses
   • Map nextpnr I[n] indices to vendor port names (dataa/datab/datac/datad)

4. Coverage gap management. The sig-cache won't cover every possible placement:

   • Constrain placement to stay within covered regions, OR
   • Expand the sig-cache with targeted pair-diff compiles for uncovered arcs
   • Track coverage: np2fasm should report hit/miss/skip counts

5. Carry chains and other vendor-specific direct wires must be modeled in the chipdb from day one, or arithmetic designs are dead on arrival. nextpnr-generic only sees the bel/wire/pip graph you give it. If you don't declare cout→cin direct pips between adjacent LEs (and a CARRY primitive in the techmap to land on them), Yosys will emit +1 as a normal LUT ripple — typically 4 LEs per bit with self-feedback for the "previous value" input. Self-feedback routes (LE → same LE.dataX) are pathological for the standard two-LUT pair-diff mining template (you can't place lut1 and lut2 at the same site), so the resulting sig-cache entries are bloated noise and the design won't run on silicon. The fix is structural, not a sig-cache patch: declare carry chain pips, write a CARRY techmap, emit an LUT mode=arith FASM directive, and mine the arith-mode CRAM cells from a Quartus reference build (which uses cout→cin natively).

6. Cross-check before sinking time into the codec. After every np2fasm change, build the same Verilog in Quartus and flash both. If they behave differently, byte-diff the RBFs and look at which CRAM columns the cells live in. A column mismatch means the front-end emitted a different topology (missing primitive); a column match with cell mismatch means a real codec bug. Treating the two cases the same wastes days.

Stage 9 — Open-toolchain escape hatch (vendor-gold → BIT FASM)

Stage 8 depends on a routing-graph model that covers the target design's density. For small/medium designs this works; at SoC scale (~1000+ LEs) a simplified chipdb will over-use tracks and nextpnr's router will fail even though silicon has the resources. Rather than let this block the project, add a deterministic escape hatch that rides entirely on Stages 1–7 (CRAM geometry, codec, CRC):

gold.rbf         ←  vendor compile (Quartus / Vivado / Diamond)
   ↓
diff against nv_zero_global (or any stable baseline) at bit granularity
   ↓
emit one BIT offset bp directive per differing bit, including hdr + fab + CRC
   ↓
fasm2rbf (with patch_rbf_crc)  →  rebuilt.rbf  (cmp == gold.rbf)
   ↓
flash

Properties of this path (EP4CE6-validated end-to-end on NEORV32, 4712 LE / 19 M9K, 2026-04-23):

• Byte-identical to vendor gold. The rebuilt RBF has the same SHA256 as the vendor's own output. Silicon behavior is provably equivalent; no silicon-level validation gap.
• Scales with RBF size, not design density. NEORV32 compressed to 127 728 BIT directives; end-to-end wall time ≈ 0.5 s. The tool does not care about LE count, LAB density, or routing complexity.
• Inspectable intermediate. The BIT FASM is a flat cell list auditable against the codec's CRAM geometry. Useful as a substrate for bitstream-mutation experiments and as ground truth when you want to compare a native build's cells against the vendor's.
• Mandatory CRC coverage. Include hdr + fab + CRC bits all as BIT directives so patch_rbf_crc sees the full final state before recomputing — do NOT filter out CRC bits during the diff. CRC frames (25..1751) get re-computed from the now-correct data; header frames (0..24) are flipped directly.
• Not a replacement for native flow. The escape hatch still needs a vendor compile to produce gold. It's the pragmatic answer when "Verilog → open toolchain → silicon" isn't reachable yet; it does not substitute for finishing Stage 8. Use it to unblock downstream work (HW-verify a design depends on) while native routing improves in the background.

When to wire this in: as soon as Stage 7 CRC patcher and Stage 4 codec are both HW-clean. It's ~80 lines of Python (diff + emit + rebuild harness) and independent of Stage 8 progress.

When NOT to mistake this for completion: the escape hatch proves the codec is correct at SoC scale; it does NOT prove the native toolchain is. Keep the Stage 8 routing-model work moving in parallel — the long-term goal is Verilog-to-silicon without any vendor compile.

When to stop

Chase a signal if a decision tree can pick it up at >70% from a balanced corpus. Drop it if two rounds of corpus expansion leave the middle leaf at ~50%: the signal probably isn't in the input space at all (it's in the vendor's placement seed or internal cost-function ties you can't observe). Mark it NEGATIVE in the project log and move on. Don't sink compute into un-mineable phenomena.

Common footguns

• XOR-delta codec mistaken for absolute: if base has bits set, compensate mask = target ^ base_tt.
• Quartus optimizes away trivial probes (assign led = ~key becomes a direct pin-to-pin wire, 0 LCELLs). Always use primitive cells + (* keep, preserve *).
• Vendor pin labels are wrong. The board we probed had "RESET" labeled on what turned out to be KEY1. Hardware-probe every pin you depend on.
• Background shells self-deadlock if you write while pgrep -f quartus; do sleep; done and the waiter itself matches quartus in its command line. Use a more specific pattern or a PID file.
• CRC isn't optional on most modern FPGAs. If your codec RBF doesn't load but diffs clean against Quartus, it's almost certainly CRC.
• Non-LAB columns have different CRAM widths. Don't apply your LAB stride model to M9K/DSP columns — they're a different format.
• Non-LAB block mining requires real physical pins (DSP/M9K/PLL). VIRTUAL_PIN ON makes Quartus synthesize a ghost pin bank, and the fake routes dominate the pair-diff — any resulting "universal" cell set is 100% fiction. An EP4CE6 first-pass found a 62-cell MULT_GLOBAL_ON under VIRTUAL_PIN that had zero overlap with a real-pin recompile at the same LOC. Shrink the probe design to fit the board's free pin count if needed; never compromise with "real clk + virtual buses".
• Non-LAB mining must also filter CRAM-only (off ≥ first CRAM byte). The RBF header band carries a seed-dependent noise floor of a few bits per compile (on EP4CE6 it was 4-5 bits concentrated at byte 44 / byte 73), and those bits are shared by every block type's diff. A 5-seed null-hypothesis test on identical designs will reveal the floor in minutes; any "header-band finding" without this filter is fiction. This same noise band swallowed a separate FF-layer-2 investigation on the same project.
• Non-LAB blocks are opaque to STA. report_timing -show_routing treats DSPMULT and M9K as black-box cells and exposes only the chip-edge I/O buffers feeding them; internal per-site routing does not appear. Don't plan a per-site mining strategy around STA wire names for these blocks — use the LOC sweep + intra-block parameter sweep instead.
• LOC syntax for megafunctions is the hierarchical node path, not a coordinate alias. set_location_assignment DSPMULT_X20_Y10_N0 -to "lpm_mult:u|mult_qpl:auto_generated|mac_mult1" works; -to "mac_mult1" or -to "u" alone does not. Discover the correct path by compiling once with no LOC and grepping fit.rpt.

Reference constants (EP4CE6 / Cyclone IV E, silicon-verified)

Keep these in your project's config.py / CLAUDE.md but treat them as the CE6 whitelist, not ground truth:

LAB column step:  7,350 bytes
Pair spacing:     210 bytes
Ctrl→Data:        48 bytes
Y encoding:       slot = (Y-2)%3, group = (Y-2)//3
Frame CRC:        CRC-16/IBM poly 0x8005, init 0xFE54, reflected
Frame layout:     1752 × 210 bytes from byte 32, frames 25..1751 CRC-enforced
True LAB_X:       [3..33] minus {15,20,27}  (28 cols, not the 22 CE6 advertises)
True LAB_Y:       [2..21]                   (20 rows, not 19 — Y=15 is real)
True non-LAB:     X ∈ {15, 27} = M9K, X = 20 = embedded multiplier