|
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 2007 Sun Microsystems, Inc. All rights reserved. |
|
60 * Use is subject to license terms. |
|
61 */ |
|
62 |
|
63 #ifndef _MPI_PRIV_H |
|
64 #define _MPI_PRIV_H |
|
65 |
|
66 #pragma ident "%Z%%M% %I% %E% SMI" |
|
67 |
|
68 /* $Id: mpi-priv.h,v 1.20 2005/11/22 07:16:43 relyea%netscape.com Exp $ */ |
|
69 |
|
70 #include "mpi.h" |
|
71 #ifndef _KERNEL |
|
72 #include <stdlib.h> |
|
73 #include <string.h> |
|
74 #include <ctype.h> |
|
75 #endif /* _KERNEL */ |
|
76 |
|
77 #if MP_DEBUG |
|
78 #include <stdio.h> |
|
79 |
|
80 #define DIAG(T,V) {fprintf(stderr,T);mp_print(V,stderr);fputc('\n',stderr);} |
|
81 #else |
|
82 #define DIAG(T,V) |
|
83 #endif |
|
84 |
|
85 /* If we aren't using a wired-in logarithm table, we need to include |
|
86 the math library to get the log() function |
|
87 */ |
|
88 |
|
89 /* {{{ s_logv_2[] - log table for 2 in various bases */ |
|
90 |
|
91 #if MP_LOGTAB |
|
92 /* |
|
93 A table of the logs of 2 for various bases (the 0 and 1 entries of |
|
94 this table are meaningless and should not be referenced). |
|
95 |
|
96 This table is used to compute output lengths for the mp_toradix() |
|
97 function. Since a number n in radix r takes up about log_r(n) |
|
98 digits, we estimate the output size by taking the least integer |
|
99 greater than log_r(n), where: |
|
100 |
|
101 log_r(n) = log_2(n) * log_r(2) |
|
102 |
|
103 This table, therefore, is a table of log_r(2) for 2 <= r <= 36, |
|
104 which are the output bases supported. |
|
105 */ |
|
106 |
|
107 extern const float s_logv_2[]; |
|
108 #define LOG_V_2(R) s_logv_2[(R)] |
|
109 |
|
110 #else |
|
111 |
|
112 /* |
|
113 If MP_LOGTAB is not defined, use the math library to compute the |
|
114 logarithms on the fly. Otherwise, use the table. |
|
115 Pick which works best for your system. |
|
116 */ |
|
117 |
|
118 #include <math.h> |
|
119 #define LOG_V_2(R) (log(2.0)/log(R)) |
|
120 |
|
121 #endif /* if MP_LOGTAB */ |
|
122 |
|
123 /* }}} */ |
|
124 |
|
125 /* {{{ Digit arithmetic macros */ |
|
126 |
|
127 /* |
|
128 When adding and multiplying digits, the results can be larger than |
|
129 can be contained in an mp_digit. Thus, an mp_word is used. These |
|
130 macros mask off the upper and lower digits of the mp_word (the |
|
131 mp_word may be more than 2 mp_digits wide, but we only concern |
|
132 ourselves with the low-order 2 mp_digits) |
|
133 */ |
|
134 |
|
135 #define CARRYOUT(W) (mp_digit)((W)>>DIGIT_BIT) |
|
136 #define ACCUM(W) (mp_digit)(W) |
|
137 |
|
138 #define MP_MIN(a,b) (((a) < (b)) ? (a) : (b)) |
|
139 #define MP_MAX(a,b) (((a) > (b)) ? (a) : (b)) |
|
140 #define MP_HOWMANY(a,b) (((a) + (b) - 1)/(b)) |
|
141 #define MP_ROUNDUP(a,b) (MP_HOWMANY(a,b) * (b)) |
|
142 |
|
143 /* }}} */ |
|
144 |
|
145 /* {{{ Comparison constants */ |
|
146 |
|
147 #define MP_LT -1 |
|
148 #define MP_EQ 0 |
|
149 #define MP_GT 1 |
|
150 |
|
151 /* }}} */ |
|
152 |
|
153 /* {{{ private function declarations */ |
|
154 |
|
155 /* |
|
156 If MP_MACRO is false, these will be defined as actual functions; |
|
157 otherwise, suitable macro definitions will be used. This works |
|
158 around the fact that ANSI C89 doesn't support an 'inline' keyword |
|
159 (although I hear C9x will ... about bloody time). At present, the |
|
160 macro definitions are identical to the function bodies, but they'll |
|
161 expand in place, instead of generating a function call. |
|
162 |
|
163 I chose these particular functions to be made into macros because |
|
164 some profiling showed they are called a lot on a typical workload, |
|
165 and yet they are primarily housekeeping. |
|
166 */ |
|
167 #if MP_MACRO == 0 |
|
168 void s_mp_setz(mp_digit *dp, mp_size count); /* zero digits */ |
|
169 void s_mp_copy(const mp_digit *sp, mp_digit *dp, mp_size count); /* copy */ |
|
170 void *s_mp_alloc(size_t nb, size_t ni, int flag); /* general allocator */ |
|
171 void s_mp_free(void *ptr, mp_size); /* general free function */ |
|
172 extern unsigned long mp_allocs; |
|
173 extern unsigned long mp_frees; |
|
174 extern unsigned long mp_copies; |
|
175 #else |
|
176 |
|
177 /* Even if these are defined as macros, we need to respect the settings |
|
178 of the MP_MEMSET and MP_MEMCPY configuration options... |
|
179 */ |
|
180 #if MP_MEMSET == 0 |
|
181 #define s_mp_setz(dp, count) \ |
|
182 {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=0;} |
|
183 #else |
|
184 #define s_mp_setz(dp, count) memset(dp, 0, (count) * sizeof(mp_digit)) |
|
185 #endif /* MP_MEMSET */ |
|
186 |
|
187 #if MP_MEMCPY == 0 |
|
188 #define s_mp_copy(sp, dp, count) \ |
|
189 {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=(sp)[ix];} |
|
190 #else |
|
191 #define s_mp_copy(sp, dp, count) memcpy(dp, sp, (count) * sizeof(mp_digit)) |
|
192 #endif /* MP_MEMCPY */ |
|
193 |
|
194 #define s_mp_alloc(nb, ni) calloc(nb, ni) |
|
195 #define s_mp_free(ptr) {if(ptr) free(ptr);} |
|
196 #endif /* MP_MACRO */ |
|
197 |
|
198 mp_err s_mp_grow(mp_int *mp, mp_size min); /* increase allocated size */ |
|
199 mp_err s_mp_pad(mp_int *mp, mp_size min); /* left pad with zeroes */ |
|
200 |
|
201 #if MP_MACRO == 0 |
|
202 void s_mp_clamp(mp_int *mp); /* clip leading zeroes */ |
|
203 #else |
|
204 #define s_mp_clamp(mp)\ |
|
205 { mp_size used = MP_USED(mp); \ |
|
206 while (used > 1 && DIGIT(mp, used - 1) == 0) --used; \ |
|
207 MP_USED(mp) = used; \ |
|
208 } |
|
209 #endif /* MP_MACRO */ |
|
210 |
|
211 void s_mp_exch(mp_int *a, mp_int *b); /* swap a and b in place */ |
|
212 |
|
213 mp_err s_mp_lshd(mp_int *mp, mp_size p); /* left-shift by p digits */ |
|
214 void s_mp_rshd(mp_int *mp, mp_size p); /* right-shift by p digits */ |
|
215 mp_err s_mp_mul_2d(mp_int *mp, mp_digit d); /* multiply by 2^d in place */ |
|
216 void s_mp_div_2d(mp_int *mp, mp_digit d); /* divide by 2^d in place */ |
|
217 void s_mp_mod_2d(mp_int *mp, mp_digit d); /* modulo 2^d in place */ |
|
218 void s_mp_div_2(mp_int *mp); /* divide by 2 in place */ |
|
219 mp_err s_mp_mul_2(mp_int *mp); /* multiply by 2 in place */ |
|
220 mp_err s_mp_norm(mp_int *a, mp_int *b, mp_digit *pd); |
|
221 /* normalize for division */ |
|
222 mp_err s_mp_add_d(mp_int *mp, mp_digit d); /* unsigned digit addition */ |
|
223 mp_err s_mp_sub_d(mp_int *mp, mp_digit d); /* unsigned digit subtract */ |
|
224 mp_err s_mp_mul_d(mp_int *mp, mp_digit d); /* unsigned digit multiply */ |
|
225 mp_err s_mp_div_d(mp_int *mp, mp_digit d, mp_digit *r); |
|
226 /* unsigned digit divide */ |
|
227 mp_err s_mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu); |
|
228 /* Barrett reduction */ |
|
229 mp_err s_mp_add(mp_int *a, const mp_int *b); /* magnitude addition */ |
|
230 mp_err s_mp_add_3arg(const mp_int *a, const mp_int *b, mp_int *c); |
|
231 mp_err s_mp_sub(mp_int *a, const mp_int *b); /* magnitude subtract */ |
|
232 mp_err s_mp_sub_3arg(const mp_int *a, const mp_int *b, mp_int *c); |
|
233 mp_err s_mp_add_offset(mp_int *a, mp_int *b, mp_size offset); |
|
234 /* a += b * RADIX^offset */ |
|
235 mp_err s_mp_mul(mp_int *a, const mp_int *b); /* magnitude multiply */ |
|
236 #if MP_SQUARE |
|
237 mp_err s_mp_sqr(mp_int *a); /* magnitude square */ |
|
238 #else |
|
239 #define s_mp_sqr(a) s_mp_mul(a, a) |
|
240 #endif |
|
241 mp_err s_mp_div(mp_int *rem, mp_int *div, mp_int *quot); /* magnitude div */ |
|
242 mp_err s_mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); |
|
243 mp_err s_mp_2expt(mp_int *a, mp_digit k); /* a = 2^k */ |
|
244 int s_mp_cmp(const mp_int *a, const mp_int *b); /* magnitude comparison */ |
|
245 int s_mp_cmp_d(const mp_int *a, mp_digit d); /* magnitude digit compare */ |
|
246 int s_mp_ispow2(const mp_int *v); /* is v a power of 2? */ |
|
247 int s_mp_ispow2d(mp_digit d); /* is d a power of 2? */ |
|
248 |
|
249 int s_mp_tovalue(char ch, int r); /* convert ch to value */ |
|
250 char s_mp_todigit(mp_digit val, int r, int low); /* convert val to digit */ |
|
251 int s_mp_outlen(int bits, int r); /* output length in bytes */ |
|
252 mp_digit s_mp_invmod_radix(mp_digit P); /* returns (P ** -1) mod RADIX */ |
|
253 mp_err s_mp_invmod_odd_m( const mp_int *a, const mp_int *m, mp_int *c); |
|
254 mp_err s_mp_invmod_2d( const mp_int *a, mp_size k, mp_int *c); |
|
255 mp_err s_mp_invmod_even_m(const mp_int *a, const mp_int *m, mp_int *c); |
|
256 |
|
257 #ifdef NSS_USE_COMBA |
|
258 |
|
259 #define IS_POWER_OF_2(a) ((a) && !((a) & ((a)-1))) |
|
260 |
|
261 void s_mp_mul_comba_4(const mp_int *A, const mp_int *B, mp_int *C); |
|
262 void s_mp_mul_comba_8(const mp_int *A, const mp_int *B, mp_int *C); |
|
263 void s_mp_mul_comba_16(const mp_int *A, const mp_int *B, mp_int *C); |
|
264 void s_mp_mul_comba_32(const mp_int *A, const mp_int *B, mp_int *C); |
|
265 |
|
266 void s_mp_sqr_comba_4(const mp_int *A, mp_int *B); |
|
267 void s_mp_sqr_comba_8(const mp_int *A, mp_int *B); |
|
268 void s_mp_sqr_comba_16(const mp_int *A, mp_int *B); |
|
269 void s_mp_sqr_comba_32(const mp_int *A, mp_int *B); |
|
270 |
|
271 #endif /* end NSS_USE_COMBA */ |
|
272 |
|
273 /* ------ mpv functions, operate on arrays of digits, not on mp_int's ------ */ |
|
274 #if defined (__OS2__) && defined (__IBMC__) |
|
275 #define MPI_ASM_DECL __cdecl |
|
276 #else |
|
277 #define MPI_ASM_DECL |
|
278 #endif |
|
279 |
|
280 #ifdef MPI_AMD64 |
|
281 |
|
282 mp_digit MPI_ASM_DECL s_mpv_mul_set_vec64(mp_digit*, mp_digit *, mp_size, mp_digit); |
|
283 mp_digit MPI_ASM_DECL s_mpv_mul_add_vec64(mp_digit*, const mp_digit*, mp_size, mp_digit); |
|
284 |
|
285 /* c = a * b */ |
|
286 #define s_mpv_mul_d(a, a_len, b, c) \ |
|
287 ((unsigned long*)c)[a_len] = s_mpv_mul_set_vec64(c, a, a_len, b) |
|
288 |
|
289 /* c += a * b */ |
|
290 #define s_mpv_mul_d_add(a, a_len, b, c) \ |
|
291 ((unsigned long*)c)[a_len] = s_mpv_mul_add_vec64(c, a, a_len, b) |
|
292 |
|
293 #else |
|
294 |
|
295 void MPI_ASM_DECL s_mpv_mul_d(const mp_digit *a, mp_size a_len, |
|
296 mp_digit b, mp_digit *c); |
|
297 void MPI_ASM_DECL s_mpv_mul_d_add(const mp_digit *a, mp_size a_len, |
|
298 mp_digit b, mp_digit *c); |
|
299 |
|
300 #endif |
|
301 |
|
302 void MPI_ASM_DECL s_mpv_mul_d_add_prop(const mp_digit *a, |
|
303 mp_size a_len, mp_digit b, |
|
304 mp_digit *c); |
|
305 void MPI_ASM_DECL s_mpv_sqr_add_prop(const mp_digit *a, |
|
306 mp_size a_len, |
|
307 mp_digit *sqrs); |
|
308 |
|
309 mp_err MPI_ASM_DECL s_mpv_div_2dx1d(mp_digit Nhi, mp_digit Nlo, |
|
310 mp_digit divisor, mp_digit *quot, mp_digit *rem); |
|
311 |
|
312 /* c += a * b * (MP_RADIX ** offset); */ |
|
313 #define s_mp_mul_d_add_offset(a, b, c, off) \ |
|
314 (s_mpv_mul_d_add_prop(MP_DIGITS(a), MP_USED(a), b, MP_DIGITS(c) + off), MP_OKAY) |
|
315 |
|
316 typedef struct { |
|
317 mp_int N; /* modulus N */ |
|
318 mp_digit n0prime; /* n0' = - (n0 ** -1) mod MP_RADIX */ |
|
319 mp_size b; /* R == 2 ** b, also b = # significant bits in N */ |
|
320 } mp_mont_modulus; |
|
321 |
|
322 mp_err s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c, |
|
323 mp_mont_modulus *mmm); |
|
324 mp_err s_mp_redc(mp_int *T, mp_mont_modulus *mmm); |
|
325 |
|
326 /* |
|
327 * s_mpi_getProcessorLineSize() returns the size in bytes of the cache line |
|
328 * if a cache exists, or zero if there is no cache. If more than one |
|
329 * cache line exists, it should return the smallest line size (which is |
|
330 * usually the L1 cache). |
|
331 * |
|
332 * mp_modexp uses this information to make sure that private key information |
|
333 * isn't being leaked through the cache. |
|
334 * |
|
335 * see mpcpucache.c for the implementation. |
|
336 */ |
|
337 unsigned long s_mpi_getProcessorLineSize(); |
|
338 |
|
339 /* }}} */ |
|
340 #endif /* _MPI_PRIV_H */ |