jhash.h 3.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143
  1. #ifndef _LINUX_JHASH_H
  2. #define _LINUX_JHASH_H
  3. /* jhash.h: Jenkins hash support.
  4. *
  5. * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net)
  6. *
  7. * http://burtleburtle.net/bob/hash/
  8. *
  9. * These are the credits from Bob's sources:
  10. *
  11. * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
  12. * hash(), hash2(), hash3, and mix() are externally useful functions.
  13. * Routines to test the hash are included if SELF_TEST is defined.
  14. * You can use this free for any purpose. It has no warranty.
  15. *
  16. * Copyright (C) 2003 David S. Miller (davem@redhat.com)
  17. *
  18. * I've modified Bob's hash to be useful in the Linux kernel, and
  19. * any bugs present are surely my fault. -DaveM
  20. */
  21. /* NOTE: Arguments are modified. */
  22. #define __jhash_mix(a, b, c) \
  23. { \
  24. a -= b; a -= c; a ^= (c>>13); \
  25. b -= c; b -= a; b ^= (a<<8); \
  26. c -= a; c -= b; c ^= (b>>13); \
  27. a -= b; a -= c; a ^= (c>>12); \
  28. b -= c; b -= a; b ^= (a<<16); \
  29. c -= a; c -= b; c ^= (b>>5); \
  30. a -= b; a -= c; a ^= (c>>3); \
  31. b -= c; b -= a; b ^= (a<<10); \
  32. c -= a; c -= b; c ^= (b>>15); \
  33. }
  34. /* The golden ration: an arbitrary value */
  35. #define JHASH_GOLDEN_RATIO 0x9e3779b9
  36. /* The most generic version, hashes an arbitrary sequence
  37. * of bytes. No alignment or length assumptions are made about
  38. * the input key.
  39. */
  40. static inline u32 jhash(const void *key, u32 length, u32 initval)
  41. {
  42. u32 a, b, c, len;
  43. const u8 *k = key;
  44. len = length;
  45. a = b = JHASH_GOLDEN_RATIO;
  46. c = initval;
  47. while (len >= 12) {
  48. a += (k[0] +((u32)k[1]<<8) +((u32)k[2]<<16) +((u32)k[3]<<24));
  49. b += (k[4] +((u32)k[5]<<8) +((u32)k[6]<<16) +((u32)k[7]<<24));
  50. c += (k[8] +((u32)k[9]<<8) +((u32)k[10]<<16)+((u32)k[11]<<24));
  51. __jhash_mix(a,b,c);
  52. k += 12;
  53. len -= 12;
  54. }
  55. c += length;
  56. switch (len) {
  57. case 11: c += ((u32)k[10]<<24);
  58. case 10: c += ((u32)k[9]<<16);
  59. case 9 : c += ((u32)k[8]<<8);
  60. case 8 : b += ((u32)k[7]<<24);
  61. case 7 : b += ((u32)k[6]<<16);
  62. case 6 : b += ((u32)k[5]<<8);
  63. case 5 : b += k[4];
  64. case 4 : a += ((u32)k[3]<<24);
  65. case 3 : a += ((u32)k[2]<<16);
  66. case 2 : a += ((u32)k[1]<<8);
  67. case 1 : a += k[0];
  68. };
  69. __jhash_mix(a,b,c);
  70. return c;
  71. }
  72. /* A special optimized version that handles 1 or more of u32s.
  73. * The length parameter here is the number of u32s in the key.
  74. */
  75. static inline u32 jhash2(u32 *k, u32 length, u32 initval)
  76. {
  77. u32 a, b, c, len;
  78. a = b = JHASH_GOLDEN_RATIO;
  79. c = initval;
  80. len = length;
  81. while (len >= 3) {
  82. a += k[0];
  83. b += k[1];
  84. c += k[2];
  85. __jhash_mix(a, b, c);
  86. k += 3; len -= 3;
  87. }
  88. c += length * 4;
  89. switch (len) {
  90. case 2 : b += k[1];
  91. case 1 : a += k[0];
  92. };
  93. __jhash_mix(a,b,c);
  94. return c;
  95. }
  96. /* A special ultra-optimized versions that knows they are hashing exactly
  97. * 3, 2 or 1 word(s).
  98. *
  99. * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
  100. * done at the end is not done here.
  101. */
  102. static inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval)
  103. {
  104. a += JHASH_GOLDEN_RATIO;
  105. b += JHASH_GOLDEN_RATIO;
  106. c += initval;
  107. __jhash_mix(a, b, c);
  108. return c;
  109. }
  110. static inline u32 jhash_2words(u32 a, u32 b, u32 initval)
  111. {
  112. return jhash_3words(a, b, 0, initval);
  113. }
  114. static inline u32 jhash_1word(u32 a, u32 initval)
  115. {
  116. return jhash_3words(a, 0, 0, initval);
  117. }
  118. #endif /* _LINUX_JHASH_H */