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 124 typedef unsigned int mp_sign; 125 typedef unsigned int mp_size; 126 typedef int mp_err; 127 typedef 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 150 typedef 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) 161 typedef 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 172 typedef 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) 187 typedef unsigned long mp_word; 188 typedef long mp_sword; 189 #define MP_WORD_MAX ULONG_MAX 190 191 #else 192 typedef unsigned long long mp_word; 193 typedef 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) 203 typedef unsigned int mp_word; 204 typedef 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 235 typedef 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 */ 244 mp_size mp_get_prec(void); 245 void mp_set_prec(mp_size prec); 246 247 /* Memory management */ 248 mp_err mp_init(mp_int *mp, int kmflag); 249 mp_err mp_init_size(mp_int *mp, mp_size prec, int kmflag); 250 mp_err mp_init_copy(mp_int *mp, const mp_int *from); 251 mp_err mp_copy(const mp_int *from, mp_int *to); 252 void mp_exch(mp_int *mp1, mp_int *mp2); 253 void mp_clear(mp_int *mp); 254 void mp_zero(mp_int *mp); 255 void mp_set(mp_int *mp, mp_digit d); 256 mp_err mp_set_int(mp_int *mp, long z); 257 #define mp_set_long(mp,z) mp_set_int(mp,z) 258 mp_err mp_set_ulong(mp_int *mp, unsigned long z); 259 260 /* Single digit arithmetic */ 261 mp_err mp_add_d(const mp_int *a, mp_digit d, mp_int *b); 262 mp_err mp_sub_d(const mp_int *a, mp_digit d, mp_int *b); 263 mp_err mp_mul_d(const mp_int *a, mp_digit d, mp_int *b); 264 mp_err mp_mul_2(const mp_int *a, mp_int *c); 265 mp_err mp_div_d(const mp_int *a, mp_digit d, mp_int *q, mp_digit *r); 266 mp_err mp_div_2(const mp_int *a, mp_int *c); 267 mp_err mp_expt_d(const mp_int *a, mp_digit d, mp_int *c); 268 269 /* Sign manipulations */ 270 mp_err mp_abs(const mp_int *a, mp_int *b); 271 mp_err mp_neg(const mp_int *a, mp_int *b); 272 273 /* Full arithmetic */ 274 mp_err mp_add(const mp_int *a, const mp_int *b, mp_int *c); 275 mp_err mp_sub(const mp_int *a, const mp_int *b, mp_int *c); 276 mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c); 277 #if MP_SQUARE 278 mp_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 282 mp_err mp_div(const mp_int *a, const mp_int *b, mp_int *q, mp_int *r); 283 mp_err mp_div_2d(const mp_int *a, mp_digit d, mp_int *q, mp_int *r); 284 mp_err mp_expt(mp_int *a, mp_int *b, mp_int *c); 285 mp_err mp_2expt(mp_int *a, mp_digit k); 286 mp_err mp_sqrt(const mp_int *a, mp_int *b); 287 288 /* Modular arithmetic */ 289 #if MP_MODARITH 290 mp_err mp_mod(const mp_int *a, const mp_int *m, mp_int *c); 291 mp_err mp_mod_d(const mp_int *a, mp_digit d, mp_digit *c); 292 mp_err mp_addmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); 293 mp_err mp_submod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); 294 mp_err mp_mulmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); 295 #if MP_SQUARE 296 mp_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 300 mp_err mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); 301 mp_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 */ 305 int mp_cmp_z(const mp_int *a); 306 int mp_cmp_d(const mp_int *a, mp_digit d); 307 int mp_cmp(const mp_int *a, const mp_int *b); 308 int mp_cmp_mag(mp_int *a, mp_int *b); 309 int mp_cmp_int(const mp_int *a, long z, int kmflag); 310 int mp_isodd(const mp_int *a); 311 int mp_iseven(const mp_int *a); 312 313 /* Number theoretic */ 314 #if MP_NUMTH 315 mp_err mp_gcd(mp_int *a, mp_int *b, mp_int *c); 316 mp_err mp_lcm(mp_int *a, mp_int *b, mp_int *c); 317 mp_err mp_xgcd(const mp_int *a, const mp_int *b, mp_int *g, mp_int *x, mp_int *y); 318 mp_err mp_invmod(const mp_int *a, const mp_int *m, mp_int *c); 319 mp_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 324 void mp_print(mp_int *mp, FILE *ofp); 325 #endif /* end MP_IOFUNC */ 326 327 /* Base conversion */ 328 mp_err mp_read_raw(mp_int *mp, char *str, int len); 329 int mp_raw_size(mp_int *mp); 330 mp_err mp_toraw(mp_int *mp, char *str); 331 mp_err mp_read_radix(mp_int *mp, const char *str, int radix); 332 mp_err mp_read_variable_radix(mp_int *a, const char * str, int default_radix); 333 int mp_radix_size(mp_int *mp, int radix); 334 mp_err mp_toradix(mp_int *mp, char *str, int radix); 335 int 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 */ 343 const char *mp_strerror(mp_err ec); 344 345 /* Octet string conversion functions */ 346 mp_err mp_read_unsigned_octets(mp_int *mp, const unsigned char *str, mp_size len); 347 int mp_unsigned_octet_size(const mp_int *mp); 348 mp_err mp_to_unsigned_octets(const mp_int *mp, unsigned char *str, mp_size maxlen); 349 mp_err mp_to_signed_octets(const mp_int *mp, unsigned char *str, mp_size maxlen); 350 mp_err mp_to_fixlen_octets(const mp_int *mp, unsigned char *str, mp_size len); 351 352 /* Miscellaneous */ 353 mp_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