|
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 * |
|
18 * Arbitrary precision integer arithmetic library |
|
19 * |
|
20 * Version: MPL 1.1/GPL 2.0/LGPL 2.1 |
|
21 * |
|
22 * The contents of this file are subject to the Mozilla Public License Version |
|
23 * 1.1 (the "License"); you may not use this file except in compliance with |
|
24 * the License. You may obtain a copy of the License at |
|
25 * http://www.mozilla.org/MPL/ |
|
26 * |
|
27 * Software distributed under the License is distributed on an "AS IS" basis, |
|
28 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License |
|
29 * for the specific language governing rights and limitations under the |
|
30 * License. |
|
31 * |
|
32 * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library. |
|
33 * |
|
34 * The Initial Developer of the Original Code is |
|
35 * Michael J. Fromberger. |
|
36 * Portions created by the Initial Developer are Copyright (C) 1998 |
|
37 * the Initial Developer. All Rights Reserved. |
|
38 * |
|
39 * Contributor(s): |
|
40 * Netscape Communications Corporation |
|
41 * |
|
42 * Alternatively, the contents of this file may be used under the terms of |
|
43 * either the GNU General Public License Version 2 or later (the "GPL"), or |
|
44 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), |
|
45 * in which case the provisions of the GPL or the LGPL are applicable instead |
|
46 * of those above. If you wish to allow use of your version of this file only |
|
47 * under the terms of either the GPL or the LGPL, and not to allow others to |
|
48 * use your version of this file under the terms of the MPL, indicate your |
|
49 * decision by deleting the provisions above and replace them with the notice |
|
50 * and other provisions required by the GPL or the LGPL. If you do not delete |
|
51 * the provisions above, a recipient may use your version of this file under |
|
52 * the terms of any one of the MPL, the GPL or the LGPL. |
|
53 * |
|
54 *********************************************************************** */ |
|
55 /* |
|
56 * Copyright 2007 Sun Microsystems, Inc. All rights reserved. |
|
57 * Use is subject to license terms. |
|
58 */ |
|
59 |
|
60 #ifndef _MPI_H |
|
61 #define _MPI_H |
|
62 |
|
63 #pragma ident "%Z%%M% %I% %E% SMI" |
|
64 |
|
65 /* $Id: mpi.h,v 1.22 2004/04/27 23:04:36 gerv%gerv.net Exp $ */ |
|
66 |
|
67 #include "mpi-config.h" |
|
68 |
|
69 #ifndef _WIN32 |
|
70 #include <sys/param.h> |
|
71 #endif /* _WIN32 */ |
|
72 |
|
73 #ifdef _KERNEL |
|
74 #include <sys/debug.h> |
|
75 #include <sys/systm.h> |
|
76 #define assert ASSERT |
|
77 #define labs(a) (a >= 0 ? a : -a) |
|
78 #define UCHAR_MAX 255 |
|
79 #define memset(s, c, n) bzero(s, n) |
|
80 #define memcpy(a,b,c) bcopy((caddr_t)b, (caddr_t)a, c) |
|
81 /* |
|
82 * Generic #define's to cover missing things in the kernel |
|
83 */ |
|
84 #ifndef isdigit |
|
85 #define isdigit(x) ((x) >= '0' && (x) <= '9') |
|
86 #endif |
|
87 #ifndef isupper |
|
88 #define isupper(x) (((unsigned)(x) >= 'A') && ((unsigned)(x) <= 'Z')) |
|
89 #endif |
|
90 #ifndef islower |
|
91 #define islower(x) (((unsigned)(x) >= 'a') && ((unsigned)(x) <= 'z')) |
|
92 #endif |
|
93 #ifndef isalpha |
|
94 #define isalpha(x) (isupper(x) || islower(x)) |
|
95 #endif |
|
96 #ifndef toupper |
|
97 #define toupper(x) (islower(x) ? (x) - 'a' + 'A' : (x)) |
|
98 #endif |
|
99 #ifndef tolower |
|
100 #define tolower(x) (isupper(x) ? (x) + 'a' - 'A' : (x)) |
|
101 #endif |
|
102 #ifndef isspace |
|
103 #define isspace(x) (((x) == ' ') || ((x) == '\r') || ((x) == '\n') || \ |
|
104 ((x) == '\t') || ((x) == '\b')) |
|
105 #endif |
|
106 #endif /* _KERNEL */ |
|
107 |
|
108 #if MP_DEBUG |
|
109 #undef MP_IOFUNC |
|
110 #define MP_IOFUNC 1 |
|
111 #endif |
|
112 |
|
113 #if MP_IOFUNC |
|
114 #include <stdio.h> |
|
115 #include <ctype.h> |
|
116 #endif |
|
117 |
|
118 #ifndef _KERNEL |
|
119 #include <limits.h> |
|
120 #endif |
|
121 |
|
122 #if defined(BSDI) |
|
123 #undef ULLONG_MAX |
|
124 #endif |
|
125 |
|
126 #if defined( macintosh ) |
|
127 #include <Types.h> |
|
128 #elif defined( _WIN32_WCE) |
|
129 /* #include <sys/types.h> What do we need here ?? */ |
|
130 #else |
|
131 #include <sys/types.h> |
|
132 #endif |
|
133 |
|
134 #define MP_NEG 1 |
|
135 #define MP_ZPOS 0 |
|
136 |
|
137 #define MP_OKAY 0 /* no error, all is well */ |
|
138 #define MP_YES 0 /* yes (boolean result) */ |
|
139 #define MP_NO -1 /* no (boolean result) */ |
|
140 #define MP_MEM -2 /* out of memory */ |
|
141 #define MP_RANGE -3 /* argument out of range */ |
|
142 #define MP_BADARG -4 /* invalid parameter */ |
|
143 #define MP_UNDEF -5 /* answer is undefined */ |
|
144 #define MP_LAST_CODE MP_UNDEF |
|
145 |
|
146 typedef unsigned int mp_sign; |
|
147 typedef unsigned int mp_size; |
|
148 typedef int mp_err; |
|
149 typedef int mp_flag; |
|
150 |
|
151 #define MP_32BIT_MAX 4294967295U |
|
152 |
|
153 #if !defined(ULONG_MAX) |
|
154 #error "ULONG_MAX not defined" |
|
155 #elif !defined(UINT_MAX) |
|
156 #error "UINT_MAX not defined" |
|
157 #elif !defined(USHRT_MAX) |
|
158 #error "USHRT_MAX not defined" |
|
159 #endif |
|
160 |
|
161 #if defined(ULONG_LONG_MAX) /* GCC, HPUX */ |
|
162 #define MP_ULONG_LONG_MAX ULONG_LONG_MAX |
|
163 #elif defined(ULLONG_MAX) /* Solaris */ |
|
164 #define MP_ULONG_LONG_MAX ULLONG_MAX |
|
165 /* MP_ULONG_LONG_MAX was defined to be ULLONG_MAX */ |
|
166 #elif defined(ULONGLONG_MAX) /* IRIX, AIX */ |
|
167 #define MP_ULONG_LONG_MAX ULONGLONG_MAX |
|
168 #endif |
|
169 |
|
170 /* We only use unsigned long for mp_digit iff long is more than 32 bits. */ |
|
171 #if !defined(MP_USE_UINT_DIGIT) && ULONG_MAX > MP_32BIT_MAX |
|
172 typedef unsigned long mp_digit; |
|
173 #define MP_DIGIT_MAX ULONG_MAX |
|
174 #define MP_DIGIT_FMT "%016lX" /* printf() format for 1 digit */ |
|
175 #define MP_HALF_DIGIT_MAX UINT_MAX |
|
176 #undef MP_NO_MP_WORD |
|
177 #define MP_NO_MP_WORD 1 |
|
178 #undef MP_USE_LONG_DIGIT |
|
179 #define MP_USE_LONG_DIGIT 1 |
|
180 #undef MP_USE_LONG_LONG_DIGIT |
|
181 |
|
182 #elif !defined(MP_USE_UINT_DIGIT) && defined(MP_ULONG_LONG_MAX) |
|
183 typedef unsigned long long mp_digit; |
|
184 #define MP_DIGIT_MAX MP_ULONG_LONG_MAX |
|
185 #define MP_DIGIT_FMT "%016llX" /* printf() format for 1 digit */ |
|
186 #define MP_HALF_DIGIT_MAX UINT_MAX |
|
187 #undef MP_NO_MP_WORD |
|
188 #define MP_NO_MP_WORD 1 |
|
189 #undef MP_USE_LONG_LONG_DIGIT |
|
190 #define MP_USE_LONG_LONG_DIGIT 1 |
|
191 #undef MP_USE_LONG_DIGIT |
|
192 |
|
193 #else |
|
194 typedef unsigned int mp_digit; |
|
195 #define MP_DIGIT_MAX UINT_MAX |
|
196 #define MP_DIGIT_FMT "%08X" /* printf() format for 1 digit */ |
|
197 #define MP_HALF_DIGIT_MAX USHRT_MAX |
|
198 #undef MP_USE_UINT_DIGIT |
|
199 #define MP_USE_UINT_DIGIT 1 |
|
200 #undef MP_USE_LONG_LONG_DIGIT |
|
201 #undef MP_USE_LONG_DIGIT |
|
202 #endif |
|
203 |
|
204 #if !defined(MP_NO_MP_WORD) |
|
205 #if defined(MP_USE_UINT_DIGIT) && \ |
|
206 (defined(MP_ULONG_LONG_MAX) || (ULONG_MAX > UINT_MAX)) |
|
207 |
|
208 #if (ULONG_MAX > UINT_MAX) |
|
209 typedef unsigned long mp_word; |
|
210 typedef long mp_sword; |
|
211 #define MP_WORD_MAX ULONG_MAX |
|
212 |
|
213 #else |
|
214 typedef unsigned long long mp_word; |
|
215 typedef long long mp_sword; |
|
216 #define MP_WORD_MAX MP_ULONG_LONG_MAX |
|
217 #endif |
|
218 |
|
219 #else |
|
220 #define MP_NO_MP_WORD 1 |
|
221 #endif |
|
222 #endif /* !defined(MP_NO_MP_WORD) */ |
|
223 |
|
224 #if !defined(MP_WORD_MAX) && defined(MP_DEFINE_SMALL_WORD) |
|
225 typedef unsigned int mp_word; |
|
226 typedef int mp_sword; |
|
227 #define MP_WORD_MAX UINT_MAX |
|
228 #endif |
|
229 |
|
230 #ifndef CHAR_BIT |
|
231 #define CHAR_BIT 8 |
|
232 #endif |
|
233 |
|
234 #define MP_DIGIT_BIT (CHAR_BIT*sizeof(mp_digit)) |
|
235 #define MP_WORD_BIT (CHAR_BIT*sizeof(mp_word)) |
|
236 #define MP_RADIX (1+(mp_word)MP_DIGIT_MAX) |
|
237 |
|
238 #define MP_HALF_DIGIT_BIT (MP_DIGIT_BIT/2) |
|
239 #define MP_HALF_RADIX (1+(mp_digit)MP_HALF_DIGIT_MAX) |
|
240 /* MP_HALF_RADIX really ought to be called MP_SQRT_RADIX, but it's named |
|
241 ** MP_HALF_RADIX because it's the radix for MP_HALF_DIGITs, and it's |
|
242 ** consistent with the other _HALF_ names. |
|
243 */ |
|
244 |
|
245 |
|
246 /* Macros for accessing the mp_int internals */ |
|
247 #define MP_FLAG(MP) ((MP)->flag) |
|
248 #define MP_SIGN(MP) ((MP)->sign) |
|
249 #define MP_USED(MP) ((MP)->used) |
|
250 #define MP_ALLOC(MP) ((MP)->alloc) |
|
251 #define MP_DIGITS(MP) ((MP)->dp) |
|
252 #define MP_DIGIT(MP,N) (MP)->dp[(N)] |
|
253 |
|
254 /* This defines the maximum I/O base (minimum is 2) */ |
|
255 #define MP_MAX_RADIX 64 |
|
256 |
|
257 typedef struct { |
|
258 mp_sign flag; /* KM_SLEEP/KM_NOSLEEP */ |
|
259 mp_sign sign; /* sign of this quantity */ |
|
260 mp_size alloc; /* how many digits allocated */ |
|
261 mp_size used; /* how many digits used */ |
|
262 mp_digit *dp; /* the digits themselves */ |
|
263 } mp_int; |
|
264 |
|
265 /* Default precision */ |
|
266 mp_size mp_get_prec(void); |
|
267 void mp_set_prec(mp_size prec); |
|
268 |
|
269 /* Memory management */ |
|
270 mp_err mp_init(mp_int *mp, int kmflag); |
|
271 mp_err mp_init_size(mp_int *mp, mp_size prec, int kmflag); |
|
272 mp_err mp_init_copy(mp_int *mp, const mp_int *from); |
|
273 mp_err mp_copy(const mp_int *from, mp_int *to); |
|
274 void mp_exch(mp_int *mp1, mp_int *mp2); |
|
275 void mp_clear(mp_int *mp); |
|
276 void mp_zero(mp_int *mp); |
|
277 void mp_set(mp_int *mp, mp_digit d); |
|
278 mp_err mp_set_int(mp_int *mp, long z); |
|
279 #define mp_set_long(mp,z) mp_set_int(mp,z) |
|
280 mp_err mp_set_ulong(mp_int *mp, unsigned long z); |
|
281 |
|
282 /* Single digit arithmetic */ |
|
283 mp_err mp_add_d(const mp_int *a, mp_digit d, mp_int *b); |
|
284 mp_err mp_sub_d(const mp_int *a, mp_digit d, mp_int *b); |
|
285 mp_err mp_mul_d(const mp_int *a, mp_digit d, mp_int *b); |
|
286 mp_err mp_mul_2(const mp_int *a, mp_int *c); |
|
287 mp_err mp_div_d(const mp_int *a, mp_digit d, mp_int *q, mp_digit *r); |
|
288 mp_err mp_div_2(const mp_int *a, mp_int *c); |
|
289 mp_err mp_expt_d(const mp_int *a, mp_digit d, mp_int *c); |
|
290 |
|
291 /* Sign manipulations */ |
|
292 mp_err mp_abs(const mp_int *a, mp_int *b); |
|
293 mp_err mp_neg(const mp_int *a, mp_int *b); |
|
294 |
|
295 /* Full arithmetic */ |
|
296 mp_err mp_add(const mp_int *a, const mp_int *b, mp_int *c); |
|
297 mp_err mp_sub(const mp_int *a, const mp_int *b, mp_int *c); |
|
298 mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c); |
|
299 #if MP_SQUARE |
|
300 mp_err mp_sqr(const mp_int *a, mp_int *b); |
|
301 #else |
|
302 #define mp_sqr(a, b) mp_mul(a, a, b) |
|
303 #endif |
|
304 mp_err mp_div(const mp_int *a, const mp_int *b, mp_int *q, mp_int *r); |
|
305 mp_err mp_div_2d(const mp_int *a, mp_digit d, mp_int *q, mp_int *r); |
|
306 mp_err mp_expt(mp_int *a, mp_int *b, mp_int *c); |
|
307 mp_err mp_2expt(mp_int *a, mp_digit k); |
|
308 mp_err mp_sqrt(const mp_int *a, mp_int *b); |
|
309 |
|
310 /* Modular arithmetic */ |
|
311 #if MP_MODARITH |
|
312 mp_err mp_mod(const mp_int *a, const mp_int *m, mp_int *c); |
|
313 mp_err mp_mod_d(const mp_int *a, mp_digit d, mp_digit *c); |
|
314 mp_err mp_addmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); |
|
315 mp_err mp_submod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); |
|
316 mp_err mp_mulmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); |
|
317 #if MP_SQUARE |
|
318 mp_err mp_sqrmod(const mp_int *a, const mp_int *m, mp_int *c); |
|
319 #else |
|
320 #define mp_sqrmod(a, m, c) mp_mulmod(a, a, m, c) |
|
321 #endif |
|
322 mp_err mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); |
|
323 mp_err mp_exptmod_d(const mp_int *a, mp_digit d, const mp_int *m, mp_int *c); |
|
324 #endif /* MP_MODARITH */ |
|
325 |
|
326 /* Comparisons */ |
|
327 int mp_cmp_z(const mp_int *a); |
|
328 int mp_cmp_d(const mp_int *a, mp_digit d); |
|
329 int mp_cmp(const mp_int *a, const mp_int *b); |
|
330 int mp_cmp_mag(mp_int *a, mp_int *b); |
|
331 int mp_cmp_int(const mp_int *a, long z, int kmflag); |
|
332 int mp_isodd(const mp_int *a); |
|
333 int mp_iseven(const mp_int *a); |
|
334 |
|
335 /* Number theoretic */ |
|
336 #if MP_NUMTH |
|
337 mp_err mp_gcd(mp_int *a, mp_int *b, mp_int *c); |
|
338 mp_err mp_lcm(mp_int *a, mp_int *b, mp_int *c); |
|
339 mp_err mp_xgcd(const mp_int *a, const mp_int *b, mp_int *g, mp_int *x, mp_int *y); |
|
340 mp_err mp_invmod(const mp_int *a, const mp_int *m, mp_int *c); |
|
341 mp_err mp_invmod_xgcd(const mp_int *a, const mp_int *m, mp_int *c); |
|
342 #endif /* end MP_NUMTH */ |
|
343 |
|
344 /* Input and output */ |
|
345 #if MP_IOFUNC |
|
346 void mp_print(mp_int *mp, FILE *ofp); |
|
347 #endif /* end MP_IOFUNC */ |
|
348 |
|
349 /* Base conversion */ |
|
350 mp_err mp_read_raw(mp_int *mp, char *str, int len); |
|
351 int mp_raw_size(mp_int *mp); |
|
352 mp_err mp_toraw(mp_int *mp, char *str); |
|
353 mp_err mp_read_radix(mp_int *mp, const char *str, int radix); |
|
354 mp_err mp_read_variable_radix(mp_int *a, const char * str, int default_radix); |
|
355 int mp_radix_size(mp_int *mp, int radix); |
|
356 mp_err mp_toradix(mp_int *mp, char *str, int radix); |
|
357 int mp_tovalue(char ch, int r); |
|
358 |
|
359 #define mp_tobinary(M, S) mp_toradix((M), (S), 2) |
|
360 #define mp_tooctal(M, S) mp_toradix((M), (S), 8) |
|
361 #define mp_todecimal(M, S) mp_toradix((M), (S), 10) |
|
362 #define mp_tohex(M, S) mp_toradix((M), (S), 16) |
|
363 |
|
364 /* Error strings */ |
|
365 const char *mp_strerror(mp_err ec); |
|
366 |
|
367 /* Octet string conversion functions */ |
|
368 mp_err mp_read_unsigned_octets(mp_int *mp, const unsigned char *str, mp_size len); |
|
369 int mp_unsigned_octet_size(const mp_int *mp); |
|
370 mp_err mp_to_unsigned_octets(const mp_int *mp, unsigned char *str, mp_size maxlen); |
|
371 mp_err mp_to_signed_octets(const mp_int *mp, unsigned char *str, mp_size maxlen); |
|
372 mp_err mp_to_fixlen_octets(const mp_int *mp, unsigned char *str, mp_size len); |
|
373 |
|
374 /* Miscellaneous */ |
|
375 mp_size mp_trailing_zeros(const mp_int *mp); |
|
376 |
|
377 #define MP_CHECKOK(x) if (MP_OKAY > (res = (x))) goto CLEANUP |
|
378 #define MP_CHECKERR(x) if (MP_OKAY > (res = (x))) goto CLEANUP |
|
379 |
|
380 #if defined(MP_API_COMPATIBLE) |
|
381 #define NEG MP_NEG |
|
382 #define ZPOS MP_ZPOS |
|
383 #define DIGIT_MAX MP_DIGIT_MAX |
|
384 #define DIGIT_BIT MP_DIGIT_BIT |
|
385 #define DIGIT_FMT MP_DIGIT_FMT |
|
386 #define RADIX MP_RADIX |
|
387 #define MAX_RADIX MP_MAX_RADIX |
|
388 #define FLAG(MP) MP_FLAG(MP) |
|
389 #define SIGN(MP) MP_SIGN(MP) |
|
390 #define USED(MP) MP_USED(MP) |
|
391 #define ALLOC(MP) MP_ALLOC(MP) |
|
392 #define DIGITS(MP) MP_DIGITS(MP) |
|
393 #define DIGIT(MP,N) MP_DIGIT(MP,N) |
|
394 |
|
395 #if MP_ARGCHK == 1 |
|
396 #define ARGCHK(X,Y) {if(!(X)){return (Y);}} |
|
397 #elif MP_ARGCHK == 2 |
|
398 #ifdef _KERNEL |
|
399 #define ARGCHK(X,Y) ASSERT(X) |
|
400 #else |
|
401 #include <assert.h> |
|
402 #define ARGCHK(X,Y) assert(X) |
|
403 #endif |
|
404 #else |
|
405 #define ARGCHK(X,Y) /* */ |
|
406 #endif |
|
407 #endif /* defined MP_API_COMPATIBLE */ |
|
408 |
|
409 #endif /* _MPI_H */ |