1#include <tommath.h>
2#ifdef BN_MP_DIV_3_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
18/* divide by three (based on routine from MPI and the GMP manual) */
19int
20mp_div_3 (mp_int * a, mp_int *c, mp_digit * d)
21{
22  mp_int   q;
23  mp_word  w, t;
24  mp_digit b;
25  int      res, ix;
26
27  /* b = 2**DIGIT_BIT / 3 */
28  b = (((mp_word)1) << ((mp_word)DIGIT_BIT)) / ((mp_word)3);
29
30  if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
31     return res;
32  }
33
34  q.used = a->used;
35  q.sign = a->sign;
36  w = 0;
37  for (ix = a->used - 1; ix >= 0; ix--) {
38     w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
39
40     if (w >= 3) {
41        /* multiply w by [1/3] */
42        t = (w * ((mp_word)b)) >> ((mp_word)DIGIT_BIT);
43
44        /* now subtract 3 * [w/3] from w, to get the remainder */
45        w -= t+t+t;
46
47        /* fixup the remainder as required since
48         * the optimization is not exact.
49         */
50        while (w >= 3) {
51           t += 1;
52           w -= 3;
53        }
54      } else {
55        t = 0;
56      }
57      q.dp[ix] = (mp_digit)t;
58  }
59
60  /* [optional] store the remainder */
61  if (d != NULL) {
62     *d = (mp_digit)w;
63  }
64
65  /* [optional] store the quotient */
66  if (c != NULL) {
67     mp_clamp(&q);
68     mp_exch(&q, c);
69  }
70  mp_clear(&q);
71
72  return res;
73}
74
75#endif
76
77/* $Source: /cvs/libtom/libtommath/bn_mp_div_3.c,v $ */
78/* $Revision: 1.4 $ */
79/* $Date: 2006/12/28 01:25:13 $ */
80