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://math.libtomcrypt.com
16 */
17
18 /* divide by three (based on routine from MPI and the GMP manual) */
19 int
mp_div_3(mp_int * a,mp_int * c,mp_digit * d)20 mp_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.3 $ */
79 /* $Date: 2006/03/31 14:18:44 $ */
80