diff options
Diffstat (limited to 'lib/mpi/mpih-div.c')
| -rw-r--r-- | lib/mpi/mpih-div.c | 223 |
1 files changed, 0 insertions, 223 deletions
diff --git a/lib/mpi/mpih-div.c b/lib/mpi/mpih-div.c deleted file mode 100644 index 913a519eb005..000000000000 --- a/lib/mpi/mpih-div.c +++ /dev/null @@ -1,223 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0-or-later -/* mpihelp-div.c - MPI helper functions - * Copyright (C) 1994, 1996 Free Software Foundation, Inc. - * Copyright (C) 1998, 1999 Free Software Foundation, Inc. - * - * This file is part of GnuPG. - * - * 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. - * The GNU MP Library itself is published under the LGPL; - * however I decided to publish this code under the plain GPL. - */ - -#include "mpi-internal.h" -#include "longlong.h" - -#ifndef UMUL_TIME -#define UMUL_TIME 1 -#endif -#ifndef UDIV_TIME -#define UDIV_TIME UMUL_TIME -#endif - -/* Divide num (NP/NSIZE) by den (DP/DSIZE) and write - * the NSIZE-DSIZE least significant quotient limbs at QP - * and the DSIZE long remainder at NP. If QEXTRA_LIMBS is - * non-zero, generate that many fraction bits and append them after the - * other quotient limbs. - * Return the most significant limb of the quotient, this is always 0 or 1. - * - * Preconditions: - * 0. NSIZE >= DSIZE. - * 1. The most significant bit of the divisor must be set. - * 2. QP must either not overlap with the input operands at all, or - * QP + DSIZE >= NP must hold true. (This means that it's - * possible to put the quotient in the high part of NUM, right after the - * remainder in NUM. - * 3. NSIZE >= DSIZE, even if QEXTRA_LIMBS is non-zero. - */ - -mpi_limb_t -mpihelp_divrem(mpi_ptr_t qp, mpi_size_t qextra_limbs, - mpi_ptr_t np, mpi_size_t nsize, mpi_ptr_t dp, mpi_size_t dsize) -{ - mpi_limb_t most_significant_q_limb = 0; - - switch (dsize) { - case 0: - /* We are asked to divide by zero, so go ahead and do it! (To make - the compiler not remove this statement, return the value.) */ - /* - * existing clients of this function have been modified - * not to call it with dsize == 0, so this should not happen - */ - return 1 / dsize; - - case 1: - { - mpi_size_t i; - mpi_limb_t n1; - mpi_limb_t d; - - d = dp[0]; - n1 = np[nsize - 1]; - - if (n1 >= d) { - n1 -= d; - most_significant_q_limb = 1; - } - - qp += qextra_limbs; - for (i = nsize - 2; i >= 0; i--) - udiv_qrnnd(qp[i], n1, n1, np[i], d); - qp -= qextra_limbs; - - for (i = qextra_limbs - 1; i >= 0; i--) - udiv_qrnnd(qp[i], n1, n1, 0, d); - - np[0] = n1; - } - break; - - case 2: - { - mpi_size_t i; - mpi_limb_t n1, n0, n2; - mpi_limb_t d1, d0; - - np += nsize - 2; - d1 = dp[1]; - d0 = dp[0]; - n1 = np[1]; - n0 = np[0]; - - if (n1 >= d1 && (n1 > d1 || n0 >= d0)) { - sub_ddmmss(n1, n0, n1, n0, d1, d0); - most_significant_q_limb = 1; - } - - for (i = qextra_limbs + nsize - 2 - 1; i >= 0; i--) { - mpi_limb_t q; - mpi_limb_t r; - - if (i >= qextra_limbs) - np--; - else - np[0] = 0; - - if (n1 == d1) { - /* Q should be either 111..111 or 111..110. Need special - * treatment of this rare case as normal division would - * give overflow. */ - q = ~(mpi_limb_t) 0; - - r = n0 + d1; - if (r < d1) { /* Carry in the addition? */ - add_ssaaaa(n1, n0, r - d0, - np[0], 0, d0); - qp[i] = q; - continue; - } - n1 = d0 - (d0 != 0 ? 1 : 0); - n0 = -d0; - } else { - udiv_qrnnd(q, r, n1, n0, d1); - umul_ppmm(n1, n0, d0, q); - } - - n2 = np[0]; -q_test: - if (n1 > r || (n1 == r && n0 > n2)) { - /* The estimated Q was too large. */ - q--; - sub_ddmmss(n1, n0, n1, n0, 0, d0); - r += d1; - if (r >= d1) /* If not carry, test Q again. */ - goto q_test; - } - - qp[i] = q; - sub_ddmmss(n1, n0, r, n2, n1, n0); - } - np[1] = n1; - np[0] = n0; - } - break; - - default: - { - mpi_size_t i; - mpi_limb_t dX, d1, n0; - - np += nsize - dsize; - dX = dp[dsize - 1]; - d1 = dp[dsize - 2]; - n0 = np[dsize - 1]; - - if (n0 >= dX) { - if (n0 > dX - || mpihelp_cmp(np, dp, dsize - 1) >= 0) { - mpihelp_sub_n(np, np, dp, dsize); - n0 = np[dsize - 1]; - most_significant_q_limb = 1; - } - } - - for (i = qextra_limbs + nsize - dsize - 1; i >= 0; i--) { - mpi_limb_t q; - mpi_limb_t n1, n2; - mpi_limb_t cy_limb; - - if (i >= qextra_limbs) { - np--; - n2 = np[dsize]; - } else { - n2 = np[dsize - 1]; - MPN_COPY_DECR(np + 1, np, dsize - 1); - np[0] = 0; - } - - if (n0 == dX) { - /* This might over-estimate q, but it's probably not worth - * the extra code here to find out. */ - q = ~(mpi_limb_t) 0; - } else { - mpi_limb_t r; - - udiv_qrnnd(q, r, n0, np[dsize - 1], dX); - umul_ppmm(n1, n0, d1, q); - - while (n1 > r - || (n1 == r - && n0 > np[dsize - 2])) { - q--; - r += dX; - if (r < dX) /* I.e. "carry in previous addition?" */ - break; - n1 -= n0 < d1; - n0 -= d1; - } - } - - /* Possible optimization: We already have (q * n0) and (1 * n1) - * after the calculation of q. Taking advantage of that, we - * could make this loop make two iterations less. */ - cy_limb = mpihelp_submul_1(np, dp, dsize, q); - - if (n2 != cy_limb) { - mpihelp_add_n(np, np, dp, dsize); - q--; - } - - qp[i] = q; - n0 = np[dsize - 1]; - } - } - } - - return most_significant_q_limb; -} |