s390x-mont.pl 6.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277
  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 2007.
  9. #
  10. # Performance improvement over vanilla C code varies from 85% to 45%
  11. # depending on key length and benchmark. Unfortunately in this context
  12. # these are not very impressive results [for code that utilizes "wide"
  13. # 64x64=128-bit multiplication, which is not commonly available to C
  14. # programmers], at least hand-coded bn_asm.c replacement is known to
  15. # provide 30-40% better results for longest keys. Well, on a second
  16. # thought it's not very surprising, because z-CPUs are single-issue
  17. # and _strictly_ in-order execution, while bn_mul_mont is more or less
  18. # dependent on CPU ability to pipe-line instructions and have several
  19. # of them "in-flight" at the same time. I mean while other methods,
  20. # for example Karatsuba, aim to minimize amount of multiplications at
  21. # the cost of other operations increase, bn_mul_mont aim to neatly
  22. # "overlap" multiplications and the other operations [and on most
  23. # platforms even minimize the amount of the other operations, in
  24. # particular references to memory]. But it's possible to improve this
  25. # module performance by implementing dedicated squaring code-path and
  26. # possibly by unrolling loops...
  27. # January 2009.
  28. #
  29. # Reschedule to minimize/avoid Address Generation Interlock hazard,
  30. # make inner loops counter-based.
  31. # November 2010.
  32. #
  33. # Adapt for -m31 build. If kernel supports what's called "highgprs"
  34. # feature on Linux [see /proc/cpuinfo], it's possible to use 64-bit
  35. # instructions and achieve "64-bit" performance even in 31-bit legacy
  36. # application context. The feature is not specific to any particular
  37. # processor, as long as it's "z-CPU". Latter implies that the code
  38. # remains z/Architecture specific. Compatibility with 32-bit BN_ULONG
  39. # is achieved by swapping words after 64-bit loads, follow _dswap-s.
  40. # On z990 it was measured to perform 2.6-2.2 times better than
  41. # compiler-generated code, less for longer keys...
  42. $flavour = shift;
  43. if ($flavour =~ /3[12]/) {
  44. $SIZE_T=4;
  45. $g="";
  46. } else {
  47. $SIZE_T=8;
  48. $g="g";
  49. }
  50. while (($output=shift) && ($output!~/^\w[\w\-]*\.\w+$/)) {}
  51. open STDOUT,">$output";
  52. $stdframe=16*$SIZE_T+4*8;
  53. $mn0="%r0";
  54. $num="%r1";
  55. # int bn_mul_mont(
  56. $rp="%r2"; # BN_ULONG *rp,
  57. $ap="%r3"; # const BN_ULONG *ap,
  58. $bp="%r4"; # const BN_ULONG *bp,
  59. $np="%r5"; # const BN_ULONG *np,
  60. $n0="%r6"; # const BN_ULONG *n0,
  61. #$num="160(%r15)" # int num);
  62. $bi="%r2"; # zaps rp
  63. $j="%r7";
  64. $ahi="%r8";
  65. $alo="%r9";
  66. $nhi="%r10";
  67. $nlo="%r11";
  68. $AHI="%r12";
  69. $NHI="%r13";
  70. $count="%r14";
  71. $sp="%r15";
  72. $code.=<<___;
  73. .text
  74. .globl bn_mul_mont
  75. .type bn_mul_mont,\@function
  76. bn_mul_mont:
  77. lgf $num,`$stdframe+$SIZE_T-4`($sp) # pull $num
  78. sla $num,`log($SIZE_T)/log(2)` # $num to enumerate bytes
  79. la $bp,0($num,$bp)
  80. st${g} %r2,2*$SIZE_T($sp)
  81. cghi $num,16 #
  82. lghi %r2,0 #
  83. blr %r14 # if($num<16) return 0;
  84. ___
  85. $code.=<<___ if ($flavour =~ /3[12]/);
  86. tmll $num,4
  87. bnzr %r14 # if ($num&1) return 0;
  88. ___
  89. $code.=<<___ if ($flavour !~ /3[12]/);
  90. cghi $num,96 #
  91. bhr %r14 # if($num>96) return 0;
  92. ___
  93. $code.=<<___;
  94. stm${g} %r3,%r15,3*$SIZE_T($sp)
  95. lghi $rp,-$stdframe-8 # leave room for carry bit
  96. lcgr $j,$num # -$num
  97. lgr %r0,$sp
  98. la $rp,0($rp,$sp)
  99. la $sp,0($j,$rp) # alloca
  100. st${g} %r0,0($sp) # back chain
  101. sra $num,3 # restore $num
  102. la $bp,0($j,$bp) # restore $bp
  103. ahi $num,-1 # adjust $num for inner loop
  104. lg $n0,0($n0) # pull n0
  105. _dswap $n0
  106. lg $bi,0($bp)
  107. _dswap $bi
  108. lg $alo,0($ap)
  109. _dswap $alo
  110. mlgr $ahi,$bi # ap[0]*bp[0]
  111. lgr $AHI,$ahi
  112. lgr $mn0,$alo # "tp[0]"*n0
  113. msgr $mn0,$n0
  114. lg $nlo,0($np) #
  115. _dswap $nlo
  116. mlgr $nhi,$mn0 # np[0]*m1
  117. algr $nlo,$alo # +="tp[0]"
  118. lghi $NHI,0
  119. alcgr $NHI,$nhi
  120. la $j,8(%r0) # j=1
  121. lr $count,$num
  122. .align 16
  123. .L1st:
  124. lg $alo,0($j,$ap)
  125. _dswap $alo
  126. mlgr $ahi,$bi # ap[j]*bp[0]
  127. algr $alo,$AHI
  128. lghi $AHI,0
  129. alcgr $AHI,$ahi
  130. lg $nlo,0($j,$np)
  131. _dswap $nlo
  132. mlgr $nhi,$mn0 # np[j]*m1
  133. algr $nlo,$NHI
  134. lghi $NHI,0
  135. alcgr $nhi,$NHI # +="tp[j]"
  136. algr $nlo,$alo
  137. alcgr $NHI,$nhi
  138. stg $nlo,$stdframe-8($j,$sp) # tp[j-1]=
  139. la $j,8($j) # j++
  140. brct $count,.L1st
  141. algr $NHI,$AHI
  142. lghi $AHI,0
  143. alcgr $AHI,$AHI # upmost overflow bit
  144. stg $NHI,$stdframe-8($j,$sp)
  145. stg $AHI,$stdframe($j,$sp)
  146. la $bp,8($bp) # bp++
  147. .Louter:
  148. lg $bi,0($bp) # bp[i]
  149. _dswap $bi
  150. lg $alo,0($ap)
  151. _dswap $alo
  152. mlgr $ahi,$bi # ap[0]*bp[i]
  153. alg $alo,$stdframe($sp) # +=tp[0]
  154. lghi $AHI,0
  155. alcgr $AHI,$ahi
  156. lgr $mn0,$alo
  157. msgr $mn0,$n0 # tp[0]*n0
  158. lg $nlo,0($np) # np[0]
  159. _dswap $nlo
  160. mlgr $nhi,$mn0 # np[0]*m1
  161. algr $nlo,$alo # +="tp[0]"
  162. lghi $NHI,0
  163. alcgr $NHI,$nhi
  164. la $j,8(%r0) # j=1
  165. lr $count,$num
  166. .align 16
  167. .Linner:
  168. lg $alo,0($j,$ap)
  169. _dswap $alo
  170. mlgr $ahi,$bi # ap[j]*bp[i]
  171. algr $alo,$AHI
  172. lghi $AHI,0
  173. alcgr $ahi,$AHI
  174. alg $alo,$stdframe($j,$sp)# +=tp[j]
  175. alcgr $AHI,$ahi
  176. lg $nlo,0($j,$np)
  177. _dswap $nlo
  178. mlgr $nhi,$mn0 # np[j]*m1
  179. algr $nlo,$NHI
  180. lghi $NHI,0
  181. alcgr $nhi,$NHI
  182. algr $nlo,$alo # +="tp[j]"
  183. alcgr $NHI,$nhi
  184. stg $nlo,$stdframe-8($j,$sp) # tp[j-1]=
  185. la $j,8($j) # j++
  186. brct $count,.Linner
  187. algr $NHI,$AHI
  188. lghi $AHI,0
  189. alcgr $AHI,$AHI
  190. alg $NHI,$stdframe($j,$sp)# accumulate previous upmost overflow bit
  191. lghi $ahi,0
  192. alcgr $AHI,$ahi # new upmost overflow bit
  193. stg $NHI,$stdframe-8($j,$sp)
  194. stg $AHI,$stdframe($j,$sp)
  195. la $bp,8($bp) # bp++
  196. cl${g} $bp,`$stdframe+8+4*$SIZE_T`($j,$sp) # compare to &bp[num]
  197. jne .Louter
  198. l${g} $rp,`$stdframe+8+2*$SIZE_T`($j,$sp) # reincarnate rp
  199. la $ap,$stdframe($sp)
  200. ahi $num,1 # restore $num, incidentally clears "borrow"
  201. la $j,0(%r0)
  202. lr $count,$num
  203. .Lsub: lg $alo,0($j,$ap)
  204. lg $nlo,0($j,$np)
  205. _dswap $nlo
  206. slbgr $alo,$nlo
  207. stg $alo,0($j,$rp)
  208. la $j,8($j)
  209. brct $count,.Lsub
  210. lghi $ahi,0
  211. slbgr $AHI,$ahi # handle upmost carry
  212. ngr $ap,$AHI
  213. lghi $np,-1
  214. xgr $np,$AHI
  215. ngr $np,$rp
  216. ogr $ap,$np # ap=borrow?tp:rp
  217. la $j,0(%r0)
  218. lgr $count,$num
  219. .Lcopy: lg $alo,0($j,$ap) # copy or in-place refresh
  220. _dswap $alo
  221. stg $j,$stdframe($j,$sp) # zap tp
  222. stg $alo,0($j,$rp)
  223. la $j,8($j)
  224. brct $count,.Lcopy
  225. la %r1,`$stdframe+8+6*$SIZE_T`($j,$sp)
  226. lm${g} %r6,%r15,0(%r1)
  227. lghi %r2,1 # signal "processed"
  228. br %r14
  229. .size bn_mul_mont,.-bn_mul_mont
  230. .string "Montgomery Multiplication for s390x, CRYPTOGAMS by <appro\@openssl.org>"
  231. ___
  232. foreach (split("\n",$code)) {
  233. s/\`([^\`]*)\`/eval $1/ge;
  234. s/_dswap\s+(%r[0-9]+)/sprintf("rllg\t%s,%s,32",$1,$1) if($SIZE_T==4)/e;
  235. print $_,"\n";
  236. }
  237. close STDOUT;