1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/mpi-priv.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,284 @@
1.4 +/*
1.5 + * mpi-priv.h - Private header file for MPI
1.6 + * Arbitrary precision integer arithmetic library
1.7 + *
1.8 + * NOTE WELL: the content of this header file is NOT part of the "public"
1.9 + * API for the MPI library, and may change at any time.
1.10 + * Application programs that use libmpi should NOT include this header file.
1.11 + *
1.12 + * This Source Code Form is subject to the terms of the Mozilla Public
1.13 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.14 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.15 +#ifndef _MPI_PRIV_H_
1.16 +#define _MPI_PRIV_H_ 1
1.17 +
1.18 +#include "mpi.h"
1.19 +#include <stdlib.h>
1.20 +#include <string.h>
1.21 +#include <ctype.h>
1.22 +
1.23 +#if MP_DEBUG
1.24 +#include <stdio.h>
1.25 +
1.26 +#define DIAG(T,V) {fprintf(stderr,T);mp_print(V,stderr);fputc('\n',stderr);}
1.27 +#else
1.28 +#define DIAG(T,V)
1.29 +#endif
1.30 +
1.31 +/* If we aren't using a wired-in logarithm table, we need to include
1.32 + the math library to get the log() function
1.33 + */
1.34 +
1.35 +/* {{{ s_logv_2[] - log table for 2 in various bases */
1.36 +
1.37 +#if MP_LOGTAB
1.38 +/*
1.39 + A table of the logs of 2 for various bases (the 0 and 1 entries of
1.40 + this table are meaningless and should not be referenced).
1.41 +
1.42 + This table is used to compute output lengths for the mp_toradix()
1.43 + function. Since a number n in radix r takes up about log_r(n)
1.44 + digits, we estimate the output size by taking the least integer
1.45 + greater than log_r(n), where:
1.46 +
1.47 + log_r(n) = log_2(n) * log_r(2)
1.48 +
1.49 + This table, therefore, is a table of log_r(2) for 2 <= r <= 36,
1.50 + which are the output bases supported.
1.51 + */
1.52 +
1.53 +extern const float s_logv_2[];
1.54 +#define LOG_V_2(R) s_logv_2[(R)]
1.55 +
1.56 +#else
1.57 +
1.58 +/*
1.59 + If MP_LOGTAB is not defined, use the math library to compute the
1.60 + logarithms on the fly. Otherwise, use the table.
1.61 + Pick which works best for your system.
1.62 + */
1.63 +
1.64 +#include <math.h>
1.65 +#define LOG_V_2(R) (log(2.0)/log(R))
1.66 +
1.67 +#endif /* if MP_LOGTAB */
1.68 +
1.69 +/* }}} */
1.70 +
1.71 +/* {{{ Digit arithmetic macros */
1.72 +
1.73 +/*
1.74 + When adding and multiplying digits, the results can be larger than
1.75 + can be contained in an mp_digit. Thus, an mp_word is used. These
1.76 + macros mask off the upper and lower digits of the mp_word (the
1.77 + mp_word may be more than 2 mp_digits wide, but we only concern
1.78 + ourselves with the low-order 2 mp_digits)
1.79 + */
1.80 +
1.81 +#define CARRYOUT(W) (mp_digit)((W)>>DIGIT_BIT)
1.82 +#define ACCUM(W) (mp_digit)(W)
1.83 +
1.84 +#define MP_MIN(a,b) (((a) < (b)) ? (a) : (b))
1.85 +#define MP_MAX(a,b) (((a) > (b)) ? (a) : (b))
1.86 +#define MP_HOWMANY(a,b) (((a) + (b) - 1)/(b))
1.87 +#define MP_ROUNDUP(a,b) (MP_HOWMANY(a,b) * (b))
1.88 +
1.89 +/* }}} */
1.90 +
1.91 +/* {{{ Comparison constants */
1.92 +
1.93 +#define MP_LT -1
1.94 +#define MP_EQ 0
1.95 +#define MP_GT 1
1.96 +
1.97 +/* }}} */
1.98 +
1.99 +/* {{{ private function declarations */
1.100 +
1.101 +/*
1.102 + If MP_MACRO is false, these will be defined as actual functions;
1.103 + otherwise, suitable macro definitions will be used. This works
1.104 + around the fact that ANSI C89 doesn't support an 'inline' keyword
1.105 + (although I hear C9x will ... about bloody time). At present, the
1.106 + macro definitions are identical to the function bodies, but they'll
1.107 + expand in place, instead of generating a function call.
1.108 +
1.109 + I chose these particular functions to be made into macros because
1.110 + some profiling showed they are called a lot on a typical workload,
1.111 + and yet they are primarily housekeeping.
1.112 + */
1.113 +#if MP_MACRO == 0
1.114 + void s_mp_setz(mp_digit *dp, mp_size count); /* zero digits */
1.115 + void s_mp_copy(const mp_digit *sp, mp_digit *dp, mp_size count); /* copy */
1.116 + void *s_mp_alloc(size_t nb, size_t ni); /* general allocator */
1.117 + void s_mp_free(void *ptr); /* general free function */
1.118 +extern unsigned long mp_allocs;
1.119 +extern unsigned long mp_frees;
1.120 +extern unsigned long mp_copies;
1.121 +#else
1.122 +
1.123 + /* Even if these are defined as macros, we need to respect the settings
1.124 + of the MP_MEMSET and MP_MEMCPY configuration options...
1.125 + */
1.126 + #if MP_MEMSET == 0
1.127 + #define s_mp_setz(dp, count) \
1.128 + {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=0;}
1.129 + #else
1.130 + #define s_mp_setz(dp, count) memset(dp, 0, (count) * sizeof(mp_digit))
1.131 + #endif /* MP_MEMSET */
1.132 +
1.133 + #if MP_MEMCPY == 0
1.134 + #define s_mp_copy(sp, dp, count) \
1.135 + {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=(sp)[ix];}
1.136 + #else
1.137 + #define s_mp_copy(sp, dp, count) memcpy(dp, sp, (count) * sizeof(mp_digit))
1.138 + #endif /* MP_MEMCPY */
1.139 +
1.140 + #define s_mp_alloc(nb, ni) calloc(nb, ni)
1.141 + #define s_mp_free(ptr) {if(ptr) free(ptr);}
1.142 +#endif /* MP_MACRO */
1.143 +
1.144 +mp_err s_mp_grow(mp_int *mp, mp_size min); /* increase allocated size */
1.145 +mp_err s_mp_pad(mp_int *mp, mp_size min); /* left pad with zeroes */
1.146 +
1.147 +#if MP_MACRO == 0
1.148 + void s_mp_clamp(mp_int *mp); /* clip leading zeroes */
1.149 +#else
1.150 + #define s_mp_clamp(mp)\
1.151 + { mp_size used = MP_USED(mp); \
1.152 + while (used > 1 && DIGIT(mp, used - 1) == 0) --used; \
1.153 + MP_USED(mp) = used; \
1.154 + }
1.155 +#endif /* MP_MACRO */
1.156 +
1.157 +void s_mp_exch(mp_int *a, mp_int *b); /* swap a and b in place */
1.158 +
1.159 +mp_err s_mp_lshd(mp_int *mp, mp_size p); /* left-shift by p digits */
1.160 +void s_mp_rshd(mp_int *mp, mp_size p); /* right-shift by p digits */
1.161 +mp_err s_mp_mul_2d(mp_int *mp, mp_digit d); /* multiply by 2^d in place */
1.162 +void s_mp_div_2d(mp_int *mp, mp_digit d); /* divide by 2^d in place */
1.163 +void s_mp_mod_2d(mp_int *mp, mp_digit d); /* modulo 2^d in place */
1.164 +void s_mp_div_2(mp_int *mp); /* divide by 2 in place */
1.165 +mp_err s_mp_mul_2(mp_int *mp); /* multiply by 2 in place */
1.166 +mp_err s_mp_norm(mp_int *a, mp_int *b, mp_digit *pd);
1.167 + /* normalize for division */
1.168 +mp_err s_mp_add_d(mp_int *mp, mp_digit d); /* unsigned digit addition */
1.169 +mp_err s_mp_sub_d(mp_int *mp, mp_digit d); /* unsigned digit subtract */
1.170 +mp_err s_mp_mul_d(mp_int *mp, mp_digit d); /* unsigned digit multiply */
1.171 +mp_err s_mp_div_d(mp_int *mp, mp_digit d, mp_digit *r);
1.172 + /* unsigned digit divide */
1.173 +mp_err s_mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu);
1.174 + /* Barrett reduction */
1.175 +mp_err s_mp_add(mp_int *a, const mp_int *b); /* magnitude addition */
1.176 +mp_err s_mp_add_3arg(const mp_int *a, const mp_int *b, mp_int *c);
1.177 +mp_err s_mp_sub(mp_int *a, const mp_int *b); /* magnitude subtract */
1.178 +mp_err s_mp_sub_3arg(const mp_int *a, const mp_int *b, mp_int *c);
1.179 +mp_err s_mp_add_offset(mp_int *a, mp_int *b, mp_size offset);
1.180 + /* a += b * RADIX^offset */
1.181 +mp_err s_mp_mul(mp_int *a, const mp_int *b); /* magnitude multiply */
1.182 +#if MP_SQUARE
1.183 +mp_err s_mp_sqr(mp_int *a); /* magnitude square */
1.184 +#else
1.185 +#define s_mp_sqr(a) s_mp_mul(a, a)
1.186 +#endif
1.187 +mp_err s_mp_div(mp_int *rem, mp_int *div, mp_int *quot); /* magnitude div */
1.188 +mp_err s_mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
1.189 +mp_err s_mp_2expt(mp_int *a, mp_digit k); /* a = 2^k */
1.190 +int s_mp_cmp(const mp_int *a, const mp_int *b); /* magnitude comparison */
1.191 +int s_mp_cmp_d(const mp_int *a, mp_digit d); /* magnitude digit compare */
1.192 +int s_mp_ispow2(const mp_int *v); /* is v a power of 2? */
1.193 +int s_mp_ispow2d(mp_digit d); /* is d a power of 2? */
1.194 +
1.195 +int s_mp_tovalue(char ch, int r); /* convert ch to value */
1.196 +char s_mp_todigit(mp_digit val, int r, int low); /* convert val to digit */
1.197 +int s_mp_outlen(int bits, int r); /* output length in bytes */
1.198 +mp_digit s_mp_invmod_radix(mp_digit P); /* returns (P ** -1) mod RADIX */
1.199 +mp_err s_mp_invmod_odd_m( const mp_int *a, const mp_int *m, mp_int *c);
1.200 +mp_err s_mp_invmod_2d( const mp_int *a, mp_size k, mp_int *c);
1.201 +mp_err s_mp_invmod_even_m(const mp_int *a, const mp_int *m, mp_int *c);
1.202 +
1.203 +#ifdef NSS_USE_COMBA
1.204 +
1.205 +#define IS_POWER_OF_2(a) ((a) && !((a) & ((a)-1)))
1.206 +
1.207 +void s_mp_mul_comba_4(const mp_int *A, const mp_int *B, mp_int *C);
1.208 +void s_mp_mul_comba_8(const mp_int *A, const mp_int *B, mp_int *C);
1.209 +void s_mp_mul_comba_16(const mp_int *A, const mp_int *B, mp_int *C);
1.210 +void s_mp_mul_comba_32(const mp_int *A, const mp_int *B, mp_int *C);
1.211 +
1.212 +void s_mp_sqr_comba_4(const mp_int *A, mp_int *B);
1.213 +void s_mp_sqr_comba_8(const mp_int *A, mp_int *B);
1.214 +void s_mp_sqr_comba_16(const mp_int *A, mp_int *B);
1.215 +void s_mp_sqr_comba_32(const mp_int *A, mp_int *B);
1.216 +
1.217 +#endif /* end NSS_USE_COMBA */
1.218 +
1.219 +/* ------ mpv functions, operate on arrays of digits, not on mp_int's ------ */
1.220 +#if defined (__OS2__) && defined (__IBMC__)
1.221 +#define MPI_ASM_DECL __cdecl
1.222 +#else
1.223 +#define MPI_ASM_DECL
1.224 +#endif
1.225 +
1.226 +#ifdef MPI_AMD64
1.227 +
1.228 +mp_digit MPI_ASM_DECL s_mpv_mul_set_vec64(mp_digit*, mp_digit *, mp_size, mp_digit);
1.229 +mp_digit MPI_ASM_DECL s_mpv_mul_add_vec64(mp_digit*, const mp_digit*, mp_size, mp_digit);
1.230 +
1.231 +/* c = a * b */
1.232 +#define s_mpv_mul_d(a, a_len, b, c) \
1.233 + ((mp_digit *)c)[a_len] = s_mpv_mul_set_vec64(c, a, a_len, b)
1.234 +
1.235 +/* c += a * b */
1.236 +#define s_mpv_mul_d_add(a, a_len, b, c) \
1.237 + ((mp_digit *)c)[a_len] = s_mpv_mul_add_vec64(c, a, a_len, b)
1.238 +
1.239 +
1.240 +#else
1.241 +
1.242 +void MPI_ASM_DECL s_mpv_mul_d(const mp_digit *a, mp_size a_len,
1.243 + mp_digit b, mp_digit *c);
1.244 +void MPI_ASM_DECL s_mpv_mul_d_add(const mp_digit *a, mp_size a_len,
1.245 + mp_digit b, mp_digit *c);
1.246 +
1.247 +#endif
1.248 +
1.249 +void MPI_ASM_DECL s_mpv_mul_d_add_prop(const mp_digit *a,
1.250 + mp_size a_len, mp_digit b,
1.251 + mp_digit *c);
1.252 +void MPI_ASM_DECL s_mpv_sqr_add_prop(const mp_digit *a,
1.253 + mp_size a_len,
1.254 + mp_digit *sqrs);
1.255 +
1.256 +mp_err MPI_ASM_DECL s_mpv_div_2dx1d(mp_digit Nhi, mp_digit Nlo,
1.257 + mp_digit divisor, mp_digit *quot, mp_digit *rem);
1.258 +
1.259 +/* c += a * b * (MP_RADIX ** offset); */
1.260 +#define s_mp_mul_d_add_offset(a, b, c, off) \
1.261 +(s_mpv_mul_d_add_prop(MP_DIGITS(a), MP_USED(a), b, MP_DIGITS(c) + off), MP_OKAY)
1.262 +
1.263 +typedef struct {
1.264 + mp_int N; /* modulus N */
1.265 + mp_digit n0prime; /* n0' = - (n0 ** -1) mod MP_RADIX */
1.266 +} mp_mont_modulus;
1.267 +
1.268 +mp_err s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c,
1.269 + mp_mont_modulus *mmm);
1.270 +mp_err s_mp_redc(mp_int *T, mp_mont_modulus *mmm);
1.271 +
1.272 +/*
1.273 + * s_mpi_getProcessorLineSize() returns the size in bytes of the cache line
1.274 + * if a cache exists, or zero if there is no cache. If more than one
1.275 + * cache line exists, it should return the smallest line size (which is
1.276 + * usually the L1 cache).
1.277 + *
1.278 + * mp_modexp uses this information to make sure that private key information
1.279 + * isn't being leaked through the cache.
1.280 + *
1.281 + * see mpcpucache.c for the implementation.
1.282 + */
1.283 +unsigned long s_mpi_getProcessorLineSize();
1.284 +
1.285 +/* }}} */
1.286 +#endif
1.287 +
