18b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen/*- 28b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * COPYRIGHT (C) 1986 Gary S. Brown. You may use this program, or 38b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * code or tables extracted from it, as desired without restriction. 48b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen */ 58b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 68b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen/* 78b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * First, the polynomial itself and its table of feedback terms. The 88b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * polynomial is 98b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * 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 108b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * 118b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * Note that we take it "backwards" and put the highest-order term in 128b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * the lowest-order bit. The X^32 term is "implied"; the LSB is the 138b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * X^31 term, etc. The X^0 term (usually shown as "+1") results in 148b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * the MSB being 1 158b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * 168b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * Note that the usual hardware shift register implementation, which 178b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * is what we're using (we're merely optimizing it by doing eight-bit 188b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * chunks at a time) shifts bits into the lowest-order term. In our 198b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * implementation, that means shifting towards the right. Why do we 208b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * do it this way? Because the calculated CRC must be transmitted in 218b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * order from highest-order term to lowest-order term. UARTs transmit 228b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * characters in order from LSB to MSB. By storing the CRC this way 238b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * we hand it to the UART in the order low-byte to high-byte; the UART 248b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * sends each low-bit to hight-bit; and the result is transmission bit 258b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * by bit from highest- to lowest-order term without requiring any bit 268b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * shuffling on our part. Reception works similarly 278b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * 288b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * The feedback terms table consists of 256, 32-bit entries. Notes 298b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * 308b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * The table can be generated at runtime if desired; code to do so 318b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * is shown later. It might not be obvious, but the feedback 328b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * terms simply represent the results of eight shift/xor opera 338b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * tions for all combinations of data and CRC register values 348b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * 358b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * The values must be right-shifted by eight bits by the "updcrc 368b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * logic; the shift must be unsigned (bring in zeroes). On some 378b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * hardware you could probably optimize the shift in assembler by 388b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * using byte-swap instructions 398b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * polynomial $edb88320 408b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * 418b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * 428b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * CRC32 code derived from work by Gary S. Brown. 438b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen */ 448b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 458b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen#include "avb_sysdeps.h" 46047ecf7d2361ffcb39a5a4ec0709480f47ed76e2David Zeuthen#include "avb_util.h" 478b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 488b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen/* Code taken from FreeBSD 8 */ 498b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 50047ecf7d2361ffcb39a5a4ec0709480f47ed76e2David Zeuthenstatic uint32_t iavb_crc32_tab[] = { 518b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 528b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 538b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, 548b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 558b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 568b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 578b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 588b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 598b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 608b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 618b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, 628b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 638b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 648b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 658b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 668b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 678b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 688b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 698b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 708b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 718b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 728b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 738b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 748b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 758b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 768b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 778b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, 788b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 798b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 808b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 818b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 828b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 838b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 848b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 858b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 868b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 878b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 888b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 898b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 908b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 918b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 928b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 938b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d}; 948b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 958b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen/* 968b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * A function that calculates the CRC-32 based on the table above is 978b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * given below for documentation purposes. An equivalent implementation 988b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * of this function that's actually used in the kernel can be found 998b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen * in sys/libkern.h, where it can be inlined. 1008b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen */ 1018b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 102047ecf7d2361ffcb39a5a4ec0709480f47ed76e2David Zeuthenstatic uint32_t iavb_crc32(uint32_t crc_in, const uint8_t* buf, int size) { 1038b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen const uint8_t* p = buf; 1048b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen uint32_t crc; 1058b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 1068b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen crc = crc_in ^ ~0U; 1074b6a634e48353da1e119ebe0287299f7b919d778David Zeuthen while (size--) 108047ecf7d2361ffcb39a5a4ec0709480f47ed76e2David Zeuthen crc = iavb_crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8); 1098b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen return crc ^ ~0U; 1108b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen} 1118b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen 1128b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthenuint32_t avb_crc32(const uint8_t* buf, size_t size) { 113047ecf7d2361ffcb39a5a4ec0709480f47ed76e2David Zeuthen return iavb_crc32(0, buf, size); 1148b6973be7468f5c0db42ff8fcd91f8e97a345a27David Zeuthen} 115