bug in bignumdiv?

[tiofw]

Hi, I've been doing my own implementation, largely based on your code, thanks! 👍

Take a look at this bit from bignumdiv:

while (bignum_cmp(&denom, a) != LARGER) // while (denom <= a) { { _lshift_one_bit(&current); // current <<= 1; _lshift_one_bit(&denom); // denom <<= 1; }

What happens when denom <= a, and denom's most significant bit is 1? The left shift fails.

My code (big numbers using 32bit arrays) looks something like this:

uint32_t const half_max = 1 + (uint32_t)INT32_MAX; bool overflow = false; // while (_bignum_cmp(denom, a) != LARGER) // while (denom <= a) { { if ( denom[array_size-1] >= half_max ) { overflow = true; break; } _lshift_one_bit(current); // current <<= 1; _lshift_one_bit(denom); // denom <<= 1; } if ( ! overflow ) { _rshift_one_bit(denom); // denom >>= 1; _rshift_one_bit(current); // current >>= 1; }

[kokke]

Hi @tiofw and thanks for your feedback :)

Have you encountered a case where the output from my code does not match the expected output?

In other words: Can you provide a test case (input + expected output + actual output) that demonstrates the bug?

That would make it a bit easier for me to understand the issue you are raising :)

[tiofw]

Hi @kokke,

I'm running my own code, I don't have an example for you using yours. But, for instance, if you take the max value of a your big number, and try to divide it by something else, you should hit the bug. For a small number example, imagine you are limited to two bits, then calculate 3 / 2 3 is 11 in binary 2 is 10 in binary 3>2, so increment current & lshift 2 when you lshift 2, you get 00 -> error 3>0 always, recursive loop

Hope that makes sense!

[kokke]

Then I don't think the issue applies to this code base. The case you mention is already covered in the test suite - see the cases at lines 61-64.

I would suspect the test suite to have caught such a case, which is why I asked for a specific example :)

[tiofw]

Only if 0xFFFFFFFF is really the highest number supported by your class. :-)

[kokke]

The cases I refer to, divide the highest number representable by a word/digit - not the highest number the library can represent.

So the issue would be triggered by dividing the highest number representable?

[tiofw]

Yes, exactly. :-)

[kokke]

Ah, thanks for bearing with me until the end :D now I finally understand.

Thanks for notifying me about this issue! I will try to add a test case that triggers the bug and then see if I can apply your fix.

[tiofw]

You're welcome. :) Sorry if I wasn't being very clear.

I ran into the issue because I was testing with bignum as a 64-bit number, so I could test using uint64_t, i.e.

typedef union { uint32_t array[2]; uint64_t big; } uint64_p;

Then I used random numbers to test, e.g.

for ( uint32_t j = 0; j < 100; ++j ) { uint64_p a, b, c; a.big = arc4random_uniform ( UINT64_MAX ); b.big = arc4random_uniform ( UINT64_MAX ); div_64(&a,&b,&c); assert(a.big / b.big == c.big); }

By the way, I also ran into an issue with the bignum_add code:

tmp = a->array[i] + b->array[i] + carry;

it wasn't always "adding" properly in my implementation (tmp was 64bit, but the array items were 32bit). I needed to do the following, as it was adding the 32-bits together and losing data whenever their sum was too large:

tmp = (DTYPE_TMP)a->array[i] + (DTYPE_TMP)b->array[i] + carry;

:-)

[jepler]

I ran into this too. Unfortunately, I have a pile of other local changes that mean I can't directly disentangle my fix and send it as a pull request. Here's the reproducing example from my commit message:

For example, the following fragment spends forever in bignum_div
instead of terminating:
    struct bn a, b, c;
    bignum_from_int(&a, 1);
    bignum_init(&b); bignum_dec(&b); // b now holds biggest bignum
    bignum_div(&b, &a, &c);
Instead, c should simply get the value of b, since the divisor a is equal
to one.

[kokke]

Should be fixed with https://github.com/kokke/tiny-bignum-c/commit/6f9097ec23513377c6fe935f5b0f3a09480bbe17

Thanks for reporting a nice small test case @jepler - thanks for providing the fix @tiofw

[kokke]

@jepler am I misunderstanding you or have you found more bugs in the code?

I've added a file to the test suite for hand-picked test cases such as the one you gave: https://github.com/kokke/tiny-bignum-c/blob/master/tests/hand_picked.c

Feel free to add any failing test cases to this file - this of course applies to everyone :) - and make a PR.

[jepler]

In this case my other changes are mostly to support compatibility with cc65, a rather crusty compiler that targets 80s era 6502 CPUs. The only other bugs I encountered have been sure to working on a system where sizeof int == 2.

On Jan 12, 2018 8:17 PM, "kokke" notifications@github.com wrote:

@jepler https://github.com/jepler am I misunderstanding you or have you found more bugs in the code?

I've added a file to the test suite for hand-picked test cases such as the one you gave: https://github.com/kokke/tiny-bignum-c/blob/master/tests/ hand_picked.c

Feel free to add any failing test cases to this file - this of course applies to everyone :) - and make a PR.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/kokke/tiny-bignum-c/issues/2#issuecomment-357402529, or mute the thread https://github.com/notifications/unsubscribe-auth/ABcm6_wDhBu5Q_oK349liz10PqPHm-1hks5tKBJPgaJpZM4RReY7 .

[tiofw]

I've a couple more in bignum_mul & bignum_pow: need to check that pointers a!=c and b!=c, otherwise you're writing to c before reading the original value. The solution of course, if a or b equal c, is to copy a and/or b to a temp variable first. :-) As far as I have seen and tested, this check isn't necessary for the other functions.