| Disk ARchive 2.5.10 Full featured and portable backup and archiving tool

- Main Page
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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
85 infinint(generic_file & x);
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
libdar::on_pool
Definition: on_pool.hpp:52
integers.hpp
are defined here basic integer types that tend to be portable
storage.hpp
contains a class that permits arbitrary large data storage
int_tools.hpp
elementary operation for infinint integers
libdar::storage
arbitrary large storage structure
Definition: storage.hpp:57
libdar::Ebug
exception used to signal a bug. A bug is triggered when reaching some code that should never be reach...
Definition: erreurs.hpp:137
libdar::generic_file
this is the interface class from which all other data transfer classes inherit
Definition: generic_file.hpp:100
on_pool.hpp
this is the base class of object that can be allocated on a memory pool
libdar::infinint
the arbitrary large positive integer class
Definition: real_infinint.hpp:59
libdar
libdar namespace encapsulate all libdar symbols
Definition: archive.hpp:47