/*

* X448 Gf Modulo 2^448 - 2^224 - 1

* (C) 2024 Jack Lloyd

*     2024 Fabian Albert - Rohde & Schwarz Cybersecurity

*

* Botan is released under the Simplified BSD License (see license.txt)

*/

#include <botan/internal/curve448_gf.h>

#include <botan/internal/ct_utils.h>

#include <botan/internal/loadstor.h>

#include <botan/internal/mp_asmi.h>

#include <botan/internal/mp_core.h>

#include <algorithm>

namespace Botan {

namespace {

/**

 * @brief Compute (a + b). The carry is returned in the carry parameter.

 *  The carry is not included for the addition.

 */

inline uint64_t u64_add(uint64_t a, uint64_t b, bool* carry) {

   // Let the compiler optimize this into fancy instructions

   const uint64_t sum = a + b;

   *carry = sum < a;

   return sum;

}

/**

 * @brief Compute (a + b + carry), where carry is in {0, 1}. The carry of this computation

 * is store in the in/out @p carry parameter.

 */

inline uint64_t u64_add_with_carry(uint64_t a, uint64_t b, bool* carry) {

   // Let the compiler optimize this into fancy instructions

   uint64_t sum = a + b;

   const bool carry_a_plus_b = (sum < a);

   sum += static_cast<uint64_t>(*carry);

   *carry = static_cast<uint64_t>(carry_a_plus_b) | static_cast<uint64_t>(sum < static_cast<uint64_t>(*carry));

   return sum;

}

/**

 * @brief Compute (a - (b + borrow)). The borrow is returned in the carry parameter.

 *

 * I.e. borrow = 1 if a < b + borrow, else 0.

 */

inline uint64_t u64_sub_with_borrow(uint64_t a, uint64_t b, bool* borrow) {

   // Let the compiler optimize this into fancy instructions

   const uint64_t diff = a - b;

   const bool borrow_a_min_b = diff > a;

   const uint64_t z = diff - static_cast<uint64_t>(*borrow);

   *borrow = static_cast<uint64_t>(borrow_a_min_b) | static_cast<uint64_t>(z > diff);

   return z;

}

/**

 * @brief Reduce the result of a addition modulo 2^448 - 2^224 - 1.

 *

 * Algorithm 1 of paper "Reduction Modulo 2^448 - 2^224 - 1", from line 27.

 *

 * @param h_3 Output

 * @param h_1 Input

 */

void reduce_after_add(std::span<uint64_t, WORDS_448> h_3, std::span<const uint64_t, 8> h_1) {

   std::array<uint64_t, 8> h_2;

   bool carry;

   // Line 27+ (of the paper's algorithm 1)

   h_2[0] = u64_add(h_1[0], h_1[7], &carry);

   h_2[1] = u64_add(h_1[1], carry, &carry);

   h_2[2] = u64_add(h_1[2], carry, &carry);

   // Line 30

   h_2[3] = u64_add_with_carry(h_1[3], h_1[7] << 32, &carry);

   // Line 31+

   h_2[4] = u64_add(h_1[4], carry, &carry);

   h_2[5] = u64_add(h_1[5], carry, &carry);

   h_2[6] = u64_add(h_1[6], carry, &carry);

   h_2[7] = carry;

   h_3[0] = u64_add(h_2[0], h_2[7], &carry);

   h_3[1] = u64_add(h_2[1], carry, &carry);

   h_3[2] = u64_add(h_2[2], carry, &carry);

   // Line 37

   h_3[3] = h_2[3] + (h_2[7] << 32) + carry;

   // Line 38

   h_3[4] = h_2[4];

   h_3[5] = h_2[5];

   h_3[6] = h_2[6];

}

/**

 * @brief Reduce the result of a addition modulo 2^448 - 2^224 - 1.

 *

 * Algorithm 1 of paper "Reduction Modulo 2^448 - 2^224 - 1".

 */

void reduce_after_mul(std::span<uint64_t, WORDS_448> out, std::span<const uint64_t, 14> in) {

   std::array<uint64_t, 8> r;

   std::array<uint64_t, 8> s;

   std::array<uint64_t, 8> t_0;

   std::array<uint64_t, 8> h_1;

   bool carry;

   // Line 4 (of the paper's algorithm 1)

   r[0] = u64_add(in[0], in[7], &carry);

   // Line 5-7

   for(size_t i = 1; i < 7; ++i) {

      r[i] = u64_add_with_carry(in[i], in[i + 7], &carry);

   }

   r[7] = carry;

   s[0] = r[0];

   s[1] = r[1];

   s[2] = r[2];

   // Line 10

   s[3] = u64_add(r[3], in[10] & 0xFFFFFFFF00000000, &carry);

   // Line 11-13

   for(size_t i = 4; i < 7; ++i) {

      s[i] = u64_add_with_carry(r[i], in[i + 7], &carry);

   }

   s[7] = r[7] + carry;

   // Line 15-17

   for(size_t i = 0; i < 3; ++i) {

      t_0[i] = (in[i + 11] << 32) | (in[i + 10] >> 32);

   }

   // Line 18

   t_0[3] = (in[7] << 32) | (in[13] >> 32);

   // Line 19-21

   for(size_t i = 4; i < 7; ++i) {

      t_0[i] = (in[i + 4] << 32) | (in[i + 3] >> 32);

   }

   h_1[0] = u64_add(s[0], t_0[0], &carry);

   // Line 23-25

   for(size_t i = 1; i < 7; ++i) {

      h_1[i] = u64_add_with_carry(s[i], t_0[i], &carry);

   }

   h_1[7] = s[7] + carry;

   reduce_after_add(out, h_1);

}

void gf_mul(std::span<uint64_t, WORDS_448> out,

            std::span<const uint64_t, WORDS_448> a,

            std::span<const uint64_t, WORDS_448> b) {

   std::array<uint64_t, 14> ws;

   comba_mul<7>(ws.data(), a.data(), b.data());

   reduce_after_mul(out, ws);

}

void gf_square(std::span<uint64_t, WORDS_448> out, std::span<const uint64_t, WORDS_448> a) {

   std::array<uint64_t, 14> ws;

   comba_sqr<7>(ws.data(), a.data());

   reduce_after_mul(out, ws);

}

void gf_add(std::span<uint64_t, WORDS_448> out,

            std::span<const uint64_t, WORDS_448> a,

            std::span<const uint64_t, WORDS_448> b) {

   std::array<uint64_t, WORDS_448 + 1> ws;

   copy_mem(std::span(ws).first<WORDS_448>(), a);

   ws[WORDS_448] = 0;

   bool carry = false;

   for(size_t i = 0; i < WORDS_448; ++i) {

      ws[i] = u64_add_with_carry(a[i], b[i], &carry);

   }

   ws[WORDS_448] = carry;

   reduce_after_add(out, ws);

}

/**

 * @brief Subtract two elements in GF(P). out = a - b

 *

 * Algorithm 2 of paper: "Reduction Modulo 2^448 - 2^224 - 1"

 */

void gf_sub(std::span<uint64_t, WORDS_448> out,

            std::span<const uint64_t, WORDS_448> a,

            std::span<const uint64_t, WORDS_448> b) {

   std::array<uint64_t, WORDS_448> h_0;

   std::array<uint64_t, WORDS_448> h_1;

   bool borrow = false;

   for(size_t i = 0; i < WORDS_448; ++i) {

      h_0[i] = u64_sub_with_borrow(a[i], b[i], &borrow);

   }

   uint64_t delta = borrow;

   uint64_t delta_p = delta << 32;

   borrow = false;

   h_1[0] = u64_sub_with_borrow(h_0[0], delta, &borrow);

   h_1[1] = u64_sub_with_borrow(h_0[1], 0, &borrow);

   h_1[2] = u64_sub_with_borrow(h_0[2], 0, &borrow);

   h_1[3] = u64_sub_with_borrow(h_0[3], delta_p, &borrow);

   h_1[4] = u64_sub_with_borrow(h_0[4], 0, &borrow);

   h_1[5] = u64_sub_with_borrow(h_0[5], 0, &borrow);

   h_1[6] = u64_sub_with_borrow(h_0[6], 0, &borrow);

   delta = borrow;

   delta_p = delta << 32;

   borrow = false;

   out[0] = u64_sub_with_borrow(h_1[0], delta, &borrow);

   out[1] = u64_sub_with_borrow(h_1[1], 0, &borrow);

   out[2] = u64_sub_with_borrow(h_1[2], 0, &borrow);

   out[3] = u64_sub_with_borrow(h_1[3], delta_p, &borrow);

   out[4] = h_1[4];

   out[5] = h_1[5];

   out[6] = h_1[6];

}

/**

 * @brief Inversion in GF(P) using Fermat's little theorem:

 * x^-1 = x^(P-2) mod P

 */

void gf_inv(std::span<uint64_t, WORDS_448> out, std::span<const uint64_t, WORDS_448> a) {

   clear_mem(out);

   out[0] = 1;

   // Square and multiply

   for(int16_t t = 448; t >= 0; --t) {

      gf_square(out, out);

      // (P-2) has zero bits at indices 1, 224, 448. All others are one.

      if(t != 448 && t != 224 && t != 1) {

         gf_mul(out, out, a);

      }

   }

}

/**

 * @brief Convert a number to its canonical representation.

 *

 * I.e. if the number is greater than P, subtract P. The number cannot be >= 2P

 * since 2*P > 2^(7*64).

 */

std::array<uint64_t, WORDS_448> to_canonical(std::span<const uint64_t, WORDS_448> in) {

   const std::array<uint64_t, WORDS_448> p = {0xffffffffffffffff,

                                              0xffffffffffffffff,

                                              0xffffffffffffffff,

                                              0xfffffffeffffffff,

                                              0xffffffffffffffff,

                                              0xffffffffffffffff,

                                              0xffffffffffffffff};

   std::array<uint64_t, WORDS_448> in_minus_p;

   bool borrow = false;

   for(size_t i = 0; i < WORDS_448; ++i) {

      in_minus_p[i] = u64_sub_with_borrow(in[i], p[i], &borrow);

   }

   std::array<uint64_t, WORDS_448> out;

   CT::Mask<uint64_t>::expand(borrow).select_n(out.data(), in.data(), in_minus_p.data(), WORDS_448);

   return out;

}

}  // namespace

Gf448Elem::Gf448Elem(std::span<const uint8_t, BYTES_448> x) {

   load_le(m_x, x);

}

Gf448Elem::Gf448Elem(uint64_t least_sig_word) {

   clear_mem(m_x);

   m_x[0] = least_sig_word;

}

void Gf448Elem::to_bytes(std::span<uint8_t, BYTES_448> out) const {

   store_le(out, to_canonical(m_x));

}

std::array<uint8_t, BYTES_448> Gf448Elem::to_bytes() const {

   std::array<uint8_t, BYTES_448> bytes;

   to_bytes(bytes);

   return bytes;

}

void Gf448Elem::ct_cond_swap(bool b, Gf448Elem& other) {

   for(size_t i = 0; i < WORDS_448; ++i) {

      CT::conditional_swap(b, m_x[i], other.m_x[i]);

   }

}

void Gf448Elem::ct_cond_assign(bool b, const Gf448Elem& other) {

   CT::conditional_assign_mem(static_cast<uint64_t>(b), m_x.data(), other.m_x.data(), WORDS_448);

}

Gf448Elem Gf448Elem::operator+(const Gf448Elem& other) const {

   Gf448Elem res(0);

   gf_add(res.m_x, m_x, other.m_x);

   return res;

}

Gf448Elem Gf448Elem::operator-(const Gf448Elem& other) const {

   Gf448Elem res(0);

   gf_sub(res.m_x, m_x, other.m_x);

   return res;

}

Gf448Elem Gf448Elem::operator-() const {

   Gf448Elem res(0);

   gf_sub(res.m_x, res.m_x, m_x);

   return res;

}

Gf448Elem Gf448Elem::operator*(const Gf448Elem& other) const {

   Gf448Elem res(0);

   gf_mul(res.m_x, m_x, other.m_x);

   return res;

}

Gf448Elem Gf448Elem::operator/(const Gf448Elem& other) const {

   Gf448Elem res(0);

   gf_inv(res.m_x, other.m_x);

   gf_mul(res.m_x, m_x, res.m_x);

   return res;

}

bool Gf448Elem::operator==(const Gf448Elem& other) const {

   const auto canonical_form_this = to_canonical(m_x);

   const auto canonical_form_other = to_canonical(other.m_x);

   return CT::is_equal(canonical_form_this.data(), canonical_form_other.data(), WORDS_448).as_bool();

}

bool Gf448Elem::is_zero() const {

   const auto canonical_form = to_canonical(m_x);

   return CT::all_zeros(canonical_form.data(), WORDS_448).as_bool();

}

bool Gf448Elem::is_odd() const {

   const auto canonical_form = to_canonical(m_x);

   return (canonical_form[0] & 1) == 1;

}

bool Gf448Elem::bytes_are_canonical_representation(std::span<const uint8_t, BYTES_448> x) {

   const auto x_words = load_le<std::array<uint64_t, WORDS_448>>(x);

   const auto x_words_canonical = to_canonical(x_words);

   return CT::is_equal(x_words.data(), x_words_canonical.data(), WORDS_448).as_bool();

}

Gf448Elem square(const Gf448Elem& elem) {

   Gf448Elem res(0);

   gf_square(res.words(), elem.words());

   return res;

}

Gf448Elem root(const Gf448Elem& elem) {

   Gf448Elem res(1);

   // (P-3)/4 is an 445 bit integer with one zero bits at 222. All others are one.

   for(int16_t t = 445; t >= 0; --t) {

      gf_square(res.words(), res.words());

      if(t != 222) {

         gf_mul(res.words(), res.words(), elem.words());

      }

   }

   return res;

}

}  // namespace Botan