crypto/bn/asm/ppc-mont.pl

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