Disk ARchive  2.5.2
Full featured and portable backup and archiving tool
limitint.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 
00030 
00031 
00032 #ifndef LIMITINT_HPP
00033 #define LIMITINT_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 
00043 #if HAVE_UNISTD_H
00044 #include <unistd.h>
00045 #endif
00046 
00047 #if HAVE_STRING_H
00048 #include <string.h>
00049 #endif
00050 
00051 #if HAVE_STRINGS_H
00052 #include <strings.h>
00053 #endif
00054 } // end extern "C"
00055 
00056 #include <typeinfo>
00057 #include "integers.hpp"
00058 #include "erreurs.hpp"
00059 #include "int_tools.hpp"
00060 #include "on_pool.hpp"
00061 
00062 
00063 #define ZEROED_SIZE 50
00064 
00065 namespace libdar
00066 {
00067 
00070 
00071 
00072     class generic_file;
00073     class user_interaction;
00074 
00086 
00087     template<class B> class limitint : public on_pool
00088     {
00089     public :
00090 
00091 #if SIZEOF_OFF_T > SIZEOF_TIME_T
00092 #if SIZEOF_OFF_T > SIZEOF_SIZE_T
00093         limitint(off_t a = 0)
00094     { limitint_from(a); };
00095 #else
00096         limitint(size_t a = 0)
00097     { limitint_from(a); };
00098 #endif
00099 #else
00100 #if SIZEOF_TIME_T > SIZEOF_SIZE_T
00101         limitint(time_t a = 0)
00102     { limitint_from(a); };
00103 #else
00104         limitint(size_t a = 0)
00105     { limitint_from(a); };
00106 #endif
00107 #endif
00108 
00109         // read an limitint from a file
00110     limitint(generic_file & x);
00111 
00112         // for coherent footprint with real infinint
00113     ~limitint() throw(Ebug) {};
00114 
00115         void dump(generic_file &x) const; // write byte sequence to file
00116         void read(generic_file &f) { build_from_file(f); };
00117 
00118         limitint & operator += (const limitint & ref);
00119         limitint & operator -= (const limitint & ref);
00120         limitint & operator *= (const limitint & ref);
00121     template <class T> limitint power(const T & exponent) const;
00122         limitint & operator /= (const limitint & ref);
00123         limitint & operator %= (const limitint & ref);
00124     limitint & operator &= (const limitint & ref);
00125     limitint & operator |= (const limitint & ref);
00126     limitint & operator ^= (const limitint & ref);
00127         limitint & operator >>= (U_32 bit);
00128         limitint & operator >>= (limitint bit);
00129         limitint & operator <<= (U_32 bit);
00130         limitint & operator <<= (limitint bit);
00131         limitint operator ++(int a)
00132     { limitint ret = *this; ++(*this); return ret; };
00133         limitint operator --(int a)
00134     { limitint ret = *this; --(*this); return ret; };
00135         limitint & operator ++()
00136     { return *this += 1; };
00137         limitint & operator --()
00138     { return *this -= 1; };
00139 
00140         U_32 operator % (U_32 arg) const;
00141 
00142             // increment the argument up to a legal value for its storage type and decrement the object in consequence
00143             // note that the initial value of the argument is not ignored !
00144             // when the object is null the value of the argument stays the same as before
00145         template <class T>void unstack(T &v)
00146     { limitint_unstack_to(v); }
00147 
00148     limitint get_storage_size() const;
00149         // it returns number of byte of information necessary to store the integer
00150 
00151     unsigned char operator [] (const limitint & position) const;
00152         // return in little endian order the information bytes storing the integer
00153 
00154     bool is_zero() const { return field == 0; };
00155 
00156         bool operator < (const limitint &x) const { return field < x.field; };
00157         bool operator == (const limitint &x) const { return field == x.field; };
00158         bool operator > (const limitint &x) const { return field > x.field; };
00159         bool operator <= (const limitint &x) const { return field <= x.field; };
00160         bool operator != (const limitint &x) const { return field != x.field; };
00161         bool operator >= (const limitint &x) const { return field >= x.field; };
00162     static bool is_system_big_endian();
00163 
00164         B debug_get_max() const { return max_value; };
00165         B debug_get_bytesize() const { return bytesize; };
00166     B debug_get_field() const { return field; };
00167 
00168     private :
00169         static const int TG = 4;
00170     static const U_32 sizeof_field = sizeof(B); // number of bytes
00171 
00172         enum endian { big_endian, little_endian, not_initialized };
00173         typedef unsigned char group[TG];
00174 
00175         B field;
00176 
00177         void build_from_file(generic_file & x);
00178         template <class T> void limitint_from(T a);
00179     template <class T> T max_val_of(T x);
00180         template <class T> void limitint_unstack_to(T &a);
00181 
00183             // static statments
00184             //
00185         static endian used_endian;
00186         static const U_I bytesize = sizeof(B);
00187         static const B max_value = ~B(0) > 0 ? ~B(0) : ~(B(1) << (bytesize*8 - 1));
00188     static U_8 zeroed_field[ZEROED_SIZE];
00189 
00190         static void setup_endian();
00191     };
00192 
00193     template <class B> U_8 limitint<B>::zeroed_field[ZEROED_SIZE];
00194 
00195     template <class B> limitint<B> operator + (const limitint<B> &, const limitint<B> &);
00196     template <class B> inline limitint<B> operator + (const limitint<B> & a, U_I b)
00197     { return a + limitint<B>(b); }
00198     template <class B> limitint<B> operator - (const limitint<B> &, const limitint<B> &);
00199     template <class B> inline limitint<B> operator - (const limitint<B> & a, U_I b)
00200     { return a - limitint<B>(b); }
00201     template <class B> limitint<B> operator * (const limitint<B> &, const limitint<B> &);
00202     template <class B> inline limitint<B> operator * (const limitint<B> & a, U_I b)
00203     { return a * limitint<B>(b); }
00204     template <class B> limitint<B> operator / (const limitint<B> &, const limitint<B> &);
00205     template <class B> limitint<B> operator / (const limitint<B> & a, U_I b)
00206     { return a / limitint<B>(b); }
00207     template <class B> limitint<B> operator % (const limitint<B> &, const limitint<B> &);
00208     template <class B> limitint<B> operator >> (const limitint<B> & a, U_32 bit);
00209     template <class B> limitint<B> operator >> (const limitint<B> & a, const limitint<B> & bit);
00210     template <class B> limitint<B> operator << (const limitint<B> & a, U_32 bit);
00211     template <class B> limitint<B> operator << (const limitint<B> & a, const limitint<B> & bit);
00212     template <class B> limitint<B> operator & (const limitint<B> & a, U_32  bit);
00213     template <class B> limitint<B> operator & (const limitint<B> & a, const limitint<B> & bit);
00214     template <class B> limitint<B> operator | (const limitint<B> & a, U_32  bit);
00215     template <class B> limitint<B> operator | (const limitint<B> & a, const limitint<B> & bit);
00216     template <class B> limitint<B> operator ^ (const limitint<B> & a, U_32  bit);
00217     template <class B> limitint<B> operator ^ (const limitint<B> & a, const limitint<B> & bit);
00218 
00219     template <class T> inline void euclide(T a, T b, T & q, T &r)
00220     {
00221 
00222         q = a/b; r = a%b;
00223     }
00224 
00225     template <class B> inline void euclide(limitint<B> a, U_I b, limitint<B> & q, limitint<B> &r)
00226     {
00227         euclide(a, limitint<B>(b), q, r);
00228     }
00229 
00230 #ifndef INFININT_BASE_TYPE
00231 #error INFININT_BASE_TYPE not defined cannot instantiate template
00232 #else
00233     typedef limitint<INFININT_BASE_TYPE> infinint;
00234 #endif
00235 } // end of namespace
00239 
00240 #include "generic_file.hpp"
00241 #include "user_interaction.hpp"
00242 
00243 namespace libdar
00244 {
00245 
00246     template <class B> typename limitint<B>::endian limitint<B>::used_endian = not_initialized;
00247 
00248 
00249     template <class B> limitint<B>::limitint(generic_file & x)
00250     {
00251     build_from_file(x);
00252     }
00253 
00254 
00255     template <class B> void limitint<B>::build_from_file(generic_file & x)
00256     {
00257         unsigned char a;
00258         bool fin = false;
00259         limitint<B> skip = 0;
00260         char *ptr = (char *)&field;
00261         S_I lu;
00262         int_tools_bitfield bf;
00263 
00264         while(!fin)
00265         {
00266             lu = x.read((char *)&a, 1);
00267 
00268             if(lu <= 0)
00269                 throw Erange("limitint::build_from_file(generic_file)", gettext("Reached end of file before all data could be read"));
00270 
00271             if(a == 0)
00272                 ++skip;
00273             else // end of size field
00274             {
00275                     // computing the size to read
00276                 U_I pos = 0;
00277 
00278                 int_tools_expand_byte(a, bf);
00279                 for(S_I i = 0; i < 8; ++i)
00280                     pos += bf[i];
00281                 if(pos != 1)
00282                     throw Erange("limitint::build_from_file(generic_file)", gettext("Badly formed \"infinint\" or not supported format")); // more than 1 bit is set to 1
00283 
00284                 pos = 0;
00285                 while(bf[pos] == 0)
00286                     ++pos;
00287                 pos += 1; // bf starts at zero, but bit zero means 1 TG of length
00288 
00289                 skip *= 8;
00290                 skip += pos;
00291                 skip *= TG;
00292 
00293                 if(skip.field > bytesize)
00294                     throw Elimitint();
00295 
00296                 field = 0; // important to also clear "unread" bytes by this call
00297                 lu = x.read(ptr, skip.field);
00298 
00299                 if(used_endian == not_initialized)
00300                     setup_endian();
00301                 if(used_endian == little_endian)
00302                     int_tools_swap_bytes((unsigned char *)ptr, skip.field);
00303                 else
00304                     field >>= (bytesize - skip.field)*8;
00305                 fin = true;
00306             }
00307         }
00308     }
00309 
00310 
00311     template <class B> void limitint<B>::dump(generic_file & x) const
00312     {
00313         B width = bytesize;
00314         B pos;
00315         unsigned char last_width;
00316         B justification;
00317         S_I direction = +1;
00318         unsigned char *ptr, *fin;
00319 
00320 
00321         if(used_endian == not_initialized)
00322             setup_endian();
00323 
00324         if(used_endian == little_endian)
00325         {
00326             direction = -1;
00327             ptr = (unsigned char *)(&field) + (bytesize - 1);
00328             fin = (unsigned char *)(&field) - 1;
00329         }
00330         else
00331         {
00332             direction = +1;
00333             ptr = (unsigned char *)(&field);
00334             fin = (unsigned char *)(&field) + bytesize;
00335         }
00336 
00337         while(ptr != fin && *ptr == 0)
00338         {
00339             ptr += direction;
00340             --width;
00341         }
00342         if(width == 0)
00343             width = 1; // minimum size of information is 1 byte
00344 
00345             // "width" is the informational field size in byte
00346             // TG is the width in TG, thus the number of bit that must have
00347             // the preamble
00348         euclide(width, (const B)(TG), width, justification);
00349         if(justification != 0)
00350                 // in case we need to add some bytes to have a width multiple of TG
00351             ++width;  // we need then one more group to have a width multiple of TG
00352 
00353         euclide(width, (const B)(8), width, pos);
00354         if(pos == 0)
00355         {
00356             width--; // division is exact, only last bit of the preambule is set
00357             last_width = 0x80 >> 7;
00358                 // as we add the last byte separately width gets shorter by 1 byte
00359         }
00360         else // division non exact, the last_width (last byte), make the rounding
00361         {
00362             U_16 pos_s = (U_16)(0xFFFF & pos);
00363             last_width = 0x80 >> (pos_s - 1);
00364         }
00365 
00366             // now we write the preamble except the last byte. All these are zeros.
00367 
00368         while(width != 0)
00369         if(width > ZEROED_SIZE)
00370         {
00371         x.write((char *)zeroed_field, ZEROED_SIZE);
00372         width -= ZEROED_SIZE;
00373         }
00374         else
00375         {
00376         x.write((char *)zeroed_field, width);
00377         width = 0;
00378         }
00379 
00380             // now we write the last byte of the preambule, which as only one bit set
00381 
00382         x.write((char *)&last_width, 1);
00383 
00384             // we need now to write some justification byte to have an informational field multiple of TG
00385 
00386         if(justification != 0)
00387         {
00388             justification = TG - justification;
00389         if(justification > ZEROED_SIZE)
00390         throw SRC_BUG;
00391         else
00392                 x.write((char *)zeroed_field, justification);
00393         }
00394 
00395             // now we continue dumping the informational bytes:
00396         if(ptr == fin) // field is equal to zero
00397             x.write((char *)zeroed_field, 1);
00398         else // we have some bytes to write down
00399             while(ptr != fin)
00400             {
00401                 x.write((char *)ptr, 1);
00402         ptr += direction;
00403             }
00404     }
00405 
00406     template<class B> limitint<B> & limitint<B>::operator += (const limitint & arg)
00407     {
00408         B res = field + arg.field;
00409         if(res < field || res < arg.field)
00410             throw Elimitint();
00411         else
00412             field = res;
00413 
00414         return *this;
00415     }
00416 
00417     template <class B> limitint<B> & limitint<B>::operator -= (const limitint & arg)
00418     {
00419         if(field < arg.field)
00420             throw Erange("limitint::operator", gettext("Subtracting an \"infinint\" greater than the first, \"infinint\" cannot be negative"));
00421 
00422             // now processing the operation
00423 
00424         field -= arg.field;
00425         return *this;
00426     }
00427 
00428 
00429     template <class B> limitint<B> & limitint<B>::operator *= (const limitint & arg)
00430     {
00431         static const B max_power = bytesize*8 - 1;
00432 
00433         B total = int_tools_higher_power_of_2(field) + int_tools_higher_power_of_2(arg.field) + 1; // for an explaination about "+2" see NOTES
00434         if(total > max_power) // this is a bit too much restrictive, but unless remaking bit by bit, the operation,
00435                 // I don't see how to simply (and fast) know the result has not overflowed.
00436                 // of course, it would be fast and easy to access the CPU flag register to check for overflow,
00437                 // but that would not be portable, and unfortunately I haven't found any standart C++ expression that
00438                 // could transparently access to it.
00439             throw Elimitint();
00440 
00441         total = field*arg.field;
00442         if(field != 0 && arg.field != 0)
00443             if(total < field || total < arg.field)
00444                 throw Elimitint();
00445         field = total;
00446         return *this;
00447     }
00448 
00449     template <class B> template<class T> limitint<B> limitint<B>::power(const T & exponent) const
00450     {
00451     limitint ret = 1;
00452     for(T count = 0; count < exponent; ++count)
00453         ret *= *this;
00454 
00455     return ret;
00456     }
00457 
00458     template <class B> limitint<B> & limitint<B>::operator /= (const limitint & arg)
00459     {
00460         if(arg == 0)
00461             throw Einfinint("limitint.cpp : operator /=", gettext("Division by zero"));
00462 
00463         field /= arg.field;
00464         return *this;
00465     }
00466 
00467     template <class B> limitint<B> & limitint<B>::operator %= (const limitint & arg)
00468     {
00469         if(arg == 0)
00470             throw Einfinint("limitint.cpp : operator %=", gettext("Division by zero"));
00471 
00472         field %= arg.field;
00473         return *this;
00474     }
00475 
00476     template <class B> limitint<B> & limitint<B>::operator >>= (U_32 bit)
00477     {
00478     if(bit >= sizeof_field*8)
00479         field = 0;
00480     else
00481         field >>= bit;
00482         return *this;
00483     }
00484 
00485     template <class B> limitint<B> & limitint<B>::operator >>= (limitint bit)
00486     {
00487         field >>= bit.field;
00488         return *this;
00489     }
00490 
00491     template <class B> limitint<B> & limitint<B>::operator <<= (U_32 bit)
00492     {
00493         if(bit + int_tools_higher_power_of_2(field) >= bytesize*8)
00494             throw Elimitint();
00495         field <<= bit;
00496         return *this;
00497     }
00498 
00499     template <class B> limitint<B> & limitint<B>::operator <<= (limitint bit)
00500     {
00501         if(bit.field + int_tools_higher_power_of_2(field) >= bytesize*8)
00502             throw Elimitint();
00503         field <<= bit.field;
00504         return *this;
00505     }
00506 
00507     template <class B> limitint<B> & limitint<B>::operator &= (const limitint & arg)
00508     {
00509         field &= arg.field;
00510         return *this;
00511     }
00512 
00513     template <class B> limitint<B> & limitint<B>::operator |= (const limitint & arg)
00514     {
00515         field |= arg.field;
00516         return *this;
00517     }
00518 
00519     template <class B> limitint<B> & limitint<B>::operator ^= (const limitint & arg)
00520     {
00521         field ^= arg.field;
00522         return *this;
00523     }
00524 
00525     template <class B> U_32 limitint<B>::operator % (U_32 arg) const
00526     {
00527         return U_32(field % arg);
00528     }
00529 
00530     template <class B> template <class T> void limitint<B>::limitint_from(T a)
00531     {
00532         if(sizeof(a) <= bytesize || a <= (T)(max_value))
00533         field = B(a);
00534         else
00535             throw Elimitint();
00536     }
00537 
00538     template <class B> template <class T> T limitint<B>::max_val_of(T x)
00539     {
00540     x = 0;
00541     x = ~x;
00542 
00543     if(x < 1) // T is a signed integer type, we are not comparing to zero to avoid compiler warning when the template is used against unsigned integers
00544     {
00545         x = 1;
00546         x = int_tools_rotate_right_one_bit(x);
00547         x = ~x;
00548     }
00549 
00550     return x;
00551     }
00552 
00553     template <class B> template <class T> void limitint<B>::limitint_unstack_to(T &a)
00554     {
00555 
00556             // T is supposed to be an unsigned "integer"
00557             // (ie.: sizeof returns the width of the storage bit field  and no sign bit is present)
00558             // Note : static here avoids the recalculation of max_T at each call
00559         static const T max_T = max_val_of(a);
00560         T step = max_T - a;
00561 
00562         if(field < (B)(step) && (T)(field) < step)
00563         {
00564             a += field;
00565             field = 0;
00566         }
00567         else
00568         {
00569             field -= step;
00570             a = max_T;
00571         }
00572     }
00573 
00574     template <class B> limitint<B> limitint<B>::get_storage_size() const
00575     {
00576     B tmp = field;
00577     B ret = 0;
00578 
00579     while(tmp != 0)
00580     {
00581         tmp >>= 8;
00582         ret++;
00583     }
00584 
00585     return limitint<B>(ret);
00586     }
00587 
00588     template <class B> unsigned char limitint<B>::operator [] (const limitint & position) const
00589     {
00590     B tmp = field;
00591     B index = position.field; // C++ has only class protection, not object protection
00592 
00593     while(index > 0)
00594     {
00595         tmp >>= 8;
00596         index--;
00597     }
00598 
00599     return (unsigned char)(tmp & 0xFF);
00600     }
00601 
00602     template <class B> void limitint<B>::setup_endian()
00603     {
00604     if(integers_system_is_big_endian())
00605             used_endian = big_endian;
00606         else
00607             used_endian = little_endian;
00608 
00609     (void)memset(zeroed_field, 0, ZEROED_SIZE);
00610     }
00611 
00612 
00613     template <class B> bool limitint<B>::is_system_big_endian()
00614     {
00615     if(used_endian == not_initialized)
00616         setup_endian();
00617 
00618     switch(used_endian)
00619     {
00620     case big_endian:
00621         return true;
00622     case little_endian:
00623         return false;
00624     case not_initialized:
00625         throw SRC_BUG;
00626     default:
00627         throw SRC_BUG;
00628     }
00629     }
00630 
00631 
00635 
00636     template <class B> limitint<B> operator + (const limitint<B> & a, const limitint<B> & b)
00637     {
00638         limitint<B> ret = a;
00639         ret += b;
00640 
00641         return ret;
00642     }
00643 
00644     template <class B> limitint<B> operator - (const limitint<B> & a, const limitint<B> & b)
00645     {
00646         limitint<B> ret = a;
00647         ret -= b;
00648 
00649         return ret;
00650     }
00651 
00652     template <class B> limitint<B> operator * (const limitint<B> & a, const limitint<B> & b)
00653     {
00654         limitint<B> ret = a;
00655         ret *= b;
00656 
00657         return ret;
00658     }
00659 
00660     template <class B> limitint<B> operator / (const limitint<B> & a, const limitint<B> & b)
00661     {
00662         limitint<B> ret = a;
00663         ret /= b;
00664 
00665         return ret;
00666     }
00667 
00668     template <class B> limitint<B> operator % (const limitint<B> & a, const limitint<B> & b)
00669     {
00670         limitint<B> ret = a;
00671         ret %= b;
00672 
00673         return ret;
00674     }
00675 
00676     template <class B> limitint<B> operator >> (const limitint<B> & a, U_32 bit)
00677     {
00678         limitint<B> ret = a;
00679         ret >>= bit;
00680         return ret;
00681     }
00682 
00683     template <class B> limitint<B> operator >> (const limitint<B> & a, const limitint<B> & bit)
00684     {
00685         limitint<B> ret = a;
00686         ret >>= bit;
00687         return ret;
00688     }
00689 
00690     template <class B> limitint<B> operator << (const limitint<B> & a, U_32 bit)
00691     {
00692         limitint<B> ret = a;
00693         ret <<= bit;
00694         return ret;
00695     }
00696 
00697     template <class B> limitint<B> operator << (const limitint<B> & a, const limitint<B> & bit)
00698     {
00699         limitint<B> ret = a;
00700         ret <<= bit;
00701         return ret;
00702     }
00703 
00704     template <class B> limitint<B> operator & (const limitint<B> & a, U_32 bit)
00705     {
00706         limitint<B> ret = a;
00707         ret &= bit;
00708         return ret;
00709     }
00710 
00711     template <class B> limitint<B> operator & (const limitint<B> & a, const limitint<B> & bit)
00712     {
00713         limitint<B> ret = a;
00714     ret &= bit;
00715         return ret;
00716     }
00717 
00718     template <class B> limitint<B> operator | (const limitint<B> & a, U_32 bit)
00719     {
00720         limitint<B> ret = a;
00721         ret |= bit;
00722         return ret;
00723     }
00724 
00725     template <class B> limitint<B> operator | (const limitint<B> & a, const limitint<B> & bit)
00726     {
00727         limitint<B> ret = a;
00728         ret |= bit;
00729         return ret;
00730     }
00731 
00732     template <class B> limitint<B> operator ^ (const limitint<B> & a, U_32 bit)
00733     {
00734         limitint<B> ret = a;
00735         ret ^= bit;
00736         return ret;
00737     }
00738 
00739     template <class B> limitint<B> operator ^ (const limitint<B> & a, const limitint<B> & bit)
00740     {
00741         limitint<B> ret = a;
00742         ret ^= bit;
00743         return ret;
00744     }
00745 
00747 
00748 } // end of namespace
00749 
00750 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines