Disk ARchive 2.3.11

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.3 2011/01/04 16:27:13 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         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(); // put the object in canonical form : no leading byte equal to zero
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; // gives the sign of (*this - arg) but only the sign !
00158 
00160             // static statments
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; // could not put all the data in the returned value !
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; // size mismatch in this algorithm
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             // T is supposed to be an unsigned "integer"
00319             // (ie.: sizeof() returns the width of the storage bit field  and no sign bit is present)
00320             // Note : static here avoids the recalculation of max_T at each call
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 } // end of namespace
00351 
00352 #endif
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Defines