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