^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) #include <linux/ceph/types.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) #include <linux/module.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * Robert Jenkin's hash function.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * https://burtleburtle.net/bob/hash/evahash.html
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * This is in the public domain.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #define mix(a, b, c) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) a = a - b; a = a - c; a = a ^ (c >> 13); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) b = b - c; b = b - a; b = b ^ (a << 8); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) c = c - a; c = c - b; c = c ^ (b >> 13); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) a = a - b; a = a - c; a = a ^ (c >> 12); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) b = b - c; b = b - a; b = b ^ (a << 16); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) c = c - a; c = c - b; c = c ^ (b >> 5); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) a = a - b; a = a - c; a = a ^ (c >> 3); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) b = b - c; b = b - a; b = b ^ (a << 10); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) c = c - a; c = c - b; c = c ^ (b >> 15); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) unsigned int ceph_str_hash_rjenkins(const char *str, unsigned int length)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) const unsigned char *k = (const unsigned char *)str;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) __u32 a, b, c; /* the internal state */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) __u32 len; /* how many key bytes still need mixing */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) /* Set up the internal state */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) len = length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) a = 0x9e3779b9; /* the golden ratio; an arbitrary value */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) b = a;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) c = 0; /* variable initialization of internal state */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) /* handle most of the key */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) while (len >= 12) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) a = a + (k[0] + ((__u32)k[1] << 8) + ((__u32)k[2] << 16) +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) ((__u32)k[3] << 24));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) b = b + (k[4] + ((__u32)k[5] << 8) + ((__u32)k[6] << 16) +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) ((__u32)k[7] << 24));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) c = c + (k[8] + ((__u32)k[9] << 8) + ((__u32)k[10] << 16) +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) ((__u32)k[11] << 24));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) mix(a, b, c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) k = k + 12;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) len = len - 12;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) /* handle the last 11 bytes */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) c = c + length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) switch (len) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) case 11:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) c = c + ((__u32)k[10] << 24);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) fallthrough;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) case 10:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) c = c + ((__u32)k[9] << 16);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) fallthrough;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) case 9:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) c = c + ((__u32)k[8] << 8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) /* the first byte of c is reserved for the length */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) fallthrough;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) case 8:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) b = b + ((__u32)k[7] << 24);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) fallthrough;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) case 7:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) b = b + ((__u32)k[6] << 16);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) fallthrough;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) case 6:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) b = b + ((__u32)k[5] << 8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) fallthrough;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) case 5:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) b = b + k[4];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) fallthrough;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) case 4:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) a = a + ((__u32)k[3] << 24);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) fallthrough;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) case 3:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) a = a + ((__u32)k[2] << 16);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) fallthrough;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) case 2:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) a = a + ((__u32)k[1] << 8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) fallthrough;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) case 1:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) a = a + k[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) /* case 0: nothing left to add */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) mix(a, b, c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) return c;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) * linux dcache hash
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) unsigned int ceph_str_hash_linux(const char *str, unsigned int length)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) unsigned long hash = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) unsigned char c;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) while (length--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) c = *str++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) hash = (hash + (c << 4) + (c >> 4)) * 11;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) return hash;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) }
^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) unsigned int ceph_str_hash(int type, const char *s, unsigned int len)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) switch (type) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) case CEPH_STR_HASH_LINUX:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) return ceph_str_hash_linux(s, len);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) case CEPH_STR_HASH_RJENKINS:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) return ceph_str_hash_rjenkins(s, len);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) default:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) EXPORT_SYMBOL(ceph_str_hash);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) const char *ceph_str_hash_name(int type)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) switch (type) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) case CEPH_STR_HASH_LINUX:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) return "linux";
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) case CEPH_STR_HASH_RJENKINS:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) return "rjenkins";
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) default:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) return "unknown";
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) EXPORT_SYMBOL(ceph_str_hash_name);
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags