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