The Tor Browser / file comparison
comparison: security/nss/lib/freebl/mpi/mpi.h
security/nss/lib/freebl/mpi/mpi.h
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:d3ce00e5a077 |
|---|---|
| 1 /* | |
| 2 * mpi.h | |
| 3 * | |
| 4 * Arbitrary precision integer arithmetic library | |
| 5 * | |
| 6 * This Source Code Form is subject to the terms of the Mozilla Public | |
| 7 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 8 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 9 | |
| 10 #ifndef _H_MPI_ | |
| 11 #define _H_MPI_ | |
| 12 | |
| 13 #include "mpi-config.h" | |
| 14 | |
| 15 #if MP_DEBUG | |
| 16 #undef MP_IOFUNC | |
| 17 #define MP_IOFUNC 1 | |
| 18 #endif | |
| 19 | |
| 20 #if MP_IOFUNC | |
| 21 #include <stdio.h> | |
| 22 #include <ctype.h> | |
| 23 #endif | |
| 24 | |
| 25 #include <limits.h> | |
| 26 | |
| 27 #if defined(BSDI) | |
| 28 #undef ULLONG_MAX | |
| 29 #endif | |
| 30 | |
| 31 #include <sys/types.h> | |
| 32 | |
| 33 #define MP_NEG 1 | |
| 34 #define MP_ZPOS 0 | |
| 35 | |
| 36 #define MP_OKAY 0 /* no error, all is well */ | |
| 37 #define MP_YES 0 /* yes (boolean result) */ | |
| 38 #define MP_NO -1 /* no (boolean result) */ | |
| 39 #define MP_MEM -2 /* out of memory */ | |
| 40 #define MP_RANGE -3 /* argument out of range */ | |
| 41 #define MP_BADARG -4 /* invalid parameter */ | |
| 42 #define MP_UNDEF -5 /* answer is undefined */ | |
| 43 #define MP_LAST_CODE MP_UNDEF | |
| 44 | |
| 45 typedef unsigned int mp_sign; | |
| 46 typedef unsigned int mp_size; | |
| 47 typedef int mp_err; | |
| 48 | |
| 49 #define MP_32BIT_MAX 4294967295U | |
| 50 | |
| 51 #if !defined(ULONG_MAX) | |
| 52 #error "ULONG_MAX not defined" | |
| 53 #elif !defined(UINT_MAX) | |
| 54 #error "UINT_MAX not defined" | |
| 55 #elif !defined(USHRT_MAX) | |
| 56 #error "USHRT_MAX not defined" | |
| 57 #endif | |
| 58 | |
| 59 #if defined(ULLONG_MAX) /* C99, Solaris */ | |
| 60 #define MP_ULONG_LONG_MAX ULLONG_MAX | |
| 61 /* MP_ULONG_LONG_MAX was defined to be ULLONG_MAX */ | |
| 62 #elif defined(ULONG_LONG_MAX) /* HPUX */ | |
| 63 #define MP_ULONG_LONG_MAX ULONG_LONG_MAX | |
| 64 #elif defined(ULONGLONG_MAX) /* IRIX, AIX */ | |
| 65 #define MP_ULONG_LONG_MAX ULONGLONG_MAX | |
| 66 #endif | |
| 67 | |
| 68 /* We only use unsigned long for mp_digit iff long is more than 32 bits. */ | |
| 69 #if !defined(MP_USE_UINT_DIGIT) && ULONG_MAX > MP_32BIT_MAX | |
| 70 typedef unsigned long mp_digit; | |
| 71 #define MP_DIGIT_MAX ULONG_MAX | |
| 72 #define MP_DIGIT_FMT "%016lX" /* printf() format for 1 digit */ | |
| 73 #define MP_HALF_DIGIT_MAX UINT_MAX | |
| 74 #undef MP_NO_MP_WORD | |
| 75 #define MP_NO_MP_WORD 1 | |
| 76 #undef MP_USE_LONG_DIGIT | |
| 77 #define MP_USE_LONG_DIGIT 1 | |
| 78 #undef MP_USE_LONG_LONG_DIGIT | |
| 79 | |
| 80 #elif !defined(MP_USE_UINT_DIGIT) && defined(MP_ULONG_LONG_MAX) | |
| 81 typedef unsigned long long mp_digit; | |
| 82 #define MP_DIGIT_MAX MP_ULONG_LONG_MAX | |
| 83 #define MP_DIGIT_FMT "%016llX" /* printf() format for 1 digit */ | |
| 84 #define MP_HALF_DIGIT_MAX UINT_MAX | |
| 85 #undef MP_NO_MP_WORD | |
| 86 #define MP_NO_MP_WORD 1 | |
| 87 #undef MP_USE_LONG_LONG_DIGIT | |
| 88 #define MP_USE_LONG_LONG_DIGIT 1 | |
| 89 #undef MP_USE_LONG_DIGIT | |
| 90 | |
| 91 #else | |
| 92 typedef unsigned int mp_digit; | |
| 93 #define MP_DIGIT_MAX UINT_MAX | |
| 94 #define MP_DIGIT_FMT "%08X" /* printf() format for 1 digit */ | |
| 95 #define MP_HALF_DIGIT_MAX USHRT_MAX | |
| 96 #undef MP_USE_UINT_DIGIT | |
| 97 #define MP_USE_UINT_DIGIT 1 | |
| 98 #undef MP_USE_LONG_LONG_DIGIT | |
| 99 #undef MP_USE_LONG_DIGIT | |
| 100 #endif | |
| 101 | |
| 102 #if !defined(MP_NO_MP_WORD) | |
| 103 #if defined(MP_USE_UINT_DIGIT) && \ | |
| 104 (defined(MP_ULONG_LONG_MAX) || (ULONG_MAX > UINT_MAX)) | |
| 105 | |
| 106 #if (ULONG_MAX > UINT_MAX) | |
| 107 typedef unsigned long mp_word; | |
| 108 typedef long mp_sword; | |
| 109 #define MP_WORD_MAX ULONG_MAX | |
| 110 | |
| 111 #else | |
| 112 typedef unsigned long long mp_word; | |
| 113 typedef long long mp_sword; | |
| 114 #define MP_WORD_MAX MP_ULONG_LONG_MAX | |
| 115 #endif | |
| 116 | |
| 117 #else | |
| 118 #define MP_NO_MP_WORD 1 | |
| 119 #endif | |
| 120 #endif /* !defined(MP_NO_MP_WORD) */ | |
| 121 | |
| 122 #if !defined(MP_WORD_MAX) && defined(MP_DEFINE_SMALL_WORD) | |
| 123 typedef unsigned int mp_word; | |
| 124 typedef int mp_sword; | |
| 125 #define MP_WORD_MAX UINT_MAX | |
| 126 #endif | |
| 127 | |
| 128 #define MP_DIGIT_BIT (CHAR_BIT*sizeof(mp_digit)) | |
| 129 #define MP_WORD_BIT (CHAR_BIT*sizeof(mp_word)) | |
| 130 #define MP_RADIX (1+(mp_word)MP_DIGIT_MAX) | |
| 131 | |
| 132 #define MP_HALF_DIGIT_BIT (MP_DIGIT_BIT/2) | |
| 133 #define MP_HALF_RADIX (1+(mp_digit)MP_HALF_DIGIT_MAX) | |
| 134 /* MP_HALF_RADIX really ought to be called MP_SQRT_RADIX, but it's named | |
| 135 ** MP_HALF_RADIX because it's the radix for MP_HALF_DIGITs, and it's | |
| 136 ** consistent with the other _HALF_ names. | |
| 137 */ | |
| 138 | |
| 139 | |
| 140 /* Macros for accessing the mp_int internals */ | |
| 141 #define MP_SIGN(MP) ((MP)->sign) | |
| 142 #define MP_USED(MP) ((MP)->used) | |
| 143 #define MP_ALLOC(MP) ((MP)->alloc) | |
| 144 #define MP_DIGITS(MP) ((MP)->dp) | |
| 145 #define MP_DIGIT(MP,N) (MP)->dp[(N)] | |
| 146 | |
| 147 /* This defines the maximum I/O base (minimum is 2) */ | |
| 148 #define MP_MAX_RADIX 64 | |
| 149 | |
| 150 typedef struct { | |
| 151 mp_sign sign; /* sign of this quantity */ | |
| 152 mp_size alloc; /* how many digits allocated */ | |
| 153 mp_size used; /* how many digits used */ | |
| 154 mp_digit *dp; /* the digits themselves */ | |
| 155 } mp_int; | |
| 156 | |
| 157 /* Default precision */ | |
| 158 mp_size mp_get_prec(void); | |
| 159 void mp_set_prec(mp_size prec); | |
| 160 | |
| 161 /* Memory management */ | |
| 162 mp_err mp_init(mp_int *mp); | |
| 163 mp_err mp_init_size(mp_int *mp, mp_size prec); | |
| 164 mp_err mp_init_copy(mp_int *mp, const mp_int *from); | |
| 165 mp_err mp_copy(const mp_int *from, mp_int *to); | |
| 166 void mp_exch(mp_int *mp1, mp_int *mp2); | |
| 167 void mp_clear(mp_int *mp); | |
| 168 void mp_zero(mp_int *mp); | |
| 169 void mp_set(mp_int *mp, mp_digit d); | |
| 170 mp_err mp_set_int(mp_int *mp, long z); | |
| 171 #define mp_set_long(mp,z) mp_set_int(mp,z) | |
| 172 mp_err mp_set_ulong(mp_int *mp, unsigned long z); | |
| 173 | |
| 174 /* Single digit arithmetic */ | |
| 175 mp_err mp_add_d(const mp_int *a, mp_digit d, mp_int *b); | |
| 176 mp_err mp_sub_d(const mp_int *a, mp_digit d, mp_int *b); | |
| 177 mp_err mp_mul_d(const mp_int *a, mp_digit d, mp_int *b); | |
| 178 mp_err mp_mul_2(const mp_int *a, mp_int *c); | |
| 179 mp_err mp_div_d(const mp_int *a, mp_digit d, mp_int *q, mp_digit *r); | |
| 180 mp_err mp_div_2(const mp_int *a, mp_int *c); | |
| 181 mp_err mp_expt_d(const mp_int *a, mp_digit d, mp_int *c); | |
| 182 | |
| 183 /* Sign manipulations */ | |
| 184 mp_err mp_abs(const mp_int *a, mp_int *b); | |
| 185 mp_err mp_neg(const mp_int *a, mp_int *b); | |
| 186 | |
| 187 /* Full arithmetic */ | |
| 188 mp_err mp_add(const mp_int *a, const mp_int *b, mp_int *c); | |
| 189 mp_err mp_sub(const mp_int *a, const mp_int *b, mp_int *c); | |
| 190 mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c); | |
| 191 #if MP_SQUARE | |
| 192 mp_err mp_sqr(const mp_int *a, mp_int *b); | |
| 193 #else | |
| 194 #define mp_sqr(a, b) mp_mul(a, a, b) | |
| 195 #endif | |
| 196 mp_err mp_div(const mp_int *a, const mp_int *b, mp_int *q, mp_int *r); | |
| 197 mp_err mp_div_2d(const mp_int *a, mp_digit d, mp_int *q, mp_int *r); | |
| 198 mp_err mp_expt(mp_int *a, mp_int *b, mp_int *c); | |
| 199 mp_err mp_2expt(mp_int *a, mp_digit k); | |
| 200 mp_err mp_sqrt(const mp_int *a, mp_int *b); | |
| 201 | |
| 202 /* Modular arithmetic */ | |
| 203 #if MP_MODARITH | |
| 204 mp_err mp_mod(const mp_int *a, const mp_int *m, mp_int *c); | |
| 205 mp_err mp_mod_d(const mp_int *a, mp_digit d, mp_digit *c); | |
| 206 mp_err mp_addmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); | |
| 207 mp_err mp_submod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); | |
| 208 mp_err mp_mulmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); | |
| 209 #if MP_SQUARE | |
| 210 mp_err mp_sqrmod(const mp_int *a, const mp_int *m, mp_int *c); | |
| 211 #else | |
| 212 #define mp_sqrmod(a, m, c) mp_mulmod(a, a, m, c) | |
| 213 #endif | |
| 214 mp_err mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); | |
| 215 mp_err mp_exptmod_d(const mp_int *a, mp_digit d, const mp_int *m, mp_int *c); | |
| 216 #endif /* MP_MODARITH */ | |
| 217 | |
| 218 /* Comparisons */ | |
| 219 int mp_cmp_z(const mp_int *a); | |
| 220 int mp_cmp_d(const mp_int *a, mp_digit d); | |
| 221 int mp_cmp(const mp_int *a, const mp_int *b); | |
| 222 int mp_cmp_mag(mp_int *a, mp_int *b); | |
| 223 int mp_cmp_int(const mp_int *a, long z); | |
| 224 int mp_isodd(const mp_int *a); | |
| 225 int mp_iseven(const mp_int *a); | |
| 226 | |
| 227 /* Number theoretic */ | |
| 228 #if MP_NUMTH | |
| 229 mp_err mp_gcd(mp_int *a, mp_int *b, mp_int *c); | |
| 230 mp_err mp_lcm(mp_int *a, mp_int *b, mp_int *c); | |
| 231 mp_err mp_xgcd(const mp_int *a, const mp_int *b, mp_int *g, mp_int *x, mp_int *y); | |
| 232 mp_err mp_invmod(const mp_int *a, const mp_int *m, mp_int *c); | |
| 233 mp_err mp_invmod_xgcd(const mp_int *a, const mp_int *m, mp_int *c); | |
| 234 #endif /* end MP_NUMTH */ | |
| 235 | |
| 236 /* Input and output */ | |
| 237 #if MP_IOFUNC | |
| 238 void mp_print(mp_int *mp, FILE *ofp); | |
| 239 #endif /* end MP_IOFUNC */ | |
| 240 | |
| 241 /* Base conversion */ | |
| 242 mp_err mp_read_raw(mp_int *mp, char *str, int len); | |
| 243 int mp_raw_size(mp_int *mp); | |
| 244 mp_err mp_toraw(mp_int *mp, char *str); | |
| 245 mp_err mp_read_radix(mp_int *mp, const char *str, int radix); | |
| 246 mp_err mp_read_variable_radix(mp_int *a, const char * str, int default_radix); | |
| 247 int mp_radix_size(mp_int *mp, int radix); | |
| 248 mp_err mp_toradix(mp_int *mp, char *str, int radix); | |
| 249 int mp_tovalue(char ch, int r); | |
| 250 | |
| 251 #define mp_tobinary(M, S) mp_toradix((M), (S), 2) | |
| 252 #define mp_tooctal(M, S) mp_toradix((M), (S), 8) | |
| 253 #define mp_todecimal(M, S) mp_toradix((M), (S), 10) | |
| 254 #define mp_tohex(M, S) mp_toradix((M), (S), 16) | |
| 255 | |
| 256 /* Error strings */ | |
| 257 const char *mp_strerror(mp_err ec); | |
| 258 | |
| 259 /* Octet string conversion functions */ | |
| 260 mp_err mp_read_unsigned_octets(mp_int *mp, const unsigned char *str, mp_size len); | |
| 261 int mp_unsigned_octet_size(const mp_int *mp); | |
| 262 mp_err mp_to_unsigned_octets(const mp_int *mp, unsigned char *str, mp_size maxlen); | |
| 263 mp_err mp_to_signed_octets(const mp_int *mp, unsigned char *str, mp_size maxlen); | |
| 264 mp_err mp_to_fixlen_octets(const mp_int *mp, unsigned char *str, mp_size len); | |
| 265 | |
| 266 /* Miscellaneous */ | |
| 267 mp_size mp_trailing_zeros(const mp_int *mp); | |
| 268 void freebl_cpuid(unsigned long op, unsigned long *eax, | |
| 269 unsigned long *ebx, unsigned long *ecx, | |
| 270 unsigned long *edx); | |
| 271 | |
| 272 | |
| 273 #define MP_CHECKOK(x) if (MP_OKAY > (res = (x))) goto CLEANUP | |
| 274 #define MP_CHECKERR(x) if (MP_OKAY > (res = (x))) goto CLEANUP | |
| 275 | |
| 276 #if defined(MP_API_COMPATIBLE) | |
| 277 #define NEG MP_NEG | |
| 278 #define ZPOS MP_ZPOS | |
| 279 #define DIGIT_MAX MP_DIGIT_MAX | |
| 280 #define DIGIT_BIT MP_DIGIT_BIT | |
| 281 #define DIGIT_FMT MP_DIGIT_FMT | |
| 282 #define RADIX MP_RADIX | |
| 283 #define MAX_RADIX MP_MAX_RADIX | |
| 284 #define SIGN(MP) MP_SIGN(MP) | |
| 285 #define USED(MP) MP_USED(MP) | |
| 286 #define ALLOC(MP) MP_ALLOC(MP) | |
| 287 #define DIGITS(MP) MP_DIGITS(MP) | |
| 288 #define DIGIT(MP,N) MP_DIGIT(MP,N) | |
| 289 | |
| 290 #if MP_ARGCHK == 1 | |
| 291 #define ARGCHK(X,Y) {if(!(X)){return (Y);}} | |
| 292 #elif MP_ARGCHK == 2 | |
| 293 #include <assert.h> | |
| 294 #define ARGCHK(X,Y) assert(X) | |
| 295 #else | |
| 296 #define ARGCHK(X,Y) /* */ | |
| 297 #endif | |
| 298 #endif /* defined MP_API_COMPATIBLE */ | |
| 299 | |
| 300 #endif /* end _H_MPI_ */ |
