GEOS  3.8.0dev
ttmathuint_noasm.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-2010, Tomasz Sowa
9  * All rights reserved.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions are met:
13  *
14  * * Redistributions of source code must retain the above copyright notice,
15  * this list of conditions and the following disclaimer.
16  *
17  * * Redistributions in binary form must reproduce the above copyright
18  * notice, this list of conditions and the following disclaimer in the
19  * documentation and/or other materials provided with the distribution.
20  *
21  * * Neither the name Tomasz Sowa nor the names of contributors to this
22  * project may be used to endorse or promote products derived
23  * from this software without specific prior written permission.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
26  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
29  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
35  * THE POSSIBILITY OF SUCH DAMAGE.
36  */
37 
38 #ifndef headerfilettmathuint_noasm
39 #define headerfilettmathuint_noasm
40 
41 
49 #ifdef TTMATH_NOASM
50 
51 
52 
53 namespace ttmath
54 {
55 
66  template<uint value_size>
67  const char * UInt<value_size>::LibTypeStr()
68  {
69  #ifdef TTMATH_PLATFORM32
70  static const char info[] = "no_asm_32";
71  #endif
72 
73  #ifdef TTMATH_PLATFORM64
74  static const char info[] = "no_asm_64";
75  #endif
76 
77  return info;
78  }
79 
80 
84  template<uint value_size>
85  LibTypeCode UInt<value_size>::LibType()
86  {
87  #ifdef TTMATH_PLATFORM32
88  LibTypeCode info = no_asm_32;
89  #endif
90 
91  #ifdef TTMATH_PLATFORM64
92  LibTypeCode info = no_asm_64;
93  #endif
94 
95  return info;
96  }
97 
98 
105  template<uint value_size>
106  uint UInt<value_size>::AddTwoWords(uint a, uint b, uint carry, uint * result)
107  {
108  uint temp;
109 
110  if( carry == 0 )
111  {
112  temp = a + b;
113 
114  if( temp < a )
115  carry = 1;
116  }
117  else
118  {
119  carry = 1;
120  temp = a + b + carry;
121 
122  if( temp > a ) // !(temp<=a)
123  carry = 0;
124  }
125 
126  *result = temp;
127 
128  return carry;
129  }
130 
131 
132 
141  template<uint value_size>
142  uint UInt<value_size>::Add(const UInt<value_size> & ss2, uint c)
143  {
144  uint i;
145 
146  for(i=0 ; i<value_size ; ++i)
147  c = AddTwoWords(table[i], ss2.table[i], c, &table[i]);
148 
149  TTMATH_LOGC("UInt::Add", c)
150 
151  return c;
152  }
153 
154 
177  template<uint value_size>
178  uint UInt<value_size>::AddInt(uint value, uint index)
179  {
180  uint i, c;
181 
182  TTMATH_ASSERT( index < value_size )
183 
184 
185  c = AddTwoWords(table[index], value, 0, &table[index]);
186 
187  for(i=index+1 ; i<value_size && c ; ++i)
188  c = AddTwoWords(table[i], 0, c, &table[i]);
189 
190  TTMATH_LOGC("UInt::AddInt", c)
191 
192  return c;
193  }
194 
195 
196 
197 
198 
235  template<uint value_size>
236  uint UInt<value_size>::AddTwoInts(uint x2, uint x1, uint index)
237  {
238  uint i, c;
239 
240  TTMATH_ASSERT( index < value_size - 1 )
241 
242 
243  c = AddTwoWords(table[index], x1, 0, &table[index]);
244  c = AddTwoWords(table[index+1], x2, c, &table[index+1]);
245 
246  for(i=index+2 ; i<value_size && c ; ++i)
247  c = AddTwoWords(table[i], 0, c, &table[i]);
248 
249  TTMATH_LOGC("UInt::AddTwoInts", c)
250 
251  return c;
252  }
253 
254 
255 
277  template<uint value_size>
278  uint UInt<value_size>::AddVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result)
279  {
280  uint i, c = 0;
281 
282  TTMATH_ASSERT( ss1_size >= ss2_size )
283 
284  for(i=0 ; i<ss2_size ; ++i)
285  c = AddTwoWords(ss1[i], ss2[i], c, &result[i]);
286 
287  for( ; i<ss1_size ; ++i)
288  c = AddTwoWords(ss1[i], 0, c, &result[i]);
289 
290  TTMATH_VECTOR_LOGC("UInt::AddVector", c, result, ss1_size)
291 
292  return c;
293  }
294 
295 
296 
297 
304  template<uint value_size>
305  uint UInt<value_size>::SubTwoWords(uint a, uint b, uint carry, uint * result)
306  {
307  if( carry == 0 )
308  {
309  *result = a - b;
310 
311  if( a < b )
312  carry = 1;
313  }
314  else
315  {
316  carry = 1;
317  *result = a - b - carry;
318 
319  if( a > b ) // !(a <= b )
320  carry = 0;
321  }
322 
323  return carry;
324  }
325 
326 
327 
328 
337  template<uint value_size>
338  uint UInt<value_size>::Sub(const UInt<value_size> & ss2, uint c)
339  {
340  uint i;
341 
342  for(i=0 ; i<value_size ; ++i)
343  c = SubTwoWords(table[i], ss2.table[i], c, &table[i]);
344 
345  TTMATH_LOGC("UInt::Sub", c)
346 
347  return c;
348  }
349 
350 
351 
352 
375  template<uint value_size>
376  uint UInt<value_size>::SubInt(uint value, uint index)
377  {
378  uint i, c;
379 
380  TTMATH_ASSERT( index < value_size )
381 
382 
383  c = SubTwoWords(table[index], value, 0, &table[index]);
384 
385  for(i=index+1 ; i<value_size && c ; ++i)
386  c = SubTwoWords(table[i], 0, c, &table[i]);
387 
388  TTMATH_LOGC("UInt::SubInt", c)
389 
390  return c;
391  }
392 
393 
415  template<uint value_size>
416  uint UInt<value_size>::SubVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result)
417  {
418  uint i, c = 0;
419 
420  TTMATH_ASSERT( ss1_size >= ss2_size )
421 
422  for(i=0 ; i<ss2_size ; ++i)
423  c = SubTwoWords(ss1[i], ss2[i], c, &result[i]);
424 
425  for( ; i<ss1_size ; ++i)
426  c = SubTwoWords(ss1[i], 0, c, &result[i]);
427 
428  TTMATH_VECTOR_LOGC("UInt::SubVector", c, result, ss1_size)
429 
430  return c;
431  }
432 
433 
434 
447  template<uint value_size>
448  uint UInt<value_size>::Rcl2_one(uint c)
449  {
450  uint i, new_c;
451 
452  if( c != 0 )
453  c = 1;
454 
455  for(i=0 ; i<value_size ; ++i)
456  {
457  new_c = (table[i] & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0;
458  table[i] = (table[i] << 1) | c;
459  c = new_c;
460  }
461 
462  TTMATH_LOGC("UInt::Rcl2_one", c)
463 
464  return c;
465  }
466 
467 
468 
469 
470 
471 
472 
485  template<uint value_size>
486  uint UInt<value_size>::Rcr2_one(uint c)
487  {
488  sint i; // signed i
489  uint new_c;
490 
491  if( c != 0 )
493 
494  for(i=sint(value_size)-1 ; i>=0 ; --i)
495  {
496  new_c = (table[i] & 1) ? TTMATH_UINT_HIGHEST_BIT : 0;
497  table[i] = (table[i] >> 1) | c;
498  c = new_c;
499  }
500 
501  c = (c != 0)? 1 : 0;
502 
503  TTMATH_LOGC("UInt::Rcr2_one", c)
504 
505  return c;
506  }
507 
508 
509 
510 
523  template<uint value_size>
524  uint UInt<value_size>::Rcl2(uint bits, uint c)
525  {
526  TTMATH_ASSERT( bits>0 && bits<TTMATH_BITS_PER_UINT )
527 
528  uint move = TTMATH_BITS_PER_UINT - bits;
529  uint i, new_c;
530 
531  if( c != 0 )
532  c = TTMATH_UINT_MAX_VALUE >> move;
533 
534  for(i=0 ; i<value_size ; ++i)
535  {
536  new_c = table[i] >> move;
537  table[i] = (table[i] << bits) | c;
538  c = new_c;
539  }
540 
541  TTMATH_LOGC("UInt::Rcl2", (c & 1))
542 
543  return (c & 1);
544  }
545 
546 
547 
548 
561  template<uint value_size>
562  uint UInt<value_size>::Rcr2(uint bits, uint c)
563  {
564  TTMATH_ASSERT( bits>0 && bits<TTMATH_BITS_PER_UINT )
565 
566  uint move = TTMATH_BITS_PER_UINT - bits;
567  sint i; // signed
568  uint new_c;
569 
570  if( c != 0 )
571  c = TTMATH_UINT_MAX_VALUE << move;
572 
573  for(i=value_size-1 ; i>=0 ; --i)
574  {
575  new_c = table[i] << move;
576  table[i] = (table[i] >> bits) | c;
577  c = new_c;
578  }
579 
580  c = (c & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0;
581 
582  TTMATH_LOGC("UInt::Rcr2", c)
583 
584  return c;
585  }
586 
587 
588 
589 
594  template<uint value_size>
595  sint UInt<value_size>::FindLeadingBitInWord(uint x)
596  {
597  if( x == 0 )
598  return -1;
599 
600  uint bit = TTMATH_BITS_PER_UINT - 1;
601 
602  while( (x & TTMATH_UINT_HIGHEST_BIT) == 0 )
603  {
604  x = x << 1;
605  --bit;
606  }
607 
608  return bit;
609  }
610 
611 
612 
617  template<uint value_size>
618  sint UInt<value_size>::FindLowestBitInWord(uint x)
619  {
620  if( x == 0 )
621  return -1;
622 
623  uint bit = 0;
624 
625  while( (x & 1) == 0 )
626  {
627  x = x >> 1;
628  ++bit;
629  }
630 
631  return bit;
632  }
633 
634 
635 
649  template<uint value_size>
650  uint UInt<value_size>::SetBitInWord(uint & value, uint bit)
651  {
652  TTMATH_ASSERT( bit < TTMATH_BITS_PER_UINT )
653 
654  uint mask = 1;
655 
656  if( bit > 0 )
657  mask = mask << bit;
658 
659  uint last = value & mask;
660  value = value | mask;
661 
662  return (last != 0) ? 1 : 0;
663  }
664 
665 
666 
667 
668 
669 
687  template<uint value_size>
688  void UInt<value_size>::MulTwoWords(uint a, uint b, uint * result_high, uint * result_low)
689  {
690  #ifdef TTMATH_PLATFORM32
691 
692  /*
693  on 32bit platforms we have defined 'unsigned long long int' type known as 'ulint' in ttmath namespace
694  this type has 64 bits, then we're using only one multiplication: 32bit * 32bit = 64bit
695  */
696 
697  union uint_
698  {
699  struct
700  {
701  uint low; // 32 bits
702  uint high; // 32 bits
703  } u_;
704 
705  ulint u; // 64 bits
706  } res;
707 
708  res.u = ulint(a) * ulint(b); // multiply two 32bit words, the result has 64 bits
709 
710  *result_high = res.u_.high;
711  *result_low = res.u_.low;
712 
713  #else
714 
715  /*
716  64 bits platforms
717 
718  we don't have a native type which has 128 bits
719  then we're splitting 'a' and 'b' to 4 parts (high and low halves)
720  and using 4 multiplications (with additions and carry correctness)
721  */
722 
723  uint_ a_;
724  uint_ b_;
725  uint_ res_high1, res_high2;
726  uint_ res_low1, res_low2;
727 
728  a_.u = a;
729  b_.u = b;
730 
731  /*
732  the multiplication is as follows (schoolbook algorithm with O(n^2) ):
733 
734  32 bits 32 bits
735 
736  +--------------------------------+
737  | a_.u_.high | a_.u_.low |
738  +--------------------------------+
739  | b_.u_.high | b_.u_.low |
740  +--------------------------------+--------------------------------+
741  | res_high1.u | res_low1.u |
742  +--------------------------------+--------------------------------+
743  | res_high2.u | res_low2.u |
744  +--------------------------------+--------------------------------+
745 
746  64 bits 64 bits
747  */
748 
749 
750  uint_ temp;
751 
752  res_low1.u = uint(b_.u_.low) * uint(a_.u_.low);
753 
754  temp.u = uint(res_low1.u_.high) + uint(b_.u_.low) * uint(a_.u_.high);
755  res_low1.u_.high = temp.u_.low;
756  res_high1.u_.low = temp.u_.high;
757  res_high1.u_.high = 0;
758 
759  res_low2.u_.low = 0;
760  temp.u = uint(b_.u_.high) * uint(a_.u_.low);
761  res_low2.u_.high = temp.u_.low;
762 
763  res_high2.u = uint(b_.u_.high) * uint(a_.u_.high) + uint(temp.u_.high);
764 
765  uint c = AddTwoWords(res_low1.u, res_low2.u, 0, &res_low2.u);
766  AddTwoWords(res_high1.u, res_high2.u, c, &res_high2.u); // there is no carry from here
767 
768  *result_high = res_high2.u;
769  *result_low = res_low2.u;
770 
771  #endif
772  }
773 
774 
775 
776 
796  template<uint value_size>
797  void UInt<value_size>::DivTwoWords(uint a, uint b, uint c, uint * r, uint * rest)
798  {
799  // (a < c ) for the result to be one word
800  TTMATH_ASSERT( c != 0 && a < c )
801 
802  #ifdef TTMATH_PLATFORM32
803 
804  union
805  {
806  struct
807  {
808  uint low; // 32 bits
809  uint high; // 32 bits
810  } u_;
811 
812  ulint u; // 64 bits
813  } ab;
814 
815  ab.u_.high = a;
816  ab.u_.low = b;
817 
818  *r = uint(ab.u / c);
819  *rest = uint(ab.u % c);
820 
821  #else
822 
823  uint_ c_;
824  c_.u = c;
825 
826 
827  if( a == 0 )
828  {
829  *r = b / c;
830  *rest = b % c;
831  }
832  else
833  if( c_.u_.high == 0 )
834  {
835  // higher half of 'c' is zero
836  // then higher half of 'a' is zero too (look at the asserts at the beginning - 'a' is smaller than 'c')
837  uint_ a_, b_, res_, temp1, temp2;
838 
839  a_.u = a;
840  b_.u = b;
841 
842  temp1.u_.high = a_.u_.low;
843  temp1.u_.low = b_.u_.high;
844 
845  res_.u_.high = (unsigned int)(temp1.u / c);
846  temp2.u_.high = (unsigned int)(temp1.u % c);
847  temp2.u_.low = b_.u_.low;
848 
849  res_.u_.low = (unsigned int)(temp2.u / c);
850  *rest = temp2.u % c;
851 
852  *r = res_.u;
853  }
854  else
855  {
856  return DivTwoWords2(a, b, c, r, rest);
857  }
858 
859  #endif
860  }
861 
862 
863 #ifdef TTMATH_PLATFORM64
864 
865 
872  template<uint value_size>
873  void UInt<value_size>::DivTwoWords2(uint a, uint b, uint c, uint * r, uint * rest)
874  {
875  // a is not zero
876  // c_.u_.high is not zero
877 
878  uint_ a_, b_, c_, u_, q_;
879  unsigned int u3; // 32 bit
880 
881  a_.u = a;
882  b_.u = b;
883  c_.u = c;
884 
885  // normalizing
886  uint d = DivTwoWordsNormalize(a_, b_, c_);
887 
888  // loop from j=1 to j=0
889  // the first step (for j=2) is skipped because our result is only in one word,
890  // (first 'q' were 0 and nothing would be changed)
891  u_.u_.high = a_.u_.high;
892  u_.u_.low = a_.u_.low;
893  u3 = b_.u_.high;
894  q_.u_.high = DivTwoWordsCalculate(u_, u3, c_);
895  MultiplySubtract(u_, u3, q_.u_.high, c_);
896 
897  u_.u_.high = u_.u_.low;
898  u_.u_.low = u3;
899  u3 = b_.u_.low;
900  q_.u_.low = DivTwoWordsCalculate(u_, u3, c_);
901  MultiplySubtract(u_, u3, q_.u_.low, c_);
902 
903  *r = q_.u;
904 
905  // unnormalizing for the remainder
906  u_.u_.high = u_.u_.low;
907  u_.u_.low = u3;
908  *rest = DivTwoWordsUnnormalize(u_.u, d);
909  }
910 
911 
912 
913 
914  template<uint value_size>
915  uint UInt<value_size>::DivTwoWordsNormalize(uint_ & a_, uint_ & b_, uint_ & c_)
916  {
917  uint d = 0;
918 
919  for( ; (c_.u & TTMATH_UINT_HIGHEST_BIT) == 0 ; ++d )
920  {
921  c_.u = c_.u << 1;
922 
923  uint bc = b_.u & TTMATH_UINT_HIGHEST_BIT; // carry from 'b'
924 
925  b_.u = b_.u << 1;
926  a_.u = a_.u << 1; // carry bits from 'a' are simply skipped
927 
928  if( bc )
929  a_.u = a_.u | 1;
930  }
931 
932  return d;
933  }
934 
935 
936  template<uint value_size>
937  uint UInt<value_size>::DivTwoWordsUnnormalize(uint u, uint d)
938  {
939  if( d == 0 )
940  return u;
941 
942  u = u >> d;
943 
944  return u;
945  }
946 
947 
948  template<uint value_size>
949  unsigned int UInt<value_size>::DivTwoWordsCalculate(uint_ u_, unsigned int u3, uint_ v_)
950  {
951  bool next_test;
952  uint_ qp_, rp_, temp_;
953 
954  qp_.u = u_.u / uint(v_.u_.high);
955  rp_.u = u_.u % uint(v_.u_.high);
956 
957  TTMATH_ASSERT( qp_.u_.high==0 || qp_.u_.high==1 )
958 
959  do
960  {
961  bool decrease = false;
962 
963  if( qp_.u_.high == 1 )
964  decrease = true;
965  else
966  {
967  temp_.u_.high = rp_.u_.low;
968  temp_.u_.low = u3;
969 
970  if( qp_.u * uint(v_.u_.low) > temp_.u )
971  decrease = true;
972  }
973 
974  next_test = false;
975 
976  if( decrease )
977  {
978  --qp_.u;
979  rp_.u += v_.u_.high;
980 
981  if( rp_.u_.high == 0 )
982  next_test = true;
983  }
984  }
985  while( next_test );
986 
987  return qp_.u_.low;
988  }
989 
990 
991  template<uint value_size>
992  void UInt<value_size>::MultiplySubtract(uint_ & u_, unsigned int & u3, unsigned int & q, uint_ v_)
993  {
994  uint_ temp_;
995 
996  uint res_high;
997  uint res_low;
998 
999  MulTwoWords(v_.u, q, &res_high, &res_low);
1000 
1001  uint_ sub_res_high_;
1002  uint_ sub_res_low_;
1003 
1004  temp_.u_.high = u_.u_.low;
1005  temp_.u_.low = u3;
1006 
1007  uint c = SubTwoWords(temp_.u, res_low, 0, &sub_res_low_.u);
1008 
1009  temp_.u_.high = 0;
1010  temp_.u_.low = u_.u_.high;
1011  c = SubTwoWords(temp_.u, res_high, c, &sub_res_high_.u);
1012 
1013  if( c )
1014  {
1015  --q;
1016 
1017  c = AddTwoWords(sub_res_low_.u, v_.u, 0, &sub_res_low_.u);
1018  AddTwoWords(sub_res_high_.u, 0, c, &sub_res_high_.u);
1019  }
1020 
1021  u_.u_.high = sub_res_high_.u_.low;
1022  u_.u_.low = sub_res_low_.u_.high;
1023  u3 = sub_res_low_.u_.low;
1024  }
1025 
1026 #endif // #ifdef TTMATH_PLATFORM64
1027 
1028 
1029 
1030 } //namespace
1031 
1032 
1033 #endif //ifdef TTMATH_NOASM
1034 #endif
1035 
1036 
1037 
1038 
#define TTMATH_UINT_HIGHEST_BIT
Definition: ttmathtypes.h:212
a namespace for the TTMath library
Definition: ttmath.h:62
LibTypeCode
Definition: ttmathtypes.h:368
#define TTMATH_UINT_MAX_VALUE
Definition: ttmathtypes.h:218
#define TTMATH_BITS_PER_UINT
Definition: ttmathtypes.h:207
uint64_t ulint
Definition: ttmathtypes.h:200
unsigned int uint
Definition: ttmathtypes.h:186