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.2.1 2007/01/17 20:18:28 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         static const U_32 sizeof_field = sizeof(B);
00153 
00154         enum endian { big_endian, little_endian, not_initialized };
00155         typedef unsigned char group[TG];
00156 
00157         B field;
00158 
00159         void build_from_file(generic_file & x);
00160         template <class T> void limitint_from(T a);
00161         template <class T> void limitint_unstack_to(T &a);
00162 
00164             // static statments
00165             //
00166         static endian used_endian;
00167         static const U_I bytesize = sizeof(B);
00168         static const B max_value = ~B(0) > 0 ? ~B(0) : ~(B(1) << (bytesize*8 - 1));
00169         static void setup_endian();
00170     };
00171 
00172     template <class B> limitint<B> operator + (const limitint<B> &, const limitint<B> &);
00173     template <class B> inline limitint<B> operator + (const limitint<B> & a, U_I b)
00174     { return a + limitint<B>(b); }
00175     template <class B> limitint<B> operator - (const limitint<B> &, const limitint<B> &);
00176     template <class B> inline limitint<B> operator - (const limitint<B> & a, U_I b)
00177     { return a - limitint<B>(b); }
00178     template <class B> limitint<B> operator * (const limitint<B> &, const limitint<B> &);
00179     template <class B> inline limitint<B> operator * (const limitint<B> & a, U_I b)
00180     { return a * limitint<B>(b); }
00181     template <class B> limitint<B> operator / (const limitint<B> &, const limitint<B> &);
00182     template <class B> limitint<B> operator / (const limitint<B> & a, U_I b)
00183     { return a / limitint<B>(b); }
00184     template <class B> limitint<B> operator % (const limitint<B> &, const limitint<B> &);
00185     template <class B> limitint<B> operator >> (const limitint<B> & a, U_32 bit);
00186     template <class B> limitint<B> operator >> (const limitint<B> & a, const limitint<B> & bit);
00187     template <class B> limitint<B> operator << (const limitint<B> & a, U_32 bit);
00188     template <class B> limitint<B> operator << (const limitint<B> & a, const limitint<B> & bit);
00189 
00190     template <class T> inline void euclide(T a, T b, T & q, T &r)
00191     {
00192         E_BEGIN;
00193         q = a/b; r = a%b;
00194         E_END("euclide", "");
00195     }
00196 
00197     template <class B> inline void euclide(limitint<B> a, U_I b, limitint<B> & q, limitint<B> &r)
00198     {
00199         euclide(a, limitint<B>(b), q, r);
00200     }
00201 
00202 #ifndef INFININT_BASE_TYPE
00203 #error INFININT_BASE_TYPE not defined cannot instantiate template
00204 #else
00205     typedef limitint<INFININT_BASE_TYPE> infinint;
00206 #endif
00207 } // end of namespace
00211 
00212 #include "generic_file.hpp"
00213 #include "user_interaction.hpp"
00214 
00215 namespace libdar
00216 {
00217 
00218     template <class B> typename limitint<B>::endian limitint<B>::used_endian = not_initialized;
00219 
00220     template <class B> limitint<B>::limitint(user_interaction & dialog, S_I *fd, generic_file *x)
00221     {
00222         if(fd != NULL && x != NULL)
00223             throw Erange("limitint::limitint(file, file)", "Both arguments are not NULL, please choose one or the other, not both"); // message not translated, expected
00224         if(fd != NULL)
00225         {
00226             fichier f = fichier(dialog, dup(*fd));
00227             build_from_file(f);
00228         }
00229         else
00230             if(x != NULL)
00231                 build_from_file(*x);
00232             else
00233                 throw Erange("limitint::limitint(file, file)", "Cannot read from file, both arguments are NULL"); // message not translated, expected
00234     }
00235 
00236     template <class B> void limitint<B>::dump(user_interaction & dialog, S_I fd) const
00237     {
00238         fichier f = fichier(dialog, dup(fd));
00239         dump(f);
00240     }
00241 
00242     template <class B> void limitint<B>::build_from_file(generic_file & x)
00243     {
00244         E_BEGIN;
00245         unsigned char a;
00246         bool fin = false;
00247         limitint<B> skip = 0;
00248         char *ptr = (char *)&field;
00249         S_I lu;
00250         int_tools_bitfield bf;
00251 
00252         while(!fin)
00253         {
00254             lu = x.read((char *)&a, 1);
00255 
00256             if(lu <= 0)
00257                 throw Erange("limitint::build_from_file(generic_file)", gettext("Reached end of file before all data could be read"));
00258 
00259             if(a == 0)
00260                 skip++;
00261             else // end of size field
00262             {
00263                     // computing the size to read
00264                 U_I pos = 0;
00265 
00266                 int_tools_expand_byte(a, bf);
00267                 for(S_I i = 0; i < 8; i++)
00268                     pos = pos + bf[i];
00269                 if(pos != 1)
00270                     throw Erange("limitint::build_from_file(generic_file)", gettext("Badly formed infinint or not supported format")); // more than 1 bit is set to 1
00271 
00272                 pos = 0;
00273                 while(bf[pos] == 0)
00274                     pos++;
00275                 pos += 1; // bf starts at zero, but bit zero means 1 TG of length
00276 
00277                 skip *= 8;
00278                 skip += pos;
00279                 skip *= TG;
00280 
00281                 if(skip.field > bytesize)
00282                     throw Elimitint();
00283 
00284                 field = 0; // important to also clear "unread" bytes by the following call
00285                 lu = x.read(ptr, skip.field);
00286 
00287                 if(used_endian == not_initialized)
00288                     setup_endian();
00289                 if(used_endian == big_endian)
00290                     int_tools_swap_bytes((unsigned char *)ptr, skip.field);
00291                 else
00292                     field >>= (bytesize - skip.field)*8;
00293                 fin = true;
00294             }
00295         }
00296         E_END("limitint::read_from_file", "generic_file");
00297     }
00298 
00299 
00300     template <class B> void limitint<B>::dump(generic_file & x) const
00301     {
00302         E_BEGIN;
00303         B width = bytesize;
00304         B pos;
00305         unsigned char last_width;
00306         B justification;
00307         S_I direction = +1;
00308         unsigned char *ptr, *fin;
00309 
00310 
00311         if(used_endian == not_initialized)
00312             setup_endian();
00313 
00314         if(used_endian == big_endian)
00315         {
00316             direction = -1;
00317             ptr = (unsigned char *)(&field) + (bytesize - 1);
00318             fin = (unsigned char *)(&field) - 1;
00319         }
00320         else
00321         {
00322             direction = +1;
00323             ptr = (unsigned char *)(&field);
00324             fin = (unsigned char *)(&field) + bytesize;
00325         }
00326 
00327         while(ptr != fin && *ptr == 0)
00328         {
00329             ptr += direction;
00330             width--;
00331         }
00332         if(width == 0)
00333             width = 1; // minimum size of information is 1 byte
00334 
00335             // "width" is the informational field size in byte
00336             // TG is the width in TG, thus the number of bit that must have
00337             // the preamble
00338         euclide(width, (const B)(TG), width, justification);
00339         if(justification != 0)
00340                 // in case we need to add some bytes to have a width multiple of TG
00341             width++;  // we need then one more group to have a width multiple of TG
00342 
00343         euclide(width, (const B)(8), width, pos);
00344         if(pos == 0)
00345         {
00346             width--; // division is exact, only last bit of the preambule is set
00347             last_width = 0x80 >> 7;
00348                 // as we add the last byte separately width gets shorter by 1 byte
00349         }
00350         else // division non exact, the last_width (last byte), make the rounding
00351         {
00352             U_16 pos_s = (U_16)(0xFFFF & pos);
00353             last_width = 0x80 >> (pos_s - 1);
00354         }
00355 
00356             // now we write the preamble except the last byte. All theses are zeros.
00357 
00358         unsigned char u = 0x00;
00359 
00360         while(width-- > 0)
00361             if(x.write((char *)(&u), 1) < 1)
00362                 throw Erange("limitint::dump(generic_file)", gettext("Cannot write data to file"));
00363 
00364 
00365             // now we write the last byte of the preambule, which as only one bit set
00366 
00367         if(x.write((char *)&last_width, 1) < 1)
00368             throw Erange("limitint::dump(generic_file)", gettext("Cannot write data to file"));
00369 
00370             // we need now to write some justification byte to have an informational field multiple of TG
00371 
00372         if(justification != 0)
00373         {
00374             justification = TG - justification;
00375             while(justification-- > 0)
00376                 if(x.write((char *)(&u), 1) < 1)
00377                     throw Erange("limitint::dump(generic_file)", gettext("Cannot write data to file"));
00378         }
00379 
00380             // now we continue dumping the informational bytes:
00381         if(ptr == fin) // field is equal to zero
00382         {
00383             if(x.write((char *)(&u), 1) < 1)
00384                 throw Erange("limitint::dump(generic_file)", gettext("Cannot write data to file"));
00385         }
00386         else // we have some bytes to write down
00387             while(ptr != fin)
00388             {
00389                 if(x.write((char *)ptr, 1) < 1)
00390                     throw Erange("limitint::dump(generic_file)", gettext("Cannot write data to file"));
00391                 else
00392                     ptr += direction;
00393             }
00394 
00395         E_END("limitint::dump", "generic_file");
00396     }
00397 
00398     template<class B> limitint<B> & limitint<B>::operator += (const limitint & arg)
00399     {
00400         E_BEGIN;
00401         B res = field + arg.field;
00402         if(res < field || res < arg.field)
00403             throw Elimitint();
00404         else
00405             field = res;
00406 
00407         return *this;
00408         E_END("limitint::operator +=", "");
00409     }
00410 
00411     template <class B> limitint<B> & limitint<B>::operator -= (const limitint & arg)
00412     {
00413         E_BEGIN;
00414         if(field < arg.field)
00415             throw Erange("limitint::operator", gettext("Subtracting a infinint greater than the first, infinint cannot be negative"));
00416 
00417             // now processing the operation
00418 
00419         field -= arg.field;
00420         return *this;
00421         E_END("limitint::operator -=", "");
00422     }
00423 
00424 
00425     template <class B> limitint<B> & limitint<B>::operator *= (const limitint & arg)
00426     {
00427         E_BEGIN;
00428         static const B max_power = bytesize*8 - 1;
00429 
00430         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
00431         if(total > max_power) // this is a bit too much restrictive, but unless remaking bit by bit, the operation,
00432                 // I don't see how to simply (and fast) know the result has not overflowed.
00433                 // of course, it would be fast and easy to access the CPU flag register to check for overflow,
00434                 // but that would not be portable, and unfortunately I haven't found any standart C++ expression that
00435                 // could transparently access to it.
00436             throw Elimitint();
00437 
00438         total = field*arg.field;
00439         if(field != 0 && arg.field != 0)
00440             if(total < field || total < arg.field)
00441                 throw Elimitint();
00442         field = total;
00443         return *this;
00444         E_END("limitint::operator *=", "");
00445     }
00446 
00447     template <class B> template<class T> limitint<B> limitint<B>::power(const T & exponent) const
00448     {
00449         limitint ret = 1;
00450         for(T count = 0; count < exponent; count++)
00451             ret *= *this;
00452 
00453         return ret;
00454     }
00455 
00456     template <class B> limitint<B> & limitint<B>::operator /= (const limitint & arg)
00457     {
00458         E_BEGIN;
00459         if(arg == 0)
00460             throw Einfinint("limitint.cpp : operator /=", gettext("Division by zero"));
00461 
00462         field /= arg.field;
00463         return *this;
00464         E_END("limitint::operator /=", "");
00465     }
00466 
00467     template <class B> limitint<B> & limitint<B>::operator %= (const limitint & arg)
00468     {
00469         E_BEGIN;
00470         if(arg == 0)
00471             throw Einfinint("limitint.cpp : operator %=", gettext("Division by zero"));
00472 
00473         field %= arg.field;
00474         return *this;
00475         E_END("limitint::operator /=", "");
00476     }
00477 
00478     template <class B> limitint<B> & limitint<B>::operator >>= (U_32 bit)
00479     {
00480         E_BEGIN;
00481         if(bit >= sizeof_field)
00482             field = 0;
00483         else
00484             field >>= bit;
00485         return *this;
00486         E_END("limitint::operator >>=", "U_32");
00487     }
00488 
00489     template <class B> limitint<B> & limitint<B>::operator >>= (limitint bit)
00490     {
00491         E_BEGIN;
00492         field >>= bit.field;
00493         return *this;
00494         E_END("limitint::operator >>=", "limitint");
00495     }
00496 
00497     template <class B> limitint<B> & limitint<B>::operator <<= (U_32 bit)
00498     {
00499         E_BEGIN;
00500         if(bit + int_tools_higher_power_of_2(field) >= bytesize*8)
00501             throw Elimitint();
00502         field <<= bit;
00503         return *this;
00504         E_END("limitint::operator <<=", "U_32");
00505     }
00506 
00507     template <class B> limitint<B> & limitint<B>::operator <<= (limitint bit)
00508     {
00509         E_BEGIN;
00510         if(bit.field + int_tools_higher_power_of_2(field) >= bytesize*8)
00511             throw Elimitint();
00512         field <<= bit.field;
00513         return *this;
00514         E_END("limitint::operator <<=", "limitint");
00515     }
00516 
00517     template <class B> U_32 limitint<B>::operator % (U_32 arg) const
00518     {
00519         E_BEGIN;
00520         return U_32(field % arg);
00521         E_END("limitint::modulo", "");
00522     }
00523 
00524     template <class B> template <class T> void limitint<B>::limitint_from(T a)
00525     {
00526         E_BEGIN;
00527         if(sizeof(a) <= bytesize || a <= (T)(max_value))
00528             field = B(a);
00529         else
00530             throw Elimitint();
00531         E_END("limitint::limitint_from", "");
00532     }
00533 
00534     template <class B> template <class T> void limitint<B>::limitint_unstack_to(T &a)
00535     {
00536         E_BEGIN;
00537             // T is supposed to be an unsigned "integer"
00538             // (ie.: sizeof returns the width of the storage bit field  and no sign bit is present)
00539             // Note : static here avoids the recalculation of max_T at each call
00540         static const T max_T = ~T(0) > 0 ? ~T(0) : ~int_tools_rotate_right_one_bit(T(1));
00541         T step = max_T - a;
00542 
00543         if(field < (B)(step) && (T)(field) < step)
00544         {
00545             a += field;
00546             field = 0;
00547         }
00548         else
00549         {
00550             field -= step;
00551             a = max_T;
00552         }
00553 
00554         E_END("limitint::limitint_unstack_to", "");
00555     }
00556 
00557     template <class B> limitint<B> limitint<B>::get_storage_size() const
00558     {
00559         B tmp = field;
00560         B ret = 0;
00561 
00562         while(tmp != 0)
00563         {
00564             tmp >>= 8;
00565             ret++;
00566         }
00567 
00568         return limitint<B>(ret);
00569     }
00570 
00571     template <class B> unsigned char limitint<B>::operator [] (const limitint & position) const
00572     {
00573         B tmp = field;
00574         B index = position.field; // C++ has only class protection, not object protection
00575 
00576         while(index > 0)
00577         {
00578             tmp >>= 8;
00579             index--;
00580         }
00581 
00582         return (unsigned char)(tmp & 0xFF);
00583     }
00584 
00585     template <class B> void limitint<B>::setup_endian()
00586     {
00587         E_BEGIN;
00588         U_16 u = 1;
00589         unsigned char *ptr = (unsigned char *)(&u);
00590 
00591         if(ptr[0] == 1)
00592             used_endian = big_endian;
00593         else
00594             used_endian = little_endian;
00595         E_END("limitint::setup_endian", "");
00596     }
00597 
00598 
00602 
00603     template <class B> limitint<B> operator + (const limitint<B> & a, const limitint<B> & b)
00604     {
00605         E_BEGIN;
00606         limitint<B> ret = a;
00607         ret += b;
00608 
00609         return ret;
00610         E_END("operator +", "limitint");
00611     }
00612 
00613     template <class B> limitint<B> operator - (const limitint<B> & a, const limitint<B> & b)
00614     {
00615         E_BEGIN;
00616         limitint<B> ret = a;
00617         ret -= b;
00618 
00619         return ret;
00620         E_END("operator -", "limitint");
00621     }
00622 
00623     template <class B> limitint<B> operator * (const limitint<B> & a, const limitint<B> & b)
00624     {
00625         E_BEGIN;
00626         limitint<B> ret = a;
00627         ret *= b;
00628 
00629         return ret;
00630         E_END("operator *", "limitint");
00631     }
00632 
00633     template <class B> limitint<B> operator / (const limitint<B> & a, const limitint<B> & b)
00634     {
00635         E_BEGIN;
00636         limitint<B> ret = a;
00637         ret /= b;
00638 
00639         return ret;
00640         E_END("operator / ", "limitint");
00641     }
00642 
00643     template <class B> limitint<B> operator % (const limitint<B> & a, const limitint<B> & b)
00644     {
00645         E_BEGIN;
00646         limitint<B> ret = a;
00647         ret %= b;
00648 
00649         return ret;
00650         E_END("operator %", "limitint");
00651     }
00652 
00653     template <class B> limitint<B> operator >> (const limitint<B> & a, U_32 bit)
00654     {
00655         E_BEGIN;
00656         limitint<B> ret = a;
00657         ret >>= bit;
00658         return ret;
00659         E_END("operator >>", "limitint, U_32");
00660     }
00661 
00662     template <class B> limitint<B> operator >> (const limitint<B> & a, const limitint<B> & bit)
00663     {
00664         E_BEGIN;
00665         limitint<B> ret = a;
00666         ret >>= bit;
00667         return ret;
00668         E_END("operator >>", "limitint");
00669     }
00670 
00671     template <class B> limitint<B> operator << (const limitint<B> & a, U_32 bit)
00672     {
00673         E_BEGIN;
00674         limitint<B> ret = a;
00675         ret <<= bit;
00676         return ret;
00677         E_END("operator <<", "limitint, U_32");
00678     }
00679 
00680     template <class B> limitint<B> operator << (const limitint<B> & a, const limitint<B> & bit)
00681     {
00682         E_BEGIN;
00683         limitint<B> ret = a;
00684         ret <<= bit;
00685         return ret;
00686         E_END("operator <<", "limitint");
00687     }
00688 
00689 } // end of namespace
00690 
00691 #endif

Generated on Tue Apr 10 07:56:11 2007 for Disk ARchive by  doxygen 1.5.1