jhash.h revision 289644
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 21289644Shselasky * 22289633Shselasky * $FreeBSD: head/sys/ofed/include/linux/jhash.h 289644 2015-10-20 19:08:26Z hselasky $ 23219820Sjeff */ 24219820Sjeff 25219820Sjeff/* NOTE: Arguments are modified. */ 26219820Sjeff#define __jhash_mix(a, b, c) \ 27219820Sjeff{ \ 28219820Sjeff a -= b; a -= c; a ^= (c>>13); \ 29219820Sjeff b -= c; b -= a; b ^= (a<<8); \ 30219820Sjeff c -= a; c -= b; c ^= (b>>13); \ 31219820Sjeff a -= b; a -= c; a ^= (c>>12); \ 32219820Sjeff b -= c; b -= a; b ^= (a<<16); \ 33219820Sjeff c -= a; c -= b; c ^= (b>>5); \ 34219820Sjeff a -= b; a -= c; a ^= (c>>3); \ 35219820Sjeff b -= c; b -= a; b ^= (a<<10); \ 36219820Sjeff c -= a; c -= b; c ^= (b>>15); \ 37219820Sjeff} 38219820Sjeff 39219820Sjeff/* The golden ration: an arbitrary value */ 40219820Sjeff#define JHASH_GOLDEN_RATIO 0x9e3779b9 41219820Sjeff 42219820Sjeff/* The most generic version, hashes an arbitrary sequence 43219820Sjeff * of bytes. No alignment or length assumptions are made about 44219820Sjeff * the input key. 45219820Sjeff */ 46219820Sjeffstatic inline u32 jhash(const void *key, u32 length, u32 initval) 47219820Sjeff{ 48219820Sjeff u32 a, b, c, len; 49219820Sjeff const u8 *k = key; 50219820Sjeff 51219820Sjeff len = length; 52219820Sjeff a = b = JHASH_GOLDEN_RATIO; 53219820Sjeff c = initval; 54219820Sjeff 55219820Sjeff while (len >= 12) { 56219820Sjeff a += (k[0] +((u32)k[1]<<8) +((u32)k[2]<<16) +((u32)k[3]<<24)); 57219820Sjeff b += (k[4] +((u32)k[5]<<8) +((u32)k[6]<<16) +((u32)k[7]<<24)); 58219820Sjeff c += (k[8] +((u32)k[9]<<8) +((u32)k[10]<<16)+((u32)k[11]<<24)); 59219820Sjeff 60219820Sjeff __jhash_mix(a,b,c); 61219820Sjeff 62219820Sjeff k += 12; 63219820Sjeff len -= 12; 64219820Sjeff } 65219820Sjeff 66219820Sjeff c += length; 67219820Sjeff switch (len) { 68219820Sjeff case 11: c += ((u32)k[10]<<24); 69219820Sjeff case 10: c += ((u32)k[9]<<16); 70219820Sjeff case 9 : c += ((u32)k[8]<<8); 71219820Sjeff case 8 : b += ((u32)k[7]<<24); 72219820Sjeff case 7 : b += ((u32)k[6]<<16); 73219820Sjeff case 6 : b += ((u32)k[5]<<8); 74219820Sjeff case 5 : b += k[4]; 75219820Sjeff case 4 : a += ((u32)k[3]<<24); 76219820Sjeff case 3 : a += ((u32)k[2]<<16); 77219820Sjeff case 2 : a += ((u32)k[1]<<8); 78219820Sjeff case 1 : a += k[0]; 79219820Sjeff }; 80219820Sjeff 81219820Sjeff __jhash_mix(a,b,c); 82219820Sjeff 83219820Sjeff return c; 84219820Sjeff} 85219820Sjeff 86219820Sjeff/* A special optimized version that handles 1 or more of u32s. 87219820Sjeff * The length parameter here is the number of u32s in the key. 88219820Sjeff */ 89219820Sjeffstatic inline u32 jhash2(const u32 *k, u32 length, u32 initval) 90219820Sjeff{ 91219820Sjeff u32 a, b, c, len; 92219820Sjeff 93219820Sjeff a = b = JHASH_GOLDEN_RATIO; 94219820Sjeff c = initval; 95219820Sjeff len = length; 96219820Sjeff 97219820Sjeff while (len >= 3) { 98219820Sjeff a += k[0]; 99219820Sjeff b += k[1]; 100219820Sjeff c += k[2]; 101219820Sjeff __jhash_mix(a, b, c); 102219820Sjeff k += 3; len -= 3; 103219820Sjeff } 104219820Sjeff 105219820Sjeff c += length * 4; 106219820Sjeff 107219820Sjeff switch (len) { 108219820Sjeff case 2 : b += k[1]; 109219820Sjeff case 1 : a += k[0]; 110219820Sjeff }; 111219820Sjeff 112219820Sjeff __jhash_mix(a,b,c); 113219820Sjeff 114219820Sjeff return c; 115219820Sjeff} 116219820Sjeff 117219820Sjeff 118219820Sjeff/* A special ultra-optimized versions that knows they are hashing exactly 119219820Sjeff * 3, 2 or 1 word(s). 120219820Sjeff * 121219820Sjeff * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally 122219820Sjeff * done at the end is not done here. 123219820Sjeff */ 124219820Sjeffstatic inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval) 125219820Sjeff{ 126219820Sjeff a += JHASH_GOLDEN_RATIO; 127219820Sjeff b += JHASH_GOLDEN_RATIO; 128219820Sjeff c += initval; 129219820Sjeff 130219820Sjeff __jhash_mix(a, b, c); 131219820Sjeff 132219820Sjeff return c; 133219820Sjeff} 134219820Sjeff 135219820Sjeffstatic inline u32 jhash_2words(u32 a, u32 b, u32 initval) 136219820Sjeff{ 137219820Sjeff return jhash_3words(a, b, 0, initval); 138219820Sjeff} 139219820Sjeff 140219820Sjeffstatic inline u32 jhash_1word(u32 a, u32 initval) 141219820Sjeff{ 142219820Sjeff return jhash_3words(a, 0, 0, initval); 143219820Sjeff} 144219820Sjeff 145219820Sjeff#endif /* _LINUX_JHASH_H_ */ 146