GEOS  3.8.0dev
ttmathuint.h
Go to the documentation of this file.
1 /*
2  * This file is a part of TTMath Bignum Library
3  * and is distributed under the 3-Clause BSD Licence.
4  * Author: Tomasz Sowa <t.sowa@ttmath.org>
5  */
6 
7 /*
8  * Copyright (c) 2006-2017, 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 
49 #include <iostream>
50 #include <iomanip>
51 
52 
53 #include "ttmathtypes.h"
54 #include "ttmathmisc.h"
55 
56 
57 
61 namespace ttmath
62 {
63 
72 template<uint value_size>
73 class UInt
74 {
75 public:
76 
81  uint table[value_size];
82 
83 
84 
96  template<class ostream_type>
97  void PrintTable(ostream_type & output) const
98  {
99  // how many columns there'll be
100  const int columns = 8;
101 
102  int c = 1;
103  for(int i=value_size-1 ; i>=0 ; --i)
104  {
105  output << "0x" << std::setfill('0');
106 
107  #ifdef TTMATH_PLATFORM32
108  output << std::setw(8);
109  #else
110  output << std::setw(16);
111  #endif
112 
113  output << std::hex << table[i];
114 
115  if( i>0 )
116  {
117  output << ", ";
118 
119  if( ++c > columns )
120  {
121  output << std::endl;
122  c = 1;
123  }
124  }
125  }
126 
127  output << std::dec << std::endl;
128  }
129 
130 
134  template<class char_type, class ostream_type>
135  static void PrintVectorLog(const char_type * msg, ostream_type & output, const uint * vector, uint vector_len)
136  {
137  output << msg << std::endl;
138 
139  for(uint i=0 ; i<vector_len ; ++i)
140  output << " table[" << i << "]: " << vector[i] << std::endl;
141  }
142 
143 
147  template<class char_type, class ostream_type>
148  static void PrintVectorLog(const char_type * msg, uint carry, ostream_type & output, const uint * vector, uint vector_len)
149  {
150  PrintVectorLog(msg, output, vector, vector_len);
151  output << " carry: " << carry << std::endl;
152  }
153 
154 
158  template<class char_type, class ostream_type>
159  void PrintLog(const char_type * msg, ostream_type & output) const
160  {
161  PrintVectorLog(msg, output, table, value_size);
162  }
163 
164 
168  template<class char_type, class ostream_type>
169  void PrintLog(const char_type * msg, uint carry, ostream_type & output) const
170  {
171  PrintVectorLog(msg, output, table, value_size);
172  output << " carry: " << carry << std::endl;
173  }
174 
175 
179  uint Size() const
180  {
181  return value_size;
182  }
183 
184 
188  void SetZero()
189  {
190  // in the future here can be 'memset'
191 
192  for(uint i=0 ; i<value_size ; ++i)
193  table[i] = 0;
194 
195  TTMATH_LOG("UInt::SetZero")
196  }
197 
198 
202  void SetOne()
203  {
204  SetZero();
205  table[0] = 1;
206 
207  TTMATH_LOG("UInt::SetOne")
208  }
209 
210 
215  void SetMax()
216  {
217  for(uint i=0 ; i<value_size ; ++i)
218  table[i] = TTMATH_UINT_MAX_VALUE;
219 
220  TTMATH_LOG("UInt::SetMax")
221  }
222 
223 
228  void SetMin()
229  {
230  SetZero();
231 
232  TTMATH_LOG("UInt::SetMin")
233  }
234 
235 
239  void Swap(UInt<value_size> & ss2)
240  {
241  for(uint i=0 ; i<value_size ; ++i)
242  {
243  uint temp = table[i];
244  table[i] = ss2.table[i];
245  ss2.table[i] = temp;
246  }
247  }
248 
249 
250 #ifdef TTMATH_PLATFORM32
251 
266  void SetFromTable(const uint * temp_table, uint temp_table_len)
267  {
268  uint temp_table_index = 0;
269  sint i; // 'i' with a sign
270 
271  for(i=value_size-1 ; i>=0 && temp_table_index<temp_table_len; --i, ++temp_table_index)
272  table[i] = temp_table[ temp_table_index ];
273 
274 
275  // rounding mantissa
276  if( temp_table_index < temp_table_len )
277  {
278  if( (temp_table[temp_table_index] & TTMATH_UINT_HIGHEST_BIT) != 0 )
279  {
280  /*
281  very simply rounding
282  if the bit from not used last word from temp_table is set to one
283  we're rouding the lowest word in the table
284 
285  in fact there should be a normal addition but
286  we don't use Add() or AddTwoInts() because these methods
287  can set a carry and then there'll be a small problem
288  for optimization
289  */
290  if( table[0] != TTMATH_UINT_MAX_VALUE )
291  ++table[0];
292  }
293  }
294 
295  // cleaning the rest of the mantissa
296  for( ; i>=0 ; --i)
297  table[i] = 0;
298 
299 
300  TTMATH_LOG("UInt::SetFromTable")
301  }
302 
303 #endif
304 
305 
306 #ifdef TTMATH_PLATFORM64
307 
325  void SetFromTable(const unsigned int * temp_table, uint temp_table_len)
326  {
327  uint temp_table_index = 0;
328  sint i; // 'i' with a sign
329 
330  for(i=value_size-1 ; i>=0 && temp_table_index<temp_table_len; --i, ++temp_table_index)
331  {
332  table[i] = uint(temp_table[ temp_table_index ]) << 32;
333 
334  ++temp_table_index;
335 
336  if( temp_table_index<temp_table_len )
337  table[i] |= temp_table[ temp_table_index ];
338  }
339 
340 
341  // rounding mantissa
342  if( temp_table_index < temp_table_len )
343  {
344  if( (temp_table[temp_table_index] & TTMATH_UINT_HIGHEST_BIT) != 0 )
345  {
346  /*
347  very simply rounding
348  if the bit from not used last word from temp_table is set to one
349  we're rouding the lowest word in the table
350 
351  in fact there should be a normal addition but
352  we don't use Add() or AddTwoInts() because these methods
353  can set a carry and then there'll be a small problem
354  for optimization
355  */
356  if( table[0] != TTMATH_UINT_MAX_VALUE )
357  ++table[0];
358  }
359  }
360 
361  // cleaning the rest of the mantissa
362  for( ; i >= 0 ; --i)
363  table[i] = 0;
364 
365  TTMATH_LOG("UInt::SetFromTable")
366  }
367 
368 #endif
369 
370 
371 
372 
373 
387  {
388  return AddInt(1);
389  }
390 
391 
396  {
397  return SubInt(1);
398  }
399 
400 
401 private:
402 
403 
409  void RclMoveAllWords(uint & rest_bits, uint & last_c, uint bits, uint c)
410  {
411  rest_bits = bits % TTMATH_BITS_PER_UINT;
412  uint all_words = bits / TTMATH_BITS_PER_UINT;
413  uint mask = ( c ) ? TTMATH_UINT_MAX_VALUE : 0;
414 
415 
416  if( all_words >= value_size )
417  {
418  if( all_words == value_size && rest_bits == 0 )
419  last_c = table[0] & 1;
420  // else: last_c is default set to 0
421 
422  // clearing
423  for(uint i = 0 ; i<value_size ; ++i)
424  table[i] = mask;
425 
426  rest_bits = 0;
427  }
428  else
429  if( all_words > 0 )
430  {
431  // 0 < all_words < value_size
432 
433  sint first, second;
434  last_c = table[value_size - all_words] & 1; // all_words is greater than 0
435 
436  // copying the first part of the value
437  for(first = value_size-1, second=first-all_words ; second>=0 ; --first, --second)
438  table[first] = table[second];
439 
440  // setting the rest to 'c'
441  for( ; first>=0 ; --first )
442  table[first] = mask;
443  }
444 
445  TTMATH_LOG("UInt::RclMoveAllWords")
446  }
447 
448 public:
449 
460  uint Rcl(uint bits, uint c=0)
461  {
462  uint last_c = 0;
463  uint rest_bits = bits;
464 
465  if( bits == 0 )
466  return 0;
467 
468  if( bits >= TTMATH_BITS_PER_UINT )
469  RclMoveAllWords(rest_bits, last_c, bits, c);
470 
471  if( rest_bits == 0 )
472  {
473  TTMATH_LOG("UInt::Rcl")
474  return last_c;
475  }
476 
477  // rest_bits is from 1 to TTMATH_BITS_PER_UINT-1 now
478  if( rest_bits == 1 )
479  {
480  last_c = Rcl2_one(c);
481  }
482  else if( rest_bits == 2 )
483  {
484  // performance tests showed that for rest_bits==2 it's better to use Rcl2_one twice instead of Rcl2(2,c)
485  Rcl2_one(c);
486  last_c = Rcl2_one(c);
487  }
488  else
489  {
490  last_c = Rcl2(rest_bits, c);
491  }
492 
493  TTMATH_LOGC("UInt::Rcl", last_c)
494 
495  return last_c;
496  }
497 
498 private:
499 
505  void RcrMoveAllWords(uint & rest_bits, uint & last_c, uint bits, uint c)
506  {
507  rest_bits = bits % TTMATH_BITS_PER_UINT;
508  uint all_words = bits / TTMATH_BITS_PER_UINT;
509  uint mask = ( c ) ? TTMATH_UINT_MAX_VALUE : 0;
510 
511 
512  if( all_words >= value_size )
513  {
514  if( all_words == value_size && rest_bits == 0 )
515  last_c = (table[value_size-1] & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0;
516  // else: last_c is default set to 0
517 
518  // clearing
519  for(uint i = 0 ; i<value_size ; ++i)
520  table[i] = mask;
521 
522  rest_bits = 0;
523  }
524  else if( all_words > 0 )
525  {
526  // 0 < all_words < value_size
527 
528  uint first, second;
529  last_c = (table[all_words - 1] & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0; // all_words is > 0
530 
531  // copying the first part of the value
532  for(first=0, second=all_words ; second<value_size ; ++first, ++second)
533  table[first] = table[second];
534 
535  // setting the rest to 'c'
536  for( ; first<value_size ; ++first )
537  table[first] = mask;
538  }
539 
540  TTMATH_LOG("UInt::RcrMoveAllWords")
541  }
542 
543 public:
544 
555  uint Rcr(uint bits, uint c=0)
556  {
557  uint last_c = 0;
558  uint rest_bits = bits;
559 
560  if( bits == 0 )
561  return 0;
562 
563  if( bits >= TTMATH_BITS_PER_UINT )
564  RcrMoveAllWords(rest_bits, last_c, bits, c);
565 
566  if( rest_bits == 0 )
567  {
568  TTMATH_LOG("UInt::Rcr")
569  return last_c;
570  }
571 
572  // rest_bits is from 1 to TTMATH_BITS_PER_UINT-1 now
573  if( rest_bits == 1 )
574  {
575  last_c = Rcr2_one(c);
576  }
577  else if( rest_bits == 2 )
578  {
579  // performance tests showed that for rest_bits==2 it's better to use Rcr2_one twice instead of Rcr2(2,c)
580  Rcr2_one(c);
581  last_c = Rcr2_one(c);
582  }
583  else
584  {
585  last_c = Rcr2(rest_bits, c);
586  }
587 
588  TTMATH_LOGC("UInt::Rcr", last_c)
589 
590  return last_c;
591  }
592 
593 
599  {
600  uint moving = 0;
601 
602  // a - index a last word which is different from zero
603  sint a;
604  for(a=value_size-1 ; a>=0 && table[a]==0 ; --a);
605 
606  if( a < 0 )
607  return moving; // all words in table have zero
608 
609  if( a != value_size-1 )
610  {
611  moving += ( value_size-1 - a ) * TTMATH_BITS_PER_UINT;
612 
613  // moving all words
614  sint i;
615  for(i=value_size-1 ; a>=0 ; --i, --a)
616  table[i] = table[a];
617 
618  // setting the rest word to zero
619  for(; i>=0 ; --i)
620  table[i] = 0;
621  }
622 
623  uint moving2 = FindLeadingBitInWord( table[value_size-1] );
624  // moving2 is different from -1 because the value table[value_size-1]
625  // is not zero
626 
627  moving2 = TTMATH_BITS_PER_UINT - moving2 - 1;
628  Rcl(moving2);
629 
630  TTMATH_LOG("UInt::CompensationToLeft")
631 
632  return moving + moving2;
633  }
634 
635 
649  bool FindLeadingBit(uint & table_id, uint & index) const
650  {
651  for(table_id=value_size-1 ; table_id!=0 && table[table_id]==0 ; --table_id);
652 
653  if( table_id==0 && table[table_id]==0 )
654  {
655  // is zero
656  index = 0;
657 
658  return false;
659  }
660 
661  // table[table_id] is different from 0
662  index = FindLeadingBitInWord( table[table_id] );
663 
664  return true;
665  }
666 
667 
681  bool FindLowestBit(uint & table_id, uint & index) const
682  {
683  for(table_id=0 ; table_id<value_size && table[table_id]==0 ; ++table_id);
684 
685  if( table_id >= value_size )
686  {
687  // is zero
688  index = 0;
689  table_id = 0;
690 
691  return false;
692  }
693 
694  // table[table_id] is different from 0
695  index = FindLowestBitInWord( table[table_id] );
696 
697  return true;
698  }
699 
700 
706  uint GetBit(uint bit_index) const
707  {
708  TTMATH_ASSERT( bit_index < value_size * TTMATH_BITS_PER_UINT )
709 
710  uint index = bit_index / TTMATH_BITS_PER_UINT;
711  uint bit = bit_index % TTMATH_BITS_PER_UINT;
712 
713  uint temp = table[index];
714  uint res = SetBitInWord(temp, bit);
715 
716  return res;
717  }
718 
719 
726  uint SetBit(uint bit_index)
727  {
728  TTMATH_ASSERT( bit_index < value_size * TTMATH_BITS_PER_UINT )
729 
730  uint index = bit_index / TTMATH_BITS_PER_UINT;
731  uint bit = bit_index % TTMATH_BITS_PER_UINT;
732  uint res = SetBitInWord(table[index], bit);
733 
734  TTMATH_LOG("UInt::SetBit")
735 
736  return res;
737  }
738 
739 
743  void BitAnd(const UInt<value_size> & ss2)
744  {
745  for(uint x=0 ; x<value_size ; ++x)
746  table[x] &= ss2.table[x];
747 
748  TTMATH_LOG("UInt::BitAnd")
749  }
750 
751 
755  void BitOr(const UInt<value_size> & ss2)
756  {
757  for(uint x=0 ; x<value_size ; ++x)
758  table[x] |= ss2.table[x];
759 
760  TTMATH_LOG("UInt::BitOr")
761  }
762 
763 
767  void BitXor(const UInt<value_size> & ss2)
768  {
769  for(uint x=0 ; x<value_size ; ++x)
770  table[x] ^= ss2.table[x];
771 
772  TTMATH_LOG("UInt::BitXor")
773  }
774 
775 
779  void BitNot()
780  {
781  for(uint x=0 ; x<value_size ; ++x)
782  table[x] = ~table[x];
783 
784  TTMATH_LOG("UInt::BitNot")
785  }
786 
787 
795  void BitNot2()
796  {
797  uint table_id, index;
798 
799  if( FindLeadingBit(table_id, index) )
800  {
801  for(uint x=0 ; x<table_id ; ++x)
802  table[x] = ~table[x];
803 
805  uint shift = TTMATH_BITS_PER_UINT - index - 1;
806 
807  if(shift)
808  mask >>= shift;
809 
810  table[table_id] ^= mask;
811  }
812  else
813  table[0] = 1;
814 
815 
816  TTMATH_LOG("UInt::BitNot2")
817  }
818 
819 
820 
828 public:
829 
836  {
837  uint r1, r2, x1;
838  uint c = 0;
839 
840  UInt<value_size> u(*this);
841  SetZero();
842 
843  if( ss2 == 0 )
844  {
845  TTMATH_LOGC("UInt::MulInt(uint)", 0)
846  return 0;
847  }
848 
849  for(x1=0 ; x1<value_size-1 ; ++x1)
850  {
851  MulTwoWords(u.table[x1], ss2, &r2, &r1);
852  c += AddTwoInts(r2,r1,x1);
853  }
854 
855  // x1 = value_size-1 (last word)
856  MulTwoWords(u.table[x1], ss2, &r2, &r1);
857  c += (r2!=0) ? 1 : 0;
858  c += AddInt(r1, x1);
859 
860  TTMATH_LOGC("UInt::MulInt(uint)", c)
861 
862  return (c==0)? 0 : 1;
863  }
864 
865 
872  template<uint result_size>
873  void MulInt(uint ss2, UInt<result_size> & result) const
874  {
875  TTMATH_ASSERT( result_size > value_size )
876 
877  uint r2,r1;
878  uint x1size=value_size;
879  uint x1start=0;
880 
881  result.SetZero();
882 
883  if( ss2 == 0 )
884  {
885  TTMATH_VECTOR_LOG("UInt::MulInt(uint, UInt<>)", result.table, result_size)
886  return;
887  }
888 
889  if( value_size > 2 )
890  {
891  // if the value_size is smaller than or equal to 2
892  // there is no sense to set x1size and x1start to another values
893 
894  for(x1size=value_size ; x1size>0 && table[x1size-1]==0 ; --x1size);
895 
896  if( x1size == 0 )
897  {
898  TTMATH_VECTOR_LOG("UInt::MulInt(uint, UInt<>)", result.table, result_size)
899  return;
900  }
901 
902  for(x1start=0 ; x1start<x1size && table[x1start]==0 ; ++x1start);
903  }
904 
905  for(uint x1=x1start ; x1<x1size ; ++x1)
906  {
907  MulTwoWords(table[x1], ss2, &r2, &r1 );
908  result.AddTwoInts(r2,r1,x1);
909  }
910 
911  TTMATH_VECTOR_LOG("UInt::MulInt(uint, UInt<>)", result.table, result_size)
912 
913  return;
914  }
915 
916 
917 
923  uint Mul(const UInt<value_size> & ss2, uint algorithm = 100)
924  {
925  switch( algorithm )
926  {
927  case 1:
928  return Mul1(ss2);
929 
930  case 2:
931  return Mul2(ss2);
932 
933  case 3:
934  return Mul3(ss2);
935 
936  case 100:
937  default:
938  return MulFastest(ss2);
939  }
940  }
941 
942 
951  void MulBig(const UInt<value_size> & ss2,
952  UInt<value_size*2> & result,
953  uint algorithm = 100)
954  {
955  switch( algorithm )
956  {
957  case 1:
958  Mul1Big(ss2, result);
959  break;
960 
961  case 2:
962  Mul2Big(ss2, result);
963  break;
964 
965  case 3:
966  Mul3Big(ss2, result);
967  break;
968 
969  case 100:
970  default:
971  MulFastestBig(ss2, result);
972  }
973  }
974 
975 
976 
981 private:
982 
988  uint Mul1Ref(const UInt<value_size> & ss2)
989  {
991 
992  UInt<value_size> ss1( *this );
993  SetZero();
994 
995  for(uint i=0; i < value_size*TTMATH_BITS_PER_UINT ; ++i)
996  {
997  if( Add(*this) )
998  {
999  TTMATH_LOGC("UInt::Mul1", 1)
1000  return 1;
1001  }
1002 
1003  if( ss1.Rcl(1) )
1004  if( Add(ss2) )
1005  {
1006  TTMATH_LOGC("UInt::Mul1", 1)
1007  return 1;
1008  }
1009  }
1010 
1011  TTMATH_LOGC("UInt::Mul1", 0)
1012 
1013  return 0;
1014  }
1015 
1016 
1017 public:
1018 
1023  uint Mul1(const UInt<value_size> & ss2)
1024  {
1025  if( this == &ss2 )
1026  {
1027  UInt<value_size> copy_ss2(ss2);
1028  return Mul1Ref(copy_ss2);
1029  }
1030  else
1031  {
1032  return Mul1Ref(ss2);
1033  }
1034  }
1035 
1036 
1043  void Mul1Big(const UInt<value_size> & ss2_, UInt<value_size*2> & result)
1044  {
1045  UInt<value_size*2> ss2;
1046  uint i;
1047 
1048  // copying *this into result and ss2_ into ss2
1049  for(i=0 ; i<value_size ; ++i)
1050  {
1051  result.table[i] = table[i];
1052  ss2.table[i] = ss2_.table[i];
1053  }
1054 
1055  // cleaning the highest bytes in result and ss2
1056  for( ; i < value_size*2 ; ++i)
1057  {
1058  result.table[i] = 0;
1059  ss2.table[i] = 0;
1060  }
1061 
1062  // multiply
1063  // (there will not be a carry)
1064  result.Mul1( ss2 );
1065 
1066  TTMATH_LOG("UInt::Mul1Big")
1067  }
1068 
1069 
1070 
1083  {
1084  UInt<value_size*2> result;
1085  uint i, c = 0;
1086 
1087  Mul2Big(ss2, result);
1088 
1089  // copying result
1090  for(i=0 ; i<value_size ; ++i)
1091  table[i] = result.table[i];
1092 
1093  // testing carry
1094  for( ; i<value_size*2 ; ++i)
1095  if( result.table[i] != 0 )
1096  {
1097  c = 1;
1098  break;
1099  }
1100 
1101  TTMATH_LOGC("UInt::Mul2", c)
1102 
1103  return c;
1104  }
1105 
1106 
1113  void Mul2Big(const UInt<value_size> & ss2, UInt<value_size*2> & result)
1114  {
1115  Mul2Big2<value_size>(table, ss2.table, result);
1116 
1117  TTMATH_LOG("UInt::Mul2Big")
1118  }
1119 
1120 
1121 private:
1122 
1130  template<uint ss_size>
1131  void Mul2Big2(const uint * ss1, const uint * ss2, UInt<ss_size*2> & result)
1132  {
1133  uint x1size = ss_size, x2size = ss_size;
1134  uint x1start = 0, x2start = 0;
1135 
1136  if( ss_size > 2 )
1137  {
1138  // if the ss_size is smaller than or equal to 2
1139  // there is no sense to set x1size (and others) to another values
1140 
1141  for(x1size=ss_size ; x1size>0 && ss1[x1size-1]==0 ; --x1size);
1142  for(x2size=ss_size ; x2size>0 && ss2[x2size-1]==0 ; --x2size);
1143 
1144  for(x1start=0 ; x1start<x1size && ss1[x1start]==0 ; ++x1start);
1145  for(x2start=0 ; x2start<x2size && ss2[x2start]==0 ; ++x2start);
1146  }
1147 
1148  Mul2Big3<ss_size>(ss1, ss2, result, x1start, x1size, x2start, x2size);
1149  }
1150 
1151 
1152 
1156  template<uint ss_size>
1157  void Mul2Big3(const uint * ss1, const uint * ss2, UInt<ss_size*2> & result, uint x1start, uint x1size, uint x2start, uint x2size)
1158  {
1159  uint r2, r1;
1160 
1161  result.SetZero();
1162 
1163  if( x1size==0 || x2size==0 )
1164  return;
1165 
1166  for(uint x1=x1start ; x1<x1size ; ++x1)
1167  {
1168  for(uint x2=x2start ; x2<x2size ; ++x2)
1169  {
1170  MulTwoWords(ss1[x1], ss2[x2], &r2, &r1);
1171  result.AddTwoInts(r2, r1, x2+x1);
1172  // here will never be a carry
1173  }
1174  }
1175  }
1176 
1177 
1178 public:
1179 
1180 
1213  {
1214  UInt<value_size*2> result;
1215  uint i, c = 0;
1216 
1217  Mul3Big(ss2, result);
1218 
1219  // copying result
1220  for(i=0 ; i<value_size ; ++i)
1221  table[i] = result.table[i];
1222 
1223  // testing carry
1224  for( ; i<value_size*2 ; ++i)
1225  if( result.table[i] != 0 )
1226  {
1227  c = 1;
1228  break;
1229  }
1230 
1231  TTMATH_LOGC("UInt::Mul3", c)
1232 
1233  return c;
1234  }
1235 
1236 
1237 
1245  void Mul3Big(const UInt<value_size> & ss2, UInt<value_size*2> & result)
1246  {
1247  Mul3Big2<value_size>(table, ss2.table, result.table);
1248 
1249  TTMATH_LOG("UInt::Mul3Big")
1250  }
1251 
1252 
1253 
1254 private:
1255 
1261  template<uint ss_size>
1262  void Mul3Big2(const uint * ss1, const uint * ss2, uint * result)
1263  {
1264  const uint * x1, * x0, * y1, * y0;
1265 
1266 
1267  if( ss_size>1 && ss_size<TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE )
1268  {
1269  UInt<ss_size*2> res;
1270  Mul2Big2<ss_size>(ss1, ss2, res);
1271 
1272 #ifdef __clang__
1273 #pragma clang diagnostic push
1274 #pragma clang diagnostic ignored "-Wtautological-compare"
1275 #endif
1276 
1277  for(uint i=0 ; i<ss_size*2 ; ++i)
1278  result[i] = res.table[i];
1279 
1280 #ifdef __clang__
1281 #pragma clang diagnostic pop
1282 #endif
1283 
1284  return;
1285  }
1286  else
1287  if( ss_size == 1 )
1288  {
1289  return MulTwoWords(*ss1, *ss2, &result[1], &result[0]);
1290  }
1291 
1292 
1293  if( (ss_size & 1) == 1 )
1294  {
1295  // ss_size is odd
1296  x0 = ss1;
1297  y0 = ss2;
1298  x1 = ss1 + ss_size / 2 + 1;
1299  y1 = ss2 + ss_size / 2 + 1;
1300 
1301  // the second vectors (x1 and y1) are smaller about one from the first ones (x0 and y0)
1302  Mul3Big3<ss_size/2 + 1, ss_size/2, ss_size*2>(x1, x0, y1, y0, result);
1303  }
1304  else
1305  {
1306  // ss_size is even
1307  x0 = ss1;
1308  y0 = ss2;
1309  x1 = ss1 + ss_size / 2;
1310  y1 = ss2 + ss_size / 2;
1311 
1312  // all four vectors (x0 x1 y0 y1) are equal in size
1313  Mul3Big3<ss_size/2, ss_size/2, ss_size*2>(x1, x0, y1, y0, result);
1314  }
1315  }
1316 
1317 
1318 
1319 #ifdef _MSC_VER
1320 #pragma warning (disable : 4717)
1321 //warning C4717: recursive on all control paths, function will cause runtime stack overflow
1322 //we have the stop point in Mul3Big2() method
1323 #endif
1324 
1325 #if defined(__GNUC__) && !defined(__clang__)
1326 #pragma GCC diagnostic push
1327 #pragma GCC diagnostic ignored "-Wunused-but-set-variable"
1328 #endif
1329 
1330 
1346  template<uint first_size, uint second_size, uint result_size>
1347  void Mul3Big3(const uint * x1, const uint * x0, const uint * y1, const uint * y0, uint * result)
1348  {
1349  uint i, c, xc, yc;
1350 
1351  UInt<first_size> temp, temp2;
1352  UInt<first_size*3> z1;
1353 
1354  // z0 and z2 we store directly in the result (we don't use any temporary variables)
1355  Mul3Big2<first_size>(x0, y0, result); // z0
1356  Mul3Big2<second_size>(x1, y1, result+first_size*2); // z2
1357 
1358  // now we calculate z1
1359  // temp = (x0 + x1)
1360  // temp2 = (y0 + y1)
1361  // we're using temp and temp2 with UInt<first_size>, although there can be a carry but
1362  // we simple remember it in xc and yc (xc and yc can be either 0 or 1),
1363  // and (x0 + x1)*(y0 + y1) we calculate in this way (schoolbook algorithm):
1364  //
1365  // xc | temp
1366  // yc | temp2
1367  // --------------------
1368  // (temp * temp2)
1369  // xc*temp2 |
1370  // yc*temp |
1371  // xc*yc |
1372  // ---------- z1 --------
1373  //
1374  // and the result is never larger in size than 3*first_size
1375 
1376  xc = AddVector(x0, x1, first_size, second_size, temp.table);
1377  yc = AddVector(y0, y1, first_size, second_size, temp2.table);
1378 
1379  Mul3Big2<first_size>(temp.table, temp2.table, z1.table);
1380 
1381 #ifdef __clang__
1382 #pragma clang diagnostic push
1383 #pragma clang diagnostic ignored "-Wtautological-compare"
1384 #endif
1385 
1386  // clearing the rest of z1
1387  for(i=first_size*2 ; i<first_size*3 ; ++i)
1388  z1.table[i] = 0;
1389 
1390 #ifdef __clang__
1391 #pragma clang diagnostic pop
1392 #endif
1393 
1394  if( xc )
1395  {
1396  c = AddVector(z1.table+first_size, temp2.table, first_size*3-first_size, first_size, z1.table+first_size);
1397  TTMATH_ASSERT( c==0 )
1398  }
1399 
1400  if( yc )
1401  {
1402  c = AddVector(z1.table+first_size, temp.table, first_size*3-first_size, first_size, z1.table+first_size);
1403  TTMATH_ASSERT( c==0 )
1404  }
1405 
1406 
1407  if( xc && yc )
1408  {
1409 #ifdef __clang__
1410 #pragma clang diagnostic push
1411 #pragma clang diagnostic ignored "-Wtautological-compare"
1412 #endif
1413 
1414  for( i=first_size*2 ; i<first_size*3 ; ++i )
1415  if( ++z1.table[i] != 0 )
1416  break; // break if there was no carry
1417 
1418 #ifdef __clang__
1419 #pragma clang diagnostic pop
1420 #endif
1421  }
1422 
1423  // z1 = z1 - z2
1424  c = SubVector(z1.table, result+first_size*2, first_size*3, second_size*2, z1.table);
1425  TTMATH_ASSERT(c==0)
1426 
1427  // z1 = z1 - z0
1428  c = SubVector(z1.table, result, first_size*3, first_size*2, z1.table);
1429  TTMATH_ASSERT(c==0)
1430 
1431  // here we've calculated the z1
1432  // now we're adding it to the result
1433 
1434  if( first_size > second_size )
1435  {
1436  uint z1_size = result_size - first_size;
1437  TTMATH_ASSERT( z1_size <= first_size*3 )
1438 
1439 #ifdef __clang__
1440 #pragma clang diagnostic push
1441 #pragma clang diagnostic ignored "-Wtautological-compare"
1442 #endif
1443 
1444  for(i=z1_size ; i<first_size*3 ; ++i)
1445  {
1446  TTMATH_ASSERT( z1.table[i] == 0 )
1447  }
1448 
1449 #ifdef __clang__
1450 #pragma clang diagnostic pop
1451 #endif
1452 
1453  c = AddVector(result+first_size, z1.table, result_size-first_size, z1_size, result+first_size);
1454  TTMATH_ASSERT(c==0)
1455  }
1456  else
1457  {
1458  c = AddVector(result+first_size, z1.table, result_size-first_size, first_size*3, result+first_size);
1459  TTMATH_ASSERT(c==0)
1460  }
1461  }
1462 
1463 
1464 #if defined(__GNUC__) && !defined(__clang__)
1465 #pragma GCC diagnostic pop
1466 #endif
1467 
1468 #ifdef _MSC_VER
1469 #pragma warning (default : 4717)
1470 #endif
1471 
1472 
1473 public:
1474 
1475 
1480  {
1481  UInt<value_size*2> result;
1482  uint i, c = 0;
1483 
1484  MulFastestBig(ss2, result);
1485 
1486  // copying result
1487  for(i=0 ; i<value_size ; ++i)
1488  table[i] = result.table[i];
1489 
1490  // testing carry
1491  for( ; i<value_size*2 ; ++i)
1492  if( result.table[i] != 0 )
1493  {
1494  c = 1;
1495  break;
1496  }
1497 
1498  TTMATH_LOGC("UInt::MulFastest", c)
1499 
1500  return c;
1501  }
1502 
1503 
1511  {
1513  {
1514  Mul2Big(ss2, result);
1515  return;
1516  }
1517 
1518  uint x1size = value_size, x2size = value_size;
1519  uint x1start = 0, x2start = 0;
1520 
1521  for(x1size=value_size ; x1size>0 && table[x1size-1]==0 ; --x1size);
1522  for(x2size=value_size ; x2size>0 && ss2.table[x2size-1]==0 ; --x2size);
1523 
1524  if( x1size==0 || x2size==0 )
1525  {
1526  // either 'this' or 'ss2' is equal zero - the result is zero too
1527  result.SetZero();
1528  return;
1529  }
1530 
1531  for(x1start=0 ; x1start<x1size && table[x1start]==0 ; ++x1start);
1532  for(x2start=0 ; x2start<x2size && ss2.table[x2start]==0 ; ++x2start);
1533 
1534  uint distancex1 = x1size - x1start;
1535  uint distancex2 = x2size - x2start;
1536 
1537  if( distancex1 < 3 || distancex2 < 3 )
1538  {
1539  // either 'this' or 'ss2' have only 2 (or 1) items different from zero (side by side)
1540  // (this condition in the future can be improved)
1541  Mul2Big3<value_size>(table, ss2.table, result, x1start, x1size, x2start, x2size);
1542  return;
1543  }
1544 
1545 
1546  // Karatsuba multiplication
1547  Mul3Big(ss2, result);
1548 
1549  TTMATH_LOG("UInt::MulFastestBig")
1550  }
1551 
1552 
1560 public:
1561 
1562 
1568  uint DivInt(uint divisor, uint * remainder = 0)
1569  {
1570  if( divisor == 0 )
1571  {
1572  if( remainder )
1573  *remainder = 0; // this is for convenience, without it the compiler can report that 'remainder' is uninitialized
1574 
1575  TTMATH_LOG("UInt::DivInt")
1576 
1577  return 1;
1578  }
1579 
1580  if( divisor == 1 )
1581  {
1582  if( remainder )
1583  *remainder = 0;
1584 
1585  TTMATH_LOG("UInt::DivInt")
1586 
1587  return 0;
1588  }
1589 
1590  UInt<value_size> dividend(*this);
1591  SetZero();
1592 
1593  sint i; // i must be with a sign
1594  uint r = 0;
1595 
1596  // we're looking for the last word in ss1
1597  for(i=value_size-1 ; i>0 && dividend.table[i]==0 ; --i);
1598 
1599  for( ; i>=0 ; --i)
1600  DivTwoWords(r, dividend.table[i], divisor, &table[i], &r);
1601 
1602  if( remainder )
1603  *remainder = r;
1604 
1605  TTMATH_LOG("UInt::DivInt")
1606 
1607  return 0;
1608  }
1609 
1610  uint DivInt(uint divisor, uint & remainder)
1611  {
1612  return DivInt(divisor, &remainder);
1613  }
1614 
1615 
1616 
1626  uint Div( const UInt<value_size> & divisor,
1627  UInt<value_size> * remainder = 0,
1628  uint algorithm = 3)
1629  {
1630  switch( algorithm )
1631  {
1632  case 1:
1633  return Div1(divisor, remainder);
1634 
1635  case 2:
1636  return Div2(divisor, remainder);
1637 
1638  case 3:
1639  default:
1640  return Div3(divisor, remainder);
1641  }
1642  }
1643 
1644  uint Div(const UInt<value_size> & divisor, UInt<value_size> & remainder, uint algorithm = 3)
1645  {
1646  return Div(divisor, &remainder, algorithm);
1647  }
1648 
1649 
1650 
1651 private:
1652 
1659  uint Div_StandardTest( const UInt<value_size> & v,
1660  uint & m, uint & n,
1661  UInt<value_size> * remainder = 0)
1662  {
1663  switch( Div_CalculatingSize(v, m, n) )
1664  {
1665  case 4: // 'this' is equal v
1666  if( remainder )
1667  remainder->SetZero();
1668 
1669  SetOne();
1670  TTMATH_LOG("UInt::Div_StandardTest")
1671  return 0;
1672 
1673  case 3: // 'this' is smaller than v
1674  if( remainder )
1675  *remainder = *this;
1676 
1677  SetZero();
1678  TTMATH_LOG("UInt::Div_StandardTest")
1679  return 0;
1680 
1681  case 2: // 'this' is zero
1682  if( remainder )
1683  remainder->SetZero();
1684 
1685  SetZero();
1686  TTMATH_LOG("UInt::Div_StandardTest")
1687  return 0;
1688 
1689  case 1: // v is zero
1690  TTMATH_LOG("UInt::Div_StandardTest")
1691  return 1;
1692  }
1693 
1694  TTMATH_LOG("UInt::Div_StandardTest")
1695 
1696  return 2;
1697  }
1698 
1699 
1700 
1713  uint Div_CalculatingSize(const UInt<value_size> & v, uint & m, uint & n)
1714  {
1715  m = n = value_size-1;
1716 
1717  for( ; n!=0 && v.table[n]==0 ; --n);
1718 
1719  if( n==0 && v.table[n]==0 )
1720  return 1;
1721 
1722  for( ; m!=0 && table[m]==0 ; --m);
1723 
1724  if( m==0 && table[m]==0 )
1725  return 2;
1726 
1727  if( m < n )
1728  return 3;
1729  else
1730  if( m == n )
1731  {
1732  uint i;
1733  for(i = n ; i!=0 && table[i]==v.table[i] ; --i);
1734 
1735  if( table[i] < v.table[i] )
1736  return 3;
1737  else
1738  if (table[i] == v.table[i] )
1739  return 4;
1740  }
1741 
1742  return 0;
1743  }
1744 
1745 
1746 public:
1747 
1752  uint Div1(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0)
1753  {
1754  uint m,n, test;
1755 
1756  test = Div_StandardTest(divisor, m, n, remainder);
1757  if( test < 2 )
1758  return test;
1759 
1760  if( !remainder )
1761  {
1762  UInt<value_size> rem;
1763 
1764  return Div1_Calculate(divisor, rem);
1765  }
1766 
1767  return Div1_Calculate(divisor, *remainder);
1768  }
1769 
1770 
1775  uint Div1(const UInt<value_size> & divisor, UInt<value_size> & remainder)
1776  {
1777  return Div1(divisor, &remainder);
1778  }
1779 
1780 
1781 private:
1782 
1783  uint Div1_Calculate(const UInt<value_size> & divisor, UInt<value_size> & rest)
1784  {
1785  if( this == &divisor )
1786  {
1787  UInt<value_size> divisor_copy(divisor);
1788  return Div1_CalculateRef(divisor_copy, rest);
1789  }
1790  else
1791  {
1792  return Div1_CalculateRef(divisor, rest);
1793  }
1794  }
1795 
1796 
1797  uint Div1_CalculateRef(const UInt<value_size> & divisor, UInt<value_size> & rest)
1798  {
1799  TTMATH_REFERENCE_ASSERT( divisor )
1800 
1801  sint loop;
1802  sint c;
1803 
1804  rest.SetZero();
1805  loop = value_size * TTMATH_BITS_PER_UINT;
1806  c = 0;
1807 
1808 
1809  div_a:
1810  c = Rcl(1, c);
1811  c = rest.Add(rest,c);
1812  c = rest.Sub(divisor,c);
1813 
1814  c = !c;
1815 
1816  if(!c)
1817  goto div_d;
1818 
1819 
1820  div_b:
1821  --loop;
1822  if(loop)
1823  goto div_a;
1824 
1825  c = Rcl(1, c);
1826  TTMATH_LOG("UInt::Div1_Calculate")
1827  return 0;
1828 
1829 
1830  div_c:
1831  c = Rcl(1, c);
1832  c = rest.Add(rest,c);
1833  c = rest.Add(divisor);
1834 
1835  if(c)
1836  goto div_b;
1837 
1838 
1839  div_d:
1840  --loop;
1841  if(loop)
1842  goto div_c;
1843 
1844  c = Rcl(1, c);
1845  c = rest.Add(divisor);
1846 
1847  TTMATH_LOG("UInt::Div1_Calculate")
1848 
1849  return 0;
1850  }
1851 
1852 
1853 public:
1854 
1862  uint Div2(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0)
1863  {
1864  if( this == &divisor )
1865  {
1866  UInt<value_size> divisor_copy(divisor);
1867  return Div2Ref(divisor_copy, remainder);
1868  }
1869  else
1870  {
1871  return Div2Ref(divisor, remainder);
1872  }
1873  }
1874 
1875 
1883  uint Div2(const UInt<value_size> & divisor, UInt<value_size> & remainder)
1884  {
1885  return Div2(divisor, &remainder);
1886  }
1887 
1888 
1889 private:
1890 
1898  uint Div2Ref(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0)
1899  {
1900  uint bits_diff;
1901  uint status = Div2_Calculate(divisor, remainder, bits_diff);
1902  if( status < 2 )
1903  return status;
1904 
1905  if( CmpBiggerEqual(divisor) )
1906  {
1907  Div2(divisor, remainder);
1908  SetBit(bits_diff);
1909  }
1910  else
1911  {
1912  if( remainder )
1913  *remainder = *this;
1914 
1915  SetZero();
1916  SetBit(bits_diff);
1917  }
1918 
1919  TTMATH_LOG("UInt::Div2")
1920 
1921  return 0;
1922  }
1923 
1924 
1932  uint Div2_Calculate(const UInt<value_size> & divisor, UInt<value_size> * remainder,
1933  uint & bits_diff)
1934  {
1935  uint table_id, index;
1936  uint divisor_table_id, divisor_index;
1937 
1938  uint status = Div2_FindLeadingBitsAndCheck( divisor, remainder,
1939  table_id, index,
1940  divisor_table_id, divisor_index);
1941 
1942  if( status < 2 )
1943  {
1944  TTMATH_LOG("UInt::Div2_Calculate")
1945  return status;
1946  }
1947 
1948  // here we know that 'this' is greater than divisor
1949  // then 'index' is greater or equal 'divisor_index'
1950  bits_diff = index - divisor_index;
1951 
1952  UInt<value_size> divisor_copy(divisor);
1953  divisor_copy.Rcl(bits_diff, 0);
1954 
1955  if( CmpSmaller(divisor_copy, table_id) )
1956  {
1957  divisor_copy.Rcr(1);
1958  --bits_diff;
1959  }
1960 
1961  Sub(divisor_copy, 0);
1962 
1963  TTMATH_LOG("UInt::Div2_Calculate")
1964 
1965  return 2;
1966  }
1967 
1968 
1975  uint Div2_FindLeadingBitsAndCheck( const UInt<value_size> & divisor,
1976  UInt<value_size> * remainder,
1977  uint & table_id, uint & index,
1978  uint & divisor_table_id, uint & divisor_index)
1979  {
1980  if( !divisor.FindLeadingBit(divisor_table_id, divisor_index) )
1981  {
1982  // division by zero
1983  TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
1984  return 1;
1985  }
1986 
1987  if( !FindLeadingBit(table_id, index) )
1988  {
1989  // zero is divided by something
1990 
1991  SetZero();
1992 
1993  if( remainder )
1994  remainder->SetZero();
1995 
1996  TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
1997 
1998  return 0;
1999  }
2000 
2001  divisor_index += divisor_table_id * TTMATH_BITS_PER_UINT;
2002  index += table_id * TTMATH_BITS_PER_UINT;
2003 
2004  if( divisor_table_id == 0 )
2005  {
2006  // dividor has only one 32-bit word
2007 
2008  uint r;
2009  DivInt(divisor.table[0], &r);
2010 
2011  if( remainder )
2012  {
2013  remainder->SetZero();
2014  remainder->table[0] = r;
2015  }
2016 
2017  TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
2018 
2019  return 0;
2020  }
2021 
2022 
2023  if( Div2_DivisorGreaterOrEqual( divisor, remainder,
2024  table_id, index,
2025  divisor_index) )
2026  {
2027  TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
2028  return 0;
2029  }
2030 
2031 
2032  TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
2033 
2034  return 2;
2035  }
2036 
2037 
2042  bool Div2_DivisorGreaterOrEqual( const UInt<value_size> & divisor,
2043  UInt<value_size> * remainder,
2044  uint table_id, uint index,
2045  uint divisor_index )
2046  {
2047  if( divisor_index > index )
2048  {
2049  // divisor is greater than this
2050 
2051  if( remainder )
2052  *remainder = *this;
2053 
2054  SetZero();
2055 
2056  TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
2057 
2058  return true;
2059  }
2060 
2061  if( divisor_index == index )
2062  {
2063  // table_id == divisor_table_id as well
2064 
2065  uint i;
2066  for(i = table_id ; i!=0 && table[i]==divisor.table[i] ; --i);
2067 
2068  if( table[i] < divisor.table[i] )
2069  {
2070  // divisor is greater than 'this'
2071 
2072  if( remainder )
2073  *remainder = *this;
2074 
2075  SetZero();
2076 
2077  TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
2078 
2079  return true;
2080  }
2081  else
2082  if( table[i] == divisor.table[i] )
2083  {
2084  // divisor is equal 'this'
2085 
2086  if( remainder )
2087  remainder->SetZero();
2088 
2089  SetOne();
2090 
2091  TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
2092 
2093  return true;
2094  }
2095  }
2096 
2097  TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
2098 
2099  return false;
2100  }
2101 
2102 
2103 public:
2104 
2108  uint Div3(const UInt<value_size> & ss2, UInt<value_size> * remainder = 0)
2109  {
2110  if( this == &ss2 )
2111  {
2112  UInt<value_size> copy_ss2(ss2);
2113  return Div3Ref(copy_ss2, remainder);
2114  }
2115  else
2116  {
2117  return Div3Ref(ss2, remainder);
2118  }
2119  }
2120 
2121 
2125  uint Div3(const UInt<value_size> & ss2, UInt<value_size> & remainder)
2126  {
2127  return Div3(ss2, &remainder);
2128  }
2129 
2130 
2131 private:
2132 
2141  uint Div3Ref(const UInt<value_size> & v, UInt<value_size> * remainder = 0)
2142  {
2143  uint m,n, test;
2144 
2145  test = Div_StandardTest(v, m, n, remainder);
2146  if( test < 2 )
2147  return test;
2148 
2149  if( n == 0 )
2150  {
2151  uint r;
2152  DivInt( v.table[0], &r );
2153 
2154  if( remainder )
2155  {
2156  remainder->SetZero();
2157  remainder->table[0] = r;
2158  }
2159 
2160  TTMATH_LOG("UInt::Div3")
2161 
2162  return 0;
2163  }
2164 
2165 
2166  // we can only use the third division algorithm when
2167  // the divisor is greater or equal 2^32 (has more than one 32-bit word)
2168  ++m;
2169  ++n;
2170  m = m - n;
2171  Div3_Division(v, remainder, m, n);
2172 
2173  TTMATH_LOG("UInt::Div3")
2174 
2175  return 0;
2176  }
2177 
2178 
2179 
2180 private:
2181 
2182 
2183  void Div3_Division(UInt<value_size> v, UInt<value_size> * remainder, uint m, uint n)
2184  {
2185  TTMATH_ASSERT( n>=2 )
2186 
2187  UInt<value_size+1> uu, vv;
2188  UInt<value_size> q;
2189  uint d, u_value_size, u0, u1, u2, v1, v0, j=m;
2190 
2191  u_value_size = Div3_Normalize(v, n, d);
2192 
2193  if( j+n == value_size )
2194  u2 = u_value_size;
2195  else
2196  u2 = table[j+n];
2197 
2198  Div3_MakeBiggerV(v, vv);
2199 
2200  for(uint i = j+1 ; i<value_size ; ++i)
2201  q.table[i] = 0;
2202 
2203  while( true )
2204  {
2205  u1 = table[j+n-1];
2206  u0 = table[j+n-2];
2207  v1 = v.table[n-1];
2208  v0 = v.table[n-2];
2209 
2210  uint qp = Div3_Calculate(u2,u1,u0, v1,v0);
2211 
2212  Div3_MakeNewU(uu, j, n, u2);
2213  Div3_MultiplySubtract(uu, vv, qp);
2214  Div3_CopyNewU(uu, j, n);
2215 
2216  q.table[j] = qp;
2217 
2218  // the next loop
2219  if( j-- == 0 )
2220  break;
2221 
2222  u2 = table[j+n];
2223  }
2224 
2225  if( remainder )
2226  Div3_Unnormalize(remainder, n, d);
2227 
2228  *this = q;
2229 
2230  TTMATH_LOG("UInt::Div3_Division")
2231  }
2232 
2233 
2234  void Div3_MakeNewU(UInt<value_size+1> & uu, uint j, uint n, uint u_max)
2235  {
2236  uint i;
2237 
2238  for(i=0 ; i<n ; ++i, ++j)
2239  uu.table[i] = table[j];
2240 
2241  // 'n' is from <1..value_size> so and 'i' is from <0..value_size>
2242  // then table[i] is always correct (look at the declaration of 'uu')
2243  uu.table[i] = u_max;
2244 
2245  for( ++i ; i<value_size+1 ; ++i)
2246  uu.table[i] = 0;
2247 
2248  TTMATH_LOG("UInt::Div3_MakeNewU")
2249  }
2250 
2251 
2252  void Div3_CopyNewU(const UInt<value_size+1> & uu, uint j, uint n)
2253  {
2254  uint i;
2255 
2256  for(i=0 ; i<n ; ++i)
2257  table[i+j] = uu.table[i];
2258 
2259  if( i+j < value_size )
2260  table[i+j] = uu.table[i];
2261 
2262  TTMATH_LOG("UInt::Div3_CopyNewU")
2263  }
2264 
2265 
2270  void Div3_MakeBiggerV(const UInt<value_size> & v, UInt<value_size+1> & vv)
2271  {
2272  for(uint i=0 ; i<value_size ; ++i)
2273  vv.table[i] = v.table[i];
2274 
2275  vv.table[value_size] = 0;
2276 
2277  TTMATH_LOG("UInt::Div3_MakeBiggerV")
2278  }
2279 
2280 
2290  uint Div3_Normalize(UInt<value_size> & v, uint n, uint & d)
2291  {
2292  // v.table[n-1] is != 0
2293 
2294  uint bit = (uint)FindLeadingBitInWord(v.table[n-1]);
2295  uint move = (TTMATH_BITS_PER_UINT - bit - 1);
2296  uint res = table[value_size-1];
2297  d = move;
2298 
2299  if( move > 0 )
2300  {
2301  v.Rcl(move, 0);
2302  Rcl(move, 0);
2303  res = res >> (bit + 1);
2304  }
2305  else
2306  {
2307  res = 0;
2308  }
2309 
2310  TTMATH_LOG("UInt::Div3_Normalize")
2311 
2312  return res;
2313  }
2314 
2315 
2316  void Div3_Unnormalize(UInt<value_size> * remainder, uint n, uint d)
2317  {
2318  for(uint i=n ; i<value_size ; ++i)
2319  table[i] = 0;
2320 
2321  Rcr(d,0);
2322 
2323  *remainder = *this;
2324 
2325  TTMATH_LOG("UInt::Div3_Unnormalize")
2326  }
2327 
2328 
2329  uint Div3_Calculate(uint u2, uint u1, uint u0, uint v1, uint v0)
2330  {
2331  UInt<2> u_temp;
2332  uint rp;
2333  bool next_test;
2334 
2335  TTMATH_ASSERT( v1 != 0 )
2336 
2337  u_temp.table[1] = u2;
2338  u_temp.table[0] = u1;
2339  u_temp.DivInt(v1, &rp);
2340 
2341  TTMATH_ASSERT( u_temp.table[1]==0 || u_temp.table[1]==1 )
2342 
2343  do
2344  {
2345  bool decrease = false;
2346 
2347  if( u_temp.table[1] == 1 )
2348  decrease = true;
2349  else
2350  {
2351  UInt<2> temp1, temp2;
2352 
2353  UInt<2>::MulTwoWords(u_temp.table[0], v0, temp1.table+1, temp1.table);
2354  temp2.table[1] = rp;
2355  temp2.table[0] = u0;
2356 
2357  if( temp1 > temp2 )
2358  decrease = true;
2359  }
2360 
2361  next_test = false;
2362 
2363  if( decrease )
2364  {
2365  u_temp.SubOne();
2366 
2367  rp += v1;
2368 
2369  if( rp >= v1 ) // it means that there wasn't a carry (r<b from the book)
2370  next_test = true;
2371  }
2372  }
2373  while( next_test );
2374 
2375  TTMATH_LOG("UInt::Div3_Calculate")
2376 
2377  return u_temp.table[0];
2378  }
2379 
2380 
2381 
2382  void Div3_MultiplySubtract( UInt<value_size+1> & uu,
2383  const UInt<value_size+1> & vv, uint & qp)
2384  {
2385  // D4 (in the book)
2386 
2387  UInt<value_size+1> vv_temp(vv);
2388  vv_temp.MulInt(qp);
2389 
2390  if( uu.Sub(vv_temp) )
2391  {
2392  // there was a carry
2393 
2394  //
2395  // !!! this part of code was not tested
2396  //
2397 
2398  --qp;
2399  uu.Add(vv);
2400 
2401  // can be a carry from this additions but it should be ignored
2402  // because it cancels with the borrow from uu.Sub(vv_temp)
2403  }
2404 
2405  TTMATH_LOG("UInt::Div3_MultiplySubtract")
2406  }
2407 
2408 
2409 
2410 
2411 
2412 
2413 public:
2414 
2415 
2426  {
2427  if(pow.IsZero() && IsZero())
2428  // we don't define zero^zero
2429  return 2;
2430 
2431  UInt<value_size> start(*this);
2432  UInt<value_size> result;
2433  result.SetOne();
2434  uint c = 0;
2435 
2436  while( !c )
2437  {
2438  if( pow.table[0] & 1 )
2439  c += result.Mul(start);
2440 
2441  pow.Rcr2_one(0);
2442  if( pow.IsZero() )
2443  break;
2444 
2445  c += start.Mul(start);
2446  }
2447 
2448  *this = result;
2449 
2450  TTMATH_LOGC("UInt::Pow(UInt<>)", c)
2451 
2452  return (c==0)? 0 : 1;
2453  }
2454 
2455 
2461  void Sqrt()
2462  {
2463  UInt<value_size> bit, temp;
2464 
2465  if( IsZero() )
2466  return;
2467 
2468  UInt<value_size> value(*this);
2469 
2470  SetZero();
2471  bit.SetZero();
2472  bit.table[value_size-1] = (TTMATH_UINT_HIGHEST_BIT >> 1);
2473 
2474  while( bit > value )
2475  bit.Rcr(2);
2476 
2477  while( !bit.IsZero() )
2478  {
2479  temp = *this;
2480  temp.Add(bit);
2481 
2482  if( value >= temp )
2483  {
2484  value.Sub(temp);
2485  Rcr(1);
2486  Add(bit);
2487  }
2488  else
2489  {
2490  Rcr(1);
2491  }
2492 
2493  bit.Rcr(2);
2494  }
2495 
2496  TTMATH_LOG("UInt::Sqrt")
2497  }
2498 
2499 
2500 
2501 
2509  {
2510  if( n >= value_size*TTMATH_BITS_PER_UINT )
2511  {
2512  SetZero();
2513  TTMATH_LOG("UInt::ClearFirstBits")
2514  return;
2515  }
2516 
2517  uint * p = table;
2518 
2519  // first we're clearing the whole words
2520  while( n >= TTMATH_BITS_PER_UINT )
2521  {
2522  *p++ = 0;
2523  n -= TTMATH_BITS_PER_UINT;
2524  }
2525 
2526  if( n == 0 )
2527  {
2528  TTMATH_LOG("UInt::ClearFirstBits")
2529  return;
2530  }
2531 
2532  // and then we're clearing one word which has left
2533  // mask -- all bits are set to one
2534  uint mask = TTMATH_UINT_MAX_VALUE;
2535 
2536  mask = mask << n;
2537 
2538  (*p) &= mask;
2539 
2540  TTMATH_LOG("UInt::ClearFirstBits")
2541  }
2542 
2543 
2547  bool IsTheHighestBitSet() const
2548  {
2549  return (table[value_size-1] & TTMATH_UINT_HIGHEST_BIT) != 0;
2550  }
2551 
2552 
2556  bool IsTheLowestBitSet() const
2557  {
2558  return (*table & 1) != 0;
2559  }
2560 
2561 
2566  {
2567 #ifdef __clang__
2568 #pragma clang diagnostic push
2569 #pragma clang diagnostic ignored "-Wtautological-compare"
2570 #endif
2571 
2572  for(uint i=0 ; i<value_size-1 ; ++i)
2573  if( table[i] != 0 )
2574  return false;
2575 
2576 #ifdef __clang__
2577 #pragma clang diagnostic pop
2578 #endif
2579  if( table[value_size-1] != TTMATH_UINT_HIGHEST_BIT )
2580  return false;
2581 
2582  return true;
2583  }
2584 
2585 
2590  {
2591  if( table[0] != 1 )
2592  return false;
2593 
2594  for(uint i=1 ; i<value_size ; ++i)
2595  if( table[i] != 0 )
2596  return false;
2597 
2598  return true;
2599  }
2600 
2601 
2605  bool IsZero() const
2606  {
2607  for(uint i=0 ; i<value_size ; ++i)
2608  if(table[i] != 0)
2609  return false;
2610 
2611  return true;
2612  }
2613 
2614 
2618  bool AreFirstBitsZero(uint bits) const
2619  {
2620  TTMATH_ASSERT( bits <= value_size * TTMATH_BITS_PER_UINT )
2621 
2622  uint index = bits / TTMATH_BITS_PER_UINT;
2623  uint rest = bits % TTMATH_BITS_PER_UINT;
2624  uint i;
2625 
2626  for(i=0 ; i<index ; ++i)
2627  if(table[i] != 0 )
2628  return false;
2629 
2630  if( rest == 0 )
2631  return true;
2632 
2633  uint mask = TTMATH_UINT_MAX_VALUE >> (TTMATH_BITS_PER_UINT - rest);
2634 
2635  return (table[i] & mask) == 0;
2636  }
2637 
2638 
2639 
2656  template<uint argument_size>
2658  {
2659  uint min_size = (value_size < argument_size)? value_size : argument_size;
2660  uint i;
2661 
2662  for(i=0 ; i<min_size ; ++i)
2663  table[i] = p.table[i];
2664 
2665 
2666  if( value_size > argument_size )
2667  {
2668  // 'this' is longer than 'p'
2669 
2670  for( ; i<value_size ; ++i)
2671  table[i] = 0;
2672  }
2673  else
2674  {
2675  for( ; i<argument_size ; ++i)
2676  if( p.table[i] != 0 )
2677  {
2678  TTMATH_LOGC("UInt::FromUInt(UInt<>)", 1)
2679  return 1;
2680  }
2681  }
2682 
2683  TTMATH_LOGC("UInt::FromUInt(UInt<>)", 0)
2684 
2685  return 0;
2686  }
2687 
2688 
2697  template<uint argument_size>
2699  {
2700  return FromUInt(p);
2701  }
2702 
2703 
2708  {
2709  for(uint i=1 ; i<value_size ; ++i)
2710  table[i] = 0;
2711 
2712  table[0] = value;
2713 
2714  TTMATH_LOG("UInt::FromUInt(uint)")
2715 
2716  // there'll never be a carry here
2717  return 0;
2718  }
2719 
2720 
2725  {
2726  return FromUInt(value);
2727  }
2728 
2729 
2733  uint FromInt(sint value)
2734  {
2735  uint c = FromUInt(uint(value));
2736 
2737  if( c || value < 0 )
2738  return 1;
2739 
2740  return 0;
2741  }
2742 
2743 
2749  template<uint argument_size>
2751  {
2752  FromUInt(p);
2753 
2754  return *this;
2755  }
2756 
2757 
2762  {
2763  for(uint i=0 ; i<value_size ; ++i)
2764  table[i] = p.table[i];
2765 
2766  TTMATH_LOG("UInt::operator=(UInt<>)")
2767 
2768  return *this;
2769  }
2770 
2771 
2776  {
2777  FromUInt(i);
2778 
2779  return *this;
2780  }
2781 
2782 
2787  {
2788  FromUInt(i);
2789  }
2790 
2791 
2796  {
2797  FromInt(i);
2798 
2799  return *this;
2800  }
2801 
2802 
2808  UInt(sint i)
2809  {
2810  FromInt(i);
2811  }
2812 
2813 
2814 #ifdef TTMATH_PLATFORM32
2815 
2816 
2822  {
2823  table[0] = (uint)n;
2824 
2825  if( value_size == 1 )
2826  {
2827  uint c = ((n >> TTMATH_BITS_PER_UINT) == 0) ? 0 : 1;
2828 
2829  TTMATH_LOGC("UInt::FromUInt(ulint)", c)
2830  return c;
2831  }
2832 
2833  table[1] = (uint)(n >> TTMATH_BITS_PER_UINT);
2834 
2835  for(uint i=2 ; i<value_size ; ++i)
2836  table[i] = 0;
2837 
2838  TTMATH_LOG("UInt::FromUInt(ulint)")
2839 
2840  return 0;
2841  }
2842 
2843 
2849  {
2850  return FromUInt(n);
2851  }
2852 
2853 
2858  uint FromInt(slint n)
2859  {
2860  uint c = FromUInt(ulint(n));
2861 
2862  if( c || n < 0 )
2863  return 1;
2864 
2865  return 0;
2866  }
2867 
2868 
2874  {
2875  FromUInt(n);
2876 
2877  return *this;
2878  }
2879 
2880 
2886  {
2887  FromUInt(n);
2888  }
2889 
2890 
2896  {
2897  FromInt(n);
2898 
2899  return *this;
2900  }
2901 
2902 
2907  UInt(slint n)
2908  {
2909  FromInt(n);
2910  }
2911 
2912 #endif
2913 
2914 
2915 
2916 #ifdef TTMATH_PLATFORM64
2917 
2918 
2923  uint FromUInt(unsigned int i)
2924  {
2925  return FromUInt(uint(i));
2926  }
2927 
2932  uint FromInt(unsigned int i)
2933  {
2934  return FromUInt(uint(i));
2935  }
2936 
2937 
2942  uint FromInt(signed int i)
2943  {
2944  return FromInt(sint(i));
2945  }
2946 
2947 
2952  UInt<value_size> & operator=(unsigned int i)
2953  {
2954  FromUInt(i);
2955 
2956  return *this;
2957  }
2958 
2959 
2964  UInt(unsigned int i)
2965  {
2966  FromUInt(i);
2967  }
2968 
2969 
2974  UInt<value_size> & operator=(signed int i)
2975  {
2976  FromInt(i);
2977 
2978  return *this;
2979  }
2980 
2981 
2986  UInt(signed int i)
2987  {
2988  FromInt(i);
2989  }
2990 
2991 
2992 #endif
2993 
2994 
2995 
2996 
2997 
3001  UInt(const char * s)
3002  {
3003  FromString(s);
3004  }
3005 
3006 
3010  UInt(const std::string & s)
3011  {
3012  FromString( s.c_str() );
3013  }
3014 
3015 
3016 #ifndef TTMATH_DONT_USE_WCHAR
3017 
3021  UInt(const wchar_t * s)
3022  {
3023  FromString(s);
3024  }
3025 
3026 
3030  UInt(const std::wstring & s)
3031  {
3032  FromString( s.c_str() );
3033  }
3034 
3035 #endif
3036 
3037 
3038 
3039 
3046  {
3047  // when macro TTMATH_DEBUG_LOG is defined
3048  // we set special values to the table
3049  // in order to be everywhere the same value of the UInt object
3050  // without this it would be difficult to analyse the log file
3051  #ifdef TTMATH_DEBUG_LOG
3052  #ifdef TTMATH_PLATFORM32
3053  for(uint i=0 ; i<value_size ; ++i)
3054  table[i] = 0xc1c1c1c1;
3055  #else
3056  for(uint i=0 ; i<value_size ; ++i)
3057  table[i] = 0xc1c1c1c1c1c1c1c1;
3058  #endif
3059  #endif
3060  }
3061 
3062 
3067  {
3068  for(uint i=0 ; i<value_size ; ++i)
3069  table[i] = u.table[i];
3070 
3071  TTMATH_LOG("UInt::UInt(UInt<>)")
3072  }
3073 
3074 
3075 
3079  template<uint argument_size>
3081  {
3082  // look that 'size' we still set as 'value_size' and not as u.value_size
3083  FromUInt(u);
3084  }
3085 
3086 
3087 
3088 
3093  {
3094  }
3095 
3096 
3103  uint ToUInt() const
3104  {
3105  return table[0];
3106  }
3107 
3108 
3113  uint ToUInt(uint & result) const
3114  {
3115  result = table[0];
3116 
3117  for(uint i=1 ; i<value_size ; ++i)
3118  if( table[i] != 0 )
3119  return 1;
3120 
3121  return 0;
3122  }
3123 
3124 
3129  uint ToInt(uint & result) const
3130  {
3131  return ToUInt(result);
3132  }
3133 
3134 
3139  uint ToInt(sint & result) const
3140  {
3141  result = sint(table[0]);
3142 
3143  if( (result & TTMATH_UINT_HIGHEST_BIT) != 0 )
3144  return 1;
3145 
3146  for(uint i=1 ; i<value_size ; ++i)
3147  if( table[i] != 0 )
3148  return 1;
3149 
3150  return 0;
3151  }
3152 
3153 
3154 #ifdef TTMATH_PLATFORM32
3155 
3161  uint ToUInt(ulint & result) const
3162  {
3163  if( value_size == 1 )
3164  {
3165  result = table[0];
3166  }
3167  else
3168  {
3169  uint low = table[0];
3170  uint high = table[1];
3171 
3172  result = low;
3173  result |= (ulint(high) << TTMATH_BITS_PER_UINT);
3174 
3175  for(uint i=2 ; i<value_size ; ++i)
3176  if( table[i] != 0 )
3177  return 1;
3178  }
3179 
3180  return 0;
3181  }
3182 
3183 
3189  uint ToInt(ulint & result) const
3190  {
3191  return ToUInt(result);
3192  }
3193 
3194 
3200  uint ToInt(slint & result) const
3201  {
3202  ulint temp;
3203 
3204  uint c = ToUInt(temp);
3205  result = slint(temp);
3206 
3207  if( c || result < 0 )
3208  return 1;
3209 
3210  return 0;
3211  }
3212 
3213 #endif
3214 
3215 
3216 
3217 #ifdef TTMATH_PLATFORM64
3218 
3224  uint ToUInt(unsigned int & result) const
3225  {
3226  result = (unsigned int)table[0];
3227 
3228  if( (table[0] >> 32) != 0 )
3229  return 1;
3230 
3231  for(uint i=1 ; i<value_size ; ++i)
3232  if( table[i] != 0 )
3233  return 1;
3234 
3235  return 0;
3236  }
3237 
3238 
3244  uint ToInt(unsigned int & result) const
3245  {
3246  return ToUInt(result);
3247  }
3248 
3249 
3255  uint ToInt(int & result) const
3256  {
3257  unsigned int temp;
3258 
3259  uint c = ToUInt(temp);
3260  result = int(temp);
3261 
3262  if( c || result < 0 )
3263  return 1;
3264 
3265  return 0;
3266  }
3267 
3268 
3269 #endif
3270 
3271 
3272 
3273 
3274 protected:
3275 
3281  double ToStringLog2(uint x) const
3282  {
3283  static double log_tab[] = {
3284  1.000000000000000000,
3285  0.630929753571457437,
3286  0.500000000000000000,
3287  0.430676558073393050,
3288  0.386852807234541586,
3289  0.356207187108022176,
3290  0.333333333333333333,
3291  0.315464876785728718,
3292  0.301029995663981195,
3293  0.289064826317887859,
3294  0.278942945651129843,
3295  0.270238154427319741,
3296  0.262649535037193547,
3297  0.255958024809815489,
3298  0.250000000000000000
3299  };
3300 
3301  if( x<2 || x>16 )
3302  return 0;
3303 
3304  return log_tab[x-2];
3305  }
3306 
3307 
3308 public:
3309 
3310 
3315  template<class string_type>
3316  void ToStringBase(string_type & result, uint b = 10, bool negative = false) const
3317  {
3318  UInt<value_size> temp(*this);
3319  uint rest, table_id, index, digits;
3320  double digits_d;
3321  char character;
3322 
3323  result.clear();
3324 
3325  if( b<2 || b>16 )
3326  return;
3327 
3328  if( !FindLeadingBit(table_id, index) )
3329  {
3330  result = '0';
3331  return;
3332  }
3333 
3334  if( negative )
3335  result = '-';
3336 
3337  digits_d = static_cast<double>(table_id); // for not making an overflow in uint type
3338  digits_d *= TTMATH_BITS_PER_UINT;
3339  digits_d += index + 1;
3340  digits_d *= ToStringLog2(b);
3341  digits = static_cast<uint>(digits_d) + 3; // plus some epsilon
3342 
3343  if( result.capacity() < digits )
3344  result.reserve(digits);
3345 
3346  do
3347  {
3348  temp.DivInt(b, &rest);
3349  character = static_cast<char>(Misc::DigitToChar(rest));
3350  result.insert(result.end(), character);
3351  }
3352  while( !temp.IsZero() );
3353 
3354  size_t i1 = negative ? 1 : 0; // the first is a hyphen (when negative is true)
3355  size_t i2 = result.size() - 1;
3356 
3357  for( ; i1 < i2 ; ++i1, --i2 )
3358  {
3359  char tempc = static_cast<char>(result[i1]);
3360  result[i1] = result[i2];
3361  result[i2] = tempc;
3362  }
3363  }
3364 
3365 
3366 
3370  void ToString(std::string & result, uint b = 10) const
3371  {
3372  return ToStringBase(result, b);
3373  }
3374 
3375 
3376  std::string ToString(uint b = 10) const
3377  {
3378  std::string result;
3379  ToStringBase(result, b);
3380 
3381  return result;
3382  }
3383 
3384 
3385 #ifndef TTMATH_DONT_USE_WCHAR
3386 
3387  void ToString(std::wstring & result, uint b = 10) const
3388  {
3389  return ToStringBase(result, b);
3390  }
3391 
3392  std::wstring ToWString(uint b = 10) const
3393  {
3394  std::wstring result;
3395  ToStringBase(result, b);
3396 
3397  return result;
3398  }
3399 
3400 #endif
3401 
3402 
3403 
3404 private:
3405 
3409  template<class char_type>
3410  uint FromStringBase(const char_type * s, uint b = 10, const char_type ** after_source = 0, bool * value_read = 0)
3411  {
3412  UInt<value_size> base( b );
3413  UInt<value_size> temp;
3414  sint z;
3415  uint c = 0;
3416 
3417  SetZero();
3418  temp.SetZero();
3419  Misc::SkipWhiteCharacters(s);
3420 
3421  if( after_source )
3422  *after_source = s;
3423 
3424  if( value_read )
3425  *value_read = false;
3426 
3427  if( b<2 || b>16 )
3428  return 1;
3429 
3430 
3431  for( ; (z=Misc::CharToDigit(*s, b)) != -1 ; ++s)
3432  {
3433  if( value_read )
3434  *value_read = true;
3435 
3436  if( c == 0 )
3437  {
3438  temp.table[0] = z;
3439 
3440  c += Mul(base); // !! IMPROVE ME: there can be used MulInt here
3441  c += Add(temp);
3442  }
3443  }
3444 
3445  if( after_source )
3446  *after_source = s;
3447 
3448  TTMATH_LOGC("UInt::FromString", c)
3449 
3450  return (c==0)? 0 : 1;
3451  }
3452 
3453 
3454 public:
3455 
3456 
3474  uint FromString(const char * s, uint b = 10, const char ** after_source = 0, bool * value_read = 0)
3475  {
3476  return FromStringBase(s, b, after_source, value_read);
3477  }
3478 
3479 
3485  uint FromString(const std::string & s, uint b = 10)
3486  {
3487  return FromString( s.c_str(), b );
3488  }
3489 
3490 
3494  UInt<value_size> & operator=(const char * s)
3495  {
3496  FromString(s);
3497 
3498  return *this;
3499  }
3500 
3501 
3505  UInt<value_size> & operator=(const std::string & s)
3506  {
3507  FromString( s.c_str() );
3508 
3509  return *this;
3510  }
3511 
3512 
3513 
3514 #ifndef TTMATH_DONT_USE_WCHAR
3515 
3519  uint FromString(const wchar_t * s, uint b = 10, const wchar_t ** after_source = 0, bool * value_read = 0)
3520  {
3521  return FromStringBase(s, b, after_source, value_read);
3522  }
3523 
3524 
3530  uint FromString(const std::wstring & s, uint b = 10)
3531  {
3532  return FromString( s.c_str(), b );
3533  }
3534 
3535 
3539  UInt<value_size> & operator=(const wchar_t * s)
3540  {
3541  FromString(s);
3542 
3543  return *this;
3544  }
3545 
3546 
3550  UInt<value_size> & operator=(const std::wstring & s)
3551  {
3552  FromString( s.c_str() );
3553 
3554  return *this;
3555  }
3556 
3557 #endif
3558 
3559 
3575  bool CmpSmaller(const UInt<value_size> & l, sint index = -1) const
3576  {
3577  sint i;
3578 
3579  if( index==-1 || index>=sint(value_size) )
3580  i = value_size - 1;
3581  else
3582  i = index;
3583 
3584 
3585  for( ; i>=0 ; --i)
3586  {
3587  if( table[i] != l.table[i] )
3588  return table[i] < l.table[i];
3589  }
3590 
3591  // they're equal
3592  return false;
3593  }
3594 
3595 
3596 
3606  bool CmpBigger(const UInt<value_size> & l, sint index = -1) const
3607  {
3608  sint i;
3609 
3610  if( index==-1 || index>=sint(value_size) )
3611  i = value_size - 1;
3612  else
3613  i = index;
3614 
3615 
3616  for( ; i>=0 ; --i)
3617  {
3618  if( table[i] != l.table[i] )
3619  return table[i] > l.table[i];
3620  }
3621 
3622  // they're equal
3623  return false;
3624  }
3625 
3626 
3634  bool CmpEqual(const UInt<value_size> & l, sint index = -1) const
3635  {
3636  sint i;
3637 
3638  if( index==-1 || index>=sint(value_size) )
3639  i = value_size - 1;
3640  else
3641  i = index;
3642 
3643 
3644  for( ; i>=0 ; --i)
3645  if( table[i] != l.table[i] )
3646  return false;
3647 
3648  return true;
3649  }
3650 
3651 
3652 
3660  bool CmpSmallerEqual(const UInt<value_size> & l, sint index=-1) const
3661  {
3662  sint i;
3663 
3664  if( index==-1 || index>=sint(value_size) )
3665  i = value_size - 1;
3666  else
3667  i = index;
3668 
3669 
3670  for( ; i>=0 ; --i)
3671  {
3672  if( table[i] != l.table[i] )
3673  return table[i] < l.table[i];
3674  }
3675 
3676  // they're equal
3677  return true;
3678  }
3679 
3680 
3681 
3689  bool CmpBiggerEqual(const UInt<value_size> & l, sint index=-1) const
3690  {
3691  sint i;
3692 
3693  if( index==-1 || index>=sint(value_size) )
3694  i = value_size - 1;
3695  else
3696  i = index;
3697 
3698 
3699  for( ; i>=0 ; --i)
3700  {
3701  if( table[i] != l.table[i] )
3702  return table[i] > l.table[i];
3703  }
3704 
3705  // they're equal
3706  return true;
3707  }
3708 
3709 
3710  /*
3711  operators for comparising
3712  */
3713 
3714  bool operator<(const UInt<value_size> & l) const
3715  {
3716  return CmpSmaller(l);
3717  }
3718 
3719 
3720  bool operator>(const UInt<value_size> & l) const
3721  {
3722  return CmpBigger(l);
3723  }
3724 
3725 
3726  bool operator==(const UInt<value_size> & l) const
3727  {
3728  return CmpEqual(l);
3729  }
3730 
3731 
3732  bool operator!=(const UInt<value_size> & l) const
3733  {
3734  return !operator==(l);
3735  }
3736 
3737 
3738  bool operator<=(const UInt<value_size> & l) const
3739  {
3740  return CmpSmallerEqual(l);
3741  }
3742 
3743  bool operator>=(const UInt<value_size> & l) const
3744  {
3745  return CmpBiggerEqual(l);
3746  }
3747 
3748 
3756  {
3757  UInt<value_size> temp(*this);
3758 
3759  temp.Sub(p2);
3760 
3761  return temp;
3762  }
3763 
3764  UInt<value_size> & operator-=(const UInt<value_size> & p2)
3765  {
3766  Sub(p2);
3767 
3768  return *this;
3769  }
3770 
3771  UInt<value_size> operator+(const UInt<value_size> & p2) const
3772  {
3773  UInt<value_size> temp(*this);
3774 
3775  temp.Add(p2);
3776 
3777  return temp;
3778  }
3779 
3780  UInt<value_size> & operator+=(const UInt<value_size> & p2)
3781  {
3782  Add(p2);
3783 
3784  return *this;
3785  }
3786 
3787 
3788  UInt<value_size> operator*(const UInt<value_size> & p2) const
3789  {
3790  UInt<value_size> temp(*this);
3791 
3792  temp.Mul(p2);
3793 
3794  return temp;
3795  }
3796 
3797 
3798  UInt<value_size> & operator*=(const UInt<value_size> & p2)
3799  {
3800  Mul(p2);
3801 
3802  return *this;
3803  }
3804 
3805 
3806  UInt<value_size> operator/(const UInt<value_size> & p2) const
3807  {
3808  UInt<value_size> temp(*this);
3809 
3810  temp.Div(p2);
3811 
3812  return temp;
3813  }
3814 
3815 
3816  UInt<value_size> & operator/=(const UInt<value_size> & p2)
3817  {
3818  Div(p2);
3819 
3820  return *this;
3821  }
3822 
3823 
3824  UInt<value_size> operator%(const UInt<value_size> & p2) const
3825  {
3826  UInt<value_size> temp(*this);
3827  UInt<value_size> remainder;
3828 
3829  temp.Div( p2, remainder );
3830 
3831  return remainder;
3832  }
3833 
3834 
3835  UInt<value_size> & operator%=(const UInt<value_size> & p2)
3836  {
3837  UInt<value_size> remainder;
3838 
3839  Div( p2, remainder );
3840  operator=(remainder);
3841 
3842  return *this;
3843  }
3844 
3845 
3850  {
3851  AddOne();
3852 
3853  return *this;
3854  }
3855 
3856 
3861  {
3862  UInt<value_size> temp( *this );
3863 
3864  AddOne();
3865 
3866  return temp;
3867  }
3868 
3869 
3870  UInt<value_size> & operator--()
3871  {
3872  SubOne();
3873 
3874  return *this;
3875  }
3876 
3877 
3878  UInt<value_size> operator--(int)
3879  {
3880  UInt<value_size> temp( *this );
3881 
3882  SubOne();
3883 
3884  return temp;
3885  }
3886 
3887 
3888 
3896  {
3897  UInt<value_size> temp( *this );
3898 
3899  temp.BitNot();
3900 
3901  return temp;
3902  }
3903 
3904 
3905  UInt<value_size> operator&(const UInt<value_size> & p2) const
3906  {
3907  UInt<value_size> temp( *this );
3908 
3909  temp.BitAnd(p2);
3910 
3911  return temp;
3912  }
3913 
3914 
3915  UInt<value_size> & operator&=(const UInt<value_size> & p2)
3916  {
3917  BitAnd(p2);
3918 
3919  return *this;
3920  }
3921 
3922 
3923  UInt<value_size> operator|(const UInt<value_size> & p2) const
3924  {
3925  UInt<value_size> temp( *this );
3926 
3927  temp.BitOr(p2);
3928 
3929  return temp;
3930  }
3931 
3932 
3933  UInt<value_size> & operator|=(const UInt<value_size> & p2)
3934  {
3935  BitOr(p2);
3936 
3937  return *this;
3938  }
3939 
3940 
3941  UInt<value_size> operator^(const UInt<value_size> & p2) const
3942  {
3943  UInt<value_size> temp( *this );
3944 
3945  temp.BitXor(p2);
3946 
3947  return temp;
3948  }
3949 
3950 
3951  UInt<value_size> & operator^=(const UInt<value_size> & p2)
3952  {
3953  BitXor(p2);
3954 
3955  return *this;
3956  }
3957 
3958 
3959  UInt<value_size> operator>>(int move) const
3960  {
3961  UInt<value_size> temp( *this );
3962 
3963  temp.Rcr(move);
3964 
3965  return temp;
3966  }
3967 
3968 
3969  UInt<value_size> & operator>>=(int move)
3970  {
3971  Rcr(move);
3972 
3973  return *this;
3974  }
3975 
3976 
3977  UInt<value_size> operator<<(int move) const
3978  {
3979  UInt<value_size> temp( *this );
3980 
3981  temp.Rcl(move);
3982 
3983  return temp;
3984  }
3985 
3986 
3987  UInt<value_size> & operator<<=(int move)
3988  {
3989  Rcl(move);
3990 
3991  return *this;
3992  }
3993 
3994 
4004 private:
4005 
4006 
4010  template<class ostream_type, class string_type>
4011  static ostream_type & OutputToStream(ostream_type & s, const UInt<value_size> & l)
4012  {
4013  string_type ss;
4014 
4015  l.ToString(ss);
4016  s << ss;
4017 
4018  return s;
4019  }
4020 
4021 
4022 public:
4023 
4024 
4028  friend std::ostream & operator<<(std::ostream & s, const UInt<value_size> & l)
4029  {
4030  return OutputToStream<std::ostream, std::string>(s, l);
4031  }
4032 
4033 
4034 #ifndef TTMATH_DONT_USE_WCHAR
4035 
4039  friend std::wostream & operator<<(std::wostream & s, const UInt<value_size> & l)
4040  {
4041  return OutputToStream<std::wostream, std::wstring>(s, l);
4042  }
4043 
4044 #endif
4045 
4046 
4047 
4048 private:
4049 
4053  template<class istream_type, class string_type, class char_type>
4054  static istream_type & InputFromStream(istream_type & s, UInt<value_size> & l)
4055  {
4056  string_type ss;
4057 
4058  // char or wchar_t for operator>>
4059  char_type z;
4060 
4061  // operator>> omits white characters if they're set for ommiting
4062  s >> z;
4063 
4064  // we're reading only digits (base=10)
4065  while( s.good() && Misc::CharToDigit(z, 10)>=0 )
4066  {
4067  ss += z;
4068  z = static_cast<char_type>(s.get());
4069  }
4070 
4071  // we're leaving the last read character
4072  // (it's not belonging to the value)
4073  s.unget();
4074 
4075  l.FromString(ss);
4076 
4077  return s;
4078  }
4079 
4080 public:
4081 
4082 
4086  friend std::istream & operator>>(std::istream & s, UInt<value_size> & l)
4087  {
4088  return InputFromStream<std::istream, std::string, char>(s, l);
4089  }
4090 
4091 
4092 #ifndef TTMATH_DONT_USE_WCHAR
4093 
4097  friend std::wistream & operator>>(std::wistream & s, UInt<value_size> & l)
4098  {
4099  return InputFromStream<std::wistream, std::wstring, wchar_t>(s, l);
4100  }
4101 
4102 #endif
4103 
4104 
4105  /*
4106  Following methods are defined in:
4107  ttmathuint_x86.h
4108  ttmathuint_x86_64.h
4109  ttmathuint_noasm.h
4110  */
4111 
4112 #ifdef TTMATH_NOASM
4113  static uint AddTwoWords(uint a, uint b, uint carry, uint * result);
4114  static uint SubTwoWords(uint a, uint b, uint carry, uint * result);
4115 
4116 #ifdef TTMATH_PLATFORM64
4117 
4118  union uint_
4119  {
4120  struct
4121  {
4122  unsigned int low; // 32 bit
4123  unsigned int high; // 32 bit
4124  } u_;
4125 
4126  uint u; // 64 bit
4127  };
4128 
4129 
4130  static void DivTwoWords2(uint a,uint b, uint c, uint * r, uint * rest);
4131  static uint DivTwoWordsNormalize(uint_ & a_, uint_ & b_, uint_ & c_);
4132  static uint DivTwoWordsUnnormalize(uint u, uint d);
4133  static unsigned int DivTwoWordsCalculate(uint_ u_, unsigned int u3, uint_ v_);
4134  static void MultiplySubtract(uint_ & u_, unsigned int & u3, unsigned int & q, uint_ v_);
4135 
4136 #endif // TTMATH_PLATFORM64
4137 #endif // TTMATH_NOASM
4138 
4139 
4140 private:
4141  uint Rcl2_one(uint c);
4142  uint Rcr2_one(uint c);
4143  uint Rcl2(uint bits, uint c);
4144  uint Rcr2(uint bits, uint c);
4145 
4146 public:
4147  static const char * LibTypeStr();
4148  static LibTypeCode LibType();
4149  uint Add(const UInt<value_size> & ss2, uint c=0);
4150  uint AddInt(uint value, uint index = 0);
4151  uint AddTwoInts(uint x2, uint x1, uint index);
4152  static uint AddVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result);
4153  uint Sub(const UInt<value_size> & ss2, uint c=0);
4154  uint SubInt(uint value, uint index = 0);
4155  static uint SubVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result);
4156  static sint FindLeadingBitInWord(uint x);
4157  static sint FindLowestBitInWord(uint x);
4158  static uint SetBitInWord(uint & value, uint bit);
4159  static void MulTwoWords(uint a, uint b, uint * result_high, uint * result_low);
4160  static void DivTwoWords(uint a,uint b, uint c, uint * r, uint * rest);
4161 
4162 };
4163 
4164 
4165 
4170 template<>
4171 class UInt<0>
4172 {
4173 public:
4174  uint table[1];
4175 
4176  void Mul2Big(const UInt<0> &, UInt<0> &) { TTMATH_ASSERT(false) };
4177  void SetZero() { TTMATH_ASSERT(false) };
4178  uint AddTwoInts(uint, uint, uint) { TTMATH_ASSERT(false) return 0; };
4179 };
4180 
4181 
4182 } //namespace
4183 
4184 
4185 #include "ttmathuint_x86.h"
4186 #include "ttmathuint_x86_64.h"
4187 #include "ttmathuint_noasm.h"
4188 
4189 #endif
UInt< value_size > & operator=(slint n)
Definition: ttmathuint.h:2895
bool IsOnlyTheLowestBitSet() const
Definition: ttmathuint.h:2589
uint Mul3(const UInt< value_size > &ss2)
Definition: ttmathuint.h:1212
uint FromString(const std::wstring &s, uint b=10)
Definition: ttmathuint.h:3530
bool CmpBigger(const UInt< value_size > &l, sint index=-1) const
Definition: ttmathuint.h:3606
uint ToUInt(ulint &result) const
Definition: ttmathuint.h:3161
static void PrintVectorLog(const char_type *msg, ostream_type &output, const uint *vector, uint vector_len)
Definition: ttmathuint.h:135
uint ToInt(ulint &result) const
Definition: ttmathuint.h:3189
uint ToInt(sint &result) const
Definition: ttmathuint.h:3139
uint MulFastest(const UInt< value_size > &ss2)
Definition: ttmathuint.h:1479
uint FromUInt(ulint n)
Definition: ttmathuint.h:2821
UInt< value_size > operator~() const
Definition: ttmathuint.h:3895
UInt< value_size > & operator=(const char *s)
Definition: ttmathuint.h:3494
uint FromUInt(const UInt< argument_size > &p)
Definition: ttmathuint.h:2657
void Mul2Big(const UInt< value_size > &ss2, UInt< value_size *2 > &result)
Definition: ttmathuint.h:1113
void Sqrt()
Definition: ttmathuint.h:2461
UInt implements a big integer value without a sign.
Definition: ttmathuint.h:73
void MulInt(uint ss2, UInt< result_size > &result) const
Definition: ttmathuint.h:873
void BitOr(const UInt< value_size > &ss2)
Definition: ttmathuint.h:755
some helpful functions
UInt< value_size > & operator=(const UInt< argument_size > &p)
Definition: ttmathuint.h:2750
void BitXor(const UInt< value_size > &ss2)
Definition: ttmathuint.h:767
void ToStringBase(string_type &result, uint b=10, bool negative=false) const
Definition: ttmathuint.h:3316
uint SubOne()
Definition: ttmathuint.h:395
uint FromString(const std::string &s, uint b=10)
Definition: ttmathuint.h:3485
UInt(const std::wstring &s)
Definition: ttmathuint.h:3030
void PrintLog(const char_type *msg, ostream_type &output) const
Definition: ttmathuint.h:159
uint FromInt(uint value)
Definition: ttmathuint.h:2724
static uint CharToDigit(uint c)
Definition: ttmathmisc.h:181
uint FromString(const wchar_t *s, uint b=10, const wchar_t **after_source=0, bool *value_read=0)
Definition: ttmathuint.h:3519
void SetMin()
Definition: ttmathuint.h:228
UInt< value_size > & operator=(uint i)
Definition: ttmathuint.h:2775
UInt< value_size > & operator=(const std::wstring &s)
Definition: ttmathuint.h:3550
void PrintTable(ostream_type &output) const
Definition: ttmathuint.h:97
uint FromInt(slint n)
Definition: ttmathuint.h:2858
void SetMax()
Definition: ttmathuint.h:215
uint ToUInt(uint &result) const
Definition: ttmathuint.h:3113
void PrintLog(const char_type *msg, uint carry, ostream_type &output) const
Definition: ttmathuint.h:169
uint Div(const UInt< value_size > &divisor, UInt< value_size > *remainder=0, uint algorithm=3)
Definition: ttmathuint.h:1626
uint Div3(const UInt< value_size > &ss2, UInt< value_size > &remainder)
Definition: ttmathuint.h:2125
uint Size() const
Definition: ttmathuint.h:179
void MulBig(const UInt< value_size > &ss2, UInt< value_size *2 > &result, uint algorithm=100)
Definition: ttmathuint.h:951
void Mul1Big(const UInt< value_size > &ss2_, UInt< value_size *2 > &result)
Definition: ttmathuint.h:1043
uint Mul1(const UInt< value_size > &ss2)
Definition: ttmathuint.h:1023
uint Div1(const UInt< value_size > &divisor, UInt< value_size > *remainder=0)
Definition: ttmathuint.h:1752
uint Mul2(const UInt< value_size > &ss2)
Definition: ttmathuint.h:1082
bool CmpEqual(const UInt< value_size > &l, sint index=-1) const
Definition: ttmathuint.h:3634
bool IsTheLowestBitSet() const
Definition: ttmathuint.h:2556
void BitNot2()
Definition: ttmathuint.h:795
UInt< value_size > & operator++()
Definition: ttmathuint.h:3849
UInt< value_size > operator-(const UInt< value_size > &p2) const
Definition: ttmathuint.h:3755
void Mul3Big(const UInt< value_size > &ss2, UInt< value_size *2 > &result)
Definition: ttmathuint.h:1245
uint CompensationToLeft()
Definition: ttmathuint.h:598
uint FromInt(const UInt< argument_size > &p)
Definition: ttmathuint.h:2698
void BitNot()
Definition: ttmathuint.h:779
void ToString(std::string &result, uint b=10) const
Definition: ttmathuint.h:3370
uint Rcl(uint bits, uint c=0)
Definition: ttmathuint.h:460
#define TTMATH_UINT_HIGHEST_BIT
Definition: ttmathtypes.h:212
static uint DigitToChar(uint digit)
Definition: ttmathmisc.h:236
template class UInt with methods without any assembler code (used for no-asm version of ttmath)...
void Swap(UInt< value_size > &ss2)
Definition: ttmathuint.h:239
void ClearFirstBits(uint n)
Definition: ttmathuint.h:2508
bool CmpBiggerEqual(const UInt< value_size > &l, sint index=-1) const
Definition: ttmathuint.h:3689
UInt< value_size > & operator=(const std::string &s)
Definition: ttmathuint.h:3505
uint Pow(UInt< value_size > pow)
Definition: ttmathuint.h:2425
bool CmpSmaller(const UInt< value_size > &l, sint index=-1) const
Definition: ttmathuint.h:3575
a namespace for the TTMath library
Definition: ttmath.h:62
Definition: ttmathuint.h:4171
UInt< value_size > operator++(int)
Definition: ttmathuint.h:3860
LibTypeCode
Definition: ttmathtypes.h:368
void SetZero()
Definition: ttmathuint.h:188
constants used in the library
uint AddOne()
Definition: ttmathuint.h:386
friend std::wistream & operator>>(std::wistream &s, UInt< value_size > &l)
Definition: ttmathuint.h:4097
~UInt()
Definition: ttmathuint.h:3092
#define TTMATH_UINT_MAX_VALUE
Definition: ttmathtypes.h:218
friend std::istream & operator>>(std::istream &s, UInt< value_size > &l)
Definition: ttmathuint.h:4086
void BitAnd(const UInt< value_size > &ss2)
Definition: ttmathuint.h:743
uint Mul(const UInt< value_size > &ss2, uint algorithm=100)
Definition: ttmathuint.h:923
uint FromInt(ulint n)
Definition: ttmathuint.h:2848
uint DivInt(uint divisor, uint *remainder=0)
Definition: ttmathuint.h:1568
UInt(uint i)
Definition: ttmathuint.h:2786
UInt(const UInt< argument_size > &u)
Definition: ttmathuint.h:3080
void MulFastestBig(const UInt< value_size > &ss2, UInt< value_size *2 > &result)
Definition: ttmathuint.h:1510
uint FromInt(sint value)
Definition: ttmathuint.h:2733
bool FindLowestBit(uint &table_id, uint &index) const
Definition: ttmathuint.h:681
void SetOne()
Definition: ttmathuint.h:202
static void PrintVectorLog(const char_type *msg, uint carry, ostream_type &output, const uint *vector, uint vector_len)
Definition: ttmathuint.h:148
uint FromString(const char *s, uint b=10, const char **after_source=0, bool *value_read=0)
Definition: ttmathuint.h:3474
bool CmpSmallerEqual(const UInt< value_size > &l, sint index=-1) const
Definition: ttmathuint.h:3660
#define TTMATH_BITS_PER_UINT
Definition: ttmathtypes.h:207
#define TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE
Definition: ttmathtypes.h:338
bool IsOnlyTheHighestBitSet() const
Definition: ttmathuint.h:2565
bool AreFirstBitsZero(uint bits) const
Definition: ttmathuint.h:2618
uint ToInt(slint &result) const
Definition: ttmathuint.h:3200
uint64_t ulint
Definition: ttmathtypes.h:200
UInt(const UInt< value_size > &u)
Definition: ttmathuint.h:3066
uint Div1(const UInt< value_size > &divisor, UInt< value_size > &remainder)
Definition: ttmathuint.h:1775
UInt(ulint n)
Definition: ttmathuint.h:2885
UInt(const std::string &s)
Definition: ttmathuint.h:3010
uint Div2(const UInt< value_size > &divisor, UInt< value_size > &remainder)
Definition: ttmathuint.h:1883
uint table[value_size]
Definition: ttmathuint.h:81
UInt()
Definition: ttmathuint.h:3045
uint MulInt(uint ss2)
Definition: ttmathuint.h:835
void SetFromTable(const uint *temp_table, uint temp_table_len)
Definition: ttmathuint.h:266
UInt< value_size > & operator=(const wchar_t *s)
Definition: ttmathuint.h:3539
bool IsZero() const
Definition: ttmathuint.h:2605
UInt(slint n)
Definition: ttmathuint.h:2907
uint Div2(const UInt< value_size > &divisor, UInt< value_size > *remainder=0)
Definition: ttmathuint.h:1862
UInt< value_size > & operator=(sint i)
Definition: ttmathuint.h:2795
uint GetBit(uint bit_index) const
Definition: ttmathuint.h:706
uint FromUInt(uint value)
Definition: ttmathuint.h:2707
unsigned int uint
Definition: ttmathtypes.h:186
UInt(const char *s)
Definition: ttmathuint.h:3001
uint Div3(const UInt< value_size > &ss2, UInt< value_size > *remainder=0)
Definition: ttmathuint.h:2108
uint ToUInt() const
Definition: ttmathuint.h:3103
double ToStringLog2(uint x) const
Definition: ttmathuint.h:3281
bool IsTheHighestBitSet() const
Definition: ttmathuint.h:2547
UInt(sint i)
Definition: ttmathuint.h:2808
uint Rcr(uint bits, uint c=0)
Definition: ttmathuint.h:555
UInt< value_size > & operator=(ulint n)
Definition: ttmathuint.h:2873
template class UInt with assembler code for 32bit x86 processors
UInt< value_size > & operator=(const UInt< value_size > &p)
Definition: ttmathuint.h:2761
uint ToInt(uint &result) const
Definition: ttmathuint.h:3129
#define TTMATH_REFERENCE_ASSERT(expression)
Definition: ttmathtypes.h:693
uint SetBit(uint bit_index)
Definition: ttmathuint.h:726
bool FindLeadingBit(uint &table_id, uint &index) const
Definition: ttmathuint.h:649
UInt(const wchar_t *s)
Definition: ttmathuint.h:3021