1 /*- 2 * COPYRIGHT (C) 1986 Gary S. Brown. You may use this program, or 3 * code or tables extracted from it, as desired without restriction. 4 * 5 * First, the polynomial itself and its table of feedback terms. The 6 * polynomial is 7 * X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0 8 * 9 * Note that we take it "backwards" and put the highest-order term in 10 * the lowest-order bit. The X^32 term is "implied"; the LSB is the 11 * X^31 term, etc. The X^0 term (usually shown as "+1") results in 12 * the MSB being 1 13 * 14 * Note that the usual hardware shift register implementation, which 15 * is what we're using (we're merely optimizing it by doing eight-bit 16 * chunks at a time) shifts bits into the lowest-order term. In our 17 * implementation, that means shifting towards the right. Why do we 18 * do it this way? Because the calculated CRC must be transmitted in 19 * order from highest-order term to lowest-order term. UARTs transmit 20 * characters in order from LSB to MSB. By storing the CRC this way 21 * we hand it to the UART in the order low-byte to high-byte; the UART 22 * sends each low-bit to hight-bit; and the result is transmission bit 23 * by bit from highest- to lowest-order term without requiring any bit 24 * shuffling on our part. Reception works similarly 25 * 26 * The feedback terms table consists of 256, 32-bit entries. Notes 27 * 28 * The table can be generated at runtime if desired; code to do so 29 * is shown later. It might not be obvious, but the feedback 30 * terms simply represent the results of eight shift/xor opera 31 * tions for all combinations of data and CRC register values 32 * 33 * The values must be right-shifted by eight bits by the "updcrc 34 * logic; the shift must be unsigned (bring in zeroes). On some 35 * hardware you could probably optimize the shift in assembler by 36 * using byte-swap instructions 37 * polynomial $edb88320 38 * 39 * CRC32 code derived from work by Gary S. Brown. 40 * 41 * $FreeBSD: src/sys/libkern/crc32.c,v 1.1.2.1 2002/07/31 09:08:34 imp Exp $ 42 * $DragonFly: src/sys/libkern/crc32.c,v 1.7 2008/11/03 08:41:31 swildner Exp $ 43 */ 44 45 /* 46 * WARNING: This code is used by various subsystems including the HAMMER 47 * filesystem. This code may be directly compiled in userland or kernel 48 * builds. 49 */ 50 51 #ifdef _KERNEL 52 #include <sys/param.h> 53 #include <sys/systm.h> 54 #else 55 #include <sys/types.h> 56 #endif 57 58 #ifndef _KERNEL 59 /* prototypes for the kernel are in <sys/systm.h> */ 60 extern const uint32_t crc32_tab[]; 61 uint32_t crc32(const void *buf, size_t size); 62 uint32_t crc32_ext(const void *buf, size_t size, uint32_t ocrc); 63 #endif 64 65 #if 0 66 /* see icrc32.c */ 67 const uint32_t crc32_tab[] = { 68 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 69 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 70 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, 71 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 72 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 73 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 74 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 75 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 76 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 77 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 78 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, 79 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 80 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 81 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 82 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 83 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 84 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 85 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 86 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 87 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 88 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 89 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 90 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 91 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 92 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 93 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 94 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, 95 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 96 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 97 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 98 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 99 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 100 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 101 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 102 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 103 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 104 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 105 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 106 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 107 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 108 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 109 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 110 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d 111 }; 112 #endif 113 114 uint32_t 115 crc32(const void *buf, size_t size) 116 { 117 const uint8_t *p; 118 uint32_t crc; 119 120 p = buf; 121 crc = ~0U; 122 123 while (size--) 124 crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8); 125 126 return crc ^ ~0U; 127 } 128 129 uint32_t 130 crc32_ext(const void *buf, size_t size, uint32_t ocrc) 131 { 132 const uint8_t *p; 133 uint32_t crc; 134 135 p = buf; 136 crc = ~ocrc; 137 138 while (size--) 139 crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8); 140 141 return crc ^ ~0U; 142 } 143 144