9 #include <botan/internal/mp_core.h>
10 #include <botan/internal/mp_asmi.h>
11 #include <botan/internal/ct_utils.h>
12 #include <botan/exceptn.h>
13 #include <botan/mem_ops.h>
26 for(
size_t i = 0; i != size; ++i)
44 for(
size_t i = 0; i != size; ++i)
50 const word z =
word_add(x[i], y[i], &carry);
66 for(
size_t i = 0; i != size; ++i)
68 const word z =
word_sub(x[i], y[i], &carry);
79 word carry = mask & 1;
80 for(
size_t i = 0; i != size; ++i)
82 const word z =
word_add(~x[i], 0, &carry);
96 const size_t blocks = y_size - (y_size % 8);
98 for(
size_t i = 0; i != blocks; i += 8)
101 for(
size_t i = blocks; i != y_size; ++i)
102 x[i] =
word_add(x[i], y[i], &carry);
104 for(
size_t i = y_size; i != x_size; ++i)
114 const word y[],
size_t y_size)
121 const size_t blocks = y_size - (y_size % 8);
123 for(
size_t i = 0; i != blocks; i += 8)
124 carry =
word8_add3(z + i, x + i, y + i, carry);
126 for(
size_t i = blocks; i != y_size; ++i)
127 z[i] =
word_add(x[i], y[i], &carry);
129 for(
size_t i = y_size; i != x_size; ++i)
138 void bigint_add2(word x[],
size_t x_size,
const word y[],
size_t y_size)
148 const word y[],
size_t y_size)
150 z[(x_size > y_size ? x_size : y_size)] +=
157 word
bigint_sub2(word x[],
size_t x_size,
const word y[],
size_t y_size)
163 const size_t blocks = y_size - (y_size % 8);
165 for(
size_t i = 0; i != blocks; i += 8)
168 for(
size_t i = blocks; i != y_size; ++i)
169 x[i] =
word_sub(x[i], y[i], &borrow);
171 for(
size_t i = y_size; i != x_size; ++i)
184 const size_t blocks = y_size - (y_size % 8);
186 for(
size_t i = 0; i != blocks; i += 8)
189 for(
size_t i = blocks; i != y_size; ++i)
190 x[i] =
word_sub(y[i], x[i], &borrow);
199 const word y[],
size_t y_size)
205 const size_t blocks = y_size - (y_size % 8);
207 for(
size_t i = 0; i != blocks; i += 8)
208 borrow =
word8_sub3(z + i, x + i, y + i, borrow);
210 for(
size_t i = blocks; i != y_size; ++i)
211 z[i] =
word_sub(x[i], y[i], &borrow);
213 for(
size_t i = y_size; i != x_size; ++i)
224 const size_t blocks = x_size - (x_size % 8);
228 for(
size_t i = 0; i != blocks; i += 8)
231 for(
size_t i = blocks; i != x_size; ++i)
242 const size_t blocks = x_size - (x_size % 8);
246 for(
size_t i = 0; i != blocks; i += 8)
249 for(
size_t i = blocks; i != x_size; ++i)
258 void bigint_shl1(word x[],
size_t x_size,
size_t word_shift,
size_t bit_shift)
262 copy_mem(x + word_shift, x, x_size);
269 for(
size_t j = word_shift; j != x_size + word_shift + 1; ++j)
272 x[j] = (temp << bit_shift) | carry;
281 void bigint_shr1(word x[],
size_t x_size,
size_t word_shift,
size_t bit_shift)
283 if(x_size < word_shift)
291 copy_mem(x, x + word_shift, x_size - word_shift);
292 clear_mem(x + x_size - word_shift, word_shift);
299 size_t top = x_size - word_shift;
304 x[top-1] = (w >> bit_shift) | carry;
308 x[top-2] = (w >> bit_shift) | carry;
312 x[top-3] = (w >> bit_shift) | carry;
316 x[top-4] = (w >> bit_shift) | carry;
325 x[top-1] = (w >> bit_shift) | carry;
337 size_t word_shift,
size_t bit_shift)
339 for(
size_t j = 0; j != x_size; ++j)
340 y[j + word_shift] = x[j];
344 for(
size_t j = word_shift; j != x_size + word_shift + 1; ++j)
347 y[j] = (w << bit_shift) | carry;
357 size_t word_shift,
size_t bit_shift)
359 if(x_size < word_shift)
return;
361 for(
size_t j = 0; j != x_size - word_shift; ++j)
362 y[j] = x[j + word_shift];
366 for(
size_t j = x_size - word_shift; j > 0; --j)
369 y[j-1] = (w >> bit_shift) | carry;
379 const word y[],
size_t y_size)
381 if(x_size < y_size) {
return (-
bigint_cmp(y, y_size, x, x_size)); }
383 while(x_size > y_size)
390 for(
size_t i = x_size; i > 0; --i)
409 word high = n1 % d, quotient = 0;
419 if(high_top_bit || high >= d)
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
word word8_sub2_rev(word x[8], const word y[8], word carry)
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)
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
void clear_mem(T *ptr, size_t n)
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
void bigint_linmul2(word x[], size_t x_size, word y)
word bigint_add3_nc(word z[], const 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)
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
word bigint_divop(word n1, word n0, word d)
word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
word word_madd2(word a, word b, word *c)
#define BOTAN_ASSERT(expr, assertion_made)
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
word word8_linmul2(word x[8], word y, word carry)
word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
T select(T mask, T from0, T from1)
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
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_cnd_abs(word cnd, word x[], size_t size)
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
word word_sub(word x, word y, word *carry)
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
word word_add(word x, word y, word *carry)
word word8_sub3(word z[8], const word x[8], const word y[8], word carry)
const word MP_WORD_TOP_BIT
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
word bigint_modop(word n1, word n0, word d)
const size_t MP_WORD_BITS