f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * mpi-priv.h - Private header file for MPI
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Arbitrary precision integer arithmetic library
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * NOTE WELL: the content of this header file is NOT part of the "public"
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * API for the MPI library, and may change at any time.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Application programs that use libmpi should NOT include this header file.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * ***** BEGIN LICENSE BLOCK *****
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Version: MPL 1.1/GPL 2.0/LGPL 2.1
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The contents of this file are subject to the Mozilla Public License Version
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * 1.1 (the "License"); you may not use this file except in compliance with
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the License. You may obtain a copy of the License at
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Software distributed under the License is distributed on an "AS IS" basis,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * for the specific language governing rights and limitations under the
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The Initial Developer of the Original Code is
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Michael J. Fromberger.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Portions created by the Initial Developer are Copyright (C) 1998
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the Initial Developer. All Rights Reserved.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Contributor(s):
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Netscape Communications Corporation
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Alternatively, the contents of this file may be used under the terms of
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * either the GNU General Public License Version 2 or later (the "GPL"), or
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * in which case the provisions of the GPL or the LGPL are applicable instead
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * of those above. If you wish to allow use of your version of this file only
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * under the terms of either the GPL or the LGPL, and not to allow others to
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * use your version of this file under the terms of the MPL, indicate your
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * decision by deleting the provisions above and replace them with the notice
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * and other provisions required by the GPL or the LGPL. If you do not delete
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the provisions above, a recipient may use your version of this file under
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the terms of any one of the MPL, the GPL or the LGPL.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * ***** END LICENSE BLOCK ***** */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Use is subject to license terms.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Sun elects to use this software under the MPL license.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#pragma ident "%Z%%M% %I% %E% SMI"
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* $Id: mpi-priv.h,v 1.20 2005/11/22 07:16:43 relyea%netscape.com Exp $ */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#endif /* _KERNEL */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#define DIAG(T,V) {fprintf(stderr,T);mp_print(V,stderr);fputc('\n',stderr);}
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* If we aren't using a wired-in logarithm table, we need to include
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers the math library to get the log() function
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* {{{ s_logv_2[] - log table for 2 in various bases */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers A table of the logs of 2 for various bases (the 0 and 1 entries of
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers this table are meaningless and should not be referenced).
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers This table is used to compute output lengths for the mp_toradix()
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers function. Since a number n in radix r takes up about log_r(n)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers digits, we estimate the output size by taking the least integer
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers greater than log_r(n), where:
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers log_r(n) = log_2(n) * log_r(2)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers This table, therefore, is a table of log_r(2) for 2 <= r <= 36,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers which are the output bases supported.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersextern const float s_logv_2[];
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers If MP_LOGTAB is not defined, use the math library to compute the
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers logarithms on the fly. Otherwise, use the table.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers Pick which works best for your system.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#endif /* if MP_LOGTAB */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* {{{ Digit arithmetic macros */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers When adding and multiplying digits, the results can be larger than
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers can be contained in an mp_digit. Thus, an mp_word is used. These
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers macros mask off the upper and lower digits of the mp_word (the
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers mp_word may be more than 2 mp_digits wide, but we only concern
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers ourselves with the low-order 2 mp_digits)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* {{{ Comparison constants */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* {{{ private function declarations */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers If MP_MACRO is false, these will be defined as actual functions;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers otherwise, suitable macro definitions will be used. This works
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers around the fact that ANSI C89 doesn't support an 'inline' keyword
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers (although I hear C9x will ... about bloody time). At present, the
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers macro definitions are identical to the function bodies, but they'll
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers expand in place, instead of generating a function call.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers I chose these particular functions to be made into macros because
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers some profiling showed they are called a lot on a typical workload,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers and yet they are primarily housekeeping.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers void s_mp_setz(mp_digit *dp, mp_size count); /* zero digits */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers void s_mp_copy(const mp_digit *sp, mp_digit *dp, mp_size count); /* copy */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers void *s_mp_alloc(size_t nb, size_t ni, int flag); /* general allocator */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers void s_mp_free(void *ptr, mp_size); /* general free function */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersextern unsigned long mp_allocs;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersextern unsigned long mp_frees;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersextern unsigned long mp_copies;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* Even if these are defined as macros, we need to respect the settings
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers of the MP_MEMSET and MP_MEMCPY configuration options...
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers #define s_mp_setz(dp, count) memset(dp, 0, (count) * sizeof(mp_digit))
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers #endif /* MP_MEMSET */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=(sp)[ix];}
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers #define s_mp_copy(sp, dp, count) memcpy(dp, sp, (count) * sizeof(mp_digit))
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers #endif /* MP_MEMCPY */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#endif /* MP_MACRO */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_grow(mp_int *mp, mp_size min); /* increase allocated size */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_pad(mp_int *mp, mp_size min); /* left pad with zeroes */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers void s_mp_clamp(mp_int *mp); /* clip leading zeroes */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers while (used > 1 && DIGIT(mp, used - 1) == 0) --used; \
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#endif /* MP_MACRO */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid s_mp_exch(mp_int *a, mp_int *b); /* swap a and b in place */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_lshd(mp_int *mp, mp_size p); /* left-shift by p digits */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid s_mp_rshd(mp_int *mp, mp_size p); /* right-shift by p digits */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_mul_2d(mp_int *mp, mp_digit d); /* multiply by 2^d in place */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid s_mp_div_2d(mp_int *mp, mp_digit d); /* divide by 2^d in place */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid s_mp_mod_2d(mp_int *mp, mp_digit d); /* modulo 2^d in place */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid s_mp_div_2(mp_int *mp); /* divide by 2 in place */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_mul_2(mp_int *mp); /* multiply by 2 in place */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_norm(mp_int *a, mp_int *b, mp_digit *pd);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* normalize for division */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_add_d(mp_int *mp, mp_digit d); /* unsigned digit addition */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_sub_d(mp_int *mp, mp_digit d); /* unsigned digit subtract */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_mul_d(mp_int *mp, mp_digit d); /* unsigned digit multiply */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_div_d(mp_int *mp, mp_digit d, mp_digit *r);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* unsigned digit divide */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* Barrett reduction */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_add(mp_int *a, const mp_int *b); /* magnitude addition */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_add_3arg(const mp_int *a, const mp_int *b, mp_int *c);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_sub(mp_int *a, const mp_int *b); /* magnitude subtract */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_sub_3arg(const mp_int *a, const mp_int *b, mp_int *c);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_add_offset(mp_int *a, mp_int *b, mp_size offset);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* a += b * RADIX^offset */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_mul(mp_int *a, const mp_int *b); /* magnitude multiply */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_div(mp_int *rem, mp_int *div, mp_int *quot); /* magnitude div */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_2expt(mp_int *a, mp_digit k); /* a = 2^k */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersint s_mp_cmp(const mp_int *a, const mp_int *b); /* magnitude comparison */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersint s_mp_cmp_d(const mp_int *a, mp_digit d); /* magnitude digit compare */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersint s_mp_ispow2(const mp_int *v); /* is v a power of 2? */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersint s_mp_ispow2d(mp_digit d); /* is d a power of 2? */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersint s_mp_tovalue(char ch, int r); /* convert ch to value */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowerschar s_mp_todigit(mp_digit val, int r, int low); /* convert val to digit */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersint s_mp_outlen(int bits, int r); /* output length in bytes */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_digit s_mp_invmod_radix(mp_digit P); /* returns (P ** -1) mod RADIX */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_invmod_odd_m( const mp_int *a, const mp_int *m, mp_int *c);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_invmod_2d( const mp_int *a, mp_size k, mp_int *c);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_invmod_even_m(const mp_int *a, const mp_int *m, mp_int *c);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid s_mp_mul_comba_4(const mp_int *A, const mp_int *B, mp_int *C);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid s_mp_mul_comba_8(const mp_int *A, const mp_int *B, mp_int *C);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid s_mp_mul_comba_16(const mp_int *A, const mp_int *B, mp_int *C);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid s_mp_mul_comba_32(const mp_int *A, const mp_int *B, mp_int *C);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#endif /* end NSS_USE_COMBA */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* ------ mpv functions, operate on arrays of digits, not on mp_int's ------ */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_digit MPI_ASM_DECL s_mpv_mul_set_vec64(mp_digit*, mp_digit *, mp_size, mp_digit);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_digit MPI_ASM_DECL s_mpv_mul_add_vec64(mp_digit*, const mp_digit*, mp_size, mp_digit);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* c = a * b */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers ((unsigned long*)c)[a_len] = s_mpv_mul_set_vec64(c, a, a_len, b)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* c += a * b */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers ((unsigned long*)c)[a_len] = s_mpv_mul_add_vec64(c, a, a_len, b)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid MPI_ASM_DECL s_mpv_mul_d(const mp_digit *a, mp_size a_len,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid MPI_ASM_DECL s_mpv_mul_d_add(const mp_digit *a, mp_size a_len,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid MPI_ASM_DECL s_mpv_mul_d_add_prop(const mp_digit *a,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid MPI_ASM_DECL s_mpv_sqr_add_prop(const mp_digit *a,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err MPI_ASM_DECL s_mpv_div_2dx1d(mp_digit Nhi, mp_digit Nlo,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* c += a * b * (MP_RADIX ** offset); */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers(s_mpv_mul_d_add_prop(MP_DIGITS(a), MP_USED(a), b, MP_DIGITS(c) + off), MP_OKAY)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowerstypedef struct {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers mp_digit n0prime; /* n0' = - (n0 ** -1) mod MP_RADIX */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers mp_size b; /* R == 2 ** b, also b = # significant bits in N */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * s_mpi_getProcessorLineSize() returns the size in bytes of the cache line
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * if a cache exists, or zero if there is no cache. If more than one
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * cache line exists, it should return the smallest line size (which is
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * usually the L1 cache).
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * mp_modexp uses this information to make sure that private key information
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * isn't being leaked through the cache.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * see mpcpucache.c for the implementation.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#endif /* _MPI_PRIV_H */