![]() |
Disk ARchive
2.5.2
Full featured and portable backup and archiving tool
|
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