1 /* Copyright (c) 2010, Paul Hsieh
2 * All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * * Redistributions of source code must retain the above copyright notice, this
8 * list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright notice,
10 * this list of conditions and the following disclaimer in the documentation
11 * and/or other materials provided with the distribution.
12 * * Neither my name, Paul Hsieh, nor the names of any other contributors to the
13 * code use may not be used to endorse or promote products derived from this
14 * software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include <stddef.h>
30 #include <stdint.h>
31
32 #undef get16bits
33 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) || \
34 defined(_MSC_VER) || defined(__BORLANDC__) || defined(__TURBOC__)
35 #define get16bits(d) (*((const uint16_t *)(d)))
36 #endif
37
38 #if !defined(get16bits)
39 #define get16bits(d) \
40 ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) + \
41 (uint32_t)(((const uint8_t *)(d))[0]))
42 #endif
43
SuperFastHash(const char * data,int len,uint32_t hash)44 uint32_t SuperFastHash(const char *data, int len, uint32_t hash)
45 {
46 uint32_t tmp;
47 int rem;
48
49 if (len <= 0 || data == NULL)
50 return 0;
51
52 rem = len & 3;
53 len >>= 2;
54
55 /* Main loop */
56 for (; len > 0; len--) {
57 hash += get16bits(data);
58 tmp = (get16bits(data + 2) << 11) ^ hash;
59 hash = (hash << 16) ^ tmp;
60 data += 2 * sizeof(uint16_t);
61 hash += hash >> 11;
62 }
63
64 /* Handle end cases */
65 switch (rem) {
66 case 3:
67 hash += get16bits(data);
68 hash ^= hash << 16;
69 hash ^= ((signed char)data[sizeof(uint16_t)]) << 18;
70 hash += hash >> 11;
71 break;
72 case 2:
73 hash += get16bits(data);
74 hash ^= hash << 11;
75 hash += hash >> 17;
76 break;
77 case 1:
78 hash += (signed char)*data;
79 hash ^= hash << 10;
80 hash += hash >> 1;
81 }
82
83 /* Force "avalanching" of final 127 bits */
84 hash ^= hash << 3;
85 hash += hash >> 5;
86 hash ^= hash << 4;
87 hash += hash >> 17;
88 hash ^= hash << 25;
89 hash += hash >> 6;
90
91 return hash;
92 }
93