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