Skip to content

Every CRC down to the bit

Andrey Shindarev edited this page Oct 19, 2026 · 1 revision

From CRC-3 to CRC-64, from whole bytes to single bits: the complete RevEng catalogue and any custom CRC, the frames of CAN, FlexRay and USB, CRCs of parts calculated in parallel and joined with combine, and the way back from a few samples of data and their CRCs to the name of the algorithm. This page walks through all four with code that runs as it stands and with the numbers it printed (JDK 25, Intel Core i9-9980HK, library 2.1.0). The reference of every call is in the README and in the javadoc.

In short

  • Complete. All 112 algorithms of the RevEng catalogue under 186 names, widths 3 to 64, 33 of them with a width that is not a multiple of 8; each one gives its catalogue check value for 123456789. What is not in the catalogue is a CrcModel.builder(width) away, widths 1 to 64.
  • Bits. model.valueOfBits(...) calculates the CRC of data that is not a whole number of bytes: the 35 bits of a CAN frame, the 20 bits of a FlexRay header, the 11 bits of a USB token.
  • Combine. first.combine(second) gives the CRC of both parts in 0.1–0.4 µs, whatever their size. A 512 MiB buffer in 16 parallel parts took 32 ms instead of 288 ms.
  • Find the model. StandardCrc.matching(data, value) names the algorithms that give the value. One sample of 16 bits or more is almost always enough, a sample of 8 bits or less needs two or three, and a sample of zeros proves nothing.

The catalogue is complete, and so is the model

A CRC is six numbers: width, polynomial, initial value, two reflections and the final XOR. The catalogue of Greg Cook's RevEng is the list of those that protocols and file formats actually use, and the library has all of it:

CrcModel modbus = CrcModel.of("CRC-16/MODBUS");               // by the name
CrcModel same = CrcModel.of("modbus");                         // by an alias, in any case of its letters
CrcModel crc32c = StandardCrc.CRC_32_ISCSI.model();            // by the constant
Width Algorithms Width Algorithms Width Algorithms
3 2 12 4 24 8
4 2 13 1 30 1
5 3 14 2 31 1
6 5 15 2 32 12
7 3 16 31 40 1
8 20 17 1 64 7
10 3 21 1
11 2

Complete means more than the list:

  • Every one is checked. Each of the 112 models gives its check value for 123456789 (0 mismatches in 112), and the tests compare each of them with a bit-by-bit implementation and with the residue of the catalogue.
  • The widths of the protocols are there. CRC-5/USB, CRC-11/FLEXRAY, CRC-15/CAN, CRC-17/CAN-FD, CRC-21/CAN-FD, CRC-24/FLEXRAY-A and -B, CRC-16/USB, CRC-16/MODBUS, CRC-8/SMBUS; 33 algorithms have a width that is not a multiple of 8, and the models handle them the same way as CRC-32.
  • Names and aliases are one algorithm. CRC-16/CCITT-FALSE, CRC-16/AUTOSAR and CRC-16/IBM-3740 are the same description, and the CRCs of models chosen by different names are equal if the parameters are the same.
  • What is not in the catalogue is not out of reach. Any parameter set of width 1 to 64 is a model, built by the builder, by CrcModel.of(width, poly, init, refin, refout, xorout) or from a parameter line of the catalogue:
CrcModel custom = CrcModel.builder(24).poly(0x864CFB).init(0xB704CE).refin(false).refout(false).xorout(0).build();
Optional<StandardCrc> known = StandardCrc.find(custom.parameters());   // Optional[CRC_24_OPENPGP]
CrcParameters line = CrcParameters.parse("width=15 poly=0x4599 init=0x0000 refin=false refout=false xorout=0x0000");
StandardCrc.find(line);                                                // Optional[CRC_15_CAN]

A parameter set that is not in the catalogue gets a unique name made of its parameters (CRC-16/P1021_IFFFF_X1234), and CrcModel.of(model.name()) gives the model back.

The CRC of bits: CAN, FlexRay, USB

Some protocols calculate the CRC of bits that do not fill whole bytes. A byte API cannot give it: padding the last byte with zeros changes the CRC (the 35 bits of the CAN frame below give 0x7F3C; the same bits padded to 5 bytes and given to value(data) give 0x6DED). valueOfBits reads the bits in the order in which the model reads the bits of a byte (the most significant bit first, the least significant one first if refin) and calculates the whole bytes with the lookup tables or the class of the JDK, the rest a bit at a time.

