/* Copyright (c) 2020, Google Inc.

 *

 * Permission to use, copy, modify, and/or distribute this software for any

 * purpose with or without fee is hereby granted, provided that the above

 * copyright notice and this permission notice appear in all copies.

 *

 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES

 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF

 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY

 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES

 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION

 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN

 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */

// Some of this code is taken from the ref10 version of Ed25519 in SUPERCOP

// 20141124 (http://bench.cr.yp.to/supercop.html). That code is released as

// public domain. Other parts have been replaced to call into code generated by

// Fiat (https://github.com/mit-plv/fiat-crypto) in //third_party/fiat.

//

// The field functions are shared by Ed25519 and X25519 where possible.

#include <ring-core/mem.h>

#include "internal.h"

#include "../internal.h"

#if defined(_MSC_VER) && !defined(__clang__)

// '=': conversion from 'int64_t' to 'int32_t', possible loss of data

#pragma warning(disable: 4242)

// '=': conversion from 'int32_t' to 'uint8_t', possible loss of data

#pragma warning(disable: 4244)

#endif

#if defined(__GNUC__) || defined(__clang__)

#pragma GCC diagnostic ignored "-Wconversion"

#pragma GCC diagnostic ignored "-Wsign-conversion"

#endif

#if defined(__GNUC__) && !defined(__clang__)

#pragma GCC diagnostic ignored "-Winline"

#endif

// Various pre-computed constants.

#include "./curve25519_tables.h"

#if defined(BORINGSSL_HAS_UINT128)

#if defined(__GNUC__)

#pragma GCC diagnostic ignored "-Wpedantic"

#endif

#include "../../third_party/fiat/curve25519_64.h"

#elif defined(OPENSSL_64_BIT)

#include "../../third_party/fiat/curve25519_64_msvc.h"

#else

#include "../../third_party/fiat/curve25519_32.h"

#endif

// Low-level intrinsic operations

static uint64_t load_3(const uint8_t *in) {

  uint64_t result;

  result = (uint64_t)in[0];

  result |= ((uint64_t)in[1]) << 8;

  result |= ((uint64_t)in[2]) << 16;

  return result;

}

static uint64_t load_4(const uint8_t *in) {

  uint64_t result;

  result = (uint64_t)in[0];

  result |= ((uint64_t)in[1]) << 8;

  result |= ((uint64_t)in[2]) << 16;

  result |= ((uint64_t)in[3]) << 24;

  return result;

}

// Field operations.

#if defined(OPENSSL_64_BIT)

// assert_fe asserts that |f| satisfies bounds:

//

//  [[0x0 ~> 0x8cccccccccccc],

//   [0x0 ~> 0x8cccccccccccc],

//   [0x0 ~> 0x8cccccccccccc],

//   [0x0 ~> 0x8cccccccccccc],

//   [0x0 ~> 0x8cccccccccccc]]

//

// See comments in curve25519_64.h for which functions use these bounds for

// inputs or outputs.

#define assert_fe(f)                                                    \

  do {                                                                  \

    for (unsigned _assert_fe_i = 0; _assert_fe_i < 5; _assert_fe_i++) { \

      dev_assert_secret(f[_assert_fe_i] <= UINT64_C(0x8cccccccccccc));  \

    }                                                                   \

  } while (0)

// assert_fe_loose asserts that |f| satisfies bounds:

//

//  [[0x0 ~> 0x1a666666666664],

//   [0x0 ~> 0x1a666666666664],

//   [0x0 ~> 0x1a666666666664],

//   [0x0 ~> 0x1a666666666664],

//   [0x0 ~> 0x1a666666666664]]

//

// See comments in curve25519_64.h for which functions use these bounds for

// inputs or outputs.

#define assert_fe_loose(f)                                              \

  do {                                                                  \

    for (unsigned _assert_fe_i = 0; _assert_fe_i < 5; _assert_fe_i++) { \

      dev_assert_secret(f[_assert_fe_i] <= UINT64_C(0x1a666666666664)); \

    }                                                                   \

  } while (0)

#else

// assert_fe asserts that |f| satisfies bounds:

//

//  [[0x0 ~> 0x4666666], [0x0 ~> 0x2333333],

//   [0x0 ~> 0x4666666], [0x0 ~> 0x2333333],

//   [0x0 ~> 0x4666666], [0x0 ~> 0x2333333],

