| Disk ARchive 2.6.11 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-2020 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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 "integers.hpp"
44 #include "int_tools.hpp"
45 #include "proto_generic_file.hpp"
46 #include "storage.hpp"
47
48 #define ZEROED_SIZE 50
49
50 namespace libdar
51 {
54
56
61 class infinint
62 {
63 public :
64
65 #if SIZEOF_OFF_T > SIZEOF_TIME_T
66 #if SIZEOF_OFF_T > SIZEOF_SIZE_T
67 infinint(off_t a = 0) { infinint_from(a); };
68 #else
69 infinint(size_t a = 0) { infinint_from(a); };
70 #endif
71 #else
72 #if SIZEOF_TIME_T > SIZEOF_SIZE_T
73 infinint(time_t a = 0) { infinint_from(a); };
74 #else
75 infinint(size_t a = 0) { infinint_from(a); };
76 #endif
77 #endif
78 infinint(proto_generic_file & x);
80
81 infinint(const infinint & ref) { copy_from(ref); }
82 infinint(infinint && ref) noexcept { field = nullptr; move_from(std::move(ref)); };
83
84 infinint & operator = (const infinint & ref) { detruit(); copy_from(ref); return *this; };
85 infinint & operator = (infinint && ref) noexcept { move_from(std::move(ref)); return *this; }
86
87 ~infinint() { detruit(); };
88
89 void dump(proto_generic_file &x) const; // write byte sequence to file
90 void read(proto_generic_file &f) { detruit(); build_from_file(f); };
91
92 infinint & operator += (const infinint & ref);
93 infinint & operator -= (const infinint & ref);
94 infinint & operator *= (unsigned char arg);
95 infinint & operator *= (const infinint & ref);
96 template <class T> infinint power(const T & exponent) const;
97 inline infinint & operator /= (const infinint & ref);
98 inline infinint & operator %= (const infinint & ref);
99 infinint & operator &= (const infinint & ref);
100 infinint & operator |= (const infinint & ref);
101 infinint & operator ^= (const infinint & ref);
102 infinint & operator >>= (U_32 bit);
103 infinint & operator >>= (infinint bit);
104 infinint & operator <<= (U_32 bit);
105 infinint & operator <<= (infinint bit);
106 infinint operator ++(int a)
107 { infinint ret = *this; ++(*this); return ret; };
108 infinint operator --(int a)
109 { infinint ret = *this; --(*this); return ret; };
110 infinint & operator ++()
111 { return *this += 1; };
112 infinint & operator --()
113 { return *this -= 1; };
114
115 U_32 operator % (U_32 arg) const
116 { return modulo(arg); };
117
119
124 template <class T>void unstack(T &v)
125 { infinint_unstack_to(v); }
126
128 infinint get_storage_size() const noexcept { return field->size(); };
129
131 unsigned char operator [] (const infinint & position) const;
132
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 constexpr int TG = 4;
148
149 enum endian { big_endian, little_endian, not_initialized };
150 using group = unsigned char[TG];
151
152 storage *field;
153
154 bool is_valid() const noexcept;
155 void build_from_file(proto_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 move_from(infinint && ref) noexcept { std::swap(field, ref.field); };
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 return a.difference(b) OP 0; \
179 }
180
181 OPERATOR(<)
182 OPERATOR(>)
183 OPERATOR(<=)
184 OPERATOR(>=)
185 OPERATOR(==)
186 OPERATOR(!=)
187
188 infinint operator + (const infinint &, const infinint &);
189 infinint operator - (const infinint &, const infinint &);
190 infinint operator * (const infinint &, const infinint &);
191 infinint operator * (const infinint &, const unsigned char);
192 infinint operator * (const unsigned char, const infinint &);
193 infinint operator / (const infinint &, const infinint &);
194 infinint operator % (const infinint &, const infinint &);
195 infinint operator & (const infinint & a, const infinint & bit);
196 infinint operator | (const infinint & a, const infinint & bit);
197 infinint operator ^ (const infinint & a, const infinint & bit);
198 infinint operator >> (const infinint & a, U_32 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 void euclide(infinint a, const infinint &b, infinint &q, infinint &r);
203 template <class T> inline void euclide(T a, T b, T & q, T &r)
204 {
205 q = a/b; r = a%b;
206 }
207
208 inline infinint & infinint::operator /= (const infinint & ref)
209 {
210 *this = *this / ref;
211 return *this;
212 }
213
214 inline infinint & infinint::operator %= (const infinint & ref)
215 {
216 *this = *this % ref;
217 return *this;
218 }
219
220
224
225 template <class T> infinint infinint::power(const T & exponent) const
226 {
227 infinint ret = 1;
228 for(T count = 0; count < exponent; ++count)
229 ret *= *this;
230
231 return ret;
232 }
233
234 template <class T> T infinint::modulo(T arg) const
235 {
236 infinint tmp = *this % infinint(arg);
237 T ret = 0;
238 unsigned char *debut = (unsigned char *)(&ret);
239 unsigned char *ptr = debut + sizeof(T) - 1;
240 storage::iterator it = tmp.field->rbegin();
241
242 while(it != tmp.field->rend() && ptr >= debut)
243 {
244 *ptr = *it;
245 --ptr;
246 --it;
247 }
248
249 // checking for overflow (should never occur, but for sanity, we check it anyway)
250
251 while(it != tmp.field->rend()) // field may not be reduced (some zeros are leading)
252 {
253 if(*it != 0)
254 throw SRC_BUG; // could not put all the data in the returned value !
255 --it;
256 }
257
258 if(used_endian == little_endian)
259 int_tools_swap_bytes(debut, sizeof(T));
260
261 return ret;
262 }
263
264
265 template <class T> void infinint::infinint_from(T a)
266 {
267 U_I size = sizeof(a);
268 S_I direction = +1;
269 unsigned char *ptr, *fin;
270
271 if(used_endian == not_initialized)
272 setup_endian();
273
274 if(used_endian == little_endian)
275 {
276 direction = -1;
277 ptr = (unsigned char *)(&a) + (size - 1);
278 fin = (unsigned char *)(&a) - 1;
279 }
280 else
281 {
282 direction = +1;
283 ptr = (unsigned char *)(&a);
284 fin = (unsigned char *)(&a) + size;
285 }
286
287 while(ptr != fin && *ptr == 0)
288 {
289 ptr += direction;
290 --size;
291 }
292
293 if(size == 0)
294 {
295 size = 1;
296 ptr -= direction;
297 }
298
299 field = new (std::nothrow) storage(size);
300 if(field != nullptr)
301 {
302 storage::iterator it = field->begin();
303
304 while(ptr != fin)
305 {
306 *it = *ptr;
307 ++it;
308 ptr += direction;
309 }
310 if(it != field->end())
311 throw SRC_BUG; // size mismatch in this algorithm
312 }
313 else
314 throw Ememory("template infinint::infinint_from");
315 }
316
317 template <class T> T infinint::max_val_of(T x)
318 {
319 x = 0;
320 x = ~x;
321
322 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
323 {
324 x = 1;
325 x = int_tools_rotate_right_one_bit(x);
326 x = ~x;
327 }
328
329 return x;
330 }
331
332 template <class T> void infinint::infinint_unstack_to(T & a)
333 {
334 // T is supposed to be an unsigned "integer"
335 // (ie.: sizeof() returns the width of the storage bit field and no sign bit is present)
336 // Note : static here avoids the recalculation of max_T at each call
337 static const T max_T = max_val_of(a);
338 infinint step = max_T - a;
339
340 if(*this < step)
341 {
342 T transfert = 0;
343 unsigned char *debut = (unsigned char *)&transfert;
344 unsigned char *ptr = debut + sizeof(transfert) - 1;
345 storage::iterator it = field->rbegin();
346
347 while(ptr >= debut && it != field->rend())
348 {
349 *ptr = *it;
350 --ptr;
351 --it;
352 }
353
354 if(used_endian == little_endian)
355 int_tools_swap_bytes(debut, sizeof(transfert));
356 a += transfert;
357 *this -= *this;
358 }
359 else
360 {
361 *this -= step;
362 a = max_T;
363 }
364 }
365
366 } // end of namespace
367
368 #endif
libdar::infinint::is_zero
bool is_zero() const
int_tools.hpp
elementary operation for infinint integers
libdar::infinint::unstack
void unstack(T &v)
convert infinint to standard interger types
Definition: real_infinint.hpp:124
libdar::proto_generic_file
ancestor class of generic_file
Definition: proto_generic_file.hpp:55
integers.hpp
are defined here basic integer types that tend to be portable
libdar::infinint
the arbitrary large positive integer class
Definition: real_infinint.hpp:62
libdar::storage
arbitrary large storage structure
Definition: storage.hpp:53
proto_generic_file.hpp
precursor class of generic_file used to avoid cyclic dependencies with storage and infinint
libdar::infinint::get_storage_size
infinint get_storage_size() const noexcept
it returns number of byte of information necessary to store the integer
Definition: real_infinint.hpp:128
libdar::infinint::operator[]
unsigned char operator[](const infinint &position) const
return in little endian order the information byte storing the integer
storage.hpp
contains a class that permits arbitrary large data storage
libdar
libdar namespace encapsulate all libdar symbols
Definition: archive.hpp:47