1 files changed, 377 insertions, 0 deletions

diff --git a/polly/lib/External/isl/imath/ChangeLog b/polly/lib/External/isl/imath/ChangeLog
new file mode 100644
index 00000000000..5222475d084
--- /dev/null
+++ b/polly/lib/External/isl/imath/ChangeLog
@@ -0,0 +1,377 @@
+1.0.1
+	First released version.
+
+1.0.2
+	Fixed a bug in mp_int_div() which would yield incorrect quotients
+	when the divisor was very close in value to a prefix of the
+	dividend.  This is now fixed, and there are regression tests in
+	the tests directory.
+
+	Added recursive multiplication and squaring (Karatsuba-Ofman) for
+	large input values.  Integrated these with the existing code for
+	exponentiation, too.  See the code for s_kmul() and s_ksqr() in
+	imath.c.  Tests added and verified against GNU bc.
+
+	Added documentation on mp_get_multiply_threshold() and the reason
+	why it exists.
+
+1.0.3
+	Fixed a couple of bugs in pi.c that were causing incorrect values
+	to be computed for > 30 digits or so.  Added a pi-computation test
+	to the default test suite (make test), checked against a static
+	file computed by bc (set scale=1024, compute 4 * atan(1)).  Added
+	command line option to specify output radix for pi.
+
+	Cleaned up a sign-related bug in mp_int_gcd(), which would cause
+	the sign of gcd(0, x) to be incorrect when x < 0.  Test cases
+	added for future regression.
+
+	Fixed a bug in s_reduce() which would give incorrect results for
+	powers of 2 in certain circumstances.  Added tests to drive this
+	case for future regression.
+
+	Added mp_int_exptmod_evalue() and mp_int_exptmod_bvalue() to make
+	it easier to work with small bases and small exponents.
+
+	Set default recursive multiplication threshold to 50 digits, since
+	this seems to work best for the platforms I've tested so far.
+
+	Added iprime.h and iprime.c to the distribution.
+
+1.0.4
+	Added `findsizes.pl' to the distribution.
+
+	Revised the type declarations in imath.h to use 32/64 bit
+	operations where the "long long" type is supported.
+
+	Fixed a sign-related bug in mp_int_invmod().
+
+	Fixed several small bugs related to shifting which affect the use
+	of 32-bit digits.  Many architectures cannot shift by 32 bits at a
+	time (e.g., MIPS), so I split each of these cases into two shifts
+	of half the size, which should scale properly for both the smaller
+	and larger cases.
+
+	Fixed several arithmetic issues with 32-bit digits that arose due
+	to missing type-casts on the right-hand sides of assignments.
+
+	Fixed s_print() and s_print_buf() to handle the sizes of digits
+	transparently.
+
+1.0.5
+	Updated the Makefile to include the _GNU_SOURCE macro.  For many
+	GCC systems, this is necessary to get the correct definition of
+	the ULLONG_MAX macro in <limits.h>.  Also, you may now build with
+	the make option DEBUG=Y to enable debugging, e.g.:
+
+	make DEBUG=Y imtest
+
+	By default, the Makefile builds with the optimizer enabled.
+
+	Cleaned up the definitions triggered by USE_LONG_LONG in imath.h,
+	and added an #error instruction in case the build is unable to
+	find a definition of ULLONG_MAX or ULONG_LONG_MAX in <limits.h>.
+	Also added the mp_int_to_unsigned(), mp_int_read_unsigned(), and
+	mp_int_unsigned_len() prototypes.
+
+	Fixed a bug in s_qmul() [imath.c:2493] that would grow the value
+	being multiplied even if there was room in the existing digits to
+	hold the result.  This was driving an (apparent) bug in the more
+	general mp_int_read_binary() routine.  Added the routines
+	mentioned in the previous paragraph, and factored some common
+	code out into a static s_tobin().
+
+	Added reset_registers() to imdrover.{h,c}.  Added new test
+	driver functions test_to_uns() and test_read_uns().  Renamed
+	test_read_bin to test_read_binary().
+
+	Silenced a sign-related warning in pi.c (related to printf).
+
+	Added many new test vectors to tests/conv.t, including the
+	original bug proof-of-concept from Tom Wu, and a series of new
+	tests for the unsigned conversion routines.
+
+	Updated `doc.txt' to reflect the changes described above.
+
+1.0.6
+	Updated copyright notices, added LICENSE file explaining the
+	license I am using.  This is basically the BSD license, so
+	you should have no trouble incorporating this code into other
+	open source projects.
+
+	No new functionality in this release.
+
+1.0.7
+	The mp_int_invmod(a, m, c) function would compute a negative value
+	for c when given a < 0.  I added some code to insure that the value
+	returned is always the least non-negative member of the congruence
+	class, if the inverse exists.  A test for this was added to invmod.t.
+
+1.0.8
+	Fixed a small buffer-overrun in s_qmul().  Because it only
+	allocates an extra digit if it absolutely has to, the test for
+	whether it needs to carry a shift out into the "spare" digit had
+	to be written carefully; I missed a subtlety, which is now
+	fixed. Along the way, I fixed a minor performance-related bug in
+	the same routine.
+
+	Added mp_int_error_string(), which converts mp_result values
+	into descriptive strings.  These are statically allocated, so
+	you don't have to free them.
+
+	This version also adds an "examples" subdirectory.  Currently,
+	there is only one program there, but I will add more examples as
+	time permits me.  You have to read the source to understand them
+	anyway, so I won't explain them here.
+
+1.1.0
+	Added imrat.h and imrat.c, containing routines for rational number
+	arithmetic at arbitrary precision.  Added support to the test driver,
+	in imath.c and included various tests in the tests/ subdirectory.
+
+	Fixed a sign-of-zero bug in mp_int_mul().  Tests added to mul.t to
+	regress this fix.
+
+1.1.2
+	Fixed a bug with leading zeroes after the decimal point in the
+	mp_rat_read_decimal() function (imrat.c).  Along the way, I also
+	found a sign-related bug, in which -0.5 would be treated as if it
+	were positive, because the sign of zero is implicitly positive,
+	and the denominator is treated as unsigned always.
+
+	Thanks to Eric Silva for pointing out the leading zeroes bug.
+	The solution isn't the most efficient possible.
+
+1.1.3
+	Rewrote mp_int_to_decimal() to support new rounding modes.  The
+	modes are documented in doc.txt.  Some of the code sucked anyway,
+	so I rewrote pretty much the entire function.
+
+	Added new rounding mode constants.
+
+1.1.4
+	Added mixed rational/integer operations:
+	  mp_rat_add_int, mp_rat_sub_int, mp_rat_mul_int, mp_rat_div_int
+	Added rational exponentiation (with integer exponents):
+	  mp_rat_expt
+
+	Tests for same were added to the tests/ subdirectory.
+
+1.1.5
+	Added mp_rat_read_cdecimal() and mp_rat_read_ustring()
+	Updated the input.c example.
+
+1.1.6
+	Fixed a bug in mp_int_read_cstring() which would read the string
+	"-0" with incorrect sign (MP_NEG instead of MP_ZPOS).  This would
+	violate an invariant that zero is always signed with positives.
+
+	Added some tests to tests/neg.t to catch this case.
+
+1.1.7
+	Fixed a bug in s_udiv(), internal to imath.c, which caused
+	division to fail in some corner cases masked by the use of long
+	long as a word type.  As a result, s_udiv() has now been wholly
+	rewritten.  I also fixed a few lingering buffer-length errors in
+	s_kmul(), and added a "const" qualifier to the input buffers for
+	the mp_int_read_string() and mp_int_read_cstring() functions,
+	and their analogs in imrat.c.
+
+1.1.8
+	Added mp_int_alloc() and mp_int_free().
+
+1.1.9
+	Added mp_rat_alloc() and mp_rat_free().  Fixed a couple of minor
+	bugs in the doc.txt file.  Added mp_int_sqrt() to imath.{h,c} and
+	doc.txt.
+
+1.2
+	Dropped bugfix component of revision number.  Fixed rsakey.c
+	example program to be complete and work faster.
+
+1.3
+	Replaced findsizes.pl with findsizes.py.  Fixed two bugs in the
+	rsakey tool that were leading to incorrect output.
+
+1.4
+	Fixed a bug in mp_int_alloc(), it was not returning NULL when out
+	of memory, but rather failing in assert() instead.  Also, updated
+	the documentation to have better language about the return values
+	in various error conditions.
+
+1.5
+	Changed the API for rational rounding.  Removed the two functions
+	mp_rat_set_rounding() and mp_rat_get_rounding(), along with the
+	round_output global variable.  Redefined the MP_ROUND_* constants
+	as an enumeration type (mp_round_mode).  Added a new parameter to
+	the mp_rat_to_decimal() function to accept a rounding mode.  Unit
+	tests and doc.txt updated suitably.
+
+	This release also incorporates a small patch submitted by Jonathan
+	Shapiro to support compilation in C++.
+
+1.6
+	Defined default_precision and multiply_threshold to be constant
+	and static.  If IMATH_TEST is defined at compile time, these are
+	made global, and can be modified by the caller (the imtimer tool
+	makes use of this ability, for example).
+
+	Implemented a single-digit optimization suggested by J. Shapiro.
+	Documentation updated.
+
+1.7
+	Fixed a subtle casting problem in the use of the ctype macros that
+	would permit negative signed character values to produce illogical
+	behaviour in some configurations (e.g., NetBSD).  Removed a dead
+	"return" statement.
+
+	Added the -pedantic switch for gcc, to get more aggressive
+	warnings; to permit the nonstandard "long long" type to still be
+	used, I also added -Wno-long-long when building with long long
+	enabled (the standard configuration).
+
+	Fixed a bug found by the Samba team running Valgrind on the
+	Heimdal project, and reported by Love Hörnquist Âstrand:  One of
+	the intermediate values used during modular exponentiation could
+	be overflowed during recursive multiplication.  Fixed by taking a
+	more conservative approach to buffer sizing.
+
+	Added a "contrib" subdirectory, whose first entry is a Makefile
+	to build IMath with the MSVC++ "nmake" program, contributed by
+	Matus Horvath.
+
+1.8
+	Fixed a bug in s_udiv() affecting the computation of quotient
+	digits.  Thanks to Love Âstrand for isolating this bug.  Also in
+	this release, defining USELLONG=Y or USELLONG=N on the command
+	line for make will switch support for the "long long" data type on
+	or off without having to edit the Makefile.  The default is still
+	to permit use of "long long", even though the type is not standard
+	ANSI C90.
+
+1.9
+	Increased the number of small primes used for primality testing to
+	100 from 32.  Removed an unwanted #define from imath.c, left over
+	from testing; added "static" to the declaration of the s_embar()
+	internal function since it is not used outside imath.c.  Reduced
+	the quantity of feedback generated by rsakey.c during the prime
+	finding stage of key generation.
+
+1.10
+	All primes less than 1000 are now used in iprime.c for preliminary
+	testing of prime candidates.  Removed declaration of s_pad() from
+	rsakey.c example.  Added imcalc.c example.
+
+	Beginning with this release, defining the DEBUG preprocessor macro
+	when compiling imath.c causes all the normally-static helper
+	functions to be exported.  This makes it easier to troubleshoot
+	bugs in the back end functions without manually editing the source
+	till you have found where the bug actually is.
+
+	Fixed a memory leak in the test driver (imtest.c) where the input
+	buffers allocated for test specs were not released before being
+	released.  No impact on the core routines, but nevertheless not a
+	good thing.
+
+	Fixed several uninitialized memory reads and one subtle read past
+	the end of a buffer in s_kmul(), found during a run of Purify.
+	Thanks to Love Hörnquist Âstrand for finding this one, and
+	providing a good test case so I could isolate the problem.  Also
+	fixed a buglet in s_kmul(), in which free() was being called
+	instead of s_free(), which would break if you provided a custom
+	version of s_alloc() and s_free() for your application.
+
+1.11
+	Those functions which take int parameters to supply one or more of
+	the arithmetic values of the function have been converted to use a
+	typedef "mp_small".  This is defined in imath.h, along with some
+	supporting macros.
+
+	Added mp_int_to_uint() and mp_int_lcm() in imath.{h,c}, based on a
+	patch contributed by Hal Finkel.  Added LCM tests as as well as
+	some more GCD tests in tests/lcm.t and tests/gcd.t
+
+	Also at Hal Finkel's request, added mp_int_root() to compute the
+	integer nth root, i.e., \lfloor a^{1/b}\rfloor; replaced the old
+	mp_int_sqrt() function with a call to mp_int_root() via a macro.
+	The new implementation is probably slightly less efficient for
+	square roots, but more general.  Added tests/root.t and moved the
+	sqrt tests there, also.
+
+1.12
+	Added a new global constant MP_MINERR which is the value of the
+	smallest error code defined by IMath itself.  This can be used by
+	clients who wish to define and use additional error codes, so that
+	those codes will not conflict with the existing set.
+
+	Extended the imcalc example to include memory.
+
+	Fixed a bug in mp_int_add() in which -1 + 1 = -0 (the sign of zero
+	was recorded incorrectly).  Added tests to the regression suite
+	for this fix.
+
+1.13
+	Cosmetic change -- updated all the files with my new web address.
+
+	Fixed a buglet caught by Love Hörnquist Âstrand using the LLVM
+	static checker tools, in which a mp_int_copy() failure would be
+	silently ignored and cause an extra copy to be generated.
+
+	Fixed a bug in the testing suite while building on MinGW.  The pi
+	generation tests compare to static files and these tests fail if
+	CR/LF is output instead of just LF.  The test script now strips
+	all CR and LF from the output and compares to files lacking them.
+	Reported by Chris Cole <cjcole@gmail.com>.
+
+1.14
+	Instead of using the preprocessor to delete "static", the static
+	definitions in imath.c now use an explicit STATIC macro, that is
+	made null when DEBUG is defined.  This avoids a subtle problem
+	with static variables defined inside functions (although no bugs
+	actually arose from it).
+
+	Fixed a bug in s_udiv() while building on MinGW.  When building
+	with short type digits, the routine was incorrectly discarding
+	overflow when computing the next quotient digit.
+	Reported by Paul DeMarco <pdemarco@ppg.com>.
+
+1.15
+	Fixed a bug in the definition of MP_DIGIT_MAX that caused errors
+	when IMath is built under 64-bit Linux.  Reported by
+	Klaus Stengel <klaus.stengel@informatik.stud.uni-erlangen.de>.
+
+	Unpacked the macro definitions in imath.c a bit, to make them more
+	readable.
+
+	Added mp_int_expt_full() by request of Andrea Barberio
+	<insomniac@slackware.it>.
+
+1.16
+	Fixed a bug in mp_int_to_uint() which was causing incorrect MP_RANGE
+	errors during small integer conversion.
+	Reported by Andrea Barberio <insomniac@slackware.it>
+
+	Added mp_int_compare_uvalue().
+	Added some new testing hooks in imtest.c, new unit tests.
+
+	Made some code style changes that do not affect functionality.
+
+1.17
+	Fixed a bug in mp_int_swap() where mpz_t structures using their single
+	field as storage would not get swapped correctly.
+	Reported by Andres Navarro <canavarro82@gmail.com>
+
+	Added regression test for this and some hooks for future
+	regressions in the tests/test.sh script.
+
+1.18
+	Made mp_int_rat() use mp_int_init() to initialize numerator and
+	denominator instead of mp_int_init_size().
+	Some minor code cleanup inside the testing code (imdrover.c).
+
+	Fixed an off-by-one bug in s_udiv() which could cause the quotient
+	guessing loop to spin.  Reported by Andres Navarro.  Added
+	triggering example to div.t as a regression test.
+
+1.19
+	Fix signedness error in compile.  Reported by Paweł Sikora.