Home | History | Annotate | Download | only in asm 
      1 #!/usr/bin/env perl
      2 #
      3 # ====================================================================
      4 # Written by Andy Polyakov <appro (at] 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 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
     81 push(@INC,"${dir}","${dir}../../perlasm");
     82 require "x86asm.pl";
     83 
     84 &asm_init($ARGV[0],"via-mont.pl");
     85 
     86 # 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);
     87 $func="bn_mul_mont_padlock";
     88 
     89 $pad=16*1;	# amount of reserved bytes on top of every vector
     90 
     91 # stack layout
     92 $mZeroPrime=&DWP(0,"esp");		# these are specified by VIA
     93 $A=&DWP(4,"esp");
     94 $B=&DWP(8,"esp");
     95 $T=&DWP(12,"esp");
     96 $M=&DWP(16,"esp");
     97 $scratch=&DWP(20,"esp");
     98 $rp=&DWP(24,"esp");			# these are mine
     99 $sp=&DWP(28,"esp");
    100 # &DWP(32,"esp")			# 32 byte scratch area
    101 # &DWP(64+(4*$num+$pad)*0,"esp")	# padded tp[num]
    102 # &DWP(64+(4*$num+$pad)*1,"esp")	# padded copy of ap[num]
    103 # &DWP(64+(4*$num+$pad)*2,"esp")	# padded copy of bp[num]
    104 # &DWP(64+(4*$num+$pad)*3,"esp")	# padded copy of np[num]
    105 # Note that SDK suggests to unconditionally allocate 2K per vector. This
    106 # has quite an impact on performance. It naturally depends on key length,
    107 # but to give an example 1024 bit private RSA key operations suffer >30%
    108 # penalty. I allocate only as much as actually required...
    109 
    110 &function_begin($func);
    111 	&xor	("eax","eax");
    112 	&mov	("ecx",&wparam(5));	# num
    113 	# meet VIA's limitations for num [note that the specification
    114 	# expresses them in bits, while we work with amount of 32-bit words]
    115 	&test	("ecx",3);
    116 	&jnz	(&label("leave"));	# num % 4 != 0
    117 	&cmp	("ecx",8);
    118 	&jb	(&label("leave"));	# num < 8
    119 	&cmp	("ecx",1024);
    120 	&ja	(&label("leave"));	# num > 1024
    121 
    122 	&pushf	();
    123 	&cld	();
    124 
    125 	&mov	("edi",&wparam(0));	# rp
    126 	&mov	("eax",&wparam(1));	# ap
    127 	&mov	("ebx",&wparam(2));	# bp
    128 	&mov	("edx",&wparam(3));	# np
    129 	&mov	("esi",&wparam(4));	# n0
    130 	&mov	("esi",&DWP(0,"esi"));	# *n0
    131 
    132 	&lea	("ecx",&DWP($pad,"","ecx",4));	# ecx becomes vector size in bytes
    133 	&lea	("ebp",&DWP(64,"","ecx",4));	# allocate 4 vectors + 64 bytes
    134 	&neg	("ebp");
    135 	&add	("ebp","esp");
    136 	&and	("ebp",-64);		# align to cache-line
    137 	&xchg	("ebp","esp");		# alloca
    138 
    139 	&mov	($rp,"edi");		# save rp
    140 	&mov	($sp,"ebp");		# save esp
    141 
    142 	&mov	($mZeroPrime,"esi");
    143 	&lea	("esi",&DWP(64,"esp"));	# tp
    144 	&mov	($T,"esi");
    145 	&lea	("edi",&DWP(32,"esp"));	# scratch area
    146 	&mov	($scratch,"edi");
    147 	&mov	("esi","eax");
    148 
    149 	&lea	("ebp",&DWP(-$pad,"ecx"));
    150 	&shr	("ebp",2);		# restore original num value in ebp
    151 
    152 	&xor	("eax","eax");
    153 
    154 	&mov	("ecx","ebp");
    155 	&lea	("ecx",&DWP((32+$pad)/4,"ecx"));# padded tp + scratch
    156 	&data_byte(0xf3,0xab);		# rep stosl, bzero
    157 
    158 	&mov	("ecx","ebp");
    159 	&lea	("edi",&DWP(64+$pad,"esp","ecx",4));# pointer to ap copy
    160 	&mov	($A,"edi");
    161 	&data_byte(0xf3,0xa5);		# rep movsl, memcpy
    162 	&mov	("ecx",$pad/4);
    163 	&data_byte(0xf3,0xab);		# rep stosl, bzero pad
    164 	# edi points at the end of padded ap copy...
    165 
    166 	&mov	("ecx","ebp");
    167 	&mov	("esi","ebx");
    168 	&mov	($B,"edi");
    169 	&data_byte(0xf3,0xa5);		# rep movsl, memcpy
    170 	&mov	("ecx",$pad/4);
    171 	&data_byte(0xf3,0xab);		# rep stosl, bzero pad
    172 	# edi points at the end of padded bp copy...
    173 
    174 	&mov	("ecx","ebp");
    175 	&mov	("esi","edx");
    176 	&mov	($M,"edi");
    177 	&data_byte(0xf3,0xa5);		# rep movsl, memcpy
    178 	&mov	("ecx",$pad/4);
    179 	&data_byte(0xf3,0xab);		# rep stosl, bzero pad
    180 	# edi points at the end of padded np copy...
    181 
    182 	# let magic happen...
    183 	&mov	("ecx","ebp");
    184 	&mov	("esi","esp");
    185 	&shl	("ecx",5);		# convert word counter to bit counter
    186 	&align	(4);
    187 	&data_byte(0xf3,0x0f,0xa6,0xc0);# rep montmul
    188 
    189 	&mov	("ecx","ebp");
    190 	&lea	("esi",&DWP(64,"esp"));		# tp
    191 	# edi still points at the end of padded np copy...
    192 	&neg	("ebp");
    193 	&lea	("ebp",&DWP(-$pad,"edi","ebp",4));	# so just "rewind"
    194 	&mov	("edi",$rp);			# restore rp
    195 	&xor	("edx","edx");			# i=0 and clear CF
    196 
    197 &set_label("sub",8);
    198 	&mov	("eax",&DWP(0,"esi","edx",4));
    199 	&sbb	("eax",&DWP(0,"ebp","edx",4));
    200 	&mov	(&DWP(0,"edi","edx",4),"eax");	# rp[i]=tp[i]-np[i]
    201 	&lea	("edx",&DWP(1,"edx"));		# i++
    202 	&loop	(&label("sub"));		# doesn't affect CF!
    203 
    204 	&mov	("eax",&DWP(0,"esi","edx",4));	# upmost overflow bit
    205 	&sbb	("eax",0);
    206 	&and	("esi","eax");
    207 	&not	("eax");
    208 	&mov	("ebp","edi");
    209 	&and	("ebp","eax");
    210 	&or	("esi","ebp");			# tp=carry?tp:rp
    211 
    212 	&mov	("ecx","edx");			# num
    213 	&xor	("edx","edx");			# i=0
    214 
    215 &set_label("copy",8);
    216 	&mov	("eax",&DWP(0,"esi","edx",4));
    217 	&mov	(&DWP(64,"esp","edx",4),"ecx");	# zap tp
    218 	&mov	(&DWP(0,"edi","edx",4),"eax");
    219 	&lea	("edx",&DWP(1,"edx"));		# i++
    220 	&loop	(&label("copy"));
    221 
    222 	&mov	("ebp",$sp);
    223 	&xor	("eax","eax");
    224 
    225 	&mov	("ecx",64/4);
    226 	&mov	("edi","esp");		# zap frame including scratch area
    227 	&data_byte(0xf3,0xab);		# rep stosl, bzero
    228 
    229 	# zap copies of ap, bp and np
    230 	&lea	("edi",&DWP(64+$pad,"esp","edx",4));# pointer to ap
    231 	&lea	("ecx",&DWP(3*$pad/4,"edx","edx",2));
    232 	&data_byte(0xf3,0xab);		# rep stosl, bzero
    233 
    234 	&mov	("esp","ebp");
    235 	&inc	("eax");		# signal "done"
    236 	&popf	();
    237 &set_label("leave");
    238 &function_end($func);
    239 
    240 &asciz("Padlock Montgomery Multiplication, CRYPTOGAMS by <appro\@openssl.org>");
    241 
    242 &asm_finish();
    243