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