crypto/bn/asm/x86_64-mont.pl

   1 #!/usr/bin/env perl
   2
   3 # ====================================================================
   4 # Written by Andy Polyakov <appro@fy.chalmers.se> for the OpenSSL
   5 # project. Rights for redistribution and usage in source and binary
   6 # forms are granted according to the OpenSSL license.
   7 # ====================================================================
   8
   9 # October 2005.
  10 #
  11 # Montgomery multiplication routine for x86_64. While it gives modest
  12 # 9% improvement of rsa4096 sign on Opteron, rsa512 sign runs more
  13 # than twice, >2x, as fast. Most common rsa1024 sign is improved by
  14 # respectful 50%. It remains to be seen if loop unrolling and
  15 # dedicated squaring routine can provide further improvement...
  16
  17 $output=shift;
  18 open STDOUT,"| $^X ../perlasm/x86_64-xlate.pl $output";
  19
  20 # int bn_mul_mont(
  21 $rp="%rdi";     # BN_ULONG *rp,
  22 $ap="%rsi";     # const BN_ULONG *ap,
  23 $bp="%rdx";     # const BN_ULONG *bp,
  24 $np="%rcx";     # const BN_ULONG *np,
  25 $n0="%r8";      # BN_ULONG n0,
  26 $num="%r9";     # int num);
  27 $lo0="%r10";
  28 $hi0="%r11";
  29 $bp="%r12";     # reassign $bp
  30 $hi1="%r13";
  31 $i="%r14";
  32 $j="%r15";
  33 $m0="%rbx";
  34 $m1="%rbp";
  35
  36 $code=<<___;
  37 .text
  38
  39 .globl  bn_mul_mont
  40 .type   bn_mul_mont,\@function,6
  41 .align  16
  42 bn_mul_mont:
  43         push    %rbx
  44         push    %rbp
  45         push    %r12
  46         push    %r13
  47         push    %r14
  48         push    %r15
  49
  50         lea     2($num),%rax
  51         mov     %rsp,%rbp
  52         neg     %rax
  53         lea     (%rsp,%rax,8),%rsp      # tp=alloca(8*(num+2))
  54         and     \$-1024,%rsp            # minimize TLB usage
  55         mov     %rbp,8(%rsp,$num,8)     # tp[num+1]=%rsp
  56         mov     %rdx,$bp                # $bp reassigned, remember?
  57
  58         xor     $i,$i                   # i=0
  59         xor     $j,$j                   # j=0
  60
  61         mov     ($bp),$m0               # m0=bp[0]
  62         mov     ($ap),%rax
  63         mulq    $m0                     # ap[0]*bp[0]
  64         mov     %rax,$lo0
  65         mov     %rdx,$hi0
  66
  67         imulq   $n0,%rax                # "tp[0]"*n0
  68         mov     %rax,$m1
  69
  70         mulq    ($np)                   # np[0]*m1
  71         add     $lo0,%rax               # discarded
  72         adc     \$0,%rdx
  73         mov     %rdx,$hi1
  74
  75         lea     1($j),$j                # j++
  76 .L1st:
  77         mov     ($ap,$j,8),%rax
  78         mulq    $m0                     # ap[j]*bp[0]
  79         add     $hi0,%rax
  80         adc     \$0,%rdx
  81         mov     %rax,$lo0
  82         mov     %rdx,$hi0
  83
  84         mov     ($np,$j,8),%rax
  85         mulq    $m1                     # np[j]*m1
  86         add     $hi1,%rax
  87         adc     \$0,%rdx
  88         add     $lo0,%rax               # np[j]*m1+ap[j]*bp[0]
  89         adc     \$0,%rdx
  90         mov     %rax,-8(%rsp,$j,8)      # tp[j-1]
  91         mov     %rdx,$hi1
  92
  93         lea     1($j),$j                # j++
  94         cmp     $num,$j
  95         jl      .L1st
  96
  97         xor     %rdx,%rdx
  98         add     $hi0,$hi1
  99         adc     \$0,%rdx
 100         mov     $hi1,-8(%rsp,$num,8)
 101         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 102
 103         lea     1($i),$i                # i++
 104 .align  4
 105 .Louter:
 106         xor     $j,$j                   # j=0
 107
 108         mov     ($bp,$i,8),$m0          # m0=bp[i]
 109         mov     ($ap),%rax              # ap[0]
 110         mulq    $m0                     # ap[0]*bp[i]
 111         add     (%rsp),%rax             # ap[0]*bp[i]+tp[0]
 112         adc     \$0,%rdx
 113         mov     %rax,$lo0
 114         mov     %rdx,$hi0
 115
 116         imulq   $n0,%rax                # tp[0]*n0
 117         mov     %rax,$m1
 118
 119         mulq    ($np,$j,8)              # np[0]*m1
 120         add     $lo0,%rax               # discarded
 121         adc     \$0,%rdx
 122         mov     %rdx,$hi1
 123
 124         lea     1($j),$j                # j++
 125 .align  4
 126 .Linner:
 127         mov     ($ap,$j,8),%rax
 128         mulq    $m0                     # ap[j]*bp[i]
 129         add     $hi0,%rax
 130         adc     \$0,%rdx
 131         add     (%rsp,$j,8),%rax        # ap[j]*bp[i]+tp[j]
 132         adc     \$0,%rdx
 133         mov     %rax,$lo0
 134         mov     %rdx,$hi0
 135
 136         mov     ($np,$j,8),%rax
 137         mulq    $m1                     # np[j]*m1
 138         add     $hi1,%rax
 139         adc     \$0,%rdx
 140         add     $lo0,%rax               # np[j]*m1+ap[j]*bp[i]+tp[j]
 141         adc     \$0,%rdx
 142         mov     %rax,-8(%rsp,$j,8)      # tp[j-1]
 143         mov     %rdx,$hi1
 144
 145         lea     1($j),$j                # j++
 146         cmp     $num,$j
 147         jl      .Linner
 148
 149         xor     %rdx,%rdx
 150         add     $hi0,$hi1
 151         adc     \$0,%rdx
 152         add     (%rsp,$num,8),$hi1      # pull upmost overflow bit
 153         adc     \$0,%rdx
 154         mov     $hi1,-8(%rsp,$num,8)
 155         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 156
 157         lea     1($i),$i                # i++
 158         cmp     $num,$i
 159         jl      .Louter
 160
 161         xor     $i,$i                   # i=0
 162         lea     -1($num),$j             # j=num-1
 163         cmp     \$0,%rdx                # %rdx still holds upmost overflow bit
 164         jnz     .Lsub                   # CF is cleared by compare with 0
 165         mov     (%rsp,$j,8),%rax
 166         cmp     ($np,$j,8),%rax         # tp[num-1]-np[num-1]
 167         jae     .Lsub                   # if taken CF was cleared by above cmp
 168 .align  4
 169 .Lcopy:
 170         mov     (%rsp,$j,8),%rax
 171         mov     %rax,($rp,$j,8)         # rp[i]=tp[i]
 172         mov     $i,(%rsp,$j,8)          # zap temporary vector
 173         dec     $j
 174         jge     .Lcopy
 175 .align  4
 176 .Lexit:
 177         mov     8(%rsp,$num,8),%rsp     # restore %rsp
 178         mov     \$1,%rax
 179         pop     %r15
 180         pop     %r14
 181         pop     %r13
 182         pop     %r12
 183         pop     %rbp
 184         pop     %rbx
 185         ret
 186
 187 .align  16
 188 .Lsub:  mov     (%rsp,$i,8),%rax
 189         sbb     ($np,$i,8),%rax
 190         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]-np[j]
 191         lea     1($i),$i                # i++
 192         dec     $j                      # doesn't affect CF!
 193         jge     .Lsub
 194         lea     -1($num),$j             # j=num-1
 195         sbb     \$0,%rdx
 196         jc      .Lcopy                  # tp was less than np
 197 .align  4
 198 .Lzap:  mov     $i,(%rsp,$j,8)          # zap temporary vector
 199         dec     $j
 200         jge     .Lzap
 201         jmp     .Lexit
 202 .size   bn_mul_mont,.-bn_mul_mont
 203 ___
 204
 205 print $code;
 206 close STDOUT;