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