All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 (new) 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 
42 #ifdef TTMATH_NOASM
43 
52 namespace ttmath
53 {
54 
65  template<uint value_size>
66  const char * UInt<value_size>::LibTypeStr()
67  {
68  #ifdef TTMATH_PLATFORM32
69  static const char info[] = "no_asm_32";
70  #endif
71 
72  #ifdef TTMATH_PLATFORM64
73  static const char info[] = "no_asm_64";
74  #endif
75 
76  return info;
77  }
78 
79 
83  template<uint value_size>
85  {
86  #ifdef TTMATH_PLATFORM32
88  #endif
89 
90  #ifdef TTMATH_PLATFORM64
91  LibTypeCode info = no_asm_64;
92  #endif
93 
94  return info;
95  }
96 
97 
104  template<uint value_size>
105  uint UInt<value_size>::AddTwoWords(uint a, uint b, uint carry, uint * result)
106  {
107  uint temp;
108 
109  if( carry == 0 )
110  {
111  temp = a + b;
112 
113  if( temp < a )
114  carry = 1;
115  }
116  else
117  {
118  carry = 1;
119  temp = a + b + carry;
120 
121  if( temp > a ) // !(temp<=a)
122  carry = 0;
123  }
124 
125  *result = temp;
126 
127  return carry;
128  }
129 
130 
131 
140  template<uint value_size>
141  uint UInt<value_size>::Add(const UInt<value_size> & ss2, uint c)
142  {
143  uint i;
144 
145  for(i=0 ; i<value_size ; ++i)
146  c = AddTwoWords(table[i], ss2.table[i], c, &table[i]);
147 
148  TTMATH_LOGC("UInt::Add", c)
149 
150  return c;
151  }
152 
153 
171  template<uint value_size>
172  uint UInt<value_size>::AddInt(uint value, uint index)
173  {
174  uint i, c;
175 
176  TTMATH_ASSERT( index < value_size )
177 
178 
179  c = AddTwoWords(table[index], value, 0, &table[index]);
180 
181  for(i=index+1 ; i<value_size && c ; ++i)
182  c = AddTwoWords(table[i], 0, c, &table[i]);
183 
184  TTMATH_LOGC("UInt::AddInt", c)
185 
186  return c;
187  }
188 
189 
190 
191 
192 
223  template<uint value_size>
224  uint UInt<value_size>::AddTwoInts(uint x2, uint x1, uint index)
225  {
226  uint i, c;
227 
228  TTMATH_ASSERT( index < value_size - 1 )
229 
230 
231  c = AddTwoWords(table[index], x1, 0, &table[index]);
232  c = AddTwoWords(table[index+1], x2, c, &table[index+1]);
233 
234  for(i=index+2 ; i<value_size && c ; ++i)
235  c = AddTwoWords(table[i], 0, c, &table[i]);
236 
237  TTMATH_LOGC("UInt::AddTwoInts", c)
238 
239  return c;
240  }
241 
242 
243 
264  template<uint value_size>
265  uint UInt<value_size>::AddVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result)
266  {
267  uint i, c = 0;
268 
269  TTMATH_ASSERT( ss1_size >= ss2_size )
270 
271  for(i=0 ; i<ss2_size ; ++i)
272  c = AddTwoWords(ss1[i], ss2[i], c, &result[i]);
273 
274  for( ; i<ss1_size ; ++i)
275  c = AddTwoWords(ss1[i], 0, c, &result[i]);
276 
277  TTMATH_VECTOR_LOGC("UInt::AddVector", c, result, ss1_size)
278 
279  return c;
280  }
281 
282 
283 
284 
291  template<uint value_size>
292  uint UInt<value_size>::SubTwoWords(uint a, uint b, uint carry, uint * result)
293  {
294  if( carry == 0 )
295  {
296  *result = a - b;
297 
298  if( a < b )
299  carry = 1;
300  }
301  else
302  {
303  carry = 1;
304  *result = a - b - carry;
305 
306  if( a > b ) // !(a <= b )
307  carry = 0;
308  }
309 
310  return carry;
311  }
312 
313 
314 
315 
324  template<uint value_size>
325  uint UInt<value_size>::Sub(const UInt<value_size> & ss2, uint c)
326  {
327  uint i;
328 
329  for(i=0 ; i<value_size ; ++i)
330  c = SubTwoWords(table[i], ss2.table[i], c, &table[i]);
331 
332  TTMATH_LOGC("UInt::Sub", c)
333 
334  return c;
335  }
336 
337 
338 
339 
357  template<uint value_size>
358  uint UInt<value_size>::SubInt(uint value, uint index)
359  {
360  uint i, c;
361 
362  TTMATH_ASSERT( index < value_size )
363 
364 
365  c = SubTwoWords(table[index], value, 0, &table[index]);
366 
367  for(i=index+1 ; i<value_size && c ; ++i)
368  c = SubTwoWords(table[i], 0, c, &table[i]);
369 
370  TTMATH_LOGC("UInt::SubInt", c)
371 
372  return c;
373  }
374 
375 
397  template<uint value_size>
398  uint UInt<value_size>::SubVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result)
399  {
400  uint i, c = 0;
401 
402  TTMATH_ASSERT( ss1_size >= ss2_size )
403 
404  for(i=0 ; i<ss2_size ; ++i)
405  c = SubTwoWords(ss1[i], ss2[i], c, &result[i]);
406 
407  for( ; i<ss1_size ; ++i)
408  c = SubTwoWords(ss1[i], 0, c, &result[i]);
409 
410  TTMATH_VECTOR_LOGC("UInt::SubVector", c, result, ss1_size)
411 
412  return c;
413  }
414 
415 
416 
429  template<uint value_size>
430  uint UInt<value_size>::Rcl2_one(uint c)
431  {
432  uint i, new_c;
433 
434  if( c != 0 )
435  c = 1;
436 
437  for(i=0 ; i<value_size ; ++i)
438  {
439  new_c = (table[i] & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0;
440  table[i] = (table[i] << 1) | c;
441  c = new_c;
442  }
443 
444  TTMATH_LOGC("UInt::Rcl2_one", c)
445 
446  return c;
447  }
448 
449 
450 
451 
452 
453 
454 
467  template<uint value_size>
468  uint UInt<value_size>::Rcr2_one(uint c)
469  {
470  sint i; // signed i
471  uint new_c;
472 
473  if( c != 0 )
475 
476  for(i=sint(value_size)-1 ; i>=0 ; --i)
477  {
478  new_c = (table[i] & 1) ? TTMATH_UINT_HIGHEST_BIT : 0;
479  table[i] = (table[i] >> 1) | c;
480  c = new_c;
481  }
482 
483  c = (c != 0)? 1 : 0;
484 
485  TTMATH_LOGC("UInt::Rcr2_one", c)
486 
487  return c;
488  }
489 
490 
491 
492 
505  template<uint value_size>
506  uint UInt<value_size>::Rcl2(uint bits, uint c)
507  {
508  TTMATH_ASSERT( bits>0 && bits<TTMATH_BITS_PER_UINT )
509 
510  uint move = TTMATH_BITS_PER_UINT - bits;
511  uint i, new_c;
512 
513  if( c != 0 )
514  c = TTMATH_UINT_MAX_VALUE >> move;
515 
516  for(i=0 ; i<value_size ; ++i)
517  {
518  new_c = table[i] >> move;
519  table[i] = (table[i] << bits) | c;
520  c = new_c;
521  }
522 
523  TTMATH_LOGC("UInt::Rcl2", (c & 1))
524 
525  return (c & 1);
526  }
527 
528 
529 
530 
543  template<uint value_size>
544  uint UInt<value_size>::Rcr2(uint bits, uint c)
545  {
546  TTMATH_ASSERT( bits>0 && bits<TTMATH_BITS_PER_UINT )
547 
548  uint move = TTMATH_BITS_PER_UINT - bits;
549  sint i; // signed
550  uint new_c;
551 
552  if( c != 0 )
553  c = TTMATH_UINT_MAX_VALUE << move;
554 
555  for(i=value_size-1 ; i>=0 ; --i)
556  {
557  new_c = table[i] << move;
558  table[i] = (table[i] >> bits) | c;
559  c = new_c;
560  }
561 
562  c = (c & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0;
563 
564  TTMATH_LOGC("UInt::Rcr2", c)
565 
566  return c;
567  }
568 
569 
570 
571 
576  template<uint value_size>
577  sint UInt<value_size>::FindLeadingBitInWord(uint x)
578  {
579  if( x == 0 )
580  return -1;
581 
582  uint bit = TTMATH_BITS_PER_UINT - 1;
583 
584  while( (x & TTMATH_UINT_HIGHEST_BIT) == 0 )
585  {
586  x = x << 1;
587  --bit;
588  }
589 
590  return bit;
591  }
592 
593 
594 
599  template<uint value_size>
601  {
602  if( x == 0 )
603  return -1;
604 
605  uint bit = 0;
606 
607  while( (x & 1) == 0 )
608  {
609  x = x >> 1;
610  ++bit;
611  }
612 
613  return bit;
614  }
615 
616 
617 
629  template<uint value_size>
631  {
633 
634  uint mask = 1;
635 
636  if( bit > 0 )
637  mask = mask << bit;
638 
639  uint last = value & mask;
640  value = value | mask;
641 
642  return (last != 0) ? 1 : 0;
643  }
644 
645 
646 
647 
648 
649 
666  template<uint value_size>
667  void UInt<value_size>::MulTwoWords(uint a, uint b, uint * result_high, uint * result_low)
668  {
669  #ifdef TTMATH_PLATFORM32
670 
671  /*
672  on 32bit platforms we have defined 'unsigned long long int' type known as 'ulint' in ttmath namespace
673  this type has 64 bits, then we're using only one multiplication: 32bit * 32bit = 64bit
674  */
675 
676  union uint_
677  {
678  struct
679  {
680  uint low; // 32 bits
681  uint high; // 32 bits
682  } u_;
683 
684  ulint u; // 64 bits
685  } res;
686 
687  res.u = ulint(a) * ulint(b); // multiply two 32bit words, the result has 64 bits
688 
689  *result_high = res.u_.high;
690  *result_low = res.u_.low;
691 
692  #else
693 
694  /*
695  64 bits platforms
696 
697  we don't have a native type which has 128 bits
698  then we're splitting 'a' and 'b' to 4 parts (high and low halves)
699  and using 4 multiplications (with additions and carry correctness)
700  */
701 
702  uint_ a_;
703  uint_ b_;
704  uint_ res_high1, res_high2;
705  uint_ res_low1, res_low2;
706 
707  a_.u = a;
708  b_.u = b;
709 
710  /*
711  the multiplication is as follows (schoolbook algorithm with O(n^2) ):
712 
713  32 bits 32 bits
714 
715  +--------------------------------+
716  | a_.u_.high | a_.u_.low |
717  +--------------------------------+
718  | b_.u_.high | b_.u_.low |
719  +--------------------------------+--------------------------------+
720  | res_high1.u | res_low1.u |
721  +--------------------------------+--------------------------------+
722  | res_high2.u | res_low2.u |
723  +--------------------------------+--------------------------------+
724 
725  64 bits 64 bits
726  */
727 
728 
729  uint_ temp;
730 
731  res_low1.u = uint(b_.u_.low) * uint(a_.u_.low);
732 
733  temp.u = uint(res_low1.u_.high) + uint(b_.u_.low) * uint(a_.u_.high);
734  res_low1.u_.high = temp.u_.low;
735  res_high1.u_.low = temp.u_.high;
736  res_high1.u_.high = 0;
737 
738  res_low2.u_.low = 0;
739  temp.u = uint(b_.u_.high) * uint(a_.u_.low);
740  res_low2.u_.high = temp.u_.low;
741 
742  res_high2.u = uint(b_.u_.high) * uint(a_.u_.high) + uint(temp.u_.high);
743 
744  uint c = AddTwoWords(res_low1.u, res_low2.u, 0, &res_low2.u);
745  AddTwoWords(res_high1.u, res_high2.u, c, &res_high2.u); // there is no carry from here
746 
747  *result_high = res_high2.u;
748  *result_low = res_low2.u;
749 
750  #endif
751  }
752 
753 
754 
755 
775  template<uint value_size>
776  void UInt<value_size>::DivTwoWords(uint a, uint b, uint c, uint * r, uint * rest)
777  {
778  // (a < c ) for the result to be one word
779  TTMATH_ASSERT( c != 0 && a < c )
780 
781  #ifdef TTMATH_PLATFORM32
782 
783  union
784  {
785  struct
786  {
787  uint low; // 32 bits
788  uint high; // 32 bits
789  } u_;
790 
791  ulint u; // 64 bits
792  } ab;
793 
794  ab.u_.high = a;
795  ab.u_.low = b;
796 
797  *r = uint(ab.u / c);
798  *rest = uint(ab.u % c);
799 
800  #else
801 
802  uint_ c_;
803  c_.u = c;
804 
805 
806  if( a == 0 )
807  {
808  *r = b / c;
809  *rest = b % c;
810  }
811  else
812  if( c_.u_.high == 0 )
813  {
814  // higher half of 'c' is zero
815  // then higher half of 'a' is zero too (look at the asserts at the beginning - 'a' is smaller than 'c')
816  uint_ a_, b_, res_, temp1, temp2;
817 
818  a_.u = a;
819  b_.u = b;
820 
821  temp1.u_.high = a_.u_.low;
822  temp1.u_.low = b_.u_.high;
823 
824  res_.u_.high = (unsigned int)(temp1.u / c);
825  temp2.u_.high = (unsigned int)(temp1.u % c);
826  temp2.u_.low = b_.u_.low;
827 
828  res_.u_.low = (unsigned int)(temp2.u / c);
829  *rest = temp2.u % c;
830 
831  *r = res_.u;
832  }
833  else
834  {
835  return DivTwoWords2(a, b, c, r, rest);
836  }
837 
838  #endif
839  }
840 
841 
842 #ifdef TTMATH_PLATFORM64
843 
844 
851  template<uint value_size>
852  void UInt<value_size>::DivTwoWords2(uint a, uint b, uint c, uint * r, uint * rest)
853  {
854  // a is not zero
855  // c_.u_.high is not zero
856 
857  uint_ a_, b_, c_, u_, q_;
858  unsigned int u3; // 32 bit
859 
860  a_.u = a;
861  b_.u = b;
862  c_.u = c;
863 
864  // normalizing
865  uint d = DivTwoWordsNormalize(a_, b_, c_);
866 
867  // loop from j=1 to j=0
868  // the first step (for j=2) is skipped because our result is only in one word,
869  // (first 'q' were 0 and nothing would be changed)
870  u_.u_.high = a_.u_.high;
871  u_.u_.low = a_.u_.low;
872  u3 = b_.u_.high;
873  q_.u_.high = DivTwoWordsCalculate(u_, u3, c_);
874  MultiplySubtract(u_, u3, q_.u_.high, c_);
875 
876  u_.u_.high = u_.u_.low;
877  u_.u_.low = u3;
878  u3 = b_.u_.low;
879  q_.u_.low = DivTwoWordsCalculate(u_, u3, c_);
880  MultiplySubtract(u_, u3, q_.u_.low, c_);
881 
882  *r = q_.u;
883 
884  // unnormalizing for the remainder
885  u_.u_.high = u_.u_.low;
886  u_.u_.low = u3;
887  *rest = DivTwoWordsUnnormalize(u_.u, d);
888  }
889 
890 
891 
892 
893  template<uint value_size>
894  uint UInt<value_size>::DivTwoWordsNormalize(uint_ & a_, uint_ & b_, uint_ & c_)
895  {
896  uint d = 0;
897 
898  for( ; (c_.u & TTMATH_UINT_HIGHEST_BIT) == 0 ; ++d )
899  {
900  c_.u = c_.u << 1;
901 
902  uint bc = b_.u & TTMATH_UINT_HIGHEST_BIT; // carry from 'b'
903 
904  b_.u = b_.u << 1;
905  a_.u = a_.u << 1; // carry bits from 'a' are simply skipped
906 
907  if( bc )
908  a_.u = a_.u | 1;
909  }
910 
911  return d;
912  }
913 
914 
915  template<uint value_size>
916  uint UInt<value_size>::DivTwoWordsUnnormalize(uint u, uint d)
917  {
918  if( d == 0 )
919  return u;
920 
921  u = u >> d;
922 
923  return u;
924  }
925 
926 
927  template<uint value_size>
928  unsigned int UInt<value_size>::DivTwoWordsCalculate(uint_ u_, unsigned int u3, uint_ v_)
929  {
930  bool next_test;
931  uint_ qp_, rp_, temp_;
932 
933  qp_.u = u_.u / uint(v_.u_.high);
934  rp_.u = u_.u % uint(v_.u_.high);
935 
936  TTMATH_ASSERT( qp_.u_.high==0 || qp_.u_.high==1 )
937 
938  do
939  {
940  bool decrease = false;
941 
942  if( qp_.u_.high == 1 )
943  decrease = true;
944  else
945  {
946  temp_.u_.high = rp_.u_.low;
947  temp_.u_.low = u3;
948 
949  if( qp_.u * uint(v_.u_.low) > temp_.u )
950  decrease = true;
951  }
952 
953  next_test = false;
954 
955  if( decrease )
956  {
957  --qp_.u;
958  rp_.u += v_.u_.high;
959 
960  if( rp_.u_.high == 0 )
961  next_test = true;
962  }
963  }
964  while( next_test );
965 
966  return qp_.u_.low;
967  }
968 
969 
970  template<uint value_size>
971  void UInt<value_size>::MultiplySubtract(uint_ & u_, unsigned int & u3, unsigned int & q, uint_ v_)
972  {
973  uint_ temp_;
974 
975  uint res_high;
976  uint res_low;
977 
978  MulTwoWords(v_.u, q, &res_high, &res_low);
979 
980  uint_ sub_res_high_;
981  uint_ sub_res_low_;
982 
983  temp_.u_.high = u_.u_.low;
984  temp_.u_.low = u3;
985 
986  uint c = SubTwoWords(temp_.u, res_low, 0, &sub_res_low_.u);
987 
988  temp_.u_.high = 0;
989  temp_.u_.low = u_.u_.high;
990  c = SubTwoWords(temp_.u, res_high, c, &sub_res_high_.u);
991 
992  if( c )
993  {
994  --q;
995 
996  c = AddTwoWords(sub_res_low_.u, v_.u, 0, &sub_res_low_.u);
997  AddTwoWords(sub_res_high_.u, 0, c, &sub_res_high_.u);
998  }
999 
1000  u_.u_.high = sub_res_high_.u_.low;
1001  u_.u_.low = sub_res_low_.u_.high;
1002  u3 = sub_res_low_.u_.low;
1003  }
1004 
1005 #endif // #ifdef TTMATH_PLATFORM64
1006 
1007 
1008 
1009 } //namespace
1010 
1011 
1012 #endif //ifdef TTMATH_NOASM
1013 #endif
1014 
1015 
1016 
1017 
Definition: ttmathtypes.h:342
static const char * LibTypeStr()
static void DivTwoWords(uint a, uint b, uint c, uint *r, uint *rest)
NetworKit::index index
Definition: BloomFilter.h:16
static LibTypeCode LibType()
uint Sub(const UInt< value_size > &ss2, uint c=0)
#define TTMATH_LOGC(msg, carry)
Definition: ttmathtypes.h:672
uint Add(const UInt< value_size > &ss2, uint c=0)
static sint FindLowestBitInWord(uint x)
#define TTMATH_UINT_HIGHEST_BIT
Definition: ttmathtypes.h:189
signed int sint
Definition: ttmathtypes.h:164
LibTypeCode
Definition: ttmathtypes.h:335
#define TTMATH_UINT_MAX_VALUE
Definition: ttmathtypes.h:195
#define TTMATH_ASSERT(expression)
Definition: ttmathtypes.h:660
static uint AddTwoWords(uint a, uint b, uint carry, uint *result)
#define TTMATH_BITS_PER_UINT
Definition: ttmathtypes.h:184
uint64_t ulint
Definition: ttmathtypes.h:177
Definition: ttmathtypes.h:341
unsigned int uint
Definition: ttmathtypes.h:163
#define TTMATH_VECTOR_LOGC(msg, carry, vector, len)
Definition: ttmathtypes.h:674
static uint SetBitInWord(uint &value, uint bit)