Protocol Model Bits under the CRC Call
CAN 2.0 CRC-15/CAN SOF, identifier, control field and data, without the stuff bits: 19 bits + 8 × DLC valueOfBits(byte[] frame, count)
FlexRay header CRC-11/FLEXRAY sync and startup indicators, frame ID and payload length: 20 bits valueOfBits(long, 20)
USB token CRC-5/USB the address and the endpoint: 11 bits valueOfBits(long, 11)
CAN FD CRC-17/CAN-FD, CRC-21/CAN-FD the fields of the frame up to the CRC valueOfBits(byte[], count)
FlexRay frame, USB data CRC-24/FLEXRAY-A/-B, CRC-16/USB whole bytes value(data)

A CAN frame of identifier 0x123, two bytes of data AB CD, the bits as the controller sends them (SOF 0, the 11 bits of the identifier, RTR, IDE and the reserved bit 0, DLC 2, the 16 bits of the data) are 35 bits, which fit into a long; longer frames, up to 19 + 64 = 83 bits, are packed into an array, the first bit being the most significant bit of the first byte:

CrcModel can = CrcModel.of("CRC-15/CAN");
long id = 0x123;
int dlc = 2;
long frame = id << 23 | (long) dlc << 16 | 0xABCD;                   // SOF 0, id, RTR/IDE/r0 = 000, DLC, data
long crc = can.valueOfBits(frame, 35);                               // 0x7F3C
long sent = frame << 15 | crc;                                       // the frame followed by its 15 bits of CRC
long receive = can.valueOfBits(sent, 50);                            // 0: the frame is valid
long damaged = can.valueOfBits(sent ^ 1L << 30, 50);                 // one bit flipped: 0x19FA
// the same frame as an array: 18 30 55 79 A0, 35 bits
byte[] packed = {0x12, 0x30, 0x55, 0x79, (byte) 0xA0};
long again = can.valueOfBits(packed, 35);                            // 0x7F3C

A valid frame followed by its CRC gives residue ^ xorout of the model, 0 for CRC-15/CAN, for every frame of any length: the receiver needs no comparison of the CRC with the one in the frame. The CRC is calculated over the destuffed bits, the stuff bits of the bus do not take part.

The FlexRay header and the USB token are short enough to be a long:

// FlexRay header: sync 1, startup 1, frame ID 0x2A, payload length 5 words
long header = 1L << 19 | 1L << 18 | 0x2AL << 7 | 5;                  // 0xC1505
long headerCrc = CrcModel.of("CRC-11/FLEXRAY").valueOfBits(header, 20);   // 0x624
// USB: address 0x15, endpoint 0xE, the first bit in bit 0 (refin)
long token = 0x15 | 0xEL << 7;
long tokenCrc = CrcModel.of("CRC-5/USB").valueOfBits(token, 11);     // 0x1D

The three values were compared with an independent bit-by-bit implementation. 0x1D is the value of the catalogue, the register of a reflected CRC; a datasheet that writes the five bits in the order of the transmission may show their reversal, 0b10111 = 0x17. A long is read from the bit count - 1 down to bit 0, or from bit 0 up if refin, and the bits above count are ignored.

There is the value only, no CRC: a CRC keeps the length of its data in bytes, for combine, crc(value, length) and equals, so the bits cannot be combined. A count that is negative or beyond the bits of the array throws ArrayIndexOutOfBoundsException, a count of a long outside 0 to 64 throws IllegalArgumentException.

Combine: the CRC of the whole from the CRCs of the parts

The CRC of part1 followed by part2 is known from the CRC of part1 and the CRC and the length of part2, without reading the data again, like zlib crc32_combine:

CrcModel model = CrcModel.of("CRC-32C", true);
CRC first = model.crc(part1);                     // calculated independently,
CRC second = model.crc(part2);                    // in parallel threads or on other nodes
CRC both = first.combine(second);                 // the CRC of part1 followed by part2
long value = model.combine(first.value(), second.value(), second.length());   // only the values are kept

