crypto/bn/asm/mips-mont.pl

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