| Disk ARchive 2.6.11 Full featured and portable backup and archiving tool

limitint.hpp
Go to the documentation of this file.
1 /*********************************************************************/
2 // dar - disk archive - a backup/restoration program
3 // Copyright (C) 2002-2020 Denis Corbin
4 //
5 // This program is free software; you can redistribute it and/or
6 // modify it under the terms of the GNU General Public License
7 // as published by the Free Software Foundation; either version 2
8 // of the License, or (at your option) any later version.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with this program; if not, write to the Free Software
17 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 //
19 // to contact the author : http://dar.linux.free.fr/email.html
20 /*********************************************************************/
21
30
31
32 #ifndef LIMITINT_HPP
33 #define LIMITINT_HPP
34
35 #include "../my_config.h"
36
37 extern "C"
38 {
39 #if HAVE_SYS_TYPES_H
40 #include <sys/types.h>
41 #endif
42
43 #if HAVE_UNISTD_H
44 #include <unistd.h>
45 #endif
46
47 #if HAVE_STRING_H
48 #include <string.h>
49 #endif
50
51 #if HAVE_STRINGS_H
52 #include <strings.h>
53 #endif
54 } // end extern "C"
55
56 #include <typeinfo>
57 #include "integers.hpp"
58 #include "erreurs.hpp"
59 #include "int_tools.hpp"
60 #include "proto_generic_file.hpp"
61
62
63 #define ZEROED_SIZE 50
64
65 namespace libdar
66 {
67
70
85
86
87 template<class B> class limitint
88 {
89 public :
90
91 #if SIZEOF_OFF_T > SIZEOF_TIME_T
92 #if SIZEOF_OFF_T > SIZEOF_SIZE_T
93 limitint(off_t a = 0)
94 { limitint_from(a); };
95 #else
96 limitint(size_t a = 0)
97 { limitint_from(a); };
98 #endif
99 #else
100 #if SIZEOF_TIME_T > SIZEOF_SIZE_T
101 limitint(time_t a = 0)
102 { limitint_from(a); };
103 #else
104 limitint(size_t a = 0)
105 { limitint_from(a); };
106 #endif
107 #endif
108
109 // read an limitint from a file
110 limitint(proto_generic_file & x);
111
112 limitint(const limitint & ref) = default;
113 limitint(limitint && ref) noexcept = default;
114 limitint & operator = (const limitint & ref) = default;
115 limitint & operator = (limitint && ref) noexcept = default;
116
117 // for coherent footprint with real infinint
118 ~limitint() = default;
119
120 void dump(proto_generic_file &x) const; // write byte sequence to file
121 void read(proto_generic_file &f) { build_from_file(f); };
122
123 limitint & operator += (const limitint & ref);
124 limitint & operator -= (const limitint & ref);
125 limitint & operator *= (const limitint & ref);
126 template <class T> limitint power(const T & exponent) const;
127 limitint & operator /= (const limitint & ref);
128 limitint & operator %= (const limitint & ref);
129 limitint & operator &= (const limitint & ref);
130 limitint & operator |= (const limitint & ref);
131 limitint & operator ^= (const limitint & ref);
132 limitint & operator >>= (U_32 bit);
133 limitint & operator >>= (limitint bit);
134 limitint & operator <<= (U_32 bit);
135 limitint & operator <<= (limitint bit);
136 limitint operator ++(int a)
137 { limitint ret = *this; ++(*this); return ret; };
138 limitint operator --(int a)
139 { limitint ret = *this; --(*this); return ret; };
140 limitint & operator ++()
141 { return *this += 1; };
142 limitint & operator --()
143 { return *this -= 1; };
144
145 U_32 operator % (U_32 arg) const;
146
147 // increment the argument up to a legal value for its storage type and decrement the object in consequence
148 // note that the initial value of the argument is not ignored !
149 // when the object is null the value of the argument stays the same as before
150 template <class T>void unstack(T &v)
151 { limitint_unstack_to(v); }
152
153 limitint get_storage_size() const;
154 // it returns number of byte of information necessary to store the integer
155
156 unsigned char operator [] (const limitint & position) const;
157 // return in little endian order the information bytes storing the integer
158
159 bool is_zero() const { return field == 0; };
160
161 bool operator < (const limitint &x) const { return field < x.field; };
162 bool operator == (const limitint &x) const { return field == x.field; };
163 bool operator > (const limitint &x) const { return field > x.field; };
164 bool operator <= (const limitint &x) const { return field <= x.field; };
165 bool operator != (const limitint &x) const { return field != x.field; };
166 bool operator >= (const limitint &x) const { return field >= x.field; };
167 static bool is_system_big_endian();
168
169 B debug_get_max() const { return max_value; };
170 B debug_get_bytesize() const { return bytesize; };
171 B debug_get_field() const { return field; };
172
173 private :
174
175 B field;
176
177 void build_from_file(proto_generic_file & x);
178 template <class T> void limitint_from(T a);
179 template <class T> T max_val_of(T x);
180 template <class T> void limitint_unstack_to(T &a);
181
183 // static statments
184 //
185 static const int TG = 4;
186 static const U_32 sizeof_field = sizeof(B); // number of bytes
187
188 enum endian { big_endian, little_endian, not_initialized };
189 using group = unsigned char[TG];
190
191 static endian used_endian;
192 static const U_I bytesize = sizeof(B);
193 static const B max_value = ~B(0) > 0 ? ~B(0) : ~(B(1) << (bytesize*8 - 1));
194 static U_8 zeroed_field[ZEROED_SIZE];
195
196 static void setup_endian();
197 };
198
199 template <class B> U_8 limitint<B>::zeroed_field[ZEROED_SIZE];
200
201 template <class B> limitint<B> operator + (const limitint<B> &, const limitint<B> &);
202 template <class B> inline limitint<B> operator + (const limitint<B> & a, U_I b)
203 { return a + limitint<B>(b); }
204 template <class B> limitint<B> operator - (const limitint<B> &, const limitint<B> &);
205 template <class B> inline limitint<B> operator - (const limitint<B> & a, U_I b)
206 { return a - limitint<B>(b); }
207 template <class B> limitint<B> operator * (const limitint<B> &, const limitint<B> &);
208 template <class B> inline limitint<B> operator * (const limitint<B> & a, U_I b)
209 { return a * limitint<B>(b); }
210 template <class B> limitint<B> operator / (const limitint<B> &, const limitint<B> &);
211 template <class B> limitint<B> operator / (const limitint<B> & a, U_I b)
212 { return a / limitint<B>(b); }
213 template <class B> limitint<B> operator % (const limitint<B> &, const limitint<B> &);
214 template <class B> limitint<B> operator >> (const limitint<B> & a, U_32 bit);
215 template <class B> limitint<B> operator >> (const limitint<B> & a, const limitint<B> & bit);
216 template <class B> limitint<B> operator << (const limitint<B> & a, U_32 bit);
217 template <class B> limitint<B> operator << (const limitint<B> & a, const limitint<B> & bit);
218 template <class B> limitint<B> operator & (const limitint<B> & a, U_32 bit);
219 template <class B> limitint<B> operator & (const limitint<B> & a, const limitint<B> & bit);
220 template <class B> limitint<B> operator | (const limitint<B> & a, U_32 bit);
221 template <class B> limitint<B> operator | (const limitint<B> & a, const limitint<B> & bit);
222 template <class B> limitint<B> operator ^ (const limitint<B> & a, U_32 bit);
223 template <class B> limitint<B> operator ^ (const limitint<B> & a, const limitint<B> & bit);
224
225 template <class T> inline void euclide(T a, T b, T & q, T &r)
226 {
227
228 q = a/b; r = a%b;
229 }
230
231 template <class B> inline void euclide(limitint<B> a, U_I b, limitint<B> & q, limitint<B> &r)
232 {
233 euclide(a, limitint<B>(b), q, r);
234 }
235
236 #ifndef INFININT_BASE_TYPE
237 #error INFININT_BASE_TYPE not defined cannot instantiate template
238 #else
239 using infinint = limitint<INFININT_BASE_TYPE>;
240 #endif
241 } // end of namespace
245
246 namespace libdar
247 {
248
249 template <class B> typename limitint<B>::endian limitint<B>::used_endian = not_initialized;
250
251
252 template <class B> limitint<B>::limitint(proto_generic_file & x)
253 {
254 build_from_file(x);
255 }
256
257
258 template <class B> void limitint<B>::build_from_file(proto_generic_file & x)
259 {
260 unsigned char a;
261 bool fin = false;
262 limitint<B> skip = 0;
263 char *ptr = (char *)&field;
264 S_I lu;
265 int_tools_bitfield bf;
266
267 while(!fin)
268 {
269 lu = x.read((char *)&a, 1);
270
271 if(lu <= 0)
272 throw Erange("limitint::build_from_file(proto_generic_file)", gettext("Reached end of file before all data could be read"));
273
274 if(a == 0)
275 ++skip;
276 else // end of size field
277 {
278 // computing the size to read
279 U_I pos = 0;
280
281 int_tools_expand_byte(a, bf);
282 for(S_I i = 0; i < 8; ++i)
283 pos += bf[i];
284 if(pos != 1)
285 throw Erange("limitint::build_from_file(proto_generic_file)", gettext("Badly formed \"infinint\" or not supported format")); // more than 1 bit is set to 1
286
287 pos = 0;
288 while(bf[pos] == 0)
289 ++pos;
290 pos += 1; // bf starts at zero, but bit zero means 1 TG of length
291
292 skip *= 8;
293 skip += pos;
294 skip *= TG;
295
296 if(skip.field > bytesize)
297 throw Elimitint();
298
299 field = 0; // important to also clear "unread" bytes by this call
300 lu = x.read(ptr, skip.field);
301
302 if(used_endian == not_initialized)
303 setup_endian();
304 if(used_endian == little_endian)
305 int_tools_swap_bytes((unsigned char *)ptr, skip.field);
306 else
307 field >>= (bytesize - skip.field)*8;
308 fin = true;
309 }
310 }
311 }
312
313
314 template <class B> void limitint<B>::dump(proto_generic_file & x) const
315 {
316 B width = bytesize;
317 B pos;
318 unsigned char last_width;
319 B justification;
320 S_I direction = +1;
321 unsigned char *ptr, *fin;
322
323
324 if(used_endian == not_initialized)
325 setup_endian();
326
327 if(used_endian == little_endian)
328 {
329 direction = -1;
330 ptr = (unsigned char *)(&field) + (bytesize - 1);
331 fin = (unsigned char *)(&field) - 1;
332 }
333 else
334 {
335 direction = +1;
336 ptr = (unsigned char *)(&field);
337 fin = (unsigned char *)(&field) + bytesize;
338 }
339
340 while(ptr != fin && *ptr == 0)
341 {
342 ptr += direction;
343 --width;
344 }
345 if(width == 0)
346 width = 1; // minimum size of information is 1 byte
347
348 // "width" is the informational field size in byte
349 // TG is the width in TG, thus the number of bit that must have
350 // the preamble
351 euclide(width, (const B)(TG), width, justification);
352 if(justification != 0)
353 // in case we need to add some bytes to have a width multiple of TG
354 ++width; // we need then one more group to have a width multiple of TG
355
356 euclide(width, (const B)(8), width, pos);
357 if(pos == 0)
358 {
359 width--; // division is exact, only last bit of the preambule is set
360 last_width = 0x80 >> 7;
361 // as we add the last byte separately width gets shorter by 1 byte
362 }
363 else // division non exact, the last_width (last byte), make the rounding
364 {
365 U_16 pos_s = (U_16)(0xFFFF & pos);
366 last_width = 0x80 >> (pos_s - 1);
367 }
368
369 // now we write the preamble except the last byte. All these are zeros.
370
371 while(width != 0)
372 if(width > ZEROED_SIZE)
373 {
374 x.write((char *)zeroed_field, ZEROED_SIZE);
375 width -= ZEROED_SIZE;
376 }
377 else
378 {
379 x.write((char *)zeroed_field, width);
380 width = 0;
381 }
382
383 // now we write the last byte of the preambule, which has only one bit set
384
385 x.write((char *)&last_width, 1);
386
387 // we need now to write some justification byte to have an informational field multiple of TG
388
389 if(justification != 0)
390 {
391 justification = TG - justification;
392 if(justification > ZEROED_SIZE)
393 throw SRC_BUG;
394 else
395 x.write((char *)zeroed_field, justification);
396 }
397
398 // now we continue dumping the informational bytes:
399 if(ptr == fin) // field is equal to zero
400 x.write((char *)zeroed_field, 1);
401 else // we have some bytes to write down
402 while(ptr != fin)
403 {
404 x.write((char *)ptr, 1);
405 ptr += direction;
406 }
407 }
408
409 template<class B> limitint<B> & limitint<B>::operator += (const limitint & arg)
410 {
411 B res = field + arg.field;
412 if(res < field || res < arg.field)
413 throw Elimitint();
414 else
415 field = res;
416
417 return *this;
418 }
419
420 template <class B> limitint<B> & limitint<B>::operator -= (const limitint & arg)
421 {
422 if(field < arg.field)
423 throw Erange("limitint::operator", gettext("Subtracting an \"infinint\" greater than the first, \"infinint\" cannot be negative"));
424
425 // now processing the operation
426
427 field -= arg.field;
428 return *this;
429 }
430
431
432 template <class B> limitint<B> & limitint<B>::operator *= (const limitint & arg)
433 {
434 static const B max_power = bytesize*8 - 1;
435
436 B total = int_tools_higher_power_of_2(field) + int_tools_higher_power_of_2(arg.field) + 1; // for an explaination about "+2" see NOTES
437 if(total > max_power) // this is a bit too much restrictive, but unless remaking bit by bit, the operation,
438 // I don't see how to simply (and fast) know the result has not overflowed.
439 // of course, it would be fast and easy to access the CPU flag register to check for overflow,
440 // but that would not be portable, and unfortunately I haven't found any standart C++ expression that
441 // could transparently access to it.
442 throw Elimitint();
443
444 total = field*arg.field;
445 if(field != 0 && arg.field != 0)
446 if(total < field || total < arg.field)
447 throw Elimitint();
448 field = total;
449 return *this;
450 }
451
452 template <class B> template<class T> limitint<B> limitint<B>::power(const T & exponent) const
453 {
454 limitint ret = 1;
455 for(T count = 0; count < exponent; ++count)
456 ret *= *this;
457
458 return ret;
459 }
460
461 template <class B> limitint<B> & limitint<B>::operator /= (const limitint & arg)
462 {
463 if(arg == 0)
464 throw Einfinint("limitint.cpp : operator /=", gettext("Division by zero"));
465
466 field /= arg.field;
467 return *this;
468 }
469
470 template <class B> limitint<B> & limitint<B>::operator %= (const limitint & arg)
471 {
472 if(arg == 0)
473 throw Einfinint("limitint.cpp : operator %=", gettext("Division by zero"));
474
475 field %= arg.field;
476 return *this;
477 }
478
479 template <class B> limitint<B> & limitint<B>::operator >>= (U_32 bit)
480 {
481 if(bit >= sizeof_field*8)
482 field = 0;
483 else
484 field >>= bit;
485 return *this;
486 }
487
488 template <class B> limitint<B> & limitint<B>::operator >>= (limitint bit)
489 {
490 field >>= bit.field;
491 return *this;
492 }
493
494 template <class B> limitint<B> & limitint<B>::operator <<= (U_32 bit)
495 {
496 if(bit + int_tools_higher_power_of_2(field) >= bytesize*8)
497 throw Elimitint();
498 field <<= bit;
499 return *this;
500 }
501
502 template <class B> limitint<B> & limitint<B>::operator <<= (limitint bit)
503 {
504 if(bit.field + int_tools_higher_power_of_2(field) >= bytesize*8)
505 throw Elimitint();
506 field <<= bit.field;
507 return *this;
508 }
509
510 template <class B> limitint<B> & limitint<B>::operator &= (const limitint & arg)
511 {
512 field &= arg.field;
513 return *this;
514 }
515
516 template <class B> limitint<B> & limitint<B>::operator |= (const limitint & arg)
517 {
518 field |= arg.field;
519 return *this;
520 }
521
522 template <class B> limitint<B> & limitint<B>::operator ^= (const limitint & arg)
523 {
524 field ^= arg.field;
525 return *this;
526 }
527
528 template <class B> U_32 limitint<B>::operator % (U_32 arg) const
529 {
530 return U_32(field % arg);
531 }
532
533 template <class B> template <class T> void limitint<B>::limitint_from(T a)
534 {
535 if(sizeof(a) <= bytesize || a <= (T)(max_value))
536 field = B(a);
537 else
538 throw Elimitint();
539 }
540
541 template <class B> template <class T> T limitint<B>::max_val_of(T x)
542 {
543 x = 0;
544 x = ~x;
545
546 if(x < 1) // T is a signed integer type, we are not comparing to zero to avoid compiler warning when the template is used against unsigned integers
547 {
548 x = 1;
549 x = int_tools_rotate_right_one_bit(x);
550 x = ~x;
551 }
552
553 return x;
554 }
555
556 template <class B> template <class T> void limitint<B>::limitint_unstack_to(T &a)
557 {
558
559 // T is supposed to be an unsigned "integer"
560 // (ie.: sizeof returns the width of the storage bit field and no sign bit is present)
561 // Note : static here avoids the recalculation of max_T at each call
562 static const T max_T = max_val_of(a);
563 T step = max_T - a;
564
565 if(field < (B)(step) && (T)(field) < step)
566 {
567 a += field;
568 field = 0;
569 }
570 else
571 {
572 field -= step;
573 a = max_T;
574 }
575 }
576
577 template <class B> limitint<B> limitint<B>::get_storage_size() const
578 {
579 B tmp = field;
580 B ret = 0;
581
582 while(tmp != 0)
583 {
584 tmp >>= 8;
585 ret++;
586 }
587
588 return limitint<B>(ret);
589 }
590
591 template <class B> unsigned char limitint<B>::operator [] (const limitint & position) const
592 {
593 B tmp = field;
594 B index = position.field; // C++ has only class protection, not object protection
595
596 while(index > 0)
597 {
598 tmp >>= 8;
599 index--;
600 }
601
602 return (unsigned char)(tmp & 0xFF);
603 }
604
605 template <class B> void limitint<B>::setup_endian()
606 {
607 if(integers_system_is_big_endian())
608 used_endian = big_endian;
609 else
610 used_endian = little_endian;
611
612 (void)memset(zeroed_field, 0, ZEROED_SIZE);
613 }
614
615
616 template <class B> bool limitint<B>::is_system_big_endian()
617 {
618 if(used_endian == not_initialized)
619 setup_endian();
620
621 switch(used_endian)
622 {
623 case big_endian:
624 return true;
625 case little_endian:
626 return false;
627 case not_initialized:
628 throw SRC_BUG;
629 default:
630 throw SRC_BUG;
631 }
632 }
633
634
638
639 template <class B> limitint<B> operator + (const limitint<B> & a, const limitint<B> & b)
640 {
641 limitint<B> ret = a;
642 ret += b;
643
644 return ret;
645 }
646
647 template <class B> limitint<B> operator - (const limitint<B> & a, const limitint<B> & b)
648 {
649 limitint<B> ret = a;
650 ret -= b;
651
652 return ret;
653 }
654
655 template <class B> limitint<B> operator * (const limitint<B> & a, const limitint<B> & b)
656 {
657 limitint<B> ret = a;
658 ret *= b;
659
660 return ret;
661 }
662
663 template <class B> limitint<B> operator / (const limitint<B> & a, const limitint<B> & b)
664 {
665 limitint<B> ret = a;
666 ret /= b;
667
668 return ret;
669 }
670
671 template <class B> limitint<B> operator % (const limitint<B> & a, const limitint<B> & b)
672 {
673 limitint<B> ret = a;
674 ret %= b;
675
676 return ret;
677 }
678
679 template <class B> limitint<B> operator >> (const limitint<B> & a, U_32 bit)
680 {
681 limitint<B> ret = a;
682 ret >>= bit;
683 return ret;
684 }
685
686 template <class B> limitint<B> operator >> (const limitint<B> & a, const limitint<B> & bit)
687 {
688 limitint<B> ret = a;
689 ret >>= bit;
690 return ret;
691 }
692
693 template <class B> limitint<B> operator << (const limitint<B> & a, U_32 bit)
694 {
695 limitint<B> ret = a;
696 ret <<= bit;
697 return ret;
698 }
699
700 template <class B> limitint<B> operator << (const limitint<B> & a, const limitint<B> & bit)
701 {
702 limitint<B> ret = a;
703 ret <<= bit;
704 return ret;
705 }
706
707 template <class B> limitint<B> operator & (const limitint<B> & a, U_32 bit)
708 {
709 limitint<B> ret = a;
710 ret &= bit;
711 return ret;
712 }
713
714 template <class B> limitint<B> operator & (const limitint<B> & a, const limitint<B> & bit)
715 {
716 limitint<B> ret = a;
717 ret &= bit;
718 return ret;
719 }
720
721 template <class B> limitint<B> operator | (const limitint<B> & a, U_32 bit)
722 {
723 limitint<B> ret = a;
724 ret |= bit;
725 return ret;
726 }
727
728 template <class B> limitint<B> operator | (const limitint<B> & a, const limitint<B> & bit)
729 {
730 limitint<B> ret = a;
731 ret |= bit;
732 return ret;
733 }
734
735 template <class B> limitint<B> operator ^ (const limitint<B> & a, U_32 bit)
736 {
737 limitint<B> ret = a;
738 ret ^= bit;
739 return ret;
740 }
741
742 template <class B> limitint<B> operator ^ (const limitint<B> & a, const limitint<B> & bit)
743 {
744 limitint<B> ret = a;
745 ret ^= bit;
746 return ret;
747 }
748
750
751 } // end of namespace
752
753 #endif
int_tools.hpp
elementary operation for infinint integers
libdar::operator<<
std::ostream & operator<<(std::ostream &ref, const infinint &arg)
specific << operator to use infinint in std::ostream
libdar::proto_generic_file
ancestor class of generic_file
Definition: proto_generic_file.hpp:55
integers.hpp
are defined here basic integer types that tend to be portable
proto_generic_file.hpp
precursor class of generic_file used to avoid cyclic dependencies with storage and infinint
libdar::integers_system_is_big_endian
bool integers_system_is_big_endian()
returns true if the system is big endian, false else
erreurs.hpp
contains all the excetion class thrown by libdar
libdar::limitint
Definition: limitint.hpp:88
libdar
libdar namespace encapsulate all libdar symbols
Definition: archive.hpp:47