* DETAILS: Details for --list-config.
[gnupg.git] / mpi / mpi-div.c
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 <config.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include "mpi-internal.h"
34 #include "longlong.h"
35
36
37
38 void
39 mpi_fdiv_r( MPI rem, MPI dividend, MPI divisor )
40 {
41     int divisor_sign = divisor->sign;
42     MPI temp_divisor = NULL;
43
44     /* We need the original value of the divisor after the remainder has been
45      * preliminary calculated.  We have to copy it to temporary space if it's
46      * the same variable as REM.  */
47     if( rem == divisor ) {
48         temp_divisor = mpi_copy( divisor );
49         divisor = temp_divisor;
50     }
51
52     mpi_tdiv_r( rem, dividend, divisor );
53
54     if( ((divisor_sign?1:0) ^ (dividend->sign?1:0)) && rem->nlimbs )
55         mpi_add( rem, rem, divisor);
56
57     if( temp_divisor )
58         mpi_free(temp_divisor);
59 }
60
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
70 mpi_fdiv_r_ui( MPI rem, MPI dividend, ulong divisor )
71 {
72     mpi_limb_t rlimb;
73
74     rlimb = mpihelp_mod_1( dividend->d, dividend->nlimbs, divisor );
75     if( rlimb && dividend->sign )
76         rlimb = divisor - rlimb;
77
78     if( rem ) {
79         rem->d[0] = rlimb;
80         rem->nlimbs = rlimb? 1:0;
81     }
82     return rlimb;
83 }
84
85
86 void
87 mpi_fdiv_q( MPI quot, MPI dividend, MPI divisor )
88 {
89     MPI tmp = mpi_alloc( mpi_get_nlimbs(quot) );
90     mpi_fdiv_qr( quot, tmp, dividend, divisor);
91     mpi_free(tmp);
92 }
93
94 void
95 mpi_fdiv_qr( MPI quot, MPI rem, MPI dividend, MPI divisor )
96 {
97     int divisor_sign = divisor->sign;
98     MPI temp_divisor = NULL;
99
100     if( quot == divisor || rem == divisor ) {
101         temp_divisor = mpi_copy( divisor );
102         divisor = temp_divisor;
103     }
104
105     mpi_tdiv_qr( quot, rem, dividend, divisor );
106
107     if( (divisor_sign ^ dividend->sign) && rem->nlimbs ) {
108         mpi_sub_ui( quot, quot, 1 );
109         mpi_add( rem, rem, divisor);
110     }
111
112     if( temp_divisor )
113         mpi_free(temp_divisor);
114 }
115
116
117 /* If den == quot, den needs temporary storage.
118  * If den == rem, den needs temporary storage.
119  * If num == quot, num needs temporary storage.
120  * If den has temporary storage, it can be normalized while being copied,
121  *   i.e no extra storage should be allocated.
122  */
123
124 void
125 mpi_tdiv_r( MPI rem, MPI num, MPI den)
126 {
127     mpi_tdiv_qr(NULL, rem, num, den );
128 }
129
130 void
131 mpi_tdiv_qr( MPI quot, MPI rem, MPI num, MPI den)
132 {
133     mpi_ptr_t np, dp;
134     mpi_ptr_t qp, rp;
135     mpi_size_t nsize = num->nlimbs;
136     mpi_size_t dsize = den->nlimbs;
137     mpi_size_t qsize, rsize;
138     mpi_size_t sign_remainder = num->sign;
139     mpi_size_t sign_quotient = num->sign ^ den->sign;
140     unsigned normalization_steps;
141     mpi_limb_t q_limb;
142     mpi_ptr_t marker[5];
143     int markidx=0;
144
145     /* Ensure space is enough for quotient and remainder.
146      * We need space for an extra limb in the remainder, because it's
147      * up-shifted (normalized) below.  */
148     rsize = nsize + 1;
149     mpi_resize( rem, rsize);
150
151     qsize = rsize - dsize;        /* qsize cannot be bigger than this.  */
152     if( qsize <= 0 ) {
153         if( num != rem ) {
154             rem->nlimbs = num->nlimbs;
155             rem->sign = num->sign;
156             MPN_COPY(rem->d, num->d, nsize);
157         }
158         if( quot ) {
159             /* This needs to follow the assignment to rem, in case the
160              * numerator and quotient are the same.  */
161             quot->nlimbs = 0;
162             quot->sign = 0;
163         }
164         return;
165     }
166
167     if( quot )
168         mpi_resize( quot, qsize);
169
170     /* Read pointers here, when reallocation is finished.  */
171     np = num->d;
172     dp = den->d;
173     rp = rem->d;
174
175     /* Optimize division by a single-limb divisor.  */
176     if( dsize == 1 ) {
177         mpi_limb_t rlimb;
178         if( quot ) {
179             qp = quot->d;
180             rlimb = mpihelp_divmod_1( qp, np, nsize, dp[0] );
181             qsize -= qp[qsize - 1] == 0;
182             quot->nlimbs = qsize;
183             quot->sign = sign_quotient;
184         }
185         else
186             rlimb = mpihelp_mod_1( np, nsize, dp[0] );
187         rp[0] = rlimb;
188         rsize = rlimb != 0?1:0;
189         rem->nlimbs = rsize;
190         rem->sign = sign_remainder;
191         return;
192     }
193
194
195     if( quot ) {
196         qp = quot->d;
197         /* Make sure QP and NP point to different objects.  Otherwise the
198          * numerator would be gradually overwritten by the quotient limbs.  */
199         if(qp == np) { /* Copy NP object to temporary space.  */
200             np = marker[markidx++] = mpi_alloc_limb_space(nsize,
201                                                           mpi_is_secure(quot));
202             MPN_COPY(np, qp, nsize);
203         }
204     }
205     else /* Put quotient at top of remainder. */
206         qp = rp + dsize;
207
208     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     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         tp = marker[markidx++] = mpi_alloc_limb_space(dsize,mpi_is_secure(den));
222         mpihelp_lshift( tp, dp, dsize, normalization_steps );
223         dp = tp;
224
225         /* Shift up the numerator, possibly introducing a new most
226          * significant word.  Move the shifted numerator in the remainder
227          * meanwhile.  */
228         nlimb = mpihelp_lshift(rp, np, nsize, normalization_steps);
229         if( nlimb ) {
230             rp[nsize] = nlimb;
231             rsize = nsize + 1;
232         }
233         else
234             rsize = nsize;
235     }
236     else {
237         /* The denominator is already normalized, as required.  Copy it to
238          * temporary space if it overlaps with the quotient or remainder.  */
239         if( dp == rp || (quot && (dp == qp))) {
240             mpi_ptr_t tp;
241
242             tp = marker[markidx++] = mpi_alloc_limb_space(dsize, mpi_is_secure(den));
243             MPN_COPY( tp, dp, dsize );
244             dp = tp;
245         }
246
247         /* Move the numerator to the remainder.  */
248         if( rp != np )
249             MPN_COPY(rp, np, nsize);
250
251         rsize = nsize;
252     }
253
254     q_limb = mpihelp_divrem( qp, 0, rp, rsize, dp, dsize );
255
256     if( quot ) {
257         qsize = rsize - dsize;
258         if(q_limb) {
259             qp[qsize] = q_limb;
260             qsize += 1;
261         }
262
263         quot->nlimbs = qsize;
264         quot->sign = sign_quotient;
265     }
266
267     rsize = dsize;
268     MPN_NORMALIZE (rp, rsize);
269
270     if( normalization_steps && rsize ) {
271         mpihelp_rshift(rp, rp, rsize, normalization_steps);
272         rsize -= rp[rsize - 1] == 0?1:0;
273     }
274
275     rem->nlimbs = rsize;
276     rem->sign   = sign_remainder;
277     while( markidx )
278         mpi_free_limb_space(marker[--markidx]);
279 }
280
281 void
282 mpi_tdiv_q_2exp( MPI w, MPI u, unsigned count )
283 {
284     mpi_size_t usize, wsize;
285     mpi_size_t limb_cnt;
286
287     usize = u->nlimbs;
288     limb_cnt = count / BITS_PER_MPI_LIMB;
289     wsize = usize - limb_cnt;
290     if( limb_cnt >= usize )
291         w->nlimbs = 0;
292     else {
293         mpi_ptr_t wp;
294         mpi_ptr_t up;
295
296         RESIZE_IF_NEEDED( w, wsize );
297         wp = w->d;
298         up = u->d;
299
300         count %= BITS_PER_MPI_LIMB;
301         if( count ) {
302             mpihelp_rshift( wp, up + limb_cnt, wsize, count );
303             wsize -= !wp[wsize - 1];
304         }
305         else {
306             MPN_COPY_INCR( wp, up + limb_cnt, wsize);
307         }
308
309         w->nlimbs = wsize;
310     }
311 }
312
313 /****************
314  * Check whether dividend is divisible by divisor
315  * (note: divisor must fit into a limb)
316  */
317 int
318 mpi_divisible_ui(MPI dividend, ulong divisor )
319 {
320     return !mpihelp_mod_1( dividend->d, dividend->nlimbs, divisor );
321 }
322