1 /* 2 Name: imath.h 3 Purpose: Arbitrary precision integer arithmetic routines. 4 Author: M. J. Fromberger <http://spinning-yarns.org/michael/> 5 6 Copyright (C) 2002-2007 Michael J. Fromberger, All Rights Reserved. 7 8 Permission is hereby granted, free of charge, to any person obtaining a copy 9 of this software and associated documentation files (the "Software"), to deal 10 in the Software without restriction, including without limitation the rights 11 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 12 copies of the Software, and to permit persons to whom the Software is 13 furnished to do so, subject to the following conditions: 14 15 The above copyright notice and this permission notice shall be included in 16 all copies or substantial portions of the Software. 17 18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 21 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 22 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 23 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 24 SOFTWARE. 25 */ 26 27 #ifndef IMATH_H_ 28 #define IMATH_H_ 29 30 #include <stdint.h> 31 #include <limits.h> 32 33 #ifdef __cplusplus 34 extern "C" { 35 #endif 36 37 typedef unsigned char mp_sign; 38 typedef unsigned int mp_size; 39 typedef int mp_result; 40 typedef long mp_small; /* must be a signed type */ 41 typedef unsigned long mp_usmall; /* must be an unsigned type */ 42 43 /* Force building with uint64_t so that the library builds consistently 44 * whether we build from the makefile or by embedding imath in another project. 45 */ 46 #undef USE_64BIT_WORDS 47 #define USE_64BIT_WORDS 48 #ifdef USE_64BIT_WORDS 49 typedef uint32_t mp_digit; 50 typedef uint64_t mp_word; 51 #else 52 typedef uint16_t mp_digit; 53 typedef uint32_t mp_word; 54 #endif 55 56 typedef struct mpz { 57 mp_digit single; 58 mp_digit *digits; 59 mp_size alloc; 60 mp_size used; 61 mp_sign sign; 62 } mpz_t, *mp_int; 63 64 #define MP_DIGITS(Z) ((Z)->digits) 65 #define MP_ALLOC(Z) ((Z)->alloc) 66 #define MP_USED(Z) ((Z)->used) 67 #define MP_SIGN(Z) ((Z)->sign) 68 69 extern const mp_result MP_OK; 70 extern const mp_result MP_FALSE; 71 extern const mp_result MP_TRUE; 72 extern const mp_result MP_MEMORY; 73 extern const mp_result MP_RANGE; 74 extern const mp_result MP_UNDEF; 75 extern const mp_result MP_TRUNC; 76 extern const mp_result MP_BADARG; 77 extern const mp_result MP_MINERR; 78 79 #define MP_DIGIT_BIT (sizeof(mp_digit) * CHAR_BIT) 80 #define MP_WORD_BIT (sizeof(mp_word) * CHAR_BIT) 81 #define MP_SMALL_MIN LONG_MIN 82 #define MP_SMALL_MAX LONG_MAX 83 #define MP_USMALL_MIN ULONG_MIN 84 #define MP_USMALL_MAX ULONG_MAX 85 86 #ifdef USE_64BIT_WORDS 87 # define MP_DIGIT_MAX (UINT32_MAX * UINT64_C(1)) 88 # define MP_WORD_MAX (UINT64_MAX) 89 #else 90 # define MP_DIGIT_MAX (UINT16_MAX * 1UL) 91 # define MP_WORD_MAX (UINT32_MAX * 1UL) 92 #endif 93 94 #define MP_MIN_RADIX 2 95 #define MP_MAX_RADIX 36 96 97 /* Values with fewer than this many significant digits use the standard 98 multiplication algorithm; otherwise, a recursive algorithm is used. 99 Choose a value to suit your platform. 100 */ 101 #define MP_MULT_THRESH 22 102 103 #define MP_DEFAULT_PREC 8 /* default memory allocation, in digits */ 104 105 extern const mp_sign MP_NEG; 106 extern const mp_sign MP_ZPOS; 107 108 #define mp_int_is_odd(Z) ((Z)->digits[0] & 1) 109 #define mp_int_is_even(Z) !((Z)->digits[0] & 1) 110 111 mp_result mp_int_init(mp_int z); 112 mp_int mp_int_alloc(void); 113 mp_result mp_int_init_size(mp_int z, mp_size prec); 114 mp_result mp_int_init_copy(mp_int z, mp_int old); 115 mp_result mp_int_init_value(mp_int z, mp_small value); 116 mp_result mp_int_init_uvalue(mp_int z, mp_usmall uvalue); 117 mp_result mp_int_set_value(mp_int z, mp_small value); 118 mp_result mp_int_set_uvalue(mp_int z, mp_usmall uvalue); 119 void mp_int_clear(mp_int z); 120 void mp_int_free(mp_int z); 121 122 mp_result mp_int_copy(mp_int a, mp_int c); /* c = a */ 123 void mp_int_swap(mp_int a, mp_int c); /* swap a, c */ 124 void mp_int_zero(mp_int z); /* z = 0 */ 125 mp_result mp_int_abs(mp_int a, mp_int c); /* c = |a| */ 126 mp_result mp_int_neg(mp_int a, mp_int c); /* c = -a */ 127 mp_result mp_int_add(mp_int a, mp_int b, mp_int c); /* c = a + b */ 128 mp_result mp_int_add_value(mp_int a, mp_small value, mp_int c); 129 mp_result mp_int_sub(mp_int a, mp_int b, mp_int c); /* c = a - b */ 130 mp_result mp_int_sub_value(mp_int a, mp_small value, mp_int c); 131 mp_result mp_int_mul(mp_int a, mp_int b, mp_int c); /* c = a * b */ 132 mp_result mp_int_mul_value(mp_int a, mp_small value, mp_int c); 133 mp_result mp_int_mul_pow2(mp_int a, mp_small p2, mp_int c); 134 mp_result mp_int_sqr(mp_int a, mp_int c); /* c = a * a */ 135 mp_result mp_int_div(mp_int a, mp_int b, /* q = a / b */ 136 mp_int q, mp_int r); /* r = a % b */ 137 mp_result mp_int_div_value(mp_int a, mp_small value, /* q = a / value */ 138 mp_int q, mp_small *r); /* r = a % value */ 139 mp_result mp_int_div_pow2(mp_int a, mp_small p2, /* q = a / 2^p2 */ 140 mp_int q, mp_int r); /* r = q % 2^p2 */ 141 mp_result mp_int_mod(mp_int a, mp_int m, mp_int c); /* c = a % m */ 142 #define mp_int_mod_value(A, V, R) mp_int_div_value((A), (V), 0, (R)) 143 mp_result mp_int_expt(mp_int a, mp_small b, mp_int c); /* c = a^b */ 144 mp_result mp_int_expt_value(mp_small a, mp_small b, mp_int c); /* c = a^b */ 145 mp_result mp_int_expt_full(mp_int a, mp_int b, mp_int c); /* c = a^b */ 146 147 int mp_int_compare(mp_int a, mp_int b); /* a <=> b */ 148 int mp_int_compare_unsigned(mp_int a, mp_int b); /* |a| <=> |b| */ 149 int mp_int_compare_zero(mp_int z); /* a <=> 0 */ 150 int mp_int_compare_value(mp_int z, mp_small v); /* a <=> v */ 151 int mp_int_compare_uvalue(mp_int z, mp_usmall uv); /* a <=> uv */ 152 153 /* Returns true if v|a, false otherwise (including errors) */ 154 int mp_int_divisible_value(mp_int a, mp_small v); 155 156 /* Returns k >= 0 such that z = 2^k, if one exists; otherwise < 0 */ 157 int mp_int_is_pow2(mp_int z); 158 159 mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, 160 mp_int c); /* c = a^b (mod m) */ 161 mp_result mp_int_exptmod_evalue(mp_int a, mp_small value, 162 mp_int m, mp_int c); /* c = a^v (mod m) */ 163 mp_result mp_int_exptmod_bvalue(mp_small value, mp_int b, 164 mp_int m, mp_int c); /* c = v^b (mod m) */ 165 mp_result mp_int_exptmod_known(mp_int a, mp_int b, 166 mp_int m, mp_int mu, 167 mp_int c); /* c = a^b (mod m) */ 168 mp_result mp_int_redux_const(mp_int m, mp_int c); 169 170 mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c); /* c = 1/a (mod m) */ 171 172 mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c); /* c = gcd(a, b) */ 173 174 mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, /* c = gcd(a, b) */ 175 mp_int x, mp_int y); /* c = ax + by */ 176 177 mp_result mp_int_lcm(mp_int a, mp_int b, mp_int c); /* c = lcm(a, b) */ 178 179 mp_result mp_int_root(mp_int a, mp_small b, mp_int c); /* c = floor(a^{1/b}) */ 180 #define mp_int_sqrt(a, c) mp_int_root(a, 2, c) /* c = floor(sqrt(a)) */ 181 182 /* Convert to a small int, if representable; else MP_RANGE */ 183 mp_result mp_int_to_int(mp_int z, mp_small *out); 184 mp_result mp_int_to_uint(mp_int z, mp_usmall *out); 185 186 /* Convert to nul-terminated string with the specified radix, writing at 187 most limit characters including the nul terminator */ 188 mp_result mp_int_to_string(mp_int z, mp_size radix, 189 char *str, int limit); 190 191 /* Return the number of characters required to represent 192 z in the given radix. May over-estimate. */ 193 mp_result mp_int_string_len(mp_int z, mp_size radix); 194 195 /* Read zero-terminated string into z */ 196 mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str); 197 mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str, 198 char **end); 199 200 /* Return the number of significant bits in z */ 201 mp_result mp_int_count_bits(mp_int z); 202 203 /* Convert z to two's complement binary, writing at most limit bytes */ 204 mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit); 205 206 /* Read a two's complement binary value into z from the given buffer */ 207 mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len); 208 209 /* Return the number of bytes required to represent z in binary. */ 210 mp_result mp_int_binary_len(mp_int z); 211 212 /* Convert z to unsigned binary, writing at most limit bytes */ 213 mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit); 214 215 /* Read an unsigned binary value into z from the given buffer */ 216 mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len); 217 218 /* Return the number of bytes required to represent z as unsigned output */ 219 mp_result mp_int_unsigned_len(mp_int z); 220 221 /* Return a statically allocated string describing error code res */ 222 const char *mp_error_string(mp_result res); 223 224 #if DEBUG 225 void s_print(char *tag, mp_int z); 226 void s_print_buf(char *tag, mp_digit *buf, mp_size num); 227 #endif 228 229 #ifdef __cplusplus 230 } 231 #endif 232 #endif /* end IMATH_H_ */ 233