diff options
author | Andrew Mahone <andrew.mahone@gmail.com> | 2009-06-01 13:40:30 +0000 |
---|---|---|
committer | Andrew Mahone <andrew.mahone@gmail.com> | 2009-06-01 13:40:30 +0000 |
commit | e0f4eafb689e75d66b34c40592024c1e698b0836 (patch) | |
tree | 9f410d5972df06328504bc803ca58cd4eb53cb9a /apps | |
parent | cb7f0099288786b3d4a80a2e36edbd55f3fcc028 (diff) | |
download | rockbox-e0f4eafb689e75d66b34c40592024c1e698b0836.tar.gz rockbox-e0f4eafb689e75d66b34c40592024c1e698b0836.zip |
Add Bob Jenkins' lookup3 32-bit and 64-bit hashes to pluginlib.
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@21155 a1c6a512-1295-4272-9138-f99709370657
Diffstat (limited to 'apps')
-rw-r--r-- | apps/plugins/lib/SOURCES | 1 | ||||
-rw-r--r-- | apps/plugins/lib/jhash.c | 699 | ||||
-rw-r--r-- | apps/plugins/lib/jhash.h | 67 |
3 files changed, 767 insertions, 0 deletions
diff --git a/apps/plugins/lib/SOURCES b/apps/plugins/lib/SOURCES index 21a35d478a..5a6abc7848 100644 --- a/apps/plugins/lib/SOURCES +++ b/apps/plugins/lib/SOURCES | |||
@@ -1,4 +1,5 @@ | |||
1 | gcc-support.c | 1 | gcc-support.c |
2 | jhash.c | ||
2 | oldmenuapi.c | 3 | oldmenuapi.c |
3 | configfile.c | 4 | configfile.c |
4 | fixedpoint.c | 5 | fixedpoint.c |
diff --git a/apps/plugins/lib/jhash.c b/apps/plugins/lib/jhash.c new file mode 100644 index 0000000000..780d220408 --- /dev/null +++ b/apps/plugins/lib/jhash.c | |||
@@ -0,0 +1,699 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2006 Bob Jenkins | ||
11 | * http://burtleburtle.net/bob/c/lookup3.c | ||
12 | * | ||
13 | * This program is free software; you can redistribute it and/or | ||
14 | * modify it under the terms of the GNU General Public License | ||
15 | * as published by the Free Software Foundation; either version 2 | ||
16 | * of the License, or (at your option) any later version. | ||
17 | * | ||
18 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
19 | * KIND, either express or implied. | ||
20 | * | ||
21 | ****************************************************************************/ | ||
22 | /* | ||
23 | lookup3.c, by Bob Jenkins, May 2006, Public Domain. | ||
24 | |||
25 | These are functions for producing 32-bit hashes for hash table lookup. | ||
26 | hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() | ||
27 | are externally useful functions. Routines to test the hash are included | ||
28 | if SELF_TEST is defined. You can use this free for any purpose. It's in | ||
29 | the public domain. It has no warranty. | ||
30 | |||
31 | You probably want to use hashlittle(). hashlittle() and hashbig() | ||
32 | hash byte arrays. hashlittle() is is faster than hashbig() on | ||
33 | little-endian machines. Intel and AMD are little-endian machines. | ||
34 | On second thought, you probably want hashlittle2(), which is identical to | ||
35 | hashlittle() except it returns two 32-bit hashes for the price of one. | ||
36 | You could implement hashbig2() if you wanted but I haven't bothered here. | ||
37 | |||
38 | If you want to find a hash of, say, exactly 7 integers, do | ||
39 | a = i1; b = i2; c = i3; | ||
40 | mix(a,b,c); | ||
41 | a += i4; b += i5; c += i6; | ||
42 | mix(a,b,c); | ||
43 | a += i7; | ||
44 | final(a,b,c); | ||
45 | then use c as the hash value. If you have a variable length array of | ||
46 | 4-byte integers to hash, use hashword(). If you have a byte array (like | ||
47 | a character string), use hashlittle(). If you have several byte arrays, or | ||
48 | a mix of things, see the comments above hashlittle(). | ||
49 | |||
50 | Why is this so big? I read 12 bytes at a time into 3 4-byte integers, | ||
51 | then mix those integers. This is fast (you can do a lot more thorough | ||
52 | mixing with 12*3 instructions on 3 integers than you can with 3 instructions | ||
53 | on 1 byte), but shoehorning those bytes into integers efficiently is messy. | ||
54 | */ | ||
55 | |||
56 | #include "jhash.h" | ||
57 | |||
58 | /* | ||
59 | * My best guess at if you are big-endian or little-endian. This may | ||
60 | * need adjustment. | ||
61 | */ | ||
62 | #if defined(ROCKBOX_LITTLE_ENDIAN) | ||
63 | # define HASH_LITTLE_ENDIAN 1 | ||
64 | # define HASH_BIG_ENDIAN 0 | ||
65 | #elif defined(ROCKBOX_BIG_ENDIAN) | ||
66 | # define HASH_LITTLE_ENDIAN 0 | ||
67 | # define HASH_BIG_ENDIAN 1 | ||
68 | #else | ||
69 | # define HASH_LITTLE_ENDIAN 0 | ||
70 | # define HASH_BIG_ENDIAN 0 | ||
71 | #endif | ||
72 | |||
73 | #define hashsize(n) ((uint32_t)1<<(n)) | ||
74 | #define hashmask(n) (hashsize(n)-1) | ||
75 | #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) | ||
76 | |||
77 | /* | ||
78 | |||
79 | mix -- mix 3 32-bit values reversibly. | ||
80 | |||
81 | This is reversible, so any information in (a,b,c) before mix() is | ||
82 | still in (a,b,c) after mix(). | ||
83 | |||
84 | If four pairs of (a,b,c) inputs are run through mix(), or through | ||
85 | mix() in reverse, there are at least 32 bits of the output that | ||
86 | are sometimes the same for one pair and different for another pair. | ||
87 | This was tested for: | ||
88 | * pairs that differed by one bit, by two bits, in any combination | ||
89 | of top bits of (a,b,c), or in any combination of bottom bits of | ||
90 | (a,b,c). | ||
91 | * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed | ||
92 | the output delta to a Gray code (a^(a>>1)) so a string of 1's (as | ||
93 | is commonly produced by subtraction) look like a single 1-bit | ||
94 | difference. | ||
95 | * the base values were pseudorandom, all zero but one bit set, or | ||
96 | all zero plus a counter that starts at zero. | ||
97 | |||
98 | Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that | ||
99 | satisfy this are | ||
100 | 4 6 8 16 19 4 | ||
101 | 9 15 3 18 27 15 | ||
102 | 14 9 3 7 17 3 | ||
103 | Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing | ||
104 | for "differ" defined as + with a one-bit base and a two-bit delta. I | ||
105 | used http://burtleburtle.net/bob/hash/avalanche.html to choose | ||
106 | the operations, constants, and arrangements of the variables. | ||
107 | |||
108 | This does not achieve avalanche. There are input bits of (a,b,c) | ||
109 | that fail to affect some output bits of (a,b,c), especially of a. The | ||
110 | most thoroughly mixed value is c, but it doesn't really even achieve | ||
111 | avalanche in c. | ||
112 | |||
113 | This allows some parallelism. Read-after-writes are good at doubling | ||
114 | the number of bits affected, so the goal of mixing pulls in the opposite | ||
115 | direction as the goal of parallelism. I did what I could. Rotates | ||
116 | seem to cost as much as shifts on every machine I could lay my hands | ||
117 | on, and rotates are much kinder to the top and bottom bits, so I used | ||
118 | rotates. | ||
119 | */ | ||
120 | #define mix(a,b,c) \ | ||
121 | { \ | ||
122 | a -= c; a ^= rot(c, 4); c += b; \ | ||
123 | b -= a; b ^= rot(a, 6); a += c; \ | ||
124 | c -= b; c ^= rot(b, 8); b += a; \ | ||
125 | a -= c; a ^= rot(c,16); c += b; \ | ||
126 | b -= a; b ^= rot(a,19); a += c; \ | ||
127 | c -= b; c ^= rot(b, 4); b += a; \ | ||
128 | } | ||
129 | |||
130 | /* | ||
131 | final -- final mixing of 3 32-bit values (a,b,c) into c | ||
132 | |||
133 | Pairs of (a,b,c) values differing in only a few bits will usually | ||
134 | produce values of c that look totally different. This was tested for | ||
135 | * pairs that differed by one bit, by two bits, in any combination | ||
136 | of top bits of (a,b,c), or in any combination of bottom bits of | ||
137 | (a,b,c). | ||
138 | * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed | ||
139 | the output delta to a Gray code (a^(a>>1)) so a string of 1's (as | ||
140 | is commonly produced by subtraction) look like a single 1-bit | ||
141 | difference. | ||
142 | * the base values were pseudorandom, all zero but one bit set, or | ||
143 | all zero plus a counter that starts at zero. | ||
144 | |||
145 | These constants passed: | ||
146 | 14 11 25 16 4 14 24 | ||
147 | 12 14 25 16 4 14 24 | ||
148 | and these came close: | ||
149 | 4 8 15 26 3 22 24 | ||
150 | 10 8 15 26 3 22 24 | ||
151 | 11 8 15 26 3 22 24 | ||
152 | */ | ||
153 | #define final(a,b,c) \ | ||
154 | { \ | ||
155 | c ^= b; c -= rot(b,14); \ | ||
156 | a ^= c; a -= rot(c,11); \ | ||
157 | b ^= a; b -= rot(a,25); \ | ||
158 | c ^= b; c -= rot(b,16); \ | ||
159 | a ^= c; a -= rot(c,4); \ | ||
160 | b ^= a; b -= rot(a,14); \ | ||
161 | c ^= b; c -= rot(b,24); \ | ||
162 | } | ||
163 | |||
164 | /* | ||
165 | k: pointer to the key, an array of uint32_t | ||
166 | length: number of elements in the key | ||
167 | initval: an initialization value | ||
168 | returns the 32-bit hash | ||
169 | */ | ||
170 | uint32_t hashw(const uint32_t *k, size_t length, uint32_t initval) | ||
171 | { | ||
172 | uint32_t a, b, c; | ||
173 | |||
174 | /* Set up the internal state */ | ||
175 | a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval; | ||
176 | |||
177 | /* handle most of the key */ | ||
178 | while (length > 3) | ||
179 | { | ||
180 | a += k[0]; | ||
181 | b += k[1]; | ||
182 | c += k[2]; | ||
183 | mix(a,b,c); | ||
184 | length -= 3; | ||
185 | k += 3; | ||
186 | } | ||
187 | |||
188 | /* handle the last 3 uint32_t's */ | ||
189 | switch(length) /* all the case statements fall through */ | ||
190 | { | ||
191 | case 3: | ||
192 | c+=k[2]; | ||
193 | case 2: | ||
194 | b+=k[1]; | ||
195 | case 1: | ||
196 | a+=k[0]; | ||
197 | final(a,b,c); | ||
198 | case 0: /* case 0: nothing left to add */ | ||
199 | break; | ||
200 | } | ||
201 | /* report the result */ | ||
202 | return c; | ||
203 | } | ||
204 | |||
205 | |||
206 | /* | ||
207 | hashw2() -- same as hashw(), but take two seeds and return two | ||
208 | 32-bit values. pc and pb must both be nonnull, and *pc and *pb must | ||
209 | both be initialized with seeds. If you pass in (*pb)==0, the output | ||
210 | (*pc) will be the same as the return value from hashword(). | ||
211 | k: pointer to the key, an array of uint32_t | ||
212 | length: number of elements in the key | ||
213 | pc, pb: pointers to primary and secondary initial values, also used to store | ||
214 | the hash results. | ||
215 | */ | ||
216 | void hashw2 (const uint32_t *k, size_t length, uint32_t *pc, uint32_t *pb) | ||
217 | { | ||
218 | uint32_t a,b,c; | ||
219 | |||
220 | /* Set up the internal state */ | ||
221 | a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc; | ||
222 | c += *pb; | ||
223 | |||
224 | /* handle most of the key */ | ||
225 | while (length > 3) | ||
226 | { | ||
227 | a += k[0]; | ||
228 | b += k[1]; | ||
229 | c += k[2]; | ||
230 | mix(a,b,c); | ||
231 | length -= 3; | ||
232 | k += 3; | ||
233 | } | ||
234 | |||
235 | /* handle the last 3 uint32_t's */ | ||
236 | switch(length) /* all the case statements fall through */ | ||
237 | { | ||
238 | case 3: | ||
239 | c+=k[2]; | ||
240 | case 2: | ||
241 | b+=k[1]; | ||
242 | case 1: | ||
243 | a+=k[0]; | ||
244 | final(a,b,c); | ||
245 | case 0: /* case 0: nothing left to add */ | ||
246 | break; | ||
247 | } | ||
248 | /* report the result */ | ||
249 | *pc=c; *pb=b; | ||
250 | } | ||
251 | |||
252 | |||
253 | /* | ||
254 | hashs() -- hash a variable-length key into a 32-bit value | ||
255 | k: pointer to the key, an array of bytes | ||
256 | length: number of elements in the key | ||
257 | initval: an initialization value | ||
258 | returns the 32-bit hash | ||
259 | Returns a 32-bit value. Every bit of the key affects every bit of | ||
260 | the return value. Two keys differing by one or two bits will have | ||
261 | totally different hash values. | ||
262 | |||
263 | The best hash table sizes are powers of 2. There is no need to do | ||
264 | mod a prime (mod is sooo slow!). If you need less than 32 bits, | ||
265 | use a bitmask. For example, if you need only 10 bits, do | ||
266 | h = (h & hashmask(10)); | ||
267 | In which case, the hash table should have hashsize(10) elements. | ||
268 | |||
269 | If you are hashing n strings (uint8_t **)k, do it like this: | ||
270 | for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); | ||
271 | |||
272 | By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this | ||
273 | code any way you wish, private, educational, or commercial. It's free. | ||
274 | |||
275 | Use for hash table lookup, or anything where one collision in 2^^32 is | ||
276 | acceptable. Do NOT use for cryptographic purposes. | ||
277 | */ | ||
278 | |||
279 | uint32_t hashs( const void *key, size_t length, uint32_t initval) | ||
280 | { | ||
281 | uint32_t a,b,c; /* internal state */ | ||
282 | union { const void *ptr; size_t i; } u;/* needed for Mac Powerbook G4 */ | ||
283 | |||
284 | /* Set up the internal state */ | ||
285 | a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; | ||
286 | |||
287 | u.ptr = key; | ||
288 | #if HASH_LITTLE_ENDIAN | ||
289 | if ((u.i & 0x3) == 0) { | ||
290 | const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ | ||
291 | |||
292 | /* all but last block: aligned reads and affect 32 bits of (a,b,c) */ | ||
293 | while (length > 12) | ||
294 | { | ||
295 | a += k[0]; | ||
296 | b += k[1]; | ||
297 | c += k[2]; | ||
298 | mix(a,b,c); | ||
299 | length -= 12; | ||
300 | k += 3; | ||
301 | } | ||
302 | |||
303 | /* handle the last (probably partial) block */ | ||
304 | switch(length) | ||
305 | { | ||
306 | case 12: | ||
307 | c += k[2]; | ||
308 | b += k[1]; | ||
309 | a += k[0]; | ||
310 | break; | ||
311 | case 11: | ||
312 | c += k[2] & 0xffffff; | ||
313 | b += k[1]; | ||
314 | a += k[0]; | ||
315 | break; | ||
316 | case 10: | ||
317 | c += k[2] & 0xffff; | ||
318 | b += k[1]; | ||
319 | a += k[0]; | ||
320 | break; | ||
321 | case 9: | ||
322 | c += k[2] & 0xff; | ||
323 | b += k[1]; | ||
324 | a += k[0]; | ||
325 | break; | ||
326 | case 8: | ||
327 | b += k[1]; | ||
328 | a += k[0]; | ||
329 | break; | ||
330 | case 7: | ||
331 | b += k[1] & 0xffffff; | ||
332 | a += k[0]; | ||
333 | break; | ||
334 | case 6: | ||
335 | b += k[1] & 0xffff; | ||
336 | a += k[0]; | ||
337 | break; | ||
338 | case 5: | ||
339 | b += k[1] & 0xff; | ||
340 | a += k[0]; | ||
341 | break; | ||
342 | case 4: | ||
343 | a += k[0]; | ||
344 | break; | ||
345 | case 3: | ||
346 | a += k[0] & 0xffffff; | ||
347 | break; | ||
348 | case 2 : | ||
349 | a += k[0] & 0xffff; | ||
350 | break; | ||
351 | case 1: | ||
352 | a += k[0] & 0xff; | ||
353 | break; | ||
354 | case 0: | ||
355 | return c; /* zero length strings require no mixing */ | ||
356 | } | ||
357 | |||
358 | } else if ((u.i & 0x1) == 0) { | ||
359 | const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ | ||
360 | const uint8_t *k8; | ||
361 | |||
362 | /* all but last block: aligned reads and different mixing */ | ||
363 | while (length > 12) | ||
364 | { | ||
365 | a += k[0] + (((uint32_t)k[1])<<16); | ||
366 | b += k[2] + (((uint32_t)k[3])<<16); | ||
367 | c += k[4] + (((uint32_t)k[5])<<16); | ||
368 | mix(a,b,c); | ||
369 | length -= 12; | ||
370 | k += 6; | ||
371 | } | ||
372 | |||
373 | /* handle the last (probably partial) block */ | ||
374 | k8 = (const uint8_t *)k; | ||
375 | switch(length) | ||
376 | { | ||
377 | case 12: | ||
378 | c += k[4] + (((uint32_t)k[5])<<16); | ||
379 | b += k[2] + (((uint32_t)k[3])<<16); | ||
380 | a += k[0] + (((uint32_t)k[1])<<16); | ||
381 | break; | ||
382 | case 11: | ||
383 | c += ((uint32_t)k8[10])<<16; /* fall through */ | ||
384 | case 10: | ||
385 | c += k[4]; | ||
386 | b += k[2] + (((uint32_t)k[3])<<16); | ||
387 | a += k[0] + (((uint32_t)k[1])<<16); | ||
388 | break; | ||
389 | case 9: | ||
390 | c += k8[8]; /* fall through */ | ||
391 | case 8: | ||
392 | b += k[2] + (((uint32_t)k[3])<<16); | ||
393 | a += k[0] + (((uint32_t)k[1])<<16); | ||
394 | break; | ||
395 | case 7: | ||
396 | b += ((uint32_t)k8[6])<<16; /* fall through */ | ||
397 | case 6: | ||
398 | b += k[2]; | ||
399 | a += k[0] + (((uint32_t)k[1])<<16); | ||
400 | break; | ||
401 | case 5: | ||
402 | b += k8[4]; /* fall through */ | ||
403 | case 4: | ||
404 | a += k[0] + (((uint32_t)k[1])<<16); | ||
405 | break; | ||
406 | case 3: | ||
407 | a += ((uint32_t)k8[2])<<16; /* fall through */ | ||
408 | case 2: | ||
409 | a += k[0]; | ||
410 | break; | ||
411 | case 1: | ||
412 | a += k8[0]; | ||
413 | break; | ||
414 | case 0: | ||
415 | return c; /* zero length requires no mixing */ | ||
416 | } | ||
417 | |||
418 | } else | ||
419 | #endif | ||
420 | { /* need to read the key one byte at a time */ | ||
421 | const uint8_t *k = (const uint8_t *)key; | ||
422 | |||
423 | /* all but the last block: affect some 32 bits of (a,b,c) */ | ||
424 | while (length > 12) | ||
425 | { | ||
426 | a += k[0]; | ||
427 | a += ((uint32_t)k[1])<<8; | ||
428 | a += ((uint32_t)k[2])<<16; | ||
429 | a += ((uint32_t)k[3])<<24; | ||
430 | b += k[4]; | ||
431 | b += ((uint32_t)k[5])<<8; | ||
432 | b += ((uint32_t)k[6])<<16; | ||
433 | b += ((uint32_t)k[7])<<24; | ||
434 | c += k[8]; | ||
435 | c += ((uint32_t)k[9])<<8; | ||
436 | c += ((uint32_t)k[10])<<16; | ||
437 | c += ((uint32_t)k[11])<<24; | ||
438 | mix(a,b,c); | ||
439 | length -= 12; | ||
440 | k += 12; | ||
441 | } | ||
442 | |||
443 | /* last block: affect all 32 bits of (c) */ | ||
444 | switch(length) /* all the case statements fall through */ | ||
445 | { | ||
446 | case 12: | ||
447 | c += ((uint32_t)k[11])<<24; | ||
448 | case 11: | ||
449 | c += ((uint32_t)k[10])<<16; | ||
450 | case 10: | ||
451 | c += ((uint32_t)k[9])<<8; | ||
452 | case 9: | ||
453 | c += k[8]; | ||
454 | case 8: | ||
455 | b += ((uint32_t)k[7])<<24; | ||
456 | case 7: | ||
457 | b += ((uint32_t)k[6])<<16; | ||
458 | case 6: | ||
459 | b += ((uint32_t)k[5])<<8; | ||
460 | case 5: | ||
461 | b += k[4]; | ||
462 | case 4: | ||
463 | a += ((uint32_t)k[3])<<24; | ||
464 | case 3: | ||
465 | a += ((uint32_t)k[2])<<16; | ||
466 | case 2: | ||
467 | a += ((uint32_t)k[1])<<8; | ||
468 | case 1: | ||
469 | a +=k [0]; | ||
470 | break; | ||
471 | case 0: | ||
472 | return c; | ||
473 | } | ||
474 | } | ||
475 | |||
476 | final(a,b,c); | ||
477 | return c; | ||
478 | } | ||
479 | |||
480 | |||
481 | /* | ||
482 | hashs2: return 2 32-bit hash values | ||
483 | k: pointer to the key, an array of bytes | ||
484 | length: number of elements in the key | ||
485 | pc, pb: pointers to primary and secondary initial values, also used to store | ||
486 | the hash results. | ||
487 | * This is identical to hashlittle(), except it returns two 32-bit hash | ||
488 | * values instead of just one. This is good enough for hash table | ||
489 | * lookup with 2^^64 buckets, or if you want a second hash if you're not | ||
490 | * happy with the first, or if you want a probably-unique 64-bit ID for | ||
491 | * the key. *pc is better mixed than *pb, so use *pc first. If you want | ||
492 | * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)". | ||
493 | */ | ||
494 | void hashs2(const void *key, size_t length, uint32_t *pc, uint32_t *pb) | ||
495 | { | ||
496 | uint32_t a, b, c; /* internal state */ | ||
497 | union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ | ||
498 | |||
499 | /* Set up the internal state */ | ||
500 | a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc; | ||
501 | c += *pb; | ||
502 | |||
503 | u.ptr = key; | ||
504 | #if HASH_LITTLE_ENDIAN | ||
505 | if (((u.i & 0x3) == 0)) { | ||
506 | const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ | ||
507 | |||
508 | /* all but last block: aligned reads and affect 32 bits of (a,b,c) */ | ||
509 | while (length > 12) | ||
510 | { | ||
511 | a += k[0]; | ||
512 | b += k[1]; | ||
513 | c += k[2]; | ||
514 | mix(a,b,c); | ||
515 | length -= 12; | ||
516 | k += 3; | ||
517 | } | ||
518 | |||
519 | /* handle the last (probably partial) block */ | ||
520 | switch(length) | ||
521 | { | ||
522 | case 12: | ||
523 | c += k[2]; | ||
524 | b += k[1]; | ||
525 | a += k[0]; | ||
526 | break; | ||
527 | case 11: | ||
528 | c += k[2] & 0xffffff; | ||
529 | b += k[1]; | ||
530 | a += k[0]; | ||
531 | break; | ||
532 | case 10: | ||
533 | c += k[2] & 0xffff; | ||
534 | b += k[1]; | ||
535 | a += k[0]; | ||
536 | break; | ||
537 | case 9: | ||
538 | c += k[2] & 0xff; | ||
539 | b += k[1]; | ||
540 | a += k[0]; | ||
541 | break; | ||
542 | case 8: | ||
543 | b += k[1]; | ||
544 | a += k[0]; | ||
545 | break; | ||
546 | case 7: | ||
547 | b += k[1] & 0xffffff; | ||
548 | a += k[0]; | ||
549 | break; | ||
550 | case 6: | ||
551 | b += k[1] & 0xffff; | ||
552 | a += k[0]; | ||
553 | break; | ||
554 | case 5: | ||
555 | b += k[1] & 0xff; | ||
556 | a += k[0]; | ||
557 | break; | ||
558 | case 4: | ||
559 | a += k[0]; | ||
560 | break; | ||
561 | case 3: | ||
562 | a += k[0] & 0xffffff; | ||
563 | break; | ||
564 | case 2: | ||
565 | a += k[0] & 0xffff; | ||
566 | break; | ||
567 | case 1: | ||
568 | a += k[0] & 0xff; | ||
569 | break; | ||
570 | case 0: | ||
571 | *pc=c; | ||
572 | *pb=b; | ||
573 | return; /* zero length strings require no mixing */ | ||
574 | } | ||
575 | } else if (((u.i & 0x1) == 0)) { | ||
576 | const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ | ||
577 | const uint8_t *k8; | ||
578 | |||
579 | /* all but last block: aligned reads and different mixing */ | ||
580 | while (length > 12) | ||
581 | { | ||
582 | a += k[0] + (((uint32_t)k[1])<<16); | ||
583 | b += k[2] + (((uint32_t)k[3])<<16); | ||
584 | c += k[4] + (((uint32_t)k[5])<<16); | ||
585 | mix(a,b,c); | ||
586 | length -= 12; | ||
587 | k += 6; | ||
588 | } | ||
589 | |||
590 | /* handle the last (probably partial) block */ | ||
591 | k8 = (const uint8_t *)k; | ||
592 | switch(length) | ||
593 | { | ||
594 | case 12: | ||
595 | c += k[4] + (((uint32_t)k[5])<<16); | ||
596 | b += k[2] + (((uint32_t)k[3])<<16); | ||
597 | a += k[0] + (((uint32_t)k[1])<<16); | ||
598 | break; | ||
599 | case 11: | ||
600 | c += ((uint32_t)k8[10])<<16; /* fall through */ | ||
601 | case 10: | ||
602 | c += k[4]; | ||
603 | b += k[2] + (((uint32_t)k[3])<<16); | ||
604 | a += k[0] + (((uint32_t)k[1])<<16); | ||
605 | break; | ||
606 | case 9: | ||
607 | c += k8[8]; /* fall through */ | ||
608 | case 8: | ||
609 | b += k[2] + (((uint32_t)k[3])<<16); | ||
610 | a += k[0] + (((uint32_t)k[1])<<16); | ||
611 | break; | ||
612 | case 7: | ||
613 | b += ((uint32_t)k8[6])<<16; /* fall through */ | ||
614 | case 6: | ||
615 | b += k[2]; | ||
616 | a += k[0] + (((uint32_t)k[1])<<16); | ||
617 | break; | ||
618 | case 5: | ||
619 | b += k8[4]; /* fall through */ | ||
620 | case 4: | ||
621 | a += k[0] + (((uint32_t)k[1])<<16); | ||
622 | break; | ||
623 | case 3: | ||
624 | a += ((uint32_t)k8[2])<<16; /* fall through */ | ||
625 | case 2: | ||
626 | a += k[0]; | ||
627 | break; | ||
628 | case 1: | ||
629 | a += k8[0]; | ||
630 | break; | ||
631 | case 0: | ||
632 | *pc=c; | ||
633 | *pb=b; | ||
634 | return; /* zero length strings require no mixing */ | ||
635 | } | ||
636 | } else | ||
637 | #endif | ||
638 | { /* need to read the key one byte at a time */ | ||
639 | const uint8_t *k = (const uint8_t *)key; | ||
640 | |||
641 | /* all but the last block: affect some 32 bits of (a,b,c) */ | ||
642 | while (length > 12) | ||
643 | { | ||
644 | a += k[0]; | ||
645 | a += ((uint32_t)k[1])<<8; | ||
646 | a += ((uint32_t)k[2])<<16; | ||
647 | a += ((uint32_t)k[3])<<24; | ||
648 | b += k[4]; | ||
649 | b += ((uint32_t)k[5])<<8; | ||
650 | b += ((uint32_t)k[6])<<16; | ||
651 | b += ((uint32_t)k[7])<<24; | ||
652 | c += k[8]; | ||
653 | c += ((uint32_t)k[9])<<8; | ||
654 | c += ((uint32_t)k[10])<<16; | ||
655 | c += ((uint32_t)k[11])<<24; | ||
656 | mix(a,b,c); | ||
657 | length -= 12; | ||
658 | k += 12; | ||
659 | } | ||
660 | |||
661 | /* last block: affect all 32 bits of (c) */ | ||
662 | switch(length) /* all the case statements fall through */ | ||
663 | { | ||
664 | case 12: | ||
665 | c += ((uint32_t)k[11]) << 24; | ||
666 | case 11: | ||
667 | c += ((uint32_t)k[10]) << 16; | ||
668 | case 10: | ||
669 | c += ((uint32_t)k[9]) << 8; | ||
670 | case 9: | ||
671 | c += k[8]; | ||
672 | case 8: | ||
673 | b += ((uint32_t)k[7]) << 24; | ||
674 | case 7: | ||
675 | b += ((uint32_t)k[6]) << 16; | ||
676 | case 6: | ||
677 | b += ((uint32_t)k[5]) << 8; | ||
678 | case 5: | ||
679 | b += k[4]; | ||
680 | case 4: | ||
681 | a += ((uint32_t)k[3]) << 24; | ||
682 | case 3: | ||
683 | a += ((uint32_t)k[2]) << 16; | ||
684 | case 2: | ||
685 | a += ((uint32_t)k[1]) << 8; | ||
686 | case 1: | ||
687 | a += k[0]; | ||
688 | break; | ||
689 | case 0: | ||
690 | *pc=c; | ||
691 | *pb=b; | ||
692 | return; /* zero length strings require no mixing */ | ||
693 | } | ||
694 | } | ||
695 | |||
696 | final(a,b,c); | ||
697 | *pc=c; | ||
698 | *pb=b; | ||
699 | } | ||
diff --git a/apps/plugins/lib/jhash.h b/apps/plugins/lib/jhash.h new file mode 100644 index 0000000000..97d1ac3d93 --- /dev/null +++ b/apps/plugins/lib/jhash.h | |||
@@ -0,0 +1,67 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2009 by Andrew Mahone | ||
11 | * | ||
12 | * jhash.c headers | ||
13 | * | ||
14 | * This program is free software; you can redistribute it and/or | ||
15 | * modify it under the terms of the GNU General Public License | ||
16 | * as published by the Free Software Foundation; either version 2 | ||
17 | * of the License, or (at your option) any later version. | ||
18 | * | ||
19 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
20 | * KIND, either express or implied. | ||
21 | * | ||
22 | ****************************************************************************/ | ||
23 | |||
24 | #ifndef _LIB_JHASH_H_ | ||
25 | #define _LIB_JHASH_H_ | ||
26 | #include <inttypes.h> /* defines uint32_t etc */ | ||
27 | #include <sys/types.h> | ||
28 | #include <plugin.h> | ||
29 | |||
30 | /* | ||
31 | hashw() -- hash an array of uint32_t into a 32-bit value | ||
32 | k: pointer to the key, an array of uint32_t | ||
33 | length: number of elements in the key | ||
34 | initval: an initialization value | ||
35 | returns the 32-bit hash | ||
36 | */ | ||
37 | uint32_t hashw(const uint32_t *k, size_t length, uint32_t initval); | ||
38 | |||
39 | /* | ||
40 | hashw() -- hash an array of uint32_t into two 32-bit values | ||
41 | (*pc) will be the same as the return value from hashword(). | ||
42 | k: pointer to the key, an array of uint32_t | ||
43 | length: number of elements in the key | ||
44 | pc, pb: pointers to primary and secondary initial values, also used to store | ||
45 | the hash results. | ||
46 | */ | ||
47 | void hashw2 (const uint32_t *k, size_t length, uint32_t *pc, uint32_t *pb); | ||
48 | |||
49 | /* | ||
50 | hashs() -- hash an array of bytes into a 32-bit value | ||
51 | k: pointer to the key, an array of bytes | ||
52 | length: number of elements in the key | ||
53 | initval: an initialization value | ||
54 | returns the 32-bit hash | ||
55 | */ | ||
56 | uint32_t hashs( const void *key, size_t length, uint32_t initval); | ||
57 | |||
58 | /* | ||
59 | hashs2() -- hash an array of bytes into two 32-bit values | ||
60 | k: pointer to the key, an array of bytes | ||
61 | length: number of elements in the key | ||
62 | pc, pb: pointers to primary and secondary initial values, also used to store | ||
63 | the hash results. | ||
64 | */ | ||
65 | void hashs2(const void *key, size_t length, uint32_t *pc, uint32_t *pb); | ||
66 | #endif | ||
67 | |||