Fix year 2039 bug for localtime with 64-bit time_t (bug 22639).
[glibc.git] / stdlib / divmod_1.c
blob91feee5d4f9ca8d67d97c6724465fc5b708c6feb
1 /* mpn_divmod_1(quot_ptr, dividend_ptr, dividend_size, divisor_limb) --
2 Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB.
3 Write DIVIDEND_SIZE limbs of quotient at QUOT_PTR.
4 Return the single-limb remainder.
5 There are no constraints on the value of the divisor.
7 QUOT_PTR and DIVIDEND_PTR might point to the same limb.
9 Copyright (C) 1991-2018 Free Software Foundation, Inc.
11 This file is part of the GNU MP Library.
13 The GNU MP Library is free software; you can redistribute it and/or modify
14 it under the terms of the GNU Lesser General Public License as published by
15 the Free Software Foundation; either version 2.1 of the License, or (at your
16 option) any later version.
18 The GNU MP Library is distributed in the hope that it will be useful, but
19 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
20 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
21 License for more details.
23 You should have received a copy of the GNU Lesser General Public License
24 along with the GNU MP Library; see the file COPYING.LIB. If not, see
25 <http://www.gnu.org/licenses/>. */
27 #include <gmp.h>
28 #include "gmp-impl.h"
29 #include "longlong.h"
31 #ifndef UMUL_TIME
32 #define UMUL_TIME 1
33 #endif
35 #ifndef UDIV_TIME
36 #define UDIV_TIME UMUL_TIME
37 #endif
39 /* FIXME: We should be using invert_limb (or invert_normalized_limb)
40 here (not udiv_qrnnd). */
42 mp_limb_t
43 mpn_divmod_1 (mp_ptr quot_ptr,
44 mp_srcptr dividend_ptr, mp_size_t dividend_size,
45 mp_limb_t divisor_limb)
47 mp_size_t i;
48 mp_limb_t n1, n0, r;
49 mp_limb_t dummy __attribute__ ((unused));
51 /* ??? Should this be handled at all? Rely on callers? */
52 if (dividend_size == 0)
53 return 0;
55 /* If multiplication is much faster than division, and the
56 dividend is large, pre-invert the divisor, and use
57 only multiplications in the inner loop. */
59 /* This test should be read:
60 Does it ever help to use udiv_qrnnd_preinv?
61 && Does what we save compensate for the inversion overhead? */
62 if (UDIV_TIME > (2 * UMUL_TIME + 6)
63 && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME)
65 int normalization_steps;
67 count_leading_zeros (normalization_steps, divisor_limb);
68 if (normalization_steps != 0)
70 mp_limb_t divisor_limb_inverted;
72 divisor_limb <<= normalization_steps;
74 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
75 result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
76 most significant bit (with weight 2**N) implicit. */
78 /* Special case for DIVISOR_LIMB == 100...000. */
79 if (divisor_limb << 1 == 0)
80 divisor_limb_inverted = ~(mp_limb_t) 0;
81 else
82 udiv_qrnnd (divisor_limb_inverted, dummy,
83 -divisor_limb, 0, divisor_limb);
85 n1 = dividend_ptr[dividend_size - 1];
86 r = n1 >> (BITS_PER_MP_LIMB - normalization_steps);
88 /* Possible optimization:
89 if (r == 0
90 && divisor_limb > ((n1 << normalization_steps)
91 | (dividend_ptr[dividend_size - 2] >> ...)))
92 ...one division less... */
94 for (i = dividend_size - 2; i >= 0; i--)
96 n0 = dividend_ptr[i];
97 udiv_qrnnd_preinv (quot_ptr[i + 1], r, r,
98 ((n1 << normalization_steps)
99 | (n0 >> (BITS_PER_MP_LIMB - normalization_steps))),
100 divisor_limb, divisor_limb_inverted);
101 n1 = n0;
103 udiv_qrnnd_preinv (quot_ptr[0], r, r,
104 n1 << normalization_steps,
105 divisor_limb, divisor_limb_inverted);
106 return r >> normalization_steps;
108 else
110 mp_limb_t divisor_limb_inverted;
112 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
113 result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
114 most significant bit (with weight 2**N) implicit. */
116 /* Special case for DIVISOR_LIMB == 100...000. */
117 if (divisor_limb << 1 == 0)
118 divisor_limb_inverted = ~(mp_limb_t) 0;
119 else
120 udiv_qrnnd (divisor_limb_inverted, dummy,
121 -divisor_limb, 0, divisor_limb);
123 i = dividend_size - 1;
124 r = dividend_ptr[i];
126 if (r >= divisor_limb)
127 r = 0;
128 else
130 quot_ptr[i] = 0;
131 i--;
134 for (; i >= 0; i--)
136 n0 = dividend_ptr[i];
137 udiv_qrnnd_preinv (quot_ptr[i], r, r,
138 n0, divisor_limb, divisor_limb_inverted);
140 return r;
143 else
145 if (UDIV_NEEDS_NORMALIZATION)
147 int normalization_steps;
149 count_leading_zeros (normalization_steps, divisor_limb);
150 if (normalization_steps != 0)
152 divisor_limb <<= normalization_steps;
154 n1 = dividend_ptr[dividend_size - 1];
155 r = n1 >> (BITS_PER_MP_LIMB - normalization_steps);
157 /* Possible optimization:
158 if (r == 0
159 && divisor_limb > ((n1 << normalization_steps)
160 | (dividend_ptr[dividend_size - 2] >> ...)))
161 ...one division less... */
163 for (i = dividend_size - 2; i >= 0; i--)
165 n0 = dividend_ptr[i];
166 udiv_qrnnd (quot_ptr[i + 1], r, r,
167 ((n1 << normalization_steps)
168 | (n0 >> (BITS_PER_MP_LIMB - normalization_steps))),
169 divisor_limb);
170 n1 = n0;
172 udiv_qrnnd (quot_ptr[0], r, r,
173 n1 << normalization_steps,
174 divisor_limb);
175 return r >> normalization_steps;
178 /* No normalization needed, either because udiv_qrnnd doesn't require
179 it, or because DIVISOR_LIMB is already normalized. */
181 i = dividend_size - 1;
182 r = dividend_ptr[i];
184 if (r >= divisor_limb)
185 r = 0;
186 else
188 quot_ptr[i] = 0;
189 i--;
192 for (; i >= 0; i--)
194 n0 = dividend_ptr[i];
195 udiv_qrnnd (quot_ptr[i], r, r, n0, divisor_limb);
197 return r;