^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) #ifndef _LINUX_JHASH_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) #define _LINUX_JHASH_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) /* jhash.h: Jenkins hash support.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * Copyright (C) 2006. Bob Jenkins (bob_jenkins@burtleburtle.net)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * https://burtleburtle.net/bob/hash/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * These are the credits from Bob's sources:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * These are functions for producing 32-bit hashes for hash table lookup.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * are externally useful functions. Routines to test the hash are included
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * if SELF_TEST is defined. You can use this free for any purpose. It's in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * the public domain. It has no warranty.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * Copyright (C) 2009-2010 Jozsef Kadlecsik (kadlec@blackhole.kfki.hu)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) * I've modified Bob's hash to be useful in the Linux kernel, and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) * any bugs present are my fault.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * Jozsef
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) #include <linux/bitops.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) #include <linux/unaligned/packed_struct.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) /* Best hash sizes are of power of two */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) #define jhash_size(n) ((u32)1<<(n))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) /* Mask the hash value, i.e (value & jhash_mask(n)) instead of (value % n) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) #define jhash_mask(n) (jhash_size(n)-1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) /* __jhash_mix -- mix 3 32-bit values reversibly. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) #define __jhash_mix(a, b, c) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) a -= c; a ^= rol32(c, 4); c += b; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) b -= a; b ^= rol32(a, 6); a += c; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) c -= b; c ^= rol32(b, 8); b += a; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) a -= c; a ^= rol32(c, 16); c += b; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) b -= a; b ^= rol32(a, 19); a += c; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) c -= b; c ^= rol32(b, 4); b += a; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) /* __jhash_final - final mixing of 3 32-bit values (a,b,c) into c */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) #define __jhash_final(a, b, c) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) c ^= b; c -= rol32(b, 14); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) a ^= c; a -= rol32(c, 11); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) b ^= a; b -= rol32(a, 25); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) c ^= b; c -= rol32(b, 16); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) a ^= c; a -= rol32(c, 4); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) b ^= a; b -= rol32(a, 14); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) c ^= b; c -= rol32(b, 24); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) /* An arbitrary initial parameter */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) #define JHASH_INITVAL 0xdeadbeef
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) /* jhash - hash an arbitrary key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) * @k: sequence of bytes as key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * @length: the length of the key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) * @initval: the previous hash, or an arbitray value
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) * The generic version, hashes an arbitrary sequence of bytes.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) * No alignment or length assumptions are made about the input key.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) * Returns the hash value of the key. The result depends on endianness.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) static inline u32 jhash(const void *key, u32 length, u32 initval)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) u32 a, b, c;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) const u8 *k = key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) /* Set up the internal state */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) a = b = c = JHASH_INITVAL + length + initval;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) /* All but the last block: affect some 32 bits of (a,b,c) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) while (length > 12) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) a += __get_unaligned_cpu32(k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) b += __get_unaligned_cpu32(k + 4);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) c += __get_unaligned_cpu32(k + 8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) __jhash_mix(a, b, c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) length -= 12;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) k += 12;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) /* Last block: affect all 32 bits of (c) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) /* All the case statements fall through */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) switch (length) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) case 12: c += (u32)k[11]<<24;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) case 11: c += (u32)k[10]<<16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) case 10: c += (u32)k[9]<<8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) case 9: c += k[8];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) case 8: b += (u32)k[7]<<24;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) case 7: b += (u32)k[6]<<16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) case 6: b += (u32)k[5]<<8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) case 5: b += k[4];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) case 4: a += (u32)k[3]<<24;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) case 3: a += (u32)k[2]<<16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) case 2: a += (u32)k[1]<<8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) case 1: a += k[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) __jhash_final(a, b, c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) case 0: /* Nothing left to add */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) return c;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) /* jhash2 - hash an array of u32's
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) * @k: the key which must be an array of u32's
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) * @length: the number of u32's in the key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) * @initval: the previous hash, or an arbitray value
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) * Returns the hash value of the key.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) static inline u32 jhash2(const u32 *k, u32 length, u32 initval)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) u32 a, b, c;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) /* Set up the internal state */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) a = b = c = JHASH_INITVAL + (length<<2) + initval;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) /* Handle most of the key */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) while (length > 3) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) a += k[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) b += k[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) c += k[2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) __jhash_mix(a, b, c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) length -= 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) k += 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) /* Handle the last 3 u32's: all the case statements fall through */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) switch (length) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) case 3: c += k[2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) case 2: b += k[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) case 1: a += k[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) __jhash_final(a, b, c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) case 0: /* Nothing left to add */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) return c;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) /* __jhash_nwords - hash exactly 3, 2 or 1 word(s) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) static inline u32 __jhash_nwords(u32 a, u32 b, u32 c, u32 initval)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) a += initval;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) b += initval;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) c += initval;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) __jhash_final(a, b, c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) return c;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) static inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) return __jhash_nwords(a, b, c, initval + JHASH_INITVAL + (3 << 2));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) static inline u32 jhash_2words(u32 a, u32 b, u32 initval)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) return __jhash_nwords(a, b, 0, initval + JHASH_INITVAL + (2 << 2));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) static inline u32 jhash_1word(u32 a, u32 initval)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) return __jhash_nwords(a, 0, 0, initval + JHASH_INITVAL + (1 << 2));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) #endif /* _LINUX_JHASH_H */
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags