summaryrefslogtreecommitdiffstats
path: root/mpi
Commit message (Collapse)AuthorAgeFilesLines
* mpi: enforce testing of some return values.Kaz Kylheku2017-06-181-32/+38
| | | | | | | | | | | | | | | | Using a feature of GCC, we mark some functions with the warn_unused_result attribute. Specifically, those functions which could return the MP_TOOBIG overflow error. * mpi/mpi.h (mp_nign): New macro. (mp_init_size, mp_add_d, mp_sub_d, mp_mul_d, mp_mul_2, mp_div_d, mp_div_2, mp_expt_d, mp_add, mp_sub, mp_mul, mp_mul_2d, mp_sqr, mp_expt, mp_2expt, mp_sqrt, mp_addmod, mp_submod, mp_mulmod, mp_sqrmod, mp_exptmod, mp_exptmod_d, mp_lcm, mp_xgcd, mp_invmod, mp_trunc_comp, mp_trunc, mp_shift, mp_to_double, mp_read_signed_bin, mp_read_unsigned_bin, mp_read_radix): Functions attributed with unused result warning.
* mpi: introduce clamp on number of digits.Kaz Kylheku2017-06-183-2/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The main purpose of this patch is to prevent two cases of numeric overflow. One is when an arithmetic operation produces a result which would have more digits than can be represented by mp_size. The calculation for the digits in the result operand will simply overflow, resulting in an undersized buffer that is then overrun. Another overflow is in calculations which work with bit indexing. Even if the digits is in range of mp_size, the bit number is eight times larger and can be out of range. We can address both problems by clamping integers to have only so many digits, that every bit has an offset that fits into mp_size. If mp_size is 32 bits, that means we can still have bignums that are half a gigabyte, which seems reasonable for nearly any conceivable application of bignums. After this patch, we must adjust the code in arith.c and other places to detect errors, at least out of the functions that can produce larger integers than their inputs. * mpi/mpi-types.h (MP_MAX_BITS, MP_MAX_DIGITS): New macro. * mpi/mpi.c (mp_err_string): New entry corresponding to the new MP_TOOBIG error. (mp_init_size, s_mp_grow): Reject, with the MP_TOOBIG error, attemps to create or grow an mp_int mp_int such that it would have more digits than MP_MAX_DIGITS. * mpi/mpi.h (MP_TOOBIG): New macro code. (MP_LAST_CODE): Redefined to MP_TOOBIG.
* mpi: avoid OOB pointer decr in two descending loops.Kaz Kylheku2017-06-181-10/+12
| | | | | | | | | | | * mpi.c (s_mp_cmp): Rewrite loop as a for with a bottom test, and the increments in the usual place. ap and bp aren't decremented if the index is zero. Ironic to fix this, given that we march through the stack in the garbage collector. (s_mp_ispow2): Similar restructuring, with an additional guard around ix being set up to descend from the second-to-last digit.
* mpi: smaller default precision.Kaz Kylheku2017-06-181-1/+1
| | | | * mpi/mpi-config.h (MP_DEFPREC): Change from 16 to 8.
* mpi: fix some careless use of integer types.Kaz Kylheku2017-06-185-119/+126
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | MPI has a mp_size type for sizing of the digit arrays and some other uses. It is not consistently used. Moreover, it is typedef'd as a signed type. The type int is used for iterating over digits, instead of the matching mpi_size type. The int type is used as a size argument in some functions, and in functions that return the number of bits. This patch makes mp_size unsigned and replaces most uses of int with a more appropriate type. Because mp_size is now used for indexing, and is unsigned, some downward loop termination tests have to be changed; the always true condition ix >= 0 cannot be used. * arith.c (width): Use mp_size for local variable which iterates over digits inside mpi_int object, and for bit count. Use unum to convert bit count to Lisp integer: mp_size could be out of range of cnum. * mpi/mpi-types.h (mp_size): Typedef to unsigned. (MP_SIZE_MAX): New macro. (MP_DIGIT_BIT, MP_WORD_BIT): Cast the value to mp_size rather than to int. * mpi/mpi.c (s_mp_defprec): Declare variable as mp_size. (s_mp_setz, s_mp_copy, mp_size, s_highest_bit_mp, s_mp_set_bit, s_mp_ispow2, s_mp_outlen, mp_set_int, mp_set_uintptr, mp_set_double_intptr, mp_expt, mp_sqrt, mp_exptmod, mp_hash, mp_gcd, mp_shift, mp_bit, mp_to_double, mp_print, mp_read_signed_bin, mp_signed_bin_size, mp_read_unsigned_bin, mp_unsigned_bin_size, mp_to_unsigned_bin, mp_to_unsigned_buf, mp_count_bits, mp_is_pow_two, mp_read_radix, mp_radix_size, mp_value_radix_size, mp_toradix_case, s_mp_setz, s_mp_copy, mp_size, s_highest_bit_mp, s_mp_set_bit, s_mp_mul_2, s_mp_mod_2d, s_mp_div_2d, s_mp_div_d, s_mp_sqr, s_mp_sqr, s_mp_div, s_mp_cmp, s_mp_cmp_d, s_mp_ispow2, s_mp_outlen): In all these functions, use size_t for external size, mp_size for number of digits and bits, in return values, arguments and local variables. Tests in descending loops are adjusted for unsigned logic. * mpi/mpi.h (mp_get_prec, mp_set_prec, mp_read_signed_bin, mp_signed_bin_size, mp_read_unsigned_bin, mp_unsigned_bin_size, mp_to_unsigned_buf, mp_count_bits, mp_is_pow_two, mp_radix_size, mp_value_radix_size): Declarations updated. * mpi/mplogic.c (mpl_not, mpl_and, mpl_or, mpl_xor, mpl_rsh, mpl_lsh, mpl_num_set, mpl_num_clear, mpl_parity): Just like in mpi.c * rand.c (make_random_state): Use mp_size and ucnum for local variables holding digit and bit counts. * sysif.c (off_t_num): Use mp_size for digit count.
* Big MPI whitepace and comment cleanup.Kaz Kylheku2017-06-147-2413/+1445
| | | | | | | | * mpi/logtab.h, mpi/mpi-config.h mpi/mpi-types.h mpi/mpi.c, mpi/mpi.h mpi/mplogic.c mpi/mplogic.h: Reformatted comments. Removed useless comments. Removed superfluous blank lines and whitespace. Added space between C keywords if, for, while, sizeof and opening parens. Removed #if 0 blocks. Tabs to spaces.
* Fix some C style casts to use casting macros.Kaz Kylheku2016-12-071-1/+1
| | | | | | | | | | | | | | | | | | | | This is uncovered by compiling with g++ using -Wold-style-cast. * mpi/mpi.c (mp_get_intptr): Use convert macro. Also in one of the rules producing REGCHAR. * parser.l (num_esc): Likewise. * struct.c (static_slot_set, static_slot_ens_rec, get_equal_method): Use coerce macro for int to pointer conversion. * sysif.c (setgroups_wrap): Use convert macro. * termios.c (termios_unpack, termios_pack): Likewise. * txr.c (sysroot_init): Likewise.
* mpi: must clamp result of conversion to bignum.Kaz Kylheku2016-11-151-0/+3
| | | | | | * mpi/mpi.c (mp_set_uintptr, mp_set_double_intptr): The value of z might not require all of the digits implied by the size of its C data type. We must clamp the result to trim trailing zero limbs from the bignum.
* mpi: eliminate trailing whitespace.Kaz Kylheku2016-11-142-104/+69
| | | | | | | | | * mpi/mpi-config.h: Eliminate several trailing spaces. * mpi/mpi.c: Eliminate all trailing spaces. Removed some commented-out code, and adjusted brace placement and indentation in one place. Also removed some spurious blank lines.
* Fix bug in bignum addition.Kaz Kylheku2016-11-141-1/+1
| | | | | | | | | * mpi/mpi.c (s_mp_add): It looks like this function had the same kind of bug I fixed years ago in the multiplication routines. ("fix-mult-bug" patch, originally). In the main loop, two digit-sized values are added together to produce a partial sum with carry. Unfortunately, both operands digit-sized, so the result is truncated to the digit type. The cast of one of the operands to mp_word is missing.
* Going back to unmodified 2-Clause BSD License.Kaz Kylheku2016-09-225-5/+10
| | | | | | | | | | | | | | | | | | | | | | | | | * LICENSE: Reverted to Two-Clause BSD license. The copyright of the Linenoise library are included, because it uses exactly the same license. A note is added about MPI being in the public domain. * LICENSE-CYG: Revised text to clarify the situation that Cygnal is only bundled with a particular Windows build of TXR. * METALICENSE: Revised text. All references to modifications to the BSD license are removed. Gives pointers to the MPI and linenoise license files. Notes that linenoise is under the Two-Clause BSD also. Makes a note about Cygnal and points to LICENSE-CYG. * inst.nsi: Remove the text which tells the user that use of the program requires agreement with the license; refer only to redistribution. The "Agree" buttons are renamed "Acknowledge". * mpi/make-logtab, mpi/mpi.c, mpi/mpi.h, mpi/mplogic.c, mpi/mplogic.h: Remove copyright notices and "all rights reserved", since the author had placed this into the public domain, as made explicit in the README file.
* Fix out-of-bounds memory access in bit.Kaz Kylheku2016-06-081-1/+1
| | | | | | | * mpi/mpi.c (mp_bit): If the digit index is beyond the available digits in the number, report MP_NO rather than accessing undefined digit material or beyond the array entirely.
* Do not leave COBJ-ified mp_int uninitialized.Kaz Kylheku2016-06-081-0/+5
| | | | | | | | | | | | | | | Here we ensure that the digits pointer of an uninitialized mp_int is nulled out. The garbage collector could conceivably encounter such an object, in which case mp_clear will then try to free a garbage pointer. This could happen if an exception is thrown out of numeric code due to low memory, interrupting its execution, leaving behind an unfilled object produced by make_ubignum. * arith.c (make_ubignum): Perform minimal initialization of the mp_int using new function. * mpi/mpi.h (mp_init_minimal): New inline function.
* Fix leaks in use of MPI and within MPI.Kaz Kylheku2016-06-081-11/+0
| | | | | | | | | | | | | | | | * arith.c (logand, logior, logxor): Use make_ubignum to create an uninitialized bignum, because mp_and, mp_or, and mp_xor expect argument c to be uninitialized, and clobber it by initializing. (comp_trunc): Use make_ubignum for b argument, because mp_trunk_comp initializes it. (lognot, logtrunc): Use make_ubignum for b, because mp_trunc initializes it. * mpi/mpi.c (mp_and, mp_or, mp_xor, mp_comp, mp_trunc_comp, mp_trunc, mp_shift, mp_bit): Do not initialize the tmp that is passed as argument b to mp_2comp, since that function initializes it.
* Fix broken bignum to int_ptr_t conversion.Kaz Kylheku2016-04-281-3/+2
| | | | | | | | | | | | | This one affects all platforms. The extra sign check and negation cancels out the one done in mp_get_uintptr, causing a positive value for a negative input value. * mpi/mpi.c (mp_get_intptr): Just coerce the uint_ptr_t result to int_ptr_t. That has the right semantics under that the bits are preserved (under two's complement, in every compiler I've ever used). The unsigned value from mp_get_uintptr already looks like the image of a two's complement value.
* Fix broken bignum to uint_ptr_t conversion.Kaz Kylheku2016-04-281-1/+1
| | | | | | | | | This applies only to some platforms, none of which are current targets on which TXR is tested and released. * mpi/mpi.c (mp_get_uinptr): Do not clobber output accumulator in the loop body: the bits must be OR-ed into it.
* Replace all stray C style casts with macros.Kaz Kylheku2016-03-293-36/+53
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * gc.c (gc_report_copies): C style casts found in this function. * linenoise.c (strip_qual, convert, coerce): Copy and paste the macros here. (record_undo, compare_completions, lino_add_completion, history_search, ab_append, sync_data_to_buf, refresh_singleline, screen_rows, refresh_multiline, find_nearest_paren, paren_jump, yank_sel, edit_move_matching_paren, edit, lino_make, lino_copy, lino_hist_add, lino_hist_set_max_len): C style casts replaced. * mpi/mpi-types.h (MP_DIGIT_BIT, MP_DIGIT_MAX, MP_WORD_BIT, MP_WORD_MAX, RADIX): C style casts replaced. * mpi/mpi.c (convert, coerce): Copy and paste the macros here. (mp_init_size, mp_init_copy, mp_copy, mp_set_int, mp_div_d, mp_bit, mp_to_double, mp_to_signed_bin, mp_to_unsigned_bin, mp_to_unsigned_buf, mp_toradix_case, mp_grow, s_mp_set_bit, s_mp_mod_2d, s_mp_mul_2d, s_mp_div_2d, s_mp_mul_d, s_mp_mul, s_mp_sqr, s_mp_div, s_mp_2expt, s_mp_todigit): C style casts replaced. * mpi/mplogic (convert): Macro copy and pasted here. (mpl_num_set, mpl_num_clear): C style casts replaced. * parser.c (provide_completions): Likewise. * signal.c (small_sigfillset): Likewise. * stream.c (stdio_truncate, test_set_indent_mode, set_indent_mode): Likewise.
* Functions for converting between buffers and integers.Kaz Kylheku2016-02-262-0/+27
| | | | | | | | | | | | | | | | | These functions convert between positive integers, and fixed-size memory buffers representing pure binary numbers in big endian byte order. This functionality will be used in some upcoming networking code. * arith.c (num_from_buffer, num_to_buffer): New functions. * arith.h (num_from_buffer, num_to_buffer): Declared. * mpi/mpi.c (mp_to_unsigned_buf): New function. * mpi/mpi.h (mp_to_unsigned_buf): Declared.
* Reduce header pollution caused by mpi.h.Kaz Kylheku2016-01-223-7/+11
| | | | | | | | | | | | | * eval.c: include <assert.h> that was previously coming via "mpi.h". * mpi/mpi.c: Includes of <stdio.h>, <ctype.h> and <assert.h> moved here. * mpi/mpi.h: Remove include of <stdio.h>, <ctype.h> and <assert.h>. Keeping <limits.h> for now; needed for CHAR_BIT. * mpi/mplogic.c: Needs <assert.h>
* New random-state-get-vec function.Kaz Kylheku2016-01-182-11/+29
| | | | | | | | | | | | | | | | | | | | | | | | | | * arith.c (UINT_PTR_MAX_MP): New static variable. (biggnum_from_uintptr): New function. (in_uint_ptr_range): New static function. (c_uint_ptr_num): New function. (arith_init): Initialize UINT_PTR_MAX_MP. * arith.h (bignum_from_uintptr, c_uint_ptr_num): Declared. * eval.c (eval_init): Register random-state-get-vec. * mpi/mpi.c (mp_set_uintptr, mp_get_uintptr): New functions. (mp_set_intptr, mp_get_intptr): Expressed in terms of mp_set_uintptr and mp_get_uintptr. * mpi/mpi.h (mp_set_uintptr, mp_get_uintptr): Declared. * rand.c (make_random_state): Handle vector seed. (random_state_get_vec): New function. * rand.h (random_state_get_vec): Declared. * txr.1: Documented new feature in make-random-state and new random-state-get-vec function.
* random: wrong mask width for power-of-two moduli.Kaz Kylheku2016-01-182-0/+6
| | | | | | | | | | | | | | | | | | | | | | | This mistake causes wasteful behavior for power-of-two moduli in the random function, in both the bignum and fixnum cases. For instance, the modulus 16 is taken to be 17 bits wide. But we really want the width 16: the number of bits needed for values in the range [0, 16). The result isn't wrong, but the loop generates 17-bit random numbers, and then throws away those which equal or exceed the modulus, which is wasteful. * mpi/mpi.c (mp_is_pow_two): New function. * mpi/mpi.h (mp_is_pow_two): Declared. * rand.c (random): In bignum case, after counting bits in the modulus, subtract 1 if the modulus is a power of two. In the fixnum case, subtract 1 from the modulus and then count the bits in the reduced value. * tests/013/maze.expected: regenerate due to different prng behavior.
* Remove include guards from MPI headers.Kaz Kylheku2015-08-152-12/+0
| | | | | * mpi/mpi-config.h, mpi/mpi.h: These headers do not require include guards. They included only once.
* eliminate-locale-dependencies patchKaz Kylheku2015-04-221-9/+14
| | | | | | | Eliminating dependencies on locale-dependent C functions. * mpi/mpi.c (s_mp_tovalue, s_mp_todigit): Avoid tolower, toupper, islower and isupper.
* add-bitops patchKaz Kylheku2015-04-222-0/+441
| | | | | | | | | | | Adding bit operations to MPI. * mpi/mpi.c (MAX, MIN): New macros. (mp_2comp, mp_and, mp_or, mp_xor, mp_comp, mp_trunc, mp_shift, mp_bit): New functions. * mpi/mpi.h (mp_2comp, mp_and, mp_or, mp_xor, mp_comp, mp_trunc, mp_shift, mp_bit): Declared.
* fix-ctype-warnings patchKaz Kylheku2015-04-221-3/+3
| | | | | * mpi/mpi.c (s_mp_tovalue): Argument changes from char to int, fixing some compiler warnings.
* mpi-to-double patchKaz Kylheku2015-04-222-0/+29
| | | | | | * mpi/mpi.c (mp_to_double): New function. * mpi/mpi.h (mp_to_double): Declared.
* faster-square-root patchKaz Kylheku2015-04-221-74/+70
| | | | | * mpi/mpi.c (s_highest_bit_mp, s_mp_set_bit): New functions. (mp_sqrt): Rewrite with more efficient algorithm.
* shrink-mpi-int patchKaz Kylheku2015-04-221-0/+5
| | | | | | * mpi/mpi.h (mp_int): Depending on the relative size of int and pointers, turn the sign and alloc fields into bitfields, so that the structure is three words wide and therefore fits into a TXR obj_t heap object.
* bit-search-optimizations patchKaz Kylheku2015-04-221-30/+232
| | | | | * mpi/mpi.c (s_highest_bit): New static function. (s_mp_norm, s_mp_ispow2): Use s_highest_bit instead of looping over bits.
* fix-bad-shifts patchKaz Kylheku2015-04-221-5/+5
| | | | | | * mpi/mpi.c (mp_div_d, s_mp_mod_2d, s_mp_mul_2d, s_mp_div_2d, s_mp_2expt): Fixing incorrect digit-wide left shifts whre the operand is not widened to the mp_digit type.
* mpi-set-double-intptr patchKaz Kylheku2015-04-222-0/+33
| | | | | | * mpi/mpi.c (mp_set_double_intptr): New function. * mpi/mpi.h (mp_set_double_intptr): Declared.
* mpi-set-mpi-word patchKaz Kylheku2015-04-222-0/+10
| | | | | | * mpi/mpi.c (mp_set_word): New function. * mpi/mpi.h (mp_set_word): Declared.
* fix-mult-bug patchKaz Kylheku2015-04-221-6/+6
| | | | | | | | Fixing bugs in MPI whereby two digits are multiplied together, but neither operand is cast to the double digit type, so that the result is truncated. * mpi/mpi.c (s_mp_mul_d, s_mp_mul, s_mp_sqr): Add casts to achieve multiplication of the proper width.
* add-mpi-toradix-with-case patchKaz Kylheku2015-04-222-4/+10
| | | | | | | | * mpi/mpi.c (mp_toradix_case): New function based on mp_toradix. Takes an argument whether to use lower case digits. (mp_toradix): Reduced to wrapper for mp_toradix_case. * mpi/mpi.h (mp_toradix_case): Declared.
* add-mp-hash patchKaz Kylheku2015-04-222-0/+30
| | | | | | * mpi/mpi.c (mp_hash): New function. * mpi/mpi.c (mp_hash): Declared.
* export-mp-eq patchKaz Kylheku2015-04-222-8/+4
| | | | | | * mpi/mpi.c (MP_LT, MP_EQ, MP_GT): Preprocessor symbols removed. * mpi/mpi.h (MP_LT, MP_EQ, MP_GT): Preprocessor symbols added.
* add-mp-set-intptr patchKaz Kylheku2015-04-222-0/+55
| | | | | | * mpi/mpi.c (mp_set_intptr, mp_get_intptr): New functions. * mpi/mpi.h (mp_set_intptr, mp_get_intptr): Declared.
* use-txr-allocator patchKaz Kylheku2015-04-221-6/+9
| | | | | | | | | * mpi/mpi.c (mem_t): TXR's mem_t typedef repeated here. (chk_calloc): New external declaration, to avoid including our entire lib.h header. (s_mp_alloc): Macro retargetted to use chk_calloc. (mp_init_size, mp_init_copy, mp_copy, s_mp_grow, s_mp_copy): Return value casts added.
* fix-warnings patchKaz Kylheku2015-04-222-7/+7
| | | | | | | * mpi/mpi.c (mp_to_unsigned_bin, s_mp_mod_2d): Fix signed/unsigned warning. (mp_toradix): Fix shadowing local variable name warning. * mpi/mplogic.c (mpl_num_set, mpl_num_clear): Fix signed/unsigned warning.
* config-types patchKaz Kylheku2015-04-223-13/+54
| | | | | | | | * mpi/mpi-types.h: Rewritten by hand to use make use of information produced by TXR's configure script into config/config.h. * mpi/mpi.c, mpi/mplogic.c: Include the config.h header, now needed by mpi-types.h.
* Bringing MPI library out of tarball into GIT.Kaz Kylheku2015-04-229-0/+5597
Importing 1.8.6 upstream baseline, minus unwanted stuff.
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-10 11:59:36 +0000