hash.c 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152
  1. #ifdef __KERNEL__
  2. # include <linux/crush/hash.h>
  3. #else
  4. # include "hash.h"
  5. #endif
  6. /*
  7. * Robert Jenkins' function for mixing 32-bit values
  8. * http://burtleburtle.net/bob/hash/evahash.html
  9. * a, b = random bits, c = input and output
  10. */
  11. #define crush_hashmix(a, b, c) do { \
  12. a = a-b; a = a-c; a = a^(c>>13); \
  13. b = b-c; b = b-a; b = b^(a<<8); \
  14. c = c-a; c = c-b; c = c^(b>>13); \
  15. a = a-b; a = a-c; a = a^(c>>12); \
  16. b = b-c; b = b-a; b = b^(a<<16); \
  17. c = c-a; c = c-b; c = c^(b>>5); \
  18. a = a-b; a = a-c; a = a^(c>>3); \
  19. b = b-c; b = b-a; b = b^(a<<10); \
  20. c = c-a; c = c-b; c = c^(b>>15); \
  21. } while (0)
  22. #define crush_hash_seed 1315423911
  23. static __u32 crush_hash32_rjenkins1(__u32 a)
  24. {
  25. __u32 hash = crush_hash_seed ^ a;
  26. __u32 b = a;
  27. __u32 x = 231232;
  28. __u32 y = 1232;
  29. crush_hashmix(b, x, hash);
  30. crush_hashmix(y, a, hash);
  31. return hash;
  32. }
  33. static __u32 crush_hash32_rjenkins1_2(__u32 a, __u32 b)
  34. {
  35. __u32 hash = crush_hash_seed ^ a ^ b;
  36. __u32 x = 231232;
  37. __u32 y = 1232;
  38. crush_hashmix(a, b, hash);
  39. crush_hashmix(x, a, hash);
  40. crush_hashmix(b, y, hash);
  41. return hash;
  42. }
  43. static __u32 crush_hash32_rjenkins1_3(__u32 a, __u32 b, __u32 c)
  44. {
  45. __u32 hash = crush_hash_seed ^ a ^ b ^ c;
  46. __u32 x = 231232;
  47. __u32 y = 1232;
  48. crush_hashmix(a, b, hash);
  49. crush_hashmix(c, x, hash);
  50. crush_hashmix(y, a, hash);
  51. crush_hashmix(b, x, hash);
  52. crush_hashmix(y, c, hash);
  53. return hash;
  54. }
  55. static __u32 crush_hash32_rjenkins1_4(__u32 a, __u32 b, __u32 c, __u32 d)
  56. {
  57. __u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d;
  58. __u32 x = 231232;
  59. __u32 y = 1232;
  60. crush_hashmix(a, b, hash);
  61. crush_hashmix(c, d, hash);
  62. crush_hashmix(a, x, hash);
  63. crush_hashmix(y, b, hash);
  64. crush_hashmix(c, x, hash);
  65. crush_hashmix(y, d, hash);
  66. return hash;
  67. }
  68. static __u32 crush_hash32_rjenkins1_5(__u32 a, __u32 b, __u32 c, __u32 d,
  69. __u32 e)
  70. {
  71. __u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d ^ e;
  72. __u32 x = 231232;
  73. __u32 y = 1232;
  74. crush_hashmix(a, b, hash);
  75. crush_hashmix(c, d, hash);
  76. crush_hashmix(e, x, hash);
  77. crush_hashmix(y, a, hash);
  78. crush_hashmix(b, x, hash);
  79. crush_hashmix(y, c, hash);
  80. crush_hashmix(d, x, hash);
  81. crush_hashmix(y, e, hash);
  82. return hash;
  83. }
  84. __u32 crush_hash32(int type, __u32 a)
  85. {
  86. switch (type) {
  87. case CRUSH_HASH_RJENKINS1:
  88. return crush_hash32_rjenkins1(a);
  89. default:
  90. return 0;
  91. }
  92. }
  93. __u32 crush_hash32_2(int type, __u32 a, __u32 b)
  94. {
  95. switch (type) {
  96. case CRUSH_HASH_RJENKINS1:
  97. return crush_hash32_rjenkins1_2(a, b);
  98. default:
  99. return 0;
  100. }
  101. }
  102. __u32 crush_hash32_3(int type, __u32 a, __u32 b, __u32 c)
  103. {
  104. switch (type) {
  105. case CRUSH_HASH_RJENKINS1:
  106. return crush_hash32_rjenkins1_3(a, b, c);
  107. default:
  108. return 0;
  109. }
  110. }
  111. __u32 crush_hash32_4(int type, __u32 a, __u32 b, __u32 c, __u32 d)
  112. {
  113. switch (type) {
  114. case CRUSH_HASH_RJENKINS1:
  115. return crush_hash32_rjenkins1_4(a, b, c, d);
  116. default:
  117. return 0;
  118. }
  119. }
  120. __u32 crush_hash32_5(int type, __u32 a, __u32 b, __u32 c, __u32 d, __u32 e)
  121. {
  122. switch (type) {
  123. case CRUSH_HASH_RJENKINS1:
  124. return crush_hash32_rjenkins1_5(a, b, c, d, e);
  125. default:
  126. return 0;
  127. }
  128. }
  129. const char *crush_hash_name(int type)
  130. {
  131. switch (type) {
  132. case CRUSH_HASH_RJENKINS1:
  133. return "rjenkins1";
  134. default:
  135. return "unknown";
  136. }
  137. }