The cost does not depend on the size of the data: one multiplication modulo the polynomial per bit set in the length of the second part, with 63 values per parameter set built on the first call. It took 85 ns for a second part of 1 MiB (one bit set), 145 ns for the same part with CRC-64/XZ and 417 ns for a part of 3,000,000 bytes (ten bits set). So a large buffer is calculated by the threads and joined at the end:

int parts = Runtime.getRuntime().availableProcessors();
int chunk = buffer.length / parts;
CRC whole = IntStream.range(0, parts).parallel()
        .mapToObj(i -> model.crc(buffer, i * chunk, i == parts - 1 ? buffer.length - i * chunk : chunk))
        .reduce(model.crc(), CRC::combine);       // the identity is the CRC of the empty data

The best of 5 rounds on a random buffer of 512 MiB, 16 threads, System.nanoTime and no JMH; every result equals the CRC of a single thread:

Model 1 thread 16 parts in parallel + combine Speed-up
CRC-32, lookup tables 288 ms 32 ms ×9.0
CRC-32C, lookup tables 277 ms 34 ms ×8.1
CRC-64/XZ, lookup tables 381 ms 54 ms ×7.1
CRC-32, java.util.zip.CRC32 (CrcModel.of("CRC-32", true)) 46 ms 19 ms ×2.4
CRC-32C, java.util.zip.CRC32C 48 ms 19 ms ×2.5

The class of the JDK calculates 12 GB/s with one thread and 28 GB/s with 16: it is limited by the memory more than by the CPU, which is why it gains less from the threads than the lookup tables do. Both CRCs of the parts have to have the same parameters (a model and its alias are fine, others give IllegalArgumentException), so a part may be calculated by the lookup tables and another by the class of the JDK: the values are equal. The same arithmetic resumes a calculation, model.crc(savedValue, savedLength).update(more), and joins the chunks of a multipart upload: each chunk is calculated when it arrives, in any order, and the CRCs are combined in the order of the file.

Find the model of a device

You know what is checked and what the result is: bytes of a frame or of a file and the CRC stored next to them. StandardCrc.matching(data, value) returns the algorithms of the catalogue whose CRC of the data is the value, a new modifiable EnumSet in the order of the catalogue:

byte[] frame = {0x01, 0x03, 0x00, 0x00, 0x00, 0x0A, (byte) 0xC5, (byte) 0xCD};
int n = frame.length - 2;                                      // the CRC is the last two bytes
long le = (frame[n] & 0xFF) | (frame[n + 1] & 0xFF) << 8;      // 0xCDC5
long be = (frame[n] & 0xFF) << 8 | (frame[n + 1] & 0xFF);      // 0xC5CD
StandardCrc.matching(frame, 0, n, be);                         // []
StandardCrc.matching(frame, 0, n, le);                         // [CRC_16_MODBUS]
StandardCrc.find("MODBUS").get().names();                      // [CRC-16/MODBUS, MODBUS]

The five questions to answer before the call, and what each wrong answer looks like:

  1. Which bytes are under the CRC? Everything before it is the first guess; the address byte or the start byte is often not. The same frame without its first byte gives []: try the ranges (0, n), (1, n - 1) and so on, the offset and the length are the arguments.
  2. In which byte order is the CRC stored? matching compares the value as it is, so read it both ways. The CRC of CRC-16/MODBUS is stored low byte first and that of CRC-16/XMODEM high byte first; the wrong reading gives [] here.
  3. How wide is it? The bytes of the CRC tell: two bytes are usually a 16-bit CRC, but a CRC-12 or a CRC-15 is stored in two bytes as well, with the high bits 0. A value with bits above the width of an algorithm does not match it, so a CRC-32 kept in an int is given as crc & 0xFFFFFFFFL: without the mask the call returns [], with it [CRC_32_ISO_HDLC].
  4. Is the sample random enough? See below.
  5. Is it a whole number of bytes? matching takes bytes. For bits, ask every model: StandardCrc.values() filtered by s.model().valueOfBits(bits, count) == value returned [CRC-15/CAN] for the CAN frame above. For a frame followed by its CRC, s.model().isValid(frame) (and isValid(frame, ByteOrder.BIG_ENDIAN) for the CRC high byte first) finds the algorithm without splitting the frame: for the Modbus frame it returned [CRC-16/MODBUS], and [] in the other byte order.

