Debian Codegraph @

extern/ttmath/ttmathuint_noasm.h

raw
1 /*
2 * This file is a part of TTMath Bignum Library
3 * and is distributed under the (new) BSD licence.
4 * Author: Tomasz Sowa <[email protected]>
5 */
6
7 /*
8 * Copyright (c) 2006-2010, Tomasz Sowa
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions are met:
13 *
14 * * Redistributions of source code must retain the above copyright notice,
15 * this list of conditions and the following disclaimer.
16 *
17 * * Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 *
21 * * Neither the name Tomasz Sowa nor the names of contributors to this
22 * project may be used to endorse or promote products derived
23 * from this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
26 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
29 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
35 * THE POSSIBILITY OF SUCH DAMAGE.
36 */
37
38 #ifndef headerfilettmathuint_noasm
39 #define headerfilettmathuint_noasm
40
41
42 #ifdef TTMATH_NOASM
43
44 /*!
45 \file ttmathuint_noasm.h
46 \brief template class UInt<uint> with methods without any assembler code
47
48 this file is included at the end of ttmathuint.h
49 */
50
51
52 namespace ttmath
53 {
54
55 /*!
56 returning the string represents the currect type of the library
57 we have following types:
58 asm_vc_32 - with asm code designed for Microsoft Visual C++ (32 bits)
59 asm_gcc_32 - with asm code designed for GCC (32 bits)
60 asm_vc_64 - with asm for VC (64 bit)
61 asm_gcc_64 - with asm for GCC (64 bit)
62 no_asm_32 - pure C++ version (32 bit) - without any asm code
63 no_asm_64 - pure C++ version (64 bit) - without any asm code
64 */
65 template<uint value_size>
66 const char * UInt<value_size>::LibTypeStr()
67 {
68 #ifdef TTMATH_PLATFORM32
69 static const char info[] = "no_asm_32";
70 #endif
71
72 #ifdef TTMATH_PLATFORM64
73 static const char info[] = "no_asm_64";
74 #endif
75
76 return info;
77 }
78
79
80 /*!
81 returning the currect type of the library
82 */
83 template<uint value_size>
84 LibTypeCode UInt<value_size>::LibType()
85 {
86 #ifdef TTMATH_PLATFORM32
87 LibTypeCode info = no_asm_32;
88 #endif
89
90 #ifdef TTMATH_PLATFORM64
91 LibTypeCode info = no_asm_64;
92 #endif
93
94 return info;
95 }
96
97
98 /*!
99 this method adds two words together
100 returns carry
101
102 this method is created only when TTMATH_NOASM macro is defined
103 */
104 template<uint value_size>
105 uint UInt<value_size>::AddTwoWords(uint a, uint b, uint carry, uint * result)
106 {
107 uint temp;
108
109 if( carry == 0 )
110 {
111 temp = a + b;
112
113 if( temp < a )
114 carry = 1;
115 }
116 else
117 {
118 carry = 1;
119 temp = a + b + carry;
120
121 if( temp > a ) // !(temp<=a)
122 carry = 0;
123 }
124
125 *result = temp;
126
127 return carry;
128 }
129
130
131
132 /*!
133 this method adding ss2 to the this and adding carry if it's defined
134 (this = this + ss2 + c)
135
136 c must be zero or one (might be a bigger value than 1)
137 function returns carry (1) (if it was)
138 */
139
140 template<uint value_size>
141 uint UInt<value_size>::Add(const UInt<value_size> & ss2, uint c)
142 {
143 uint i;
144
145 for(i=0 ; i<value_size ; ++i)
146 c = AddTwoWords(table[i], ss2.table[i], c, &table[i]);
147
148 TTMATH_LOGC("UInt::Add", c)
149
150 return c;
151 }
152
153
154 /*!
155 this method adds one word (at a specific position)
156 and returns a carry (if it was)
157
158 if we've got (value_size=3):
159 table[0] = 10;
160 table[1] = 30;
161 table[2] = 5;
162 and we call:
163 AddInt(2,1)
164 then it'll be:
165 table[0] = 10;
166 table[1] = 30 + 2;
167 table[2] = 5;
168
169 of course if there was a carry from table[2] it would be returned
170 */
171 template<uint value_size>
172 uint UInt<value_size>::AddInt(uint value, uint index)
173 {
174 uint i, c;
175
176 TTMATH_ASSERT( index < value_size )
177
178
179 c = AddTwoWords(table[index], value, 0, &table[index]);
180
181 for(i=index+1 ; i<value_size && c ; ++i)
182 c = AddTwoWords(table[i], 0, c, &table[i]);
183
184 TTMATH_LOGC("UInt::AddInt", c)
185
186 return c;
187 }
188
189
190
191
192
193 /*!
194 this method adds only two unsigned words to the existing value
195 and these words begin on the 'index' position
196 (it's used in the multiplication algorithm 2)
197
198 index should be equal or smaller than value_size-2 (index <= value_size-2)
199 x1 - lower word, x2 - higher word
200
201 for example if we've got value_size equal 4 and:
202 table[0] = 3
203 table[1] = 4
204 table[2] = 5
205 table[3] = 6
206 then let
207 x1 = 10
208 x2 = 20
209 and
210 index = 1
211
212 the result of this method will be:
213 table[0] = 3
214 table[1] = 4 + x1 = 14
215 table[2] = 5 + x2 = 25
216 table[3] = 6
217
218 and no carry at the end of table[3]
219
220 (of course if there was a carry in table[2](5+20) then
221 this carry would be passed to the table[3] etc.)
222 */
223 template<uint value_size>
224 uint UInt<value_size>::AddTwoInts(uint x2, uint x1, uint index)
225 {
226 uint i, c;
227
228 TTMATH_ASSERT( index < value_size - 1 )
229
230
231 c = AddTwoWords(table[index], x1, 0, &table[index]);
232 c = AddTwoWords(table[index+1], x2, c, &table[index+1]);
233
234 for(i=index+2 ; i<value_size && c ; ++i)
235 c = AddTwoWords(table[i], 0, c, &table[i]);
236
237 TTMATH_LOGC("UInt::AddTwoInts", c)
238
239 return c;
240 }
241
242
243
244 /*!
245 this static method addes one vector to the other
246 'ss1' is larger in size or equal to 'ss2'
247
248 ss1 points to the first (larger) vector
249 ss2 points to the second vector
250 ss1_size - size of the ss1 (and size of the result too)
251 ss2_size - size of the ss2
252 result - is the result vector (which has size the same as ss1: ss1_size)
253
254 Example: ss1_size is 5, ss2_size is 3
255 ss1: ss2: result (output):
256 5 1 5+1
257 4 3 4+3
258 2 7 2+7
259 6 6
260 9 9
261 of course the carry is propagated and will be returned from the last item
262 (this method is used by the Karatsuba multiplication algorithm)
263 */
264 template<uint value_size>
265 uint UInt<value_size>::AddVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result)
266 {
267 uint i, c = 0;
268
269 TTMATH_ASSERT( ss1_size >= ss2_size )
270
271 for(i=0 ; i<ss2_size ; ++i)
272 c = AddTwoWords(ss1[i], ss2[i], c, &result[i]);
273
274 for( ; i<ss1_size ; ++i)
275 c = AddTwoWords(ss1[i], 0, c, &result[i]);
276
277 TTMATH_VECTOR_LOGC("UInt::AddVector", c, result, ss1_size)
278
279 return c;
280 }
281
282
283
284
285 /*!
286 this method subtractes one word from the other
287 returns carry
288
289 this method is created only when TTMATH_NOASM macro is defined
290 */
291 template<uint value_size>
292 uint UInt<value_size>::SubTwoWords(uint a, uint b, uint carry, uint * result)
293 {
294 if( carry == 0 )
295 {
296 *result = a - b;
297
298 if( a < b )
299 carry = 1;
300 }
301 else
302 {
303 carry = 1;
304 *result = a - b - carry;
305
306 if( a > b ) // !(a <= b )
307 carry = 0;
308 }
309
310 return carry;
311 }
312
313
314
315
316 /*!
317 this method's subtracting ss2 from the 'this' and subtracting
318 carry if it has been defined
319 (this = this - ss2 - c)
320
321 c must be zero or one (might be a bigger value than 1)
322 function returns carry (1) (if it was)
323 */
324 template<uint value_size>
325 uint UInt<value_size>::Sub(const UInt<value_size> & ss2, uint c)
326 {
327 uint i;
328
329 for(i=0 ; i<value_size ; ++i)
330 c = SubTwoWords(table[i], ss2.table[i], c, &table[i]);
331
332 TTMATH_LOGC("UInt::Sub", c)
333
334 return c;
335 }
336
337
338
339
340 /*!
341 this method subtracts one word (at a specific position)
342 and returns a carry (if it was)
343
344 if we've got (value_size=3):
345 table[0] = 10;
346 table[1] = 30;
347 table[2] = 5;
348 and we call:
349 SubInt(2,1)
350 then it'll be:
351 table[0] = 10;
352 table[1] = 30 - 2;
353 table[2] = 5;
354
355 of course if there was a carry from table[2] it would be returned
356 */
357 template<uint value_size>
358 uint UInt<value_size>::SubInt(uint value, uint index)
359 {
360 uint i, c;
361
362 TTMATH_ASSERT( index < value_size )
363
364
365 c = SubTwoWords(table[index], value, 0, &table[index]);
366
367 for(i=index+1 ; i<value_size && c ; ++i)
368 c = SubTwoWords(table[i], 0, c, &table[i]);
369
370 TTMATH_LOGC("UInt::SubInt", c)
371
372 return c;
373 }
374
375
376 /*!
377 this static method subtractes one vector from the other
378 'ss1' is larger in size or equal to 'ss2'
379
380 ss1 points to the first (larger) vector
381 ss2 points to the second vector
382 ss1_size - size of the ss1 (and size of the result too)
383 ss2_size - size of the ss2
384 result - is the result vector (which has size the same as ss1: ss1_size)
385
386 Example: ss1_size is 5, ss2_size is 3
387 ss1: ss2: result (output):
388 5 1 5-1
389 4 3 4-3
390 2 7 2-7
391 6 6-1 (the borrow from previous item)
392 9 9
393 return (carry): 0
394 of course the carry (borrow) is propagated and will be returned from the last item
395 (this method is used by the Karatsuba multiplication algorithm)
396 */
397 template<uint value_size>
398 uint UInt<value_size>::SubVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result)
399 {
400 uint i, c = 0;
401
402 TTMATH_ASSERT( ss1_size >= ss2_size )
403
404 for(i=0 ; i<ss2_size ; ++i)
405 c = SubTwoWords(ss1[i], ss2[i], c, &result[i]);
406
407 for( ; i<ss1_size ; ++i)
408 c = SubTwoWords(ss1[i], 0, c, &result[i]);
409
410 TTMATH_VECTOR_LOGC("UInt::SubVector", c, result, ss1_size)
411
412 return c;
413 }
414
415
416
417 /*!
418 this method moves all bits into the left hand side
419 return value <- this <- c
420
421 the lowest *bit* will be held the 'c' and
422 the state of one additional bit (on the left hand side)
423 will be returned
424
425 for example:
426 let this is 001010000
427 after Rcl2_one(1) there'll be 010100001 and Rcl2_one returns 0
428 */
429 template<uint value_size>
430 uint UInt<value_size>::Rcl2_one(uint c)
431 {
432 uint i, new_c;
433
434 if( c != 0 )
435 c = 1;
436
437 for(i=0 ; i<value_size ; ++i)
438 {
439 new_c = (table[i] & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0;
440 table[i] = (table[i] << 1) | c;
441 c = new_c;
442 }
443
444 TTMATH_LOGC("UInt::Rcl2_one", c)
445
446 return c;
447 }
448
449
450
451
452
453
454
455 /*!
456 this method moves all bits into the right hand side
457 c -> this -> return value
458
459 the highest *bit* will be held the 'c' and
460 the state of one additional bit (on the right hand side)
461 will be returned
462
463 for example:
464 let this is 000000010
465 after Rcr2_one(1) there'll be 100000001 and Rcr2_one returns 0
466 */
467 template<uint value_size>
468 uint UInt<value_size>::Rcr2_one(uint c)
469 {
470 sint i; // signed i
471 uint new_c;
472
473 if( c != 0 )
474 c = TTMATH_UINT_HIGHEST_BIT;
475
476 for(i=sint(value_size)-1 ; i>=0 ; --i)
477 {
478 new_c = (table[i] & 1) ? TTMATH_UINT_HIGHEST_BIT : 0;
479 table[i] = (table[i] >> 1) | c;
480 c = new_c;
481 }
482
483 c = (c != 0)? 1 : 0;
484
485 TTMATH_LOGC("UInt::Rcr2_one", c)
486
487 return c;
488 }
489
490
491
492
493 /*!
494 this method moves all bits into the left hand side
495 return value <- this <- c
496
497 the lowest *bits* will be held the 'c' and
498 the state of one additional bit (on the left hand side)
499 will be returned
500
501 for example:
502 let this is 001010000
503 after Rcl2(3, 1) there'll be 010000111 and Rcl2 returns 1
504 */
505 template<uint value_size>
506 uint UInt<value_size>::Rcl2(uint bits, uint c)
507 {
508 TTMATH_ASSERT( bits>0 && bits<TTMATH_BITS_PER_UINT )
509
510 uint move = TTMATH_BITS_PER_UINT - bits;
511 uint i, new_c;
512
513 if( c != 0 )
514 c = TTMATH_UINT_MAX_VALUE >> move;
515
516 for(i=0 ; i<value_size ; ++i)
517 {
518 new_c = table[i] >> move;
519 table[i] = (table[i] << bits) | c;
520 c = new_c;
521 }
522
523 TTMATH_LOGC("UInt::Rcl2", (c & 1))
524
525 return (c & 1);
526 }
527
528
529
530
531 /*!
532 this method moves all bits into the right hand side
533 C -> this -> return value
534
535 the highest *bits* will be held the 'c' and
536 the state of one additional bit (on the right hand side)
537 will be returned
538
539 for example:
540 let this is 000000010
541 after Rcr2(2, 1) there'll be 110000000 and Rcr2 returns 1
542 */
543 template<uint value_size>
544 uint UInt<value_size>::Rcr2(uint bits, uint c)
545 {
546 TTMATH_ASSERT( bits>0 && bits<TTMATH_BITS_PER_UINT )
547
548 uint move = TTMATH_BITS_PER_UINT - bits;
549 sint i; // signed
550 uint new_c;
551
552 if( c != 0 )
553 c = TTMATH_UINT_MAX_VALUE << move;
554
555 for(i=value_size-1 ; i>=0 ; --i)
556 {
557 new_c = table[i] << move;
558 table[i] = (table[i] >> bits) | c;
559 c = new_c;
560 }
561
562 c = (c & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0;
563
564 TTMATH_LOGC("UInt::Rcr2", c)
565
566 return c;
567 }
568
569
570
571
572 /*!
573 this method returns the number of the highest set bit in x
574 if the 'x' is zero this method returns '-1'
575 */
576 template<uint value_size>
577 sint UInt<value_size>::FindLeadingBitInWord(uint x)
578 {
579 if( x == 0 )
580 return -1;
581
582 uint bit = TTMATH_BITS_PER_UINT - 1;
583
584 while( (x & TTMATH_UINT_HIGHEST_BIT) == 0 )
585 {
586 x = x << 1;
587 --bit;
588 }
589
590 return bit;
591 }
592
593
594
595 /*!
596 this method returns the number of the highest set bit in x
597 if the 'x' is zero this method returns '-1'
598 */
599 template<uint value_size>
600 sint UInt<value_size>::FindLowestBitInWord(uint x)
601 {
602 if( x == 0 )
603 return -1;
604
605 uint bit = 0;
606
607 while( (x & 1) == 0 )
608 {
609 x = x >> 1;
610 ++bit;
611 }
612
613 return bit;
614 }
615
616
617
618 /*!
619 this method sets a special bit in the 'value'
620 and returns the last state of the bit (zero or one)
621
622 bit is from <0,TTMATH_BITS_PER_UINT-1>
623
624 e.g.
625 uint x = 100;
626 uint bit = SetBitInWord(x, 3);
627 now: x = 108 and bit = 0
628 */
629 template<uint value_size>
630 uint UInt<value_size>::SetBitInWord(uint & value, uint bit)
631 {
632 TTMATH_ASSERT( bit < TTMATH_BITS_PER_UINT )
633
634 uint mask = 1;
635
636 if( bit > 0 )
637 mask = mask << bit;
638
639 uint last = value & mask;
640 value = value | mask;
641
642 return (last != 0) ? 1 : 0;
643 }
644
645
646
647
648
649
650 /*!
651 *
652 * Multiplication
653 *
654 *
655 */
656
657
658 /*!
659 multiplication: result_high:result_low = a * b
660 result_high - higher word of the result
661 result_low - lower word of the result
662
663 this methos never returns a carry
664 this method is used in the second version of the multiplication algorithms
665 */
666 template<uint value_size>
667 void UInt<value_size>::MulTwoWords(uint a, uint b, uint * result_high, uint * result_low)
668 {
669 #ifdef TTMATH_PLATFORM32
670
671 /*
672 on 32bit platforms we have defined 'unsigned long long int' type known as 'ulint' in ttmath namespace
673 this type has 64 bits, then we're using only one multiplication: 32bit * 32bit = 64bit
674 */
675
676 union uint_
677 {
678 struct
679 {
680 uint low; // 32 bits
681 uint high; // 32 bits
682 } u_;
683
684 ulint u; // 64 bits
685 } res;
686
687 res.u = ulint(a) * ulint(b); // multiply two 32bit words, the result has 64 bits
688
689 *result_high = res.u_.high;
690 *result_low = res.u_.low;
691
692 #else
693
694 /*
695 64 bits platforms
696
697 we don't have a native type which has 128 bits
698 then we're splitting 'a' and 'b' to 4 parts (high and low halves)
699 and using 4 multiplications (with additions and carry correctness)
700 */
701
702 uint_ a_;
703 uint_ b_;
704 uint_ res_high1, res_high2;
705 uint_ res_low1, res_low2;
706
707 a_.u = a;
708 b_.u = b;
709
710 /*
711 the multiplication is as follows (schoolbook algorithm with O(n^2) ):
712
713 32 bits 32 bits
714
715 +--------------------------------+
716 | a_.u_.high | a_.u_.low |
717 +--------------------------------+
718 | b_.u_.high | b_.u_.low |
719 +--------------------------------+--------------------------------+
720 | res_high1.u | res_low1.u |
721 +--------------------------------+--------------------------------+
722 | res_high2.u | res_low2.u |
723 +--------------------------------+--------------------------------+
724
725 64 bits 64 bits
726 */
727
728
729 uint_ temp;
730
731 res_low1.u = uint(b_.u_.low) * uint(a_.u_.low);
732
733 temp.u = uint(res_low1.u_.high) + uint(b_.u_.low) * uint(a_.u_.high);
734 res_low1.u_.high = temp.u_.low;
735 res_high1.u_.low = temp.u_.high;
736 res_high1.u_.high = 0;
737
738 res_low2.u_.low = 0;
739 temp.u = uint(b_.u_.high) * uint(a_.u_.low);
740 res_low2.u_.high = temp.u_.low;
741
742 res_high2.u = uint(b_.u_.high) * uint(a_.u_.high) + uint(temp.u_.high);
743
744 uint c = AddTwoWords(res_low1.u, res_low2.u, 0, &res_low2.u);
745 AddTwoWords(res_high1.u, res_high2.u, c, &res_high2.u); // there is no carry from here
746
747 *result_high = res_high2.u;
748 *result_low = res_low2.u;
749
750 #endif
751 }
752
753
754
755
756 /*!
757 *
758 * Division
759 *
760 *
761 */
762
763
764 /*!
765 this method calculates 64bits word a:b / 32bits c (a higher, b lower word)
766 r = a:b / c and rest - remainder
767
768 *
769 * WARNING:
770 * the c has to be suitably large for the result being keeped in one word,
771 * if c is equal zero there'll be a hardware interruption (0)
772 * and probably the end of your program
773 *
774 */
775 template<uint value_size>
776 void UInt<value_size>::DivTwoWords(uint a, uint b, uint c, uint * r, uint * rest)
777 {
778 // (a < c ) for the result to be one word
779 TTMATH_ASSERT( c != 0 && a < c )
780
781 #ifdef TTMATH_PLATFORM32
782
783 union
784 {
785 struct
786 {
787 uint low; // 32 bits
788 uint high; // 32 bits
789 } u_;
790
791 ulint u; // 64 bits
792 } ab;
793
794 ab.u_.high = a;
795 ab.u_.low = b;
796
797 *r = uint(ab.u / c);
798 *rest = uint(ab.u % c);
799
800 #else
801
802 uint_ c_;
803 c_.u = c;
804
805
806 if( a == 0 )
807 {
808 *r = b / c;
809 *rest = b % c;
810 }
811 else
812 if( c_.u_.high == 0 )
813 {
814 // higher half of 'c' is zero
815 // then higher half of 'a' is zero too (look at the asserts at the beginning - 'a' is smaller than 'c')
816 uint_ a_, b_, res_, temp1, temp2;
817
818 a_.u = a;
819 b_.u = b;
820
821 temp1.u_.high = a_.u_.low;
822 temp1.u_.low = b_.u_.high;
823
824 res_.u_.high = (unsigned int)(temp1.u / c);
825 temp2.u_.high = (unsigned int)(temp1.u % c);
826 temp2.u_.low = b_.u_.low;
827
828 res_.u_.low = (unsigned int)(temp2.u / c);
829 *rest = temp2.u % c;
830
831 *r = res_.u;
832 }
833 else
834 {
835 return DivTwoWords2(a, b, c, r, rest);
836 }
837
838 #endif
839 }
840
841
842 #ifdef TTMATH_PLATFORM64
843
844
845 /*!
846 this method is available only on 64bit platforms
847
848 the same algorithm like the third division algorithm in ttmathuint.h
849 but now with the radix=2^32
850 */
851 template<uint value_size>
852 void UInt<value_size>::DivTwoWords2(uint a, uint b, uint c, uint * r, uint * rest)
853 {
854 // a is not zero
855 // c_.u_.high is not zero
856
857 uint_ a_, b_, c_, u_, q_;
858 unsigned int u3; // 32 bit
859
860 a_.u = a;
861 b_.u = b;
862 c_.u = c;
863
864 // normalizing
865 uint d = DivTwoWordsNormalize(a_, b_, c_);
866
867 // loop from j=1 to j=0
868 // the first step (for j=2) is skipped because our result is only in one word,
869 // (first 'q' were 0 and nothing would be changed)
870 u_.u_.high = a_.u_.high;
871 u_.u_.low = a_.u_.low;
872 u3 = b_.u_.high;
873 q_.u_.high = DivTwoWordsCalculate(u_, u3, c_);
874 MultiplySubtract(u_, u3, q_.u_.high, c_);
875
876 u_.u_.high = u_.u_.low;
877 u_.u_.low = u3;
878 u3 = b_.u_.low;
879 q_.u_.low = DivTwoWordsCalculate(u_, u3, c_);
880 MultiplySubtract(u_, u3, q_.u_.low, c_);
881
882 *r = q_.u;
883
884 // unnormalizing for the remainder
885 u_.u_.high = u_.u_.low;
886 u_.u_.low = u3;
887 *rest = DivTwoWordsUnnormalize(u_.u, d);
888 }
889
890
891
892
893 template<uint value_size>
894 uint UInt<value_size>::DivTwoWordsNormalize(uint_ & a_, uint_ & b_, uint_ & c_)
895 {
896 uint d = 0;
897
898 for( ; (c_.u & TTMATH_UINT_HIGHEST_BIT) == 0 ; ++d )
899 {
900 c_.u = c_.u << 1;
901
902 uint bc = b_.u & TTMATH_UINT_HIGHEST_BIT; // carry from 'b'
903
904 b_.u = b_.u << 1;
905 a_.u = a_.u << 1; // carry bits from 'a' are simply skipped
906
907 if( bc )
908 a_.u = a_.u | 1;
909 }
910
911 return d;
912 }
913
914
915 template<uint value_size>
916 uint UInt<value_size>::DivTwoWordsUnnormalize(uint u, uint d)
917 {
918 if( d == 0 )
919 return u;
920
921 u = u >> d;
922
923 return u;
924 }
925
926
927 template<uint value_size>
928 unsigned int UInt<value_size>::DivTwoWordsCalculate(uint_ u_, unsigned int u3, uint_ v_)
929 {
930 bool next_test;
931 uint_ qp_, rp_, temp_;
932
933 qp_.u = u_.u / uint(v_.u_.high);
934 rp_.u = u_.u % uint(v_.u_.high);
935
936 TTMATH_ASSERT( qp_.u_.high==0 || qp_.u_.high==1 )
937
938 do
939 {
940 bool decrease = false;
941
942 if( qp_.u_.high == 1 )
943 decrease = true;
944 else
945 {
946 temp_.u_.high = rp_.u_.low;
947 temp_.u_.low = u3;
948
949 if( qp_.u * uint(v_.u_.low) > temp_.u )
950 decrease = true;
951 }
952
953 next_test = false;
954
955 if( decrease )
956 {
957 --qp_.u;
958 rp_.u += v_.u_.high;
959
960 if( rp_.u_.high == 0 )
961 next_test = true;
962 }
963 }
964 while( next_test );
965
966 return qp_.u_.low;
967 }
968
969
970 template<uint value_size>
971 void UInt<value_size>::MultiplySubtract(uint_ & u_, unsigned int & u3, unsigned int & q, uint_ v_)
972 {
973 uint_ temp_;
974
975 uint res_high;
976 uint res_low;
977
978 MulTwoWords(v_.u, q, &res_high, &res_low);
979
980 uint_ sub_res_high_;
981 uint_ sub_res_low_;
982
983 temp_.u_.high = u_.u_.low;
984 temp_.u_.low = u3;
985
986 uint c = SubTwoWords(temp_.u, res_low, 0, &sub_res_low_.u);
987
988 temp_.u_.high = 0;
989 temp_.u_.low = u_.u_.high;
990 c = SubTwoWords(temp_.u, res_high, c, &sub_res_high_.u);
991
992 if( c )
993 {
994 --q;
995
996 c = AddTwoWords(sub_res_low_.u, v_.u, 0, &sub_res_low_.u);
997 AddTwoWords(sub_res_high_.u, 0, c, &sub_res_high_.u);
998 }
999
1000 u_.u_.high = sub_res_high_.u_.low;
1001 u_.u_.low = sub_res_low_.u_.high;
1002 u3 = sub_res_low_.u_.low;
1003 }
1004
1005 #endif // #ifdef TTMATH_PLATFORM64
1006
1007
1008
1009 } //namespace
1010
1011
1012 #endif //ifdef TTMATH_NOASM
1013 #endif
1014
1015
1016
1017