/src/dropbear/libtommath/bn_mp_mul.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_MP_MUL_C |
3 | | /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 | | /* SPDX-License-Identifier: Unlicense */ |
5 | | |
6 | | /* high level multiplication (handles sign) */ |
7 | | mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c) |
8 | 1 | { |
9 | 1 | mp_err err; |
10 | 1 | int min_len = MP_MIN(a->used, b->used), |
11 | 1 | max_len = MP_MAX(a->used, b->used), |
12 | 1 | digs = a->used + b->used + 1; |
13 | 1 | mp_sign neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG; |
14 | | |
15 | 1 | if (MP_HAS(S_MP_BALANCE_MUL) && |
16 | | /* Check sizes. The smaller one needs to be larger than the Karatsuba cut-off. |
17 | | * The bigger one needs to be at least about one MP_KARATSUBA_MUL_CUTOFF bigger |
18 | | * to make some sense, but it depends on architecture, OS, position of the |
19 | | * stars... so YMMV. |
20 | | * Using it to cut the input into slices small enough for fast_s_mp_mul_digs |
21 | | * was actually slower on the author's machine, but YMMV. |
22 | | */ |
23 | 1 | (min_len >= MP_KARATSUBA_MUL_CUTOFF) && |
24 | 1 | ((max_len / 2) >= MP_KARATSUBA_MUL_CUTOFF) && |
25 | | /* Not much effect was observed below a ratio of 1:2, but again: YMMV. */ |
26 | 1 | (max_len >= (2 * min_len))) { |
27 | 0 | err = s_mp_balance_mul(a,b,c); |
28 | 1 | } else if (MP_HAS(S_MP_TOOM_MUL) && |
29 | 1 | (min_len >= MP_TOOM_MUL_CUTOFF)) { |
30 | 0 | err = s_mp_toom_mul(a, b, c); |
31 | 1 | } else if (MP_HAS(S_MP_KARATSUBA_MUL) && |
32 | 1 | (min_len >= MP_KARATSUBA_MUL_CUTOFF)) { |
33 | 0 | err = s_mp_karatsuba_mul(a, b, c); |
34 | 1 | } else if (MP_HAS(S_MP_MUL_DIGS_FAST) && |
35 | | /* can we use the fast multiplier? |
36 | | * |
37 | | * The fast multiplier can be used if the output will |
38 | | * have less than MP_WARRAY digits and the number of |
39 | | * digits won't affect carry propagation |
40 | | */ |
41 | 1 | (digs < MP_WARRAY) && |
42 | 1 | (min_len <= MP_MAXFAST)) { |
43 | 1 | err = s_mp_mul_digs_fast(a, b, c, digs); |
44 | 1 | } else if (MP_HAS(S_MP_MUL_DIGS)) { |
45 | 0 | err = s_mp_mul_digs(a, b, c, digs); |
46 | 0 | } else { |
47 | 0 | err = MP_VAL; |
48 | 0 | } |
49 | 1 | c->sign = (c->used > 0) ? neg : MP_ZPOS; |
50 | 1 | return err; |
51 | 1 | } |
52 | | #endif |