1 /* mpn_mod_1(dividend_ptr, dividend_size, divisor_limb) --
2 Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB.
3 Return the single-limb remainder.
4 There are no constraints on the value of the divisor.
6 QUOT_PTR and DIVIDEND_PTR might point to the same limb.
8 Copyright (C) 1991, 1992 Free Software Foundation, Inc.
10 This file is part of the GNU MP Library.
12 The GNU MP Library is free software; you can redistribute it and/or modify
13 it under the terms of the GNU General Public License as published by
14 the Free Software Foundation; either version 2, or (at your option)
17 The GNU MP Library is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License for more details.
22 You should have received a copy of the GNU General Public License
23 along with the GNU MP Library; see the file COPYING. If not, write to
24 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
32 mpn_mod_1 (mp_srcptr dividend_ptr, mp_size dividend_size,
33 unsigned long int divisor_limb)
35 mpn_mod_1 (dividend_ptr, dividend_size, divisor_limb)
36 mp_srcptr dividend_ptr;
37 mp_size dividend_size;
38 unsigned long int divisor_limb;
41 int normalization_steps;
46 /* Botch: Should this be handled at all? Rely on callers? */
47 if (dividend_size == 0)
50 if (UDIV_NEEDS_NORMALIZATION)
52 count_leading_zeros (normalization_steps, divisor_limb);
53 if (normalization_steps != 0)
55 divisor_limb <<= normalization_steps;
57 n1 = dividend_ptr[dividend_size - 1];
58 r = n1 >> (BITS_PER_MP_LIMB - normalization_steps);
60 /* Possible optimization:
62 && divisor_limb > ((n1 << normalization_steps)
63 | (dividend_ptr[dividend_size - 2] >> ...)))
64 ...one division less...
67 for (i = dividend_size - 2; i >= 0; i--)
70 udiv_qrnnd (dummy, r, r,
71 ((n1 << normalization_steps)
72 | (n0 >> (BITS_PER_MP_LIMB - normalization_steps))),
76 udiv_qrnnd (dummy, r, r,
77 n1 << normalization_steps,
79 return r >> normalization_steps;
83 /* No normalization needed, either because udiv_qrnnd doesn't require
84 it, or because DIVISOR_LIMB is already normalized. */
86 i = dividend_size - 1;
89 if (r >= divisor_limb)
100 n0 = dividend_ptr[i];
101 udiv_qrnnd (dummy, r, r, n0, divisor_limb);