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 uint32_t crc32(const void *buf, size_t size); 61 uint32_t crc32_ext(const void *buf, size_t size, uint32_t ocrc); 62 #endif 63 64 uint32_t crc32_tab[] = { 65 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 66 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 67 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, 68 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 69 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 70 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 71 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 72 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 73 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 74 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 75 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, 76 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 77 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 78 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 79 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 80 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 81 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 82 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 83 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 84 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 85 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 86 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 87 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 88 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 89 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 90 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 91 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, 92 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 93 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 94 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 95 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 96 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 97 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 98 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 99 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 100 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 101 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 102 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 103 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 104 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 105 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 106 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 107 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d 108 }; 109 110 uint32_t 111 crc32(const void *buf, size_t size) 112 { 113 const uint8_t *p; 114 uint32_t crc; 115 116 p = buf; 117 crc = ~0U; 118 119 while (size--) 120 crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8); 121 122 return crc ^ ~0U; 123 } 124 125 uint32_t 126 crc32_ext(const void *buf, size_t size, uint32_t ocrc) 127 { 128 const uint8_t *p; 129 uint32_t crc; 130 131 p = buf; 132 crc = ~ocrc; 133 134 while (size--) 135 crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8); 136 137 return crc ^ ~0U; 138 } 139 140