//   [0x0 ~> 0x4666666], [0x0 ~> 0x2333333],

//   [0x0 ~> 0x4666666], [0x0 ~> 0x2333333]]

//

// See comments in curve25519_32.h for which functions use these bounds for

// inputs or outputs.

#define assert_fe(f)                                                     \

  do {                                                                   \

    for (unsigned _assert_fe_i = 0; _assert_fe_i < 10; _assert_fe_i++) { \

      dev_assert_secret(f[_assert_fe_i] <=                               \

             ((_assert_fe_i & 1) ? 0x2333333u : 0x4666666u));            \

    }                                                                    \

  } while (0)

// assert_fe_loose asserts that |f| satisfies bounds:

//

//  [[0x0 ~> 0xd333332], [0x0 ~> 0x6999999],

//   [0x0 ~> 0xd333332], [0x0 ~> 0x6999999],

//   [0x0 ~> 0xd333332], [0x0 ~> 0x6999999],

//   [0x0 ~> 0xd333332], [0x0 ~> 0x6999999],

//   [0x0 ~> 0xd333332], [0x0 ~> 0x6999999]]

//

// See comments in curve25519_32.h for which functions use these bounds for

// inputs or outputs.

#define assert_fe_loose(f)                                               \

  do {                                                                   \

    for (unsigned _assert_fe_i = 0; _assert_fe_i < 10; _assert_fe_i++) { \

      dev_assert_secret(f[_assert_fe_i] <=                               \

             ((_assert_fe_i & 1) ? 0x6999999u : 0xd333332u));            \

    }                                                                    \

  } while (0)

#endif  // OPENSSL_64_BIT

OPENSSL_STATIC_ASSERT(sizeof(fe) == sizeof(fe_limb_t) * FE_NUM_LIMBS,

                      "fe_limb_t[FE_NUM_LIMBS] is inconsistent with fe");

static void fe_frombytes_strict(fe *h, const uint8_t s[32]) {

  // |fiat_25519_from_bytes| requires the top-most bit be clear.

  dev_assert_secret((s[31] & 0x80) == 0);

  fiat_25519_from_bytes(h->v, s);

  assert_fe(h->v);

}

static void fe_frombytes(fe *h, const uint8_t s[32]) {

  uint8_t s_copy[32];

  OPENSSL_memcpy(s_copy, s, 32);

  s_copy[31] &= 0x7f;

  fe_frombytes_strict(h, s_copy);

}

static void fe_tobytes(uint8_t s[32], const fe *f) {

  assert_fe(f->v);

  fiat_25519_to_bytes(s, f->v);

}

// h = 0

static void fe_0(fe *h) {

  OPENSSL_memset(h, 0, sizeof(fe));

}

#if defined(OPENSSL_SMALL)

static void fe_loose_0(fe_loose *h) {

  OPENSSL_memset(h, 0, sizeof(fe_loose));

}

#endif

// h = 1

static void fe_1(fe *h) {

  OPENSSL_memset(h, 0, sizeof(fe));

  h->v[0] = 1;

}

#if defined(OPENSSL_SMALL)

static void fe_loose_1(fe_loose *h) {

  OPENSSL_memset(h, 0, sizeof(fe_loose));

  h->v[0] = 1;

}

#endif

// h = f + g

// Can overlap h with f or g.

static void fe_add(fe_loose *h, const fe *f, const fe *g) {

  assert_fe(f->v);

  assert_fe(g->v);

  fiat_25519_add(h->v, f->v, g->v);

  assert_fe_loose(h->v);

}

// h = f - g

// Can overlap h with f or g.

static void fe_sub(fe_loose *h, const fe *f, const fe *g) {

  assert_fe(f->v);

  assert_fe(g->v);

  fiat_25519_sub(h->v, f->v, g->v);

  assert_fe_loose(h->v);

}

static void fe_carry(fe *h, const fe_loose* f) {

  assert_fe_loose(f->v);

  fiat_25519_carry(h->v, f->v);

  assert_fe(h->v);

}

static void fe_mul_impl(fe_limb_t out[FE_NUM_LIMBS],

                        const fe_limb_t in1[FE_NUM_LIMBS],

                        const fe_limb_t in2[FE_NUM_LIMBS]) {

  assert_fe_loose(in1);

  assert_fe_loose(in2);

  fiat_25519_carry_mul(out, in1, in2);

  assert_fe(out);

}

