Mercurial > dropbear

comparison libtommath/bn_mp_div_3.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_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 * SPDX-License-Identifier: Unlicense
13 */
14 5
15 /* 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) */
16 int mp_div_3(const mp_int *a, mp_int *c, mp_digit *d) 7 mp_err mp_div_3(const mp_int *a, mp_int *c, mp_digit *d)
17 { 8 {
18 mp_int q; 9 mp_int q;
19 mp_word w, t; 10 mp_word w, t;
20 mp_digit b; 11 mp_digit b;
21 int res, ix; 12 mp_err err;
13 int ix;
22 14
23 /* b = 2**DIGIT_BIT / 3 */ 15 /* b = 2**MP_DIGIT_BIT / 3 */
24 b = ((mp_word)1 << (mp_word)DIGIT_BIT) / (mp_word)3; 16 b = ((mp_word)1 << (mp_word)MP_DIGIT_BIT) / (mp_word)3;
25 17
26 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) { 18 if ((err = mp_init_size(&q, a->used)) != MP_OKAY) {
27 return res; 19 return err;
28 } 20 }
29 21
30 q.used = a->used; 22 q.used = a->used;
31 q.sign = a->sign; 23 q.sign = a->sign;
32 w = 0; 24 w = 0;
33 for (ix = a->used - 1; ix >= 0; ix--) { 25 for (ix = a->used - 1; ix >= 0; ix--) {
34 w = (w << (mp_word)DIGIT_BIT) | (mp_word)a->dp[ix]; 26 w = (w << (mp_word)MP_DIGIT_BIT) | (mp_word)a->dp[ix];
35 27
36 if (w >= 3u) { 28 if (w >= 3u) {
37 /* multiply w by [1/3] */ 29 /* multiply w by [1/3] */
38 t = (w * (mp_word)b) >> (mp_word)DIGIT_BIT; 30 t = (w * (mp_word)b) >> (mp_word)MP_DIGIT_BIT;
39 31
40 /* now subtract 3 * [w/3] from w, to get the remainder */ 32 /* now subtract 3 * [w/3] from w, to get the remainder */
41 w -= t+t+t; 33 w -= t+t+t;
42 34
43 /* fixup the remainder as required since 35 /* fixup the remainder as required since
63 mp_clamp(&q); 55 mp_clamp(&q);
64 mp_exch(&q, c); 56 mp_exch(&q, c);
65 } 57 }
66 mp_clear(&q); 58 mp_clear(&q);
67 59
68 return res; 60 return err;
69 } 61 }
70 62
71 #endif 63 #endif
72
73 /* ref: HEAD -> master, tag: v1.1.0 */
74 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
75 /* commit time: 2019-01-28 20:32:32 +0100 */