Disk ARchive  2.4.10
 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 "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