clang-format: no single-line case
[awesomized/libmemcached] / src / libhashkit / murmur.cc
1 /*
2 +--------------------------------------------------------------------+
3 | libmemcached - C/C++ Client Library for memcached |
4 +--------------------------------------------------------------------+
5 | Redistribution and use in source and binary forms, with or without |
6 | modification, are permitted under the terms of the BSD license. |
7 | You should have received a copy of the license in a bundled file |
8 | named LICENSE; in case you did not receive a copy you can review |
9 | the terms online at: https://opensource.org/licenses/BSD-3-Clause |
10 +--------------------------------------------------------------------+
11 | Copyright (c) 2006-2014 Brian Aker https://datadifferential.com/ |
12 | Copyright (c) 2020 Michael Wallner <mike@php.net> |
13 +--------------------------------------------------------------------+
14 */
15
16 #include "libhashkit/common.h"
17
18 #ifdef HAVE_MURMUR_HASH
19
20 # ifdef BYTESWAP_HEADER
21 # include BYTESWAP_HEADER
22 # endif
23
24 # include <cstring>
25
26 uint32_t hashkit_murmur(const char *key, size_t length, void *context) {
27 /*
28 'm' and 'r' are mixing constants generated offline. They're not
29 really 'magic', they just happen to work well.
30 */
31
32 const unsigned int m = 0x5bd1e995;
33 const uint32_t seed = (0xdeadbeef * (uint32_t) length);
34 const int r = 24;
35
36 // Initialize the hash to a 'random' value
37
38 uint32_t h = seed ^ (uint32_t) length;
39
40 // Mix 4 bytes at a time into the hash
41
42 const unsigned char *data = (const unsigned char *) key;
43 (void) context;
44
45 while (length >= 4) {
46 uint32_t k;
47 memcpy(&k, data, sizeof(k));
48 # if WORDS_BIGENDIAN
49 k = BYTESWAP_32(k);
50 # endif
51
52 k *= m;
53 k ^= k >> r;
54 k *= m;
55
56 h *= m;
57 h ^= k;
58
59 data += 4;
60 length -= 4;
61 }
62
63 // Handle the last few bytes of the input array
64 if (length) {
65 uint32_t k = 0;
66 memcpy(&k, data, length);
67 # if WORDS_BIGENDIAN
68 k = BYTESWAP_32(k);
69 # endif
70 h ^= k;
71 h *= m;
72 }
73
74 /*
75 Do a few final mixes of the hash to ensure the last few bytes are
76 well-incorporated.
77 */
78
79 h ^= h >> 13;
80 h *= m;
81 h ^= h >> 15;
82
83 return h;
84 }
85
86 #else
87 uint32_t hashkit_murmur(const char *, size_t, void *) {
88 return 0;
89 }
90 #endif