py/mpz: Fix overflow of borrow in mpn_div. #6844
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
f3ba882 to
97487e6
Compare
|
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>
97487e6 to
0a59938
Compare
|
@tannewt you may want to pull this in. |
|
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
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
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.