1 /* mpi-div.c - MPI functions
2 * Copyright (C) 1994, 1996 Free Software Foundation, Inc.
3 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
5 * This file is part of GnuPG.
7 * GnuPG is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * GnuPG is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
21 * Note: This code is heavily based on the GNU MP Library.
22 * Actually it's the same code with only minor changes in the
23 * way the data is stored; this is to support the abstraction
24 * of an optional secure memory allocation which may be used
25 * to avoid revealing of sensitive data due to paging etc.
26 * The GNU MP Library itself is published under the LGPL;
27 * however I decided to publish this code under the plain GPL.
30 #include <linux/string.h>
31 #include "mpi-internal.h"
34 int mpi_fdiv_r(MPI rem
, MPI dividend
, MPI divisor
)
37 int divisor_sign
= divisor
->sign
;
38 MPI temp_divisor
= NULL
;
40 /* We need the original value of the divisor after the remainder has been
41 * preliminary calculated. We have to copy it to temporary space if it's
42 * the same variable as REM. */
44 if (mpi_copy(&temp_divisor
, divisor
) < 0)
46 divisor
= temp_divisor
;
49 if (mpi_tdiv_qr(NULL
, rem
, dividend
, divisor
) < 0)
51 if (((divisor_sign
? 1 : 0) ^ (dividend
->sign
? 1 : 0)) && rem
->nlimbs
)
52 if (mpi_add(rem
, rem
, divisor
) < 0)
59 mpi_free(temp_divisor
);
64 * Division rounding the quotient towards -infinity.
65 * The remainder gets the same sign as the denominator.
69 ulong
mpi_fdiv_r_ui(MPI rem
, MPI dividend
, ulong divisor
)
73 rlimb
= mpihelp_mod_1(dividend
->d
, dividend
->nlimbs
, divisor
);
74 if (rlimb
&& dividend
->sign
)
75 rlimb
= divisor
- rlimb
;
79 rem
->nlimbs
= rlimb
? 1 : 0;
84 int mpi_fdiv_q(MPI quot
, MPI dividend
, MPI divisor
)
86 MPI tmp
= mpi_alloc(mpi_get_nlimbs(quot
));
89 mpi_fdiv_qr(quot
, tmp
, dividend
, divisor
);
94 int mpi_fdiv_qr(MPI quot
, MPI rem
, MPI dividend
, MPI divisor
)
96 int divisor_sign
= divisor
->sign
;
97 MPI temp_divisor
= NULL
;
99 if (quot
== divisor
|| rem
== divisor
) {
100 if (mpi_copy(&temp_divisor
, divisor
) < 0)
102 divisor
= temp_divisor
;
105 if (mpi_tdiv_qr(quot
, rem
, dividend
, divisor
) < 0)
108 if ((divisor_sign
^ dividend
->sign
) && rem
->nlimbs
) {
109 if (mpi_sub_ui(quot
, quot
, 1) < 0)
111 if (mpi_add(rem
, rem
, divisor
) < 0)
116 mpi_free(temp_divisor
);
121 mpi_free(temp_divisor
);
125 /* If den == quot, den needs temporary storage.
126 * If den == rem, den needs temporary storage.
127 * If num == quot, num needs temporary storage.
128 * If den has temporary storage, it can be normalized while being copied,
129 * i.e no extra storage should be allocated.
132 int mpi_tdiv_r(MPI rem
, MPI num
, MPI den
)
134 return mpi_tdiv_qr(NULL
, rem
, num
, den
);
137 int mpi_tdiv_qr(MPI quot
, MPI rem
, MPI num
, MPI den
)
142 mpi_size_t nsize
= num
->nlimbs
;
143 mpi_size_t dsize
= den
->nlimbs
;
144 mpi_size_t qsize
, rsize
;
145 mpi_size_t sign_remainder
= num
->sign
;
146 mpi_size_t sign_quotient
= num
->sign
^ den
->sign
;
147 unsigned normalization_steps
;
152 memset(marker
, 0, sizeof(marker
));
154 /* Ensure space is enough for quotient and remainder.
155 * We need space for an extra limb in the remainder, because it's
156 * up-shifted (normalized) below. */
158 if (mpi_resize(rem
, rsize
) < 0)
161 qsize
= rsize
- dsize
; /* qsize cannot be bigger than this. */
164 rem
->nlimbs
= num
->nlimbs
;
165 rem
->sign
= num
->sign
;
166 MPN_COPY(rem
->d
, num
->d
, nsize
);
169 /* This needs to follow the assignment to rem, in case the
170 * numerator and quotient are the same. */
178 if (mpi_resize(quot
, qsize
) < 0)
181 /* Read pointers here, when reallocation is finished. */
186 /* Optimize division by a single-limb divisor. */
191 rlimb
= mpihelp_divmod_1(qp
, np
, nsize
, dp
[0]);
192 qsize
-= qp
[qsize
- 1] == 0;
193 quot
->nlimbs
= qsize
;
194 quot
->sign
= sign_quotient
;
196 rlimb
= mpihelp_mod_1(np
, nsize
, dp
[0]);
198 rsize
= rlimb
!= 0 ? 1 : 0;
200 rem
->sign
= sign_remainder
;
206 /* Make sure QP and NP point to different objects. Otherwise the
207 * numerator would be gradually overwritten by the quotient limbs. */
208 if (qp
== np
) { /* Copy NP object to temporary space. */
209 np
= marker
[markidx
++] = mpi_alloc_limb_space(nsize
);
210 MPN_COPY(np
, qp
, nsize
);
212 } else /* Put quotient at top of remainder. */
215 count_leading_zeros(normalization_steps
, dp
[dsize
- 1]);
217 /* Normalize the denominator, i.e. make its most significant bit set by
218 * shifting it NORMALIZATION_STEPS bits to the left. Also shift the
219 * numerator the same number of steps (to keep the quotient the same!).
221 if (normalization_steps
) {
225 /* Shift up the denominator setting the most significant bit of
226 * the most significant word. Use temporary storage not to clobber
227 * the original contents of the denominator. */
228 tp
= marker
[markidx
++] = mpi_alloc_limb_space(dsize
);
231 mpihelp_lshift(tp
, dp
, dsize
, normalization_steps
);
234 /* Shift up the numerator, possibly introducing a new most
235 * significant word. Move the shifted numerator in the remainder
237 nlimb
= mpihelp_lshift(rp
, np
, nsize
, normalization_steps
);
244 /* The denominator is already normalized, as required. Copy it to
245 * temporary space if it overlaps with the quotient or remainder. */
246 if (dp
== rp
|| (quot
&& (dp
== qp
))) {
249 tp
= marker
[markidx
++] = mpi_alloc_limb_space(dsize
);
252 MPN_COPY(tp
, dp
, dsize
);
256 /* Move the numerator to the remainder. */
258 MPN_COPY(rp
, np
, nsize
);
263 q_limb
= mpihelp_divrem(qp
, 0, rp
, rsize
, dp
, dsize
);
266 qsize
= rsize
- dsize
;
272 quot
->nlimbs
= qsize
;
273 quot
->sign
= sign_quotient
;
277 MPN_NORMALIZE(rp
, rsize
);
279 if (normalization_steps
&& rsize
) {
280 mpihelp_rshift(rp
, rp
, rsize
, normalization_steps
);
281 rsize
-= rp
[rsize
- 1] == 0 ? 1 : 0;
285 rem
->sign
= sign_remainder
;
290 mpi_free_limb_space(marker
[--markidx
]);
294 int mpi_tdiv_q_2exp(MPI w
, MPI u
, unsigned count
)
296 mpi_size_t usize
, wsize
;
300 limb_cnt
= count
/ BITS_PER_MPI_LIMB
;
301 wsize
= usize
- limb_cnt
;
302 if (limb_cnt
>= usize
)
308 if (RESIZE_IF_NEEDED(w
, wsize
) < 0)
313 count
%= BITS_PER_MPI_LIMB
;
315 mpihelp_rshift(wp
, up
+ limb_cnt
, wsize
, count
);
316 wsize
-= !wp
[wsize
- 1];
318 MPN_COPY_INCR(wp
, up
+ limb_cnt
, wsize
);
327 * Check whether dividend is divisible by divisor
328 * (note: divisor must fit into a limb)
330 int mpi_divisible_ui(MPI dividend
, ulong divisor
)
332 return !mpihelp_mod_1(dividend
->d
, dividend
->nlimbs
, divisor
);