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 }