This git patch adds x86_64 AVX2 optimization of SHA1 transform to crypto support. The patch has been tested with 3.14.0-rc1 kernel. On a Haswell desktop, with turbo disabled and all cpus running at maximum frequency, tcrypt shows AVX2 performance improvement from 3% for 256 bytes update to 16% for 1024 bytes update over AVX implementation. Signed-off-by: Chandramouli Narayanan <mouli@xxxxxxxxxxxxxxx> diff --git a/arch/x86/crypto/sha1_avx2_x86_64_asm.S b/arch/x86/crypto/sha1_avx2_x86_64_asm.S new file mode 100644 index 0000000..2f71294 --- /dev/null +++ b/arch/x86/crypto/sha1_avx2_x86_64_asm.S @@ -0,0 +1,732 @@ +/* + Implement fast SHA-1 with AVX2 instructions. (x86_64) + + This file is provided under a dual BSD/GPLv2 license. When using or + redistributing this file, you may do so under either license. + + GPL LICENSE SUMMARY + + Copyright(c) 2014 Intel Corporation. + + This program is free software; you can redistribute it and/or modify + it under the terms of version 2 of the GNU General Public License as + published by the Free Software Foundation. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + Contact Information: + Ilya Albrekht <ilya.albrekht@xxxxxxxxx> + Maxim Locktyukhin <maxim.locktyukhin@xxxxxxxxx> + Ronen Zohar <ronen.zohar@xxxxxxxxx> + Chandramouli Narayanan <mouli@xxxxxxxxxxxxxxx> + + BSD LICENSE + + Copyright(c) 2014 Intel Corporation. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in + the documentation and/or other materials provided with the + distribution. + * Neither the name of Intel Corporation nor the names of its + contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*/ + +#--------------------- +# +#SHA-1 implementation with Intel(R) AVX2 instruction set extensions. +# +#This implementation is based on the previous SSSE3 release: +#Visit http://software.intel.com/en-us/articles/ +#and refer to improving-the-performance-of-the-secure-hash-algorithm-1/ +# +#Updates 20-byte SHA-1 record in 'hash' for even number of +#'num_blocks' consecutive 64-byte blocks +# +#extern "C" void sha1_transform_avx2( +# int *hash, const char* input, size_t num_blocks ); +# + +#ifdef CONFIG_AS_AVX2 +#include <linux/linkage.h> + +#define CTX %rdi /* arg1 */ +#define BUF %rsi /* arg2 */ +#define CNT %rdx /* arg3 */ + +#define REG_A %ecx +#define REG_B %esi +#define REG_C %edi +#define REG_D %eax +#define REG_E %edx +#define REG_TB %ebx +#define REG_TA %r12d +#define REG_RA %rcx +#define REG_RB %rsi +#define REG_RC %rdi +#define REG_RD %rax +#define REG_RE %rdx +#define REG_RTA %r12 +#define REG_RTB %rbx +#define REG_T1 %ebp +#define xmm_mov vmovups +#define avx2_zeroupper vzeroupper +#define RND_F1 1 +#define RND_F2 2 +#define RND_F3 3 + +.macro REGALLOC + .set A, REG_A + .set B, REG_B + .set C, REG_C + .set D, REG_D + .set E, REG_E + .set TB, REG_TB + .set TA, REG_TA + + .set RA, REG_RA + .set RB, REG_RB + .set RC, REG_RC + .set RD, REG_RD + .set RE, REG_RE + + .set RTA, REG_RTA + .set RTB, REG_RTB + + .set T1, REG_T1 +.endm + +#define K_BASE %r8 +#define HASH_PTR %r9 +#define BUFFER_PTR %r10 +#define BUFFER_PTR2 %r13 +#define BUFFER_END %r11 + +#define PRECALC_BUF %r14 +#define WK_BUF %r15 + +#define W_TMP %xmm0 +#define WY_TMP %ymm0 +#define WY_TMP2 %ymm9 + +# AVX2 variables +#define WY0 %ymm3 +#define WY4 %ymm5 +#define WY08 %ymm7 +#define WY12 %ymm8 +#define WY16 %ymm12 +#define WY20 %ymm13 +#define WY24 %ymm14 +#define WY28 %ymm15 + +#define YMM_SHUFB_BSWAP %ymm10 + +# Keep 2 iterations precalculated at a time: +# - 80 DWORDs per iteration * 2 +#define W_SIZE (80*2*2 +16) + +#define WK(t) ((((t) % 80) / 4)*32 + ( (t) % 4)*4 + ((t)/80)*16 )(WK_BUF) +#define PRECALC_WK(t) ((t)*2*2)(PRECALC_BUF) + +#----------------------------------------------------------------------------- +# +# macro implements SHA-1 function's body for several 64-byte blocks +# param: function's name +# +.macro SHA1_VECTOR_ASM name + ENTRY(\name) +.align 4096 + + push %rbx + push %rbp + push %r12 + push %r13 + push %r14 + push %r15 + #FIXME: Save rsp + + RESERVE_STACK = (W_SIZE*4 + 8+24) + + # Align stack + mov %rsp, %rbx + and $(0x1000-1), %rbx + sub $(8+32), %rbx + sub %rbx, %rsp + push %rbx + sub $RESERVE_STACK, %rsp + + avx2_zeroupper + + lea K_XMM_AR(%rip), K_BASE + + mov CTX, HASH_PTR + mov BUF, BUFFER_PTR + lea 64(BUF), BUFFER_PTR2 + + shl $6, CNT # mul by 64 + add BUF, CNT + add $64, CNT + mov CNT, BUFFER_END + + cmp BUFFER_END, BUFFER_PTR2 + cmovae K_BASE, BUFFER_PTR2 + + xmm_mov BSWAP_SHUFB_CTL(%rip), YMM_SHUFB_BSWAP + + SHA1_PIPELINED_MAIN_BODY + + avx2_zeroupper + + add $RESERVE_STACK, %rsp + pop %rbx + add %rbx, %rsp + + pop %r15 + pop %r14 + pop %r13 + pop %r12 + pop %rbp + pop %rbx + + ret + + ENDPROC(\name) +.endm + +#-------------------------------------------- +# macro implements 80 rounds of SHA-1, for multiple blocks with s/w pipelining +# +.macro SHA1_PIPELINED_MAIN_BODY + + REGALLOC + + mov (HASH_PTR), A + mov 4(HASH_PTR), B + mov 8(HASH_PTR), C + mov 12(HASH_PTR), D + mov 16(HASH_PTR), E + + mov %rsp, PRECALC_BUF + lea (2*4*80+32)(%rsp), WK_BUF + + # Precalc WK for first 2 blocks + PRECALC_OFFSET = 0 + .set i, 0 + .rept 160 + PRECALC i + .set i, i + 1 + .endr + PRECALC_OFFSET = 128 + xchg WK_BUF, PRECALC_BUF + + .align 32 + _loop: + # code loops through more than one block + # we use K_BASE value as a signal of a last block, + # it is set below by: cmovae BUFFER_PTR, K_BASE + cmp K_BASE, BUFFER_PTR + jne _begin + .align 32 + jmp _end + .align 32 + _begin: + + # Do first block + RR 0 + RR 2 + RR 4 + RR 6 + RR 8 + + jmp _loop0 +_loop0: + + RR 10 + RR 12 + RR 14 + RR 16 + RR 18 + + RR 20 + RR 22 + RR 24 + RR 26 + RR 28 + + RR 30 + RR 32 + RR 34 + RR 36 + RR 38 + + RR 40 + RR 42 + RR 44 + RR 46 + RR 48 + + RR 50 + RR 52 + RR 54 + RR 56 + RR 58 + + add $(2*64), BUFFER_PTR # move to next odd-64-byte block + cmp BUFFER_END, BUFFER_PTR # is current block the last one? + cmovae K_BASE, BUFFER_PTR # signal the last iteration smartly + + RR 60 + RR 62 + RR 64 + RR 66 + RR 68 + + RR 70 + RR 72 + RR 74 + RR 76 + RR 78 + + UPDATE_HASH (HASH_PTR), A + UPDATE_HASH 4(HASH_PTR), TB + UPDATE_HASH 8(HASH_PTR), C + UPDATE_HASH 12(HASH_PTR), D + UPDATE_HASH 16(HASH_PTR), E + + cmp K_BASE, BUFFER_PTR # is current block the last one? + je _loop + + mov TB, B + + # Process second block + + RR 0+80 + RR 2+80 + RR 4+80 + RR 6+80 + RR 8+80 + + RR 10+80 + RR 12+80 + RR 14+80 + RR 16+80 + RR 18+80 + + jmp _loop1 +_loop1: + + RR 20+80 + RR 22+80 + RR 24+80 + RR 26+80 + RR 28+80 + + RR 30+80 + RR 32+80 + RR 34+80 + RR 36+80 + RR 38+80 + + jmp _loop2 +_loop2: + + RR 40+80 + RR 42+80 + RR 44+80 + RR 46+80 + RR 48+80 + + RR 50+80 + RR 52+80 + RR 54+80 + RR 56+80 + RR 58+80 + + + add $(2*64), BUFFER_PTR2 # move to next even-64-byte block + + cmp BUFFER_END, BUFFER_PTR2 # is current block the last one + cmovae K_BASE, BUFFER_PTR # signal the last iteration smartly + + jmp _loop3 +_loop3: + + RR 60+80 + RR 62+80 + RR 64+80 + RR 66+80 + RR 68+80 + + RR 70+80 + RR 72+80 + RR 74+80 + RR 76+80 + RR 78+80 + + UPDATE_HASH (HASH_PTR), A + UPDATE_HASH 4(HASH_PTR), TB + UPDATE_HASH 8(HASH_PTR), C + UPDATE_HASH 12(HASH_PTR), D + UPDATE_HASH 16(HASH_PTR), E + + # Reset state for AVX2 reg permutation + mov A, TA + mov TB, A + mov C, TB + mov E, C + mov D, B + mov TA, D + + REGALLOC + + xchg WK_BUF, PRECALC_BUF + + jmp _loop + + .align 32 + _end: + +.endm + +.macro UPDATE_HASH hash, val + add \hash, \val + mov \val, \hash +.endm + +.macro PRECALC r, s + .set i, \r + + .if (i < 40) + .set K_XMM, 32*0 + .elseif (i < 80) + .set K_XMM, 32*1 + .elseif (i < 120) + .set K_XMM, 32*2 + .else + .set K_XMM, 32*3 + .endif + + .if (i<32) + PRECALC_00_15 \s + .elseif (i<64) + PRECALC_16_31 \s + .elseif (i < 160) + PRECALC_32_79 \s + .endif +.endm + +.macro PRECALC_RESET_WY + .set WY_00, WY0 + .set WY_04, WY4 + .set WY_08, WY08 + .set WY_12, WY12 + .set WY_16, WY16 + .set WY_20, WY20 + .set WY_24, WY24 + .set WY_28, WY28 + .set WY_32, WY_00 +.endm + +.macro PRECALC_ROTATE_WY + # Rotate macros + .set WY_32, WY_28 + .set WY_28, WY_24 + .set WY_24, WY_20 + .set WY_20, WY_16 + .set WY_16, WY_12 + .set WY_12, WY_08 + .set WY_08, WY_04 + .set WY_04, WY_00 + .set WY_00, WY_32 + + # Define register aliases + .set WY, WY_00 + .set WY_minus_04, WY_04 + .set WY_minus_08, WY_08 + .set WY_minus_12, WY_12 + .set WY_minus_16, WY_16 + .set WY_minus_20, WY_20 + .set WY_minus_24, WY_24 + .set WY_minus_28, WY_28 + .set WY_minus_32, WY +.endm + +.macro PRECALC_00_15 + + .if (i == 0) # Initialize and rotate registers + PRECALC_RESET_WY + PRECALC_ROTATE_WY + .endif + + # message scheduling pre-compute for rounds 0-15 + .if ((i & 7) == 0) + #blended AVX2 and ALU instruction scheduling + #1 vector iteration per 8 rounds + vmovdqu ((i * 2) + PRECALC_OFFSET)(BUFFER_PTR), W_TMP + .elseif ((i & 7) == 1) + vinsertf128 $1, (((i-1) * 2)+PRECALC_OFFSET)(BUFFER_PTR2), WY_TMP, WY_TMP + .elseif ((i & 7) == 2) + vpshufb YMM_SHUFB_BSWAP, WY_TMP, WY + .elseif ((i & 7) == 4) + vpaddd K_XMM(K_BASE), WY, WY_TMP + .elseif ((i & 7) == 7) + vmovdqu WY_TMP, PRECALC_WK(i&~7) + + PRECALC_ROTATE_WY + .endif + +.endm + +.macro PRECALC_16_31 + # message scheduling pre-compute for rounds 16-31 + # calculating last 32 w[i] values in 8 XMM registers + # pre-calculate K+w[i] values and store to mem + # for later load by ALU add instruction + # + # "brute force" vectorization for rounds 16-31 only + # due to w[i]->w[i-3] dependency + # + .if ((i & 7) == 0) + #blended AVX2 and ALU instruction scheduling + #1 vector iteration per 8 rounds + vpalignr $8, WY_minus_16, WY_minus_12, WY # w[i-14] + vpsrldq $4, WY_minus_04, WY_TMP # w[i-3] + .elseif ((i & 7) == 1) + vpxor WY_minus_08, WY, WY + vpxor WY_minus_16, WY_TMP, WY_TMP + .elseif ((i & 7) == 2) + vpxor WY_TMP, WY, WY + vpslldq $12, WY, WY_TMP2 + .elseif ((i & 7) == 3) + vpslld $1, WY, WY_TMP + vpsrld $31, WY, WY + .elseif ((i & 7) == 4) + vpor WY, WY_TMP, WY_TMP + vpslld $2, WY_TMP2, WY + .elseif ((i & 7) == 5) + vpsrld $30, WY_TMP2, WY_TMP2 + vpxor WY, WY_TMP, WY_TMP + .elseif ((i & 7) == 7) + vpxor WY_TMP2, WY_TMP, WY + vpaddd K_XMM(K_BASE), WY, WY_TMP + vmovdqu WY_TMP, PRECALC_WK(i&~7) + + PRECALC_ROTATE_WY + .endif +.endm + +.macro PRECALC_32_79 + # in SHA-1 specification: + # w[i] = (w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16]) rol 1 + # instead we do equal: + # w[i] = (w[i-6] ^ w[i-16] ^ w[i-28] ^ w[i-32]) rol 2 + # allows more efficient vectorization + # since w[i]=>w[i-3] dependency is broken + # + .if ((i & 7) == 0) + #blended AVX2 and ALU instruction scheduling + #1 vector iteration per 8 rounds + vpalignr $8, WY_minus_08, WY_minus_04, WY_TMP + .elseif ((i & 7) == 1) + vpxor WY_minus_28, WY, WY # W is W_minus_32 before xor + .elseif ((i & 7) == 2) + vpxor WY_minus_16, WY_TMP, WY_TMP + .elseif ((i & 7) == 3) + vpxor WY_TMP, WY, WY + .elseif ((i & 7) == 4) + vpslld $2, WY, WY_TMP + .elseif ((i & 7) == 5) + vpsrld $30, WY, WY + vpor WY, WY_TMP, WY + .elseif ((i & 7) == 7) + vpaddd K_XMM(K_BASE), WY, WY_TMP + vmovdqu WY_TMP, PRECALC_WK(i&~7) + + PRECALC_ROTATE_WY + .endif +.endm + +.macro ROTATE_STATE + .set T_REG, E + .set E, D + .set D, C + .set C, B + .set B, TB + .set TB, A + .set A, T_REG + + .set T_REG, RE + .set RE, RD + .set RD, RC + .set RC, RB + .set RB, RTB + .set RTB, RA + .set RA, T_REG +.endm + +# Macro relies on saved ROUND_Fx + +.macro RND_FUN f, r + .if (\f == RND_F1) + ROUND_F1 \r + .elseif (\f == RND_F2) + ROUND_F2 \r + .elseif (\f == RND_F3) + ROUND_F3 \r + .endif +.endm + +.macro RR r + .set round_id, (\r % 80) + + .if (round_id == 0) # Precalculate F for first round + .set ROUND_FUNC, RND_F1 + mov B, TB + + rorx $(32-30), B, B # b>>>2 + andn D, TB, T1 + and C, TB + xor T1, TB + .endif + + RND_FUN ROUND_FUNC, \r + ROTATE_STATE + + .if (round_id == 18) + .set ROUND_FUNC, RND_F2 + .elseif (round_id == 38) + .set ROUND_FUNC, RND_F3 + .elseif (round_id == 58) + .set ROUND_FUNC, RND_F2 + .endif + + .set round_id, ( (\r+1) % 80) + + RND_FUN ROUND_FUNC, (\r+1) + ROTATE_STATE +.endm + +.macro ROUND_F1 r + add WK(\r), E + + andn C, A, T1 # ~b&d + lea (RE,RTB), E # Add F from the previous round + + rorx $(32-5), A, TA # T2 = A >>> 5 + rorx $(32-30),A, TB # b>>>2 for next round + + PRECALC (\r) # message scheduling for next 2 blocks + + # Calculate F for the next round + # (b & c) ^ andn[b, d] + and B, A # b&c + xor T1, A # F1 = (b&c) ^ (~b&d) + + lea (RE,RTA), E # E += A >>> 5 +.endm + +.macro ROUND_F2 r + add WK(\r), E + lea (RE,RTB), E # Add F from the previous round + + # Calculate F for the next round + rorx $(32-5), A, TA # T2 = A >>> 5 + .if ((round_id) < 79) + rorx $(32-30), A, TB # b>>>2 for next round + .endif + PRECALC (\r) # message scheduling for next 2 blocks + + .if ((round_id) < 79) + xor B, A + .endif + + add TA, E # E += A >>> 5 + + .if ((round_id) < 79) + xor C, A + .endif +.endm + +.macro ROUND_F3 r + add WK(\r), E + PRECALC (\r) # message scheduling for next 2 blocks + + lea (RE,RTB), E # Add F from the previous round + + mov B, T1 + or A, T1 + + rorx $(32-5), A, TA # T2 = A >>> 5 + rorx $(32-30), A, TB # b>>>2 for next round + + # Calculate F for the next round + # (b and c) or (d and (b or c)) + and C, T1 + and B, A + or T1, A + + add TA, E # E += A >>> 5 + +.endm + +#---------------------- +.section .rodata + +#define K1 0x5a827999 +#define K2 0x6ed9eba1 +#define K3 0x8f1bbcdc +#define K4 0xca62c1d6 + +.align 128 +K_XMM_AR: + .long K1, K1, K1, K1 + .long K1, K1, K1, K1 + .long K2, K2, K2, K2 + .long K2, K2, K2, K2 + .long K3, K3, K3, K3 + .long K3, K3, K3, K3 + .long K4, K4, K4, K4 + .long K4, K4, K4, K4 + +BSWAP_SHUFB_CTL: + .long 0x00010203 + .long 0x04050607 + .long 0x08090a0b + .long 0x0c0d0e0f + .long 0x00010203 + .long 0x04050607 + .long 0x08090a0b + .long 0x0c0d0e0f + +##---------------------- +.text + +/* AVX2 optimized implementation: + * extern "C" void sha1_transform_avx2( + * int *hash, const char* input, size_t num_blocks ); + */ +SHA1_VECTOR_ASM sha1_transform_avx2 +#endif /* CONFIG_AS_AVX2 */ -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
