1 /* SPDX-License-Identifier: GPL-2.0 */ 2 /* 3 * Copyright 2021 Google LLC 4 */ 5 /* 6 * This is an efficient implementation of POLYVAL using intel PCLMULQDQ-NI 7 * instructions. It works on 8 blocks at a time, by precomputing the first 8 8 * keys powers h^8, ..., h^1 in the POLYVAL finite field. This precomputation 9 * allows us to split finite field multiplication into two steps. 10 * 11 * In the first step, we consider h^i, m_i as normal polynomials of degree less 12 * than 128. We then compute p(x) = h^8m_0 + ... + h^1m_7 where multiplication 13 * is simply polynomial multiplication. 14 * 15 * In the second step, we compute the reduction of p(x) modulo the finite field 16 * modulus g(x) = x^128 + x^127 + x^126 + x^121 + 1. 17 * 18 * This two step process is equivalent to computing h^8m_0 + ... + h^1m_7 where 19 * multiplication is finite field multiplication. The advantage is that the 20 * two-step process only requires 1 finite field reduction for every 8 21 * polynomial multiplications. Further parallelism is gained by interleaving the 22 * multiplications and polynomial reductions. 23 */ 24 25 #include <linux/linkage.h> 26 #include <asm/frame.h> 27 28 #define STRIDE_BLOCKS 8 29 30 #define GSTAR %xmm7 31 #define PL %xmm8 32 #define PH %xmm9 33 #define TMP_XMM %xmm11 34 #define LO %xmm12 35 #define HI %xmm13 36 #define MI %xmm14 37 #define SUM %xmm15 38 39 #define KEY_POWERS %rdi 40 #define MSG %rsi 41 #define BLOCKS_LEFT %rdx 42 #define ACCUMULATOR %rcx 43 #define TMP %rax 44 45 .section .rodata.cst16.gstar, "aM", @progbits, 16 46 .align 16 47 48 .Lgstar: 49 .quad 0xc200000000000000, 0xc200000000000000 50 51 .text 52 53 /* 54 * Performs schoolbook1_iteration on two lists of 128-bit polynomials of length 55 * count pointed to by MSG and KEY_POWERS. 56 */ 57 .macro schoolbook1 count 58 .set i, 0 59 .rept (\count) 60 schoolbook1_iteration i 0 61 .set i, (i +1) 62 .endr 63 .endm 64 65 /* 66 * Computes the product of two 128-bit polynomials at the memory locations 67 * specified by (MSG + 16*i) and (KEY_POWERS + 16*i) and XORs the components of 68 * the 256-bit product into LO, MI, HI. 69 * 70 * Given: 71 * X = [X_1 : X_0] 72 * Y = [Y_1 : Y_0] 73 * 74 * We compute: 75 * LO += X_0 * Y_0 76 * MI += X_0 * Y_1 + X_1 * Y_0 77 * HI += X_1 * Y_1 78 * 79 * Later, the 256-bit result can be extracted as: 80 * [HI_1 : HI_0 + MI_1 : LO_1 + MI_0 : LO_0] 81 * This step is done when computing the polynomial reduction for efficiency 82 * reasons. 83 * 84 * If xor_sum == 1, then also XOR the value of SUM into m_0. This avoids an 85 * extra multiplication of SUM and h^8. 86 */ 87 .macro schoolbook1_iteration i xor_sum 88 movups (16*\i)(MSG), %xmm0 89 .if (\i == 0 && \xor_sum == 1) 90 pxor SUM, %xmm0 91 .endif 92 vpclmulqdq $0x01, (16*\i)(KEY_POWERS), %xmm0, %xmm2 93 vpclmulqdq $0x00, (16*\i)(KEY_POWERS), %xmm0, %xmm1 94 vpclmulqdq $0x10, (16*\i)(KEY_POWERS), %xmm0, %xmm3 95 vpclmulqdq $0x11, (16*\i)(KEY_POWERS), %xmm0, %xmm4 96 vpxor %xmm2, MI, MI 97 vpxor %xmm1, LO, LO 98 vpxor %xmm4, HI, HI 99 vpxor %xmm3, MI, MI 100 .endm 101 102 /* 103 * Performs the same computation as schoolbook1_iteration, except we expect the 104 * arguments to already be loaded into xmm0 and xmm1 and we set the result 105 * registers LO, MI, and HI directly rather than XOR'ing into them. 106 */ 107 .macro schoolbook1_noload 108 vpclmulqdq $0x01, %xmm0, %xmm1, MI 109 vpclmulqdq $0x10, %xmm0, %xmm1, %xmm2 110 vpclmulqdq $0x00, %xmm0, %xmm1, LO 111 vpclmulqdq $0x11, %xmm0, %xmm1, HI 112 vpxor %xmm2, MI, MI 113 .endm 114 115 /* 116 * Computes the 256-bit polynomial represented by LO, HI, MI. Stores 117 * the result in PL, PH. 118 * [PH : PL] = [HI_1 : HI_0 + MI_1 : LO_1 + MI_0 : LO_0] 119 */ 120 .macro schoolbook2 121 vpslldq $8, MI, PL 122 vpsrldq $8, MI, PH 123 pxor LO, PL 124 pxor HI, PH 125 .endm 126 127 /* 128 * Computes the 128-bit reduction of PH : PL. Stores the result in dest. 129 * 130 * This macro computes p(x) mod g(x) where p(x) is in montgomery form and g(x) = 131 * x^128 + x^127 + x^126 + x^121 + 1. 132 * 133 * We have a 256-bit polynomial PH : PL = P_3 : P_2 : P_1 : P_0 that is the 134 * product of two 128-bit polynomials in Montgomery form. We need to reduce it 135 * mod g(x). Also, since polynomials in Montgomery form have an "extra" factor 136 * of x^128, this product has two extra factors of x^128. To get it back into 137 * Montgomery form, we need to remove one of these factors by dividing by x^128. 138 * 139 * To accomplish both of these goals, we add multiples of g(x) that cancel out 140 * the low 128 bits P_1 : P_0, leaving just the high 128 bits. Since the low 141 * bits are zero, the polynomial division by x^128 can be done by right shifting. 142 * 143 * Since the only nonzero term in the low 64 bits of g(x) is the constant term, 144 * the multiple of g(x) needed to cancel out P_0 is P_0 * g(x). The CPU can 145 * only do 64x64 bit multiplications, so split P_0 * g(x) into x^128 * P_0 + 146 * x^64 * g*(x) * P_0 + P_0, where g*(x) is bits 64-127 of g(x). Adding this to 147 * the original polynomial gives P_3 : P_2 + P_0 + T_1 : P_1 + T_0 : 0, where T 148 * = T_1 : T_0 = g*(x) * P_0. Thus, bits 0-63 got "folded" into bits 64-191. 149 * 150 * Repeating this same process on the next 64 bits "folds" bits 64-127 into bits 151 * 128-255, giving the answer in bits 128-255. This time, we need to cancel P_1 152 * + T_0 in bits 64-127. The multiple of g(x) required is (P_1 + T_0) * g(x) * 153 * x^64. Adding this to our previous computation gives P_3 + P_1 + T_0 + V_1 : 154 * P_2 + P_0 + T_1 + V_0 : 0 : 0, where V = V_1 : V_0 = g*(x) * (P_1 + T_0). 155 * 156 * So our final computation is: 157 * T = T_1 : T_0 = g*(x) * P_0 158 * V = V_1 : V_0 = g*(x) * (P_1 + T_0) 159 * p(x) / x^{128} mod g(x) = P_3 + P_1 + T_0 + V_1 : P_2 + P_0 + T_1 + V_0 160 * 161 * The implementation below saves a XOR instruction by computing P_1 + T_0 : P_0 162 * + T_1 and XORing into dest, rather than separately XORing P_1 : P_0 and T_0 : 163 * T_1 into dest. This allows us to reuse P_1 + T_0 when computing V. 164 */ 165 .macro montgomery_reduction dest 166 vpclmulqdq $0x00, PL, GSTAR, TMP_XMM # TMP_XMM = T_1 : T_0 = P_0 * g*(x) 167 pshufd $0b01001110, TMP_XMM, TMP_XMM # TMP_XMM = T_0 : T_1 168 pxor PL, TMP_XMM # TMP_XMM = P_1 + T_0 : P_0 + T_1 169 pxor TMP_XMM, PH # PH = P_3 + P_1 + T_0 : P_2 + P_0 + T_1 170 pclmulqdq $0x11, GSTAR, TMP_XMM # TMP_XMM = V_1 : V_0 = V = [(P_1 + T_0) * g*(x)] 171 vpxor TMP_XMM, PH, \dest 172 .endm 173 174 /* 175 * Compute schoolbook multiplication for 8 blocks 176 * m_0h^8 + ... + m_7h^1 177 * 178 * If reduce is set, also computes the montgomery reduction of the 179 * previous full_stride call and XORs with the first message block. 180 * (m_0 + REDUCE(PL, PH))h^8 + ... + m_7h^1. 181 * I.e., the first multiplication uses m_0 + REDUCE(PL, PH) instead of m_0. 182 */ 183 .macro full_stride reduce 184 pxor LO, LO 185 pxor HI, HI 186 pxor MI, MI 187 188 schoolbook1_iteration 7 0 189 .if \reduce 190 vpclmulqdq $0x00, PL, GSTAR, TMP_XMM 191 .endif 192 193 schoolbook1_iteration 6 0 194 .if \reduce 195 pshufd $0b01001110, TMP_XMM, TMP_XMM 196 .endif 197 198 schoolbook1_iteration 5 0 199 .if \reduce 200 pxor PL, TMP_XMM 201 .endif 202 203 schoolbook1_iteration 4 0 204 .if \reduce 205 pxor TMP_XMM, PH 206 .endif 207 208 schoolbook1_iteration 3 0 209 .if \reduce 210 pclmulqdq $0x11, GSTAR, TMP_XMM 211 .endif 212 213 schoolbook1_iteration 2 0 214 .if \reduce 215 vpxor TMP_XMM, PH, SUM 216 .endif 217 218 schoolbook1_iteration 1 0 219 220 schoolbook1_iteration 0 1 221 222 addq $(8*16), MSG 223 schoolbook2 224 .endm 225 226 /* 227 * Process BLOCKS_LEFT blocks, where 0 < BLOCKS_LEFT < STRIDE_BLOCKS 228 */ 229 .macro partial_stride 230 mov BLOCKS_LEFT, TMP 231 shlq $4, TMP 232 addq $(16*STRIDE_BLOCKS), KEY_POWERS 233 subq TMP, KEY_POWERS 234 235 movups (MSG), %xmm0 236 pxor SUM, %xmm0 237 movaps (KEY_POWERS), %xmm1 238 schoolbook1_noload 239 dec BLOCKS_LEFT 240 addq $16, MSG 241 addq $16, KEY_POWERS 242 243 test $4, BLOCKS_LEFT 244 jz .Lpartial4BlocksDone 245 schoolbook1 4 246 addq $(4*16), MSG 247 addq $(4*16), KEY_POWERS 248 .Lpartial4BlocksDone: 249 test $2, BLOCKS_LEFT 250 jz .Lpartial2BlocksDone 251 schoolbook1 2 252 addq $(2*16), MSG 253 addq $(2*16), KEY_POWERS 254 .Lpartial2BlocksDone: 255 test $1, BLOCKS_LEFT 256 jz .LpartialDone 257 schoolbook1 1 258 .LpartialDone: 259 schoolbook2 260 montgomery_reduction SUM 261 .endm 262 263 /* 264 * Perform montgomery multiplication in GF(2^128) and store result in op1. 265 * 266 * Computes op1*op2*x^{-128} mod x^128 + x^127 + x^126 + x^121 + 1 267 * If op1, op2 are in montgomery form, this computes the montgomery 268 * form of op1*op2. 269 * 270 * void clmul_polyval_mul(u8 *op1, const u8 *op2); 271 */ 272 SYM_FUNC_START(clmul_polyval_mul) 273 FRAME_BEGIN 274 vmovdqa .Lgstar(%rip), GSTAR 275 movups (%rdi), %xmm0 276 movups (%rsi), %xmm1 277 schoolbook1_noload 278 schoolbook2 279 montgomery_reduction SUM 280 movups SUM, (%rdi) 281 FRAME_END 282 RET 283 SYM_FUNC_END(clmul_polyval_mul) 284 285 /* 286 * Perform polynomial evaluation as specified by POLYVAL. This computes: 287 * h^n * accumulator + h^n * m_0 + ... + h^1 * m_{n-1} 288 * where n=nblocks, h is the hash key, and m_i are the message blocks. 289 * 290 * rdi - pointer to precomputed key powers h^8 ... h^1 291 * rsi - pointer to message blocks 292 * rdx - number of blocks to hash 293 * rcx - pointer to the accumulator 294 * 295 * void clmul_polyval_update(const struct polyval_tfm_ctx *keys, 296 * const u8 *in, size_t nblocks, u8 *accumulator); 297 */ 298 SYM_FUNC_START(clmul_polyval_update) 299 FRAME_BEGIN 300 vmovdqa .Lgstar(%rip), GSTAR 301 movups (ACCUMULATOR), SUM 302 subq $STRIDE_BLOCKS, BLOCKS_LEFT 303 js .LstrideLoopExit 304 full_stride 0 305 subq $STRIDE_BLOCKS, BLOCKS_LEFT 306 js .LstrideLoopExitReduce 307 .LstrideLoop: 308 full_stride 1 309 subq $STRIDE_BLOCKS, BLOCKS_LEFT 310 jns .LstrideLoop 311 .LstrideLoopExitReduce: 312 montgomery_reduction SUM 313 .LstrideLoopExit: 314 add $STRIDE_BLOCKS, BLOCKS_LEFT 315 jz .LskipPartial 316 partial_stride 317 .LskipPartial: 318 movups SUM, (ACCUMULATOR) 319 FRAME_END 320 RET 321 SYM_FUNC_END(clmul_polyval_update) 322