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.
4 *
5 * This file is part of GnuPG.
6 *
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.
11 *
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.
16 *
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
20 *
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.
28 */
29
30 #include <linux/string.h>
31 #include "mpi-internal.h"
32 #include "longlong.h"
33
mpi_fdiv_r(MPI rem,MPI dividend,MPI divisor)34 int mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor)
35 {
36 int rc = -ENOMEM;
37 int divisor_sign = divisor->sign;
38 MPI temp_divisor = NULL;
39
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. */
43 if (rem == divisor) {
44 if (mpi_copy(&temp_divisor, divisor) < 0)
45 goto nomem;
46 divisor = temp_divisor;
47 }
48
49 if (mpi_tdiv_qr(NULL, rem, dividend, divisor) < 0)
50 goto nomem;
51 if (((divisor_sign ? 1 : 0) ^ (dividend->sign ? 1 : 0)) && rem->nlimbs)
52 if (mpi_add(rem, rem, divisor) < 0)
53 goto nomem;
54
55 rc = 0;
56
57 nomem:
58 if (temp_divisor)
59 mpi_free(temp_divisor);
60 return rc;
61 }
62
63 /****************
64 * Division rounding the quotient towards -infinity.
65 * The remainder gets the same sign as the denominator.
66 * rem is optional
67 */
68
mpi_fdiv_r_ui(MPI rem,MPI dividend,ulong divisor)69 ulong mpi_fdiv_r_ui(MPI rem, MPI dividend, ulong divisor)
70 {
71 mpi_limb_t rlimb;
72
73 rlimb = mpihelp_mod_1(dividend->d, dividend->nlimbs, divisor);
74 if (rlimb && dividend->sign)
75 rlimb = divisor - rlimb;
76
77 if (rem) {
78 rem->d[0] = rlimb;
79 rem->nlimbs = rlimb ? 1 : 0;
80 }
81 return rlimb;
82 }
83
mpi_fdiv_q(MPI quot,MPI dividend,MPI divisor)84 int mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor)
85 {
86 MPI tmp = mpi_alloc(mpi_get_nlimbs(quot));
87 if (!tmp)
88 return -ENOMEM;
89 mpi_fdiv_qr(quot, tmp, dividend, divisor);
90 mpi_free(tmp);
91 return 0;
92 }
93
mpi_fdiv_qr(MPI quot,MPI rem,MPI dividend,MPI divisor)94 int mpi_fdiv_qr(MPI quot, MPI rem, MPI dividend, MPI divisor)
95 {
96 int divisor_sign = divisor->sign;
97 MPI temp_divisor = NULL;
98
99 if (quot == divisor || rem == divisor) {
100 if (mpi_copy(&temp_divisor, divisor) < 0)
101 return -ENOMEM;
102 divisor = temp_divisor;
103 }
104
105 if (mpi_tdiv_qr(quot, rem, dividend, divisor) < 0)
106 goto nomem;
107
108 if ((divisor_sign ^ dividend->sign) && rem->nlimbs) {
109 if (mpi_sub_ui(quot, quot, 1) < 0)
110 goto nomem;
111 if (mpi_add(rem, rem, divisor) < 0)
112 goto nomem;
113 }
114
115 if (temp_divisor)
116 mpi_free(temp_divisor);
117
118 return 0;
119
120 nomem:
121 mpi_free(temp_divisor);
122 return -ENOMEM;
123 }
124
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.
130 */
131
mpi_tdiv_r(MPI rem,MPI num,MPI den)132 int mpi_tdiv_r(MPI rem, MPI num, MPI den)
133 {
134 return mpi_tdiv_qr(NULL, rem, num, den);
135 }
136
mpi_tdiv_qr(MPI quot,MPI rem,MPI num,MPI den)137 int mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den)
138 {
139 int rc = -ENOMEM;
140 mpi_ptr_t np, dp;
141 mpi_ptr_t qp, rp;
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;
148 mpi_limb_t q_limb;
149 mpi_ptr_t marker[5];
150 int markidx = 0;
151
152 if (!dsize)
153 return -EINVAL;
154
155 memset(marker, 0, sizeof(marker));
156
157 /* Ensure space is enough for quotient and remainder.
158 * We need space for an extra limb in the remainder, because it's
159 * up-shifted (normalized) below. */
160 rsize = nsize + 1;
161 if (mpi_resize(rem, rsize) < 0)
162 goto nomem;
163
164 qsize = rsize - dsize; /* qsize cannot be bigger than this. */
165 if (qsize <= 0) {
166 if (num != rem) {
167 rem->nlimbs = num->nlimbs;
168 rem->sign = num->sign;
169 MPN_COPY(rem->d, num->d, nsize);
170 }
171 if (quot) {
172 /* This needs to follow the assignment to rem, in case the
173 * numerator and quotient are the same. */
174 quot->nlimbs = 0;
175 quot->sign = 0;
176 }
177 return 0;
178 }
179
180 if (quot)
181 if (mpi_resize(quot, qsize) < 0)
182 goto nomem;
183
184 /* Read pointers here, when reallocation is finished. */
185 np = num->d;
186 dp = den->d;
187 rp = rem->d;
188
189 /* Optimize division by a single-limb divisor. */
190 if (dsize == 1) {
191 mpi_limb_t rlimb;
192 if (quot) {
193 qp = quot->d;
194 rlimb = mpihelp_divmod_1(qp, np, nsize, dp[0]);
195 qsize -= qp[qsize - 1] == 0;
196 quot->nlimbs = qsize;
197 quot->sign = sign_quotient;
198 } else
199 rlimb = mpihelp_mod_1(np, nsize, dp[0]);
200 rp[0] = rlimb;
201 rsize = rlimb != 0 ? 1 : 0;
202 rem->nlimbs = rsize;
203 rem->sign = sign_remainder;
204 return 0;
205 }
206
207 if (quot) {
208 qp = quot->d;
209 /* Make sure QP and NP point to different objects. Otherwise the
210 * numerator would be gradually overwritten by the quotient limbs. */
211 if (qp == np) { /* Copy NP object to temporary space. */
212 np = marker[markidx++] = mpi_alloc_limb_space(nsize);
213 if (!np)
214 goto nomem;
215 MPN_COPY(np, qp, nsize);
216 }
217 } else /* Put quotient at top of remainder. */
218 qp = rp + dsize;
219
220 count_leading_zeros(normalization_steps, dp[dsize - 1]);
221
222 /* Normalize the denominator, i.e. make its most significant bit set by
223 * shifting it NORMALIZATION_STEPS bits to the left. Also shift the
224 * numerator the same number of steps (to keep the quotient the same!).
225 */
226 if (normalization_steps) {
227 mpi_ptr_t tp;
228 mpi_limb_t nlimb;
229
230 /* Shift up the denominator setting the most significant bit of
231 * the most significant word. Use temporary storage not to clobber
232 * the original contents of the denominator. */
233 tp = marker[markidx++] = mpi_alloc_limb_space(dsize);
234 if (!tp)
235 goto nomem;
236 mpihelp_lshift(tp, dp, dsize, normalization_steps);
237 dp = tp;
238
239 /* Shift up the numerator, possibly introducing a new most
240 * significant word. Move the shifted numerator in the remainder
241 * meanwhile. */
242 nlimb = mpihelp_lshift(rp, np, nsize, normalization_steps);
243 if (nlimb) {
244 rp[nsize] = nlimb;
245 rsize = nsize + 1;
246 } else
247 rsize = nsize;
248 } else {
249 /* The denominator is already normalized, as required. Copy it to
250 * temporary space if it overlaps with the quotient or remainder. */
251 if (dp == rp || (quot && (dp == qp))) {
252 mpi_ptr_t tp;
253
254 tp = marker[markidx++] = mpi_alloc_limb_space(dsize);
255 if (!tp)
256 goto nomem;
257 MPN_COPY(tp, dp, dsize);
258 dp = tp;
259 }
260
261 /* Move the numerator to the remainder. */
262 if (rp != np)
263 MPN_COPY(rp, np, nsize);
264
265 rsize = nsize;
266 }
267
268 q_limb = mpihelp_divrem(qp, 0, rp, rsize, dp, dsize);
269
270 if (quot) {
271 qsize = rsize - dsize;
272 if (q_limb) {
273 qp[qsize] = q_limb;
274 qsize += 1;
275 }
276
277 quot->nlimbs = qsize;
278 quot->sign = sign_quotient;
279 }
280
281 rsize = dsize;
282 MPN_NORMALIZE(rp, rsize);
283
284 if (normalization_steps && rsize) {
285 mpihelp_rshift(rp, rp, rsize, normalization_steps);
286 rsize -= rp[rsize - 1] == 0 ? 1 : 0;
287 }
288
289 rem->nlimbs = rsize;
290 rem->sign = sign_remainder;
291
292 rc = 0;
293 nomem:
294 while (markidx)
295 mpi_free_limb_space(marker[--markidx]);
296 return rc;
297 }
298
mpi_tdiv_q_2exp(MPI w,MPI u,unsigned count)299 int mpi_tdiv_q_2exp(MPI w, MPI u, unsigned count)
300 {
301 mpi_size_t usize, wsize;
302 mpi_size_t limb_cnt;
303
304 usize = u->nlimbs;
305 limb_cnt = count / BITS_PER_MPI_LIMB;
306 wsize = usize - limb_cnt;
307 if (limb_cnt >= usize)
308 w->nlimbs = 0;
309 else {
310 mpi_ptr_t wp;
311 mpi_ptr_t up;
312
313 if (RESIZE_IF_NEEDED(w, wsize) < 0)
314 return -ENOMEM;
315 wp = w->d;
316 up = u->d;
317
318 count %= BITS_PER_MPI_LIMB;
319 if (count) {
320 mpihelp_rshift(wp, up + limb_cnt, wsize, count);
321 wsize -= !wp[wsize - 1];
322 } else {
323 MPN_COPY_INCR(wp, up + limb_cnt, wsize);
324 }
325
326 w->nlimbs = wsize;
327 }
328 return 0;
329 }
330
331 /****************
332 * Check whether dividend is divisible by divisor
333 * (note: divisor must fit into a limb)
334 */
mpi_divisible_ui(MPI dividend,ulong divisor)335 int mpi_divisible_ui(MPI dividend, ulong divisor)
336 {
337 return !mpihelp_mod_1(dividend->d, dividend->nlimbs, divisor);
338 }
339