BigInteger impl

static inline int16_t xorsign_biginthelper( int16_t  lsign, int16_t  rsign )

Returns the sign of combined bigint_t.sign_and_used_digits fields.  The returned value is either < 0 if exactly one of the parameter is negative.  The returned value is >= 0 if both parameter are either negative (<0) or positive (>=0).

Compiler Implementation Dependent

This function uses bit operations on signed integers which is implementation-defined.

static int add_biginthelper( bigint_t  *restrict  * result, const  bigint_t  * lbig, const  bigint_t  * rbig )

Adds two integers.  The result has the same sign as lbig.

static int sub_biginthelper( bigint_t  *restrict  * result, const  bigint_t  * lbig, const  bigint_t  * rbig )

Subtracts two integers.  The sign of lbig is used to determine the sign of the result.  If the magnitude of lbig is bigger than rbig (<cmpmagnitude_bigint>) the result has the same sign as lbig else it is reverted.

static void mult_biginthelper( bigint_t  * big, uint16_t  lnrdigits, const  uint32_t  * ldigits, uint16_t  rnrdigits, const  uint32_t  * rdigits, const  uint16_t  exponent )

Multiplies two numbers with the simple schoolbook algorithm.

(unchecked) Preconditions

1. big must be allocated with size == (lnrdigits + rnrdigits) 2. lnrdigits > 0 && rnrdigits > 0 3. lnrdigits <= rnrdigits 4. ldigits[lnrdigits-1] != 0 && rdigits[rnrdigits-1] != 0

static int multsplit_biginthelper( bigint_t  *restrict  * result, uint16_t  lnrdigits, const  uint32_t  * ldigits, uint16_t  rnrdigits, const  uint32_t  * rdigits )

Multiplies two big integer numbers and returns the positive result.  The multiplication is done with splitting of numbers to save one multiplication.

(unchecked) Preconditions

1. result must be allocated with size == (lnrdigits + rnrdigits) 2.  After skipping of trailing zeros: (lnrdigits > 0 && rnrdigits > 0) 3.  (ldigits[lnrdigits-1] != 0 && rdigits[rnrdigits-1] != 0)

static void div3by2digits_biginthelper( bigint_divstate_t  * state )

Divides 3 32 bit integer digits by 2 32 bit integer digits.  The returned number in nextdigit is ((((uint128_t)dividend << 32) + nextdigit) / divisor).  The returned value is used to estimate the next digit of the quotient.  It is either correct or one too large.

After return the dividend contains the remainder of the division also.

(unchecked) Precondition

1. dividend < divisor ==> nextdigit <= UINT32_MAX 2. dividend > UINT32_MAX && divisor > UINT32_MAX ==> “nextdigit either correct or one too large”

static void submul_biginthelper( bigint_divstate_t  * state )

Computes ldigits[*]-=nextdigit*rdigits[*] and corrects nextdigits with -1 if necessary.  The factor nextdigit is corrected in case it is too high (see first precondition).

Special case (nextdigit==0)

Use nextdigit == UINT32_MAX and assume that correction is not needed.  This is called after nextdigit is corrected from 1 to 0 ==> dividend == divisor.  The next step is to compute ((dividend * (UINT32_MAX+1)) + nextdigit) / divisor which would result in UINT32_MAX+1 and can not be represented with nextdigit.  But with the previous correction from 1 to 0 we already know that factor (UINT32_MAX+1) is too big and UINT32_MAX is the correct choice.  But calculating (with dividend==divisor)

dividend = ((dividend * (UINT32_MAX+1)) + nextdigit) - UINT32_MAX * divisor

results in

dividend = dividend + nextdigit

which could overflow dividend.  In the case of overflow the carry bit is ignored.  In the implementation the computation subtracts a correction value from dividend but a possible underflow is ignored cause if the missing carry bit.  But we already know UINT32_MAX is the correct next digit.

Special case (nextdigit==1)

No multiplication needed and returned corrected nextdigit could become 0.

(unchecked) Preconditions

1.  (nextdigit+1)*rdigits[*] > ldigits[*] 2.  (nextdigit*rdigits[*]) <= ldigits[*] || (nextdigit-1)*rdigits[*] <= ldigits[*]

static void divmod_biginthelper(     bigint_t  *restrict  * divresult,     bigint_t  *restrict  * modresult,     uint16_t  divnrdigits,     // number of digits which must be computed const  uint16_t  modnrdigits,     // number of digits of the remainder const  int16_t  divsign,     // sign ([-1,+1]) of divresult const  int16_t  lsign,     // sign ([-1,+1]) of ldigits (which is the sign of modresult) const  uint16_t  lnrdigits,     // the number of digits in array ldigits  uint32_t  * ldigits,     // the array of digits for the left operand const  uint16_t  rnrdigits,     // the number of digits in array rdigits const  uint32_t  * rdigits ) // the array of digits for the right operand

Computes ldigits[0..lnrdigits-1] = divresult * rdigits[0..rnrdigits-1] + modresult.  After return divresult contains the result of

ldigits[0..lnrdigits-1]/rdigits[0..rnrdigits-1]

and modresult contains the result of

ldigits[0..lnrdigits-1] - divresult * rdigits[0..rnrdigits-1].

(unchecked) Preconditions

1. rnrdigits >= 2 2. lnrdigits >= rnrdigits 3. divnrdigits > 0 && modnrdigits >= 2 && modnrdigits <= lnrdigits 4.  (divnrdigits != 1) || (modnrdigits == lnrdigits) 5. divresult == 0 || divresult->allocated_digits >= divnrdigits 6. divresult == 0 || is_valid(divresult->exponent) 7. modresult == 0 || modresult->allocated_digits >= modnrdigits 8. modresult == 0 || is_valid(modresult->exponent)

static void divmodui32_biginthelper( bigint_t  *restrict  * divresult, bigint_t  *restrict  * modresult, uint16_t  divnrdigits, const  int16_t  divsign, const  int16_t  lsign, uint16_t  lnrdigits, const uint32_t *  const  ldigits, const  uint32_t  divisor )

Divides lbig by signed divisor.  The result numbers must be preallocated with correct size.  See »Preconditions« item 4. and 5. for the expected size.  The sign of divresult is set to divsign and the sign of modresult is set to the same sign as lbig.

(unchecked) Preconditions

1. lnrdigits > 0 2. divisor > 0 3. divnrdigits > 0 4. divresult == 0 || divresult->allocated_digits >= divnrdigits 5. modresult == 0 || modresult->allocated_digits >= max(1, (lnrdigits - (divnrdigits-1))) 6. divresult == 0 || is_valid(divresult->exponent) 7. modresult == 0 || is_valid(modresult->exponent)