hunt.redis.util.MurmurHash source code

1 /*
2  * Hunt - A redis client library for D programming language.
3  *
4  * Copyright (C) 2018-2019 HuntLabs
5  *
6  * Website: https://www.huntlabs.net/
7  *
8  * Licensed under the Apache-2.0 License.
9  *
10  */
11  
12 module hunt.redis.util.MurmurHash;
13 
14 import hunt.redis.util.SafeEncoder;
15 import hunt.redis.util.Hashing;
16 
17 import hunt.Byte;
18 import hunt.io.ByteBuffer;
19 import hunt.io.BufferUtils;
20 import hunt.util.ByteOrder;
21 
22 /**
23  * This is a very fast, non-cryptographic hash suitable for general hash-based lookup. See
24  * http://murmurhash.googlepages.com/ for more details. <br>
25  * <p>
26  * The C version of MurmurHash 2.0 found at that site was ported to Java by Andrzej Bialecki (ab at
27  * getopt org).
28  * </p>
29  */
30 class MurmurHash : Hashing {
31     /**
32    * Hashes bytes in an array.
33    * @param data The bytes to hash.
34    * @param seed The seed for the hash.
35    * @return The 32 bit hash of the bytes in question.
36    */
37     static int hash(const(ubyte)[] data, int seed) {
38         return hash(BufferUtils.toBuffer(cast(byte[])data), seed);
39     }
40 
41     /**
42    * Hashes bytes in part of an array.
43    * @param data The data to hash.
44    * @param offset Where to start munging.
45    * @param length How many bytes to process.
46    * @param seed The seed to start with.
47    * @return The 32-bit hash of the data in question.
48    */
49     static int hash(const(ubyte)[] data, int offset, int length, int seed) {
50         return hash(BufferUtils.toBuffer(cast(byte[])data, offset, length), seed);
51     }
52 
53     /**
54    * Hashes the bytes in a buffer from the current position to the limit.
55    * @param buf The bytes to hash.
56    * @param seed The seed for the hash.
57    * @return The 32 bit murmur hash of the bytes in the buffer.
58    */
59     static int hash(ByteBuffer buf, int seed) {
60         // save byte order for later restoration
61         ByteOrder byteOrder = buf.order();
62         buf.order(ByteOrder.LittleEndian);
63 
64         int m = 0x5bd1e995;
65         int r = 24;
66 
67         int h = seed ^ buf.remaining();
68 
69         int k;
70         while (buf.remaining() >= 4) {
71             k = buf.getInt();
72 
73             k *= m;
74             k ^= k >>> r;
75             k *= m;
76 
77             h *= m;
78             h ^= k;
79         }
80 
81         if (buf.remaining() > 0) {
82             ByteBuffer finish = BufferUtils.allocate(4).order(ByteOrder.LittleEndian);
83             // for big-endian version, use this first:
84             // finish.position(4-buf.remaining());
85             finish.put(buf).rewind();
86             h ^= finish.getInt();
87             h *= m;
88         }
89 
90         h ^= h >>> 13;
91         h *= m;
92         h ^= h >>> 15;
93 
94         buf.order(byteOrder);
95         return h;
96     }
97 
98     static long hash64A(const(ubyte)[] data, int seed) {
99         return hash64A(BufferUtils.toBuffer(cast(byte[])data), seed);
100     }
101 
102     static long hash64A(const(ubyte)[] data, int offset, int length, int seed) {
103         return hash64A(BufferUtils.toBuffer(cast(byte[])data, offset, length), seed);
104     }
105 
106     static long hash64A(ByteBuffer buf, int seed) {
107         ByteOrder byteOrder = buf.order();
108         buf.order(ByteOrder.LittleEndian);
109 
110         long m = 0xc6a4a7935bd1e995L;
111         int r = 47;
112 
113         long h = seed ^ (buf.remaining() * m);
114 
115         long k;
116         while (buf.remaining() >= 8) {
117             k = buf.getLong();
118 
119             k *= m;
120             k ^= k >>> r;
121             k *= m;
122 
123             h ^= k;
124             h *= m;
125         }
126 
127         if (buf.remaining() > 0) {
128             ByteBuffer finish = BufferUtils.allocate(8).order(ByteOrder.LittleEndian);
129             // for big-endian version, do this first:
130             // finish.position(8-buf.remaining());
131             finish.put(buf).rewind();
132             h ^= finish.getLong();
133             h *= m;
134         }
135 
136         h ^= h >>> r;
137         h *= m;
138         h ^= h >>> r;
139 
140         buf.order(byteOrder);
141         return h;
142     }
143 
144     override long hash(const(ubyte)[] key) {
145         return hash64A(key, 0x1234ABCD);
146     }
147 
148     override long hash(string key) {
149         return hash(SafeEncoder.encode(key));
150     }
151 }