Re: [PATCH] crypto: arm/chacha20 - faster 8-bit rotations and other optimizations

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On 31 August 2018 at 17:56, Ard Biesheuvel <ard.biesheuvel@xxxxxxxxxx> wrote:
> 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]

Also, would it perhaps be more efficient to keep the rotation vector
in a pair of GPRs, and use something like

vmov d16, r4, r5

here?


>>         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
>>



[Index of Archives]     [Kernel]     [Gnu Classpath]     [Gnu Crypto]     [DM Crypt]     [Netfilter]     [Bugtraq]

  Powered by Linux