Mercurial > dropbear

comparison libtommath/bn_fast_s_mp_mul_high_digs.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
comparison
equal deleted inserted replaced
1654:cc0fc5131c5c 1655:f52919ffd3b1
1 #include <tommath_private.h> 1 #include "tommath_private.h"
2 #ifdef BN_FAST_S_MP_MUL_HIGH_DIGS_C 2 #ifdef BN_FAST_S_MP_MUL_HIGH_DIGS_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 /* this is a modified version of fast_s_mul_digs that only produces 15 /* this is a modified version of fast_s_mul_digs that only produces
19 * output digits *above* digs. See the comments for fast_s_mul_digs 16 * output digits *above* digs. See the comments for fast_s_mul_digs
20 * to see how it works. 17 * to see how it works.
22 * This is used in the Barrett reduction since for one of the multiplications 19 * This is used in the Barrett reduction since for one of the multiplications
23 * only the higher digits were needed. This essentially halves the work. 20 * only the higher digits were needed. This essentially halves the work.
24 * 21 *
25 * Based on Algorithm 14.12 on pp.595 of HAC. 22 * Based on Algorithm 14.12 on pp.595 of HAC.
26 */ 23 */
27 int fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs) 24 int fast_s_mp_mul_high_digs(const mp_int *a, const mp_int *b, mp_int *c, int digs)
28 { 25 {
29 int olduse, res, pa, ix, iz; 26 int olduse, res, pa, ix, iz;
30 mp_digit W[MP_WARRAY]; 27 mp_digit W[MP_WARRAY];
31 mp_word _W; 28 mp_word _W;
32 29
33 /* grow the destination as required */ 30 /* grow the destination as required */
34 pa = a->used + b->used; 31 pa = a->used + b->used;
35 if (c->alloc < pa) { 32 if (c->alloc < pa) {
36 if ((res = mp_grow (c, pa)) != MP_OKAY) { 33 if ((res = mp_grow(c, pa)) != MP_OKAY) {
37 return res; 34 return res;
38 } 35 }
39 } 36 }
40 37
41 /* number of output digits to produce */ 38 /* number of output digits to produce */
42 pa = a->used + b->used; 39 pa = a->used + b->used;
43 _W = 0; 40 _W = 0;
44 for (ix = digs; ix < pa; ix++) { 41 for (ix = digs; ix < pa; ix++) {
45 int tx, ty, iy; 42 int tx, ty, iy;
46 mp_digit *tmpx, *tmpy; 43 mp_digit *tmpx, *tmpy;
47 44
48 /* get offsets into the two bignums */ 45 /* get offsets into the two bignums */
49 ty = MIN(b->used-1, ix); 46 ty = MIN(b->used-1, ix);
51 48
52 /* setup temp aliases */ 49 /* setup temp aliases */
53 tmpx = a->dp + tx; 50 tmpx = a->dp + tx;
54 tmpy = b->dp + ty; 51 tmpy = b->dp + ty;
55 52
56 /* this is the number of times the loop will iterrate, essentially its 53 /* this is the number of times the loop will iterrate, essentially its
57 while (tx++ < a->used && ty-- >= 0) { ... } 54 while (tx++ < a->used && ty-- >= 0) { ... }
58 */ 55 */
59 iy = MIN(a->used-tx, ty+1); 56 iy = MIN(a->used-tx, ty+1);
60 57
61 /* execute loop */ 58 /* execute loop */
62 for (iz = 0; iz < iy; iz++) { 59 for (iz = 0; iz < iy; iz++) {
63 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--); 60 _W += (mp_word)*tmpx++ * (mp_word)*tmpy--;
64 } 61 }
65 62
66 /* store term */ 63 /* store term */
67 W[ix] = ((mp_digit)_W) & MP_MASK; 64 W[ix] = (mp_digit)_W & MP_MASK;
68 65
69 /* make next carry */ 66 /* make next carry */
70 _W = _W >> ((mp_word)DIGIT_BIT); 67 _W = _W >> (mp_word)DIGIT_BIT;
71 } 68 }
72
73 /* setup dest */
74 olduse = c->used;
75 c->used = pa;
76 69
77 { 70 /* setup dest */
78 mp_digit *tmpc; 71 olduse = c->used;
72 c->used = pa;
79 73
80 tmpc = c->dp + digs; 74 {
81 for (ix = digs; ix < pa; ix++) { 75 mp_digit *tmpc;
82 /* now extract the previous digit [below the carry] */
83 *tmpc++ = W[ix];
84 }
85 76
86 /* clear unused digits [that existed in the old copy of c] */ 77 tmpc = c->dp + digs;
87 for (; ix < olduse; ix++) { 78 for (ix = digs; ix < pa; ix++) {
88 *tmpc++ = 0; 79 /* now extract the previous digit [below the carry] */
89 } 80 *tmpc++ = W[ix];
90 } 81 }
91 mp_clamp (c); 82
92 return MP_OKAY; 83 /* clear unused digits [that existed in the old copy of c] */
84 for (; ix < olduse; ix++) {
85 *tmpc++ = 0;
86 }
87 }
88 mp_clamp(c);
89 return MP_OKAY;
93 } 90 }
94 #endif 91 #endif
95 92
96 /* ref: $Format:%D$ */ 93 /* ref: HEAD -> master, tag: v1.1.0 */
97 /* git commit: $Format:%H$ */ 94 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
98 /* commit time: $Format:%ai$ */ 95 /* commit time: 2019-01-28 20:32:32 +0100 */