/* Copyright (c) 2018, 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. */

#include <openssl/ec.h>

#include <assert.h>

#include "internal.h"

#include "../bn/internal.h"

#include "../../internal.h"

void ec_GFp_mont_mul(const EC_GROUP *group, EC_JACOBIAN *r,

                     const EC_JACOBIAN *p, const EC_SCALAR *scalar) {

  // This is a generic implementation for uncommon curves that not do not

  // warrant a tuned one. It uses unsigned digits so that the doubling case in

  // |ec_GFp_mont_add| is always unreachable, erring on safety and simplicity.

  // Compute a table of the first 32 multiples of |p| (including infinity).

  EC_JACOBIAN precomp[32];

  ec_GFp_simple_point_set_to_infinity(group, &precomp[0]);

  ec_GFp_simple_point_copy(&precomp[1], p);

  for (size_t j = 2; j < OPENSSL_ARRAY_SIZE(precomp); j++) {

    if (j & 1) {

      ec_GFp_mont_add(group, &precomp[j], &precomp[1], &precomp[j - 1]);

    } else {

      ec_GFp_mont_dbl(group, &precomp[j], &precomp[j / 2]);

    }

  }

  // Divide bits in |scalar| into windows.

  unsigned bits =  EC_GROUP_order_bits(group);

  int r_is_at_infinity = 1;

  for (unsigned i = bits - 1; i < bits; i--) {

    if (!r_is_at_infinity) {

      ec_GFp_mont_dbl(group, r, r);

    }

    if (i % 5 == 0) {

      // Compute the next window value.

      const size_t width = group->order.N.width;

      uint8_t window = bn_is_bit_set_words(scalar->words, width, i + 4) << 4;

      window |= bn_is_bit_set_words(scalar->words, width, i + 3) << 3;

      window |= bn_is_bit_set_words(scalar->words, width, i + 2) << 2;

      window |= bn_is_bit_set_words(scalar->words, width, i + 1) << 1;

      window |= bn_is_bit_set_words(scalar->words, width, i);

      // Select the entry in constant-time.

      EC_JACOBIAN tmp;

      OPENSSL_memset(&tmp, 0, sizeof(EC_JACOBIAN));

      for (size_t j = 0; j < OPENSSL_ARRAY_SIZE(precomp); j++) {

        BN_ULONG mask = constant_time_eq_w(j, window);

        ec_point_select(group, &tmp, mask, &precomp[j], &tmp);

      }

      if (r_is_at_infinity) {

        ec_GFp_simple_point_copy(r, &tmp);

        r_is_at_infinity = 0;

      } else {

        ec_GFp_mont_add(group, r, r, &tmp);

      }

    }

  }

  if (r_is_at_infinity) {

    ec_GFp_simple_point_set_to_infinity(group, r);

  }

}

void ec_GFp_mont_mul_base(const EC_GROUP *group, EC_JACOBIAN *r,

                          const EC_SCALAR *scalar) {

  ec_GFp_mont_mul(group, r, &group->generator.raw, scalar);

}

static void ec_GFp_mont_batch_precomp(const EC_GROUP *group, EC_JACOBIAN *out,

                                      size_t num, const EC_JACOBIAN *p) {

  assert(num > 1);

  ec_GFp_simple_point_set_to_infinity(group, &out[0]);

  ec_GFp_simple_point_copy(&out[1], p);

  for (size_t j = 2; j < num; j++) {

    if (j & 1) {

      ec_GFp_mont_add(group, &out[j], &out[1], &out[j - 1]);

    } else {

      ec_GFp_mont_dbl(group, &out[j], &out[j / 2]);

    }

  }

}

