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