Disk ARchive 2.4.2
|
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 // $Id: real_infinint.hpp,v 1.26 2011/02/17 21:45:22 edrusb Rel $ 00022 // 00023 /*********************************************************************/ 00024 00031 00032 #ifndef REAL_INFININT_HPP 00033 #define REAL_INFININT_HPP 00034 00035 #include "../my_config.h" 00036 00037 extern "C" 00038 { 00039 #if HAVE_SYS_TYPES_H 00040 #include <sys/types.h> 00041 #endif 00042 } // end extern "C" 00043 00044 #include <typeinfo> 00045 #include "storage.hpp" 00046 #include "integers.hpp" 00047 #include "int_tools.hpp" 00048 00049 #define ZEROED_SIZE 50 00050 00051 namespace libdar 00052 { 00053 class generic_file; 00054 class user_interaction; 00055 00057 00060 class infinint 00061 { 00062 public : 00063 00064 #if SIZEOF_OFF_T > SIZEOF_TIME_T 00065 #if SIZEOF_OFF_T > SIZEOF_SIZE_T 00066 infinint(off_t a = 0) 00067 { E_BEGIN infinint_from(a); E_END("infinint::infinint", "off_t") }; 00068 #else 00069 infinint(size_t a = 0) 00070 { E_BEGIN infinint_from(a); E_END("infinint::infinint", "size_t") }; 00071 #endif 00072 #else 00073 #if SIZEOF_TIME_T > SIZEOF_SIZE_T 00074 infinint(time_t a = 0) 00075 { E_BEGIN infinint_from(a); E_END("infinint::infinint", "time_t") }; 00076 #else 00077 infinint(size_t a = 0) 00078 { E_BEGIN infinint_from(a); E_END("infinint::infinint", "size_t") }; 00079 #endif 00080 #endif 00081 00082 infinint(const infinint & ref) 00083 { E_BEGIN; copy_from(ref); E_END("infinint::infinint", "const infinint &"); } 00084 00085 // read an infinint from a file 00086 infinint(user_interaction & dialog, S_I fd); 00087 infinint(generic_file & x); 00088 00089 ~infinint() 00090 { E_BEGIN detruit(); E_END("infinint::~infinint","") }; 00091 00092 const infinint & operator = (const infinint & ref) 00093 { E_BEGIN detruit(); copy_from(ref); return *this; E_END("infinint::operator =","") }; 00094 00095 void dump(user_interaction & dialog, int fd) const; // write byte sequence to file 00096 void dump(generic_file &x) const; // write byte sequence to file 00097 void read(generic_file &f) { detruit(); build_from_file(f); }; 00098 00099 infinint & operator += (const infinint & ref); 00100 infinint & operator -= (const infinint & ref); 00101 infinint & operator *= (unsigned char arg); 00102 infinint & operator *= (const infinint & ref); 00103 template <class T> infinint power(const T & exponent) const; 00104 inline infinint & operator /= (const infinint & ref); 00105 inline infinint & operator %= (const infinint & ref); 00106 infinint & operator &= (const infinint & ref); 00107 infinint & operator |= (const infinint & ref); 00108 infinint & operator ^= (const infinint & ref); 00109 infinint & operator >>= (U_32 bit); 00110 infinint & operator >>= (infinint bit); 00111 infinint & operator <<= (U_32 bit); 00112 infinint & operator <<= (infinint bit); 00113 infinint operator ++(int a) 00114 { E_BEGIN infinint ret = *this; ++(*this); return ret; E_END("infinint::operator ++", "int") }; 00115 infinint operator --(int a) 00116 { E_BEGIN infinint ret = *this; --(*this); return ret; E_END("infinint::operator --", "int") }; 00117 infinint & operator ++() 00118 { E_BEGIN return *this += 1; E_END("infinint::operator ++", "()") }; 00119 infinint & operator --() 00120 { E_BEGIN return *this -= 1; E_END("infinint::operator --", "()") }; 00121 00122 U_32 operator % (U_32 arg) const 00123 { E_BEGIN return modulo(arg); E_END("infinint::operator %","") }; 00124 00125 // increment the argument up to a legal value for its storage type and decrement the object in consequence 00126 // note that the initial value of the argument is not ignored ! 00127 // when the object is null the value of the argument is unchanged 00128 template <class T>void unstack(T &v) 00129 { E_BEGIN infinint_unstack_to(v); E_END("infinint::unstack", typeid(v).name()) } 00130 00131 infinint get_storage_size() const { return field->size(); }; 00132 // it returns number of byte of information necessary to store the integer 00133 00134 unsigned char operator [] (const infinint & position) const; 00135 // return in big endian order the information byte storing the integer 00136 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 bool operator >= (const infinint &, const infinint &); 00143 friend void euclide(infinint a, const infinint &b, infinint &q, infinint &r); 00144 00145 static bool is_system_big_endian(); 00146 00147 private : 00148 static const int TG = 4; 00149 00150 enum endian { big_endian, little_endian, not_initialized }; 00151 typedef unsigned char group[TG]; 00152 00153 storage *field; 00154 00155 bool is_valid() const; 00156 void build_from_file(generic_file & x); 00157 void reduce(); // put the object in canonical form : no leading byte equal to zero 00158 void copy_from(const infinint & ref); 00159 void detruit(); 00160 void make_at_least_as_wider_as(const infinint & ref); 00161 template <class T> void infinint_from(T a); 00162 template <class T> T max_val_of(T x); 00163 template <class T> void infinint_unstack_to(T &a); 00164 template <class T> T modulo(T arg) const; 00165 signed int difference(const infinint & b) const; // gives the sign of (*this - arg) but only the sign ! 00166 00168 // static statments 00169 // 00170 static endian used_endian; 00171 static U_8 zeroed_field[ZEROED_SIZE]; 00172 static void setup_endian(); 00173 }; 00174 00175 00176 #define OPERATOR(OP) inline bool operator OP (const infinint &a, const infinint &b) \ 00177 { \ 00178 E_BEGIN \ 00179 return a.difference(b) OP 0; \ 00180 E_END("operator OP", "infinint, infinint") \ 00181 } 00182 00183 OPERATOR(<) 00184 OPERATOR(>) 00185 OPERATOR(<=) 00186 OPERATOR(>=) 00187 OPERATOR(==) 00188 OPERATOR(!=) 00189 00190 infinint operator + (const infinint &, const infinint &); 00191 infinint operator - (const infinint &, const infinint &); 00192 infinint operator * (const infinint &, const infinint &); 00193 infinint operator * (const infinint &, const unsigned char); 00194 infinint operator * (const unsigned char, const infinint &); 00195 infinint operator / (const infinint &, const infinint &); 00196 infinint operator % (const infinint &, const infinint &); 00197 infinint operator & (const infinint & a, const infinint & bit); 00198 infinint operator | (const infinint & a, const infinint & bit); 00199 infinint operator ^ (const infinint & a, const infinint & bit); 00200 infinint operator >> (const infinint & a, U_32 bit); 00201 infinint operator >> (const infinint & a, const infinint & bit); 00202 infinint operator << (const infinint & a, U_32 bit); 00203 infinint operator << (const infinint & a, const infinint & bit); 00204 void euclide(infinint a, const infinint &b, infinint &q, infinint &r); 00205 template <class T> inline void euclide(T a, T b, T & q, T &r) 00206 { 00207 E_BEGIN 00208 q = a/b; r = a%b; 00209 E_END("euclide", "") 00210 } 00211 00212 inline infinint & infinint::operator /= (const infinint & ref) 00213 { 00214 E_BEGIN 00215 *this = *this / ref; 00216 return *this; 00217 E_END("infinint::operator /=", "") 00218 } 00219 00220 inline infinint & infinint::operator %= (const infinint & ref) 00221 { 00222 E_BEGIN 00223 *this = *this % ref; 00224 return *this; 00225 E_END("infinint::operator %=", "") 00226 } 00227 00228 00232 00233 template <class T> infinint infinint::power(const T & exponent) const 00234 { 00235 infinint ret = 1; 00236 for(T count = 0; count < exponent; ++count) 00237 ret *= *this; 00238 00239 return ret; 00240 } 00241 00242 template <class T> T infinint::modulo(T arg) const 00243 { 00244 E_BEGIN 00245 infinint tmp = *this % infinint(arg); 00246 T ret = 0; 00247 unsigned char *debut = (unsigned char *)(&ret); 00248 unsigned char *ptr = debut + sizeof(T) - 1; 00249 storage::iterator it = tmp.field->rbegin(); 00250 00251 while(it != tmp.field->rend() && ptr >= debut) 00252 { 00253 *ptr = *it; 00254 --ptr; 00255 --it; 00256 } 00257 00258 // checking for overflow (should never occur, but for sanity, we check it anyway) 00259 00260 while(it != tmp.field->rend()) // field may not be reduced (some zeros are leading) 00261 { 00262 if(*it != 0) 00263 throw SRC_BUG; // could not put all the data in the returned value ! 00264 --it; 00265 } 00266 00267 if(used_endian == little_endian) 00268 int_tools_swap_bytes(debut, sizeof(T)); 00269 00270 return ret; 00271 E_END("infinint::modulo", "") 00272 } 00273 00274 00275 template <class T> void infinint::infinint_from(T a) 00276 { 00277 E_BEGIN 00278 U_I size = sizeof(a); 00279 S_I direction = +1; 00280 unsigned char *ptr, *fin; 00281 00282 if(used_endian == not_initialized) 00283 setup_endian(); 00284 00285 if(used_endian == little_endian) 00286 { 00287 direction = -1; 00288 ptr = (unsigned char *)(&a) + (size - 1); 00289 fin = (unsigned char *)(&a) - 1; 00290 } 00291 else 00292 { 00293 direction = +1; 00294 ptr = (unsigned char *)(&a); 00295 fin = (unsigned char *)(&a) + size; 00296 } 00297 00298 while(ptr != fin && *ptr == 0) 00299 { 00300 ptr += direction; 00301 --size; 00302 } 00303 00304 if(size == 0) 00305 { 00306 size = 1; 00307 ptr -= direction; 00308 } 00309 00310 field = new storage(size); 00311 if(field != NULL) 00312 { 00313 storage::iterator it = field->begin(); 00314 00315 while(ptr != fin) 00316 { 00317 *it = *ptr; 00318 ++it; 00319 ptr += direction; 00320 } 00321 if(it != field->end()) 00322 throw SRC_BUG; // size mismatch in this algorithm 00323 } 00324 else 00325 throw Ememory("template infinint::infinint_from"); 00326 00327 E_END("infinint::infinint_from", "") 00328 } 00329 00330 template <class T> T infinint::max_val_of(T x) 00331 { 00332 x = 0; 00333 x = ~x; 00334 00335 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 00336 { 00337 x = 1; 00338 x = int_tools_rotate_right_one_bit(x); 00339 x = ~x; 00340 } 00341 00342 return x; 00343 } 00344 00345 template <class T> void infinint::infinint_unstack_to(T &a) 00346 { 00347 E_BEGIN; 00348 // T is supposed to be an unsigned "integer" 00349 // (ie.: sizeof() returns the width of the storage bit field and no sign bit is present) 00350 // Note : static here avoids the recalculation of max_T at each call 00351 static const T max_T = max_val_of(a); 00352 infinint step = max_T - a; 00353 00354 if(*this < step) 00355 { 00356 T transfert = 0; 00357 unsigned char *debut = (unsigned char *)&transfert; 00358 unsigned char *ptr = debut + sizeof(transfert) - 1; 00359 storage::iterator it = field->rbegin(); 00360 00361 while(ptr >= debut && it != field->rend()) 00362 { 00363 *ptr = *it; 00364 --ptr; 00365 --it; 00366 } 00367 00368 if(used_endian == little_endian) 00369 int_tools_swap_bytes(debut, sizeof(transfert)); 00370 a += transfert; 00371 *this -= *this; 00372 } 00373 else 00374 { 00375 *this -= step; 00376 a = max_T; 00377 } 00378 E_END("infinint::infinint_unstack_to", "") 00379 } 00380 00381 } // end of namespace 00382 00383 #endif