Commit | Line | Data |
---|---|---|
7e8dec91 DK |
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 | ||
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 | ||
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 | ||
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 | ||
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 | ||
132 | int mpi_tdiv_r(MPI rem, MPI num, MPI den) | |
133 | { | |
134 | return mpi_tdiv_qr(NULL, rem, num, den); | |
135 | } | |
136 | ||
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 | ||
e2fe85c2 DK |
152 | if (!dsize) |
153 | return -EINVAL; | |
154 | ||
7e8dec91 DK |
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); | |
43b2c0ae DK |
213 | if (!np) |
214 | goto nomem; | |
7e8dec91 DK |
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 | ||
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 | */ | |
335 | int mpi_divisible_ui(MPI dividend, ulong divisor) | |
336 | { | |
337 | return !mpihelp_mod_1(dividend->d, dividend->nlimbs, divisor); | |
338 | } |