Mercurial > dropbear

comparison libtommath/bn_mp_div_3.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_3_C 2 #ifdef BN_MP_DIV_3_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 /* divide by three (based on routine from MPI and the GMP manual) */ 6 /* divide by three (based on routine from MPI and the GMP manual) */
19 int 7 mp_err mp_div_3(const mp_int *a, mp_int *c, mp_digit *d)
20 mp_div_3 (mp_int * a, mp_int *c, mp_digit * d)
21 { 8 {
22 mp_int q; 9 mp_int q;
23 mp_word w, t; 10 mp_word w, t;
24 mp_digit b; 11 mp_digit b;
25 int res, ix; 12 mp_err err;
26 13 int ix;
27 /* b = 2**DIGIT_BIT / 3 */
28 b = (((mp_word)1) << ((mp_word)DIGIT_BIT)) / ((mp_word)3);
29 14
30 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) { 15 /* b = 2**MP_DIGIT_BIT / 3 */
31 return res; 16 b = ((mp_word)1 << (mp_word)MP_DIGIT_BIT) / (mp_word)3;
32 }
33
34 q.used = a->used;
35 q.sign = a->sign;
36 w = 0;
37 for (ix = a->used - 1; ix >= 0; ix--) {
38 w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
39 17
40 if (w >= 3) { 18 if ((err = mp_init_size(&q, a->used)) != MP_OKAY) {
41 /* multiply w by [1/3] */ 19 return err;
42 t = (w * ((mp_word)b)) >> ((mp_word)DIGIT_BIT); 20 }
43 21
44 /* now subtract 3 * [w/3] from w, to get the remainder */ 22 q.used = a->used;
45 w -= t+t+t; 23 q.sign = a->sign;
24 w = 0;
25 for (ix = a->used - 1; ix >= 0; ix--) {
26 w = (w << (mp_word)MP_DIGIT_BIT) | (mp_word)a->dp[ix];
46 27
47 /* fixup the remainder as required since 28 if (w >= 3u) {
48 * the optimization is not exact. 29 /* multiply w by [1/3] */
49 */ 30 t = (w * (mp_word)b) >> (mp_word)MP_DIGIT_BIT;
50 while (w >= 3) { 31
51 t += 1; 32 /* now subtract 3 * [w/3] from w, to get the remainder */
52 w -= 3; 33 w -= t+t+t;
53 } 34
35 /* fixup the remainder as required since
36 * the optimization is not exact.
37 */
38 while (w >= 3u) {
39 t += 1u;
40 w -= 3u;
41 }
54 } else { 42 } else {
55 t = 0; 43 t = 0;
56 } 44 }
57 q.dp[ix] = (mp_digit)t; 45 q.dp[ix] = (mp_digit)t;
58 } 46 }
59 47
60 /* [optional] store the remainder */ 48 /* [optional] store the remainder */
61 if (d != NULL) { 49 if (d != NULL) {
62 *d = (mp_digit)w; 50 *d = (mp_digit)w;
63 } 51 }
64 52
65 /* [optional] store the quotient */ 53 /* [optional] store the quotient */
66 if (c != NULL) { 54 if (c != NULL) {
67 mp_clamp(&q); 55 mp_clamp(&q);
68 mp_exch(&q, c); 56 mp_exch(&q, c);
69 } 57 }
70 mp_clear(&q); 58 mp_clear(&q);
71 59
72 return res; 60 return err;
73 } 61 }
74 62
75 #endif 63 #endif
76
77 /* ref: $Format:%D$ */
78 /* git commit: $Format:%H$ */
79 /* commit time: $Format:%ai$ */