xxhash.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467
  1. // SPDX-License-Identifier: (GPL-2.0 or BSD-2-Clause)
  2. /*
  3. * xxHash - Extremely Fast Hash algorithm
  4. * Copyright (C) 2012-2016, Yann Collet.
  5. *
  6. * You can contact the author at:
  7. * - xxHash homepage: http://cyan4973.github.io/xxHash/
  8. * - xxHash source repository: https://github.com/Cyan4973/xxHash
  9. */
  10. #include <asm/unaligned.h>
  11. #include <linux/errno.h>
  12. #include <linux/compiler.h>
  13. #include <linux/kernel.h>
  14. #include <linux/compat.h>
  15. #include <linux/string.h>
  16. #include <linux/xxhash.h>
  17. /*-*************************************
  18. * Macros
  19. **************************************/
  20. #define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r)))
  21. #define xxh_rotl64(x, r) ((x << r) | (x >> (64 - r)))
  22. #ifdef __LITTLE_ENDIAN
  23. # define XXH_CPU_LITTLE_ENDIAN 1
  24. #else
  25. # define XXH_CPU_LITTLE_ENDIAN 0
  26. #endif
  27. /*-*************************************
  28. * Constants
  29. **************************************/
  30. static const uint32_t PRIME32_1 = 2654435761U;
  31. static const uint32_t PRIME32_2 = 2246822519U;
  32. static const uint32_t PRIME32_3 = 3266489917U;
  33. static const uint32_t PRIME32_4 = 668265263U;
  34. static const uint32_t PRIME32_5 = 374761393U;
  35. static const uint64_t PRIME64_1 = 11400714785074694791ULL;
  36. static const uint64_t PRIME64_2 = 14029467366897019727ULL;
  37. static const uint64_t PRIME64_3 = 1609587929392839161ULL;
  38. static const uint64_t PRIME64_4 = 9650029242287828579ULL;
  39. static const uint64_t PRIME64_5 = 2870177450012600261ULL;
  40. /*-**************************
  41. * Utils
  42. ***************************/
  43. void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src)
  44. {
  45. memcpy(dst, src, sizeof(*dst));
  46. }
  47. EXPORT_SYMBOL(xxh32_copy_state);
  48. void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src)
  49. {
  50. memcpy(dst, src, sizeof(*dst));
  51. }
  52. EXPORT_SYMBOL(xxh64_copy_state);
  53. /*-***************************
  54. * Simple Hash Functions
  55. ****************************/
  56. static uint32_t xxh32_round(uint32_t seed, const uint32_t input)
  57. {
  58. seed += input * PRIME32_2;
  59. seed = xxh_rotl32(seed, 13);
  60. seed *= PRIME32_1;
  61. return seed;
  62. }
  63. uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)
  64. {
  65. const uint8_t *p = (const uint8_t *)input;
  66. const uint8_t *b_end = p + len;
  67. uint32_t h32;
  68. if (len >= 16) {
  69. const uint8_t *const limit = b_end - 16;
  70. uint32_t v1 = seed + PRIME32_1 + PRIME32_2;
  71. uint32_t v2 = seed + PRIME32_2;
  72. uint32_t v3 = seed + 0;
  73. uint32_t v4 = seed - PRIME32_1;
  74. do {
  75. v1 = xxh32_round(v1, get_unaligned_le32(p));
  76. p += 4;
  77. v2 = xxh32_round(v2, get_unaligned_le32(p));
  78. p += 4;
  79. v3 = xxh32_round(v3, get_unaligned_le32(p));
  80. p += 4;
  81. v4 = xxh32_round(v4, get_unaligned_le32(p));
  82. p += 4;
  83. } while (p <= limit);
  84. h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) +
  85. xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18);
  86. } else {
  87. h32 = seed + PRIME32_5;
  88. }
  89. h32 += (uint32_t)len;
  90. while (p + 4 <= b_end) {
  91. h32 += get_unaligned_le32(p) * PRIME32_3;
  92. h32 = xxh_rotl32(h32, 17) * PRIME32_4;
  93. p += 4;
  94. }
  95. while (p < b_end) {
  96. h32 += (*p) * PRIME32_5;
  97. h32 = xxh_rotl32(h32, 11) * PRIME32_1;
  98. p++;
  99. }
  100. h32 ^= h32 >> 15;
  101. h32 *= PRIME32_2;
  102. h32 ^= h32 >> 13;
  103. h32 *= PRIME32_3;
  104. h32 ^= h32 >> 16;
  105. return h32;
  106. }
  107. EXPORT_SYMBOL(xxh32);
  108. static uint64_t xxh64_round(uint64_t acc, const uint64_t input)
  109. {
  110. acc += input * PRIME64_2;
  111. acc = xxh_rotl64(acc, 31);
  112. acc *= PRIME64_1;
  113. return acc;
  114. }
  115. static uint64_t xxh64_merge_round(uint64_t acc, uint64_t val)
  116. {
  117. val = xxh64_round(0, val);
  118. acc ^= val;
  119. acc = acc * PRIME64_1 + PRIME64_4;
  120. return acc;
  121. }
  122. uint64_t xxh64(const void *input, const size_t len, const uint64_t seed)
  123. {
  124. const uint8_t *p = (const uint8_t *)input;
  125. const uint8_t *const b_end = p + len;
  126. uint64_t h64;
  127. if (len >= 32) {
  128. const uint8_t *const limit = b_end - 32;
  129. uint64_t v1 = seed + PRIME64_1 + PRIME64_2;
  130. uint64_t v2 = seed + PRIME64_2;
  131. uint64_t v3 = seed + 0;
  132. uint64_t v4 = seed - PRIME64_1;
  133. do {
  134. v1 = xxh64_round(v1, get_unaligned_le64(p));
  135. p += 8;
  136. v2 = xxh64_round(v2, get_unaligned_le64(p));
  137. p += 8;
  138. v3 = xxh64_round(v3, get_unaligned_le64(p));
  139. p += 8;
  140. v4 = xxh64_round(v4, get_unaligned_le64(p));
  141. p += 8;
  142. } while (p <= limit);
  143. h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
  144. xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
  145. h64 = xxh64_merge_round(h64, v1);
  146. h64 = xxh64_merge_round(h64, v2);
  147. h64 = xxh64_merge_round(h64, v3);
  148. h64 = xxh64_merge_round(h64, v4);
  149. } else {
  150. h64 = seed + PRIME64_5;
  151. }
  152. h64 += (uint64_t)len;
  153. while (p + 8 <= b_end) {
  154. const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
  155. h64 ^= k1;
  156. h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
  157. p += 8;
  158. }
  159. if (p + 4 <= b_end) {
  160. h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
  161. h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
  162. p += 4;
  163. }
  164. while (p < b_end) {
  165. h64 ^= (*p) * PRIME64_5;
  166. h64 = xxh_rotl64(h64, 11) * PRIME64_1;
  167. p++;
  168. }
  169. h64 ^= h64 >> 33;
  170. h64 *= PRIME64_2;
  171. h64 ^= h64 >> 29;
  172. h64 *= PRIME64_3;
  173. h64 ^= h64 >> 32;
  174. return h64;
  175. }
  176. EXPORT_SYMBOL(xxh64);
  177. /*-**************************************************
  178. * Advanced Hash Functions
  179. ***************************************************/
  180. void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed)
  181. {
  182. /* use a local state for memcpy() to avoid strict-aliasing warnings */
  183. struct xxh32_state state;
  184. memset(&state, 0, sizeof(state));
  185. state.v1 = seed + PRIME32_1 + PRIME32_2;
  186. state.v2 = seed + PRIME32_2;
  187. state.v3 = seed + 0;
  188. state.v4 = seed - PRIME32_1;
  189. memcpy(statePtr, &state, sizeof(state));
  190. }
  191. EXPORT_SYMBOL(xxh32_reset);
  192. void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed)
  193. {
  194. /* use a local state for memcpy() to avoid strict-aliasing warnings */
  195. struct xxh64_state state;
  196. memset(&state, 0, sizeof(state));
  197. state.v1 = seed + PRIME64_1 + PRIME64_2;
  198. state.v2 = seed + PRIME64_2;
  199. state.v3 = seed + 0;
  200. state.v4 = seed - PRIME64_1;
  201. memcpy(statePtr, &state, sizeof(state));
  202. }
  203. EXPORT_SYMBOL(xxh64_reset);
  204. int xxh32_update(struct xxh32_state *state, const void *input, const size_t len)
  205. {
  206. const uint8_t *p = (const uint8_t *)input;
  207. const uint8_t *const b_end = p + len;
  208. if (input == NULL)
  209. return -EINVAL;
  210. state->total_len_32 += (uint32_t)len;
  211. state->large_len |= (len >= 16) | (state->total_len_32 >= 16);
  212. if (state->memsize + len < 16) { /* fill in tmp buffer */
  213. memcpy((uint8_t *)(state->mem32) + state->memsize, input, len);
  214. state->memsize += (uint32_t)len;
  215. return 0;
  216. }
  217. if (state->memsize) { /* some data left from previous update */
  218. const uint32_t *p32 = state->mem32;
  219. memcpy((uint8_t *)(state->mem32) + state->memsize, input,
  220. 16 - state->memsize);
  221. state->v1 = xxh32_round(state->v1, get_unaligned_le32(p32));
  222. p32++;
  223. state->v2 = xxh32_round(state->v2, get_unaligned_le32(p32));
  224. p32++;
  225. state->v3 = xxh32_round(state->v3, get_unaligned_le32(p32));
  226. p32++;
  227. state->v4 = xxh32_round(state->v4, get_unaligned_le32(p32));
  228. p32++;
  229. p += 16-state->memsize;
  230. state->memsize = 0;
  231. }
  232. if (p <= b_end - 16) {
  233. const uint8_t *const limit = b_end - 16;
  234. uint32_t v1 = state->v1;
  235. uint32_t v2 = state->v2;
  236. uint32_t v3 = state->v3;
  237. uint32_t v4 = state->v4;
  238. do {
  239. v1 = xxh32_round(v1, get_unaligned_le32(p));
  240. p += 4;
  241. v2 = xxh32_round(v2, get_unaligned_le32(p));
  242. p += 4;
  243. v3 = xxh32_round(v3, get_unaligned_le32(p));
  244. p += 4;
  245. v4 = xxh32_round(v4, get_unaligned_le32(p));
  246. p += 4;
  247. } while (p <= limit);
  248. state->v1 = v1;
  249. state->v2 = v2;
  250. state->v3 = v3;
  251. state->v4 = v4;
  252. }
  253. if (p < b_end) {
  254. memcpy(state->mem32, p, (size_t)(b_end-p));
  255. state->memsize = (uint32_t)(b_end-p);
  256. }
  257. return 0;
  258. }
  259. EXPORT_SYMBOL(xxh32_update);
  260. uint32_t xxh32_digest(const struct xxh32_state *state)
  261. {
  262. const uint8_t *p = (const uint8_t *)state->mem32;
  263. const uint8_t *const b_end = (const uint8_t *)(state->mem32) +
  264. state->memsize;
  265. uint32_t h32;
  266. if (state->large_len) {
  267. h32 = xxh_rotl32(state->v1, 1) + xxh_rotl32(state->v2, 7) +
  268. xxh_rotl32(state->v3, 12) + xxh_rotl32(state->v4, 18);
  269. } else {
  270. h32 = state->v3 /* == seed */ + PRIME32_5;
  271. }
  272. h32 += state->total_len_32;
  273. while (p + 4 <= b_end) {
  274. h32 += get_unaligned_le32(p) * PRIME32_3;
  275. h32 = xxh_rotl32(h32, 17) * PRIME32_4;
  276. p += 4;
  277. }
  278. while (p < b_end) {
  279. h32 += (*p) * PRIME32_5;
  280. h32 = xxh_rotl32(h32, 11) * PRIME32_1;
  281. p++;
  282. }
  283. h32 ^= h32 >> 15;
  284. h32 *= PRIME32_2;
  285. h32 ^= h32 >> 13;
  286. h32 *= PRIME32_3;
  287. h32 ^= h32 >> 16;
  288. return h32;
  289. }
  290. EXPORT_SYMBOL(xxh32_digest);
  291. int xxh64_update(struct xxh64_state *state, const void *input, const size_t len)
  292. {
  293. const uint8_t *p = (const uint8_t *)input;
  294. const uint8_t *const b_end = p + len;
  295. if (input == NULL)
  296. return -EINVAL;
  297. state->total_len += len;
  298. if (state->memsize + len < 32) { /* fill in tmp buffer */
  299. memcpy(((uint8_t *)state->mem64) + state->memsize, input, len);
  300. state->memsize += (uint32_t)len;
  301. return 0;
  302. }
  303. if (state->memsize) { /* tmp buffer is full */
  304. uint64_t *p64 = state->mem64;
  305. memcpy(((uint8_t *)p64) + state->memsize, input,
  306. 32 - state->memsize);
  307. state->v1 = xxh64_round(state->v1, get_unaligned_le64(p64));
  308. p64++;
  309. state->v2 = xxh64_round(state->v2, get_unaligned_le64(p64));
  310. p64++;
  311. state->v3 = xxh64_round(state->v3, get_unaligned_le64(p64));
  312. p64++;
  313. state->v4 = xxh64_round(state->v4, get_unaligned_le64(p64));
  314. p += 32 - state->memsize;
  315. state->memsize = 0;
  316. }
  317. if (p + 32 <= b_end) {
  318. const uint8_t *const limit = b_end - 32;
  319. uint64_t v1 = state->v1;
  320. uint64_t v2 = state->v2;
  321. uint64_t v3 = state->v3;
  322. uint64_t v4 = state->v4;
  323. do {
  324. v1 = xxh64_round(v1, get_unaligned_le64(p));
  325. p += 8;
  326. v2 = xxh64_round(v2, get_unaligned_le64(p));
  327. p += 8;
  328. v3 = xxh64_round(v3, get_unaligned_le64(p));
  329. p += 8;
  330. v4 = xxh64_round(v4, get_unaligned_le64(p));
  331. p += 8;
  332. } while (p <= limit);
  333. state->v1 = v1;
  334. state->v2 = v2;
  335. state->v3 = v3;
  336. state->v4 = v4;
  337. }
  338. if (p < b_end) {
  339. memcpy(state->mem64, p, (size_t)(b_end-p));
  340. state->memsize = (uint32_t)(b_end - p);
  341. }
  342. return 0;
  343. }
  344. EXPORT_SYMBOL(xxh64_update);
  345. uint64_t xxh64_digest(const struct xxh64_state *state)
  346. {
  347. const uint8_t *p = (const uint8_t *)state->mem64;
  348. const uint8_t *const b_end = (const uint8_t *)state->mem64 +
  349. state->memsize;
  350. uint64_t h64;
  351. if (state->total_len >= 32) {
  352. const uint64_t v1 = state->v1;
  353. const uint64_t v2 = state->v2;
  354. const uint64_t v3 = state->v3;
  355. const uint64_t v4 = state->v4;
  356. h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
  357. xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
  358. h64 = xxh64_merge_round(h64, v1);
  359. h64 = xxh64_merge_round(h64, v2);
  360. h64 = xxh64_merge_round(h64, v3);
  361. h64 = xxh64_merge_round(h64, v4);
  362. } else {
  363. h64 = state->v3 + PRIME64_5;
  364. }
  365. h64 += (uint64_t)state->total_len;
  366. while (p + 8 <= b_end) {
  367. const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
  368. h64 ^= k1;
  369. h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
  370. p += 8;
  371. }
  372. if (p + 4 <= b_end) {
  373. h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
  374. h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
  375. p += 4;
  376. }
  377. while (p < b_end) {
  378. h64 ^= (*p) * PRIME64_5;
  379. h64 = xxh_rotl64(h64, 11) * PRIME64_1;
  380. p++;
  381. }
  382. h64 ^= h64 >> 33;
  383. h64 *= PRIME64_2;
  384. h64 ^= h64 >> 29;
  385. h64 *= PRIME64_3;
  386. h64 ^= h64 >> 32;
  387. return h64;
  388. }
  389. EXPORT_SYMBOL(xxh64_digest);