crc32.c revision 213136
1213136Spjd/*- 2213136Spjd * COPYRIGHT (C) 1986 Gary S. Brown. You may use this program, or 3213136Spjd * code or tables extracted from it, as desired without restriction. 4213136Spjd */ 5213136Spjd 6213136Spjd/* 7213136Spjd * First, the polynomial itself and its table of feedback terms. The 8213136Spjd * polynomial is 9213136Spjd * 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 10213136Spjd * 11213136Spjd * Note that we take it "backwards" and put the highest-order term in 12213136Spjd * the lowest-order bit. The X^32 term is "implied"; the LSB is the 13213136Spjd * X^31 term, etc. The X^0 term (usually shown as "+1") results in 14213136Spjd * the MSB being 1 15213136Spjd * 16213136Spjd * Note that the usual hardware shift register implementation, which 17213136Spjd * is what we're using (we're merely optimizing it by doing eight-bit 18213136Spjd * chunks at a time) shifts bits into the lowest-order term. In our 19213136Spjd * implementation, that means shifting towards the right. Why do we 20213136Spjd * do it this way? Because the calculated CRC must be transmitted in 21213136Spjd * order from highest-order term to lowest-order term. UARTs transmit 22213136Spjd * characters in order from LSB to MSB. By storing the CRC this way 23213136Spjd * we hand it to the UART in the order low-byte to high-byte; the UART 24213136Spjd * sends each low-bit to hight-bit; and the result is transmission bit 25213136Spjd * by bit from highest- to lowest-order term without requiring any bit 26213136Spjd * shuffling on our part. Reception works similarly 27213136Spjd * 28213136Spjd * The feedback terms table consists of 256, 32-bit entries. Notes 29213136Spjd * 30213136Spjd * The table can be generated at runtime if desired; code to do so 31213136Spjd * is shown later. It might not be obvious, but the feedback 32213136Spjd * terms simply represent the results of eight shift/xor opera 33213136Spjd * tions for all combinations of data and CRC register values 34213136Spjd * 35213136Spjd * The values must be right-shifted by eight bits by the "updcrc 36213136Spjd * logic; the shift must be unsigned (bring in zeroes). On some 37213136Spjd * hardware you could probably optimize the shift in assembler by 38213136Spjd * using byte-swap instructions 39213136Spjd * polynomial $edb88320 40213136Spjd * 41213136Spjd * 42213136Spjd * CRC32 code derived from work by Gary S. Brown. 43213136Spjd */ 44213136Spjd 45213136Spjd#include <sys/cdefs.h> 46213136Spjd__FBSDID("$FreeBSD: head/sys/boot/common/crc32.c 213136 2010-09-24 19:49:12Z pjd $"); 47213136Spjd 48213136Spjd#include <sys/types.h> 49213136Spjd 50213136Spjd#include "crc32.h" 51213136Spjd 52213136Spjdstatic uint32_t crc32_tab[] = { 53213136Spjd 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 54213136Spjd 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 55213136Spjd 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, 56213136Spjd 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 57213136Spjd 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 58213136Spjd 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 59213136Spjd 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 60213136Spjd 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 61213136Spjd 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 62213136Spjd 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 63213136Spjd 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, 64213136Spjd 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 65213136Spjd 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 66213136Spjd 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 67213136Spjd 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 68213136Spjd 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 69213136Spjd 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 70213136Spjd 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 71213136Spjd 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 72213136Spjd 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 73213136Spjd 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 74213136Spjd 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 75213136Spjd 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 76213136Spjd 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 77213136Spjd 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 78213136Spjd 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 79213136Spjd 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, 80213136Spjd 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 81213136Spjd 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 82213136Spjd 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 83213136Spjd 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 84213136Spjd 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 85213136Spjd 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 86213136Spjd 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 87213136Spjd 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 88213136Spjd 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 89213136Spjd 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 90213136Spjd 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 91213136Spjd 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 92213136Spjd 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 93213136Spjd 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 94213136Spjd 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 95213136Spjd 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d 96213136Spjd}; 97213136Spjd 98213136Spjduint32_t 99213136Spjdcrc32(const void *buf, size_t size) 100213136Spjd{ 101213136Spjd const uint8_t *p = buf; 102213136Spjd uint32_t crc; 103213136Spjd 104213136Spjd crc = ~0U; 105213136Spjd while (size--) 106213136Spjd crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8); 107213136Spjd return (crc ^ ~0U); 108213136Spjd} 109