Disk ARchive  2.4.15
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Modules
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 #include <new>
43 
44 #include "storage.hpp"
45 #include "integers.hpp"
46 #include "int_tools.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
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
85  infinint(user_interaction & dialog, S_I fd);
87 
88  ~infinint()
89  { detruit(); };
90 
91  const infinint & operator = (const infinint & ref)
92  { detruit(); copy_from(ref); return *this; };
93 
94  void dump(user_interaction & dialog, int fd) const; // write byte sequence to file
95  void dump(generic_file &x) const; // write byte sequence to file
96  void read(generic_file &f) { detruit(); build_from_file(f); };
97 
98  infinint & operator += (const infinint & ref);
99  infinint & operator -= (const infinint & ref);
100  infinint & operator *= (unsigned char arg);
101  infinint & operator *= (const infinint & ref);
102  template <class T> infinint power(const T & exponent) const;
103  inline infinint & operator /= (const infinint & ref);
104  inline infinint & operator %= (const infinint & ref);
105  infinint & operator &= (const infinint & ref);
106  infinint & operator |= (const infinint & ref);
107  infinint & operator ^= (const infinint & ref);
108  infinint & operator >>= (U_32 bit);
109  infinint & operator >>= (infinint bit);
110  infinint & operator <<= (U_32 bit);
111  infinint & operator <<= (infinint bit);
112  infinint operator ++(int a)
113  { infinint ret = *this; ++(*this); return ret; };
114  infinint operator --(int a)
115  { infinint ret = *this; --(*this); return ret; };
116  infinint & operator ++()
117  { return *this += 1; };
118  infinint & operator --()
119  { return *this -= 1; };
120 
121  U_32 operator % (U_32 arg) const
122  { return modulo(arg); };
123 
124  // increment the argument up to a legal value for its storage type and decrement the object in consequence
125  // note that the initial value of the argument is not ignored !
126  // when the object is null the value of the argument is unchanged
127  template <class T>void unstack(T &v)
128  { infinint_unstack_to(v); }
129 
130  infinint get_storage_size() const { return field->size(); };
131  // it returns number of byte of information necessary to store the integer
132 
133  unsigned char operator [] (const infinint & position) const;
134  // return in big endian order the information byte storing the integer
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 #ifdef LIBDAR_SPECIAL_ALLOC
147  USE_SPECIAL_ALLOC(infinint);
148 #endif
149  private :
150  static const int TG = 4;
151 
152  enum endian { big_endian, little_endian, not_initialized };
153  typedef unsigned char group[TG];
154 
155  storage *field;
156 
157  bool is_valid() const;
158  void build_from_file(generic_file & x);
159  void reduce(); // put the object in canonical form : no leading byte equal to zero
160  void copy_from(const infinint & ref);
161  void detruit();
162  void make_at_least_as_wider_as(const infinint & ref);
163  template <class T> void infinint_from(T a);
164  template <class T> T max_val_of(T x);
165  template <class T> void infinint_unstack_to(T &a);
166  template <class T> T modulo(T arg) const;
167  signed int difference(const infinint & b) const; // gives the sign of (*this - arg) but only the sign !
168 
170  // static statments
171  //
172  static endian used_endian;
173  static U_8 zeroed_field[ZEROED_SIZE];
174  static void setup_endian();
175  };
176 
177 
178 #define OPERATOR(OP) inline bool operator OP (const infinint &a, const infinint &b) \
179  { \
180  return a.difference(b) OP 0; \
181  }
182 
183  OPERATOR(<)
184  OPERATOR(>)
185  OPERATOR(<=)
186  OPERATOR(>=)
187  OPERATOR(==)
188  OPERATOR(!=)
189 
190  infinint operator + (const infinint &, const infinint &);
191  infinint operator - (const infinint &, const infinint &);
192  infinint operator * (const infinint &, const infinint &);
193  infinint operator * (const infinint &, const unsigned char);
194  infinint operator * (const unsigned char, const infinint &);
195  infinint operator / (const infinint &, const infinint &);
196  infinint operator % (const infinint &, const infinint &);
197  infinint operator & (const infinint & a, const infinint & bit);
198  infinint operator | (const infinint & a, const infinint & bit);
199  infinint operator ^ (const infinint & a, const infinint & bit);
200  infinint operator >> (const infinint & a, U_32 bit);
201  infinint operator >> (const infinint & a, const infinint & bit);
202  infinint operator << (const infinint & a, U_32 bit);
203  infinint operator << (const infinint & a, const infinint & bit);
204  void euclide(infinint a, const infinint &b, infinint &q, infinint &r);
205  template <class T> inline void euclide(T a, T b, T & q, T &r)
206  {
207  q = a/b; r = a%b;
208  }
209 
210  inline infinint & infinint::operator /= (const infinint & ref)
211  {
212  *this = *this / ref;
213  return *this;
214  }
215 
216  inline infinint & infinint::operator %= (const infinint & ref)
217  {
218  *this = *this % ref;
219  return *this;
220  }
221 
222 
226 
227  template <class T> infinint infinint::power(const T & exponent) const
228  {
229  infinint ret = 1;
230  for(T count = 0; count < exponent; ++count)
231  ret *= *this;
232 
233  return ret;
234  }
235 
236  template <class T> T infinint::modulo(T arg) const
237  {
238  infinint tmp = *this % infinint(arg);
239  T ret = 0;
240  unsigned char *debut = (unsigned char *)(&ret);
241  unsigned char *ptr = debut + sizeof(T) - 1;
242  storage::iterator it = tmp.field->rbegin();
243 
244  while(it != tmp.field->rend() && ptr >= debut)
245  {
246  *ptr = *it;
247  --ptr;
248  --it;
249  }
250 
251  // checking for overflow (should never occur, but for sanity, we check it anyway)
252 
253  while(it != tmp.field->rend()) // field may not be reduced (some zeros are leading)
254  {
255  if(*it != 0)
256  throw SRC_BUG; // could not put all the data in the returned value !
257  --it;
258  }
259 
260  if(used_endian == little_endian)
261  int_tools_swap_bytes(debut, sizeof(T));
262 
263  return ret;
264  }
265 
266 
267  template <class T> void infinint::infinint_from(T a)
268  {
269  U_I size = sizeof(a);
270  S_I direction = +1;
271  unsigned char *ptr, *fin;
272 
273  if(used_endian == not_initialized)
274  setup_endian();
275 
276  if(used_endian == little_endian)
277  {
278  direction = -1;
279  ptr = (unsigned char *)(&a) + (size - 1);
280  fin = (unsigned char *)(&a) - 1;
281  }
282  else
283  {
284  direction = +1;
285  ptr = (unsigned char *)(&a);
286  fin = (unsigned char *)(&a) + size;
287  }
288 
289  while(ptr != fin && *ptr == 0)
290  {
291  ptr += direction;
292  --size;
293  }
294 
295  if(size == 0)
296  {
297  size = 1;
298  ptr -= direction;
299  }
300 
301  field = new (std::nothrow) storage(size);
302  if(field != NULL)
303  {
304  storage::iterator it = field->begin();
305 
306  while(ptr != fin)
307  {
308  *it = *ptr;
309  ++it;
310  ptr += direction;
311  }
312  if(it != field->end())
313  throw SRC_BUG; // size mismatch in this algorithm
314  }
315  else
316  throw Ememory("template infinint::infinint_from");
317  }
318 
319  template <class T> T infinint::max_val_of(T x)
320  {
321  x = 0;
322  x = ~x;
323 
324  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
325  {
326  x = 1;
327  x = int_tools_rotate_right_one_bit(x);
328  x = ~x;
329  }
330 
331  return x;
332  }
333 
334  template <class T> void infinint::infinint_unstack_to(T &a)
335  {
336  // T is supposed to be an unsigned "integer"
337  // (ie.: sizeof() returns the width of the storage bit field and no sign bit is present)
338  // Note : static here avoids the recalculation of max_T at each call
339  static const T max_T = max_val_of(a);
340  infinint step = max_T - a;
341 
342  if(*this < step)
343  {
344  T transfert = 0;
345  unsigned char *debut = (unsigned char *)&transfert;
346  unsigned char *ptr = debut + sizeof(transfert) - 1;
347  storage::iterator it = field->rbegin();
348 
349  while(ptr >= debut && it != field->rend())
350  {
351  *ptr = *it;
352  --ptr;
353  --it;
354  }
355 
356  if(used_endian == little_endian)
357  int_tools_swap_bytes(debut, sizeof(transfert));
358  a += transfert;
359  *this -= *this;
360  }
361  else
362  {
363  *this -= step;
364  a = max_T;
365  }
366  }
367 
368 } // end of namespace
369 
370 #endif
are defined here basic integer types that tend to be portable
the deleted file entry
Definition: catalogue.hpp:906
This is a pure virtual class that is used by libdar when interaction with the user is required...
contains a class that permits arbitrary large data storage
elementary operation for infinint integers
arbitrary large storage structure
Definition: storage.hpp:57
this is the interface class from which all other data transfer classes inherit
the arbitrary large positive integer class
libdar namespace encapsulate all libdar symbols
Definition: archive.hpp:43