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