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