1 | // SPDX-License-Identifier: GPL-2.0 OR MIT |
2 | /* |
3 | * Copyright (C) 2020 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. |
4 | * Copyright (c) 2016-2020 INRIA, CMU and Microsoft Corporation |
5 | */ |
6 | |
7 | #include <crypto/curve25519.h> |
8 | #include <crypto/internal/kpp.h> |
9 | |
10 | #include <linux/types.h> |
11 | #include <linux/jump_label.h> |
12 | #include <linux/kernel.h> |
13 | #include <linux/module.h> |
14 | #include <linux/scatterlist.h> |
15 | |
16 | #include <asm/cpufeature.h> |
17 | #include <asm/processor.h> |
18 | |
19 | static __always_inline u64 eq_mask(u64 a, u64 b) |
20 | { |
21 | u64 x = a ^ b; |
22 | u64 minus_x = ~x + (u64)1U; |
23 | u64 x_or_minus_x = x | minus_x; |
24 | u64 xnx = x_or_minus_x >> (u32)63U; |
25 | return xnx - (u64)1U; |
26 | } |
27 | |
28 | static __always_inline u64 gte_mask(u64 a, u64 b) |
29 | { |
30 | u64 x = a; |
31 | u64 y = b; |
32 | u64 x_xor_y = x ^ y; |
33 | u64 x_sub_y = x - y; |
34 | u64 x_sub_y_xor_y = x_sub_y ^ y; |
35 | u64 q = x_xor_y | x_sub_y_xor_y; |
36 | u64 x_xor_q = x ^ q; |
37 | u64 x_xor_q_ = x_xor_q >> (u32)63U; |
38 | return x_xor_q_ - (u64)1U; |
39 | } |
40 | |
41 | /* Computes the addition of four-element f1 with value in f2 |
42 | * and returns the carry (if any) */ |
43 | static inline u64 add_scalar(u64 *out, const u64 *f1, u64 f2) |
44 | { |
45 | u64 carry_r; |
46 | |
47 | asm volatile( |
48 | /* Clear registers to propagate the carry bit */ |
49 | " xor %%r8d, %%r8d;" |
50 | " xor %%r9d, %%r9d;" |
51 | " xor %%r10d, %%r10d;" |
52 | " xor %%r11d, %%r11d;" |
53 | " xor %k1, %k1;" |
54 | |
55 | /* Begin addition chain */ |
56 | " addq 0(%3), %0;" |
57 | " movq %0, 0(%2);" |
58 | " adcxq 8(%3), %%r8;" |
59 | " movq %%r8, 8(%2);" |
60 | " adcxq 16(%3), %%r9;" |
61 | " movq %%r9, 16(%2);" |
62 | " adcxq 24(%3), %%r10;" |
63 | " movq %%r10, 24(%2);" |
64 | |
65 | /* Return the carry bit in a register */ |
66 | " adcx %%r11, %1;" |
67 | : "+&r" (f2), "=&r" (carry_r) |
68 | : "r" (out), "r" (f1) |
69 | : "%r8" , "%r9" , "%r10" , "%r11" , "memory" , "cc" ); |
70 | |
71 | return carry_r; |
72 | } |
73 | |
74 | /* Computes the field addition of two field elements */ |
75 | static inline void fadd(u64 *out, const u64 *f1, const u64 *f2) |
76 | { |
77 | asm volatile( |
78 | /* Compute the raw addition of f1 + f2 */ |
79 | " movq 0(%0), %%r8;" |
80 | " addq 0(%2), %%r8;" |
81 | " movq 8(%0), %%r9;" |
82 | " adcxq 8(%2), %%r9;" |
83 | " movq 16(%0), %%r10;" |
84 | " adcxq 16(%2), %%r10;" |
85 | " movq 24(%0), %%r11;" |
86 | " adcxq 24(%2), %%r11;" |
87 | |
88 | /* Wrap the result back into the field */ |
89 | |
90 | /* Step 1: Compute carry*38 */ |
91 | " mov $0, %%rax;" |
92 | " mov $38, %0;" |
93 | " cmovc %0, %%rax;" |
94 | |
95 | /* Step 2: Add carry*38 to the original sum */ |
96 | " xor %%ecx, %%ecx;" |
97 | " add %%rax, %%r8;" |
98 | " adcx %%rcx, %%r9;" |
99 | " movq %%r9, 8(%1);" |
100 | " adcx %%rcx, %%r10;" |
101 | " movq %%r10, 16(%1);" |
102 | " adcx %%rcx, %%r11;" |
103 | " movq %%r11, 24(%1);" |
104 | |
105 | /* Step 3: Fold the carry bit back in; guaranteed not to carry at this point */ |
106 | " mov $0, %%rax;" |
107 | " cmovc %0, %%rax;" |
108 | " add %%rax, %%r8;" |
109 | " movq %%r8, 0(%1);" |
110 | : "+&r" (f2) |
111 | : "r" (out), "r" (f1) |
112 | : "%rax" , "%rcx" , "%r8" , "%r9" , "%r10" , "%r11" , "memory" , "cc" ); |
113 | } |
114 | |
115 | /* Computes the field subtraction of two field elements */ |
116 | static inline void fsub(u64 *out, const u64 *f1, const u64 *f2) |
117 | { |
118 | asm volatile( |
119 | /* Compute the raw subtraction of f1-f2 */ |
120 | " movq 0(%1), %%r8;" |
121 | " subq 0(%2), %%r8;" |
122 | " movq 8(%1), %%r9;" |
123 | " sbbq 8(%2), %%r9;" |
124 | " movq 16(%1), %%r10;" |
125 | " sbbq 16(%2), %%r10;" |
126 | " movq 24(%1), %%r11;" |
127 | " sbbq 24(%2), %%r11;" |
128 | |
129 | /* Wrap the result back into the field */ |
130 | |
131 | /* Step 1: Compute carry*38 */ |
132 | " mov $0, %%rax;" |
133 | " mov $38, %%rcx;" |
134 | " cmovc %%rcx, %%rax;" |
135 | |
136 | /* Step 2: Subtract carry*38 from the original difference */ |
137 | " sub %%rax, %%r8;" |
138 | " sbb $0, %%r9;" |
139 | " sbb $0, %%r10;" |
140 | " sbb $0, %%r11;" |
141 | |
142 | /* Step 3: Fold the carry bit back in; guaranteed not to carry at this point */ |
143 | " mov $0, %%rax;" |
144 | " cmovc %%rcx, %%rax;" |
145 | " sub %%rax, %%r8;" |
146 | |
147 | /* Store the result */ |
148 | " movq %%r8, 0(%0);" |
149 | " movq %%r9, 8(%0);" |
150 | " movq %%r10, 16(%0);" |
151 | " movq %%r11, 24(%0);" |
152 | : |
153 | : "r" (out), "r" (f1), "r" (f2) |
154 | : "%rax" , "%rcx" , "%r8" , "%r9" , "%r10" , "%r11" , "memory" , "cc" ); |
155 | } |
156 | |
157 | /* Computes a field multiplication: out <- f1 * f2 |
158 | * Uses the 8-element buffer tmp for intermediate results */ |
159 | static inline void fmul(u64 *out, const u64 *f1, const u64 *f2, u64 *tmp) |
160 | { |
161 | asm volatile( |
162 | |
163 | /* Compute the raw multiplication: tmp <- src1 * src2 */ |
164 | |
165 | /* Compute src1[0] * src2 */ |
166 | " movq 0(%0), %%rdx;" |
167 | " mulxq 0(%1), %%r8, %%r9;" |
168 | " xor %%r10d, %%r10d;" |
169 | " movq %%r8, 0(%2);" |
170 | " mulxq 8(%1), %%r10, %%r11;" |
171 | " adox %%r9, %%r10;" |
172 | " movq %%r10, 8(%2);" |
173 | " mulxq 16(%1), %%rbx, %%r13;" |
174 | " adox %%r11, %%rbx;" |
175 | " mulxq 24(%1), %%r14, %%rdx;" |
176 | " adox %%r13, %%r14;" |
177 | " mov $0, %%rax;" |
178 | " adox %%rdx, %%rax;" |
179 | |
180 | /* Compute src1[1] * src2 */ |
181 | " movq 8(%0), %%rdx;" |
182 | " mulxq 0(%1), %%r8, %%r9;" |
183 | " xor %%r10d, %%r10d;" |
184 | " adcxq 8(%2), %%r8;" |
185 | " movq %%r8, 8(%2);" |
186 | " mulxq 8(%1), %%r10, %%r11;" |
187 | " adox %%r9, %%r10;" |
188 | " adcx %%rbx, %%r10;" |
189 | " movq %%r10, 16(%2);" |
190 | " mulxq 16(%1), %%rbx, %%r13;" |
191 | " adox %%r11, %%rbx;" |
192 | " adcx %%r14, %%rbx;" |
193 | " mov $0, %%r8;" |
194 | " mulxq 24(%1), %%r14, %%rdx;" |
195 | " adox %%r13, %%r14;" |
196 | " adcx %%rax, %%r14;" |
197 | " mov $0, %%rax;" |
198 | " adox %%rdx, %%rax;" |
199 | " adcx %%r8, %%rax;" |
200 | |
201 | /* Compute src1[2] * src2 */ |
202 | " movq 16(%0), %%rdx;" |
203 | " mulxq 0(%1), %%r8, %%r9;" |
204 | " xor %%r10d, %%r10d;" |
205 | " adcxq 16(%2), %%r8;" |
206 | " movq %%r8, 16(%2);" |
207 | " mulxq 8(%1), %%r10, %%r11;" |
208 | " adox %%r9, %%r10;" |
209 | " adcx %%rbx, %%r10;" |
210 | " movq %%r10, 24(%2);" |
211 | " mulxq 16(%1), %%rbx, %%r13;" |
212 | " adox %%r11, %%rbx;" |
213 | " adcx %%r14, %%rbx;" |
214 | " mov $0, %%r8;" |
215 | " mulxq 24(%1), %%r14, %%rdx;" |
216 | " adox %%r13, %%r14;" |
217 | " adcx %%rax, %%r14;" |
218 | " mov $0, %%rax;" |
219 | " adox %%rdx, %%rax;" |
220 | " adcx %%r8, %%rax;" |
221 | |
222 | /* Compute src1[3] * src2 */ |
223 | " movq 24(%0), %%rdx;" |
224 | " mulxq 0(%1), %%r8, %%r9;" |
225 | " xor %%r10d, %%r10d;" |
226 | " adcxq 24(%2), %%r8;" |
227 | " movq %%r8, 24(%2);" |
228 | " mulxq 8(%1), %%r10, %%r11;" |
229 | " adox %%r9, %%r10;" |
230 | " adcx %%rbx, %%r10;" |
231 | " movq %%r10, 32(%2);" |
232 | " mulxq 16(%1), %%rbx, %%r13;" |
233 | " adox %%r11, %%rbx;" |
234 | " adcx %%r14, %%rbx;" |
235 | " movq %%rbx, 40(%2);" |
236 | " mov $0, %%r8;" |
237 | " mulxq 24(%1), %%r14, %%rdx;" |
238 | " adox %%r13, %%r14;" |
239 | " adcx %%rax, %%r14;" |
240 | " movq %%r14, 48(%2);" |
241 | " mov $0, %%rax;" |
242 | " adox %%rdx, %%rax;" |
243 | " adcx %%r8, %%rax;" |
244 | " movq %%rax, 56(%2);" |
245 | |
246 | /* Line up pointers */ |
247 | " mov %2, %0;" |
248 | " mov %3, %2;" |
249 | |
250 | /* Wrap the result back into the field */ |
251 | |
252 | /* Step 1: Compute dst + carry == tmp_hi * 38 + tmp_lo */ |
253 | " mov $38, %%rdx;" |
254 | " mulxq 32(%0), %%r8, %%r13;" |
255 | " xor %k1, %k1;" |
256 | " adoxq 0(%0), %%r8;" |
257 | " mulxq 40(%0), %%r9, %%rbx;" |
258 | " adcx %%r13, %%r9;" |
259 | " adoxq 8(%0), %%r9;" |
260 | " mulxq 48(%0), %%r10, %%r13;" |
261 | " adcx %%rbx, %%r10;" |
262 | " adoxq 16(%0), %%r10;" |
263 | " mulxq 56(%0), %%r11, %%rax;" |
264 | " adcx %%r13, %%r11;" |
265 | " adoxq 24(%0), %%r11;" |
266 | " adcx %1, %%rax;" |
267 | " adox %1, %%rax;" |
268 | " imul %%rdx, %%rax;" |
269 | |
270 | /* Step 2: Fold the carry back into dst */ |
271 | " add %%rax, %%r8;" |
272 | " adcx %1, %%r9;" |
273 | " movq %%r9, 8(%2);" |
274 | " adcx %1, %%r10;" |
275 | " movq %%r10, 16(%2);" |
276 | " adcx %1, %%r11;" |
277 | " movq %%r11, 24(%2);" |
278 | |
279 | /* Step 3: Fold the carry bit back in; guaranteed not to carry at this point */ |
280 | " mov $0, %%rax;" |
281 | " cmovc %%rdx, %%rax;" |
282 | " add %%rax, %%r8;" |
283 | " movq %%r8, 0(%2);" |
284 | : "+&r" (f1), "+&r" (f2), "+&r" (tmp) |
285 | : "r" (out) |
286 | : "%rax" , "%rbx" , "%rdx" , "%r8" , "%r9" , "%r10" , "%r11" , "%r13" , |
287 | "%r14" , "memory" , "cc" ); |
288 | } |
289 | |
290 | /* Computes two field multiplications: |
291 | * out[0] <- f1[0] * f2[0] |
292 | * out[1] <- f1[1] * f2[1] |
293 | * Uses the 16-element buffer tmp for intermediate results: */ |
294 | static inline void fmul2(u64 *out, const u64 *f1, const u64 *f2, u64 *tmp) |
295 | { |
296 | asm volatile( |
297 | |
298 | /* Compute the raw multiplication tmp[0] <- f1[0] * f2[0] */ |
299 | |
300 | /* Compute src1[0] * src2 */ |
301 | " movq 0(%0), %%rdx;" |
302 | " mulxq 0(%1), %%r8, %%r9;" |
303 | " xor %%r10d, %%r10d;" |
304 | " movq %%r8, 0(%2);" |
305 | " mulxq 8(%1), %%r10, %%r11;" |
306 | " adox %%r9, %%r10;" |
307 | " movq %%r10, 8(%2);" |
308 | " mulxq 16(%1), %%rbx, %%r13;" |
309 | " adox %%r11, %%rbx;" |
310 | " mulxq 24(%1), %%r14, %%rdx;" |
311 | " adox %%r13, %%r14;" |
312 | " mov $0, %%rax;" |
313 | " adox %%rdx, %%rax;" |
314 | |
315 | /* Compute src1[1] * src2 */ |
316 | " movq 8(%0), %%rdx;" |
317 | " mulxq 0(%1), %%r8, %%r9;" |
318 | " xor %%r10d, %%r10d;" |
319 | " adcxq 8(%2), %%r8;" |
320 | " movq %%r8, 8(%2);" |
321 | " mulxq 8(%1), %%r10, %%r11;" |
322 | " adox %%r9, %%r10;" |
323 | " adcx %%rbx, %%r10;" |
324 | " movq %%r10, 16(%2);" |
325 | " mulxq 16(%1), %%rbx, %%r13;" |
326 | " adox %%r11, %%rbx;" |
327 | " adcx %%r14, %%rbx;" |
328 | " mov $0, %%r8;" |
329 | " mulxq 24(%1), %%r14, %%rdx;" |
330 | " adox %%r13, %%r14;" |
331 | " adcx %%rax, %%r14;" |
332 | " mov $0, %%rax;" |
333 | " adox %%rdx, %%rax;" |
334 | " adcx %%r8, %%rax;" |
335 | |
336 | /* Compute src1[2] * src2 */ |
337 | " movq 16(%0), %%rdx;" |
338 | " mulxq 0(%1), %%r8, %%r9;" |
339 | " xor %%r10d, %%r10d;" |
340 | " adcxq 16(%2), %%r8;" |
341 | " movq %%r8, 16(%2);" |
342 | " mulxq 8(%1), %%r10, %%r11;" |
343 | " adox %%r9, %%r10;" |
344 | " adcx %%rbx, %%r10;" |
345 | " movq %%r10, 24(%2);" |
346 | " mulxq 16(%1), %%rbx, %%r13;" |
347 | " adox %%r11, %%rbx;" |
348 | " adcx %%r14, %%rbx;" |
349 | " mov $0, %%r8;" |
350 | " mulxq 24(%1), %%r14, %%rdx;" |
351 | " adox %%r13, %%r14;" |
352 | " adcx %%rax, %%r14;" |
353 | " mov $0, %%rax;" |
354 | " adox %%rdx, %%rax;" |
355 | " adcx %%r8, %%rax;" |
356 | |
357 | /* Compute src1[3] * src2 */ |
358 | " movq 24(%0), %%rdx;" |
359 | " mulxq 0(%1), %%r8, %%r9;" |
360 | " xor %%r10d, %%r10d;" |
361 | " adcxq 24(%2), %%r8;" |
362 | " movq %%r8, 24(%2);" |
363 | " mulxq 8(%1), %%r10, %%r11;" |
364 | " adox %%r9, %%r10;" |
365 | " adcx %%rbx, %%r10;" |
366 | " movq %%r10, 32(%2);" |
367 | " mulxq 16(%1), %%rbx, %%r13;" |
368 | " adox %%r11, %%rbx;" |
369 | " adcx %%r14, %%rbx;" |
370 | " movq %%rbx, 40(%2);" |
371 | " mov $0, %%r8;" |
372 | " mulxq 24(%1), %%r14, %%rdx;" |
373 | " adox %%r13, %%r14;" |
374 | " adcx %%rax, %%r14;" |
375 | " movq %%r14, 48(%2);" |
376 | " mov $0, %%rax;" |
377 | " adox %%rdx, %%rax;" |
378 | " adcx %%r8, %%rax;" |
379 | " movq %%rax, 56(%2);" |
380 | |
381 | /* Compute the raw multiplication tmp[1] <- f1[1] * f2[1] */ |
382 | |
383 | /* Compute src1[0] * src2 */ |
384 | " movq 32(%0), %%rdx;" |
385 | " mulxq 32(%1), %%r8, %%r9;" |
386 | " xor %%r10d, %%r10d;" |
387 | " movq %%r8, 64(%2);" |
388 | " mulxq 40(%1), %%r10, %%r11;" |
389 | " adox %%r9, %%r10;" |
390 | " movq %%r10, 72(%2);" |
391 | " mulxq 48(%1), %%rbx, %%r13;" |
392 | " adox %%r11, %%rbx;" |
393 | " mulxq 56(%1), %%r14, %%rdx;" |
394 | " adox %%r13, %%r14;" |
395 | " mov $0, %%rax;" |
396 | " adox %%rdx, %%rax;" |
397 | |
398 | /* Compute src1[1] * src2 */ |
399 | " movq 40(%0), %%rdx;" |
400 | " mulxq 32(%1), %%r8, %%r9;" |
401 | " xor %%r10d, %%r10d;" |
402 | " adcxq 72(%2), %%r8;" |
403 | " movq %%r8, 72(%2);" |
404 | " mulxq 40(%1), %%r10, %%r11;" |
405 | " adox %%r9, %%r10;" |
406 | " adcx %%rbx, %%r10;" |
407 | " movq %%r10, 80(%2);" |
408 | " mulxq 48(%1), %%rbx, %%r13;" |
409 | " adox %%r11, %%rbx;" |
410 | " adcx %%r14, %%rbx;" |
411 | " mov $0, %%r8;" |
412 | " mulxq 56(%1), %%r14, %%rdx;" |
413 | " adox %%r13, %%r14;" |
414 | " adcx %%rax, %%r14;" |
415 | " mov $0, %%rax;" |
416 | " adox %%rdx, %%rax;" |
417 | " adcx %%r8, %%rax;" |
418 | |
419 | /* Compute src1[2] * src2 */ |
420 | " movq 48(%0), %%rdx;" |
421 | " mulxq 32(%1), %%r8, %%r9;" |
422 | " xor %%r10d, %%r10d;" |
423 | " adcxq 80(%2), %%r8;" |
424 | " movq %%r8, 80(%2);" |
425 | " mulxq 40(%1), %%r10, %%r11;" |
426 | " adox %%r9, %%r10;" |
427 | " adcx %%rbx, %%r10;" |
428 | " movq %%r10, 88(%2);" |
429 | " mulxq 48(%1), %%rbx, %%r13;" |
430 | " adox %%r11, %%rbx;" |
431 | " adcx %%r14, %%rbx;" |
432 | " mov $0, %%r8;" |
433 | " mulxq 56(%1), %%r14, %%rdx;" |
434 | " adox %%r13, %%r14;" |
435 | " adcx %%rax, %%r14;" |
436 | " mov $0, %%rax;" |
437 | " adox %%rdx, %%rax;" |
438 | " adcx %%r8, %%rax;" |
439 | |
440 | /* Compute src1[3] * src2 */ |
441 | " movq 56(%0), %%rdx;" |
442 | " mulxq 32(%1), %%r8, %%r9;" |
443 | " xor %%r10d, %%r10d;" |
444 | " adcxq 88(%2), %%r8;" |
445 | " movq %%r8, 88(%2);" |
446 | " mulxq 40(%1), %%r10, %%r11;" |
447 | " adox %%r9, %%r10;" |
448 | " adcx %%rbx, %%r10;" |
449 | " movq %%r10, 96(%2);" |
450 | " mulxq 48(%1), %%rbx, %%r13;" |
451 | " adox %%r11, %%rbx;" |
452 | " adcx %%r14, %%rbx;" |
453 | " movq %%rbx, 104(%2);" |
454 | " mov $0, %%r8;" |
455 | " mulxq 56(%1), %%r14, %%rdx;" |
456 | " adox %%r13, %%r14;" |
457 | " adcx %%rax, %%r14;" |
458 | " movq %%r14, 112(%2);" |
459 | " mov $0, %%rax;" |
460 | " adox %%rdx, %%rax;" |
461 | " adcx %%r8, %%rax;" |
462 | " movq %%rax, 120(%2);" |
463 | |
464 | /* Line up pointers */ |
465 | " mov %2, %0;" |
466 | " mov %3, %2;" |
467 | |
468 | /* Wrap the results back into the field */ |
469 | |
470 | /* Step 1: Compute dst + carry == tmp_hi * 38 + tmp_lo */ |
471 | " mov $38, %%rdx;" |
472 | " mulxq 32(%0), %%r8, %%r13;" |
473 | " xor %k1, %k1;" |
474 | " adoxq 0(%0), %%r8;" |
475 | " mulxq 40(%0), %%r9, %%rbx;" |
476 | " adcx %%r13, %%r9;" |
477 | " adoxq 8(%0), %%r9;" |
478 | " mulxq 48(%0), %%r10, %%r13;" |
479 | " adcx %%rbx, %%r10;" |
480 | " adoxq 16(%0), %%r10;" |
481 | " mulxq 56(%0), %%r11, %%rax;" |
482 | " adcx %%r13, %%r11;" |
483 | " adoxq 24(%0), %%r11;" |
484 | " adcx %1, %%rax;" |
485 | " adox %1, %%rax;" |
486 | " imul %%rdx, %%rax;" |
487 | |
488 | /* Step 2: Fold the carry back into dst */ |
489 | " add %%rax, %%r8;" |
490 | " adcx %1, %%r9;" |
491 | " movq %%r9, 8(%2);" |
492 | " adcx %1, %%r10;" |
493 | " movq %%r10, 16(%2);" |
494 | " adcx %1, %%r11;" |
495 | " movq %%r11, 24(%2);" |
496 | |
497 | /* Step 3: Fold the carry bit back in; guaranteed not to carry at this point */ |
498 | " mov $0, %%rax;" |
499 | " cmovc %%rdx, %%rax;" |
500 | " add %%rax, %%r8;" |
501 | " movq %%r8, 0(%2);" |
502 | |
503 | /* Step 1: Compute dst + carry == tmp_hi * 38 + tmp_lo */ |
504 | " mov $38, %%rdx;" |
505 | " mulxq 96(%0), %%r8, %%r13;" |
506 | " xor %k1, %k1;" |
507 | " adoxq 64(%0), %%r8;" |
508 | " mulxq 104(%0), %%r9, %%rbx;" |
509 | " adcx %%r13, %%r9;" |
510 | " adoxq 72(%0), %%r9;" |
511 | " mulxq 112(%0), %%r10, %%r13;" |
512 | " adcx %%rbx, %%r10;" |
513 | " adoxq 80(%0), %%r10;" |
514 | " mulxq 120(%0), %%r11, %%rax;" |
515 | " adcx %%r13, %%r11;" |
516 | " adoxq 88(%0), %%r11;" |
517 | " adcx %1, %%rax;" |
518 | " adox %1, %%rax;" |
519 | " imul %%rdx, %%rax;" |
520 | |
521 | /* Step 2: Fold the carry back into dst */ |
522 | " add %%rax, %%r8;" |
523 | " adcx %1, %%r9;" |
524 | " movq %%r9, 40(%2);" |
525 | " adcx %1, %%r10;" |
526 | " movq %%r10, 48(%2);" |
527 | " adcx %1, %%r11;" |
528 | " movq %%r11, 56(%2);" |
529 | |
530 | /* Step 3: Fold the carry bit back in; guaranteed not to carry at this point */ |
531 | " mov $0, %%rax;" |
532 | " cmovc %%rdx, %%rax;" |
533 | " add %%rax, %%r8;" |
534 | " movq %%r8, 32(%2);" |
535 | : "+&r" (f1), "+&r" (f2), "+&r" (tmp) |
536 | : "r" (out) |
537 | : "%rax" , "%rbx" , "%rdx" , "%r8" , "%r9" , "%r10" , "%r11" , "%r13" , |
538 | "%r14" , "memory" , "cc" ); |
539 | } |
540 | |
541 | /* Computes the field multiplication of four-element f1 with value in f2 |
542 | * Requires f2 to be smaller than 2^17 */ |
543 | static inline void fmul_scalar(u64 *out, const u64 *f1, u64 f2) |
544 | { |
545 | register u64 f2_r asm("rdx" ) = f2; |
546 | |
547 | asm volatile( |
548 | /* Compute the raw multiplication of f1*f2 */ |
549 | " mulxq 0(%2), %%r8, %%rcx;" /* f1[0]*f2 */ |
550 | " mulxq 8(%2), %%r9, %%rbx;" /* f1[1]*f2 */ |
551 | " add %%rcx, %%r9;" |
552 | " mov $0, %%rcx;" |
553 | " mulxq 16(%2), %%r10, %%r13;" /* f1[2]*f2 */ |
554 | " adcx %%rbx, %%r10;" |
555 | " mulxq 24(%2), %%r11, %%rax;" /* f1[3]*f2 */ |
556 | " adcx %%r13, %%r11;" |
557 | " adcx %%rcx, %%rax;" |
558 | |
559 | /* Wrap the result back into the field */ |
560 | |
561 | /* Step 1: Compute carry*38 */ |
562 | " mov $38, %%rdx;" |
563 | " imul %%rdx, %%rax;" |
564 | |
565 | /* Step 2: Fold the carry back into dst */ |
566 | " add %%rax, %%r8;" |
567 | " adcx %%rcx, %%r9;" |
568 | " movq %%r9, 8(%1);" |
569 | " adcx %%rcx, %%r10;" |
570 | " movq %%r10, 16(%1);" |
571 | " adcx %%rcx, %%r11;" |
572 | " movq %%r11, 24(%1);" |
573 | |
574 | /* Step 3: Fold the carry bit back in; guaranteed not to carry at this point */ |
575 | " mov $0, %%rax;" |
576 | " cmovc %%rdx, %%rax;" |
577 | " add %%rax, %%r8;" |
578 | " movq %%r8, 0(%1);" |
579 | : "+&r" (f2_r) |
580 | : "r" (out), "r" (f1) |
581 | : "%rax" , "%rbx" , "%rcx" , "%r8" , "%r9" , "%r10" , "%r11" , "%r13" , |
582 | "memory" , "cc" ); |
583 | } |
584 | |
585 | /* Computes p1 <- bit ? p2 : p1 in constant time */ |
586 | static inline void cswap2(u64 bit, const u64 *p1, const u64 *p2) |
587 | { |
588 | asm volatile( |
589 | /* Transfer bit into CF flag */ |
590 | " add $18446744073709551615, %0;" |
591 | |
592 | /* cswap p1[0], p2[0] */ |
593 | " movq 0(%1), %%r8;" |
594 | " movq 0(%2), %%r9;" |
595 | " mov %%r8, %%r10;" |
596 | " cmovc %%r9, %%r8;" |
597 | " cmovc %%r10, %%r9;" |
598 | " movq %%r8, 0(%1);" |
599 | " movq %%r9, 0(%2);" |
600 | |
601 | /* cswap p1[1], p2[1] */ |
602 | " movq 8(%1), %%r8;" |
603 | " movq 8(%2), %%r9;" |
604 | " mov %%r8, %%r10;" |
605 | " cmovc %%r9, %%r8;" |
606 | " cmovc %%r10, %%r9;" |
607 | " movq %%r8, 8(%1);" |
608 | " movq %%r9, 8(%2);" |
609 | |
610 | /* cswap p1[2], p2[2] */ |
611 | " movq 16(%1), %%r8;" |
612 | " movq 16(%2), %%r9;" |
613 | " mov %%r8, %%r10;" |
614 | " cmovc %%r9, %%r8;" |
615 | " cmovc %%r10, %%r9;" |
616 | " movq %%r8, 16(%1);" |
617 | " movq %%r9, 16(%2);" |
618 | |
619 | /* cswap p1[3], p2[3] */ |
620 | " movq 24(%1), %%r8;" |
621 | " movq 24(%2), %%r9;" |
622 | " mov %%r8, %%r10;" |
623 | " cmovc %%r9, %%r8;" |
624 | " cmovc %%r10, %%r9;" |
625 | " movq %%r8, 24(%1);" |
626 | " movq %%r9, 24(%2);" |
627 | |
628 | /* cswap p1[4], p2[4] */ |
629 | " movq 32(%1), %%r8;" |
630 | " movq 32(%2), %%r9;" |
631 | " mov %%r8, %%r10;" |
632 | " cmovc %%r9, %%r8;" |
633 | " cmovc %%r10, %%r9;" |
634 | " movq %%r8, 32(%1);" |
635 | " movq %%r9, 32(%2);" |
636 | |
637 | /* cswap p1[5], p2[5] */ |
638 | " movq 40(%1), %%r8;" |
639 | " movq 40(%2), %%r9;" |
640 | " mov %%r8, %%r10;" |
641 | " cmovc %%r9, %%r8;" |
642 | " cmovc %%r10, %%r9;" |
643 | " movq %%r8, 40(%1);" |
644 | " movq %%r9, 40(%2);" |
645 | |
646 | /* cswap p1[6], p2[6] */ |
647 | " movq 48(%1), %%r8;" |
648 | " movq 48(%2), %%r9;" |
649 | " mov %%r8, %%r10;" |
650 | " cmovc %%r9, %%r8;" |
651 | " cmovc %%r10, %%r9;" |
652 | " movq %%r8, 48(%1);" |
653 | " movq %%r9, 48(%2);" |
654 | |
655 | /* cswap p1[7], p2[7] */ |
656 | " movq 56(%1), %%r8;" |
657 | " movq 56(%2), %%r9;" |
658 | " mov %%r8, %%r10;" |
659 | " cmovc %%r9, %%r8;" |
660 | " cmovc %%r10, %%r9;" |
661 | " movq %%r8, 56(%1);" |
662 | " movq %%r9, 56(%2);" |
663 | : "+&r" (bit) |
664 | : "r" (p1), "r" (p2) |
665 | : "%r8" , "%r9" , "%r10" , "memory" , "cc" ); |
666 | } |
667 | |
668 | /* Computes the square of a field element: out <- f * f |
669 | * Uses the 8-element buffer tmp for intermediate results */ |
670 | static inline void fsqr(u64 *out, const u64 *f, u64 *tmp) |
671 | { |
672 | asm volatile( |
673 | /* Compute the raw multiplication: tmp <- f * f */ |
674 | |
675 | /* Step 1: Compute all partial products */ |
676 | " movq 0(%0), %%rdx;" /* f[0] */ |
677 | " mulxq 8(%0), %%r8, %%r14;" |
678 | " xor %%r15d, %%r15d;" /* f[1]*f[0] */ |
679 | " mulxq 16(%0), %%r9, %%r10;" |
680 | " adcx %%r14, %%r9;" /* f[2]*f[0] */ |
681 | " mulxq 24(%0), %%rax, %%rcx;" |
682 | " adcx %%rax, %%r10;" /* f[3]*f[0] */ |
683 | " movq 24(%0), %%rdx;" /* f[3] */ |
684 | " mulxq 8(%0), %%r11, %%rbx;" |
685 | " adcx %%rcx, %%r11;" /* f[1]*f[3] */ |
686 | " mulxq 16(%0), %%rax, %%r13;" |
687 | " adcx %%rax, %%rbx;" /* f[2]*f[3] */ |
688 | " movq 8(%0), %%rdx;" |
689 | " adcx %%r15, %%r13;" /* f1 */ |
690 | " mulxq 16(%0), %%rax, %%rcx;" |
691 | " mov $0, %%r14;" /* f[2]*f[1] */ |
692 | |
693 | /* Step 2: Compute two parallel carry chains */ |
694 | " xor %%r15d, %%r15d;" |
695 | " adox %%rax, %%r10;" |
696 | " adcx %%r8, %%r8;" |
697 | " adox %%rcx, %%r11;" |
698 | " adcx %%r9, %%r9;" |
699 | " adox %%r15, %%rbx;" |
700 | " adcx %%r10, %%r10;" |
701 | " adox %%r15, %%r13;" |
702 | " adcx %%r11, %%r11;" |
703 | " adox %%r15, %%r14;" |
704 | " adcx %%rbx, %%rbx;" |
705 | " adcx %%r13, %%r13;" |
706 | " adcx %%r14, %%r14;" |
707 | |
708 | /* Step 3: Compute intermediate squares */ |
709 | " movq 0(%0), %%rdx;" |
710 | " mulx %%rdx, %%rax, %%rcx;" /* f[0]^2 */ |
711 | " movq %%rax, 0(%1);" |
712 | " add %%rcx, %%r8;" |
713 | " movq %%r8, 8(%1);" |
714 | " movq 8(%0), %%rdx;" |
715 | " mulx %%rdx, %%rax, %%rcx;" /* f[1]^2 */ |
716 | " adcx %%rax, %%r9;" |
717 | " movq %%r9, 16(%1);" |
718 | " adcx %%rcx, %%r10;" |
719 | " movq %%r10, 24(%1);" |
720 | " movq 16(%0), %%rdx;" |
721 | " mulx %%rdx, %%rax, %%rcx;" /* f[2]^2 */ |
722 | " adcx %%rax, %%r11;" |
723 | " movq %%r11, 32(%1);" |
724 | " adcx %%rcx, %%rbx;" |
725 | " movq %%rbx, 40(%1);" |
726 | " movq 24(%0), %%rdx;" |
727 | " mulx %%rdx, %%rax, %%rcx;" /* f[3]^2 */ |
728 | " adcx %%rax, %%r13;" |
729 | " movq %%r13, 48(%1);" |
730 | " adcx %%rcx, %%r14;" |
731 | " movq %%r14, 56(%1);" |
732 | |
733 | /* Line up pointers */ |
734 | " mov %1, %0;" |
735 | " mov %2, %1;" |
736 | |
737 | /* Wrap the result back into the field */ |
738 | |
739 | /* Step 1: Compute dst + carry == tmp_hi * 38 + tmp_lo */ |
740 | " mov $38, %%rdx;" |
741 | " mulxq 32(%0), %%r8, %%r13;" |
742 | " xor %%ecx, %%ecx;" |
743 | " adoxq 0(%0), %%r8;" |
744 | " mulxq 40(%0), %%r9, %%rbx;" |
745 | " adcx %%r13, %%r9;" |
746 | " adoxq 8(%0), %%r9;" |
747 | " mulxq 48(%0), %%r10, %%r13;" |
748 | " adcx %%rbx, %%r10;" |
749 | " adoxq 16(%0), %%r10;" |
750 | " mulxq 56(%0), %%r11, %%rax;" |
751 | " adcx %%r13, %%r11;" |
752 | " adoxq 24(%0), %%r11;" |
753 | " adcx %%rcx, %%rax;" |
754 | " adox %%rcx, %%rax;" |
755 | " imul %%rdx, %%rax;" |
756 | |
757 | /* Step 2: Fold the carry back into dst */ |
758 | " add %%rax, %%r8;" |
759 | " adcx %%rcx, %%r9;" |
760 | " movq %%r9, 8(%1);" |
761 | " adcx %%rcx, %%r10;" |
762 | " movq %%r10, 16(%1);" |
763 | " adcx %%rcx, %%r11;" |
764 | " movq %%r11, 24(%1);" |
765 | |
766 | /* Step 3: Fold the carry bit back in; guaranteed not to carry at this point */ |
767 | " mov $0, %%rax;" |
768 | " cmovc %%rdx, %%rax;" |
769 | " add %%rax, %%r8;" |
770 | " movq %%r8, 0(%1);" |
771 | : "+&r" (f), "+&r" (tmp) |
772 | : "r" (out) |
773 | : "%rax" , "%rbx" , "%rcx" , "%rdx" , "%r8" , "%r9" , "%r10" , "%r11" , |
774 | "%r13" , "%r14" , "%r15" , "memory" , "cc" ); |
775 | } |
776 | |
777 | /* Computes two field squarings: |
778 | * out[0] <- f[0] * f[0] |
779 | * out[1] <- f[1] * f[1] |
780 | * Uses the 16-element buffer tmp for intermediate results */ |
781 | static inline void fsqr2(u64 *out, const u64 *f, u64 *tmp) |
782 | { |
783 | asm volatile( |
784 | /* Step 1: Compute all partial products */ |
785 | " movq 0(%0), %%rdx;" /* f[0] */ |
786 | " mulxq 8(%0), %%r8, %%r14;" |
787 | " xor %%r15d, %%r15d;" /* f[1]*f[0] */ |
788 | " mulxq 16(%0), %%r9, %%r10;" |
789 | " adcx %%r14, %%r9;" /* f[2]*f[0] */ |
790 | " mulxq 24(%0), %%rax, %%rcx;" |
791 | " adcx %%rax, %%r10;" /* f[3]*f[0] */ |
792 | " movq 24(%0), %%rdx;" /* f[3] */ |
793 | " mulxq 8(%0), %%r11, %%rbx;" |
794 | " adcx %%rcx, %%r11;" /* f[1]*f[3] */ |
795 | " mulxq 16(%0), %%rax, %%r13;" |
796 | " adcx %%rax, %%rbx;" /* f[2]*f[3] */ |
797 | " movq 8(%0), %%rdx;" |
798 | " adcx %%r15, %%r13;" /* f1 */ |
799 | " mulxq 16(%0), %%rax, %%rcx;" |
800 | " mov $0, %%r14;" /* f[2]*f[1] */ |
801 | |
802 | /* Step 2: Compute two parallel carry chains */ |
803 | " xor %%r15d, %%r15d;" |
804 | " adox %%rax, %%r10;" |
805 | " adcx %%r8, %%r8;" |
806 | " adox %%rcx, %%r11;" |
807 | " adcx %%r9, %%r9;" |
808 | " adox %%r15, %%rbx;" |
809 | " adcx %%r10, %%r10;" |
810 | " adox %%r15, %%r13;" |
811 | " adcx %%r11, %%r11;" |
812 | " adox %%r15, %%r14;" |
813 | " adcx %%rbx, %%rbx;" |
814 | " adcx %%r13, %%r13;" |
815 | " adcx %%r14, %%r14;" |
816 | |
817 | /* Step 3: Compute intermediate squares */ |
818 | " movq 0(%0), %%rdx;" |
819 | " mulx %%rdx, %%rax, %%rcx;" /* f[0]^2 */ |
820 | " movq %%rax, 0(%1);" |
821 | " add %%rcx, %%r8;" |
822 | " movq %%r8, 8(%1);" |
823 | " movq 8(%0), %%rdx;" |
824 | " mulx %%rdx, %%rax, %%rcx;" /* f[1]^2 */ |
825 | " adcx %%rax, %%r9;" |
826 | " movq %%r9, 16(%1);" |
827 | " adcx %%rcx, %%r10;" |
828 | " movq %%r10, 24(%1);" |
829 | " movq 16(%0), %%rdx;" |
830 | " mulx %%rdx, %%rax, %%rcx;" /* f[2]^2 */ |
831 | " adcx %%rax, %%r11;" |
832 | " movq %%r11, 32(%1);" |
833 | " adcx %%rcx, %%rbx;" |
834 | " movq %%rbx, 40(%1);" |
835 | " movq 24(%0), %%rdx;" |
836 | " mulx %%rdx, %%rax, %%rcx;" /* f[3]^2 */ |
837 | " adcx %%rax, %%r13;" |
838 | " movq %%r13, 48(%1);" |
839 | " adcx %%rcx, %%r14;" |
840 | " movq %%r14, 56(%1);" |
841 | |
842 | /* Step 1: Compute all partial products */ |
843 | " movq 32(%0), %%rdx;" /* f[0] */ |
844 | " mulxq 40(%0), %%r8, %%r14;" |
845 | " xor %%r15d, %%r15d;" /* f[1]*f[0] */ |
846 | " mulxq 48(%0), %%r9, %%r10;" |
847 | " adcx %%r14, %%r9;" /* f[2]*f[0] */ |
848 | " mulxq 56(%0), %%rax, %%rcx;" |
849 | " adcx %%rax, %%r10;" /* f[3]*f[0] */ |
850 | " movq 56(%0), %%rdx;" /* f[3] */ |
851 | " mulxq 40(%0), %%r11, %%rbx;" |
852 | " adcx %%rcx, %%r11;" /* f[1]*f[3] */ |
853 | " mulxq 48(%0), %%rax, %%r13;" |
854 | " adcx %%rax, %%rbx;" /* f[2]*f[3] */ |
855 | " movq 40(%0), %%rdx;" |
856 | " adcx %%r15, %%r13;" /* f1 */ |
857 | " mulxq 48(%0), %%rax, %%rcx;" |
858 | " mov $0, %%r14;" /* f[2]*f[1] */ |
859 | |
860 | /* Step 2: Compute two parallel carry chains */ |
861 | " xor %%r15d, %%r15d;" |
862 | " adox %%rax, %%r10;" |
863 | " adcx %%r8, %%r8;" |
864 | " adox %%rcx, %%r11;" |
865 | " adcx %%r9, %%r9;" |
866 | " adox %%r15, %%rbx;" |
867 | " adcx %%r10, %%r10;" |
868 | " adox %%r15, %%r13;" |
869 | " adcx %%r11, %%r11;" |
870 | " adox %%r15, %%r14;" |
871 | " adcx %%rbx, %%rbx;" |
872 | " adcx %%r13, %%r13;" |
873 | " adcx %%r14, %%r14;" |
874 | |
875 | /* Step 3: Compute intermediate squares */ |
876 | " movq 32(%0), %%rdx;" |
877 | " mulx %%rdx, %%rax, %%rcx;" /* f[0]^2 */ |
878 | " movq %%rax, 64(%1);" |
879 | " add %%rcx, %%r8;" |
880 | " movq %%r8, 72(%1);" |
881 | " movq 40(%0), %%rdx;" |
882 | " mulx %%rdx, %%rax, %%rcx;" /* f[1]^2 */ |
883 | " adcx %%rax, %%r9;" |
884 | " movq %%r9, 80(%1);" |
885 | " adcx %%rcx, %%r10;" |
886 | " movq %%r10, 88(%1);" |
887 | " movq 48(%0), %%rdx;" |
888 | " mulx %%rdx, %%rax, %%rcx;" /* f[2]^2 */ |
889 | " adcx %%rax, %%r11;" |
890 | " movq %%r11, 96(%1);" |
891 | " adcx %%rcx, %%rbx;" |
892 | " movq %%rbx, 104(%1);" |
893 | " movq 56(%0), %%rdx;" |
894 | " mulx %%rdx, %%rax, %%rcx;" /* f[3]^2 */ |
895 | " adcx %%rax, %%r13;" |
896 | " movq %%r13, 112(%1);" |
897 | " adcx %%rcx, %%r14;" |
898 | " movq %%r14, 120(%1);" |
899 | |
900 | /* Line up pointers */ |
901 | " mov %1, %0;" |
902 | " mov %2, %1;" |
903 | |
904 | /* Step 1: Compute dst + carry == tmp_hi * 38 + tmp_lo */ |
905 | " mov $38, %%rdx;" |
906 | " mulxq 32(%0), %%r8, %%r13;" |
907 | " xor %%ecx, %%ecx;" |
908 | " adoxq 0(%0), %%r8;" |
909 | " mulxq 40(%0), %%r9, %%rbx;" |
910 | " adcx %%r13, %%r9;" |
911 | " adoxq 8(%0), %%r9;" |
912 | " mulxq 48(%0), %%r10, %%r13;" |
913 | " adcx %%rbx, %%r10;" |
914 | " adoxq 16(%0), %%r10;" |
915 | " mulxq 56(%0), %%r11, %%rax;" |
916 | " adcx %%r13, %%r11;" |
917 | " adoxq 24(%0), %%r11;" |
918 | " adcx %%rcx, %%rax;" |
919 | " adox %%rcx, %%rax;" |
920 | " imul %%rdx, %%rax;" |
921 | |
922 | /* Step 2: Fold the carry back into dst */ |
923 | " add %%rax, %%r8;" |
924 | " adcx %%rcx, %%r9;" |
925 | " movq %%r9, 8(%1);" |
926 | " adcx %%rcx, %%r10;" |
927 | " movq %%r10, 16(%1);" |
928 | " adcx %%rcx, %%r11;" |
929 | " movq %%r11, 24(%1);" |
930 | |
931 | /* Step 3: Fold the carry bit back in; guaranteed not to carry at this point */ |
932 | " mov $0, %%rax;" |
933 | " cmovc %%rdx, %%rax;" |
934 | " add %%rax, %%r8;" |
935 | " movq %%r8, 0(%1);" |
936 | |
937 | /* Step 1: Compute dst + carry == tmp_hi * 38 + tmp_lo */ |
938 | " mov $38, %%rdx;" |
939 | " mulxq 96(%0), %%r8, %%r13;" |
940 | " xor %%ecx, %%ecx;" |
941 | " adoxq 64(%0), %%r8;" |
942 | " mulxq 104(%0), %%r9, %%rbx;" |
943 | " adcx %%r13, %%r9;" |
944 | " adoxq 72(%0), %%r9;" |
945 | " mulxq 112(%0), %%r10, %%r13;" |
946 | " adcx %%rbx, %%r10;" |
947 | " adoxq 80(%0), %%r10;" |
948 | " mulxq 120(%0), %%r11, %%rax;" |
949 | " adcx %%r13, %%r11;" |
950 | " adoxq 88(%0), %%r11;" |
951 | " adcx %%rcx, %%rax;" |
952 | " adox %%rcx, %%rax;" |
953 | " imul %%rdx, %%rax;" |
954 | |
955 | /* Step 2: Fold the carry back into dst */ |
956 | " add %%rax, %%r8;" |
957 | " adcx %%rcx, %%r9;" |
958 | " movq %%r9, 40(%1);" |
959 | " adcx %%rcx, %%r10;" |
960 | " movq %%r10, 48(%1);" |
961 | " adcx %%rcx, %%r11;" |
962 | " movq %%r11, 56(%1);" |
963 | |
964 | /* Step 3: Fold the carry bit back in; guaranteed not to carry at this point */ |
965 | " mov $0, %%rax;" |
966 | " cmovc %%rdx, %%rax;" |
967 | " add %%rax, %%r8;" |
968 | " movq %%r8, 32(%1);" |
969 | : "+&r" (f), "+&r" (tmp) |
970 | : "r" (out) |
971 | : "%rax" , "%rbx" , "%rcx" , "%rdx" , "%r8" , "%r9" , "%r10" , "%r11" , |
972 | "%r13" , "%r14" , "%r15" , "memory" , "cc" ); |
973 | } |
974 | |
975 | static void point_add_and_double(u64 *q, u64 *p01_tmp1, u64 *tmp2) |
976 | { |
977 | u64 *nq = p01_tmp1; |
978 | u64 *nq_p1 = p01_tmp1 + (u32)8U; |
979 | u64 *tmp1 = p01_tmp1 + (u32)16U; |
980 | u64 *x1 = q; |
981 | u64 *x2 = nq; |
982 | u64 *z2 = nq + (u32)4U; |
983 | u64 *z3 = nq_p1 + (u32)4U; |
984 | u64 *a = tmp1; |
985 | u64 *b = tmp1 + (u32)4U; |
986 | u64 *ab = tmp1; |
987 | u64 *dc = tmp1 + (u32)8U; |
988 | u64 *x3; |
989 | u64 *z31; |
990 | u64 *d0; |
991 | u64 *c0; |
992 | u64 *a1; |
993 | u64 *b1; |
994 | u64 *d; |
995 | u64 *c; |
996 | u64 *ab1; |
997 | u64 *dc1; |
998 | fadd(out: a, f1: x2, f2: z2); |
999 | fsub(out: b, f1: x2, f2: z2); |
1000 | x3 = nq_p1; |
1001 | z31 = nq_p1 + (u32)4U; |
1002 | d0 = dc; |
1003 | c0 = dc + (u32)4U; |
1004 | fadd(out: c0, f1: x3, f2: z31); |
1005 | fsub(out: d0, f1: x3, f2: z31); |
1006 | fmul2(out: dc, f1: dc, f2: ab, tmp: tmp2); |
1007 | fadd(out: x3, f1: d0, f2: c0); |
1008 | fsub(out: z31, f1: d0, f2: c0); |
1009 | a1 = tmp1; |
1010 | b1 = tmp1 + (u32)4U; |
1011 | d = tmp1 + (u32)8U; |
1012 | c = tmp1 + (u32)12U; |
1013 | ab1 = tmp1; |
1014 | dc1 = tmp1 + (u32)8U; |
1015 | fsqr2(out: dc1, f: ab1, tmp: tmp2); |
1016 | fsqr2(out: nq_p1, f: nq_p1, tmp: tmp2); |
1017 | a1[0U] = c[0U]; |
1018 | a1[1U] = c[1U]; |
1019 | a1[2U] = c[2U]; |
1020 | a1[3U] = c[3U]; |
1021 | fsub(out: c, f1: d, f2: c); |
1022 | fmul_scalar(out: b1, f1: c, f2: (u64)121665U); |
1023 | fadd(out: b1, f1: b1, f2: d); |
1024 | fmul2(out: nq, f1: dc1, f2: ab1, tmp: tmp2); |
1025 | fmul(out: z3, f1: z3, f2: x1, tmp: tmp2); |
1026 | } |
1027 | |
1028 | static void point_double(u64 *nq, u64 *tmp1, u64 *tmp2) |
1029 | { |
1030 | u64 *x2 = nq; |
1031 | u64 *z2 = nq + (u32)4U; |
1032 | u64 *a = tmp1; |
1033 | u64 *b = tmp1 + (u32)4U; |
1034 | u64 *d = tmp1 + (u32)8U; |
1035 | u64 *c = tmp1 + (u32)12U; |
1036 | u64 *ab = tmp1; |
1037 | u64 *dc = tmp1 + (u32)8U; |
1038 | fadd(out: a, f1: x2, f2: z2); |
1039 | fsub(out: b, f1: x2, f2: z2); |
1040 | fsqr2(out: dc, f: ab, tmp: tmp2); |
1041 | a[0U] = c[0U]; |
1042 | a[1U] = c[1U]; |
1043 | a[2U] = c[2U]; |
1044 | a[3U] = c[3U]; |
1045 | fsub(out: c, f1: d, f2: c); |
1046 | fmul_scalar(out: b, f1: c, f2: (u64)121665U); |
1047 | fadd(out: b, f1: b, f2: d); |
1048 | fmul2(out: nq, f1: dc, f2: ab, tmp: tmp2); |
1049 | } |
1050 | |
1051 | static void montgomery_ladder(u64 *out, const u8 *key, u64 *init1) |
1052 | { |
1053 | u64 tmp2[16U] = { 0U }; |
1054 | u64 p01_tmp1_swap[33U] = { 0U }; |
1055 | u64 *p0 = p01_tmp1_swap; |
1056 | u64 *p01 = p01_tmp1_swap; |
1057 | u64 *p03 = p01; |
1058 | u64 *p11 = p01 + (u32)8U; |
1059 | u64 *x0; |
1060 | u64 *z0; |
1061 | u64 *p01_tmp1; |
1062 | u64 *p01_tmp11; |
1063 | u64 *nq10; |
1064 | u64 *nq_p11; |
1065 | u64 *swap1; |
1066 | u64 sw0; |
1067 | u64 *nq1; |
1068 | u64 *tmp1; |
1069 | memcpy(p11, init1, (u32)8U * sizeof(init1[0U])); |
1070 | x0 = p03; |
1071 | z0 = p03 + (u32)4U; |
1072 | x0[0U] = (u64)1U; |
1073 | x0[1U] = (u64)0U; |
1074 | x0[2U] = (u64)0U; |
1075 | x0[3U] = (u64)0U; |
1076 | z0[0U] = (u64)0U; |
1077 | z0[1U] = (u64)0U; |
1078 | z0[2U] = (u64)0U; |
1079 | z0[3U] = (u64)0U; |
1080 | p01_tmp1 = p01_tmp1_swap; |
1081 | p01_tmp11 = p01_tmp1_swap; |
1082 | nq10 = p01_tmp1_swap; |
1083 | nq_p11 = p01_tmp1_swap + (u32)8U; |
1084 | swap1 = p01_tmp1_swap + (u32)32U; |
1085 | cswap2(bit: (u64)1U, p1: nq10, p2: nq_p11); |
1086 | point_add_and_double(q: init1, p01_tmp1: p01_tmp11, tmp2); |
1087 | swap1[0U] = (u64)1U; |
1088 | { |
1089 | u32 i; |
1090 | for (i = (u32)0U; i < (u32)251U; i = i + (u32)1U) { |
1091 | u64 *p01_tmp12 = p01_tmp1_swap; |
1092 | u64 *swap2 = p01_tmp1_swap + (u32)32U; |
1093 | u64 *nq2 = p01_tmp12; |
1094 | u64 *nq_p12 = p01_tmp12 + (u32)8U; |
1095 | u64 bit = (u64)(key[((u32)253U - i) / (u32)8U] >> ((u32)253U - i) % (u32)8U & (u8)1U); |
1096 | u64 sw = swap2[0U] ^ bit; |
1097 | cswap2(bit: sw, p1: nq2, p2: nq_p12); |
1098 | point_add_and_double(q: init1, p01_tmp1: p01_tmp12, tmp2); |
1099 | swap2[0U] = bit; |
1100 | } |
1101 | } |
1102 | sw0 = swap1[0U]; |
1103 | cswap2(bit: sw0, p1: nq10, p2: nq_p11); |
1104 | nq1 = p01_tmp1; |
1105 | tmp1 = p01_tmp1 + (u32)16U; |
1106 | point_double(nq: nq1, tmp1, tmp2); |
1107 | point_double(nq: nq1, tmp1, tmp2); |
1108 | point_double(nq: nq1, tmp1, tmp2); |
1109 | memcpy(out, p0, (u32)8U * sizeof(p0[0U])); |
1110 | |
1111 | memzero_explicit(s: tmp2, count: sizeof(tmp2)); |
1112 | memzero_explicit(s: p01_tmp1_swap, count: sizeof(p01_tmp1_swap)); |
1113 | } |
1114 | |
1115 | static void fsquare_times(u64 *o, const u64 *inp, u64 *tmp, u32 n1) |
1116 | { |
1117 | u32 i; |
1118 | fsqr(out: o, f: inp, tmp); |
1119 | for (i = (u32)0U; i < n1 - (u32)1U; i = i + (u32)1U) |
1120 | fsqr(out: o, f: o, tmp); |
1121 | } |
1122 | |
1123 | static void finv(u64 *o, const u64 *i, u64 *tmp) |
1124 | { |
1125 | u64 t1[16U] = { 0U }; |
1126 | u64 *a0 = t1; |
1127 | u64 *b = t1 + (u32)4U; |
1128 | u64 *c = t1 + (u32)8U; |
1129 | u64 *t00 = t1 + (u32)12U; |
1130 | u64 *tmp1 = tmp; |
1131 | u64 *a; |
1132 | u64 *t0; |
1133 | fsquare_times(o: a0, inp: i, tmp: tmp1, n1: (u32)1U); |
1134 | fsquare_times(o: t00, inp: a0, tmp: tmp1, n1: (u32)2U); |
1135 | fmul(out: b, f1: t00, f2: i, tmp); |
1136 | fmul(out: a0, f1: b, f2: a0, tmp); |
1137 | fsquare_times(o: t00, inp: a0, tmp: tmp1, n1: (u32)1U); |
1138 | fmul(out: b, f1: t00, f2: b, tmp); |
1139 | fsquare_times(o: t00, inp: b, tmp: tmp1, n1: (u32)5U); |
1140 | fmul(out: b, f1: t00, f2: b, tmp); |
1141 | fsquare_times(o: t00, inp: b, tmp: tmp1, n1: (u32)10U); |
1142 | fmul(out: c, f1: t00, f2: b, tmp); |
1143 | fsquare_times(o: t00, inp: c, tmp: tmp1, n1: (u32)20U); |
1144 | fmul(out: t00, f1: t00, f2: c, tmp); |
1145 | fsquare_times(o: t00, inp: t00, tmp: tmp1, n1: (u32)10U); |
1146 | fmul(out: b, f1: t00, f2: b, tmp); |
1147 | fsquare_times(o: t00, inp: b, tmp: tmp1, n1: (u32)50U); |
1148 | fmul(out: c, f1: t00, f2: b, tmp); |
1149 | fsquare_times(o: t00, inp: c, tmp: tmp1, n1: (u32)100U); |
1150 | fmul(out: t00, f1: t00, f2: c, tmp); |
1151 | fsquare_times(o: t00, inp: t00, tmp: tmp1, n1: (u32)50U); |
1152 | fmul(out: t00, f1: t00, f2: b, tmp); |
1153 | fsquare_times(o: t00, inp: t00, tmp: tmp1, n1: (u32)5U); |
1154 | a = t1; |
1155 | t0 = t1 + (u32)12U; |
1156 | fmul(out: o, f1: t0, f2: a, tmp); |
1157 | } |
1158 | |
1159 | static void store_felem(u64 *b, u64 *f) |
1160 | { |
1161 | u64 f30 = f[3U]; |
1162 | u64 top_bit0 = f30 >> (u32)63U; |
1163 | u64 f31; |
1164 | u64 top_bit; |
1165 | u64 f0; |
1166 | u64 f1; |
1167 | u64 f2; |
1168 | u64 f3; |
1169 | u64 m0; |
1170 | u64 m1; |
1171 | u64 m2; |
1172 | u64 m3; |
1173 | u64 mask; |
1174 | u64 f0_; |
1175 | u64 f1_; |
1176 | u64 f2_; |
1177 | u64 f3_; |
1178 | u64 o0; |
1179 | u64 o1; |
1180 | u64 o2; |
1181 | u64 o3; |
1182 | f[3U] = f30 & (u64)0x7fffffffffffffffU; |
1183 | add_scalar(out: f, f1: f, f2: (u64)19U * top_bit0); |
1184 | f31 = f[3U]; |
1185 | top_bit = f31 >> (u32)63U; |
1186 | f[3U] = f31 & (u64)0x7fffffffffffffffU; |
1187 | add_scalar(out: f, f1: f, f2: (u64)19U * top_bit); |
1188 | f0 = f[0U]; |
1189 | f1 = f[1U]; |
1190 | f2 = f[2U]; |
1191 | f3 = f[3U]; |
1192 | m0 = gte_mask(a: f0, b: (u64)0xffffffffffffffedU); |
1193 | m1 = eq_mask(a: f1, b: (u64)0xffffffffffffffffU); |
1194 | m2 = eq_mask(a: f2, b: (u64)0xffffffffffffffffU); |
1195 | m3 = eq_mask(a: f3, b: (u64)0x7fffffffffffffffU); |
1196 | mask = ((m0 & m1) & m2) & m3; |
1197 | f0_ = f0 - (mask & (u64)0xffffffffffffffedU); |
1198 | f1_ = f1 - (mask & (u64)0xffffffffffffffffU); |
1199 | f2_ = f2 - (mask & (u64)0xffffffffffffffffU); |
1200 | f3_ = f3 - (mask & (u64)0x7fffffffffffffffU); |
1201 | o0 = f0_; |
1202 | o1 = f1_; |
1203 | o2 = f2_; |
1204 | o3 = f3_; |
1205 | b[0U] = o0; |
1206 | b[1U] = o1; |
1207 | b[2U] = o2; |
1208 | b[3U] = o3; |
1209 | } |
1210 | |
1211 | static void encode_point(u8 *o, const u64 *i) |
1212 | { |
1213 | const u64 *x = i; |
1214 | const u64 *z = i + (u32)4U; |
1215 | u64 tmp[4U] = { 0U }; |
1216 | u64 tmp_w[16U] = { 0U }; |
1217 | finv(o: tmp, i: z, tmp: tmp_w); |
1218 | fmul(out: tmp, f1: tmp, f2: x, tmp: tmp_w); |
1219 | store_felem(b: (u64 *)o, f: tmp); |
1220 | } |
1221 | |
1222 | static void curve25519_ever64(u8 *out, const u8 *priv, const u8 *pub) |
1223 | { |
1224 | u64 init1[8U] = { 0U }; |
1225 | u64 tmp[4U] = { 0U }; |
1226 | u64 tmp3; |
1227 | u64 *x; |
1228 | u64 *z; |
1229 | { |
1230 | u32 i; |
1231 | for (i = (u32)0U; i < (u32)4U; i = i + (u32)1U) { |
1232 | u64 *os = tmp; |
1233 | const u8 *bj = pub + i * (u32)8U; |
1234 | u64 u = *(u64 *)bj; |
1235 | u64 r = u; |
1236 | u64 x0 = r; |
1237 | os[i] = x0; |
1238 | } |
1239 | } |
1240 | tmp3 = tmp[3U]; |
1241 | tmp[3U] = tmp3 & (u64)0x7fffffffffffffffU; |
1242 | x = init1; |
1243 | z = init1 + (u32)4U; |
1244 | z[0U] = (u64)1U; |
1245 | z[1U] = (u64)0U; |
1246 | z[2U] = (u64)0U; |
1247 | z[3U] = (u64)0U; |
1248 | x[0U] = tmp[0U]; |
1249 | x[1U] = tmp[1U]; |
1250 | x[2U] = tmp[2U]; |
1251 | x[3U] = tmp[3U]; |
1252 | montgomery_ladder(out: init1, key: priv, init1); |
1253 | encode_point(o: out, i: init1); |
1254 | } |
1255 | |
1256 | /* The below constants were generated using this sage script: |
1257 | * |
1258 | * #!/usr/bin/env sage |
1259 | * import sys |
1260 | * from sage.all import * |
1261 | * def limbs(n): |
1262 | * n = int(n) |
1263 | * l = ((n >> 0) % 2^64, (n >> 64) % 2^64, (n >> 128) % 2^64, (n >> 192) % 2^64) |
1264 | * return "0x%016xULL, 0x%016xULL, 0x%016xULL, 0x%016xULL" % l |
1265 | * ec = EllipticCurve(GF(2^255 - 19), [0, 486662, 0, 1, 0]) |
1266 | * p_minus_s = (ec.lift_x(9) - ec.lift_x(1))[0] |
1267 | * print("static const u64 p_minus_s[] = { %s };\n" % limbs(p_minus_s)) |
1268 | * print("static const u64 table_ladder[] = {") |
1269 | * p = ec.lift_x(9) |
1270 | * for i in range(252): |
1271 | * l = (p[0] + p[2]) / (p[0] - p[2]) |
1272 | * print(("\t%s" + ("," if i != 251 else "")) % limbs(l)) |
1273 | * p = p * 2 |
1274 | * print("};") |
1275 | * |
1276 | */ |
1277 | |
1278 | static const u64 p_minus_s[] = { 0x816b1e0137d48290ULL, 0x440f6a51eb4d1207ULL, 0x52385f46dca2b71dULL, 0x215132111d8354cbULL }; |
1279 | |
1280 | static const u64 table_ladder[] = { |
1281 | 0xfffffffffffffff3ULL, 0xffffffffffffffffULL, 0xffffffffffffffffULL, 0x5fffffffffffffffULL, |
1282 | 0x6b8220f416aafe96ULL, 0x82ebeb2b4f566a34ULL, 0xd5a9a5b075a5950fULL, 0x5142b2cf4b2488f4ULL, |
1283 | 0x6aaebc750069680cULL, 0x89cf7820a0f99c41ULL, 0x2a58d9183b56d0f4ULL, 0x4b5aca80e36011a4ULL, |
1284 | 0x329132348c29745dULL, 0xf4a2e616e1642fd7ULL, 0x1e45bb03ff67bc34ULL, 0x306912d0f42a9b4aULL, |
1285 | 0xff886507e6af7154ULL, 0x04f50e13dfeec82fULL, 0xaa512fe82abab5ceULL, 0x174e251a68d5f222ULL, |
1286 | 0xcf96700d82028898ULL, 0x1743e3370a2c02c5ULL, 0x379eec98b4e86eaaULL, 0x0c59888a51e0482eULL, |
1287 | 0xfbcbf1d699b5d189ULL, 0xacaef0d58e9fdc84ULL, 0xc1c20d06231f7614ULL, 0x2938218da274f972ULL, |
1288 | 0xf6af49beff1d7f18ULL, 0xcc541c22387ac9c2ULL, 0x96fcc9ef4015c56bULL, 0x69c1627c690913a9ULL, |
1289 | 0x7a86fd2f4733db0eULL, 0xfdb8c4f29e087de9ULL, 0x095e4b1a8ea2a229ULL, 0x1ad7a7c829b37a79ULL, |
1290 | 0x342d89cad17ea0c0ULL, 0x67bedda6cced2051ULL, 0x19ca31bf2bb42f74ULL, 0x3df7b4c84980acbbULL, |
1291 | 0xa8c6444dc80ad883ULL, 0xb91e440366e3ab85ULL, 0xc215cda00164f6d8ULL, 0x3d867c6ef247e668ULL, |
1292 | 0xc7dd582bcc3e658cULL, 0xfd2c4748ee0e5528ULL, 0xa0fd9b95cc9f4f71ULL, 0x7529d871b0675ddfULL, |
1293 | 0xb8f568b42d3cbd78ULL, 0x1233011b91f3da82ULL, 0x2dce6ccd4a7c3b62ULL, 0x75e7fc8e9e498603ULL, |
1294 | 0x2f4f13f1fcd0b6ecULL, 0xf1a8ca1f29ff7a45ULL, 0xc249c1a72981e29bULL, 0x6ebe0dbb8c83b56aULL, |
1295 | 0x7114fa8d170bb222ULL, 0x65a2dcd5bf93935fULL, 0xbdc41f68b59c979aULL, 0x2f0eef79a2ce9289ULL, |
1296 | 0x42ecbf0c083c37ceULL, 0x2930bc09ec496322ULL, 0xf294b0c19cfeac0dULL, 0x3780aa4bedfabb80ULL, |
1297 | 0x56c17d3e7cead929ULL, 0xe7cb4beb2e5722c5ULL, 0x0ce931732dbfe15aULL, 0x41b883c7621052f8ULL, |
1298 | 0xdbf75ca0c3d25350ULL, 0x2936be086eb1e351ULL, 0xc936e03cb4a9b212ULL, 0x1d45bf82322225aaULL, |
1299 | 0xe81ab1036a024cc5ULL, 0xe212201c304c9a72ULL, 0xc5d73fba6832b1fcULL, 0x20ffdb5a4d839581ULL, |
1300 | 0xa283d367be5d0fadULL, 0x6c2b25ca8b164475ULL, 0x9d4935467caaf22eULL, 0x5166408eee85ff49ULL, |
1301 | 0x3c67baa2fab4e361ULL, 0xb3e433c67ef35cefULL, 0x5259729241159b1cULL, 0x6a621892d5b0ab33ULL, |
1302 | 0x20b74a387555cdcbULL, 0x532aa10e1208923fULL, 0xeaa17b7762281dd1ULL, 0x61ab3443f05c44bfULL, |
1303 | 0x257a6c422324def8ULL, 0x131c6c1017e3cf7fULL, 0x23758739f630a257ULL, 0x295a407a01a78580ULL, |
1304 | 0xf8c443246d5da8d9ULL, 0x19d775450c52fa5dULL, 0x2afcfc92731bf83dULL, 0x7d10c8e81b2b4700ULL, |
1305 | 0xc8e0271f70baa20bULL, 0x993748867ca63957ULL, 0x5412efb3cb7ed4bbULL, 0x3196d36173e62975ULL, |
1306 | 0xde5bcad141c7dffcULL, 0x47cc8cd2b395c848ULL, 0xa34cd942e11af3cbULL, 0x0256dbf2d04ecec2ULL, |
1307 | 0x875ab7e94b0e667fULL, 0xcad4dd83c0850d10ULL, 0x47f12e8f4e72c79fULL, 0x5f1a87bb8c85b19bULL, |
1308 | 0x7ae9d0b6437f51b8ULL, 0x12c7ce5518879065ULL, 0x2ade09fe5cf77aeeULL, 0x23a05a2f7d2c5627ULL, |
1309 | 0x5908e128f17c169aULL, 0xf77498dd8ad0852dULL, 0x74b4c4ceab102f64ULL, 0x183abadd10139845ULL, |
1310 | 0xb165ba8daa92aaacULL, 0xd5c5ef9599386705ULL, 0xbe2f8f0cf8fc40d1ULL, 0x2701e635ee204514ULL, |
1311 | 0x629fa80020156514ULL, 0xf223868764a8c1ceULL, 0x5b894fff0b3f060eULL, 0x60d9944cf708a3faULL, |
1312 | 0xaeea001a1c7a201fULL, 0xebf16a633ee2ce63ULL, 0x6f7709594c7a07e1ULL, 0x79b958150d0208cbULL, |
1313 | 0x24b55e5301d410e7ULL, 0xe3a34edff3fdc84dULL, 0xd88768e4904032d8ULL, 0x131384427b3aaeecULL, |
1314 | 0x8405e51286234f14ULL, 0x14dc4739adb4c529ULL, 0xb8a2b5b250634ffdULL, 0x2fe2a94ad8a7ff93ULL, |
1315 | 0xec5c57efe843faddULL, 0x2843ce40f0bb9918ULL, 0xa4b561d6cf3d6305ULL, 0x743629bde8fb777eULL, |
1316 | 0x343edd46bbaf738fULL, 0xed981828b101a651ULL, 0xa401760b882c797aULL, 0x1fc223e28dc88730ULL, |
1317 | 0x48604e91fc0fba0eULL, 0xb637f78f052c6fa4ULL, 0x91ccac3d09e9239cULL, 0x23f7eed4437a687cULL, |
1318 | 0x5173b1118d9bd800ULL, 0x29d641b63189d4a7ULL, 0xfdbf177988bbc586ULL, 0x2959894fcad81df5ULL, |
1319 | 0xaebc8ef3b4bbc899ULL, 0x4148995ab26992b9ULL, 0x24e20b0134f92cfbULL, 0x40d158894a05dee8ULL, |
1320 | 0x46b00b1185af76f6ULL, 0x26bac77873187a79ULL, 0x3dc0bf95ab8fff5fULL, 0x2a608bd8945524d7ULL, |
1321 | 0x26449588bd446302ULL, 0x7c4bc21c0388439cULL, 0x8e98a4f383bd11b2ULL, 0x26218d7bc9d876b9ULL, |
1322 | 0xe3081542997c178aULL, 0x3c2d29a86fb6606fULL, 0x5c217736fa279374ULL, 0x7dde05734afeb1faULL, |
1323 | 0x3bf10e3906d42babULL, 0xe4f7803e1980649cULL, 0xe6053bf89595bf7aULL, 0x394faf38da245530ULL, |
1324 | 0x7a8efb58896928f4ULL, 0xfbc778e9cc6a113cULL, 0x72670ce330af596fULL, 0x48f222a81d3d6cf7ULL, |
1325 | 0xf01fce410d72caa7ULL, 0x5a20ecc7213b5595ULL, 0x7bc21165c1fa1483ULL, 0x07f89ae31da8a741ULL, |
1326 | 0x05d2c2b4c6830ff9ULL, 0xd43e330fc6316293ULL, 0xa5a5590a96d3a904ULL, 0x705edb91a65333b6ULL, |
1327 | 0x048ee15e0bb9a5f7ULL, 0x3240cfca9e0aaf5dULL, 0x8f4b71ceedc4a40bULL, 0x621c0da3de544a6dULL, |
1328 | 0x92872836a08c4091ULL, 0xce8375b010c91445ULL, 0x8a72eb524f276394ULL, 0x2667fcfa7ec83635ULL, |
1329 | 0x7f4c173345e8752aULL, 0x061b47feee7079a5ULL, 0x25dd9afa9f86ff34ULL, 0x3780cef5425dc89cULL, |
1330 | 0x1a46035a513bb4e9ULL, 0x3e1ef379ac575adaULL, 0xc78c5f1c5fa24b50ULL, 0x321a967634fd9f22ULL, |
1331 | 0x946707b8826e27faULL, 0x3dca84d64c506fd0ULL, 0xc189218075e91436ULL, 0x6d9284169b3b8484ULL, |
1332 | 0x3a67e840383f2ddfULL, 0x33eec9a30c4f9b75ULL, 0x3ec7c86fa783ef47ULL, 0x26ec449fbac9fbc4ULL, |
1333 | 0x5c0f38cba09b9e7dULL, 0x81168cc762a3478cULL, 0x3e23b0d306fc121cULL, 0x5a238aa0a5efdcddULL, |
1334 | 0x1ba26121c4ea43ffULL, 0x36f8c77f7c8832b5ULL, 0x88fbea0b0adcf99aULL, 0x5ca9938ec25bebf9ULL, |
1335 | 0xd5436a5e51fccda0ULL, 0x1dbc4797c2cd893bULL, 0x19346a65d3224a08ULL, 0x0f5034e49b9af466ULL, |
1336 | 0xf23c3967a1e0b96eULL, 0xe58b08fa867a4d88ULL, 0xfb2fabc6a7341679ULL, 0x2a75381eb6026946ULL, |
1337 | 0xc80a3be4c19420acULL, 0x66b1f6c681f2b6dcULL, 0x7cf7036761e93388ULL, 0x25abbbd8a660a4c4ULL, |
1338 | 0x91ea12ba14fd5198ULL, 0x684950fc4a3cffa9ULL, 0xf826842130f5ad28ULL, 0x3ea988f75301a441ULL, |
1339 | 0xc978109a695f8c6fULL, 0x1746eb4a0530c3f3ULL, 0x444d6d77b4459995ULL, 0x75952b8c054e5cc7ULL, |
1340 | 0xa3703f7915f4d6aaULL, 0x66c346202f2647d8ULL, 0xd01469df811d644bULL, 0x77fea47d81a5d71fULL, |
1341 | 0xc5e9529ef57ca381ULL, 0x6eeeb4b9ce2f881aULL, 0xb6e91a28e8009bd6ULL, 0x4b80be3e9afc3fecULL, |
1342 | 0x7e3773c526aed2c5ULL, 0x1b4afcb453c9a49dULL, 0xa920bdd7baffb24dULL, 0x7c54699f122d400eULL, |
1343 | 0xef46c8e14fa94bc8ULL, 0xe0b074ce2952ed5eULL, 0xbea450e1dbd885d5ULL, 0x61b68649320f712cULL, |
1344 | 0x8a485f7309ccbdd1ULL, 0xbd06320d7d4d1a2dULL, 0x25232973322dbef4ULL, 0x445dc4758c17f770ULL, |
1345 | 0xdb0434177cc8933cULL, 0xed6fe82175ea059fULL, 0x1efebefdc053db34ULL, 0x4adbe867c65daf99ULL, |
1346 | 0x3acd71a2a90609dfULL, 0xe5e991856dd04050ULL, 0x1ec69b688157c23cULL, 0x697427f6885cfe4dULL, |
1347 | 0xd7be7b9b65e1a851ULL, 0xa03d28d522c536ddULL, 0x28399d658fd2b645ULL, 0x49e5b7e17c2641e1ULL, |
1348 | 0x6f8c3a98700457a4ULL, 0x5078f0a25ebb6778ULL, 0xd13c3ccbc382960fULL, 0x2e003258a7df84b1ULL, |
1349 | 0x8ad1f39be6296a1cULL, 0xc1eeaa652a5fbfb2ULL, 0x33ee0673fd26f3cbULL, 0x59256173a69d2cccULL, |
1350 | 0x41ea07aa4e18fc41ULL, 0xd9fc19527c87a51eULL, 0xbdaacb805831ca6fULL, 0x445b652dc916694fULL, |
1351 | 0xce92a3a7f2172315ULL, 0x1edc282de11b9964ULL, 0xa1823aafe04c314aULL, 0x790a2d94437cf586ULL, |
1352 | 0x71c447fb93f6e009ULL, 0x8922a56722845276ULL, 0xbf70903b204f5169ULL, 0x2f7a89891ba319feULL, |
1353 | 0x02a08eb577e2140cULL, 0xed9a4ed4427bdcf4ULL, 0x5253ec44e4323cd1ULL, 0x3e88363c14e9355bULL, |
1354 | 0xaa66c14277110b8cULL, 0x1ae0391610a23390ULL, 0x2030bd12c93fc2a2ULL, 0x3ee141579555c7abULL, |
1355 | 0x9214de3a6d6e7d41ULL, 0x3ccdd88607f17efeULL, 0x674f1288f8e11217ULL, 0x5682250f329f93d0ULL, |
1356 | 0x6cf00b136d2e396eULL, 0x6e4cf86f1014debfULL, 0x5930b1b5bfcc4e83ULL, 0x047069b48aba16b6ULL, |
1357 | 0x0d4ce4ab69b20793ULL, 0xb24db91a97d0fb9eULL, 0xcdfa50f54e00d01dULL, 0x221b1085368bddb5ULL, |
1358 | 0xe7e59468b1e3d8d2ULL, 0x53c56563bd122f93ULL, 0xeee8a903e0663f09ULL, 0x61efa662cbbe3d42ULL, |
1359 | 0x2cf8ddddde6eab2aULL, 0x9bf80ad51435f231ULL, 0x5deadacec9f04973ULL, 0x29275b5d41d29b27ULL, |
1360 | 0xcfde0f0895ebf14fULL, 0xb9aab96b054905a7ULL, 0xcae80dd9a1c420fdULL, 0x0a63bf2f1673bbc7ULL, |
1361 | 0x092f6e11958fbc8cULL, 0x672a81e804822fadULL, 0xcac8351560d52517ULL, 0x6f3f7722c8f192f8ULL, |
1362 | 0xf8ba90ccc2e894b7ULL, 0x2c7557a438ff9f0dULL, 0x894d1d855ae52359ULL, 0x68e122157b743d69ULL, |
1363 | 0xd87e5570cfb919f3ULL, 0x3f2cdecd95798db9ULL, 0x2121154710c0a2ceULL, 0x3c66a115246dc5b2ULL, |
1364 | 0xcbedc562294ecb72ULL, 0xba7143c36a280b16ULL, 0x9610c2efd4078b67ULL, 0x6144735d946a4b1eULL, |
1365 | 0x536f111ed75b3350ULL, 0x0211db8c2041d81bULL, 0xf93cb1000e10413cULL, 0x149dfd3c039e8876ULL, |
1366 | 0xd479dde46b63155bULL, 0xb66e15e93c837976ULL, 0xdafde43b1f13e038ULL, 0x5fafda1a2e4b0b35ULL, |
1367 | 0x3600bbdf17197581ULL, 0x3972050bbe3cd2c2ULL, 0x5938906dbdd5be86ULL, 0x34fce5e43f9b860fULL, |
1368 | 0x75a8a4cd42d14d02ULL, 0x828dabc53441df65ULL, 0x33dcabedd2e131d3ULL, 0x3ebad76fb814d25fULL, |
1369 | 0xd4906f566f70e10fULL, 0x5d12f7aa51690f5aULL, 0x45adb16e76cefcf2ULL, 0x01f768aead232999ULL, |
1370 | 0x2b6cc77b6248febdULL, 0x3cd30628ec3aaffdULL, 0xce1c0b80d4ef486aULL, 0x4c3bff2ea6f66c23ULL, |
1371 | 0x3f2ec4094aeaeb5fULL, 0x61b19b286e372ca7ULL, 0x5eefa966de2a701dULL, 0x23b20565de55e3efULL, |
1372 | 0xe301ca5279d58557ULL, 0x07b2d4ce27c2874fULL, 0xa532cd8a9dcf1d67ULL, 0x2a52fee23f2bff56ULL, |
1373 | 0x8624efb37cd8663dULL, 0xbbc7ac20ffbd7594ULL, 0x57b85e9c82d37445ULL, 0x7b3052cb86a6ec66ULL, |
1374 | 0x3482f0ad2525e91eULL, 0x2cb68043d28edca0ULL, 0xaf4f6d052e1b003aULL, 0x185f8c2529781b0aULL, |
1375 | 0xaa41de5bd80ce0d6ULL, 0x9407b2416853e9d6ULL, 0x563ec36e357f4c3aULL, 0x4cc4b8dd0e297bceULL, |
1376 | 0xa2fc1a52ffb8730eULL, 0x1811f16e67058e37ULL, 0x10f9a366cddf4ee1ULL, 0x72f4a0c4a0b9f099ULL, |
1377 | 0x8c16c06f663f4ea7ULL, 0x693b3af74e970fbaULL, 0x2102e7f1d69ec345ULL, 0x0ba53cbc968a8089ULL, |
1378 | 0xca3d9dc7fea15537ULL, 0x4c6824bb51536493ULL, 0xb9886314844006b1ULL, 0x40d2a72ab454cc60ULL, |
1379 | 0x5936a1b712570975ULL, 0x91b9d648debda657ULL, 0x3344094bb64330eaULL, 0x006ba10d12ee51d0ULL, |
1380 | 0x19228468f5de5d58ULL, 0x0eb12f4c38cc05b0ULL, 0xa1039f9dd5601990ULL, 0x4502d4ce4fff0e0bULL, |
1381 | 0xeb2054106837c189ULL, 0xd0f6544c6dd3b93cULL, 0x40727064c416d74fULL, 0x6e15c6114b502ef0ULL, |
1382 | 0x4df2a398cfb1a76bULL, 0x11256c7419f2f6b1ULL, 0x4a497962066e6043ULL, 0x705b3aab41355b44ULL, |
1383 | 0x365ef536d797b1d8ULL, 0x00076bd622ddf0dbULL, 0x3bbf33b0e0575a88ULL, 0x3777aa05c8e4ca4dULL, |
1384 | 0x392745c85578db5fULL, 0x6fda4149dbae5ae2ULL, 0xb1f0b00b8adc9867ULL, 0x09963437d36f1da3ULL, |
1385 | 0x7e824e90a5dc3853ULL, 0xccb5f6641f135cbdULL, 0x6736d86c87ce8fccULL, 0x625f3ce26604249fULL, |
1386 | 0xaf8ac8059502f63fULL, 0x0c05e70a2e351469ULL, 0x35292e9c764b6305ULL, 0x1a394360c7e23ac3ULL, |
1387 | 0xd5c6d53251183264ULL, 0x62065abd43c2b74fULL, 0xb5fbf5d03b973f9bULL, 0x13a3da3661206e5eULL, |
1388 | 0xc6bd5837725d94e5ULL, 0x18e30912205016c5ULL, 0x2088ce1570033c68ULL, 0x7fba1f495c837987ULL, |
1389 | 0x5a8c7423f2f9079dULL, 0x1735157b34023fc5ULL, 0xe4f9b49ad2fab351ULL, 0x6691ff72c878e33cULL, |
1390 | 0x122c2adedc5eff3eULL, 0xf8dd4bf1d8956cf4ULL, 0xeb86205d9e9e5bdaULL, 0x049b92b9d975c743ULL, |
1391 | 0xa5379730b0f6c05aULL, 0x72a0ffacc6f3a553ULL, 0xb0032c34b20dcd6dULL, 0x470e9dbc88d5164aULL, |
1392 | 0xb19cf10ca237c047ULL, 0xb65466711f6c81a2ULL, 0xb3321bd16dd80b43ULL, 0x48c14f600c5fbe8eULL, |
1393 | 0x66451c264aa6c803ULL, 0xb66e3904a4fa7da6ULL, 0xd45f19b0b3128395ULL, 0x31602627c3c9bc10ULL, |
1394 | 0x3120dc4832e4e10dULL, 0xeb20c46756c717f7ULL, 0x00f52e3f67280294ULL, 0x566d4fc14730c509ULL, |
1395 | 0x7e3a5d40fd837206ULL, 0xc1e926dc7159547aULL, 0x216730fba68d6095ULL, 0x22e8c3843f69cea7ULL, |
1396 | 0x33d074e8930e4b2bULL, 0xb6e4350e84d15816ULL, 0x5534c26ad6ba2365ULL, 0x7773c12f89f1f3f3ULL, |
1397 | 0x8cba404da57962aaULL, 0x5b9897a81999ce56ULL, 0x508e862f121692fcULL, 0x3a81907fa093c291ULL, |
1398 | 0x0dded0ff4725a510ULL, 0x10d8cc10673fc503ULL, 0x5b9d151c9f1f4e89ULL, 0x32a5c1d5cb09a44cULL, |
1399 | 0x1e0aa442b90541fbULL, 0x5f85eb7cc1b485dbULL, 0xbee595ce8a9df2e5ULL, 0x25e496c722422236ULL, |
1400 | 0x5edf3c46cd0fe5b9ULL, 0x34e75a7ed2a43388ULL, 0xe488de11d761e352ULL, 0x0e878a01a085545cULL, |
1401 | 0xba493c77e021bb04ULL, 0x2b4d1843c7df899aULL, 0x9ea37a487ae80d67ULL, 0x67a9958011e41794ULL, |
1402 | 0x4b58051a6697b065ULL, 0x47e33f7d8d6ba6d4ULL, 0xbb4da8d483ca46c1ULL, 0x68becaa181c2db0dULL, |
1403 | 0x8d8980e90b989aa5ULL, 0xf95eb14a2c93c99bULL, 0x51c6c7c4796e73a2ULL, 0x6e228363b5efb569ULL, |
1404 | 0xc6bbc0b02dd624c8ULL, 0x777eb47dec8170eeULL, 0x3cde15a004cfafa9ULL, 0x1dc6bc087160bf9bULL, |
1405 | 0x2e07e043eec34002ULL, 0x18e9fc677a68dc7fULL, 0xd8da03188bd15b9aULL, 0x48fbc3bb00568253ULL, |
1406 | 0x57547d4cfb654ce1ULL, 0xd3565b82a058e2adULL, 0xf63eaf0bbf154478ULL, 0x47531ef114dfbb18ULL, |
1407 | 0xe1ec630a4278c587ULL, 0x5507d546ca8e83f3ULL, 0x85e135c63adc0c2bULL, 0x0aa7efa85682844eULL, |
1408 | 0x72691ba8b3e1f615ULL, 0x32b4e9701fbe3ffaULL, 0x97b6d92e39bb7868ULL, 0x2cfe53dea02e39e8ULL, |
1409 | 0x687392cd85cd52b0ULL, 0x27ff66c910e29831ULL, 0x97134556a9832d06ULL, 0x269bb0360a84f8a0ULL, |
1410 | 0x706e55457643f85cULL, 0x3734a48c9b597d1bULL, 0x7aee91e8c6efa472ULL, 0x5cd6abc198a9d9e0ULL, |
1411 | 0x0e04de06cb3ce41aULL, 0xd8c6eb893402e138ULL, 0x904659bb686e3772ULL, 0x7215c371746ba8c8ULL, |
1412 | 0xfd12a97eeae4a2d9ULL, 0x9514b7516394f2c5ULL, 0x266fd5809208f294ULL, 0x5c847085619a26b9ULL, |
1413 | 0x52985410fed694eaULL, 0x3c905b934a2ed254ULL, 0x10bb47692d3be467ULL, 0x063b3d2d69e5e9e1ULL, |
1414 | 0x472726eedda57debULL, 0xefb6c4ae10f41891ULL, 0x2b1641917b307614ULL, 0x117c554fc4f45b7cULL, |
1415 | 0xc07cf3118f9d8812ULL, 0x01dbd82050017939ULL, 0xd7e803f4171b2827ULL, 0x1015e87487d225eaULL, |
1416 | 0xc58de3fed23acc4dULL, 0x50db91c294a7be2dULL, 0x0b94d43d1c9cf457ULL, 0x6b1640fa6e37524aULL, |
1417 | 0x692f346c5fda0d09ULL, 0x200b1c59fa4d3151ULL, 0xb8c46f760777a296ULL, 0x4b38395f3ffdfbcfULL, |
1418 | 0x18d25e00be54d671ULL, 0x60d50582bec8aba6ULL, 0x87ad8f263b78b982ULL, 0x50fdf64e9cda0432ULL, |
1419 | 0x90f567aac578dcf0ULL, 0xef1e9b0ef2a3133bULL, 0x0eebba9242d9de71ULL, 0x15473c9bf03101c7ULL, |
1420 | 0x7c77e8ae56b78095ULL, 0xb678e7666e6f078eULL, 0x2da0b9615348ba1fULL, 0x7cf931c1ff733f0bULL, |
1421 | 0x26b357f50a0a366cULL, 0xe9708cf42b87d732ULL, 0xc13aeea5f91cb2c0ULL, 0x35d90c991143bb4cULL, |
1422 | 0x47c1c404a9a0d9dcULL, 0x659e58451972d251ULL, 0x3875a8c473b38c31ULL, 0x1fbd9ed379561f24ULL, |
1423 | 0x11fabc6fd41ec28dULL, 0x7ef8dfe3cd2a2dcaULL, 0x72e73b5d8c404595ULL, 0x6135fa4954b72f27ULL, |
1424 | 0xccfc32a2de24b69cULL, 0x3f55698c1f095d88ULL, 0xbe3350ed5ac3f929ULL, 0x5e9bf806ca477eebULL, |
1425 | 0xe9ce8fb63c309f68ULL, 0x5376f63565e1f9f4ULL, 0xd1afcfb35a6393f1ULL, 0x6632a1ede5623506ULL, |
1426 | 0x0b7d6c390c2ded4cULL, 0x56cb3281df04cb1fULL, 0x66305a1249ecc3c7ULL, 0x5d588b60a38ca72aULL, |
1427 | 0xa6ecbf78e8e5f42dULL, 0x86eeb44b3c8a3eecULL, 0xec219c48fbd21604ULL, 0x1aaf1af517c36731ULL, |
1428 | 0xc306a2836769bde7ULL, 0x208280622b1e2adbULL, 0x8027f51ffbff94a6ULL, 0x76cfa1ce1124f26bULL, |
1429 | 0x18eb00562422abb6ULL, 0xf377c4d58f8c29c3ULL, 0x4dbbc207f531561aULL, 0x0253b7f082128a27ULL, |
1430 | 0x3d1f091cb62c17e0ULL, 0x4860e1abd64628a9ULL, 0x52d17436309d4253ULL, 0x356f97e13efae576ULL, |
1431 | 0xd351e11aa150535bULL, 0x3e6b45bb1dd878ccULL, 0x0c776128bed92c98ULL, 0x1d34ae93032885b8ULL, |
1432 | 0x4ba0488ca85ba4c3ULL, 0x985348c33c9ce6ceULL, 0x66124c6f97bda770ULL, 0x0f81a0290654124aULL, |
1433 | 0x9ed09ca6569b86fdULL, 0x811009fd18af9a2dULL, 0xff08d03f93d8c20aULL, 0x52a148199faef26bULL, |
1434 | 0x3e03f9dc2d8d1b73ULL, 0x4205801873961a70ULL, 0xc0d987f041a35970ULL, 0x07aa1f15a1c0d549ULL, |
1435 | 0xdfd46ce08cd27224ULL, 0x6d0a024f934e4239ULL, 0x808a7a6399897b59ULL, 0x0a4556e9e13d95a2ULL, |
1436 | 0xd21a991fe9c13045ULL, 0x9b0e8548fe7751b8ULL, 0x5da643cb4bf30035ULL, 0x77db28d63940f721ULL, |
1437 | 0xfc5eeb614adc9011ULL, 0x5229419ae8c411ebULL, 0x9ec3e7787d1dcf74ULL, 0x340d053e216e4cb5ULL, |
1438 | 0xcac7af39b48df2b4ULL, 0xc0faec2871a10a94ULL, 0x140a69245ca575edULL, 0x0cf1c37134273a4cULL, |
1439 | 0xc8ee306ac224b8a5ULL, 0x57eaee7ccb4930b0ULL, 0xa1e806bdaacbe74fULL, 0x7d9a62742eeb657dULL, |
1440 | 0x9eb6b6ef546c4830ULL, 0x885cca1fddb36e2eULL, 0xe6b9f383ef0d7105ULL, 0x58654fef9d2e0412ULL, |
1441 | 0xa905c4ffbe0e8e26ULL, 0x942de5df9b31816eULL, 0x497d723f802e88e1ULL, 0x30684dea602f408dULL, |
1442 | 0x21e5a278a3e6cb34ULL, 0xaefb6e6f5b151dc4ULL, 0xb30b8e049d77ca15ULL, 0x28c3c9cf53b98981ULL, |
1443 | 0x287fb721556cdd2aULL, 0x0d317ca897022274ULL, 0x7468c7423a543258ULL, 0x4a7f11464eb5642fULL, |
1444 | 0xa237a4774d193aa6ULL, 0xd865986ea92129a1ULL, 0x24c515ecf87c1a88ULL, 0x604003575f39f5ebULL, |
1445 | 0x47b9f189570a9b27ULL, 0x2b98cede465e4b78ULL, 0x026df551dbb85c20ULL, 0x74fcd91047e21901ULL, |
1446 | 0x13e2a90a23c1bfa3ULL, 0x0cb0074e478519f6ULL, 0x5ff1cbbe3af6cf44ULL, 0x67fe5438be812dbeULL, |
1447 | 0xd13cf64fa40f05b0ULL, 0x054dfb2f32283787ULL, 0x4173915b7f0d2aeaULL, 0x482f144f1f610d4eULL, |
1448 | 0xf6210201b47f8234ULL, 0x5d0ae1929e70b990ULL, 0xdcd7f455b049567cULL, 0x7e93d0f1f0916f01ULL, |
1449 | 0xdd79cbf18a7db4faULL, 0xbe8391bf6f74c62fULL, 0x027145d14b8291bdULL, 0x585a73ea2cbf1705ULL, |
1450 | 0x485ca03e928a0db2ULL, 0x10fc01a5742857e7ULL, 0x2f482edbd6d551a7ULL, 0x0f0433b5048fdb8aULL, |
1451 | 0x60da2e8dd7dc6247ULL, 0x88b4c9d38cd4819aULL, 0x13033ac001f66697ULL, 0x273b24fe3b367d75ULL, |
1452 | 0xc6e8f66a31b3b9d4ULL, 0x281514a494df49d5ULL, 0xd1726fdfc8b23da7ULL, 0x4b3ae7d103dee548ULL, |
1453 | 0xc6256e19ce4b9d7eULL, 0xff5c5cf186e3c61cULL, 0xacc63ca34b8ec145ULL, 0x74621888fee66574ULL, |
1454 | 0x956f409645290a1eULL, 0xef0bf8e3263a962eULL, 0xed6a50eb5ec2647bULL, 0x0694283a9dca7502ULL, |
1455 | 0x769b963643a2dcd1ULL, 0x42b7c8ea09fc5353ULL, 0x4f002aee13397eabULL, 0x63005e2c19b7d63aULL, |
1456 | 0xca6736da63023beaULL, 0x966c7f6db12a99b7ULL, 0xace09390c537c5e1ULL, 0x0b696063a1aa89eeULL, |
1457 | 0xebb03e97288c56e5ULL, 0x432a9f9f938c8be8ULL, 0xa6a5a93d5b717f71ULL, 0x1a5fb4c3e18f9d97ULL, |
1458 | 0x1c94e7ad1c60cdceULL, 0xee202a43fc02c4a0ULL, 0x8dafe4d867c46a20ULL, 0x0a10263c8ac27b58ULL, |
1459 | 0xd0dea9dfe4432a4aULL, 0x856af87bbe9277c5ULL, 0xce8472acc212c71aULL, 0x6f151b6d9bbb1e91ULL, |
1460 | 0x26776c527ceed56aULL, 0x7d211cb7fbf8faecULL, 0x37ae66a6fd4609ccULL, 0x1f81b702d2770c42ULL, |
1461 | 0x2fb0b057eac58392ULL, 0xe1dd89fe29744e9dULL, 0xc964f8eb17beb4f8ULL, 0x29571073c9a2d41eULL, |
1462 | 0xa948a18981c0e254ULL, 0x2df6369b65b22830ULL, 0xa33eb2d75fcfd3c6ULL, 0x078cd6ec4199a01fULL, |
1463 | 0x4a584a41ad900d2fULL, 0x32142b78e2c74c52ULL, 0x68c4e8338431c978ULL, 0x7f69ea9008689fc2ULL, |
1464 | 0x52f2c81e46a38265ULL, 0xfd78072d04a832fdULL, 0x8cd7d5fa25359e94ULL, 0x4de71b7454cc29d2ULL, |
1465 | 0x42eb60ad1eda6ac9ULL, 0x0aad37dfdbc09c3aULL, 0x81004b71e33cc191ULL, 0x44e6be345122803cULL, |
1466 | 0x03fe8388ba1920dbULL, 0xf5d57c32150db008ULL, 0x49c8c4281af60c29ULL, 0x21edb518de701aeeULL, |
1467 | 0x7fb63e418f06dc99ULL, 0xa4460d99c166d7b8ULL, 0x24dd5248ce520a83ULL, 0x5ec3ad712b928358ULL, |
1468 | 0x15022a5fbd17930fULL, 0xa4f64a77d82570e3ULL, 0x12bc8d6915783712ULL, 0x498194c0fc620abbULL, |
1469 | 0x38a2d9d255686c82ULL, 0x785c6bd9193e21f0ULL, 0xe4d5c81ab24a5484ULL, 0x56307860b2e20989ULL, |
1470 | 0x429d55f78b4d74c4ULL, 0x22f1834643350131ULL, 0x1e60c24598c71fffULL, 0x59f2f014979983efULL, |
1471 | 0x46a47d56eb494a44ULL, 0x3e22a854d636a18eULL, 0xb346e15274491c3bULL, 0x2ceafd4e5390cde7ULL, |
1472 | 0xba8a8538be0d6675ULL, 0x4b9074bb50818e23ULL, 0xcbdab89085d304c3ULL, 0x61a24fe0e56192c4ULL, |
1473 | 0xcb7615e6db525bcbULL, 0xdd7d8c35a567e4caULL, 0xe6b4153acafcdd69ULL, 0x2d668e097f3c9766ULL, |
1474 | 0xa57e7e265ce55ef0ULL, 0x5d9f4e527cd4b967ULL, 0xfbc83606492fd1e5ULL, 0x090d52beb7c3f7aeULL, |
1475 | 0x09b9515a1e7b4d7cULL, 0x1f266a2599da44c0ULL, 0xa1c49548e2c55504ULL, 0x7ef04287126f15ccULL, |
1476 | 0xfed1659dbd30ef15ULL, 0x8b4ab9eec4e0277bULL, 0x884d6236a5df3291ULL, 0x1fd96ea6bf5cf788ULL, |
1477 | 0x42a161981f190d9aULL, 0x61d849507e6052c1ULL, 0x9fe113bf285a2cd5ULL, 0x7c22d676dbad85d8ULL, |
1478 | 0x82e770ed2bfbd27dULL, 0x4c05b2ece996f5a5ULL, 0xcd40a9c2b0900150ULL, 0x5895319213d9bf64ULL, |
1479 | 0xe7cc5d703fea2e08ULL, 0xb50c491258e2188cULL, 0xcce30baa48205bf0ULL, 0x537c659ccfa32d62ULL, |
1480 | 0x37b6623a98cfc088ULL, 0xfe9bed1fa4d6aca4ULL, 0x04d29b8e56a8d1b0ULL, 0x725f71c40b519575ULL, |
1481 | 0x28c7f89cd0339ce6ULL, 0x8367b14469ddc18bULL, 0x883ada83a6a1652cULL, 0x585f1974034d6c17ULL, |
1482 | 0x89cfb266f1b19188ULL, 0xe63b4863e7c35217ULL, 0xd88c9da6b4c0526aULL, 0x3e035c9df0954635ULL, |
1483 | 0xdd9d5412fb45de9dULL, 0xdd684532e4cff40dULL, 0x4b5c999b151d671cULL, 0x2d8c2cc811e7f690ULL, |
1484 | 0x7f54be1d90055d40ULL, 0xa464c5df464aaf40ULL, 0x33979624f0e917beULL, 0x2c018dc527356b30ULL, |
1485 | 0xa5415024e330b3d4ULL, 0x73ff3d96691652d3ULL, 0x94ec42c4ef9b59f1ULL, 0x0747201618d08e5aULL, |
1486 | 0x4d6ca48aca411c53ULL, 0x66415f2fcfa66119ULL, 0x9c4dd40051e227ffULL, 0x59810bc09a02f7ebULL, |
1487 | 0x2a7eb171b3dc101dULL, 0x441c5ab99ffef68eULL, 0x32025c9b93b359eaULL, 0x5e8ce0a71e9d112fULL, |
1488 | 0xbfcccb92429503fdULL, 0xd271ba752f095d55ULL, 0x345ead5e972d091eULL, 0x18c8df11a83103baULL, |
1489 | 0x90cd949a9aed0f4cULL, 0xc5d1f4cb6660e37eULL, 0xb8cac52d56c52e0bULL, 0x6e42e400c5808e0dULL, |
1490 | 0xa3b46966eeaefd23ULL, 0x0c4f1f0be39ecdcaULL, 0x189dc8c9d683a51dULL, 0x51f27f054c09351bULL, |
1491 | 0x4c487ccd2a320682ULL, 0x587ea95bb3df1c96ULL, 0xc8ccf79e555cb8e8ULL, 0x547dc829a206d73dULL, |
1492 | 0xb822a6cd80c39b06ULL, 0xe96d54732000d4c6ULL, 0x28535b6f91463b4dULL, 0x228f4660e2486e1dULL, |
1493 | 0x98799538de8d3abfULL, 0x8cd8330045ebca6eULL, 0x79952a008221e738ULL, 0x4322e1a7535cd2bbULL, |
1494 | 0xb114c11819d1801cULL, 0x2016e4d84f3f5ec7ULL, 0xdd0e2df409260f4cULL, 0x5ec362c0ae5f7266ULL, |
1495 | 0xc0462b18b8b2b4eeULL, 0x7cc8d950274d1afbULL, 0xf25f7105436b02d2ULL, 0x43bbf8dcbff9ccd3ULL, |
1496 | 0xb6ad1767a039e9dfULL, 0xb0714da8f69d3583ULL, 0x5e55fa18b42931f5ULL, 0x4ed5558f33c60961ULL, |
1497 | 0x1fe37901c647a5ddULL, 0x593ddf1f8081d357ULL, 0x0249a4fd813fd7a6ULL, 0x69acca274e9caf61ULL, |
1498 | 0x047ba3ea330721c9ULL, 0x83423fc20e7e1ea0ULL, 0x1df4c0af01314a60ULL, 0x09a62dab89289527ULL, |
1499 | 0xa5b325a49cc6cb00ULL, 0xe94b5dc654b56cb6ULL, 0x3be28779adc994a0ULL, 0x4296e8f8ba3a4aadULL, |
1500 | 0x328689761e451eabULL, 0x2e4d598bff59594aULL, 0x49b96853d7a7084aULL, 0x4980a319601420a8ULL, |
1501 | 0x9565b9e12f552c42ULL, 0x8a5318db7100fe96ULL, 0x05c90b4d43add0d7ULL, 0x538b4cd66a5d4edaULL, |
1502 | 0xf4e94fc3e89f039fULL, 0x592c9af26f618045ULL, 0x08a36eb5fd4b9550ULL, 0x25fffaf6c2ed1419ULL, |
1503 | 0x34434459cc79d354ULL, 0xeeecbfb4b1d5476bULL, 0xddeb34a061615d99ULL, 0x5129cecceb64b773ULL, |
1504 | 0xee43215894993520ULL, 0x772f9c7cf14c0b3bULL, 0xd2e2fce306bedad5ULL, 0x715f42b546f06a97ULL, |
1505 | 0x434ecdceda5b5f1aULL, 0x0da17115a49741a9ULL, 0x680bd77c73edad2eULL, 0x487c02354edd9041ULL, |
1506 | 0xb8efeff3a70ed9c4ULL, 0x56a32aa3e857e302ULL, 0xdf3a68bd48a2a5a0ULL, 0x07f650b73176c444ULL, |
1507 | 0xe38b9b1626e0ccb1ULL, 0x79e053c18b09fb36ULL, 0x56d90319c9f94964ULL, 0x1ca941e7ac9ff5c4ULL, |
1508 | 0x49c4df29162fa0bbULL, 0x8488cf3282b33305ULL, 0x95dfda14cabb437dULL, 0x3391f78264d5ad86ULL, |
1509 | 0x729ae06ae2b5095dULL, 0xd58a58d73259a946ULL, 0xe9834262d13921edULL, 0x27fedafaa54bb592ULL, |
1510 | 0xa99dc5b829ad48bbULL, 0x5f025742499ee260ULL, 0x802c8ecd5d7513fdULL, 0x78ceb3ef3f6dd938ULL, |
1511 | 0xc342f44f8a135d94ULL, 0x7b9edb44828cdda3ULL, 0x9436d11a0537cfe7ULL, 0x5064b164ec1ab4c8ULL, |
1512 | 0x7020eccfd37eb2fcULL, 0x1f31ea3ed90d25fcULL, 0x1b930d7bdfa1bb34ULL, 0x5344467a48113044ULL, |
1513 | 0x70073170f25e6dfbULL, 0xe385dc1a50114cc8ULL, 0x2348698ac8fc4f00ULL, 0x2a77a55284dd40d8ULL, |
1514 | 0xfe06afe0c98c6ce4ULL, 0xc235df96dddfd6e4ULL, 0x1428d01e33bf1ed3ULL, 0x785768ec9300bdafULL, |
1515 | 0x9702e57a91deb63bULL, 0x61bdb8bfe5ce8b80ULL, 0x645b426f3d1d58acULL, 0x4804a82227a557bcULL, |
1516 | 0x8e57048ab44d2601ULL, 0x68d6501a4b3a6935ULL, 0xc39c9ec3f9e1c293ULL, 0x4172f257d4de63e2ULL, |
1517 | 0xd368b450330c6401ULL, 0x040d3017418f2391ULL, 0x2c34bb6090b7d90dULL, 0x16f649228fdfd51fULL, |
1518 | 0xbea6818e2b928ef5ULL, 0xe28ccf91cdc11e72ULL, 0x594aaa68e77a36cdULL, 0x313034806c7ffd0fULL, |
1519 | 0x8a9d27ac2249bd65ULL, 0x19a3b464018e9512ULL, 0xc26ccff352b37ec7ULL, 0x056f68341d797b21ULL, |
1520 | 0x5e79d6757efd2327ULL, 0xfabdbcb6553afe15ULL, 0xd3e7222c6eaf5a60ULL, 0x7046c76d4dae743bULL, |
1521 | 0x660be872b18d4a55ULL, 0x19992518574e1496ULL, 0xc103053a302bdcbbULL, 0x3ed8e9800b218e8eULL, |
1522 | 0x7b0b9239fa75e03eULL, 0xefe9fb684633c083ULL, 0x98a35fbe391a7793ULL, 0x6065510fe2d0fe34ULL, |
1523 | 0x55cb668548abad0cULL, 0xb4584548da87e527ULL, 0x2c43ecea0107c1ddULL, 0x526028809372de35ULL, |
1524 | 0x3415c56af9213b1fULL, 0x5bee1a4d017e98dbULL, 0x13f6b105b5cf709bULL, 0x5ff20e3482b29ab6ULL, |
1525 | 0x0aa29c75cc2e6c90ULL, 0xfc7d73ca3a70e206ULL, 0x899fc38fc4b5c515ULL, 0x250386b124ffc207ULL, |
1526 | 0x54ea28d5ae3d2b56ULL, 0x9913149dd6de60ceULL, 0x16694fc58f06d6c1ULL, 0x46b23975eb018fc7ULL, |
1527 | 0x470a6a0fb4b7b4e2ULL, 0x5d92475a8f7253deULL, 0xabeee5b52fbd3adbULL, 0x7fa20801a0806968ULL, |
1528 | 0x76f3faf19f7714d2ULL, 0xb3e840c12f4660c3ULL, 0x0fb4cd8df212744eULL, 0x4b065a251d3a2dd2ULL, |
1529 | 0x5cebde383d77cd4aULL, 0x6adf39df882c9cb1ULL, 0xa2dd242eb09af759ULL, 0x3147c0e50e5f6422ULL, |
1530 | 0x164ca5101d1350dbULL, 0xf8d13479c33fc962ULL, 0xe640ce4d13e5da08ULL, 0x4bdee0c45061f8baULL, |
1531 | 0xd7c46dc1a4edb1c9ULL, 0x5514d7b6437fd98aULL, 0x58942f6bb2a1c00bULL, 0x2dffb2ab1d70710eULL, |
1532 | 0xccdfcf2fc18b6d68ULL, 0xa8ebcba8b7806167ULL, 0x980697f95e2937e3ULL, 0x02fbba1cd0126e8cULL |
1533 | }; |
1534 | |
1535 | static void curve25519_ever64_base(u8 *out, const u8 *priv) |
1536 | { |
1537 | u64 swap = 1; |
1538 | int i, j, k; |
1539 | u64 tmp[16 + 32 + 4]; |
1540 | u64 *x1 = &tmp[0]; |
1541 | u64 *z1 = &tmp[4]; |
1542 | u64 *x2 = &tmp[8]; |
1543 | u64 *z2 = &tmp[12]; |
1544 | u64 *xz1 = &tmp[0]; |
1545 | u64 *xz2 = &tmp[8]; |
1546 | u64 *a = &tmp[0 + 16]; |
1547 | u64 *b = &tmp[4 + 16]; |
1548 | u64 *c = &tmp[8 + 16]; |
1549 | u64 *ab = &tmp[0 + 16]; |
1550 | u64 *abcd = &tmp[0 + 16]; |
1551 | u64 *ef = &tmp[16 + 16]; |
1552 | u64 *efgh = &tmp[16 + 16]; |
1553 | u64 *key = &tmp[0 + 16 + 32]; |
1554 | |
1555 | memcpy(key, priv, 32); |
1556 | ((u8 *)key)[0] &= 248; |
1557 | ((u8 *)key)[31] = (((u8 *)key)[31] & 127) | 64; |
1558 | |
1559 | x1[0] = 1, x1[1] = x1[2] = x1[3] = 0; |
1560 | z1[0] = 1, z1[1] = z1[2] = z1[3] = 0; |
1561 | z2[0] = 1, z2[1] = z2[2] = z2[3] = 0; |
1562 | memcpy(x2, p_minus_s, sizeof(p_minus_s)); |
1563 | |
1564 | j = 3; |
1565 | for (i = 0; i < 4; ++i) { |
1566 | while (j < (const int[]){ 64, 64, 64, 63 }[i]) { |
1567 | u64 bit = (key[i] >> j) & 1; |
1568 | k = (64 * i + j - 3); |
1569 | swap = swap ^ bit; |
1570 | cswap2(bit: swap, p1: xz1, p2: xz2); |
1571 | swap = bit; |
1572 | fsub(out: b, f1: x1, f2: z1); |
1573 | fadd(out: a, f1: x1, f2: z1); |
1574 | fmul(out: c, f1: &table_ladder[4 * k], f2: b, tmp: ef); |
1575 | fsub(out: b, f1: a, f2: c); |
1576 | fadd(out: a, f1: a, f2: c); |
1577 | fsqr2(out: ab, f: ab, tmp: efgh); |
1578 | fmul2(out: xz1, f1: xz2, f2: ab, tmp: efgh); |
1579 | ++j; |
1580 | } |
1581 | j = 0; |
1582 | } |
1583 | |
1584 | point_double(nq: xz1, tmp1: abcd, tmp2: efgh); |
1585 | point_double(nq: xz1, tmp1: abcd, tmp2: efgh); |
1586 | point_double(nq: xz1, tmp1: abcd, tmp2: efgh); |
1587 | encode_point(o: out, i: xz1); |
1588 | |
1589 | memzero_explicit(s: tmp, count: sizeof(tmp)); |
1590 | } |
1591 | |
1592 | static __ro_after_init DEFINE_STATIC_KEY_FALSE(curve25519_use_bmi2_adx); |
1593 | |
1594 | void curve25519_arch(u8 mypublic[CURVE25519_KEY_SIZE], |
1595 | const u8 secret[CURVE25519_KEY_SIZE], |
1596 | const u8 basepoint[CURVE25519_KEY_SIZE]) |
1597 | { |
1598 | if (static_branch_likely(&curve25519_use_bmi2_adx)) |
1599 | curve25519_ever64(out: mypublic, priv: secret, pub: basepoint); |
1600 | else |
1601 | curve25519_generic(out: mypublic, scalar: secret, point: basepoint); |
1602 | } |
1603 | EXPORT_SYMBOL(curve25519_arch); |
1604 | |
1605 | void curve25519_base_arch(u8 pub[CURVE25519_KEY_SIZE], |
1606 | const u8 secret[CURVE25519_KEY_SIZE]) |
1607 | { |
1608 | if (static_branch_likely(&curve25519_use_bmi2_adx)) |
1609 | curve25519_ever64_base(out: pub, priv: secret); |
1610 | else |
1611 | curve25519_generic(out: pub, scalar: secret, point: curve25519_base_point); |
1612 | } |
1613 | EXPORT_SYMBOL(curve25519_base_arch); |
1614 | |
1615 | static int curve25519_set_secret(struct crypto_kpp *tfm, const void *buf, |
1616 | unsigned int len) |
1617 | { |
1618 | u8 *secret = kpp_tfm_ctx(tfm); |
1619 | |
1620 | if (!len) |
1621 | curve25519_generate_secret(secret); |
1622 | else if (len == CURVE25519_KEY_SIZE && |
1623 | crypto_memneq(a: buf, b: curve25519_null_point, size: CURVE25519_KEY_SIZE)) |
1624 | memcpy(secret, buf, CURVE25519_KEY_SIZE); |
1625 | else |
1626 | return -EINVAL; |
1627 | return 0; |
1628 | } |
1629 | |
1630 | static int curve25519_generate_public_key(struct kpp_request *req) |
1631 | { |
1632 | struct crypto_kpp *tfm = crypto_kpp_reqtfm(req); |
1633 | const u8 *secret = kpp_tfm_ctx(tfm); |
1634 | u8 buf[CURVE25519_KEY_SIZE]; |
1635 | int copied, nbytes; |
1636 | |
1637 | if (req->src) |
1638 | return -EINVAL; |
1639 | |
1640 | curve25519_base_arch(buf, secret); |
1641 | |
1642 | /* might want less than we've got */ |
1643 | nbytes = min_t(size_t, CURVE25519_KEY_SIZE, req->dst_len); |
1644 | copied = sg_copy_from_buffer(sgl: req->dst, nents: sg_nents_for_len(sg: req->dst, |
1645 | len: nbytes), |
1646 | buf, buflen: nbytes); |
1647 | if (copied != nbytes) |
1648 | return -EINVAL; |
1649 | return 0; |
1650 | } |
1651 | |
1652 | static int curve25519_compute_shared_secret(struct kpp_request *req) |
1653 | { |
1654 | struct crypto_kpp *tfm = crypto_kpp_reqtfm(req); |
1655 | const u8 *secret = kpp_tfm_ctx(tfm); |
1656 | u8 public_key[CURVE25519_KEY_SIZE]; |
1657 | u8 buf[CURVE25519_KEY_SIZE]; |
1658 | int copied, nbytes; |
1659 | |
1660 | if (!req->src) |
1661 | return -EINVAL; |
1662 | |
1663 | copied = sg_copy_to_buffer(sgl: req->src, |
1664 | nents: sg_nents_for_len(sg: req->src, |
1665 | len: CURVE25519_KEY_SIZE), |
1666 | buf: public_key, buflen: CURVE25519_KEY_SIZE); |
1667 | if (copied != CURVE25519_KEY_SIZE) |
1668 | return -EINVAL; |
1669 | |
1670 | curve25519_arch(buf, secret, public_key); |
1671 | |
1672 | /* might want less than we've got */ |
1673 | nbytes = min_t(size_t, CURVE25519_KEY_SIZE, req->dst_len); |
1674 | copied = sg_copy_from_buffer(sgl: req->dst, nents: sg_nents_for_len(sg: req->dst, |
1675 | len: nbytes), |
1676 | buf, buflen: nbytes); |
1677 | if (copied != nbytes) |
1678 | return -EINVAL; |
1679 | return 0; |
1680 | } |
1681 | |
1682 | static unsigned int curve25519_max_size(struct crypto_kpp *tfm) |
1683 | { |
1684 | return CURVE25519_KEY_SIZE; |
1685 | } |
1686 | |
1687 | static struct kpp_alg curve25519_alg = { |
1688 | .base.cra_name = "curve25519" , |
1689 | .base.cra_driver_name = "curve25519-x86" , |
1690 | .base.cra_priority = 200, |
1691 | .base.cra_module = THIS_MODULE, |
1692 | .base.cra_ctxsize = CURVE25519_KEY_SIZE, |
1693 | |
1694 | .set_secret = curve25519_set_secret, |
1695 | .generate_public_key = curve25519_generate_public_key, |
1696 | .compute_shared_secret = curve25519_compute_shared_secret, |
1697 | .max_size = curve25519_max_size, |
1698 | }; |
1699 | |
1700 | |
1701 | static int __init curve25519_mod_init(void) |
1702 | { |
1703 | if (boot_cpu_has(X86_FEATURE_BMI2) && boot_cpu_has(X86_FEATURE_ADX)) |
1704 | static_branch_enable(&curve25519_use_bmi2_adx); |
1705 | else |
1706 | return 0; |
1707 | return IS_REACHABLE(CONFIG_CRYPTO_KPP) ? |
1708 | crypto_register_kpp(alg: &curve25519_alg) : 0; |
1709 | } |
1710 | |
1711 | static void __exit curve25519_mod_exit(void) |
1712 | { |
1713 | if (IS_REACHABLE(CONFIG_CRYPTO_KPP) && |
1714 | static_branch_likely(&curve25519_use_bmi2_adx)) |
1715 | crypto_unregister_kpp(alg: &curve25519_alg); |
1716 | } |
1717 | |
1718 | module_init(curve25519_mod_init); |
1719 | module_exit(curve25519_mod_exit); |
1720 | |
1721 | MODULE_ALIAS_CRYPTO("curve25519" ); |
1722 | MODULE_ALIAS_CRYPTO("curve25519-x86" ); |
1723 | MODULE_LICENSE("GPL v2" ); |
1724 | MODULE_AUTHOR("Jason A. Donenfeld <Jason@zx2c4.com>" ); |
1725 | |