2
0

via-mont.pl 8.8 KB

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