/src/dropbear/libtommath/bn_mp_div_d.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_MP_DIV_D_C |
3 | | /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 | | /* SPDX-License-Identifier: Unlicense */ |
5 | | |
6 | | /* single digit division (based on routine from MPI) */ |
7 | | mp_err mp_div_d(const mp_int *a, mp_digit b, mp_int *c, mp_digit *d) |
8 | 25.3k | { |
9 | 25.3k | mp_int q; |
10 | 25.3k | mp_word w; |
11 | 25.3k | mp_digit t; |
12 | 25.3k | mp_err err; |
13 | 25.3k | int ix; |
14 | | |
15 | | /* cannot divide by zero */ |
16 | 25.3k | if (b == 0u) { |
17 | 0 | return MP_VAL; |
18 | 0 | } |
19 | | |
20 | | /* quick outs */ |
21 | 25.3k | if ((b == 1u) || MP_IS_ZERO(a)) { |
22 | 0 | if (d != NULL) { |
23 | 0 | *d = 0; |
24 | 0 | } |
25 | 0 | if (c != NULL) { |
26 | 0 | return mp_copy(a, c); |
27 | 0 | } |
28 | 0 | return MP_OKAY; |
29 | 0 | } |
30 | | |
31 | | /* power of two ? */ |
32 | 25.3k | if ((b & (b - 1u)) == 0u) { |
33 | 135 | ix = 1; |
34 | 135 | while ((ix < MP_DIGIT_BIT) && (b != (((mp_digit)1)<<ix))) { |
35 | 0 | ix++; |
36 | 0 | } |
37 | 135 | if (d != NULL) { |
38 | 135 | *d = a->dp[0] & (((mp_digit)1<<(mp_digit)ix) - 1uL); |
39 | 135 | } |
40 | 135 | if (c != NULL) { |
41 | 0 | return mp_div_2d(a, ix, c, NULL); |
42 | 0 | } |
43 | 135 | return MP_OKAY; |
44 | 135 | } |
45 | | |
46 | | /* three? */ |
47 | 25.2k | if (MP_HAS(MP_DIV_3) && (b == 3u)) { |
48 | 135 | return mp_div_3(a, c, d); |
49 | 135 | } |
50 | | |
51 | | /* no easy answer [c'est la vie]. Just division */ |
52 | 25.0k | if ((err = mp_init_size(&q, a->used)) != MP_OKAY) { |
53 | 0 | return err; |
54 | 0 | } |
55 | | |
56 | 25.0k | q.used = a->used; |
57 | 25.0k | q.sign = a->sign; |
58 | 25.0k | w = 0; |
59 | 103k | for (ix = a->used - 1; ix >= 0; ix--) { |
60 | 78.6k | w = (w << (mp_word)MP_DIGIT_BIT) | (mp_word)a->dp[ix]; |
61 | | |
62 | 78.6k | if (w >= b) { |
63 | 78.2k | t = (mp_digit)(w / b); |
64 | 78.2k | w -= (mp_word)t * (mp_word)b; |
65 | 78.2k | } else { |
66 | 378 | t = 0; |
67 | 378 | } |
68 | 78.6k | q.dp[ix] = t; |
69 | 78.6k | } |
70 | | |
71 | 25.0k | if (d != NULL) { |
72 | 25.0k | *d = (mp_digit)w; |
73 | 25.0k | } |
74 | | |
75 | 25.0k | if (c != NULL) { |
76 | 0 | mp_clamp(&q); |
77 | 0 | mp_exch(&q, c); |
78 | 0 | } |
79 | 25.0k | mp_clear(&q); |
80 | | |
81 | 25.0k | return err; |
82 | 25.0k | } |
83 | | |
84 | | #endif |