lib/dvb/crc32.cpp

   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
  40 /* $Id: crc32.cpp,v 1.1 2003-10-17 15:35:50 tmbinc Exp $ */
  41
  42 #include "crc32.h"
  43 #if 0
  44 const uint32_t crc32_table[256] = {
  45         0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
  46         0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
  47         0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
  48         0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
  49         0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
  50         0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
  51         0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
  52         0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
  53         0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
  54         0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
  55         0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
  56         0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
  57         0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
  58         0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
  59         0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
  60         0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
  61         0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
  62         0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
  63         0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
  64         0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
  65         0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
  66         0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
  67         0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
  68         0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
  69         0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
  70         0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
  71         0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
  72         0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
  73         0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
  74         0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
  75         0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
  76         0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
  77         0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
  78         0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
  79         0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
  80         0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
  81         0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
  82         0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
  83         0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
  84         0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
  85         0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
  86         0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
  87         0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
  88         0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
  89         0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
  90         0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
  91         0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
  92         0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
  93         0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
  94         0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
  95         0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
  96         0x2d02ef8dL
  97 };
  98 #else
  99 const uint32_t crc32_table[256] = {
 100         0, 0x4C11DB7, 0x9823B6E, 0xD4326D9,
 101         0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
 102         0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
 103         0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD,
 104         0x4C11DB70, 0x48D0C6C7, 0x4593E01E, 0x4152FDA9,
 105         0x5F15ADAC, 0x5BD4B01B, 0x569796C2, 0x52568B75,
 106         0x6A1936C8, 0x6ED82B7F, 0x639B0DA6, 0x675A1011,
 107         0x791D4014, 0x7DDC5DA3, 0x709F7B7A, 0x745E66CD,
 108         0x9823B6E0, 0x9CE2AB57, 0x91A18D8E, 0x95609039,
 109         0x8B27C03C, 0x8FE6DD8B, 0x82A5FB52, 0x8664E6E5,
 110         0xBE2B5B58, 0xBAEA46EF, 0xB7A96036, 0xB3687D81,
 111         0xAD2F2D84, 0xA9EE3033, 0xA4AD16EA, 0xA06C0B5D,
 112         0xD4326D90, 0xD0F37027, 0xDDB056FE, 0xD9714B49,
 113         0xC7361B4C, 0xC3F706FB, 0xCEB42022, 0xCA753D95,
 114         0xF23A8028, 0xF6FB9D9F, 0xFBB8BB46, 0xFF79A6F1,
 115         0xE13EF6F4, 0xE5FFEB43, 0xE8BCCD9A, 0xEC7DD02D,
 116         0x34867077, 0x30476DC0, 0x3D044B19, 0x39C556AE,
 117         0x278206AB, 0x23431B1C, 0x2E003DC5, 0x2AC12072,
 118         0x128E9DCF, 0x164F8078, 0x1B0CA6A1, 0x1FCDBB16,
 119         0x18AEB13, 0x54BF6A4, 0x808D07D, 0xCC9CDCA,
 120         0x7897AB07, 0x7C56B6B0, 0x71159069, 0x75D48DDE,
 121         0x6B93DDDB, 0x6F52C06C, 0x6211E6B5, 0x66D0FB02,
 122         0x5E9F46BF, 0x5A5E5B08, 0x571D7DD1, 0x53DC6066,
 123         0x4D9B3063, 0x495A2DD4, 0x44190B0D, 0x40D816BA,
 124         0xACA5C697, 0xA864DB20, 0xA527FDF9, 0xA1E6E04E,
 125         0xBFA1B04B, 0xBB60ADFC, 0xB6238B25, 0xB2E29692,
 126         0x8AAD2B2F, 0x8E6C3698, 0x832F1041, 0x87EE0DF6,
 127         0x99A95DF3, 0x9D684044, 0x902B669D, 0x94EA7B2A,
 128         0xE0B41DE7, 0xE4750050, 0xE9362689, 0xEDF73B3E,
 129         0xF3B06B3B, 0xF771768C, 0xFA325055, 0xFEF34DE2,
 130         0xC6BCF05F, 0xC27DEDE8, 0xCF3ECB31, 0xCBFFD686,
 131         0xD5B88683, 0xD1799B34, 0xDC3ABDED, 0xD8FBA05A,
 132         0x690CE0EE, 0x6DCDFD59, 0x608EDB80, 0x644FC637,
 133         0x7A089632, 0x7EC98B85, 0x738AAD5C, 0x774BB0EB,
 134         0x4F040D56, 0x4BC510E1, 0x46863638, 0x42472B8F,
 135         0x5C007B8A, 0x58C1663D, 0x558240E4, 0x51435D53,
 136         0x251D3B9E, 0x21DC2629, 0x2C9F00F0, 0x285E1D47,
 137         0x36194D42, 0x32D850F5, 0x3F9B762C, 0x3B5A6B9B,
 138         0x315D626, 0x7D4CB91, 0xA97ED48, 0xE56F0FF,
 139         0x1011A0FA, 0x14D0BD4D, 0x19939B94, 0x1D528623,
 140         0xF12F560E, 0xF5EE4BB9, 0xF8AD6D60, 0xFC6C70D7,
 141         0xE22B20D2, 0xE6EA3D65, 0xEBA91BBC, 0xEF68060B,
 142         0xD727BBB6, 0xD3E6A601, 0xDEA580D8, 0xDA649D6F,
 143         0xC423CD6A, 0xC0E2D0DD, 0xCDA1F604, 0xC960EBB3,
 144         0xBD3E8D7E, 0xB9FF90C9, 0xB4BCB610, 0xB07DABA7,
 145         0xAE3AFBA2, 0xAAFBE615, 0xA7B8C0CC, 0xA379DD7B,
 146         0x9B3660C6, 0x9FF77D71, 0x92B45BA8, 0x9675461F,
 147         0x8832161A, 0x8CF30BAD, 0x81B02D74, 0x857130C3,
 148         0x5D8A9099, 0x594B8D2E, 0x5408ABF7, 0x50C9B640,
 149         0x4E8EE645, 0x4A4FFBF2, 0x470CDD2B, 0x43CDC09C,
 150         0x7B827D21, 0x7F436096, 0x7200464F, 0x76C15BF8,
 151         0x68860BFD, 0x6C47164A, 0x61043093, 0x65C52D24,
 152         0x119B4BE9, 0x155A565E, 0x18197087, 0x1CD86D30,
 153         0x29F3D35, 0x65E2082, 0xB1D065B, 0xFDC1BEC,
 154         0x3793A651, 0x3352BBE6, 0x3E119D3F, 0x3AD08088,
 155         0x2497D08D, 0x2056CD3A, 0x2D15EBE3, 0x29D4F654,
 156         0xC5A92679, 0xC1683BCE, 0xCC2B1D17, 0xC8EA00A0,
 157         0xD6AD50A5, 0xD26C4D12, 0xDF2F6BCB, 0xDBEE767C,
 158         0xE3A1CBC1, 0xE760D676, 0xEA23F0AF, 0xEEE2ED18,
 159         0xF0A5BD1D, 0xF464A0AA, 0xF9278673, 0xFDE69BC4,
 160         0x89B8FD09, 0x8D79E0BE, 0x803AC667, 0x84FBDBD0,
 161         0x9ABC8BD5, 0x9E7D9662, 0x933EB0BB, 0x97FFAD0C,
 162         0xAFB010B1, 0xAB710D06, 0xA6322BDF, 0xA2F33668,
 163         0xBCB4666D, 0xB8757BDA, 0xB5365D03, 0xB1F740B4};
 164 #endif