crypto/bn/asm/via-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 # Wrapper around 'rep montmul', VIA-specific instruction accessing
  11 # PadLock Montgomery Multiplier. The wrapper is designed as drop-in
  12 # replacement for OpenSSL bn_mul_mont [first implemented in 0.9.9].
  13 #
  14 # Below are interleaved outputs from 'openssl speed rsa dsa' for 4
  15 # different software configurations on 1.5GHz VIA Esther processor.
  16 # Lines marked with "software integer" denote performance of hand-
  17 # coded integer-only assembler found in OpenSSL 0.9.7. "Software SSE2"
  18 # refers to hand-coded SSE2 Montgomery multiplication procedure found
  19 # OpenSSL 0.9.9. "Hardware VIA SDK" refers to padlock_pmm routine from
  20 # Padlock SDK 2.0.1 available for download from VIA, which naturally
  21 # utilizes the magic 'repz montmul' instruction. And finally "hardware
  22 # this" refers to *this* implementation which also uses 'repz montmul'
  23 #
  24 #                   sign    verify    sign/s verify/s
  25 # rsa  512 bits 0.001720s 0.000140s    581.4   7149.7   software integer
  26 # rsa  512 bits 0.000690s 0.000086s   1450.3  11606.0   software SSE2
  27 # rsa  512 bits 0.006136s 0.000201s    163.0   4974.5   hardware VIA SDK
  28 # rsa  512 bits 0.000712s 0.000050s   1404.9  19858.5   hardware this
  29 #
  30 # rsa 1024 bits 0.008518s 0.000413s    117.4   2420.8   software integer
  31 # rsa 1024 bits 0.004275s 0.000277s    233.9   3609.7   software SSE2
  32 # rsa 1024 bits 0.012136s 0.000260s     82.4   3844.5   hardware VIA SDK
  33 # rsa 1024 bits 0.002522s 0.000116s    396.5   8650.9   hardware this
  34 #
  35 # rsa 2048 bits 0.050101s 0.001371s     20.0    729.6   software integer
  36 # rsa 2048 bits 0.030273s 0.001008s     33.0    991.9   software SSE2
  37 # rsa 2048 bits 0.030833s 0.000976s     32.4   1025.1   hardware VIA SDK
  38 # rsa 2048 bits 0.011879s 0.000342s     84.2   2921.7   hardware this
  39 #
  40 # rsa 4096 bits 0.327097s 0.004859s      3.1    205.8   software integer
  41 # rsa 4096 bits 0.229318s 0.003859s      4.4    259.2   software SSE2
  42 # rsa 4096 bits 0.233953s 0.003274s      4.3    305.4   hardware VIA SDK
  43 # rsa 4096 bits 0.070493s 0.001166s     14.2    857.6   hardware this
  44 #
  45 # dsa  512 bits 0.001342s 0.001651s    745.2    605.7   software integer
  46 # dsa  512 bits 0.000844s 0.000987s   1185.3   1013.1   software SSE2
  47 # dsa  512 bits 0.001902s 0.002247s    525.6    444.9   hardware VIA SDK
  48 # dsa  512 bits 0.000458s 0.000524s   2182.2   1909.1   hardware this
  49 #
  50 # dsa 1024 bits 0.003964s 0.004926s    252.3    203.0   software integer
  51 # dsa 1024 bits 0.002686s 0.003166s    372.3    315.8   software SSE2
  52 # dsa 1024 bits 0.002397s 0.002823s    417.1    354.3   hardware VIA SDK
  53 # dsa 1024 bits 0.000978s 0.001170s   1022.2    855.0   hardware this
  54 #
  55 # dsa 2048 bits 0.013280s 0.016518s     75.3     60.5   software integer
  56 # dsa 2048 bits 0.009911s 0.011522s    100.9     86.8   software SSE2
  57 # dsa 2048 bits 0.009542s 0.011763s    104.8     85.0   hardware VIA SDK
  58 # dsa 2048 bits 0.002884s 0.003352s    346.8    298.3   hardware this
  59 #
  60 # To give you some other reference point here is output for 2.4GHz P4
  61 # running hand-coded SSE2 bn_mul_mont found in 0.9.9, i.e. "software
  62 # SSE2" in above terms.
  63 #
  64 # rsa  512 bits 0.000407s 0.000047s   2454.2  21137.0
  65 # rsa 1024 bits 0.002426s 0.000141s    412.1   7100.0
  66 # rsa 2048 bits 0.015046s 0.000491s     66.5   2034.9
  67 # rsa 4096 bits 0.109770s 0.002379s      9.1    420.3
  68 # dsa  512 bits 0.000438s 0.000525s   2281.1   1904.1
  69 # dsa 1024 bits 0.001346s 0.001595s    742.7    627.0
  70 # dsa 2048 bits 0.004745s 0.005582s    210.7    179.1
  71 #
  72 # Conclusions:
  73 # - VIA SDK leaves a *lot* of room for improvement (which this
  74 #   implementation successfully fills:-);
  75 # - 'rep montmul' gives up to >3x performance improvement depending on
  76 #   key length;
  77 # - in terms of absolute performance it delivers approximately as much
  78 #   as modern out-of-order 32-bit cores [again, for longer keys].
  79
  80 push(@INC,".","../../perlasm");
  81 require "x86asm.pl";
  82
  83 &asm_init($ARGV[0],"via-mont.pl");
  84
  85 # int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, const BN_ULONG *np,const BN_ULONG *n0, int num);
  86 $func="bn_mul_mont_padlock";
  87
  88 $pad=16*1;      # amount of reserved bytes on top of every vector
  89
  90 # stack layout
  91 $mZeroPrime=&DWP(0,"esp");              # these are specified by VIA
  92 $A=&DWP(4,"esp");
  93 $B=&DWP(8,"esp");
  94 $T=&DWP(12,"esp");
  95 $M=&DWP(16,"esp");
  96 $scratch=&DWP(20,"esp");
  97 $rp=&DWP(24,"esp");                     # these are mine
  98 $sp=&DWP(28,"esp");
  99 # &DWP(32,"esp")                        # 32 byte scratch area
 100 # &DWP(64+(4*$num+$pad)*0,"esp")        # padded tp[num]
 101 # &DWP(64+(4*$num+$pad)*1,"esp")        # padded copy of ap[num]
 102 # &DWP(64+(4*$num+$pad)*2,"esp")        # padded copy of bp[num]
 103 # &DWP(64+(4*$num+$pad)*2,"esp")        # padded copy of np[num]
 104 # Note that SDK suggests to unconditionally allocate 2K per vector. This
 105 # has quite an impact on performance. It naturally depends on key length,
 106 # but to give an example 1024 bit private RSA key operations suffer >30%
 107 # penalty. I allocate only as much as actually required...
 108
 109 &function_begin($func);
 110         &xor    ("eax","eax");
 111         &mov    ("ecx",&wparam(5));     # num
 112         # meet VIA's limitations for num [note that the specification
 113         # expresses them in bits, while we work with amount of 32-bit words]
 114         &test   ("ecx",3);
 115         &jnz    (&label("leave"));      # num % 4 != 0
 116         &cmp    ("ecx",8);
 117         &jb     (&label("leave"));      # num < 8
 118         &cmp    ("ecx",256);
 119         &ja     (&label("leave"));      # num > 1024
 120
 121         &pushf  ();
 122         &cld    ();
 123
 124         &mov    ("edi",&wparam(0));     # rp
 125         &mov    ("eax",&wparam(1));     # ap
 126         &mov    ("ebx",&wparam(2));     # bp
 127         &mov    ("edx",&wparam(3));     # np
 128         &mov    ("esi",&wparam(4));     # n0
 129         &mov    ("esi",&DWP(0,"esi"));  # *n0
 130
 131         &lea    ("ecx",&DWP($pad,"","ecx",4));  # ecx becomes vector size in bytes
 132         &lea    ("ebp",&DWP(64,"","ecx",4));    # allocate 4 vectors + 64 bytes
 133         &neg    ("ebp");
 134         &add    ("ebp","esp");
 135         &and    ("ebp",-64);            # align to cache-line
 136         &xchg   ("ebp","esp");          # alloca
 137
 138         &mov    ($rp,"edi");            # save rp
 139         &mov    ($sp,"ebp");            # save esp
 140
 141         &mov    ($mZeroPrime,"esi");
 142         &lea    ("esi",&DWP(64,"esp")); # tp
 143         &mov    ($T,"esi");
 144         &lea    ("edi",&DWP(32,"esp")); # scratch area
 145         &mov    ($scratch,"edi");
 146         &mov    ("esi","eax");
 147
 148         &lea    ("ebp",&DWP(-$pad,"ecx"));
 149         &shr    ("ebp",2);              # restore original num value in ebp
 150
 151         &add    ("ecx",32/4);           # (4 vectors + 32 byte scratch)/4
 152         &xor    ("eax","eax");
 153         &data_byte(0xf3,0xab);          # rep stosl, bzero
 154
 155         &mov    ("ecx","ebp");
 156         &lea    ("edi",&DWP(64+$pad,"esp","ecx",4));# pointer to ap copy
 157         &mov    ($A,"edi");
 158         &data_byte(0xf3,0xa5);          # rep movsl, memcpy
 159
 160         # edi points at the end of ap copy...
 161         &mov    ("ecx","ebp");
 162         &add    ("edi",$pad);           # skip padding to point at bp copy
 163         &mov    ("esi","ebx");
 164         &mov    ($B,"edi");
 165         &data_byte(0xf3,0xa5);          # rep movsl, memcpy
 166
 167         # edi points at the end of bp copy...
 168         &mov    ("ecx","ebp");
 169         &add    ("edi",$pad);           # skip padding to point at np copy
 170         &mov    ("esi","edx");
 171         &mov    ($M,"edi");
 172         &data_byte(0xf3,0xa5);          # rep movsl, memcpy
 173
 174         # let magic happen...
 175         &mov    ("ecx","ebp");
 176         &mov    ("esi","esp");
 177         &xor    ("eax","eax");
 178         &shl    ("ecx",5);              # convert word counter to bit counter
 179         &align  (4);
 180         &data_byte(0xf3,0x0f,0xa6,0xc0);# rep montmul
 181
 182         &mov    ("ecx","ebp");
 183         &xor    ("edx","edx");          # i=0
 184         &lea    ("esi",&DWP(64,"esp")); # tp
 185         # edi still points at the end of np copy...
 186         &neg    ("ebp");
 187         &lea    ("ebp",&DWP(0,"edi","ebp",4));  # so just "rewind"
 188         &mov    ("edi",$rp);            # restore rp
 189
 190         &mov    ("ebx",&DWP(0,"esi","ecx",4));  # upmost overflow bit
 191         &cmp    ("ebx",0);                      # clears CF unconfitionally
 192         &jnz    (&label("sub"));
 193         &mov    ("eax",&DWP(-4,"esi","ecx",4));
 194         &cmp    ("eax",&DWP(-4,"ebp","ecx",4)); # tp[num-1]-np[num-1]?
 195         &jae    (&label("sub"));                # if taken CF is cleared
 196
 197 &set_label("copy",4);
 198         &mov    ("ebx","ecx");
 199         &data_byte(0xf3,0xa5);                  # rep movsl
 200         &mov    ("ecx","ebx");
 201         &jmp    (&label("zap"));
 202
 203 &set_label("sub",16);
 204         &mov    ("eax",&DWP(0,"esi","edx",4));
 205         &sbb    ("eax",&DWP(0,"ebp","edx",4));
 206         &mov    (&DWP(0,"edi","edx",4),"eax");  # rp[i]=tp[i]-np[i]
 207         &lea    ("edx",&DWP(1,"edx"));          # i++
 208         &dec    ("ecx");                        # doesn't affect CF!
 209         &jg     (&label("sub"));
 210         &sbb    ("ebx",0);                      # upmost overflow is still there
 211         &mov    ("ecx","edx");
 212         &jc     (&label("copy"));
 213
 214 &set_label("zap",4);
 215         &mov    ("ebp",$sp);
 216         &xor    ("eax","eax");
 217         &lea    ("ecx",&DWP(64/4+$pad,"","ecx",4));# size of frame divided by 4
 218         &mov    ("edi","esp");
 219         &data_byte(0xf3,0xab);          # rep stosl, bzero
 220
 221         &mov    ("esp","ebp");
 222         &inc    ("eax");                # signal "done"
 223         &popf   ();
 224 &set_label("leave");
 225 &function_end($func);
 226
 227 &asm_finish();