static void fe_mul_ltt(fe_loose *h, const fe *f, const fe *g) {

  fe_mul_impl(h->v, f->v, g->v);

}

#if defined(OPENSSL_SMALL)

static void fe_mul_llt(fe_loose *h, const fe_loose *f, const fe *g) {

  fe_mul_impl(h->v, f->v, g->v);

}

#endif

static void fe_mul_ttt(fe *h, const fe *f, const fe *g) {

  fe_mul_impl(h->v, f->v, g->v);

}

static void fe_mul_tlt(fe *h, const fe_loose *f, const fe *g) {

  fe_mul_impl(h->v, f->v, g->v);

}

static void fe_mul_ttl(fe *h, const fe *f, const fe_loose *g) {

  fe_mul_impl(h->v, f->v, g->v);

}

static void fe_mul_tll(fe *h, const fe_loose *f, const fe_loose *g) {

  fe_mul_impl(h->v, f->v, g->v);

}

static void fe_sq_tl(fe *h, const fe_loose *f) {

  assert_fe_loose(f->v);

  fiat_25519_carry_square(h->v, f->v);

  assert_fe(h->v);

}

static void fe_sq_tt(fe *h, const fe *f) {

  assert_fe_loose(f->v);

  fiat_25519_carry_square(h->v, f->v);

  assert_fe(h->v);

}

// Replace (f,g) with (g,f) if b == 1;

// replace (f,g) with (f,g) if b == 0.

//

// Preconditions: b in {0,1}.

static void fe_cswap(fe *f, fe *g, fe_limb_t b) {

  b = 0-b;

  for (unsigned i = 0; i < FE_NUM_LIMBS; i++) {

    fe_limb_t x = f->v[i] ^ g->v[i];

    x &= b;

    f->v[i] ^= x;

    g->v[i] ^= x;

  }

}

static void fe_mul121666(fe *h, const fe_loose *f) {

  assert_fe_loose(f->v);

  fiat_25519_carry_scmul_121666(h->v, f->v);

  assert_fe(h->v);

}

// h = -f

static void fe_neg(fe_loose *h, const fe *f) {

  assert_fe(f->v);

  fiat_25519_opp(h->v, f->v);

  assert_fe_loose(h->v);

}

// Replace (f,g) with (g,g) if b == 1;

// replace (f,g) with (f,g) if b == 0.

//

// Preconditions: b in {0,1}.

static void fe_cmov(fe_loose *f, const fe_loose *g, fe_limb_t b) {

  // Silence an unused function warning. |fiat_25519_selectznz| isn't quite the

  // calling convention the rest of this code wants, so implement it by hand.

  //

  // TODO(davidben): Switch to fiat's calling convention, or ask fiat to emit a

  // different one.

  (void)fiat_25519_selectznz;

  b = 0-b;

  for (unsigned i = 0; i < FE_NUM_LIMBS; i++) {

    fe_limb_t x = f->v[i] ^ g->v[i];

    x &= b;

    f->v[i] ^= x;

  }

}

// h = f

static void fe_copy(fe *h, const fe *f) {

  fe_limbs_copy(h->v, f->v);

}

static void fe_copy_lt(fe_loose *h, const fe *f) {

  OPENSSL_STATIC_ASSERT(sizeof(fe_loose) == sizeof(fe), "fe and fe_loose mismatch");

  fe_limbs_copy(h->v, f->v);

}

