Merge lp:~tangent-org/libmemcached/1.0-build/ Build: jenkins-Libmemcached-187
[m6w6/libmemcached] / libhashkit / murmur.cc
1 /* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
2 *
3 * HashKit library
4 *
5 * Copyright (C) 2011-2012 Data Differential, http://datadifferential.com/
6 * Copyright (C) 2006-2009 Brian Aker All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are
10 * met:
11 *
12 * * Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 *
15 * * Redistributions in binary form must reproduce the above
16 * copyright notice, this list of conditions and the following disclaimer
17 * in the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * * The names of its contributors may not be used to endorse or
21 * promote products derived from this software without specific prior
22 * written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
27 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
28 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
29 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
30 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
31 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
34 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 *
36 */
37
38 /*
39 "Murmur" hash provided by Austin, tanjent@gmail.com
40 http://murmurhash.googlepages.com/
41
42 Note - This code makes a few assumptions about how your machine behaves -
43
44 1. We can read a 4-byte value from any address without crashing
45 2. sizeof(int) == 4
46
47 And it has a few limitations -
48 1. It will not work incrementally.
49 2. It will not produce the same results on little-endian and big-endian
50 machines.
51
52 Updated to murmur2 hash - BP
53 */
54
55 #include <libhashkit/common.h>
56
57 #ifdef HAVE_MURMUR_HASH
58
59 uint32_t hashkit_murmur(const char *key, size_t length, void *context)
60 {
61 /*
62 'm' and 'r' are mixing constants generated offline. They're not
63 really 'magic', they just happen to work well.
64 */
65
66 const unsigned int m= 0x5bd1e995;
67 const uint32_t seed= (0xdeadbeef * (uint32_t)length);
68 const int r= 24;
69
70
71 // Initialize the hash to a 'random' value
72
73 uint32_t h= seed ^ (uint32_t)length;
74
75 // Mix 4 bytes at a time into the hash
76
77 const unsigned char * data= (const unsigned char *)key;
78 (void)context;
79
80 while(length >= 4)
81 {
82 unsigned int k = *(unsigned int *)data;
83
84 k *= m;
85 k ^= k >> r;
86 k *= m;
87
88 h *= m;
89 h ^= k;
90
91 data += 4;
92 length -= 4;
93 }
94
95 // Handle the last few bytes of the input array
96
97 switch(length)
98 {
99 case 3: h ^= ((uint32_t)data[2]) << 16;
100 case 2: h ^= ((uint32_t)data[1]) << 8;
101 case 1: h ^= data[0];
102 h *= m;
103 default: break;
104 };
105
106 /*
107 Do a few final mixes of the hash to ensure the last few bytes are
108 well-incorporated.
109 */
110
111 h ^= h >> 13;
112 h *= m;
113 h ^= h >> 15;
114
115 return h;
116 }
117
118 #else
119 uint32_t hashkit_murmur(const char *, size_t , void *)
120 {
121 return 0;
122 }
123 #endif