/src/dropbear/libtommath/bn_mp_div_d.c
Line | Count | Source |
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 | 0 | { |
9 | 0 | mp_int q; |
10 | 0 | mp_word w; |
11 | 0 | mp_digit t; |
12 | 0 | mp_err err; |
13 | 0 | int ix; |
14 | | |
15 | | /* cannot divide by zero */ |
16 | 0 | if (b == 0u) { |
17 | 0 | return MP_VAL; |
18 | 0 | } |
19 | | |
20 | | /* quick outs */ |
21 | 0 | 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 | 0 | if ((b & (b - 1u)) == 0u) { |
33 | 0 | ix = 1; |
34 | 0 | while ((ix < MP_DIGIT_BIT) && (b != (((mp_digit)1)<<ix))) { |
35 | 0 | ix++; |
36 | 0 | } |
37 | 0 | if (d != NULL) { |
38 | 0 | *d = a->dp[0] & (((mp_digit)1<<(mp_digit)ix) - 1uL); |
39 | 0 | } |
40 | 0 | if (c != NULL) { |
41 | 0 | return mp_div_2d(a, ix, c, NULL); |
42 | 0 | } |
43 | 0 | return MP_OKAY; |
44 | 0 | } |
45 | | |
46 | | /* three? */ |
47 | 0 | if (MP_HAS(MP_DIV_3) && (b == 3u)) { |
48 | 0 | return mp_div_3(a, c, d); |
49 | 0 | } |
50 | | |
51 | | /* no easy answer [c'est la vie]. Just division */ |
52 | 0 | if ((err = mp_init_size(&q, a->used)) != MP_OKAY) { |
53 | 0 | return err; |
54 | 0 | } |
55 | | |
56 | 0 | q.used = a->used; |
57 | 0 | q.sign = a->sign; |
58 | 0 | w = 0; |
59 | 0 | for (ix = a->used - 1; ix >= 0; ix--) { |
60 | 0 | w = (w << (mp_word)MP_DIGIT_BIT) | (mp_word)a->dp[ix]; |
61 | |
|
62 | 0 | if (w >= b) { |
63 | 0 | t = (mp_digit)(w / b); |
64 | 0 | w -= (mp_word)t * (mp_word)b; |
65 | 0 | } else { |
66 | 0 | t = 0; |
67 | 0 | } |
68 | 0 | q.dp[ix] = t; |
69 | 0 | } |
70 | |
|
71 | 0 | if (d != NULL) { |
72 | 0 | *d = (mp_digit)w; |
73 | 0 | } |
74 | |
|
75 | 0 | if (c != NULL) { |
76 | 0 | mp_clamp(&q); |
77 | 0 | mp_exch(&q, c); |
78 | 0 | } |
79 | 0 | mp_clear(&q); |
80 | |
|
81 | 0 | return err; |
82 | 0 | } |
83 | | |
84 | | #endif |