My hobbyist coding updates and releases as the mysterious "Mr. Tines"

Sunday, 9 December 2007

What's wrong with this code?

Spent today getting about 2/3 coverage on the Bignums class, including rewriting the modularInverse function to complete in a finite time, based on the recursive method given in Wikipedia -- I can always redo it as iterative if there are problems, but for now I have achieved RSA.

So everything was running fine in the JVM; go to .Net, and … infinite loop trying to divide 40! by 20! (in a bit taken from the Ruby bignum unit tests. Eventually, I tracked it down to this:

    private static void s_m_mult_sub(
        int[] result, int ro,
        int[] multi, int mo,
        int scalar, int length)
    {
        long borrow = 0;
        int index = 0;

        /* Is basically practical => proceed */
        while(index < length)
        {
            long product = multUnitxUnit(scalar, multi[mo+index]) + borrow;
            borrow = product >>> 32;
            product &= MASK;
            if(product > (result[ro+index]&MASK))
                ++borrow;
            result[ro+index++] -= (int)product;
        }
        result[ro+index] -= (int)(borrow&MASK);
    }

which Java -- and the original 'C' from which this was taken -- runs "as you'd expect" but J# handles as if it were

result[ro+index++] = result[ro+index++] - (int)product;
and increments index twice, as well as splattering other mayhem around the structure.

Next up, getting JZlib tidied and turning its tests into JUnit form, and adding the PGP needed twiddles; then a first release to replace my old crypt.zip.

The original 'C' code:

static void s_m_mult_sub(unit result[], unit multi[], unit scalar, unit length)
{
    register unit high, low1, low2;
    unit borrow = 0;
    unit index = 0;

    /* Is basically practical => proceed */
    while(index < length)
    {
        multUnitxUnit(high, low1, scalar, multi[(size_t)index]);
        low2 = low1 + borrow;
        if(low2 < low1) high++;
        if(low2 > result[(size_t)index])
            borrow = high + 1;
        else
            borrow = high;
        result[(size_t)(index++)] -= low2;
    }
    assert(result[(size_t)index] >= borrow);
    result[(size_t)index] -= borrow;
}

No comments: