Merge lp:~tangent-org/libmemcached/1.0-build/ Build: jenkins-Libmemcached-187
[m6w6/libmemcached] / 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 }