cmetrohash64.c 5.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184
  1. // metrohash64.cpp
  2. //
  3. // The MIT License (MIT)
  4. //
  5. // Copyright (c) 2015 J. Andrew Rogers
  6. //
  7. // Permission is hereby granted, free of charge, to any person obtaining a copy
  8. // of this software and associated documentation files (the "Software"), to deal
  9. // in the Software without restriction, including without limitation the rights
  10. // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11. // copies of the Software, and to permit persons to whom the Software is
  12. // furnished to do so, subject to the following conditions:
  13. //
  14. // The above copyright notice and this permission notice shall be included in all
  15. // copies or substantial portions of the Software.
  16. //
  17. // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18. // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19. // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20. // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21. // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22. // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  23. // SOFTWARE.
  24. //
  25. #include "cmetrohash.h"
  26. void cmetrohash64_1(const uint8_t * key, uint64_t len, uint32_t seed, uint8_t * out)
  27. {
  28. static const uint64_t k0 = 0xC83A91E1;
  29. static const uint64_t k1 = 0x8648DBDB;
  30. static const uint64_t k2 = 0x7BDEC03B;
  31. static const uint64_t k3 = 0x2F5870A5;
  32. const uint8_t * ptr = key;
  33. const uint8_t * const end = ptr + len;
  34. uint64_t hash = ((((uint64_t) seed) + k2) * k0) + len;
  35. if (len >= 32)
  36. {
  37. uint64_t v[4];
  38. v[0] = hash;
  39. v[1] = hash;
  40. v[2] = hash;
  41. v[3] = hash;
  42. do
  43. {
  44. v[0] += cread_u64(ptr) * k0; ptr += 8; v[0] = crotate_right(v[0],29) + v[2];
  45. v[1] += cread_u64(ptr) * k1; ptr += 8; v[1] = crotate_right(v[1],29) + v[3];
  46. v[2] += cread_u64(ptr) * k2; ptr += 8; v[2] = crotate_right(v[2],29) + v[0];
  47. v[3] += cread_u64(ptr) * k3; ptr += 8; v[3] = crotate_right(v[3],29) + v[1];
  48. }
  49. while (ptr <= (end - 32));
  50. v[2] ^= crotate_right(((v[0] + v[3]) * k0) + v[1], 33) * k1;
  51. v[3] ^= crotate_right(((v[1] + v[2]) * k1) + v[0], 33) * k0;
  52. v[0] ^= crotate_right(((v[0] + v[2]) * k0) + v[3], 33) * k1;
  53. v[1] ^= crotate_right(((v[1] + v[3]) * k1) + v[2], 33) * k0;
  54. hash += v[0] ^ v[1];
  55. }
  56. if ((end - ptr) >= 16)
  57. {
  58. uint64_t v0 = hash + (cread_u64(ptr) * k0); ptr += 8; v0 = crotate_right(v0,33) * k1;
  59. uint64_t v1 = hash + (cread_u64(ptr) * k1); ptr += 8; v1 = crotate_right(v1,33) * k2;
  60. v0 ^= crotate_right(v0 * k0, 35) + v1;
  61. v1 ^= crotate_right(v1 * k3, 35) + v0;
  62. hash += v1;
  63. }
  64. if ((end - ptr) >= 8)
  65. {
  66. hash += cread_u64(ptr) * k3; ptr += 8;
  67. hash ^= crotate_right(hash, 33) * k1;
  68. }
  69. if ((end - ptr) >= 4)
  70. {
  71. hash += cread_u32(ptr) * k3; ptr += 4;
  72. hash ^= crotate_right(hash, 15) * k1;
  73. }
  74. if ((end - ptr) >= 2)
  75. {
  76. hash += cread_u16(ptr) * k3; ptr += 2;
  77. hash ^= crotate_right(hash, 13) * k1;
  78. }
  79. if ((end - ptr) >= 1)
  80. {
  81. hash += cread_u8 (ptr) * k3;
  82. hash ^= crotate_right(hash, 25) * k1;
  83. }
  84. hash ^= crotate_right(hash, 33);
  85. hash *= k0;
  86. hash ^= crotate_right(hash, 33);
  87. memcpy(out, &hash, 8);
  88. }
  89. void cmetrohash64_2(const uint8_t * key, uint64_t len, uint32_t seed, uint8_t * out)
  90. {
  91. static const uint64_t k0 = 0xD6D018F5;
  92. static const uint64_t k1 = 0xA2AA033B;
  93. static const uint64_t k2 = 0x62992FC1;
  94. static const uint64_t k3 = 0x30BC5B29;
  95. const uint8_t * ptr = key;
  96. const uint8_t * const end = ptr + len;
  97. uint64_t hash = ((((uint64_t) seed) + k2) * k0) + len;
  98. if (len >= 32)
  99. {
  100. uint64_t v[4];
  101. v[0] = hash;
  102. v[1] = hash;
  103. v[2] = hash;
  104. v[3] = hash;
  105. do
  106. {
  107. v[0] += cread_u64(ptr) * k0; ptr += 8; v[0] = crotate_right(v[0],29) + v[2];
  108. v[1] += cread_u64(ptr) * k1; ptr += 8; v[1] = crotate_right(v[1],29) + v[3];
  109. v[2] += cread_u64(ptr) * k2; ptr += 8; v[2] = crotate_right(v[2],29) + v[0];
  110. v[3] += cread_u64(ptr) * k3; ptr += 8; v[3] = crotate_right(v[3],29) + v[1];
  111. }
  112. while (ptr <= (end - 32));
  113. v[2] ^= crotate_right(((v[0] + v[3]) * k0) + v[1], 30) * k1;
  114. v[3] ^= crotate_right(((v[1] + v[2]) * k1) + v[0], 30) * k0;
  115. v[0] ^= crotate_right(((v[0] + v[2]) * k0) + v[3], 30) * k1;
  116. v[1] ^= crotate_right(((v[1] + v[3]) * k1) + v[2], 30) * k0;
  117. hash += v[0] ^ v[1];
  118. }
  119. if ((end - ptr) >= 16)
  120. {
  121. uint64_t v0 = hash + (cread_u64(ptr) * k2); ptr += 8; v0 = crotate_right(v0,29) * k3;
  122. uint64_t v1 = hash + (cread_u64(ptr) * k2); ptr += 8; v1 = crotate_right(v1,29) * k3;
  123. v0 ^= crotate_right(v0 * k0, 34) + v1;
  124. v1 ^= crotate_right(v1 * k3, 34) + v0;
  125. hash += v1;
  126. }
  127. if ((end - ptr) >= 8)
  128. {
  129. hash += cread_u64(ptr) * k3; ptr += 8;
  130. hash ^= crotate_right(hash, 36) * k1;
  131. }
  132. if ((end - ptr) >= 4)
  133. {
  134. hash += cread_u32(ptr) * k3; ptr += 4;
  135. hash ^= crotate_right(hash, 15) * k1;
  136. }
  137. if ((end - ptr) >= 2)
  138. {
  139. hash += cread_u16(ptr) * k3; ptr += 2;
  140. hash ^= crotate_right(hash, 15) * k1;
  141. }
  142. if ((end - ptr) >= 1)
  143. {
  144. hash += cread_u8 (ptr) * k3;
  145. hash ^= crotate_right(hash, 23) * k1;
  146. }
  147. hash ^= crotate_right(hash, 28);
  148. hash *= k0;
  149. hash ^= crotate_right(hash, 29);
  150. memcpy(out, &hash, 8);
  151. }