Mercurial > dropbear

annotate libtommath/bn_s_mp_mul_high_digs_fast.c @ 1843:03dfecca99bd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Use sudo for the real github action job (Wasn't required by act's runner)
author Matt Johnston <matt@ucc.asn.au>
date Mon, 18 Oct 2021 23:25:20 +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