mpi-priv.h (9116B)
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 /* {{{ private function declarations */ 94 95 void s_mp_setz(mp_digit *dp, mp_size count); /* zero digits */ 96 void s_mp_copy(const mp_digit *sp, mp_digit *dp, mp_size count); /* copy */ 97 void *s_mp_alloc(size_t nb, size_t ni); /* general allocator */ 98 void s_mp_free(void *ptr); /* general free function */ 99 100 mp_err s_mp_grow(mp_int *mp, mp_size min); /* increase allocated size */ 101 mp_err s_mp_pad(mp_int *mp, mp_size min); /* left pad with zeroes */ 102 103 void s_mp_clamp(mp_int *mp); /* clip leading zeroes */ 104 105 void s_mp_exch(mp_int *a, mp_int *b); /* swap a and b in place */ 106 107 mp_err s_mp_lshd(mp_int *mp, mp_size p); /* left-shift by p digits */ 108 void s_mp_rshd(mp_int *mp, mp_size p); /* right-shift by p digits */ 109 mp_err s_mp_mul_2d(mp_int *mp, mp_digit d); /* multiply by 2^d in place */ 110 void s_mp_div_2d(mp_int *mp, mp_digit d); /* divide by 2^d in place */ 111 void s_mp_mod_2d(mp_int *mp, mp_digit d); /* modulo 2^d in place */ 112 void s_mp_div_2(mp_int *mp); /* divide by 2 in place */ 113 mp_err s_mp_mul_2(mp_int *mp); /* multiply by 2 in place */ 114 mp_err s_mp_norm(mp_int *a, mp_int *b, mp_digit *pd); 115 /* normalize for division */ 116 mp_err s_mp_add_d(mp_int *mp, mp_digit d); /* unsigned digit addition */ 117 mp_err s_mp_sub_d(mp_int *mp, mp_digit d); /* unsigned digit subtract */ 118 mp_err s_mp_mul_d(mp_int *mp, mp_digit d); /* unsigned digit multiply */ 119 mp_err s_mp_div_d(mp_int *mp, mp_digit d, mp_digit *r); 120 /* unsigned digit divide */ 121 mp_err s_mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu); 122 /* Barrett reduction */ 123 mp_err s_mp_add(mp_int *a, const mp_int *b); /* magnitude addition */ 124 mp_err s_mp_add_3arg(const mp_int *a, const mp_int *b, mp_int *c); 125 mp_err s_mp_sub(mp_int *a, const mp_int *b); /* magnitude subtract */ 126 mp_err s_mp_sub_3arg(const mp_int *a, const mp_int *b, mp_int *c); 127 mp_err s_mp_add_offset(mp_int *a, mp_int *b, mp_size offset); 128 /* a += b * RADIX^offset */ 129 mp_err s_mp_mul(mp_int *a, const mp_int *b); /* magnitude multiply */ 130 #if MP_SQUARE 131 mp_err s_mp_sqr(mp_int *a); /* magnitude square */ 132 #else 133 #define s_mp_sqr(a) s_mp_mul(a, a) 134 #endif 135 mp_err s_mp_div(mp_int *rem, mp_int *div, mp_int *quot); /* magnitude div */ 136 mp_err s_mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); 137 mp_err s_mp_2expt(mp_int *a, mp_digit k); /* a = 2^k */ 138 int s_mp_cmp(const mp_int *a, const mp_int *b); /* magnitude comparison */ 139 int s_mp_cmp_d(const mp_int *a, mp_digit d); /* magnitude digit compare */ 140 int s_mp_ispow2(const mp_int *v); /* is v a power of 2? */ 141 int s_mp_ispow2d(mp_digit d); /* is d a power of 2? */ 142 143 int s_mp_tovalue(char ch, int r); /* convert ch to value */ 144 char s_mp_todigit(mp_digit val, int r, int low); /* convert val to digit */ 145 int s_mp_outlen(int bits, int r); /* output length in bytes */ 146 mp_digit s_mp_invmod_radix(mp_digit P); /* returns (P ** -1) mod RADIX */ 147 mp_err s_mp_invmod_odd_m(const mp_int *a, const mp_int *m, mp_int *c); 148 mp_err s_mp_invmod_2d(const mp_int *a, mp_size k, mp_int *c); 149 mp_err s_mp_invmod_even_m(const mp_int *a, const mp_int *m, mp_int *c); 150 151 #ifdef NSS_USE_COMBA 152 PR_STATIC_ASSERT(sizeof(mp_digit) == 8); 153 #define IS_POWER_OF_2(a) ((a) && !((a) & ((a)-1))) 154 155 void s_mp_mul_comba_4(const mp_int *A, const mp_int *B, mp_int *C); 156 void s_mp_mul_comba_8(const mp_int *A, const mp_int *B, mp_int *C); 157 void s_mp_mul_comba_16(const mp_int *A, const mp_int *B, mp_int *C); 158 void s_mp_mul_comba_32(const mp_int *A, const mp_int *B, mp_int *C); 159 160 void s_mp_sqr_comba_4(const mp_int *A, mp_int *B); 161 void s_mp_sqr_comba_8(const mp_int *A, mp_int *B); 162 void s_mp_sqr_comba_16(const mp_int *A, mp_int *B); 163 void s_mp_sqr_comba_32(const mp_int *A, mp_int *B); 164 165 #endif /* end NSS_USE_COMBA */ 166 167 /* ------ mpv functions, operate on arrays of digits, not on mp_int's ------ */ 168 #if defined(__IBMC__) 169 #define MPI_ASM_DECL __cdecl 170 #else 171 #define MPI_ASM_DECL 172 #endif 173 174 #ifdef MPI_AMD64 175 176 mp_digit MPI_ASM_DECL s_mpv_mul_set_vec64(mp_digit *, mp_digit *, mp_size, mp_digit); 177 mp_digit MPI_ASM_DECL s_mpv_mul_add_vec64(mp_digit *, const mp_digit *, mp_size, mp_digit); 178 179 /* c = a * b */ 180 #define s_mpv_mul_d(a, a_len, b, c) \ 181 ((mp_digit *)c)[a_len] = s_mpv_mul_set_vec64(c, a, a_len, b) 182 183 /* c += a * b */ 184 #define s_mpv_mul_d_add(a, a_len, b, c) \ 185 ((mp_digit *)c)[a_len] = s_mpv_mul_add_vec64(c, a, a_len, b) 186 187 #else 188 189 void MPI_ASM_DECL s_mpv_mul_d(const mp_digit *a, mp_size a_len, 190 mp_digit b, mp_digit *c); 191 void MPI_ASM_DECL s_mpv_mul_d_add(const mp_digit *a, mp_size a_len, 192 mp_digit b, mp_digit *c); 193 194 #endif 195 196 void MPI_ASM_DECL s_mpv_mul_d_add_prop(const mp_digit *a, 197 mp_size a_len, mp_digit b, 198 mp_digit *c); 199 void MPI_ASM_DECL s_mpv_mul_d_add_propCT(const mp_digit *a, 200 mp_size a_len, mp_digit b, 201 mp_digit *c, mp_size c_len); 202 void MPI_ASM_DECL s_mpv_sqr_add_prop(const mp_digit *a, 203 mp_size a_len, 204 mp_digit *sqrs); 205 206 mp_err MPI_ASM_DECL s_mpv_div_2dx1d(mp_digit Nhi, mp_digit Nlo, 207 mp_digit divisor, mp_digit *quot, mp_digit *rem); 208 209 /* c += a * b * (MP_RADIX ** offset); */ 210 /* Callers of this macro should be aware that the return type might vary; 211 * it should be treated as a void function. */ 212 #define s_mp_mul_d_add_offset(a, b, c, off) \ 213 s_mpv_mul_d_add_prop(MP_DIGITS(a), MP_USED(a), b, MP_DIGITS(c) + off) 214 215 typedef struct { 216 mp_int N; /* modulus N */ 217 mp_digit n0prime; /* n0' = - (n0 ** -1) mod MP_RADIX */ 218 } mp_mont_modulus; 219 220 mp_err s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c, 221 mp_mont_modulus *mmm); 222 mp_err s_mp_redc(mp_int *T, mp_mont_modulus *mmm); 223 224 /* 225 * s_mpi_getProcessorLineSize() returns the size in bytes of the cache line 226 * if a cache exists, or zero if there is no cache. If more than one 227 * cache line exists, it should return the smallest line size (which is 228 * usually the L1 cache). 229 * 230 * mp_modexp uses this information to make sure that private key information 231 * isn't being leaked through the cache. 232 * 233 * see mpcpucache.c for the implementation. 234 */ 235 unsigned long s_mpi_getProcessorLineSize(); 236 237 /* }}} */ 238 #endif