Mercurial > dropbear

comparison libtommath/bn_fast_s_mp_sqr.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_SQR_C 2 #ifdef BN_FAST_S_MP_SQR_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 /* the jist of squaring... 15 /* the jist of squaring...
19 * you do like mult except the offset of the tmpx [one that 16 * you do like mult except the offset of the tmpx [one that
20 * starts closer to zero] can't equal the offset of tmpy. 17 * starts closer to zero] can't equal the offset of tmpy.
21 * So basically you set up iy like before then you min it with 18 * So basically you set up iy like before then you min it with
22 * (ty-tx) so that it never happens. You double all those 19 * (ty-tx) so that it never happens. You double all those
23 * you add in the inner loop 20 * you add in the inner loop
24 21
25 After that loop you do the squares and add them in. 22 After that loop you do the squares and add them in.
26 */ 23 */
27 24
28 int fast_s_mp_sqr (mp_int * a, mp_int * b) 25 int fast_s_mp_sqr(const mp_int *a, mp_int *b)
29 { 26 {
30 int olduse, res, pa, ix, iz; 27 int olduse, res, pa, ix, iz;
31 mp_digit W[MP_WARRAY], *tmpx; 28 mp_digit W[MP_WARRAY], *tmpx;
32 mp_word W1; 29 mp_word W1;
33 30
34 /* grow the destination as required */ 31 /* grow the destination as required */
35 pa = a->used + a->used; 32 pa = a->used + a->used;
36 if (b->alloc < pa) { 33 if (b->alloc < pa) {
37 if ((res = mp_grow (b, pa)) != MP_OKAY) { 34 if ((res = mp_grow(b, pa)) != MP_OKAY) {
38 return res; 35 return res;
39 } 36 }
40 } 37 }
41 38
42 /* number of output digits to produce */ 39 /* number of output digits to produce */
43 W1 = 0; 40 W1 = 0;
44 for (ix = 0; ix < pa; ix++) { 41 for (ix = 0; ix < pa; ix++) {
45 int tx, ty, iy; 42 int tx, ty, iy;
46 mp_word _W; 43 mp_word _W;
47 mp_digit *tmpy; 44 mp_digit *tmpy;
48 45
49 /* clear counter */ 46 /* clear counter */
60 /* this is the number of times the loop will iterrate, essentially 57 /* this is the number of times the loop will iterrate, essentially
61 while (tx++ < a->used && ty-- >= 0) { ... } 58 while (tx++ < a->used && ty-- >= 0) { ... }
62 */ 59 */
63 iy = MIN(a->used-tx, ty+1); 60 iy = MIN(a->used-tx, ty+1);
64 61
65 /* now for squaring tx can never equal ty 62 /* now for squaring tx can never equal ty
66 * we halve the distance since they approach at a rate of 2x 63 * we halve the distance since they approach at a rate of 2x
67 * and we have to round because odd cases need to be executed 64 * and we have to round because odd cases need to be executed
68 */ 65 */
69 iy = MIN(iy, ((ty-tx)+1)>>1); 66 iy = MIN(iy, ((ty-tx)+1)>>1);
70 67
71 /* execute loop */ 68 /* execute loop */
72 for (iz = 0; iz < iy; iz++) { 69 for (iz = 0; iz < iy; iz++) {
73 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--); 70 _W += (mp_word)*tmpx++ * (mp_word)*tmpy--;
74 } 71 }
75 72
76 /* double the inner product and add carry */ 73 /* double the inner product and add carry */
77 _W = _W + _W + W1; 74 _W = _W + _W + W1;
78 75
79 /* even columns have the square term in them */ 76 /* even columns have the square term in them */
80 if ((ix&1) == 0) { 77 if (((unsigned)ix & 1u) == 0u) {
81 _W += ((mp_word)a->dp[ix>>1])*((mp_word)a->dp[ix>>1]); 78 _W += (mp_word)a->dp[ix>>1] * (mp_word)a->dp[ix>>1];
82 } 79 }
83 80
84 /* store it */ 81 /* store it */
85 W[ix] = (mp_digit)(_W & MP_MASK); 82 W[ix] = _W & MP_MASK;
86 83
87 /* make next carry */ 84 /* make next carry */
88 W1 = _W >> ((mp_word)DIGIT_BIT); 85 W1 = _W >> (mp_word)DIGIT_BIT;
89 } 86 }
90 87
91 /* setup dest */ 88 /* setup dest */
92 olduse = b->used; 89 olduse = b->used;
93 b->used = a->used+a->used; 90 b->used = a->used+a->used;
94 91
95 { 92 {
96 mp_digit *tmpb; 93 mp_digit *tmpb;
97 tmpb = b->dp; 94 tmpb = b->dp;
98 for (ix = 0; ix < pa; ix++) { 95 for (ix = 0; ix < pa; ix++) {
99 *tmpb++ = W[ix] & MP_MASK; 96 *tmpb++ = W[ix] & MP_MASK;
100 } 97 }
101 98
102 /* clear unused digits [that existed in the old copy of c] */ 99 /* clear unused digits [that existed in the old copy of c] */
103 for (; ix < olduse; ix++) { 100 for (; ix < olduse; ix++) {
104 *tmpb++ = 0; 101 *tmpb++ = 0;
105 } 102 }
106 } 103 }
107 mp_clamp (b); 104 mp_clamp(b);
108 return MP_OKAY; 105 return MP_OKAY;
109 } 106 }
110 #endif 107 #endif
111 108
112 /* ref: $Format:%D$ */ 109 /* ref: HEAD -> master, tag: v1.1.0 */
113 /* git commit: $Format:%H$ */ 110 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
114 /* commit time: $Format:%ai$ */ 111 /* commit time: 2019-01-28 20:32:32 +0100 */