annotate nss/lib/freebl/mpi/mpmontg.c @ 4:b513267f632f tip

Build DBM module
author Andre Heinecke <andre.heinecke@intevation.de>
date Tue, 05 Aug 2014 18:58:03 +0200
parents 1e5118fa0cb1
children
rev   line source
0
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1 /* This Source Code Form is subject to the terms of the Mozilla Public
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
4
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
5 /* This file implements moduluar exponentiation using Montgomery's
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
6 * method for modular reduction. This file implements the method
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
7 * described as "Improvement 2" in the paper "A Cryptogrpahic Library for
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
8 * the Motorola DSP56000" by Stephen R. Dusse' and Burton S. Kaliski Jr.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
9 * published in "Advances in Cryptology: Proceedings of EUROCRYPT '90"
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
10 * "Lecture Notes in Computer Science" volume 473, 1991, pg 230-244,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
11 * published by Springer Verlag.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
12 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
13
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
14 #define MP_USING_CACHE_SAFE_MOD_EXP 1
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
15 #include <string.h>
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
16 #include "mpi-priv.h"
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
17 #include "mplogic.h"
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
18 #include "mpprime.h"
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
19 #ifdef MP_USING_MONT_MULF
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
20 #include "montmulf.h"
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
21 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
22 #include <stddef.h> /* ptrdiff_t */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
23
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
24 /* if MP_CHAR_STORE_SLOW is defined, we */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
25 /* need to know endianness of this platform. */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
26 #ifdef MP_CHAR_STORE_SLOW
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
27 #if !defined(MP_IS_BIG_ENDIAN) && !defined(MP_IS_LITTLE_ENDIAN)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
28 #error "You must define MP_IS_BIG_ENDIAN or MP_IS_LITTLE_ENDIAN\n" \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
29 " if you define MP_CHAR_STORE_SLOW."
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
30 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
31 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
32
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
33 #define STATIC
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
34
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
35 #define MAX_ODD_INTS 32 /* 2 ** (WINDOW_BITS - 1) */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
36
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
37 /*! computes T = REDC(T), 2^b == R
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
38 \param T < RN
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
39 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
40 mp_err s_mp_redc(mp_int *T, mp_mont_modulus *mmm)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
41 {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
42 mp_err res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
43 mp_size i;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
44
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
45 i = (MP_USED(&mmm->N) << 1) + 1;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
46 MP_CHECKOK( s_mp_pad(T, i) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
47 for (i = 0; i < MP_USED(&mmm->N); ++i ) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
48 mp_digit m_i = MP_DIGIT(T, i) * mmm->n0prime;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
49 /* T += N * m_i * (MP_RADIX ** i); */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
50 MP_CHECKOK( s_mp_mul_d_add_offset(&mmm->N, m_i, T, i) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
51 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
52 s_mp_clamp(T);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
53
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
54 /* T /= R */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
55 s_mp_rshd( T, MP_USED(&mmm->N) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
56
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
57 if ((res = s_mp_cmp(T, &mmm->N)) >= 0) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
58 /* T = T - N */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
59 MP_CHECKOK( s_mp_sub(T, &mmm->N) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
60 #ifdef DEBUG
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
61 if ((res = mp_cmp(T, &mmm->N)) >= 0) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
62 res = MP_UNDEF;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
63 goto CLEANUP;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
64 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
65 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
66 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
67 res = MP_OKAY;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
68 CLEANUP:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
69 return res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
70 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
71
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
72 #if !defined(MP_MONT_USE_MP_MUL)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
73
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
74 /*! c <- REDC( a * b ) mod N
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
75 \param a < N i.e. "reduced"
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
76 \param b < N i.e. "reduced"
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
77 \param mmm modulus N and n0' of N
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
78 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
79 mp_err s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
80 mp_mont_modulus *mmm)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
81 {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
82 mp_digit *pb;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
83 mp_digit m_i;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
84 mp_err res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
85 mp_size ib; /* "index b": index of current digit of B */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
86 mp_size useda, usedb;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
87
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
88 ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
89
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
90 if (MP_USED(a) < MP_USED(b)) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
91 const mp_int *xch = b; /* switch a and b, to do fewer outer loops */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
92 b = a;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
93 a = xch;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
94 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
95
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
96 MP_USED(c) = 1; MP_DIGIT(c, 0) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
97 ib = (MP_USED(&mmm->N) << 1) + 1;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
98 if((res = s_mp_pad(c, ib)) != MP_OKAY)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
99 goto CLEANUP;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
100
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
101 useda = MP_USED(a);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
102 pb = MP_DIGITS(b);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
103 s_mpv_mul_d(MP_DIGITS(a), useda, *pb++, MP_DIGITS(c));
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
104 s_mp_setz(MP_DIGITS(c) + useda + 1, ib - (useda + 1));
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
105 m_i = MP_DIGIT(c, 0) * mmm->n0prime;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
106 s_mp_mul_d_add_offset(&mmm->N, m_i, c, 0);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
107
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
108 /* Outer loop: Digits of b */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
109 usedb = MP_USED(b);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
110 for (ib = 1; ib < usedb; ib++) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
111 mp_digit b_i = *pb++;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
112
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
113 /* Inner product: Digits of a */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
114 if (b_i)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
115 s_mpv_mul_d_add_prop(MP_DIGITS(a), useda, b_i, MP_DIGITS(c) + ib);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
116 m_i = MP_DIGIT(c, ib) * mmm->n0prime;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
117 s_mp_mul_d_add_offset(&mmm->N, m_i, c, ib);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
118 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
119 if (usedb < MP_USED(&mmm->N)) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
120 for (usedb = MP_USED(&mmm->N); ib < usedb; ++ib ) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
121 m_i = MP_DIGIT(c, ib) * mmm->n0prime;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
122 s_mp_mul_d_add_offset(&mmm->N, m_i, c, ib);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
123 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
124 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
125 s_mp_clamp(c);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
126 s_mp_rshd( c, MP_USED(&mmm->N) ); /* c /= R */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
127 if (s_mp_cmp(c, &mmm->N) >= 0) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
128 MP_CHECKOK( s_mp_sub(c, &mmm->N) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
129 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
130 res = MP_OKAY;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
131
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
132 CLEANUP:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
133 return res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
134 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
135 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
136
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
137 STATIC
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
138 mp_err s_mp_to_mont(const mp_int *x, mp_mont_modulus *mmm, mp_int *xMont)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
139 {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
140 mp_err res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
141
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
142 /* xMont = x * R mod N where N is modulus */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
143 MP_CHECKOK( mp_copy( x, xMont ) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
144 MP_CHECKOK( s_mp_lshd( xMont, MP_USED(&mmm->N) ) ); /* xMont = x << b */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
145 MP_CHECKOK( mp_div(xMont, &mmm->N, 0, xMont) ); /* mod N */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
146 CLEANUP:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
147 return res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
148 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
149
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
150 #ifdef MP_USING_MONT_MULF
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
151
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
152 /* the floating point multiply is already cache safe,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
153 * don't turn on cache safe unless we specifically
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
154 * force it */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
155 #ifndef MP_FORCE_CACHE_SAFE
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
156 #undef MP_USING_CACHE_SAFE_MOD_EXP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
157 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
158
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
159 unsigned int mp_using_mont_mulf = 1;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
160
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
161 /* computes montgomery square of the integer in mResult */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
162 #define SQR \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
163 conv_i32_to_d32_and_d16(dm1, d16Tmp, mResult, nLen); \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
164 mont_mulf_noconv(mResult, dm1, d16Tmp, \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
165 dTmp, dn, MP_DIGITS(modulus), nLen, dn0)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
166
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
167 /* computes montgomery product of x and the integer in mResult */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
168 #define MUL(x) \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
169 conv_i32_to_d32(dm1, mResult, nLen); \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
170 mont_mulf_noconv(mResult, dm1, oddPowers[x], \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
171 dTmp, dn, MP_DIGITS(modulus), nLen, dn0)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
172
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
173 /* Do modular exponentiation using floating point multiply code. */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
174 mp_err mp_exptmod_f(const mp_int * montBase,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
175 const mp_int * exponent,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
176 const mp_int * modulus,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
177 mp_int * result,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
178 mp_mont_modulus *mmm,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
179 int nLen,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
180 mp_size bits_in_exponent,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
181 mp_size window_bits,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
182 mp_size odd_ints)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
183 {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
184 mp_digit *mResult;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
185 double *dBuf = 0, *dm1, *dn, *dSqr, *d16Tmp, *dTmp;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
186 double dn0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
187 mp_size i;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
188 mp_err res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
189 int expOff;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
190 int dSize = 0, oddPowSize, dTmpSize;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
191 mp_int accum1;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
192 double *oddPowers[MAX_ODD_INTS];
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
193
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
194 /* function for computing n0prime only works if n0 is odd */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
195
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
196 MP_DIGITS(&accum1) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
197
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
198 for (i = 0; i < MAX_ODD_INTS; ++i)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
199 oddPowers[i] = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
200
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
201 MP_CHECKOK( mp_init_size(&accum1, 3 * nLen + 2) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
202
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
203 mp_set(&accum1, 1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
204 MP_CHECKOK( s_mp_to_mont(&accum1, mmm, &accum1) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
205 MP_CHECKOK( s_mp_pad(&accum1, nLen) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
206
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
207 oddPowSize = 2 * nLen + 1;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
208 dTmpSize = 2 * oddPowSize;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
209 dSize = sizeof(double) * (nLen * 4 + 1 +
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
210 ((odd_ints + 1) * oddPowSize) + dTmpSize);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
211 dBuf = (double *)malloc(dSize);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
212 dm1 = dBuf; /* array of d32 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
213 dn = dBuf + nLen; /* array of d32 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
214 dSqr = dn + nLen; /* array of d32 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
215 d16Tmp = dSqr + nLen; /* array of d16 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
216 dTmp = d16Tmp + oddPowSize;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
217
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
218 for (i = 0; i < odd_ints; ++i) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
219 oddPowers[i] = dTmp;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
220 dTmp += oddPowSize;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
221 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
222 mResult = (mp_digit *)(dTmp + dTmpSize); /* size is nLen + 1 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
223
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
224 /* Make dn and dn0 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
225 conv_i32_to_d32(dn, MP_DIGITS(modulus), nLen);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
226 dn0 = (double)(mmm->n0prime & 0xffff);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
227
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
228 /* Make dSqr */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
229 conv_i32_to_d32_and_d16(dm1, oddPowers[0], MP_DIGITS(montBase), nLen);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
230 mont_mulf_noconv(mResult, dm1, oddPowers[0],
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
231 dTmp, dn, MP_DIGITS(modulus), nLen, dn0);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
232 conv_i32_to_d32(dSqr, mResult, nLen);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
233
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
234 for (i = 1; i < odd_ints; ++i) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
235 mont_mulf_noconv(mResult, dSqr, oddPowers[i - 1],
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
236 dTmp, dn, MP_DIGITS(modulus), nLen, dn0);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
237 conv_i32_to_d16(oddPowers[i], mResult, nLen);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
238 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
239
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
240 s_mp_copy(MP_DIGITS(&accum1), mResult, nLen); /* from, to, len */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
241
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
242 for (expOff = bits_in_exponent - window_bits; expOff >= 0; expOff -= window_bits) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
243 mp_size smallExp;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
244 MP_CHECKOK( mpl_get_bits(exponent, expOff, window_bits) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
245 smallExp = (mp_size)res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
246
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
247 if (window_bits == 1) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
248 if (!smallExp) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
249 SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
250 } else if (smallExp & 1) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
251 SQR; MUL(0);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
252 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
253 abort();
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
254 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
255 } else if (window_bits == 4) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
256 if (!smallExp) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
257 SQR; SQR; SQR; SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
258 } else if (smallExp & 1) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
259 SQR; SQR; SQR; SQR; MUL(smallExp/2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
260 } else if (smallExp & 2) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
261 SQR; SQR; SQR; MUL(smallExp/4); SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
262 } else if (smallExp & 4) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
263 SQR; SQR; MUL(smallExp/8); SQR; SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
264 } else if (smallExp & 8) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
265 SQR; MUL(smallExp/16); SQR; SQR; SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
266 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
267 abort();
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
268 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
269 } else if (window_bits == 5) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
270 if (!smallExp) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
271 SQR; SQR; SQR; SQR; SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
272 } else if (smallExp & 1) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
273 SQR; SQR; SQR; SQR; SQR; MUL(smallExp/2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
274 } else if (smallExp & 2) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
275 SQR; SQR; SQR; SQR; MUL(smallExp/4); SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
276 } else if (smallExp & 4) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
277 SQR; SQR; SQR; MUL(smallExp/8); SQR; SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
278 } else if (smallExp & 8) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
279 SQR; SQR; MUL(smallExp/16); SQR; SQR; SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
280 } else if (smallExp & 0x10) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
281 SQR; MUL(smallExp/32); SQR; SQR; SQR; SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
282 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
283 abort();
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
284 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
285 } else if (window_bits == 6) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
286 if (!smallExp) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
287 SQR; SQR; SQR; SQR; SQR; SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
288 } else if (smallExp & 1) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
289 SQR; SQR; SQR; SQR; SQR; SQR; MUL(smallExp/2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
290 } else if (smallExp & 2) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
291 SQR; SQR; SQR; SQR; SQR; MUL(smallExp/4); SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
292 } else if (smallExp & 4) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
293 SQR; SQR; SQR; SQR; MUL(smallExp/8); SQR; SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
294 } else if (smallExp & 8) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
295 SQR; SQR; SQR; MUL(smallExp/16); SQR; SQR; SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
296 } else if (smallExp & 0x10) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
297 SQR; SQR; MUL(smallExp/32); SQR; SQR; SQR; SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
298 } else if (smallExp & 0x20) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
299 SQR; MUL(smallExp/64); SQR; SQR; SQR; SQR; SQR;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
300 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
301 abort();
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
302 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
303 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
304 abort();
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
305 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
306 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
307
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
308 s_mp_copy(mResult, MP_DIGITS(&accum1), nLen); /* from, to, len */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
309
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
310 res = s_mp_redc(&accum1, mmm);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
311 mp_exch(&accum1, result);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
312
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
313 CLEANUP:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
314 mp_clear(&accum1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
315 if (dBuf) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
316 if (dSize)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
317 memset(dBuf, 0, dSize);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
318 free(dBuf);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
319 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
320
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
321 return res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
322 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
323 #undef SQR
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
324 #undef MUL
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
325 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
326
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
327 #define SQR(a,b) \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
328 MP_CHECKOK( mp_sqr(a, b) );\
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
329 MP_CHECKOK( s_mp_redc(b, mmm) )
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
330
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
331 #if defined(MP_MONT_USE_MP_MUL)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
332 #define MUL(x,a,b) \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
333 MP_CHECKOK( mp_mul(a, oddPowers + (x), b) ); \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
334 MP_CHECKOK( s_mp_redc(b, mmm) )
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
335 #else
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
336 #define MUL(x,a,b) \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
337 MP_CHECKOK( s_mp_mul_mont(a, oddPowers + (x), b, mmm) )
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
338 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
339
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
340 #define SWAPPA ptmp = pa1; pa1 = pa2; pa2 = ptmp
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
341
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
342 /* Do modular exponentiation using integer multiply code. */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
343 mp_err mp_exptmod_i(const mp_int * montBase,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
344 const mp_int * exponent,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
345 const mp_int * modulus,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
346 mp_int * result,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
347 mp_mont_modulus *mmm,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
348 int nLen,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
349 mp_size bits_in_exponent,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
350 mp_size window_bits,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
351 mp_size odd_ints)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
352 {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
353 mp_int *pa1, *pa2, *ptmp;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
354 mp_size i;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
355 mp_err res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
356 int expOff;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
357 mp_int accum1, accum2, power2, oddPowers[MAX_ODD_INTS];
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
358
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
359 /* power2 = base ** 2; oddPowers[i] = base ** (2*i + 1); */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
360 /* oddPowers[i] = base ** (2*i + 1); */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
361
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
362 MP_DIGITS(&accum1) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
363 MP_DIGITS(&accum2) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
364 MP_DIGITS(&power2) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
365 for (i = 0; i < MAX_ODD_INTS; ++i) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
366 MP_DIGITS(oddPowers + i) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
367 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
368
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
369 MP_CHECKOK( mp_init_size(&accum1, 3 * nLen + 2) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
370 MP_CHECKOK( mp_init_size(&accum2, 3 * nLen + 2) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
371
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
372 MP_CHECKOK( mp_init_copy(&oddPowers[0], montBase) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
373
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
374 mp_init_size(&power2, nLen + 2 * MP_USED(montBase) + 2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
375 MP_CHECKOK( mp_sqr(montBase, &power2) ); /* power2 = montBase ** 2 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
376 MP_CHECKOK( s_mp_redc(&power2, mmm) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
377
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
378 for (i = 1; i < odd_ints; ++i) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
379 mp_init_size(oddPowers + i, nLen + 2 * MP_USED(&power2) + 2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
380 MP_CHECKOK( mp_mul(oddPowers + (i - 1), &power2, oddPowers + i) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
381 MP_CHECKOK( s_mp_redc(oddPowers + i, mmm) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
382 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
383
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
384 /* set accumulator to montgomery residue of 1 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
385 mp_set(&accum1, 1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
386 MP_CHECKOK( s_mp_to_mont(&accum1, mmm, &accum1) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
387 pa1 = &accum1;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
388 pa2 = &accum2;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
389
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
390 for (expOff = bits_in_exponent - window_bits; expOff >= 0; expOff -= window_bits) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
391 mp_size smallExp;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
392 MP_CHECKOK( mpl_get_bits(exponent, expOff, window_bits) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
393 smallExp = (mp_size)res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
394
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
395 if (window_bits == 1) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
396 if (!smallExp) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
397 SQR(pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
398 } else if (smallExp & 1) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
399 SQR(pa1,pa2); MUL(0,pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
400 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
401 abort();
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
402 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
403 } else if (window_bits == 4) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
404 if (!smallExp) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
405 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
406 } else if (smallExp & 1) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
407 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
408 MUL(smallExp/2, pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
409 } else if (smallExp & 2) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
410 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
411 MUL(smallExp/4,pa2,pa1); SQR(pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
412 } else if (smallExp & 4) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
413 SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/8,pa1,pa2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
414 SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
415 } else if (smallExp & 8) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
416 SQR(pa1,pa2); MUL(smallExp/16,pa2,pa1); SQR(pa1,pa2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
417 SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
418 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
419 abort();
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
420 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
421 } else if (window_bits == 5) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
422 if (!smallExp) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
423 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
424 SQR(pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
425 } else if (smallExp & 1) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
426 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
427 SQR(pa1,pa2); MUL(smallExp/2,pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
428 } else if (smallExp & 2) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
429 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
430 MUL(smallExp/4,pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
431 } else if (smallExp & 4) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
432 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
433 MUL(smallExp/8,pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
434 } else if (smallExp & 8) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
435 SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/16,pa1,pa2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
436 SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
437 } else if (smallExp & 0x10) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
438 SQR(pa1,pa2); MUL(smallExp/32,pa2,pa1); SQR(pa1,pa2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
439 SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
440 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
441 abort();
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
442 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
443 } else if (window_bits == 6) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
444 if (!smallExp) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
445 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
446 SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
447 } else if (smallExp & 1) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
448 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
449 SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/2,pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
450 } else if (smallExp & 2) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
451 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
452 SQR(pa1,pa2); MUL(smallExp/4,pa2,pa1); SQR(pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
453 } else if (smallExp & 4) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
454 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
455 MUL(smallExp/8,pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
456 } else if (smallExp & 8) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
457 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
458 MUL(smallExp/16,pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
459 SQR(pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
460 } else if (smallExp & 0x10) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
461 SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/32,pa1,pa2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
462 SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
463 } else if (smallExp & 0x20) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
464 SQR(pa1,pa2); MUL(smallExp/64,pa2,pa1); SQR(pa1,pa2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
465 SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
466 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
467 abort();
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
468 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
469 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
470 abort();
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
471 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
472 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
473
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
474 res = s_mp_redc(pa1, mmm);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
475 mp_exch(pa1, result);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
476
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
477 CLEANUP:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
478 mp_clear(&accum1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
479 mp_clear(&accum2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
480 mp_clear(&power2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
481 for (i = 0; i < odd_ints; ++i) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
482 mp_clear(oddPowers + i);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
483 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
484 return res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
485 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
486 #undef SQR
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
487 #undef MUL
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
488
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
489 #ifdef MP_USING_CACHE_SAFE_MOD_EXP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
490 unsigned int mp_using_cache_safe_exp = 1;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
491 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
492
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
493 mp_err mp_set_safe_modexp(int value)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
494 {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
495 #ifdef MP_USING_CACHE_SAFE_MOD_EXP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
496 mp_using_cache_safe_exp = value;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
497 return MP_OKAY;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
498 #else
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
499 if (value == 0) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
500 return MP_OKAY;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
501 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
502 return MP_BADARG;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
503 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
504 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
505
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
506 #ifdef MP_USING_CACHE_SAFE_MOD_EXP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
507 #define WEAVE_WORD_SIZE 4
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
508
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
509 #ifndef MP_CHAR_STORE_SLOW
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
510 /*
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
511 * mpi_to_weave takes an array of bignums, a matrix in which each bignum
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
512 * occupies all the columns of a row, and transposes it into a matrix in
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
513 * which each bignum occupies a column of every row. The first row of the
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
514 * input matrix becomes the first column of the output matrix. The n'th
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
515 * row of input becomes the n'th column of output. The input data is said
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
516 * to be "interleaved" or "woven" into the output matrix.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
517 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
518 * The array of bignums is left in this woven form. Each time a single
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
519 * bignum value is needed, it is recreated by fetching the n'th column,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
520 * forming a single row which is the new bignum.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
521 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
522 * The purpose of this interleaving is make it impossible to determine which
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
523 * of the bignums is being used in any one operation by examining the pattern
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
524 * of cache misses.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
525 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
526 * The weaving function does not transpose the entire input matrix in one call.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
527 * It transposes 4 rows of mp_ints into their respective columns of output.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
528 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
529 * There are two different implementations of the weaving and unweaving code
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
530 * in this file. One uses byte loads and stores. The second uses loads and
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
531 * stores of mp_weave_word size values. The weaved forms of these two
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
532 * implementations differ. Consequently, each one has its own explanation.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
533 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
534 * Here is the explanation for the byte-at-a-time implementation.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
535 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
536 * This implementation treats each mp_int bignum as an array of bytes,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
537 * rather than as an array of mp_digits. It stores those bytes as a
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
538 * column of bytes in the output matrix. It doesn't care if the machine
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
539 * uses big-endian or little-endian byte ordering within mp_digits.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
540 * The first byte of the mp_digit array becomes the first byte in the output
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
541 * column, regardless of whether that byte is the MSB or LSB of the mp_digit.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
542 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
543 * "bignums" is an array of mp_ints.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
544 * It points to four rows, four mp_ints, a subset of a larger array of mp_ints.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
545 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
546 * "weaved" is the weaved output matrix.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
547 * The first byte of bignums[0] is stored in weaved[0].
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
548 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
549 * "nBignums" is the total number of bignums in the array of which "bignums"
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
550 * is a part.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
551 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
552 * "nDigits" is the size in mp_digits of each mp_int in the "bignums" array.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
553 * mp_ints that use less than nDigits digits are logically padded with zeros
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
554 * while being stored in the weaved array.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
555 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
556 mp_err mpi_to_weave(const mp_int *bignums,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
557 unsigned char *weaved,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
558 mp_size nDigits, /* in each mp_int of input */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
559 mp_size nBignums) /* in the entire source array */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
560 {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
561 mp_size i;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
562 unsigned char * endDest = weaved + (nDigits * nBignums * sizeof(mp_digit));
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
563
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
564 for (i=0; i < WEAVE_WORD_SIZE; i++) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
565 mp_size used = MP_USED(&bignums[i]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
566 unsigned char *pSrc = (unsigned char *)MP_DIGITS(&bignums[i]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
567 unsigned char *endSrc = pSrc + (used * sizeof(mp_digit));
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
568 unsigned char *pDest = weaved + i;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
569
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
570 ARGCHK(MP_SIGN(&bignums[i]) == MP_ZPOS, MP_BADARG);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
571 ARGCHK(used <= nDigits, MP_BADARG);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
572
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
573 for (; pSrc < endSrc; pSrc++) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
574 *pDest = *pSrc;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
575 pDest += nBignums;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
576 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
577 while (pDest < endDest) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
578 *pDest = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
579 pDest += nBignums;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
580 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
581 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
582
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
583 return MP_OKAY;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
584 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
585
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
586 /* Reverse the operation above for one mp_int.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
587 * Reconstruct one mp_int from its column in the weaved array.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
588 * "pSrc" points to the offset into the weave array of the bignum we
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
589 * are going to reconstruct.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
590 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
591 mp_err weave_to_mpi(mp_int *a, /* output, result */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
592 const unsigned char *pSrc, /* input, byte matrix */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
593 mp_size nDigits, /* per mp_int output */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
594 mp_size nBignums) /* bignums in weaved matrix */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
595 {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
596 unsigned char *pDest = (unsigned char *)MP_DIGITS(a);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
597 unsigned char *endDest = pDest + (nDigits * sizeof(mp_digit));
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
598
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
599 MP_SIGN(a) = MP_ZPOS;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
600 MP_USED(a) = nDigits;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
601
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
602 for (; pDest < endDest; pSrc += nBignums, pDest++) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
603 *pDest = *pSrc;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
604 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
605 s_mp_clamp(a);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
606 return MP_OKAY;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
607 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
608
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
609 #else
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
610
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
611 /* Need a primitive that we know is 32 bits long... */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
612 /* this is true on all modern processors we know of today*/
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
613 typedef unsigned int mp_weave_word;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
614
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
615 /*
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
616 * on some platforms character stores into memory is very expensive since they
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
617 * generate a read/modify/write operation on the bus. On those platforms
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
618 * we need to do integer writes to the bus. Because of some unrolled code,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
619 * in this current code the size of mp_weave_word must be four. The code that
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
620 * makes this assumption explicity is called out. (on some platforms a write
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
621 * of 4 bytes still requires a single read-modify-write operation.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
622 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
623 * This function is takes the identical parameters as the function above,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
624 * however it lays out the final array differently. Where the previous function
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
625 * treats the mpi_int as an byte array, this function treats it as an array of
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
626 * mp_digits where each digit is stored in big endian order.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
627 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
628 * since we need to interleave on a byte by byte basis, we need to collect
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
629 * several mpi structures together into a single PRUint32 before we write. We
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
630 * also need to make sure the PRUint32 is arranged so that the first value of
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
631 * the first array winds up in b[0]. This means construction of that PRUint32
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
632 * is endian specific (even though the layout of the mp_digits in the array
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
633 * is always big endian).
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
634 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
635 * The final data is stored as follows :
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
636 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
637 * Our same logical array p array, m is sizeof(mp_digit),
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
638 * N is still count and n is now b_size. If we define p[i].digit[j]0 as the
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
639 * most significant byte of the word p[i].digit[j], p[i].digit[j]1 as
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
640 * the next most significant byte of p[i].digit[j], ... and p[i].digit[j]m-1
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
641 * is the least significant byte.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
642 * Our array would look like:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
643 * p[0].digit[0]0 p[1].digit[0]0 ... p[N-2].digit[0]0 p[N-1].digit[0]0
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
644 * p[0].digit[0]1 p[1].digit[0]1 ... p[N-2].digit[0]1 p[N-1].digit[0]1
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
645 * . .
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
646 * p[0].digit[0]m-1 p[1].digit[0]m-1 ... p[N-2].digit[0]m-1 p[N-1].digit[0]m-1
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
647 * p[0].digit[1]0 p[1].digit[1]0 ... p[N-2].digit[1]0 p[N-1].digit[1]0
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
648 * . .
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
649 * . .
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
650 * p[0].digit[n-1]m-2 p[1].digit[n-1]m-2 ... p[N-2].digit[n-1]m-2 p[N-1].digit[n-1]m-2
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
651 * p[0].digit[n-1]m-1 p[1].digit[n-1]m-1 ... p[N-2].digit[n-1]m-1 p[N-1].digit[n-1]m-1
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
652 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
653 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
654 mp_err mpi_to_weave(const mp_int *a, unsigned char *b,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
655 mp_size b_size, mp_size count)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
656 {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
657 mp_size i;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
658 mp_digit *digitsa0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
659 mp_digit *digitsa1;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
660 mp_digit *digitsa2;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
661 mp_digit *digitsa3;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
662 mp_size useda0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
663 mp_size useda1;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
664 mp_size useda2;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
665 mp_size useda3;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
666 mp_weave_word *weaved = (mp_weave_word *)b;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
667
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
668 count = count/sizeof(mp_weave_word);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
669
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
670 /* this code pretty much depends on this ! */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
671 #if MP_ARGCHK == 2
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
672 assert(WEAVE_WORD_SIZE == 4);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
673 assert(sizeof(mp_weave_word) == 4);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
674 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
675
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
676 digitsa0 = MP_DIGITS(&a[0]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
677 digitsa1 = MP_DIGITS(&a[1]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
678 digitsa2 = MP_DIGITS(&a[2]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
679 digitsa3 = MP_DIGITS(&a[3]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
680 useda0 = MP_USED(&a[0]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
681 useda1 = MP_USED(&a[1]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
682 useda2 = MP_USED(&a[2]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
683 useda3 = MP_USED(&a[3]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
684
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
685 ARGCHK(MP_SIGN(&a[0]) == MP_ZPOS, MP_BADARG);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
686 ARGCHK(MP_SIGN(&a[1]) == MP_ZPOS, MP_BADARG);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
687 ARGCHK(MP_SIGN(&a[2]) == MP_ZPOS, MP_BADARG);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
688 ARGCHK(MP_SIGN(&a[3]) == MP_ZPOS, MP_BADARG);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
689 ARGCHK(useda0 <= b_size, MP_BADARG);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
690 ARGCHK(useda1 <= b_size, MP_BADARG);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
691 ARGCHK(useda2 <= b_size, MP_BADARG);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
692 ARGCHK(useda3 <= b_size, MP_BADARG);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
693
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
694 #define SAFE_FETCH(digit, used, word) ((word) < (used) ? (digit[word]) : 0)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
695
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
696 for (i=0; i < b_size; i++) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
697 mp_digit d0 = SAFE_FETCH(digitsa0,useda0,i);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
698 mp_digit d1 = SAFE_FETCH(digitsa1,useda1,i);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
699 mp_digit d2 = SAFE_FETCH(digitsa2,useda2,i);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
700 mp_digit d3 = SAFE_FETCH(digitsa3,useda3,i);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
701 register mp_weave_word acc;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
702
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
703 /*
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
704 * ONE_STEP takes the MSB of each of our current digits and places that
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
705 * byte in the appropriate position for writing to the weaved array.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
706 * On little endian:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
707 * b3 b2 b1 b0
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
708 * On big endian:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
709 * b0 b1 b2 b3
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
710 * When the data is written it would always wind up:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
711 * b[0] = b0
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
712 * b[1] = b1
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
713 * b[2] = b2
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
714 * b[3] = b3
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
715 *
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
716 * Once we've written the MSB, we shift the whole digit up left one
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
717 * byte, putting the Next Most Significant Byte in the MSB position,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
718 * so we we repeat the next one step that byte will be written.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
719 * NOTE: This code assumes sizeof(mp_weave_word) and MP_WEAVE_WORD_SIZE
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
720 * is 4.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
721 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
722 #ifdef MP_IS_LITTLE_ENDIAN
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
723 #define MPI_WEAVE_ONE_STEP \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
724 acc = (d0 >> (MP_DIGIT_BIT-8)) & 0x000000ff; d0 <<= 8; /*b0*/ \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
725 acc |= (d1 >> (MP_DIGIT_BIT-16)) & 0x0000ff00; d1 <<= 8; /*b1*/ \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
726 acc |= (d2 >> (MP_DIGIT_BIT-24)) & 0x00ff0000; d2 <<= 8; /*b2*/ \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
727 acc |= (d3 >> (MP_DIGIT_BIT-32)) & 0xff000000; d3 <<= 8; /*b3*/ \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
728 *weaved = acc; weaved += count;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
729 #else
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
730 #define MPI_WEAVE_ONE_STEP \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
731 acc = (d0 >> (MP_DIGIT_BIT-32)) & 0xff000000; d0 <<= 8; /*b0*/ \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
732 acc |= (d1 >> (MP_DIGIT_BIT-24)) & 0x00ff0000; d1 <<= 8; /*b1*/ \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
733 acc |= (d2 >> (MP_DIGIT_BIT-16)) & 0x0000ff00; d2 <<= 8; /*b2*/ \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
734 acc |= (d3 >> (MP_DIGIT_BIT-8)) & 0x000000ff; d3 <<= 8; /*b3*/ \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
735 *weaved = acc; weaved += count;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
736 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
737 switch (sizeof(mp_digit)) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
738 case 32:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
739 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
740 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
741 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
742 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
743 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
744 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
745 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
746 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
747 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
748 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
749 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
750 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
751 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
752 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
753 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
754 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
755 case 16:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
756 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
757 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
758 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
759 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
760 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
761 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
762 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
763 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
764 case 8:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
765 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
766 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
767 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
768 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
769 case 4:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
770 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
771 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
772 case 2:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
773 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
774 case 1:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
775 MPI_WEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
776 break;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
777 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
778 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
779
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
780 return MP_OKAY;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
781 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
782
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
783 /* reverse the operation above for one entry.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
784 * b points to the offset into the weave array of the power we are
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
785 * calculating */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
786 mp_err weave_to_mpi(mp_int *a, const unsigned char *b,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
787 mp_size b_size, mp_size count)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
788 {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
789 mp_digit *pb = MP_DIGITS(a);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
790 mp_digit *end = &pb[b_size];
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
791
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
792 MP_SIGN(a) = MP_ZPOS;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
793 MP_USED(a) = b_size;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
794
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
795 for (; pb < end; pb++) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
796 register mp_digit digit;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
797
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
798 digit = *b << 8; b += count;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
799 #define MPI_UNWEAVE_ONE_STEP digit |= *b; b += count; digit = digit << 8;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
800 switch (sizeof(mp_digit)) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
801 case 32:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
802 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
803 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
804 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
805 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
806 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
807 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
808 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
809 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
810 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
811 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
812 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
813 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
814 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
815 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
816 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
817 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
818 case 16:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
819 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
820 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
821 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
822 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
823 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
824 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
825 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
826 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
827 case 8:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
828 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
829 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
830 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
831 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
832 case 4:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
833 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
834 MPI_UNWEAVE_ONE_STEP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
835 case 2:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
836 break;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
837 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
838 digit |= *b; b += count;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
839
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
840 *pb = digit;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
841 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
842 s_mp_clamp(a);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
843 return MP_OKAY;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
844 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
845 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
846
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
847
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
848 #define SQR(a,b) \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
849 MP_CHECKOK( mp_sqr(a, b) );\
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
850 MP_CHECKOK( s_mp_redc(b, mmm) )
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
851
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
852 #if defined(MP_MONT_USE_MP_MUL)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
853 #define MUL_NOWEAVE(x,a,b) \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
854 MP_CHECKOK( mp_mul(a, x, b) ); \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
855 MP_CHECKOK( s_mp_redc(b, mmm) )
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
856 #else
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
857 #define MUL_NOWEAVE(x,a,b) \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
858 MP_CHECKOK( s_mp_mul_mont(a, x, b, mmm) )
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
859 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
860
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
861 #define MUL(x,a,b) \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
862 MP_CHECKOK( weave_to_mpi(&tmp, powers + (x), nLen, num_powers) ); \
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
863 MUL_NOWEAVE(&tmp,a,b)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
864
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
865 #define SWAPPA ptmp = pa1; pa1 = pa2; pa2 = ptmp
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
866 #define MP_ALIGN(x,y) ((((ptrdiff_t)(x))+((y)-1))&(((ptrdiff_t)0)-(y)))
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
867
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
868 /* Do modular exponentiation using integer multiply code. */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
869 mp_err mp_exptmod_safe_i(const mp_int * montBase,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
870 const mp_int * exponent,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
871 const mp_int * modulus,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
872 mp_int * result,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
873 mp_mont_modulus *mmm,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
874 int nLen,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
875 mp_size bits_in_exponent,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
876 mp_size window_bits,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
877 mp_size num_powers)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
878 {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
879 mp_int *pa1, *pa2, *ptmp;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
880 mp_size i;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
881 mp_size first_window;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
882 mp_err res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
883 int expOff;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
884 mp_int accum1, accum2, accum[WEAVE_WORD_SIZE];
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
885 mp_int tmp;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
886 unsigned char *powersArray;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
887 unsigned char *powers;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
888
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
889 MP_DIGITS(&accum1) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
890 MP_DIGITS(&accum2) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
891 MP_DIGITS(&accum[0]) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
892 MP_DIGITS(&accum[1]) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
893 MP_DIGITS(&accum[2]) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
894 MP_DIGITS(&accum[3]) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
895 MP_DIGITS(&tmp) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
896
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
897 powersArray = (unsigned char *)malloc(num_powers*(nLen*sizeof(mp_digit)+1));
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
898 if (powersArray == NULL) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
899 res = MP_MEM;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
900 goto CLEANUP;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
901 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
902
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
903 /* powers[i] = base ** (i); */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
904 powers = (unsigned char *)MP_ALIGN(powersArray,num_powers);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
905
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
906 /* grab the first window value. This allows us to preload accumulator1
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
907 * and save a conversion, some squares and a multiple*/
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
908 MP_CHECKOK( mpl_get_bits(exponent,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
909 bits_in_exponent-window_bits, window_bits) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
910 first_window = (mp_size)res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
911
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
912 MP_CHECKOK( mp_init_size(&accum1, 3 * nLen + 2) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
913 MP_CHECKOK( mp_init_size(&accum2, 3 * nLen + 2) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
914 MP_CHECKOK( mp_init_size(&tmp, 3 * nLen + 2) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
915
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
916 /* build the first WEAVE_WORD powers inline */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
917 /* if WEAVE_WORD_SIZE is not 4, this code will have to change */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
918 if (num_powers > 2) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
919 MP_CHECKOK( mp_init_size(&accum[0], 3 * nLen + 2) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
920 MP_CHECKOK( mp_init_size(&accum[1], 3 * nLen + 2) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
921 MP_CHECKOK( mp_init_size(&accum[2], 3 * nLen + 2) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
922 MP_CHECKOK( mp_init_size(&accum[3], 3 * nLen + 2) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
923 mp_set(&accum[0], 1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
924 MP_CHECKOK( s_mp_to_mont(&accum[0], mmm, &accum[0]) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
925 MP_CHECKOK( mp_copy(montBase, &accum[1]) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
926 SQR(montBase, &accum[2]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
927 MUL_NOWEAVE(montBase, &accum[2], &accum[3]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
928 MP_CHECKOK( mpi_to_weave(accum, powers, nLen, num_powers) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
929 if (first_window < 4) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
930 MP_CHECKOK( mp_copy(&accum[first_window], &accum1) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
931 first_window = num_powers;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
932 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
933 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
934 if (first_window == 0) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
935 mp_set(&accum1, 1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
936 MP_CHECKOK( s_mp_to_mont(&accum1, mmm, &accum1) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
937 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
938 /* assert first_window == 1? */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
939 MP_CHECKOK( mp_copy(montBase, &accum1) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
940 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
941 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
942
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
943 /*
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
944 * calculate all the powers in the powers array.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
945 * this adds 2**(k-1)-2 square operations over just calculating the
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
946 * odd powers where k is the window size in the two other mp_modexpt
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
947 * implementations in this file. We will get some of that
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
948 * back by not needing the first 'k' squares and one multiply for the
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
949 * first window */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
950 for (i = WEAVE_WORD_SIZE; i < num_powers; i++) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
951 int acc_index = i & (WEAVE_WORD_SIZE-1); /* i % WEAVE_WORD_SIZE */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
952 if ( i & 1 ) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
953 MUL_NOWEAVE(montBase, &accum[acc_index-1] , &accum[acc_index]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
954 /* we've filled the array do our 'per array' processing */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
955 if (acc_index == (WEAVE_WORD_SIZE-1)) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
956 MP_CHECKOK( mpi_to_weave(accum, powers + i - (WEAVE_WORD_SIZE-1),
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
957 nLen, num_powers) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
958
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
959 if (first_window <= i) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
960 MP_CHECKOK( mp_copy(&accum[first_window & (WEAVE_WORD_SIZE-1)],
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
961 &accum1) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
962 first_window = num_powers;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
963 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
964 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
965 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
966 /* up to 8 we can find 2^i-1 in the accum array, but at 8 we our source
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
967 * and target are the same so we need to copy.. After that, the
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
968 * value is overwritten, so we need to fetch it from the stored
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
969 * weave array */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
970 if (i > 2* WEAVE_WORD_SIZE) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
971 MP_CHECKOK(weave_to_mpi(&accum2, powers+i/2, nLen, num_powers));
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
972 SQR(&accum2, &accum[acc_index]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
973 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
974 int half_power_index = (i/2) & (WEAVE_WORD_SIZE-1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
975 if (half_power_index == acc_index) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
976 /* copy is cheaper than weave_to_mpi */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
977 MP_CHECKOK(mp_copy(&accum[half_power_index], &accum2));
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
978 SQR(&accum2,&accum[acc_index]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
979 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
980 SQR(&accum[half_power_index],&accum[acc_index]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
981 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
982 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
983 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
984 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
985 /* if the accum1 isn't set, Then there is something wrong with our logic
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
986 * above and is an internal programming error.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
987 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
988 #if MP_ARGCHK == 2
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
989 assert(MP_USED(&accum1) != 0);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
990 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
991
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
992 /* set accumulator to montgomery residue of 1 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
993 pa1 = &accum1;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
994 pa2 = &accum2;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
995
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
996 for (expOff = bits_in_exponent - window_bits*2; expOff >= 0; expOff -= window_bits) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
997 mp_size smallExp;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
998 MP_CHECKOK( mpl_get_bits(exponent, expOff, window_bits) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
999 smallExp = (mp_size)res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1000
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1001 /* handle unroll the loops */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1002 switch (window_bits) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1003 case 1:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1004 if (!smallExp) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1005 SQR(pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1006 } else if (smallExp & 1) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1007 SQR(pa1,pa2); MUL_NOWEAVE(montBase,pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1008 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1009 abort();
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1010 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1011 break;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1012 case 6:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1013 SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1014 /* fall through */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1015 case 4:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1016 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1017 MUL(smallExp, pa1,pa2); SWAPPA;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1018 break;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1019 case 5:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1020 SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1021 SQR(pa1,pa2); MUL(smallExp,pa2,pa1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1022 break;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1023 default:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1024 abort(); /* could do a loop? */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1025 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1026 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1027
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1028 res = s_mp_redc(pa1, mmm);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1029 mp_exch(pa1, result);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1030
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1031 CLEANUP:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1032 mp_clear(&accum1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1033 mp_clear(&accum2);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1034 mp_clear(&accum[0]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1035 mp_clear(&accum[1]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1036 mp_clear(&accum[2]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1037 mp_clear(&accum[3]);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1038 mp_clear(&tmp);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1039 /* PORT_Memset(powers,0,num_powers*nLen*sizeof(mp_digit)); */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1040 free(powersArray);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1041 return res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1042 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1043 #undef SQR
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1044 #undef MUL
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1045 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1046
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1047 mp_err mp_exptmod(const mp_int *inBase, const mp_int *exponent,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1048 const mp_int *modulus, mp_int *result)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1049 {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1050 const mp_int *base;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1051 mp_size bits_in_exponent, i, window_bits, odd_ints;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1052 mp_err res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1053 int nLen;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1054 mp_int montBase, goodBase;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1055 mp_mont_modulus mmm;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1056 #ifdef MP_USING_CACHE_SAFE_MOD_EXP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1057 static unsigned int max_window_bits;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1058 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1059
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1060 /* function for computing n0prime only works if n0 is odd */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1061 if (!mp_isodd(modulus))
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1062 return s_mp_exptmod(inBase, exponent, modulus, result);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1063
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1064 MP_DIGITS(&montBase) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1065 MP_DIGITS(&goodBase) = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1066
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1067 if (mp_cmp(inBase, modulus) < 0) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1068 base = inBase;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1069 } else {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1070 MP_CHECKOK( mp_init(&goodBase) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1071 base = &goodBase;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1072 MP_CHECKOK( mp_mod(inBase, modulus, &goodBase) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1073 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1074
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1075 nLen = MP_USED(modulus);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1076 MP_CHECKOK( mp_init_size(&montBase, 2 * nLen + 2) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1077
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1078 mmm.N = *modulus; /* a copy of the mp_int struct */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1079
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1080 /* compute n0', given n0, n0' = -(n0 ** -1) mod MP_RADIX
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1081 ** where n0 = least significant mp_digit of N, the modulus.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1082 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1083 mmm.n0prime = 0 - s_mp_invmod_radix( MP_DIGIT(modulus, 0) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1084
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1085 MP_CHECKOK( s_mp_to_mont(base, &mmm, &montBase) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1086
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1087 bits_in_exponent = mpl_significant_bits(exponent);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1088 #ifdef MP_USING_CACHE_SAFE_MOD_EXP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1089 if (mp_using_cache_safe_exp) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1090 if (bits_in_exponent > 780)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1091 window_bits = 6;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1092 else if (bits_in_exponent > 256)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1093 window_bits = 5;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1094 else if (bits_in_exponent > 20)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1095 window_bits = 4;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1096 /* RSA public key exponents are typically under 20 bits (common values
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1097 * are: 3, 17, 65537) and a 4-bit window is inefficient
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1098 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1099 else
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1100 window_bits = 1;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1101 } else
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1102 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1103 if (bits_in_exponent > 480)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1104 window_bits = 6;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1105 else if (bits_in_exponent > 160)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1106 window_bits = 5;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1107 else if (bits_in_exponent > 20)
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1108 window_bits = 4;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1109 /* RSA public key exponents are typically under 20 bits (common values
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1110 * are: 3, 17, 65537) and a 4-bit window is inefficient
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1111 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1112 else
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1113 window_bits = 1;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1114
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1115 #ifdef MP_USING_CACHE_SAFE_MOD_EXP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1116 /*
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1117 * clamp the window size based on
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1118 * the cache line size.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1119 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1120 if (!max_window_bits) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1121 unsigned long cache_size = s_mpi_getProcessorLineSize();
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1122 /* processor has no cache, use 'fast' code always */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1123 if (cache_size == 0) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1124 mp_using_cache_safe_exp = 0;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1125 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1126 if ((cache_size == 0) || (cache_size >= 64)) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1127 max_window_bits = 6;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1128 } else if (cache_size >= 32) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1129 max_window_bits = 5;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1130 } else if (cache_size >= 16) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1131 max_window_bits = 4;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1132 } else max_window_bits = 1; /* should this be an assert? */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1133 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1134
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1135 /* clamp the window size down before we caclulate bits_in_exponent */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1136 if (mp_using_cache_safe_exp) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1137 if (window_bits > max_window_bits) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1138 window_bits = max_window_bits;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1139 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1140 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1141 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1142
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1143 odd_ints = 1 << (window_bits - 1);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1144 i = bits_in_exponent % window_bits;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1145 if (i != 0) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1146 bits_in_exponent += window_bits - i;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1147 }
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1148
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1149 #ifdef MP_USING_MONT_MULF
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1150 if (mp_using_mont_mulf) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1151 MP_CHECKOK( s_mp_pad(&montBase, nLen) );
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1152 res = mp_exptmod_f(&montBase, exponent, modulus, result, &mmm, nLen,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1153 bits_in_exponent, window_bits, odd_ints);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1154 } else
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1155 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1156 #ifdef MP_USING_CACHE_SAFE_MOD_EXP
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1157 if (mp_using_cache_safe_exp) {
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1158 res = mp_exptmod_safe_i(&montBase, exponent, modulus, result, &mmm, nLen,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1159 bits_in_exponent, window_bits, 1 << window_bits);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1160 } else
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1161 #endif
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1162 res = mp_exptmod_i(&montBase, exponent, modulus, result, &mmm, nLen,
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1163 bits_in_exponent, window_bits, odd_ints);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1164
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1165 CLEANUP:
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1166 mp_clear(&montBase);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1167 mp_clear(&goodBase);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1168 /* Don't mp_clear mmm.N because it is merely a copy of modulus.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1169 ** Just zap it.
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1170 */
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1171 memset(&mmm, 0, sizeof mmm);
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1172 return res;
1e5118fa0cb1 This is NSS with a Cmake Buildsyste
Andre Heinecke <andre.heinecke@intevation.de>
parents:
diff changeset
1173 }
This site is hosted by Intevation GmbH (Datenschutzerklärung und Impressum | Privacy Policy and Imprint)