crypto/bn/asm/mips-mont.pl

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