2 # Copyright 2006-2018 The OpenSSL Project Authors. All Rights Reserved.
4 # Licensed under the Apache License 2.0 (the "License"). You may not use
5 # this file except in compliance with the License. You can obtain a copy
6 # in the file LICENSE in the source distribution or at
7 # https://www.openssl.org/source/license.html
10 # ====================================================================
11 # Written by Andy Polyakov <appro@openssl.org> for the OpenSSL
12 # project. The module is, however, dual licensed under OpenSSL and
13 # CRYPTOGAMS licenses depending on where you obtain it. For further
14 # details see http://www.openssl.org/~appro/cryptogams/.
15 # ====================================================================
19 # "Teaser" Montgomery multiplication module for PowerPC. It's possible
20 # to gain a bit more by modulo-scheduling outer loop, then dedicated
21 # squaring procedure should give further 20% and code can be adapted
22 # for 32-bit application running on 64-bit CPU. As for the latter.
23 # It won't be able to achieve "native" 64-bit performance, because in
24 # 32-bit application context every addc instruction will have to be
25 # expanded as addc, twice right shift by 32 and finally adde, etc.
26 # So far RSA *sign* performance improvement over pre-bn_mul_mont asm
27 # for 64-bit application running on PPC970/G5 is:
36 # Add multiplication procedure operating on lengths divisible by 4
37 # and squaring procedure operating on lengths divisible by 8. Length
38 # is expressed in number of limbs. RSA private key operations are
39 # ~35-50% faster (more for longer keys) on contemporary high-end POWER
40 # processors in 64-bit builds, [mysteriously enough] more in 32-bit
41 # builds. On low-end 32-bit processors performance improvement turned
44 # $output is the last argument if it looks like a file (it has an extension)
45 # $flavour is the first argument if it doesn't look like a file
46 $output = $#ARGV >= 0 && $ARGV[$#ARGV] =~ m|\.\w+$| ? pop : undef;
47 $flavour = $#ARGV >= 0 && $ARGV[0] !~ m|\.| ? shift : undef;
49 if ($flavour =~ /32/) {
56 $LDU= "lwzu"; # load and update
57 $LDX= "lwzx"; # load indexed
59 $STU= "stwu"; # store and update
60 $STX= "stwx"; # store indexed
61 $STUX= "stwux"; # store indexed and update
62 $UMULL= "mullw"; # unsigned multiply low
63 $UMULH= "mulhwu"; # unsigned multiply high
64 $UCMP= "cmplw"; # unsigned compare
65 $SHRI= "srwi"; # unsigned shift right by immediate
66 $SHLI= "slwi"; # unsigned shift left by immediate
69 } elsif ($flavour =~ /64/) {
75 # same as above, but 64-bit mnemonics...
77 $LDU= "ldu"; # load and update
78 $LDX= "ldx"; # load indexed
80 $STU= "stdu"; # store and update
81 $STX= "stdx"; # store indexed
82 $STUX= "stdux"; # store indexed and update
83 $UMULL= "mulld"; # unsigned multiply low
84 $UMULH= "mulhdu"; # unsigned multiply high
85 $UCMP= "cmpld"; # unsigned compare
86 $SHRI= "srdi"; # unsigned shift right by immediate
87 $SHLI= "sldi"; # unsigned shift left by immediate
90 } else { die "nonsense $flavour"; }
92 $FRAME=8*$SIZE_T+$RZONE;
95 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
96 ( $xlate="${dir}ppc-xlate.pl" and -f $xlate ) or
97 ( $xlate="${dir}../../perlasm/ppc-xlate.pl" and -f $xlate) or
98 die "can't locate ppc-xlate.pl";
100 open STDOUT,"| $^X $xlate $flavour \"$output\""
101 or die "can't call $xlate: $!";
114 my $rp="r9"; # $rp is reassigned
118 # non-volatile registers
138 .globl .bn_mul_mont_int
141 mr $rp,r3 ; $rp is reassigned
144 $code.=<<___ if ($BNSZ==4);
145 cmpwi $num,32 ; longer key performance is not better
149 slwi $num,$num,`log($BNSZ)/log(2)`
151 addi $ovf,$num,$FRAME
152 subf $ovf,$ovf,$sp ; $sp-$ovf
153 and $ovf,$ovf,$tj ; minimize TLB usage
154 subf $ovf,$sp,$ovf ; $ovf-$sp
156 srwi $num,$num,`log($BNSZ)/log(2)`
159 $PUSH r20,`-12*$SIZE_T`($tj)
160 $PUSH r21,`-11*$SIZE_T`($tj)
161 $PUSH r22,`-10*$SIZE_T`($tj)
162 $PUSH r23,`-9*$SIZE_T`($tj)
163 $PUSH r24,`-8*$SIZE_T`($tj)
164 $PUSH r25,`-7*$SIZE_T`($tj)
165 $PUSH r26,`-6*$SIZE_T`($tj)
166 $PUSH r27,`-5*$SIZE_T`($tj)
167 $PUSH r28,`-4*$SIZE_T`($tj)
168 $PUSH r29,`-3*$SIZE_T`($tj)
169 $PUSH r30,`-2*$SIZE_T`($tj)
170 $PUSH r31,`-1*$SIZE_T`($tj)
172 $LD $n0,0($n0) ; pull n0[0] value
173 addi $num,$num,-2 ; adjust $num for counter register
175 $LD $m0,0($bp) ; m0=bp[0]
176 $LD $aj,0($ap) ; ap[0]
178 $UMULL $lo0,$aj,$m0 ; ap[0]*bp[0]
181 $LD $aj,$BNSZ($ap) ; ap[1]
182 $LD $nj,0($np) ; np[0]
184 $UMULL $m1,$lo0,$n0 ; "tp[0]"*n0
186 $UMULL $alo,$aj,$m0 ; ap[1]*bp[0]
189 $UMULL $lo1,$nj,$m1 ; np[0]*m1
191 $LD $nj,$BNSZ($np) ; np[1]
195 $UMULL $nlo,$nj,$m1 ; np[1]*m1
202 $LDX $aj,$ap,$j ; ap[j]
204 $LDX $nj,$np,$j ; np[j]
206 $UMULL $alo,$aj,$m0 ; ap[j]*bp[0]
210 $UMULL $nlo,$nj,$m1 ; np[j]*m1
211 addc $lo1,$lo1,$lo0 ; np[j]*m1+ap[j]*bp[0]
214 $ST $lo1,0($tp) ; tp[j-1]
216 addi $j,$j,$BNSZ ; j++
217 addi $tp,$tp,$BNSZ ; tp++
225 addc $lo1,$lo1,$lo0 ; np[j]*m1+ap[j]*bp[0]
227 $ST $lo1,0($tp) ; tp[j-1]
231 addze $ovf,$ovf ; upmost overflow bit
237 $LDX $m0,$bp,$i ; m0=bp[i]
238 $LD $aj,0($ap) ; ap[0]
240 $LD $tj,$LOCALS($sp); tp[0]
241 $UMULL $lo0,$aj,$m0 ; ap[0]*bp[i]
243 $LD $aj,$BNSZ($ap) ; ap[1]
244 $LD $nj,0($np) ; np[0]
245 addc $lo0,$lo0,$tj ; ap[0]*bp[i]+tp[0]
246 $UMULL $alo,$aj,$m0 ; ap[j]*bp[i]
248 $UMULL $m1,$lo0,$n0 ; tp[0]*n0
250 $UMULL $lo1,$nj,$m1 ; np[0]*m1
252 $LD $nj,$BNSZ($np) ; np[1]
254 $UMULL $nlo,$nj,$m1 ; np[1]*m1
262 $LDX $aj,$ap,$j ; ap[j]
264 $LD $tj,$BNSZ($tp) ; tp[j]
266 $LDX $nj,$np,$j ; np[j]
268 $UMULL $alo,$aj,$m0 ; ap[j]*bp[i]
271 addc $lo0,$lo0,$tj ; ap[j]*bp[i]+tp[j]
272 $UMULL $nlo,$nj,$m1 ; np[j]*m1
275 addc $lo1,$lo1,$lo0 ; np[j]*m1+ap[j]*bp[i]+tp[j]
276 addi $j,$j,$BNSZ ; j++
278 $ST $lo1,0($tp) ; tp[j-1]
279 addi $tp,$tp,$BNSZ ; tp++
282 $LD $tj,$BNSZ($tp) ; tp[j]
285 addc $lo0,$lo0,$tj ; ap[j]*bp[i]+tp[j]
290 addc $lo1,$lo1,$lo0 ; np[j]*m1+ap[j]*bp[i]+tp[j]
292 $ST $lo1,0($tp) ; tp[j-1]
294 addic $ovf,$ovf,-1 ; move upmost overflow to XER[CA]
300 slwi $tj,$num,`log($BNSZ)/log(2)`
305 addi $num,$num,2 ; restore $num
306 subfc $j,$j,$j ; j=0 and "clear" XER[CA]
311 Lsub: $LDX $tj,$tp,$j
313 subfe $aj,$nj,$tj ; tp[j]-np[j]
320 subfe $ovf,$j,$ovf ; handle upmost overflow bit
323 Lcopy: ; conditional copy
328 $STX $j,$tp,$j ; zap at once
336 $POP r20,`-12*$SIZE_T`($tj)
337 $POP r21,`-11*$SIZE_T`($tj)
338 $POP r22,`-10*$SIZE_T`($tj)
339 $POP r23,`-9*$SIZE_T`($tj)
340 $POP r24,`-8*$SIZE_T`($tj)
341 $POP r25,`-7*$SIZE_T`($tj)
342 $POP r26,`-6*$SIZE_T`($tj)
343 $POP r27,`-5*$SIZE_T`($tj)
344 $POP r28,`-4*$SIZE_T`($tj)
345 $POP r29,`-3*$SIZE_T`($tj)
346 $POP r30,`-2*$SIZE_T`($tj)
347 $POP r31,`-1*$SIZE_T`($tj)
351 .byte 0,12,4,0,0x80,12,6,0
353 .size .bn_mul_mont_int,.-.bn_mul_mont_int
360 $acc0,$acc1,$acc2,$acc3,$acc4,
361 $bi,$mi,$tp,$ap_end,$cnt) = map("r$_",(9..12,14..31));
362 my ($carry,$zero) = ($rp,"r0");
364 # sp----------->+-------------------------------+
366 # +-------------------------------+
368 # +8*size_t +-------------------------------+
372 # +12*size_t +-------------------------------+
373 # | size_t tmp[num] |
377 # +-------------------------------+
380 # -18*size_t +-------------------------------+
381 # | 18 saved gpr, r14-r31 |
384 # +-------------------------------+
386 .globl .bn_mul4x_mont_int
395 slwi $num,$num,`log($SIZE_T)/log(2)`
399 $STUX $sp,$sp,$a1 # alloca
401 $PUSH r14,-$SIZE_T*18($a0)
402 $PUSH r15,-$SIZE_T*17($a0)
403 $PUSH r16,-$SIZE_T*16($a0)
404 $PUSH r17,-$SIZE_T*15($a0)
405 $PUSH r18,-$SIZE_T*14($a0)
406 $PUSH r19,-$SIZE_T*13($a0)
407 $PUSH r20,-$SIZE_T*12($a0)
408 $PUSH r21,-$SIZE_T*11($a0)
409 $PUSH r22,-$SIZE_T*10($a0)
410 $PUSH r23,-$SIZE_T*9($a0)
411 $PUSH r24,-$SIZE_T*8($a0)
412 $PUSH r25,-$SIZE_T*7($a0)
413 $PUSH r26,-$SIZE_T*6($a0)
414 $PUSH r27,-$SIZE_T*5($a0)
415 $PUSH r28,-$SIZE_T*4($a0)
416 $PUSH r29,-$SIZE_T*3($a0)
417 $PUSH r30,-$SIZE_T*2($a0)
418 $PUSH r31,-$SIZE_T*1($a0)
420 subi $ap,$ap,$SIZE_T # bias by -1
421 subi $np,$np,$SIZE_T # bias by -1
422 subi $rp,$rp,$SIZE_T # bias by -1
427 subi $t0,$t0,$SIZE_T*4 # &b[num-4]
429 $LD $bi,$SIZE_T*0($bp) # b[0]
431 $LD $a0,$SIZE_T*1($ap) # a[0..3]
433 $LD $a1,$SIZE_T*2($ap)
435 $LD $a2,$SIZE_T*3($ap)
437 $LDU $a3,$SIZE_T*4($ap)
438 $LD $m0,$SIZE_T*1($np) # n[0..3]
439 $LD $m1,$SIZE_T*2($np)
440 $LD $m2,$SIZE_T*3($np)
441 $LDU $m3,$SIZE_T*4($np)
443 $PUSH $rp,$SIZE_T*6($sp) # offload rp and &b[num-4]
444 $PUSH $t0,$SIZE_T*7($sp)
446 addic $tp,$sp,$SIZE_T*7 # &t[-1], clear carry bit
449 b .Loop_mul4x_1st_reduction
452 .Loop_mul4x_1st_reduction:
453 $UMULL $t0,$a0,$bi # lo(a[0..3]*b[0])
454 addze $carry,$carry # modulo-scheduled
456 addi $cnt,$cnt,$SIZE_T
458 andi. $cnt,$cnt,$SIZE_T*4-1
461 $UMULH $t0,$a0,$bi # hi(a[0..3]*b[0])
465 $UMULL $mi,$acc0,$n0 # t[0]*n0
470 $LDX $bi,$bp,$cnt # next b[i] (or b[0])
472 # (*) mul $t0,$m0,$mi # lo(n[0..3]*t[0]*n0)
473 $STU $mi,$SIZE_T($tp) # put aside t[0]*n0 for tail processing
478 adde $acc4,$acc4,$t3 # can't overflow
480 # (*) addc $acc0,$acc0,$t0
481 # (*) As for removal of first multiplication and addition
482 # instructions. The outcome of first addition is
483 # guaranteed to be zero, which leaves two computationally
484 # significant outcomes: it either carries or not. Then
485 # question is when does it carry? Is there alternative
486 # way to deduce it? If you follow operations, you can
487 # observe that condition for carry is quite simple:
488 # $acc0 being non-zero. So that carry can be calculated
489 # by adding -1 to $acc0. That's what next instruction does.
490 addic $acc0,$acc0,-1 # (*), discarded
491 $UMULH $t0,$m0,$mi # hi(n[0..3]*t[0]*n0)
498 adde $acc3,$acc4,$carry
505 bne .Loop_mul4x_1st_reduction
508 beq .Lmul4x4_post_condition
510 $LD $a0,$SIZE_T*1($ap) # a[4..7]
511 $LD $a1,$SIZE_T*2($ap)
512 $LD $a2,$SIZE_T*3($ap)
513 $LDU $a3,$SIZE_T*4($ap)
514 $LD $mi,$SIZE_T*8($sp) # a[0]*n0
515 $LD $m0,$SIZE_T*1($np) # n[4..7]
516 $LD $m1,$SIZE_T*2($np)
517 $LD $m2,$SIZE_T*3($np)
518 $LDU $m3,$SIZE_T*4($np)
519 b .Loop_mul4x_1st_tail
522 .Loop_mul4x_1st_tail:
523 $UMULL $t0,$a0,$bi # lo(a[4..7]*b[i])
524 addze $carry,$carry # modulo-scheduled
526 addi $cnt,$cnt,$SIZE_T
528 andi. $cnt,$cnt,$SIZE_T*4-1
531 $UMULH $t0,$a0,$bi # hi(a[4..7]*b[i])
539 $LDX $bi,$bp,$cnt # next b[i] (or b[0])
541 $UMULL $t0,$m0,$mi # lo(n[4..7]*a[0]*n0)
546 adde $acc4,$acc4,$t3 # can't overflow
549 $UMULH $t0,$m0,$mi # hi(n[4..7]*a[0]*n0)
555 adde $acc4,$acc4,$carry
558 addi $mi,$sp,$SIZE_T*8
559 $LDX $mi,$mi,$cnt # next t[0]*n0
560 $STU $acc0,$SIZE_T($tp) # word of result
566 bne .Loop_mul4x_1st_tail
568 sub $t1,$ap_end,$num # rewinded $ap
569 $UCMP $ap_end,$ap # done yet?
572 $LD $a0,$SIZE_T*1($ap)
573 $LD $a1,$SIZE_T*2($ap)
574 $LD $a2,$SIZE_T*3($ap)
575 $LDU $a3,$SIZE_T*4($ap)
576 $LD $m0,$SIZE_T*1($np)
577 $LD $m1,$SIZE_T*2($np)
578 $LD $m2,$SIZE_T*3($np)
579 $LDU $m3,$SIZE_T*4($np)
580 b .Loop_mul4x_1st_tail
584 $LDU $bi,$SIZE_T*4($bp) # *++b
585 addze $carry,$carry # topmost carry
586 $LD $a0,$SIZE_T*1($t1)
587 $LD $a1,$SIZE_T*2($t1)
588 $LD $a2,$SIZE_T*3($t1)
589 $LD $a3,$SIZE_T*4($t1)
590 addi $ap,$t1,$SIZE_T*4
591 sub $np,$np,$num # rewind np
593 $ST $acc0,$SIZE_T*1($tp) # result
594 $ST $acc1,$SIZE_T*2($tp)
595 $ST $acc2,$SIZE_T*3($tp)
596 $ST $acc3,$SIZE_T*4($tp)
597 $ST $carry,$SIZE_T*5($tp) # save topmost carry
598 $LD $acc0,$SIZE_T*12($sp) # t[0..3]
599 $LD $acc1,$SIZE_T*13($sp)
600 $LD $acc2,$SIZE_T*14($sp)
601 $LD $acc3,$SIZE_T*15($sp)
603 $LD $m0,$SIZE_T*1($np) # n[0..3]
604 $LD $m1,$SIZE_T*2($np)
605 $LD $m2,$SIZE_T*3($np)
606 $LDU $m3,$SIZE_T*4($np)
607 addic $tp,$sp,$SIZE_T*7 # &t[-1], clear carry bit
609 b .Loop_mul4x_reduction
612 .Loop_mul4x_reduction:
613 $UMULL $t0,$a0,$bi # lo(a[0..3]*b[4])
614 addze $carry,$carry # modulo-scheduled
616 addi $cnt,$cnt,$SIZE_T
618 andi. $cnt,$cnt,$SIZE_T*4-1
621 $UMULH $t0,$a0,$bi # hi(a[0..3]*b[4])
625 $UMULL $mi,$acc0,$n0 # t[0]*n0
630 $LDX $bi,$bp,$cnt # next b[i]
632 # (*) mul $t0,$m0,$mi
633 $STU $mi,$SIZE_T($tp) # put aside t[0]*n0 for tail processing
635 $UMULL $t1,$m1,$mi # lo(n[0..3]*t[0]*n0
638 adde $acc4,$acc4,$t3 # can't overflow
640 # (*) addc $acc0,$acc0,$t0
641 addic $acc0,$acc0,-1 # (*), discarded
642 $UMULH $t0,$m0,$mi # hi(n[0..3]*t[0]*n0
649 adde $acc3,$acc4,$carry
656 bne .Loop_mul4x_reduction
658 $LD $t0,$SIZE_T*5($tp) # t[4..7]
660 $LD $t1,$SIZE_T*6($tp)
661 $LD $t2,$SIZE_T*7($tp)
662 $LD $t3,$SIZE_T*8($tp)
663 $LD $a0,$SIZE_T*1($ap) # a[4..7]
664 $LD $a1,$SIZE_T*2($ap)
665 $LD $a2,$SIZE_T*3($ap)
666 $LDU $a3,$SIZE_T*4($ap)
673 $LD $mi,$SIZE_T*8($sp) # t[0]*n0
674 $LD $m0,$SIZE_T*1($np) # n[4..7]
675 $LD $m1,$SIZE_T*2($np)
676 $LD $m2,$SIZE_T*3($np)
677 $LDU $m3,$SIZE_T*4($np)
682 $UMULL $t0,$a0,$bi # lo(a[4..7]*b[4])
683 addze $carry,$carry # modulo-scheduled
685 addi $cnt,$cnt,$SIZE_T
687 andi. $cnt,$cnt,$SIZE_T*4-1
690 $UMULH $t0,$a0,$bi # hi(a[4..7]*b[4])
698 $LDX $bi,$bp,$cnt # next b[i]
700 $UMULL $t0,$m0,$mi # lo(n[4..7]*t[0]*n0)
705 adde $acc4,$acc4,$t3 # can't overflow
708 $UMULH $t0,$m0,$mi # hi(n[4..7]*t[0]*n0)
715 adde $acc4,$acc4,$carry
716 addi $mi,$sp,$SIZE_T*8
717 $LDX $mi,$mi,$cnt # next a[0]*n0
719 $STU $acc0,$SIZE_T($tp) # word of result
727 $LD $t0,$SIZE_T*5($tp) # next t[i] or topmost carry
728 sub $t1,$np,$num # rewinded np?
730 $UCMP $ap_end,$ap # done yet?
731 beq .Loop_mul4x_break
733 $LD $t1,$SIZE_T*6($tp)
734 $LD $t2,$SIZE_T*7($tp)
735 $LD $t3,$SIZE_T*8($tp)
736 $LD $a0,$SIZE_T*1($ap)
737 $LD $a1,$SIZE_T*2($ap)
738 $LD $a2,$SIZE_T*3($ap)
739 $LDU $a3,$SIZE_T*4($ap)
746 $LD $m0,$SIZE_T*1($np) # n[4..7]
747 $LD $m1,$SIZE_T*2($np)
748 $LD $m2,$SIZE_T*3($np)
749 $LDU $m3,$SIZE_T*4($np)
754 $POP $t2,$SIZE_T*6($sp) # pull rp and &b[num-4]
755 $POP $t3,$SIZE_T*7($sp)
756 addc $a0,$acc0,$t0 # accumulate topmost carry
757 $LD $acc0,$SIZE_T*12($sp) # t[0..3]
759 $LD $acc1,$SIZE_T*13($sp)
761 $LD $acc2,$SIZE_T*14($sp)
763 $LD $acc3,$SIZE_T*15($sp)
764 addze $carry,$carry # topmost carry
765 $ST $a0,$SIZE_T*1($tp) # result
766 sub $ap,$ap_end,$num # rewind ap
767 $ST $a1,$SIZE_T*2($tp)
768 $ST $a2,$SIZE_T*3($tp)
769 $ST $a3,$SIZE_T*4($tp)
770 $ST $carry,$SIZE_T*5($tp) # store topmost carry
772 $LD $m0,$SIZE_T*1($t1) # n[0..3]
773 $LD $m1,$SIZE_T*2($t1)
774 $LD $m2,$SIZE_T*3($t1)
775 $LD $m3,$SIZE_T*4($t1)
776 addi $np,$t1,$SIZE_T*4
777 $UCMP $bp,$t3 # done yet?
780 $LDU $bi,$SIZE_T*4($bp)
781 $LD $a0,$SIZE_T*1($ap) # a[0..3]
782 $LD $a1,$SIZE_T*2($ap)
783 $LD $a2,$SIZE_T*3($ap)
784 $LDU $a3,$SIZE_T*4($ap)
786 addic $tp,$sp,$SIZE_T*7 # &t[-1], clear carry bit
787 b .Loop_mul4x_reduction
791 # Final step. We see if result is larger than modulus, and
792 # if it is, subtract the modulus. But comparison implies
793 # subtraction. So we subtract modulus, see if it borrowed,
794 # and conditionally copy original value.
795 srwi $cnt,$num,`log($SIZE_T)/log(2)+2`
798 mr $ap_end,$t2 # &rp[-1] copy
800 addi $tp,$sp,$SIZE_T*15
805 $LD $m0,$SIZE_T*1($np)
806 $LD $acc0,$SIZE_T*1($tp)
808 $LD $m1,$SIZE_T*2($np)
809 $LD $acc1,$SIZE_T*2($tp)
811 $LD $m2,$SIZE_T*3($np)
812 $LD $acc2,$SIZE_T*3($tp)
813 $LDU $m3,$SIZE_T*4($np)
814 $LDU $acc3,$SIZE_T*4($tp)
815 $ST $t0,$SIZE_T*1($bp)
816 $ST $t1,$SIZE_T*2($bp)
818 $ST $t2,$SIZE_T*3($bp)
819 $STU $t3,$SIZE_T*4($bp)
823 $LD $a0,$SIZE_T*1($ap_end)
824 $ST $t0,$SIZE_T*1($bp)
825 $LD $t0,$SIZE_T*12($sp)
827 $LD $a1,$SIZE_T*2($ap_end)
828 $ST $t1,$SIZE_T*2($bp)
829 $LD $t1,$SIZE_T*13($sp)
831 subfe $carry,$zero,$carry # did it borrow?
832 addi $tp,$sp,$SIZE_T*12
833 $LD $a2,$SIZE_T*3($ap_end)
834 $ST $t2,$SIZE_T*3($bp)
835 $LD $t2,$SIZE_T*14($sp)
836 $LD $a3,$SIZE_T*4($ap_end)
837 $ST $t3,$SIZE_T*4($bp)
838 $LD $t3,$SIZE_T*15($sp)
844 $ST $zero,$SIZE_T*0($tp) # wipe stack clean
847 $ST $zero,$SIZE_T*1($tp)
850 $ST $zero,$SIZE_T*2($tp)
853 $ST $zero,$SIZE_T*3($tp)
855 $LD $a0,$SIZE_T*5($ap_end)
856 $LD $t0,$SIZE_T*4($tp)
858 $LD $a1,$SIZE_T*6($ap_end)
859 $LD $t1,$SIZE_T*5($tp)
861 $LD $a2,$SIZE_T*7($ap_end)
862 $LD $t2,$SIZE_T*6($tp)
864 $LD $a3,$SIZE_T*8($ap_end)
865 $LD $t3,$SIZE_T*7($tp)
866 addi $tp,$tp,$SIZE_T*4
867 $ST $acc0,$SIZE_T*1($ap_end)
868 $ST $acc1,$SIZE_T*2($ap_end)
869 $ST $acc2,$SIZE_T*3($ap_end)
870 $STU $acc3,$SIZE_T*4($ap_end)
871 bdnz .Lmul4x_cond_copy
873 $POP $bp,0($sp) # pull saved sp
876 $ST $zero,$SIZE_T*0($tp)
879 $ST $zero,$SIZE_T*1($tp)
882 $ST $zero,$SIZE_T*2($tp)
885 $ST $zero,$SIZE_T*3($tp)
888 $ST $zero,$SIZE_T*4($tp)
891 $ST $acc0,$SIZE_T*1($ap_end)
892 $ST $acc1,$SIZE_T*2($ap_end)
893 $ST $acc2,$SIZE_T*3($ap_end)
894 $ST $acc3,$SIZE_T*4($ap_end)
899 .Lmul4x4_post_condition:
900 $POP $ap,$SIZE_T*6($sp) # pull &rp[-1]
901 $POP $bp,0($sp) # pull saved sp
902 addze $carry,$carry # modulo-scheduled
903 # $acc0-3,$carry hold result, $m0-3 hold modulus
908 subfe $carry,$zero,$carry # did it borrow?
919 $ST $a0,$SIZE_T*1($ap) # write result
920 $ST $a1,$SIZE_T*2($ap)
921 $ST $a2,$SIZE_T*3($ap)
922 $ST $a3,$SIZE_T*4($ap)
925 $ST $zero,$SIZE_T*8($sp) # wipe stack clean
926 $ST $zero,$SIZE_T*9($sp)
927 $ST $zero,$SIZE_T*10($sp)
928 $ST $zero,$SIZE_T*11($sp)
929 li r3,1 # signal "done"
930 $POP r14,-$SIZE_T*18($bp)
931 $POP r15,-$SIZE_T*17($bp)
932 $POP r16,-$SIZE_T*16($bp)
933 $POP r17,-$SIZE_T*15($bp)
934 $POP r18,-$SIZE_T*14($bp)
935 $POP r19,-$SIZE_T*13($bp)
936 $POP r20,-$SIZE_T*12($bp)
937 $POP r21,-$SIZE_T*11($bp)
938 $POP r22,-$SIZE_T*10($bp)
939 $POP r23,-$SIZE_T*9($bp)
940 $POP r24,-$SIZE_T*8($bp)
941 $POP r25,-$SIZE_T*7($bp)
942 $POP r26,-$SIZE_T*6($bp)
943 $POP r27,-$SIZE_T*5($bp)
944 $POP r28,-$SIZE_T*4($bp)
945 $POP r29,-$SIZE_T*3($bp)
946 $POP r30,-$SIZE_T*2($bp)
947 $POP r31,-$SIZE_T*1($bp)
951 .byte 0,12,4,0x20,0x80,18,6,0
953 .size .bn_mul4x_mont_int,.-.bn_mul4x_mont_int
958 ########################################################################
959 # Following is PPC adaptation of sqrx8x_mont from x86_64-mont5 module.
961 my ($a0,$a1,$a2,$a3,$a4,$a5,$a6,$a7)=map("r$_",(9..12,14..17));
962 my ($t0,$t1,$t2,$t3)=map("r$_",(18..21));
963 my ($acc0,$acc1,$acc2,$acc3,$acc4,$acc5,$acc6,$acc7)=map("r$_",(22..29));
964 my ($cnt,$carry,$zero)=("r30","r31","r0");
965 my ($tp,$ap_end,$na0)=($bp,$np,$carry);
967 # sp----------->+-------------------------------+
969 # +-------------------------------+
971 # +12*size_t +-------------------------------+
972 # | size_t tmp[2*num] |
976 # +-------------------------------+
978 # -18*size_t +-------------------------------+
979 # | 18 saved gpr, r14-r31 |
982 # +-------------------------------+
988 slwi $a1,$num,`log($SIZE_T)/log(2)+1`
991 slwi $num,$num,`log($SIZE_T)/log(2)`
992 $STUX $sp,$sp,$a1 # alloca
994 $PUSH r14,-$SIZE_T*18($a0)
995 $PUSH r15,-$SIZE_T*17($a0)
996 $PUSH r16,-$SIZE_T*16($a0)
997 $PUSH r17,-$SIZE_T*15($a0)
998 $PUSH r18,-$SIZE_T*14($a0)
999 $PUSH r19,-$SIZE_T*13($a0)
1000 $PUSH r20,-$SIZE_T*12($a0)
1001 $PUSH r21,-$SIZE_T*11($a0)
1002 $PUSH r22,-$SIZE_T*10($a0)
1003 $PUSH r23,-$SIZE_T*9($a0)
1004 $PUSH r24,-$SIZE_T*8($a0)
1005 $PUSH r25,-$SIZE_T*7($a0)
1006 $PUSH r26,-$SIZE_T*6($a0)
1007 $PUSH r27,-$SIZE_T*5($a0)
1008 $PUSH r28,-$SIZE_T*4($a0)
1009 $PUSH r29,-$SIZE_T*3($a0)
1010 $PUSH r30,-$SIZE_T*2($a0)
1011 $PUSH r31,-$SIZE_T*1($a0)
1013 subi $ap,$ap,$SIZE_T # bias by -1
1014 subi $t0,$np,$SIZE_T # bias by -1
1015 subi $rp,$rp,$SIZE_T # bias by -1
1016 $LD $n0,0($n0) # *n0
1019 add $ap_end,$ap,$num
1020 $LD $a0,$SIZE_T*1($ap)
1022 $LD $a1,$SIZE_T*2($ap)
1024 $LD $a2,$SIZE_T*3($ap)
1026 $LD $a3,$SIZE_T*4($ap)
1028 $LD $a4,$SIZE_T*5($ap)
1030 $LD $a5,$SIZE_T*6($ap)
1032 $LD $a6,$SIZE_T*7($ap)
1034 $LDU $a7,$SIZE_T*8($ap)
1037 addi $tp,$sp,$SIZE_T*11 # &tp[-1]
1038 subic. $cnt,$num,$SIZE_T*8
1039 b .Lsqr8x_zero_start
1043 subic. $cnt,$cnt,$SIZE_T*8
1044 $ST $zero,$SIZE_T*1($tp)
1045 $ST $zero,$SIZE_T*2($tp)
1046 $ST $zero,$SIZE_T*3($tp)
1047 $ST $zero,$SIZE_T*4($tp)
1048 $ST $zero,$SIZE_T*5($tp)
1049 $ST $zero,$SIZE_T*6($tp)
1050 $ST $zero,$SIZE_T*7($tp)
1051 $ST $zero,$SIZE_T*8($tp)
1053 $ST $zero,$SIZE_T*9($tp)
1054 $ST $zero,$SIZE_T*10($tp)
1055 $ST $zero,$SIZE_T*11($tp)
1056 $ST $zero,$SIZE_T*12($tp)
1057 $ST $zero,$SIZE_T*13($tp)
1058 $ST $zero,$SIZE_T*14($tp)
1059 $ST $zero,$SIZE_T*15($tp)
1060 $STU $zero,$SIZE_T*16($tp)
1063 $PUSH $rp,$SIZE_T*6($sp) # offload &rp[-1]
1064 $PUSH $t0,$SIZE_T*7($sp) # offload &np[-1]
1065 $PUSH $n0,$SIZE_T*8($sp) # offload n0
1066 $PUSH $tp,$SIZE_T*9($sp) # &tp[2*num-1]
1067 $PUSH $zero,$SIZE_T*10($sp) # initial top-most carry
1068 addi $tp,$sp,$SIZE_T*11 # &tp[-1]
1070 # Multiply everything but a[i]*a[i]
1102 $UMULL $t0,$a1,$a0 # lo(a[1..7]*a[0]) (i)
1106 addc $acc1,$acc1,$t0 # t[1]+lo(a[1]*a[0])
1108 adde $acc2,$acc2,$t1
1110 adde $acc3,$acc3,$t2
1112 adde $acc4,$acc4,$t3
1113 $UMULH $t3,$a1,$a0 # hi(a[1..7]*a[0])
1114 adde $acc5,$acc5,$t0
1116 adde $acc6,$acc6,$t1
1118 adde $acc7,$acc7,$t2
1120 $ST $acc0,$SIZE_T*1($tp) # t[0]
1121 addze $acc0,$zero # t[8]
1122 $ST $acc1,$SIZE_T*2($tp) # t[1]
1123 addc $acc2,$acc2,$t3 # t[2]+lo(a[1]*a[0])
1125 adde $acc3,$acc3,$t0
1127 adde $acc4,$acc4,$t1
1129 adde $acc5,$acc5,$t2
1130 $UMULL $t2,$a2,$a1 # lo(a[2..7]*a[1]) (ii)
1131 adde $acc6,$acc6,$t3
1133 adde $acc7,$acc7,$t0
1135 adde $acc0,$acc0,$t1
1138 addc $acc3,$acc3,$t2
1140 adde $acc4,$acc4,$t3
1142 adde $acc5,$acc5,$t0
1143 $UMULH $t0,$a2,$a1 # hi(a[2..7]*a[1])
1144 adde $acc6,$acc6,$t1
1146 adde $acc7,$acc7,$t2
1148 adde $acc0,$acc0,$t3
1150 $ST $acc2,$SIZE_T*3($tp) # t[2]
1151 addze $acc1,$zero # t[9]
1152 $ST $acc3,$SIZE_T*4($tp) # t[3]
1153 addc $acc4,$acc4,$t0
1155 adde $acc5,$acc5,$t1
1157 adde $acc6,$acc6,$t2
1158 $UMULL $t2,$a3,$a2 # lo(a[3..7]*a[2]) (iii)
1159 adde $acc7,$acc7,$t3
1161 adde $acc0,$acc0,$t0
1163 adde $acc1,$acc1,$t1
1166 addc $acc5,$acc5,$t2
1168 adde $acc6,$acc6,$t3
1169 $UMULH $t3,$a3,$a2 # hi(a[3..7]*a[2])
1170 adde $acc7,$acc7,$t0
1172 adde $acc0,$acc0,$t1
1174 adde $acc1,$acc1,$t2
1176 $ST $acc4,$SIZE_T*5($tp) # t[4]
1177 addze $acc2,$zero # t[10]
1178 $ST $acc5,$SIZE_T*6($tp) # t[5]
1179 addc $acc6,$acc6,$t3
1181 adde $acc7,$acc7,$t0
1182 $UMULL $t0,$a4,$a3 # lo(a[4..7]*a[3]) (iv)
1183 adde $acc0,$acc0,$t1
1185 adde $acc1,$acc1,$t2
1187 adde $acc2,$acc2,$t3
1190 addc $acc7,$acc7,$t0
1191 $UMULH $t0,$a4,$a3 # hi(a[4..7]*a[3])
1192 adde $acc0,$acc0,$t1
1194 adde $acc1,$acc1,$t2
1196 adde $acc2,$acc2,$t3
1198 $ST $acc6,$SIZE_T*7($tp) # t[6]
1199 addze $acc3,$zero # t[11]
1200 $STU $acc7,$SIZE_T*8($tp) # t[7]
1201 addc $acc0,$acc0,$t0
1202 $UMULL $t0,$a5,$a4 # lo(a[5..7]*a[4]) (v)
1203 adde $acc1,$acc1,$t1
1205 adde $acc2,$acc2,$t2
1207 adde $acc3,$acc3,$t3
1209 $UMULH $t3,$a5,$a4 # hi(a[5..7]*a[4])
1210 addc $acc1,$acc1,$t0
1212 adde $acc2,$acc2,$t1
1214 adde $acc3,$acc3,$t2
1215 $UMULL $t2,$a6,$a5 # lo(a[6..7]*a[5]) (vi)
1216 addze $acc4,$zero # t[12]
1217 addc $acc2,$acc2,$t3
1219 adde $acc3,$acc3,$t0
1220 $UMULH $t0,$a6,$a5 # hi(a[6..7]*a[5])
1221 adde $acc4,$acc4,$t1
1224 addc $acc3,$acc3,$t2
1225 $UMULL $t2,$a7,$a6 # lo(a[7]*a[6]) (vii)
1226 adde $acc4,$acc4,$t3
1227 $UMULH $t3,$a7,$a6 # hi(a[7]*a[6])
1228 addze $acc5,$zero # t[13]
1229 addc $acc4,$acc4,$t0
1230 $UCMP $ap_end,$ap # done yet?
1231 adde $acc5,$acc5,$t1
1233 addc $acc5,$acc5,$t2
1234 sub $t0,$ap_end,$num # rewinded ap
1235 addze $acc6,$zero # t[14]
1238 beq .Lsqr8x_outer_break
1241 $LD $a0,$SIZE_T*1($tp)
1242 $LD $a1,$SIZE_T*2($tp)
1243 $LD $a2,$SIZE_T*3($tp)
1244 $LD $a3,$SIZE_T*4($tp)
1245 $LD $a4,$SIZE_T*5($tp)
1246 $LD $a5,$SIZE_T*6($tp)
1247 $LD $a6,$SIZE_T*7($tp)
1248 $LD $a7,$SIZE_T*8($tp)
1249 addc $acc0,$acc0,$a0
1250 $LD $a0,$SIZE_T*1($ap)
1251 adde $acc1,$acc1,$a1
1252 $LD $a1,$SIZE_T*2($ap)
1253 adde $acc2,$acc2,$a2
1254 $LD $a2,$SIZE_T*3($ap)
1255 adde $acc3,$acc3,$a3
1256 $LD $a3,$SIZE_T*4($ap)
1257 adde $acc4,$acc4,$a4
1258 $LD $a4,$SIZE_T*5($ap)
1259 adde $acc5,$acc5,$a5
1260 $LD $a5,$SIZE_T*6($ap)
1261 adde $acc6,$acc6,$a6
1262 $LD $a6,$SIZE_T*7($ap)
1263 subi $rp,$ap,$SIZE_T*7
1265 $LDU $a7,$SIZE_T*8($ap)
1266 #addze $carry,$zero # moved below
1279 # a[f]a[1]........................
1281 # a[f]a[2]........................
1283 # a[f]a[3]........................
1285 # a[f]a[4]........................
1287 # a[f]a[5]........................
1289 # a[f]a[6]........................
1291 # a[f]a[7]........................
1295 addze $carry,$zero # carry bit, modulo-scheduled
1297 addi $cnt,$cnt,$SIZE_T
1299 andi. $cnt,$cnt,$SIZE_T*8-1
1301 addc $acc0,$acc0,$t0
1303 adde $acc1,$acc1,$t1
1305 adde $acc2,$acc2,$t2
1307 adde $acc3,$acc3,$t3
1309 adde $acc4,$acc4,$t0
1311 adde $acc5,$acc5,$t1
1313 adde $acc6,$acc6,$t2
1315 adde $acc7,$acc7,$t3
1318 $STU $acc0,$SIZE_T($tp)
1319 addc $acc0,$acc1,$t0
1321 adde $acc1,$acc2,$t1
1323 adde $acc2,$acc3,$t2
1325 adde $acc3,$acc4,$t3
1328 adde $acc4,$acc5,$t0
1329 adde $acc5,$acc6,$t1
1330 adde $acc6,$acc7,$t2
1331 adde $acc7,$carry,$t3
1332 #addze $carry,$zero # moved above
1334 # note that carry flag is guaranteed
1335 # to be zero at this point
1336 $UCMP $ap,$ap_end # done yet?
1339 $LD $a0,$SIZE_T*1($tp)
1340 $LD $a1,$SIZE_T*2($tp)
1341 $LD $a2,$SIZE_T*3($tp)
1342 $LD $a3,$SIZE_T*4($tp)
1343 $LD $a4,$SIZE_T*5($tp)
1344 $LD $a5,$SIZE_T*6($tp)
1345 $LD $a6,$SIZE_T*7($tp)
1346 $LD $a7,$SIZE_T*8($tp)
1347 addc $acc0,$acc0,$a0
1348 $LD $a0,$SIZE_T*1($ap)
1349 adde $acc1,$acc1,$a1
1350 $LD $a1,$SIZE_T*2($ap)
1351 adde $acc2,$acc2,$a2
1352 $LD $a2,$SIZE_T*3($ap)
1353 adde $acc3,$acc3,$a3
1354 $LD $a3,$SIZE_T*4($ap)
1355 adde $acc4,$acc4,$a4
1356 $LD $a4,$SIZE_T*5($ap)
1357 adde $acc5,$acc5,$a5
1358 $LD $a5,$SIZE_T*6($ap)
1359 adde $acc6,$acc6,$a6
1360 $LD $a6,$SIZE_T*7($ap)
1361 adde $acc7,$acc7,$a7
1362 $LDU $a7,$SIZE_T*8($ap)
1363 #addze $carry,$zero # moved above
1368 $LD $a0,$SIZE_T*8($rp)
1369 addi $ap,$rp,$SIZE_T*15
1370 $LD $a1,$SIZE_T*9($rp)
1371 sub. $t0,$ap_end,$ap # is it last iteration?
1372 $LD $a2,$SIZE_T*10($rp)
1374 $LD $a3,$SIZE_T*11($rp)
1375 $LD $a4,$SIZE_T*12($rp)
1376 $LD $a5,$SIZE_T*13($rp)
1377 $LD $a6,$SIZE_T*14($rp)
1378 $LD $a7,$SIZE_T*15($rp)
1379 beq .Lsqr8x_outer_loop
1381 $ST $acc0,$SIZE_T*1($tp)
1382 $LD $acc0,$SIZE_T*1($t1)
1383 $ST $acc1,$SIZE_T*2($tp)
1384 $LD $acc1,$SIZE_T*2($t1)
1385 $ST $acc2,$SIZE_T*3($tp)
1386 $LD $acc2,$SIZE_T*3($t1)
1387 $ST $acc3,$SIZE_T*4($tp)
1388 $LD $acc3,$SIZE_T*4($t1)
1389 $ST $acc4,$SIZE_T*5($tp)
1390 $LD $acc4,$SIZE_T*5($t1)
1391 $ST $acc5,$SIZE_T*6($tp)
1392 $LD $acc5,$SIZE_T*6($t1)
1393 $ST $acc6,$SIZE_T*7($tp)
1394 $LD $acc6,$SIZE_T*7($t1)
1395 $ST $acc7,$SIZE_T*8($tp)
1396 $LD $acc7,$SIZE_T*8($t1)
1398 b .Lsqr8x_outer_loop
1401 .Lsqr8x_outer_break:
1402 ####################################################################
1403 # Now multiply above result by 2 and add a[n-1]*a[n-1]|...|a[0]*a[0]
1404 $LD $a1,$SIZE_T*1($t0) # recall that $t0 is &a[-1]
1405 $LD $a3,$SIZE_T*2($t0)
1406 $LD $a5,$SIZE_T*3($t0)
1407 $LD $a7,$SIZE_T*4($t0)
1408 addi $ap,$t0,$SIZE_T*4
1409 # "tp[x]" comments are for num==8 case
1410 $LD $t1,$SIZE_T*13($sp) # =tp[1], t[0] is not interesting
1411 $LD $t2,$SIZE_T*14($sp)
1412 $LD $t3,$SIZE_T*15($sp)
1413 $LD $t0,$SIZE_T*16($sp)
1415 $ST $acc0,$SIZE_T*1($tp) # tp[8]=
1416 srwi $cnt,$num,`log($SIZE_T)/log(2)+2`
1417 $ST $acc1,$SIZE_T*2($tp)
1419 $ST $acc2,$SIZE_T*3($tp)
1420 $ST $acc3,$SIZE_T*4($tp)
1421 $ST $acc4,$SIZE_T*5($tp)
1422 $ST $acc5,$SIZE_T*6($tp)
1423 $ST $acc6,$SIZE_T*7($tp)
1424 #$ST $acc7,$SIZE_T*8($tp) # tp[15] is not interesting
1425 addi $tp,$sp,$SIZE_T*11 # &tp[-1]
1426 $UMULL $acc0,$a1,$a1
1428 add $acc1,$t1,$t1 # <<1
1429 $SHRI $t1,$t1,$BITS-1
1432 addc $acc1,$acc1,$a1
1434 $SHRI $t2,$t2,$BITS-1
1436 $SHRI $t3,$t3,$BITS-1
1440 .Lsqr4x_shift_n_add:
1443 $LD $t1,$SIZE_T*6($tp) # =tp[5]
1444 $LD $a1,$SIZE_T*1($ap)
1445 adde $acc2,$acc2,$a2
1447 $SHRI $t0,$t0,$BITS-1
1449 $LD $t2,$SIZE_T*7($tp) # =tp[6]
1450 adde $acc3,$acc3,$a3
1451 $LD $a3,$SIZE_T*2($ap)
1453 $SHRI $t1,$t1,$BITS-1
1455 $LD $t3,$SIZE_T*8($tp) # =tp[7]
1458 adde $acc4,$acc4,$a4
1460 $SHRI $t2,$t2,$BITS-1
1462 $LD $t0,$SIZE_T*9($tp) # =tp[8]
1463 adde $acc5,$acc5,$a5
1464 $LD $a5,$SIZE_T*3($ap)
1466 $SHRI $t3,$t3,$BITS-1
1468 $LD $t1,$SIZE_T*10($tp) # =tp[9]
1471 adde $acc6,$acc6,$a6
1472 $ST $acc0,$SIZE_T*1($tp) # tp[0]=
1474 $SHRI $t0,$t0,$BITS-1
1476 $LD $t2,$SIZE_T*11($tp) # =tp[10]
1477 adde $acc7,$acc7,$a7
1478 $LDU $a7,$SIZE_T*4($ap)
1479 $ST $acc1,$SIZE_T*2($tp) # tp[1]=
1481 $SHRI $t1,$t1,$BITS-1
1483 $LD $t3,$SIZE_T*12($tp) # =tp[11]
1486 adde $acc0,$acc0,$a0
1487 $ST $acc2,$SIZE_T*3($tp) # tp[2]=
1489 $SHRI $t2,$t2,$BITS-1
1491 $LD $t0,$SIZE_T*13($tp) # =tp[12]
1492 adde $acc1,$acc1,$a1
1493 $ST $acc3,$SIZE_T*4($tp) # tp[3]=
1494 $ST $acc4,$SIZE_T*5($tp) # tp[4]=
1495 $ST $acc5,$SIZE_T*6($tp) # tp[5]=
1496 $ST $acc6,$SIZE_T*7($tp) # tp[6]=
1497 $STU $acc7,$SIZE_T*8($tp) # tp[7]=
1499 $SHRI $t3,$t3,$BITS-1
1501 bdnz .Lsqr4x_shift_n_add
1503 my ($np,$np_end)=($ap,$ap_end);
1505 $POP $np,$SIZE_T*7($sp) # pull &np[-1] and n0
1506 $POP $n0,$SIZE_T*8($sp)
1510 $ST $acc0,$SIZE_T*1($tp) # tp[8]=
1511 $LD $acc0,$SIZE_T*12($sp) # =tp[0]
1512 $LD $t1,$SIZE_T*6($tp) # =tp[13]
1513 adde $acc2,$acc2,$a2
1515 $SHRI $t0,$t0,$BITS-1
1517 $LD $t2,$SIZE_T*7($tp) # =tp[14]
1518 adde $acc3,$acc3,$a3
1520 $SHRI $t1,$t1,$BITS-1
1524 adde $acc4,$acc4,$a4
1526 $SHRI $t2,$t2,$BITS-1
1528 $ST $acc1,$SIZE_T*2($tp) # tp[9]=
1529 $LD $acc1,$SIZE_T*13($sp) # =tp[1]
1530 adde $acc5,$acc5,$a5
1532 $LD $a0,$SIZE_T*1($np)
1533 $LD $a1,$SIZE_T*2($np)
1534 adde $acc6,$acc6,$a6
1535 $LD $a2,$SIZE_T*3($np)
1536 $LD $a3,$SIZE_T*4($np)
1538 $LD $a4,$SIZE_T*5($np)
1539 $LD $a5,$SIZE_T*6($np)
1541 ################################################################
1542 # Reduce by 8 limbs per iteration
1543 $UMULL $na0,$n0,$acc0 # t[0]*n0
1545 $LD $a6,$SIZE_T*7($np)
1546 add $np_end,$np,$num
1547 $LDU $a7,$SIZE_T*8($np)
1548 $ST $acc2,$SIZE_T*3($tp) # tp[10]=
1549 $LD $acc2,$SIZE_T*14($sp)
1550 $ST $acc3,$SIZE_T*4($tp) # tp[11]=
1551 $LD $acc3,$SIZE_T*15($sp)
1552 $ST $acc4,$SIZE_T*5($tp) # tp[12]=
1553 $LD $acc4,$SIZE_T*16($sp)
1554 $ST $acc5,$SIZE_T*6($tp) # tp[13]=
1555 $LD $acc5,$SIZE_T*17($sp)
1556 $ST $acc6,$SIZE_T*7($tp) # tp[14]=
1557 $LD $acc6,$SIZE_T*18($sp)
1558 $ST $acc7,$SIZE_T*8($tp) # tp[15]=
1559 $LD $acc7,$SIZE_T*19($sp)
1560 addi $tp,$sp,$SIZE_T*11 # &tp[-1]
1566 # (*) $UMULL $t0,$a0,$na0 # lo(n[0-7])*lo(t[0]*n0)
1569 $STU $na0,$SIZE_T($tp) # put aside t[0]*n0 for tail processing
1571 # (*) addc $acc0,$acc0,$t0
1572 addic $acc0,$acc0,-1 # (*)
1574 adde $acc0,$acc1,$t1
1576 adde $acc1,$acc2,$t2
1578 adde $acc2,$acc3,$t3
1580 adde $acc3,$acc4,$t0
1581 $UMULH $t0,$a0,$na0 # hi(n[0-7])*lo(t[0]*n0)
1582 adde $acc4,$acc5,$t1
1584 adde $acc5,$acc6,$t2
1586 adde $acc6,$acc7,$t3
1589 addc $acc0,$acc0,$t0
1591 adde $acc1,$acc1,$t1
1593 adde $acc2,$acc2,$t2
1595 adde $acc3,$acc3,$t3
1597 $UMULL $na0,$n0,$acc0 # next t[0]*n0
1598 adde $acc4,$acc4,$t0
1599 adde $acc5,$acc5,$t1
1600 adde $acc6,$acc6,$t2
1601 adde $acc7,$acc7,$t3
1602 bdnz .Lsqr8x_reduction
1604 $LD $t0,$SIZE_T*1($tp)
1605 $LD $t1,$SIZE_T*2($tp)
1606 $LD $t2,$SIZE_T*3($tp)
1607 $LD $t3,$SIZE_T*4($tp)
1608 subi $rp,$tp,$SIZE_T*7
1609 $UCMP $np_end,$np # done yet?
1610 addc $acc0,$acc0,$t0
1611 $LD $t0,$SIZE_T*5($tp)
1612 adde $acc1,$acc1,$t1
1613 $LD $t1,$SIZE_T*6($tp)
1614 adde $acc2,$acc2,$t2
1615 $LD $t2,$SIZE_T*7($tp)
1616 adde $acc3,$acc3,$t3
1617 $LD $t3,$SIZE_T*8($tp)
1618 adde $acc4,$acc4,$t0
1619 adde $acc5,$acc5,$t1
1620 adde $acc6,$acc6,$t2
1621 adde $acc7,$acc7,$t3
1622 #addze $carry,$zero # moved below
1623 beq .Lsqr8x8_post_condition
1625 $LD $n0,$SIZE_T*0($rp)
1626 $LD $a0,$SIZE_T*1($np)
1627 $LD $a1,$SIZE_T*2($np)
1628 $LD $a2,$SIZE_T*3($np)
1629 $LD $a3,$SIZE_T*4($np)
1630 $LD $a4,$SIZE_T*5($np)
1631 $LD $a5,$SIZE_T*6($np)
1632 $LD $a6,$SIZE_T*7($np)
1633 $LDU $a7,$SIZE_T*8($np)
1639 addze $carry,$zero # carry bit, modulo-scheduled
1641 addi $cnt,$cnt,$SIZE_T
1643 andi. $cnt,$cnt,$SIZE_T*8-1
1645 addc $acc0,$acc0,$t0
1647 adde $acc1,$acc1,$t1
1649 adde $acc2,$acc2,$t2
1651 adde $acc3,$acc3,$t3
1653 adde $acc4,$acc4,$t0
1655 adde $acc5,$acc5,$t1
1657 adde $acc6,$acc6,$t2
1659 adde $acc7,$acc7,$t3
1662 $STU $acc0,$SIZE_T($tp)
1663 addc $acc0,$acc1,$t0
1665 adde $acc1,$acc2,$t1
1667 adde $acc2,$acc3,$t2
1669 adde $acc3,$acc4,$t3
1672 adde $acc4,$acc5,$t0
1673 adde $acc5,$acc6,$t1
1674 adde $acc6,$acc7,$t2
1675 adde $acc7,$carry,$t3
1676 #addze $carry,$zero # moved above
1678 # note that carry flag is guaranteed
1679 # to be zero at this point
1680 $LD $a0,$SIZE_T*1($tp)
1681 $POP $carry,$SIZE_T*10($sp) # pull top-most carry in case we break
1682 $UCMP $np_end,$np # done yet?
1683 $LD $a1,$SIZE_T*2($tp)
1684 sub $t2,$np_end,$num # rewinded np
1685 $LD $a2,$SIZE_T*3($tp)
1686 $LD $a3,$SIZE_T*4($tp)
1687 $LD $a4,$SIZE_T*5($tp)
1688 $LD $a5,$SIZE_T*6($tp)
1689 $LD $a6,$SIZE_T*7($tp)
1690 $LD $a7,$SIZE_T*8($tp)
1691 beq .Lsqr8x_tail_break
1693 addc $acc0,$acc0,$a0
1694 $LD $a0,$SIZE_T*1($np)
1695 adde $acc1,$acc1,$a1
1696 $LD $a1,$SIZE_T*2($np)
1697 adde $acc2,$acc2,$a2
1698 $LD $a2,$SIZE_T*3($np)
1699 adde $acc3,$acc3,$a3
1700 $LD $a3,$SIZE_T*4($np)
1701 adde $acc4,$acc4,$a4
1702 $LD $a4,$SIZE_T*5($np)
1703 adde $acc5,$acc5,$a5
1704 $LD $a5,$SIZE_T*6($np)
1705 adde $acc6,$acc6,$a6
1706 $LD $a6,$SIZE_T*7($np)
1707 adde $acc7,$acc7,$a7
1708 $LDU $a7,$SIZE_T*8($np)
1709 #addze $carry,$zero # moved above
1714 $POP $n0,$SIZE_T*8($sp) # pull n0
1715 $POP $t3,$SIZE_T*9($sp) # &tp[2*num-1]
1716 addi $cnt,$tp,$SIZE_T*8 # end of current t[num] window
1718 addic $carry,$carry,-1 # "move" top-most carry to carry bit
1720 $LD $acc0,$SIZE_T*8($rp)
1721 $LD $a0,$SIZE_T*1($t2) # recall that $t2 is &n[-1]
1723 $LD $acc1,$SIZE_T*9($rp)
1724 $LD $a1,$SIZE_T*2($t2)
1725 adde $acc2,$acc2,$a2
1726 $LD $a2,$SIZE_T*3($t2)
1727 adde $acc3,$acc3,$a3
1728 $LD $a3,$SIZE_T*4($t2)
1729 adde $acc4,$acc4,$a4
1730 $LD $a4,$SIZE_T*5($t2)
1731 adde $acc5,$acc5,$a5
1732 $LD $a5,$SIZE_T*6($t2)
1733 adde $acc6,$acc6,$a6
1734 $LD $a6,$SIZE_T*7($t2)
1735 adde $acc7,$acc7,$a7
1736 $LD $a7,$SIZE_T*8($t2)
1737 addi $np,$t2,$SIZE_T*8
1738 addze $t2,$zero # top-most carry
1739 $UMULL $na0,$n0,$acc0
1740 $ST $t0,$SIZE_T*1($tp)
1741 $UCMP $cnt,$t3 # did we hit the bottom?
1742 $ST $t1,$SIZE_T*2($tp)
1744 $ST $acc2,$SIZE_T*3($tp)
1745 $LD $acc2,$SIZE_T*10($rp)
1746 $ST $acc3,$SIZE_T*4($tp)
1747 $LD $acc3,$SIZE_T*11($rp)
1748 $ST $acc4,$SIZE_T*5($tp)
1749 $LD $acc4,$SIZE_T*12($rp)
1750 $ST $acc5,$SIZE_T*6($tp)
1751 $LD $acc5,$SIZE_T*13($rp)
1752 $ST $acc6,$SIZE_T*7($tp)
1753 $LD $acc6,$SIZE_T*14($rp)
1754 $ST $acc7,$SIZE_T*8($tp)
1755 $LD $acc7,$SIZE_T*15($rp)
1756 $PUSH $t2,$SIZE_T*10($sp) # off-load top-most carry
1757 addi $tp,$rp,$SIZE_T*7 # slide the window
1759 bne .Lsqr8x_reduction
1761 ################################################################
1762 # Final step. We see if result is larger than modulus, and
1763 # if it is, subtract the modulus. But comparison implies
1764 # subtraction. So we subtract modulus, see if it borrowed,
1765 # and conditionally copy original value.
1766 $POP $rp,$SIZE_T*6($sp) # pull &rp[-1]
1767 srwi $cnt,$num,`log($SIZE_T)/log(2)+3`
1768 mr $n0,$tp # put tp aside
1769 addi $tp,$tp,$SIZE_T*8
1774 mr $ap_end,$rp # $rp copy
1781 $LD $a0,$SIZE_T*1($np)
1782 $LD $acc0,$SIZE_T*1($tp)
1783 $LD $a1,$SIZE_T*2($np)
1784 $LD $acc1,$SIZE_T*2($tp)
1786 $LD $a2,$SIZE_T*3($np)
1787 $LD $acc2,$SIZE_T*3($tp)
1789 $LD $a3,$SIZE_T*4($np)
1790 $LD $acc3,$SIZE_T*4($tp)
1791 $ST $t0,$SIZE_T*1($rp)
1793 $LD $a4,$SIZE_T*5($np)
1794 $LD $acc4,$SIZE_T*5($tp)
1795 $ST $t1,$SIZE_T*2($rp)
1797 $LD $a5,$SIZE_T*6($np)
1798 $LD $acc5,$SIZE_T*6($tp)
1799 $ST $t2,$SIZE_T*3($rp)
1801 $LD $a6,$SIZE_T*7($np)
1802 $LD $acc6,$SIZE_T*7($tp)
1803 $ST $t3,$SIZE_T*4($rp)
1805 $LDU $a7,$SIZE_T*8($np)
1806 $LDU $acc7,$SIZE_T*8($tp)
1807 $ST $t0,$SIZE_T*5($rp)
1809 $ST $t1,$SIZE_T*6($rp)
1811 $ST $t2,$SIZE_T*7($rp)
1812 $STU $t3,$SIZE_T*8($rp)
1815 srwi $cnt,$num,`log($SIZE_T)/log(2)+2`
1816 $LD $a0,$SIZE_T*1($ap_end) # original $rp
1817 $LD $acc0,$SIZE_T*1($n0) # original $tp
1819 $LD $a1,$SIZE_T*2($ap_end)
1820 $LD $acc1,$SIZE_T*2($n0)
1822 $LD $a2,$SIZE_T*3($ap_end)
1823 $LD $acc2,$SIZE_T*3($n0)
1825 $LD $a3,$SIZE_T*4($ap_end)
1826 $LDU $acc3,$SIZE_T*4($n0)
1827 $ST $t0,$SIZE_T*1($rp)
1829 $ST $t1,$SIZE_T*2($rp)
1831 $ST $t2,$SIZE_T*3($rp)
1833 $ST $t3,$SIZE_T*4($rp)
1835 $ST $t0,$SIZE_T*5($rp)
1836 subfe $carry,$zero,$carry # did it borrow?
1837 $ST $t1,$SIZE_T*6($rp)
1838 $ST $t2,$SIZE_T*7($rp)
1839 $ST $t3,$SIZE_T*8($rp)
1841 addi $tp,$sp,$SIZE_T*11
1846 $ST $zero,-$SIZE_T*3($n0) # wipe stack clean
1847 and $acc0,$acc0,$carry
1848 $ST $zero,-$SIZE_T*2($n0)
1850 $ST $zero,-$SIZE_T*1($n0)
1851 and $acc1,$acc1,$carry
1852 $ST $zero,-$SIZE_T*0($n0)
1854 $ST $zero,$SIZE_T*1($tp)
1855 and $acc2,$acc2,$carry
1856 $ST $zero,$SIZE_T*2($tp)
1858 $ST $zero,$SIZE_T*3($tp)
1859 and $acc3,$acc3,$carry
1860 $STU $zero,$SIZE_T*4($tp)
1862 $LD $a0,$SIZE_T*5($ap_end)
1863 $LD $acc0,$SIZE_T*1($n0)
1865 $LD $a1,$SIZE_T*6($ap_end)
1866 $LD $acc1,$SIZE_T*2($n0)
1868 $LD $a2,$SIZE_T*7($ap_end)
1869 $LD $acc2,$SIZE_T*3($n0)
1871 $LD $a3,$SIZE_T*8($ap_end)
1872 $LDU $acc3,$SIZE_T*4($n0)
1873 $ST $t0,$SIZE_T*1($ap_end)
1874 $ST $t1,$SIZE_T*2($ap_end)
1875 $ST $t2,$SIZE_T*3($ap_end)
1876 $STU $t3,$SIZE_T*4($ap_end)
1877 bdnz .Lsqr4x_cond_copy
1879 $POP $ap,0($sp) # pull saved sp
1881 and $acc0,$acc0,$carry
1883 and $acc1,$acc1,$carry
1885 and $acc2,$acc2,$carry
1887 and $acc3,$acc3,$carry
1892 $ST $t0,$SIZE_T*1($ap_end)
1893 $ST $t1,$SIZE_T*2($ap_end)
1894 $ST $t2,$SIZE_T*3($ap_end)
1895 $ST $t3,$SIZE_T*4($ap_end)
1900 .Lsqr8x8_post_condition:
1901 $POP $rp,$SIZE_T*6($sp) # pull rp
1902 $POP $ap,0($sp) # pull saved sp
1905 # $acc0-7,$carry hold result, $a0-7 hold modulus
1906 subfc $acc0,$a0,$acc0
1907 subfe $acc1,$a1,$acc1
1908 $ST $zero,$SIZE_T*12($sp) # wipe stack clean
1909 $ST $zero,$SIZE_T*13($sp)
1910 subfe $acc2,$a2,$acc2
1911 $ST $zero,$SIZE_T*14($sp)
1912 $ST $zero,$SIZE_T*15($sp)
1913 subfe $acc3,$a3,$acc3
1914 $ST $zero,$SIZE_T*16($sp)
1915 $ST $zero,$SIZE_T*17($sp)
1916 subfe $acc4,$a4,$acc4
1917 $ST $zero,$SIZE_T*18($sp)
1918 $ST $zero,$SIZE_T*19($sp)
1919 subfe $acc5,$a5,$acc5
1920 $ST $zero,$SIZE_T*20($sp)
1921 $ST $zero,$SIZE_T*21($sp)
1922 subfe $acc6,$a6,$acc6
1923 $ST $zero,$SIZE_T*22($sp)
1924 $ST $zero,$SIZE_T*23($sp)
1925 subfe $acc7,$a7,$acc7
1926 $ST $zero,$SIZE_T*24($sp)
1927 $ST $zero,$SIZE_T*25($sp)
1928 subfe $carry,$zero,$carry # did it borrow?
1929 $ST $zero,$SIZE_T*26($sp)
1930 $ST $zero,$SIZE_T*27($sp)
1934 addc $acc0,$acc0,$a0 # add modulus back if borrowed
1936 adde $acc1,$acc1,$a1
1938 adde $acc2,$acc2,$a2
1940 adde $acc3,$acc3,$a3
1942 adde $acc4,$acc4,$a4
1944 adde $acc5,$acc5,$a5
1946 adde $acc6,$acc6,$a6
1947 adde $acc7,$acc7,$a7
1948 $ST $acc0,$SIZE_T*1($rp)
1949 $ST $acc1,$SIZE_T*2($rp)
1950 $ST $acc2,$SIZE_T*3($rp)
1951 $ST $acc3,$SIZE_T*4($rp)
1952 $ST $acc4,$SIZE_T*5($rp)
1953 $ST $acc5,$SIZE_T*6($rp)
1954 $ST $acc6,$SIZE_T*7($rp)
1955 $ST $acc7,$SIZE_T*8($rp)
1958 $PUSH $zero,$SIZE_T*8($sp)
1959 $PUSH $zero,$SIZE_T*10($sp)
1961 $POP r14,-$SIZE_T*18($ap)
1962 li r3,1 # signal "done"
1963 $POP r15,-$SIZE_T*17($ap)
1964 $POP r16,-$SIZE_T*16($ap)
1965 $POP r17,-$SIZE_T*15($ap)
1966 $POP r18,-$SIZE_T*14($ap)
1967 $POP r19,-$SIZE_T*13($ap)
1968 $POP r20,-$SIZE_T*12($ap)
1969 $POP r21,-$SIZE_T*11($ap)
1970 $POP r22,-$SIZE_T*10($ap)
1971 $POP r23,-$SIZE_T*9($ap)
1972 $POP r24,-$SIZE_T*8($ap)
1973 $POP r25,-$SIZE_T*7($ap)
1974 $POP r26,-$SIZE_T*6($ap)
1975 $POP r27,-$SIZE_T*5($ap)
1976 $POP r28,-$SIZE_T*4($ap)
1977 $POP r29,-$SIZE_T*3($ap)
1978 $POP r30,-$SIZE_T*2($ap)
1979 $POP r31,-$SIZE_T*1($ap)
1983 .byte 0,12,4,0x20,0x80,18,6,0
1985 .size __bn_sqr8x_mont,.-__bn_sqr8x_mont
1989 .asciz "Montgomery Multiplication for PPC, CRYPTOGAMS by <appro\@openssl.org>"
1992 $code =~ s/\`([^\`]*)\`/eval $1/gem;
1994 close STDOUT or die "error closing STDOUT: $!";