12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994 |
- #! /usr/bin/env perl
- # Copyright 2006-2020 The OpenSSL Project Authors. All Rights Reserved.
- #
- # Licensed under the Apache License 2.0 (the "License"). You may not use
- # this file except in compliance with the License. You can obtain a copy
- # in the file LICENSE in the source distribution or at
- # https://www.openssl.org/source/license.html
- # ====================================================================
- # Written by Andy Polyakov <appro@openssl.org> for the OpenSSL
- # project. The module is, however, dual licensed under OpenSSL and
- # CRYPTOGAMS licenses depending on where you obtain it. For further
- # details see http://www.openssl.org/~appro/cryptogams/.
- # ====================================================================
- # April 2006
- # "Teaser" Montgomery multiplication module for PowerPC. It's possible
- # to gain a bit more by modulo-scheduling outer loop, then dedicated
- # squaring procedure should give further 20% and code can be adapted
- # for 32-bit application running on 64-bit CPU. As for the latter.
- # It won't be able to achieve "native" 64-bit performance, because in
- # 32-bit application context every addc instruction will have to be
- # expanded as addc, twice right shift by 32 and finally adde, etc.
- # So far RSA *sign* performance improvement over pre-bn_mul_mont asm
- # for 64-bit application running on PPC970/G5 is:
- #
- # 512-bit +65%
- # 1024-bit +35%
- # 2048-bit +18%
- # 4096-bit +4%
- # September 2016
- #
- # Add multiplication procedure operating on lengths divisible by 4
- # and squaring procedure operating on lengths divisible by 8. Length
- # is expressed in number of limbs. RSA private key operations are
- # ~35-50% faster (more for longer keys) on contemporary high-end POWER
- # processors in 64-bit builds, [mysteriously enough] more in 32-bit
- # builds. On low-end 32-bit processors performance improvement turned
- # to be marginal...
- # $output is the last argument if it looks like a file (it has an extension)
- # $flavour is the first argument if it doesn't look like a file
- $output = $#ARGV >= 0 && $ARGV[$#ARGV] =~ m|\.\w+$| ? pop : undef;
- $flavour = $#ARGV >= 0 && $ARGV[0] !~ m|\.| ? shift : undef;
- if ($flavour =~ /32/) {
- $BITS= 32;
- $BNSZ= $BITS/8;
- $SIZE_T=4;
- $RZONE= 224;
- $LD= "lwz"; # load
- $LDU= "lwzu"; # load and update
- $LDX= "lwzx"; # load indexed
- $ST= "stw"; # store
- $STU= "stwu"; # store and update
- $STX= "stwx"; # store indexed
- $STUX= "stwux"; # store indexed and update
- $UMULL= "mullw"; # unsigned multiply low
- $UMULH= "mulhwu"; # unsigned multiply high
- $UCMP= "cmplw"; # unsigned compare
- $SHRI= "srwi"; # unsigned shift right by immediate
- $SHLI= "slwi"; # unsigned shift left by immediate
- $PUSH= $ST;
- $POP= $LD;
- } elsif ($flavour =~ /64/) {
- $BITS= 64;
- $BNSZ= $BITS/8;
- $SIZE_T=8;
- $RZONE= 288;
- # same as above, but 64-bit mnemonics...
- $LD= "ld"; # load
- $LDU= "ldu"; # load and update
- $LDX= "ldx"; # load indexed
- $ST= "std"; # store
- $STU= "stdu"; # store and update
- $STX= "stdx"; # store indexed
- $STUX= "stdux"; # store indexed and update
- $UMULL= "mulld"; # unsigned multiply low
- $UMULH= "mulhdu"; # unsigned multiply high
- $UCMP= "cmpld"; # unsigned compare
- $SHRI= "srdi"; # unsigned shift right by immediate
- $SHLI= "sldi"; # unsigned shift left by immediate
- $PUSH= $ST;
- $POP= $LD;
- } else { die "nonsense $flavour"; }
- $FRAME=8*$SIZE_T+$RZONE;
- $LOCALS=8*$SIZE_T;
- $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
- ( $xlate="${dir}ppc-xlate.pl" and -f $xlate ) or
- ( $xlate="${dir}../../perlasm/ppc-xlate.pl" and -f $xlate) or
- die "can't locate ppc-xlate.pl";
- open STDOUT,"| $^X $xlate $flavour \"$output\""
- or die "can't call $xlate: $!";
- $sp="r1";
- $toc="r2";
- $rp="r3";
- $ap="r4";
- $bp="r5";
- $np="r6";
- $n0="r7";
- $num="r8";
- {
- my $ovf=$rp;
- my $rp="r9"; # $rp is reassigned
- my $aj="r10";
- my $nj="r11";
- my $tj="r12";
- # non-volatile registers
- my $i="r20";
- my $j="r21";
- my $tp="r22";
- my $m0="r23";
- my $m1="r24";
- my $lo0="r25";
- my $hi0="r26";
- my $lo1="r27";
- my $hi1="r28";
- my $alo="r29";
- my $ahi="r30";
- my $nlo="r31";
- #
- my $nhi="r0";
- $code=<<___;
- .machine "any"
- .text
- .globl .bn_mul_mont_int
- .align 5
- .bn_mul_mont_int:
- mr $rp,r3 ; $rp is reassigned
- li r3,0
- ___
- $code.=<<___ if ($BNSZ==4);
- cmpwi $num,32 ; longer key performance is not better
- bgelr
- ___
- $code.=<<___;
- slwi $num,$num,`log($BNSZ)/log(2)`
- li $tj,-4096
- addi $ovf,$num,$FRAME
- subf $ovf,$ovf,$sp ; $sp-$ovf
- and $ovf,$ovf,$tj ; minimize TLB usage
- subf $ovf,$sp,$ovf ; $ovf-$sp
- mr $tj,$sp
- srwi $num,$num,`log($BNSZ)/log(2)`
- $STUX $sp,$sp,$ovf
- $PUSH r20,`-12*$SIZE_T`($tj)
- $PUSH r21,`-11*$SIZE_T`($tj)
- $PUSH r22,`-10*$SIZE_T`($tj)
- $PUSH r23,`-9*$SIZE_T`($tj)
- $PUSH r24,`-8*$SIZE_T`($tj)
- $PUSH r25,`-7*$SIZE_T`($tj)
- $PUSH r26,`-6*$SIZE_T`($tj)
- $PUSH r27,`-5*$SIZE_T`($tj)
- $PUSH r28,`-4*$SIZE_T`($tj)
- $PUSH r29,`-3*$SIZE_T`($tj)
- $PUSH r30,`-2*$SIZE_T`($tj)
- $PUSH r31,`-1*$SIZE_T`($tj)
- $LD $n0,0($n0) ; pull n0[0] value
- addi $num,$num,-2 ; adjust $num for counter register
- $LD $m0,0($bp) ; m0=bp[0]
- $LD $aj,0($ap) ; ap[0]
- addi $tp,$sp,$LOCALS
- $UMULL $lo0,$aj,$m0 ; ap[0]*bp[0]
- $UMULH $hi0,$aj,$m0
- $LD $aj,$BNSZ($ap) ; ap[1]
- $LD $nj,0($np) ; np[0]
- $UMULL $m1,$lo0,$n0 ; "tp[0]"*n0
- $UMULL $alo,$aj,$m0 ; ap[1]*bp[0]
- $UMULH $ahi,$aj,$m0
- $UMULL $lo1,$nj,$m1 ; np[0]*m1
- $UMULH $hi1,$nj,$m1
- $LD $nj,$BNSZ($np) ; np[1]
- addc $lo1,$lo1,$lo0
- addze $hi1,$hi1
- $UMULL $nlo,$nj,$m1 ; np[1]*m1
- $UMULH $nhi,$nj,$m1
- mtctr $num
- li $j,`2*$BNSZ`
- .align 4
- L1st:
- $LDX $aj,$ap,$j ; ap[j]
- addc $lo0,$alo,$hi0
- $LDX $nj,$np,$j ; np[j]
- addze $hi0,$ahi
- $UMULL $alo,$aj,$m0 ; ap[j]*bp[0]
- addc $lo1,$nlo,$hi1
- $UMULH $ahi,$aj,$m0
- addze $hi1,$nhi
- $UMULL $nlo,$nj,$m1 ; np[j]*m1
- addc $lo1,$lo1,$lo0 ; np[j]*m1+ap[j]*bp[0]
- $UMULH $nhi,$nj,$m1
- addze $hi1,$hi1
- $ST $lo1,0($tp) ; tp[j-1]
- addi $j,$j,$BNSZ ; j++
- addi $tp,$tp,$BNSZ ; tp++
- bdnz L1st
- ;L1st
- addc $lo0,$alo,$hi0
- addze $hi0,$ahi
- addc $lo1,$nlo,$hi1
- addze $hi1,$nhi
- addc $lo1,$lo1,$lo0 ; np[j]*m1+ap[j]*bp[0]
- addze $hi1,$hi1
- $ST $lo1,0($tp) ; tp[j-1]
- li $ovf,0
- addc $hi1,$hi1,$hi0
- addze $ovf,$ovf ; upmost overflow bit
- $ST $hi1,$BNSZ($tp)
- li $i,$BNSZ
- .align 4
- Louter:
- $LDX $m0,$bp,$i ; m0=bp[i]
- $LD $aj,0($ap) ; ap[0]
- addi $tp,$sp,$LOCALS
- $LD $tj,$LOCALS($sp); tp[0]
- $UMULL $lo0,$aj,$m0 ; ap[0]*bp[i]
- $UMULH $hi0,$aj,$m0
- $LD $aj,$BNSZ($ap) ; ap[1]
- $LD $nj,0($np) ; np[0]
- addc $lo0,$lo0,$tj ; ap[0]*bp[i]+tp[0]
- $UMULL $alo,$aj,$m0 ; ap[j]*bp[i]
- addze $hi0,$hi0
- $UMULL $m1,$lo0,$n0 ; tp[0]*n0
- $UMULH $ahi,$aj,$m0
- $UMULL $lo1,$nj,$m1 ; np[0]*m1
- $UMULH $hi1,$nj,$m1
- $LD $nj,$BNSZ($np) ; np[1]
- addc $lo1,$lo1,$lo0
- $UMULL $nlo,$nj,$m1 ; np[1]*m1
- addze $hi1,$hi1
- $UMULH $nhi,$nj,$m1
- mtctr $num
- li $j,`2*$BNSZ`
- .align 4
- Linner:
- $LDX $aj,$ap,$j ; ap[j]
- addc $lo0,$alo,$hi0
- $LD $tj,$BNSZ($tp) ; tp[j]
- addze $hi0,$ahi
- $LDX $nj,$np,$j ; np[j]
- addc $lo1,$nlo,$hi1
- $UMULL $alo,$aj,$m0 ; ap[j]*bp[i]
- addze $hi1,$nhi
- $UMULH $ahi,$aj,$m0
- addc $lo0,$lo0,$tj ; ap[j]*bp[i]+tp[j]
- $UMULL $nlo,$nj,$m1 ; np[j]*m1
- addze $hi0,$hi0
- $UMULH $nhi,$nj,$m1
- addc $lo1,$lo1,$lo0 ; np[j]*m1+ap[j]*bp[i]+tp[j]
- addi $j,$j,$BNSZ ; j++
- addze $hi1,$hi1
- $ST $lo1,0($tp) ; tp[j-1]
- addi $tp,$tp,$BNSZ ; tp++
- bdnz Linner
- ;Linner
- $LD $tj,$BNSZ($tp) ; tp[j]
- addc $lo0,$alo,$hi0
- addze $hi0,$ahi
- addc $lo0,$lo0,$tj ; ap[j]*bp[i]+tp[j]
- addze $hi0,$hi0
- addc $lo1,$nlo,$hi1
- addze $hi1,$nhi
- addc $lo1,$lo1,$lo0 ; np[j]*m1+ap[j]*bp[i]+tp[j]
- addze $hi1,$hi1
- $ST $lo1,0($tp) ; tp[j-1]
- addic $ovf,$ovf,-1 ; move upmost overflow to XER[CA]
- li $ovf,0
- adde $hi1,$hi1,$hi0
- addze $ovf,$ovf
- $ST $hi1,$BNSZ($tp)
- ;
- slwi $tj,$num,`log($BNSZ)/log(2)`
- $UCMP $i,$tj
- addi $i,$i,$BNSZ
- ble Louter
- addi $num,$num,2 ; restore $num
- subfc $j,$j,$j ; j=0 and "clear" XER[CA]
- addi $tp,$sp,$LOCALS
- mtctr $num
- .align 4
- Lsub: $LDX $tj,$tp,$j
- $LDX $nj,$np,$j
- subfe $aj,$nj,$tj ; tp[j]-np[j]
- $STX $aj,$rp,$j
- addi $j,$j,$BNSZ
- bdnz Lsub
- li $j,0
- mtctr $num
- subfe $ovf,$j,$ovf ; handle upmost overflow bit
- .align 4
- Lcopy: ; conditional copy
- $LDX $tj,$tp,$j
- $LDX $aj,$rp,$j
- and $tj,$tj,$ovf
- andc $aj,$aj,$ovf
- $STX $j,$tp,$j ; zap at once
- or $aj,$aj,$tj
- $STX $aj,$rp,$j
- addi $j,$j,$BNSZ
- bdnz Lcopy
- $POP $tj,0($sp)
- li r3,1
- $POP r20,`-12*$SIZE_T`($tj)
- $POP r21,`-11*$SIZE_T`($tj)
- $POP r22,`-10*$SIZE_T`($tj)
- $POP r23,`-9*$SIZE_T`($tj)
- $POP r24,`-8*$SIZE_T`($tj)
- $POP r25,`-7*$SIZE_T`($tj)
- $POP r26,`-6*$SIZE_T`($tj)
- $POP r27,`-5*$SIZE_T`($tj)
- $POP r28,`-4*$SIZE_T`($tj)
- $POP r29,`-3*$SIZE_T`($tj)
- $POP r30,`-2*$SIZE_T`($tj)
- $POP r31,`-1*$SIZE_T`($tj)
- mr $sp,$tj
- blr
- .long 0
- .byte 0,12,4,0,0x80,12,6,0
- .long 0
- .size .bn_mul_mont_int,.-.bn_mul_mont_int
- ___
- }
- if (1) {
- my ($a0,$a1,$a2,$a3,
- $t0,$t1,$t2,$t3,
- $m0,$m1,$m2,$m3,
- $acc0,$acc1,$acc2,$acc3,$acc4,
- $bi,$mi,$tp,$ap_end,$cnt) = map("r$_",(9..12,14..31));
- my ($carry,$zero) = ($rp,"r0");
- # sp----------->+-------------------------------+
- # | saved sp |
- # +-------------------------------+
- # . .
- # +8*size_t +-------------------------------+
- # | 4 "n0*t0" |
- # . .
- # . .
- # +12*size_t +-------------------------------+
- # | size_t tmp[num] |
- # . .
- # . .
- # . .
- # +-------------------------------+
- # | topmost carry |
- # . .
- # -18*size_t +-------------------------------+
- # | 18 saved gpr, r14-r31 |
- # . .
- # . .
- # +-------------------------------+
- $code.=<<___;
- .globl .bn_mul4x_mont_int
- .align 5
- .bn_mul4x_mont_int:
- andi. r0,$num,7
- bne .Lmul4x_do
- $UCMP $ap,$bp
- bne .Lmul4x_do
- b .Lsqr8x_do
- .Lmul4x_do:
- slwi $num,$num,`log($SIZE_T)/log(2)`
- mr $a0,$sp
- li $a1,-32*$SIZE_T
- sub $a1,$a1,$num
- $STUX $sp,$sp,$a1 # alloca
- $PUSH r14,-$SIZE_T*18($a0)
- $PUSH r15,-$SIZE_T*17($a0)
- $PUSH r16,-$SIZE_T*16($a0)
- $PUSH r17,-$SIZE_T*15($a0)
- $PUSH r18,-$SIZE_T*14($a0)
- $PUSH r19,-$SIZE_T*13($a0)
- $PUSH r20,-$SIZE_T*12($a0)
- $PUSH r21,-$SIZE_T*11($a0)
- $PUSH r22,-$SIZE_T*10($a0)
- $PUSH r23,-$SIZE_T*9($a0)
- $PUSH r24,-$SIZE_T*8($a0)
- $PUSH r25,-$SIZE_T*7($a0)
- $PUSH r26,-$SIZE_T*6($a0)
- $PUSH r27,-$SIZE_T*5($a0)
- $PUSH r28,-$SIZE_T*4($a0)
- $PUSH r29,-$SIZE_T*3($a0)
- $PUSH r30,-$SIZE_T*2($a0)
- $PUSH r31,-$SIZE_T*1($a0)
- subi $ap,$ap,$SIZE_T # bias by -1
- subi $np,$np,$SIZE_T # bias by -1
- subi $rp,$rp,$SIZE_T # bias by -1
- $LD $n0,0($n0) # *n0
- add $t0,$bp,$num
- add $ap_end,$ap,$num
- subi $t0,$t0,$SIZE_T*4 # &b[num-4]
- $LD $bi,$SIZE_T*0($bp) # b[0]
- li $acc0,0
- $LD $a0,$SIZE_T*1($ap) # a[0..3]
- li $acc1,0
- $LD $a1,$SIZE_T*2($ap)
- li $acc2,0
- $LD $a2,$SIZE_T*3($ap)
- li $acc3,0
- $LDU $a3,$SIZE_T*4($ap)
- $LD $m0,$SIZE_T*1($np) # n[0..3]
- $LD $m1,$SIZE_T*2($np)
- $LD $m2,$SIZE_T*3($np)
- $LDU $m3,$SIZE_T*4($np)
- $PUSH $rp,$SIZE_T*6($sp) # offload rp and &b[num-4]
- $PUSH $t0,$SIZE_T*7($sp)
- li $carry,0
- addic $tp,$sp,$SIZE_T*7 # &t[-1], clear carry bit
- li $cnt,0
- li $zero,0
- b .Loop_mul4x_1st_reduction
- .align 5
- .Loop_mul4x_1st_reduction:
- $UMULL $t0,$a0,$bi # lo(a[0..3]*b[0])
- addze $carry,$carry # modulo-scheduled
- $UMULL $t1,$a1,$bi
- addi $cnt,$cnt,$SIZE_T
- $UMULL $t2,$a2,$bi
- andi. $cnt,$cnt,$SIZE_T*4-1
- $UMULL $t3,$a3,$bi
- addc $acc0,$acc0,$t0
- $UMULH $t0,$a0,$bi # hi(a[0..3]*b[0])
- adde $acc1,$acc1,$t1
- $UMULH $t1,$a1,$bi
- adde $acc2,$acc2,$t2
- $UMULL $mi,$acc0,$n0 # t[0]*n0
- adde $acc3,$acc3,$t3
- $UMULH $t2,$a2,$bi
- addze $acc4,$zero
- $UMULH $t3,$a3,$bi
- $LDX $bi,$bp,$cnt # next b[i] (or b[0])
- addc $acc1,$acc1,$t0
- # (*) mul $t0,$m0,$mi # lo(n[0..3]*t[0]*n0)
- $STU $mi,$SIZE_T($tp) # put aside t[0]*n0 for tail processing
- adde $acc2,$acc2,$t1
- $UMULL $t1,$m1,$mi
- adde $acc3,$acc3,$t2
- $UMULL $t2,$m2,$mi
- adde $acc4,$acc4,$t3 # can't overflow
- $UMULL $t3,$m3,$mi
- # (*) addc $acc0,$acc0,$t0
- # (*) As for removal of first multiplication and addition
- # instructions. The outcome of first addition is
- # guaranteed to be zero, which leaves two computationally
- # significant outcomes: it either carries or not. Then
- # question is when does it carry? Is there alternative
- # way to deduce it? If you follow operations, you can
- # observe that condition for carry is quite simple:
- # $acc0 being non-zero. So that carry can be calculated
- # by adding -1 to $acc0. That's what next instruction does.
- addic $acc0,$acc0,-1 # (*), discarded
- $UMULH $t0,$m0,$mi # hi(n[0..3]*t[0]*n0)
- adde $acc0,$acc1,$t1
- $UMULH $t1,$m1,$mi
- adde $acc1,$acc2,$t2
- $UMULH $t2,$m2,$mi
- adde $acc2,$acc3,$t3
- $UMULH $t3,$m3,$mi
- adde $acc3,$acc4,$carry
- addze $carry,$zero
- addc $acc0,$acc0,$t0
- adde $acc1,$acc1,$t1
- adde $acc2,$acc2,$t2
- adde $acc3,$acc3,$t3
- #addze $carry,$carry
- bne .Loop_mul4x_1st_reduction
- $UCMP $ap_end,$ap
- beq .Lmul4x4_post_condition
- $LD $a0,$SIZE_T*1($ap) # a[4..7]
- $LD $a1,$SIZE_T*2($ap)
- $LD $a2,$SIZE_T*3($ap)
- $LDU $a3,$SIZE_T*4($ap)
- $LD $mi,$SIZE_T*8($sp) # a[0]*n0
- $LD $m0,$SIZE_T*1($np) # n[4..7]
- $LD $m1,$SIZE_T*2($np)
- $LD $m2,$SIZE_T*3($np)
- $LDU $m3,$SIZE_T*4($np)
- b .Loop_mul4x_1st_tail
- .align 5
- .Loop_mul4x_1st_tail:
- $UMULL $t0,$a0,$bi # lo(a[4..7]*b[i])
- addze $carry,$carry # modulo-scheduled
- $UMULL $t1,$a1,$bi
- addi $cnt,$cnt,$SIZE_T
- $UMULL $t2,$a2,$bi
- andi. $cnt,$cnt,$SIZE_T*4-1
- $UMULL $t3,$a3,$bi
- addc $acc0,$acc0,$t0
- $UMULH $t0,$a0,$bi # hi(a[4..7]*b[i])
- adde $acc1,$acc1,$t1
- $UMULH $t1,$a1,$bi
- adde $acc2,$acc2,$t2
- $UMULH $t2,$a2,$bi
- adde $acc3,$acc3,$t3
- $UMULH $t3,$a3,$bi
- addze $acc4,$zero
- $LDX $bi,$bp,$cnt # next b[i] (or b[0])
- addc $acc1,$acc1,$t0
- $UMULL $t0,$m0,$mi # lo(n[4..7]*a[0]*n0)
- adde $acc2,$acc2,$t1
- $UMULL $t1,$m1,$mi
- adde $acc3,$acc3,$t2
- $UMULL $t2,$m2,$mi
- adde $acc4,$acc4,$t3 # can't overflow
- $UMULL $t3,$m3,$mi
- addc $acc0,$acc0,$t0
- $UMULH $t0,$m0,$mi # hi(n[4..7]*a[0]*n0)
- adde $acc1,$acc1,$t1
- $UMULH $t1,$m1,$mi
- adde $acc2,$acc2,$t2
- $UMULH $t2,$m2,$mi
- adde $acc3,$acc3,$t3
- adde $acc4,$acc4,$carry
- $UMULH $t3,$m3,$mi
- addze $carry,$zero
- addi $mi,$sp,$SIZE_T*8
- $LDX $mi,$mi,$cnt # next t[0]*n0
- $STU $acc0,$SIZE_T($tp) # word of result
- addc $acc0,$acc1,$t0
- adde $acc1,$acc2,$t1
- adde $acc2,$acc3,$t2
- adde $acc3,$acc4,$t3
- #addze $carry,$carry
- bne .Loop_mul4x_1st_tail
- sub $t1,$ap_end,$num # rewinded $ap
- $UCMP $ap_end,$ap # done yet?
- beq .Lmul4x_proceed
- $LD $a0,$SIZE_T*1($ap)
- $LD $a1,$SIZE_T*2($ap)
- $LD $a2,$SIZE_T*3($ap)
- $LDU $a3,$SIZE_T*4($ap)
- $LD $m0,$SIZE_T*1($np)
- $LD $m1,$SIZE_T*2($np)
- $LD $m2,$SIZE_T*3($np)
- $LDU $m3,$SIZE_T*4($np)
- b .Loop_mul4x_1st_tail
- .align 5
- .Lmul4x_proceed:
- $LDU $bi,$SIZE_T*4($bp) # *++b
- addze $carry,$carry # topmost carry
- $LD $a0,$SIZE_T*1($t1)
- $LD $a1,$SIZE_T*2($t1)
- $LD $a2,$SIZE_T*3($t1)
- $LD $a3,$SIZE_T*4($t1)
- addi $ap,$t1,$SIZE_T*4
- sub $np,$np,$num # rewind np
- $ST $acc0,$SIZE_T*1($tp) # result
- $ST $acc1,$SIZE_T*2($tp)
- $ST $acc2,$SIZE_T*3($tp)
- $ST $acc3,$SIZE_T*4($tp)
- $ST $carry,$SIZE_T*5($tp) # save topmost carry
- $LD $acc0,$SIZE_T*12($sp) # t[0..3]
- $LD $acc1,$SIZE_T*13($sp)
- $LD $acc2,$SIZE_T*14($sp)
- $LD $acc3,$SIZE_T*15($sp)
- $LD $m0,$SIZE_T*1($np) # n[0..3]
- $LD $m1,$SIZE_T*2($np)
- $LD $m2,$SIZE_T*3($np)
- $LDU $m3,$SIZE_T*4($np)
- addic $tp,$sp,$SIZE_T*7 # &t[-1], clear carry bit
- li $carry,0
- b .Loop_mul4x_reduction
- .align 5
- .Loop_mul4x_reduction:
- $UMULL $t0,$a0,$bi # lo(a[0..3]*b[4])
- addze $carry,$carry # modulo-scheduled
- $UMULL $t1,$a1,$bi
- addi $cnt,$cnt,$SIZE_T
- $UMULL $t2,$a2,$bi
- andi. $cnt,$cnt,$SIZE_T*4-1
- $UMULL $t3,$a3,$bi
- addc $acc0,$acc0,$t0
- $UMULH $t0,$a0,$bi # hi(a[0..3]*b[4])
- adde $acc1,$acc1,$t1
- $UMULH $t1,$a1,$bi
- adde $acc2,$acc2,$t2
- $UMULL $mi,$acc0,$n0 # t[0]*n0
- adde $acc3,$acc3,$t3
- $UMULH $t2,$a2,$bi
- addze $acc4,$zero
- $UMULH $t3,$a3,$bi
- $LDX $bi,$bp,$cnt # next b[i]
- addc $acc1,$acc1,$t0
- # (*) mul $t0,$m0,$mi
- $STU $mi,$SIZE_T($tp) # put aside t[0]*n0 for tail processing
- adde $acc2,$acc2,$t1
- $UMULL $t1,$m1,$mi # lo(n[0..3]*t[0]*n0
- adde $acc3,$acc3,$t2
- $UMULL $t2,$m2,$mi
- adde $acc4,$acc4,$t3 # can't overflow
- $UMULL $t3,$m3,$mi
- # (*) addc $acc0,$acc0,$t0
- addic $acc0,$acc0,-1 # (*), discarded
- $UMULH $t0,$m0,$mi # hi(n[0..3]*t[0]*n0
- adde $acc0,$acc1,$t1
- $UMULH $t1,$m1,$mi
- adde $acc1,$acc2,$t2
- $UMULH $t2,$m2,$mi
- adde $acc2,$acc3,$t3
- $UMULH $t3,$m3,$mi
- adde $acc3,$acc4,$carry
- addze $carry,$zero
- addc $acc0,$acc0,$t0
- adde $acc1,$acc1,$t1
- adde $acc2,$acc2,$t2
- adde $acc3,$acc3,$t3
- #addze $carry,$carry
- bne .Loop_mul4x_reduction
- $LD $t0,$SIZE_T*5($tp) # t[4..7]
- addze $carry,$carry
- $LD $t1,$SIZE_T*6($tp)
- $LD $t2,$SIZE_T*7($tp)
- $LD $t3,$SIZE_T*8($tp)
- $LD $a0,$SIZE_T*1($ap) # a[4..7]
- $LD $a1,$SIZE_T*2($ap)
- $LD $a2,$SIZE_T*3($ap)
- $LDU $a3,$SIZE_T*4($ap)
- addc $acc0,$acc0,$t0
- adde $acc1,$acc1,$t1
- adde $acc2,$acc2,$t2
- adde $acc3,$acc3,$t3
- #addze $carry,$carry
- $LD $mi,$SIZE_T*8($sp) # t[0]*n0
- $LD $m0,$SIZE_T*1($np) # n[4..7]
- $LD $m1,$SIZE_T*2($np)
- $LD $m2,$SIZE_T*3($np)
- $LDU $m3,$SIZE_T*4($np)
- b .Loop_mul4x_tail
- .align 5
- .Loop_mul4x_tail:
- $UMULL $t0,$a0,$bi # lo(a[4..7]*b[4])
- addze $carry,$carry # modulo-scheduled
- $UMULL $t1,$a1,$bi
- addi $cnt,$cnt,$SIZE_T
- $UMULL $t2,$a2,$bi
- andi. $cnt,$cnt,$SIZE_T*4-1
- $UMULL $t3,$a3,$bi
- addc $acc0,$acc0,$t0
- $UMULH $t0,$a0,$bi # hi(a[4..7]*b[4])
- adde $acc1,$acc1,$t1
- $UMULH $t1,$a1,$bi
- adde $acc2,$acc2,$t2
- $UMULH $t2,$a2,$bi
- adde $acc3,$acc3,$t3
- $UMULH $t3,$a3,$bi
- addze $acc4,$zero
- $LDX $bi,$bp,$cnt # next b[i]
- addc $acc1,$acc1,$t0
- $UMULL $t0,$m0,$mi # lo(n[4..7]*t[0]*n0)
- adde $acc2,$acc2,$t1
- $UMULL $t1,$m1,$mi
- adde $acc3,$acc3,$t2
- $UMULL $t2,$m2,$mi
- adde $acc4,$acc4,$t3 # can't overflow
- $UMULL $t3,$m3,$mi
- addc $acc0,$acc0,$t0
- $UMULH $t0,$m0,$mi # hi(n[4..7]*t[0]*n0)
- adde $acc1,$acc1,$t1
- $UMULH $t1,$m1,$mi
- adde $acc2,$acc2,$t2
- $UMULH $t2,$m2,$mi
- adde $acc3,$acc3,$t3
- $UMULH $t3,$m3,$mi
- adde $acc4,$acc4,$carry
- addi $mi,$sp,$SIZE_T*8
- $LDX $mi,$mi,$cnt # next a[0]*n0
- addze $carry,$zero
- $STU $acc0,$SIZE_T($tp) # word of result
- addc $acc0,$acc1,$t0
- adde $acc1,$acc2,$t1
- adde $acc2,$acc3,$t2
- adde $acc3,$acc4,$t3
- #addze $carry,$carry
- bne .Loop_mul4x_tail
- $LD $t0,$SIZE_T*5($tp) # next t[i] or topmost carry
- sub $t1,$np,$num # rewinded np?
- addze $carry,$carry
- $UCMP $ap_end,$ap # done yet?
- beq .Loop_mul4x_break
- $LD $t1,$SIZE_T*6($tp)
- $LD $t2,$SIZE_T*7($tp)
- $LD $t3,$SIZE_T*8($tp)
- $LD $a0,$SIZE_T*1($ap)
- $LD $a1,$SIZE_T*2($ap)
- $LD $a2,$SIZE_T*3($ap)
- $LDU $a3,$SIZE_T*4($ap)
- addc $acc0,$acc0,$t0
- adde $acc1,$acc1,$t1
- adde $acc2,$acc2,$t2
- adde $acc3,$acc3,$t3
- #addze $carry,$carry
- $LD $m0,$SIZE_T*1($np) # n[4..7]
- $LD $m1,$SIZE_T*2($np)
- $LD $m2,$SIZE_T*3($np)
- $LDU $m3,$SIZE_T*4($np)
- b .Loop_mul4x_tail
- .align 5
- .Loop_mul4x_break:
- $POP $t2,$SIZE_T*6($sp) # pull rp and &b[num-4]
- $POP $t3,$SIZE_T*7($sp)
- addc $a0,$acc0,$t0 # accumulate topmost carry
- $LD $acc0,$SIZE_T*12($sp) # t[0..3]
- addze $a1,$acc1
- $LD $acc1,$SIZE_T*13($sp)
- addze $a2,$acc2
- $LD $acc2,$SIZE_T*14($sp)
- addze $a3,$acc3
- $LD $acc3,$SIZE_T*15($sp)
- addze $carry,$carry # topmost carry
- $ST $a0,$SIZE_T*1($tp) # result
- sub $ap,$ap_end,$num # rewind ap
- $ST $a1,$SIZE_T*2($tp)
- $ST $a2,$SIZE_T*3($tp)
- $ST $a3,$SIZE_T*4($tp)
- $ST $carry,$SIZE_T*5($tp) # store topmost carry
- $LD $m0,$SIZE_T*1($t1) # n[0..3]
- $LD $m1,$SIZE_T*2($t1)
- $LD $m2,$SIZE_T*3($t1)
- $LD $m3,$SIZE_T*4($t1)
- addi $np,$t1,$SIZE_T*4
- $UCMP $bp,$t3 # done yet?
- beq .Lmul4x_post
- $LDU $bi,$SIZE_T*4($bp)
- $LD $a0,$SIZE_T*1($ap) # a[0..3]
- $LD $a1,$SIZE_T*2($ap)
- $LD $a2,$SIZE_T*3($ap)
- $LDU $a3,$SIZE_T*4($ap)
- li $carry,0
- addic $tp,$sp,$SIZE_T*7 # &t[-1], clear carry bit
- b .Loop_mul4x_reduction
- .align 5
- .Lmul4x_post:
- # Final step. We see if result is larger than modulus, and
- # if it is, subtract the modulus. But comparison implies
- # subtraction. So we subtract modulus, see if it borrowed,
- # and conditionally copy original value.
- srwi $cnt,$num,`log($SIZE_T)/log(2)+2`
- mr $bp,$t2 # &rp[-1]
- subi $cnt,$cnt,1
- mr $ap_end,$t2 # &rp[-1] copy
- subfc $t0,$m0,$acc0
- addi $tp,$sp,$SIZE_T*15
- subfe $t1,$m1,$acc1
- mtctr $cnt
- .Lmul4x_sub:
- $LD $m0,$SIZE_T*1($np)
- $LD $acc0,$SIZE_T*1($tp)
- subfe $t2,$m2,$acc2
- $LD $m1,$SIZE_T*2($np)
- $LD $acc1,$SIZE_T*2($tp)
- subfe $t3,$m3,$acc3
- $LD $m2,$SIZE_T*3($np)
- $LD $acc2,$SIZE_T*3($tp)
- $LDU $m3,$SIZE_T*4($np)
- $LDU $acc3,$SIZE_T*4($tp)
- $ST $t0,$SIZE_T*1($bp)
- $ST $t1,$SIZE_T*2($bp)
- subfe $t0,$m0,$acc0
- $ST $t2,$SIZE_T*3($bp)
- $STU $t3,$SIZE_T*4($bp)
- subfe $t1,$m1,$acc1
- bdnz .Lmul4x_sub
- $LD $a0,$SIZE_T*1($ap_end)
- $ST $t0,$SIZE_T*1($bp)
- $LD $t0,$SIZE_T*12($sp)
- subfe $t2,$m2,$acc2
- $LD $a1,$SIZE_T*2($ap_end)
- $ST $t1,$SIZE_T*2($bp)
- $LD $t1,$SIZE_T*13($sp)
- subfe $t3,$m3,$acc3
- subfe $carry,$zero,$carry # did it borrow?
- addi $tp,$sp,$SIZE_T*12
- $LD $a2,$SIZE_T*3($ap_end)
- $ST $t2,$SIZE_T*3($bp)
- $LD $t2,$SIZE_T*14($sp)
- $LD $a3,$SIZE_T*4($ap_end)
- $ST $t3,$SIZE_T*4($bp)
- $LD $t3,$SIZE_T*15($sp)
- mtctr $cnt
- .Lmul4x_cond_copy:
- and $t0,$t0,$carry
- andc $a0,$a0,$carry
- $ST $zero,$SIZE_T*0($tp) # wipe stack clean
- and $t1,$t1,$carry
- andc $a1,$a1,$carry
- $ST $zero,$SIZE_T*1($tp)
- and $t2,$t2,$carry
- andc $a2,$a2,$carry
- $ST $zero,$SIZE_T*2($tp)
- and $t3,$t3,$carry
- andc $a3,$a3,$carry
- $ST $zero,$SIZE_T*3($tp)
- or $acc0,$t0,$a0
- $LD $a0,$SIZE_T*5($ap_end)
- $LD $t0,$SIZE_T*4($tp)
- or $acc1,$t1,$a1
- $LD $a1,$SIZE_T*6($ap_end)
- $LD $t1,$SIZE_T*5($tp)
- or $acc2,$t2,$a2
- $LD $a2,$SIZE_T*7($ap_end)
- $LD $t2,$SIZE_T*6($tp)
- or $acc3,$t3,$a3
- $LD $a3,$SIZE_T*8($ap_end)
- $LD $t3,$SIZE_T*7($tp)
- addi $tp,$tp,$SIZE_T*4
- $ST $acc0,$SIZE_T*1($ap_end)
- $ST $acc1,$SIZE_T*2($ap_end)
- $ST $acc2,$SIZE_T*3($ap_end)
- $STU $acc3,$SIZE_T*4($ap_end)
- bdnz .Lmul4x_cond_copy
- $POP $bp,0($sp) # pull saved sp
- and $t0,$t0,$carry
- andc $a0,$a0,$carry
- $ST $zero,$SIZE_T*0($tp)
- and $t1,$t1,$carry
- andc $a1,$a1,$carry
- $ST $zero,$SIZE_T*1($tp)
- and $t2,$t2,$carry
- andc $a2,$a2,$carry
- $ST $zero,$SIZE_T*2($tp)
- and $t3,$t3,$carry
- andc $a3,$a3,$carry
- $ST $zero,$SIZE_T*3($tp)
- or $acc0,$t0,$a0
- or $acc1,$t1,$a1
- $ST $zero,$SIZE_T*4($tp)
- or $acc2,$t2,$a2
- or $acc3,$t3,$a3
- $ST $acc0,$SIZE_T*1($ap_end)
- $ST $acc1,$SIZE_T*2($ap_end)
- $ST $acc2,$SIZE_T*3($ap_end)
- $ST $acc3,$SIZE_T*4($ap_end)
- b .Lmul4x_done
- .align 4
- .Lmul4x4_post_condition:
- $POP $ap,$SIZE_T*6($sp) # pull &rp[-1]
- $POP $bp,0($sp) # pull saved sp
- addze $carry,$carry # modulo-scheduled
- # $acc0-3,$carry hold result, $m0-3 hold modulus
- subfc $a0,$m0,$acc0
- subfe $a1,$m1,$acc1
- subfe $a2,$m2,$acc2
- subfe $a3,$m3,$acc3
- subfe $carry,$zero,$carry # did it borrow?
- and $m0,$m0,$carry
- and $m1,$m1,$carry
- addc $a0,$a0,$m0
- and $m2,$m2,$carry
- adde $a1,$a1,$m1
- and $m3,$m3,$carry
- adde $a2,$a2,$m2
- adde $a3,$a3,$m3
- $ST $a0,$SIZE_T*1($ap) # write result
- $ST $a1,$SIZE_T*2($ap)
- $ST $a2,$SIZE_T*3($ap)
- $ST $a3,$SIZE_T*4($ap)
- .Lmul4x_done:
- $ST $zero,$SIZE_T*8($sp) # wipe stack clean
- $ST $zero,$SIZE_T*9($sp)
- $ST $zero,$SIZE_T*10($sp)
- $ST $zero,$SIZE_T*11($sp)
- li r3,1 # signal "done"
- $POP r14,-$SIZE_T*18($bp)
- $POP r15,-$SIZE_T*17($bp)
- $POP r16,-$SIZE_T*16($bp)
- $POP r17,-$SIZE_T*15($bp)
- $POP r18,-$SIZE_T*14($bp)
- $POP r19,-$SIZE_T*13($bp)
- $POP r20,-$SIZE_T*12($bp)
- $POP r21,-$SIZE_T*11($bp)
- $POP r22,-$SIZE_T*10($bp)
- $POP r23,-$SIZE_T*9($bp)
- $POP r24,-$SIZE_T*8($bp)
- $POP r25,-$SIZE_T*7($bp)
- $POP r26,-$SIZE_T*6($bp)
- $POP r27,-$SIZE_T*5($bp)
- $POP r28,-$SIZE_T*4($bp)
- $POP r29,-$SIZE_T*3($bp)
- $POP r30,-$SIZE_T*2($bp)
- $POP r31,-$SIZE_T*1($bp)
- mr $sp,$bp
- blr
- .long 0
- .byte 0,12,4,0x20,0x80,18,6,0
- .long 0
- .size .bn_mul4x_mont_int,.-.bn_mul4x_mont_int
- ___
- }
- if (1) {
- ########################################################################
- # Following is PPC adaptation of sqrx8x_mont from x86_64-mont5 module.
- my ($a0,$a1,$a2,$a3,$a4,$a5,$a6,$a7)=map("r$_",(9..12,14..17));
- my ($t0,$t1,$t2,$t3)=map("r$_",(18..21));
- my ($acc0,$acc1,$acc2,$acc3,$acc4,$acc5,$acc6,$acc7)=map("r$_",(22..29));
- my ($cnt,$carry,$zero)=("r30","r31","r0");
- my ($tp,$ap_end,$na0)=($bp,$np,$carry);
- # sp----------->+-------------------------------+
- # | saved sp |
- # +-------------------------------+
- # . .
- # +12*size_t +-------------------------------+
- # | size_t tmp[2*num] |
- # . .
- # . .
- # . .
- # +-------------------------------+
- # . .
- # -18*size_t +-------------------------------+
- # | 18 saved gpr, r14-r31 |
- # . .
- # . .
- # +-------------------------------+
- $code.=<<___;
- .align 5
- __bn_sqr8x_mont:
- .Lsqr8x_do:
- mr $a0,$sp
- slwi $a1,$num,`log($SIZE_T)/log(2)+1`
- li $a2,-32*$SIZE_T
- sub $a1,$a2,$a1
- slwi $num,$num,`log($SIZE_T)/log(2)`
- $STUX $sp,$sp,$a1 # alloca
- $PUSH r14,-$SIZE_T*18($a0)
- $PUSH r15,-$SIZE_T*17($a0)
- $PUSH r16,-$SIZE_T*16($a0)
- $PUSH r17,-$SIZE_T*15($a0)
- $PUSH r18,-$SIZE_T*14($a0)
- $PUSH r19,-$SIZE_T*13($a0)
- $PUSH r20,-$SIZE_T*12($a0)
- $PUSH r21,-$SIZE_T*11($a0)
- $PUSH r22,-$SIZE_T*10($a0)
- $PUSH r23,-$SIZE_T*9($a0)
- $PUSH r24,-$SIZE_T*8($a0)
- $PUSH r25,-$SIZE_T*7($a0)
- $PUSH r26,-$SIZE_T*6($a0)
- $PUSH r27,-$SIZE_T*5($a0)
- $PUSH r28,-$SIZE_T*4($a0)
- $PUSH r29,-$SIZE_T*3($a0)
- $PUSH r30,-$SIZE_T*2($a0)
- $PUSH r31,-$SIZE_T*1($a0)
- subi $ap,$ap,$SIZE_T # bias by -1
- subi $t0,$np,$SIZE_T # bias by -1
- subi $rp,$rp,$SIZE_T # bias by -1
- $LD $n0,0($n0) # *n0
- li $zero,0
- add $ap_end,$ap,$num
- $LD $a0,$SIZE_T*1($ap)
- #li $acc0,0
- $LD $a1,$SIZE_T*2($ap)
- li $acc1,0
- $LD $a2,$SIZE_T*3($ap)
- li $acc2,0
- $LD $a3,$SIZE_T*4($ap)
- li $acc3,0
- $LD $a4,$SIZE_T*5($ap)
- li $acc4,0
- $LD $a5,$SIZE_T*6($ap)
- li $acc5,0
- $LD $a6,$SIZE_T*7($ap)
- li $acc6,0
- $LDU $a7,$SIZE_T*8($ap)
- li $acc7,0
- addi $tp,$sp,$SIZE_T*11 # &tp[-1]
- subic. $cnt,$num,$SIZE_T*8
- b .Lsqr8x_zero_start
- .align 5
- .Lsqr8x_zero:
- subic. $cnt,$cnt,$SIZE_T*8
- $ST $zero,$SIZE_T*1($tp)
- $ST $zero,$SIZE_T*2($tp)
- $ST $zero,$SIZE_T*3($tp)
- $ST $zero,$SIZE_T*4($tp)
- $ST $zero,$SIZE_T*5($tp)
- $ST $zero,$SIZE_T*6($tp)
- $ST $zero,$SIZE_T*7($tp)
- $ST $zero,$SIZE_T*8($tp)
- .Lsqr8x_zero_start:
- $ST $zero,$SIZE_T*9($tp)
- $ST $zero,$SIZE_T*10($tp)
- $ST $zero,$SIZE_T*11($tp)
- $ST $zero,$SIZE_T*12($tp)
- $ST $zero,$SIZE_T*13($tp)
- $ST $zero,$SIZE_T*14($tp)
- $ST $zero,$SIZE_T*15($tp)
- $STU $zero,$SIZE_T*16($tp)
- bne .Lsqr8x_zero
- $PUSH $rp,$SIZE_T*6($sp) # offload &rp[-1]
- $PUSH $t0,$SIZE_T*7($sp) # offload &np[-1]
- $PUSH $n0,$SIZE_T*8($sp) # offload n0
- $PUSH $tp,$SIZE_T*9($sp) # &tp[2*num-1]
- $PUSH $zero,$SIZE_T*10($sp) # initial top-most carry
- addi $tp,$sp,$SIZE_T*11 # &tp[-1]
- # Multiply everything but a[i]*a[i]
- .align 5
- .Lsqr8x_outer_loop:
- # a[1]a[0] (i)
- # a[2]a[0]
- # a[3]a[0]
- # a[4]a[0]
- # a[5]a[0]
- # a[6]a[0]
- # a[7]a[0]
- # a[2]a[1] (ii)
- # a[3]a[1]
- # a[4]a[1]
- # a[5]a[1]
- # a[6]a[1]
- # a[7]a[1]
- # a[3]a[2] (iii)
- # a[4]a[2]
- # a[5]a[2]
- # a[6]a[2]
- # a[7]a[2]
- # a[4]a[3] (iv)
- # a[5]a[3]
- # a[6]a[3]
- # a[7]a[3]
- # a[5]a[4] (v)
- # a[6]a[4]
- # a[7]a[4]
- # a[6]a[5] (vi)
- # a[7]a[5]
- # a[7]a[6] (vii)
- $UMULL $t0,$a1,$a0 # lo(a[1..7]*a[0]) (i)
- $UMULL $t1,$a2,$a0
- $UMULL $t2,$a3,$a0
- $UMULL $t3,$a4,$a0
- addc $acc1,$acc1,$t0 # t[1]+lo(a[1]*a[0])
- $UMULL $t0,$a5,$a0
- adde $acc2,$acc2,$t1
- $UMULL $t1,$a6,$a0
- adde $acc3,$acc3,$t2
- $UMULL $t2,$a7,$a0
- adde $acc4,$acc4,$t3
- $UMULH $t3,$a1,$a0 # hi(a[1..7]*a[0])
- adde $acc5,$acc5,$t0
- $UMULH $t0,$a2,$a0
- adde $acc6,$acc6,$t1
- $UMULH $t1,$a3,$a0
- adde $acc7,$acc7,$t2
- $UMULH $t2,$a4,$a0
- $ST $acc0,$SIZE_T*1($tp) # t[0]
- addze $acc0,$zero # t[8]
- $ST $acc1,$SIZE_T*2($tp) # t[1]
- addc $acc2,$acc2,$t3 # t[2]+lo(a[1]*a[0])
- $UMULH $t3,$a5,$a0
- adde $acc3,$acc3,$t0
- $UMULH $t0,$a6,$a0
- adde $acc4,$acc4,$t1
- $UMULH $t1,$a7,$a0
- adde $acc5,$acc5,$t2
- $UMULL $t2,$a2,$a1 # lo(a[2..7]*a[1]) (ii)
- adde $acc6,$acc6,$t3
- $UMULL $t3,$a3,$a1
- adde $acc7,$acc7,$t0
- $UMULL $t0,$a4,$a1
- adde $acc0,$acc0,$t1
- $UMULL $t1,$a5,$a1
- addc $acc3,$acc3,$t2
- $UMULL $t2,$a6,$a1
- adde $acc4,$acc4,$t3
- $UMULL $t3,$a7,$a1
- adde $acc5,$acc5,$t0
- $UMULH $t0,$a2,$a1 # hi(a[2..7]*a[1])
- adde $acc6,$acc6,$t1
- $UMULH $t1,$a3,$a1
- adde $acc7,$acc7,$t2
- $UMULH $t2,$a4,$a1
- adde $acc0,$acc0,$t3
- $UMULH $t3,$a5,$a1
- $ST $acc2,$SIZE_T*3($tp) # t[2]
- addze $acc1,$zero # t[9]
- $ST $acc3,$SIZE_T*4($tp) # t[3]
- addc $acc4,$acc4,$t0
- $UMULH $t0,$a6,$a1
- adde $acc5,$acc5,$t1
- $UMULH $t1,$a7,$a1
- adde $acc6,$acc6,$t2
- $UMULL $t2,$a3,$a2 # lo(a[3..7]*a[2]) (iii)
- adde $acc7,$acc7,$t3
- $UMULL $t3,$a4,$a2
- adde $acc0,$acc0,$t0
- $UMULL $t0,$a5,$a2
- adde $acc1,$acc1,$t1
- $UMULL $t1,$a6,$a2
- addc $acc5,$acc5,$t2
- $UMULL $t2,$a7,$a2
- adde $acc6,$acc6,$t3
- $UMULH $t3,$a3,$a2 # hi(a[3..7]*a[2])
- adde $acc7,$acc7,$t0
- $UMULH $t0,$a4,$a2
- adde $acc0,$acc0,$t1
- $UMULH $t1,$a5,$a2
- adde $acc1,$acc1,$t2
- $UMULH $t2,$a6,$a2
- $ST $acc4,$SIZE_T*5($tp) # t[4]
- addze $acc2,$zero # t[10]
- $ST $acc5,$SIZE_T*6($tp) # t[5]
- addc $acc6,$acc6,$t3
- $UMULH $t3,$a7,$a2
- adde $acc7,$acc7,$t0
- $UMULL $t0,$a4,$a3 # lo(a[4..7]*a[3]) (iv)
- adde $acc0,$acc0,$t1
- $UMULL $t1,$a5,$a3
- adde $acc1,$acc1,$t2
- $UMULL $t2,$a6,$a3
- adde $acc2,$acc2,$t3
- $UMULL $t3,$a7,$a3
- addc $acc7,$acc7,$t0
- $UMULH $t0,$a4,$a3 # hi(a[4..7]*a[3])
- adde $acc0,$acc0,$t1
- $UMULH $t1,$a5,$a3
- adde $acc1,$acc1,$t2
- $UMULH $t2,$a6,$a3
- adde $acc2,$acc2,$t3
- $UMULH $t3,$a7,$a3
- $ST $acc6,$SIZE_T*7($tp) # t[6]
- addze $acc3,$zero # t[11]
- $STU $acc7,$SIZE_T*8($tp) # t[7]
- addc $acc0,$acc0,$t0
- $UMULL $t0,$a5,$a4 # lo(a[5..7]*a[4]) (v)
- adde $acc1,$acc1,$t1
- $UMULL $t1,$a6,$a4
- adde $acc2,$acc2,$t2
- $UMULL $t2,$a7,$a4
- adde $acc3,$acc3,$t3
- $UMULH $t3,$a5,$a4 # hi(a[5..7]*a[4])
- addc $acc1,$acc1,$t0
- $UMULH $t0,$a6,$a4
- adde $acc2,$acc2,$t1
- $UMULH $t1,$a7,$a4
- adde $acc3,$acc3,$t2
- $UMULL $t2,$a6,$a5 # lo(a[6..7]*a[5]) (vi)
- addze $acc4,$zero # t[12]
- addc $acc2,$acc2,$t3
- $UMULL $t3,$a7,$a5
- adde $acc3,$acc3,$t0
- $UMULH $t0,$a6,$a5 # hi(a[6..7]*a[5])
- adde $acc4,$acc4,$t1
- $UMULH $t1,$a7,$a5
- addc $acc3,$acc3,$t2
- $UMULL $t2,$a7,$a6 # lo(a[7]*a[6]) (vii)
- adde $acc4,$acc4,$t3
- $UMULH $t3,$a7,$a6 # hi(a[7]*a[6])
- addze $acc5,$zero # t[13]
- addc $acc4,$acc4,$t0
- $UCMP $ap_end,$ap # done yet?
- adde $acc5,$acc5,$t1
- addc $acc5,$acc5,$t2
- sub $t0,$ap_end,$num # rewinded ap
- addze $acc6,$zero # t[14]
- add $acc6,$acc6,$t3
- beq .Lsqr8x_outer_break
- mr $n0,$a0
- $LD $a0,$SIZE_T*1($tp)
- $LD $a1,$SIZE_T*2($tp)
- $LD $a2,$SIZE_T*3($tp)
- $LD $a3,$SIZE_T*4($tp)
- $LD $a4,$SIZE_T*5($tp)
- $LD $a5,$SIZE_T*6($tp)
- $LD $a6,$SIZE_T*7($tp)
- $LD $a7,$SIZE_T*8($tp)
- addc $acc0,$acc0,$a0
- $LD $a0,$SIZE_T*1($ap)
- adde $acc1,$acc1,$a1
- $LD $a1,$SIZE_T*2($ap)
- adde $acc2,$acc2,$a2
- $LD $a2,$SIZE_T*3($ap)
- adde $acc3,$acc3,$a3
- $LD $a3,$SIZE_T*4($ap)
- adde $acc4,$acc4,$a4
- $LD $a4,$SIZE_T*5($ap)
- adde $acc5,$acc5,$a5
- $LD $a5,$SIZE_T*6($ap)
- adde $acc6,$acc6,$a6
- $LD $a6,$SIZE_T*7($ap)
- subi $rp,$ap,$SIZE_T*7
- addze $acc7,$a7
- $LDU $a7,$SIZE_T*8($ap)
- #addze $carry,$zero # moved below
- li $cnt,0
- b .Lsqr8x_mul
- # a[8]a[0]
- # a[9]a[0]
- # a[a]a[0]
- # a[b]a[0]
- # a[c]a[0]
- # a[d]a[0]
- # a[e]a[0]
- # a[f]a[0]
- # a[8]a[1]
- # a[f]a[1]........................
- # a[8]a[2]
- # a[f]a[2]........................
- # a[8]a[3]
- # a[f]a[3]........................
- # a[8]a[4]
- # a[f]a[4]........................
- # a[8]a[5]
- # a[f]a[5]........................
- # a[8]a[6]
- # a[f]a[6]........................
- # a[8]a[7]
- # a[f]a[7]........................
- .align 5
- .Lsqr8x_mul:
- $UMULL $t0,$a0,$n0
- addze $carry,$zero # carry bit, modulo-scheduled
- $UMULL $t1,$a1,$n0
- addi $cnt,$cnt,$SIZE_T
- $UMULL $t2,$a2,$n0
- andi. $cnt,$cnt,$SIZE_T*8-1
- $UMULL $t3,$a3,$n0
- addc $acc0,$acc0,$t0
- $UMULL $t0,$a4,$n0
- adde $acc1,$acc1,$t1
- $UMULL $t1,$a5,$n0
- adde $acc2,$acc2,$t2
- $UMULL $t2,$a6,$n0
- adde $acc3,$acc3,$t3
- $UMULL $t3,$a7,$n0
- adde $acc4,$acc4,$t0
- $UMULH $t0,$a0,$n0
- adde $acc5,$acc5,$t1
- $UMULH $t1,$a1,$n0
- adde $acc6,$acc6,$t2
- $UMULH $t2,$a2,$n0
- adde $acc7,$acc7,$t3
- $UMULH $t3,$a3,$n0
- addze $carry,$carry
- $STU $acc0,$SIZE_T($tp)
- addc $acc0,$acc1,$t0
- $UMULH $t0,$a4,$n0
- adde $acc1,$acc2,$t1
- $UMULH $t1,$a5,$n0
- adde $acc2,$acc3,$t2
- $UMULH $t2,$a6,$n0
- adde $acc3,$acc4,$t3
- $UMULH $t3,$a7,$n0
- $LDX $n0,$rp,$cnt
- adde $acc4,$acc5,$t0
- adde $acc5,$acc6,$t1
- adde $acc6,$acc7,$t2
- adde $acc7,$carry,$t3
- #addze $carry,$zero # moved above
- bne .Lsqr8x_mul
- # note that carry flag is guaranteed
- # to be zero at this point
- $UCMP $ap,$ap_end # done yet?
- beq .Lsqr8x_break
- $LD $a0,$SIZE_T*1($tp)
- $LD $a1,$SIZE_T*2($tp)
- $LD $a2,$SIZE_T*3($tp)
- $LD $a3,$SIZE_T*4($tp)
- $LD $a4,$SIZE_T*5($tp)
- $LD $a5,$SIZE_T*6($tp)
- $LD $a6,$SIZE_T*7($tp)
- $LD $a7,$SIZE_T*8($tp)
- addc $acc0,$acc0,$a0
- $LD $a0,$SIZE_T*1($ap)
- adde $acc1,$acc1,$a1
- $LD $a1,$SIZE_T*2($ap)
- adde $acc2,$acc2,$a2
- $LD $a2,$SIZE_T*3($ap)
- adde $acc3,$acc3,$a3
- $LD $a3,$SIZE_T*4($ap)
- adde $acc4,$acc4,$a4
- $LD $a4,$SIZE_T*5($ap)
- adde $acc5,$acc5,$a5
- $LD $a5,$SIZE_T*6($ap)
- adde $acc6,$acc6,$a6
- $LD $a6,$SIZE_T*7($ap)
- adde $acc7,$acc7,$a7
- $LDU $a7,$SIZE_T*8($ap)
- #addze $carry,$zero # moved above
- b .Lsqr8x_mul
- .align 5
- .Lsqr8x_break:
- $LD $a0,$SIZE_T*8($rp)
- addi $ap,$rp,$SIZE_T*15
- $LD $a1,$SIZE_T*9($rp)
- sub. $t0,$ap_end,$ap # is it last iteration?
- $LD $a2,$SIZE_T*10($rp)
- sub $t1,$tp,$t0
- $LD $a3,$SIZE_T*11($rp)
- $LD $a4,$SIZE_T*12($rp)
- $LD $a5,$SIZE_T*13($rp)
- $LD $a6,$SIZE_T*14($rp)
- $LD $a7,$SIZE_T*15($rp)
- beq .Lsqr8x_outer_loop
- $ST $acc0,$SIZE_T*1($tp)
- $LD $acc0,$SIZE_T*1($t1)
- $ST $acc1,$SIZE_T*2($tp)
- $LD $acc1,$SIZE_T*2($t1)
- $ST $acc2,$SIZE_T*3($tp)
- $LD $acc2,$SIZE_T*3($t1)
- $ST $acc3,$SIZE_T*4($tp)
- $LD $acc3,$SIZE_T*4($t1)
- $ST $acc4,$SIZE_T*5($tp)
- $LD $acc4,$SIZE_T*5($t1)
- $ST $acc5,$SIZE_T*6($tp)
- $LD $acc5,$SIZE_T*6($t1)
- $ST $acc6,$SIZE_T*7($tp)
- $LD $acc6,$SIZE_T*7($t1)
- $ST $acc7,$SIZE_T*8($tp)
- $LD $acc7,$SIZE_T*8($t1)
- mr $tp,$t1
- b .Lsqr8x_outer_loop
- .align 5
- .Lsqr8x_outer_break:
- ####################################################################
- # Now multiply above result by 2 and add a[n-1]*a[n-1]|...|a[0]*a[0]
- $LD $a1,$SIZE_T*1($t0) # recall that $t0 is &a[-1]
- $LD $a3,$SIZE_T*2($t0)
- $LD $a5,$SIZE_T*3($t0)
- $LD $a7,$SIZE_T*4($t0)
- addi $ap,$t0,$SIZE_T*4
- # "tp[x]" comments are for num==8 case
- $LD $t1,$SIZE_T*13($sp) # =tp[1], t[0] is not interesting
- $LD $t2,$SIZE_T*14($sp)
- $LD $t3,$SIZE_T*15($sp)
- $LD $t0,$SIZE_T*16($sp)
- $ST $acc0,$SIZE_T*1($tp) # tp[8]=
- srwi $cnt,$num,`log($SIZE_T)/log(2)+2`
- $ST $acc1,$SIZE_T*2($tp)
- subi $cnt,$cnt,1
- $ST $acc2,$SIZE_T*3($tp)
- $ST $acc3,$SIZE_T*4($tp)
- $ST $acc4,$SIZE_T*5($tp)
- $ST $acc5,$SIZE_T*6($tp)
- $ST $acc6,$SIZE_T*7($tp)
- #$ST $acc7,$SIZE_T*8($tp) # tp[15] is not interesting
- addi $tp,$sp,$SIZE_T*11 # &tp[-1]
- $UMULL $acc0,$a1,$a1
- $UMULH $a1,$a1,$a1
- add $acc1,$t1,$t1 # <<1
- $SHRI $t1,$t1,$BITS-1
- $UMULL $a2,$a3,$a3
- $UMULH $a3,$a3,$a3
- addc $acc1,$acc1,$a1
- add $acc2,$t2,$t2
- $SHRI $t2,$t2,$BITS-1
- add $acc3,$t3,$t3
- $SHRI $t3,$t3,$BITS-1
- or $acc2,$acc2,$t1
- mtctr $cnt
- .Lsqr4x_shift_n_add:
- $UMULL $a4,$a5,$a5
- $UMULH $a5,$a5,$a5
- $LD $t1,$SIZE_T*6($tp) # =tp[5]
- $LD $a1,$SIZE_T*1($ap)
- adde $acc2,$acc2,$a2
- add $acc4,$t0,$t0
- $SHRI $t0,$t0,$BITS-1
- or $acc3,$acc3,$t2
- $LD $t2,$SIZE_T*7($tp) # =tp[6]
- adde $acc3,$acc3,$a3
- $LD $a3,$SIZE_T*2($ap)
- add $acc5,$t1,$t1
- $SHRI $t1,$t1,$BITS-1
- or $acc4,$acc4,$t3
- $LD $t3,$SIZE_T*8($tp) # =tp[7]
- $UMULL $a6,$a7,$a7
- $UMULH $a7,$a7,$a7
- adde $acc4,$acc4,$a4
- add $acc6,$t2,$t2
- $SHRI $t2,$t2,$BITS-1
- or $acc5,$acc5,$t0
- $LD $t0,$SIZE_T*9($tp) # =tp[8]
- adde $acc5,$acc5,$a5
- $LD $a5,$SIZE_T*3($ap)
- add $acc7,$t3,$t3
- $SHRI $t3,$t3,$BITS-1
- or $acc6,$acc6,$t1
- $LD $t1,$SIZE_T*10($tp) # =tp[9]
- $UMULL $a0,$a1,$a1
- $UMULH $a1,$a1,$a1
- adde $acc6,$acc6,$a6
- $ST $acc0,$SIZE_T*1($tp) # tp[0]=
- add $acc0,$t0,$t0
- $SHRI $t0,$t0,$BITS-1
- or $acc7,$acc7,$t2
- $LD $t2,$SIZE_T*11($tp) # =tp[10]
- adde $acc7,$acc7,$a7
- $LDU $a7,$SIZE_T*4($ap)
- $ST $acc1,$SIZE_T*2($tp) # tp[1]=
- add $acc1,$t1,$t1
- $SHRI $t1,$t1,$BITS-1
- or $acc0,$acc0,$t3
- $LD $t3,$SIZE_T*12($tp) # =tp[11]
- $UMULL $a2,$a3,$a3
- $UMULH $a3,$a3,$a3
- adde $acc0,$acc0,$a0
- $ST $acc2,$SIZE_T*3($tp) # tp[2]=
- add $acc2,$t2,$t2
- $SHRI $t2,$t2,$BITS-1
- or $acc1,$acc1,$t0
- $LD $t0,$SIZE_T*13($tp) # =tp[12]
- adde $acc1,$acc1,$a1
- $ST $acc3,$SIZE_T*4($tp) # tp[3]=
- $ST $acc4,$SIZE_T*5($tp) # tp[4]=
- $ST $acc5,$SIZE_T*6($tp) # tp[5]=
- $ST $acc6,$SIZE_T*7($tp) # tp[6]=
- $STU $acc7,$SIZE_T*8($tp) # tp[7]=
- add $acc3,$t3,$t3
- $SHRI $t3,$t3,$BITS-1
- or $acc2,$acc2,$t1
- bdnz .Lsqr4x_shift_n_add
- ___
- my ($np,$np_end)=($ap,$ap_end);
- $code.=<<___;
- $POP $np,$SIZE_T*7($sp) # pull &np[-1] and n0
- $POP $n0,$SIZE_T*8($sp)
- $UMULL $a4,$a5,$a5
- $UMULH $a5,$a5,$a5
- $ST $acc0,$SIZE_T*1($tp) # tp[8]=
- $LD $acc0,$SIZE_T*12($sp) # =tp[0]
- $LD $t1,$SIZE_T*6($tp) # =tp[13]
- adde $acc2,$acc2,$a2
- add $acc4,$t0,$t0
- $SHRI $t0,$t0,$BITS-1
- or $acc3,$acc3,$t2
- $LD $t2,$SIZE_T*7($tp) # =tp[14]
- adde $acc3,$acc3,$a3
- add $acc5,$t1,$t1
- $SHRI $t1,$t1,$BITS-1
- or $acc4,$acc4,$t3
- $UMULL $a6,$a7,$a7
- $UMULH $a7,$a7,$a7
- adde $acc4,$acc4,$a4
- add $acc6,$t2,$t2
- $SHRI $t2,$t2,$BITS-1
- or $acc5,$acc5,$t0
- $ST $acc1,$SIZE_T*2($tp) # tp[9]=
- $LD $acc1,$SIZE_T*13($sp) # =tp[1]
- adde $acc5,$acc5,$a5
- or $acc6,$acc6,$t1
- $LD $a0,$SIZE_T*1($np)
- $LD $a1,$SIZE_T*2($np)
- adde $acc6,$acc6,$a6
- $LD $a2,$SIZE_T*3($np)
- $LD $a3,$SIZE_T*4($np)
- adde $acc7,$a7,$t2
- $LD $a4,$SIZE_T*5($np)
- $LD $a5,$SIZE_T*6($np)
- ################################################################
- # Reduce by 8 limbs per iteration
- $UMULL $na0,$n0,$acc0 # t[0]*n0
- li $cnt,8
- $LD $a6,$SIZE_T*7($np)
- add $np_end,$np,$num
- $LDU $a7,$SIZE_T*8($np)
- $ST $acc2,$SIZE_T*3($tp) # tp[10]=
- $LD $acc2,$SIZE_T*14($sp)
- $ST $acc3,$SIZE_T*4($tp) # tp[11]=
- $LD $acc3,$SIZE_T*15($sp)
- $ST $acc4,$SIZE_T*5($tp) # tp[12]=
- $LD $acc4,$SIZE_T*16($sp)
- $ST $acc5,$SIZE_T*6($tp) # tp[13]=
- $LD $acc5,$SIZE_T*17($sp)
- $ST $acc6,$SIZE_T*7($tp) # tp[14]=
- $LD $acc6,$SIZE_T*18($sp)
- $ST $acc7,$SIZE_T*8($tp) # tp[15]=
- $LD $acc7,$SIZE_T*19($sp)
- addi $tp,$sp,$SIZE_T*11 # &tp[-1]
- mtctr $cnt
- b .Lsqr8x_reduction
- .align 5
- .Lsqr8x_reduction:
- # (*) $UMULL $t0,$a0,$na0 # lo(n[0-7])*lo(t[0]*n0)
- $UMULL $t1,$a1,$na0
- $UMULL $t2,$a2,$na0
- $STU $na0,$SIZE_T($tp) # put aside t[0]*n0 for tail processing
- $UMULL $t3,$a3,$na0
- # (*) addc $acc0,$acc0,$t0
- addic $acc0,$acc0,-1 # (*)
- $UMULL $t0,$a4,$na0
- adde $acc0,$acc1,$t1
- $UMULL $t1,$a5,$na0
- adde $acc1,$acc2,$t2
- $UMULL $t2,$a6,$na0
- adde $acc2,$acc3,$t3
- $UMULL $t3,$a7,$na0
- adde $acc3,$acc4,$t0
- $UMULH $t0,$a0,$na0 # hi(n[0-7])*lo(t[0]*n0)
- adde $acc4,$acc5,$t1
- $UMULH $t1,$a1,$na0
- adde $acc5,$acc6,$t2
- $UMULH $t2,$a2,$na0
- adde $acc6,$acc7,$t3
- $UMULH $t3,$a3,$na0
- addze $acc7,$zero
- addc $acc0,$acc0,$t0
- $UMULH $t0,$a4,$na0
- adde $acc1,$acc1,$t1
- $UMULH $t1,$a5,$na0
- adde $acc2,$acc2,$t2
- $UMULH $t2,$a6,$na0
- adde $acc3,$acc3,$t3
- $UMULH $t3,$a7,$na0
- $UMULL $na0,$n0,$acc0 # next t[0]*n0
- adde $acc4,$acc4,$t0
- adde $acc5,$acc5,$t1
- adde $acc6,$acc6,$t2
- adde $acc7,$acc7,$t3
- bdnz .Lsqr8x_reduction
- $LD $t0,$SIZE_T*1($tp)
- $LD $t1,$SIZE_T*2($tp)
- $LD $t2,$SIZE_T*3($tp)
- $LD $t3,$SIZE_T*4($tp)
- subi $rp,$tp,$SIZE_T*7
- $UCMP $np_end,$np # done yet?
- addc $acc0,$acc0,$t0
- $LD $t0,$SIZE_T*5($tp)
- adde $acc1,$acc1,$t1
- $LD $t1,$SIZE_T*6($tp)
- adde $acc2,$acc2,$t2
- $LD $t2,$SIZE_T*7($tp)
- adde $acc3,$acc3,$t3
- $LD $t3,$SIZE_T*8($tp)
- adde $acc4,$acc4,$t0
- adde $acc5,$acc5,$t1
- adde $acc6,$acc6,$t2
- adde $acc7,$acc7,$t3
- #addze $carry,$zero # moved below
- beq .Lsqr8x8_post_condition
- $LD $n0,$SIZE_T*0($rp)
- $LD $a0,$SIZE_T*1($np)
- $LD $a1,$SIZE_T*2($np)
- $LD $a2,$SIZE_T*3($np)
- $LD $a3,$SIZE_T*4($np)
- $LD $a4,$SIZE_T*5($np)
- $LD $a5,$SIZE_T*6($np)
- $LD $a6,$SIZE_T*7($np)
- $LDU $a7,$SIZE_T*8($np)
- li $cnt,0
- .align 5
- .Lsqr8x_tail:
- $UMULL $t0,$a0,$n0
- addze $carry,$zero # carry bit, modulo-scheduled
- $UMULL $t1,$a1,$n0
- addi $cnt,$cnt,$SIZE_T
- $UMULL $t2,$a2,$n0
- andi. $cnt,$cnt,$SIZE_T*8-1
- $UMULL $t3,$a3,$n0
- addc $acc0,$acc0,$t0
- $UMULL $t0,$a4,$n0
- adde $acc1,$acc1,$t1
- $UMULL $t1,$a5,$n0
- adde $acc2,$acc2,$t2
- $UMULL $t2,$a6,$n0
- adde $acc3,$acc3,$t3
- $UMULL $t3,$a7,$n0
- adde $acc4,$acc4,$t0
- $UMULH $t0,$a0,$n0
- adde $acc5,$acc5,$t1
- $UMULH $t1,$a1,$n0
- adde $acc6,$acc6,$t2
- $UMULH $t2,$a2,$n0
- adde $acc7,$acc7,$t3
- $UMULH $t3,$a3,$n0
- addze $carry,$carry
- $STU $acc0,$SIZE_T($tp)
- addc $acc0,$acc1,$t0
- $UMULH $t0,$a4,$n0
- adde $acc1,$acc2,$t1
- $UMULH $t1,$a5,$n0
- adde $acc2,$acc3,$t2
- $UMULH $t2,$a6,$n0
- adde $acc3,$acc4,$t3
- $UMULH $t3,$a7,$n0
- $LDX $n0,$rp,$cnt
- adde $acc4,$acc5,$t0
- adde $acc5,$acc6,$t1
- adde $acc6,$acc7,$t2
- adde $acc7,$carry,$t3
- #addze $carry,$zero # moved above
- bne .Lsqr8x_tail
- # note that carry flag is guaranteed
- # to be zero at this point
- $LD $a0,$SIZE_T*1($tp)
- $POP $carry,$SIZE_T*10($sp) # pull top-most carry in case we break
- $UCMP $np_end,$np # done yet?
- $LD $a1,$SIZE_T*2($tp)
- sub $t2,$np_end,$num # rewinded np
- $LD $a2,$SIZE_T*3($tp)
- $LD $a3,$SIZE_T*4($tp)
- $LD $a4,$SIZE_T*5($tp)
- $LD $a5,$SIZE_T*6($tp)
- $LD $a6,$SIZE_T*7($tp)
- $LD $a7,$SIZE_T*8($tp)
- beq .Lsqr8x_tail_break
- addc $acc0,$acc0,$a0
- $LD $a0,$SIZE_T*1($np)
- adde $acc1,$acc1,$a1
- $LD $a1,$SIZE_T*2($np)
- adde $acc2,$acc2,$a2
- $LD $a2,$SIZE_T*3($np)
- adde $acc3,$acc3,$a3
- $LD $a3,$SIZE_T*4($np)
- adde $acc4,$acc4,$a4
- $LD $a4,$SIZE_T*5($np)
- adde $acc5,$acc5,$a5
- $LD $a5,$SIZE_T*6($np)
- adde $acc6,$acc6,$a6
- $LD $a6,$SIZE_T*7($np)
- adde $acc7,$acc7,$a7
- $LDU $a7,$SIZE_T*8($np)
- #addze $carry,$zero # moved above
- b .Lsqr8x_tail
- .align 5
- .Lsqr8x_tail_break:
- $POP $n0,$SIZE_T*8($sp) # pull n0
- $POP $t3,$SIZE_T*9($sp) # &tp[2*num-1]
- addi $cnt,$tp,$SIZE_T*8 # end of current t[num] window
- addic $carry,$carry,-1 # "move" top-most carry to carry bit
- adde $t0,$acc0,$a0
- $LD $acc0,$SIZE_T*8($rp)
- $LD $a0,$SIZE_T*1($t2) # recall that $t2 is &n[-1]
- adde $t1,$acc1,$a1
- $LD $acc1,$SIZE_T*9($rp)
- $LD $a1,$SIZE_T*2($t2)
- adde $acc2,$acc2,$a2
- $LD $a2,$SIZE_T*3($t2)
- adde $acc3,$acc3,$a3
- $LD $a3,$SIZE_T*4($t2)
- adde $acc4,$acc4,$a4
- $LD $a4,$SIZE_T*5($t2)
- adde $acc5,$acc5,$a5
- $LD $a5,$SIZE_T*6($t2)
- adde $acc6,$acc6,$a6
- $LD $a6,$SIZE_T*7($t2)
- adde $acc7,$acc7,$a7
- $LD $a7,$SIZE_T*8($t2)
- addi $np,$t2,$SIZE_T*8
- addze $t2,$zero # top-most carry
- $UMULL $na0,$n0,$acc0
- $ST $t0,$SIZE_T*1($tp)
- $UCMP $cnt,$t3 # did we hit the bottom?
- $ST $t1,$SIZE_T*2($tp)
- li $cnt,8
- $ST $acc2,$SIZE_T*3($tp)
- $LD $acc2,$SIZE_T*10($rp)
- $ST $acc3,$SIZE_T*4($tp)
- $LD $acc3,$SIZE_T*11($rp)
- $ST $acc4,$SIZE_T*5($tp)
- $LD $acc4,$SIZE_T*12($rp)
- $ST $acc5,$SIZE_T*6($tp)
- $LD $acc5,$SIZE_T*13($rp)
- $ST $acc6,$SIZE_T*7($tp)
- $LD $acc6,$SIZE_T*14($rp)
- $ST $acc7,$SIZE_T*8($tp)
- $LD $acc7,$SIZE_T*15($rp)
- $PUSH $t2,$SIZE_T*10($sp) # off-load top-most carry
- addi $tp,$rp,$SIZE_T*7 # slide the window
- mtctr $cnt
- bne .Lsqr8x_reduction
- ################################################################
- # Final step. We see if result is larger than modulus, and
- # if it is, subtract the modulus. But comparison implies
- # subtraction. So we subtract modulus, see if it borrowed,
- # and conditionally copy original value.
- $POP $rp,$SIZE_T*6($sp) # pull &rp[-1]
- srwi $cnt,$num,`log($SIZE_T)/log(2)+3`
- mr $n0,$tp # put tp aside
- addi $tp,$tp,$SIZE_T*8
- subi $cnt,$cnt,1
- subfc $t0,$a0,$acc0
- subfe $t1,$a1,$acc1
- mr $carry,$t2
- mr $ap_end,$rp # $rp copy
- mtctr $cnt
- b .Lsqr8x_sub
- .align 5
- .Lsqr8x_sub:
- $LD $a0,$SIZE_T*1($np)
- $LD $acc0,$SIZE_T*1($tp)
- $LD $a1,$SIZE_T*2($np)
- $LD $acc1,$SIZE_T*2($tp)
- subfe $t2,$a2,$acc2
- $LD $a2,$SIZE_T*3($np)
- $LD $acc2,$SIZE_T*3($tp)
- subfe $t3,$a3,$acc3
- $LD $a3,$SIZE_T*4($np)
- $LD $acc3,$SIZE_T*4($tp)
- $ST $t0,$SIZE_T*1($rp)
- subfe $t0,$a4,$acc4
- $LD $a4,$SIZE_T*5($np)
- $LD $acc4,$SIZE_T*5($tp)
- $ST $t1,$SIZE_T*2($rp)
- subfe $t1,$a5,$acc5
- $LD $a5,$SIZE_T*6($np)
- $LD $acc5,$SIZE_T*6($tp)
- $ST $t2,$SIZE_T*3($rp)
- subfe $t2,$a6,$acc6
- $LD $a6,$SIZE_T*7($np)
- $LD $acc6,$SIZE_T*7($tp)
- $ST $t3,$SIZE_T*4($rp)
- subfe $t3,$a7,$acc7
- $LDU $a7,$SIZE_T*8($np)
- $LDU $acc7,$SIZE_T*8($tp)
- $ST $t0,$SIZE_T*5($rp)
- subfe $t0,$a0,$acc0
- $ST $t1,$SIZE_T*6($rp)
- subfe $t1,$a1,$acc1
- $ST $t2,$SIZE_T*7($rp)
- $STU $t3,$SIZE_T*8($rp)
- bdnz .Lsqr8x_sub
- srwi $cnt,$num,`log($SIZE_T)/log(2)+2`
- $LD $a0,$SIZE_T*1($ap_end) # original $rp
- $LD $acc0,$SIZE_T*1($n0) # original $tp
- subi $cnt,$cnt,1
- $LD $a1,$SIZE_T*2($ap_end)
- $LD $acc1,$SIZE_T*2($n0)
- subfe $t2,$a2,$acc2
- $LD $a2,$SIZE_T*3($ap_end)
- $LD $acc2,$SIZE_T*3($n0)
- subfe $t3,$a3,$acc3
- $LD $a3,$SIZE_T*4($ap_end)
- $LDU $acc3,$SIZE_T*4($n0)
- $ST $t0,$SIZE_T*1($rp)
- subfe $t0,$a4,$acc4
- $ST $t1,$SIZE_T*2($rp)
- subfe $t1,$a5,$acc5
- $ST $t2,$SIZE_T*3($rp)
- subfe $t2,$a6,$acc6
- $ST $t3,$SIZE_T*4($rp)
- subfe $t3,$a7,$acc7
- $ST $t0,$SIZE_T*5($rp)
- subfe $carry,$zero,$carry # did it borrow?
- $ST $t1,$SIZE_T*6($rp)
- $ST $t2,$SIZE_T*7($rp)
- $ST $t3,$SIZE_T*8($rp)
- addi $tp,$sp,$SIZE_T*11
- mtctr $cnt
- .Lsqr4x_cond_copy:
- andc $a0,$a0,$carry
- $ST $zero,-$SIZE_T*3($n0) # wipe stack clean
- and $acc0,$acc0,$carry
- $ST $zero,-$SIZE_T*2($n0)
- andc $a1,$a1,$carry
- $ST $zero,-$SIZE_T*1($n0)
- and $acc1,$acc1,$carry
- $ST $zero,-$SIZE_T*0($n0)
- andc $a2,$a2,$carry
- $ST $zero,$SIZE_T*1($tp)
- and $acc2,$acc2,$carry
- $ST $zero,$SIZE_T*2($tp)
- andc $a3,$a3,$carry
- $ST $zero,$SIZE_T*3($tp)
- and $acc3,$acc3,$carry
- $STU $zero,$SIZE_T*4($tp)
- or $t0,$a0,$acc0
- $LD $a0,$SIZE_T*5($ap_end)
- $LD $acc0,$SIZE_T*1($n0)
- or $t1,$a1,$acc1
- $LD $a1,$SIZE_T*6($ap_end)
- $LD $acc1,$SIZE_T*2($n0)
- or $t2,$a2,$acc2
- $LD $a2,$SIZE_T*7($ap_end)
- $LD $acc2,$SIZE_T*3($n0)
- or $t3,$a3,$acc3
- $LD $a3,$SIZE_T*8($ap_end)
- $LDU $acc3,$SIZE_T*4($n0)
- $ST $t0,$SIZE_T*1($ap_end)
- $ST $t1,$SIZE_T*2($ap_end)
- $ST $t2,$SIZE_T*3($ap_end)
- $STU $t3,$SIZE_T*4($ap_end)
- bdnz .Lsqr4x_cond_copy
- $POP $ap,0($sp) # pull saved sp
- andc $a0,$a0,$carry
- and $acc0,$acc0,$carry
- andc $a1,$a1,$carry
- and $acc1,$acc1,$carry
- andc $a2,$a2,$carry
- and $acc2,$acc2,$carry
- andc $a3,$a3,$carry
- and $acc3,$acc3,$carry
- or $t0,$a0,$acc0
- or $t1,$a1,$acc1
- or $t2,$a2,$acc2
- or $t3,$a3,$acc3
- $ST $t0,$SIZE_T*1($ap_end)
- $ST $t1,$SIZE_T*2($ap_end)
- $ST $t2,$SIZE_T*3($ap_end)
- $ST $t3,$SIZE_T*4($ap_end)
- b .Lsqr8x_done
- .align 5
- .Lsqr8x8_post_condition:
- $POP $rp,$SIZE_T*6($sp) # pull rp
- $POP $ap,0($sp) # pull saved sp
- addze $carry,$zero
- # $acc0-7,$carry hold result, $a0-7 hold modulus
- subfc $acc0,$a0,$acc0
- subfe $acc1,$a1,$acc1
- $ST $zero,$SIZE_T*12($sp) # wipe stack clean
- $ST $zero,$SIZE_T*13($sp)
- subfe $acc2,$a2,$acc2
- $ST $zero,$SIZE_T*14($sp)
- $ST $zero,$SIZE_T*15($sp)
- subfe $acc3,$a3,$acc3
- $ST $zero,$SIZE_T*16($sp)
- $ST $zero,$SIZE_T*17($sp)
- subfe $acc4,$a4,$acc4
- $ST $zero,$SIZE_T*18($sp)
- $ST $zero,$SIZE_T*19($sp)
- subfe $acc5,$a5,$acc5
- $ST $zero,$SIZE_T*20($sp)
- $ST $zero,$SIZE_T*21($sp)
- subfe $acc6,$a6,$acc6
- $ST $zero,$SIZE_T*22($sp)
- $ST $zero,$SIZE_T*23($sp)
- subfe $acc7,$a7,$acc7
- $ST $zero,$SIZE_T*24($sp)
- $ST $zero,$SIZE_T*25($sp)
- subfe $carry,$zero,$carry # did it borrow?
- $ST $zero,$SIZE_T*26($sp)
- $ST $zero,$SIZE_T*27($sp)
- and $a0,$a0,$carry
- and $a1,$a1,$carry
- addc $acc0,$acc0,$a0 # add modulus back if borrowed
- and $a2,$a2,$carry
- adde $acc1,$acc1,$a1
- and $a3,$a3,$carry
- adde $acc2,$acc2,$a2
- and $a4,$a4,$carry
- adde $acc3,$acc3,$a3
- and $a5,$a5,$carry
- adde $acc4,$acc4,$a4
- and $a6,$a6,$carry
- adde $acc5,$acc5,$a5
- and $a7,$a7,$carry
- adde $acc6,$acc6,$a6
- adde $acc7,$acc7,$a7
- $ST $acc0,$SIZE_T*1($rp)
- $ST $acc1,$SIZE_T*2($rp)
- $ST $acc2,$SIZE_T*3($rp)
- $ST $acc3,$SIZE_T*4($rp)
- $ST $acc4,$SIZE_T*5($rp)
- $ST $acc5,$SIZE_T*6($rp)
- $ST $acc6,$SIZE_T*7($rp)
- $ST $acc7,$SIZE_T*8($rp)
- .Lsqr8x_done:
- $PUSH $zero,$SIZE_T*8($sp)
- $PUSH $zero,$SIZE_T*10($sp)
- $POP r14,-$SIZE_T*18($ap)
- li r3,1 # signal "done"
- $POP r15,-$SIZE_T*17($ap)
- $POP r16,-$SIZE_T*16($ap)
- $POP r17,-$SIZE_T*15($ap)
- $POP r18,-$SIZE_T*14($ap)
- $POP r19,-$SIZE_T*13($ap)
- $POP r20,-$SIZE_T*12($ap)
- $POP r21,-$SIZE_T*11($ap)
- $POP r22,-$SIZE_T*10($ap)
- $POP r23,-$SIZE_T*9($ap)
- $POP r24,-$SIZE_T*8($ap)
- $POP r25,-$SIZE_T*7($ap)
- $POP r26,-$SIZE_T*6($ap)
- $POP r27,-$SIZE_T*5($ap)
- $POP r28,-$SIZE_T*4($ap)
- $POP r29,-$SIZE_T*3($ap)
- $POP r30,-$SIZE_T*2($ap)
- $POP r31,-$SIZE_T*1($ap)
- mr $sp,$ap
- blr
- .long 0
- .byte 0,12,4,0x20,0x80,18,6,0
- .long 0
- .size __bn_sqr8x_mont,.-__bn_sqr8x_mont
- ___
- }
- $code.=<<___;
- .asciz "Montgomery Multiplication for PPC, CRYPTOGAMS by <appro\@openssl.org>"
- ___
- $code =~ s/\`([^\`]*)\`/eval $1/gem;
- print $code;
- close STDOUT or die "error closing STDOUT: $!";
|