trustbridge/nss-cmake-static: nss/lib/freebl/mpi/mpmontg.c annotate

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 (2i + 1); /
1e5118fa0cb1 This is NSS with a Cmake Buildsyste Andre Heinecke <andre.heinecke@intevation.de> parents: diff changeset	360 /* oddPowers[i] = base ** (2i + 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_powersnLensizeof(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 }

Mercurial > trustbridge > nss-cmake-static

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