1 /* $NetBSD: bn_mp_div_d.c,v 1.2 2017/01/28 21:31:47 christos Exp $ */
2
3 #include <tommath.h>
4 #ifdef BN_MP_DIV_D_C
5 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6 *
7 * LibTomMath is a library that provides multiple-precision
8 * integer arithmetic as well as number theoretic functionality.
9 *
10 * The library was designed directly after the MPI library by
11 * Michael Fromberger but has been written from scratch with
12 * additional optimizations in place.
13 *
14 * The library is free for all purposes without any express
15 * guarantee it works.
16 *
17 * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
18 */
19
s_is_power_of_two(mp_digit b,int * p)20 static int s_is_power_of_two(mp_digit b, int *p)
21 {
22 int x;
23
24 /* fast return if no power of two */
25 if ((b==0) || (b & (b-1))) {
26 return 0;
27 }
28
29 for (x = 0; x < DIGIT_BIT; x++) {
30 if (b == (((mp_digit)1)<<x)) {
31 *p = x;
32 return 1;
33 }
34 }
35 return 0;
36 }
37
38 /* single digit division (based on routine from MPI) */
mp_div_d(mp_int * a,mp_digit b,mp_int * c,mp_digit * d)39 int mp_div_d (mp_int * a, mp_digit b, mp_int * c, mp_digit * d)
40 {
41 mp_int q;
42 mp_word w;
43 mp_digit t;
44 int res, ix;
45
46 /* cannot divide by zero */
47 if (b == 0) {
48 return MP_VAL;
49 }
50
51 /* quick outs */
52 if (b == 1 || mp_iszero(a) == 1) {
53 if (d != NULL) {
54 *d = 0;
55 }
56 if (c != NULL) {
57 return mp_copy(a, c);
58 }
59 return MP_OKAY;
60 }
61
62 /* power of two ? */
63 if (s_is_power_of_two(b, &ix) == 1) {
64 if (d != NULL) {
65 *d = a->dp[0] & ((((mp_digit)1)<<ix) - 1);
66 }
67 if (c != NULL) {
68 return mp_div_2d(a, ix, c, NULL);
69 }
70 return MP_OKAY;
71 }
72
73 #ifdef BN_MP_DIV_3_C
74 /* three? */
75 if (b == 3) {
76 return mp_div_3(a, c, d);
77 }
78 #endif
79
80 /* no easy answer [c'est la vie]. Just division */
81 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
82 return res;
83 }
84
85 q.used = a->used;
86 q.sign = a->sign;
87 w = 0;
88 for (ix = a->used - 1; ix >= 0; ix--) {
89 w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
90
91 if (w >= b) {
92 t = (mp_digit)(w / b);
93 w -= ((mp_word)t) * ((mp_word)b);
94 } else {
95 t = 0;
96 }
97 q.dp[ix] = (mp_digit)t;
98 }
99
100 if (d != NULL) {
101 *d = (mp_digit)w;
102 }
103
104 if (c != NULL) {
105 mp_clamp(&q);
106 mp_exch(&q, c);
107 }
108 mp_clear(&q);
109
110 return res;
111 }
112
113 #endif
114
115 /* Source: /cvs/libtom/libtommath/bn_mp_div_d.c,v */
116 /* Revision: 1.5 */
117 /* Date: 2007/01/09 04:44:32 */
118