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