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_noasm.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-2010, 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 #ifndef headerfilettmathuint_noasm 00039 #define headerfilettmathuint_noasm 00040 00041 00042 #ifdef TTMATH_NOASM 00043 00044 /*! 00045 \file ttmathuint_noasm.h 00046 \brief template class UInt<uint> with methods without any assembler code 00047 00048 this file is included at the end of ttmathuint.h 00049 */ 00050 00051 00052 namespace ttmath 00053 { 00054 00055 /*! 00056 returning the string represents the currect type of the library 00057 we have following types: 00058 asm_vc_32 - with asm code designed for Microsoft Visual C++ (32 bits) 00059 asm_gcc_32 - with asm code designed for GCC (32 bits) 00060 asm_vc_64 - with asm for VC (64 bit) 00061 asm_gcc_64 - with asm for GCC (64 bit) 00062 no_asm_32 - pure C++ version (32 bit) - without any asm code 00063 no_asm_64 - pure C++ version (64 bit) - without any asm code 00064 */ 00065 template<uint value_size> 00066 const char * UInt<value_size>::LibTypeStr () 00067 { 00068 #ifdef TTMATH_PLATFORM32 00069 static const char info[] = "no_asm_32"; 00070 #endif 00071 00072 #ifdef TTMATH_PLATFORM64 00073 static const char info[] = "no_asm_64"; 00074 #endif 00075 00076 return info; 00077 } 00078 00079 00080 /*! 00081 returning the currect type of the library 00082 */ 00083 template<uint value_size> 00084 LibTypeCode UInt<value_size>::LibType () 00085 { 00086 #ifdef TTMATH_PLATFORM32 00087 LibTypeCode info = no_asm_32; 00088 #endif 00089 00090 #ifdef TTMATH_PLATFORM64 00091 LibTypeCode info = no_asm_64; 00092 #endif 00093 00094 return info; 00095 } 00096 00097 00098 /*! 00099 this method adds two words together 00100 returns carry 00101 00102 this method is created only when TTMATH_NOASM macro is defined 00103 */ 00104 template<uint value_size> 00105 uint UInt<value_size>::AddTwoWords (uint a, uint b, uint carry, uint * result) 00106 { 00107 uint temp; 00108 00109 if( carry == 0 ) 00110 { 00111 temp = a + b; 00112 00113 if( temp < a ) 00114 carry = 1; 00115 } 00116 else 00117 { 00118 carry = 1; 00119 temp = a + b + carry; 00120 00121 if( temp > a ) // !(temp<=a) 00122 carry = 0; 00123 } 00124 00125 *result = temp; 00126 00127 return carry; 00128 } 00129 00130 00131 00132 /*! 00133 this method adding ss2 to the this and adding carry if it's defined 00134 (this = this + ss2 + c) 00135 00136 c must be zero or one (might be a bigger value than 1) 00137 function returns carry (1) (if it was) 00138 */ 00139 00140 template<uint value_size> 00141 uint UInt<value_size>::Add (const UInt<value_size> & ss2, uint c) 00142 { 00143 uint i; 00144 00145 for(i=0 ; i<value_size ; ++i) 00146 c = AddTwoWords(table[i], ss2.table [i], c, &table[i]); 00147 00148 TTMATH_LOGC("UInt::Add", c) 00149 00150 return c; 00151 } 00152 00153 00154 /*! 00155 this method adds one word (at a specific position) 00156 and returns a carry (if it was) 00157 00158 if we've got (value_size=3): 00159 table[0] = 10; 00160 table[1] = 30; 00161 table[2] = 5; 00162 and we call: 00163 AddInt(2,1) 00164 then it'll be: 00165 table[0] = 10; 00166 table[1] = 30 + 2; 00167 table[2] = 5; 00168 00169 of course if there was a carry from table[2] it would be returned 00170 */ 00171 template<uint value_size> 00172 uint UInt<value_size>::AddInt (uint value, uint index) 00173 { 00174 uint i, c; 00175 00176 TTMATH_ASSERT( index < value_size ) 00177 00178 00179 c = AddTwoWords(table[index], value, 0, &table[index]); 00180 00181 for(i=index+1 ; i<value_size && c ; ++i) 00182 c = AddTwoWords(table[i], 0, c, &table[i]); 00183 00184 TTMATH_LOGC("UInt::AddInt", c) 00185 00186 return c; 00187 } 00188 00189 00190 00191 00192 00193 /*! 00194 this method adds only two unsigned words to the existing value 00195 and these words begin on the 'index' position 00196 (it's used in the multiplication algorithm 2) 00197 00198 index should be equal or smaller than value_size-2 (index <= value_size-2) 00199 x1 - lower word, x2 - higher word 00200 00201 for example if we've got value_size equal 4 and: 00202 table[0] = 3 00203 table[1] = 4 00204 table[2] = 5 00205 table[3] = 6 00206 then let 00207 x1 = 10 00208 x2 = 20 00209 and 00210 index = 1 00211 00212 the result of this method will be: 00213 table[0] = 3 00214 table[1] = 4 + x1 = 14 00215 table[2] = 5 + x2 = 25 00216 table[3] = 6 00217 00218 and no carry at the end of table[3] 00219 00220 (of course if there was a carry in table[2](5+20) then 00221 this carry would be passed to the table[3] etc.) 00222 */ 00223 template<uint value_size> 00224 uint UInt<value_size>::AddTwoInts (uint x2, uint x1, uint index) 00225 { 00226 uint i, c; 00227 00228 TTMATH_ASSERT( index < value_size - 1 ) 00229 00230 00231 c = AddTwoWords(table[index], x1, 0, &table[index]); 00232 c = AddTwoWords(table[index+1], x2, c, &table[index+1]); 00233 00234 for(i=index+2 ; i<value_size && c ; ++i) 00235 c = AddTwoWords(table[i], 0, c, &table[i]); 00236 00237 TTMATH_LOGC("UInt::AddTwoInts", c) 00238 00239 return c; 00240 } 00241 00242 00243 00244 /*! 00245 this static method addes one vector to the other 00246 'ss1' is larger in size or equal to 'ss2' 00247 00248 ss1 points to the first (larger) vector 00249 ss2 points to the second vector 00250 ss1_size - size of the ss1 (and size of the result too) 00251 ss2_size - size of the ss2 00252 result - is the result vector (which has size the same as ss1: ss1_size) 00253 00254 Example: ss1_size is 5, ss2_size is 3 00255 ss1: ss2: result (output): 00256 5 1 5+1 00257 4 3 4+3 00258 2 7 2+7 00259 6 6 00260 9 9 00261 of course the carry is propagated and will be returned from the last item 00262 (this method is used by the Karatsuba multiplication algorithm) 00263 */ 00264 template<uint value_size> 00265 uint UInt<value_size>::AddVector (const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result) 00266 { 00267 uint i, c = 0; 00268 00269 TTMATH_ASSERT( ss1_size >= ss2_size ) 00270 00271 for(i=0 ; i<ss2_size ; ++i) 00272 c = AddTwoWords(ss1[i], ss2[i], c, &result[i]); 00273 00274 for( ; i<ss1_size ; ++i) 00275 c = AddTwoWords(ss1[i], 0, c, &result[i]); 00276 00277 TTMATH_VECTOR_LOGC("UInt::AddVector", c, result, ss1_size) 00278 00279 return c; 00280 } 00281 00282 00283 00284 00285 /*! 00286 this method subtractes one word from the other 00287 returns carry 00288 00289 this method is created only when TTMATH_NOASM macro is defined 00290 */ 00291 template<uint value_size> 00292 uint UInt<value_size>::SubTwoWords (uint a, uint b, uint carry, uint * result) 00293 { 00294 if( carry == 0 ) 00295 { 00296 *result = a - b; 00297 00298 if( a < b ) 00299 carry = 1; 00300 } 00301 else 00302 { 00303 carry = 1; 00304 *result = a - b - carry; 00305 00306 if( a > b ) // !(a <= b ) 00307 carry = 0; 00308 } 00309 00310 return carry; 00311 } 00312 00313 00314 00315 00316 /*! 00317 this method's subtracting ss2 from the 'this' and subtracting 00318 carry if it has been defined 00319 (this = this - ss2 - c) 00320 00321 c must be zero or one (might be a bigger value than 1) 00322 function returns carry (1) (if it was) 00323 */ 00324 template<uint value_size> 00325 uint UInt<value_size>::Sub (const UInt<value_size> & ss2, uint c) 00326 { 00327 uint i; 00328 00329 for(i=0 ; i<value_size ; ++i) 00330 c = SubTwoWords(table[i], ss2.table [i], c, &table[i]); 00331 00332 TTMATH_LOGC("UInt::Sub", c) 00333 00334 return c; 00335 } 00336 00337 00338 00339 00340 /*! 00341 this method subtracts one word (at a specific position) 00342 and returns a carry (if it was) 00343 00344 if we've got (value_size=3): 00345 table[0] = 10; 00346 table[1] = 30; 00347 table[2] = 5; 00348 and we call: 00349 SubInt(2,1) 00350 then it'll be: 00351 table[0] = 10; 00352 table[1] = 30 - 2; 00353 table[2] = 5; 00354 00355 of course if there was a carry from table[2] it would be returned 00356 */ 00357 template<uint value_size> 00358 uint UInt<value_size>::SubInt (uint value, uint index) 00359 { 00360 uint i, c; 00361 00362 TTMATH_ASSERT( index < value_size ) 00363 00364 00365 c = SubTwoWords(table[index], value, 0, &table[index]); 00366 00367 for(i=index+1 ; i<value_size && c ; ++i) 00368 c = SubTwoWords(table[i], 0, c, &table[i]); 00369 00370 TTMATH_LOGC("UInt::SubInt", c) 00371 00372 return c; 00373 } 00374 00375 00376 /*! 00377 this static method subtractes one vector from the other 00378 'ss1' is larger in size or equal to 'ss2' 00379 00380 ss1 points to the first (larger) vector 00381 ss2 points to the second vector 00382 ss1_size - size of the ss1 (and size of the result too) 00383 ss2_size - size of the ss2 00384 result - is the result vector (which has size the same as ss1: ss1_size) 00385 00386 Example: ss1_size is 5, ss2_size is 3 00387 ss1: ss2: result (output): 00388 5 1 5-1 00389 4 3 4-3 00390 2 7 2-7 00391 6 6-1 (the borrow from previous item) 00392 9 9 00393 return (carry): 0 00394 of course the carry (borrow) is propagated and will be returned from the last item 00395 (this method is used by the Karatsuba multiplication algorithm) 00396 */ 00397 template<uint value_size> 00398 uint UInt<value_size>::SubVector (const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result) 00399 { 00400 uint i, c = 0; 00401 00402 TTMATH_ASSERT( ss1_size >= ss2_size ) 00403 00404 for(i=0 ; i<ss2_size ; ++i) 00405 c = SubTwoWords(ss1[i], ss2[i], c, &result[i]); 00406 00407 for( ; i<ss1_size ; ++i) 00408 c = SubTwoWords(ss1[i], 0, c, &result[i]); 00409 00410 TTMATH_VECTOR_LOGC("UInt::SubVector", c, result, ss1_size) 00411 00412 return c; 00413 } 00414 00415 00416 00417 /*! 00418 this method moves all bits into the left hand side 00419 return value <- this <- c 00420 00421 the lowest *bit* will be held the 'c' and 00422 the state of one additional bit (on the left hand side) 00423 will be returned 00424 00425 for example: 00426 let this is 001010000 00427 after Rcl2_one(1) there'll be 010100001 and Rcl2_one returns 0 00428 */ 00429 template<uint value_size> 00430 uint UInt<value_size>::Rcl2_one(uint c) 00431 { 00432 uint i, new_c; 00433 00434 if( c != 0 ) 00435 c = 1; 00436 00437 for(i=0 ; i<value_size ; ++i) 00438 { 00439 new_c = (table[i] & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0; 00440 table[i] = (table[i] << 1) | c; 00441 c = new_c; 00442 } 00443 00444 TTMATH_LOGC("UInt::Rcl2_one", c) 00445 00446 return c; 00447 } 00448 00449 00450 00451 00452 00453 00454 00455 /*! 00456 this method moves all bits into the right hand side 00457 c -> this -> return value 00458 00459 the highest *bit* will be held the 'c' and 00460 the state of one additional bit (on the right hand side) 00461 will be returned 00462 00463 for example: 00464 let this is 000000010 00465 after Rcr2_one(1) there'll be 100000001 and Rcr2_one returns 0 00466 */ 00467 template<uint value_size> 00468 uint UInt<value_size>::Rcr2_one(uint c) 00469 { 00470 sint i; // signed i 00471 uint new_c; 00472 00473 if( c != 0 ) 00474 c = TTMATH_UINT_HIGHEST_BIT; 00475 00476 for(i=sint(value_size)-1 ; i>=0 ; --i) 00477 { 00478 new_c = (table[i] & 1) ? TTMATH_UINT_HIGHEST_BIT : 0; 00479 table[i] = (table[i] >> 1) | c; 00480 c = new_c; 00481 } 00482 00483 c = (c != 0)? 1 : 0; 00484 00485 TTMATH_LOGC("UInt::Rcr2_one", c) 00486 00487 return c; 00488 } 00489 00490 00491 00492 00493 /*! 00494 this method moves all bits into the left hand side 00495 return value <- this <- c 00496 00497 the lowest *bits* will be held the 'c' and 00498 the state of one additional bit (on the left hand side) 00499 will be returned 00500 00501 for example: 00502 let this is 001010000 00503 after Rcl2(3, 1) there'll be 010000111 and Rcl2 returns 1 00504 */ 00505 template<uint value_size> 00506 uint UInt<value_size>::Rcl2(uint bits, uint c) 00507 { 00508 TTMATH_ASSERT( bits>0 && bits<TTMATH_BITS_PER_UINT ) 00509 00510 uint move = TTMATH_BITS_PER_UINT - bits; 00511 uint i, new_c; 00512 00513 if( c != 0 ) 00514 c = TTMATH_UINT_MAX_VALUE >> move; 00515 00516 for(i=0 ; i<value_size ; ++i) 00517 { 00518 new_c = table[i] >> move; 00519 table[i] = (table[i] << bits) | c; 00520 c = new_c; 00521 } 00522 00523 TTMATH_LOGC("UInt::Rcl2", (c & 1)) 00524 00525 return (c & 1); 00526 } 00527 00528 00529 00530 00531 /*! 00532 this method moves all bits into the right hand side 00533 C -> this -> return value 00534 00535 the highest *bits* will be held the 'c' and 00536 the state of one additional bit (on the right hand side) 00537 will be returned 00538 00539 for example: 00540 let this is 000000010 00541 after Rcr2(2, 1) there'll be 110000000 and Rcr2 returns 1 00542 */ 00543 template<uint value_size> 00544 uint UInt<value_size>::Rcr2(uint bits, uint c) 00545 { 00546 TTMATH_ASSERT( bits>0 && bits<TTMATH_BITS_PER_UINT ) 00547 00548 uint move = TTMATH_BITS_PER_UINT - bits; 00549 sint i; // signed 00550 uint new_c; 00551 00552 if( c != 0 ) 00553 c = TTMATH_UINT_MAX_VALUE << move; 00554 00555 for(i=value_size-1 ; i>=0 ; --i) 00556 { 00557 new_c = table[i] << move; 00558 table[i] = (table[i] >> bits) | c; 00559 c = new_c; 00560 } 00561 00562 c = (c & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0; 00563 00564 TTMATH_LOGC("UInt::Rcr2", c) 00565 00566 return c; 00567 } 00568 00569 00570 00571 00572 /*! 00573 this method returns the number of the highest set bit in x 00574 if the 'x' is zero this method returns '-1' 00575 */ 00576 template<uint value_size> 00577 sint UInt<value_size>::FindLeadingBitInWord(uint x) 00578 { 00579 if( x == 0 ) 00580 return -1; 00581 00582 uint bit = TTMATH_BITS_PER_UINT - 1; 00583 00584 while( (x & TTMATH_UINT_HIGHEST_BIT) == 0 ) 00585 { 00586 x = x << 1; 00587 --bit; 00588 } 00589 00590 return bit; 00591 } 00592 00593 00594 00595 /*! 00596 this method returns the number of the highest set bit in x 00597 if the 'x' is zero this method returns '-1' 00598 */ 00599 template<uint value_size> 00600 sint UInt<value_size>::FindLowestBitInWord (uint x) 00601 { 00602 if( x == 0 ) 00603 return -1; 00604 00605 uint bit = 0; 00606 00607 while( (x & 1) == 0 ) 00608 { 00609 x = x >> 1; 00610 ++bit; 00611 } 00612 00613 return bit; 00614 } 00615 00616 00617 00618 /*! 00619 this method sets a special bit in the 'value' 00620 and returns the last state of the bit (zero or one) 00621 00622 bit is from <0,TTMATH_BITS_PER_UINT-1> 00623 00624 e.g. 00625 uint x = 100; 00626 uint bit = SetBitInWord(x, 3); 00627 now: x = 108 and bit = 0 00628 */ 00629 template<uint value_size> 00630 uint UInt<value_size>::SetBitInWord (uint & value, uint bit) 00631 { 00632 TTMATH_ASSERT( bit < TTMATH_BITS_PER_UINT ) 00633 00634 uint mask = 1; 00635 00636 if( bit > 0 ) 00637 mask = mask << bit; 00638 00639 uint last = value & mask; 00640 value = value | mask; 00641 00642 return (last != 0) ? 1 : 0; 00643 } 00644 00645 00646 00647 00648 00649 00650 /*! 00651 * 00652 * Multiplication 00653 * 00654 * 00655 */ 00656 00657 00658 /*! 00659 multiplication: result_high:result_low = a * b 00660 result_high - higher word of the result 00661 result_low - lower word of the result 00662 00663 this methos never returns a carry 00664 this method is used in the second version of the multiplication algorithms 00665 */ 00666 template<uint value_size> 00667 void UInt<value_size>::MulTwoWords (uint a, uint b, uint * result_high, uint * result_low) 00668 { 00669 #ifdef TTMATH_PLATFORM32 00670 00671 /* 00672 on 32bit platforms we have defined 'unsigned long long int' type known as 'ulint' in ttmath namespace 00673 this type has 64 bits, then we're using only one multiplication: 32bit * 32bit = 64bit 00674 */ 00675 00676 union uint_ 00677 { 00678 struct 00679 { 00680 uint low; // 32 bits 00681 uint high; // 32 bits 00682 } u_; 00683 00684 ulint u; // 64 bits 00685 } res; 00686 00687 res.u = ulint (a) * ulint (b); // multiply two 32bit words, the result has 64 bits 00688 00689 *result_high = res.u_.high; 00690 *result_low = res.u_.low; 00691 00692 #else 00693 00694 /* 00695 64 bits platforms 00696 00697 we don't have a native type which has 128 bits 00698 then we're splitting 'a' and 'b' to 4 parts (high and low halves) 00699 and using 4 multiplications (with additions and carry correctness) 00700 */ 00701 00702 uint_ a_; 00703 uint_ b_; 00704 uint_ res_high1, res_high2; 00705 uint_ res_low1, res_low2; 00706 00707 a_.u = a; 00708 b_.u = b; 00709 00710 /* 00711 the multiplication is as follows (schoolbook algorithm with O(n^2) ): 00712 00713 32 bits 32 bits 00714 00715 +--------------------------------+ 00716 | a_.u_.high | a_.u_.low | 00717 +--------------------------------+ 00718 | b_.u_.high | b_.u_.low | 00719 +--------------------------------+--------------------------------+ 00720 | res_high1.u | res_low1.u | 00721 +--------------------------------+--------------------------------+ 00722 | res_high2.u | res_low2.u | 00723 +--------------------------------+--------------------------------+ 00724 00725 64 bits 64 bits 00726 */ 00727 00728 00729 uint_ temp; 00730 00731 res_low1.u = uint (b_.u_.low) * uint (a_.u_.low); 00732 00733 temp.u = uint (res_low1.u_.high) + uint (b_.u_.low) * uint (a_.u_.high); 00734 res_low1.u_.high = temp.u_.low; 00735 res_high1.u_.low = temp.u_.high; 00736 res_high1.u_.high = 0; 00737 00738 res_low2.u_.low = 0; 00739 temp.u = uint (b_.u_.high) * uint (a_.u_.low); 00740 res_low2.u_.high = temp.u_.low; 00741 00742 res_high2.u = uint (b_.u_.high) * uint (a_.u_.high) + uint (temp.u_.high); 00743 00744 uint c = AddTwoWords(res_low1.u, res_low2.u, 0, &res_low2.u); 00745 AddTwoWords(res_high1.u, res_high2.u, c, &res_high2.u); // there is no carry from here 00746 00747 *result_high = res_high2.u; 00748 *result_low = res_low2.u; 00749 00750 #endif 00751 } 00752 00753 00754 00755 00756 /*! 00757 * 00758 * Division 00759 * 00760 * 00761 */ 00762 00763 00764 /*! 00765 this method calculates 64bits word a:b / 32bits c (a higher, b lower word) 00766 r = a:b / c and rest - remainder 00767 00768 * 00769 * WARNING: 00770 * the c has to be suitably large for the result being keeped in one word, 00771 * if c is equal zero there'll be a hardware interruption (0) 00772 * and probably the end of your program 00773 * 00774 */ 00775 template<uint value_size> 00776 void UInt<value_size>::DivTwoWords (uint a, uint b, uint c, uint * r, uint * rest) 00777 { 00778 // (a < c ) for the result to be one word 00779 TTMATH_ASSERT( c != 0 && a < c ) 00780 00781 #ifdef TTMATH_PLATFORM32 00782 00783 union 00784 { 00785 struct 00786 { 00787 uint low; // 32 bits 00788 uint high; // 32 bits 00789 } u_; 00790 00791 ulint u; // 64 bits 00792 } ab; 00793 00794 ab.u_.high = a; 00795 ab.u_.low = b; 00796 00797 *r = uint (ab.u / c); 00798 *rest = uint (ab.u % c); 00799 00800 #else 00801 00802 uint_ c_; 00803 c_.u = c; 00804 00805 00806 if( a == 0 ) 00807 { 00808 *r = b / c; 00809 *rest = b % c; 00810 } 00811 else 00812 if( c_.u_.high == 0 ) 00813 { 00814 // higher half of 'c' is zero 00815 // then higher half of 'a' is zero too (look at the asserts at the beginning - 'a' is smaller than 'c') 00816 uint_ a_, b_, res_, temp1, temp2; 00817 00818 a_.u = a; 00819 b_.u = b; 00820 00821 temp1.u_.high = a_.u_.low; 00822 temp1.u_.low = b_.u_.high; 00823 00824 res_.u_.high = (unsigned int)(temp1.u / c); 00825 temp2.u_.high = (unsigned int)(temp1.u % c); 00826 temp2.u_.low = b_.u_.low; 00827 00828 res_.u_.low = (unsigned int)(temp2.u / c); 00829 *rest = temp2.u % c; 00830 00831 *r = res_.u; 00832 } 00833 else 00834 { 00835 return DivTwoWords2(a, b, c, r, rest); 00836 } 00837 00838 #endif 00839 } 00840 00841 00842 #ifdef TTMATH_PLATFORM64 00843 00844 00845 /*! 00846 this method is available only on 64bit platforms 00847 00848 the same algorithm like the third division algorithm in ttmathuint.h 00849 but now with the radix=2^32 00850 */ 00851 template<uint value_size> 00852 void UInt<value_size>::DivTwoWords2 (uint a, uint b, uint c, uint * r, uint * rest) 00853 { 00854 // a is not zero 00855 // c_.u_.high is not zero 00856 00857 uint_ a_, b_, c_, u_, q_; 00858 unsigned int u3; // 32 bit 00859 00860 a_.u = a; 00861 b_.u = b; 00862 c_.u = c; 00863 00864 // normalizing 00865 uint d = DivTwoWordsNormalize(a_, b_, c_); 00866 00867 // loop from j=1 to j=0 00868 // the first step (for j=2) is skipped because our result is only in one word, 00869 // (first 'q' were 0 and nothing would be changed) 00870 u_.u_.high = a_.u_.high; 00871 u_.u_.low = a_.u_.low; 00872 u3 = b_.u_.high; 00873 q_.u_.high = DivTwoWordsCalculate(u_, u3, c_); 00874 MultiplySubtract(u_, u3, q_.u_.high, c_); 00875 00876 u_.u_.high = u_.u_.low; 00877 u_.u_.low = u3; 00878 u3 = b_.u_.low; 00879 q_.u_.low = DivTwoWordsCalculate(u_, u3, c_); 00880 MultiplySubtract(u_, u3, q_.u_.low, c_); 00881 00882 *r = q_.u; 00883 00884 // unnormalizing for the remainder 00885 u_.u_.high = u_.u_.low; 00886 u_.u_.low = u3; 00887 *rest = DivTwoWordsUnnormalize(u_.u, d); 00888 } 00889 00890 00891 00892 00893 template<uint value_size> 00894 uint UInt<value_size>::DivTwoWordsNormalize(uint_ & a_, uint_ & b_, uint_ & c_) 00895 { 00896 uint d = 0; 00897 00898 for( ; (c_.u & TTMATH_UINT_HIGHEST_BIT) == 0 ; ++d ) 00899 { 00900 c_.u = c_.u << 1; 00901 00902 uint bc = b_.u & TTMATH_UINT_HIGHEST_BIT; // carry from 'b' 00903 00904 b_.u = b_.u << 1; 00905 a_.u = a_.u << 1; // carry bits from 'a' are simply skipped 00906 00907 if( bc ) 00908 a_.u = a_.u | 1; 00909 } 00910 00911 return d; 00912 } 00913 00914 00915 template<uint value_size> 00916 uint UInt<value_size>::DivTwoWordsUnnormalize(uint u, uint d) 00917 { 00918 if( d == 0 ) 00919 return u; 00920 00921 u = u >> d; 00922 00923 return u; 00924 } 00925 00926 00927 template<uint value_size> 00928 unsigned int UInt<value_size>::DivTwoWordsCalculate(uint_ u_, unsigned int u3, uint_ v_) 00929 { 00930 bool next_test; 00931 uint_ qp_, rp_, temp_; 00932 00933 qp_.u = u_.u / uint (v_.u_.high); 00934 rp_.u = u_.u % uint (v_.u_.high); 00935 00936 TTMATH_ASSERT( qp_.u_.high==0 || qp_.u_.high==1 ) 00937 00938 do 00939 { 00940 bool decrease = false; 00941 00942 if( qp_.u_.high == 1 ) 00943 decrease = true; 00944 else 00945 { 00946 temp_.u_.high = rp_.u_.low; 00947 temp_.u_.low = u3; 00948 00949 if( qp_.u * uint (v_.u_.low) > temp_.u ) 00950 decrease = true; 00951 } 00952 00953 next_test = false; 00954 00955 if( decrease ) 00956 { 00957 --qp_.u; 00958 rp_.u += v_.u_.high; 00959 00960 if( rp_.u_.high == 0 ) 00961 next_test = true; 00962 } 00963 } 00964 while( next_test ); 00965 00966 return qp_.u_.low; 00967 } 00968 00969 00970 template<uint value_size> 00971 void UInt<value_size>::MultiplySubtract(uint_ & u_, unsigned int & u3, unsigned int & q, uint_ v_) 00972 { 00973 uint_ temp_; 00974 00975 uint res_high; 00976 uint res_low; 00977 00978 MulTwoWords(v_.u, q, &res_high, &res_low); 00979 00980 uint_ sub_res_high_; 00981 uint_ sub_res_low_; 00982 00983 temp_.u_.high = u_.u_.low; 00984 temp_.u_.low = u3; 00985 00986 uint c = SubTwoWords(temp_.u, res_low, 0, &sub_res_low_.u); 00987 00988 temp_.u_.high = 0; 00989 temp_.u_.low = u_.u_.high; 00990 c = SubTwoWords(temp_.u, res_high, c, &sub_res_high_.u); 00991 00992 if( c ) 00993 { 00994 --q; 00995 00996 c = AddTwoWords(sub_res_low_.u, v_.u, 0, &sub_res_low_.u); 00997 AddTwoWords(sub_res_high_.u, 0, c, &sub_res_high_.u); 00998 } 00999 01000 u_.u_.high = sub_res_high_.u_.low; 01001 u_.u_.low = sub_res_low_.u_.high; 01002 u3 = sub_res_low_.u_.low; 01003 } 01004 01005 #endif // #ifdef TTMATH_PLATFORM64 01006 01007 01008 01009 } //namespace 01010 01011 01012 #endif //ifdef TTMATH_NOASM 01013 #endif 01014 01015 01016 01017 01018
Generated on Tue Jul 12 2022 14:03:18 by
1.7.2