All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ttmathuint_x86.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-2009, 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_x86
41 #define headerfilettmathuint_x86
42 
43 
44 #ifndef TTMATH_NOASM
45 #ifdef TTMATH_PLATFORM32
46 
47 
60 namespace ttmath
61 {
62 
73  template<uint value_size>
74  const char * UInt<value_size>::LibTypeStr()
75  {
76  #ifndef __GNUC__
77  static const char info[] = "asm_vc_32";
78  #endif
79 
80  #ifdef __GNUC__
81  static const char info[] = "asm_gcc_32";
82  #endif
83 
84  return info;
85  }
86 
87 
91  template<uint value_size>
93  {
94  #ifndef __GNUC__
96  #endif
97 
98  #ifdef __GNUC__
99  LibTypeCode info = asm_gcc_32;
100  #endif
101 
102  return info;
103  }
104 
105 
106 
121  template<uint value_size>
122  uint UInt<value_size>::Add(const UInt<value_size> & ss2, uint c)
123  {
124  uint b = value_size;
125  uint * p1 = table;
126  uint * p2 = const_cast<uint*>(ss2.table);
127 
128  // we don't have to use TTMATH_REFERENCE_ASSERT here
129  // this algorithm doesn't require it
130 
131  #ifndef __GNUC__
132 
133  // this part might be compiled with for example visual c
134 
135  __asm
136  {
137  push eax
138  push ebx
139  push ecx
140  push edx
141  push esi
142 
143  mov ecx,[b]
144 
145  mov ebx,[p1]
146  mov esi,[p2]
147 
148  xor edx,edx // edx=0
149  mov eax,[c]
150  neg eax // CF=1 if rax!=0 , CF=0 if rax==0
151 
152  ttmath_loop:
153  mov eax,[esi+edx*4]
154  adc [ebx+edx*4],eax
155 
156  inc edx
157  dec ecx
158  jnz ttmath_loop
159 
160  adc ecx, ecx
161  mov [c], ecx
162 
163  pop esi
164  pop edx
165  pop ecx
166  pop ebx
167  pop eax
168  }
169 
170 
171 
172  #endif
173 
174 
175  #ifdef __GNUC__
176  uint dummy, dummy2;
177  // this part should be compiled with gcc
178 
179  __asm__ __volatile__(
180 
181  "xorl %%edx, %%edx \n"
182  "negl %%eax \n" // CF=1 if rax!=0 , CF=0 if rax==0
183 
184  "1: \n"
185  "movl (%%esi,%%edx,4), %%eax \n"
186  "adcl %%eax, (%%ebx,%%edx,4) \n"
187 
188  "incl %%edx \n"
189  "decl %%ecx \n"
190  "jnz 1b \n"
191 
192  "adc %%ecx, %%ecx \n"
193 
194  : "=c" (c), "=a" (dummy), "=d" (dummy2)
195  : "0" (b), "1" (c), "b" (p1), "S" (p2)
196  : "cc", "memory" );
197  #endif
198 
199  TTMATH_LOGC("UInt::Add", c)
200 
201  return c;
202  }
203 
204 
205 
225  template<uint value_size>
226  uint UInt<value_size>::AddInt(uint value, uint index)
227  {
228  uint b = value_size;
229  uint * p1 = table;
230  uint c;
231 
232  TTMATH_ASSERT( index < value_size )
233 
234  #ifndef __GNUC__
235 
236  __asm
237  {
238  push eax
239  push ebx
240  push ecx
241  push edx
242 
243  mov ecx, [b]
244  sub ecx, [index]
245 
246  mov edx, [index]
247  mov ebx, [p1]
248 
249  mov eax, [value]
250 
251  ttmath_loop:
252  add [ebx+edx*4], eax
253  jnc ttmath_end
254 
255  mov eax, 1
256  inc edx
257  dec ecx
258  jnz ttmath_loop
259 
260  ttmath_end:
261  setc al
262  movzx edx, al
263  mov [c], edx
264 
265  pop edx
266  pop ecx
267  pop ebx
268  pop eax
269  }
270 
271  #endif
272 
273 
274  #ifdef __GNUC__
275  uint dummy, dummy2;
276 
277  __asm__ __volatile__(
278 
279  "subl %%edx, %%ecx \n"
280 
281  "1: \n"
282  "addl %%eax, (%%ebx,%%edx,4) \n"
283  "jnc 2f \n"
284 
285  "movl $1, %%eax \n"
286  "incl %%edx \n"
287  "decl %%ecx \n"
288  "jnz 1b \n"
289 
290  "2: \n"
291  "setc %%al \n"
292  "movzx %%al, %%edx \n"
293 
294  : "=d" (c), "=a" (dummy), "=c" (dummy2)
295  : "0" (index), "1" (value), "2" (b), "b" (p1)
296  : "cc", "memory" );
297 
298  #endif
299 
300  TTMATH_LOGC("UInt::AddInt", c)
301 
302  return c;
303  }
304 
305 
306 
307 
338  template<uint value_size>
339  uint UInt<value_size>::AddTwoInts(uint x2, uint x1, uint index)
340  {
341  uint b = value_size;
342  uint * p1 = table;
343  uint c;
344 
345  TTMATH_ASSERT( index < value_size - 1 )
346 
347  #ifndef __GNUC__
348  __asm
349  {
350  push eax
351  push ebx
352  push ecx
353  push edx
354 
355  mov ecx, [b]
356  sub ecx, [index]
357 
358  mov ebx, [p1]
359  mov edx, [index]
360 
361  mov eax, [x1]
362  add [ebx+edx*4], eax
363  inc edx
364  dec ecx
365 
366  mov eax, [x2]
367 
368  ttmath_loop:
369  adc [ebx+edx*4], eax
370  jnc ttmath_end
371 
372  mov eax, 0
373  inc edx
374  dec ecx
375  jnz ttmath_loop
376 
377  ttmath_end:
378  setc al
379  movzx edx, al
380  mov [c], edx
381 
382  pop edx
383  pop ecx
384  pop ebx
385  pop eax
386 
387  }
388  #endif
389 
390 
391  #ifdef __GNUC__
392  uint dummy, dummy2;
393 
394  __asm__ __volatile__(
395 
396  "subl %%edx, %%ecx \n"
397 
398  "addl %%esi, (%%ebx,%%edx,4) \n"
399  "incl %%edx \n"
400  "decl %%ecx \n"
401 
402  "1: \n"
403  "adcl %%eax, (%%ebx,%%edx,4) \n"
404  "jnc 2f \n"
405 
406  "mov $0, %%eax \n"
407  "incl %%edx \n"
408  "decl %%ecx \n"
409  "jnz 1b \n"
410 
411  "2: \n"
412  "setc %%al \n"
413  "movzx %%al, %%eax \n"
414 
415  : "=a" (c), "=c" (dummy), "=d" (dummy2)
416  : "0" (x2), "1" (b), "2" (index), "b" (p1), "S" (x1)
417  : "cc", "memory" );
418 
419  #endif
420 
421  TTMATH_LOGC("UInt::AddTwoInts", c)
422 
423  return c;
424  }
425 
426 
427 
448  template<uint value_size>
449  uint UInt<value_size>::AddVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result)
450  {
451  TTMATH_ASSERT( ss1_size >= ss2_size )
452 
453  uint rest = ss1_size - ss2_size;
454  uint c;
455 
456  #ifndef __GNUC__
457 
458  // this part might be compiled with for example visual c
459  __asm
460  {
461  pushad
462 
463  mov ecx, [ss2_size]
464  xor edx, edx // edx = 0, cf = 0
465 
466  mov esi, [ss1]
467  mov ebx, [ss2]
468  mov edi, [result]
469 
470  ttmath_loop:
471  mov eax, [esi+edx*4]
472  adc eax, [ebx+edx*4]
473  mov [edi+edx*4], eax
474 
475  inc edx
476  dec ecx
477  jnz ttmath_loop
478 
479  adc ecx, ecx // ecx has the cf state
480 
481  mov ebx, [rest]
482  or ebx, ebx
483  jz ttmath_end
484 
485  xor ebx, ebx // ebx = 0
486  neg ecx // setting cf from ecx
487  mov ecx, [rest] // ecx is != 0
488 
489  ttmath_loop2:
490  mov eax, [esi+edx*4]
491  adc eax, ebx
492  mov [edi+edx*4], eax
493 
494  inc edx
495  dec ecx
496  jnz ttmath_loop2
497 
498  adc ecx, ecx
499 
500  ttmath_end:
501  mov [c], ecx
502 
503  popad
504  }
505 
506  #endif
507 
508 
509  #ifdef __GNUC__
510 
511  // this part should be compiled with gcc
512  uint dummy1, dummy2, dummy3;
513 
514  __asm__ __volatile__(
515  "push %%edx \n"
516  "xor %%edx, %%edx \n" // edx = 0, cf = 0
517  "1: \n"
518  "mov (%%esi,%%edx,4), %%eax \n"
519  "adc (%%ebx,%%edx,4), %%eax \n"
520  "mov %%eax, (%%edi,%%edx,4) \n"
521 
522  "inc %%edx \n"
523  "dec %%ecx \n"
524  "jnz 1b \n"
525 
526  "adc %%ecx, %%ecx \n" // ecx has the cf state
527  "pop %%eax \n" // eax = rest
528 
529  "or %%eax, %%eax \n"
530  "jz 3f \n"
531 
532  "xor %%ebx, %%ebx \n" // ebx = 0
533  "neg %%ecx \n" // setting cf from ecx
534  "mov %%eax, %%ecx \n" // ecx=rest and is != 0
535  "2: \n"
536  "mov (%%esi, %%edx, 4), %%eax \n"
537  "adc %%ebx, %%eax \n"
538  "mov %%eax, (%%edi, %%edx, 4) \n"
539 
540  "inc %%edx \n"
541  "dec %%ecx \n"
542  "jnz 2b \n"
543 
544  "adc %%ecx, %%ecx \n"
545  "3: \n"
546 
547  : "=a" (dummy1), "=b" (dummy2), "=c" (c), "=d" (dummy3)
548  : "1" (ss2), "2" (ss2_size), "3" (rest), "S" (ss1), "D" (result)
549  : "cc", "memory" );
550 
551  #endif
552 
553  TTMATH_VECTOR_LOGC("UInt::AddVector", c, result, ss1_size)
554 
555  return c;
556  }
557 
558 
567  template<uint value_size>
568  uint UInt<value_size>::Sub(const UInt<value_size> & ss2, uint c)
569  {
570  uint b = value_size;
571  uint * p1 = table;
572  uint * p2 = const_cast<uint*>(ss2.table);
573 
574  // we don't have to use TTMATH_REFERENCE_ASSERT here
575  // this algorithm doesn't require it
576 
577  #ifndef __GNUC__
578 
579  __asm
580  {
581  push eax
582  push ebx
583  push ecx
584  push edx
585  push esi
586 
587  mov ecx,[b]
588 
589  mov ebx,[p1]
590  mov esi,[p2]
591 
592  xor edx,edx // edx=0
593  mov eax,[c]
594  neg eax // CF=1 if rax!=0 , CF=0 if rax==0
595 
596  ttmath_loop:
597  mov eax,[esi+edx*4]
598  sbb [ebx+edx*4],eax
599 
600  inc edx
601  dec ecx
602  jnz ttmath_loop
603 
604  adc ecx, ecx
605  mov [c], ecx
606 
607  pop esi
608  pop edx
609  pop ecx
610  pop ebx
611  pop eax
612  }
613 
614  #endif
615 
616 
617  #ifdef __GNUC__
618  uint dummy, dummy2;
619 
620  __asm__ __volatile__(
621 
622  "xorl %%edx, %%edx \n"
623  "negl %%eax \n" // CF=1 if rax!=0 , CF=0 if rax==0
624 
625  "1: \n"
626  "movl (%%esi,%%edx,4), %%eax \n"
627  "sbbl %%eax, (%%ebx,%%edx,4) \n"
628 
629  "incl %%edx \n"
630  "decl %%ecx \n"
631  "jnz 1b \n"
632 
633  "adc %%ecx, %%ecx \n"
634 
635  : "=c" (c), "=a" (dummy), "=d" (dummy2)
636  : "0" (b), "1" (c), "b" (p1), "S" (p2)
637  : "cc", "memory" );
638 
639  #endif
640 
641  TTMATH_LOGC("UInt::Sub", c)
642 
643  return c;
644  }
645 
646 
647 
648 
668  template<uint value_size>
669  uint UInt<value_size>::SubInt(uint value, uint index)
670  {
671  uint b = value_size;
672  uint * p1 = table;
673  uint c;
674 
675  TTMATH_ASSERT( index < value_size )
676 
677  #ifndef __GNUC__
678 
679  __asm
680  {
681  push eax
682  push ebx
683  push ecx
684  push edx
685 
686  mov ecx, [b]
687  sub ecx, [index]
688 
689  mov edx, [index]
690  mov ebx, [p1]
691 
692  mov eax, [value]
693 
694  ttmath_loop:
695  sub [ebx+edx*4], eax
696  jnc ttmath_end
697 
698  mov eax, 1
699  inc edx
700  dec ecx
701  jnz ttmath_loop
702 
703  ttmath_end:
704  setc al
705  movzx edx, al
706  mov [c], edx
707 
708  pop edx
709  pop ecx
710  pop ebx
711  pop eax
712  }
713 
714  #endif
715 
716 
717  #ifdef __GNUC__
718  uint dummy, dummy2;
719 
720  __asm__ __volatile__(
721 
722  "subl %%edx, %%ecx \n"
723 
724  "1: \n"
725  "subl %%eax, (%%ebx,%%edx,4) \n"
726  "jnc 2f \n"
727 
728  "movl $1, %%eax \n"
729  "incl %%edx \n"
730  "decl %%ecx \n"
731  "jnz 1b \n"
732 
733  "2: \n"
734  "setc %%al \n"
735  "movzx %%al, %%edx \n"
736 
737  : "=d" (c), "=a" (dummy), "=c" (dummy2)
738  : "0" (index), "1" (value), "2" (b), "b" (p1)
739  : "cc", "memory" );
740 
741  #endif
742 
743  TTMATH_LOGC("UInt::SubInt", c)
744 
745  return c;
746  }
747 
748 
749 
771  template<uint value_size>
772  uint UInt<value_size>::SubVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result)
773  {
774  TTMATH_ASSERT( ss1_size >= ss2_size )
775 
776  uint rest = ss1_size - ss2_size;
777  uint c;
778 
779  #ifndef __GNUC__
780 
781  // this part might be compiled with for example visual c
782 
783  /*
784  the asm code is nearly the same as in AddVector
785  only two instructions 'adc' are changed to 'sbb'
786  */
787  __asm
788  {
789  pushad
790 
791  mov ecx, [ss2_size]
792  xor edx, edx // edx = 0, cf = 0
793 
794  mov esi, [ss1]
795  mov ebx, [ss2]
796  mov edi, [result]
797 
798  ttmath_loop:
799  mov eax, [esi+edx*4]
800  sbb eax, [ebx+edx*4]
801  mov [edi+edx*4], eax
802 
803  inc edx
804  dec ecx
805  jnz ttmath_loop
806 
807  adc ecx, ecx // ecx has the cf state
808 
809  mov ebx, [rest]
810  or ebx, ebx
811  jz ttmath_end
812 
813  xor ebx, ebx // ebx = 0
814  neg ecx // setting cf from ecx
815  mov ecx, [rest] // ecx is != 0
816 
817  ttmath_loop2:
818  mov eax, [esi+edx*4]
819  sbb eax, ebx
820  mov [edi+edx*4], eax
821 
822  inc edx
823  dec ecx
824  jnz ttmath_loop2
825 
826  adc ecx, ecx
827 
828  ttmath_end:
829  mov [c], ecx
830 
831  popad
832  }
833 
834  #endif
835 
836 
837  #ifdef __GNUC__
838 
839  // this part should be compiled with gcc
840  uint dummy1, dummy2, dummy3;
841 
842  __asm__ __volatile__(
843  "push %%edx \n"
844  "xor %%edx, %%edx \n" // edx = 0, cf = 0
845  "1: \n"
846  "mov (%%esi,%%edx,4), %%eax \n"
847  "sbb (%%ebx,%%edx,4), %%eax \n"
848  "mov %%eax, (%%edi,%%edx,4) \n"
849 
850  "inc %%edx \n"
851  "dec %%ecx \n"
852  "jnz 1b \n"
853 
854  "adc %%ecx, %%ecx \n" // ecx has the cf state
855  "pop %%eax \n" // eax = rest
856 
857  "or %%eax, %%eax \n"
858  "jz 3f \n"
859 
860  "xor %%ebx, %%ebx \n" // ebx = 0
861  "neg %%ecx \n" // setting cf from ecx
862  "mov %%eax, %%ecx \n" // ecx=rest and is != 0
863  "2: \n"
864  "mov (%%esi, %%edx, 4), %%eax \n"
865  "sbb %%ebx, %%eax \n"
866  "mov %%eax, (%%edi, %%edx, 4) \n"
867 
868  "inc %%edx \n"
869  "dec %%ecx \n"
870  "jnz 2b \n"
871 
872  "adc %%ecx, %%ecx \n"
873  "3: \n"
874 
875  : "=a" (dummy1), "=b" (dummy2), "=c" (c), "=d" (dummy3)
876  : "1" (ss2), "2" (ss2_size), "3" (rest), "S" (ss1), "D" (result)
877  : "cc", "memory" );
878 
879  #endif
880 
881  TTMATH_VECTOR_LOGC("UInt::SubVector", c, result, ss1_size)
882 
883  return c;
884  }
885 
886 
887 
900  template<uint value_size>
901  uint UInt<value_size>::Rcl2_one(uint c)
902  {
903  uint b = value_size;
904  uint * p1 = table;
905 
906  #ifndef __GNUC__
907  __asm
908  {
909  push ebx
910  push ecx
911  push edx
912 
913  mov ebx, [p1]
914  xor edx, edx
915  mov ecx, [c]
916  neg ecx
917  mov ecx, [b]
918 
919  ttmath_loop:
920  rcl dword ptr [ebx+edx*4], 1
921 
922  inc edx
923  dec ecx
924  jnz ttmath_loop
925 
926  adc ecx, ecx
927  mov [c], ecx
928 
929  pop edx
930  pop ecx
931  pop ebx
932  }
933  #endif
934 
935 
936  #ifdef __GNUC__
937  uint dummy, dummy2;
938 
939  __asm__ __volatile__(
940 
941  "xorl %%edx, %%edx \n" // edx=0
942  "negl %%eax \n" // CF=1 if eax!=0 , CF=0 if eax==0
943 
944  "1: \n"
945  "rcll $1, (%%ebx, %%edx, 4) \n"
946 
947  "incl %%edx \n"
948  "decl %%ecx \n"
949  "jnz 1b \n"
950 
951  "adcl %%ecx, %%ecx \n"
952 
953  : "=c" (c), "=a" (dummy), "=d" (dummy2)
954  : "0" (b), "1" (c), "b" (p1)
955  : "cc", "memory" );
956 
957  #endif
958 
959  TTMATH_LOGC("UInt::Rcl2_one", c)
960 
961  return c;
962  }
963 
964 
965 
978  template<uint value_size>
979  uint UInt<value_size>::Rcr2_one(uint c)
980  {
981  uint b = value_size;
982  uint * p1 = table;
983 
984  #ifndef __GNUC__
985  __asm
986  {
987  push ebx
988  push ecx
989 
990  mov ebx, [p1]
991  mov ecx, [c]
992  neg ecx
993  mov ecx, [b]
994 
995  ttmath_loop:
996  rcr dword ptr [ebx+ecx*4-4], 1
997 
998  dec ecx
999  jnz ttmath_loop
1000 
1001  adc ecx, ecx
1002  mov [c], ecx
1003 
1004  pop ecx
1005  pop ebx
1006  }
1007  #endif
1008 
1009 
1010  #ifdef __GNUC__
1011  uint dummy;
1012 
1013  __asm__ __volatile__(
1014 
1015  "negl %%eax \n" // CF=1 if eax!=0 , CF=0 if eax==0
1016 
1017  "1: \n"
1018  "rcrl $1, -4(%%ebx, %%ecx, 4) \n"
1019 
1020  "decl %%ecx \n"
1021  "jnz 1b \n"
1022 
1023  "adcl %%ecx, %%ecx \n"
1024 
1025  : "=c" (c), "=a" (dummy)
1026  : "0" (b), "1" (c), "b" (p1)
1027  : "cc", "memory" );
1028 
1029  #endif
1030 
1031  TTMATH_LOGC("UInt::Rcr2_one", c)
1032 
1033  return c;
1034  }
1035 
1036 
1037 
1038 #ifdef _MSC_VER
1039 #pragma warning (disable : 4731)
1040 //warning C4731: frame pointer register 'ebp' modified by inline assembly code
1041 #endif
1042 
1043 
1044 
1057  template<uint value_size>
1058  uint UInt<value_size>::Rcl2(uint bits, uint c)
1059  {
1060  TTMATH_ASSERT( bits>0 && bits<TTMATH_BITS_PER_UINT )
1061 
1062  uint b = value_size;
1063  uint * p1 = table;
1064 
1065  #ifndef __GNUC__
1066  __asm
1067  {
1068  push eax
1069  push ebx
1070  push ecx
1071  push edx
1072  push esi
1073  push edi
1074  push ebp
1075 
1076  mov edi, [b]
1077 
1078  mov ecx, 32
1079  sub ecx, [bits]
1080  mov edx, -1
1081  shr edx, cl
1082 
1083  mov ecx, [bits]
1084  mov ebx, [p1]
1085  mov eax, [c]
1086 
1087  mov ebp, edx // ebp = mask (modified ebp - don't read/write to variables)
1088 
1089  xor edx, edx // edx = 0
1090  mov esi, edx
1091  or eax, eax
1092  cmovnz esi, ebp // if(c) esi=mask else esi=0
1093 
1094  ttmath_loop:
1095  rol dword ptr [ebx+edx*4], cl
1096 
1097  mov eax, [ebx+edx*4]
1098  and eax, ebp
1099  xor [ebx+edx*4], eax // clearing bits
1100  or [ebx+edx*4], esi // saving old value
1101  mov esi, eax
1102 
1103  inc edx
1104  dec edi
1105  jnz ttmath_loop
1106 
1107  pop ebp // restoring ebp
1108 
1109  and eax, 1
1110  mov [c], eax
1111 
1112  pop edi
1113  pop esi
1114  pop edx
1115  pop ecx
1116  pop ebx
1117  pop eax
1118  }
1119  #endif
1120 
1121 
1122  #ifdef __GNUC__
1123  uint dummy, dummy2, dummy3;
1124 
1125  __asm__ __volatile__(
1126 
1127  "push %%ebp \n"
1128 
1129  "movl %%ecx, %%esi \n"
1130  "movl $32, %%ecx \n"
1131  "subl %%esi, %%ecx \n" // ecx = 32 - bits
1132  "movl $-1, %%edx \n" // edx = -1 (all bits set to one)
1133  "shrl %%cl, %%edx \n" // shifting (0 -> edx -> cf) (cl times)
1134  "movl %%edx, %%ebp \n" // ebp = edx = mask
1135  "movl %%esi, %%ecx \n"
1136 
1137  "xorl %%edx, %%edx \n"
1138  "movl %%edx, %%esi \n"
1139  "orl %%eax, %%eax \n"
1140  "cmovnz %%ebp, %%esi \n" // if(c) esi=mask else esi=0
1141 
1142  "1: \n"
1143  "roll %%cl, (%%ebx,%%edx,4) \n"
1144 
1145  "movl (%%ebx,%%edx,4), %%eax \n"
1146  "andl %%ebp, %%eax \n"
1147  "xorl %%eax, (%%ebx,%%edx,4) \n"
1148  "orl %%esi, (%%ebx,%%edx,4) \n"
1149  "movl %%eax, %%esi \n"
1150 
1151  "incl %%edx \n"
1152  "decl %%edi \n"
1153  "jnz 1b \n"
1154 
1155  "and $1, %%eax \n"
1156 
1157  "pop %%ebp \n"
1158 
1159  : "=a" (c), "=D" (dummy), "=S" (dummy2), "=d" (dummy3)
1160  : "0" (c), "1" (b), "b" (p1), "c" (bits)
1161  : "cc", "memory" );
1162 
1163  #endif
1164 
1165  TTMATH_LOGC("UInt::Rcl2", c)
1166 
1167  return c;
1168  }
1169 
1170 
1171 
1172 
1185  template<uint value_size>
1186  uint UInt<value_size>::Rcr2(uint bits, uint c)
1187  {
1188  TTMATH_ASSERT( bits>0 && bits<TTMATH_BITS_PER_UINT )
1189 
1190  uint b = value_size;
1191  uint * p1 = table;
1192 
1193  #ifndef __GNUC__
1194  __asm
1195  {
1196  push eax
1197  push ebx
1198  push ecx
1199  push edx
1200  push esi
1201  push edi
1202  push ebp
1203 
1204  mov edi, [b]
1205 
1206  mov ecx, 32
1207  sub ecx, [bits]
1208  mov edx, -1
1209  shl edx, cl
1210 
1211  mov ecx, [bits]
1212  mov ebx, [p1]
1213  mov eax, [c]
1214 
1215  mov ebp, edx // ebp = mask (modified ebp - don't read/write to variables)
1216 
1217  xor edx, edx // edx = 0
1218  mov esi, edx
1219  add edx, edi
1220  dec edx // edx is pointing at the end of the table (on last word)
1221  or eax, eax
1222  cmovnz esi, ebp // if(c) esi=mask else esi=0
1223 
1224  ttmath_loop:
1225  ror dword ptr [ebx+edx*4], cl
1226 
1227  mov eax, [ebx+edx*4]
1228  and eax, ebp
1229  xor [ebx+edx*4], eax // clearing bits
1230  or [ebx+edx*4], esi // saving old value
1231  mov esi, eax
1232 
1233  dec edx
1234  dec edi
1235  jnz ttmath_loop
1236 
1237  pop ebp // restoring ebp
1238 
1239  rol eax, 1 // 31bit will be first
1240  and eax, 1
1241  mov [c], eax
1242 
1243  pop edi
1244  pop esi
1245  pop edx
1246  pop ecx
1247  pop ebx
1248  pop eax
1249  }
1250  #endif
1251 
1252 
1253  #ifdef __GNUC__
1254  uint dummy, dummy2, dummy3;
1255 
1256  __asm__ __volatile__(
1257 
1258  "push %%ebp \n"
1259 
1260  "movl %%ecx, %%esi \n"
1261  "movl $32, %%ecx \n"
1262  "subl %%esi, %%ecx \n" // ecx = 32 - bits
1263  "movl $-1, %%edx \n" // edx = -1 (all bits set to one)
1264  "shll %%cl, %%edx \n" // shifting (cf <- edx <- 0) (cl times)
1265  "movl %%edx, %%ebp \n" // ebp = edx = mask
1266  "movl %%esi, %%ecx \n"
1267 
1268  "xorl %%edx, %%edx \n"
1269  "movl %%edx, %%esi \n"
1270  "addl %%edi, %%edx \n"
1271  "decl %%edx \n" // edx is pointing at the end of the table (on last word)
1272  "orl %%eax, %%eax \n"
1273  "cmovnz %%ebp, %%esi \n" // if(c) esi=mask else esi=0
1274 
1275  "1: \n"
1276  "rorl %%cl, (%%ebx,%%edx,4) \n"
1277 
1278  "movl (%%ebx,%%edx,4), %%eax \n"
1279  "andl %%ebp, %%eax \n"
1280  "xorl %%eax, (%%ebx,%%edx,4) \n"
1281  "orl %%esi, (%%ebx,%%edx,4) \n"
1282  "movl %%eax, %%esi \n"
1283 
1284  "decl %%edx \n"
1285  "decl %%edi \n"
1286  "jnz 1b \n"
1287 
1288  "roll $1, %%eax \n"
1289  "andl $1, %%eax \n"
1290 
1291  "pop %%ebp \n"
1292 
1293  : "=a" (c), "=D" (dummy), "=S" (dummy2), "=d" (dummy3)
1294  : "0" (c), "1" (b), "b" (p1), "c" (bits)
1295  : "cc", "memory" );
1296 
1297  #endif
1298 
1299  TTMATH_LOGC("UInt::Rcr2", c)
1300 
1301  return c;
1302  }
1303 
1304 
1305 #ifdef _MSC_VER
1306 #pragma warning (default : 4731)
1307 #endif
1308 
1309 
1310  /*
1311  this method returns the number of the highest set bit in one 32-bit word
1312  if the 'x' is zero this method returns '-1'
1313  */
1314  template<uint value_size>
1316  {
1317  sint result;
1318 
1319  #ifndef __GNUC__
1320  __asm
1321  {
1322  push eax
1323  push edx
1324 
1325  mov edx,-1
1326  bsr eax,[x]
1327  cmovz eax,edx
1328  mov [result], eax
1329 
1330  pop edx
1331  pop eax
1332  }
1333  #endif
1334 
1335 
1336  #ifdef __GNUC__
1337  uint dummy;
1338 
1339  __asm__ (
1340 
1341  "movl $-1, %1 \n"
1342  "bsrl %2, %0 \n"
1343  "cmovz %1, %0 \n"
1344 
1345  : "=r" (result), "=&r" (dummy)
1346  : "r" (x)
1347  : "cc" );
1348 
1349  #endif
1350 
1351  return result;
1352  }
1353 
1354 
1355 
1356  /*
1357  this method returns the number of the smallest set bit in one 32-bit word
1358  if the 'x' is zero this method returns '-1'
1359  */
1360  template<uint value_size>
1362  {
1363  sint result;
1364 
1365  #ifndef __GNUC__
1366  __asm
1367  {
1368  push eax
1369  push edx
1370 
1371  mov edx,-1
1372  bsf eax,[x]
1373  cmovz eax,edx
1374  mov [result], eax
1375 
1376  pop edx
1377  pop eax
1378  }
1379  #endif
1380 
1381 
1382  #ifdef __GNUC__
1383  uint dummy;
1384 
1385  __asm__ (
1386 
1387  "movl $-1, %1 \n"
1388  "bsfl %2, %0 \n"
1389  "cmovz %1, %0 \n"
1390 
1391  : "=r" (result), "=&r" (dummy)
1392  : "r" (x)
1393  : "cc" );
1394 
1395  #endif
1396 
1397  return result;
1398  }
1399 
1400 
1401 
1412  template<uint value_size>
1414  {
1416 
1417  uint old_bit;
1418  uint v = value;
1419 
1420  #ifndef __GNUC__
1421  __asm
1422  {
1423  push ebx
1424  push eax
1425 
1426  mov eax, [v]
1427  mov ebx, [bit]
1428  bts eax, ebx
1429  mov [v], eax
1430 
1431  setc bl
1432  movzx ebx, bl
1433  mov [old_bit], ebx
1434 
1435  pop eax
1436  pop ebx
1437  }
1438  #endif
1439 
1440 
1441  #ifdef __GNUC__
1442  __asm__ (
1443 
1444  "btsl %%ebx, %%eax \n"
1445  "setc %%bl \n"
1446  "movzx %%bl, %%ebx \n"
1447 
1448  : "=a" (v), "=b" (old_bit)
1449  : "0" (v), "1" (bit)
1450  : "cc" );
1451 
1452  #endif
1453 
1454  value = v;
1455 
1456  return old_bit;
1457  }
1458 
1459 
1460 
1461 
1470  template<uint value_size>
1471  void UInt<value_size>::MulTwoWords(uint a, uint b, uint * result_high, uint * result_low)
1472  {
1473  /*
1474  we must use these temporary variables in order to inform the compilator
1475  that value pointed with result1 and result2 has changed
1476 
1477  this has no effect in visual studio but it's useful when
1478  using gcc and options like -Ox
1479  */
1480  uint result1_;
1481  uint result2_;
1482 
1483  #ifndef __GNUC__
1484 
1485  __asm
1486  {
1487  push eax
1488  push edx
1489 
1490  mov eax, [a]
1491  mul dword ptr [b]
1492 
1493  mov [result2_], edx
1494  mov [result1_], eax
1495 
1496  pop edx
1497  pop eax
1498  }
1499 
1500  #endif
1501 
1502 
1503  #ifdef __GNUC__
1504 
1505  __asm__ (
1506 
1507  "mull %%edx \n"
1508 
1509  : "=a" (result1_), "=d" (result2_)
1510  : "0" (a), "1" (b)
1511  : "cc" );
1512 
1513  #endif
1514 
1515 
1516  *result_low = result1_;
1517  *result_high = result2_;
1518  }
1519 
1520 
1521 
1522 
1523 
1545  template<uint value_size>
1546  void UInt<value_size>::DivTwoWords(uint a, uint b, uint c, uint * r, uint * rest)
1547  {
1548  uint r_;
1549  uint rest_;
1550  /*
1551  these variables have similar meaning like those in
1552  the multiplication algorithm MulTwoWords
1553  */
1554 
1555  TTMATH_ASSERT( c != 0 )
1556 
1557  #ifndef __GNUC__
1558  __asm
1559  {
1560  push eax
1561  push edx
1562 
1563  mov edx, [a]
1564  mov eax, [b]
1565  div dword ptr [c]
1566 
1567  mov [r_], eax
1568  mov [rest_], edx
1569 
1570  pop edx
1571  pop eax
1572  }
1573  #endif
1574 
1575 
1576  #ifdef __GNUC__
1577 
1578  __asm__ (
1579 
1580  "divl %%ecx \n"
1581 
1582  : "=a" (r_), "=d" (rest_)
1583  : "0" (b), "1" (a), "c" (c)
1584  : "cc" );
1585 
1586  #endif
1587 
1588 
1589  *r = r_;
1590  *rest = rest_;
1591 
1592  }
1593 
1594 
1595 
1596 } //namespace
1597 
1598 
1599 
1600 #endif //ifdef TTMATH_PLATFORM32
1601 #endif //ifndef TTMATH_NOASM
1602 #endif
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)
signed int sint
Definition: ttmathtypes.h:164
LibTypeCode
Definition: ttmathtypes.h:335
static sint FindLeadingBitInWord(uint x)
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:338
Definition: ttmathtypes.h:337
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)