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