neo/idlib/hashing/CRC32.cpp

   1
   2 #include "../precompiled.h"
   3 #pragma hdrstop
   4
   5 /*
   6    CRC-32
   7    Copyright (C) 1995-1998 Mark Adler
   8 */
   9
  10 #define CRC32_INIT_VALUE        0xffffffffL
  11 #define CRC32_XOR_VALUE         0xffffffffL
  12
  13 #ifdef CREATE_CRC_TABLE
  14
  15 static unsigned long crctable[256];
  16
  17 /*
  18    Generate a table for a byte-wise 32-bit CRC calculation on the polynomial:
  19    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.
  20
  21    Polynomials over GF(2) are represented in binary, one bit per coefficient,
  22    with the lowest powers in the most significant bit.  Then adding polynomials
  23    is just exclusive-or, and multiplying a polynomial by x is a right shift by
  24    one.  If we call the above polynomial p, and represent a byte as the
  25    polynomial q, also with the lowest power in the most significant bit (so the
  26    byte 0xb1 is the polynomial x^7+x^3+x^1+x^0), then the CRC is (q*x^32) mod p,
  27    where a mod b means the remainder after dividing a by b.
  28
  29    This calculation is done using the shift-register method of multiplying and
  30    taking the remainder.  The register is initialized to zero, and for each
  31    incoming bit, x^32 is added mod p to the register if the bit is a one (where
  32    x^32 mod p is p+x^32 = x^26+...+x^0), and the register is multiplied mod p by
  33    x (which is shifting right by one and adding x^32 mod p if the bit shifted
  34    out is a one).  We start with the highest power (least significant bit) of
  35    q and repeat for all eight bits of q.
  36
  37    The table is simply the CRC of all possible eight bit values. This is all
  38    the information needed to generate CRC's on data a byte at a time for all
  39    combinations of CRC register values and incoming bytes.
  40 */
  41
  42 void make_crc_table( void ) {
  43         int i, j;
  44         unsigned long c, poly;
  45         /* terms of polynomial defining this crc (except x^32): */
  46         static const byte p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
  47
  48         /* make exclusive-or pattern from polynomial (0xedb88320L) */
  49         poly = 0L;
  50         for ( i = 0; i < sizeof( p ) / sizeof( byte ); i++ ) {
  51                 poly |= 1L << ( 31 - p[i] );
  52         }
  53
  54         for ( i = 0; i < 256; i++ ) {
  55                 c = (unsigned long)i;
  56                 for ( j = 0; j < 8; j++ ) {
  57                         c = ( c & 1 ) ? poly ^ ( c >> 1 ) : ( c >> 1 );
  58                 }
  59                 crctable[i] = c;
  60         }
  61 }
  62
  63 #else
  64
  65 /*
  66   Table of CRC-32's of all single-byte values (made by make_crc_table)
  67 */
  68 static unsigned long crctable[256] = {
  69         0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL,
  70         0x076dc419L, 0x706af48fL, 0xe963a535L, 0x9e6495a3L,
  71         0x0edb8832L, 0x79dcb8a4L, 0xe0d5e91eL, 0x97d2d988L,
  72         0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L, 0x90bf1d91L,
  73         0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
  74         0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L,
  75         0x136c9856L, 0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL,
  76         0x14015c4fL, 0x63066cd9L, 0xfa0f3d63L, 0x8d080df5L,
  77         0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L, 0xa2677172L,
  78         0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
  79         0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L,
  80         0x32d86ce3L, 0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L,
  81         0x26d930acL, 0x51de003aL, 0xc8d75180L, 0xbfd06116L,
  82         0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L, 0xb8bda50fL,
  83         0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
  84         0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL,
  85         0x76dc4190L, 0x01db7106L, 0x98d220bcL, 0xefd5102aL,
  86         0x71b18589L, 0x06b6b51fL, 0x9fbfe4a5L, 0xe8b8d433L,
  87         0x7807c9a2L, 0x0f00f934L, 0x9609a88eL, 0xe10e9818L,
  88         0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
  89         0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL,
  90         0x6c0695edL, 0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L,
  91         0x65b0d9c6L, 0x12b7e950L, 0x8bbeb8eaL, 0xfcb9887cL,
  92         0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L, 0xfbd44c65L,
  93         0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
  94         0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL,
  95         0x4369e96aL, 0x346ed9fcL, 0xad678846L, 0xda60b8d0L,
  96         0x44042d73L, 0x33031de5L, 0xaa0a4c5fL, 0xdd0d7cc9L,
  97         0x5005713cL, 0x270241aaL, 0xbe0b1010L, 0xc90c2086L,
  98         0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
  99         0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L,
 100         0x59b33d17L, 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL,
 101         0xedb88320L, 0x9abfb3b6L, 0x03b6e20cL, 0x74b1d29aL,
 102         0xead54739L, 0x9dd277afL, 0x04db2615L, 0x73dc1683L,
 103         0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
 104         0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L,
 105         0xf00f9344L, 0x8708a3d2L, 0x1e01f268L, 0x6906c2feL,
 106         0xf762575dL, 0x806567cbL, 0x196c3671L, 0x6e6b06e7L,
 107         0xfed41b76L, 0x89d32be0L, 0x10da7a5aL, 0x67dd4accL,
 108         0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
 109         0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L,
 110         0xd1bb67f1L, 0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL,
 111         0xd80d2bdaL, 0xaf0a1b4cL, 0x36034af6L, 0x41047a60L,
 112         0xdf60efc3L, 0xa867df55L, 0x316e8eefL, 0x4669be79L,
 113         0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
 114         0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL,
 115         0xc5ba3bbeL, 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L,
 116         0xc2d7ffa7L, 0xb5d0cf31L, 0x2cd99e8bL, 0x5bdeae1dL,
 117         0x9b64c2b0L, 0xec63f226L, 0x756aa39cL, 0x026d930aL,
 118         0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
 119         0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L,
 120         0x92d28e9bL, 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L,
 121         0x86d3d2d4L, 0xf1d4e242L, 0x68ddb3f8L, 0x1fda836eL,
 122         0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L, 0x18b74777L,
 123         0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
 124         0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L,
 125         0xa00ae278L, 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L,
 126         0xa7672661L, 0xd06016f7L, 0x4969474dL, 0x3e6e77dbL,
 127         0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L, 0x37d83bf0L,
 128         0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
 129         0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L,
 130         0xbad03605L, 0xcdd70693L, 0x54de5729L, 0x23d967bfL,
 131         0xb3667a2eL, 0xc4614ab8L, 0x5d681b02L, 0x2a6f2b94L,
 132         0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL, 0x2d02ef8dL
 133 };
 134
 135 #endif
 136
 137 void CRC32_InitChecksum( unsigned long &crcvalue ) {
 138         crcvalue = CRC32_INIT_VALUE;
 139 }
 140
 141 void CRC32_Update( unsigned long &crcvalue, const byte data ) {
 142         crcvalue = crctable[ ( crcvalue ^ data ) & 0xff ] ^ ( crcvalue >> 8 );
 143 }
 144
 145 void CRC32_UpdateChecksum( unsigned long &crcvalue, const void *data, int length ) {
 146         unsigned long crc;
 147         const unsigned char *buf = (const unsigned char *) data;
 148
 149         crc = crcvalue;
 150         while( length-- ) {
 151                 crc = crctable[ ( crc ^ ( *buf++ ) ) & 0xff ] ^ ( crc >> 8 );
 152         }
 153         crcvalue = crc;
 154 }
 155
 156 void CRC32_FinishChecksum( unsigned long &crcvalue ) {
 157         crcvalue ^= CRC32_XOR_VALUE;
 158 }
 159
 160 unsigned long CRC32_BlockChecksum( const void *data, int length ) {
 161         unsigned long crc;
 162
 163         CRC32_InitChecksum( crc );
 164         CRC32_UpdateChecksum( crc, data, length );
 165         CRC32_FinishChecksum( crc );
 166         return crc;
 167 }