| 1 | #! /usr/bin/env perl
|
|---|
| 2 | # Copyright 2011-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 <[email protected]> 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 | # May 2011
|
|---|
| 18 | #
|
|---|
| 19 | # The module implements bn_GF2m_mul_2x2 polynomial multiplication
|
|---|
| 20 | # used in bn_gf2m.c. It's kind of low-hanging mechanical port from
|
|---|
| 21 | # C for the time being... Except that it has two code paths: pure
|
|---|
| 22 | # integer code suitable for any ARMv4 and later CPU and NEON code
|
|---|
| 23 | # suitable for ARMv7. Pure integer 1x1 multiplication subroutine runs
|
|---|
| 24 | # in ~45 cycles on dual-issue core such as Cortex A8, which is ~50%
|
|---|
| 25 | # faster than compiler-generated code. For ECDH and ECDSA verify (but
|
|---|
| 26 | # not for ECDSA sign) it means 25%-45% improvement depending on key
|
|---|
| 27 | # length, more for longer keys. Even though NEON 1x1 multiplication
|
|---|
| 28 | # runs in even less cycles, ~30, improvement is measurable only on
|
|---|
| 29 | # longer keys. One has to optimize code elsewhere to get NEON glow...
|
|---|
| 30 | #
|
|---|
| 31 | # April 2014
|
|---|
| 32 | #
|
|---|
| 33 | # Double bn_GF2m_mul_2x2 performance by using algorithm from paper
|
|---|
| 34 | # referred below, which improves ECDH and ECDSA verify benchmarks
|
|---|
| 35 | # by 18-40%.
|
|---|
| 36 | #
|
|---|
| 37 | # Câmara, D.; Gouvêa, C. P. L.; López, J. & Dahab, R.: Fast Software
|
|---|
| 38 | # Polynomial Multiplication on ARM Processors using the NEON Engine.
|
|---|
| 39 | #
|
|---|
| 40 | # http://conradoplg.cryptoland.net/files/2010/12/mocrysen13.pdf
|
|---|
| 41 |
|
|---|
| 42 | $flavour = shift;
|
|---|
| 43 | if ($flavour=~/\w[\w\-]*\.\w+$/) { $output=$flavour; undef $flavour; }
|
|---|
| 44 | else { while (($output=shift) && ($output!~/\w[\w\-]*\.\w+$/)) {} }
|
|---|
| 45 |
|
|---|
| 46 | if ($flavour && $flavour ne "void") {
|
|---|
| 47 | $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
|
|---|
| 48 | ( $xlate="${dir}arm-xlate.pl" and -f $xlate ) or
|
|---|
| 49 | ( $xlate="${dir}../../perlasm/arm-xlate.pl" and -f $xlate) or
|
|---|
| 50 | die "can't locate arm-xlate.pl";
|
|---|
| 51 |
|
|---|
| 52 | open STDOUT,"| \"$^X\" $xlate $flavour $output";
|
|---|
| 53 | } else {
|
|---|
| 54 | open STDOUT,">$output";
|
|---|
| 55 | }
|
|---|
| 56 |
|
|---|
| 57 | $code=<<___;
|
|---|
| 58 | #include "arm_arch.h"
|
|---|
| 59 |
|
|---|
| 60 | .text
|
|---|
| 61 | #if defined(__thumb2__)
|
|---|
| 62 | .syntax unified
|
|---|
| 63 | .thumb
|
|---|
| 64 | #else
|
|---|
| 65 | .code 32
|
|---|
| 66 | #endif
|
|---|
| 67 | ___
|
|---|
| 68 | ################
|
|---|
| 69 | # private interface to mul_1x1_ialu
|
|---|
| 70 | #
|
|---|
| 71 | $a="r1";
|
|---|
| 72 | $b="r0";
|
|---|
| 73 |
|
|---|
| 74 | ($a0,$a1,$a2,$a12,$a4,$a14)=
|
|---|
| 75 | ($hi,$lo,$t0,$t1, $i0,$i1 )=map("r$_",(4..9),12);
|
|---|
| 76 |
|
|---|
| 77 | $mask="r12";
|
|---|
| 78 |
|
|---|
| 79 | $code.=<<___;
|
|---|
| 80 | .type mul_1x1_ialu,%function
|
|---|
| 81 | .align 5
|
|---|
| 82 | mul_1x1_ialu:
|
|---|
| 83 | mov $a0,#0
|
|---|
| 84 | bic $a1,$a,#3<<30 @ a1=a&0x3fffffff
|
|---|
| 85 | str $a0,[sp,#0] @ tab[0]=0
|
|---|
| 86 | add $a2,$a1,$a1 @ a2=a1<<1
|
|---|
| 87 | str $a1,[sp,#4] @ tab[1]=a1
|
|---|
| 88 | eor $a12,$a1,$a2 @ a1^a2
|
|---|
| 89 | str $a2,[sp,#8] @ tab[2]=a2
|
|---|
| 90 | mov $a4,$a1,lsl#2 @ a4=a1<<2
|
|---|
| 91 | str $a12,[sp,#12] @ tab[3]=a1^a2
|
|---|
| 92 | eor $a14,$a1,$a4 @ a1^a4
|
|---|
| 93 | str $a4,[sp,#16] @ tab[4]=a4
|
|---|
| 94 | eor $a0,$a2,$a4 @ a2^a4
|
|---|
| 95 | str $a14,[sp,#20] @ tab[5]=a1^a4
|
|---|
| 96 | eor $a12,$a12,$a4 @ a1^a2^a4
|
|---|
| 97 | str $a0,[sp,#24] @ tab[6]=a2^a4
|
|---|
| 98 | and $i0,$mask,$b,lsl#2
|
|---|
| 99 | str $a12,[sp,#28] @ tab[7]=a1^a2^a4
|
|---|
| 100 |
|
|---|
| 101 | and $i1,$mask,$b,lsr#1
|
|---|
| 102 | ldr $lo,[sp,$i0] @ tab[b & 0x7]
|
|---|
| 103 | and $i0,$mask,$b,lsr#4
|
|---|
| 104 | ldr $t1,[sp,$i1] @ tab[b >> 3 & 0x7]
|
|---|
| 105 | and $i1,$mask,$b,lsr#7
|
|---|
| 106 | ldr $t0,[sp,$i0] @ tab[b >> 6 & 0x7]
|
|---|
| 107 | eor $lo,$lo,$t1,lsl#3 @ stall
|
|---|
| 108 | mov $hi,$t1,lsr#29
|
|---|
| 109 | ldr $t1,[sp,$i1] @ tab[b >> 9 & 0x7]
|
|---|
| 110 |
|
|---|
| 111 | and $i0,$mask,$b,lsr#10
|
|---|
| 112 | eor $lo,$lo,$t0,lsl#6
|
|---|
| 113 | eor $hi,$hi,$t0,lsr#26
|
|---|
| 114 | ldr $t0,[sp,$i0] @ tab[b >> 12 & 0x7]
|
|---|
| 115 |
|
|---|
| 116 | and $i1,$mask,$b,lsr#13
|
|---|
| 117 | eor $lo,$lo,$t1,lsl#9
|
|---|
| 118 | eor $hi,$hi,$t1,lsr#23
|
|---|
| 119 | ldr $t1,[sp,$i1] @ tab[b >> 15 & 0x7]
|
|---|
| 120 |
|
|---|
| 121 | and $i0,$mask,$b,lsr#16
|
|---|
| 122 | eor $lo,$lo,$t0,lsl#12
|
|---|
| 123 | eor $hi,$hi,$t0,lsr#20
|
|---|
| 124 | ldr $t0,[sp,$i0] @ tab[b >> 18 & 0x7]
|
|---|
| 125 |
|
|---|
| 126 | and $i1,$mask,$b,lsr#19
|
|---|
| 127 | eor $lo,$lo,$t1,lsl#15
|
|---|
| 128 | eor $hi,$hi,$t1,lsr#17
|
|---|
| 129 | ldr $t1,[sp,$i1] @ tab[b >> 21 & 0x7]
|
|---|
| 130 |
|
|---|
| 131 | and $i0,$mask,$b,lsr#22
|
|---|
| 132 | eor $lo,$lo,$t0,lsl#18
|
|---|
| 133 | eor $hi,$hi,$t0,lsr#14
|
|---|
| 134 | ldr $t0,[sp,$i0] @ tab[b >> 24 & 0x7]
|
|---|
| 135 |
|
|---|
| 136 | and $i1,$mask,$b,lsr#25
|
|---|
| 137 | eor $lo,$lo,$t1,lsl#21
|
|---|
| 138 | eor $hi,$hi,$t1,lsr#11
|
|---|
| 139 | ldr $t1,[sp,$i1] @ tab[b >> 27 & 0x7]
|
|---|
| 140 |
|
|---|
| 141 | tst $a,#1<<30
|
|---|
| 142 | and $i0,$mask,$b,lsr#28
|
|---|
| 143 | eor $lo,$lo,$t0,lsl#24
|
|---|
| 144 | eor $hi,$hi,$t0,lsr#8
|
|---|
| 145 | ldr $t0,[sp,$i0] @ tab[b >> 30 ]
|
|---|
| 146 |
|
|---|
| 147 | #ifdef __thumb2__
|
|---|
| 148 | itt ne
|
|---|
| 149 | #endif
|
|---|
| 150 | eorne $lo,$lo,$b,lsl#30
|
|---|
| 151 | eorne $hi,$hi,$b,lsr#2
|
|---|
| 152 | tst $a,#1<<31
|
|---|
| 153 | eor $lo,$lo,$t1,lsl#27
|
|---|
| 154 | eor $hi,$hi,$t1,lsr#5
|
|---|
| 155 | #ifdef __thumb2__
|
|---|
| 156 | itt ne
|
|---|
| 157 | #endif
|
|---|
| 158 | eorne $lo,$lo,$b,lsl#31
|
|---|
| 159 | eorne $hi,$hi,$b,lsr#1
|
|---|
| 160 | eor $lo,$lo,$t0,lsl#30
|
|---|
| 161 | eor $hi,$hi,$t0,lsr#2
|
|---|
| 162 |
|
|---|
| 163 | mov pc,lr
|
|---|
| 164 | .size mul_1x1_ialu,.-mul_1x1_ialu
|
|---|
| 165 | ___
|
|---|
| 166 | ################
|
|---|
| 167 | # void bn_GF2m_mul_2x2(BN_ULONG *r,
|
|---|
| 168 | # BN_ULONG a1,BN_ULONG a0,
|
|---|
| 169 | # BN_ULONG b1,BN_ULONG b0); # r[3..0]=a1a0·b1b0
|
|---|
| 170 | {
|
|---|
| 171 | $code.=<<___;
|
|---|
| 172 | .global bn_GF2m_mul_2x2
|
|---|
| 173 | .type bn_GF2m_mul_2x2,%function
|
|---|
| 174 | .align 5
|
|---|
| 175 | bn_GF2m_mul_2x2:
|
|---|
| 176 | #if __ARM_MAX_ARCH__>=7
|
|---|
| 177 | stmdb sp!,{r10,lr}
|
|---|
| 178 | ldr r12,.LOPENSSL_armcap
|
|---|
| 179 | adr r10,.LOPENSSL_armcap
|
|---|
| 180 | ldr r12,[r12,r10]
|
|---|
| 181 | #ifdef __APPLE__
|
|---|
| 182 | ldr r12,[r12]
|
|---|
| 183 | #endif
|
|---|
| 184 | tst r12,#ARMV7_NEON
|
|---|
| 185 | itt ne
|
|---|
| 186 | ldrne r10,[sp],#8
|
|---|
| 187 | bne .LNEON
|
|---|
| 188 | stmdb sp!,{r4-r9}
|
|---|
| 189 | #else
|
|---|
| 190 | stmdb sp!,{r4-r10,lr}
|
|---|
| 191 | #endif
|
|---|
| 192 | ___
|
|---|
| 193 | $ret="r10"; # reassigned 1st argument
|
|---|
| 194 | $code.=<<___;
|
|---|
| 195 | mov $ret,r0 @ reassign 1st argument
|
|---|
| 196 | mov $b,r3 @ $b=b1
|
|---|
| 197 | sub r7,sp,#36
|
|---|
| 198 | mov r8,sp
|
|---|
| 199 | and r7,r7,#-32
|
|---|
| 200 | ldr r3,[sp,#32] @ load b0
|
|---|
| 201 | mov $mask,#7<<2
|
|---|
| 202 | mov sp,r7 @ allocate tab[8]
|
|---|
| 203 | str r8,[r7,#32]
|
|---|
| 204 |
|
|---|
| 205 | bl mul_1x1_ialu @ a1·b1
|
|---|
| 206 | str $lo,[$ret,#8]
|
|---|
| 207 | str $hi,[$ret,#12]
|
|---|
| 208 |
|
|---|
| 209 | eor $b,$b,r3 @ flip b0 and b1
|
|---|
| 210 | eor $a,$a,r2 @ flip a0 and a1
|
|---|
| 211 | eor r3,r3,$b
|
|---|
| 212 | eor r2,r2,$a
|
|---|
| 213 | eor $b,$b,r3
|
|---|
| 214 | eor $a,$a,r2
|
|---|
| 215 | bl mul_1x1_ialu @ a0·b0
|
|---|
| 216 | str $lo,[$ret]
|
|---|
| 217 | str $hi,[$ret,#4]
|
|---|
| 218 |
|
|---|
| 219 | eor $a,$a,r2
|
|---|
| 220 | eor $b,$b,r3
|
|---|
| 221 | bl mul_1x1_ialu @ (a1+a0)·(b1+b0)
|
|---|
| 222 | ___
|
|---|
| 223 | @r=map("r$_",(6..9));
|
|---|
| 224 | $code.=<<___;
|
|---|
| 225 | ldmia $ret,{@r[0]-@r[3]}
|
|---|
| 226 | eor $lo,$lo,$hi
|
|---|
| 227 | ldr sp,[sp,#32] @ destroy tab[8]
|
|---|
| 228 | eor $hi,$hi,@r[1]
|
|---|
| 229 | eor $lo,$lo,@r[0]
|
|---|
| 230 | eor $hi,$hi,@r[2]
|
|---|
| 231 | eor $lo,$lo,@r[3]
|
|---|
| 232 | eor $hi,$hi,@r[3]
|
|---|
| 233 | str $hi,[$ret,#8]
|
|---|
| 234 | eor $lo,$lo,$hi
|
|---|
| 235 | str $lo,[$ret,#4]
|
|---|
| 236 |
|
|---|
| 237 | #if __ARM_ARCH__>=5
|
|---|
| 238 | ldmia sp!,{r4-r10,pc}
|
|---|
| 239 | #else
|
|---|
| 240 | ldmia sp!,{r4-r10,lr}
|
|---|
| 241 | tst lr,#1
|
|---|
| 242 | moveq pc,lr @ be binary compatible with V4, yet
|
|---|
| 243 | bx lr @ interoperable with Thumb ISA:-)
|
|---|
| 244 | #endif
|
|---|
| 245 | ___
|
|---|
| 246 | }
|
|---|
| 247 | {
|
|---|
| 248 | my ($r,$t0,$t1,$t2,$t3)=map("q$_",(0..3,8..12));
|
|---|
| 249 | my ($a,$b,$k48,$k32,$k16)=map("d$_",(26..31));
|
|---|
| 250 |
|
|---|
| 251 | $code.=<<___;
|
|---|
| 252 | #if __ARM_MAX_ARCH__>=7
|
|---|
| 253 | .arch armv7-a
|
|---|
| 254 | .fpu neon
|
|---|
| 255 |
|
|---|
| 256 | .align 5
|
|---|
| 257 | .LNEON:
|
|---|
| 258 | ldr r12, [sp] @ 5th argument
|
|---|
| 259 | vmov $a, r2, r1
|
|---|
| 260 | vmov $b, r12, r3
|
|---|
| 261 | vmov.i64 $k48, #0x0000ffffffffffff
|
|---|
| 262 | vmov.i64 $k32, #0x00000000ffffffff
|
|---|
| 263 | vmov.i64 $k16, #0x000000000000ffff
|
|---|
| 264 |
|
|---|
| 265 | vext.8 $t0#lo, $a, $a, #1 @ A1
|
|---|
| 266 | vmull.p8 $t0, $t0#lo, $b @ F = A1*B
|
|---|
| 267 | vext.8 $r#lo, $b, $b, #1 @ B1
|
|---|
| 268 | vmull.p8 $r, $a, $r#lo @ E = A*B1
|
|---|
| 269 | vext.8 $t1#lo, $a, $a, #2 @ A2
|
|---|
| 270 | vmull.p8 $t1, $t1#lo, $b @ H = A2*B
|
|---|
| 271 | vext.8 $t3#lo, $b, $b, #2 @ B2
|
|---|
| 272 | vmull.p8 $t3, $a, $t3#lo @ G = A*B2
|
|---|
| 273 | vext.8 $t2#lo, $a, $a, #3 @ A3
|
|---|
| 274 | veor $t0, $t0, $r @ L = E + F
|
|---|
| 275 | vmull.p8 $t2, $t2#lo, $b @ J = A3*B
|
|---|
| 276 | vext.8 $r#lo, $b, $b, #3 @ B3
|
|---|
| 277 | veor $t1, $t1, $t3 @ M = G + H
|
|---|
| 278 | vmull.p8 $r, $a, $r#lo @ I = A*B3
|
|---|
| 279 | veor $t0#lo, $t0#lo, $t0#hi @ t0 = (L) (P0 + P1) << 8
|
|---|
| 280 | vand $t0#hi, $t0#hi, $k48
|
|---|
| 281 | vext.8 $t3#lo, $b, $b, #4 @ B4
|
|---|
| 282 | veor $t1#lo, $t1#lo, $t1#hi @ t1 = (M) (P2 + P3) << 16
|
|---|
| 283 | vand $t1#hi, $t1#hi, $k32
|
|---|
| 284 | vmull.p8 $t3, $a, $t3#lo @ K = A*B4
|
|---|
| 285 | veor $t2, $t2, $r @ N = I + J
|
|---|
| 286 | veor $t0#lo, $t0#lo, $t0#hi
|
|---|
| 287 | veor $t1#lo, $t1#lo, $t1#hi
|
|---|
| 288 | veor $t2#lo, $t2#lo, $t2#hi @ t2 = (N) (P4 + P5) << 24
|
|---|
| 289 | vand $t2#hi, $t2#hi, $k16
|
|---|
| 290 | vext.8 $t0, $t0, $t0, #15
|
|---|
| 291 | veor $t3#lo, $t3#lo, $t3#hi @ t3 = (K) (P6 + P7) << 32
|
|---|
| 292 | vmov.i64 $t3#hi, #0
|
|---|
| 293 | vext.8 $t1, $t1, $t1, #14
|
|---|
| 294 | veor $t2#lo, $t2#lo, $t2#hi
|
|---|
| 295 | vmull.p8 $r, $a, $b @ D = A*B
|
|---|
| 296 | vext.8 $t3, $t3, $t3, #12
|
|---|
| 297 | vext.8 $t2, $t2, $t2, #13
|
|---|
| 298 | veor $t0, $t0, $t1
|
|---|
| 299 | veor $t2, $t2, $t3
|
|---|
| 300 | veor $r, $r, $t0
|
|---|
| 301 | veor $r, $r, $t2
|
|---|
| 302 |
|
|---|
| 303 | vst1.32 {$r}, [r0]
|
|---|
| 304 | ret @ bx lr
|
|---|
| 305 | #endif
|
|---|
| 306 | ___
|
|---|
| 307 | }
|
|---|
| 308 | $code.=<<___;
|
|---|
| 309 | .size bn_GF2m_mul_2x2,.-bn_GF2m_mul_2x2
|
|---|
| 310 | #if __ARM_MAX_ARCH__>=7
|
|---|
| 311 | .align 5
|
|---|
| 312 | .LOPENSSL_armcap:
|
|---|
| 313 | .word OPENSSL_armcap_P-.
|
|---|
| 314 | #endif
|
|---|
| 315 | .asciz "GF(2^m) Multiplication for ARMv4/NEON, CRYPTOGAMS by <appro\@openssl.org>"
|
|---|
| 316 | .align 5
|
|---|
| 317 |
|
|---|
| 318 | #if __ARM_MAX_ARCH__>=7
|
|---|
| 319 | .comm OPENSSL_armcap_P,4,4
|
|---|
| 320 | #endif
|
|---|
| 321 | ___
|
|---|
| 322 |
|
|---|
| 323 | foreach (split("\n",$code)) {
|
|---|
| 324 | s/\`([^\`]*)\`/eval $1/geo;
|
|---|
| 325 |
|
|---|
| 326 | s/\bq([0-9]+)#(lo|hi)/sprintf "d%d",2*$1+($2 eq "hi")/geo or
|
|---|
| 327 | s/\bret\b/bx lr/go or
|
|---|
| 328 | s/\bbx\s+lr\b/.word\t0xe12fff1e/go; # make it possible to compile with -march=armv4
|
|---|
| 329 |
|
|---|
| 330 | print $_,"\n";
|
|---|
| 331 | }
|
|---|
| 332 | close STDOUT or die "error closing STDOUT: $!"; # enforce flush
|
|---|
