LCOV - code coverage report
Current view: top level - mpi - mpi-div.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 127 154 82.5 %
Date: 2016-09-12 12:56:58 Functions: 9 9 100.0 %

          Line data    Source code
       1             : /* mpi-div.c  -  MPI functions
       2             :  * Copyright (C) 1994, 1996, 1998, 2001, 2002,
       3             :  *               2003 Free Software Foundation, Inc.
       4             :  *
       5             :  * This file is part of Libgcrypt.
       6             :  *
       7             :  * Libgcrypt is free software; you can redistribute it and/or modify
       8             :  * it under the terms of the GNU Lesser General Public License as
       9             :  * published by the Free Software Foundation; either version 2.1 of
      10             :  * the License, or (at your option) any later version.
      11             :  *
      12             :  * Libgcrypt is distributed in the hope that it will be useful,
      13             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      14             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15             :  * GNU Lesser General Public License for more details.
      16             :  *
      17             :  * You should have received a copy of the GNU Lesser General Public
      18             :  * License along with this program; if not, write to the Free Software
      19             :  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
      20             :  *
      21             :  * Note: This code is heavily based on the GNU MP Library.
      22             :  *       Actually it's the same code with only minor changes in the
      23             :  *       way the data is stored; this is to support the abstraction
      24             :  *       of an optional secure memory allocation which may be used
      25             :  *       to avoid revealing of sensitive data due to paging etc.
      26             :  */
      27             : 
      28             : #include <config.h>
      29             : #include <stdio.h>
      30             : #include <stdlib.h>
      31             : #include "mpi-internal.h"
      32             : #include "longlong.h"
      33             : #include "g10lib.h"
      34             : 
      35             : 
      36             : void
      37    38033152 : _gcry_mpi_fdiv_r( gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor )
      38             : {
      39    38033152 :     int divisor_sign = divisor->sign;
      40    38033152 :     gcry_mpi_t temp_divisor = NULL;
      41             : 
      42             :     /* We need the original value of the divisor after the remainder has been
      43             :      * preliminary calculated.  We have to copy it to temporary space if it's
      44             :      * the same variable as REM.  */
      45    38033152 :     if( rem == divisor ) {
      46        5198 :         temp_divisor = mpi_copy( divisor );
      47        5198 :         divisor = temp_divisor;
      48             :     }
      49             : 
      50    38033152 :     _gcry_mpi_tdiv_r( rem, dividend, divisor );
      51             : 
      52    38033152 :     if( ((divisor_sign?1:0) ^ (dividend->sign?1:0)) && rem->nlimbs )
      53          46 :         mpi_add (rem, rem, divisor);
      54             : 
      55    38033152 :     if( temp_divisor )
      56        5198 :         mpi_free(temp_divisor);
      57    38033152 : }
      58             : 
      59             : 
      60             : 
      61             : /****************
      62             :  * Division rounding the quotient towards -infinity.
      63             :  * The remainder gets the same sign as the denominator.
      64             :  * rem is optional
      65             :  */
      66             : 
      67             : ulong
      68      347360 : _gcry_mpi_fdiv_r_ui( gcry_mpi_t rem, gcry_mpi_t dividend, ulong divisor )
      69             : {
      70             :     mpi_limb_t rlimb;
      71             : 
      72      347360 :     rlimb = _gcry_mpih_mod_1( dividend->d, dividend->nlimbs, divisor );
      73      347360 :     if( rlimb && dividend->sign )
      74           0 :         rlimb = divisor - rlimb;
      75             : 
      76      347360 :     if( rem ) {
      77           0 :         rem->d[0] = rlimb;
      78           0 :         rem->nlimbs = rlimb? 1:0;
      79             :     }
      80      347360 :     return rlimb;
      81             : }
      82             : 
      83             : 
      84             : void
      85         214 : _gcry_mpi_fdiv_q( gcry_mpi_t quot, gcry_mpi_t dividend, gcry_mpi_t divisor )
      86             : {
      87         214 :     gcry_mpi_t tmp = mpi_alloc( mpi_get_nlimbs(quot) );
      88         214 :     _gcry_mpi_fdiv_qr( quot, tmp, dividend, divisor);
      89         214 :     mpi_free(tmp);
      90         214 : }
      91             : 
      92             : void
      93         214 : _gcry_mpi_fdiv_qr( gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor )
      94             : {
      95         214 :     int divisor_sign = divisor->sign;
      96         214 :     gcry_mpi_t temp_divisor = NULL;
      97             : 
      98         214 :     if( quot == divisor || rem == divisor ) {
      99           0 :         temp_divisor = mpi_copy( divisor );
     100           0 :         divisor = temp_divisor;
     101             :     }
     102             : 
     103         214 :     _gcry_mpi_tdiv_qr( quot, rem, dividend, divisor );
     104             : 
     105         214 :     if( (divisor_sign ^ dividend->sign) && rem->nlimbs ) {
     106           0 :         mpi_sub_ui( quot, quot, 1 );
     107           0 :         mpi_add( rem, rem, divisor);
     108             :     }
     109             : 
     110         214 :     if( temp_divisor )
     111           0 :         mpi_free(temp_divisor);
     112         214 : }
     113             : 
     114             : 
     115             : /* If den == quot, den needs temporary storage.
     116             :  * If den == rem, den needs temporary storage.
     117             :  * If num == quot, num needs temporary storage.
     118             :  * If den has temporary storage, it can be normalized while being copied,
     119             :  *   i.e no extra storage should be allocated.
     120             :  */
     121             : 
     122             : void
     123    38113229 : _gcry_mpi_tdiv_r( gcry_mpi_t rem, gcry_mpi_t num, gcry_mpi_t den)
     124             : {
     125    38113229 :     _gcry_mpi_tdiv_qr(NULL, rem, num, den );
     126    38113229 : }
     127             : 
     128             : void
     129    38113443 : _gcry_mpi_tdiv_qr( gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t num, gcry_mpi_t den)
     130             : {
     131             :     mpi_ptr_t np, dp;
     132             :     mpi_ptr_t qp, rp;
     133    38113443 :     mpi_size_t nsize = num->nlimbs;
     134    38113443 :     mpi_size_t dsize = den->nlimbs;
     135             :     mpi_size_t qsize, rsize;
     136    38113443 :     mpi_size_t sign_remainder = num->sign;
     137    38113443 :     mpi_size_t sign_quotient = num->sign ^ den->sign;
     138             :     unsigned normalization_steps;
     139             :     mpi_limb_t q_limb;
     140             :     mpi_ptr_t marker[5];
     141             :     unsigned int marker_nlimbs[5];
     142    38113443 :     int markidx=0;
     143             : 
     144             :     /* Ensure space is enough for quotient and remainder.
     145             :      * We need space for an extra limb in the remainder, because it's
     146             :      * up-shifted (normalized) below.  */
     147    38113443 :     rsize = nsize + 1;
     148    38113443 :     mpi_resize( rem, rsize);
     149             : 
     150    38113443 :     qsize = rsize - dsize;        /* qsize cannot be bigger than this.  */
     151    38113443 :     if( qsize <= 0 ) {
     152       84322 :         if( num != rem ) {
     153       11525 :             rem->nlimbs = num->nlimbs;
     154       11525 :             rem->sign = num->sign;
     155       11525 :             MPN_COPY(rem->d, num->d, nsize);
     156             :         }
     157       84322 :         if( quot ) {
     158             :             /* This needs to follow the assignment to rem, in case the
     159             :              * numerator and quotient are the same.  */
     160           0 :             quot->nlimbs = 0;
     161           0 :             quot->sign = 0;
     162             :         }
     163      228661 :         return;
     164             :     }
     165             : 
     166    38029121 :     if( quot )
     167         214 :         mpi_resize( quot, qsize);
     168             : 
     169             :     /* Read pointers here, when reallocation is finished.  */
     170    38029121 :     np = num->d;
     171    38029121 :     dp = den->d;
     172    38029121 :     rp = rem->d;
     173             : 
     174             :     /* Optimize division by a single-limb divisor.  */
     175    38029121 :     if( dsize == 1 ) {
     176             :         mpi_limb_t rlimb;
     177       60017 :         if( quot ) {
     178          63 :             qp = quot->d;
     179          63 :             rlimb = _gcry_mpih_divmod_1( qp, np, nsize, dp[0] );
     180          63 :             qsize -= qp[qsize - 1] == 0;
     181          63 :             quot->nlimbs = qsize;
     182          63 :             quot->sign = sign_quotient;
     183             :         }
     184             :         else
     185       59954 :             rlimb = _gcry_mpih_mod_1( np, nsize, dp[0] );
     186       60017 :         rp[0] = rlimb;
     187       60017 :         rsize = rlimb != 0?1:0;
     188       60017 :         rem->nlimbs = rsize;
     189       60017 :         rem->sign = sign_remainder;
     190       60017 :         return;
     191             :     }
     192             : 
     193             : 
     194    37969104 :     if( quot ) {
     195         151 :         qp = quot->d;
     196             :         /* Make sure QP and NP point to different objects.  Otherwise the
     197             :          * numerator would be gradually overwritten by the quotient limbs.  */
     198         151 :         if(qp == np) { /* Copy NP object to temporary space.  */
     199          27 :             marker_nlimbs[markidx] = nsize;
     200          27 :             np = marker[markidx++] = mpi_alloc_limb_space(nsize,
     201             :                                                           mpi_is_secure(quot));
     202          27 :             MPN_COPY(np, qp, nsize);
     203             :         }
     204             :     }
     205             :     else /* Put quotient at top of remainder. */
     206    37968953 :         qp = rp + dsize;
     207             : 
     208    37969104 :     count_leading_zeros( normalization_steps, dp[dsize - 1] );
     209             : 
     210             :     /* Normalize the denominator, i.e. make its most significant bit set by
     211             :      * shifting it NORMALIZATION_STEPS bits to the left.  Also shift the
     212             :      * numerator the same number of steps (to keep the quotient the same!).
     213             :      */
     214    37969104 :     if( normalization_steps ) {
     215             :         mpi_ptr_t tp;
     216             :         mpi_limb_t nlimb;
     217             : 
     218             :         /* Shift up the denominator setting the most significant bit of
     219             :          * the most significant word.  Use temporary storage not to clobber
     220             :          * the original contents of the denominator.  */
     221    35933516 :         marker_nlimbs[markidx] = dsize;
     222    35933516 :         tp = marker[markidx++] = mpi_alloc_limb_space(dsize,mpi_is_secure(den));
     223    35933516 :         _gcry_mpih_lshift( tp, dp, dsize, normalization_steps );
     224    35933516 :         dp = tp;
     225             : 
     226             :         /* Shift up the numerator, possibly introducing a new most
     227             :          * significant word.  Move the shifted numerator in the remainder
     228             :          * meanwhile.  */
     229    35933516 :         nlimb = _gcry_mpih_lshift(rp, np, nsize, normalization_steps);
     230    35933516 :         if( nlimb ) {
     231     6005586 :             rp[nsize] = nlimb;
     232     6005586 :             rsize = nsize + 1;
     233             :         }
     234             :         else
     235    29927930 :             rsize = nsize;
     236             :     }
     237             :     else {
     238             :         /* The denominator is already normalized, as required.  Copy it to
     239             :          * temporary space if it overlaps with the quotient or remainder.  */
     240     2035588 :         if( dp == rp || (quot && (dp == qp))) {
     241             :             mpi_ptr_t tp;
     242             : 
     243           0 :             marker_nlimbs[markidx] = dsize;
     244           0 :             tp = marker[markidx++] = mpi_alloc_limb_space(dsize,
     245             :                                                           mpi_is_secure(den));
     246           0 :             MPN_COPY( tp, dp, dsize );
     247           0 :             dp = tp;
     248             :         }
     249             : 
     250             :         /* Move the numerator to the remainder.  */
     251     2035588 :         if( rp != np )
     252        1238 :             MPN_COPY(rp, np, nsize);
     253             : 
     254     2035588 :         rsize = nsize;
     255             :     }
     256             : 
     257    37969104 :     q_limb = _gcry_mpih_divrem( qp, 0, rp, rsize, dp, dsize );
     258             : 
     259    37969104 :     if( quot ) {
     260         151 :         qsize = rsize - dsize;
     261         151 :         if(q_limb) {
     262           0 :             qp[qsize] = q_limb;
     263           0 :             qsize += 1;
     264             :         }
     265             : 
     266         151 :         quot->nlimbs = qsize;
     267         151 :         quot->sign = sign_quotient;
     268             :     }
     269             : 
     270    37969104 :     rsize = dsize;
     271    37969104 :     MPN_NORMALIZE (rp, rsize);
     272             : 
     273    37969104 :     if( normalization_steps && rsize ) {
     274    35933106 :         _gcry_mpih_rshift(rp, rp, rsize, normalization_steps);
     275    35933106 :         rsize -= rp[rsize - 1] == 0?1:0;
     276             :     }
     277             : 
     278    37969104 :     rem->nlimbs = rsize;
     279    37969104 :     rem->sign        = sign_remainder;
     280   111871751 :     while( markidx )
     281             :       {
     282    35933543 :         markidx--;
     283    35933543 :         _gcry_mpi_free_limb_space (marker[markidx], marker_nlimbs[markidx]);
     284             :       }
     285             : }
     286             : 
     287             : void
     288         606 : _gcry_mpi_tdiv_q_2exp( gcry_mpi_t w, gcry_mpi_t u, unsigned int count )
     289             : {
     290             :     mpi_size_t usize, wsize;
     291             :     mpi_size_t limb_cnt;
     292             : 
     293         606 :     usize = u->nlimbs;
     294         606 :     limb_cnt = count / BITS_PER_MPI_LIMB;
     295         606 :     wsize = usize - limb_cnt;
     296         606 :     if( limb_cnt >= usize )
     297           0 :         w->nlimbs = 0;
     298             :     else {
     299             :         mpi_ptr_t wp;
     300             :         mpi_ptr_t up;
     301             : 
     302         606 :         RESIZE_IF_NEEDED( w, wsize );
     303         606 :         wp = w->d;
     304         606 :         up = u->d;
     305             : 
     306         606 :         count %= BITS_PER_MPI_LIMB;
     307         606 :         if( count ) {
     308         606 :             _gcry_mpih_rshift( wp, up + limb_cnt, wsize, count );
     309         606 :             wsize -= !wp[wsize - 1];
     310             :         }
     311             :         else {
     312           0 :             MPN_COPY_INCR( wp, up + limb_cnt, wsize);
     313             :         }
     314             : 
     315         606 :         w->nlimbs = wsize;
     316             :     }
     317         606 : }
     318             : 
     319             : /****************
     320             :  * Check whether dividend is divisible by divisor
     321             :  * (note: divisor must fit into a limb)
     322             :  */
     323             : int
     324     2370459 : _gcry_mpi_divisible_ui(gcry_mpi_t dividend, ulong divisor )
     325             : {
     326     2370459 :     return !_gcry_mpih_mod_1( dividend->d, dividend->nlimbs, divisor );
     327             : }
     328             : 
     329             : 
     330             : void
     331           2 : _gcry_mpi_div (gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t dividend,
     332             :                gcry_mpi_t divisor, int round)
     333             : {
     334           2 :   if (!round)
     335             :     {
     336           0 :       if (!rem)
     337             :         {
     338           0 :           gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs(quot));
     339           0 :           _gcry_mpi_tdiv_qr (quot, tmp, dividend, divisor);
     340           0 :           mpi_free (tmp);
     341             :         }
     342             :       else
     343           0 :         _gcry_mpi_tdiv_qr (quot, rem, dividend, divisor);
     344             :     }
     345           2 :   else if (round < 0)
     346             :     {
     347           2 :       if (!rem)
     348           2 :         _gcry_mpi_fdiv_q (quot, dividend, divisor);
     349           0 :       else if (!quot)
     350           0 :         _gcry_mpi_fdiv_r (rem, dividend, divisor);
     351             :       else
     352           0 :         _gcry_mpi_fdiv_qr (quot, rem, dividend, divisor);
     353             :     }
     354             :   else
     355           0 :     log_bug ("mpi rounding to ceiling not yet implemented\n");
     356           2 : }

Generated by: LCOV version 1.11