jhash.h revision 169978
1169978Skmacy#ifndef _JHASH_H 2169978Skmacy#define _JHASH_H 3169978Skmacy 4169978Skmacy/* jhash.h: Jenkins hash support. 5169978Skmacy * 6169978Skmacy * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net) 7169978Skmacy * 8169978Skmacy * http://burtleburtle.net/bob/hash/ 9169978Skmacy * 10169978Skmacy * These are the credits from Bob's sources: 11169978Skmacy * 12169978Skmacy * lookup2.c, by Bob Jenkins, December 1996, Public Domain. 13169978Skmacy * hash(), hash2(), hash3, and mix() are externally useful functions. 14169978Skmacy * Routines to test the hash are included if SELF_TEST is defined. 15169978Skmacy * You can use this free for any purpose. It has no warranty. 16169978Skmacy * 17169978Skmacy * $FreeBSD: head/sys/dev/cxgb/common/jhash.h 169978 2007-05-25 09:48:20Z kmacy $ 18169978Skmacy */ 19169978Skmacy 20169978Skmacy/* NOTE: Arguments are modified. */ 21169978Skmacy#define __jhash_mix(a, b, c) \ 22169978Skmacy{ \ 23169978Skmacy a -= b; a -= c; a ^= (c>>13); \ 24169978Skmacy b -= c; b -= a; b ^= (a<<8); \ 25169978Skmacy c -= a; c -= b; c ^= (b>>13); \ 26169978Skmacy a -= b; a -= c; a ^= (c>>12); \ 27169978Skmacy b -= c; b -= a; b ^= (a<<16); \ 28169978Skmacy c -= a; c -= b; c ^= (b>>5); \ 29169978Skmacy a -= b; a -= c; a ^= (c>>3); \ 30169978Skmacy b -= c; b -= a; b ^= (a<<10); \ 31169978Skmacy c -= a; c -= b; c ^= (b>>15); \ 32169978Skmacy} 33169978Skmacy 34169978Skmacy/* The golden ration: an arbitrary value */ 35169978Skmacy#define JHASH_GOLDEN_RATIO 0x9e3779b9 36169978Skmacy 37169978Skmacy/* The most generic version, hashes an arbitrary sequence 38169978Skmacy * of bytes. No alignment or length assumptions are made about 39169978Skmacy * the input key. 40169978Skmacy */ 41169978Skmacystatic inline u32 jhash(const void *key, u32 length, u32 initval) 42169978Skmacy{ 43169978Skmacy u32 a, b, c, len; 44169978Skmacy const u8 *k = key; 45169978Skmacy 46169978Skmacy len = length; 47169978Skmacy a = b = JHASH_GOLDEN_RATIO; 48169978Skmacy c = initval; 49169978Skmacy 50169978Skmacy while (len >= 12) { 51169978Skmacy a += (k[0] +((u32)k[1]<<8) +((u32)k[2]<<16) +((u32)k[3]<<24)); 52169978Skmacy b += (k[4] +((u32)k[5]<<8) +((u32)k[6]<<16) +((u32)k[7]<<24)); 53169978Skmacy c += (k[8] +((u32)k[9]<<8) +((u32)k[10]<<16)+((u32)k[11]<<24)); 54169978Skmacy 55169978Skmacy __jhash_mix(a,b,c); 56169978Skmacy 57169978Skmacy k += 12; 58169978Skmacy len -= 12; 59169978Skmacy } 60169978Skmacy 61169978Skmacy c += length; 62169978Skmacy switch (len) { 63169978Skmacy case 11: c += ((u32)k[10]<<24); 64169978Skmacy case 10: c += ((u32)k[9]<<16); 65169978Skmacy case 9 : c += ((u32)k[8]<<8); 66169978Skmacy case 8 : b += ((u32)k[7]<<24); 67169978Skmacy case 7 : b += ((u32)k[6]<<16); 68169978Skmacy case 6 : b += ((u32)k[5]<<8); 69169978Skmacy case 5 : b += k[4]; 70169978Skmacy case 4 : a += ((u32)k[3]<<24); 71169978Skmacy case 3 : a += ((u32)k[2]<<16); 72169978Skmacy case 2 : a += ((u32)k[1]<<8); 73169978Skmacy case 1 : a += k[0]; 74169978Skmacy }; 75169978Skmacy 76169978Skmacy __jhash_mix(a,b,c); 77169978Skmacy 78169978Skmacy return c; 79169978Skmacy} 80169978Skmacy 81169978Skmacy/* A special optimized version that handles 1 or more of u32s. 82169978Skmacy * The length parameter here is the number of u32s in the key. 83169978Skmacy */ 84169978Skmacystatic inline u32 jhash2(u32 *k, u32 length, u32 initval) 85169978Skmacy{ 86169978Skmacy u32 a, b, c, len; 87169978Skmacy 88169978Skmacy a = b = JHASH_GOLDEN_RATIO; 89169978Skmacy c = initval; 90169978Skmacy len = length; 91169978Skmacy 92169978Skmacy while (len >= 3) { 93169978Skmacy a += k[0]; 94169978Skmacy b += k[1]; 95169978Skmacy c += k[2]; 96169978Skmacy __jhash_mix(a, b, c); 97169978Skmacy k += 3; len -= 3; 98169978Skmacy } 99169978Skmacy 100169978Skmacy c += length * 4; 101169978Skmacy 102169978Skmacy switch (len) { 103169978Skmacy case 2 : b += k[1]; 104169978Skmacy case 1 : a += k[0]; 105169978Skmacy }; 106169978Skmacy 107169978Skmacy __jhash_mix(a,b,c); 108169978Skmacy 109169978Skmacy return c; 110169978Skmacy} 111169978Skmacy 112169978Skmacy 113169978Skmacy/* A special ultra-optimized versions that knows they are hashing exactly 114169978Skmacy * 3, 2 or 1 word(s). 115169978Skmacy * 116169978Skmacy * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally 117169978Skmacy * done at the end is not done here. 118169978Skmacy */ 119169978Skmacystatic inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval) 120169978Skmacy{ 121169978Skmacy a += JHASH_GOLDEN_RATIO; 122169978Skmacy b += JHASH_GOLDEN_RATIO; 123169978Skmacy c += initval; 124169978Skmacy 125169978Skmacy __jhash_mix(a, b, c); 126169978Skmacy 127169978Skmacy return c; 128169978Skmacy} 129169978Skmacy 130169978Skmacystatic inline u32 jhash_2words(u32 a, u32 b, u32 initval) 131169978Skmacy{ 132169978Skmacy return jhash_3words(a, b, 0, initval); 133169978Skmacy} 134169978Skmacy 135169978Skmacystatic inline u32 jhash_1word(u32 a, u32 initval) 136169978Skmacy{ 137169978Skmacy return jhash_3words(a, 0, 0, initval); 138169978Skmacy} 139169978Skmacy 140169978Skmacy#endif /* _JHASH_H */ 141