128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/*- 228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * COPYRIGHT (C) 1986 Gary S. Brown. You may use this program, or 328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * code or tables extracted from it, as desired without restriction. 428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross */ 528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* 728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * First, the polynomial itself and its table of feedback terms. The 828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * polynomial is 928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * 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 1028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * 1128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * Note that we take it "backwards" and put the highest-order term in 1228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * the lowest-order bit. The X^32 term is "implied"; the LSB is the 1328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * X^31 term, etc. The X^0 term (usually shown as "+1") results in 1428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * the MSB being 1 1528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * 1628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * Note that the usual hardware shift register implementation, which 1728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * is what we're using (we're merely optimizing it by doing eight-bit 1828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * chunks at a time) shifts bits into the lowest-order term. In our 1928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * implementation, that means shifting towards the right. Why do we 2028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * do it this way? Because the calculated CRC must be transmitted in 2128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * order from highest-order term to lowest-order term. UARTs transmit 2228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * characters in order from LSB to MSB. By storing the CRC this way 2328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * we hand it to the UART in the order low-byte to high-byte; the UART 2428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * sends each low-bit to hight-bit; and the result is transmission bit 2528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * by bit from highest- to lowest-order term without requiring any bit 2628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * shuffling on our part. Reception works similarly 2728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * 2828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * The feedback terms table consists of 256, 32-bit entries. Notes 2928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * 3028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * The table can be generated at runtime if desired; code to do so 3128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * is shown later. It might not be obvious, but the feedback 3228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * terms simply represent the results of eight shift/xor opera 3328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * tions for all combinations of data and CRC register values 3428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * 3528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * The values must be right-shifted by eight bits by the "updcrc 3628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * logic; the shift must be unsigned (bring in zeroes). On some 3728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * hardware you could probably optimize the shift in assembler by 3828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * using byte-swap instructions 3928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * polynomial $edb88320 4028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * 4128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * 4228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * CRC32 code derived from work by Gary S. Brown. 4328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross */ 4428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 4528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* Code taken from FreeBSD 8 */ 4628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross#include <stdint.h> 4728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 4828fa5bc347390480fe190294c6c385b6a9f0d68bColin Crossstatic uint32_t crc32_tab[] = { 4928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 5028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 5128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, 5228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 5328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 5428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 5528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 5628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 5728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 5828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 5928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, 6028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 6128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 6228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 6328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 6428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 6528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 6628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 6728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 6828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 6928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 7028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 7128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 7228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 7328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 7428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 7528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, 7628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 7728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 7828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 7928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 8028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 8128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 8228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 8328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 8428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 8528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 8628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 8728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 8828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 8928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 9028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 9128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d 9228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross}; 9328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 9428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* 9528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * A function that calculates the CRC-32 based on the table above is 9628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * given below for documentation purposes. An equivalent implementation 9728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * of this function that's actually used in the kernel can be found 9828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * in sys/libkern.h, where it can be inlined. 9928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross */ 10028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 10128fa5bc347390480fe190294c6c385b6a9f0d68bColin Crossuint32_t sparse_crc32(uint32_t crc_in, const void *buf, int size) 10228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 10328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross const uint8_t *p = buf; 10428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross uint32_t crc; 10528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 10628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross crc = crc_in ^ ~0U; 10728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross while (size--) 10828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8); 10928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross return crc ^ ~0U; 11028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 11128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 112