/build/source/polly/lib/External/isl/imath/imath.c

Bug Summary

File:	build/source/polly/lib/External/isl/imath/imath.c
Warning:	line 1145, column 3 Potential leak of memory pointed to by field 'digits'
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name imath.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=../../../../ -fdebug-prefix-map=/build/source/= -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-19/lib/clang/19 -I tools/polly/lib/External -I /build/source/polly/lib/External -I /build/source/polly/lib/External/isl -I /build/source/polly/lib/External/isl/include -I /build/source/polly/lib/External/isl/imath -I tools/polly/lib/External/isl -I tools/polly/include -I /build/source/polly/lib/External/pet/include -I tools/polly/lib/External/isl/include -I /build/source/polly/include -I include -I /build/source/llvm/include -D _DEBUG -D _GLIBCXX_ASSERTIONS -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/llvm-19/lib/clang/19/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=../../../../ -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=../../../../ -fcoverage-prefix-map=/build/source/= -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=gnu99 -fconst-strings -ferror-limit 19 -stack-protector 2 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2024-04-02-020108-72015-1 -x c /build/source/polly/lib/External/isl/imath/imath.c
1/*
Name:     imath.c
Purpose:  Arbitrary precision integer arithmetic routines.
Author:   M. J. Fromberger

Copyright (C) 2002-2007 Michael J. Fromberger, All Rights Reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/

27#include "imath.h"

29#include <assert.h>
30#include <ctype.h>
31#include <stdlib.h>
32#include <string.h>

34const mp_result MP_OK = 0;      /* no error, all is well  */
35const mp_result MP_FALSE = 0;   /* boolean false          */
36const mp_result MP_TRUE = -1;   /* boolean true           */
37const mp_result MP_MEMORY = -2; /* out of memory          */
38const mp_result MP_RANGE = -3;  /* argument out of range  */
39const mp_result MP_UNDEF = -4;  /* result undefined       */
40const mp_result MP_TRUNC = -5;  /* output truncated       */
41const mp_result MP_BADARG = -6; /* invalid null argument  */
42const mp_result MP_MINERR = -6;

44const mp_sign MP_NEG = 1;  /* value is strictly negative */
45const mp_sign MP_ZPOS = 0; /* value is non-negative      */

47static const char *s_unknown_err = "unknown result code";
48static const char *s_error_msg[] = {"error code 0",     "boolean true",
                                  "out of memory",    "argument out of range",
                                  "result undefined", "output truncated",
                                  "invalid argument", NULL((void*)0)};

53/* The ith entry of this table gives the value of log_i(2).

 An integer value n requires ceil(log_i(n)) digits to be represented
 in base i.  Since it is easy to compute lg(n), by counting bits, we
 can compute log_i(n) = lg(n) * log_i(2).

 The use of this table eliminates a dependency upon linkage against
 the standard math libraries.

 If MP_MAX_RADIX is increased, this table should be expanded too.
*/
64static const double s_log2[] = {
  0.000000000, 0.000000000, 1.000000000, 0.630929754, /* (D)(D) 2  3 */
  0.500000000, 0.430676558, 0.386852807, 0.356207187, /*  4  5  6  7 */
  0.333333333, 0.315464877, 0.301029996, 0.289064826, /*  8  9 10 11 */
  0.278942946, 0.270238154, 0.262649535, 0.255958025, /* 12 13 14 15 */
  0.250000000, 0.244650542, 0.239812467, 0.235408913, /* 16 17 18 19 */
  0.231378213, 0.227670249, 0.224243824, 0.221064729, /* 20 21 22 23 */
  0.218104292, 0.215338279, 0.212746054, 0.210309918, /* 24 25 26 27 */
  0.208014598, 0.205846832, 0.203795047, 0.201849087, /* 28 29 30 31 */
  0.200000000, 0.198239863, 0.196561632, 0.194959022, /* 32 33 34 35 */
  0.193426404,                                        /* 36          */
75};

77/* Return the number of digits needed to represent a static value */
78#define MP_VALUE_DIGITS(V)((sizeof(V) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit)) \
((sizeof(V) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit))

81/* Round precision P to nearest word boundary */
82static inline mp_size s_round_prec(mp_size P) { return 2 * ((P + 1) / 2); }

84/* Set array P of S digits to zero */
85static inline void ZERO(mp_digit *P, mp_size S) {
mp_size i__ = S * sizeof(mp_digit);
mp_digit *p__ = P;
memset(p__, 0, i__);
89}

91/* Copy S digits from array P to array Q */
92static inline void COPY(mp_digit *P, mp_digit *Q, mp_size S) {
mp_size i__ = S * sizeof(mp_digit);
mp_digit *p__ = P;
mp_digit *q__ = Q;
memcpy(q__, p__, i__);
97}

99/* Reverse N elements of unsigned char in A. */
100static inline void REV(unsigned char *A, int N) {
unsigned char *u_ = A;
unsigned char *v_ = u_ + N - 1;
while (u_ < v_) {
  unsigned char xch = *u_;
  *u_++ = *v_;
  *v_-- = xch;
}
108}

110/* Strip leading zeroes from z_ in-place. */
111static inline void CLAMP(mp_int z_) {
mp_size uz_ = MP_USED(z_);
mp_digit *dz_ = MP_DIGITS(z_) + uz_ - 1;
while (uz_ > 1 && (*dz_-- == 0)) --uz_;
z_->used = uz_;
116}

118/* Select min/max. */
119static inline int MIN(int A, int B) { return (B < A ? B : A); }
120static inline mp_size MAX(mp_size A, mp_size B) { return (B > A ? B : A); }

122/* Exchange lvalues A and B of type T, e.g.
 SWAP(int, x, y) where x and y are variables of type int. */
124#define SWAP(T, A, B)do { T t_ = (A); A = (B); B = t_; } while (0) \
do {                \
  T t_ = (A);       \
  A = (B);          \
  B = t_;           \
} while (0)

131/* Declare a block of N temporary mpz_t values.
 These values are initialized to zero.
 You must add CLEANUP_TEMP() at the end of the function.
 Use TEMP(i) to access a pointer to the ith value.
*/
136#define DECLARE_TEMP(N)struct { mpz_t value[(N)]; int len; mp_result err; } temp_ = {
 .len = (N), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0)                   \
struct {                                \
  mpz_t value[(N)];                     \
  int len;                              \
  mp_result err;                        \
} temp_ = {                             \
    .len = (N),                         \
    .err = MP_OK,                       \
};                                      \
do {                                    \
  for (int i = 0; i < temp_.len; i++) { \
    mp_int_init(TEMP(i)(temp_.value + (i)));               \
  }                                     \
} while (0)

151/* Clear all allocated temp values. */
152#define CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0)                    \
CLEANUP:                                \
do {                                    \
  for (int i = 0; i < temp_.len; i++) { \
    mp_int_clear(TEMP(i)(temp_.value + (i)));              \
  }                                     \
  if (temp_.err != MP_OK) {             \
    return temp_.err;                   \
  }                                     \
} while (0)

163/* A pointer to the kth temp value. */
164#define TEMP(K)(temp_.value + (K)) (temp_.value + (K))

166/* Evaluate E, an expression of type mp_result expected to return MP_OK.  If
 the value is not MP_OK, the error is cached and control resumes at the
 cleanup handler, which returns it.
169*/
170#define REQUIRE(E)do { temp_.err = (E); if (temp_.err != MP_OK) goto CLEANUP; }
 while (0)                        \
do {                                    \
  temp_.err = (E);                      \
  if (temp_.err != MP_OK) goto CLEANUP; \
} while (0)

176/* Compare value to zero. */
177static inline int CMPZ(mp_int Z) {
if (Z->used == 1 && Z->digits[0] == 0) return 0;
return (Z->sign == MP_NEG) ? -1 : 1;
180}

182static inline mp_word UPPER_HALF(mp_word W) { return (W >> MP_DIGIT_BIT(sizeof(mp_digit) * 8)); }
183static inline mp_digit LOWER_HALF(mp_word W) { return (mp_digit)(W); }

185/* Report whether the highest-order bit of W is 1. */
186static inline bool_Bool HIGH_BIT_SET(mp_word W) {
return (W >> (MP_WORD_BIT(sizeof(mp_word) * 8) - 1)) != 0;
188}

190/* Report whether adding W + V will carry out. */
191static inline bool_Bool ADD_WILL_OVERFLOW(mp_word W, mp_word V) {
return ((MP_WORD_MAX((18446744073709551615UL)) - V) < W);
193}

195/* Default number of digits allocated to a new mp_int */
196static mp_size default_precision = 8;

198void mp_int_default_precision(mp_size size) {
assert(size > 0)((void) sizeof ((size > 0) ? 1 : 0), __extension__ ({ if (
size > 0) ; else __assert_fail ("size > 0", "polly/lib/External/isl/imath/imath.c"
, 199, __extension__ __PRETTY_FUNCTION__); }));
default_precision = size;
201}

203/* Minimum number of digits to invoke recursive multiply */
204static mp_size multiply_threshold = 32;

206void mp_int_multiply_threshold(mp_size thresh) {
assert(thresh >= sizeof(mp_word))((void) sizeof ((thresh >= sizeof(mp_word)) ? 1 : 0), __extension__
 ({ if (thresh >= sizeof(mp_word)) ; else __assert_fail ("thresh >= sizeof(mp_word)"
, "polly/lib/External/isl/imath/imath.c", 207, __extension__ __PRETTY_FUNCTION__
); }));
multiply_threshold = thresh;
209}

211/* Allocate a buffer of (at least) num digits, or return
 NULL if that couldn't be done.  */
213static mp_digit *s_alloc(mp_size num);

215/* Release a buffer of digits allocated by s_alloc(). */
216static void s_free(void *ptr);

218/* Insure that z has at least min digits allocated, resizing if
 necessary.  Returns true if successful, false if out of memory. */
220static bool_Bool s_pad(mp_int z, mp_size min);

222/* Ensure Z has at least N digits allocated. */
223static inline mp_result GROW(mp_int Z, mp_size N) {
return s_pad(Z, N) ? MP_OK : MP_MEMORY;
225}

227/* Fill in a "fake" mp_int on the stack with a given value */
228static void s_fake(mp_int z, mp_small value, mp_digit vbuf[]);
229static void s_ufake(mp_int z, mp_usmall value, mp_digit vbuf[]);

231/* Compare two runs of digits of given length, returns <0, 0, >0 */
232static int s_cdig(mp_digit *da, mp_digit *db, mp_size len);

234/* Pack the unsigned digits of v into array t */
235static int s_uvpack(mp_usmall v, mp_digit t[]);

237/* Compare magnitudes of a and b, returns <0, 0, >0 */
238static int s_ucmp(mp_int a, mp_int b);

240/* Compare magnitudes of a and v, returns <0, 0, >0 */
241static int s_vcmp(mp_int a, mp_small v);
242static int s_uvcmp(mp_int a, mp_usmall uv);

244/* Unsigned magnitude addition; assumes dc is big enough.
 Carry out is returned (no memory allocated). */
246static mp_digit s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a,
                     mp_size size_b);

249/* Unsigned magnitude subtraction.  Assumes dc is big enough. */
250static void s_usub(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a,
                 mp_size size_b);

253/* Unsigned recursive multiplication.  Assumes dc is big enough. */
254static int s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a,
                mp_size size_b);

257/* Unsigned magnitude multiplication.  Assumes dc is big enough. */
258static void s_umul(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a,
                 mp_size size_b);

261/* Unsigned recursive squaring.  Assumes dc is big enough. */
262static int s_ksqr(mp_digit *da, mp_digit *dc, mp_size size_a);

264/* Unsigned magnitude squaring.  Assumes dc is big enough. */
265static void s_usqr(mp_digit *da, mp_digit *dc, mp_size size_a);

267/* Single digit addition.  Assumes a is big enough. */
268static void s_dadd(mp_int a, mp_digit b);

270/* Single digit multiplication.  Assumes a is big enough. */
271static void s_dmul(mp_int a, mp_digit b);

273/* Single digit multiplication on buffers; assumes dc is big enough. */
274static void s_dbmul(mp_digit *da, mp_digit b, mp_digit *dc, mp_size size_a);

276/* Single digit division.  Replaces a with the quotient,
 returns the remainder.  */
278static mp_digit s_ddiv(mp_int a, mp_digit b);

280/* Quick division by a power of 2, replaces z (no allocation) */
281static void s_qdiv(mp_int z, mp_size p2);

283/* Quick remainder by a power of 2, replaces z (no allocation) */
284static void s_qmod(mp_int z, mp_size p2);

286/* Quick multiplication by a power of 2, replaces z.
 Allocates if necessary; returns false in case this fails. */
288static int s_qmul(mp_int z, mp_size p2);

290/* Quick subtraction from a power of 2, replaces z.
 Allocates if necessary; returns false in case this fails. */
292static int s_qsub(mp_int z, mp_size p2);

294/* Return maximum k such that 2^k divides z. */
295static int s_dp2k(mp_int z);

297/* Return k >= 0 such that z = 2^k, or -1 if there is no such k. */
298static int s_isp2(mp_int z);

300/* Set z to 2^k.  May allocate; returns false in case this fails. */
301static int s_2expt(mp_int z, mp_small k);

303/* Normalize a and b for division, returns normalization constant */
304static int s_norm(mp_int a, mp_int b);

306/* Compute constant mu for Barrett reduction, given modulus m, result
 replaces z, m is untouched. */
308static mp_result s_brmu(mp_int z, mp_int m);

310/* Reduce a modulo m, using Barrett's algorithm. */
311static int s_reduce(mp_int x, mp_int m, mp_int mu, mp_int q1, mp_int q2);

313/* Modular exponentiation, using Barrett reduction */
314static mp_result s_embar(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c);

316/* Unsigned magnitude division.  Assumes |a| > |b|.  Allocates temporaries;
 overwrites a with quotient, b with remainder. */
318static mp_result s_udiv_knuth(mp_int a, mp_int b);

320/* Compute the number of digits in radix r required to represent the given
 value.  Does not account for sign flags, terminators, etc. */
322static int s_outlen(mp_int z, mp_size r);

324/* Guess how many digits of precision will be needed to represent a radix r
 value of the specified number of digits.  Returns a value guaranteed to be
 no smaller than the actual number required. */
327static mp_size s_inlen(int len, mp_size r);

329/* Convert a character to a digit value in radix r, or
 -1 if out of range */
331static int s_ch2val(char c, int r);

333/* Convert a digit value to a character */
334static char s_val2ch(int v, int caps);

336/* Take 2's complement of a buffer in place */
337static void s_2comp(unsigned char *buf, int len);

339/* Convert a value to binary, ignoring sign.  On input, *limpos is the bound on
 how many bytes should be written to buf; on output, *limpos is set to the
 number of bytes actually written. */
342static mp_result s_tobin(mp_int z, unsigned char *buf, int *limpos, int pad);

344/* Multiply X by Y into Z, ignoring signs.  Requires that Z have enough storage
 preallocated to hold the result. */
346static inline void UMUL(mp_int X, mp_int Y, mp_int Z) {
mp_size ua_ = MP_USED(X);
mp_size ub_ = MP_USED(Y);
mp_size o_ = ua_ + ub_;
ZERO(MP_DIGITS(Z), o_);
(void)s_kmul(MP_DIGITS(X), MP_DIGITS(Y), MP_DIGITS(Z), ua_, ub_);
Z->used = o_;
CLAMP(Z);
354}

356/* Square X into Z.  Requires that Z have enough storage to hold the result. */
357static inline void USQR(mp_int X, mp_int Z) {
mp_size ua_ = MP_USED(X);
mp_size o_ = ua_ + ua_;
ZERO(MP_DIGITS(Z), o_);
(void)s_ksqr(MP_DIGITS(X), MP_DIGITS(Z), ua_);
Z->used = o_;
CLAMP(Z);
364}

