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