diff options
Diffstat (limited to 'lib/jhash.c')
| -rw-r--r-- | lib/jhash.c | 254 |
1 files changed, 130 insertions, 124 deletions
diff --git a/lib/jhash.c b/lib/jhash.c index 33589b64e2..b943997b1b 100644 --- a/lib/jhash.c +++ b/lib/jhash.c @@ -24,129 +24,138 @@ #define JHASH_GOLDEN_RATIO 0x9e3779b9 /* NOTE: Arguments are modified. */ -#define __jhash_mix(a, b, c) \ -{ \ - a -= b; a -= c; a ^= (c>>13); \ - b -= c; b -= a; b ^= (a<<8); \ - c -= a; c -= b; c ^= (b>>13); \ - a -= b; a -= c; a ^= (c>>12); \ - b -= c; b -= a; b ^= (a<<16); \ - c -= a; c -= b; c ^= (b>>5); \ - a -= b; a -= c; a ^= (c>>3); \ - b -= c; b -= a; b ^= (a<<10); \ - c -= a; c -= b; c ^= (b>>15); \ -} +#define __jhash_mix(a, b, c) \ + { \ + a -= b; \ + a -= c; \ + a ^= (c >> 13); \ + b -= c; \ + b -= a; \ + b ^= (a << 8); \ + c -= a; \ + c -= b; \ + c ^= (b >> 13); \ + a -= b; \ + a -= c; \ + a ^= (c >> 12); \ + b -= c; \ + b -= a; \ + b ^= (a << 16); \ + c -= a; \ + c -= b; \ + c ^= (b >> 5); \ + a -= b; \ + a -= c; \ + a ^= (c >> 3); \ + b -= c; \ + b -= a; \ + b ^= (a << 10); \ + c -= a; \ + c -= b; \ + c ^= (b >> 15); \ + } /* The most generic version, hashes an arbitrary sequence * of bytes. No alignment or length assumptions are made about * the input key. */ -u_int32_t -jhash (const void *key, u_int32_t length, u_int32_t initval) +u_int32_t jhash(const void *key, u_int32_t length, u_int32_t initval) { - u_int32_t a, b, c, len; - const u_int8_t *k = key; - - len = length; - a = b = JHASH_GOLDEN_RATIO; - c = initval; - - while (len >= 12) - { - a += - (k[0] + ((u_int32_t) k[1] << 8) + ((u_int32_t) k[2] << 16) + - ((u_int32_t) k[3] << 24)); - b += - (k[4] + ((u_int32_t) k[5] << 8) + ((u_int32_t) k[6] << 16) + - ((u_int32_t) k[7] << 24)); - c += - (k[8] + ((u_int32_t) k[9] << 8) + ((u_int32_t) k[10] << 16) + - ((u_int32_t) k[11] << 24)); - - __jhash_mix (a, b, c); - - k += 12; - len -= 12; - } - - c += length; - switch (len) - { - case 11: - c += ((u_int32_t) k[10] << 24); - /* fallthru */ - case 10: - c += ((u_int32_t) k[9] << 16); - /* fallthru */ - case 9: - c += ((u_int32_t) k[8] << 8); - /* fallthru */ - case 8: - b += ((u_int32_t) k[7] << 24); - /* fallthru */ - case 7: - b += ((u_int32_t) k[6] << 16); - /* fallthru */ - case 6: - b += ((u_int32_t) k[5] << 8); - /* fallthru */ - case 5: - b += k[4]; - /* fallthru */ - case 4: - a += ((u_int32_t) k[3] << 24); - /* fallthru */ - case 3: - a += ((u_int32_t) k[2] << 16); - /* fallthru */ - case 2: - a += ((u_int32_t) k[1] << 8); - /* fallthru */ - case 1: - a += k[0]; - }; - - __jhash_mix (a, b, c); - - return c; + u_int32_t a, b, c, len; + const u_int8_t *k = key; + + len = length; + a = b = JHASH_GOLDEN_RATIO; + c = initval; + + while (len >= 12) { + a += (k[0] + ((u_int32_t)k[1] << 8) + ((u_int32_t)k[2] << 16) + + ((u_int32_t)k[3] << 24)); + b += (k[4] + ((u_int32_t)k[5] << 8) + ((u_int32_t)k[6] << 16) + + ((u_int32_t)k[7] << 24)); + c += (k[8] + ((u_int32_t)k[9] << 8) + ((u_int32_t)k[10] << 16) + + ((u_int32_t)k[11] << 24)); + + __jhash_mix(a, b, c); + + k += 12; + len -= 12; + } + + c += length; + switch (len) { + case 11: + c += ((u_int32_t)k[10] << 24); + /* fallthru */ + case 10: + c += ((u_int32_t)k[9] << 16); + /* fallthru */ + case 9: + c += ((u_int32_t)k[8] << 8); + /* fallthru */ + case 8: + b += ((u_int32_t)k[7] << 24); + /* fallthru */ + case 7: + b += ((u_int32_t)k[6] << 16); + /* fallthru */ + case 6: + b += ((u_int32_t)k[5] << 8); + /* fallthru */ + case 5: + b += k[4]; + /* fallthru */ + case 4: + a += ((u_int32_t)k[3] << 24); + /* fallthru */ + case 3: + a += ((u_int32_t)k[2] << 16); + /* fallthru */ + case 2: + a += ((u_int32_t)k[1] << 8); + /* fallthru */ + case 1: + a += k[0]; + }; + + __jhash_mix(a, b, c); + + return c; } /* A special optimized version that handles 1 or more of u_int32_ts. * The length parameter here is the number of u_int32_ts in the key. */ -u_int32_t -jhash2 (const u_int32_t *k, u_int32_t length, u_int32_t initval) +u_int32_t jhash2(const u_int32_t *k, u_int32_t length, u_int32_t initval) { - u_int32_t a, b, c, len; - - a = b = JHASH_GOLDEN_RATIO; - c = initval; - len = length; - - while (len >= 3) - { - a += k[0]; - b += k[1]; - c += k[2]; - __jhash_mix (a, b, c); - k += 3; - len -= 3; - } - - c += length * 4; - - switch (len) - { - case 2: - b += k[1]; - /* fallthru */ - case 1: - a += k[0]; - }; - - __jhash_mix (a, b, c); - - return c; + u_int32_t a, b, c, len; + + a = b = JHASH_GOLDEN_RATIO; + c = initval; + len = length; + + while (len >= 3) { + a += k[0]; + b += k[1]; + c += k[2]; + __jhash_mix(a, b, c); + k += 3; + len -= 3; + } + + c += length * 4; + + switch (len) { + case 2: + b += k[1]; + /* fallthru */ + case 1: + a += k[0]; + }; + + __jhash_mix(a, b, c); + + return c; } @@ -156,26 +165,23 @@ jhash2 (const u_int32_t *k, u_int32_t length, u_int32_t initval) * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally * done at the end is not done here. */ -u_int32_t -jhash_3words (u_int32_t a, u_int32_t b, u_int32_t c, u_int32_t initval) +u_int32_t jhash_3words(u_int32_t a, u_int32_t b, u_int32_t c, u_int32_t initval) { - a += JHASH_GOLDEN_RATIO; - b += JHASH_GOLDEN_RATIO; - c += initval; + a += JHASH_GOLDEN_RATIO; + b += JHASH_GOLDEN_RATIO; + c += initval; - __jhash_mix (a, b, c); + __jhash_mix(a, b, c); - return c; + return c; } -u_int32_t -jhash_2words (u_int32_t a, u_int32_t b, u_int32_t initval) +u_int32_t jhash_2words(u_int32_t a, u_int32_t b, u_int32_t initval) { - return jhash_3words (a, b, 0, initval); + return jhash_3words(a, b, 0, initval); } -u_int32_t -jhash_1word (u_int32_t a, u_int32_t initval) +u_int32_t jhash_1word(u_int32_t a, u_int32_t initval) { - return jhash_3words (a, 0, 0, initval); + return jhash_3words(a, 0, 0, initval); } |