Mercurial > dropbear

comparison bn_mp_div_d.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 static int s_is_power_of_two(mp_digit b, int *p)
18 {
19 int x;
20
21 for (x = 1; x < DIGIT_BIT; x++) {
22 if (b == (((mp_digit)1)<<x)) {
23 *p = x;
24 return 1;
25 }
26 }
27 return 0;
28 }
29
30 /* single digit division (based on routine from MPI) */
31 int mp_div_d (mp_int * a, mp_digit b, mp_int * c, mp_digit * d)
32 {
33 mp_int q;
34 mp_word w;
35 mp_digit t;
36 int res, ix;
37
38 /* cannot divide by zero */
39 if (b == 0) {
40 return MP_VAL;
41 }
42
43 /* quick outs */
44 if (b == 1 || mp_iszero(a) == 1) {
45 if (d != NULL) {
46 *d = 0;
47 }
48 if (c != NULL) {
49 return mp_copy(a, c);
50 }
51 return MP_OKAY;
52 }
53
54 /* power of two ? */
55 if (s_is_power_of_two(b, &ix) == 1) {
56 if (d != NULL) {
57 *d = a->dp[0] & ((1<<ix) - 1);
58 }
59 if (c != NULL) {
60 return mp_div_2d(a, ix, c, NULL);
61 }
62 return MP_OKAY;
63 }
64
65 /* three? */
66 if (b == 3) {
67 return mp_div_3(a, c, d);
68 }
69
70 /* no easy answer [c'est la vie]. Just division */
71 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
72 return res;
73 }
74
75 q.used = a->used;
76 q.sign = a->sign;
77 w = 0;
78 for (ix = a->used - 1; ix >= 0; ix--) {
79 w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
80
81 if (w >= b) {
82 t = (mp_digit)(w / b);
83 w -= ((mp_word)t) * ((mp_word)b);
84 } else {
85 t = 0;
86 }
87 q.dp[ix] = (mp_digit)t;
88 }
89
90 if (d != NULL) {
91 *d = (mp_digit)w;
92 }
93
94 if (c != NULL) {
95 mp_clamp(&q);
96 mp_exch(&q, c);
97 }
98 mp_clear(&q);
99
100 return res;
101 }
102