1 /* 2 * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved. 3 * Use is subject to license terms. 4 * 5 * This library is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Lesser General Public 7 * License as published by the Free Software Foundation; either 8 * version 2.1 of the License, or (at your option) any later version. 9 * 10 * This library is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * Lesser General Public License for more details. 14 * 15 * You should have received a copy of the GNU Lesser General Public License 16 * along with this library; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 /* ********************************************************************* 25 * 26 * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library. 27 * 28 * The Initial Developer of the Original Code is 29 * Michael J. Fromberger. 30 * Portions created by the Initial Developer are Copyright (C) 1998 31 * the Initial Developer. All Rights Reserved. 32 * 33 * Contributor(s): 34 * Netscape Communications Corporation 35 * 36 *********************************************************************** */ 37 38 /* Arbitrary precision integer arithmetic library 39 * 40 * NOTE WELL: the content of this header file is NOT part of the "public" 41 * API for the MPI library, and may change at any time. 42 * Application programs that use libmpi should NOT include this header file. 43 */ 44 45 #ifndef _MPI_PRIV_H 46 #define _MPI_PRIV_H 47 48 /* $Id: mpi-priv.h,v 1.20 2005/11/22 07:16:43 relyea%netscape.com Exp $ */ 49 50 #include "mpi.h" 51 #ifndef _KERNEL 52 #include <stdlib.h> 53 #include <string.h> 54 #include <ctype.h> 55 #endif /* _KERNEL */ 56 57 #if MP_DEBUG 58 #include <stdio.h> 59 60 #define DIAG(T,V) {fprintf(stderr,T);mp_print(V,stderr);fputc('\n',stderr);} 61 #else 62 #define DIAG(T,V) 63 #endif 64 65 /* If we aren't using a wired-in logarithm table, we need to include 66 the math library to get the log() function 67 */ 68 69 /* {{{ s_logv_2[] - log table for 2 in various bases */ 70 71 #if MP_LOGTAB 72 /* 73 A table of the logs of 2 for various bases (the 0 and 1 entries of 74 this table are meaningless and should not be referenced). 75 76 This table is used to compute output lengths for the mp_toradix() 77 function. Since a number n in radix r takes up about log_r(n) 78 digits, we estimate the output size by taking the least integer 79 greater than log_r(n), where: 80 81 log_r(n) = log_2(n) * log_r(2) 82 83 This table, therefore, is a table of log_r(2) for 2 <= r <= 36, 84 which are the output bases supported. 85 */ 86 87 extern const float s_logv_2[]; 88 #define LOG_V_2(R) s_logv_2[(R)] 89 90 #else 91 92 /* 93 If MP_LOGTAB is not defined, use the math library to compute the 94 logarithms on the fly. Otherwise, use the table. 95 Pick which works best for your system. 96 */ 97 98 #include <math.h> 99 #define LOG_V_2(R) (log(2.0)/log(R)) 100 101 #endif /* if MP_LOGTAB */ 102 103 /* }}} */ 104 105 /* {{{ Digit arithmetic macros */ 106 107 /* 108 When adding and multiplying digits, the results can be larger than 109 can be contained in an mp_digit. Thus, an mp_word is used. These 110 macros mask off the upper and lower digits of the mp_word (the 111 mp_word may be more than 2 mp_digits wide, but we only concern 112 ourselves with the low-order 2 mp_digits) 113 */ 114 115 #define CARRYOUT(W) (mp_digit)((W)>>DIGIT_BIT) 116 #define ACCUM(W) (mp_digit)(W) 117 118 #define MP_MIN(a,b) (((a) < (b)) ? (a) : (b)) 119 #define MP_MAX(a,b) (((a) > (b)) ? (a) : (b)) 120 #define MP_HOWMANY(a,b) (((a) + (b) - 1)/(b)) 121 #define MP_ROUNDUP(a,b) (MP_HOWMANY(a,b) * (b)) 122 123 /* }}} */ 124 125 /* {{{ Comparison constants */ 126 127 #define MP_LT -1 128 #define MP_EQ 0 129 #define MP_GT 1 130 131 /* }}} */ 132 133 /* {{{ private function declarations */ 134 135 /* 136 If MP_MACRO is false, these will be defined as actual functions; 137 otherwise, suitable macro definitions will be used. This works 138 around the fact that ANSI C89 doesn't support an 'inline' keyword 139 (although I hear C9x will ... about bloody time). At present, the 140 macro definitions are identical to the function bodies, but they'll 141 expand in place, instead of generating a function call. 142 143 I chose these particular functions to be made into macros because 144 some profiling showed they are called a lot on a typical workload, 145 and yet they are primarily housekeeping. 146 */ 147 #if MP_MACRO == 0 148 void s_mp_setz(mp_digit *dp, mp_size count); /* zero digits */ 149 void s_mp_copy(const mp_digit *sp, mp_digit *dp, mp_size count); /* copy */ 150 void *s_mp_alloc(size_t nb, size_t ni, int flag); /* general allocator */ 151 void s_mp_free(void *ptr, mp_size); /* general free function */ 152 extern unsigned long mp_allocs; 153 extern unsigned long mp_frees; 154 extern unsigned long mp_copies; 155 #else 156 157 /* Even if these are defined as macros, we need to respect the settings 158 of the MP_MEMSET and MP_MEMCPY configuration options... 159 */ 160 #if MP_MEMSET == 0 161 #define s_mp_setz(dp, count) \ 162 {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=0;} 163 #else 164 #define s_mp_setz(dp, count) memset(dp, 0, (count) * sizeof(mp_digit)) 165 #endif /* MP_MEMSET */ 166 167 #if MP_MEMCPY == 0 168 #define s_mp_copy(sp, dp, count) \ 169 {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=(sp)[ix];} 170 #else 171 #define s_mp_copy(sp, dp, count) memcpy(dp, sp, (count) * sizeof(mp_digit)) 172 #endif /* MP_MEMCPY */ 173 174 #define s_mp_alloc(nb, ni) calloc(nb, ni) 175 #define s_mp_free(ptr) {if(ptr) free(ptr);} 176 #endif /* MP_MACRO */ 177 178 mp_err s_mp_grow(mp_int *mp, mp_size min); /* increase allocated size */ 179 mp_err s_mp_pad(mp_int *mp, mp_size min); /* left pad with zeroes */ 180 181 #if MP_MACRO == 0 182 void s_mp_clamp(mp_int *mp); /* clip leading zeroes */ 183 #else 184 #define s_mp_clamp(mp)\ 185 { mp_size used = MP_USED(mp); \ 186 while (used > 1 && DIGIT(mp, used - 1) == 0) --used; \ 187 MP_USED(mp) = used; \ 188 } 189 #endif /* MP_MACRO */ 190 191 void s_mp_exch(mp_int *a, mp_int *b); /* swap a and b in place */ 192 193 mp_err s_mp_lshd(mp_int *mp, mp_size p); /* left-shift by p digits */ 194 void s_mp_rshd(mp_int *mp, mp_size p); /* right-shift by p digits */ 195 mp_err s_mp_mul_2d(mp_int *mp, mp_digit d); /* multiply by 2^d in place */ 196 void s_mp_div_2d(mp_int *mp, mp_digit d); /* divide by 2^d in place */ 197 void s_mp_mod_2d(mp_int *mp, mp_digit d); /* modulo 2^d in place */ 198 void s_mp_div_2(mp_int *mp); /* divide by 2 in place */ 199 mp_err s_mp_mul_2(mp_int *mp); /* multiply by 2 in place */ 200 mp_err s_mp_norm(mp_int *a, mp_int *b, mp_digit *pd); 201 /* normalize for division */ 202 mp_err s_mp_add_d(mp_int *mp, mp_digit d); /* unsigned digit addition */ 203 mp_err s_mp_sub_d(mp_int *mp, mp_digit d); /* unsigned digit subtract */ 204 mp_err s_mp_mul_d(mp_int *mp, mp_digit d); /* unsigned digit multiply */ 205 mp_err s_mp_div_d(mp_int *mp, mp_digit d, mp_digit *r); 206 /* unsigned digit divide */ 207 mp_err s_mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu); 208 /* Barrett reduction */ 209 mp_err s_mp_add(mp_int *a, const mp_int *b); /* magnitude addition */ 210 mp_err s_mp_add_3arg(const mp_int *a, const mp_int *b, mp_int *c); 211 mp_err s_mp_sub(mp_int *a, const mp_int *b); /* magnitude subtract */ 212 mp_err s_mp_sub_3arg(const mp_int *a, const mp_int *b, mp_int *c); 213 mp_err s_mp_add_offset(mp_int *a, mp_int *b, mp_size offset); 214 /* a += b * RADIX^offset */ 215 mp_err s_mp_mul(mp_int *a, const mp_int *b); /* magnitude multiply */ 216 #if MP_SQUARE 217 mp_err s_mp_sqr(mp_int *a); /* magnitude square */ 218 #else 219 #define s_mp_sqr(a) s_mp_mul(a, a) 220 #endif 221 mp_err s_mp_div(mp_int *rem, mp_int *div, mp_int *quot); /* magnitude div */ 222 mp_err s_mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); 223 mp_err s_mp_2expt(mp_int *a, mp_digit k); /* a = 2^k */ 224 int s_mp_cmp(const mp_int *a, const mp_int *b); /* magnitude comparison */ 225 int s_mp_cmp_d(const mp_int *a, mp_digit d); /* magnitude digit compare */ 226 int s_mp_ispow2(const mp_int *v); /* is v a power of 2? */ 227 int s_mp_ispow2d(mp_digit d); /* is d a power of 2? */ 228 229 int s_mp_tovalue(char ch, int r); /* convert ch to value */ 230 char s_mp_todigit(mp_digit val, int r, int low); /* convert val to digit */ 231 int s_mp_outlen(int bits, int r); /* output length in bytes */ 232 mp_digit s_mp_invmod_radix(mp_digit P); /* returns (P ** -1) mod RADIX */ 233 mp_err s_mp_invmod_odd_m( const mp_int *a, const mp_int *m, mp_int *c); 234 mp_err s_mp_invmod_2d( const mp_int *a, mp_size k, mp_int *c); 235 mp_err s_mp_invmod_even_m(const mp_int *a, const mp_int *m, mp_int *c); 236 237 #ifdef NSS_USE_COMBA 238 239 #define IS_POWER_OF_2(a) ((a) && !((a) & ((a)-1))) 240 241 void s_mp_mul_comba_4(const mp_int *A, const mp_int *B, mp_int *C); 242 void s_mp_mul_comba_8(const mp_int *A, const mp_int *B, mp_int *C); 243 void s_mp_mul_comba_16(const mp_int *A, const mp_int *B, mp_int *C); 244 void s_mp_mul_comba_32(const mp_int *A, const mp_int *B, mp_int *C); 245 246 void s_mp_sqr_comba_4(const mp_int *A, mp_int *B); 247 void s_mp_sqr_comba_8(const mp_int *A, mp_int *B); 248 void s_mp_sqr_comba_16(const mp_int *A, mp_int *B); 249 void s_mp_sqr_comba_32(const mp_int *A, mp_int *B); 250 251 #endif /* end NSS_USE_COMBA */ 252 253 /* ------ mpv functions, operate on arrays of digits, not on mp_int's ------ */ 254 #if defined (__OS2__) && defined (__IBMC__) 255 #define MPI_ASM_DECL __cdecl 256 #else 257 #define MPI_ASM_DECL 258 #endif 259 260 #ifdef MPI_AMD64 261 262 mp_digit MPI_ASM_DECL s_mpv_mul_set_vec64(mp_digit*, mp_digit *, mp_size, mp_digit); 263 mp_digit MPI_ASM_DECL s_mpv_mul_add_vec64(mp_digit*, const mp_digit*, mp_size, mp_digit); 264 265 /* c = a * b */ 266 #define s_mpv_mul_d(a, a_len, b, c) \ 267 ((unsigned long*)c)[a_len] = s_mpv_mul_set_vec64(c, a, a_len, b) 268 269 /* c += a * b */ 270 #define s_mpv_mul_d_add(a, a_len, b, c) \ 271 ((unsigned long*)c)[a_len] = s_mpv_mul_add_vec64(c, a, a_len, b) 272 273 #else 274 275 void MPI_ASM_DECL s_mpv_mul_d(const mp_digit *a, mp_size a_len, 276 mp_digit b, mp_digit *c); 277 void MPI_ASM_DECL s_mpv_mul_d_add(const mp_digit *a, mp_size a_len, 278 mp_digit b, mp_digit *c); 279 280 #endif 281 282 void MPI_ASM_DECL s_mpv_mul_d_add_prop(const mp_digit *a, 283 mp_size a_len, mp_digit b, 284 mp_digit *c); 285 void MPI_ASM_DECL s_mpv_sqr_add_prop(const mp_digit *a, 286 mp_size a_len, 287 mp_digit *sqrs); 288 289 mp_err MPI_ASM_DECL s_mpv_div_2dx1d(mp_digit Nhi, mp_digit Nlo, 290 mp_digit divisor, mp_digit *quot, mp_digit *rem); 291 292 /* c += a * b * (MP_RADIX ** offset); */ 293 #define s_mp_mul_d_add_offset(a, b, c, off) \ 294 (s_mpv_mul_d_add_prop(MP_DIGITS(a), MP_USED(a), b, MP_DIGITS(c) + off), MP_OKAY) 295 296 typedef struct { 297 mp_int N; /* modulus N */ 298 mp_digit n0prime; /* n0' = - (n0 ** -1) mod MP_RADIX */ 299 mp_size b; /* R == 2 ** b, also b = # significant bits in N */ 300 } mp_mont_modulus; 301 302 mp_err s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c, 303 mp_mont_modulus *mmm); 304 mp_err s_mp_redc(mp_int *T, mp_mont_modulus *mmm); 305 306 /* 307 * s_mpi_getProcessorLineSize() returns the size in bytes of the cache line 308 * if a cache exists, or zero if there is no cache. If more than one 309 * cache line exists, it should return the smallest line size (which is 310 * usually the L1 cache). 311 * 312 * mp_modexp uses this information to make sure that private key information 313 * isn't being leaked through the cache. 314 * 315 * see mpcpucache.c for the implementation. 316 */ 317 unsigned long s_mpi_getProcessorLineSize(); 318 319 /* }}} */ 320 #endif /* _MPI_PRIV_H */ 321