Mercurial > hg > Members > anatofuz > MoarVM

comparison 3rdparty/libtommath/bn_mp_div_d.c @ 0:2cf249471370

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
convert mercurial for git
author Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
date Tue, 08 May 2018 16:09:12 +0900
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:2cf249471370
1 #include <tommath_private.h>
2 #ifdef BN_MP_DIV_D_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4 *
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
7 *
8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place.
11 *
12 * The library is free for all purposes without any express
13 * guarantee it works.
14 *
15 * Tom St Denis, tstdenis82@gmail.com, http://libtom.org
16 */
17
18 static int s_is_power_of_two(mp_digit b, int *p)
19 {
20 int x;
21
22 /* fast return if no power of two */
23 if ((b == 0) || ((b & (b-1)) != 0)) {
24 return 0;
25 }
26
27 for (x = 0; x < DIGIT_BIT; x++) {
28 if (b == (((mp_digit)1)<<x)) {
29 *p = x;
30 return 1;
31 }
32 }
33 return 0;
34 }
35
36 /* single digit division (based on routine from MPI) */
37 int mp_div_d (mp_int * a, mp_digit b, mp_int * c, mp_digit * d)
38 {
39 mp_int q;
40 mp_word w;
41 mp_digit t;
42 int res, ix;
43
44 /* cannot divide by zero */
45 if (b == 0) {
46 return MP_VAL;
47 }
48
49 /* quick outs */
50 if ((b == 1) || (mp_iszero(a) == MP_YES)) {
51 if (d != NULL) {
52 *d = 0;
53 }
54 if (c != NULL) {
55 return mp_copy(a, c);
56 }
57 return MP_OKAY;
58 }
59
60 /* power of two ? */
61 if (s_is_power_of_two(b, &ix) == 1) {
62 if (d != NULL) {
63 *d = a->dp[0] & ((((mp_digit)1)<<ix) - 1);
64 }
65 if (c != NULL) {
66 return mp_div_2d(a, ix, c, NULL);
67 }
68 return MP_OKAY;
69 }
70
71 #ifdef BN_MP_DIV_3_C
72 /* three? */
73 if (b == 3) {
74 return mp_div_3(a, c, d);
75 }
76 #endif
77
78 /* no easy answer [c'est la vie]. Just division */
79 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
80 return res;
81 }
82
83 q.used = a->used;
84 q.sign = a->sign;
85 w = 0;
86 for (ix = a->used - 1; ix >= 0; ix--) {
87 w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
88
89 if (w >= b) {
90 t = (mp_digit)(w / b);
91 w -= ((mp_word)t) * ((mp_word)b);
92 } else {
93 t = 0;
94 }
95 q.dp[ix] = (mp_digit)t;
96 }
97
98 if (d != NULL) {
99 *d = (mp_digit)w;
100 }
101
102 if (c != NULL) {
103 mp_clamp(&q);
104 mp_exch(&q, c);
105 }
106 mp_clear(&q);
107
108 return res;
109 }
110
111 #endif
112
113 /* $Source$ */
114 /* $Revision$ */
115 /* $Date$ */