Mercurial > dropbear

annotate libtommath/bn_s_mp_mul_high_digs_fast.c @ 1769:0e178f767ada

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, 29 Oct 2020 21:51:41 +0800
parents 1051e4eea25a
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1692
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
1 #include "tommath_private.h"
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
2 #ifdef BN_S_MP_MUL_HIGH_DIGS_FAST_C
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
4 /* SPDX-License-Identifier: Unlicense */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
5
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
6 /* this is a modified version of fast_s_mul_digs that only produces
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
7 * output digits *above* digs. See the comments for fast_s_mul_digs
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
8 * to see how it works.
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
9 *
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
10 * This is used in the Barrett reduction since for one of the multiplications
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
11 * only the higher digits were needed. This essentially halves the work.
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
12 *
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
13 * Based on Algorithm 14.12 on pp.595 of HAC.
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
14 */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
15 mp_err s_mp_mul_high_digs_fast(const mp_int *a, const mp_int *b, mp_int *c, int digs)
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
16 {
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
17 int olduse, pa, ix, iz;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
18 mp_err err;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
19 mp_digit W[MP_WARRAY];
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
20 mp_word _W;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
21
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
22 /* grow the destination as required */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
23 pa = a->used + b->used;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
24 if (c->alloc < pa) {
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
25 if ((err = mp_grow(c, pa)) != MP_OKAY) {
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
26 return err;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
27 }
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
28 }
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
29
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
30 /* number of output digits to produce */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
31 pa = a->used + b->used;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
32 _W = 0;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
33 for (ix = digs; ix < pa; ix++) {
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
34 int tx, ty, iy;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
35 mp_digit *tmpx, *tmpy;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
36
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
37 /* get offsets into the two bignums */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
38 ty = MP_MIN(b->used-1, ix);
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
39 tx = ix - ty;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
40
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
41 /* setup temp aliases */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
42 tmpx = a->dp + tx;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
43 tmpy = b->dp + ty;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
44
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
45 /* this is the number of times the loop will iterrate, essentially its
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
46 while (tx++ < a->used && ty-- >= 0) { ... }
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
47 */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
48 iy = MP_MIN(a->used-tx, ty+1);
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
49
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
50 /* execute loop */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
51 for (iz = 0; iz < iy; iz++) {
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
52 _W += (mp_word)*tmpx++ * (mp_word)*tmpy--;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
53 }
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
54
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
55 /* store term */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
56 W[ix] = (mp_digit)_W & MP_MASK;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
57
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
58 /* make next carry */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
59 _W = _W >> (mp_word)MP_DIGIT_BIT;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
60 }
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
61
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
62 /* setup dest */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
63 olduse = c->used;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
64 c->used = pa;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
65
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
66 {
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
67 mp_digit *tmpc;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
68
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
69 tmpc = c->dp + digs;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
70 for (ix = digs; ix < pa; ix++) {
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
71 /* now extract the previous digit [below the carry] */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
72 *tmpc++ = W[ix];
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
73 }
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
74
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
75 /* clear unused digits [that existed in the old copy of c] */
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
76 MP_ZERO_DIGITS(tmpc, olduse - ix);
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
77 }
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
78 mp_clamp(c);
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
79 return MP_OKAY;
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
80 }
1051e4eea25a Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff changeset
81 #endif