bc8e6fe4ed28789d6fe7c39ede3eb9fc15bd3fb3
[project/luci.git] / libs / lmo / src / lmo_hash.c
1 /*
2 * Hash function from http://www.azillionmonkeys.com/qed/hash.html
3 * Copyright (C) 2004-2008 by Paul Hsieh
4 */
5
6 #include "lmo.h"
7
8 uint32_t sfh_hash(const char * data, int len)
9 {
10 uint32_t hash = len, tmp;
11 int rem;
12
13 if (len <= 0 || data == NULL) return 0;
14
15 rem = len & 3;
16 len >>= 2;
17
18 /* Main loop */
19 for (;len > 0; len--) {
20 hash += sfh_get16(data);
21 tmp = (sfh_get16(data+2) << 11) ^ hash;
22 hash = (hash << 16) ^ tmp;
23 data += 2*sizeof(uint16_t);
24 hash += hash >> 11;
25 }
26
27 /* Handle end cases */
28 switch (rem) {
29 case 3: hash += sfh_get16(data);
30 hash ^= hash << 16;
31 hash ^= data[sizeof(uint16_t)] << 18;
32 hash += hash >> 11;
33 break;
34 case 2: hash += sfh_get16(data);
35 hash ^= hash << 11;
36 hash += hash >> 17;
37 break;
38 case 1: hash += *data;
39 hash ^= hash << 10;
40 hash += hash >> 1;
41 }
42
43 /* Force "avalanching" of final 127 bits */
44 hash ^= hash << 3;
45 hash += hash >> 5;
46 hash ^= hash << 4;
47 hash += hash >> 17;
48 hash ^= hash << 25;
49 hash += hash >> 6;
50
51 return hash;
52 }
53