All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ttmathuint_x86_64.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 
39 #ifndef headerfilettmathuint_x86_64
40 #define headerfilettmathuint_x86_64
41 
42 
43 #ifndef TTMATH_NOASM
44 #ifdef TTMATH_PLATFORM64
45 
46 
54 #ifndef __GNUC__
55 #include <intrin.h>
56 #endif
57 
58 
59 namespace ttmath
60 {
61 
62  #ifndef __GNUC__
63 
64  extern "C"
65  {
66  uint __fastcall ttmath_adc_x64(uint* p1, const uint* p2, uint nSize, uint c);
67  uint __fastcall ttmath_addindexed_x64(uint* p1, uint nSize, uint nPos, uint nValue);
68  uint __fastcall ttmath_addindexed2_x64(uint* p1, uint nSize, uint nPos, uint nValue1, uint nValue2);
69  uint __fastcall ttmath_addvector_x64(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result);
70  uint __fastcall ttmath_sbb_x64(uint* p1, const uint* p2, uint nSize, uint c);
71  uint __fastcall ttmath_subindexed_x64(uint* p1, uint nSize, uint nPos, uint nValue);
72  uint __fastcall ttmath_subvector_x64(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result);
73  uint __fastcall ttmath_rcl_x64(uint* p1, uint nSize, uint nLowestBit);
74  uint __fastcall ttmath_rcr_x64(uint* p1, uint nSize, uint nLowestBit);
75  uint __fastcall ttmath_div_x64(uint* pnValHi, uint* pnValLo, uint nDiv);
76  uint __fastcall ttmath_rcl2_x64(uint* p1, uint nSize, uint nBits, uint c);
77  uint __fastcall ttmath_rcr2_x64(uint* p1, uint nSize, uint nBits, uint c);
78  };
79  #endif
80 
81 
92  template<uint value_size>
93  const char * UInt<value_size>::LibTypeStr()
94  {
95  #ifndef __GNUC__
96  static const char info[] = "asm_vc_64";
97  #endif
98 
99  #ifdef __GNUC__
100  static const char info[] = "asm_gcc_64";
101  #endif
102 
103  return info;
104  }
105 
106 
110  template<uint value_size>
112  {
113  #ifndef __GNUC__
115  #endif
116 
117  #ifdef __GNUC__
118  LibTypeCode info = asm_gcc_64;
119  #endif
120 
121  return info;
122  }
123 
124 
142  template<uint value_size>
143  uint UInt<value_size>::Add(const UInt<value_size> & ss2, uint c)
144  {
145  uint b = value_size;
146  uint * p1 = table;
147  const uint * p2 = ss2.table;
148 
149  // we don't have to use TTMATH_REFERENCE_ASSERT here
150  // this algorithm doesn't require it
151 
152  #ifndef __GNUC__
153  c = ttmath_adc_x64(p1,p2,b,c);
154  #endif
155 
156  #ifdef __GNUC__
157  uint dummy, dummy2;
158 
159  /*
160  this part should be compiled with gcc
161  */
162  __asm__ __volatile__(
163 
164  "xorq %%rdx, %%rdx \n"
165  "negq %%rax \n" // CF=1 if rax!=0 , CF=0 if rax==0
166 
167  "1: \n"
168  "movq (%%rsi,%%rdx,8), %%rax \n"
169  "adcq %%rax, (%%rbx,%%rdx,8) \n"
170 
171  "incq %%rdx \n"
172  "decq %%rcx \n"
173  "jnz 1b \n"
174 
175  "adcq %%rcx, %%rcx \n"
176 
177  : "=c" (c), "=a" (dummy), "=d" (dummy2)
178  : "0" (b), "1" (c), "b" (p1), "S" (p2)
179  : "cc", "memory" );
180 
181  #endif
182 
183  TTMATH_LOGC("UInt::Add", c)
184 
185  return c;
186  }
187 
188 
189 
210  template<uint value_size>
211  uint UInt<value_size>::AddInt(uint value, uint index)
212  {
213  uint b = value_size;
214  uint * p1 = table;
215  uint c;
216 
217  TTMATH_ASSERT( index < value_size )
218 
219  #ifndef __GNUC__
220  c = ttmath_addindexed_x64(p1,b,index,value);
221  #endif
222 
223 
224  #ifdef __GNUC__
225  uint dummy, dummy2;
226 
227  __asm__ __volatile__(
228 
229  "subq %%rdx, %%rcx \n"
230 
231  "1: \n"
232  "addq %%rax, (%%rbx,%%rdx,8) \n"
233  "jnc 2f \n"
234 
235  "movq $1, %%rax \n"
236  "incq %%rdx \n"
237  "decq %%rcx \n"
238  "jnz 1b \n"
239 
240  "2: \n"
241  "setc %%al \n"
242  "movzx %%al, %%rdx \n"
243 
244  : "=d" (c), "=a" (dummy), "=c" (dummy2)
245  : "0" (index), "1" (value), "2" (b), "b" (p1)
246  : "cc", "memory" );
247 
248  #endif
249 
250  TTMATH_LOGC("UInt::AddInt", c)
251 
252  return c;
253  }
254 
255 
256 
289  template<uint value_size>
290  uint UInt<value_size>::AddTwoInts(uint x2, uint x1, uint index)
291  {
292  uint b = value_size;
293  uint * p1 = table;
294  uint c;
295 
296  TTMATH_ASSERT( index < value_size - 1 )
297 
298  #ifndef __GNUC__
299  c = ttmath_addindexed2_x64(p1,b,index,x1,x2);
300  #endif
301 
302 
303  #ifdef __GNUC__
304  uint dummy, dummy2;
305 
306  __asm__ __volatile__(
307 
308  "subq %%rdx, %%rcx \n"
309 
310  "addq %%rsi, (%%rbx,%%rdx,8) \n"
311  "incq %%rdx \n"
312  "decq %%rcx \n"
313 
314  "1: \n"
315  "adcq %%rax, (%%rbx,%%rdx,8) \n"
316  "jnc 2f \n"
317 
318  "mov $0, %%rax \n"
319  "incq %%rdx \n"
320  "decq %%rcx \n"
321  "jnz 1b \n"
322 
323  "2: \n"
324  "setc %%al \n"
325  "movzx %%al, %%rax \n"
326 
327  : "=a" (c), "=c" (dummy), "=d" (dummy2)
328  : "0" (x2), "1" (b), "2" (index), "b" (p1), "S" (x1)
329  : "cc", "memory" );
330 
331  #endif
332 
333  TTMATH_LOGC("UInt::AddTwoInts", c)
334 
335  return c;
336  }
337 
338 
339 
360  template<uint value_size>
361  uint UInt<value_size>::AddVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result)
362  {
363  TTMATH_ASSERT( ss1_size >= ss2_size )
364 
365  uint c;
366 
367  #ifndef __GNUC__
368  c = ttmath_addvector_x64(ss1, ss2, ss1_size, ss2_size, result);
369  #endif
370 
371 
372  #ifdef __GNUC__
373  uint dummy1, dummy2, dummy3;
374  uint rest = ss1_size - ss2_size;
375 
376  // this part should be compiled with gcc
377 
378  __asm__ __volatile__(
379  "mov %%rdx, %%r8 \n"
380  "xor %%rdx, %%rdx \n" // rdx = 0, cf = 0
381  "1: \n"
382  "mov (%%rsi,%%rdx,8), %%rax \n"
383  "adc (%%rbx,%%rdx,8), %%rax \n"
384  "mov %%rax, (%%rdi,%%rdx,8) \n"
385 
386  "inc %%rdx \n"
387  "dec %%rcx \n"
388  "jnz 1b \n"
389 
390  "adc %%rcx, %%rcx \n" // rcx has the cf state
391 
392  "or %%r8, %%r8 \n"
393  "jz 3f \n"
394 
395  "xor %%rbx, %%rbx \n" // ebx = 0
396  "neg %%rcx \n" // setting cf from rcx
397  "mov %%r8, %%rcx \n" // rcx=rest and is != 0
398  "2: \n"
399  "mov (%%rsi, %%rdx, 8), %%rax \n"
400  "adc %%rbx, %%rax \n"
401  "mov %%rax, (%%rdi, %%rdx, 8) \n"
402 
403  "inc %%rdx \n"
404  "dec %%rcx \n"
405  "jnz 2b \n"
406 
407  "adc %%rcx, %%rcx \n"
408  "3: \n"
409 
410  : "=a" (dummy1), "=b" (dummy2), "=c" (c), "=d" (dummy3)
411  : "1" (ss2), "2" (ss2_size), "3" (rest), "S" (ss1), "D" (result)
412  : "%r8", "cc", "memory" );
413 
414  #endif
415 
416  TTMATH_VECTOR_LOGC("UInt::AddVector", c, result, ss1_size)
417 
418  return c;
419  }
420 
421 
422 
433  template<uint value_size>
434  uint UInt<value_size>::Sub(const UInt<value_size> & ss2, uint c)
435  {
436  uint b = value_size;
437  uint * p1 = table;
438  const uint * p2 = ss2.table;
439 
440  // we don't have to use TTMATH_REFERENCE_ASSERT here
441  // this algorithm doesn't require it
442 
443  #ifndef __GNUC__
444  c = ttmath_sbb_x64(p1,p2,b,c);
445  #endif
446 
447 
448  #ifdef __GNUC__
449  uint dummy, dummy2;
450 
451  __asm__ __volatile__(
452 
453  "xorq %%rdx, %%rdx \n"
454  "negq %%rax \n" // CF=1 if rax!=0 , CF=0 if rax==0
455 
456  "1: \n"
457  "movq (%%rsi,%%rdx,8), %%rax \n"
458  "sbbq %%rax, (%%rbx,%%rdx,8) \n"
459 
460  "incq %%rdx \n"
461  "decq %%rcx \n"
462  "jnz 1b \n"
463 
464  "adcq %%rcx, %%rcx \n"
465 
466  : "=c" (c), "=a" (dummy), "=d" (dummy2)
467  : "0" (b), "1" (c), "b" (p1), "S" (p2)
468  : "cc", "memory" );
469 
470  #endif
471 
472  TTMATH_LOGC("UInt::Sub", c)
473 
474  return c;
475  }
476 
477 
478 
498  template<uint value_size>
499  uint UInt<value_size>::SubInt(uint value, uint index)
500  {
501  uint b = value_size;
502  uint * p1 = table;
503  uint c;
504 
505  TTMATH_ASSERT( index < value_size )
506 
507  #ifndef __GNUC__
508  c = ttmath_subindexed_x64(p1,b,index,value);
509  #endif
510 
511 
512  #ifdef __GNUC__
513  uint dummy, dummy2;
514 
515  __asm__ __volatile__(
516 
517  "subq %%rdx, %%rcx \n"
518 
519  "1: \n"
520  "subq %%rax, (%%rbx,%%rdx,8) \n"
521  "jnc 2f \n"
522 
523  "movq $1, %%rax \n"
524  "incq %%rdx \n"
525  "decq %%rcx \n"
526  "jnz 1b \n"
527 
528  "2: \n"
529  "setc %%al \n"
530  "movzx %%al, %%rdx \n"
531 
532  : "=d" (c), "=a" (dummy), "=c" (dummy2)
533  : "0" (index), "1" (value), "2" (b), "b" (p1)
534  : "cc", "memory" );
535 
536  #endif
537 
538  TTMATH_LOGC("UInt::SubInt", c)
539 
540  return c;
541  }
542 
543 
565  template<uint value_size>
566  uint UInt<value_size>::SubVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result)
567  {
568  TTMATH_ASSERT( ss1_size >= ss2_size )
569 
570  uint c;
571 
572  #ifndef __GNUC__
573  c = ttmath_subvector_x64(ss1, ss2, ss1_size, ss2_size, result);
574  #endif
575 
576 
577  #ifdef __GNUC__
578 
579  // the asm code is nearly the same as in AddVector
580  // only two instructions 'adc' are changed to 'sbb'
581 
582  uint dummy1, dummy2, dummy3;
583  uint rest = ss1_size - ss2_size;
584 
585  __asm__ __volatile__(
586  "mov %%rdx, %%r8 \n"
587  "xor %%rdx, %%rdx \n" // rdx = 0, cf = 0
588  "1: \n"
589  "mov (%%rsi,%%rdx,8), %%rax \n"
590  "sbb (%%rbx,%%rdx,8), %%rax \n"
591  "mov %%rax, (%%rdi,%%rdx,8) \n"
592 
593  "inc %%rdx \n"
594  "dec %%rcx \n"
595  "jnz 1b \n"
596 
597  "adc %%rcx, %%rcx \n" // rcx has the cf state
598 
599  "or %%r8, %%r8 \n"
600  "jz 3f \n"
601 
602  "xor %%rbx, %%rbx \n" // ebx = 0
603  "neg %%rcx \n" // setting cf from rcx
604  "mov %%r8, %%rcx \n" // rcx=rest and is != 0
605  "2: \n"
606  "mov (%%rsi, %%rdx, 8), %%rax \n"
607  "sbb %%rbx, %%rax \n"
608  "mov %%rax, (%%rdi, %%rdx, 8) \n"
609 
610  "inc %%rdx \n"
611  "dec %%rcx \n"
612  "jnz 2b \n"
613 
614  "adc %%rcx, %%rcx \n"
615  "3: \n"
616 
617  : "=a" (dummy1), "=b" (dummy2), "=c" (c), "=d" (dummy3)
618  : "1" (ss2), "2" (ss2_size), "3" (rest), "S" (ss1), "D" (result)
619  : "%r8", "cc", "memory" );
620 
621  #endif
622 
623  TTMATH_VECTOR_LOGC("UInt::SubVector", c, result, ss1_size)
624 
625  return c;
626  }
627 
628 
643  template<uint value_size>
644  uint UInt<value_size>::Rcl2_one(uint c)
645  {
646  sint b = value_size;
647  uint * p1 = table;
648 
649 
650  #ifndef __GNUC__
651  c = ttmath_rcl_x64(p1,b,c);
652  #endif
653 
654 
655  #ifdef __GNUC__
656  uint dummy, dummy2;
657 
658  __asm__ __volatile__(
659 
660  "xorq %%rdx, %%rdx \n" // rdx=0
661  "negq %%rax \n" // CF=1 if rax!=0 , CF=0 if rax==0
662 
663  "1: \n"
664  "rclq $1, (%%rbx, %%rdx, 8) \n"
665 
666  "incq %%rdx \n"
667  "decq %%rcx \n"
668  "jnz 1b \n"
669 
670  "adcq %%rcx, %%rcx \n"
671 
672  : "=c" (c), "=a" (dummy), "=d" (dummy2)
673  : "0" (b), "1" (c), "b" (p1)
674  : "cc", "memory" );
675 
676  #endif
677 
678  TTMATH_LOGC("UInt::Rcl2_one", c)
679 
680  return c;
681  }
682 
683 
698  template<uint value_size>
699  uint UInt<value_size>::Rcr2_one(uint c)
700  {
701  sint b = value_size;
702  uint * p1 = table;
703 
704 
705  #ifndef __GNUC__
706  c = ttmath_rcr_x64(p1,b,c);
707  #endif
708 
709 
710  #ifdef __GNUC__
711  uint dummy;
712 
713  __asm__ __volatile__(
714 
715  "negq %%rax \n" // CF=1 if rax!=0 , CF=0 if rax==0
716 
717  "1: \n"
718  "rcrq $1, -8(%%rbx, %%rcx, 8) \n"
719 
720  "decq %%rcx \n"
721  "jnz 1b \n"
722 
723  "adcq %%rcx, %%rcx \n"
724 
725  : "=c" (c), "=a" (dummy)
726  : "0" (b), "1" (c), "b" (p1)
727  : "cc", "memory" );
728 
729  #endif
730 
731  TTMATH_LOGC("UInt::Rcr2_one", c)
732 
733  return c;
734  }
735 
736 
737 
752  template<uint value_size>
753  uint UInt<value_size>::Rcl2(uint bits, uint c)
754  {
755  TTMATH_ASSERT( bits>0 && bits<TTMATH_BITS_PER_UINT )
756 
757  uint b = value_size;
758  uint * p1 = table;
759 
760 
761  #ifndef __GNUC__
762  c = ttmath_rcl2_x64(p1,b,bits,c);
763  #endif
764 
765 
766  #ifdef __GNUC__
767  uint dummy, dummy2, dummy3;
768 
769  __asm__ __volatile__(
770 
771  "movq %%rcx, %%rsi \n"
772  "movq $64, %%rcx \n"
773  "subq %%rsi, %%rcx \n"
774  "movq $-1, %%rdx \n"
775  "shrq %%cl, %%rdx \n"
776  "movq %%rdx, %%r8 \n"
777  "movq %%rsi, %%rcx \n"
778 
779  "xorq %%rdx, %%rdx \n"
780  "movq %%rdx, %%rsi \n"
781  "orq %%rax, %%rax \n"
782  "cmovnz %%r8, %%rsi \n"
783 
784  "1: \n"
785  "rolq %%cl, (%%rbx,%%rdx,8) \n"
786 
787  "movq (%%rbx,%%rdx,8), %%rax \n"
788  "andq %%r8, %%rax \n"
789  "xorq %%rax, (%%rbx,%%rdx,8) \n"
790  "orq %%rsi, (%%rbx,%%rdx,8) \n"
791  "movq %%rax, %%rsi \n"
792 
793  "incq %%rdx \n"
794  "decq %%rdi \n"
795  "jnz 1b \n"
796 
797  "and $1, %%rax \n"
798 
799  : "=a" (c), "=D" (dummy), "=S" (dummy2), "=d" (dummy3)
800  : "0" (c), "1" (b), "b" (p1), "c" (bits)
801  : "%r8", "cc", "memory" );
802 
803  #endif
804 
805  TTMATH_LOGC("UInt::Rcl2", c)
806 
807  return c;
808  }
809 
810 
825  template<uint value_size>
826  uint UInt<value_size>::Rcr2(uint bits, uint c)
827  {
828  TTMATH_ASSERT( bits>0 && bits<TTMATH_BITS_PER_UINT )
829 
830  sint b = value_size;
831  uint * p1 = table;
832 
833 
834  #ifndef __GNUC__
835  c = ttmath_rcr2_x64(p1,b,bits,c);
836  #endif
837 
838 
839  #ifdef __GNUC__
840  uint dummy, dummy2, dummy3;
841 
842  __asm__ __volatile__(
843 
844  "movq %%rcx, %%rsi \n"
845  "movq $64, %%rcx \n"
846  "subq %%rsi, %%rcx \n"
847  "movq $-1, %%rdx \n"
848  "shlq %%cl, %%rdx \n"
849  "movq %%rdx, %%R8 \n"
850  "movq %%rsi, %%rcx \n"
851 
852  "xorq %%rdx, %%rdx \n"
853  "movq %%rdx, %%rsi \n"
854  "addq %%rdi, %%rdx \n"
855  "decq %%rdx \n"
856  "orq %%rax, %%rax \n"
857  "cmovnz %%R8, %%rsi \n"
858 
859  "1: \n"
860  "rorq %%cl, (%%rbx,%%rdx,8) \n"
861 
862  "movq (%%rbx,%%rdx,8), %%rax \n"
863  "andq %%R8, %%rax \n"
864  "xorq %%rax, (%%rbx,%%rdx,8) \n"
865  "orq %%rsi, (%%rbx,%%rdx,8) \n"
866  "movq %%rax, %%rsi \n"
867 
868  "decq %%rdx \n"
869  "decq %%rdi \n"
870  "jnz 1b \n"
871 
872  "rolq $1, %%rax \n"
873  "andq $1, %%rax \n"
874 
875  : "=a" (c), "=D" (dummy), "=S" (dummy2), "=d" (dummy3)
876  : "0" (c), "1" (b), "b" (p1), "c" (bits)
877  : "%r8", "cc", "memory" );
878 
879  #endif
880 
881  TTMATH_LOGC("UInt::Rcr2", c)
882 
883  return c;
884  }
885 
886 
887  /*
888  this method returns the number of the highest set bit in one 64-bit word
889  if the 'x' is zero this method returns '-1'
890 
891  ***this method is created only on a 64bit platform***
892  */
893  template<uint value_size>
894  sint UInt<value_size>::FindLeadingBitInWord(uint x)
895  {
896  sint result;
897 
898 
899  #ifndef __GNUC__
900 
901  unsigned long nIndex = 0;
902 
903  if( _BitScanReverse64(&nIndex,x) == 0 )
904  result = -1;
905  else
906  result = nIndex;
907 
908  #endif
909 
910 
911  #ifdef __GNUC__
912  uint dummy;
913 
914  __asm__ (
915 
916  "movq $-1, %1 \n"
917  "bsrq %2, %0 \n"
918  "cmovz %1, %0 \n"
919 
920  : "=r" (result), "=&r" (dummy)
921  : "r" (x)
922  : "cc" );
923 
924  #endif
925 
926 
927  return result;
928  }
929 
930 
931  /*
932  this method returns the number of the highest set bit in one 64-bit word
933  if the 'x' is zero this method returns '-1'
934 
935  ***this method is created only on a 64bit platform***
936  */
937  template<uint value_size>
939  {
940  sint result;
941 
942 
943  #ifndef __GNUC__
944 
945  unsigned long nIndex = 0;
946 
947  if( _BitScanForward64(&nIndex,x) == 0 )
948  result = -1;
949  else
950  result = nIndex;
951 
952  #endif
953 
954 
955  #ifdef __GNUC__
956  uint dummy;
957 
958  __asm__ (
959 
960  "movq $-1, %1 \n"
961  "bsfq %2, %0 \n"
962  "cmovz %1, %0 \n"
963 
964  : "=r" (result), "=&r" (dummy)
965  : "r" (x)
966  : "cc" );
967 
968  #endif
969 
970 
971  return result;
972  }
973 
974 
988  template<uint value_size>
990  {
992 
993  uint old_bit;
994  uint v = value;
995 
996 
997  #ifndef __GNUC__
998  old_bit = _bittestandset64((__int64*)&value,bit) != 0;
999  #endif
1000 
1001 
1002  #ifdef __GNUC__
1003 
1004  __asm__ (
1005 
1006  "btsq %%rbx, %%rax \n"
1007  "setc %%bl \n"
1008  "movzx %%bl, %%rbx \n"
1009 
1010  : "=a" (v), "=b" (old_bit)
1011  : "0" (v), "1" (bit)
1012  : "cc" );
1013 
1014  #endif
1015 
1016  value = v;
1017 
1018  return old_bit;
1019  }
1020 
1021 
1040  template<uint value_size>
1041  void UInt<value_size>::MulTwoWords(uint a, uint b, uint * result_high, uint * result_low)
1042  {
1043  /*
1044  we must use these temporary variables in order to inform the compilator
1045  that value pointed with result1 and result2 has changed
1046 
1047  this has no effect in visual studio but it's usefull when
1048  using gcc and options like -O
1049  */
1050  uint result1_;
1051  uint result2_;
1052 
1053 
1054  #ifndef __GNUC__
1055  result1_ = _umul128(a,b,&result2_);
1056  #endif
1057 
1058 
1059  #ifdef __GNUC__
1060 
1061  __asm__ (
1062 
1063  "mulq %%rdx \n"
1064 
1065  : "=a" (result1_), "=d" (result2_)
1066  : "0" (a), "1" (b)
1067  : "cc" );
1068 
1069  #endif
1070 
1071 
1072  *result_low = result1_;
1073  *result_high = result2_;
1074  }
1075 
1076 
1077 
1078 
1100  template<uint value_size>
1101  void UInt<value_size>::DivTwoWords(uint a,uint b, uint c, uint * r, uint * rest)
1102  {
1103  uint r_;
1104  uint rest_;
1105  /*
1106  these variables have similar meaning like those in
1107  the multiplication algorithm MulTwoWords
1108  */
1109 
1110  TTMATH_ASSERT( c != 0 )
1111 
1112 
1113  #ifndef __GNUC__
1114 
1115  ttmath_div_x64(&a,&b,c);
1116  r_ = a;
1117  rest_ = b;
1118 
1119  #endif
1120 
1121 
1122  #ifdef __GNUC__
1123 
1124  __asm__ (
1125 
1126  "divq %%rcx \n"
1127 
1128  : "=a" (r_), "=d" (rest_)
1129  : "d" (a), "a" (b), "c" (c)
1130  : "cc" );
1131 
1132  #endif
1133 
1134 
1135  *r = r_;
1136  *rest = rest_;
1137  }
1138 
1139 } //namespace
1140 
1141 
1142 #endif //ifdef TTMATH_PLATFORM64
1143 #endif //ifndef TTMATH_NOASM
1144 #endif
1145 
1146 
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()
#define TTMATH_LOGC(msg, carry)
Definition: ttmathtypes.h:672
uint Add(const UInt< value_size > &ss2, uint c=0)
static sint FindLowestBitInWord(uint x)
Definition: ttmathtypes.h:339
signed int sint
Definition: ttmathtypes.h:164
LibTypeCode
Definition: ttmathtypes.h:335
static void MulTwoWords(uint a, uint b, uint *result_high, uint *result_low)
#define TTMATH_ASSERT(expression)
Definition: ttmathtypes.h:660
#define TTMATH_BITS_PER_UINT
Definition: ttmathtypes.h:184
Definition: ttmathtypes.h:340
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)