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