Mercurial > dropbear

comparison libtommath/bn_mp_mul.c @ 1692:1051e4eea25a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update LibTomMath to 1.2.0 (#84) * update C files * update other files * update headers * update makefiles * remove mp_set/get_double() * use ltm 1.2.0 API * update ltm_desc * use bundled tommath if system-tommath is too old * XMALLOC etc. were changed to MP_MALLOC etc.
author Steffen Jaeckel <s@jaeckel.eu>
date Tue, 26 May 2020 17:36:47 +0200
parents f52919ffd3b1
children
comparison
equal deleted inserted replaced
1691:2d3745d58843 1692:1051e4eea25a
1 #include "tommath_private.h" 1 #include "tommath_private.h"
2 #ifdef BN_MP_MUL_C 2 #ifdef BN_MP_MUL_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
4 * 4 /* SPDX-License-Identifier: Unlicense */
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
7 *
8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place.
11 *
12 * SPDX-License-Identifier: Unlicense
13 */
14 5
15 /* high level multiplication (handles sign) */ 6 /* high level multiplication (handles sign) */
16 int mp_mul(const mp_int *a, const mp_int *b, mp_int *c) 7 mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
17 { 8 {
18 int res, neg; 9 mp_err err;
19 neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG; 10 int min_len = MP_MIN(a->used, b->used),
11 max_len = MP_MAX(a->used, b->used),
12 digs = a->used + b->used + 1;
13 mp_sign neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG;
20 14
21 /* use Toom-Cook? */ 15 if (MP_HAS(S_MP_BALANCE_MUL) &&
22 #ifdef BN_MP_TOOM_MUL_C 16 /* Check sizes. The smaller one needs to be larger than the Karatsuba cut-off.
23 if (MIN(a->used, b->used) >= TOOM_MUL_CUTOFF) { 17 * The bigger one needs to be at least about one MP_KARATSUBA_MUL_CUTOFF bigger
24 res = mp_toom_mul(a, b, c); 18 * to make some sense, but it depends on architecture, OS, position of the
25 } else 19 * stars... so YMMV.
26 #endif 20 * Using it to cut the input into slices small enough for fast_s_mp_mul_digs
27 #ifdef BN_MP_KARATSUBA_MUL_C 21 * was actually slower on the author's machine, but YMMV.
28 /* use Karatsuba? */ 22 */
29 if (MIN(a->used, b->used) >= KARATSUBA_MUL_CUTOFF) { 23 (min_len >= MP_KARATSUBA_MUL_CUTOFF) &&
30 res = mp_karatsuba_mul(a, b, c); 24 ((max_len / 2) >= MP_KARATSUBA_MUL_CUTOFF) &&
31 } else 25 /* Not much effect was observed below a ratio of 1:2, but again: YMMV. */
32 #endif 26 (max_len >= (2 * min_len))) {
33 { 27 err = s_mp_balance_mul(a,b,c);
34 /* can we use the fast multiplier? 28 } else if (MP_HAS(S_MP_TOOM_MUL) &&
35 * 29 (min_len >= MP_TOOM_MUL_CUTOFF)) {
36 * The fast multiplier can be used if the output will 30 err = s_mp_toom_mul(a, b, c);
37 * have less than MP_WARRAY digits and the number of 31 } else if (MP_HAS(S_MP_KARATSUBA_MUL) &&
38 * digits won't affect carry propagation 32 (min_len >= MP_KARATSUBA_MUL_CUTOFF)) {
39 */ 33 err = s_mp_karatsuba_mul(a, b, c);
40 int digs = a->used + b->used + 1; 34 } else if (MP_HAS(S_MP_MUL_DIGS_FAST) &&
41 35 /* can we use the fast multiplier?
42 #ifdef BN_FAST_S_MP_MUL_DIGS_C 36 *
43 if ((digs < (int)MP_WARRAY) && 37 * The fast multiplier can be used if the output will
44 (MIN(a->used, b->used) <= 38 * have less than MP_WARRAY digits and the number of
45 (int)(1u << (((size_t)CHAR_BIT * sizeof(mp_word)) - (2u * (size_t)DIGIT_BIT))))) { 39 * digits won't affect carry propagation
46 res = fast_s_mp_mul_digs(a, b, c, digs); 40 */
47 } else 41 (digs < MP_WARRAY) &&
48 #endif 42 (min_len <= MP_MAXFAST)) {
49 { 43 err = s_mp_mul_digs_fast(a, b, c, digs);
50 #ifdef BN_S_MP_MUL_DIGS_C 44 } else if (MP_HAS(S_MP_MUL_DIGS)) {
51 res = s_mp_mul(a, b, c); /* uses s_mp_mul_digs */ 45 err = s_mp_mul_digs(a, b, c, digs);
52 #else 46 } else {
53 res = MP_VAL; 47 err = MP_VAL;
54 #endif 48 }
55 }
56 }
57 c->sign = (c->used > 0) ? neg : MP_ZPOS; 49 c->sign = (c->used > 0) ? neg : MP_ZPOS;
58 return res; 50 return err;
59 } 51 }
60 #endif 52 #endif
61
62 /* ref: HEAD -> master, tag: v1.1.0 */
63 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
64 /* commit time: 2019-01-28 20:32:32 +0100 */