xxhash.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500
  1. /*
  2. * xxHash - Extremely Fast Hash algorithm
  3. * Copyright (C) 2012-2016, Yann Collet.
  4. *
  5. * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
  6. *
  7. * Redistribution and use in source and binary forms, with or without
  8. * modification, are permitted provided that the following conditions are
  9. * met:
  10. *
  11. * * Redistributions of source code must retain the above copyright
  12. * notice, this list of conditions and the following disclaimer.
  13. * * Redistributions in binary form must reproduce the above
  14. * copyright notice, this list of conditions and the following disclaimer
  15. * in the documentation and/or other materials provided with the
  16. * distribution.
  17. *
  18. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19. * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20. * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21. * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22. * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23. * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24. * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25. * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26. * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28. * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29. *
  30. * This program is free software; you can redistribute it and/or modify it under
  31. * the terms of the GNU General Public License version 2 as published by the
  32. * Free Software Foundation. This program is dual-licensed; you may select
  33. * either version 2 of the GNU General Public License ("GPL") or BSD license
  34. * ("BSD").
  35. *
  36. * You can contact the author at:
  37. * - xxHash homepage: https://cyan4973.github.io/xxHash/
  38. * - xxHash source repository: https://github.com/Cyan4973/xxHash
  39. */
  40. #include <asm/unaligned.h>
  41. #include <linux/errno.h>
  42. #include <linux/compiler.h>
  43. #include <linux/kernel.h>
  44. #include <linux/module.h>
  45. #include <linux/string.h>
  46. #include <linux/xxhash.h>
  47. /*-*************************************
  48. * Macros
  49. **************************************/
  50. #define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r)))
  51. #define xxh_rotl64(x, r) ((x << r) | (x >> (64 - r)))
  52. #ifdef __LITTLE_ENDIAN
  53. # define XXH_CPU_LITTLE_ENDIAN 1
  54. #else
  55. # define XXH_CPU_LITTLE_ENDIAN 0
  56. #endif
  57. /*-*************************************
  58. * Constants
  59. **************************************/
  60. static const uint32_t PRIME32_1 = 2654435761U;
  61. static const uint32_t PRIME32_2 = 2246822519U;
  62. static const uint32_t PRIME32_3 = 3266489917U;
  63. static const uint32_t PRIME32_4 = 668265263U;
  64. static const uint32_t PRIME32_5 = 374761393U;
  65. static const uint64_t PRIME64_1 = 11400714785074694791ULL;
  66. static const uint64_t PRIME64_2 = 14029467366897019727ULL;
  67. static const uint64_t PRIME64_3 = 1609587929392839161ULL;
  68. static const uint64_t PRIME64_4 = 9650029242287828579ULL;
  69. static const uint64_t PRIME64_5 = 2870177450012600261ULL;
  70. /*-**************************
  71. * Utils
  72. ***************************/
  73. void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src)
  74. {
  75. memcpy(dst, src, sizeof(*dst));
  76. }
  77. EXPORT_SYMBOL(xxh32_copy_state);
  78. void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src)
  79. {
  80. memcpy(dst, src, sizeof(*dst));
  81. }
  82. EXPORT_SYMBOL(xxh64_copy_state);
  83. /*-***************************
  84. * Simple Hash Functions
  85. ****************************/
  86. static uint32_t xxh32_round(uint32_t seed, const uint32_t input)
  87. {
  88. seed += input * PRIME32_2;
  89. seed = xxh_rotl32(seed, 13);
  90. seed *= PRIME32_1;
  91. return seed;
  92. }
  93. uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)
  94. {
  95. const uint8_t *p = (const uint8_t *)input;
  96. const uint8_t *b_end = p + len;
  97. uint32_t h32;
  98. if (len >= 16) {
  99. const uint8_t *const limit = b_end - 16;
  100. uint32_t v1 = seed + PRIME32_1 + PRIME32_2;
  101. uint32_t v2 = seed + PRIME32_2;
  102. uint32_t v3 = seed + 0;
  103. uint32_t v4 = seed - PRIME32_1;
  104. do {
  105. v1 = xxh32_round(v1, get_unaligned_le32(p));
  106. p += 4;
  107. v2 = xxh32_round(v2, get_unaligned_le32(p));
  108. p += 4;
  109. v3 = xxh32_round(v3, get_unaligned_le32(p));
  110. p += 4;
  111. v4 = xxh32_round(v4, get_unaligned_le32(p));
  112. p += 4;
  113. } while (p <= limit);
  114. h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) +
  115. xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18);
  116. } else {
  117. h32 = seed + PRIME32_5;
  118. }
  119. h32 += (uint32_t)len;
  120. while (p + 4 <= b_end) {
  121. h32 += get_unaligned_le32(p) * PRIME32_3;
  122. h32 = xxh_rotl32(h32, 17) * PRIME32_4;
  123. p += 4;
  124. }
  125. while (p < b_end) {
  126. h32 += (*p) * PRIME32_5;
  127. h32 = xxh_rotl32(h32, 11) * PRIME32_1;
  128. p++;
  129. }
  130. h32 ^= h32 >> 15;
  131. h32 *= PRIME32_2;
  132. h32 ^= h32 >> 13;
  133. h32 *= PRIME32_3;
  134. h32 ^= h32 >> 16;
  135. return h32;
  136. }
  137. EXPORT_SYMBOL(xxh32);
  138. static uint64_t xxh64_round(uint64_t acc, const uint64_t input)
  139. {
  140. acc += input * PRIME64_2;
  141. acc = xxh_rotl64(acc, 31);
  142. acc *= PRIME64_1;
  143. return acc;
  144. }
  145. static uint64_t xxh64_merge_round(uint64_t acc, uint64_t val)
  146. {
  147. val = xxh64_round(0, val);
  148. acc ^= val;
  149. acc = acc * PRIME64_1 + PRIME64_4;
  150. return acc;
  151. }
  152. uint64_t xxh64(const void *input, const size_t len, const uint64_t seed)
  153. {
  154. const uint8_t *p = (const uint8_t *)input;
  155. const uint8_t *const b_end = p + len;
  156. uint64_t h64;
  157. if (len >= 32) {
  158. const uint8_t *const limit = b_end - 32;
  159. uint64_t v1 = seed + PRIME64_1 + PRIME64_2;
  160. uint64_t v2 = seed + PRIME64_2;
  161. uint64_t v3 = seed + 0;
  162. uint64_t v4 = seed - PRIME64_1;
  163. do {
  164. v1 = xxh64_round(v1, get_unaligned_le64(p));
  165. p += 8;
  166. v2 = xxh64_round(v2, get_unaligned_le64(p));
  167. p += 8;
  168. v3 = xxh64_round(v3, get_unaligned_le64(p));
  169. p += 8;
  170. v4 = xxh64_round(v4, get_unaligned_le64(p));
  171. p += 8;
  172. } while (p <= limit);
  173. h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
  174. xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
  175. h64 = xxh64_merge_round(h64, v1);
  176. h64 = xxh64_merge_round(h64, v2);
  177. h64 = xxh64_merge_round(h64, v3);
  178. h64 = xxh64_merge_round(h64, v4);
  179. } else {
  180. h64 = seed + PRIME64_5;
  181. }
  182. h64 += (uint64_t)len;
  183. while (p + 8 <= b_end) {
  184. const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
  185. h64 ^= k1;
  186. h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
  187. p += 8;
  188. }
  189. if (p + 4 <= b_end) {
  190. h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
  191. h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
  192. p += 4;
  193. }
  194. while (p < b_end) {
  195. h64 ^= (*p) * PRIME64_5;
  196. h64 = xxh_rotl64(h64, 11) * PRIME64_1;
  197. p++;
  198. }
  199. h64 ^= h64 >> 33;
  200. h64 *= PRIME64_2;
  201. h64 ^= h64 >> 29;
  202. h64 *= PRIME64_3;
  203. h64 ^= h64 >> 32;
  204. return h64;
  205. }
  206. EXPORT_SYMBOL(xxh64);
  207. /*-**************************************************
  208. * Advanced Hash Functions
  209. ***************************************************/
  210. void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed)
  211. {
  212. /* use a local state for memcpy() to avoid strict-aliasing warnings */
  213. struct xxh32_state state;
  214. memset(&state, 0, sizeof(state));
  215. state.v1 = seed + PRIME32_1 + PRIME32_2;
  216. state.v2 = seed + PRIME32_2;
  217. state.v3 = seed + 0;
  218. state.v4 = seed - PRIME32_1;
  219. memcpy(statePtr, &state, sizeof(state));
  220. }
  221. EXPORT_SYMBOL(xxh32_reset);
  222. void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed)
  223. {
  224. /* use a local state for memcpy() to avoid strict-aliasing warnings */
  225. struct xxh64_state state;
  226. memset(&state, 0, sizeof(state));
  227. state.v1 = seed + PRIME64_1 + PRIME64_2;
  228. state.v2 = seed + PRIME64_2;
  229. state.v3 = seed + 0;
  230. state.v4 = seed - PRIME64_1;
  231. memcpy(statePtr, &state, sizeof(state));
  232. }
  233. EXPORT_SYMBOL(xxh64_reset);
  234. int xxh32_update(struct xxh32_state *state, const void *input, const size_t len)
  235. {
  236. const uint8_t *p = (const uint8_t *)input;
  237. const uint8_t *const b_end = p + len;
  238. if (input == NULL)
  239. return -EINVAL;
  240. state->total_len_32 += (uint32_t)len;
  241. state->large_len |= (len >= 16) | (state->total_len_32 >= 16);
  242. if (state->memsize + len < 16) { /* fill in tmp buffer */
  243. memcpy((uint8_t *)(state->mem32) + state->memsize, input, len);
  244. state->memsize += (uint32_t)len;
  245. return 0;
  246. }
  247. if (state->memsize) { /* some data left from previous update */
  248. const uint32_t *p32 = state->mem32;
  249. memcpy((uint8_t *)(state->mem32) + state->memsize, input,
  250. 16 - state->memsize);
  251. state->v1 = xxh32_round(state->v1, get_unaligned_le32(p32));
  252. p32++;
  253. state->v2 = xxh32_round(state->v2, get_unaligned_le32(p32));
  254. p32++;
  255. state->v3 = xxh32_round(state->v3, get_unaligned_le32(p32));
  256. p32++;
  257. state->v4 = xxh32_round(state->v4, get_unaligned_le32(p32));
  258. p32++;
  259. p += 16-state->memsize;
  260. state->memsize = 0;
  261. }
  262. if (p <= b_end - 16) {
  263. const uint8_t *const limit = b_end - 16;
  264. uint32_t v1 = state->v1;
  265. uint32_t v2 = state->v2;
  266. uint32_t v3 = state->v3;
  267. uint32_t v4 = state->v4;
  268. do {
  269. v1 = xxh32_round(v1, get_unaligned_le32(p));
  270. p += 4;
  271. v2 = xxh32_round(v2, get_unaligned_le32(p));
  272. p += 4;
  273. v3 = xxh32_round(v3, get_unaligned_le32(p));
  274. p += 4;
  275. v4 = xxh32_round(v4, get_unaligned_le32(p));
  276. p += 4;
  277. } while (p <= limit);
  278. state->v1 = v1;
  279. state->v2 = v2;
  280. state->v3 = v3;
  281. state->v4 = v4;
  282. }
  283. if (p < b_end) {
  284. memcpy(state->mem32, p, (size_t)(b_end-p));
  285. state->memsize = (uint32_t)(b_end-p);
  286. }
  287. return 0;
  288. }
  289. EXPORT_SYMBOL(xxh32_update);
  290. uint32_t xxh32_digest(const struct xxh32_state *state)
  291. {
  292. const uint8_t *p = (const uint8_t *)state->mem32;
  293. const uint8_t *const b_end = (const uint8_t *)(state->mem32) +
  294. state->memsize;
  295. uint32_t h32;
  296. if (state->large_len) {
  297. h32 = xxh_rotl32(state->v1, 1) + xxh_rotl32(state->v2, 7) +
  298. xxh_rotl32(state->v3, 12) + xxh_rotl32(state->v4, 18);
  299. } else {
  300. h32 = state->v3 /* == seed */ + PRIME32_5;
  301. }
  302. h32 += state->total_len_32;
  303. while (p + 4 <= b_end) {
  304. h32 += get_unaligned_le32(p) * PRIME32_3;
  305. h32 = xxh_rotl32(h32, 17) * PRIME32_4;
  306. p += 4;
  307. }
  308. while (p < b_end) {
  309. h32 += (*p) * PRIME32_5;
  310. h32 = xxh_rotl32(h32, 11) * PRIME32_1;
  311. p++;
  312. }
  313. h32 ^= h32 >> 15;
  314. h32 *= PRIME32_2;
  315. h32 ^= h32 >> 13;
  316. h32 *= PRIME32_3;
  317. h32 ^= h32 >> 16;
  318. return h32;
  319. }
  320. EXPORT_SYMBOL(xxh32_digest);
  321. int xxh64_update(struct xxh64_state *state, const void *input, const size_t len)
  322. {
  323. const uint8_t *p = (const uint8_t *)input;
  324. const uint8_t *const b_end = p + len;
  325. if (input == NULL)
  326. return -EINVAL;
  327. state->total_len += len;
  328. if (state->memsize + len < 32) { /* fill in tmp buffer */
  329. memcpy(((uint8_t *)state->mem64) + state->memsize, input, len);
  330. state->memsize += (uint32_t)len;
  331. return 0;
  332. }
  333. if (state->memsize) { /* tmp buffer is full */
  334. uint64_t *p64 = state->mem64;
  335. memcpy(((uint8_t *)p64) + state->memsize, input,
  336. 32 - state->memsize);
  337. state->v1 = xxh64_round(state->v1, get_unaligned_le64(p64));
  338. p64++;
  339. state->v2 = xxh64_round(state->v2, get_unaligned_le64(p64));
  340. p64++;
  341. state->v3 = xxh64_round(state->v3, get_unaligned_le64(p64));
  342. p64++;
  343. state->v4 = xxh64_round(state->v4, get_unaligned_le64(p64));
  344. p += 32 - state->memsize;
  345. state->memsize = 0;
  346. }
  347. if (p + 32 <= b_end) {
  348. const uint8_t *const limit = b_end - 32;
  349. uint64_t v1 = state->v1;
  350. uint64_t v2 = state->v2;
  351. uint64_t v3 = state->v3;
  352. uint64_t v4 = state->v4;
  353. do {
  354. v1 = xxh64_round(v1, get_unaligned_le64(p));
  355. p += 8;
  356. v2 = xxh64_round(v2, get_unaligned_le64(p));
  357. p += 8;
  358. v3 = xxh64_round(v3, get_unaligned_le64(p));
  359. p += 8;
  360. v4 = xxh64_round(v4, get_unaligned_le64(p));
  361. p += 8;
  362. } while (p <= limit);
  363. state->v1 = v1;
  364. state->v2 = v2;
  365. state->v3 = v3;
  366. state->v4 = v4;
  367. }
  368. if (p < b_end) {
  369. memcpy(state->mem64, p, (size_t)(b_end-p));
  370. state->memsize = (uint32_t)(b_end - p);
  371. }
  372. return 0;
  373. }
  374. EXPORT_SYMBOL(xxh64_update);
  375. uint64_t xxh64_digest(const struct xxh64_state *state)
  376. {
  377. const uint8_t *p = (const uint8_t *)state->mem64;
  378. const uint8_t *const b_end = (const uint8_t *)state->mem64 +
  379. state->memsize;
  380. uint64_t h64;
  381. if (state->total_len >= 32) {
  382. const uint64_t v1 = state->v1;
  383. const uint64_t v2 = state->v2;
  384. const uint64_t v3 = state->v3;
  385. const uint64_t v4 = state->v4;
  386. h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
  387. xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
  388. h64 = xxh64_merge_round(h64, v1);
  389. h64 = xxh64_merge_round(h64, v2);
  390. h64 = xxh64_merge_round(h64, v3);
  391. h64 = xxh64_merge_round(h64, v4);
  392. } else {
  393. h64 = state->v3 + PRIME64_5;
  394. }
  395. h64 += (uint64_t)state->total_len;
  396. while (p + 8 <= b_end) {
  397. const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
  398. h64 ^= k1;
  399. h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
  400. p += 8;
  401. }
  402. if (p + 4 <= b_end) {
  403. h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
  404. h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
  405. p += 4;
  406. }
  407. while (p < b_end) {
  408. h64 ^= (*p) * PRIME64_5;
  409. h64 = xxh_rotl64(h64, 11) * PRIME64_1;
  410. p++;
  411. }
  412. h64 ^= h64 >> 33;
  413. h64 *= PRIME64_2;
  414. h64 ^= h64 >> 29;
  415. h64 *= PRIME64_3;
  416. h64 ^= h64 >> 32;
  417. return h64;
  418. }
  419. EXPORT_SYMBOL(xxh64_digest);
  420. MODULE_LICENSE("Dual BSD/GPL");
  421. MODULE_DESCRIPTION("xxHash");