static void fe_loose_invert(fe *out, const fe_loose *z) {

  fe t0;

  fe t1;

  fe t2;

  fe t3;

  int i;

  fe_sq_tl(&t0, z);

  fe_sq_tt(&t1, &t0);

  for (i = 1; i < 2; ++i) {

    fe_sq_tt(&t1, &t1);

  }

  fe_mul_tlt(&t1, z, &t1);

  fe_mul_ttt(&t0, &t0, &t1);

  fe_sq_tt(&t2, &t0);

  fe_mul_ttt(&t1, &t1, &t2);

  fe_sq_tt(&t2, &t1);

  for (i = 1; i < 5; ++i) {

    fe_sq_tt(&t2, &t2);

  }

  fe_mul_ttt(&t1, &t2, &t1);

  fe_sq_tt(&t2, &t1);

  for (i = 1; i < 10; ++i) {

    fe_sq_tt(&t2, &t2);

  }

  fe_mul_ttt(&t2, &t2, &t1);

  fe_sq_tt(&t3, &t2);

  for (i = 1; i < 20; ++i) {

    fe_sq_tt(&t3, &t3);

  }

  fe_mul_ttt(&t2, &t3, &t2);

  fe_sq_tt(&t2, &t2);

  for (i = 1; i < 10; ++i) {

    fe_sq_tt(&t2, &t2);

  }

  fe_mul_ttt(&t1, &t2, &t1);

  fe_sq_tt(&t2, &t1);

  for (i = 1; i < 50; ++i) {

    fe_sq_tt(&t2, &t2);

  }

  fe_mul_ttt(&t2, &t2, &t1);

  fe_sq_tt(&t3, &t2);

  for (i = 1; i < 100; ++i) {

    fe_sq_tt(&t3, &t3);

  }

  fe_mul_ttt(&t2, &t3, &t2);

  fe_sq_tt(&t2, &t2);

  for (i = 1; i < 50; ++i) {

    fe_sq_tt(&t2, &t2);

  }

  fe_mul_ttt(&t1, &t2, &t1);

  fe_sq_tt(&t1, &t1);

  for (i = 1; i < 5; ++i) {

    fe_sq_tt(&t1, &t1);

  }

  fe_mul_ttt(out, &t1, &t0);

}

static void fe_invert(fe *out, const fe *z) {

  fe_loose l;

  fe_copy_lt(&l, z);

  fe_loose_invert(out, &l);

}

// return 0 if f == 0

// return 1 if f != 0

static int fe_isnonzero(const fe_loose *f) {

  fe tight;

  fe_carry(&tight, f);

  uint8_t s[32];

  fe_tobytes(s, &tight);

  static const uint8_t zero[32] = {0};

  return CRYPTO_memcmp(s, zero, sizeof(zero)) != 0;

}

// return 1 if f is in {1,3,5,...,q-2}

// return 0 if f is in {0,2,4,...,q-1}

static int fe_isnegative(const fe *f) {

  uint8_t s[32];

  fe_tobytes(s, f);

  return s[0] & 1;

}

static void fe_sq2_tt(fe *h, const fe *f) {

  // h = f^2

  fe_sq_tt(h, f);

  // h = h + h

  fe_loose tmp;

  fe_add(&tmp, h, h);

  fe_carry(h, &tmp);

}

static void fe_pow22523(fe *out, const fe *z) {

  fe t0;

  fe t1;

  fe t2;

  int i;

  fe_sq_tt(&t0, z);

  fe_sq_tt(&t1, &t0);

  for (i = 1; i < 2; ++i) {

    fe_sq_tt(&t1, &t1);

  }

  fe_mul_ttt(&t1, z, &t1);

  fe_mul_ttt(&t0, &t0, &t1);

  fe_sq_tt(&t0, &t0);

  fe_mul_ttt(&t0, &t1, &t0);

  fe_sq_tt(&t1, &t0);

  for (i = 1; i < 5; ++i) {

    fe_sq_tt(&t1, &t1);

  }

  fe_mul_ttt(&t0, &t1, &t0);

  fe_sq_tt(&t1, &t0);

  for (i = 1; i < 10; ++i) {

    fe_sq_tt(&t1, &t1);

  }

  fe_mul_ttt(&t1, &t1, &t0);

  fe_sq_tt(&t2, &t1);

  for (i = 1; i < 20; ++i) {

    fe_sq_tt(&t2, &t2);

  }

  fe_mul_ttt(&t1, &t2, &t1);

  fe_sq_tt(&t1, &t1);

  for (i = 1; i < 10; ++i) {

    fe_sq_tt(&t1, &t1);

  }

  fe_mul_ttt(&t0, &t1, &t0);

  fe_sq_tt(&t1, &t0);

  for (i = 1; i < 50; ++i) {

    fe_sq_tt(&t1, &t1);

  }

  fe_mul_ttt(&t1, &t1, &t0);

  fe_sq_tt(&t2, &t1);

  for (i = 1; i < 100; ++i) {

    fe_sq_tt(&t2, &t2);

  }

  fe_mul_ttt(&t1, &t2, &t1);

  fe_sq_tt(&t1, &t1);

  for (i = 1; i < 50; ++i) {

    fe_sq_tt(&t1, &t1);

  }

  fe_mul_ttt(&t0, &t1, &t0);

  fe_sq_tt(&t0, &t0);

  for (i = 1; i < 2; ++i) {

    fe_sq_tt(&t0, &t0);

  }

  fe_mul_ttt(out, &t0, z);

}

