2d225cf6d895c76bb781cddc221f513c70ca2b19
[openssl.git] / crypto / modes / asm / ghash-armv4.pl
1 #!/usr/bin/env perl
2 #
3 # ====================================================================
4 # Written by Andy Polyakov <appro@openssl.org> 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 # April 2010
11 #
12 # The module implements "4-bit" GCM GHASH function and underlying
13 # single multiplication operation in GF(2^128). "4-bit" means that it
14 # uses 256 bytes per-key table [+32 bytes shared table]. There is no
15 # experimental performance data available yet. The only approximation
16 # that can be made at this point is based on code size. Inner loop is
17 # 32 instructions long and on single-issue core should execute in <40
18 # cycles. Having verified that gcc 3.4 didn't unroll corresponding
19 # loop, this assembler loop body was found to be ~3x smaller than
20 # compiler-generated one...
21 #
22 # July 2010
23 #
24 # Rescheduling for dual-issue pipeline resulted in 8.5% improvement on
25 # Cortex A8 core and ~25 cycles per processed byte (which was observed
26 # to be ~3 times faster than gcc-generated code:-)
27 #
28 # February 2011
29 #
30 # Profiler-assisted and platform-specific optimization resulted in 7%
31 # improvement on Cortex A8 core and ~23.5 cycles per byte.
32 #
33 # March 2011
34 #
35 # Add NEON implementation featuring polynomial multiplication, i.e. no
36 # lookup tables involved. On Cortex A8 it was measured to process one
37 # byte in 15 cycles or 55% faster than integer-only code.
38 #
39 # April 2014
40 #
41 # Switch to multiplication algorithm suggested in paper referred
42 # below and combine it with reduction algorithm from x86 module.
43 # Performance improvement over previous version varies from 65% on
44 # Snapdragon S4 to 110% on Cortex A9. In absolute terms Cortex A8
45 # processes one byte in 8.45 cycles, A9 - in 10.2, A15 - in 7.63,
46 # Snapdragon S4 - in 9.33.
47 #
48 # Câmara, D.; Gouvêa, C. P. L.; López, J. & Dahab, R.: Fast Software
49 # Polynomial Multiplication on ARM Processors using the NEON Engine.
50
51 # http://conradoplg.cryptoland.net/files/2010/12/mocrysen13.pdf
52
53 # ====================================================================
54 # Note about "528B" variant. In ARM case it makes lesser sense to
55 # implement it for following reasons:
56 #
57 # - performance improvement won't be anywhere near 50%, because 128-
58 #   bit shift operation is neatly fused with 128-bit xor here, and
59 #   "538B" variant would eliminate only 4-5 instructions out of 32
60 #   in the inner loop (meaning that estimated improvement is ~15%);
61 # - ARM-based systems are often embedded ones and extra memory
62 #   consumption might be unappreciated (for so little improvement);
63 #
64 # Byte order [in]dependence. =========================================
65 #
66 # Caller is expected to maintain specific *dword* order in Htable,
67 # namely with *least* significant dword of 128-bit value at *lower*
68 # address. This differs completely from C code and has everything to
69 # do with ldm instruction and order in which dwords are "consumed" by
70 # algorithm. *Byte* order within these dwords in turn is whatever
71 # *native* byte order on current platform. See gcm128.c for working
72 # example...
73
74 $flavour = shift;
75 if ($flavour=~/^\w[\w\-]*\.\w+$/) { $output=$flavour; undef $flavour; }
76 else { while (($output=shift) && ($output!~/^\w[\w\-]*\.\w+$/)) {} }
77
78 if ($flavour && $flavour ne "void") {
79     $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
80     ( $xlate="${dir}arm-xlate.pl" and -f $xlate ) or
81     ( $xlate="${dir}../../perlasm/arm-xlate.pl" and -f $xlate) or
82     die "can't locate arm-xlate.pl";
83
84     open STDOUT,"| \"$^X\" $xlate $flavour $output";
85 } else {
86     open STDOUT,">$output";
87 }
88
89 $Xi="r0";       # argument block
90 $Htbl="r1";
91 $inp="r2";
92 $len="r3";
93
94 $Zll="r4";      # variables
95 $Zlh="r5";
96 $Zhl="r6";
97 $Zhh="r7";
98 $Tll="r8";
99 $Tlh="r9";
100 $Thl="r10";
101 $Thh="r11";
102 $nlo="r12";
103 ################# r13 is stack pointer
104 $nhi="r14";
105 ################# r15 is program counter
106
107 $rem_4bit=$inp; # used in gcm_gmult_4bit
108 $cnt=$len;
109
110 sub Zsmash() {
111   my $i=12;
112   my @args=@_;
113   for ($Zll,$Zlh,$Zhl,$Zhh) {
114     $code.=<<___;
115 #if __ARM_ARCH__>=7 && defined(__ARMEL__)
116         rev     $_,$_
117         str     $_,[$Xi,#$i]
118 #elif defined(__ARMEB__)
119         str     $_,[$Xi,#$i]
120 #else
121         mov     $Tlh,$_,lsr#8
122         strb    $_,[$Xi,#$i+3]
123         mov     $Thl,$_,lsr#16
124         strb    $Tlh,[$Xi,#$i+2]
125         mov     $Thh,$_,lsr#24
126         strb    $Thl,[$Xi,#$i+1]
127         strb    $Thh,[$Xi,#$i]
128 #endif
129 ___
130     $code.="\t".shift(@args)."\n";
131     $i-=4;
132   }
133 }
134
135 $code=<<___;
136 #include "arm_arch.h"
137
138 .text
139 .code   32
140
141 #ifdef  __APPLE__
142 #define ldrplb  ldrbpl
143 #define ldrneb  ldrbne
144 #endif
145
146 .type   rem_4bit,%object
147 .align  5
148 rem_4bit:
149 .short  0x0000,0x1C20,0x3840,0x2460
150 .short  0x7080,0x6CA0,0x48C0,0x54E0
151 .short  0xE100,0xFD20,0xD940,0xC560
152 .short  0x9180,0x8DA0,0xA9C0,0xB5E0
153 .size   rem_4bit,.-rem_4bit
154
155 .type   rem_4bit_get,%function
156 rem_4bit_get:
157         sub     $rem_4bit,pc,#8
158         sub     $rem_4bit,$rem_4bit,#32 @ &rem_4bit
159         b       .Lrem_4bit_got
160         nop
161 .size   rem_4bit_get,.-rem_4bit_get
162
163 .global gcm_ghash_4bit
164 .type   gcm_ghash_4bit,%function
165 gcm_ghash_4bit:
166         sub     r12,pc,#8
167         add     $len,$inp,$len          @ $len to point at the end
168         stmdb   sp!,{r3-r11,lr}         @ save $len/end too
169         sub     r12,r12,#48             @ &rem_4bit
170
171         ldmia   r12,{r4-r11}            @ copy rem_4bit ...
172         stmdb   sp!,{r4-r11}            @ ... to stack
173
174         ldrb    $nlo,[$inp,#15]
175         ldrb    $nhi,[$Xi,#15]
176 .Louter:
177         eor     $nlo,$nlo,$nhi
178         and     $nhi,$nlo,#0xf0
179         and     $nlo,$nlo,#0x0f
180         mov     $cnt,#14
181
182         add     $Zhh,$Htbl,$nlo,lsl#4
183         ldmia   $Zhh,{$Zll-$Zhh}        @ load Htbl[nlo]
184         add     $Thh,$Htbl,$nhi
185         ldrb    $nlo,[$inp,#14]
186
187         and     $nhi,$Zll,#0xf          @ rem
188         ldmia   $Thh,{$Tll-$Thh}        @ load Htbl[nhi]
189         add     $nhi,$nhi,$nhi
190         eor     $Zll,$Tll,$Zll,lsr#4
191         ldrh    $Tll,[sp,$nhi]          @ rem_4bit[rem]
192         eor     $Zll,$Zll,$Zlh,lsl#28
193         ldrb    $nhi,[$Xi,#14]
194         eor     $Zlh,$Tlh,$Zlh,lsr#4
195         eor     $Zlh,$Zlh,$Zhl,lsl#28
196         eor     $Zhl,$Thl,$Zhl,lsr#4
197         eor     $Zhl,$Zhl,$Zhh,lsl#28
198         eor     $Zhh,$Thh,$Zhh,lsr#4
199         eor     $nlo,$nlo,$nhi
200         and     $nhi,$nlo,#0xf0
201         and     $nlo,$nlo,#0x0f
202         eor     $Zhh,$Zhh,$Tll,lsl#16
203
204 .Linner:
205         add     $Thh,$Htbl,$nlo,lsl#4
206         and     $nlo,$Zll,#0xf          @ rem
207         subs    $cnt,$cnt,#1
208         add     $nlo,$nlo,$nlo
209         ldmia   $Thh,{$Tll-$Thh}        @ load Htbl[nlo]
210         eor     $Zll,$Tll,$Zll,lsr#4
211         eor     $Zll,$Zll,$Zlh,lsl#28
212         eor     $Zlh,$Tlh,$Zlh,lsr#4
213         eor     $Zlh,$Zlh,$Zhl,lsl#28
214         ldrh    $Tll,[sp,$nlo]          @ rem_4bit[rem]
215         eor     $Zhl,$Thl,$Zhl,lsr#4
216         ldrplb  $nlo,[$inp,$cnt]
217         eor     $Zhl,$Zhl,$Zhh,lsl#28
218         eor     $Zhh,$Thh,$Zhh,lsr#4
219
220         add     $Thh,$Htbl,$nhi
221         and     $nhi,$Zll,#0xf          @ rem
222         eor     $Zhh,$Zhh,$Tll,lsl#16   @ ^= rem_4bit[rem]
223         add     $nhi,$nhi,$nhi
224         ldmia   $Thh,{$Tll-$Thh}        @ load Htbl[nhi]
225         eor     $Zll,$Tll,$Zll,lsr#4
226         ldrplb  $Tll,[$Xi,$cnt]
227         eor     $Zll,$Zll,$Zlh,lsl#28
228         eor     $Zlh,$Tlh,$Zlh,lsr#4
229         ldrh    $Tlh,[sp,$nhi]
230         eor     $Zlh,$Zlh,$Zhl,lsl#28
231         eor     $Zhl,$Thl,$Zhl,lsr#4
232         eor     $Zhl,$Zhl,$Zhh,lsl#28
233         eorpl   $nlo,$nlo,$Tll
234         eor     $Zhh,$Thh,$Zhh,lsr#4
235         andpl   $nhi,$nlo,#0xf0
236         andpl   $nlo,$nlo,#0x0f
237         eor     $Zhh,$Zhh,$Tlh,lsl#16   @ ^= rem_4bit[rem]
238         bpl     .Linner
239
240         ldr     $len,[sp,#32]           @ re-load $len/end
241         add     $inp,$inp,#16
242         mov     $nhi,$Zll
243 ___
244         &Zsmash("cmp\t$inp,$len","ldrneb\t$nlo,[$inp,#15]");
245 $code.=<<___;
246         bne     .Louter
247
248         add     sp,sp,#36
249 #if __ARM_ARCH__>=5
250         ldmia   sp!,{r4-r11,pc}
251 #else
252         ldmia   sp!,{r4-r11,lr}
253         tst     lr,#1
254         moveq   pc,lr                   @ be binary compatible with V4, yet
255         bx      lr                      @ interoperable with Thumb ISA:-)
256 #endif
257 .size   gcm_ghash_4bit,.-gcm_ghash_4bit
258
259 .global gcm_gmult_4bit
260 .type   gcm_gmult_4bit,%function
261 gcm_gmult_4bit:
262         stmdb   sp!,{r4-r11,lr}
263         ldrb    $nlo,[$Xi,#15]
264         b       rem_4bit_get
265 .Lrem_4bit_got:
266         and     $nhi,$nlo,#0xf0
267         and     $nlo,$nlo,#0x0f
268         mov     $cnt,#14
269
270         add     $Zhh,$Htbl,$nlo,lsl#4
271         ldmia   $Zhh,{$Zll-$Zhh}        @ load Htbl[nlo]
272         ldrb    $nlo,[$Xi,#14]
273
274         add     $Thh,$Htbl,$nhi
275         and     $nhi,$Zll,#0xf          @ rem
276         ldmia   $Thh,{$Tll-$Thh}        @ load Htbl[nhi]
277         add     $nhi,$nhi,$nhi
278         eor     $Zll,$Tll,$Zll,lsr#4
279         ldrh    $Tll,[$rem_4bit,$nhi]   @ rem_4bit[rem]
280         eor     $Zll,$Zll,$Zlh,lsl#28
281         eor     $Zlh,$Tlh,$Zlh,lsr#4
282         eor     $Zlh,$Zlh,$Zhl,lsl#28
283         eor     $Zhl,$Thl,$Zhl,lsr#4
284         eor     $Zhl,$Zhl,$Zhh,lsl#28
285         eor     $Zhh,$Thh,$Zhh,lsr#4
286         and     $nhi,$nlo,#0xf0
287         eor     $Zhh,$Zhh,$Tll,lsl#16
288         and     $nlo,$nlo,#0x0f
289
290 .Loop:
291         add     $Thh,$Htbl,$nlo,lsl#4
292         and     $nlo,$Zll,#0xf          @ rem
293         subs    $cnt,$cnt,#1
294         add     $nlo,$nlo,$nlo
295         ldmia   $Thh,{$Tll-$Thh}        @ load Htbl[nlo]
296         eor     $Zll,$Tll,$Zll,lsr#4
297         eor     $Zll,$Zll,$Zlh,lsl#28
298         eor     $Zlh,$Tlh,$Zlh,lsr#4
299         eor     $Zlh,$Zlh,$Zhl,lsl#28
300         ldrh    $Tll,[$rem_4bit,$nlo]   @ rem_4bit[rem]
301         eor     $Zhl,$Thl,$Zhl,lsr#4
302         ldrplb  $nlo,[$Xi,$cnt]
303         eor     $Zhl,$Zhl,$Zhh,lsl#28
304         eor     $Zhh,$Thh,$Zhh,lsr#4
305
306         add     $Thh,$Htbl,$nhi
307         and     $nhi,$Zll,#0xf          @ rem
308         eor     $Zhh,$Zhh,$Tll,lsl#16   @ ^= rem_4bit[rem]
309         add     $nhi,$nhi,$nhi
310         ldmia   $Thh,{$Tll-$Thh}        @ load Htbl[nhi]
311         eor     $Zll,$Tll,$Zll,lsr#4
312         eor     $Zll,$Zll,$Zlh,lsl#28
313         eor     $Zlh,$Tlh,$Zlh,lsr#4
314         ldrh    $Tll,[$rem_4bit,$nhi]   @ rem_4bit[rem]
315         eor     $Zlh,$Zlh,$Zhl,lsl#28
316         eor     $Zhl,$Thl,$Zhl,lsr#4
317         eor     $Zhl,$Zhl,$Zhh,lsl#28
318         eor     $Zhh,$Thh,$Zhh,lsr#4
319         andpl   $nhi,$nlo,#0xf0
320         andpl   $nlo,$nlo,#0x0f
321         eor     $Zhh,$Zhh,$Tll,lsl#16   @ ^= rem_4bit[rem]
322         bpl     .Loop
323 ___
324         &Zsmash();
325 $code.=<<___;
326 #if __ARM_ARCH__>=5
327         ldmia   sp!,{r4-r11,pc}
328 #else
329         ldmia   sp!,{r4-r11,lr}
330         tst     lr,#1
331         moveq   pc,lr                   @ be binary compatible with V4, yet
332         bx      lr                      @ interoperable with Thumb ISA:-)
333 #endif
334 .size   gcm_gmult_4bit,.-gcm_gmult_4bit
335 ___
336 {
337 my ($Xl,$Xm,$Xh,$IN)=map("q$_",(0..3));
338 my ($t0,$t1,$t2,$t3)=map("q$_",(8..12));
339 my ($Hlo,$Hhi,$Hhl,$k48,$k32,$k16)=map("d$_",(26..31));
340
341 sub clmul64x64 {
342 my ($r,$a,$b)=@_;
343 $code.=<<___;
344         vext.8          $t0#lo, $a, $a, #1      @ A1
345         vmull.p8        $t0, $t0#lo, $b         @ F = A1*B
346         vext.8          $r#lo, $b, $b, #1       @ B1
347         vmull.p8        $r, $a, $r#lo           @ E = A*B1
348         vext.8          $t1#lo, $a, $a, #2      @ A2
349         vmull.p8        $t1, $t1#lo, $b         @ H = A2*B
350         vext.8          $t3#lo, $b, $b, #2      @ B2
351         vmull.p8        $t3, $a, $t3#lo         @ G = A*B2
352         vext.8          $t2#lo, $a, $a, #3      @ A3
353         veor            $t0, $t0, $r            @ L = E + F
354         vmull.p8        $t2, $t2#lo, $b         @ J = A3*B
355         vext.8          $r#lo, $b, $b, #3       @ B3
356         veor            $t1, $t1, $t3           @ M = G + H
357         vmull.p8        $r, $a, $r#lo           @ I = A*B3
358         veor            $t0#lo, $t0#lo, $t0#hi  @ t0 = (L) (P0 + P1) << 8
359         vand            $t0#hi, $t0#hi, $k48
360         vext.8          $t3#lo, $b, $b, #4      @ B4
361         veor            $t1#lo, $t1#lo, $t1#hi  @ t1 = (M) (P2 + P3) << 16
362         vand            $t1#hi, $t1#hi, $k32
363         vmull.p8        $t3, $a, $t3#lo         @ K = A*B4
364         veor            $t2, $t2, $r            @ N = I + J
365         veor            $t0#lo, $t0#lo, $t0#hi
366         veor            $t1#lo, $t1#lo, $t1#hi
367         veor            $t2#lo, $t2#lo, $t2#hi  @ t2 = (N) (P4 + P5) << 24
368         vand            $t2#hi, $t2#hi, $k16
369         vext.8          $t0, $t0, $t0, #15
370         veor            $t3#lo, $t3#lo, $t3#hi  @ t3 = (K) (P6 + P7) << 32
371         vmov.i64        $t3#hi, #0
372         vext.8          $t1, $t1, $t1, #14
373         veor            $t2#lo, $t2#lo, $t2#hi
374         vmull.p8        $r, $a, $b              @ D = A*B
375         vext.8          $t3, $t3, $t3, #12
376         vext.8          $t2, $t2, $t2, #13
377         veor            $t0, $t0, $t1
378         veor            $t2, $t2, $t3
379         veor            $r, $r, $t0
380         veor            $r, $r, $t2
381 ___
382 }
383
384 $code.=<<___;
385 #if __ARM_MAX_ARCH__>=7
386 .arch   armv7-a
387 .fpu    neon
388
389 .global gcm_init_neon
390 .type   gcm_init_neon,%function
391 .align  4
392 gcm_init_neon:
393         vld1.64         $IN#hi,[r1]!            @ load H
394         vmov.i8         $t0,#0xe1
395         vld1.64         $IN#lo,[r1]
396         vshl.i64        $t0#hi,#57
397         vshr.u64        $t0#lo,#63              @ t0=0xc2....01
398         vdup.8          $t1,$IN#hi[7]
399         vshr.u64        $Hlo,$IN#lo,#63
400         vshr.s8         $t1,#7                  @ broadcast carry bit
401         vshl.i64        $IN,$IN,#1
402         vand            $t0,$t0,$t1
403         vorr            $IN#hi,$Hlo             @ H<<<=1
404         veor            $IN,$IN,$t0             @ twisted H
405         vstmia          r0,{$IN}
406
407         ret                                     @ bx lr
408 .size   gcm_init_neon,.-gcm_init_neon
409
410 .global gcm_gmult_neon
411 .type   gcm_gmult_neon,%function
412 .align  4
413 gcm_gmult_neon:
414         vld1.64         $IN#hi,[$Xi]!           @ load Xi
415         vld1.64         $IN#lo,[$Xi]!
416         vmov.i64        $k48,#0x0000ffffffffffff
417         vldmia          $Htbl,{$Hlo-$Hhi}       @ load twisted H
418         vmov.i64        $k32,#0x00000000ffffffff
419 #ifdef __ARMEL__
420         vrev64.8        $IN,$IN
421 #endif
422         vmov.i64        $k16,#0x000000000000ffff
423         veor            $Hhl,$Hlo,$Hhi          @ Karatsuba pre-processing
424         mov             $len,#16
425         b               .Lgmult_neon
426 .size   gcm_gmult_neon,.-gcm_gmult_neon
427
428 .global gcm_ghash_neon
429 .type   gcm_ghash_neon,%function
430 .align  4
431 gcm_ghash_neon:
432         vld1.64         $Xl#hi,[$Xi]!           @ load Xi
433         vld1.64         $Xl#lo,[$Xi]!
434         vmov.i64        $k48,#0x0000ffffffffffff
435         vldmia          $Htbl,{$Hlo-$Hhi}       @ load twisted H
436         vmov.i64        $k32,#0x00000000ffffffff
437 #ifdef __ARMEL__
438         vrev64.8        $Xl,$Xl
439 #endif
440         vmov.i64        $k16,#0x000000000000ffff
441         veor            $Hhl,$Hlo,$Hhi          @ Karatsuba pre-processing
442
443 .Loop_neon:
444         vld1.64         $IN#hi,[$inp]!          @ load inp
445         vld1.64         $IN#lo,[$inp]!
446 #ifdef __ARMEL__
447         vrev64.8        $IN,$IN
448 #endif
449         veor            $IN,$Xl                 @ inp^=Xi
450 .Lgmult_neon:
451 ___
452         &clmul64x64     ($Xl,$Hlo,"$IN#lo");    # H.lo·Xi.lo
453 $code.=<<___;
454         veor            $IN#lo,$IN#lo,$IN#hi    @ Karatsuba pre-processing
455 ___
456         &clmul64x64     ($Xm,$Hhl,"$IN#lo");    # (H.lo+H.hi)·(Xi.lo+Xi.hi)
457         &clmul64x64     ($Xh,$Hhi,"$IN#hi");    # H.hi·Xi.hi
458 $code.=<<___;
459         veor            $Xm,$Xm,$Xl             @ Karatsuba post-processing
460         veor            $Xm,$Xm,$Xh
461         veor            $Xl#hi,$Xl#hi,$Xm#lo
462         veor            $Xh#lo,$Xh#lo,$Xm#hi    @ Xh|Xl - 256-bit result
463
464         @ equivalent of reduction_avx from ghash-x86_64.pl
465         vshl.i64        $t1,$Xl,#57             @ 1st phase
466         vshl.i64        $t2,$Xl,#62
467         veor            $t2,$t2,$t1             @
468         vshl.i64        $t1,$Xl,#63
469         veor            $t2, $t2, $t1           @
470         veor            $Xl#hi,$Xl#hi,$t2#lo    @
471         veor            $Xh#lo,$Xh#lo,$t2#hi
472
473         vshr.u64        $t2,$Xl,#1              @ 2nd phase
474         veor            $Xh,$Xh,$Xl
475         veor            $Xl,$Xl,$t2             @
476         vshr.u64        $t2,$t2,#6
477         vshr.u64        $Xl,$Xl,#1              @
478         veor            $Xl,$Xl,$Xh             @
479         veor            $Xl,$Xl,$t2             @
480
481         subs            $len,#16
482         bne             .Loop_neon
483
484 #ifdef __ARMEL__
485         vrev64.8        $Xl,$Xl
486 #endif
487         sub             $Xi,#16 
488         vst1.64         $Xl#hi,[$Xi]!           @ write out Xi
489         vst1.64         $Xl#lo,[$Xi]
490
491         ret                                     @ bx lr
492 .size   gcm_ghash_neon,.-gcm_ghash_neon
493 #endif
494 ___
495 }
496 $code.=<<___;
497 .asciz  "GHASH for ARMv4/NEON, CRYPTOGAMS by <appro\@openssl.org>"
498 .align  2
499 ___
500
501 foreach (split("\n",$code)) {
502         s/\`([^\`]*)\`/eval $1/geo;
503
504         s/\bq([0-9]+)#(lo|hi)/sprintf "d%d",2*$1+($2 eq "hi")/geo       or
505         s/\bret\b/bx    lr/go           or
506         s/\bbx\s+lr\b/.word\t0xe12fff1e/go;    # make it possible to compile with -march=armv4
507
508         print $_,"\n";
509 }
510 close STDOUT; # enforce flush