diff options
author | Werner Koch <wk@gnupg.org> | 2008-12-02 11:38:43 +0000 |
---|---|---|
committer | Werner Koch <wk@gnupg.org> | 2008-12-02 11:38:43 +0000 |
commit | 1542e469807398149e2cab3b8f9856121493637b (patch) | |
tree | 64a290865be627f84a5fa9957c6ecb3fb56fdaab /mpi/mpi-pow.c | |
parent | ee188790d59e674b31b964709971d0c94508c152 (diff) | |
download | libgcrypt-1542e469807398149e2cab3b8f9856121493637b.tar.gz |
Re-indented some code.
Diffstat (limited to 'mpi/mpi-pow.c')
-rw-r--r-- | mpi/mpi-pow.c | 525 |
1 files changed, 279 insertions, 246 deletions
diff --git a/mpi/mpi-pow.c b/mpi/mpi-pow.c index 975e4aa3..dc75df52 100644 --- a/mpi/mpi-pow.c +++ b/mpi/mpi-pow.c @@ -1,5 +1,6 @@ -/* mpi-pow.c - MPI functions - * Copyright (C) 1994, 1996, 1998, 2000, 2002, 2003 Free Software Foundation, Inc. +/* mpi-pow.c - MPI functions for exponentiation + * Copyright (C) 1994, 1996, 1998, 2000, 2002 + * 2003 Free Software Foundation, Inc. * * This file is part of Libgcrypt. * @@ -14,8 +15,7 @@ * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA + * License along with this program; if not, see <http://www.gnu.org/licenses/>. * * Note: This code is heavily based on the GNU MP Library. * Actually it's the same code with only minor changes in the @@ -37,265 +37,298 @@ * RES = BASE ^ EXPO mod MOD */ void -gcry_mpi_powm( gcry_mpi_t res, gcry_mpi_t base, gcry_mpi_t expo, gcry_mpi_t mod) +gcry_mpi_powm (gcry_mpi_t res, + gcry_mpi_t base, gcry_mpi_t expo, gcry_mpi_t mod) { - mpi_ptr_t rp, ep, mp, bp; - mpi_size_t esize, msize, bsize, rsize; - int msign, bsign, rsign; - int esec, msec, bsec, rsec; - mpi_size_t size; - int mod_shift_cnt; - int negative_result; - mpi_ptr_t mp_marker=NULL, bp_marker=NULL, ep_marker=NULL; - mpi_ptr_t xp_marker=NULL; - unsigned int mp_nlimbs = 0, bp_nlimbs = 0, ep_nlimbs = 0; - unsigned int xp_nlimbs = 0; - int assign_rp = 0; - mpi_ptr_t tspace = NULL; - mpi_size_t tsize=0; /* to avoid compiler warning */ - /* fixme: we should check that the warning is void*/ - - esize = expo->nlimbs; - msize = mod->nlimbs; - size = 2 * msize; - msign = mod->sign; - - esec = mpi_is_secure(expo); - msec = mpi_is_secure(mod); - bsec = mpi_is_secure(base); - rsec = mpi_is_secure(res); - - rp = res->d; - ep = expo->d; - - if( !msize ) - msize = 1 / msize; /* provoke a signal */ - - if( !esize ) { - /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 - * depending on if MOD equals 1. */ - rp[0] = 1; - res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1; - res->sign = 0; - goto leave; + mpi_ptr_t rp, ep, mp, bp; + mpi_size_t esize, msize, bsize, rsize; + int msign, bsign, rsign; + int esec, msec, bsec, rsec; + mpi_size_t size; + int mod_shift_cnt; + int negative_result; + mpi_ptr_t mp_marker = NULL; + mpi_ptr_t bp_marker = NULL; + mpi_ptr_t ep_marker = NULL; + mpi_ptr_t xp_marker = NULL; + unsigned int mp_nlimbs = 0; + unsigned int bp_nlimbs = 0; + unsigned int ep_nlimbs = 0; + unsigned int xp_nlimbs = 0; + int assign_rp = 0; + mpi_ptr_t tspace = NULL; + mpi_size_t tsize = 0; + + + esize = expo->nlimbs; + msize = mod->nlimbs; + size = 2 * msize; + msign = mod->sign; + + esec = mpi_is_secure(expo); + msec = mpi_is_secure(mod); + bsec = mpi_is_secure(base); + rsec = mpi_is_secure(res); + + rp = res->d; + ep = expo->d; + + if (!msize) + msize = 1 / msize; /* Provoke a signal. */ + + if (!esize) + { + /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 depending + on if MOD equals 1. */ + rp[0] = 1; + res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1; + res->sign = 0; + goto leave; } - /* Normalize MOD (i.e. make its most significant bit set) as required by - * mpn_divrem. This will make the intermediate values in the calculation - * slightly larger, but the correct result is obtained after a final - * reduction using the original MOD value. */ - mp_nlimbs = msec? msize:0; - mp = mp_marker = mpi_alloc_limb_space(msize, msec); - count_leading_zeros( mod_shift_cnt, mod->d[msize-1] ); - if( mod_shift_cnt ) - _gcry_mpih_lshift( mp, mod->d, msize, mod_shift_cnt ); - else - MPN_COPY( mp, mod->d, msize ); - - bsize = base->nlimbs; - bsign = base->sign; - if( bsize > msize ) { /* The base is larger than the module. Reduce it. */ - /* Allocate (BSIZE + 1) with space for remainder and quotient. - * (The quotient is (bsize - msize + 1) limbs.) */ - bp_nlimbs = bsec ? (bsize + 1):0; - bp = bp_marker = mpi_alloc_limb_space( bsize + 1, bsec ); - MPN_COPY( bp, base->d, bsize ); - /* We don't care about the quotient, store it above the remainder, - * at BP + MSIZE. */ - _gcry_mpih_divrem( bp + msize, 0, bp, bsize, mp, msize ); - bsize = msize; - /* Canonicalize the base, since we are going to multiply with it - * quite a few times. */ - MPN_NORMALIZE( bp, bsize ); + /* Normalize MOD (i.e. make its most significant bit set) as + required by mpn_divrem. This will make the intermediate values + in the calculation slightly larger, but the correct result is + obtained after a final reduction using the original MOD value. */ + mp_nlimbs = msec? msize:0; + mp = mp_marker = mpi_alloc_limb_space(msize, msec); + count_leading_zeros (mod_shift_cnt, mod->d[msize-1]); + if (mod_shift_cnt) + _gcry_mpih_lshift (mp, mod->d, msize, mod_shift_cnt); + else + MPN_COPY( mp, mod->d, msize ); + + bsize = base->nlimbs; + bsign = base->sign; + if (bsize > msize) + { + /* The base is larger than the module. Reduce it. + + Allocate (BSIZE + 1) with space for remainder and quotient. + (The quotient is (bsize - msize + 1) limbs.) */ + bp_nlimbs = bsec ? (bsize + 1):0; + bp = bp_marker = mpi_alloc_limb_space( bsize + 1, bsec ); + MPN_COPY ( bp, base->d, bsize ); + /* We don't care about the quotient, store it above the + * remainder, at BP + MSIZE. */ + _gcry_mpih_divrem( bp + msize, 0, bp, bsize, mp, msize ); + bsize = msize; + /* Canonicalize the base, since we are going to multiply with it + quite a few times. */ + MPN_NORMALIZE( bp, bsize ); } - else - bp = base->d; + else + bp = base->d; - if( !bsize ) { - res->nlimbs = 0; - res->sign = 0; - goto leave; + if (!bsize) + { + res->nlimbs = 0; + res->sign = 0; + goto leave; } - if( res->alloced < size ) { - /* We have to allocate more space for RES. If any of the input - * parameters are identical to RES, defer deallocation of the old - * space. */ - if( rp == ep || rp == mp || rp == bp ) { + if (res->alloced < size) + { + /* We have to allocate more space for RES. If any of the input + parameters are identical to RES, defer deallocation of the + old space. */ + if ( rp == ep || rp == mp || rp == bp ) + { rp = mpi_alloc_limb_space( size, rsec ); assign_rp = 1; - } - else { + } + else + { mpi_resize( res, size ); rp = res->d; - } + } } - else { /* Make BASE, EXPO and MOD not overlap with RES. */ - if( rp == bp ) { - /* RES and BASE are identical. Allocate temp. space for BASE. */ - gcry_assert (!bp_marker); - bp_nlimbs = bsec? bsize:0; - bp = bp_marker = mpi_alloc_limb_space( bsize, bsec ); - MPN_COPY(bp, rp, bsize); + else + { + /* Make BASE, EXPO and MOD not overlap with RES. */ + if ( rp == bp ) + { + /* RES and BASE are identical. Allocate temp. space for BASE. */ + gcry_assert (!bp_marker); + bp_nlimbs = bsec? bsize:0; + bp = bp_marker = mpi_alloc_limb_space( bsize, bsec ); + MPN_COPY(bp, rp, bsize); } - if( rp == ep ) { - /* RES and EXPO are identical. Allocate temp. space for EXPO. */ - ep_nlimbs = esec? esize:0; - ep = ep_marker = mpi_alloc_limb_space( esize, esec ); - MPN_COPY(ep, rp, esize); + if ( rp == ep ) + { + /* RES and EXPO are identical. Allocate temp. space for EXPO. */ + ep_nlimbs = esec? esize:0; + ep = ep_marker = mpi_alloc_limb_space( esize, esec ); + MPN_COPY(ep, rp, esize); } - if( rp == mp ) { - /* RES and MOD are identical. Allocate temporary space for MOD.*/ - gcry_assert (!mp_marker); - mp_nlimbs = msec?msize:0; - mp = mp_marker = mpi_alloc_limb_space( msize, msec ); - MPN_COPY(mp, rp, msize); + if ( rp == mp ) + { + /* RES and MOD are identical. Allocate temporary space for MOD.*/ + gcry_assert (!mp_marker); + mp_nlimbs = msec?msize:0; + mp = mp_marker = mpi_alloc_limb_space( msize, msec ); + MPN_COPY(mp, rp, msize); } } - - MPN_COPY( rp, bp, bsize ); - rsize = bsize; - rsign = bsign; - + + MPN_COPY ( rp, bp, bsize ); + rsize = bsize; + rsign = bsign; + + { + mpi_size_t i; + mpi_ptr_t xp; + int c; + mpi_limb_t e; + mpi_limb_t carry_limb; + struct karatsuba_ctx karactx; + + xp_nlimbs = msec? (2 * (msize + 1)):0; + xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec ); + + memset( &karactx, 0, sizeof karactx ); + negative_result = (ep[0] & 1) && base->sign; + + i = esize - 1; + e = ep[i]; + count_leading_zeros (c, e); + e = (e << c) << 1; /* Shift the expo bits to the left, lose msb. */ + c = BITS_PER_MPI_LIMB - 1 - c; + + /* Main loop. + + Make the result be pointed to alternately by XP and RP. This + helps us avoid block copying, which would otherwise be + necessary with the overlap restrictions of + _gcry_mpih_divmod. With 50% probability the result after this + loop will be in the area originally pointed by RP (==RES->d), + and with 50% probability in the area originally pointed to by XP. */ + for (;;) + { + while (c) + { + mpi_ptr_t tp; + mpi_size_t xsize; + + /*mpih_mul_n(xp, rp, rp, rsize);*/ + if ( rsize < KARATSUBA_THRESHOLD ) + _gcry_mpih_sqr_n_basecase( xp, rp, rsize ); + else + { + if ( !tspace ) + { + tsize = 2 * rsize; + tspace = mpi_alloc_limb_space( tsize, 0 ); + } + else if ( tsize < (2*rsize) ) + { + _gcry_mpi_free_limb_space (tspace, 0); + tsize = 2 * rsize; + tspace = mpi_alloc_limb_space (tsize, 0 ); + } + _gcry_mpih_sqr_n (xp, rp, rsize, tspace); + } + + xsize = 2 * rsize; + if ( xsize > msize ) + { + _gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize); + xsize = msize; + } + + tp = rp; rp = xp; xp = tp; + rsize = xsize; + + if ( (mpi_limb_signed_t)e < 0 ) + { + /*mpih_mul( xp, rp, rsize, bp, bsize );*/ + if( bsize < KARATSUBA_THRESHOLD ) + _gcry_mpih_mul ( xp, rp, rsize, bp, bsize ); + else + _gcry_mpih_mul_karatsuba_case (xp, rp, rsize, bp, bsize, + &karactx); + + xsize = rsize + bsize; + if ( xsize > msize ) + { + _gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize); + xsize = msize; + } + + tp = rp; rp = xp; xp = tp; + rsize = xsize; + } + e <<= 1; + c--; + } + + i--; + if ( i < 0 ) + break; + e = ep[i]; + c = BITS_PER_MPI_LIMB; + } + + /* We shifted MOD, the modulo reduction argument, left + MOD_SHIFT_CNT steps. Adjust the result by reducing it with the + original MOD. + + Also make sure the result is put in RES->d (where it already + might be, see above). */ + if ( mod_shift_cnt ) + { + carry_limb = _gcry_mpih_lshift( res->d, rp, rsize, mod_shift_cnt); + rp = res->d; + if ( carry_limb ) + { + rp[rsize] = carry_limb; + rsize++; + } + } + else + { + MPN_COPY( res->d, rp, rsize); + rp = res->d; + } + + if ( rsize >= msize ) + { + _gcry_mpih_divrem(rp + msize, 0, rp, rsize, mp, msize); + rsize = msize; + } + + /* Remove any leading zero words from the result. */ + if ( mod_shift_cnt ) + _gcry_mpih_rshift( rp, rp, rsize, mod_shift_cnt); + MPN_NORMALIZE (rp, rsize); + + _gcry_mpih_release_karatsuba_ctx (&karactx ); + } + + if ( negative_result && rsize ) { - mpi_size_t i; - mpi_ptr_t xp; - int c; - mpi_limb_t e; - mpi_limb_t carry_limb; - struct karatsuba_ctx karactx; - - xp_nlimbs = msec? (2 * (msize + 1)):0; - xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec ); - - memset( &karactx, 0, sizeof karactx ); - negative_result = (ep[0] & 1) && base->sign; - - i = esize - 1; - e = ep[i]; - count_leading_zeros (c, e); - e = (e << c) << 1; /* shift the expo bits to the left, lose msb */ - c = BITS_PER_MPI_LIMB - 1 - c; - - /* Main loop. - * - * Make the result be pointed to alternately by XP and RP. This - * helps us avoid block copying, which would otherwise be necessary - * with the overlap restrictions of _gcry_mpih_divmod. With 50% probability - * the result after this loop will be in the area originally pointed - * by RP (==RES->d), and with 50% probability in the area originally - * pointed to by XP. - */ - - for(;;) { - while( c ) { - mpi_ptr_t tp; - mpi_size_t xsize; - - /*mpih_mul_n(xp, rp, rp, rsize);*/ - if( rsize < KARATSUBA_THRESHOLD ) - _gcry_mpih_sqr_n_basecase( xp, rp, rsize ); - else { - if( !tspace ) { - tsize = 2 * rsize; - tspace = mpi_alloc_limb_space( tsize, 0 ); - } - else if( tsize < (2*rsize) ) { - _gcry_mpi_free_limb_space (tspace, 0); - tsize = 2 * rsize; - tspace = mpi_alloc_limb_space( tsize, 0 ); - } - _gcry_mpih_sqr_n( xp, rp, rsize, tspace ); - } - - xsize = 2 * rsize; - if( xsize > msize ) { - _gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize); - xsize = msize; - } - - tp = rp; rp = xp; xp = tp; - rsize = xsize; - - if( (mpi_limb_signed_t)e < 0 ) { - /*mpih_mul( xp, rp, rsize, bp, bsize );*/ - if( bsize < KARATSUBA_THRESHOLD ) { - _gcry_mpih_mul( xp, rp, rsize, bp, bsize ); - } - else { - _gcry_mpih_mul_karatsuba_case( - xp, rp, rsize, bp, bsize, &karactx ); - } - - xsize = rsize + bsize; - if( xsize > msize ) { - _gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize); - xsize = msize; - } - - tp = rp; rp = xp; xp = tp; - rsize = xsize; - } - e <<= 1; - c--; - } - - i--; - if( i < 0 ) - break; - e = ep[i]; - c = BITS_PER_MPI_LIMB; - } - - /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT - * steps. Adjust the result by reducing it with the original MOD. - * - * Also make sure the result is put in RES->d (where it already - * might be, see above). - */ - if( mod_shift_cnt ) { - carry_limb = _gcry_mpih_lshift( res->d, rp, rsize, mod_shift_cnt); - rp = res->d; - if( carry_limb ) { - rp[rsize] = carry_limb; - rsize++; - } - } - else { - MPN_COPY( res->d, rp, rsize); - rp = res->d; - } - - if( rsize >= msize ) { - _gcry_mpih_divrem(rp + msize, 0, rp, rsize, mp, msize); - rsize = msize; - } - - /* Remove any leading zero words from the result. */ - if( mod_shift_cnt ) - _gcry_mpih_rshift( rp, rp, rsize, mod_shift_cnt); - MPN_NORMALIZE (rp, rsize); - - _gcry_mpih_release_karatsuba_ctx( &karactx ); + if ( mod_shift_cnt ) + _gcry_mpih_rshift( mp, mp, msize, mod_shift_cnt); + _gcry_mpih_sub( rp, mp, msize, rp, rsize); + rsize = msize; + rsign = msign; + MPN_NORMALIZE(rp, rsize); } - - if( negative_result && rsize ) { - if( mod_shift_cnt ) - _gcry_mpih_rshift( mp, mp, msize, mod_shift_cnt); - _gcry_mpih_sub( rp, mp, msize, rp, rsize); - rsize = msize; - rsign = msign; - MPN_NORMALIZE(rp, rsize); - } - res->nlimbs = rsize; - res->sign = rsign; - - leave: - if( assign_rp ) _gcry_mpi_assign_limb_space( res, rp, size ); - if( mp_marker ) _gcry_mpi_free_limb_space( mp_marker, mp_nlimbs ); - if( bp_marker ) _gcry_mpi_free_limb_space( bp_marker, bp_nlimbs ); - if( ep_marker ) _gcry_mpi_free_limb_space( ep_marker, ep_nlimbs ); - if( xp_marker ) _gcry_mpi_free_limb_space( xp_marker, xp_nlimbs ); - if( tspace ) _gcry_mpi_free_limb_space( tspace, 0 ); + res->nlimbs = rsize; + res->sign = rsign; + + leave: + if (assign_rp) + _gcry_mpi_assign_limb_space( res, rp, size ); + if (mp_marker) + _gcry_mpi_free_limb_space( mp_marker, mp_nlimbs ); + if (bp_marker) + _gcry_mpi_free_limb_space( bp_marker, bp_nlimbs ); + if (ep_marker) + _gcry_mpi_free_limb_space( ep_marker, ep_nlimbs ); + if (xp_marker) + _gcry_mpi_free_limb_space( xp_marker, xp_nlimbs ); + if (tspace) + _gcry_mpi_free_limb_space( tspace, 0 ); } |