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