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
 44mpi_limb_t
 45mpihelp_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	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		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			d = dp[0];
 67			n1 = np[nsize - 1];
 68
 69			if (n1 >= d) {
 70				n1 -= d;
 71				most_significant_q_limb = 1;
 72			}
 73
 74			qp += qextra_limbs;
 75			for (i = nsize - 2; i >= 0; i--)
 76				udiv_qrnnd(qp[i], n1, n1, np[i], d);
 77			qp -= qextra_limbs;
 78
 79			for (i = qextra_limbs - 1; i >= 0; i--)
 80				udiv_qrnnd(qp[i], n1, n1, 0, d);
 81
 82			np[0] = n1;
 83		}
 84		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			np += nsize - 2;
 93			d1 = dp[1];
 94			d0 = dp[0];
 95			n1 = np[1];
 96			n0 = np[0];
 97
 98			if (n1 >= d1 && (n1 > d1 || n0 >= d0)) {
 99				sub_ddmmss(n1, n0, n1, n0, d1, d0);
100				most_significant_q_limb = 1;
101			}
102
103			for (i = qextra_limbs + nsize - 2 - 1; i >= 0; i--) {
104				mpi_limb_t q;
105				mpi_limb_t r;
106
107				if (i >= qextra_limbs)
108					np--;
109				else
110					np[0] = 0;
111
112				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					r = n0 + d1;
119					if (r < d1) {	/* Carry in the addition? */
120						add_ssaaaa(n1, n0, r - d0,
121							   np[0], 0, d0);
122						qp[i] = q;
123						continue;
124					}
125					n1 = d0 - (d0 != 0 ? 1 : 0);
126					n0 = -d0;
127				} else {
128					udiv_qrnnd(q, r, n1, n0, d1);
129					umul_ppmm(n1, n0, d0, q);
130				}
131
132				n2 = np[0];
133q_test:
134				if (n1 > r || (n1 == r && n0 > n2)) {
135					/* The estimated Q was too large.  */
136					q--;
137					sub_ddmmss(n1, n0, n1, n0, 0, d0);
138					r += d1;
139					if (r >= d1)	/* If not carry, test Q again.  */
140						goto q_test;
141				}
142
143				qp[i] = q;
144				sub_ddmmss(n1, n0, r, n2, n1, n0);
145			}
146			np[1] = n1;
147			np[0] = n0;
148		}
149		break;
150
151	default:
152		{
153			mpi_size_t i;
154			mpi_limb_t dX, d1, n0;
155
156			np += nsize - dsize;
157			dX = dp[dsize - 1];
158			d1 = dp[dsize - 2];
159			n0 = np[dsize - 1];
160
161			if (n0 >= dX) {
162				if (n0 > dX
163				    || mpihelp_cmp(np, dp, dsize - 1) >= 0) {
164					mpihelp_sub_n(np, np, dp, dsize);
165					n0 = np[dsize - 1];
166					most_significant_q_limb = 1;
167				}
168			}
169
170			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				if (i >= qextra_limbs) {
176					np--;
177					n2 = np[dsize];
178				} else {
179					n2 = np[dsize - 1];
180					MPN_COPY_DECR(np + 1, np, dsize - 1);
181					np[0] = 0;
182				}
183
184				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					udiv_qrnnd(q, r, n0, np[dsize - 1], dX);
192					umul_ppmm(n1, n0, d1, q);
193
194					while (n1 > r
195					       || (n1 == r
196						   && n0 > np[dsize - 2])) {
197						q--;
198						r += dX;
199						if (r < dX)	/* I.e. "carry in previous addition?" */
200							break;
201						n1 -= n0 < d1;
202						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				cy_limb = mpihelp_submul_1(np, dp, dsize, q);
210
211				if (n2 != cy_limb) {
212					mpihelp_add_n(np, np, dp, dsize);
213					q--;
214				}
215
216				qp[i] = q;
217				n0 = np[dsize - 1];
218			}
219		}
220	}
221
222	return most_significant_q_limb;
223}