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