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

Generated on Fri Nov 17 01:43:09 2006 for Disk ARchive by  doxygen 1.5.1