How many samples

An algorithm of n bits gives the value of random data with a probability of 2^-n, so the width of the value says how much a match means. On random values:

Value Matched by some algorithm Meaning
16 bits, random 2 of 2000 (0.1%) a match is almost certainly the algorithm
8 bits, random 264 of 2000 (13%) a match may be chance, take a second sample
up to 8 bits 35 of the 112 algorithms are 8 bits wide or less take three or more samples

For two bytes of data (AB), 71 of the 65536 values of 16 bits are matched by exactly one algorithm, 3 by two and 1 by three; of the 256 values of 8 bits 225 are matched by none, 27 by one, 3 by two and 1 by three. So a few samples narrow the set down; keep what matches all of them:

CrcModel device = CrcModel.of("CRC-8/SMBUS");                  // the unknown one
byte[] sample1 = {0x01};                                       // value 0x07
byte[] sample2 = {0x41, 0x42};                                 // value 0x87
Set<StandardCrc> found = StandardCrc.matching(sample1, device.value(sample1));
// [CRC_4_G_704, CRC_5_G_704, CRC_8_SMBUS]
found.retainAll(StandardCrc.matching(sample2, device.value(sample2)));
// [CRC_8_SMBUS]
CrcModel model = found.iterator().next().model();

Do not take zeros. Many algorithms have the initial value 0 and the final XOR 0, and then the CRC of zeros is 0: four zero bytes with the value 0 are matched by 41 algorithms, from CRC-4/G-704 to CRC-64/ECMA-182. Take data with all the bytes different, and take the samples from different frames.

Check the result with all the samples you have, then with the frames that are not samples: model.isValid(frame) is true for every frame of the device, and a single false is an error in the choice of the range or of the byte order, not of the algorithm.

The cost is small: a call for a 16-bit value of 64 bytes took 12 µs, for a 32-bit value of 64 bytes 2.9 µs and of 1 KiB 18 µs (the wider the value, the fewer algorithms are calculated). The first call of the JVM took 22 ms, class loading included, because it builds the lookup tables of the algorithms the value fits into, about 1 MiB for all 112, which the garbage collector collects when no model uses them (see Memory).

Nothing matches

The value is not an error when the call returns []; the list of causes, in the order to check them: the range of the bytes, the byte order, the mask of an int, bits instead of bytes (the loop above), and then a CRC that is not in the catalogue. The last one has a trick when the algorithm differs from a known one in the final XOR only: the XOR of the two values is the difference of the two xorout values, the same for all data. A device whose CRC-16 matches nothing:

// deviceValue(data) is the CRC the device sends for the data
CrcModel known = CrcModel.of("CRC-16/CCITT-FALSE");             // the same poly and init, a guess
long a = deviceValue("hello".getBytes()) ^ known.value("hello".getBytes());     // 0x1234
long b = deviceValue("world!!".getBytes()) ^ known.value("world!!".getBytes()); // 0x1234 again: only the xorout differs
CrcModel device = CrcModel.builder(16).poly(0x1021).init(0xFFFF).refin(false).refout(false).xorout(0x1234).build();
StandardCrc.find(device.parameters());                          // Optional.empty: it is not in the catalogue

If the XOR changes with the data, the initial value or the reflection differs as well; the RevEng tool finds the parameters of an unknown CRC from a few frames, and the line it prints is read by CrcParameters.parse(line).

What to call

You know You want Call
the name in the specification the model CrcModel.of(name)
a parameter line the model, its name in the catalogue CrcParameters.parse(line), StandardCrc.find(parameters), CrcModel.of(parameters)
bytes and their CRC the algorithm StandardCrc.matching(data, offset, length, value), several samples with retainAll
a frame with its CRC at the end the algorithm s.model().isValid(frame) for StandardCrc.values()
bits and their CRC the algorithm s.model().valueOfBits(bits, count) for StandardCrc.values()
the bits of a CAN, FlexRay or USB frame the CRC model.valueOfBits(bits, count)
the CRCs of the parts the CRC of the whole first.combine(second), model.combine(v1, v2, length2)
a CRC that is not in the catalogue the model CrcModel.builder(width)…build()