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