10#ifndef BOTAN_MP_CORE_OPS_H_
11#define BOTAN_MP_CORE_OPS_H_
13#include <botan/types.h>
14#include <botan/exceptn.h>
15#include <botan/mem_ops.h>
16#include <botan/internal/mp_asmi.h>
17#include <botan/internal/ct_utils.h>
33 for(
size_t i = 0; i != size; ++i)
37 x[i] = mask.select(b, a);
38 y[i] = mask.select(a, b);
43 const word y[],
size_t y_size)
51 const size_t blocks = y_size - (y_size % 8);
54 for(
size_t i = 0; i != blocks; i += 8)
57 mask.select_n(x + i, z, x + i, 8);
60 for(
size_t i = blocks; i != y_size; ++i)
63 x[i] = mask.select(z[0], x[i]);
66 for(
size_t i = y_size; i != x_size; ++i)
69 x[i] = mask.select(z[0], x[i]);
72 return mask.if_set_return(
carry);
89 word x[],
size_t x_size,
90 const word y[],
size_t y_size)
98 const size_t blocks = y_size - (y_size % 8);
101 for(
size_t i = 0; i != blocks; i += 8)
104 mask.select_n(x + i, z, x + i, 8);
107 for(
size_t i = blocks; i != y_size; ++i)
110 x[i] = mask.select(z[0], x[i]);
113 for(
size_t i = y_size; i != x_size; ++i)
116 x[i] = mask.select(z[0], x[i]);
119 return mask.if_set_return(
carry);
141 const size_t blocks = size - (size % 8);
149 for(
size_t i = 0; i != blocks; i += 8)
152 borrow =
word8_sub3(t1, x + i, y + i, borrow);
154 for(
size_t j = 0; j != 8; ++j)
155 x[i+j] = mask.
select(t0[j], t1[j]);
158 for(
size_t i = blocks; i != size; ++i)
161 const word s =
word_sub(x[i], y[i], &borrow);
177 const word y[],
const word z[],
180 const size_t blocks = size - (size % 8);
188 for(
size_t i = 0; i != blocks; i += 8)
191 borrow =
word8_sub3(t1, x + i, z + i, borrow);
193 for(
size_t j = 0; j != 8; ++j)
194 x[i+j] = mask.
select(t0[j], t1[j]);
197 for(
size_t i = blocks; i != size; ++i)
200 t1[0] =
word_sub(x[i], z[i], &borrow);
201 x[i] = mask.
select(t0[0], t1[0]);
216 word
carry = mask.if_set_return(1);
217 for(
size_t i = 0; i != size; ++i)
220 x[i] = mask.select(z, x[i]);
227inline word
bigint_add2_nc(word x[],
size_t x_size,
const word y[],
size_t y_size)
233 const size_t blocks = y_size - (y_size % 8);
235 for(
size_t i = 0; i != blocks; i += 8)
238 for(
size_t i = blocks; i != y_size; ++i)
241 for(
size_t i = y_size; i != x_size; ++i)
251 const word x[],
size_t x_size,
252 const word y[],
size_t y_size)
259 const size_t blocks = y_size - (y_size % 8);
261 for(
size_t i = 0; i != blocks; i += 8)
264 for(
size_t i = blocks; i != y_size; ++i)
267 for(
size_t i = y_size; i != x_size; ++i)
281 const word y[],
size_t y_size)
290 const word x[],
size_t x_size,
291 const word y[],
size_t y_size)
293 z[x_size > y_size ? x_size : y_size] +=
301 const word y[],
size_t y_size)
307 const size_t blocks = y_size - (y_size % 8);
309 for(
size_t i = 0; i != blocks; i += 8)
312 for(
size_t i = blocks; i != y_size; ++i)
313 x[i] =
word_sub(x[i], y[i], &borrow);
315 for(
size_t i = y_size; i != x_size; ++i)
328 const size_t blocks = y_size - (y_size % 8);
330 for(
size_t i = 0; i != blocks; i += 8)
333 for(
size_t i = blocks; i != y_size; ++i)
334 x[i] =
word_sub(y[i], x[i], &borrow);
343 const word x[],
size_t x_size,
344 const word y[],
size_t y_size)
350 const size_t blocks = y_size - (y_size % 8);
352 for(
size_t i = 0; i != blocks; i += 8)
353 borrow =
word8_sub3(z + i, x + i, y + i, borrow);
355 for(
size_t i = blocks; i != y_size; ++i)
356 z[i] =
word_sub(x[i], y[i], &borrow);
358 for(
size_t i = y_size; i != x_size; ++i)
378 const word x[],
const word y[],
size_t N,
389 const size_t blocks = N - (N % 8);
391 for(
size_t i = 0; i != blocks; i += 8)
393 borrow0 =
word8_sub3(ws0 + i, x + i, y + i, borrow0);
394 borrow1 =
word8_sub3(ws1 + i, y + i, x + i, borrow1);
397 for(
size_t i = blocks; i != N; ++i)
399 ws0[i] =
word_sub(x[i], y[i], &borrow0);
400 ws1[i] =
word_sub(y[i], x[i], &borrow1);
410 size_t word_shift,
size_t bit_shift)
412 copy_mem(x + word_shift, x, x_words);
416 const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
419 for(
size_t i = word_shift; i != x_size; ++i)
422 x[i] = (w << bit_shift) |
carry;
428 size_t word_shift,
size_t bit_shift)
430 const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0;
434 clear_mem(x + top, std::min(word_shift, x_size));
437 const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
441 for(
size_t i = 0; i != top; ++i)
443 const word w = x[top - i - 1];
444 x[top-i-1] = (w >> bit_shift) |
carry;
450 size_t word_shift,
size_t bit_shift)
452 copy_mem(y + word_shift, x, x_size);
455 const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
458 for(
size_t i = word_shift; i != x_size + word_shift + 1; ++i)
461 y[i] = (w << bit_shift) |
carry;
467 size_t word_shift,
size_t bit_shift)
469 const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift);
472 copy_mem(y, x + word_shift, new_size);
475 const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
478 for(
size_t i = new_size; i > 0; --i)
481 y[i-1] = (w >> bit_shift) |
carry;
491 const size_t blocks = x_size - (x_size % 8);
495 for(
size_t i = 0; i != blocks; i += 8)
498 for(
size_t i = blocks; i != x_size; ++i)
506 const size_t blocks = x_size - (x_size % 8);
510 for(
size_t i = 0; i != blocks; i += 8)
513 for(
size_t i = blocks; i != x_size; ++i)
526 const word y[],
size_t y_size)
528 static_assert(
sizeof(word) >=
sizeof(uint32_t),
"Size assumption");
530 const word LT =
static_cast<word
>(-1);
534 const size_t common_elems = std::min(x_size, y_size);
538 for(
size_t i = 0; i != common_elems; i++)
543 result = is_eq.select(result, is_lt.select(LT, GT));
549 for(
size_t i = x_size; i != y_size; i++)
555 else if(y_size < x_size)
558 for(
size_t i = y_size; i != x_size; i++)
567 return static_cast<int32_t
>(result);
577 const word y[],
size_t y_size,
578 bool lt_or_equal =
false)
580 const size_t common_elems = std::min(x_size, y_size);
584 for(
size_t i = 0; i != common_elems; i++)
588 is_lt = eq.select_mask(is_lt, lt);
594 for(
size_t i = x_size; i != y_size; i++)
599 else if(y_size < x_size)
602 for(
size_t i = y_size; i != x_size; i++)
614 const word y[],
size_t y_size)
616 const size_t common_elems = std::min(x_size, y_size);
620 for(
size_t i = 0; i != common_elems; i++)
622 diff |= (x[i] ^ y[i]);
628 for(
size_t i = x_size; i != y_size; i++)
631 else if(y_size < x_size)
633 for(
size_t i = y_size; i != x_size; i++)
655 const word x[],
size_t x_size,
656 const word y[],
size_t y_size)
658 const int32_t relative_size =
bigint_cmp(x, x_size, y, y_size);
661 const bool need_swap = relative_size < 0;
670 y_size = std::min(x_size, y_size);
674 return relative_size;
687bigint_mod_sub(word t[],
const word s[],
const word mod[],
size_t mod_sw, word ws[])
693 const word borrow =
bigint_sub3(ws, mod, mod_sw, s, mod_sw);
726#if defined(BOTAN_HAS_MP_DWORD)
727 return static_cast<word
>(((
static_cast<dword
>(n1) << BOTAN_MP_WORD_BITS) | n0) / d);
733 for(
size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i)
735 const word high_top_bit = high >> (BOTAN_MP_WORD_BITS-1);
738 high |= (n0 >> (BOTAN_MP_WORD_BITS-1-i)) & 1;
741 if(high_top_bit || high >= d)
760#if defined(BOTAN_HAS_MP_DWORD)
761 return ((
static_cast<dword
>(n1) << BOTAN_MP_WORD_BITS) | n0) % d;
799 const word p[],
size_t p_size,
809 const word x[],
size_t x_size,
size_t x_sw,
810 const word y[],
size_t y_size,
size_t y_sw,
811 word workspace[],
size_t ws_size);
814 const word x[],
size_t x_size,
size_t x_sw,
815 word workspace[],
size_t ws_size);
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_UNUSED(...)
#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_WARN_UNUSED_RESULT
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)
word BOTAN_WARN_UNUSED_RESULT bigint_linmul2(word x[], size_t x_size, word y)
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
void bigint_comba_mul4(word z[8], const word x[4], const word y[4])
word word8_sub2(word x[8], const word y[8], word carry)
void bigint_shl1(word x[], size_t x_size, size_t x_words, size_t word_shift, size_t bit_shift)
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
void bigint_comba_sqr6(word z[12], const word x[6])
void bigint_comba_sqr16(word z[32], const word x[16])
void bigint_cnd_add_or_sub(CT::Mask< word > mask, word x[], const word y[], size_t size)
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)
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)
word word8_add2(word x[8], const word y[8], word carry)
void bigint_comba_mul8(word z[16], const word x[8], const word y[8])
word word8_linmul3(word z[8], const word x[8], word y, word carry)
void bigint_comba_sqr4(word z[8], const word x[4])
void carry(int64_t &h0, int64_t &h1)
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_comba_sqr9(word z[18], const word x[9])
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
void copy_mem(T *out, const T *in, size_t n)
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_mul24(word z[48], const word x[24], const word y[24])
void bigint_comba_sqr24(word z[48], const word x[24])
word word_madd2(word a, word b, word *c)
word word_add(word x, word y, word *carry)
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
void bigint_comba_mul9(word z[18], const word x[9], const word y[9])
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
word word8_sub2_rev(word x[8], const word y[8], word carry)
word bigint_modop(word n1, word n0, word d)
void bigint_cnd_abs(word cnd, word x[], size_t 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)
void bigint_comba_mul16(word z[32], const word x[16], const word y[16])
void bigint_comba_mul6(word z[12], const word x[6], const word y[6])
void clear_mem(T *ptr, size_t n)
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
void bigint_comba_sqr8(word z[16], const word x[8])
CT::Mask< word > bigint_ct_is_eq(const word x[], size_t x_size, const word y[], size_t y_size)
void bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])