Debian Codegraph @

extern/ttmath/ttmathuint_x86.h

raw
1 /*
2 * This file is a part of TTMath Bignum Library
3 * and is distributed under the (new) BSD licence.
4 * Author: Tomasz Sowa <[email protected]>
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
48 /*!
49 \file ttmathuint_x86.h
50 \brief template class UInt<uint> with assembler code for 32bit x86 processors
51
52 this file is included at the end of ttmathuint.h
53 */
54
55
56
57 /*!
58 \brief a namespace for the TTMath library
59 */
60 namespace ttmath
61 {
62
63 /*!
64 returning the string represents the currect type of the library
65 we have following types:
66 asm_vc_32 - with asm code designed for Microsoft Visual C++ (32 bits)
67 asm_gcc_32 - with asm code designed for GCC (32 bits)
68 asm_vc_64 - with asm for VC (64 bit)
69 asm_gcc_64 - with asm for GCC (64 bit)
70 no_asm_32 - pure C++ version (32 bit) - without any asm code
71 no_asm_64 - pure C++ version (64 bit) - without any asm code
72 */
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
88 /*!
89 returning the currect type of the library
90 */
91 template<uint value_size>
92 LibTypeCode UInt<value_size>::LibType()
93 {
94 #ifndef __GNUC__
95 LibTypeCode info = asm_vc_32;
96 #endif
97
98 #ifdef __GNUC__
99 LibTypeCode info = asm_gcc_32;
100 #endif
101
102 return info;
103 }
104
105
106
107 /*!
108 *
109 * basic mathematic functions
110 *
111 */
112
113
114 /*!
115 adding ss2 to the this and adding carry if it's defined
116 (this = this + ss2 + c)
117
118 c must be zero or one (might be a bigger value than 1)
119 function returns carry (1) (if it has been)
120 */
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
206 /*!
207 adding one word (at a specific position)
208 and returning a carry (if it has been)
209
210 e.g.
211
212 if we've got (value_size=3):
213 table[0] = 10;
214 table[1] = 30;
215 table[2] = 5;
216 and we call:
217 AddInt(2,1)
218 then it'll be:
219 table[0] = 10;
220 table[1] = 30 + 2;
221 table[2] = 5;
222
223 of course if there was a carry from table[2] it would be returned
224 */
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
308 /*!
309 adding only two unsigned words to the existing value
310 and these words begin on the 'index' position
311 (it's used in the multiplication algorithm 2)
312
313 index should be equal or smaller than value_size-2 (index <= value_size-2)
314 x1 - lower word, x2 - higher word
315
316 for example if we've got value_size equal 4 and:
317 table[0] = 3
318 table[1] = 4
319 table[2] = 5
320 table[3] = 6
321 then let
322 x1 = 10
323 x2 = 20
324 and
325 index = 1
326
327 the result of this method will be:
328 table[0] = 3
329 table[1] = 4 + x1 = 14
330 table[2] = 5 + x2 = 25
331 table[3] = 6
332
333 and no carry at the end of table[3]
334
335 (of course if there was a carry in table[2](5+20) then
336 this carry would be passed to the table[3] etc.)
337 */
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
428 /*!
429 this static method addes one vector to the other
430 'ss1' is larger in size or equal to 'ss2'
431
432 ss1 points to the first (larger) vector
433 ss2 points to the second vector
434 ss1_size - size of the ss1 (and size of the result too)
435 ss2_size - size of the ss2
436 result - is the result vector (which has size the same as ss1: ss1_size)
437
438 Example: ss1_size is 5, ss2_size is 3
439 ss1: ss2: result (output):
440 5 1 5+1
441 4 3 4+3
442 2 7 2+7
443 6 6
444 9 9
445 of course the carry is propagated and will be returned from the last item
446 (this method is used by the Karatsuba multiplication algorithm)
447 */
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
559 /*!
560 subtracting ss2 from the 'this' and subtracting
561 carry if it has been defined
562 (this = this - ss2 - c)
563
564 c must be zero or one (might be a bigger value than 1)
565 function returns carry (1) (if it has been)
566 */
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
649 /*!
650 this method subtracts one word (at a specific position)
651 and returns a carry (if it was)
652
653 e.g.
654
655 if we've got (value_size=3):
656 table[0] = 10;
657 table[1] = 30;
658 table[2] = 5;
659 and we call:
660 SubInt(2,1)
661 then it'll be:
662 table[0] = 10;
663 table[1] = 30 - 2;
664 table[2] = 5;
665
666 of course if there was a carry from table[2] it would be returned
667 */
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
750 /*!
751 this static method subtractes one vector from the other
752 'ss1' is larger in size or equal to 'ss2'
753
754 ss1 points to the first (larger) vector
755 ss2 points to the second vector
756 ss1_size - size of the ss1 (and size of the result too)
757 ss2_size - size of the ss2
758 result - is the result vector (which has size the same as ss1: ss1_size)
759
760 Example: ss1_size is 5, ss2_size is 3
761 ss1: ss2: result (output):
762 5 1 5-1
763 4 3 4-3
764 2 7 2-7
765 6 6-1 (the borrow from previous item)
766 9 9
767 return (carry): 0
768 of course the carry (borrow) is propagated and will be returned from the last item
769 (this method is used by the Karatsuba multiplication algorithm)
770 */
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
888 /*!
889 this method moves all bits into the left hand side
890 return value <- this <- c
891
892 the lowest *bit* will be held the 'c' and
893 the state of one additional bit (on the left hand side)
894 will be returned
895
896 for example:
897 let this is 001010000
898 after Rcl2_one(1) there'll be 010100001 and Rcl2_one returns 0
899 */
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
966 /*!
967 this method moves all bits into the right hand side
968 c -> this -> return value
969
970 the highest *bit* will be held the 'c' and
971 the state of one additional bit (on the right hand side)
972 will be returned
973
974 for example:
975 let this is 000000010
976 after Rcr2_one(1) there'll be 100000001 and Rcr2_one returns 0
977 */
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
1045 /*!
1046 this method moves all bits into the left hand side
1047 return value <- this <- c
1048
1049 the lowest *bits* will be held the 'c' and
1050 the state of one additional bit (on the left hand side)
1051 will be returned
1052
1053 for example:
1054 let this is 001010000
1055 after Rcl2(3, 1) there'll be 010000111 and Rcl2 returns 1
1056 */
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
1173 /*!
1174 this method moves all bits into the right hand side
1175 C -> this -> return value
1176
1177 the highest *bits* will be held the 'c' and
1178 the state of one additional bit (on the right hand side)
1179 will be returned
1180
1181 for example:
1182 let this is 000000010
1183 after Rcr2(2, 1) there'll be 110000000 and Rcr2 returns 1
1184 */
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>
1315 sint UInt<value_size>::FindLeadingBitInWord(uint x)
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>
1361 sint UInt<value_size>::FindLowestBitInWord(uint x)
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
1402 /*!
1403 this method sets a special bit in the 'value'
1404 and returns the last state of the bit (zero or one)
1405
1406 bit is from <0,31>
1407 e.g.
1408 uint x = 100;
1409 uint bit = SetBitInWord(x, 3);
1410 now: x = 108 and bit = 0
1411 */
1412 template<uint value_size>
1413 uint UInt<value_size>::SetBitInWord(uint & value, uint bit)
1414 {
1415 TTMATH_ASSERT( bit < TTMATH_BITS_PER_UINT )
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
1462 /*!
1463 multiplication: result_high:result_low = a * b
1464 result_high - higher word of the result
1465 result_low - lower word of the result
1466
1467 this methos never returns a carry
1468 this method is used in the second version of the multiplication algorithms
1469 */
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
1524 /*!
1525 *
1526 * Division
1527 *
1528 *
1529 */
1530
1531
1532
1533
1534 /*!
1535 this method calculates 64bits word a:b / 32bits c (a higher, b lower word)
1536 r = a:b / c and rest - remainder
1537
1538 *
1539 * WARNING:
1540 * if r (one word) is too small for the result or c is equal zero
1541 * there'll be a hardware interruption (0)
1542 * and probably the end of your program
1543 *
1544 */
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