10000 py/mpz: Fix overflow of borrow in mpn_div. by dpgeorge · Pull Request #6844 · micropython/micropython · GitHub
[go: up one dir, main page]

Skip to content

py/mpz: Fix overflow of borrow in mpn_div. #6844

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged

Conversation

dpgeorge
Copy link
Member
@dpgeorge dpgeorge commented Feb 4, 2021

This fixes #6777. But there might be a cleaner way to fix it, and there might also be additional overflow of the borrow that is not caught by this fix.

Edit: there is a cleaner fix, which is now applied in this PR.

@dpgeorge dpgeorge added the py-core Relates to py/ directory in source label Feb 4, 2021
@dpgeorge dpgeorge force-pushed the py-mpz-fix-div-borrow-overflow branch 2 times, most recently from f3ba882 to 97487e6 Compare February 6, 2021 13:50
@dpgeorge
Copy link
Member Author
dpgeorge commented Feb 6, 2021

Code has been simplified a lot to use arithmetic that does not overflow, so there are no longer any branches.

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 micropython#6777.

Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge dpgeorge force-pushed the py-mpz-fix-div-borrow-overflow branch from 97487e6 to 0a59938 Compare February 8, 2021 01:00
@dpgeorge dpgeorge merged commit 0a59938 into micropython:master Feb 8, 2021
@dpgeorge dpgeorge deleted the py-mpz-fix-div-borrow-overflow branch February 8, 2021 01:25
@dpgeorge
Copy link
Member Author
dpgeorge commented Feb 8, 2021

@tannewt you may want to pull this in.

@tannewt
Copy link
tannewt commented Feb 8, 2021

Thanks! I opened an issue for us to. ☝️

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
py-core Relates to py/ directory in source
Projects
None yet
Development

Successfully merging this pull request may close these issues.

MPZ arithmetic errors with DIG_SIZE == MPZ_DIG_SIZE
2 participants
0