UNPKG

2.02 kBJavaScriptView Raw
1/*!
2 * murmur3.js - murmur3 hash for bcoin
3 * Copyright (c) 2014-2015, Fedor Indutny (MIT License)
4 * Copyright (c) 2014-2017, Christopher Jeffrey (MIT License).
5 * https://github.com/bcoin-org/bcoin
6 */
7
8'use strict';
9
10/**
11 * Murmur3 hash.
12 * @param {Buffer} data
13 * @param {Number} seed
14 * @returns {Number}
15 */
16
17function sum(data, seed) {
18 const tail = data.length - (data.length % 4);
19 const c1 = 0xcc9e2d51;
20 const c2 = 0x1b873593;
21
22 let h1 = seed;
23
24 for (let i = 0; i < tail; i += 4) {
25 let k1 = (data[i + 3] << 24)
26 | (data[i + 2] << 16)
27 | (data[i + 1] << 8)
28 | data[i];
29 k1 = mul32(k1, c1);
30 k1 = rotl32(k1, 15);
31 k1 = mul32(k1, c2);
32 h1 ^= k1;
33 h1 = rotl32(h1, 13);
34 h1 = sum32(mul32(h1, 5), 0xe6546b64);
35 }
36
37 let k1 = 0;
38 switch (data.length & 3) {
39 case 3:
40 k1 ^= data[tail + 2] << 16;
41 case 2:
42 k1 ^= data[tail + 1] << 8;
43 case 1:
44 k1 ^= data[tail + 0];
45 k1 = mul32(k1, c1);
46 k1 = rotl32(k1, 15);
47 k1 = mul32(k1, c2);
48 h1 ^= k1;
49 }
50
51 h1 ^= data.length;
52 h1 ^= h1 >>> 16;
53 h1 = mul32(h1, 0x85ebca6b);
54 h1 ^= h1 >>> 13;
55 h1 = mul32(h1, 0xc2b2ae35);
56 h1 ^= h1 >>> 16;
57
58 if (h1 < 0)
59 h1 += 0x100000000;
60
61 return h1;
62}
63
64/**
65 * Murmur3 hash.
66 * @param {Buffer} data
67 * @param {Number} n
68 * @param {Number} tweak
69 * @returns {Number}
70 */
71
72function tweak(data, n, _tweak) {
73 const seed = sum32(mul32(n, 0xfba4c795), _tweak);
74 return sum(data, seed);
75}
76
77/*
78 * Helpers
79 */
80
81function mul32(a, b) {
82 const alo = a & 0xffff;
83 const blo = b & 0xffff;
84 const ahi = a >>> 16;
85 const bhi = b >>> 16;
86
87 let lo = alo * blo;
88 let hi = (ahi * blo + bhi * alo) & 0xffff;
89
90 hi += lo >>> 16;
91 lo &= 0xffff;
92
93 let r = (hi << 16) | lo;
94
95 if (r < 0)
96 r += 0x100000000;
97
98 return r;
99}
100
101function sum32(a, b) {
102 let r = (a + b) & 0xffffffff;
103
104 if (r < 0)
105 r += 0x100000000;
106
107 return r;
108}
109
110function rotl32(w, b) {
111 return (w << b) | (w >>> (32 - b));
112}
113
114/**
115 * Expose
116 */
117
118exports.sum = sum;
119exports.tweak = tweak;