tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
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/*
23lookup3.c, by Bob Jenkins, May 2006, Public Domain.
24
25These are functions for producing 32-bit hashes for hash table lookup.
26hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
27are externally useful functions. Routines to test the hash are included
28if SELF_TEST is defined. You can use this free for any purpose. It's in
29the public domain. It has no warranty.
30
31You probably want to use hashlittle(). hashlittle() and hashbig()
32hash byte arrays. hashlittle() is is faster than hashbig() on
33little-endian machines. Intel and AMD are little-endian machines.
34On second thought, you probably want hashlittle2(), which is identical to
35hashlittle() except it returns two 32-bit hashes for the price of one.
36You could implement hashbig2() if you wanted but I haven't bothered here.
37
38If you want to find a hash of, say, exactly 7 integers, do
39a = i1; b = i2; c = i3;
40mix(a,b,c);
41a += i4; b += i5; c += i6;
42mix(a,b,c);
43a += i7;
44final(a,b,c);
45then use c as the hash value. If you have a variable length array of
464-byte integers to hash, use hashword(). If you have a byte array (like
47a character string), use hashlittle(). If you have several byte arrays, or
48a mix of things, see the comments above hashlittle().
49
50Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
51then mix those integers. This is fast (you can do a lot more thorough
52mixing with 12*3 instructions on 3 integers than you can with 3 instructions
53on 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
79mix -- mix 3 32-bit values reversibly.
80
81This is reversible, so any information in (a,b,c) before mix() is
82still in (a,b,c) after mix().
83
84If four pairs of (a,b,c) inputs are run through mix(), or through
85mix() in reverse, there are at least 32 bits of the output that
86are sometimes the same for one pair and different for another pair.
87This 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
98Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
99satisfy this are
100 4 6 8 16 19 4
101 9 15 3 18 27 15
102 14 9 3 7 17 3
103Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
104for "differ" defined as + with a one-bit base and a two-bit delta. I
105used http://burtleburtle.net/bob/hash/avalanche.html to choose
106the operations, constants, and arrangements of the variables.
107
108This does not achieve avalanche. There are input bits of (a,b,c)
109that fail to affect some output bits of (a,b,c), especially of a. The
110most thoroughly mixed value is c, but it doesn't really even achieve
111avalanche in c.
112
113This allows some parallelism. Read-after-writes are good at doubling
114the number of bits affected, so the goal of mixing pulls in the opposite
115direction as the goal of parallelism. I did what I could. Rotates
116seem to cost as much as shifts on every machine I could lay my hands
117on, and rotates are much kinder to the top and bottom bits, so I used
118rotates.
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/*
131final -- final mixing of 3 32-bit values (a,b,c) into c
132
133Pairs of (a,b,c) values differing in only a few bits will usually
134produce 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
145These constants passed:
146 14 11 25 16 4 14 24
147 12 14 25 16 4 14 24
148and 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*/
170uint32_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/*
207hashw2() -- same as hashw(), but take two seeds and return two
20832-bit values. pc and pb must both be nonnull, and *pc and *pb must
209both 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*/
216void 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/*
254hashs() -- 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
259Returns a 32-bit value. Every bit of the key affects every bit of
260the return value. Two keys differing by one or two bits will have
261totally different hash values.
262
263The best hash table sizes are powers of 2. There is no need to do
264mod a prime (mod is sooo slow!). If you need less than 32 bits,
265use a bitmask. For example, if you need only 10 bits, do
266h = (h & hashmask(10));
267In which case, the hash table should have hashsize(10) elements.
268
269If you are hashing n strings (uint8_t **)k, do it like this:
270for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
271
272By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
273code any way you wish, private, educational, or commercial. It's free.
274
275Use for hash table lookup, or anything where one collision in 2^^32 is
276acceptable. Do NOT use for cryptographic purposes.
277*/
278
279uint32_t hashs( const void *key, size_t length, uint32_t initval)
280{
281 uint32_t a,b,c; /* internal state */
282#if HASH_LITTLE_ENDIAN
283 union { const void *ptr; size_t i; } u;/* needed for Mac Powerbook G4 */
284#endif
285
286 /* Set up the internal state */
287 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
288
289#if HASH_LITTLE_ENDIAN
290 u.ptr = key;
291 if ((u.i & 0x3) == 0) {
292 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
293
294 /* all but last block: aligned reads and affect 32 bits of (a,b,c) */
295 while (length > 12)
296 {
297 a += k[0];
298 b += k[1];
299 c += k[2];
300 mix(a,b,c);
301 length -= 12;
302 k += 3;
303 }
304
305/* handle the last (probably partial) block */
306 switch(length)
307 {
308 case 12:
309 c += k[2];
310 b += k[1];
311 a += k[0];
312 break;
313 case 11:
314 c += k[2] & 0xffffff;
315 b += k[1];
316 a += k[0];
317 break;
318 case 10:
319 c += k[2] & 0xffff;
320 b += k[1];
321 a += k[0];
322 break;
323 case 9:
324 c += k[2] & 0xff;
325 b += k[1];
326 a += k[0];
327 break;
328 case 8:
329 b += k[1];
330 a += k[0];
331 break;
332 case 7:
333 b += k[1] & 0xffffff;
334 a += k[0];
335 break;
336 case 6:
337 b += k[1] & 0xffff;
338 a += k[0];
339 break;
340 case 5:
341 b += k[1] & 0xff;
342 a += k[0];
343 break;
344 case 4:
345 a += k[0];
346 break;
347 case 3:
348 a += k[0] & 0xffffff;
349 break;
350 case 2 :
351 a += k[0] & 0xffff;
352 break;
353 case 1:
354 a += k[0] & 0xff;
355 break;
356 case 0:
357 return c; /* zero length strings require no mixing */
358 }
359
360 } else if ((u.i & 0x1) == 0) {
361 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
362 const uint8_t *k8;
363
364 /* all but last block: aligned reads and different mixing */
365 while (length > 12)
366 {
367 a += k[0] + (((uint32_t)k[1])<<16);
368 b += k[2] + (((uint32_t)k[3])<<16);
369 c += k[4] + (((uint32_t)k[5])<<16);
370 mix(a,b,c);
371 length -= 12;
372 k += 6;
373 }
374
375 /* handle the last (probably partial) block */
376 k8 = (const uint8_t *)k;
377 switch(length)
378 {
379 case 12:
380 c += k[4] + (((uint32_t)k[5])<<16);
381 b += k[2] + (((uint32_t)k[3])<<16);
382 a += k[0] + (((uint32_t)k[1])<<16);
383 break;
384 case 11:
385 c += ((uint32_t)k8[10])<<16; /* fall through */
386 case 10:
387 c += k[4];
388 b += k[2] + (((uint32_t)k[3])<<16);
389 a += k[0] + (((uint32_t)k[1])<<16);
390 break;
391 case 9:
392 c += k8[8]; /* fall through */
393 case 8:
394 b += k[2] + (((uint32_t)k[3])<<16);
395 a += k[0] + (((uint32_t)k[1])<<16);
396 break;
397 case 7:
398 b += ((uint32_t)k8[6])<<16; /* fall through */
399 case 6:
400 b += k[2];
401 a += k[0] + (((uint32_t)k[1])<<16);
402 break;
403 case 5:
404 b += k8[4]; /* fall through */
405 case 4:
406 a += k[0] + (((uint32_t)k[1])<<16);
407 break;
408 case 3:
409 a += ((uint32_t)k8[2])<<16; /* fall through */
410 case 2:
411 a += k[0];
412 break;
413 case 1:
414 a += k8[0];
415 break;
416 case 0:
417 return c; /* zero length requires no mixing */
418 }
419
420 } else
421#endif
422 { /* need to read the key one byte at a time */
423 const uint8_t *k = (const uint8_t *)key;
424
425 /* all but the last block: affect some 32 bits of (a,b,c) */
426 while (length > 12)
427 {
428 a += k[0];
429 a += ((uint32_t)k[1])<<8;
430 a += ((uint32_t)k[2])<<16;
431 a += ((uint32_t)k[3])<<24;
432 b += k[4];
433 b += ((uint32_t)k[5])<<8;
434 b += ((uint32_t)k[6])<<16;
435 b += ((uint32_t)k[7])<<24;
436 c += k[8];
437 c += ((uint32_t)k[9])<<8;
438 c += ((uint32_t)k[10])<<16;
439 c += ((uint32_t)k[11])<<24;
440 mix(a,b,c);
441 length -= 12;
442 k += 12;
443 }
444
445 /* last block: affect all 32 bits of (c) */
446 switch(length) /* all the case statements fall through */
447 {
448 case 12:
449 c += ((uint32_t)k[11])<<24;
450 case 11:
451 c += ((uint32_t)k[10])<<16;
452 case 10:
453 c += ((uint32_t)k[9])<<8;
454 case 9:
455 c += k[8];
456 case 8:
457 b += ((uint32_t)k[7])<<24;
458 case 7:
459 b += ((uint32_t)k[6])<<16;
460 case 6:
461 b += ((uint32_t)k[5])<<8;
462 case 5:
463 b += k[4];
464 case 4:
465 a += ((uint32_t)k[3])<<24;
466 case 3:
467 a += ((uint32_t)k[2])<<16;
468 case 2:
469 a += ((uint32_t)k[1])<<8;
470 case 1:
471 a +=k [0];
472 break;
473 case 0:
474 return c;
475 }
476 }
477
478 final(a,b,c);
479 return c;
480}
481
482
483/*
484hashs2: return 2 32-bit hash values
485 k: pointer to the key, an array of bytes
486 length: number of elements in the key
487 pc, pb: pointers to primary and secondary initial values, also used to store
488 the hash results.
489* This is identical to hashlittle(), except it returns two 32-bit hash
490* values instead of just one. This is good enough for hash table
491* lookup with 2^^64 buckets, or if you want a second hash if you're not
492* happy with the first, or if you want a probably-unique 64-bit ID for
493* the key. *pc is better mixed than *pb, so use *pc first. If you want
494* a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
495*/
496void hashs2(const void *key, size_t length, uint32_t *pc, uint32_t *pb)
497{
498 uint32_t a, b, c; /* internal state */
499#if HASH_LITTLE_ENDIAN
500 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
501#endif
502
503 /* Set up the internal state */
504 a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc;
505 c += *pb;
506
507#if HASH_LITTLE_ENDIAN
508 u.ptr = key;
509 if (((u.i & 0x3) == 0)) {
510 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
511
512 /* all but last block: aligned reads and affect 32 bits of (a,b,c) */
513 while (length > 12)
514 {
515 a += k[0];
516 b += k[1];
517 c += k[2];
518 mix(a,b,c);
519 length -= 12;
520 k += 3;
521 }
522
523/* handle the last (probably partial) block */
524 switch(length)
525 {
526 case 12:
527 c += k[2];
528 b += k[1];
529 a += k[0];
530 break;
531 case 11:
532 c += k[2] & 0xffffff;
533 b += k[1];
534 a += k[0];
535 break;
536 case 10:
537 c += k[2] & 0xffff;
538 b += k[1];
539 a += k[0];
540 break;
541 case 9:
542 c += k[2] & 0xff;
543 b += k[1];
544 a += k[0];
545 break;
546 case 8:
547 b += k[1];
548 a += k[0];
549 break;
550 case 7:
551 b += k[1] & 0xffffff;
552 a += k[0];
553 break;
554 case 6:
555 b += k[1] & 0xffff;
556 a += k[0];
557 break;
558 case 5:
559 b += k[1] & 0xff;
560 a += k[0];
561 break;
562 case 4:
563 a += k[0];
564 break;
565 case 3:
566 a += k[0] & 0xffffff;
567 break;
568 case 2:
569 a += k[0] & 0xffff;
570 break;
571 case 1:
572 a += k[0] & 0xff;
573 break;
574 case 0:
575 *pc=c;
576 *pb=b;
577 return; /* zero length strings require no mixing */
578 }
579 } else if (((u.i & 0x1) == 0)) {
580 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
581 const uint8_t *k8;
582
583 /* all but last block: aligned reads and different mixing */
584 while (length > 12)
585 {
586 a += k[0] + (((uint32_t)k[1])<<16);
587 b += k[2] + (((uint32_t)k[3])<<16);
588 c += k[4] + (((uint32_t)k[5])<<16);
589 mix(a,b,c);
590 length -= 12;
591 k += 6;
592 }
593
594 /* handle the last (probably partial) block */
595 k8 = (const uint8_t *)k;
596 switch(length)
597 {
598 case 12:
599 c += k[4] + (((uint32_t)k[5])<<16);
600 b += k[2] + (((uint32_t)k[3])<<16);
601 a += k[0] + (((uint32_t)k[1])<<16);
602 break;
603 case 11:
604 c += ((uint32_t)k8[10])<<16; /* fall through */
605 case 10:
606 c += k[4];
607 b += k[2] + (((uint32_t)k[3])<<16);
608 a += k[0] + (((uint32_t)k[1])<<16);
609 break;
610 case 9:
611 c += k8[8]; /* fall through */
612 case 8:
613 b += k[2] + (((uint32_t)k[3])<<16);
614 a += k[0] + (((uint32_t)k[1])<<16);
615 break;
616 case 7:
617 b += ((uint32_t)k8[6])<<16; /* fall through */
618 case 6:
619 b += k[2];
620 a += k[0] + (((uint32_t)k[1])<<16);
621 break;
622 case 5:
623 b += k8[4]; /* fall through */
624 case 4:
625 a += k[0] + (((uint32_t)k[1])<<16);
626 break;
627 case 3:
628 a += ((uint32_t)k8[2])<<16; /* fall through */
629 case 2:
630 a += k[0];
631 break;
632 case 1:
633 a += k8[0];
634 break;
635 case 0:
636 *pc=c;
637 *pb=b;
638 return; /* zero length strings require no mixing */
639 }
640 } else
641#endif
642 { /* need to read the key one byte at a time */
643 const uint8_t *k = (const uint8_t *)key;
644
645 /* all but the last block: affect some 32 bits of (a,b,c) */
646 while (length > 12)
647 {
648 a += k[0];
649 a += ((uint32_t)k[1])<<8;
650 a += ((uint32_t)k[2])<<16;
651 a += ((uint32_t)k[3])<<24;
652 b += k[4];
653 b += ((uint32_t)k[5])<<8;
654 b += ((uint32_t)k[6])<<16;
655 b += ((uint32_t)k[7])<<24;
656 c += k[8];
657 c += ((uint32_t)k[9])<<8;
658 c += ((uint32_t)k[10])<<16;
659 c += ((uint32_t)k[11])<<24;
660 mix(a,b,c);
661 length -= 12;
662 k += 12;
663 }
664
665 /* last block: affect all 32 bits of (c) */
666 switch(length) /* all the case statements fall through */
667 {
668 case 12:
669 c += ((uint32_t)k[11]) << 24;
670 case 11:
671 c += ((uint32_t)k[10]) << 16;
672 case 10:
673 c += ((uint32_t)k[9]) << 8;
674 case 9:
675 c += k[8];
676 case 8:
677 b += ((uint32_t)k[7]) << 24;
678 case 7:
679 b += ((uint32_t)k[6]) << 16;
680 case 6:
681 b += ((uint32_t)k[5]) << 8;
682 case 5:
683 b += k[4];
684 case 4:
685 a += ((uint32_t)k[3]) << 24;
686 case 3:
687 a += ((uint32_t)k[2]) << 16;
688 case 2:
689 a += ((uint32_t)k[1]) << 8;
690 case 1:
691 a += k[0];
692 break;
693 case 0:
694 *pc=c;
695 *pb=b;
696 return; /* zero length strings require no mixing */
697 }
698 }
699
700 final(a,b,c);
701 *pc=c;
702 *pb=b;
703}