jhash.h revision 219820
1#ifndef _LINUX_JHASH_H_ 2#define _LINUX_JHASH_H_ 3 4/* jhash.h: Jenkins hash support. 5 * 6 * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net) 7 * 8 * http://burtleburtle.net/bob/hash/ 9 * 10 * These are the credits from Bob's sources: 11 * 12 * lookup2.c, by Bob Jenkins, December 1996, Public Domain. 13 * hash(), hash2(), hash3, and mix() are externally useful functions. 14 * Routines to test the hash are included if SELF_TEST is defined. 15 * You can use this free for any purpose. It has no warranty. 16 * 17 * Copyright (C) 2003 David S. Miller (davem@redhat.com) 18 * 19 * I've modified Bob's hash to be useful in the Linux kernel, and 20 * any bugs present are surely my fault. -DaveM 21 */ 22 23/* NOTE: Arguments are modified. */ 24#define __jhash_mix(a, b, c) \ 25{ \ 26 a -= b; a -= c; a ^= (c>>13); \ 27 b -= c; b -= a; b ^= (a<<8); \ 28 c -= a; c -= b; c ^= (b>>13); \ 29 a -= b; a -= c; a ^= (c>>12); \ 30 b -= c; b -= a; b ^= (a<<16); \ 31 c -= a; c -= b; c ^= (b>>5); \ 32 a -= b; a -= c; a ^= (c>>3); \ 33 b -= c; b -= a; b ^= (a<<10); \ 34 c -= a; c -= b; c ^= (b>>15); \ 35} 36 37/* The golden ration: an arbitrary value */ 38#define JHASH_GOLDEN_RATIO 0x9e3779b9 39 40/* The most generic version, hashes an arbitrary sequence 41 * of bytes. No alignment or length assumptions are made about 42 * the input key. 43 */ 44static inline u32 jhash(const void *key, u32 length, u32 initval) 45{ 46 u32 a, b, c, len; 47 const u8 *k = key; 48 49 len = length; 50 a = b = JHASH_GOLDEN_RATIO; 51 c = initval; 52 53 while (len >= 12) { 54 a += (k[0] +((u32)k[1]<<8) +((u32)k[2]<<16) +((u32)k[3]<<24)); 55 b += (k[4] +((u32)k[5]<<8) +((u32)k[6]<<16) +((u32)k[7]<<24)); 56 c += (k[8] +((u32)k[9]<<8) +((u32)k[10]<<16)+((u32)k[11]<<24)); 57 58 __jhash_mix(a,b,c); 59 60 k += 12; 61 len -= 12; 62 } 63 64 c += length; 65 switch (len) { 66 case 11: c += ((u32)k[10]<<24); 67 case 10: c += ((u32)k[9]<<16); 68 case 9 : c += ((u32)k[8]<<8); 69 case 8 : b += ((u32)k[7]<<24); 70 case 7 : b += ((u32)k[6]<<16); 71 case 6 : b += ((u32)k[5]<<8); 72 case 5 : b += k[4]; 73 case 4 : a += ((u32)k[3]<<24); 74 case 3 : a += ((u32)k[2]<<16); 75 case 2 : a += ((u32)k[1]<<8); 76 case 1 : a += k[0]; 77 }; 78 79 __jhash_mix(a,b,c); 80 81 return c; 82} 83 84/* A special optimized version that handles 1 or more of u32s. 85 * The length parameter here is the number of u32s in the key. 86 */ 87static inline u32 jhash2(const u32 *k, u32 length, u32 initval) 88{ 89 u32 a, b, c, len; 90 91 a = b = JHASH_GOLDEN_RATIO; 92 c = initval; 93 len = length; 94 95 while (len >= 3) { 96 a += k[0]; 97 b += k[1]; 98 c += k[2]; 99 __jhash_mix(a, b, c); 100 k += 3; len -= 3; 101 } 102 103 c += length * 4; 104 105 switch (len) { 106 case 2 : b += k[1]; 107 case 1 : a += k[0]; 108 }; 109 110 __jhash_mix(a,b,c); 111 112 return c; 113} 114 115 116/* A special ultra-optimized versions that knows they are hashing exactly 117 * 3, 2 or 1 word(s). 118 * 119 * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally 120 * done at the end is not done here. 121 */ 122static inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval) 123{ 124 a += JHASH_GOLDEN_RATIO; 125 b += JHASH_GOLDEN_RATIO; 126 c += initval; 127 128 __jhash_mix(a, b, c); 129 130 return c; 131} 132 133static inline u32 jhash_2words(u32 a, u32 b, u32 initval) 134{ 135 return jhash_3words(a, b, 0, initval); 136} 137 138static inline u32 jhash_1word(u32 a, u32 initval) 139{ 140 return jhash_3words(a, 0, 0, initval); 141} 142 143#endif /* _LINUX_JHASH_H_ */ 144