7#ifndef BOTAN_PCURVES_UTIL_H_
8#define BOTAN_PCURVES_UTIL_H_
10#include <botan/internal/mp_core.h>
17template <WordType W,
size_t N,
size_t XN>
18inline consteval std::array<W, N> reduce_mod(
const std::array<W, XN>& x,
const std::array<W, N>& p) {
19 std::array<W, N + 1> r = {0};
20 std::array<W, N + 1> t = {0};
22 const size_t x_bits = XN * WordInfo<W>::bits;
24 for(
size_t i = 0; i != x_bits; ++i) {
25 const size_t b = x_bits - 1 - i;
27 const size_t b_word = b / WordInfo<W>::bits;
28 const size_t b_bit = b % WordInfo<W>::bits;
29 const bool x_b = (x[b_word] >> b_bit) & 1;
44 copy_mem(rs, std::span{r}.template first<N>());
48template <WordType W,
size_t N>
49inline consteval std::array<W, N> montygomery_r(
const std::array<W, N>& p) {
50 std::array<W, N + 1> x = {0};
52 return reduce_mod(x, p);
55template <WordType W,
size_t N>
56inline consteval std::array<W, N> mul_mod(
const std::array<W, N>& x,
57 const std::array<W, N>& y,
58 const std::array<W, N>& p) {
59 std::array<W, 2 * N> z;
61 return reduce_mod(z, p);
64template <WordType W,
size_t N>
65inline constexpr auto monty_redc_pdash1(
const std::array<W, 2 * N>& z,
const std::array<W, N>& p) -> std::array<W, N> {
66 static_assert(N >= 1);
74 ws[0] = accum.monty_step_pdash1();
76 for(
size_t i = 1; i != N; ++i) {
77 for(
size_t j = 0; j < i; ++j) {
78 accum.mul(ws[j], p[i - j]);
83 ws[i] = accum.monty_step_pdash1();
86 for(
size_t i = 0; i != N - 1; ++i) {
87 for(
size_t j = i + 1; j != N; ++j) {
88 accum.mul(ws[j], p[N + i - j]);
93 ws[i] = accum.extract();
96 accum.add(z[2 * N - 1]);
98 ws[N - 1] = accum.extract();
100 const W w1 = accum.extract();
108template <WordType W,
size_t N>
109inline constexpr auto monty_redc(
const std::array<W, 2 * N>& z,
const std::array<W, N>& p, W p_dash)
110 -> std::array<W, N> {
111 static_assert(N >= 1);
119 ws[0] = accum.monty_step(p[0], p_dash);
121 for(
size_t i = 1; i != N; ++i) {
122 for(
size_t j = 0; j < i; ++j) {
123 accum.mul(ws[j], p[i - j]);
128 ws[i] = accum.monty_step(p[0], p_dash);
131 for(
size_t i = 0; i != N - 1; ++i) {
132 for(
size_t j = i + 1; j != N; ++j) {
133 accum.mul(ws[j], p[N + i - j]);
138 ws[i] = accum.extract();
141 accum.add(z[2 * N - 1]);
143 ws[N - 1] = accum.extract();
145 const W w1 = accum.extract();
153template <u
int8_t X, WordType W,
size_t N>
154inline consteval std::array<W, N> p_minus(
const std::array<W, N>& p) {
156 static_assert(
X > 0);
160 std::reverse(r.begin(), r.end());
164template <WordType W,
size_t N>
165inline consteval std::array<W, N> p_plus_1_over_4(
const std::array<W, N>& p) {
170 std::reverse(r.begin(), r.end());
174template <WordType W,
size_t N>
175inline consteval std::array<W, N> p_minus_1_over_2(
const std::array<W, N>& p) {
180 std::reverse(r.begin(), r.end());
184template <WordType W,
size_t N>
185inline consteval size_t count_bits(
const std::array<W, N>& p) {
186 auto get_bit = [&](
size_t i) {
187 const size_t w = i / WordInfo<W>::bits;
188 const size_t b = i % WordInfo<W>::bits;
189 return static_cast<uint8_t
>((p[w] >> b) & 0x01);
192 size_t b = WordInfo<W>::bits * N;
194 while(get_bit(b - 1) == 0) {
201template <WordType W,
size_t N,
size_t L>
202inline constexpr auto bytes_to_words(std::span<const uint8_t, L> bytes) {
203 static_assert(L <= WordInfo<W>::bytes * N);
207 std::array<W, N> r = {};
208 for(
size_t i = 0; i != L; ++i) {
216template <
size_t WindowBits,
typename W,
size_t N>
217constexpr size_t read_window_bits(std::span<const W, N> words,
size_t offset) {
218 static_assert(WindowBits >= 1 && WindowBits <= 7);
220 const uint8_t WindowMask =
static_cast<uint8_t
>(1 << WindowBits) - 1;
222 const size_t W_bits =
sizeof(W) * 8;
223 const auto bit_shift = offset % W_bits;
224 const auto word_offset = words.size() - 1 - (offset / W_bits);
226 const bool single_byte_window = bit_shift <= (W_bits - WindowBits) || word_offset == 0;
228 const auto w0 = words[word_offset];
230 if(single_byte_window) {
231 return (w0 >> bit_shift) & WindowMask;
234 const auto w1 = words[word_offset - 1];
235 const auto combined = ((w0 >> bit_shift) | (w1 << (W_bits - bit_shift)));
236 return combined & WindowMask;
constexpr W shift_left(std::array< W, N > &x)
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
void carry(int64_t &h0, int64_t &h1)
constexpr void copy_mem(T *out, const T *in, size_t n)
constexpr W shift_right(std::array< W, N > &x)
constexpr auto bigint_add3_nc(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W