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