projects / mirror_frr.git / blame
| Commit | Line | Data |
|---|---|---|
| b9790b34 | 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. */ | |
| d62a17ae | 27 | #define __jhash_mix(a, b, c) \ |
| 28 | { \ | |
| 29 | a -= b; \ | |
| 30 | a -= c; \ | |
| 31 | a ^= (c >> 13); \ | |
| 32 | b -= c; \ | |
| 33 | b -= a; \ | |
| 34 | b ^= (a << 8); \ | |
| 35 | c -= a; \ | |
| 36 | c -= b; \ | |
| 37 | c ^= (b >> 13); \ | |
| 38 | a -= b; \ | |
| 39 | a -= c; \ | |
| 40 | a ^= (c >> 12); \ | |
| 41 | b -= c; \ | |
| 42 | b -= a; \ | |
| 43 | b ^= (a << 16); \ | |
| 44 | c -= a; \ | |
| 45 | c -= b; \ | |
| 46 | c ^= (b >> 5); \ | |
| 47 | a -= b; \ | |
| 48 | a -= c; \ | |
| 49 | a ^= (c >> 3); \ | |
| 50 | b -= c; \ | |
| 51 | b -= a; \ | |
| 52 | b ^= (a << 10); \ | |
| 53 | c -= a; \ | |
| 54 | c -= b; \ | |
| 55 | c ^= (b >> 15); \ | |
| 56 | } | |
| b9790b34 | 57 | |
| 58 | /* The most generic version, hashes an arbitrary sequence | |
| 59 | * of bytes. No alignment or length assumptions are made about | |
| 60 | * the input key. | |
| 61 | */ | |
| d7c0a89a | 62 | uint32_t jhash(const void *key, uint32_t length, uint32_t initval) |
| b9790b34 | 63 | { |
| d7c0a89a QY |
64 | uint32_t a, b, c, len; |
| 65 | const uint8_t *k = key; | |
| d62a17ae | 66 | |
| 67 | len = length; | |
| 68 | a = b = JHASH_GOLDEN_RATIO; | |
| 69 | c = initval; | |
| 70 | ||
| 71 | while (len >= 12) { | |
| d7c0a89a QY |
72 | a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16) |
| 73 | + ((uint32_t)k[3] << 24)); | |
| 74 | b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16) | |
| 75 | + ((uint32_t)k[7] << 24)); | |
| 76 | c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16) | |
| 77 | + ((uint32_t)k[11] << 24)); | |
| d62a17ae | 78 | |
| 79 | __jhash_mix(a, b, c); | |
| 80 | ||
| 81 | k += 12; | |
| 82 | len -= 12; | |
| 83 | } | |
| 84 | ||
| 85 | c += length; | |
| 86 | switch (len) { | |
| 87 | case 11: | |
| d7c0a89a | 88 | c += ((uint32_t)k[10] << 24); |
| d62a17ae | 89 | /* fallthru */ |
| 90 | case 10: | |
| d7c0a89a | 91 | c += ((uint32_t)k[9] << 16); |
| d62a17ae | 92 | /* fallthru */ |
| 93 | case 9: | |
| d7c0a89a | 94 | c += ((uint32_t)k[8] << 8); |
| d62a17ae | 95 | /* fallthru */ |
| 96 | case 8: | |
| d7c0a89a | 97 | b += ((uint32_t)k[7] << 24); |
| d62a17ae | 98 | /* fallthru */ |
| 99 | case 7: | |
| d7c0a89a | 100 | b += ((uint32_t)k[6] << 16); |
| d62a17ae | 101 | /* fallthru */ |
| 102 | case 6: | |
| d7c0a89a | 103 | b += ((uint32_t)k[5] << 8); |
| d62a17ae | 104 | /* fallthru */ |
| 105 | case 5: | |
| 106 | b += k[4]; | |
| 107 | /* fallthru */ | |
| 108 | case 4: | |
| d7c0a89a | 109 | a += ((uint32_t)k[3] << 24); |
| d62a17ae | 110 | /* fallthru */ |
| 111 | case 3: | |
| d7c0a89a | 112 | a += ((uint32_t)k[2] << 16); |
| d62a17ae | 113 | /* fallthru */ |
| 114 | case 2: | |
| d7c0a89a | 115 | a += ((uint32_t)k[1] << 8); |
| d62a17ae | 116 | /* fallthru */ |
| 117 | case 1: | |
| 118 | a += k[0]; | |
| 119 | }; | |
| 120 | ||
| 121 | __jhash_mix(a, b, c); | |
| 122 | ||
| 123 | return c; | |
| b9790b34 | 124 | } |
| 125 | ||
| d7c0a89a QY |
126 | /* A special optimized version that handles 1 or more of uint32_ts. |
| 127 | * The length parameter here is the number of uint32_ts in the key. | |
| b9790b34 | 128 | */ |
| d7c0a89a | 129 | uint32_t jhash2(const uint32_t *k, uint32_t length, uint32_t initval) |
| b9790b34 | 130 | { |
| d7c0a89a | 131 | uint32_t a, b, c, len; |
| d62a17ae | 132 | |
| 133 | a = b = JHASH_GOLDEN_RATIO; | |
| 134 | c = initval; | |
| 135 | len = length; | |
| 136 | ||
| 137 | while (len >= 3) { | |
| 138 | a += k[0]; | |
| 139 | b += k[1]; | |
| 140 | c += k[2]; | |
| 141 | __jhash_mix(a, b, c); | |
| 142 | k += 3; | |
| 143 | len -= 3; | |
| 144 | } | |
| 145 | ||
| 146 | c += length * 4; | |
| 147 | ||
| 148 | switch (len) { | |
| 149 | case 2: | |
| 150 | b += k[1]; | |
| 151 | /* fallthru */ | |
| 152 | case 1: | |
| 153 | a += k[0]; | |
| 154 | }; | |
| 155 | ||
| 156 | __jhash_mix(a, b, c); | |
| 157 | ||
| 158 | return c; | |
| b9790b34 | 159 | } |
| 160 | ||
| 161 | ||
| 162 | /* A special ultra-optimized versions that knows they are hashing exactly | |
| 163 | * 3, 2 or 1 word(s). | |
| 164 | * | |
| 165 | * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally | |
| 166 | * done at the end is not done here. | |
| 167 | */ | |
| d7c0a89a | 168 | uint32_t jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval) |
| b9790b34 | 169 | { |
| d62a17ae | 170 | a += JHASH_GOLDEN_RATIO; |
| 171 | b += JHASH_GOLDEN_RATIO; | |
| 172 | c += initval; | |
| b9790b34 | 173 | |
| d62a17ae | 174 | __jhash_mix(a, b, c); |
| b9790b34 | 175 | |
| d62a17ae | 176 | return c; |
| b9790b34 | 177 | } |
| 178 | ||
| d7c0a89a | 179 | uint32_t jhash_2words(uint32_t a, uint32_t b, uint32_t initval) |
| b9790b34 | 180 | { |
| d62a17ae | 181 | return jhash_3words(a, b, 0, initval); |
| b9790b34 | 182 | } |
| 183 | ||
| d7c0a89a | 184 | uint32_t jhash_1word(uint32_t a, uint32_t initval) |
| b9790b34 | 185 | { |
| d62a17ae | 186 | return jhash_3words(a, 0, 0, initval); |
| b9790b34 | 187 | } |