Disk ARchive  2.5.3
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-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
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  {
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
are defined here basic integer types that tend to be portable
class generic_file is defined here as well as class fichierthe generic_file interface is widely used ...
bool integers_system_is_big_endian()
returns true if the system is big endian, false else
exception used when a limitint overflow is detected, the maximum value of the limitint has been excee...
Definition: erreurs.hpp:166
U_I read(char *a, U_I size)
read data from the generic_file
elementary operation for infinint integers
defines the interaction between libdar and the user.Three classes are defined
exception used when arithmetic error is detected when operating on infinint
Definition: erreurs.hpp:153
contains all the excetion class thrown by libdar
exception used to signal range error
Definition: erreurs.hpp:179
exception used to signal a bug. A bug is triggered when reaching some code that should never be reach...
Definition: erreurs.hpp:137
this is the interface class from which all other data transfer classes inherit
void write(const char *a, U_I size)
write data to the generic_file
this is the base class of object that can be allocated on a memory pool
the arbitrary large positive integer class
libdar namespace encapsulate all libdar symbols
Definition: archive.hpp:47