Lines Matching +full:carry +full:- +full:less
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* mpihelp-div.c - MPI helper functions
17 #include "mpi-internal.h"
41 * dividend is large, pre-invert the divisor, and use in mpihelp_mod_1()
49 && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) { in mpihelp_mod_1()
58 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The in mpihelp_mod_1()
59 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the in mpihelp_mod_1()
68 -divisor_limb, 0, divisor_limb); in mpihelp_mod_1()
70 n1 = dividend_ptr[dividend_size - 1]; in mpihelp_mod_1()
71 r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps); in mpihelp_mod_1()
76 * | (dividend_ptr[dividend_size - 2] >> ...))) in mpihelp_mod_1()
77 * ...one division less... in mpihelp_mod_1()
79 for (i = dividend_size - 2; i >= 0; i--) { in mpihelp_mod_1()
83 | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))), in mpihelp_mod_1()
94 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The in mpihelp_mod_1()
95 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the in mpihelp_mod_1()
104 -divisor_limb, 0, divisor_limb); in mpihelp_mod_1()
106 i = dividend_size - 1; in mpihelp_mod_1()
112 i--; in mpihelp_mod_1()
114 for ( ; i >= 0; i--) { in mpihelp_mod_1()
129 n1 = dividend_ptr[dividend_size - 1]; in mpihelp_mod_1()
130 r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps); in mpihelp_mod_1()
135 * | (dividend_ptr[dividend_size - 2] >> ...))) in mpihelp_mod_1()
136 * ...one division less... in mpihelp_mod_1()
138 for (i = dividend_size - 2; i >= 0; i--) { in mpihelp_mod_1()
142 | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))), in mpihelp_mod_1()
155 i = dividend_size - 1; in mpihelp_mod_1()
161 i--; in mpihelp_mod_1()
163 for (; i >= 0; i--) { in mpihelp_mod_1()
172 * the NSIZE-DSIZE least significant quotient limbs at QP
174 * non-zero, generate that many fraction bits and append them after the
185 * 3. NSIZE >= DSIZE, even if QEXTRA_LIMBS is non-zero.
211 n1 = np[nsize - 1]; in mpihelp_divrem()
214 n1 -= d; in mpihelp_divrem()
219 for (i = nsize - 2; i >= 0; i--) in mpihelp_divrem()
221 qp -= qextra_limbs; in mpihelp_divrem()
223 for (i = qextra_limbs - 1; i >= 0; i--) in mpihelp_divrem()
236 np += nsize - 2; in mpihelp_divrem()
247 for (i = qextra_limbs + nsize - 2 - 1; i >= 0; i--) { in mpihelp_divrem()
252 np--; in mpihelp_divrem()
263 if (r < d1) { /* Carry in the addition? */ in mpihelp_divrem()
264 add_ssaaaa(n1, n0, r - d0, in mpihelp_divrem()
269 n1 = d0 - (d0 != 0 ? 1 : 0); in mpihelp_divrem()
270 n0 = -d0; in mpihelp_divrem()
280 q--; in mpihelp_divrem()
283 if (r >= d1) /* If not carry, test Q again. */ in mpihelp_divrem()
300 np += nsize - dsize; in mpihelp_divrem()
301 dX = dp[dsize - 1]; in mpihelp_divrem()
302 d1 = dp[dsize - 2]; in mpihelp_divrem()
303 n0 = np[dsize - 1]; in mpihelp_divrem()
307 || mpihelp_cmp(np, dp, dsize - 1) >= 0) { in mpihelp_divrem()
309 n0 = np[dsize - 1]; in mpihelp_divrem()
314 for (i = qextra_limbs + nsize - dsize - 1; i >= 0; i--) { in mpihelp_divrem()
320 np--; in mpihelp_divrem()
323 n2 = np[dsize - 1]; in mpihelp_divrem()
324 MPN_COPY_DECR(np + 1, np, dsize - 1); in mpihelp_divrem()
329 /* This might over-estimate q, but it's probably not worth in mpihelp_divrem()
335 udiv_qrnnd(q, r, n0, np[dsize - 1], dX); in mpihelp_divrem()
340 && n0 > np[dsize - 2])) { in mpihelp_divrem()
341 q--; in mpihelp_divrem()
343 if (r < dX) /* I.e. "carry in previous addition?" */ in mpihelp_divrem()
345 n1 -= n0 < d1; in mpihelp_divrem()
346 n0 -= d1; in mpihelp_divrem()
352 * could make this loop make two iterations less. */ in mpihelp_divrem()
357 q--; in mpihelp_divrem()
361 n0 = np[dsize - 1]; in mpihelp_divrem()
372 * Return the single-limb remainder.
391 * dividend is large, pre-invert the divisor, and use in mpihelp_divmod_1()
399 && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) { in mpihelp_divmod_1()
408 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The in mpihelp_divmod_1()
409 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the in mpihelp_divmod_1()
417 -divisor_limb, 0, divisor_limb); in mpihelp_divmod_1()
419 n1 = dividend_ptr[dividend_size - 1]; in mpihelp_divmod_1()
420 r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps); in mpihelp_divmod_1()
425 * | (dividend_ptr[dividend_size - 2] >> ...))) in mpihelp_divmod_1()
426 * ...one division less... in mpihelp_divmod_1()
428 for (i = dividend_size - 2; i >= 0; i--) { in mpihelp_divmod_1()
432 | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))), in mpihelp_divmod_1()
443 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The in mpihelp_divmod_1()
444 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the in mpihelp_divmod_1()
452 -divisor_limb, 0, divisor_limb); in mpihelp_divmod_1()
454 i = dividend_size - 1; in mpihelp_divmod_1()
460 quot_ptr[i--] = 0; in mpihelp_divmod_1()
462 for ( ; i >= 0; i--) { in mpihelp_divmod_1()
477 n1 = dividend_ptr[dividend_size - 1]; in mpihelp_divmod_1()
478 r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps); in mpihelp_divmod_1()
483 * | (dividend_ptr[dividend_size - 2] >> ...))) in mpihelp_divmod_1()
484 * ...one division less... in mpihelp_divmod_1()
486 for (i = dividend_size - 2; i >= 0; i--) { in mpihelp_divmod_1()
490 | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))), in mpihelp_divmod_1()
503 i = dividend_size - 1; in mpihelp_divmod_1()
509 quot_ptr[i--] = 0; in mpihelp_divmod_1()
511 for (; i >= 0; i--) { in mpihelp_divmod_1()