10#ifndef BOTAN_MP_CORE_OPS_H_
11#define BOTAN_MP_CORE_OPS_H_
13#include <botan/assert.h>
14#include <botan/exceptn.h>
15#include <botan/mem_ops.h>
16#include <botan/types.h>
17#include <botan/internal/ct_utils.h>
18#include <botan/internal/mp_asmi.h>
34 for(
size_t i = 0; i != size; ++i) {
37 x[i] = mask.select(b, a);
38 y[i] = mask.select(a, b);
43inline constexpr W
bigint_cnd_add(W cnd, W x[],
size_t x_size,
const W y[],
size_t y_size) {
50 for(
size_t i = 0; i != y_size; ++i) {
54 for(
size_t i = y_size; i != x_size; ++i) {
58 return (mask &
carry);
75inline constexpr auto bigint_cnd_sub(W cnd, W x[],
size_t x_size,
const W y[],
size_t y_size) -> W {
82 for(
size_t i = 0; i != y_size; ++i) {
86 for(
size_t i = y_size; i != x_size; ++i) {
90 return (mask &
carry);
98inline constexpr auto bigint_cnd_sub(W cnd, W x[],
const W y[],
size_t size) -> W {
111 const size_t blocks = size - (size % 8);
119 for(
size_t i = 0; i != blocks; i += 8) {
121 borrow =
word8_sub3(t1, x + i, y + i, borrow);
125 for(
size_t i = blocks; i != size; ++i) {
127 const W s =
word_sub(x[i], y[i], &borrow);
144 const size_t blocks = size - (size % 8);
152 for(
size_t i = 0; i != blocks; i += 8) {
154 borrow =
word8_sub3(t1, x + i, z + i, borrow);
155 mask.select_n(x + i, t0, t1, 8);
158 for(
size_t i = blocks; i != size; ++i) {
160 t1[0] =
word_sub(x[i], z[i], &borrow);
161 x[i] = mask.select(t0[0], t1[0]);
164 return mask.select(
carry, borrow);
176 W
carry = mask.if_set_return(1);
177 for(
size_t i = 0; i != size; ++i) {
179 x[i] = mask.select(z, x[i]);
187inline constexpr auto bigint_add2_nc(W x[],
size_t x_size,
const W y[],
size_t y_size) -> W {
192 const size_t blocks = y_size - (y_size % 8);
194 for(
size_t i = 0; i != blocks; i += 8) {
198 for(
size_t i = blocks; i != y_size; ++i) {
202 for(
size_t i = y_size; i != x_size; ++i) {
213inline constexpr auto bigint_add3_nc(W z[],
const W x[],
size_t x_size,
const W y[],
size_t y_size) -> W {
214 if(x_size < y_size) {
220 const size_t blocks = y_size - (y_size % 8);
222 for(
size_t i = 0; i != blocks; i += 8) {
226 for(
size_t i = blocks; i != y_size; ++i) {
230 for(
size_t i = y_size; i != x_size; ++i) {
245inline constexpr void bigint_add2(W x[],
size_t x_size,
const W y[],
size_t y_size) {
253inline constexpr void bigint_add3(W z[],
const W x[],
size_t x_size,
const W y[],
size_t y_size) {
254 z[x_size > y_size ? x_size : y_size] +=
bigint_add3_nc(z, x, x_size, y, y_size);
261inline constexpr auto bigint_sub2(W x[],
size_t x_size,
const W y[],
size_t y_size) -> W {
266 const size_t blocks = y_size - (y_size % 8);
268 for(
size_t i = 0; i != blocks; i += 8) {
272 for(
size_t i = blocks; i != y_size; ++i) {
273 x[i] =
word_sub(x[i], y[i], &borrow);
276 for(
size_t i = y_size; i != x_size; ++i) {
277 x[i] =
word_sub(x[i],
static_cast<W
>(0), &borrow);
290 const size_t blocks = y_size - (y_size % 8);
292 for(
size_t i = 0; i != blocks; i += 8) {
296 for(
size_t i = blocks; i != y_size; ++i) {
297 x[i] =
word_sub(y[i], x[i], &borrow);
311inline constexpr auto bigint_sub3(W z[],
const W x[],
size_t x_size,
const W y[],
size_t y_size) -> W {
316 const size_t blocks = y_size - (y_size % 8);
318 for(
size_t i = 0; i != blocks; i += 8) {
319 borrow =
word8_sub3(z + i, x + i, y + i, borrow);
322 for(
size_t i = blocks; i != y_size; ++i) {
323 z[i] =
word_sub(x[i], y[i], &borrow);
326 for(
size_t i = y_size; i != x_size; ++i) {
327 z[i] =
word_sub(x[i],
static_cast<W
>(0), &borrow);
347 const size_t blocks = N - (N % 8);
349 for(
size_t i = 0; i != blocks; i += 8) {
350 borrow =
word8_sub3(z + i, x + i, p + i, borrow);
353 for(
size_t i = blocks; i != N; ++i) {
354 z[i] =
word_sub(x[i], p[i], &borrow);
357 borrow = (x0 - borrow) > x0;
372template <
size_t N, WordType W>
376 for(
size_t i = 0; i != N; ++i) {
377 z[i] =
word_sub(x[i], y[i], &borrow);
380 borrow = (x0 - borrow) > x0;
407 const size_t blocks = N - (N % 8);
409 for(
size_t i = 0; i != blocks; i += 8) {
410 borrow0 =
word8_sub3(ws0 + i, x + i, y + i, borrow0);
411 borrow1 =
word8_sub3(ws1 + i, y + i, x + i, borrow1);
414 for(
size_t i = blocks; i != N; ++i) {
415 ws0[i] =
word_sub(x[i], y[i], &borrow0);
416 ws1[i] =
word_sub(y[i], x[i], &borrow1);
426inline constexpr void bigint_shl1(W x[],
size_t x_size,
size_t x_words,
size_t shift) {
430 copy_mem(x + word_shift, x, x_words);
437 for(
size_t i = word_shift; i != x_size; ++i) {
439 x[i] = (w << bit_shift) |
carry;
445inline constexpr void bigint_shr1(W x[],
size_t x_size,
size_t shift) {
449 const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0;
454 clear_mem(x + top, std::min(word_shift, x_size));
461 for(
size_t i = 0; i != top; ++i) {
462 const W w = x[top - i - 1];
463 x[top - i - 1] = (w >> bit_shift) |
carry;
469inline constexpr void bigint_shl2(W y[],
const W x[],
size_t x_size,
size_t shift) {
473 copy_mem(y + word_shift, x, x_size);
479 for(
size_t i = word_shift; i != x_size + word_shift + 1; ++i) {
481 y[i] = (w << bit_shift) |
carry;
487inline constexpr void bigint_shr2(W y[],
const W x[],
size_t x_size,
size_t shift) {
490 const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift);
493 copy_mem(y, x + word_shift, new_size);
500 for(
size_t i = new_size; i > 0; --i) {
502 y[i - 1] = (w >> bit_shift) |
carry;
511[[nodiscard]]
inline constexpr auto bigint_linmul2(W x[],
size_t x_size, W y) -> W {
512 const size_t blocks = x_size - (x_size % 8);
516 for(
size_t i = 0; i != blocks; i += 8) {
520 for(
size_t i = blocks; i != x_size; ++i) {
529 const size_t blocks = x_size - (x_size % 8);
533 for(
size_t i = 0; i != blocks; i += 8) {
537 for(
size_t i = blocks; i != x_size; ++i) {
551inline constexpr int32_t
bigint_cmp(
const W x[],
size_t x_size,
const W y[],
size_t y_size) {
552 static_assert(
sizeof(W) >=
sizeof(uint32_t),
"Size assumption");
554 const W LT =
static_cast<W
>(-1);
558 const size_t common_elems = std::min(x_size, y_size);
562 for(
size_t i = 0; i != common_elems; i++) {
566 result = is_eq.select(result, is_lt.select(LT, GT));
569 if(x_size < y_size) {
571 for(
size_t i = x_size; i != y_size; i++) {
577 }
else if(y_size < x_size) {
579 for(
size_t i = y_size; i != x_size; i++) {
589 return static_cast<int32_t
>(result);
598inline constexpr auto bigint_ct_is_lt(
const W x[],
size_t x_size,
const W y[],
size_t y_size,
bool lt_or_equal =
false)
600 const size_t common_elems = std::min(x_size, y_size);
604 for(
size_t i = 0; i != common_elems; i++) {
607 is_lt = eq.select_mask(is_lt, lt);
610 if(x_size < y_size) {
612 for(
size_t i = x_size; i != y_size; i++) {
617 }
else if(y_size < x_size) {
619 for(
size_t i = y_size; i != x_size; i++) {
632 const size_t common_elems = std::min(x_size, y_size);
636 for(
size_t i = 0; i != common_elems; i++) {
637 diff |= (x[i] ^ y[i]);
641 if(x_size < y_size) {
642 for(
size_t i = x_size; i != y_size; i++) {
645 }
else if(y_size < x_size) {
646 for(
size_t i = y_size; i != x_size; i++) {
668inline constexpr int32_t
bigint_sub_abs(W z[],
const W x[],
size_t x_size,
const W y[],
size_t y_size) {
669 const int32_t relative_size =
bigint_cmp(x, x_size, y, y_size);
672 const bool need_swap = relative_size < 0;
681 y_size = std::min(x_size, y_size);
685 return relative_size;
698inline constexpr void bigint_mod_sub(W t[],
const W s[],
const W mod[],
size_t mod_sw, W ws[]) {
700 const W borrow =
bigint_sub3(ws, t, mod_sw, s, mod_sw);
719 n <<= WordInfo<W>::bits;
721 return static_cast<W
>(n / d);
733 if(high_top_bit || high >= d) {
794template <
size_t S, WordType W,
size_t N>
796 static_assert(S < WordInfo<W>::bits,
"Shift too large");
799 for(
size_t i = 0; i != N; ++i) {
801 x[i] = (w << S) |
carry;
808template <
size_t S, WordType W,
size_t N>
810 static_assert(S < WordInfo<W>::bits,
"Shift too large");
813 for(
size_t i = 0; i != N; ++i) {
814 const W w = x[N - 1 - i];
815 x[N - 1 - i] = (w >> S) |
carry;
823template <WordType W,
size_t N>
826 const constexpr size_t C = N - 1;
832 const constexpr size_t S = (C + NPW - 1) / NPW;
834 auto hex2int = [](
char c) -> int8_t {
835 if(c >=
'0' && c <=
'9') {
836 return static_cast<int8_t
>(c -
'0');
837 }
else if(c >=
'a' && c <=
'f') {
838 return static_cast<int8_t
>(c -
'a' + 10);
839 }
else if(c >=
'A' && c <=
'F') {
840 return static_cast<int8_t
>(c -
'A' + 10);
846 std::array<W, S> r = {0};
848 for(
size_t i = 0; i != C; ++i) {
849 const int8_t c = hex2int(s[i]);
881template <
size_t N, WordType W>
882constexpr inline void comba_mul(W z[2 * N],
const W x[N],
const W y[N]) {
883 if(!std::is_constant_evaluated()) {
884 if constexpr(std::same_as<W, word> && N == 4) {
887 if constexpr(std::same_as<W, word> && N == 6) {
890 if constexpr(std::same_as<W, word> && N == 7) {
893 if constexpr(std::same_as<W, word> && N == 8) {
896 if constexpr(std::same_as<W, word> && N == 9) {
899 if constexpr(std::same_as<W, word> && N == 16) {
906 for(
size_t i = 0; i != 2 * N; ++i) {
907 const size_t start = i + 1 < N ? 0 : i + 1 - N;
908 const size_t end = std::min(N, i + 1);
910 for(
size_t j = start; j != end; ++j) {
911 accum.
mul(x[j], y[i - j]);
917template <
size_t N, WordType W>
918constexpr inline void comba_sqr(W z[2 * N],
const W x[N]) {
919 if(!std::is_constant_evaluated()) {
920 if constexpr(std::same_as<W, word> && N == 4) {
923 if constexpr(std::same_as<W, word> && N == 6) {
926 if constexpr(std::same_as<W, word> && N == 7) {
929 if constexpr(std::same_as<W, word> && N == 8) {
932 if constexpr(std::same_as<W, word> && N == 9) {
935 if constexpr(std::same_as<W, word> && N == 16) {
942 for(
size_t i = 0; i != 2 * N; ++i) {
943 const size_t start = i + 1 < N ? 0 : i + 1 - N;
944 const size_t end = std::min(N, i + 1);
946 for(
size_t j = start; j != end; ++j) {
947 accum.
mul(x[j], x[i - j]);
970 word r[],
const word z[],
size_t z_size,
const word p[],
size_t p_size,
word p_dash,
word ws[]);
988 word r[],
const word z[],
const word p[],
size_t p_size,
word p_dash,
word ws[],
size_t ws_size) {
989 const size_t z_size = 2 * p_size;
991 BOTAN_ARG_CHECK(ws_size >= p_size,
"Montgomery reduction workspace too small");
995 }
else if(p_size == 6) {
997 }
else if(p_size == 8) {
999 }
else if(p_size == 12) {
1001 }
else if(p_size == 16) {
1003 }
else if(p_size == 24) {
1005 }
else if(p_size == 32) {
1043void bigint_sqr(
word z[],
size_t z_size,
const word x[],
size_t x_size,
size_t x_sw,
word workspace[],
size_t ws_size);
1055template <WordType W,
size_t N, W C>
1057 static_assert(N >= 2);
1059 std::array<W, N> hi = {};
1064 for(
size_t i = 0; i != N; ++i) {
1069 word carry_c[2] = {0};
1076 std::array<W, N> r = {};
1091#if defined(BOTAN_MP_USE_X86_64_ASM) && defined(__GNUC__) && !defined(__clang__)
1092 if constexpr(N == 4 && std::same_as<W, uint64_t>) {
1093 if(!std::is_constant_evaluated()) {
1095 movq 0(%[x]), %[borrow]
1096 subq %[p0], %[borrow]
1097 movq %[borrow], 0(%[r])
1098 movq 16(%[x]), %[borrow]
1100 movq %[borrow], 8(%[r])
1101 movq 16(%[x]), %[borrow]
1103 movq %[borrow], 16(%[r])
1104 movq 24(%[x]), %[borrow]
1106 movq %[borrow], 24(%[r])
1107 sbbq %[borrow],%[borrow]
1110 : [borrow] "=r"(borrow)
1111 : [x]
"r"(hi.data()), [p0]
"r"(P0), [r]
"r"(r.data()),
"0"(borrow)
1121 r[0] =
word_sub(hi[0], P0, &borrow);
1122 for(
size_t i = 1; i != N; ++i) {
1136template <
size_t N, WordType W>
1137constexpr inline void bigint_correct_redc(std::array<W, N>& r,
const std::array<W, N>& P,
const std::array<W, N>& C) {
1144template <
size_t WindowBits,
typename W,
size_t N>
1146 static_assert(WindowBits >= 1 && WindowBits <= 7);
1148 constexpr uint8_t WindowMask =
static_cast<uint8_t
>(1 << WindowBits) - 1;
1150 constexpr size_t W_bits =
sizeof(W) * 8;
1151 const auto bit_shift = offset % W_bits;
1152 const auto word_offset = words.size() - 1 - (offset / W_bits);
1154 const bool single_byte_window = bit_shift <= (W_bits - WindowBits) || word_offset == 0;
1156 const auto w0 = words[word_offset];
1158 if(single_byte_window) {
1159 return (w0 >> bit_shift) & WindowMask;
1162 const auto w1 = words[word_offset - 1];
1163 const auto combined = ((w0 >> bit_shift) | (w1 << (W_bits - bit_shift)));
1164 return combined & WindowMask;
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ARG_CHECK(expr, msg)
#define BOTAN_ASSERT(expr, assertion_made)
constexpr void select_n(T output[], const T x[], const T y[], size_t len) const
static constexpr Mask< T > expand(T v)
constexpr T select(T x, T y) const
static constexpr Mask< T > is_equal(T x, T y)
static constexpr Mask< T > is_lt(T x, T y)
static constexpr Mask< T > is_zero(T x)
constexpr void mul(W x, W y)
constexpr void conditional_swap_ptr(bool cnd, T &x, T &y)
constexpr void conditional_swap(bool cnd, T &x, T &y)
constexpr Mask< T > conditional_assign_mem(T cnd, T *sink, const T *src, size_t elems)
constexpr Mask< T > conditional_copy_mem(Mask< T > mask, T *to, const T *from0, const T *from1, size_t elems)
constexpr void unpoison(const T *p, size_t n)
constexpr void bigint_cnd_abs(W cnd, W x[], size_t size)
constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y)
constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size)
constexpr auto word8_sub3(W z[8], const W x[8], const W y[8], W carry) -> W
constexpr W shift_left(std::array< W, N > &x)
constexpr auto word_sub(W x, W y, W *carry) -> W
constexpr auto word_add(W x, W y, W *carry) -> W
constexpr void comba_sqr(W z[2 *N], const W x[N])
constexpr uint64_t carry_shift(const donna128 &a, size_t shift)
constexpr void bigint_shr2(W y[], const W x[], size_t x_size, size_t shift)
BOTAN_FUZZER_API void basecase_sqr(word z[], size_t z_size, const word x[], size_t x_size)
constexpr size_t read_window_bits(std::span< const W, N > words, size_t offset)
void bigint_comba_sqr4(word z[8], const word x[4])
void bigint_comba_sqr6(word z[12], const word x[6])
constexpr void bigint_shr1(W x[], size_t x_size, size_t shift)
constexpr auto word8_add3(W z[8], const W x[8], const W y[8], W carry) -> W
BOTAN_FUZZER_API void bigint_monty_redc_6(word r[6], const word z[12], const word p[6], word p_dash, word ws[6])
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
constexpr auto word8_sub2(W x[8], const W y[8], W carry) -> W
void bigint_comba_sqr7(word z[14], const word x[7])
void bigint_comba_mul4(word z[8], const word x[4], const word y[4])
constexpr auto word_madd2(W a, W b, W *c) -> W
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
void bigint_comba_mul16(word z[32], const word x[16], const word y[16])
constexpr auto word8_sub2_rev(W x[8], const W y[8], W carry) -> W
BOTAN_FUZZER_API void bigint_monty_redc_24(word r[24], const word z[48], const word p[24], word p_dash, word ws[24])
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
constexpr auto monty_inverse(W a) -> W
BOTAN_FUZZER_API void bigint_monty_redc_generic(word r[], const word z[], size_t z_size, const word p[], size_t p_size, word p_dash, word ws[])
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
constexpr auto bigint_cnd_addsub(CT::Mask< W > mask, W x[], const W y[], const W z[], size_t size) -> W
void bigint_comba_mul6(word z[12], const word x[6], const word y[6])
constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift)
constexpr auto bigint_ct_is_eq(const W x[], size_t x_size, const W y[], size_t y_size) -> CT::Mask< W >
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
BOTAN_FUZZER_API void bigint_monty_redc_4(word r[4], const word z[8], const word p[4], word p_dash, word ws[4])
void bigint_monty_redc_inplace(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
void bigint_monty_redc(word r[], const word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
void bigint_comba_mul7(word z[14], const word x[7], const word y[7])
constexpr auto bigint_cnd_sub(W cnd, 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[])
constexpr void bigint_shl2(W y[], const W x[], size_t x_size, size_t shift)
void bigint_comba_mul9(word z[18], const word x[9], const word y[9])
BOTAN_FUZZER_API void bigint_monty_redc_12(word r[12], const word z[24], const word p[12], word p_dash, word ws[12])
constexpr W bigint_cnd_add(W cnd, W x[], size_t x_size, const W y[], size_t y_size)
void carry(int64_t &h0, int64_t &h1)
constexpr auto word8_linmul2(W x[8], W y, W carry) -> W
BOTAN_FUZZER_API void bigint_monty_redc_16(word r[16], const word z[32], const word p[16], word p_dash, word ws[16])
void bigint_comba_mul24(word z[48], const word x[24], const word y[24])
constexpr auto bigint_modop_vartime(W n1, W n0, W d) -> W
constexpr auto bigint_sub_abs(W z[], const W x[], const W y[], size_t N, W ws[]) -> CT::Mask< W >
constexpr void bigint_add2(W x[], size_t x_size, const W y[], size_t y_size)
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
constexpr std::array< W, N > redc_crandall(std::span< const W, 2 *N > z)
constexpr void bigint_correct_redc(std::array< W, N > &r, const std::array< W, N > &P, const std::array< W, N > &C)
constexpr auto word8_add2(W x[8], const W y[8], W carry) -> W
constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W
void bigint_comba_sqr8(word z[16], const word x[8])
constexpr auto hex_to_words(const char(&s)[N])
void bigint_comba_sqr16(word z[32], const word x[16])
constexpr void bigint_cnd_add_or_sub(CT::Mask< W > mask, W x[], const W y[], size_t size)
constexpr void bigint_sub2_rev(W x[], const W y[], size_t y_size)
void bigint_comba_sqr9(word z[18], const word x[9])
constexpr auto bigint_add2_nc(W x[], size_t x_size, const W y[], size_t y_size) -> W
constexpr auto word8_linmul3(W z[8], const W x[8], W y, W carry) -> W
BOTAN_FUZZER_API void basecase_mul(word z[], size_t z_size, const word x[], size_t x_size, const word y[], size_t y_size)
constexpr void bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size)
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
void bigint_comba_sqr24(word z[48], const word x[24])
constexpr void copy_mem(T *out, const T *in, size_t n)
void bigint_comba_mul8(word z[16], const word x[8], const word y[8])
BOTAN_FUZZER_API void bigint_monty_redc_8(word r[8], const word z[16], const word p[8], word p_dash, word ws[8])
constexpr void clear_mem(T *ptr, size_t n)
constexpr auto bigint_divop_vartime(W n1, W n0, W d) -> W
constexpr W shift_right(std::array< W, N > &x)
constexpr void bigint_mod_sub(W t[], const W s[], const W mod[], size_t mod_sw, W ws[])
BOTAN_FUZZER_API void bigint_monty_redc_32(word r[32], const word z[64], const word p[32], word p_dash, word ws[32])
constexpr auto word_madd3(W a, W b, W c, W *d) -> W
constexpr auto bigint_add3_nc(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
constexpr auto bigint_linmul2(W x[], size_t x_size, W y) -> W