Back to index

lightning-sunbird  0.9+nobinonly
mpi.h
Go to the documentation of this file.
00001 /*
00002  *  mpi.h
00003  *
00004  *  Arbitrary precision integer arithmetic library
00005  *
00006  * ***** BEGIN LICENSE BLOCK *****
00007  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00008  *
00009  * The contents of this file are subject to the Mozilla Public License Version
00010  * 1.1 (the "License"); you may not use this file except in compliance with
00011  * the License. You may obtain a copy of the License at
00012  * http://www.mozilla.org/MPL/
00013  *
00014  * Software distributed under the License is distributed on an "AS IS" basis,
00015  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00016  * for the specific language governing rights and limitations under the
00017  * License.
00018  *
00019  * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library.
00020  *
00021  * The Initial Developer of the Original Code is
00022  * Michael J. Fromberger.
00023  * Portions created by the Initial Developer are Copyright (C) 1998
00024  * the Initial Developer. All Rights Reserved.
00025  *
00026  * Contributor(s):
00027  *   Netscape Communications Corporation
00028  *
00029  * Alternatively, the contents of this file may be used under the terms of
00030  * either the GNU General Public License Version 2 or later (the "GPL"), or
00031  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00032  * in which case the provisions of the GPL or the LGPL are applicable instead
00033  * of those above. If you wish to allow use of your version of this file only
00034  * under the terms of either the GPL or the LGPL, and not to allow others to
00035  * use your version of this file under the terms of the MPL, indicate your
00036  * decision by deleting the provisions above and replace them with the notice
00037  * and other provisions required by the GPL or the LGPL. If you do not delete
00038  * the provisions above, a recipient may use your version of this file under
00039  * the terms of any one of the MPL, the GPL or the LGPL.
00040  *
00041  * ***** END LICENSE BLOCK ***** */
00042 /* $Id: mpi.h,v 1.22 2004/04/27 23:04:36 gerv%gerv.net Exp $ */
00043 
00044 #ifndef _H_MPI_
00045 #define _H_MPI_
00046 
00047 #include "mpi-config.h"
00048 
00049 #if MP_DEBUG
00050 #undef MP_IOFUNC
00051 #define MP_IOFUNC 1
00052 #endif
00053 
00054 #if MP_IOFUNC
00055 #include <stdio.h>
00056 #include <ctype.h>
00057 #endif
00058 
00059 #include <limits.h>
00060 
00061 #if defined(BSDI)
00062 #undef ULLONG_MAX
00063 #endif
00064 
00065 #if defined( macintosh )
00066 #include <Types.h>
00067 #elif defined( _WIN32_WCE)
00068 /* #include <sys/types.h> What do we need here ?? */
00069 #else
00070 #include <sys/types.h>
00071 #endif
00072 
00073 #define  MP_NEG    1
00074 #define  MP_ZPOS   0
00075 
00076 #define  MP_OKAY          0 /* no error, all is well */
00077 #define  MP_YES           0 /* yes (boolean result)  */
00078 #define  MP_NO           -1 /* no (boolean result)   */
00079 #define  MP_MEM          -2 /* out of memory         */
00080 #define  MP_RANGE        -3 /* argument out of range */
00081 #define  MP_BADARG       -4 /* invalid parameter     */
00082 #define  MP_UNDEF        -5 /* answer is undefined   */
00083 #define  MP_LAST_CODE    MP_UNDEF
00084 
00085 typedef unsigned int      mp_sign;
00086 typedef unsigned int      mp_size;
00087 typedef int               mp_err;
00088 
00089 #define MP_32BIT_MAX 4294967295U
00090 
00091 #if !defined(ULONG_MAX) 
00092 #error "ULONG_MAX not defined"
00093 #elif !defined(UINT_MAX)
00094 #error "UINT_MAX not defined"
00095 #elif !defined(USHRT_MAX)
00096 #error "USHRT_MAX not defined"
00097 #endif
00098 
00099 #if defined(ULONG_LONG_MAX)               /* GCC, HPUX */
00100 #define MP_ULONG_LONG_MAX ULONG_LONG_MAX
00101 #elif defined(ULLONG_MAX)                 /* Solaris */
00102 #define MP_ULONG_LONG_MAX ULLONG_MAX
00103 /* MP_ULONG_LONG_MAX was defined to be ULLONG_MAX */
00104 #elif defined(ULONGLONG_MAX)                     /* IRIX, AIX */
00105 #define MP_ULONG_LONG_MAX ULONGLONG_MAX
00106 #endif
00107 
00108 /* We only use unsigned long for mp_digit iff long is more than 32 bits. */
00109 #if !defined(MP_USE_UINT_DIGIT) && ULONG_MAX > MP_32BIT_MAX
00110 typedef unsigned long     mp_digit;
00111 #define MP_DIGIT_MAX      ULONG_MAX
00112 #define MP_DIGIT_FMT      "%016lX"   /* printf() format for 1 digit */
00113 #define MP_HALF_DIGIT_MAX UINT_MAX
00114 #undef  MP_NO_MP_WORD
00115 #define MP_NO_MP_WORD 1
00116 #undef  MP_USE_LONG_DIGIT
00117 #define MP_USE_LONG_DIGIT 1
00118 #undef  MP_USE_LONG_LONG_DIGIT
00119 
00120 #elif !defined(MP_USE_UINT_DIGIT) && defined(MP_ULONG_LONG_MAX) 
00121 typedef unsigned long long mp_digit;
00122 #define MP_DIGIT_MAX       MP_ULONG_LONG_MAX
00123 #define MP_DIGIT_FMT      "%016llX"  /* printf() format for 1 digit */
00124 #define MP_HALF_DIGIT_MAX  UINT_MAX
00125 #undef  MP_NO_MP_WORD
00126 #define MP_NO_MP_WORD 1
00127 #undef  MP_USE_LONG_LONG_DIGIT
00128 #define MP_USE_LONG_LONG_DIGIT 1
00129 #undef  MP_USE_LONG_DIGIT
00130 
00131 #else
00132 typedef unsigned int      mp_digit;
00133 #define MP_DIGIT_MAX      UINT_MAX
00134 #define MP_DIGIT_FMT      "%08X"     /* printf() format for 1 digit */
00135 #define MP_HALF_DIGIT_MAX USHRT_MAX
00136 #undef  MP_USE_UINT_DIGIT
00137 #define MP_USE_UINT_DIGIT 1
00138 #undef  MP_USE_LONG_LONG_DIGIT
00139 #undef  MP_USE_LONG_DIGIT
00140 #endif
00141 
00142 #if !defined(MP_NO_MP_WORD) 
00143 #if  defined(MP_USE_UINT_DIGIT) && \
00144     (defined(MP_ULONG_LONG_MAX) || (ULONG_MAX > UINT_MAX))
00145 
00146 #if (ULONG_MAX > UINT_MAX)
00147 typedef unsigned long     mp_word;
00148 typedef          long     mp_sword;
00149 #define MP_WORD_MAX       ULONG_MAX
00150 
00151 #else
00152 typedef unsigned long long mp_word;
00153 typedef          long long mp_sword;
00154 #define MP_WORD_MAX       MP_ULONG_LONG_MAX
00155 #endif
00156 
00157 #else 
00158 #define MP_NO_MP_WORD 1
00159 #endif
00160 #endif /* !defined(MP_NO_MP_WORD) */
00161 
00162 #if !defined(MP_WORD_MAX) && defined(MP_DEFINE_SMALL_WORD)
00163 typedef unsigned int      mp_word;
00164 typedef          int      mp_sword;
00165 #define MP_WORD_MAX       UINT_MAX
00166 #endif
00167 
00168 #define MP_DIGIT_BIT      (CHAR_BIT*sizeof(mp_digit))
00169 #define MP_WORD_BIT       (CHAR_BIT*sizeof(mp_word))
00170 #define MP_RADIX          (1+(mp_word)MP_DIGIT_MAX)
00171 
00172 #define MP_HALF_DIGIT_BIT (MP_DIGIT_BIT/2)
00173 #define MP_HALF_RADIX     (1+(mp_digit)MP_HALF_DIGIT_MAX)
00174 /* MP_HALF_RADIX really ought to be called MP_SQRT_RADIX, but it's named 
00175 ** MP_HALF_RADIX because it's the radix for MP_HALF_DIGITs, and it's 
00176 ** consistent with the other _HALF_ names.
00177 */
00178 
00179 
00180 /* Macros for accessing the mp_int internals           */
00181 #define  MP_SIGN(MP)     ((MP)->sign)
00182 #define  MP_USED(MP)     ((MP)->used)
00183 #define  MP_ALLOC(MP)    ((MP)->alloc)
00184 #define  MP_DIGITS(MP)   ((MP)->dp)
00185 #define  MP_DIGIT(MP,N)  (MP)->dp[(N)]
00186 
00187 /* This defines the maximum I/O base (minimum is 2)   */
00188 #define MP_MAX_RADIX         64
00189 
00190 typedef struct {
00191   mp_sign       sign;    /* sign of this quantity      */
00192   mp_size       alloc;   /* how many digits allocated  */
00193   mp_size       used;    /* how many digits used       */
00194   mp_digit     *dp;      /* the digits themselves      */
00195 } mp_int;
00196 
00197 /* Default precision       */
00198 mp_size mp_get_prec(void);
00199 void    mp_set_prec(mp_size prec);
00200 
00201 /* Memory management       */
00202 mp_err mp_init(mp_int *mp);
00203 mp_err mp_init_size(mp_int *mp, mp_size prec);
00204 mp_err mp_init_copy(mp_int *mp, const mp_int *from);
00205 mp_err mp_copy(const mp_int *from, mp_int *to);
00206 void   mp_exch(mp_int *mp1, mp_int *mp2);
00207 void   mp_clear(mp_int *mp);
00208 void   mp_zero(mp_int *mp);
00209 void   mp_set(mp_int *mp, mp_digit d);
00210 mp_err mp_set_int(mp_int *mp, long z);
00211 #define mp_set_long(mp,z) mp_set_int(mp,z)
00212 mp_err mp_set_ulong(mp_int *mp, unsigned long z);
00213 
00214 /* Single digit arithmetic */
00215 mp_err mp_add_d(const mp_int *a, mp_digit d, mp_int *b);
00216 mp_err mp_sub_d(const mp_int *a, mp_digit d, mp_int *b);
00217 mp_err mp_mul_d(const mp_int *a, mp_digit d, mp_int *b);
00218 mp_err mp_mul_2(const mp_int *a, mp_int *c);
00219 mp_err mp_div_d(const mp_int *a, mp_digit d, mp_int *q, mp_digit *r);
00220 mp_err mp_div_2(const mp_int *a, mp_int *c);
00221 mp_err mp_expt_d(const mp_int *a, mp_digit d, mp_int *c);
00222 
00223 /* Sign manipulations      */
00224 mp_err mp_abs(const mp_int *a, mp_int *b);
00225 mp_err mp_neg(const mp_int *a, mp_int *b);
00226 
00227 /* Full arithmetic         */
00228 mp_err mp_add(const mp_int *a, const mp_int *b, mp_int *c);
00229 mp_err mp_sub(const mp_int *a, const mp_int *b, mp_int *c);
00230 mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c);
00231 #if MP_SQUARE
00232 mp_err mp_sqr(const mp_int *a, mp_int *b);
00233 #else
00234 #define mp_sqr(a, b) mp_mul(a, a, b)
00235 #endif
00236 mp_err mp_div(const mp_int *a, const mp_int *b, mp_int *q, mp_int *r);
00237 mp_err mp_div_2d(const mp_int *a, mp_digit d, mp_int *q, mp_int *r);
00238 mp_err mp_expt(mp_int *a, mp_int *b, mp_int *c);
00239 mp_err mp_2expt(mp_int *a, mp_digit k);
00240 mp_err mp_sqrt(const mp_int *a, mp_int *b);
00241 
00242 /* Modular arithmetic      */
00243 #if MP_MODARITH
00244 mp_err mp_mod(const mp_int *a, const mp_int *m, mp_int *c);
00245 mp_err mp_mod_d(const mp_int *a, mp_digit d, mp_digit *c);
00246 mp_err mp_addmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
00247 mp_err mp_submod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
00248 mp_err mp_mulmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
00249 #if MP_SQUARE
00250 mp_err mp_sqrmod(const mp_int *a, const mp_int *m, mp_int *c);
00251 #else
00252 #define mp_sqrmod(a, m, c) mp_mulmod(a, a, m, c)
00253 #endif
00254 mp_err mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
00255 mp_err mp_exptmod_d(const mp_int *a, mp_digit d, const mp_int *m, mp_int *c);
00256 #endif /* MP_MODARITH */
00257 
00258 /* Comparisons             */
00259 int    mp_cmp_z(const mp_int *a);
00260 int    mp_cmp_d(const mp_int *a, mp_digit d);
00261 int    mp_cmp(const mp_int *a, const mp_int *b);
00262 int    mp_cmp_mag(mp_int *a, mp_int *b);
00263 int    mp_cmp_int(const mp_int *a, long z);
00264 int    mp_isodd(const mp_int *a);
00265 int    mp_iseven(const mp_int *a);
00266 
00267 /* Number theoretic        */
00268 #if MP_NUMTH
00269 mp_err mp_gcd(mp_int *a, mp_int *b, mp_int *c);
00270 mp_err mp_lcm(mp_int *a, mp_int *b, mp_int *c);
00271 mp_err mp_xgcd(const mp_int *a, const mp_int *b, mp_int *g, mp_int *x, mp_int *y);
00272 mp_err mp_invmod(const mp_int *a, const mp_int *m, mp_int *c);
00273 mp_err mp_invmod_xgcd(const mp_int *a, const mp_int *m, mp_int *c);
00274 #endif /* end MP_NUMTH */
00275 
00276 /* Input and output        */
00277 #if MP_IOFUNC
00278 void   mp_print(mp_int *mp, FILE *ofp);
00279 #endif /* end MP_IOFUNC */
00280 
00281 /* Base conversion         */
00282 mp_err mp_read_raw(mp_int *mp, char *str, int len);
00283 int    mp_raw_size(mp_int *mp);
00284 mp_err mp_toraw(mp_int *mp, char *str);
00285 mp_err mp_read_radix(mp_int *mp, const char *str, int radix);
00286 mp_err mp_read_variable_radix(mp_int *a, const char * str, int default_radix);
00287 int    mp_radix_size(mp_int *mp, int radix);
00288 mp_err mp_toradix(mp_int *mp, char *str, int radix);
00289 int    mp_tovalue(char ch, int r);
00290 
00291 #define mp_tobinary(M, S)  mp_toradix((M), (S), 2)
00292 #define mp_tooctal(M, S)   mp_toradix((M), (S), 8)
00293 #define mp_todecimal(M, S) mp_toradix((M), (S), 10)
00294 #define mp_tohex(M, S)     mp_toradix((M), (S), 16)
00295 
00296 /* Error strings           */
00297 const  char  *mp_strerror(mp_err ec);
00298 
00299 /* Octet string conversion functions */
00300 mp_err mp_read_unsigned_octets(mp_int *mp, const unsigned char *str, mp_size len);
00301 int    mp_unsigned_octet_size(const mp_int *mp);
00302 mp_err mp_to_unsigned_octets(const mp_int *mp, unsigned char *str, mp_size maxlen);
00303 mp_err mp_to_signed_octets(const mp_int *mp, unsigned char *str, mp_size maxlen);
00304 mp_err mp_to_fixlen_octets(const mp_int *mp, unsigned char *str, mp_size len);
00305 
00306 /* Miscellaneous */
00307 mp_size mp_trailing_zeros(const mp_int *mp);
00308 
00309 #define MP_CHECKOK(x)  if (MP_OKAY > (res = (x))) goto CLEANUP
00310 #define MP_CHECKERR(x) if (MP_OKAY > (res = (x))) goto CLEANUP
00311 
00312 #if defined(MP_API_COMPATIBLE)
00313 #define NEG             MP_NEG
00314 #define ZPOS            MP_ZPOS
00315 #define DIGIT_MAX       MP_DIGIT_MAX
00316 #define DIGIT_BIT       MP_DIGIT_BIT
00317 #define DIGIT_FMT       MP_DIGIT_FMT
00318 #define RADIX           MP_RADIX
00319 #define MAX_RADIX       MP_MAX_RADIX
00320 #define SIGN(MP)        MP_SIGN(MP)
00321 #define USED(MP)        MP_USED(MP)
00322 #define ALLOC(MP)       MP_ALLOC(MP)
00323 #define DIGITS(MP)      MP_DIGITS(MP)
00324 #define DIGIT(MP,N)     MP_DIGIT(MP,N)
00325 
00326 #if MP_ARGCHK == 1
00327 #define  ARGCHK(X,Y)  {if(!(X)){return (Y);}}
00328 #elif MP_ARGCHK == 2
00329 #include <assert.h>
00330 #define  ARGCHK(X,Y)  assert(X)
00331 #else
00332 #define  ARGCHK(X,Y)  /*  */
00333 #endif
00334 #endif /* defined MP_API_COMPATIBLE */
00335 
00336 #endif /* end _H_MPI_ */