1219351Spjd/*- 2219351Spjd * COPYRIGHT (C) 1986 Gary S. Brown. You may use this program, or 3219351Spjd * code or tables extracted from it, as desired without restriction. 4219351Spjd */ 5219351Spjd 6219351Spjd/* 7219351Spjd * First, the polynomial itself and its table of feedback terms. The 8219351Spjd * polynomial is 9219351Spjd * 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 10219351Spjd * 11219351Spjd * Note that we take it "backwards" and put the highest-order term in 12219351Spjd * the lowest-order bit. The X^32 term is "implied"; the LSB is the 13219351Spjd * X^31 term, etc. The X^0 term (usually shown as "+1") results in 14219351Spjd * the MSB being 1 15219351Spjd * 16219351Spjd * Note that the usual hardware shift register implementation, which 17219351Spjd * is what we're using (we're merely optimizing it by doing eight-bit 18219351Spjd * chunks at a time) shifts bits into the lowest-order term. In our 19219351Spjd * implementation, that means shifting towards the right. Why do we 20219351Spjd * do it this way? Because the calculated CRC must be transmitted in 21219351Spjd * order from highest-order term to lowest-order term. UARTs transmit 22219351Spjd * characters in order from LSB to MSB. By storing the CRC this way 23219351Spjd * we hand it to the UART in the order low-byte to high-byte; the UART 24219351Spjd * sends each low-bit to hight-bit; and the result is transmission bit 25219351Spjd * by bit from highest- to lowest-order term without requiring any bit 26219351Spjd * shuffling on our part. Reception works similarly 27219351Spjd * 28219351Spjd * The feedback terms table consists of 256, 32-bit entries. Notes 29219351Spjd * 30219351Spjd * The table can be generated at runtime if desired; code to do so 31219351Spjd * is shown later. It might not be obvious, but the feedback 32219351Spjd * terms simply represent the results of eight shift/xor opera 33219351Spjd * tions for all combinations of data and CRC register values 34219351Spjd * 35219351Spjd * The values must be right-shifted by eight bits by the "updcrc 36219351Spjd * logic; the shift must be unsigned (bring in zeroes). On some 37219351Spjd * hardware you could probably optimize the shift in assembler by 38219351Spjd * using byte-swap instructions 39219351Spjd * polynomial $edb88320 40219351Spjd * 41219351Spjd * 42219351Spjd * CRC32 code derived from work by Gary S. Brown. 43219351Spjd */ 44219351Spjd 45219351Spjd#include <sys/cdefs.h> 46219351Spjd__FBSDID("$FreeBSD$"); 47219351Spjd 48219351Spjd#include <stdint.h> 49219351Spjd 50219351Spjd#include <crc32.h> 51219351Spjd 52219351Spjduint32_t crc32_tab[] = { 53219351Spjd 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 54219351Spjd 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 55219351Spjd 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, 56219351Spjd 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 57219351Spjd 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 58219351Spjd 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 59219351Spjd 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 60219351Spjd 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 61219351Spjd 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 62219351Spjd 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 63219351Spjd 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, 64219351Spjd 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 65219351Spjd 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 66219351Spjd 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 67219351Spjd 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 68219351Spjd 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 69219351Spjd 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 70219351Spjd 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 71219351Spjd 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 72219351Spjd 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 73219351Spjd 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 74219351Spjd 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 75219351Spjd 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 76219351Spjd 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 77219351Spjd 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 78219351Spjd 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 79219351Spjd 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, 80219351Spjd 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 81219351Spjd 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 82219351Spjd 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 83219351Spjd 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 84219351Spjd 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 85219351Spjd 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 86219351Spjd 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 87219351Spjd 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 88219351Spjd 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 89219351Spjd 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 90219351Spjd 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 91219351Spjd 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 92219351Spjd 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 93219351Spjd 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 94219351Spjd 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 95219351Spjd 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d 96219351Spjd}; 97219351Spjd 98219351Spjd/* 99219351Spjd * A function that calculates the CRC-32 based on the table above is 100219351Spjd * given below for documentation purposes. An equivalent implementation 101219351Spjd * of this function that's actually used in the kernel can be found 102219351Spjd * in sys/libkern.h, where it can be inlined. 103219351Spjd * 104219351Spjd * uint32_t 105219351Spjd * crc32(const void *buf, size_t size) 106219351Spjd * { 107219351Spjd * const uint8_t *p = buf; 108219351Spjd * uint32_t crc; 109219351Spjd * 110219351Spjd * crc = ~0U; 111219351Spjd * while (size--) 112219351Spjd * crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8); 113219351Spjd * return crc ^ ~0U; 114219351Spjd * } 115219351Spjd */ 116