crc32.c 15 KB

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