Mercurial > dropbear

comparison libtommath/bn_mp_mul.c @ 1739:13d834efc376 fuzz

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge from main
author Matt Johnston <matt@ucc.asn.au>
date Thu, 15 Oct 2020 19:55:15 +0800
parents 1051e4eea25a
children
comparison
equal deleted inserted replaced
1562:768ebf737aa0 1739:13d834efc376
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 * The library is free for all purposes without any express
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */
17 5
18 /* high level multiplication (handles sign) */ 6 /* high level multiplication (handles sign) */
19 int mp_mul (mp_int * a, mp_int * b, mp_int * c) 7 mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
20 { 8 {
21 int res, neg; 9 mp_err err;
22 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;
23 14
24 /* use Toom-Cook? */ 15 if (MP_HAS(S_MP_BALANCE_MUL) &&
25 #ifdef BN_MP_TOOM_MUL_C 16 /* Check sizes. The smaller one needs to be larger than the Karatsuba cut-off.
26 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
27 res = mp_toom_mul(a, b, c); 18 * to make some sense, but it depends on architecture, OS, position of the
28 } else 19 * stars... so YMMV.
29 #endif 20 * Using it to cut the input into slices small enough for fast_s_mp_mul_digs
30 #ifdef BN_MP_KARATSUBA_MUL_C 21 * was actually slower on the author's machine, but YMMV.
31 /* use Karatsuba? */ 22 */
32 if (MIN (a->used, b->used) >= KARATSUBA_MUL_CUTOFF) { 23 (min_len >= MP_KARATSUBA_MUL_CUTOFF) &&
33 res = mp_karatsuba_mul (a, b, c); 24 ((max_len / 2) >= MP_KARATSUBA_MUL_CUTOFF) &&
34 } else 25 /* Not much effect was observed below a ratio of 1:2, but again: YMMV. */
35 #endif 26 (max_len >= (2 * min_len))) {
36 { 27 err = s_mp_balance_mul(a,b,c);
37 /* can we use the fast multiplier? 28 } else if (MP_HAS(S_MP_TOOM_MUL) &&
38 * 29 (min_len >= MP_TOOM_MUL_CUTOFF)) {
39 * The fast multiplier can be used if the output will 30 err = s_mp_toom_mul(a, b, c);
40 * have less than MP_WARRAY digits and the number of 31 } else if (MP_HAS(S_MP_KARATSUBA_MUL) &&
41 * digits won't affect carry propagation 32 (min_len >= MP_KARATSUBA_MUL_CUTOFF)) {
42 */ 33 err = s_mp_karatsuba_mul(a, b, c);
43 int digs = a->used + b->used + 1; 34 } else if (MP_HAS(S_MP_MUL_DIGS_FAST) &&
44 35 /* can we use the fast multiplier?
45 #ifdef BN_FAST_S_MP_MUL_DIGS_C 36 *
46 if ((digs < MP_WARRAY) && 37 * The fast multiplier can be used if the output will
47 (MIN(a->used, b->used) <= 38 * have less than MP_WARRAY digits and the number of
48 (1 << ((CHAR_BIT * sizeof(mp_word)) - (2 * DIGIT_BIT))))) { 39 * digits won't affect carry propagation
49 res = fast_s_mp_mul_digs (a, b, c, digs); 40 */
50 } else 41 (digs < MP_WARRAY) &&
51 #endif 42 (min_len <= MP_MAXFAST)) {
52 { 43 err = s_mp_mul_digs_fast(a, b, c, digs);
53 #ifdef BN_S_MP_MUL_DIGS_C 44 } else if (MP_HAS(S_MP_MUL_DIGS)) {
54 res = s_mp_mul (a, b, c); /* uses s_mp_mul_digs */ 45 err = s_mp_mul_digs(a, b, c, digs);
55 #else 46 } else {
56 res = MP_VAL; 47 err = MP_VAL;
57 #endif 48 }
58 } 49 c->sign = (c->used > 0) ? neg : MP_ZPOS;
59 } 50 return err;
60 c->sign = (c->used > 0) ? neg : MP_ZPOS;
61 return res;
62 } 51 }
63 #endif 52 #endif
64
65 /* ref: $Format:%D$ */
66 /* git commit: $Format:%H$ */
67 /* commit time: $Format:%ai$ */