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