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
Get rid of C limitation for shift count in right shift #74002
Comments
Currently the value of right operand of the right shift operator is limited by C Py_ssize_t type. >>> 1 >> 10**100
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OverflowError: Python int too large to convert to C ssize_t
>>> (-1) >> 10**100
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OverflowError: Python int too large to convert to C ssize_t
>>> 1 >> -10**100
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OverflowError: Python int too large to convert to C ssize_t
>>> (-1) >> -10**100
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OverflowError: Python int too large to convert to C ssize_t But this is artificial limitation. Right shift can be extended to support arbitrary integers. >>> 1 >> 10
0
>>> (-1) >> 10
-1
>>> 1 >> -10
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: negative shift count
>>> (-1) >> -10
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: negative shift count |
If we change something, I suggest to be consistent with lshift. I expect a memory error on "1 << (1 << 1024)" (no unlimited loop before a global system collapse please ;-)) |
FYI I saw recently that the C limitation of len() was reported in the "owasp-pysec" project: I don't understand what such "deliberate" limitation was reported in a hardened CPython project? |
I agree that left shift should raise an ValueError rather than OverflowError for large negative shifts. But is hard to handle large positive shifts. |
This may be a part of this issue or a separate issue: bytes(-1) raises a ValueError, but bytes(-10**100) raises an OverflowError. |
It's common that integer overflow on memory allocation in C code raises a MemoryError, not an OverflowError. >>> "x" * (2**60)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
MemoryError I suggest to raise a MemoryError. |
This is not MemoryError. On 32-bit platform |
Unfortunately it is hard to totally avoid OverflowError in right shift. Righ shift of huge positive value can get non-zero result even if shift count is larger than PY_SSIZE_T_MAX. PR 680 just decreases the opportunity of getting a OverflowError. |
i played a little with a patch earlier today, but stopped because I anyway, just in case my code is not totally rubbish, I attach my (of course, I don't suggest to use my code instead of PR 680. I just (on my Windows 10, it passed some manual tests by me, and the test |
Thank you Oren, but your code doesn't work when PY_SSIZE_T_MAX < b < PY_SSIZE_T_MAX * PyLong_SHIFT and a > 2 ** b. When you drop wordshift and left only loshift_d you should drop lower wordshift digits in a. The code for left shift would be even more complex. |
Updated PR. Now OverflowError is never raised if the result is representable. Mark, could you please make a review? |
I'll try to find time this week. At least in principle, the change sounds good to me. |
Here are two patches. The first uses C long long arithmetic (it corresponds current PR 680), the second uses PyLong arithmetic. What is easier to read and verify? |
I much prefer the |
Updated the PR to divrem1-based version. The drawback is that divrem1 can fail with MemoryError while C long long arithmetic always works for integers of the size less than 1 exbibyte. |
The special case would be not needed if limit Python ints on 32-bit platforms to approximately 2**2**28. int.bit_length() could be simpler too. |
Thank you for your review Mark. |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: