Mercurial > dropbear
comparison libtommath/bn_mp_gcd.c @ 1692:1051e4eea25a
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_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 * SPDX-License-Identifier: Unlicense | |
13 */ | |
14 | 5 |
15 /* Greatest Common Divisor using the binary method */ | 6 /* Greatest Common Divisor using the binary method */ |
16 int mp_gcd(const mp_int *a, const mp_int *b, mp_int *c) | 7 mp_err mp_gcd(const mp_int *a, const mp_int *b, mp_int *c) |
17 { | 8 { |
18 mp_int u, v; | 9 mp_int u, v; |
19 int k, u_lsb, v_lsb, res; | 10 int k, u_lsb, v_lsb; |
11 mp_err err; | |
20 | 12 |
21 /* either zero than gcd is the largest */ | 13 /* either zero than gcd is the largest */ |
22 if (mp_iszero(a) == MP_YES) { | 14 if (MP_IS_ZERO(a)) { |
23 return mp_abs(b, c); | 15 return mp_abs(b, c); |
24 } | 16 } |
25 if (mp_iszero(b) == MP_YES) { | 17 if (MP_IS_ZERO(b)) { |
26 return mp_abs(a, c); | 18 return mp_abs(a, c); |
27 } | 19 } |
28 | 20 |
29 /* get copies of a and b we can modify */ | 21 /* get copies of a and b we can modify */ |
30 if ((res = mp_init_copy(&u, a)) != MP_OKAY) { | 22 if ((err = mp_init_copy(&u, a)) != MP_OKAY) { |
31 return res; | 23 return err; |
32 } | 24 } |
33 | 25 |
34 if ((res = mp_init_copy(&v, b)) != MP_OKAY) { | 26 if ((err = mp_init_copy(&v, b)) != MP_OKAY) { |
35 goto LBL_U; | 27 goto LBL_U; |
36 } | 28 } |
37 | 29 |
38 /* must be positive for the remainder of the algorithm */ | 30 /* must be positive for the remainder of the algorithm */ |
39 u.sign = v.sign = MP_ZPOS; | 31 u.sign = v.sign = MP_ZPOS; |
40 | 32 |
41 /* B1. Find the common power of two for u and v */ | 33 /* B1. Find the common power of two for u and v */ |
42 u_lsb = mp_cnt_lsb(&u); | 34 u_lsb = mp_cnt_lsb(&u); |
43 v_lsb = mp_cnt_lsb(&v); | 35 v_lsb = mp_cnt_lsb(&v); |
44 k = MIN(u_lsb, v_lsb); | 36 k = MP_MIN(u_lsb, v_lsb); |
45 | 37 |
46 if (k > 0) { | 38 if (k > 0) { |
47 /* divide the power of two out */ | 39 /* divide the power of two out */ |
48 if ((res = mp_div_2d(&u, k, &u, NULL)) != MP_OKAY) { | 40 if ((err = mp_div_2d(&u, k, &u, NULL)) != MP_OKAY) { |
49 goto LBL_V; | 41 goto LBL_V; |
50 } | 42 } |
51 | 43 |
52 if ((res = mp_div_2d(&v, k, &v, NULL)) != MP_OKAY) { | 44 if ((err = mp_div_2d(&v, k, &v, NULL)) != MP_OKAY) { |
53 goto LBL_V; | 45 goto LBL_V; |
54 } | 46 } |
55 } | 47 } |
56 | 48 |
57 /* divide any remaining factors of two out */ | 49 /* divide any remaining factors of two out */ |
58 if (u_lsb != k) { | 50 if (u_lsb != k) { |
59 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) { |
60 goto LBL_V; | 52 goto LBL_V; |
61 } | 53 } |
62 } | 54 } |
63 | 55 |
64 if (v_lsb != k) { | 56 if (v_lsb != k) { |
65 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) { |
66 goto LBL_V; | 58 goto LBL_V; |
67 } | 59 } |
68 } | 60 } |
69 | 61 |
70 while (mp_iszero(&v) == MP_NO) { | 62 while (!MP_IS_ZERO(&v)) { |
71 /* make sure v is the largest */ | 63 /* make sure v is the largest */ |
72 if (mp_cmp_mag(&u, &v) == MP_GT) { | 64 if (mp_cmp_mag(&u, &v) == MP_GT) { |
73 /* swap u and v to make sure v is >= u */ | 65 /* swap u and v to make sure v is >= u */ |
74 mp_exch(&u, &v); | 66 mp_exch(&u, &v); |
75 } | 67 } |
76 | 68 |
77 /* subtract smallest from largest */ | 69 /* subtract smallest from largest */ |
78 if ((res = s_mp_sub(&v, &u, &v)) != MP_OKAY) { | 70 if ((err = s_mp_sub(&v, &u, &v)) != MP_OKAY) { |
79 goto LBL_V; | 71 goto LBL_V; |
80 } | 72 } |
81 | 73 |
82 /* Divide out all factors of two */ | 74 /* Divide out all factors of two */ |
83 if ((res = mp_div_2d(&v, mp_cnt_lsb(&v), &v, NULL)) != MP_OKAY) { | 75 if ((err = mp_div_2d(&v, mp_cnt_lsb(&v), &v, NULL)) != MP_OKAY) { |
84 goto LBL_V; | 76 goto LBL_V; |
85 } | 77 } |
86 } | 78 } |
87 | 79 |
88 /* multiply by 2**k which we divided out at the beginning */ | 80 /* multiply by 2**k which we divided out at the beginning */ |
89 if ((res = mp_mul_2d(&u, k, c)) != MP_OKAY) { | 81 if ((err = mp_mul_2d(&u, k, c)) != MP_OKAY) { |
90 goto LBL_V; | 82 goto LBL_V; |
91 } | 83 } |
92 c->sign = MP_ZPOS; | 84 c->sign = MP_ZPOS; |
93 res = MP_OKAY; | 85 err = MP_OKAY; |
94 LBL_V: | 86 LBL_V: |
95 mp_clear(&u); | 87 mp_clear(&u); |
96 LBL_U: | 88 LBL_U: |
97 mp_clear(&v); | 89 mp_clear(&v); |
98 return res; | 90 return err; |
99 } | 91 } |
100 #endif | 92 #endif |
101 | |
102 /* ref: HEAD -> master, tag: v1.1.0 */ | |
103 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */ | |
104 /* commit time: 2019-01-28 20:32:32 +0100 */ |