1 /* $NetBSD: bn_mp_div_3.c,v 1.2 2017/01/28 21:31:47 christos 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) */
21 int
mp_div_3(mp_int * a,mp_int * c,mp_digit * d)22 mp_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