summaryrefslogtreecommitdiffstats
path: root/otherlibs/num/bignum/c
diff options
context:
space:
mode:
Diffstat (limited to 'otherlibs/num/bignum/c')
-rw-r--r--otherlibs/num/bignum/c/KerN.c932
-rw-r--r--otherlibs/num/bignum/c/bn/bnCmp.c77
-rw-r--r--otherlibs/num/bignum/c/bn/bnDivide.c156
-rw-r--r--otherlibs/num/bignum/c/bn/bnInit.c74
-rw-r--r--otherlibs/num/bignum/c/bn/bnMult.c84
-rw-r--r--otherlibs/num/bignum/c/bz.c833
-rw-r--r--otherlibs/num/bignum/c/bzf.c50
-rw-r--r--otherlibs/num/bignum/c/bztest.c167
-rw-r--r--otherlibs/num/bignum/c/testKerN.c1085
9 files changed, 3458 insertions, 0 deletions
diff --git a/otherlibs/num/bignum/c/KerN.c b/otherlibs/num/bignum/c/KerN.c
new file mode 100644
index 000000000..7b9ef1ce1
--- /dev/null
+++ b/otherlibs/num/bignum/c/KerN.c
@@ -0,0 +1,932 @@
+/* Copyright Digital Equipment Corporation & INRIA 1988, 1989 */
+/* Last modified_on Thu Feb 20 18:18:12 GMT+1:00 1992 by shand */
+/* modified_on Tue Jan 15 19:32:53 GMT+1:00 1991 by herve */
+
+
+/* KerN.c: the kernel written in C */
+
+/*
+ * Description of types and constants.
+ *
+ * Several conventions are used in the commentary:
+ * A "BigNum" is the name for an infinite-precision number.
+ * Capital letters (e.g., "N") are used to refer to the value of BigNums.
+ * The word "digit" refers to a single BigNum digit.
+ * The notation "Size(N)" refers to the number of digits in N,
+ * which is typically passed to the subroutine as "nl".
+ * The notation "Length(N)" refers to the number of digits in N,
+ * not including any leading zeros.
+ * The word "Base" is used for the number 2 ** BN_DIGIT_SIZE, where
+ * BN_DIGIT_SIZE is the number of bits in a single BigNum digit.
+ * The expression "BBase(N)" is used for Base ** NumDigits(N).
+ * The term "leading zeros" refers to any zeros before the most
+ * significant digit of a number.
+ *
+ *
+ * In the code, we have:
+ *
+ * "nn" is a pointer to a big number,
+ * "nl" is the number of digits from nn,
+ * "d" is a digit.
+ *
+ */
+
+
+/* */
+
+#define BNNMACROS_OFF
+#include "BigNum.h"
+#define NOMEM
+
+ /*** copyright ***/
+
+static char copyright[]="@(#)KerN.c: copyright Digital Equipment Corporation & INRIA 1988, 1989\n";
+
+
+ /******* non arithmetic access to digits ********/
+
+
+#ifndef _NO_PROTO
+void BnnSetToZero (BigNum nn, BigNumLength nl)
+#else
+void BnnSetToZero (nn, nl)
+BigNum nn; BigNumLength nl;
+#endif
+
+/*
+ * Sets all the specified digits of the BigNum to 0
+ */
+
+{
+ BigNum nnlim;
+ if (nl <= 0)
+ return;
+ nnlim = nn+nl-1;
+ do *nn = 0; while(nn++ < nnlim);
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+void BnnAssign (BigNum mm, BigNum nn, BigNumLength nl)
+#else /* _NO_PROTO */
+void BnnAssign ( mm, nn, nl)
+BigNum mm; BigNum nn; BigNumLength nl;
+#endif /* _NO_PROTO */
+
+/*
+ * Copies N => M
+ */
+
+{
+ BigNum nnlim;
+ if (nl <= 0)
+ return;
+ nnlim = nn+nl;
+#ifdef MSDOS
+ if (realaddr(mm) < realaddr(nn) || realaddr(mm) > realaddr(nnlim))
+#else
+ if ((mm < nn) || ( mm > nnlim))
+#endif
+ do *mm++ = *nn++; while(nn < nnlim);
+ else
+#ifdef MSDOS
+ if (realaddr(mm) > realaddr(nn))
+#else
+ if (mm > nn)
+#endif
+ {
+ mm += nl;
+ do *--mm = *--nnlim; while(nn < nnlim);
+ }
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+void BnnSetDigit (BigNum nn, BigNumDigit d)
+#else /* _NO_PROTO */
+void BnnSetDigit ( nn, d)
+BigNum nn; BigNumDigit d;
+#endif /* _NO_PROTO */
+
+/*
+ * Sets a single digit of N to the passed value
+ */
+
+{
+ *nn = d;
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+BigNumDigit BnnGetDigit (BigNum nn)
+#else /* _NO_PROTO */
+BigNumDigit BnnGetDigit ( nn)
+BigNum nn;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns the single digit pointed by N
+ */
+
+{
+ return (*nn);
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+BigNumLength BnnNumDigits (BigNum nn, BigNumLength nl)
+#else /* _NO_PROTO */
+BigNumLength BnnNumDigits ( nn, nl)
+BigNum nn; BigNumLength nl;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns the number of digits of N, not counting leading zeros
+ */
+
+{
+ nn += nl;
+
+ while (nl != 0 && *--nn == 0)
+ nl--;
+
+ return (nl == 0 ? 1 : nl);
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+BigNumDigit BnnNumLeadingZeroBitsInDigit (BigNumDigit d)
+#else /* _NO_PROTO */
+BigNumDigit BnnNumLeadingZeroBitsInDigit ( d)
+BigNumDigit d;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns the number of leading zero bits in a digit
+ */
+
+{
+ register int p = 0;
+ if (BN_DIGIT_SIZE == 16 || BN_DIGIT_SIZE == 32 || BN_DIGIT_SIZE == 64)
+ {
+ register BigNumDigit mask = (~(BigNumDigit)0) << (BN_DIGIT_SIZE/2);
+ register BigNumLength maskl = BN_DIGIT_SIZE/2;
+
+ if (d == 0)
+ return (BN_DIGIT_SIZE);
+ while (maskl)
+ {
+ if ((d & mask) == 0)
+ {
+ p += maskl;
+ d <<= maskl;
+ }
+ maskl >>= 1;
+ mask <<= maskl;
+ }
+ }
+ else
+ {
+ register BigNumDigit mask = ((BigNumDigit)1) << (BN_DIGIT_SIZE-1);
+
+ while ((d & mask) == 0)
+ {
+ p++;
+ mask >>= 1;
+ }
+ }
+
+ return (p);
+}
+
+ /***************************************/
+/* */
+
+ /************** Predicates on one digit ***************/
+
+
+#ifndef _NO_PROTO
+Boolean BnnDoesDigitFitInWord (BigNumDigit d)
+#else /* _NO_PROTO */
+Boolean BnnDoesDigitFitInWord ( d)
+BigNumDigit d;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns TRUE iff the digit can be represented in just BN_WORD_SIZE bits
+ */
+{
+ /* The C compiler must evaluate the predicate at compile time */
+ if (BN_DIGIT_SIZE > BN_WORD_SIZE)
+ return (d >= ((BigNumDigit)1) << BN_WORD_SIZE ? FALSE : TRUE);
+ else
+ return (TRUE);
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+Boolean BnnIsDigitZero (BigNumDigit d)
+#else /* _NO_PROTO */
+Boolean BnnIsDigitZero ( d)
+BigNumDigit d;
+#endif /* _NO_PROTO */
+
+/* Returns TRUE iff digit = 0 */
+
+{
+ return (d == 0);
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+Boolean BnnIsDigitNormalized (BigNumDigit d)
+#else /* _NO_PROTO */
+Boolean BnnIsDigitNormalized ( d)
+BigNumDigit d;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns TRUE iff Base/2 <= digit < Base
+ * i.e., if digit's leading bit is 1
+ */
+
+{
+ return (d & (((BigNumDigit)1) << (BN_DIGIT_SIZE - 1)) ? TRUE : FALSE);
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+Boolean BnnIsDigitOdd (BigNumDigit d)
+#else /* _NO_PROTO */
+Boolean BnnIsDigitOdd ( d)
+BigNumDigit d;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns TRUE iff digit is odd
+ */
+
+{
+ return (d & 1 ? TRUE : FALSE);
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+BigNumCmp BnnCompareDigits (BigNumDigit d1, BigNumDigit d2)
+#else /* _NO_PROTO */
+BigNumCmp BnnCompareDigits ( d1, d2)
+BigNumDigit d1; BigNumDigit d2;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns BN_GREATER if digit1 > digit2
+ * BN_EQUAL if digit1 = digit2
+ * BN_LESS if digit1 < digit2
+ */
+
+{
+ return (d1 > d2 ? BN_GT : (d1 == d2 ? BN_EQ : BN_LT));
+}
+
+ /***************** Logical operations ********************/
+
+
+#ifndef _NO_PROTO
+void BnnComplement (BigNum nn, BigNumLength nl)
+#else /* _NO_PROTO */
+void BnnComplement ( nn, nl)
+BigNum nn; BigNumLength nl;
+#endif /* _NO_PROTO */
+
+/*
+ * Performs the computation BBase(N) - N - 1 => N
+ */
+
+{
+ BigNum nnlim;
+
+ if (nl <= 0)
+ return;
+ nnlim = nn+nl;
+ do
+ {
+ nn++;
+ nn[-1] = ~nn[-1];
+ }
+ while (nn < nnlim);
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+void BnnAndDigits (BigNum n, BigNumDigit d)
+#else /* _NO_PROTO */
+void BnnAndDigits ( n, d)
+BigNum n; BigNumDigit d;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns the logical computation n[0] AND d in n[0]
+ */
+
+{
+ *n &= d;
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+void BnnOrDigits (BigNum n, BigNumDigit d)
+#else /* _NO_PROTO */
+void BnnOrDigits ( n, d)
+BigNum n; BigNumDigit d;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns the logical computation n[0] OR d2 in n[0].
+ */
+
+{
+ *n |= d;
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+void BnnXorDigits (BigNum n, BigNumDigit d)
+#else /* _NO_PROTO */
+void BnnXorDigits ( n, d)
+BigNum n; BigNumDigit d;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns the logical computation n[0] XOR d in n[0].
+ */
+
+{
+ *n ^= d;
+}
+
+ /***************************************/
+/* */
+
+ /****************** Shift operations *******************/
+
+
+#ifndef _NO_PROTO
+BigNumDigit BnnShiftLeft (BigNum mm, BigNumLength ml, int nbits)
+#else /* _NO_PROTO */
+BigNumDigit BnnShiftLeft ( mm, ml, nbits)
+BigNum mm; BigNumLength ml; int nbits;
+#endif /* _NO_PROTO */
+
+/*
+ * Shifts M left by "nbits", filling with 0s.
+ * Returns the leftmost "nbits" of M in a digit.
+ * Assumes 0 <= nbits < BN_DIGIT_SIZE.
+ */
+
+{
+ register BigNumDigit res = 0, save;
+ int rnbits;
+
+
+ if (nbits != 0)
+ {
+ rnbits = BN_DIGIT_SIZE - nbits;
+
+ while (ml-- > 0)
+ {
+ save = *mm;
+ *mm++ = (save << nbits) | res;
+ res = save >> rnbits;
+ }
+ }
+
+ return (res);
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+BigNumDigit BnnShiftRight (BigNum mm, BigNumLength ml, int nbits)
+#else /* _NO_PROTO */
+BigNumDigit BnnShiftRight ( mm, ml, nbits)
+BigNum mm; BigNumLength ml; int nbits;
+#endif /* _NO_PROTO */
+
+/*
+ * Shifts M right by "nbits", filling with 0s.
+ * Returns the rightmost "nbits" of M in a digit.
+ * Assumes 0 <= nbits < BN_DIGIT_SIZE.
+ */
+
+{
+ register BigNumDigit res = 0, save;
+ int lnbits;
+
+
+ if (nbits != 0)
+ {
+ mm += ml;
+ lnbits = BN_DIGIT_SIZE - nbits;
+
+ while (ml-- > 0)
+ {
+ save = *(--mm);
+ *mm = (save >> nbits) | res;
+ res = save << lnbits;
+ }
+ }
+
+ return (res);
+}
+
+ /***************************************/
+/* */
+
+
+ /******************* Additions **************************/
+
+
+#ifndef _NO_PROTO
+BigNumCarry BnnAddCarry (BigNum nn, BigNumLength nl, BigNumCarry carryin)
+#else /* _NO_PROTO */
+BigNumCarry BnnAddCarry ( nn, nl, carryin)
+BigNum nn; BigNumLength nl; BigNumCarry carryin;
+#endif /* _NO_PROTO */
+
+/*
+ * Performs the sum N + CarryIn => N.
+ * Returns the CarryOut.
+ */
+
+{
+ if (carryin == 0)
+ return (0);
+
+ if (nl == 0)
+ return (1);
+
+ while (nl > 0 && !(++(*nn++)))
+ nl--;
+
+ return (nl > 0 ? 0 : 1);
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+BigNumCarry BnnAdd (BigNum mm, BigNumLength ml, BigNum nn, BigNumLength nl, BigNumCarry carryin)
+#else /* _NO_PROTO */
+BigNumCarry BnnAdd ( mm, ml, nn, nl, carryin)
+BigNum mm; BigNumLength ml; BigNum nn; BigNumLength nl; BigNumCarry carryin;
+#endif /* _NO_PROTO */
+
+/*
+ * Performs the sum M + N + CarryIn => M.
+ * Returns the CarryOut.
+ * Assumes Size(M) >= Size(N).
+ */
+
+{
+ register BigNumProduct c = carryin;
+
+
+ ml -= nl;
+ /* test computed at compile time */
+ if (sizeof (BigNumProduct) > sizeof (BigNumDigit))
+ {
+ while (nl > 0)
+ {
+ c += ((BigNumProduct)*mm) + *(nn++);
+ *(mm++) = c;
+ c >>= BN_DIGIT_SIZE;
+ nl--;
+ }
+ }
+ else
+ {
+ register BigNumProduct save;
+
+ while (nl > 0)
+ {
+ save = *mm;
+ c += save;
+ if (c < save)
+ {
+ *(mm++) = *(nn++);
+ c = 1;
+ }
+ else
+ {
+ save = *(nn++);
+ c += save;
+ *(mm++) = c;
+ c = (c < save) ? 1 : 0;
+ }
+ nl--;
+ }
+ }
+
+ return (BnnAddCarry (mm, ml, (BigNumCarry) c));
+}
+
+ /***************************************/
+/* */
+
+ /****************** Subtraction *************************/
+
+
+
+#ifndef _NO_PROTO
+BigNumCarry BnnSubtractBorrow (BigNum nn, BigNumLength nl, BigNumCarry carryin)
+#else /* _NO_PROTO */
+BigNumCarry BnnSubtractBorrow ( nn, nl, carryin)
+BigNum nn; BigNumLength nl; BigNumCarry carryin;
+#endif /* _NO_PROTO */
+
+/*
+ * Performs the difference N + CarryIn - 1 => N.
+ * Returns the CarryOut.
+ */
+
+{
+ if (carryin == 1)
+ return (1);
+ if (nl == 0)
+ return (0);
+
+ while (nl > 0 && !((*nn++)--))
+ nl--;
+
+ return (nl > 0 ? 1 : 0);
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+BigNumCarry BnnSubtract (BigNum mm, BigNumLength ml, BigNum nn, BigNumLength nl, BigNumCarry carryin)
+#else /* _NO_PROTO */
+BigNumCarry BnnSubtract ( mm, ml, nn, nl, carryin)
+BigNum mm; BigNumLength ml; BigNum nn; BigNumLength nl; BigNumCarry carryin;
+#endif /* _NO_PROTO */
+
+/*
+ * Performs the difference M - N + CarryIn - 1 => M.
+ * Returns the CarryOut.
+ * Assumes Size(M) >= Size(N).
+ */
+
+{
+ register BigNumProduct c = carryin;
+ register BigNumDigit invn;
+
+
+ ml -= nl;
+ /* test computed at compile time */
+ if (sizeof (BigNumProduct) > sizeof (BigNumDigit))
+ {
+ while (nl > 0)
+ {
+ invn = *(nn++) ^ -1;
+ c += ((BigNumProduct)*mm) + invn;
+ *(mm++) = c;
+ c >>= BN_DIGIT_SIZE;
+ nl--;
+ }
+ }
+ else
+ {
+ register BigNumProduct save;
+
+ while (nl > 0)
+ {
+ save = *mm;
+ invn = *(nn++) ^ -1;
+ c += save;
+
+ if (c < save)
+ {
+ *(mm++) = invn;
+ c = 1;
+ }
+ else
+ {
+ c += invn;
+ *(mm++) = c;
+ c = (c < invn) ? 1 : 0;
+ }
+ nl--;
+ }
+ }
+
+ return (BnnSubtractBorrow (mm, ml, (BigNumCarry) c)); }
+
+
+ /***************************************/
+/* */
+
+ /***************** Multiplication ************************/
+
+#ifndef _NO_PROTO
+BigNumCarry BnnMultiplyDigit (BigNum pp, BigNumLength pl, BigNum mm, BigNumLength ml, BigNumDigit d)
+#else /* _NO_PROTO */
+BigNumCarry BnnMultiplyDigit ( pp, pl, mm, ml, d)
+BigNum pp; BigNumLength pl; BigNum mm; BigNumLength ml; BigNumDigit d;
+#endif /* _NO_PROTO */
+
+/*
+ * Performs the product:
+ * Q = P + M * d
+ * BB = BBase(P)
+ * Q mod BB => P
+ * Q div BB => CarryOut
+ * Returns the CarryOut.
+ * Assumes Size(P) >= Size(M) + 1.
+ */
+
+{
+ register BigNumProduct c = 0;
+
+
+ if (d == 0)
+ return (0);
+
+ if (d == 1)
+ return (BnnAdd (pp, pl, mm, ml, (BigNumCarry) 0));
+
+ pl -= ml;
+ /* test computed at compile time */
+ if (sizeof (BigNumProduct) > sizeof (BigNumDigit))
+ {
+ while (ml != 0)
+ {
+ ml--;
+ c += *pp + (((BigNumProduct)d) * (*(mm++)));
+ *(pp++) = c;
+ c >>= BN_DIGIT_SIZE;
+ }
+
+ while (pl != 0)
+ {
+ pl--;
+ c += *pp;
+ *(pp++) = c;
+ c >>= BN_DIGIT_SIZE;
+ }
+
+ return (c);
+ }
+ else
+ {
+/* help for stupid compilers--may actually be counter
+ productive on pipelined machines with decent register allocation!! */
+#define m_digit X0
+#define X3 Lm
+#define X1 Hm
+ register BigNumDigit Lm, Hm, Ld, Hd, X0, X2 /*, X1, X3 */;
+
+ Ld = d & ((((BigNumDigit)1) << (BN_DIGIT_SIZE / 2)) -1);
+ Hd = d >> (BN_DIGIT_SIZE / 2);
+ while (ml != 0)
+ {
+ ml--;
+ m_digit = *mm++;
+ Lm = m_digit & ((((BigNumDigit)1) << (BN_DIGIT_SIZE / 2)) -1);
+ Hm = m_digit >> (BN_DIGIT_SIZE / 2);
+ X0 = Ld * Lm;
+ X2 = Hd * Lm;
+ X3 = Hd * Hm;
+ X1 = Ld * Hm;
+
+ if ((c += X0) < X0) X3++;
+ if ((X1 += X2) < X2) X3 += (((BigNumDigit)1)<<(BN_DIGIT_SIZE / 2));
+ X3 += (X1 >> (BN_DIGIT_SIZE / 2));
+ X1 <<= (BN_DIGIT_SIZE / 2);
+ if ((c += X1) < X1) X3++;
+ if ((*pp += c) < c) X3++;
+ pp++;
+
+ c = X3;
+#undef m_digit
+#undef X1
+#undef X3
+ }
+
+ X0 = *pp;
+ c += X0;
+ *(pp++) = c;
+
+ if (c >= X0)
+ return (0);
+
+ pl--;
+ while (pl != 0 && !(++(*pp++)))
+ pl--;
+
+ return (pl != 0 ? 0 : 1);
+ }
+}
+
+#ifdef mips
+#ifndef _NO_PROTO
+BigNumCarry BnnMultiply2Digit (BigNum pp, BigNumLength pl, BigNum mm, BigNumLength ml, BigNumDigit d0, BigNumDigit d1)
+#else /* _NO_PROTO */
+BigNumCarry BnnMultiply2Digit ( pp, pl, mm, ml, d0, d1)
+BigNum pp; BigNumLength pl; BigNum mm; BigNumLength ml; BigNumDigit d0; BigNumDigit d1;
+#endif /* _NO_PROTO */
+
+/*
+ * Provided for compatibility with mips assembler implementation.
+ * Performs the product:
+ * Q = P + M * d0_d1
+ * BB = BBase(P)
+ * Q mod BB => P
+ * Q div BB => CarryOut
+ * Returns the CarryOut.
+ * Assumes Size(P) >= Size(M) + 1.
+ */
+
+{
+ return
+ BnnMultiplyDigit (pp, pl, mm, ml, d0)
+ + BnnMultiplyDigit (pp+1, pl-1, mm, ml, d1);
+}
+#endif /* mips */
+
+
+ /***************************************/
+/* */
+
+ /********************** Division *************************/
+
+
+ /* xh:xl -= yh:yl */
+#define SUB(xh,xl,yh,yl) if (yl > xl) {xl -= yl; xh -= yh + 1;}\
+ else {xl -= yl; xh -= yh;}
+
+#define LOW(x) (x & ((((BigNumDigit)1) << (BN_DIGIT_SIZE / 2)) -1))
+#define HIGH(x) (x >> (BN_DIGIT_SIZE / 2))
+#define L2H(x) (x << (BN_DIGIT_SIZE / 2))
+
+
+#ifndef _NO_PROTO
+BigNumDigit BnnDivideDigit (BigNum qq, BigNum nn, BigNumLength nl, BigNumDigit d)
+#else /* _NO_PROTO */
+BigNumDigit BnnDivideDigit ( qq, nn, nl, d)
+BigNum qq; BigNum nn; BigNumLength nl; BigNumDigit d;
+#endif /* _NO_PROTO */
+
+/* Performs the quotient: N div d => Q
+ * Returns R = N mod d
+ * Assumes leading digit of N < d, and d > 0.
+ */
+
+{
+ /* test computed at compile time */
+ if (sizeof (BigNumProduct) > sizeof (BigNumDigit))
+ {
+ register BigNumProduct quad;
+
+
+ nn += nl;
+ nl--;
+ qq += nl;
+ quad = *(--nn);
+
+ while (nl != 0)
+ {
+ nl--;
+ quad = (quad << BN_DIGIT_SIZE) | *(--nn);
+ *(--qq) = quad / d;
+ quad = quad % d;
+ }
+
+ return (quad);
+ }
+ else
+ {
+ int k;
+ BigNumLength orig_nl;
+ BigNumDigit rh; /* Two halves of current remainder */
+ BigNumDigit rl; /* Correspond to quad above */
+ register BigNumDigit qa; /* Current appr. to quotient */
+ register BigNumDigit ph, pl; /* product of c and qa */
+ BigNumDigit ch, cl, prev_qq;
+
+
+ /* Normalize divisor */
+ k = BnnNumLeadingZeroBitsInDigit (d);
+ if (k != 0)
+ {
+ prev_qq = qq[-1];
+ orig_nl = nl;
+ d <<= k;
+ BnnShiftLeft (nn, nl, k);
+ }
+
+ nn += nl;
+ nl--;
+ qq += nl;
+
+ ch = HIGH (d);
+ cl = LOW (d);
+
+ rl = *(--nn);
+
+ while (nl != 0)
+ {
+ nl--;
+ rh = rl;
+ rl = *(--nn);
+ qa = rh / ch; /* appr. quotient */
+
+ /* Compute ph, pl */
+ pl = cl * qa;
+ ph = ch * qa;
+ ph += HIGH (pl);
+ pl = L2H (pl);
+
+ /* While ph:pl > rh:rl, decrement qa, adjust qh:ql */
+ while (ph > rh || ph == rh && pl > rl)
+ {
+ qa--;
+ SUB (ph, pl, ch, L2H (cl));
+ }
+
+ SUB (rh, rl, ph, pl);
+
+ /* Top half of quotient is correct; save it */
+ *(--qq) = L2H (qa);
+ qa = (L2H (rh) | HIGH (rl)) / ch;
+
+ /* Approx low half of q */
+ /* Compute ph, pl, again */
+ pl = cl * qa;
+ ph = ch * qa;
+ ph += HIGH (pl);
+ pl = LOW (pl) | L2H (LOW (ph));
+ ph = HIGH (ph);
+
+ /* While ph:pl > rh:rl, decrement qa, adjust qh:ql */
+ while (ph > rh || ph == rh && pl > rl)
+ {
+ qa--;
+ SUB (ph, pl, 0, d);
+ }
+
+ /* Subtract ph:pl from rh:rl; we know rh will be 0 */
+ rl -= pl;
+ *qq |= qa;
+ }
+
+ /* Denormalize dividend */
+ if (k != 0) {
+ if((qq > nn) && (qq < &nn[orig_nl])) {
+ /* Overlap between qq and nn. Care of *qq! */
+ orig_nl = (qq - nn);
+ BnnShiftRight (nn, orig_nl, k);
+ nn[orig_nl - 1] = prev_qq;
+ } else if(qq == nn) {
+ BnnShiftRight(&nn[orig_nl - 1], 1, k);
+ } else {
+ BnnShiftRight (nn, orig_nl, k);
+ } }
+ return (rl >> k);
+ }
+}
+
+ /***************************************/
+
+
diff --git a/otherlibs/num/bignum/c/bn/bnCmp.c b/otherlibs/num/bignum/c/bn/bnCmp.c
new file mode 100644
index 000000000..b678124d1
--- /dev/null
+++ b/otherlibs/num/bignum/c/bn/bnCmp.c
@@ -0,0 +1,77 @@
+/* Copyright Digital Equipment Corporation & INRIA 1988, 1989 */
+/* Last modified_on Fri Oct 5 16:13:31 GMT+1:00 1990 by herve */
+/* modified_on Fri Aug 10 17:21:47 GMT+2:00 1990 by shand */
+
+
+/* bnCmp.c: a piece of the bignum kernel written in C */
+
+
+ /***************************************/
+
+#define BNNMACROS_OFF
+#include "BigNum.h"
+
+ /*** copyright ***/
+
+static char copyright[]="@(#)bnCmp.c: copyright Digital Equipment Corporation & INRIA 1988, 1989, 1990\n";
+
+
+#ifndef _NO_PROTO
+Boolean BnnIsZero (BigNum nn, BigNumLength nl)
+#else /* _NO_PROTO */
+Boolean BnnIsZero (nn, nl)
+BigNum nn; BigNumLength nl;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns TRUE iff N = 0
+ */
+
+{
+ return (BnnNumDigits (nn, nl) == 1 && (nl == 0 || BnnIsDigitZero (*nn)));
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+BigNumCmp BnnCompare (BigNum mm, BigNumLength ml, BigNum nn, BigNumLength nl)
+#else /* _NO_PROTO */
+BigNumCmp BnnCompare (mm, ml, nn, nl)
+BigNum mm; BigNumLength ml; BigNum nn; BigNumLength nl;
+#endif /* _NO_PROTO */
+
+/*
+ * return
+ * BN_GT iff M > N
+ * BN_EQ iff N = N
+ * BN_LT iff N < N
+*/
+
+{
+ register BigNumCmp result = BN_EQ;
+
+
+ ml = BnnNumDigits (mm, ml);
+ nl = BnnNumDigits (nn, nl);
+
+ if (ml != nl)
+ return (ml > nl ? BN_GT : BN_LT);
+
+ while (result == BN_EQ && ml-- > 0)
+ result = BnnCompareDigits (*(mm+ml), *(nn+ml));
+
+ return (result);
+
+/**** USE memcmp() instead: extern int memcmp ();
+
+ if (ml == nl)
+ {
+ lex = memcmp (mm, nn, nl*BN_DIGIT_SIZE/BN_BYTE_SIZE);
+ return (lex > 0 ? BN_GT: (lex == 0 ? BN_EQ: BN_LT));
+ }
+ else
+ return (ml > nl ? BN_GT : BN_LT);
+******/
+}
diff --git a/otherlibs/num/bignum/c/bn/bnDivide.c b/otherlibs/num/bignum/c/bn/bnDivide.c
new file mode 100644
index 000000000..e25938bb8
--- /dev/null
+++ b/otherlibs/num/bignum/c/bn/bnDivide.c
@@ -0,0 +1,156 @@
+/* Copyright Digital Equipment Corporation & INRIA 1988, 1989 */
+/* Last modified_on Mon Apr 15 18:51:35 GMT+2:00 1991 by herve */
+/* modified_on Fri Mar 30 3:29:17 GMT+2:00 1990 by shand */
+
+
+/* bnDivide.c: a piece of the bignum kernel written in C */
+
+
+ /***************************************/
+
+#define BNNMACROS_OFF
+#include "BigNum.h"
+
+ /*** copyright ***/
+
+static char copyright[]="@(#)bnDivide.c: copyright Digital Equipment Corporation & INRIA 1988, 1989, 1990\n";
+
+
+static divide (nn, nl, dd, dl)
+
+ BigNum nn, dd;
+register BigNumLength nl, dl;
+
+/*
+ * In-place division.
+ *
+ * Input (N has been EXTENDED by 1 PLACE; D is normalized):
+ * +-----------------------------------------------+----+
+ * | N EXT|
+ * +-----------------------------------------------+----+
+ *
+ * +-------------------------------+
+ * | D 1|
+ * +-------------------------------+
+ *
+ * Output (in place of N):
+ * +-------------------------------+---------------+----+
+ * | R | Q |
+ * +-------------------------------+---------------+----+
+ *
+ * Assumes:
+ * N > D
+ * Size(N) > Size(D)
+ * last digit of N < last digit of D
+ * D is normalized (Base/2 <= last digit of D < Base)
+ */
+
+{
+ register int ni;
+ BigNumDigit DDigit, BaseMinus1, QApp, RApp;
+
+
+ /* Initialize constants */
+ BnnSetDigit (&BaseMinus1, 0);
+ BnnComplement(&BaseMinus1, 1);
+
+ /* Save the most significant digit of D */
+ BnnAssign (&DDigit, dd+dl-1, 1);
+
+ /* Replace D by Base - D */
+ BnnComplement (dd, dl);
+ BnnAddCarry (dd, dl, 1);
+
+ /* For each digit of the divisor, from most significant to least: */
+ nl += 1;
+ ni = nl-dl;
+ while (--ni >= 0)
+ {
+ /* Compute the approximate quotient */
+ nl--;
+
+ /* If first digits of numerator and denominator are the same, */
+ if (BnnCompareDigits (*(nn+nl), DDigit) == BN_EQ)
+ /* Use "Base - 1" for the approximate quotient */
+ BnnAssign (&QApp, &BaseMinus1, 1);
+ else
+ /* Divide the first 2 digits of N by the first digit of D */
+ RApp = BnnDivideDigit (&QApp, nn+nl-1, 2, DDigit);
+
+ /* Compute the remainder */
+ BnnMultiplyDigit (nn+ni, dl+1, dd, dl, QApp);
+
+ /* Correct the approximate quotient, in case it was too large */
+ while (BnnCompareDigits (*(nn+nl), QApp) != BN_EQ)
+ {
+ BnnSubtract (nn+ni, dl+1, dd, dl, 1); /* Subtract D from N */
+ BnnSubtractBorrow (&QApp, 1, 0); /* Q -= 1 */
+ }
+ }
+
+ /* Restore original D */
+ BnnComplement (dd, dl);
+ BnnAddCarry (dd, dl, 1);
+}
+
+
+ /***************************************/
+/* */
+
+
+void BnnDivide (nn, nl, dd, dl)
+
+ BigNum nn, dd;
+register BigNumLength nl, dl;
+
+/*
+ * Performs the quotient:
+ * N div D => high-order bits of N, starting at N[dl]
+ * N mod D => low-order dl bits of N
+ *
+ * Assumes
+ * Size(N) > Size(D),
+ * last digit of N < last digit of D (if N > D).
+ */
+
+{
+ BigNumDigit nshift;
+
+
+ /* Take care of easy cases first */
+ switch (BnnCompare (nn, nl, dd, dl))
+ {
+ case BN_LT: /* n < d */
+ ; /* N => R */
+ BnnSetToZero (nn+dl, nl-dl); /* 0 => Q */
+ return;
+ case BN_EQ: /* n == d */
+ BnnSetToZero (nn, nl); /* 0 => R */
+ BnnSetDigit (nn+dl, 1); /* 1 => Q */
+ /* bug fixed Mon Apr 15 18:36:50 GMT+2:00 1991 by jch,
+ was BnnSetDigit (nn+nl-1, 1); */
+ return;
+ }
+
+ /* here: n > d */
+
+ /* If divisor is just 1 digit, use a special divide */
+ if (dl == 1)
+ *nn = BnnDivideDigit (nn+1, nn, nl, *dd); /* note: nn+1 = nn+dl */
+ /* Otherwise, divide one digit at a time */
+ else
+ {
+ /* Normalize */
+ nshift = BnnNumLeadingZeroBitsInDigit (*(dd+dl-1));
+ BnnShiftLeft (dd, dl, nshift);
+ BnnShiftLeft (nn, nl, nshift);
+
+ /* Divide */
+ divide (nn, nl-1, dd, dl);
+
+ /* Unnormalize */
+ BnnShiftRight (dd, dl, nshift);
+ BnnShiftRight (nn, dl, nshift);
+ /* note: unnormalize N <=> unnormalize R (with R < D) */
+ }
+}
diff --git a/otherlibs/num/bignum/c/bn/bnInit.c b/otherlibs/num/bignum/c/bn/bnInit.c
new file mode 100644
index 000000000..d02301508
--- /dev/null
+++ b/otherlibs/num/bignum/c/bn/bnInit.c
@@ -0,0 +1,74 @@
+/* Copyright Digital Equipment Corporation & INRIA 1988, 1989 */
+/* Last modified_on Fri Oct 5 16:28:39 GMT+1:00 1990 by herve */
+/* modified_on Fri Mar 30 3:28:56 GMT+2:00 1990 by shand */
+
+
+/* bnInit.c: a piece of the bignum kernel written in C */
+
+
+ /***************************************/
+
+#define BNNMACROS_OFF
+#include "BigNum.h"
+
+static int Initialized = FALSE;
+
+ /*** copyright ***/
+
+static char copyright[]="@(#)bnInit.c: copyright Digital Equipment Corporation & INRIA 1988, 1989, 1990\n";
+
+
+ /***************************************/
+
+void BnnInit ()
+{
+ if (!Initialized)
+ {
+
+
+ Initialized = TRUE;
+ }
+}
+
+ /***************************************/
+
+void BnnClose ()
+{
+ if (Initialized)
+ {
+
+
+ Initialized = FALSE;
+ }
+}
+
+ /***************************************/
+
+ /* some U*ix standard functions do not exist on VMS */
+ /* neither on MSDOS */
+
+#ifdef NOMEM
+
+/* Copies LENGTH bytes from string SRC to string DST */
+void bcopy(src, dst, length)
+char *src, *dst;
+register int length;
+{
+ for (; length > 0; length--)
+ *dst++ = *src++;
+}
+
+/* Places LENGTH 0 bytes in the string B */
+void bzero(buffer, length)
+char *buffer;
+register int length;
+{
+ for (; length>0; length--)
+ *buffer++ = 0;
+}
+
+#endif
+
+
+
+ /***************************************/
diff --git a/otherlibs/num/bignum/c/bn/bnMult.c b/otherlibs/num/bignum/c/bn/bnMult.c
new file mode 100644
index 000000000..f4ecf8337
--- /dev/null
+++ b/otherlibs/num/bignum/c/bn/bnMult.c
@@ -0,0 +1,84 @@
+/* Copyright Digital Equipment Corporation & INRIA 1988, 1989 */
+/* Last modified_on Tue Oct 9 10:43:48 GMT+1:00 1990 by herve */
+/* modified_on Fri Mar 30 4:13:47 GMT+2:00 1990 by shand */
+
+
+/* bnMult.c: a piece of the bignum kernel written in C */
+
+
+ /***************************************/
+
+#define BNNMACROS_OFF
+#include "BigNum.h"
+
+ /*** copyright ***/
+
+static char copyright[]="@(#)bnMult.c: copyright Digital Equipment Corporation & INRIA 1988, 1989, 1990\n";
+
+
+BigNumCarry BnnMultiply (pp, pl, mm, ml, nn, nl)
+
+register BigNum pp, nn;
+ BigNum mm;
+register BigNumLength pl, nl;
+ BigNumLength ml;
+
+/*
+ * Performs the product:
+ * Q = P + M * N
+ * BB = BBase(P)
+ * Q mod BB => P
+ * Q div BB => CarryOut
+ *
+ * Returns the CarryOut.
+ *
+ * Assumes:
+ * Size(P) >= Size(M) + Size(N),
+ * Size(M) >= Size(N).
+ */
+
+{
+ BigNumCarry c;
+
+ /* Multiply one digit at a time */
+
+ /* the following code give higher performance squaring.
+ ** Unfortunately for small nl, procedure call overheads kills it
+ */
+#ifndef mips_v131
+#ifndef MSDOS
+ /* Squaring code provoke a mips optimizer bug in V1.31 */
+ /* It also doesn't work using MSDOS */
+ if (mm == nn && ml == nl && nl > 6)
+ {
+ register BigNumDigit n_prev = 0;
+ /* special case of squaring */
+ for (c = 0; nl > 0; )
+ {
+ register BigNumDigit n = *nn;
+ c += BnnMultiplyDigit(pp, pl, nn, 1, n);
+ if (n_prev)
+ c += BnnAdd(pp, pl, nn, 1, (BigNumCarry) 0);
+ nl--, nn++;
+ pp += 2, pl -= 2;
+ c += BnnMultiplyDigit(pp-1, pl+1, nn, nl, n+n+n_prev);
+ /* note following if statements are resolved at compile time */
+ if (sizeof(BigNumDigit) == sizeof(short))
+ n_prev = ((short) n) < 0;
+ else if (sizeof(BigNumDigit) == sizeof(int))
+ n_prev = ((int) n) < 0;
+ else if (sizeof(BigNumDigit) == sizeof(long))
+ n_prev = ((long) n) < 0;
+ else
+ n_prev = ((n<<1)>>1) == n;
+ }
+ }
+ else
+#endif
+#endif
+ for (c = 0; nl-- > 0; pp++, nn++, pl--)
+ c += BnnMultiplyDigit (pp, pl, mm, ml, *nn);
+
+ return c;
+}
+
diff --git a/otherlibs/num/bignum/c/bz.c b/otherlibs/num/bignum/c/bz.c
new file mode 100644
index 000000000..10d0c224f
--- /dev/null
+++ b/otherlibs/num/bignum/c/bz.c
@@ -0,0 +1,833 @@
+/* Copyright Digital Equipment Corporation & INRIA 1988, 1989 */
+/* Last modified_on Thu Apr 4 20:01:18 GMT+2:00 1991 by herve */
+/* modified_on Thu Mar 22 20:45:38 GMT+1:00 1990 by shand */
+
+
+/* bz.c: provides an implementation of "unlimited-precision"
+ * arithmetic for signed integers.
+ *
+ * Several conventions are used in the commentary:
+ * A "BigZ" is the name for an arbitrary-precision signed integer.
+ * Capital letters (e.g., "Z") are used to refer to the value of BigZs.
+ */
+
+
+#include "BigZ.h"
+
+
+ /***************************************/
+/*
+#include <stdio.h>
+#include <macros.h>
+#include <math.h>
+#include <malloc.h>
+#include <values.h>
+*/
+
+#define NULL 0
+#define max(a,b) (a<b ? b : a)
+#define abs(x) (x>=0 ? x : -(x))
+#define M_LN2 0.69314718055994530942
+#define M_LN10 2.30258509299404568402
+#define BITSPERBYTE 8
+#define BITS(type) (BITSPERBYTE * (int)sizeof(type))
+#define HIBITI (1 << BITS(int) - 1)
+#define MAXINT (~HIBITI)
+
+ /***************************************/
+
+#define BzToBn(z) ((z)->Digits)
+#define CTOI(c) (c >= '0' && c <= '9' ? c - '0' :\
+ c >= 'a' && c <= 'f' ? c - 'a' + 10:\
+ c >= 'A' && c <= 'F' ? c - 'A' + 10:\
+ 0)
+
+extern char *malloc();
+
+ /*** copyright ***/
+
+static char copyright[]="@(#)bz.c: copyright Digital Equipment Corporation & INRIA 1988, 1989\n";
+
+
+ /***************************************/
+
+static int Initialized = FALSE;
+
+/* constants used by BzToString() and BzFromString() */
+static double BzLog [] =
+{
+ 0,
+ 0, /* log (1) */
+ M_LN2, /* log (2) */
+ 1.098612, /* log (3) */
+ 1.386294, /* log (4) */
+ 1.609438, /* log (5) */
+ 1.791759, /* log (6) */
+ 1.945910, /* log (7) */
+ 2.079442, /* log (8) */
+ 2.197225, /* log (9) */
+ M_LN10, /* log (10) */
+ 2.397895, /* log (11) */
+ 2.484907, /* log (12) */
+ 2.564949, /* log (13) */
+ 2.639057, /* log (14) */
+ 2.708050, /* log (15) */
+ 2.772588, /* log (16) */
+};
+
+/* */
+
+
+#ifndef _NO_PROTO
+void BzInit (void)
+#else /* _NO_PROTO */
+void BzInit ()
+#endif /* _NO_PROTO */
+{
+ if (!Initialized)
+ {
+ BnnInit ();
+ Initialized = TRUE;
+ }
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+BigZ BzCreate (BigNumLength Size)
+#else /* _NO_PROTO */
+BigZ BzCreate (Size)
+BigNumLength Size;
+#endif /* _NO_PROTO */
+
+/*
+ * Allocates a BigZ of the desired size.
+ * Sets it to 0.
+ */
+
+{
+ BigZ z;
+
+
+ if ((z = (BigZ) (malloc (sizeof (struct BigZHeader) + Size * sizeof (BigNumDigit)))) != NULL)
+ {
+ /* reset digits */
+ BnnSetToZero (BzToBn (z), Size);
+
+ /* init header */
+ BzSetSize (z, Size);
+ BzSetSign (z, BZ_ZERO);
+ }
+
+ return (z);
+}
+
+
+
+#ifndef _NO_PROTO
+void BzFree (BigZ z)
+#else /* _NO_PROTO */
+void BzFree (z)
+BigZ z;
+#endif /* _NO_PROTO */
+
+/*
+ * Frees an existing BigZ.
+ */
+
+{
+ free (z);
+}
+
+ /***************************************/
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+void BzFreeString (char *s)
+#else /* _NO_PROTO */
+void BzFreeString (s)
+char *s;
+#endif /* _NO_PROTO */
+
+/*
+ * Frees an existing BigZ allocated string.
+ */
+
+{
+ free (s);
+}
+
+ /***************************************/
+/* */
+
+#ifndef _NO_PROTO
+BigNumLength BzNumDigits (BigZ z)
+#else /* _NO_PROTO */
+BigNumLength BzNumDigits (z)
+BigZ z;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns the number of digits used by z.
+ */
+
+{
+ return (BnnNumDigits (BzToBn (z), BzGetSize (z)));
+}
+
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+BigZ BzCopy (BigZ z)
+#else /* _NO_PROTO */
+BigZ BzCopy (z)
+BigZ z;
+#endif /* _NO_PROTO */
+
+/*
+ * Creates a copy of the passed BigZ.
+ */
+
+{
+ BigZ y;
+ int zl;
+
+
+ zl = BzNumDigits (z);
+ if ((y = BzCreate (zl)) != NULL)
+ {
+ /* copy the digits */
+ BnnAssign (BzToBn (y), BzToBn (z), zl);
+
+ /* copy the header WITHOUT the size !! */
+ BzSetSign (y, BzGetSign (z));
+ }
+
+ return (y);
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+BigZ BzNegate (BigZ z)
+#else /* _NO_PROTO */
+BigZ BzNegate (z)
+BigZ z;
+#endif /* _NO_PROTO */
+
+/*
+ * Negates the passed BigZ.
+ */
+
+{
+ BigZ y;
+
+ y = BzCopy (z);
+ BzSetSign (y, BzGetOppositeSign (z));
+
+ return (y);
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+BigZ BzAbs (BigZ z)
+#else /* _NO_PROTO */
+BigZ BzAbs (z)
+BigZ z;
+#endif /* _NO_PROTO */
+
+/*
+ * Takes the absolute value of the passed BigZ.
+ */
+
+{
+ BigZ y;
+
+ y = BzCopy (z);
+ BzSetSign (y, abs (BzGetSign (z)));
+
+ return (y);
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+BzCmp BzCompare (BigZ y, BigZ z)
+#else /* _NO_PROTO */
+BzCmp BzCompare (y, z)
+BigZ y; BigZ z;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns BZ_GT if Y > Z,
+ * BZ_LT if Y < Z,
+ * BZ_EQ otherwise.
+ */
+
+{
+ return (BzGetSign (y) > BzGetSign (z) ? BZ_GT :
+ BzGetSign (y) < BzGetSign (z) ? BZ_LT :
+ BzGetSign (y) > 0 ? BnnCompare (BzToBn (y), BzGetSize (y),
+ BzToBn (z), BzGetSize (z)) :
+ BzGetSign (y) < 0 ? BnnCompare (BzToBn (z), BzGetSize (z),
+ BzToBn (y), BzGetSize (y)) :
+ BZ_EQ);
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+BigZ BzAdd (BigZ y, BigZ z)
+#else /* _NO_PROTO */
+BigZ BzAdd (y, z)
+BigZ y; BigZ z;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns Y + Z.
+ */
+
+{
+ BigZ n;
+ int yl;
+ int zl;
+
+
+ yl = BzNumDigits (y);
+ zl = BzNumDigits (z);
+
+ if (BzGetSign (y) == BzGetSign (z))
+ {
+ /* Add magnitudes if signs are the same */
+ switch (BnnCompare (BzToBn (y), yl, BzToBn (z), zl))
+ {
+ case BZ_EQ:
+ case BZ_GT: /* |Y| >= |Z| */
+
+ if ((n = BzCreate (yl+1)) != NULL)
+ {
+ BnnAssign (BzToBn (n), BzToBn (y), yl);
+ BnnAdd (BzToBn (n), yl+1, BzToBn (z), zl, (BigNumCarry) 0);
+ BzSetSign (n, BzGetSign (y));
+ }
+ break;
+
+ default: /* BZ_LT: |Y| < |Z| */
+
+ if ((n = BzCreate (zl+1)) != NULL)
+ {
+ BnnAssign (BzToBn (n), BzToBn (z), zl);
+ BnnAdd (BzToBn (n), zl+1, BzToBn (y), yl, (BigNumCarry) 0);
+ BzSetSign (n, BzGetSign (z));
+ }
+ break;
+ }
+ }
+/* */
+
+
+ else
+ {
+ /* Subtract magnitudes if signs are different */
+ switch (BnnCompare (BzToBn (y), yl, BzToBn (z), zl))
+ {
+ case BZ_EQ: /* Y = -Z */
+
+ n = BzCreate (1);
+ break;
+
+ case BZ_GT: /* |Y| > |Z| */
+
+ if ((n = BzCreate (yl)) != NULL)
+ {
+ BnnAssign (BzToBn (n), BzToBn (y), yl);
+ BnnSubtract (BzToBn (n), yl, BzToBn (z), zl, (BigNumCarry) 1);
+ BzSetSign (n, BzGetSign (y));
+ }
+ break;
+
+ default: /* BZ_LT: |Y| < |Z| */
+
+ if ((n = BzCreate (zl)) != NULL)
+ {
+ BnnAssign (BzToBn (n), BzToBn (z), zl);
+ BnnSubtract (BzToBn (n), zl, BzToBn (y), yl, (BigNumCarry) 1);
+ BzSetSign (n, BzGetSign (z));
+ }
+ break;
+ }
+ }
+
+ return (n);
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+BigZ BzSubtract (BigZ y, BigZ z)
+#else /* _NO_PROTO */
+BigZ BzSubtract (y, z)
+BigZ y; BigZ z;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns Y - Z.
+ */
+
+{
+ if (y == z)
+ return (BzCreate (1));
+ else
+ {
+ BigZ diff;
+
+ BzSetSign (z, BzGetOppositeSign (z));
+ diff = BzAdd (y, z);
+ BzSetSign (z, BzGetOppositeSign (z));
+
+ return diff;
+ }
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+BigZ BzMultiply (BigZ y, BigZ z)
+#else /* _NO_PROTO */
+BigZ BzMultiply (y, z)
+BigZ y; BigZ z;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns Y * Z.
+ */
+
+{
+ BigZ n;
+ int yl, zl;
+
+
+ yl = BzNumDigits (y);
+ zl = BzNumDigits (z);
+
+ if ((n = BzCreate (yl+zl)) != NULL)
+ {
+ BnnMultiply (BzToBn (n), yl+zl, BzToBn (y), yl, BzToBn (z), zl);
+ BzSetSign (n, BzGetSign (y) * BzGetSign (z));
+ }
+
+ return (n);
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+BigZ BzDivide (BigZ y, BigZ z, BigZ *r)
+#else /* _NO_PROTO */
+BigZ BzDivide (y, z, r)
+BigZ y; BigZ z; BigZ *r;
+#endif /* _NO_PROTO */
+
+/*
+ * Sets Y mod Z => R,
+ * Returns Y div Z => Q
+ *
+ * such that Y = ZQ + R
+ * and 0 <= R < |Z|.
+ *
+ * Return NULL if Z = 0
+ *
+ * Return floor(Y/Z) if Z > 0
+ * otherwise return ceil(Y/Z)
+ * where / is the real numbers division.
+ */
+
+{
+ BigZ q;
+ int yl, zl, ql, rl;
+ Boolean rnotnul;
+
+
+ if (BzGetSign (z) == BZ_ZERO)
+ return (NULL);
+
+ yl = BzNumDigits (y);
+ zl = BzNumDigits (z);
+
+ /* max +1 since BnnAddCarry can overflow */
+ ql = max (yl-zl+1, 1) +1;
+ rl = max (zl,yl) + 1;
+
+ /* Set up quotient, remainder */
+ q = BzCreate (ql);
+ *r = BzCreate (rl);
+
+ if (!*r || !q)
+ return (NULL);
+
+ BnnAssign (BzToBn (*r), BzToBn (y), yl);
+
+ /* Do the division */
+ BnnDivide (BzToBn (*r), rl, BzToBn (z), zl);
+ BnnAssign (BzToBn (q), BzToBn (*r) + zl, rl-zl);
+ BnnSetToZero (BzToBn (*r) + zl, rl-zl);
+ rl = zl;
+
+ /* Correct the signs, adjusting the quotient and remainder */
+ rnotnul = !BnnIsZero (BzToBn (*r), rl);
+ if (BzGetSign (y) == BZ_MINUS && rnotnul)
+ {
+ /* Y < 0, R > 0: (Q+1)=>Q, Z-R=>R */
+ BnnAddCarry (BzToBn (q), ql, (BigNumCarry) 1);
+
+ BzSetSign (q, BzGetOppositeSign (z));
+ BnnComplement (BzToBn (*r), rl);
+ BnnAdd (BzToBn (*r), rl, BzToBn (z), zl, (BigNumCarry) 1);
+ }
+ else
+ BzSetSign (q, BzGetSign (y) * BzGetSign (z));
+
+ if (BnnIsZero (BzToBn(q),ql))
+ BzSetSign (q,BZ_ZERO);
+
+ /* Correct the sign of the remainder */
+ if (rnotnul)
+ BzSetSign (*r, BZ_PLUS);
+
+ return (q);
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+BigZ BzDiv (BigZ y, BigZ z)
+#else /* _NO_PROTO */
+BigZ BzDiv (y, z)
+BigZ y; BigZ z;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns Y div Z.
+ *
+ * Return NULL if Z = 0
+ *
+ * Return floor(Y/Z) if Z > 0
+ * otherwise return ceil(Y/Z)
+ * where / is the real numbers division
+ */
+
+{
+ BigZ q, r;
+
+
+ q = BzDivide (y, z, &r);
+ BzFree (r);
+
+ return (q);
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+BigZ BzMod (BigZ y, BigZ z)
+#else /* _NO_PROTO */
+BigZ BzMod (y, z)
+BigZ y; BigZ z;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns Y mod Z.
+ */
+
+{
+ BigZ r;
+
+
+ BzFree (BzDivide (y, z, &r));
+
+ return (r);
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+char * BzToString (BigZ z, BigNumDigit base)
+#else /* _NO_PROTO */
+char * BzToString (z, base)
+BigZ z; BigNumDigit base;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns a pointer to a string that represents Z in the specified base.
+ * Assumes 2 <= base <= 16.
+ */
+
+{
+ char * string;
+ BigZ y, q, t;
+ BigNumDigit r;
+
+ static char Digit[] = "0123456789ABCDEF";
+ char * s;
+ int sd;
+ int zl, sl;
+
+
+ if (base < 2 || base > 16)
+ return (NULL);
+
+ /* Allocate BigNums and set up string */
+ zl = BzNumDigits (z) + 1;
+ sl = BzLog[2] * BN_DIGIT_SIZE * zl / BzLog[base] + 3;
+
+ y = BzCreate (zl);
+ q = BzCreate (zl);
+
+ string = malloc (sl * sizeof (char));
+
+ if (!y || !q || !string)
+ return (NULL);
+
+ BnnAssign (BzToBn (y), BzToBn (z), zl-1);
+ s = string + sl;
+
+ /* Divide Z by base repeatedly; successive digits given by remainders */
+ *--s = '\0';
+ if (BzGetSign (z) == BZ_ZERO)
+ *--s = '0';
+ else
+ do
+ {
+ r = BnnDivideDigit (BzToBn (q), BzToBn (y), zl, base);
+ *--s = Digit[r];
+
+ /* exchange y and q (to avoid BzMove (y, q) */
+ t = q, q = y, y = t;
+ } while (!BnnIsZero (BzToBn (y), zl));
+
+ /* Set sign if negative */
+ if (BzGetSign (z) < 0)
+ *--s = '-';
+
+ /* and move string into position */
+ if ((sd = s-string) > 0)
+ while (s < string + sl)
+ {
+ *(s-sd) = *s;
+ s++;
+ }
+
+ /* Free temporary BigNums and return the string */
+ BzFree(y);
+ BzFree(q);
+
+ return string;
+}
+
+ /***************************************/
+/* */
+
+
+#ifndef _NO_PROTO
+BigZ BzFromString (char *s, BigNumDigit base)
+#else /* _NO_PROTO */
+BigZ BzFromString (s, base)
+char *s; BigNumDigit base;
+#endif /* _NO_PROTO */
+
+/*
+ * Creates a BigZ whose value is represented by "string" in the
+ * specified base. The "string" may contain leading spaces,
+ * followed by an optional sign, followed by a series of digits.
+ * Assumes 2 <= base <= 16.
+ * When called from C, only the first 2 arguments are passed.
+ */
+
+{
+ BigZ z, p, t;
+ BzSign sign;
+ int zl;
+
+
+ /* Throw away any initial space */
+ while (*s == ' ')
+ s++;
+
+ /* Allocate BigNums */
+ zl = strlen (s) * BzLog[base] / (BzLog[2] * BN_DIGIT_SIZE) + 1;
+
+ z = BzCreate (zl);
+ p = BzCreate (zl);
+
+ if (!z || !p)
+ return (NULL);
+
+ /* Set up sign, base, initialize result */
+ sign = (*s == '-' ? (s++, BZ_MINUS) : *s == '+' ? (s++, BZ_PLUS) : BZ_PLUS);
+
+ /* Multiply in the digits of the string, one at a time */
+ for (; *s != '\0'; s++)
+ {
+ BnnSetToZero (BzToBn (p), zl);
+ BnnSetDigit (BzToBn (p), CTOI (*s));
+ BnnMultiplyDigit (BzToBn (p), zl, BzToBn (z), zl, base);
+
+ /* exchange z and p (to avoid BzMove (z, p) */
+ t = p, p = z, z = t;
+ }
+
+ /* Set sign of result */
+ BzSetSign (z, BnnIsZero (BzToBn (z), zl) ? BZ_ZERO : sign);
+
+ /* Free temporary BigNums */
+ BzFree (p);
+
+ return (z);
+}
+
+ /***************************************/
+
+#ifndef _NO_PROTO
+BigZ BzFromInteger (int i)
+#else /* _NO_PROTO */
+BigZ BzFromInteger (i)
+int i;
+#endif /* _NO_PROTO */
+
+{
+ BigZ z;
+
+
+ z = BzCreate (1);
+
+ z->Digits[0] = abs (i);
+
+ if (i > 0)
+ BzSetSign (z, BZ_PLUS);
+ else
+ if (i < 0)
+ BzSetSign (z, BZ_MINUS);
+ else
+ BzSetSign (z, BZ_ZERO);
+
+ return z;
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+int BzToInteger (BigZ z)
+#else /* _NO_PROTO */
+int BzToInteger (z)
+BigZ z;
+#endif /* _NO_PROTO */
+
+{
+ if (BzNumDigits (z) > 1)
+ return (MAXINT);
+
+ if (BzGetSign (z) == BZ_MINUS)
+ return (- z->Digits[0]);
+ else
+ return (z->Digits[0]);
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+BigZ BzFromBigNum (BigNum n, BigNumLength nl)
+#else /* _NO_PROTO */
+BigZ BzFromBigNum (n, nl)
+BigNum n; BigNumLength nl;
+#endif /* _NO_PROTO */
+
+{
+ BigZ z;
+ int i;
+
+
+ z = BzCreate (nl);
+
+ /* set the sign of z such that the pointer n is unchanged yet */
+ if (BnnIsZero (n, nl))
+ BzSetSign (z, BZ_ZERO);
+ else
+ BzSetSign (z, BZ_PLUS);
+
+ for (i = 0; i < nl; i++, n++)
+ z->Digits[i] = *n;
+
+ return z;
+}
+
+ /***************************************/
+
+#ifndef _NO_PROTO
+BigNum BzToBigNum (BigZ z, BigNumLength *nl)
+#else /* _NO_PROTO */
+BigNum BzToBigNum (z, nl)
+BigZ z; BigNumLength *nl;
+#endif /* _NO_PROTO */
+
+{
+ BigNum n, m;
+ int i;
+
+
+ if (BzGetSign (z) == BZ_MINUS)
+ return NULL;
+
+ *nl = BzNumDigits (z);
+
+ if ((n = (BigNum) (malloc (((*nl+1) * sizeof (BigNumDigit))))) != NULL)
+ {
+ *n = *nl; /* set size */
+
+ for (i = 0, m = ++n; i < *nl; i++, m++)
+ *m = z->Digits[i];
+ }
+
+ return n;
+}
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+void BzClose (void)
+#else /* _NO_PROTO */
+void BzClose ()
+#endif /* _NO_PROTO */
+{
+ if (Initialized)
+ {
+ BnnClose ();
+ Initialized = FALSE;
+ }
+}
+
+ /***************************************/
diff --git a/otherlibs/num/bignum/c/bzf.c b/otherlibs/num/bignum/c/bzf.c
new file mode 100644
index 000000000..7186452aa
--- /dev/null
+++ b/otherlibs/num/bignum/c/bzf.c
@@ -0,0 +1,50 @@
+/* Copyright Digital Equipment Corporation & INRIA 1988, 1989 */
+/* Last modified_on Mon Jan 23 16:05:27 GMT+1:00 1989 by herve */
+
+/*
+ * bzf.c: Miscellaneous functions built on top of BigZ.
+ *
+ */
+
+
+#include "BigZ.h"
+
+ /***************************************/
+
+#define BzToBn(z) ((z)->Digits)
+
+ /***************************************/
+
+
+#ifndef _NO_PROTO
+BigZ BzFactorial (BigZ z)
+#else /* _NO_PROTO */
+BigZ BzFactorial (z)
+BigZ z;
+#endif /* _NO_PROTO */
+
+/*
+ * Returns Z!
+ * Assumes Z < Base.
+ */
+
+{
+ BigZ f;
+ BigNumDigit zval;
+ int fl = 1;
+
+
+ zval = BnnGetDigit (BzToBn (z));
+ f = BzCreate (zval+1);
+ BnnSetDigit (BzToBn (f), 1);
+ BzSetSign (f, BzGetSign (z));
+
+ while (zval-- > 1)
+ {
+ BnnMultiplyDigit (BzToBn (f), fl+1, BzToBn (f), fl, zval);
+ fl = BnnNumDigits (BzToBn (f), fl+1);
+ }
+
+ return (f);
+}
+
diff --git a/otherlibs/num/bignum/c/bztest.c b/otherlibs/num/bignum/c/bztest.c
new file mode 100644
index 000000000..2d06b184e
--- /dev/null
+++ b/otherlibs/num/bignum/c/bztest.c
@@ -0,0 +1,167 @@
+/* Copyright Digital Equipment Corporation & INRIA 1988, 1989 */
+/* Last modified_on Tue Feb 25 1:27:57 GMT+1:00 1992 by shand */
+/* modified_on Mon Apr 15 18:44:14 GMT+2:00 1991 by herve */
+
+#include <stdio.h>
+#include "BigZ.h"
+
+#ifndef MSDOS
+#define S(A,B) strcmp(A,B)
+#define P(A) fprintf(stderr,"%d...",A)
+#define E(A,B,C) fprintf(stderr,"\nError in test #%d:\nComputed: %s\nCorrect: %s\n",A,C,B)
+#define T(A,B,C) S(B,C)?E(A,B,C):P(A)
+#else
+void T(A,B,C)
+int A;
+char *B, *C;
+{
+ if (strcmp (B, C))
+ fprintf (stderr, "\nError in test #%d:\nComputed: %s\nCorrect: %s\n",A,C,B);
+ else
+ fprintf (stderr,"%2d...",A);
+}
+#endif
+#define NEWLINE fprintf(stderr,"\n")
+#define To(A) BzToString(A,10)
+#define From(A) BzFromString(A,10)
+#define Abs(A) BzAbs(A)
+#define Neg(A) BzNegate(A)
+#define Add(A,B) BzAdd(A,B)
+#define Sub(A,B) BzSubtract(A,B)
+#define Mul(A,B) BzMultiply(A,B)
+#define Div(A,B) BzDiv(A,B)
+#define Mod(A,B) BzMod(A,B)
+#define Fac(A) BzFactorial(A)
+#define FromI(I) BzFromInteger(I)
+#define Cmp(A,B) BzCompare(A,B)
+#define Sqa(A) Mul(A,A)
+
+#define zero FromI(0)
+#define one FromI(1)
+#define two FromI(2)
+#define minusone FromI(-1)
+
+#ifdef DIGITonUSHORT
+#define two31m1 Sub(Mul(From("65536"),From("32768")),one)
+#else
+#define two31m1 FromI(0x7FFFFFFF)
+#endif
+
+main()
+{
+ BigZ a,b;
+
+ T(1,"12", To(From("12"))) ;
+ T(2,"12345678910", To(From("12345678910"))) ;
+ T(3,"123", To(From("00000123"))) ;
+ T(4,"-123", To(From("-123"))) ;
+ T(5,"-32768", To(From("-32768"))) ;
+ T(6,"-32768", To(Neg(From("32768")))) ;
+ T(7,"-32768", To(Add(From("-16384"),From("-16384")))) ;
+ T(8,"-32768", To(Add(From("-16383"),From("-16385")))) ;
+ T(9,"-32768", To(Mul(From("2"),From("-16384")))) ;
+ T(10,"-16384", To(Div(From("-32768"),From("2")))) ;
+ NEWLINE;
+ T(11,"100000", To(Add(From("1"),From("99999")))) ;
+ T(12,"12343994",To(Add(From("-1684"),From("12345678"))));
+ T(13,"-12329294",To(Sub(From("16384"),From("12345678"))));
+ T(14,"135801",To(Add(From("12345"),From("123456"))));
+ T(15,"123456135801",To(Add(From("12345"),From("123456123456"))));
+ T(16,"135801",To(Add(From("123456"),From("12345"))));
+ T(17,"123456135801",To(Add(From("123456123456"),From("12345"))));
+ T(18,"135801",To(Sub(From("12345"),From("-123456"))));
+ T(19,"123456135801",To(Sub(From("12345"),From("-123456123456"))));
+ T(20,"135801",To(Sub(From("123456"),From("-12345"))));
+ NEWLINE;
+ T(21,"123456135801",To(Sub(From("123456123456"),From("-12345"))));
+ T(22,"-111111",To(Sub(From("12345"),From("123456"))));
+ T(23,"111111",To(Sub(From("123456"),From("12345"))));
+ T(24,"-123456111111",To(Sub(From("12345"),From("123456123456"))));
+ T(25,"123456111111",To(Sub(From("123456123456"),From("12345"))));
+ T(26,"-111111",To(Add(From("12345"),From("-123456"))));
+ T(27,"111111",To(Add(From("123456"),From("-12345"))));
+ T(28,"-123456111111",To(Add(From("12345"),From("-123456123456"))));
+ T(29,"123456111111",To(Add(From("123456123456"),From("-12345"))));
+ T(30,"2", To(Div(From("264195"),From("97200")))) ;
+ NEWLINE;
+ T(31,"27405", To(Mod(From("97200"),From("69795")))) ;
+ T(32,"4294967295", To(Div(From("22685491128062564230891640495451214097"),From("5281877500950955845296219748")))) ;
+ T(33,"99997",To(Add(From("-3"),From("100000"))));
+ T(34,"-100003",To(Add(From("-3"),From("-100000"))));
+ T(35,"999999",To(Sub(From("1000000"),From("1"))));
+ T(36,"999999999",To(Mul(From("12345679"),From("81"))));
+ a = From("1234567");
+ b = From("123456");
+ T(37,"1234567",To(Add(Mul(Div(a,b),b),Mod(a,b))));
+ T(38,"-1234567",To(Add(Mul(Div(Neg(a),Neg(b)),Neg(b)),Mod(Neg(a),Neg(b)))));
+ T(39,"1234567",To(Add(Mul(Div(a,Neg(b)),Neg(b)),Mod(a,Neg(b)))));
+ T(40,"10000000000000000000000",To(Mul(From("-100000000000"),From("-100000000000"))));
+ NEWLINE;
+ T(41,"-10000000000000000000000",To(Mul(From("-100000000000"),From("100000000000"))));
+ T(42,"-10000000000000000000000",To(Mul(From("100000000000"),From("-100000000000"))));
+ T(43,"10000000000000000000000",To(Mul(From("100000000000"),From("100000000000"))));
+ a = Sub(From("10000000000000"),From("10000000000000"));
+ T(44,"0",To(Mod(a,From("1000000000000"))));
+ T(45,"0",To(Div(a,From("1000000000000"))));
+ T(46,"0",To(Mod(Neg(a),From("10000000000000"))));
+ T(47,"0",To(Div(Neg(a),From("10000000000000"))));
+ T(48,"2",To(Div(From("3000"),Sub(From("1234567891234"),From("1234567890000")))));
+ T(49,"532",To(Mod(From("3000"),Sub(From("1234567891234"),From("1234567890000")))));
+ T(50,"9",To(Mod(From("-1234567890"),From("1234567899"))));
+ NEWLINE;
+ T(51,"2",To(Mod(Sub(From("12345678900000"),From("12345678926887")),From("3"))));
+ T(52,"40830949904677684825316369628906250000000000000",To(Mul(From("48270948888581289062500000000"),From("845870049062500000"))));
+ T(53,"22666179639240748063923391983020279316955515",To(Mul(From("6956883693"),From("3258093801689886619170103176686855"))));
+ T(54,"1405006117752879898543142606244511569936384000000000",To(Fac(From("42"))));
+ T(55,"0",To(Mod(Fac(From("13")),Fac(From("9")))));
+ T(56,"0",To(Mod(Fac(From("34")),Fac(From("13")))));
+ T(57,"0",To(Mod(Fac(From("57")),Fac(From("21")))));
+ T(58,"0",To(Mod(Fac(From("40")),Fac(From("39")))));
+ T(59,"59",To(Div(Fac(From("59")),Fac(From("58")))));
+ T(60,"2",To(Div(From("5"),From("2"))));
+ NEWLINE;
+ T(61,"1",To(Mod(From("5"),From("2"))));
+ T(62,"-3",To(Div(From("-5"),From("2"))));
+ T(63,"1",To(Mod(From("-5"),From("2"))));
+ T(64,"3",To(Div(From("-5"),From("-2"))));
+ T(65,"1",To(Mod(From("-5"),From("-2"))));
+ T(66,"-2",To(Div(From("5"),From("-2"))));
+ T(67,"1",To(Mod(From("5"),From("-2"))));
+ T(68,"3",To(Div(From("6"),From("2"))));
+ T(69,"0",To(Mod(From("6"),From("2"))));
+ T(70,"-3",To(Div(From("-6"),From("2"))));
+ NEWLINE;
+ T(71,"0",To(Mod(From("-6"),From("2"))));
+ T(72,"3",To(Div(From("-6"),From("-2"))));
+ T(73,"0",To(Mod(From("-6"),From("-2"))));
+ T(74,"-3",To(Div(From("6"),From("-2"))));
+ T(75,"0",To(Mod(From("6"),From("-2"))));
+ T(76,"0",To(Abs(From("0"))));
+ T(77,"1234567890",To(Abs(From("1234567890"))));
+ T(78,"1234567890",To(Abs(From("-1234567890"))));
+ T(79,"1",BzCompare(From("-1234567890"),From("12345"))<0?"1":"0");
+ T(80,"1",BzGetSign(From("-1234567890"))<0?"1":"0");
+ NEWLINE;
+ T(81,"0", To(Add(From("-1"),Mul(From("-1"),From("-1")))));
+ T(82,"-1",To(Add(From("-1"),Mul(From("0"), From("-1")))));
+ T(83,"-3",To(Add(From("-1"),Mul(From("-2"),From("1" )))));
+ T(84,"1", To(Add(From("-1"),Mul(From("-2"),From("-1")))));
+ T(85,"-1",To(Add(From("1"), Mul(From("-2"),From("1" )))));
+ T(86,"18446744065119617025",To(Mul(From("4294967295"),From("4294967295"))));
+ /* (-2^64 + 2^32 - 1) / 2^32 */
+ T(87,"-4294967296",To(Div(
+ Sub(Mul(Mul(Add(Mul(two31m1,two),one),Mul(Add(two31m1,one), two)),minusone),one),
+ Mul(Add (two31m1,one),two))));
+ T(88,"Equal",(Cmp(Mod(FromI(10),FromI(5)),zero) == BZ_EQ)?"Equal":"Not equal");
+ T(89,"Equal",(Cmp(Div(FromI(4),FromI(5)),zero) == BZ_EQ)?"Equal":"Not equal");
+ a = From ("100000000000000000000000000000000000000");
+ T(90,To (a),To(Div (Sqa (a),a)));
+ /* 90: tests the MIPS & turbo C optimizer bugs. If the special */
+ /* purpose squaring code is enabled and the optimizer */
+ /* messes up, this test will fail */
+ NEWLINE;
+ b = Sqa (a);
+ T(91,To (b),To(Div (Sqa (b),b)));
+ T(92,"-1",To(Div(From("13"),From("-13"))));
+ NEWLINE;
+}
diff --git a/otherlibs/num/bignum/c/testKerN.c b/otherlibs/num/bignum/c/testKerN.c
new file mode 100644
index 000000000..22faa3224
--- /dev/null
+++ b/otherlibs/num/bignum/c/testKerN.c
@@ -0,0 +1,1085 @@
+/* Copyright Digital Equipment Corporation & INRIA 1988, 1989 */
+/* testKerN.c: tests des primitives de KerN */
+/* Last modified_on Thu Feb 20 17:26:13 GMT+1:00 1992 by shand */
+/* modified_on Wed Feb 14 16:14:04 GMT+1:00 1990 by herve */
+/* modified_on 17-OCT-1989 20:35:55.91 by Jim Lawton */
+
+/* You can comment the line below if you want to test the C macro Package
+ instead of C or Assembly functions. */
+
+#define BNNMACROS_OFF 1
+
+
+#include "BigNum.h"
+ /* old types of Bn */
+
+typedef BigNumDigit BigNumType; /* A BigNum's type */
+
+struct BigNumHeader /* The header of a BigNum */
+{
+ BigNumType type;
+ BigNumLength length;
+};
+
+ /* old functions of Bn */
+
+/*
+ * Creation and access to type and length fields.
+ */
+extern char *malloc();
+/* Allocates a BigNum structure and returns a pointer to it */
+BigNum BnAlloc(size) int size; {
+ register BigNum n;
+
+ n = (BigNum) (malloc(sizeof(struct BigNumHeader) +
+ size * sizeof(BigNumDigit))
+ + sizeof(struct BigNumHeader));
+ (((struct BigNumHeader *) n) - 1)->length = size;
+ return(n);
+}
+
+/* Allocates a BigNum, inserts its Type, and returns a pointer to it */
+BigNum BnCreate(type, size) BigNumType type; int size; {
+ register BigNum n;
+
+ n = BnAlloc(size);
+ (((struct BigNumHeader *) n) - 1)->type = type;
+ BnnSetToZero ((n+ 0), size);
+ return(n);
+}
+
+/* Frees a BigNum structure */
+BnFree(n) BigNum n; {
+ free(((struct BigNumHeader *) n) - 1);
+ return 1;
+}
+
+/* Returns the BigNum's Type */
+BigNumType BnGetType(n) BigNum n; {
+ return((((struct BigNumHeader *) n) - 1)->type);
+}
+
+/* Sets the BigNum's Type */
+BnSetType(n, type) BigNum n; BigNumType type; {
+ (((struct BigNumHeader *) n) - 1)->type = type;
+}
+
+/* Returns the number of digits allocated for the BigNum */
+BnGetSize(n) BigNum n; {
+ return((((struct BigNumHeader *) n) - 1)->length);
+}
+
+
+
+ /* structure d'un test */
+
+struct testenv {
+ char *name; /* Le nom de la fonction teste'e. */
+ int flag; /* Pour savoir si l'on continue le Test. */
+ char hist[2048]; /* L'expression qui provoque l'erreur. */
+ char *depend; /* De quoi depend le Test. */
+};
+
+
+ /* Les nombres pre'de'finies. */
+
+static BigNum NumbVect[5][2];
+static BigNum NumbProto, Ntmp2, NtmpBig;
+
+#define RN(n) NumbVect[n][0]
+#define SN(n) NumbVect[n][1]
+
+ /* Taille des nombres utilise's. */
+ /* de la forme 4(n + 1) */
+#define TESTLENGTH 16
+#define DTL TESTLENGTH/2
+#define QTL TESTLENGTH/4
+
+/* Nombre de test. */
+int TestCount, CallDummy = 0;
+
+int dummy()
+{
+ /* a simple way to get control after <n> steps in the debugger */
+ printf("TestCount = %d\n", TestCount);
+}
+
+int TestCountInc()
+{
+ TestCount++;
+ if (TestCount == CallDummy)
+ dummy();
+}
+
+ResetTest(n) int n; {
+ /* Remet le nieme nombre a` la valeur prototype. */
+ BnnAssign ((RN(n)+ 0), ( NumbProto+ 0), TESTLENGTH);
+ BnnAssign ((SN(n)+ 0), ( NumbProto+ 0), TESTLENGTH);
+}
+
+Check(n) int n; {
+ int i;
+ /* Verifie que les n nombres calcules correspondent aux simule's. */
+ for(i = 0; i < n; i++)
+ if(CheckSubRange(i, 0, TESTLENGTH)) return(1);
+ return(FALSE);
+}
+
+CheckSubRange(x, nd, nl) int x, nd, nl; {
+ /* Verifie l'e'galite' des sous-nombres
+ (RN(x), nd, nl) et (SN(x), nd, nl) */
+ while(nl) {
+ nl--;
+ if(BnnCompareDigits (*(RN(x)+ nd), *( SN(x)+ nd))) return(nd + 1);
+ nd++;
+ }
+ return(FALSE);
+}
+
+ShowDiff0(e, r1, r2) struct testenv *e; int r1,r2; {
+ ErrorPrint(e);
+ if(r1 != r2)
+ printf("---- Result is %d and should be %d----\n", r1, r2);
+ return(e->flag);
+}
+
+ShowDiff1(e, r1, r2, n, nd, nl)
+ struct testenv *e; char *n; int r1, r2, nd, nl; {
+ ErrorPrint(e);
+ if(r1 != r2)
+ printf("---- Result is %d and should be %d----\n", r1, r2);
+ ShowOutRange(0, n, nd, nl);
+ ShowSubNumber(0, n, nd, nl);
+ return(e->flag);
+}
+
+ShowDiff2(e, r1, r2, n, nd, nl, m, md, ml)
+ struct testenv *e; char *n, *m; int r1, r2, nd, nl, md, ml; {
+ ErrorPrint(e);
+ if(r1 != r2)
+ printf("---- Result is %d and should be %d----\n", r1, r2);
+ ShowOutRange(0, n, nd, nl);
+ ShowOutRange(1, m, md, ml);
+ ShowSubNumber(0, n, nd, nl);
+ ShowSubNumber(1, m, md, ml);
+ return(e->flag);
+}
+
+ShowDiff3(e, r1, r2, n, nd, nl, m, md, ml, o, od, ol)
+ struct testenv *e; char *n, *m, *o;
+ int r1, r2, nd, nl, md, ml, od, ol; {
+ ErrorPrint(e);
+ if(r1 != r2)
+ printf("---- Result is %d and should be %d----\n", r1, r2);
+ ShowOutRange(0, n, nd, nl);
+ ShowOutRange(1, m, md, ml);
+ ShowOutRange(2, o, od, ol);
+ ShowSubNumber(0, n, nd, nl);
+ ShowSubNumber(1, m, md, ml);
+ ShowSubNumber(2, o, od, ol);
+ return(e->flag);
+}
+
+ShowDiff4(e, r1, r2, n, nd, nl, m, md, ml, o, od, ol, p, pd, pl)
+ struct testenv *e; char *n, *m, *o, *p;
+ int r1, r2, nd, nl, md, ml, od, ol, pd, pl; {
+ ErrorPrint(e);
+ if(r1 != r2)
+ printf("---- Result is %d and should be %d----\n", r1, r2);
+ ShowOutRange(0, n, nd, nl);
+ ShowOutRange(1, m, md, ml);
+ ShowOutRange(2, o, od, ol);
+ ShowOutRange(3, p, pd, pl);
+ ShowSubNumber(0, n, nd, nl);
+ ShowSubNumber(1, m, md, ml);
+ ShowSubNumber(2, o, od, ol);
+ ShowSubNumber(3, p, pd, pl);
+ return(e->flag);
+}
+
+ShowSubNumber(x, n, nd, nl) char *n; int x, nd, nl; {
+ printf("[%s, %d, %d] = ", n, nd, nl);
+ RangeNumberPrint("", RN(x), nd, nl);
+ if(CheckSubRange(x, nd, nl)) {
+ RangeNumberPrint(" Before: ", NumbProto, nd, nl);
+ RangeNumberPrint(" Simulated: ", SN(x), nd, nl);
+} }
+
+RangeNumberPrint(s, n, nd, nl) char *s; BigNum n; int nd, nl; {
+ int first = 1;
+
+ /* Ne marche que si BnGetDigit est garanti!!! */
+ printf("%s {", s);
+ while(nl) {
+ nl--;
+ if(!first) printf(", "); else first = 0;
+ if(BN_DIGIT_SIZE <= 16)
+ printf("%.4X", BnnGetDigit ((n+ nd + nl)));
+ else if(BN_DIGIT_SIZE <= 32)
+ printf("%.8X", BnnGetDigit ((n+ nd + nl)));
+ else printf("%.16lX", BnnGetDigit ((n+ nd + nl)));
+ }
+ printf("}\n");
+}
+
+char *msg = "---- Modification Out of Range of number ";
+ShowOutRange(x, n, nd, nl) char *n; int x, nd, nl; {
+ int i = 0, bol = 0;
+
+ while(i = CheckSubRange(x, i, TESTLENGTH - i)) {
+ if((i <= nd) || (i > nd + nl)) {
+ if(!bol) {
+ bol = 1;
+ printf("%s %s at index: (%d", msg, n, i - 1);
+ } else {
+ printf(" %d", i - 1);
+ } } }
+ if(bol) printf(").\n");
+}
+
+ErrorPrint(e) struct testenv *e; {
+ printf("*** Error in compute : %s\n", e->hist);
+ printf(" Depends on %s\n", e->depend);
+}
+
+/*
+ * Tests des fonctions non redefinisables
+ */
+
+int genlengthvec[] = {9, 8, 1, 0, 2000, 32000,};
+BigNumType gentypevec[] = {0, 1, 2, 3, 4, 5,};
+
+Generique(e) struct testenv *e; {
+ int i;
+ int length, length2;
+ BigNumType type, type2;
+ int fix;
+ BigNum n;
+
+
+ for(i=0; i < 6; i++) {
+ type = gentypevec[i];
+ length = genlengthvec[i];
+ n = BnCreate(type, length);
+ if((type2 = BnGetType(n)) != type) {
+ sprintf(e->hist,"BnGetType(BnCreate(%d, %d));", type, length);
+ if(ShowDiff0(e, type, type2)) return(TRUE);
+ }
+ if((length2 = BnGetSize(n)) != length) {
+ sprintf(e->hist,"BnGetSize(BnCreate(%d, %d));", type, length);
+ if(ShowDiff0(e, length, length2)) return(TRUE);
+ }
+ if(BnFree(n) == 0) {
+ sprintf(e->hist, "BnFree(BnCreate(%d, %d));", type, length);
+ if(ShowDiff0(e, 1, 0)) return(TRUE);
+ }
+ BnSetType((n = BnAlloc(length)), type);
+ if((type2 = BnGetType(n)) != type) {
+ sprintf(e->hist,"BnGetType(BnAlloc(%d, %d));", type, length);
+ if(ShowDiff0(e, type, type2)) return(TRUE);
+ }
+ if((length2 = BnGetSize(n)) != length) {
+ sprintf(e->hist,"BnGetSize(BnAlloc(%d, %d));", type, length);
+ if(ShowDiff0(e, length, length2)) return(TRUE);
+ }
+ if(BnFree(n) == 0) {
+ sprintf(e->hist, "BnFree(BnAlloc(%d, %d));", type, length);
+ if(ShowDiff0(e, 1, 0)) return(TRUE);
+ }
+ }
+ return(FALSE);
+}
+
+/*
+ * BnSetToZero
+ */
+___BnSetToZero___(n, nd, nl) register BigNum n; register int nd, nl; {
+ register int i;
+ for(i=0; i<nl; i++)
+ BnnSetDigit ((n+ nd + i), 0);
+}
+
+TestBnSetToZero(e) struct testenv *e; {
+ int nd, nl;
+
+ e->depend = "(BnSetDigit)";
+ for(nd = 0; nd <= TESTLENGTH; nd++)
+ for(nl = 0; nl <= TESTLENGTH - nd; nl++) {
+ TestCountInc();
+ ResetTest(0);
+ BnnSetToZero ((RN(0)+ nd), nl);
+ ___BnSetToZero___(SN(0), nd, nl);
+ if(Check(1)) {
+ sprintf(e->hist, "%s(n, %d, %d)", e->name, nd, nl);
+ if(ShowDiff1(e, 0, 0, "n", nd, nl)) return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnAssign
+ */
+___BnAssign___(m, md, n, nd, nl) BigNum m, n; int md, nd, nl; {
+ register int i;
+ for(i=0; i<nl; i++)
+ BnnSetDigit ((NtmpBig+ i), BnnGetDigit ((n+ nd + i)));
+ for(i=0; i<nl; i++)
+ BnnSetDigit ((m+ md + i), BnnGetDigit ((NtmpBig+ i)));
+}
+
+TestBnAssign(e) struct testenv *e; {
+ int md, nd, nl;
+
+ e->depend = "(BnGetDigit, BnSetDigit)";
+ for(md = 0; md <= TESTLENGTH; md++)
+ for(nd = 0; nd <= TESTLENGTH; nd++)
+ for(nl=0; ((nl<=TESTLENGTH-nd) && (nl<=TESTLENGTH-md)); nl++) {
+ TestCountInc();
+ ResetTest(0);
+ BnnAssign ((RN(0)+ md), ( RN(0)+ nd), nl);
+ ___BnAssign___(SN(0), md, SN(0), nd, nl);
+ if(Check(1)) {
+ sprintf(e->hist, "%s(m, %d, n, %d, %d)", e->name,
+ md, nd, nl);
+ if(ShowDiff1(e, 0, 0, "n", md, nl)) return(1);
+ } }
+ return(FALSE);
+}
+
+
+/*
+ * BnNumDigits
+ */
+___BnNumDigits___(n, nd, nl) register BigNum n; register int nd, nl; {
+
+ while(nl != 0) {
+ nl--;
+ if(!BnnIsDigitZero (*(n+ nd + nl))) break;
+ }
+ return(nl + 1);
+}
+
+TestBnNumDigits(e) struct testenv *e; {
+ int nd0, nl0, nd, nl, l1, l2;
+
+ e->depend = "(BnIsDigitZero)";
+ for(nd0 = 0; nd0 <= TESTLENGTH; nd0++)
+ for(nl0 = 0; nl0 <= TESTLENGTH - nd0; nl0++)
+ for(nd = 0; nd <= TESTLENGTH; nd++)
+ for(nl = 0; nl <= TESTLENGTH - nd; nl++) {
+ TestCountInc();
+ ResetTest(0);
+ BnnSetToZero ((RN(0)+ nd0), nl0);
+ BnnSetToZero ((SN(0)+ nd0), nl0);
+ l1 = BnnNumDigits ((RN(0)+ nd), nl);
+ l2 = ___BnNumDigits___(SN(0), nd, nl);
+ if(Check(1) || l1 != l2) {
+ sprintf(e->hist, "%s(n, %d, %d)", e->name, nd, nl);
+ if(ShowDiff1(e, l1, l2, "n", nd, nl)) return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnNumLeadingZeroBitsInDigit
+ */
+__BnNumLeadingZeroBitsInDigit__(n, nd) BigNum n; int nd; {
+ int p = 0;
+
+ if(BnnIsDigitZero (*(n+ nd))) return(BN_DIGIT_SIZE);
+ BnnAssign ((Ntmp2+ 0), ( n+ nd), 1);
+ *( Ntmp2+ 1) = BnnShiftLeft ((Ntmp2+ 0), 1, 1);
+ while(BnnIsDigitZero (*(Ntmp2+ 1))) {
+ *( Ntmp2+ 1) = BnnShiftLeft ((Ntmp2+ 0), 1, 1);
+ p++;
+ }
+ return(p);
+}
+
+TestBnNumLeadingZeroBitsInDigit(e) struct testenv *e; {
+ int nd; int l1, l2;
+
+
+ e->depend = "(BnShiftLeft, BnIsDigitZero)";
+ ResetTest(0);
+ for(nd = 0; nd < TESTLENGTH; nd++) {
+ TestCountInc();
+ l1 = BnnNumLeadingZeroBitsInDigit (*(RN(0)+ nd));
+ l2 = __BnNumLeadingZeroBitsInDigit__(SN(0), nd);
+ if(Check(1) || l1 != l2) {
+ sprintf(e->hist, "%s(n, %d)", e->name, nd);
+ if(ShowDiff1(e, l1, l2, "n", nd, 1)) return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnIsDigitZero
+ */
+___BnIsDigitZero___(n, nd) BigNum n; int nd; {
+ if(BnnGetDigit ((n+ nd)) == 0) return(1);
+ return(0);
+}
+
+TestBnIsDigitZero(e) struct testenv *e; {
+ int nd; int l1, l2;
+
+ e->depend = "()";
+ ResetTest(0);
+ for(nd = 0; nd < TESTLENGTH; nd++) {
+ TestCountInc();
+ l1 = BnnIsDigitZero (*(RN(0)+ nd));
+ l2 = ___BnIsDigitZero___(SN(0), nd);
+ if(Check(1) || ((l1 == 0) && (l2 != 0)) ||
+ ((l1 != 0) && (l2 == 0))) {
+ sprintf(e->hist, "%s(n, %d)", e->name, nd);
+ if(ShowDiff1(e, l1, l2, "n", nd, 1)) return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnIsDigitNormalized
+ */
+___BnIsDigitNormalized___(n, nd) BigNum n; int nd; {
+ BnnAssign ((Ntmp2+ 0), ( n+ nd), 1);
+ *( Ntmp2+ 1) = BnnShiftLeft ((Ntmp2+ 0), 1, 1);
+ if(BnnIsDigitZero (*(Ntmp2+ 1))) return(0);
+ return(1);
+}
+
+TestBnIsDigitNormalized(e) struct testenv *e; {
+ int nd; int l1, l2;
+
+ e->depend = "(BnShiftLeft, BnIsDigitZero)";
+ ResetTest(0);
+ for(nd = 0; nd < TESTLENGTH; nd++) {
+ TestCountInc();
+ l1 = BnnIsDigitNormalized (*(RN(0)+ nd));
+ l2 = ___BnIsDigitNormalized___(SN(0), nd);
+ if(Check(1) || ((l1 == 0) && (l2 != 0)) ||
+ ((l1 != 0) && (l2 == 0))) {
+ sprintf(e->hist, "%s(n, %d)", e->name, nd);
+ if(ShowDiff1(e, l1, l2, "n", nd, 1)) return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnIsDigitOdd
+ */
+___BnIsDigitOdd___(n, nd) BigNum n; int nd; {
+ BnnAssign ((Ntmp2+ 0), ( n+ nd), 1);
+ *( Ntmp2+ 1) = BnnShiftRight ((Ntmp2+ 0), 1, 1);
+ if(BnnIsDigitZero (*(Ntmp2+ 1))) return(0);
+ return(1);
+}
+
+TestBnIsDigitOdd(e) struct testenv *e; {
+ int nd; int l1, l2;
+
+ e->depend = "(BnShiftRight, BnIsDigitZero)";
+ ResetTest(0);
+ for(nd = 0; nd < TESTLENGTH; nd++) {
+ TestCountInc();
+ l1 = BnnIsDigitOdd (*(RN(0)+ nd));
+ l2 = ___BnIsDigitOdd___(SN(0), nd);
+ if(Check(1) || ((l1 == 0) && (l2 != 0)) ||
+ ((l1 != 0) && (l2 == 0))) {
+ sprintf(e->hist, "%s(n, %d)", e->name, nd);
+ if(ShowDiff1(e, l1, l2, "n", nd, 1)) return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnCompareDigits
+ */
+___BnCompareDigits___(n, nd, m, md) BigNum n, m; int nd, md; {
+ BnnAssign ((Ntmp2+ 0), ( n+ nd), 1);
+ BnnComplement ((Ntmp2+ 0), 1);
+ if(BnnAdd ((Ntmp2+ 0), 1, ( m+ md), 1, (BigNumCarry) 0)) return(-1);
+ BnnComplement ((Ntmp2+ 0), 1);
+ if(BnnIsDigitZero (*(Ntmp2+ 0))) return(0);
+ return(1);
+}
+
+TestBnCompareDigits(e) struct testenv *e; {
+ int nd, md; int l1, l2;
+
+ e->depend = "(BnComplement, BnAdd, BnIsDigitZero)";
+ ResetTest(0);
+ ResetTest(1);
+ for(nd = 0; nd < TESTLENGTH; nd++)
+ for(md = 0; md < TESTLENGTH; md++) {
+ TestCountInc();
+ l1 = BnnCompareDigits (*(RN(0)+ nd), *( RN(1)+ md));
+ l2 = ___BnCompareDigits___(SN(0), nd, SN(1), md);
+ if(Check(2) || l1 != l2) {
+ sprintf(e->hist, "%s(n, %d, m, %d)", e->name, nd, md);
+ if(ShowDiff2(e, l1, l2, "n", nd, 1, "m", md, 1))
+ return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnComplement
+ */
+___BnComplement___(n, nd, nl) BigNum n; int nd, nl; {
+ int i;
+
+ BnnSetDigit ((Ntmp2+ 0), 0);
+ BnnSubtractBorrow ((Ntmp2+ 0), 1, 0);
+ for(i = 0; i < nl; i++)
+ BnnXorDigits ((n+ nd + i), *( Ntmp2+ 0));
+}
+
+TestBnComplement(e) struct testenv *e; {
+ int nd, nl;
+
+ e->depend = "(BnSubtractBorrow, BnXorDigits)";
+ for(nd = 0; nd <= TESTLENGTH; nd++)
+ for(nl = 0; nl <= TESTLENGTH - nd; nl++) {
+ TestCountInc();
+ ResetTest(0);
+ BnnComplement ((RN(0)+ nd), nl);
+ ___BnComplement___(SN(0), nd, nl);
+ if(Check(1)) {
+ sprintf(e->hist, "%s(n, %d, %d)", e->name, nd, nl);
+ if(ShowDiff1(e, 0, 0, "n", nd, nl)) return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnAndDigits
+ */
+___BnAndDigits___(n, nd, m, md) BigNum n, m; int nd, md; {
+ BnnAssign ((Ntmp2+ 0), ( n+ nd), 1);
+ BnnOrDigits ((Ntmp2+ 0), *( m+ md));
+ BnnXorDigits ((Ntmp2+ 0), *( m+ md));
+ BnnXorDigits ((n+ nd), *( Ntmp2+ 0));
+}
+
+TestBnAndDigits(e) struct testenv *e; {
+ int nd, md;
+
+ e->depend = "(BnOrDigits, BnXorDigits)";
+ ResetTest(1);
+ for(nd = 0; nd < TESTLENGTH; nd++)
+ for(md = 0; md < TESTLENGTH; md++) {
+ TestCountInc();
+ ResetTest(0);
+ BnnAndDigits ((RN(0)+ nd), *( RN(1)+ md));
+ ___BnAndDigits___(SN(0), nd, SN(1), md);
+ if(Check(2)) {
+ sprintf(e->hist, "%s(n, %d, m, %d)", e->name, nd, md);
+ if(ShowDiff2(e, 0, 0, "n", nd, 1, "m", md, 1))
+ return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnOrDigits
+ */
+___BnOrDigits___(n, nd, m, md) BigNum n, m; int nd, md; {
+ BnnAssign ((Ntmp2+ 0), ( n+ nd), 1);
+ BnnAndDigits ((Ntmp2+ 0), *( m+ md));
+ BnnXorDigits ((Ntmp2+ 0), *( m+ md));
+ BnnXorDigits ((n+ nd), *( Ntmp2+ 0));
+}
+
+TestBnOrDigits(e) struct testenv *e; {
+ int nd, md;
+
+ e->depend = "(BnAndDigits, BnXorDigits)";
+ ResetTest(1);
+ for(nd = 0; nd < TESTLENGTH; nd++)
+ for(md = 0; md < TESTLENGTH; md++) {
+ TestCountInc();
+ ResetTest(0);
+ BnnOrDigits ((RN(0)+ nd), *( RN(1)+ md));
+ ___BnOrDigits___(SN(0), nd, SN(1), md);
+ if(Check(2)) {
+ sprintf(e->hist, "%s(n, %d, m, %d)", e->name, nd, md);
+ if(ShowDiff2(e, 0, 0, "n", nd, 1, "m", md, 1))
+ return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnXorDigits
+ */
+___BnXorDigits___(n, nd, m, md) BigNum n, m; int nd, md; {
+ BnnAssign ((Ntmp2+ 0), ( n+ nd), 1);
+ BnnAndDigits ((Ntmp2+ 0), *( m+ md));
+ BnnComplement ((Ntmp2+ 0), 1);
+ BnnOrDigits ((n+ nd), *( m+ md));
+ BnnAndDigits ((n+ nd), *( Ntmp2+ 0));
+}
+
+TestBnXorDigits(e) struct testenv *e; {
+ int nd, md;
+
+ e->depend = "(BnAndDigits, BnComplement, BnOrDigits)";
+ ResetTest(1);
+ for(nd = 0; nd < TESTLENGTH; nd++)
+ for(md = 0; md < TESTLENGTH; md++) {
+ TestCountInc();
+ ResetTest(0);
+ BnnXorDigits ((RN(0)+ nd), *( RN(1)+ md));
+ ___BnXorDigits___(SN(0), nd, SN(1), md);
+ if(Check(2)) {
+ sprintf(e->hist, "%s(n, %d, m, %d)", e->name, nd, md);
+ if(ShowDiff2(e, 0, 0, "n", nd, 1, "m", md, 1))
+ return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnShiftLeft
+ */
+___BnShiftLeft___(n, nd, nl, m, md, s) BigNum n, m; int nd, nl, md; int s; {
+ BnnSetDigit ((m+ md), 2);
+ BnnSetDigit ((Ntmp2+ 0), 1);
+ while(s--) {
+ BnnSetToZero ((NtmpBig+ 0), 2);
+ BnnMultiplyDigit ((NtmpBig+ 0), 2, ( Ntmp2+ 0), 1, *( m+ md));
+ BnnAssign ((Ntmp2+ 0), ( NtmpBig+ 0), 1);
+ }
+ BnnSetToZero ((NtmpBig+ 0), nl + 1);
+ BnnMultiplyDigit ((NtmpBig+ 0), nl + 1, ( n+ nd), nl, *( Ntmp2+ 0));
+ BnnAssign ((n+ nd), ( NtmpBig+ 0), nl);
+ BnnAssign ((m+ md), ( NtmpBig+ nl), 1);
+}
+
+TestBnShiftLeft(e) struct testenv *e; {
+ int nd, nl, md; int s;
+
+ e->depend = "(BnSetToZero, BnMultiplyDigit)";
+ ResetTest(1);
+ for(nd = 0; nd <= TESTLENGTH; nd++)
+ for(nl = 0; nl <= TESTLENGTH - nd; nl++)
+ for(md = 0; md < 2; md++)
+ for(s = 0; s < BN_DIGIT_SIZE; s++) {
+ TestCountInc();
+ ResetTest(0);
+ *( RN(1)+ md) = BnnShiftLeft ((RN(0)+ nd), nl, s);
+ ___BnShiftLeft___(SN(0), nd, nl, SN(1), md, s);
+ if(Check(2)) {
+ sprintf(e->hist, "%s(n, %d, %d, m, %d, %d)",
+ e->name, nd, nl, md, s);
+ if(ShowDiff2(e, 0, 0, "n", nd, nl, "m", md, 1))
+ return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnShiftRight
+ */
+___BnShiftRight___(n, nd, nl, m, md, s) BigNum n, m; int nd, nl, md; int s; {
+ if((nl == 0) || (s == 0)) {
+ BnnSetDigit ((m+ md), 0);
+ return;
+ }
+ BnnAssign ((NtmpBig+ 0), ( n+ nd), nl);
+ *( NtmpBig+ nl) = BnnShiftLeft ((NtmpBig+ 0), nl, BN_DIGIT_SIZE - s);
+ BnnAssign ((n+ nd), ( NtmpBig+ 1), nl);
+ BnnAssign ((m+ md), ( NtmpBig+ 0), 1);
+}
+
+TestBnShiftRight(e) struct testenv *e; {
+ int nd, nl, md; int s;
+
+ e->depend = "(BnShiftLeft)";
+ ResetTest(1);
+ for(nd = 0; nd <= TESTLENGTH; nd++)
+ for(nl = 0; nl <= TESTLENGTH - nd; nl++)
+ for(md = 0; md < 2; md++)
+ for(s = 0; s < BN_DIGIT_SIZE; s++) {
+ TestCountInc();
+ ResetTest(0);
+ *( RN(1)+ md) = BnnShiftRight ((RN(0)+ nd), nl, s);
+ ___BnShiftRight___(SN(0), nd, nl, SN(1), md, s);
+ if(Check(2)) {
+ sprintf(e->hist, "%s(n, %d, %d, m, %d, %d)",
+ e->name, nd, nl, md, s);
+ if(ShowDiff2(e, 0, 0, "n", nd, nl, "m", md, 1))
+ return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnAddCarry
+ */
+BigNumCarry
+___BnAddCarry___(n, nd, nl, r) BigNum n; int nd, nl; int r;{
+ if(r == 0) return(0);
+ BnnComplement ((n+ nd), nl);
+ r = BnnSubtractBorrow ((n+ nd), nl, 0);
+ BnnComplement ((n+ nd), nl);
+ if(r == 0) return(1);
+ return(0);
+}
+
+TestBnAddCarry(e) struct testenv *e; {
+ int nd, nl; int r, l1, l2;
+
+ e->depend = "(BnComplement, BnSubtractBorrow)";
+ for(nd = 0; nd <= TESTLENGTH; nd++)
+ for(nl = 0; nl <= TESTLENGTH - nd; nl++)
+ for(r = 0; r < 2; r++) {
+ TestCountInc();
+ ResetTest(0);
+ l1 = BnnAddCarry ((RN(0)+ nd), nl, r);
+ l2 = ___BnAddCarry___(SN(0), nd, nl, r);
+ if(Check(1) || l1 != l2) {
+ sprintf(e->hist, "%s(n, %d, %d, %d)",
+ e->name, nd, nl, r);
+ if(ShowDiff1(e, l1, l2, "n", nd, nl)) return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnAdd
+ */
+BigNumCarry
+___BnAdd___(n, nd, nl, m, md, ml, r) BigNum n, m; int nd, nl, md, ml; BigNumCarry r;{
+ BnnComplement ((m+ md), ml);
+ r = BnnSubtract ((n+ nd), ml, ( m+ md), ml, r);
+ BnnComplement ((m+ md), ml);
+ return(BnnAddCarry ((n+ nd + ml), nl - ml, r));
+}
+
+TestBnAdd(e) struct testenv *e; {
+ int nd, nl, md, ml; int l1, l2; BigNumCarry r;
+
+ e->depend = "(BnComplement, BnSubtract, BnAddCarry)";
+ ResetTest(1);
+ for(nd = 0; nd <= TESTLENGTH; nd++)
+ for(nl = 0; nl <= TESTLENGTH - nd; nl++)
+ for(md = 0; md <= TESTLENGTH - nl; md++)
+ for(ml = 0; ml <= nl ; ml++)
+ for(r = 0; r < 2; r++) {
+ TestCountInc();
+ ResetTest(0);
+ l1 = BnnAdd ((RN(0)+ nd), nl, ( RN(1)+ md), ml, r);
+ l2 = ___BnAdd___(SN(0), nd, nl, SN(1), md, ml, r);
+ if(Check(2) || l1 != l2) {
+ sprintf(e->hist, "%s(n, %d, %d, m, %d, %d, %d)",
+ e->name, nd, nl, md, ml, r);
+ if(ShowDiff2(e, l1, l2, "n", nd, nl, "m", md, ml))
+ return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnSubtractBorrow
+ */
+BigNumCarry
+___BnSubtractBorrow___(n, nd, nl, r) BigNum n; int nd, nl; BigNumCarry r;{
+ if(r == 1) return(1);
+ BnnComplement ((n+ nd), nl);
+ r = BnnAddCarry ((n+ nd), nl, (BigNumCarry) 1);
+ BnnComplement ((n+ nd), nl);
+ if(r == 0) return(1);
+ return(0);
+}
+
+TestBnSubtractBorrow(e) struct testenv *e; {
+ int nd, nl; int l1, l2; BigNumCarry r;
+
+ e->depend = "(BnComplement, BnAddCarry)";
+ for(nd = 0; nd <= TESTLENGTH; nd++)
+ for(nl = 0; nl <= TESTLENGTH - nd; nl++)
+ for(r = 0; r < 2; r++) {
+ TestCountInc();
+ ResetTest(0);
+ l1 = BnnSubtractBorrow ((RN(0)+ nd), nl, r);
+ l2 = ___BnSubtractBorrow___(SN(0), nd, nl, r);
+ if(Check(1) || l1 != l2) {
+ sprintf(e->hist, "%s(n, %d, %d, %d)",
+ e->name, nd, nl, r);
+ if(ShowDiff1(e, l1, l2, "n", nd, nl)) return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnSubtract
+ */
+BigNumCarry
+___BnSubtract___(n, nd, nl, m, md, ml, r) BigNum n, m; int nd, nl, md, ml; BigNumCarry r;{
+ BnnComplement ((m+ md), ml);
+ r = BnnAdd ((n+ nd), ml, ( m+ md), ml, r);
+ BnnComplement ((m+ md), ml);
+ return(BnnSubtractBorrow ((n+ nd + ml), nl - ml, r));
+}
+
+TestBnSubtract(e) struct testenv *e; {
+ int nd, nl, md, ml; int l1, l2; BigNumCarry r;
+
+ e->depend = "(BnComplement, BnAdd, BnSubtractBorrow)";
+ ResetTest(1);
+ for(nd = 0; nd <= TESTLENGTH; nd++)
+ for(nl = 0; nl <= TESTLENGTH - nd; nl++)
+ for(md = 0; md <= TESTLENGTH - nl; md++)
+ for(ml = 0; ml <= nl ; ml++)
+ for(r = 0; r < 2; r++) {
+ TestCountInc();
+ ResetTest(0);
+ l1 = BnnSubtract ((RN(0)+ nd), nl, ( RN(1)+ md), ml, r);
+ l2 = ___BnSubtract___(SN(0), nd, nl, SN(1), md, ml, r);
+ if(Check(2) || l1 != l2) {
+ sprintf(e->hist, "%s(n, %d, %d, m, %d, %d, %d)",
+ e->name, nd, nl, md, ml, r);
+ if(ShowDiff2(e, l1, l2, "n", nd, nl, "m", md, ml))
+ return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnMultiplyDigit
+ */
+BigNumCarry
+___BnMultiplyDigit___(p, pd, pl, n, nd, nl, m, md) BigNum p, n, m; int pd, pl, nd, nl, md; {
+ BigNumCarry r = 0, ret = 0;
+
+ BnnAssign ((Ntmp2+ 0), ( m+ md), 1);
+ BnnAssign ((NtmpBig+ 0), ( n+ nd), nl);
+ BnnSetToZero ((NtmpBig+ nl), 1);
+ while(!BnnIsDigitZero (*(Ntmp2+ 0))) {
+ if(BnnIsDigitOdd (*(Ntmp2+ 0))) {
+ r = BnnAdd ((p+ pd), pl, ( NtmpBig+ 0), nl + 1, (BigNumCarry) 0);
+ if((ret == 0) && (r == 1)) ret = 1;
+ else if((ret == 1) && (r == 1)) ret = 2;
+ }
+ *( Ntmp2+ 1) = BnnShiftRight ((Ntmp2+ 0), 1, 1);
+ *( Ntmp2+ 1) = BnnShiftLeft ((NtmpBig+ 0), nl + 1, 1);
+ if(!BnnIsDigitZero (*(Ntmp2+ 1))) ret = 3;
+ }
+ return(ret);
+}
+
+TestBnMultiplyDigit(e) struct testenv *e; {
+ int pd, pl, nd, nl, md; int l1, l2;
+
+ e->depend = "(BnSetToZero, BnIsDigitZero, BnIsDigitOdd, BnAdd, BnShiftRight, BnShiftLeft)";
+ ResetTest(1);
+ ResetTest(2);
+ for(pd = 0; pd <= TESTLENGTH; pd++)
+ for(pl = 0; pl <= TESTLENGTH - pd; pl++)
+ for(nd = 0; nd <= TESTLENGTH - pl; nd++)
+ for(nl = 0; nl < pl ; nl++)
+ for(md = 0; md < TESTLENGTH; md++) {
+ TestCountInc();
+ ResetTest(0);
+ l1 = BnnMultiplyDigit ((RN(0)+pd), pl, (RN(1)+nd), nl, *(RN(2)+md));
+ l2 = ___BnMultiplyDigit___(SN(0),pd,pl,SN(1),nd,nl,SN(2),md);
+ if(Check(3) || l1 != l2) {
+ sprintf(e->hist,
+ "BnMultiplyDigit(p, %d, %d, n, %d, %d, m, %d)",
+ pd, pl, nd, nl, md);
+ if(ShowDiff3(e,l1,l2,"p",pd,pl,"n",nd,nl,"m",md,1))
+ return(1);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnDivideDigit
+ */
+TestBnDivideDigit(e) struct testenv *e; {
+ int nd, nl, md, qd, rd, l2;
+
+ e->depend = "(BnSetToZero, BnMultiplyDigit, BnCompareDigits)";
+ ResetTest(2);
+ ResetTest(3);
+ for(nd = 0; nd <= TESTLENGTH - 2; nd++)
+ for(nl = 2; nl <= TESTLENGTH - nd; nl++)
+ for(md = 0; md < TESTLENGTH; md++)
+ for(qd = 0; qd < TESTLENGTH - nl + 1 ; qd++)
+ for(rd = 0; rd < 2; rd++)
+ if((!BnnIsDigitZero (*(RN(3)+ md))) &&
+ (BnnCompareDigits (*(RN(2)+ nd+nl-1), *( RN(3)+ md)) == -1)) {
+ TestCountInc();
+ ResetTest(0);
+ ResetTest(1);
+ *( RN(1)+ rd) = BnnDivideDigit ((RN(0)+ qd), ( RN(2)+ nd), nl, *( RN(3)+ md));
+ BnnAssign ((SN(0)+ qd), ( RN(0)+ qd), nl - 1);
+ BnnAssign ((SN(1)+ rd), ( RN(1)+ rd), 1);
+ BnnSetToZero ((SN(2)+ nd), nl);
+ BnnAssign ((SN(2)+ nd), ( SN(1)+ rd), 1);
+ l2 = BnnMultiplyDigit ((SN(2)+nd), nl, ( SN(0)+qd), nl - 1, *( SN(3)+ md));
+ if(Check(4) || l2 != 0) {
+ sprintf(e->hist,
+ "BnDivideDigit(q, %d, r, %d, n, %d, %d, m, %d)",
+ qd, rd, nd, nl, md);
+ if(ShowDiff4(e, 0, l2, "q", qd, nl - 1, "r", rd, 1,
+ "n", nd, nl, "m", md, 1))
+ return(TRUE);
+ } }
+ return(FALSE);
+}
+
+/*
+ * BnMultiply
+ */
+___BnMultiply___(p, pd, pl, m, md, ml, n, nd, nl) BigNum p, m, n; int pd, pl, md, ml, nd, nl; {
+ int ret;
+
+ for (ret = 0; nl-- > 0; pd++, nd++, pl--)
+ ret += BnnMultiplyDigit ((p+ pd), pl, ( m+ md), ml, *( n+ nd));
+ return(ret);
+}
+
+TestBnMultiply(e) struct testenv *e; {
+ BigNumLength pd, pl, nd, nl, md, ml; int l1, l2;
+
+ e->depend = "(BnSetToZero, BnMultiplyDigit)";
+ ResetTest(1);
+ ResetTest(2);
+ for(pd = 0; pd <= TESTLENGTH; pd++)
+ for(pl = 0; pl <= TESTLENGTH - pd && pl <= TESTLENGTH/2; pl++)
+ for(nd = 0; nd <= TESTLENGTH - pl; nd++)
+ for(nl = 0; nl < pl && nl <= TESTLENGTH/3; nl++)
+ {
+ if (nl <= pl-nl)
+ {
+ /* Test squaring */
+ TestCountInc();
+ ResetTest(0);
+ l1 = BnnMultiply ((RN(0)+pd), pl, (RN(1)+nd), nl, (RN(1)+nd), nl);
+ l2 = ___BnMultiply___(SN(0),pd,pl,SN(1),nd,nl,SN(1),nd,nl);
+ if(Check(3) || l1 != l2) {
+ sprintf(e->hist,
+ "BnMultiply(p, %d, %d, n, %d, %d, n, %d, %d)",
+ pd, pl, nd, nl, nd, nl);
+ if(ShowDiff3(e,l1,l2,"p",pd,pl,"n",nd,nl,"n",nd,nl))
+ return(1);
+ }
+
+ }
+ for(md = 0; md <= TESTLENGTH; md++)
+ for (ml = 0; ml <= pl-nl && ml <= TESTLENGTH/3 && md+ml <= TESTLENGTH; ml++) {
+ TestCountInc();
+ ResetTest(0);
+ l1 = BnnMultiply ((RN(0)+pd), pl, (RN(1)+nd), nl, (RN(2)+md), ml);
+ l2 = ___BnMultiply___(SN(0),pd,pl,SN(1),nd,nl,SN(2),md,ml);
+ if(Check(3) || l1 != l2) {
+ sprintf(e->hist,
+ "BnMultiply(p, %d, %d, n, %d, %d, m, %d, %d)",
+ pd, pl, nd, nl, md, ml);
+ if(ShowDiff3(e,l1,l2,"p",pd,pl,"n",nd,nl,"m",md,ml))
+ return(1);
+ } } }
+ return(FALSE);
+}
+
+/*
+ * Main
+ */
+typedef struct {
+ int (*TestFnt)();
+ char *NameFnt;
+} TESTONE;
+TESTONE AllTest[] = {
+ Generique, "Generic Functions",
+ TestBnSetToZero, "BnSetToZero",
+ TestBnAssign, "BnAssign",
+ TestBnNumDigits, "BnNumDigits",
+ TestBnNumLeadingZeroBitsInDigit, "BnNumLeadingZeroBitsInDigit",
+ TestBnIsDigitZero, "BnIsDigitZero",
+ TestBnIsDigitNormalized, "BnIsDigitNormalized",
+ TestBnIsDigitOdd, "BnIsDigitOdd",
+ TestBnCompareDigits, "BnCompareDigits",
+ TestBnComplement, "BnComplement",
+ TestBnAndDigits, "BnAndDigits",
+ TestBnOrDigits, "BnOrDigits",
+ TestBnXorDigits, "BnXorDigits",
+ TestBnShiftLeft, "BnShiftLeft",
+ TestBnShiftRight, "BnShiftRight",
+ TestBnAddCarry, "BnAddCarry",
+ TestBnAdd, "BnAdd",
+ TestBnSubtractBorrow, "BnSubtractBorrow",
+ TestBnSubtract, "BnSubtract",
+ TestBnMultiplyDigit, "BnMultiplyDigit",
+ TestBnDivideDigit, "BnDivideDigit",
+ TestBnMultiply, "BnMultiply",
+};
+
+main(n, s) int n; char **s; {
+ struct testenv realenv, *e = &realenv;
+ int i, j, nbtest, SizeAllTest;
+
+ /* Initialisations de l'environnement de test. */
+ e->flag = 1;
+ e->depend = "()";
+ /* Allocation des 2 nombres globaux. */
+ Ntmp2 = BnAlloc(2);
+ NtmpBig = BnAlloc(2 * TESTLENGTH);
+ NumbProto = BnAlloc(TESTLENGTH);
+ /* Creation du nombre prototype. */
+ BnnSetDigit ((NumbProto+ 0), 0); /* Les 2 premiers a` ze'ro. */
+ BnnSetDigit ((NumbProto+ 1), 0);
+ for(i=0; i < TESTLENGTH/4 - 1; i++) /* Le premier quart est la */
+ BnnSetDigit ((NumbProto+ i + 2), i + 1); /* suite 1, 2, 3, ... */
+ /* Le 2nd quart est le 1er shifte de BN_DIGIT_SIZE - 2. 0x4000 0x8000 ...*/
+ BnnAssign ((NumbProto+ QTL + 1), ( NumbProto+ 2), QTL - 1);
+ *( NumbProto+ 0) = BnnShiftLeft ((NumbProto+ QTL + 1), QTL - 1, BN_DIGIT_SIZE - 2);
+ /* La 2nd moitie est l'inverse logique de la 1ere */
+ BnnAssign ((NumbProto+ DTL), ( NumbProto+ 0), DTL);
+ BnnComplement ((NumbProto+ DTL), DTL);
+ /* Allocation des nombres utilise's */
+ for(i=0; i < 5; i++) {
+ RN(i) = BnAlloc(TESTLENGTH);
+ SN(i) = BnAlloc(TESTLENGTH);
+ }
+ if(n > 1 && s[1][0] == '-') {
+ CallDummy = atoi(s[1]+1);
+ n--;
+ s++;
+ }
+ if(n == 1) {
+ printf("%s [-CallDummy#] v|a|TestNum\n", s[0]);
+ }
+ /* On y va */
+ SizeAllTest = (sizeof(AllTest)/sizeof(AllTest[0]));
+ for(i = 1; i < n; i++) {
+ if(s[i][0] == 'm') {
+ /* 0 = No skip; 1 = skip to next; else STOP */
+ e->flag = atoi(&s[i][1]);
+ } else if(s[i][0] == 'a') {
+ for(i = 0; i < SizeAllTest; i++)
+ dotest(e, i);
+ } else if(s[i][0] == 'v') {
+ for(j = 0; j < SizeAllTest; j++)
+ seetest(j);
+ } else {
+ nbtest = atoi(s[i]);
+ if((nbtest < 0) || (nbtest >= SizeAllTest))
+ printf("Test %d is invalid\n", nbtest);
+ else dotest(e, nbtest);
+} } }
+
+dotest(e, n) struct testenv *e; int n; {
+ seetest(n);
+ TestCount = 0;
+ e->name = AllTest[n].NameFnt;
+ if(((*(AllTest[n].TestFnt)) (e)) && e->flag > 1) exit(0);
+ printf("%d tests were performed\n", TestCount);
+}
+
+seetest(n) int n; {
+ printf("%d. Testing %s\n", n, AllTest[n].NameFnt);
+}
+
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-03-20 12:06:26 +0000