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