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