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