antlr.v4.runtime.misc.MurmurHash source code

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