11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com> 31da177e4SLinus Torvalds * Nicer crc32 functions/docs submitted by linux@horizon.com. Thanks! 41da177e4SLinus Torvalds * Code was from the public domain, copyright abandoned. Code was 51da177e4SLinus Torvalds * subsequently included in the kernel, thus was re-licensed under the 61da177e4SLinus Torvalds * GNU GPL v2. 71da177e4SLinus Torvalds * 81da177e4SLinus Torvalds * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com> 91da177e4SLinus Torvalds * Same crc32 function was used in 5 other places in the kernel. 101da177e4SLinus Torvalds * I made one version, and deleted the others. 111da177e4SLinus Torvalds * There are various incantations of crc32(). Some use a seed of 0 or ~0. 121da177e4SLinus Torvalds * Some xor at the end with ~0. The generic crc32() function takes 131da177e4SLinus Torvalds * seed as an argument, and doesn't xor at the end. Then individual 141da177e4SLinus Torvalds * users can do whatever they need. 151da177e4SLinus Torvalds * drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0. 161da177e4SLinus Torvalds * fs/jffs2 uses seed 0, doesn't xor with ~0. 171da177e4SLinus Torvalds * fs/partitions/efi.c uses seed ~0, xor's with ~0. 181da177e4SLinus Torvalds * 191da177e4SLinus Torvalds * This source code is licensed under the GNU General Public License, 201da177e4SLinus Torvalds * Version 2. See the file COPYING for more details. 211da177e4SLinus Torvalds */ 221da177e4SLinus Torvalds 231da177e4SLinus Torvalds #include <linux/crc32.h> 241da177e4SLinus Torvalds #include <linux/kernel.h> 251da177e4SLinus Torvalds #include <linux/module.h> 261da177e4SLinus Torvalds #include <linux/compiler.h> 271da177e4SLinus Torvalds #include <linux/types.h> 281da177e4SLinus Torvalds #include <linux/init.h> 291da177e4SLinus Torvalds #include <asm/atomic.h> 301da177e4SLinus Torvalds #include "crc32defs.h" 311da177e4SLinus Torvalds #if CRC_LE_BITS == 8 321da177e4SLinus Torvalds # define tole(x) __constant_cpu_to_le32(x) 331da177e4SLinus Torvalds #else 341da177e4SLinus Torvalds # define tole(x) (x) 354f2a9463SJoakim Tjernlund #endif 364f2a9463SJoakim Tjernlund 374f2a9463SJoakim Tjernlund #if CRC_BE_BITS == 8 384f2a9463SJoakim Tjernlund # define tobe(x) __constant_cpu_to_be32(x) 394f2a9463SJoakim Tjernlund #else 401da177e4SLinus Torvalds # define tobe(x) (x) 411da177e4SLinus Torvalds #endif 421da177e4SLinus Torvalds #include "crc32table.h" 431da177e4SLinus Torvalds 441da177e4SLinus Torvalds MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>"); 451da177e4SLinus Torvalds MODULE_DESCRIPTION("Ethernet CRC32 calculations"); 461da177e4SLinus Torvalds MODULE_LICENSE("GPL"); 471da177e4SLinus Torvalds 48ddcaccbcSJoakim Tjernlund #if CRC_LE_BITS == 8 || CRC_BE_BITS == 8 49ddcaccbcSJoakim Tjernlund 50ddcaccbcSJoakim Tjernlund static inline u32 51*836e2af9SJoakim Tjernlund crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) 52ddcaccbcSJoakim Tjernlund { 53ddcaccbcSJoakim Tjernlund # ifdef __LITTLE_ENDIAN 54*836e2af9SJoakim Tjernlund # define DO_CRC(x) crc = tab[0][(crc ^ (x)) & 255] ^ (crc >> 8) 55*836e2af9SJoakim Tjernlund # define DO_CRC4 crc = tab[3][(crc) & 255] ^ \ 56*836e2af9SJoakim Tjernlund tab[2][(crc >> 8) & 255] ^ \ 57*836e2af9SJoakim Tjernlund tab[1][(crc >> 16) & 255] ^ \ 58*836e2af9SJoakim Tjernlund tab[0][(crc >> 24) & 255] 59ddcaccbcSJoakim Tjernlund # else 60*836e2af9SJoakim Tjernlund # define DO_CRC(x) crc = tab[0][((crc >> 24) ^ (x)) & 255] ^ (crc << 8) 61*836e2af9SJoakim Tjernlund # define DO_CRC4 crc = tab[0][(crc) & 255] ^ \ 62*836e2af9SJoakim Tjernlund tab[1][(crc >> 8) & 255] ^ \ 63*836e2af9SJoakim Tjernlund tab[2][(crc >> 16) & 255] ^ \ 64*836e2af9SJoakim Tjernlund tab[3][(crc >> 24) & 255] 65ddcaccbcSJoakim Tjernlund # endif 664f2a9463SJoakim Tjernlund const u32 *b; 67ddcaccbcSJoakim Tjernlund size_t rem_len; 68ddcaccbcSJoakim Tjernlund 69ddcaccbcSJoakim Tjernlund /* Align it */ 704f2a9463SJoakim Tjernlund if (unlikely((long)buf & 3 && len)) { 71ddcaccbcSJoakim Tjernlund do { 724f2a9463SJoakim Tjernlund DO_CRC(*buf++); 734f2a9463SJoakim Tjernlund } while ((--len) && ((long)buf)&3); 74ddcaccbcSJoakim Tjernlund } 75ddcaccbcSJoakim Tjernlund rem_len = len & 3; 76ddcaccbcSJoakim Tjernlund /* load data 32 bits wide, xor data 32 bits wide. */ 77ddcaccbcSJoakim Tjernlund len = len >> 2; 784f2a9463SJoakim Tjernlund b = (const u32 *)buf; 79ddcaccbcSJoakim Tjernlund for (--b; len; --len) { 80ddcaccbcSJoakim Tjernlund crc ^= *++b; /* use pre increment for speed */ 81*836e2af9SJoakim Tjernlund DO_CRC4; 82ddcaccbcSJoakim Tjernlund } 83ddcaccbcSJoakim Tjernlund len = rem_len; 84ddcaccbcSJoakim Tjernlund /* And the last few bytes */ 85ddcaccbcSJoakim Tjernlund if (len) { 86ddcaccbcSJoakim Tjernlund u8 *p = (u8 *)(b + 1) - 1; 87ddcaccbcSJoakim Tjernlund do { 88ddcaccbcSJoakim Tjernlund DO_CRC(*++p); /* use pre increment for speed */ 89ddcaccbcSJoakim Tjernlund } while (--len); 90ddcaccbcSJoakim Tjernlund } 91ddcaccbcSJoakim Tjernlund return crc; 924f2a9463SJoakim Tjernlund #undef DO_CRC 93*836e2af9SJoakim Tjernlund #undef DO_CRC4 94ddcaccbcSJoakim Tjernlund } 95ddcaccbcSJoakim Tjernlund #endif 962f72100cSRandy Dunlap /** 972f72100cSRandy Dunlap * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32 982f72100cSRandy Dunlap * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for 992f72100cSRandy Dunlap * other uses, or the previous crc32 value if computing incrementally. 1002f72100cSRandy Dunlap * @p: pointer to buffer over which CRC is run 1012f72100cSRandy Dunlap * @len: length of buffer @p 1022f72100cSRandy Dunlap */ 103e8c44319SRalf Baechle u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len); 1042f72100cSRandy Dunlap 1051da177e4SLinus Torvalds #if CRC_LE_BITS == 1 1061da177e4SLinus Torvalds /* 1071da177e4SLinus Torvalds * In fact, the table-based code will work in this case, but it can be 1081da177e4SLinus Torvalds * simplified by inlining the table in ?: form. 1091da177e4SLinus Torvalds */ 1101da177e4SLinus Torvalds 111e8c44319SRalf Baechle u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) 1121da177e4SLinus Torvalds { 1131da177e4SLinus Torvalds int i; 1141da177e4SLinus Torvalds while (len--) { 1151da177e4SLinus Torvalds crc ^= *p++; 1161da177e4SLinus Torvalds for (i = 0; i < 8; i++) 1171da177e4SLinus Torvalds crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0); 1181da177e4SLinus Torvalds } 1191da177e4SLinus Torvalds return crc; 1201da177e4SLinus Torvalds } 1211da177e4SLinus Torvalds #else /* Table-based approach */ 1221da177e4SLinus Torvalds 123e8c44319SRalf Baechle u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) 1241da177e4SLinus Torvalds { 1251da177e4SLinus Torvalds # if CRC_LE_BITS == 8 126*836e2af9SJoakim Tjernlund const u32 (*tab)[] = crc32table_le; 1271da177e4SLinus Torvalds 1281da177e4SLinus Torvalds crc = __cpu_to_le32(crc); 129ddcaccbcSJoakim Tjernlund crc = crc32_body(crc, p, len, tab); 1301da177e4SLinus Torvalds return __le32_to_cpu(crc); 1311da177e4SLinus Torvalds # elif CRC_LE_BITS == 4 1321da177e4SLinus Torvalds while (len--) { 1331da177e4SLinus Torvalds crc ^= *p++; 1341da177e4SLinus Torvalds crc = (crc >> 4) ^ crc32table_le[crc & 15]; 1351da177e4SLinus Torvalds crc = (crc >> 4) ^ crc32table_le[crc & 15]; 1361da177e4SLinus Torvalds } 1371da177e4SLinus Torvalds return crc; 1381da177e4SLinus Torvalds # elif CRC_LE_BITS == 2 1391da177e4SLinus Torvalds while (len--) { 1401da177e4SLinus Torvalds crc ^= *p++; 1411da177e4SLinus Torvalds crc = (crc >> 2) ^ crc32table_le[crc & 3]; 1421da177e4SLinus Torvalds crc = (crc >> 2) ^ crc32table_le[crc & 3]; 1431da177e4SLinus Torvalds crc = (crc >> 2) ^ crc32table_le[crc & 3]; 1441da177e4SLinus Torvalds crc = (crc >> 2) ^ crc32table_le[crc & 3]; 1451da177e4SLinus Torvalds } 1461da177e4SLinus Torvalds return crc; 1471da177e4SLinus Torvalds # endif 1481da177e4SLinus Torvalds } 1491da177e4SLinus Torvalds #endif 1501da177e4SLinus Torvalds 1512f72100cSRandy Dunlap /** 1522f72100cSRandy Dunlap * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32 1532f72100cSRandy Dunlap * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for 1542f72100cSRandy Dunlap * other uses, or the previous crc32 value if computing incrementally. 1552f72100cSRandy Dunlap * @p: pointer to buffer over which CRC is run 1562f72100cSRandy Dunlap * @len: length of buffer @p 1572f72100cSRandy Dunlap */ 158e8c44319SRalf Baechle u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len); 1592f72100cSRandy Dunlap 1601da177e4SLinus Torvalds #if CRC_BE_BITS == 1 1611da177e4SLinus Torvalds /* 1621da177e4SLinus Torvalds * In fact, the table-based code will work in this case, but it can be 1631da177e4SLinus Torvalds * simplified by inlining the table in ?: form. 1641da177e4SLinus Torvalds */ 1651da177e4SLinus Torvalds 166e8c44319SRalf Baechle u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) 1671da177e4SLinus Torvalds { 1681da177e4SLinus Torvalds int i; 1691da177e4SLinus Torvalds while (len--) { 1701da177e4SLinus Torvalds crc ^= *p++ << 24; 1711da177e4SLinus Torvalds for (i = 0; i < 8; i++) 1721da177e4SLinus Torvalds crc = 1731da177e4SLinus Torvalds (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE : 1741da177e4SLinus Torvalds 0); 1751da177e4SLinus Torvalds } 1761da177e4SLinus Torvalds return crc; 1771da177e4SLinus Torvalds } 1781da177e4SLinus Torvalds 1791da177e4SLinus Torvalds #else /* Table-based approach */ 180e8c44319SRalf Baechle u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) 1811da177e4SLinus Torvalds { 1821da177e4SLinus Torvalds # if CRC_BE_BITS == 8 183*836e2af9SJoakim Tjernlund const u32 (*tab)[] = crc32table_be; 1841da177e4SLinus Torvalds 1851da177e4SLinus Torvalds crc = __cpu_to_be32(crc); 186ddcaccbcSJoakim Tjernlund crc = crc32_body(crc, p, len, tab); 1871da177e4SLinus Torvalds return __be32_to_cpu(crc); 1881da177e4SLinus Torvalds # elif CRC_BE_BITS == 4 1891da177e4SLinus Torvalds while (len--) { 1901da177e4SLinus Torvalds crc ^= *p++ << 24; 1911da177e4SLinus Torvalds crc = (crc << 4) ^ crc32table_be[crc >> 28]; 1921da177e4SLinus Torvalds crc = (crc << 4) ^ crc32table_be[crc >> 28]; 1931da177e4SLinus Torvalds } 1941da177e4SLinus Torvalds return crc; 1951da177e4SLinus Torvalds # elif CRC_BE_BITS == 2 1961da177e4SLinus Torvalds while (len--) { 1971da177e4SLinus Torvalds crc ^= *p++ << 24; 1981da177e4SLinus Torvalds crc = (crc << 2) ^ crc32table_be[crc >> 30]; 1991da177e4SLinus Torvalds crc = (crc << 2) ^ crc32table_be[crc >> 30]; 2001da177e4SLinus Torvalds crc = (crc << 2) ^ crc32table_be[crc >> 30]; 2011da177e4SLinus Torvalds crc = (crc << 2) ^ crc32table_be[crc >> 30]; 2021da177e4SLinus Torvalds } 2031da177e4SLinus Torvalds return crc; 2041da177e4SLinus Torvalds # endif 2051da177e4SLinus Torvalds } 2061da177e4SLinus Torvalds #endif 2071da177e4SLinus Torvalds 2081da177e4SLinus Torvalds EXPORT_SYMBOL(crc32_le); 2091da177e4SLinus Torvalds EXPORT_SYMBOL(crc32_be); 2101da177e4SLinus Torvalds 2111da177e4SLinus Torvalds /* 2121da177e4SLinus Torvalds * A brief CRC tutorial. 2131da177e4SLinus Torvalds * 2141da177e4SLinus Torvalds * A CRC is a long-division remainder. You add the CRC to the message, 2151da177e4SLinus Torvalds * and the whole thing (message+CRC) is a multiple of the given 2161da177e4SLinus Torvalds * CRC polynomial. To check the CRC, you can either check that the 2171da177e4SLinus Torvalds * CRC matches the recomputed value, *or* you can check that the 2181da177e4SLinus Torvalds * remainder computed on the message+CRC is 0. This latter approach 2191da177e4SLinus Torvalds * is used by a lot of hardware implementations, and is why so many 2201da177e4SLinus Torvalds * protocols put the end-of-frame flag after the CRC. 2211da177e4SLinus Torvalds * 2221da177e4SLinus Torvalds * It's actually the same long division you learned in school, except that 2231da177e4SLinus Torvalds * - We're working in binary, so the digits are only 0 and 1, and 2241da177e4SLinus Torvalds * - When dividing polynomials, there are no carries. Rather than add and 2251da177e4SLinus Torvalds * subtract, we just xor. Thus, we tend to get a bit sloppy about 2261da177e4SLinus Torvalds * the difference between adding and subtracting. 2271da177e4SLinus Torvalds * 2281da177e4SLinus Torvalds * A 32-bit CRC polynomial is actually 33 bits long. But since it's 2291da177e4SLinus Torvalds * 33 bits long, bit 32 is always going to be set, so usually the CRC 2301da177e4SLinus Torvalds * is written in hex with the most significant bit omitted. (If you're 2311da177e4SLinus Torvalds * familiar with the IEEE 754 floating-point format, it's the same idea.) 2321da177e4SLinus Torvalds * 2331da177e4SLinus Torvalds * Note that a CRC is computed over a string of *bits*, so you have 2341da177e4SLinus Torvalds * to decide on the endianness of the bits within each byte. To get 2351da177e4SLinus Torvalds * the best error-detecting properties, this should correspond to the 2361da177e4SLinus Torvalds * order they're actually sent. For example, standard RS-232 serial is 2371da177e4SLinus Torvalds * little-endian; the most significant bit (sometimes used for parity) 2381da177e4SLinus Torvalds * is sent last. And when appending a CRC word to a message, you should 2391da177e4SLinus Torvalds * do it in the right order, matching the endianness. 2401da177e4SLinus Torvalds * 2411da177e4SLinus Torvalds * Just like with ordinary division, the remainder is always smaller than 2421da177e4SLinus Torvalds * the divisor (the CRC polynomial) you're dividing by. Each step of the 2431da177e4SLinus Torvalds * division, you take one more digit (bit) of the dividend and append it 2441da177e4SLinus Torvalds * to the current remainder. Then you figure out the appropriate multiple 2451da177e4SLinus Torvalds * of the divisor to subtract to being the remainder back into range. 2461da177e4SLinus Torvalds * In binary, it's easy - it has to be either 0 or 1, and to make the 2471da177e4SLinus Torvalds * XOR cancel, it's just a copy of bit 32 of the remainder. 2481da177e4SLinus Torvalds * 2491da177e4SLinus Torvalds * When computing a CRC, we don't care about the quotient, so we can 2501da177e4SLinus Torvalds * throw the quotient bit away, but subtract the appropriate multiple of 2511da177e4SLinus Torvalds * the polynomial from the remainder and we're back to where we started, 2521da177e4SLinus Torvalds * ready to process the next bit. 2531da177e4SLinus Torvalds * 2541da177e4SLinus Torvalds * A big-endian CRC written this way would be coded like: 2551da177e4SLinus Torvalds * for (i = 0; i < input_bits; i++) { 2561da177e4SLinus Torvalds * multiple = remainder & 0x80000000 ? CRCPOLY : 0; 2571da177e4SLinus Torvalds * remainder = (remainder << 1 | next_input_bit()) ^ multiple; 2581da177e4SLinus Torvalds * } 2591da177e4SLinus Torvalds * Notice how, to get at bit 32 of the shifted remainder, we look 2601da177e4SLinus Torvalds * at bit 31 of the remainder *before* shifting it. 2611da177e4SLinus Torvalds * 2621da177e4SLinus Torvalds * But also notice how the next_input_bit() bits we're shifting into 2631da177e4SLinus Torvalds * the remainder don't actually affect any decision-making until 2641da177e4SLinus Torvalds * 32 bits later. Thus, the first 32 cycles of this are pretty boring. 2651da177e4SLinus Torvalds * Also, to add the CRC to a message, we need a 32-bit-long hole for it at 2661da177e4SLinus Torvalds * the end, so we have to add 32 extra cycles shifting in zeros at the 2671da177e4SLinus Torvalds * end of every message, 2681da177e4SLinus Torvalds * 2691da177e4SLinus Torvalds * So the standard trick is to rearrage merging in the next_input_bit() 2701da177e4SLinus Torvalds * until the moment it's needed. Then the first 32 cycles can be precomputed, 2711da177e4SLinus Torvalds * and merging in the final 32 zero bits to make room for the CRC can be 2721da177e4SLinus Torvalds * skipped entirely. 2731da177e4SLinus Torvalds * This changes the code to: 2741da177e4SLinus Torvalds * for (i = 0; i < input_bits; i++) { 2751da177e4SLinus Torvalds * remainder ^= next_input_bit() << 31; 2761da177e4SLinus Torvalds * multiple = (remainder & 0x80000000) ? CRCPOLY : 0; 2771da177e4SLinus Torvalds * remainder = (remainder << 1) ^ multiple; 2781da177e4SLinus Torvalds * } 2791da177e4SLinus Torvalds * With this optimization, the little-endian code is simpler: 2801da177e4SLinus Torvalds * for (i = 0; i < input_bits; i++) { 2811da177e4SLinus Torvalds * remainder ^= next_input_bit(); 2821da177e4SLinus Torvalds * multiple = (remainder & 1) ? CRCPOLY : 0; 2831da177e4SLinus Torvalds * remainder = (remainder >> 1) ^ multiple; 2841da177e4SLinus Torvalds * } 2851da177e4SLinus Torvalds * 2861da177e4SLinus Torvalds * Note that the other details of endianness have been hidden in CRCPOLY 2871da177e4SLinus Torvalds * (which must be bit-reversed) and next_input_bit(). 2881da177e4SLinus Torvalds * 2891da177e4SLinus Torvalds * However, as long as next_input_bit is returning the bits in a sensible 2901da177e4SLinus Torvalds * order, we can actually do the merging 8 or more bits at a time rather 2911da177e4SLinus Torvalds * than one bit at a time: 2921da177e4SLinus Torvalds * for (i = 0; i < input_bytes; i++) { 2931da177e4SLinus Torvalds * remainder ^= next_input_byte() << 24; 2941da177e4SLinus Torvalds * for (j = 0; j < 8; j++) { 2951da177e4SLinus Torvalds * multiple = (remainder & 0x80000000) ? CRCPOLY : 0; 2961da177e4SLinus Torvalds * remainder = (remainder << 1) ^ multiple; 2971da177e4SLinus Torvalds * } 2981da177e4SLinus Torvalds * } 2991da177e4SLinus Torvalds * Or in little-endian: 3001da177e4SLinus Torvalds * for (i = 0; i < input_bytes; i++) { 3011da177e4SLinus Torvalds * remainder ^= next_input_byte(); 3021da177e4SLinus Torvalds * for (j = 0; j < 8; j++) { 3031da177e4SLinus Torvalds * multiple = (remainder & 1) ? CRCPOLY : 0; 3041da177e4SLinus Torvalds * remainder = (remainder << 1) ^ multiple; 3051da177e4SLinus Torvalds * } 3061da177e4SLinus Torvalds * } 3071da177e4SLinus Torvalds * If the input is a multiple of 32 bits, you can even XOR in a 32-bit 3081da177e4SLinus Torvalds * word at a time and increase the inner loop count to 32. 3091da177e4SLinus Torvalds * 3101da177e4SLinus Torvalds * You can also mix and match the two loop styles, for example doing the 3111da177e4SLinus Torvalds * bulk of a message byte-at-a-time and adding bit-at-a-time processing 3121da177e4SLinus Torvalds * for any fractional bytes at the end. 3131da177e4SLinus Torvalds * 3141da177e4SLinus Torvalds * The only remaining optimization is to the byte-at-a-time table method. 3151da177e4SLinus Torvalds * Here, rather than just shifting one bit of the remainder to decide 3161da177e4SLinus Torvalds * in the correct multiple to subtract, we can shift a byte at a time. 3171da177e4SLinus Torvalds * This produces a 40-bit (rather than a 33-bit) intermediate remainder, 3181da177e4SLinus Torvalds * but again the multiple of the polynomial to subtract depends only on 3191da177e4SLinus Torvalds * the high bits, the high 8 bits in this case. 3201da177e4SLinus Torvalds * 321643d1f7fSJoe Perches * The multiple we need in that case is the low 32 bits of a 40-bit 3221da177e4SLinus Torvalds * value whose high 8 bits are given, and which is a multiple of the 3231da177e4SLinus Torvalds * generator polynomial. This is simply the CRC-32 of the given 3241da177e4SLinus Torvalds * one-byte message. 3251da177e4SLinus Torvalds * 3261da177e4SLinus Torvalds * Two more details: normally, appending zero bits to a message which 3271da177e4SLinus Torvalds * is already a multiple of a polynomial produces a larger multiple of that 3281da177e4SLinus Torvalds * polynomial. To enable a CRC to detect this condition, it's common to 3291da177e4SLinus Torvalds * invert the CRC before appending it. This makes the remainder of the 3301da177e4SLinus Torvalds * message+crc come out not as zero, but some fixed non-zero value. 3311da177e4SLinus Torvalds * 3321da177e4SLinus Torvalds * The same problem applies to zero bits prepended to the message, and 3331da177e4SLinus Torvalds * a similar solution is used. Instead of starting with a remainder of 3341da177e4SLinus Torvalds * 0, an initial remainder of all ones is used. As long as you start 3351da177e4SLinus Torvalds * the same way on decoding, it doesn't make a difference. 3361da177e4SLinus Torvalds */ 3371da177e4SLinus Torvalds 3381da177e4SLinus Torvalds #ifdef UNITTEST 3391da177e4SLinus Torvalds 3401da177e4SLinus Torvalds #include <stdlib.h> 3411da177e4SLinus Torvalds #include <stdio.h> 3421da177e4SLinus Torvalds 3431da177e4SLinus Torvalds #if 0 /*Not used at present */ 3441da177e4SLinus Torvalds static void 3451da177e4SLinus Torvalds buf_dump(char const *prefix, unsigned char const *buf, size_t len) 3461da177e4SLinus Torvalds { 3471da177e4SLinus Torvalds fputs(prefix, stdout); 3481da177e4SLinus Torvalds while (len--) 3491da177e4SLinus Torvalds printf(" %02x", *buf++); 3501da177e4SLinus Torvalds putchar('\n'); 3511da177e4SLinus Torvalds 3521da177e4SLinus Torvalds } 3531da177e4SLinus Torvalds #endif 3541da177e4SLinus Torvalds 3551da177e4SLinus Torvalds static void bytereverse(unsigned char *buf, size_t len) 3561da177e4SLinus Torvalds { 3571da177e4SLinus Torvalds while (len--) { 358906d66dfSAkinobu Mita unsigned char x = bitrev8(*buf); 3591da177e4SLinus Torvalds *buf++ = x; 3601da177e4SLinus Torvalds } 3611da177e4SLinus Torvalds } 3621da177e4SLinus Torvalds 3631da177e4SLinus Torvalds static void random_garbage(unsigned char *buf, size_t len) 3641da177e4SLinus Torvalds { 3651da177e4SLinus Torvalds while (len--) 3661da177e4SLinus Torvalds *buf++ = (unsigned char) random(); 3671da177e4SLinus Torvalds } 3681da177e4SLinus Torvalds 3691da177e4SLinus Torvalds #if 0 /* Not used at present */ 3701da177e4SLinus Torvalds static void store_le(u32 x, unsigned char *buf) 3711da177e4SLinus Torvalds { 3721da177e4SLinus Torvalds buf[0] = (unsigned char) x; 3731da177e4SLinus Torvalds buf[1] = (unsigned char) (x >> 8); 3741da177e4SLinus Torvalds buf[2] = (unsigned char) (x >> 16); 3751da177e4SLinus Torvalds buf[3] = (unsigned char) (x >> 24); 3761da177e4SLinus Torvalds } 3771da177e4SLinus Torvalds #endif 3781da177e4SLinus Torvalds 3791da177e4SLinus Torvalds static void store_be(u32 x, unsigned char *buf) 3801da177e4SLinus Torvalds { 3811da177e4SLinus Torvalds buf[0] = (unsigned char) (x >> 24); 3821da177e4SLinus Torvalds buf[1] = (unsigned char) (x >> 16); 3831da177e4SLinus Torvalds buf[2] = (unsigned char) (x >> 8); 3841da177e4SLinus Torvalds buf[3] = (unsigned char) x; 3851da177e4SLinus Torvalds } 3861da177e4SLinus Torvalds 3871da177e4SLinus Torvalds /* 3881da177e4SLinus Torvalds * This checks that CRC(buf + CRC(buf)) = 0, and that 3891da177e4SLinus Torvalds * CRC commutes with bit-reversal. This has the side effect 3901da177e4SLinus Torvalds * of bytewise bit-reversing the input buffer, and returns 3911da177e4SLinus Torvalds * the CRC of the reversed buffer. 3921da177e4SLinus Torvalds */ 3931da177e4SLinus Torvalds static u32 test_step(u32 init, unsigned char *buf, size_t len) 3941da177e4SLinus Torvalds { 3951da177e4SLinus Torvalds u32 crc1, crc2; 3961da177e4SLinus Torvalds size_t i; 3971da177e4SLinus Torvalds 3981da177e4SLinus Torvalds crc1 = crc32_be(init, buf, len); 3991da177e4SLinus Torvalds store_be(crc1, buf + len); 4001da177e4SLinus Torvalds crc2 = crc32_be(init, buf, len + 4); 4011da177e4SLinus Torvalds if (crc2) 4021da177e4SLinus Torvalds printf("\nCRC cancellation fail: 0x%08x should be 0\n", 4031da177e4SLinus Torvalds crc2); 4041da177e4SLinus Torvalds 4051da177e4SLinus Torvalds for (i = 0; i <= len + 4; i++) { 4061da177e4SLinus Torvalds crc2 = crc32_be(init, buf, i); 4071da177e4SLinus Torvalds crc2 = crc32_be(crc2, buf + i, len + 4 - i); 4081da177e4SLinus Torvalds if (crc2) 4091da177e4SLinus Torvalds printf("\nCRC split fail: 0x%08x\n", crc2); 4101da177e4SLinus Torvalds } 4111da177e4SLinus Torvalds 4121da177e4SLinus Torvalds /* Now swap it around for the other test */ 4131da177e4SLinus Torvalds 4141da177e4SLinus Torvalds bytereverse(buf, len + 4); 415906d66dfSAkinobu Mita init = bitrev32(init); 416906d66dfSAkinobu Mita crc2 = bitrev32(crc1); 417906d66dfSAkinobu Mita if (crc1 != bitrev32(crc2)) 418cfc646faSDominik Hackl printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n", 419906d66dfSAkinobu Mita crc1, crc2, bitrev32(crc2)); 4201da177e4SLinus Torvalds crc1 = crc32_le(init, buf, len); 4211da177e4SLinus Torvalds if (crc1 != crc2) 4221da177e4SLinus Torvalds printf("\nCRC endianness fail: 0x%08x != 0x%08x\n", crc1, 4231da177e4SLinus Torvalds crc2); 4241da177e4SLinus Torvalds crc2 = crc32_le(init, buf, len + 4); 4251da177e4SLinus Torvalds if (crc2) 4261da177e4SLinus Torvalds printf("\nCRC cancellation fail: 0x%08x should be 0\n", 4271da177e4SLinus Torvalds crc2); 4281da177e4SLinus Torvalds 4291da177e4SLinus Torvalds for (i = 0; i <= len + 4; i++) { 4301da177e4SLinus Torvalds crc2 = crc32_le(init, buf, i); 4311da177e4SLinus Torvalds crc2 = crc32_le(crc2, buf + i, len + 4 - i); 4321da177e4SLinus Torvalds if (crc2) 4331da177e4SLinus Torvalds printf("\nCRC split fail: 0x%08x\n", crc2); 4341da177e4SLinus Torvalds } 4351da177e4SLinus Torvalds 4361da177e4SLinus Torvalds return crc1; 4371da177e4SLinus Torvalds } 4381da177e4SLinus Torvalds 4391da177e4SLinus Torvalds #define SIZE 64 4401da177e4SLinus Torvalds #define INIT1 0 4411da177e4SLinus Torvalds #define INIT2 0 4421da177e4SLinus Torvalds 4431da177e4SLinus Torvalds int main(void) 4441da177e4SLinus Torvalds { 4451da177e4SLinus Torvalds unsigned char buf1[SIZE + 4]; 4461da177e4SLinus Torvalds unsigned char buf2[SIZE + 4]; 4471da177e4SLinus Torvalds unsigned char buf3[SIZE + 4]; 4481da177e4SLinus Torvalds int i, j; 4491da177e4SLinus Torvalds u32 crc1, crc2, crc3; 4501da177e4SLinus Torvalds 4511da177e4SLinus Torvalds for (i = 0; i <= SIZE; i++) { 4521da177e4SLinus Torvalds printf("\rTesting length %d...", i); 4531da177e4SLinus Torvalds fflush(stdout); 4541da177e4SLinus Torvalds random_garbage(buf1, i); 4551da177e4SLinus Torvalds random_garbage(buf2, i); 4561da177e4SLinus Torvalds for (j = 0; j < i; j++) 4571da177e4SLinus Torvalds buf3[j] = buf1[j] ^ buf2[j]; 4581da177e4SLinus Torvalds 4591da177e4SLinus Torvalds crc1 = test_step(INIT1, buf1, i); 4601da177e4SLinus Torvalds crc2 = test_step(INIT2, buf2, i); 4611da177e4SLinus Torvalds /* Now check that CRC(buf1 ^ buf2) = CRC(buf1) ^ CRC(buf2) */ 4621da177e4SLinus Torvalds crc3 = test_step(INIT1 ^ INIT2, buf3, i); 4631da177e4SLinus Torvalds if (crc3 != (crc1 ^ crc2)) 4641da177e4SLinus Torvalds printf("CRC XOR fail: 0x%08x != 0x%08x ^ 0x%08x\n", 4651da177e4SLinus Torvalds crc3, crc1, crc2); 4661da177e4SLinus Torvalds } 4671da177e4SLinus Torvalds printf("\nAll test complete. No failures expected.\n"); 4681da177e4SLinus Torvalds return 0; 4691da177e4SLinus Torvalds } 4701da177e4SLinus Torvalds 4711da177e4SLinus Torvalds #endif /* UNITTEST */ 472