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