Mercurial > dropbear
annotate tomsfastmath/src/bit/fp_div_2d.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 /* c = a / 2**b */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
13 void fp_div_2d(fp_int *a, int b, fp_int *c, fp_int *d) |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
14 { |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
15 fp_digit D, r, rr; |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
16 int x; |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
17 fp_int t; |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
18 |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
19 /* if the shift count is <= 0 then we do no work */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
20 if (b <= 0) { |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
21 fp_copy (a, c); |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
22 if (d != NULL) { |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
23 fp_zero (d); |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
24 } |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
25 return; |
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 |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
28 fp_init(&t); |
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 /* get the remainder */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
31 if (d != NULL) { |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
32 fp_mod_2d (a, b, &t); |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
33 } |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
34 |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
35 /* copy */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
36 fp_copy(a, c); |
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 /* shift by as many digits in the bit count */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
39 if (b >= (int)DIGIT_BIT) { |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
40 fp_rshd (c, b / DIGIT_BIT); |
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 /* shift any bit count < DIGIT_BIT */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
44 D = (fp_digit) (b % DIGIT_BIT); |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
45 if (D != 0) { |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
46 register fp_digit *tmpc, mask, shift; |
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 /* mask */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
49 mask = (((fp_digit)1) << D) - 1; |
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 /* shift for lsb */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
52 shift = DIGIT_BIT - D; |
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 /* alias */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
55 tmpc = c->dp + (c->used - 1); |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
56 |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
57 /* carry */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
58 r = 0; |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
59 for (x = c->used - 1; x >= 0; x--) { |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
60 /* get the lower bits of this word in a temp */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
61 rr = *tmpc & mask; |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
62 |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
63 /* shift the current word and mix in the carry bits from the previous word */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
64 *tmpc = (*tmpc >> D) | (r << shift); |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
65 --tmpc; |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
66 |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
67 /* set the carry to the carry bits of the current word found above */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
68 r = rr; |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
69 } |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
70 } |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
71 fp_clamp (c); |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
72 if (d != NULL) { |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
73 fp_copy (&t, d); |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
74 } |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
75 } |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
76 |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
77 /* $Source$ */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
78 /* $Revision$ */ |
a362b62d38b2
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff
changeset
|
79 /* $Date$ */ |