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
114