All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 (new) BSD licence.
4  * Author: Tomasz Sowa <t.sowa@ttmath.org>
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 
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)
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  return Mul1Big(ss2, result);
959 
960  case 2:
961  return Mul2Big(ss2, result);
962 
963  case 3:
964  return Mul3Big(ss2, result);
965 
966  case 100:
967  default:
968  return MulFastestBig(ss2, result);
969  }
970  }
971 
972 
973 
978 private:
979 
985  uint Mul1Ref(const UInt<value_size> & ss2)
986  {
988 
989  UInt<value_size> ss1( *this );
990  SetZero();
991 
992  for(uint i=0; i < value_size*TTMATH_BITS_PER_UINT ; ++i)
993  {
994  if( Add(*this) )
995  {
996  TTMATH_LOGC("UInt::Mul1", 1)
997  return 1;
998  }
999 
1000  if( ss1.Rcl(1) )
1001  if( Add(ss2) )
1002  {
1003  TTMATH_LOGC("UInt::Mul1", 1)
1004  return 1;
1005  }
1006  }
1007 
1008  TTMATH_LOGC("UInt::Mul1", 0)
1009 
1010  return 0;
1011  }
1012 
1013 
1014 public:
1015 
1020  uint Mul1(const UInt<value_size> & ss2)
1021  {
1022  if( this == &ss2 )
1023  {
1024  UInt<value_size> copy_ss2(ss2);
1025  return Mul1Ref(copy_ss2);
1026  }
1027  else
1028  {
1029  return Mul1Ref(ss2);
1030  }
1031  }
1032 
1033 
1040  void Mul1Big(const UInt<value_size> & ss2_, UInt<value_size*2> & result)
1041  {
1042  UInt<value_size*2> ss2;
1043  uint i;
1044 
1045  // copying *this into result and ss2_ into ss2
1046  for(i=0 ; i<value_size ; ++i)
1047  {
1048  result.table[i] = table[i];
1049  ss2.table[i] = ss2_.table[i];
1050  }
1051 
1052  // cleaning the highest bytes in result and ss2
1053  for( ; i < value_size*2 ; ++i)
1054  {
1055  result.table[i] = 0;
1056  ss2.table[i] = 0;
1057  }
1058 
1059  // multiply
1060  // (there will not be a carry)
1061  result.Mul1( ss2 );
1062 
1063  TTMATH_LOG("UInt::Mul1Big")
1064  }
1065 
1066 
1067 
1080  {
1081  UInt<value_size*2> result;
1082  uint i, c = 0;
1083 
1084  Mul2Big(ss2, result);
1085 
1086  // copying result
1087  for(i=0 ; i<value_size ; ++i)
1088  table[i] = result.table[i];
1089 
1090  // testing carry
1091  for( ; i<value_size*2 ; ++i)
1092  if( result.table[i] != 0 )
1093  {
1094  c = 1;
1095  break;
1096  }
1097 
1098  TTMATH_LOGC("UInt::Mul2", c)
1099 
1100  return c;
1101  }
1102 
1103 
1110  void Mul2Big(const UInt<value_size> & ss2, UInt<value_size*2> & result)
1111  {
1112  Mul2Big2<value_size>(table, ss2.table, result);
1113 
1114  TTMATH_LOG("UInt::Mul2Big")
1115  }
1116 
1117 
1118 private:
1119 
1127  template<uint ss_size>
1128  void Mul2Big2(const uint * ss1, const uint * ss2, UInt<ss_size*2> & result)
1129  {
1130  uint x1size = ss_size, x2size = ss_size;
1131  uint x1start = 0, x2start = 0;
1132 
1133  if( ss_size > 2 )
1134  {
1135  // if the ss_size is smaller than or equal to 2
1136  // there is no sense to set x1size (and others) to another values
1137 
1138  for(x1size=ss_size ; x1size>0 && ss1[x1size-1]==0 ; --x1size);
1139  for(x2size=ss_size ; x2size>0 && ss2[x2size-1]==0 ; --x2size);
1140 
1141  for(x1start=0 ; x1start<x1size && ss1[x1start]==0 ; ++x1start);
1142  for(x2start=0 ; x2start<x2size && ss2[x2start]==0 ; ++x2start);
1143  }
1144 
1145  Mul2Big3<ss_size>(ss1, ss2, result, x1start, x1size, x2start, x2size);
1146  }
1147 
1148 
1149 
1153  template<uint ss_size>
1154  void Mul2Big3(const uint * ss1, const uint * ss2, UInt<ss_size*2> & result, uint x1start, uint x1size, uint x2start, uint x2size)
1155  {
1156  uint r2, r1;
1157 
1158  result.SetZero();
1159 
1160  if( x1size==0 || x2size==0 )
1161  return;
1162 
1163  for(uint x1=x1start ; x1<x1size ; ++x1)
1164  {
1165  for(uint x2=x2start ; x2<x2size ; ++x2)
1166  {
1167  MulTwoWords(ss1[x1], ss2[x2], &r2, &r1);
1168  result.AddTwoInts(r2, r1, x2+x1);
1169  // here will never be a carry
1170  }
1171  }
1172  }
1173 
1174 
1175 public:
1176 
1177 
1204  {
1205  UInt<value_size*2> result;
1206  uint i, c = 0;
1207 
1208  Mul3Big(ss2, result);
1209 
1210  // copying result
1211  for(i=0 ; i<value_size ; ++i)
1212  table[i] = result.table[i];
1213 
1214  // testing carry
1215  for( ; i<value_size*2 ; ++i)
1216  if( result.table[i] != 0 )
1217  {
1218  c = 1;
1219  break;
1220  }
1221 
1222  TTMATH_LOGC("UInt::Mul3", c)
1223 
1224  return c;
1225  }
1226 
1227 
1228 
1236  void Mul3Big(const UInt<value_size> & ss2, UInt<value_size*2> & result)
1237  {
1238  Mul3Big2<value_size>(table, ss2.table, result.table);
1239 
1240  TTMATH_LOG("UInt::Mul3Big")
1241  }
1242 
1243 
1244 
1245 private:
1246 
1252  template<uint ss_size>
1253  void Mul3Big2(const uint * ss1, const uint * ss2, uint * result)
1254  {
1255  const uint * x1, * x0, * y1, * y0;
1256 
1257 
1258  if( ss_size>1 && ss_size<TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE )
1259  {
1260  UInt<ss_size*2> res;
1261  Mul2Big2<ss_size>(ss1, ss2, res);
1262 
1263 #ifdef __clang__
1264 #pragma clang diagnostic push
1265 #pragma clang diagnostic ignored "-Wtautological-compare"
1266 #endif
1267 
1268  for(uint i=0 ; i<ss_size*2 ; ++i)
1269  result[i] = res.table[i];
1270 
1271 #ifdef __clang__
1272 #pragma clang diagnostic pop
1273 #endif
1274 
1275  return;
1276  }
1277  else
1278  if( ss_size == 1 )
1279  {
1280  return MulTwoWords(*ss1, *ss2, &result[1], &result[0]);
1281  }
1282 
1283 
1284  if( (ss_size & 1) == 1 )
1285  {
1286  // ss_size is odd
1287  x0 = ss1;
1288  y0 = ss2;
1289  x1 = ss1 + ss_size / 2 + 1;
1290  y1 = ss2 + ss_size / 2 + 1;
1291 
1292  // the second vectors (x1 and y1) are smaller about one from the first ones (x0 and y0)
1293  Mul3Big3<ss_size/2 + 1, ss_size/2, ss_size*2>(x1, x0, y1, y0, result);
1294  }
1295  else
1296  {
1297  // ss_size is even
1298  x0 = ss1;
1299  y0 = ss2;
1300  x1 = ss1 + ss_size / 2;
1301  y1 = ss2 + ss_size / 2;
1302 
1303  // all four vectors (x0 x1 y0 y1) are equal in size
1304  Mul3Big3<ss_size/2, ss_size/2, ss_size*2>(x1, x0, y1, y0, result);
1305  }
1306  }
1307 
1308 
1309 
1310 #ifdef _MSC_VER
1311 #pragma warning (disable : 4717)
1312 //warning C4717: recursive on all control paths, function will cause runtime stack overflow
1313 //we have the stop point in Mul3Big2() method
1314 #endif
1315 
1316 
1332  template<uint first_size, uint second_size, uint result_size>
1333  void Mul3Big3(const uint * x1, const uint * x0, const uint * y1, const uint * y0, uint * result)
1334  {
1335  uint i, c, xc, yc;
1336 
1337  UInt<first_size> temp, temp2;
1338  UInt<first_size*3> z1;
1339 
1340  // z0 and z2 we store directly in the result (we don't use any temporary variables)
1341  Mul3Big2<first_size>(x0, y0, result); // z0
1342  Mul3Big2<second_size>(x1, y1, result+first_size*2); // z2
1343 
1344  // now we calculate z1
1345  // temp = (x0 + x1)
1346  // temp2 = (y0 + y1)
1347  // we're using temp and temp2 with UInt<first_size>, although there can be a carry but
1348  // we simple remember it in xc and yc (xc and yc can be either 0 or 1),
1349  // and (x0 + x1)*(y0 + y1) we calculate in this way (schoolbook algorithm):
1350  //
1351  // xc | temp
1352  // yc | temp2
1353  // --------------------
1354  // (temp * temp2)
1355  // xc*temp2 |
1356  // yc*temp |
1357  // xc*yc |
1358  // ---------- z1 --------
1359  //
1360  // and the result is never larger in size than 3*first_size
1361 
1362  xc = AddVector(x0, x1, first_size, second_size, temp.table);
1363  yc = AddVector(y0, y1, first_size, second_size, temp2.table);
1364 
1365  Mul3Big2<first_size>(temp.table, temp2.table, z1.table);
1366 
1367 #ifdef __clang__
1368 #pragma clang diagnostic push
1369 #pragma clang diagnostic ignored "-Wtautological-compare"
1370 #endif
1371 
1372  // clearing the rest of z1
1373  for(i=first_size*2 ; i<first_size*3 ; ++i)
1374  z1.table[i] = 0;
1375 
1376 #ifdef __clang__
1377 #pragma clang diagnostic pop
1378 #endif
1379 
1380  if( xc )
1381  {
1382  c = AddVector(z1.table+first_size, temp2.table, first_size*3-first_size, first_size, z1.table+first_size);
1383  TTMATH_ASSERT( c==0 )
1384  }
1385 
1386  if( yc )
1387  {
1388  c = AddVector(z1.table+first_size, temp.table, first_size*3-first_size, first_size, z1.table+first_size);
1389  TTMATH_ASSERT( c==0 )
1390  }
1391 
1392 
1393  if( xc && yc )
1394  {
1395 #ifdef __clang__
1396 #pragma clang diagnostic push
1397 #pragma clang diagnostic ignored "-Wtautological-compare"
1398 #endif
1399 
1400  for( i=first_size*2 ; i<first_size*3 ; ++i )
1401  if( ++z1.table[i] != 0 )
1402  break; // break if there was no carry
1403 
1404 #ifdef __clang__
1405 #pragma clang diagnostic pop
1406 #endif
1407  }
1408 
1409  // z1 = z1 - z2
1410  c = SubVector(z1.table, result+first_size*2, first_size*3, second_size*2, z1.table);
1411  TTMATH_ASSERT(c==0)
1412 
1413  // z1 = z1 - z0
1414  c = SubVector(z1.table, result, first_size*3, first_size*2, z1.table);
1415  TTMATH_ASSERT(c==0)
1416 
1417  // here we've calculated the z1
1418  // now we're adding it to the result
1419 
1420  if( first_size > second_size )
1421  {
1422  uint z1_size = result_size - first_size;
1423  TTMATH_ASSERT( z1_size <= first_size*3 )
1424 
1425 #ifdef __clang__
1426 #pragma clang diagnostic push
1427 #pragma clang diagnostic ignored "-Wtautological-compare"
1428 #endif
1429 
1430  for(i=z1_size ; i<first_size*3 ; ++i)
1431  {
1432  TTMATH_ASSERT( z1.table[i] == 0 )
1433  }
1434 
1435 #ifdef __clang__
1436 #pragma clang diagnostic pop
1437 #endif
1438 
1439  c = AddVector(result+first_size, z1.table, result_size-first_size, z1_size, result+first_size);
1440  TTMATH_ASSERT(c==0)
1441  }
1442  else
1443  {
1444  c = AddVector(result+first_size, z1.table, result_size-first_size, first_size*3, result+first_size);
1445  TTMATH_ASSERT(c==0)
1446  }
1447  }
1448 
1449 
1450 
1451 #ifdef _MSC_VER
1452 #pragma warning (default : 4717)
1453 #endif
1454 
1455 
1456 public:
1457 
1458 
1463  {
1464  UInt<value_size*2> result;
1465  uint i, c = 0;
1466 
1467  MulFastestBig(ss2, result);
1468 
1469  // copying result
1470  for(i=0 ; i<value_size ; ++i)
1471  table[i] = result.table[i];
1472 
1473  // testing carry
1474  for( ; i<value_size*2 ; ++i)
1475  if( result.table[i] != 0 )
1476  {
1477  c = 1;
1478  break;
1479  }
1480 
1481  TTMATH_LOGC("UInt::MulFastest", c)
1482 
1483  return c;
1484  }
1485 
1486 
1494  {
1496  return Mul2Big(ss2, result);
1497 
1498  uint x1size = value_size, x2size = value_size;
1499  uint x1start = 0, x2start = 0;
1500 
1501  for(x1size=value_size ; x1size>0 && table[x1size-1]==0 ; --x1size);
1502  for(x2size=value_size ; x2size>0 && ss2.table[x2size-1]==0 ; --x2size);
1503 
1504  if( x1size==0 || x2size==0 )
1505  {
1506  // either 'this' or 'ss2' is equal zero - the result is zero too
1507  result.SetZero();
1508  return;
1509  }
1510 
1511  for(x1start=0 ; x1start<x1size && table[x1start]==0 ; ++x1start);
1512  for(x2start=0 ; x2start<x2size && ss2.table[x2start]==0 ; ++x2start);
1513 
1514  uint distancex1 = x1size - x1start;
1515  uint distancex2 = x2size - x2start;
1516 
1517  if( distancex1 < 3 || distancex2 < 3 )
1518  // either 'this' or 'ss2' have only 2 (or 1) items different from zero (side by side)
1519  // (this condition in the future can be improved)
1520  return Mul2Big3<value_size>(table, ss2.table, result, x1start, x1size, x2start, x2size);
1521 
1522 
1523  // Karatsuba multiplication
1524  Mul3Big(ss2, result);
1525 
1526  TTMATH_LOG("UInt::MulFastestBig")
1527  }
1528 
1529 
1537 public:
1538 
1539 
1545  uint DivInt(uint divisor, uint * remainder = 0)
1546  {
1547  if( divisor == 0 )
1548  {
1549  if( remainder )
1550  *remainder = 0; // this is for convenience, without it the compiler can report that 'remainder' is uninitialized
1551 
1552  TTMATH_LOG("UInt::DivInt")
1553 
1554  return 1;
1555  }
1556 
1557  if( divisor == 1 )
1558  {
1559  if( remainder )
1560  *remainder = 0;
1561 
1562  TTMATH_LOG("UInt::DivInt")
1563 
1564  return 0;
1565  }
1566 
1567  UInt<value_size> dividend(*this);
1568  SetZero();
1569 
1570  sint i; // i must be with a sign
1571  uint r = 0;
1572 
1573  // we're looking for the last word in ss1
1574  for(i=value_size-1 ; i>0 && dividend.table[i]==0 ; --i);
1575 
1576  for( ; i>=0 ; --i)
1577  DivTwoWords(r, dividend.table[i], divisor, &table[i], &r);
1578 
1579  if( remainder )
1580  *remainder = r;
1581 
1582  TTMATH_LOG("UInt::DivInt")
1583 
1584  return 0;
1585  }
1586 
1587  uint DivInt(uint divisor, uint & remainder)
1588  {
1589  return DivInt(divisor, &remainder);
1590  }
1591 
1592 
1593 
1603  uint Div( const UInt<value_size> & divisor,
1604  UInt<value_size> * remainder = 0,
1605  uint algorithm = 3)
1606  {
1607  switch( algorithm )
1608  {
1609  case 1:
1610  return Div1(divisor, remainder);
1611 
1612  case 2:
1613  return Div2(divisor, remainder);
1614 
1615  case 3:
1616  default:
1617  return Div3(divisor, remainder);
1618  }
1619  }
1620 
1621  uint Div(const UInt<value_size> & divisor, UInt<value_size> & remainder, uint algorithm = 3)
1622  {
1623  return Div(divisor, &remainder, algorithm);
1624  }
1625 
1626 
1627 
1628 private:
1629 
1636  uint Div_StandardTest( const UInt<value_size> & v,
1637  uint & m, uint & n,
1638  UInt<value_size> * remainder = 0)
1639  {
1640  switch( Div_CalculatingSize(v, m, n) )
1641  {
1642  case 4: // 'this' is equal v
1643  if( remainder )
1644  remainder->SetZero();
1645 
1646  SetOne();
1647  TTMATH_LOG("UInt::Div_StandardTest")
1648  return 0;
1649 
1650  case 3: // 'this' is smaller than v
1651  if( remainder )
1652  *remainder = *this;
1653 
1654  SetZero();
1655  TTMATH_LOG("UInt::Div_StandardTest")
1656  return 0;
1657 
1658  case 2: // 'this' is zero
1659  if( remainder )
1660  remainder->SetZero();
1661 
1662  SetZero();
1663  TTMATH_LOG("UInt::Div_StandardTest")
1664  return 0;
1665 
1666  case 1: // v is zero
1667  TTMATH_LOG("UInt::Div_StandardTest")
1668  return 1;
1669  }
1670 
1671  TTMATH_LOG("UInt::Div_StandardTest")
1672 
1673  return 2;
1674  }
1675 
1676 
1677 
1690  uint Div_CalculatingSize(const UInt<value_size> & v, uint & m, uint & n)
1691  {
1692  m = n = value_size-1;
1693 
1694  for( ; n!=0 && v.table[n]==0 ; --n);
1695 
1696  if( n==0 && v.table[n]==0 )
1697  return 1;
1698 
1699  for( ; m!=0 && table[m]==0 ; --m);
1700 
1701  if( m==0 && table[m]==0 )
1702  return 2;
1703 
1704  if( m < n )
1705  return 3;
1706  else
1707  if( m == n )
1708  {
1709  uint i;
1710  for(i = n ; i!=0 && table[i]==v.table[i] ; --i);
1711 
1712  if( table[i] < v.table[i] )
1713  return 3;
1714  else
1715  if (table[i] == v.table[i] )
1716  return 4;
1717  }
1718 
1719  return 0;
1720  }
1721 
1722 
1723 public:
1724 
1729  uint Div1(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0)
1730  {
1731  uint m,n, test;
1732 
1733  test = Div_StandardTest(divisor, m, n, remainder);
1734  if( test < 2 )
1735  return test;
1736 
1737  if( !remainder )
1738  {
1739  UInt<value_size> rem;
1740 
1741  return Div1_Calculate(divisor, rem);
1742  }
1743 
1744  return Div1_Calculate(divisor, *remainder);
1745  }
1746 
1747 
1752  uint Div1(const UInt<value_size> & divisor, UInt<value_size> & remainder)
1753  {
1754  return Div1(divisor, &remainder);
1755  }
1756 
1757 
1758 private:
1759 
1760  uint Div1_Calculate(const UInt<value_size> & divisor, UInt<value_size> & rest)
1761  {
1762  if( this == &divisor )
1763  {
1764  UInt<value_size> divisor_copy(divisor);
1765  return Div1_CalculateRef(divisor_copy, rest);
1766  }
1767  else
1768  {
1769  return Div1_CalculateRef(divisor, rest);
1770  }
1771  }
1772 
1773 
1774  uint Div1_CalculateRef(const UInt<value_size> & divisor, UInt<value_size> & rest)
1775  {
1776  TTMATH_REFERENCE_ASSERT( divisor )
1777 
1778  sint loop;
1779  sint c;
1780 
1781  rest.SetZero();
1782  loop = value_size * TTMATH_BITS_PER_UINT;
1783  c = 0;
1784 
1785 
1786  div_a:
1787  c = Rcl(1, c);
1788  c = rest.Add(rest,c);
1789  c = rest.Sub(divisor,c);
1790 
1791  c = !c;
1792 
1793  if(!c)
1794  goto div_d;
1795 
1796 
1797  div_b:
1798  --loop;
1799  if(loop)
1800  goto div_a;
1801 
1802  c = Rcl(1, c);
1803  TTMATH_LOG("UInt::Div1_Calculate")
1804  return 0;
1805 
1806 
1807  div_c:
1808  c = Rcl(1, c);
1809  c = rest.Add(rest,c);
1810  c = rest.Add(divisor);
1811 
1812  if(c)
1813  goto div_b;
1814 
1815 
1816  div_d:
1817  --loop;
1818  if(loop)
1819  goto div_c;
1820 
1821  c = Rcl(1, c);
1822  c = rest.Add(divisor);
1823 
1824  TTMATH_LOG("UInt::Div1_Calculate")
1825 
1826  return 0;
1827  }
1828 
1829 
1830 public:
1831 
1839  uint Div2(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0)
1840  {
1841  if( this == &divisor )
1842  {
1843  UInt<value_size> divisor_copy(divisor);
1844  return Div2Ref(divisor_copy, remainder);
1845  }
1846  else
1847  {
1848  return Div2Ref(divisor, remainder);
1849  }
1850  }
1851 
1852 
1860  uint Div2(const UInt<value_size> & divisor, UInt<value_size> & remainder)
1861  {
1862  return Div2(divisor, &remainder);
1863  }
1864 
1865 
1866 private:
1867 
1875  uint Div2Ref(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0)
1876  {
1877  uint bits_diff;
1878  uint status = Div2_Calculate(divisor, remainder, bits_diff);
1879  if( status < 2 )
1880  return status;
1881 
1882  if( CmpBiggerEqual(divisor) )
1883  {
1884  Div2(divisor, remainder);
1885  SetBit(bits_diff);
1886  }
1887  else
1888  {
1889  if( remainder )
1890  *remainder = *this;
1891 
1892  SetZero();
1893  SetBit(bits_diff);
1894  }
1895 
1896  TTMATH_LOG("UInt::Div2")
1897 
1898  return 0;
1899  }
1900 
1901 
1909  uint Div2_Calculate(const UInt<value_size> & divisor, UInt<value_size> * remainder,
1910  uint & bits_diff)
1911  {
1912  uint table_id, index;
1913  uint divisor_table_id, divisor_index;
1914 
1915  uint status = Div2_FindLeadingBitsAndCheck( divisor, remainder,
1916  table_id, index,
1917  divisor_table_id, divisor_index);
1918 
1919  if( status < 2 )
1920  {
1921  TTMATH_LOG("UInt::Div2_Calculate")
1922  return status;
1923  }
1924 
1925  // here we know that 'this' is greater than divisor
1926  // then 'index' is greater or equal 'divisor_index'
1927  bits_diff = index - divisor_index;
1928 
1929  UInt<value_size> divisor_copy(divisor);
1930  divisor_copy.Rcl(bits_diff, 0);
1931 
1932  if( CmpSmaller(divisor_copy, table_id) )
1933  {
1934  divisor_copy.Rcr(1);
1935  --bits_diff;
1936  }
1937 
1938  Sub(divisor_copy, 0);
1939 
1940  TTMATH_LOG("UInt::Div2_Calculate")
1941 
1942  return 2;
1943  }
1944 
1945 
1952  uint Div2_FindLeadingBitsAndCheck( const UInt<value_size> & divisor,
1953  UInt<value_size> * remainder,
1954  uint & table_id, uint & index,
1955  uint & divisor_table_id, uint & divisor_index)
1956  {
1957  if( !divisor.FindLeadingBit(divisor_table_id, divisor_index) )
1958  {
1959  // division by zero
1960  TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
1961  return 1;
1962  }
1963 
1964  if( !FindLeadingBit(table_id, index) )
1965  {
1966  // zero is divided by something
1967 
1968  SetZero();
1969 
1970  if( remainder )
1971  remainder->SetZero();
1972 
1973  TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
1974 
1975  return 0;
1976  }
1977 
1978  divisor_index += divisor_table_id * TTMATH_BITS_PER_UINT;
1979  index += table_id * TTMATH_BITS_PER_UINT;
1980 
1981  if( divisor_table_id == 0 )
1982  {
1983  // dividor has only one 32-bit word
1984 
1985  uint r;
1986  DivInt(divisor.table[0], &r);
1987 
1988  if( remainder )
1989  {
1990  remainder->SetZero();
1991  remainder->table[0] = r;
1992  }
1993 
1994  TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
1995 
1996  return 0;
1997  }
1998 
1999 
2000  if( Div2_DivisorGreaterOrEqual( divisor, remainder,
2001  table_id, index,
2002  divisor_index) )
2003  {
2004  TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
2005  return 0;
2006  }
2007 
2008 
2009  TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
2010 
2011  return 2;
2012  }
2013 
2014 
2019  bool Div2_DivisorGreaterOrEqual( const UInt<value_size> & divisor,
2020  UInt<value_size> * remainder,
2021  uint table_id, uint index,
2022  uint divisor_index )
2023  {
2024  if( divisor_index > index )
2025  {
2026  // divisor is greater than this
2027 
2028  if( remainder )
2029  *remainder = *this;
2030 
2031  SetZero();
2032 
2033  TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
2034 
2035  return true;
2036  }
2037 
2038  if( divisor_index == index )
2039  {
2040  // table_id == divisor_table_id as well
2041 
2042  uint i;
2043  for(i = table_id ; i!=0 && table[i]==divisor.table[i] ; --i);
2044 
2045  if( table[i] < divisor.table[i] )
2046  {
2047  // divisor is greater than 'this'
2048 
2049  if( remainder )
2050  *remainder = *this;
2051 
2052  SetZero();
2053 
2054  TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
2055 
2056  return true;
2057  }
2058  else
2059  if( table[i] == divisor.table[i] )
2060  {
2061  // divisor is equal 'this'
2062 
2063  if( remainder )
2064  remainder->SetZero();
2065 
2066  SetOne();
2067 
2068  TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
2069 
2070  return true;
2071  }
2072  }
2073 
2074  TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
2075 
2076  return false;
2077  }
2078 
2079 
2080 public:
2081 
2085  uint Div3(const UInt<value_size> & ss2, UInt<value_size> * remainder = 0)
2086  {
2087  if( this == &ss2 )
2088  {
2089  UInt<value_size> copy_ss2(ss2);
2090  return Div3Ref(copy_ss2, remainder);
2091  }
2092  else
2093  {
2094  return Div3Ref(ss2, remainder);
2095  }
2096  }
2097 
2098 
2102  uint Div3(const UInt<value_size> & ss2, UInt<value_size> & remainder)
2103  {
2104  return Div3(ss2, &remainder);
2105  }
2106 
2107 
2108 private:
2109 
2118  uint Div3Ref(const UInt<value_size> & v, UInt<value_size> * remainder = 0)
2119  {
2120  uint m,n, test;
2121 
2122  test = Div_StandardTest(v, m, n, remainder);
2123  if( test < 2 )
2124  return test;
2125 
2126  if( n == 0 )
2127  {
2128  uint r;
2129  DivInt( v.table[0], &r );
2130 
2131  if( remainder )
2132  {
2133  remainder->SetZero();
2134  remainder->table[0] = r;
2135  }
2136 
2137  TTMATH_LOG("UInt::Div3")
2138 
2139  return 0;
2140  }
2141 
2142 
2143  // we can only use the third division algorithm when
2144  // the divisor is greater or equal 2^32 (has more than one 32-bit word)
2145  ++m;
2146  ++n;
2147  m = m - n;
2148  Div3_Division(v, remainder, m, n);
2149 
2150  TTMATH_LOG("UInt::Div3")
2151 
2152  return 0;
2153  }
2154 
2155 
2156 
2157 private:
2158 
2159 
2160  void Div3_Division(UInt<value_size> v, UInt<value_size> * remainder, uint m, uint n)
2161  {
2162  TTMATH_ASSERT( n>=2 )
2163 
2164  UInt<value_size+1> uu, vv;
2165  UInt<value_size> q;
2166  uint d, u_value_size, u0, u1, u2, v1, v0, j=m;
2167 
2168  u_value_size = Div3_Normalize(v, n, d);
2169 
2170  if( j+n == value_size )
2171  u2 = u_value_size;
2172  else
2173  u2 = table[j+n];
2174 
2175  Div3_MakeBiggerV(v, vv);
2176 
2177  for(uint i = j+1 ; i<value_size ; ++i)
2178  q.table[i] = 0;
2179 
2180  while( true )
2181  {
2182  u1 = table[j+n-1];
2183  u0 = table[j+n-2];
2184  v1 = v.table[n-1];
2185  v0 = v.table[n-2];
2186 
2187  uint qp = Div3_Calculate(u2,u1,u0, v1,v0);
2188 
2189  Div3_MakeNewU(uu, j, n, u2);
2190  Div3_MultiplySubtract(uu, vv, qp);
2191  Div3_CopyNewU(uu, j, n);
2192 
2193  q.table[j] = qp;
2194 
2195  // the next loop
2196  if( j-- == 0 )
2197  break;
2198 
2199  u2 = table[j+n];
2200  }
2201 
2202  if( remainder )
2203  Div3_Unnormalize(remainder, n, d);
2204 
2205  *this = q;
2206 
2207  TTMATH_LOG("UInt::Div3_Division")
2208  }
2209 
2210 
2211  void Div3_MakeNewU(UInt<value_size+1> & uu, uint j, uint n, uint u_max)
2212  {
2213  uint i;
2214 
2215  for(i=0 ; i<n ; ++i, ++j)
2216  uu.table[i] = table[j];
2217 
2218  // 'n' is from <1..value_size> so and 'i' is from <0..value_size>
2219  // then table[i] is always correct (look at the declaration of 'uu')
2220  uu.table[i] = u_max;
2221 
2222  for( ++i ; i<value_size+1 ; ++i)
2223  uu.table[i] = 0;
2224 
2225  TTMATH_LOG("UInt::Div3_MakeNewU")
2226  }
2227 
2228 
2229  void Div3_CopyNewU(const UInt<value_size+1> & uu, uint j, uint n)
2230  {
2231  uint i;
2232 
2233  for(i=0 ; i<n ; ++i)
2234  table[i+j] = uu.table[i];
2235 
2236  if( i+j < value_size )
2237  table[i+j] = uu.table[i];
2238 
2239  TTMATH_LOG("UInt::Div3_CopyNewU")
2240  }
2241 
2242 
2247  void Div3_MakeBiggerV(const UInt<value_size> & v, UInt<value_size+1> & vv)
2248  {
2249  for(uint i=0 ; i<value_size ; ++i)
2250  vv.table[i] = v.table[i];
2251 
2252  vv.table[value_size] = 0;
2253 
2254  TTMATH_LOG("UInt::Div3_MakeBiggerV")
2255  }
2256 
2257 
2267  uint Div3_Normalize(UInt<value_size> & v, uint n, uint & d)
2268  {
2269  // v.table[n-1] is != 0
2270 
2271  uint bit = (uint)FindLeadingBitInWord(v.table[n-1]);
2272  uint move = (TTMATH_BITS_PER_UINT - bit - 1);
2273  uint res = table[value_size-1];
2274  d = move;
2275 
2276  if( move > 0 )
2277  {
2278  v.Rcl(move, 0);
2279  Rcl(move, 0);
2280  res = res >> (bit + 1);
2281  }
2282  else
2283  {
2284  res = 0;
2285  }
2286 
2287  TTMATH_LOG("UInt::Div3_Normalize")
2288 
2289  return res;
2290  }
2291 
2292 
2293  void Div3_Unnormalize(UInt<value_size> * remainder, uint n, uint d)
2294  {
2295  for(uint i=n ; i<value_size ; ++i)
2296  table[i] = 0;
2297 
2298  Rcr(d,0);
2299 
2300  *remainder = *this;
2301 
2302  TTMATH_LOG("UInt::Div3_Unnormalize")
2303  }
2304 
2305 
2306  uint Div3_Calculate(uint u2, uint u1, uint u0, uint v1, uint v0)
2307  {
2308  UInt<2> u_temp;
2309  uint rp;
2310  bool next_test;
2311 
2312  TTMATH_ASSERT( v1 != 0 )
2313 
2314  u_temp.table[1] = u2;
2315  u_temp.table[0] = u1;
2316  u_temp.DivInt(v1, &rp);
2317 
2318  TTMATH_ASSERT( u_temp.table[1]==0 || u_temp.table[1]==1 )
2319 
2320  do
2321  {
2322  bool decrease = false;
2323 
2324  if( u_temp.table[1] == 1 )
2325  decrease = true;
2326  else
2327  {
2328  UInt<2> temp1, temp2;
2329 
2330  UInt<2>::MulTwoWords(u_temp.table[0], v0, temp1.table+1, temp1.table);
2331  temp2.table[1] = rp;
2332  temp2.table[0] = u0;
2333 
2334  if( temp1 > temp2 )
2335  decrease = true;
2336  }
2337 
2338  next_test = false;
2339 
2340  if( decrease )
2341  {
2342  u_temp.SubOne();
2343 
2344  rp += v1;
2345 
2346  if( rp >= v1 ) // it means that there wasn't a carry (r<b from the book)
2347  next_test = true;
2348  }
2349  }
2350  while( next_test );
2351 
2352  TTMATH_LOG("UInt::Div3_Calculate")
2353 
2354  return u_temp.table[0];
2355  }
2356 
2357 
2358 
2359  void Div3_MultiplySubtract( UInt<value_size+1> & uu,
2360  const UInt<value_size+1> & vv, uint & qp)
2361  {
2362  // D4 (in the book)
2363 
2364  UInt<value_size+1> vv_temp(vv);
2365  vv_temp.MulInt(qp);
2366 
2367  if( uu.Sub(vv_temp) )
2368  {
2369  // there was a carry
2370 
2371  //
2372  // !!! this part of code was not tested
2373  //
2374 
2375  --qp;
2376  uu.Add(vv);
2377 
2378  // can be a carry from this additions but it should be ignored
2379  // because it cancels with the borrow from uu.Sub(vv_temp)
2380  }
2381 
2382  TTMATH_LOG("UInt::Div3_MultiplySubtract")
2383  }
2384 
2385 
2386 
2387 
2388 
2389 
2390 public:
2391 
2392 
2403  {
2404  if(pow.IsZero() && IsZero())
2405  // we don't define zero^zero
2406  return 2;
2407 
2408  UInt<value_size> start(*this);
2409  UInt<value_size> result;
2410  result.SetOne();
2411  uint c = 0;
2412 
2413  while( !c )
2414  {
2415  if( pow.table[0] & 1 )
2416  c += result.Mul(start);
2417 
2418  pow.Rcr2_one(0);
2419  if( pow.IsZero() )
2420  break;
2421 
2422  c += start.Mul(start);
2423  }
2424 
2425  *this = result;
2426 
2427  TTMATH_LOGC("UInt::Pow(UInt<>)", c)
2428 
2429  return (c==0)? 0 : 1;
2430  }
2431 
2432 
2438  void Sqrt()
2439  {
2440  UInt<value_size> bit, temp;
2441 
2442  if( IsZero() )
2443  return;
2444 
2445  UInt<value_size> value(*this);
2446 
2447  SetZero();
2448  bit.SetZero();
2449  bit.table[value_size-1] = (TTMATH_UINT_HIGHEST_BIT >> 1);
2450 
2451  while( bit > value )
2452  bit.Rcr(2);
2453 
2454  while( !bit.IsZero() )
2455  {
2456  temp = *this;
2457  temp.Add(bit);
2458 
2459  if( value >= temp )
2460  {
2461  value.Sub(temp);
2462  Rcr(1);
2463  Add(bit);
2464  }
2465  else
2466  {
2467  Rcr(1);
2468  }
2469 
2470  bit.Rcr(2);
2471  }
2472 
2473  TTMATH_LOG("UInt::Sqrt")
2474  }
2475 
2476 
2477 
2485  {
2486  if( n >= value_size*TTMATH_BITS_PER_UINT )
2487  {
2488  SetZero();
2489  TTMATH_LOG("UInt::ClearFirstBits")
2490  return;
2491  }
2492 
2493  uint * p = table;
2494 
2495  // first we're clearing the whole words
2496  while( n >= TTMATH_BITS_PER_UINT )
2497  {
2498  *p++ = 0;
2499  n -= TTMATH_BITS_PER_UINT;
2500  }
2501 
2502  if( n == 0 )
2503  {
2504  TTMATH_LOG("UInt::ClearFirstBits")
2505  return;
2506  }
2507 
2508  // and then we're clearing one word which has left
2509  // mask -- all bits are set to one
2510  uint mask = TTMATH_UINT_MAX_VALUE;
2511 
2512  mask = mask << n;
2513 
2514  (*p) &= mask;
2515 
2516  TTMATH_LOG("UInt::ClearFirstBits")
2517  }
2518 
2519 
2523  bool IsTheHighestBitSet() const
2524  {
2525  return (table[value_size-1] & TTMATH_UINT_HIGHEST_BIT) != 0;
2526  }
2527 
2528 
2532  bool IsTheLowestBitSet() const
2533  {
2534  return (*table & 1) != 0;
2535  }
2536 
2537 
2542  {
2543 #ifdef __clang__
2544 #pragma clang diagnostic push
2545 #pragma clang diagnostic ignored "-Wtautological-compare"
2546 #endif
2547 
2548  for(uint i=0 ; i<value_size-1 ; ++i)
2549  if( table[i] != 0 )
2550  return false;
2551 
2552 #ifdef __clang__
2553 #pragma clang diagnostic pop
2554 #endif
2555  if( table[value_size-1] != TTMATH_UINT_HIGHEST_BIT )
2556  return false;
2557 
2558  return true;
2559  }
2560 
2561 
2566  {
2567  if( table[0] != 1 )
2568  return false;
2569 
2570  for(uint i=1 ; i<value_size ; ++i)
2571  if( table[i] != 0 )
2572  return false;
2573 
2574  return true;
2575  }
2576 
2577 
2581  bool IsZero() const
2582  {
2583  for(uint i=0 ; i<value_size ; ++i)
2584  if(table[i] != 0)
2585  return false;
2586 
2587  return true;
2588  }
2589 
2590 
2594  bool AreFirstBitsZero(uint bits) const
2595  {
2596  TTMATH_ASSERT( bits <= value_size * TTMATH_BITS_PER_UINT )
2597 
2598  uint index = bits / TTMATH_BITS_PER_UINT;
2599  uint rest = bits % TTMATH_BITS_PER_UINT;
2600  uint i;
2601 
2602  for(i=0 ; i<index ; ++i)
2603  if(table[i] != 0 )
2604  return false;
2605 
2606  if( rest == 0 )
2607  return true;
2608 
2609  uint mask = TTMATH_UINT_MAX_VALUE >> (TTMATH_BITS_PER_UINT - rest);
2610 
2611  return (table[i] & mask) == 0;
2612  }
2613 
2614 
2615 
2632  template<uint argument_size>
2634  {
2635  uint min_size = (value_size < argument_size)? value_size : argument_size;
2636  uint i;
2637 
2638  for(i=0 ; i<min_size ; ++i)
2639  table[i] = p.table[i];
2640 
2641 
2642  if( value_size > argument_size )
2643  {
2644  // 'this' is longer than 'p'
2645 
2646  for( ; i<value_size ; ++i)
2647  table[i] = 0;
2648  }
2649  else
2650  {
2651  for( ; i<argument_size ; ++i)
2652  if( p.table[i] != 0 )
2653  {
2654  TTMATH_LOGC("UInt::FromUInt(UInt<>)", 1)
2655  return 1;
2656  }
2657  }
2658 
2659  TTMATH_LOGC("UInt::FromUInt(UInt<>)", 0)
2660 
2661  return 0;
2662  }
2663 
2664 
2673  template<uint argument_size>
2675  {
2676  return FromUInt(p);
2677  }
2678 
2679 
2684  {
2685  for(uint i=1 ; i<value_size ; ++i)
2686  table[i] = 0;
2687 
2688  table[0] = value;
2689 
2690  TTMATH_LOG("UInt::FromUInt(uint)")
2691 
2692  // there'll never be a carry here
2693  return 0;
2694  }
2695 
2696 
2701  {
2702  return FromUInt(value);
2703  }
2704 
2705 
2710  {
2711  uint c = FromUInt(uint(value));
2712 
2713  if( c || value < 0 )
2714  return 1;
2715 
2716  return 0;
2717  }
2718 
2719 
2725  template<uint argument_size>
2727  {
2728  FromUInt(p);
2729 
2730  return *this;
2731  }
2732 
2733 
2738  {
2739  for(uint i=0 ; i<value_size ; ++i)
2740  table[i] = p.table[i];
2741 
2742  TTMATH_LOG("UInt::operator=(UInt<>)")
2743 
2744  return *this;
2745  }
2746 
2747 
2752  {
2753  FromUInt(i);
2754 
2755  return *this;
2756  }
2757 
2758 
2763  {
2764  FromUInt(i);
2765  }
2766 
2767 
2772  {
2773  FromInt(i);
2774 
2775  return *this;
2776  }
2777 
2778 
2785  {
2786  FromInt(i);
2787  }
2788 
2789 
2790 #ifdef TTMATH_PLATFORM32
2791 
2792 
2798  {
2799  table[0] = (uint)n;
2800 
2801  if( value_size == 1 )
2802  {
2803  uint c = ((n >> TTMATH_BITS_PER_UINT) == 0) ? 0 : 1;
2804 
2805  TTMATH_LOGC("UInt::FromUInt(ulint)", c)
2806  return c;
2807  }
2808 
2809  table[1] = (uint)(n >> TTMATH_BITS_PER_UINT);
2810 
2811  for(uint i=2 ; i<value_size ; ++i)
2812  table[i] = 0;
2813 
2814  TTMATH_LOG("UInt::FromUInt(ulint)")
2815 
2816  return 0;
2817  }
2818 
2819 
2825  {
2826  return FromUInt(n);
2827  }
2828 
2829 
2835  {
2836  uint c = FromUInt(ulint(n));
2837 
2838  if( c || n < 0 )
2839  return 1;
2840 
2841  return 0;
2842  }
2843 
2844 
2850  {
2851  FromUInt(n);
2852 
2853  return *this;
2854  }
2855 
2856 
2862  {
2863  FromUInt(n);
2864  }
2865 
2866 
2872  {
2873  FromInt(n);
2874 
2875  return *this;
2876  }
2877 
2878 
2884  {
2885  FromInt(n);
2886  }
2887 
2888 #endif
2889 
2890 
2891 
2892 #ifdef TTMATH_PLATFORM64
2893 
2894 
2899  uint FromUInt(unsigned int i)
2900  {
2901  return FromUInt(uint(i));
2902  }
2903 
2908  uint FromInt(unsigned int i)
2909  {
2910  return FromUInt(uint(i));
2911  }
2912 
2913 
2918  uint FromInt(signed int i)
2919  {
2920  return FromInt(sint(i));
2921  }
2922 
2923 
2928  UInt<value_size> & operator=(unsigned int i)
2929  {
2930  FromUInt(i);
2931 
2932  return *this;
2933  }
2934 
2935 
2940  UInt(unsigned int i)
2941  {
2942  FromUInt(i);
2943  }
2944 
2945 
2950  UInt<value_size> & operator=(signed int i)
2951  {
2952  FromInt(i);
2953 
2954  return *this;
2955  }
2956 
2957 
2962  UInt(signed int i)
2963  {
2964  FromInt(i);
2965  }
2966 
2967 
2968 #endif
2969 
2970 
2971 
2972 
2973 
2977  UInt(const char * s)
2978  {
2979  FromString(s);
2980  }
2981 
2982 
2986  UInt(const std::string & s)
2987  {
2988  FromString( s.c_str() );
2989  }
2990 
2991 
2992 #ifndef TTMATH_DONT_USE_WCHAR
2993 
2997  UInt(const wchar_t * s)
2998  {
2999  FromString(s);
3000  }
3001 
3002 
3006  UInt(const std::wstring & s)
3007  {
3008  FromString( s.c_str() );
3009  }
3010 
3011 #endif
3012 
3013 
3014 
3015 
3022  {
3023  // when macro TTMATH_DEBUG_LOG is defined
3024  // we set special values to the table
3025  // in order to be everywhere the same value of the UInt object
3026  // without this it would be difficult to analyse the log file
3027  #ifdef TTMATH_DEBUG_LOG
3028  #ifdef TTMATH_PLATFORM32
3029  for(uint i=0 ; i<value_size ; ++i)
3030  table[i] = 0xc1c1c1c1;
3031  #else
3032  for(uint i=0 ; i<value_size ; ++i)
3033  table[i] = 0xc1c1c1c1c1c1c1c1;
3034  #endif
3035  #endif
3036  }
3037 
3038 
3043  {
3044  for(uint i=0 ; i<value_size ; ++i)
3045  table[i] = u.table[i];
3046 
3047  TTMATH_LOG("UInt::UInt(UInt<>)")
3048  }
3049 
3050 
3051 
3055  template<uint argument_size>
3057  {
3058  // look that 'size' we still set as 'value_size' and not as u.value_size
3059  FromUInt(u);
3060  }
3061 
3062 
3063 
3064 
3069  {
3070  }
3071 
3072 
3079  uint ToUInt() const
3080  {
3081  return table[0];
3082  }
3083 
3084 
3089  uint ToUInt(uint & result) const
3090  {
3091  result = table[0];
3092 
3093  for(uint i=1 ; i<value_size ; ++i)
3094  if( table[i] != 0 )
3095  return 1;
3096 
3097  return 0;
3098  }
3099 
3100 
3105  uint ToInt(uint & result) const
3106  {
3107  return ToUInt(result);
3108  }
3109 
3110 
3115  uint ToInt(sint & result) const
3116  {
3117  result = sint(table[0]);
3118 
3119  if( (result & TTMATH_UINT_HIGHEST_BIT) != 0 )
3120  return 1;
3121 
3122  for(uint i=1 ; i<value_size ; ++i)
3123  if( table[i] != 0 )
3124  return 1;
3125 
3126  return 0;
3127  }
3128 
3129 
3130 #ifdef TTMATH_PLATFORM32
3131 
3137  uint ToUInt(ulint & result) const
3138  {
3139  if( value_size == 1 )
3140  {
3141  result = table[0];
3142  }
3143  else
3144  {
3145  uint low = table[0];
3146  uint high = table[1];
3147 
3148  result = low;
3149  result |= (ulint(high) << TTMATH_BITS_PER_UINT);
3150 
3151  for(uint i=2 ; i<value_size ; ++i)
3152  if( table[i] != 0 )
3153  return 1;
3154  }
3155 
3156  return 0;
3157  }
3158 
3159 
3165  uint ToInt(ulint & result) const
3166  {
3167  return ToUInt(result);
3168  }
3169 
3170 
3176  uint ToInt(slint & result) const
3177  {
3178  ulint temp;
3179 
3180  uint c = ToUInt(temp);
3181  result = slint(temp);
3182 
3183  if( c || result < 0 )
3184  return 1;
3185 
3186  return 0;
3187  }
3188 
3189 #endif
3190 
3191 
3192 
3193 #ifdef TTMATH_PLATFORM64
3194 
3200  uint ToUInt(unsigned int & result) const
3201  {
3202  result = (unsigned int)table[0];
3203 
3204  if( (table[0] >> 32) != 0 )
3205  return 1;
3206 
3207  for(uint i=1 ; i<value_size ; ++i)
3208  if( table[i] != 0 )
3209  return 1;
3210 
3211  return 0;
3212  }
3213 
3214 
3220  uint ToInt(unsigned int & result) const
3221  {
3222  return ToUInt(result);
3223  }
3224 
3225 
3231  uint ToInt(int & result) const
3232  {
3233  unsigned int temp;
3234 
3235  uint c = ToUInt(temp);
3236  result = int(temp);
3237 
3238  if( c || result < 0 )
3239  return 1;
3240 
3241  return 0;
3242  }
3243 
3244 
3245 #endif
3246 
3247 
3248 
3249 
3250 protected:
3251 
3257  double ToStringLog2(uint x) const
3258  {
3259  static double log_tab[] = {
3260  1.000000000000000000,
3261  0.630929753571457437,
3262  0.500000000000000000,
3263  0.430676558073393050,
3264  0.386852807234541586,
3265  0.356207187108022176,
3266  0.333333333333333333,
3267  0.315464876785728718,
3268  0.301029995663981195,
3269  0.289064826317887859,
3270  0.278942945651129843,
3271  0.270238154427319741,
3272  0.262649535037193547,
3273  0.255958024809815489,
3274  0.250000000000000000
3275  };
3276 
3277  if( x<2 || x>16 )
3278  return 0;
3279 
3280  return log_tab[x-2];
3281  }
3282 
3283 
3284 public:
3285 
3286 
3291  template<class string_type>
3292  void ToStringBase(string_type & result, uint b = 10, bool negative = false) const
3293  {
3294  UInt<value_size> temp(*this);
3295  uint rest, table_id, index, digits;
3296  double digits_d;
3297  char character;
3298 
3299  result.clear();
3300 
3301  if( b<2 || b>16 )
3302  return;
3303 
3304  if( !FindLeadingBit(table_id, index) )
3305  {
3306  result = '0';
3307  return;
3308  }
3309 
3310  if( negative )
3311  result = '-';
3312 
3313  digits_d = table_id; // for not making an overflow in uint type
3314  digits_d *= TTMATH_BITS_PER_UINT;
3315  digits_d += index + 1;
3316  digits_d *= ToStringLog2(b);
3317  digits = static_cast<uint>(digits_d) + 3; // plus some epsilon
3318 
3319  if( result.capacity() < digits )
3320  result.reserve(digits);
3321 
3322  do
3323  {
3324  temp.DivInt(b, &rest);
3325  character = static_cast<char>(Misc::DigitToChar(rest));
3326  result.insert(result.end(), character);
3327  }
3328  while( !temp.IsZero() );
3329 
3330  size_t i1 = negative ? 1 : 0; // the first is a hyphen (when negative is true)
3331  size_t i2 = result.size() - 1;
3332 
3333  for( ; i1 < i2 ; ++i1, --i2 )
3334  {
3335  char tempc = static_cast<char>(result[i1]);
3336  result[i1] = result[i2];
3337  result[i2] = tempc;
3338  }
3339  }
3340 
3341 
3342 
3346  void ToString(std::string & result, uint b = 10) const
3347  {
3348  return ToStringBase(result, b);
3349  }
3350 
3351 
3352  std::string ToString(uint b = 10) const
3353  {
3354  std::string result;
3355  ToStringBase(result, b);
3356 
3357  return result;
3358  }
3359 
3360 
3361 #ifndef TTMATH_DONT_USE_WCHAR
3362 
3363  void ToString(std::wstring & result, uint b = 10) const
3364  {
3365  return ToStringBase(result, b);
3366  }
3367 
3368  std::wstring ToWString(uint b = 10) const
3369  {
3370  std::wstring result;
3371  ToStringBase(result, b);
3372 
3373  return result;
3374  }
3375 
3376 #endif
3377 
3378 
3379 
3380 private:
3381 
3385  template<class char_type>
3386  uint FromStringBase(const char_type * s, uint b = 10, const char_type ** after_source = 0, bool * value_read = 0)
3387  {
3388  UInt<value_size> base( b );
3389  UInt<value_size> temp;
3390  sint z;
3391  uint c = 0;
3392 
3393  SetZero();
3394  temp.SetZero();
3396 
3397  if( after_source )
3398  *after_source = s;
3399 
3400  if( value_read )
3401  *value_read = false;
3402 
3403  if( b<2 || b>16 )
3404  return 1;
3405 
3406 
3407  for( ; (z=Misc::CharToDigit(*s, b)) != -1 ; ++s)
3408  {
3409  if( value_read )
3410  *value_read = true;
3411 
3412  if( c == 0 )
3413  {
3414  temp.table[0] = z;
3415 
3416  c += Mul(base); // !! IMPROVE ME: there can be used MulInt here
3417  c += Add(temp);
3418  }
3419  }
3420 
3421  if( after_source )
3422  *after_source = s;
3423 
3424  TTMATH_LOGC("UInt::FromString", c)
3425 
3426  return (c==0)? 0 : 1;
3427  }
3428 
3429 
3430 public:
3431 
3432 
3450  uint FromString(const char * s, uint b = 10, const char ** after_source = 0, bool * value_read = 0)
3451  {
3452  return FromStringBase(s, b, after_source, value_read);
3453  }
3454 
3455 
3461  uint FromString(const std::string & s, uint b = 10)
3462  {
3463  return FromString( s.c_str(), b );
3464  }
3465 
3466 
3470  UInt<value_size> & operator=(const char * s)
3471  {
3472  FromString(s);
3473 
3474  return *this;
3475  }
3476 
3477 
3481  UInt<value_size> & operator=(const std::string & s)
3482  {
3483  FromString( s.c_str() );
3484 
3485  return *this;
3486  }
3487 
3488 
3489 
3490 #ifndef TTMATH_DONT_USE_WCHAR
3491 
3495  uint FromString(const wchar_t * s, uint b = 10, const wchar_t ** after_source = 0, bool * value_read = 0)
3496  {
3497  return FromStringBase(s, b, after_source, value_read);
3498  }
3499 
3500 
3506  uint FromString(const std::wstring & s, uint b = 10)
3507  {
3508  return FromString( s.c_str(), b );
3509  }
3510 
3511 
3515  UInt<value_size> & operator=(const wchar_t * s)
3516  {
3517  FromString(s);
3518 
3519  return *this;
3520  }
3521 
3522 
3526  UInt<value_size> & operator=(const std::wstring & s)
3527  {
3528  FromString( s.c_str() );
3529 
3530  return *this;
3531  }
3532 
3533 #endif
3534 
3535 
3551  bool CmpSmaller(const UInt<value_size> & l, sint index = -1) const
3552  {
3553  sint i;
3554 
3555  if( index==-1 || index>=sint(value_size) )
3556  i = value_size - 1;
3557  else
3558  i = index;
3559 
3560 
3561  for( ; i>=0 ; --i)
3562  {
3563  if( table[i] != l.table[i] )
3564  return table[i] < l.table[i];
3565  }
3566 
3567  // they're equal
3568  return false;
3569  }
3570 
3571 
3572 
3582  bool CmpBigger(const UInt<value_size> & l, sint index = -1) const
3583  {
3584  sint i;
3585 
3586  if( index==-1 || index>=sint(value_size) )
3587  i = value_size - 1;
3588  else
3589  i = index;
3590 
3591 
3592  for( ; i>=0 ; --i)
3593  {
3594  if( table[i] != l.table[i] )
3595  return table[i] > l.table[i];
3596  }
3597 
3598  // they're equal
3599  return false;
3600  }
3601 
3602 
3610  bool CmpEqual(const UInt<value_size> & l, sint index = -1) const
3611  {
3612  sint i;
3613 
3614  if( index==-1 || index>=sint(value_size) )
3615  i = value_size - 1;
3616  else
3617  i = index;
3618 
3619 
3620  for( ; i>=0 ; --i)
3621  if( table[i] != l.table[i] )
3622  return false;
3623 
3624  return true;
3625  }
3626 
3627 
3628 
3636  bool CmpSmallerEqual(const UInt<value_size> & l, sint index=-1) const
3637  {
3638  sint i;
3639 
3640  if( index==-1 || index>=sint(value_size) )
3641  i = value_size - 1;
3642  else
3643  i = index;
3644 
3645 
3646  for( ; i>=0 ; --i)
3647  {
3648  if( table[i] != l.table[i] )
3649  return table[i] < l.table[i];
3650  }
3651 
3652  // they're equal
3653  return true;
3654  }
3655 
3656 
3657 
3665  bool CmpBiggerEqual(const UInt<value_size> & l, sint index=-1) const
3666  {
3667  sint i;
3668 
3669  if( index==-1 || index>=sint(value_size) )
3670  i = value_size - 1;
3671  else
3672  i = index;
3673 
3674 
3675  for( ; i>=0 ; --i)
3676  {
3677  if( table[i] != l.table[i] )
3678  return table[i] > l.table[i];
3679  }
3680 
3681  // they're equal
3682  return true;
3683  }
3684 
3685 
3686  /*
3687  operators for comparising
3688  */
3689 
3690  bool operator<(const UInt<value_size> & l) const
3691  {
3692  return CmpSmaller(l);
3693  }
3694 
3695 
3696  bool operator>(const UInt<value_size> & l) const
3697  {
3698  return CmpBigger(l);
3699  }
3700 
3701 
3702  bool operator==(const UInt<value_size> & l) const
3703  {
3704  return CmpEqual(l);
3705  }
3706 
3707 
3708  bool operator!=(const UInt<value_size> & l) const
3709  {
3710  return !operator==(l);
3711  }
3712 
3713 
3714  bool operator<=(const UInt<value_size> & l) const
3715  {
3716  return CmpSmallerEqual(l);
3717  }
3718 
3719  bool operator>=(const UInt<value_size> & l) const
3720  {
3721  return CmpBiggerEqual(l);
3722  }
3723 
3724 
3732  {
3733  UInt<value_size> temp(*this);
3734 
3735  temp.Sub(p2);
3736 
3737  return temp;
3738  }
3739 
3741  {
3742  Sub(p2);
3743 
3744  return *this;
3745  }
3746 
3748  {
3749  UInt<value_size> temp(*this);
3750 
3751  temp.Add(p2);
3752 
3753  return temp;
3754  }
3755 
3757  {
3758  Add(p2);
3759 
3760  return *this;
3761  }
3762 
3763 
3765  {
3766  UInt<value_size> temp(*this);
3767 
3768  temp.Mul(p2);
3769 
3770  return temp;
3771  }
3772 
3773 
3775  {
3776  Mul(p2);
3777 
3778  return *this;
3779  }
3780 
3781 
3783  {
3784  UInt<value_size> temp(*this);
3785 
3786  temp.Div(p2);
3787 
3788  return temp;
3789  }
3790 
3791 
3793  {
3794  Div(p2);
3795 
3796  return *this;
3797  }
3798 
3799 
3801  {
3802  UInt<value_size> temp(*this);
3803  UInt<value_size> remainder;
3804 
3805  temp.Div( p2, remainder );
3806 
3807  return remainder;
3808  }
3809 
3810 
3812  {
3813  UInt<value_size> remainder;
3814 
3815  Div( p2, remainder );
3816  operator=(remainder);
3817 
3818  return *this;
3819  }
3820 
3821 
3826  {
3827  AddOne();
3828 
3829  return *this;
3830  }
3831 
3832 
3837  {
3838  UInt<value_size> temp( *this );
3839 
3840  AddOne();
3841 
3842  return temp;
3843  }
3844 
3845 
3847  {
3848  SubOne();
3849 
3850  return *this;
3851  }
3852 
3853 
3855  {
3856  UInt<value_size> temp( *this );
3857 
3858  SubOne();
3859 
3860  return temp;
3861  }
3862 
3863 
3864 
3872  {
3873  UInt<value_size> temp( *this );
3874 
3875  temp.BitNot();
3876 
3877  return temp;
3878  }
3879 
3880 
3882  {
3883  UInt<value_size> temp( *this );
3884 
3885  temp.BitAnd(p2);
3886 
3887  return temp;
3888  }
3889 
3890 
3892  {
3893  BitAnd(p2);
3894 
3895  return *this;
3896  }
3897 
3898 
3900  {
3901  UInt<value_size> temp( *this );
3902 
3903  temp.BitOr(p2);
3904 
3905  return temp;
3906  }
3907 
3908 
3910  {
3911  BitOr(p2);
3912 
3913  return *this;
3914  }
3915 
3916 
3918  {
3919  UInt<value_size> temp( *this );
3920 
3921  temp.BitXor(p2);
3922 
3923  return temp;
3924  }
3925 
3926 
3928  {
3929  BitXor(p2);
3930 
3931  return *this;
3932  }
3933 
3934 
3936  {
3937  UInt<value_size> temp( *this );
3938 
3939  temp.Rcr(move);
3940 
3941  return temp;
3942  }
3943 
3944 
3946  {
3947  Rcr(move);
3948 
3949  return *this;
3950  }
3951 
3952 
3954  {
3955  UInt<value_size> temp( *this );
3956 
3957  temp.Rcl(move);
3958 
3959  return temp;
3960  }
3961 
3962 
3964  {
3965  Rcl(move);
3966 
3967  return *this;
3968  }
3969 
3970 
3980 private:
3981 
3982 
3986  template<class ostream_type, class string_type>
3987  static ostream_type & OutputToStream(ostream_type & s, const UInt<value_size> & l)
3988  {
3989  string_type ss;
3990 
3991  l.ToString(ss);
3992  s << ss;
3993 
3994  return s;
3995  }
3996 
3997 
3998 public:
3999 
4000 
4004  friend std::ostream & operator<<(std::ostream & s, const UInt<value_size> & l)
4005  {
4006  return OutputToStream<std::ostream, std::string>(s, l);
4007  }
4008 
4009 
4010 #ifndef TTMATH_DONT_USE_WCHAR
4011 
4015  friend std::wostream & operator<<(std::wostream & s, const UInt<value_size> & l)
4016  {
4017  return OutputToStream<std::wostream, std::wstring>(s, l);
4018  }
4019 
4020 #endif
4021 
4022 
4023 
4024 private:
4025 
4029  template<class istream_type, class string_type, class char_type>
4030  static istream_type & InputFromStream(istream_type & s, UInt<value_size> & l)
4031  {
4032  string_type ss;
4033 
4034  // char or wchar_t for operator>>
4035  char_type z;
4036 
4037  // operator>> omits white characters if they're set for ommiting
4038  s >> z;
4039 
4040  // we're reading only digits (base=10)
4041  while( s.good() && Misc::CharToDigit(z, 10)>=0 )
4042  {
4043  ss += z;
4044  z = static_cast<char_type>(s.get());
4045  }
4046 
4047  // we're leaving the last read character
4048  // (it's not belonging to the value)
4049  s.unget();
4050 
4051  l.FromString(ss);
4052 
4053  return s;
4054  }
4055 
4056 public:
4057 
4058 
4062  friend std::istream & operator>>(std::istream & s, UInt<value_size> & l)
4063  {
4064  return InputFromStream<std::istream, std::string, char>(s, l);
4065  }
4066 
4067 
4068 #ifndef TTMATH_DONT_USE_WCHAR
4069 
4073  friend std::wistream & operator>>(std::wistream & s, UInt<value_size> & l)
4074  {
4075  return InputFromStream<std::wistream, std::wstring, wchar_t>(s, l);
4076  }
4077 
4078 #endif
4079 
4080 
4081  /*
4082  Following methods are defined in:
4083  ttmathuint_x86.h
4084  ttmathuint_x86_64.h
4085  ttmathuint_noasm.h
4086  */
4087 
4088 #ifdef TTMATH_NOASM
4089  static uint AddTwoWords(uint a, uint b, uint carry, uint * result);
4090  static uint SubTwoWords(uint a, uint b, uint carry, uint * result);
4091 
4092 #ifdef TTMATH_PLATFORM64
4093 
4094  union uint_
4095  {
4096  struct
4097  {
4098  unsigned int low; // 32 bit
4099  unsigned int high; // 32 bit
4100  } u_;
4101 
4102  uint u; // 64 bit
4103  };
4104 
4105 
4106  static void DivTwoWords2(uint a,uint b, uint c, uint * r, uint * rest);
4107  static uint DivTwoWordsNormalize(uint_ & a_, uint_ & b_, uint_ & c_);
4108  static uint DivTwoWordsUnnormalize(uint u, uint d);
4109  static unsigned int DivTwoWordsCalculate(uint_ u_, unsigned int u3, uint_ v_);
4110  static void MultiplySubtract(uint_ & u_, unsigned int & u3, unsigned int & q, uint_ v_);
4111 
4112 #endif // TTMATH_PLATFORM64
4113 #endif // TTMATH_NOASM
4114 
4115 
4116 private:
4117  uint Rcl2_one(uint c);
4118  uint Rcr2_one(uint c);
4119  uint Rcl2(uint bits, uint c);
4120  uint Rcr2(uint bits, uint c);
4121 
4122 public:
4123  static const char * LibTypeStr();
4124  static LibTypeCode LibType();
4125  uint Add(const UInt<value_size> & ss2, uint c=0);
4126  uint AddInt(uint value, uint index = 0);
4127  uint AddTwoInts(uint x2, uint x1, uint index);
4128  static uint AddVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result);
4129  uint Sub(const UInt<value_size> & ss2, uint c=0);
4130  uint SubInt(uint value, uint index = 0);
4131  static uint SubVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result);
4132  static sint FindLeadingBitInWord(uint x);
4133  static sint FindLowestBitInWord(uint x);
4134  static uint SetBitInWord(uint & value, uint bit);
4135  static void MulTwoWords(uint a, uint b, uint * result_high, uint * result_low);
4136  static void DivTwoWords(uint a,uint b, uint c, uint * r, uint * rest);
4137 
4138 };
4139 
4140 
4141 
4146 template<>
4147 class UInt<0>
4148 {
4149 public:
4150  uint table[1];
4151 
4152  void Mul2Big(const UInt<0> &, UInt<0> &) { TTMATH_ASSERT(false) };
4153  void SetZero() { TTMATH_ASSERT(false) };
4154  uint AddTwoInts(uint, uint, uint) { TTMATH_ASSERT(false) return 0; };
4155 };
4156 
4157 
4158 } //namespace
4159 
4160 
4161 #include "ttmathuint_x86.h"
4162 #include "ttmathuint_x86_64.h"
4163 #include "ttmathuint_noasm.h"
4164 
4165 #endif
UInt< value_size > & operator=(const char *s)
Definition: ttmathuint.h:3470
bool CmpSmallerEqual(const UInt< value_size > &l, sint index=-1) const
Definition: ttmathuint.h:3636
uint Div1(const UInt< value_size > &divisor, UInt< value_size > *remainder=0)
Definition: ttmathuint.h:1729
UInt(const UInt< argument_size > &u)
Definition: ttmathuint.h:3056
uint Rcl(uint bits, uint c=0)
Definition: ttmathuint.h:460
void Mul2Big(const UInt< value_size > &ss2, UInt< value_size *2 > &result)
Definition: ttmathuint.h:1110
UInt< value_size > operator%(const UInt< value_size > &p2) const
Definition: ttmathuint.h:3800
UInt< value_size > & operator^=(const UInt< value_size > &p2)
Definition: ttmathuint.h:3927
uint SubInt(uint value, uint index=0)
bool operator>=(const UInt< value_size > &l) const
Definition: ttmathuint.h:3719
bool FindLeadingBit(uint &table_id, uint &index) const
Definition: ttmathuint.h:649
UInt< value_size > & operator+=(const UInt< value_size > &p2)
Definition: ttmathuint.h:3756
static void SkipWhiteCharacters(const char_type *&c)
Definition: ttmathmisc.h:160
uint FromInt(const UInt< argument_size > &p)
Definition: ttmathuint.h:2674
UInt< value_size > & operator=(const std::wstring &s)
Definition: ttmathuint.h:3526
static uint CharToDigit(uint c)
Definition: ttmathmisc.h:181
static const char * LibTypeStr()
void MulInt(uint ss2, UInt< result_size > &result) const
Definition: ttmathuint.h:873
uint FromUInt(const UInt< argument_size > &p)
Definition: ttmathuint.h:2633
static void DivTwoWords(uint a, uint b, uint c, uint *r, uint *rest)
void Mul2Big(const UInt< 0 > &, UInt< 0 > &)
Definition: ttmathuint.h:4152
NetworKit::index index
Definition: BloomFilter.h:16
void Mul3Big(const UInt< value_size > &ss2, UInt< value_size *2 > &result)
Definition: ttmathuint.h:1236
uint AddInt(uint value, uint index=0)
UInt< value_size > operator-(const UInt< value_size > &p2) const
Definition: ttmathuint.h:3731
uint ToInt(slint &result) const
Definition: ttmathuint.h:3176
uint FromString(const char *s, uint b=10, const char **after_source=0, bool *value_read=0)
Definition: ttmathuint.h:3450
uint FromInt(slint n)
Definition: ttmathuint.h:2834
uint table[value_size]
Definition: ttmathuint.h:81
UInt< value_size > & operator=(const std::string &s)
Definition: ttmathuint.h:3481
uint Div3(const UInt< value_size > &ss2, UInt< value_size > *remainder=0)
Definition: ttmathuint.h:2085
#define TTMATH_VECTOR_LOG(msg, vector, len)
Definition: ttmathtypes.h:673
some helpful functions
UInt< value_size > operator--(int)
Definition: ttmathuint.h:3854
~UInt()
Definition: ttmathuint.h:3068
uint AddTwoInts(uint, uint, uint)
Definition: ttmathuint.h:4154
#define TTMATH_LOG(msg)
Definition: ttmathtypes.h:671
UInt< value_size > operator/(const UInt< value_size > &p2) const
Definition: ttmathuint.h:3782
uint DivInt(uint divisor, uint &remainder)
Definition: ttmathuint.h:1587
UInt(const std::wstring &s)
Definition: ttmathuint.h:3006
uint ToUInt(uint &result) const
Definition: ttmathuint.h:3089
UInt< value_size > & operator|=(const UInt< value_size > &p2)
Definition: ttmathuint.h:3909
bool AreFirstBitsZero(uint bits) const
Definition: ttmathuint.h:2594
UInt< value_size > & operator=(const wchar_t *s)
Definition: ttmathuint.h:3515
static LibTypeCode LibType()
UInt< value_size > operator++(int)
Definition: ttmathuint.h:3836
UInt< value_size > & operator=(uint i)
Definition: ttmathuint.h:2751
static uint DigitToChar(uint digit)
Definition: ttmathmisc.h:236
void PrintLog(const char_type *msg, uint carry, ostream_type &output) const
Definition: ttmathuint.h:169
UInt< value_size > & operator/=(const UInt< value_size > &p2)
Definition: ttmathuint.h:3792
int64_t slint
Definition: ttmathtypes.h:178
uint Sub(const UInt< value_size > &ss2, uint c=0)
UInt(const UInt< value_size > &u)
Definition: ttmathuint.h:3042
uint Mul2(const UInt< value_size > &ss2)
Definition: ttmathuint.h:1079
UInt< value_size > operator|(const UInt< value_size > &p2) const
Definition: ttmathuint.h:3899
#define TTMATH_LOGC(msg, carry)
Definition: ttmathtypes.h:672
uint Add(const UInt< value_size > &ss2, uint c=0)
void ToStringBase(string_type &result, uint b=10, bool negative=false) const
Definition: ttmathuint.h:3292
UInt(ulint n)
Definition: ttmathuint.h:2861
uint ToInt(ulint &result) const
Definition: ttmathuint.h:3165
UInt< value_size > operator~() const
Definition: ttmathuint.h:3871
UInt< value_size > & operator=(sint i)
Definition: ttmathuint.h:2771
UInt(const char *s)
Definition: ttmathuint.h:2977
UInt< value_size > & operator=(const UInt< argument_size > &p)
Definition: ttmathuint.h:2726
static sint FindLowestBitInWord(uint x)
friend std::istream & operator>>(std::istream &s, UInt< value_size > &l)
Definition: ttmathuint.h:4062
bool CmpEqual(const UInt< value_size > &l, sint index=-1) const
Definition: ttmathuint.h:3610
void MulBig(const UInt< value_size > &ss2, UInt< value_size *2 > &result, uint algorithm=100)
Definition: ttmathuint.h:951
uint FromString(const std::string &s, uint b=10)
Definition: ttmathuint.h:3461
void SetMax()
Definition: ttmathuint.h:215
uint FromInt(sint value)
Definition: ttmathuint.h:2709
std::string ToString(uint b=10) const
Definition: ttmathuint.h:3352
UInt< value_size > operator&(const UInt< value_size > &p2) const
Definition: ttmathuint.h:3881
bool operator!=(const UInt< value_size > &l) const
Definition: ttmathuint.h:3708
std::wstring ToWString(uint b=10) const
Definition: ttmathuint.h:3368
bool IsTheLowestBitSet() const
Definition: ttmathuint.h:2532
uint FromUInt(ulint n)
Definition: ttmathuint.h:2797
#define TTMATH_UINT_HIGHEST_BIT
Definition: ttmathtypes.h:189
void Sqrt()
Definition: ttmathuint.h:2438
uint MulInt(uint ss2)
Definition: ttmathuint.h:835
void ToString(std::wstring &result, uint b=10) const
Definition: ttmathuint.h:3363
UInt< value_size > & operator=(ulint n)
Definition: ttmathuint.h:2849
static void PrintVectorLog(const char_type *msg, ostream_type &output, const uint *vector, uint vector_len)
Definition: ttmathuint.h:135
UInt< value_size > & operator=(const UInt< value_size > &p)
Definition: ttmathuint.h:2737
signed int sint
Definition: ttmathtypes.h:164
uint GetBit(uint bit_index) const
Definition: ttmathuint.h:706
uint Div2(const UInt< value_size > &divisor, UInt< value_size > *remainder=0)
Definition: ttmathuint.h:1839
LibTypeCode
Definition: ttmathtypes.h:335
void SetFromTable(const uint *temp_table, uint temp_table_len)
Definition: ttmathuint.h:266
void SetZero()
Definition: ttmathuint.h:188
uint ToInt(sint &result) const
Definition: ttmathuint.h:3115
double ToStringLog2(uint x) const
Definition: ttmathuint.h:3257
UInt< value_size > operator*(const UInt< value_size > &p2) const
Definition: ttmathuint.h:3764
constants used in the library
uint ToUInt() const
Definition: ttmathuint.h:3079
bool IsOnlyTheHighestBitSet() const
Definition: ttmathuint.h:2541
static void PrintVectorLog(const char_type *msg, uint carry, ostream_type &output, const uint *vector, uint vector_len)
Definition: ttmathuint.h:148
uint Div(const UInt< value_size > &divisor, UInt< value_size > *remainder=0, uint algorithm=3)
Definition: ttmathuint.h:1603
#define TTMATH_UINT_MAX_VALUE
Definition: ttmathtypes.h:195
static sint FindLeadingBitInWord(uint x)
uint Pow(UInt< value_size > pow)
Definition: ttmathuint.h:2402
static void MulTwoWords(uint a, uint b, uint *result_high, uint *result_low)
void BitAnd(const UInt< value_size > &ss2)
Definition: ttmathuint.h:743
void BitNot()
Definition: ttmathuint.h:779
uint AddTwoInts(uint x2, uint x1, uint index)
uint Rcr(uint bits, uint c=0)
Definition: ttmathuint.h:555
uint FromInt(ulint n)
Definition: ttmathuint.h:2824
uint Div2(const UInt< value_size > &divisor, UInt< value_size > &remainder)
Definition: ttmathuint.h:1860
#define TTMATH_ASSERT(expression)
Definition: ttmathtypes.h:660
void BitOr(const UInt< value_size > &ss2)
Definition: ttmathuint.h:755
bool CmpBigger(const UInt< value_size > &l, sint index=-1) const
Definition: ttmathuint.h:3582
static uint AddTwoWords(uint a, uint b, uint carry, uint *result)
bool FindLowestBit(uint &table_id, uint &index) const
Definition: ttmathuint.h:681
static uint SubTwoWords(uint a, uint b, uint carry, uint *result)
void BitNot2()
Definition: ttmathuint.h:795
UInt< value_size > & operator-=(const UInt< value_size > &p2)
Definition: ttmathuint.h:3740
#define TTMATH_BITS_PER_UINT
Definition: ttmathtypes.h:184
void BitXor(const UInt< value_size > &ss2)
Definition: ttmathuint.h:767
uint CompensationToLeft()
Definition: ttmathuint.h:598
UInt< value_size > & operator%=(const UInt< value_size > &p2)
Definition: ttmathuint.h:3811
UInt< value_size > operator^(const UInt< value_size > &p2) const
Definition: ttmathuint.h:3917
UInt implements a big integer value without a sign.
Definition: ttmathuint.h:73
UInt< value_size > operator<<(int move) const
Definition: ttmathuint.h:3953
#define TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE
Definition: ttmathtypes.h:305
UInt(const wchar_t *s)
Definition: ttmathuint.h:2997
uint Div3(const UInt< value_size > &ss2, UInt< value_size > &remainder)
Definition: ttmathuint.h:2102
void SetMin()
Definition: ttmathuint.h:228
UInt< value_size > & operator&=(const UInt< value_size > &p2)
Definition: ttmathuint.h:3891
UInt(uint i)
Definition: ttmathuint.h:2762
uint MulFastest(const UInt< value_size > &ss2)
Definition: ttmathuint.h:1462
void MulFastestBig(const UInt< value_size > &ss2, UInt< value_size *2 > &result)
Definition: ttmathuint.h:1493
void Mul1Big(const UInt< value_size > &ss2_, UInt< value_size *2 > &result)
Definition: ttmathuint.h:1040
uint Div(const UInt< value_size > &divisor, UInt< value_size > &remainder, uint algorithm=3)
Definition: ttmathuint.h:1621
uint64_t ulint
Definition: ttmathtypes.h:177
friend std::wistream & operator>>(std::wistream &s, UInt< value_size > &l)
Definition: ttmathuint.h:4073
bool CmpBiggerEqual(const UInt< value_size > &l, sint index=-1) const
Definition: ttmathuint.h:3665
UInt< value_size > & operator>>=(int move)
Definition: ttmathuint.h:3945
UInt(const std::string &s)
Definition: ttmathuint.h:2986
UInt< value_size > & operator<<=(int move)
Definition: ttmathuint.h:3963
uint FromInt(uint value)
Definition: ttmathuint.h:2700
uint Mul3(const UInt< value_size > &ss2)
Definition: ttmathuint.h:1203
UInt< value_size > & operator=(slint n)
Definition: ttmathuint.h:2871
bool operator>(const UInt< value_size > &l) const
Definition: ttmathuint.h:3696
void ClearFirstBits(uint n)
Definition: ttmathuint.h:2484
UInt(sint i)
Definition: ttmathuint.h:2784
uint Div1(const UInt< value_size > &divisor, UInt< value_size > &remainder)
Definition: ttmathuint.h:1752
bool CmpSmaller(const UInt< value_size > &l, sint index=-1) const
Definition: ttmathuint.h:3551
uint Mul(const UInt< value_size > &ss2, uint algorithm=100)
Definition: ttmathuint.h:923
UInt< value_size > & operator++()
Definition: ttmathuint.h:3825
uint Size() const
Definition: ttmathuint.h:179
uint FromUInt(uint value)
Definition: ttmathuint.h:2683
uint ToInt(uint &result) const
Definition: ttmathuint.h:3105
uint SetBit(uint bit_index)
Definition: ttmathuint.h:726
unsigned int uint
Definition: ttmathtypes.h:163
uint AddOne()
Definition: ttmathuint.h:386
void SetZero()
Definition: ttmathuint.h:4153
void SetOne()
Definition: ttmathuint.h:202
UInt(slint n)
Definition: ttmathuint.h:2883
uint FromString(const wchar_t *s, uint b=10, const wchar_t **after_source=0, bool *value_read=0)
Definition: ttmathuint.h:3495
static uint AddVector(const uint *ss1, const uint *ss2, uint ss1_size, uint ss2_size, uint *result)
UInt()
Definition: ttmathuint.h:3021
UInt< value_size > & operator*=(const UInt< value_size > &p2)
Definition: ttmathuint.h:3774
Definition: ttmathuint.h:4147
UInt< value_size > & operator--()
Definition: ttmathuint.h:3846
void PrintLog(const char_type *msg, ostream_type &output) const
Definition: ttmathuint.h:159
bool IsTheHighestBitSet() const
Definition: ttmathuint.h:2523
static uint SubVector(const uint *ss1, const uint *ss2, uint ss1_size, uint ss2_size, uint *result)
uint DivInt(uint divisor, uint *remainder=0)
Definition: ttmathuint.h:1545
void ToString(std::string &result, uint b=10) const
Definition: ttmathuint.h:3346
UInt< value_size > operator>>(int move) const
Definition: ttmathuint.h:3935
bool IsZero() const
Definition: ttmathuint.h:2581
bool IsOnlyTheLowestBitSet() const
Definition: ttmathuint.h:2565
#define TTMATH_REFERENCE_ASSERT(expression)
Definition: ttmathtypes.h:659
bool operator==(const UInt< value_size > &l) const
Definition: ttmathuint.h:3702
uint Mul1(const UInt< value_size > &ss2)
Definition: ttmathuint.h:1020
void Swap(UInt< value_size > &ss2)
Definition: ttmathuint.h:239
UInt< value_size > operator+(const UInt< value_size > &p2) const
Definition: ttmathuint.h:3747
static uint SetBitInWord(uint &value, uint bit)
uint FromString(const std::wstring &s, uint b=10)
Definition: ttmathuint.h:3506
uint SubOne()
Definition: ttmathuint.h:395
void PrintTable(ostream_type &output) const
Definition: ttmathuint.h:97
uint ToUInt(ulint &result) const
Definition: ttmathuint.h:3137