9#include <botan/internal/mp_core.h>
10#include <botan/internal/mp_asmi.h>
11#include <botan/internal/ct_utils.h>
12#include <botan/mem_ops.h>
13#include <botan/exceptn.h>
19const size_t KARATSUBA_MULTIPLY_THRESHOLD = 32;
20const size_t KARATSUBA_SQUARE_THRESHOLD = 32;
25void basecase_mul(word z[],
size_t z_size,
26 const word x[],
size_t x_size,
27 const word y[],
size_t y_size)
29 if(z_size < x_size + y_size)
30 throw Invalid_Argument(
"basecase_mul z_size too small");
32 const size_t x_size_8 = x_size - (x_size % 8);
36 for(
size_t i = 0; i != y_size; ++i)
38 const word y_i = y[i];
42 for(
size_t j = 0; j != x_size_8; j += 8)
45 for(
size_t j = x_size_8; j != x_size; ++j)
52void basecase_sqr(word z[],
size_t z_size,
53 const word x[],
size_t x_size)
56 throw Invalid_Argument(
"basecase_sqr z_size too small");
58 const size_t x_size_8 = x_size - (x_size % 8);
62 for(
size_t i = 0; i != x_size; ++i)
64 const word x_i = x[i];
68 for(
size_t j = 0; j != x_size_8; j += 8)
71 for(
size_t j = x_size_8; j != x_size; ++j)
81void karatsuba_mul(word z[],
const word x[],
const word y[],
size_t N,
84 if(N < KARATSUBA_MULTIPLY_THRESHOLD || N % 2)
99 return basecase_mul(z, 2*N, x, N, y, N);
103 const size_t N2 = N / 2;
106 const word* x1 = x + N2;
108 const word* y1 = y + N2;
112 word* ws0 = workspace;
113 word* ws1 = workspace + N;
129 const auto neg_mask = ~(cmp0 ^ cmp1);
131 karatsuba_mul(ws0, z0, z1, N2, ws1);
134 karatsuba_mul(z0, x0, y0, N2, ws1);
137 karatsuba_mul(z1, x1, y1, N2, ws1);
153void karatsuba_sqr(word z[],
const word x[],
size_t N, word workspace[])
155 if(N < KARATSUBA_SQUARE_THRESHOLD || N % 2)
170 return basecase_sqr(z, 2*N, x, N);
174 const size_t N2 = N / 2;
177 const word* x1 = x + N2;
181 word* ws0 = workspace;
182 word* ws1 = workspace + N;
188 karatsuba_sqr(ws0, z0, N2, ws1);
190 karatsuba_sqr(z0, x0, N2, ws1);
191 karatsuba_sqr(z1, x1, N2, ws1);
210size_t karatsuba_size(
size_t z_size,
211 size_t x_size,
size_t x_sw,
212 size_t y_size,
size_t y_sw)
214 if(x_sw > x_size || x_sw > y_size || y_sw > x_size || y_sw > y_size)
217 if(((x_size == x_sw) && (x_size % 2)) ||
218 ((y_size == y_sw) && (y_size % 2)))
221 const size_t start = (x_sw > y_sw) ? x_sw : y_sw;
222 const size_t end = (x_size < y_size) ? x_size : y_size;
231 for(
size_t j = start; j <= end; ++j)
239 if(x_sw <= j && j <= x_size && y_sw <= j && j <= y_size)
242 (j+2) <= x_size && (j+2) <= y_size && 2*(j+2) <= z_size)
254size_t karatsuba_size(
size_t z_size,
size_t x_size,
size_t x_sw)
263 for(
size_t j = x_sw; j <= x_size; ++j)
271 if(j % 4 == 2 && (j+2) <= x_size && 2*(j+2) <= z_size)
280inline bool sized_for_comba_mul(
size_t x_sw,
size_t x_size,
281 size_t y_sw,
size_t y_size,
284 return (x_sw <= SZ && x_size >= SZ &&
285 y_sw <= SZ && y_size >= SZ &&
290inline bool sized_for_comba_sqr(
size_t x_sw,
size_t x_size,
293 return (x_sw <= SZ && x_size >= SZ && z_size >= 2*SZ);
299 const word x[],
size_t x_size,
size_t x_sw,
300 const word y[],
size_t y_size,
size_t y_sw,
301 word workspace[],
size_t ws_size)
313 else if(sized_for_comba_mul<4>(x_sw, x_size, y_sw, y_size, z_size))
317 else if(sized_for_comba_mul<6>(x_sw, x_size, y_sw, y_size, z_size))
321 else if(sized_for_comba_mul<8>(x_sw, x_size, y_sw, y_size, z_size))
325 else if(sized_for_comba_mul<9>(x_sw, x_size, y_sw, y_size, z_size))
329 else if(sized_for_comba_mul<16>(x_sw, x_size, y_sw, y_size, z_size))
333 else if(sized_for_comba_mul<24>(x_sw, x_size, y_sw, y_size, z_size))
337 else if(x_sw < KARATSUBA_MULTIPLY_THRESHOLD ||
338 y_sw < KARATSUBA_MULTIPLY_THRESHOLD ||
341 basecase_mul(z, z_size, x, x_sw, y, y_sw);
345 const size_t N = karatsuba_size(z_size, x_size, x_sw, y_size, y_sw);
347 if(N && z_size >= 2*N && ws_size >= 2*N)
348 karatsuba_mul(z, x, y, N, workspace);
350 basecase_mul(z, z_size, x, x_sw, y, y_sw);
358 const word x[],
size_t x_size,
size_t x_sw,
359 word workspace[],
size_t ws_size)
363 BOTAN_ASSERT(z_size/2 >= x_sw,
"Output size is sufficient");
369 else if(sized_for_comba_sqr<4>(x_sw, x_size, z_size))
373 else if(sized_for_comba_sqr<6>(x_sw, x_size, z_size))
377 else if(sized_for_comba_sqr<8>(x_sw, x_size, z_size))
381 else if(sized_for_comba_sqr<9>(x_sw, x_size, z_size))
385 else if(sized_for_comba_sqr<16>(x_sw, x_size, z_size))
389 else if(sized_for_comba_sqr<24>(x_sw, x_size, z_size))
393 else if(x_size < KARATSUBA_SQUARE_THRESHOLD || !workspace)
395 basecase_sqr(z, z_size, x, x_sw);
399 const size_t N = karatsuba_size(z_size, x_size, x_sw);
401 if(N && z_size >= 2*N && ws_size >= 2*N)
402 karatsuba_sqr(z, x, N, workspace);
404 basecase_sqr(z, z_size, x, x_sw);
#define BOTAN_ASSERT(expr, assertion_made)
word word8_madd3(word z[8], const word x[8], word y, word carry)
void bigint_linmul3(word z[], const 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])
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)
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_comba_mul8(word z[16], const word x[8], const word y[8])
void bigint_comba_sqr4(word z[8], const word x[4])
void carry(int64_t &h0, int64_t &h1)
word word_madd3(word a, word b, word c, word *d)
void bigint_comba_sqr9(word z[18], const word x[9])
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])
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)
word bigint_add3_nc(word z[], 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)
void bigint_comba_sqr8(word z[16], const word x[8])