Disk ARchive  2.5.0
Full featured and portable backup and archiving tool
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups
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
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
endian
type used to return the endian nature of the current system