2 * crc32.c --- CRC32 function
4 * Copyright (C) 2008 Theodore Ts'o.
7 * This file may be redistributed under the terms of the GNU Public
13 * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com>
14 * Nicer crc32 functions/docs submitted by linux@horizon.com. Thanks!
15 * Code was from the public domain, copyright abandoned. Code was
16 * subsequently included in the kernel, thus was re-licensed under the
19 * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com>
20 * Same crc32 function was used in 5 other places in the kernel.
21 * I made one version, and deleted the others.
22 * There are various incantations of crc32(). Some use a seed of 0 or ~0.
23 * Some xor at the end with ~0. The generic crc32() function takes
24 * seed as an argument, and doesn't xor at the end. Then individual
25 * users can do whatever they need.
26 * drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0.
27 * fs/jffs2 uses seed 0, doesn't xor with ~0.
28 * fs/partitions/efi.c uses seed ~0, xor's with ~0.
30 * This source code is licensed under the GNU General Public License,
31 * Version 2. See the file COPYING for more details.
45 #include "crc32defs.h"
47 #define tole(x) __constant_cpu_to_le32(x)
48 #define tobe(x) __constant_cpu_to_be32(x)
53 #include "crc32table.h"
58 * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32
59 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for
60 * other uses, or the previous crc32 value if computing incrementally.
61 * @p: pointer to buffer over which CRC is run
62 * @len: length of buffer @p
64 __u32 crc32_le(__u32 crc, unsigned char const *p, size_t len);
68 * In fact, the table-based code will work in this case, but it can be
69 * simplified by inlining the table in ?: form.
72 __u32 crc32_le(__u32 crc, unsigned char const *p, size_t len)
77 for (i = 0; i < 8; i++)
78 crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0);
82 #else /* Table-based approach */
84 __u32 crc32_le(__u32 crc, unsigned char const *p, size_t len)
87 const __u32 *b =(__u32 *)p;
88 const __u32 *tab = crc32table_le;
90 # ifdef WORDS_BIGENDIAN
91 # define DO_CRC(x) crc = tab[ ((crc >> 24) ^ (x)) & 255] ^ (crc<<8)
93 # define DO_CRC(x) crc = tab[ (crc ^ (x)) & 255 ] ^ (crc>>8)
96 crc = __cpu_to_le32(crc);
98 if(unlikely(((long)b)&3 && len)){
103 } while ((--len) && ((long)b)&3 );
105 if(likely(len >= 4)){
106 /* load data 32 bits wide, xor data 32 bits wide. */
107 size_t save_len = len & 3;
109 --b; /* use pre increment below(*++b) for speed */
117 b++; /* point to next byte(s) */
120 /* And the last few bytes */
129 return __le32_to_cpu(crc);
133 # elif CRC_LE_BITS == 4
136 crc = (crc >> 4) ^ crc32table_le[crc & 15];
137 crc = (crc >> 4) ^ crc32table_le[crc & 15];
140 # elif CRC_LE_BITS == 2
143 crc = (crc >> 2) ^ crc32table_le[crc & 3];
144 crc = (crc >> 2) ^ crc32table_le[crc & 3];
145 crc = (crc >> 2) ^ crc32table_le[crc & 3];
146 crc = (crc >> 2) ^ crc32table_le[crc & 3];
153 #endif /* UNITTEST */
156 * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
157 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for
158 * other uses, or the previous crc32 value if computing incrementally.
159 * @p: pointer to buffer over which CRC is run
160 * @len: length of buffer @p
162 __u32 crc32_be(__u32 crc, unsigned char const *p, size_t len);
166 * In fact, the table-based code will work in this case, but it can be
167 * simplified by inlining the table in ?: form.
170 __u32 crc32_be(__u32 crc, unsigned char const *p, size_t len)
175 for (i = 0; i < 8; i++)
177 (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE :
183 #else /* Table-based approach */
184 __u32 crc32_be(__u32 crc, unsigned char const *p, size_t len)
186 # if CRC_BE_BITS == 8
187 const __u32 *b =(const __u32 *)p;
188 const __u32 *tab = crc32table_be;
190 # ifdef WORDS_BIGENDIAN
191 # define DO_CRC(x) crc = tab[ ((crc >> 24) ^ (x)) & 255] ^ (crc<<8)
193 # define DO_CRC(x) crc = tab[ (crc ^ (x)) & 255 ] ^ (crc>>8)
196 crc = __cpu_to_be32(crc);
198 if(unlikely(((long)b)&3 && len)){
200 const __u8 *q = (const __u8 *)b;
202 b = (const __u32 *)q;
203 } while ((--len) && ((long)b)&3 );
205 if(likely(len >= 4)){
206 /* load data 32 bits wide, xor data 32 bits wide. */
207 size_t save_len = len & 3;
209 --b; /* use pre increment below(*++b) for speed */
217 b++; /* point to next byte(s) */
220 /* And the last few bytes */
223 const __u8 *q = (const __u8 *)b;
228 return __be32_to_cpu(crc);
232 # elif CRC_BE_BITS == 4
235 crc = (crc << 4) ^ crc32table_be[crc >> 28];
236 crc = (crc << 4) ^ crc32table_be[crc >> 28];
239 # elif CRC_BE_BITS == 2
242 crc = (crc << 2) ^ crc32table_be[crc >> 30];
243 crc = (crc << 2) ^ crc32table_be[crc >> 30];
244 crc = (crc << 2) ^ crc32table_be[crc >> 30];
245 crc = (crc << 2) ^ crc32table_be[crc >> 30];
253 * A brief CRC tutorial.
255 * A CRC is a long-division remainder. You add the CRC to the message,
256 * and the whole thing (message+CRC) is a multiple of the given
257 * CRC polynomial. To check the CRC, you can either check that the
258 * CRC matches the recomputed value, *or* you can check that the
259 * remainder computed on the message+CRC is 0. This latter approach
260 * is used by a lot of hardware implementations, and is why so many
261 * protocols put the end-of-frame flag after the CRC.
263 * It's actually the same long division you learned in school, except that
264 * - We're working in binary, so the digits are only 0 and 1, and
265 * - When dividing polynomials, there are no carries. Rather than add and
266 * subtract, we just xor. Thus, we tend to get a bit sloppy about
267 * the difference between adding and subtracting.
269 * A 32-bit CRC polynomial is actually 33 bits long. But since it's
270 * 33 bits long, bit 32 is always going to be set, so usually the CRC
271 * is written in hex with the most significant bit omitted. (If you're
272 * familiar with the IEEE 754 floating-point format, it's the same idea.)
274 * Note that a CRC is computed over a string of *bits*, so you have
275 * to decide on the endianness of the bits within each byte. To get
276 * the best error-detecting properties, this should correspond to the
277 * order they're actually sent. For example, standard RS-232 serial is
278 * little-endian; the most significant bit (sometimes used for parity)
279 * is sent last. And when appending a CRC word to a message, you should
280 * do it in the right order, matching the endianness.
282 * Just like with ordinary division, the remainder is always smaller than
283 * the divisor (the CRC polynomial) you're dividing by. Each step of the
284 * division, you take one more digit (bit) of the dividend and append it
285 * to the current remainder. Then you figure out the appropriate multiple
286 * of the divisor to subtract to being the remainder back into range.
287 * In binary, it's easy - it has to be either 0 or 1, and to make the
288 * XOR cancel, it's just a copy of bit 32 of the remainder.
290 * When computing a CRC, we don't care about the quotient, so we can
291 * throw the quotient bit away, but subtract the appropriate multiple of
292 * the polynomial from the remainder and we're back to where we started,
293 * ready to process the next bit.
295 * A big-endian CRC written this way would be coded like:
296 * for (i = 0; i < input_bits; i++) {
297 * multiple = remainder & 0x80000000 ? CRCPOLY : 0;
298 * remainder = (remainder << 1 | next_input_bit()) ^ multiple;
300 * Notice how, to get at bit 32 of the shifted remainder, we look
301 * at bit 31 of the remainder *before* shifting it.
303 * But also notice how the next_input_bit() bits we're shifting into
304 * the remainder don't actually affect any decision-making until
305 * 32 bits later. Thus, the first 32 cycles of this are pretty boring.
306 * Also, to add the CRC to a message, we need a 32-bit-long hole for it at
307 * the end, so we have to add 32 extra cycles shifting in zeros at the
308 * end of every message,
310 * So the standard trick is to rearrage merging in the next_input_bit()
311 * until the moment it's needed. Then the first 32 cycles can be precomputed,
312 * and merging in the final 32 zero bits to make room for the CRC can be
314 * This changes the code to:
315 * for (i = 0; i < input_bits; i++) {
316 * remainder ^= next_input_bit() << 31;
317 * multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
318 * remainder = (remainder << 1) ^ multiple;
320 * With this optimization, the little-endian code is simpler:
321 * for (i = 0; i < input_bits; i++) {
322 * remainder ^= next_input_bit();
323 * multiple = (remainder & 1) ? CRCPOLY : 0;
324 * remainder = (remainder >> 1) ^ multiple;
327 * Note that the other details of endianness have been hidden in CRCPOLY
328 * (which must be bit-reversed) and next_input_bit().
330 * However, as long as next_input_bit is returning the bits in a sensible
331 * order, we can actually do the merging 8 or more bits at a time rather
332 * than one bit at a time:
333 * for (i = 0; i < input_bytes; i++) {
334 * remainder ^= next_input_byte() << 24;
335 * for (j = 0; j < 8; j++) {
336 * multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
337 * remainder = (remainder << 1) ^ multiple;
340 * Or in little-endian:
341 * for (i = 0; i < input_bytes; i++) {
342 * remainder ^= next_input_byte();
343 * for (j = 0; j < 8; j++) {
344 * multiple = (remainder & 1) ? CRCPOLY : 0;
345 * remainder = (remainder << 1) ^ multiple;
348 * If the input is a multiple of 32 bits, you can even XOR in a 32-bit
349 * word at a time and increase the inner loop count to 32.
351 * You can also mix and match the two loop styles, for example doing the
352 * bulk of a message byte-at-a-time and adding bit-at-a-time processing
353 * for any fractional bytes at the end.
355 * The only remaining optimization is to the byte-at-a-time table method.
356 * Here, rather than just shifting one bit of the remainder to decide
357 * in the correct multiple to subtract, we can shift a byte at a time.
358 * This produces a 40-bit (rather than a 33-bit) intermediate remainder,
359 * but again the multiple of the polynomial to subtract depends only on
360 * the high bits, the high 8 bits in this case.
362 * The multiple we need in that case is the low 32 bits of a 40-bit
363 * value whose high 8 bits are given, and which is a multiple of the
364 * generator polynomial. This is simply the CRC-32 of the given
367 * Two more details: normally, appending zero bits to a message which
368 * is already a multiple of a polynomial produces a larger multiple of that
369 * polynomial. To enable a CRC to detect this condition, it's common to
370 * invert the CRC before appending it. This makes the remainder of the
371 * message+crc come out not as zero, but some fixed non-zero value.
373 * The same problem applies to zero bits prepended to the message, and
374 * a similar solution is used. Instead of starting with a remainder of
375 * 0, an initial remainder of all ones is used. As long as you start
376 * the same way on decoding, it doesn't make a difference.
384 const __u8 byte_rev_table[256] = {
385 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
386 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
387 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
388 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
389 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
390 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
391 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
392 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
393 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
394 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
395 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
396 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
397 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
398 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
399 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
400 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
401 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
402 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
403 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
404 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
405 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
406 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
407 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
408 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
409 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
410 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
411 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
412 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
413 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
414 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
415 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
416 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
419 static inline __u8 bitrev8(__u8 byte)
421 return byte_rev_table[byte];
424 static inline __u16 bitrev16(__u16 x)
426 return (bitrev8(x & 0xff) << 8) | bitrev8(x >> 8);
430 * bitrev32 - reverse the order of bits in a u32 value
431 * @x: value to be bit-reversed
433 static __u32 bitrev32(__u32 x)
435 return (bitrev16(x & 0xffff) << 16) | bitrev16(x >> 16);
438 #if 0 /*Not used at present */
441 buf_dump(char const *prefix, unsigned char const *buf, size_t len)
443 fputs(prefix, stdout);
445 printf(" %02x", *buf++);
451 static void bytereverse(unsigned char *buf, size_t len)
454 unsigned char x = bitrev8(*buf);
459 static void random_garbage(unsigned char *buf, size_t len)
462 *buf++ = (unsigned char) random();
465 #if 0 /* Not used at present */
466 static void store_le(__u32 x, unsigned char *buf)
468 buf[0] = (unsigned char) x;
469 buf[1] = (unsigned char) (x >> 8);
470 buf[2] = (unsigned char) (x >> 16);
471 buf[3] = (unsigned char) (x >> 24);
475 static void store_be(__u32 x, unsigned char *buf)
477 buf[0] = (unsigned char) (x >> 24);
478 buf[1] = (unsigned char) (x >> 16);
479 buf[2] = (unsigned char) (x >> 8);
480 buf[3] = (unsigned char) x;
484 * This checks that CRC(buf + CRC(buf)) = 0, and that
485 * CRC commutes with bit-reversal. This has the side effect
486 * of bytewise bit-reversing the input buffer, and returns
487 * the CRC of the reversed buffer.
489 static __u32 test_step(__u32 init, unsigned char *buf, size_t len)
494 crc1 = crc32_be(init, buf, len);
495 store_be(crc1, buf + len);
496 crc2 = crc32_be(init, buf, len + 4);
498 printf("\nCRC cancellation fail: 0x%08x should be 0\n",
501 for (i = 0; i <= len + 4; i++) {
502 crc2 = crc32_be(init, buf, i);
503 crc2 = crc32_be(crc2, buf + i, len + 4 - i);
505 printf("\nCRC split fail: 0x%08x\n", crc2);
508 /* Now swap it around for the other test */
510 bytereverse(buf, len + 4);
511 init = bitrev32(init);
512 crc2 = bitrev32(crc1);
513 if (crc1 != bitrev32(crc2))
514 printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n",
515 crc1, crc2, bitrev32(crc2));
516 crc1 = crc32_le(init, buf, len);
518 printf("\nCRC endianness fail: 0x%08x != 0x%08x\n", crc1,
520 crc2 = crc32_le(init, buf, len + 4);
522 printf("\nCRC cancellation fail: 0x%08x should be 0\n",
525 for (i = 0; i <= len + 4; i++) {
526 crc2 = crc32_le(init, buf, i);
527 crc2 = crc32_le(crc2, buf + i, len + 4 - i);
529 printf("\nCRC split fail: 0x%08x\n", crc2);
539 int main(int argc, char **argv)
541 unsigned char buf1[SIZE + 4];
542 unsigned char buf2[SIZE + 4];
543 unsigned char buf3[SIZE + 4];
545 __u32 crc1, crc2, crc3;
548 for (i = 0; i <= SIZE; i++) {
549 printf("\rTesting length %d...", i);
551 random_garbage(buf1, i);
552 random_garbage(buf2, i);
553 for (j = 0; j < i; j++)
554 buf3[j] = buf1[j] ^ buf2[j];
556 crc1 = test_step(INIT1, buf1, i);
557 crc2 = test_step(INIT2, buf2, i);
558 /* Now check that CRC(buf1 ^ buf2) = CRC(buf1) ^ CRC(buf2) */
559 crc3 = test_step(INIT1 ^ INIT2, buf3, i);
560 if (crc3 != (crc1 ^ crc2)) {
561 printf("CRC XOR fail: 0x%08x != 0x%08x ^ 0x%08x\n",
566 printf("\nAll test complete. No failures expected.\n");
570 #endif /* UNITTEST */