py/mpz: Fix overflow of borrow in mpn_div.

For certain operands to mpn_div, the existing code path for
`DIG_SIZE == MPZ_DBL_DIG_SIZE / 2` had a bug in it where borrow could still
overflow in the `(x >= *n || *n - x <= borrow)` branch, ie
`borrow + x - (mpz_dbl_dig_t)*n` overflows the borrow variable.  In such
cases the subsequent right-shift of borrow would not bring in the overflow
bit, leading to an error in the result.  An example division that had
overflow when MPZ_DIG_SIZE = 16 is `(2 ** 48 - 1) ** 2 // (2 ** 48 - 1)`.

This is fixed in this commit by simplifying the code and handling the low
digits of borrow first, and then the upper bits (to shift down) separately.
There is no longer a distinction between `DIG_SIZE < MPZ_DBL_DIG_SIZE / 2`
and `DIG_SIZE == MPZ_DBL_DIG_SIZE / 2`.

This commit also simplifies the second part of the calculation so that
borrow does not need to be negated (instead the code just works knowing
that borrow is negative and using + instead of - in calculations involving
borrow).

Fixes #6777.

Signed-off-by: Damien George <damien@micropython.org>

1 files changed, 4 insertions, 0 deletions

diff --git a/tests/basics/int_big_div.py b/tests/basics/int_big_div.py
index 642f051d41..29fd405970 100644
--- a/tests/basics/int_big_div.py
+++ b/tests/basics/int_big_div.py
@@ -8,3 +8,7 @@ x = 0x8000000000000000
 print((x + 1) // x)
 x = 0x86c60128feff5330
 print((x + 1) // x)
+
+# these check edge cases where borrow overflows
+print((2 ** 48 - 1) ** 2 // (2 ** 48 - 1))
+print((2 ** 256 - 2 ** 32) ** 2 // (2 ** 256 - 2 ** 32))