Mercurial > dropbear

comparison tomsfastmath/src/divide/fp_div_d.c @ 643:a362b62d38b2 dropbear-tfm

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a with Makefile.in renamed
author Matt Johnston <matt@ucc.asn.au>
date Wed, 23 Nov 2011 18:10:20 +0700
parents
children
comparison
equal deleted inserted replaced
642:33fd2f3499d2 643:a362b62d38b2
1 /* TomsFastMath, a fast ISO C bignum library.
2 *
3 * This project is meant to fill in where LibTomMath
4 * falls short. That is speed ;-)
5 *
6 * This project is public domain and free for all purposes.
7 *
8 * Tom St Denis, [email protected]
9 */
10 #include <tfm.h>
11
12 static int s_is_power_of_two(fp_digit b, int *p)
13 {
14 int x;
15
16 /* fast return if no power of two */
17 if ((b==0) || (b & (b-1))) {
18 return 0;
19 }
20
21 for (x = 0; x < DIGIT_BIT; x++) {
22 if (b == (((fp_digit)1)<<x)) {
23 *p = x;
24 return 1;
25 }
26 }
27 return 0;
28 }
29
30 /* a/b => cb + d == a */
31 int fp_div_d(fp_int *a, fp_digit b, fp_int *c, fp_digit *d)
32 {
33 fp_int q;
34 fp_word w;
35 fp_digit t;
36 int ix;
37
38 /* cannot divide by zero */
39 if (b == 0) {
40 return FP_VAL;
41 }
42
43 /* quick outs */
44 if (b == 1 || fp_iszero(a) == 1) {
45 if (d != NULL) {
46 *d = 0;
47 }
48 if (c != NULL) {
49 fp_copy(a, c);
50 }
51 return FP_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] & ((((fp_digit)1)<<ix) - 1);
58 }
59 if (c != NULL) {
60 fp_div_2d(a, ix, c, NULL);
61 }
62 return FP_OKAY;
63 }
64
65 /* no easy answer [c'est la vie]. Just division */
66 fp_init(&q);
67
68 q.used = a->used;
69 q.sign = a->sign;
70 w = 0;
71 for (ix = a->used - 1; ix >= 0; ix--) {
72 w = (w << ((fp_word)DIGIT_BIT)) | ((fp_word)a->dp[ix]);
73
74 if (w >= b) {
75 t = (fp_digit)(w / b);
76 w -= ((fp_word)t) * ((fp_word)b);
77 } else {
78 t = 0;
79 }
80 q.dp[ix] = (fp_digit)t;
81 }
82
83 if (d != NULL) {
84 *d = (fp_digit)w;
85 }
86
87 if (c != NULL) {
88 fp_clamp(&q);
89 fp_copy(&q, c);
90 }
91
92 return FP_OKAY;
93 }
94
95
96 /* $Source$ */
97 /* $Revision$ */
98 /* $Date$ */