/src/dropbear/libtommath/bn_mp_div_3.c
Line | Count | Source |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_MP_DIV_3_C |
3 | | /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 | | /* SPDX-License-Identifier: Unlicense */ |
5 | | |
6 | | /* divide by three (based on routine from MPI and the GMP manual) */ |
7 | | mp_err mp_div_3(const mp_int *a, mp_int *c, mp_digit *d) |
8 | 141 | { |
9 | 141 | mp_int q; |
10 | 141 | mp_word w, t; |
11 | 141 | mp_digit b; |
12 | 141 | mp_err err; |
13 | 141 | int ix; |
14 | | |
15 | | /* b = 2**MP_DIGIT_BIT / 3 */ |
16 | 141 | b = ((mp_word)1 << (mp_word)MP_DIGIT_BIT) / (mp_word)3; |
17 | | |
18 | 141 | if ((err = mp_init_size(&q, a->used)) != MP_OKAY) { |
19 | 0 | return err; |
20 | 0 | } |
21 | | |
22 | 141 | q.used = a->used; |
23 | 141 | q.sign = a->sign; |
24 | 141 | w = 0; |
25 | 1.02k | for (ix = a->used - 1; ix >= 0; ix--) { |
26 | 888 | w = (w << (mp_word)MP_DIGIT_BIT) | (mp_word)a->dp[ix]; |
27 | | |
28 | 888 | if (w >= 3u) { |
29 | | /* multiply w by [1/3] */ |
30 | 789 | t = (w * (mp_word)b) >> (mp_word)MP_DIGIT_BIT; |
31 | | |
32 | | /* now subtract 3 * [w/3] from w, to get the remainder */ |
33 | 789 | w -= t+t+t; |
34 | | |
35 | | /* fixup the remainder as required since |
36 | | * the optimization is not exact. |
37 | | */ |
38 | 1.25k | while (w >= 3u) { |
39 | 463 | t += 1u; |
40 | 463 | w -= 3u; |
41 | 463 | } |
42 | 789 | } else { |
43 | 99 | t = 0; |
44 | 99 | } |
45 | 888 | q.dp[ix] = (mp_digit)t; |
46 | 888 | } |
47 | | |
48 | | /* [optional] store the remainder */ |
49 | 141 | if (d != NULL) { |
50 | 141 | *d = (mp_digit)w; |
51 | 141 | } |
52 | | |
53 | | /* [optional] store the quotient */ |
54 | 141 | if (c != NULL) { |
55 | 0 | mp_clamp(&q); |
56 | 0 | mp_exch(&q, c); |
57 | 0 | } |
58 | 141 | mp_clear(&q); |
59 | | |
60 | 141 | return err; |
61 | 141 | } |
62 | | |
63 | | #endif |