usr/src/common/mpi/mpi.h

   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
 129 typedef unsigned int      mp_sign;
 130 typedef unsigned int      mp_size;
 131 typedef int               mp_err;
 132 typedef 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
 155 typedef 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)
 166 typedef 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
 177 typedef 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)
 192 typedef unsigned long     mp_word;
 193 typedef          long     mp_sword;
 194 #define MP_WORD_MAX       ULONG_MAX
 195
 196 #else
 197 typedef unsigned long long mp_word;
 198 typedef          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)
 208 typedef unsigned int      mp_word;
 209 typedef          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
 240 typedef 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       */
 249 mp_size mp_get_prec(void);
 250 void    mp_set_prec(mp_size prec);
 251
 252 /* Memory management       */
 253 mp_err mp_init(mp_int *mp, int kmflag);
 254 mp_err mp_init_size(mp_int *mp, mp_size prec, int kmflag);
 255 mp_err mp_init_copy(mp_int *mp, const mp_int *from);
 256 mp_err mp_copy(const mp_int *from, mp_int *to);
 257 void   mp_exch(mp_int *mp1, mp_int *mp2);
 258 void   mp_clear(mp_int *mp);
 259 void   mp_zero(mp_int *mp);
 260 void   mp_set(mp_int *mp, mp_digit d);
 261 mp_err mp_set_int(mp_int *mp, long z);
 262 #define mp_set_long(mp,z) mp_set_int(mp,z)
 263 mp_err mp_set_ulong(mp_int *mp, unsigned long z);
 264
 265 /* Single digit arithmetic */
 266 mp_err mp_add_d(const mp_int *a, mp_digit d, mp_int *b);
 267 mp_err mp_sub_d(const mp_int *a, mp_digit d, mp_int *b);
 268 mp_err mp_mul_d(const mp_int *a, mp_digit d, mp_int *b);
 269 mp_err mp_mul_2(const mp_int *a, mp_int *c);
 270 mp_err mp_div_d(const mp_int *a, mp_digit d, mp_int *q, mp_digit *r);
 271 mp_err mp_div_2(const mp_int *a, mp_int *c);
 272 mp_err mp_expt_d(const mp_int *a, mp_digit d, mp_int *c);
 273
 274 /* Sign manipulations      */
 275 mp_err mp_abs(const mp_int *a, mp_int *b);
 276 mp_err mp_neg(const mp_int *a, mp_int *b);
 277
 278 /* Full arithmetic         */
 279 mp_err mp_add(const mp_int *a, const mp_int *b, mp_int *c);
 280 mp_err mp_sub(const mp_int *a, const mp_int *b, mp_int *c);
 281 mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c);
 282 #if MP_SQUARE
 283 mp_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
 287 mp_err mp_div(const mp_int *a, const mp_int *b, mp_int *q, mp_int *r);
 288 mp_err mp_div_2d(const mp_int *a, mp_digit d, mp_int *q, mp_int *r);
 289 mp_err mp_expt(mp_int *a, mp_int *b, mp_int *c);
 290 mp_err mp_2expt(mp_int *a, mp_digit k);
 291 mp_err mp_sqrt(const mp_int *a, mp_int *b);
 292
 293 /* Modular arithmetic      */
 294 #if MP_MODARITH
 295 mp_err mp_mod(const mp_int *a, const mp_int *m, mp_int *c);
 296 mp_err mp_mod_d(const mp_int *a, mp_digit d, mp_digit *c);
 297 mp_err mp_addmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
 298 mp_err mp_submod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
 299 mp_err mp_mulmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
 300 #if MP_SQUARE
 301 mp_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
 305 mp_err mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
 306 mp_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             */
 310 int    mp_cmp_z(const mp_int *a);
 311 int    mp_cmp_d(const mp_int *a, mp_digit d);
 312 int    mp_cmp(const mp_int *a, const mp_int *b);
 313 int    mp_cmp_mag(mp_int *a, mp_int *b);
 314 int    mp_cmp_int(const mp_int *a, long z, int kmflag);
 315 int    mp_isodd(const mp_int *a);
 316 int    mp_iseven(const mp_int *a);
 317
 318 /* Number theoretic        */
 319 #if MP_NUMTH
 320 mp_err mp_gcd(mp_int *a, mp_int *b, mp_int *c);
 321 mp_err mp_lcm(mp_int *a, mp_int *b, mp_int *c);
 322 mp_err mp_xgcd(const mp_int *a, const mp_int *b, mp_int *g, mp_int *x, mp_int *y);
 323 mp_err mp_invmod(const mp_int *a, const mp_int *m, mp_int *c);
 324 mp_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
 329 void   mp_print(mp_int *mp, FILE *ofp);
 330 #endif /* end MP_IOFUNC */
 331
 332 /* Base conversion         */
 333 mp_err mp_read_raw(mp_int *mp, char *str, int len);
 334 int    mp_raw_size(mp_int *mp);
 335 mp_err mp_toraw(mp_int *mp, char *str);
 336 mp_err mp_read_radix(mp_int *mp, const char *str, int radix);
 337 mp_err mp_read_variable_radix(mp_int *a, const char * str, int default_radix);
 338 int    mp_radix_size(mp_int *mp, int radix);
 339 mp_err mp_toradix(mp_int *mp, char *str, int radix);
 340 int    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           */
 348 const  char  *mp_strerror(mp_err ec);
 349
 350 /* Octet string conversion functions */
 351 mp_err mp_read_unsigned_octets(mp_int *mp, const unsigned char *str, mp_size len);
 352 int    mp_unsigned_octet_size(const mp_int *mp);
 353 mp_err mp_to_unsigned_octets(const mp_int *mp, unsigned char *str, mp_size maxlen);
 354 mp_err mp_to_signed_octets(const mp_int *mp, unsigned char *str, mp_size maxlen);
 355 mp_err mp_to_fixlen_octets(const mp_int *mp, unsigned char *str, mp_size len);
 356
 357 /* Miscellaneous */
 358 mp_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 */