10#ifndef BOTAN_MP_CORE_OPS_H_
11#define BOTAN_MP_CORE_OPS_H_
13#include <botan/exceptn.h>
14#include <botan/mem_ops.h>
15#include <botan/types.h>
16#include <botan/internal/ct_utils.h>
17#include <botan/internal/mp_asmi.h>
32 for(
size_t i = 0; i != size; ++i) {
35 x[i] = mask.select(b, a);
36 y[i] = mask.select(a, b);
40inline word
bigint_cnd_add(word cnd, word x[], word x_size,
const word y[],
size_t y_size) {
47 const size_t blocks = y_size - (y_size % 8);
50 for(
size_t i = 0; i != blocks; i += 8) {
52 mask.select_n(x + i, z, x + i, 8);
55 for(
size_t i = blocks; i != y_size; ++i) {
57 x[i] = mask.select(z[0], x[i]);
60 for(
size_t i = y_size; i != x_size; ++i) {
62 x[i] = mask.select(z[0], x[i]);
65 return mask.if_set_return(
carry);
80inline word
bigint_cnd_sub(word cnd, word x[],
size_t x_size,
const word y[],
size_t y_size) {
87 const size_t blocks = y_size - (y_size % 8);
90 for(
size_t i = 0; i != blocks; i += 8) {
92 mask.select_n(x + i, z, x + i, 8);
95 for(
size_t i = blocks; i != y_size; ++i) {
97 x[i] = mask.select(z[0], x[i]);
100 for(
size_t i = y_size; i != x_size; ++i) {
102 x[i] = mask.select(z[0], x[i]);
105 return mask.if_set_return(
carry);
124 const size_t blocks = size - (size % 8);
132 for(
size_t i = 0; i != blocks; i += 8) {
134 borrow =
word8_sub3(t1, x + i, y + i, borrow);
136 for(
size_t j = 0; j != 8; ++j) {
137 x[i + j] = mask.
select(t0[j], t1[j]);
141 for(
size_t i = blocks; i != size; ++i) {
143 const word s =
word_sub(x[i], y[i], &borrow);
159 const size_t blocks = size - (size % 8);
167 for(
size_t i = 0; i != blocks; i += 8) {
169 borrow =
word8_sub3(t1, x + i, z + i, borrow);
171 for(
size_t j = 0; j != 8; ++j) {
172 x[i + j] = mask.
select(t0[j], t1[j]);
176 for(
size_t i = blocks; i != size; ++i) {
178 t1[0] =
word_sub(x[i], z[i], &borrow);
179 x[i] = mask.
select(t0[0], t1[0]);
193 word
carry = mask.if_set_return(1);
194 for(
size_t i = 0; i != size; ++i) {
196 x[i] = mask.select(z, x[i]);
203inline word
bigint_add2_nc(word x[],
size_t x_size,
const word y[],
size_t y_size) {
208 const size_t blocks = y_size - (y_size % 8);
210 for(
size_t i = 0; i != blocks; i += 8) {
214 for(
size_t i = blocks; i != y_size; ++i) {
218 for(
size_t i = y_size; i != x_size; ++i) {
228inline word
bigint_add3_nc(word z[],
const word x[],
size_t x_size,
const word y[],
size_t y_size) {
229 if(x_size < y_size) {
235 const size_t blocks = y_size - (y_size % 8);
237 for(
size_t i = 0; i != blocks; i += 8) {
241 for(
size_t i = blocks; i != y_size; ++i) {
245 for(
size_t i = y_size; i != x_size; ++i) {
259inline void bigint_add2(word x[],
size_t x_size,
const word y[],
size_t y_size) {
266inline void bigint_add3(word z[],
const word x[],
size_t x_size,
const word y[],
size_t y_size) {
267 z[x_size > y_size ? x_size : y_size] +=
bigint_add3_nc(z, x, x_size, y, y_size);
273inline word
bigint_sub2(word x[],
size_t x_size,
const word y[],
size_t y_size) {
278 const size_t blocks = y_size - (y_size % 8);
280 for(
size_t i = 0; i != blocks; i += 8) {
284 for(
size_t i = blocks; i != y_size; ++i) {
285 x[i] =
word_sub(x[i], y[i], &borrow);
288 for(
size_t i = y_size; i != x_size; ++i) {
301 const size_t blocks = y_size - (y_size % 8);
303 for(
size_t i = 0; i != blocks; i += 8) {
307 for(
size_t i = blocks; i != y_size; ++i) {
308 x[i] =
word_sub(y[i], x[i], &borrow);
321inline word
bigint_sub3(word z[],
const word x[],
size_t x_size,
const word y[],
size_t y_size) {
326 const size_t blocks = y_size - (y_size % 8);
328 for(
size_t i = 0; i != blocks; i += 8) {
329 borrow =
word8_sub3(z + i, x + i, y + i, borrow);
332 for(
size_t i = blocks; i != y_size; ++i) {
333 z[i] =
word_sub(x[i], y[i], &borrow);
336 for(
size_t i = y_size; i != x_size; ++i) {
364 const size_t blocks = N - (N % 8);
366 for(
size_t i = 0; i != blocks; i += 8) {
367 borrow0 =
word8_sub3(ws0 + i, x + i, y + i, borrow0);
368 borrow1 =
word8_sub3(ws1 + i, y + i, x + i, borrow1);
371 for(
size_t i = blocks; i != N; ++i) {
372 ws0[i] =
word_sub(x[i], y[i], &borrow0);
373 ws1[i] =
word_sub(y[i], x[i], &borrow1);
382inline void bigint_shl1(word x[],
size_t x_size,
size_t x_words,
size_t word_shift,
size_t bit_shift) {
383 copy_mem(x + word_shift, x, x_words);
390 for(
size_t i = word_shift; i != x_size; ++i) {
392 x[i] = (w << bit_shift) |
carry;
397inline void bigint_shr1(word x[],
size_t x_size,
size_t word_shift,
size_t bit_shift) {
398 const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0;
403 clear_mem(x + top, std::min(word_shift, x_size));
410 for(
size_t i = 0; i != top; ++i) {
411 const word w = x[top - i - 1];
412 x[top - i - 1] = (w >> bit_shift) |
carry;
417inline void bigint_shl2(word y[],
const word x[],
size_t x_size,
size_t word_shift,
size_t bit_shift) {
418 copy_mem(y + word_shift, x, x_size);
424 for(
size_t i = word_shift; i != x_size + word_shift + 1; ++i) {
426 y[i] = (w << bit_shift) |
carry;
431inline void bigint_shr2(word y[],
const word x[],
size_t x_size,
size_t word_shift,
size_t bit_shift) {
432 const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift);
435 copy_mem(y, x + word_shift, new_size);
442 for(
size_t i = new_size; i > 0; --i) {
444 y[i - 1] = (w >> bit_shift) |
carry;
453 const size_t blocks = x_size - (x_size % 8);
457 for(
size_t i = 0; i != blocks; i += 8) {
461 for(
size_t i = blocks; i != x_size; ++i) {
469 const size_t blocks = x_size - (x_size % 8);
473 for(
size_t i = 0; i != blocks; i += 8) {
477 for(
size_t i = blocks; i != x_size; ++i) {
490inline int32_t
bigint_cmp(
const word x[],
size_t x_size,
const word y[],
size_t y_size) {
491 static_assert(
sizeof(word) >=
sizeof(uint32_t),
"Size assumption");
493 const word LT =
static_cast<word
>(-1);
497 const size_t common_elems = std::min(x_size, y_size);
501 for(
size_t i = 0; i != common_elems; i++) {
505 result = is_eq.select(result, is_lt.select(LT, GT));
508 if(x_size < y_size) {
510 for(
size_t i = x_size; i != y_size; i++) {
516 }
else if(y_size < x_size) {
518 for(
size_t i = y_size; i != x_size; i++) {
528 return static_cast<int32_t
>(result);
537 const word x[],
size_t x_size,
const word y[],
size_t y_size,
bool lt_or_equal =
false) {
538 const size_t common_elems = std::min(x_size, y_size);
542 for(
size_t i = 0; i != common_elems; i++) {
545 is_lt = eq.select_mask(is_lt, lt);
548 if(x_size < y_size) {
550 for(
size_t i = x_size; i != y_size; i++) {
555 }
else if(y_size < x_size) {
557 for(
size_t i = y_size; i != x_size; i++) {
569 const size_t common_elems = std::min(x_size, y_size);
573 for(
size_t i = 0; i != common_elems; i++) {
574 diff |= (x[i] ^ y[i]);
578 if(x_size < y_size) {
579 for(
size_t i = x_size; i != y_size; i++) {
582 }
else if(y_size < x_size) {
583 for(
size_t i = y_size; i != x_size; i++) {
604inline int32_t
bigint_sub_abs(word z[],
const word x[],
size_t x_size,
const word y[],
size_t y_size) {
605 const int32_t relative_size =
bigint_cmp(x, x_size, y, y_size);
608 const bool need_swap = relative_size < 0;
617 y_size = std::min(x_size, y_size);
621 return relative_size;
633inline void bigint_mod_sub(word t[],
const word s[],
const word mod[],
size_t mod_sw, word ws[]) {
638 const word borrow =
bigint_sub3(ws, mod, mod_sw, s, mod_sw);
670#if defined(BOTAN_MP_DWORD)
671 return static_cast<word
>(((
static_cast<BOTAN_MP_DWORD
>(n1) <<
BOTAN_MP_WORD_BITS) | n0) / d);
684 if(high_top_bit || high >= d) {
702#if defined(BOTAN_MP_DWORD)
757inline void bigint_monty_redc(word z[],
const word p[],
size_t p_size, word p_dash, word ws[],
size_t ws_size) {
758 const size_t z_size = 2 * p_size;
760 BOTAN_ARG_CHECK(ws_size >= p_size + 1,
"Montgomery workspace too small");
764 }
else if(p_size == 6) {
766 }
else if(p_size == 8) {
768 }
else if(p_size == 16) {
770 }
else if(p_size == 24) {
772 }
else if(p_size == 32) {
783void basecase_mul(word z[],
size_t z_size,
const word x[],
size_t x_size,
const word y[],
size_t y_size);
789void basecase_sqr(word z[],
size_t z_size,
const word x[],
size_t x_size);
805void 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);
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ARG_CHECK(expr, msg)
#define BOTAN_ASSERT(expr, assertion_made)
static Mask< T > is_equal(T x, T y)
static Mask< T > is_zero(T x)
static Mask< T > expand(T v)
static Mask< T > is_lt(T x, T y)
#define BOTAN_MP_WORD_BITS
Mask< T > conditional_copy_mem(Mask< T > mask, T *to, const T *from0, const T *from1, size_t elems)
void conditional_swap_ptr(bool cnd, T &x, T &y)
void conditional_swap(bool cnd, T &x, T &y)
void unpoison(const T *p, size_t n)
word word8_sub3(word z[8], const word x[8], const word y[8], word carry)
word bigint_modop_vartime(word n1, word n0, word d)
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
word word_sub(word x, word y, word *carry)
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
word word8_sub2(word x[8], const word y[8], word carry)
BOTAN_FUZZER_API void basecase_sqr(word z[], size_t z_size, const word x[], size_t x_size)
void bigint_shl1(word x[], size_t x_size, size_t x_words, size_t word_shift, size_t bit_shift)
void bigint_comba_sqr4(word z[8], const word x[4])
void bigint_comba_sqr6(word z[12], const word x[6])
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
BOTAN_FUZZER_API void bigint_monty_redc_24(word z[48], const word p[24], word p_dash, word ws[])
void bigint_cnd_add_or_sub(CT::Mask< word > mask, word x[], const word y[], size_t size)
void bigint_comba_mul4(word z[8], const word x[4], const word y[4])
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])
word bigint_cnd_add(word cnd, word x[], word x_size, const word y[], size_t y_size)
word bigint_cnd_sub(word cnd, word x[], size_t x_size, const word y[], size_t y_size)
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, 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)
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
void bigint_comba_mul6(word z[12], const word x[6], const word y[6])
word word8_add2(word x[8], const word y[8], word carry)
word word8_linmul3(word z[8], const word x[8], word y, word carry)
BOTAN_FUZZER_API void bigint_monty_redc_4(word z[8], const word p[4], word p_dash, word ws[])
word word8_linmul2(word x[8], word y, word carry)
word bigint_cnd_addsub(CT::Mask< word > mask, word x[], const word y[], const word z[], size_t size)
CT::Mask< word > bigint_ct_is_lt(const word x[], size_t x_size, const word y[], size_t y_size, bool lt_or_equal=false)
uint64_t carry_shift(const donna128 &a, size_t shift)
word bigint_divop_vartime(word n1, word n0, word d)
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
word word8_add3(word z[8], const word x[8], const word y[8], word carry)
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
void bigint_comba_mul9(word z[18], const word x[9], const word y[9])
word word_madd2(word a, word b, word *c)
void carry(int64_t &h0, int64_t &h1)
word word_add(word x, word y, word *carry)
void bigint_comba_mul24(word z[48], const word x[24], const word y[24])
BOTAN_FUZZER_API void bigint_monty_redc_6(word z[12], const word p[6], word p_dash, word ws[])
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
void bigint_comba_sqr8(word z[16], const word x[8])
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
void bigint_comba_sqr16(word z[32], const word x[16])
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
void bigint_comba_sqr9(word z[18], const word x[9])
word word8_sub2_rev(word x[8], const word y[8], word carry)
word bigint_linmul2(word x[], size_t x_size, word y)
void bigint_cnd_abs(word cnd, word x[], size_t size)
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)
void bigint_mod_sub_n(word t[], const word s[], const word mod[], word ws[])
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
BOTAN_FUZZER_API void bigint_monty_redc_generic(word z[], size_t z_size, const word p[], size_t p_size, word p_dash, word ws[])
void bigint_comba_sqr24(word z[48], const word x[24])
constexpr void copy_mem(T *out, const T *in, size_t n)
BOTAN_FUZZER_API void bigint_monty_redc_32(word z[64], const word p[32], word p_dash, word ws[])
void bigint_comba_mul8(word z[16], const word x[8], const word y[8])
BOTAN_FUZZER_API void bigint_monty_redc_16(word z[32], const word p[16], word p_dash, word ws[])
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
constexpr void clear_mem(T *ptr, size_t n)
CT::Mask< word > bigint_ct_is_eq(const word x[], size_t x_size, const word y[], size_t y_size)
BOTAN_FUZZER_API void bigint_monty_redc_8(word z[16], const word p[8], word p_dash, word ws[])
void bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])