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 #include <stdint.h>
29 #include <stdlib.h>
30
31 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
32 +(uint32_t)(((const uint8_t *)(d))[0]) )
33
SuperFastHash(const char * data,int len)34 uint32_t SuperFastHash (const char * data, int len) {
35 uint32_t hash = (uint32_t)len, tmp;
36 int rem;
37
38 if (len <= 0 || data == NULL) return 0;
39
40 rem = len & 3;
41 len >>= 2;
42
43 /* Main loop */
44 for (;len > 0; len--) {
45 hash += get16bits (data);
46 tmp = (uint32_t)(get16bits (data+2) << 11) ^ hash;
47 hash = (hash << 16) ^ tmp;
48 data += 2*sizeof (uint16_t);
49 hash += hash >> 11;
50 }
51
52 /* Handle end cases */
53 switch (rem) {
54 case 3: hash += get16bits (data);
55 hash ^= hash << 16;
56 hash ^= (uint32_t)(signed char)data[sizeof (uint16_t)] << 18;
57 hash += hash >> 11;
58 break;
59 case 2: hash += get16bits (data);
60 hash ^= hash << 11;
61 hash += hash >> 17;
62 break;
63 case 1: hash += (uint32_t)((signed char)*data);
64 hash ^= hash << 10;
65 hash += hash >> 1;
66 }
67
68 /* Force "avalanching" of final 127 bits */
69 hash ^= hash << 3;
70 hash += hash >> 5;
71 hash ^= hash << 4;
72 hash += hash >> 17;
73 hash ^= hash << 25;
74 hash += hash >> 6;
75
76 return hash;
77 }
78