1/* mpi-internal.h - Internal to the Multi Precision Integers 2 * Copyright (C) 1994, 1996, 1998, 2000, 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#ifndef G10_MPI_INTERNAL_H 29#define G10_MPI_INTERNAL_H 30 31#include "mpi-asm-defs.h" 32 33#ifndef BITS_PER_MPI_LIMB 34#if BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_INT 35 typedef unsigned int mpi_limb_t; 36 typedef signed int mpi_limb_signed_t; 37#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_LONG 38 typedef unsigned long int mpi_limb_t; 39 typedef signed long int mpi_limb_signed_t; 40#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_LONG_LONG 41 typedef unsigned long long int mpi_limb_t; 42 typedef signed long long int mpi_limb_signed_t; 43#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_SHORT 44 typedef unsigned short int mpi_limb_t; 45 typedef signed short int mpi_limb_signed_t; 46#else 47#error BYTES_PER_MPI_LIMB does not match any C type 48#endif 49#define BITS_PER_MPI_LIMB (8*BYTES_PER_MPI_LIMB) 50#endif /*BITS_PER_MPI_LIMB*/ 51 52#include "mpi.h" 53 54/* If KARATSUBA_THRESHOLD is not already defined, define it to a 55 * value which is good on most machines. */ 56 57/* tested 4, 16, 32 and 64, where 16 gave the best performance when 58 * checking a 768 and a 1024 bit ElGamal signature. 59 * (wk 22.12.97) */ 60#ifndef KARATSUBA_THRESHOLD 61#define KARATSUBA_THRESHOLD 16 62#endif 63 64/* The code can't handle KARATSUBA_THRESHOLD smaller than 2. */ 65#if KARATSUBA_THRESHOLD < 2 66#undef KARATSUBA_THRESHOLD 67#define KARATSUBA_THRESHOLD 2 68#endif 69 70 71typedef mpi_limb_t *mpi_ptr_t; /* pointer to a limb */ 72typedef int mpi_size_t; /* (must be a signed type) */ 73 74#define ABS(x) (x >= 0 ? x : -x) 75#define MIN(l,o) ((l) < (o) ? (l) : (o)) 76#define MAX(h,i) ((h) > (i) ? (h) : (i)) 77#define RESIZE_IF_NEEDED(a,b) \ 78 do { \ 79 if( (a)->alloced < (b) ) \ 80 mpi_resize((a), (b)); \ 81 } while(0) 82 83/* Copy N limbs from S to D. */ 84#define MPN_COPY( d, s, n) \ 85 do { \ 86 mpi_size_t _i; \ 87 for( _i = 0; _i < (n); _i++ ) \ 88 (d)[_i] = (s)[_i]; \ 89 } while(0) 90 91#define MPN_COPY_INCR( d, s, n) \ 92 do { \ 93 mpi_size_t _i; \ 94 for( _i = 0; _i < (n); _i++ ) \ 95 (d)[_i] = (d)[_i]; \ 96 } while (0) 97 98#define MPN_COPY_DECR( d, s, n ) \ 99 do { \ 100 mpi_size_t _i; \ 101 for( _i = (n)-1; _i >= 0; _i--) \ 102 (d)[_i] = (s)[_i]; \ 103 } while(0) 104 105/* Zero N limbs at D */ 106#define MPN_ZERO(d, n) \ 107 do { \ 108 int _i; \ 109 for( _i = 0; _i < (n); _i++ ) \ 110 (d)[_i] = 0; \ 111 } while (0) 112 113#define MPN_NORMALIZE(d, n) \ 114 do { \ 115 while( (n) > 0 ) { \ 116 if( (d)[(n)-1] ) \ 117 break; \ 118 (n)--; \ 119 } \ 120 } while(0) 121 122#define MPN_NORMALIZE_NOT_ZERO(d, n) \ 123 do { \ 124 for(;;) { \ 125 if( (d)[(n)-1] ) \ 126 break; \ 127 (n)--; \ 128 } \ 129 } while(0) 130 131#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \ 132 do { \ 133 if( (size) < KARATSUBA_THRESHOLD ) \ 134 mul_n_basecase (prodp, up, vp, size); \ 135 else \ 136 mul_n (prodp, up, vp, size, tspace); \ 137 } while (0); 138 139 140/* Divide the two-limb number in (NH,,NL) by D, with DI being the largest 141 * limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB). 142 * If this would yield overflow, DI should be the largest possible number 143 * (i.e., only ones). For correct operation, the most significant bit of D 144 * has to be set. Put the quotient in Q and the remainder in R. 145 */ 146#define UDIV_QRNND_PREINV(q, r, nh, nl, d, di) \ 147 do { \ 148 mpi_limb_t _q, _ql, _r; \ 149 mpi_limb_t _xh, _xl; \ 150 umul_ppmm (_q, _ql, (nh), (di)); \ 151 _q += (nh); /* DI is 2**BITS_PER_MPI_LIMB too small */ \ 152 umul_ppmm (_xh, _xl, _q, (d)); \ 153 sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl); \ 154 if( _xh ) { \ 155 sub_ddmmss (_xh, _r, _xh, _r, 0, (d)); \ 156 _q++; \ 157 if( _xh) { \ 158 sub_ddmmss (_xh, _r, _xh, _r, 0, (d)); \ 159 _q++; \ 160 } \ 161 } \ 162 if( _r >= (d) ) { \ 163 _r -= (d); \ 164 _q++; \ 165 } \ 166 (r) = _r; \ 167 (q) = _q; \ 168 } while (0) 169 170 171/*-- mpiutil.c --*/ 172#define mpi_alloc_limb_space(n,f) _gcry_mpi_alloc_limb_space((n),(f)) 173mpi_ptr_t _gcry_mpi_alloc_limb_space( unsigned nlimbs, int sec ); 174void _gcry_mpi_free_limb_space( mpi_ptr_t a, unsigned int nlimbs ); 175void _gcry_mpi_assign_limb_space( gcry_mpi_t a, mpi_ptr_t ap, unsigned nlimbs ); 176 177/*-- mpi-bit.c --*/ 178#define mpi_rshift_limbs(a,n) _gcry_mpi_rshift_limbs ((a), (n)) 179#define mpi_lshift_limbs(a,n) _gcry_mpi_lshift_limbs ((a), (n)) 180 181void _gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count ); 182void _gcry_mpi_lshift_limbs( gcry_mpi_t a, unsigned int count ); 183 184 185/*-- mpih-add.c --*/ 186mpi_limb_t _gcry_mpih_add_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, 187 mpi_size_t s1_size, mpi_limb_t s2_limb ); 188mpi_limb_t _gcry_mpih_add_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, 189 mpi_ptr_t s2_ptr, mpi_size_t size); 190mpi_limb_t _gcry_mpih_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, 191 mpi_ptr_t s2_ptr, mpi_size_t s2_size); 192 193/*-- mpih-sub.c --*/ 194mpi_limb_t _gcry_mpih_sub_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, 195 mpi_size_t s1_size, mpi_limb_t s2_limb ); 196mpi_limb_t _gcry_mpih_sub_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, 197 mpi_ptr_t s2_ptr, mpi_size_t size); 198mpi_limb_t _gcry_mpih_sub(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, 199 mpi_ptr_t s2_ptr, mpi_size_t s2_size); 200 201/*-- mpih-cmp.c --*/ 202int _gcry_mpih_cmp( mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size ); 203 204/*-- mpih-mul.c --*/ 205 206struct karatsuba_ctx { 207 struct karatsuba_ctx *next; 208 mpi_ptr_t tspace; 209 unsigned int tspace_nlimbs; 210 mpi_size_t tspace_size; 211 mpi_ptr_t tp; 212 unsigned int tp_nlimbs; 213 mpi_size_t tp_size; 214}; 215 216void _gcry_mpih_release_karatsuba_ctx( struct karatsuba_ctx *ctx ); 217 218mpi_limb_t _gcry_mpih_addmul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, 219 mpi_size_t s1_size, mpi_limb_t s2_limb); 220mpi_limb_t _gcry_mpih_submul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, 221 mpi_size_t s1_size, mpi_limb_t s2_limb); 222void _gcry_mpih_mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, 223 mpi_size_t size); 224mpi_limb_t _gcry_mpih_mul( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, 225 mpi_ptr_t vp, mpi_size_t vsize); 226void _gcry_mpih_sqr_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size ); 227void _gcry_mpih_sqr_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, 228 mpi_ptr_t tspace); 229 230void _gcry_mpih_mul_karatsuba_case( mpi_ptr_t prodp, 231 mpi_ptr_t up, mpi_size_t usize, 232 mpi_ptr_t vp, mpi_size_t vsize, 233 struct karatsuba_ctx *ctx ); 234 235 236/*-- mpih-mul_1.c (or xxx/cpu/ *.S) --*/ 237mpi_limb_t _gcry_mpih_mul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, 238 mpi_size_t s1_size, mpi_limb_t s2_limb); 239 240/*-- mpih-div.c --*/ 241mpi_limb_t _gcry_mpih_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size, 242 mpi_limb_t divisor_limb); 243mpi_limb_t _gcry_mpih_divrem( mpi_ptr_t qp, mpi_size_t qextra_limbs, 244 mpi_ptr_t np, mpi_size_t nsize, 245 mpi_ptr_t dp, mpi_size_t dsize); 246mpi_limb_t _gcry_mpih_divmod_1( mpi_ptr_t quot_ptr, 247 mpi_ptr_t dividend_ptr, mpi_size_t dividend_size, 248 mpi_limb_t divisor_limb); 249 250/*-- mpih-shift.c --*/ 251mpi_limb_t _gcry_mpih_lshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, 252 unsigned cnt); 253mpi_limb_t _gcry_mpih_rshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, 254 unsigned cnt); 255 256 257/* Define stuff for longlong.h. */ 258#define W_TYPE_SIZE BITS_PER_MPI_LIMB 259 typedef mpi_limb_t UWtype; 260 typedef unsigned int UHWtype; 261#if defined (__GNUC__) 262 typedef unsigned int UQItype __attribute__ ((mode (QI))); 263 typedef int SItype __attribute__ ((mode (SI))); 264 typedef unsigned int USItype __attribute__ ((mode (SI))); 265 typedef int DItype __attribute__ ((mode (DI))); 266 typedef unsigned int UDItype __attribute__ ((mode (DI))); 267#else 268 typedef unsigned char UQItype; 269 typedef long SItype; 270 typedef unsigned long USItype; 271#endif 272 273#ifdef __GNUC__ 274#include "mpi-inline.h" 275#endif 276 277#endif /*G10_MPI_INTERNAL_H*/ 278