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]);
140 for(
size_t i = blocks; i != size; ++i) {
142 const word s =
word_sub(x[i], y[i], &borrow);
158 const size_t blocks = size - (size % 8);
166 for(
size_t i = 0; i != blocks; i += 8) {
168 borrow =
word8_sub3(t1, x + i, z + i, borrow);
170 for(
size_t j = 0; j != 8; ++j)
171 x[i + j] = mask.
select(t0[j], t1[j]);
174 for(
size_t i = blocks; i != size; ++i) {
176 t1[0] =
word_sub(x[i], z[i], &borrow);
177 x[i] = mask.
select(t0[0], t1[0]);
191 word
carry = mask.if_set_return(1);
192 for(
size_t i = 0; i != size; ++i) {
194 x[i] = mask.select(z, x[i]);
201inline word
bigint_add2_nc(word x[],
size_t x_size,
const word y[],
size_t y_size) {
206 const size_t blocks = y_size - (y_size % 8);
208 for(
size_t i = 0; i != blocks; i += 8)
211 for(
size_t i = blocks; i != y_size; ++i)
214 for(
size_t i = y_size; i != x_size; ++i)
223inline word
bigint_add3_nc(word z[],
const word x[],
size_t x_size,
const word y[],
size_t y_size) {
224 if(x_size < y_size) {
230 const size_t blocks = y_size - (y_size % 8);
232 for(
size_t i = 0; i != blocks; i += 8)
235 for(
size_t i = blocks; i != y_size; ++i)
238 for(
size_t i = y_size; i != x_size; ++i)
251inline void bigint_add2(word x[],
size_t x_size,
const word y[],
size_t y_size) {
258inline void bigint_add3(word z[],
const word x[],
size_t x_size,
const word y[],
size_t y_size) {
259 z[x_size > y_size ? x_size : y_size] +=
bigint_add3_nc(z, x, x_size, y, y_size);
265inline word
bigint_sub2(word x[],
size_t x_size,
const word y[],
size_t y_size) {
270 const size_t blocks = y_size - (y_size % 8);
272 for(
size_t i = 0; i != blocks; i += 8)
275 for(
size_t i = blocks; i != y_size; ++i)
276 x[i] =
word_sub(x[i], y[i], &borrow);
278 for(
size_t i = y_size; i != x_size; ++i)
290 const size_t blocks = y_size - (y_size % 8);
292 for(
size_t i = 0; i != blocks; i += 8)
295 for(
size_t i = blocks; i != y_size; ++i)
296 x[i] =
word_sub(y[i], x[i], &borrow);
308inline word
bigint_sub3(word z[],
const word x[],
size_t x_size,
const word y[],
size_t y_size) {
313 const size_t blocks = y_size - (y_size % 8);
315 for(
size_t i = 0; i != blocks; i += 8)
316 borrow =
word8_sub3(z + i, x + i, y + i, borrow);
318 for(
size_t i = blocks; i != y_size; ++i)
319 z[i] =
word_sub(x[i], y[i], &borrow);
321 for(
size_t i = y_size; i != x_size; ++i)
348 const size_t blocks = N - (N % 8);
350 for(
size_t i = 0; i != blocks; i += 8) {
351 borrow0 =
word8_sub3(ws0 + i, x + i, y + i, borrow0);
352 borrow1 =
word8_sub3(ws1 + i, y + i, x + i, borrow1);
355 for(
size_t i = blocks; i != N; ++i) {
356 ws0[i] =
word_sub(x[i], y[i], &borrow0);
357 ws1[i] =
word_sub(y[i], x[i], &borrow1);
366inline void bigint_shl1(word x[],
size_t x_size,
size_t x_words,
size_t word_shift,
size_t bit_shift) {
367 copy_mem(x + word_shift, x, x_words);
374 for(
size_t i = word_shift; i != x_size; ++i) {
376 x[i] = (w << bit_shift) |
carry;
381inline void bigint_shr1(word x[],
size_t x_size,
size_t word_shift,
size_t bit_shift) {
382 const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0;
386 clear_mem(x + top, std::min(word_shift, x_size));
393 for(
size_t i = 0; i != top; ++i) {
394 const word w = x[top - i - 1];
395 x[top - i - 1] = (w >> bit_shift) |
carry;
400inline void bigint_shl2(word y[],
const word x[],
size_t x_size,
size_t word_shift,
size_t bit_shift) {
401 copy_mem(y + word_shift, x, x_size);
407 for(
size_t i = word_shift; i != x_size + word_shift + 1; ++i) {
409 y[i] = (w << bit_shift) |
carry;
414inline void bigint_shr2(word y[],
const word x[],
size_t x_size,
size_t word_shift,
size_t bit_shift) {
415 const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift);
418 copy_mem(y, x + word_shift, new_size);
424 for(
size_t i = new_size; i > 0; --i) {
426 y[i - 1] = (w >> bit_shift) |
carry;
435 const size_t blocks = x_size - (x_size % 8);
439 for(
size_t i = 0; i != blocks; i += 8)
442 for(
size_t i = blocks; i != x_size; ++i)
449 const size_t blocks = x_size - (x_size % 8);
453 for(
size_t i = 0; i != blocks; i += 8)
456 for(
size_t i = blocks; i != x_size; ++i)
468inline int32_t
bigint_cmp(
const word x[],
size_t x_size,
const word y[],
size_t y_size) {
469 static_assert(
sizeof(word) >=
sizeof(uint32_t),
"Size assumption");
471 const word LT =
static_cast<word
>(-1);
475 const size_t common_elems = std::min(x_size, y_size);
479 for(
size_t i = 0; i != common_elems; i++) {
483 result = is_eq.select(result, is_lt.select(LT, GT));
486 if(x_size < y_size) {
488 for(
size_t i = x_size; i != y_size; i++)
493 }
else if(y_size < x_size) {
495 for(
size_t i = y_size; i != x_size; i++)
504 return static_cast<int32_t
>(result);
513 const word x[],
size_t x_size,
const word y[],
size_t y_size,
bool lt_or_equal =
false) {
514 const size_t common_elems = std::min(x_size, y_size);
518 for(
size_t i = 0; i != common_elems; i++) {
521 is_lt = eq.select_mask(is_lt, lt);
524 if(x_size < y_size) {
526 for(
size_t i = x_size; i != y_size; i++)
530 }
else if(y_size < x_size) {
532 for(
size_t i = y_size; i != x_size; i++)
543 const size_t common_elems = std::min(x_size, y_size);
547 for(
size_t i = 0; i != common_elems; i++) {
548 diff |= (x[i] ^ y[i]);
552 if(x_size < y_size) {
553 for(
size_t i = x_size; i != y_size; i++)
555 }
else if(y_size < x_size) {
556 for(
size_t i = y_size; i != x_size; i++)
576inline int32_t
bigint_sub_abs(word z[],
const word x[],
size_t x_size,
const word y[],
size_t y_size) {
577 const int32_t relative_size =
bigint_cmp(x, x_size, y, y_size);
580 const bool need_swap = relative_size < 0;
589 y_size = std::min(x_size, y_size);
593 return relative_size;
605inline void bigint_mod_sub(word t[],
const word s[],
const word mod[],
size_t mod_sw, word ws[]) {
610 const word borrow =
bigint_sub3(ws, mod, mod_sw, s, mod_sw);
641#if defined(BOTAN_MP_DWORD)
642 return static_cast<word
>(((
static_cast<BOTAN_MP_DWORD
>(n1) <<
BOTAN_MP_WORD_BITS) | n0) / d);
655 if(high_top_bit || high >= d) {
672#if defined(BOTAN_MP_DWORD)
727inline void bigint_monty_redc(word z[],
const word p[],
size_t p_size, word p_dash, word ws[],
size_t ws_size) {
728 const size_t z_size = 2 * p_size;
730 BOTAN_ARG_CHECK(ws_size >= p_size + 1,
"Montgomery workspace too small");
738 else if(p_size == 16)
740 else if(p_size == 24)
742 else if(p_size == 32)
752void basecase_mul(word z[],
size_t z_size,
const word x[],
size_t x_size,
const word y[],
size_t y_size);
758void basecase_sqr(word z[],
size_t z_size,
const word x[],
size_t x_size);
774void 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
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)
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
word bigint_divop(word n1, word n0, word d)
word word8_sub3(word z[8], const word x[8], const word y[8], word carry)
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)
constexpr void copy_mem(T *out, const T *in, size_t n)
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)
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)
word bigint_modop(word n1, word n0, word d)
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])
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[])