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