crc32.c 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501
  1. /*
  2. * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com>
  3. * Nicer crc32 functions/docs submitted by linux@horizon.com. Thanks!
  4. * Code was from the public domain, copyright abandoned. Code was
  5. * subsequently included in the kernel, thus was re-licensed under the
  6. * GNU GPL v2.
  7. *
  8. * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com>
  9. * Same crc32 function was used in 5 other places in the kernel.
  10. * I made one version, and deleted the others.
  11. * There are various incantations of crc32(). Some use a seed of 0 or ~0.
  12. * Some xor at the end with ~0. The generic crc32() function takes
  13. * seed as an argument, and doesn't xor at the end. Then individual
  14. * users can do whatever they need.
  15. * drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0.
  16. * fs/jffs2 uses seed 0, doesn't xor with ~0.
  17. * fs/partitions/efi.c uses seed ~0, xor's with ~0.
  18. *
  19. * This source code is licensed under the GNU General Public License,
  20. * Version 2. See the file COPYING for more details.
  21. */
  22. #include <linux/crc32.h>
  23. #include <linux/kernel.h>
  24. #include <linux/module.h>
  25. #include <linux/compiler.h>
  26. #include <linux/types.h>
  27. #include <linux/slab.h>
  28. #include <linux/init.h>
  29. #include <asm/atomic.h>
  30. #include "crc32defs.h"
  31. #if CRC_LE_BITS == 8
  32. #define tole(x) __constant_cpu_to_le32(x)
  33. #define tobe(x) __constant_cpu_to_be32(x)
  34. #else
  35. #define tole(x) (x)
  36. #define tobe(x) (x)
  37. #endif
  38. #include "crc32table.h"
  39. MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
  40. MODULE_DESCRIPTION("Ethernet CRC32 calculations");
  41. MODULE_LICENSE("GPL");
  42. /**
  43. * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32
  44. * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for
  45. * other uses, or the previous crc32 value if computing incrementally.
  46. * @p: pointer to buffer over which CRC is run
  47. * @len: length of buffer @p
  48. */
  49. u32 __attribute_pure__ crc32_le(u32 crc, unsigned char const *p, size_t len);
  50. #if CRC_LE_BITS == 1
  51. /*
  52. * In fact, the table-based code will work in this case, but it can be
  53. * simplified by inlining the table in ?: form.
  54. */
  55. u32 __attribute_pure__ crc32_le(u32 crc, unsigned char const *p, size_t len)
  56. {
  57. int i;
  58. while (len--) {
  59. crc ^= *p++;
  60. for (i = 0; i < 8; i++)
  61. crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0);
  62. }
  63. return crc;
  64. }
  65. #else /* Table-based approach */
  66. u32 __attribute_pure__ crc32_le(u32 crc, unsigned char const *p, size_t len)
  67. {
  68. # if CRC_LE_BITS == 8
  69. const u32 *b =(u32 *)p;
  70. const u32 *tab = crc32table_le;
  71. # ifdef __LITTLE_ENDIAN
  72. # define DO_CRC(x) crc = tab[ (crc ^ (x)) & 255 ] ^ (crc>>8)
  73. # else
  74. # define DO_CRC(x) crc = tab[ ((crc >> 24) ^ (x)) & 255] ^ (crc<<8)
  75. # endif
  76. crc = __cpu_to_le32(crc);
  77. /* Align it */
  78. if(unlikely(((long)b)&3 && len)){
  79. do {
  80. u8 *p = (u8 *)b;
  81. DO_CRC(*p++);
  82. b = (void *)p;
  83. } while ((--len) && ((long)b)&3 );
  84. }
  85. if(likely(len >= 4)){
  86. /* load data 32 bits wide, xor data 32 bits wide. */
  87. size_t save_len = len & 3;
  88. len = len >> 2;
  89. --b; /* use pre increment below(*++b) for speed */
  90. do {
  91. crc ^= *++b;
  92. DO_CRC(0);
  93. DO_CRC(0);
  94. DO_CRC(0);
  95. DO_CRC(0);
  96. } while (--len);
  97. b++; /* point to next byte(s) */
  98. len = save_len;
  99. }
  100. /* And the last few bytes */
  101. if(len){
  102. do {
  103. u8 *p = (u8 *)b;
  104. DO_CRC(*p++);
  105. b = (void *)p;
  106. } while (--len);
  107. }
  108. return __le32_to_cpu(crc);
  109. #undef ENDIAN_SHIFT
  110. #undef DO_CRC
  111. # elif CRC_LE_BITS == 4
  112. while (len--) {
  113. crc ^= *p++;
  114. crc = (crc >> 4) ^ crc32table_le[crc & 15];
  115. crc = (crc >> 4) ^ crc32table_le[crc & 15];
  116. }
  117. return crc;
  118. # elif CRC_LE_BITS == 2
  119. while (len--) {
  120. crc ^= *p++;
  121. crc = (crc >> 2) ^ crc32table_le[crc & 3];
  122. crc = (crc >> 2) ^ crc32table_le[crc & 3];
  123. crc = (crc >> 2) ^ crc32table_le[crc & 3];
  124. crc = (crc >> 2) ^ crc32table_le[crc & 3];
  125. }
  126. return crc;
  127. # endif
  128. }
  129. #endif
  130. /**
  131. * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
  132. * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for
  133. * other uses, or the previous crc32 value if computing incrementally.
  134. * @p: pointer to buffer over which CRC is run
  135. * @len: length of buffer @p
  136. */
  137. u32 __attribute_pure__ crc32_be(u32 crc, unsigned char const *p, size_t len);
  138. #if CRC_BE_BITS == 1
  139. /*
  140. * In fact, the table-based code will work in this case, but it can be
  141. * simplified by inlining the table in ?: form.
  142. */
  143. u32 __attribute_pure__ crc32_be(u32 crc, unsigned char const *p, size_t len)
  144. {
  145. int i;
  146. while (len--) {
  147. crc ^= *p++ << 24;
  148. for (i = 0; i < 8; i++)
  149. crc =
  150. (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE :
  151. 0);
  152. }
  153. return crc;
  154. }
  155. #else /* Table-based approach */
  156. u32 __attribute_pure__ crc32_be(u32 crc, unsigned char const *p, size_t len)
  157. {
  158. # if CRC_BE_BITS == 8
  159. const u32 *b =(u32 *)p;
  160. const u32 *tab = crc32table_be;
  161. # ifdef __LITTLE_ENDIAN
  162. # define DO_CRC(x) crc = tab[ (crc ^ (x)) & 255 ] ^ (crc>>8)
  163. # else
  164. # define DO_CRC(x) crc = tab[ ((crc >> 24) ^ (x)) & 255] ^ (crc<<8)
  165. # endif
  166. crc = __cpu_to_be32(crc);
  167. /* Align it */
  168. if(unlikely(((long)b)&3 && len)){
  169. do {
  170. u8 *p = (u8 *)b;
  171. DO_CRC(*p++);
  172. b = (u32 *)p;
  173. } while ((--len) && ((long)b)&3 );
  174. }
  175. if(likely(len >= 4)){
  176. /* load data 32 bits wide, xor data 32 bits wide. */
  177. size_t save_len = len & 3;
  178. len = len >> 2;
  179. --b; /* use pre increment below(*++b) for speed */
  180. do {
  181. crc ^= *++b;
  182. DO_CRC(0);
  183. DO_CRC(0);
  184. DO_CRC(0);
  185. DO_CRC(0);
  186. } while (--len);
  187. b++; /* point to next byte(s) */
  188. len = save_len;
  189. }
  190. /* And the last few bytes */
  191. if(len){
  192. do {
  193. u8 *p = (u8 *)b;
  194. DO_CRC(*p++);
  195. b = (void *)p;
  196. } while (--len);
  197. }
  198. return __be32_to_cpu(crc);
  199. #undef ENDIAN_SHIFT
  200. #undef DO_CRC
  201. # elif CRC_BE_BITS == 4
  202. while (len--) {
  203. crc ^= *p++ << 24;
  204. crc = (crc << 4) ^ crc32table_be[crc >> 28];
  205. crc = (crc << 4) ^ crc32table_be[crc >> 28];
  206. }
  207. return crc;
  208. # elif CRC_BE_BITS == 2
  209. while (len--) {
  210. crc ^= *p++ << 24;
  211. crc = (crc << 2) ^ crc32table_be[crc >> 30];
  212. crc = (crc << 2) ^ crc32table_be[crc >> 30];
  213. crc = (crc << 2) ^ crc32table_be[crc >> 30];
  214. crc = (crc << 2) ^ crc32table_be[crc >> 30];
  215. }
  216. return crc;
  217. # endif
  218. }
  219. #endif
  220. EXPORT_SYMBOL(crc32_le);
  221. EXPORT_SYMBOL(crc32_be);
  222. /*
  223. * A brief CRC tutorial.
  224. *
  225. * A CRC is a long-division remainder. You add the CRC to the message,
  226. * and the whole thing (message+CRC) is a multiple of the given
  227. * CRC polynomial. To check the CRC, you can either check that the
  228. * CRC matches the recomputed value, *or* you can check that the
  229. * remainder computed on the message+CRC is 0. This latter approach
  230. * is used by a lot of hardware implementations, and is why so many
  231. * protocols put the end-of-frame flag after the CRC.
  232. *
  233. * It's actually the same long division you learned in school, except that
  234. * - We're working in binary, so the digits are only 0 and 1, and
  235. * - When dividing polynomials, there are no carries. Rather than add and
  236. * subtract, we just xor. Thus, we tend to get a bit sloppy about
  237. * the difference between adding and subtracting.
  238. *
  239. * A 32-bit CRC polynomial is actually 33 bits long. But since it's
  240. * 33 bits long, bit 32 is always going to be set, so usually the CRC
  241. * is written in hex with the most significant bit omitted. (If you're
  242. * familiar with the IEEE 754 floating-point format, it's the same idea.)
  243. *
  244. * Note that a CRC is computed over a string of *bits*, so you have
  245. * to decide on the endianness of the bits within each byte. To get
  246. * the best error-detecting properties, this should correspond to the
  247. * order they're actually sent. For example, standard RS-232 serial is
  248. * little-endian; the most significant bit (sometimes used for parity)
  249. * is sent last. And when appending a CRC word to a message, you should
  250. * do it in the right order, matching the endianness.
  251. *
  252. * Just like with ordinary division, the remainder is always smaller than
  253. * the divisor (the CRC polynomial) you're dividing by. Each step of the
  254. * division, you take one more digit (bit) of the dividend and append it
  255. * to the current remainder. Then you figure out the appropriate multiple
  256. * of the divisor to subtract to being the remainder back into range.
  257. * In binary, it's easy - it has to be either 0 or 1, and to make the
  258. * XOR cancel, it's just a copy of bit 32 of the remainder.
  259. *
  260. * When computing a CRC, we don't care about the quotient, so we can
  261. * throw the quotient bit away, but subtract the appropriate multiple of
  262. * the polynomial from the remainder and we're back to where we started,
  263. * ready to process the next bit.
  264. *
  265. * A big-endian CRC written this way would be coded like:
  266. * for (i = 0; i < input_bits; i++) {
  267. * multiple = remainder & 0x80000000 ? CRCPOLY : 0;
  268. * remainder = (remainder << 1 | next_input_bit()) ^ multiple;
  269. * }
  270. * Notice how, to get at bit 32 of the shifted remainder, we look
  271. * at bit 31 of the remainder *before* shifting it.
  272. *
  273. * But also notice how the next_input_bit() bits we're shifting into
  274. * the remainder don't actually affect any decision-making until
  275. * 32 bits later. Thus, the first 32 cycles of this are pretty boring.
  276. * Also, to add the CRC to a message, we need a 32-bit-long hole for it at
  277. * the end, so we have to add 32 extra cycles shifting in zeros at the
  278. * end of every message,
  279. *
  280. * So the standard trick is to rearrage merging in the next_input_bit()
  281. * until the moment it's needed. Then the first 32 cycles can be precomputed,
  282. * and merging in the final 32 zero bits to make room for the CRC can be
  283. * skipped entirely.
  284. * This changes the code to:
  285. * for (i = 0; i < input_bits; i++) {
  286. * remainder ^= next_input_bit() << 31;
  287. * multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
  288. * remainder = (remainder << 1) ^ multiple;
  289. * }
  290. * With this optimization, the little-endian code is simpler:
  291. * for (i = 0; i < input_bits; i++) {
  292. * remainder ^= next_input_bit();
  293. * multiple = (remainder & 1) ? CRCPOLY : 0;
  294. * remainder = (remainder >> 1) ^ multiple;
  295. * }
  296. *
  297. * Note that the other details of endianness have been hidden in CRCPOLY
  298. * (which must be bit-reversed) and next_input_bit().
  299. *
  300. * However, as long as next_input_bit is returning the bits in a sensible
  301. * order, we can actually do the merging 8 or more bits at a time rather
  302. * than one bit at a time:
  303. * for (i = 0; i < input_bytes; i++) {
  304. * remainder ^= next_input_byte() << 24;
  305. * for (j = 0; j < 8; j++) {
  306. * multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
  307. * remainder = (remainder << 1) ^ multiple;
  308. * }
  309. * }
  310. * Or in little-endian:
  311. * for (i = 0; i < input_bytes; i++) {
  312. * remainder ^= next_input_byte();
  313. * for (j = 0; j < 8; j++) {
  314. * multiple = (remainder & 1) ? CRCPOLY : 0;
  315. * remainder = (remainder << 1) ^ multiple;
  316. * }
  317. * }
  318. * If the input is a multiple of 32 bits, you can even XOR in a 32-bit
  319. * word at a time and increase the inner loop count to 32.
  320. *
  321. * You can also mix and match the two loop styles, for example doing the
  322. * bulk of a message byte-at-a-time and adding bit-at-a-time processing
  323. * for any fractional bytes at the end.
  324. *
  325. * The only remaining optimization is to the byte-at-a-time table method.
  326. * Here, rather than just shifting one bit of the remainder to decide
  327. * in the correct multiple to subtract, we can shift a byte at a time.
  328. * This produces a 40-bit (rather than a 33-bit) intermediate remainder,
  329. * but again the multiple of the polynomial to subtract depends only on
  330. * the high bits, the high 8 bits in this case.
  331. *
  332. * The multile we need in that case is the low 32 bits of a 40-bit
  333. * value whose high 8 bits are given, and which is a multiple of the
  334. * generator polynomial. This is simply the CRC-32 of the given
  335. * one-byte message.
  336. *
  337. * Two more details: normally, appending zero bits to a message which
  338. * is already a multiple of a polynomial produces a larger multiple of that
  339. * polynomial. To enable a CRC to detect this condition, it's common to
  340. * invert the CRC before appending it. This makes the remainder of the
  341. * message+crc come out not as zero, but some fixed non-zero value.
  342. *
  343. * The same problem applies to zero bits prepended to the message, and
  344. * a similar solution is used. Instead of starting with a remainder of
  345. * 0, an initial remainder of all ones is used. As long as you start
  346. * the same way on decoding, it doesn't make a difference.
  347. */
  348. #ifdef UNITTEST
  349. #include <stdlib.h>
  350. #include <stdio.h>
  351. #if 0 /*Not used at present */
  352. static void
  353. buf_dump(char const *prefix, unsigned char const *buf, size_t len)
  354. {
  355. fputs(prefix, stdout);
  356. while (len--)
  357. printf(" %02x", *buf++);
  358. putchar('\n');
  359. }
  360. #endif
  361. static void bytereverse(unsigned char *buf, size_t len)
  362. {
  363. while (len--) {
  364. unsigned char x = bitrev8(*buf);
  365. *buf++ = x;
  366. }
  367. }
  368. static void random_garbage(unsigned char *buf, size_t len)
  369. {
  370. while (len--)
  371. *buf++ = (unsigned char) random();
  372. }
  373. #if 0 /* Not used at present */
  374. static void store_le(u32 x, unsigned char *buf)
  375. {
  376. buf[0] = (unsigned char) x;
  377. buf[1] = (unsigned char) (x >> 8);
  378. buf[2] = (unsigned char) (x >> 16);
  379. buf[3] = (unsigned char) (x >> 24);
  380. }
  381. #endif
  382. static void store_be(u32 x, unsigned char *buf)
  383. {
  384. buf[0] = (unsigned char) (x >> 24);
  385. buf[1] = (unsigned char) (x >> 16);
  386. buf[2] = (unsigned char) (x >> 8);
  387. buf[3] = (unsigned char) x;
  388. }
  389. /*
  390. * This checks that CRC(buf + CRC(buf)) = 0, and that
  391. * CRC commutes with bit-reversal. This has the side effect
  392. * of bytewise bit-reversing the input buffer, and returns
  393. * the CRC of the reversed buffer.
  394. */
  395. static u32 test_step(u32 init, unsigned char *buf, size_t len)
  396. {
  397. u32 crc1, crc2;
  398. size_t i;
  399. crc1 = crc32_be(init, buf, len);
  400. store_be(crc1, buf + len);
  401. crc2 = crc32_be(init, buf, len + 4);
  402. if (crc2)
  403. printf("\nCRC cancellation fail: 0x%08x should be 0\n",
  404. crc2);
  405. for (i = 0; i <= len + 4; i++) {
  406. crc2 = crc32_be(init, buf, i);
  407. crc2 = crc32_be(crc2, buf + i, len + 4 - i);
  408. if (crc2)
  409. printf("\nCRC split fail: 0x%08x\n", crc2);
  410. }
  411. /* Now swap it around for the other test */
  412. bytereverse(buf, len + 4);
  413. init = bitrev32(init);
  414. crc2 = bitrev32(crc1);
  415. if (crc1 != bitrev32(crc2))
  416. printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n",
  417. crc1, crc2, bitrev32(crc2));
  418. crc1 = crc32_le(init, buf, len);
  419. if (crc1 != crc2)
  420. printf("\nCRC endianness fail: 0x%08x != 0x%08x\n", crc1,
  421. crc2);
  422. crc2 = crc32_le(init, buf, len + 4);
  423. if (crc2)
  424. printf("\nCRC cancellation fail: 0x%08x should be 0\n",
  425. crc2);
  426. for (i = 0; i <= len + 4; i++) {
  427. crc2 = crc32_le(init, buf, i);
  428. crc2 = crc32_le(crc2, buf + i, len + 4 - i);
  429. if (crc2)
  430. printf("\nCRC split fail: 0x%08x\n", crc2);
  431. }
  432. return crc1;
  433. }
  434. #define SIZE 64
  435. #define INIT1 0
  436. #define INIT2 0
  437. int main(void)
  438. {
  439. unsigned char buf1[SIZE + 4];
  440. unsigned char buf2[SIZE + 4];
  441. unsigned char buf3[SIZE + 4];
  442. int i, j;
  443. u32 crc1, crc2, crc3;
  444. for (i = 0; i <= SIZE; i++) {
  445. printf("\rTesting length %d...", i);
  446. fflush(stdout);
  447. random_garbage(buf1, i);
  448. random_garbage(buf2, i);
  449. for (j = 0; j < i; j++)
  450. buf3[j] = buf1[j] ^ buf2[j];
  451. crc1 = test_step(INIT1, buf1, i);
  452. crc2 = test_step(INIT2, buf2, i);
  453. /* Now check that CRC(buf1 ^ buf2) = CRC(buf1) ^ CRC(buf2) */
  454. crc3 = test_step(INIT1 ^ INIT2, buf3, i);
  455. if (crc3 != (crc1 ^ crc2))
  456. printf("CRC XOR fail: 0x%08x != 0x%08x ^ 0x%08x\n",
  457. crc3, crc1, crc2);
  458. }
  459. printf("\nAll test complete. No failures expected.\n");
  460. return 0;
  461. }
  462. #endif /* UNITTEST */