diff options
Diffstat (limited to 'mpi/generic')
| -rw-r--r-- | mpi/generic/distfiles | 1 | ||||
| -rw-r--r-- | mpi/generic/mpih-lshift.c (renamed from mpi/generic/mpih-shift.c) | 38 | ||||
| -rw-r--r-- | mpi/generic/mpih-rshift.c | 67 | ||||
| -rw-r--r-- | mpi/generic/udiv-w-sdiv.c | 135 |
4 files changed, 205 insertions, 36 deletions
diff --git a/mpi/generic/distfiles b/mpi/generic/distfiles index 02a1ca4c..0bf4600f 100644 --- a/mpi/generic/distfiles +++ b/mpi/generic/distfiles @@ -5,4 +5,5 @@ mpih-mul3.c mpih-lshift.c mpih-rshift.c mpih-sub1.c +udiv-w-sdiv.c diff --git a/mpi/generic/mpih-shift.c b/mpi/generic/mpih-lshift.c index 2da2edd7..698cd38d 100644 --- a/mpi/generic/mpih-shift.c +++ b/mpi/generic/mpih-lshift.c @@ -1,6 +1,5 @@ -/* mpihelp-shift.c - MPI helper functions - * Copyright (c) 1997 by Werner Koch (dd9jn) - * Copyright (C) 1994, 1996 Free Software Foundation, Inc. +/* mpihelp-lshift.c - MPI helper functions + * Copyright (C) 1994, 1996, 1998 Free Software Foundation, Inc. * * This file is part of G10. * @@ -68,36 +67,3 @@ mpihelp_lshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, } -/* Shift U (pointed to by UP and USIZE limbs long) CNT bits to the right - * and store the USIZE least significant limbs of the result at WP. - * The bits shifted out to the right are returned. - * - * Argument constraints: - * 1. 0 < CNT < BITS_PER_MP_LIMB - * 2. If the result is to be written over the input, WP must be <= UP. - */ - -mpi_limb_t -mpihelp_rshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned cnt) -{ - mpi_limb_t high_limb, low_limb; - unsigned sh_1, sh_2; - mpi_size_t i; - mpi_limb_t retval; - - sh_1 = cnt; - wp -= 1; - sh_2 = BITS_PER_MPI_LIMB - sh_1; - high_limb = up[0]; - retval = high_limb << sh_2; - low_limb = high_limb; - for( i=1; i < usize; i++) { - high_limb = up[i]; - wp[i] = (low_limb >> sh_1) | (high_limb << sh_2); - low_limb = high_limb; - } - wp[i] = low_limb >> sh_1; - - return retval; -} - diff --git a/mpi/generic/mpih-rshift.c b/mpi/generic/mpih-rshift.c new file mode 100644 index 00000000..d8ca35f1 --- /dev/null +++ b/mpi/generic/mpih-rshift.c @@ -0,0 +1,67 @@ +/* mpih-rshift.c - MPI helper functions + * Copyright (C) 1994, 1996, 1998 Free Software Foundation, Inc. + * + * This file is part of GNUPG + * + * GNUPG is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * GNUPG is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA + * + * Note: This code is heavily based on the GNU MP Library. + * Actually it's the same code with only minor changes in the + * way the data is stored; this is to support the abstraction + * of an optional secure memory allocation which may be used + * to avoid revealing of sensitive data due to paging etc. + * The GNU MP Library itself is published under the LGPL; + * however I decided to publish this code under the plain GPL. + */ + +#include <config.h> +#include <stdio.h> +#include <stdlib.h> +#include "mpi-internal.h" + + +/* Shift U (pointed to by UP and USIZE limbs long) CNT bits to the right + * and store the USIZE least significant limbs of the result at WP. + * The bits shifted out to the right are returned. + * + * Argument constraints: + * 1. 0 < CNT < BITS_PER_MP_LIMB + * 2. If the result is to be written over the input, WP must be <= UP. + */ + +mpi_limb_t +mpihelp_rshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned cnt) +{ + mpi_limb_t high_limb, low_limb; + unsigned sh_1, sh_2; + mpi_size_t i; + mpi_limb_t retval; + + sh_1 = cnt; + wp -= 1; + sh_2 = BITS_PER_MPI_LIMB - sh_1; + high_limb = up[0]; + retval = high_limb << sh_2; + low_limb = high_limb; + for( i=1; i < usize; i++) { + high_limb = up[i]; + wp[i] = (low_limb >> sh_1) | (high_limb << sh_2); + low_limb = high_limb; + } + wp[i] = low_limb >> sh_1; + + return retval; +} + diff --git a/mpi/generic/udiv-w-sdiv.c b/mpi/generic/udiv-w-sdiv.c new file mode 100644 index 00000000..7ffec099 --- /dev/null +++ b/mpi/generic/udiv-w-sdiv.c @@ -0,0 +1,135 @@ +/* mpihelp_udiv_w_sdiv -- implement udiv_qrnnd on machines with only signed + * division. + * + * Contributed by Peter L. Montgomery. + * + * Copyright (C) 1992, 1994, 1996, 1998 Free Software Foundation, Inc. + * + * This file is part of GnuPG. + * + * GnuPG is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * GnuPG is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA + */ + +#include <config.h> +#include <stdio.h> +#include <stdlib.h> +#include "mpi-internal.h" +#include "longlong.h" + + +#if 0 /* not yet ported to MPI */ + +mpi_limb_t +mpihelp_udiv_w_sdiv( mpi_limp_t *rp, + mpi_limp_t *a1, + mpi_limp_t *a0, + mpi_limp_t *d ) +{ + mp_limb_t q, r; + mp_limb_t c0, c1, b1; + + if ((mpi_limb_signed_t) d >= 0) + { + if (a1 < d - a1 - (a0 >> (BITS_PER_MP_LIMB - 1))) + { + /* dividend, divisor, and quotient are nonnegative */ + sdiv_qrnnd (q, r, a1, a0, d); + } + else + { + /* Compute c1*2^32 + c0 = a1*2^32 + a0 - 2^31*d */ + sub_ddmmss (c1, c0, a1, a0, d >> 1, d << (BITS_PER_MP_LIMB - 1)); + /* Divide (c1*2^32 + c0) by d */ + sdiv_qrnnd (q, r, c1, c0, d); + /* Add 2^31 to quotient */ + q += (mp_limb_t) 1 << (BITS_PER_MP_LIMB - 1); + } + } + else + { + b1 = d >> 1; /* d/2, between 2^30 and 2^31 - 1 */ + c1 = a1 >> 1; /* A/2 */ + c0 = (a1 << (BITS_PER_MP_LIMB - 1)) + (a0 >> 1); + + if (a1 < b1) /* A < 2^32*b1, so A/2 < 2^31*b1 */ + { + sdiv_qrnnd (q, r, c1, c0, b1); /* (A/2) / (d/2) */ + + r = 2*r + (a0 & 1); /* Remainder from A/(2*b1) */ + if ((d & 1) != 0) + { + if (r >= q) + r = r - q; + else if (q - r <= d) + { + r = r - q + d; + q--; + } + else + { + r = r - q + 2*d; + q -= 2; + } + } + } + else if (c1 < b1) /* So 2^31 <= (A/2)/b1 < 2^32 */ + { + c1 = (b1 - 1) - c1; + c0 = ~c0; /* logical NOT */ + + sdiv_qrnnd (q, r, c1, c0, b1); /* (A/2) / (d/2) */ + + q = ~q; /* (A/2)/b1 */ + r = (b1 - 1) - r; + + r = 2*r + (a0 & 1); /* A/(2*b1) */ + + if ((d & 1) != 0) + { + if (r >= q) + r = r - q; + else if (q - r <= d) + { + r = r - q + d; + q--; + } + else + { + r = r - q + 2*d; + q -= 2; + } + } + } + else /* Implies c1 = b1 */ + { /* Hence a1 = d - 1 = 2*b1 - 1 */ + if (a0 >= -d) + { + q = -1; + r = a0 + d; + } + else + { + q = -2; + r = a0 + 2*d; + } + } + } + + *rp = r; + return q; +} + +#endif + |