Mercurial > dropbear

comparison bn_mp_div_3.c @ 1:22d5cf7d4b1a libtommath

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Renaming branch
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:23:46 +0000
parents
children d29b64170cf0
comparison
equal deleted inserted replaced
-1:000000000000 1:22d5cf7d4b1a
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2 *
3 * LibTomMath is a library that provides multiple-precision
4 * integer arithmetic as well as number theoretic functionality.
5 *
6 * The library was designed directly after the MPI library by
7 * Michael Fromberger but has been written from scratch with
8 * additional optimizations in place.
9 *
10 * The library is free for all purposes without any express
11 * guarantee it works.
12 *
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org
14 */
15 #include <tommath.h>
16
17 /* divide by three (based on routine from MPI and the GMP manual) */
18 int
19 mp_div_3 (mp_int * a, mp_int *c, mp_digit * d)
20 {
21 mp_int q;
22 mp_word w, t;
23 mp_digit b;
24 int res, ix;
25
26 /* b = 2**DIGIT_BIT / 3 */
27 b = (((mp_word)1) << ((mp_word)DIGIT_BIT)) / ((mp_word)3);
28
29 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
30 return res;
31 }
32
33 q.used = a->used;
34 q.sign = a->sign;
35 w = 0;
36 for (ix = a->used - 1; ix >= 0; ix--) {
37 w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
38
39 if (w >= 3) {
40 /* multiply w by [1/3] */
41 t = (w * ((mp_word)b)) >> ((mp_word)DIGIT_BIT);
42
43 /* now subtract 3 * [w/3] from w, to get the remainder */
44 w -= t+t+t;
45
46 /* fixup the remainder as required since
47 * the optimization is not exact.
48 */
49 while (w >= 3) {
50 t += 1;
51 w -= 3;
52 }
53 } else {
54 t = 0;
55 }
56 q.dp[ix] = (mp_digit)t;
57 }
58
59 /* [optional] store the remainder */
60 if (d != NULL) {
61 *d = (mp_digit)w;
62 }
63
64 /* [optional] store the quotient */
65 if (c != NULL) {
66 mp_clamp(&q);
67 mp_exch(&q, c);
68 }
69 mp_clear(&q);
70
71 return res;
72 }
73