static void ec_GFp_mont_batch_get_window(const EC_GROUP *group,

                                         EC_JACOBIAN *out,

                                         const EC_JACOBIAN precomp[17],

                                         const EC_SCALAR *scalar, unsigned i) {

  const size_t width = group->order.N.width;

  uint8_t window = bn_is_bit_set_words(scalar->words, width, i + 4) << 5;

  window |= bn_is_bit_set_words(scalar->words, width, i + 3) << 4;

  window |= bn_is_bit_set_words(scalar->words, width, i + 2) << 3;

  window |= bn_is_bit_set_words(scalar->words, width, i + 1) << 2;

  window |= bn_is_bit_set_words(scalar->words, width, i) << 1;

  if (i > 0) {

    window |= bn_is_bit_set_words(scalar->words, width, i - 1);

  }

  crypto_word_t sign, digit;

  ec_GFp_nistp_recode_scalar_bits(&sign, &digit, window);

  // Select the entry in constant-time.

  OPENSSL_memset(out, 0, sizeof(EC_JACOBIAN));

  for (size_t j = 0; j < 17; j++) {

    BN_ULONG mask = constant_time_eq_w(j, digit);

    ec_point_select(group, out, mask, &precomp[j], out);

  }

  // Negate if necessary.

  EC_FELEM neg_Y;

  ec_felem_neg(group, &neg_Y, &out->Y);

  crypto_word_t sign_mask = sign;

  sign_mask = 0u - sign_mask;

  ec_felem_select(group, &out->Y, sign_mask, &neg_Y, &out->Y);

}

void ec_GFp_mont_mul_batch(const EC_GROUP *group, EC_JACOBIAN *r,

                           const EC_JACOBIAN *p0, const EC_SCALAR *scalar0,

                           const EC_JACOBIAN *p1, const EC_SCALAR *scalar1,

                           const EC_JACOBIAN *p2, const EC_SCALAR *scalar2) {

  EC_JACOBIAN precomp[3][17];

  ec_GFp_mont_batch_precomp(group, precomp[0], 17, p0);

  ec_GFp_mont_batch_precomp(group, precomp[1], 17, p1);

  if (p2 != NULL) {

    ec_GFp_mont_batch_precomp(group, precomp[2], 17, p2);

  }

  // Divide bits in |scalar| into windows.

  unsigned bits = EC_GROUP_order_bits(group);

  int r_is_at_infinity = 1;

  for (unsigned i = bits; i <= bits; i--) {

    if (!r_is_at_infinity) {

      ec_GFp_mont_dbl(group, r, r);

    }

    if (i % 5 == 0) {

      EC_JACOBIAN tmp;

      ec_GFp_mont_batch_get_window(group, &tmp, precomp[0], scalar0, i);

      if (r_is_at_infinity) {

        ec_GFp_simple_point_copy(r, &tmp);

        r_is_at_infinity = 0;

      } else {

        ec_GFp_mont_add(group, r, r, &tmp);

      }

      ec_GFp_mont_batch_get_window(group, &tmp, precomp[1], scalar1, i);

      ec_GFp_mont_add(group, r, r, &tmp);

      if (p2 != NULL) {

        ec_GFp_mont_batch_get_window(group, &tmp, precomp[2], scalar2, i);

        ec_GFp_mont_add(group, r, r, &tmp);

      }

    }

  }

  if (r_is_at_infinity) {

    ec_GFp_simple_point_set_to_infinity(group, r);

  }

}

static unsigned ec_GFp_mont_comb_stride(const EC_GROUP *group) {

  return (EC_GROUP_get_degree(group) + EC_MONT_PRECOMP_COMB_SIZE - 1) /

         EC_MONT_PRECOMP_COMB_SIZE;

}

