summaryrefslogtreecommitdiffstats
Commit message (Collapse)AuthorAgeFilesLines
* pbn_div: fix the handling of qhatHEADmasterH. Peter Anvin2012-03-211-39/+46
| | | | | qhat can genuinely end up as a 33-bit number under certain circumstances, so we need to properly take it into account.
* pbn_mul: Fix the handling of carryH. Peter Anvin2012-03-211-14/+16
| | | | | | | | | Fix the handling of carry in pbn_mul; adding in the already accumulated values may cause a carry, too. However, we will never overflow two limbs, because: if a = 2^(n-1) - 1 then a * a + a + a = 2^n - 1
* pbn_init.c: correct realloc/memset use in pbn_cow()H. Peter Anvin2012-03-211-3/+9
| | | | | realloc(): check the return value memset(): only do this if we actually grew the allocation
* Add *.a to .gitignoreH. Peter Anvin2012-03-201-0/+1
|
* Add pbn_mulus_add()H. Peter Anvin2012-03-203-1/+56
| | | | | | | | | | Add pbn_mulus_add(); equivalent to pbn_muls() except: a) it takes an unsigned multiplier, and b) it takes a second single-limb unsigned addend. It thus computes <long> * <short1> + <short2>; this is highly useful in base conversion.
* pbn_muls: Fix pbn_muls() implementationH. Peter Anvin2012-03-201-7/+4
| | | | Fix several bugs in pbn_muls()
* pbn_ctz: Add function to count trailing zeroesH. Peter Anvin2012-03-202-1/+86
| | | | | | Add pbn_ctz() to count the number of trailing zeroes in a nonzero number. This is a useful operation in decimal-to-binary floating point conversion, and probably all other kinds of things.
* Add pbn_muls() -- long * short multiplicationH. Peter Anvin2012-03-203-2/+62
| | | | | Add pbn_muls() for multiplication of a PBN with a short number (single limb).
* Switch terminology from "atom" to the more standard "limb"H. Peter Anvin2012-03-1313-113/+113
| | | | | The "limb" terminology ("like a digit but larger") seems to have become standard enough that we might as well follow suit.
* Fix the division case where the denominator is a single limbH. Peter Anvin2012-03-133-89/+101
| | | | | | The code for Knuth-D assumes a denominator of >= 2 limbs; test for this and fall back to a simple divide loop for a single-limb denominator.
* Do division via Knuth's Algorithm D (limb long division)H. Peter Anvin2012-03-126-80/+191
| | | | | Instead of bitwise, do division via Knuth's Algorithm D, which is basically probabilistic long division.
* pbn_cmp: optimize comparisonH. Peter Anvin2012-03-111-8/+4
| | | | Make the loop a bit cleaner by simply comparing for equality first.
* Makefile: build a library (.a file)H. Peter Anvin2012-03-111-4/+13
|
* Encapsulate the gcc hack better.H. Peter Anvin2007-10-131-9/+3
|
* pbn_divs(): special hint of gcc on i386: generate divlH. Peter Anvin2007-10-131-4/+20
| | | | | | gcc on i386 won't generate divl for 64/32 -> 32 division. Since this is a particularly important platform for us (NASM) put in a specific hint for it.
* Enable optimization (-O2)H. Peter Anvin2007-10-131-1/+1
|
* Fix calculation of bits in pbn_xor()H. Peter Anvin2007-10-131-2/+1
|
* Add a routine for "small division" (bignum/smallnum)H. Peter Anvin2007-10-134-1/+97
| | | | | Small division can be done much more efficiently than big division, so make small division available to the user.
* pbn_div(): r is produced by pbn_sub() or pbn_cow() so r->bits is OKH. Peter Anvin2007-10-131-2/+2
| | | | | | There is no need to call pbn_adjust_bits() since r was produced by pbn_sub() or pbn_cow() and therefore already has r->bits correctly set.
* Make pbn_div() slightly faster by avoiding pbn_set_bit()H. Peter Anvin2007-10-131-1/+9
| | | | Don't use pbn_set_bit() inside pbn_div().
* Fix the zero cases for logical operations; handle signH. Peter Anvin2007-10-123-5/+19
| | | | | - Fix the various zero cases for the logical operations - Do something semi-sane with the sign for the logical ops
* Add working (but slow) division algorithm; fix shiftsH. Peter Anvin2007-10-1214-52/+176
| | | | | | - Add working (but slow) pbn_div(); - Make pbn_adjust_bits() a part of the official API - Fix bug in the simple-case shift code
* Add pbn_abs()H. Peter Anvin2007-10-123-1/+30
| | | | Add pbn_abs() to return the absolute value of a pbn.
* Add absolute value compare; pbn_addsub() should use itH. Peter Anvin2007-10-123-14/+35
| | | | | Add pbn_abscmp() to compare absolute values; this is what pbn_addsub() actually wanted to use.
* pbn_div: update comment (statement of intent, no implementation yet)H. Peter Anvin2007-10-121-1/+6
|
* Add bitwise operationsH. Peter Anvin2007-10-1211-31/+246
| | | | Add bitwise operations: and, or, xor, set_bit, clr_bit, bit
* Fix right shift, and add test for shiftsH. Peter Anvin2007-10-122-13/+42
| | | | Right shift was broken; correct. Add simple test for shifts.
* Add shifts to MakefileH. Peter Anvin2007-10-121-1/+1
| | | | Add pbn_shift.o to Makefile
* Fix pbn_shr()/pbn_shl()H. Peter Anvin2007-10-121-2/+4
| | | | Silly typos in the shift functions
* Be more careful about the zero caseH. Peter Anvin2007-10-123-1/+20
| | | | Handle the zero case better
* Add pbn_shl() and pbn_shr()H. Peter Anvin2007-10-121-0/+98
| | | | Shift operations
* Add .gitignore fileH. Peter Anvin2007-10-121-0/+3
|
* Change name from mpn to "pbn" (Peter's BigNum library)H. Peter Anvin2007-10-1211-193/+233
|
* Simple multiprecision libraryH. Peter Anvin2007-10-129-0/+591