// Group operations.

int x25519_ge_frombytes_vartime(ge_p3 *h, const uint8_t s[32]) {

  fe u;

  fe_loose v;

  fe w;

  fe vxx;

  fe_loose check;

  fe_frombytes(&h->Y, s);

  fe_1(&h->Z);

  fe_sq_tt(&w, &h->Y);

  fe_mul_ttt(&vxx, &w, &d);

  fe_sub(&v, &w, &h->Z);  // u = y^2-1

  fe_carry(&u, &v);

  fe_add(&v, &vxx, &h->Z);  // v = dy^2+1

  fe_mul_ttl(&w, &u, &v);  // w = u*v

  fe_pow22523(&h->X, &w);  // x = w^((q-5)/8)

  fe_mul_ttt(&h->X, &h->X, &u);  // x = u*w^((q-5)/8)

  fe_sq_tt(&vxx, &h->X);

  fe_mul_ttl(&vxx, &vxx, &v);

  fe_sub(&check, &vxx, &u);

  if (fe_isnonzero(&check)) {

    fe_add(&check, &vxx, &u);

    if (fe_isnonzero(&check)) {

      return 0;

    }

    fe_mul_ttt(&h->X, &h->X, &sqrtm1);

  }

  if (fe_isnegative(&h->X) != (s[31] >> 7)) {

    fe_loose t;

    fe_neg(&t, &h->X);

    fe_carry(&h->X, &t);

  }

  fe_mul_ttt(&h->T, &h->X, &h->Y);

  return 1;

}

static void ge_p2_0(ge_p2 *h) {

  fe_0(&h->X);

  fe_1(&h->Y);

  fe_1(&h->Z);

}

static void ge_p3_0(ge_p3 *h) {

  fe_0(&h->X);

  fe_1(&h->Y);

  fe_1(&h->Z);

  fe_0(&h->T);

}

#if defined(OPENSSL_SMALL)

static void ge_precomp_0(ge_precomp *h) {

  fe_loose_1(&h->yplusx);

  fe_loose_1(&h->yminusx);

  fe_loose_0(&h->xy2d);

}

#endif

// r = p

static void ge_p3_to_p2(ge_p2 *r, const ge_p3 *p) {

  fe_copy(&r->X, &p->X);

  fe_copy(&r->Y, &p->Y);

  fe_copy(&r->Z, &p->Z);

}

// r = p

static void x25519_ge_p3_to_cached(ge_cached *r, const ge_p3 *p) {

  fe_add(&r->YplusX, &p->Y, &p->X);

  fe_sub(&r->YminusX, &p->Y, &p->X);

  fe_copy_lt(&r->Z, &p->Z);

  fe_mul_ltt(&r->T2d, &p->T, &d2);

}

// r = p

static void x25519_ge_p1p1_to_p2(ge_p2 *r, const ge_p1p1 *p) {

  fe_mul_tll(&r->X, &p->X, &p->T);

  fe_mul_tll(&r->Y, &p->Y, &p->Z);

  fe_mul_tll(&r->Z, &p->Z, &p->T);

}

// r = p

static void x25519_ge_p1p1_to_p3(ge_p3 *r, const ge_p1p1 *p) {

  fe_mul_tll(&r->X, &p->X, &p->T);

  fe_mul_tll(&r->Y, &p->Y, &p->Z);

  fe_mul_tll(&r->Z, &p->Z, &p->T);

  fe_mul_tll(&r->T, &p->X, &p->Y);

}

// r = 2 * p

static void ge_p2_dbl(ge_p1p1 *r, const ge_p2 *p) {

  fe trX, trZ, trT;

  fe t0;

  fe_sq_tt(&trX, &p->X);

  fe_sq_tt(&trZ, &p->Y);

  fe_sq2_tt(&trT, &p->Z);

  fe_add(&r->Y, &p->X, &p->Y);

  fe_sq_tl(&t0, &r->Y);

  fe_add(&r->Y, &trZ, &trX);

  fe_sub(&r->Z, &trZ, &trX);

  fe_carry(&trZ, &r->Y);

  fe_sub(&r->X, &t0, &trZ);

  fe_carry(&trZ, &r->Z);

  fe_sub(&r->T, &trT, &trZ);

}

// r = 2 * p

