-
Notifications
You must be signed in to change notification settings - Fork 188
/
hashfn.h
182 lines (154 loc) · 5.25 KB
/
hashfn.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
/*
Copyright 2005-2010 Jakub Kruszona-Zawadzki, Gemius SA, 2013-2014 EditShare, 2013-2015 Skytechnology sp. z o.o..
This file was part of MooseFS and is part of LizardFS.
LizardFS is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, version 3.
LizardFS is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with LizardFS If not, see <http://www.gnu.org/licenses/>.
*/
#pragma once
#include "common/platform.h"
#include <inttypes.h>
#include <numeric>
#include <stdexcept>
#include <tuple>
#include "common/integer_sequence.h"
/* fast integer hash functions by Thomas Wang */
/* all of them pass the avalanche test */
/* They are not mutch better in standard collision test than stupid "X*prime"
* functions, but calculation times are similar, so it should be safer to use
* this functions */
/* 32bit -> 32bit */
static inline uint32_t hash32(uint32_t key) {
key = ~key + (key << 15); // key = (key << 15) - key - 1;
key = key ^ (key >> 12);
key = key + (key << 2);
key = key ^ (key >> 4);
key = key * 2057; // key = (key + (key << 3)) + (key << 11);
key = key ^ (key >> 16);
return key;
}
/* 32bit -> 32bit - with 32bit multiplication (can be adjusted by other constant values, such as: 0xb55a4f09,0x165667b1,2034824023,2034824021 etc.) */
static inline uint32_t hash32mult(uint32_t key) {
key = (key ^ 61) ^ (key >> 16);
key = key + (key << 3);
key = key ^ (key >> 4);
key = key * 0x27d4eb2d;
key = key ^ (key >> 15);
return key;
}
/* 64bit -> 32bit */
static inline uint32_t hash6432(uint64_t key) {
key = (~key) + (key << 18); // key = (key << 18) - key - 1;
key = key ^ (key >> 31);
key = key * 21; // key = (key + (key << 2)) + (key << 4);
key = key ^ (key >> 11);
key = key + (key << 6);
key = key ^ (key >> 22);
return (uint32_t)key;
}
/* 64bit -> 64bit */
static inline uint64_t hash64(uint64_t key) {
key = (~key) + (key << 21); // key = (key << 21) - key - 1;
key = key ^ (key >> 24);
key = (key + (key << 3)) + (key << 8); // key * 265
key = key ^ (key >> 14);
key = (key + (key << 2)) + (key << 4); // key * 21
key = key ^ (key >> 28);
key = key + (key << 31);
return key;
}
// This is the generic hashing function template declaration.
//
// There is no general definition; definitions are provided per-specialization for
// supported types only.
//
// The function is declared as a template to ensure that hash(unsupported_type)
// fails with 'undefined reference to hash<unsupported_type>' instead of attempting
// to cast unsupported_type to some random type supported by hash e.g. bool.
template <class T>
uint64_t hash(T);
#define HASH_PRIMITIVE32(type) \
template<> \
inline uint64_t hash<type>(type val) { \
return hash32mult(val); \
}
#define HASH_PRIMITIVE64(type) \
template<> \
inline uint64_t hash<type>(type val) { \
return hash64(val); \
}
HASH_PRIMITIVE32(bool)
HASH_PRIMITIVE32(char)
HASH_PRIMITIVE32(signed char)
HASH_PRIMITIVE32(unsigned char)
HASH_PRIMITIVE32(short)
HASH_PRIMITIVE32(unsigned short)
HASH_PRIMITIVE32(int)
HASH_PRIMITIVE32(unsigned int)
HASH_PRIMITIVE64(long)
HASH_PRIMITIVE64(unsigned long)
HASH_PRIMITIVE64(long long)
HASH_PRIMITIVE64(unsigned long long)
// takes the hash, not an arbitrary object instance
static inline void hashCombineRaw(uint64_t& seed, uint64_t hash) {
seed ^= hash + 11400714819323198485ULL + (seed << 6) + (seed >> 2);
}
static inline void hashCombine(uint64_t&) {
}
template<class T, class... Args>
static inline void hashCombine(uint64_t& seed, const T& val, Args... args) {
hashCombineRaw(seed, hash<T>(val));
hashCombine(seed, args...);
}
// ByteArray can be used to checksum byte arrays.
// The first element is the pointer to the array, the second is the size.
// Examples:
// return hash(ByteArray(&foo, sizeof(foo)))
// hashCombine(checksum, foo, ByteArray(bar, bar_size), baz, qaz)
struct ByteArray {
ByteArray(const uint8_t *ptr, const size_t size) : ptr(ptr), size(size) {}
ByteArray(const char *ptr, const size_t size)
: ptr(reinterpret_cast<const uint8_t*>(ptr)),
size(size) {
}
const uint8_t *ptr;
const size_t size;
};
template<>
inline uint64_t hash<ByteArray>(ByteArray array) {
uint64_t seed = 399871011; // arbitrary number
for (size_t i = 0; i < array.size; i++) {
hashCombine(seed, array.ptr[i]);
}
return seed;
}
// functions for dynamically changing checksums
inline void addToChecksum(uint64_t& checksum, uint64_t hash) {
checksum ^= hash;
}
inline void removeFromChecksum(uint64_t& checksum, uint64_t hash) {
checksum ^= hash;
}
/**
* A class providing dumb hashing function for std::tuple's
*/
template <class... Args>
struct AlmostGenericTupleHash {
typedef std::tuple<Args...> Tuple;
uint64_t operator()(const Tuple& t) const noexcept {
uint64_t seed = 0;
combine(seed, t, make_index_sequence<sizeof...(Args)>());
return seed;
}
private:
template<std::size_t... Is>
void combine(uint64_t &seed, const Tuple& t, index_sequence<Is...>) const {
hashCombine(seed, std::get<Is>(t)...);
}
};