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