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
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  {
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
std::vector< T > operator+=(std::vector< T > &a, const std::vector< T > &b)
template function to add two vectors
Definition: tools.hpp:332
elementary operation for infinint integers
defines the interaction between libdar and the user.Three classes are defined
contains all the excetion class thrown by libdar
endian
type used to return the endian nature of the current system
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
this is the base class of object that can be allocated on a memory pool
libdar namespace encapsulate all libdar symbols
Definition: archive.hpp:47