diff --git a/mpi/mpi-div.c b/mpi/mpi-div.c index eb621fe4..166ab875 100644 --- a/mpi/mpi-div.c +++ b/mpi/mpi-div.c @@ -1,357 +1,360 @@ /* mpi-div.c - MPI functions * Copyright (C) 1994, 1996, 1998, 2001, 2002, * 2003 Free Software Foundation, Inc. * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 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 * * Note: This code is heavily based on the GNU MP Library. * Actually it's the same code with only minor changes in the * way the data is stored; this is to support the abstraction * of an optional secure memory allocation which may be used * to avoid revealing of sensitive data due to paging etc. */ #include #include #include #include "mpi-internal.h" #include "longlong.h" #include "g10lib.h" void _gcry_mpi_fdiv_r( gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor ) { int divisor_sign = divisor->sign; gcry_mpi_t temp_divisor = NULL; /* We need the original value of the divisor after the remainder has been * preliminary calculated. We have to copy it to temporary space if it's * the same variable as REM. */ if( rem == divisor ) { temp_divisor = mpi_copy( divisor ); divisor = temp_divisor; } _gcry_mpi_tdiv_r( rem, dividend, divisor ); if( ((divisor_sign?1:0) ^ (dividend->sign?1:0)) && rem->nlimbs ) mpi_add (rem, rem, divisor); if( temp_divisor ) mpi_free(temp_divisor); } /**************** * Division rounding the quotient towards -infinity. * The remainder gets the same sign as the denominator. * rem is optional */ unsigned long _gcry_mpi_fdiv_r_ui( gcry_mpi_t rem, gcry_mpi_t dividend, unsigned long divisor ) { mpi_limb_t rlimb; rlimb = _gcry_mpih_mod_1( dividend->d, dividend->nlimbs, divisor ); if( rlimb && dividend->sign ) rlimb = divisor - rlimb; if( rem ) { rem->d[0] = rlimb; rem->nlimbs = rlimb? 1:0; } return rlimb; } void _gcry_mpi_fdiv_q( gcry_mpi_t quot, gcry_mpi_t dividend, gcry_mpi_t divisor ) { gcry_mpi_t tmp = mpi_alloc( mpi_get_nlimbs(quot) ); _gcry_mpi_fdiv_qr( quot, tmp, dividend, divisor); mpi_free(tmp); } void _gcry_mpi_fdiv_qr( gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor ) { int divisor_sign = divisor->sign; gcry_mpi_t temp_divisor = NULL; if( quot == divisor || rem == divisor ) { temp_divisor = mpi_copy( divisor ); divisor = temp_divisor; } _gcry_mpi_tdiv_qr( quot, rem, dividend, divisor ); if( (divisor_sign ^ dividend->sign) && rem->nlimbs ) { mpi_sub_ui( quot, quot, 1 ); mpi_add( rem, rem, divisor); } if( temp_divisor ) mpi_free(temp_divisor); } /* If den == quot, den needs temporary storage. * If den == rem, den needs temporary storage. * If num == quot, num needs temporary storage. * If den has temporary storage, it can be normalized while being copied, * i.e no extra storage should be allocated. */ void _gcry_mpi_tdiv_r( gcry_mpi_t rem, gcry_mpi_t num, gcry_mpi_t den) { _gcry_mpi_tdiv_qr(NULL, rem, num, den ); } void _gcry_mpi_tdiv_qr( gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t num, gcry_mpi_t den) { mpi_ptr_t np, dp; mpi_ptr_t qp, rp; mpi_size_t nsize = num->nlimbs; mpi_size_t dsize = den->nlimbs; mpi_size_t qsize, rsize; mpi_size_t sign_remainder = num->sign; mpi_size_t sign_quotient = num->sign ^ den->sign; unsigned normalization_steps; mpi_limb_t q_limb; mpi_ptr_t marker[5]; unsigned int marker_nlimbs[5]; int markidx=0; /* Ensure space is enough for quotient and remainder. * We need space for an extra limb in the remainder, because it's * up-shifted (normalized) below. */ rsize = nsize + 1; mpi_resize( rem, rsize); qsize = rsize - dsize; /* qsize cannot be bigger than this. */ if( qsize <= 0 ) { if( num != rem ) { rem->nlimbs = num->nlimbs; rem->sign = num->sign; MPN_COPY(rem->d, num->d, nsize); } if( quot ) { /* This needs to follow the assignment to rem, in case the * numerator and quotient are the same. */ quot->nlimbs = 0; quot->sign = 0; } return; } if( quot ) mpi_resize( quot, qsize); + if (!dsize) + _gcry_divide_by_zero(); + /* Read pointers here, when reallocation is finished. */ np = num->d; dp = den->d; rp = rem->d; /* Optimize division by a single-limb divisor. */ if( dsize == 1 ) { mpi_limb_t rlimb; if( quot ) { qp = quot->d; rlimb = _gcry_mpih_divmod_1( qp, np, nsize, dp[0] ); qsize -= qp[qsize - 1] == 0; quot->nlimbs = qsize; quot->sign = sign_quotient; } else rlimb = _gcry_mpih_mod_1( np, nsize, dp[0] ); rp[0] = rlimb; rsize = rlimb != 0?1:0; rem->nlimbs = rsize; rem->sign = sign_remainder; return; } if( quot ) { qp = quot->d; /* Make sure QP and NP point to different objects. Otherwise the * numerator would be gradually overwritten by the quotient limbs. */ if(qp == np) { /* Copy NP object to temporary space. */ marker_nlimbs[markidx] = nsize; np = marker[markidx++] = mpi_alloc_limb_space(nsize, mpi_is_secure(quot)); MPN_COPY(np, qp, nsize); } } else /* Put quotient at top of remainder. */ qp = rp + dsize; count_leading_zeros( normalization_steps, dp[dsize - 1] ); /* Normalize the denominator, i.e. make its most significant bit set by * shifting it NORMALIZATION_STEPS bits to the left. Also shift the * numerator the same number of steps (to keep the quotient the same!). */ if( normalization_steps ) { mpi_ptr_t tp; mpi_limb_t nlimb; /* Shift up the denominator setting the most significant bit of * the most significant word. Use temporary storage not to clobber * the original contents of the denominator. */ marker_nlimbs[markidx] = dsize; tp = marker[markidx++] = mpi_alloc_limb_space(dsize,mpi_is_secure(den)); _gcry_mpih_lshift( tp, dp, dsize, normalization_steps ); dp = tp; /* Shift up the numerator, possibly introducing a new most * significant word. Move the shifted numerator in the remainder * meanwhile. */ nlimb = _gcry_mpih_lshift(rp, np, nsize, normalization_steps); if( nlimb ) { rp[nsize] = nlimb; rsize = nsize + 1; } else rsize = nsize; } else { /* The denominator is already normalized, as required. Copy it to * temporary space if it overlaps with the quotient or remainder. */ if( dp == rp || (quot && (dp == qp))) { mpi_ptr_t tp; marker_nlimbs[markidx] = dsize; tp = marker[markidx++] = mpi_alloc_limb_space(dsize, mpi_is_secure(den)); MPN_COPY( tp, dp, dsize ); dp = tp; } /* Move the numerator to the remainder. */ if( rp != np ) MPN_COPY(rp, np, nsize); rsize = nsize; } q_limb = _gcry_mpih_divrem( qp, 0, rp, rsize, dp, dsize ); if( quot ) { qsize = rsize - dsize; if(q_limb) { qp[qsize] = q_limb; qsize += 1; } quot->nlimbs = qsize; quot->sign = sign_quotient; } rsize = dsize; MPN_NORMALIZE (rp, rsize); if( normalization_steps && rsize ) { _gcry_mpih_rshift(rp, rp, rsize, normalization_steps); rsize -= rp[rsize - 1] == 0?1:0; } rem->nlimbs = rsize; rem->sign = sign_remainder; while( markidx ) { markidx--; _gcry_mpi_free_limb_space (marker[markidx], marker_nlimbs[markidx]); } } void _gcry_mpi_tdiv_q_2exp( gcry_mpi_t w, gcry_mpi_t u, unsigned int count ) { mpi_size_t usize, wsize; mpi_size_t limb_cnt; usize = u->nlimbs; limb_cnt = count / BITS_PER_MPI_LIMB; wsize = usize - limb_cnt; if( limb_cnt >= usize ) w->nlimbs = 0; else { mpi_ptr_t wp; mpi_ptr_t up; RESIZE_IF_NEEDED( w, wsize ); wp = w->d; up = u->d; count %= BITS_PER_MPI_LIMB; if( count ) { _gcry_mpih_rshift( wp, up + limb_cnt, wsize, count ); wsize -= !wp[wsize - 1]; } else { MPN_COPY_INCR( wp, up + limb_cnt, wsize); } w->nlimbs = wsize; } } /**************** * Check whether dividend is divisible by divisor * (note: divisor must fit into a limb) */ int _gcry_mpi_divisible_ui(gcry_mpi_t dividend, unsigned long divisor ) { return !_gcry_mpih_mod_1( dividend->d, dividend->nlimbs, divisor ); } void _gcry_mpi_div (gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor, int round) { if (!round) { if (!rem) { gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs(quot)); _gcry_mpi_tdiv_qr (quot, tmp, dividend, divisor); mpi_free (tmp); } else _gcry_mpi_tdiv_qr (quot, rem, dividend, divisor); } else if (round < 0) { if (!rem) _gcry_mpi_fdiv_q (quot, dividend, divisor); else if (!quot) _gcry_mpi_fdiv_r (rem, dividend, divisor); else _gcry_mpi_fdiv_qr (quot, rem, dividend, divisor); } else log_bug ("mpi rounding to ceiling not yet implemented\n"); }