home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / hashing / Honeyman.cpp < prev    next >
C/C++ Source or Header  |  2005-11-14  |  4KB  |  117 lines
  1.  
  2. #include "../precompiled.h"
  3. #pragma hdrstop
  4.  
  5. #define HONEYMAN_INIT_VALUE        0x00000000L
  6. #define HONEYMAN_XOR_VALUE        0x00000000L
  7.  
  8. #ifdef CREATE_CRC_TABLE
  9.  
  10. static unsigned long crctable[256];
  11.  
  12. /*
  13.     Create the CRC table for the simplified version of the pathalias hashing function.
  14.     Thanks to Steve Belovin and Peter Honeyman
  15.  
  16.     This fast table calculation works only if POLY is a prime polynomial
  17.     in the field of integers modulo 2.  Since the coefficients of a
  18.     32-bit polynomial won't fit in a 32-bit word, the high-order bit is
  19.     implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
  20.     31 down to 25 are zero.  Happily, we have candidates, from
  21.     E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
  22.     x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
  23.     x^31 + x^3 + x^0
  24.  
  25.     We reverse the bits to get:
  26.     111101010000000000000000000000001 but drop the last 1
  27.         f   5   0   0   0   0   0   0
  28.     010010000000000000000000000000001 ditto, for 31-bit crc
  29.         4   8   0   0   0   0   0   0
  30. */
  31.  
  32. void make_crc_table( void ) {
  33.  
  34.     #define POLY 0x48000000L    /* 31-bit polynomial (avoids sign problems) */
  35.  
  36.     for ( int i = 0; i < 128; i++ ) {
  37.         int sum = 0;
  38.         for ( int j = 7 - 1; j >= 0; --j ) {
  39.             if ( i & ( 1 << j ) ) {
  40.                 sum ^= POLY >> j;
  41.             }
  42.         }
  43.         crctable[i] = sum;
  44.     }
  45. }
  46.  
  47. #else
  48.  
  49. static unsigned long crctable[256] = {
  50.     0x00000000L, 0x48000000L, 0x24000000L, 0x6c000000L,
  51.     0x12000000L, 0x5a000000L, 0x36000000L, 0x7e000000L,
  52.     0x09000000L, 0x41000000L, 0x2d000000L, 0x65000000L,
  53.     0x1b000000L, 0x53000000L, 0x3f000000L, 0x77000000L,
  54.     0x04800000L, 0x4c800000L, 0x20800000L, 0x68800000L,
  55.     0x16800000L, 0x5e800000L, 0x32800000L, 0x7a800000L,
  56.     0x0d800000L, 0x45800000L, 0x29800000L, 0x61800000L,
  57.     0x1f800000L, 0x57800000L, 0x3b800000L, 0x73800000L,
  58.     0x02400000L, 0x4a400000L, 0x26400000L, 0x6e400000L,
  59.     0x10400000L, 0x58400000L, 0x34400000L, 0x7c400000L,
  60.     0x0b400000L, 0x43400000L, 0x2f400000L, 0x67400000L,
  61.     0x19400000L, 0x51400000L, 0x3d400000L, 0x75400000L,
  62.     0x06c00000L, 0x4ec00000L, 0x22c00000L, 0x6ac00000L,
  63.     0x14c00000L, 0x5cc00000L, 0x30c00000L, 0x78c00000L,
  64.     0x0fc00000L, 0x47c00000L, 0x2bc00000L, 0x63c00000L,
  65.     0x1dc00000L, 0x55c00000L, 0x39c00000L, 0x71c00000L,
  66.     0x01200000L, 0x49200000L, 0x25200000L, 0x6d200000L,
  67.     0x13200000L, 0x5b200000L, 0x37200000L, 0x7f200000L,
  68.     0x08200000L, 0x40200000L, 0x2c200000L, 0x64200000L,
  69.     0x1a200000L, 0x52200000L, 0x3e200000L, 0x76200000L,
  70.     0x05a00000L, 0x4da00000L, 0x21a00000L, 0x69a00000L,
  71.     0x17a00000L, 0x5fa00000L, 0x33a00000L, 0x7ba00000L,
  72.     0x0ca00000L, 0x44a00000L, 0x28a00000L, 0x60a00000L,
  73.     0x1ea00000L, 0x56a00000L, 0x3aa00000L, 0x72a00000L,
  74.     0x03600000L, 0x4b600000L, 0x27600000L, 0x6f600000L,
  75.     0x11600000L, 0x59600000L, 0x35600000L, 0x7d600000L,
  76.     0x0a600000L, 0x42600000L, 0x2e600000L, 0x66600000L,
  77.     0x18600000L, 0x50600000L, 0x3c600000L, 0x74600000L,
  78.     0x07e00000L, 0x4fe00000L, 0x23e00000L, 0x6be00000L,
  79.     0x15e00000L, 0x5de00000L, 0x31e00000L, 0x79e00000L,
  80.     0x0ee00000L, 0x46e00000L, 0x2ae00000L, 0x62e00000L,
  81.     0x1ce00000L, 0x54e00000L, 0x38e00000L, 0x70e00000L
  82. };
  83.  
  84. #endif
  85.  
  86. void Honeyman_InitChecksum( unsigned long &crcvalue ) {
  87.     crcvalue = HONEYMAN_INIT_VALUE;
  88. }
  89.  
  90. void Honeyman_Update( unsigned long &crcvalue, const byte data ) {
  91.     crcvalue = ( ( crcvalue >> 7 ) ^ crctable[ ( crcvalue ^ data ) & 0x7f ] );
  92. }
  93.  
  94. void Honeyman_UpdateChecksum( unsigned long &crcvalue, const void *data, int length ) {
  95.     unsigned long crc;
  96.     const unsigned char *buf = (const unsigned char *) data;
  97.  
  98.     crc = crcvalue;
  99.     while( length-- ) {
  100.         crc = ( ( crc >> 7 ) ^ crctable[ ( crc ^ *buf++ ) & 0x7f ] );
  101.     }
  102.     crcvalue = crc;
  103. }
  104.  
  105. void Honeyman_FinishChecksum( unsigned long &crcvalue ) {
  106.     crcvalue ^= HONEYMAN_XOR_VALUE;
  107. }
  108.  
  109. unsigned long Honeyman_BlockChecksum( const void *data, int length ) {
  110.     unsigned long crc;
  111.  
  112.     Honeyman_InitChecksum( crc );
  113.     Honeyman_UpdateChecksum( crc, data, length );
  114.     Honeyman_FinishChecksum( crc );
  115.     return crc;
  116. }
  117.