int ec_GFp_mont_init_precomp(const EC_GROUP *group, EC_PRECOMP *out,

                             const EC_JACOBIAN *p) {

  // comb[i - 1] stores the ith element of the comb. That is, if i is

  // b4 * 2^4 + b3 * 2^3 + ... + b0 * 2^0, it stores k * |p|, where k is

  // b4 * 2^(4*stride) + b3 * 2^(3*stride) + ... + b0 * 2^(0*stride). stride

  // here is |ec_GFp_mont_comb_stride|. We store at index i - 1 because the 0th

  // comb entry is always infinity.

  EC_JACOBIAN comb[(1 << EC_MONT_PRECOMP_COMB_SIZE) - 1];

  unsigned stride = ec_GFp_mont_comb_stride(group);

  // We compute the comb sequentially by the highest set bit. Initially, all

  // entries up to 2^0 are filled.

  comb[(1 << 0) - 1] = *p;

  for (unsigned i = 1; i < EC_MONT_PRECOMP_COMB_SIZE; i++) {

    // Compute entry 2^i by doubling the entry for 2^(i-1) |stride| times.

    unsigned bit = 1 << i;

    ec_GFp_mont_dbl(group, &comb[bit - 1], &comb[bit / 2 - 1]);

    for (unsigned j = 1; j < stride; j++) {

      ec_GFp_mont_dbl(group, &comb[bit - 1], &comb[bit - 1]);

    }

    // Compute entries from 2^i + 1 to 2^i + (2^i - 1) by adding entry 2^i to

    // a previous entry.

    for (unsigned j = 1; j < bit; j++) {

      ec_GFp_mont_add(group, &comb[bit + j - 1], &comb[bit - 1], &comb[j - 1]);

    }

  }

  // Store the comb in affine coordinates to shrink the table. (This reduces

  // cache pressure and makes the constant-time selects faster.)

  static_assert(OPENSSL_ARRAY_SIZE(comb) == OPENSSL_ARRAY_SIZE(out->comb),

                "comb sizes did not match");

  return ec_jacobian_to_affine_batch(group, out->comb, comb,

                                     OPENSSL_ARRAY_SIZE(comb));

}

static void ec_GFp_mont_get_comb_window(const EC_GROUP *group,

                                        EC_JACOBIAN *out,

                                        const EC_PRECOMP *precomp,

                                        const EC_SCALAR *scalar, unsigned i) {

  const size_t width = group->order.N.width;

  unsigned stride = ec_GFp_mont_comb_stride(group);

  // Select the bits corresponding to the comb shifted up by |i|.

  unsigned window = 0;

  for (unsigned j = 0; j < EC_MONT_PRECOMP_COMB_SIZE; j++) {

    window |= bn_is_bit_set_words(scalar->words, width, j * stride + i)

              << j;

  }

  // Select precomp->comb[window - 1]. If |window| is zero, |match| will always

  // be zero, which will leave |out| at infinity.

  OPENSSL_memset(out, 0, sizeof(EC_JACOBIAN));

  for (unsigned j = 0; j < OPENSSL_ARRAY_SIZE(precomp->comb); j++) {

    BN_ULONG match = constant_time_eq_w(window, j + 1);

    ec_felem_select(group, &out->X, match, &precomp->comb[j].X, &out->X);

    ec_felem_select(group, &out->Y, match, &precomp->comb[j].Y, &out->Y);

  }

  BN_ULONG is_infinity = constant_time_is_zero_w(window);

  ec_felem_select(group, &out->Z, is_infinity, &out->Z, ec_felem_one(group));

}

void ec_GFp_mont_mul_precomp(const EC_GROUP *group, EC_JACOBIAN *r,

                             const EC_PRECOMP *p0, const EC_SCALAR *scalar0,

                             const EC_PRECOMP *p1, const EC_SCALAR *scalar1,

                             const EC_PRECOMP *p2, const EC_SCALAR *scalar2) {

  unsigned stride = ec_GFp_mont_comb_stride(group);

  int r_is_at_infinity = 1;

  for (unsigned i = stride - 1; i < stride; i--) {

    if (!r_is_at_infinity) {

      ec_GFp_mont_dbl(group, r, r);

    }

    EC_JACOBIAN tmp;

    ec_GFp_mont_get_comb_window(group, &tmp, p0, scalar0, i);

    if (r_is_at_infinity) {

      ec_GFp_simple_point_copy(r, &tmp);

      r_is_at_infinity = 0;

    } else {

      ec_GFp_mont_add(group, r, r, &tmp);

    }

    if (p1 != NULL) {

      ec_GFp_mont_get_comb_window(group, &tmp, p1, scalar1, i);

      ec_GFp_mont_add(group, r, r, &tmp);

    }

    if (p2 != NULL) {

      ec_GFp_mont_get_comb_window(group, &tmp, p2, scalar2, i);

      ec_GFp_mont_add(group, r, r, &tmp);

    }

  }

  if (r_is_at_infinity) {

    ec_GFp_simple_point_set_to_infinity(group, r);

  }

}