11.0.1 2 First released version. 3 41.0.2 5 Fixed a bug in mp_int_div() which would yield incorrect quotients 6 when the divisor was very close in value to a prefix of the 7 dividend. This is now fixed, and there are regression tests in 8 the tests directory. 9 10 Added recursive multiplication and squaring (Karatsuba-Ofman) for 11 large input values. Integrated these with the existing code for 12 exponentiation, too. See the code for s_kmul() and s_ksqr() in 13 imath.c. Tests added and verified against GNU bc. 14 15 Added documentation on mp_get_multiply_threshold() and the reason 16 why it exists. 17 181.0.3 19 Fixed a couple of bugs in pi.c that were causing incorrect values 20 to be computed for > 30 digits or so. Added a pi-computation test 21 to the default test suite (make test), checked against a static 22 file computed by bc (set scale=1024, compute 4 * atan(1)). Added 23 command line option to specify output radix for pi. 24 25 Cleaned up a sign-related bug in mp_int_gcd(), which would cause 26 the sign of gcd(0, x) to be incorrect when x < 0. Test cases 27 added for future regression. 28 29 Fixed a bug in s_reduce() which would give incorrect results for 30 powers of 2 in certain circumstances. Added tests to drive this 31 case for future regression. 32 33 Added mp_int_exptmod_evalue() and mp_int_exptmod_bvalue() to make 34 it easier to work with small bases and small exponents. 35 36 Set default recursive multiplication threshold to 50 digits, since 37 this seems to work best for the platforms I've tested so far. 38 39 Added iprime.h and iprime.c to the distribution. 40 411.0.4 42 Added `findsizes.pl' to the distribution. 43 44 Revised the type declarations in imath.h to use 32/64 bit 45 operations where the "long long" type is supported. 46 47 Fixed a sign-related bug in mp_int_invmod(). 48 49 Fixed several small bugs related to shifting which affect the use 50 of 32-bit digits. Many architectures cannot shift by 32 bits at a 51 time (e.g., MIPS), so I split each of these cases into two shifts 52 of half the size, which should scale properly for both the smaller 53 and larger cases. 54 55 Fixed several arithmetic issues with 32-bit digits that arose due 56 to missing type-casts on the right-hand sides of assignments. 57 58 Fixed s_print() and s_print_buf() to handle the sizes of digits 59 transparently. 60 611.0.5 62 Updated the Makefile to include the _GNU_SOURCE macro. For many 63 GCC systems, this is necessary to get the correct definition of 64 the ULLONG_MAX macro in <limits.h>. Also, you may now build with 65 the make option DEBUG=Y to enable debugging, e.g.: 66 67 make DEBUG=Y imtest 68 69 By default, the Makefile builds with the optimizer enabled. 70 71 Cleaned up the definitions triggered by USE_LONG_LONG in imath.h, 72 and added an #error instruction in case the build is unable to 73 find a definition of ULLONG_MAX or ULONG_LONG_MAX in <limits.h>. 74 Also added the mp_int_to_unsigned(), mp_int_read_unsigned(), and 75 mp_int_unsigned_len() prototypes. 76 77 Fixed a bug in s_qmul() [imath.c:2493] that would grow the value 78 being multiplied even if there was room in the existing digits to 79 hold the result. This was driving an (apparent) bug in the more 80 general mp_int_read_binary() routine. Added the routines 81 mentioned in the previous paragraph, and factored some common 82 code out into a static s_tobin(). 83 84 Added reset_registers() to imdrover.{h,c}. Added new test 85 driver functions test_to_uns() and test_read_uns(). Renamed 86 test_read_bin to test_read_binary(). 87 88 Silenced a sign-related warning in pi.c (related to printf). 89 90 Added many new test vectors to tests/conv.t, including the 91 original bug proof-of-concept from Tom Wu, and a series of new 92 tests for the unsigned conversion routines. 93 94 Updated `doc.txt' to reflect the changes described above. 95 961.0.6 97 Updated copyright notices, added LICENSE file explaining the 98 license I am using. This is basically the BSD license, so 99 you should have no trouble incorporating this code into other 100 open source projects. 101 102 No new functionality in this release. 103 1041.0.7 105 The mp_int_invmod(a, m, c) function would compute a negative value 106 for c when given a < 0. I added some code to insure that the value 107 returned is always the least non-negative member of the congruence 108 class, if the inverse exists. A test for this was added to invmod.t. 109 1101.0.8 111 Fixed a small buffer-overrun in s_qmul(). Because it only 112 allocates an extra digit if it absolutely has to, the test for 113 whether it needs to carry a shift out into the "spare" digit had 114 to be written carefully; I missed a subtlety, which is now 115 fixed. Along the way, I fixed a minor performance-related bug in 116 the same routine. 117 118 Added mp_int_error_string(), which converts mp_result values 119 into descriptive strings. These are statically allocated, so 120 you don't have to free them. 121 122 This version also adds an "examples" subdirectory. Currently, 123 there is only one program there, but I will add more examples as 124 time permits me. You have to read the source to understand them 125 anyway, so I won't explain them here. 126 1271.1.0 128 Added imrat.h and imrat.c, containing routines for rational number 129 arithmetic at arbitrary precision. Added support to the test driver, 130 in imath.c and included various tests in the tests/ subdirectory. 131 132 Fixed a sign-of-zero bug in mp_int_mul(). Tests added to mul.t to 133 regress this fix. 134 1351.1.2 136 Fixed a bug with leading zeroes after the decimal point in the 137 mp_rat_read_decimal() function (imrat.c). Along the way, I also 138 found a sign-related bug, in which -0.5 would be treated as if it 139 were positive, because the sign of zero is implicitly positive, 140 and the denominator is treated as unsigned always. 141 142 Thanks to Eric Silva for pointing out the leading zeroes bug. 143 The solution isn't the most efficient possible. 144 1451.1.3 146 Rewrote mp_int_to_decimal() to support new rounding modes. The 147 modes are documented in doc.txt. Some of the code sucked anyway, 148 so I rewrote pretty much the entire function. 149 150 Added new rounding mode constants. 151 1521.1.4 153 Added mixed rational/integer operations: 154 mp_rat_add_int, mp_rat_sub_int, mp_rat_mul_int, mp_rat_div_int 155 Added rational exponentiation (with integer exponents): 156 mp_rat_expt 157 158 Tests for same were added to the tests/ subdirectory. 159 1601.1.5 161 Added mp_rat_read_cdecimal() and mp_rat_read_ustring() 162 Updated the input.c example. 163 1641.1.6 165 Fixed a bug in mp_int_read_cstring() which would read the string 166 "-0" with incorrect sign (MP_NEG instead of MP_ZPOS). This would 167 violate an invariant that zero is always signed with positives. 168 169 Added some tests to tests/neg.t to catch this case. 170 1711.1.7 172 Fixed a bug in s_udiv(), internal to imath.c, which caused 173 division to fail in some corner cases masked by the use of long 174 long as a word type. As a result, s_udiv() has now been wholly 175 rewritten. I also fixed a few lingering buffer-length errors in 176 s_kmul(), and added a "const" qualifier to the input buffers for 177 the mp_int_read_string() and mp_int_read_cstring() functions, 178 and their analogs in imrat.c. 179 1801.1.8 181 Added mp_int_alloc() and mp_int_free(). 182 1831.1.9 184 Added mp_rat_alloc() and mp_rat_free(). Fixed a couple of minor 185 bugs in the doc.txt file. Added mp_int_sqrt() to imath.{h,c} and 186 doc.txt. 187 1881.2 189 Dropped bugfix component of revision number. Fixed rsakey.c 190 example program to be complete and work faster. 191 1921.3 193 Replaced findsizes.pl with findsizes.py. Fixed two bugs in the 194 rsakey tool that were leading to incorrect output. 195 1961.4 197 Fixed a bug in mp_int_alloc(), it was not returning NULL when out 198 of memory, but rather failing in assert() instead. Also, updated 199 the documentation to have better language about the return values 200 in various error conditions. 201 2021.5 203 Changed the API for rational rounding. Removed the two functions 204 mp_rat_set_rounding() and mp_rat_get_rounding(), along with the 205 round_output global variable. Redefined the MP_ROUND_* constants 206 as an enumeration type (mp_round_mode). Added a new parameter to 207 the mp_rat_to_decimal() function to accept a rounding mode. Unit 208 tests and doc.txt updated suitably. 209 210 This release also incorporates a small patch submitted by Jonathan 211 Shapiro to support compilation in C++. 212 2131.6 214 Defined default_precision and multiply_threshold to be constant 215 and static. If IMATH_TEST is defined at compile time, these are 216 made global, and can be modified by the caller (the imtimer tool 217 makes use of this ability, for example). 218 219 Implemented a single-digit optimization suggested by J. Shapiro. 220 Documentation updated. 221 2221.7 223 Fixed a subtle casting problem in the use of the ctype macros that 224 would permit negative signed character values to produce illogical 225 behaviour in some configurations (e.g., NetBSD). Removed a dead 226 "return" statement. 227 228 Added the -pedantic switch for gcc, to get more aggressive 229 warnings; to permit the nonstandard "long long" type to still be 230 used, I also added -Wno-long-long when building with long long 231 enabled (the standard configuration). 232 233 Fixed a bug found by the Samba team running Valgrind on the 234 Heimdal project, and reported by Love Hörnquist Âstrand: One of 235 the intermediate values used during modular exponentiation could 236 be overflowed during recursive multiplication. Fixed by taking a 237 more conservative approach to buffer sizing. 238 239 Added a "contrib" subdirectory, whose first entry is a Makefile 240 to build IMath with the MSVC++ "nmake" program, contributed by 241 Matus Horvath. 242 2431.8 244 Fixed a bug in s_udiv() affecting the computation of quotient 245 digits. Thanks to Love Âstrand for isolating this bug. Also in 246 this release, defining USELLONG=Y or USELLONG=N on the command 247 line for make will switch support for the "long long" data type on 248 or off without having to edit the Makefile. The default is still 249 to permit use of "long long", even though the type is not standard 250 ANSI C90. 251 2521.9 253 Increased the number of small primes used for primality testing to 254 100 from 32. Removed an unwanted #define from imath.c, left over 255 from testing; added "static" to the declaration of the s_embar() 256 internal function since it is not used outside imath.c. Reduced 257 the quantity of feedback generated by rsakey.c during the prime 258 finding stage of key generation. 259 2601.10 261 All primes less than 1000 are now used in iprime.c for preliminary 262 testing of prime candidates. Removed declaration of s_pad() from 263 rsakey.c example. Added imcalc.c example. 264 265 Beginning with this release, defining the DEBUG preprocessor macro 266 when compiling imath.c causes all the normally-static helper 267 functions to be exported. This makes it easier to troubleshoot 268 bugs in the back end functions without manually editing the source 269 till you have found where the bug actually is. 270 271 Fixed a memory leak in the test driver (imtest.c) where the input 272 buffers allocated for test specs were not released before being 273 released. No impact on the core routines, but nevertheless not a 274 good thing. 275 276 Fixed several uninitialized memory reads and one subtle read past 277 the end of a buffer in s_kmul(), found during a run of Purify. 278 Thanks to Love Hörnquist Âstrand for finding this one, and 279 providing a good test case so I could isolate the problem. Also 280 fixed a buglet in s_kmul(), in which free() was being called 281 instead of s_free(), which would break if you provided a custom 282 version of s_alloc() and s_free() for your application. 283 2841.11 285 Those functions which take int parameters to supply one or more of 286 the arithmetic values of the function have been converted to use a 287 typedef "mp_small". This is defined in imath.h, along with some 288 supporting macros. 289 290 Added mp_int_to_uint() and mp_int_lcm() in imath.{h,c}, based on a 291 patch contributed by Hal Finkel. Added LCM tests as as well as 292 some more GCD tests in tests/lcm.t and tests/gcd.t 293 294 Also at Hal Finkel's request, added mp_int_root() to compute the 295 integer nth root, i.e., \lfloor a^{1/b}\rfloor; replaced the old 296 mp_int_sqrt() function with a call to mp_int_root() via a macro. 297 The new implementation is probably slightly less efficient for 298 square roots, but more general. Added tests/root.t and moved the 299 sqrt tests there, also. 300 3011.12 302 Added a new global constant MP_MINERR which is the value of the 303 smallest error code defined by IMath itself. This can be used by 304 clients who wish to define and use additional error codes, so that 305 those codes will not conflict with the existing set. 306 307 Extended the imcalc example to include memory. 308 309 Fixed a bug in mp_int_add() in which -1 + 1 = -0 (the sign of zero 310 was recorded incorrectly). Added tests to the regression suite 311 for this fix. 312 3131.13 314 Cosmetic change -- updated all the files with my new web address. 315 316 Fixed a buglet caught by Love Hörnquist Âstrand using the LLVM 317 static checker tools, in which a mp_int_copy() failure would be 318 silently ignored and cause an extra copy to be generated. 319 320 Fixed a bug in the testing suite while building on MinGW. The pi 321 generation tests compare to static files and these tests fail if 322 CR/LF is output instead of just LF. The test script now strips 323 all CR and LF from the output and compares to files lacking them. 324 Reported by Chris Cole <cjcole@gmail.com>. 325 3261.14 327 Instead of using the preprocessor to delete "static", the static 328 definitions in imath.c now use an explicit STATIC macro, that is 329 made null when DEBUG is defined. This avoids a subtle problem 330 with static variables defined inside functions (although no bugs 331 actually arose from it). 332 333 Fixed a bug in s_udiv() while building on MinGW. When building 334 with short type digits, the routine was incorrectly discarding 335 overflow when computing the next quotient digit. 336 Reported by Paul DeMarco <pdemarco@ppg.com>. 337 3381.15 339 Fixed a bug in the definition of MP_DIGIT_MAX that caused errors 340 when IMath is built under 64-bit Linux. Reported by 341 Klaus Stengel <klaus.stengel@informatik.stud.uni-erlangen.de>. 342 343 Unpacked the macro definitions in imath.c a bit, to make them more 344 readable. 345 346 Added mp_int_expt_full() by request of Andrea Barberio 347 <insomniac@slackware.it>. 348 3491.16 350 Fixed a bug in mp_int_to_uint() which was causing incorrect MP_RANGE 351 errors during small integer conversion. 352 Reported by Andrea Barberio <insomniac@slackware.it> 353 354 Added mp_int_compare_uvalue(). 355 Added some new testing hooks in imtest.c, new unit tests. 356 357 Made some code style changes that do not affect functionality. 358 3591.17 360 Fixed a bug in mp_int_swap() where mpz_t structures using their single 361 field as storage would not get swapped correctly. 362 Reported by Andres Navarro <canavarro82@gmail.com> 363 364 Added regression test for this and some hooks for future 365 regressions in the tests/test.sh script. 366 3671.18 368 Made mp_int_rat() use mp_int_init() to initialize numerator and 369 denominator instead of mp_int_init_size(). 370 Some minor code cleanup inside the testing code (imdrover.c). 371 372 Fixed an off-by-one bug in s_udiv() which could cause the quotient 373 guessing loop to spin. Reported by Andres Navarro. Added 374 triggering example to div.t as a regression test. 375 3761.19 377 Fix signedness error in compile. Reported by Paweł Sikora. 378 3791.20 380 Fix broken comments, apparently from a previous bad merge. 381 Remove emacs folding-mode comments throughout. 382 Some minor Makefile cleanup to make clang happier. 383 3841.21 385 Fix a syntax error. TODO: Run tests before merging, or better 386 still set up CI someplace. 387 Remove dead division code. 388 Restore a missing comparison. 389 Drop dead flags from the Makefile. 390 3911.22 392 Remove MP_USMALL_MIN, which was unused by anything in imath. 393 Rework doc.txt into Markdown. 394 Restore imath-test.scm and imath.py, dropped during import. 395 3961.23 397 Portability fixes from PostgreSQL (#8), from nmisch. 398 3991.24 400 A cosmetic update, consisting mainly of readability updates, 401 documentation fixes, and warning fixes. There are not intended to 402 be any functional changes in this update, but a fair bit of code 403 and the Makefile have been modified, so I'm adding a tag. 404 405 My intent is to keep the source formatted with clang-format going 406 forward, though I will need to set up some presubmit checks to 407 enforce that. For now it is still a manual step via "make format". 408 409 7e45d6a Remove a doc reference to MP_USMALL_MIN. 410 544687d Fix the spelling of mp_error_string in doc.md. 411 592d4a0 Fix some mis-converted section breaks in doc.md. 412 df9fe8e Format source files with clang-format. 413 fcb4e21 Build with 64-bit words by default. 414 1579b70 Minor simplifications to the Makefile. 415 0fbe8e6 Style cleanup: More invasive manual changes. 416 1d28177 Add -Wextra and -Wno-unused-parameter to default build flags. 417 15ba02a Fix warnings for signed/unsigned comparisons. 418 3556984 Style cleanup: Insert missing brackets. 419 4201.25 421 This version fixes several issues found by clang static analysis. 422 It also includes some additional follow-on cleanup tasks from the 423 previous release. 424 425 b5a73c4 Cleanup: Use .tc for test files instead of .t. 426 dc307ae Cleanup: Remove dead author URLs, SVN markers. 427 389a1be bug: Fix a memory leak in test_meta. 428 8fb98f7 bug: Fix a use of an uninitalized pointer. 429 fe0757a bug: Fix reads of uninitalized fields in free_test. 430 08fe765 bug: Fix a reachable null pointer indirection. 431 7b10453 bug: Remove a redundant initialization. 432 cebce44 bug: Fix various dead assignments. 433 ef36352 Remove the findsizes.py script. 434 eebfb85 Fix some more comparison-sign mismatches. 435 9abcf66 Cleanup: Update a stale reference to doc.txt in the README. 436 8ec696f Cleanup: Consolidate the USE_32BIT_WORDS macro sections. 437 4381.26 439 Another round of fixes. Notably the gmp-compat-test again works on 440 macOS, fixing https://github.com/creachadair/imath/issues/26. 441 Also, this release cleans up some more warnings and fixes some 442 missing #include paths. 443 444 2ea0fff gmp_compat: Fix warnings for mixed-sign comparisons. 445 2a41bae Fix DLL loading. 446 56c40f4 Make gmp-compat-test work again on macOS. 447 f163906 Comment out a vacuously true assertion. 448 667d90e gmp_compat: Ensure a definition of ssize_t is available. 449 6c6fdd8 Fix a vacuously meaningless comparison. 450 4dac16f Silence a warning about an uninitalized variable. 451 c6119c4 Include strings.h for strcasecmp. 452 4531.27 454 Another round of cleanup and bug fixes. This release includes a 455 Dockerfile to support basic Linux testing, which I found useful as 456 I do most of my work on macOS. 457 458 This release also addresses most of issue #29 (Switching from C90 459 to C99). Part of that change removes most function-like macros 460 from the API headers, replacing them with static functions. Code 461 that used the macros as lvalues will no longer work, but can and 462 should be easily updated to access the members of mpz_t directly. 463 464 Fixed: #34. 465 466 899e202 Add a docker config for basic Linux testing. 467 40e8887 Move imath-test.scm to the tests directory. 468 6f01c9f Add .dockerignore to the release tarball. 469 1dab081 Fix the spelling of __abs__ in imath.py. 470 8f0a00c Enable source formatting for Python. 471 99e27c8 Format all Python source with yapf. 472 bf289f0 gmp-compat-test: Remove dependency on Python 3. 473 9269d57 Clean up the Linux test image. 474 61ca691 Include stdbool.h and use the bool type where appropriate. 475 d4760ee Replace macros with static inline functions. 476 8241977 linux test: Layer the image for better caching. 477 46bb578 imath: Replace accessor macros with inline functions. 478 50c6cc8 imrat: Replace accessor macros with static functions. 479 0c5cec9 gmp_compat: Fix lvalue uses of MP_USED. 480 89c72f2 Remove CHECK and NRCHECK macros. 481 dbe9f50 imath: Replace macros with static functions. 482 0006998 imath: Replace ROUND_PREC macro with a function. 483 b628a0c Move local variable declarations closer to first use. 484 54d51da Remove obsolete division spec. 485 796776f iprime: Move and scope variables closer to first use. 486 8fd5236 iprime: Use a sentinel instead of a length. 487 ce89180 Include getopt.h explicitly where it is required. 488 e6fc170 Make libimath.so build correctly under GCC. 489 b54d8c9 Use Bourne in preference to Bash. 490 8f88c01 Makefile: Export CC and CFLAGS for submakes. 491 58f4392 Use the inherited settings in the gmp-compat-tests. 492 8a181cd Make the Linux docker test run "make check". 493 28617f2 gmp_compat: Fix overflow in the uint conversion adapter. 494 4951.28 496 Another round of cleanup, and some more invasive API changes. 497 I removed more macros, and added an API surface for setting the 498 default precision and recursive-multiply threshold. 499 The compile-time switchable statics are now strictly static. 500 The handling of temporary values was greatly reworked to make it 501 less brittle. 502 503 ba44b37 Add unit tests for mp_int_is_prime. 504 6f10877 imath: Remove lvalue uses of access macros, and the macros. 505 f4939db Fix formatting. 506 85137fa docs: Remove macro implementation comments. 507 37f046e Rework the handling of temporaries. 508 cc8ac74 imtimer: Fix a lingering lvalue use of MP_USED. 509 9736a8b imath: Drop switchable statics and stdio dependency. 510 5445ad8 Add functions to set default precision and multiply threshold. 511 58f2d6e Use alpine:latest rather than a fixed version. 512 5131.29 514 The Documentation Edition. The main improvement here is that the 515 API documentation is now unified in the header files, and doc.md 516 is now generated from a template that includes the text from the 517 headers. The automation for this is still unsatisfactory, but it 518 is better than it was. 519 520 d239b2e Remove imath.py. 521 e43b0f5 imath: Clean up extraneous whitespace. 522 fbbbbad Remove the mpz struct tag. 523 718fef2 imath: Add documentation comments to the header. 524 02600e5 imath: Make radix bound checks into requirements. 525 c21f49d imrat: Add documentation comments to the header. 526 ea5398f Remove the mpq struct tag. 527 c1549c7 Move tools and tests into subdirectories. 528 7187c49 Remove extraneous whitespace from declarations. 529 afa715c Comment cleanup on Aisle 2. 530 cbf9a03 Add tools/mkdoc.py. 531 58672fc Remove the "dist" target from Makefile. 532 894bb90 Move rtest.c into the tests directory. 533 d4cfc69 Add a doc.md.in template file. 534 bd929aa Add a make rule for doc.md from doc.md.in. 535 6dea44e Update doc.md using the new generator. 536 56ef9a0 doc: Include mp_int_set_uvalue. 537 13618b3 doc: Explain the comparator terminology. 538 9990b2e Make the clean and distclean make-rules equivalent. 539 13df978 doc: Update the explanation of temp handling macros. 540 b80bd8a doc: Emit one generated comment for the whole file. 541 3cde6b8 doc: Remove the markdown disclaimer. 542 045a2a6 doc: Point my address to github instead of e-mail. 543 08f2efd doc: Add headings for general API functions. 544 77159d9 mkdoc.py: Link back to source lines. 545 aec8587 doc: Include links back to the source. 546 f8c9f6c imath: Document a constraint on mp_int_redux_const. 547 5481.30 549 Improve test automation; no functional changes to the library. 550 551 fc7846a imtest: Ensure the exit code is non-zero when tests fail. 552 87edcbe test.sh: Exit non-zero if any unit tests fail. 553 276d1f9 imtest: Make test output easier to read. 554 c8c90c4 Make the Linux test protocol less brittle. 555 f68ba5b Add a .gitattributes file. 556 33c2843 Add a docker-test target to the Makefile. 557 5581.31 559 Improvements to build and test automation; add CI configuration. 560 561 d419633 Add a Travis CI configuration for imath. 562 3305c4a Ensure the Makefile respects a $CC set in the environment. 563 d2da4b6 Update instructions for reporting bugs. 564