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