3 # ====================================================================
4 # Written by Andy Polyakov <appro@fy.chalmers.se> for the OpenSSL
5 # project. The module is, however, dual licensed under OpenSSL and
6 # CRYPTOGAMS licenses depending on where you obtain it. For further
7 # details see http://www.openssl.org/~appro/cryptogams/.
8 # ====================================================================
12 # Performance improvement over vanilla C code varies from 85% to 45%
13 # depending on key length and benchmark. Unfortunately in this context
14 # these are not very impressive results [for code that utilizes "wide"
15 # 64x64=128-bit multiplication, which is not commonly available to C
16 # programmers], at least hand-coded bn_asm.c replacement is known to
17 # provide 30-40% better results for longest keys. Well, on a second
18 # thought it's not very surprising, because z-CPUs are single-issue
19 # and _strictly_ in-order execution, while bn_mul_mont is more or less
20 # dependent on CPU ability to pipe-line instructions and have several
21 # of them "in-flight" at the same time. I mean while other methods,
22 # for example Karatsuba, aim to minimize amount of multiplications at
23 # the cost of other operations increase, bn_mul_mont aim to neatly
24 # "overlap" multiplications and the other operations [and on most
25 # platforms even minimize the amount of the other operations, in
26 # particular references to memory]. But it's possible to improve this
27 # module performance by implementing dedicated squaring code-path and
28 # possibly by unrolling loops...
32 # Reschedule to minimize/avoid Address Generation Interlock hazard,
33 # make inner loops counter-based.
39 $rp="%r2"; # BN_ULONG *rp,
40 $ap="%r3"; # const BN_ULONG *ap,
41 $bp="%r4"; # const BN_ULONG *bp,
42 $np="%r5"; # const BN_ULONG *np,
43 $n0="%r6"; # const BN_ULONG *n0,
44 #$num="160(%r15)" # int num);
61 .type bn_mul_mont,\@function
63 lgf $num,164($sp) # pull $num
64 sla $num,3 # $num to enumerate bytes
71 blr %r14 # if($num<16) return 0;
73 bhr %r14 # if($num>128) return 0;
75 lghi $rp,-160-8 # leave room for carry bit
79 la $sp,0($j,$rp) # alloca
80 stg %r0,0($sp) # back chain
82 sra $num,3 # restore $num
83 la $bp,0($j,$bp) # restore $bp
84 ahi $num,-1 # adjust $num for inner loop
85 lg $n0,0($n0) # pull n0
89 mlgr $ahi,$bi # ap[0]*bp[0]
92 lgr $mn0,$alo # "tp[0]"*n0
96 mlgr $nhi,$mn0 # np[0]*m1
97 algr $nlo,$alo # +="tp[0]"
107 mlgr $ahi,$bi # ap[j]*bp[0]
113 mlgr $nhi,$mn0 # np[j]*m1
116 alcgr $nhi,$NHI # +="tp[j]"
120 stg $nlo,160-8($j,$sp) # tp[j-1]=
126 alcgr $AHI,$AHI # upmost overflow bit
127 stg $NHI,160-8($j,$sp)
132 lg $bi,0($bp) # bp[i]
134 mlgr $ahi,$bi # ap[0]*bp[i]
135 alg $alo,160($sp) # +=tp[0]
140 msgr $mn0,$n0 # tp[0]*n0
142 lg $nlo,0($np) # np[0]
143 mlgr $nhi,$mn0 # np[0]*m1
144 algr $nlo,$alo # +="tp[0]"
154 mlgr $ahi,$bi # ap[j]*bp[i]
158 alg $alo,160($j,$sp)# +=tp[j]
162 mlgr $nhi,$mn0 # np[j]*m1
166 algr $nlo,$alo # +="tp[j]"
169 stg $nlo,160-8($j,$sp) # tp[j-1]=
176 alg $NHI,160($j,$sp)# accumulate previous upmost overflow bit
178 alcgr $AHI,$ahi # new upmost overflow bit
179 stg $NHI,160-8($j,$sp)
183 clg $bp,160+8+32($j,$sp) # compare to &bp[num]
186 lg $rp,160+8+16($j,$sp) # reincarnate rp
188 ahi $num,1 # restore $num, incidentally clears "borrow"
192 .Lsub: lg $alo,0($j,$ap)
198 slbgr $AHI,$ahi # handle upmost carry
204 ogr $ap,$np # ap=borrow?tp:rp
208 .Lcopy: lg $alo,0($j,$ap) # copy or in-place refresh
209 stg $j,160($j,$sp) # zap tp
214 la %r1,160+8+48($j,$sp)
216 lghi %r2,1 # signal "processed"
218 .size bn_mul_mont,.-bn_mul_mont
219 .string "Montgomery Multiplication for s390x, CRYPTOGAMS by <appro\@openssl.org>"