antlr.v4.runtime.misc.MurmurHash source code

1 /*
2  * Copyright (c) 2012-2020 The ANTLR Project. All rights reserved.
3  * Use of this file is governed by the BSD 3-clause license that
4  * can be found in the LICENSE.txt file in the project root.
5  */
6 
7 module antlr.v4.runtime.misc.MurmurHash;
8 
9 import std.conv;
10 import std.stdio;
11 
12 /**
13  * @author Sam Harwell
14  * @author Egbert Voigt (D)
15  */
16 class MurmurHash
17 {
18 
19     enum size_t DEFAULT_SEED = 0;
20 
21     /**
22      * Initialize the hash using the default seed value.
23      *
24      *  @return the intermediate hash value
25      * @uml
26      * @safe
27      * @nothrow
28      */
29     public static size_t initialize() @safe nothrow
30     {
31         auto mh = new MurmurHash;
32         return initialize(DEFAULT_SEED);
33     }
34 
35     /**
36      * Initialize the hash using the specified {@code seed}.
37      *
38      *  @param seed the seed
39      *  @return the intermediate hash value
40      * @uml
41      * @safe
42      * @nothrow
43      */
44     public static size_t initialize(size_t seed) @safe nothrow
45     {
46         return seed;
47     }
48 
49     /**
50      * Update the intermediate hash value for the next input {@code value}.
51      *
52      * @param hash the intermediate hash value
53      * @param value the value to add to the current hash
54      * @return the updated intermediate hash value
55      *
56      * @uml
57      * @safe
58      * @nothrow
59      */
60     public static size_t update(size_t hash, size_t value) @safe nothrow
61     {
62         immutable size_t c1 = 0xCC9E2D51;
63         immutable size_t c2 = 0x1B873593;
64         immutable size_t r1 = 15;
65         immutable size_t r2 = 13;
66         immutable size_t m = 5;
67         immutable size_t n = 0xE6546B64;
68 
69         size_t k = value;
70         k = k * c1;
71         k = (k << r1) | (k >>> (32 - r1));
72         k = k * c2;
73 
74         hash = hash ^ k;
75         hash = (hash << r2) | (hash >>> (32 - r2));
76         hash = hash * m + n;
77 
78         return hash;
79 
80     }
81 
82     /**
83      * Update the intermediate hash value for the next input {@code value}.
84      *
85      * @param hash the intermediate hash value
86      * @param value the value to add to the current hash
87      * @return the updated intermediate hash value
88      *
89      * @uml
90      * @nothrow
91      */
92     public static size_t update(U)(size_t hash, U value) nothrow
93     {
94         return update(hash, value !is null ? value.toHash : 0);
95     }
96 
97     /**
98      * Apply the final computation steps to the intermediate value {@code hash}
99      * to form the final result of the MurmurHash 3 hash function.
100      *
101      *  @param hash the intermediate hash value
102      *  @param numberOfWords the number of integer values added to the hash
103      *  @return the final hash result
104      * @uml
105      * @safe
106      * @nothrow
107      */
108     public static size_t finish(size_t hash, size_t numberOfWords) @safe nothrow
109     {
110         hash = hash ^ (cast(size_t) numberOfWords * 4);
111         hash = hash ^ (hash >>> 16);
112         hash = hash * 0x85EBCA6B;
113         hash = hash ^ (hash >>> 13);
114         hash = hash * 0xC2B2AE35;
115         hash = hash ^ (hash >>> 16);
116         return hash;
117     }
118 
119     /**
120      * Utility function to compute the hash code of an array using the
121      * MurmurHash algorithm.
122      *
123      * @param T the array element type
124      * @param data the array data
125      * @param seed the seed for the MurmurHash algorithm
126      * @return the hash code of the data
127      */
128     public static size_t hashCode(T)(T[] data, size_t seed)
129     {
130         size_t hash = initialize(seed);
131         foreach (T value; data)
132         {
133             hash = update(hash, value);
134         }
135         hash = finish(hash, data.length);
136         return hash;
137     }
138 
139 }
140 
141 version (unittest)
142 {
143     import dshould : equal, should;
144     import unit_threaded;
145 
146     @Tags("MurmurHash")
147     @("Calculation")
148     unittest
149     {
150         auto hash = MurmurHash.initialize;
151         hash.should.equal(0);
152         hash = MurmurHash.update(hash, 33);
153         static if (size_t.sizeof == 4)
154         {
155             hash.should.equal(3641358107U);
156         }
157         else
158         {
159             hash.should.equal(6137767987951124103UL);
160         }
161         hash = MurmurHash.finish(hash, 1);
162         static if (size_t.sizeof == 4)
163         {
164             hash.should.equal(2689861987U);
165         }
166         else
167         {
168             hash.should.equal(4470425249505779227UL);
169         }
170     }
171 }