Disk ARchive  2.4.2
 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 2011/02/17 21:45:22 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  { E_BEGIN infinint_from(a); E_END("infinint::infinint", "off_t") };
68 #else
69  infinint(size_t a = 0)
70  { E_BEGIN infinint_from(a); E_END("infinint::infinint", "size_t") };
71 #endif
72 #else
73 #if SIZEOF_TIME_T > SIZEOF_SIZE_T
74  infinint(time_t a = 0)
75  { E_BEGIN infinint_from(a); E_END("infinint::infinint", "time_t") };
76 #else
77  infinint(size_t a = 0)
78  { E_BEGIN infinint_from(a); E_END("infinint::infinint", "size_t") };
79 #endif
80 #endif
81 
82  infinint(const infinint & ref)
83  { E_BEGIN; copy_from(ref); E_END("infinint::infinint", "const infinint &"); }
84 
85  // read an infinint from a file
86  infinint(user_interaction & dialog, S_I fd);
88 
89  ~infinint()
90  { E_BEGIN detruit(); E_END("infinint::~infinint","") };
91 
92  const infinint & operator = (const infinint & ref)
93  { E_BEGIN detruit(); copy_from(ref); return *this; E_END("infinint::operator =","") };
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  { E_BEGIN infinint ret = *this; ++(*this); return ret; E_END("infinint::operator ++", "int") };
115  infinint operator --(int a)
116  { E_BEGIN infinint ret = *this; --(*this); return ret; E_END("infinint::operator --", "int") };
117  infinint & operator ++()
118  { E_BEGIN return *this += 1; E_END("infinint::operator ++", "()") };
119  infinint & operator --()
120  { E_BEGIN return *this -= 1; E_END("infinint::operator --", "()") };
121 
122  U_32 operator % (U_32 arg) const
123  { E_BEGIN return modulo(arg); E_END("infinint::operator %","") };
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  { E_BEGIN infinint_unstack_to(v); E_END("infinint::unstack", typeid(v).name()) }
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  private :
148  static const int TG = 4;
149 
150  enum endian { big_endian, little_endian, not_initialized };
151  typedef unsigned char group[TG];
152 
153  storage *field;
154 
155  bool is_valid() const;
156  void build_from_file(generic_file & x);
157  void reduce(); // put the object in canonical form : no leading byte equal to zero
158  void copy_from(const infinint & ref);
159  void detruit();
160  void make_at_least_as_wider_as(const infinint & ref);
161  template <class T> void infinint_from(T a);
162  template <class T> T max_val_of(T x);
163  template <class T> void infinint_unstack_to(T &a);
164  template <class T> T modulo(T arg) const;
165  signed int difference(const infinint & b) const; // gives the sign of (*this - arg) but only the sign !
166 
168  // static statments
169  //
170  static endian used_endian;
171  static U_8 zeroed_field[ZEROED_SIZE];
172  static void setup_endian();
173  };
174 
175 
176 #define OPERATOR(OP) inline bool operator OP (const infinint &a, const infinint &b) \
177  { \
178  E_BEGIN \
179  return a.difference(b) OP 0; \
180  E_END("operator OP", "infinint, infinint") \
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  E_BEGIN
208  q = a/b; r = a%b;
209  E_END("euclide", "")
210  }
211 
212  inline infinint & infinint::operator /= (const infinint & ref)
213  {
214  E_BEGIN
215  *this = *this / ref;
216  return *this;
217  E_END("infinint::operator /=", "")
218  }
219 
220  inline infinint & infinint::operator %= (const infinint & ref)
221  {
222  E_BEGIN
223  *this = *this % ref;
224  return *this;
225  E_END("infinint::operator %=", "")
226  }
227 
228 
232 
233  template <class T> infinint infinint::power(const T & exponent) const
234  {
235  infinint ret = 1;
236  for(T count = 0; count < exponent; ++count)
237  ret *= *this;
238 
239  return ret;
240  }
241 
242  template <class T> T infinint::modulo(T arg) const
243  {
244  E_BEGIN
245  infinint tmp = *this % infinint(arg);
246  T ret = 0;
247  unsigned char *debut = (unsigned char *)(&ret);
248  unsigned char *ptr = debut + sizeof(T) - 1;
249  storage::iterator it = tmp.field->rbegin();
250 
251  while(it != tmp.field->rend() && ptr >= debut)
252  {
253  *ptr = *it;
254  --ptr;
255  --it;
256  }
257 
258  // checking for overflow (should never occur, but for sanity, we check it anyway)
259 
260  while(it != tmp.field->rend()) // field may not be reduced (some zeros are leading)
261  {
262  if(*it != 0)
263  throw SRC_BUG; // could not put all the data in the returned value !
264  --it;
265  }
266 
267  if(used_endian == little_endian)
268  int_tools_swap_bytes(debut, sizeof(T));
269 
270  return ret;
271  E_END("infinint::modulo", "")
272  }
273 
274 
275  template <class T> void infinint::infinint_from(T a)
276  {
277  E_BEGIN
278  U_I size = sizeof(a);
279  S_I direction = +1;
280  unsigned char *ptr, *fin;
281 
282  if(used_endian == not_initialized)
283  setup_endian();
284 
285  if(used_endian == little_endian)
286  {
287  direction = -1;
288  ptr = (unsigned char *)(&a) + (size - 1);
289  fin = (unsigned char *)(&a) - 1;
290  }
291  else
292  {
293  direction = +1;
294  ptr = (unsigned char *)(&a);
295  fin = (unsigned char *)(&a) + size;
296  }
297 
298  while(ptr != fin && *ptr == 0)
299  {
300  ptr += direction;
301  --size;
302  }
303 
304  if(size == 0)
305  {
306  size = 1;
307  ptr -= direction;
308  }
309 
310  field = new storage(size);
311  if(field != NULL)
312  {
313  storage::iterator it = field->begin();
314 
315  while(ptr != fin)
316  {
317  *it = *ptr;
318  ++it;
319  ptr += direction;
320  }
321  if(it != field->end())
322  throw SRC_BUG; // size mismatch in this algorithm
323  }
324  else
325  throw Ememory("template infinint::infinint_from");
326 
327  E_END("infinint::infinint_from", "")
328  }
329 
330  template <class T> T infinint::max_val_of(T x)
331  {
332  x = 0;
333  x = ~x;
334 
335  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
336  {
337  x = 1;
338  x = int_tools_rotate_right_one_bit(x);
339  x = ~x;
340  }
341 
342  return x;
343  }
344 
345  template <class T> void infinint::infinint_unstack_to(T &a)
346  {
347  E_BEGIN;
348  // T is supposed to be an unsigned "integer"
349  // (ie.: sizeof() returns the width of the storage bit field and no sign bit is present)
350  // Note : static here avoids the recalculation of max_T at each call
351  static const T max_T = max_val_of(a);
352  infinint step = max_T - a;
353 
354  if(*this < step)
355  {
356  T transfert = 0;
357  unsigned char *debut = (unsigned char *)&transfert;
358  unsigned char *ptr = debut + sizeof(transfert) - 1;
359  storage::iterator it = field->rbegin();
360 
361  while(ptr >= debut && it != field->rend())
362  {
363  *ptr = *it;
364  --ptr;
365  --it;
366  }
367 
368  if(used_endian == little_endian)
369  int_tools_swap_bytes(debut, sizeof(transfert));
370  a += transfert;
371  *this -= *this;
372  }
373  else
374  {
375  *this -= step;
376  a = max_T;
377  }
378  E_END("infinint::infinint_unstack_to", "")
379  }
380 
381 } // end of namespace
382 
383 #endif