Line data Source code
1 : // Copyright (c) 2019 Made to Order Software Corp. All Rights Reserved
2 : //
3 : // https://snapwebsites.org/project/snapdatabase
4 : // contact@m2osw.com
5 : //
6 : // This program is free software; you can redistribute it and/or modify
7 : // it under the terms of the GNU General Public License as published by
8 : // the Free Software Foundation; either version 2 of the License, or
9 : // (at your option) any later version.
10 : //
11 : // This program is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 : //
16 : // You should have received a copy of the GNU General Public License along
17 : // with this program; if not, write to the Free Software Foundation, Inc.,
18 : // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
19 :
20 :
21 : /** \file
22 : * \brief Database file implementation.
23 : *
24 : * Each table uses one or more files. Each file is handled by a dbfile
25 : * object and a corresponding set of blocks.
26 : */
27 :
28 : // self
29 : //
30 : #include "snapdatabase/file/hash.h"
31 :
32 : #include "snapdatabase/exception.h"
33 :
34 : // C lib
35 : //
36 : #include <string.h>
37 :
38 : // last include
39 : //
40 : #include <snapdev/poison.h>
41 :
42 :
43 :
44 : namespace snapdatabase
45 : {
46 :
47 :
48 : constexpr hash_t END_OF_BUFFER = static_cast<hash_t>(-1);
49 :
50 :
51 : /** \brief Init the hash with the specified seed.
52 : *
53 : * The hash class starts with the specified seed. By changing the seed
54 : * you can reuse the same class as if you were using several different
55 : * hash functions. This is how we create multiple hashes for bloom
56 : * filters.
57 : *
58 : * \param[in] seed The seed to start with.
59 : */
60 0 : hash::hash(hash_t seed)
61 0 : : f_hash(seed)
62 : {
63 0 : }
64 :
65 :
66 0 : hash_t hash::get_byte() const
67 : {
68 0 : if(f_temp_size > 0)
69 : {
70 0 : --f_temp_size;
71 0 : return f_temp[f_temp_size];
72 : }
73 :
74 0 : if(f_size > 0)
75 : {
76 0 : uint8_t const v(*f_buffer);
77 0 : ++f_buffer;
78 0 : --f_size;
79 0 : return v;
80 : }
81 :
82 0 : return END_OF_BUFFER;
83 : }
84 :
85 :
86 0 : hash_t hash::peek_byte(int pos) const
87 : {
88 0 : if(static_cast<std::size_t>(pos) < f_temp_size)
89 : {
90 : // bytes are in reverse order in f_temp
91 : //
92 0 : return f_temp[f_temp_size - pos - 1];
93 : }
94 0 : pos -= f_temp_size;
95 :
96 0 : if(static_cast<std::size_t>(pos) < f_size)
97 : {
98 0 : return f_buffer[pos];
99 : }
100 :
101 0 : return 0;
102 : }
103 :
104 :
105 0 : size_t hash::size() const
106 : {
107 0 : return f_temp_size + f_size;
108 : }
109 :
110 :
111 0 : void hash::get_64bits(hash_t & v1, hash_t & v2)
112 : {
113 0 : if(f_temp_size == 0 && f_size >= 8)
114 : {
115 : // faster this way
116 : //
117 0 : v1 = (f_buffer[0] << 24)
118 0 : + (f_buffer[1] << 16)
119 0 : + (f_buffer[2] << 8)
120 0 : + (f_buffer[3] << 0);
121 :
122 0 : v2 = (f_buffer[4] << 24)
123 0 : + (f_buffer[5] << 16)
124 0 : + (f_buffer[6] << 8)
125 0 : + (f_buffer[7] << 0);
126 :
127 0 : f_buffer += 8;
128 0 : f_size -= 8;
129 :
130 0 : return;
131 : }
132 :
133 0 : if(size() >= 8)
134 : {
135 0 : v1 = (get_byte() << 24)
136 0 : + (get_byte() << 16)
137 0 : + (get_byte() << 8)
138 0 : + (get_byte() << 0);
139 :
140 0 : v2 = (get_byte() << 24)
141 0 : + (get_byte() << 16)
142 0 : + (get_byte() << 8)
143 0 : + (get_byte() << 0);
144 :
145 0 : return;
146 : }
147 :
148 0 : throw snapdatabase_logic_error("called get_64bits() when the input buffer is less than 64 bits");
149 : }
150 :
151 :
152 0 : void hash::peek_64bits(hash_t & v1, hash_t & v2) const
153 : {
154 0 : switch(size())
155 : {
156 0 : case 7:
157 0 : v1 = (get_byte() << 24)
158 0 : + (get_byte() << 16)
159 0 : + (get_byte() << 8)
160 0 : + (get_byte() << 0);
161 :
162 0 : v2 = (get_byte() << 16)
163 0 : + (get_byte() << 8)
164 0 : + (get_byte() << 0);
165 0 : break;
166 :
167 0 : case 6:
168 0 : v1 = (get_byte() << 24)
169 0 : + (get_byte() << 16)
170 0 : + (get_byte() << 8)
171 0 : + (get_byte() << 0);
172 :
173 0 : v2 = (get_byte() << 8)
174 0 : + (get_byte() << 0);
175 0 : break;
176 :
177 0 : case 5:
178 0 : v1 = (get_byte() << 24)
179 0 : + (get_byte() << 16)
180 0 : + (get_byte() << 8)
181 0 : + (get_byte() << 0);
182 :
183 0 : v2 = (get_byte() << 0);
184 0 : break;
185 :
186 0 : case 4:
187 0 : v1 = (get_byte() << 24)
188 0 : + (get_byte() << 16)
189 0 : + (get_byte() << 8)
190 0 : + (get_byte() << 0);
191 :
192 0 : v2 = 0;
193 0 : break;
194 :
195 0 : case 3:
196 0 : v1 = (get_byte() << 16)
197 0 : + (get_byte() << 8)
198 0 : + (get_byte() << 0);
199 :
200 0 : v2 = 0;
201 0 : break;
202 :
203 0 : case 2:
204 0 : v1 = (get_byte() << 8)
205 0 : + (get_byte() << 0);
206 :
207 0 : v2 = 0;
208 0 : break;
209 :
210 0 : case 1:
211 0 : v1 = (get_byte() << 0);
212 :
213 0 : v2 = 0;
214 0 : break;
215 :
216 0 : case 0:
217 0 : v1 = 0;
218 0 : v2 = 0;
219 0 : break;
220 :
221 0 : default:
222 0 : throw snapdatabase_logic_error("called peek_64bits() when the input buffer is 64 bits or more");
223 :
224 : }
225 0 : }
226 :
227 :
228 : // hash function taken from: https://github.com/ArashPartow/bloom
229 : // and modified to work incrementally.
230 : //
231 0 : void hash::add(uint8_t const * v, std::size_t buffer_size)
232 : {
233 0 : f_buffer = v;
234 0 : f_size = buffer_size;
235 :
236 0 : while(size() >= 8)
237 : {
238 0 : hash_t v1(0);
239 0 : hash_t v2(0);
240 0 : get_64bits(v1, v2);
241 :
242 0 : f_hash ^= (f_hash << 7) ^ (v1 * (f_hash >> 3))
243 0 : ^ (~((f_hash << 11) + (v2 ^ (f_hash >> 5))));
244 : }
245 :
246 0 : if(f_temp_size > 0 && f_size > 0)
247 : {
248 0 : memmove(f_temp + f_size, f_temp, f_temp_size);
249 : }
250 :
251 0 : f_temp_size += f_size;
252 0 : for(int in(0); f_size > 0; ++in)
253 : {
254 0 : --f_size;
255 0 : f_temp[in] = f_buffer[f_size];
256 : }
257 0 : }
258 :
259 :
260 0 : hash_t hash::get() const
261 : {
262 0 : hash_t h(f_hash);
263 :
264 0 : std::size_t sz(size());
265 0 : if(sz > 0)
266 : {
267 0 : hash_t loop(0);
268 : hash_t v1;
269 : hash_t v2;
270 0 : peek_64bits(v1, v2);
271 :
272 0 : if(sz >= 4)
273 : {
274 0 : h ^= ~((h << 11) + (v1 ^ (h >> 5)));
275 0 : ++loop;
276 :
277 0 : sz -= 4;
278 0 : v1 = v2;
279 : }
280 :
281 0 : if(sz >= 3)
282 : {
283 0 : v2 = v1 >> 8;
284 0 : if(loop != 0)
285 : {
286 0 : h ^= (h << 7) ^ v2 * (h >> 3);
287 : }
288 : else
289 : {
290 0 : h ^= (~((h << 11) + (v2 ^ (h >> 5))));
291 : }
292 0 : ++loop;
293 :
294 0 : sz = 1;
295 0 : v1 &= 255;
296 : }
297 0 : else if(sz == 2)
298 : {
299 0 : if(loop != 0)
300 : {
301 0 : h ^= (h << 7) ^ v1 * (h >> 3);
302 : }
303 : else
304 : {
305 0 : h ^= (~((h << 11) + (v1 ^ (h >> 5))));
306 : }
307 : //++loop; -- not necessary, we won't reuse it
308 :
309 0 : sz = 0;
310 : }
311 :
312 0 : if(sz > 0)
313 : {
314 0 : h += (v1 ^ (h * 0xA5A5A5A5)) + loop;
315 : }
316 : }
317 :
318 0 : return h;
319 : }
320 :
321 :
322 :
323 : } // namespace snapdatabase
324 : // vim: ts=4 sw=4 et
|