jhash.c 3.6 KB

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