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