Repository navigation
Get rid of C limitation for shift count in right shift #74002
Description
Activity
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.
x >> very_large_valueshould be 0 for non-negative x and -1 for negative x.x >> negative_valueshould raise ValueError.>>> 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:
https://github.com/ebranca/owasp-pysec/wiki/Overflow-in-len-functionI don't understand what such "deliberate" limitation was reported in a hardened CPython project?
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 ;-))
I agree that left shift should raise an ValueError rather than OverflowError for large negative shifts. But is hard to handle large positive shifts.
1 << countconsumescount*2/15bytes of memory. There is a gap between the maximal value of bits represented as Py_ssize_t (PY_SSIZE_T_MAX) and the number of bits of maximal Python int (PY_SSIZE_T_MAX*15/2). _PyLong_NumBits() starves from the same issue. I think an OverflowError is appropriate here for denoting the platform and implementation limitation.This may be a part of this issue or a separate issue: bytes(-1) raises a ValueError, but bytes(-10**100) raises an OverflowError.
I think an OverflowError is appropriate here for denoting the platform and implementation limitation.
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
1 << (sys.maxsize + 1)raises an OverflowError, but1 << sys.maxsize << 1can be calculated.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.
orenmn commented
on Mar 15, 2017 orenmnmannequinMannequini played a little with a patch earlier today, but stopped because I
am short on time.anyway, just in case my code is not totally rubbish, I attach my
patch draft, which should avoid OverflowError also for big positive
ints.(of course, I don't suggest to use my code instead of PR 680. I just
put it here in case it might be useful for someone.)(on my Windows 10, it passed some manual tests by me, and the test
module (except for test_venv, which fails also without the patch))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?
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
divrem1-based version: it makes fewer assumptions about relative sizes of long / long long / size_t and about the number of bits per digit. I'd rather not have another place that would have to be carefully examined in the future if the number of bits per digit changed again. Overall, Objects/longobject.c is highly portable, and I'd like to keep it that way as much as possible.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: