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