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