A CRC Function in C

Part II · Module 22 · Chapter 22.4 · A CRC Function in C

1. The First Function That Can Be Wrong

Chapters 22.1 to 22.3 imported an adder and a divider, and that was deliberate: nothing in them could be wrong, so every failure was wiring and the wiring is what those chapters were about.

A CRC is different. It can be wrong in at least six ways that all compile, all run, and all return confident-looking hex — the wrong polynomial, the wrong initial value, the wrong bit order, the wrong final XOR, the wrong width, or bytes folded in the wrong end. None of those is a C error. Each produces a number.

So this chapter is not more wiring. It is the first one where the question "is the imported function correct?" has to be answered, and the whole chapter is about the fact that for this particular function, it can be.

2. Why a CRC Is the Canonical First Import

Four reasons, and it is worth separating them because only the second is special.

It is the right division of labour. A CRC is a tight loop over bytes with shifts and conditional XORs. It is natural in C and tedious in SystemVerilog, and a testbench that needs one on every packet wants it fast.

It has a published check value. Every standard CRC is specified with the value it produces over the nine ASCII characters 123456789. That is unusual and extremely valuable: correctness is decidable, by a comparison you can write in one line, against a number you did not choose.

It is pure. No state, no allocation, no lifetime, no ownership — none of Modules 20 and 21's hazards apply. Chapter 22.7 adds state deliberately; here there is none to get wrong.

And its failure mode is total. Chapter 21.7 §3 measured it: a one-byte difference in the input produces a completely unrelated output. The same property means a wrong implementation produces an unrelated output too, so a CRC cannot be nearly right — which makes a single check conclusive in a way that a single check of an arithmetic function would not be.

3. The Structure: One File, No Simulator Types

/* crc.h */
uint8_t  crc8_smbus(const uint8_t *p, size_t n);
uint16_t crc16_ccitt_false(const uint8_t *p, size_t n);
uint8_t  crc8_update(uint8_t c, uint8_t x);     /* one byte, incremental */

/* crc.c */
uint8_t crc8_smbus(const uint8_t *p, size_t n) {
    uint8_t c = 0x00u;
    for (size_t i = 0; i < n; i++) { c ^= p[i];
        for (int b = 0; b < 8; b++) c = (uint8_t)((c & 0x80u) ? ((c << 1) ^ 0x07u) : (c << 1)); }
    return c;
}

Nothing in that file knows a simulator exists. It is Chapter 15.2's masks and Chapter 15.4's shifting, in a loop. The glue that connects it to the import lives in a different file, and the point of the separation is immediate and measurable.

Measured, crc.c compiled into a plain C binary with a test main, before any simulator is involved:

  CRC-8/SMBUS        over "123456789" = 0xF4  (published 0xF4): match
  CRC-16/CCITT-FALSE over "123456789" = 0x29B1 (published 0x29B1): match
  incremental form gives 0xF4 -- same as one-shot: yes

Measured, the same crc.c called from a running simulation:

  CRC-8  over the 9-byte check string = 0xf4 (published 0xF4):   match
  CRC-16 over the 9-byte check string = 0x29b1 (published 0x29B1): match
  built one byte at a time            = 0xf4 -- same as one-shot: yes

Same file, two programs, same published values. That is Chapter 21.3 §5's argument made concrete: the C-side build exists before the import does and remains the faster way to find a bug afterwards.

4. The Incremental Form, and Why It Must Agree

A testbench rarely has the whole packet in one place. More often it has a byte per cycle, so the useful import folds one byte at a time:

uint8_t crc8_update(uint8_t c, uint8_t x) {
    c ^= x;
    for (int b = 0; b < 8; b++) c = (uint8_t)((c & 0x80u) ? ((c << 1) ^ 0x07u) : (c << 1));
    return c;
}

Measured, folded across the nine check bytes in a SystemVerilog loop:

  built one byte at a time = 0xf4 -- same as one-shot: yes

That agreement is a real check and not a formality, because the two forms can disagree in ways that are easy to write: an initial value applied in the wrong place, a final XOR applied once per byte instead of once per message, or a reflection done at the wrong granularity. All of those leave the one-shot version correct and the incremental version wrong, or the reverse.

So the incremental form gets two checks: against the published value, and against the one-shot form. Measured, both pass.

And the prefix table is worth having for exactly this reason — it is what you compare against when a partial message disagrees:

  1 byte(s) -> 0x97      6 byte(s) -> 0xfd
  2 byte(s) -> 0x72      7 byte(s) -> 0x78
  3 byte(s) -> 0xc0      8 byte(s) -> 0xc7
  4 byte(s) -> 0xc2      9 byte(s) -> 0xf4
  5 byte(s) -> 0xcb

The ninth entry is the published check value; the other eight are the intermediate states a byte-at-a-time implementation passes through, and a mismatch at byte k localises the bug far better than a mismatch at the end.

5. Checking It, in the Order That Localises Faults

Chapter 22.1 §6's isolating order, applied to a function that can itself be wrong:

