|
996
|
1 /*********************************************************************
|
|
|
2 *
|
|
|
3 * Copyright (C) 2001-2002, Simon Kagstrom
|
|
|
4 *
|
|
|
5 * Filename: hash_functions.c
|
|
|
6 * Description: Hash functions
|
|
|
7 *
|
|
|
8 * This program is free software; you can redistribute it and/or
|
|
|
9 * modify it under the terms of the GNU Library General Public License
|
|
|
10 * as published by the Free Software Foundation; either version 2
|
|
|
11 * of the License, or (at your option) any later version.
|
|
|
12 *
|
|
|
13 * This program is distributed in the hope that it will be useful,
|
|
|
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
16 * GNU General Public License for more details.
|
|
|
17 *
|
|
|
18 * You should have received a copy of the GNU Library General Public
|
|
|
19 * License along with this program; if not, write to the Free Software
|
|
|
20 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
|
|
|
21 * 02111-1307, USA.
|
|
|
22 *
|
|
|
23 * $Id: hash_functions.c 2174 2005-03-18 07:00:30Z ska $
|
|
|
24 *
|
|
|
25 ********************************************************************/
|
|
|
26
|
|
|
27 #if 0
|
|
|
28 /* One-at-a-time hash (found in a web article from ddj), this is the
|
|
|
29 * standard hash function.
|
|
|
30 *
|
|
|
31 * See http://burtleburtle.net/bob/hash/doobs.html
|
|
|
32 * for the hash functions used here.
|
|
|
33 */
|
|
|
34 FUNGE_ATTR_FAST ght_uint32_t ght_one_at_a_time_hash(const ght_hash_key_t *p_key)
|
|
|
35 {
|
|
|
36 ght_uint32_t i_hash = 0;
|
|
|
37 size_t i;
|
|
|
38
|
|
|
39 assert(p_key != NULL);
|
|
|
40
|
|
|
41 for (i = 0; i < sizeof(fungeSpaceHashKey); ++i) {
|
|
|
42 i_hash += ((const unsigned char*)&(p_key->p_key))[i];
|
|
|
43 i_hash += (i_hash << 10);
|
|
|
44 i_hash ^= (i_hash >> 6);
|
|
|
45 }
|
|
|
46 i_hash += (i_hash << 3);
|
|
|
47 i_hash ^= (i_hash >> 11);
|
|
|
48 i_hash += (i_hash << 15);
|
|
|
49
|
|
|
50 return i_hash;
|
|
|
51 }
|
|
|
52 #endif
|
|
|
53
|
|
|
54 #if 1
|
|
|
55 /* CRC32 hash based on code from comp.compression FAQ.
|
|
|
56 * Added by Dru Lemley <spambait@lemley.net>
|
|
|
57 */
|
|
|
58 FUNGE_ATTR_FAST ght_uint32_t CF_GHT_NAME(CF_GHT_VAR, crc_hash)(const CF_GHT_NAME(CF_GHT_VAR, hash_key_t) *p_key)
|
|
|
59 {
|
|
|
60 const unsigned char *p;
|
|
|
61 ght_uint32_t crc;
|
|
|
62
|
|
|
63 assert(p_key != NULL);
|
|
|
64
|
|
|
65 crc = 0xffffffff; /* preload shift register, per CRC-32 spec */
|
|
|
66 p = (const unsigned char *)&(p_key->p_key);
|
|
|
67
|
|
|
68 for (size_t i = 0; i < sizeof(CF_GHT_KEY); i++)
|
|
|
69 crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ (p[i])];
|
|
|
70
|
|
|
71 return ~crc; /* transmit complement, per CRC-32 spec */
|
|
|
72 }
|
|
|
73 #endif
|
|
|
74
|
|
|
75 #if 0
|
|
|
76 #ifdef USE64
|
|
|
77 FUNGE_ATTR_FAST
|
|
|
78 static inline ght_uint32_t MurmurHash2(const fungeSpaceHashKey * key)
|
|
|
79 {
|
|
|
80 // 'm' and 'r' are mixing constants generated offline.
|
|
|
81 // They're not really 'magic', they just happen to work well.
|
|
|
82
|
|
|
83 const ght_uint32_t m = 0x5bd1e995;
|
|
|
84 const int32_t r = 24;
|
|
|
85
|
|
|
86 // Initialise the hash to a 'random' value
|
|
|
87 size_t len = sizeof(fungeSpaceHashKey);
|
|
|
88 ght_uint32_t h = 0x7fd652ad ^ len;
|
|
|
89
|
|
|
90 // Mix 4 bytes at a time into the hash
|
|
|
91
|
|
|
92 const unsigned char * data = (const unsigned char *)key;
|
|
|
93
|
|
|
94 while(len >= 4)
|
|
|
95 {
|
|
|
96 ght_uint32_t k = *(const ght_uint32_t *)data;
|
|
|
97
|
|
|
98 k *= m;
|
|
|
99 k ^= k >> r;
|
|
|
100 k *= m;
|
|
|
101
|
|
|
102 h *= m;
|
|
|
103 h ^= k;
|
|
|
104
|
|
|
105 data += 4;
|
|
|
106 len -= 4;
|
|
|
107 }
|
|
|
108
|
|
|
109 // Not needed the way we use it.
|
|
|
110 #if 0
|
|
|
111 // Handle the last few bytes of the input array
|
|
|
112
|
|
|
113 switch(len)
|
|
|
114 {
|
|
|
115 case 3: h ^= data[2] << 16;
|
|
|
116 case 2: h ^= data[1] << 8;
|
|
|
117 case 1: h ^= data[0];
|
|
|
118 h *= m;
|
|
|
119 };
|
|
|
120 #endif
|
|
|
121
|
|
|
122 // Do a few final mixes of the hash to ensure the last few
|
|
|
123 // bytes are well-incorporated.
|
|
|
124
|
|
|
125 h ^= h >> 13;
|
|
|
126 h *= m;
|
|
|
127 h ^= h >> 15;
|
|
|
128
|
|
|
129 return h;
|
|
|
130 }
|
|
|
131 #endif
|
|
|
132
|
|
|
133 /* CRC32 hash based on code from comp.compression FAQ.
|
|
|
134 * Added by Dru Lemley <spambait@lemley.net>
|
|
|
135 */
|
|
|
136 FUNGE_ATTR_FAST ght_uint32_t murmur_hash(const ght_hash_key_t *p_key)
|
|
|
137 {
|
|
|
138 #ifdef USE32
|
|
|
139 const ght_uint32_t m = 0xc6a4a793;
|
|
|
140
|
|
|
141 ght_uint32_t h = 0x7fd652ad ^ (8 * m), k;
|
|
|
142
|
|
|
143 k = p_key->p_key.x; k *= m; k ^= k >> 16; k *= m; h += k; h *= m;
|
|
|
144 k = p_key->p_key.y; k *= m; k ^= k >> 16; k *= m; h += k; h *= m;
|
|
|
145
|
|
|
146 h *= m; h ^= h >> 10;
|
|
|
147 h *= m; h ^= h >> 17;
|
|
|
148
|
|
|
149 return h;
|
|
|
150 #else
|
|
|
151 return MurmurHash2(&p_key->p_key);
|
|
|
152 #endif
|
|
|
153 }
|
|
|
154 #endif
|
