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
20static 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) */
39int 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