Debian Codegraph @

extern/ttmath/ttmathuint.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-2011, 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
39
40 #ifndef headerfilettmathuint
41 #define headerfilettmathuint
42
43
44 /*!
45 \file ttmathuint.h
46 \brief template class UInt<uint>
47 */
48
49 #include <iostream>
50 #include <iomanip>
51
52
53 #include "ttmathtypes.h"
54 #include "ttmathmisc.h"
55
56
57
58 /*!
59 \brief a namespace for the TTMath library
60 */
61 namespace ttmath
62 {
63
64 /*!
65 \brief UInt implements a big integer value without a sign
66
67 value_size - how many bytes specify our value
68 on 32bit platforms: value_size=1 -> 4 bytes -> 32 bits
69 on 64bit platforms: value_size=1 -> 8 bytes -> 64 bits
70 value_size = 1,2,3,4,5,6....
71 */
72 template<uint value_size>
73 class UInt
74 {
75 public:
76
77 /*!
78 buffer for the integer value
79 table[0] - the lowest word of the value
80 */
81 uint table[value_size];
82
83
84
85 /*!
86 some methods used for debugging purposes
87 */
88
89
90 /*!
91 this method is used when macro TTMATH_DEBUG_LOG is defined
92 */
93 template<class char_type, class ostream_type>
94 static void PrintVectorLog(const char_type * msg, ostream_type & output, const uint * vector, uint vector_len)
95 {
96 output << msg << std::endl;
97
98 for(uint i=0 ; i<vector_len ; ++i)
99 output << " table[" << i << "]: " << vector[i] << std::endl;
100 }
101
102
103 /*!
104 this method is used when macro TTMATH_DEBUG_LOG is defined
105 */
106 template<class char_type, class ostream_type>
107 static void PrintVectorLog(const char_type * msg, uint carry, ostream_type & output, const uint * vector, uint vector_len)
108 {
109 PrintVectorLog(msg, output, vector, vector_len);
110 output << " carry: " << carry << std::endl;
111 }
112
113
114 /*!
115 this method is used when macro TTMATH_DEBUG_LOG is defined
116 */
117 template<class char_type, class ostream_type>
118 void PrintLog(const char_type * msg, ostream_type & output) const
119 {
120 PrintVectorLog(msg, output, table, value_size);
121 }
122
123
124 /*!
125 this method is used when macro TTMATH_DEBUG_LOG is defined
126 */
127 template<class char_type, class ostream_type>
128 void PrintLog(const char_type * msg, uint carry, ostream_type & output) const
129 {
130 PrintVectorLog(msg, output, table, value_size);
131 output << " carry: " << carry << std::endl;
132 }
133
134
135 /*!
136 this method returns the size of the table
137 */
138 uint Size() const
139 {
140 return value_size;
141 }
142
143
144 /*!
145 this method sets zero
146 */
147 void SetZero()
148 {
149 // in the future here can be 'memset'
150
151 for(uint i=0 ; i<value_size ; ++i)
152 table[i] = 0;
153
154 TTMATH_LOG("UInt::SetZero")
155 }
156
157
158 /*!
159 this method sets one
160 */
161 void SetOne()
162 {
163 SetZero();
164 table[0] = 1;
165
166 TTMATH_LOG("UInt::SetOne")
167 }
168
169
170 /*!
171 this method sets the max value which this class can hold
172 (all bits will be one)
173 */
174 void SetMax()
175 {
176 for(uint i=0 ; i<value_size ; ++i)
177 table[i] = TTMATH_UINT_MAX_VALUE;
178
179 TTMATH_LOG("UInt::SetMax")
180 }
181
182
183 /*!
184 this method sets the min value which this class can hold
185 (for an unsigned integer value the zero is the smallest value)
186 */
187 void SetMin()
188 {
189 SetZero();
190
191 TTMATH_LOG("UInt::SetMin")
192 }
193
194
195 /*!
196 this method swappes this for an argument
197 */
198 void Swap(UInt<value_size> & ss2)
199 {
200 for(uint i=0 ; i<value_size ; ++i)
201 {
202 uint temp = table[i];
203 table[i] = ss2.table[i];
204 ss2.table[i] = temp;
205 }
206 }
207
208
209 #ifdef TTMATH_PLATFORM32
210
211 /*!
212 this method copies the value stored in an another table
213 (warning: first values in temp_table are the highest words -- it's different
214 from our table)
215
216 we copy as many words as it is possible
217
218 if temp_table_len is bigger than value_size we'll try to round
219 the lowest word from table depending on the last not used bit in temp_table
220 (this rounding isn't a perfect rounding -- look at the description below)
221
222 and if temp_table_len is smaller than value_size we'll clear the rest words
223 in the table
224 */
225 void SetFromTable(const uint * temp_table, uint temp_table_len)
226 {
227 uint temp_table_index = 0;
228 sint i; // 'i' with a sign
229
230 for(i=value_size-1 ; i>=0 && temp_table_index<temp_table_len; --i, ++temp_table_index)
231 table[i] = temp_table[ temp_table_index ];
232
233
234 // rounding mantissa
235 if( temp_table_index < temp_table_len )
236 {
237 if( (temp_table[temp_table_index] & TTMATH_UINT_HIGHEST_BIT) != 0 )
238 {
239 /*
240 very simply rounding
241 if the bit from not used last word from temp_table is set to one
242 we're rouding the lowest word in the table
243
244 in fact there should be a normal addition but
245 we don't use Add() or AddTwoInts() because these methods
246 can set a carry and then there'll be a small problem
247 for optimization
248 */
249 if( table[0] != TTMATH_UINT_MAX_VALUE )
250 ++table[0];
251 }
252 }
253
254 // cleaning the rest of the mantissa
255 for( ; i>=0 ; --i)
256 table[i] = 0;
257
258
259 TTMATH_LOG("UInt::SetFromTable")
260 }
261
262 #endif
263
264
265 #ifdef TTMATH_PLATFORM64
266 /*!
267 this method copies the value stored in an another table
268 (warning: first values in temp_table are the highest words -- it's different
269 from our table)
270
271 ***this method is created only on a 64bit platform***
272
273 we copy as many words as it is possible
274
275 if temp_table_len is bigger than value_size we'll try to round
276 the lowest word from table depending on the last not used bit in temp_table
277 (this rounding isn't a perfect rounding -- look at the description below)
278
279 and if temp_table_len is smaller than value_size we'll clear the rest words
280 in the table
281
282 warning: we're using 'temp_table' as a pointer at 32bit words
283 */
284 void SetFromTable(const unsigned int * temp_table, uint temp_table_len)
285 {
286 uint temp_table_index = 0;
287 sint i; // 'i' with a sign
288
289 for(i=value_size-1 ; i>=0 && temp_table_index<temp_table_len; --i, ++temp_table_index)
290 {
291 table[i] = uint(temp_table[ temp_table_index ]) << 32;
292
293 ++temp_table_index;
294
295 if( temp_table_index<temp_table_len )
296 table[i] |= temp_table[ temp_table_index ];
297 }
298
299
300 // rounding mantissa
301 if( temp_table_index < temp_table_len )
302 {
303 if( (temp_table[temp_table_index] & TTMATH_UINT_HIGHEST_BIT) != 0 )
304 {
305 /*
306 very simply rounding
307 if the bit from not used last word from temp_table is set to one
308 we're rouding the lowest word in the table
309
310 in fact there should be a normal addition but
311 we don't use Add() or AddTwoInts() because these methods
312 can set a carry and then there'll be a small problem
313 for optimization
314 */
315 if( table[0] != TTMATH_UINT_MAX_VALUE )
316 ++table[0];
317 }
318 }
319
320 // cleaning the rest of the mantissa
321 for( ; i >= 0 ; --i)
322 table[i] = 0;
323
324 TTMATH_LOG("UInt::SetFromTable")
325 }
326
327 #endif
328
329
330
331
332
333 /*!
334 *
335 * basic mathematic functions
336 *
337 */
338
339
340
341
342 /*!
343 this method adds one to the existing value
344 */
345 uint AddOne()
346 {
347 return AddInt(1);
348 }
349
350
351 /*!
352 this method subtracts one from the existing value
353 */
354 uint SubOne()
355 {
356 return SubInt(1);
357 }
358
359
360 private:
361
362
363 /*!
364 an auxiliary method for moving bits into the left hand side
365
366 this method moves only words
367 */
368 void RclMoveAllWords(uint & rest_bits, uint & last_c, uint bits, uint c)
369 {
370 rest_bits = bits % TTMATH_BITS_PER_UINT;
371 uint all_words = bits / TTMATH_BITS_PER_UINT;
372 uint mask = ( c ) ? TTMATH_UINT_MAX_VALUE : 0;
373
374
375 if( all_words >= value_size )
376 {
377 if( all_words == value_size && rest_bits == 0 )
378 last_c = table[0] & 1;
379 // else: last_c is default set to 0
380
381 // clearing
382 for(uint i = 0 ; i<value_size ; ++i)
383 table[i] = mask;
384
385 rest_bits = 0;
386 }
387 else
388 if( all_words > 0 )
389 {
390 // 0 < all_words < value_size
391
392 sint first, second;
393 last_c = table[value_size - all_words] & 1; // all_words is greater than 0
394
395 // copying the first part of the value
396 for(first = value_size-1, second=first-all_words ; second>=0 ; --first, --second)
397 table[first] = table[second];
398
399 // setting the rest to 'c'
400 for( ; first>=0 ; --first )
401 table[first] = mask;
402 }
403
404 TTMATH_LOG("UInt::RclMoveAllWords")
405 }
406
407 public:
408
409 /*!
410 moving all bits into the left side 'bits' times
411 return value <- this <- C
412
413 bits is from a range of <0, man * TTMATH_BITS_PER_UINT>
414 or it can be even bigger then all bits will be set to 'c'
415
416 the value c will be set into the lowest bits
417 and the method returns state of the last moved bit
418 */
419 uint Rcl(uint bits, uint c=0)
420 {
421 uint last_c = 0;
422 uint rest_bits = bits;
423
424 if( bits == 0 )
425 return 0;
426
427 if( bits >= TTMATH_BITS_PER_UINT )
428 RclMoveAllWords(rest_bits, last_c, bits, c);
429
430 if( rest_bits == 0 )
431 {
432 TTMATH_LOG("UInt::Rcl")
433 return last_c;
434 }
435
436 // rest_bits is from 1 to TTMATH_BITS_PER_UINT-1 now
437 if( rest_bits == 1 )
438 {
439 last_c = Rcl2_one(c);
440 }
441 else if( rest_bits == 2 )
442 {
443 // performance tests showed that for rest_bits==2 it's better to use Rcl2_one twice instead of Rcl2(2,c)
444 Rcl2_one(c);
445 last_c = Rcl2_one(c);
446 }
447 else
448 {
449 last_c = Rcl2(rest_bits, c);
450 }
451
452 TTMATH_LOGC("UInt::Rcl", last_c)
453
454 return last_c;
455 }
456
457 private:
458
459 /*!
460 an auxiliary method for moving bits into the right hand side
461
462 this method moves only words
463 */
464 void RcrMoveAllWords(uint & rest_bits, uint & last_c, uint bits, uint c)
465 {
466 rest_bits = bits % TTMATH_BITS_PER_UINT;
467 uint all_words = bits / TTMATH_BITS_PER_UINT;
468 uint mask = ( c ) ? TTMATH_UINT_MAX_VALUE : 0;
469
470
471 if( all_words >= value_size )
472 {
473 if( all_words == value_size && rest_bits == 0 )
474 last_c = (table[value_size-1] & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0;
475 // else: last_c is default set to 0
476
477 // clearing
478 for(uint i = 0 ; i<value_size ; ++i)
479 table[i] = mask;
480
481 rest_bits = 0;
482 }
483 else if( all_words > 0 )
484 {
485 // 0 < all_words < value_size
486
487 uint first, second;
488 last_c = (table[all_words - 1] & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0; // all_words is > 0
489
490 // copying the first part of the value
491 for(first=0, second=all_words ; second<value_size ; ++first, ++second)
492 table[first] = table[second];
493
494 // setting the rest to 'c'
495 for( ; first<value_size ; ++first )
496 table[first] = mask;
497 }
498
499 TTMATH_LOG("UInt::RcrMoveAllWords")
500 }
501
502 public:
503
504 /*!
505 moving all bits into the right side 'bits' times
506 c -> this -> return value
507
508 bits is from a range of <0, man * TTMATH_BITS_PER_UINT>
509 or it can be even bigger then all bits will be set to 'c'
510
511 the value c will be set into the highest bits
512 and the method returns state of the last moved bit
513 */
514 uint Rcr(uint bits, uint c=0)
515 {
516 uint last_c = 0;
517 uint rest_bits = bits;
518
519 if( bits == 0 )
520 return 0;
521
522 if( bits >= TTMATH_BITS_PER_UINT )
523 RcrMoveAllWords(rest_bits, last_c, bits, c);
524
525 if( rest_bits == 0 )
526 {
527 TTMATH_LOG("UInt::Rcr")
528 return last_c;
529 }
530
531 // rest_bits is from 1 to TTMATH_BITS_PER_UINT-1 now
532 if( rest_bits == 1 )
533 {
534 last_c = Rcr2_one(c);
535 }
536 else if( rest_bits == 2 )
537 {
538 // performance tests showed that for rest_bits==2 it's better to use Rcr2_one twice instead of Rcr2(2,c)
539 Rcr2_one(c);
540 last_c = Rcr2_one(c);
541 }
542 else
543 {
544 last_c = Rcr2(rest_bits, c);
545 }
546
547 TTMATH_LOGC("UInt::Rcr", last_c)
548
549 return last_c;
550 }
551
552
553 /*!
554 this method moves all bits into the left side
555 (it returns value how many bits have been moved)
556 */
557 uint CompensationToLeft()
558 {
559 uint moving = 0;
560
561 // a - index a last word which is different from zero
562 sint a;
563 for(a=value_size-1 ; a>=0 && table[a]==0 ; --a);
564
565 if( a < 0 )
566 return moving; // all words in table have zero
567
568 if( a != value_size-1 )
569 {
570 moving += ( value_size-1 - a ) * TTMATH_BITS_PER_UINT;
571
572 // moving all words
573 sint i;
574 for(i=value_size-1 ; a>=0 ; --i, --a)
575 table[i] = table[a];
576
577 // setting the rest word to zero
578 for(; i>=0 ; --i)
579 table[i] = 0;
580 }
581
582 uint moving2 = FindLeadingBitInWord( table[value_size-1] );
583 // moving2 is different from -1 because the value table[value_size-1]
584 // is not zero
585
586 moving2 = TTMATH_BITS_PER_UINT - moving2 - 1;
587 Rcl(moving2);
588
589 TTMATH_LOG("UInt::CompensationToLeft")
590
591 return moving + moving2;
592 }
593
594
595 /*!
596 this method looks for the highest set bit
597
598 result:
599 if 'this' is not zero:
600 return value - true
601 'table_id' - the index of a word <0..value_size-1>
602 'index' - the index of this set bit in the word <0..TTMATH_BITS_PER_UINT)
603
604 if 'this' is zero:
605 return value - false
606 both 'table_id' and 'index' are zero
607 */
608 bool FindLeadingBit(uint & table_id, uint & index) const
609 {
610 for(table_id=value_size-1 ; table_id!=0 && table[table_id]==0 ; --table_id);
611
612 if( table_id==0 && table[table_id]==0 )
613 {
614 // is zero
615 index = 0;
616
617 return false;
618 }
619
620 // table[table_id] is different from 0
621 index = FindLeadingBitInWord( table[table_id] );
622
623 return true;
624 }
625
626
627 /*!
628 this method looks for the smallest set bit
629
630 result:
631 if 'this' is not zero:
632 return value - true
633 'table_id' - the index of a word <0..value_size-1>
634 'index' - the index of this set bit in the word <0..TTMATH_BITS_PER_UINT)
635
636 if 'this' is zero:
637 return value - false
638 both 'table_id' and 'index' are zero
639 */
640 bool FindLowestBit(uint & table_id, uint & index) const
641 {
642 for(table_id=0 ; table_id<value_size && table[table_id]==0 ; ++table_id);
643
644 if( table_id >= value_size )
645 {
646 // is zero
647 index = 0;
648 table_id = 0;
649
650 return false;
651 }
652
653 // table[table_id] is different from 0
654 index = FindLowestBitInWord( table[table_id] );
655
656 return true;
657 }
658
659
660 /*!
661 getting the 'bit_index' bit
662
663 bit_index bigger or equal zero
664 */
665 uint GetBit(uint bit_index) const
666 {
667 TTMATH_ASSERT( bit_index < value_size * TTMATH_BITS_PER_UINT )
668
669 uint index = bit_index / TTMATH_BITS_PER_UINT;
670 uint bit = bit_index % TTMATH_BITS_PER_UINT;
671
672 uint temp = table[index];
673 uint res = SetBitInWord(temp, bit);
674
675 return res;
676 }
677
678
679 /*!
680 setting the 'bit_index' bit
681 and returning the last state of the bit
682
683 bit_index bigger or equal zero
684 */
685 uint SetBit(uint bit_index)
686 {
687 TTMATH_ASSERT( bit_index < value_size * TTMATH_BITS_PER_UINT )
688
689 uint index = bit_index / TTMATH_BITS_PER_UINT;
690 uint bit = bit_index % TTMATH_BITS_PER_UINT;
691 uint res = SetBitInWord(table[index], bit);
692
693 TTMATH_LOG("UInt::SetBit")
694
695 return res;
696 }
697
698
699 /*!
700 this method performs a bitwise operation AND
701 */
702 void BitAnd(const UInt<value_size> & ss2)
703 {
704 for(uint x=0 ; x<value_size ; ++x)
705 table[x] &= ss2.table[x];
706
707 TTMATH_LOG("UInt::BitAnd")
708 }
709
710
711 /*!
712 this method performs a bitwise operation OR
713 */
714 void BitOr(const UInt<value_size> & ss2)
715 {
716 for(uint x=0 ; x<value_size ; ++x)
717 table[x] |= ss2.table[x];
718
719 TTMATH_LOG("UInt::BitOr")
720 }
721
722
723 /*!
724 this method performs a bitwise operation XOR
725 */
726 void BitXor(const UInt<value_size> & ss2)
727 {
728 for(uint x=0 ; x<value_size ; ++x)
729 table[x] ^= ss2.table[x];
730
731 TTMATH_LOG("UInt::BitXor")
732 }
733
734
735 /*!
736 this method performs a bitwise operation NOT
737 */
738 void BitNot()
739 {
740 for(uint x=0 ; x<value_size ; ++x)
741 table[x] = ~table[x];
742
743 TTMATH_LOG("UInt::BitNot")
744 }
745
746
747 /*!
748 this method performs a bitwise operation NOT but only
749 on the range of <0, leading_bit>
750
751 for example:
752 BitNot2(8) = BitNot2( 1000(bin) ) = 111(bin) = 7
753 */
754 void BitNot2()
755 {
756 uint table_id, index;
757
758 if( FindLeadingBit(table_id, index) )
759 {
760 for(uint x=0 ; x<table_id ; ++x)
761 table[x] = ~table[x];
762
763 uint mask = TTMATH_UINT_MAX_VALUE;
764 uint shift = TTMATH_BITS_PER_UINT - index - 1;
765
766 if(shift)
767 mask >>= shift;
768
769 table[table_id] ^= mask;
770 }
771 else
772 table[0] = 1;
773
774
775 TTMATH_LOG("UInt::BitNot2")
776 }
777
778
779
780 /*!
781 *
782 * Multiplication
783 *
784 *
785 */
786
787 public:
788
789 /*!
790 multiplication: this = this * ss2
791
792 it can return a carry
793 */
794 uint MulInt(uint ss2)
795 {
796 uint r1, r2, x1;
797 uint c = 0;
798
799 UInt<value_size> u(*this);
800 SetZero();
801
802 if( ss2 == 0 )
803 {
804 TTMATH_LOGC("UInt::MulInt(uint)", 0)
805 return 0;
806 }
807
808 for(x1=0 ; x1<value_size-1 ; ++x1)
809 {
810 MulTwoWords(u.table[x1], ss2, &r2, &r1);
811 c += AddTwoInts(r2,r1,x1);
812 }
813
814 // x1 = value_size-1 (last word)
815 MulTwoWords(u.table[x1], ss2, &r2, &r1);
816 c += (r2!=0) ? 1 : 0;
817 c += AddInt(r1, x1);
818
819 TTMATH_LOGC("UInt::MulInt(uint)", c)
820
821 return (c==0)? 0 : 1;
822 }
823
824
825 /*!
826 multiplication: result = this * ss2
827
828 we're using this method only when result_size is greater than value_size
829 if so there will not be a carry
830 */
831 template<uint result_size>
832 void MulInt(uint ss2, UInt<result_size> & result) const
833 {
834 TTMATH_ASSERT( result_size > value_size )
835
836 uint r2,r1;
837 uint x1size=value_size;
838 uint x1start=0;
839
840 result.SetZero();
841
842 if( ss2 == 0 )
843 {
844 TTMATH_VECTOR_LOG("UInt::MulInt(uint, UInt<>)", result.table, result_size)
845 return;
846 }
847
848 if( value_size > 2 )
849 {
850 // if the value_size is smaller than or equal to 2
851 // there is no sense to set x1size and x1start to another values
852
853 for(x1size=value_size ; x1size>0 && table[x1size-1]==0 ; --x1size);
854
855 if( x1size == 0 )
856 {
857 TTMATH_VECTOR_LOG("UInt::MulInt(uint, UInt<>)", result.table, result_size)
858 return;
859 }
860
861 for(x1start=0 ; x1start<x1size && table[x1start]==0 ; ++x1start);
862 }
863
864 for(uint x1=x1start ; x1<x1size ; ++x1)
865 {
866 MulTwoWords(table[x1], ss2, &r2, &r1 );
867 result.AddTwoInts(r2,r1,x1);
868 }
869
870 TTMATH_VECTOR_LOG("UInt::MulInt(uint, UInt<>)", result.table, result_size)
871
872 return;
873 }
874
875
876
877 /*!
878 the multiplication 'this' = 'this' * ss2
879
880 algorithm: 100 - means automatically choose the fastest algorithm
881 */
882 uint Mul(const UInt<value_size> & ss2, uint algorithm = 100)
883 {
884 switch( algorithm )
885 {
886 case 1:
887 return Mul1(ss2);
888
889 case 2:
890 return Mul2(ss2);
891
892 case 3:
893 return Mul3(ss2);
894
895 case 100:
896 default:
897 return MulFastest(ss2);
898 }
899 }
900
901
902 /*!
903 the multiplication 'result' = 'this' * ss2
904
905 since the 'result' is twice bigger than 'this' and 'ss2'
906 this method never returns a carry
907
908 algorithm: 100 - means automatically choose the fastest algorithm
909 */
910 void MulBig(const UInt<value_size> & ss2,
911 UInt<value_size*2> & result,
912 uint algorithm = 100)
913 {
914 switch( algorithm )
915 {
916 case 1:
917 return Mul1Big(ss2, result);
918
919 case 2:
920 return Mul2Big(ss2, result);
921
922 case 3:
923 return Mul3Big(ss2, result);
924
925 case 100:
926 default:
927 return MulFastestBig(ss2, result);
928 }
929 }
930
931
932
933 /*!
934 the first version of the multiplication algorithm
935 */
936
937 private:
938
939 /*!
940 multiplication: this = this * ss2
941
942 it returns carry if it has been
943 */
944 uint Mul1Ref(const UInt<value_size> & ss2)
945 {
946 TTMATH_REFERENCE_ASSERT( ss2 )
947
948 UInt<value_size> ss1( *this );
949 SetZero();
950
951 for(uint i=0; i < value_size*TTMATH_BITS_PER_UINT ; ++i)
952 {
953 if( Add(*this) )
954 {
955 TTMATH_LOGC("UInt::Mul1", 1)
956 return 1;
957 }
958
959 if( ss1.Rcl(1) )
960 if( Add(ss2) )
961 {
962 TTMATH_LOGC("UInt::Mul1", 1)
963 return 1;
964 }
965 }
966
967 TTMATH_LOGC("UInt::Mul1", 0)
968
969 return 0;
970 }
971
972
973 public:
974
975 /*!
976 multiplication: this = this * ss2
977 can return carry
978 */
979 uint Mul1(const UInt<value_size> & ss2)
980 {
981 if( this == &ss2 )
982 {
983 UInt<value_size> copy_ss2(ss2);
984 return Mul1Ref(copy_ss2);
985 }
986 else
987 {
988 return Mul1Ref(ss2);
989 }
990 }
991
992
993 /*!
994 multiplication: result = this * ss2
995
996 result is twice bigger than 'this' and 'ss2'
997 this method never returns carry
998 */
999 void Mul1Big(const UInt<value_size> & ss2_, UInt<value_size*2> & result)
1000 {
1001 UInt<value_size*2> ss2;
1002 uint i;
1003
1004 // copying *this into result and ss2_ into ss2
1005 for(i=0 ; i<value_size ; ++i)
1006 {
1007 result.table[i] = table[i];
1008 ss2.table[i] = ss2_.table[i];
1009 }
1010
1011 // cleaning the highest bytes in result and ss2
1012 for( ; i < value_size*2 ; ++i)
1013 {
1014 result.table[i] = 0;
1015 ss2.table[i] = 0;
1016 }
1017
1018 // multiply
1019 // (there will not be a carry)
1020 result.Mul1( ss2 );
1021
1022 TTMATH_LOG("UInt::Mul1Big")
1023 }
1024
1025
1026
1027 /*!
1028 the second version of the multiplication algorithm
1029
1030 this algorithm is similar to the 'schoolbook method' which is done by hand
1031 */
1032
1033 /*!
1034 multiplication: this = this * ss2
1035
1036 it returns carry if it has been
1037 */
1038 uint Mul2(const UInt<value_size> & ss2)
1039 {
1040 UInt<value_size*2> result;
1041 uint i, c = 0;
1042
1043 Mul2Big(ss2, result);
1044
1045 // copying result
1046 for(i=0 ; i<value_size ; ++i)
1047 table[i] = result.table[i];
1048
1049 // testing carry
1050 for( ; i<value_size*2 ; ++i)
1051 if( result.table[i] != 0 )
1052 {
1053 c = 1;
1054 break;
1055 }
1056
1057 TTMATH_LOGC("UInt::Mul2", c)
1058
1059 return c;
1060 }
1061
1062
1063 /*!
1064 multiplication: result = this * ss2
1065
1066 result is twice bigger than this and ss2
1067 this method never returns carry
1068 */
1069 void Mul2Big(const UInt<value_size> & ss2, UInt<value_size*2> & result)
1070 {
1071 Mul2Big2<value_size>(table, ss2.table, result);
1072
1073 TTMATH_LOG("UInt::Mul2Big")
1074 }
1075
1076
1077 private:
1078
1079 /*!
1080 an auxiliary method for calculating the multiplication
1081
1082 arguments we're taking as pointers (this is to improve the Mul3Big2()- avoiding
1083 unnecessary copying objects), the result should be taken as a pointer too,
1084 but at the moment there is no method AddTwoInts() which can operate on pointers
1085 */
1086 template<uint ss_size>
1087 void Mul2Big2(const uint * ss1, const uint * ss2, UInt<ss_size*2> & result)
1088 {
1089 uint x1size = ss_size, x2size = ss_size;
1090 uint x1start = 0, x2start = 0;
1091
1092 if( ss_size > 2 )
1093 {
1094 // if the ss_size is smaller than or equal to 2
1095 // there is no sense to set x1size (and others) to another values
1096
1097 for(x1size=ss_size ; x1size>0 && ss1[x1size-1]==0 ; --x1size);
1098 for(x2size=ss_size ; x2size>0 && ss2[x2size-1]==0 ; --x2size);
1099
1100 for(x1start=0 ; x1start<x1size && ss1[x1start]==0 ; ++x1start);
1101 for(x2start=0 ; x2start<x2size && ss2[x2start]==0 ; ++x2start);
1102 }
1103
1104 Mul2Big3<ss_size>(ss1, ss2, result, x1start, x1size, x2start, x2size);
1105 }
1106
1107
1108
1109 /*!
1110 an auxiliary method for calculating the multiplication
1111 */
1112 template<uint ss_size>
1113 void Mul2Big3(const uint * ss1, const uint * ss2, UInt<ss_size*2> & result, uint x1start, uint x1size, uint x2start, uint x2size)
1114 {
1115 uint r2, r1;
1116
1117 result.SetZero();
1118
1119 if( x1size==0 || x2size==0 )
1120 return;
1121
1122 for(uint x1=x1start ; x1<x1size ; ++x1)
1123 {
1124 for(uint x2=x2start ; x2<x2size ; ++x2)
1125 {
1126 MulTwoWords(ss1[x1], ss2[x2], &r2, &r1);
1127 result.AddTwoInts(r2, r1, x2+x1);
1128 // here will never be a carry
1129 }
1130 }
1131 }
1132
1133
1134 public:
1135
1136
1137 /*!
1138 multiplication: this = this * ss2
1139
1140 This is Karatsuba Multiplication algorithm, we're using it when value_size is greater than
1141 or equal to TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE macro (defined in ttmathuint.h).
1142 If value_size is smaller then we're using Mul2Big() instead.
1143
1144 Karatsuba multiplication:
1145 Assume we have:
1146 this = x = x1*B^m + x0
1147 ss2 = y = y1*B^m + y0
1148 where x0 and y0 are less than B^m
1149 the product from multiplication we can show as:
1150 x*y = (x1*B^m + x0)(y1*B^m + y0) = z2*B^(2m) + z1*B^m + z0
1151 where
1152 z2 = x1*y1
1153 z1 = x1*y0 + x0*y1
1154 z0 = x0*y0
1155 this is standard schoolbook algorithm with O(n^2), Karatsuba observed that z1 can be given in other form:
1156 z1 = (x1 + x0)*(y1 + y0) - z2 - z0 / z1 = (x1*y1 + x1*y0 + x0*y1 + x0*y0) - x1*y1 - x0*y0 = x1*y0 + x0*y1 /
1157 and to calculate the multiplication we need only three multiplications (with some additions and subtractions)
1158
1159 Our objects 'this' and 'ss2' we divide into two parts and by using recurrence we calculate the multiplication.
1160 Karatsuba multiplication has O( n^(ln(3)/ln(2)) )
1161 */
1162 uint Mul3(const UInt<value_size> & ss2)
1163 {
1164 UInt<value_size*2> result;
1165 uint i, c = 0;
1166
1167 Mul3Big(ss2, result);
1168
1169 // copying result
1170 for(i=0 ; i<value_size ; ++i)
1171 table[i] = result.table[i];
1172
1173 // testing carry
1174 for( ; i<value_size*2 ; ++i)
1175 if( result.table[i] != 0 )
1176 {
1177 c = 1;
1178 break;
1179 }
1180
1181 TTMATH_LOGC("UInt::Mul3", c)
1182
1183 return c;
1184 }
1185
1186
1187
1188 /*!
1189 multiplication: result = this * ss2
1190
1191 result is twice bigger than this and ss2,
1192 this method never returns carry,
1193 (Karatsuba multiplication)
1194 */
1195 void Mul3Big(const UInt<value_size> & ss2, UInt<value_size*2> & result)
1196 {
1197 Mul3Big2<value_size>(table, ss2.table, result.table);
1198
1199 TTMATH_LOG("UInt::Mul3Big")
1200 }
1201
1202
1203
1204 private:
1205
1206 /*!
1207 an auxiliary method for calculating the Karatsuba multiplication
1208
1209 result_size is equal ss_size*2
1210 */
1211 template<uint ss_size>
1212 void Mul3Big2(const uint * ss1, const uint * ss2, uint * result)
1213 {
1214 const uint * x1, * x0, * y1, * y0;
1215
1216
1217 if( ss_size>1 && ss_size<TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE )
1218 {
1219 UInt<ss_size*2> res;
1220 Mul2Big2<ss_size>(ss1, ss2, res);
1221
1222 #ifdef __clang__
1223 #pragma clang diagnostic push
1224 #pragma clang diagnostic ignored "-Wtautological-compare"
1225 #endif
1226
1227 for(uint i=0 ; i<ss_size*2 ; ++i)
1228 result[i] = res.table[i];
1229
1230 #ifdef __clang__
1231 #pragma clang diagnostic pop
1232 #endif
1233
1234 return;
1235 }
1236 else
1237 if( ss_size == 1 )
1238 {
1239 return MulTwoWords(*ss1, *ss2, &result[1], &result[0]);
1240 }
1241
1242
1243 if( (ss_size & 1) == 1 )
1244 {
1245 // ss_size is odd
1246 x0 = ss1;
1247 y0 = ss2;
1248 x1 = ss1 + ss_size / 2 + 1;
1249 y1 = ss2 + ss_size / 2 + 1;
1250
1251 // the second vectors (x1 and y1) are smaller about one from the first ones (x0 and y0)
1252 Mul3Big3<ss_size/2 + 1, ss_size/2, ss_size*2>(x1, x0, y1, y0, result);
1253 }
1254 else
1255 {
1256 // ss_size is even
1257 x0 = ss1;
1258 y0 = ss2;
1259 x1 = ss1 + ss_size / 2;
1260 y1 = ss2 + ss_size / 2;
1261
1262 // all four vectors (x0 x1 y0 y1) are equal in size
1263 Mul3Big3<ss_size/2, ss_size/2, ss_size*2>(x1, x0, y1, y0, result);
1264 }
1265 }
1266
1267
1268
1269 #ifdef _MSC_VER
1270 #pragma warning (disable : 4717)
1271 //warning C4717: recursive on all control paths, function will cause runtime stack overflow
1272 //we have the stop point in Mul3Big2() method
1273 #endif
1274
1275
1276 /*!
1277 an auxiliary method for calculating the Karatsuba multiplication
1278
1279 x = x1*B^m + x0
1280 y = y1*B^m + y0
1281
1282 first_size - is the size of vectors: x0 and y0
1283 second_size - is the size of vectors: x1 and y1 (can be either equal first_size or smaller about one from first_size)
1284
1285 x*y = (x1*B^m + x0)(y1*B^m + y0) = z2*B^(2m) + z1*B^m + z0
1286 where
1287 z0 = x0*y0
1288 z2 = x1*y1
1289 z1 = (x1 + x0)*(y1 + y0) - z2 - z0
1290 */
1291 template<uint first_size, uint second_size, uint result_size>
1292 uint Mul3Big3(const uint * x1, const uint * x0, const uint * y1, const uint * y0, uint * result)
1293 {
1294 uint i, c, xc, yc;
1295
1296 UInt<first_size> temp, temp2;
1297 UInt<first_size*3> z1;
1298
1299 // z0 and z2 we store directly in the result (we don't use any temporary variables)
1300 Mul3Big2<first_size>(x0, y0, result); // z0
1301 Mul3Big2<second_size>(x1, y1, result+first_size*2); // z2
1302
1303 // now we calculate z1
1304 // temp = (x0 + x1)
1305 // temp2 = (y0 + y1)
1306 // we're using temp and temp2 with UInt<first_size>, although there can be a carry but
1307 // we simple remember it in xc and yc (xc and yc can be either 0 or 1),
1308 // and (x0 + x1)*(y0 + y1) we calculate in this way (schoolbook algorithm):
1309 //
1310 // xc | temp
1311 // yc | temp2
1312 // --------------------
1313 // (temp * temp2)
1314 // xc*temp2 |
1315 // yc*temp |
1316 // xc*yc |
1317 // ---------- z1 --------
1318 //
1319 // and the result is never larger in size than 3*first_size
1320
1321 xc = AddVector(x0, x1, first_size, second_size, temp.table);
1322 yc = AddVector(y0, y1, first_size, second_size, temp2.table);
1323
1324 Mul3Big2<first_size>(temp.table, temp2.table, z1.table);
1325
1326 #ifdef __clang__
1327 #pragma clang diagnostic push
1328 #pragma clang diagnostic ignored "-Wtautological-compare"
1329 #endif
1330
1331 // clearing the rest of z1
1332 for(i=first_size*2 ; i<first_size*3 ; ++i)
1333 z1.table[i] = 0;
1334
1335 #ifdef __clang__
1336 #pragma clang diagnostic pop
1337 #endif
1338
1339 if( xc )
1340 {
1341 c = AddVector(z1.table+first_size, temp2.table, first_size*3-first_size, first_size, z1.table+first_size);
1342 TTMATH_ASSERT( c==0 )
1343 }
1344
1345 if( yc )
1346 {
1347 c = AddVector(z1.table+first_size, temp.table, first_size*3-first_size, first_size, z1.table+first_size);
1348 TTMATH_ASSERT( c==0 )
1349 }
1350
1351
1352 if( xc && yc )
1353 {
1354 #ifdef __clang__
1355 #pragma clang diagnostic push
1356 #pragma clang diagnostic ignored "-Wtautological-compare"
1357 #endif
1358
1359 for( i=first_size*2 ; i<first_size*3 ; ++i )
1360 if( ++z1.table[i] != 0 )
1361 break; // break if there was no carry
1362
1363 #ifdef __clang__
1364 #pragma clang diagnostic pop
1365 #endif
1366 }
1367
1368 // z1 = z1 - z2
1369 c = SubVector(z1.table, result+first_size*2, first_size*3, second_size*2, z1.table);
1370 TTMATH_ASSERT(c==0)
1371
1372 // z1 = z1 - z0
1373 c = SubVector(z1.table, result, first_size*3, first_size*2, z1.table);
1374 TTMATH_ASSERT(c==0)
1375
1376 // here we've calculated the z1
1377 // now we're adding it to the result
1378
1379 if( first_size > second_size )
1380 {
1381 uint z1_size = result_size - first_size;
1382 TTMATH_ASSERT( z1_size <= first_size*3 )
1383
1384 #ifdef __clang__
1385 #pragma clang diagnostic push
1386 #pragma clang diagnostic ignored "-Wtautological-compare"
1387 #endif
1388
1389 for(i=z1_size ; i<first_size*3 ; ++i)
1390 {
1391 TTMATH_ASSERT( z1.table[i] == 0 )
1392 }
1393
1394 #ifdef __clang__
1395 #pragma clang diagnostic pop
1396 #endif
1397
1398 c = AddVector(result+first_size, z1.table, result_size-first_size, z1_size, result+first_size);
1399 TTMATH_ASSERT(c==0)
1400 }
1401 else
1402 {
1403 c = AddVector(result+first_size, z1.table, result_size-first_size, first_size*3, result+first_size);
1404 TTMATH_ASSERT(c==0)
1405 }
1406 return c;
1407 }
1408
1409
1410
1411 #ifdef _MSC_VER
1412 #pragma warning (default : 4717)
1413 #endif
1414
1415
1416 public:
1417
1418
1419 /*!
1420 multiplication this = this * ss2
1421 */
1422 uint MulFastest(const UInt<value_size> & ss2)
1423 {
1424 UInt<value_size*2> result;
1425 uint i, c = 0;
1426
1427 MulFastestBig(ss2, result);
1428
1429 // copying result
1430 for(i=0 ; i<value_size ; ++i)
1431 table[i] = result.table[i];
1432
1433 // testing carry
1434 for( ; i<value_size*2 ; ++i)
1435 if( result.table[i] != 0 )
1436 {
1437 c = 1;
1438 break;
1439 }
1440
1441 TTMATH_LOGC("UInt::MulFastest", c)
1442
1443 return c;
1444 }
1445
1446
1447 /*!
1448 multiplication result = this * ss2
1449
1450 this method is trying to select the fastest algorithm
1451 (in the future this method can be improved)
1452 */
1453 void MulFastestBig(const UInt<value_size> & ss2, UInt<value_size*2> & result)
1454 {
1455 if( value_size < TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE )
1456 return Mul2Big(ss2, result);
1457
1458 uint x1size = value_size, x2size = value_size;
1459 uint x1start = 0, x2start = 0;
1460
1461 for(x1size=value_size ; x1size>0 && table[x1size-1]==0 ; --x1size);
1462 for(x2size=value_size ; x2size>0 && ss2.table[x2size-1]==0 ; --x2size);
1463
1464 if( x1size==0 || x2size==0 )
1465 {
1466 // either 'this' or 'ss2' is equal zero - the result is zero too
1467 result.SetZero();
1468 return;
1469 }
1470
1471 for(x1start=0 ; x1start<x1size && table[x1start]==0 ; ++x1start);
1472 for(x2start=0 ; x2start<x2size && ss2.table[x2start]==0 ; ++x2start);
1473
1474 uint distancex1 = x1size - x1start;
1475 uint distancex2 = x2size - x2start;
1476
1477 if( distancex1 < 3 || distancex2 < 3 )
1478 // either 'this' or 'ss2' have only 2 (or 1) items different from zero (side by side)
1479 // (this condition in the future can be improved)
1480 return Mul2Big3<value_size>(table, ss2.table, result, x1start, x1size, x2start, x2size);
1481
1482
1483 // Karatsuba multiplication
1484 Mul3Big(ss2, result);
1485
1486 TTMATH_LOG("UInt::MulFastestBig")
1487 }
1488
1489
1490 /*!
1491 *
1492 * Division
1493 *
1494 *
1495 */
1496
1497 public:
1498
1499
1500 /*!
1501 division by one unsigned word
1502
1503 returns 1 when divisor is zero
1504 */
1505 uint DivInt(uint divisor, uint * remainder = 0)
1506 {
1507 if( divisor == 0 )
1508 {
1509 if( remainder )
1510 *remainder = 0; // this is for convenience, without it the compiler can report that 'remainder' is uninitialized
1511
1512 TTMATH_LOG("UInt::DivInt")
1513
1514 return 1;
1515 }
1516
1517 if( divisor == 1 )
1518 {
1519 if( remainder )
1520 *remainder = 0;
1521
1522 TTMATH_LOG("UInt::DivInt")
1523
1524 return 0;
1525 }
1526
1527 UInt<value_size> dividend(*this);
1528 SetZero();
1529
1530 sint i; // i must be with a sign
1531 uint r = 0;
1532
1533 // we're looking for the last word in ss1
1534 for(i=value_size-1 ; i>0 && dividend.table[i]==0 ; --i);
1535
1536 for( ; i>=0 ; --i)
1537 DivTwoWords(r, dividend.table[i], divisor, &table[i], &r);
1538
1539 if( remainder )
1540 *remainder = r;
1541
1542 TTMATH_LOG("UInt::DivInt")
1543
1544 return 0;
1545 }
1546
1547 uint DivInt(uint divisor, uint & remainder)
1548 {
1549 return DivInt(divisor, &remainder);
1550 }
1551
1552
1553
1554 /*!
1555 division this = this / ss2
1556
1557 return values:
1558 0 - ok
1559 1 - division by zero
1560 'this' will be the quotient
1561 'remainder' - remainder
1562 */
1563 uint Div( const UInt<value_size> & divisor,
1564 UInt<value_size> * remainder = 0,
1565 uint algorithm = 3)
1566 {
1567 switch( algorithm )
1568 {
1569 case 1:
1570 return Div1(divisor, remainder);
1571
1572 case 2:
1573 return Div2(divisor, remainder);
1574
1575 case 3:
1576 default:
1577 return Div3(divisor, remainder);
1578 }
1579 }
1580
1581 uint Div(const UInt<value_size> & divisor, UInt<value_size> & remainder, uint algorithm = 3)
1582 {
1583 return Div(divisor, &remainder, algorithm);
1584 }
1585
1586
1587
1588 private:
1589
1590 /*!
1591 return values:
1592 0 - none has to be done
1593 1 - division by zero
1594 2 - division should be made
1595 */
1596 uint Div_StandardTest( const UInt<value_size> & v,
1597 uint & m, uint & n,
1598 UInt<value_size> * remainder = 0)
1599 {
1600 switch( Div_CalculatingSize(v, m, n) )
1601 {
1602 case 4: // 'this' is equal v
1603 if( remainder )
1604 remainder->SetZero();
1605
1606 SetOne();
1607 TTMATH_LOG("UInt::Div_StandardTest")
1608 return 0;
1609
1610 case 3: // 'this' is smaller than v
1611 if( remainder )
1612 *remainder = *this;
1613
1614 SetZero();
1615 TTMATH_LOG("UInt::Div_StandardTest")
1616 return 0;
1617
1618 case 2: // 'this' is zero
1619 if( remainder )
1620 remainder->SetZero();
1621
1622 SetZero();
1623 TTMATH_LOG("UInt::Div_StandardTest")
1624 return 0;
1625
1626 case 1: // v is zero
1627 TTMATH_LOG("UInt::Div_StandardTest")
1628 return 1;
1629 }
1630
1631 TTMATH_LOG("UInt::Div_StandardTest")
1632
1633 return 2;
1634 }
1635
1636
1637
1638 /*!
1639 return values:
1640 0 - ok
1641 'm' - is the index (from 0) of last non-zero word in table ('this')
1642 'n' - is the index (from 0) of last non-zero word in v.table
1643 1 - v is zero
1644 2 - 'this' is zero
1645 3 - 'this' is smaller than v
1646 4 - 'this' is equal v
1647
1648 if the return value is different than zero the 'm' and 'n' are undefined
1649 */
1650 uint Div_CalculatingSize(const UInt<value_size> & v, uint & m, uint & n)
1651 {
1652 m = n = value_size-1;
1653
1654 for( ; n!=0 && v.table[n]==0 ; --n);
1655
1656 if( n==0 && v.table[n]==0 )
1657 return 1;
1658
1659 for( ; m!=0 && table[m]==0 ; --m);
1660
1661 if( m==0 && table[m]==0 )
1662 return 2;
1663
1664 if( m < n )
1665 return 3;
1666 else
1667 if( m == n )
1668 {
1669 uint i;
1670 for(i = n ; i!=0 && table[i]==v.table[i] ; --i);
1671
1672 if( table[i] < v.table[i] )
1673 return 3;
1674 else
1675 if (table[i] == v.table[i] )
1676 return 4;
1677 }
1678
1679 return 0;
1680 }
1681
1682
1683 public:
1684
1685 /*!
1686 the first division algorithm
1687 radix 2
1688 */
1689 uint Div1(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0)
1690 {
1691 uint m,n, test;
1692
1693 test = Div_StandardTest(divisor, m, n, remainder);
1694 if( test < 2 )
1695 return test;
1696
1697 if( !remainder )
1698 {
1699 UInt<value_size> rem;
1700
1701 return Div1_Calculate(divisor, rem);
1702 }
1703
1704 return Div1_Calculate(divisor, *remainder);
1705 }
1706
1707
1708 /*!
1709 the first division algorithm
1710 radix 2
1711 */
1712 uint Div1(const UInt<value_size> & divisor, UInt<value_size> & remainder)
1713 {
1714 return Div1(divisor, &remainder);
1715 }
1716
1717
1718 private:
1719
1720 uint Div1_Calculate(const UInt<value_size> & divisor, UInt<value_size> & rest)
1721 {
1722 if( this == &divisor )
1723 {
1724 UInt<value_size> divisor_copy(divisor);
1725 return Div1_CalculateRef(divisor_copy, rest);
1726 }
1727 else
1728 {
1729 return Div1_CalculateRef(divisor, rest);
1730 }
1731 }
1732
1733
1734 uint Div1_CalculateRef(const UInt<value_size> & divisor, UInt<value_size> & rest)
1735 {
1736 TTMATH_REFERENCE_ASSERT( divisor )
1737
1738 sint loop;
1739 sint c;
1740
1741 rest.SetZero();
1742 loop = value_size * TTMATH_BITS_PER_UINT;
1743 c = 0;
1744
1745
1746 div_a:
1747 c = Rcl(1, c);
1748 c = rest.Add(rest,c);
1749 c = rest.Sub(divisor,c);
1750
1751 c = !c;
1752
1753 if(!c)
1754 goto div_d;
1755
1756
1757 div_b:
1758 --loop;
1759 if(loop)
1760 goto div_a;
1761
1762 c = Rcl(1, c);
1763 TTMATH_LOG("UInt::Div1_Calculate")
1764 return 0;
1765
1766
1767 div_c:
1768 c = Rcl(1, c);
1769 c = rest.Add(rest,c);
1770 c = rest.Add(divisor);
1771
1772 if(c)
1773 goto div_b;
1774
1775
1776 div_d:
1777 --loop;
1778 if(loop)
1779 goto div_c;
1780
1781 c = Rcl(1, c);
1782 c = rest.Add(divisor);
1783
1784 TTMATH_LOG("UInt::Div1_Calculate")
1785
1786 return 0;
1787 }
1788
1789
1790 public:
1791
1792 /*!
1793 the second division algorithm
1794
1795 return values:
1796 0 - ok
1797 1 - division by zero
1798 */
1799 uint Div2(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0)
1800 {
1801 if( this == &divisor )
1802 {
1803 UInt<value_size> divisor_copy(divisor);
1804 return Div2Ref(divisor_copy, remainder);
1805 }
1806 else
1807 {
1808 return Div2Ref(divisor, remainder);
1809 }
1810 }
1811
1812
1813 /*!
1814 the second division algorithm
1815
1816 return values:
1817 0 - ok
1818 1 - division by zero
1819 */
1820 uint Div2(const UInt<value_size> & divisor, UInt<value_size> & remainder)
1821 {
1822 return Div2(divisor, &remainder);
1823 }
1824
1825
1826 private:
1827
1828 /*!
1829 the second division algorithm
1830
1831 return values:
1832 0 - ok
1833 1 - division by zero
1834 */
1835 uint Div2Ref(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0)
1836 {
1837 uint bits_diff;
1838 uint status = Div2_Calculate(divisor, remainder, bits_diff);
1839 if( status < 2 )
1840 return status;
1841
1842 if( CmpBiggerEqual(divisor) )
1843 {
1844 Div2(divisor, remainder);
1845 SetBit(bits_diff);
1846 }
1847 else
1848 {
1849 if( remainder )
1850 *remainder = *this;
1851
1852 SetZero();
1853 SetBit(bits_diff);
1854 }
1855
1856 TTMATH_LOG("UInt::Div2")
1857
1858 return 0;
1859 }
1860
1861
1862 /*!
1863 return values:
1864 0 - we've calculated the division
1865 1 - division by zero
1866 2 - we have to still calculate
1867
1868 */
1869 uint Div2_Calculate(const UInt<value_size> & divisor, UInt<value_size> * remainder,
1870 uint & bits_diff)
1871 {
1872 uint table_id, index;
1873 uint divisor_table_id, divisor_index;
1874
1875 uint status = Div2_FindLeadingBitsAndCheck( divisor, remainder,
1876 table_id, index,
1877 divisor_table_id, divisor_index);
1878
1879 if( status < 2 )
1880 {
1881 TTMATH_LOG("UInt::Div2_Calculate")
1882 return status;
1883 }
1884
1885 // here we know that 'this' is greater than divisor
1886 // then 'index' is greater or equal 'divisor_index'
1887 bits_diff = index - divisor_index;
1888
1889 UInt<value_size> divisor_copy(divisor);
1890 divisor_copy.Rcl(bits_diff, 0);
1891
1892 if( CmpSmaller(divisor_copy, table_id) )
1893 {
1894 divisor_copy.Rcr(1);
1895 --bits_diff;
1896 }
1897
1898 Sub(divisor_copy, 0);
1899
1900 TTMATH_LOG("UInt::Div2_Calculate")
1901
1902 return 2;
1903 }
1904
1905
1906 /*!
1907 return values:
1908 0 - we've calculated the division
1909 1 - division by zero
1910 2 - we have to still calculate
1911 */
1912 uint Div2_FindLeadingBitsAndCheck( const UInt<value_size> & divisor,
1913 UInt<value_size> * remainder,
1914 uint & table_id, uint & index,
1915 uint & divisor_table_id, uint & divisor_index)
1916 {
1917 if( !divisor.FindLeadingBit(divisor_table_id, divisor_index) )
1918 {
1919 // division by zero
1920 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
1921 return 1;
1922 }
1923
1924 if( !FindLeadingBit(table_id, index) )
1925 {
1926 // zero is divided by something
1927
1928 SetZero();
1929
1930 if( remainder )
1931 remainder->SetZero();
1932
1933 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
1934
1935 return 0;
1936 }
1937
1938 divisor_index += divisor_table_id * TTMATH_BITS_PER_UINT;
1939 index += table_id * TTMATH_BITS_PER_UINT;
1940
1941 if( divisor_table_id == 0 )
1942 {
1943 // dividor has only one 32-bit word
1944
1945 uint r;
1946 DivInt(divisor.table[0], &r);
1947
1948 if( remainder )
1949 {
1950 remainder->SetZero();
1951 remainder->table[0] = r;
1952 }
1953
1954 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
1955
1956 return 0;
1957 }
1958
1959
1960 if( Div2_DivisorGreaterOrEqual( divisor, remainder,
1961 table_id, index,
1962 divisor_index) )
1963 {
1964 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
1965 return 0;
1966 }
1967
1968
1969 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
1970
1971 return 2;
1972 }
1973
1974
1975 /*!
1976 return values:
1977 true if divisor is equal or greater than 'this'
1978 */
1979 bool Div2_DivisorGreaterOrEqual( const UInt<value_size> & divisor,
1980 UInt<value_size> * remainder,
1981 uint table_id, uint index,
1982 uint divisor_index )
1983 {
1984 if( divisor_index > index )
1985 {
1986 // divisor is greater than this
1987
1988 if( remainder )
1989 *remainder = *this;
1990
1991 SetZero();
1992
1993 TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
1994
1995 return true;
1996 }
1997
1998 if( divisor_index == index )
1999 {
2000 // table_id == divisor_table_id as well
2001
2002 uint i;
2003 for(i = table_id ; i!=0 && table[i]==divisor.table[i] ; --i);
2004
2005 if( table[i] < divisor.table[i] )
2006 {
2007 // divisor is greater than 'this'
2008
2009 if( remainder )
2010 *remainder = *this;
2011
2012 SetZero();
2013
2014 TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
2015
2016 return true;
2017 }
2018 else
2019 if( table[i] == divisor.table[i] )
2020 {
2021 // divisor is equal 'this'
2022
2023 if( remainder )
2024 remainder->SetZero();
2025
2026 SetOne();
2027
2028 TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
2029
2030 return true;
2031 }
2032 }
2033
2034 TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
2035
2036 return false;
2037 }
2038
2039
2040 public:
2041
2042 /*!
2043 the third division algorithm
2044 */
2045 uint Div3(const UInt<value_size> & ss2, UInt<value_size> * remainder = 0)
2046 {
2047 if( this == &ss2 )
2048 {
2049 UInt<value_size> copy_ss2(ss2);
2050 return Div3Ref(copy_ss2, remainder);
2051 }
2052 else
2053 {
2054 return Div3Ref(ss2, remainder);
2055 }
2056 }
2057
2058
2059 /*!
2060 the third division algorithm
2061 */
2062 uint Div3(const UInt<value_size> & ss2, UInt<value_size> & remainder)
2063 {
2064 return Div3(ss2, &remainder);
2065 }
2066
2067
2068 private:
2069
2070 /*!
2071 the third division algorithm
2072
2073 this algorithm is described in the following book:
2074 "The art of computer programming 2" (4.3.1 page 272)
2075 Donald E. Knuth
2076 !! give the description here (from the book)
2077 */
2078 uint Div3Ref(const UInt<value_size> & v, UInt<value_size> * remainder = 0)
2079 {
2080 uint m,n, test;
2081
2082 test = Div_StandardTest(v, m, n, remainder);
2083 if( test < 2 )
2084 return test;
2085
2086 if( n == 0 )
2087 {
2088 uint r;
2089 DivInt( v.table[0], &r );
2090
2091 if( remainder )
2092 {
2093 remainder->SetZero();
2094 remainder->table[0] = r;
2095 }
2096
2097 TTMATH_LOG("UInt::Div3")
2098
2099 return 0;
2100 }
2101
2102
2103 // we can only use the third division algorithm when
2104 // the divisor is greater or equal 2^32 (has more than one 32-bit word)
2105 ++m;
2106 ++n;
2107 m = m - n;
2108 Div3_Division(v, remainder, m, n);
2109
2110 TTMATH_LOG("UInt::Div3")
2111
2112 return 0;
2113 }
2114
2115
2116
2117 private:
2118
2119
2120 void Div3_Division(UInt<value_size> v, UInt<value_size> * remainder, uint m, uint n)
2121 {
2122 TTMATH_ASSERT( n>=2 )
2123
2124 UInt<value_size+1> uu, vv;
2125 UInt<value_size> q;
2126 uint d, u_value_size, u0, u1, u2, v1, v0, j=m;
2127
2128 u_value_size = Div3_Normalize(v, n, d);
2129
2130 if( j+n == value_size )
2131 u2 = u_value_size;
2132 else
2133 u2 = table[j+n];
2134
2135 Div3_MakeBiggerV(v, vv);
2136
2137 for(uint i = j+1 ; i<value_size ; ++i)
2138 q.table[i] = 0;
2139
2140 while( true )
2141 {
2142 u1 = table[j+n-1];
2143 u0 = table[j+n-2];
2144 v1 = v.table[n-1];
2145 v0 = v.table[n-2];
2146
2147 uint qp = Div3_Calculate(u2,u1,u0, v1,v0);
2148
2149 Div3_MakeNewU(uu, j, n, u2);
2150 Div3_MultiplySubtract(uu, vv, qp);
2151 Div3_CopyNewU(uu, j, n);
2152
2153 q.table[j] = qp;
2154
2155 // the next loop
2156 if( j-- == 0 )
2157 break;
2158
2159 u2 = table[j+n];
2160 }
2161
2162 if( remainder )
2163 Div3_Unnormalize(remainder, n, d);
2164
2165 *this = q;
2166
2167 TTMATH_LOG("UInt::Div3_Division")
2168 }
2169
2170
2171 void Div3_MakeNewU(UInt<value_size+1> & uu, uint j, uint n, uint u_max)
2172 {
2173 uint i;
2174
2175 for(i=0 ; i<n ; ++i, ++j)
2176 uu.table[i] = table[j];
2177
2178 // 'n' is from <1..value_size> so and 'i' is from <0..value_size>
2179 // then table[i] is always correct (look at the declaration of 'uu')
2180 uu.table[i] = u_max;
2181
2182 for( ++i ; i<value_size+1 ; ++i)
2183 uu.table[i] = 0;
2184
2185 TTMATH_LOG("UInt::Div3_MakeNewU")
2186 }
2187
2188
2189 void Div3_CopyNewU(const UInt<value_size+1> & uu, uint j, uint n)
2190 {
2191 uint i;
2192
2193 for(i=0 ; i<n ; ++i)
2194 table[i+j] = uu.table[i];
2195
2196 if( i+j < value_size )
2197 table[i+j] = uu.table[i];
2198
2199 TTMATH_LOG("UInt::Div3_CopyNewU")
2200 }
2201
2202
2203 /*!
2204 we're making the new 'vv'
2205 the value is actually the same but the 'table' is bigger (value_size+1)
2206 */
2207 void Div3_MakeBiggerV(const UInt<value_size> & v, UInt<value_size+1> & vv)
2208 {
2209 for(uint i=0 ; i<value_size ; ++i)
2210 vv.table[i] = v.table[i];
2211
2212 vv.table[value_size] = 0;
2213
2214 TTMATH_LOG("UInt::Div3_MakeBiggerV")
2215 }
2216
2217
2218 /*!
2219 we're moving all bits from 'v' into the left side of the n-1 word
2220 (the highest bit at v.table[n-1] will be equal one,
2221 the bits from 'this' we're moving the same times as 'v')
2222
2223 return values:
2224 d - how many times we've moved
2225 return - the next-left value from 'this' (that after table[value_size-1])
2226 */
2227 uint Div3_Normalize(UInt<value_size> & v, uint n, uint & d)
2228 {
2229 // v.table[n-1] is != 0
2230
2231 uint bit = (uint)FindLeadingBitInWord(v.table[n-1]);
2232 uint move = (TTMATH_BITS_PER_UINT - bit - 1);
2233 uint res = table[value_size-1];
2234 d = move;
2235
2236 if( move > 0 )
2237 {
2238 v.Rcl(move, 0);
2239 Rcl(move, 0);
2240 res = res >> (bit + 1);
2241 }
2242 else
2243 {
2244 res = 0;
2245 }
2246
2247 TTMATH_LOG("UInt::Div3_Normalize")
2248
2249 return res;
2250 }
2251
2252
2253 void Div3_Unnormalize(UInt<value_size> * remainder, uint n, uint d)
2254 {
2255 for(uint i=n ; i<value_size ; ++i)
2256 table[i] = 0;
2257
2258 Rcr(d,0);
2259
2260 *remainder = *this;
2261
2262 TTMATH_LOG("UInt::Div3_Unnormalize")
2263 }
2264
2265
2266 uint Div3_Calculate(uint u2, uint u1, uint u0, uint v1, uint v0)
2267 {
2268 UInt<2> u_temp;
2269 uint rp;
2270 bool next_test;
2271
2272 TTMATH_ASSERT( v1 != 0 )
2273
2274 u_temp.table[1] = u2;
2275 u_temp.table[0] = u1;
2276 u_temp.DivInt(v1, &rp);
2277
2278 TTMATH_ASSERT( u_temp.table[1]==0 || u_temp.table[1]==1 )
2279
2280 do
2281 {
2282 bool decrease = false;
2283
2284 if( u_temp.table[1] == 1 )
2285 decrease = true;
2286 else
2287 {
2288 UInt<2> temp1, temp2;
2289
2290 UInt<2>::MulTwoWords(u_temp.table[0], v0, temp1.table+1, temp1.table);
2291 temp2.table[1] = rp;
2292 temp2.table[0] = u0;
2293
2294 if( temp1 > temp2 )
2295 decrease = true;
2296 }
2297
2298 next_test = false;
2299
2300 if( decrease )
2301 {
2302 u_temp.SubOne();
2303
2304 rp += v1;
2305
2306 if( rp >= v1 ) // it means that there wasn't a carry (r<b from the book)
2307 next_test = true;
2308 }
2309 }
2310 while( next_test );
2311
2312 TTMATH_LOG("UInt::Div3_Calculate")
2313
2314 return u_temp.table[0];
2315 }
2316
2317
2318
2319 void Div3_MultiplySubtract( UInt<value_size+1> & uu,
2320 const UInt<value_size+1> & vv, uint & qp)
2321 {
2322 // D4 (in the book)
2323
2324 UInt<value_size+1> vv_temp(vv);
2325 vv_temp.MulInt(qp);
2326
2327 if( uu.Sub(vv_temp) )
2328 {
2329 // there was a carry
2330
2331 //
2332 // !!! this part of code was not tested
2333 //
2334
2335 --qp;
2336 uu.Add(vv);
2337
2338 // can be a carry from this additions but it should be ignored
2339 // because it cancels with the borrow from uu.Sub(vv_temp)
2340 }
2341
2342 TTMATH_LOG("UInt::Div3_MultiplySubtract")
2343 }
2344
2345
2346
2347
2348
2349
2350 public:
2351
2352
2353 /*!
2354 power this = this ^ pow
2355 binary algorithm (r-to-l)
2356
2357 return values:
2358 0 - ok
2359 1 - carry
2360 2 - incorrect argument (0^0)
2361 */
2362 uint Pow(UInt<value_size> pow)
2363 {
2364 if(pow.IsZero() && IsZero())
2365 // we don't define zero^zero
2366 return 2;
2367
2368 UInt<value_size> start(*this);
2369 UInt<value_size> result;
2370 result.SetOne();
2371 uint c = 0;
2372
2373 while( !c )
2374 {
2375 if( pow.table[0] & 1 )
2376 c += result.Mul(start);
2377
2378 pow.Rcr2_one(0);
2379 if( pow.IsZero() )
2380 break;
2381
2382 c += start.Mul(start);
2383 }
2384
2385 *this = result;
2386
2387 TTMATH_LOGC("UInt::Pow(UInt<>)", c)
2388
2389 return (c==0)? 0 : 1;
2390 }
2391
2392
2393 /*!
2394 square root
2395 e.g. Sqrt(9) = 3
2396 ('digit-by-digit' algorithm)
2397 */
2398 void Sqrt()
2399 {
2400 UInt<value_size> bit, temp;
2401
2402 if( IsZero() )
2403 return;
2404
2405 UInt<value_size> value(*this);
2406
2407 SetZero();
2408 bit.SetZero();
2409 bit.table[value_size-1] = (TTMATH_UINT_HIGHEST_BIT >> 1);
2410
2411 while( bit > value )
2412 bit.Rcr(2);
2413
2414 while( !bit.IsZero() )
2415 {
2416 temp = *this;
2417 temp.Add(bit);
2418
2419 if( value >= temp )
2420 {
2421 value.Sub(temp);
2422 Rcr(1);
2423 Add(bit);
2424 }
2425 else
2426 {
2427 Rcr(1);
2428 }
2429
2430 bit.Rcr(2);
2431 }
2432
2433 TTMATH_LOG("UInt::Sqrt")
2434 }
2435
2436
2437
2438 /*!
2439 this method sets n first bits to value zero
2440
2441 For example:
2442 let n=2 then if there's a value 111 (bin) there'll be '100' (bin)
2443 */
2444 void ClearFirstBits(uint n)
2445 {
2446 if( n >= value_size*TTMATH_BITS_PER_UINT )
2447 {
2448 SetZero();
2449 TTMATH_LOG("UInt::ClearFirstBits")
2450 return;
2451 }
2452
2453 uint * p = table;
2454
2455 // first we're clearing the whole words
2456 while( n >= TTMATH_BITS_PER_UINT )
2457 {
2458 *p++ = 0;
2459 n -= TTMATH_BITS_PER_UINT;
2460 }
2461
2462 if( n == 0 )
2463 {
2464 TTMATH_LOG("UInt::ClearFirstBits")
2465 return;
2466 }
2467
2468 // and then we're clearing one word which has left
2469 // mask -- all bits are set to one
2470 uint mask = TTMATH_UINT_MAX_VALUE;
2471
2472 mask = mask << n;
2473
2474 (*p) &= mask;
2475
2476 TTMATH_LOG("UInt::ClearFirstBits")
2477 }
2478
2479
2480 /*!
2481 this method returns true if the highest bit of the value is set
2482 */
2483 bool IsTheHighestBitSet() const
2484 {
2485 return (table[value_size-1] & TTMATH_UINT_HIGHEST_BIT) != 0;
2486 }
2487
2488
2489 /*!
2490 this method returns true if the lowest bit of the value is set
2491 */
2492 bool IsTheLowestBitSet() const
2493 {
2494 return (*table & 1) != 0;
2495 }
2496
2497
2498 /*!
2499 returning true if only the highest bit is set
2500 */
2501 bool IsOnlyTheHighestBitSet() const
2502 {
2503 #ifdef __clang__
2504 #pragma clang diagnostic push
2505 #pragma clang diagnostic ignored "-Wtautological-compare"
2506 #endif
2507
2508 for(uint i=0 ; i<value_size-1 ; ++i)
2509 if( table[i] != 0 )
2510 return false;
2511
2512 #ifdef __clang__
2513 #pragma clang diagnostic pop
2514 #endif
2515 if( table[value_size-1] != TTMATH_UINT_HIGHEST_BIT )
2516 return false;
2517
2518 return true;
2519 }
2520
2521
2522 /*!
2523 returning true if only the lowest bit is set
2524 */
2525 bool IsOnlyTheLowestBitSet() const
2526 {
2527 if( table[0] != 1 )
2528 return false;
2529
2530 for(uint i=1 ; i<value_size ; ++i)
2531 if( table[i] != 0 )
2532 return false;
2533
2534 return true;
2535 }
2536
2537
2538 /*!
2539 this method returns true if the value is equal zero
2540 */
2541 bool IsZero() const
2542 {
2543 for(uint i=0 ; i<value_size ; ++i)
2544 if(table[i] != 0)
2545 return false;
2546
2547 return true;
2548 }
2549
2550
2551 /*!
2552 returning true if first 'bits' bits are equal zero
2553 */
2554 bool AreFirstBitsZero(uint bits) const
2555 {
2556 TTMATH_ASSERT( bits <= value_size * TTMATH_BITS_PER_UINT )
2557
2558 uint index = bits / TTMATH_BITS_PER_UINT;
2559 uint rest = bits % TTMATH_BITS_PER_UINT;
2560 uint i;
2561
2562 for(i=0 ; i<index ; ++i)
2563 if(table[i] != 0 )
2564 return false;
2565
2566 if( rest == 0 )
2567 return true;
2568
2569 uint mask = TTMATH_UINT_MAX_VALUE >> (TTMATH_BITS_PER_UINT - rest);
2570
2571 return (table[i] & mask) == 0;
2572 }
2573
2574
2575
2576 /*!
2577 *
2578 * conversion methods
2579 *
2580 */
2581
2582
2583
2584 /*!
2585 this method converts an UInt<another_size> type to this class
2586
2587 this operation has mainly sense if the value from p is
2588 equal or smaller than that one which is returned from UInt<value_size>::SetMax()
2589
2590 it returns a carry if the value 'p' is too big
2591 */
2592 template<uint argument_size>
2593 uint FromUInt(const UInt<argument_size> & p)
2594 {
2595 uint min_size = (value_size < argument_size)? value_size : argument_size;
2596 uint i;
2597
2598 for(i=0 ; i<min_size ; ++i)
2599 table[i] = p.table[i];
2600
2601
2602 if( value_size > argument_size )
2603 {
2604 // 'this' is longer than 'p'
2605
2606 for( ; i<value_size ; ++i)
2607 table[i] = 0;
2608 }
2609 else
2610 {
2611 for( ; i<argument_size ; ++i)
2612 if( p.table[i] != 0 )
2613 {
2614 TTMATH_LOGC("UInt::FromUInt(UInt<>)", 1)
2615 return 1;
2616 }
2617 }
2618
2619 TTMATH_LOGC("UInt::FromUInt(UInt<>)", 0)
2620
2621 return 0;
2622 }
2623
2624
2625 /*!
2626 this method converts an UInt<another_size> type to this class
2627
2628 this operation has mainly sense if the value from p is
2629 equal or smaller than that one which is returned from UInt<value_size>::SetMax()
2630
2631 it returns a carry if the value 'p' is too big
2632 */
2633 template<uint argument_size>
2634 uint FromInt(const UInt<argument_size> & p)
2635 {
2636 return FromUInt(p);
2637 }
2638
2639
2640 /*!
2641 this method converts the uint type to this class
2642 */
2643 uint FromUInt(uint value)
2644 {
2645 for(uint i=1 ; i<value_size ; ++i)
2646 table[i] = 0;
2647
2648 table[0] = value;
2649
2650 TTMATH_LOG("UInt::FromUInt(uint)")
2651
2652 // there'll never be a carry here
2653 return 0;
2654 }
2655
2656
2657 /*!
2658 this method converts the uint type to this class
2659 */
2660 uint FromInt(uint value)
2661 {
2662 return FromUInt(value);
2663 }
2664
2665
2666 /*!
2667 this method converts the sint type to this class
2668 */
2669 uint FromInt(sint value)
2670 {
2671 uint c = FromUInt(uint(value));
2672
2673 if( c || value < 0 )
2674 return 1;
2675
2676 return 0;
2677 }
2678
2679
2680 /*!
2681 this operator converts an UInt<another_size> type to this class
2682
2683 it doesn't return a carry
2684 */
2685 /* template<uint argument_size>
2686 UInt<value_size> & operator=(const UInt<argument_size> & p)
2687 {
2688 FromUInt(p);
2689
2690 return *this;
2691 }
2692 */
2693
2694 /*!
2695 the assignment operator
2696 */
2697 /* UInt<value_size> & operator=(const UInt<value_size> & p)
2698 {
2699 for(uint i=0 ; i<value_size ; ++i)
2700 table[i] = p.table[i];
2701
2702 TTMATH_LOG("UInt::operator=(UInt<>)")
2703
2704 return *this;
2705 }
2706 */
2707
2708 /*!
2709 this method converts the uint type to this class
2710 */
2711 UInt<value_size> & operator=(uint i)
2712 {
2713 FromUInt(i);
2714
2715 return *this;
2716 }
2717
2718
2719 /*!
2720 a constructor for converting the uint to this class
2721 */
2722 /* UInt(uint i)
2723 {
2724 FromUInt(i);
2725 }
2726 */
2727
2728 /*!
2729 this method converts the sint type to this class
2730 */
2731 UInt<value_size> & operator=(sint i)
2732 {
2733 FromInt(i);
2734
2735 return *this;
2736 }
2737
2738
2739 /*!
2740 a constructor for converting the sint to this class
2741
2742 look at the description of UInt::operator=(sint)
2743 */
2744 /* UInt(sint i)
2745 {
2746 FromInt(i);
2747 }
2748 */
2749
2750 #ifdef TTMATH_PLATFORM32
2751
2752
2753 /*!
2754 this method converts unsigned 64 bit int type to this class
2755 ***this method is created only on a 32bit platform***
2756 */
2757 uint FromUInt(ulint n)
2758 {
2759 table[0] = (uint)n;
2760
2761 if( value_size == 1 )
2762 {
2763 uint c = ((n >> TTMATH_BITS_PER_UINT) == 0) ? 0 : 1;
2764
2765 TTMATH_LOGC("UInt::FromUInt(ulint)", c)
2766 return c;
2767 }
2768
2769 table[1] = (uint)(n >> TTMATH_BITS_PER_UINT);
2770
2771 for(uint i=2 ; i<value_size ; ++i)
2772 table[i] = 0;
2773
2774 TTMATH_LOG("UInt::FromUInt(ulint)")
2775
2776 return 0;
2777 }
2778
2779
2780 /*!
2781 this method converts unsigned 64 bit int type to this class
2782 ***this method is created only on a 32bit platform***
2783 */
2784 uint FromInt(ulint n)
2785 {
2786 return FromUInt(n);
2787 }
2788
2789
2790 /*!
2791 this method converts signed 64 bit int type to this class
2792 ***this method is created only on a 32bit platform***
2793 */
2794 uint FromInt(slint n)
2795 {
2796 uint c = FromUInt(ulint(n));
2797
2798 if( c || n < 0 )
2799 return 1;
2800
2801 return 0;
2802 }
2803
2804
2805 /*!
2806 this operator converts unsigned 64 bit int type to this class
2807 ***this operator is created only on a 32bit platform***
2808 */
2809 UInt<value_size> & operator=(ulint n)
2810 {
2811 FromUInt(n);
2812
2813 return *this;
2814 }
2815
2816
2817 /*!
2818 a constructor for converting unsigned 64 bit int to this class
2819 ***this constructor is created only on a 32bit platform***
2820 */
2821 /* UInt(ulint n)
2822 {
2823 FromUInt(n);
2824 }
2825 */
2826
2827 /*!
2828 this operator converts signed 64 bit int type to this class
2829 ***this operator is created only on a 32bit platform***
2830 */
2831 UInt<value_size> & operator=(slint n)
2832 {
2833 FromInt(n);
2834
2835 return *this;
2836 }
2837
2838
2839 /*!
2840 a constructor for converting signed 64 bit int to this class
2841 ***this constructor is created only on a 32bit platform***
2842 */
2843 /* UInt(slint n)
2844 {
2845 FromInt(n);
2846 }
2847 */
2848 #endif
2849
2850
2851
2852 #ifdef TTMATH_PLATFORM64
2853
2854
2855 /*!
2856 this method converts 32 bit unsigned int type to this class
2857 ***this operator is created only on a 64bit platform***
2858 */
2859 uint FromUInt(unsigned int i)
2860 {
2861 return FromUInt(uint(i));
2862 }
2863
2864 /*!
2865 this method converts 32 bit unsigned int type to this class
2866 ***this operator is created only on a 64bit platform***
2867 */
2868 uint FromInt(unsigned int i)
2869 {
2870 return FromUInt(uint(i));
2871 }
2872
2873
2874 /*!
2875 this method converts 32 bit signed int type to this class
2876 ***this operator is created only on a 64bit platform***
2877 */
2878 uint FromInt(signed int i)
2879 {
2880 return FromInt(sint(i));
2881 }
2882
2883
2884 /*!
2885 this operator converts 32 bit unsigned int type to this class
2886 ***this operator is created only on a 64bit platform***
2887 */
2888 UInt<value_size> & operator=(unsigned int i)
2889 {
2890 FromUInt(i);
2891
2892 return *this;
2893 }
2894
2895
2896 /*!
2897 a constructor for converting 32 bit unsigned int to this class
2898 ***this constructor is created only on a 64bit platform***
2899 */
2900 /* UInt(unsigned int i)
2901 {
2902 FromUInt(i);
2903 }
2904 */
2905
2906 /*!
2907 an operator for converting 32 bit signed int to this class
2908 ***this constructor is created only on a 64bit platform***
2909 */
2910 UInt<value_size> & operator=(signed int i)
2911 {
2912 FromInt(i);
2913
2914 return *this;
2915 }
2916
2917
2918 /*!
2919 a constructor for converting 32 bit signed int to this class
2920 ***this constructor is created only on a 64bit platform***
2921 */
2922 /* UInt(signed int i)
2923 {
2924 FromInt(i);
2925 }
2926 */
2927
2928 #endif
2929
2930
2931
2932
2933
2934 /*!
2935 a constructor for converting a string to this class (with the base=10)
2936 */
2937 /* UInt(const char * s)
2938 {
2939 FromString(s);
2940 }
2941 */
2942
2943 /*!
2944 a constructor for converting a string to this class (with the base=10)
2945 */
2946 /* UInt(const std::string & s)
2947 {
2948 FromString( s.c_str() );
2949 }
2950 */
2951
2952 #ifndef TTMATH_DONT_USE_WCHAR
2953
2954 /*!
2955 a constructor for converting a string to this class (with the base=10)
2956 */
2957 UInt(const wchar_t * s)
2958 {
2959 FromString(s);
2960 }
2961
2962
2963 /*!
2964 a constructor for converting a string to this class (with the base=10)
2965 */
2966 UInt(const std::wstring & s)
2967 {
2968 FromString( s.c_str() );
2969 }
2970
2971 #endif
2972
2973
2974
2975
2976 /*!
2977 a default constructor
2978
2979 we don't clear the table
2980 */
2981 /* UInt()
2982 {
2983 // when macro TTMATH_DEBUG_LOG is defined
2984 // we set special values to the table
2985 // in order to be everywhere the same value of the UInt object
2986 // without this it would be difficult to analyse the log file
2987 #ifdef TTMATH_DEBUG_LOG
2988 #ifdef TTMATH_PLATFORM32
2989 for(uint i=0 ; i<value_size ; ++i)
2990 table[i] = 0xc1c1c1c1;
2991 #else
2992 for(uint i=0 ; i<value_size ; ++i)
2993 table[i] = 0xc1c1c1c1c1c1c1c1;
2994 #endif
2995 #endif
2996 }
2997 */
2998
2999 /*!
3000 a copy constructor
3001 */
3002 /* UInt(const UInt<value_size> & u)
3003 {
3004 for(uint i=0 ; i<value_size ; ++i)
3005 table[i] = u.table[i];
3006
3007 TTMATH_LOG("UInt::UInt(UInt<>)")
3008 }
3009 */
3010
3011
3012 /*!
3013 a template for producting constructors for copying from another types
3014 */
3015 /* template<uint argument_size>
3016 UInt(const UInt<argument_size> & u)
3017 {
3018 // look that 'size' we still set as 'value_size' and not as u.value_size
3019 FromUInt(u);
3020 }
3021 */
3022
3023
3024
3025 /*!
3026 a destructor
3027 */
3028 /* ~UInt()
3029 {
3030 }
3031 */
3032
3033 /*!
3034 this method returns the lowest value from table
3035
3036 we must be sure when we using this method whether the value
3037 will hold in an uint type or not (the rest value from the table must be zero)
3038 */
3039 uint ToUInt() const
3040 {
3041 return table[0];
3042 }
3043
3044
3045 /*!
3046 this method converts the value to uint type
3047 can return a carry if the value is too long to store it in uint type
3048 */
3049 uint ToUInt(uint & result) const
3050 {
3051 result = table[0];
3052
3053 for(uint i=1 ; i<value_size ; ++i)
3054 if( table[i] != 0 )
3055 return 1;
3056
3057 return 0;
3058 }
3059
3060
3061 /*!
3062 this method converts the value to uint type
3063 can return a carry if the value is too long to store it in uint type
3064 */
3065 uint ToInt(uint & result) const
3066 {
3067 return ToUInt(result);
3068 }
3069
3070
3071 /*!
3072 this method converts the value to sint type (signed integer)
3073 can return a carry if the value is too long to store it in sint type
3074 */
3075 uint ToInt(sint & result) const
3076 {
3077 result = sint(table[0]);
3078
3079 if( (result & TTMATH_UINT_HIGHEST_BIT) != 0 )
3080 return 1;
3081
3082 for(uint i=1 ; i<value_size ; ++i)
3083 if( table[i] != 0 )
3084 return 1;
3085
3086 return 0;
3087 }
3088
3089
3090 #ifdef TTMATH_PLATFORM32
3091
3092 /*!
3093 this method converts the value to ulint type (64 bit unsigned integer)
3094 can return a carry if the value is too long to store it in ulint type
3095 *** this method is created only on a 32 bit platform ***
3096 */
3097 uint ToUInt(ulint & result) const
3098 {
3099 if( value_size == 1 )
3100 {
3101 result = table[0];
3102 }
3103 else
3104 {
3105 uint low = table[0];
3106 uint high = table[1];
3107
3108 result = low;
3109 result |= (ulint(high) << TTMATH_BITS_PER_UINT);
3110
3111 for(uint i=2 ; i<value_size ; ++i)
3112 if( table[i] != 0 )
3113 return 1;
3114 }
3115
3116 return 0;
3117 }
3118
3119
3120 /*!
3121 this method converts the value to ulint type (64 bit unsigned integer)
3122 can return a carry if the value is too long to store it in ulint type
3123 *** this method is created only on a 32 bit platform ***
3124 */
3125 uint ToInt(ulint & result) const
3126 {
3127 return ToUInt(result);
3128 }
3129
3130
3131 /*!
3132 this method converts the value to slint type (64 bit signed integer)
3133 can return a carry if the value is too long to store it in slint type
3134 *** this method is created only on a 32 bit platform ***
3135 */
3136 uint ToInt(slint & result) const
3137 {
3138 ulint temp;
3139
3140 uint c = ToUInt(temp);
3141 result = slint(temp);
3142
3143 if( c || result < 0 )
3144 return 1;
3145
3146 return 0;
3147 }
3148
3149 #endif
3150
3151
3152
3153 #ifdef TTMATH_PLATFORM64
3154
3155 /*!
3156 this method converts the value to a 32 unsigned integer
3157 can return a carry if the value is too long to store it in this type
3158 *** this method is created only on a 64 bit platform ***
3159 */
3160 uint ToUInt(unsigned int & result) const
3161 {
3162 result = (unsigned int)table[0];
3163
3164 if( (table[0] >> 32) != 0 )
3165 return 1;
3166
3167 for(uint i=1 ; i<value_size ; ++i)
3168 if( table[i] != 0 )
3169 return 1;
3170
3171 return 0;
3172 }
3173
3174
3175 /*!
3176 this method converts the value to a 32 unsigned integer
3177 can return a carry if the value is too long to store it in this type
3178 *** this method is created only on a 64 bit platform ***
3179 */
3180 uint ToInt(unsigned int & result) const
3181 {
3182 return ToUInt(result);
3183 }
3184
3185
3186 /*!
3187 this method converts the value to a 32 signed integer
3188 can return a carry if the value is too long to store it in this type
3189 *** this method is created only on a 64 bit platform ***
3190 */
3191 uint ToInt(int & result) const
3192 {
3193 unsigned int temp;
3194
3195 uint c = ToUInt(temp);
3196 result = int(temp);
3197
3198 if( c || result < 0 )
3199 return 1;
3200
3201 return 0;
3202 }
3203
3204
3205 #endif
3206
3207
3208
3209
3210 protected:
3211
3212 /*!
3213 an auxiliary method for converting into the string
3214 it returns the log (with the base 2) from x
3215 where x is in <2;16>
3216 */
3217 double ToStringLog2(uint x) const
3218 {
3219 static double log_tab[] = {
3220 1.000000000000000000,
3221 0.630929753571457437,
3222 0.500000000000000000,
3223 0.430676558073393050,
3224 0.386852807234541586,
3225 0.356207187108022176,
3226 0.333333333333333333,
3227 0.315464876785728718,
3228 0.301029995663981195,
3229 0.289064826317887859,
3230 0.278942945651129843,
3231 0.270238154427319741,
3232 0.262649535037193547,
3233 0.255958024809815489,
3234 0.250000000000000000
3235 };
3236
3237 if( x<2 || x>16 )
3238 return 0;
3239
3240 return log_tab[x-2];
3241 }
3242
3243
3244 public:
3245
3246
3247 /*!
3248 an auxiliary method for converting to a string
3249 it's used from Int::ToString() too (negative is set true then)
3250 */
3251 template<class string_type>
3252 void ToStringBase(string_type & result, uint b = 10, bool negative = false) const
3253 {
3254 UInt<value_size> temp(*this);
3255 uint rest, table_id, index, digits;
3256 double digits_d;
3257 char character;
3258
3259 result.clear();
3260
3261 if( b<2 || b>16 )
3262 return;
3263
3264 if( !FindLeadingBit(table_id, index) )
3265 {
3266 result = '0';
3267 return;
3268 }
3269
3270 if( negative )
3271 result = '-';
3272
3273 digits_d = table_id; // for not making an overflow in uint type
3274 digits_d *= TTMATH_BITS_PER_UINT;
3275 digits_d += index + 1;
3276 digits_d *= ToStringLog2(b);
3277 digits = static_cast<uint>(digits_d) + 3; // plus some epsilon
3278
3279 if( result.capacity() < digits )
3280 result.reserve(digits);
3281
3282 do
3283 {
3284 temp.DivInt(b, &rest);
3285 character = static_cast<char>(Misc::DigitToChar(rest));
3286 result.insert(result.end(), character);
3287 }
3288 while( !temp.IsZero() );
3289
3290 size_t i1 = negative ? 1 : 0; // the first is a hyphen (when negative is true)
3291 size_t i2 = result.size() - 1;
3292
3293 for( ; i1 < i2 ; ++i1, --i2 )
3294 {
3295 char tempc = static_cast<char>(result[i1]);
3296 result[i1] = result[i2];
3297 result[i2] = tempc;
3298 }
3299 }
3300
3301
3302
3303 /*!
3304 this method converts the value to a string with a base equal 'b'
3305 */
3306 void ToString(std::string & result, uint b = 10) const
3307 {
3308 return ToStringBase(result, b);
3309 }
3310
3311
3312 std::string ToString(uint b = 10) const
3313 {
3314 std::string result;
3315 ToStringBase(result, b);
3316
3317 return result;
3318 }
3319
3320
3321 #ifndef TTMATH_DONT_USE_WCHAR
3322
3323 void ToString(std::wstring & result, uint b = 10) const
3324 {
3325 return ToStringBase(result, b);
3326 }
3327
3328 std::wstring ToWString(uint b = 10) const
3329 {
3330 std::wstring result;
3331 ToStringBase(result, b);
3332
3333 return result;
3334 }
3335
3336 #endif
3337
3338
3339
3340 private:
3341
3342 /*!
3343 an auxiliary method for converting from a string
3344 */
3345 template<class char_type>
3346 uint FromStringBase(const char_type * s, uint b = 10, const char_type ** after_source = 0, bool * value_read = 0)
3347 {
3348 UInt<value_size> base;
3349 base.FromUInt( b );
3350 UInt<value_size> temp;
3351 sint z;
3352 uint c = 0;
3353
3354 SetZero();
3355 temp.SetZero();
3356 Misc::SkipWhiteCharacters(s);
3357
3358 if( after_source )
3359 *after_source = s;
3360
3361 if( value_read )
3362 *value_read = false;
3363
3364 if( b<2 || b>16 )
3365 return 1;
3366
3367
3368 for( ; (z=Misc::CharToDigit(*s, b)) != -1 ; ++s)
3369 {
3370 if( value_read )
3371 *value_read = true;
3372
3373 if( c == 0 )
3374 {
3375 temp.table[0] = z;
3376
3377 c += Mul(base); // !! IMPROVE ME: there can be used MulInt here
3378 c += Add(temp);
3379 }
3380 }
3381
3382 if( after_source )
3383 *after_source = s;
3384
3385 TTMATH_LOGC("UInt::FromString", c)
3386
3387 return (c==0)? 0 : 1;
3388 }
3389
3390
3391 public:
3392
3393
3394 /*!
3395 this method converts a string into its value
3396 it returns carry=1 if the value will be too big or an incorrect base 'b' is given
3397
3398 string is ended with a non-digit value, for example:
3399 "12" will be translated to 12
3400 as well as:
3401 "12foo" will be translated to 12 too
3402
3403 existing first white characters will be ommited
3404
3405 if the value from s is too large the rest digits will be skipped
3406
3407 after_source (if exists) is pointing at the end of the parsed string
3408
3409 value_read (if exists) tells whether something has actually been read (at least one digit)
3410 */
3411 uint FromString(const char * s, uint b = 10, const char ** after_source = 0, bool * value_read = 0)
3412 {
3413 return FromStringBase(s, b, after_source, value_read);
3414 }
3415
3416
3417 /*!
3418 this method converts a string into its value
3419
3420 (it returns carry=1 if the value will be too big or an incorrect base 'b' is given)
3421 */
3422 uint FromString(const std::string & s, uint b = 10)
3423 {
3424 return FromString( s.c_str(), b );
3425 }
3426
3427
3428 /*!
3429 this operator converts a string into its value (with base = 10)
3430 */
3431 UInt<value_size> & operator=(const char * s)
3432 {
3433 FromString(s);
3434
3435 return *this;
3436 }
3437
3438
3439 /*!
3440 this operator converts a string into its value (with base = 10)
3441 */
3442 UInt<value_size> & operator=(const std::string & s)
3443 {
3444 FromString( s.c_str() );
3445
3446 return *this;
3447 }
3448
3449
3450
3451 #ifndef TTMATH_DONT_USE_WCHAR
3452
3453 /*!
3454 this method converts a string into its value
3455 */
3456 uint FromString(const wchar_t * s, uint b = 10, const wchar_t ** after_source = 0, bool * value_read = 0)
3457 {
3458 return FromStringBase(s, b, after_source, value_read);
3459 }
3460
3461
3462 /*!
3463 this method converts a string into its value
3464
3465 (it returns carry=1 if the value will be too big or an incorrect base 'b' is given)
3466 */
3467 uint FromString(const std::wstring & s, uint b = 10)
3468 {
3469 return FromString( s.c_str(), b );
3470 }
3471
3472
3473 /*!
3474 this operator converts a string into its value (with base = 10)
3475 */
3476 UInt<value_size> & operator=(const wchar_t * s)
3477 {
3478 FromString(s);
3479
3480 return *this;
3481 }
3482
3483
3484 /*!
3485 this operator converts a string into its value (with base = 10)
3486 */
3487 UInt<value_size> & operator=(const std::wstring & s)
3488 {
3489 FromString( s.c_str() );
3490
3491 return *this;
3492 }
3493
3494 #endif
3495
3496
3497 /*!
3498 *
3499 * methods for comparing
3500 *
3501 */
3502
3503
3504 /*!
3505 this method returns true if 'this' is smaller than 'l'
3506
3507 'index' is an index of the first word from will be the comparison performed
3508 (note: we start the comparison from back - from the last word, when index is -1 /default/
3509 it is automatically set into the last word)
3510 I introduced it for some kind of optimization made in the second division algorithm (Div2)
3511 */
3512 bool CmpSmaller(const UInt<value_size> & l, sint index = -1) const
3513 {
3514 sint i;
3515
3516 if( index==-1 || index>=sint(value_size) )
3517 i = value_size - 1;
3518 else
3519 i = index;
3520
3521
3522 for( ; i>=0 ; --i)
3523 {
3524 if( table[i] != l.table[i] )
3525 return table[i] < l.table[i];
3526 }
3527
3528 // they're equal
3529 return false;
3530 }
3531
3532
3533
3534 /*!
3535 this method returns true if 'this' is bigger than 'l'
3536
3537 'index' is an index of the first word from will be the comparison performed
3538 (note: we start the comparison from back - from the last word, when index is -1 /default/
3539 it is automatically set into the last word)
3540
3541 I introduced it for some kind of optimization made in the second division algorithm (Div2)
3542 */
3543 bool CmpBigger(const UInt<value_size> & l, sint index = -1) const
3544 {
3545 sint i;
3546
3547 if( index==-1 || index>=sint(value_size) )
3548 i = value_size - 1;
3549 else
3550 i = index;
3551
3552
3553 for( ; i>=0 ; --i)
3554 {
3555 if( table[i] != l.table[i] )
3556 return table[i] > l.table[i];
3557 }
3558
3559 // they're equal
3560 return false;
3561 }
3562
3563
3564 /*!
3565 this method returns true if 'this' is equal 'l'
3566
3567 'index' is an index of the first word from will be the comparison performed
3568 (note: we start the comparison from back - from the last word, when index is -1 /default/
3569 it is automatically set into the last word)
3570 */
3571 bool CmpEqual(const UInt<value_size> & l, sint index = -1) const
3572 {
3573 sint i;
3574
3575 if( index==-1 || index>=sint(value_size) )
3576 i = value_size - 1;
3577 else
3578 i = index;
3579
3580
3581 for( ; i>=0 ; --i)
3582 if( table[i] != l.table[i] )
3583 return false;
3584
3585 return true;
3586 }
3587
3588
3589
3590 /*!
3591 this method returns true if 'this' is smaller than or equal 'l'
3592
3593 'index' is an index of the first word from will be the comparison performed
3594 (note: we start the comparison from back - from the last word, when index is -1 /default/
3595 it is automatically set into the last word)
3596 */
3597 bool CmpSmallerEqual(const UInt<value_size> & l, sint index=-1) const
3598 {
3599 sint i;
3600
3601 if( index==-1 || index>=sint(value_size) )
3602 i = value_size - 1;
3603 else
3604 i = index;
3605
3606
3607 for( ; i>=0 ; --i)
3608 {
3609 if( table[i] != l.table[i] )
3610 return table[i] < l.table[i];
3611 }
3612
3613 // they're equal
3614 return true;
3615 }
3616
3617
3618
3619 /*!
3620 this method returns true if 'this' is bigger than or equal 'l'
3621
3622 'index' is an index of the first word from will be the comparison performed
3623 (note: we start the comparison from back - from the last word, when index is -1 /default/
3624 it is automatically set into the last word)
3625 */
3626 bool CmpBiggerEqual(const UInt<value_size> & l, sint index=-1) const
3627 {
3628 sint i;
3629
3630 if( index==-1 || index>=sint(value_size) )
3631 i = value_size - 1;
3632 else
3633 i = index;
3634
3635
3636 for( ; i>=0 ; --i)
3637 {
3638 if( table[i] != l.table[i] )
3639 return table[i] > l.table[i];
3640 }
3641
3642 // they're equal
3643 return true;
3644 }
3645
3646
3647 /*
3648 operators for comparising
3649 */
3650
3651 bool operator<(const UInt<value_size> & l) const
3652 {
3653 return CmpSmaller(l);
3654 }
3655
3656
3657 bool operator>(const UInt<value_size> & l) const
3658 {
3659 return CmpBigger(l);
3660 }
3661
3662
3663 bool operator==(const UInt<value_size> & l) const
3664 {
3665 return CmpEqual(l);
3666 }
3667
3668
3669 bool operator!=(const UInt<value_size> & l) const
3670 {
3671 return !operator==(l);
3672 }
3673
3674
3675 bool operator<=(const UInt<value_size> & l) const
3676 {
3677 return CmpSmallerEqual(l);
3678 }
3679
3680 bool operator>=(const UInt<value_size> & l) const
3681 {
3682 return CmpBiggerEqual(l);
3683 }
3684
3685
3686 /*!
3687 *
3688 * standard mathematical operators
3689 *
3690 */
3691
3692 UInt<value_size> operator-(const UInt<value_size> & p2) const
3693 {
3694 UInt<value_size> temp(*this);
3695
3696 temp.Sub(p2);
3697
3698 return temp;
3699 }
3700
3701 UInt<value_size> & operator-=(const UInt<value_size> & p2)
3702 {
3703 Sub(p2);
3704
3705 return *this;
3706 }
3707
3708 UInt<value_size> operator+(const UInt<value_size> & p2) const
3709 {
3710 UInt<value_size> temp(*this);
3711
3712 temp.Add(p2);
3713
3714 return temp;
3715 }
3716
3717 UInt<value_size> & operator+=(const UInt<value_size> & p2)
3718 {
3719 Add(p2);
3720
3721 return *this;
3722 }
3723
3724
3725 UInt<value_size> operator*(const UInt<value_size> & p2) const
3726 {
3727 UInt<value_size> temp(*this);
3728
3729 temp.Mul(p2);
3730
3731 return temp;
3732 }
3733
3734
3735 UInt<value_size> & operator*=(const UInt<value_size> & p2)
3736 {
3737 Mul(p2);
3738
3739 return *this;
3740 }
3741
3742
3743 UInt<value_size> operator/(const UInt<value_size> & p2) const
3744 {
3745 UInt<value_size> temp(*this);
3746
3747 temp.Div(p2);
3748
3749 return temp;
3750 }
3751
3752
3753 UInt<value_size> & operator/=(const UInt<value_size> & p2)
3754 {
3755 Div(p2);
3756
3757 return *this;
3758 }
3759
3760
3761 UInt<value_size> operator%(const UInt<value_size> & p2) const
3762 {
3763 UInt<value_size> temp(*this);
3764 UInt<value_size> remainder;
3765
3766 temp.Div( p2, remainder );
3767
3768 return remainder;
3769 }
3770
3771
3772 UInt<value_size> & operator%=(const UInt<value_size> & p2)
3773 {
3774 UInt<value_size> remainder;
3775
3776 Div( p2, remainder );
3777 operator=(remainder);
3778
3779 return *this;
3780 }
3781
3782
3783 /*!
3784 Prefix operator e.g ++variable
3785 */
3786 UInt<value_size> & operator++()
3787 {
3788 AddOne();
3789
3790 return *this;
3791 }
3792
3793
3794 /*!
3795 Postfix operator e.g variable++
3796 */
3797 UInt<value_size> operator++(int)
3798 {
3799 UInt<value_size> temp( *this );
3800
3801 AddOne();
3802
3803 return temp;
3804 }
3805
3806
3807 UInt<value_size> & operator--()
3808 {
3809 SubOne();
3810
3811 return *this;
3812 }
3813
3814
3815 UInt<value_size> operator--(int)
3816 {
3817 UInt<value_size> temp( *this );
3818
3819 SubOne();
3820
3821 return temp;
3822 }
3823
3824
3825
3826 /*!
3827 *
3828 * bitwise operators
3829 *
3830 */
3831
3832 UInt<value_size> operator~() const
3833 {
3834 UInt<value_size> temp( *this );
3835
3836 temp.BitNot();
3837
3838 return temp;
3839 }
3840
3841
3842 UInt<value_size> operator&(const UInt<value_size> & p2) const
3843 {
3844 UInt<value_size> temp( *this );
3845
3846 temp.BitAnd(p2);
3847
3848 return temp;
3849 }
3850
3851
3852 UInt<value_size> & operator&=(const UInt<value_size> & p2)
3853 {
3854 BitAnd(p2);
3855
3856 return *this;
3857 }
3858
3859
3860 UInt<value_size> operator|(const UInt<value_size> & p2) const
3861 {
3862 UInt<value_size> temp( *this );
3863
3864 temp.BitOr(p2);
3865
3866 return temp;
3867 }
3868
3869
3870 UInt<value_size> & operator|=(const UInt<value_size> & p2)
3871 {
3872 BitOr(p2);
3873
3874 return *this;
3875 }
3876
3877
3878 UInt<value_size> operator^(const UInt<value_size> & p2) const
3879 {
3880 UInt<value_size> temp( *this );
3881
3882 temp.BitXor(p2);
3883
3884 return temp;
3885 }
3886
3887
3888 UInt<value_size> & operator^=(const UInt<value_size> & p2)
3889 {
3890 BitXor(p2);
3891
3892 return *this;
3893 }
3894
3895
3896 UInt<value_size> operator>>(int move) const
3897 {
3898 UInt<value_size> temp( *this );
3899
3900 temp.Rcr(move);
3901
3902 return temp;
3903 }
3904
3905
3906 UInt<value_size> & operator>>=(int move)
3907 {
3908 Rcr(move);
3909
3910 return *this;
3911 }
3912
3913
3914 UInt<value_size> operator<<(int move) const
3915 {
3916 UInt<value_size> temp( *this );
3917
3918 temp.Rcl(move);
3919
3920 return temp;
3921 }
3922
3923
3924 UInt<value_size> & operator<<=(int move)
3925 {
3926 Rcl(move);
3927
3928 return *this;
3929 }
3930
3931
3932 /*!
3933 *
3934 * input/output operators for standard streams
3935 *
3936 * (they are very simple, in the future they should be changed)
3937 *
3938 */
3939
3940
3941 private:
3942
3943
3944 /*!
3945 an auxiliary method for outputing to standard streams
3946 */
3947 template<class ostream_type, class string_type>
3948 static ostream_type & OutputToStream(ostream_type & s, const UInt<value_size> & l)
3949 {
3950 string_type ss;
3951
3952 l.ToString(ss);
3953 s << ss;
3954
3955 return s;
3956 }
3957
3958
3959 public:
3960
3961
3962 /*!
3963 output to standard streams
3964 */
3965 friend std::ostream & operator<<(std::ostream & s, const UInt<value_size> & l)
3966 {
3967 return OutputToStream<std::ostream, std::string>(s, l);
3968 }
3969
3970
3971 #ifndef TTMATH_DONT_USE_WCHAR
3972
3973 /*!
3974 output to standard streams
3975 */
3976 friend std::wostream & operator<<(std::wostream & s, const UInt<value_size> & l)
3977 {
3978 return OutputToStream<std::wostream, std::wstring>(s, l);
3979 }
3980
3981 #endif
3982
3983
3984
3985 private:
3986
3987 /*!
3988 an auxiliary method for reading from standard streams
3989 */
3990 template<class istream_type, class string_type, class char_type>
3991 static istream_type & InputFromStream(istream_type & s, UInt<value_size> & l)
3992 {
3993 string_type ss;
3994
3995 // char or wchar_t for operator>>
3996 char_type z;
3997
3998 // operator>> omits white characters if they're set for ommiting
3999 s >> z;
4000
4001 // we're reading only digits (base=10)
4002 while( s.good() && Misc::CharToDigit(z, 10)>=0 )
4003 {
4004 ss += z;
4005 z = static_cast<char_type>(s.get());
4006 }
4007
4008 // we're leaving the last read character
4009 // (it's not belonging to the value)
4010 s.unget();
4011
4012 l.FromString(ss);
4013
4014 return s;
4015 }
4016
4017 public:
4018
4019
4020 /*!
4021 input from standard streams
4022 */
4023 friend std::istream & operator>>(std::istream & s, UInt<value_size> & l)
4024 {
4025 return InputFromStream<std::istream, std::string, char>(s, l);
4026 }
4027
4028
4029 #ifndef TTMATH_DONT_USE_WCHAR
4030
4031 /*!
4032 input from standard streams
4033 */
4034 friend std::wistream & operator>>(std::wistream & s, UInt<value_size> & l)
4035 {
4036 return InputFromStream<std::wistream, std::wstring, wchar_t>(s, l);
4037 }
4038
4039 #endif
4040
4041
4042 /*
4043 Following methods are defined in:
4044 ttmathuint_x86.h
4045 ttmathuint_x86_64.h
4046 ttmathuint_noasm.h
4047 */
4048
4049 #ifdef TTMATH_NOASM
4050 static uint AddTwoWords(uint a, uint b, uint carry, uint * result);
4051 static uint SubTwoWords(uint a, uint b, uint carry, uint * result);
4052
4053 #ifdef TTMATH_PLATFORM64
4054
4055 union uint_
4056 {
4057 struct
4058 {
4059 unsigned int low; // 32 bit
4060 unsigned int high; // 32 bit
4061 } u_;
4062
4063 uint u; // 64 bit
4064 };
4065
4066
4067 static void DivTwoWords2(uint a,uint b, uint c, uint * r, uint * rest);
4068 static uint DivTwoWordsNormalize(uint_ & a_, uint_ & b_, uint_ & c_);
4069 static uint DivTwoWordsUnnormalize(uint u, uint d);
4070 static unsigned int DivTwoWordsCalculate(uint_ u_, unsigned int u3, uint_ v_);
4071 static void MultiplySubtract(uint_ & u_, unsigned int & u3, unsigned int & q, uint_ v_);
4072
4073 #endif // TTMATH_PLATFORM64
4074 #endif // TTMATH_NOASM
4075
4076
4077 private:
4078 uint Rcl2_one(uint c);
4079 uint Rcr2_one(uint c);
4080 uint Rcl2(uint bits, uint c);
4081 uint Rcr2(uint bits, uint c);
4082
4083 public:
4084 static const char * LibTypeStr();
4085 static LibTypeCode LibType();
4086 uint Add(const UInt<value_size> & ss2, uint c=0);
4087 uint AddInt(uint value, uint index = 0);
4088 uint AddTwoInts(uint x2, uint x1, uint index);
4089 static uint AddVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result);
4090 uint Sub(const UInt<value_size> & ss2, uint c=0);
4091 uint SubInt(uint value, uint index = 0);
4092 static uint SubVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result);
4093 static sint FindLeadingBitInWord(uint x);
4094 static sint FindLowestBitInWord(uint x);
4095 static uint SetBitInWord(uint & value, uint bit);
4096 static void MulTwoWords(uint a, uint b, uint * result_high, uint * result_low);
4097 static void DivTwoWords(uint a,uint b, uint c, uint * r, uint * rest);
4098
4099 };
4100
4101
4102
4103 /*!
4104 this specialization is needed in order to not confused the compiler "error: ISO C++ forbids zero-size array"
4105 when compiling Mul3Big2() method
4106 */
4107 template<>
4108 class UInt<0>
4109 {
4110 public:
4111 uint table[1];
4112
4113 void Mul2Big(const UInt<0> &, UInt<0> &) { TTMATH_ASSERT(false) };
4114 void SetZero() { TTMATH_ASSERT(false) };
4115 uint AddTwoInts(uint, uint, uint) { TTMATH_ASSERT(false) return 0; };
4116 };
4117
4118
4119 } //namespace
4120
4121
4122 #include "ttmathuint_x86.h"
4123 #include "ttmathuint_x86_64.h"
4124 #include "ttmathuint_noasm.h"
4125
4126 #endif