Ignore:
Timestamp:
Jan 9, 2017, 11:09:38 AM (2 years ago)
Author:
jrpelegrina
Message:

Update new version: 3.15.02

File:
1 edited

Legend:

Unmodified
Added
Removed
  • filezilla/trunk/fuentes/src/putty/sshbn.c

    r130 r3185  
    8888/*
    8989 * Internal addition. Sets c = a - b, where 'a', 'b' and 'c' are all
    90  * big-endian arrays of 'len' BignumInts. Returns a BignumInt carried
    91  * off the top.
    92  */
    93 static BignumInt internal_add(const BignumInt *a, const BignumInt *b,
    94                               BignumInt *c, int len)
     90 * big-endian arrays of 'len' BignumInts. Returns the carry off the
     91 * top.
     92 */
     93static BignumCarry internal_add(const BignumInt *a, const BignumInt *b,
     94                                BignumInt *c, int len)
    9595{
    9696    int i;
    97     BignumDblInt carry = 0;
    98 
    99     for (i = len-1; i >= 0; i--) {
    100         carry += (BignumDblInt)a[i] + b[i];
    101         c[i] = (BignumInt)carry;
    102         carry >>= BIGNUM_INT_BITS;
    103     }
     97    BignumCarry carry = 0;
     98
     99    for (i = len-1; i >= 0; i--)
     100        BignumADC(c[i], carry, a[i], b[i], carry);
    104101
    105102    return (BignumInt)carry;
     
    115112{
    116113    int i;
    117     BignumDblInt carry = 1;
    118 
    119     for (i = len-1; i >= 0; i--) {
    120         carry += (BignumDblInt)a[i] + (b[i] ^ BIGNUM_INT_MASK);
    121         c[i] = (BignumInt)carry;
    122         carry >>= BIGNUM_INT_BITS;
    123     }
     114    BignumCarry carry = 1;
     115
     116    for (i = len-1; i >= 0; i--)
     117        BignumADC(c[i], carry, a[i], ~b[i], carry);
    124118}
    125119
     
    185179        int toplen = len/2, botlen = len - toplen; /* botlen is the bigger */
    186180        int midlen = botlen + 1;
    187         BignumDblInt carry;
     181        BignumCarry carry;
    188182#ifdef KARA_DEBUG
    189183        int i;
     
    314308        while (carry) {
    315309            assert(i >= 0);
    316             carry += c[i];
    317             c[i] = (BignumInt)carry;
    318             carry >>= BIGNUM_INT_BITS;
     310            BignumADC(c[i], carry, c[i], 0, carry);
    319311            i--;
    320312        }
     
    330322        int i;
    331323        BignumInt carry;
    332         BignumDblInt t;
    333324        const BignumInt *ap, *bp;
    334325        BignumInt *cp, *cps;
     
    343334        for (cps = c + 2*len, ap = a + len; ap-- > a; cps--) {
    344335            carry = 0;
    345             for (cp = cps, bp = b + len; cp--, bp-- > b ;) {
    346                 t = (MUL_WORD(*ap, *bp) + carry) + *cp;
    347                 *cp = (BignumInt) t;
    348                 carry = (BignumInt)(t >> BIGNUM_INT_BITS);
    349             }
     336            for (cp = cps, bp = b + len; cp--, bp-- > b ;)
     337                BignumMULADD2(carry, *cp, *ap, *bp, *cp, carry);
    350338            *cp = carry;
    351339        }
     
    432420        int i;
    433421        BignumInt carry;
    434         BignumDblInt t;
    435422        const BignumInt *ap, *bp;
    436423        BignumInt *cp, *cps;
     
    445432        for (cps = c + len, ap = a + len; ap-- > a; cps--) {
    446433            carry = 0;
    447             for (cp = cps, bp = b + len; bp--, cp-- > c ;) {
    448                 t = (MUL_WORD(*ap, *bp) + carry) + *cp;
    449                 *cp = (BignumInt) t;
    450                 carry = (BignumInt)(t >> BIGNUM_INT_BITS);
    451             }
     434            for (cp = cps, bp = b + len; bp--, cp-- > c ;)
     435                BignumMULADD2(carry, *cp, *ap, *bp, *cp, carry);
    452436        }
    453437    }
     
    520504    int word = 1 + (shift / BIGNUM_INT_BITS);
    521505    int bshift = shift % BIGNUM_INT_BITS;
    522     BignumDblInt addend;
    523 
    524     addend = (BignumDblInt)n << bshift;
    525 
    526     while (addend) {
     506    BignumInt addendh, addendl;
     507    BignumCarry carry;
     508
     509    addendl = n << bshift;
     510    addendh = (bshift == 0 ? 0 : n >> (BIGNUM_INT_BITS - bshift));
     511
     512    assert(word <= number[0]);
     513    BignumADC(number[word], carry, number[word], addendl, 0);
     514    word++;
     515    if (!addendh && !carry)
     516        return;
     517    assert(word <= number[0]);
     518    BignumADC(number[word], carry, number[word], addendh, carry);
     519    word++;
     520    while (carry) {
    527521        assert(word <= number[0]);
    528         addend += number[word];
    529         number[word] = (BignumInt) addend & BIGNUM_INT_MASK;
    530         addend >>= BIGNUM_INT_BITS;
     522        BignumADC(number[word], carry, number[word], 0, carry);
    531523        word++;
    532524    }
     525}
     526
     527static int bn_clz(BignumInt x)
     528{
     529    /*
     530     * Count the leading zero bits in x. Equivalently, how far left
     531     * would we need to shift x to make its top bit set?
     532     *
     533     * Precondition: x != 0.
     534     */
     535
     536    /* FIXME: would be nice to put in some compiler intrinsics under
     537     * ifdef here */
     538    int i, ret = 0;
     539    for (i = BIGNUM_INT_BITS / 2; i != 0; i >>= 1) {
     540        if ((x >> (BIGNUM_INT_BITS-i)) == 0) {
     541            x <<= i;
     542            ret += i;
     543        }
     544    }
     545    return ret;
     546}
     547
     548static BignumInt reciprocal_word(BignumInt d)
     549{
     550    BignumInt dshort, recip, prodh, prodl;
     551    int corrections;
     552
     553    /*
     554     * Input: a BignumInt value d, with its top bit set.
     555     */
     556    assert(d >> (BIGNUM_INT_BITS-1) == 1);
     557
     558    /*
     559     * Output: a value, shifted to fill a BignumInt, which is strictly
     560     * less than 1/(d+1), i.e. is an *under*-estimate (but by as
     561     * little as possible within the constraints) of the reciprocal of
     562     * any number whose first BIGNUM_INT_BITS bits match d.
     563     *
     564     * Ideally we'd like to _totally_ fill BignumInt, i.e. always
     565     * return a value with the top bit set. Unfortunately we can't
     566     * quite guarantee that for all inputs and also return a fixed
     567     * exponent. So instead we take our reciprocal to be
     568     * 2^(BIGNUM_INT_BITS*2-1) / d, so that it has the top bit clear
     569     * only in the exceptional case where d takes exactly the maximum
     570     * value BIGNUM_INT_MASK; in that case, the top bit is clear and
     571     * the next bit down is set.
     572     */
     573
     574    /*
     575     * Start by computing a half-length version of the answer, by
     576     * straightforward division within a BignumInt.
     577     */
     578    dshort = (d >> (BIGNUM_INT_BITS/2)) + 1;
     579    recip = (BIGNUM_TOP_BIT + dshort - 1) / dshort;
     580    recip <<= BIGNUM_INT_BITS - BIGNUM_INT_BITS/2;
     581
     582    /*
     583     * Newton-Raphson iteration to improve that starting reciprocal
     584     * estimate: take f(x) = d - 1/x, and then the N-R formula gives
     585     * x_new = x - f(x)/f'(x) = x - (d-1/x)/(1/x^2) = x(2-d*x). Or,
     586     * taking our fixed-point representation into account, take f(x)
     587     * to be d - K/x (where K = 2^(BIGNUM_INT_BITS*2-1) as discussed
     588     * above) and then we get (2K - d*x) * x/K.
     589     *
     590     * Newton-Raphson doubles the number of correct bits at every
     591     * iteration, and the initial division above already gave us half
     592     * the output word, so it's only worth doing one iteration.
     593     */
     594    BignumMULADD(prodh, prodl, recip, d, recip);
     595    prodl = ~prodl;
     596    prodh = ~prodh;
     597    {
     598        BignumCarry c;
     599        BignumADC(prodl, c, prodl, 1, 0);
     600        prodh += c;
     601    }
     602    BignumMUL(prodh, prodl, prodh, recip);
     603    recip = (prodh << 1) | (prodl >> (BIGNUM_INT_BITS-1));
     604
     605    /*
     606     * Now make sure we have the best possible reciprocal estimate,
     607     * before we return it. We might have been off by a handful either
     608     * way - not enough to bother with any better-thought-out kind of
     609     * correction loop.
     610     */
     611    BignumMULADD(prodh, prodl, recip, d, recip);
     612    corrections = 0;
     613    if (prodh >= BIGNUM_TOP_BIT) {
     614        do {
     615            BignumCarry c = 1;
     616            BignumADC(prodl, c, prodl, ~d, c); prodh += BIGNUM_INT_MASK + c;
     617            recip--;
     618            corrections++;
     619        } while (prodh >= ((BignumInt)1 << (BIGNUM_INT_BITS-1)));
     620    } else {
     621        while (1) {
     622            BignumInt newprodh, newprodl;
     623            BignumCarry c = 0;
     624            BignumADC(newprodl, c, prodl, d, c); newprodh = prodh + c;
     625            if (newprodh >= BIGNUM_TOP_BIT)
     626                break;
     627            prodh = newprodh;
     628            prodl = newprodl;
     629            recip++;
     630            corrections++;
     631        }
     632    }
     633
     634    return recip;
    533635}
    534636
     
    538640 * Output in first alen words of a
    539641 * (of which first alen-mlen words will be zero).
    540  * The MSW of m MUST have its high bit set.
    541642 * Quotient is accumulated in the `quotient' array, which is a Bignum
    542  * rather than the internal bigendian format. Quotient parts are shifted
    543  * left by `qshift' before adding into quot.
     643 * rather than the internal bigendian format.
     644 *
     645 * 'recip' must be the result of calling reciprocal_word() on the top
     646 * BIGNUM_INT_BITS of the modulus (denoted m0 in comments below), with
     647 * the topmost set bit normalised to the MSB of the input to
     648 * reciprocal_word. 'rshift' is how far left the top nonzero word of
     649 * the modulus had to be shifted to set that top bit.
    544650 */
    545651static void internal_mod(BignumInt *a, int alen,
    546652                         BignumInt *m, int mlen,
    547                          BignumInt *quot, int qshift)
    548 {
    549     BignumInt m0, m1, h;
     653                         BignumInt *quot, BignumInt recip, int rshift)
     654{
    550655    int i, k;
    551656
    552     m0 = m[0];
    553     assert(m0 >> (BIGNUM_INT_BITS-1) == 1);
    554     if (mlen > 1)
    555         m1 = m[1];
    556     else
    557         m1 = 0;
    558 
    559     for (i = 0; i <= alen - mlen; i++) {
    560         BignumDblInt t;
    561         BignumInt q, r, c, ai1;
    562 
    563         if (i == 0) {
    564             h = 0;
    565         } else {
    566             h = a[i - 1];
    567             a[i - 1] = 0;
    568         }
    569 
    570         if (i == alen - 1)
    571             ai1 = 0;
    572         else
    573             ai1 = a[i + 1];
    574 
    575         /* Find q = h:a[i] / m0 */
    576         if (h >= m0) {
    577             /*
    578              * Special case.
    579              *
    580              * To illustrate it, suppose a BignumInt is 8 bits, and
    581              * we are dividing (say) A1:23:45:67 by A1:B2:C3. Then
    582              * our initial division will be 0xA123 / 0xA1, which
    583              * will give a quotient of 0x100 and a divide overflow.
    584              * However, the invariants in this division algorithm
    585              * are not violated, since the full number A1:23:... is
    586              * _less_ than the quotient prefix A1:B2:... and so the
    587              * following correction loop would have sorted it out.
    588              *
    589              * In this situation we set q to be the largest
    590              * quotient we _can_ stomach (0xFF, of course).
    591              */
    592             q = BIGNUM_INT_MASK;
    593         } else {
    594             /* Macro doesn't want an array subscript expression passed
    595              * into it (see definition), so use a temporary. */
    596             BignumInt tmplo = a[i];
    597             DIVMOD_WORD(q, r, h, tmplo, m0);
    598 
    599             /* Refine our estimate of q by looking at
    600              h:a[i]:a[i+1] / m0:m1 */
    601             t = MUL_WORD(m1, q);
    602             if (t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) {
    603                 q--;
    604                 t -= m1;
    605                 r = (r + m0) & BIGNUM_INT_MASK;     /* overflow? */
    606                 if (r >= (BignumDblInt) m0 &&
    607                     t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) q--;
    608             }
    609         }
    610 
    611         /* Subtract q * m from a[i...] */
    612         c = 0;
    613         for (k = mlen - 1; k >= 0; k--) {
    614             t = MUL_WORD(q, m[k]);
    615             t += c;
    616             c = (BignumInt)(t >> BIGNUM_INT_BITS);
    617             if ((BignumInt) t > a[i + k])
    618                 c++;
    619             a[i + k] -= (BignumInt) t;
    620         }
    621 
    622         /* Add back m in case of borrow */
    623         if (c != h) {
    624             t = 0;
    625             for (k = mlen - 1; k >= 0; k--) {
    626                 t += m[k];
    627                 t += a[i + k];
    628                 a[i + k] = (BignumInt) t;
    629                 t = t >> BIGNUM_INT_BITS;
    630             }
    631             q--;
    632         }
    633         if (quot)
    634             internal_add_shifted(quot, q, qshift + BIGNUM_INT_BITS * (alen - mlen - i));
    635     }
     657#ifdef DIVISION_DEBUG
     658    {
     659        int d;
     660        printf("start division, m=0x");
     661        for (d = 0; d < mlen; d++)
     662            printf("%0*llx", BIGNUM_INT_BITS/4, (unsigned long long)m[d]);
     663        printf(", recip=%#0*llx, rshift=%d\n",
     664               BIGNUM_INT_BITS/4, (unsigned long long)recip, rshift);
     665    }
     666#endif
     667
     668    /*
     669     * Repeatedly use that reciprocal estimate to get a decent number
     670     * of quotient bits, and subtract off the resulting multiple of m.
     671     *
     672     * Normally we expect to terminate this loop by means of finding
     673     * out q=0 part way through, but one way in which we might not get
     674     * that far in the first place is if the input a is actually zero,
     675     * in which case we'll discard zero words from the front of a
     676     * until we reach the termination condition in the for statement
     677     * here.
     678     */
     679    for (i = 0; i <= alen - mlen ;) {
     680        BignumInt product;
     681        BignumInt aword, q;
     682        int shift, full_bitoffset, bitoffset, wordoffset;
     683
     684#ifdef DIVISION_DEBUG
     685        {
     686            int d;
     687            printf("main loop, a=0x");
     688            for (d = 0; d < alen; d++)
     689                printf("%0*llx", BIGNUM_INT_BITS/4, (unsigned long long)a[d]);
     690            printf("\n");
     691        }
     692#endif
     693
     694        if (a[i] == 0) {
     695#ifdef DIVISION_DEBUG
     696            printf("zero word at i=%d\n", i);
     697#endif
     698            i++;
     699            continue;
     700        }
     701
     702        aword = a[i];
     703        shift = bn_clz(aword);
     704        aword <<= shift;
     705        if (shift > 0 && i+1 < alen)
     706            aword |= a[i+1] >> (BIGNUM_INT_BITS - shift);
     707
     708        {
     709            BignumInt unused;
     710            BignumMUL(q, unused, recip, aword);
     711            (void)unused;
     712        }
     713
     714#ifdef DIVISION_DEBUG
     715        printf("i=%d, aword=%#0*llx, shift=%d, q=%#0*llx\n",
     716               i, BIGNUM_INT_BITS/4, (unsigned long long)aword,
     717               shift, BIGNUM_INT_BITS/4, (unsigned long long)q);
     718#endif
     719
     720        /*
     721         * Work out the right bit and word offsets to use when
     722         * subtracting q*m from a.
     723         *
     724         * aword was taken from a[i], which means its LSB was at bit
     725         * position (alen-1-i) * BIGNUM_INT_BITS. But then we shifted
     726         * it left by 'shift', so now the low bit of aword corresponds
     727         * to bit position (alen-1-i) * BIGNUM_INT_BITS - shift, i.e.
     728         * aword is approximately equal to a / 2^(that).
     729         *
     730         * m0 comes from the top word of mod, so its LSB is at bit
     731         * position (mlen-1) * BIGNUM_INT_BITS - rshift, i.e. it can
     732         * be considered to be m / 2^(that power). 'recip' is the
     733         * reciprocal of m0, times 2^(BIGNUM_INT_BITS*2-1), i.e. it's
     734         * about 2^((mlen+1) * BIGNUM_INT_BITS - rshift - 1) / m.
     735         *
     736         * Hence, recip * aword is approximately equal to the product
     737         * of those, which simplifies to
     738         *
     739         * a/m * 2^((mlen+2+i-alen)*BIGNUM_INT_BITS + shift - rshift - 1)
     740         *
     741         * But we've also shifted recip*aword down by BIGNUM_INT_BITS
     742         * to form q, so we have
     743         *
     744         * q ~= a/m * 2^((mlen+1+i-alen)*BIGNUM_INT_BITS + shift - rshift - 1)
     745         *
     746         * and hence, when we now compute q*m, it will be about
     747         * a*2^(all that lot), i.e. the negation of that expression is
     748         * how far left we have to shift the product q*m to make it
     749         * approximately equal to a.
     750         */
     751        full_bitoffset = -((mlen+1+i-alen)*BIGNUM_INT_BITS + shift-rshift-1);
     752#ifdef DIVISION_DEBUG
     753        printf("full_bitoffset=%d\n", full_bitoffset);
     754#endif
     755
     756        if (full_bitoffset < 0) {
     757            /*
     758             * If we find ourselves needing to shift q*m _right_, that
     759             * means we've reached the bottom of the quotient. Clip q
     760             * so that its right shift becomes zero, and if that means
     761             * q becomes _actually_ zero, this loop is done.
     762             */
     763            if (full_bitoffset <= -BIGNUM_INT_BITS)
     764                break;
     765            q >>= -full_bitoffset;
     766            full_bitoffset = 0;
     767            if (!q)
     768                break;
     769#ifdef DIVISION_DEBUG
     770            printf("now full_bitoffset=%d, q=%#0*llx\n",
     771                   full_bitoffset, BIGNUM_INT_BITS/4, (unsigned long long)q);
     772#endif
     773        }
     774
     775        wordoffset = full_bitoffset / BIGNUM_INT_BITS;
     776        bitoffset = full_bitoffset % BIGNUM_INT_BITS;
     777#ifdef DIVISION_DEBUG
     778        printf("wordoffset=%d, bitoffset=%d\n", wordoffset, bitoffset);
     779#endif
     780
     781        /* wordoffset as computed above is the offset between the LSWs
     782         * of m and a. But in fact m and a are stored MSW-first, so we
     783         * need to adjust it to be the offset between the actual array
     784         * indices, and flip the sign too. */
     785        wordoffset = alen - mlen - wordoffset;
     786
     787        if (bitoffset == 0) {
     788            BignumCarry c = 1;
     789            BignumInt prev_hi_word = 0;
     790            for (k = mlen - 1; wordoffset+k >= i; k--) {
     791                BignumInt mword = k<0 ? 0 : m[k];
     792                BignumMULADD(prev_hi_word, product, q, mword, prev_hi_word);
     793#ifdef DIVISION_DEBUG
     794                printf("  aligned sub: product word for m[%d] = %#0*llx\n",
     795                       k, BIGNUM_INT_BITS/4,
     796                       (unsigned long long)product);
     797#endif
     798#ifdef DIVISION_DEBUG
     799                printf("  aligned sub: subtrahend for a[%d] = %#0*llx\n",
     800                       wordoffset+k, BIGNUM_INT_BITS/4,
     801                       (unsigned long long)product);
     802#endif
     803                BignumADC(a[wordoffset+k], c, a[wordoffset+k], ~product, c);
     804            }
     805        } else {
     806            BignumInt add_word = 0;
     807            BignumInt c = 1;
     808            BignumInt prev_hi_word = 0;
     809            for (k = mlen - 1; wordoffset+k >= i; k--) {
     810                BignumInt mword = k<0 ? 0 : m[k];
     811                BignumMULADD(prev_hi_word, product, q, mword, prev_hi_word);
     812#ifdef DIVISION_DEBUG
     813                printf("  unaligned sub: product word for m[%d] = %#0*llx\n",
     814                       k, BIGNUM_INT_BITS/4,
     815                       (unsigned long long)product);
     816#endif
     817
     818                add_word |= product << bitoffset;
     819
     820#ifdef DIVISION_DEBUG
     821                printf("  unaligned sub: subtrahend for a[%d] = %#0*llx\n",
     822                       wordoffset+k,
     823                       BIGNUM_INT_BITS/4, (unsigned long long)add_word);
     824#endif
     825                BignumADC(a[wordoffset+k], c, a[wordoffset+k], ~add_word, c);
     826
     827                add_word = product >> (BIGNUM_INT_BITS - bitoffset);
     828            }
     829        }
     830
     831        if (quot) {
     832#ifdef DIVISION_DEBUG
     833            printf("adding quotient word %#0*llx << %d\n",
     834                   BIGNUM_INT_BITS/4, (unsigned long long)q, full_bitoffset);
     835#endif
     836            internal_add_shifted(quot, q, full_bitoffset);
     837#ifdef DIVISION_DEBUG
     838            {
     839                int d;
     840                printf("now quot=0x");
     841                for (d = quot[0]; d > 0; d--)
     842                    printf("%0*llx", BIGNUM_INT_BITS/4,
     843                           (unsigned long long)quot[d]);
     844                printf("\n");
     845            }
     846#endif
     847        }
     848    }
     849
     850#ifdef DIVISION_DEBUG
     851    {
     852        int d;
     853        printf("end main loop, a=0x");
     854        for (d = 0; d < alen; d++)
     855            printf("%0*llx", BIGNUM_INT_BITS/4, (unsigned long long)a[d]);
     856        if (quot) {
     857            printf(", quot=0x");
     858            for (d = quot[0]; d > 0; d--)
     859                printf("%0*llx", BIGNUM_INT_BITS/4,
     860                       (unsigned long long)quot[d]);
     861        }
     862        printf("\n");
     863    }
     864#endif
     865
     866    /*
     867     * The above loop should terminate with the remaining value in a
     868     * being strictly less than 2*m (if a >= 2*m then we should always
     869     * have managed to get a nonzero q word), but we can't guarantee
     870     * that it will be strictly less than m: consider a case where the
     871     * remainder is 1, and another where the remainder is m-1. By the
     872     * time a contains a value that's _about m_, you clearly can't
     873     * distinguish those cases by looking at only the top word of a -
     874     * you have to go all the way down to the bottom before you find
     875     * out whether it's just less or just more than m.
     876     *
     877     * Hence, we now do a final fixup in which we subtract one last
     878     * copy of m, or don't, accordingly. We should never have to
     879     * subtract more than one copy of m here.
     880     */
     881    for (i = 0; i < alen; i++) {
     882        /* Compare a with m, word by word, from the MSW down. As soon
     883         * as we encounter a difference, we know whether we need the
     884         * fixup. */
     885        int mindex = mlen-alen+i;
     886        BignumInt mword = mindex < 0 ? 0 : m[mindex];
     887        if (a[i] < mword) {
     888#ifdef DIVISION_DEBUG
     889            printf("final fixup not needed, a < m\n");
     890#endif
     891            return;
     892        } else if (a[i] > mword) {
     893#ifdef DIVISION_DEBUG
     894            printf("final fixup is needed, a > m\n");
     895#endif
     896            break;
     897        }
     898        /* If neither of those cases happened, the words are the same,
     899         * so keep going and look at the next one. */
     900    }
     901#ifdef DIVISION_DEBUG
     902    if (i == mlen) /* if we printed neither of the above diagnostics */
     903        printf("final fixup is needed, a == m\n");
     904#endif
     905
     906    /*
     907     * If we got here without returning, then a >= m, so we must
     908     * subtract m, and increment the quotient.
     909     */
     910    {
     911        BignumCarry c = 1;
     912        for (i = alen - 1; i >= 0; i--) {
     913            int mindex = mlen-alen+i;
     914            BignumInt mword = mindex < 0 ? 0 : m[mindex];
     915            BignumADC(a[i], c, a[i], ~mword, c);
     916        }
     917    }
     918    if (quot)
     919        internal_add_shifted(quot, 1, 0);
     920
     921#ifdef DIVISION_DEBUG
     922    {
     923        int d;
     924        printf("after final fixup, a=0x");
     925        for (d = 0; d < alen; d++)
     926            printf("%0*llx", BIGNUM_INT_BITS/4, (unsigned long long)a[d]);
     927        if (quot) {
     928            printf(", quot=0x");
     929            for (d = quot[0]; d > 0; d--)
     930                printf("%0*llx", BIGNUM_INT_BITS/4,
     931                       (unsigned long long)quot[d]);
     932        }
     933        printf("\n");
     934    }
     935#endif
    636936}
    637937
     
    642942{
    643943    BignumInt *a, *b, *n, *m, *scratch;
    644     int mshift;
     944    BignumInt recip;
     945    int rshift;
    645946    int mlen, scratchlen, i, j;
    646947    Bignum base, result;
     
    664965    for (j = 0; j < mlen; j++)
    665966        m[j] = mod[mod[0] - j];
    666 
    667     /* Shift m left to make msb bit set */
    668     for (mshift = 0; mshift < BIGNUM_INT_BITS-1; mshift++)
    669         if ((m[0] << mshift) & BIGNUM_TOP_BIT)
    670             break;
    671     if (mshift) {
    672         for (i = 0; i < mlen - 1; i++)
    673             m[i] = (m[i] << mshift) | (m[i + 1] >> (BIGNUM_INT_BITS - mshift));
    674         m[mlen - 1] = m[mlen - 1] << mshift;
    675     }
    676967
    677968    /* Allocate n of size mlen, copy base to n */
     
    705996    }
    706997
     998    /* Compute reciprocal of the top full word of the modulus */
     999    {
     1000        BignumInt m0 = m[0];
     1001        rshift = bn_clz(m0);
     1002        if (rshift) {
     1003            m0 <<= rshift;
     1004            if (mlen > 1)
     1005                m0 |= m[1] >> (BIGNUM_INT_BITS - rshift);
     1006        }
     1007        recip = reciprocal_word(m0);
     1008    }
     1009
    7071010    /* Main computation */
    7081011    while (i < (int)exp[0]) {
    7091012        while (j >= 0) {
    7101013            internal_mul(a + mlen, a + mlen, b, mlen, scratch);
    711             internal_mod(b, mlen * 2, m, mlen, NULL, 0);
     1014            internal_mod(b, mlen * 2, m, mlen, NULL, recip, rshift);
    7121015            if ((exp[exp[0] - i] & ((BignumInt)1 << j)) != 0) {
    7131016                internal_mul(b + mlen, n, a, mlen, scratch);
    714                 internal_mod(a, mlen * 2, m, mlen, NULL, 0);
     1017                internal_mod(a, mlen * 2, m, mlen, NULL, recip, rshift);
    7151018            } else {
    7161019                BignumInt *t;
     
    7231026        i++;
    7241027        j = BIGNUM_INT_BITS-1;
    725     }
    726 
    727     /* Fixup result in case the modulus was shifted */
    728     if (mshift) {
    729         for (i = mlen - 1; i < 2 * mlen - 1; i++)
    730             a[i] = (a[i] << mshift) | (a[i + 1] >> (BIGNUM_INT_BITS - mshift));
    731         a[2 * mlen - 1] = a[2 * mlen - 1] << mshift;
    732         internal_mod(a, mlen * 2, m, mlen, NULL, 0);
    733         for (i = 2 * mlen - 1; i >= mlen; i--)
    734             a[i] = (a[i] >> mshift) | (a[i - 1] << (BIGNUM_INT_BITS - mshift));
    7351028    }
    7361029
     
    9131206{
    9141207    BignumInt *a, *n, *m, *o, *scratch;
    915     int mshift, scratchlen;
     1208    BignumInt recip;
     1209    int rshift, scratchlen;
    9161210    int pqlen, mlen, rlen, i, j;
    9171211    Bignum result;
     
    9291223    for (j = 0; j < mlen; j++)
    9301224        m[j] = mod[mod[0] - j];
    931 
    932     /* Shift m left to make msb bit set */
    933     for (mshift = 0; mshift < BIGNUM_INT_BITS-1; mshift++)
    934         if ((m[0] << mshift) & BIGNUM_TOP_BIT)
    935             break;
    936     if (mshift) {
    937         for (i = 0; i < mlen - 1; i++)
    938             m[i] = (m[i] << mshift) | (m[i + 1] >> (BIGNUM_INT_BITS - mshift));
    939         m[mlen - 1] = m[mlen - 1] << mshift;
    940     }
    9411225
    9421226    pqlen = (p[0] > q[0] ? p[0] : q[0]);
     
    9721256    scratch = snewn(scratchlen, BignumInt);
    9731257
     1258    /* Compute reciprocal of the top full word of the modulus */
     1259    {
     1260        BignumInt m0 = m[0];
     1261        rshift = bn_clz(m0);
     1262        if (rshift) {
     1263            m0 <<= rshift;
     1264            if (mlen > 1)
     1265                m0 |= m[1] >> (BIGNUM_INT_BITS - rshift);
     1266        }
     1267        recip = reciprocal_word(m0);
     1268    }
     1269
    9741270    /* Main computation */
    9751271    internal_mul(n, o, a, pqlen, scratch);
    976     internal_mod(a, pqlen * 2, m, mlen, NULL, 0);
    977 
    978     /* Fixup result in case the modulus was shifted */
    979     if (mshift) {
    980         for (i = 2 * pqlen - mlen - 1; i < 2 * pqlen - 1; i++)
    981             a[i] = (a[i] << mshift) | (a[i + 1] >> (BIGNUM_INT_BITS - mshift));
    982         a[2 * pqlen - 1] = a[2 * pqlen - 1] << mshift;
    983         internal_mod(a, pqlen * 2, m, mlen, NULL, 0);
    984         for (i = 2 * pqlen - 1; i >= 2 * pqlen - mlen; i--)
    985             a[i] = (a[i] >> mshift) | (a[i - 1] << (BIGNUM_INT_BITS - mshift));
    986     }
     1272    internal_mod(a, pqlen * 2, m, mlen, NULL, recip, rshift);
    9871273
    9881274    /* Copy result to buffer */
     
    10481334{
    10491335    BignumInt *n, *m;
    1050     int mshift;
     1336    BignumInt recip;
     1337    int rshift;
    10511338    int plen, mlen, i, j;
    10521339
     
    10641351        m[j] = mod[mod[0] - j];
    10651352
    1066     /* Shift m left to make msb bit set */
    1067     for (mshift = 0; mshift < BIGNUM_INT_BITS-1; mshift++)
    1068         if ((m[0] << mshift) & BIGNUM_TOP_BIT)
    1069             break;
    1070     if (mshift) {
    1071         for (i = 0; i < mlen - 1; i++)
    1072             m[i] = (m[i] << mshift) | (m[i + 1] >> (BIGNUM_INT_BITS - mshift));
    1073         m[mlen - 1] = m[mlen - 1] << mshift;
    1074     }
    1075 
    10761353    plen = p[0];
    10771354    /* Ensure plen > mlen */
     
    10861363        n[plen - j] = p[j];
    10871364
     1365    /* Compute reciprocal of the top full word of the modulus */
     1366    {
     1367        BignumInt m0 = m[0];
     1368        rshift = bn_clz(m0);
     1369        if (rshift) {
     1370            m0 <<= rshift;
     1371            if (mlen > 1)
     1372                m0 |= m[1] >> (BIGNUM_INT_BITS - rshift);
     1373        }
     1374        recip = reciprocal_word(m0);
     1375    }
     1376
    10881377    /* Main computation */
    1089     internal_mod(n, plen, m, mlen, quotient, mshift);
    1090 
    1091     /* Fixup result in case the modulus was shifted */
    1092     if (mshift) {
    1093         for (i = plen - mlen - 1; i < plen - 1; i++)
    1094             n[i] = (n[i] << mshift) | (n[i + 1] >> (BIGNUM_INT_BITS - mshift));
    1095         n[plen - 1] = n[plen - 1] << mshift;
    1096         internal_mod(n, plen, m, mlen, quotient, 0);
    1097         for (i = plen - 1; i >= plen - mlen; i--)
    1098             n[i] = (n[i] >> mshift) | (n[i - 1] << (BIGNUM_INT_BITS - mshift));
    1099     }
     1378    internal_mod(n, plen, m, mlen, quotient, recip, rshift);
    11001379
    11011380    /* Copy result to buffer */
     
    11431422    }
    11441423
    1145     while (result[0] > 1 && result[result[0]] == 0)
    1146         result[0]--;
     1424    bn_restore_invariant(result);
    11471425    return result;
    11481426}
     
    11661444    }
    11671445
    1168     while (result[0] > 1 && result[result[0]] == 0)
    1169         result[0]--;
     1446    bn_restore_invariant(result);
    11701447    return result;
    11711448}
     
    13121589void bignum_set_bit(Bignum bn, int bitnum, int value)
    13131590{
    1314     if (bitnum < 0 || bitnum >= (int)(BIGNUM_INT_BITS * bn[0]))
    1315         abort();                       /* beyond the end */
    1316     else {
     1591    if (bitnum < 0 || bitnum >= (int)(BIGNUM_INT_BITS * bn[0])) {
     1592        if (value) abort();                    /* beyond the end */
     1593    } else {
    13171594        int v = bitnum / BIGNUM_INT_BITS + 1;
    13181595        BignumInt mask = (BignumInt)1 << (bitnum % BIGNUM_INT_BITS);
     
    14791756    /* now add in the addend, if any */
    14801757    if (addend) {
    1481         BignumDblInt carry = 0;
     1758        BignumCarry carry = 0;
    14821759        for (i = 1; i <= rlen; i++) {
    1483             carry += (i <= (int)ret[0] ? ret[i] : 0);
    1484             carry += (i <= (int)addend[0] ? addend[i] : 0);
    1485             ret[i] = (BignumInt) carry & BIGNUM_INT_MASK;
    1486             carry >>= BIGNUM_INT_BITS;
     1760            BignumInt retword = (i <= (int)ret[0] ? ret[i] : 0);
     1761            BignumInt addword = (i <= (int)addend[0] ? addend[i] : 0);
     1762            BignumADC(ret[i], carry, retword, addword, carry);
    14871763            if (ret[i] != 0 && i > maxspot)
    14881764                maxspot = i;
     
    15131789    int i, maxspot;
    15141790    Bignum ret;
    1515     BignumDblInt carry;
     1791    BignumCarry carry;
    15161792
    15171793    ret = newbn(rlen);
     
    15201796    maxspot = 0;
    15211797    for (i = 1; i <= rlen; i++) {
    1522         carry += (i <= (int)a[0] ? a[i] : 0);
    1523         carry += (i <= (int)b[0] ? b[i] : 0);
    1524         ret[i] = (BignumInt) carry & BIGNUM_INT_MASK;
    1525         carry >>= BIGNUM_INT_BITS;
     1798        BignumInt aword = (i <= (int)a[0] ? a[i] : 0);
     1799        BignumInt bword = (i <= (int)b[0] ? b[i] : 0);
     1800        BignumADC(ret[i], carry, aword, bword, carry);
    15261801        if (ret[i] != 0 && i > maxspot)
    15271802            maxspot = i;
     
    15431818    int i, maxspot;
    15441819    Bignum ret;
    1545     BignumDblInt carry;
     1820    BignumCarry carry;
    15461821
    15471822    ret = newbn(rlen);
     
    15501825    maxspot = 0;
    15511826    for (i = 1; i <= rlen; i++) {
    1552         carry += (i <= (int)a[0] ? a[i] : 0);
    1553         carry += (i <= (int)b[0] ? b[i] ^ BIGNUM_INT_MASK : BIGNUM_INT_MASK);
    1554         ret[i] = (BignumInt) carry & BIGNUM_INT_MASK;
    1555         carry >>= BIGNUM_INT_BITS;
     1827        BignumInt aword = (i <= (int)a[0] ? a[i] : 0);
     1828        BignumInt bword = (i <= (int)b[0] ? b[i] : 0);
     1829        BignumADC(ret[i], carry, aword, ~bword, carry);
    15561830        if (ret[i] != 0 && i > maxspot)
    15571831            maxspot = i;
     
    15931867
    15941868/*
    1595  * Convert a (max 32-bit) long into a bignum.
    1596  */
    1597 Bignum bignum_from_long(unsigned long nn)
    1598 {
     1869 * Convert an unsigned long into a bignum.
     1870 */
     1871Bignum bignum_from_long(unsigned long n)
     1872{
     1873    const int maxwords =
     1874        (sizeof(unsigned long) + sizeof(BignumInt) - 1) / sizeof(BignumInt);
    15991875    Bignum ret;
    1600     BignumDblInt n = nn;
    1601 
    1602     ret = newbn(3);
    1603     ret[1] = (BignumInt)(n & BIGNUM_INT_MASK);
    1604     ret[2] = (BignumInt)((n >> BIGNUM_INT_BITS) & BIGNUM_INT_MASK);
    1605     ret[3] = 0;
    1606     ret[0] = (ret[2]  ? 2 : 1);
     1876    int i;
     1877
     1878    ret = newbn(maxwords);
     1879    ret[0] = 0;
     1880    for (i = 0; i < maxwords; i++) {
     1881        ret[i+1] = n >> (i * BIGNUM_INT_BITS);
     1882        if (ret[i+1] != 0)
     1883            ret[0] = i+1;
     1884    }
     1885
    16071886    return ret;
    16081887}
     
    16111890 * Add a long to a bignum.
    16121891 */
    1613 Bignum bignum_add_long(Bignum number, unsigned long addendx)
    1614 {
    1615     Bignum ret = newbn(number[0] + 1);
    1616     int i, maxspot = 0;
    1617     BignumDblInt carry = 0, addend = addendx;
    1618 
    1619     for (i = 1; i <= (int)ret[0]; i++) {
    1620         carry += addend & BIGNUM_INT_MASK;
    1621         carry += (i <= (int)number[0] ? number[i] : 0);
    1622         addend >>= BIGNUM_INT_BITS;
    1623         ret[i] = (BignumInt) carry & BIGNUM_INT_MASK;
    1624         carry >>= BIGNUM_INT_BITS;
    1625         if (ret[i] != 0)
    1626             maxspot = i;
    1627     }
    1628     ret[0] = maxspot;
     1892Bignum bignum_add_long(Bignum number, unsigned long n)
     1893{
     1894    const int maxwords =
     1895        (sizeof(unsigned long) + sizeof(BignumInt) - 1) / sizeof(BignumInt);
     1896    Bignum ret;
     1897    int words, i;
     1898    BignumCarry carry;
     1899
     1900    words = number[0];
     1901    if (words < maxwords)
     1902        words = maxwords;
     1903    words++;
     1904    ret = newbn(words);
     1905
     1906    carry = 0;
     1907    ret[0] = 0;
     1908    for (i = 0; i < words; i++) {
     1909        BignumInt nword = (i < maxwords ? n >> (i * BIGNUM_INT_BITS) : 0);
     1910        BignumInt numword = (i < number[0] ? number[i+1] : 0);
     1911        BignumADC(ret[i+1], carry, numword, nword, carry);
     1912        if (ret[i+1] != 0)
     1913            ret[0] = i+1;
     1914    }
    16291915    return ret;
    16301916}
     
    16351921unsigned short bignum_mod_short(Bignum number, unsigned short modulus)
    16361922{
    1637     BignumDblInt mod, r;
     1923    unsigned long mod = modulus, r = 0;
     1924    /* Precompute (BIGNUM_INT_MASK+1) % mod */
     1925    unsigned long base_r = (BIGNUM_INT_MASK - modulus + 1) % mod;
    16381926    int i;
    16391927
    1640     r = 0;
    1641     mod = modulus;
    1642     for (i = number[0]; i > 0; i--)
    1643         r = (r * (BIGNUM_TOP_BIT % mod) * 2 + number[i] % mod) % mod;
     1928    for (i = number[0]; i > 0; i--) {
     1929        /*
     1930         * Conceptually, ((r << BIGNUM_INT_BITS) + number[i]) % mod
     1931         */
     1932        r = ((r * base_r) + (number[i] % mod)) % mod;
     1933    }
    16441934    return (unsigned short) r;
    16451935}
     
    17992089    int ndigits, ndigit;
    18002090    int i, iszero;
    1801     BignumDblInt carry;
     2091    BignumInt carry;
    18022092    char *ret;
    18032093    BignumInt *workspace;
     
    18462136        carry = 0;
    18472137        for (i = 0; i < (int)x[0]; i++) {
    1848             carry = (carry << BIGNUM_INT_BITS) + workspace[i];
    1849             workspace[i] = (BignumInt) (carry / 10);
     2138            /*
     2139             * Conceptually, we want to compute
     2140             *
     2141             *   (carry << BIGNUM_INT_BITS) + workspace[i]
     2142             *   -----------------------------------------
     2143             *                      10
     2144             *
     2145             * but we don't have an integer type longer than BignumInt
     2146             * to work with. So we have to do it in pieces.
     2147             */
     2148
     2149            BignumInt q, r;
     2150            q = workspace[i] / 10;
     2151            r = workspace[i] % 10;
     2152
     2153            /* I want (BIGNUM_INT_MASK+1)/10 but can't say so directly! */
     2154            q += carry * ((BIGNUM_INT_MASK-9) / 10 + 1);
     2155            r += carry * ((BIGNUM_INT_MASK-9) % 10);
     2156
     2157            q += r / 10;
     2158            r %= 10;
     2159
     2160            workspace[i] = q;
     2161            carry = r;
     2162
    18502163            if (workspace[i])
    18512164                iszero = 0;
    1852             carry %= 10;
    18532165        }
    18542166        ret[--ndigit] = (char) (carry + '0');
     
    18692181    return ret;
    18702182}
    1871 
    1872 #ifdef TESTBN
    1873 
    1874 #include <stdio.h>
    1875 #include <stdlib.h>
    1876 #include <ctype.h>
    1877 
    1878 /*
    1879  * gcc -Wall -g -O0 -DTESTBN -o testbn sshbn.c misc.c conf.c tree234.c unix/uxmisc.c -I. -I unix -I charset
    1880  *
    1881  * Then feed to this program's standard input the output of
    1882  * testdata/bignum.py .
    1883  */
    1884 
    1885 void modalfatalbox(const char *p, ...)
    1886 {
    1887     va_list ap;
    1888     fprintf(stderr, "FATAL ERROR: ");
    1889     va_start(ap, p);
    1890     vfprintf(stderr, p, ap);
    1891     va_end(ap);
    1892     fputc('\n', stderr);
    1893     exit(1);
    1894 }
    1895 
    1896 int random_byte(void)
    1897 {
    1898     modalfatalbox("random_byte called in testbn");
    1899     return 0;
    1900 }
    1901 
    1902 #define fromxdigit(c) ( (c)>'9' ? ((c)&0xDF) - 'A' + 10 : (c) - '0' )
    1903 
    1904 int main(int argc, char **argv)
    1905 {
    1906     char *buf;
    1907     int line = 0;
    1908     int passes = 0, fails = 0;
    1909 
    1910     while ((buf = fgetline(stdin)) != NULL) {
    1911         int maxlen = strlen(buf);
    1912         unsigned char *data = snewn(maxlen, unsigned char);
    1913         unsigned char *ptrs[5], *q;
    1914         int ptrnum;
    1915         char *bufp = buf;
    1916 
    1917         line++;
    1918 
    1919         q = data;
    1920         ptrnum = 0;
    1921 
    1922         while (*bufp && !isspace((unsigned char)*bufp))
    1923             bufp++;
    1924         if (bufp)
    1925             *bufp++ = '\0';
    1926 
    1927         while (*bufp) {
    1928             char *start, *end;
    1929             int i;
    1930 
    1931             while (*bufp && !isxdigit((unsigned char)*bufp))
    1932                 bufp++;
    1933             start = bufp;
    1934 
    1935             if (!*bufp)
    1936                 break;
    1937 
    1938             while (*bufp && isxdigit((unsigned char)*bufp))
    1939                 bufp++;
    1940             end = bufp;
    1941 
    1942             if (ptrnum >= lenof(ptrs))
    1943                 break;
    1944             ptrs[ptrnum++] = q;
    1945            
    1946             for (i = -((end - start) & 1); i < end-start; i += 2) {
    1947                 unsigned char val = (i < 0 ? 0 : fromxdigit(start[i]));
    1948                 val = val * 16 + fromxdigit(start[i+1]);
    1949                 *q++ = val;
    1950             }
    1951 
    1952             ptrs[ptrnum] = q;
    1953         }
    1954 
    1955         if (!strcmp(buf, "mul")) {
    1956             Bignum a, b, c, p;
    1957 
    1958             if (ptrnum != 3) {
    1959                 printf("%d: mul with %d parameters, expected 3\n", line, ptrnum);
    1960                 exit(1);
    1961             }
    1962             a = bignum_from_bytes(ptrs[0], ptrs[1]-ptrs[0]);
    1963             b = bignum_from_bytes(ptrs[1], ptrs[2]-ptrs[1]);
    1964             c = bignum_from_bytes(ptrs[2], ptrs[3]-ptrs[2]);
    1965             p = bigmul(a, b);
    1966 
    1967             if (bignum_cmp(c, p) == 0) {
    1968                 passes++;
    1969             } else {
    1970                 char *as = bignum_decimal(a);
    1971                 char *bs = bignum_decimal(b);
    1972                 char *cs = bignum_decimal(c);
    1973                 char *ps = bignum_decimal(p);
    1974                
    1975                 printf("%d: fail: %s * %s gave %s expected %s\n",
    1976                        line, as, bs, ps, cs);
    1977                 fails++;
    1978 
    1979                 sfree(as);
    1980                 sfree(bs);
    1981                 sfree(cs);
    1982                 sfree(ps);
    1983             }
    1984             freebn(a);
    1985             freebn(b);
    1986             freebn(c);
    1987             freebn(p);
    1988         } else if (!strcmp(buf, "modmul")) {
    1989             Bignum a, b, m, c, p;
    1990 
    1991             if (ptrnum != 4) {
    1992                 printf("%d: modmul with %d parameters, expected 4\n",
    1993                        line, ptrnum);
    1994                 exit(1);
    1995             }
    1996             a = bignum_from_bytes(ptrs[0], ptrs[1]-ptrs[0]);
    1997             b = bignum_from_bytes(ptrs[1], ptrs[2]-ptrs[1]);
    1998             m = bignum_from_bytes(ptrs[2], ptrs[3]-ptrs[2]);
    1999             c = bignum_from_bytes(ptrs[3], ptrs[4]-ptrs[3]);
    2000             p = modmul(a, b, m);
    2001 
    2002             if (bignum_cmp(c, p) == 0) {
    2003                 passes++;
    2004             } else {
    2005                 char *as = bignum_decimal(a);
    2006                 char *bs = bignum_decimal(b);
    2007                 char *ms = bignum_decimal(m);
    2008                 char *cs = bignum_decimal(c);
    2009                 char *ps = bignum_decimal(p);
    2010                
    2011                 printf("%d: fail: %s * %s mod %s gave %s expected %s\n",
    2012                        line, as, bs, ms, ps, cs);
    2013                 fails++;
    2014 
    2015                 sfree(as);
    2016                 sfree(bs);
    2017                 sfree(ms);
    2018                 sfree(cs);
    2019                 sfree(ps);
    2020             }
    2021             freebn(a);
    2022             freebn(b);
    2023             freebn(m);
    2024             freebn(c);
    2025             freebn(p);
    2026         } else if (!strcmp(buf, "pow")) {
    2027             Bignum base, expt, modulus, expected, answer;
    2028 
    2029             if (ptrnum != 4) {
    2030                 printf("%d: mul with %d parameters, expected 4\n", line, ptrnum);
    2031                 exit(1);
    2032             }
    2033 
    2034             base = bignum_from_bytes(ptrs[0], ptrs[1]-ptrs[0]);
    2035             expt = bignum_from_bytes(ptrs[1], ptrs[2]-ptrs[1]);
    2036             modulus = bignum_from_bytes(ptrs[2], ptrs[3]-ptrs[2]);
    2037             expected = bignum_from_bytes(ptrs[3], ptrs[4]-ptrs[3]);
    2038             answer = modpow(base, expt, modulus);
    2039 
    2040             if (bignum_cmp(expected, answer) == 0) {
    2041                 passes++;
    2042             } else {
    2043                 char *as = bignum_decimal(base);
    2044                 char *bs = bignum_decimal(expt);
    2045                 char *cs = bignum_decimal(modulus);
    2046                 char *ds = bignum_decimal(answer);
    2047                 char *ps = bignum_decimal(expected);
    2048                
    2049                 printf("%d: fail: %s ^ %s mod %s gave %s expected %s\n",
    2050                        line, as, bs, cs, ds, ps);
    2051                 fails++;
    2052 
    2053                 sfree(as);
    2054                 sfree(bs);
    2055                 sfree(cs);
    2056                 sfree(ds);
    2057                 sfree(ps);
    2058             }
    2059             freebn(base);
    2060             freebn(expt);
    2061             freebn(modulus);
    2062             freebn(expected);
    2063             freebn(answer);
    2064         } else {
    2065             printf("%d: unrecognised test keyword: '%s'\n", line, buf);
    2066             exit(1);
    2067         }
    2068 
    2069         sfree(buf);
    2070         sfree(data);
    2071     }
    2072 
    2073     printf("passed %d failed %d total %d\n", passes, fails, passes+fails);
    2074     return fails != 0;
    2075 }
    2076 
    2077 #endif
Note: See TracChangeset for help on using the changeset viewer.