Mercurial > dropbear

comparison bn_mp_div.c @ 142:d29b64170cf0 libtommath-orig

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
import of libtommath 0.32
author Matt Johnston <matt@ucc.asn.au>
date Sun, 19 Dec 2004 11:33:56 +0000
parents 86e0b50a9b58
children d8254fc979e9
comparison
equal deleted inserted replaced
19:e1037a1e12e7 142:d29b64170cf0
1 #include <tommath.h>
2 #ifdef BN_MP_DIV_C
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2 * 4 *
3 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
4 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
5 * 7 *
10 * The library is free for all purposes without any express 12 * The library is free for all purposes without any express
11 * guarantee it works. 13 * guarantee it works.
12 * 14 *
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org 15 * Tom St Denis, [email protected], http://math.libtomcrypt.org
14 */ 16 */
15 #include <tommath.h> 17
18 #ifdef BN_MP_DIV_SMALL
19
20 /* slower bit-bang division... also smaller */
21 int mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d)
22 {
23 mp_int ta, tb, tq, q;
24 int res, n, n2;
25
26 /* is divisor zero ? */
27 if (mp_iszero (b) == 1) {
28 return MP_VAL;
29 }
30
31 /* if a < b then q=0, r = a */
32 if (mp_cmp_mag (a, b) == MP_LT) {
33 if (d != NULL) {
34 res = mp_copy (a, d);
35 } else {
36 res = MP_OKAY;
37 }
38 if (c != NULL) {
39 mp_zero (c);
40 }
41 return res;
42 }
43
44 /* init our temps */
45 if ((res = mp_init_multi(&ta, &tb, &tq, &q, NULL) != MP_OKAY)) {
46 return res;
47 }
48
49
50 mp_set(&tq, 1);
51 n = mp_count_bits(a) - mp_count_bits(b);
52 if (((res = mp_copy(a, &ta)) != MP_OKAY) ||
53 ((res = mp_copy(b, &tb)) != MP_OKAY) ||
54 ((res = mp_mul_2d(&tb, n, &tb)) != MP_OKAY) ||
55 ((res = mp_mul_2d(&tq, n, &tq)) != MP_OKAY)) {
56 goto __ERR;
57 }
58
59 while (n-- >= 0) {
60 if (mp_cmp(&tb, &ta) != MP_GT) {
61 if (((res = mp_sub(&ta, &tb, &ta)) != MP_OKAY) ||
62 ((res = mp_add(&q, &tq, &q)) != MP_OKAY)) {
63 goto __ERR;
64 }
65 }
66 if (((res = mp_div_2d(&tb, 1, &tb, NULL)) != MP_OKAY) ||
67 ((res = mp_div_2d(&tq, 1, &tq, NULL)) != MP_OKAY)) {
68 goto __ERR;
69 }
70 }
71
72 /* now q == quotient and ta == remainder */
73 n = a->sign;
74 n2 = (a->sign == b->sign ? MP_ZPOS : MP_NEG);
75 if (c != NULL) {
76 mp_exch(c, &q);
77 c->sign = n2;
78 }
79 if (d != NULL) {
80 mp_exch(d, &ta);
81 d->sign = n;
82 }
83 __ERR:
84 mp_clear_multi(&ta, &tb, &tq, &q, NULL);
85 return res;
86 }
87
88 #else
16 89
17 /* integer signed division. 90 /* integer signed division.
18 * c*b + d == a [e.g. a/b, c=quotient, d=remainder] 91 * c*b + d == a [e.g. a/b, c=quotient, d=remainder]
19 * HAC pp.598 Algorithm 14.20 92 * HAC pp.598 Algorithm 14.20
20 * 93 *
185 /* now q is the quotient and x is the remainder 258 /* now q is the quotient and x is the remainder
186 * [which we have to normalize] 259 * [which we have to normalize]
187 */ 260 */
188 261
189 /* get sign before writing to c */ 262 /* get sign before writing to c */
190 x.sign = a->sign; 263 x.sign = x.used == 0 ? MP_ZPOS : a->sign;
191 264
192 if (c != NULL) { 265 if (c != NULL) {
193 mp_clamp (&q); 266 mp_clamp (&q);
194 mp_exch (&q, c); 267 mp_exch (&q, c);
195 c->sign = neg; 268 c->sign = neg;
207 __T2:mp_clear (&t2); 280 __T2:mp_clear (&t2);
208 __T1:mp_clear (&t1); 281 __T1:mp_clear (&t1);
209 __Q:mp_clear (&q); 282 __Q:mp_clear (&q);
210 return res; 283 return res;
211 } 284 }
285
286 #endif
287
288 #endif