diff --git a/include/types.h b/include/types.h
index 6baccdbbb..3c5248502 100644
--- a/include/types.h
+++ b/include/types.h
@@ -1,146 +1,155 @@
/* types.h - some common typedefs
* Copyright (C) 1998, 1999, 2000, 2001 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 3 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, see .
*/
#ifndef G10_TYPES_H
#define G10_TYPES_H
#ifdef HAVE_INTTYPES_H
# include /* For uint64_t */
#endif
/* The AC_CHECK_SIZEOF() in configure fails for some machines.
* we provide some fallback values here */
#if !SIZEOF_UNSIGNED_SHORT
# undef SIZEOF_UNSIGNED_SHORT
# define SIZEOF_UNSIGNED_SHORT 2
#endif
#if !SIZEOF_UNSIGNED_INT
# undef SIZEOF_UNSIGNED_INT
# define SIZEOF_UNSIGNED_INT 4
#endif
#if !SIZEOF_UNSIGNED_LONG
# undef SIZEOF_UNSIGNED_LONG
# define SIZEOF_UNSIGNED_LONG 4
#endif
#include
#ifndef HAVE_BYTE_TYPEDEF
# undef byte /* maybe there is a macro with this name */
# ifndef __riscos__
typedef unsigned char byte;
# else
/* Norcroft treats char = unsigned char as legal assignment
but char* = unsigned char* as illegal assignment
and the same applies to the signed variants as well */
typedef char byte;
# endif
# define HAVE_BYTE_TYPEDEF
#endif
#ifndef HAVE_USHORT_TYPEDEF
# undef ushort /* maybe there is a macro with this name */
typedef unsigned short ushort;
# define HAVE_USHORT_TYPEDEF
#endif
#ifndef HAVE_ULONG_TYPEDEF
# undef ulong /* maybe there is a macro with this name */
typedef unsigned long ulong;
# define HAVE_ULONG_TYPEDEF
#endif
#ifndef HAVE_U16_TYPEDEF
# undef u16 /* maybe there is a macro with this name */
# if SIZEOF_UNSIGNED_INT == 2
typedef unsigned int u16;
# elif SIZEOF_UNSIGNED_SHORT == 2
typedef unsigned short u16;
# else
# error no typedef for u16
# endif
# define HAVE_U16_TYPEDEF
#endif
#ifndef HAVE_U32_TYPEDEF
# undef u32 /* maybe there is a macro with this name */
# if SIZEOF_UNSIGNED_INT == 4
typedef unsigned int u32;
# elif SIZEOF_UNSIGNED_LONG == 4
typedef unsigned long u32;
# else
# error no typedef for u32
# endif
# define HAVE_U32_TYPEDEF
#endif
/****************
* Warning: Some systems segfault when this u64 typedef and
* the dummy code in cipher/md.c is not available. Examples are
* Solaris and IRIX.
*/
#ifndef HAVE_U64_TYPEDEF
# undef u64 /* maybe there is a macro with this name */
# if SIZEOF_UINT64_T == 8
typedef uint64_t u64;
# ifdef UINT64_C
# define U64_C(c) (UINT64_C(c))
# else
/* make a best guess, could happen with UNIX98 */
# define U64_C(c) (c)
# endif
# define HAVE_U64_TYPEDEF
#elif SIZEOF_UNSIGNED_INT == 8
typedef unsigned int u64;
# define U64_C(c) (c ## U)
# define HAVE_U64_TYPEDEF
# elif SIZEOF_UNSIGNED_LONG == 8
typedef unsigned long u64;
# define U64_C(c) (c ## UL)
# define HAVE_U64_TYPEDEF
#elif SIZEOF_UNSIGNED_LONG_LONG == 8
typedef unsigned long long u64;
# define U64_C(c) (c ## ULL)
# define HAVE_U64_TYPEDEF
# endif
#endif
typedef union {
int a;
short b;
char c[1];
long d;
#ifdef HAVE_U64_TYPEDEF
u64 e;
#endif
float f;
double g;
} PROPERLY_ALIGNED_TYPE;
struct string_list {
struct string_list *next;
unsigned int flags;
char d[1];
};
typedef struct string_list *STRLIST;
typedef struct string_list *strlist_t;
+
+
+#if __GNUC__ > 2 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 5 )
+# define GNUPG_GCC_ATTR_UNUSED __attribute__ ((unused))
+#else
+# define GNUPG_GCC_ATTR_UNUSED
+#endif
+
+
#endif /*G10_TYPES_H*/
diff --git a/mpi/mpi-internal.h b/mpi/mpi-internal.h
index 46da08d0d..9f79781f4 100644
--- a/mpi/mpi-internal.h
+++ b/mpi/mpi-internal.h
@@ -1,290 +1,291 @@
/* mpi-internal.h - Internal to the Multi Precision Integers
* Copyright (C) 1994, 1996 Free Software Foundation, Inc.
* Copyright (C) 1998, 2000 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 3 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, see .
*
* 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.
*/
#ifndef G10_MPI_INTERNAL_H
#define G10_MPI_INTERNAL_H
#include "mpi.h"
#include "mpi-asm-defs.h"
#if BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_INT
typedef unsigned int mpi_limb_t;
typedef signed int mpi_limb_signed_t;
#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_LONG
typedef unsigned long int mpi_limb_t;
typedef signed long int mpi_limb_signed_t;
#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_LONG_LONG
typedef unsigned long long int mpi_limb_t;
typedef signed long long int mpi_limb_signed_t;
#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_SHORT
typedef unsigned short int mpi_limb_t;
typedef signed short int mpi_limb_signed_t;
#else
#error BYTES_PER_MPI_LIMB does not match any C type
#endif
#define BITS_PER_MPI_LIMB (8*BYTES_PER_MPI_LIMB)
struct gcry_mpi {
int alloced; /* array size (# of allocated limbs) */
int nlimbs; /* number of valid limbs */
unsigned int nbits; /* the real number of valid bits (info only) */
int sign; /* indicates a negative number */
unsigned flags; /* bit 0: array must be allocated in secure memory space */
/* bit 1: not used */
/* bit 2: the limb is a pointer to some xmalloced data */
mpi_limb_t *d; /* array with the limbs */
};
/* If KARATSUBA_THRESHOLD is not already defined, define it to a
* value which is good on most machines. */
/* tested 4, 16, 32 and 64, where 16 gave the best performance when
* checking a 768 and a 1024 bit ElGamal signature.
* (wk 22.12.97) */
#ifndef KARATSUBA_THRESHOLD
#define KARATSUBA_THRESHOLD 16
#endif
/* The code can't handle KARATSUBA_THRESHOLD smaller than 2. */
#if KARATSUBA_THRESHOLD < 2
#undef KARATSUBA_THRESHOLD
#define KARATSUBA_THRESHOLD 2
#endif
typedef mpi_limb_t *mpi_ptr_t; /* pointer to a limb */
typedef int mpi_size_t; /* (must be a signed type) */
#define ABS(x) (x >= 0 ? x : -x)
#define MIN(l,o) ((l) < (o) ? (l) : (o))
#define MAX(h,i) ((h) > (i) ? (h) : (i))
#define RESIZE_IF_NEEDED(a,b) \
do { \
if( (a)->alloced < (b) ) \
mpi_resize((a), (b)); \
} while(0)
/* Copy N limbs from S to D. */
#define MPN_COPY( d, s, n) \
do { \
mpi_size_t _i; \
for( _i = 0; _i < (n); _i++ ) \
(d)[_i] = (s)[_i]; \
} while(0)
#define MPN_COPY_INCR( d, s, n) \
do { \
mpi_size_t _i; \
for( _i = 0; _i < (n); _i++ ) \
(d)[_i] = (s)[_i]; \
} while (0)
#define MPN_COPY_DECR( d, s, n ) \
do { \
mpi_size_t _i; \
for( _i = (n)-1; _i >= 0; _i--) \
(d)[_i] = (s)[_i]; \
} while(0)
/* Zero N limbs at D */
#define MPN_ZERO(d, n) \
do { \
int _i; \
for( _i = 0; _i < (n); _i++ ) \
(d)[_i] = 0; \
} while (0)
#define MPN_NORMALIZE(d, n) \
do { \
while( (n) > 0 ) { \
if( (d)[(n)-1] ) \
break; \
(n)--; \
} \
} while(0)
#define MPN_NORMALIZE_NOT_ZERO(d, n) \
do { \
for(;;) { \
if( (d)[(n)-1] ) \
break; \
(n)--; \
} \
} while(0)
#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
do { \
if( (size) < KARATSUBA_THRESHOLD ) \
mul_n_basecase (prodp, up, vp, size); \
else \
mul_n (prodp, up, vp, size, tspace); \
} while (0);
/* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
* limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB).
* If this would yield overflow, DI should be the largest possible number
* (i.e., only ones). For correct operation, the most significant bit of D
* has to be set. Put the quotient in Q and the remainder in R.
*/
#define UDIV_QRNND_PREINV(q, r, nh, nl, d, di) \
do { \
- mpi_limb_t _q, _ql, _r; \
+ mpi_limb_t _ql GNUPG_GCC_ATTR_UNUSED; \
+ mpi_limb_t _q, _r; \
mpi_limb_t _xh, _xl; \
umul_ppmm (_q, _ql, (nh), (di)); \
_q += (nh); /* DI is 2**BITS_PER_MPI_LIMB too small */ \
umul_ppmm (_xh, _xl, _q, (d)); \
sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl); \
if( _xh ) { \
sub_ddmmss (_xh, _r, _xh, _r, 0, (d)); \
_q++; \
if( _xh) { \
sub_ddmmss (_xh, _r, _xh, _r, 0, (d)); \
_q++; \
} \
} \
if( _r >= (d) ) { \
_r -= (d); \
_q++; \
} \
(r) = _r; \
(q) = _q; \
} while (0)
/*-- mpiutil.c --*/
#ifdef M_DEBUG
#define mpi_alloc_limb_space(n,f) mpi_debug_alloc_limb_space((n),(f), M_DBGINFO( __LINE__ ) )
#define mpi_free_limb_space(n) mpi_debug_free_limb_space((n), M_DBGINFO( __LINE__ ) )
mpi_ptr_t mpi_debug_alloc_limb_space( unsigned nlimbs, int sec, const char *info );
void mpi_debug_free_limb_space( mpi_ptr_t a, const char *info );
#else
mpi_ptr_t mpi_alloc_limb_space( unsigned nlimbs, int sec );
void mpi_free_limb_space( mpi_ptr_t a );
#endif
void mpi_assign_limb_space( MPI a, mpi_ptr_t ap, unsigned nlimbs );
/*-- mpi-bit.c --*/
void mpi_rshift_limbs( MPI a, unsigned int count );
void mpi_lshift_limbs( MPI a, unsigned int count );
/*-- mpihelp-add.c --*/
mpi_limb_t mpihelp_add_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_size_t s1_size, mpi_limb_t s2_limb );
mpi_limb_t mpihelp_add_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_ptr_t s2_ptr, mpi_size_t size);
mpi_limb_t mpihelp_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
mpi_ptr_t s2_ptr, mpi_size_t s2_size);
/*-- mpihelp-sub.c --*/
mpi_limb_t mpihelp_sub_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_size_t s1_size, mpi_limb_t s2_limb );
mpi_limb_t mpihelp_sub_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_ptr_t s2_ptr, mpi_size_t size);
mpi_limb_t mpihelp_sub(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
mpi_ptr_t s2_ptr, mpi_size_t s2_size);
/*-- mpihelp-cmp.c --*/
int mpihelp_cmp( mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size );
/*-- mpihelp-mul.c --*/
struct karatsuba_ctx {
struct karatsuba_ctx *next;
mpi_ptr_t tspace;
mpi_size_t tspace_size;
mpi_ptr_t tp;
mpi_size_t tp_size;
};
void mpihelp_release_karatsuba_ctx( struct karatsuba_ctx *ctx );
mpi_limb_t mpihelp_addmul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_size_t s1_size, mpi_limb_t s2_limb);
mpi_limb_t mpihelp_submul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_size_t s1_size, mpi_limb_t s2_limb);
void mpihelp_mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
mpi_size_t size);
mpi_limb_t mpihelp_mul( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
mpi_ptr_t vp, mpi_size_t vsize);
void mpih_sqr_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size );
void mpih_sqr_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size,
mpi_ptr_t tspace);
void mpihelp_mul_karatsuba_case( mpi_ptr_t prodp,
mpi_ptr_t up, mpi_size_t usize,
mpi_ptr_t vp, mpi_size_t vsize,
struct karatsuba_ctx *ctx );
/*-- mpihelp-mul_1.c (or xxx/cpu/ *.S) --*/
mpi_limb_t mpihelp_mul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_size_t s1_size, mpi_limb_t s2_limb);
/*-- mpihelp-div.c --*/
mpi_limb_t mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
mpi_limb_t divisor_limb);
mpi_limb_t mpihelp_divrem( mpi_ptr_t qp, mpi_size_t qextra_limbs,
mpi_ptr_t np, mpi_size_t nsize,
mpi_ptr_t dp, mpi_size_t dsize);
mpi_limb_t mpihelp_divmod_1( mpi_ptr_t quot_ptr,
mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
mpi_limb_t divisor_limb);
/*-- mpihelp-shift.c --*/
mpi_limb_t mpihelp_lshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
unsigned cnt);
mpi_limb_t mpihelp_rshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
unsigned cnt);
/* Define stuff for longlong.h. */
#define W_TYPE_SIZE BITS_PER_MPI_LIMB
typedef mpi_limb_t UWtype;
typedef unsigned int UHWtype;
#if defined (__GNUC__)
typedef unsigned int UQItype __attribute__ ((mode (QI)));
typedef int SItype __attribute__ ((mode (SI)));
typedef unsigned int USItype __attribute__ ((mode (SI)));
typedef int DItype __attribute__ ((mode (DI)));
typedef unsigned int UDItype __attribute__ ((mode (DI)));
#else
typedef unsigned char UQItype;
typedef long SItype;
typedef unsigned long USItype;
#endif
#ifdef __GNUC__
#include "mpi-inline.h"
#endif
#endif /*G10_MPI_INTERNAL_H*/
diff --git a/mpi/mpih-div.c b/mpi/mpih-div.c
index 235a8107b..eedfabf55 100644
--- a/mpi/mpih-div.c
+++ b/mpi/mpih-div.c
@@ -1,534 +1,534 @@
/* mpihelp-div.c - MPI helper functions
* Copyright (C) 1994, 1996 Free Software Foundation, Inc.
* Copyright (C) 1998, 1999 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 3 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, see .
*
* 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
#include
#include
#include "mpi-internal.h"
#include "longlong.h"
#ifndef UMUL_TIME
#define UMUL_TIME 1
#endif
#ifndef UDIV_TIME
#define UDIV_TIME UMUL_TIME
#endif
/* FIXME: We should be using invert_limb (or invert_normalized_limb)
* here (not udiv_qrnnd).
*/
mpi_limb_t
mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
mpi_limb_t divisor_limb)
{
mpi_size_t i;
mpi_limb_t n1, n0, r;
- int dummy;
+ int dummy GNUPG_GCC_ATTR_UNUSED;
/* Botch: Should this be handled at all? Rely on callers? */
if( !dividend_size )
return 0;
/* If multiplication is much faster than division, and the
* dividend is large, pre-invert the divisor, and use
* only multiplications in the inner loop.
*
* This test should be read:
* Does it ever help to use udiv_qrnnd_preinv?
* && Does what we save compensate for the inversion overhead?
*/
if( UDIV_TIME > (2 * UMUL_TIME + 6)
&& (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME ) {
int normalization_steps;
count_leading_zeros( normalization_steps, divisor_limb );
if( normalization_steps ) {
mpi_limb_t divisor_limb_inverted;
divisor_limb <<= normalization_steps;
/* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
* result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
* most significant bit (with weight 2**N) implicit.
*
* Special case for DIVISOR_LIMB == 100...000.
*/
if( !(divisor_limb << 1) )
divisor_limb_inverted = ~(mpi_limb_t)0;
else
udiv_qrnnd(divisor_limb_inverted, dummy,
-divisor_limb, 0, divisor_limb);
n1 = dividend_ptr[dividend_size - 1];
r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
/* Possible optimization:
* if (r == 0
* && divisor_limb > ((n1 << normalization_steps)
* | (dividend_ptr[dividend_size - 2] >> ...)))
* ...one division less...
*/
for( i = dividend_size - 2; i >= 0; i--) {
n0 = dividend_ptr[i];
UDIV_QRNND_PREINV(dummy, r, r,
((n1 << normalization_steps)
| (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
divisor_limb, divisor_limb_inverted);
n1 = n0;
}
UDIV_QRNND_PREINV(dummy, r, r,
n1 << normalization_steps,
divisor_limb, divisor_limb_inverted);
return r >> normalization_steps;
}
else {
mpi_limb_t divisor_limb_inverted;
/* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
* result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
* most significant bit (with weight 2**N) implicit.
*
* Special case for DIVISOR_LIMB == 100...000.
*/
if( !(divisor_limb << 1) )
divisor_limb_inverted = ~(mpi_limb_t)0;
else
udiv_qrnnd(divisor_limb_inverted, dummy,
-divisor_limb, 0, divisor_limb);
i = dividend_size - 1;
r = dividend_ptr[i];
if( r >= divisor_limb )
r = 0;
else
i--;
for( ; i >= 0; i--) {
n0 = dividend_ptr[i];
UDIV_QRNND_PREINV(dummy, r, r,
n0, divisor_limb, divisor_limb_inverted);
}
return r;
}
}
else {
if( UDIV_NEEDS_NORMALIZATION ) {
int normalization_steps;
count_leading_zeros(normalization_steps, divisor_limb);
if( normalization_steps ) {
divisor_limb <<= normalization_steps;
n1 = dividend_ptr[dividend_size - 1];
r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
/* Possible optimization:
* if (r == 0
* && divisor_limb > ((n1 << normalization_steps)
* | (dividend_ptr[dividend_size - 2] >> ...)))
* ...one division less...
*/
for(i = dividend_size - 2; i >= 0; i--) {
n0 = dividend_ptr[i];
udiv_qrnnd (dummy, r, r,
((n1 << normalization_steps)
| (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
divisor_limb);
n1 = n0;
}
udiv_qrnnd (dummy, r, r,
n1 << normalization_steps,
divisor_limb);
return r >> normalization_steps;
}
}
/* No normalization needed, either because udiv_qrnnd doesn't require
* it, or because DIVISOR_LIMB is already normalized. */
i = dividend_size - 1;
r = dividend_ptr[i];
if(r >= divisor_limb)
r = 0;
else
i--;
for(; i >= 0; i--) {
n0 = dividend_ptr[i];
udiv_qrnnd (dummy, r, r, n0, divisor_limb);
}
return r;
}
}
/* Divide num (NP/NSIZE) by den (DP/DSIZE) and write
* the NSIZE-DSIZE least significant quotient limbs at QP
* and the DSIZE long remainder at NP. If QEXTRA_LIMBS is
* non-zero, generate that many fraction bits and append them after the
* other quotient limbs.
* Return the most significant limb of the quotient, this is always 0 or 1.
*
* Preconditions:
* 0. NSIZE >= DSIZE.
* 1. The most significant bit of the divisor must be set.
* 2. QP must either not overlap with the input operands at all, or
* QP + DSIZE >= NP must hold true. (This means that it's
* possible to put the quotient in the high part of NUM, right after the
* remainder in NUM.
* 3. NSIZE >= DSIZE, even if QEXTRA_LIMBS is non-zero.
*/
mpi_limb_t
mpihelp_divrem( mpi_ptr_t qp, mpi_size_t qextra_limbs,
mpi_ptr_t np, mpi_size_t nsize,
mpi_ptr_t dp, mpi_size_t dsize)
{
mpi_limb_t most_significant_q_limb = 0;
switch(dsize) {
case 0:
/* We are asked to divide by zero, so go ahead and do it! (To make
the compiler not remove this statement, return the value.) */
return 1 / dsize;
case 1:
{
mpi_size_t i;
mpi_limb_t n1;
mpi_limb_t d;
d = dp[0];
n1 = np[nsize - 1];
if( n1 >= d ) {
n1 -= d;
most_significant_q_limb = 1;
}
qp += qextra_limbs;
for( i = nsize - 2; i >= 0; i--)
udiv_qrnnd( qp[i], n1, n1, np[i], d );
qp -= qextra_limbs;
for( i = qextra_limbs - 1; i >= 0; i-- )
udiv_qrnnd (qp[i], n1, n1, 0, d);
np[0] = n1;
}
break;
case 2:
{
mpi_size_t i;
mpi_limb_t n1, n0, n2;
mpi_limb_t d1, d0;
np += nsize - 2;
d1 = dp[1];
d0 = dp[0];
n1 = np[1];
n0 = np[0];
if( n1 >= d1 && (n1 > d1 || n0 >= d0) ) {
sub_ddmmss (n1, n0, n1, n0, d1, d0);
most_significant_q_limb = 1;
}
for( i = qextra_limbs + nsize - 2 - 1; i >= 0; i-- ) {
mpi_limb_t q;
mpi_limb_t r;
if( i >= qextra_limbs )
np--;
else
np[0] = 0;
if( n1 == d1 ) {
/* Q should be either 111..111 or 111..110. Need special
* treatment of this rare case as normal division would
* give overflow. */
q = ~(mpi_limb_t)0;
r = n0 + d1;
if( r < d1 ) { /* Carry in the addition? */
add_ssaaaa( n1, n0, r - d0, np[0], 0, d0 );
qp[i] = q;
continue;
}
n1 = d0 - (d0 != 0?1:0);
n0 = -d0;
}
else {
udiv_qrnnd (q, r, n1, n0, d1);
umul_ppmm (n1, n0, d0, q);
}
n2 = np[0];
q_test:
if( n1 > r || (n1 == r && n0 > n2) ) {
/* The estimated Q was too large. */
q--;
sub_ddmmss (n1, n0, n1, n0, 0, d0);
r += d1;
if( r >= d1 ) /* If not carry, test Q again. */
goto q_test;
}
qp[i] = q;
sub_ddmmss (n1, n0, r, n2, n1, n0);
}
np[1] = n1;
np[0] = n0;
}
break;
default:
{
mpi_size_t i;
mpi_limb_t dX, d1, n0;
np += nsize - dsize;
dX = dp[dsize - 1];
d1 = dp[dsize - 2];
n0 = np[dsize - 1];
if( n0 >= dX ) {
if(n0 > dX || mpihelp_cmp(np, dp, dsize - 1) >= 0 ) {
mpihelp_sub_n(np, np, dp, dsize);
n0 = np[dsize - 1];
most_significant_q_limb = 1;
}
}
for( i = qextra_limbs + nsize - dsize - 1; i >= 0; i--) {
mpi_limb_t q;
mpi_limb_t n1, n2;
mpi_limb_t cy_limb;
if( i >= qextra_limbs ) {
np--;
n2 = np[dsize];
}
else {
n2 = np[dsize - 1];
MPN_COPY_DECR (np + 1, np, dsize - 1);
np[0] = 0;
}
if( n0 == dX ) {
/* This might over-estimate q, but it's probably not worth
* the extra code here to find out. */
q = ~(mpi_limb_t)0;
}
else {
mpi_limb_t r;
udiv_qrnnd(q, r, n0, np[dsize - 1], dX);
umul_ppmm(n1, n0, d1, q);
while( n1 > r || (n1 == r && n0 > np[dsize - 2])) {
q--;
r += dX;
if( r < dX ) /* I.e. "carry in previous addition?" */
break;
n1 -= n0 < d1;
n0 -= d1;
}
}
/* Possible optimization: We already have (q * n0) and (1 * n1)
* after the calculation of q. Taking advantage of that, we
* could make this loop make two iterations less. */
cy_limb = mpihelp_submul_1(np, dp, dsize, q);
if( n2 != cy_limb ) {
mpihelp_add_n(np, np, dp, dsize);
q--;
}
qp[i] = q;
n0 = np[dsize - 1];
}
}
}
return most_significant_q_limb;
}
/****************
* Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB.
* Write DIVIDEND_SIZE limbs of quotient at QUOT_PTR.
* Return the single-limb remainder.
* There are no constraints on the value of the divisor.
*
* QUOT_PTR and DIVIDEND_PTR might point to the same limb.
*/
mpi_limb_t
mpihelp_divmod_1( mpi_ptr_t quot_ptr,
mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
mpi_limb_t divisor_limb)
{
mpi_size_t i;
mpi_limb_t n1, n0, r;
- int dummy;
+ int dummy GNUPG_GCC_ATTR_UNUSED;
if( !dividend_size )
return 0;
/* If multiplication is much faster than division, and the
* dividend is large, pre-invert the divisor, and use
* only multiplications in the inner loop.
*
* This test should be read:
* Does it ever help to use udiv_qrnnd_preinv?
* && Does what we save compensate for the inversion overhead?
*/
if( UDIV_TIME > (2 * UMUL_TIME + 6)
&& (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME ) {
int normalization_steps;
count_leading_zeros( normalization_steps, divisor_limb );
if( normalization_steps ) {
mpi_limb_t divisor_limb_inverted;
divisor_limb <<= normalization_steps;
/* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
* result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
* most significant bit (with weight 2**N) implicit.
*/
/* Special case for DIVISOR_LIMB == 100...000. */
if( !(divisor_limb << 1) )
divisor_limb_inverted = ~(mpi_limb_t)0;
else
udiv_qrnnd(divisor_limb_inverted, dummy,
-divisor_limb, 0, divisor_limb);
n1 = dividend_ptr[dividend_size - 1];
r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
/* Possible optimization:
* if (r == 0
* && divisor_limb > ((n1 << normalization_steps)
* | (dividend_ptr[dividend_size - 2] >> ...)))
* ...one division less...
*/
for( i = dividend_size - 2; i >= 0; i--) {
n0 = dividend_ptr[i];
UDIV_QRNND_PREINV( quot_ptr[i + 1], r, r,
((n1 << normalization_steps)
| (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
divisor_limb, divisor_limb_inverted);
n1 = n0;
}
UDIV_QRNND_PREINV( quot_ptr[0], r, r,
n1 << normalization_steps,
divisor_limb, divisor_limb_inverted);
return r >> normalization_steps;
}
else {
mpi_limb_t divisor_limb_inverted;
/* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
* result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
* most significant bit (with weight 2**N) implicit.
*/
/* Special case for DIVISOR_LIMB == 100...000. */
if( !(divisor_limb << 1) )
divisor_limb_inverted = ~(mpi_limb_t) 0;
else
udiv_qrnnd(divisor_limb_inverted, dummy,
-divisor_limb, 0, divisor_limb);
i = dividend_size - 1;
r = dividend_ptr[i];
if( r >= divisor_limb )
r = 0;
else
quot_ptr[i--] = 0;
for( ; i >= 0; i-- ) {
n0 = dividend_ptr[i];
UDIV_QRNND_PREINV( quot_ptr[i], r, r,
n0, divisor_limb, divisor_limb_inverted);
}
return r;
}
}
else {
if(UDIV_NEEDS_NORMALIZATION) {
int normalization_steps;
count_leading_zeros (normalization_steps, divisor_limb);
if( normalization_steps ) {
divisor_limb <<= normalization_steps;
n1 = dividend_ptr[dividend_size - 1];
r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
/* Possible optimization:
* if (r == 0
* && divisor_limb > ((n1 << normalization_steps)
* | (dividend_ptr[dividend_size - 2] >> ...)))
* ...one division less...
*/
for( i = dividend_size - 2; i >= 0; i--) {
n0 = dividend_ptr[i];
udiv_qrnnd (quot_ptr[i + 1], r, r,
((n1 << normalization_steps)
| (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
divisor_limb);
n1 = n0;
}
udiv_qrnnd (quot_ptr[0], r, r,
n1 << normalization_steps,
divisor_limb);
return r >> normalization_steps;
}
}
/* No normalization needed, either because udiv_qrnnd doesn't require
* it, or because DIVISOR_LIMB is already normalized. */
i = dividend_size - 1;
r = dividend_ptr[i];
if(r >= divisor_limb)
r = 0;
else
quot_ptr[i--] = 0;
for(; i >= 0; i--) {
n0 = dividend_ptr[i];
udiv_qrnnd( quot_ptr[i], r, r, n0, divisor_limb );
}
return r;
}
}