static void ge_p3_dbl(ge_p1p1 *r, const ge_p3 *p) {

  ge_p2 q;

  ge_p3_to_p2(&q, p);

  ge_p2_dbl(r, &q);

}

// r = p + q

static void ge_madd(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) {

  fe trY, trZ, trT;

  fe_add(&r->X, &p->Y, &p->X);

  fe_sub(&r->Y, &p->Y, &p->X);

  fe_mul_tll(&trZ, &r->X, &q->yplusx);

  fe_mul_tll(&trY, &r->Y, &q->yminusx);

  fe_mul_tlt(&trT, &q->xy2d, &p->T);

  fe_add(&r->T, &p->Z, &p->Z);

  fe_sub(&r->X, &trZ, &trY);

  fe_add(&r->Y, &trZ, &trY);

  fe_carry(&trZ, &r->T);

  fe_add(&r->Z, &trZ, &trT);

  fe_sub(&r->T, &trZ, &trT);

}

// r = p - q

static void ge_msub(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) {

  fe trY, trZ, trT;

  fe_add(&r->X, &p->Y, &p->X);

  fe_sub(&r->Y, &p->Y, &p->X);

  fe_mul_tll(&trZ, &r->X, &q->yminusx);

  fe_mul_tll(&trY, &r->Y, &q->yplusx);

  fe_mul_tlt(&trT, &q->xy2d, &p->T);

  fe_add(&r->T, &p->Z, &p->Z);

  fe_sub(&r->X, &trZ, &trY);

  fe_add(&r->Y, &trZ, &trY);

  fe_carry(&trZ, &r->T);

  fe_sub(&r->Z, &trZ, &trT);

  fe_add(&r->T, &trZ, &trT);

}

// r = p + q

static void x25519_ge_add(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) {

  fe trX, trY, trZ, trT;

  fe_add(&r->X, &p->Y, &p->X);

  fe_sub(&r->Y, &p->Y, &p->X);

  fe_mul_tll(&trZ, &r->X, &q->YplusX);

  fe_mul_tll(&trY, &r->Y, &q->YminusX);

  fe_mul_tlt(&trT, &q->T2d, &p->T);

  fe_mul_ttl(&trX, &p->Z, &q->Z);

  fe_add(&r->T, &trX, &trX);

  fe_sub(&r->X, &trZ, &trY);

  fe_add(&r->Y, &trZ, &trY);

  fe_carry(&trZ, &r->T);

  fe_add(&r->Z, &trZ, &trT);

  fe_sub(&r->T, &trZ, &trT);

}

// r = p - q

static void x25519_ge_sub(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) {

  fe trX, trY, trZ, trT;

  fe_add(&r->X, &p->Y, &p->X);

  fe_sub(&r->Y, &p->Y, &p->X);

  fe_mul_tll(&trZ, &r->X, &q->YminusX);

  fe_mul_tll(&trY, &r->Y, &q->YplusX);

  fe_mul_tlt(&trT, &q->T2d, &p->T);

  fe_mul_ttl(&trX, &p->Z, &q->Z);

  fe_add(&r->T, &trX, &trX);

  fe_sub(&r->X, &trZ, &trY);

  fe_add(&r->Y, &trZ, &trY);

  fe_carry(&trZ, &r->T);

  fe_sub(&r->Z, &trZ, &trT);

  fe_add(&r->T, &trZ, &trT);

}

static void cmov(ge_precomp *t, const ge_precomp *u, uint8_t b) {

  fe_cmov(&t->yplusx, &u->yplusx, b);

  fe_cmov(&t->yminusx, &u->yminusx, b);

  fe_cmov(&t->xy2d, &u->xy2d, b);

}

#if defined(OPENSSL_SMALL)

