[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Serhiy Storchaka added the comment:


New changeset 997a4adea606069e01beac6269920709db3994d1 by Serhiy Storchaka in 
branch 'master':
Remove outdated note about constraining of the bit shift right operand. (#1258)
https://github.com/python/cpython/commit/997a4adea606069e01beac6269920709db3994d1


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
pull_requests: +1371

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Thank you for your review Mark.

--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Serhiy Storchaka added the comment:


New changeset 918403cfc3304d27e80fb792357f40bb3ba69c4e by Serhiy Storchaka in 
branch 'master':
bpo-29816: Shift operation now has less opportunity to raise OverflowError. 
(#680)
https://github.com/python/cpython/commit/918403cfc3304d27e80fb792357f40bb3ba69c4e


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Mark Dickinson]

Mark Dickinson added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


Added file: http://bugs.python.org/file46747/long-shift-overflow-long-long.diff

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


Added file: http://bugs.python.org/file46748/long-shift-overflow-divrem1.diff

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Mark Dickinson]

Mark Dickinson added the comment:

> 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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Updated PR. Now OverflowError is never raised if the result is representable.

Mark, could you please make a review?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Oren Milman]

Oren Milman added the comment:

i 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))

--
keywords: +patch
Added file: http://bugs.python.org/file46727/patchDraft1.diff

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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.

--
stage: needs patch -> patch review

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
pull_requests: +557

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

This is not MemoryError. On 32-bit platform `1 << (sys.maxsize + 1)` raises an 
OverflowError, but `1 << sys.maxsize << 1` can be calculated.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[STINNER Victor]

STINNER Victor added the comment:

> 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 "", line 1, in 
MemoryError

I suggest to raise a MemoryError.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

This may be a part of this issue or a separate issue: bytes(-1) raises a 
ValueError, but bytes(-10**100) raises an OverflowError.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

> 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 << 
count` consumes `count*2/15` bytes 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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[STINNER Victor]

STINNER Victor added the comment:

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-function

I don't understand what such "deliberate" limitation was reported in a hardened 
CPython project?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[STINNER Victor]

STINNER Victor added the comment:

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 ;-))

--
nosy: +haypo

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue29816] Get rid of C limitation for shift count in right shift

[Serhiy Storchaka]

New submission from Serhiy Storchaka:

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 "", line 1, in 
OverflowError: Python int too large to convert to C ssize_t
>>> (-1) >> 10**100
Traceback (most recent call last):
  File "", line 1, in 
OverflowError: Python int too large to convert to C ssize_t
>>> 1 >> -10**100
Traceback (most recent call last):
  File "", line 1, in 
OverflowError: Python int too large to convert to C ssize_t
>>> (-1) >> -10**100
Traceback (most recent call last):
  File "", line 1, in 
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_value` should be 0 for non-negative x and 
-1 for negative x. `x >> negative_value` should raise ValueError.

>>> 1 >> 10
0
>>> (-1) >> 10
-1
>>> 1 >> -10
Traceback (most recent call last):
  File "", line 1, in 
ValueError: negative shift count
>>> (-1) >> -10
Traceback (most recent call last):
  File "", line 1, in 
ValueError: negative shift count

--
components: Interpreter Core
messages: 289650
nosy: Oren Milman, mark.dickinson, serhiy.storchaka
priority: normal
severity: normal
stage: needs patch
status: open
title: Get rid of C limitation for shift count in right shift
type: enhancement
versions: Python 3.7

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com