Table of Contents
- Introduction to CRC
- The Math Behind CRC: GF(2) Polynomials
- Division With XOR and a Shift Register
- Why the Top Bit of the Polynomial Disappears
- The Bit-by-Bit CRC Algorithm
- Worked Example: CRC-8 of a Single Byte
- Table-Based CRC
- Reflected CRC
- CRC-32: The 32-bit Workhorse
- A Real Implementation: CRC-32 in C
- RFC and Standards Reference
- Conclusion
Introduction to CRC
A cyclic Redundancy Check, or CRC, is a checksum algorithm built for the same job as Adler-32: proving that a block of data arrived exactly the way it was sent. Both algorithms attach a small, fixed-size value to a message so that a receiver can recompute it and compare. Where they differ is in how seriously they take the job. Adler-32 leans on simple running sums, which makes it fast but leaves it exposed to collisions, especially on short or repetitive data. CRC instead treats the data as a giant binary polynomial and performs actual polynomial division on it, which is more expensive to compute by hand but dramatically better at catching the kinds of errors that actually happen on real hardware, especially burst errors, where several consecutive bits get flipped together by a scratch on a disk, a noisy cable, or a bad radio signal.
That extra rigor is why CRC, not Adler-32, is the checksum sitting at the end of every chunk in the PNG file format. Every PNG chunk (IHDR, IDAT, IEND, and the rest) ends with a 4-byte CRC-32 value computed over the chunk's type and data, so a decoder can immediately tell whether that chunk was corrupted before it even tries to interpret it. The same CRC-32 also shows up in gzip and ZIP archives, in Ethernet frames as the frame check sequence, in SATA and USB packets, and inside most flash storage controllers, Anywhere data has to cross a wire or sit on unreliable media, there is a good chance a CRC is quietly watching it.
The algorithm itself is older than most of the formats that used it today. It was introduced by W. Wesley in 1961, in a paper that proposed using cyclic error-correcting codes for detecting errors in transmitted data. The specific 32-bit polynomial that Ethernet and most modern file formats now use was standardized later, in 1975, through the combined work of several researchers rather than a single inventor. That 1975 polynomial is the same one you will reused, in one form or another, throughout this article.
The Math Behind CRC: GF(2) Polynomials
A traditional checksum, like the two running sums in Adler-32, is built from ordinary addition. CRC takes a different route: it treats the entire data stream as one long binary polynomial and divides it by a fixed, predetermined polynomial called the generator polynomial. The remainder of that division is the CRC.
The division does not happen in ordinary arithmetic, though. It happens in GF(2), the Galois field of two elements, where there are only two possible values, 0 and 1, and addition and subtraction are both just the XOR operation. There is no carrying and no borrowing. This matters because it means “division” in CRC math is nothing like long division of decimal numbers; it is a sequence of XOR operations and bit shifts, which is exactly the kind of thing binary hardware is extremely good at doing quickly.
Concretely: every bit position in the data can be thought of as the coefficient of a term in a polynomial over x, where bit 7 of a byte is the coefficient of x^7, bit 6 is coefficient of x^6, and so on. The generator polynomial is a fixed, agreed-upon polynomial of this same kind. Dividing the (much longer) data polynomial by the generator polynomial, using XOR instead of subtraction at each step, produces a remainder that is shorter than the generator polynomial. That remainder is the CRC value.
Division With XOR and a Shift Register
Long division in school works by comparing the dividend to the divisor, subtracting if the divisor “fits”, and bringing down the next digit. Polynomial division over GF(2) works the same way conceptually, just with XOR standing in for subtraction:
- Look at the current value. If its most significant bit is 1, the divisor “fits” so XOR the divisor into the value (this is the GF(2) equivalent of subtracting it).
- Shift the value left by one bit to bring in the next bit of data, the same way long division brings down the next digit.
- Repeat until every bit of the (augmented) data has been processed. What's left over is the remainder, and that remainder is the CRC.
To actually carry this out, we need somewhere to hold the running value between steps. That holding place is called the shift register. Its width matches the CRC size: and 8-bit CRC uses an 8-bit register, a 16-bit CRC a 16-bit register, and a 32-bit CRC a 32-bit register. On every iteration, the register is shifted left by one bit, and, depending on the bit that was just shifted out of the top, the generator polynomial is XORed in or out, After the register has processed every bit of the message, its final contents are the CRC.
One subtlety worth calling out explicitly: the check for “does the divisor fit” has to happen using the top bit before the shift, not after. The implementation below captures the top bit first, then shifts, then decides whether to XOR in the polynomial, precisely so that the decision is always based on the bit that is about to be discarded by the shift.
Why the Top Bit of the Polynomial Disappears
Every CRC has a defining generator polynomial, usually written in the form:
x^8 + x^4 + x^3 + x^2 + 1which, if you write out every power of x from 8 down to 0 and mark which ones are present, corresponds to the binary pattern 1 0001 1101, or 0x11D in hexadecimal. Notice this pattern is 9 bits wide, one bit wider than the 8-bit CRC it defines. That leading 1, the coefficient of x^8, is always present in a polynomial's mathematical definition and is always dropped from the value actually stored in code. what you will see programmed as the “polynomial constant" for this example is just 0x1D, the remaining 0001 1101, with the top bit implied rather than written down.
The reason for dropping it is register width. An 8-bit CRC uses an 8-bit shift register, and every generator polynomial for an n-bit CRC always has its degree-n term equal to 1 by definition (that leading 1 is what makes it a valid n-bit generator in the first place). Since it's always there and always 1, storing it would just cost an extra bit for no benefit; instead, the width of the register itself stands in for that implicit top bit. During the table-generation and bit-processing logic, the algorithm behaves as though that top bit exists, it's the bit that is checked before every shift, it's just never physically stored in the polynomial constant.
The Bit-by-Bit CRC Algorithm
Putting the pieces together, computing a CRC over and entire message means:
- For each byte of the message, XOR it into the shift register.
- For each of the 8 bits in that byte, check whether the register's most significant bit is set, then shift the register left by one, then, if that saved bit was set, XOR the generator polynomial into the register.
- Once every byte has been processed this way, whatever remains in the register is the CRC.
Here is a direct implementation of that process for an 8-bit CRC using the generator polynomial 0x1D:
#define POLYNOMIAL 0X1D
#define CRC_INIT 0x00
#define MSB_MASK 0x80
typedef unsigned char byte;
byte calculate_crc8(const byte *data, size_t data_size) {
// example input: three bytes, e.g. { 0x12, 0xAB, 0xC2 }
if (NULL == data || 0 == data_size)
return 0;
byte crc = CRC_INIT;
for (size_t i = 0; i < data_size; i++) {
crc ^= data[i];
for (int b = 0; b < 8; b++) {
byte msb = crc & MSB_MASK; // save the bit is about to bring
// in the next bit position like
// bringing down a digit
crc <<= 1;
if (msb) {
crc ^= POLYNOMIAL;
}
}
}
return crc;
}Walking through what each line is doing:
- We reject a null pointer or a zero length buffer up front, since there is nothing meaningful to checksum.
crc ^= data[i]folds the next byte of the message into the register. XOR is being used here as the GF(2) equivalent of “add.”- Inside the inner loop,
msbcaptures the bit that is about to fall off the top of the register once we shift, this is the “does the divisor fit” test. crc <<= 1is the shift step, standing in for bringing down the next digit in long division.- If
msbwas set, we XOR in the polynomial, the GF(2) equivalent of performing the subtraction. - After all bytes and all bits have been processed, the register holds the final remainder: the CRC.
Worked Example: CRC-8 of a Single Byte
To see the mechanics play out with real numbers, let's compute the CRC-8 (polynomial 0x1D, initial value 0) of a single byte, 0xC2 (binary 1100 0010).
crc = 0x00
bit 0: msb=1, shift -> 1000 0100, XOR 0x1D -> 1001 1001
bit 1: msb=1, shift -> 0011 0010, XOR 0x1D -> 0010 1111
bit 2: msb=0, shift -> 0101 1110
bit 3: msb=0, shift -> 1011 1100
bit 4: msb=1, shift -> 0111 1000, XOR 0x1D -> 0110 0101
bit 5: msb=0, shift -> 1100 1010
bit 6: msb=1, shift -> 1001 0100, XOR 0x1D -> 1000 1001
bit 7: msb=1, shift -> 0001 0010, XOR 0x1D -> 0000 1111
Final CRC = 0x0FEach row shows the same three steps every time: save the top bit, shift left, and conditionally XOR in the polynomial. Eight rounds later, the leftover value in the register, 0x0F, is the CRC-8 checksum of that single byte. Feed in more bytes and the same three steps simply repeat for each one, with the register's state carrying over between bytes.
Table-Based CRC
Processing one bit at a time is easy to follow but slow. Since a byte only has 256 possible values, and the CRC contribution of a byte depends purely on its value combined with whatever is already in the register, we can precompute the result for all 256 possible input bytes exactly once, store the results in a lookup table, and then reduce the per-byte work in the main loop to a single table lookup plus one XOR. This turns the inner bit-loop (8 operations per byte) into a single array read, which is the difference between roughly O(n × 8) work and O(n) work for a message of n bytes, a substantial speedup for anything beyond trivially small inputs.
#define POLYNOMIAL 0x1D
#define TABLE_SIZE 256
#define MSB_MASK 0x80
typedef unsigned char byte;
static byte crc_table[TABLE_SIZE];
static int table_ready = 0;
static void crc8_table_init(void) {
for (int i = 0; i < TABLE_SIZE; i++) {
byte value = (byte)i;
for (int b = 0; b < 8; b++) {
if (value & MSB_MASK) {
value = (value << 1) ^ POLYNOMIAL;
} else {
value <<= 1;
}
}
crc_table[i] = value;
}
table_ready = 1;
}
byte crc8_calculate(const byte *data, size_t data_len) {
if (!table_ready) {
crc8_table_init();
}
byte crc = 0x00;
for (size_t i = 0; i < data_len; i++) {
crc = crc_table[crc ^ data[i]];
}
return crc;
}crc8_table_init runs the exact same bit-by-bit logic from the previous section, just once per possible byte value (0 through 255) instead of once per byte of real data, and stores each result at the index matching that byte value. crc8_calculate then does the actual work: for every byte of the message, it XORs the incoming byte with the current CRC register, uses that combined value as an index into the table, and replaces the register with whatever the table already computed for that case. The table only ever needs to be built once and can be reuse across every subsequent call, which is why implementations typically guard the init step with a flag like table_ready, or simply hardcode the finished table as a static array shipped with the source.
Reflected CRC
Everything so far has processed each byte starting from its most significant bit, and shifted the register left. This is sometimes called the "normal" or "MSB-first" form of CRC. A large number of real protocols, however, use the mirror image of this: the reflected form, which processes each byte starting from its least significant bit and shifts the register right instead of left.
The reason reflected CRCs exist at all comes down to how bits are actually transmitted on the wire. Many serial protocols, including the ones underlying Ethernet and most UART-based links, transmit the least significant bit of each byte first. A CRC hardware implementation that also consumes bits LSB-first fits that transmission order naturally, without needing to reverse any bits before or after the calculation. Because so much hardware was built this way, several major standards, including the CRC-32 used in Ethernet, PNG, gzip, and ZIP, standardized on the reflected form rather than the "textbook" MSB-first form, even though the underlying mathematics is equivalent either way.
Two more parameters go along with reflection, and both exist to make the CRC output line up correctly with data streams that already contain long runs of a single value:
- Initial value: instead of starting the register at all zero bits, many CRCs (including CRC-32) start it filled with all one bits. If the register started at zero, any message consisting entirely of leading zero bytes would produce the exact same CRC as a shorter message with fewer leading zeros, since XORing in zero changes nothing. Starting from all ones breaks that blind spot.
- Final XOR: for the same reason, the finished remainder is XORed with a fixed value (again, often all ones) before being reported as the final CRC. This guarantees that appending extra zero bytes to a message, or a corruption that flips a run of bits to zero, still changes the reported checksum rather than accidentally leaving it unchanged.
CRC-32: The 32-bit Workhorse
CRC-32 is simply CRC scaled up to a 32-bit register, and it is by far the most widely deployed CRC variant. Here is the same bit-by-bit approach from earlier, written for a 32-bit register using the "normal," non-reflected form and the well-known polynomial 0x04C11DB7:
#include
#include
#define MSB_MASK 0x80000000u
#define POLYNOMIAL 0x04C11DB7u
#define CRC_INIT 0xFFFFFFFFu
#define FINAL_XOR 0xFFFFFFFFu
typedef unsigned char byte;
typedef unsigned int u_int32;
u_int32 crc32(const byte *data, size_t data_len) {
u_int32 crc = CRC_INIT;
for (size_t i = 0; i < data_len; i++) {
crc ^= ((u_int32)data[i] << 24); // align this byte with the top of the 32-bit register
for (int b = 0; b < 8; b++) {
if (crc & MSB_MASK) {
crc = (crc << 1) ^ POLYNOMIAL;
} else {
crc <<= 1;
}
}
}
return crc ^ FINAL_XOR;
}The one detail that differs from the CRC-8 walkthrough is data[i] << 24. Because the register is 32 bits wide but each incoming byte is only 8 bits, the byte first has to be shifted up so that it occupies the top 8 bits of the register before it's XORed in, the same position an 8-bit register's single byte occupied naturally. Everything after that, the per-bit MSB check, the shift, and the conditional XOR, works exactly like the smaller example. The initial value and final XOR are both set to all ones here, for the reasons covered in the previous section.
A Real Implementation: CRC-32 in C
The version above is written for clarity, not speed, and it also uses the "normal" MSB-first form rather than the reflected form that most real-world CRC-32 users, including the PNG format, actually rely on. Here's a production-style implementation, taken from a small header/source pair in a steganography project on GitHub (crc32.h and crc32.c), that combines the table-based approach with the reflected form:
// crc32.h
#ifndef CRC32_H
#define CRC32_H
#include "../include/utils.h"
#include
#include
#define CRC32_TABLE_LEN 256
#define CRC32_INIT 0xFFFFFFFF
#define CRC32_XOROUT 0xFFFFFFFF
#define POLYNOMIAL 0xEDB88320
u_int32_t crc32_calculate(const byte *data, size_t size);
#endifThis specific parameter set, polynomial 0xEDB88320, initial value 0xFFFFFFFF, and a final XOR of 0xFFFFFFFF, is the exact CRC-32 variant used by PNG, gzip, ZIP, and Ethernet. It's commonly catalogued as CRC-32/ISO-HDLC (also referred to informally as "PKZIP CRC-32"). The polynomial constant here, 0xEDB88320, is the bit-reversed version of the 0x04C11DB7 used in the earlier "normal-form" example; reflecting the polynomial itself is what allows the implementation to process bits LSB-first without having to reverse the input or output separately.
// crc32.c
#include "../include/crc32.h"
#include "utils.h"
#include
#include
#include
static u_int32_t table[CRC32_TABLE_LEN];
static bool table_init = false;
static void init_crc32_table(void);
u_int32_t crc32_calculate(const byte *data, size_t size) {
u_int32_t crc = CRC32_INIT;
init_crc32_table();
for (size_t i = 0; i < size; i++) {
byte index = data[i] ^ (byte)crc;
crc = (crc >> BITS_PER_BYTE) ^ table[index];
}
return crc ^ CRC32_XOROUT;
}
static void init_crc32_table(void) {
if (table_init)
return;
for (u_int32_t i = 0; i < CRC32_TABLE_LEN; i++) {
u_int32_t current_byte = i;
for (size_t b = 0; b < BITS_PER_BYTE; b++) {
if (current_byte & 1) {
current_byte = (current_byte >> 1) ^ POLYNOMIAL;
} else {
current_byte >>= 1;
}
}
table[i] = current_byte;
}
table_init = true;
}A few things are worth pointing out about this implementation specifically:
- The table-building loop checks
current_byte & 1, the least significant bit, and shifts right, rather than checking the most significant bit and shifting left. This is the reflected form in action: bits are consumed from the bottom instead of the top. - In the main loop,
data[i] ^ (byte)crccombines the incoming byte with only the bottom 8 bits of the current CRC register, since in the reflected form the "active" byte of the register lives at the bottom, not the top. crc = (crc >> 8) ^ table[index]then shifts the whole 32-bit register right by a full byte and folds in the precomputed table result, doing the equivalent of eight individual bit-steps in one operation.table_initguards against rebuilding the table on every call; the table only depends on the polynomial, so it only ever needs to be computed once for the lifetime of the program.- The initial value and final XOR (both
0xFFFFFFFF) are exactly the reason a message made entirely of zero bytes, or a message with a bit flipped to zero at the very end, still produces a distinguishable, non-trivial checksum, as explained in the reflected CRC section above.
RFC and Standards Reference
Unlike Adler-32, which is defined directly inside an RFC, CRC-32 as used by PNG and friends is defined across a few closely related standards rather than one single RFC:
- The PNG file format itself is a W3C Recommendation (and ISO/IEC 15948) rather than an IETF RFC. Its Annex on CRC computation specifies exactly the polynomial, initial value, and final XOR used in this article, and is the authoritative source for how CRC is applied to PNG chunks.
- RFC 1952, which defines the gzip file format, specifies the same CRC-32 algorithm (polynomial
0xEDB88320in reflected form) for its own per-member checksum field. You can read it at RFC 1952 – GZIP File Format Specification. - The underlying 32-bit polynomial itself is also standardized outside the IETF entirely, in ITU-T Recommendation V.42 and in ISO/IEC 3309, both of which predate its adoption by PNG, gzip, and ZIP and are the reason this exact CRC-32 variant is sometimes labeled "CRC-32/ISO-HDLC" in checksum catalogs.
So while there's no single "RFC for CRC-32" the way there is an RFC 1950 for Adler-32, the algorithm is nonetheless precisely and consistently specified, it's simply documented across a standards body (ITU/ISO) rather than a single IETF document, with RFC 1952 serving as the closest thing to an IETF-hosted reference.
Conclusion
CRC earns its extra implementation complexity compared to something like Adler-32 by doing genuine polynomial division instead of simple summation, which makes it dramatically better at catching burst errors, the kind of correlated, contiguous corruption that shows up constantly in real transmission and storage hardware. That strength is exactly why it sits at the end of every PNG chunk, inside every gzip and ZIP entry, and in the frame check sequence of every Ethernet packet you've ever sent.
It isn't free of trade-offs, though. CRC is not a cryptographic construct: because it's a linear function over GF(2), an attacker who understands the algorithm can compute exactly what bits to flip in a message to leave the CRC unchanged, so it offers zero protection against deliberate tampering, only against accidental noise. It also requires more upfront implementation care than a sum-based checksum: getting the polynomial, initial value, reflection, and final XOR all correct and matching the target specification is easy to get subtly wrong, and a CRC computed with the wrong parameters will silently produce a different, equally "valid-looking" value.
Used within its intended scope, detecting accidental corruption rather than malicious modification, and implemented against the exact parameter set the target format expects (as the PNG/gzip/ZIP variant is above), CRC-32 remains one of the most efficient, well understood, and battle-tested tools available for verifying that a block of data really is what it claims to be.