static void x25519_ge_scalarmult_small_precomp(

    ge_p3 *h, const uint8_t a[32], const uint8_t precomp_table[15 * 2 * 32]) {

  // precomp_table is first expanded into matching |ge_precomp|

  // elements.

  ge_precomp multiples[15];

  unsigned i;

  for (i = 0; i < 15; i++) {

    // The precomputed table is assumed to already clear the top bit, so

    // |fe_frombytes_strict| may be used directly.

    const uint8_t *bytes = &precomp_table[i*(2 * 32)];

    fe x, y;

    fe_frombytes_strict(&x, bytes);

    fe_frombytes_strict(&y, bytes + 32);

    ge_precomp *out = &multiples[i];

    fe_add(&out->yplusx, &y, &x);

    fe_sub(&out->yminusx, &y, &x);

    fe_mul_ltt(&out->xy2d, &x, &y);

    fe_mul_llt(&out->xy2d, &out->xy2d, &d2);

  }

  // See the comment above |k25519SmallPrecomp| about the structure of the

  // precomputed elements. This loop does 64 additions and 64 doublings to

  // calculate the result.

  ge_p3_0(h);

  for (i = 63; i < 64; i--) {

    unsigned j;

    signed char index = 0;

    for (j = 0; j < 4; j++) {

      const uint8_t bit = 1 & (a[(8 * j) + (i / 8)] >> (i & 7));

      index |= (bit << j);

    }

    ge_precomp e;

    ge_precomp_0(&e);

    for (j = 1; j < 16; j++) {

      cmov(&e, &multiples[j-1], 1&constant_time_eq_w(index, j));

    }

    ge_cached cached;

    ge_p1p1 r;

    x25519_ge_p3_to_cached(&cached, h);

    x25519_ge_add(&r, h, &cached);

    x25519_ge_p1p1_to_p3(h, &r);

    ge_madd(&r, h, &e);

    x25519_ge_p1p1_to_p3(h, &r);

  }

}

void x25519_ge_scalarmult_base(ge_p3 *h, const uint8_t a[32], int use_adx) {

  (void)use_adx;

  x25519_ge_scalarmult_small_precomp(h, a, k25519SmallPrecomp);

}

#else

static void table_select(ge_precomp *t, const int pos, const signed char b) {

  uint8_t bnegative = constant_time_msb_w(b);

  uint8_t babs = b - ((bnegative & b) << 1);

  uint8_t t_bytes[3][32] = {

      {constant_time_is_zero_w(b) & 1}, {constant_time_is_zero_w(b) & 1}, {0}};

#if defined(__clang__) // materialize for vectorization, 6% speedup

  __asm__("" : "+m" (t_bytes) : /*no inputs*/);

#endif

  OPENSSL_STATIC_ASSERT(sizeof(t_bytes) == sizeof(k25519Precomp[pos][0]), "");

  for (int i = 0; i < 8; i++) {

    constant_time_conditional_memxor(t_bytes, k25519Precomp[pos][i],

                                     sizeof(t_bytes),

                                     constant_time_eq_w(babs, 1 + i));

  }

  fe yplusx, yminusx, xy2d;

  fe_frombytes_strict(&yplusx, t_bytes[0]);

  fe_frombytes_strict(&yminusx, t_bytes[1]);

  fe_frombytes_strict(&xy2d, t_bytes[2]);

  fe_copy_lt(&t->yplusx, &yplusx);

  fe_copy_lt(&t->yminusx, &yminusx);

  fe_copy_lt(&t->xy2d, &xy2d);

  ge_precomp minust;

  fe_copy_lt(&minust.yplusx, &yminusx);

  fe_copy_lt(&minust.yminusx, &yplusx);

  fe_neg(&minust.xy2d, &xy2d);

  cmov(t, &minust, bnegative>>7);

}

// h = a * B

// where a = a[0]+256*a[1]+...+256^31 a[31]

// B is the Ed25519 base point (x,4/5) with x positive.

//

// Preconditions:

//   a[31] <= 127

