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 private :
00139 static const int TG = 4;
00140
00141 enum endian { big_endian, little_endian, not_initialized };
00142 typedef unsigned char group[TG];
00143
00144 storage *field;
00145
00146 bool is_valid() const;
00147 void build_from_file(generic_file & x);
00148 void reduce();
00149 void copy_from(const infinint & ref);
00150 void detruit();
00151 void make_at_least_as_wider_as(const infinint & ref);
00152 template <class T> void infinint_from(T a);
00153 template <class T> void infinint_unstack_to(T &a);
00154 template <class T> T modulo(T arg) const;
00155 signed int difference(const infinint & b) const;
00156
00158
00159
00160 static endian used_endian;
00161 static void setup_endian();
00162 };
00163
00164
00165 #define OPERATOR(OP) inline bool operator OP (const infinint &a, const infinint &b) \
00166 { \
00167 E_BEGIN \
00168 return a.difference(b) OP 0; \
00169 E_END("operator OP", "infinint, infinint") \
00170 }
00171
00172 OPERATOR(<)
00173 OPERATOR(>)
00174 OPERATOR(<=)
00175 OPERATOR(>=)
00176 OPERATOR(==)
00177 OPERATOR(!=)
00178
00179 infinint operator + (const infinint &, const infinint &);
00180 infinint operator - (const infinint &, const infinint &);
00181 infinint operator * (const infinint &, const infinint &);
00182 infinint operator * (const infinint &, const unsigned char);
00183 infinint operator * (const unsigned char, const infinint &);
00184 infinint operator / (const infinint &, const infinint &);
00185 infinint operator % (const infinint &, const infinint &);
00186 infinint operator & (const infinint & a, const infinint & bit);
00187 infinint operator | (const infinint & a, const infinint & bit);
00188 infinint operator ^ (const infinint & a, const infinint & bit);
00189 infinint operator >> (const infinint & a, U_32 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 void euclide(infinint a, const infinint &b, infinint &q, infinint &r);
00194 template <class T> inline void euclide(T a, T b, T & q, T &r)
00195 {
00196 E_BEGIN
00197 q = a/b; r = a%b;
00198 E_END("euclide", "")
00199 }
00200
00201 inline infinint & infinint::operator /= (const infinint & ref)
00202 {
00203 E_BEGIN
00204 *this = *this / ref;
00205 return *this;
00206 E_END("infinint::operator /=", "")
00207 }
00208
00209 inline infinint & infinint::operator %= (const infinint & ref)
00210 {
00211 E_BEGIN
00212 *this = *this % ref;
00213 return *this;
00214 E_END("infinint::operator %=", "")
00215 }
00216
00217
00221
00222 template <class T> infinint infinint::power(const T & exponent) const
00223 {
00224 infinint ret = 1;
00225 for(T count = 0; count < exponent; ++count)
00226 ret *= *this;
00227
00228 return ret;
00229 }
00230
00231 template <class T> T infinint::modulo(T arg) const
00232 {
00233 E_BEGIN
00234 infinint tmp = *this % infinint(arg);
00235 T ret = 0;
00236 unsigned char *debut = (unsigned char *)(&ret);
00237 unsigned char *ptr = debut + sizeof(T) - 1;
00238 storage::iterator it = tmp.field->rbegin();
00239
00240 while(it != tmp.field->rend() && ptr >= debut)
00241 {
00242 *ptr = *it;
00243 --ptr;
00244 --it;
00245 }
00246
00247 if(it != tmp.field->rend())
00248 throw SRC_BUG;
00249
00250 if(used_endian == big_endian)
00251 int_tools_swap_bytes(debut, sizeof(T));
00252
00253 return ret;
00254 E_END("infinint::modulo", "")
00255 }
00256
00257
00258 template <class T> void infinint::infinint_from(T a)
00259 {
00260 E_BEGIN
00261 U_I size = sizeof(a);
00262 S_I direction = +1;
00263 unsigned char *ptr, *fin;
00264
00265 if(used_endian == not_initialized)
00266 setup_endian();
00267
00268 if(used_endian == big_endian)
00269 {
00270 direction = -1;
00271 ptr = (unsigned char *)(&a) + (size - 1);
00272 fin = (unsigned char *)(&a) - 1;
00273 }
00274 else
00275 {
00276 direction = +1;
00277 ptr = (unsigned char *)(&a);
00278 fin = (unsigned char *)(&a) + size;
00279 }
00280
00281 while(ptr != fin && *ptr == 0)
00282 {
00283 ptr += direction;
00284 --size;
00285 }
00286
00287 if(size == 0)
00288 {
00289 size = 1;
00290 ptr -= direction;
00291 }
00292
00293 field = new storage(size);
00294 if(field != NULL)
00295 {
00296 storage::iterator it = field->begin();
00297
00298 while(ptr != fin)
00299 {
00300 *it = *ptr;
00301 ++it;
00302 ptr += direction;
00303 }
00304 if(it != field->end())
00305 throw SRC_BUG;
00306 }
00307 else
00308 throw Ememory("template infinint::infinint_from");
00309
00310 E_END("infinint::infinint_from", "")
00311 }
00312
00313 template <class T> void infinint::infinint_unstack_to(T &a)
00314 {
00315 E_BEGIN
00316
00317
00318
00319 static const T max_T = int_tools_maxof_agregate(T(0));
00320 infinint step = max_T - a;
00321
00322 if(*this < step)
00323 {
00324 T transfert = 0;
00325 unsigned char *debut = (unsigned char *)&transfert;
00326 unsigned char *ptr = debut + sizeof(transfert) - 1;
00327 storage::iterator it = field->rbegin();
00328
00329 while(ptr >= debut && it != field->rend())
00330 {
00331 *ptr = *it;
00332 --ptr;
00333 --it;
00334 }
00335 if(used_endian == big_endian)
00336 int_tools_swap_bytes(debut, sizeof(transfert));
00337 a += transfert;
00338 *this -= *this;
00339 }
00340 else
00341 {
00342 *this -= step;
00343 a = max_T;
00344 }
00345 E_END("infinint::infinint_unstack_to", "")
00346 }
00347
00348 }
00349
00350 #endif