![]() |
Disk ARchive
2.5.2
Full featured and portable backup and archiving tool
|
00001 /*********************************************************************/ 00002 // dar - disk archive - a backup/restoration program 00003 // Copyright (C) 2002-2052 Denis Corbin 00004 // 00005 // This program is free software; you can redistribute it and/or 00006 // modify it under the terms of the GNU General Public License 00007 // as published by the Free Software Foundation; either version 2 00008 // of the License, or (at your option) any later version. 00009 // 00010 // This program is distributed in the hope that it will be useful, 00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00013 // GNU General Public License for more details. 00014 // 00015 // You should have received a copy of the GNU General Public License 00016 // along with this program; if not, write to the Free Software 00017 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 00018 // 00019 // to contact the author : http://dar.linux.free.fr/email.html 00020 /*********************************************************************/ 00021 00028 00029 #ifndef REAL_INFININT_HPP 00030 #define REAL_INFININT_HPP 00031 00032 #include "../my_config.h" 00033 00034 extern "C" 00035 { 00036 #if HAVE_SYS_TYPES_H 00037 #include <sys/types.h> 00038 #endif 00039 } // end extern "C" 00040 00041 #include <typeinfo> 00042 00043 #include "storage.hpp" 00044 #include "integers.hpp" 00045 #include "int_tools.hpp" 00046 #include "on_pool.hpp" 00047 00048 #define ZEROED_SIZE 50 00049 00050 namespace libdar 00051 { 00052 class generic_file; 00053 class user_interaction; 00054 00056 00059 class infinint : public on_pool 00060 { 00061 public : 00062 00063 #if SIZEOF_OFF_T > SIZEOF_TIME_T 00064 #if SIZEOF_OFF_T > SIZEOF_SIZE_T 00065 infinint(off_t a = 0) 00066 { infinint_from(a); }; 00067 #else 00068 infinint(size_t a = 0) 00069 { infinint_from(a); }; 00070 #endif 00071 #else 00072 #if SIZEOF_TIME_T > SIZEOF_SIZE_T 00073 infinint(time_t a = 0) 00074 { infinint_from(a); }; 00075 #else 00076 infinint(size_t a = 0) 00077 { infinint_from(a); }; 00078 #endif 00079 #endif 00080 00081 infinint(const infinint & ref) 00082 { copy_from(ref); } 00083 00084 // read an infinint from a file 00085 infinint(generic_file & x); 00086 00087 ~infinint() throw(Ebug) 00088 { detruit(); }; 00089 00090 const infinint & operator = (const infinint & ref) 00091 { detruit(); copy_from(ref); return *this; }; 00092 00093 void dump(generic_file &x) const; // write byte sequence to file 00094 void read(generic_file &f) { detruit(); build_from_file(f); }; 00095 00096 infinint & operator += (const infinint & ref); 00097 infinint & operator -= (const infinint & ref); 00098 infinint & operator *= (unsigned char arg); 00099 infinint & operator *= (const infinint & ref); 00100 template <class T> infinint power(const T & exponent) const; 00101 inline infinint & operator /= (const infinint & ref); 00102 inline infinint & operator %= (const infinint & ref); 00103 infinint & operator &= (const infinint & ref); 00104 infinint & operator |= (const infinint & ref); 00105 infinint & operator ^= (const infinint & ref); 00106 infinint & operator >>= (U_32 bit); 00107 infinint & operator >>= (infinint bit); 00108 infinint & operator <<= (U_32 bit); 00109 infinint & operator <<= (infinint bit); 00110 infinint operator ++(int a) 00111 { infinint ret = *this; ++(*this); return ret; }; 00112 infinint operator --(int a) 00113 { infinint ret = *this; --(*this); return ret; }; 00114 infinint & operator ++() 00115 { return *this += 1; }; 00116 infinint & operator --() 00117 { return *this -= 1; }; 00118 00119 U_32 operator % (U_32 arg) const 00120 { return modulo(arg); }; 00121 00122 // increment the argument up to a legal value for its storage type and decrement the object in consequence 00123 // note that the initial value of the argument is not ignored ! 00124 // when the object is null the value of the argument is unchanged 00125 template <class T>void unstack(T &v) 00126 { infinint_unstack_to(v); } 00127 00128 infinint get_storage_size() const { return field->size(); }; 00129 // it returns number of byte of information necessary to store the integer 00130 00131 unsigned char operator [] (const infinint & position) const; 00132 // return in little endian order the information byte storing the integer 00133 00134 bool is_zero() const; 00135 00136 friend bool operator < (const infinint &, const infinint &); 00137 friend bool operator == (const infinint &, const infinint &); 00138 friend bool operator > (const infinint &, const infinint &); 00139 friend bool operator <= (const infinint &, const infinint &); 00140 friend bool operator != (const infinint &, const infinint &); 00141 friend bool operator >= (const infinint &, const infinint &); 00142 friend void euclide(infinint a, const infinint &b, infinint &q, infinint &r); 00143 00144 static bool is_system_big_endian(); 00145 00146 private : 00147 static const int TG = 4; 00148 00149 enum endian { big_endian, little_endian, not_initialized }; 00150 typedef unsigned char group[TG]; 00151 00152 storage *field; 00153 00154 bool is_valid() const; 00155 void build_from_file(generic_file & x); 00156 void reduce(); // put the object in canonical form : no leading byte equal to zero 00157 void copy_from(const infinint & ref); 00158 void detruit(); 00159 void make_at_least_as_wider_as(const infinint & ref); 00160 template <class T> void infinint_from(T a); 00161 template <class T> T max_val_of(T x); 00162 template <class T> void infinint_unstack_to(T &a); 00163 template <class T> T modulo(T arg) const; 00164 signed int difference(const infinint & b) const; // gives the sign of (*this - arg) but only the sign ! 00165 00167 // static statments 00168 // 00169 static endian used_endian; 00170 static U_8 zeroed_field[ZEROED_SIZE]; 00171 static void setup_endian(); 00172 }; 00173 00174 00175 #define OPERATOR(OP) inline bool operator OP (const infinint &a, const infinint &b) \ 00176 { \ 00177 return a.difference(b) OP 0; \ 00178 } 00179 00180 OPERATOR(<) 00181 OPERATOR(>) 00182 OPERATOR(<=) 00183 OPERATOR(>=) 00184 OPERATOR(==) 00185 OPERATOR(!=) 00186 00187 infinint operator + (const infinint &, const infinint &); 00188 infinint operator - (const infinint &, const infinint &); 00189 infinint operator * (const infinint &, const infinint &); 00190 infinint operator * (const infinint &, const unsigned char); 00191 infinint operator * (const unsigned char, const infinint &); 00192 infinint operator / (const infinint &, const infinint &); 00193 infinint operator % (const infinint &, const infinint &); 00194 infinint operator & (const infinint & a, const infinint & bit); 00195 infinint operator | (const infinint & a, const infinint & bit); 00196 infinint operator ^ (const infinint & a, const infinint & bit); 00197 infinint operator >> (const infinint & a, U_32 bit); 00198 infinint operator >> (const infinint & a, const infinint & bit); 00199 infinint operator << (const infinint & a, U_32 bit); 00200 infinint operator << (const infinint & a, const infinint & bit); 00201 void euclide(infinint a, const infinint &b, infinint &q, infinint &r); 00202 template <class T> inline void euclide(T a, T b, T & q, T &r) 00203 { 00204 q = a/b; r = a%b; 00205 } 00206 00207 inline infinint & infinint::operator /= (const infinint & ref) 00208 { 00209 *this = *this / ref; 00210 return *this; 00211 } 00212 00213 inline infinint & infinint::operator %= (const infinint & ref) 00214 { 00215 *this = *this % ref; 00216 return *this; 00217 } 00218 00219 00223 00224 template <class T> infinint infinint::power(const T & exponent) const 00225 { 00226 infinint ret = 1; 00227 for(T count = 0; count < exponent; ++count) 00228 ret *= *this; 00229 00230 return ret; 00231 } 00232 00233 template <class T> T infinint::modulo(T arg) const 00234 { 00235 infinint tmp = *this % infinint(arg); 00236 T ret = 0; 00237 unsigned char *debut = (unsigned char *)(&ret); 00238 unsigned char *ptr = debut + sizeof(T) - 1; 00239 storage::iterator it = tmp.field->rbegin(); 00240 00241 while(it != tmp.field->rend() && ptr >= debut) 00242 { 00243 *ptr = *it; 00244 --ptr; 00245 --it; 00246 } 00247 00248 // checking for overflow (should never occur, but for sanity, we check it anyway) 00249 00250 while(it != tmp.field->rend()) // field may not be reduced (some zeros are leading) 00251 { 00252 if(*it != 0) 00253 throw SRC_BUG; // could not put all the data in the returned value ! 00254 --it; 00255 } 00256 00257 if(used_endian == little_endian) 00258 int_tools_swap_bytes(debut, sizeof(T)); 00259 00260 return ret; 00261 } 00262 00263 00264 template <class T> void infinint::infinint_from(T a) 00265 { 00266 U_I size = sizeof(a); 00267 S_I direction = +1; 00268 unsigned char *ptr, *fin; 00269 00270 if(used_endian == not_initialized) 00271 setup_endian(); 00272 00273 if(used_endian == little_endian) 00274 { 00275 direction = -1; 00276 ptr = (unsigned char *)(&a) + (size - 1); 00277 fin = (unsigned char *)(&a) - 1; 00278 } 00279 else 00280 { 00281 direction = +1; 00282 ptr = (unsigned char *)(&a); 00283 fin = (unsigned char *)(&a) + size; 00284 } 00285 00286 while(ptr != fin && *ptr == 0) 00287 { 00288 ptr += direction; 00289 --size; 00290 } 00291 00292 if(size == 0) 00293 { 00294 size = 1; 00295 ptr -= direction; 00296 } 00297 00298 field = new (std::nothrow) storage(size); 00299 if(field != nullptr) 00300 { 00301 storage::iterator it = field->begin(); 00302 00303 while(ptr != fin) 00304 { 00305 *it = *ptr; 00306 ++it; 00307 ptr += direction; 00308 } 00309 if(it != field->end()) 00310 throw SRC_BUG; // size mismatch in this algorithm 00311 } 00312 else 00313 throw Ememory("template infinint::infinint_from"); 00314 } 00315 00316 template <class T> T infinint::max_val_of(T x) 00317 { 00318 x = 0; 00319 x = ~x; 00320 00321 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 00322 { 00323 x = 1; 00324 x = int_tools_rotate_right_one_bit(x); 00325 x = ~x; 00326 } 00327 00328 return x; 00329 } 00330 00331 template <class T> void infinint::infinint_unstack_to(T &a) 00332 { 00333 // T is supposed to be an unsigned "integer" 00334 // (ie.: sizeof() returns the width of the storage bit field and no sign bit is present) 00335 // Note : static here avoids the recalculation of max_T at each call 00336 static const T max_T = max_val_of(a); 00337 infinint step = max_T - a; 00338 00339 if(*this < step) 00340 { 00341 T transfert = 0; 00342 unsigned char *debut = (unsigned char *)&transfert; 00343 unsigned char *ptr = debut + sizeof(transfert) - 1; 00344 storage::iterator it = field->rbegin(); 00345 00346 while(ptr >= debut && it != field->rend()) 00347 { 00348 *ptr = *it; 00349 --ptr; 00350 --it; 00351 } 00352 00353 if(used_endian == little_endian) 00354 int_tools_swap_bytes(debut, sizeof(transfert)); 00355 a += transfert; 00356 *this -= *this; 00357 } 00358 else 00359 { 00360 *this -= step; 00361 a = max_T; 00362 } 00363 } 00364 00365 } // end of namespace 00366 00367 #endif