00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
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 }
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);
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;
00089 void dump(generic_file &x) const;
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
00119
00120
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
00126
00127 unsigned char operator [] (const infinint & position) const;
00128
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();
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;
00158
00160
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;
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;
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
00319
00320
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 }
00351
00352 #endif