jhash.h revision 219820
1219820Sjeff#ifndef _LINUX_JHASH_H_ 2219820Sjeff#define _LINUX_JHASH_H_ 3219820Sjeff 4219820Sjeff/* jhash.h: Jenkins hash support. 5219820Sjeff * 6219820Sjeff * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net) 7219820Sjeff * 8219820Sjeff * http://burtleburtle.net/bob/hash/ 9219820Sjeff * 10219820Sjeff * These are the credits from Bob's sources: 11219820Sjeff * 12219820Sjeff * lookup2.c, by Bob Jenkins, December 1996, Public Domain. 13219820Sjeff * hash(), hash2(), hash3, and mix() are externally useful functions. 14219820Sjeff * Routines to test the hash are included if SELF_TEST is defined. 15219820Sjeff * You can use this free for any purpose. It has no warranty. 16219820Sjeff * 17219820Sjeff * Copyright (C) 2003 David S. Miller (davem@redhat.com) 18219820Sjeff * 19219820Sjeff * I've modified Bob's hash to be useful in the Linux kernel, and 20219820Sjeff * any bugs present are surely my fault. -DaveM 21219820Sjeff */ 22219820Sjeff 23219820Sjeff/* NOTE: Arguments are modified. */ 24219820Sjeff#define __jhash_mix(a, b, c) \ 25219820Sjeff{ \ 26219820Sjeff a -= b; a -= c; a ^= (c>>13); \ 27219820Sjeff b -= c; b -= a; b ^= (a<<8); \ 28219820Sjeff c -= a; c -= b; c ^= (b>>13); \ 29219820Sjeff a -= b; a -= c; a ^= (c>>12); \ 30219820Sjeff b -= c; b -= a; b ^= (a<<16); \ 31219820Sjeff c -= a; c -= b; c ^= (b>>5); \ 32219820Sjeff a -= b; a -= c; a ^= (c>>3); \ 33219820Sjeff b -= c; b -= a; b ^= (a<<10); \ 34219820Sjeff c -= a; c -= b; c ^= (b>>15); \ 35219820Sjeff} 36219820Sjeff 37219820Sjeff/* The golden ration: an arbitrary value */ 38219820Sjeff#define JHASH_GOLDEN_RATIO 0x9e3779b9 39219820Sjeff 40219820Sjeff/* The most generic version, hashes an arbitrary sequence 41219820Sjeff * of bytes. No alignment or length assumptions are made about 42219820Sjeff * the input key. 43219820Sjeff */ 44219820Sjeffstatic inline u32 jhash(const void *key, u32 length, u32 initval) 45219820Sjeff{ 46219820Sjeff u32 a, b, c, len; 47219820Sjeff const u8 *k = key; 48219820Sjeff 49219820Sjeff len = length; 50219820Sjeff a = b = JHASH_GOLDEN_RATIO; 51219820Sjeff c = initval; 52219820Sjeff 53219820Sjeff while (len >= 12) { 54219820Sjeff a += (k[0] +((u32)k[1]<<8) +((u32)k[2]<<16) +((u32)k[3]<<24)); 55219820Sjeff b += (k[4] +((u32)k[5]<<8) +((u32)k[6]<<16) +((u32)k[7]<<24)); 56219820Sjeff c += (k[8] +((u32)k[9]<<8) +((u32)k[10]<<16)+((u32)k[11]<<24)); 57219820Sjeff 58219820Sjeff __jhash_mix(a,b,c); 59219820Sjeff 60219820Sjeff k += 12; 61219820Sjeff len -= 12; 62219820Sjeff } 63219820Sjeff 64219820Sjeff c += length; 65219820Sjeff switch (len) { 66219820Sjeff case 11: c += ((u32)k[10]<<24); 67219820Sjeff case 10: c += ((u32)k[9]<<16); 68219820Sjeff case 9 : c += ((u32)k[8]<<8); 69219820Sjeff case 8 : b += ((u32)k[7]<<24); 70219820Sjeff case 7 : b += ((u32)k[6]<<16); 71219820Sjeff case 6 : b += ((u32)k[5]<<8); 72219820Sjeff case 5 : b += k[4]; 73219820Sjeff case 4 : a += ((u32)k[3]<<24); 74219820Sjeff case 3 : a += ((u32)k[2]<<16); 75219820Sjeff case 2 : a += ((u32)k[1]<<8); 76219820Sjeff case 1 : a += k[0]; 77219820Sjeff }; 78219820Sjeff 79219820Sjeff __jhash_mix(a,b,c); 80219820Sjeff 81219820Sjeff return c; 82219820Sjeff} 83219820Sjeff 84219820Sjeff/* A special optimized version that handles 1 or more of u32s. 85219820Sjeff * The length parameter here is the number of u32s in the key. 86219820Sjeff */ 87219820Sjeffstatic inline u32 jhash2(const u32 *k, u32 length, u32 initval) 88219820Sjeff{ 89219820Sjeff u32 a, b, c, len; 90219820Sjeff 91219820Sjeff a = b = JHASH_GOLDEN_RATIO; 92219820Sjeff c = initval; 93219820Sjeff len = length; 94219820Sjeff 95219820Sjeff while (len >= 3) { 96219820Sjeff a += k[0]; 97219820Sjeff b += k[1]; 98219820Sjeff c += k[2]; 99219820Sjeff __jhash_mix(a, b, c); 100219820Sjeff k += 3; len -= 3; 101219820Sjeff } 102219820Sjeff 103219820Sjeff c += length * 4; 104219820Sjeff 105219820Sjeff switch (len) { 106219820Sjeff case 2 : b += k[1]; 107219820Sjeff case 1 : a += k[0]; 108219820Sjeff }; 109219820Sjeff 110219820Sjeff __jhash_mix(a,b,c); 111219820Sjeff 112219820Sjeff return c; 113219820Sjeff} 114219820Sjeff 115219820Sjeff 116219820Sjeff/* A special ultra-optimized versions that knows they are hashing exactly 117219820Sjeff * 3, 2 or 1 word(s). 118219820Sjeff * 119219820Sjeff * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally 120219820Sjeff * done at the end is not done here. 121219820Sjeff */ 122219820Sjeffstatic inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval) 123219820Sjeff{ 124219820Sjeff a += JHASH_GOLDEN_RATIO; 125219820Sjeff b += JHASH_GOLDEN_RATIO; 126219820Sjeff c += initval; 127219820Sjeff 128219820Sjeff __jhash_mix(a, b, c); 129219820Sjeff 130219820Sjeff return c; 131219820Sjeff} 132219820Sjeff 133219820Sjeffstatic inline u32 jhash_2words(u32 a, u32 b, u32 initval) 134219820Sjeff{ 135219820Sjeff return jhash_3words(a, b, 0, initval); 136219820Sjeff} 137219820Sjeff 138219820Sjeffstatic inline u32 jhash_1word(u32 a, u32 initval) 139219820Sjeff{ 140219820Sjeff return jhash_3words(a, 0, 0, initval); 141219820Sjeff} 142219820Sjeff 143219820Sjeff#endif /* _LINUX_JHASH_H_ */ 144