Branch data     Line data    Source code

       1                 :            : // SPDX-License-Identifier: GPL-2.0-or-later
       2                 :            : /* mpihelp-div.c  -  MPI helper functions
       3                 :            :  *      Copyright (C) 1994, 1996 Free Software Foundation, Inc.
       4                 :            :  *      Copyright (C) 1998, 1999 Free Software Foundation, Inc.
       5                 :            :  *
       6                 :            :  * This file is part of GnuPG.
       7                 :            :  *
       8                 :            :  * Note: This code is heavily based on the GNU MP Library.
       9                 :            :  *       Actually it's the same code with only minor changes in the
      10                 :            :  *       way the data is stored; this is to support the abstraction
      11                 :            :  *       of an optional secure memory allocation which may be used
      12                 :            :  *       to avoid revealing of sensitive data due to paging etc.
      13                 :            :  *       The GNU MP Library itself is published under the LGPL;
      14                 :            :  *       however I decided to publish this code under the plain GPL.
      15                 :            :  */
      16                 :            : 
      17                 :            : #include "mpi-internal.h"
      18                 :            : #include "longlong.h"
      19                 :            : 
      20                 :            : #ifndef UMUL_TIME
      21                 :            : #define UMUL_TIME 1
      22                 :            : #endif
      23                 :            : #ifndef UDIV_TIME
      24                 :            : #define UDIV_TIME UMUL_TIME
      25                 :            : #endif
      26                 :            : 
      27                 :            : /* Divide num (NP/NSIZE) by den (DP/DSIZE) and write
      28                 :            :  * the NSIZE-DSIZE least significant quotient limbs at QP
      29                 :            :  * and the DSIZE long remainder at NP.  If QEXTRA_LIMBS is
      30                 :            :  * non-zero, generate that many fraction bits and append them after the
      31                 :            :  * other quotient limbs.
      32                 :            :  * Return the most significant limb of the quotient, this is always 0 or 1.
      33                 :            :  *
      34                 :            :  * Preconditions:
      35                 :            :  * 0. NSIZE >= DSIZE.
      36                 :            :  * 1. The most significant bit of the divisor must be set.
      37                 :            :  * 2. QP must either not overlap with the input operands at all, or
      38                 :            :  *    QP + DSIZE >= NP must hold true.       (This means that it's
      39                 :            :  *    possible to put the quotient in the high part of NUM, right after the
      40                 :            :  *    remainder in NUM.
      41                 :            :  * 3. NSIZE >= DSIZE, even if QEXTRA_LIMBS is non-zero.
      42                 :            :  */
      43                 :            : 
      44                 :            : mpi_limb_t
      45                 :          3 : mpihelp_divrem(mpi_ptr_t qp, mpi_size_t qextra_limbs,
      46                 :            :                mpi_ptr_t np, mpi_size_t nsize, mpi_ptr_t dp, mpi_size_t dsize)
      47                 :            : {
      48                 :            :         mpi_limb_t most_significant_q_limb = 0;
      49                 :            : 
      50                 :          3 :         switch (dsize) {
      51                 :            :         case 0:
      52                 :            :                 /* We are asked to divide by zero, so go ahead and do it!  (To make
      53                 :            :                    the compiler not remove this statement, return the value.)  */
      54                 :            :                 /*
      55                 :            :                  * existing clients of this function have been modified
      56                 :            :                  * not to call it with dsize == 0, so this should not happen
      57                 :            :                  */
      58                 :          0 :                 return 1 / dsize;
      59                 :            : 
      60                 :            :         case 1:
      61                 :            :                 {
      62                 :            :                         mpi_size_t i;
      63                 :            :                         mpi_limb_t n1;
      64                 :            :                         mpi_limb_t d;
      65                 :            : 
      66                 :          0 :                         d = dp[0];
      67                 :          0 :                         n1 = np[nsize - 1];
      68                 :            : 
      69                 :          0 :                         if (n1 >= d) {
      70                 :          0 :                                 n1 -= d;
      71                 :            :                                 most_significant_q_limb = 1;
      72                 :            :                         }
      73                 :            : 
      74                 :          0 :                         qp += qextra_limbs;
      75                 :          0 :                         for (i = nsize - 2; i >= 0; i--)
      76                 :          0 :                                 udiv_qrnnd(qp[i], n1, n1, np[i], d);
      77                 :            :                         qp -= qextra_limbs;
      78                 :            : 
      79                 :          0 :                         for (i = qextra_limbs - 1; i >= 0; i--)
      80                 :          0 :                                 udiv_qrnnd(qp[i], n1, n1, 0, d);
      81                 :            : 
      82                 :          0 :                         np[0] = n1;
      83                 :            :                 }
      84                 :          0 :                 break;
      85                 :            : 
      86                 :            :         case 2:
      87                 :            :                 {
      88                 :            :                         mpi_size_t i;
      89                 :            :                         mpi_limb_t n1, n0, n2;
      90                 :            :                         mpi_limb_t d1, d0;
      91                 :            : 
      92                 :          0 :                         np += nsize - 2;
      93                 :          0 :                         d1 = dp[1];
      94                 :          0 :                         d0 = dp[0];
      95                 :          0 :                         n1 = np[1];
      96                 :          0 :                         n0 = np[0];
      97                 :            : 
      98                 :          0 :                         if (n1 >= d1 && (n1 > d1 || n0 >= d0)) {
      99                 :          0 :                                 sub_ddmmss(n1, n0, n1, n0, d1, d0);
     100                 :            :                                 most_significant_q_limb = 1;
     101                 :            :                         }
     102                 :            : 
     103                 :          0 :                         for (i = qextra_limbs + nsize - 2 - 1; i >= 0; i--) {
     104                 :            :                                 mpi_limb_t q;
     105                 :            :                                 mpi_limb_t r;
     106                 :            : 
     107                 :          0 :                                 if (i >= qextra_limbs)
     108                 :          0 :                                         np--;
     109                 :            :                                 else
     110                 :          0 :                                         np[0] = 0;
     111                 :            : 
     112                 :          0 :                                 if (n1 == d1) {
     113                 :            :                                         /* Q should be either 111..111 or 111..110.  Need special
     114                 :            :                                          * treatment of this rare case as normal division would
     115                 :            :                                          * give overflow.  */
     116                 :            :                                         q = ~(mpi_limb_t) 0;
     117                 :            : 
     118                 :          0 :                                         r = n0 + d1;
     119                 :          0 :                                         if (r < d1) {        /* Carry in the addition? */
     120                 :          0 :                                                 add_ssaaaa(n1, n0, r - d0,
     121                 :            :                                                            np[0], 0, d0);
     122                 :          0 :                                                 qp[i] = q;
     123                 :          0 :                                                 continue;
     124                 :            :                                         }
     125                 :          0 :                                         n1 = d0 - (d0 != 0 ? 1 : 0);
     126                 :          0 :                                         n0 = -d0;
     127                 :            :                                 } else {
     128                 :          0 :                                         udiv_qrnnd(q, r, n1, n0, d1);
     129                 :          0 :                                         umul_ppmm(n1, n0, d0, q);
     130                 :            :                                 }
     131                 :            : 
     132                 :          0 :                                 n2 = np[0];
     133                 :            : q_test:
     134                 :          0 :                                 if (n1 > r || (n1 == r && n0 > n2)) {
     135                 :            :                                         /* The estimated Q was too large.  */
     136                 :          0 :                                         q--;
     137                 :          0 :                                         sub_ddmmss(n1, n0, n1, n0, 0, d0);
     138                 :          0 :                                         r += d1;
     139                 :          0 :                                         if (r >= d1) /* If not carry, test Q again.  */
     140                 :            :                                                 goto q_test;
     141                 :            :                                 }
     142                 :            : 
     143                 :          0 :                                 qp[i] = q;
     144                 :          0 :                                 sub_ddmmss(n1, n0, r, n2, n1, n0);
     145                 :            :                         }
     146                 :          0 :                         np[1] = n1;
     147                 :          0 :                         np[0] = n0;
     148                 :            :                 }
     149                 :          0 :                 break;
     150                 :            : 
     151                 :            :         default:
     152                 :            :                 {
     153                 :            :                         mpi_size_t i;
     154                 :            :                         mpi_limb_t dX, d1, n0;
     155                 :            : 
     156                 :          3 :                         np += nsize - dsize;
     157                 :          3 :                         dX = dp[dsize - 1];
     158                 :          3 :                         d1 = dp[dsize - 2];
     159                 :          3 :                         n0 = np[dsize - 1];
     160                 :            : 
     161                 :          3 :                         if (n0 >= dX) {
     162                 :          0 :                                 if (n0 > dX
     163                 :          0 :                                     || mpihelp_cmp(np, dp, dsize - 1) >= 0) {
     164                 :          0 :                                         mpihelp_sub_n(np, np, dp, dsize);
     165                 :          0 :                                         n0 = np[dsize - 1];
     166                 :            :                                         most_significant_q_limb = 1;
     167                 :            :                                 }
     168                 :            :                         }
     169                 :            : 
     170                 :          3 :                         for (i = qextra_limbs + nsize - dsize - 1; i >= 0; i--) {
     171                 :            :                                 mpi_limb_t q;
     172                 :            :                                 mpi_limb_t n1, n2;
     173                 :            :                                 mpi_limb_t cy_limb;
     174                 :            : 
     175                 :          3 :                                 if (i >= qextra_limbs) {
     176                 :          3 :                                         np--;
     177                 :          3 :                                         n2 = np[dsize];
     178                 :            :                                 } else {
     179                 :          0 :                                         n2 = np[dsize - 1];
     180                 :          0 :                                         MPN_COPY_DECR(np + 1, np, dsize - 1);
     181                 :          0 :                                         np[0] = 0;
     182                 :            :                                 }
     183                 :            : 
     184                 :          3 :                                 if (n0 == dX) {
     185                 :            :                                         /* This might over-estimate q, but it's probably not worth
     186                 :            :                                          * the extra code here to find out.  */
     187                 :            :                                         q = ~(mpi_limb_t) 0;
     188                 :            :                                 } else {
     189                 :            :                                         mpi_limb_t r;
     190                 :            : 
     191                 :          3 :                                         udiv_qrnnd(q, r, n0, np[dsize - 1], dX);
     192                 :          3 :                                         umul_ppmm(n1, n0, d1, q);
     193                 :            : 
     194                 :          3 :                                         while (n1 > r
     195                 :          3 :                                                || (n1 == r
     196                 :          0 :                                                    && n0 > np[dsize - 2])) {
     197                 :          3 :                                                 q--;
     198                 :          3 :                                                 r += dX;
     199                 :          3 :                                                 if (r < dX)  /* I.e. "carry in previous addition?" */
     200                 :            :                                                         break;
     201                 :          3 :                                                 n1 -= n0 < d1;
     202                 :          3 :                                                 n0 -= d1;
     203                 :            :                                         }
     204                 :            :                                 }
     205                 :            : 
     206                 :            :                                 /* Possible optimization: We already have (q * n0) and (1 * n1)
     207                 :            :                                  * after the calculation of q.  Taking advantage of that, we
     208                 :            :                                  * could make this loop make two iterations less.  */
     209                 :          3 :                                 cy_limb = mpihelp_submul_1(np, dp, dsize, q);
     210                 :            : 
     211                 :          3 :                                 if (n2 != cy_limb) {
     212                 :          0 :                                         mpihelp_add_n(np, np, dp, dsize);
     213                 :          0 :                                         q--;
     214                 :            :                                 }
     215                 :            : 
     216                 :          3 :                                 qp[i] = q;
     217                 :          3 :                                 n0 = np[dsize - 1];
     218                 :            :                         }
     219                 :            :                 }
     220                 :            :         }
     221                 :            : 
     222                 :          3 :         return most_significant_q_limb;
     223                 :            : }