Debian Codegraph @

extern/ttmath/ttmathuint_x86_64.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-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
47 /*!
48 \file ttmathuint_x86_64.h
49 \brief template class UInt<uint> with assembler code for 64bit x86_64 processors
50
51 this file is included at the end of ttmathuint.h
52 */
53
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
82 /*!
83 returning the string represents the currect type of the library
84 we have following types:
85 asm_vc_32 - with asm code designed for Microsoft Visual C++ (32 bits)
86 asm_gcc_32 - with asm code designed for GCC (32 bits)
87 asm_vc_64 - with asm for VC (64 bit)
88 asm_gcc_64 - with asm for GCC (64 bit)
89 no_asm_32 - pure C++ version (32 bit) - without any asm code
90 no_asm_64 - pure C++ version (64 bit) - without any asm code
91 */
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
107 /*!
108 returning the currect type of the library
109 */
110 template<uint value_size>
111 LibTypeCode UInt<value_size>::LibType()
112 {
113 #ifndef __GNUC__
114 LibTypeCode info = asm_vc_64;
115 #endif
116
117 #ifdef __GNUC__
118 LibTypeCode info = asm_gcc_64;
119 #endif
120
121 return info;
122 }
123
124
125 /*!
126 *
127 * basic mathematic functions
128 *
129 */
130
131
132
133 /*!
134 this method adding ss2 to the this and adding carry if it's defined
135 (this = this + ss2 + c)
136
137 ***this method is created only on a 64bit platform***
138
139 c must be zero or one (might be a bigger value than 1)
140 function returns carry (1) (if it was)
141 */
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
190 /*!
191 this method adds one word (at a specific position)
192 and returns a carry (if it was)
193
194 ***this method is created only on a 64bit platform***
195
196
197 if we've got (value_size=3):
198 table[0] = 10;
199 table[1] = 30;
200 table[2] = 5;
201 and we call:
202 AddInt(2,1)
203 then it'll be:
204 table[0] = 10;
205 table[1] = 30 + 2;
206 table[2] = 5;
207
208 of course if there was a carry from table[2] it would be returned
209 */
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
257 /*!
258 this method adds only two unsigned words to the existing value
259 and these words begin on the 'index' position
260 (it's used in the multiplication algorithm 2)
261
262 ***this method is created only on a 64bit platform***
263
264 index should be equal or smaller than value_size-2 (index <= value_size-2)
265 x1 - lower word, x2 - higher word
266
267 for example if we've got value_size equal 4 and:
268 table[0] = 3
269 table[1] = 4
270 table[2] = 5
271 table[3] = 6
272 then let
273 x1 = 10
274 x2 = 20
275 and
276 index = 1
277
278 the result of this method will be:
279 table[0] = 3
280 table[1] = 4 + x1 = 14
281 table[2] = 5 + x2 = 25
282 table[3] = 6
283
284 and no carry at the end of table[3]
285
286 (of course if there was a carry in table[2](5+20) then
287 this carry would be passed to the table[3] etc.)
288 */
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
340 /*!
341 this static method addes one vector to the other
342 'ss1' is larger in size or equal to 'ss2'
343
344 ss1 points to the first (larger) vector
345 ss2 points to the second vector
346 ss1_size - size of the ss1 (and size of the result too)
347 ss2_size - size of the ss2
348 result - is the result vector (which has size the same as ss1: ss1_size)
349
350 Example: ss1_size is 5, ss2_size is 3
351 ss1: ss2: result (output):
352 5 1 5+1
353 4 3 4+3
354 2 7 2+7
355 6 6
356 9 9
357 of course the carry is propagated and will be returned from the last item
358 (this method is used by the Karatsuba multiplication algorithm)
359 */
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
423 /*!
424 this method's subtracting ss2 from the 'this' and subtracting
425 carry if it has been defined
426 (this = this - ss2 - c)
427
428 ***this method is created only on a 64bit platform***
429
430 c must be zero or one (might be a bigger value than 1)
431 function returns carry (1) (if it was)
432 */
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
479 /*!
480 this method subtracts one word (at a specific position)
481 and returns a carry (if it was)
482
483 ***this method is created only on a 64bit platform***
484
485 if we've got (value_size=3):
486 table[0] = 10;
487 table[1] = 30;
488 table[2] = 5;
489 and we call:
490 SubInt(2,1)
491 then it'll be:
492 table[0] = 10;
493 table[1] = 30 - 2;
494 table[2] = 5;
495
496 of course if there was a carry from table[2] it would be returned
497 */
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
544 /*!
545 this static method subtractes one vector from the other
546 'ss1' is larger in size or equal to 'ss2'
547
548 ss1 points to the first (larger) vector
549 ss2 points to the second vector
550 ss1_size - size of the ss1 (and size of the result too)
551 ss2_size - size of the ss2
552 result - is the result vector (which has size the same as ss1: ss1_size)
553
554 Example: ss1_size is 5, ss2_size is 3
555 ss1: ss2: result (output):
556 5 1 5-1
557 4 3 4-3
558 2 7 2-7
559 6 6-1 (the borrow from previous item)
560 9 9
561 return (carry): 0
562 of course the carry (borrow) is propagated and will be returned from the last item
563 (this method is used by the Karatsuba multiplication algorithm)
564 */
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
629 /*!
630 this method moves all bits into the left hand side
631 return value <- this <- c
632
633 the lowest *bit* will be held the 'c' and
634 the state of one additional bit (on the left hand side)
635 will be returned
636
637 for example:
638 let this is 001010000
639 after Rcl2_one(1) there'll be 010100001 and Rcl2_one returns 0
640
641 ***this method is created only on a 64bit platform***
642 */
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
684 /*!
685 this method moves all bits into the right hand side
686 c -> this -> return value
687
688 the highest *bit* will be held the 'c' and
689 the state of one additional bit (on the right hand side)
690 will be returned
691
692 for example:
693 let this is 000000010
694 after Rcr2_one(1) there'll be 100000001 and Rcr2_one returns 0
695
696 ***this method is created only on a 64bit platform***
697 */
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
738 /*!
739 this method moves all bits into the left hand side
740 return value <- this <- c
741
742 the lowest *bits* will be held the 'c' and
743 the state of one additional bit (on the left hand side)
744 will be returned
745
746 for example:
747 let this is 001010000
748 after Rcl2(3, 1) there'll be 010000111 and Rcl2 returns 1
749
750 ***this method is created only on a 64bit platform***
751 */
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
811 /*!
812 this method moves all bits into the right hand side
813 C -> this -> return value
814
815 the highest *bits* will be held the 'c' and
816 the state of one additional bit (on the right hand side)
817 will be returned
818
819 for example:
820 let this is 000000010
821 after Rcr2(2, 1) there'll be 110000000 and Rcr2 returns 1
822
823 ***this method is created only on a 64bit platform***
824 */
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>
938 sint UInt<value_size>::FindLowestBitInWord(uint x)
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
975 /*!
976 this method sets a special bit in the 'value'
977 and returns the last state of the bit (zero or one)
978
979 ***this method is created only on a 64bit platform***
980
981 bit is from <0,63>
982
983 e.g.
984 uint x = 100;
985 uint bit = SetBitInWord(x, 3);
986 now: x = 108 and bit = 0
987 */
988 template<uint value_size>
989 uint UInt<value_size>::SetBitInWord(uint & value, uint bit)
990 {
991 TTMATH_ASSERT( bit < TTMATH_BITS_PER_UINT )
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
1022 /*!
1023 *
1024 * Multiplication
1025 *
1026 *
1027 */
1028
1029
1030 /*!
1031 multiplication: result_high:result_low = a * b
1032 result_high - higher word of the result
1033 result_low - lower word of the result
1034
1035 this methos never returns a carry
1036 this method is used in the second version of the multiplication algorithms
1037
1038 ***this method is created only on a 64bit platform***
1039 */
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
1079 /*!
1080 *
1081 * Division
1082 *
1083 *
1084 */
1085
1086
1087 /*!
1088 this method calculates 64bits word a:b / 32bits c (a higher, b lower word)
1089 r = a:b / c and rest - remainder
1090
1091 ***this method is created only on a 64bit platform***
1092
1093 *
1094 * WARNING:
1095 * if r (one word) is too small for the result or c is equal zero
1096 * there'll be a hardware interruption (0)
1097 * and probably the end of your program
1098 *
1099 */
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