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) \ 24 { \ 25 fprintf(stderr, T); \ 26 mp_print(V, stderr); \ 27 fputc('\n', stderr); \ 28 } 29 #else 30 #define DIAG(T, V) 31 #endif 32 33 /* If we aren't using a wired-in logarithm table, we need to include 34 the math library to get the log() function 35 */ 36 37 /* {{{ s_logv_2[] - log table for 2 in various bases */ 38 39 #if MP_LOGTAB 40 /* 41 A table of the logs of 2 for various bases (the 0 and 1 entries of 42 this table are meaningless and should not be referenced). 43 44 This table is used to compute output lengths for the mp_toradix() 45 function. Since a number n in radix r takes up about log_r(n) 46 digits, we estimate the output size by taking the least integer 47 greater than log_r(n), where: 48 49 log_r(n) = log_2(n) * log_r(2) 50 51 This table, therefore, is a table of log_r(2) for 2 <= r <= 36, 52 which are the output bases supported. 53 */ 54 55 extern const float s_logv_2[]; 56 #define LOG_V_2(R) s_logv_2[(R)] 57 58 #else 59 60 /* 61 If MP_LOGTAB is not defined, use the math library to compute the 62 logarithms on the fly. Otherwise, use the table. 63 Pick which works best for your system. 64 */ 65 66 #include <math.h> 67 #define LOG_V_2(R) (log(2.0) / log(R)) 68 69 #endif /* if MP_LOGTAB */ 70 71 /* }}} */ 72 73 /* {{{ Digit arithmetic macros */ 74 75 /* 76 When adding and multiplying digits, the results can be larger than 77 can be contained in an mp_digit. Thus, an mp_word is used. These 78 macros mask off the upper and lower digits of the mp_word (the 79 mp_word may be more than 2 mp_digits wide, but we only concern 80 ourselves with the low-order 2 mp_digits) 81 */ 82 83 #define CARRYOUT(W) (mp_digit)((W) >> DIGIT_BIT) 84 #define ACCUM(W) (mp_digit)(W) 85 86 #define MP_MIN(a, b) (((a) < (b)) ? (a) : (b)) 87 #define MP_MAX(a, b) (((a) > (b)) ? (a) : (b)) 88 #define MP_HOWMANY(a, b) (((a) + (b)-1) / (b)) 89 #define MP_ROUNDUP(a, b) (MP_HOWMANY(a, b) * (b)) 90 91 /* }}} */ 92 93 /* {{{ Comparison constants */ 94 95 #define MP_LT -1 96 #define MP_EQ 0 97 #define MP_GT 1 98 99 /* }}} */ 100 101 /* {{{ private function declarations */ 102 103 void s_mp_setz(mp_digit *dp, mp_size count); /* zero digits */ 104 void s_mp_copy(const mp_digit *sp, mp_digit *dp, mp_size count); /* copy */ 105 void *s_mp_alloc(size_t nb, size_t ni); /* general allocator */ 106 void s_mp_free(void *ptr); /* general free function */ 107 108 mp_err s_mp_grow(mp_int *mp, mp_size min); /* increase allocated size */ 109 mp_err s_mp_pad(mp_int *mp, mp_size min); /* left pad with zeroes */ 110 111 void s_mp_clamp(mp_int *mp); /* clip leading zeroes */ 112 113 void s_mp_exch(mp_int *a, mp_int *b); /* swap a and b in place */ 114 115 mp_err s_mp_lshd(mp_int *mp, mp_size p); /* left-shift by p digits */ 116 void s_mp_rshd(mp_int *mp, mp_size p); /* right-shift by p digits */ 117 mp_err s_mp_mul_2d(mp_int *mp, mp_digit d); /* multiply by 2^d in place */ 118 void s_mp_div_2d(mp_int *mp, mp_digit d); /* divide by 2^d in place */ 119 void s_mp_mod_2d(mp_int *mp, mp_digit d); /* modulo 2^d in place */ 120 void s_mp_div_2(mp_int *mp); /* divide by 2 in place */ 121 mp_err s_mp_mul_2(mp_int *mp); /* multiply by 2 in place */ 122 mp_err s_mp_norm(mp_int *a, mp_int *b, mp_digit *pd); 123 /* normalize for division */ 124 mp_err s_mp_add_d(mp_int *mp, mp_digit d); /* unsigned digit addition */ 125 mp_err s_mp_sub_d(mp_int *mp, mp_digit d); /* unsigned digit subtract */ 126 mp_err s_mp_mul_d(mp_int *mp, mp_digit d); /* unsigned digit multiply */ 127 mp_err s_mp_div_d(mp_int *mp, mp_digit d, mp_digit *r); 128 /* unsigned digit divide */ 129 mp_err s_mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu); 130 /* Barrett reduction */ 131 mp_err s_mp_add(mp_int *a, const mp_int *b); /* magnitude addition */ 132 mp_err s_mp_add_3arg(const mp_int *a, const mp_int *b, mp_int *c); 133 mp_err s_mp_sub(mp_int *a, const mp_int *b); /* magnitude subtract */ 134 mp_err s_mp_sub_3arg(const mp_int *a, const mp_int *b, mp_int *c); 135 mp_err s_mp_add_offset(mp_int *a, mp_int *b, mp_size offset); 136 /* a += b * RADIX^offset */ 137 mp_err s_mp_mul(mp_int *a, const mp_int *b); /* magnitude multiply */ 138 #if MP_SQUARE 139 mp_err s_mp_sqr(mp_int *a); /* magnitude square */ 140 #else 141 #define s_mp_sqr(a) s_mp_mul(a, a) 142 #endif 143 mp_err s_mp_div(mp_int *rem, mp_int *div, mp_int *quot); /* magnitude div */ 144 mp_err s_mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); 145 mp_err s_mp_2expt(mp_int *a, mp_digit k); /* a = 2^k */ 146 int s_mp_cmp(const mp_int *a, const mp_int *b); /* magnitude comparison */ 147 int s_mp_cmp_d(const mp_int *a, mp_digit d); /* magnitude digit compare */ 148 int s_mp_ispow2(const mp_int *v); /* is v a power of 2? */ 149 int s_mp_ispow2d(mp_digit d); /* is d a power of 2? */ 150 151 int s_mp_tovalue(char ch, int r); /* convert ch to value */ 152 char s_mp_todigit(mp_digit val, int r, int low); /* convert val to digit */ 153 int s_mp_outlen(int bits, int r); /* output length in bytes */ 154 mp_digit s_mp_invmod_radix(mp_digit P); /* returns (P ** -1) mod RADIX */ 155 mp_err s_mp_invmod_odd_m(const mp_int *a, const mp_int *m, mp_int *c); 156 mp_err s_mp_invmod_2d(const mp_int *a, mp_size k, mp_int *c); 157 mp_err s_mp_invmod_even_m(const mp_int *a, const mp_int *m, mp_int *c); 158 159 #ifdef NSS_USE_COMBA 160 PR_STATIC_ASSERT(sizeof(mp_digit) == 8); 161 #define IS_POWER_OF_2(a) ((a) && !((a) & ((a)-1))) 162 163 void s_mp_mul_comba_4(const mp_int *A, const mp_int *B, mp_int *C); 164 void s_mp_mul_comba_8(const mp_int *A, const mp_int *B, mp_int *C); 165 void s_mp_mul_comba_16(const mp_int *A, const mp_int *B, mp_int *C); 166 void s_mp_mul_comba_32(const mp_int *A, const mp_int *B, mp_int *C); 167 168 void s_mp_sqr_comba_4(const mp_int *A, mp_int *B); 169 void s_mp_sqr_comba_8(const mp_int *A, mp_int *B); 170 void s_mp_sqr_comba_16(const mp_int *A, mp_int *B); 171 void s_mp_sqr_comba_32(const mp_int *A, mp_int *B); 172 173 #endif /* end NSS_USE_COMBA */ 174 175 /* ------ mpv functions, operate on arrays of digits, not on mp_int's ------ */ 176 #if defined(__OS2__) && defined(__IBMC__) 177 #define MPI_ASM_DECL __cdecl 178 #else 179 #define MPI_ASM_DECL 180 #endif 181 182 #ifdef MPI_AMD64 183 184 mp_digit MPI_ASM_DECL s_mpv_mul_set_vec64(mp_digit *, mp_digit *, mp_size, mp_digit); 185 mp_digit MPI_ASM_DECL s_mpv_mul_add_vec64(mp_digit *, const mp_digit *, mp_size, mp_digit); 186 187 /* c = a * b */ 188 #define s_mpv_mul_d(a, a_len, b, c) \ 189 ((mp_digit *)c)[a_len] = s_mpv_mul_set_vec64(c, a, a_len, b) 190 191 /* c += a * b */ 192 #define s_mpv_mul_d_add(a, a_len, b, c) \ 193 ((mp_digit *)c)[a_len] = s_mpv_mul_add_vec64(c, a, a_len, b) 194 195 #else 196 197 void MPI_ASM_DECL s_mpv_mul_d(const mp_digit *a, mp_size a_len, 198 mp_digit b, mp_digit *c); 199 void MPI_ASM_DECL s_mpv_mul_d_add(const mp_digit *a, mp_size a_len, 200 mp_digit b, mp_digit *c); 201 202 #endif 203 204 void MPI_ASM_DECL s_mpv_mul_d_add_prop(const mp_digit *a, 205 mp_size a_len, mp_digit b, 206 mp_digit *c); 207 void MPI_ASM_DECL s_mpv_sqr_add_prop(const mp_digit *a, 208 mp_size a_len, 209 mp_digit *sqrs); 210 211 mp_err MPI_ASM_DECL s_mpv_div_2dx1d(mp_digit Nhi, mp_digit Nlo, 212 mp_digit divisor, mp_digit *quot, mp_digit *rem); 213 214 /* c += a * b * (MP_RADIX ** offset); */ 215 /* Callers of this macro should be aware that the return type might vary; 216 * it should be treated as a void function. */ 217 #define s_mp_mul_d_add_offset(a, b, c, off) \ 218 s_mpv_mul_d_add_prop(MP_DIGITS(a), MP_USED(a), b, MP_DIGITS(c) + off) 219 220 typedef struct { 221 mp_int N; /* modulus N */ 222 mp_digit n0prime; /* n0' = - (n0 ** -1) mod MP_RADIX */ 223 } mp_mont_modulus; 224 225 mp_err s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c, 226 mp_mont_modulus *mmm); 227 mp_err s_mp_redc(mp_int *T, mp_mont_modulus *mmm); 228 229 /* 230 * s_mpi_getProcessorLineSize() returns the size in bytes of the cache line 231 * if a cache exists, or zero if there is no cache. If more than one 232 * cache line exists, it should return the smallest line size (which is 233 * usually the L1 cache). 234 * 235 * mp_modexp uses this information to make sure that private key information 236 * isn't being leaked through the cache. 237 * 238 * see mpcpucache.c for the implementation. 239 */ 240 unsigned long s_mpi_getProcessorLineSize(); 241 242 /* }}} */ 243 #endif 244