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