git.m6w6.name Git - m6w6/libmemcached/blob - libhashkit/crc32.cc

   1 /*  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
   2  *
   3  *  HashKit library
   4  *
   5  *  Copyright (C) 2009-2012 Data Differential, http://datadifferential.com/
   6  *
   7  *  Redistribution and use in source and binary forms, with or without
   8  *  modification, are permitted provided that the following conditions are
   9  *  met:
  10  *
  11  *      * Redistributions of source code must retain the above copyright
  12  *  notice, this list of conditions and the following disclaimer.
  13  *
  14  *      * Redistributions in binary form must reproduce the above
  15  *  copyright notice, this list of conditions and the following disclaimer
  16  *  in the documentation and/or other materials provided with the
  17  *  distribution.
  18  *
  19  *      * The names of its contributors may not be used to endorse or
  20  *  promote products derived from this software without specific prior
  21  *  written permission.
  22  *
  23  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26  *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  *  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  29  *  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  30  *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  31  *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  32  *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  33  *  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  *
  35  */
  36
  37 /* The crc32 functions and data was originally written by Spencer
  38  * Garrett <srg@quick.com> and was gleaned from the PostgreSQL source
  39  * tree via the files contrib/ltree/crc32.[ch] and from FreeBSD at
  40  * src/usr.bin/cksum/crc32.c.
  41  */
  42
  43 #include <libhashkit/common.h>
  44
  45 static const uint32_t crc32tab[256] = {
  46   0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
  47   0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
  48   0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
  49   0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
  50   0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
  51   0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
  52   0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
  53   0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
  54   0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
  55   0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
  56   0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
  57   0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
  58   0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
  59   0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
  60   0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
  61   0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
  62   0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
  63   0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
  64   0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
  65   0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
  66   0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
  67   0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
  68   0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
  69   0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
  70   0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
  71   0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
  72   0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
  73   0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
  74   0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
  75   0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
  76   0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
  77   0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
  78   0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
  79   0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
  80   0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
  81   0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
  82   0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
  83   0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
  84   0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
  85   0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
  86   0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
  87   0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
  88   0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
  89   0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
  90   0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
  91   0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
  92   0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
  93   0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
  94   0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
  95   0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
  96   0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
  97   0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
  98   0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
  99   0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 100   0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
 101   0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
 102   0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 103   0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
 104   0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
 105   0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 106   0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
 107   0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
 108   0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 109   0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d,
 110 };
 111
 112 uint32_t hashkit_crc32(const char *key, size_t key_length, void *context)
 113 {
 114   uint64_t x;
 115   uint32_t crc= UINT32_MAX;
 116   (void)context;
 117
 118   for (x= 0; x < key_length; x++)
 119      crc= (crc >> 8) ^ crc32tab[(crc ^ (uint64_t)key[x]) & 0xff];
 120
 121   return ((~crc) >> 16) & 0x7fff;
 122 }