Disk ARchive  2.5.1
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 
167  private :
168  static const int TG = 4;
169  static const U_32 sizeof_field = sizeof(B); // number of bytes
170 
171  enum endian { big_endian, little_endian, not_initialized };
172  typedef unsigned char group[TG];
173 
174  B field;
175 
176  void build_from_file(generic_file & x);
177  template <class T> void limitint_from(T a);
178  template <class T> T max_val_of(T x);
179  template <class T> void limitint_unstack_to(T &a);
180 
182  // static statments
183  //
184  static endian used_endian;
185  static const U_I bytesize = sizeof(B);
186  static const B max_value = ~B(0) > 0 ? ~B(0) : ~(B(1) << (bytesize*8 - 1));
187  static U_8 zeroed_field[ZEROED_SIZE];
188 
189  static void setup_endian();
190  };
191 
192  template <class B> U_8 limitint<B>::zeroed_field[ZEROED_SIZE];
193 
194  template <class B> limitint<B> operator + (const limitint<B> &, const limitint<B> &);
195  template <class B> inline limitint<B> operator + (const limitint<B> & a, U_I b)
196  { return a + limitint<B>(b); }
197  template <class B> limitint<B> operator - (const limitint<B> &, const limitint<B> &);
198  template <class B> inline limitint<B> operator - (const limitint<B> & a, U_I b)
199  { return a - limitint<B>(b); }
200  template <class B> limitint<B> operator * (const limitint<B> &, const limitint<B> &);
201  template <class B> inline limitint<B> operator * (const limitint<B> & a, U_I b)
202  { return a * limitint<B>(b); }
203  template <class B> limitint<B> operator / (const limitint<B> &, const limitint<B> &);
204  template <class B> limitint<B> operator / (const limitint<B> & a, U_I b)
205  { return a / limitint<B>(b); }
206  template <class B> limitint<B> operator % (const limitint<B> &, const limitint<B> &);
207  template <class B> limitint<B> operator >> (const limitint<B> & a, U_32 bit);
208  template <class B> limitint<B> operator >> (const limitint<B> & a, const limitint<B> & bit);
209  template <class B> limitint<B> operator << (const limitint<B> & a, U_32 bit);
210  template <class B> limitint<B> operator << (const limitint<B> & a, const limitint<B> & bit);
211  template <class B> limitint<B> operator & (const limitint<B> & a, U_32 bit);
212  template <class B> limitint<B> operator & (const limitint<B> & a, const limitint<B> & bit);
213  template <class B> limitint<B> operator | (const limitint<B> & a, U_32 bit);
214  template <class B> limitint<B> operator | (const limitint<B> & a, const limitint<B> & bit);
215  template <class B> limitint<B> operator ^ (const limitint<B> & a, U_32 bit);
216  template <class B> limitint<B> operator ^ (const limitint<B> & a, const limitint<B> & bit);
217 
218  template <class T> inline void euclide(T a, T b, T & q, T &r)
219  {
220 
221  q = a/b; r = a%b;
222  }
223 
224  template <class B> inline void euclide(limitint<B> a, U_I b, limitint<B> & q, limitint<B> &r)
225  {
226  euclide(a, limitint<B>(b), q, r);
227  }
228 
229 #ifndef INFININT_BASE_TYPE
230 #error INFININT_BASE_TYPE not defined cannot instantiate template
231 #else
232  typedef limitint<INFININT_BASE_TYPE> infinint;
233 #endif
234 } // end of namespace
238 
239 #include "generic_file.hpp"
240 #include "user_interaction.hpp"
241 
242 namespace libdar
243 {
244 
245  template <class B> typename limitint<B>::endian limitint<B>::used_endian = not_initialized;
246 
247 
248  template <class B> limitint<B>::limitint(generic_file & x)
249  {
250  build_from_file(x);
251  }
252 
253 
254  template <class B> void limitint<B>::build_from_file(generic_file & x)
255  {
256  unsigned char a;
257  bool fin = false;
258  limitint<B> skip = 0;
259  char *ptr = (char *)&field;
260  S_I lu;
261  int_tools_bitfield bf;
262 
263  while(!fin)
264  {
265  lu = x.read((char *)&a, 1);
266 
267  if(lu <= 0)
268  throw Erange("limitint::build_from_file(generic_file)", gettext("Reached end of file before all data could be read"));
269 
270  if(a == 0)
271  ++skip;
272  else // end of size field
273  {
274  // computing the size to read
275  U_I pos = 0;
276 
277  int_tools_expand_byte(a, bf);
278  for(S_I i = 0; i < 8; ++i)
279  pos += bf[i];
280  if(pos != 1)
281  throw Erange("limitint::build_from_file(generic_file)", gettext("Badly formed \"infinint\" or not supported format")); // more than 1 bit is set to 1
282 
283  pos = 0;
284  while(bf[pos] == 0)
285  ++pos;
286  pos += 1; // bf starts at zero, but bit zero means 1 TG of length
287 
288  skip *= 8;
289  skip += pos;
290  skip *= TG;
291 
292  if(skip.field > bytesize)
293  throw Elimitint();
294 
295  field = 0; // important to also clear "unread" bytes by this call
296  lu = x.read(ptr, skip.field);
297 
298  if(used_endian == not_initialized)
299  setup_endian();
300  if(used_endian == little_endian)
301  int_tools_swap_bytes((unsigned char *)ptr, skip.field);
302  else
303  field >>= (bytesize - skip.field)*8;
304  fin = true;
305  }
306  }
307  }
308 
309 
310  template <class B> void limitint<B>::dump(generic_file & x) const
311  {
312  B width = bytesize;
313  B pos;
314  unsigned char last_width;
315  B justification;
316  S_I direction = +1;
317  unsigned char *ptr, *fin;
318 
319 
320  if(used_endian == not_initialized)
321  setup_endian();
322 
323  if(used_endian == little_endian)
324  {
325  direction = -1;
326  ptr = (unsigned char *)(&field) + (bytesize - 1);
327  fin = (unsigned char *)(&field) - 1;
328  }
329  else
330  {
331  direction = +1;
332  ptr = (unsigned char *)(&field);
333  fin = (unsigned char *)(&field) + bytesize;
334  }
335 
336  while(ptr != fin && *ptr == 0)
337  {
338  ptr += direction;
339  --width;
340  }
341  if(width == 0)
342  width = 1; // minimum size of information is 1 byte
343 
344  // "width" is the informational field size in byte
345  // TG is the width in TG, thus the number of bit that must have
346  // the preamble
347  euclide(width, (const B)(TG), width, justification);
348  if(justification != 0)
349  // in case we need to add some bytes to have a width multiple of TG
350  ++width; // we need then one more group to have a width multiple of TG
351 
352  euclide(width, (const B)(8), width, pos);
353  if(pos == 0)
354  {
355  width--; // division is exact, only last bit of the preambule is set
356  last_width = 0x80 >> 7;
357  // as we add the last byte separately width gets shorter by 1 byte
358  }
359  else // division non exact, the last_width (last byte), make the rounding
360  {
361  U_16 pos_s = (U_16)(0xFFFF & pos);
362  last_width = 0x80 >> (pos_s - 1);
363  }
364 
365  // now we write the preamble except the last byte. All these are zeros.
366 
367  while(width != 0)
368  if(width > ZEROED_SIZE)
369  {
370  x.write((char *)zeroed_field, ZEROED_SIZE);
371  width -= ZEROED_SIZE;
372  }
373  else
374  {
375  x.write((char *)zeroed_field, width);
376  width = 0;
377  }
378 
379  // now we write the last byte of the preambule, which as only one bit set
380 
381  x.write((char *)&last_width, 1);
382 
383  // we need now to write some justification byte to have an informational field multiple of TG
384 
385  if(justification != 0)
386  {
387  justification = TG - justification;
388  if(justification > ZEROED_SIZE)
389  throw SRC_BUG;
390  else
391  x.write((char *)zeroed_field, justification);
392  }
393 
394  // now we continue dumping the informational bytes:
395  if(ptr == fin) // field is equal to zero
396  x.write((char *)zeroed_field, 1);
397  else // we have some bytes to write down
398  while(ptr != fin)
399  {
400  x.write((char *)ptr, 1);
401  ptr += direction;
402  }
403  }
404 
405  template<class B> limitint<B> & limitint<B>::operator += (const limitint & arg)
406  {
407  B res = field + arg.field;
408  if(res < field || res < arg.field)
409  throw Elimitint();
410  else
411  field = res;
412 
413  return *this;
414  }
415 
416  template <class B> limitint<B> & limitint<B>::operator -= (const limitint & arg)
417  {
418  if(field < arg.field)
419  throw Erange("limitint::operator", gettext("Subtracting an \"infinint\" greater than the first, \"infinint\" cannot be negative"));
420 
421  // now processing the operation
422 
423  field -= arg.field;
424  return *this;
425  }
426 
427 
428  template <class B> limitint<B> & limitint<B>::operator *= (const limitint & arg)
429  {
430  static const B max_power = bytesize*8 - 1;
431 
432  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
433  if(total > max_power) // this is a bit too much restrictive, but unless remaking bit by bit, the operation,
434  // I don't see how to simply (and fast) know the result has not overflowed.
435  // of course, it would be fast and easy to access the CPU flag register to check for overflow,
436  // but that would not be portable, and unfortunately I haven't found any standart C++ expression that
437  // could transparently access to it.
438  throw Elimitint();
439 
440  total = field*arg.field;
441  if(field != 0 && arg.field != 0)
442  if(total < field || total < arg.field)
443  throw Elimitint();
444  field = total;
445  return *this;
446  }
447 
448  template <class B> template<class T> limitint<B> limitint<B>::power(const T & exponent) const
449  {
450  limitint ret = 1;
451  for(T count = 0; count < exponent; ++count)
452  ret *= *this;
453 
454  return ret;
455  }
456 
457  template <class B> limitint<B> & limitint<B>::operator /= (const limitint & arg)
458  {
459  if(arg == 0)
460  throw Einfinint("limitint.cpp : operator /=", gettext("Division by zero"));
461 
462  field /= arg.field;
463  return *this;
464  }
465 
466  template <class B> limitint<B> & limitint<B>::operator %= (const limitint & arg)
467  {
468  if(arg == 0)
469  throw Einfinint("limitint.cpp : operator %=", gettext("Division by zero"));
470 
471  field %= arg.field;
472  return *this;
473  }
474 
475  template <class B> limitint<B> & limitint<B>::operator >>= (U_32 bit)
476  {
477  if(bit >= sizeof_field*8)
478  field = 0;
479  else
480  field >>= bit;
481  return *this;
482  }
483 
484  template <class B> limitint<B> & limitint<B>::operator >>= (limitint bit)
485  {
486  field >>= bit.field;
487  return *this;
488  }
489 
490  template <class B> limitint<B> & limitint<B>::operator <<= (U_32 bit)
491  {
492  if(bit + int_tools_higher_power_of_2(field) >= bytesize*8)
493  throw Elimitint();
494  field <<= bit;
495  return *this;
496  }
497 
498  template <class B> limitint<B> & limitint<B>::operator <<= (limitint bit)
499  {
500  if(bit.field + int_tools_higher_power_of_2(field) >= bytesize*8)
501  throw Elimitint();
502  field <<= bit.field;
503  return *this;
504  }
505 
506  template <class B> limitint<B> & limitint<B>::operator &= (const limitint & arg)
507  {
508  field &= arg.field;
509  return *this;
510  }
511 
512  template <class B> limitint<B> & limitint<B>::operator |= (const limitint & arg)
513  {
514  field |= arg.field;
515  return *this;
516  }
517 
518  template <class B> limitint<B> & limitint<B>::operator ^= (const limitint & arg)
519  {
520  field ^= arg.field;
521  return *this;
522  }
523 
524  template <class B> U_32 limitint<B>::operator % (U_32 arg) const
525  {
526  return U_32(field % arg);
527  }
528 
529  template <class B> template <class T> void limitint<B>::limitint_from(T a)
530  {
531  if(sizeof(a) <= bytesize || a <= (T)(max_value))
532  field = B(a);
533  else
534  throw Elimitint();
535  }
536 
537  template <class B> template <class T> T limitint<B>::max_val_of(T x)
538  {
539  x = 0;
540  x = ~x;
541 
542  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
543  {
544  x = 1;
545  x = int_tools_rotate_right_one_bit(x);
546  x = ~x;
547  }
548 
549  return x;
550  }
551 
552  template <class B> template <class T> void limitint<B>::limitint_unstack_to(T &a)
553  {
554 
555  // T is supposed to be an unsigned "integer"
556  // (ie.: sizeof returns the width of the storage bit field and no sign bit is present)
557  // Note : static here avoids the recalculation of max_T at each call
558  static const T max_T = max_val_of(a);
559  T step = max_T - a;
560 
561  if(field < (B)(step) && (T)(field) < step)
562  {
563  a += field;
564  field = 0;
565  }
566  else
567  {
568  field -= step;
569  a = max_T;
570  }
571  }
572 
573  template <class B> limitint<B> limitint<B>::get_storage_size() const
574  {
575  B tmp = field;
576  B ret = 0;
577 
578  while(tmp != 0)
579  {
580  tmp >>= 8;
581  ret++;
582  }
583 
584  return limitint<B>(ret);
585  }
586 
587  template <class B> unsigned char limitint<B>::operator [] (const limitint & position) const
588  {
589  B tmp = field;
590  B index = position.field; // C++ has only class protection, not object protection
591 
592  while(index > 0)
593  {
594  tmp >>= 8;
595  index--;
596  }
597 
598  return (unsigned char)(tmp & 0xFF);
599  }
600 
601  template <class B> void limitint<B>::setup_endian()
602  {
604  used_endian = big_endian;
605  else
606  used_endian = little_endian;
607 
608  (void)memset(zeroed_field, 0, ZEROED_SIZE);
609  }
610 
611 
612  template <class B> bool limitint<B>::is_system_big_endian()
613  {
614  if(used_endian == not_initialized)
615  setup_endian();
616 
617  switch(used_endian)
618  {
619  case big_endian:
620  return true;
621  case little_endian:
622  return false;
623  case not_initialized:
624  throw SRC_BUG;
625  default:
626  throw SRC_BUG;
627  }
628  }
629 
630 
634 
635  template <class B> limitint<B> operator + (const limitint<B> & a, const limitint<B> & b)
636  {
637  limitint<B> ret = a;
638  ret += b;
639 
640  return ret;
641  }
642 
643  template <class B> limitint<B> operator - (const limitint<B> & a, const limitint<B> & b)
644  {
645  limitint<B> ret = a;
646  ret -= b;
647 
648  return ret;
649  }
650 
651  template <class B> limitint<B> operator * (const limitint<B> & a, const limitint<B> & b)
652  {
653  limitint<B> ret = a;
654  ret *= b;
655 
656  return ret;
657  }
658 
659  template <class B> limitint<B> operator / (const limitint<B> & a, const limitint<B> & b)
660  {
661  limitint<B> ret = a;
662  ret /= b;
663 
664  return ret;
665  }
666 
667  template <class B> limitint<B> operator % (const limitint<B> & a, const limitint<B> & b)
668  {
669  limitint<B> ret = a;
670  ret %= b;
671 
672  return ret;
673  }
674 
675  template <class B> limitint<B> operator >> (const limitint<B> & a, U_32 bit)
676  {
677  limitint<B> ret = a;
678  ret >>= bit;
679  return ret;
680  }
681 
682  template <class B> limitint<B> operator >> (const limitint<B> & a, const limitint<B> & bit)
683  {
684  limitint<B> ret = a;
685  ret >>= bit;
686  return ret;
687  }
688 
689  template <class B> limitint<B> operator << (const limitint<B> & a, U_32 bit)
690  {
691  limitint<B> ret = a;
692  ret <<= bit;
693  return ret;
694  }
695 
696  template <class B> limitint<B> operator << (const limitint<B> & a, const limitint<B> & bit)
697  {
698  limitint<B> ret = a;
699  ret <<= bit;
700  return ret;
701  }
702 
703  template <class B> limitint<B> operator & (const limitint<B> & a, U_32 bit)
704  {
705  limitint<B> ret = a;
706  ret &= bit;
707  return ret;
708  }
709 
710  template <class B> limitint<B> operator & (const limitint<B> & a, const limitint<B> & bit)
711  {
712  limitint<B> ret = a;
713  ret &= bit;
714  return ret;
715  }
716 
717  template <class B> limitint<B> operator | (const limitint<B> & a, U_32 bit)
718  {
719  limitint<B> ret = a;
720  ret |= bit;
721  return ret;
722  }
723 
724  template <class B> limitint<B> operator | (const limitint<B> & a, const limitint<B> & bit)
725  {
726  limitint<B> ret = a;
727  ret |= bit;
728  return ret;
729  }
730 
731  template <class B> limitint<B> operator ^ (const limitint<B> & a, U_32 bit)
732  {
733  limitint<B> ret = a;
734  ret ^= bit;
735  return ret;
736  }
737 
738  template <class B> limitint<B> operator ^ (const limitint<B> & a, const limitint<B> & bit)
739  {
740  limitint<B> ret = a;
741  ret ^= bit;
742  return ret;
743  }
744 
746 
747 } // end of namespace
748 
749 #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