Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /* mpihelp-div.c  -  MPI helper functions
0003  *  Copyright (C) 1994, 1996 Free Software Foundation, Inc.
0004  *  Copyright (C) 1998, 1999 Free Software Foundation, Inc.
0005  *
0006  * This file is part of GnuPG.
0007  *
0008  * Note: This code is heavily based on the GNU MP Library.
0009  *   Actually it's the same code with only minor changes in the
0010  *   way the data is stored; this is to support the abstraction
0011  *   of an optional secure memory allocation which may be used
0012  *   to avoid revealing of sensitive data due to paging etc.
0013  *   The GNU MP Library itself is published under the LGPL;
0014  *   however I decided to publish this code under the plain GPL.
0015  */
0016 
0017 #include "mpi-internal.h"
0018 #include "longlong.h"
0019 
0020 #ifndef UMUL_TIME
0021 #define UMUL_TIME 1
0022 #endif
0023 #ifndef UDIV_TIME
0024 #define UDIV_TIME UMUL_TIME
0025 #endif
0026 
0027 
0028 mpi_limb_t
0029 mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
0030             mpi_limb_t divisor_limb)
0031 {
0032     mpi_size_t i;
0033     mpi_limb_t n1, n0, r;
0034     mpi_limb_t dummy __maybe_unused;
0035 
0036     /* Botch: Should this be handled at all?  Rely on callers?  */
0037     if (!dividend_size)
0038         return 0;
0039 
0040     /* If multiplication is much faster than division, and the
0041      * dividend is large, pre-invert the divisor, and use
0042      * only multiplications in the inner loop.
0043      *
0044      * This test should be read:
0045      *   Does it ever help to use udiv_qrnnd_preinv?
0046      *     && Does what we save compensate for the inversion overhead?
0047      */
0048     if (UDIV_TIME > (2 * UMUL_TIME + 6)
0049             && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
0050         int normalization_steps;
0051 
0052         normalization_steps = count_leading_zeros(divisor_limb);
0053         if (normalization_steps) {
0054             mpi_limb_t divisor_limb_inverted;
0055 
0056             divisor_limb <<= normalization_steps;
0057 
0058             /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
0059              * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
0060              * most significant bit (with weight 2**N) implicit.
0061              *
0062              * Special case for DIVISOR_LIMB == 100...000.
0063              */
0064             if (!(divisor_limb << 1))
0065                 divisor_limb_inverted = ~(mpi_limb_t)0;
0066             else
0067                 udiv_qrnnd(divisor_limb_inverted, dummy,
0068                         -divisor_limb, 0, divisor_limb);
0069 
0070             n1 = dividend_ptr[dividend_size - 1];
0071             r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
0072 
0073             /* Possible optimization:
0074              * if (r == 0
0075              * && divisor_limb > ((n1 << normalization_steps)
0076              *             | (dividend_ptr[dividend_size - 2] >> ...)))
0077              * ...one division less...
0078              */
0079             for (i = dividend_size - 2; i >= 0; i--) {
0080                 n0 = dividend_ptr[i];
0081                 UDIV_QRNND_PREINV(dummy, r, r,
0082                         ((n1 << normalization_steps)
0083                          | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
0084                         divisor_limb, divisor_limb_inverted);
0085                 n1 = n0;
0086             }
0087             UDIV_QRNND_PREINV(dummy, r, r,
0088                     n1 << normalization_steps,
0089                     divisor_limb, divisor_limb_inverted);
0090             return r >> normalization_steps;
0091         } else {
0092             mpi_limb_t divisor_limb_inverted;
0093 
0094             /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
0095              * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
0096              * most significant bit (with weight 2**N) implicit.
0097              *
0098              * Special case for DIVISOR_LIMB == 100...000.
0099              */
0100             if (!(divisor_limb << 1))
0101                 divisor_limb_inverted = ~(mpi_limb_t)0;
0102             else
0103                 udiv_qrnnd(divisor_limb_inverted, dummy,
0104                         -divisor_limb, 0, divisor_limb);
0105 
0106             i = dividend_size - 1;
0107             r = dividend_ptr[i];
0108 
0109             if (r >= divisor_limb)
0110                 r = 0;
0111             else
0112                 i--;
0113 
0114             for ( ; i >= 0; i--) {
0115                 n0 = dividend_ptr[i];
0116                 UDIV_QRNND_PREINV(dummy, r, r,
0117                         n0, divisor_limb, divisor_limb_inverted);
0118             }
0119             return r;
0120         }
0121     } else {
0122         if (UDIV_NEEDS_NORMALIZATION) {
0123             int normalization_steps;
0124 
0125             normalization_steps = count_leading_zeros(divisor_limb);
0126             if (normalization_steps) {
0127                 divisor_limb <<= normalization_steps;
0128 
0129                 n1 = dividend_ptr[dividend_size - 1];
0130                 r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
0131 
0132                 /* Possible optimization:
0133                  * if (r == 0
0134                  * && divisor_limb > ((n1 << normalization_steps)
0135                  *         | (dividend_ptr[dividend_size - 2] >> ...)))
0136                  * ...one division less...
0137                  */
0138                 for (i = dividend_size - 2; i >= 0; i--) {
0139                     n0 = dividend_ptr[i];
0140                     udiv_qrnnd(dummy, r, r,
0141                         ((n1 << normalization_steps)
0142                          | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
0143                         divisor_limb);
0144                     n1 = n0;
0145                 }
0146                 udiv_qrnnd(dummy, r, r,
0147                         n1 << normalization_steps,
0148                         divisor_limb);
0149                 return r >> normalization_steps;
0150             }
0151         }
0152         /* No normalization needed, either because udiv_qrnnd doesn't require
0153          * it, or because DIVISOR_LIMB is already normalized.
0154          */
0155         i = dividend_size - 1;
0156         r = dividend_ptr[i];
0157 
0158         if (r >= divisor_limb)
0159             r = 0;
0160         else
0161             i--;
0162 
0163         for (; i >= 0; i--) {
0164             n0 = dividend_ptr[i];
0165             udiv_qrnnd(dummy, r, r, n0, divisor_limb);
0166         }
0167         return r;
0168     }
0169 }
0170 
0171 /* Divide num (NP/NSIZE) by den (DP/DSIZE) and write
0172  * the NSIZE-DSIZE least significant quotient limbs at QP
0173  * and the DSIZE long remainder at NP.  If QEXTRA_LIMBS is
0174  * non-zero, generate that many fraction bits and append them after the
0175  * other quotient limbs.
0176  * Return the most significant limb of the quotient, this is always 0 or 1.
0177  *
0178  * Preconditions:
0179  * 0. NSIZE >= DSIZE.
0180  * 1. The most significant bit of the divisor must be set.
0181  * 2. QP must either not overlap with the input operands at all, or
0182  *    QP + DSIZE >= NP must hold true.  (This means that it's
0183  *    possible to put the quotient in the high part of NUM, right after the
0184  *    remainder in NUM.
0185  * 3. NSIZE >= DSIZE, even if QEXTRA_LIMBS is non-zero.
0186  */
0187 
0188 mpi_limb_t
0189 mpihelp_divrem(mpi_ptr_t qp, mpi_size_t qextra_limbs,
0190            mpi_ptr_t np, mpi_size_t nsize, mpi_ptr_t dp, mpi_size_t dsize)
0191 {
0192     mpi_limb_t most_significant_q_limb = 0;
0193 
0194     switch (dsize) {
0195     case 0:
0196         /* We are asked to divide by zero, so go ahead and do it!  (To make
0197            the compiler not remove this statement, return the value.)  */
0198         /*
0199          * existing clients of this function have been modified
0200          * not to call it with dsize == 0, so this should not happen
0201          */
0202         return 1 / dsize;
0203 
0204     case 1:
0205         {
0206             mpi_size_t i;
0207             mpi_limb_t n1;
0208             mpi_limb_t d;
0209 
0210             d = dp[0];
0211             n1 = np[nsize - 1];
0212 
0213             if (n1 >= d) {
0214                 n1 -= d;
0215                 most_significant_q_limb = 1;
0216             }
0217 
0218             qp += qextra_limbs;
0219             for (i = nsize - 2; i >= 0; i--)
0220                 udiv_qrnnd(qp[i], n1, n1, np[i], d);
0221             qp -= qextra_limbs;
0222 
0223             for (i = qextra_limbs - 1; i >= 0; i--)
0224                 udiv_qrnnd(qp[i], n1, n1, 0, d);
0225 
0226             np[0] = n1;
0227         }
0228         break;
0229 
0230     case 2:
0231         {
0232             mpi_size_t i;
0233             mpi_limb_t n1, n0, n2;
0234             mpi_limb_t d1, d0;
0235 
0236             np += nsize - 2;
0237             d1 = dp[1];
0238             d0 = dp[0];
0239             n1 = np[1];
0240             n0 = np[0];
0241 
0242             if (n1 >= d1 && (n1 > d1 || n0 >= d0)) {
0243                 sub_ddmmss(n1, n0, n1, n0, d1, d0);
0244                 most_significant_q_limb = 1;
0245             }
0246 
0247             for (i = qextra_limbs + nsize - 2 - 1; i >= 0; i--) {
0248                 mpi_limb_t q;
0249                 mpi_limb_t r;
0250 
0251                 if (i >= qextra_limbs)
0252                     np--;
0253                 else
0254                     np[0] = 0;
0255 
0256                 if (n1 == d1) {
0257                     /* Q should be either 111..111 or 111..110.  Need special
0258                      * treatment of this rare case as normal division would
0259                      * give overflow.  */
0260                     q = ~(mpi_limb_t) 0;
0261 
0262                     r = n0 + d1;
0263                     if (r < d1) {   /* Carry in the addition? */
0264                         add_ssaaaa(n1, n0, r - d0,
0265                                np[0], 0, d0);
0266                         qp[i] = q;
0267                         continue;
0268                     }
0269                     n1 = d0 - (d0 != 0 ? 1 : 0);
0270                     n0 = -d0;
0271                 } else {
0272                     udiv_qrnnd(q, r, n1, n0, d1);
0273                     umul_ppmm(n1, n0, d0, q);
0274                 }
0275 
0276                 n2 = np[0];
0277 q_test:
0278                 if (n1 > r || (n1 == r && n0 > n2)) {
0279                     /* The estimated Q was too large.  */
0280                     q--;
0281                     sub_ddmmss(n1, n0, n1, n0, 0, d0);
0282                     r += d1;
0283                     if (r >= d1)    /* If not carry, test Q again.  */
0284                         goto q_test;
0285                 }
0286 
0287                 qp[i] = q;
0288                 sub_ddmmss(n1, n0, r, n2, n1, n0);
0289             }
0290             np[1] = n1;
0291             np[0] = n0;
0292         }
0293         break;
0294 
0295     default:
0296         {
0297             mpi_size_t i;
0298             mpi_limb_t dX, d1, n0;
0299 
0300             np += nsize - dsize;
0301             dX = dp[dsize - 1];
0302             d1 = dp[dsize - 2];
0303             n0 = np[dsize - 1];
0304 
0305             if (n0 >= dX) {
0306                 if (n0 > dX
0307                     || mpihelp_cmp(np, dp, dsize - 1) >= 0) {
0308                     mpihelp_sub_n(np, np, dp, dsize);
0309                     n0 = np[dsize - 1];
0310                     most_significant_q_limb = 1;
0311                 }
0312             }
0313 
0314             for (i = qextra_limbs + nsize - dsize - 1; i >= 0; i--) {
0315                 mpi_limb_t q;
0316                 mpi_limb_t n1, n2;
0317                 mpi_limb_t cy_limb;
0318 
0319                 if (i >= qextra_limbs) {
0320                     np--;
0321                     n2 = np[dsize];
0322                 } else {
0323                     n2 = np[dsize - 1];
0324                     MPN_COPY_DECR(np + 1, np, dsize - 1);
0325                     np[0] = 0;
0326                 }
0327 
0328                 if (n0 == dX) {
0329                     /* This might over-estimate q, but it's probably not worth
0330                      * the extra code here to find out.  */
0331                     q = ~(mpi_limb_t) 0;
0332                 } else {
0333                     mpi_limb_t r;
0334 
0335                     udiv_qrnnd(q, r, n0, np[dsize - 1], dX);
0336                     umul_ppmm(n1, n0, d1, q);
0337 
0338                     while (n1 > r
0339                            || (n1 == r
0340                            && n0 > np[dsize - 2])) {
0341                         q--;
0342                         r += dX;
0343                         if (r < dX) /* I.e. "carry in previous addition?" */
0344                             break;
0345                         n1 -= n0 < d1;
0346                         n0 -= d1;
0347                     }
0348                 }
0349 
0350                 /* Possible optimization: We already have (q * n0) and (1 * n1)
0351                  * after the calculation of q.  Taking advantage of that, we
0352                  * could make this loop make two iterations less.  */
0353                 cy_limb = mpihelp_submul_1(np, dp, dsize, q);
0354 
0355                 if (n2 != cy_limb) {
0356                     mpihelp_add_n(np, np, dp, dsize);
0357                     q--;
0358                 }
0359 
0360                 qp[i] = q;
0361                 n0 = np[dsize - 1];
0362             }
0363         }
0364     }
0365 
0366     return most_significant_q_limb;
0367 }
0368 
0369 /****************
0370  * Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB.
0371  * Write DIVIDEND_SIZE limbs of quotient at QUOT_PTR.
0372  * Return the single-limb remainder.
0373  * There are no constraints on the value of the divisor.
0374  *
0375  * QUOT_PTR and DIVIDEND_PTR might point to the same limb.
0376  */
0377 
0378 mpi_limb_t
0379 mpihelp_divmod_1(mpi_ptr_t quot_ptr,
0380         mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
0381         mpi_limb_t divisor_limb)
0382 {
0383     mpi_size_t i;
0384     mpi_limb_t n1, n0, r;
0385     mpi_limb_t dummy __maybe_unused;
0386 
0387     if (!dividend_size)
0388         return 0;
0389 
0390     /* If multiplication is much faster than division, and the
0391      * dividend is large, pre-invert the divisor, and use
0392      * only multiplications in the inner loop.
0393      *
0394      * This test should be read:
0395      * Does it ever help to use udiv_qrnnd_preinv?
0396      * && Does what we save compensate for the inversion overhead?
0397      */
0398     if (UDIV_TIME > (2 * UMUL_TIME + 6)
0399             && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
0400         int normalization_steps;
0401 
0402         normalization_steps = count_leading_zeros(divisor_limb);
0403         if (normalization_steps) {
0404             mpi_limb_t divisor_limb_inverted;
0405 
0406             divisor_limb <<= normalization_steps;
0407 
0408             /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
0409              * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
0410              * most significant bit (with weight 2**N) implicit.
0411              */
0412             /* Special case for DIVISOR_LIMB == 100...000.  */
0413             if (!(divisor_limb << 1))
0414                 divisor_limb_inverted = ~(mpi_limb_t)0;
0415             else
0416                 udiv_qrnnd(divisor_limb_inverted, dummy,
0417                         -divisor_limb, 0, divisor_limb);
0418 
0419             n1 = dividend_ptr[dividend_size - 1];
0420             r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
0421 
0422             /* Possible optimization:
0423              * if (r == 0
0424              * && divisor_limb > ((n1 << normalization_steps)
0425              *             | (dividend_ptr[dividend_size - 2] >> ...)))
0426              * ...one division less...
0427              */
0428             for (i = dividend_size - 2; i >= 0; i--) {
0429                 n0 = dividend_ptr[i];
0430                 UDIV_QRNND_PREINV(quot_ptr[i + 1], r, r,
0431                         ((n1 << normalization_steps)
0432                          | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
0433                         divisor_limb, divisor_limb_inverted);
0434                 n1 = n0;
0435             }
0436             UDIV_QRNND_PREINV(quot_ptr[0], r, r,
0437                     n1 << normalization_steps,
0438                     divisor_limb, divisor_limb_inverted);
0439             return r >> normalization_steps;
0440         } else {
0441             mpi_limb_t divisor_limb_inverted;
0442 
0443             /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
0444              * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
0445              * most significant bit (with weight 2**N) implicit.
0446              */
0447             /* Special case for DIVISOR_LIMB == 100...000.  */
0448             if (!(divisor_limb << 1))
0449                 divisor_limb_inverted = ~(mpi_limb_t) 0;
0450             else
0451                 udiv_qrnnd(divisor_limb_inverted, dummy,
0452                         -divisor_limb, 0, divisor_limb);
0453 
0454             i = dividend_size - 1;
0455             r = dividend_ptr[i];
0456 
0457             if (r >= divisor_limb)
0458                 r = 0;
0459             else
0460                 quot_ptr[i--] = 0;
0461 
0462             for ( ; i >= 0; i--) {
0463                 n0 = dividend_ptr[i];
0464                 UDIV_QRNND_PREINV(quot_ptr[i], r, r,
0465                         n0, divisor_limb, divisor_limb_inverted);
0466             }
0467             return r;
0468         }
0469     } else {
0470         if (UDIV_NEEDS_NORMALIZATION) {
0471             int normalization_steps;
0472 
0473             normalization_steps = count_leading_zeros(divisor_limb);
0474             if (normalization_steps) {
0475                 divisor_limb <<= normalization_steps;
0476 
0477                 n1 = dividend_ptr[dividend_size - 1];
0478                 r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
0479 
0480                 /* Possible optimization:
0481                  * if (r == 0
0482                  * && divisor_limb > ((n1 << normalization_steps)
0483                  *         | (dividend_ptr[dividend_size - 2] >> ...)))
0484                  * ...one division less...
0485                  */
0486                 for (i = dividend_size - 2; i >= 0; i--) {
0487                     n0 = dividend_ptr[i];
0488                     udiv_qrnnd(quot_ptr[i + 1], r, r,
0489                         ((n1 << normalization_steps)
0490                          | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
0491                         divisor_limb);
0492                     n1 = n0;
0493                 }
0494                 udiv_qrnnd(quot_ptr[0], r, r,
0495                         n1 << normalization_steps,
0496                         divisor_limb);
0497                 return r >> normalization_steps;
0498             }
0499         }
0500         /* No normalization needed, either because udiv_qrnnd doesn't require
0501          * it, or because DIVISOR_LIMB is already normalized.
0502          */
0503         i = dividend_size - 1;
0504         r = dividend_ptr[i];
0505 
0506         if (r >= divisor_limb)
0507             r = 0;
0508         else
0509             quot_ptr[i--] = 0;
0510 
0511         for (; i >= 0; i--) {
0512             n0 = dividend_ptr[i];
0513             udiv_qrnnd(quot_ptr[i], r, r, n0, divisor_limb);
0514         }
0515         return r;
0516     }
0517 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!