366mp_result mp_int_init(mp_int z) {
if (z == NULL((void*)0)) return MP_BADARG;

z->single = 0;
z->digits = &(z->single);
z->alloc = 1;
z->used = 1;
z->sign = MP_ZPOS;

return MP_OK;
376}

378mp_int mp_int_alloc(void) {
mp_int out = malloc(sizeof(mpz_t));

if (out != NULL((void*)0)) mp_int_init(out);

return out;
384}

386mp_result mp_int_init_size(mp_int z, mp_size prec) {
assert(z != NULL)((void) sizeof ((z != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (z != ((void*)0)) ; else __assert_fail ("z != NULL", "polly/lib/External/isl/imath/imath.c"
, 387, __extension__ __PRETTY_FUNCTION__); }));

if (prec == 0) {
  prec = default_precision;
} else if (prec == 1) {
  return mp_int_init(z);
} else {
  prec = s_round_prec(prec);
}

z->digits = s_alloc(prec);
if (MP_DIGITS(z) == NULL((void*)0)) return MP_MEMORY;

z->digits[0] = 0;
z->used = 1;
z->alloc = prec;
z->sign = MP_ZPOS;

return MP_OK;
406}

408mp_result mp_int_init_copy(mp_int z, mp_int old) {
assert(z != NULL && old != NULL)((void) sizeof ((z != ((void*)0) && old != ((void*)0)
) ? 1 : 0), __extension__ ({ if (z != ((void*)0) && old
 != ((void*)0)) ; else __assert_fail ("z != NULL && old != NULL"
, "polly/lib/External/isl/imath/imath.c", 409, __extension__ __PRETTY_FUNCTION__
); }));

mp_size uold = MP_USED(old);
if (uold == 1) {
  mp_int_init(z);
} else {
  mp_size target = MAX(uold, default_precision);
  mp_result res = mp_int_init_size(z, target);
  if (res != MP_OK) return res;
}

z->used = uold;
z->sign = old->sign;
COPY(MP_DIGITS(old), MP_DIGITS(z), uold);

return MP_OK;
425}

427mp_result mp_int_init_value(mp_int z, mp_small value) {
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit))];

s_fake(&vtmp, value, vbuf);
return mp_int_init_copy(z, &vtmp);
433}

435mp_result mp_int_init_uvalue(mp_int z, mp_usmall uvalue) {
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(uvalue)((sizeof(uvalue) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit)
)];

s_ufake(&vtmp, uvalue, vbuf);
return mp_int_init_copy(z, &vtmp);
441}

443mp_result mp_int_set_value(mp_int z, mp_small value) {
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit))];

s_fake(&vtmp, value, vbuf);
return mp_int_copy(&vtmp, z);
449}

451mp_result mp_int_set_uvalue(mp_int z, mp_usmall uvalue) {
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(uvalue)((sizeof(uvalue) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit)
)];

s_ufake(&vtmp, uvalue, vbuf);
return mp_int_copy(&vtmp, z);
457}

459void mp_int_clear(mp_int z) {
if (z == NULL((void*)0)) return;

if (MP_DIGITS(z) != NULL((void*)0)) {
  if (MP_DIGITS(z) != &(z->single)) s_free(MP_DIGITS(z));

  z->digits = NULL((void*)0);
}
467}

469void mp_int_free(mp_int z) {
assert(z != NULL)((void) sizeof ((z != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (z != ((void*)0)) ; else __assert_fail ("z != NULL", "polly/lib/External/isl/imath/imath.c"
, 470, __extension__ __PRETTY_FUNCTION__); }));

mp_int_clear(z);
free(z); /* note: NOT s_free() */
474}

476mp_result mp_int_copy(mp_int a, mp_int c) {
assert(a != NULL && c != NULL)((void) sizeof ((a != ((void*)0) && c != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && c !=
 ((void*)0)) ; else __assert_fail ("a != NULL && c != NULL"
, "polly/lib/External/isl/imath/imath.c", 477, __extension__ __PRETTY_FUNCTION__
); }));

if (a != c) {
  mp_size ua = MP_USED(a);
  mp_digit *da, *dc;

  if (!s_pad(c, ua)) return MP_MEMORY;

  da = MP_DIGITS(a);
  dc = MP_DIGITS(c);
  COPY(da, dc, ua);

  c->used = ua;
  c->sign = a->sign;
}

return MP_OK;
494}

496void mp_int_swap(mp_int a, mp_int c) {
if (a != c) {
  mpz_t tmp = *a;

  *a = *c;
  *c = tmp;

  if (MP_DIGITS(a) == &(c->single)) a->digits = &(a->single);
  if (MP_DIGITS(c) == &(a->single)) c->digits = &(c->single);
}
506}

508void mp_int_zero(mp_int z) {
assert(z != NULL)((void) sizeof ((z != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (z != ((void*)0)) ; else __assert_fail ("z != NULL", "polly/lib/External/isl/imath/imath.c"
, 509, __extension__ __PRETTY_FUNCTION__); }));

z->digits[0] = 0;
z->used = 1;
z->sign = MP_ZPOS;
514}

516mp_result mp_int_abs(mp_int a, mp_int c) {
assert(a != NULL && c != NULL)((void) sizeof ((a != ((void*)0) && c != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && c !=
 ((void*)0)) ; else __assert_fail ("a != NULL && c != NULL"
, "polly/lib/External/isl/imath/imath.c", 517, __extension__ __PRETTY_FUNCTION__
); }));

mp_result res;
if ((res = mp_int_copy(a, c)) != MP_OK) return res;

c->sign = MP_ZPOS;
return MP_OK;
524}

526mp_result mp_int_neg(mp_int a, mp_int c) {
assert(a != NULL && c != NULL)((void) sizeof ((a != ((void*)0) && c != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && c !=
 ((void*)0)) ; else __assert_fail ("a != NULL && c != NULL"
, "polly/lib/External/isl/imath/imath.c", 527, __extension__ __PRETTY_FUNCTION__
); }));

mp_result res;
if ((res = mp_int_copy(a, c)) != MP_OK) return res;

if (CMPZ(c) != 0) c->sign = 1 - MP_SIGN(a);

return MP_OK;
535}

537mp_result mp_int_add(mp_int a, mp_int b, mp_int c) {
assert(a != NULL && b != NULL && c != NULL)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && b != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != NULL && b != NULL && c != NULL"
, "polly/lib/External/isl/imath/imath.c", 538, __extension__ __PRETTY_FUNCTION__
); }));
24
←
Taking true branch→

mp_size ua = MP_USED(a);
mp_size ub = MP_USED(b);
mp_size max = MAX(ua, ub);

if (MP_SIGN(a) == MP_SIGN(b)) {
25
←
Assuming the condition is true→
26
←
Taking true branch→
  /* Same sign -- add magnitudes, preserve sign of addends */
  if (!s_pad(c, max)) return MP_MEMORY;
27
←
Taking false branch→

  mp_digit carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
  mp_size uc = max;

  if (carry) {
28
←
Assuming 'carry' is not equal to 0→
29
←
Taking true branch→
    if (!s_pad(c, max + 1)) return MP_MEMORY;
30
←
Calling 's_pad'→
40
←
Returned allocated memory→
41
←
Taking false branch→

    c->digits[max] = carry;
    ++uc;
  }

  c->used = uc;
  c->sign = a->sign;

} else {
  /* Different signs -- subtract magnitudes, preserve sign of greater */
  int cmp = s_ucmp(a, b); /* magnitude comparison, sign ignored */

  /* Set x to max(a, b), y to min(a, b) to simplify later code.
     A special case yields zero for equal magnitudes.
  */
  mp_int x, y;
  if (cmp == 0) {
    mp_int_zero(c);
    return MP_OK;
  } else if (cmp < 0) {
    x = b;
    y = a;
  } else {
    x = a;
    y = b;
  }

  if (!s_pad(c, MP_USED(x))) return MP_MEMORY;

  /* Subtract smaller from larger */
  s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
  c->used = x->used;
  CLAMP(c);

  /* Give result the sign of the larger */
  c->sign = x->sign;
}

return MP_OK;
592}

594mp_result mp_int_add_value(mp_int a, mp_small value, mp_int c) {
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit))];

s_fake(&vtmp, value, vbuf);

return mp_int_add(a, &vtmp, c);
601}

603mp_result mp_int_sub(mp_int a, mp_int b, mp_int c) {
assert(a != NULL && b != NULL && c != NULL)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && b != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != NULL && b != NULL && c != NULL"
, "polly/lib/External/isl/imath/imath.c", 604, __extension__ __PRETTY_FUNCTION__
); }));

mp_size ua = MP_USED(a);
mp_size ub = MP_USED(b);
mp_size max = MAX(ua, ub);

if (MP_SIGN(a) != MP_SIGN(b)) {
  /* Different signs -- add magnitudes and keep sign of a */
  if (!s_pad(c, max)) return MP_MEMORY;

  mp_digit carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
  mp_size uc = max;

  if (carry) {
    if (!s_pad(c, max + 1)) return MP_MEMORY;

    c->digits[max] = carry;
    ++uc;
  }

  c->used = uc;
  c->sign = a->sign;

} else {
  /* Same signs -- subtract magnitudes */
  if (!s_pad(c, max)) return MP_MEMORY;
  mp_int x, y;
  mp_sign osign;

  int cmp = s_ucmp(a, b);
  if (cmp >= 0) {
    x = a;
    y = b;
    osign = MP_ZPOS;
  } else {
    x = b;
    y = a;
    osign = MP_NEG;
  }

  if (MP_SIGN(a) == MP_NEG && cmp != 0) osign = 1 - osign;

  s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
  c->used = x->used;
  CLAMP(c);

  c->sign = osign;
}

return MP_OK;
654}

656mp_result mp_int_sub_value(mp_int a, mp_small value, mp_int c) {
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit))];

s_fake(&vtmp, value, vbuf);

return mp_int_sub(a, &vtmp, c);
663}

665mp_result mp_int_mul(mp_int a, mp_int b, mp_int c) {
assert(a != NULL && b != NULL && c != NULL)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && b != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != NULL && b != NULL && c != NULL"
, "polly/lib/External/isl/imath/imath.c", 666, __extension__ __PRETTY_FUNCTION__
); }));

/* If either input is zero, we can shortcut multiplication */
if (mp_int_compare_zero(a) == 0 || mp_int_compare_zero(b) == 0) {
  mp_int_zero(c);
  return MP_OK;
}

/* Output is positive if inputs have same sign, otherwise negative */
mp_sign osign = (MP_SIGN(a) == MP_SIGN(b)) ? MP_ZPOS : MP_NEG;

/* If the output is not identical to any of the inputs, we'll write the
   results directly; otherwise, allocate a temporary space. */
mp_size ua = MP_USED(a);
mp_size ub = MP_USED(b);
mp_size osize = MAX(ua, ub);
osize = 4 * ((osize + 1) / 2);

mp_digit *out;
mp_size p = 0;
if (c == a || c == b) {
  p = MAX(s_round_prec(osize), default_precision);

  if ((out = s_alloc(p)) == NULL((void*)0)) return MP_MEMORY;
} else {
  if (!s_pad(c, osize)) return MP_MEMORY;

  out = MP_DIGITS(c);
}
ZERO(out, osize);

if (!s_kmul(MP_DIGITS(a), MP_DIGITS(b), out, ua, ub)) return MP_MEMORY;

/* If we allocated a new buffer, get rid of whatever memory c was already
   using, and fix up its fields to reflect that.
 */
if (out != MP_DIGITS(c)) {
  if ((void *)MP_DIGITS(c) != (void *)c) s_free(MP_DIGITS(c));
  c->digits = out;
  c->alloc = p;
}

c->used = osize; /* might not be true, but we'll fix it ... */
CLAMP(c);        /* ... right here */
c->sign = osign;

return MP_OK;
713}

715mp_result mp_int_mul_value(mp_int a, mp_small value, mp_int c) {
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit))];

s_fake(&vtmp, value, vbuf);

return mp_int_mul(a, &vtmp, c);
722}

724mp_result mp_int_mul_pow2(mp_int a, mp_small p2, mp_int c) {
assert(a != NULL && c != NULL && p2 >= 0)((void) sizeof ((a != ((void*)0) && c != ((void*)0) &&
 p2 >= 0) ? 1 : 0), __extension__ ({ if (a != ((void*)0) &&
 c != ((void*)0) && p2 >= 0) ; else __assert_fail (
"a != NULL && c != NULL && p2 >= 0", "polly/lib/External/isl/imath/imath.c"
, 725, __extension__ __PRETTY_FUNCTION__); }));

mp_result res = mp_int_copy(a, c);
if (res != MP_OK) return res;

if (s_qmul(c, (mp_size)p2)) {
  return MP_OK;
} else {
  return MP_MEMORY;
}
735}

737mp_result mp_int_sqr(mp_int a, mp_int c) {
assert(a != NULL && c != NULL)((void) sizeof ((a != ((void*)0) && c != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && c !=
 ((void*)0)) ; else __assert_fail ("a != NULL && c != NULL"
, "polly/lib/External/isl/imath/imath.c", 738, __extension__ __PRETTY_FUNCTION__
); }));

/* Get a temporary buffer big enough to hold the result */
mp_size osize = (mp_size)4 * ((MP_USED(a) + 1) / 2);
mp_size p = 0;
mp_digit *out;
if (a == c) {
  p = s_round_prec(osize);
  p = MAX(p, default_precision);

  if ((out = s_alloc(p)) == NULL((void*)0)) return MP_MEMORY;
} else {
  if (!s_pad(c, osize)) return MP_MEMORY;

  out = MP_DIGITS(c);
}
ZERO(out, osize);

s_ksqr(MP_DIGITS(a), out, MP_USED(a));

/* Get rid of whatever memory c was already using, and fix up its fields to
   reflect the new digit array it's using
 */
if (out != MP_DIGITS(c)) {
  if ((void *)MP_DIGITS(c) != (void *)c) s_free(MP_DIGITS(c));
  c->digits = out;
  c->alloc = p;
}

c->used = osize; /* might not be true, but we'll fix it ... */
CLAMP(c);        /* ... right here */
c->sign = MP_ZPOS;

return MP_OK;
772}

774mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r) {
assert(a != NULL && b != NULL && q != r)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 q != r) ? 1 : 0), __extension__ ({ if (a != ((void*)0) &&
 b != ((void*)0) && q != r) ; else __assert_fail ("a != NULL && b != NULL && q != r"
, "polly/lib/External/isl/imath/imath.c", 775, __extension__ __PRETTY_FUNCTION__
); }));

int cmp;
mp_result res = MP_OK;
mp_int qout, rout;
mp_sign sa = MP_SIGN(a);
mp_sign sb = MP_SIGN(b);
if (CMPZ(b) == 0) {
  return MP_UNDEF;
} else if ((cmp = s_ucmp(a, b)) < 0) {
  /* If |a| < |b|, no division is required:
     q = 0, r = a
   */
  if (r && (res = mp_int_copy(a, r)) != MP_OK) return res;

  if (q) mp_int_zero(q);

  return MP_OK;
} else if (cmp == 0) {
  /* If |a| = |b|, no division is required:
     q = 1 or -1, r = 0
   */
  if (r) mp_int_zero(r);

  if (q) {
    mp_int_zero(q);
    q->digits[0] = 1;

    if (sa != sb) q->sign = MP_NEG;
  }

  return MP_OK;
}

/* When |a| > |b|, real division is required.  We need someplace to store
   quotient and remainder, but q and r are allowed to be NULL or to overlap
   with the inputs.
 */
