1238384Sjkim#!/usr/bin/env perl 2238384Sjkim# 3238384Sjkim# ==================================================================== 4238384Sjkim# Written by Andy Polyakov <appro@fy.chalmers.se> for the OpenSSL 5238384Sjkim# project. The module is, however, dual licensed under OpenSSL and 6238384Sjkim# CRYPTOGAMS licenses depending on where you obtain it. For further 7238384Sjkim# details see http://www.openssl.org/~appro/cryptogams/. 8238384Sjkim# ==================================================================== 9238384Sjkim# 10238384Sjkim# Wrapper around 'rep montmul', VIA-specific instruction accessing 11238384Sjkim# PadLock Montgomery Multiplier. The wrapper is designed as drop-in 12238384Sjkim# replacement for OpenSSL bn_mul_mont [first implemented in 0.9.9]. 13238384Sjkim# 14238384Sjkim# Below are interleaved outputs from 'openssl speed rsa dsa' for 4 15238384Sjkim# different software configurations on 1.5GHz VIA Esther processor. 16238384Sjkim# Lines marked with "software integer" denote performance of hand- 17238384Sjkim# coded integer-only assembler found in OpenSSL 0.9.7. "Software SSE2" 18238384Sjkim# refers to hand-coded SSE2 Montgomery multiplication procedure found 19238384Sjkim# OpenSSL 0.9.9. "Hardware VIA SDK" refers to padlock_pmm routine from 20238384Sjkim# Padlock SDK 2.0.1 available for download from VIA, which naturally 21238384Sjkim# utilizes the magic 'repz montmul' instruction. And finally "hardware 22238384Sjkim# this" refers to *this* implementation which also uses 'repz montmul' 23238384Sjkim# 24238384Sjkim# sign verify sign/s verify/s 25238384Sjkim# rsa 512 bits 0.001720s 0.000140s 581.4 7149.7 software integer 26238384Sjkim# rsa 512 bits 0.000690s 0.000086s 1450.3 11606.0 software SSE2 27238384Sjkim# rsa 512 bits 0.006136s 0.000201s 163.0 4974.5 hardware VIA SDK 28238384Sjkim# rsa 512 bits 0.000712s 0.000050s 1404.9 19858.5 hardware this 29238384Sjkim# 30238384Sjkim# rsa 1024 bits 0.008518s 0.000413s 117.4 2420.8 software integer 31238384Sjkim# rsa 1024 bits 0.004275s 0.000277s 233.9 3609.7 software SSE2 32238384Sjkim# rsa 1024 bits 0.012136s 0.000260s 82.4 3844.5 hardware VIA SDK 33238384Sjkim# rsa 1024 bits 0.002522s 0.000116s 396.5 8650.9 hardware this 34238384Sjkim# 35238384Sjkim# rsa 2048 bits 0.050101s 0.001371s 20.0 729.6 software integer 36238384Sjkim# rsa 2048 bits 0.030273s 0.001008s 33.0 991.9 software SSE2 37238384Sjkim# rsa 2048 bits 0.030833s 0.000976s 32.4 1025.1 hardware VIA SDK 38238384Sjkim# rsa 2048 bits 0.011879s 0.000342s 84.2 2921.7 hardware this 39238384Sjkim# 40238384Sjkim# rsa 4096 bits 0.327097s 0.004859s 3.1 205.8 software integer 41238384Sjkim# rsa 4096 bits 0.229318s 0.003859s 4.4 259.2 software SSE2 42238384Sjkim# rsa 4096 bits 0.233953s 0.003274s 4.3 305.4 hardware VIA SDK 43238384Sjkim# rsa 4096 bits 0.070493s 0.001166s 14.2 857.6 hardware this 44238384Sjkim# 45238384Sjkim# dsa 512 bits 0.001342s 0.001651s 745.2 605.7 software integer 46238384Sjkim# dsa 512 bits 0.000844s 0.000987s 1185.3 1013.1 software SSE2 47238384Sjkim# dsa 512 bits 0.001902s 0.002247s 525.6 444.9 hardware VIA SDK 48238384Sjkim# dsa 512 bits 0.000458s 0.000524s 2182.2 1909.1 hardware this 49238384Sjkim# 50238384Sjkim# dsa 1024 bits 0.003964s 0.004926s 252.3 203.0 software integer 51238384Sjkim# dsa 1024 bits 0.002686s 0.003166s 372.3 315.8 software SSE2 52238384Sjkim# dsa 1024 bits 0.002397s 0.002823s 417.1 354.3 hardware VIA SDK 53238384Sjkim# dsa 1024 bits 0.000978s 0.001170s 1022.2 855.0 hardware this 54238384Sjkim# 55238384Sjkim# dsa 2048 bits 0.013280s 0.016518s 75.3 60.5 software integer 56238384Sjkim# dsa 2048 bits 0.009911s 0.011522s 100.9 86.8 software SSE2 57238384Sjkim# dsa 2048 bits 0.009542s 0.011763s 104.8 85.0 hardware VIA SDK 58238384Sjkim# dsa 2048 bits 0.002884s 0.003352s 346.8 298.3 hardware this 59238384Sjkim# 60238384Sjkim# To give you some other reference point here is output for 2.4GHz P4 61238384Sjkim# running hand-coded SSE2 bn_mul_mont found in 0.9.9, i.e. "software 62238384Sjkim# SSE2" in above terms. 63238384Sjkim# 64238384Sjkim# rsa 512 bits 0.000407s 0.000047s 2454.2 21137.0 65238384Sjkim# rsa 1024 bits 0.002426s 0.000141s 412.1 7100.0 66238384Sjkim# rsa 2048 bits 0.015046s 0.000491s 66.5 2034.9 67238384Sjkim# rsa 4096 bits 0.109770s 0.002379s 9.1 420.3 68238384Sjkim# dsa 512 bits 0.000438s 0.000525s 2281.1 1904.1 69238384Sjkim# dsa 1024 bits 0.001346s 0.001595s 742.7 627.0 70238384Sjkim# dsa 2048 bits 0.004745s 0.005582s 210.7 179.1 71238384Sjkim# 72238384Sjkim# Conclusions: 73238384Sjkim# - VIA SDK leaves a *lot* of room for improvement (which this 74238384Sjkim# implementation successfully fills:-); 75238384Sjkim# - 'rep montmul' gives up to >3x performance improvement depending on 76238384Sjkim# key length; 77238384Sjkim# - in terms of absolute performance it delivers approximately as much 78238384Sjkim# as modern out-of-order 32-bit cores [again, for longer keys]. 79238384Sjkim 80238384Sjkim$0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1; 81238384Sjkimpush(@INC,"${dir}","${dir}../../perlasm"); 82238384Sjkimrequire "x86asm.pl"; 83238384Sjkim 84238384Sjkim&asm_init($ARGV[0],"via-mont.pl"); 85238384Sjkim 86238384Sjkim# 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); 87238384Sjkim$func="bn_mul_mont_padlock"; 88238384Sjkim 89238384Sjkim$pad=16*1; # amount of reserved bytes on top of every vector 90238384Sjkim 91238384Sjkim# stack layout 92238384Sjkim$mZeroPrime=&DWP(0,"esp"); # these are specified by VIA 93238384Sjkim$A=&DWP(4,"esp"); 94238384Sjkim$B=&DWP(8,"esp"); 95238384Sjkim$T=&DWP(12,"esp"); 96238384Sjkim$M=&DWP(16,"esp"); 97238384Sjkim$scratch=&DWP(20,"esp"); 98238384Sjkim$rp=&DWP(24,"esp"); # these are mine 99238384Sjkim$sp=&DWP(28,"esp"); 100238384Sjkim# &DWP(32,"esp") # 32 byte scratch area 101238384Sjkim# &DWP(64+(4*$num+$pad)*0,"esp") # padded tp[num] 102238384Sjkim# &DWP(64+(4*$num+$pad)*1,"esp") # padded copy of ap[num] 103238384Sjkim# &DWP(64+(4*$num+$pad)*2,"esp") # padded copy of bp[num] 104238384Sjkim# &DWP(64+(4*$num+$pad)*3,"esp") # padded copy of np[num] 105238384Sjkim# Note that SDK suggests to unconditionally allocate 2K per vector. This 106238384Sjkim# has quite an impact on performance. It naturally depends on key length, 107238384Sjkim# but to give an example 1024 bit private RSA key operations suffer >30% 108238384Sjkim# penalty. I allocate only as much as actually required... 109238384Sjkim 110238384Sjkim&function_begin($func); 111238384Sjkim &xor ("eax","eax"); 112238384Sjkim &mov ("ecx",&wparam(5)); # num 113238384Sjkim # meet VIA's limitations for num [note that the specification 114238384Sjkim # expresses them in bits, while we work with amount of 32-bit words] 115238384Sjkim &test ("ecx",3); 116238384Sjkim &jnz (&label("leave")); # num % 4 != 0 117238384Sjkim &cmp ("ecx",8); 118238384Sjkim &jb (&label("leave")); # num < 8 119238384Sjkim &cmp ("ecx",1024); 120238384Sjkim &ja (&label("leave")); # num > 1024 121238384Sjkim 122238384Sjkim &pushf (); 123238384Sjkim &cld (); 124238384Sjkim 125238384Sjkim &mov ("edi",&wparam(0)); # rp 126238384Sjkim &mov ("eax",&wparam(1)); # ap 127238384Sjkim &mov ("ebx",&wparam(2)); # bp 128238384Sjkim &mov ("edx",&wparam(3)); # np 129238384Sjkim &mov ("esi",&wparam(4)); # n0 130238384Sjkim &mov ("esi",&DWP(0,"esi")); # *n0 131238384Sjkim 132238384Sjkim &lea ("ecx",&DWP($pad,"","ecx",4)); # ecx becomes vector size in bytes 133238384Sjkim &lea ("ebp",&DWP(64,"","ecx",4)); # allocate 4 vectors + 64 bytes 134238384Sjkim &neg ("ebp"); 135238384Sjkim &add ("ebp","esp"); 136238384Sjkim &and ("ebp",-64); # align to cache-line 137238384Sjkim &xchg ("ebp","esp"); # alloca 138238384Sjkim 139238384Sjkim &mov ($rp,"edi"); # save rp 140238384Sjkim &mov ($sp,"ebp"); # save esp 141238384Sjkim 142238384Sjkim &mov ($mZeroPrime,"esi"); 143238384Sjkim &lea ("esi",&DWP(64,"esp")); # tp 144238384Sjkim &mov ($T,"esi"); 145238384Sjkim &lea ("edi",&DWP(32,"esp")); # scratch area 146238384Sjkim &mov ($scratch,"edi"); 147238384Sjkim &mov ("esi","eax"); 148238384Sjkim 149238384Sjkim &lea ("ebp",&DWP(-$pad,"ecx")); 150238384Sjkim &shr ("ebp",2); # restore original num value in ebp 151238384Sjkim 152238384Sjkim &xor ("eax","eax"); 153238384Sjkim 154238384Sjkim &mov ("ecx","ebp"); 155238384Sjkim &lea ("ecx",&DWP((32+$pad)/4,"ecx"));# padded tp + scratch 156238384Sjkim &data_byte(0xf3,0xab); # rep stosl, bzero 157238384Sjkim 158238384Sjkim &mov ("ecx","ebp"); 159238384Sjkim &lea ("edi",&DWP(64+$pad,"esp","ecx",4));# pointer to ap copy 160238384Sjkim &mov ($A,"edi"); 161238384Sjkim &data_byte(0xf3,0xa5); # rep movsl, memcpy 162238384Sjkim &mov ("ecx",$pad/4); 163238384Sjkim &data_byte(0xf3,0xab); # rep stosl, bzero pad 164238384Sjkim # edi points at the end of padded ap copy... 165238384Sjkim 166238384Sjkim &mov ("ecx","ebp"); 167238384Sjkim &mov ("esi","ebx"); 168238384Sjkim &mov ($B,"edi"); 169238384Sjkim &data_byte(0xf3,0xa5); # rep movsl, memcpy 170238384Sjkim &mov ("ecx",$pad/4); 171238384Sjkim &data_byte(0xf3,0xab); # rep stosl, bzero pad 172238384Sjkim # edi points at the end of padded bp copy... 173238384Sjkim 174238384Sjkim &mov ("ecx","ebp"); 175238384Sjkim &mov ("esi","edx"); 176238384Sjkim &mov ($M,"edi"); 177238384Sjkim &data_byte(0xf3,0xa5); # rep movsl, memcpy 178238384Sjkim &mov ("ecx",$pad/4); 179238384Sjkim &data_byte(0xf3,0xab); # rep stosl, bzero pad 180238384Sjkim # edi points at the end of padded np copy... 181238384Sjkim 182238384Sjkim # let magic happen... 183238384Sjkim &mov ("ecx","ebp"); 184238384Sjkim &mov ("esi","esp"); 185238384Sjkim &shl ("ecx",5); # convert word counter to bit counter 186238384Sjkim &align (4); 187238384Sjkim &data_byte(0xf3,0x0f,0xa6,0xc0);# rep montmul 188238384Sjkim 189238384Sjkim &mov ("ecx","ebp"); 190238384Sjkim &lea ("esi",&DWP(64,"esp")); # tp 191238384Sjkim # edi still points at the end of padded np copy... 192238384Sjkim &neg ("ebp"); 193238384Sjkim &lea ("ebp",&DWP(-$pad,"edi","ebp",4)); # so just "rewind" 194238384Sjkim &mov ("edi",$rp); # restore rp 195238384Sjkim &xor ("edx","edx"); # i=0 and clear CF 196238384Sjkim 197238384Sjkim&set_label("sub",8); 198238384Sjkim &mov ("eax",&DWP(0,"esi","edx",4)); 199238384Sjkim &sbb ("eax",&DWP(0,"ebp","edx",4)); 200238384Sjkim &mov (&DWP(0,"edi","edx",4),"eax"); # rp[i]=tp[i]-np[i] 201238384Sjkim &lea ("edx",&DWP(1,"edx")); # i++ 202238384Sjkim &loop (&label("sub")); # doesn't affect CF! 203238384Sjkim 204238384Sjkim &mov ("eax",&DWP(0,"esi","edx",4)); # upmost overflow bit 205238384Sjkim &sbb ("eax",0); 206238384Sjkim &and ("esi","eax"); 207238384Sjkim ¬ ("eax"); 208238384Sjkim &mov ("ebp","edi"); 209238384Sjkim &and ("ebp","eax"); 210238384Sjkim &or ("esi","ebp"); # tp=carry?tp:rp 211238384Sjkim 212238384Sjkim &mov ("ecx","edx"); # num 213238384Sjkim &xor ("edx","edx"); # i=0 214238384Sjkim 215238384Sjkim&set_label("copy",8); 216238384Sjkim &mov ("eax",&DWP(0,"esi","edx",4)); 217238384Sjkim &mov (&DWP(64,"esp","edx",4),"ecx"); # zap tp 218238384Sjkim &mov (&DWP(0,"edi","edx",4),"eax"); 219238384Sjkim &lea ("edx",&DWP(1,"edx")); # i++ 220238384Sjkim &loop (&label("copy")); 221238384Sjkim 222238384Sjkim &mov ("ebp",$sp); 223238384Sjkim &xor ("eax","eax"); 224238384Sjkim 225238384Sjkim &mov ("ecx",64/4); 226238384Sjkim &mov ("edi","esp"); # zap frame including scratch area 227238384Sjkim &data_byte(0xf3,0xab); # rep stosl, bzero 228238384Sjkim 229238384Sjkim # zap copies of ap, bp and np 230238384Sjkim &lea ("edi",&DWP(64+$pad,"esp","edx",4));# pointer to ap 231238384Sjkim &lea ("ecx",&DWP(3*$pad/4,"edx","edx",2)); 232238384Sjkim &data_byte(0xf3,0xab); # rep stosl, bzero 233238384Sjkim 234238384Sjkim &mov ("esp","ebp"); 235238384Sjkim &inc ("eax"); # signal "done" 236238384Sjkim &popf (); 237238384Sjkim&set_label("leave"); 238238384Sjkim&function_end($func); 239238384Sjkim 240238384Sjkim&asciz("Padlock Montgomery Multiplication, CRYPTOGAMS by <appro\@openssl.org>"); 241238384Sjkim 242238384Sjkim&asm_finish(); 243