Merge lp:~tangent-org/libmemcached/1.0-build/ Build: jenkins-Libmemcached-187
[m6w6/libmemcached] / libhashkit / hsieh.cc
1 /* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
2 *
3 * HashKit library
4 *
5 * Copyright (C) 2011-2012 Data Differential, http://datadifferential.com/
6 * Copyright (C) 2006-2009 Brian Aker All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are
10 * met:
11 *
12 * * Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 *
15 * * Redistributions in binary form must reproduce the above
16 * copyright notice, this list of conditions and the following disclaimer
17 * in the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * * The names of its contributors may not be used to endorse or
21 * promote products derived from this software without specific prior
22 * written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
27 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
28 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
29 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
30 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
31 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
34 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 *
36 */
37
38 /* By Paul Hsieh (C) 2004, 2005. Covered under the Paul Hsieh
39 * derivative license.
40 * See: http://www.azillionmonkeys.com/qed/weblicense.html for license
41 * details.
42 * http://www.azillionmonkeys.com/qed/hash.html
43 */
44
45 #include <libhashkit/common.h>
46
47 #undef get16bits
48 #if (defined(__GNUC__) && defined(__i386__))
49 #define get16bits(d) (*((const uint16_t *) (d)))
50 #endif
51
52 #if !defined (get16bits)
53 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
54 +(uint32_t)(((const uint8_t *)(d))[0]) )
55 #endif
56
57 #ifdef HAVE_HSIEH_HASH
58 uint32_t hashkit_hsieh(const char *key, size_t key_length, void *)
59 {
60 uint32_t hash = 0, tmp;
61 int rem;
62
63 if (key_length <= 0 || key == NULL)
64 return 0;
65
66 rem = key_length & 3;
67 key_length >>= 2;
68
69 /* Main loop */
70 for (;key_length > 0; key_length--)
71 {
72 hash += get16bits (key);
73 tmp = (get16bits (key+2) << 11) ^ hash;
74 hash = (hash << 16) ^ tmp;
75 key += 2*sizeof (uint16_t);
76 hash += hash >> 11;
77 }
78
79 /* Handle end cases */
80 switch (rem)
81 {
82 case 3: hash += get16bits (key);
83 hash ^= hash << 16;
84 hash ^= (uint32_t)key[sizeof (uint16_t)] << 18;
85 hash += hash >> 11;
86 break;
87 case 2: hash += get16bits (key);
88 hash ^= hash << 11;
89 hash += hash >> 17;
90 break;
91 case 1: hash += (unsigned char)(*key);
92 hash ^= hash << 10;
93 hash += hash >> 1;
94 default:
95 break;
96 }
97
98 /* Force "avalanching" of final 127 bits */
99 hash ^= hash << 3;
100 hash += hash >> 5;
101 hash ^= hash << 4;
102 hash += hash >> 17;
103 hash ^= hash << 25;
104 hash += hash >> 6;
105
106 return hash;
107 }
108 #else
109 uint32_t hashkit_hsieh(const char *, size_t , void *)
110 {
111 return 0;
112 }
113 #endif