/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
struct Hash {
public:
typedef uint64_t Value;
Hash() {}
Hash(const Token *buf, unsigned blocksize) {
value = 0;
for (unsigned num = 0; num < blocksize; ++num)
advance_add(buf[num]);
oldCoefficient = powHash(multiplyAmount, blocksize);
}
void advance(Token out, Token in) {
advance_remove(out);
advance_add(in);
}
static unsigned modulo(Value hash, unsigned d) {
// Assumes d is power of 2.
return hash & (d - 1);
}
Value getValue() {return value >> extraProcBits;}
private:
typedef uint64_t ProcValue;
static const unsigned extraProcBits = (sizeof(ProcValue) - sizeof(Value)) * 8;
static const ProcValue multiplyAmount = (1ll << extraProcBits) | 181;
ProcValue oldCoefficient, value;
void advance_add(Token in) {
value += in;
value *= multiplyAmount;
}
void advance_remove(Token out) {
value -= out * oldCoefficient;
}
static ProcValue powHash(ProcValue x, unsigned y) {
ProcValue res = 1;
while (y) {
if (y & 1) res *= x;
x *= x;
y >>= 1;
}
return res;
}
};