Stephen Paulger
Library for big numbers from http://www.ttmath.org/
Dependents: PIDHeater82 Conceptcontroller_v_1_0 AlarmClockApp COG4050_adxl355_tilt ... more
Embed:
(wiki syntax)
Show/hide line numbers
ttmathuint.h
Go to the documentation of this file.
00001 /* 00002 * This file is a part of TTMath Bignum Library 00003 * and is distributed under the (new) BSD licence. 00004 * Author: Tomasz Sowa <t.sowa@ttmath.org> 00005 */ 00006 00007 /* 00008 * Copyright (c) 2006-2011, Tomasz Sowa 00009 * All rights reserved. 00010 * 00011 * Redistribution and use in source and binary forms, with or without 00012 * modification, are permitted provided that the following conditions are met: 00013 * 00014 * * Redistributions of source code must retain the above copyright notice, 00015 * this list of conditions and the following disclaimer. 00016 * 00017 * * Redistributions in binary form must reproduce the above copyright 00018 * notice, this list of conditions and the following disclaimer in the 00019 * documentation and/or other materials provided with the distribution. 00020 * 00021 * * Neither the name Tomasz Sowa nor the names of contributors to this 00022 * project may be used to endorse or promote products derived 00023 * from this software without specific prior written permission. 00024 * 00025 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 00026 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00027 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00028 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 00029 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 00030 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 00031 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 00032 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 00033 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 00034 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 00035 * THE POSSIBILITY OF SUCH DAMAGE. 00036 */ 00037 00038 00039 00040 #ifndef headerfilettmathuint 00041 #define headerfilettmathuint 00042 00043 00044 /*! 00045 \file ttmathuint.h 00046 \brief template class UInt<uint> 00047 */ 00048 00049 #include <iostream> 00050 #include <iomanip> 00051 00052 00053 #include "ttmathtypes.h" 00054 #include "ttmathmisc.h" 00055 00056 00057 00058 /*! 00059 \brief a namespace for the TTMath library 00060 */ 00061 namespace ttmath 00062 { 00063 00064 /*! 00065 \brief UInt implements a big integer value without a sign 00066 00067 value_size - how many bytes specify our value 00068 on 32bit platforms: value_size=1 -> 4 bytes -> 32 bits 00069 on 64bit platforms: value_size=1 -> 8 bytes -> 64 bits 00070 value_size = 1,2,3,4,5,6.... 00071 */ 00072 template<uint value_size> 00073 class UInt 00074 { 00075 public: 00076 00077 /*! 00078 buffer for the integer value 00079 table[0] - the lowest word of the value 00080 */ 00081 uint table [value_size]; 00082 00083 00084 00085 /*! 00086 some methods used for debugging purposes 00087 */ 00088 00089 00090 /*! 00091 this method is only for debugging purposes or when we want to make 00092 a table of a variable (constant) in ttmathbig.h 00093 00094 it prints the table in a nice form of several columns 00095 */ 00096 template<class ostream_type> 00097 void PrintTable (ostream_type & output) const 00098 { 00099 // how many columns there'll be 00100 const int columns = 8; 00101 00102 int c = 1; 00103 for(int i=value_size-1 ; i>=0 ; --i) 00104 { 00105 output << "0x" << std::setfill('0'); 00106 00107 #ifdef TTMATH_PLATFORM32 00108 output << std::setw(8); 00109 #else 00110 output << std::setw(16); 00111 #endif 00112 00113 output << std::hex << table [i]; 00114 00115 if( i>0 ) 00116 { 00117 output << ", "; 00118 00119 if( ++c > columns ) 00120 { 00121 output << std::endl; 00122 c = 1; 00123 } 00124 } 00125 } 00126 00127 output << std::dec << std::endl; 00128 } 00129 00130 00131 /*! 00132 this method is used when macro TTMATH_DEBUG_LOG is defined 00133 */ 00134 template<class char_type, class ostream_type> 00135 static void PrintVectorLog (const char_type * msg, ostream_type & output, const uint * vector, uint vector_len) 00136 { 00137 output << msg << std::endl; 00138 00139 for(uint i=0 ; i<vector_len ; ++i) 00140 output << " table[" << i << "]: " << vector[i] << std::endl; 00141 } 00142 00143 00144 /*! 00145 this method is used when macro TTMATH_DEBUG_LOG is defined 00146 */ 00147 template<class char_type, class ostream_type> 00148 static void PrintVectorLog (const char_type * msg, uint carry, ostream_type & output, const uint * vector, uint vector_len) 00149 { 00150 PrintVectorLog (msg, output, vector, vector_len); 00151 output << " carry: " << carry << std::endl; 00152 } 00153 00154 00155 /*! 00156 this method is used when macro TTMATH_DEBUG_LOG is defined 00157 */ 00158 template<class char_type, class ostream_type> 00159 void PrintLog (const char_type * msg, ostream_type & output) const 00160 { 00161 PrintVectorLog (msg, output, table , value_size); 00162 } 00163 00164 00165 /*! 00166 this method is used when macro TTMATH_DEBUG_LOG is defined 00167 */ 00168 template<class char_type, class ostream_type> 00169 void PrintLog (const char_type * msg, uint carry, ostream_type & output) const 00170 { 00171 PrintVectorLog (msg, output, table , value_size); 00172 output << " carry: " << carry << std::endl; 00173 } 00174 00175 00176 /*! 00177 this method returns the size of the table 00178 */ 00179 uint Size () const 00180 { 00181 return value_size; 00182 } 00183 00184 00185 /*! 00186 this method sets zero 00187 */ 00188 void SetZero () 00189 { 00190 // in the future here can be 'memset' 00191 00192 for(uint i=0 ; i<value_size ; ++i) 00193 table [i] = 0; 00194 00195 TTMATH_LOG("UInt::SetZero") 00196 } 00197 00198 00199 /*! 00200 this method sets one 00201 */ 00202 void SetOne () 00203 { 00204 SetZero (); 00205 table [0] = 1; 00206 00207 TTMATH_LOG("UInt::SetOne") 00208 } 00209 00210 00211 /*! 00212 this method sets the max value which this class can hold 00213 (all bits will be one) 00214 */ 00215 void SetMax () 00216 { 00217 for(uint i=0 ; i<value_size ; ++i) 00218 table [i] = TTMATH_UINT_MAX_VALUE; 00219 00220 TTMATH_LOG("UInt::SetMax") 00221 } 00222 00223 00224 /*! 00225 this method sets the min value which this class can hold 00226 (for an unsigned integer value the zero is the smallest value) 00227 */ 00228 void SetMin () 00229 { 00230 SetZero (); 00231 00232 TTMATH_LOG("UInt::SetMin") 00233 } 00234 00235 00236 /*! 00237 this method swappes this for an argument 00238 */ 00239 void Swap (UInt<value_size> & ss2) 00240 { 00241 for(uint i=0 ; i<value_size ; ++i) 00242 { 00243 uint temp = table [i]; 00244 table [i] = ss2.table [i]; 00245 ss2.table [i] = temp; 00246 } 00247 } 00248 00249 00250 #ifdef TTMATH_PLATFORM32 00251 00252 /*! 00253 this method copies the value stored in an another table 00254 (warning: first values in temp_table are the highest words -- it's different 00255 from our table) 00256 00257 we copy as many words as it is possible 00258 00259 if temp_table_len is bigger than value_size we'll try to round 00260 the lowest word from table depending on the last not used bit in temp_table 00261 (this rounding isn't a perfect rounding -- look at the description below) 00262 00263 and if temp_table_len is smaller than value_size we'll clear the rest words 00264 in the table 00265 */ 00266 void SetFromTable (const uint * temp_table, uint temp_table_len) 00267 { 00268 uint temp_table_index = 0; 00269 sint i; // 'i' with a sign 00270 00271 for(i=value_size-1 ; i>=0 && temp_table_index<temp_table_len; --i, ++temp_table_index) 00272 table [i] = temp_table[ temp_table_index ]; 00273 00274 00275 // rounding mantissa 00276 if( temp_table_index < temp_table_len ) 00277 { 00278 if( (temp_table[temp_table_index] & TTMATH_UINT_HIGHEST_BIT) != 0 ) 00279 { 00280 /* 00281 very simply rounding 00282 if the bit from not used last word from temp_table is set to one 00283 we're rouding the lowest word in the table 00284 00285 in fact there should be a normal addition but 00286 we don't use Add() or AddTwoInts() because these methods 00287 can set a carry and then there'll be a small problem 00288 for optimization 00289 */ 00290 if( table [0] != TTMATH_UINT_MAX_VALUE ) 00291 ++table [0]; 00292 } 00293 } 00294 00295 // cleaning the rest of the mantissa 00296 for( ; i>=0 ; --i) 00297 table [i] = 0; 00298 00299 00300 TTMATH_LOG("UInt::SetFromTable") 00301 } 00302 00303 #endif 00304 00305 00306 #ifdef TTMATH_PLATFORM64 00307 /*! 00308 this method copies the value stored in an another table 00309 (warning: first values in temp_table are the highest words -- it's different 00310 from our table) 00311 00312 ***this method is created only on a 64bit platform*** 00313 00314 we copy as many words as it is possible 00315 00316 if temp_table_len is bigger than value_size we'll try to round 00317 the lowest word from table depending on the last not used bit in temp_table 00318 (this rounding isn't a perfect rounding -- look at the description below) 00319 00320 and if temp_table_len is smaller than value_size we'll clear the rest words 00321 in the table 00322 00323 warning: we're using 'temp_table' as a pointer at 32bit words 00324 */ 00325 void SetFromTable (const unsigned int * temp_table, uint temp_table_len) 00326 { 00327 uint temp_table_index = 0; 00328 sint i; // 'i' with a sign 00329 00330 for(i=value_size-1 ; i>=0 && temp_table_index<temp_table_len; --i, ++temp_table_index) 00331 { 00332 table [i] = uint (temp_table[ temp_table_index ]) << 32; 00333 00334 ++temp_table_index; 00335 00336 if( temp_table_index<temp_table_len ) 00337 table [i] |= temp_table[ temp_table_index ]; 00338 } 00339 00340 00341 // rounding mantissa 00342 if( temp_table_index < temp_table_len ) 00343 { 00344 if( (temp_table[temp_table_index] & TTMATH_UINT_HIGHEST_BIT) != 0 ) 00345 { 00346 /* 00347 very simply rounding 00348 if the bit from not used last word from temp_table is set to one 00349 we're rouding the lowest word in the table 00350 00351 in fact there should be a normal addition but 00352 we don't use Add() or AddTwoInts() because these methods 00353 can set a carry and then there'll be a small problem 00354 for optimization 00355 */ 00356 if( table [0] != TTMATH_UINT_MAX_VALUE ) 00357 ++table [0]; 00358 } 00359 } 00360 00361 // cleaning the rest of the mantissa 00362 for( ; i >= 0 ; --i) 00363 table [i] = 0; 00364 00365 TTMATH_LOG("UInt::SetFromTable") 00366 } 00367 00368 #endif 00369 00370 00371 00372 00373 00374 /*! 00375 * 00376 * basic mathematic functions 00377 * 00378 */ 00379 00380 00381 00382 00383 /*! 00384 this method adds one to the existing value 00385 */ 00386 uint AddOne () 00387 { 00388 return AddInt (1); 00389 } 00390 00391 00392 /*! 00393 this method subtracts one from the existing value 00394 */ 00395 uint SubOne () 00396 { 00397 return SubInt (1); 00398 } 00399 00400 00401 private: 00402 00403 00404 /*! 00405 an auxiliary method for moving bits into the left hand side 00406 00407 this method moves only words 00408 */ 00409 void RclMoveAllWords(uint & rest_bits, uint & last_c, uint bits, uint c) 00410 { 00411 rest_bits = bits % TTMATH_BITS_PER_UINT; 00412 uint all_words = bits / TTMATH_BITS_PER_UINT; 00413 uint mask = ( c ) ? TTMATH_UINT_MAX_VALUE : 0; 00414 00415 00416 if( all_words >= value_size ) 00417 { 00418 if( all_words == value_size && rest_bits == 0 ) 00419 last_c = table [0] & 1; 00420 // else: last_c is default set to 0 00421 00422 // clearing 00423 for(uint i = 0 ; i<value_size ; ++i) 00424 table [i] = mask; 00425 00426 rest_bits = 0; 00427 } 00428 else 00429 if( all_words > 0 ) 00430 { 00431 // 0 < all_words < value_size 00432 00433 sint first, second; 00434 last_c = table [value_size - all_words] & 1; // all_words is greater than 0 00435 00436 // copying the first part of the value 00437 for(first = value_size-1, second=first-all_words ; second>=0 ; --first, --second) 00438 table [first] = table [second]; 00439 00440 // setting the rest to 'c' 00441 for( ; first>=0 ; --first ) 00442 table [first] = mask; 00443 } 00444 00445 TTMATH_LOG("UInt::RclMoveAllWords") 00446 } 00447 00448 public: 00449 00450 /*! 00451 moving all bits into the left side 'bits' times 00452 return value <- this <- C 00453 00454 bits is from a range of <0, man * TTMATH_BITS_PER_UINT> 00455 or it can be even bigger then all bits will be set to 'c' 00456 00457 the value c will be set into the lowest bits 00458 and the method returns state of the last moved bit 00459 */ 00460 uint Rcl (uint bits, uint c=0) 00461 { 00462 uint last_c = 0; 00463 uint rest_bits = bits; 00464 00465 if( bits == 0 ) 00466 return 0; 00467 00468 if( bits >= TTMATH_BITS_PER_UINT ) 00469 RclMoveAllWords(rest_bits, last_c, bits, c); 00470 00471 if( rest_bits == 0 ) 00472 { 00473 TTMATH_LOG("UInt::Rcl") 00474 return last_c; 00475 } 00476 00477 // rest_bits is from 1 to TTMATH_BITS_PER_UINT-1 now 00478 if( rest_bits == 1 ) 00479 { 00480 last_c = Rcl2_one(c); 00481 } 00482 else if( rest_bits == 2 ) 00483 { 00484 // performance tests showed that for rest_bits==2 it's better to use Rcl2_one twice instead of Rcl2(2,c) 00485 Rcl2_one(c); 00486 last_c = Rcl2_one(c); 00487 } 00488 else 00489 { 00490 last_c = Rcl2(rest_bits, c); 00491 } 00492 00493 TTMATH_LOGC("UInt::Rcl", last_c) 00494 00495 return last_c; 00496 } 00497 00498 private: 00499 00500 /*! 00501 an auxiliary method for moving bits into the right hand side 00502 00503 this method moves only words 00504 */ 00505 void RcrMoveAllWords(uint & rest_bits, uint & last_c, uint bits, uint c) 00506 { 00507 rest_bits = bits % TTMATH_BITS_PER_UINT; 00508 uint all_words = bits / TTMATH_BITS_PER_UINT; 00509 uint mask = ( c ) ? TTMATH_UINT_MAX_VALUE : 0; 00510 00511 00512 if( all_words >= value_size ) 00513 { 00514 if( all_words == value_size && rest_bits == 0 ) 00515 last_c = (table [value_size-1] & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0; 00516 // else: last_c is default set to 0 00517 00518 // clearing 00519 for(uint i = 0 ; i<value_size ; ++i) 00520 table [i] = mask; 00521 00522 rest_bits = 0; 00523 } 00524 else if( all_words > 0 ) 00525 { 00526 // 0 < all_words < value_size 00527 00528 uint first, second; 00529 last_c = (table [all_words - 1] & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0; // all_words is > 0 00530 00531 // copying the first part of the value 00532 for(first=0, second=all_words ; second<value_size ; ++first, ++second) 00533 table [first] = table [second]; 00534 00535 // setting the rest to 'c' 00536 for( ; first<value_size ; ++first ) 00537 table [first] = mask; 00538 } 00539 00540 TTMATH_LOG("UInt::RcrMoveAllWords") 00541 } 00542 00543 public: 00544 00545 /*! 00546 moving all bits into the right side 'bits' times 00547 c -> this -> return value 00548 00549 bits is from a range of <0, man * TTMATH_BITS_PER_UINT> 00550 or it can be even bigger then all bits will be set to 'c' 00551 00552 the value c will be set into the highest bits 00553 and the method returns state of the last moved bit 00554 */ 00555 uint Rcr (uint bits, uint c=0) 00556 { 00557 uint last_c = 0; 00558 uint rest_bits = bits; 00559 00560 if( bits == 0 ) 00561 return 0; 00562 00563 if( bits >= TTMATH_BITS_PER_UINT ) 00564 RcrMoveAllWords(rest_bits, last_c, bits, c); 00565 00566 if( rest_bits == 0 ) 00567 { 00568 TTMATH_LOG("UInt::Rcr") 00569 return last_c; 00570 } 00571 00572 // rest_bits is from 1 to TTMATH_BITS_PER_UINT-1 now 00573 if( rest_bits == 1 ) 00574 { 00575 last_c = Rcr2_one(c); 00576 } 00577 else if( rest_bits == 2 ) 00578 { 00579 // performance tests showed that for rest_bits==2 it's better to use Rcr2_one twice instead of Rcr2(2,c) 00580 Rcr2_one(c); 00581 last_c = Rcr2_one(c); 00582 } 00583 else 00584 { 00585 last_c = Rcr2(rest_bits, c); 00586 } 00587 00588 TTMATH_LOGC("UInt::Rcr", last_c) 00589 00590 return last_c; 00591 } 00592 00593 00594 /*! 00595 this method moves all bits into the left side 00596 (it returns value how many bits have been moved) 00597 */ 00598 uint CompensationToLeft () 00599 { 00600 uint moving = 0; 00601 00602 // a - index a last word which is different from zero 00603 sint a; 00604 for(a=value_size-1 ; a>=0 && table [a]==0 ; --a); 00605 00606 if( a < 0 ) 00607 return moving; // all words in table have zero 00608 00609 if( a != value_size-1 ) 00610 { 00611 moving += ( value_size-1 - a ) * TTMATH_BITS_PER_UINT; 00612 00613 // moving all words 00614 sint i; 00615 for(i=value_size-1 ; a>=0 ; --i, --a) 00616 table [i] = table [a]; 00617 00618 // setting the rest word to zero 00619 for(; i>=0 ; --i) 00620 table [i] = 0; 00621 } 00622 00623 uint moving2 = FindLeadingBitInWord ( table [value_size-1] ); 00624 // moving2 is different from -1 because the value table[value_size-1] 00625 // is not zero 00626 00627 moving2 = TTMATH_BITS_PER_UINT - moving2 - 1; 00628 Rcl (moving2); 00629 00630 TTMATH_LOG("UInt::CompensationToLeft") 00631 00632 return moving + moving2; 00633 } 00634 00635 00636 /*! 00637 this method looks for the highest set bit 00638 00639 result: 00640 if 'this' is not zero: 00641 return value - true 00642 'table_id' - the index of a word <0..value_size-1> 00643 'index' - the index of this set bit in the word <0..TTMATH_BITS_PER_UINT) 00644 00645 if 'this' is zero: 00646 return value - false 00647 both 'table_id' and 'index' are zero 00648 */ 00649 bool FindLeadingBit (uint & table_id, uint & index) const 00650 { 00651 for(table_id=value_size-1 ; table_id!=0 && table [table_id]==0 ; --table_id); 00652 00653 if( table_id==0 && table [table_id]==0 ) 00654 { 00655 // is zero 00656 index = 0; 00657 00658 return false; 00659 } 00660 00661 // table[table_id] is different from 0 00662 index = FindLeadingBitInWord ( table [table_id] ); 00663 00664 return true; 00665 } 00666 00667 00668 /*! 00669 this method looks for the smallest set bit 00670 00671 result: 00672 if 'this' is not zero: 00673 return value - true 00674 'table_id' - the index of a word <0..value_size-1> 00675 'index' - the index of this set bit in the word <0..TTMATH_BITS_PER_UINT) 00676 00677 if 'this' is zero: 00678 return value - false 00679 both 'table_id' and 'index' are zero 00680 */ 00681 bool FindLowestBit (uint & table_id, uint & index) const 00682 { 00683 for(table_id=0 ; table_id<value_size && table [table_id]==0 ; ++table_id); 00684 00685 if( table_id >= value_size ) 00686 { 00687 // is zero 00688 index = 0; 00689 table_id = 0; 00690 00691 return false; 00692 } 00693 00694 // table[table_id] is different from 0 00695 index = FindLowestBitInWord ( table[table_id] ); 00696 00697 return true; 00698 } 00699 00700 00701 /*! 00702 getting the 'bit_index' bit 00703 00704 bit_index bigger or equal zero 00705 */ 00706 uint GetBit (uint bit_index) const 00707 { 00708 TTMATH_ASSERT( bit_index < value_size * TTMATH_BITS_PER_UINT ) 00709 00710 uint index = bit_index / TTMATH_BITS_PER_UINT; 00711 uint bit = bit_index % TTMATH_BITS_PER_UINT; 00712 00713 uint temp = table [index]; 00714 uint res = SetBitInWord (temp, bit); 00715 00716 return res; 00717 } 00718 00719 00720 /*! 00721 setting the 'bit_index' bit 00722 and returning the last state of the bit 00723 00724 bit_index bigger or equal zero 00725 */ 00726 uint SetBit (uint bit_index) 00727 { 00728 TTMATH_ASSERT( bit_index < value_size * TTMATH_BITS_PER_UINT ) 00729 00730 uint index = bit_index / TTMATH_BITS_PER_UINT; 00731 uint bit = bit_index % TTMATH_BITS_PER_UINT; 00732 uint res = SetBitInWord (table [index], bit); 00733 00734 TTMATH_LOG("UInt::SetBit") 00735 00736 return res; 00737 } 00738 00739 00740 /*! 00741 this method performs a bitwise operation AND 00742 */ 00743 void BitAnd (const UInt<value_size> & ss2) 00744 { 00745 for(uint x=0 ; x<value_size ; ++x) 00746 table [x] &= ss2.table [x]; 00747 00748 TTMATH_LOG("UInt::BitAnd") 00749 } 00750 00751 00752 /*! 00753 this method performs a bitwise operation OR 00754 */ 00755 void BitOr (const UInt<value_size> & ss2) 00756 { 00757 for(uint x=0 ; x<value_size ; ++x) 00758 table [x] |= ss2.table [x]; 00759 00760 TTMATH_LOG("UInt::BitOr") 00761 } 00762 00763 00764 /*! 00765 this method performs a bitwise operation XOR 00766 */ 00767 void BitXor (const UInt<value_size> & ss2) 00768 { 00769 for(uint x=0 ; x<value_size ; ++x) 00770 table [x] ^= ss2.table [x]; 00771 00772 TTMATH_LOG("UInt::BitXor") 00773 } 00774 00775 00776 /*! 00777 this method performs a bitwise operation NOT 00778 */ 00779 void BitNot () 00780 { 00781 for(uint x=0 ; x<value_size ; ++x) 00782 table [x] = ~table [x]; 00783 00784 TTMATH_LOG("UInt::BitNot") 00785 } 00786 00787 00788 /*! 00789 this method performs a bitwise operation NOT but only 00790 on the range of <0, leading_bit> 00791 00792 for example: 00793 BitNot2(8) = BitNot2( 1000(bin) ) = 111(bin) = 7 00794 */ 00795 void BitNot2 () 00796 { 00797 uint table_id, index; 00798 00799 if( FindLeadingBit (table_id, index) ) 00800 { 00801 for(uint x=0 ; x<table_id ; ++x) 00802 table [x] = ~table [x]; 00803 00804 uint mask = TTMATH_UINT_MAX_VALUE; 00805 uint shift = TTMATH_BITS_PER_UINT - index - 1; 00806 00807 if(shift) 00808 mask >>= shift; 00809 00810 table [table_id] ^= mask; 00811 } 00812 else 00813 table [0] = 1; 00814 00815 00816 TTMATH_LOG("UInt::BitNot2") 00817 } 00818 00819 00820 00821 /*! 00822 * 00823 * Multiplication 00824 * 00825 * 00826 */ 00827 00828 public: 00829 00830 /*! 00831 multiplication: this = this * ss2 00832 00833 it can return a carry 00834 */ 00835 uint MulInt (uint ss2) 00836 { 00837 uint r1, r2, x1; 00838 uint c = 0; 00839 00840 UInt<value_size> u(*this); 00841 SetZero (); 00842 00843 if( ss2 == 0 ) 00844 { 00845 TTMATH_LOGC("UInt::MulInt(uint)", 0) 00846 return 0; 00847 } 00848 00849 for(x1=0 ; x1<value_size-1 ; ++x1) 00850 { 00851 MulTwoWords (u.table [x1], ss2, &r2, &r1); 00852 c += AddTwoInts (r2,r1,x1); 00853 } 00854 00855 // x1 = value_size-1 (last word) 00856 MulTwoWords (u.table [x1], ss2, &r2, &r1); 00857 c += (r2!=0) ? 1 : 0; 00858 c += AddInt (r1, x1); 00859 00860 TTMATH_LOGC("UInt::MulInt(uint)", c) 00861 00862 return (c==0)? 0 : 1; 00863 } 00864 00865 00866 /*! 00867 multiplication: result = this * ss2 00868 00869 we're using this method only when result_size is greater than value_size 00870 if so there will not be a carry 00871 */ 00872 template<uint result_size> 00873 void MulInt (uint ss2, UInt<result_size> & result) const 00874 { 00875 TTMATH_ASSERT( result_size > value_size ) 00876 00877 uint r2,r1; 00878 uint x1size=value_size; 00879 uint x1start=0; 00880 00881 result.SetZero (); 00882 00883 if( ss2 == 0 ) 00884 { 00885 TTMATH_VECTOR_LOG("UInt::MulInt(uint, UInt<>)", result.table , result_size) 00886 return; 00887 } 00888 00889 if( value_size > 2 ) 00890 { 00891 // if the value_size is smaller than or equal to 2 00892 // there is no sense to set x1size and x1start to another values 00893 00894 for(x1size=value_size ; x1size>0 && table [x1size-1]==0 ; --x1size); 00895 00896 if( x1size == 0 ) 00897 { 00898 TTMATH_VECTOR_LOG("UInt::MulInt(uint, UInt<>)", result.table , result_size) 00899 return; 00900 } 00901 00902 for(x1start=0 ; x1start<x1size && table[x1start]==0 ; ++x1start); 00903 } 00904 00905 for(uint x1=x1start ; x1<x1size ; ++x1) 00906 { 00907 MulTwoWords (table [x1], ss2, &r2, &r1 ); 00908 result.AddTwoInts (r2,r1,x1); 00909 } 00910 00911 TTMATH_VECTOR_LOG("UInt::MulInt(uint, UInt<>)", result.table , result_size) 00912 00913 return; 00914 } 00915 00916 00917 00918 /*! 00919 the multiplication 'this' = 'this' * ss2 00920 00921 algorithm: 100 - means automatically choose the fastest algorithm 00922 */ 00923 uint Mul (const UInt<value_size> & ss2, uint algorithm = 100) 00924 { 00925 switch( algorithm ) 00926 { 00927 case 1: 00928 return Mul1 (ss2); 00929 00930 case 2: 00931 return Mul2 (ss2); 00932 00933 case 3: 00934 return Mul3 (ss2); 00935 00936 case 100: 00937 default: 00938 return MulFastest (ss2); 00939 } 00940 } 00941 00942 00943 /*! 00944 the multiplication 'result' = 'this' * ss2 00945 00946 since the 'result' is twice bigger than 'this' and 'ss2' 00947 this method never returns a carry 00948 00949 algorithm: 100 - means automatically choose the fastest algorithm 00950 */ 00951 void MulBig (const UInt<value_size> & ss2, 00952 UInt<value_size*2> & result, 00953 uint algorithm = 100) 00954 { 00955 switch( algorithm ) 00956 { 00957 case 1: 00958 return Mul1Big (ss2, result); 00959 00960 case 2: 00961 return Mul2Big (ss2, result); 00962 00963 case 3: 00964 return Mul3Big (ss2, result); 00965 00966 case 100: 00967 default: 00968 return MulFastestBig (ss2, result); 00969 } 00970 } 00971 00972 00973 00974 /*! 00975 the first version of the multiplication algorithm 00976 */ 00977 00978 private: 00979 00980 /*! 00981 multiplication: this = this * ss2 00982 00983 it returns carry if it has been 00984 */ 00985 uint Mul1Ref(const UInt<value_size> & ss2) 00986 { 00987 TTMATH_REFERENCE_ASSERT( ss2 ) 00988 00989 UInt<value_size> ss1( *this ); 00990 SetZero (); 00991 00992 for(uint i=0; i < value_size*TTMATH_BITS_PER_UINT ; ++i) 00993 { 00994 if( Add (*this) ) 00995 { 00996 TTMATH_LOGC("UInt::Mul1", 1) 00997 return 1; 00998 } 00999 01000 if( ss1.Rcl (1) ) 01001 if( Add (ss2) ) 01002 { 01003 TTMATH_LOGC("UInt::Mul1", 1) 01004 return 1; 01005 } 01006 } 01007 01008 TTMATH_LOGC("UInt::Mul1 ", 0) 01009 01010 return 0; 01011 } 01012 01013 01014 public: 01015 01016 /*! 01017 multiplication: this = this * ss2 01018 can return carry 01019 */ 01020 uint Mul1(const UInt<value_size> & ss2) 01021 { 01022 if( this == &ss2 ) 01023 { 01024 UInt<value_size> copy_ss2(ss2); 01025 return Mul1Ref(copy_ss2); 01026 } 01027 else 01028 { 01029 return Mul1Ref(ss2); 01030 } 01031 } 01032 01033 01034 /*! 01035 multiplication: result = this * ss2 01036 01037 result is twice bigger than 'this' and 'ss2' 01038 this method never returns carry 01039 */ 01040 void Mul1Big (const UInt<value_size> & ss2_, UInt<value_size*2> & result) 01041 { 01042 UInt<value_size*2> ss2; 01043 uint i; 01044 01045 // copying *this into result and ss2_ into ss2 01046 for(i=0 ; i<value_size ; ++i) 01047 { 01048 result.table [i] = table [i]; 01049 ss2.table [i] = ss2_.table [i]; 01050 } 01051 01052 // cleaning the highest bytes in result and ss2 01053 for( ; i < value_size*2 ; ++i) 01054 { 01055 result.table [i] = 0; 01056 ss2.table [i] = 0; 01057 } 01058 01059 // multiply 01060 // (there will not be a carry) 01061 result.Mul1 ( ss2 ); 01062 01063 TTMATH_LOG("UInt::Mul1Big") 01064 } 01065 01066 01067 01068 /*! 01069 the second version of the multiplication algorithm 01070 01071 this algorithm is similar to the 'schoolbook method' which is done by hand 01072 */ 01073 01074 /*! 01075 multiplication: this = this * ss2 01076 01077 it returns carry if it has been 01078 */ 01079 uint Mul2 (const UInt<value_size> & ss2) 01080 { 01081 UInt<value_size*2> result; 01082 uint i, c = 0; 01083 01084 Mul2Big (ss2, result); 01085 01086 // copying result 01087 for(i=0 ; i<value_size ; ++i) 01088 table [i] = result.table [i]; 01089 01090 // testing carry 01091 for( ; i<value_size*2 ; ++i) 01092 if( result.table [i] != 0 ) 01093 { 01094 c = 1; 01095 break; 01096 } 01097 01098 TTMATH_LOGC("UInt::Mul2", c) 01099 01100 return c; 01101 } 01102 01103 01104 /*! 01105 multiplication: result = this * ss2 01106 01107 result is twice bigger than this and ss2 01108 this method never returns carry 01109 */ 01110 void Mul2Big (const UInt<value_size> & ss2, UInt<value_size*2> & result) 01111 { 01112 Mul2Big2<value_size>(table , ss2.table , result); 01113 01114 TTMATH_LOG("UInt::Mul2Big") 01115 } 01116 01117 01118 private: 01119 01120 /*! 01121 an auxiliary method for calculating the multiplication 01122 01123 arguments we're taking as pointers (this is to improve the Mul3Big2()- avoiding 01124 unnecessary copying objects), the result should be taken as a pointer too, 01125 but at the moment there is no method AddTwoInts() which can operate on pointers 01126 */ 01127 template<uint ss_size> 01128 void Mul2Big2(const uint * ss1, const uint * ss2, UInt<ss_size*2> & result) 01129 { 01130 uint x1size = ss_size, x2size = ss_size; 01131 uint x1start = 0, x2start = 0; 01132 01133 if( ss_size > 2 ) 01134 { 01135 // if the ss_size is smaller than or equal to 2 01136 // there is no sense to set x1size (and others) to another values 01137 01138 for(x1size=ss_size ; x1size>0 && ss1[x1size-1]==0 ; --x1size); 01139 for(x2size=ss_size ; x2size>0 && ss2[x2size-1]==0 ; --x2size); 01140 01141 for(x1start=0 ; x1start<x1size && ss1[x1start]==0 ; ++x1start); 01142 for(x2start=0 ; x2start<x2size && ss2[x2start]==0 ; ++x2start); 01143 } 01144 01145 Mul2Big3<ss_size>(ss1, ss2, result, x1start, x1size, x2start, x2size); 01146 } 01147 01148 01149 01150 /*! 01151 an auxiliary method for calculating the multiplication 01152 */ 01153 template<uint ss_size> 01154 void Mul2Big3(const uint * ss1, const uint * ss2, UInt<ss_size*2> & result, uint x1start, uint x1size, uint x2start, uint x2size) 01155 { 01156 uint r2, r1; 01157 01158 result.SetZero(); 01159 01160 if( x1size==0 || x2size==0 ) 01161 return; 01162 01163 for(uint x1=x1start ; x1<x1size ; ++x1) 01164 { 01165 for(uint x2=x2start ; x2<x2size ; ++x2) 01166 { 01167 MulTwoWords (ss1[x1], ss2[x2], &r2, &r1); 01168 result.AddTwoInts(r2, r1, x2+x1); 01169 // here will never be a carry 01170 } 01171 } 01172 } 01173 01174 01175 public: 01176 01177 01178 /*! 01179 multiplication: this = this * ss2 01180 01181 This is Karatsuba Multiplication algorithm, we're using it when value_size is greater than 01182 or equal to TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE macro (defined in ttmathuint.h). 01183 If value_size is smaller then we're using Mul2Big() instead. 01184 01185 Karatsuba multiplication: 01186 Assume we have: 01187 this = x = x1*B^m + x0 01188 ss2 = y = y1*B^m + y0 01189 where x0 and y0 are less than B^m 01190 the product from multiplication we can show as: 01191 x*y = (x1*B^m + x0)(y1*B^m + y0) = z2*B^(2m) + z1*B^m + z0 01192 where 01193 z2 = x1*y1 01194 z1 = x1*y0 + x0*y1 01195 z0 = x0*y0 01196 this is standard schoolbook algorithm with O(n^2), Karatsuba observed that z1 can be given in other form: 01197 z1 = (x1 + x0)*(y1 + y0) - z2 - z0 / z1 = (x1*y1 + x1*y0 + x0*y1 + x0*y0) - x1*y1 - x0*y0 = x1*y0 + x0*y1 / 01198 and to calculate the multiplication we need only three multiplications (with some additions and subtractions) 01199 01200 Our objects 'this' and 'ss2' we divide into two parts and by using recurrence we calculate the multiplication. 01201 Karatsuba multiplication has O( n^(ln(3)/ln(2)) ) 01202 */ 01203 uint Mul3 (const UInt<value_size> & ss2) 01204 { 01205 UInt<value_size*2> result; 01206 uint i, c = 0; 01207 01208 Mul3Big (ss2, result); 01209 01210 // copying result 01211 for(i=0 ; i<value_size ; ++i) 01212 table [i] = result.table [i]; 01213 01214 // testing carry 01215 for( ; i<value_size*2 ; ++i) 01216 if( result.table [i] != 0 ) 01217 { 01218 c = 1; 01219 break; 01220 } 01221 01222 TTMATH_LOGC("UInt::Mul3", c) 01223 01224 return c; 01225 } 01226 01227 01228 01229 /*! 01230 multiplication: result = this * ss2 01231 01232 result is twice bigger than this and ss2, 01233 this method never returns carry, 01234 (Karatsuba multiplication) 01235 */ 01236 void Mul3Big (const UInt<value_size> & ss2, UInt<value_size*2> & result) 01237 { 01238 Mul3Big2<value_size>(table , ss2.table , result.table ); 01239 01240 TTMATH_LOG("UInt::Mul3Big") 01241 } 01242 01243 01244 01245 private: 01246 01247 /*! 01248 an auxiliary method for calculating the Karatsuba multiplication 01249 01250 result_size is equal ss_size*2 01251 */ 01252 template<uint ss_size> 01253 void Mul3Big2(const uint * ss1, const uint * ss2, uint * result) 01254 { 01255 const uint * x1, * x0, * y1, * y0; 01256 01257 01258 if( ss_size>1 && ss_size<TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE ) 01259 { 01260 UInt<ss_size*2> res; 01261 Mul2Big2<ss_size>(ss1, ss2, res); 01262 01263 #ifdef __clang__ 01264 #pragma clang diagnostic push 01265 #pragma clang diagnostic ignored "-Wtautological-compare" 01266 #endif 01267 01268 for(uint i=0 ; i<ss_size*2 ; ++i) 01269 result[i] = res.table [i]; 01270 01271 #ifdef __clang__ 01272 #pragma clang diagnostic pop 01273 #endif 01274 01275 return; 01276 } 01277 else 01278 if( ss_size == 1 ) 01279 { 01280 return MulTwoWords (*ss1, *ss2, &result[1], &result[0]); 01281 } 01282 01283 01284 if( (ss_size & 1) == 1 ) 01285 { 01286 // ss_size is odd 01287 x0 = ss1; 01288 y0 = ss2; 01289 x1 = ss1 + ss_size / 2 + 1; 01290 y1 = ss2 + ss_size / 2 + 1; 01291 01292 // the second vectors (x1 and y1) are smaller about one from the first ones (x0 and y0) 01293 Mul3Big3<ss_size/2 + 1, ss_size/2, ss_size*2>(x1, x0, y1, y0, result); 01294 } 01295 else 01296 { 01297 // ss_size is even 01298 x0 = ss1; 01299 y0 = ss2; 01300 x1 = ss1 + ss_size / 2; 01301 y1 = ss2 + ss_size / 2; 01302 01303 // all four vectors (x0 x1 y0 y1) are equal in size 01304 Mul3Big3<ss_size/2, ss_size/2, ss_size*2>(x1, x0, y1, y0, result); 01305 } 01306 } 01307 01308 01309 01310 #ifdef _MSC_VER 01311 #pragma warning (disable : 4717) 01312 //warning C4717: recursive on all control paths, function will cause runtime stack overflow 01313 //we have the stop point in Mul3Big2() method 01314 #endif 01315 01316 01317 /*! 01318 an auxiliary method for calculating the Karatsuba multiplication 01319 01320 x = x1*B^m + x0 01321 y = y1*B^m + y0 01322 01323 first_size - is the size of vectors: x0 and y0 01324 second_size - is the size of vectors: x1 and y1 (can be either equal first_size or smaller about one from first_size) 01325 01326 x*y = (x1*B^m + x0)(y1*B^m + y0) = z2*B^(2m) + z1*B^m + z0 01327 where 01328 z0 = x0*y0 01329 z2 = x1*y1 01330 z1 = (x1 + x0)*(y1 + y0) - z2 - z0 01331 */ 01332 template<uint first_size, uint second_size, uint result_size> 01333 void Mul3Big3(const uint * x1, const uint * x0, const uint * y1, const uint * y0, uint * result) 01334 { 01335 uint i, c, xc, yc; 01336 01337 UInt<first_size> temp, temp2; 01338 UInt<first_size*3> z1; 01339 01340 // z0 and z2 we store directly in the result (we don't use any temporary variables) 01341 Mul3Big2<first_size>(x0, y0, result); // z0 01342 Mul3Big2<second_size>(x1, y1, result+first_size*2); // z2 01343 01344 // now we calculate z1 01345 // temp = (x0 + x1) 01346 // temp2 = (y0 + y1) 01347 // we're using temp and temp2 with UInt<first_size>, although there can be a carry but 01348 // we simple remember it in xc and yc (xc and yc can be either 0 or 1), 01349 // and (x0 + x1)*(y0 + y1) we calculate in this way (schoolbook algorithm): 01350 // 01351 // xc | temp 01352 // yc | temp2 01353 // -------------------- 01354 // (temp * temp2) 01355 // xc*temp2 | 01356 // yc*temp | 01357 // xc*yc | 01358 // ---------- z1 -------- 01359 // 01360 // and the result is never larger in size than 3*first_size 01361 01362 xc = AddVector (x0, x1, first_size, second_size, temp.table); 01363 yc = AddVector (y0, y1, first_size, second_size, temp2.table); 01364 01365 Mul3Big2<first_size>(temp.table, temp2.table, z1.table); 01366 01367 #ifdef __clang__ 01368 #pragma clang diagnostic push 01369 #pragma clang diagnostic ignored "-Wtautological-compare" 01370 #endif 01371 01372 // clearing the rest of z1 01373 for(i=first_size*2 ; i<first_size*3 ; ++i) 01374 z1.table[i] = 0; 01375 01376 #ifdef __clang__ 01377 #pragma clang diagnostic pop 01378 #endif 01379 01380 if( xc ) 01381 { 01382 c = AddVector (z1.table+first_size, temp2.table, first_size*3-first_size, first_size, z1.table+first_size); 01383 TTMATH_ASSERT( c==0 ) 01384 } 01385 01386 if( yc ) 01387 { 01388 c = AddVector (z1.table+first_size, temp.table, first_size*3-first_size, first_size, z1.table+first_size); 01389 TTMATH_ASSERT( c==0 ) 01390 } 01391 01392 01393 if( xc && yc ) 01394 { 01395 #ifdef __clang__ 01396 #pragma clang diagnostic push 01397 #pragma clang diagnostic ignored "-Wtautological-compare" 01398 #endif 01399 01400 for( i=first_size*2 ; i<first_size*3 ; ++i ) 01401 if( ++z1.table[i] != 0 ) 01402 break; // break if there was no carry 01403 01404 #ifdef __clang__ 01405 #pragma clang diagnostic pop 01406 #endif 01407 } 01408 01409 // z1 = z1 - z2 01410 c = SubVector (z1.table, result+first_size*2, first_size*3, second_size*2, z1.table); 01411 TTMATH_ASSERT(c==0) 01412 01413 // z1 = z1 - z0 01414 c = SubVector (z1.table , result, first_size*3, first_size*2, z1.table); 01415 TTMATH_ASSERT(c==0) 01416 01417 // here we've calculated the z1 01418 // now we're adding it to the result 01419 01420 if( first_size > second_size ) 01421 { 01422 uint z1_size = result_size - first_size; 01423 TTMATH_ASSERT( z1_size <= first_size*3 ) 01424 01425 #ifdef __clang__ 01426 #pragma clang diagnostic push 01427 #pragma clang diagnostic ignored "-Wtautological-compare" 01428 #endif 01429 01430 for(i=z1_size ; i<first_size*3 ; ++i) 01431 { 01432 TTMATH_ASSERT( z1.table[i] == 0 ) 01433 } 01434 01435 #ifdef __clang__ 01436 #pragma clang diagnostic pop 01437 #endif 01438 01439 c = AddVector (result+first_size, z1.table, result_size-first_size, z1_size, result+first_size); 01440 TTMATH_ASSERT(c==0) 01441 } 01442 else 01443 { 01444 c = AddVector (result+first_size, z1.table, result_size-first_size, first_size*3, result+first_size); 01445 TTMATH_ASSERT(c==0) 01446 } 01447 } 01448 01449 01450 01451 #ifdef _MSC_VER 01452 #pragma warning (default : 4717) 01453 #endif 01454 01455 01456 public: 01457 01458 01459 /*! 01460 multiplication this = this * ss2 01461 */ 01462 uint MulFastest (const UInt<value_size> & ss2) 01463 { 01464 UInt<value_size*2> result; 01465 uint i, c = 0; 01466 01467 MulFastestBig (ss2, result); 01468 01469 // copying result 01470 for(i=0 ; i<value_size ; ++i) 01471 table[i] = result.table [i]; 01472 01473 // testing carry 01474 for( ; i<value_size*2 ; ++i) 01475 if( result.table [i] != 0 ) 01476 { 01477 c = 1; 01478 break; 01479 } 01480 01481 TTMATH_LOGC("UInt::MulFastest", c) 01482 01483 return c; 01484 } 01485 01486 01487 /*! 01488 multiplication result = this * ss2 01489 01490 this method is trying to select the fastest algorithm 01491 (in the future this method can be improved) 01492 */ 01493 void MulFastestBig (const UInt<value_size> & ss2, UInt<value_size*2> & result) 01494 { 01495 if( value_size < TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE ) 01496 return Mul2Big (ss2, result); 01497 01498 uint x1size = value_size, x2size = value_size; 01499 uint x1start = 0, x2start = 0; 01500 01501 for(x1size=value_size ; x1size>0 && table[x1size-1]==0 ; --x1size); 01502 for(x2size=value_size ; x2size>0 && ss2.table [x2size-1]==0 ; --x2size); 01503 01504 if( x1size==0 || x2size==0 ) 01505 { 01506 // either 'this' or 'ss2' is equal zero - the result is zero too 01507 result.SetZero (); 01508 return; 01509 } 01510 01511 for(x1start=0 ; x1start<x1size && table[x1start]==0 ; ++x1start); 01512 for(x2start=0 ; x2start<x2size && ss2.table [x2start]==0 ; ++x2start); 01513 01514 uint distancex1 = x1size - x1start; 01515 uint distancex2 = x2size - x2start; 01516 01517 if( distancex1 < 3 || distancex2 < 3 ) 01518 // either 'this' or 'ss2' have only 2 (or 1) items different from zero (side by side) 01519 // (this condition in the future can be improved) 01520 return Mul2Big3<value_size>(table , ss2.table , result, x1start, x1size, x2start, x2size); 01521 01522 01523 // Karatsuba multiplication 01524 Mul3Big (ss2, result); 01525 01526 TTMATH_LOG("UInt::MulFastestBig") 01527 } 01528 01529 01530 /*! 01531 * 01532 * Division 01533 * 01534 * 01535 */ 01536 01537 public: 01538 01539 01540 /*! 01541 division by one unsigned word 01542 01543 returns 1 when divisor is zero 01544 */ 01545 uint DivInt (uint divisor, uint * remainder = 0) 01546 { 01547 if( divisor == 0 ) 01548 { 01549 if( remainder ) 01550 *remainder = 0; // this is for convenience, without it the compiler can report that 'remainder' is uninitialized 01551 01552 TTMATH_LOG("UInt::DivInt") 01553 01554 return 1; 01555 } 01556 01557 if( divisor == 1 ) 01558 { 01559 if( remainder ) 01560 *remainder = 0; 01561 01562 TTMATH_LOG("UInt::DivInt") 01563 01564 return 0; 01565 } 01566 01567 UInt<value_size> dividend(*this); 01568 SetZero (); 01569 01570 sint i; // i must be with a sign 01571 uint r = 0; 01572 01573 // we're looking for the last word in ss1 01574 for(i=value_size-1 ; i>0 && dividend.table [i]==0 ; --i); 01575 01576 for( ; i>=0 ; --i) 01577 DivTwoWords (r, dividend.table [i], divisor, &table[i], &r); 01578 01579 if( remainder ) 01580 *remainder = r; 01581 01582 TTMATH_LOG("UInt::DivInt") 01583 01584 return 0; 01585 } 01586 01587 uint DivInt (uint divisor, uint & remainder) 01588 { 01589 return DivInt (divisor, &remainder); 01590 } 01591 01592 01593 01594 /*! 01595 division this = this / ss2 01596 01597 return values: 01598 0 - ok 01599 1 - division by zero 01600 'this' will be the quotient 01601 'remainder' - remainder 01602 */ 01603 uint Div ( const UInt<value_size> & divisor, 01604 UInt<value_size> * remainder = 0, 01605 uint algorithm = 3) 01606 { 01607 switch( algorithm ) 01608 { 01609 case 1: 01610 return Div1 (divisor, remainder); 01611 01612 case 2: 01613 return Div2 (divisor, remainder); 01614 01615 case 3: 01616 default: 01617 return Div3 (divisor, remainder); 01618 } 01619 } 01620 01621 uint Div (const UInt<value_size> & divisor, UInt<value_size> & remainder, uint algorithm = 3) 01622 { 01623 return Div (divisor, &remainder, algorithm); 01624 } 01625 01626 01627 01628 private: 01629 01630 /*! 01631 return values: 01632 0 - none has to be done 01633 1 - division by zero 01634 2 - division should be made 01635 */ 01636 uint Div_StandardTest( const UInt<value_size> & v, 01637 uint & m, uint & n, 01638 UInt<value_size> * remainder = 0) 01639 { 01640 switch( Div_CalculatingSize(v, m, n) ) 01641 { 01642 case 4: // 'this' is equal v 01643 if( remainder ) 01644 remainder->SetZero(); 01645 01646 SetOne (); 01647 TTMATH_LOG("UInt::Div_StandardTest") 01648 return 0; 01649 01650 case 3: // 'this' is smaller than v 01651 if( remainder ) 01652 *remainder = *this; 01653 01654 SetZero (); 01655 TTMATH_LOG("UInt ::Div_StandardTest") 01656 return 0; 01657 01658 case 2: // 'this' is zero 01659 if( remainder ) 01660 remainder->SetZero (); 01661 01662 SetZero(); 01663 TTMATH_LOG("UInt ::Div_StandardTest") 01664 return 0; 01665 01666 case 1: // v is zero 01667 TTMATH_LOG("UInt ::Div_StandardTest") 01668 return 1; 01669 } 01670 01671 TTMATH_LOG("UInt ::Div_StandardTest") 01672 01673 return 2; 01674 } 01675 01676 01677 01678 /*! 01679 return values: 01680 0 - ok 01681 'm' - is the index (from 0) of last non-zero word in table ('this') 01682 'n' - is the index (from 0) of last non-zero word in v.table 01683 1 - v is zero 01684 2 - 'this' is zero 01685 3 - 'this' is smaller than v 01686 4 - 'this' is equal v 01687 01688 if the return value is different than zero the 'm' and 'n' are undefined 01689 */ 01690 uint Div_CalculatingSize(const UInt <value_size> & v, uint & m, uint & n) 01691 { 01692 m = n = value_size-1; 01693 01694 for( ; n!=0 && v.table[n]==0 ; --n); 01695 01696 if( n==0 && v.table[n]==0 ) 01697 return 1; 01698 01699 for( ; m!=0 && table[m]==0 ; --m); 01700 01701 if( m==0 && table[m]==0 ) 01702 return 2; 01703 01704 if( m < n ) 01705 return 3; 01706 else 01707 if( m == n ) 01708 { 01709 uint i; 01710 for(i = n ; i!=0 && table[i]==v.table[i] ; --i); 01711 01712 if( table[i] < v.table[i] ) 01713 return 3; 01714 else 01715 if (table[i] == v.table[i] ) 01716 return 4; 01717 } 01718 01719 return 0; 01720 } 01721 01722 01723 public: 01724 01725 /*! 01726 the first division algorithm 01727 radix 2 01728 */ 01729 uint Div1 (const UInt<value_size> & divisor, UInt<value_size> * remainder = 0) 01730 { 01731 uint m,n, test; 01732 01733 test = Div_StandardTest(divisor, m, n, remainder); 01734 if( test < 2 ) 01735 return test; 01736 01737 if( !remainder ) 01738 { 01739 UInt<value_size> rem; 01740 01741 return Div1_Calculate(divisor, rem); 01742 } 01743 01744 return Div1_Calculate(divisor, *remainder); 01745 } 01746 01747 01748 /*! 01749 the first division algorithm 01750 radix 2 01751 */ 01752 uint Div1 (const UInt<value_size> & divisor, UInt<value_size> & remainder) 01753 { 01754 return Div1 (divisor, &remainder); 01755 } 01756 01757 01758 private: 01759 01760 uint Div1_Calculate(const UInt<value_size> & divisor, UInt<value_size> & rest) 01761 { 01762 if( this == &divisor ) 01763 { 01764 UInt<value_size> divisor_copy(divisor); 01765 return Div1_CalculateRef(divisor_copy, rest); 01766 } 01767 else 01768 { 01769 return Div1_CalculateRef(divisor, rest); 01770 } 01771 } 01772 01773 01774 uint Div1_CalculateRef(const UInt<value_size> & divisor, UInt<value_size> & rest) 01775 { 01776 TTMATH_REFERENCE_ASSERT( divisor ) 01777 01778 sint loop; 01779 sint c; 01780 01781 rest.SetZero(); 01782 loop = value_size * TTMATH_BITS_PER_UINT; 01783 c = 0; 01784 01785 01786 div_a: 01787 c = Rcl (1, c); 01788 c = rest.Add (rest,c); 01789 c = rest.Sub (divisor,c); 01790 01791 c = !c; 01792 01793 if(!c) 01794 goto div_d; 01795 01796 01797 div_b: 01798 --loop; 01799 if(loop) 01800 goto div_a; 01801 01802 c = Rcl(1, c); 01803 TTMATH_LOG("UInt ::Div1_Calculate") 01804 return 0; 01805 01806 01807 div_c: 01808 c = Rcl(1, c); 01809 c = rest.Add (rest,c); 01810 c = rest.Add (divisor); 01811 01812 if(c) 01813 goto div_b; 01814 01815 01816 div_d: 01817 --loop; 01818 if(loop) 01819 goto div_c; 01820 01821 c = Rcl(1, c); 01822 c = rest.Add (divisor); 01823 01824 TTMATH_LOG("UInt ::Div1_Calculate") 01825 01826 return 0; 01827 } 01828 01829 01830 public: 01831 01832 /*! 01833 the second division algorithm 01834 01835 return values: 01836 0 - ok 01837 1 - division by zero 01838 */ 01839 uint Div2 (const UInt<value_size> & divisor, UInt<value_size> * remainder = 0) 01840 { 01841 if( this == &divisor ) 01842 { 01843 UInt<value_size> divisor_copy(divisor); 01844 return Div2Ref(divisor_copy, remainder); 01845 } 01846 else 01847 { 01848 return Div2Ref(divisor, remainder); 01849 } 01850 } 01851 01852 01853 /*! 01854 the second division algorithm 01855 01856 return values: 01857 0 - ok 01858 1 - division by zero 01859 */ 01860 uint Div2 (const UInt<value_size> & divisor, UInt<value_size> & remainder) 01861 { 01862 return Div2 (divisor, &remainder); 01863 } 01864 01865 01866 private: 01867 01868 /*! 01869 the second division algorithm 01870 01871 return values: 01872 0 - ok 01873 1 - division by zero 01874 */ 01875 uint Div2Ref(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0) 01876 { 01877 uint bits_diff; 01878 uint status = Div2_Calculate(divisor, remainder, bits_diff); 01879 if( status < 2 ) 01880 return status; 01881 01882 if( CmpBiggerEqual (divisor) ) 01883 { 01884 Div2 (divisor, remainder); 01885 SetBit (bits_diff); 01886 } 01887 else 01888 { 01889 if( remainder ) 01890 *remainder = *this; 01891 01892 SetZero (); 01893 SetBit (bits_diff); 01894 } 01895 01896 TTMATH_LOG("UInt::Div2") 01897 01898 return 0; 01899 } 01900 01901 01902 /*! 01903 return values: 01904 0 - we've calculated the division 01905 1 - division by zero 01906 2 - we have to still calculate 01907 01908 */ 01909 uint Div2_Calculate(const UInt <value_size> & divisor, UInt <value_size> * remainder, 01910 uint & bits_diff) 01911 { 01912 uint table_id, index; 01913 uint divisor_table_id, divisor_index; 01914 01915 uint status = Div2_FindLeadingBitsAndCheck( divisor, remainder, 01916 table_id, index, 01917 divisor_table_id, divisor_index); 01918 01919 if( status < 2 ) 01920 { 01921 TTMATH_LOG("UInt::Div2_Calculate") 01922 return status; 01923 } 01924 01925 // here we know that 'this' is greater than divisor 01926 // then 'index' is greater or equal 'divisor_index' 01927 bits_diff = index - divisor_index; 01928 01929 UInt <value_size> divisor_copy(divisor); 01930 divisor_copy.Rcl (bits_diff, 0); 01931 01932 if( CmpSmaller (divisor_copy, table_id) ) 01933 { 01934 divisor_copy.Rcr(1); 01935 --bits_diff; 01936 } 01937 01938 Sub (divisor_copy, 0); 01939 01940 TTMATH_LOG("UInt::Div2_Calculate") 01941 01942 return 2; 01943 } 01944 01945 01946 /*! 01947 return values: 01948 0 - we've calculated the division 01949 1 - division by zero 01950 2 - we have to still calculate 01951 */ 01952 uint Div2_FindLeadingBitsAndCheck( const UInt <value_size> & divisor, 01953 UInt <value_size> * remainder, 01954 uint & table_id, uint & index, 01955 uint & divisor_table_id, uint & divisor_index) 01956 { 01957 if( !divisor.FindLeadingBit(divisor_table_id, divisor_index) ) 01958 { 01959 // division by zero 01960 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck") 01961 return 1; 01962 } 01963 01964 if( !FindLeadingBit (table_id, index) ) 01965 { 01966 // zero is divided by something 01967 01968 SetZero (); 01969 01970 if( remainder ) 01971 remainder->SetZero(); 01972 01973 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck") 01974 01975 return 0; 01976 } 01977 01978 divisor_index += divisor_table_id * TTMATH_BITS_PER_UINT; 01979 index += table_id * TTMATH_BITS_PER_UINT; 01980 01981 if( divisor_table_id == 0 ) 01982 { 01983 // dividor has only one 32-bit word 01984 01985 uint r; 01986 DivInt (divisor.table[0], &r); 01987 01988 if( remainder ) 01989 { 01990 remainder->SetZero(); 01991 remainder->table[0] = r; 01992 } 01993 01994 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck") 01995 01996 return 0; 01997 } 01998 01999 02000 if( Div2_DivisorGreaterOrEqual( divisor, remainder, 02001 table_id, index, 02002 divisor_index) ) 02003 { 02004 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck") 02005 return 0; 02006 } 02007 02008 02009 TTMATH_LOG("UInt ::Div2_FindLeadingBitsAndCheck") 02010 02011 return 2; 02012 } 02013 02014 02015 /*! 02016 return values: 02017 true if divisor is equal or greater than 'this' 02018 */ 02019 bool Div2_DivisorGreaterOrEqual( const UInt <value_size> & divisor, 02020 UInt <value_size> * remainder, 02021 uint table_id, uint index, 02022 uint divisor_index ) 02023 { 02024 if( divisor_index > index ) 02025 { 02026 // divisor is greater than this 02027 02028 if( remainder ) 02029 *remainder = *this; 02030 02031 SetZero (); 02032 02033 TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual") 02034 02035 return true; 02036 } 02037 02038 if( divisor_index == index ) 02039 { 02040 // table_id == divisor_table_id as well 02041 02042 uint i; 02043 for(i = table_id ; i!=0 && table[i]==divisor.table[i] ; --i); 02044 02045 if( table[i] < divisor.table[i] ) 02046 { 02047 // divisor is greater than 'this' 02048 02049 if( remainder ) 02050 *remainder = *this; 02051 02052 SetZero (); 02053 02054 TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual") 02055 02056 return true; 02057 } 02058 else 02059 if( table[i] == divisor.table[i] ) 02060 { 02061 // divisor is equal 'this' 02062 02063 if( remainder ) 02064 remainder->SetZero(); 02065 02066 SetOne (); 02067 02068 TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual") 02069 02070 return true; 02071 } 02072 } 02073 02074 TTMATH_LOG("UInt ::Div2_DivisorGreaterOrEqual") 02075 02076 return false; 02077 } 02078 02079 02080 public: 02081 02082 /*! 02083 the third division algorithm 02084 */ 02085 uint Div3 (const UInt<value_size> & ss2, UInt<value_size> * remainder = 0) 02086 { 02087 if( this == &ss2 ) 02088 { 02089 UInt<value_size> copy_ss2(ss2); 02090 return Div3Ref(copy_ss2, remainder); 02091 } 02092 else 02093 { 02094 return Div3Ref(ss2, remainder); 02095 } 02096 } 02097 02098 02099 /*! 02100 the third division algorithm 02101 */ 02102 uint Div3 (const UInt<value_size> & ss2, UInt<value_size> & remainder) 02103 { 02104 return Div3 (ss2, &remainder); 02105 } 02106 02107 02108 private: 02109 02110 /*! 02111 the third division algorithm 02112 02113 this algorithm is described in the following book: 02114 "The art of computer programming 2" (4.3.1 page 272) 02115 Donald E. Knuth 02116 !! give the description here (from the book) 02117 */ 02118 uint Div3Ref(const UInt<value_size> & v, UInt<value_size> * remainder = 0) 02119 { 02120 uint m,n, test; 02121 02122 test = Div_StandardTest(v, m, n, remainder); 02123 if( test < 2 ) 02124 return test; 02125 02126 if( n == 0 ) 02127 { 02128 uint r; 02129 DivInt ( v.table [0], &r ); 02130 02131 if( remainder ) 02132 { 02133 remainder->SetZero(); 02134 remainder->table[0] = r; 02135 } 02136 02137 TTMATH_LOG("UInt::Div3") 02138 02139 return 0; 02140 } 02141 02142 02143 // we can only use the third division algorithm when 02144 // the divisor is greater or equal 2^32 (has more than one 32-bit word) 02145 ++m; 02146 ++n; 02147 m = m - n; 02148 Div3_Division(v, remainder, m, n); 02149 02150 TTMATH_LOG("UInt ::Div3 ") 02151 02152 return 0; 02153 } 02154 02155 02156 02157 private: 02158 02159 02160 void Div3_Division(UInt <value_size> v, UInt <value_size> * remainder, uint m, uint n) 02161 { 02162 TTMATH_ASSERT( n>=2 ) 02163 02164 UInt <value_size+1> uu, vv; 02165 UInt <value_size> q; 02166 uint d, u_value_size, u0, u1, u2, v1, v0, j=m; 02167 02168 u_value_size = Div3_Normalize(v, n, d); 02169 02170 if( j+n == value_size ) 02171 u2 = u_value_size; 02172 else 02173 u2 = table[j+n]; 02174 02175 Div3_MakeBiggerV(v, vv); 02176 02177 for(uint i = j+1 ; i<value_size ; ++i) 02178 q.table[i] = 0; 02179 02180 while( true ) 02181 { 02182 u1 = table[j+n-1]; 02183 u0 = table[j+n-2]; 02184 v1 = v.table[n-1]; 02185 v0 = v.table[n-2]; 02186 02187 uint qp = Div3_Calculate(u2,u1,u0, v1,v0); 02188 02189 Div3_MakeNewU(uu, j, n, u2); 02190 Div3_MultiplySubtract(uu, vv, qp); 02191 Div3_CopyNewU(uu, j, n); 02192 02193 q.table[j] = qp; 02194 02195 // the next loop 02196 if( j-- == 0 ) 02197 break; 02198 02199 u2 = table[j+n]; 02200 } 02201 02202 if( remainder ) 02203 Div3_Unnormalize(remainder, n, d); 02204 02205 *this = q; 02206 02207 TTMATH_LOG("UInt::Div3_Division") 02208 } 02209 02210 02211 void Div3_MakeNewU(UInt<value_size+1> & uu, uint j, uint n, uint u_max) 02212 { 02213 uint i; 02214 02215 for(i=0 ; i<n ; ++i, ++j) 02216 uu.table[i] = table[j]; 02217 02218 // 'n' is from <1..value_size> so and 'i' is from <0..value_size> 02219 // then table[i] is always correct (look at the declaration of 'uu') 02220 uu.table[i] = u_max; 02221 02222 for( ++i ; i<value_size+1 ; ++i) 02223 uu.table[i] = 0; 02224 02225 TTMATH_LOG("UInt::Div3_MakeNewU") 02226 } 02227 02228 02229 void Div3_CopyNewU(const UInt<value_size+1> & uu, uint j, uint n) 02230 { 02231 uint i; 02232 02233 for(i=0 ; i<n ; ++i) 02234 table[i+j] = uu.table[i]; 02235 02236 if( i+j < value_size ) 02237 table[i+j] = uu.table[i]; 02238 02239 TTMATH_LOG("UInt::Div3_CopyNewU") 02240 } 02241 02242 02243 /*! 02244 we're making the new 'vv' 02245 the value is actually the same but the 'table' is bigger (value_size+1) 02246 */ 02247 void Div3_MakeBiggerV(const UInt<value_size> & v, UInt<value_size+1> & vv) 02248 { 02249 for(uint i=0 ; i<value_size ; ++i) 02250 vv.table[i] = v.table[i]; 02251 02252 vv.table[value_size] = 0; 02253 02254 TTMATH_LOG("UInt::Div3_MakeBiggerV") 02255 } 02256 02257 02258 /*! 02259 we're moving all bits from 'v' into the left side of the n-1 word 02260 (the highest bit at v.table[n-1] will be equal one, 02261 the bits from 'this' we're moving the same times as 'v') 02262 02263 return values: 02264 d - how many times we've moved 02265 return - the next-left value from 'this' (that after table[value_size-1]) 02266 */ 02267 uint Div3_Normalize(UInt<value_size> & v, uint n, uint & d) 02268 { 02269 // v.table[n-1] is != 0 02270 02271 uint bit = (uint )FindLeadingBitInWord (v.table[n-1]); 02272 uint move = (TTMATH_BITS_PER_UINT - bit - 1); 02273 uint res = table[value_size-1]; 02274 d = move; 02275 02276 if( move > 0 ) 02277 { 02278 v.Rcl (move, 0); 02279 Rcl (move, 0); 02280 res = res >> (bit + 1); 02281 } 02282 else 02283 { 02284 res = 0; 02285 } 02286 02287 TTMATH_LOG("UInt::Div3_Normalize") 02288 02289 return res; 02290 } 02291 02292 02293 void Div3_Unnormalize(UInt <value_size> * remainder, uint n, uint d) 02294 { 02295 for(uint i=n ; i<value_size ; ++i) 02296 table[i] = 0; 02297 02298 Rcr (d,0); 02299 02300 *remainder = *this; 02301 02302 TTMATH_LOG("UInt::Div3_Unnormalize") 02303 } 02304 02305 02306 uint Div3_Calculate(uint u2, uint u1, uint u0, uint v1, uint v0) 02307 { 02308 UInt<2> u_temp; 02309 uint rp; 02310 bool next_test; 02311 02312 TTMATH_ASSERT( v1 != 0 ) 02313 02314 u_temp.table[1] = u2; 02315 u_temp.table[0] = u1; 02316 u_temp.DivInt (v1, &rp); 02317 02318 TTMATH_ASSERT( u_temp.table[1]==0 || u_temp.table[1]==1 ) 02319 02320 do 02321 { 02322 bool decrease = false; 02323 02324 if( u_temp.table[1] == 1 ) 02325 decrease = true; 02326 else 02327 { 02328 UInt<2> temp1, temp2; 02329 02330 UInt<2>::MulTwoWords (u_temp.table[0], v0, temp1.table+1, temp1.table); 02331 temp2.table[1] = rp; 02332 temp2.table[0] = u0; 02333 02334 if( temp1 > temp2 ) 02335 decrease = true; 02336 } 02337 02338 next_test = false; 02339 02340 if( decrease ) 02341 { 02342 u_temp.SubOne(); 02343 02344 rp += v1; 02345 02346 if( rp >= v1 ) // it means that there wasn't a carry (r<b from the book) 02347 next_test = true; 02348 } 02349 } 02350 while( next_test ); 02351 02352 TTMATH_LOG("UInt::Div3_Calculate") 02353 02354 return u_temp.table[0]; 02355 } 02356 02357 02358 02359 void Div3_MultiplySubtract( UInt <value_size+1> & uu, 02360 const UInt <value_size+1> & vv, uint & qp) 02361 { 02362 // D4 (in the book) 02363 02364 UInt<value_size+1> vv_temp(vv); 02365 vv_temp.MulInt(qp); 02366 02367 if( uu.Sub(vv_temp) ) 02368 { 02369 // there was a carry 02370 02371 // 02372 // !!! this part of code was not tested 02373 // 02374 02375 --qp; 02376 uu.Add(vv); 02377 02378 // can be a carry from this additions but it should be ignored 02379 // because it cancels with the borrow from uu.Sub(vv_temp) 02380 } 02381 02382 TTMATH_LOG("UInt::Div3_MultiplySubtract") 02383 } 02384 02385 02386 02387 02388 02389 02390 public: 02391 02392 02393 /*! 02394 power this = this ^ pow 02395 binary algorithm (r-to-l) 02396 02397 return values: 02398 0 - ok 02399 1 - carry 02400 2 - incorrect argument (0^0) 02401 */ 02402 uint Pow (UInt<value_size> pow) 02403 { 02404 if(pow.IsZero () && IsZero ()) 02405 // we don't define zero^zero 02406 return 2; 02407 02408 UInt<value_size> start(*this); 02409 UInt<value_size> result; 02410 result.SetOne (); 02411 uint c = 0; 02412 02413 while( !c ) 02414 { 02415 if( pow.table [0] & 1 ) 02416 c += result.Mul (start); 02417 02418 pow.Rcr2_one(0); 02419 if( pow.IsZero () ) 02420 break; 02421 02422 c += start.Mul (start); 02423 } 02424 02425 *this = result; 02426 02427 TTMATH_LOGC("UInt::Pow(UInt<>)", c) 02428 02429 return (c==0)? 0 : 1; 02430 } 02431 02432 02433 /*! 02434 square root 02435 e.g. Sqrt(9) = 3 02436 ('digit-by-digit' algorithm) 02437 */ 02438 void Sqrt () 02439 { 02440 UInt<value_size> bit, temp; 02441 02442 if( IsZero () ) 02443 return; 02444 02445 UInt<value_size> value(*this); 02446 02447 SetZero (); 02448 bit.SetZero (); 02449 bit.table [value_size-1] = (TTMATH_UINT_HIGHEST_BIT >> 1); 02450 02451 while( bit > value ) 02452 bit.Rcr (2); 02453 02454 while( !bit.IsZero () ) 02455 { 02456 temp = *this; 02457 temp.Add (bit); 02458 02459 if( value >= temp ) 02460 { 02461 value.Sub (temp); 02462 Rcr (1); 02463 Add (bit); 02464 } 02465 else 02466 { 02467 Rcr (1); 02468 } 02469 02470 bit.Rcr (2); 02471 } 02472 02473 TTMATH_LOG("UInt::Sqrt") 02474 } 02475 02476 02477 02478 /*! 02479 this method sets n first bits to value zero 02480 02481 For example: 02482 let n=2 then if there's a value 111 (bin) there'll be '100' (bin) 02483 */ 02484 void ClearFirstBits (uint n) 02485 { 02486 if( n >= value_size*TTMATH_BITS_PER_UINT ) 02487 { 02488 SetZero (); 02489 TTMATH_LOG("UInt::ClearFirstBits") 02490 return; 02491 } 02492 02493 uint * p = table ; 02494 02495 // first we're clearing the whole words 02496 while( n >= TTMATH_BITS_PER_UINT ) 02497 { 02498 *p++ = 0; 02499 n -= TTMATH_BITS_PER_UINT; 02500 } 02501 02502 if( n == 0 ) 02503 { 02504 TTMATH_LOG("UInt::ClearFirstBits") 02505 return; 02506 } 02507 02508 // and then we're clearing one word which has left 02509 // mask -- all bits are set to one 02510 uint mask = TTMATH_UINT_MAX_VALUE; 02511 02512 mask = mask << n; 02513 02514 (*p) &= mask; 02515 02516 TTMATH_LOG("UInt::ClearFirstBits") 02517 } 02518 02519 02520 /*! 02521 this method returns true if the highest bit of the value is set 02522 */ 02523 bool IsTheHighestBitSet () const 02524 { 02525 return (table[value_size-1] & TTMATH_UINT_HIGHEST_BIT) != 0; 02526 } 02527 02528 02529 /*! 02530 this method returns true if the lowest bit of the value is set 02531 */ 02532 bool IsTheLowestBitSet () const 02533 { 02534 return (*table & 1) != 0; 02535 } 02536 02537 02538 /*! 02539 returning true if only the highest bit is set 02540 */ 02541 bool IsOnlyTheHighestBitSet () const 02542 { 02543 #ifdef __clang__ 02544 #pragma clang diagnostic push 02545 #pragma clang diagnostic ignored "-Wtautological-compare" 02546 #endif 02547 02548 for(uint i=0 ; i<value_size-1 ; ++i) 02549 if( table[i] != 0 ) 02550 return false; 02551 02552 #ifdef __clang__ 02553 #pragma clang diagnostic pop 02554 #endif 02555 if( table[value_size-1] != TTMATH_UINT_HIGHEST_BIT ) 02556 return false; 02557 02558 return true; 02559 } 02560 02561 02562 /*! 02563 returning true if only the lowest bit is set 02564 */ 02565 bool IsOnlyTheLowestBitSet () const 02566 { 02567 if( table[0] != 1 ) 02568 return false; 02569 02570 for(uint i=1 ; i<value_size ; ++i) 02571 if( table[i] != 0 ) 02572 return false; 02573 02574 return true; 02575 } 02576 02577 02578 /*! 02579 this method returns true if the value is equal zero 02580 */ 02581 bool IsZero () const 02582 { 02583 for(uint i=0 ; i<value_size ; ++i) 02584 if(table[i] != 0) 02585 return false; 02586 02587 return true; 02588 } 02589 02590 02591 /*! 02592 returning true if first 'bits' bits are equal zero 02593 */ 02594 bool AreFirstBitsZero (uint bits) const 02595 { 02596 TTMATH_ASSERT( bits <= value_size * TTMATH_BITS_PER_UINT ) 02597 02598 uint index = bits / TTMATH_BITS_PER_UINT; 02599 uint rest = bits % TTMATH_BITS_PER_UINT; 02600 uint i; 02601 02602 for(i=0 ; i<index ; ++i) 02603 if(table[i] != 0 ) 02604 return false; 02605 02606 if( rest == 0 ) 02607 return true; 02608 02609 uint mask = TTMATH_UINT_MAX_VALUE >> (TTMATH_BITS_PER_UINT - rest); 02610 02611 return (table[i] & mask) == 0; 02612 } 02613 02614 02615 02616 /*! 02617 * 02618 * conversion methods 02619 * 02620 */ 02621 02622 02623 02624 /*! 02625 this method converts an UInt<another_size> type to this class 02626 02627 this operation has mainly sense if the value from p is 02628 equal or smaller than that one which is returned from UInt<value_size>::SetMax() 02629 02630 it returns a carry if the value 'p' is too big 02631 */ 02632 template<uint argument_size> 02633 uint FromUInt (const UInt<argument_size> & p) 02634 { 02635 uint min_size = (value_size < argument_size)? value_size : argument_size; 02636 uint i; 02637 02638 for(i=0 ; i<min_size ; ++i) 02639 table[i] = p.table [i]; 02640 02641 02642 if( value_size > argument_size ) 02643 { 02644 // 'this' is longer than 'p' 02645 02646 for( ; i<value_size ; ++i) 02647 table[i] = 0; 02648 } 02649 else 02650 { 02651 for( ; i<argument_size ; ++i) 02652 if( p.table [i] != 0 ) 02653 { 02654 TTMATH_LOGC("UInt::FromUInt(UInt<>)", 1) 02655 return 1; 02656 } 02657 } 02658 02659 TTMATH_LOGC("UInt::FromUInt(UInt<>)", 0) 02660 02661 return 0; 02662 } 02663 02664 02665 /*! 02666 this method converts an UInt<another_size> type to this class 02667 02668 this operation has mainly sense if the value from p is 02669 equal or smaller than that one which is returned from UInt<value_size>::SetMax() 02670 02671 it returns a carry if the value 'p' is too big 02672 */ 02673 template<uint argument_size> 02674 uint FromInt (const UInt<argument_size> & p) 02675 { 02676 return FromUInt (p); 02677 } 02678 02679 02680 /*! 02681 this method converts the uint type to this class 02682 */ 02683 uint FromUInt (uint value) 02684 { 02685 for(uint i=1 ; i<value_size ; ++i) 02686 table[i] = 0; 02687 02688 table[0] = value; 02689 02690 TTMATH_LOG("UInt::FromUInt(uint)") 02691 02692 // there'll never be a carry here 02693 return 0; 02694 } 02695 02696 02697 /*! 02698 this method converts the uint type to this class 02699 */ 02700 uint FromInt (uint value) 02701 { 02702 return FromUInt (value); 02703 } 02704 02705 02706 /*! 02707 this method converts the sint type to this class 02708 */ 02709 uint FromInt (sint value) 02710 { 02711 uint c = FromUInt (uint (value)); 02712 02713 if( c || value < 0 ) 02714 return 1; 02715 02716 return 0; 02717 } 02718 02719 02720 /*! 02721 this operator converts an UInt<another_size> type to this class 02722 02723 it doesn't return a carry 02724 */ 02725 template<uint argument_size> 02726 UInt<value_size> & operator= (const UInt<argument_size> & p) 02727 { 02728 FromUInt (p); 02729 02730 return *this; 02731 } 02732 02733 02734 /*! 02735 the assignment operator 02736 */ 02737 UInt<value_size> & operator= (const UInt<value_size> & p) 02738 { 02739 for(uint i=0 ; i<value_size ; ++i) 02740 table[i] = p.table [i]; 02741 02742 TTMATH_LOG("UInt::operator=(UInt<>)") 02743 02744 return *this; 02745 } 02746 02747 02748 /*! 02749 this method converts the uint type to this class 02750 */ 02751 UInt<value_size> & operator= (uint i) 02752 { 02753 FromUInt (i); 02754 02755 return *this; 02756 } 02757 02758 02759 /*! 02760 a constructor for converting the uint to this class 02761 */ 02762 UInt (uint i) 02763 { 02764 FromUInt (i); 02765 } 02766 02767 02768 /*! 02769 this method converts the sint type to this class 02770 */ 02771 UInt<value_size> & operator= (sint i) 02772 { 02773 FromInt (i); 02774 02775 return *this; 02776 } 02777 02778 02779 /*! 02780 a constructor for converting the sint to this class 02781 02782 look at the description of UInt::operator=(sint) 02783 */ 02784 UInt (sint i) 02785 { 02786 FromInt (i); 02787 } 02788 02789 02790 #ifdef TTMATH_PLATFORM32 02791 02792 02793 /*! 02794 this method converts unsigned 64 bit int type to this class 02795 ***this method is created only on a 32bit platform*** 02796 */ 02797 uint FromUInt (ulint n) 02798 { 02799 table[0] = (uint )n; 02800 02801 if( value_size == 1 ) 02802 { 02803 uint c = ((n >> TTMATH_BITS_PER_UINT) == 0) ? 0 : 1; 02804 02805 TTMATH_LOGC("UInt::FromUInt(ulint)", c) 02806 return c; 02807 } 02808 02809 table[1] = (uint )(n >> TTMATH_BITS_PER_UINT); 02810 02811 for(uint i=2 ; i<value_size ; ++i) 02812 table[i] = 0; 02813 02814 TTMATH_LOG("UInt::FromUInt(ulint)") 02815 02816 return 0; 02817 } 02818 02819 02820 /*! 02821 this method converts unsigned 64 bit int type to this class 02822 ***this method is created only on a 32bit platform*** 02823 */ 02824 uint FromInt (ulint n) 02825 { 02826 return FromUInt (n); 02827 } 02828 02829 02830 /*! 02831 this method converts signed 64 bit int type to this class 02832 ***this method is created only on a 32bit platform*** 02833 */ 02834 uint FromInt (slint n) 02835 { 02836 uint c = FromUInt (ulint (n)); 02837 02838 if( c || n < 0 ) 02839 return 1; 02840 02841 return 0; 02842 } 02843 02844 02845 /*! 02846 this operator converts unsigned 64 bit int type to this class 02847 ***this operator is created only on a 32bit platform*** 02848 */ 02849 UInt<value_size> & operator= (ulint n) 02850 { 02851 FromUInt (n); 02852 02853 return *this; 02854 } 02855 02856 02857 /*! 02858 a constructor for converting unsigned 64 bit int to this class 02859 ***this constructor is created only on a 32bit platform*** 02860 */ 02861 UInt (ulint n) 02862 { 02863 FromUInt (n); 02864 } 02865 02866 02867 /*! 02868 this operator converts signed 64 bit int type to this class 02869 ***this operator is created only on a 32bit platform*** 02870 */ 02871 UInt<value_size> & operator= (slint n) 02872 { 02873 FromInt (n); 02874 02875 return *this; 02876 } 02877 02878 02879 /*! 02880 a constructor for converting signed 64 bit int to this class 02881 ***this constructor is created only on a 32bit platform*** 02882 */ 02883 UInt (slint n) 02884 { 02885 FromInt (n); 02886 } 02887 02888 #endif 02889 02890 02891 02892 #ifdef TTMATH_PLATFORM64 02893 02894 02895 /*! 02896 this method converts 32 bit unsigned int type to this class 02897 ***this operator is created only on a 64bit platform*** 02898 */ 02899 uint FromUInt (unsigned int i) 02900 { 02901 return FromUInt (uint (i)); 02902 } 02903 02904 /*! 02905 this method converts 32 bit unsigned int type to this class 02906 ***this operator is created only on a 64bit platform*** 02907 */ 02908 uint FromInt (unsigned int i) 02909 { 02910 return FromUInt (uint (i)); 02911 } 02912 02913 02914 /*! 02915 this method converts 32 bit signed int type to this class 02916 ***this operator is created only on a 64bit platform*** 02917 */ 02918 uint FromInt (signed int i) 02919 { 02920 return FromInt (sint(i)); 02921 } 02922 02923 02924 /*! 02925 this operator converts 32 bit unsigned int type to this class 02926 ***this operator is created only on a 64bit platform*** 02927 */ 02928 UInt<value_size> & operator= (unsigned int i) 02929 { 02930 FromUInt (i); 02931 02932 return *this; 02933 } 02934 02935 02936 /*! 02937 a constructor for converting 32 bit unsigned int to this class 02938 ***this constructor is created only on a 64bit platform*** 02939 */ 02940 UInt (unsigned int i) 02941 { 02942 FromUInt (i); 02943 } 02944 02945 02946 /*! 02947 an operator for converting 32 bit signed int to this class 02948 ***this constructor is created only on a 64bit platform*** 02949 */ 02950 UInt<value_size> & operator= (signed int i) 02951 { 02952 FromInt (i); 02953 02954 return *this; 02955 } 02956 02957 02958 /*! 02959 a constructor for converting 32 bit signed int to this class 02960 ***this constructor is created only on a 64bit platform*** 02961 */ 02962 UInt (signed int i) 02963 { 02964 FromInt (i); 02965 } 02966 02967 02968 #endif 02969 02970 02971 02972 02973 02974 /*! 02975 a constructor for converting a string to this class (with the base=10) 02976 */ 02977 UInt (const char * s) 02978 { 02979 FromString (s); 02980 } 02981 02982 02983 /*! 02984 a constructor for converting a string to this class (with the base=10) 02985 */ 02986 UInt (const std::string & s) 02987 { 02988 FromString ( s.c_str() ); 02989 } 02990 02991 02992 #ifndef TTMATH_DONT_USE_WCHAR 02993 02994 /*! 02995 a constructor for converting a string to this class (with the base=10) 02996 */ 02997 UInt (const wchar_t * s) 02998 { 02999 FromString (s); 03000 } 03001 03002 03003 /*! 03004 a constructor for converting a string to this class (with the base=10) 03005 */ 03006 UInt (const std::wstring & s) 03007 { 03008 FromString ( s.c_str() ); 03009 } 03010 03011 #endif 03012 03013 03014 03015 03016 /*! 03017 a default constructor 03018 03019 we don't clear the table 03020 */ 03021 UInt () 03022 { 03023 // when macro TTMATH_DEBUG_LOG is defined 03024 // we set special values to the table 03025 // in order to be everywhere the same value of the UInt object 03026 // without this it would be difficult to analyse the log file 03027 #ifdef TTMATH_DEBUG_LOG 03028 #ifdef TTMATH_PLATFORM32 03029 for(uint i=0 ; i<value_size ; ++i) 03030 table[i] = 0xc1c1c1c1; 03031 #else 03032 for(uint i=0 ; i<value_size ; ++i) 03033 table[i] = 0xc1c1c1c1c1c1c1c1; 03034 #endif 03035 #endif 03036 } 03037 03038 03039 /*! 03040 a copy constructor 03041 */ 03042 UInt (const UInt<value_size> & u) 03043 { 03044 for(uint i=0 ; i<value_size ; ++i) 03045 table[i] = u.table [i]; 03046 03047 TTMATH_LOG("UInt::UInt(UInt<>)") 03048 } 03049 03050 03051 03052 /*! 03053 a template for producting constructors for copying from another types 03054 */ 03055 template<uint argument_size> 03056 UInt (const UInt<argument_size> & u) 03057 { 03058 // look that 'size' we still set as 'value_size' and not as u.value_size 03059 FromUInt (u); 03060 } 03061 03062 03063 03064 03065 /*! 03066 a destructor 03067 */ 03068 ~UInt () 03069 { 03070 } 03071 03072 03073 /*! 03074 this method returns the lowest value from table 03075 03076 we must be sure when we using this method whether the value 03077 will hold in an uint type or not (the rest value from the table must be zero) 03078 */ 03079 uint ToUInt () const 03080 { 03081 return table[0]; 03082 } 03083 03084 03085 /*! 03086 this method converts the value to uint type 03087 can return a carry if the value is too long to store it in uint type 03088 */ 03089 uint ToUInt (uint & result) const 03090 { 03091 result = table[0]; 03092 03093 for(uint i=1 ; i<value_size ; ++i) 03094 if( table[i] != 0 ) 03095 return 1; 03096 03097 return 0; 03098 } 03099 03100 03101 /*! 03102 this method converts the value to uint type 03103 can return a carry if the value is too long to store it in uint type 03104 */ 03105 uint ToInt (uint & result) const 03106 { 03107 return ToUInt (result); 03108 } 03109 03110 03111 /*! 03112 this method converts the value to sint type (signed integer) 03113 can return a carry if the value is too long to store it in sint type 03114 */ 03115 uint ToInt (sint & result) const 03116 { 03117 result = sint(table[0]); 03118 03119 if( (result & TTMATH_UINT_HIGHEST_BIT) != 0 ) 03120 return 1; 03121 03122 for(uint i=1 ; i<value_size ; ++i) 03123 if( table[i] != 0 ) 03124 return 1; 03125 03126 return 0; 03127 } 03128 03129 03130 #ifdef TTMATH_PLATFORM32 03131 03132 /*! 03133 this method converts the value to ulint type (64 bit unsigned integer) 03134 can return a carry if the value is too long to store it in ulint type 03135 *** this method is created only on a 32 bit platform *** 03136 */ 03137 uint ToUInt (ulint & result) const 03138 { 03139 if( value_size == 1 ) 03140 { 03141 result = table[0]; 03142 } 03143 else 03144 { 03145 uint low = table[0]; 03146 uint high = table[1]; 03147 03148 result = low; 03149 result |= (ulint (high) << TTMATH_BITS_PER_UINT); 03150 03151 for(uint i=2 ; i<value_size ; ++i) 03152 if( table[i] != 0 ) 03153 return 1; 03154 } 03155 03156 return 0; 03157 } 03158 03159 03160 /*! 03161 this method converts the value to ulint type (64 bit unsigned integer) 03162 can return a carry if the value is too long to store it in ulint type 03163 *** this method is created only on a 32 bit platform *** 03164 */ 03165 uint ToInt (ulint & result) const 03166 { 03167 return ToUInt (result); 03168 } 03169 03170 03171 /*! 03172 this method converts the value to slint type (64 bit signed integer) 03173 can return a carry if the value is too long to store it in slint type 03174 *** this method is created only on a 32 bit platform *** 03175 */ 03176 uint ToInt (slint & result) const 03177 { 03178 ulint temp; 03179 03180 uint c = ToUInt (temp); 03181 result = slint(temp); 03182 03183 if( c || result < 0 ) 03184 return 1; 03185 03186 return 0; 03187 } 03188 03189 #endif 03190 03191 03192 03193 #ifdef TTMATH_PLATFORM64 03194 03195 /*! 03196 this method converts the value to a 32 unsigned integer 03197 can return a carry if the value is too long to store it in this type 03198 *** this method is created only on a 64 bit platform *** 03199 */ 03200 uint ToUInt (unsigned int & result) const 03201 { 03202 result = (unsigned int)table[0]; 03203 03204 if( (table[0] >> 32) != 0 ) 03205 return 1; 03206 03207 for(uint i=1 ; i<value_size ; ++i) 03208 if( table[i] != 0 ) 03209 return 1; 03210 03211 return 0; 03212 } 03213 03214 03215 /*! 03216 this method converts the value to a 32 unsigned integer 03217 can return a carry if the value is too long to store it in this type 03218 *** this method is created only on a 64 bit platform *** 03219 */ 03220 uint ToInt (unsigned int & result) const 03221 { 03222 return ToUInt (result); 03223 } 03224 03225 03226 /*! 03227 this method converts the value to a 32 signed integer 03228 can return a carry if the value is too long to store it in this type 03229 *** this method is created only on a 64 bit platform *** 03230 */ 03231 uint ToInt (int & result) const 03232 { 03233 unsigned int temp; 03234 03235 uint c = ToUInt (temp); 03236 result = int(temp); 03237 03238 if( c || result < 0 ) 03239 return 1; 03240 03241 return 0; 03242 } 03243 03244 03245 #endif 03246 03247 03248 03249 03250 protected: 03251 03252 /*! 03253 an auxiliary method for converting into the string 03254 it returns the log (with the base 2) from x 03255 where x is in <2;16> 03256 */ 03257 double ToStringLog2 (uint x) const 03258 { 03259 static double log_tab[] = { 03260 1.000000000000000000, 03261 0.630929753571457437, 03262 0.500000000000000000, 03263 0.430676558073393050, 03264 0.386852807234541586, 03265 0.356207187108022176, 03266 0.333333333333333333, 03267 0.315464876785728718, 03268 0.301029995663981195, 03269 0.289064826317887859, 03270 0.278942945651129843, 03271 0.270238154427319741, 03272 0.262649535037193547, 03273 0.255958024809815489, 03274 0.250000000000000000 03275 }; 03276 03277 if( x<2 || x>16 ) 03278 return 0; 03279 03280 return log_tab[x-2]; 03281 } 03282 03283 03284 public: 03285 03286 03287 /*! 03288 an auxiliary method for converting to a string 03289 it's used from Int::ToString() too (negative is set true then) 03290 */ 03291 template<class string_type> 03292 void ToStringBase (string_type & result, uint b = 10, bool negative = false) const 03293 { 03294 UInt<value_size> temp(*this); 03295 uint rest, table_id, index, digits; 03296 double digits_d; 03297 char character; 03298 03299 result.clear(); 03300 03301 if( b<2 || b>16 ) 03302 return; 03303 03304 if( !FindLeadingBit (table_id, index) ) 03305 { 03306 result = '0'; 03307 return; 03308 } 03309 03310 if( negative ) 03311 result = '-'; 03312 03313 digits_d = table_id; // for not making an overflow in uint type 03314 digits_d *= TTMATH_BITS_PER_UINT; 03315 digits_d += index + 1; 03316 digits_d *= ToStringLog2 (b); 03317 digits = static_cast<uint >(digits_d) + 3; // plus some epsilon 03318 03319 if( result.capacity() < digits ) 03320 result.reserve(digits); 03321 03322 do 03323 { 03324 temp.DivInt (b, &rest); 03325 character = static_cast<char>(Misc::DigitToChar (rest)); 03326 result.insert(result.end(), character); 03327 } 03328 while( !temp.IsZero () ); 03329 03330 size_t i1 = negative ? 1 : 0; // the first is a hyphen (when negative is true) 03331 size_t i2 = result.size() - 1; 03332 03333 for( ; i1 < i2 ; ++i1, --i2 ) 03334 { 03335 char tempc = static_cast<char>(result[i1]); 03336 result[i1] = result[i2]; 03337 result[i2] = tempc; 03338 } 03339 } 03340 03341 03342 03343 /*! 03344 this method converts the value to a string with a base equal 'b' 03345 */ 03346 void ToString (std::string & result, uint b = 10) const 03347 { 03348 return ToStringBase (result, b); 03349 } 03350 03351 03352 std::string ToString (uint b = 10) const 03353 { 03354 std::string result; 03355 ToStringBase (result, b); 03356 03357 return result; 03358 } 03359 03360 03361 #ifndef TTMATH_DONT_USE_WCHAR 03362 03363 void ToString (std::wstring & result, uint b = 10) const 03364 { 03365 return ToStringBase (result, b); 03366 } 03367 03368 std::wstring ToWString(uint b = 10) const 03369 { 03370 std::wstring result; 03371 ToStringBase (result, b); 03372 03373 return result; 03374 } 03375 03376 #endif 03377 03378 03379 03380 private: 03381 03382 /*! 03383 an auxiliary method for converting from a string 03384 */ 03385 template<class char_type> 03386 uint FromStringBase(const char_type * s, uint b = 10, const char_type ** after_source = 0, bool * value_read = 0) 03387 { 03388 UInt<value_size> base( b ); 03389 UInt<value_size> temp; 03390 sint z; 03391 uint c = 0; 03392 03393 SetZero (); 03394 temp.SetZero(); 03395 Misc::SkipWhiteCharacters(s); 03396 03397 if( after_source ) 03398 *after_source = s; 03399 03400 if( value_read ) 03401 *value_read = false; 03402 03403 if( b<2 || b>16 ) 03404 return 1; 03405 03406 03407 for( ; (z=Misc::CharToDigit (*s, b)) != -1 ; ++s) 03408 { 03409 if( value_read ) 03410 *value_read = true; 03411 03412 if( c == 0 ) 03413 { 03414 temp.table[0] = z; 03415 03416 c += Mul (base); // !! IMPROVE ME: there can be used MulInt here 03417 c += Add (temp); 03418 } 03419 } 03420 03421 if( after_source ) 03422 *after_source = s; 03423 03424 TTMATH_LOGC("UInt::FromString", c) 03425 03426 return (c==0)? 0 : 1; 03427 } 03428 03429 03430 public: 03431 03432 03433 /*! 03434 this method converts a string into its value 03435 it returns carry=1 if the value will be too big or an incorrect base 'b' is given 03436 03437 string is ended with a non-digit value, for example: 03438 "12" will be translated to 12 03439 as well as: 03440 "12foo" will be translated to 12 too 03441 03442 existing first white characters will be ommited 03443 03444 if the value from s is too large the rest digits will be skipped 03445 03446 after_source (if exists) is pointing at the end of the parsed string 03447 03448 value_read (if exists) tells whether something has actually been read (at least one digit) 03449 */ 03450 uint FromString (const char * s, uint b = 10, const char ** after_source = 0, bool * value_read = 0) 03451 { 03452 return FromStringBase(s, b, after_source, value_read); 03453 } 03454 03455 03456 /*! 03457 this method converts a string into its value 03458 03459 (it returns carry=1 if the value will be too big or an incorrect base 'b' is given) 03460 */ 03461 uint FromString (const std::string & s, uint b = 10) 03462 { 03463 return FromString ( s.c_str(), b ); 03464 } 03465 03466 03467 /*! 03468 this operator converts a string into its value (with base = 10) 03469 */ 03470 UInt<value_size> & operator= (const char * s) 03471 { 03472 FromString (s); 03473 03474 return *this; 03475 } 03476 03477 03478 /*! 03479 this operator converts a string into its value (with base = 10) 03480 */ 03481 UInt<value_size> & operator= (const std::string & s) 03482 { 03483 FromString ( s.c_str() ); 03484 03485 return *this; 03486 } 03487 03488 03489 03490 #ifndef TTMATH_DONT_USE_WCHAR 03491 03492 /*! 03493 this method converts a string into its value 03494 */ 03495 uint FromString (const wchar_t * s, uint b = 10, const wchar_t ** after_source = 0, bool * value_read = 0) 03496 { 03497 return FromStringBase(s, b, after_source, value_read); 03498 } 03499 03500 03501 /*! 03502 this method converts a string into its value 03503 03504 (it returns carry=1 if the value will be too big or an incorrect base 'b' is given) 03505 */ 03506 uint FromString (const std::wstring & s, uint b = 10) 03507 { 03508 return FromString ( s.c_str(), b ); 03509 } 03510 03511 03512 /*! 03513 this operator converts a string into its value (with base = 10) 03514 */ 03515 UInt<value_size> & operator= (const wchar_t * s) 03516 { 03517 FromString (s); 03518 03519 return *this; 03520 } 03521 03522 03523 /*! 03524 this operator converts a string into its value (with base = 10) 03525 */ 03526 UInt<value_size> & operator= (const std::wstring & s) 03527 { 03528 FromString ( s.c_str() ); 03529 03530 return *this; 03531 } 03532 03533 #endif 03534 03535 03536 /*! 03537 * 03538 * methods for comparing 03539 * 03540 */ 03541 03542 03543 /*! 03544 this method returns true if 'this' is smaller than 'l' 03545 03546 'index' is an index of the first word from will be the comparison performed 03547 (note: we start the comparison from back - from the last word, when index is -1 /default/ 03548 it is automatically set into the last word) 03549 I introduced it for some kind of optimization made in the second division algorithm (Div2) 03550 */ 03551 bool CmpSmaller (const UInt<value_size> & l, sint index = -1) const 03552 { 03553 sint i; 03554 03555 if( index==-1 || index>=sint(value_size) ) 03556 i = value_size - 1; 03557 else 03558 i = index; 03559 03560 03561 for( ; i>=0 ; --i) 03562 { 03563 if( table[i] != l.table [i] ) 03564 return table[i] < l.table [i]; 03565 } 03566 03567 // they're equal 03568 return false; 03569 } 03570 03571 03572 03573 /*! 03574 this method returns true if 'this' is bigger than 'l' 03575 03576 'index' is an index of the first word from will be the comparison performed 03577 (note: we start the comparison from back - from the last word, when index is -1 /default/ 03578 it is automatically set into the last word) 03579 03580 I introduced it for some kind of optimization made in the second division algorithm (Div2) 03581 */ 03582 bool CmpBigger (const UInt<value_size> & l, sint index = -1) const 03583 { 03584 sint i; 03585 03586 if( index==-1 || index>=sint(value_size) ) 03587 i = value_size - 1; 03588 else 03589 i = index; 03590 03591 03592 for( ; i>=0 ; --i) 03593 { 03594 if( table[i] != l.table [i] ) 03595 return table[i] > l.table [i]; 03596 } 03597 03598 // they're equal 03599 return false; 03600 } 03601 03602 03603 /*! 03604 this method returns true if 'this' is equal 'l' 03605 03606 'index' is an index of the first word from will be the comparison performed 03607 (note: we start the comparison from back - from the last word, when index is -1 /default/ 03608 it is automatically set into the last word) 03609 */ 03610 bool CmpEqual (const UInt<value_size> & l, sint index = -1) const 03611 { 03612 sint i; 03613 03614 if( index==-1 || index>=sint(value_size) ) 03615 i = value_size - 1; 03616 else 03617 i = index; 03618 03619 03620 for( ; i>=0 ; --i) 03621 if( table[i] != l.table [i] ) 03622 return false; 03623 03624 return true; 03625 } 03626 03627 03628 03629 /*! 03630 this method returns true if 'this' is smaller than or equal 'l' 03631 03632 'index' is an index of the first word from will be the comparison performed 03633 (note: we start the comparison from back - from the last word, when index is -1 /default/ 03634 it is automatically set into the last word) 03635 */ 03636 bool CmpSmallerEqual (const UInt<value_size> & l, sint index=-1) const 03637 { 03638 sint i; 03639 03640 if( index==-1 || index>=sint(value_size) ) 03641 i = value_size - 1; 03642 else 03643 i = index; 03644 03645 03646 for( ; i>=0 ; --i) 03647 { 03648 if( table[i] != l.table [i] ) 03649 return table[i] < l.table [i]; 03650 } 03651 03652 // they're equal 03653 return true; 03654 } 03655 03656 03657 03658 /*! 03659 this method returns true if 'this' is bigger than or equal 'l' 03660 03661 'index' is an index of the first word from will be the comparison performed 03662 (note: we start the comparison from back - from the last word, when index is -1 /default/ 03663 it is automatically set into the last word) 03664 */ 03665 bool CmpBiggerEqual (const UInt<value_size> & l, sint index=-1) const 03666 { 03667 sint i; 03668 03669 if( index==-1 || index>=sint(value_size) ) 03670 i = value_size - 1; 03671 else 03672 i = index; 03673 03674 03675 for( ; i>=0 ; --i) 03676 { 03677 if( table[i] != l.table [i] ) 03678 return table[i] > l.table [i]; 03679 } 03680 03681 // they're equal 03682 return true; 03683 } 03684 03685 03686 /* 03687 operators for comparising 03688 */ 03689 03690 bool operator<(const UInt<value_size> & l) const 03691 { 03692 return CmpSmaller (l); 03693 } 03694 03695 03696 bool operator>(const UInt<value_size> & l) const 03697 { 03698 return CmpBigger (l); 03699 } 03700 03701 03702 bool operator==(const UInt<value_size> & l) const 03703 { 03704 return CmpEqual (l); 03705 } 03706 03707 03708 bool operator!=(const UInt<value_size> & l) const 03709 { 03710 return !operator==(l); 03711 } 03712 03713 03714 bool operator<=(const UInt<value_size> & l) const 03715 { 03716 return CmpSmallerEqual (l); 03717 } 03718 03719 bool operator>=(const UInt<value_size> & l) const 03720 { 03721 return CmpBiggerEqual (l); 03722 } 03723 03724 03725 /*! 03726 * 03727 * standard mathematical operators 03728 * 03729 */ 03730 03731 UInt<value_size> operator- (const UInt<value_size> & p2) const 03732 { 03733 UInt<value_size> temp(*this); 03734 03735 temp.Sub (p2); 03736 03737 return temp; 03738 } 03739 03740 UInt<value_size> & operator-=(const UInt<value_size> & p2) 03741 { 03742 Sub (p2); 03743 03744 return *this; 03745 } 03746 03747 UInt<value_size> operator+(const UInt<value_size> & p2) const 03748 { 03749 UInt<value_size> temp(*this); 03750 03751 temp.Add(p2); 03752 03753 return temp; 03754 } 03755 03756 UInt<value_size> & operator+=(const UInt<value_size> & p2) 03757 { 03758 Add (p2); 03759 03760 return *this; 03761 } 03762 03763 03764 UInt<value_size> operator*(const UInt<value_size> & p2) const 03765 { 03766 UInt<value_size> temp(*this); 03767 03768 temp.Mul(p2); 03769 03770 return temp; 03771 } 03772 03773 03774 UInt<value_size> & operator*=(const UInt<value_size> & p2) 03775 { 03776 Mul (p2); 03777 03778 return *this; 03779 } 03780 03781 03782 UInt<value_size> operator/(const UInt<value_size> & p2) const 03783 { 03784 UInt<value_size> temp(*this); 03785 03786 temp.Div(p2); 03787 03788 return temp; 03789 } 03790 03791 03792 UInt<value_size> & operator/=(const UInt<value_size> & p2) 03793 { 03794 Div (p2); 03795 03796 return *this; 03797 } 03798 03799 03800 UInt<value_size> operator%(const UInt<value_size> & p2) const 03801 { 03802 UInt<value_size> temp(*this); 03803 UInt<value_size> remainder; 03804 03805 temp.Div( p2, remainder ); 03806 03807 return remainder; 03808 } 03809 03810 03811 UInt<value_size> & operator%=(const UInt<value_size> & p2) 03812 { 03813 UInt<value_size> remainder; 03814 03815 Div ( p2, remainder ); 03816 operator= (remainder); 03817 03818 return *this; 03819 } 03820 03821 03822 /*! 03823 Prefix operator e.g ++variable 03824 */ 03825 UInt<value_size> & operator++ () 03826 { 03827 AddOne (); 03828 03829 return *this; 03830 } 03831 03832 03833 /*! 03834 Postfix operator e.g variable++ 03835 */ 03836 UInt<value_size> operator++ (int) 03837 { 03838 UInt<value_size> temp( *this ); 03839 03840 AddOne (); 03841 03842 return temp; 03843 } 03844 03845 03846 UInt<value_size> & operator--() 03847 { 03848 SubOne (); 03849 03850 return *this; 03851 } 03852 03853 03854 UInt<value_size> operator--(int) 03855 { 03856 UInt<value_size> temp( *this ); 03857 03858 SubOne (); 03859 03860 return temp; 03861 } 03862 03863 03864 03865 /*! 03866 * 03867 * bitwise operators 03868 * 03869 */ 03870 03871 UInt<value_size> operator~ () const 03872 { 03873 UInt<value_size> temp( *this ); 03874 03875 temp.BitNot (); 03876 03877 return temp; 03878 } 03879 03880 03881 UInt<value_size> operator&(const UInt<value_size> & p2) const 03882 { 03883 UInt<value_size> temp( *this ); 03884 03885 temp.BitAnd(p2); 03886 03887 return temp; 03888 } 03889 03890 03891 UInt<value_size> & operator&=(const UInt<value_size> & p2) 03892 { 03893 BitAnd (p2); 03894 03895 return *this; 03896 } 03897 03898 03899 UInt<value_size> operator|(const UInt<value_size> & p2) const 03900 { 03901 UInt<value_size> temp( *this ); 03902 03903 temp.BitOr(p2); 03904 03905 return temp; 03906 } 03907 03908 03909 UInt<value_size> & operator|=(const UInt<value_size> & p2) 03910 { 03911 BitOr (p2); 03912 03913 return *this; 03914 } 03915 03916 03917 UInt<value_size> operator^(const UInt<value_size> & p2) const 03918 { 03919 UInt<value_size> temp( *this ); 03920 03921 temp.BitXor(p2); 03922 03923 return temp; 03924 } 03925 03926 03927 UInt<value_size> & operator^=(const UInt<value_size> & p2) 03928 { 03929 BitXor (p2); 03930 03931 return *this; 03932 } 03933 03934 03935 UInt<value_size> operator>>(int move) const 03936 { 03937 UInt<value_size> temp( *this ); 03938 03939 temp.Rcr(move); 03940 03941 return temp; 03942 } 03943 03944 03945 UInt<value_size> & operator>>=(int move) 03946 { 03947 Rcr (move); 03948 03949 return *this; 03950 } 03951 03952 03953 UInt<value_size> operator<<(int move) const 03954 { 03955 UInt<value_size> temp( *this ); 03956 03957 temp.Rcl(move); 03958 03959 return temp; 03960 } 03961 03962 03963 UInt<value_size> & operator<<=(int move) 03964 { 03965 Rcl (move); 03966 03967 return *this; 03968 } 03969 03970 03971 /*! 03972 * 03973 * input/output operators for standard streams 03974 * 03975 * (they are very simple, in the future they should be changed) 03976 * 03977 */ 03978 03979 03980 private: 03981 03982 03983 /*! 03984 an auxiliary method for outputing to standard streams 03985 */ 03986 template<class ostream_type, class string_type> 03987 static ostream_type & OutputToStream(ostream_type & s, const UInt<value_size> & l) 03988 { 03989 string_type ss; 03990 03991 l.ToString(ss); 03992 s << ss; 03993 03994 return s; 03995 } 03996 03997 03998 public: 03999 04000 04001 /*! 04002 output to standard streams 04003 */ 04004 friend std::ostream & operator<<(std::ostream & s, const UInt<value_size> & l) 04005 { 04006 return OutputToStream<std::ostream, std::string>(s, l); 04007 } 04008 04009 04010 #ifndef TTMATH_DONT_USE_WCHAR 04011 04012 /*! 04013 output to standard streams 04014 */ 04015 friend std::wostream & operator<<(std::wostream & s, const UInt<value_size> & l) 04016 { 04017 return OutputToStream<std::wostream, std::wstring>(s, l); 04018 } 04019 04020 #endif 04021 04022 04023 04024 private: 04025 04026 /*! 04027 an auxiliary method for reading from standard streams 04028 */ 04029 template<class istream_type, class string_type, class char_type> 04030 static istream_type & InputFromStream(istream_type & s, UInt<value_size> & l) 04031 { 04032 string_type ss; 04033 04034 // char or wchar_t for operator>> 04035 char_type z; 04036 04037 // operator>> omits white characters if they're set for ommiting 04038 s >> z; 04039 04040 // we're reading only digits (base=10) 04041 while( s.good() && Misc::CharToDigit (z, 10)>=0 ) 04042 { 04043 ss += z; 04044 z = static_cast<char_type>(s.get()); 04045 } 04046 04047 // we're leaving the last read character 04048 // (it's not belonging to the value) 04049 s.unget(); 04050 04051 l.FromString (ss); 04052 04053 return s; 04054 } 04055 04056 public: 04057 04058 04059 /*! 04060 input from standard streams 04061 */ 04062 friend std::istream & operator>>(std::istream & s, UInt<value_size> & l) 04063 { 04064 return InputFromStream<std::istream, std::string, char>(s, l); 04065 } 04066 04067 04068 #ifndef TTMATH_DONT_USE_WCHAR 04069 04070 /*! 04071 input from standard streams 04072 */ 04073 friend std::wistream & operator>>(std::wistream & s, UInt<value_size> & l) 04074 { 04075 return InputFromStream<std::wistream, std::wstring, wchar_t>(s, l); 04076 } 04077 04078 #endif 04079 04080 04081 /* 04082 Following methods are defined in: 04083 ttmathuint_x86.h 04084 ttmathuint_x86_64.h 04085 ttmathuint_noasm.h 04086 */ 04087 04088 #ifdef TTMATH_NOASM 04089 static uint AddTwoWords (uint a, uint b, uint carry, uint * result); 04090 static uint SubTwoWords (uint a, uint b, uint carry, uint * result); 04091 04092 #ifdef TTMATH_PLATFORM64 04093 04094 union uint_ 04095 { 04096 struct 04097 { 04098 unsigned int low; // 32 bit 04099 unsigned int high; // 32 bit 04100 } u_; 04101 04102 uint u; // 64 bit 04103 }; 04104 04105 04106 static void DivTwoWords2 (uint a,uint b, uint c, uint * r, uint * rest); 04107 static uint DivTwoWordsNormalize(uint_ & a_, uint_ & b_, uint_ & c_); 04108 static uint DivTwoWordsUnnormalize(uint u, uint d); 04109 static unsigned int DivTwoWordsCalculate(uint_ u_, unsigned int u3, uint_ v_); 04110 static void MultiplySubtract(uint_ & u_, unsigned int & u3, unsigned int & q, uint_ v_); 04111 04112 #endif // TTMATH_PLATFORM64 04113 #endif // TTMATH_NOASM 04114 04115 04116 private: 04117 uint Rcl2_one(uint c); 04118 uint Rcr2_one(uint c); 04119 uint Rcl2(uint bits, uint c); 04120 uint Rcr2(uint bits, uint c); 04121 04122 public: 04123 static const char * LibTypeStr (); 04124 static LibTypeCode LibType (); 04125 uint Add (const UInt<value_size> & ss2, uint c=0); 04126 uint AddInt (uint value, uint index = 0); 04127 uint AddTwoInts (uint x2, uint x1, uint index); 04128 static uint AddVector (const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result); 04129 uint Sub (const UInt<value_size> & ss2, uint c=0); 04130 uint SubInt (uint value, uint index = 0); 04131 static uint SubVector (const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result); 04132 static sint FindLeadingBitInWord (uint x); 04133 static sint FindLowestBitInWord (uint x); 04134 static uint SetBitInWord (uint & value, uint bit); 04135 static void MulTwoWords (uint a, uint b, uint * result_high, uint * result_low); 04136 static void DivTwoWords (uint a,uint b, uint c, uint * r, uint * rest); 04137 04138 }; 04139 04140 04141 04142 /*! 04143 this specialization is needed in order to not confused the compiler "error: ISO C++ forbids zero-size array" 04144 when compiling Mul3Big2() method 04145 */ 04146 template<> 04147 class UInt<0> 04148 { 04149 public: 04150 uint table[1]; 04151 04152 void Mul2Big (const UInt<0> &, UInt<0> &) { TTMATH_ASSERT(false) }; 04153 void SetZero () { TTMATH_ASSERT(false) }; 04154 uint AddTwoInts (uint , uint , uint ) { TTMATH_ASSERT(false) return 0; }; 04155 }; 04156 04157 04158 } //namespace 04159 04160 04161 #include "ttmathuint_x86.h" 04162 #include "ttmathuint_x86_64.h" 04163 #include "ttmathuint_noasm.h" 04164 04165 #endif 04166
Generated on Tue Jul 12 2022 14:03:18 by
1.7.2