crypto/bn/asm/s390x-mont.pl

   1 #!/usr/bin/env perl
   2
   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 # ====================================================================
   9
  10 # April 2007.
  11 #
  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...
  29
  30 $mn0="%r0";
  31 $num="%r1";
  32
  33 # int bn_mul_mont(
  34 $rp="%r2";              # BN_ULONG *rp,
  35 $ap="%r3";              # const BN_ULONG *ap,
  36 $bp="%r4";              # const BN_ULONG *bp,
  37 $np="%r5";              # const BN_ULONG *np,
  38 $n0="%r6";              # const BN_ULONG *n0,
  39 #$num="160(%r15)"       # int num);
  40
  41 $bi="%r2";      # zaps rp
  42 $j="%r7";
  43
  44 $ahi="%r8";
  45 $alo="%r9";
  46 $nhi="%r10";
  47 $nlo="%r11";
  48 $AHI="%r12";
  49 $NHI="%r13";
  50 $fp="%r14";
  51 $sp="%r15";
  52
  53 $code.=<<___;
  54 .text
  55 .globl  bn_mul_mont
  56 .type   bn_mul_mont,\@function
  57 bn_mul_mont:
  58         lgf     $num,164($sp)   # pull $num
  59         sla     $num,3          # $num to enumerate bytes
  60         la      $rp,0($num,$rp) # pointers to point at the vectors' ends
  61         la      $ap,0($num,$ap)
  62         la      $bp,0($num,$bp)
  63         la      $np,0($num,$np)
  64
  65         stmg    %r2,%r15,16($sp)
  66
  67         cghi    $num,16         #
  68         lghi    %r2,0           #
  69         blr     %r14            # if($num<16) return 0;
  70
  71         lcgr    $num,$num       # -$num
  72         lgr     %r0,$sp
  73         lgr     $fp,$sp
  74         aghi    $fp,-160-8      # leave room for carry bit
  75         la      $sp,0($num,$fp) # alloca
  76         stg     %r0,0($sp)
  77         aghi    $fp,160-8       # $fp to point at tp[$num-1]
  78
  79         la      $bp,0($num,$bp) # restore $bp
  80         lg      $n0,0($n0)      # pull n0
  81
  82         lg      $bi,0($bp)
  83         lg      $alo,0($num,$ap)
  84         mlgr    $ahi,$bi        # ap[0]*bp[0]
  85         lgr     $AHI,$ahi
  86
  87         lgr     $mn0,$alo       # "tp[0]"*n0
  88         msgr    $mn0,$n0
  89
  90         lg      $nlo,0($num,$np)#
  91         mlgr    $nhi,$mn0       # np[0]*m1
  92         algr    $nlo,$alo       # +="tp[0]"
  93         lghi    $NHI,0
  94         alcgr   $NHI,$nhi
  95
  96         lgr     $j,$num
  97         aghi    $j,8            # j=1
  98 .L1st:
  99         lg      $alo,0($j,$ap)
 100         mlgr    $ahi,$bi        # ap[j]*bp[0]
 101         algr    $alo,$AHI
 102         lghi    $AHI,0
 103         alcgr   $AHI,$ahi
 104
 105         lg      $nlo,0($j,$np)
 106         mlgr    $nhi,$mn0       # np[j]*m1
 107         algr    $nlo,$NHI
 108         lghi    $NHI,0
 109         alcgr   $nhi,$NHI       # +="tp[j]"
 110         algr    $nlo,$alo
 111         alcgr   $NHI,$nhi
 112
 113         stg     $nlo,0($j,$fp)  # tp[j-1]=
 114         aghi    $j,8            # j++
 115         jnz     .L1st
 116
 117         algr    $NHI,$AHI
 118         lghi    $AHI,0
 119         alcgr   $AHI,$AHI       # upmost overflow bit
 120         stg     $NHI,0($fp)
 121         stg     $AHI,8($fp)
 122         la      $bp,8($bp)      # bp++
 123
 124 .Louter:
 125         lg      $bi,0($bp)      # bp[i]
 126         lg      $alo,0($num,$ap)
 127         mlgr    $ahi,$bi        # ap[0]*bp[i]
 128         alg     $alo,8($num,$fp)# +=tp[0]
 129         lghi    $AHI,0
 130         alcgr   $AHI,$ahi
 131
 132         lgr     $mn0,$alo
 133         msgr    $mn0,$n0                # tp[0]*n0
 134
 135         lg      $nlo,0($num,$np)# np[0]
 136         mlgr    $nhi,$mn0       # np[0]*m1
 137         algr    $nlo,$alo       # +="tp[0]"
 138         lghi    $NHI,0
 139         alcgr   $NHI,$nhi
 140
 141         lgr     $j,$num
 142         aghi    $j,8            # j=1
 143 .Linner:
 144         lg      $alo,0($j,$ap)
 145         mlgr    $ahi,$bi        # ap[j]*bp[i]
 146         algr    $alo,$AHI
 147         lghi    $AHI,0
 148         alcgr   $ahi,$AHI
 149         alg     $alo,8($j,$fp)  # +=tp[j]
 150         alcgr   $AHI,$ahi
 151
 152         lg      $nlo,0($j,$np)
 153         mlgr    $nhi,$mn0       # np[j]*m1
 154         algr    $nlo,$NHI
 155         lghi    $NHI,0
 156         alcgr   $nhi,$NHI
 157         algr    $nlo,$alo       # +="tp[j]"
 158         alcgr   $NHI,$nhi
 159
 160         stg     $nlo,0($j,$fp)  # tp[j-1]=
 161         aghi    $j,8            # j++
 162         jnz     .Linner
 163
 164         algr    $NHI,$AHI
 165         lghi    $AHI,0
 166         alcgr   $AHI,$AHI
 167         alg     $NHI,8($fp)     # accumulate previous upmost overflow bit
 168         lghi    $ahi,0
 169         alcgr   $AHI,$ahi       # new upmost overflow bit
 170         stg     $NHI,0($fp)
 171         stg     $AHI,8($fp)
 172
 173         la      $bp,8($bp)      # bp++
 174         clg     $bp,16+32($fp)  # compare to &bp[num]
 175         jne     .Louter
 176 ___
 177
 178 undef $bi;
 179 $count=$ap; undef $ap;
 180
 181 $code.=<<___;
 182         lg      $rp,16+16($fp)  # reincarnate rp
 183         lgr     $j,$num
 184         ltgr    $AHI,$AHI
 185         jnz     .Lsub           # upmost overflow bit is not zero
 186         #slg    $NHI,-8($np)    # tp[num-1]-np[num-1]
 187         lghi    $count,-8               # buggy assembler
 188         slg     $NHI,0($count,$np)      # buggy assembler
 189         jnle    .Lsub           # branch if not borrow
 190
 191 .Lcopy: lg      $alo,8($j,$fp)
 192         stg     $j,8($j,$fp)
 193         stg     $alo,0($j,$rp)
 194         aghi    $j,8
 195         jnz     .Lcopy
 196 .Lexit:
 197         lmg     %r6,%r15,16+48($fp)
 198         lghi    %r2,1           # signal "processed"
 199         br      %r14
 200
 201 .Lsub:  lcgr    $count,$num
 202         sra     $count,3        # incidentally clears "borrow"
 203 .Lsubloop:
 204         lg      $alo,8($j,$fp)
 205         slbg    $alo,0($j,$np)
 206         stg     $alo,0($j,$rp)
 207         la      $j,8($j)
 208         brct    $count,.Lsubloop
 209         lghi    $ahi,0
 210         slbgr   $AHI,$ahi
 211         lgr     $j,$num
 212         jle     .Lcopy          # branch if borrow
 213
 214 .Lzap:  stg     $j,8($j,$fp)
 215         aghi    $j,8
 216         jnz     .Lzap
 217         j       .Lexit
 218 .size   bn_mul_mont,.-bn_mul_mont
 219 .string "Montgomery Multiplication for s390x, CRYPTOGAMS by <appro\@openssl.org>"
 220 ___
 221
 222 print $code;
 223 close STDOUT;