annotate src/share/native/sun/security/ec/impl/mpi-priv.h @ 4272:b49a0af85821

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