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