source: grub-pc/trunk/fuentes/grub-core/lib/libgcrypt/mpi/mpi-div.c @ 22

Last change on this file since 22 was 22, checked in by mabarracus, 4 years ago

updated version and apply net.ifnames=0 into debian/rules

File size: 9.3 KB
Line 
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
36void
37_gcry_mpi_fdiv_r( gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor )
38{
39    int divisor_sign = divisor->sign;
40    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    if( rem == divisor ) {
46        temp_divisor = mpi_copy( divisor );
47        divisor = temp_divisor;
48    }
49
50    _gcry_mpi_tdiv_r( rem, dividend, divisor );
51
52    if( ((divisor_sign?1:0) ^ (dividend->sign?1:0)) && rem->nlimbs )
53        gcry_mpi_add( rem, rem, divisor);
54
55    if( temp_divisor )
56        mpi_free(temp_divisor);
57}
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
67ulong
68_gcry_mpi_fdiv_r_ui( gcry_mpi_t rem, gcry_mpi_t dividend, ulong divisor )
69{
70    mpi_limb_t rlimb;
71
72    rlimb = _gcry_mpih_mod_1( dividend->d, dividend->nlimbs, divisor );
73    if( rlimb && dividend->sign )
74        rlimb = divisor - rlimb;
75
76    if( rem ) {
77        rem->d[0] = rlimb;
78        rem->nlimbs = rlimb? 1:0;
79    }
80    return rlimb;
81}
82
83
84void
85_gcry_mpi_fdiv_q( gcry_mpi_t quot, gcry_mpi_t dividend, gcry_mpi_t divisor )
86{
87    gcry_mpi_t tmp = mpi_alloc( mpi_get_nlimbs(quot) );
88    _gcry_mpi_fdiv_qr( quot, tmp, dividend, divisor);
89    mpi_free(tmp);
90}
91
92void
93_gcry_mpi_fdiv_qr( gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor )
94{
95    int divisor_sign = divisor->sign;
96    gcry_mpi_t temp_divisor = NULL;
97
98    if( quot == divisor || rem == divisor ) {
99        temp_divisor = mpi_copy( divisor );
100        divisor = temp_divisor;
101    }
102
103    _gcry_mpi_tdiv_qr( quot, rem, dividend, divisor );
104
105    if( (divisor_sign ^ dividend->sign) && rem->nlimbs ) {
106        gcry_mpi_sub_ui( quot, quot, 1 );
107        gcry_mpi_add( rem, rem, divisor);
108    }
109
110    if( temp_divisor )
111        mpi_free(temp_divisor);
112}
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
122void
123_gcry_mpi_tdiv_r( gcry_mpi_t rem, gcry_mpi_t num, gcry_mpi_t den)
124{
125    _gcry_mpi_tdiv_qr(NULL, rem, num, den );
126}
127
128void
129_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    mpi_size_t nsize = num->nlimbs;
134    mpi_size_t dsize = den->nlimbs;
135    mpi_size_t qsize, rsize;
136    mpi_size_t sign_remainder = num->sign;
137    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    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    rsize = nsize + 1;
148    mpi_resize( rem, rsize);
149
150    qsize = rsize - dsize;        /* qsize cannot be bigger than this.  */
151    if( qsize <= 0 ) {
152        if( num != rem ) {
153            rem->nlimbs = num->nlimbs;
154            rem->sign = num->sign;
155            MPN_COPY(rem->d, num->d, nsize);
156        }
157        if( quot ) {
158            /* This needs to follow the assignment to rem, in case the
159             * numerator and quotient are the same.  */
160            quot->nlimbs = 0;
161            quot->sign = 0;
162        }
163        return;
164    }
165
166    if( quot )
167        mpi_resize( quot, qsize);
168
169    /* Read pointers here, when reallocation is finished.  */
170    np = num->d;
171    dp = den->d;
172    rp = rem->d;
173
174    /* Optimize division by a single-limb divisor.  */
175    if( dsize == 1 ) {
176        mpi_limb_t rlimb;
177        if( quot ) {
178            qp = quot->d;
179            rlimb = _gcry_mpih_divmod_1( qp, np, nsize, dp[0] );
180            qsize -= qp[qsize - 1] == 0;
181            quot->nlimbs = qsize;
182            quot->sign = sign_quotient;
183        }
184        else
185            rlimb = _gcry_mpih_mod_1( np, nsize, dp[0] );
186        rp[0] = rlimb;
187        rsize = rlimb != 0?1:0;
188        rem->nlimbs = rsize;
189        rem->sign = sign_remainder;
190        return;
191    }
192
193
194    if( quot ) {
195        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        if(qp == np) { /* Copy NP object to temporary space.  */
199            marker_nlimbs[markidx] = nsize;
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        marker_nlimbs[markidx] = dsize;
222        tp = marker[markidx++] = mpi_alloc_limb_space(dsize,mpi_is_secure(den));
223        _gcry_mpih_lshift( tp, dp, dsize, normalization_steps );
224        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        nlimb = _gcry_mpih_lshift(rp, np, nsize, normalization_steps);
230        if( nlimb ) {
231            rp[nsize] = nlimb;
232            rsize = nsize + 1;
233        }
234        else
235            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        if( dp == rp || (quot && (dp == qp))) {
241            mpi_ptr_t tp;
242
243            marker_nlimbs[markidx] = dsize;
244            tp = marker[markidx++] = mpi_alloc_limb_space(dsize,
245                                                          mpi_is_secure(den));
246            MPN_COPY( tp, dp, dsize );
247            dp = tp;
248        }
249
250        /* Move the numerator to the remainder.  */
251        if( rp != np )
252            MPN_COPY(rp, np, nsize);
253
254        rsize = nsize;
255    }
256
257    q_limb = _gcry_mpih_divrem( qp, 0, rp, rsize, dp, dsize );
258
259    if( quot ) {
260        qsize = rsize - dsize;
261        if(q_limb) {
262            qp[qsize] = q_limb;
263            qsize += 1;
264        }
265
266        quot->nlimbs = qsize;
267        quot->sign = sign_quotient;
268    }
269
270    rsize = dsize;
271    MPN_NORMALIZE (rp, rsize);
272
273    if( normalization_steps && rsize ) {
274        _gcry_mpih_rshift(rp, rp, rsize, normalization_steps);
275        rsize -= rp[rsize - 1] == 0?1:0;
276    }
277
278    rem->nlimbs = rsize;
279    rem->sign   = sign_remainder;
280    while( markidx )
281      {
282        markidx--;
283        _gcry_mpi_free_limb_space (marker[markidx], marker_nlimbs[markidx]);
284      }
285}
286
287void
288_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    usize = u->nlimbs;
294    limb_cnt = count / BITS_PER_MPI_LIMB;
295    wsize = usize - limb_cnt;
296    if( limb_cnt >= usize )
297        w->nlimbs = 0;
298    else {
299        mpi_ptr_t wp;
300        mpi_ptr_t up;
301
302        RESIZE_IF_NEEDED( w, wsize );
303        wp = w->d;
304        up = u->d;
305
306        count %= BITS_PER_MPI_LIMB;
307        if( count ) {
308            _gcry_mpih_rshift( wp, up + limb_cnt, wsize, count );
309            wsize -= !wp[wsize - 1];
310        }
311        else {
312            MPN_COPY_INCR( wp, up + limb_cnt, wsize);
313        }
314
315        w->nlimbs = wsize;
316    }
317}
318
319/****************
320 * Check whether dividend is divisible by divisor
321 * (note: divisor must fit into a limb)
322 */
323int
324_gcry_mpi_divisible_ui(gcry_mpi_t dividend, ulong divisor )
325{
326    return !_gcry_mpih_mod_1( dividend->d, dividend->nlimbs, divisor );
327}
328
329
330void
331gcry_mpi_div (gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor, int round)
332{
333  if (!round)
334    {
335      if (!rem)
336        {
337          gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs(quot));
338          _gcry_mpi_tdiv_qr (quot, tmp, dividend, divisor);
339          mpi_free (tmp);
340        }
341      else
342        _gcry_mpi_tdiv_qr (quot, rem, dividend, divisor);
343    }
344  else if (round < 0)
345    {
346      if (!rem)
347        _gcry_mpi_fdiv_q (quot, dividend, divisor);
348      else if (!quot)
349        _gcry_mpi_fdiv_r (rem, dividend, divisor);
350      else
351        _gcry_mpi_fdiv_qr (quot, rem, dividend, divisor);
352    }
353  else
354    log_bug ("mpi rounding to ceiling not yet implemented\n");
355}
Note: See TracBrowser for help on using the repository browser.