Disk ARchive  2.5.6
Full featured and portable backup and archiving tool
real_infinint.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 
28 
29 #ifndef REAL_INFININT_HPP
30 #define REAL_INFININT_HPP
31 
32 #include "../my_config.h"
33 
34 extern "C"
35 {
36 #if HAVE_SYS_TYPES_H
37 #include <sys/types.h>
38 #endif
39 } // end extern "C"
40 
41 #include <typeinfo>
42 
43 #include "storage.hpp"
44 #include "integers.hpp"
45 #include "int_tools.hpp"
46 #include "on_pool.hpp"
47 
48 #define ZEROED_SIZE 50
49 
50 namespace libdar
51 {
52  class generic_file;
53  class user_interaction;
54 
56 
59  class infinint : public on_pool
60  {
61  public :
62 
63 #if SIZEOF_OFF_T > SIZEOF_TIME_T
64 #if SIZEOF_OFF_T > SIZEOF_SIZE_T
65  infinint(off_t a = 0)
66  { infinint_from(a); };
67 #else
68  infinint(size_t a = 0)
69  { infinint_from(a); };
70 #endif
71 #else
72 #if SIZEOF_TIME_T > SIZEOF_SIZE_T
73  infinint(time_t a = 0)
74  { infinint_from(a); };
75 #else
76  infinint(size_t a = 0)
77  { infinint_from(a); };
78 #endif
79 #endif
80 
81  infinint(const infinint & ref)
82  { copy_from(ref); }
83 
84  // read an infinint from a file
86 
87  ~infinint() throw(Ebug)
88  { detruit(); };
89 
90  const infinint & operator = (const infinint & ref)
91  { detruit(); copy_from(ref); return *this; };
92 
93  void dump(generic_file &x) const; // write byte sequence to file
94  void read(generic_file &f) { detruit(); build_from_file(f); };
95 
96  infinint & operator += (const infinint & ref);
97  infinint & operator -= (const infinint & ref);
98  infinint & operator *= (unsigned char arg);
99  infinint & operator *= (const infinint & ref);
100  template <class T> infinint power(const T & exponent) const;
101  inline infinint & operator /= (const infinint & ref);
102  inline infinint & operator %= (const infinint & ref);
103  infinint & operator &= (const infinint & ref);
104  infinint & operator |= (const infinint & ref);
105  infinint & operator ^= (const infinint & ref);
106  infinint & operator >>= (U_32 bit);
107  infinint & operator >>= (infinint bit);
108  infinint & operator <<= (U_32 bit);
109  infinint & operator <<= (infinint bit);
110  infinint operator ++(int a)
111  { infinint ret = *this; ++(*this); return ret; };
112  infinint operator --(int a)
113  { infinint ret = *this; --(*this); return ret; };
114  infinint & operator ++()
115  { return *this += 1; };
116  infinint & operator --()
117  { return *this -= 1; };
118 
119  U_32 operator % (U_32 arg) const
120  { return modulo(arg); };
121 
122  // increment the argument up to a legal value for its storage type and decrement the object in consequence
123  // note that the initial value of the argument is not ignored !
124  // when the object is null the value of the argument is unchanged
125  template <class T>void unstack(T &v)
126  { infinint_unstack_to(v); }
127 
128  infinint get_storage_size() const { return field->size(); };
129  // it returns number of byte of information necessary to store the integer
130 
131  unsigned char operator [] (const infinint & position) const;
132  // return in little endian order the information byte storing the integer
133 
134  bool is_zero() const;
135 
136  friend bool operator < (const infinint &, const infinint &);
137  friend bool operator == (const infinint &, const infinint &);
138  friend bool operator > (const infinint &, const infinint &);
139  friend bool operator <= (const infinint &, const infinint &);
140  friend bool operator != (const infinint &, const infinint &);
141  friend bool operator >= (const infinint &, const infinint &);
142  friend void euclide(infinint a, const infinint &b, infinint &q, infinint &r);
143 
144  static bool is_system_big_endian();
145 
146  private :
147  static const int TG = 4;
148 
149  enum endian { big_endian, little_endian, not_initialized };
150  typedef unsigned char group[TG];
151 
152  storage *field;
153 
154  bool is_valid() const;
155  void build_from_file(generic_file & x);
156  void reduce(); // put the object in canonical form : no leading byte equal to zero
157  void copy_from(const infinint & ref);
158  void detruit();
159  void make_at_least_as_wider_as(const infinint & ref);
160  template <class T> void infinint_from(T a);
161  template <class T> T max_val_of(T x);
162  template <class T> void infinint_unstack_to(T &a);
163  template <class T> T modulo(T arg) const;
164  signed int difference(const infinint & b) const; // gives the sign of (*this - arg) but only the sign !
165 
167  // static statments
168  //
169  static endian used_endian;
170  static U_8 zeroed_field[ZEROED_SIZE];
171  static void setup_endian();
172  };
173 
174 
175 #define OPERATOR(OP) inline bool operator OP (const infinint &a, const infinint &b) \
176  { \
177  return a.difference(b) OP 0; \
178  }
179 
180  OPERATOR(<)
181  OPERATOR(>)
182  OPERATOR(<=)
183  OPERATOR(>=)
184  OPERATOR(==)
185  OPERATOR(!=)
186 
187  infinint operator + (const infinint &, const infinint &);
188  infinint operator - (const infinint &, const infinint &);
189  infinint operator * (const infinint &, const infinint &);
190  infinint operator * (const infinint &, const unsigned char);
191  infinint operator * (const unsigned char, const infinint &);
192  infinint operator / (const infinint &, const infinint &);
193  infinint operator % (const infinint &, const infinint &);
194  infinint operator & (const infinint & a, const infinint & bit);
195  infinint operator | (const infinint & a, const infinint & bit);
196  infinint operator ^ (const infinint & a, const infinint & bit);
197  infinint operator >> (const infinint & a, U_32 bit);
198  infinint operator >> (const infinint & a, const infinint & bit);
199  infinint operator << (const infinint & a, U_32 bit);
200  infinint operator << (const infinint & a, const infinint & bit);
201  void euclide(infinint a, const infinint &b, infinint &q, infinint &r);
202  template <class T> inline void euclide(T a, T b, T & q, T &r)
203  {
204  q = a/b; r = a%b;
205  }
206 
207  inline infinint & infinint::operator /= (const infinint & ref)
208  {
209  *this = *this / ref;
210  return *this;
211  }
212 
213  inline infinint & infinint::operator %= (const infinint & ref)
214  {
215  *this = *this % ref;
216  return *this;
217  }
218 
219 
223 
224  template <class T> infinint infinint::power(const T & exponent) const
225  {
226  infinint ret = 1;
227  for(T count = 0; count < exponent; ++count)
228  ret *= *this;
229 
230  return ret;
231  }
232 
233  template <class T> T infinint::modulo(T arg) const
234  {
235  infinint tmp = *this % infinint(arg);
236  T ret = 0;
237  unsigned char *debut = (unsigned char *)(&ret);
238  unsigned char *ptr = debut + sizeof(T) - 1;
239  storage::iterator it = tmp.field->rbegin();
240 
241  while(it != tmp.field->rend() && ptr >= debut)
242  {
243  *ptr = *it;
244  --ptr;
245  --it;
246  }
247 
248  // checking for overflow (should never occur, but for sanity, we check it anyway)
249 
250  while(it != tmp.field->rend()) // field may not be reduced (some zeros are leading)
251  {
252  if(*it != 0)
253  throw SRC_BUG; // could not put all the data in the returned value !
254  --it;
255  }
256 
257  if(used_endian == little_endian)
258  int_tools_swap_bytes(debut, sizeof(T));
259 
260  return ret;
261  }
262 
263 
264  template <class T> void infinint::infinint_from(T a)
265  {
266  U_I size = sizeof(a);
267  S_I direction = +1;
268  unsigned char *ptr, *fin;
269 
270  if(used_endian == not_initialized)
271  setup_endian();
272 
273  if(used_endian == little_endian)
274  {
275  direction = -1;
276  ptr = (unsigned char *)(&a) + (size - 1);
277  fin = (unsigned char *)(&a) - 1;
278  }
279  else
280  {
281  direction = +1;
282  ptr = (unsigned char *)(&a);
283  fin = (unsigned char *)(&a) + size;
284  }
285 
286  while(ptr != fin && *ptr == 0)
287  {
288  ptr += direction;
289  --size;
290  }
291 
292  if(size == 0)
293  {
294  size = 1;
295  ptr -= direction;
296  }
297 
298  field = new (std::nothrow) storage(size);
299  if(field != nullptr)
300  {
301  storage::iterator it = field->begin();
302 
303  while(ptr != fin)
304  {
305  *it = *ptr;
306  ++it;
307  ptr += direction;
308  }
309  if(it != field->end())
310  throw SRC_BUG; // size mismatch in this algorithm
311  }
312  else
313  throw Ememory("template infinint::infinint_from");
314  }
315 
316  template <class T> T infinint::max_val_of(T x)
317  {
318  x = 0;
319  x = ~x;
320 
321  if(x <= 0) // T is a signed integer type. Note that it should be "x < 0" but to avoid compiler warning when T is unsigned it does not hurt having "x <= 0" here
322  {
323  x = 1;
324  x = int_tools_rotate_right_one_bit(x);
325  x = ~x;
326  }
327 
328  return x;
329  }
330 
331  template <class T> void infinint::infinint_unstack_to(T &a)
332  {
333  // T is supposed to be an unsigned "integer"
334  // (ie.: sizeof() returns the width of the storage bit field and no sign bit is present)
335  // Note : static here avoids the recalculation of max_T at each call
336  static const T max_T = max_val_of(a);
337  infinint step = max_T - a;
338 
339  if(*this < step)
340  {
341  T transfert = 0;
342  unsigned char *debut = (unsigned char *)&transfert;
343  unsigned char *ptr = debut + sizeof(transfert) - 1;
344  storage::iterator it = field->rbegin();
345 
346  while(ptr >= debut && it != field->rend())
347  {
348  *ptr = *it;
349  --ptr;
350  --it;
351  }
352 
353  if(used_endian == little_endian)
354  int_tools_swap_bytes(debut, sizeof(transfert));
355  a += transfert;
356  *this -= *this;
357  }
358  else
359  {
360  *this -= step;
361  a = max_T;
362  }
363  }
364 
365 } // end of namespace
366 
367 #endif
are defined here basic integer types that tend to be portable
std::ostream & operator<<(std::ostream &ref, const infinint &arg)
specific << operator to use infinint in std::ostream
contains a class that permits arbitrary large data storage
elementary operation for infinint integers
exception used when memory has been exhausted
Definition: erreurs.hpp:111
arbitrary large storage structure
Definition: storage.hpp:57
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
the arbitrary large positive integer class
libdar namespace encapsulate all libdar symbols
Definition: archive.hpp:47