Mercurial > dropbear

comparison libtommath/bn_mp_div_d.c @ 1655:f52919ffd3b1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) * make key-generation compliant to FIPS 186.4 * fix includes in tommath_class.h * update fuzzcorpus instead of error-out * fixup fuzzing make-targets * update Makefile.in * apply necessary patches to ltm sources * clean-up not required ltm files * update to vanilla ltm 1.1.0 this already only contains the required files * remove set/get double
author Steffen Jaeckel <s_jaeckel@gmx.de>
date Mon, 16 Sep 2019 15:50:38 +0200
parents 8bba51a55704
children 1051e4eea25a
comparison
equal deleted inserted replaced
1654:cc0fc5131c5c 1655:f52919ffd3b1
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 *
5 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
7 * 7 *
8 * The library was designed directly after the MPI library by 8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with 9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place. 10 * additional optimizations in place.
11 * 11 *
12 * The library is free for all purposes without any express 12 * SPDX-License-Identifier: Unlicense
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */ 13 */
17 14
18 static int s_is_power_of_two(mp_digit b, int *p) 15 static int s_is_power_of_two(mp_digit b, int *p)
19 { 16 {
20 int x; 17 int x;
21 18
22 /* fast return if no power of two */ 19 /* fast return if no power of two */
23 if ((b == 0) || ((b & (b-1)) != 0)) { 20 if ((b == 0u) || ((b & (b-1u)) != 0u)) {
24 return 0; 21 return 0;
25 } 22 }
26 23
27 for (x = 0; x < DIGIT_BIT; x++) { 24 for (x = 0; x < DIGIT_BIT; x++) {
28 if (b == (((mp_digit)1)<<x)) { 25 if (b == ((mp_digit)1<<(mp_digit)x)) {
29 *p = x; 26 *p = x;
30 return 1; 27 return 1;
31 } 28 }
32 } 29 }
33 return 0; 30 return 0;
34 } 31 }
35 32
36 /* single digit division (based on routine from MPI) */ 33 /* 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) 34 int mp_div_d(const mp_int *a, mp_digit b, mp_int *c, mp_digit *d)
38 { 35 {
39 mp_int q; 36 mp_int q;
40 mp_word w; 37 mp_word w;
41 mp_digit t; 38 mp_digit t;
42 int res, ix; 39 int res, ix;
43 40
44 /* cannot divide by zero */ 41 /* cannot divide by zero */
45 if (b == 0) { 42 if (b == 0u) {
46 return MP_VAL; 43 return MP_VAL;
47 } 44 }
48 45
49 /* quick outs */ 46 /* quick outs */
50 if ((b == 1) || (mp_iszero(a) == MP_YES)) { 47 if ((b == 1u) || (mp_iszero(a) == MP_YES)) {
51 if (d != NULL) { 48 if (d != NULL) {
52 *d = 0; 49 *d = 0;
53 } 50 }
54 if (c != NULL) { 51 if (c != NULL) {
55 return mp_copy(a, c); 52 return mp_copy(a, c);
56 } 53 }
57 return MP_OKAY; 54 return MP_OKAY;
58 } 55 }
59 56
60 /* power of two ? */ 57 /* power of two ? */
61 if (s_is_power_of_two(b, &ix) == 1) { 58 if (s_is_power_of_two(b, &ix) == 1) {
62 if (d != NULL) { 59 if (d != NULL) {
63 *d = a->dp[0] & ((((mp_digit)1)<<ix) - 1); 60 *d = a->dp[0] & (((mp_digit)1<<(mp_digit)ix) - 1uL);
64 } 61 }
65 if (c != NULL) { 62 if (c != NULL) {
66 return mp_div_2d(a, ix, c, NULL); 63 return mp_div_2d(a, ix, c, NULL);
67 } 64 }
68 return MP_OKAY; 65 return MP_OKAY;
69 } 66 }
70 67
71 #ifdef BN_MP_DIV_3_C 68 #ifdef BN_MP_DIV_3_C
72 /* three? */ 69 /* three? */
73 if (b == 3) { 70 if (b == 3u) {
74 return mp_div_3(a, c, d); 71 return mp_div_3(a, c, d);
75 } 72 }
76 #endif 73 #endif
77 74
78 /* no easy answer [c'est la vie]. Just division */ 75 /* no easy answer [c'est la vie]. Just division */
79 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) { 76 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
80 return res; 77 return res;
81 } 78 }
82 79
83 q.used = a->used; 80 q.used = a->used;
84 q.sign = a->sign; 81 q.sign = a->sign;
85 w = 0; 82 w = 0;
86 for (ix = a->used - 1; ix >= 0; ix--) { 83 for (ix = a->used - 1; ix >= 0; ix--) {
87 w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]); 84 w = (w << (mp_word)DIGIT_BIT) | (mp_word)a->dp[ix];
88 85
89 if (w >= b) { 86 if (w >= b) {
90 t = (mp_digit)(w / b); 87 t = (mp_digit)(w / b);
91 w -= ((mp_word)t) * ((mp_word)b); 88 w -= (mp_word)t * (mp_word)b;
92 } else { 89 } else {
93 t = 0; 90 t = 0;
94 } 91 }
95 q.dp[ix] = (mp_digit)t; 92 q.dp[ix] = t;
96 } 93 }
97 94
98 if (d != NULL) { 95 if (d != NULL) {
99 *d = (mp_digit)w; 96 *d = (mp_digit)w;
100 } 97 }
101 98
102 if (c != NULL) { 99 if (c != NULL) {
103 mp_clamp(&q); 100 mp_clamp(&q);
104 mp_exch(&q, c); 101 mp_exch(&q, c);
105 } 102 }
106 mp_clear(&q); 103 mp_clear(&q);
107 104
108 return res; 105 return res;
109 } 106 }
110 107
111 #endif 108 #endif
112 109
113 /* ref: $Format:%D$ */ 110 /* ref: HEAD -> master, tag: v1.1.0 */
114 /* git commit: $Format:%H$ */ 111 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
115 /* commit time: $Format:%ai$ */ 112 /* commit time: 2019-01-28 20:32:32 +0100 */