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