| File: | tools/polly/lib/External/isl/imath/imath.h |
| Warning: | line 56, column 16 Excessive padding in 'struct mpz' (11 padding bytes, where 3 is optimal). Optimal fields order: digits, single, alloc, used, sign, consider reordering the fields or adding explicit padding members |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 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 { |
Excessive padding in 'struct mpz' (11 padding bytes, where 3 is optimal).
Optimal fields order:
digits,
single,
alloc,
used,
sign,
consider reordering the fields or adding explicit padding members | |
| 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) ((Z)->digits) |
| 65 | #define MP_ALLOC(Z)((Z)->alloc) ((Z)->alloc) |
| 66 | #define MP_USED(Z)((Z)->used) ((Z)->used) |
| 67 | #define MP_SIGN(Z)((Z)->sign) ((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) * 8) (sizeof(mp_digit) * CHAR_BIT8) |
| 80 | #define MP_WORD_BIT(sizeof(mp_word) * 8) (sizeof(mp_word) * CHAR_BIT8) |
| 81 | #define MP_SMALL_MIN(-9223372036854775807L -1L) LONG_MIN(-9223372036854775807L -1L) |
| 82 | #define MP_SMALL_MAX9223372036854775807L LONG_MAX9223372036854775807L |
| 83 | #define MP_USMALL_MINULONG_MIN ULONG_MIN |
| 84 | #define MP_USMALL_MAX(9223372036854775807L *2UL+1UL) ULONG_MAX(9223372036854775807L *2UL+1UL) |
| 85 | |
| 86 | #ifdef USE_64BIT_WORDS |
| 87 | # define MP_DIGIT_MAX((4294967295U) * 1UL) (UINT32_MAX(4294967295U) * UINT64_C(1)1UL) |
| 88 | # define MP_WORD_MAX((18446744073709551615UL)) (UINT64_MAX(18446744073709551615UL)) |
| 89 | #else |
| 90 | # define MP_DIGIT_MAX((4294967295U) * 1UL) (UINT16_MAX(65535) * 1UL) |
| 91 | # define MP_WORD_MAX((18446744073709551615UL)) (UINT32_MAX(4294967295U) * 1UL) |
| 92 | #endif |
| 93 | |
| 94 | #define MP_MIN_RADIX2 2 |
| 95 | #define MP_MAX_RADIX36 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_THRESH22 22 |
| 102 | |
| 103 | #define MP_DEFAULT_PREC8 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) ((Z)->digits[0] & 1) |
| 109 | #define mp_int_is_even(Z)!((Z)->digits[0] & 1) !((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)) 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) 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_ */ |