564 lines · plain
11.0.12 First released version.3 41.0.25 Fixed a bug in mp_int_div() which would yield incorrect quotients6 when the divisor was very close in value to a prefix of the7 dividend. This is now fixed, and there are regression tests in8 the tests directory.9 10 Added recursive multiplication and squaring (Karatsuba-Ofman) for11 large input values. Integrated these with the existing code for12 exponentiation, too. See the code for s_kmul() and s_ksqr() in13 imath.c. Tests added and verified against GNU bc.14 15 Added documentation on mp_get_multiply_threshold() and the reason16 why it exists.17 181.0.319 Fixed a couple of bugs in pi.c that were causing incorrect values20 to be computed for > 30 digits or so. Added a pi-computation test21 to the default test suite (make test), checked against a static22 file computed by bc (set scale=1024, compute 4 * atan(1)). Added23 command line option to specify output radix for pi.24 25 Cleaned up a sign-related bug in mp_int_gcd(), which would cause26 the sign of gcd(0, x) to be incorrect when x < 0. Test cases27 added for future regression.28 29 Fixed a bug in s_reduce() which would give incorrect results for30 powers of 2 in certain circumstances. Added tests to drive this31 case for future regression.32 33 Added mp_int_exptmod_evalue() and mp_int_exptmod_bvalue() to make34 it easier to work with small bases and small exponents.35 36 Set default recursive multiplication threshold to 50 digits, since37 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.442 Added `findsizes.pl' to the distribution.43 44 Revised the type declarations in imath.h to use 32/64 bit45 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 use50 of 32-bit digits. Many architectures cannot shift by 32 bits at a51 time (e.g., MIPS), so I split each of these cases into two shifts52 of half the size, which should scale properly for both the smaller53 and larger cases.54 55 Fixed several arithmetic issues with 32-bit digits that arose due56 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 digits59 transparently.60 611.0.562 Updated the Makefile to include the _GNU_SOURCE macro. For many63 GCC systems, this is necessary to get the correct definition of64 the ULLONG_MAX macro in <limits.h>. Also, you may now build with65 the make option DEBUG=Y to enable debugging, e.g.:66 67 make DEBUG=Y imtest68 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 to73 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(), and75 mp_int_unsigned_len() prototypes.76 77 Fixed a bug in s_qmul() [imath.c:2493] that would grow the value78 being multiplied even if there was room in the existing digits to79 hold the result. This was driving an (apparent) bug in the more80 general mp_int_read_binary() routine. Added the routines81 mentioned in the previous paragraph, and factored some common82 code out into a static s_tobin().83 84 Added reset_registers() to imdrover.{h,c}. Added new test85 driver functions test_to_uns() and test_read_uns(). Renamed86 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 the91 original bug proof-of-concept from Tom Wu, and a series of new92 tests for the unsigned conversion routines.93 94 Updated `doc.txt' to reflect the changes described above.95 961.0.697 Updated copyright notices, added LICENSE file explaining the98 license I am using. This is basically the BSD license, so99 you should have no trouble incorporating this code into other100 open source projects.101 102 No new functionality in this release.103 1041.0.7105 The mp_int_invmod(a, m, c) function would compute a negative value106 for c when given a < 0. I added some code to insure that the value107 returned is always the least non-negative member of the congruence108 class, if the inverse exists. A test for this was added to invmod.t.109 1101.0.8111 Fixed a small buffer-overrun in s_qmul(). Because it only112 allocates an extra digit if it absolutely has to, the test for113 whether it needs to carry a shift out into the "spare" digit had114 to be written carefully; I missed a subtlety, which is now115 fixed. Along the way, I fixed a minor performance-related bug in116 the same routine.117 118 Added mp_int_error_string(), which converts mp_result values119 into descriptive strings. These are statically allocated, so120 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 as124 time permits me. You have to read the source to understand them125 anyway, so I won't explain them here.126 1271.1.0128 Added imrat.h and imrat.c, containing routines for rational number129 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 to133 regress this fix.134 1351.1.2136 Fixed a bug with leading zeroes after the decimal point in the137 mp_rat_read_decimal() function (imrat.c). Along the way, I also138 found a sign-related bug, in which -0.5 would be treated as if it139 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.3146 Rewrote mp_int_to_decimal() to support new rounding modes. The147 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.4153 Added mixed rational/integer operations:154 mp_rat_add_int, mp_rat_sub_int, mp_rat_mul_int, mp_rat_div_int155 Added rational exponentiation (with integer exponents):156 mp_rat_expt157 158 Tests for same were added to the tests/ subdirectory.159 1601.1.5161 Added mp_rat_read_cdecimal() and mp_rat_read_ustring()162 Updated the input.c example.163 1641.1.6165 Fixed a bug in mp_int_read_cstring() which would read the string166 "-0" with incorrect sign (MP_NEG instead of MP_ZPOS). This would167 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.7172 Fixed a bug in s_udiv(), internal to imath.c, which caused173 division to fail in some corner cases masked by the use of long174 long as a word type. As a result, s_udiv() has now been wholly175 rewritten. I also fixed a few lingering buffer-length errors in176 s_kmul(), and added a "const" qualifier to the input buffers for177 the mp_int_read_string() and mp_int_read_cstring() functions,178 and their analogs in imrat.c.179 1801.1.8181 Added mp_int_alloc() and mp_int_free().182 1831.1.9184 Added mp_rat_alloc() and mp_rat_free(). Fixed a couple of minor185 bugs in the doc.txt file. Added mp_int_sqrt() to imath.{h,c} and186 doc.txt.187 1881.2189 Dropped bugfix component of revision number. Fixed rsakey.c190 example program to be complete and work faster.191 1921.3193 Replaced findsizes.pl with findsizes.py. Fixed two bugs in the194 rsakey tool that were leading to incorrect output.195 1961.4197 Fixed a bug in mp_int_alloc(), it was not returning NULL when out198 of memory, but rather failing in assert() instead. Also, updated199 the documentation to have better language about the return values200 in various error conditions.201 2021.5203 Changed the API for rational rounding. Removed the two functions204 mp_rat_set_rounding() and mp_rat_get_rounding(), along with the205 round_output global variable. Redefined the MP_ROUND_* constants206 as an enumeration type (mp_round_mode). Added a new parameter to207 the mp_rat_to_decimal() function to accept a rounding mode. Unit208 tests and doc.txt updated suitably.209 210 This release also incorporates a small patch submitted by Jonathan211 Shapiro to support compilation in C++.212 2131.6214 Defined default_precision and multiply_threshold to be constant215 and static. If IMATH_TEST is defined at compile time, these are216 made global, and can be modified by the caller (the imtimer tool217 makes use of this ability, for example).218 219 Implemented a single-digit optimization suggested by J. Shapiro.220 Documentation updated.221 2221.7223 Fixed a subtle casting problem in the use of the ctype macros that224 would permit negative signed character values to produce illogical225 behaviour in some configurations (e.g., NetBSD). Removed a dead226 "return" statement.227 228 Added the -pedantic switch for gcc, to get more aggressive229 warnings; to permit the nonstandard "long long" type to still be230 used, I also added -Wno-long-long when building with long long231 enabled (the standard configuration).232 233 Fixed a bug found by the Samba team running Valgrind on the234 Heimdal project, and reported by Love Hörnquist Âstrand: One of235 the intermediate values used during modular exponentiation could236 be overflowed during recursive multiplication. Fixed by taking a237 more conservative approach to buffer sizing.238 239 Added a "contrib" subdirectory, whose first entry is a Makefile240 to build IMath with the MSVC++ "nmake" program, contributed by241 Matus Horvath.242 2431.8244 Fixed a bug in s_udiv() affecting the computation of quotient245 digits. Thanks to Love Âstrand for isolating this bug. Also in246 this release, defining USELLONG=Y or USELLONG=N on the command247 line for make will switch support for the "long long" data type on248 or off without having to edit the Makefile. The default is still249 to permit use of "long long", even though the type is not standard250 ANSI C90.251 2521.9253 Increased the number of small primes used for primality testing to254 100 from 32. Removed an unwanted #define from imath.c, left over255 from testing; added "static" to the declaration of the s_embar()256 internal function since it is not used outside imath.c. Reduced257 the quantity of feedback generated by rsakey.c during the prime258 finding stage of key generation.259 2601.10261 All primes less than 1000 are now used in iprime.c for preliminary262 testing of prime candidates. Removed declaration of s_pad() from263 rsakey.c example. Added imcalc.c example.264 265 Beginning with this release, defining the DEBUG preprocessor macro266 when compiling imath.c causes all the normally-static helper267 functions to be exported. This makes it easier to troubleshoot268 bugs in the back end functions without manually editing the source269 till you have found where the bug actually is.270 271 Fixed a memory leak in the test driver (imtest.c) where the input272 buffers allocated for test specs were not released before being273 released. No impact on the core routines, but nevertheless not a274 good thing.275 276 Fixed several uninitialized memory reads and one subtle read past277 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, and279 providing a good test case so I could isolate the problem. Also280 fixed a buglet in s_kmul(), in which free() was being called281 instead of s_free(), which would break if you provided a custom282 version of s_alloc() and s_free() for your application.283 2841.11285 Those functions which take int parameters to supply one or more of286 the arithmetic values of the function have been converted to use a287 typedef "mp_small". This is defined in imath.h, along with some288 supporting macros.289 290 Added mp_int_to_uint() and mp_int_lcm() in imath.{h,c}, based on a291 patch contributed by Hal Finkel. Added LCM tests as as well as292 some more GCD tests in tests/lcm.t and tests/gcd.t293 294 Also at Hal Finkel's request, added mp_int_root() to compute the295 integer nth root, i.e., \lfloor a^{1/b}\rfloor; replaced the old296 mp_int_sqrt() function with a call to mp_int_root() via a macro.297 The new implementation is probably slightly less efficient for298 square roots, but more general. Added tests/root.t and moved the299 sqrt tests there, also.300 3011.12302 Added a new global constant MP_MINERR which is the value of the303 smallest error code defined by IMath itself. This can be used by304 clients who wish to define and use additional error codes, so that305 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 zero310 was recorded incorrectly). Added tests to the regression suite311 for this fix.312 3131.13314 Cosmetic change -- updated all the files with my new web address.315 316 Fixed a buglet caught by Love Hörnquist Âstrand using the LLVM317 static checker tools, in which a mp_int_copy() failure would be318 silently ignored and cause an extra copy to be generated.319 320 Fixed a bug in the testing suite while building on MinGW. The pi321 generation tests compare to static files and these tests fail if322 CR/LF is output instead of just LF. The test script now strips323 all CR and LF from the output and compares to files lacking them.324 Reported by Chris Cole <cjcole@gmail.com>.325 3261.14327 Instead of using the preprocessor to delete "static", the static328 definitions in imath.c now use an explicit STATIC macro, that is329 made null when DEBUG is defined. This avoids a subtle problem330 with static variables defined inside functions (although no bugs331 actually arose from it).332 333 Fixed a bug in s_udiv() while building on MinGW. When building334 with short type digits, the routine was incorrectly discarding335 overflow when computing the next quotient digit.336 Reported by Paul DeMarco <pdemarco@ppg.com>.337 3381.15339 Fixed a bug in the definition of MP_DIGIT_MAX that caused errors340 when IMath is built under 64-bit Linux. Reported by341 Klaus Stengel <klaus.stengel@informatik.stud.uni-erlangen.de>.342 343 Unpacked the macro definitions in imath.c a bit, to make them more344 readable.345 346 Added mp_int_expt_full() by request of Andrea Barberio347 <insomniac@slackware.it>.348 3491.16350 Fixed a bug in mp_int_to_uint() which was causing incorrect MP_RANGE351 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.17360 Fixed a bug in mp_int_swap() where mpz_t structures using their single361 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 future365 regressions in the tests/test.sh script.366 3671.18368 Made mp_int_rat() use mp_int_init() to initialize numerator and369 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 quotient373 guessing loop to spin. Reported by Andres Navarro. Added374 triggering example to div.t as a regression test.375 3761.19377 Fix signedness error in compile. Reported by Paweł Sikora.378 3791.20380 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.21385 Fix a syntax error. TODO: Run tests before merging, or better386 still set up CI someplace.387 Remove dead division code.388 Restore a missing comparison.389 Drop dead flags from the Makefile.390 3911.22392 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.23397 Portability fixes from PostgreSQL (#8), from nmisch.398 3991.24400 A cosmetic update, consisting mainly of readability updates,401 documentation fixes, and warning fixes. There are not intended to402 be any functional changes in this update, but a fair bit of code403 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 going406 forward, though I will need to set up some presubmit checks to407 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.25421 This version fixes several issues found by clang static analysis.422 It also includes some additional follow-on cleanup tasks from the423 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.26439 Another round of fixes. Notably the gmp-compat-test again works on440 macOS, fixing https://github.com/creachadair/imath/issues/26.441 Also, this release cleans up some more warnings and fixes some442 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.27454 Another round of cleanup and bug fixes. This release includes a455 Dockerfile to support basic Linux testing, which I found useful as456 I do most of my work on macOS.457 458 This release also addresses most of issue #29 (Switching from C90459 to C99). Part of that change removes most function-like macros460 from the API headers, replacing them with static functions. Code461 that used the macros as lvalues will no longer work, but can and462 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.28496 Another round of cleanup, and some more invasive API changes.497 I removed more macros, and added an API surface for setting the498 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 it501 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.29514 The Documentation Edition. The main improvement here is that the515 API documentation is now unified in the header files, and doc.md516 is now generated from a template that includes the text from the517 headers. The automation for this is still unsatisfactory, but it518 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.30549 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.31559 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