# real_infinint.hpp

Go to the documentation of this file.

    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.2 2007/07/22 16:35:00 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     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(); // put the object in canonical form : no leading byte equal to zero
    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; // gives the sign of (*this - arg) but only the sign !
    00156
    00158             // static statments
    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; // could not put all the data in the returned value !
    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; // size mismatch in this algorithm
    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             // T is supposed to be an unsigned "integer"
    00317             // (ie.: sizeof() returns the width of the storage bit field  and no sign bit is present)
    00318             // Note : static here avoids the recalculation of max_T at each call
    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 } // end of namespace
    00349
    00350 #endif