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