ferrite-lithic811 tests · 21 designs

ferrite-lithic-corpus305 tests

The corpus

Twenty-one real algorithms written the way hardware would want them, each checked three ways.

Every other crate in the workspace is a tool, and a tool gets tested with inputs chosen by whoever wrote it — so its tests drift toward what the tool was built to do. A corpus entry is a real algorithm written the way hardware would want it, checked three ways: against the original crate as the golden model, through the step testbench, and against Verilator by compiling the emitted Verilog and comparing cycle by cycle.

The golden model is never a second implementation by the same hand. Where the original crate is unavailable the entry says so on its own docs and states what stands in for it, because a self-consistent round trip proves the design is self-consistent and nothing else.

Step by step

  1. 01

    Tier 1 — LFSRs and checksums

    The cheapest designs with a register and a bit stream, and the ones that find toolchain bugs first. crc3 is three flops and two conditional XORs consuming one byte per cycle; crc32 is 32 of them. ghash is the most ASIC-shaped thing in the corpus: a CPU does it with carryless multiply over limbs, and the hardware is 128 cycles of a register and two conditional XORs.

    4entriescrc3, crc32, lfsr, ghash — and crc32fast's 8 kB lookup is the cost hardware does not pay
  2. 02

    Tier 2 — block ciphers

    Two opposite cases on purpose. sha256 is 64 unrolled rounds with no ROM and a perfectly serial dependency chain, which is exactly the case SIMD cannot help. chacha20 is the counterexample to "ROM-heavy ciphers are the ASIC ones": no tables at all, just 32-bit adders and rotators, one block per cycle for pure ALU. aes is the opposite again — the S-box ROM *is* the design.

    200duplicate armsAES's S-box as a case_ tree, where real silicon would infer one block RAM
  3. 03

    Tier 3 — codecs

    hex and base64 are LUTs, and they are in the corpus because they are the tier that validates the toolchain cheaply: a nibble or sextet table is the smallest honest test of whether a ROM lowers correctly and whether the cosimulator compares the right columns.

  4. 04

    Tier 4 — automata

    One state register, one transition table, one byte per edge. This tier contains the project's most useful negative result: memchr is a real design and it still loses to the CPU — by 4.2×, measured per byte at an assumed 1 GHz. The design does one byte per clock edge; the crate does 32 bytes per AVX2 instruction. It is in the corpus anyway, as the baseline the other two are measured against, and because 31 nodes against a CPU core is not a close comparison either way.

    1 vs 32bytes per edge vs per AVX2 instructionThe structural comparison. The wall-clock ratio is measured at run time and printed, but it varies by build profile and host — see benchmarks.
  5. 05

    Tier 5 — data infrastructure

    The decode kernels of a columnar engine, and the probabilistic sketches. bitpack, rle, roaring, hamming, sorting, sketch. The sorting network is measured for depth against the formula rather than against its own layer count, which is the check that catches a network that is one layer short and still sorts most inputs.

  6. 06

    Tier 6 — packet

    packet is a 64-byte header window in and every field out, combinationally. It reports three verdicts rather than one — valid is structural, csum_ok is integrity, malformed is ipv4 && !valid — because a switch that wants to drop bad checksums and a switch that only cares whether a header parses want different things, and folding the checksum into valid would cost the first one its choice.

  7. 07

    Tier 7 — entropy coding

    huffman, fse and the deflate bit layer. This tier arrived in one commit and had never been run: fourteen of its tests failed. Four were the design's and four were the tests' own, plus a mistyped constant in the sketches. Finishing it is the subject of the findings page.

    14failuresin the one commit that added the tier — none of which were in the tools
  8. 08

    What each design is checked against

    Three checks, and they are not interchangeable. The differential against the original crate catches a design that computes the wrong function. The step testbench catches a design whose handshake or timing is wrong. The Verilator equivalence catches an emitter bug that the simulator happens to agree with. A design needs all three, and the ones with no golden crate say so on their own docs.

What bites

  • No design here beats a CPU at being a CPU

    The corpus is not an argument that hardware beats software at software's job. It is an argument that the toolchain is correct, and the evidence is that a 60-line shift-and-XOR design found four bugs that 471 tests of the tools had not.

  • Every table is a multiplexer tree

    There is no initialised-memory node in the IR, so a 512-entry Huffman decode table is 512 arms of case_. Correct, and not what anyone would ship. Design::rom documents the cost instead of hiding it.

Notes

  • measured

    An earlier revision of this page quoted a number it should not have

    It computes the ratio at run time and prints it without asserting it, because the figure depends on host load, build profile and clock rather than on the design. What it times is the software simulator: an interpreter stepping one node per cycle costs far more wall time than the single clock edge it models, so the number is a debugging signal and not a hardware result. tests/speed.rs exists to replace it, comparing the design's actual clock edges against the crate and quoting the frequency it assumed. The corpus keeps the loss because it is a loss — and the loss is structural, not an artefact of any ratio.

  • decision

    The golden model is never the same author

    Where a real crate exists it is used. Where none does — FSE has no golden crate in this workspace at all — the entry states the ceiling of its own evidence rather than implying more.