2
0

x86_64-mont5.pl 82 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295329632973298329933003301330233033304330533063307330833093310331133123313331433153316331733183319332033213322332333243325332633273328332933303331333233333334333533363337333833393340334133423343334433453346334733483349335033513352335333543355335633573358335933603361336233633364336533663367336833693370337133723373337433753376337733783379338033813382338333843385338633873388338933903391339233933394339533963397339833993400340134023403340434053406340734083409341034113412341334143415341634173418341934203421342234233424342534263427342834293430343134323433343434353436343734383439344034413442344334443445344634473448344934503451345234533454345534563457345834593460346134623463346434653466346734683469347034713472347334743475347634773478347934803481348234833484348534863487348834893490349134923493349434953496349734983499350035013502350335043505350635073508350935103511351235133514351535163517351835193520352135223523352435253526352735283529353035313532353335343535353635373538353935403541354235433544354535463547354835493550355135523553355435553556355735583559356035613562356335643565356635673568356935703571357235733574357535763577357835793580358135823583358435853586358735883589359035913592359335943595359635973598359936003601360236033604360536063607360836093610361136123613361436153616361736183619362036213622362336243625362636273628362936303631363236333634363536363637363836393640364136423643364436453646364736483649365036513652365336543655365636573658365936603661366236633664366536663667366836693670367136723673367436753676367736783679368036813682368336843685368636873688368936903691369236933694369536963697369836993700370137023703370437053706370737083709371037113712371337143715371637173718371937203721372237233724372537263727372837293730373137323733373437353736373737383739374037413742374337443745374637473748374937503751375237533754375537563757375837593760376137623763376437653766376737683769
  1. #! /usr/bin/env perl
  2. # Copyright 2011-2020 The OpenSSL Project Authors. All Rights Reserved.
  3. #
  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
  8. # ====================================================================
  9. # Written by Andy Polyakov <appro@openssl.org> for the OpenSSL
  10. # project. The module is, however, dual licensed under OpenSSL and
  11. # CRYPTOGAMS licenses depending on where you obtain it. For further
  12. # details see http://www.openssl.org/~appro/cryptogams/.
  13. # ====================================================================
  14. # August 2011.
  15. #
  16. # Companion to x86_64-mont.pl that optimizes cache-timing attack
  17. # countermeasures. The subroutines are produced by replacing bp[i]
  18. # references in their x86_64-mont.pl counterparts with cache-neutral
  19. # references to powers table computed in BN_mod_exp_mont_consttime.
  20. # In addition subroutine that scatters elements of the powers table
  21. # is implemented, so that scatter-/gathering can be tuned without
  22. # bn_exp.c modifications.
  23. # August 2013.
  24. #
  25. # Add MULX/AD*X code paths and additional interfaces to optimize for
  26. # branch prediction unit. For input lengths that are multiples of 8
  27. # the np argument is not just modulus value, but one interleaved
  28. # with 0. This is to optimize post-condition...
  29. # $output is the last argument if it looks like a file (it has an extension)
  30. # $flavour is the first argument if it doesn't look like a file
  31. $output = $#ARGV >= 0 && $ARGV[$#ARGV] =~ m|\.\w+$| ? pop : undef;
  32. $flavour = $#ARGV >= 0 && $ARGV[0] !~ m|\.| ? shift : undef;
  33. $win64=0; $win64=1 if ($flavour =~ /[nm]asm|mingw64/ || $output =~ /\.asm$/);
  34. $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
  35. ( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
  36. ( $xlate="${dir}../../perlasm/x86_64-xlate.pl" and -f $xlate) or
  37. die "can't locate x86_64-xlate.pl";
  38. open OUT,"| \"$^X\" \"$xlate\" $flavour \"$output\""
  39. or die "can't call $xlate: $!";
  40. *STDOUT=*OUT;
  41. if (`$ENV{CC} -Wa,-v -c -o /dev/null -x assembler /dev/null 2>&1`
  42. =~ /GNU assembler version ([2-9]\.[0-9]+)/) {
  43. $addx = ($1>=2.23);
  44. }
  45. if (!$addx && $win64 && ($flavour =~ /nasm/ || $ENV{ASM} =~ /nasm/) &&
  46. `nasm -v 2>&1` =~ /NASM version ([2-9]\.[0-9]+)/) {
  47. $addx = ($1>=2.10);
  48. }
  49. if (!$addx && $win64 && ($flavour =~ /masm/ || $ENV{ASM} =~ /ml64/) &&
  50. `ml64 2>&1` =~ /Version ([0-9]+)\./) {
  51. $addx = ($1>=12);
  52. }
  53. if (!$addx && `$ENV{CC} -v 2>&1` =~ /((?:clang|LLVM) version|.*based on LLVM) ([0-9]+)\.([0-9]+)/) {
  54. my $ver = $2 + $3/100.0; # 3.1->3.01, 3.10->3.10
  55. $addx = ($ver>=3.03);
  56. }
  57. # int bn_mul_mont_gather5(
  58. $rp="%rdi"; # BN_ULONG *rp,
  59. $ap="%rsi"; # const BN_ULONG *ap,
  60. $bp="%rdx"; # const BN_ULONG *bp,
  61. $np="%rcx"; # const BN_ULONG *np,
  62. $n0="%r8"; # const BN_ULONG *n0,
  63. $num="%r9"; # int num,
  64. # int idx); # 0 to 2^5-1, "index" in $bp holding
  65. # pre-computed powers of a', interlaced
  66. # in such manner that b[0] is $bp[idx],
  67. # b[1] is [2^5+idx], etc.
  68. $lo0="%r10";
  69. $hi0="%r11";
  70. $hi1="%r13";
  71. $i="%r14";
  72. $j="%r15";
  73. $m0="%rbx";
  74. $m1="%rbp";
  75. $code=<<___;
  76. .text
  77. .extern OPENSSL_ia32cap_P
  78. .globl bn_mul_mont_gather5
  79. .type bn_mul_mont_gather5,\@function,6
  80. .align 64
  81. bn_mul_mont_gather5:
  82. .cfi_startproc
  83. mov ${num}d,${num}d
  84. mov %rsp,%rax
  85. .cfi_def_cfa_register %rax
  86. test \$7,${num}d
  87. jnz .Lmul_enter
  88. ___
  89. $code.=<<___ if ($addx);
  90. mov OPENSSL_ia32cap_P+8(%rip),%r11d
  91. ___
  92. $code.=<<___;
  93. jmp .Lmul4x_enter
  94. .align 16
  95. .Lmul_enter:
  96. movd `($win64?56:8)`(%rsp),%xmm5 # load 7th argument
  97. push %rbx
  98. .cfi_push %rbx
  99. push %rbp
  100. .cfi_push %rbp
  101. push %r12
  102. .cfi_push %r12
  103. push %r13
  104. .cfi_push %r13
  105. push %r14
  106. .cfi_push %r14
  107. push %r15
  108. .cfi_push %r15
  109. neg $num
  110. mov %rsp,%r11
  111. lea -280(%rsp,$num,8),%r10 # future alloca(8*(num+2)+256+8)
  112. neg $num # restore $num
  113. and \$-1024,%r10 # minimize TLB usage
  114. # An OS-agnostic version of __chkstk.
  115. #
  116. # Some OSes (Windows) insist on stack being "wired" to
  117. # physical memory in strictly sequential manner, i.e. if stack
  118. # allocation spans two pages, then reference to farmost one can
  119. # be punishable by SEGV. But page walking can do good even on
  120. # other OSes, because it guarantees that villain thread hits
  121. # the guard page before it can make damage to innocent one...
  122. sub %r10,%r11
  123. and \$-4096,%r11
  124. lea (%r10,%r11),%rsp
  125. mov (%rsp),%r11
  126. cmp %r10,%rsp
  127. ja .Lmul_page_walk
  128. jmp .Lmul_page_walk_done
  129. .Lmul_page_walk:
  130. lea -4096(%rsp),%rsp
  131. mov (%rsp),%r11
  132. cmp %r10,%rsp
  133. ja .Lmul_page_walk
  134. .Lmul_page_walk_done:
  135. lea .Linc(%rip),%r10
  136. mov %rax,8(%rsp,$num,8) # tp[num+1]=%rsp
  137. .cfi_cfa_expression %rsp+8,$num,8,mul,plus,deref,+8
  138. .Lmul_body:
  139. lea 128($bp),%r12 # reassign $bp (+size optimization)
  140. ___
  141. $bp="%r12";
  142. $STRIDE=2**5*8; # 5 is "window size"
  143. $N=$STRIDE/4; # should match cache line size
  144. $code.=<<___;
  145. movdqa 0(%r10),%xmm0 # 00000001000000010000000000000000
  146. movdqa 16(%r10),%xmm1 # 00000002000000020000000200000002
  147. lea 24-112(%rsp,$num,8),%r10# place the mask after tp[num+3] (+ICache optimization)
  148. and \$-16,%r10
  149. pshufd \$0,%xmm5,%xmm5 # broadcast index
  150. movdqa %xmm1,%xmm4
  151. movdqa %xmm1,%xmm2
  152. ___
  153. ########################################################################
  154. # calculate mask by comparing 0..31 to index and save result to stack
  155. #
  156. $code.=<<___;
  157. paddd %xmm0,%xmm1
  158. pcmpeqd %xmm5,%xmm0 # compare to 1,0
  159. .byte 0x67
  160. movdqa %xmm4,%xmm3
  161. ___
  162. for($k=0;$k<$STRIDE/16-4;$k+=4) {
  163. $code.=<<___;
  164. paddd %xmm1,%xmm2
  165. pcmpeqd %xmm5,%xmm1 # compare to 3,2
  166. movdqa %xmm0,`16*($k+0)+112`(%r10)
  167. movdqa %xmm4,%xmm0
  168. paddd %xmm2,%xmm3
  169. pcmpeqd %xmm5,%xmm2 # compare to 5,4
  170. movdqa %xmm1,`16*($k+1)+112`(%r10)
  171. movdqa %xmm4,%xmm1
  172. paddd %xmm3,%xmm0
  173. pcmpeqd %xmm5,%xmm3 # compare to 7,6
  174. movdqa %xmm2,`16*($k+2)+112`(%r10)
  175. movdqa %xmm4,%xmm2
  176. paddd %xmm0,%xmm1
  177. pcmpeqd %xmm5,%xmm0
  178. movdqa %xmm3,`16*($k+3)+112`(%r10)
  179. movdqa %xmm4,%xmm3
  180. ___
  181. }
  182. $code.=<<___; # last iteration can be optimized
  183. paddd %xmm1,%xmm2
  184. pcmpeqd %xmm5,%xmm1
  185. movdqa %xmm0,`16*($k+0)+112`(%r10)
  186. paddd %xmm2,%xmm3
  187. .byte 0x67
  188. pcmpeqd %xmm5,%xmm2
  189. movdqa %xmm1,`16*($k+1)+112`(%r10)
  190. pcmpeqd %xmm5,%xmm3
  191. movdqa %xmm2,`16*($k+2)+112`(%r10)
  192. pand `16*($k+0)-128`($bp),%xmm0 # while it's still in register
  193. pand `16*($k+1)-128`($bp),%xmm1
  194. pand `16*($k+2)-128`($bp),%xmm2
  195. movdqa %xmm3,`16*($k+3)+112`(%r10)
  196. pand `16*($k+3)-128`($bp),%xmm3
  197. por %xmm2,%xmm0
  198. por %xmm3,%xmm1
  199. ___
  200. for($k=0;$k<$STRIDE/16-4;$k+=4) {
  201. $code.=<<___;
  202. movdqa `16*($k+0)-128`($bp),%xmm4
  203. movdqa `16*($k+1)-128`($bp),%xmm5
  204. movdqa `16*($k+2)-128`($bp),%xmm2
  205. pand `16*($k+0)+112`(%r10),%xmm4
  206. movdqa `16*($k+3)-128`($bp),%xmm3
  207. pand `16*($k+1)+112`(%r10),%xmm5
  208. por %xmm4,%xmm0
  209. pand `16*($k+2)+112`(%r10),%xmm2
  210. por %xmm5,%xmm1
  211. pand `16*($k+3)+112`(%r10),%xmm3
  212. por %xmm2,%xmm0
  213. por %xmm3,%xmm1
  214. ___
  215. }
  216. $code.=<<___;
  217. por %xmm1,%xmm0
  218. pshufd \$0x4e,%xmm0,%xmm1
  219. por %xmm1,%xmm0
  220. lea $STRIDE($bp),$bp
  221. movq %xmm0,$m0 # m0=bp[0]
  222. mov ($n0),$n0 # pull n0[0] value
  223. mov ($ap),%rax
  224. xor $i,$i # i=0
  225. xor $j,$j # j=0
  226. mov $n0,$m1
  227. mulq $m0 # ap[0]*bp[0]
  228. mov %rax,$lo0
  229. mov ($np),%rax
  230. imulq $lo0,$m1 # "tp[0]"*n0
  231. mov %rdx,$hi0
  232. mulq $m1 # np[0]*m1
  233. add %rax,$lo0 # discarded
  234. mov 8($ap),%rax
  235. adc \$0,%rdx
  236. mov %rdx,$hi1
  237. lea 1($j),$j # j++
  238. jmp .L1st_enter
  239. .align 16
  240. .L1st:
  241. add %rax,$hi1
  242. mov ($ap,$j,8),%rax
  243. adc \$0,%rdx
  244. add $hi0,$hi1 # np[j]*m1+ap[j]*bp[0]
  245. mov $lo0,$hi0
  246. adc \$0,%rdx
  247. mov $hi1,-16(%rsp,$j,8) # tp[j-1]
  248. mov %rdx,$hi1
  249. .L1st_enter:
  250. mulq $m0 # ap[j]*bp[0]
  251. add %rax,$hi0
  252. mov ($np,$j,8),%rax
  253. adc \$0,%rdx
  254. lea 1($j),$j # j++
  255. mov %rdx,$lo0
  256. mulq $m1 # np[j]*m1
  257. cmp $num,$j
  258. jne .L1st # note that upon exit $j==$num, so
  259. # they can be used interchangeably
  260. add %rax,$hi1
  261. adc \$0,%rdx
  262. add $hi0,$hi1 # np[j]*m1+ap[j]*bp[0]
  263. adc \$0,%rdx
  264. mov $hi1,-16(%rsp,$num,8) # tp[num-1]
  265. mov %rdx,$hi1
  266. mov $lo0,$hi0
  267. xor %rdx,%rdx
  268. add $hi0,$hi1
  269. adc \$0,%rdx
  270. mov $hi1,-8(%rsp,$num,8)
  271. mov %rdx,(%rsp,$num,8) # store upmost overflow bit
  272. lea 1($i),$i # i++
  273. jmp .Louter
  274. .align 16
  275. .Louter:
  276. lea 24+128(%rsp,$num,8),%rdx # where 256-byte mask is (+size optimization)
  277. and \$-16,%rdx
  278. pxor %xmm4,%xmm4
  279. pxor %xmm5,%xmm5
  280. ___
  281. for($k=0;$k<$STRIDE/16;$k+=4) {
  282. $code.=<<___;
  283. movdqa `16*($k+0)-128`($bp),%xmm0
  284. movdqa `16*($k+1)-128`($bp),%xmm1
  285. movdqa `16*($k+2)-128`($bp),%xmm2
  286. movdqa `16*($k+3)-128`($bp),%xmm3
  287. pand `16*($k+0)-128`(%rdx),%xmm0
  288. pand `16*($k+1)-128`(%rdx),%xmm1
  289. por %xmm0,%xmm4
  290. pand `16*($k+2)-128`(%rdx),%xmm2
  291. por %xmm1,%xmm5
  292. pand `16*($k+3)-128`(%rdx),%xmm3
  293. por %xmm2,%xmm4
  294. por %xmm3,%xmm5
  295. ___
  296. }
  297. $code.=<<___;
  298. por %xmm5,%xmm4
  299. pshufd \$0x4e,%xmm4,%xmm0
  300. por %xmm4,%xmm0
  301. lea $STRIDE($bp),$bp
  302. mov ($ap),%rax # ap[0]
  303. movq %xmm0,$m0 # m0=bp[i]
  304. xor $j,$j # j=0
  305. mov $n0,$m1
  306. mov (%rsp),$lo0
  307. mulq $m0 # ap[0]*bp[i]
  308. add %rax,$lo0 # ap[0]*bp[i]+tp[0]
  309. mov ($np),%rax
  310. adc \$0,%rdx
  311. imulq $lo0,$m1 # tp[0]*n0
  312. mov %rdx,$hi0
  313. mulq $m1 # np[0]*m1
  314. add %rax,$lo0 # discarded
  315. mov 8($ap),%rax
  316. adc \$0,%rdx
  317. mov 8(%rsp),$lo0 # tp[1]
  318. mov %rdx,$hi1
  319. lea 1($j),$j # j++
  320. jmp .Linner_enter
  321. .align 16
  322. .Linner:
  323. add %rax,$hi1
  324. mov ($ap,$j,8),%rax
  325. adc \$0,%rdx
  326. add $lo0,$hi1 # np[j]*m1+ap[j]*bp[i]+tp[j]
  327. mov (%rsp,$j,8),$lo0
  328. adc \$0,%rdx
  329. mov $hi1,-16(%rsp,$j,8) # tp[j-1]
  330. mov %rdx,$hi1
  331. .Linner_enter:
  332. mulq $m0 # ap[j]*bp[i]
  333. add %rax,$hi0
  334. mov ($np,$j,8),%rax
  335. adc \$0,%rdx
  336. add $hi0,$lo0 # ap[j]*bp[i]+tp[j]
  337. mov %rdx,$hi0
  338. adc \$0,$hi0
  339. lea 1($j),$j # j++
  340. mulq $m1 # np[j]*m1
  341. cmp $num,$j
  342. jne .Linner # note that upon exit $j==$num, so
  343. # they can be used interchangeably
  344. add %rax,$hi1
  345. adc \$0,%rdx
  346. add $lo0,$hi1 # np[j]*m1+ap[j]*bp[i]+tp[j]
  347. mov (%rsp,$num,8),$lo0
  348. adc \$0,%rdx
  349. mov $hi1,-16(%rsp,$num,8) # tp[num-1]
  350. mov %rdx,$hi1
  351. xor %rdx,%rdx
  352. add $hi0,$hi1
  353. adc \$0,%rdx
  354. add $lo0,$hi1 # pull upmost overflow bit
  355. adc \$0,%rdx
  356. mov $hi1,-8(%rsp,$num,8)
  357. mov %rdx,(%rsp,$num,8) # store upmost overflow bit
  358. lea 1($i),$i # i++
  359. cmp $num,$i
  360. jb .Louter
  361. xor $i,$i # i=0 and clear CF!
  362. mov (%rsp),%rax # tp[0]
  363. lea (%rsp),$ap # borrow ap for tp
  364. mov $num,$j # j=num
  365. jmp .Lsub
  366. .align 16
  367. .Lsub: sbb ($np,$i,8),%rax
  368. mov %rax,($rp,$i,8) # rp[i]=tp[i]-np[i]
  369. mov 8($ap,$i,8),%rax # tp[i+1]
  370. lea 1($i),$i # i++
  371. dec $j # doesn't affect CF!
  372. jnz .Lsub
  373. sbb \$0,%rax # handle upmost overflow bit
  374. mov \$-1,%rbx
  375. xor %rax,%rbx
  376. xor $i,$i
  377. mov $num,$j # j=num
  378. .Lcopy: # conditional copy
  379. mov ($rp,$i,8),%rcx
  380. mov (%rsp,$i,8),%rdx
  381. and %rbx,%rcx
  382. and %rax,%rdx
  383. mov $i,(%rsp,$i,8) # zap temporary vector
  384. or %rcx,%rdx
  385. mov %rdx,($rp,$i,8) # rp[i]=tp[i]
  386. lea 1($i),$i
  387. sub \$1,$j
  388. jnz .Lcopy
  389. mov 8(%rsp,$num,8),%rsi # restore %rsp
  390. .cfi_def_cfa %rsi,8
  391. mov \$1,%rax
  392. mov -48(%rsi),%r15
  393. .cfi_restore %r15
  394. mov -40(%rsi),%r14
  395. .cfi_restore %r14
  396. mov -32(%rsi),%r13
  397. .cfi_restore %r13
  398. mov -24(%rsi),%r12
  399. .cfi_restore %r12
  400. mov -16(%rsi),%rbp
  401. .cfi_restore %rbp
  402. mov -8(%rsi),%rbx
  403. .cfi_restore %rbx
  404. lea (%rsi),%rsp
  405. .cfi_def_cfa_register %rsp
  406. .Lmul_epilogue:
  407. ret
  408. .cfi_endproc
  409. .size bn_mul_mont_gather5,.-bn_mul_mont_gather5
  410. ___
  411. {{{
  412. my @A=("%r10","%r11");
  413. my @N=("%r13","%rdi");
  414. $code.=<<___;
  415. .type bn_mul4x_mont_gather5,\@function,6
  416. .align 32
  417. bn_mul4x_mont_gather5:
  418. .cfi_startproc
  419. .byte 0x67
  420. mov %rsp,%rax
  421. .cfi_def_cfa_register %rax
  422. .Lmul4x_enter:
  423. ___
  424. $code.=<<___ if ($addx);
  425. and \$0x80108,%r11d
  426. cmp \$0x80108,%r11d # check for AD*X+BMI2+BMI1
  427. je .Lmulx4x_enter
  428. ___
  429. $code.=<<___;
  430. push %rbx
  431. .cfi_push %rbx
  432. push %rbp
  433. .cfi_push %rbp
  434. push %r12
  435. .cfi_push %r12
  436. push %r13
  437. .cfi_push %r13
  438. push %r14
  439. .cfi_push %r14
  440. push %r15
  441. .cfi_push %r15
  442. .Lmul4x_prologue:
  443. .byte 0x67
  444. shl \$3,${num}d # convert $num to bytes
  445. lea ($num,$num,2),%r10 # 3*$num in bytes
  446. neg $num # -$num
  447. ##############################################################
  448. # Ensure that stack frame doesn't alias with $rptr+3*$num
  449. # modulo 4096, which covers ret[num], am[num] and n[num]
  450. # (see bn_exp.c). This is done to allow memory disambiguation
  451. # logic do its magic. [Extra [num] is allocated in order
  452. # to align with bn_power5's frame, which is cleansed after
  453. # completing exponentiation. Extra 256 bytes is for power mask
  454. # calculated from 7th argument, the index.]
  455. #
  456. lea -320(%rsp,$num,2),%r11
  457. mov %rsp,%rbp
  458. sub $rp,%r11
  459. and \$4095,%r11
  460. cmp %r11,%r10
  461. jb .Lmul4xsp_alt
  462. sub %r11,%rbp # align with $rp
  463. lea -320(%rbp,$num,2),%rbp # future alloca(frame+2*num*8+256)
  464. jmp .Lmul4xsp_done
  465. .align 32
  466. .Lmul4xsp_alt:
  467. lea 4096-320(,$num,2),%r10
  468. lea -320(%rbp,$num,2),%rbp # future alloca(frame+2*num*8+256)
  469. sub %r10,%r11
  470. mov \$0,%r10
  471. cmovc %r10,%r11
  472. sub %r11,%rbp
  473. .Lmul4xsp_done:
  474. and \$-64,%rbp
  475. mov %rsp,%r11
  476. sub %rbp,%r11
  477. and \$-4096,%r11
  478. lea (%rbp,%r11),%rsp
  479. mov (%rsp),%r10
  480. cmp %rbp,%rsp
  481. ja .Lmul4x_page_walk
  482. jmp .Lmul4x_page_walk_done
  483. .Lmul4x_page_walk:
  484. lea -4096(%rsp),%rsp
  485. mov (%rsp),%r10
  486. cmp %rbp,%rsp
  487. ja .Lmul4x_page_walk
  488. .Lmul4x_page_walk_done:
  489. neg $num
  490. mov %rax,40(%rsp)
  491. .cfi_cfa_expression %rsp+40,deref,+8
  492. .Lmul4x_body:
  493. call mul4x_internal
  494. mov 40(%rsp),%rsi # restore %rsp
  495. .cfi_def_cfa %rsi,8
  496. mov \$1,%rax
  497. mov -48(%rsi),%r15
  498. .cfi_restore %r15
  499. mov -40(%rsi),%r14
  500. .cfi_restore %r14
  501. mov -32(%rsi),%r13
  502. .cfi_restore %r13
  503. mov -24(%rsi),%r12
  504. .cfi_restore %r12
  505. mov -16(%rsi),%rbp
  506. .cfi_restore %rbp
  507. mov -8(%rsi),%rbx
  508. .cfi_restore %rbx
  509. lea (%rsi),%rsp
  510. .cfi_def_cfa_register %rsp
  511. .Lmul4x_epilogue:
  512. ret
  513. .cfi_endproc
  514. .size bn_mul4x_mont_gather5,.-bn_mul4x_mont_gather5
  515. .type mul4x_internal,\@abi-omnipotent
  516. .align 32
  517. mul4x_internal:
  518. .cfi_startproc
  519. shl \$5,$num # $num was in bytes
  520. movd `($win64?56:8)`(%rax),%xmm5 # load 7th argument, index
  521. lea .Linc(%rip),%rax
  522. lea 128(%rdx,$num),%r13 # end of powers table (+size optimization)
  523. shr \$5,$num # restore $num
  524. ___
  525. $bp="%r12";
  526. $STRIDE=2**5*8; # 5 is "window size"
  527. $N=$STRIDE/4; # should match cache line size
  528. $tp=$i;
  529. $code.=<<___;
  530. movdqa 0(%rax),%xmm0 # 00000001000000010000000000000000
  531. movdqa 16(%rax),%xmm1 # 00000002000000020000000200000002
  532. lea 88-112(%rsp,$num),%r10 # place the mask after tp[num+1] (+ICache optimization)
  533. lea 128(%rdx),$bp # size optimization
  534. pshufd \$0,%xmm5,%xmm5 # broadcast index
  535. movdqa %xmm1,%xmm4
  536. .byte 0x67,0x67
  537. movdqa %xmm1,%xmm2
  538. ___
  539. ########################################################################
  540. # calculate mask by comparing 0..31 to index and save result to stack
  541. #
  542. $code.=<<___;
  543. paddd %xmm0,%xmm1
  544. pcmpeqd %xmm5,%xmm0 # compare to 1,0
  545. .byte 0x67
  546. movdqa %xmm4,%xmm3
  547. ___
  548. for($i=0;$i<$STRIDE/16-4;$i+=4) {
  549. $code.=<<___;
  550. paddd %xmm1,%xmm2
  551. pcmpeqd %xmm5,%xmm1 # compare to 3,2
  552. movdqa %xmm0,`16*($i+0)+112`(%r10)
  553. movdqa %xmm4,%xmm0
  554. paddd %xmm2,%xmm3
  555. pcmpeqd %xmm5,%xmm2 # compare to 5,4
  556. movdqa %xmm1,`16*($i+1)+112`(%r10)
  557. movdqa %xmm4,%xmm1
  558. paddd %xmm3,%xmm0
  559. pcmpeqd %xmm5,%xmm3 # compare to 7,6
  560. movdqa %xmm2,`16*($i+2)+112`(%r10)
  561. movdqa %xmm4,%xmm2
  562. paddd %xmm0,%xmm1
  563. pcmpeqd %xmm5,%xmm0
  564. movdqa %xmm3,`16*($i+3)+112`(%r10)
  565. movdqa %xmm4,%xmm3
  566. ___
  567. }
  568. $code.=<<___; # last iteration can be optimized
  569. paddd %xmm1,%xmm2
  570. pcmpeqd %xmm5,%xmm1
  571. movdqa %xmm0,`16*($i+0)+112`(%r10)
  572. paddd %xmm2,%xmm3
  573. .byte 0x67
  574. pcmpeqd %xmm5,%xmm2
  575. movdqa %xmm1,`16*($i+1)+112`(%r10)
  576. pcmpeqd %xmm5,%xmm3
  577. movdqa %xmm2,`16*($i+2)+112`(%r10)
  578. pand `16*($i+0)-128`($bp),%xmm0 # while it's still in register
  579. pand `16*($i+1)-128`($bp),%xmm1
  580. pand `16*($i+2)-128`($bp),%xmm2
  581. movdqa %xmm3,`16*($i+3)+112`(%r10)
  582. pand `16*($i+3)-128`($bp),%xmm3
  583. por %xmm2,%xmm0
  584. por %xmm3,%xmm1
  585. ___
  586. for($i=0;$i<$STRIDE/16-4;$i+=4) {
  587. $code.=<<___;
  588. movdqa `16*($i+0)-128`($bp),%xmm4
  589. movdqa `16*($i+1)-128`($bp),%xmm5
  590. movdqa `16*($i+2)-128`($bp),%xmm2
  591. pand `16*($i+0)+112`(%r10),%xmm4
  592. movdqa `16*($i+3)-128`($bp),%xmm3
  593. pand `16*($i+1)+112`(%r10),%xmm5
  594. por %xmm4,%xmm0
  595. pand `16*($i+2)+112`(%r10),%xmm2
  596. por %xmm5,%xmm1
  597. pand `16*($i+3)+112`(%r10),%xmm3
  598. por %xmm2,%xmm0
  599. por %xmm3,%xmm1
  600. ___
  601. }
  602. $code.=<<___;
  603. por %xmm1,%xmm0
  604. pshufd \$0x4e,%xmm0,%xmm1
  605. por %xmm1,%xmm0
  606. lea $STRIDE($bp),$bp
  607. movq %xmm0,$m0 # m0=bp[0]
  608. mov %r13,16+8(%rsp) # save end of b[num]
  609. mov $rp, 56+8(%rsp) # save $rp
  610. mov ($n0),$n0 # pull n0[0] value
  611. mov ($ap),%rax
  612. lea ($ap,$num),$ap # end of a[num]
  613. neg $num
  614. mov $n0,$m1
  615. mulq $m0 # ap[0]*bp[0]
  616. mov %rax,$A[0]
  617. mov ($np),%rax
  618. imulq $A[0],$m1 # "tp[0]"*n0
  619. lea 64+8(%rsp),$tp
  620. mov %rdx,$A[1]
  621. mulq $m1 # np[0]*m1
  622. add %rax,$A[0] # discarded
  623. mov 8($ap,$num),%rax
  624. adc \$0,%rdx
  625. mov %rdx,$N[1]
  626. mulq $m0
  627. add %rax,$A[1]
  628. mov 8*1($np),%rax
  629. adc \$0,%rdx
  630. mov %rdx,$A[0]
  631. mulq $m1
  632. add %rax,$N[1]
  633. mov 16($ap,$num),%rax
  634. adc \$0,%rdx
  635. add $A[1],$N[1]
  636. lea 4*8($num),$j # j=4
  637. lea 8*4($np),$np
  638. adc \$0,%rdx
  639. mov $N[1],($tp)
  640. mov %rdx,$N[0]
  641. jmp .L1st4x
  642. .align 32
  643. .L1st4x:
  644. mulq $m0 # ap[j]*bp[0]
  645. add %rax,$A[0]
  646. mov -8*2($np),%rax
  647. lea 32($tp),$tp
  648. adc \$0,%rdx
  649. mov %rdx,$A[1]
  650. mulq $m1 # np[j]*m1
  651. add %rax,$N[0]
  652. mov -8($ap,$j),%rax
  653. adc \$0,%rdx
  654. add $A[0],$N[0] # np[j]*m1+ap[j]*bp[0]
  655. adc \$0,%rdx
  656. mov $N[0],-24($tp) # tp[j-1]
  657. mov %rdx,$N[1]
  658. mulq $m0 # ap[j]*bp[0]
  659. add %rax,$A[1]
  660. mov -8*1($np),%rax
  661. adc \$0,%rdx
  662. mov %rdx,$A[0]
  663. mulq $m1 # np[j]*m1
  664. add %rax,$N[1]
  665. mov ($ap,$j),%rax
  666. adc \$0,%rdx
  667. add $A[1],$N[1] # np[j]*m1+ap[j]*bp[0]
  668. adc \$0,%rdx
  669. mov $N[1],-16($tp) # tp[j-1]
  670. mov %rdx,$N[0]
  671. mulq $m0 # ap[j]*bp[0]
  672. add %rax,$A[0]
  673. mov 8*0($np),%rax
  674. adc \$0,%rdx
  675. mov %rdx,$A[1]
  676. mulq $m1 # np[j]*m1
  677. add %rax,$N[0]
  678. mov 8($ap,$j),%rax
  679. adc \$0,%rdx
  680. add $A[0],$N[0] # np[j]*m1+ap[j]*bp[0]
  681. adc \$0,%rdx
  682. mov $N[0],-8($tp) # tp[j-1]
  683. mov %rdx,$N[1]
  684. mulq $m0 # ap[j]*bp[0]
  685. add %rax,$A[1]
  686. mov 8*1($np),%rax
  687. adc \$0,%rdx
  688. mov %rdx,$A[0]
  689. mulq $m1 # np[j]*m1
  690. add %rax,$N[1]
  691. mov 16($ap,$j),%rax
  692. adc \$0,%rdx
  693. add $A[1],$N[1] # np[j]*m1+ap[j]*bp[0]
  694. lea 8*4($np),$np
  695. adc \$0,%rdx
  696. mov $N[1],($tp) # tp[j-1]
  697. mov %rdx,$N[0]
  698. add \$32,$j # j+=4
  699. jnz .L1st4x
  700. mulq $m0 # ap[j]*bp[0]
  701. add %rax,$A[0]
  702. mov -8*2($np),%rax
  703. lea 32($tp),$tp
  704. adc \$0,%rdx
  705. mov %rdx,$A[1]
  706. mulq $m1 # np[j]*m1
  707. add %rax,$N[0]
  708. mov -8($ap),%rax
  709. adc \$0,%rdx
  710. add $A[0],$N[0] # np[j]*m1+ap[j]*bp[0]
  711. adc \$0,%rdx
  712. mov $N[0],-24($tp) # tp[j-1]
  713. mov %rdx,$N[1]
  714. mulq $m0 # ap[j]*bp[0]
  715. add %rax,$A[1]
  716. mov -8*1($np),%rax
  717. adc \$0,%rdx
  718. mov %rdx,$A[0]
  719. mulq $m1 # np[j]*m1
  720. add %rax,$N[1]
  721. mov ($ap,$num),%rax # ap[0]
  722. adc \$0,%rdx
  723. add $A[1],$N[1] # np[j]*m1+ap[j]*bp[0]
  724. adc \$0,%rdx
  725. mov $N[1],-16($tp) # tp[j-1]
  726. mov %rdx,$N[0]
  727. lea ($np,$num),$np # rewind $np
  728. xor $N[1],$N[1]
  729. add $A[0],$N[0]
  730. adc \$0,$N[1]
  731. mov $N[0],-8($tp)
  732. jmp .Louter4x
  733. .align 32
  734. .Louter4x:
  735. lea 16+128($tp),%rdx # where 256-byte mask is (+size optimization)
  736. pxor %xmm4,%xmm4
  737. pxor %xmm5,%xmm5
  738. ___
  739. for($i=0;$i<$STRIDE/16;$i+=4) {
  740. $code.=<<___;
  741. movdqa `16*($i+0)-128`($bp),%xmm0
  742. movdqa `16*($i+1)-128`($bp),%xmm1
  743. movdqa `16*($i+2)-128`($bp),%xmm2
  744. movdqa `16*($i+3)-128`($bp),%xmm3
  745. pand `16*($i+0)-128`(%rdx),%xmm0
  746. pand `16*($i+1)-128`(%rdx),%xmm1
  747. por %xmm0,%xmm4
  748. pand `16*($i+2)-128`(%rdx),%xmm2
  749. por %xmm1,%xmm5
  750. pand `16*($i+3)-128`(%rdx),%xmm3
  751. por %xmm2,%xmm4
  752. por %xmm3,%xmm5
  753. ___
  754. }
  755. $code.=<<___;
  756. por %xmm5,%xmm4
  757. pshufd \$0x4e,%xmm4,%xmm0
  758. por %xmm4,%xmm0
  759. lea $STRIDE($bp),$bp
  760. movq %xmm0,$m0 # m0=bp[i]
  761. mov ($tp,$num),$A[0]
  762. mov $n0,$m1
  763. mulq $m0 # ap[0]*bp[i]
  764. add %rax,$A[0] # ap[0]*bp[i]+tp[0]
  765. mov ($np),%rax
  766. adc \$0,%rdx
  767. imulq $A[0],$m1 # tp[0]*n0
  768. mov %rdx,$A[1]
  769. mov $N[1],($tp) # store upmost overflow bit
  770. lea ($tp,$num),$tp # rewind $tp
  771. mulq $m1 # np[0]*m1
  772. add %rax,$A[0] # "$N[0]", discarded
  773. mov 8($ap,$num),%rax
  774. adc \$0,%rdx
  775. mov %rdx,$N[1]
  776. mulq $m0 # ap[j]*bp[i]
  777. add %rax,$A[1]
  778. mov 8*1($np),%rax
  779. adc \$0,%rdx
  780. add 8($tp),$A[1] # +tp[1]
  781. adc \$0,%rdx
  782. mov %rdx,$A[0]
  783. mulq $m1 # np[j]*m1
  784. add %rax,$N[1]
  785. mov 16($ap,$num),%rax
  786. adc \$0,%rdx
  787. add $A[1],$N[1] # np[j]*m1+ap[j]*bp[i]+tp[j]
  788. lea 4*8($num),$j # j=4
  789. lea 8*4($np),$np
  790. adc \$0,%rdx
  791. mov %rdx,$N[0]
  792. jmp .Linner4x
  793. .align 32
  794. .Linner4x:
  795. mulq $m0 # ap[j]*bp[i]
  796. add %rax,$A[0]
  797. mov -8*2($np),%rax
  798. adc \$0,%rdx
  799. add 16($tp),$A[0] # ap[j]*bp[i]+tp[j]
  800. lea 32($tp),$tp
  801. adc \$0,%rdx
  802. mov %rdx,$A[1]
  803. mulq $m1 # np[j]*m1
  804. add %rax,$N[0]
  805. mov -8($ap,$j),%rax
  806. adc \$0,%rdx
  807. add $A[0],$N[0]
  808. adc \$0,%rdx
  809. mov $N[1],-32($tp) # tp[j-1]
  810. mov %rdx,$N[1]
  811. mulq $m0 # ap[j]*bp[i]
  812. add %rax,$A[1]
  813. mov -8*1($np),%rax
  814. adc \$0,%rdx
  815. add -8($tp),$A[1]
  816. adc \$0,%rdx
  817. mov %rdx,$A[0]
  818. mulq $m1 # np[j]*m1
  819. add %rax,$N[1]
  820. mov ($ap,$j),%rax
  821. adc \$0,%rdx
  822. add $A[1],$N[1]
  823. adc \$0,%rdx
  824. mov $N[0],-24($tp) # tp[j-1]
  825. mov %rdx,$N[0]
  826. mulq $m0 # ap[j]*bp[i]
  827. add %rax,$A[0]
  828. mov 8*0($np),%rax
  829. adc \$0,%rdx
  830. add ($tp),$A[0] # ap[j]*bp[i]+tp[j]
  831. adc \$0,%rdx
  832. mov %rdx,$A[1]
  833. mulq $m1 # np[j]*m1
  834. add %rax,$N[0]
  835. mov 8($ap,$j),%rax
  836. adc \$0,%rdx
  837. add $A[0],$N[0]
  838. adc \$0,%rdx
  839. mov $N[1],-16($tp) # tp[j-1]
  840. mov %rdx,$N[1]
  841. mulq $m0 # ap[j]*bp[i]
  842. add %rax,$A[1]
  843. mov 8*1($np),%rax
  844. adc \$0,%rdx
  845. add 8($tp),$A[1]
  846. adc \$0,%rdx
  847. mov %rdx,$A[0]
  848. mulq $m1 # np[j]*m1
  849. add %rax,$N[1]
  850. mov 16($ap,$j),%rax
  851. adc \$0,%rdx
  852. add $A[1],$N[1]
  853. lea 8*4($np),$np
  854. adc \$0,%rdx
  855. mov $N[0],-8($tp) # tp[j-1]
  856. mov %rdx,$N[0]
  857. add \$32,$j # j+=4
  858. jnz .Linner4x
  859. mulq $m0 # ap[j]*bp[i]
  860. add %rax,$A[0]
  861. mov -8*2($np),%rax
  862. adc \$0,%rdx
  863. add 16($tp),$A[0] # ap[j]*bp[i]+tp[j]
  864. lea 32($tp),$tp
  865. adc \$0,%rdx
  866. mov %rdx,$A[1]
  867. mulq $m1 # np[j]*m1
  868. add %rax,$N[0]
  869. mov -8($ap),%rax
  870. adc \$0,%rdx
  871. add $A[0],$N[0]
  872. adc \$0,%rdx
  873. mov $N[1],-32($tp) # tp[j-1]
  874. mov %rdx,$N[1]
  875. mulq $m0 # ap[j]*bp[i]
  876. add %rax,$A[1]
  877. mov $m1,%rax
  878. mov -8*1($np),$m1
  879. adc \$0,%rdx
  880. add -8($tp),$A[1]
  881. adc \$0,%rdx
  882. mov %rdx,$A[0]
  883. mulq $m1 # np[j]*m1
  884. add %rax,$N[1]
  885. mov ($ap,$num),%rax # ap[0]
  886. adc \$0,%rdx
  887. add $A[1],$N[1]
  888. adc \$0,%rdx
  889. mov $N[0],-24($tp) # tp[j-1]
  890. mov %rdx,$N[0]
  891. mov $N[1],-16($tp) # tp[j-1]
  892. lea ($np,$num),$np # rewind $np
  893. xor $N[1],$N[1]
  894. add $A[0],$N[0]
  895. adc \$0,$N[1]
  896. add ($tp),$N[0] # pull upmost overflow bit
  897. adc \$0,$N[1] # upmost overflow bit
  898. mov $N[0],-8($tp)
  899. cmp 16+8(%rsp),$bp
  900. jb .Louter4x
  901. ___
  902. if (1) {
  903. $code.=<<___;
  904. xor %rax,%rax
  905. sub $N[0],$m1 # compare top-most words
  906. adc $j,$j # $j is zero
  907. or $j,$N[1]
  908. sub $N[1],%rax # %rax=-$N[1]
  909. lea ($tp,$num),%rbx # tptr in .sqr4x_sub
  910. mov ($np),%r12
  911. lea ($np),%rbp # nptr in .sqr4x_sub
  912. mov %r9,%rcx
  913. sar \$3+2,%rcx
  914. mov 56+8(%rsp),%rdi # rptr in .sqr4x_sub
  915. dec %r12 # so that after 'not' we get -n[0]
  916. xor %r10,%r10
  917. mov 8*1(%rbp),%r13
  918. mov 8*2(%rbp),%r14
  919. mov 8*3(%rbp),%r15
  920. jmp .Lsqr4x_sub_entry
  921. ___
  922. } else {
  923. my @ri=("%rax",$bp,$m0,$m1);
  924. my $rp="%rdx";
  925. $code.=<<___
  926. xor \$1,$N[1]
  927. lea ($tp,$num),$tp # rewind $tp
  928. sar \$5,$num # cf=0
  929. lea ($np,$N[1],8),$np
  930. mov 56+8(%rsp),$rp # restore $rp
  931. jmp .Lsub4x
  932. .align 32
  933. .Lsub4x:
  934. .byte 0x66
  935. mov 8*0($tp),@ri[0]
  936. mov 8*1($tp),@ri[1]
  937. .byte 0x66
  938. sbb 16*0($np),@ri[0]
  939. mov 8*2($tp),@ri[2]
  940. sbb 16*1($np),@ri[1]
  941. mov 3*8($tp),@ri[3]
  942. lea 4*8($tp),$tp
  943. sbb 16*2($np),@ri[2]
  944. mov @ri[0],8*0($rp)
  945. sbb 16*3($np),@ri[3]
  946. lea 16*4($np),$np
  947. mov @ri[1],8*1($rp)
  948. mov @ri[2],8*2($rp)
  949. mov @ri[3],8*3($rp)
  950. lea 8*4($rp),$rp
  951. inc $num
  952. jnz .Lsub4x
  953. ret
  954. ___
  955. }
  956. $code.=<<___;
  957. .cfi_endproc
  958. .size mul4x_internal,.-mul4x_internal
  959. ___
  960. }}}
  961. {{{
  962. ######################################################################
  963. # void bn_power5(
  964. my $rptr="%rdi"; # BN_ULONG *rptr,
  965. my $aptr="%rsi"; # const BN_ULONG *aptr,
  966. my $bptr="%rdx"; # const void *table,
  967. my $nptr="%rcx"; # const BN_ULONG *nptr,
  968. my $n0 ="%r8"; # const BN_ULONG *n0);
  969. my $num ="%r9"; # int num, has to be divisible by 8
  970. # int pwr
  971. my ($i,$j,$tptr)=("%rbp","%rcx",$rptr);
  972. my @A0=("%r10","%r11");
  973. my @A1=("%r12","%r13");
  974. my ($a0,$a1,$ai)=("%r14","%r15","%rbx");
  975. $code.=<<___;
  976. .globl bn_power5
  977. .type bn_power5,\@function,6
  978. .align 32
  979. bn_power5:
  980. .cfi_startproc
  981. mov %rsp,%rax
  982. .cfi_def_cfa_register %rax
  983. ___
  984. $code.=<<___ if ($addx);
  985. mov OPENSSL_ia32cap_P+8(%rip),%r11d
  986. and \$0x80108,%r11d
  987. cmp \$0x80108,%r11d # check for AD*X+BMI2+BMI1
  988. je .Lpowerx5_enter
  989. ___
  990. $code.=<<___;
  991. push %rbx
  992. .cfi_push %rbx
  993. push %rbp
  994. .cfi_push %rbp
  995. push %r12
  996. .cfi_push %r12
  997. push %r13
  998. .cfi_push %r13
  999. push %r14
  1000. .cfi_push %r14
  1001. push %r15
  1002. .cfi_push %r15
  1003. .Lpower5_prologue:
  1004. shl \$3,${num}d # convert $num to bytes
  1005. lea ($num,$num,2),%r10d # 3*$num
  1006. neg $num
  1007. mov ($n0),$n0 # *n0
  1008. ##############################################################
  1009. # Ensure that stack frame doesn't alias with $rptr+3*$num
  1010. # modulo 4096, which covers ret[num], am[num] and n[num]
  1011. # (see bn_exp.c). This is done to allow memory disambiguation
  1012. # logic do its magic. [Extra 256 bytes is for power mask
  1013. # calculated from 7th argument, the index.]
  1014. #
  1015. lea -320(%rsp,$num,2),%r11
  1016. mov %rsp,%rbp
  1017. sub $rptr,%r11
  1018. and \$4095,%r11
  1019. cmp %r11,%r10
  1020. jb .Lpwr_sp_alt
  1021. sub %r11,%rbp # align with $aptr
  1022. lea -320(%rbp,$num,2),%rbp # future alloca(frame+2*num*8+256)
  1023. jmp .Lpwr_sp_done
  1024. .align 32
  1025. .Lpwr_sp_alt:
  1026. lea 4096-320(,$num,2),%r10
  1027. lea -320(%rbp,$num,2),%rbp # future alloca(frame+2*num*8+256)
  1028. sub %r10,%r11
  1029. mov \$0,%r10
  1030. cmovc %r10,%r11
  1031. sub %r11,%rbp
  1032. .Lpwr_sp_done:
  1033. and \$-64,%rbp
  1034. mov %rsp,%r11
  1035. sub %rbp,%r11
  1036. and \$-4096,%r11
  1037. lea (%rbp,%r11),%rsp
  1038. mov (%rsp),%r10
  1039. cmp %rbp,%rsp
  1040. ja .Lpwr_page_walk
  1041. jmp .Lpwr_page_walk_done
  1042. .Lpwr_page_walk:
  1043. lea -4096(%rsp),%rsp
  1044. mov (%rsp),%r10
  1045. cmp %rbp,%rsp
  1046. ja .Lpwr_page_walk
  1047. .Lpwr_page_walk_done:
  1048. mov $num,%r10
  1049. neg $num
  1050. ##############################################################
  1051. # Stack layout
  1052. #
  1053. # +0 saved $num, used in reduction section
  1054. # +8 &t[2*$num], used in reduction section
  1055. # +32 saved *n0
  1056. # +40 saved %rsp
  1057. # +48 t[2*$num]
  1058. #
  1059. mov $n0, 32(%rsp)
  1060. mov %rax, 40(%rsp) # save original %rsp
  1061. .cfi_cfa_expression %rsp+40,deref,+8
  1062. .Lpower5_body:
  1063. movq $rptr,%xmm1 # save $rptr, used in sqr8x
  1064. movq $nptr,%xmm2 # save $nptr
  1065. movq %r10, %xmm3 # -$num, used in sqr8x
  1066. movq $bptr,%xmm4
  1067. call __bn_sqr8x_internal
  1068. call __bn_post4x_internal
  1069. call __bn_sqr8x_internal
  1070. call __bn_post4x_internal
  1071. call __bn_sqr8x_internal
  1072. call __bn_post4x_internal
  1073. call __bn_sqr8x_internal
  1074. call __bn_post4x_internal
  1075. call __bn_sqr8x_internal
  1076. call __bn_post4x_internal
  1077. movq %xmm2,$nptr
  1078. movq %xmm4,$bptr
  1079. mov $aptr,$rptr
  1080. mov 40(%rsp),%rax
  1081. lea 32(%rsp),$n0
  1082. call mul4x_internal
  1083. mov 40(%rsp),%rsi # restore %rsp
  1084. .cfi_def_cfa %rsi,8
  1085. mov \$1,%rax
  1086. mov -48(%rsi),%r15
  1087. .cfi_restore %r15
  1088. mov -40(%rsi),%r14
  1089. .cfi_restore %r14
  1090. mov -32(%rsi),%r13
  1091. .cfi_restore %r13
  1092. mov -24(%rsi),%r12
  1093. .cfi_restore %r12
  1094. mov -16(%rsi),%rbp
  1095. .cfi_restore %rbp
  1096. mov -8(%rsi),%rbx
  1097. .cfi_restore %rbx
  1098. lea (%rsi),%rsp
  1099. .cfi_def_cfa_register %rsp
  1100. .Lpower5_epilogue:
  1101. ret
  1102. .cfi_endproc
  1103. .size bn_power5,.-bn_power5
  1104. .globl bn_sqr8x_internal
  1105. .hidden bn_sqr8x_internal
  1106. .type bn_sqr8x_internal,\@abi-omnipotent
  1107. .align 32
  1108. bn_sqr8x_internal:
  1109. __bn_sqr8x_internal:
  1110. .cfi_startproc
  1111. ##############################################################
  1112. # Squaring part:
  1113. #
  1114. # a) multiply-n-add everything but a[i]*a[i];
  1115. # b) shift result of a) by 1 to the left and accumulate
  1116. # a[i]*a[i] products;
  1117. #
  1118. ##############################################################
  1119. # a[1]a[0]
  1120. # a[2]a[0]
  1121. # a[3]a[0]
  1122. # a[2]a[1]
  1123. # a[4]a[0]
  1124. # a[3]a[1]
  1125. # a[5]a[0]
  1126. # a[4]a[1]
  1127. # a[3]a[2]
  1128. # a[6]a[0]
  1129. # a[5]a[1]
  1130. # a[4]a[2]
  1131. # a[7]a[0]
  1132. # a[6]a[1]
  1133. # a[5]a[2]
  1134. # a[4]a[3]
  1135. # a[7]a[1]
  1136. # a[6]a[2]
  1137. # a[5]a[3]
  1138. # a[7]a[2]
  1139. # a[6]a[3]
  1140. # a[5]a[4]
  1141. # a[7]a[3]
  1142. # a[6]a[4]
  1143. # a[7]a[4]
  1144. # a[6]a[5]
  1145. # a[7]a[5]
  1146. # a[7]a[6]
  1147. # a[1]a[0]
  1148. # a[2]a[0]
  1149. # a[3]a[0]
  1150. # a[4]a[0]
  1151. # a[5]a[0]
  1152. # a[6]a[0]
  1153. # a[7]a[0]
  1154. # a[2]a[1]
  1155. # a[3]a[1]
  1156. # a[4]a[1]
  1157. # a[5]a[1]
  1158. # a[6]a[1]
  1159. # a[7]a[1]
  1160. # a[3]a[2]
  1161. # a[4]a[2]
  1162. # a[5]a[2]
  1163. # a[6]a[2]
  1164. # a[7]a[2]
  1165. # a[4]a[3]
  1166. # a[5]a[3]
  1167. # a[6]a[3]
  1168. # a[7]a[3]
  1169. # a[5]a[4]
  1170. # a[6]a[4]
  1171. # a[7]a[4]
  1172. # a[6]a[5]
  1173. # a[7]a[5]
  1174. # a[7]a[6]
  1175. # a[0]a[0]
  1176. # a[1]a[1]
  1177. # a[2]a[2]
  1178. # a[3]a[3]
  1179. # a[4]a[4]
  1180. # a[5]a[5]
  1181. # a[6]a[6]
  1182. # a[7]a[7]
  1183. lea 32(%r10),$i # $i=-($num-32)
  1184. lea ($aptr,$num),$aptr # end of a[] buffer, ($aptr,$i)=&ap[2]
  1185. mov $num,$j # $j=$num
  1186. # comments apply to $num==8 case
  1187. mov -32($aptr,$i),$a0 # a[0]
  1188. lea 48+8(%rsp,$num,2),$tptr # end of tp[] buffer, &tp[2*$num]
  1189. mov -24($aptr,$i),%rax # a[1]
  1190. lea -32($tptr,$i),$tptr # end of tp[] window, &tp[2*$num-"$i"]
  1191. mov -16($aptr,$i),$ai # a[2]
  1192. mov %rax,$a1
  1193. mul $a0 # a[1]*a[0]
  1194. mov %rax,$A0[0] # a[1]*a[0]
  1195. mov $ai,%rax # a[2]
  1196. mov %rdx,$A0[1]
  1197. mov $A0[0],-24($tptr,$i) # t[1]
  1198. mul $a0 # a[2]*a[0]
  1199. add %rax,$A0[1]
  1200. mov $ai,%rax
  1201. adc \$0,%rdx
  1202. mov $A0[1],-16($tptr,$i) # t[2]
  1203. mov %rdx,$A0[0]
  1204. mov -8($aptr,$i),$ai # a[3]
  1205. mul $a1 # a[2]*a[1]
  1206. mov %rax,$A1[0] # a[2]*a[1]+t[3]
  1207. mov $ai,%rax
  1208. mov %rdx,$A1[1]
  1209. lea ($i),$j
  1210. mul $a0 # a[3]*a[0]
  1211. add %rax,$A0[0] # a[3]*a[0]+a[2]*a[1]+t[3]
  1212. mov $ai,%rax
  1213. mov %rdx,$A0[1]
  1214. adc \$0,$A0[1]
  1215. add $A1[0],$A0[0]
  1216. adc \$0,$A0[1]
  1217. mov $A0[0],-8($tptr,$j) # t[3]
  1218. jmp .Lsqr4x_1st
  1219. .align 32
  1220. .Lsqr4x_1st:
  1221. mov ($aptr,$j),$ai # a[4]
  1222. mul $a1 # a[3]*a[1]
  1223. add %rax,$A1[1] # a[3]*a[1]+t[4]
  1224. mov $ai,%rax
  1225. mov %rdx,$A1[0]
  1226. adc \$0,$A1[0]
  1227. mul $a0 # a[4]*a[0]
  1228. add %rax,$A0[1] # a[4]*a[0]+a[3]*a[1]+t[4]
  1229. mov $ai,%rax # a[3]
  1230. mov 8($aptr,$j),$ai # a[5]
  1231. mov %rdx,$A0[0]
  1232. adc \$0,$A0[0]
  1233. add $A1[1],$A0[1]
  1234. adc \$0,$A0[0]
  1235. mul $a1 # a[4]*a[3]
  1236. add %rax,$A1[0] # a[4]*a[3]+t[5]
  1237. mov $ai,%rax
  1238. mov $A0[1],($tptr,$j) # t[4]
  1239. mov %rdx,$A1[1]
  1240. adc \$0,$A1[1]
  1241. mul $a0 # a[5]*a[2]
  1242. add %rax,$A0[0] # a[5]*a[2]+a[4]*a[3]+t[5]
  1243. mov $ai,%rax
  1244. mov 16($aptr,$j),$ai # a[6]
  1245. mov %rdx,$A0[1]
  1246. adc \$0,$A0[1]
  1247. add $A1[0],$A0[0]
  1248. adc \$0,$A0[1]
  1249. mul $a1 # a[5]*a[3]
  1250. add %rax,$A1[1] # a[5]*a[3]+t[6]
  1251. mov $ai,%rax
  1252. mov $A0[0],8($tptr,$j) # t[5]
  1253. mov %rdx,$A1[0]
  1254. adc \$0,$A1[0]
  1255. mul $a0 # a[6]*a[2]
  1256. add %rax,$A0[1] # a[6]*a[2]+a[5]*a[3]+t[6]
  1257. mov $ai,%rax # a[3]
  1258. mov 24($aptr,$j),$ai # a[7]
  1259. mov %rdx,$A0[0]
  1260. adc \$0,$A0[0]
  1261. add $A1[1],$A0[1]
  1262. adc \$0,$A0[0]
  1263. mul $a1 # a[6]*a[5]
  1264. add %rax,$A1[0] # a[6]*a[5]+t[7]
  1265. mov $ai,%rax
  1266. mov $A0[1],16($tptr,$j) # t[6]
  1267. mov %rdx,$A1[1]
  1268. adc \$0,$A1[1]
  1269. lea 32($j),$j
  1270. mul $a0 # a[7]*a[4]
  1271. add %rax,$A0[0] # a[7]*a[4]+a[6]*a[5]+t[6]
  1272. mov $ai,%rax
  1273. mov %rdx,$A0[1]
  1274. adc \$0,$A0[1]
  1275. add $A1[0],$A0[0]
  1276. adc \$0,$A0[1]
  1277. mov $A0[0],-8($tptr,$j) # t[7]
  1278. cmp \$0,$j
  1279. jne .Lsqr4x_1st
  1280. mul $a1 # a[7]*a[5]
  1281. add %rax,$A1[1]
  1282. lea 16($i),$i
  1283. adc \$0,%rdx
  1284. add $A0[1],$A1[1]
  1285. adc \$0,%rdx
  1286. mov $A1[1],($tptr) # t[8]
  1287. mov %rdx,$A1[0]
  1288. mov %rdx,8($tptr) # t[9]
  1289. jmp .Lsqr4x_outer
  1290. .align 32
  1291. .Lsqr4x_outer: # comments apply to $num==6 case
  1292. mov -32($aptr,$i),$a0 # a[0]
  1293. lea 48+8(%rsp,$num,2),$tptr # end of tp[] buffer, &tp[2*$num]
  1294. mov -24($aptr,$i),%rax # a[1]
  1295. lea -32($tptr,$i),$tptr # end of tp[] window, &tp[2*$num-"$i"]
  1296. mov -16($aptr,$i),$ai # a[2]
  1297. mov %rax,$a1
  1298. mul $a0 # a[1]*a[0]
  1299. mov -24($tptr,$i),$A0[0] # t[1]
  1300. add %rax,$A0[0] # a[1]*a[0]+t[1]
  1301. mov $ai,%rax # a[2]
  1302. adc \$0,%rdx
  1303. mov $A0[0],-24($tptr,$i) # t[1]
  1304. mov %rdx,$A0[1]
  1305. mul $a0 # a[2]*a[0]
  1306. add %rax,$A0[1]
  1307. mov $ai,%rax
  1308. adc \$0,%rdx
  1309. add -16($tptr,$i),$A0[1] # a[2]*a[0]+t[2]
  1310. mov %rdx,$A0[0]
  1311. adc \$0,$A0[0]
  1312. mov $A0[1],-16($tptr,$i) # t[2]
  1313. xor $A1[0],$A1[0]
  1314. mov -8($aptr,$i),$ai # a[3]
  1315. mul $a1 # a[2]*a[1]
  1316. add %rax,$A1[0] # a[2]*a[1]+t[3]
  1317. mov $ai,%rax
  1318. adc \$0,%rdx
  1319. add -8($tptr,$i),$A1[0]
  1320. mov %rdx,$A1[1]
  1321. adc \$0,$A1[1]
  1322. mul $a0 # a[3]*a[0]
  1323. add %rax,$A0[0] # a[3]*a[0]+a[2]*a[1]+t[3]
  1324. mov $ai,%rax
  1325. adc \$0,%rdx
  1326. add $A1[0],$A0[0]
  1327. mov %rdx,$A0[1]
  1328. adc \$0,$A0[1]
  1329. mov $A0[0],-8($tptr,$i) # t[3]
  1330. lea ($i),$j
  1331. jmp .Lsqr4x_inner
  1332. .align 32
  1333. .Lsqr4x_inner:
  1334. mov ($aptr,$j),$ai # a[4]
  1335. mul $a1 # a[3]*a[1]
  1336. add %rax,$A1[1] # a[3]*a[1]+t[4]
  1337. mov $ai,%rax
  1338. mov %rdx,$A1[0]
  1339. adc \$0,$A1[0]
  1340. add ($tptr,$j),$A1[1]
  1341. adc \$0,$A1[0]
  1342. .byte 0x67
  1343. mul $a0 # a[4]*a[0]
  1344. add %rax,$A0[1] # a[4]*a[0]+a[3]*a[1]+t[4]
  1345. mov $ai,%rax # a[3]
  1346. mov 8($aptr,$j),$ai # a[5]
  1347. mov %rdx,$A0[0]
  1348. adc \$0,$A0[0]
  1349. add $A1[1],$A0[1]
  1350. adc \$0,$A0[0]
  1351. mul $a1 # a[4]*a[3]
  1352. add %rax,$A1[0] # a[4]*a[3]+t[5]
  1353. mov $A0[1],($tptr,$j) # t[4]
  1354. mov $ai,%rax
  1355. mov %rdx,$A1[1]
  1356. adc \$0,$A1[1]
  1357. add 8($tptr,$j),$A1[0]
  1358. lea 16($j),$j # j++
  1359. adc \$0,$A1[1]
  1360. mul $a0 # a[5]*a[2]
  1361. add %rax,$A0[0] # a[5]*a[2]+a[4]*a[3]+t[5]
  1362. mov $ai,%rax
  1363. adc \$0,%rdx
  1364. add $A1[0],$A0[0]
  1365. mov %rdx,$A0[1]
  1366. adc \$0,$A0[1]
  1367. mov $A0[0],-8($tptr,$j) # t[5], "preloaded t[1]" below
  1368. cmp \$0,$j
  1369. jne .Lsqr4x_inner
  1370. .byte 0x67
  1371. mul $a1 # a[5]*a[3]
  1372. add %rax,$A1[1]
  1373. adc \$0,%rdx
  1374. add $A0[1],$A1[1]
  1375. adc \$0,%rdx
  1376. mov $A1[1],($tptr) # t[6], "preloaded t[2]" below
  1377. mov %rdx,$A1[0]
  1378. mov %rdx,8($tptr) # t[7], "preloaded t[3]" below
  1379. add \$16,$i
  1380. jnz .Lsqr4x_outer
  1381. # comments apply to $num==4 case
  1382. mov -32($aptr),$a0 # a[0]
  1383. lea 48+8(%rsp,$num,2),$tptr # end of tp[] buffer, &tp[2*$num]
  1384. mov -24($aptr),%rax # a[1]
  1385. lea -32($tptr,$i),$tptr # end of tp[] window, &tp[2*$num-"$i"]
  1386. mov -16($aptr),$ai # a[2]
  1387. mov %rax,$a1
  1388. mul $a0 # a[1]*a[0]
  1389. add %rax,$A0[0] # a[1]*a[0]+t[1], preloaded t[1]
  1390. mov $ai,%rax # a[2]
  1391. mov %rdx,$A0[1]
  1392. adc \$0,$A0[1]
  1393. mul $a0 # a[2]*a[0]
  1394. add %rax,$A0[1]
  1395. mov $ai,%rax
  1396. mov $A0[0],-24($tptr) # t[1]
  1397. mov %rdx,$A0[0]
  1398. adc \$0,$A0[0]
  1399. add $A1[1],$A0[1] # a[2]*a[0]+t[2], preloaded t[2]
  1400. mov -8($aptr),$ai # a[3]
  1401. adc \$0,$A0[0]
  1402. mul $a1 # a[2]*a[1]
  1403. add %rax,$A1[0] # a[2]*a[1]+t[3], preloaded t[3]
  1404. mov $ai,%rax
  1405. mov $A0[1],-16($tptr) # t[2]
  1406. mov %rdx,$A1[1]
  1407. adc \$0,$A1[1]
  1408. mul $a0 # a[3]*a[0]
  1409. add %rax,$A0[0] # a[3]*a[0]+a[2]*a[1]+t[3]
  1410. mov $ai,%rax
  1411. mov %rdx,$A0[1]
  1412. adc \$0,$A0[1]
  1413. add $A1[0],$A0[0]
  1414. adc \$0,$A0[1]
  1415. mov $A0[0],-8($tptr) # t[3]
  1416. mul $a1 # a[3]*a[1]
  1417. add %rax,$A1[1]
  1418. mov -16($aptr),%rax # a[2]
  1419. adc \$0,%rdx
  1420. add $A0[1],$A1[1]
  1421. adc \$0,%rdx
  1422. mov $A1[1],($tptr) # t[4]
  1423. mov %rdx,$A1[0]
  1424. mov %rdx,8($tptr) # t[5]
  1425. mul $ai # a[2]*a[3]
  1426. ___
  1427. {
  1428. my ($shift,$carry)=($a0,$a1);
  1429. my @S=(@A1,$ai,$n0);
  1430. $code.=<<___;
  1431. add \$16,$i
  1432. xor $shift,$shift
  1433. sub $num,$i # $i=16-$num
  1434. xor $carry,$carry
  1435. add $A1[0],%rax # t[5]
  1436. adc \$0,%rdx
  1437. mov %rax,8($tptr) # t[5]
  1438. mov %rdx,16($tptr) # t[6]
  1439. mov $carry,24($tptr) # t[7]
  1440. mov -16($aptr,$i),%rax # a[0]
  1441. lea 48+8(%rsp),$tptr
  1442. xor $A0[0],$A0[0] # t[0]
  1443. mov 8($tptr),$A0[1] # t[1]
  1444. lea ($shift,$A0[0],2),$S[0] # t[2*i]<<1 | shift
  1445. shr \$63,$A0[0]
  1446. lea ($j,$A0[1],2),$S[1] # t[2*i+1]<<1 |
  1447. shr \$63,$A0[1]
  1448. or $A0[0],$S[1] # | t[2*i]>>63
  1449. mov 16($tptr),$A0[0] # t[2*i+2] # prefetch
  1450. mov $A0[1],$shift # shift=t[2*i+1]>>63
  1451. mul %rax # a[i]*a[i]
  1452. neg $carry # mov $carry,cf
  1453. mov 24($tptr),$A0[1] # t[2*i+2+1] # prefetch
  1454. adc %rax,$S[0]
  1455. mov -8($aptr,$i),%rax # a[i+1] # prefetch
  1456. mov $S[0],($tptr)
  1457. adc %rdx,$S[1]
  1458. lea ($shift,$A0[0],2),$S[2] # t[2*i]<<1 | shift
  1459. mov $S[1],8($tptr)
  1460. sbb $carry,$carry # mov cf,$carry
  1461. shr \$63,$A0[0]
  1462. lea ($j,$A0[1],2),$S[3] # t[2*i+1]<<1 |
  1463. shr \$63,$A0[1]
  1464. or $A0[0],$S[3] # | t[2*i]>>63
  1465. mov 32($tptr),$A0[0] # t[2*i+2] # prefetch
  1466. mov $A0[1],$shift # shift=t[2*i+1]>>63
  1467. mul %rax # a[i]*a[i]
  1468. neg $carry # mov $carry,cf
  1469. mov 40($tptr),$A0[1] # t[2*i+2+1] # prefetch
  1470. adc %rax,$S[2]
  1471. mov 0($aptr,$i),%rax # a[i+1] # prefetch
  1472. mov $S[2],16($tptr)
  1473. adc %rdx,$S[3]
  1474. lea 16($i),$i
  1475. mov $S[3],24($tptr)
  1476. sbb $carry,$carry # mov cf,$carry
  1477. lea 64($tptr),$tptr
  1478. jmp .Lsqr4x_shift_n_add
  1479. .align 32
  1480. .Lsqr4x_shift_n_add:
  1481. lea ($shift,$A0[0],2),$S[0] # t[2*i]<<1 | shift
  1482. shr \$63,$A0[0]
  1483. lea ($j,$A0[1],2),$S[1] # t[2*i+1]<<1 |
  1484. shr \$63,$A0[1]
  1485. or $A0[0],$S[1] # | t[2*i]>>63
  1486. mov -16($tptr),$A0[0] # t[2*i+2] # prefetch
  1487. mov $A0[1],$shift # shift=t[2*i+1]>>63
  1488. mul %rax # a[i]*a[i]
  1489. neg $carry # mov $carry,cf
  1490. mov -8($tptr),$A0[1] # t[2*i+2+1] # prefetch
  1491. adc %rax,$S[0]
  1492. mov -8($aptr,$i),%rax # a[i+1] # prefetch
  1493. mov $S[0],-32($tptr)
  1494. adc %rdx,$S[1]
  1495. lea ($shift,$A0[0],2),$S[2] # t[2*i]<<1 | shift
  1496. mov $S[1],-24($tptr)
  1497. sbb $carry,$carry # mov cf,$carry
  1498. shr \$63,$A0[0]
  1499. lea ($j,$A0[1],2),$S[3] # t[2*i+1]<<1 |
  1500. shr \$63,$A0[1]
  1501. or $A0[0],$S[3] # | t[2*i]>>63
  1502. mov 0($tptr),$A0[0] # t[2*i+2] # prefetch
  1503. mov $A0[1],$shift # shift=t[2*i+1]>>63
  1504. mul %rax # a[i]*a[i]
  1505. neg $carry # mov $carry,cf
  1506. mov 8($tptr),$A0[1] # t[2*i+2+1] # prefetch
  1507. adc %rax,$S[2]
  1508. mov 0($aptr,$i),%rax # a[i+1] # prefetch
  1509. mov $S[2],-16($tptr)
  1510. adc %rdx,$S[3]
  1511. lea ($shift,$A0[0],2),$S[0] # t[2*i]<<1 | shift
  1512. mov $S[3],-8($tptr)
  1513. sbb $carry,$carry # mov cf,$carry
  1514. shr \$63,$A0[0]
  1515. lea ($j,$A0[1],2),$S[1] # t[2*i+1]<<1 |
  1516. shr \$63,$A0[1]
  1517. or $A0[0],$S[1] # | t[2*i]>>63
  1518. mov 16($tptr),$A0[0] # t[2*i+2] # prefetch
  1519. mov $A0[1],$shift # shift=t[2*i+1]>>63
  1520. mul %rax # a[i]*a[i]
  1521. neg $carry # mov $carry,cf
  1522. mov 24($tptr),$A0[1] # t[2*i+2+1] # prefetch
  1523. adc %rax,$S[0]
  1524. mov 8($aptr,$i),%rax # a[i+1] # prefetch
  1525. mov $S[0],0($tptr)
  1526. adc %rdx,$S[1]
  1527. lea ($shift,$A0[0],2),$S[2] # t[2*i]<<1 | shift
  1528. mov $S[1],8($tptr)
  1529. sbb $carry,$carry # mov cf,$carry
  1530. shr \$63,$A0[0]
  1531. lea ($j,$A0[1],2),$S[3] # t[2*i+1]<<1 |
  1532. shr \$63,$A0[1]
  1533. or $A0[0],$S[3] # | t[2*i]>>63
  1534. mov 32($tptr),$A0[0] # t[2*i+2] # prefetch
  1535. mov $A0[1],$shift # shift=t[2*i+1]>>63
  1536. mul %rax # a[i]*a[i]
  1537. neg $carry # mov $carry,cf
  1538. mov 40($tptr),$A0[1] # t[2*i+2+1] # prefetch
  1539. adc %rax,$S[2]
  1540. mov 16($aptr,$i),%rax # a[i+1] # prefetch
  1541. mov $S[2],16($tptr)
  1542. adc %rdx,$S[3]
  1543. mov $S[3],24($tptr)
  1544. sbb $carry,$carry # mov cf,$carry
  1545. lea 64($tptr),$tptr
  1546. add \$32,$i
  1547. jnz .Lsqr4x_shift_n_add
  1548. lea ($shift,$A0[0],2),$S[0] # t[2*i]<<1 | shift
  1549. .byte 0x67
  1550. shr \$63,$A0[0]
  1551. lea ($j,$A0[1],2),$S[1] # t[2*i+1]<<1 |
  1552. shr \$63,$A0[1]
  1553. or $A0[0],$S[1] # | t[2*i]>>63
  1554. mov -16($tptr),$A0[0] # t[2*i+2] # prefetch
  1555. mov $A0[1],$shift # shift=t[2*i+1]>>63
  1556. mul %rax # a[i]*a[i]
  1557. neg $carry # mov $carry,cf
  1558. mov -8($tptr),$A0[1] # t[2*i+2+1] # prefetch
  1559. adc %rax,$S[0]
  1560. mov -8($aptr),%rax # a[i+1] # prefetch
  1561. mov $S[0],-32($tptr)
  1562. adc %rdx,$S[1]
  1563. lea ($shift,$A0[0],2),$S[2] # t[2*i]<<1|shift
  1564. mov $S[1],-24($tptr)
  1565. sbb $carry,$carry # mov cf,$carry
  1566. shr \$63,$A0[0]
  1567. lea ($j,$A0[1],2),$S[3] # t[2*i+1]<<1 |
  1568. shr \$63,$A0[1]
  1569. or $A0[0],$S[3] # | t[2*i]>>63
  1570. mul %rax # a[i]*a[i]
  1571. neg $carry # mov $carry,cf
  1572. adc %rax,$S[2]
  1573. adc %rdx,$S[3]
  1574. mov $S[2],-16($tptr)
  1575. mov $S[3],-8($tptr)
  1576. ___
  1577. }
  1578. ######################################################################
  1579. # Montgomery reduction part, "word-by-word" algorithm.
  1580. #
  1581. # This new path is inspired by multiple submissions from Intel, by
  1582. # Shay Gueron, Vlad Krasnov, Erdinc Ozturk, James Guilford,
  1583. # Vinodh Gopal...
  1584. {
  1585. my ($nptr,$tptr,$carry,$m0)=("%rbp","%rdi","%rsi","%rbx");
  1586. $code.=<<___;
  1587. movq %xmm2,$nptr
  1588. __bn_sqr8x_reduction:
  1589. xor %rax,%rax
  1590. lea ($nptr,$num),%rcx # end of n[]
  1591. lea 48+8(%rsp,$num,2),%rdx # end of t[] buffer
  1592. mov %rcx,0+8(%rsp)
  1593. lea 48+8(%rsp,$num),$tptr # end of initial t[] window
  1594. mov %rdx,8+8(%rsp)
  1595. neg $num
  1596. jmp .L8x_reduction_loop
  1597. .align 32
  1598. .L8x_reduction_loop:
  1599. lea ($tptr,$num),$tptr # start of current t[] window
  1600. .byte 0x66
  1601. mov 8*0($tptr),$m0
  1602. mov 8*1($tptr),%r9
  1603. mov 8*2($tptr),%r10
  1604. mov 8*3($tptr),%r11
  1605. mov 8*4($tptr),%r12
  1606. mov 8*5($tptr),%r13
  1607. mov 8*6($tptr),%r14
  1608. mov 8*7($tptr),%r15
  1609. mov %rax,(%rdx) # store top-most carry bit
  1610. lea 8*8($tptr),$tptr
  1611. .byte 0x67
  1612. mov $m0,%r8
  1613. imulq 32+8(%rsp),$m0 # n0*a[0]
  1614. mov 8*0($nptr),%rax # n[0]
  1615. mov \$8,%ecx
  1616. jmp .L8x_reduce
  1617. .align 32
  1618. .L8x_reduce:
  1619. mulq $m0
  1620. mov 8*1($nptr),%rax # n[1]
  1621. neg %r8
  1622. mov %rdx,%r8
  1623. adc \$0,%r8
  1624. mulq $m0
  1625. add %rax,%r9
  1626. mov 8*2($nptr),%rax
  1627. adc \$0,%rdx
  1628. add %r9,%r8
  1629. mov $m0,48-8+8(%rsp,%rcx,8) # put aside n0*a[i]
  1630. mov %rdx,%r9
  1631. adc \$0,%r9
  1632. mulq $m0
  1633. add %rax,%r10
  1634. mov 8*3($nptr),%rax
  1635. adc \$0,%rdx
  1636. add %r10,%r9
  1637. mov 32+8(%rsp),$carry # pull n0, borrow $carry
  1638. mov %rdx,%r10
  1639. adc \$0,%r10
  1640. mulq $m0
  1641. add %rax,%r11
  1642. mov 8*4($nptr),%rax
  1643. adc \$0,%rdx
  1644. imulq %r8,$carry # modulo-scheduled
  1645. add %r11,%r10
  1646. mov %rdx,%r11
  1647. adc \$0,%r11
  1648. mulq $m0
  1649. add %rax,%r12
  1650. mov 8*5($nptr),%rax
  1651. adc \$0,%rdx
  1652. add %r12,%r11
  1653. mov %rdx,%r12
  1654. adc \$0,%r12
  1655. mulq $m0
  1656. add %rax,%r13
  1657. mov 8*6($nptr),%rax
  1658. adc \$0,%rdx
  1659. add %r13,%r12
  1660. mov %rdx,%r13
  1661. adc \$0,%r13
  1662. mulq $m0
  1663. add %rax,%r14
  1664. mov 8*7($nptr),%rax
  1665. adc \$0,%rdx
  1666. add %r14,%r13
  1667. mov %rdx,%r14
  1668. adc \$0,%r14
  1669. mulq $m0
  1670. mov $carry,$m0 # n0*a[i]
  1671. add %rax,%r15
  1672. mov 8*0($nptr),%rax # n[0]
  1673. adc \$0,%rdx
  1674. add %r15,%r14
  1675. mov %rdx,%r15
  1676. adc \$0,%r15
  1677. dec %ecx
  1678. jnz .L8x_reduce
  1679. lea 8*8($nptr),$nptr
  1680. xor %rax,%rax
  1681. mov 8+8(%rsp),%rdx # pull end of t[]
  1682. cmp 0+8(%rsp),$nptr # end of n[]?
  1683. jae .L8x_no_tail
  1684. .byte 0x66
  1685. add 8*0($tptr),%r8
  1686. adc 8*1($tptr),%r9
  1687. adc 8*2($tptr),%r10
  1688. adc 8*3($tptr),%r11
  1689. adc 8*4($tptr),%r12
  1690. adc 8*5($tptr),%r13
  1691. adc 8*6($tptr),%r14
  1692. adc 8*7($tptr),%r15
  1693. sbb $carry,$carry # top carry
  1694. mov 48+56+8(%rsp),$m0 # pull n0*a[0]
  1695. mov \$8,%ecx
  1696. mov 8*0($nptr),%rax
  1697. jmp .L8x_tail
  1698. .align 32
  1699. .L8x_tail:
  1700. mulq $m0
  1701. add %rax,%r8
  1702. mov 8*1($nptr),%rax
  1703. mov %r8,($tptr) # save result
  1704. mov %rdx,%r8
  1705. adc \$0,%r8
  1706. mulq $m0
  1707. add %rax,%r9
  1708. mov 8*2($nptr),%rax
  1709. adc \$0,%rdx
  1710. add %r9,%r8
  1711. lea 8($tptr),$tptr # $tptr++
  1712. mov %rdx,%r9
  1713. adc \$0,%r9
  1714. mulq $m0
  1715. add %rax,%r10
  1716. mov 8*3($nptr),%rax
  1717. adc \$0,%rdx
  1718. add %r10,%r9
  1719. mov %rdx,%r10
  1720. adc \$0,%r10
  1721. mulq $m0
  1722. add %rax,%r11
  1723. mov 8*4($nptr),%rax
  1724. adc \$0,%rdx
  1725. add %r11,%r10
  1726. mov %rdx,%r11
  1727. adc \$0,%r11
  1728. mulq $m0
  1729. add %rax,%r12
  1730. mov 8*5($nptr),%rax
  1731. adc \$0,%rdx
  1732. add %r12,%r11
  1733. mov %rdx,%r12
  1734. adc \$0,%r12
  1735. mulq $m0
  1736. add %rax,%r13
  1737. mov 8*6($nptr),%rax
  1738. adc \$0,%rdx
  1739. add %r13,%r12
  1740. mov %rdx,%r13
  1741. adc \$0,%r13
  1742. mulq $m0
  1743. add %rax,%r14
  1744. mov 8*7($nptr),%rax
  1745. adc \$0,%rdx
  1746. add %r14,%r13
  1747. mov %rdx,%r14
  1748. adc \$0,%r14
  1749. mulq $m0
  1750. mov 48-16+8(%rsp,%rcx,8),$m0# pull n0*a[i]
  1751. add %rax,%r15
  1752. adc \$0,%rdx
  1753. add %r15,%r14
  1754. mov 8*0($nptr),%rax # pull n[0]
  1755. mov %rdx,%r15
  1756. adc \$0,%r15
  1757. dec %ecx
  1758. jnz .L8x_tail
  1759. lea 8*8($nptr),$nptr
  1760. mov 8+8(%rsp),%rdx # pull end of t[]
  1761. cmp 0+8(%rsp),$nptr # end of n[]?
  1762. jae .L8x_tail_done # break out of loop
  1763. mov 48+56+8(%rsp),$m0 # pull n0*a[0]
  1764. neg $carry
  1765. mov 8*0($nptr),%rax # pull n[0]
  1766. adc 8*0($tptr),%r8
  1767. adc 8*1($tptr),%r9
  1768. adc 8*2($tptr),%r10
  1769. adc 8*3($tptr),%r11
  1770. adc 8*4($tptr),%r12
  1771. adc 8*5($tptr),%r13
  1772. adc 8*6($tptr),%r14
  1773. adc 8*7($tptr),%r15
  1774. sbb $carry,$carry # top carry
  1775. mov \$8,%ecx
  1776. jmp .L8x_tail
  1777. .align 32
  1778. .L8x_tail_done:
  1779. xor %rax,%rax
  1780. add (%rdx),%r8 # can this overflow?
  1781. adc \$0,%r9
  1782. adc \$0,%r10
  1783. adc \$0,%r11
  1784. adc \$0,%r12
  1785. adc \$0,%r13
  1786. adc \$0,%r14
  1787. adc \$0,%r15
  1788. adc \$0,%rax
  1789. neg $carry
  1790. .L8x_no_tail:
  1791. adc 8*0($tptr),%r8
  1792. adc 8*1($tptr),%r9
  1793. adc 8*2($tptr),%r10
  1794. adc 8*3($tptr),%r11
  1795. adc 8*4($tptr),%r12
  1796. adc 8*5($tptr),%r13
  1797. adc 8*6($tptr),%r14
  1798. adc 8*7($tptr),%r15
  1799. adc \$0,%rax # top-most carry
  1800. mov -8($nptr),%rcx # np[num-1]
  1801. xor $carry,$carry
  1802. movq %xmm2,$nptr # restore $nptr
  1803. mov %r8,8*0($tptr) # store top 512 bits
  1804. mov %r9,8*1($tptr)
  1805. movq %xmm3,$num # $num is %r9, can't be moved upwards
  1806. mov %r10,8*2($tptr)
  1807. mov %r11,8*3($tptr)
  1808. mov %r12,8*4($tptr)
  1809. mov %r13,8*5($tptr)
  1810. mov %r14,8*6($tptr)
  1811. mov %r15,8*7($tptr)
  1812. lea 8*8($tptr),$tptr
  1813. cmp %rdx,$tptr # end of t[]?
  1814. jb .L8x_reduction_loop
  1815. ret
  1816. .cfi_endproc
  1817. .size bn_sqr8x_internal,.-bn_sqr8x_internal
  1818. ___
  1819. }
  1820. ##############################################################
  1821. # Post-condition, 4x unrolled
  1822. #
  1823. {
  1824. my ($tptr,$nptr)=("%rbx","%rbp");
  1825. $code.=<<___;
  1826. .type __bn_post4x_internal,\@abi-omnipotent
  1827. .align 32
  1828. __bn_post4x_internal:
  1829. .cfi_startproc
  1830. mov 8*0($nptr),%r12
  1831. lea (%rdi,$num),$tptr # %rdi was $tptr above
  1832. mov $num,%rcx
  1833. movq %xmm1,$rptr # restore $rptr
  1834. neg %rax
  1835. movq %xmm1,$aptr # prepare for back-to-back call
  1836. sar \$3+2,%rcx
  1837. dec %r12 # so that after 'not' we get -n[0]
  1838. xor %r10,%r10
  1839. mov 8*1($nptr),%r13
  1840. mov 8*2($nptr),%r14
  1841. mov 8*3($nptr),%r15
  1842. jmp .Lsqr4x_sub_entry
  1843. .align 16
  1844. .Lsqr4x_sub:
  1845. mov 8*0($nptr),%r12
  1846. mov 8*1($nptr),%r13
  1847. mov 8*2($nptr),%r14
  1848. mov 8*3($nptr),%r15
  1849. .Lsqr4x_sub_entry:
  1850. lea 8*4($nptr),$nptr
  1851. not %r12
  1852. not %r13
  1853. not %r14
  1854. not %r15
  1855. and %rax,%r12
  1856. and %rax,%r13
  1857. and %rax,%r14
  1858. and %rax,%r15
  1859. neg %r10 # mov %r10,%cf
  1860. adc 8*0($tptr),%r12
  1861. adc 8*1($tptr),%r13
  1862. adc 8*2($tptr),%r14
  1863. adc 8*3($tptr),%r15
  1864. mov %r12,8*0($rptr)
  1865. lea 8*4($tptr),$tptr
  1866. mov %r13,8*1($rptr)
  1867. sbb %r10,%r10 # mov %cf,%r10
  1868. mov %r14,8*2($rptr)
  1869. mov %r15,8*3($rptr)
  1870. lea 8*4($rptr),$rptr
  1871. inc %rcx # pass %cf
  1872. jnz .Lsqr4x_sub
  1873. mov $num,%r10 # prepare for back-to-back call
  1874. neg $num # restore $num
  1875. ret
  1876. .cfi_endproc
  1877. .size __bn_post4x_internal,.-__bn_post4x_internal
  1878. ___
  1879. }
  1880. }}}
  1881. if ($addx) {{{
  1882. my $bp="%rdx"; # restore original value
  1883. $code.=<<___;
  1884. .type bn_mulx4x_mont_gather5,\@function,6
  1885. .align 32
  1886. bn_mulx4x_mont_gather5:
  1887. .cfi_startproc
  1888. mov %rsp,%rax
  1889. .cfi_def_cfa_register %rax
  1890. .Lmulx4x_enter:
  1891. push %rbx
  1892. .cfi_push %rbx
  1893. push %rbp
  1894. .cfi_push %rbp
  1895. push %r12
  1896. .cfi_push %r12
  1897. push %r13
  1898. .cfi_push %r13
  1899. push %r14
  1900. .cfi_push %r14
  1901. push %r15
  1902. .cfi_push %r15
  1903. .Lmulx4x_prologue:
  1904. shl \$3,${num}d # convert $num to bytes
  1905. lea ($num,$num,2),%r10 # 3*$num in bytes
  1906. neg $num # -$num
  1907. mov ($n0),$n0 # *n0
  1908. ##############################################################
  1909. # Ensure that stack frame doesn't alias with $rptr+3*$num
  1910. # modulo 4096, which covers ret[num], am[num] and n[num]
  1911. # (see bn_exp.c). This is done to allow memory disambiguation
  1912. # logic do its magic. [Extra [num] is allocated in order
  1913. # to align with bn_power5's frame, which is cleansed after
  1914. # completing exponentiation. Extra 256 bytes is for power mask
  1915. # calculated from 7th argument, the index.]
  1916. #
  1917. lea -320(%rsp,$num,2),%r11
  1918. mov %rsp,%rbp
  1919. sub $rp,%r11
  1920. and \$4095,%r11
  1921. cmp %r11,%r10
  1922. jb .Lmulx4xsp_alt
  1923. sub %r11,%rbp # align with $aptr
  1924. lea -320(%rbp,$num,2),%rbp # future alloca(frame+2*$num*8+256)
  1925. jmp .Lmulx4xsp_done
  1926. .Lmulx4xsp_alt:
  1927. lea 4096-320(,$num,2),%r10
  1928. lea -320(%rbp,$num,2),%rbp # future alloca(frame+2*$num*8+256)
  1929. sub %r10,%r11
  1930. mov \$0,%r10
  1931. cmovc %r10,%r11
  1932. sub %r11,%rbp
  1933. .Lmulx4xsp_done:
  1934. and \$-64,%rbp # ensure alignment
  1935. mov %rsp,%r11
  1936. sub %rbp,%r11
  1937. and \$-4096,%r11
  1938. lea (%rbp,%r11),%rsp
  1939. mov (%rsp),%r10
  1940. cmp %rbp,%rsp
  1941. ja .Lmulx4x_page_walk
  1942. jmp .Lmulx4x_page_walk_done
  1943. .Lmulx4x_page_walk:
  1944. lea -4096(%rsp),%rsp
  1945. mov (%rsp),%r10
  1946. cmp %rbp,%rsp
  1947. ja .Lmulx4x_page_walk
  1948. .Lmulx4x_page_walk_done:
  1949. ##############################################################
  1950. # Stack layout
  1951. # +0 -num
  1952. # +8 off-loaded &b[i]
  1953. # +16 end of b[num]
  1954. # +24 inner counter
  1955. # +32 saved n0
  1956. # +40 saved %rsp
  1957. # +48
  1958. # +56 saved rp
  1959. # +64 tmp[num+1]
  1960. #
  1961. mov $n0, 32(%rsp) # save *n0
  1962. mov %rax,40(%rsp) # save original %rsp
  1963. .cfi_cfa_expression %rsp+40,deref,+8
  1964. .Lmulx4x_body:
  1965. call mulx4x_internal
  1966. mov 40(%rsp),%rsi # restore %rsp
  1967. .cfi_def_cfa %rsi,8
  1968. mov \$1,%rax
  1969. mov -48(%rsi),%r15
  1970. .cfi_restore %r15
  1971. mov -40(%rsi),%r14
  1972. .cfi_restore %r14
  1973. mov -32(%rsi),%r13
  1974. .cfi_restore %r13
  1975. mov -24(%rsi),%r12
  1976. .cfi_restore %r12
  1977. mov -16(%rsi),%rbp
  1978. .cfi_restore %rbp
  1979. mov -8(%rsi),%rbx
  1980. .cfi_restore %rbx
  1981. lea (%rsi),%rsp
  1982. .cfi_def_cfa_register %rsp
  1983. .Lmulx4x_epilogue:
  1984. ret
  1985. .cfi_endproc
  1986. .size bn_mulx4x_mont_gather5,.-bn_mulx4x_mont_gather5
  1987. .type mulx4x_internal,\@abi-omnipotent
  1988. .align 32
  1989. mulx4x_internal:
  1990. .cfi_startproc
  1991. mov $num,8(%rsp) # save -$num (it was in bytes)
  1992. mov $num,%r10
  1993. neg $num # restore $num
  1994. shl \$5,$num
  1995. neg %r10 # restore $num
  1996. lea 128($bp,$num),%r13 # end of powers table (+size optimization)
  1997. shr \$5+5,$num
  1998. movd `($win64?56:8)`(%rax),%xmm5 # load 7th argument
  1999. sub \$1,$num
  2000. lea .Linc(%rip),%rax
  2001. mov %r13,16+8(%rsp) # end of b[num]
  2002. mov $num,24+8(%rsp) # inner counter
  2003. mov $rp, 56+8(%rsp) # save $rp
  2004. ___
  2005. my ($aptr, $bptr, $nptr, $tptr, $mi, $bi, $zero, $num)=
  2006. ("%rsi","%rdi","%rcx","%rbx","%r8","%r9","%rbp","%rax");
  2007. my $rptr=$bptr;
  2008. my $STRIDE=2**5*8; # 5 is "window size"
  2009. my $N=$STRIDE/4; # should match cache line size
  2010. $code.=<<___;
  2011. movdqa 0(%rax),%xmm0 # 00000001000000010000000000000000
  2012. movdqa 16(%rax),%xmm1 # 00000002000000020000000200000002
  2013. lea 88-112(%rsp,%r10),%r10 # place the mask after tp[num+1] (+ICache optimization)
  2014. lea 128($bp),$bptr # size optimization
  2015. pshufd \$0,%xmm5,%xmm5 # broadcast index
  2016. movdqa %xmm1,%xmm4
  2017. .byte 0x67
  2018. movdqa %xmm1,%xmm2
  2019. ___
  2020. ########################################################################
  2021. # calculate mask by comparing 0..31 to index and save result to stack
  2022. #
  2023. $code.=<<___;
  2024. .byte 0x67
  2025. paddd %xmm0,%xmm1
  2026. pcmpeqd %xmm5,%xmm0 # compare to 1,0
  2027. movdqa %xmm4,%xmm3
  2028. ___
  2029. for($i=0;$i<$STRIDE/16-4;$i+=4) {
  2030. $code.=<<___;
  2031. paddd %xmm1,%xmm2
  2032. pcmpeqd %xmm5,%xmm1 # compare to 3,2
  2033. movdqa %xmm0,`16*($i+0)+112`(%r10)
  2034. movdqa %xmm4,%xmm0
  2035. paddd %xmm2,%xmm3
  2036. pcmpeqd %xmm5,%xmm2 # compare to 5,4
  2037. movdqa %xmm1,`16*($i+1)+112`(%r10)
  2038. movdqa %xmm4,%xmm1
  2039. paddd %xmm3,%xmm0
  2040. pcmpeqd %xmm5,%xmm3 # compare to 7,6
  2041. movdqa %xmm2,`16*($i+2)+112`(%r10)
  2042. movdqa %xmm4,%xmm2
  2043. paddd %xmm0,%xmm1
  2044. pcmpeqd %xmm5,%xmm0
  2045. movdqa %xmm3,`16*($i+3)+112`(%r10)
  2046. movdqa %xmm4,%xmm3
  2047. ___
  2048. }
  2049. $code.=<<___; # last iteration can be optimized
  2050. .byte 0x67
  2051. paddd %xmm1,%xmm2
  2052. pcmpeqd %xmm5,%xmm1
  2053. movdqa %xmm0,`16*($i+0)+112`(%r10)
  2054. paddd %xmm2,%xmm3
  2055. pcmpeqd %xmm5,%xmm2
  2056. movdqa %xmm1,`16*($i+1)+112`(%r10)
  2057. pcmpeqd %xmm5,%xmm3
  2058. movdqa %xmm2,`16*($i+2)+112`(%r10)
  2059. pand `16*($i+0)-128`($bptr),%xmm0 # while it's still in register
  2060. pand `16*($i+1)-128`($bptr),%xmm1
  2061. pand `16*($i+2)-128`($bptr),%xmm2
  2062. movdqa %xmm3,`16*($i+3)+112`(%r10)
  2063. pand `16*($i+3)-128`($bptr),%xmm3
  2064. por %xmm2,%xmm0
  2065. por %xmm3,%xmm1
  2066. ___
  2067. for($i=0;$i<$STRIDE/16-4;$i+=4) {
  2068. $code.=<<___;
  2069. movdqa `16*($i+0)-128`($bptr),%xmm4
  2070. movdqa `16*($i+1)-128`($bptr),%xmm5
  2071. movdqa `16*($i+2)-128`($bptr),%xmm2
  2072. pand `16*($i+0)+112`(%r10),%xmm4
  2073. movdqa `16*($i+3)-128`($bptr),%xmm3
  2074. pand `16*($i+1)+112`(%r10),%xmm5
  2075. por %xmm4,%xmm0
  2076. pand `16*($i+2)+112`(%r10),%xmm2
  2077. por %xmm5,%xmm1
  2078. pand `16*($i+3)+112`(%r10),%xmm3
  2079. por %xmm2,%xmm0
  2080. por %xmm3,%xmm1
  2081. ___
  2082. }
  2083. $code.=<<___;
  2084. pxor %xmm1,%xmm0
  2085. pshufd \$0x4e,%xmm0,%xmm1
  2086. por %xmm1,%xmm0
  2087. lea $STRIDE($bptr),$bptr
  2088. movq %xmm0,%rdx # bp[0]
  2089. lea 64+8*4+8(%rsp),$tptr
  2090. mov %rdx,$bi
  2091. mulx 0*8($aptr),$mi,%rax # a[0]*b[0]
  2092. mulx 1*8($aptr),%r11,%r12 # a[1]*b[0]
  2093. add %rax,%r11
  2094. mulx 2*8($aptr),%rax,%r13 # ...
  2095. adc %rax,%r12
  2096. adc \$0,%r13
  2097. mulx 3*8($aptr),%rax,%r14
  2098. mov $mi,%r15
  2099. imulq 32+8(%rsp),$mi # "t[0]"*n0
  2100. xor $zero,$zero # cf=0, of=0
  2101. mov $mi,%rdx
  2102. mov $bptr,8+8(%rsp) # off-load &b[i]
  2103. lea 4*8($aptr),$aptr
  2104. adcx %rax,%r13
  2105. adcx $zero,%r14 # cf=0
  2106. mulx 0*8($nptr),%rax,%r10
  2107. adcx %rax,%r15 # discarded
  2108. adox %r11,%r10
  2109. mulx 1*8($nptr),%rax,%r11
  2110. adcx %rax,%r10
  2111. adox %r12,%r11
  2112. mulx 2*8($nptr),%rax,%r12
  2113. mov 24+8(%rsp),$bptr # counter value
  2114. mov %r10,-8*4($tptr)
  2115. adcx %rax,%r11
  2116. adox %r13,%r12
  2117. mulx 3*8($nptr),%rax,%r15
  2118. mov $bi,%rdx
  2119. mov %r11,-8*3($tptr)
  2120. adcx %rax,%r12
  2121. adox $zero,%r15 # of=0
  2122. lea 4*8($nptr),$nptr
  2123. mov %r12,-8*2($tptr)
  2124. jmp .Lmulx4x_1st
  2125. .align 32
  2126. .Lmulx4x_1st:
  2127. adcx $zero,%r15 # cf=0, modulo-scheduled
  2128. mulx 0*8($aptr),%r10,%rax # a[4]*b[0]
  2129. adcx %r14,%r10
  2130. mulx 1*8($aptr),%r11,%r14 # a[5]*b[0]
  2131. adcx %rax,%r11
  2132. mulx 2*8($aptr),%r12,%rax # ...
  2133. adcx %r14,%r12
  2134. mulx 3*8($aptr),%r13,%r14
  2135. .byte 0x67,0x67
  2136. mov $mi,%rdx
  2137. adcx %rax,%r13
  2138. adcx $zero,%r14 # cf=0
  2139. lea 4*8($aptr),$aptr
  2140. lea 4*8($tptr),$tptr
  2141. adox %r15,%r10
  2142. mulx 0*8($nptr),%rax,%r15
  2143. adcx %rax,%r10
  2144. adox %r15,%r11
  2145. mulx 1*8($nptr),%rax,%r15
  2146. adcx %rax,%r11
  2147. adox %r15,%r12
  2148. mulx 2*8($nptr),%rax,%r15
  2149. mov %r10,-5*8($tptr)
  2150. adcx %rax,%r12
  2151. mov %r11,-4*8($tptr)
  2152. adox %r15,%r13
  2153. mulx 3*8($nptr),%rax,%r15
  2154. mov $bi,%rdx
  2155. mov %r12,-3*8($tptr)
  2156. adcx %rax,%r13
  2157. adox $zero,%r15
  2158. lea 4*8($nptr),$nptr
  2159. mov %r13,-2*8($tptr)
  2160. dec $bptr # of=0, pass cf
  2161. jnz .Lmulx4x_1st
  2162. mov 8(%rsp),$num # load -num
  2163. adc $zero,%r15 # modulo-scheduled
  2164. lea ($aptr,$num),$aptr # rewind $aptr
  2165. add %r15,%r14
  2166. mov 8+8(%rsp),$bptr # re-load &b[i]
  2167. adc $zero,$zero # top-most carry
  2168. mov %r14,-1*8($tptr)
  2169. jmp .Lmulx4x_outer
  2170. .align 32
  2171. .Lmulx4x_outer:
  2172. lea 16-256($tptr),%r10 # where 256-byte mask is (+density control)
  2173. pxor %xmm4,%xmm4
  2174. .byte 0x67,0x67
  2175. pxor %xmm5,%xmm5
  2176. ___
  2177. for($i=0;$i<$STRIDE/16;$i+=4) {
  2178. $code.=<<___;
  2179. movdqa `16*($i+0)-128`($bptr),%xmm0
  2180. movdqa `16*($i+1)-128`($bptr),%xmm1
  2181. movdqa `16*($i+2)-128`($bptr),%xmm2
  2182. pand `16*($i+0)+256`(%r10),%xmm0
  2183. movdqa `16*($i+3)-128`($bptr),%xmm3
  2184. pand `16*($i+1)+256`(%r10),%xmm1
  2185. por %xmm0,%xmm4
  2186. pand `16*($i+2)+256`(%r10),%xmm2
  2187. por %xmm1,%xmm5
  2188. pand `16*($i+3)+256`(%r10),%xmm3
  2189. por %xmm2,%xmm4
  2190. por %xmm3,%xmm5
  2191. ___
  2192. }
  2193. $code.=<<___;
  2194. por %xmm5,%xmm4
  2195. pshufd \$0x4e,%xmm4,%xmm0
  2196. por %xmm4,%xmm0
  2197. lea $STRIDE($bptr),$bptr
  2198. movq %xmm0,%rdx # m0=bp[i]
  2199. mov $zero,($tptr) # save top-most carry
  2200. lea 4*8($tptr,$num),$tptr # rewind $tptr
  2201. mulx 0*8($aptr),$mi,%r11 # a[0]*b[i]
  2202. xor $zero,$zero # cf=0, of=0
  2203. mov %rdx,$bi
  2204. mulx 1*8($aptr),%r14,%r12 # a[1]*b[i]
  2205. adox -4*8($tptr),$mi # +t[0]
  2206. adcx %r14,%r11
  2207. mulx 2*8($aptr),%r15,%r13 # ...
  2208. adox -3*8($tptr),%r11
  2209. adcx %r15,%r12
  2210. mulx 3*8($aptr),%rdx,%r14
  2211. adox -2*8($tptr),%r12
  2212. adcx %rdx,%r13
  2213. lea ($nptr,$num),$nptr # rewind $nptr
  2214. lea 4*8($aptr),$aptr
  2215. adox -1*8($tptr),%r13
  2216. adcx $zero,%r14
  2217. adox $zero,%r14
  2218. mov $mi,%r15
  2219. imulq 32+8(%rsp),$mi # "t[0]"*n0
  2220. mov $mi,%rdx
  2221. xor $zero,$zero # cf=0, of=0
  2222. mov $bptr,8+8(%rsp) # off-load &b[i]
  2223. mulx 0*8($nptr),%rax,%r10
  2224. adcx %rax,%r15 # discarded
  2225. adox %r11,%r10
  2226. mulx 1*8($nptr),%rax,%r11
  2227. adcx %rax,%r10
  2228. adox %r12,%r11
  2229. mulx 2*8($nptr),%rax,%r12
  2230. adcx %rax,%r11
  2231. adox %r13,%r12
  2232. mulx 3*8($nptr),%rax,%r15
  2233. mov $bi,%rdx
  2234. mov 24+8(%rsp),$bptr # counter value
  2235. mov %r10,-8*4($tptr)
  2236. adcx %rax,%r12
  2237. mov %r11,-8*3($tptr)
  2238. adox $zero,%r15 # of=0
  2239. mov %r12,-8*2($tptr)
  2240. lea 4*8($nptr),$nptr
  2241. jmp .Lmulx4x_inner
  2242. .align 32
  2243. .Lmulx4x_inner:
  2244. mulx 0*8($aptr),%r10,%rax # a[4]*b[i]
  2245. adcx $zero,%r15 # cf=0, modulo-scheduled
  2246. adox %r14,%r10
  2247. mulx 1*8($aptr),%r11,%r14 # a[5]*b[i]
  2248. adcx 0*8($tptr),%r10
  2249. adox %rax,%r11
  2250. mulx 2*8($aptr),%r12,%rax # ...
  2251. adcx 1*8($tptr),%r11
  2252. adox %r14,%r12
  2253. mulx 3*8($aptr),%r13,%r14
  2254. mov $mi,%rdx
  2255. adcx 2*8($tptr),%r12
  2256. adox %rax,%r13
  2257. adcx 3*8($tptr),%r13
  2258. adox $zero,%r14 # of=0
  2259. lea 4*8($aptr),$aptr
  2260. lea 4*8($tptr),$tptr
  2261. adcx $zero,%r14 # cf=0
  2262. adox %r15,%r10
  2263. mulx 0*8($nptr),%rax,%r15
  2264. adcx %rax,%r10
  2265. adox %r15,%r11
  2266. mulx 1*8($nptr),%rax,%r15
  2267. adcx %rax,%r11
  2268. adox %r15,%r12
  2269. mulx 2*8($nptr),%rax,%r15
  2270. mov %r10,-5*8($tptr)
  2271. adcx %rax,%r12
  2272. adox %r15,%r13
  2273. mov %r11,-4*8($tptr)
  2274. mulx 3*8($nptr),%rax,%r15
  2275. mov $bi,%rdx
  2276. lea 4*8($nptr),$nptr
  2277. mov %r12,-3*8($tptr)
  2278. adcx %rax,%r13
  2279. adox $zero,%r15
  2280. mov %r13,-2*8($tptr)
  2281. dec $bptr # of=0, pass cf
  2282. jnz .Lmulx4x_inner
  2283. mov 0+8(%rsp),$num # load -num
  2284. adc $zero,%r15 # modulo-scheduled
  2285. sub 0*8($tptr),$bptr # pull top-most carry to %cf
  2286. mov 8+8(%rsp),$bptr # re-load &b[i]
  2287. mov 16+8(%rsp),%r10
  2288. adc %r15,%r14
  2289. lea ($aptr,$num),$aptr # rewind $aptr
  2290. adc $zero,$zero # top-most carry
  2291. mov %r14,-1*8($tptr)
  2292. cmp %r10,$bptr
  2293. jb .Lmulx4x_outer
  2294. mov -8($nptr),%r10
  2295. mov $zero,%r8
  2296. mov ($nptr,$num),%r12
  2297. lea ($nptr,$num),%rbp # rewind $nptr
  2298. mov $num,%rcx
  2299. lea ($tptr,$num),%rdi # rewind $tptr
  2300. xor %eax,%eax
  2301. xor %r15,%r15
  2302. sub %r14,%r10 # compare top-most words
  2303. adc %r15,%r15
  2304. or %r15,%r8
  2305. sar \$3+2,%rcx
  2306. sub %r8,%rax # %rax=-%r8
  2307. mov 56+8(%rsp),%rdx # restore rp
  2308. dec %r12 # so that after 'not' we get -n[0]
  2309. mov 8*1(%rbp),%r13
  2310. xor %r8,%r8
  2311. mov 8*2(%rbp),%r14
  2312. mov 8*3(%rbp),%r15
  2313. jmp .Lsqrx4x_sub_entry # common post-condition
  2314. .cfi_endproc
  2315. .size mulx4x_internal,.-mulx4x_internal
  2316. ___
  2317. } {
  2318. ######################################################################
  2319. # void bn_power5(
  2320. my $rptr="%rdi"; # BN_ULONG *rptr,
  2321. my $aptr="%rsi"; # const BN_ULONG *aptr,
  2322. my $bptr="%rdx"; # const void *table,
  2323. my $nptr="%rcx"; # const BN_ULONG *nptr,
  2324. my $n0 ="%r8"; # const BN_ULONG *n0);
  2325. my $num ="%r9"; # int num, has to be divisible by 8
  2326. # int pwr);
  2327. my ($i,$j,$tptr)=("%rbp","%rcx",$rptr);
  2328. my @A0=("%r10","%r11");
  2329. my @A1=("%r12","%r13");
  2330. my ($a0,$a1,$ai)=("%r14","%r15","%rbx");
  2331. $code.=<<___;
  2332. .type bn_powerx5,\@function,6
  2333. .align 32
  2334. bn_powerx5:
  2335. .cfi_startproc
  2336. mov %rsp,%rax
  2337. .cfi_def_cfa_register %rax
  2338. .Lpowerx5_enter:
  2339. push %rbx
  2340. .cfi_push %rbx
  2341. push %rbp
  2342. .cfi_push %rbp
  2343. push %r12
  2344. .cfi_push %r12
  2345. push %r13
  2346. .cfi_push %r13
  2347. push %r14
  2348. .cfi_push %r14
  2349. push %r15
  2350. .cfi_push %r15
  2351. .Lpowerx5_prologue:
  2352. shl \$3,${num}d # convert $num to bytes
  2353. lea ($num,$num,2),%r10 # 3*$num in bytes
  2354. neg $num
  2355. mov ($n0),$n0 # *n0
  2356. ##############################################################
  2357. # Ensure that stack frame doesn't alias with $rptr+3*$num
  2358. # modulo 4096, which covers ret[num], am[num] and n[num]
  2359. # (see bn_exp.c). This is done to allow memory disambiguation
  2360. # logic do its magic. [Extra 256 bytes is for power mask
  2361. # calculated from 7th argument, the index.]
  2362. #
  2363. lea -320(%rsp,$num,2),%r11
  2364. mov %rsp,%rbp
  2365. sub $rptr,%r11
  2366. and \$4095,%r11
  2367. cmp %r11,%r10
  2368. jb .Lpwrx_sp_alt
  2369. sub %r11,%rbp # align with $aptr
  2370. lea -320(%rbp,$num,2),%rbp # future alloca(frame+2*$num*8+256)
  2371. jmp .Lpwrx_sp_done
  2372. .align 32
  2373. .Lpwrx_sp_alt:
  2374. lea 4096-320(,$num,2),%r10
  2375. lea -320(%rbp,$num,2),%rbp # alloca(frame+2*$num*8+256)
  2376. sub %r10,%r11
  2377. mov \$0,%r10
  2378. cmovc %r10,%r11
  2379. sub %r11,%rbp
  2380. .Lpwrx_sp_done:
  2381. and \$-64,%rbp
  2382. mov %rsp,%r11
  2383. sub %rbp,%r11
  2384. and \$-4096,%r11
  2385. lea (%rbp,%r11),%rsp
  2386. mov (%rsp),%r10
  2387. cmp %rbp,%rsp
  2388. ja .Lpwrx_page_walk
  2389. jmp .Lpwrx_page_walk_done
  2390. .Lpwrx_page_walk:
  2391. lea -4096(%rsp),%rsp
  2392. mov (%rsp),%r10
  2393. cmp %rbp,%rsp
  2394. ja .Lpwrx_page_walk
  2395. .Lpwrx_page_walk_done:
  2396. mov $num,%r10
  2397. neg $num
  2398. ##############################################################
  2399. # Stack layout
  2400. #
  2401. # +0 saved $num, used in reduction section
  2402. # +8 &t[2*$num], used in reduction section
  2403. # +16 intermediate carry bit
  2404. # +24 top-most carry bit, used in reduction section
  2405. # +32 saved *n0
  2406. # +40 saved %rsp
  2407. # +48 t[2*$num]
  2408. #
  2409. pxor %xmm0,%xmm0
  2410. movq $rptr,%xmm1 # save $rptr
  2411. movq $nptr,%xmm2 # save $nptr
  2412. movq %r10, %xmm3 # -$num
  2413. movq $bptr,%xmm4
  2414. mov $n0, 32(%rsp)
  2415. mov %rax, 40(%rsp) # save original %rsp
  2416. .cfi_cfa_expression %rsp+40,deref,+8
  2417. .Lpowerx5_body:
  2418. call __bn_sqrx8x_internal
  2419. call __bn_postx4x_internal
  2420. call __bn_sqrx8x_internal
  2421. call __bn_postx4x_internal
  2422. call __bn_sqrx8x_internal
  2423. call __bn_postx4x_internal
  2424. call __bn_sqrx8x_internal
  2425. call __bn_postx4x_internal
  2426. call __bn_sqrx8x_internal
  2427. call __bn_postx4x_internal
  2428. mov %r10,$num # -num
  2429. mov $aptr,$rptr
  2430. movq %xmm2,$nptr
  2431. movq %xmm4,$bptr
  2432. mov 40(%rsp),%rax
  2433. call mulx4x_internal
  2434. mov 40(%rsp),%rsi # restore %rsp
  2435. .cfi_def_cfa %rsi,8
  2436. mov \$1,%rax
  2437. mov -48(%rsi),%r15
  2438. .cfi_restore %r15
  2439. mov -40(%rsi),%r14
  2440. .cfi_restore %r14
  2441. mov -32(%rsi),%r13
  2442. .cfi_restore %r13
  2443. mov -24(%rsi),%r12
  2444. .cfi_restore %r12
  2445. mov -16(%rsi),%rbp
  2446. .cfi_restore %rbp
  2447. mov -8(%rsi),%rbx
  2448. .cfi_restore %rbx
  2449. lea (%rsi),%rsp
  2450. .cfi_def_cfa_register %rsp
  2451. .Lpowerx5_epilogue:
  2452. ret
  2453. .cfi_endproc
  2454. .size bn_powerx5,.-bn_powerx5
  2455. .globl bn_sqrx8x_internal
  2456. .hidden bn_sqrx8x_internal
  2457. .type bn_sqrx8x_internal,\@abi-omnipotent
  2458. .align 32
  2459. bn_sqrx8x_internal:
  2460. __bn_sqrx8x_internal:
  2461. .cfi_startproc
  2462. ##################################################################
  2463. # Squaring part:
  2464. #
  2465. # a) multiply-n-add everything but a[i]*a[i];
  2466. # b) shift result of a) by 1 to the left and accumulate
  2467. # a[i]*a[i] products;
  2468. #
  2469. ##################################################################
  2470. # a[7]a[7]a[6]a[6]a[5]a[5]a[4]a[4]a[3]a[3]a[2]a[2]a[1]a[1]a[0]a[0]
  2471. # a[1]a[0]
  2472. # a[2]a[0]
  2473. # a[3]a[0]
  2474. # a[2]a[1]
  2475. # a[3]a[1]
  2476. # a[3]a[2]
  2477. #
  2478. # a[4]a[0]
  2479. # a[5]a[0]
  2480. # a[6]a[0]
  2481. # a[7]a[0]
  2482. # a[4]a[1]
  2483. # a[5]a[1]
  2484. # a[6]a[1]
  2485. # a[7]a[1]
  2486. # a[4]a[2]
  2487. # a[5]a[2]
  2488. # a[6]a[2]
  2489. # a[7]a[2]
  2490. # a[4]a[3]
  2491. # a[5]a[3]
  2492. # a[6]a[3]
  2493. # a[7]a[3]
  2494. #
  2495. # a[5]a[4]
  2496. # a[6]a[4]
  2497. # a[7]a[4]
  2498. # a[6]a[5]
  2499. # a[7]a[5]
  2500. # a[7]a[6]
  2501. # a[7]a[7]a[6]a[6]a[5]a[5]a[4]a[4]a[3]a[3]a[2]a[2]a[1]a[1]a[0]a[0]
  2502. ___
  2503. {
  2504. my ($zero,$carry)=("%rbp","%rcx");
  2505. my $aaptr=$zero;
  2506. $code.=<<___;
  2507. lea 48+8(%rsp),$tptr
  2508. lea ($aptr,$num),$aaptr
  2509. mov $num,0+8(%rsp) # save $num
  2510. mov $aaptr,8+8(%rsp) # save end of $aptr
  2511. jmp .Lsqr8x_zero_start
  2512. .align 32
  2513. .byte 0x66,0x66,0x66,0x2e,0x0f,0x1f,0x84,0x00,0x00,0x00,0x00,0x00
  2514. .Lsqrx8x_zero:
  2515. .byte 0x3e
  2516. movdqa %xmm0,0*8($tptr)
  2517. movdqa %xmm0,2*8($tptr)
  2518. movdqa %xmm0,4*8($tptr)
  2519. movdqa %xmm0,6*8($tptr)
  2520. .Lsqr8x_zero_start: # aligned at 32
  2521. movdqa %xmm0,8*8($tptr)
  2522. movdqa %xmm0,10*8($tptr)
  2523. movdqa %xmm0,12*8($tptr)
  2524. movdqa %xmm0,14*8($tptr)
  2525. lea 16*8($tptr),$tptr
  2526. sub \$64,$num
  2527. jnz .Lsqrx8x_zero
  2528. mov 0*8($aptr),%rdx # a[0], modulo-scheduled
  2529. #xor %r9,%r9 # t[1], ex-$num, zero already
  2530. xor %r10,%r10
  2531. xor %r11,%r11
  2532. xor %r12,%r12
  2533. xor %r13,%r13
  2534. xor %r14,%r14
  2535. xor %r15,%r15
  2536. lea 48+8(%rsp),$tptr
  2537. xor $zero,$zero # cf=0, cf=0
  2538. jmp .Lsqrx8x_outer_loop
  2539. .align 32
  2540. .Lsqrx8x_outer_loop:
  2541. mulx 1*8($aptr),%r8,%rax # a[1]*a[0]
  2542. adcx %r9,%r8 # a[1]*a[0]+=t[1]
  2543. adox %rax,%r10
  2544. mulx 2*8($aptr),%r9,%rax # a[2]*a[0]
  2545. adcx %r10,%r9
  2546. adox %rax,%r11
  2547. .byte 0xc4,0xe2,0xab,0xf6,0x86,0x18,0x00,0x00,0x00 # mulx 3*8($aptr),%r10,%rax # ...
  2548. adcx %r11,%r10
  2549. adox %rax,%r12
  2550. .byte 0xc4,0xe2,0xa3,0xf6,0x86,0x20,0x00,0x00,0x00 # mulx 4*8($aptr),%r11,%rax
  2551. adcx %r12,%r11
  2552. adox %rax,%r13
  2553. mulx 5*8($aptr),%r12,%rax
  2554. adcx %r13,%r12
  2555. adox %rax,%r14
  2556. mulx 6*8($aptr),%r13,%rax
  2557. adcx %r14,%r13
  2558. adox %r15,%rax
  2559. mulx 7*8($aptr),%r14,%r15
  2560. mov 1*8($aptr),%rdx # a[1]
  2561. adcx %rax,%r14
  2562. adox $zero,%r15
  2563. adc 8*8($tptr),%r15
  2564. mov %r8,1*8($tptr) # t[1]
  2565. mov %r9,2*8($tptr) # t[2]
  2566. sbb $carry,$carry # mov %cf,$carry
  2567. xor $zero,$zero # cf=0, of=0
  2568. mulx 2*8($aptr),%r8,%rbx # a[2]*a[1]
  2569. mulx 3*8($aptr),%r9,%rax # a[3]*a[1]
  2570. adcx %r10,%r8
  2571. adox %rbx,%r9
  2572. mulx 4*8($aptr),%r10,%rbx # ...
  2573. adcx %r11,%r9
  2574. adox %rax,%r10
  2575. .byte 0xc4,0xe2,0xa3,0xf6,0x86,0x28,0x00,0x00,0x00 # mulx 5*8($aptr),%r11,%rax
  2576. adcx %r12,%r10
  2577. adox %rbx,%r11
  2578. .byte 0xc4,0xe2,0x9b,0xf6,0x9e,0x30,0x00,0x00,0x00 # mulx 6*8($aptr),%r12,%rbx
  2579. adcx %r13,%r11
  2580. adox %r14,%r12
  2581. .byte 0xc4,0x62,0x93,0xf6,0xb6,0x38,0x00,0x00,0x00 # mulx 7*8($aptr),%r13,%r14
  2582. mov 2*8($aptr),%rdx # a[2]
  2583. adcx %rax,%r12
  2584. adox %rbx,%r13
  2585. adcx %r15,%r13
  2586. adox $zero,%r14 # of=0
  2587. adcx $zero,%r14 # cf=0
  2588. mov %r8,3*8($tptr) # t[3]
  2589. mov %r9,4*8($tptr) # t[4]
  2590. mulx 3*8($aptr),%r8,%rbx # a[3]*a[2]
  2591. mulx 4*8($aptr),%r9,%rax # a[4]*a[2]
  2592. adcx %r10,%r8
  2593. adox %rbx,%r9
  2594. mulx 5*8($aptr),%r10,%rbx # ...
  2595. adcx %r11,%r9
  2596. adox %rax,%r10
  2597. .byte 0xc4,0xe2,0xa3,0xf6,0x86,0x30,0x00,0x00,0x00 # mulx 6*8($aptr),%r11,%rax
  2598. adcx %r12,%r10
  2599. adox %r13,%r11
  2600. .byte 0xc4,0x62,0x9b,0xf6,0xae,0x38,0x00,0x00,0x00 # mulx 7*8($aptr),%r12,%r13
  2601. .byte 0x3e
  2602. mov 3*8($aptr),%rdx # a[3]
  2603. adcx %rbx,%r11
  2604. adox %rax,%r12
  2605. adcx %r14,%r12
  2606. mov %r8,5*8($tptr) # t[5]
  2607. mov %r9,6*8($tptr) # t[6]
  2608. mulx 4*8($aptr),%r8,%rax # a[4]*a[3]
  2609. adox $zero,%r13 # of=0
  2610. adcx $zero,%r13 # cf=0
  2611. mulx 5*8($aptr),%r9,%rbx # a[5]*a[3]
  2612. adcx %r10,%r8
  2613. adox %rax,%r9
  2614. mulx 6*8($aptr),%r10,%rax # ...
  2615. adcx %r11,%r9
  2616. adox %r12,%r10
  2617. mulx 7*8($aptr),%r11,%r12
  2618. mov 4*8($aptr),%rdx # a[4]
  2619. mov 5*8($aptr),%r14 # a[5]
  2620. adcx %rbx,%r10
  2621. adox %rax,%r11
  2622. mov 6*8($aptr),%r15 # a[6]
  2623. adcx %r13,%r11
  2624. adox $zero,%r12 # of=0
  2625. adcx $zero,%r12 # cf=0
  2626. mov %r8,7*8($tptr) # t[7]
  2627. mov %r9,8*8($tptr) # t[8]
  2628. mulx %r14,%r9,%rax # a[5]*a[4]
  2629. mov 7*8($aptr),%r8 # a[7]
  2630. adcx %r10,%r9
  2631. mulx %r15,%r10,%rbx # a[6]*a[4]
  2632. adox %rax,%r10
  2633. adcx %r11,%r10
  2634. mulx %r8,%r11,%rax # a[7]*a[4]
  2635. mov %r14,%rdx # a[5]
  2636. adox %rbx,%r11
  2637. adcx %r12,%r11
  2638. #adox $zero,%rax # of=0
  2639. adcx $zero,%rax # cf=0
  2640. mulx %r15,%r14,%rbx # a[6]*a[5]
  2641. mulx %r8,%r12,%r13 # a[7]*a[5]
  2642. mov %r15,%rdx # a[6]
  2643. lea 8*8($aptr),$aptr
  2644. adcx %r14,%r11
  2645. adox %rbx,%r12
  2646. adcx %rax,%r12
  2647. adox $zero,%r13
  2648. .byte 0x67,0x67
  2649. mulx %r8,%r8,%r14 # a[7]*a[6]
  2650. adcx %r8,%r13
  2651. adcx $zero,%r14
  2652. cmp 8+8(%rsp),$aptr
  2653. je .Lsqrx8x_outer_break
  2654. neg $carry # mov $carry,%cf
  2655. mov \$-8,%rcx
  2656. mov $zero,%r15
  2657. mov 8*8($tptr),%r8
  2658. adcx 9*8($tptr),%r9 # +=t[9]
  2659. adcx 10*8($tptr),%r10 # ...
  2660. adcx 11*8($tptr),%r11
  2661. adc 12*8($tptr),%r12
  2662. adc 13*8($tptr),%r13
  2663. adc 14*8($tptr),%r14
  2664. adc 15*8($tptr),%r15
  2665. lea ($aptr),$aaptr
  2666. lea 2*64($tptr),$tptr
  2667. sbb %rax,%rax # mov %cf,$carry
  2668. mov -64($aptr),%rdx # a[0]
  2669. mov %rax,16+8(%rsp) # offload $carry
  2670. mov $tptr,24+8(%rsp)
  2671. #lea 8*8($tptr),$tptr # see 2*8*8($tptr) above
  2672. xor %eax,%eax # cf=0, of=0
  2673. jmp .Lsqrx8x_loop
  2674. .align 32
  2675. .Lsqrx8x_loop:
  2676. mov %r8,%rbx
  2677. mulx 0*8($aaptr),%rax,%r8 # a[8]*a[i]
  2678. adcx %rax,%rbx # +=t[8]
  2679. adox %r9,%r8
  2680. mulx 1*8($aaptr),%rax,%r9 # ...
  2681. adcx %rax,%r8
  2682. adox %r10,%r9
  2683. mulx 2*8($aaptr),%rax,%r10
  2684. adcx %rax,%r9
  2685. adox %r11,%r10
  2686. mulx 3*8($aaptr),%rax,%r11
  2687. adcx %rax,%r10
  2688. adox %r12,%r11
  2689. .byte 0xc4,0x62,0xfb,0xf6,0xa5,0x20,0x00,0x00,0x00 # mulx 4*8($aaptr),%rax,%r12
  2690. adcx %rax,%r11
  2691. adox %r13,%r12
  2692. mulx 5*8($aaptr),%rax,%r13
  2693. adcx %rax,%r12
  2694. adox %r14,%r13
  2695. mulx 6*8($aaptr),%rax,%r14
  2696. mov %rbx,($tptr,%rcx,8) # store t[8+i]
  2697. mov \$0,%ebx
  2698. adcx %rax,%r13
  2699. adox %r15,%r14
  2700. .byte 0xc4,0x62,0xfb,0xf6,0xbd,0x38,0x00,0x00,0x00 # mulx 7*8($aaptr),%rax,%r15
  2701. mov 8($aptr,%rcx,8),%rdx # a[i]
  2702. adcx %rax,%r14
  2703. adox %rbx,%r15 # %rbx is 0, of=0
  2704. adcx %rbx,%r15 # cf=0
  2705. .byte 0x67
  2706. inc %rcx # of=0
  2707. jnz .Lsqrx8x_loop
  2708. lea 8*8($aaptr),$aaptr
  2709. mov \$-8,%rcx
  2710. cmp 8+8(%rsp),$aaptr # done?
  2711. je .Lsqrx8x_break
  2712. sub 16+8(%rsp),%rbx # mov 16(%rsp),%cf
  2713. .byte 0x66
  2714. mov -64($aptr),%rdx
  2715. adcx 0*8($tptr),%r8
  2716. adcx 1*8($tptr),%r9
  2717. adc 2*8($tptr),%r10
  2718. adc 3*8($tptr),%r11
  2719. adc 4*8($tptr),%r12
  2720. adc 5*8($tptr),%r13
  2721. adc 6*8($tptr),%r14
  2722. adc 7*8($tptr),%r15
  2723. lea 8*8($tptr),$tptr
  2724. .byte 0x67
  2725. sbb %rax,%rax # mov %cf,%rax
  2726. xor %ebx,%ebx # cf=0, of=0
  2727. mov %rax,16+8(%rsp) # offload carry
  2728. jmp .Lsqrx8x_loop
  2729. .align 32
  2730. .Lsqrx8x_break:
  2731. xor $zero,$zero
  2732. sub 16+8(%rsp),%rbx # mov 16(%rsp),%cf
  2733. adcx $zero,%r8
  2734. mov 24+8(%rsp),$carry # initial $tptr, borrow $carry
  2735. adcx $zero,%r9
  2736. mov 0*8($aptr),%rdx # a[8], modulo-scheduled
  2737. adc \$0,%r10
  2738. mov %r8,0*8($tptr)
  2739. adc \$0,%r11
  2740. adc \$0,%r12
  2741. adc \$0,%r13
  2742. adc \$0,%r14
  2743. adc \$0,%r15
  2744. cmp $carry,$tptr # cf=0, of=0
  2745. je .Lsqrx8x_outer_loop
  2746. mov %r9,1*8($tptr)
  2747. mov 1*8($carry),%r9
  2748. mov %r10,2*8($tptr)
  2749. mov 2*8($carry),%r10
  2750. mov %r11,3*8($tptr)
  2751. mov 3*8($carry),%r11
  2752. mov %r12,4*8($tptr)
  2753. mov 4*8($carry),%r12
  2754. mov %r13,5*8($tptr)
  2755. mov 5*8($carry),%r13
  2756. mov %r14,6*8($tptr)
  2757. mov 6*8($carry),%r14
  2758. mov %r15,7*8($tptr)
  2759. mov 7*8($carry),%r15
  2760. mov $carry,$tptr
  2761. jmp .Lsqrx8x_outer_loop
  2762. .align 32
  2763. .Lsqrx8x_outer_break:
  2764. mov %r9,9*8($tptr) # t[9]
  2765. movq %xmm3,%rcx # -$num
  2766. mov %r10,10*8($tptr) # ...
  2767. mov %r11,11*8($tptr)
  2768. mov %r12,12*8($tptr)
  2769. mov %r13,13*8($tptr)
  2770. mov %r14,14*8($tptr)
  2771. ___
  2772. } {
  2773. my $i="%rcx";
  2774. $code.=<<___;
  2775. lea 48+8(%rsp),$tptr
  2776. mov ($aptr,$i),%rdx # a[0]
  2777. mov 8($tptr),$A0[1] # t[1]
  2778. xor $A0[0],$A0[0] # t[0], of=0, cf=0
  2779. mov 0+8(%rsp),$num # restore $num
  2780. adox $A0[1],$A0[1]
  2781. mov 16($tptr),$A1[0] # t[2] # prefetch
  2782. mov 24($tptr),$A1[1] # t[3] # prefetch
  2783. #jmp .Lsqrx4x_shift_n_add # happens to be aligned
  2784. .align 32
  2785. .Lsqrx4x_shift_n_add:
  2786. mulx %rdx,%rax,%rbx
  2787. adox $A1[0],$A1[0]
  2788. adcx $A0[0],%rax
  2789. .byte 0x48,0x8b,0x94,0x0e,0x08,0x00,0x00,0x00 # mov 8($aptr,$i),%rdx # a[i+1] # prefetch
  2790. .byte 0x4c,0x8b,0x97,0x20,0x00,0x00,0x00 # mov 32($tptr),$A0[0] # t[2*i+4] # prefetch
  2791. adox $A1[1],$A1[1]
  2792. adcx $A0[1],%rbx
  2793. mov 40($tptr),$A0[1] # t[2*i+4+1] # prefetch
  2794. mov %rax,0($tptr)
  2795. mov %rbx,8($tptr)
  2796. mulx %rdx,%rax,%rbx
  2797. adox $A0[0],$A0[0]
  2798. adcx $A1[0],%rax
  2799. mov 16($aptr,$i),%rdx # a[i+2] # prefetch
  2800. mov 48($tptr),$A1[0] # t[2*i+6] # prefetch
  2801. adox $A0[1],$A0[1]
  2802. adcx $A1[1],%rbx
  2803. mov 56($tptr),$A1[1] # t[2*i+6+1] # prefetch
  2804. mov %rax,16($tptr)
  2805. mov %rbx,24($tptr)
  2806. mulx %rdx,%rax,%rbx
  2807. adox $A1[0],$A1[0]
  2808. adcx $A0[0],%rax
  2809. mov 24($aptr,$i),%rdx # a[i+3] # prefetch
  2810. lea 32($i),$i
  2811. mov 64($tptr),$A0[0] # t[2*i+8] # prefetch
  2812. adox $A1[1],$A1[1]
  2813. adcx $A0[1],%rbx
  2814. mov 72($tptr),$A0[1] # t[2*i+8+1] # prefetch
  2815. mov %rax,32($tptr)
  2816. mov %rbx,40($tptr)
  2817. mulx %rdx,%rax,%rbx
  2818. adox $A0[0],$A0[0]
  2819. adcx $A1[0],%rax
  2820. jrcxz .Lsqrx4x_shift_n_add_break
  2821. .byte 0x48,0x8b,0x94,0x0e,0x00,0x00,0x00,0x00 # mov 0($aptr,$i),%rdx # a[i+4] # prefetch
  2822. adox $A0[1],$A0[1]
  2823. adcx $A1[1],%rbx
  2824. mov 80($tptr),$A1[0] # t[2*i+10] # prefetch
  2825. mov 88($tptr),$A1[1] # t[2*i+10+1] # prefetch
  2826. mov %rax,48($tptr)
  2827. mov %rbx,56($tptr)
  2828. lea 64($tptr),$tptr
  2829. nop
  2830. jmp .Lsqrx4x_shift_n_add
  2831. .align 32
  2832. .Lsqrx4x_shift_n_add_break:
  2833. adcx $A1[1],%rbx
  2834. mov %rax,48($tptr)
  2835. mov %rbx,56($tptr)
  2836. lea 64($tptr),$tptr # end of t[] buffer
  2837. ___
  2838. }
  2839. ######################################################################
  2840. # Montgomery reduction part, "word-by-word" algorithm.
  2841. #
  2842. # This new path is inspired by multiple submissions from Intel, by
  2843. # Shay Gueron, Vlad Krasnov, Erdinc Ozturk, James Guilford,
  2844. # Vinodh Gopal...
  2845. {
  2846. my ($nptr,$carry,$m0)=("%rbp","%rsi","%rdx");
  2847. $code.=<<___;
  2848. movq %xmm2,$nptr
  2849. __bn_sqrx8x_reduction:
  2850. xor %eax,%eax # initial top-most carry bit
  2851. mov 32+8(%rsp),%rbx # n0
  2852. mov 48+8(%rsp),%rdx # "%r8", 8*0($tptr)
  2853. lea -8*8($nptr,$num),%rcx # end of n[]
  2854. #lea 48+8(%rsp,$num,2),$tptr # end of t[] buffer
  2855. mov %rcx, 0+8(%rsp) # save end of n[]
  2856. mov $tptr,8+8(%rsp) # save end of t[]
  2857. lea 48+8(%rsp),$tptr # initial t[] window
  2858. jmp .Lsqrx8x_reduction_loop
  2859. .align 32
  2860. .Lsqrx8x_reduction_loop:
  2861. mov 8*1($tptr),%r9
  2862. mov 8*2($tptr),%r10
  2863. mov 8*3($tptr),%r11
  2864. mov 8*4($tptr),%r12
  2865. mov %rdx,%r8
  2866. imulq %rbx,%rdx # n0*a[i]
  2867. mov 8*5($tptr),%r13
  2868. mov 8*6($tptr),%r14
  2869. mov 8*7($tptr),%r15
  2870. mov %rax,24+8(%rsp) # store top-most carry bit
  2871. lea 8*8($tptr),$tptr
  2872. xor $carry,$carry # cf=0,of=0
  2873. mov \$-8,%rcx
  2874. jmp .Lsqrx8x_reduce
  2875. .align 32
  2876. .Lsqrx8x_reduce:
  2877. mov %r8, %rbx
  2878. mulx 8*0($nptr),%rax,%r8 # n[0]
  2879. adcx %rbx,%rax # discarded
  2880. adox %r9,%r8
  2881. mulx 8*1($nptr),%rbx,%r9 # n[1]
  2882. adcx %rbx,%r8
  2883. adox %r10,%r9
  2884. mulx 8*2($nptr),%rbx,%r10
  2885. adcx %rbx,%r9
  2886. adox %r11,%r10
  2887. mulx 8*3($nptr),%rbx,%r11
  2888. adcx %rbx,%r10
  2889. adox %r12,%r11
  2890. .byte 0xc4,0x62,0xe3,0xf6,0xa5,0x20,0x00,0x00,0x00 # mulx 8*4($nptr),%rbx,%r12
  2891. mov %rdx,%rax
  2892. mov %r8,%rdx
  2893. adcx %rbx,%r11
  2894. adox %r13,%r12
  2895. mulx 32+8(%rsp),%rbx,%rdx # %rdx discarded
  2896. mov %rax,%rdx
  2897. mov %rax,64+48+8(%rsp,%rcx,8) # put aside n0*a[i]
  2898. mulx 8*5($nptr),%rax,%r13
  2899. adcx %rax,%r12
  2900. adox %r14,%r13
  2901. mulx 8*6($nptr),%rax,%r14
  2902. adcx %rax,%r13
  2903. adox %r15,%r14
  2904. mulx 8*7($nptr),%rax,%r15
  2905. mov %rbx,%rdx
  2906. adcx %rax,%r14
  2907. adox $carry,%r15 # $carry is 0
  2908. adcx $carry,%r15 # cf=0
  2909. .byte 0x67,0x67,0x67
  2910. inc %rcx # of=0
  2911. jnz .Lsqrx8x_reduce
  2912. mov $carry,%rax # xor %rax,%rax
  2913. cmp 0+8(%rsp),$nptr # end of n[]?
  2914. jae .Lsqrx8x_no_tail
  2915. mov 48+8(%rsp),%rdx # pull n0*a[0]
  2916. add 8*0($tptr),%r8
  2917. lea 8*8($nptr),$nptr
  2918. mov \$-8,%rcx
  2919. adcx 8*1($tptr),%r9
  2920. adcx 8*2($tptr),%r10
  2921. adc 8*3($tptr),%r11
  2922. adc 8*4($tptr),%r12
  2923. adc 8*5($tptr),%r13
  2924. adc 8*6($tptr),%r14
  2925. adc 8*7($tptr),%r15
  2926. lea 8*8($tptr),$tptr
  2927. sbb %rax,%rax # top carry
  2928. xor $carry,$carry # of=0, cf=0
  2929. mov %rax,16+8(%rsp)
  2930. jmp .Lsqrx8x_tail
  2931. .align 32
  2932. .Lsqrx8x_tail:
  2933. mov %r8,%rbx
  2934. mulx 8*0($nptr),%rax,%r8
  2935. adcx %rax,%rbx
  2936. adox %r9,%r8
  2937. mulx 8*1($nptr),%rax,%r9
  2938. adcx %rax,%r8
  2939. adox %r10,%r9
  2940. mulx 8*2($nptr),%rax,%r10
  2941. adcx %rax,%r9
  2942. adox %r11,%r10
  2943. mulx 8*3($nptr),%rax,%r11
  2944. adcx %rax,%r10
  2945. adox %r12,%r11
  2946. .byte 0xc4,0x62,0xfb,0xf6,0xa5,0x20,0x00,0x00,0x00 # mulx 8*4($nptr),%rax,%r12
  2947. adcx %rax,%r11
  2948. adox %r13,%r12
  2949. mulx 8*5($nptr),%rax,%r13
  2950. adcx %rax,%r12
  2951. adox %r14,%r13
  2952. mulx 8*6($nptr),%rax,%r14
  2953. adcx %rax,%r13
  2954. adox %r15,%r14
  2955. mulx 8*7($nptr),%rax,%r15
  2956. mov 72+48+8(%rsp,%rcx,8),%rdx # pull n0*a[i]
  2957. adcx %rax,%r14
  2958. adox $carry,%r15
  2959. mov %rbx,($tptr,%rcx,8) # save result
  2960. mov %r8,%rbx
  2961. adcx $carry,%r15 # cf=0
  2962. inc %rcx # of=0
  2963. jnz .Lsqrx8x_tail
  2964. cmp 0+8(%rsp),$nptr # end of n[]?
  2965. jae .Lsqrx8x_tail_done # break out of loop
  2966. sub 16+8(%rsp),$carry # mov 16(%rsp),%cf
  2967. mov 48+8(%rsp),%rdx # pull n0*a[0]
  2968. lea 8*8($nptr),$nptr
  2969. adc 8*0($tptr),%r8
  2970. adc 8*1($tptr),%r9
  2971. adc 8*2($tptr),%r10
  2972. adc 8*3($tptr),%r11
  2973. adc 8*4($tptr),%r12
  2974. adc 8*5($tptr),%r13
  2975. adc 8*6($tptr),%r14
  2976. adc 8*7($tptr),%r15
  2977. lea 8*8($tptr),$tptr
  2978. sbb %rax,%rax
  2979. sub \$8,%rcx # mov \$-8,%rcx
  2980. xor $carry,$carry # of=0, cf=0
  2981. mov %rax,16+8(%rsp)
  2982. jmp .Lsqrx8x_tail
  2983. .align 32
  2984. .Lsqrx8x_tail_done:
  2985. xor %rax,%rax
  2986. add 24+8(%rsp),%r8 # can this overflow?
  2987. adc \$0,%r9
  2988. adc \$0,%r10
  2989. adc \$0,%r11
  2990. adc \$0,%r12
  2991. adc \$0,%r13
  2992. adc \$0,%r14
  2993. adc \$0,%r15
  2994. adc \$0,%rax
  2995. sub 16+8(%rsp),$carry # mov 16(%rsp),%cf
  2996. .Lsqrx8x_no_tail: # %cf is 0 if jumped here
  2997. adc 8*0($tptr),%r8
  2998. movq %xmm3,%rcx
  2999. adc 8*1($tptr),%r9
  3000. mov 8*7($nptr),$carry
  3001. movq %xmm2,$nptr # restore $nptr
  3002. adc 8*2($tptr),%r10
  3003. adc 8*3($tptr),%r11
  3004. adc 8*4($tptr),%r12
  3005. adc 8*5($tptr),%r13
  3006. adc 8*6($tptr),%r14
  3007. adc 8*7($tptr),%r15
  3008. adc \$0,%rax # top-most carry
  3009. mov 32+8(%rsp),%rbx # n0
  3010. mov 8*8($tptr,%rcx),%rdx # modulo-scheduled "%r8"
  3011. mov %r8,8*0($tptr) # store top 512 bits
  3012. lea 8*8($tptr),%r8 # borrow %r8
  3013. mov %r9,8*1($tptr)
  3014. mov %r10,8*2($tptr)
  3015. mov %r11,8*3($tptr)
  3016. mov %r12,8*4($tptr)
  3017. mov %r13,8*5($tptr)
  3018. mov %r14,8*6($tptr)
  3019. mov %r15,8*7($tptr)
  3020. lea 8*8($tptr,%rcx),$tptr # start of current t[] window
  3021. cmp 8+8(%rsp),%r8 # end of t[]?
  3022. jb .Lsqrx8x_reduction_loop
  3023. ret
  3024. .cfi_endproc
  3025. .size bn_sqrx8x_internal,.-bn_sqrx8x_internal
  3026. ___
  3027. }
  3028. ##############################################################
  3029. # Post-condition, 4x unrolled
  3030. #
  3031. {
  3032. my ($rptr,$nptr)=("%rdx","%rbp");
  3033. $code.=<<___;
  3034. .align 32
  3035. __bn_postx4x_internal:
  3036. .cfi_startproc
  3037. mov 8*0($nptr),%r12
  3038. mov %rcx,%r10 # -$num
  3039. mov %rcx,%r9 # -$num
  3040. neg %rax
  3041. sar \$3+2,%rcx
  3042. #lea 48+8(%rsp,%r9),$tptr
  3043. movq %xmm1,$rptr # restore $rptr
  3044. movq %xmm1,$aptr # prepare for back-to-back call
  3045. dec %r12 # so that after 'not' we get -n[0]
  3046. mov 8*1($nptr),%r13
  3047. xor %r8,%r8
  3048. mov 8*2($nptr),%r14
  3049. mov 8*3($nptr),%r15
  3050. jmp .Lsqrx4x_sub_entry
  3051. .align 16
  3052. .Lsqrx4x_sub:
  3053. mov 8*0($nptr),%r12
  3054. mov 8*1($nptr),%r13
  3055. mov 8*2($nptr),%r14
  3056. mov 8*3($nptr),%r15
  3057. .Lsqrx4x_sub_entry:
  3058. andn %rax,%r12,%r12
  3059. lea 8*4($nptr),$nptr
  3060. andn %rax,%r13,%r13
  3061. andn %rax,%r14,%r14
  3062. andn %rax,%r15,%r15
  3063. neg %r8 # mov %r8,%cf
  3064. adc 8*0($tptr),%r12
  3065. adc 8*1($tptr),%r13
  3066. adc 8*2($tptr),%r14
  3067. adc 8*3($tptr),%r15
  3068. mov %r12,8*0($rptr)
  3069. lea 8*4($tptr),$tptr
  3070. mov %r13,8*1($rptr)
  3071. sbb %r8,%r8 # mov %cf,%r8
  3072. mov %r14,8*2($rptr)
  3073. mov %r15,8*3($rptr)
  3074. lea 8*4($rptr),$rptr
  3075. inc %rcx
  3076. jnz .Lsqrx4x_sub
  3077. neg %r9 # restore $num
  3078. ret
  3079. .cfi_endproc
  3080. .size __bn_postx4x_internal,.-__bn_postx4x_internal
  3081. ___
  3082. }
  3083. }}}
  3084. {
  3085. my ($inp,$num,$tbl,$idx)=$win64?("%rcx","%edx","%r8", "%r9d") : # Win64 order
  3086. ("%rdi","%esi","%rdx","%ecx"); # Unix order
  3087. my $out=$inp;
  3088. my $STRIDE=2**5*8;
  3089. my $N=$STRIDE/4;
  3090. $code.=<<___;
  3091. .globl bn_get_bits5
  3092. .type bn_get_bits5,\@abi-omnipotent
  3093. .align 16
  3094. bn_get_bits5:
  3095. .cfi_startproc
  3096. lea 0($inp),%r10
  3097. lea 1($inp),%r11
  3098. mov $num,%ecx
  3099. shr \$4,$num
  3100. and \$15,%ecx
  3101. lea -8(%ecx),%eax
  3102. cmp \$11,%ecx
  3103. cmova %r11,%r10
  3104. cmova %eax,%ecx
  3105. movzw (%r10,$num,2),%eax
  3106. shrl %cl,%eax
  3107. and \$31,%eax
  3108. ret
  3109. .cfi_endproc
  3110. .size bn_get_bits5,.-bn_get_bits5
  3111. .globl bn_scatter5
  3112. .type bn_scatter5,\@abi-omnipotent
  3113. .align 16
  3114. bn_scatter5:
  3115. .cfi_startproc
  3116. cmp \$0, $num
  3117. jz .Lscatter_epilogue
  3118. lea ($tbl,$idx,8),$tbl
  3119. .Lscatter:
  3120. mov ($inp),%rax
  3121. lea 8($inp),$inp
  3122. mov %rax,($tbl)
  3123. lea 32*8($tbl),$tbl
  3124. sub \$1,$num
  3125. jnz .Lscatter
  3126. .Lscatter_epilogue:
  3127. ret
  3128. .cfi_endproc
  3129. .size bn_scatter5,.-bn_scatter5
  3130. .globl bn_gather5
  3131. .type bn_gather5,\@abi-omnipotent
  3132. .align 32
  3133. bn_gather5:
  3134. .LSEH_begin_bn_gather5: # Win64 thing, but harmless in other cases
  3135. .cfi_startproc
  3136. # I can't trust assembler to use specific encoding:-(
  3137. .byte 0x4c,0x8d,0x14,0x24 #lea (%rsp),%r10
  3138. .byte 0x48,0x81,0xec,0x08,0x01,0x00,0x00 #sub $0x108,%rsp
  3139. lea .Linc(%rip),%rax
  3140. and \$-16,%rsp # shouldn't be formally required
  3141. movd $idx,%xmm5
  3142. movdqa 0(%rax),%xmm0 # 00000001000000010000000000000000
  3143. movdqa 16(%rax),%xmm1 # 00000002000000020000000200000002
  3144. lea 128($tbl),%r11 # size optimization
  3145. lea 128(%rsp),%rax # size optimization
  3146. pshufd \$0,%xmm5,%xmm5 # broadcast $idx
  3147. movdqa %xmm1,%xmm4
  3148. movdqa %xmm1,%xmm2
  3149. ___
  3150. ########################################################################
  3151. # calculate mask by comparing 0..31 to $idx and save result to stack
  3152. #
  3153. for($i=0;$i<$STRIDE/16;$i+=4) {
  3154. $code.=<<___;
  3155. paddd %xmm0,%xmm1
  3156. pcmpeqd %xmm5,%xmm0 # compare to 1,0
  3157. ___
  3158. $code.=<<___ if ($i);
  3159. movdqa %xmm3,`16*($i-1)-128`(%rax)
  3160. ___
  3161. $code.=<<___;
  3162. movdqa %xmm4,%xmm3
  3163. paddd %xmm1,%xmm2
  3164. pcmpeqd %xmm5,%xmm1 # compare to 3,2
  3165. movdqa %xmm0,`16*($i+0)-128`(%rax)
  3166. movdqa %xmm4,%xmm0
  3167. paddd %xmm2,%xmm3
  3168. pcmpeqd %xmm5,%xmm2 # compare to 5,4
  3169. movdqa %xmm1,`16*($i+1)-128`(%rax)
  3170. movdqa %xmm4,%xmm1
  3171. paddd %xmm3,%xmm0
  3172. pcmpeqd %xmm5,%xmm3 # compare to 7,6
  3173. movdqa %xmm2,`16*($i+2)-128`(%rax)
  3174. movdqa %xmm4,%xmm2
  3175. ___
  3176. }
  3177. $code.=<<___;
  3178. movdqa %xmm3,`16*($i-1)-128`(%rax)
  3179. jmp .Lgather
  3180. .align 32
  3181. .Lgather:
  3182. pxor %xmm4,%xmm4
  3183. pxor %xmm5,%xmm5
  3184. ___
  3185. for($i=0;$i<$STRIDE/16;$i+=4) {
  3186. $code.=<<___;
  3187. movdqa `16*($i+0)-128`(%r11),%xmm0
  3188. movdqa `16*($i+1)-128`(%r11),%xmm1
  3189. movdqa `16*($i+2)-128`(%r11),%xmm2
  3190. pand `16*($i+0)-128`(%rax),%xmm0
  3191. movdqa `16*($i+3)-128`(%r11),%xmm3
  3192. pand `16*($i+1)-128`(%rax),%xmm1
  3193. por %xmm0,%xmm4
  3194. pand `16*($i+2)-128`(%rax),%xmm2
  3195. por %xmm1,%xmm5
  3196. pand `16*($i+3)-128`(%rax),%xmm3
  3197. por %xmm2,%xmm4
  3198. por %xmm3,%xmm5
  3199. ___
  3200. }
  3201. $code.=<<___;
  3202. por %xmm5,%xmm4
  3203. lea $STRIDE(%r11),%r11
  3204. pshufd \$0x4e,%xmm4,%xmm0
  3205. por %xmm4,%xmm0
  3206. movq %xmm0,($out) # m0=bp[0]
  3207. lea 8($out),$out
  3208. sub \$1,$num
  3209. jnz .Lgather
  3210. lea (%r10),%rsp
  3211. ret
  3212. .LSEH_end_bn_gather5:
  3213. .cfi_endproc
  3214. .size bn_gather5,.-bn_gather5
  3215. ___
  3216. }
  3217. $code.=<<___;
  3218. .align 64
  3219. .Linc:
  3220. .long 0,0, 1,1
  3221. .long 2,2, 2,2
  3222. .asciz "Montgomery Multiplication with scatter/gather for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
  3223. ___
  3224. # EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
  3225. # CONTEXT *context,DISPATCHER_CONTEXT *disp)
  3226. if ($win64) {
  3227. $rec="%rcx";
  3228. $frame="%rdx";
  3229. $context="%r8";
  3230. $disp="%r9";
  3231. $code.=<<___;
  3232. .extern __imp_RtlVirtualUnwind
  3233. .type mul_handler,\@abi-omnipotent
  3234. .align 16
  3235. mul_handler:
  3236. push %rsi
  3237. push %rdi
  3238. push %rbx
  3239. push %rbp
  3240. push %r12
  3241. push %r13
  3242. push %r14
  3243. push %r15
  3244. pushfq
  3245. sub \$64,%rsp
  3246. mov 120($context),%rax # pull context->Rax
  3247. mov 248($context),%rbx # pull context->Rip
  3248. mov 8($disp),%rsi # disp->ImageBase
  3249. mov 56($disp),%r11 # disp->HandlerData
  3250. mov 0(%r11),%r10d # HandlerData[0]
  3251. lea (%rsi,%r10),%r10 # end of prologue label
  3252. cmp %r10,%rbx # context->Rip<end of prologue label
  3253. jb .Lcommon_seh_tail
  3254. mov 4(%r11),%r10d # HandlerData[1]
  3255. lea (%rsi,%r10),%r10 # beginning of body label
  3256. cmp %r10,%rbx # context->Rip<body label
  3257. jb .Lcommon_pop_regs
  3258. mov 152($context),%rax # pull context->Rsp
  3259. mov 8(%r11),%r10d # HandlerData[2]
  3260. lea (%rsi,%r10),%r10 # epilogue label
  3261. cmp %r10,%rbx # context->Rip>=epilogue label
  3262. jae .Lcommon_seh_tail
  3263. lea .Lmul_epilogue(%rip),%r10
  3264. cmp %r10,%rbx
  3265. ja .Lbody_40
  3266. mov 192($context),%r10 # pull $num
  3267. mov 8(%rax,%r10,8),%rax # pull saved stack pointer
  3268. jmp .Lcommon_pop_regs
  3269. .Lbody_40:
  3270. mov 40(%rax),%rax # pull saved stack pointer
  3271. .Lcommon_pop_regs:
  3272. mov -8(%rax),%rbx
  3273. mov -16(%rax),%rbp
  3274. mov -24(%rax),%r12
  3275. mov -32(%rax),%r13
  3276. mov -40(%rax),%r14
  3277. mov -48(%rax),%r15
  3278. mov %rbx,144($context) # restore context->Rbx
  3279. mov %rbp,160($context) # restore context->Rbp
  3280. mov %r12,216($context) # restore context->R12
  3281. mov %r13,224($context) # restore context->R13
  3282. mov %r14,232($context) # restore context->R14
  3283. mov %r15,240($context) # restore context->R15
  3284. .Lcommon_seh_tail:
  3285. mov 8(%rax),%rdi
  3286. mov 16(%rax),%rsi
  3287. mov %rax,152($context) # restore context->Rsp
  3288. mov %rsi,168($context) # restore context->Rsi
  3289. mov %rdi,176($context) # restore context->Rdi
  3290. mov 40($disp),%rdi # disp->ContextRecord
  3291. mov $context,%rsi # context
  3292. mov \$154,%ecx # sizeof(CONTEXT)
  3293. .long 0xa548f3fc # cld; rep movsq
  3294. mov $disp,%rsi
  3295. xor %rcx,%rcx # arg1, UNW_FLAG_NHANDLER
  3296. mov 8(%rsi),%rdx # arg2, disp->ImageBase
  3297. mov 0(%rsi),%r8 # arg3, disp->ControlPc
  3298. mov 16(%rsi),%r9 # arg4, disp->FunctionEntry
  3299. mov 40(%rsi),%r10 # disp->ContextRecord
  3300. lea 56(%rsi),%r11 # &disp->HandlerData
  3301. lea 24(%rsi),%r12 # &disp->EstablisherFrame
  3302. mov %r10,32(%rsp) # arg5
  3303. mov %r11,40(%rsp) # arg6
  3304. mov %r12,48(%rsp) # arg7
  3305. mov %rcx,56(%rsp) # arg8, (NULL)
  3306. call *__imp_RtlVirtualUnwind(%rip)
  3307. mov \$1,%eax # ExceptionContinueSearch
  3308. add \$64,%rsp
  3309. popfq
  3310. pop %r15
  3311. pop %r14
  3312. pop %r13
  3313. pop %r12
  3314. pop %rbp
  3315. pop %rbx
  3316. pop %rdi
  3317. pop %rsi
  3318. ret
  3319. .size mul_handler,.-mul_handler
  3320. .section .pdata
  3321. .align 4
  3322. .rva .LSEH_begin_bn_mul_mont_gather5
  3323. .rva .LSEH_end_bn_mul_mont_gather5
  3324. .rva .LSEH_info_bn_mul_mont_gather5
  3325. .rva .LSEH_begin_bn_mul4x_mont_gather5
  3326. .rva .LSEH_end_bn_mul4x_mont_gather5
  3327. .rva .LSEH_info_bn_mul4x_mont_gather5
  3328. .rva .LSEH_begin_bn_power5
  3329. .rva .LSEH_end_bn_power5
  3330. .rva .LSEH_info_bn_power5
  3331. ___
  3332. $code.=<<___ if ($addx);
  3333. .rva .LSEH_begin_bn_mulx4x_mont_gather5
  3334. .rva .LSEH_end_bn_mulx4x_mont_gather5
  3335. .rva .LSEH_info_bn_mulx4x_mont_gather5
  3336. .rva .LSEH_begin_bn_powerx5
  3337. .rva .LSEH_end_bn_powerx5
  3338. .rva .LSEH_info_bn_powerx5
  3339. ___
  3340. $code.=<<___;
  3341. .rva .LSEH_begin_bn_gather5
  3342. .rva .LSEH_end_bn_gather5
  3343. .rva .LSEH_info_bn_gather5
  3344. .section .xdata
  3345. .align 8
  3346. .LSEH_info_bn_mul_mont_gather5:
  3347. .byte 9,0,0,0
  3348. .rva mul_handler
  3349. .rva .Lmul_body,.Lmul_body,.Lmul_epilogue # HandlerData[]
  3350. .align 8
  3351. .LSEH_info_bn_mul4x_mont_gather5:
  3352. .byte 9,0,0,0
  3353. .rva mul_handler
  3354. .rva .Lmul4x_prologue,.Lmul4x_body,.Lmul4x_epilogue # HandlerData[]
  3355. .align 8
  3356. .LSEH_info_bn_power5:
  3357. .byte 9,0,0,0
  3358. .rva mul_handler
  3359. .rva .Lpower5_prologue,.Lpower5_body,.Lpower5_epilogue # HandlerData[]
  3360. ___
  3361. $code.=<<___ if ($addx);
  3362. .align 8
  3363. .LSEH_info_bn_mulx4x_mont_gather5:
  3364. .byte 9,0,0,0
  3365. .rva mul_handler
  3366. .rva .Lmulx4x_prologue,.Lmulx4x_body,.Lmulx4x_epilogue # HandlerData[]
  3367. .align 8
  3368. .LSEH_info_bn_powerx5:
  3369. .byte 9,0,0,0
  3370. .rva mul_handler
  3371. .rva .Lpowerx5_prologue,.Lpowerx5_body,.Lpowerx5_epilogue # HandlerData[]
  3372. ___
  3373. $code.=<<___;
  3374. .align 8
  3375. .LSEH_info_bn_gather5:
  3376. .byte 0x01,0x0b,0x03,0x0a
  3377. .byte 0x0b,0x01,0x21,0x00 # sub rsp,0x108
  3378. .byte 0x04,0xa3,0x00,0x00 # lea r10,(rsp)
  3379. .align 8
  3380. ___
  3381. }
  3382. $code =~ s/\`([^\`]*)\`/eval($1)/gem;
  3383. print $code;
  3384. close STDOUT or die "error closing STDOUT: $!";