void x25519_ge_scalarmult_base(ge_p3 *h, const uint8_t a[32], int use_adx) {

#if defined(BORINGSSL_FE25519_ADX)

  if (use_adx) {

    uint8_t t[4][32];

    x25519_ge_scalarmult_base_adx(t, a);

    fiat_25519_from_bytes(h->X.v, t[0]);

    fiat_25519_from_bytes(h->Y.v, t[1]);

    fiat_25519_from_bytes(h->Z.v, t[2]);

    fiat_25519_from_bytes(h->T.v, t[3]);

    return;

  }

#else

  (void)use_adx;

#endif

  signed char e[64];

  signed char carry;

  ge_p1p1 r;

  ge_p2 s;

  ge_precomp t;

  int i;

  for (i = 0; i < 32; ++i) {

    e[2 * i + 0] = (a[i] >> 0) & 15;

    e[2 * i + 1] = (a[i] >> 4) & 15;

  }

  // each e[i] is between 0 and 15

  // e[63] is between 0 and 7

  carry = 0;

  for (i = 0; i < 63; ++i) {

    e[i] += carry;

    carry = e[i] + 8;

    carry >>= 4;

    e[i] -= carry << 4;

  }

  e[63] += carry;

  // each e[i] is between -8 and 8

  ge_p3_0(h);

  for (i = 1; i < 64; i += 2) {

    table_select(&t, i / 2, e[i]);

    ge_madd(&r, h, &t);

    x25519_ge_p1p1_to_p3(h, &r);

  }

  ge_p3_dbl(&r, h);

  x25519_ge_p1p1_to_p2(&s, &r);

  ge_p2_dbl(&r, &s);

  x25519_ge_p1p1_to_p2(&s, &r);

  ge_p2_dbl(&r, &s);

  x25519_ge_p1p1_to_p2(&s, &r);

  ge_p2_dbl(&r, &s);

  x25519_ge_p1p1_to_p3(h, &r);

  for (i = 0; i < 64; i += 2) {

    table_select(&t, i / 2, e[i]);

    ge_madd(&r, h, &t);

    x25519_ge_p1p1_to_p3(h, &r);

  }

}

#endif

static void slide(signed char *r, const uint8_t *a) {

  int i;

  int b;

  int k;

  for (i = 0; i < 256; ++i) {

    r[i] = 1 & (a[i >> 3] >> (i & 7));

  }

  for (i = 0; i < 256; ++i) {

    if (r[i]) {

      for (b = 1; b <= 6 && i + b < 256; ++b) {

        if (r[i + b]) {

          if (r[i] + (r[i + b] << b) <= 15) {

            r[i] += r[i + b] << b;

            r[i + b] = 0;

          } else if (r[i] - (r[i + b] << b) >= -15) {

            r[i] -= r[i + b] << b;

            for (k = i + b; k < 256; ++k) {

              if (!r[k]) {

                r[k] = 1;

                break;

              }

              r[k] = 0;

            }

          } else {

            break;

          }

        }

      }

    }

  }

}

// r = a * A + b * B

// where a = a[0]+256*a[1]+...+256^31 a[31].

// and b = b[0]+256*b[1]+...+256^31 b[31].

// B is the Ed25519 base point (x,4/5) with x positive.

static void ge_double_scalarmult_vartime(ge_p2 *r, const uint8_t *a,

                                         const ge_p3 *A, const uint8_t *b) {

  signed char aslide[256];

  signed char bslide[256];

  ge_cached Ai[8];  // A,3A,5A,7A,9A,11A,13A,15A

  ge_p1p1 t;

  ge_p3 u;

  ge_p3 A2;

  int i;

  slide(aslide, a);

  slide(bslide, b);

  x25519_ge_p3_to_cached(&Ai[0], A);

  ge_p3_dbl(&t, A);

  x25519_ge_p1p1_to_p3(&A2, &t);

  x25519_ge_add(&t, &A2, &Ai[0]);

  x25519_ge_p1p1_to_p3(&u, &t);

  x25519_ge_p3_to_cached(&Ai[1], &u);

  x25519_ge_add(&t, &A2, &Ai[1]);

  x25519_ge_p1p1_to_p3(&u, &t);

  x25519_ge_p3_to_cached(&Ai[2], &u);

  x25519_ge_add(&t, &A2, &Ai[2]);

  x25519_ge_p1p1_to_p3(&u, &t);

  x25519_ge_p3_to_cached(&Ai[3], &u);

  x25519_ge_add(&t, &A2, &Ai[3]);

  x25519_ge_p1p1_to_p3(&u, &t);

  x25519_ge_p3_to_cached(&Ai[4], &u);

  x25519_ge_add(&t, &A2, &Ai[4]);

  x25519_ge_p1p1_to_p3(&u, &t);

  x25519_ge_p3_to_cached(&Ai[5], &u);

  x25519_ge_add(&t, &A2, &Ai[5]);

  x25519_ge_p1p1_to_p3(&u, &t);

  x25519_ge_p3_to_cached(&Ai[6], &u);

  x25519_ge_add(&t, &A2, &Ai[6]);

  x25519_ge_p1p1_to_p3(&u, &t);

  x25519_ge_p3_to_cached(&Ai[7], &u);

  ge_p2_0(r);

  for (i = 255; i >= 0; --i) {

    if (aslide[i] || bslide[i]) {

      break;

    }

  }

  for (; i >= 0; --i) {