Mercurial > dropbear

comparison libtommath/bn_mp_div_d.c @ 1739:13d834efc376 fuzz

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge from main
author Matt Johnston <matt@ucc.asn.au>
date Thu, 15 Oct 2020 19:55:15 +0800
parents 1051e4eea25a
children
comparison
equal deleted inserted replaced
1562:768ebf737aa0 1739:13d834efc376
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 * The library is free for all purposes without any express
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */
17 5
18 static int s_is_power_of_two(mp_digit b, int *p) 6 /* single digit division (based on routine from MPI) */
7 mp_err mp_div_d(const mp_int *a, mp_digit b, mp_int *c, mp_digit *d)
19 { 8 {
20 int x; 9 mp_int q;
10 mp_word w;
11 mp_digit t;
12 mp_err err;
13 int ix;
21 14
22 /* fast return if no power of two */ 15 /* cannot divide by zero */
23 if ((b == 0) || ((b & (b-1)) != 0)) { 16 if (b == 0u) {
24 return 0; 17 return MP_VAL;
25 } 18 }
26 19
27 for (x = 0; x < DIGIT_BIT; x++) { 20 /* quick outs */
28 if (b == (((mp_digit)1)<<x)) { 21 if ((b == 1u) || MP_IS_ZERO(a)) {
29 *p = x; 22 if (d != NULL) {
30 return 1; 23 *d = 0;
31 } 24 }
25 if (c != NULL) {
26 return mp_copy(a, c);
27 }
28 return MP_OKAY;
32 } 29 }
33 return 0;
34 }
35 30
36 /* single digit division (based on routine from MPI) */ 31 /* power of two ? */
37 int mp_div_d (mp_int * a, mp_digit b, mp_int * c, mp_digit * d) 32 if ((b & (b - 1u)) == 0u) {
38 { 33 ix = 1;
39 mp_int q; 34 while ((ix < MP_DIGIT_BIT) && (b != (((mp_digit)1)<<ix))) {
40 mp_word w; 35 ix++;
41 mp_digit t; 36 }
42 int res, ix; 37 if (d != NULL) {
38 *d = a->dp[0] & (((mp_digit)1<<(mp_digit)ix) - 1uL);
39 }
40 if (c != NULL) {
41 return mp_div_2d(a, ix, c, NULL);
42 }
43 return MP_OKAY;
44 }
43 45
44 /* cannot divide by zero */ 46 /* three? */
45 if (b == 0) { 47 if (MP_HAS(MP_DIV_3) && (b == 3u)) {
46 return MP_VAL; 48 return mp_div_3(a, c, d);
47 } 49 }
48 50
49 /* quick outs */ 51 /* no easy answer [c'est la vie]. Just division */
50 if ((b == 1) || (mp_iszero(a) == MP_YES)) { 52 if ((err = mp_init_size(&q, a->used)) != MP_OKAY) {
51 if (d != NULL) { 53 return err;
52 *d = 0; 54 }
53 }
54 if (c != NULL) {
55 return mp_copy(a, c);
56 }
57 return MP_OKAY;
58 }
59 55
60 /* power of two ? */ 56 q.used = a->used;
61 if (s_is_power_of_two(b, &ix) == 1) { 57 q.sign = a->sign;
62 if (d != NULL) { 58 w = 0;
63 *d = a->dp[0] & ((((mp_digit)1)<<ix) - 1); 59 for (ix = a->used - 1; ix >= 0; ix--) {
64 } 60 w = (w << (mp_word)MP_DIGIT_BIT) | (mp_word)a->dp[ix];
65 if (c != NULL) {
66 return mp_div_2d(a, ix, c, NULL);
67 }
68 return MP_OKAY;
69 }
70 61
71 #ifdef BN_MP_DIV_3_C 62 if (w >= b) {
72 /* three? */ 63 t = (mp_digit)(w / b);
73 if (b == 3) { 64 w -= (mp_word)t * (mp_word)b;
74 return mp_div_3(a, c, d); 65 } else {
75 } 66 t = 0;
76 #endif 67 }
68 q.dp[ix] = t;
69 }
77 70
78 /* no easy answer [c'est la vie]. Just division */ 71 if (d != NULL) {
79 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) { 72 *d = (mp_digit)w;
80 return res; 73 }
81 } 74
82 75 if (c != NULL) {
83 q.used = a->used; 76 mp_clamp(&q);
84 q.sign = a->sign; 77 mp_exch(&q, c);
85 w = 0; 78 }
86 for (ix = a->used - 1; ix >= 0; ix--) { 79 mp_clear(&q);
87 w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]); 80
88 81 return err;
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 } 82 }
110 83
111 #endif 84 #endif
112
113 /* ref: $Format:%D$ */
114 /* git commit: $Format:%H$ */
115 /* commit time: $Format:%ai$ */