Mercurial > dropbear

comparison libtommath/bn_mp_div_d.c @ 1692:1051e4eea25a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update LibTomMath to 1.2.0 (#84) * update C files * update other files * update headers * update makefiles * remove mp_set/get_double() * use ltm 1.2.0 API * update ltm_desc * use bundled tommath if system-tommath is too old * XMALLOC etc. were changed to MP_MALLOC etc.
author Steffen Jaeckel <s@jaeckel.eu>
date Tue, 26 May 2020 17:36:47 +0200
parents f52919ffd3b1
children
comparison
equal deleted inserted replaced
1691:2d3745d58843 1692:1051e4eea25a
1 #include "tommath_private.h" 1 #include "tommath_private.h"
2 #ifdef BN_MP_DIV_D_C 2 #ifdef BN_MP_DIV_D_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
4 * 4 /* SPDX-License-Identifier: Unlicense */
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 * SPDX-License-Identifier: Unlicense
13 */
14
15 static int s_is_power_of_two(mp_digit b, int *p)
16 {
17 int x;
18
19 /* fast return if no power of two */
20 if ((b == 0u) || ((b & (b-1u)) != 0u)) {
21 return 0;
22 }
23
24 for (x = 0; x < DIGIT_BIT; x++) {
25 if (b == ((mp_digit)1<<(mp_digit)x)) {
26 *p = x;
27 return 1;
28 }
29 }
30 return 0;
31 }
32 5
33 /* single digit division (based on routine from MPI) */ 6 /* single digit division (based on routine from MPI) */
34 int mp_div_d(const mp_int *a, mp_digit b, mp_int *c, mp_digit *d) 7 mp_err mp_div_d(const mp_int *a, mp_digit b, mp_int *c, mp_digit *d)
35 { 8 {
36 mp_int q; 9 mp_int q;
37 mp_word w; 10 mp_word w;
38 mp_digit t; 11 mp_digit t;
39 int res, ix; 12 mp_err err;
13 int ix;
40 14
41 /* cannot divide by zero */ 15 /* cannot divide by zero */
42 if (b == 0u) { 16 if (b == 0u) {
43 return MP_VAL; 17 return MP_VAL;
44 } 18 }
45 19
46 /* quick outs */ 20 /* quick outs */
47 if ((b == 1u) || (mp_iszero(a) == MP_YES)) { 21 if ((b == 1u) || MP_IS_ZERO(a)) {
48 if (d != NULL) { 22 if (d != NULL) {
49 *d = 0; 23 *d = 0;
50 } 24 }
51 if (c != NULL) { 25 if (c != NULL) {
52 return mp_copy(a, c); 26 return mp_copy(a, c);
53 } 27 }
54 return MP_OKAY; 28 return MP_OKAY;
55 } 29 }
56 30
57 /* power of two ? */ 31 /* power of two ? */
58 if (s_is_power_of_two(b, &ix) == 1) { 32 if ((b & (b - 1u)) == 0u) {
33 ix = 1;
34 while ((ix < MP_DIGIT_BIT) && (b != (((mp_digit)1)<<ix))) {
35 ix++;
36 }
59 if (d != NULL) { 37 if (d != NULL) {
60 *d = a->dp[0] & (((mp_digit)1<<(mp_digit)ix) - 1uL); 38 *d = a->dp[0] & (((mp_digit)1<<(mp_digit)ix) - 1uL);
61 } 39 }
62 if (c != NULL) { 40 if (c != NULL) {
63 return mp_div_2d(a, ix, c, NULL); 41 return mp_div_2d(a, ix, c, NULL);
64 } 42 }
65 return MP_OKAY; 43 return MP_OKAY;
66 } 44 }
67 45
68 #ifdef BN_MP_DIV_3_C
69 /* three? */ 46 /* three? */
70 if (b == 3u) { 47 if (MP_HAS(MP_DIV_3) && (b == 3u)) {
71 return mp_div_3(a, c, d); 48 return mp_div_3(a, c, d);
72 } 49 }
73 #endif
74 50
75 /* no easy answer [c'est la vie]. Just division */ 51 /* no easy answer [c'est la vie]. Just division */
76 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) { 52 if ((err = mp_init_size(&q, a->used)) != MP_OKAY) {
77 return res; 53 return err;
78 } 54 }
79 55
80 q.used = a->used; 56 q.used = a->used;
81 q.sign = a->sign; 57 q.sign = a->sign;
82 w = 0; 58 w = 0;
83 for (ix = a->used - 1; ix >= 0; ix--) { 59 for (ix = a->used - 1; ix >= 0; ix--) {
84 w = (w << (mp_word)DIGIT_BIT) | (mp_word)a->dp[ix]; 60 w = (w << (mp_word)MP_DIGIT_BIT) | (mp_word)a->dp[ix];
85 61
86 if (w >= b) { 62 if (w >= b) {
87 t = (mp_digit)(w / b); 63 t = (mp_digit)(w / b);
88 w -= (mp_word)t * (mp_word)b; 64 w -= (mp_word)t * (mp_word)b;
89 } else { 65 } else {
100 mp_clamp(&q); 76 mp_clamp(&q);
101 mp_exch(&q, c); 77 mp_exch(&q, c);
102 } 78 }
103 mp_clear(&q); 79 mp_clear(&q);
104 80
105 return res; 81 return err;
106 } 82 }
107 83
108 #endif 84 #endif
109
110 /* ref: HEAD -> master, tag: v1.1.0 */
111 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
112 /* commit time: 2019-01-28 20:32:32 +0100 */