First, the published check value in a C main. One comparison, no simulator, and it settles whether the algorithm is the algorithm. If this fails, nothing else is worth looking at — and measured, this is where both CRCs were confirmed before the import existed.

Second, the incremental form against the one-shot form, still in C. §4's second check.

Third, the same two checks through the import. If the C passed and the import fails, the fault is in the wiring, and Chapter 22.1 §5 catalogued what each wiring failure looks like.

Fourth, the prefix table, for localising anything that still disagrees.

The order matters because each step has a different suspect list, and running them out of order means debugging the union.

6. The Misconception: My CRC Matches the Design's, So Both Are Right

"I ran the model and the RTL on a thousand packets and every CRC matched. The implementation is confirmed."

This is Chapter 18.2's point in the place it is most tempting, so it is worth being precise about what the agreement does and does not establish.

Two implementations agreeing is evidence that they share their assumptions. If the model and the design were written from the same specification paragraph, by people who read it the same way, they will agree on a thousand packets while both using the wrong initial value, the wrong reflection, or the wrong final XOR — and the thousand packets will not contain a counterexample, because there isn't one.

A CRC's failure mode makes this worse, not better. §2 noted that a wrong CRC produces an unrelated answer rather than a near-miss. The flip side is that two copies of the same wrong CRC produce the same unrelated answer, every time, with total confidence.

The published check value is an independent third party. It was computed by whoever specified the algorithm, before either implementation existed, and it is the only thing in the loop that cannot have inherited your misreading. Measured, it costs one comparison: crc8_smbus("123456789", 9) == 0xF4.

The corrected position:

Agreement between your model and the design tells you they match each other. The published check value tells you they match the specification. These are different claims, and only the second is the one anybody wants — so check against the published value first, and let the agreement with the design mean what it should: that the design is right too.

7. What You Should Be Able to Say Now

1. The first import where the function itself can be wrong — and a CRC can be wrong six ways that all return confident hex.
2. Four reasons a CRC is the canonical first import: the right division of labour · a published check value · purity · a total failure mode.
3. Put the CRC in its own file with no simulator types. The glue goes elsewhere.
4. Measured in a plain C binary: 0xF4 and 0x29B1, both matching their published values, before any simulator.
5. Measured through the import: the same 0xF4 and 0x29B1 from the same crc.c.
6. The incremental form must agree with the one-shot form — measured, 0xF4 both ways — and the ways they can disagree are easy to write.
7. Keep the prefix table — 0x97 0x72 0xc0 0xc2 0xcb 0xfd 0x78 0xc7 0xf4 — because a mismatch at byte k localises far better than one at the end.
8. An unplanned 22.2 confirmation: the 8-bit-declared function delivered 0x000000f4 when nothing narrowed it. Assign into a sized variable and let that be what the testbench sees.
9. Check in isolating order: published value in C · incremental against one-shot in C · both through the import · then the prefix table.
10. Agreeing with the design is not correctness (18.2) — two copies of the same wrong CRC agree perfectly. The published value is the independent third party.

8. Exercises

1. Implement CRC-8/SMBUS and compare it against 0xF4 over 123456789 before writing any glue. What does a failure here rule out?
2. Change the polynomial by one bit and run the check again. How close is the wrong answer to the right one, and what does that tell you about near-misses?
3. Implement the incremental form and fold the nine check bytes through it. Does it agree with the one-shot? Name two ways it could have failed while the one-shot passed.
4. Produce the prefix table for 1 to 9 bytes. If an implementation first disagrees at byte 3, what does that narrow the fault down to?
5. Compile the same crc.c into a plain binary and into the simulation. Confirm both give the published value. What is in the file that makes this possible?
6. Print an imported 8-bit result with and without a sized destination. Explain the difference using Chapter 22.2 §3.
7. A colleague reports a model and RTL agreeing on 10,000 packets. What single check would you ask for, and why does the sample size not substitute for it?
8. Pick a CRC used in a protocol you know. Find its published check value and write the one-line assertion.

9. Summary

• The first import whose function can itself be wrong — six ways, all returning plausible hex.
• Why a CRC: natural in C · a published check value · pure · a total failure mode.
• Its own file, no simulator types — the glue lives elsewhere.
• Measured, plain C binary: 0xF4 and 0x29B1, both matching published values, before any simulator.
• Measured, through the import: the same values from the same crc.c.
• The incremental form agrees with the one-shot — measured 0xF4 — and that is a real check.
• Keep the prefix table for localisation: 0x97 0x72 0xc0 0xc2 0xcb 0xfd 0x78 0xc7 0xf4.
• An unplanned 22.2 confirmation: 0x000000f4 from an 8-bit-declared function. Narrow at a sized destination.
• Check in isolating order, C first.
• Agreement with the design is not correctness — the published value is the only independent party, and it costs one line.

A CRC is a one-way function: the testbench computes it and compares. The more interesting imports come in pairs, where one function undoes what the other did — and a pair can be checked against itself in a way a single function cannot, which turns out to be both a powerful technique and a trap with a specific shape.