GNU Linux-libre 5.19-rc6-gnu
[releases.git] / lib / crypto / curve25519-hacl64.c
1 // SPDX-License-Identifier: GPL-2.0 OR MIT
2 /*
3  * Copyright (C) 2016-2017 INRIA and Microsoft Corporation.
4  * Copyright (C) 2018-2019 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
5  *
6  * This is a machine-generated formally verified implementation of Curve25519
7  * ECDH from: <https://github.com/mitls/hacl-star>. Though originally machine
8  * generated, it has been tweaked to be suitable for use in the kernel. It is
9  * optimized for 64-bit machines that can efficiently work with 128-bit
10  * integer types.
11  */
12
13 #include <asm/unaligned.h>
14 #include <crypto/curve25519.h>
15 #include <linux/string.h>
16
17 typedef __uint128_t u128;
18
19 static __always_inline u64 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         u64 c = xnx - (u64)1U;
26         return c;
27 }
28
29 static __always_inline u64 u64_gte_mask(u64 a, u64 b)
30 {
31         u64 x = a;
32         u64 y = b;
33         u64 x_xor_y = x ^ y;
34         u64 x_sub_y = x - y;
35         u64 x_sub_y_xor_y = x_sub_y ^ y;
36         u64 q = x_xor_y | x_sub_y_xor_y;
37         u64 x_xor_q = x ^ q;
38         u64 x_xor_q_ = x_xor_q >> (u32)63U;
39         u64 c = x_xor_q_ - (u64)1U;
40         return c;
41 }
42
43 static __always_inline void modulo_carry_top(u64 *b)
44 {
45         u64 b4 = b[4];
46         u64 b0 = b[0];
47         u64 b4_ = b4 & 0x7ffffffffffffLLU;
48         u64 b0_ = b0 + 19 * (b4 >> 51);
49         b[4] = b4_;
50         b[0] = b0_;
51 }
52
53 static __always_inline void fproduct_copy_from_wide_(u64 *output, u128 *input)
54 {
55         {
56                 u128 xi = input[0];
57                 output[0] = ((u64)(xi));
58         }
59         {
60                 u128 xi = input[1];
61                 output[1] = ((u64)(xi));
62         }
63         {
64                 u128 xi = input[2];
65                 output[2] = ((u64)(xi));
66         }
67         {
68                 u128 xi = input[3];
69                 output[3] = ((u64)(xi));
70         }
71         {
72                 u128 xi = input[4];
73                 output[4] = ((u64)(xi));
74         }
75 }
76
77 static __always_inline void
78 fproduct_sum_scalar_multiplication_(u128 *output, u64 *input, u64 s)
79 {
80         output[0] += (u128)input[0] * s;
81         output[1] += (u128)input[1] * s;
82         output[2] += (u128)input[2] * s;
83         output[3] += (u128)input[3] * s;
84         output[4] += (u128)input[4] * s;
85 }
86
87 static __always_inline void fproduct_carry_wide_(u128 *tmp)
88 {
89         {
90                 u32 ctr = 0;
91                 u128 tctr = tmp[ctr];
92                 u128 tctrp1 = tmp[ctr + 1];
93                 u64 r0 = ((u64)(tctr)) & 0x7ffffffffffffLLU;
94                 u128 c = ((tctr) >> (51));
95                 tmp[ctr] = ((u128)(r0));
96                 tmp[ctr + 1] = ((tctrp1) + (c));
97         }
98         {
99                 u32 ctr = 1;
100                 u128 tctr = tmp[ctr];
101                 u128 tctrp1 = tmp[ctr + 1];
102                 u64 r0 = ((u64)(tctr)) & 0x7ffffffffffffLLU;
103                 u128 c = ((tctr) >> (51));
104                 tmp[ctr] = ((u128)(r0));
105                 tmp[ctr + 1] = ((tctrp1) + (c));
106         }
107
108         {
109                 u32 ctr = 2;
110                 u128 tctr = tmp[ctr];
111                 u128 tctrp1 = tmp[ctr + 1];
112                 u64 r0 = ((u64)(tctr)) & 0x7ffffffffffffLLU;
113                 u128 c = ((tctr) >> (51));
114                 tmp[ctr] = ((u128)(r0));
115                 tmp[ctr + 1] = ((tctrp1) + (c));
116         }
117         {
118                 u32 ctr = 3;
119                 u128 tctr = tmp[ctr];
120                 u128 tctrp1 = tmp[ctr + 1];
121                 u64 r0 = ((u64)(tctr)) & 0x7ffffffffffffLLU;
122                 u128 c = ((tctr) >> (51));
123                 tmp[ctr] = ((u128)(r0));
124                 tmp[ctr + 1] = ((tctrp1) + (c));
125         }
126 }
127
128 static __always_inline void fmul_shift_reduce(u64 *output)
129 {
130         u64 tmp = output[4];
131         u64 b0;
132         {
133                 u32 ctr = 5 - 0 - 1;
134                 u64 z = output[ctr - 1];
135                 output[ctr] = z;
136         }
137         {
138                 u32 ctr = 5 - 1 - 1;
139                 u64 z = output[ctr - 1];
140                 output[ctr] = z;
141         }
142         {
143                 u32 ctr = 5 - 2 - 1;
144                 u64 z = output[ctr - 1];
145                 output[ctr] = z;
146         }
147         {
148                 u32 ctr = 5 - 3 - 1;
149                 u64 z = output[ctr - 1];
150                 output[ctr] = z;
151         }
152         output[0] = tmp;
153         b0 = output[0];
154         output[0] = 19 * b0;
155 }
156
157 static __always_inline void fmul_mul_shift_reduce_(u128 *output, u64 *input,
158                                                    u64 *input21)
159 {
160         u32 i;
161         u64 input2i;
162         {
163                 u64 input2i = input21[0];
164                 fproduct_sum_scalar_multiplication_(output, input, input2i);
165                 fmul_shift_reduce(input);
166         }
167         {
168                 u64 input2i = input21[1];
169                 fproduct_sum_scalar_multiplication_(output, input, input2i);
170                 fmul_shift_reduce(input);
171         }
172         {
173                 u64 input2i = input21[2];
174                 fproduct_sum_scalar_multiplication_(output, input, input2i);
175                 fmul_shift_reduce(input);
176         }
177         {
178                 u64 input2i = input21[3];
179                 fproduct_sum_scalar_multiplication_(output, input, input2i);
180                 fmul_shift_reduce(input);
181         }
182         i = 4;
183         input2i = input21[i];
184         fproduct_sum_scalar_multiplication_(output, input, input2i);
185 }
186
187 static __always_inline void fmul_fmul(u64 *output, u64 *input, u64 *input21)
188 {
189         u64 tmp[5] = { input[0], input[1], input[2], input[3], input[4] };
190         {
191                 u128 b4;
192                 u128 b0;
193                 u128 b4_;
194                 u128 b0_;
195                 u64 i0;
196                 u64 i1;
197                 u64 i0_;
198                 u64 i1_;
199                 u128 t[5] = { 0 };
200                 fmul_mul_shift_reduce_(t, tmp, input21);
201                 fproduct_carry_wide_(t);
202                 b4 = t[4];
203                 b0 = t[0];
204                 b4_ = ((b4) & (((u128)(0x7ffffffffffffLLU))));
205                 b0_ = ((b0) + (((u128)(19) * (((u64)(((b4) >> (51))))))));
206                 t[4] = b4_;
207                 t[0] = b0_;
208                 fproduct_copy_from_wide_(output, t);
209                 i0 = output[0];
210                 i1 = output[1];
211                 i0_ = i0 & 0x7ffffffffffffLLU;
212                 i1_ = i1 + (i0 >> 51);
213                 output[0] = i0_;
214                 output[1] = i1_;
215         }
216 }
217
218 static __always_inline void fsquare_fsquare__(u128 *tmp, u64 *output)
219 {
220         u64 r0 = output[0];
221         u64 r1 = output[1];
222         u64 r2 = output[2];
223         u64 r3 = output[3];
224         u64 r4 = output[4];
225         u64 d0 = r0 * 2;
226         u64 d1 = r1 * 2;
227         u64 d2 = r2 * 2 * 19;
228         u64 d419 = r4 * 19;
229         u64 d4 = d419 * 2;
230         u128 s0 = ((((((u128)(r0) * (r0))) + (((u128)(d4) * (r1))))) +
231                    (((u128)(d2) * (r3))));
232         u128 s1 = ((((((u128)(d0) * (r1))) + (((u128)(d4) * (r2))))) +
233                    (((u128)(r3 * 19) * (r3))));
234         u128 s2 = ((((((u128)(d0) * (r2))) + (((u128)(r1) * (r1))))) +
235                    (((u128)(d4) * (r3))));
236         u128 s3 = ((((((u128)(d0) * (r3))) + (((u128)(d1) * (r2))))) +
237                    (((u128)(r4) * (d419))));
238         u128 s4 = ((((((u128)(d0) * (r4))) + (((u128)(d1) * (r3))))) +
239                    (((u128)(r2) * (r2))));
240         tmp[0] = s0;
241         tmp[1] = s1;
242         tmp[2] = s2;
243         tmp[3] = s3;
244         tmp[4] = s4;
245 }
246
247 static __always_inline void fsquare_fsquare_(u128 *tmp, u64 *output)
248 {
249         u128 b4;
250         u128 b0;
251         u128 b4_;
252         u128 b0_;
253         u64 i0;
254         u64 i1;
255         u64 i0_;
256         u64 i1_;
257         fsquare_fsquare__(tmp, output);
258         fproduct_carry_wide_(tmp);
259         b4 = tmp[4];
260         b0 = tmp[0];
261         b4_ = ((b4) & (((u128)(0x7ffffffffffffLLU))));
262         b0_ = ((b0) + (((u128)(19) * (((u64)(((b4) >> (51))))))));
263         tmp[4] = b4_;
264         tmp[0] = b0_;
265         fproduct_copy_from_wide_(output, tmp);
266         i0 = output[0];
267         i1 = output[1];
268         i0_ = i0 & 0x7ffffffffffffLLU;
269         i1_ = i1 + (i0 >> 51);
270         output[0] = i0_;
271         output[1] = i1_;
272 }
273
274 static __always_inline void fsquare_fsquare_times_(u64 *output, u128 *tmp,
275                                                    u32 count1)
276 {
277         u32 i;
278         fsquare_fsquare_(tmp, output);
279         for (i = 1; i < count1; ++i)
280                 fsquare_fsquare_(tmp, output);
281 }
282
283 static __always_inline void fsquare_fsquare_times(u64 *output, u64 *input,
284                                                   u32 count1)
285 {
286         u128 t[5];
287         memcpy(output, input, 5 * sizeof(*input));
288         fsquare_fsquare_times_(output, t, count1);
289 }
290
291 static __always_inline void fsquare_fsquare_times_inplace(u64 *output,
292                                                           u32 count1)
293 {
294         u128 t[5];
295         fsquare_fsquare_times_(output, t, count1);
296 }
297
298 static __always_inline void crecip_crecip(u64 *out, u64 *z)
299 {
300         u64 buf[20] = { 0 };
301         u64 *a0 = buf;
302         u64 *t00 = buf + 5;
303         u64 *b0 = buf + 10;
304         u64 *t01;
305         u64 *b1;
306         u64 *c0;
307         u64 *a;
308         u64 *t0;
309         u64 *b;
310         u64 *c;
311         fsquare_fsquare_times(a0, z, 1);
312         fsquare_fsquare_times(t00, a0, 2);
313         fmul_fmul(b0, t00, z);
314         fmul_fmul(a0, b0, a0);
315         fsquare_fsquare_times(t00, a0, 1);
316         fmul_fmul(b0, t00, b0);
317         fsquare_fsquare_times(t00, b0, 5);
318         t01 = buf + 5;
319         b1 = buf + 10;
320         c0 = buf + 15;
321         fmul_fmul(b1, t01, b1);
322         fsquare_fsquare_times(t01, b1, 10);
323         fmul_fmul(c0, t01, b1);
324         fsquare_fsquare_times(t01, c0, 20);
325         fmul_fmul(t01, t01, c0);
326         fsquare_fsquare_times_inplace(t01, 10);
327         fmul_fmul(b1, t01, b1);
328         fsquare_fsquare_times(t01, b1, 50);
329         a = buf;
330         t0 = buf + 5;
331         b = buf + 10;
332         c = buf + 15;
333         fmul_fmul(c, t0, b);
334         fsquare_fsquare_times(t0, c, 100);
335         fmul_fmul(t0, t0, c);
336         fsquare_fsquare_times_inplace(t0, 50);
337         fmul_fmul(t0, t0, b);
338         fsquare_fsquare_times_inplace(t0, 5);
339         fmul_fmul(out, t0, a);
340 }
341
342 static __always_inline void fsum(u64 *a, u64 *b)
343 {
344         a[0] += b[0];
345         a[1] += b[1];
346         a[2] += b[2];
347         a[3] += b[3];
348         a[4] += b[4];
349 }
350
351 static __always_inline void fdifference(u64 *a, u64 *b)
352 {
353         u64 tmp[5] = { 0 };
354         u64 b0;
355         u64 b1;
356         u64 b2;
357         u64 b3;
358         u64 b4;
359         memcpy(tmp, b, 5 * sizeof(*b));
360         b0 = tmp[0];
361         b1 = tmp[1];
362         b2 = tmp[2];
363         b3 = tmp[3];
364         b4 = tmp[4];
365         tmp[0] = b0 + 0x3fffffffffff68LLU;
366         tmp[1] = b1 + 0x3ffffffffffff8LLU;
367         tmp[2] = b2 + 0x3ffffffffffff8LLU;
368         tmp[3] = b3 + 0x3ffffffffffff8LLU;
369         tmp[4] = b4 + 0x3ffffffffffff8LLU;
370         {
371                 u64 xi = a[0];
372                 u64 yi = tmp[0];
373                 a[0] = yi - xi;
374         }
375         {
376                 u64 xi = a[1];
377                 u64 yi = tmp[1];
378                 a[1] = yi - xi;
379         }
380         {
381                 u64 xi = a[2];
382                 u64 yi = tmp[2];
383                 a[2] = yi - xi;
384         }
385         {
386                 u64 xi = a[3];
387                 u64 yi = tmp[3];
388                 a[3] = yi - xi;
389         }
390         {
391                 u64 xi = a[4];
392                 u64 yi = tmp[4];
393                 a[4] = yi - xi;
394         }
395 }
396
397 static __always_inline void fscalar(u64 *output, u64 *b, u64 s)
398 {
399         u128 tmp[5];
400         u128 b4;
401         u128 b0;
402         u128 b4_;
403         u128 b0_;
404         {
405                 u64 xi = b[0];
406                 tmp[0] = ((u128)(xi) * (s));
407         }
408         {
409                 u64 xi = b[1];
410                 tmp[1] = ((u128)(xi) * (s));
411         }
412         {
413                 u64 xi = b[2];
414                 tmp[2] = ((u128)(xi) * (s));
415         }
416         {
417                 u64 xi = b[3];
418                 tmp[3] = ((u128)(xi) * (s));
419         }
420         {
421                 u64 xi = b[4];
422                 tmp[4] = ((u128)(xi) * (s));
423         }
424         fproduct_carry_wide_(tmp);
425         b4 = tmp[4];
426         b0 = tmp[0];
427         b4_ = ((b4) & (((u128)(0x7ffffffffffffLLU))));
428         b0_ = ((b0) + (((u128)(19) * (((u64)(((b4) >> (51))))))));
429         tmp[4] = b4_;
430         tmp[0] = b0_;
431         fproduct_copy_from_wide_(output, tmp);
432 }
433
434 static __always_inline void fmul(u64 *output, u64 *a, u64 *b)
435 {
436         fmul_fmul(output, a, b);
437 }
438
439 static __always_inline void crecip(u64 *output, u64 *input)
440 {
441         crecip_crecip(output, input);
442 }
443
444 static __always_inline void point_swap_conditional_step(u64 *a, u64 *b,
445                                                         u64 swap1, u32 ctr)
446 {
447         u32 i = ctr - 1;
448         u64 ai = a[i];
449         u64 bi = b[i];
450         u64 x = swap1 & (ai ^ bi);
451         u64 ai1 = ai ^ x;
452         u64 bi1 = bi ^ x;
453         a[i] = ai1;
454         b[i] = bi1;
455 }
456
457 static __always_inline void point_swap_conditional5(u64 *a, u64 *b, u64 swap1)
458 {
459         point_swap_conditional_step(a, b, swap1, 5);
460         point_swap_conditional_step(a, b, swap1, 4);
461         point_swap_conditional_step(a, b, swap1, 3);
462         point_swap_conditional_step(a, b, swap1, 2);
463         point_swap_conditional_step(a, b, swap1, 1);
464 }
465
466 static __always_inline void point_swap_conditional(u64 *a, u64 *b, u64 iswap)
467 {
468         u64 swap1 = 0 - iswap;
469         point_swap_conditional5(a, b, swap1);
470         point_swap_conditional5(a + 5, b + 5, swap1);
471 }
472
473 static __always_inline void point_copy(u64 *output, u64 *input)
474 {
475         memcpy(output, input, 5 * sizeof(*input));
476         memcpy(output + 5, input + 5, 5 * sizeof(*input));
477 }
478
479 static __always_inline void addanddouble_fmonty(u64 *pp, u64 *ppq, u64 *p,
480                                                 u64 *pq, u64 *qmqp)
481 {
482         u64 *qx = qmqp;
483         u64 *x2 = pp;
484         u64 *z2 = pp + 5;
485         u64 *x3 = ppq;
486         u64 *z3 = ppq + 5;
487         u64 *x = p;
488         u64 *z = p + 5;
489         u64 *xprime = pq;
490         u64 *zprime = pq + 5;
491         u64 buf[40] = { 0 };
492         u64 *origx = buf;
493         u64 *origxprime0 = buf + 5;
494         u64 *xxprime0;
495         u64 *zzprime0;
496         u64 *origxprime;
497         xxprime0 = buf + 25;
498         zzprime0 = buf + 30;
499         memcpy(origx, x, 5 * sizeof(*x));
500         fsum(x, z);
501         fdifference(z, origx);
502         memcpy(origxprime0, xprime, 5 * sizeof(*xprime));
503         fsum(xprime, zprime);
504         fdifference(zprime, origxprime0);
505         fmul(xxprime0, xprime, z);
506         fmul(zzprime0, x, zprime);
507         origxprime = buf + 5;
508         {
509                 u64 *xx0;
510                 u64 *zz0;
511                 u64 *xxprime;
512                 u64 *zzprime;
513                 u64 *zzzprime;
514                 xx0 = buf + 15;
515                 zz0 = buf + 20;
516                 xxprime = buf + 25;
517                 zzprime = buf + 30;
518                 zzzprime = buf + 35;
519                 memcpy(origxprime, xxprime, 5 * sizeof(*xxprime));
520                 fsum(xxprime, zzprime);
521                 fdifference(zzprime, origxprime);
522                 fsquare_fsquare_times(x3, xxprime, 1);
523                 fsquare_fsquare_times(zzzprime, zzprime, 1);
524                 fmul(z3, zzzprime, qx);
525                 fsquare_fsquare_times(xx0, x, 1);
526                 fsquare_fsquare_times(zz0, z, 1);
527                 {
528                         u64 *zzz;
529                         u64 *xx;
530                         u64 *zz;
531                         u64 scalar;
532                         zzz = buf + 10;
533                         xx = buf + 15;
534                         zz = buf + 20;
535                         fmul(x2, xx, zz);
536                         fdifference(zz, xx);
537                         scalar = 121665;
538                         fscalar(zzz, zz, scalar);
539                         fsum(zzz, xx);
540                         fmul(z2, zzz, zz);
541                 }
542         }
543 }
544
545 static __always_inline void
546 ladder_smallloop_cmult_small_loop_step(u64 *nq, u64 *nqpq, u64 *nq2, u64 *nqpq2,
547                                        u64 *q, u8 byt)
548 {
549         u64 bit0 = (u64)(byt >> 7);
550         u64 bit;
551         point_swap_conditional(nq, nqpq, bit0);
552         addanddouble_fmonty(nq2, nqpq2, nq, nqpq, q);
553         bit = (u64)(byt >> 7);
554         point_swap_conditional(nq2, nqpq2, bit);
555 }
556
557 static __always_inline void
558 ladder_smallloop_cmult_small_loop_double_step(u64 *nq, u64 *nqpq, u64 *nq2,
559                                               u64 *nqpq2, u64 *q, u8 byt)
560 {
561         u8 byt1;
562         ladder_smallloop_cmult_small_loop_step(nq, nqpq, nq2, nqpq2, q, byt);
563         byt1 = byt << 1;
564         ladder_smallloop_cmult_small_loop_step(nq2, nqpq2, nq, nqpq, q, byt1);
565 }
566
567 static __always_inline void
568 ladder_smallloop_cmult_small_loop(u64 *nq, u64 *nqpq, u64 *nq2, u64 *nqpq2,
569                                   u64 *q, u8 byt, u32 i)
570 {
571         while (i--) {
572                 ladder_smallloop_cmult_small_loop_double_step(nq, nqpq, nq2,
573                                                               nqpq2, q, byt);
574                 byt <<= 2;
575         }
576 }
577
578 static __always_inline void ladder_bigloop_cmult_big_loop(u8 *n1, u64 *nq,
579                                                           u64 *nqpq, u64 *nq2,
580                                                           u64 *nqpq2, u64 *q,
581                                                           u32 i)
582 {
583         while (i--) {
584                 u8 byte = n1[i];
585                 ladder_smallloop_cmult_small_loop(nq, nqpq, nq2, nqpq2, q,
586                                                   byte, 4);
587         }
588 }
589
590 static void ladder_cmult(u64 *result, u8 *n1, u64 *q)
591 {
592         u64 point_buf[40] = { 0 };
593         u64 *nq = point_buf;
594         u64 *nqpq = point_buf + 10;
595         u64 *nq2 = point_buf + 20;
596         u64 *nqpq2 = point_buf + 30;
597         point_copy(nqpq, q);
598         nq[0] = 1;
599         ladder_bigloop_cmult_big_loop(n1, nq, nqpq, nq2, nqpq2, q, 32);
600         point_copy(result, nq);
601 }
602
603 static __always_inline void format_fexpand(u64 *output, const u8 *input)
604 {
605         const u8 *x00 = input + 6;
606         const u8 *x01 = input + 12;
607         const u8 *x02 = input + 19;
608         const u8 *x0 = input + 24;
609         u64 i0, i1, i2, i3, i4, output0, output1, output2, output3, output4;
610         i0 = get_unaligned_le64(input);
611         i1 = get_unaligned_le64(x00);
612         i2 = get_unaligned_le64(x01);
613         i3 = get_unaligned_le64(x02);
614         i4 = get_unaligned_le64(x0);
615         output0 = i0 & 0x7ffffffffffffLLU;
616         output1 = i1 >> 3 & 0x7ffffffffffffLLU;
617         output2 = i2 >> 6 & 0x7ffffffffffffLLU;
618         output3 = i3 >> 1 & 0x7ffffffffffffLLU;
619         output4 = i4 >> 12 & 0x7ffffffffffffLLU;
620         output[0] = output0;
621         output[1] = output1;
622         output[2] = output2;
623         output[3] = output3;
624         output[4] = output4;
625 }
626
627 static __always_inline void format_fcontract_first_carry_pass(u64 *input)
628 {
629         u64 t0 = input[0];
630         u64 t1 = input[1];
631         u64 t2 = input[2];
632         u64 t3 = input[3];
633         u64 t4 = input[4];
634         u64 t1_ = t1 + (t0 >> 51);
635         u64 t0_ = t0 & 0x7ffffffffffffLLU;
636         u64 t2_ = t2 + (t1_ >> 51);
637         u64 t1__ = t1_ & 0x7ffffffffffffLLU;
638         u64 t3_ = t3 + (t2_ >> 51);
639         u64 t2__ = t2_ & 0x7ffffffffffffLLU;
640         u64 t4_ = t4 + (t3_ >> 51);
641         u64 t3__ = t3_ & 0x7ffffffffffffLLU;
642         input[0] = t0_;
643         input[1] = t1__;
644         input[2] = t2__;
645         input[3] = t3__;
646         input[4] = t4_;
647 }
648
649 static __always_inline void format_fcontract_first_carry_full(u64 *input)
650 {
651         format_fcontract_first_carry_pass(input);
652         modulo_carry_top(input);
653 }
654
655 static __always_inline void format_fcontract_second_carry_pass(u64 *input)
656 {
657         u64 t0 = input[0];
658         u64 t1 = input[1];
659         u64 t2 = input[2];
660         u64 t3 = input[3];
661         u64 t4 = input[4];
662         u64 t1_ = t1 + (t0 >> 51);
663         u64 t0_ = t0 & 0x7ffffffffffffLLU;
664         u64 t2_ = t2 + (t1_ >> 51);
665         u64 t1__ = t1_ & 0x7ffffffffffffLLU;
666         u64 t3_ = t3 + (t2_ >> 51);
667         u64 t2__ = t2_ & 0x7ffffffffffffLLU;
668         u64 t4_ = t4 + (t3_ >> 51);
669         u64 t3__ = t3_ & 0x7ffffffffffffLLU;
670         input[0] = t0_;
671         input[1] = t1__;
672         input[2] = t2__;
673         input[3] = t3__;
674         input[4] = t4_;
675 }
676
677 static __always_inline void format_fcontract_second_carry_full(u64 *input)
678 {
679         u64 i0;
680         u64 i1;
681         u64 i0_;
682         u64 i1_;
683         format_fcontract_second_carry_pass(input);
684         modulo_carry_top(input);
685         i0 = input[0];
686         i1 = input[1];
687         i0_ = i0 & 0x7ffffffffffffLLU;
688         i1_ = i1 + (i0 >> 51);
689         input[0] = i0_;
690         input[1] = i1_;
691 }
692
693 static __always_inline void format_fcontract_trim(u64 *input)
694 {
695         u64 a0 = input[0];
696         u64 a1 = input[1];
697         u64 a2 = input[2];
698         u64 a3 = input[3];
699         u64 a4 = input[4];
700         u64 mask0 = u64_gte_mask(a0, 0x7ffffffffffedLLU);
701         u64 mask1 = u64_eq_mask(a1, 0x7ffffffffffffLLU);
702         u64 mask2 = u64_eq_mask(a2, 0x7ffffffffffffLLU);
703         u64 mask3 = u64_eq_mask(a3, 0x7ffffffffffffLLU);
704         u64 mask4 = u64_eq_mask(a4, 0x7ffffffffffffLLU);
705         u64 mask = (((mask0 & mask1) & mask2) & mask3) & mask4;
706         u64 a0_ = a0 - (0x7ffffffffffedLLU & mask);
707         u64 a1_ = a1 - (0x7ffffffffffffLLU & mask);
708         u64 a2_ = a2 - (0x7ffffffffffffLLU & mask);
709         u64 a3_ = a3 - (0x7ffffffffffffLLU & mask);
710         u64 a4_ = a4 - (0x7ffffffffffffLLU & mask);
711         input[0] = a0_;
712         input[1] = a1_;
713         input[2] = a2_;
714         input[3] = a3_;
715         input[4] = a4_;
716 }
717
718 static __always_inline void format_fcontract_store(u8 *output, u64 *input)
719 {
720         u64 t0 = input[0];
721         u64 t1 = input[1];
722         u64 t2 = input[2];
723         u64 t3 = input[3];
724         u64 t4 = input[4];
725         u64 o0 = t1 << 51 | t0;
726         u64 o1 = t2 << 38 | t1 >> 13;
727         u64 o2 = t3 << 25 | t2 >> 26;
728         u64 o3 = t4 << 12 | t3 >> 39;
729         u8 *b0 = output;
730         u8 *b1 = output + 8;
731         u8 *b2 = output + 16;
732         u8 *b3 = output + 24;
733         put_unaligned_le64(o0, b0);
734         put_unaligned_le64(o1, b1);
735         put_unaligned_le64(o2, b2);
736         put_unaligned_le64(o3, b3);
737 }
738
739 static __always_inline void format_fcontract(u8 *output, u64 *input)
740 {
741         format_fcontract_first_carry_full(input);
742         format_fcontract_second_carry_full(input);
743         format_fcontract_trim(input);
744         format_fcontract_store(output, input);
745 }
746
747 static __always_inline void format_scalar_of_point(u8 *scalar, u64 *point)
748 {
749         u64 *x = point;
750         u64 *z = point + 5;
751         u64 buf[10] __aligned(32) = { 0 };
752         u64 *zmone = buf;
753         u64 *sc = buf + 5;
754         crecip(zmone, z);
755         fmul(sc, x, zmone);
756         format_fcontract(scalar, sc);
757 }
758
759 void curve25519_generic(u8 mypublic[CURVE25519_KEY_SIZE],
760                         const u8 secret[CURVE25519_KEY_SIZE],
761                         const u8 basepoint[CURVE25519_KEY_SIZE])
762 {
763         u64 buf0[10] __aligned(32) = { 0 };
764         u64 *x0 = buf0;
765         u64 *z = buf0 + 5;
766         u64 *q;
767         format_fexpand(x0, basepoint);
768         z[0] = 1;
769         q = buf0;
770         {
771                 u8 e[32] __aligned(32) = { 0 };
772                 u8 *scalar;
773                 memcpy(e, secret, 32);
774                 curve25519_clamp_secret(e);
775                 scalar = e;
776                 {
777                         u64 buf[15] = { 0 };
778                         u64 *nq = buf;
779                         u64 *x = nq;
780                         x[0] = 1;
781                         ladder_cmult(nq, scalar, q);
782                         format_scalar_of_point(mypublic, nq);
783                         memzero_explicit(buf, sizeof(buf));
784                 }
785                 memzero_explicit(e, sizeof(e));
786         }
787         memzero_explicit(buf0, sizeof(buf0));
788 }