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