Mercurial > dropbear

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