crypto/bn/asm/vis3-mont.pl

   1 #!/usr/bin/env perl
   2
   3 # ====================================================================
   4 # Written by Andy Polyakov <appro@openssl.org> 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 # October 2012.
  11 #
  12 # SPARCv9 VIS3 Montgomery multiplicaion procedure suitable for T3 and
  13 # onward. There are three new instructions used here: umulxhi,
  14 # addxc[cc] and initializing store. On T3 RSA private key operations
  15 # are 1.54/1.87/2.11/2.26 times faster for 512/1024/2048/4096-bit key
  16 # lengths. This is without dedicated squaring procedure. On T4
  17 # corresponding coefficients are 1.47/2.10/2.80/2.90x, which is mostly
  18 # for reference purposes, because T4 has dedicated Montgomery
  19 # multiplication and squaring *instructions* that deliver even more.
  20
  21 $output = pop;
  22 open STDOUT,">$output";
  23
  24 $frame = "STACK_FRAME";
  25 $bias = "STACK_BIAS";
  26
  27 $code.=<<___;
  28 #include "sparc_arch.h"
  29
  30 #ifdef  __arch64__
  31 .register       %g2,#scratch
  32 .register       %g3,#scratch
  33 #endif
  34
  35 .section        ".text",#alloc,#execinstr
  36 ___
  37
  38 ($n0,$m0,$m1,$lo0,$hi0, $lo1,$hi1,$aj,$alo,$nj,$nlo,$tj)=
  39         (map("%g$_",(1..5)),map("%o$_",(0..5,7)));
  40
  41 # int bn_mul_mont(
  42 $rp="%o0";      # BN_ULONG *rp,
  43 $ap="%o1";      # const BN_ULONG *ap,
  44 $bp="%o2";      # const BN_ULONG *bp,
  45 $np="%o3";      # const BN_ULONG *np,
  46 $n0p="%o4";     # const BN_ULONG *n0,
  47 $num="%o5";     # int num);     # caller ensures that num is even
  48                                 # and >=6
  49 $code.=<<___;
  50 .globl  bn_mul_mont_vis3
  51 .align  32
  52 bn_mul_mont_vis3:
  53         add     %sp,    $bias,  %g4     ! real top of stack
  54         sll     $num,   2,      $num    ! size in bytes
  55         add     $num,   63,     %g5
  56         andn    %g5,    63,     %g5     ! buffer size rounded up to 64 bytes
  57         add     %g5,    %g5,    %g1
  58         add     %g5,    %g1,    %g1     ! 3*buffer size
  59         sub     %g4,    %g1,    %g1
  60         andn    %g1,    63,     %g1     ! align at 64 byte
  61         sub     %g1,    $frame, %g1     ! new top of stack
  62         sub     %g1,    %g4,    %g1
  63
  64         save    %sp,    %g1,    %sp
  65 ___
  66 \f
  67 #       +-------------------------------+<----- %sp
  68 #       .                               .
  69 #       +-------------------------------+<----- aligned at 64 bytes
  70 #       | __int64 tmp[0]                |
  71 #       +-------------------------------+
  72 #       .                               .
  73 #       .                               .
  74 #       +-------------------------------+<----- aligned at 64 bytes
  75 #       | __int64 ap[1..0]              |       converted ap[]
  76 #       +-------------------------------+
  77 #       | __int64 np[1..0]              |       converted np[]
  78 #       +-------------------------------+
  79 #       | __int64 ap[3..2]              |
  80 #       .                               .
  81 #       .                               .
  82 #       +-------------------------------+
  83 ($rp,$ap,$bp,$np,$n0p,$num)=map("%i$_",(0..5));
  84 ($t0,$t1,$t2,$t3,$cnt,$tp,$bufsz,$anp)=map("%l$_",(0..7));
  85 ($ovf,$i)=($t0,$t1);
  86 $code.=<<___;
  87         ld      [$n0p+0],       $t0     ! pull n0[0..1] value
  88         add     %sp, $bias+$frame, $tp
  89         ld      [$n0p+4],       $t1
  90         add     $tp,    %g5,    $anp
  91         ld      [$bp+0],        $t2     ! m0=bp[0]
  92         sllx    $t1,    32,     $n0
  93         ld      [$bp+4],        $t3
  94         or      $t0,    $n0,    $n0
  95         add     $bp,    8,      $bp
  96 \f
  97         ld      [$ap+0],        $t0     ! ap[0]
  98         sllx    $t3,    32,     $m0
  99         ld      [$ap+4],        $t1
 100         or      $t2,    $m0,    $m0
 101
 102         ld      [$ap+8],        $t2     ! ap[1]
 103         sllx    $t1,    32,     $aj
 104         ld      [$ap+12],       $t3
 105         or      $t0,    $aj,    $aj
 106         add     $ap,    16,     $ap
 107         stx     $aj,    [$anp]          ! converted ap[0]
 108
 109         mulx    $aj,    $m0,    $lo0    ! ap[0]*bp[0]
 110         umulxhi $aj,    $m0,    $hi0
 111
 112         ld      [$np+0],        $t0     ! np[0]
 113         sllx    $t3,    32,     $aj
 114         ld      [$np+4],        $t1
 115         or      $t2,    $aj,    $aj
 116
 117         ld      [$np+8],        $t2     ! np[1]
 118         sllx    $t1,    32,     $nj
 119         ld      [$np+12],       $t3
 120         or      $t0, $nj,       $nj
 121         add     $np,    16,     $np
 122         stx     $nj,    [$anp+8]        ! converted np[0]
 123
 124         mulx    $lo0,   $n0,    $m1     ! "tp[0]"*n0
 125         stx     $aj,    [$anp+16]       ! converted ap[1]
 126
 127         mulx    $aj,    $m0,    $alo    ! ap[1]*bp[0]
 128         umulxhi $aj,    $m0,    $aj     ! ahi=aj
 129
 130         mulx    $nj,    $m1,    $lo1    ! np[0]*m1
 131         umulxhi $nj,    $m1,    $hi1
 132
 133         sllx    $t3,    32,     $nj
 134         or      $t2,    $nj,    $nj
 135         stx     $nj,    [$anp+24]       ! converted np[1]
 136         add     $anp,   32,     $anp
 137
 138         addcc   $lo0,   $lo1,   $lo1
 139         addxc   %g0,    $hi1,   $hi1
 140
 141         mulx    $nj,    $m1,    $nlo    ! np[1]*m1
 142         umulxhi $nj,    $m1,    $nj     ! nhi=nj
 143 \f
 144         ba      .L1st
 145         sub     $num,   24,     $cnt    ! cnt=num-3
 146
 147 .align  16
 148 .L1st:
 149         ld      [$ap+0],        $t0     ! ap[j]
 150         addcc   $alo,   $hi0,   $lo0
 151         ld      [$ap+4],        $t1
 152         addxc   $aj,    %g0,    $hi0
 153
 154         sllx    $t1,    32,     $aj
 155         add     $ap,    8,      $ap
 156         or      $t0,    $aj,    $aj
 157         stx     $aj,    [$anp]          ! converted ap[j]
 158
 159         ld      [$np+0],        $t2     ! np[j]
 160         addcc   $nlo,   $hi1,   $lo1
 161         ld      [$np+4],        $t3
 162         addxc   $nj,    %g0,    $hi1    ! nhi=nj
 163
 164         sllx    $t3,    32,     $nj
 165         add     $np,    8,      $np
 166         mulx    $aj,    $m0,    $alo    ! ap[j]*bp[0]
 167         or      $t2,    $nj,    $nj
 168         umulxhi $aj,    $m0,    $aj     ! ahi=aj
 169         stx     $nj,    [$anp+8]        ! converted np[j]
 170         add     $anp,   16,     $anp    ! anp++
 171
 172         mulx    $nj,    $m1,    $nlo    ! np[j]*m1
 173         addcc   $lo0,   $lo1,   $lo1    ! np[j]*m1+ap[j]*bp[0]
 174         umulxhi $nj,    $m1,    $nj     ! nhi=nj
 175         addxc   %g0,    $hi1,   $hi1
 176         stx     $lo1,   [$tp]           ! tp[j-1]
 177         add     $tp,    8,      $tp     ! tp++
 178
 179         brnz,pt $cnt,   .L1st
 180         sub     $cnt,   8,      $cnt    ! j--
 181 !.L1st
 182         addcc   $alo,   $hi0,   $lo0
 183         addxc   $aj,    %g0,    $hi0    ! ahi=aj
 184
 185         addcc   $nlo,   $hi1,   $lo1
 186         addxc   $nj,    %g0,    $hi1
 187         addcc   $lo0,   $lo1,   $lo1    ! np[j]*m1+ap[j]*bp[0]
 188         addxc   %g0,    $hi1,   $hi1
 189         stx     $lo1,   [$tp]           ! tp[j-1]
 190         add     $tp,    8,      $tp
 191
 192         addcc   $hi0,   $hi1,   $hi1
 193         addxc   %g0,    %g0,    $ovf    ! upmost overflow bit
 194         stx     $hi1,   [$tp]
 195         add     $tp,    8,      $tp
 196 \f
 197         ba      .Louter
 198         sub     $num,   16,     $i      ! i=num-2
 199
 200 .align  16
 201 .Louter:
 202         ld      [$bp+0],        $t2     ! m0=bp[i]
 203         ld      [$bp+4],        $t3
 204
 205         sub     $anp,   $num,   $anp    ! rewind
 206         sub     $tp,    $num,   $tp
 207         sub     $anp,   $num,   $anp
 208
 209         add     $bp,    8,      $bp
 210         sllx    $t3,    32,     $m0
 211         ldx     [$anp+0],       $aj     ! ap[0]
 212         or      $t2,    $m0,    $m0
 213         ldx     [$anp+8],       $nj     ! np[0]
 214
 215         mulx    $aj,    $m0,    $lo0    ! ap[0]*bp[i]
 216         ldx     [$tp],          $tj     ! tp[0]
 217         umulxhi $aj,    $m0,    $hi0
 218         ldx     [$anp+16],      $aj     ! ap[1]
 219         addcc   $lo0,   $tj,    $lo0    ! ap[0]*bp[i]+tp[0]
 220         mulx    $aj,    $m0,    $alo    ! ap[1]*bp[i]
 221         addxc   %g0,    $hi0,   $hi0
 222         mulx    $lo0,   $n0,    $m1     ! tp[0]*n0
 223         umulxhi $aj,    $m0,    $aj     ! ahi=aj
 224         mulx    $nj,    $m1,    $lo1    ! np[0]*m1
 225         umulxhi $nj,    $m1,    $hi1
 226         ldx     [$anp+24],      $nj     ! np[1]
 227         add     $anp,   32,     $anp
 228         addcc   $lo1,   $lo0,   $lo1
 229         mulx    $nj,    $m1,    $nlo    ! np[1]*m1
 230         addxc   %g0,    $hi1,   $hi1
 231         umulxhi $nj,    $m1,    $nj     ! nhi=nj
 232 \f
 233         ba      .Linner
 234         sub     $num,   24,     $cnt    ! cnt=num-3
 235 .align  16
 236 .Linner:
 237         addcc   $alo,   $hi0,   $lo0
 238         ldx     [$tp+8],        $tj     ! tp[j]
 239         addxc   $aj,    %g0,    $hi0    ! ahi=aj
 240         ldx     [$anp+0],       $aj     ! ap[j]
 241         addcc   $nlo,   $hi1,   $lo1
 242         mulx    $aj,    $m0,    $alo    ! ap[j]*bp[i]
 243         addxc   $nj,    %g0,    $hi1    ! nhi=nj
 244         ldx     [$anp+8],       $nj     ! np[j]
 245         add     $anp,   16,     $anp
 246         umulxhi $aj,    $m0,    $aj     ! ahi=aj
 247         addcc   $lo0,   $tj,    $lo0    ! ap[j]*bp[i]+tp[j]
 248         mulx    $nj,    $m1,    $nlo    ! np[j]*m1
 249         addxc   %g0,    $hi0,   $hi0
 250         umulxhi $nj,    $m1,    $nj     ! nhi=nj
 251         addcc   $lo1,   $lo0,   $lo1    ! np[j]*m1+ap[j]*bp[i]+tp[j]
 252         addxc   %g0,    $hi1,   $hi1
 253         stx     $lo1,   [$tp]           ! tp[j-1]
 254         add     $tp,    8,      $tp
 255         brnz,pt $cnt,   .Linner
 256         sub     $cnt,   8,      $cnt
 257 !.Linner
 258         ldx     [$tp+8],        $tj     ! tp[j]
 259         addcc   $alo,   $hi0,   $lo0
 260         addxc   $aj,    %g0,    $hi0    ! ahi=aj
 261         addcc   $lo0,   $tj,    $lo0    ! ap[j]*bp[i]+tp[j]
 262         addxc   %g0,    $hi0,   $hi0
 263
 264         addcc   $nlo,   $hi1,   $lo1
 265         addxc   $nj,    %g0,    $hi1    ! nhi=nj
 266         addcc   $lo1,   $lo0,   $lo1    ! np[j]*m1+ap[j]*bp[i]+tp[j]
 267         addxc   %g0,    $hi1,   $hi1
 268         stx     $lo1,   [$tp]           ! tp[j-1]
 269
 270         subcc   %g0,    $ovf,   %g0     ! move upmost overflow to CCR.xcc
 271         addxccc $hi1,   $hi0,   $hi1
 272         addxc   %g0,    %g0,    $ovf
 273         stx     $hi1,   [$tp+8]
 274         add     $tp,    16,     $tp
 275
 276         brnz,pt $i,     .Louter
 277         sub     $i,     8,      $i
 278 \f
 279         sub     $anp,   $num,   $anp    ! rewind
 280         sub     $tp,    $num,   $tp
 281         sub     $anp,   $num,   $anp
 282         ba      .Lsub
 283         subcc   $num,   8,      $cnt    ! cnt=num-1 and clear CCR.xcc
 284
 285 .align  16
 286 .Lsub:
 287         ldx     [$tp],          $tj
 288         add     $tp,    8,      $tp
 289         ldx     [$anp+8],       $nj
 290         add     $anp,   16,     $anp
 291         subccc  $tj,    $nj,    $t2     ! tp[j]-np[j]
 292         srlx    $tj,    32,     $tj
 293         srlx    $nj,    32,     $nj
 294         subccc  $tj,    $nj,    $t3
 295         add     $rp,    8,      $rp
 296         st      $t2,    [$rp-4]         ! reverse order
 297         st      $t3,    [$rp-8]
 298         brnz,pt $cnt,   .Lsub
 299         sub     $cnt,   8,      $cnt
 300
 301         sub     $anp,   $num,   $anp    ! rewind
 302         sub     $tp,    $num,   $tp
 303         sub     $anp,   $num,   $anp
 304         sub     $rp,    $num,   $rp
 305
 306         subc    $ovf,   %g0,    $ovf    ! handle upmost overflow bit
 307         and     $tp,    $ovf,   $ap
 308         andn    $rp,    $ovf,   $np
 309         or      $np,    $ap,    $ap     ! ap=borrow?tp:rp
 310         ba      .Lcopy
 311         sub     $num,   8,      $cnt
 312
 313 .align  16
 314 .Lcopy:                                 ! copy or in-place refresh
 315         ld      [$ap+0],        $t2
 316         ld      [$ap+4],        $t3
 317         add     $ap,    8,      $ap
 318         stx     %g0,    [$tp]           ! zap
 319         add     $tp,    8,      $tp
 320         stx     %g0,    [$anp]          ! zap
 321         stx     %g0,    [$anp+8]
 322         add     $anp,   16,     $anp
 323         st      $t3,    [$rp+0]         ! flip order
 324         st      $t2,    [$rp+4]
 325         add     $rp,    8,      $rp
 326         brnz    $cnt,   .Lcopy
 327         sub     $cnt,   8,      $cnt
 328
 329         mov     1,      %o0
 330         ret
 331         restore
 332 .type   bn_mul_mont_vis3, #function
 333 .size   bn_mul_mont_vis3, .-bn_mul_mont_vis3
 334 .asciz  "Montgomery Multiplication for SPARCv9 VIS3, CRYPTOGAMS by <appro\@openssl.org>"
 335 .align  4
 336 ___
 337 \f
 338 # Purpose of these subroutines is to explicitly encode VIS instructions,
 339 # so that one can compile the module without having to specify VIS
 340 # extensions on compiler command line, e.g. -xarch=v9 vs. -xarch=v9a.
 341 # Idea is to reserve for option to produce "universal" binary and let
 342 # programmer detect if current CPU is VIS capable at run-time.
 343 sub unvis3 {
 344 my ($mnemonic,$rs1,$rs2,$rd)=@_;
 345 my %bias = ( "g" => 0, "o" => 8, "l" => 16, "i" => 24 );
 346 my ($ref,$opf);
 347 my %visopf = (  "addxc"         => 0x011,
 348                 "addxccc"       => 0x013,
 349                 "umulxhi"       => 0x016        );
 350
 351     $ref = "$mnemonic\t$rs1,$rs2,$rd";
 352
 353     if ($opf=$visopf{$mnemonic}) {
 354         foreach ($rs1,$rs2,$rd) {
 355             return $ref if (!/%([goli])([0-9])/);
 356             $_=$bias{$1}+$2;
 357         }
 358
 359         return  sprintf ".word\t0x%08x !%s",
 360                         0x81b00000|$rd<<25|$rs1<<14|$opf<<5|$rs2,
 361                         $ref;
 362     } else {
 363         return $ref;
 364     }
 365 }
 366
 367 foreach (split("\n",$code)) {
 368         s/\`([^\`]*)\`/eval $1/ge;
 369
 370         s/\b(umulxhi|addxc[c]{0,2})\s+(%[goli][0-7]),\s*(%[goli][0-7]),\s*(%[goli][0-7])/
 371                 &unvis3($1,$2,$3,$4)
 372          /ge;
 373
 374         print $_,"\n";
 375 }
 376
 377 close STDOUT;