Home | History | Annotate | Download | only in mpi
      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