crypto/bn/asm/mips-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 # This module doesn't present direct interest for OpenSSL, because it
  11 # doesn't provide better performance for longer keys, at least not on
  12 # in-order-execution cores. While 512-bit RSA sign operations can be
  13 # 65% faster in 64-bit mode, 1024-bit ones are only 15% faster, and
  14 # 4096-bit ones are up to 15% slower. In 32-bit mode it varies from
  15 # 16% improvement for 512-bit RSA sign to -33% for 4096-bit RSA
  16 # verify:-( All comparisons are against bn_mul_mont-free assembler.
  17 # The module might be of interest to embedded system developers, as
  18 # the code is smaller than 1KB, yet offers >3x improvement on MIPS64
  19 # and 75-30% [less for longer keys] on MIPS32 over compiler-generated
  20 # code.
  21
  22 ######################################################################
  23 # There is a number of MIPS ABI in use, O32 and N32/64 are most
  24 # widely used. Then there is a new contender: NUBI. It appears that if
  25 # one picks the latter, it's possible to arrange code in ABI neutral
  26 # manner. Therefore let's stick to NUBI register layout:
  27 #
  28 ($zero,$at,$t0,$t1,$t2)=map("\$$_",(0..2,24,25));
  29 ($a0,$a1,$a2,$a3,$a4,$a5,$a6,$a7)=map("\$$_",(4..11));
  30 ($s0,$s1,$s2,$s3,$s4,$s5,$s6,$s7,$s8,$s9,$s10,$s11)=map("\$$_",(12..23));
  31 ($gp,$tp,$sp,$fp,$ra)=map("\$$_",(3,28..31));
  32 #
  33 # The return value is placed in $a0. Following coding rules facilitate
  34 # interoperability:
  35 #
  36 # - never ever touch $tp, "thread pointer", former $gp;
  37 # - copy return value to $t0, former $v0 [or to $a0 if you're adapting
  38 #   old code];
  39 # - on O32 populate $a4-$a7 with 'lw $aN,4*N($sp)' if necessary;
  40 #
  41 # For reference here is register layout for N32/64 MIPS ABIs:
  42 #
  43 # ($zero,$at,$v0,$v1)=map("\$$_",(0..3));
  44 # ($a0,$a1,$a2,$a3,$a4,$a5,$a6,$a7)=map("\$$_",(4..11));
  45 # ($t0,$t1,$t2,$t3,$t8,$t9)=map("\$$_",(12..15,24,25));
  46 # ($s0,$s1,$s2,$s3,$s4,$s5,$s6,$s7)=map("\$$_",(16..23));
  47 # ($gp,$sp,$fp,$ra)=map("\$$_",(28..31));
  48 #
  49 $flavour = shift || "o32"; # supported flavours are o32,n32,64,nubi32,nubi64
  50
  51 if ($flavour =~ /64|n32/i) {
  52         $PTR_ADD="dadd";        # incidentally works even on n32
  53         $PTR_SUB="dsub";        # incidentally works even on n32
  54         $REG_S="sd";
  55         $REG_L="ld";
  56         $SZREG=8;
  57 } else {
  58         $PTR_ADD="add";
  59         $PTR_SUB="sub";
  60         $REG_S="sw";
  61         $REG_L="lw";
  62         $SZREG=4;
  63 }
  64 $SAVED_REGS_MASK = ($flavour =~ /nubi/i) ? 0x00fff000 : 0x00ff0000;
  65 #
  66 # <appro@openssl.org>
  67 #
  68 ######################################################################
  69
  70 while (($output=shift) && ($output!~/^\w[\w\-]*\.\w+$/)) {}
  71 open STDOUT,">$output";
  72
  73 if ($flavour =~ /64|n32/i) {
  74         $LD="ld";
  75         $ST="sd";
  76         $MULTU="dmultu";
  77         $ADDU="daddu";
  78         $SUBU="dsubu";
  79         $BNSZ=8;
  80 } else {
  81         $LD="lw";
  82         $ST="sw";
  83         $MULTU="multu";
  84         $ADDU="addu";
  85         $SUBU="subu";
  86         $BNSZ=4;
  87 }
  88
  89 # int bn_mul_mont(
  90 $rp=$a0;        # BN_ULONG *rp,
  91 $ap=$a1;        # const BN_ULONG *ap,
  92 $bp=$a2;        # const BN_ULONG *bp,
  93 $np=$a3;        # const BN_ULONG *np,
  94 $n0=$a4;        # const BN_ULONG *n0,
  95 $num=$a5;       # int num);
  96
  97 $lo0=$a6;
  98 $hi0=$a7;
  99 $lo1=$t1;
 100 $hi1=$t2;
 101 $aj=$s0;
 102 $bi=$s1;
 103 $nj=$s2;
 104 $tp=$s3;
 105 $alo=$s4;
 106 $ahi=$s5;
 107 $nlo=$s6;
 108 $nhi=$s7;
 109 $tj=$s8;
 110 $i=$s9;
 111 $j=$s10;
 112 $m1=$s11;
 113
 114 $FRAMESIZE=14;
 115
 116 $code=<<___;
 117 .text
 118
 119 .set    noat
 120 .set    noreorder
 121
 122 .align  5
 123 .globl  bn_mul_mont
 124 .ent    bn_mul_mont
 125 bn_mul_mont:
 126 ___
 127 $code.=<<___ if ($flavour =~ /o32/i);
 128         lw      $n0,16($sp)
 129         lw      $num,20($sp)
 130 ___
 131 $code.=<<___;
 132         slt     $at,$num,4
 133         bnez    $at,1f
 134         li      $t0,0
 135         slt     $at,$num,17     # on in-order CPU
 136         bnez    $at,bn_mul_mont_internal
 137         nop
 138 1:      jr      $ra
 139         li      $a0,0
 140 .end    bn_mul_mont
 141
 142 .align  5
 143 .ent    bn_mul_mont_internal
 144 bn_mul_mont_internal:
 145         .frame  $fp,$FRAMESIZE*$SZREG,$ra
 146         .mask   0x40000000|$SAVED_REGS_MASK,-$SZREG
 147         $PTR_SUB $sp,$FRAMESIZE*$SZREG
 148         $REG_S  $fp,($FRAMESIZE-1)*$SZREG($sp)
 149         $REG_S  $s11,($FRAMESIZE-2)*$SZREG($sp)
 150         $REG_S  $s10,($FRAMESIZE-3)*$SZREG($sp)
 151         $REG_S  $s9,($FRAMESIZE-4)*$SZREG($sp)
 152         $REG_S  $s8,($FRAMESIZE-5)*$SZREG($sp)
 153         $REG_S  $s7,($FRAMESIZE-6)*$SZREG($sp)
 154         $REG_S  $s6,($FRAMESIZE-7)*$SZREG($sp)
 155         $REG_S  $s5,($FRAMESIZE-8)*$SZREG($sp)
 156         $REG_S  $s4,($FRAMESIZE-9)*$SZREG($sp)
 157 ___
 158 $code.=<<___ if ($flavour =~ /nubi/i);
 159         $REG_S  $s3,($FRAMESIZE-10)*$SZREG($sp)
 160         $REG_S  $s2,($FRAMESIZE-11)*$SZREG($sp)
 161         $REG_S  $s1,($FRAMESIZE-12)*$SZREG($sp)
 162         $REG_S  $s0,($FRAMESIZE-13)*$SZREG($sp)
 163 ___
 164 $code.=<<___;
 165         move    $fp,$sp
 166
 167         .set    reorder
 168         $LD     $n0,0($n0)
 169         $LD     $bi,0($bp)      # bp[0]
 170         $LD     $aj,0($ap)      # ap[0]
 171         $LD     $nj,0($np)      # np[0]
 172
 173         $PTR_SUB $sp,2*$BNSZ    # place for two extra words
 174         sll     $num,`log($BNSZ)/log(2)`
 175         li      $at,-4096
 176         $PTR_SUB $sp,$num
 177         and     $sp,$at
 178
 179         $MULTU  $aj,$bi
 180         $LD     $alo,$BNSZ($ap)
 181         $LD     $nlo,$BNSZ($np)
 182         mflo    $lo0
 183         mfhi    $hi0
 184         $MULTU  $lo0,$n0
 185         mflo    $m1
 186
 187         $MULTU  $alo,$bi
 188         mflo    $alo
 189         mfhi    $ahi
 190
 191         $MULTU  $nj,$m1
 192         mflo    $lo1
 193         mfhi    $hi1
 194         $MULTU  $nlo,$m1
 195         $ADDU   $lo1,$lo0
 196         sltu    $at,$lo1,$lo0
 197         $ADDU   $hi1,$at
 198         mflo    $nlo
 199         mfhi    $nhi
 200
 201         move    $tp,$sp
 202         li      $j,2*$BNSZ
 203 .align  4
 204 .L1st:
 205         .set    noreorder
 206         $PTR_ADD $aj,$ap,$j
 207         $PTR_ADD $nj,$np,$j
 208         $LD     $aj,($aj)
 209         $LD     $nj,($nj)
 210
 211         $MULTU  $aj,$bi
 212         $ADDU   $lo0,$alo,$hi0
 213         $ADDU   $lo1,$nlo,$hi1
 214         sltu    $at,$lo0,$hi0
 215         sltu    $t0,$lo1,$hi1
 216         $ADDU   $hi0,$ahi,$at
 217         $ADDU   $hi1,$nhi,$t0
 218         mflo    $alo
 219         mfhi    $ahi
 220
 221         $ADDU   $lo1,$lo0
 222         sltu    $at,$lo1,$lo0
 223         $MULTU  $nj,$m1
 224         $ADDU   $hi1,$at
 225         addu    $j,$BNSZ
 226         $ST     $lo1,($tp)
 227         sltu    $t0,$j,$num
 228         mflo    $nlo
 229         mfhi    $nhi
 230
 231         bnez    $t0,.L1st
 232         $PTR_ADD $tp,$BNSZ
 233         .set    reorder
 234
 235         $ADDU   $lo0,$alo,$hi0
 236         sltu    $at,$lo0,$hi0
 237         $ADDU   $hi0,$ahi,$at
 238
 239         $ADDU   $lo1,$nlo,$hi1
 240         sltu    $t0,$lo1,$hi1
 241         $ADDU   $hi1,$nhi,$t0
 242         $ADDU   $lo1,$lo0
 243         sltu    $at,$lo1,$lo0
 244         $ADDU   $hi1,$at
 245
 246         $ST     $lo1,($tp)
 247
 248         $ADDU   $hi1,$hi0
 249         sltu    $at,$hi1,$hi0
 250         $ST     $hi1,$BNSZ($tp)
 251         $ST     $at,2*$BNSZ($tp)
 252
 253         li      $i,$BNSZ
 254 .align  4
 255 .Louter:
 256         $PTR_ADD $bi,$bp,$i
 257         $LD     $bi,($bi)
 258         $LD     $aj,($ap)
 259         $LD     $alo,$BNSZ($ap)
 260         $LD     $tj,($sp)
 261
 262         $MULTU  $aj,$bi
 263         $LD     $nj,($np)
 264         $LD     $nlo,$BNSZ($np)
 265         mflo    $lo0
 266         mfhi    $hi0
 267         $ADDU   $lo0,$tj
 268         $MULTU  $lo0,$n0
 269         sltu    $at,$lo0,$tj
 270         $ADDU   $hi0,$at
 271         mflo    $m1
 272
 273         $MULTU  $alo,$bi
 274         mflo    $alo
 275         mfhi    $ahi
 276
 277         $MULTU  $nj,$m1
 278         mflo    $lo1
 279         mfhi    $hi1
 280
 281         $MULTU  $nlo,$m1
 282         $ADDU   $lo1,$lo0
 283         sltu    $at,$lo1,$lo0
 284         $ADDU   $hi1,$at
 285         mflo    $nlo
 286         mfhi    $nhi
 287
 288         move    $tp,$sp
 289         li      $j,2*$BNSZ
 290         $LD     $tj,$BNSZ($tp)
 291 .align  4
 292 .Linner:
 293         .set    noreorder
 294         $PTR_ADD $aj,$ap,$j
 295         $PTR_ADD $nj,$np,$j
 296         $LD     $aj,($aj)
 297         $LD     $nj,($nj)
 298
 299         $MULTU  $aj,$bi
 300         $ADDU   $lo0,$alo,$hi0
 301         $ADDU   $lo1,$nlo,$hi1
 302         sltu    $at,$lo0,$hi0
 303         sltu    $t0,$lo1,$hi1
 304         $ADDU   $hi0,$ahi,$at
 305         $ADDU   $hi1,$nhi,$t0
 306         mflo    $alo
 307         mfhi    $ahi
 308
 309         $ADDU   $lo0,$tj
 310         addu    $j,$BNSZ
 311         $MULTU  $nj,$m1
 312         sltu    $at,$lo0,$tj
 313         $ADDU   $lo1,$lo0
 314         $ADDU   $hi0,$at
 315         sltu    $t0,$lo1,$lo0
 316         $LD     $tj,2*$BNSZ($tp)
 317         $ADDU   $hi1,$t0
 318         sltu    $at,$j,$num
 319         mflo    $nlo
 320         mfhi    $nhi
 321         $ST     $lo1,($tp)
 322         bnez    $at,.Linner
 323         $PTR_ADD $tp,$BNSZ
 324         .set    reorder
 325
 326         $ADDU   $lo0,$alo,$hi0
 327         sltu    $at,$lo0,$hi0
 328         $ADDU   $hi0,$ahi,$at
 329         $ADDU   $lo0,$tj
 330         sltu    $t0,$lo0,$tj
 331         $ADDU   $hi0,$t0
 332
 333         $LD     $tj,2*$BNSZ($tp)
 334         $ADDU   $lo1,$nlo,$hi1
 335         sltu    $at,$lo1,$hi1
 336         $ADDU   $hi1,$nhi,$at
 337         $ADDU   $lo1,$lo0
 338         sltu    $t0,$lo1,$lo0
 339         $ADDU   $hi1,$t0
 340         $ST     $lo1,($tp)
 341
 342         $ADDU   $lo1,$hi1,$hi0
 343         sltu    $hi1,$lo1,$hi0
 344         $ADDU   $lo1,$tj
 345         sltu    $at,$lo1,$tj
 346         $ADDU   $hi1,$at
 347         $ST     $lo1,$BNSZ($tp)
 348         $ST     $hi1,2*$BNSZ($tp)
 349
 350         addu    $i,$BNSZ
 351         sltu    $t0,$i,$num
 352         bnez    $t0,.Louter
 353 \f
 354         .set    noreorder
 355         $PTR_ADD $tj,$sp,$num   # &tp[num]
 356         move    $tp,$sp
 357         move    $ap,$sp
 358         li      $hi0,0          # clear borrow bit
 359
 360 .align  4
 361 .Lsub:  $LD     $lo0,($tp)
 362         $LD     $lo1,($np)
 363         $PTR_ADD $tp,$BNSZ
 364         $PTR_ADD $np,$BNSZ
 365         $SUBU   $lo1,$lo0,$lo1  # tp[i]-np[i]
 366         sgtu    $at,$lo1,$lo0
 367         $SUBU   $lo0,$lo1,$hi0
 368         sgtu    $hi0,$lo0,$lo1
 369         $ST     $lo0,($rp)
 370         or      $hi0,$at
 371         sltu    $at,$tp,$tj
 372         bnez    $at,.Lsub
 373         $PTR_ADD $rp,$BNSZ
 374
 375         $SUBU   $hi0,$hi1,$hi0  # handle upmost overflow bit
 376         move    $tp,$sp
 377         $PTR_SUB $rp,$num       # restore rp
 378         not     $hi1,$hi0
 379
 380         and     $ap,$hi0,$sp
 381         and     $bp,$hi1,$rp
 382         or      $ap,$ap,$bp     # ap=borrow?tp:rp
 383
 384 .align  4
 385 .Lcopy: $LD     $aj,($ap)
 386         $PTR_ADD $ap,$BNSZ
 387         $ST     $zero,($tp)
 388         $PTR_ADD $tp,$BNSZ
 389         sltu    $at,$tp,$tj
 390         $ST     $aj,($rp)
 391         bnez    $at,.Lcopy
 392         $PTR_ADD $rp,$BNSZ
 393
 394         li      $a0,1
 395         li      $t0,1
 396
 397         .set    noreorder
 398         move    $sp,$fp
 399         $REG_L  $fp,($FRAMESIZE-1)*$SZREG($sp)
 400         $REG_L  $s11,($FRAMESIZE-2)*$SZREG($sp)
 401         $REG_L  $s10,($FRAMESIZE-3)*$SZREG($sp)
 402         $REG_L  $s9,($FRAMESIZE-4)*$SZREG($sp)
 403         $REG_L  $s8,($FRAMESIZE-5)*$SZREG($sp)
 404         $REG_L  $s7,($FRAMESIZE-6)*$SZREG($sp)
 405         $REG_L  $s6,($FRAMESIZE-7)*$SZREG($sp)
 406         $REG_L  $s5,($FRAMESIZE-8)*$SZREG($sp)
 407         $REG_L  $s4,($FRAMESIZE-9)*$SZREG($sp)
 408 ___
 409 $code.=<<___ if ($flavour =~ /nubi/i);
 410         $REG_L  $s3,($FRAMESIZE-10)*$SZREG($sp)
 411         $REG_L  $s2,($FRAMESIZE-11)*$SZREG($sp)
 412         $REG_L  $s1,($FRAMESIZE-12)*$SZREG($sp)
 413         $REG_L  $s0,($FRAMESIZE-13)*$SZREG($sp)
 414 ___
 415 $code.=<<___;
 416         jr      $ra
 417         $PTR_ADD $sp,$FRAMESIZE*$SZREG
 418 .end    bn_mul_mont_internal
 419 .rdata
 420 .asciiz "Montgomery Multiplication for MIPS, CRYPTOGAMS by <appro\@openssl.org>"
 421 ___
 422
 423 $code =~ s/\`([^\`]*)\`/eval $1/gem;
 424
 425 print $code;
 426 close STDOUT;