Line data Source code
1 : /* mpi-div.c - MPI functions
2 : * Copyright (C) 1994, 1996, 1998, 2001, 2002,
3 : * 2003 Free Software Foundation, Inc.
4 : *
5 : * This file is part of Libgcrypt.
6 : *
7 : * Libgcrypt is free software; you can redistribute it and/or modify
8 : * it under the terms of the GNU Lesser General Public License as
9 : * published by the Free Software Foundation; either version 2.1 of
10 : * the License, or (at your option) any later version.
11 : *
12 : * Libgcrypt 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 Lesser General Public License for more details.
16 : *
17 : * You should have received a copy of the GNU Lesser General Public
18 : * License 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 : */
27 :
28 : #include <config.h>
29 : #include <stdio.h>
30 : #include <stdlib.h>
31 : #include "mpi-internal.h"
32 : #include "longlong.h"
33 : #include "g10lib.h"
34 :
35 :
36 : void
37 32855222 : _gcry_mpi_fdiv_r( gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor )
38 : {
39 32855222 : int divisor_sign = divisor->sign;
40 32855222 : gcry_mpi_t temp_divisor = NULL;
41 :
42 : /* We need the original value of the divisor after the remainder has been
43 : * preliminary calculated. We have to copy it to temporary space if it's
44 : * the same variable as REM. */
45 32855222 : if( rem == divisor ) {
46 4386 : temp_divisor = mpi_copy( divisor );
47 4386 : divisor = temp_divisor;
48 : }
49 :
50 32855222 : _gcry_mpi_tdiv_r( rem, dividend, divisor );
51 :
52 32855222 : if( ((divisor_sign?1:0) ^ (dividend->sign?1:0)) && rem->nlimbs )
53 6261671 : mpi_add (rem, rem, divisor);
54 :
55 32855222 : if( temp_divisor )
56 4386 : mpi_free(temp_divisor);
57 32855222 : }
58 :
59 :
60 :
61 : /****************
62 : * Division rounding the quotient towards -infinity.
63 : * The remainder gets the same sign as the denominator.
64 : * rem is optional
65 : */
66 :
67 : ulong
68 235136 : _gcry_mpi_fdiv_r_ui( gcry_mpi_t rem, gcry_mpi_t dividend, ulong divisor )
69 : {
70 : mpi_limb_t rlimb;
71 :
72 235136 : rlimb = _gcry_mpih_mod_1( dividend->d, dividend->nlimbs, divisor );
73 235136 : if( rlimb && dividend->sign )
74 0 : rlimb = divisor - rlimb;
75 :
76 235136 : if( rem ) {
77 0 : rem->d[0] = rlimb;
78 0 : rem->nlimbs = rlimb? 1:0;
79 : }
80 235136 : return rlimb;
81 : }
82 :
83 :
84 : void
85 165 : _gcry_mpi_fdiv_q( gcry_mpi_t quot, gcry_mpi_t dividend, gcry_mpi_t divisor )
86 : {
87 165 : gcry_mpi_t tmp = mpi_alloc( mpi_get_nlimbs(quot) );
88 165 : _gcry_mpi_fdiv_qr( quot, tmp, dividend, divisor);
89 165 : mpi_free(tmp);
90 165 : }
91 :
92 : void
93 165 : _gcry_mpi_fdiv_qr( gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor )
94 : {
95 165 : int divisor_sign = divisor->sign;
96 165 : gcry_mpi_t temp_divisor = NULL;
97 :
98 165 : if( quot == divisor || rem == divisor ) {
99 0 : temp_divisor = mpi_copy( divisor );
100 0 : divisor = temp_divisor;
101 : }
102 :
103 165 : _gcry_mpi_tdiv_qr( quot, rem, dividend, divisor );
104 :
105 165 : if( (divisor_sign ^ dividend->sign) && rem->nlimbs ) {
106 0 : mpi_sub_ui( quot, quot, 1 );
107 0 : mpi_add( rem, rem, divisor);
108 : }
109 :
110 165 : if( temp_divisor )
111 0 : mpi_free(temp_divisor);
112 165 : }
113 :
114 :
115 : /* If den == quot, den needs temporary storage.
116 : * If den == rem, den needs temporary storage.
117 : * If num == quot, num needs temporary storage.
118 : * If den has temporary storage, it can be normalized while being copied,
119 : * i.e no extra storage should be allocated.
120 : */
121 :
122 : void
123 32930198 : _gcry_mpi_tdiv_r( gcry_mpi_t rem, gcry_mpi_t num, gcry_mpi_t den)
124 : {
125 32930198 : _gcry_mpi_tdiv_qr(NULL, rem, num, den );
126 32930198 : }
127 :
128 : void
129 32930363 : _gcry_mpi_tdiv_qr( gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t num, gcry_mpi_t den)
130 : {
131 : mpi_ptr_t np, dp;
132 : mpi_ptr_t qp, rp;
133 32930363 : mpi_size_t nsize = num->nlimbs;
134 32930363 : mpi_size_t dsize = den->nlimbs;
135 : mpi_size_t qsize, rsize;
136 32930363 : mpi_size_t sign_remainder = num->sign;
137 32930363 : mpi_size_t sign_quotient = num->sign ^ den->sign;
138 : unsigned normalization_steps;
139 : mpi_limb_t q_limb;
140 : mpi_ptr_t marker[5];
141 : unsigned int marker_nlimbs[5];
142 32930363 : int markidx=0;
143 :
144 : /* Ensure space is enough for quotient and remainder.
145 : * We need space for an extra limb in the remainder, because it's
146 : * up-shifted (normalized) below. */
147 32930363 : rsize = nsize + 1;
148 32930363 : mpi_resize( rem, rsize);
149 :
150 32930363 : qsize = rsize - dsize; /* qsize cannot be bigger than this. */
151 32930363 : if( qsize <= 0 ) {
152 85502 : if( num != rem ) {
153 9599 : rem->nlimbs = num->nlimbs;
154 9599 : rem->sign = num->sign;
155 9599 : MPN_COPY(rem->d, num->d, nsize);
156 : }
157 85502 : if( quot ) {
158 : /* This needs to follow the assignment to rem, in case the
159 : * numerator and quotient are the same. */
160 0 : quot->nlimbs = 0;
161 0 : quot->sign = 0;
162 : }
163 210158 : return;
164 : }
165 :
166 32844861 : if( quot )
167 165 : mpi_resize( quot, qsize);
168 :
169 : /* Read pointers here, when reallocation is finished. */
170 32844861 : np = num->d;
171 32844861 : dp = den->d;
172 32844861 : rp = rem->d;
173 :
174 : /* Optimize division by a single-limb divisor. */
175 32844861 : if( dsize == 1 ) {
176 : mpi_limb_t rlimb;
177 39154 : if( quot ) {
178 53 : qp = quot->d;
179 53 : rlimb = _gcry_mpih_divmod_1( qp, np, nsize, dp[0] );
180 53 : qsize -= qp[qsize - 1] == 0;
181 53 : quot->nlimbs = qsize;
182 53 : quot->sign = sign_quotient;
183 : }
184 : else
185 39101 : rlimb = _gcry_mpih_mod_1( np, nsize, dp[0] );
186 39154 : rp[0] = rlimb;
187 39154 : rsize = rlimb != 0?1:0;
188 39154 : rem->nlimbs = rsize;
189 39154 : rem->sign = sign_remainder;
190 39154 : return;
191 : }
192 :
193 :
194 32805707 : if( quot ) {
195 112 : qp = quot->d;
196 : /* Make sure QP and NP point to different objects. Otherwise the
197 : * numerator would be gradually overwritten by the quotient limbs. */
198 112 : if(qp == np) { /* Copy NP object to temporary space. */
199 24 : marker_nlimbs[markidx] = nsize;
200 24 : np = marker[markidx++] = mpi_alloc_limb_space(nsize,
201 : mpi_is_secure(quot));
202 24 : MPN_COPY(np, qp, nsize);
203 : }
204 : }
205 : else /* Put quotient at top of remainder. */
206 32805595 : qp = rp + dsize;
207 :
208 32805707 : count_leading_zeros( normalization_steps, dp[dsize - 1] );
209 :
210 : /* Normalize the denominator, i.e. make its most significant bit set by
211 : * shifting it NORMALIZATION_STEPS bits to the left. Also shift the
212 : * numerator the same number of steps (to keep the quotient the same!).
213 : */
214 32805707 : if( normalization_steps ) {
215 : mpi_ptr_t tp;
216 : mpi_limb_t nlimb;
217 :
218 : /* Shift up the denominator setting the most significant bit of
219 : * the most significant word. Use temporary storage not to clobber
220 : * the original contents of the denominator. */
221 31116033 : marker_nlimbs[markidx] = dsize;
222 31116033 : tp = marker[markidx++] = mpi_alloc_limb_space(dsize,mpi_is_secure(den));
223 31116033 : _gcry_mpih_lshift( tp, dp, dsize, normalization_steps );
224 31116033 : dp = tp;
225 :
226 : /* Shift up the numerator, possibly introducing a new most
227 : * significant word. Move the shifted numerator in the remainder
228 : * meanwhile. */
229 31116033 : nlimb = _gcry_mpih_lshift(rp, np, nsize, normalization_steps);
230 31116033 : if( nlimb ) {
231 4109729 : rp[nsize] = nlimb;
232 4109729 : rsize = nsize + 1;
233 : }
234 : else
235 27006304 : rsize = nsize;
236 : }
237 : else {
238 : /* The denominator is already normalized, as required. Copy it to
239 : * temporary space if it overlaps with the quotient or remainder. */
240 1689674 : if( dp == rp || (quot && (dp == qp))) {
241 : mpi_ptr_t tp;
242 :
243 0 : marker_nlimbs[markidx] = dsize;
244 0 : tp = marker[markidx++] = mpi_alloc_limb_space(dsize,
245 : mpi_is_secure(den));
246 0 : MPN_COPY( tp, dp, dsize );
247 0 : dp = tp;
248 : }
249 :
250 : /* Move the numerator to the remainder. */
251 1689674 : if( rp != np )
252 1178 : MPN_COPY(rp, np, nsize);
253 :
254 1689674 : rsize = nsize;
255 : }
256 :
257 32805707 : q_limb = _gcry_mpih_divrem( qp, 0, rp, rsize, dp, dsize );
258 :
259 32805707 : if( quot ) {
260 112 : qsize = rsize - dsize;
261 112 : if(q_limb) {
262 0 : qp[qsize] = q_limb;
263 0 : qsize += 1;
264 : }
265 :
266 112 : quot->nlimbs = qsize;
267 112 : quot->sign = sign_quotient;
268 : }
269 :
270 32805707 : rsize = dsize;
271 32805707 : MPN_NORMALIZE (rp, rsize);
272 :
273 32805707 : if( normalization_steps && rsize ) {
274 31115921 : _gcry_mpih_rshift(rp, rp, rsize, normalization_steps);
275 31115921 : rsize -= rp[rsize - 1] == 0?1:0;
276 : }
277 :
278 32805707 : rem->nlimbs = rsize;
279 32805707 : rem->sign = sign_remainder;
280 96727471 : while( markidx )
281 : {
282 31116057 : markidx--;
283 31116057 : _gcry_mpi_free_limb_space (marker[markidx], marker_nlimbs[markidx]);
284 : }
285 : }
286 :
287 : void
288 435 : _gcry_mpi_tdiv_q_2exp( gcry_mpi_t w, gcry_mpi_t u, unsigned int count )
289 : {
290 : mpi_size_t usize, wsize;
291 : mpi_size_t limb_cnt;
292 :
293 435 : usize = u->nlimbs;
294 435 : limb_cnt = count / BITS_PER_MPI_LIMB;
295 435 : wsize = usize - limb_cnt;
296 435 : if( limb_cnt >= usize )
297 0 : w->nlimbs = 0;
298 : else {
299 : mpi_ptr_t wp;
300 : mpi_ptr_t up;
301 :
302 435 : RESIZE_IF_NEEDED( w, wsize );
303 435 : wp = w->d;
304 435 : up = u->d;
305 :
306 435 : count %= BITS_PER_MPI_LIMB;
307 435 : if( count ) {
308 435 : _gcry_mpih_rshift( wp, up + limb_cnt, wsize, count );
309 435 : wsize -= !wp[wsize - 1];
310 : }
311 : else {
312 0 : MPN_COPY_INCR( wp, up + limb_cnt, wsize);
313 : }
314 :
315 435 : w->nlimbs = wsize;
316 : }
317 435 : }
318 :
319 : /****************
320 : * Check whether dividend is divisible by divisor
321 : * (note: divisor must fit into a limb)
322 : */
323 : int
324 1778676 : _gcry_mpi_divisible_ui(gcry_mpi_t dividend, ulong divisor )
325 : {
326 1778676 : return !_gcry_mpih_mod_1( dividend->d, dividend->nlimbs, divisor );
327 : }
328 :
329 :
330 : void
331 2 : _gcry_mpi_div (gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t dividend,
332 : gcry_mpi_t divisor, int round)
333 : {
334 2 : if (!round)
335 : {
336 0 : if (!rem)
337 : {
338 0 : gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs(quot));
339 0 : _gcry_mpi_tdiv_qr (quot, tmp, dividend, divisor);
340 0 : mpi_free (tmp);
341 : }
342 : else
343 0 : _gcry_mpi_tdiv_qr (quot, rem, dividend, divisor);
344 : }
345 2 : else if (round < 0)
346 : {
347 2 : if (!rem)
348 2 : _gcry_mpi_fdiv_q (quot, dividend, divisor);
349 0 : else if (!quot)
350 0 : _gcry_mpi_fdiv_r (rem, dividend, divisor);
351 : else
352 0 : _gcry_mpi_fdiv_qr (quot, rem, dividend, divisor);
353 : }
354 : else
355 0 : log_bug ("mpi rounding to ceiling not yet implemented\n");
356 2 : }
|
