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