Mercurial > dropbear
comparison libtommath/bn_mp_gcd.c @ 1733:d529a52b2f7c coverity coverity
merge coverity from main
author | Matt Johnston <matt@ucc.asn.au> |
---|---|
date | Fri, 26 Jun 2020 21:07:34 +0800 |
parents | 1051e4eea25a |
children |
comparison
equal
deleted
inserted
replaced
1643:b59623a64678 | 1733:d529a52b2f7c |
---|---|
1 #include <tommath_private.h> | 1 #include "tommath_private.h" |
2 #ifdef BN_MP_GCD_C | 2 #ifdef BN_MP_GCD_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 /* Greatest Common Divisor using the binary method */ | 6 /* Greatest Common Divisor using the binary method */ |
19 int mp_gcd (mp_int * a, mp_int * b, mp_int * c) | 7 mp_err mp_gcd(const mp_int *a, const mp_int *b, mp_int *c) |
20 { | 8 { |
21 mp_int u, v; | 9 mp_int u, v; |
22 int k, u_lsb, v_lsb, res; | 10 int k, u_lsb, v_lsb; |
11 mp_err err; | |
23 | 12 |
24 /* either zero than gcd is the largest */ | 13 /* either zero than gcd is the largest */ |
25 if (mp_iszero (a) == MP_YES) { | 14 if (MP_IS_ZERO(a)) { |
26 return mp_abs (b, c); | 15 return mp_abs(b, c); |
27 } | 16 } |
28 if (mp_iszero (b) == MP_YES) { | 17 if (MP_IS_ZERO(b)) { |
29 return mp_abs (a, c); | 18 return mp_abs(a, c); |
30 } | 19 } |
31 | 20 |
32 /* get copies of a and b we can modify */ | 21 /* get copies of a and b we can modify */ |
33 if ((res = mp_init_copy (&u, a)) != MP_OKAY) { | 22 if ((err = mp_init_copy(&u, a)) != MP_OKAY) { |
34 return res; | 23 return err; |
35 } | 24 } |
36 | 25 |
37 if ((res = mp_init_copy (&v, b)) != MP_OKAY) { | 26 if ((err = mp_init_copy(&v, b)) != MP_OKAY) { |
38 goto LBL_U; | 27 goto LBL_U; |
39 } | 28 } |
40 | 29 |
41 /* must be positive for the remainder of the algorithm */ | 30 /* must be positive for the remainder of the algorithm */ |
42 u.sign = v.sign = MP_ZPOS; | 31 u.sign = v.sign = MP_ZPOS; |
43 | 32 |
44 /* B1. Find the common power of two for u and v */ | 33 /* B1. Find the common power of two for u and v */ |
45 u_lsb = mp_cnt_lsb(&u); | 34 u_lsb = mp_cnt_lsb(&u); |
46 v_lsb = mp_cnt_lsb(&v); | 35 v_lsb = mp_cnt_lsb(&v); |
47 k = MIN(u_lsb, v_lsb); | 36 k = MP_MIN(u_lsb, v_lsb); |
48 | 37 |
49 if (k > 0) { | 38 if (k > 0) { |
50 /* divide the power of two out */ | 39 /* divide the power of two out */ |
51 if ((res = mp_div_2d(&u, k, &u, NULL)) != MP_OKAY) { | 40 if ((err = mp_div_2d(&u, k, &u, NULL)) != MP_OKAY) { |
52 goto LBL_V; | 41 goto LBL_V; |
53 } | 42 } |
54 | 43 |
55 if ((res = mp_div_2d(&v, k, &v, NULL)) != MP_OKAY) { | 44 if ((err = mp_div_2d(&v, k, &v, NULL)) != MP_OKAY) { |
56 goto LBL_V; | 45 goto LBL_V; |
57 } | 46 } |
58 } | 47 } |
59 | 48 |
60 /* divide any remaining factors of two out */ | 49 /* divide any remaining factors of two out */ |
61 if (u_lsb != k) { | 50 if (u_lsb != k) { |
62 if ((res = mp_div_2d(&u, u_lsb - k, &u, NULL)) != MP_OKAY) { | 51 if ((err = mp_div_2d(&u, u_lsb - k, &u, NULL)) != MP_OKAY) { |
63 goto LBL_V; | 52 goto LBL_V; |
64 } | 53 } |
65 } | 54 } |
66 | 55 |
67 if (v_lsb != k) { | 56 if (v_lsb != k) { |
68 if ((res = mp_div_2d(&v, v_lsb - k, &v, NULL)) != MP_OKAY) { | 57 if ((err = mp_div_2d(&v, v_lsb - k, &v, NULL)) != MP_OKAY) { |
69 goto LBL_V; | 58 goto LBL_V; |
70 } | 59 } |
71 } | 60 } |
72 | 61 |
73 while (mp_iszero(&v) == MP_NO) { | 62 while (!MP_IS_ZERO(&v)) { |
74 /* make sure v is the largest */ | 63 /* make sure v is the largest */ |
75 if (mp_cmp_mag(&u, &v) == MP_GT) { | 64 if (mp_cmp_mag(&u, &v) == MP_GT) { |
76 /* swap u and v to make sure v is >= u */ | 65 /* swap u and v to make sure v is >= u */ |
77 mp_exch(&u, &v); | 66 mp_exch(&u, &v); |
78 } | 67 } |
79 | |
80 /* subtract smallest from largest */ | |
81 if ((res = s_mp_sub(&v, &u, &v)) != MP_OKAY) { | |
82 goto LBL_V; | |
83 } | |
84 | |
85 /* Divide out all factors of two */ | |
86 if ((res = mp_div_2d(&v, mp_cnt_lsb(&v), &v, NULL)) != MP_OKAY) { | |
87 goto LBL_V; | |
88 } | |
89 } | |
90 | 68 |
91 /* multiply by 2**k which we divided out at the beginning */ | 69 /* subtract smallest from largest */ |
92 if ((res = mp_mul_2d (&u, k, c)) != MP_OKAY) { | 70 if ((err = s_mp_sub(&v, &u, &v)) != MP_OKAY) { |
93 goto LBL_V; | 71 goto LBL_V; |
94 } | 72 } |
95 c->sign = MP_ZPOS; | 73 |
96 res = MP_OKAY; | 74 /* Divide out all factors of two */ |
97 LBL_V:mp_clear (&u); | 75 if ((err = mp_div_2d(&v, mp_cnt_lsb(&v), &v, NULL)) != MP_OKAY) { |
98 LBL_U:mp_clear (&v); | 76 goto LBL_V; |
99 return res; | 77 } |
78 } | |
79 | |
80 /* multiply by 2**k which we divided out at the beginning */ | |
81 if ((err = mp_mul_2d(&u, k, c)) != MP_OKAY) { | |
82 goto LBL_V; | |
83 } | |
84 c->sign = MP_ZPOS; | |
85 err = MP_OKAY; | |
86 LBL_V: | |
87 mp_clear(&u); | |
88 LBL_U: | |
89 mp_clear(&v); | |
90 return err; | |
100 } | 91 } |
101 #endif | 92 #endif |
102 | |
103 /* ref: $Format:%D$ */ | |
104 /* git commit: $Format:%H$ */ | |
105 /* commit time: $Format:%ai$ */ |