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

- Main Page
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

limitint.hpp
Go to the documentation of this file.
1 /*********************************************************************/
2 // dar - disk archive - a backup/restoration program
3 // Copyright (C) 2002-2052 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 "on_pool.hpp"
61
62
63 #define ZEROED_SIZE 50
64
65 namespace libdar
66 {
67
70
71
72 class generic_file;
73 class user_interaction;
74
86
87 template<class B> class limitint : public on_pool
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(generic_file & x);
111
112 // for coherent footprint with real infinint
113 ~limitint() throw(Ebug) {};
114
115 void dump(generic_file &x) const; // write byte sequence to file
116 void read(generic_file &f) { build_from_file(f); };
117
118 limitint & operator += (const limitint & ref);
119 limitint & operator -= (const limitint & ref);
120 limitint & operator *= (const limitint & ref);
121 template <class T> limitint power(const T & exponent) const;
122 limitint & operator /= (const limitint & ref);
123 limitint & operator %= (const limitint & ref);
124 limitint & operator &= (const limitint & ref);
125 limitint & operator |= (const limitint & ref);
126 limitint & operator ^= (const limitint & ref);
127 limitint & operator >>= (U_32 bit);
128 limitint & operator >>= (limitint bit);
129 limitint & operator <<= (U_32 bit);
130 limitint & operator <<= (limitint bit);
131 limitint operator ++(int a)
132 { limitint ret = *this; ++(*this); return ret; };
133 limitint operator --(int a)
134 { limitint ret = *this; --(*this); return ret; };
135 limitint & operator ++()
136 { return *this += 1; };
137 limitint & operator --()
138 { return *this -= 1; };
139
140 U_32 operator % (U_32 arg) const;
141
142 // increment the argument up to a legal value for its storage type and decrement the object in consequence
143 // note that the initial value of the argument is not ignored !
144 // when the object is null the value of the argument stays the same as before
145 template <class T>void unstack(T &v)
146 { limitint_unstack_to(v); }
147
148 limitint get_storage_size() const;
149 // it returns number of byte of information necessary to store the integer
150
151 unsigned char operator [] (const limitint & position) const;
152 // return in little endian order the information bytes storing the integer
153
154 bool is_zero() const { return field == 0; };
155
156 bool operator < (const limitint &x) const { return field < x.field; };
157 bool operator == (const limitint &x) const { return field == x.field; };
158 bool operator > (const limitint &x) const { return field > x.field; };
159 bool operator <= (const limitint &x) const { return field <= x.field; };
160 bool operator != (const limitint &x) const { return field != x.field; };
161 bool operator >= (const limitint &x) const { return field >= x.field; };
162 static bool is_system_big_endian();
163
164 B debug_get_max() const { return max_value; };
165 B debug_get_bytesize() const { return bytesize; };
166 B debug_get_field() const { return field; };
167
168 private :
169 static const int TG = 4;
170 static const U_32 sizeof_field = sizeof(B); // number of bytes
171
172 enum endian { big_endian, little_endian, not_initialized };
173 typedef unsigned char group[TG];
174
175 B field;
176
177 void build_from_file(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 endian used_endian;
186 static const U_I bytesize = sizeof(B);
187 static const B max_value = ~B(0) > 0 ? ~B(0) : ~(B(1) << (bytesize*8 - 1));
188 static U_8 zeroed_field[ZEROED_SIZE];
189
190 static void setup_endian();
191 };
192
193 template <class B> U_8 limitint<B>::zeroed_field[ZEROED_SIZE];
194
195 template <class B> limitint<B> operator + (const limitint<B> &, const limitint<B> &);
196 template <class B> inline limitint<B> operator + (const limitint<B> & a, U_I b)
197 { return a + limitint<B>(b); }
198 template <class B> limitint<B> operator - (const limitint<B> &, const limitint<B> &);
199 template <class B> inline limitint<B> operator - (const limitint<B> & a, U_I b)
200 { return a - limitint<B>(b); }
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> 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> limitint<B> operator >> (const limitint<B> & a, U_32 bit);
209 template <class B> limitint<B> operator >> (const limitint<B> & a, const limitint<B> & bit);
210 template <class B> limitint<B> operator << (const limitint<B> & a, U_32 bit);
211 template <class B> limitint<B> operator << (const limitint<B> & a, const limitint<B> & bit);
212 template <class B> limitint<B> operator & (const limitint<B> & a, U_32 bit);
213 template <class B> limitint<B> operator & (const limitint<B> & a, const limitint<B> & bit);
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
219 template <class T> inline void euclide(T a, T b, T & q, T &r)
220 {
221
222 q = a/b; r = a%b;
223 }
224
225 template <class B> inline void euclide(limitint<B> a, U_I b, limitint<B> & q, limitint<B> &r)
226 {
227 euclide(a, limitint<B>(b), q, r);
228 }
229
230 #ifndef INFININT_BASE_TYPE
231 #error INFININT_BASE_TYPE not defined cannot instantiate template
232 #else
233 typedef limitint<INFININT_BASE_TYPE> infinint;
234 #endif
235 } // end of namespace
239
240 #include "generic_file.hpp"
241 #include "user_interaction.hpp"
242
243 namespace libdar
244 {
245
246 template <class B> typename limitint<B>::endian limitint<B>::used_endian = not_initialized;
247
248
249 template <class B> limitint<B>::limitint(generic_file & x)
250 {
251 build_from_file(x);
252 }
253
254
255 template <class B> void limitint<B>::build_from_file(generic_file & x)
256 {
257 unsigned char a;
258 bool fin = false;
259 limitint<B> skip = 0;
260 char *ptr = (char *)&field;
261 S_I lu;
262 int_tools_bitfield bf;
263
264 while(!fin)
265 {
266 lu = x.read((char *)&a, 1);
267
268 if(lu <= 0)
269 throw Erange("limitint::build_from_file(generic_file)", gettext("Reached end of file before all data could be read"));
270
271 if(a == 0)
272 ++skip;
273 else // end of size field
274 {
275 // computing the size to read
276 U_I pos = 0;
277
278 int_tools_expand_byte(a, bf);
279 for(S_I i = 0; i < 8; ++i)
280 pos += bf[i];
281 if(pos != 1)
282 throw Erange("limitint::build_from_file(generic_file)", gettext("Badly formed \"infinint\" or not supported format")); // more than 1 bit is set to 1
283
284 pos = 0;
285 while(bf[pos] == 0)
286 ++pos;
287 pos += 1; // bf starts at zero, but bit zero means 1 TG of length
288
289 skip *= 8;
290 skip += pos;
291 skip *= TG;
292
293 if(skip.field > bytesize)
294 throw Elimitint();
295
296 field = 0; // important to also clear "unread" bytes by this call
297 lu = x.read(ptr, skip.field);
298
299 if(used_endian == not_initialized)
300 setup_endian();
301 if(used_endian == little_endian)
302 int_tools_swap_bytes((unsigned char *)ptr, skip.field);
303 else
304 field >>= (bytesize - skip.field)*8;
305 fin = true;
306 }
307 }
308 }
309
310
311 template <class B> void limitint<B>::dump(generic_file & x) const
312 {
313 B width = bytesize;
314 B pos;
315 unsigned char last_width;
316 B justification;
317 S_I direction = +1;
318 unsigned char *ptr, *fin;
319
320
321 if(used_endian == not_initialized)
322 setup_endian();
323
324 if(used_endian == little_endian)
325 {
326 direction = -1;
327 ptr = (unsigned char *)(&field) + (bytesize - 1);
328 fin = (unsigned char *)(&field) - 1;
329 }
330 else
331 {
332 direction = +1;
333 ptr = (unsigned char *)(&field);
334 fin = (unsigned char *)(&field) + bytesize;
335 }
336
337 while(ptr != fin && *ptr == 0)
338 {
339 ptr += direction;
340 --width;
341 }
342 if(width == 0)
343 width = 1; // minimum size of information is 1 byte
344
345 // "width" is the informational field size in byte
346 // TG is the width in TG, thus the number of bit that must have
347 // the preamble
348 euclide(width, (const B)(TG), width, justification);
349 if(justification != 0)
350 // in case we need to add some bytes to have a width multiple of TG
351 ++width; // we need then one more group to have a width multiple of TG
352
353 euclide(width, (const B)(8), width, pos);
354 if(pos == 0)
355 {
356 width--; // division is exact, only last bit of the preambule is set
357 last_width = 0x80 >> 7;
358 // as we add the last byte separately width gets shorter by 1 byte
359 }
360 else // division non exact, the last_width (last byte), make the rounding
361 {
362 U_16 pos_s = (U_16)(0xFFFF & pos);
363 last_width = 0x80 >> (pos_s - 1);
364 }
365
366 // now we write the preamble except the last byte. All these are zeros.
367
368 while(width != 0)
369 if(width > ZEROED_SIZE)
370 {
371 x.write((char *)zeroed_field, ZEROED_SIZE);
372 width -= ZEROED_SIZE;
373 }
374 else
375 {
376 x.write((char *)zeroed_field, width);
377 width = 0;
378 }
379
380 // now we write the last byte of the preambule, which as only one bit set
381
382 x.write((char *)&last_width, 1);
383
384 // we need now to write some justification byte to have an informational field multiple of TG
385
386 if(justification != 0)
387 {
388 justification = TG - justification;
389 if(justification > ZEROED_SIZE)
390 throw SRC_BUG;
391 else
392 x.write((char *)zeroed_field, justification);
393 }
394
395 // now we continue dumping the informational bytes:
396 if(ptr == fin) // field is equal to zero
397 x.write((char *)zeroed_field, 1);
398 else // we have some bytes to write down
399 while(ptr != fin)
400 {
401 x.write((char *)ptr, 1);
402 ptr += direction;
403 }
404 }
405
406 template<class B> limitint<B> & limitint<B>::operator += (const limitint & arg)
407 {
408 B res = field + arg.field;
409 if(res < field || res < arg.field)
410 throw Elimitint();
411 else
412 field = res;
413
414 return *this;
415 }
416
417 template <class B> limitint<B> & limitint<B>::operator -= (const limitint & arg)
418 {
419 if(field < arg.field)
420 throw Erange("limitint::operator", gettext("Subtracting an \"infinint\" greater than the first, \"infinint\" cannot be negative"));
421
422 // now processing the operation
423
424 field -= arg.field;
425 return *this;
426 }
427
428
429 template <class B> limitint<B> & limitint<B>::operator *= (const limitint & arg)
430 {
431 static const B max_power = bytesize*8 - 1;
432
433 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
434 if(total > max_power) // this is a bit too much restrictive, but unless remaking bit by bit, the operation,
435 // I don't see how to simply (and fast) know the result has not overflowed.
436 // of course, it would be fast and easy to access the CPU flag register to check for overflow,
437 // but that would not be portable, and unfortunately I haven't found any standart C++ expression that
438 // could transparently access to it.
439 throw Elimitint();
440
441 total = field*arg.field;
442 if(field != 0 && arg.field != 0)
443 if(total < field || total < arg.field)
444 throw Elimitint();
445 field = total;
446 return *this;
447 }
448
449 template <class B> template<class T> limitint<B> limitint<B>::power(const T & exponent) const
450 {
451 limitint ret = 1;
452 for(T count = 0; count < exponent; ++count)
453 ret *= *this;
454
455 return ret;
456 }
457
458 template <class B> limitint<B> & limitint<B>::operator /= (const limitint & arg)
459 {
460 if(arg == 0)
461 throw Einfinint("limitint.cpp : operator /=", gettext("Division by zero"));
462
463 field /= arg.field;
464 return *this;
465 }
466
467 template <class B> limitint<B> & limitint<B>::operator %= (const limitint & arg)
468 {
469 if(arg == 0)
470 throw Einfinint("limitint.cpp : operator %=", gettext("Division by zero"));
471
472 field %= arg.field;
473 return *this;
474 }
475
476 template <class B> limitint<B> & limitint<B>::operator >>= (U_32 bit)
477 {
478 if(bit >= sizeof_field*8)
479 field = 0;
480 else
481 field >>= bit;
482 return *this;
483 }
484
485 template <class B> limitint<B> & limitint<B>::operator >>= (limitint bit)
486 {
487 field >>= bit.field;
488 return *this;
489 }
490
491 template <class B> limitint<B> & limitint<B>::operator <<= (U_32 bit)
492 {
493 if(bit + int_tools_higher_power_of_2(field) >= bytesize*8)
494 throw Elimitint();
495 field <<= bit;
496 return *this;
497 }
498
499 template <class B> limitint<B> & limitint<B>::operator <<= (limitint bit)
500 {
501 if(bit.field + int_tools_higher_power_of_2(field) >= bytesize*8)
502 throw Elimitint();
503 field <<= bit.field;
504 return *this;
505 }
506
507 template <class B> limitint<B> & limitint<B>::operator &= (const limitint & arg)
508 {
509 field &= arg.field;
510 return *this;
511 }
512
513 template <class B> limitint<B> & limitint<B>::operator |= (const limitint & arg)
514 {
515 field |= arg.field;
516 return *this;
517 }
518
519 template <class B> limitint<B> & limitint<B>::operator ^= (const limitint & arg)
520 {
521 field ^= arg.field;
522 return *this;
523 }
524
525 template <class B> U_32 limitint<B>::operator % (U_32 arg) const
526 {
527 return U_32(field % arg);
528 }
529
530 template <class B> template <class T> void limitint<B>::limitint_from(T a)
531 {
532 if(sizeof(a) <= bytesize || a <= (T)(max_value))
533 field = B(a);
534 else
535 throw Elimitint();
536 }
537
538 template <class B> template <class T> T limitint<B>::max_val_of(T x)
539 {
540 x = 0;
541 x = ~x;
542
543 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
544 {
545 x = 1;
546 x = int_tools_rotate_right_one_bit(x);
547 x = ~x;
548 }
549
550 return x;
551 }
552
553 template <class B> template <class T> void limitint<B>::limitint_unstack_to(T &a)
554 {
555
556 // T is supposed to be an unsigned "integer"
557 // (ie.: sizeof returns the width of the storage bit field and no sign bit is present)
558 // Note : static here avoids the recalculation of max_T at each call
559 static const T max_T = max_val_of(a);
560 T step = max_T - a;
561
562 if(field < (B)(step) && (T)(field) < step)
563 {
564 a += field;
565 field = 0;
566 }
567 else
568 {
569 field -= step;
570 a = max_T;
571 }
572 }
573
574 template <class B> limitint<B> limitint<B>::get_storage_size() const
575 {
576 B tmp = field;
577 B ret = 0;
578
579 while(tmp != 0)
580 {
581 tmp >>= 8;
582 ret++;
583 }
584
585 return limitint<B>(ret);
586 }
587
588 template <class B> unsigned char limitint<B>::operator [] (const limitint & position) const
589 {
590 B tmp = field;
591 B index = position.field; // C++ has only class protection, not object protection
592
593 while(index > 0)
594 {
595 tmp >>= 8;
596 index--;
597 }
598
599 return (unsigned char)(tmp & 0xFF);
600 }
601
602 template <class B> void limitint<B>::setup_endian()
603 {
604 if(integers_system_is_big_endian())
605 used_endian = big_endian;
606 else
607 used_endian = little_endian;
608
609 (void)memset(zeroed_field, 0, ZEROED_SIZE);
610 }
611
612
613 template <class B> bool limitint<B>::is_system_big_endian()
614 {
615 if(used_endian == not_initialized)
616 setup_endian();
617
618 switch(used_endian)
619 {
620 case big_endian:
621 return true;
622 case little_endian:
623 return false;
624 case not_initialized:
625 throw SRC_BUG;
626 default:
627 throw SRC_BUG;
628 }
629 }
630
631
635
636 template <class B> limitint<B> operator + (const limitint<B> & a, const limitint<B> & b)
637 {
638 limitint<B> ret = a;
639 ret += b;
640
641 return ret;
642 }
643
644 template <class B> limitint<B> operator - (const limitint<B> & a, const limitint<B> & b)
645 {
646 limitint<B> ret = a;
647 ret -= b;
648
649 return ret;
650 }
651
652 template <class B> limitint<B> operator * (const limitint<B> & a, const limitint<B> & b)
653 {
654 limitint<B> ret = a;
655 ret *= b;
656
657 return ret;
658 }
659
660 template <class B> limitint<B> operator / (const limitint<B> & a, const limitint<B> & b)
661 {
662 limitint<B> ret = a;
663 ret /= b;
664
665 return ret;
666 }
667
668 template <class B> limitint<B> operator % (const limitint<B> & a, const limitint<B> & b)
669 {
670 limitint<B> ret = a;
671 ret %= b;
672
673 return ret;
674 }
675
676 template <class B> limitint<B> operator >> (const limitint<B> & a, U_32 bit)
677 {
678 limitint<B> ret = a;
679 ret >>= bit;
680 return ret;
681 }
682
683 template <class B> limitint<B> operator >> (const limitint<B> & a, const limitint<B> & bit)
684 {
685 limitint<B> ret = a;
686 ret >>= bit;
687 return ret;
688 }
689
690 template <class B> limitint<B> operator << (const limitint<B> & a, U_32 bit)
691 {
692 limitint<B> ret = a;
693 ret <<= bit;
694 return ret;
695 }
696
697 template <class B> limitint<B> operator << (const limitint<B> & a, const limitint<B> & bit)
698 {
699 limitint<B> ret = a;
700 ret <<= bit;
701 return ret;
702 }
703
704 template <class B> limitint<B> operator & (const limitint<B> & a, U_32 bit)
705 {
706 limitint<B> ret = a;
707 ret &= bit;
708 return ret;
709 }
710
711 template <class B> limitint<B> operator & (const limitint<B> & a, const limitint<B> & bit)
712 {
713 limitint<B> ret = a;
714 ret &= bit;
715 return ret;
716 }
717
718 template <class B> limitint<B> operator | (const limitint<B> & a, U_32 bit)
719 {
720 limitint<B> ret = a;
721 ret |= bit;
722 return ret;
723 }
724
725 template <class B> limitint<B> operator | (const limitint<B> & a, const limitint<B> & bit)
726 {
727 limitint<B> ret = a;
728 ret |= bit;
729 return ret;
730 }
731
732 template <class B> limitint<B> operator ^ (const limitint<B> & a, U_32 bit)
733 {
734 limitint<B> ret = a;
735 ret ^= bit;
736 return ret;
737 }
738
739 template <class B> limitint<B> operator ^ (const limitint<B> & a, const limitint<B> & bit)
740 {
741 limitint<B> ret = a;
742 ret ^= bit;
743 return ret;
744 }
745
747
748 } // end of namespace
749
750 #endif
libdar::on_pool
Definition: on_pool.hpp:52
integers.hpp
are defined here basic integer types that tend to be portable
generic_file.hpp
class generic_file is defined here as well as class fichierthe generic_file interface is widely used ...
libdar::integers_system_is_big_endian
bool integers_system_is_big_endian()
returns true if the system is big endian, false else
libdar::operator+=
std::vector< T > operator+=(std::vector< T > &a, const std::vector< T > &b)
template function to add two vectors
Definition: tools.hpp:332
int_tools.hpp
elementary operation for infinint integers
user_interaction.hpp
defines the interaction between libdar and the user.Three classes are defined
libdar::limitint
Definition: limitint.hpp:87
erreurs.hpp
contains all the excetion class thrown by libdar
libdar::compile_time::endian
endian
type used to return the endian nature of the current system
Definition: compile_time_features.hpp:90
libdar::Ebug
exception used to signal a bug. A bug is triggered when reaching some code that should never be reach...
Definition: erreurs.hpp:137
libdar::generic_file
this is the interface class from which all other data transfer classes inherit
Definition: generic_file.hpp:100
on_pool.hpp
this is the base class of object that can be allocated on a memory pool
libdar
libdar namespace encapsulate all libdar symbols
Definition: archive.hpp:47