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