| 1 |
/* SPDX-License-Identifier: LGPL-2.1-only */ |
| 2 |
/* |
| 3 |
* This code was taken from http://ccodearchive.net/info/hash.html |
| 4 |
* The original file was modified to remove unwanted code |
| 5 |
* and some changes to fit the current build environment |
| 6 |
*/ |
| 7 |
/* |
| 8 |
------------------------------------------------------------------------------- |
| 9 |
lookup3.c, by Bob Jenkins, May 2006, Public Domain. |
| 10 |
|
| 11 |
These are functions for producing 32-bit hashes for hash table lookup. |
| 12 |
hash_word(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() |
| 13 |
are externally useful functions. Routines to test the hash are included |
| 14 |
if SELF_TEST is defined. You can use this free for any purpose. It's in |
| 15 |
the public domain. It has no warranty. |
| 16 |
|
| 17 |
You probably want to use hashlittle(). hashlittle() and hashbig() |
| 18 |
hash byte arrays. hashlittle() is is faster than hashbig() on |
| 19 |
little-endian machines. Intel and AMD are little-endian machines. |
| 20 |
On second thought, you probably want hashlittle2(), which is identical to |
| 21 |
hashlittle() except it returns two 32-bit hashes for the price of one. |
| 22 |
You could implement hashbig2() if you wanted but I haven't bothered here. |
| 23 |
|
| 24 |
If you want to find a hash of, say, exactly 7 integers, do |
| 25 |
a = i1; b = i2; c = i3; |
| 26 |
mix(a,b,c); |
| 27 |
a += i4; b += i5; c += i6; |
| 28 |
mix(a,b,c); |
| 29 |
a += i7; |
| 30 |
final(a,b,c); |
| 31 |
then use c as the hash value. If you have a variable length array of |
| 32 |
4-byte integers to hash, use hash_word(). If you have a byte array (like |
| 33 |
a character string), use hashlittle(). If you have several byte arrays, or |
| 34 |
a mix of things, see the comments above hashlittle(). |
| 35 |
|
| 36 |
Why is this so big? I read 12 bytes at a time into 3 4-byte integers, |
| 37 |
then mix those integers. This is fast (you can do a lot more thorough |
| 38 |
mixing with 12*3 instructions on 3 integers than you can with 3 instructions |
| 39 |
on 1 byte), but shoehorning those bytes into integers efficiently is messy. |
| 40 |
------------------------------------------------------------------------------- |
| 41 |
*/ |
| 42 |
#include "nl-default.h" |
| 43 |
|
| 44 |
#include <netlink/hash.h> |
| 45 |
|
| 46 |
#if HAVE_LITTLE_ENDIAN |
| 47 |
#define HASH_LITTLE_ENDIAN 1 |
| 48 |
#define HASH_BIG_ENDIAN 0 |
| 49 |
#elif HAVE_BIG_ENDIAN |
| 50 |
#define HASH_LITTLE_ENDIAN 0 |
| 51 |
#define HASH_BIG_ENDIAN 1 |
| 52 |
#else |
| 53 |
#error Unknown endian |
| 54 |
#endif |
| 55 |
|
| 56 |
#define hashsize(n) ((uint32_t)1<<(n)) |
| 57 |
#define hashmask(n) (hashsize(n)-1) |
| 58 |
#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) |
| 59 |
|
| 60 |
/* |
| 61 |
------------------------------------------------------------------------------- |
| 62 |
mix -- mix 3 32-bit values reversibly. |
| 63 |
|
| 64 |
This is reversible, so any information in (a,b,c) before mix() is |
| 65 |
still in (a,b,c) after mix(). |
| 66 |
|
| 67 |
If four pairs of (a,b,c) inputs are run through mix(), or through |
| 68 |
mix() in reverse, there are at least 32 bits of the output that |
| 69 |
are sometimes the same for one pair and different for another pair. |
| 70 |
This was tested for: |
| 71 |
* pairs that differed by one bit, by two bits, in any combination |
| 72 |
of top bits of (a,b,c), or in any combination of bottom bits of |
| 73 |
(a,b,c). |
| 74 |
* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed |
| 75 |
the output delta to a Gray code (a^(a>>1)) so a string of 1's (as |
| 76 |
is commonly produced by subtraction) look like a single 1-bit |
| 77 |
difference. |
| 78 |
* the base values were pseudorandom, all zero but one bit set, or |
| 79 |
all zero plus a counter that starts at zero. |
| 80 |
|
| 81 |
Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that |
| 82 |
satisfy this are |
| 83 |
4 6 8 16 19 4 |
| 84 |
9 15 3 18 27 15 |
| 85 |
14 9 3 7 17 3 |
| 86 |
Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing |
| 87 |
for "differ" defined as + with a one-bit base and a two-bit delta. I |
| 88 |
used http://burtleburtle.net/bob/hash/avalanche.html to choose |
| 89 |
the operations, constants, and arrangements of the variables. |
| 90 |
|
| 91 |
This does not achieve avalanche. There are input bits of (a,b,c) |
| 92 |
that fail to affect some output bits of (a,b,c), especially of a. The |
| 93 |
most thoroughly mixed value is c, but it doesn't really even achieve |
| 94 |
avalanche in c. |
| 95 |
|
| 96 |
This allows some parallelism. Read-after-writes are good at doubling |
| 97 |
the number of bits affected, so the goal of mixing pulls in the opposite |
| 98 |
direction as the goal of parallelism. I did what I could. Rotates |
| 99 |
seem to cost as much as shifts on every machine I could lay my hands |
| 100 |
on, and rotates are much kinder to the top and bottom bits, so I used |
| 101 |
rotates. |
| 102 |
------------------------------------------------------------------------------- |
| 103 |
*/ |
| 104 |
#define mix(a,b,c) \ |
| 105 |
{ \ |
| 106 |
a -= c; a ^= rot(c, 4); c += b; \ |
| 107 |
b -= a; b ^= rot(a, 6); a += c; \ |
| 108 |
c -= b; c ^= rot(b, 8); b += a; \ |
| 109 |
a -= c; a ^= rot(c,16); c += b; \ |
| 110 |
b -= a; b ^= rot(a,19); a += c; \ |
| 111 |
c -= b; c ^= rot(b, 4); b += a; \ |
| 112 |
} |
| 113 |
|
| 114 |
/* |
| 115 |
------------------------------------------------------------------------------- |
| 116 |
final -- final mixing of 3 32-bit values (a,b,c) into c |
| 117 |
|
| 118 |
Pairs of (a,b,c) values differing in only a few bits will usually |
| 119 |
produce values of c that look totally different. This was tested for |
| 120 |
* pairs that differed by one bit, by two bits, in any combination |
| 121 |
of top bits of (a,b,c), or in any combination of bottom bits of |
| 122 |
(a,b,c). |
| 123 |
* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed |
| 124 |
the output delta to a Gray code (a^(a>>1)) so a string of 1's (as |
| 125 |
is commonly produced by subtraction) look like a single 1-bit |
| 126 |
difference. |
| 127 |
* the base values were pseudorandom, all zero but one bit set, or |
| 128 |
all zero plus a counter that starts at zero. |
| 129 |
|
| 130 |
These constants passed: |
| 131 |
14 11 25 16 4 14 24 |
| 132 |
12 14 25 16 4 14 24 |
| 133 |
and these came close: |
| 134 |
4 8 15 26 3 22 24 |
| 135 |
10 8 15 26 3 22 24 |
| 136 |
11 8 15 26 3 22 24 |
| 137 |
------------------------------------------------------------------------------- |
| 138 |
*/ |
| 139 |
#define final(a,b,c) \ |
| 140 |
{ \ |
| 141 |
c ^= b; c -= rot(b,14); \ |
| 142 |
a ^= c; a -= rot(c,11); \ |
| 143 |
b ^= a; b -= rot(a,25); \ |
| 144 |
c ^= b; c -= rot(b,16); \ |
| 145 |
a ^= c; a -= rot(c,4); \ |
| 146 |
b ^= a; b -= rot(a,14); \ |
| 147 |
c ^= b; c -= rot(b,24); \ |
| 148 |
} |
| 149 |
|
| 150 |
/* |
| 151 |
------------------------------------------------------------------------------- |
| 152 |
hashlittle() -- hash a variable-length key into a 32-bit value |
| 153 |
k : the key (the unaligned variable-length array of bytes) |
| 154 |
length : the length of the key, counting by bytes |
| 155 |
val2 : IN: can be any 4-byte value OUT: second 32 bit hash. |
| 156 |
Returns a 32-bit value. Every bit of the key affects every bit of |
| 157 |
the return value. Two keys differing by one or two bits will have |
| 158 |
totally different hash values. Note that the return value is better |
| 159 |
mixed than val2, so use that first. |
| 160 |
|
| 161 |
The best hash table sizes are powers of 2. There is no need to do |
| 162 |
mod a prime (mod is sooo slow!). If you need less than 32 bits, |
| 163 |
use a bitmask. For example, if you need only 10 bits, do |
| 164 |
h = (h & hashmask(10)); |
| 165 |
In which case, the hash table should have hashsize(10) elements. |
| 166 |
|
| 167 |
If you are hashing n strings (uint8_t **)k, do it like this: |
| 168 |
for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); |
| 169 |
|
| 170 |
By Bob Jenkins, 2006. [email protected]. You may use this |
| 171 |
code any way you wish, private, educational, or commercial. It's free. |
| 172 |
|
| 173 |
Use for hash table lookup, or anything where one collision in 2^^32 is |
| 174 |
acceptable. Do NOT use for cryptographic purposes. |
| 175 |
------------------------------------------------------------------------------- |
| 176 |
*/ |
| 177 |
|
| 178 |
static uint32_t hashlittle( const void *key, size_t length, uint32_t *val2 ) |
| 179 |
{ |
| 180 |
uint32_t a,b,c; /* internal state */ |
| 181 |
union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ |
| 182 |
|
| 183 |
/* Set up the internal state */ |
| 184 |
a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2; |
| 185 |
|
| 186 |
u.ptr = key; |
| 187 |
if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { |
| 188 |
const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ |
| 189 |
const uint8_t *k8; |
| 190 |
|
| 191 |
/*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ |
| 192 |
while (length > 12) |
| 193 |
{ |
| 194 |
a += k[0]; |
| 195 |
b += k[1]; |
| 196 |
c += k[2]; |
| 197 |
mix(a,b,c); |
| 198 |
length -= 12; |
| 199 |
k += 3; |
| 200 |
} |
| 201 |
|
| 202 |
/*----------------------------- handle the last (probably partial) block */ |
| 203 |
/* |
| 204 |
* "k[2]&0xffffff" actually reads beyond the end of the string, but |
| 205 |
* then masks off the part it's not allowed to read. Because the |
| 206 |
* string is aligned, the masked-off tail is in the same word as the |
| 207 |
* rest of the string. Every machine with memory protection I've seen |
| 208 |
* does it on word boundaries, so is OK with this. But VALGRIND will |
| 209 |
* still catch it and complain. The masking trick does make the hash |
| 210 |
* noticably faster for short strings (like English words). |
| 211 |
* |
| 212 |
* Not on my testing with gcc 4.5 on an intel i5 CPU, at least --RR. |
| 213 |
*/ |
| 214 |
#if 0 |
| 215 |
switch(length) |
| 216 |
{ |
| 217 |
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; |
| 218 |
case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; |
| 219 |
case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; |
| 220 |
case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; |
| 221 |
case 8 : b+=k[1]; a+=k[0]; break; |
| 222 |
case 7 : b+=k[1]&0xffffff; a+=k[0]; break; |
| 223 |
case 6 : b+=k[1]&0xffff; a+=k[0]; break; |
| 224 |
case 5 : b+=k[1]&0xff; a+=k[0]; break; |
| 225 |
case 4 : a+=k[0]; break; |
| 226 |
case 3 : a+=k[0]&0xffffff; break; |
| 227 |
case 2 : a+=k[0]&0xffff; break; |
| 228 |
case 1 : a+=k[0]&0xff; break; |
| 229 |
case 0 : return c; /* zero length strings require no mixing */ |
| 230 |
} |
| 231 |
|
| 232 |
#else /* make valgrind happy */ |
| 233 |
|
| 234 |
k8 = (const uint8_t *)k; |
| 235 |
switch(length) |
| 236 |
{ |
| 237 |
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; |
| 238 |
case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ |
| 239 |
case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ |
| 240 |
case 9 : c+=k8[8]; /* fall through */ |
| 241 |
case 8 : b+=k[1]; a+=k[0]; break; |
| 242 |
case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ |
| 243 |
case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ |
| 244 |
case 5 : b+=k8[4]; /* fall through */ |
| 245 |
case 4 : a+=k[0]; break; |
| 246 |
case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ |
| 247 |
case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ |
| 248 |
case 1 : a+=k8[0]; break; |
| 249 |
case 0 : return c; |
| 250 |
} |
| 251 |
|
| 252 |
#endif /* !valgrind */ |
| 253 |
|
| 254 |
} else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { |
| 255 |
const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ |
| 256 |
const uint8_t *k8; |
| 257 |
|
| 258 |
/*--------------- all but last block: aligned reads and different mixing */ |
| 259 |
while (length > 12) |
| 260 |
{ |
| 261 |
a += k[0] + (((uint32_t)k[1])<<16); |
| 262 |
b += k[2] + (((uint32_t)k[3])<<16); |
| 263 |
c += k[4] + (((uint32_t)k[5])<<16); |
| 264 |
mix(a,b,c); |
| 265 |
length -= 12; |
| 266 |
k += 6; |
| 267 |
} |
| 268 |
|
| 269 |
/*----------------------------- handle the last (probably partial) block */ |
| 270 |
k8 = (const uint8_t *)k; |
| 271 |
switch(length) |
| 272 |
{ |
| 273 |
case 12: c+=k[4]+(((uint32_t)k[5])<<16); |
| 274 |
b+=k[2]+(((uint32_t)k[3])<<16); |
| 275 |
a+=k[0]+(((uint32_t)k[1])<<16); |
| 276 |
break; |
| 277 |
case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ |
| 278 |
case 10: c+=k[4]; |
| 279 |
b+=k[2]+(((uint32_t)k[3])<<16); |
| 280 |
a+=k[0]+(((uint32_t)k[1])<<16); |
| 281 |
break; |
| 282 |
case 9 : c+=k8[8]; /* fall through */ |
| 283 |
case 8 : b+=k[2]+(((uint32_t)k[3])<<16); |
| 284 |
a+=k[0]+(((uint32_t)k[1])<<16); |
| 285 |
break; |
| 286 |
case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ |
| 287 |
case 6 : b+=k[2]; |
| 288 |
a+=k[0]+(((uint32_t)k[1])<<16); |
| 289 |
break; |
| 290 |
case 5 : b+=k8[4]; /* fall through */ |
| 291 |
case 4 : a+=k[0]+(((uint32_t)k[1])<<16); |
| 292 |
break; |
| 293 |
case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ |
| 294 |
case 2 : a+=k[0]; |
| 295 |
break; |
| 296 |
case 1 : a+=k8[0]; |
| 297 |
break; |
| 298 |
case 0 : return c; /* zero length requires no mixing */ |
| 299 |
} |
| 300 |
|
| 301 |
} else { /* need to read the key one byte at a time */ |
| 302 |
const uint8_t *k = (const uint8_t *)key; |
| 303 |
|
| 304 |
/*--------------- all but the last block: affect some 32 bits of (a,b,c) */ |
| 305 |
while (length > 12) |
| 306 |
{ |
| 307 |
a += k[0]; |
| 308 |
a += ((uint32_t)k[1])<<8; |
| 309 |
a += ((uint32_t)k[2])<<16; |
| 310 |
a += ((uint32_t)k[3])<<24; |
| 311 |
b += k[4]; |
| 312 |
b += ((uint32_t)k[5])<<8; |
| 313 |
b += ((uint32_t)k[6])<<16; |
| 314 |
b += ((uint32_t)k[7])<<24; |
| 315 |
c += k[8]; |
| 316 |
c += ((uint32_t)k[9])<<8; |
| 317 |
c += ((uint32_t)k[10])<<16; |
| 318 |
c += ((uint32_t)k[11])<<24; |
| 319 |
mix(a,b,c); |
| 320 |
length -= 12; |
| 321 |
k += 12; |
| 322 |
} |
| 323 |
|
| 324 |
/*-------------------------------- last block: affect all 32 bits of (c) */ |
| 325 |
switch(length) /* all the case statements fall through */ |
| 326 |
{ |
| 327 |
case 12: c+=((uint32_t)k[11])<<24; /* fall through */ |
| 328 |
case 11: c+=((uint32_t)k[10])<<16; /* fall through */ |
| 329 |
case 10: c+=((uint32_t)k[9])<<8; /* fall through */ |
| 330 |
case 9 : c+=k[8]; /* fall through */ |
| 331 |
case 8 : b+=((uint32_t)k[7])<<24; /* fall through */ |
| 332 |
case 7 : b+=((uint32_t)k[6])<<16; /* fall through */ |
| 333 |
case 6 : b+=((uint32_t)k[5])<<8; /* fall through */ |
| 334 |
case 5 : b+=k[4]; /* fall through */ |
| 335 |
case 4 : a+=((uint32_t)k[3])<<24; /* fall through */ |
| 336 |
case 3 : a+=((uint32_t)k[2])<<16; /* fall through */ |
| 337 |
case 2 : a+=((uint32_t)k[1])<<8; /* fall through */ |
| 338 |
case 1 : a+=k[0]; |
| 339 |
break; |
| 340 |
case 0 : return c; |
| 341 |
} |
| 342 |
} |
| 343 |
|
| 344 |
final(a,b,c); |
| 345 |
*val2 = b; |
| 346 |
return c; |
| 347 |
} |
| 348 |
|
| 349 |
/* |
| 350 |
* hashbig(): |
| 351 |
* This is the same as hash_word() on big-endian machines. It is different |
| 352 |
* from hashlittle() on all machines. hashbig() takes advantage of |
| 353 |
* big-endian byte ordering. |
| 354 |
*/ |
| 355 |
static uint32_t hashbig( const void *key, size_t length, uint32_t *val2) |
| 356 |
{ |
| 357 |
uint32_t a,b,c; |
| 358 |
union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */ |
| 359 |
|
| 360 |
/* Set up the internal state */ |
| 361 |
a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2; |
| 362 |
|
| 363 |
u.ptr = key; |
| 364 |
if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) { |
| 365 |
const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ |
| 366 |
const uint8_t *k8; |
| 367 |
|
| 368 |
/*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ |
| 369 |
while (length > 12) |
| 370 |
{ |
| 371 |
a += k[0]; |
| 372 |
b += k[1]; |
| 373 |
c += k[2]; |
| 374 |
mix(a,b,c); |
| 375 |
length -= 12; |
| 376 |
k += 3; |
| 377 |
} |
| 378 |
|
| 379 |
/*----------------------------- handle the last (probably partial) block */ |
| 380 |
/* |
| 381 |
* "k[2]<<8" actually reads beyond the end of the string, but |
| 382 |
* then shifts out the part it's not allowed to read. Because the |
| 383 |
* string is aligned, the illegal read is in the same word as the |
| 384 |
* rest of the string. Every machine with memory protection I've seen |
| 385 |
* does it on word boundaries, so is OK with this. But VALGRIND will |
| 386 |
* still catch it and complain. The masking trick does make the hash |
| 387 |
* noticably faster for short strings (like English words). |
| 388 |
* |
| 389 |
* Not on my testing with gcc 4.5 on an intel i5 CPU, at least --RR. |
| 390 |
*/ |
| 391 |
#if 0 |
| 392 |
switch(length) |
| 393 |
{ |
| 394 |
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; |
| 395 |
case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break; |
| 396 |
case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break; |
| 397 |
case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break; |
| 398 |
case 8 : b+=k[1]; a+=k[0]; break; |
| 399 |
case 7 : b+=k[1]&0xffffff00; a+=k[0]; break; |
| 400 |
case 6 : b+=k[1]&0xffff0000; a+=k[0]; break; |
| 401 |
case 5 : b+=k[1]&0xff000000; a+=k[0]; break; |
| 402 |
case 4 : a+=k[0]; break; |
| 403 |
case 3 : a+=k[0]&0xffffff00; break; |
| 404 |
case 2 : a+=k[0]&0xffff0000; break; |
| 405 |
case 1 : a+=k[0]&0xff000000; break; |
| 406 |
case 0 : return c; /* zero length strings require no mixing */ |
| 407 |
} |
| 408 |
|
| 409 |
#else /* make valgrind happy */ |
| 410 |
|
| 411 |
k8 = (const uint8_t *)k; |
| 412 |
switch(length) /* all the case statements fall through */ |
| 413 |
{ |
| 414 |
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; |
| 415 |
case 11: c+=((uint32_t)k8[10])<<8; /* fall through */ |
| 416 |
case 10: c+=((uint32_t)k8[9])<<16; /* fall through */ |
| 417 |
case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */ |
| 418 |
case 8 : b+=k[1]; a+=k[0]; break; |
| 419 |
case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */ |
| 420 |
case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */ |
| 421 |
case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */ |
| 422 |
case 4 : a+=k[0]; break; |
| 423 |
case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */ |
| 424 |
case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */ |
| 425 |
case 1 : a+=((uint32_t)k8[0])<<24; break; |
| 426 |
case 0 : return c; |
| 427 |
} |
| 428 |
|
| 429 |
#endif /* !VALGRIND */ |
| 430 |
|
| 431 |
} else { /* need to read the key one byte at a time */ |
| 432 |
const uint8_t *k = (const uint8_t *)key; |
| 433 |
|
| 434 |
/*--------------- all but the last block: affect some 32 bits of (a,b,c) */ |
| 435 |
while (length > 12) |
| 436 |
{ |
| 437 |
a += ((uint32_t)k[0])<<24; |
| 438 |
a += ((uint32_t)k[1])<<16; |
| 439 |
a += ((uint32_t)k[2])<<8; |
| 440 |
a += ((uint32_t)k[3]); |
| 441 |
b += ((uint32_t)k[4])<<24; |
| 442 |
b += ((uint32_t)k[5])<<16; |
| 443 |
b += ((uint32_t)k[6])<<8; |
| 444 |
b += ((uint32_t)k[7]); |
| 445 |
c += ((uint32_t)k[8])<<24; |
| 446 |
c += ((uint32_t)k[9])<<16; |
| 447 |
c += ((uint32_t)k[10])<<8; |
| 448 |
c += ((uint32_t)k[11]); |
| 449 |
mix(a,b,c); |
| 450 |
length -= 12; |
| 451 |
k += 12; |
| 452 |
} |
| 453 |
|
| 454 |
/*-------------------------------- last block: affect all 32 bits of (c) */ |
| 455 |
switch(length) /* all the case statements fall through */ |
| 456 |
{ |
| 457 |
case 12: c+=k[11]; /* fall through */ |
| 458 |
case 11: c+=((uint32_t)k[10])<<8; /* fall through */ |
| 459 |
case 10: c+=((uint32_t)k[9])<<16; /* fall through */ |
| 460 |
case 9 : c+=((uint32_t)k[8])<<24; /* fall through */ |
| 461 |
case 8 : b+=k[7]; /* fall through */ |
| 462 |
case 7 : b+=((uint32_t)k[6])<<8; /* fall through */ |
| 463 |
case 6 : b+=((uint32_t)k[5])<<16; /* fall through */ |
| 464 |
case 5 : b+=((uint32_t)k[4])<<24; /* fall through */ |
| 465 |
case 4 : a+=k[3]; /* fall through */ |
| 466 |
case 3 : a+=((uint32_t)k[2])<<8; /* fall through */ |
| 467 |
case 2 : a+=((uint32_t)k[1])<<16; /* fall through */ |
| 468 |
case 1 : a+=((uint32_t)k[0])<<24; /* fall through */ |
| 469 |
break; |
| 470 |
case 0 : return c; |
| 471 |
} |
| 472 |
} |
| 473 |
|
| 474 |
final(a,b,c); |
| 475 |
*val2 = b; |
| 476 |
return c; |
| 477 |
} |
| 478 |
|
| 479 |
uint32_t nl_hash_any(const void *key, size_t length, uint32_t base) |
| 480 |
{ |
| 481 |
if (HASH_BIG_ENDIAN) |
| 482 |
return hashbig(key, length, &base); |
| 483 |
else |
| 484 |
return hashlittle(key, length, &base); |
| 485 |
} |