raw
smg_comms_c_wrappers    1 /* mpi-internal.h  -  Internal to the Multi Precision Integers
smg_comms_c_wrappers    2  * Modified by No Such Labs. (C) 2015. See README.
smg_comms_c_wrappers    3  * Modified by S.MG, 2017: fixing broken MPN_COPY_INCR macro. See EuCrypt patches.
smg_comms_c_wrappers    4  *
smg_comms_c_wrappers    5  * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
smg_comms_c_wrappers    6  * SHA256(gnupg-1.4.10.tar.gz):
smg_comms_c_wrappers    7  *        0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
smg_comms_c_wrappers    8  * (C) 1994-2005 Free Software Foundation, Inc.
smg_comms_c_wrappers    9  *
smg_comms_c_wrappers   10  * This program is free software: you can redistribute it and/or modify
smg_comms_c_wrappers   11  * it under the terms of the GNU General Public License as published by
smg_comms_c_wrappers   12  * the Free Software Foundation, either version 3 of the License, or
smg_comms_c_wrappers   13  * (at your option) any later version.
smg_comms_c_wrappers   14  *
smg_comms_c_wrappers   15  * This program is distributed in the hope that it will be useful,
smg_comms_c_wrappers   16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
smg_comms_c_wrappers   17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
smg_comms_c_wrappers   18  * GNU General Public License for more details.
smg_comms_c_wrappers   19  *
smg_comms_c_wrappers   20  * You should have received a copy of the GNU General Public License
smg_comms_c_wrappers   21  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
smg_comms_c_wrappers   22  */
smg_comms_c_wrappers   23 
smg_comms_c_wrappers   24 #ifndef G10_MPI_INTERNAL_H
smg_comms_c_wrappers   25 #define G10_MPI_INTERNAL_H
smg_comms_c_wrappers   26 
smg_comms_c_wrappers   27 #include "mpi.h"
smg_comms_c_wrappers   28 
smg_comms_c_wrappers   29 /* from the old mpi-asm-defs.h */
smg_comms_c_wrappers   30 #define BYTES_PER_MPI_LIMB  (SIZEOF_UNSIGNED_LONG)
smg_comms_c_wrappers   31 
smg_comms_c_wrappers   32 #if BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_INT
smg_comms_c_wrappers   33   typedef unsigned int mpi_limb_t;
smg_comms_c_wrappers   34   typedef   signed int mpi_limb_signed_t;
smg_comms_c_wrappers   35 #elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_LONG
smg_comms_c_wrappers   36   typedef unsigned long int mpi_limb_t;
smg_comms_c_wrappers   37   typedef   signed long int mpi_limb_signed_t;
smg_comms_c_wrappers   38 #elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_LONG_LONG
smg_comms_c_wrappers   39   typedef unsigned long long int mpi_limb_t;
smg_comms_c_wrappers   40   typedef   signed long long int mpi_limb_signed_t;
smg_comms_c_wrappers   41 #elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_SHORT
smg_comms_c_wrappers   42   typedef unsigned short int mpi_limb_t;
smg_comms_c_wrappers   43   typedef   signed short int mpi_limb_signed_t;
smg_comms_c_wrappers   44 #else
smg_comms_c_wrappers   45 #error BYTES_PER_MPI_LIMB does not match any C type
smg_comms_c_wrappers   46 #endif
smg_comms_c_wrappers   47 #define BITS_PER_MPI_LIMB    (8*BYTES_PER_MPI_LIMB)
smg_comms_c_wrappers   48 
smg_comms_c_wrappers   49 
smg_comms_c_wrappers   50 struct gcry_mpi {
smg_comms_c_wrappers   51     int alloced;    /* array size (# of allocated limbs) */
smg_comms_c_wrappers   52     int nlimbs;     /* number of valid limbs */
smg_comms_c_wrappers   53     unsigned int nbits; /* the real number of valid bits (info only) */
smg_comms_c_wrappers   54     int sign;	    /* indicates a negative number */
smg_comms_c_wrappers   55     unsigned flags; /* bit 0: array must be allocated in secure memory space */
smg_comms_c_wrappers   56 		    /* bit 1: not used */
smg_comms_c_wrappers   57 		    /* bit 2: the limb is a pointer to some xmalloced data */
smg_comms_c_wrappers   58     mpi_limb_t *d;  /* array with the limbs */
smg_comms_c_wrappers   59 };
smg_comms_c_wrappers   60 
smg_comms_c_wrappers   61 
smg_comms_c_wrappers   62 
smg_comms_c_wrappers   63 /* If KARATSUBA_THRESHOLD is not already defined, define it to a
smg_comms_c_wrappers   64  * value which is good on most machines.  */
smg_comms_c_wrappers   65 
smg_comms_c_wrappers   66 /* tested 4, 16, 32 and 64, where 16 gave the best performance when
smg_comms_c_wrappers   67  * checking a 768 and a 1024 bit ElGamal signature.
smg_comms_c_wrappers   68  * (wk 22.12.97) */
smg_comms_c_wrappers   69 #ifndef KARATSUBA_THRESHOLD
smg_comms_c_wrappers   70 #define KARATSUBA_THRESHOLD 16
smg_comms_c_wrappers   71 #endif
smg_comms_c_wrappers   72 
smg_comms_c_wrappers   73 /* The code can't handle KARATSUBA_THRESHOLD smaller than 2.  */
smg_comms_c_wrappers   74 #if KARATSUBA_THRESHOLD < 2
smg_comms_c_wrappers   75 #undef KARATSUBA_THRESHOLD
smg_comms_c_wrappers   76 #define KARATSUBA_THRESHOLD 2
smg_comms_c_wrappers   77 #endif
smg_comms_c_wrappers   78 
smg_comms_c_wrappers   79 
smg_comms_c_wrappers   80 typedef mpi_limb_t *mpi_ptr_t; /* pointer to a limb */
smg_comms_c_wrappers   81 typedef int mpi_size_t;        /* (must be a signed type) */
smg_comms_c_wrappers   82 
smg_comms_c_wrappers   83 #define ABS(x) (x >= 0 ? x : -x)
smg_comms_c_wrappers   84 #define MIN(l,o) ((l) < (o) ? (l) : (o))
smg_comms_c_wrappers   85 #define MAX(h,i) ((h) > (i) ? (h) : (i))
smg_comms_c_wrappers   86 #define RESIZE_IF_NEEDED(a,b) \
smg_comms_c_wrappers   87     do {			   \
smg_comms_c_wrappers   88 	if( (a)->alloced < (b) )   \
smg_comms_c_wrappers   89 	    mpi_resize((a), (b));  \
smg_comms_c_wrappers   90     } while(0)
smg_comms_c_wrappers   91 
smg_comms_c_wrappers   92 /* Copy N limbs from S to D.  */
smg_comms_c_wrappers   93 #define MPN_COPY( d, s, n) \
smg_comms_c_wrappers   94     do {				\
smg_comms_c_wrappers   95 	mpi_size_t _i;			\
smg_comms_c_wrappers   96 	for( _i = 0; _i < (n); _i++ )	\
smg_comms_c_wrappers   97 	    (d)[_i] = (s)[_i];		\
smg_comms_c_wrappers   98     } while(0)
smg_comms_c_wrappers   99 
smg_comms_c_wrappers  100 #define MPN_COPY_INCR( d, s, n) 	\
smg_comms_c_wrappers  101     do {				\
smg_comms_c_wrappers  102 	mpi_size_t _i;			\
smg_comms_c_wrappers  103 	for( _i = 0; _i < (n); _i++ )	\
smg_comms_c_wrappers  104 	    (d)[_i] = (s)[_i];		\
smg_comms_c_wrappers  105     } while (0)
smg_comms_c_wrappers  106 
smg_comms_c_wrappers  107 #define MPN_COPY_DECR( d, s, n ) \
smg_comms_c_wrappers  108     do {				\
smg_comms_c_wrappers  109 	mpi_size_t _i;			\
smg_comms_c_wrappers  110 	for( _i = (n)-1; _i >= 0; _i--) \
smg_comms_c_wrappers  111 	   (d)[_i] = (s)[_i];		\
smg_comms_c_wrappers  112     } while(0)
smg_comms_c_wrappers  113 
smg_comms_c_wrappers  114 /* Zero N limbs at D */
smg_comms_c_wrappers  115 #define MPN_ZERO(d, n) \
smg_comms_c_wrappers  116     do {				  \
smg_comms_c_wrappers  117 	int  _i;			  \
smg_comms_c_wrappers  118 	for( _i = 0; _i < (n); _i++ )  \
smg_comms_c_wrappers  119 	    (d)[_i] = 0;		    \
smg_comms_c_wrappers  120     } while (0)
smg_comms_c_wrappers  121 
smg_comms_c_wrappers  122 #define MPN_NORMALIZE(d, n)  \
smg_comms_c_wrappers  123     do {		       \
smg_comms_c_wrappers  124 	while( (n) > 0 ) {     \
smg_comms_c_wrappers  125 	    if( (d)[(n)-1] ) \
smg_comms_c_wrappers  126 		break;	       \
smg_comms_c_wrappers  127 	    (n)--;	       \
smg_comms_c_wrappers  128 	}		       \
smg_comms_c_wrappers  129     } while(0)
smg_comms_c_wrappers  130 
smg_comms_c_wrappers  131 #define MPN_NORMALIZE_NOT_ZERO(d, n) \
smg_comms_c_wrappers  132     do {				    \
smg_comms_c_wrappers  133 	for(;;) {			    \
smg_comms_c_wrappers  134 	    if( (d)[(n)-1] )		    \
smg_comms_c_wrappers  135 		break;			    \
smg_comms_c_wrappers  136 	    (n)--;			    \
smg_comms_c_wrappers  137 	}				    \
smg_comms_c_wrappers  138     } while(0)
smg_comms_c_wrappers  139 
smg_comms_c_wrappers  140 #define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
smg_comms_c_wrappers  141     do {						\
smg_comms_c_wrappers  142 	if( (size) < KARATSUBA_THRESHOLD )		\
smg_comms_c_wrappers  143 	    mul_n_basecase (prodp, up, vp, size);	\
smg_comms_c_wrappers  144 	else						\
smg_comms_c_wrappers  145 	    mul_n (prodp, up, vp, size, tspace);	\
smg_comms_c_wrappers  146     } while (0);
smg_comms_c_wrappers  147 
smg_comms_c_wrappers  148 
smg_comms_c_wrappers  149 /* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
smg_comms_c_wrappers  150  * limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB).
smg_comms_c_wrappers  151  * If this would yield overflow, DI should be the largest possible number
smg_comms_c_wrappers  152  * (i.e., only ones).  For correct operation, the most significant bit of D
smg_comms_c_wrappers  153  * has to be set.  Put the quotient in Q and the remainder in R.
smg_comms_c_wrappers  154  */
smg_comms_c_wrappers  155 #define UDIV_QRNND_PREINV(q, r, nh, nl, d, di) \
smg_comms_c_wrappers  156     do {							    \
smg_comms_c_wrappers  157 	mpi_limb_t _q, _ql, _r; 				    \
smg_comms_c_wrappers  158 	mpi_limb_t _xh, _xl;					    \
smg_comms_c_wrappers  159 	umul_ppmm (_q, _ql, (nh), (di));			    \
smg_comms_c_wrappers  160 	_q += (nh);	/* DI is 2**BITS_PER_MPI_LIMB too small */  \
smg_comms_c_wrappers  161 	umul_ppmm (_xh, _xl, _q, (d));				    \
smg_comms_c_wrappers  162 	sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl);		    \
smg_comms_c_wrappers  163 	if( _xh ) {						    \
smg_comms_c_wrappers  164 	    sub_ddmmss (_xh, _r, _xh, _r, 0, (d));		    \
smg_comms_c_wrappers  165 	    _q++;						    \
smg_comms_c_wrappers  166 	    if( _xh) {						    \
smg_comms_c_wrappers  167 		sub_ddmmss (_xh, _r, _xh, _r, 0, (d));		    \
smg_comms_c_wrappers  168 		_q++;						    \
smg_comms_c_wrappers  169 	    }							    \
smg_comms_c_wrappers  170 	}							    \
smg_comms_c_wrappers  171 	if( _r >= (d) ) {					    \
smg_comms_c_wrappers  172 	    _r -= (d);						    \
smg_comms_c_wrappers  173 	    _q++;						    \
smg_comms_c_wrappers  174 	}							    \
smg_comms_c_wrappers  175 	(r) = _r;						    \
smg_comms_c_wrappers  176 	(q) = _q;						    \
smg_comms_c_wrappers  177     } while (0)
smg_comms_c_wrappers  178 
smg_comms_c_wrappers  179 
smg_comms_c_wrappers  180 /*-- mpiutil.c --*/
smg_comms_c_wrappers  181 #ifdef M_DEBUG
smg_comms_c_wrappers  182 #define mpi_alloc_limb_space(n,f)  mpi_debug_alloc_limb_space((n),(f), M_DBGINFO( __LINE__ ) )
smg_comms_c_wrappers  183 #define mpi_free_limb_space(n)  mpi_debug_free_limb_space((n),  M_DBGINFO( __LINE__ ) )
smg_comms_c_wrappers  184   mpi_ptr_t mpi_debug_alloc_limb_space( unsigned nlimbs, int sec, const char *info  );
smg_comms_c_wrappers  185   void mpi_debug_free_limb_space( mpi_ptr_t a, const char *info );
smg_comms_c_wrappers  186 #else
smg_comms_c_wrappers  187   mpi_ptr_t mpi_alloc_limb_space( unsigned nlimbs, int sec );
smg_comms_c_wrappers  188   void mpi_free_limb_space( mpi_ptr_t a );
smg_comms_c_wrappers  189 #endif
smg_comms_c_wrappers  190 void mpi_assign_limb_space( MPI a, mpi_ptr_t ap, unsigned nlimbs );
smg_comms_c_wrappers  191 
smg_comms_c_wrappers  192 /*-- mpi-bit.c --*/
smg_comms_c_wrappers  193 void mpi_rshift_limbs( MPI a, unsigned int count );
smg_comms_c_wrappers  194 void mpi_lshift_limbs( MPI a, unsigned int count );
smg_comms_c_wrappers  195 
smg_comms_c_wrappers  196 
smg_comms_c_wrappers  197 /*-- mpihelp-add.c --*/
smg_comms_c_wrappers  198 mpi_limb_t mpihelp_add_1(mpi_ptr_t res_ptr,  mpi_ptr_t s1_ptr,
smg_comms_c_wrappers  199 			 mpi_size_t s1_size, mpi_limb_t s2_limb );
smg_comms_c_wrappers  200 mpi_limb_t mpihelp_add_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
smg_comms_c_wrappers  201 			  mpi_ptr_t s2_ptr,  mpi_size_t size);
smg_comms_c_wrappers  202 mpi_limb_t mpihelp_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
smg_comms_c_wrappers  203 		       mpi_ptr_t s2_ptr, mpi_size_t s2_size);
smg_comms_c_wrappers  204 
smg_comms_c_wrappers  205 /*-- mpihelp-sub.c --*/
smg_comms_c_wrappers  206 mpi_limb_t mpihelp_sub_1( mpi_ptr_t res_ptr,  mpi_ptr_t s1_ptr,
smg_comms_c_wrappers  207 			  mpi_size_t s1_size, mpi_limb_t s2_limb );
smg_comms_c_wrappers  208 mpi_limb_t mpihelp_sub_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
smg_comms_c_wrappers  209 			  mpi_ptr_t s2_ptr, mpi_size_t size);
smg_comms_c_wrappers  210 mpi_limb_t mpihelp_sub(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
smg_comms_c_wrappers  211 		       mpi_ptr_t s2_ptr, mpi_size_t s2_size);
smg_comms_c_wrappers  212 
smg_comms_c_wrappers  213 /*-- mpihelp-cmp.c --*/
smg_comms_c_wrappers  214 int mpihelp_cmp( mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size );
smg_comms_c_wrappers  215 
smg_comms_c_wrappers  216 /*-- mpihelp-mul.c --*/
smg_comms_c_wrappers  217 
smg_comms_c_wrappers  218 struct karatsuba_ctx {
smg_comms_c_wrappers  219     struct karatsuba_ctx *next;
smg_comms_c_wrappers  220     mpi_ptr_t tspace;
smg_comms_c_wrappers  221     mpi_size_t tspace_size;
smg_comms_c_wrappers  222     mpi_ptr_t tp;
smg_comms_c_wrappers  223     mpi_size_t tp_size;
smg_comms_c_wrappers  224 };
smg_comms_c_wrappers  225 
smg_comms_c_wrappers  226 void mpihelp_release_karatsuba_ctx( struct karatsuba_ctx *ctx );
smg_comms_c_wrappers  227 
smg_comms_c_wrappers  228 mpi_limb_t mpihelp_addmul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
smg_comms_c_wrappers  229 			     mpi_size_t s1_size, mpi_limb_t s2_limb);
smg_comms_c_wrappers  230 mpi_limb_t mpihelp_submul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
smg_comms_c_wrappers  231 			     mpi_size_t s1_size, mpi_limb_t s2_limb);
smg_comms_c_wrappers  232 void mpihelp_mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
smg_comms_c_wrappers  233 						   mpi_size_t size);
smg_comms_c_wrappers  234 mpi_limb_t mpihelp_mul( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
smg_comms_c_wrappers  235 					 mpi_ptr_t vp, mpi_size_t vsize);
smg_comms_c_wrappers  236 void mpih_sqr_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size );
smg_comms_c_wrappers  237 void mpih_sqr_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size,
smg_comms_c_wrappers  238 						mpi_ptr_t tspace);
smg_comms_c_wrappers  239 
smg_comms_c_wrappers  240 void mpihelp_mul_karatsuba_case( mpi_ptr_t prodp,
smg_comms_c_wrappers  241 				 mpi_ptr_t up, mpi_size_t usize,
smg_comms_c_wrappers  242 				 mpi_ptr_t vp, mpi_size_t vsize,
smg_comms_c_wrappers  243 				 struct karatsuba_ctx *ctx );
smg_comms_c_wrappers  244 
smg_comms_c_wrappers  245 
smg_comms_c_wrappers  246 /*-- mpihelp-mul_1.c (or xxx/cpu/ *.S) --*/
smg_comms_c_wrappers  247 mpi_limb_t mpihelp_mul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
smg_comms_c_wrappers  248 			  mpi_size_t s1_size, mpi_limb_t s2_limb);
smg_comms_c_wrappers  249 
smg_comms_c_wrappers  250 /*-- mpihelp-div.c --*/
smg_comms_c_wrappers  251 mpi_limb_t mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
smg_comms_c_wrappers  252 						 mpi_limb_t divisor_limb);
smg_comms_c_wrappers  253 mpi_limb_t mpihelp_divrem( mpi_ptr_t qp, mpi_size_t qextra_limbs,
smg_comms_c_wrappers  254 			   mpi_ptr_t np, mpi_size_t nsize,
smg_comms_c_wrappers  255 			   mpi_ptr_t dp, mpi_size_t dsize);
smg_comms_c_wrappers  256 mpi_limb_t mpihelp_divmod_1( mpi_ptr_t quot_ptr,
smg_comms_c_wrappers  257 			     mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
smg_comms_c_wrappers  258 			     mpi_limb_t divisor_limb);
smg_comms_c_wrappers  259 
smg_comms_c_wrappers  260 /*-- mpihelp-shift.c --*/
smg_comms_c_wrappers  261 mpi_limb_t mpihelp_lshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
smg_comms_c_wrappers  262 							   unsigned cnt);
smg_comms_c_wrappers  263 mpi_limb_t mpihelp_rshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
smg_comms_c_wrappers  264 							   unsigned cnt);
smg_comms_c_wrappers  265 
smg_comms_c_wrappers  266 
smg_comms_c_wrappers  267 /* Define stuff for longlong.h.  */
smg_comms_c_wrappers  268 #define W_TYPE_SIZE BITS_PER_MPI_LIMB
smg_comms_c_wrappers  269   typedef mpi_limb_t   UWtype;
smg_comms_c_wrappers  270   typedef unsigned int UHWtype;
smg_comms_c_wrappers  271 #if defined (__GNUC__)
smg_comms_c_wrappers  272   typedef unsigned int UQItype	  __attribute__ ((mode (QI)));
smg_comms_c_wrappers  273   typedef	   int SItype	  __attribute__ ((mode (SI)));
smg_comms_c_wrappers  274   typedef unsigned int USItype	  __attribute__ ((mode (SI)));
smg_comms_c_wrappers  275   typedef	   int DItype	  __attribute__ ((mode (DI)));
smg_comms_c_wrappers  276   typedef unsigned int UDItype	  __attribute__ ((mode (DI)));
smg_comms_c_wrappers  277 #else
smg_comms_c_wrappers  278   typedef unsigned char UQItype;
smg_comms_c_wrappers  279   typedef	   long SItype;
smg_comms_c_wrappers  280   typedef unsigned long USItype;
smg_comms_c_wrappers  281 #endif
smg_comms_c_wrappers  282 
smg_comms_c_wrappers  283 #ifdef __GNUC__
smg_comms_c_wrappers  284 #include "mpi-inline.h"
smg_comms_c_wrappers  285 #endif
smg_comms_c_wrappers  286 
smg_comms_c_wrappers  287 #endif /*G10_MPI_INTERNAL_H*/