/* * Copyright 2015 INRIA Paris-Rocquencourt * * Use of this software is governed by the MIT license * * Written by Michael Kruse, INRIA Paris-Rocquencourt, * Domaine de Voluceau, Rocquenqourt, B.P. 105, * 78153 Le Chesnay Cedex France */ #ifndef ISL_INT_SIOIMATH_H #define ISL_INT_SIOIMATH_H #include <inttypes.h> #include <limits.h> #include <stdint.h> #include <stdlib.h> #include <isl_imath.h> #include <isl/hash.h> #define ARRAY_SIZE(array) … /* Visual Studio before VS2015 does not support the inline keyword when * compiling in C mode because it was introduced in C99 which it does not * officially support. Instead, it has a proprietary extension using __inline. */ #if defined(_MSC_VER) && (_MSC_VER < 1900) #define inline __inline #endif /* The type to represent integers optimized for small values. It is either a * pointer to an mp_int ( = mpz_t*; big representation) or an int32_t (small * represenation) with a discriminator at the least significant bit. In big * representation it will be always zero because of heap alignment. It is set * to 1 for small representation and use the 32 most significant bits for the * int32_t. * * Structure on 64 bit machines, with 8-byte aligment (3 bits): * * Big representation: * MSB LSB * |------------------------------------------------------------000 * | mpz_t* | * | != NULL | * * Small representation: * MSB 32 LSB * |------------------------------|00000000000000000000000000000001 * | int32_t | * | 2147483647 ... -2147483647 | * ^ * | * discriminator bit * * On 32 bit machines isl_sioimath type is blown up to 8 bytes, i.e. * isl_sioimath is guaranteed to be at least 8 bytes. This is to ensure the * int32_t can be hidden in that type without data loss. In the future we might * optimize this to use 31 hidden bits in a 32 bit pointer. We may also use 63 * bits on 64 bit machines, but this comes with the cost of additional overflow * checks because there is no standardized 128 bit integer we could expand to. * * We use native integer types and avoid union structures to avoid assumptions * on the machine's endianness. * * This implementation makes the following assumptions: * - long can represent any int32_t * - mp_small is signed long * - mp_usmall is unsigned long * - adresses returned by malloc are aligned to 2-byte boundaries (leastmost * bit is zero) */ #if UINT64_MAX > UINTPTR_MAX typedef uint64_t isl_sioimath; #else isl_sioimath; #endif /* The negation of the smallest possible number in int32_t, INT32_MIN * (0x80000000u, -2147483648), cannot be represented in an int32_t, therefore * every operation that may produce this value needs to special-case it. * The operations are: * abs(INT32_MIN) * -INT32_MIN (negation) * -1 * INT32_MIN (multiplication) * INT32_MIN/-1 (any division: divexact, fdiv, cdiv, tdiv) * To avoid checking these cases, we exclude INT32_MIN from small * representation. */ #define ISL_SIOIMATH_SMALL_MIN … /* Largest possible number in small representation */ #define ISL_SIOIMATH_SMALL_MAX … /* Used for function parameters the function modifies. */ isl_sioimath_ptr; /* Used for function parameters that are read-only. */ isl_sioimath_src; /* Return whether the argument is stored in small representation. */ inline int isl_sioimath_is_small(isl_sioimath val) { … } /* Return whether the argument is stored in big representation. */ inline int isl_sioimath_is_big(isl_sioimath val) { … } /* Get the number of an isl_int in small representation. Result is undefined if * val is not stored in that format. */ inline int32_t isl_sioimath_get_small(isl_sioimath val) { … } /* Get the number of an in isl_int in big representation. Result is undefined if * val is not stored in that format. */ inline mp_int isl_sioimath_get_big(isl_sioimath val) { … } /* Return 1 if val is stored in small representation and store its value to * small. We rely on the compiler to optimize the isl_sioimath_get_small such * that the shift is moved into the branch that executes in case of small * representation. If there is no such branch, then a single shift is still * cheaper than introducing branching code. */ inline int isl_sioimath_decode_small(isl_sioimath val, int32_t *small) { … } /* Return 1 if val is stored in big representation and store its value to big. */ inline int isl_sioimath_decode_big(isl_sioimath val, mp_int *big) { … } /* Encode a small representation into an isl_int. */ inline isl_sioimath isl_sioimath_encode_small(int32_t val) { … } /* Encode a big representation. */ inline isl_sioimath isl_sioimath_encode_big(mp_int val) { … } /* A common situation is to call an IMath function with at least one argument * that is currently in small representation or an integer parameter, i.e. a big * representation of the same number is required. Promoting the original * argument comes with multiple problems, such as modifying a read-only * argument, the responsibility of deallocation and the execution cost. Instead, * we make a copy by 'faking' the IMath internal structure. * * We reserve the maximum number of required digits on the stack to avoid heap * allocations. * * mp_digit can be uint32_t or uint16_t. This code must work for little and big * endian digits. The structure for an uint64_t argument and 32-bit mp_digits is * sketched below. * * |----------------------------| * uint64_t * * |-------------||-------------| * mp_digit mp_digit * digits[1] digits[0] * Most sig digit Least sig digit */ isl_sioimath_scratchspace_t; /* Convert a native integer to IMath's digit representation. A native integer * might be big- or little endian, but IMath always stores the least significant * digit in the lowest array indices. memcpy therefore is not possible. * * We also have to consider that long and mp_digit can be of different sizes, * depending on the compiler (LP64, LLP64) and IMath's USE_64BIT_WORDS. This * macro should work for all of them. * * "used" is set to the number of written digits. It must be minimal (IMath * checks zeroness using the used field), but always at least one. Also note * that the result of num>>(sizeof(num)*CHAR_BIT) is undefined. */ #define ISL_SIOIMATH_TO_DIGITS(num, digits, used) … inline void isl_siomath_uint32_to_digits(uint32_t num, mp_digit *digits, mp_size *used) { … } inline void isl_siomath_ulong_to_digits(unsigned long num, mp_digit *digits, mp_size *used) { … } inline void isl_siomath_uint64_to_digits(uint64_t num, mp_digit *digits, mp_size *used) { … } /* Get the IMath representation of an isl_int without modifying it. * For the case it is not in big representation yet, pass some scratch space we * can use to store the big representation in. * In order to avoid requiring init and free on the scratch space, we directly * modify the internal representation. * * The name derives from its indented use: getting the big representation of an * input (src) argument. */ inline mp_int isl_sioimath_bigarg_src(isl_sioimath arg, isl_sioimath_scratchspace_t *scratch) { … } /* Create a temporary IMath mp_int for a signed long. */ inline mp_int isl_sioimath_siarg_src(signed long arg, isl_sioimath_scratchspace_t *scratch) { … } /* Create a temporary IMath mp_int for an int64_t. */ inline mp_int isl_sioimath_si64arg_src(int64_t arg, isl_sioimath_scratchspace_t *scratch) { … } /* Create a temporary IMath mp_int for an unsigned long. */ inline mp_int isl_sioimath_uiarg_src(unsigned long arg, isl_sioimath_scratchspace_t *scratch) { … } /* Ensure big representation. Does not preserve the current number. * Callers may use the fact that the value _is_ preserved if the presentation * was big before. */ inline mp_int isl_sioimath_reinit_big(isl_sioimath_ptr ptr) { … } /* Set ptr to a number in small representation. */ inline void isl_sioimath_set_small(isl_sioimath_ptr ptr, int32_t val) { … } /* Set ptr to val, choosing small representation if possible. */ inline void isl_sioimath_set_int32(isl_sioimath_ptr ptr, int32_t val) { … } /* Assign an int64_t number using small representation if possible. */ inline void isl_sioimath_set_int64(isl_sioimath_ptr ptr, int64_t val) { … } /* Convert to big representation while preserving the current number. */ inline void isl_sioimath_promote(isl_sioimath_ptr dst) { … } /* Convert to small representation while preserving the current number. Does * nothing if dst doesn't fit small representation. */ inline void isl_sioimath_try_demote(isl_sioimath_ptr dst) { … } /* Initialize an isl_int. The implicit value is 0 in small representation. */ inline void isl_sioimath_init(isl_sioimath_ptr dst) { … } /* Free the resources taken by an isl_int. */ inline void isl_sioimath_clear(isl_sioimath_ptr dst) { … } /* Copy the value of one isl_int to another. */ inline void isl_sioimath_set(isl_sioimath_ptr dst, isl_sioimath_src val) { … } /* Store a signed long into an isl_int. */ inline void isl_sioimath_set_si(isl_sioimath_ptr dst, long val) { … } /* Store an unsigned long into an isl_int. */ inline void isl_sioimath_set_ui(isl_sioimath_ptr dst, unsigned long val) { … } /* Return whether a number can be represented by a signed long. */ inline int isl_sioimath_fits_slong(isl_sioimath_src val) { … } /* Return a number as signed long. Result is undefined if the number cannot be * represented as long. */ inline long isl_sioimath_get_si(isl_sioimath_src val) { … } /* Return whether a number can be represented as unsigned long. */ inline int isl_sioimath_fits_ulong(isl_sioimath_src val) { … } /* Return a number as unsigned long. Result is undefined if the number cannot be * represented as unsigned long. */ inline unsigned long isl_sioimath_get_ui(isl_sioimath_src val) { … } /* Return a number as floating point value. */ inline double isl_sioimath_get_d(isl_sioimath_src val) { … } /* Format a number as decimal string. * * The largest possible string from small representation is 12 characters * ("-2147483647"). */ inline char *isl_sioimath_get_str(isl_sioimath_src val) { … } /* Return the absolute value. */ inline void isl_sioimath_abs(isl_sioimath_ptr dst, isl_sioimath_src arg) { … } /* Return the negation of a number. */ inline void isl_sioimath_neg(isl_sioimath_ptr dst, isl_sioimath_src arg) { … } /* Swap two isl_ints. * * isl_sioimath can be copied bytewise; nothing depends on its address. It can * also be stored in a CPU register. */ inline void isl_sioimath_swap(isl_sioimath_ptr lhs, isl_sioimath_ptr rhs) { … } /* Add an unsigned long to the number. * * On LP64 unsigned long exceeds the range of an int64_t, therefore we check in * advance whether small representation possibly overflows. */ inline void isl_sioimath_add_ui(isl_sioimath_ptr dst, isl_sioimath lhs, unsigned long rhs) { … } /* Subtract an unsigned long. * * On LP64 unsigned long exceeds the range of an int64_t. If * ISL_SIOIMATH_SMALL_MIN-rhs>=INT64_MIN we can do the calculation using int64_t * without risking an overflow. */ inline void isl_sioimath_sub_ui(isl_sioimath_ptr dst, isl_sioimath lhs, unsigned long rhs) { … } /* Sum of two isl_ints. */ inline void isl_sioimath_add(isl_sioimath_ptr dst, isl_sioimath_src lhs, isl_sioimath_src rhs) { … } /* Subtract two isl_ints. */ inline void isl_sioimath_sub(isl_sioimath_ptr dst, isl_sioimath_src lhs, isl_sioimath_src rhs) { … } /* Multiply two isl_ints. */ inline void isl_sioimath_mul(isl_sioimath_ptr dst, isl_sioimath_src lhs, isl_sioimath_src rhs) { … } /* Shift lhs by rhs bits to the left and store the result in dst. Effectively, * this operation computes 'lhs * 2^rhs'. */ inline void isl_sioimath_mul_2exp(isl_sioimath_ptr dst, isl_sioimath lhs, unsigned long rhs) { … } /* Multiply an isl_int and a signed long. */ inline void isl_sioimath_mul_si(isl_sioimath_ptr dst, isl_sioimath lhs, signed long rhs) { … } /* Multiply an isl_int and an unsigned long. */ inline void isl_sioimath_mul_ui(isl_sioimath_ptr dst, isl_sioimath lhs, unsigned long rhs) { … } /* Compute the power of an isl_int to an unsigned long. * Always let IMath do it; the result is unlikely to be small except in some * special cases. * Note: 0^0 == 1 */ inline void isl_sioimath_pow_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, unsigned long rhs) { … } /* Fused multiply-add. */ inline void isl_sioimath_addmul(isl_sioimath_ptr dst, isl_sioimath_src lhs, isl_sioimath_src rhs) { … } /* Fused multiply-add with an unsigned long. */ inline void isl_sioimath_addmul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, unsigned long rhs) { … } /* Fused multiply-subtract. */ inline void isl_sioimath_submul(isl_sioimath_ptr dst, isl_sioimath_src lhs, isl_sioimath_src rhs) { … } /* Fused multiply-add with an unsigned long. */ inline void isl_sioimath_submul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, unsigned long rhs) { … } void isl_sioimath_gcd(isl_sioimath_ptr dst, isl_sioimath_src lhs, isl_sioimath_src rhs); void isl_sioimath_lcm(isl_sioimath_ptr dst, isl_sioimath_src lhs, isl_sioimath_src rhs); /* Divide lhs by rhs, rounding to zero (Truncate). */ inline void isl_sioimath_tdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs, isl_sioimath_src rhs) { … } /* Divide lhs by an unsigned long rhs, rounding to zero (Truncate). */ inline void isl_sioimath_tdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, unsigned long rhs) { … } /* Divide lhs by rhs, rounding to positive infinity (Ceil). */ inline void isl_sioimath_cdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs, isl_sioimath_src rhs) { … } /* Compute the division of lhs by a rhs of type unsigned long, rounding towards * positive infinity (Ceil). */ inline void isl_sioimath_cdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, unsigned long rhs) { … } /* Divide lhs by rhs, rounding to negative infinity (Floor). */ inline void isl_sioimath_fdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs, isl_sioimath_src rhs) { … } /* Compute the division of lhs by a rhs of type unsigned long, rounding towards * negative infinity (Floor). */ inline void isl_sioimath_fdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, unsigned long rhs) { … } /* Get the remainder of: lhs divided by rhs rounded towards negative infinite * (Floor). */ inline void isl_sioimath_fdiv_r(isl_sioimath_ptr dst, isl_sioimath_src lhs, isl_sioimath_src rhs) { … } void isl_sioimath_read(isl_sioimath_ptr dst, const char *str); /* Return: * +1 for a positive number * -1 for a negative number * 0 if the number is zero */ inline int isl_sioimath_sgn(isl_sioimath_src arg) { … } /* Return: * +1 if lhs > rhs * -1 if lhs < rhs * 0 if lhs = rhs */ inline int isl_sioimath_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs) { … } /* As isl_sioimath_cmp, but with signed long rhs. */ inline int isl_sioimath_cmp_si(isl_sioimath_src lhs, signed long rhs) { … } /* Return: * +1 if |lhs| > |rhs| * -1 if |lhs| < |rhs| * 0 if |lhs| = |rhs| */ inline int isl_sioimath_abs_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs) { … } /* Return whether lhs is divisible by rhs. * In particular, can rhs be multiplied by some integer to result in lhs? * If rhs is zero, then this means lhs has to be zero too. */ inline int isl_sioimath_is_divisible_by(isl_sioimath_src lhs, isl_sioimath_src rhs) { … } /* Return a hash code of an isl_sioimath. * The hash code for a number in small and big representation must be identical * on the same machine because small representation if not obligatory if fits. */ inline uint32_t isl_sioimath_hash(isl_sioimath_src arg, uint32_t hash) { … } /* Return the number of digits in a number of the given base or more, i.e. the * string length without sign and null terminator. * * Current implementation for small representation returns the maximal number * of binary digits in that representation, which can be much larger than the * smallest possible solution. */ inline size_t isl_sioimath_sizeinbase(isl_sioimath_src arg, int base) { … } void isl_sioimath_print(FILE *out, isl_sioimath_src i, int width); void isl_sioimath_dump(isl_sioimath_src arg); isl_int; #define isl_int_init(i) … #define isl_int_clear(i) … #define isl_int_set(r, i) … #define isl_int_set_si(r, i) … #define isl_int_set_ui(r, i) … #define isl_int_fits_slong(r) … #define isl_int_get_si(r) … #define isl_int_fits_ulong(r) … #define isl_int_get_ui(r) … #define isl_int_get_d(r) … #define isl_int_get_str(r) … #define isl_int_abs(r, i) … #define isl_int_neg(r, i) … #define isl_int_swap(i, j) … #define isl_int_swap_or_set(i, j) … #define isl_int_add_ui(r, i, j) … #define isl_int_sub_ui(r, i, j) … #define isl_int_add(r, i, j) … #define isl_int_sub(r, i, j) … #define isl_int_mul(r, i, j) … #define isl_int_mul_2exp(r, i, j) … #define isl_int_mul_si(r, i, j) … #define isl_int_mul_ui(r, i, j) … #define isl_int_pow_ui(r, i, j) … #define isl_int_addmul(r, i, j) … #define isl_int_addmul_ui(r, i, j) … #define isl_int_submul(r, i, j) … #define isl_int_submul_ui(r, i, j) … #define isl_int_gcd(r, i, j) … #define isl_int_lcm(r, i, j) … #define isl_int_divexact(r, i, j) … #define isl_int_divexact_ui(r, i, j) … #define isl_int_tdiv_q(r, i, j) … #define isl_int_cdiv_q(r, i, j) … #define isl_int_cdiv_q_ui(r, i, j) … #define isl_int_fdiv_q(r, i, j) … #define isl_int_fdiv_r(r, i, j) … #define isl_int_fdiv_q_ui(r, i, j) … #define isl_int_read(r, s) … #define isl_int_sgn(i) … #define isl_int_cmp(i, j) … #define isl_int_cmp_si(i, si) … #define isl_int_eq(i, j) … #define isl_int_ne(i, j) … #define isl_int_lt(i, j) … #define isl_int_le(i, j) … #define isl_int_gt(i, j) … #define isl_int_ge(i, j) … #define isl_int_abs_cmp(i, j) … #define isl_int_abs_eq(i, j) … #define isl_int_abs_ne(i, j) … #define isl_int_abs_lt(i, j) … #define isl_int_abs_gt(i, j) … #define isl_int_abs_ge(i, j) … #define isl_int_is_divisible_by(i, j) … #define isl_int_hash(v, h) … #define isl_int_free_str(s) … #define isl_int_print(out, i, width) … #endif /* ISL_INT_SIOIMATH_H */
Codebase Browser
llvm