HashCrc32 / HashCrc32C

A CRC answers one question: did these bytes survive the wire or the disk? Not “which bucket does this key go in”, and not “can I trust whoever sent this” — those are HashFast and a cryptographic digest respectively. A CRC detects accidental corruption, and it detects it with a proof rather than with a probability.

// Our own record format: we choose, so we choose the stronger, faster polynomial.
const u32 checksum = HashCrc32C(record_bytes);

// A PNG chunk: the format chose for us, decades ago.
const u32 chunk_crc = HashCrc32(chunk_bytes);

Use HashCrc32C for anything new. It detects strictly more error patterns than the IEEE polynomial at every length that matters, and it is the one with a CPU instruction behind it — measured at 31.7 GB/s against 2.2 GB/s for the software path on the same machine. HashCrc32 (IEEE) exists so you can read and write the formats that specified it before that instruction existed: gzip, zip, PNG, Ethernet.

Which one, in one table

	HashCrc32C	HashCrc32
Standard name	CRC-32/ISCSI (Castagnoli)	CRC-32/ISO-HDLC (IEEE)
Choose it for	anything you design yourself	gzip, zip, PNG, Ethernet/PPP interop
Detects every 5-bit error up to	~655 bytes	33 bytes
Detects every 3-bit error up to	256 MB	~11 KB
Hardware	SSE4.2 crc32, used automatically	none on x86-64
Used by	iSCSI, LevelDB, ext4, Btrfs, Snappy, Kafka, Google Cloud Storage	gzip, zip, PNG, Ethernet, HDLC, PPP

Both are frozen forever. Their values are fixed by published standards, not by Basalt: any conformant implementation in any language reproduces them, and a file you checksum today stays verifiable in ten years. The classic self-check is in the test suite as a literal — HashCrc32("123456789") == 0xCBF43926, HashCrc32C("123456789") == 0xE3069283 — alongside 338 frozen vectors that are never regenerated. Those vectors were computed from the standards’ own definitions and then cross-checked, once, outside the repository, against existing implementations — zlib’s crc32 for the IEEE polynomial and Mark Adler’s crc32c.c (software and SSE4.2 paths) for Castagnoli — with all 338 agreeing on every path.

What the guarantee actually is

This is the part that makes a CRC worth having next to a hash.

• Every burst error of at most 32 bits is caught. Not “almost always” — always. That is a theorem about the code, and it is what a corrupted disk sector or a flipped run of bits on a cable produces.
• Every 5-bit error in a 655-byte message is caught by HashCrc32C, and every 3-bit error up to 256 MB. Beyond those lengths the guarantee degrades to a probability like any other checksum’s.
• No hash offers either. HashRapidV3Nano gives you a birthday bound over random inputs, which says nothing about the two-bit flip a bad cable produced.

What it does not promise

A CRC is not a security check, and this is provable rather than presumed

A CRC is a linear map: given any message and any CRC value you want it to have, computing the bytes to append is closed-form arithmetic that takes microseconds. Anyone who can modify your data can keep the checksum valid. A CRC detects accidents, and nothing else. If you are defending against someone who chooses the bytes, you need a cryptographic digest and a key.

Not a hash for a table

The output of a CRC is not distributed the way a hash table needs — the low bits of a short input track the input’s own bits. Key your maps with HashFast.

Checksumming something you cannot hold in memory

The running CRC is the whole state, so continuing is one call and there is nothing to allocate, initialise or finalise:

u32 checksum = 0;                     // 0 starts a CRC — not 0xFFFFFFFF
for (String8 chunk = ReadNextChunk(file); chunk.size != 0; chunk = ReadNextChunk(file))
{
    checksum = HashCrc32CExtend(checksum, chunk);
}

HashCrc32C(bytes) is exactly HashCrc32CExtend(0, bytes), splitting the input anywhere gives the same answer, and extending by nothing changes nothing. The start value is 0 because the standard’s pre- and post-inversion live inside the function — the same convention as zlib’s crc32(crc, buf, len), Go’s crc32.Update and LevelDB’s Extend, so a value you compute here is one those tools recognise.

One consequence worth stating: the CRC of an empty input is 0. That falls out of the definition, not from a convention, and it is why 0 is the right thing to start from. It does not mean you can read “checksum is 0” as “no data” — a non-empty input can produce 0 too.

Speed, and where it comes from

HashCrc32C checks once per call whether the CPU has SSE4.2 and, if so, runs three independent crc32 instruction streams over the input and recombines them. The instruction has a latency of three cycles and a throughput of one, so a single stream would leave two thirds of the machine idle; three streams is where the order-of-magnitude gap over the software path comes from. You do not opt in, and there is nothing to configure — a CPU without SSE4.2 gets the same values from the software kernel, which the test suite proves bit-identical over the whole frozen corpus.

HashCrc32 has no such path: x86-64 has no instruction for the IEEE polynomial. That is the second reason to prefer HashCrc32C when the choice is yours.

API summary

Parameters, assertions and the full contract are documented in basalt/core/hash/HashCrc32.h.

Signature	Purpose
HashCrc32C(String8 bytes)	The frozen CRC-32C of the bytes. Use this one for new work.
HashCrc32CExtend(u32 previous, String8 bytes)	Continues a running CRC-32C. 0 starts one.
HashCrc32(String8 bytes)	The frozen CRC-32 (IEEE) of the bytes. For gzip/zip/PNG interop.
HashCrc32Extend(u32 previous, String8 bytes)	Continues a running CRC-32 (IEEE). 0 starts one.