Hi Eric,
On 31 August 2018 at 10:01, Eric Biggers <ebiggers@xxxxxxxxxx> wrote:
> From: Eric Biggers <ebiggers@xxxxxxxxxx>
>
> Optimize ChaCha20 NEON performance by:
>
> - Implementing the 8-bit rotations using the 'vtbl.8' instruction.
> - Streamlining the part that adds the original state and XORs the data.
> - Making some other small tweaks.
>
> On ARM Cortex-A7, these optimizations improve ChaCha20 performance from
> about 11.9 cycles per byte to 11.3.
>
> There is a tradeoff involved with the 'vtbl.8' rotation method since
> there is at least one CPU where it's not fastest. But it seems to be a
> better default; see the added comment.
>
> Signed-off-by: Eric Biggers <ebiggers@xxxxxxxxxx>
> ---
> arch/arm/crypto/chacha20-neon-core.S | 289 ++++++++++++++-------------
> 1 file changed, 147 insertions(+), 142 deletions(-)
>
> diff --git a/arch/arm/crypto/chacha20-neon-core.S b/arch/arm/crypto/chacha20-neon-core.S
> index 3fecb2124c35a..d381cebaba31d 100644
> --- a/arch/arm/crypto/chacha20-neon-core.S
> +++ b/arch/arm/crypto/chacha20-neon-core.S
> @@ -18,6 +18,33 @@
> * (at your option) any later version.
> */
>
> + /*
> + * NEON doesn't have a rotate instruction. The alternatives are, more or less:
> + *
> + * (a) vshl.u32 + vsri.u32 (needs temporary register)
> + * (b) vshl.u32 + vshr.u32 + vorr (needs temporary register)
> + * (c) vrev32.16 (16-bit rotations only)
> + * (d) vtbl.8 + vtbl.8 (multiple of 8 bits rotations only,
> + * needs index vector)
> + *
> + * ChaCha20 has 16, 12, 8, and 7-bit rotations. For the 12 and 7-bit
> + * rotations, the only choices are (a) and (b). We use (a) since it takes
> + * two-thirds the cycles of (b) on both Cortex-A7 and Cortex-A53.
> + *
> + * For the 16-bit rotation, we use vrev32.16 since it's consistently fastest
> + * and doesn't need a temporary register.
> + *
> + * For the 8-bit rotation, we use vtbl.8 + vtbl.8. On Cortex-A7, this sequence
> + * is twice as fast as (a), even when doing (a) on multiple registers
> + * simultaneously to eliminate the stall between vshl and vsri. Also, it
> + * parallelizes better when temporary registers are scarce.
> + *
> + * A disadvantage is that on Cortex-A53, the vtbl sequence is the same speed as
> + * (a), so the need to load the rotation table actually makes the vtbl method
> + * slightly slower overall on that CPU. Still, it seems to be a good
> + * compromise to get a significant speed boost on some CPUs.
> + */
> +
Thanks for sharing these results. I have been working on 32-bit ARM
code under the assumption that the A53 pipeline more or less resembles
the A7 one, but this is obviously not the case looking at your
results. My contributions to arch/arm/crypto mainly involved Crypto
Extensions code, which the A7 does not support in the first place, so
it does not really matter, but I will keep this in mind going forward.
> #include <linux/linkage.h>
>
> .text
> @@ -46,6 +73,9 @@ ENTRY(chacha20_block_xor_neon)
> vmov q10, q2
> vmov q11, q3
>
> + ldr ip, =.Lrol8_table
> + vld1.8 {d10}, [ip, :64]
> +
I usually try to avoid the =literal ldr notation, because it involves
an additional load via the D-cache. Could you use a 64-bit literal
instead of a byte array and use vldr instead? Or switch to adr? (and
move the literal in range, I suppose)
> mov r3, #10
>
> .Ldoubleround:
> @@ -63,9 +93,9 @@ ENTRY(chacha20_block_xor_neon)
>
> // x0 += x1, x3 = rotl32(x3 ^ x0, 8)
> vadd.i32 q0, q0, q1
> - veor q4, q3, q0
> - vshl.u32 q3, q4, #8
> - vsri.u32 q3, q4, #24
> + veor q3, q3, q0
> + vtbl.8 d6, {d6}, d10
> + vtbl.8 d7, {d7}, d10
>
> // x2 += x3, x1 = rotl32(x1 ^ x2, 7)
> vadd.i32 q2, q2, q3
> @@ -94,9 +124,9 @@ ENTRY(chacha20_block_xor_neon)
>
> // x0 += x1, x3 = rotl32(x3 ^ x0, 8)
> vadd.i32 q0, q0, q1
> - veor q4, q3, q0
> - vshl.u32 q3, q4, #8
> - vsri.u32 q3, q4, #24
> + veor q3, q3, q0
> + vtbl.8 d6, {d6}, d10
> + vtbl.8 d7, {d7}, d10
>
> // x2 += x3, x1 = rotl32(x1 ^ x2, 7)
> vadd.i32 q2, q2, q3
> @@ -143,11 +173,11 @@ ENDPROC(chacha20_block_xor_neon)
>
> .align 5
> ENTRY(chacha20_4block_xor_neon)
> - push {r4-r6, lr}
> - mov ip, sp // preserve the stack pointer
> - sub r3, sp, #0x20 // allocate a 32 byte buffer
> - bic r3, r3, #0x1f // aligned to 32 bytes
> - mov sp, r3
> + push {r4}
The ARM EABI mandates 8 byte stack alignment, and if you take an
interrupt right at this point, you will enter the interrupt handler
with a misaligned stack. Whether this could actually cause any
problems is a different question, but it is better to keep it 8-byte
aligned to be sure.
I'd suggest you just push r4 and lr, so you can return from the
function by popping r4 and pc, as is customary on ARM.
> + mov r4, sp // preserve the stack pointer
> + sub ip, sp, #0x20 // allocate a 32 byte buffer
> + bic ip, ip, #0x1f // aligned to 32 bytes
> + mov sp, ip
>
Is there a reason for preferring ip over r3 for preserving the
original value of sp?
> // r0: Input state matrix, s
> // r1: 4 data blocks output, o
> @@ -157,25 +187,24 @@ ENTRY(chacha20_4block_xor_neon)
> // This function encrypts four consecutive ChaCha20 blocks by loading
> // the state matrix in NEON registers four times. The algorithm performs
> // each operation on the corresponding word of each state matrix, hence
> - // requires no word shuffling. For final XORing step we transpose the
> - // matrix by interleaving 32- and then 64-bit words, which allows us to
> - // do XOR in NEON registers.
> + // requires no word shuffling. The words are re-interleaved before the
> + // final addition of the original state and the XORing step.
> //
>
> - // x0..15[0-3] = s0..3[0..3]
> - add r3, r0, #0x20
> + // x0..15[0-3] = s0..15[0-3]
> + add ip, r0, #0x20
> vld1.32 {q0-q1}, [r0]
> - vld1.32 {q2-q3}, [r3]
> + vld1.32 {q2-q3}, [ip]
>
> - adr r3, CTRINC
> + adr ip, .Lctrinc1
> vdup.32 q15, d7[1]
> vdup.32 q14, d7[0]
> - vld1.32 {q11}, [r3, :128]
> + vld1.32 {q4}, [ip, :128]
> vdup.32 q13, d6[1]
> vdup.32 q12, d6[0]
> - vadd.i32 q12, q12, q11 // x12 += counter values 0-3
> vdup.32 q11, d5[1]
> vdup.32 q10, d5[0]
> + vadd.u32 q12, q12, q4 // x12 += counter values 0-3
> vdup.32 q9, d4[1]
> vdup.32 q8, d4[0]
> vdup.32 q7, d3[1]
> @@ -187,6 +216,7 @@ ENTRY(chacha20_4block_xor_neon)
> vdup.32 q1, d0[1]
> vdup.32 q0, d0[0]
>
> + adr ip, .Lrol8_table
> mov r3, #10
>
> .Ldoubleround4:
> @@ -238,24 +268,25 @@ ENTRY(chacha20_4block_xor_neon)
> // x1 += x5, x13 = rotl32(x13 ^ x1, 8)
> // x2 += x6, x14 = rotl32(x14 ^ x2, 8)
> // x3 += x7, x15 = rotl32(x15 ^ x3, 8)
> + vld1.8 {d16}, [ip, :64]
> vadd.i32 q0, q0, q4
> vadd.i32 q1, q1, q5
> vadd.i32 q2, q2, q6
> vadd.i32 q3, q3, q7
>
> - veor q8, q12, q0
> - veor q9, q13, q1
> - vshl.u32 q12, q8, #8
> - vshl.u32 q13, q9, #8
> - vsri.u32 q12, q8, #24
> - vsri.u32 q13, q9, #24
> + veor q12, q12, q0
> + veor q13, q13, q1
> + veor q14, q14, q2
> + veor q15, q15, q3
>
> - veor q8, q14, q2
> - veor q9, q15, q3
> - vshl.u32 q14, q8, #8
> - vshl.u32 q15, q9, #8
> - vsri.u32 q14, q8, #24
> - vsri.u32 q15, q9, #24
> + vtbl.8 d24, {d24}, d16
> + vtbl.8 d25, {d25}, d16
> + vtbl.8 d26, {d26}, d16
> + vtbl.8 d27, {d27}, d16
> + vtbl.8 d28, {d28}, d16
> + vtbl.8 d29, {d29}, d16
> + vtbl.8 d30, {d30}, d16
> + vtbl.8 d31, {d31}, d16
>
> vld1.32 {q8-q9}, [sp, :256]
>
> @@ -334,24 +365,25 @@ ENTRY(chacha20_4block_xor_neon)
> // x1 += x6, x12 = rotl32(x12 ^ x1, 8)
> // x2 += x7, x13 = rotl32(x13 ^ x2, 8)
> // x3 += x4, x14 = rotl32(x14 ^ x3, 8)
> + vld1.8 {d16}, [ip, :64]
> vadd.i32 q0, q0, q5
> vadd.i32 q1, q1, q6
> vadd.i32 q2, q2, q7
> vadd.i32 q3, q3, q4
>
> - veor q8, q15, q0
> - veor q9, q12, q1
> - vshl.u32 q15, q8, #8
> - vshl.u32 q12, q9, #8
> - vsri.u32 q15, q8, #24
> - vsri.u32 q12, q9, #24
> + veor q15, q15, q0
> + veor q12, q12, q1
> + veor q13, q13, q2
> + veor q14, q14, q3
>
> - veor q8, q13, q2
> - veor q9, q14, q3
> - vshl.u32 q13, q8, #8
> - vshl.u32 q14, q9, #8
> - vsri.u32 q13, q8, #24
> - vsri.u32 q14, q9, #24
> + vtbl.8 d30, {d30}, d16
> + vtbl.8 d31, {d31}, d16
> + vtbl.8 d24, {d24}, d16
> + vtbl.8 d25, {d25}, d16
> + vtbl.8 d26, {d26}, d16
> + vtbl.8 d27, {d27}, d16
> + vtbl.8 d28, {d28}, d16
> + vtbl.8 d29, {d29}, d16
>
> vld1.32 {q8-q9}, [sp, :256]
>
> @@ -381,104 +413,74 @@ ENTRY(chacha20_4block_xor_neon)
> vsri.u32 q6, q9, #25
>
> subs r3, r3, #1
> - beq 0f
> -
> - vld1.32 {q8-q9}, [sp, :256]
> - b .Ldoubleround4
> -
> - // x0[0-3] += s0[0]
> - // x1[0-3] += s0[1]
> - // x2[0-3] += s0[2]
> - // x3[0-3] += s0[3]
> -0: ldmia r0!, {r3-r6}
> - vdup.32 q8, r3
> - vdup.32 q9, r4
> - vadd.i32 q0, q0, q8
> - vadd.i32 q1, q1, q9
> - vdup.32 q8, r5
> - vdup.32 q9, r6
> - vadd.i32 q2, q2, q8
> - vadd.i32 q3, q3, q9
> -
> - // x4[0-3] += s1[0]
> - // x5[0-3] += s1[1]
> - // x6[0-3] += s1[2]
> - // x7[0-3] += s1[3]
> - ldmia r0!, {r3-r6}
> - vdup.32 q8, r3
> - vdup.32 q9, r4
> - vadd.i32 q4, q4, q8
> - vadd.i32 q5, q5, q9
> - vdup.32 q8, r5
> - vdup.32 q9, r6
> - vadd.i32 q6, q6, q8
> - vadd.i32 q7, q7, q9
> -
> - // interleave 32-bit words in state n, n+1
> - vzip.32 q0, q1
> - vzip.32 q2, q3
> - vzip.32 q4, q5
> - vzip.32 q6, q7
> -
> - // interleave 64-bit words in state n, n+2
> - vswp d1, d4
> - vswp d3, d6
> - vswp d9, d12
> - vswp d11, d14
> -
> - // xor with corresponding input, write to output
> - vld1.8 {q8-q9}, [r2]!
> - veor q8, q8, q0
> - veor q9, q9, q4
> - vst1.8 {q8-q9}, [r1]!
> -
> vld1.32 {q8-q9}, [sp, :256]
> -
> - // x8[0-3] += s2[0]
> - // x9[0-3] += s2[1]
> - // x10[0-3] += s2[2]
> - // x11[0-3] += s2[3]
> - ldmia r0!, {r3-r6}
> - vdup.32 q0, r3
> - vdup.32 q4, r4
> - vadd.i32 q8, q8, q0
> - vadd.i32 q9, q9, q4
> - vdup.32 q0, r5
> - vdup.32 q4, r6
> - vadd.i32 q10, q10, q0
> - vadd.i32 q11, q11, q4
> -
> - // x12[0-3] += s3[0]
> - // x13[0-3] += s3[1]
> - // x14[0-3] += s3[2]
> - // x15[0-3] += s3[3]
> - ldmia r0!, {r3-r6}
> - vdup.32 q0, r3
> - vdup.32 q4, r4
> - adr r3, CTRINC
> - vadd.i32 q12, q12, q0
> - vld1.32 {q0}, [r3, :128]
> - vadd.i32 q13, q13, q4
> - vadd.i32 q12, q12, q0 // x12 += counter values 0-3
> -
> - vdup.32 q0, r5
> - vdup.32 q4, r6
> - vadd.i32 q14, q14, q0
> - vadd.i32 q15, q15, q4
> -
> - // interleave 32-bit words in state n, n+1
> - vzip.32 q8, q9
> - vzip.32 q10, q11
> - vzip.32 q12, q13
> - vzip.32 q14, q15
> -
> - // interleave 64-bit words in state n, n+2
> - vswp d17, d20
> - vswp d19, d22
> - vswp d25, d28
> + bne .Ldoubleround4
> +
> + // re-interleave the 32-bit words of the four blocks
> + vzip.32 q14, q15 // => (14 15 14 15) (14 15 14 15)
> + vzip.32 q12, q13 // => (12 13 12 13) (12 13 12 13)
> + vzip.32 q10, q11 // => (10 11 10 11) (10 11 10 11)
> + vzip.32 q8, q9 // => (8 9 8 9) (8 9 8 9)
> + vzip.32 q6, q7 // => (6 7 6 7) (6 7 6 7)
> + vzip.32 q4, q5 // => (4 5 4 5) (4 5 4 5)
> + vzip.32 q2, q3 // => (2 3 2 3) (2 3 2 3)
> + vzip.32 q0, q1 // => (0 1 0 1) (0 1 0 1)
> vswp d27, d30
> + vswp d25, d28
> + vswp d19, d22
> + vswp d17, d20
> + vswp d11, d14
> + vst1.32 {q14-q15}, [sp, :256] // free up two registers
> + vswp d9, d12
> + vswp d3, d6
> + vld1.32 {q14-q15}, [r0]! // load s0..7
> + vswp d1, d4
>
> - vmov q4, q1
> + // Swap q1 and q4 so that we'll free up consecutive registers (q0-q1)
> + // after XORing the first 32 bytes.
> + vswp q1, q4
> +
> + // blocks are: (q0 q1 q8 q12) (q2 q6 q10 q14) (q4 q5 q9 q13) (q3 q7 q11 q15)
> +
> + // x0..3[0-3] += s0..3[0-3] (add orig state to 1st row of each block)
> + vadd.u32 q0, q0, q14
> + vadd.u32 q2, q2, q14
> + vadd.u32 q4, q4, q14
> + vadd.u32 q3, q3, q14
> +
> + // x4..7[0-3] += s4..7[0-3] (add orig state to 2nd row of each block)
> + vadd.u32 q1, q1, q15
> + vadd.u32 q6, q6, q15
> + vadd.u32 q5, q5, q15
> + vadd.u32 q7, q7, q15
> +
> + // XOR first 32 bytes using keystream from first two rows of first block
> + vld1.8 {q14-q15}, [r2]!
> + veor q14, q14, q0
> + veor q15, q15, q1
> + vld1.32 {q0-q1}, [r0] // load s8..s15
> + vst1.8 {q14-q15}, [r1]!
> +
> + // x8..11[0-3] += s8..11[0-3] (add orig state to 3rd row of each block)
> + vadd.u32 q8, q8, q0
> + vadd.u32 q10, q10, q0
> + vld1.32 {q14-q15}, [sp, :256]
> + vadd.u32 q9, q9, q0
> + adr ip, .Lctrinc2
> + vadd.u32 q11, q11, q0
> +
> + // x12..15[0-3] += s12..15[0-3] (add orig state to 4th row of each block)
> + vld1.32 {q0}, [ip, :128] // load (1, 0, 2, 0)
Would something like
vmov.i32 d0, #1
vmovl.u32 q0, d0
vadd.u64 d1, d1
(untested) work as well?
> + vadd.u32 q15, q15, q1
> + vadd.u32 q13, q13, q1
> + vadd.u32 q14, q14, q1
> + vadd.u32 q12, q12, q1
> + vadd.u32 d30, d30, d1 // x12[3] += 2
> + vadd.u32 d26, d26, d1 // x12[2] += 2
> + vadd.u32 d28, d28, d0 // x12[1] += 1
> + vadd.u32 d30, d30, d0 // x12[3] += 1
> +
> + // XOR the rest of the data with the keystream
>
> vld1.8 {q0-q1}, [r2]!
> veor q0, q0, q8
> @@ -511,13 +513,16 @@ ENTRY(chacha20_4block_xor_neon)
> vst1.8 {q0-q1}, [r1]!
>
> vld1.8 {q0-q1}, [r2]
> + mov sp, r4 // restore original stack pointer
> veor q0, q0, q11
> veor q1, q1, q15
> vst1.8 {q0-q1}, [r1]
>
> - mov sp, ip
> - pop {r4-r6, pc}
> + pop {r4}
> + bx lr
> ENDPROC(chacha20_4block_xor_neon)
>
> .align 4
> -CTRINC: .word 0, 1, 2, 3
> +.Lctrinc1: .word 0, 1, 2, 3
> +.Lctrinc2: .word 1, 0, 2, 0
> +.Lrol8_table: .byte 3, 0, 1, 2, 7, 4, 5, 6
> --
> 2.18.0
>
