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/bigint/bigint.h"
31 :
32 : #include "snapdatabase/exception.h"
33 :
34 :
35 : // C++ lib
36 : //
37 : #include <cstring>
38 : #include <iostream>
39 : #include <string>
40 :
41 :
42 : // last include
43 : //
44 : #include <snapdev/poison.h>
45 :
46 :
47 :
48 : namespace snapdatabase
49 : {
50 :
51 :
52 :
53 :
54 :
55 1038885 : int512_t::int512_t()
56 : {
57 1038885 : }
58 :
59 :
60 0 : int512_t::int512_t(int512_t const & rhs)
61 : {
62 0 : for(int idx(0); idx < 7; ++idx)
63 : {
64 0 : f_value[idx] = rhs.f_value[idx];
65 : }
66 0 : f_high_value = rhs.f_high_value;
67 0 : }
68 :
69 :
70 1038885 : int512_t::int512_t(uint512_t const & rhs)
71 : {
72 8311080 : for(int idx(0); idx < 7; ++idx)
73 : {
74 7272195 : f_value[idx] = rhs.f_value[idx];
75 : }
76 1038885 : f_high_value = rhs.f_value[7];
77 1038885 : }
78 :
79 :
80 0 : int512_t::int512_t(std::initializer_list<std::uint64_t> rhs)
81 : {
82 0 : if(rhs.size() > std::size(f_value))
83 : {
84 : throw snapdatabase_out_of_range(
85 : "rhs array too large for int512_t constructor ("
86 0 : + std::to_string(rhs.size())
87 0 : + " > "
88 0 : + std::to_string(std::size(f_value))
89 0 : + ").");
90 : }
91 :
92 0 : std::copy(rhs.begin(), rhs.end(), f_value);
93 0 : if(rhs.size() < std::size(f_value))
94 : {
95 0 : std::memset(reinterpret_cast<uint8_t *>(f_value) + rhs.size(), 0, sizeof(f_value) - rhs.size());
96 : }
97 0 : }
98 :
99 :
100 1038885 : std::size_t int512_t::bit_size() const
101 : {
102 1038885 : int512_t p;
103 1038885 : if(is_negative())
104 : {
105 2 : p -= *this;
106 2 : if(p.is_negative())
107 : {
108 0 : return 512;
109 : }
110 : }
111 : else
112 : {
113 1038883 : p = *this;
114 : }
115 :
116 1038885 : if(p.f_high_value != 0)
117 : {
118 0 : return (__builtin_clzll(p.f_high_value) ^ 0x3F) + 7 * 64 + 1;
119 : }
120 :
121 1038885 : std::size_t result(512 - 63);
122 7272216 : for(int idx(6); idx >= 0; --idx)
123 : {
124 7272195 : result -= 64;
125 7272195 : if(p.f_value[idx] != 0)
126 : {
127 1038864 : return (__builtin_clzll(p.f_value[idx]) ^ 0x3F) + result;
128 : }
129 : }
130 :
131 21 : return 0;
132 : }
133 :
134 :
135 0 : int512_t int512_t::operator - () const
136 : {
137 0 : int512_t neg;
138 0 : neg -= *this;
139 0 : return neg;
140 : }
141 :
142 :
143 0 : int512_t & int512_t::operator += (int512_t const & rhs)
144 : {
145 0 : add512(f_value, rhs.f_value); // the add includes the high value
146 0 : return *this;
147 : }
148 :
149 :
150 2 : int512_t & int512_t::operator -= (int512_t const & rhs)
151 : {
152 2 : sub512(f_value, rhs.f_value); // the sub includes the high value
153 2 : return *this;
154 : }
155 :
156 :
157 :
158 :
159 16703418 : uint512_t::uint512_t()
160 : {
161 16703418 : }
162 :
163 :
164 2458078 : uint512_t::uint512_t(uint512_t const & rhs)
165 : {
166 2458078 : f_value[0] = rhs.f_value[0];
167 2458078 : f_value[1] = rhs.f_value[1];
168 2458078 : f_value[2] = rhs.f_value[2];
169 2458078 : f_value[3] = rhs.f_value[3];
170 2458078 : f_value[4] = rhs.f_value[4];
171 2458078 : f_value[5] = rhs.f_value[5];
172 2458078 : f_value[6] = rhs.f_value[6];
173 2458078 : f_value[7] = rhs.f_value[7];
174 2458078 : }
175 :
176 :
177 0 : uint512_t::uint512_t(int512_t const & rhs)
178 : {
179 0 : f_value[0] = rhs.f_value[0];
180 0 : f_value[1] = rhs.f_value[1];
181 0 : f_value[2] = rhs.f_value[2];
182 0 : f_value[3] = rhs.f_value[3];
183 0 : f_value[4] = rhs.f_value[4];
184 0 : f_value[5] = rhs.f_value[5];
185 0 : f_value[6] = rhs.f_value[6];
186 0 : f_value[7] = rhs.f_high_value;
187 0 : }
188 :
189 :
190 76 : uint512_t::uint512_t(std::initializer_list<std::uint64_t> rhs)
191 : {
192 76 : if(rhs.size() > std::size(f_value))
193 : {
194 : throw snapdatabase_out_of_range(
195 : "rhs array too large for int512_t constructor ("
196 0 : + std::to_string(rhs.size())
197 0 : + " > "
198 0 : + std::to_string(std::size(f_value))
199 0 : + ").");
200 : }
201 :
202 76 : std::copy(rhs.begin(), rhs.end(), f_value);
203 76 : if(rhs.size() < std::size(f_value))
204 : {
205 0 : std::memset(reinterpret_cast<uint8_t *>(f_value) + rhs.size(), 0, sizeof(f_value) - rhs.size());
206 : }
207 76 : }
208 :
209 :
210 2 : uint512_t & uint512_t::operator = (uint512_t const & rhs)
211 : {
212 2 : f_value[0] = rhs.f_value[0];
213 2 : f_value[1] = rhs.f_value[1];
214 2 : f_value[2] = rhs.f_value[2];
215 2 : f_value[3] = rhs.f_value[3];
216 2 : f_value[4] = rhs.f_value[4];
217 2 : f_value[5] = rhs.f_value[5];
218 2 : f_value[6] = rhs.f_value[6];
219 2 : f_value[7] = rhs.f_value[7];
220 :
221 2 : return *this;
222 : }
223 :
224 :
225 0 : uint512_t & uint512_t::operator = (int512_t const & rhs)
226 : {
227 0 : f_value[0] = rhs.f_value[0];
228 0 : f_value[1] = rhs.f_value[1];
229 0 : f_value[2] = rhs.f_value[2];
230 0 : f_value[3] = rhs.f_value[3];
231 0 : f_value[4] = rhs.f_value[4];
232 0 : f_value[5] = rhs.f_value[5];
233 0 : f_value[6] = rhs.f_value[6];
234 0 : f_value[7] = rhs.f_high_value;
235 :
236 0 : return *this;
237 : }
238 :
239 :
240 8 : size_t uint512_t::bit_size() const
241 : {
242 8 : std::size_t result(512);
243 65 : for(int idx(7); idx >= 0; --idx)
244 : {
245 64 : result -= 64;
246 64 : if(f_value[idx] != 0)
247 : {
248 7 : return (__builtin_clzll(f_value[idx]) ^ 0x3F) + result;
249 : }
250 : }
251 :
252 1 : return 0;
253 : }
254 :
255 :
256 38 : void uint512_t::lsl(int count)
257 : {
258 38 : if(count < 0)
259 : {
260 : throw snapdatabase_out_of_range(
261 : "lsl() cannot be called with a negative value ("
262 0 : + std::to_string(count)
263 0 : + ").");
264 : }
265 :
266 38 : if(count > 512)
267 : {
268 0 : count = 512;
269 : }
270 :
271 38 : int pos(8);
272 38 : int move(count / 64);
273 38 : int const shift(count % 64);
274 38 : if(move > 0)
275 : {
276 0 : pos = 8 - move;
277 0 : if(move < 8)
278 : {
279 0 : memmove(f_value + move, f_value, pos * 8);
280 : }
281 0 : memset(f_value, 0, move * 8);
282 : }
283 38 : if(shift != 0)
284 : {
285 38 : int remainder(64 - shift);
286 :
287 38 : std::uint64_t extra(0);
288 646 : while(move < 8)
289 : {
290 304 : std::uint64_t const next(f_value[move] >> remainder);
291 304 : f_value[move] = (f_value[move] << shift) | extra;
292 304 : extra = next;
293 304 : ++move;
294 : }
295 : }
296 38 : }
297 :
298 :
299 40 : void uint512_t::lsr(int count)
300 : {
301 40 : if(count < 0)
302 : {
303 : throw snapdatabase_out_of_range(
304 : "lsr() cannot be called with a negative value ("
305 0 : + std::to_string(count)
306 0 : + ").");
307 : }
308 :
309 40 : if(count > 512)
310 : {
311 0 : count = 512;
312 : }
313 :
314 40 : int pos(8);
315 40 : int const move(count / 64);
316 40 : int const shift(count % 64);
317 40 : if(move > 0)
318 : {
319 0 : pos = 8 - move;
320 0 : if(move < 8)
321 : {
322 0 : memmove(f_value, f_value + move, pos * 8);
323 : }
324 0 : memset(f_value + pos * 8, 0, move * 8);
325 : }
326 40 : if(shift != 0)
327 : {
328 40 : int remainder(64 - shift);
329 :
330 40 : std::uint64_t extra(0);
331 680 : while(pos > 0)
332 : {
333 320 : --pos;
334 320 : std::uint64_t const next(f_value[pos] << remainder);
335 320 : f_value[pos] = (f_value[pos] >> shift) | extra;
336 320 : extra = next;
337 : }
338 : }
339 40 : }
340 :
341 :
342 0 : bool uint512_t::is_zero() const
343 : {
344 0 : return f_value[0] == 0
345 0 : && f_value[1] == 0
346 0 : && f_value[2] == 0
347 0 : && f_value[3] == 0
348 0 : && f_value[4] == 0
349 0 : && f_value[5] == 0
350 0 : && f_value[6] == 0
351 0 : && f_value[7] == 0;
352 : }
353 :
354 :
355 0 : int uint512_t::compare(uint512_t const & rhs) const
356 : {
357 0 : int idx(8);
358 0 : while(idx > 0)
359 : {
360 0 : --idx;
361 0 : if(f_value[idx] != rhs.f_value[idx])
362 : {
363 0 : return f_value[idx] > rhs.f_value[idx] ? 1 : -1;
364 : }
365 : }
366 :
367 0 : return 0;
368 : }
369 :
370 :
371 : // we have this one because we need it to convert back to a string
372 : //
373 0 : uint512_t & uint512_t::div(uint512_t const & rhs, uint512_t & remainder)
374 : {
375 0 : bool zero(true);
376 0 : for(int idx(0); idx < 8; ++idx)
377 : {
378 0 : if(f_value[idx] != 0)
379 : {
380 0 : zero = false;
381 0 : break;
382 : }
383 : }
384 0 : if(zero)
385 : {
386 0 : throw snapdatabase_logic_error("Division by zero not allowed in uint512_t.");
387 : }
388 :
389 0 : int c(compare(rhs));
390 0 : if(c == -1)
391 : {
392 : // a / (a + n) = 0 (remainder = a) where n > 0
393 : //
394 0 : remainder = *this;
395 0 : memset(f_value, 0, sizeof(f_value));
396 0 : return *this;
397 : }
398 :
399 0 : if(c == 0)
400 : {
401 : // a / a = 1 (remainder = 0)
402 : //
403 0 : memset(remainder.f_value, 0, sizeof(remainder.f_value));
404 0 : f_value[0] = 1;
405 0 : memset(f_value + 1, 0, sizeof(f_value) - sizeof(f_value[0]));
406 0 : return *this;
407 : }
408 :
409 : // in this case we have to do the division
410 : //
411 : // TBD: we could also use these size to handle the two previous
412 : // special cases; we'd have to determine which of the compare()
413 : // and the bit_size() is faster...
414 : //
415 0 : std::size_t lhs_size(bit_size());
416 0 : std::size_t rhs_size(rhs.bit_size());
417 :
418 0 : remainder = *this;
419 0 : memset(f_value, 0, sizeof(f_value));
420 :
421 0 : uint512_t divisor(rhs);
422 0 : divisor.lsl(lhs_size - rhs_size);
423 :
424 0 : uint512_t one;
425 0 : one.f_value[0] = 1;
426 :
427 : // this is it! this loop calculates the division the very slow way
428 : // (TODO we need to use (a / b) and (a % b) and do all the math and
429 : // it will be much faster... the bit by bit operations are slow even
430 : // if they work magic)
431 0 : do
432 : {
433 0 : lsl(1);
434 0 : c = remainder.compare(divisor);
435 0 : if(c >= 0)
436 : {
437 0 : remainder -= divisor;
438 0 : operator += (one);
439 : }
440 0 : divisor.lsr(1);
441 : }
442 0 : while(!divisor.is_zero());
443 :
444 0 : return *this;
445 : }
446 :
447 :
448 2 : uint512_t uint512_t::operator - () const
449 : {
450 2 : uint512_t neg;
451 2 : neg -= *this;
452 2 : return neg;
453 : }
454 :
455 :
456 48268881 : uint512_t & uint512_t::operator += (uint512_t const & rhs)
457 : {
458 48268881 : add512(f_value, rhs.f_value);
459 48268881 : return *this;
460 : }
461 :
462 :
463 2 : uint512_t & uint512_t::operator -= (uint512_t const & rhs)
464 : {
465 2 : sub512(f_value, rhs.f_value);
466 2 : return *this;
467 : }
468 :
469 :
470 2 : uint512_t & uint512_t::operator *= (uint512_t const & rhs)
471 : {
472 : // this is a very slow way to do a multiplication, but very easy,
473 : // we do not use it much so we're fine for now...
474 : //
475 2 : uint512_t lhs(*this);
476 :
477 2 : uint512_t factor(rhs);
478 2 : if((factor.f_value[0] & 1) == 0)
479 : {
480 2 : lhs.f_value[0] = 0;
481 2 : lhs.f_value[1] = 0;
482 2 : lhs.f_value[2] = 0;
483 2 : lhs.f_value[3] = 0;
484 2 : lhs.f_value[4] = 0;
485 2 : lhs.f_value[5] = 0;
486 2 : lhs.f_value[6] = 0;
487 2 : lhs.f_value[7] = 0;
488 : }
489 :
490 : for(;;)
491 : {
492 78 : factor.lsr(1);
493 40 : if(factor == 0)
494 : {
495 2 : break;
496 : }
497 :
498 38 : lhs.lsl(1);
499 38 : if((factor.f_value[0] & 1) != 0)
500 : {
501 14 : *this += lhs;
502 : }
503 : }
504 :
505 2 : return *this;
506 : }
507 :
508 :
509 40 : bool uint512_t::operator == (uint64_t rhs) const
510 : {
511 40 : return f_value[0] == rhs
512 2 : && f_value[1] == 0
513 2 : && f_value[2] == 0
514 2 : && f_value[3] == 0
515 2 : && f_value[4] == 0
516 2 : && f_value[5] == 0
517 2 : && f_value[6] == 0
518 42 : && f_value[7] == 0;
519 : }
520 :
521 :
522 0 : bool uint512_t::operator != (uint64_t rhs) const
523 : {
524 0 : return f_value[0] != rhs
525 0 : || f_value[1] != 0
526 0 : || f_value[2] != 0
527 0 : || f_value[3] != 0
528 0 : || f_value[4] != 0
529 0 : || f_value[5] != 0
530 0 : || f_value[6] != 0
531 0 : || f_value[7] != 0;
532 : }
533 :
534 :
535 :
536 6 : } // namespace snapdatabase
537 : // vim: ts=4 sw=4 et
|
