Line data Source code
1 : import { Hasher } from "./hash.js";
2 : import { PseudoRandomNumberGenerator, TycheI } from "./prng.js";
3 :
4 : // Derived from here:
5 : // https://github.com/bryc/code/tree/master/jshash/hashes
6 : // https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
7 :
8 1 : function fmix32(h: number) {
9 1 : h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b);
10 1 : h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35);
11 1 : h ^= h >>> 16;
12 1 : return h;
13 1 : }
14 :
15 1 : const c1 = 0x239b961b;
16 1 : const c2 = 0xab0e9789;
17 1 : const c3 = 0x38b34ae5;
18 1 : const c4 = 0xa1e38b93;
19 :
20 1 : const encoder = new TextEncoder();
21 :
22 : /// Implements the murmur3 x86 128 bit variant
23 1 : export class Murmur3_x86_128 implements Hasher {
24 1 : h1: number;
25 1 : h2: number;
26 1 : h3: number;
27 1 : h4: number;
28 1 : len: number;
29 :
30 1 : constructor(seed: number = 0, preserveSeed: boolean = false) {
31 : // bryc xor'ed h1-h4 with p1-p4, but this is deviating from the original murmur3:
32 : // https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
33 1 : if (preserveSeed) {
34 1 : this.h1 = seed;
35 1 : this.h2 = seed;
36 1 : this.h3 = seed;
37 1 : this.h4 = seed;
38 1 : } else {
39 1 : this.h1 = seed ^ c1;
40 1 : this.h2 = seed ^ c2;
41 1 : this.h3 = seed ^ c3;
42 1 : this.h4 = seed ^ c4;
43 1 : }
44 1 : this.len = 0;
45 1 : }
46 :
47 1 : public static withSeed(seed: number, preserveSeed: boolean = false): Murmur3_x86_128 {
48 1 : return new Murmur3_x86_128(seed, preserveSeed);
49 1 : }
50 1 : public static hash(str: string): Hasher {
51 1 : return (new Murmur3_x86_128()).add(str);
52 1 : }
53 :
54 0 : public clone(): Hasher {
55 0 : const c = new Murmur3_x86_128();
56 0 : c.h1 = this.h1;
57 0 : c.h2 = this.h2;
58 0 : c.h3 = this.h3;
59 0 : c.h4 = this.h4;
60 0 : c.len = this.len;
61 0 : return c;
62 0 : }
63 :
64 1 : add(keyStr: string): Hasher {
65 : // Get utf8 bytes for string
66 1 : const key = encoder.encode(keyStr);
67 :
68 : // First process blocks of 4 32-bit integers
69 1 : const bytesPerBlock = 4 * 4;
70 1 : const blockCount = Math.floor(key.length / bytesPerBlock);
71 1 : const blocks = new Uint32Array(key.buffer, key.byteOffset, blockCount * 4);
72 :
73 1 : for (let i = 0; (i + 4) <= blocks.length; i += 4) {
74 1 : let k1 = blocks[i];
75 1 : let k2 = blocks[i + 1];
76 1 : let k3 = blocks[i + 2];
77 1 : let k4 = blocks[i + 3];
78 :
79 1 : k1 = Math.imul(k1, c1); k1 = k1 << 15 | k1 >>> 17;
80 1 : this.h1 ^= Math.imul(k1, c2); this.h1 = this.h1 << 19 | this.h1 >>> 13; this.h1 += this.h2;
81 1 : this.h1 = Math.imul(this.h1, 5) + 0x561ccd1b | 0; // |0 = prevent float
82 :
83 1 : k2 = Math.imul(k2, c2); k2 = k2 << 16 | k2 >>> 16;
84 1 : this.h2 ^= Math.imul(k2, c3); this.h2 = this.h2 << 17 | this.h2 >>> 15; this.h2 += this.h3;
85 1 : this.h2 = Math.imul(this.h2, 5) + 0x0bcaa747 | 0;
86 :
87 1 : k3 = Math.imul(k3, c3); k3 = k3 << 17 | k3 >>> 15;
88 1 : this.h3 ^= Math.imul(k3, c4); this.h3 = this.h3 << 15 | this.h3 >>> 17; this.h3 += this.h4;
89 1 : this.h3 = Math.imul(this.h3, 5) + 0x96cd1c35 | 0;
90 :
91 1 : k4 = Math.imul(k4, c4); k4 = k4 << 18 | k4 >>> 14;
92 1 : this.h4 ^= Math.imul(k4, c1); this.h4 = this.h4 << 13 | this.h4 >>> 19; this.h4 += this.h1;
93 1 : this.h4 = Math.imul(this.h4, 5) + 0x32ac3b17 | 0;
94 1 : }
95 :
96 : // Then process the trailing bytes
97 1 : let i = blockCount * bytesPerBlock;
98 1 : let k1 = 0;
99 1 : let k2 = 0
100 1 : let k3 = 0
101 1 : let k4 = 0;
102 1 : switch (key.length & 15) {
103 0 : case 15: k4 ^= key[i + 14] << 16;
104 0 : case 14: k4 ^= key[i + 13] << 8;
105 1 : case 13: k4 ^= key[i + 12];
106 1 : k4 = Math.imul(k4, c4); k4 = k4 << 18 | k4 >>> 14;
107 1 : this.h4 ^= Math.imul(k4, c1);
108 1 : case 12: k3 ^= key[i + 11] << 24;
109 1 : case 11: k3 ^= key[i + 10] << 16;
110 1 : case 10: k3 ^= key[i + 9] << 8;
111 1 : case 9: k3 ^= key[i + 8];
112 1 : k3 = Math.imul(k3, c3); k3 = k3 << 17 | k3 >>> 15;
113 1 : this.h3 ^= Math.imul(k3, c4);
114 1 : case 8: k2 ^= key[i + 7] << 24;
115 1 : case 7: k2 ^= key[i + 6] << 16;
116 1 : case 6: k2 ^= key[i + 5] << 8;
117 1 : case 5: k2 ^= key[i + 4];
118 1 : k2 = Math.imul(k2, c2); k2 = k2 << 16 | k2 >>> 16;
119 1 : this.h2 ^= Math.imul(k2, c3);
120 1 : case 4: k1 ^= key[i + 3] << 24;
121 1 : case 3: k1 ^= key[i + 2] << 16;
122 1 : case 2: k1 ^= key[i + 1] << 8;
123 1 : case 1: k1 ^= key[i];
124 1 : k1 = Math.imul(k1, c1); k1 = k1 << 15 | k1 >>> 17;
125 1 : this.h1 ^= Math.imul(k1, c2);
126 1 : }
127 :
128 1 : this.len += key.length;
129 1 : return this;
130 1 : };
131 :
132 1 : protected finish(): [number, number, number, number] {
133 1 : let h1 = this.h1;
134 1 : let h2 = this.h2;
135 1 : let h3 = this.h3;
136 1 : let h4 = this.h4;
137 1 : h1 ^= this.len; h2 ^= this.len; h3 ^= this.len; h4 ^= this.len;
138 1 : h1 += h2; h1 += h3; h1 += h4;
139 1 : h2 += h1; h3 += h1; h4 += h1;
140 :
141 1 : h1 = fmix32(h1);
142 1 : h2 = fmix32(h2);
143 1 : h3 = fmix32(h3);
144 1 : h4 = fmix32(h4);
145 :
146 1 : h1 += h2; h1 += h3; h1 += h4;
147 1 : h2 += h1; h3 += h1; h4 += h1;
148 :
149 1 : h1 >>>= 0;
150 1 : h2 >>>= 0;
151 1 : h3 >>>= 0;
152 1 : h4 >>>= 0;
153 :
154 1 : return [h1, h2, h3, h4];
155 1 : }
156 :
157 0 : public addN(strs: string[]): Hasher {
158 0 : for (const str of strs) {
159 0 : this.add(str);
160 : }
161 0 : return this;
162 0 : }
163 :
164 1 : public asPrng(): PseudoRandomNumberGenerator {
165 1 : const [h1, h2, h3, h4] = this.finish();
166 1 : return new TycheI(h1, h2, h3, h4);
167 1 : }
168 1 : public asString(): string {
169 1 : const [h1, h2, h3, h4] = this.finish();
170 1 : return (
171 1 : ("00000000" + h1.toString(16)).slice(-8) +
172 1 : ("00000000" + h2.toString(16)).slice(-8) +
173 1 : ("00000000" + h3.toString(16)).slice(-8) +
174 1 : ("00000000" + h4.toString(16)).slice(-8)
175 : );
176 1 : }
177 1 : }
|
