ppc-mont.pl 7.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335
  1. #!/usr/bin/env perl
  2. # ====================================================================
  3. # Written by Andy Polyakov <appro@fy.chalmers.se> for the OpenSSL
  4. # project. The module is, however, dual licensed under OpenSSL and
  5. # CRYPTOGAMS licenses depending on where you obtain it. For further
  6. # details see http://www.openssl.org/~appro/cryptogams/.
  7. # ====================================================================
  8. # April 2006
  9. # "Teaser" Montgomery multiplication module for PowerPC. It's possible
  10. # to gain a bit more by modulo-scheduling outer loop, then dedicated
  11. # squaring procedure should give further 20% and code can be adapted
  12. # for 32-bit application running on 64-bit CPU. As for the latter.
  13. # It won't be able to achieve "native" 64-bit performance, because in
  14. # 32-bit application context every addc instruction will have to be
  15. # expanded as addc, twice right shift by 32 and finally adde, etc.
  16. # So far RSA *sign* performance improvement over pre-bn_mul_mont asm
  17. # for 64-bit application running on PPC970/G5 is:
  18. #
  19. # 512-bit +65%
  20. # 1024-bit +35%
  21. # 2048-bit +18%
  22. # 4096-bit +4%
  23. $flavour = shift;
  24. if ($flavour =~ /32/) {
  25. $BITS= 32;
  26. $BNSZ= $BITS/8;
  27. $SIZE_T=4;
  28. $RZONE= 224;
  29. $LD= "lwz"; # load
  30. $LDU= "lwzu"; # load and update
  31. $LDX= "lwzx"; # load indexed
  32. $ST= "stw"; # store
  33. $STU= "stwu"; # store and update
  34. $STX= "stwx"; # store indexed
  35. $STUX= "stwux"; # store indexed and update
  36. $UMULL= "mullw"; # unsigned multiply low
  37. $UMULH= "mulhwu"; # unsigned multiply high
  38. $UCMP= "cmplw"; # unsigned compare
  39. $SHRI= "srwi"; # unsigned shift right by immediate
  40. $PUSH= $ST;
  41. $POP= $LD;
  42. } elsif ($flavour =~ /64/) {
  43. $BITS= 64;
  44. $BNSZ= $BITS/8;
  45. $SIZE_T=8;
  46. $RZONE= 288;
  47. # same as above, but 64-bit mnemonics...
  48. $LD= "ld"; # load
  49. $LDU= "ldu"; # load and update
  50. $LDX= "ldx"; # load indexed
  51. $ST= "std"; # store
  52. $STU= "stdu"; # store and update
  53. $STX= "stdx"; # store indexed
  54. $STUX= "stdux"; # store indexed and update
  55. $UMULL= "mulld"; # unsigned multiply low
  56. $UMULH= "mulhdu"; # unsigned multiply high
  57. $UCMP= "cmpld"; # unsigned compare
  58. $SHRI= "srdi"; # unsigned shift right by immediate
  59. $PUSH= $ST;
  60. $POP= $LD;
  61. } else { die "nonsense $flavour"; }
  62. $FRAME=8*$SIZE_T+$RZONE;
  63. $LOCALS=8*$SIZE_T;
  64. $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
  65. ( $xlate="${dir}ppc-xlate.pl" and -f $xlate ) or
  66. ( $xlate="${dir}../../perlasm/ppc-xlate.pl" and -f $xlate) or
  67. die "can't locate ppc-xlate.pl";
  68. open STDOUT,"| $^X $xlate $flavour ".shift || die "can't call $xlate: $!";
  69. $sp="r1";
  70. $toc="r2";
  71. $rp="r3"; $ovf="r3";
  72. $ap="r4";
  73. $bp="r5";
  74. $np="r6";
  75. $n0="r7";
  76. $num="r8";
  77. $rp="r9"; # $rp is reassigned
  78. $aj="r10";
  79. $nj="r11";
  80. $tj="r12";
  81. # non-volatile registers
  82. $i="r20";
  83. $j="r21";
  84. $tp="r22";
  85. $m0="r23";
  86. $m1="r24";
  87. $lo0="r25";
  88. $hi0="r26";
  89. $lo1="r27";
  90. $hi1="r28";
  91. $alo="r29";
  92. $ahi="r30";
  93. $nlo="r31";
  94. #
  95. $nhi="r0";
  96. $code=<<___;
  97. .machine "any"
  98. .text
  99. .globl .bn_mul_mont_int
  100. .align 4
  101. .bn_mul_mont_int:
  102. cmpwi $num,4
  103. mr $rp,r3 ; $rp is reassigned
  104. li r3,0
  105. bltlr
  106. ___
  107. $code.=<<___ if ($BNSZ==4);
  108. cmpwi $num,32 ; longer key performance is not better
  109. bgelr
  110. ___
  111. $code.=<<___;
  112. slwi $num,$num,`log($BNSZ)/log(2)`
  113. li $tj,-4096
  114. addi $ovf,$num,$FRAME
  115. subf $ovf,$ovf,$sp ; $sp-$ovf
  116. and $ovf,$ovf,$tj ; minimize TLB usage
  117. subf $ovf,$sp,$ovf ; $ovf-$sp
  118. mr $tj,$sp
  119. srwi $num,$num,`log($BNSZ)/log(2)`
  120. $STUX $sp,$sp,$ovf
  121. $PUSH r20,`-12*$SIZE_T`($tj)
  122. $PUSH r21,`-11*$SIZE_T`($tj)
  123. $PUSH r22,`-10*$SIZE_T`($tj)
  124. $PUSH r23,`-9*$SIZE_T`($tj)
  125. $PUSH r24,`-8*$SIZE_T`($tj)
  126. $PUSH r25,`-7*$SIZE_T`($tj)
  127. $PUSH r26,`-6*$SIZE_T`($tj)
  128. $PUSH r27,`-5*$SIZE_T`($tj)
  129. $PUSH r28,`-4*$SIZE_T`($tj)
  130. $PUSH r29,`-3*$SIZE_T`($tj)
  131. $PUSH r30,`-2*$SIZE_T`($tj)
  132. $PUSH r31,`-1*$SIZE_T`($tj)
  133. $LD $n0,0($n0) ; pull n0[0] value
  134. addi $num,$num,-2 ; adjust $num for counter register
  135. $LD $m0,0($bp) ; m0=bp[0]
  136. $LD $aj,0($ap) ; ap[0]
  137. addi $tp,$sp,$LOCALS
  138. $UMULL $lo0,$aj,$m0 ; ap[0]*bp[0]
  139. $UMULH $hi0,$aj,$m0
  140. $LD $aj,$BNSZ($ap) ; ap[1]
  141. $LD $nj,0($np) ; np[0]
  142. $UMULL $m1,$lo0,$n0 ; "tp[0]"*n0
  143. $UMULL $alo,$aj,$m0 ; ap[1]*bp[0]
  144. $UMULH $ahi,$aj,$m0
  145. $UMULL $lo1,$nj,$m1 ; np[0]*m1
  146. $UMULH $hi1,$nj,$m1
  147. $LD $nj,$BNSZ($np) ; np[1]
  148. addc $lo1,$lo1,$lo0
  149. addze $hi1,$hi1
  150. $UMULL $nlo,$nj,$m1 ; np[1]*m1
  151. $UMULH $nhi,$nj,$m1
  152. mtctr $num
  153. li $j,`2*$BNSZ`
  154. .align 4
  155. L1st:
  156. $LDX $aj,$ap,$j ; ap[j]
  157. addc $lo0,$alo,$hi0
  158. $LDX $nj,$np,$j ; np[j]
  159. addze $hi0,$ahi
  160. $UMULL $alo,$aj,$m0 ; ap[j]*bp[0]
  161. addc $lo1,$nlo,$hi1
  162. $UMULH $ahi,$aj,$m0
  163. addze $hi1,$nhi
  164. $UMULL $nlo,$nj,$m1 ; np[j]*m1
  165. addc $lo1,$lo1,$lo0 ; np[j]*m1+ap[j]*bp[0]
  166. $UMULH $nhi,$nj,$m1
  167. addze $hi1,$hi1
  168. $ST $lo1,0($tp) ; tp[j-1]
  169. addi $j,$j,$BNSZ ; j++
  170. addi $tp,$tp,$BNSZ ; tp++
  171. bdnz- L1st
  172. ;L1st
  173. addc $lo0,$alo,$hi0
  174. addze $hi0,$ahi
  175. addc $lo1,$nlo,$hi1
  176. addze $hi1,$nhi
  177. addc $lo1,$lo1,$lo0 ; np[j]*m1+ap[j]*bp[0]
  178. addze $hi1,$hi1
  179. $ST $lo1,0($tp) ; tp[j-1]
  180. li $ovf,0
  181. addc $hi1,$hi1,$hi0
  182. addze $ovf,$ovf ; upmost overflow bit
  183. $ST $hi1,$BNSZ($tp)
  184. li $i,$BNSZ
  185. .align 4
  186. Louter:
  187. $LDX $m0,$bp,$i ; m0=bp[i]
  188. $LD $aj,0($ap) ; ap[0]
  189. addi $tp,$sp,$LOCALS
  190. $LD $tj,$LOCALS($sp); tp[0]
  191. $UMULL $lo0,$aj,$m0 ; ap[0]*bp[i]
  192. $UMULH $hi0,$aj,$m0
  193. $LD $aj,$BNSZ($ap) ; ap[1]
  194. $LD $nj,0($np) ; np[0]
  195. addc $lo0,$lo0,$tj ; ap[0]*bp[i]+tp[0]
  196. $UMULL $alo,$aj,$m0 ; ap[j]*bp[i]
  197. addze $hi0,$hi0
  198. $UMULL $m1,$lo0,$n0 ; tp[0]*n0
  199. $UMULH $ahi,$aj,$m0
  200. $UMULL $lo1,$nj,$m1 ; np[0]*m1
  201. $UMULH $hi1,$nj,$m1
  202. $LD $nj,$BNSZ($np) ; np[1]
  203. addc $lo1,$lo1,$lo0
  204. $UMULL $nlo,$nj,$m1 ; np[1]*m1
  205. addze $hi1,$hi1
  206. $UMULH $nhi,$nj,$m1
  207. mtctr $num
  208. li $j,`2*$BNSZ`
  209. .align 4
  210. Linner:
  211. $LDX $aj,$ap,$j ; ap[j]
  212. addc $lo0,$alo,$hi0
  213. $LD $tj,$BNSZ($tp) ; tp[j]
  214. addze $hi0,$ahi
  215. $LDX $nj,$np,$j ; np[j]
  216. addc $lo1,$nlo,$hi1
  217. $UMULL $alo,$aj,$m0 ; ap[j]*bp[i]
  218. addze $hi1,$nhi
  219. $UMULH $ahi,$aj,$m0
  220. addc $lo0,$lo0,$tj ; ap[j]*bp[i]+tp[j]
  221. $UMULL $nlo,$nj,$m1 ; np[j]*m1
  222. addze $hi0,$hi0
  223. $UMULH $nhi,$nj,$m1
  224. addc $lo1,$lo1,$lo0 ; np[j]*m1+ap[j]*bp[i]+tp[j]
  225. addi $j,$j,$BNSZ ; j++
  226. addze $hi1,$hi1
  227. $ST $lo1,0($tp) ; tp[j-1]
  228. addi $tp,$tp,$BNSZ ; tp++
  229. bdnz- Linner
  230. ;Linner
  231. $LD $tj,$BNSZ($tp) ; tp[j]
  232. addc $lo0,$alo,$hi0
  233. addze $hi0,$ahi
  234. addc $lo0,$lo0,$tj ; ap[j]*bp[i]+tp[j]
  235. addze $hi0,$hi0
  236. addc $lo1,$nlo,$hi1
  237. addze $hi1,$nhi
  238. addc $lo1,$lo1,$lo0 ; np[j]*m1+ap[j]*bp[i]+tp[j]
  239. addze $hi1,$hi1
  240. $ST $lo1,0($tp) ; tp[j-1]
  241. addic $ovf,$ovf,-1 ; move upmost overflow to XER[CA]
  242. li $ovf,0
  243. adde $hi1,$hi1,$hi0
  244. addze $ovf,$ovf
  245. $ST $hi1,$BNSZ($tp)
  246. ;
  247. slwi $tj,$num,`log($BNSZ)/log(2)`
  248. $UCMP $i,$tj
  249. addi $i,$i,$BNSZ
  250. ble- Louter
  251. addi $num,$num,2 ; restore $num
  252. subfc $j,$j,$j ; j=0 and "clear" XER[CA]
  253. addi $tp,$sp,$LOCALS
  254. mtctr $num
  255. .align 4
  256. Lsub: $LDX $tj,$tp,$j
  257. $LDX $nj,$np,$j
  258. subfe $aj,$nj,$tj ; tp[j]-np[j]
  259. $STX $aj,$rp,$j
  260. addi $j,$j,$BNSZ
  261. bdnz- Lsub
  262. li $j,0
  263. mtctr $num
  264. subfe $ovf,$j,$ovf ; handle upmost overflow bit
  265. and $ap,$tp,$ovf
  266. andc $np,$rp,$ovf
  267. or $ap,$ap,$np ; ap=borrow?tp:rp
  268. .align 4
  269. Lcopy: ; copy or in-place refresh
  270. $LDX $tj,$ap,$j
  271. $STX $tj,$rp,$j
  272. $STX $j,$tp,$j ; zap at once
  273. addi $j,$j,$BNSZ
  274. bdnz- Lcopy
  275. $POP $tj,0($sp)
  276. li r3,1
  277. $POP r20,`-12*$SIZE_T`($tj)
  278. $POP r21,`-11*$SIZE_T`($tj)
  279. $POP r22,`-10*$SIZE_T`($tj)
  280. $POP r23,`-9*$SIZE_T`($tj)
  281. $POP r24,`-8*$SIZE_T`($tj)
  282. $POP r25,`-7*$SIZE_T`($tj)
  283. $POP r26,`-6*$SIZE_T`($tj)
  284. $POP r27,`-5*$SIZE_T`($tj)
  285. $POP r28,`-4*$SIZE_T`($tj)
  286. $POP r29,`-3*$SIZE_T`($tj)
  287. $POP r30,`-2*$SIZE_T`($tj)
  288. $POP r31,`-1*$SIZE_T`($tj)
  289. mr $sp,$tj
  290. blr
  291. .long 0
  292. .byte 0,12,4,0,0x80,12,6,0
  293. .long 0
  294. .size .bn_mul_mont_int,.-.bn_mul_mont_int
  295. .asciz "Montgomery Multiplication for PPC, CRYPTOGAMS by <appro\@openssl.org>"
  296. ___
  297. $code =~ s/\`([^\`]*)\`/eval $1/gem;
  298. print $code;
  299. close STDOUT;