DECLARE_TEMP(2)struct { mpz_t value[(2)]; int len; mp_result err; } temp_ = {
 .len = (2), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
int lg;
if ((lg = s_isp2(b)) < 0) {
  if (q && b != q) {
    REQUIRE(mp_int_copy(a, q))do { temp_.err = (mp_int_copy(a, q)); if (temp_.err != MP_OK)
 goto CLEANUP; } while (0);
    qout = q;
  } else {
    REQUIRE(mp_int_copy(a, TEMP(0)))do { temp_.err = (mp_int_copy(a, (temp_.value + (0)))); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
    qout = TEMP(0)(temp_.value + (0));
  }

  if (r && a != r) {
    REQUIRE(mp_int_copy(b, r))do { temp_.err = (mp_int_copy(b, r)); if (temp_.err != MP_OK)
 goto CLEANUP; } while (0);
    rout = r;
  } else {
    REQUIRE(mp_int_copy(b, TEMP(1)))do { temp_.err = (mp_int_copy(b, (temp_.value + (1)))); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
    rout = TEMP(1)(temp_.value + (1));
  }

  REQUIRE(s_udiv_knuth(qout, rout))do { temp_.err = (s_udiv_knuth(qout, rout)); if (temp_.err !=
 MP_OK) goto CLEANUP; } while (0);
} else {
  if (q) REQUIRE(mp_int_copy(a, q))do { temp_.err = (mp_int_copy(a, q)); if (temp_.err != MP_OK)
 goto CLEANUP; } while (0);
  if (r) REQUIRE(mp_int_copy(a, r))do { temp_.err = (mp_int_copy(a, r)); if (temp_.err != MP_OK)
 goto CLEANUP; } while (0);

  if (q) s_qdiv(q, (mp_size)lg);
  qout = q;
  if (r) s_qmod(r, (mp_size)lg);
  rout = r;
}

/* Recompute signs for output */
if (rout) {
  rout->sign = sa;
  if (CMPZ(rout) == 0) rout->sign = MP_ZPOS;
}
if (qout) {
  qout->sign = (sa == sb) ? MP_ZPOS : MP_NEG;
  if (CMPZ(qout) == 0) qout->sign = MP_ZPOS;
}

if (q) REQUIRE(mp_int_copy(qout, q))do { temp_.err = (mp_int_copy(qout, q)); if (temp_.err != MP_OK
) goto CLEANUP; } while (0);
if (r) REQUIRE(mp_int_copy(rout, r))do { temp_.err = (mp_int_copy(rout, r)); if (temp_.err != MP_OK
) goto CLEANUP; } while (0);
CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return res;
857}

859mp_result mp_int_mod(mp_int a, mp_int m, mp_int c) {
DECLARE_TEMP(1)struct { mpz_t value[(1)]; int len; mp_result err; } temp_ = {
 .len = (1), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
16
←
Loop condition is true.  Entering loop body→
17
←
Loop condition is false. Execution continues on line 860→
mp_int out = (m17.1
'm' is not equal to 'c'
 == c) ? TEMP(0)(temp_.value + (0)) : c;
18
←
'?' condition is false→
REQUIRE(mp_int_div(a, m, NULL, out))do { temp_.err = (mp_int_div(a, m, ((void*)0), out)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
19
←
Assuming 'MP_OK' is equal to field 'err'→
20
←
Taking false branch→
21
←
Loop condition is false.  Exiting loop→
if (CMPZ(out) < 0) {
22
←
Taking true branch→
  REQUIRE(mp_int_add(out, m, c))do { temp_.err = (mp_int_add(out, m, c)); if (temp_.err != MP_OK
) goto CLEANUP; } while (0);
23
←
Calling 'mp_int_add'→
42
←
Returned allocated memory→
43
←
Taking false branch→
44
←
Loop condition is false.  Exiting loop→
} else {
  REQUIRE(mp_int_copy(out, c))do { temp_.err = (mp_int_copy(out, c)); if (temp_.err != MP_OK
) goto CLEANUP; } while (0);
}
CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
45
←
Loop condition is true.  Entering loop body→
46
←
Loop condition is false. Execution continues on line 868→
47
←
Taking false branch→
48
←
Loop condition is false.  Exiting loop→
return MP_OK;
870}

872mp_result mp_int_div_value(mp_int a, mp_small value, mp_int q, mp_small *r) {
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit))];
s_fake(&vtmp, value, vbuf);

DECLARE_TEMP(1)struct { mpz_t value[(1)]; int len; mp_result err; } temp_ = {
 .len = (1), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
REQUIRE(mp_int_div(a, &vtmp, q, TEMP(0)))do { temp_.err = (mp_int_div(a, &vtmp, q, (temp_.value + (
0)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);

if (r) (void)mp_int_to_int(TEMP(0)(temp_.value + (0)), r); /* can't fail */

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return MP_OK;
884}

886mp_result mp_int_div_pow2(mp_int a, mp_small p2, mp_int q, mp_int r) {
assert(a != NULL && p2 >= 0 && q != r)((void) sizeof ((a != ((void*)0) && p2 >= 0 &&
 q != r) ? 1 : 0), __extension__ ({ if (a != ((void*)0) &&
 p2 >= 0 && q != r) ; else __assert_fail ("a != NULL && p2 >= 0 && q != r"
, "polly/lib/External/isl/imath/imath.c", 887, __extension__ __PRETTY_FUNCTION__
); }));

mp_result res = MP_OK;
if (q != NULL((void*)0) && (res = mp_int_copy(a, q)) == MP_OK) {
  s_qdiv(q, (mp_size)p2);
}

if (res == MP_OK && r != NULL((void*)0) && (res = mp_int_copy(a, r)) == MP_OK) {
  s_qmod(r, (mp_size)p2);
}

return res;
899}

901mp_result mp_int_expt(mp_int a, mp_small b, mp_int c) {
assert(c != NULL)((void) sizeof ((c != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (c != ((void*)0)) ; else __assert_fail ("c != NULL", "polly/lib/External/isl/imath/imath.c"
, 902, __extension__ __PRETTY_FUNCTION__); }));
if (b < 0) return MP_RANGE;

DECLARE_TEMP(1)struct { mpz_t value[(1)]; int len; mp_result err; } temp_ = {
 .len = (1), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
REQUIRE(mp_int_copy(a, TEMP(0)))do { temp_.err = (mp_int_copy(a, (temp_.value + (0)))); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);

(void)mp_int_set_value(c, 1);
unsigned int v = labs(b);
while (v != 0) {
  if (v & 1) {
    REQUIRE(mp_int_mul(c, TEMP(0), c))do { temp_.err = (mp_int_mul(c, (temp_.value + (0)), c)); if (
temp_.err != MP_OK) goto CLEANUP; } while (0);
  }

  v >>= 1;
  if (v == 0) break;

  REQUIRE(mp_int_sqr(TEMP(0), TEMP(0)))do { temp_.err = (mp_int_sqr((temp_.value + (0)), (temp_.value
 + (0)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);
}

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return MP_OK;
923}

925mp_result mp_int_expt_value(mp_small a, mp_small b, mp_int c) {
assert(c != NULL)((void) sizeof ((c != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (c != ((void*)0)) ; else __assert_fail ("c != NULL", "polly/lib/External/isl/imath/imath.c"
, 926, __extension__ __PRETTY_FUNCTION__); }));
if (b < 0) return MP_RANGE;

DECLARE_TEMP(1)struct { mpz_t value[(1)]; int len; mp_result err; } temp_ = {
 .len = (1), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
REQUIRE(mp_int_set_value(TEMP(0), a))do { temp_.err = (mp_int_set_value((temp_.value + (0)), a)); if
 (temp_.err != MP_OK) goto CLEANUP; } while (0);

(void)mp_int_set_value(c, 1);
unsigned int v = labs(b);
while (v != 0) {
  if (v & 1) {
    REQUIRE(mp_int_mul(c, TEMP(0), c))do { temp_.err = (mp_int_mul(c, (temp_.value + (0)), c)); if (
temp_.err != MP_OK) goto CLEANUP; } while (0);
  }

  v >>= 1;
  if (v == 0) break;

  REQUIRE(mp_int_sqr(TEMP(0), TEMP(0)))do { temp_.err = (mp_int_sqr((temp_.value + (0)), (temp_.value
 + (0)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);
}

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return MP_OK;
947}

949mp_result mp_int_expt_full(mp_int a, mp_int b, mp_int c) {
assert(a != NULL && b != NULL && c != NULL)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && b != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != NULL && b != NULL && c != NULL"
, "polly/lib/External/isl/imath/imath.c", 950, __extension__ __PRETTY_FUNCTION__
); }));
if (MP_SIGN(b) == MP_NEG) return MP_RANGE;

DECLARE_TEMP(1)struct { mpz_t value[(1)]; int len; mp_result err; } temp_ = {
 .len = (1), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
REQUIRE(mp_int_copy(a, TEMP(0)))do { temp_.err = (mp_int_copy(a, (temp_.value + (0)))); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);

(void)mp_int_set_value(c, 1);
for (unsigned ix = 0; ix < MP_USED(b); ++ix) {
  mp_digit d = b->digits[ix];

  for (unsigned jx = 0; jx < MP_DIGIT_BIT(sizeof(mp_digit) * 8); ++jx) {
    if (d & 1) {
      REQUIRE(mp_int_mul(c, TEMP(0), c))do { temp_.err = (mp_int_mul(c, (temp_.value + (0)), c)); if (
temp_.err != MP_OK) goto CLEANUP; } while (0);
    }

    d >>= 1;
    if (d == 0 && ix + 1 == MP_USED(b)) break;
    REQUIRE(mp_int_sqr(TEMP(0), TEMP(0)))do { temp_.err = (mp_int_sqr((temp_.value + (0)), (temp_.value
 + (0)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);
  }
}

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return MP_OK;
973}

975int mp_int_compare(mp_int a, mp_int b) {
assert(a != NULL && b != NULL)((void) sizeof ((a != ((void*)0) && b != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && b !=
 ((void*)0)) ; else __assert_fail ("a != NULL && b != NULL"
, "polly/lib/External/isl/imath/imath.c", 976, __extension__ __PRETTY_FUNCTION__
); }));

mp_sign sa = MP_SIGN(a);
if (sa == MP_SIGN(b)) {
  int cmp = s_ucmp(a, b);

  /* If they're both zero or positive, the normal comparison applies; if both
     negative, the sense is reversed. */
  if (sa == MP_ZPOS) {
    return cmp;
  } else {
    return -cmp;
  }
} else if (sa == MP_ZPOS) {
  return 1;
} else {
  return -1;
}
994}

996int mp_int_compare_unsigned(mp_int a, mp_int b) {
assert(a != NULL && b != NULL)((void) sizeof ((a != ((void*)0) && b != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && b !=
 ((void*)0)) ; else __assert_fail ("a != NULL && b != NULL"
, "polly/lib/External/isl/imath/imath.c", 997, __extension__ __PRETTY_FUNCTION__
); }));

return s_ucmp(a, b);
1000}

1002int mp_int_compare_zero(mp_int z) {
assert(z != NULL)((void) sizeof ((z != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (z != ((void*)0)) ; else __assert_fail ("z != NULL", "polly/lib/External/isl/imath/imath.c"
, 1003, __extension__ __PRETTY_FUNCTION__); }));

if (MP_USED(z) == 1 && z->digits[0] == 0) {
  return 0;
} else if (MP_SIGN(z) == MP_ZPOS) {
  return 1;
} else {
  return -1;
}
1012}

1014int mp_int_compare_value(mp_int z, mp_small value) {
assert(z != NULL)((void) sizeof ((z != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (z != ((void*)0)) ; else __assert_fail ("z != NULL", "polly/lib/External/isl/imath/imath.c"
, 1015, __extension__ __PRETTY_FUNCTION__); }));

mp_sign vsign = (value < 0) ? MP_NEG : MP_ZPOS;
if (vsign == MP_SIGN(z)) {
  int cmp = s_vcmp(z, value);

  return (vsign == MP_ZPOS) ? cmp : -cmp;
} else {
  return (value < 0) ? 1 : -1;
}
1025}

1027int mp_int_compare_uvalue(mp_int z, mp_usmall uv) {
assert(z != NULL)((void) sizeof ((z != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (z != ((void*)0)) ; else __assert_fail ("z != NULL", "polly/lib/External/isl/imath/imath.c"
, 1028, __extension__ __PRETTY_FUNCTION__); }));

if (MP_SIGN(z) == MP_NEG) {
  return -1;
} else {
  return s_uvcmp(z, uv);
}
1035}

1037mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, mp_int c) {
assert(a != NULL && b != NULL && c != NULL && m != NULL)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0) && m != ((void*)0)) ? 1 : 0), __extension__
 ({ if (a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0) && m != ((void*)0)) ; else __assert_fail
 ("a != NULL && b != NULL && c != NULL && m != NULL"
, "polly/lib/External/isl/imath/imath.c", 1038, __extension__
 __PRETTY_FUNCTION__); }));

/* Zero moduli and negative exponents are not considered. */
if (CMPZ(m) == 0) return MP_UNDEF;
if (CMPZ(b) < 0) return MP_RANGE;

mp_size um = MP_USED(m);
DECLARE_TEMP(3)struct { mpz_t value[(3)]; int len; mp_result err; } temp_ = {
 .len = (3), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
REQUIRE(GROW(TEMP(0), 2 * um))do { temp_.err = (GROW((temp_.value + (0)), 2 * um)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(GROW(TEMP(1), 2 * um))do { temp_.err = (GROW((temp_.value + (1)), 2 * um)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);

mp_int s;
if (c == b || c == m) {
  REQUIRE(GROW(TEMP(2), 2 * um))do { temp_.err = (GROW((temp_.value + (2)), 2 * um)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
  s = TEMP(2)(temp_.value + (2));
} else {
  s = c;
}

REQUIRE(mp_int_mod(a, m, TEMP(0)))do { temp_.err = (mp_int_mod(a, m, (temp_.value + (0)))); if (
temp_.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(s_brmu(TEMP(1), m))do { temp_.err = (s_brmu((temp_.value + (1)), m)); if (temp_.
err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(s_embar(TEMP(0), b, m, TEMP(1), s))do { temp_.err = (s_embar((temp_.value + (0)), b, m, (temp_.value
 + (1)), s)); if (temp_.err != MP_OK) goto CLEANUP; } while (
0);
REQUIRE(mp_int_copy(s, c))do { temp_.err = (mp_int_copy(s, c)); if (temp_.err != MP_OK)
 goto CLEANUP; } while (0);

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return MP_OK;
1064}

1066mp_result mp_int_exptmod_evalue(mp_int a, mp_small value, mp_int m, mp_int c) {
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit))];

s_fake(&vtmp, value, vbuf);

return mp_int_exptmod(a, &vtmp, m, c);
1073}

1075mp_result mp_int_exptmod_bvalue(mp_small value, mp_int b, mp_int m, mp_int c) {
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit))];

s_fake(&vtmp, value, vbuf);

return mp_int_exptmod(&vtmp, b, m, c);
1082}

1084mp_result mp_int_exptmod_known(mp_int a, mp_int b, mp_int m, mp_int mu,
                             mp_int c) {
assert(a && b && m && c)((void) sizeof ((a && b && m && c) ? 1
 : 0), __extension__ ({ if (a && b && m &&
 c) ; else __assert_fail ("a && b && m && c"
, "polly/lib/External/isl/imath/imath.c", 1086, __extension__
 __PRETTY_FUNCTION__); }));

/* Zero moduli and negative exponents are not considered. */
if (CMPZ(m) == 0) return MP_UNDEF;
if (CMPZ(b) < 0) return MP_RANGE;

DECLARE_TEMP(2)struct { mpz_t value[(2)]; int len; mp_result err; } temp_ = {
 .len = (2), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
mp_size um = MP_USED(m);
REQUIRE(GROW(TEMP(0), 2 * um))do { temp_.err = (GROW((temp_.value + (0)), 2 * um)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);

mp_int s;
if (c == b || c == m) {
  REQUIRE(GROW(TEMP(1), 2 * um))do { temp_.err = (GROW((temp_.value + (1)), 2 * um)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
  s = TEMP(1)(temp_.value + (1));
} else {
  s = c;
}

REQUIRE(mp_int_mod(a, m, TEMP(0)))do { temp_.err = (mp_int_mod(a, m, (temp_.value + (0)))); if (
temp_.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(s_embar(TEMP(0), b, m, mu, s))do { temp_.err = (s_embar((temp_.value + (0)), b, m, mu, s));
 if (temp_.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(mp_int_copy(s, c))do { temp_.err = (mp_int_copy(s, c)); if (temp_.err != MP_OK)
 goto CLEANUP; } while (0);

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return MP_OK;
1110}

1112mp_result mp_int_redux_const(mp_int m, mp_int c) {
assert(m != NULL && c != NULL && m != c)((void) sizeof ((m != ((void*)0) && c != ((void*)0) &&
 m != c) ? 1 : 0), __extension__ ({ if (m != ((void*)0) &&
 c != ((void*)0) && m != c) ; else __assert_fail ("m != NULL && c != NULL && m != c"
, "polly/lib/External/isl/imath/imath.c", 1113, __extension__
 __PRETTY_FUNCTION__); }));

return s_brmu(c, m);
1116}

1118mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c) {
assert(a != NULL && m != NULL && c != NULL)((void) sizeof ((a != ((void*)0) && m != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && m != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != NULL && m != NULL && c != NULL"
, "polly/lib/External/isl/imath/imath.c", 1119, __extension__
 __PRETTY_FUNCTION__); }));
1
Assuming 'a' is not equal to null→
2
←
Assuming 'm' is not equal to null→
3
←
Assuming 'c' is not equal to null→
4
←
Taking true branch→

if (CMPZ(a) == 0 || CMPZ(m) <= 0) return MP_RANGE;
5
←
Taking false branch→

DECLARE_TEMP(2)struct { mpz_t value[(2)]; int len; mp_result err; } temp_ = {
 .len = (2), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
6
←
Loop condition is true.  Entering loop body→
7
←
Loop condition is true.  Entering loop body→
8
←
Loop condition is false. Execution continues on line 1123→
9
←
Loop condition is false.  Exiting loop→

REQUIRE(mp_int_egcd(a, m, TEMP(0), TEMP(1), NULL))do { temp_.err = (mp_int_egcd(a, m, (temp_.value + (0)), (temp_
.value + (1)), ((void*)0))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
10
←
Assuming 'MP_OK' is equal to field 'err'→
11
←
Taking false branch→
12
←
Loop condition is false.  Exiting loop→

if (mp_int_compare_value(TEMP(0)(temp_.value + (0)), 1) != 0) {
13
←
Assuming the condition is false→
14
←
Taking false branch→
  REQUIRE(MP_UNDEF)do { temp_.err = (MP_UNDEF); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
}

/* It is first necessary to constrain the value to the proper range */
REQUIRE(mp_int_mod(TEMP(1), m, TEMP(1)))do { temp_.err = (mp_int_mod((temp_.value + (1)), m, (temp_.value
 + (1)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);
15
←
Calling 'mp_int_mod'→
49
←
Returned allocated memory→
50
←
Taking false branch→
51
←
Loop condition is false.  Exiting loop→

/* Now, if 'a' was originally negative, the value we have is actually the
   magnitude of the negative representative; to get the positive value we
   have to subtract from the modulus.  Otherwise, the value is okay as it
   stands.
 */
if (MP_SIGN(a) == MP_NEG) {
52
←
Assuming the condition is false→
53
←
Taking false branch→
  REQUIRE(mp_int_sub(m, TEMP(1), c))do { temp_.err = (mp_int_sub(m, (temp_.value + (1)), c)); if (
temp_.err != MP_OK) goto CLEANUP; } while (0);
} else {
  REQUIRE(mp_int_copy(TEMP(1), c))do { temp_.err = (mp_int_copy((temp_.value + (1)), c)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
54
←
Taking false branch→
55
←
Loop condition is false.  Exiting loop→
}

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
56
←
Assuming 'i' is >= field 'len'→
57
←
Loop condition is false. Execution continues on line 1145→
58
←
Taking false branch→
59
←
Potential leak of memory pointed to by field 'digits'
return MP_OK;
1147}

1149/* Binary GCD algorithm due to Josef Stein, 1961 */
1150mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c) {
assert(a != NULL && b != NULL && c != NULL)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && b != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != NULL && b != NULL && c != NULL"
, "polly/lib/External/isl/imath/imath.c", 1151, __extension__
 __PRETTY_FUNCTION__); }));

int ca = CMPZ(a);
int cb = CMPZ(b);
if (ca == 0 && cb == 0) {
  return MP_UNDEF;
} else if (ca == 0) {
  return mp_int_abs(b, c);
} else if (cb == 0) {
  return mp_int_abs(a, c);
}

DECLARE_TEMP(3)struct { mpz_t value[(3)]; int len; mp_result err; } temp_ = {
 .len = (3), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
REQUIRE(mp_int_copy(a, TEMP(0)))do { temp_.err = (mp_int_copy(a, (temp_.value + (0)))); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(mp_int_copy(b, TEMP(1)))do { temp_.err = (mp_int_copy(b, (temp_.value + (1)))); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);

TEMP(0)(temp_.value + (0))->sign = MP_ZPOS;
TEMP(1)(temp_.value + (1))->sign = MP_ZPOS;

int k = 0;
{ /* Divide out common factors of 2 from u and v */
  int div2_u = s_dp2k(TEMP(0)(temp_.value + (0)));
  int div2_v = s_dp2k(TEMP(1)(temp_.value + (1)));

  k = MIN(div2_u, div2_v);
  s_qdiv(TEMP(0)(temp_.value + (0)), (mp_size)k);
  s_qdiv(TEMP(1)(temp_.value + (1)), (mp_size)k);
}

if (mp_int_is_odd(TEMP(0)(temp_.value + (0)))) {
  REQUIRE(mp_int_neg(TEMP(1), TEMP(2)))do { temp_.err = (mp_int_neg((temp_.value + (1)), (temp_.value
 + (2)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);
} else {
  REQUIRE(mp_int_copy(TEMP(0), TEMP(2)))do { temp_.err = (mp_int_copy((temp_.value + (0)), (temp_.value
 + (2)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);
}

for (;;) {
  s_qdiv(TEMP(2)(temp_.value + (2)), s_dp2k(TEMP(2)(temp_.value + (2))));

  if (CMPZ(TEMP(2)(temp_.value + (2))) > 0) {
    REQUIRE(mp_int_copy(TEMP(2), TEMP(0)))do { temp_.err = (mp_int_copy((temp_.value + (2)), (temp_.value
 + (0)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);
  } else {
    REQUIRE(mp_int_neg(TEMP(2), TEMP(1)))do { temp_.err = (mp_int_neg((temp_.value + (2)), (temp_.value
 + (1)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);
  }

  REQUIRE(mp_int_sub(TEMP(0), TEMP(1), TEMP(2)))do { temp_.err = (mp_int_sub((temp_.value + (0)), (temp_.value
 + (1)), (temp_.value + (2)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);

  if (CMPZ(TEMP(2)(temp_.value + (2))) == 0) break;
}

REQUIRE(mp_int_abs(TEMP(0), c))do { temp_.err = (mp_int_abs((temp_.value + (0)), c)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
if (!s_qmul(c, (mp_size)k)) REQUIRE(MP_MEMORY)do { temp_.err = (MP_MEMORY); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return MP_OK;
1205}

1207/* This is the binary GCD algorithm again, but this time we keep track of the
 elementary matrix operations as we go, so we can get values x and y
 satisfying c = ax + by.
*/
1211mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, mp_int x, mp_int y) {
assert(a != NULL && b != NULL && c != NULL && (x != NULL || y != NULL))((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0) && (x != ((void*)0) || y != ((void*)
0))) ? 1 : 0), __extension__ ({ if (a != ((void*)0) &&
 b != ((void*)0) && c != ((void*)0) && (x != (
(void*)0) || y != ((void*)0))) ; else __assert_fail ("a != NULL && b != NULL && c != NULL && (x != NULL || y != NULL)"
, "polly/lib/External/isl/imath/imath.c", 1212, __extension__
 __PRETTY_FUNCTION__); }));

mp_result res = MP_OK;
int ca = CMPZ(a);
int cb = CMPZ(b);
if (ca == 0 && cb == 0) {
  return MP_UNDEF;
} else if (ca == 0) {
  if ((res = mp_int_abs(b, c)) != MP_OK) return res;
  mp_int_zero(x);
  (void)mp_int_set_value(y, 1);
  return MP_OK;
} else if (cb == 0) {
  if ((res = mp_int_abs(a, c)) != MP_OK) return res;
  (void)mp_int_set_value(x, 1);
  mp_int_zero(y);
  return MP_OK;
}

/* Initialize temporaries:
   A:0, B:1, C:2, D:3, u:4, v:5, ou:6, ov:7 */
DECLARE_TEMP(8)struct { mpz_t value[(8)]; int len; mp_result err; } temp_ = {
 .len = (8), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
REQUIRE(mp_int_set_value(TEMP(0), 1))do { temp_.err = (mp_int_set_value((temp_.value + (0)), 1)); if
 (temp_.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(mp_int_set_value(TEMP(3), 1))do { temp_.err = (mp_int_set_value((temp_.value + (3)), 1)); if
 (temp_.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(mp_int_copy(a, TEMP(4)))do { temp_.err = (mp_int_copy(a, (temp_.value + (4)))); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(mp_int_copy(b, TEMP(5)))do { temp_.err = (mp_int_copy(b, (temp_.value + (5)))); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);

/* We will work with absolute values here */
TEMP(4)(temp_.value + (4))->sign = MP_ZPOS;
TEMP(5)(temp_.value + (5))->sign = MP_ZPOS;

int k = 0;
{ /* Divide out common factors of 2 from u and v */
  int div2_u = s_dp2k(TEMP(4)(temp_.value + (4))), div2_v = s_dp2k(TEMP(5)(temp_.value + (5)));

  k = MIN(div2_u, div2_v);
  s_qdiv(TEMP(4)(temp_.value + (4)), k);
  s_qdiv(TEMP(5)(temp_.value + (5)), k);
}

REQUIRE(mp_int_copy(TEMP(4), TEMP(6)))do { temp_.err = (mp_int_copy((temp_.value + (4)), (temp_.value
 + (6)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(mp_int_copy(TEMP(5), TEMP(7)))do { temp_.err = (mp_int_copy((temp_.value + (5)), (temp_.value
 + (7)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);

for (;;) {
  while (mp_int_is_even(TEMP(4)(temp_.value + (4)))) {
    s_qdiv(TEMP(4)(temp_.value + (4)), 1);

    if (mp_int_is_odd(TEMP(0)(temp_.value + (0))) || mp_int_is_odd(TEMP(1)(temp_.value + (1)))) {
      REQUIRE(mp_int_add(TEMP(0), TEMP(7), TEMP(0)))do { temp_.err = (mp_int_add((temp_.value + (0)), (temp_.value
 + (7)), (temp_.value + (0)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
      REQUIRE(mp_int_sub(TEMP(1), TEMP(6), TEMP(1)))do { temp_.err = (mp_int_sub((temp_.value + (1)), (temp_.value
 + (6)), (temp_.value + (1)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
    }

    s_qdiv(TEMP(0)(temp_.value + (0)), 1);
    s_qdiv(TEMP(1)(temp_.value + (1)), 1);
  }

  while (mp_int_is_even(TEMP(5)(temp_.value + (5)))) {
    s_qdiv(TEMP(5)(temp_.value + (5)), 1);

    if (mp_int_is_odd(TEMP(2)(temp_.value + (2))) || mp_int_is_odd(TEMP(3)(temp_.value + (3)))) {
      REQUIRE(mp_int_add(TEMP(2), TEMP(7), TEMP(2)))do { temp_.err = (mp_int_add((temp_.value + (2)), (temp_.value
 + (7)), (temp_.value + (2)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
      REQUIRE(mp_int_sub(TEMP(3), TEMP(6), TEMP(3)))do { temp_.err = (mp_int_sub((temp_.value + (3)), (temp_.value
 + (6)), (temp_.value + (3)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
    }

    s_qdiv(TEMP(2)(temp_.value + (2)), 1);
    s_qdiv(TEMP(3)(temp_.value + (3)), 1);
  }

  if (mp_int_compare(TEMP(4)(temp_.value + (4)), TEMP(5)(temp_.value + (5))) >= 0) {
    REQUIRE(mp_int_sub(TEMP(4), TEMP(5), TEMP(4)))do { temp_.err = (mp_int_sub((temp_.value + (4)), (temp_.value
 + (5)), (temp_.value + (4)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
    REQUIRE(mp_int_sub(TEMP(0), TEMP(2), TEMP(0)))do { temp_.err = (mp_int_sub((temp_.value + (0)), (temp_.value
 + (2)), (temp_.value + (0)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
    REQUIRE(mp_int_sub(TEMP(1), TEMP(3), TEMP(1)))do { temp_.err = (mp_int_sub((temp_.value + (1)), (temp_.value
 + (3)), (temp_.value + (1)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
  } else {
    REQUIRE(mp_int_sub(TEMP(5), TEMP(4), TEMP(5)))do { temp_.err = (mp_int_sub((temp_.value + (5)), (temp_.value
 + (4)), (temp_.value + (5)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
    REQUIRE(mp_int_sub(TEMP(2), TEMP(0), TEMP(2)))do { temp_.err = (mp_int_sub((temp_.value + (2)), (temp_.value
 + (0)), (temp_.value + (2)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
    REQUIRE(mp_int_sub(TEMP(3), TEMP(1), TEMP(3)))do { temp_.err = (mp_int_sub((temp_.value + (3)), (temp_.value
 + (1)), (temp_.value + (3)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
  }

  if (CMPZ(TEMP(4)(temp_.value + (4))) == 0) {
    if (x) REQUIRE(mp_int_copy(TEMP(2), x))do { temp_.err = (mp_int_copy((temp_.value + (2)), x)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
    if (y) REQUIRE(mp_int_copy(TEMP(3), y))do { temp_.err = (mp_int_copy((temp_.value + (3)), y)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
    if (c) {
      if (!s_qmul(TEMP(5)(temp_.value + (5)), k)) {
        REQUIRE(MP_MEMORY)do { temp_.err = (MP_MEMORY); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
      }
      REQUIRE(mp_int_copy(TEMP(5), c))do { temp_.err = (mp_int_copy((temp_.value + (5)), c)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
    }

    break;
  }
}

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return MP_OK;
1306}

1308mp_result mp_int_lcm(mp_int a, mp_int b, mp_int c) {
assert(a != NULL && b != NULL && c != NULL)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && b != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != NULL && b != NULL && c != NULL"
, "polly/lib/External/isl/imath/imath.c", 1309, __extension__
 __PRETTY_FUNCTION__); }));

/* Since a * b = gcd(a, b) * lcm(a, b), we can compute
   lcm(a, b) = (a / gcd(a, b)) * b.

   This formulation insures everything works even if the input
   variables share space.
 */
DECLARE_TEMP(1)struct { mpz_t value[(1)]; int len; mp_result err; } temp_ = {
 .len = (1), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
REQUIRE(mp_int_gcd(a, b, TEMP(0)))do { temp_.err = (mp_int_gcd(a, b, (temp_.value + (0)))); if (
temp_.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(mp_int_div(a, TEMP(0), TEMP(0), NULL))do { temp_.err = (mp_int_div(a, (temp_.value + (0)), (temp_.value
 + (0)), ((void*)0))); if (temp_.err != MP_OK) goto CLEANUP; }
 while (0);
REQUIRE(mp_int_mul(TEMP(0), b, TEMP(0)))do { temp_.err = (mp_int_mul((temp_.value + (0)), b, (temp_.value
 + (0)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(mp_int_copy(TEMP(0), c))do { temp_.err = (mp_int_copy((temp_.value + (0)), c)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return MP_OK;
1325}

1327bool_Bool mp_int_divisible_value(mp_int a, mp_small v) {
mp_small rem = 0;

if (mp_int_div_value(a, v, NULL((void*)0), &rem) != MP_OK) {
  return false0;
}
return rem == 0;
1334}

1336int mp_int_is_pow2(mp_int z) {
assert(z != NULL)((void) sizeof ((z != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (z != ((void*)0)) ; else __assert_fail ("z != NULL", "polly/lib/External/isl/imath/imath.c"
, 1337, __extension__ __PRETTY_FUNCTION__); }));

return s_isp2(z);
1340}

1342/* Implementation of Newton's root finding method, based loosely on a patch
 contributed by Hal Finkel <half@halssoftware.com>
 modified by M. J. Fromberger.
*/
1346mp_result mp_int_root(mp_int a, mp_small b, mp_int c) {
assert(a != NULL && c != NULL && b > 0)((void) sizeof ((a != ((void*)0) && c != ((void*)0) &&
 b > 0) ? 1 : 0), __extension__ ({ if (a != ((void*)0) &&
 c != ((void*)0) && b > 0) ; else __assert_fail ("a != NULL && c != NULL && b > 0"
, "polly/lib/External/isl/imath/imath.c", 1347, __extension__
 __PRETTY_FUNCTION__); }));

if (b == 1) {
  return mp_int_copy(a, c);
}
bool_Bool flips = false0;
if (MP_SIGN(a) == MP_NEG) {
  if (b % 2 == 0) {
    return MP_UNDEF; /* root does not exist for negative a with even b */
  } else {
    flips = true1;
  }
}

DECLARE_TEMP(5)struct { mpz_t value[(5)]; int len; mp_result err; } temp_ = {
 .len = (5), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
REQUIRE(mp_int_copy(a, TEMP(0)))do { temp_.err = (mp_int_copy(a, (temp_.value + (0)))); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(mp_int_copy(a, TEMP(1)))do { temp_.err = (mp_int_copy(a, (temp_.value + (1)))); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
TEMP(0)(temp_.value + (0))->sign = MP_ZPOS;
TEMP(1)(temp_.value + (1))->sign = MP_ZPOS;

for (;;) {
  REQUIRE(mp_int_expt(TEMP(1), b, TEMP(2)))do { temp_.err = (mp_int_expt((temp_.value + (1)), b, (temp_.
value + (2)))); if (temp_.err != MP_OK) goto CLEANUP; } while
 (0);

  if (mp_int_compare_unsigned(TEMP(2)(temp_.value + (2)), TEMP(0)(temp_.value + (0))) <= 0) break;

  REQUIRE(mp_int_sub(TEMP(2), TEMP(0), TEMP(2)))do { temp_.err = (mp_int_sub((temp_.value + (2)), (temp_.value
 + (0)), (temp_.value + (2)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
  REQUIRE(mp_int_expt(TEMP(1), b - 1, TEMP(3)))do { temp_.err = (mp_int_expt((temp_.value + (1)), b - 1, (temp_
.value + (3)))); if (temp_.err != MP_OK) goto CLEANUP; } while
 (0);
  REQUIRE(mp_int_mul_value(TEMP(3), b, TEMP(3)))do { temp_.err = (mp_int_mul_value((temp_.value + (3)), b, (temp_
.value + (3)))); if (temp_.err != MP_OK) goto CLEANUP; } while
 (0);
  REQUIRE(mp_int_div(TEMP(2), TEMP(3), TEMP(4), NULL))do { temp_.err = (mp_int_div((temp_.value + (2)), (temp_.value
 + (3)), (temp_.value + (4)), ((void*)0))); if (temp_.err != MP_OK
) goto CLEANUP; } while (0);
  REQUIRE(mp_int_sub(TEMP(1), TEMP(4), TEMP(4)))do { temp_.err = (mp_int_sub((temp_.value + (1)), (temp_.value
 + (4)), (temp_.value + (4)))); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);

  if (mp_int_compare_unsigned(TEMP(1)(temp_.value + (1)), TEMP(4)(temp_.value + (4))) == 0) {
    REQUIRE(mp_int_sub_value(TEMP(4), 1, TEMP(4)))do { temp_.err = (mp_int_sub_value((temp_.value + (4)), 1, (temp_
.value + (4)))); if (temp_.err != MP_OK) goto CLEANUP; } while
 (0);
  }
  REQUIRE(mp_int_copy(TEMP(4), TEMP(1)))do { temp_.err = (mp_int_copy((temp_.value + (4)), (temp_.value
 + (1)))); if (temp_.err != MP_OK) goto CLEANUP; } while (0);
}

REQUIRE(mp_int_copy(TEMP(1), c))do { temp_.err = (mp_int_copy((temp_.value + (1)), c)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);

/* If the original value of a was negative, flip the output sign. */
if (flips) (void)mp_int_neg(c, c); /* cannot fail */

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return MP_OK;
1391}

1393mp_result mp_int_to_int(mp_int z, mp_small *out) {
assert(z != NULL)((void) sizeof ((z != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (z != ((void*)0)) ; else __assert_fail ("z != NULL", "polly/lib/External/isl/imath/imath.c"
, 1394, __extension__ __PRETTY_FUNCTION__); }));

/* Make sure the value is representable as a small integer */
mp_sign sz = MP_SIGN(z);
if ((sz == MP_ZPOS && mp_int_compare_value(z, MP_SMALL_MAX9223372036854775807L) > 0) ||
    mp_int_compare_value(z, MP_SMALL_MIN(-9223372036854775807L -1L)) < 0) {
  return MP_RANGE;
}

mp_usmall uz = MP_USED(z);
mp_digit *dz = MP_DIGITS(z) + uz - 1;
mp_small uv = 0;
while (uz > 0) {
  uv <<= MP_DIGIT_BIT(sizeof(mp_digit) * 8) / 2;
  uv = (uv << (MP_DIGIT_BIT(sizeof(mp_digit) * 8) / 2)) | *dz--;
  --uz;
}

if (out) *out = (mp_small)((sz == MP_NEG) ? -uv : uv);

return MP_OK;
1415}

1417mp_result mp_int_to_uint(mp_int z, mp_usmall *out) {
assert(z != NULL)((void) sizeof ((z != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (z != ((void*)0)) ; else __assert_fail ("z != NULL", "polly/lib/External/isl/imath/imath.c"
, 1418, __extension__ __PRETTY_FUNCTION__); }));

/* Make sure the value is representable as an unsigned small integer */
mp_size sz = MP_SIGN(z);
if (sz == MP_NEG || mp_int_compare_uvalue(z, MP_USMALL_MAX(9223372036854775807L *2UL+1UL)) > 0) {
  return MP_RANGE;
}

mp_size uz = MP_USED(z);
mp_digit *dz = MP_DIGITS(z) + uz - 1;
mp_usmall uv = 0;

while (uz > 0) {
  uv <<= MP_DIGIT_BIT(sizeof(mp_digit) * 8) / 2;
  uv = (uv << (MP_DIGIT_BIT(sizeof(mp_digit) * 8) / 2)) | *dz--;
  --uz;
}

if (out) *out = uv;

return MP_OK;
1439}

1441mp_result mp_int_to_string(mp_int z, mp_size radix, char *str, int limit) {
assert(z != NULL && str != NULL && limit >= 2)((void) sizeof ((z != ((void*)0) && str != ((void*)0)
 && limit >= 2) ? 1 : 0), __extension__ ({ if (z !=
 ((void*)0) && str != ((void*)0) && limit >=
 2) ; else __assert_fail ("z != NULL && str != NULL && limit >= 2"
, "polly/lib/External/isl/imath/imath.c", 1442, __extension__
 __PRETTY_FUNCTION__); }));
assert(radix >= MP_MIN_RADIX && radix <= MP_MAX_RADIX)((void) sizeof ((radix >= 2 && radix <= 36) ? 1
 : 0), __extension__ ({ if (radix >= 2 && radix <=
 36) ; else __assert_fail ("radix >= MP_MIN_RADIX && radix <= MP_MAX_RADIX"
, "polly/lib/External/isl/imath/imath.c", 1443, __extension__
 __PRETTY_FUNCTION__); }));

int cmp = 0;
if (CMPZ(z) == 0) {
  *str++ = s_val2ch(0, 1);
} else {
  mp_result res;
  mpz_t tmp;
  char *h, *t;

  if ((res = mp_int_init_copy(&tmp, z)) != MP_OK) return res;

  if (MP_SIGN(z) == MP_NEG) {
    *str++ = '-';
    --limit;
  }
  h = str;

  /* Generate digits in reverse order until finished or limit reached */
  for (/* */; limit > 0; --limit) {
    mp_digit d;

    if ((cmp = CMPZ(&tmp)) == 0) break;

    d = s_ddiv(&tmp, (mp_digit)radix);
    *str++ = s_val2ch(d, 1);
  }
  t = str - 1;

  /* Put digits back in correct output order */
  while (h < t) {
    char tc = *h;
    *h++ = *t;
    *t-- = tc;
  }

  mp_int_clear(&tmp);
}

*str = '\0';
if (cmp == 0) {
  return MP_OK;
} else {
  return MP_TRUNC;
}
1488}

1490mp_result mp_int_string_len(mp_int z, mp_size radix) {
assert(z != NULL)((void) sizeof ((z != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (z != ((void*)0)) ; else __assert_fail ("z != NULL", "polly/lib/External/isl/imath/imath.c"
, 1491, __extension__ __PRETTY_FUNCTION__); }));
assert(radix >= MP_MIN_RADIX && radix <= MP_MAX_RADIX)((void) sizeof ((radix >= 2 && radix <= 36) ? 1
 : 0), __extension__ ({ if (radix >= 2 && radix <=
 36) ; else __assert_fail ("radix >= MP_MIN_RADIX && radix <= MP_MAX_RADIX"
, "polly/lib/External/isl/imath/imath.c", 1492, __extension__
 __PRETTY_FUNCTION__); }));

int len = s_outlen(z, radix) + 1; /* for terminator */

/* Allow for sign marker on negatives */
if (MP_SIGN(z) == MP_NEG) len += 1;

return len;
1500}

1502/* Read zero-terminated string into z */
1503mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str) {
return mp_int_read_cstring(z, radix, str, NULL((void*)0));
1505}

1507mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str,
                            char **end) {
assert(z != NULL && str != NULL)((void) sizeof ((z != ((void*)0) && str != ((void*)0)
) ? 1 : 0), __extension__ ({ if (z != ((void*)0) && str
 != ((void*)0)) ; else __assert_fail ("z != NULL && str != NULL"
, "polly/lib/External/isl/imath/imath.c", 1509, __extension__
 __PRETTY_FUNCTION__); }));
assert(radix >= MP_MIN_RADIX && radix <= MP_MAX_RADIX)((void) sizeof ((radix >= 2 && radix <= 36) ? 1
 : 0), __extension__ ({ if (radix >= 2 && radix <=
 36) ; else __assert_fail ("radix >= MP_MIN_RADIX && radix <= MP_MAX_RADIX"
, "polly/lib/External/isl/imath/imath.c", 1510, __extension__
 __PRETTY_FUNCTION__); }));

/* Skip leading whitespace */
while (isspace((unsigned char)*str)((*__ctype_b_loc ())[(int) (((unsigned char)*str))] & (unsigned
 short int) _ISspace)) ++str;

/* Handle leading sign tag (+/-, positive default) */
switch (*str) {
  case '-':
    z->sign = MP_NEG;
    ++str;
    break;
  case '+':
    ++str; /* fallthrough */
  default:
    z->sign = MP_ZPOS;
    break;
}

/* Skip leading zeroes */
int ch;
while ((ch = s_ch2val(*str, radix)) == 0) ++str;

/* Make sure there is enough space for the value */
if (!s_pad(z, s_inlen(strlen(str), radix))) return MP_MEMORY;

z->used = 1;
z->digits[0] = 0;

while (*str != '\0' && ((ch = s_ch2val(*str, radix)) >= 0)) {
  s_dmul(z, (mp_digit)radix);
  s_dadd(z, (mp_digit)ch);
  ++str;
}

CLAMP(z);

/* Override sign for zero, even if negative specified. */
if (CMPZ(z) == 0) z->sign = MP_ZPOS;

if (end != NULL((void*)0)) *end = (char *)str;

/* Return a truncation error if the string has unprocessed characters
   remaining, so the caller can tell if the whole string was done */
if (*str != '\0') {
  return MP_TRUNC;
} else {
  return MP_OK;
}
1558}

1560mp_result mp_int_count_bits(mp_int z) {
assert(z != NULL)((void) sizeof ((z != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (z != ((void*)0)) ; else __assert_fail ("z != NULL", "polly/lib/External/isl/imath/imath.c"
, 1561, __extension__ __PRETTY_FUNCTION__); }));

mp_size uz = MP_USED(z);
if (uz == 1 && z->digits[0] == 0) return 1;

--uz;
mp_size nbits = uz * MP_DIGIT_BIT(sizeof(mp_digit) * 8);
mp_digit d = z->digits[uz];

while (d != 0) {
  d >>= 1;
  ++nbits;
}

return nbits;
1576}

1578mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit) {
static const int PAD_FOR_2C = 1;

assert(z != NULL && buf != NULL)((void) sizeof ((z != ((void*)0) && buf != ((void*)0)
) ? 1 : 0), __extension__ ({ if (z != ((void*)0) && buf
 != ((void*)0)) ; else __assert_fail ("z != NULL && buf != NULL"
, "polly/lib/External/isl/imath/imath.c", 1581, __extension__
 __PRETTY_FUNCTION__); }));

int limpos = limit;
mp_result res = s_tobin(z, buf, &limpos, PAD_FOR_2C);

if (MP_SIGN(z) == MP_NEG) s_2comp(buf, limpos);

return res;
1589}

1591mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len) {
assert(z != NULL && buf != NULL && len > 0)((void) sizeof ((z != ((void*)0) && buf != ((void*)0)
 && len > 0) ? 1 : 0), __extension__ ({ if (z != (
(void*)0) && buf != ((void*)0) && len > 0)
 ; else __assert_fail ("z != NULL && buf != NULL && len > 0"
, "polly/lib/External/isl/imath/imath.c", 1592, __extension__
 __PRETTY_FUNCTION__); }));

/* Figure out how many digits are needed to represent this value */
mp_size need = ((len * CHAR_BIT8) + (MP_DIGIT_BIT(sizeof(mp_digit) * 8) - 1)) / MP_DIGIT_BIT(sizeof(mp_digit) * 8);
if (!s_pad(z, need)) return MP_MEMORY;

mp_int_zero(z);

/* If the high-order bit is set, take the 2's complement before reading the
   value (it will be restored afterward) */
if (buf[0] >> (CHAR_BIT8 - 1)) {
  z->sign = MP_NEG;
  s_2comp(buf, len);
}

mp_digit *dz = MP_DIGITS(z);
unsigned char *tmp = buf;
for (int i = len; i > 0; --i, ++tmp) {
  s_qmul(z, (mp_size)CHAR_BIT8);
  *dz |= *tmp;
}

/* Restore 2's complement if we took it before */
if (MP_SIGN(z) == MP_NEG) s_2comp(buf, len);

return MP_OK;
1618}

1620mp_result mp_int_binary_len(mp_int z) {
mp_result res = mp_int_count_bits(z);
if (res <= 0) return res;

int bytes = mp_int_unsigned_len(z);

/* If the highest-order bit falls exactly on a byte boundary, we need to pad
   with an extra byte so that the sign will be read correctly when reading it
   back in. */
if (bytes * CHAR_BIT8 == res) ++bytes;

return bytes;
1632}

1634mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit) {
static const int NO_PADDING = 0;

assert(z != NULL && buf != NULL)((void) sizeof ((z != ((void*)0) && buf != ((void*)0)
) ? 1 : 0), __extension__ ({ if (z != ((void*)0) && buf
 != ((void*)0)) ; else __assert_fail ("z != NULL && buf != NULL"
, "polly/lib/External/isl/imath/imath.c", 1637, __extension__
 __PRETTY_FUNCTION__); }));

return s_tobin(z, buf, &limit, NO_PADDING);
1640}

1642mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len) {
assert(z != NULL && buf != NULL && len > 0)((void) sizeof ((z != ((void*)0) && buf != ((void*)0)
 && len > 0) ? 1 : 0), __extension__ ({ if (z != (
(void*)0) && buf != ((void*)0) && len > 0)
 ; else __assert_fail ("z != NULL && buf != NULL && len > 0"
, "polly/lib/External/isl/imath/imath.c", 1643, __extension__
 __PRETTY_FUNCTION__); }));

/* Figure out how many digits are needed to represent this value */
mp_size need = ((len * CHAR_BIT8) + (MP_DIGIT_BIT(sizeof(mp_digit) * 8) - 1)) / MP_DIGIT_BIT(sizeof(mp_digit) * 8);
if (!s_pad(z, need)) return MP_MEMORY;

mp_int_zero(z);

unsigned char *tmp = buf;
for (int i = len; i > 0; --i, ++tmp) {
  (void)s_qmul(z, CHAR_BIT8);
  *MP_DIGITS(z) |= *tmp;
}

return MP_OK;
1658}

1660mp_result mp_int_unsigned_len(mp_int z) {
mp_result res = mp_int_count_bits(z);
if (res <= 0) return res;

int bytes = (res + (CHAR_BIT8 - 1)) / CHAR_BIT8;
return bytes;
1666}

1668const char *mp_error_string(mp_result res) {
if (res > 0) return s_unknown_err;

res = -res;
int ix;
for (ix = 0; ix < res && s_error_msg[ix] != NULL((void*)0); ++ix)
  ;

if (s_error_msg[ix] != NULL((void*)0)) {
  return s_error_msg[ix];
} else {
  return s_unknown_err;
}
1681}

1683/*------------------------------------------------------------------------*/
1684/* Private functions for internal use.  These make assumptions.           */

1686#if DEBUG
1687static const mp_digit fill = (mp_digit)0xdeadbeefabad1dea;
1688#endif

1690static mp_digit *s_alloc(mp_size num) {
mp_digit *out = malloc(num * sizeof(mp_digit));
assert(out != NULL)((void) sizeof ((out != ((void*)0)) ? 1 : 0), __extension__ (
{ if (out != ((void*)0)) ; else __assert_fail ("out != NULL",
 "polly/lib/External/isl/imath/imath.c", 1692, __extension__ __PRETTY_FUNCTION__
); }));

1694#if DEBUG
for (mp_size ix = 0; ix < num; ++ix) out[ix] = fill;
1696#endif
return out;
1698}

1700static mp_digit *s_realloc(mp_digit *old, mp_size osize, mp_size nsize) {
1701#if DEBUG
mp_digit *new = s_alloc(nsize);
assert(new != NULL)((void) sizeof ((new != ((void*)0)) ? 1 : 0), __extension__ (
{ if (new != ((void*)0)) ; else __assert_fail ("new != NULL",
 "polly/lib/External/isl/imath/imath.c", 1703, __extension__ __PRETTY_FUNCTION__
); }));

for (mp_size ix = 0; ix < nsize; ++ix) new[ix] = fill;
memcpy(new, old, osize * sizeof(mp_digit));
1707#else
mp_digit *new = realloc(old, nsize * sizeof(mp_digit));
35
←
Memory is allocated→
assert(new != NULL)((void) sizeof ((new != ((void*)0)) ? 1 : 0), __extension__ (
{ if (new != ((void*)0)) ; else __assert_fail ("new != NULL",
 "polly/lib/External/isl/imath/imath.c", 1709, __extension__ __PRETTY_FUNCTION__
); }));
36
←
Assuming 'new' is not equal to null→
37
←
Taking true branch→
1710#endif

return new;
1713}

1715static void s_free(void *ptr) { free(ptr); }

1717static bool_Bool s_pad(mp_int z, mp_size min) {
if (MP_ALLOC(z) < min) {
31
←
Assuming the condition is true→
32
←
Taking true branch→
  mp_size nsize = s_round_prec(min);
  mp_digit *tmp;

  if (z->digits == &(z->single)) {
33
←
Taking false branch→
    if ((tmp = s_alloc(nsize)) == NULL((void*)0)) return false0;
    tmp[0] = z->single;
  } else if ((tmp = s_realloc(MP_DIGITS(z), MP_ALLOC(z), nsize)) == NULL((void*)0)) {
34
←
Calling 's_realloc'→
38
←
Returned allocated memory→
39
←
Taking false branch→
    return false0;
  }

  z->digits = tmp;
  z->alloc = nsize;
}

return true1;
1734}

1736/* Note: This will not work correctly when value == MP_SMALL_MIN */
1737static void s_fake(mp_int z, mp_small value, mp_digit vbuf[]) {
mp_usmall uv = (mp_usmall)(value < 0) ? -value : value;
s_ufake(z, uv, vbuf);
if (value < 0) z->sign = MP_NEG;
1741}

1743static void s_ufake(mp_int z, mp_usmall value, mp_digit vbuf[]) {
mp_size ndig = (mp_size)s_uvpack(value, vbuf);

z->used = ndig;
z->alloc = MP_VALUE_DIGITS(value)((sizeof(value) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit));
z->sign = MP_ZPOS;
z->digits = vbuf;
1750}

1752static int s_cdig(mp_digit *da, mp_digit *db, mp_size len) {
mp_digit *dat = da + len - 1, *dbt = db + len - 1;

for (/* */; len != 0; --len, --dat, --dbt) {
  if (*dat > *dbt) {
    return 1;
  } else if (*dat < *dbt) {
    return -1;
  }
}

return 0;
1764}

1766static int s_uvpack(mp_usmall uv, mp_digit t[]) {
int ndig = 0;

if (uv == 0)
  t[ndig++] = 0;
else {
  while (uv != 0) {
    t[ndig++] = (mp_digit)uv;
    uv >>= MP_DIGIT_BIT(sizeof(mp_digit) * 8) / 2;
    uv >>= MP_DIGIT_BIT(sizeof(mp_digit) * 8) / 2;
  }
}

return ndig;
1780}

1782static int s_ucmp(mp_int a, mp_int b) {
mp_size ua = MP_USED(a), ub = MP_USED(b);

if (ua > ub) {
  return 1;
} else if (ub > ua) {
  return -1;
} else {
  return s_cdig(MP_DIGITS(a), MP_DIGITS(b), ua);
}
1792}

1794static int s_vcmp(mp_int a, mp_small v) {
mp_usmall uv = (v < 0) ? -(mp_usmall)v : (mp_usmall)v;
return s_uvcmp(a, uv);
1797}

1799static int s_uvcmp(mp_int a, mp_usmall uv) {
mpz_t vtmp;
mp_digit vdig[MP_VALUE_DIGITS(uv)((sizeof(uv) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit))];

s_ufake(&vtmp, uv, vdig);
return s_ucmp(a, &vtmp);
1805}

1807static mp_digit s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a,
                     mp_size size_b) {
mp_size pos;
mp_word w = 0;

/* Insure that da is the longer of the two to simplify later code */
if (size_b > size_a) {
  SWAP(mp_digit *, da, db)do { mp_digit * t_ = (da); da = (db); db = t_; } while (0);
  SWAP(mp_size, size_a, size_b)do { mp_size t_ = (size_a); size_a = (size_b); size_b = t_; }
 while (0);
}

/* Add corresponding digits until the shorter number runs out */
for (pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc) {
  w = w + (mp_word)*da + (mp_word)*db;
  *dc = LOWER_HALF(w);
  w = UPPER_HALF(w);
}

/* Propagate carries as far as necessary */
for (/* */; pos < size_a; ++pos, ++da, ++dc) {
  w = w + *da;

  *dc = LOWER_HALF(w);
  w = UPPER_HALF(w);
}

/* Return carry out */
return (mp_digit)w;
1835}

1837static void s_usub(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a,
                 mp_size size_b) {
mp_size pos;
mp_word w = 0;

/* We assume that |a| >= |b| so this should definitely hold */
assert(size_a >= size_b)((void) sizeof ((size_a >= size_b) ? 1 : 0), __extension__
 ({ if (size_a >= size_b) ; else __assert_fail ("size_a >= size_b"
, "polly/lib/External/isl/imath/imath.c", 1843, __extension__
 __PRETTY_FUNCTION__); }));

/* Subtract corresponding digits and propagate borrow */
for (pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc) {
  w = ((mp_word)MP_DIGIT_MAX((4294967295U) * 1UL) + 1 + /* MP_RADIX */
       (mp_word)*da) -
      w - (mp_word)*db;

  *dc = LOWER_HALF(w);
  w = (UPPER_HALF(w) == 0);
}

/* Finish the subtraction for remaining upper digits of da */
for (/* */; pos < size_a; ++pos, ++da, ++dc) {
  w = ((mp_word)MP_DIGIT_MAX((4294967295U) * 1UL) + 1 + /* MP_RADIX */
       (mp_word)*da) -
      w;

  *dc = LOWER_HALF(w);
  w = (UPPER_HALF(w) == 0);
}

/* If there is a borrow out at the end, it violates the precondition */
assert(w == 0)((void) sizeof ((w == 0) ? 1 : 0), __extension__ ({ if (w == 0
) ; else __assert_fail ("w == 0", "polly/lib/External/isl/imath/imath.c"
, 1866, __extension__ __PRETTY_FUNCTION__); }));
1867}

1869static int s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a,
                mp_size size_b) {
mp_size bot_size;

/* Make sure b is the smaller of the two input values */
if (size_b > size_a) {
  SWAP(mp_digit *, da, db)do { mp_digit * t_ = (da); da = (db); db = t_; } while (0);
  SWAP(mp_size, size_a, size_b)do { mp_size t_ = (size_a); size_a = (size_b); size_b = t_; }
 while (0);
}

/* Insure that the bottom is the larger half in an odd-length split; the code
   below relies on this being true.
 */
bot_size = (size_a + 1) / 2;

/* If the values are big enough to bother with recursion, use the Karatsuba
   algorithm to compute the product; otherwise use the normal multiplication
   algorithm
 */
if (multiply_threshold && size_a >= multiply_threshold && size_b > bot_size) {
  mp_digit *t1, *t2, *t3, carry;

  mp_digit *a_top = da + bot_size;
  mp_digit *b_top = db + bot_size;

  mp_size at_size = size_a - bot_size;
  mp_size bt_size = size_b - bot_size;
  mp_size buf_size = 2 * bot_size;

  /* Do a single allocation for all three temporary buffers needed; each
     buffer must be big enough to hold the product of two bottom halves, and
     one buffer needs space for the completed product; twice the space is
     plenty.
   */
  if ((t1 = s_alloc(4 * buf_size)) == NULL((void*)0)) return 0;
  t2 = t1 + buf_size;
  t3 = t2 + buf_size;
  ZERO(t1, 4 * buf_size);

  /* t1 and t2 are initially used as temporaries to compute the inner product
     (a1 + a0)(b1 + b0) = a1b1 + a1b0 + a0b1 + a0b0
   */
  carry = s_uadd(da, a_top, t1, bot_size, at_size); /* t1 = a1 + a0 */
  t1[bot_size] = carry;

  carry = s_uadd(db, b_top, t2, bot_size, bt_size); /* t2 = b1 + b0 */
  t2[bot_size] = carry;

  (void)s_kmul(t1, t2, t3, bot_size + 1, bot_size + 1); /* t3 = t1 * t2 */

  /* Now we'll get t1 = a0b0 and t2 = a1b1, and subtract them out so that
     we're left with only the pieces we want:  t3 = a1b0 + a0b1
   */
  ZERO(t1, buf_size);
  ZERO(t2, buf_size);
  (void)s_kmul(da, db, t1, bot_size, bot_size);     /* t1 = a0 * b0 */
  (void)s_kmul(a_top, b_top, t2, at_size, bt_size); /* t2 = a1 * b1 */

  /* Subtract out t1 and t2 to get the inner product */
  s_usub(t3, t1, t3, buf_size + 2, buf_size);
  s_usub(t3, t2, t3, buf_size + 2, buf_size);

  /* Assemble the output value */
  COPY(t1, dc, buf_size);
  carry = s_uadd(t3, dc + bot_size, dc + bot_size, buf_size + 1, buf_size);
  assert(carry == 0)((void) sizeof ((carry == 0) ? 1 : 0), __extension__ ({ if (carry
 == 0) ; else __assert_fail ("carry == 0", "polly/lib/External/isl/imath/imath.c"
, 1934, __extension__ __PRETTY_FUNCTION__); }));

  carry =
      s_uadd(t2, dc + 2 * bot_size, dc + 2 * bot_size, buf_size, buf_size);
  assert(carry == 0)((void) sizeof ((carry == 0) ? 1 : 0), __extension__ ({ if (carry
 == 0) ; else __assert_fail ("carry == 0", "polly/lib/External/isl/imath/imath.c"
, 1938, __extension__ __PRETTY_FUNCTION__); }));

  s_free(t1); /* note t2 and t3 are just internal pointers to t1 */
} else {
  s_umul(da, db, dc, size_a, size_b);
}

return 1;
1946}

1948static void s_umul(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a,
                 mp_size size_b) {
mp_size a, b;
mp_word w;

for (a = 0; a < size_a; ++a, ++dc, ++da) {
  mp_digit *dct = dc;
  mp_digit *dbt = db;

  if (*da == 0) continue;

  w = 0;
  for (b = 0; b < size_b; ++b, ++dbt, ++dct) {
    w = (mp_word)*da * (mp_word)*dbt + w + (mp_word)*dct;

    *dct = LOWER_HALF(w);
    w = UPPER_HALF(w);
  }

  *dct = (mp_digit)w;
}
1969}

1971static int s_ksqr(mp_digit *da, mp_digit *dc, mp_size size_a) {
if (multiply_threshold && size_a > multiply_threshold) {
  mp_size bot_size = (size_a + 1) / 2;
  mp_digit *a_top = da + bot_size;
  mp_digit *t1, *t2, *t3, carry;
  mp_size at_size = size_a - bot_size;
  mp_size buf_size = 2 * bot_size;

  if ((t1 = s_alloc(4 * buf_size)) == NULL((void*)0)) return 0;
  t2 = t1 + buf_size;
  t3 = t2 + buf_size;
  ZERO(t1, 4 * buf_size);

  (void)s_ksqr(da, t1, bot_size);   /* t1 = a0 ^ 2 */
  (void)s_ksqr(a_top, t2, at_size); /* t2 = a1 ^ 2 */

  (void)s_kmul(da, a_top, t3, bot_size, at_size); /* t3 = a0 * a1 */

  /* Quick multiply t3 by 2, shifting left (can't overflow) */
  {
    int i, top = bot_size + at_size;
    mp_word w, save = 0;

    for (i = 0; i < top; ++i) {
      w = t3[i];
      w = (w << 1) | save;
      t3[i] = LOWER_HALF(w);
      save = UPPER_HALF(w);
    }
    t3[i] = LOWER_HALF(save);
  }

  /* Assemble the output value */
  COPY(t1, dc, 2 * bot_size);
  carry = s_uadd(t3, dc + bot_size, dc + bot_size, buf_size + 1, buf_size);
  assert(carry == 0)((void) sizeof ((carry == 0) ? 1 : 0), __extension__ ({ if (carry
 == 0) ; else __assert_fail ("carry == 0", "polly/lib/External/isl/imath/imath.c"
, 2006, __extension__ __PRETTY_FUNCTION__); }));

  carry =
      s_uadd(t2, dc + 2 * bot_size, dc + 2 * bot_size, buf_size, buf_size);
  assert(carry == 0)((void) sizeof ((carry == 0) ? 1 : 0), __extension__ ({ if (carry
 == 0) ; else __assert_fail ("carry == 0", "polly/lib/External/isl/imath/imath.c"
, 2010, __extension__ __PRETTY_FUNCTION__); }));

  s_free(t1); /* note that t2 and t2 are internal pointers only */

} else {
  s_usqr(da, dc, size_a);
}

return 1;
2019}

2021static void s_usqr(mp_digit *da, mp_digit *dc, mp_size size_a) {
mp_size i, j;
mp_word w;

for (i = 0; i < size_a; ++i, dc += 2, ++da) {
  mp_digit *dct = dc, *dat = da;

  if (*da == 0) continue;

  /* Take care of the first digit, no rollover */
  w = (mp_word)*dat * (mp_word)*dat + (mp_word)*dct;
  *dct = LOWER_HALF(w);
  w = UPPER_HALF(w);
  ++dat;
  ++dct;

  for (j = i + 1; j < size_a; ++j, ++dat, ++dct) {
    mp_word t = (mp_word)*da * (mp_word)*dat;
    mp_word u = w + (mp_word)*dct, ov = 0;

    /* Check if doubling t will overflow a word */
    if (HIGH_BIT_SET(t)) ov = 1;

    w = t + t;

    /* Check if adding u to w will overflow a word */
    if (ADD_WILL_OVERFLOW(w, u)) ov = 1;

    w += u;

    *dct = LOWER_HALF(w);
    w = UPPER_HALF(w);
    if (ov) {
      w += MP_DIGIT_MAX((4294967295U) * 1UL); /* MP_RADIX */
      ++w;
    }
  }

  w = w + *dct;
  *dct = (mp_digit)w;
  while ((w = UPPER_HALF(w)) != 0) {
    ++dct;
    w = w + *dct;
    *dct = LOWER_HALF(w);
  }

  assert(w == 0)((void) sizeof ((w == 0) ? 1 : 0), __extension__ ({ if (w == 0
) ; else __assert_fail ("w == 0", "polly/lib/External/isl/imath/imath.c"
, 2067, __extension__ __PRETTY_FUNCTION__); }));
}
2069}

2071static void s_dadd(mp_int a, mp_digit b) {
mp_word w = 0;
mp_digit *da = MP_DIGITS(a);
mp_size ua = MP_USED(a);

w = (mp_word)*da + b;
*da++ = LOWER_HALF(w);
w = UPPER_HALF(w);

for (ua -= 1; ua > 0; --ua, ++da) {
  w = (mp_word)*da + w;

  *da = LOWER_HALF(w);
  w = UPPER_HALF(w);
}

if (w) {
  *da = (mp_digit)w;
  a->used += 1;
}
2091}

2093static void s_dmul(mp_int a, mp_digit b) {
mp_word w = 0;
mp_digit *da = MP_DIGITS(a);
mp_size ua = MP_USED(a);

while (ua > 0) {
  w = (mp_word)*da * b + w;
  *da++ = LOWER_HALF(w);
  w = UPPER_HALF(w);
  --ua;
}

if (w) {
  *da = (mp_digit)w;
  a->used += 1;
}
2109}

2111static void s_dbmul(mp_digit *da, mp_digit b, mp_digit *dc, mp_size size_a) {
mp_word w = 0;

while (size_a > 0) {
  w = (mp_word)*da++ * (mp_word)b + w;

  *dc++ = LOWER_HALF(w);
  w = UPPER_HALF(w);
  --size_a;
}

if (w) *dc = LOWER_HALF(w);
2123}

2125static mp_digit s_ddiv(mp_int a, mp_digit b) {
mp_word w = 0, qdigit;
mp_size ua = MP_USED(a);
mp_digit *da = MP_DIGITS(a) + ua - 1;

for (/* */; ua > 0; --ua, --da) {
  w = (w << MP_DIGIT_BIT(sizeof(mp_digit) * 8)) | *da;

  if (w >= b) {
    qdigit = w / b;
    w = w % b;
  } else {
    qdigit = 0;
  }

  *da = (mp_digit)qdigit;
}

CLAMP(a);
return (mp_digit)w;
2145}

2147static void s_qdiv(mp_int z, mp_size p2) {
mp_size ndig = p2 / MP_DIGIT_BIT(sizeof(mp_digit) * 8), nbits = p2 % MP_DIGIT_BIT(sizeof(mp_digit) * 8);
mp_size uz = MP_USED(z);

if (ndig) {
  mp_size mark;
  mp_digit *to, *from;

  if (ndig >= uz) {
    mp_int_zero(z);
    return;
  }

  to = MP_DIGITS(z);
  from = to + ndig;

  for (mark = ndig; mark < uz; ++mark) {
    *to++ = *from++;
  }

  z->used = uz - ndig;
}

if (nbits) {
  mp_digit d = 0, *dz, save;
  mp_size up = MP_DIGIT_BIT(sizeof(mp_digit) * 8) - nbits;

  uz = MP_USED(z);
  dz = MP_DIGITS(z) + uz - 1;

  for (/* */; uz > 0; --uz, --dz) {
    save = *dz;

    *dz = (*dz >> nbits) | (d << up);
    d = save;
  }

  CLAMP(z);
}

if (MP_USED(z) == 1 && z->digits[0] == 0) z->sign = MP_ZPOS;
2188}

2190static void s_qmod(mp_int z, mp_size p2) {
mp_size start = p2 / MP_DIGIT_BIT(sizeof(mp_digit) * 8) + 1, rest = p2 % MP_DIGIT_BIT(sizeof(mp_digit) * 8);
mp_size uz = MP_USED(z);
mp_digit mask = (1u << rest) - 1;

if (start <= uz) {
  z->used = start;
  z->digits[start - 1] &= mask;
  CLAMP(z);
}
2200}

2202static int s_qmul(mp_int z, mp_size p2) {
mp_size uz, need, rest, extra, i;
mp_digit *from, *to, d;

if (p2 == 0) return 1;

uz = MP_USED(z);
need = p2 / MP_DIGIT_BIT(sizeof(mp_digit) * 8);
rest = p2 % MP_DIGIT_BIT(sizeof(mp_digit) * 8);

/* Figure out if we need an extra digit at the top end; this occurs if the
   topmost `rest' bits of the high-order digit of z are not zero, meaning
   they will be shifted off the end if not preserved */
extra = 0;
if (rest != 0) {
  mp_digit *dz = MP_DIGITS(z) + uz - 1;

  if ((*dz >> (MP_DIGIT_BIT(sizeof(mp_digit) * 8) - rest)) != 0) extra = 1;
}

if (!s_pad(z, uz + need + extra)) return 0;

/* If we need to shift by whole digits, do that in one pass, then
   to back and shift by partial digits.
 */
if (need > 0) {
  from = MP_DIGITS(z) + uz - 1;
  to = from + need;

  for (i = 0; i < uz; ++i) *to-- = *from--;

  ZERO(MP_DIGITS(z), need);
  uz += need;
}

if (rest) {
  d = 0;
  for (i = need, from = MP_DIGITS(z) + need; i < uz; ++i, ++from) {
    mp_digit save = *from;

    *from = (*from << rest) | (d >> (MP_DIGIT_BIT(sizeof(mp_digit) * 8) - rest));
    d = save;
  }

  d >>= (MP_DIGIT_BIT(sizeof(mp_digit) * 8) - rest);
  if (d != 0) {
    *from = d;
    uz += extra;
  }
}

z->used = uz;
CLAMP(z);

return 1;
2257}

2259/* Compute z = 2^p2 - |z|; requires that 2^p2 >= |z|
 The sign of the result is always zero/positive.
*/
2262static int s_qsub(mp_int z, mp_size p2) {
mp_digit hi = (1u << (p2 % MP_DIGIT_BIT(sizeof(mp_digit) * 8))), *zp;
mp_size tdig = (p2 / MP_DIGIT_BIT(sizeof(mp_digit) * 8)), pos;
mp_word w = 0;

if (!s_pad(z, tdig + 1)) return 0;

for (pos = 0, zp = MP_DIGITS(z); pos < tdig; ++pos, ++zp) {
  w = ((mp_word)MP_DIGIT_MAX((4294967295U) * 1UL) + 1) - w - (mp_word)*zp;

  *zp = LOWER_HALF(w);
  w = UPPER_HALF(w) ? 0 : 1;
}

w = ((mp_word)MP_DIGIT_MAX((4294967295U) * 1UL) + 1 + hi) - w - (mp_word)*zp;
*zp = LOWER_HALF(w);

assert(UPPER_HALF(w) != 0)((void) sizeof ((UPPER_HALF(w) != 0) ? 1 : 0), __extension__ (
{ if (UPPER_HALF(w) != 0) ; else __assert_fail ("UPPER_HALF(w) != 0"
, "polly/lib/External/isl/imath/imath.c", 2279, __extension__
 __PRETTY_FUNCTION__); })); /* no borrow out should be possible */

z->sign = MP_ZPOS;
CLAMP(z);

return 1;
2285}

2287static int s_dp2k(mp_int z) {
int k = 0;
mp_digit *dp = MP_DIGITS(z), d;

if (MP_USED(z) == 1 && *dp == 0) return 1;

while (*dp == 0) {
  k += MP_DIGIT_BIT(sizeof(mp_digit) * 8);
  ++dp;
}

d = *dp;
while ((d & 1) == 0) {
  d >>= 1;
  ++k;
}

return k;
2305}

2307static int s_isp2(mp_int z) {
mp_size uz = MP_USED(z), k = 0;
mp_digit *dz = MP_DIGITS(z), d;

while (uz > 1) {
  if (*dz++ != 0) return -1;
  k += MP_DIGIT_BIT(sizeof(mp_digit) * 8);
  --uz;
}

d = *dz;
while (d > 1) {
  if (d & 1) return -1;
  ++k;
  d >>= 1;
}

return (int)k;
2325}

2327static int s_2expt(mp_int z, mp_small k) {
mp_size ndig, rest;
mp_digit *dz;

ndig = (k + MP_DIGIT_BIT(sizeof(mp_digit) * 8)) / MP_DIGIT_BIT(sizeof(mp_digit) * 8);
rest = k % MP_DIGIT_BIT(sizeof(mp_digit) * 8);

if (!s_pad(z, ndig)) return 0;

dz = MP_DIGITS(z);
ZERO(dz, ndig);
*(dz + ndig - 1) = (1u << rest);
z->used = ndig;

return 1;
2342}

2344static int s_norm(mp_int a, mp_int b) {
mp_digit d = b->digits[MP_USED(b) - 1];
int k = 0;

while (d < (1u << (mp_digit)(MP_DIGIT_BIT(sizeof(mp_digit) * 8) - 1))) { /* d < (MP_RADIX / 2) */
  d <<= 1;
  ++k;
}

/* These multiplications can't fail */
if (k != 0) {
  (void)s_qmul(a, (mp_size)k);
  (void)s_qmul(b, (mp_size)k);
}

return k;
2360}

2362static mp_result s_brmu(mp_int z, mp_int m) {
mp_size um = MP_USED(m) * 2;

if (!s_pad(z, um)) return MP_MEMORY;

s_2expt(z, MP_DIGIT_BIT(sizeof(mp_digit) * 8) * um);
return mp_int_div(z, m, z, NULL((void*)0));
2369}

2371static int s_reduce(mp_int x, mp_int m, mp_int mu, mp_int q1, mp_int q2) {
mp_size um = MP_USED(m), umb_p1, umb_m1;

umb_p1 = (um + 1) * MP_DIGIT_BIT(sizeof(mp_digit) * 8);
umb_m1 = (um - 1) * MP_DIGIT_BIT(sizeof(mp_digit) * 8);

if (mp_int_copy(x, q1) != MP_OK) return 0;

/* Compute q2 = floor((floor(x / b^(k-1)) * mu) / b^(k+1)) */
s_qdiv(q1, umb_m1);
UMUL(q1, mu, q2);
s_qdiv(q2, umb_p1);

/* Set x = x mod b^(k+1) */
s_qmod(x, umb_p1);

/* Now, q is a guess for the quotient a / m.
   Compute x - q * m mod b^(k+1), replacing x.  This may be off
   by a factor of 2m, but no more than that.
 */
UMUL(q2, m, q1);
s_qmod(q1, umb_p1);
(void)mp_int_sub(x, q1, x); /* can't fail */

/* The result may be < 0; if it is, add b^(k+1) to pin it in the proper
   range. */
if ((CMPZ(x) < 0) && !s_qsub(x, umb_p1)) return 0;

/* If x > m, we need to back it off until it is in range.  This will be
   required at most twice.  */
if (mp_int_compare(x, m) >= 0) {
  (void)mp_int_sub(x, m, x);
  if (mp_int_compare(x, m) >= 0) {
    (void)mp_int_sub(x, m, x);
  }
}

/* At this point, x has been properly reduced. */
return 1;
2410}

2412/* Perform modular exponentiation using Barrett's method, where mu is the
 reduction constant for m.  Assumes a < m, b > 0. */
2414static mp_result s_embar(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c) {
mp_digit umu = MP_USED(mu);
mp_digit *db = MP_DIGITS(b);
mp_digit *dbt = db + MP_USED(b) - 1;

DECLARE_TEMP(3)struct { mpz_t value[(3)]; int len; mp_result err; } temp_ = {
 .len = (3), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
REQUIRE(GROW(TEMP(0), 4 * umu))do { temp_.err = (GROW((temp_.value + (0)), 4 * umu)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(GROW(TEMP(1), 4 * umu))do { temp_.err = (GROW((temp_.value + (1)), 4 * umu)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(GROW(TEMP(2), 4 * umu))do { temp_.err = (GROW((temp_.value + (2)), 4 * umu)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
ZERO(TEMP(0)(temp_.value + (0))->digits, TEMP(0)(temp_.value + (0))->alloc);
ZERO(TEMP(1)(temp_.value + (1))->digits, TEMP(1)(temp_.value + (1))->alloc);
ZERO(TEMP(2)(temp_.value + (2))->digits, TEMP(2)(temp_.value + (2))->alloc);

(void)mp_int_set_value(c, 1);

/* Take care of low-order digits */
while (db < dbt) {
  mp_digit d = *db;

  for (int i = MP_DIGIT_BIT(sizeof(mp_digit) * 8); i > 0; --i, d >>= 1) {
    if (d & 1) {
      /* The use of a second temporary avoids allocation */
      UMUL(c, a, TEMP(0)(temp_.value + (0)));
      if (!s_reduce(TEMP(0)(temp_.value + (0)), m, mu, TEMP(1)(temp_.value + (1)), TEMP(2)(temp_.value + (2)))) {
        REQUIRE(MP_MEMORY)do { temp_.err = (MP_MEMORY); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
      }
      mp_int_copy(TEMP(0)(temp_.value + (0)), c);
    }

    USQR(a, TEMP(0)(temp_.value + (0)));
    assert(MP_SIGN(TEMP(0)) == MP_ZPOS)((void) sizeof ((MP_SIGN((temp_.value + (0))) == MP_ZPOS) ? 1
 : 0), __extension__ ({ if (MP_SIGN((temp_.value + (0))) == MP_ZPOS
) ; else __assert_fail ("MP_SIGN(TEMP(0)) == MP_ZPOS", "polly/lib/External/isl/imath/imath.c"
, 2444, __extension__ __PRETTY_FUNCTION__); }));
    if (!s_reduce(TEMP(0)(temp_.value + (0)), m, mu, TEMP(1)(temp_.value + (1)), TEMP(2)(temp_.value + (2)))) {
      REQUIRE(MP_MEMORY)do { temp_.err = (MP_MEMORY); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
    }
    assert(MP_SIGN(TEMP(0)) == MP_ZPOS)((void) sizeof ((MP_SIGN((temp_.value + (0))) == MP_ZPOS) ? 1
 : 0), __extension__ ({ if (MP_SIGN((temp_.value + (0))) == MP_ZPOS
) ; else __assert_fail ("MP_SIGN(TEMP(0)) == MP_ZPOS", "polly/lib/External/isl/imath/imath.c"
, 2448, __extension__ __PRETTY_FUNCTION__); }));
    mp_int_copy(TEMP(0)(temp_.value + (0)), a);
  }

  ++db;
}

/* Take care of highest-order digit */
mp_digit d = *dbt;
for (;;) {
  if (d & 1) {
    UMUL(c, a, TEMP(0)(temp_.value + (0)));
    if (!s_reduce(TEMP(0)(temp_.value + (0)), m, mu, TEMP(1)(temp_.value + (1)), TEMP(2)(temp_.value + (2)))) {
      REQUIRE(MP_MEMORY)do { temp_.err = (MP_MEMORY); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
    }
    mp_int_copy(TEMP(0)(temp_.value + (0)), c);
  }

  d >>= 1;
  if (!d) break;

  USQR(a, TEMP(0)(temp_.value + (0)));
  if (!s_reduce(TEMP(0)(temp_.value + (0)), m, mu, TEMP(1)(temp_.value + (1)), TEMP(2)(temp_.value + (2)))) {
    REQUIRE(MP_MEMORY)do { temp_.err = (MP_MEMORY); if (temp_.err != MP_OK) goto CLEANUP
; } while (0);
  }
  (void)mp_int_copy(TEMP(0)(temp_.value + (0)), a);
}

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return MP_OK;
2478}

2480/* Division of nonnegative integers

 This function implements division algorithm for unsigned multi-precision
 integers. The algorithm is based on Algorithm D from Knuth's "The Art of
 Computer Programming", 3rd ed. 1998, pg 272-273.

 We diverge from Knuth's algorithm in that we do not perform the subtraction
 from the remainder until we have determined that we have the correct
 quotient digit. This makes our algorithm less efficient that Knuth because
 we might have to perform multiple multiplication and comparison steps before
 the subtraction. The advantage is that it is easy to implement and ensure
 correctness without worrying about underflow from the subtraction.

 inputs: u   a n+m digit integer in base b (b is 2^MP_DIGIT_BIT)
         v   a n   digit integer in base b (b is 2^MP_DIGIT_BIT)
         n >= 1
         m >= 0
outputs: u / v stored in u
         u % v stored in v
*/
2500static mp_result s_udiv_knuth(mp_int u, mp_int v) {
/* Force signs to positive */
u->sign = MP_ZPOS;
v->sign = MP_ZPOS;

/* Use simple division algorithm when v is only one digit long */
if (MP_USED(v) == 1) {
  mp_digit d, rem;
  d = v->digits[0];
  rem = s_ddiv(u, d);
  mp_int_set_value(v, rem);
  return MP_OK;
}

/* Algorithm D

   The n and m variables are defined as used by Knuth.
   u is an n digit number with digits u_{n-1}..u_0.
   v is an n+m digit number with digits from v_{m+n-1}..v_0.
   We require that n > 1 and m >= 0
 */
mp_size n = MP_USED(v);
mp_size m = MP_USED(u) - n;
assert(n > 1)((void) sizeof ((n > 1) ? 1 : 0), __extension__ ({ if (n >
 1) ; else __assert_fail ("n > 1", "polly/lib/External/isl/imath/imath.c"
, 2523, __extension__ __PRETTY_FUNCTION__); }));
/* assert(m >= 0) follows because m is unsigned. */

/* D1: Normalize.
   The normalization step provides the necessary condition for Theorem B,
   which states that the quotient estimate for q_j, call it qhat

     qhat = u_{j+n}u_{j+n-1} / v_{n-1}

   is bounded by

    qhat - 2 <= q_j <= qhat.

   That is, qhat is always greater than the actual quotient digit q,
   and it is never more than two larger than the actual quotient digit.
 */
int k = s_norm(u, v);

/* Extend size of u by one if needed.

   The algorithm begins with a value of u that has one more digit of input.
   The normalization step sets u_{m+n}..u_0 = 2^k * u_{m+n-1}..u_0. If the
   multiplication did not increase the number of digits of u, we need to add
   a leading zero here.
 */
if (k == 0 || MP_USED(u) != m + n + 1) {
  if (!s_pad(u, m + n + 1)) return MP_MEMORY;
  u->digits[m + n] = 0;
  u->used = m + n + 1;
}

/* Add a leading 0 to v.

   The multiplication in step D4 multiplies qhat * 0v_{n-1}..v_0.  We need to
   add the leading zero to v here to ensure that the multiplication will
   produce the full n+1 digit result.
 */
if (!s_pad(v, n + 1)) return MP_MEMORY;
v->digits[n] = 0;

/* Initialize temporary variables q and t.
   q allocates space for m+1 digits to store the quotient digits
   t allocates space for n+1 digits to hold the result of q_j*v
 */
DECLARE_TEMP(2)struct { mpz_t value[(2)]; int len; mp_result err; } temp_ = {
 .len = (2), .err = MP_OK, }; do { for (int i = 0; i < temp_
.len; i++) { mp_int_init((temp_.value + (i))); } } while (0);
REQUIRE(GROW(TEMP(0), m + 1))do { temp_.err = (GROW((temp_.value + (0)), m + 1)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);
REQUIRE(GROW(TEMP(1), n + 1))do { temp_.err = (GROW((temp_.value + (1)), n + 1)); if (temp_
.err != MP_OK) goto CLEANUP; } while (0);

/* D2: Initialize j */
int j = m;
mpz_t r;
r.digits = MP_DIGITS(u) + j; /* The contents of r are shared with u */
r.used = n + 1;
r.sign = MP_ZPOS;
r.alloc = MP_ALLOC(u);
ZERO(TEMP(1)(temp_.value + (1))->digits, TEMP(1)(temp_.value + (1))->alloc);

/* Calculate the m+1 digits of the quotient result */
for (; j >= 0; j--) {
  /* D3: Calculate q' */
  /* r->digits is aligned to position j of the number u */
  mp_word pfx, qhat;
  pfx = r.digits[n];
  pfx <<= MP_DIGIT_BIT(sizeof(mp_digit) * 8) / 2;
  pfx <<= MP_DIGIT_BIT(sizeof(mp_digit) * 8) / 2;
  pfx |= r.digits[n - 1]; /* pfx = u_{j+n}{j+n-1} */

  qhat = pfx / v->digits[n - 1];
  /* Check to see if qhat > b, and decrease qhat if so.
     Theorem B guarantess that qhat is at most 2 larger than the
     actual value, so it is possible that qhat is greater than
     the maximum value that will fit in a digit */
  if (qhat > MP_DIGIT_MAX((4294967295U) * 1UL)) qhat = MP_DIGIT_MAX((4294967295U) * 1UL);

  /* D4,D5,D6: Multiply qhat * v and test for a correct value of q

     We proceed a bit different than the way described by Knuth. This way is
     simpler but less efficent. Instead of doing the multiply and subtract
     then checking for underflow, we first do the multiply of qhat * v and
     see if it is larger than the current remainder r. If it is larger, we
     decrease qhat by one and try again. We may need to decrease qhat one
     more time before we get a value that is smaller than r.

     This way is less efficent than Knuth because we do more multiplies, but
     we do not need to worry about underflow this way.
   */
  /* t = qhat * v */
  s_dbmul(MP_DIGITS(v), (mp_digit)qhat, TEMP(1)(temp_.value + (1))->digits, n + 1);
  TEMP(1)(temp_.value + (1))->used = n + 1;
  CLAMP(TEMP(1)(temp_.value + (1)));

  /* Clamp r for the comparison. Comparisons do not like leading zeros. */
  CLAMP(&r);
  if (s_ucmp(TEMP(1)(temp_.value + (1)), &r) > 0) { /* would the remainder be negative? */
    qhat -= 1;                   /* try a smaller q */
    s_dbmul(MP_DIGITS(v), (mp_digit)qhat, TEMP(1)(temp_.value + (1))->digits, n + 1);
    TEMP(1)(temp_.value + (1))->used = n + 1;
    CLAMP(TEMP(1)(temp_.value + (1)));
    if (s_ucmp(TEMP(1)(temp_.value + (1)), &r) > 0) { /* would the remainder be negative? */
      assert(qhat > 0)((void) sizeof ((qhat > 0) ? 1 : 0), __extension__ ({ if (
qhat > 0) ; else __assert_fail ("qhat > 0", "polly/lib/External/isl/imath/imath.c"
, 2622, __extension__ __PRETTY_FUNCTION__); }));
      qhat -= 1; /* try a smaller q */
      s_dbmul(MP_DIGITS(v), (mp_digit)qhat, TEMP(1)(temp_.value + (1))->digits, n + 1);
      TEMP(1)(temp_.value + (1))->used = n + 1;
      CLAMP(TEMP(1)(temp_.value + (1)));
    }
    assert(s_ucmp(TEMP(1), &r) <= 0 && "The mathematics failed us.")((void) sizeof ((s_ucmp((temp_.value + (1)), &r) <= 0 &&
 "The mathematics failed us.") ? 1 : 0), __extension__ ({ if (
s_ucmp((temp_.value + (1)), &r) <= 0 && "The mathematics failed us."
) ; else __assert_fail ("s_ucmp(TEMP(1), &r) <= 0 && \"The mathematics failed us.\""
, "polly/lib/External/isl/imath/imath.c", 2628, __extension__
 __PRETTY_FUNCTION__); }));
  }
  /* Unclamp r. The D algorithm expects r = u_{j+n}..u_j to always be n+1
     digits long. */
  r.used = n + 1;

  /* D4: Multiply and subtract

     Note: The multiply was completed above so we only need to subtract here.
   */
  s_usub(r.digits, TEMP(1)(temp_.value + (1))->digits, r.digits, r.used, TEMP(1)(temp_.value + (1))->used);

  /* D5: Test remainder

     Note: Not needed because we always check that qhat is the correct value
           before performing the subtract.  Value cast to mp_digit to prevent
           warning, qhat has been clamped to MP_DIGIT_MAX
   */
  TEMP(0)(temp_.value + (0))->digits[j] = (mp_digit)qhat;

  /* D6: Add back
     Note: Not needed because we always check that qhat is the correct value
           before performing the subtract.
   */

  /* D7: Loop on j */
  r.digits--;
  ZERO(TEMP(1)(temp_.value + (1))->digits, TEMP(1)(temp_.value + (1))->alloc);
}

/* Get rid of leading zeros in q */
TEMP(0)(temp_.value + (0))->used = m + 1;
CLAMP(TEMP(0)(temp_.value + (0)));

/* Denormalize the remainder */
CLAMP(u); /* use u here because the r.digits pointer is off-by-one */
if (k != 0) s_qdiv(u, k);

mp_int_copy(u, v);       /* ok:  0 <= r < v */
mp_int_copy(TEMP(0)(temp_.value + (0)), u); /* ok:  q <= u     */

CLEANUP_TEMP()CLEANUP: do { for (int i = 0; i < temp_.len; i++) { mp_int_clear
((temp_.value + (i))); } if (temp_.err != MP_OK) { return temp_
.err; } } while (0);
return MP_OK;
2671}

2673static int s_outlen(mp_int z, mp_size r) {
assert(r >= MP_MIN_RADIX && r <= MP_MAX_RADIX)((void) sizeof ((r >= 2 && r <= 36) ? 1 : 0), __extension__
 ({ if (r >= 2 && r <= 36) ; else __assert_fail
 ("r >= MP_MIN_RADIX && r <= MP_MAX_RADIX", "polly/lib/External/isl/imath/imath.c"
, 2674, __extension__ __PRETTY_FUNCTION__); }));

mp_result bits = mp_int_count_bits(z);
double raw = (double)bits * s_log2[r];

return (int)(raw + 0.999999);
2680}

2682static mp_size s_inlen(int len, mp_size r) {
double raw = (double)len / s_log2[r];
mp_size bits = (mp_size)(raw + 0.5);

return (mp_size)((bits + (MP_DIGIT_BIT(sizeof(mp_digit) * 8) - 1)) / MP_DIGIT_BIT(sizeof(mp_digit) * 8)) + 1;
2687}

2689static int s_ch2val(char c, int r) {
int out;

/*
 * In some locales, isalpha() accepts characters outside the range A-Z,
 * producing out<0 or out>=36.  The "out >= r" check will always catch
 * out>=36.  Though nothing explicitly catches out<0, our caller reacts the
 * same way to every negative return value.
 */
if (isdigit((unsigned char)c)((*__ctype_b_loc ())[(int) (((unsigned char)c))] & (unsigned
 short int) _ISdigit))
  out = c - '0';
else if (r > 10 && isalpha((unsigned char)c)((*__ctype_b_loc ())[(int) (((unsigned char)c))] & (unsigned
 short int) _ISalpha))
  out = toupper((unsigned char)c)(__extension__ ({ int __res; if (sizeof ((unsigned char)c) >
 1) { if (__builtin_constant_p ((unsigned char)c)) { int __c =
 ((unsigned char)c); __res = __c < -128 || __c > 255 ? __c
 : (*__ctype_toupper_loc ())[__c]; } else __res = toupper ((unsigned
 char)c); } else __res = (*__ctype_toupper_loc ())[(int) ((unsigned
 char)c)]; __res; })) - 'A' + 10;
else
  return -1;

return (out >= r) ? -1 : out;
2706}

2708static char s_val2ch(int v, int caps) {
assert(v >= 0)((void) sizeof ((v >= 0) ? 1 : 0), __extension__ ({ if (v >=
 0) ; else __assert_fail ("v >= 0", "polly/lib/External/isl/imath/imath.c"
, 2709, __extension__ __PRETTY_FUNCTION__); }));

if (v < 10) {
  return v + '0';
} else {
  char out = (v - 10) + 'a';

  if (caps) {
    return toupper((unsigned char)out)(__extension__ ({ int __res; if (sizeof ((unsigned char)out) >
 1) { if (__builtin_constant_p ((unsigned char)out)) { int __c
 = ((unsigned char)out); __res = __c < -128 || __c > 255
 ? __c : (*__ctype_toupper_loc ())[__c]; } else __res = toupper
 ((unsigned char)out); } else __res = (*__ctype_toupper_loc (
))[(int) ((unsigned char)out)]; __res; }));
  } else {
    return out;
  }
}
2722}

2724static void s_2comp(unsigned char *buf, int len) {
unsigned short s = 1;

for (int i = len - 1; i >= 0; --i) {
  unsigned char c = ~buf[i];

  s = c + s;
  c = s & UCHAR_MAX(127*2 +1);
  s >>= CHAR_BIT8;

  buf[i] = c;
}

/* last carry out is ignored */
2738}

2740static mp_result s_tobin(mp_int z, unsigned char *buf, int *limpos, int pad) {
int pos = 0, limit = *limpos;
mp_size uz = MP_USED(z);
mp_digit *dz = MP_DIGITS(z);

while (uz > 0 && pos < limit) {
  mp_digit d = *dz++;
  int i;

  for (i = sizeof(mp_digit); i > 0 && pos < limit; --i) {
    buf[pos++] = (unsigned char)d;
    d >>= CHAR_BIT8;

    /* Don't write leading zeroes */
    if (d == 0 && uz == 1) i = 0; /* exit loop without signaling truncation */
  }

  /* Detect truncation (loop exited with pos >= limit) */
  if (i > 0) break;

  --uz;
}

if (pad != 0 && (buf[pos - 1] >> (CHAR_BIT8 - 1))) {
  if (pos < limit) {
    buf[pos++] = 0;
  } else {
    uz = 1;
  }
}

/* Digits are in reverse order, fix that */
REV(buf, pos);

/* Return the number of bytes actually written */
*limpos = pos;

return (uz == 0) ? MP_OK : MP_TRUNC;
2778}

2780/* Here there be dragons */