0001 A brief CRC tutorial.
0002
0003 A CRC is a long-division remainder. You add the CRC to the message,
0004 and the whole thing (message+CRC) is a multiple of the given
0005 CRC polynomial. To check the CRC, you can either check that the
0006 CRC matches the recomputed value, *or* you can check that the
0007 remainder computed on the message+CRC is 0. This latter approach
0008 is used by a lot of hardware implementations, and is why so many
0009 protocols put the end-of-frame flag after the CRC.
0010
0011 It's actually the same long division you learned in school, except that
0012 - We're working in binary, so the digits are only 0 and 1, and
0013 - When dividing polynomials, there are no carries. Rather than add and
0014 subtract, we just xor. Thus, we tend to get a bit sloppy about
0015 the difference between adding and subtracting.
0016
0017 Like all division, the remainder is always smaller than the divisor.
0018 To produce a 32-bit CRC, the divisor is actually a 33-bit CRC polynomial.
0019 Since it's 33 bits long, bit 32 is always going to be set, so usually the
0020 CRC is written in hex with the most significant bit omitted. (If you're
0021 familiar with the IEEE 754 floating-point format, it's the same idea.)
0022
0023 Note that a CRC is computed over a string of *bits*, so you have
0024 to decide on the endianness of the bits within each byte. To get
0025 the best error-detecting properties, this should correspond to the
0026 order they're actually sent. For example, standard RS-232 serial is
0027 little-endian; the most significant bit (sometimes used for parity)
0028 is sent last. And when appending a CRC word to a message, you should
0029 do it in the right order, matching the endianness.
0030
0031 Just like with ordinary division, you proceed one digit (bit) at a time.
0032 Each step of the division you take one more digit (bit) of the dividend
0033 and append it to the current remainder. Then you figure out the
0034 appropriate multiple of the divisor to subtract to being the remainder
0035 back into range. In binary, this is easy - it has to be either 0 or 1,
0036 and to make the XOR cancel, it's just a copy of bit 32 of the remainder.
0037
0038 When computing a CRC, we don't care about the quotient, so we can
0039 throw the quotient bit away, but subtract the appropriate multiple of
0040 the polynomial from the remainder and we're back to where we started,
0041 ready to process the next bit.
0042
0043 A big-endian CRC written this way would be coded like:
0044 for (i = 0; i < input_bits; i++) {
0045 multiple = remainder & 0x80000000 ? CRCPOLY : 0;
0046 remainder = (remainder << 1 | next_input_bit()) ^ multiple;
0047 }
0048
0049 Notice how, to get at bit 32 of the shifted remainder, we look
0050 at bit 31 of the remainder *before* shifting it.
0051
0052 But also notice how the next_input_bit() bits we're shifting into
0053 the remainder don't actually affect any decision-making until
0054 32 bits later. Thus, the first 32 cycles of this are pretty boring.
0055 Also, to add the CRC to a message, we need a 32-bit-long hole for it at
0056 the end, so we have to add 32 extra cycles shifting in zeros at the
0057 end of every message,
0058
0059 These details lead to a standard trick: rearrange merging in the
0060 next_input_bit() until the moment it's needed. Then the first 32 cycles
0061 can be precomputed, and merging in the final 32 zero bits to make room
0062 for the CRC can be skipped entirely. This changes the code to:
0063
0064 for (i = 0; i < input_bits; i++) {
0065 remainder ^= next_input_bit() << 31;
0066 multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
0067 remainder = (remainder << 1) ^ multiple;
0068 }
0069
0070 With this optimization, the little-endian code is particularly simple:
0071 for (i = 0; i < input_bits; i++) {
0072 remainder ^= next_input_bit();
0073 multiple = (remainder & 1) ? CRCPOLY : 0;
0074 remainder = (remainder >> 1) ^ multiple;
0075 }
0076
0077 The most significant coefficient of the remainder polynomial is stored
0078 in the least significant bit of the binary "remainder" variable.
0079 The other details of endianness have been hidden in CRCPOLY (which must
0080 be bit-reversed) and next_input_bit().
0081
0082 As long as next_input_bit is returning the bits in a sensible order, we don't
0083 *have* to wait until the last possible moment to merge in additional bits.
0084 We can do it 8 bits at a time rather than 1 bit at a time:
0085 for (i = 0; i < input_bytes; i++) {
0086 remainder ^= next_input_byte() << 24;
0087 for (j = 0; j < 8; j++) {
0088 multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
0089 remainder = (remainder << 1) ^ multiple;
0090 }
0091 }
0092
0093 Or in little-endian:
0094 for (i = 0; i < input_bytes; i++) {
0095 remainder ^= next_input_byte();
0096 for (j = 0; j < 8; j++) {
0097 multiple = (remainder & 1) ? CRCPOLY : 0;
0098 remainder = (remainder >> 1) ^ multiple;
0099 }
0100 }
0101
0102 If the input is a multiple of 32 bits, you can even XOR in a 32-bit
0103 word at a time and increase the inner loop count to 32.
0104
0105 You can also mix and match the two loop styles, for example doing the
0106 bulk of a message byte-at-a-time and adding bit-at-a-time processing
0107 for any fractional bytes at the end.
0108
0109 To reduce the number of conditional branches, software commonly uses
0110 the byte-at-a-time table method, popularized by Dilip V. Sarwate,
0111 "Computation of Cyclic Redundancy Checks via Table Look-Up", Comm. ACM
0112 v.31 no.8 (August 1998) p. 1008-1013.
0113
0114 Here, rather than just shifting one bit of the remainder to decide
0115 in the correct multiple to subtract, we can shift a byte at a time.
0116 This produces a 40-bit (rather than a 33-bit) intermediate remainder,
0117 and the correct multiple of the polynomial to subtract is found using
0118 a 256-entry lookup table indexed by the high 8 bits.
0119
0120 (The table entries are simply the CRC-32 of the given one-byte messages.)
0121
0122 When space is more constrained, smaller tables can be used, e.g. two
0123 4-bit shifts followed by a lookup in a 16-entry table.
0124
0125 It is not practical to process much more than 8 bits at a time using this
0126 technique, because tables larger than 256 entries use too much memory and,
0127 more importantly, too much of the L1 cache.
0128
0129 To get higher software performance, a "slicing" technique can be used.
0130 See "High Octane CRC Generation with the Intel Slicing-by-8 Algorithm",
0131 ftp://download.intel.com/technology/comms/perfnet/download/slicing-by-8.pdf
0132
0133 This does not change the number of table lookups, but does increase
0134 the parallelism. With the classic Sarwate algorithm, each table lookup
0135 must be completed before the index of the next can be computed.
0136
0137 A "slicing by 2" technique would shift the remainder 16 bits at a time,
0138 producing a 48-bit intermediate remainder. Rather than doing a single
0139 lookup in a 65536-entry table, the two high bytes are looked up in
0140 two different 256-entry tables. Each contains the remainder required
0141 to cancel out the corresponding byte. The tables are different because the
0142 polynomials to cancel are different. One has non-zero coefficients from
0143 x^32 to x^39, while the other goes from x^40 to x^47.
0144
0145 Since modern processors can handle many parallel memory operations, this
0146 takes barely longer than a single table look-up and thus performs almost
0147 twice as fast as the basic Sarwate algorithm.
0148
0149 This can be extended to "slicing by 4" using 4 256-entry tables.
0150 Each step, 32 bits of data is fetched, XORed with the CRC, and the result
0151 broken into bytes and looked up in the tables. Because the 32-bit shift
0152 leaves the low-order bits of the intermediate remainder zero, the
0153 final CRC is simply the XOR of the 4 table look-ups.
0154
0155 But this still enforces sequential execution: a second group of table
0156 look-ups cannot begin until the previous groups 4 table look-ups have all
0157 been completed. Thus, the processor's load/store unit is sometimes idle.
0158
0159 To make maximum use of the processor, "slicing by 8" performs 8 look-ups
0160 in parallel. Each step, the 32-bit CRC is shifted 64 bits and XORed
0161 with 64 bits of input data. What is important to note is that 4 of
0162 those 8 bytes are simply copies of the input data; they do not depend
0163 on the previous CRC at all. Thus, those 4 table look-ups may commence
0164 immediately, without waiting for the previous loop iteration.
0165
0166 By always having 4 loads in flight, a modern superscalar processor can
0167 be kept busy and make full use of its L1 cache.
0168
0169 Two more details about CRC implementation in the real world:
0170
0171 Normally, appending zero bits to a message which is already a multiple
0172 of a polynomial produces a larger multiple of that polynomial. Thus,
0173 a basic CRC will not detect appended zero bits (or bytes). To enable
0174 a CRC to detect this condition, it's common to invert the CRC before
0175 appending it. This makes the remainder of the message+crc come out not
0176 as zero, but some fixed non-zero value. (The CRC of the inversion
0177 pattern, 0xffffffff.)
0178
0179 The same problem applies to zero bits prepended to the message, and a
0180 similar solution is used. Instead of starting the CRC computation with
0181 a remainder of 0, an initial remainder of all ones is used. As long as
0182 you start the same way on decoding, it doesn't make a difference.