Repository: cython/cython
Pull request: Use hex to store large integers
This avoids running into Python's limits about the maximum number of digits to use in string conversion.

Fixes #5596

I suspect this isn't *everywhere* that could generate long number strings but it's sufficient to solve the reported bug.

Problem statement:
[BUG] Integer string conversion limit
### Describe the bug

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "setup.py", line 10, in <module>
    ext_modules=cythonize("dp.pyx", compiler_directives=compiler_directives),
  File "Cython/Build/Dependencies.py", line 1134, in cythonize
    cythonize_one(*args)
  File "Cython/Build/Dependencies.py", line 1280, in cythonize_one
    result = compile_single(pyx_file, options, full_module_name=full_module_name)
  File "Cython/Compiler/Main.py", line 615, in compile_single
    return run_pipeline(source, options, full_module_name)
  File "Cython/Compiler/Main.py", line 539, in run_pipeline
    err, enddata = Pipeline.run_pipeline(pipeline, source)
  File "Cython/Compiler/Pipeline.py", line 398, in run_pipeline
    data = run(phase, data)
  File "Cython/Compiler/Pipeline.py", line 375, in run
    return phase(data)
  File "Cython/Compiler/Visitor.py", line 294, in Cython.Compiler.Visitor.VisitorTransform.__call__
  File "Cython/Compiler/Visitor.py", line 190, in Cython.Compiler.Visitor.TreeVisitor._visit
  File "Cython/Compiler/Visitor.py", line 141, in Cython.Compiler.Visitor.TreeVisitor._raise_compiler_error
  File "Cython/Compiler/Visitor.py", line 109, in Cython.Compiler.Visitor.TreeVisitor.dump_node
ValueError: Exceeds the limit (4300) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit


### Code to reproduce the behaviour:

```cython
# example code
```
cdef large_integer = 10**4301
print(large_integer)


### Expected behaviour

should allow one to overide the python3 new security settings
or provide some work around
working with 
Python 3.10.12
cython (latest from github)
gmpy2


### OS

Linux

### Python version

3.10.12

### Cython version

cython --version Cython version 3.0.0

### Additional context

same issue in a slightly older version of cython

Hints from issue discussion:
> should allow one to overide the python3 new security settings

That's arguably something that you should be doing (e.g. the `PYTHONINTMAXSTRDIGITS` environmental variable) and we shouldn't be taking the decision for you.

I suspect in a lot of cases we could just write a hex value instead though.
Hex values (in strings) are generally a good idea, because they are very efficient to convert to integer digits. Much faster than decimal numbers.

However, this integer value is so large that we cannot store it in any other way in C than a string. We could avoid folding such large calculated values into integers and generate code for the original calculation instead, but I'm not sure if that's so much better. There could still be limits that users may have reduced on their side, so it's still not safe (and always arbitrary) to draw a line.

CPython doesn't limit the length of hex numbers (or anything else with base 2) so hex does solve the problem
some applications in pure mathematics requires much larger numbers, is there a way around the issue? gmpy2 easily supports such numbers, and I have worked with even much larger numbers with it. 
Maybe I don't understand the problem. Python provides [ways around this](https://docs.python.org/3/library/stdtypes.html#int-max-str-digits) via `sys.set_int_max_str_digits()` or the equivalent [`PYTHONINTMAXSTRDIGITS`](https://docs.python.org/3/using/cmdline.html#envvar-PYTHONINTMAXSTRDIGITS). Why can't this work for you?
```
export PYTHONINTMAXSTRDIGITS=0
python ...
```
I am trying to create a demo— without writing patches for python and still
get reasonable speed.


It will take me six more months to write custom patches, what is wrong with
the override feature? It worked for like, FOREVER…

Gmpy2 allows for arbitrary precision , I am not sure if it can provide a
work around for this issue in a way Cython supports, suggestions are
welcome.

I realize I am pushing the limit of what is doable, but this was within the
limits like a year ago.

Breaking the number up introduces a lot of complexity that I am trying to
avoid, until really top notch programmers can address these difficult task.

That is the whole point of python and Cython, it puts complex coding into
the reach of normal every day programmers for demo’s and prototyping.


Thanks!

On Mon, Aug 7, 2023 at 2:36 AM scoder ***@***.***> wrote:

> Hex values (in strings) are generally a good idea, because they are very
> efficient to convert to integer digits. Much faster than decimal numbers.
>
> However, this integer value is so large that we cannot store it in any
> other way in C than a string. We could avoid folding such large calculated
> values into integers and generate code for the original calculation
> instead, but I'm not sure if that's so much better. There could still be
> limits that users may have reduced on their side, so it's still not safe
> (and always arbitrary) to draw a line.
>
> —
> Reply to this email directly, view it on GitHub
> <https://github.com/cython/cython/issues/5596#issuecomment-1667269522>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/ADDBZWLFJLIIB75KYCTJOMTXUCEF5ANCNFSM6AAAAAA3GM5BNU>
> .
> You are receiving this because you authored the thread.Message ID:
> ***@***.***>
>

> Maybe I don't understand the problem. Python provides [ways around this](https://docs.python.org/3/library/stdtypes.html#int-max-str-digits) via `sys.set_int_max_str_digits()` or the equivalent [`PYTHONINTMAXSTRDIGITS`](https://docs.python.org/3/using/cmdline.html#envvar-PYTHONINTMAXSTRDIGITS). Why can't this work for you?
> 
> ```
> export PYTHONINTMAXSTRDIGITS=0
> python ...
> ```

yes this is the fix, thank you 
this does not work inside the program
sys.set_int_max_str_digits(5000)
is there a way to set it to a certain number of digits rather than just any digits, I assume there is more of a speed issue if it can be any length verses a fixed (large ) number, maybe?
> this does not work inside the program
> `sys.set_int_max_str_digits(5000)`

Can you try `sys.set_int_max_str_digits(0)`?

> I assume there is more of a speed issue ...

The issue is not one of speed. As the link I pointed to states: 
> CPython has a global limit for converting between [int](https://docs.python.org/3/library/functions.html#int) and [str](https://docs.python.org/3/library/stdtypes.html#str) to mitigate denial of service attacks.

But since you already know your program, and are willing to accept the consequences of using large ints, you can turn off the limit. Doing so does not make conversions faster, it removes a check which was added because of a CVE that was filed against CPython. 

BTW, there is [a PR](https://github.com/python/cpython/issues/90716) to use a faster algorithm in CPython, which will lift this limit to a much higher number. It could use some people who use bigints to comment and say "yes, speed is important to me"
Thank you very much for the help!

My program works just need to find a way to speed out up 100x to 1000x.
Parallelization is a huge help but only like 15x to 30x .

I started profiling to find optimizations, but they only will get me
another 3x or so :-(


Regards,


Steven

On Mon, Aug 7, 2023 at 11:00 AM Matti Picus ***@***.***>
wrote:

> this does not work inside the program
> sys.set_int_max_str_digits(5000)
>
> Can you try sys.set_int_max_str_digits(0)?
>
> I assume there is more of a speed issue ...
>
> The issue is not one of speed. As the link I pointed to states:
>
> CPython has a global limit for converting between int
> <https://docs.python.org/3/library/functions.html#int> and str
> <https://docs.python.org/3/library/stdtypes.html#str> to mitigate denial
> of service attacks.
>
> But since you already know your program, and are willing to accept the
> consequences of using large ints, you can turn off the limit. Doing so does
> not make conversions faster, it removes a check which was added because of
> a CVE that was filed against CPython.
>
> BTW, there is a PR <https://github.com/python/cpython/issues/90716> to
> use a faster algorithm in CPython, which will lift this limit to a much
> higher number. It could use some people who use bigints to comment and say
> "yes, speed is important to me"
>
> —
> Reply to this email directly, view it on GitHub
> <https://github.com/cython/cython/issues/5596#issuecomment-1668036931>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/ADDBZWPOG366455LZWFMKMDXUD7IJANCNFSM6AAAAAA3GM5BNU>
> .
> You are receiving this because you authored the thread.Message ID:
> ***@***.***>
>

Commit message: Fix code format

Patch to review:
diff --git a/Cython/Compiler/ExprNodes.py b/Cython/Compiler/ExprNodes.py
index 275a6233da5..4822791f451 100644
--- a/Cython/Compiler/ExprNodes.py
+++ b/Cython/Compiler/ExprNodes.py
@@ -1365,6 +1365,16 @@ class IntNode(ConstNode):
     longness = ""
     is_c_literal = None  # unknown
 
+    # hex_value and base_10_value are designed only to simplify
+    # writing tests to get a consistent representation of value
+    @property
+    def hex_value(self):
+        return Utils.strip_l_py2(hex(Utils.str_to_number(self.value)))
+
+    @property
+    def base_10_value(self):
+        return str(Utils.str_to_number(self.value))
+
     def __init__(self, pos, **kwds):
         ExprNode.__init__(self, pos, **kwds)
         if 'type' not in kwds:
@@ -1436,7 +1446,15 @@ def coerce_to_boolean(self, env):
     def generate_evaluation_code(self, code):
         if self.type.is_pyobject:
             # pre-allocate a Python version of the number
-            plain_integer_string = str(Utils.str_to_number(self.value))
+            # (In hex if sufficiently large to cope with Python's string-to-int limitations.
+            #  We use quite a small value of "sufficiently large" - 10**13 is picked as
+            #  the approximate point where hex strings become shorter)
+            value = Utils.str_to_number(self.value)
+            formatter = hex if value > (10**13) else str
+            plain_integer_string = formatter(value)
+            if plain_integer_string[-1] in 'lL':
+                # Python 2 fix...
+                plain_integer_string = plain_integer_string[:-1]
             self.result_code = code.get_py_int(plain_integer_string, self.longness)
         else:
             self.result_code = self.get_constant_c_result_code()
diff --git a/Cython/Compiler/Optimize.py b/Cython/Compiler/Optimize.py
index 2d5b7b61882..08a732dbdd0 100644
--- a/Cython/Compiler/Optimize.py
+++ b/Cython/Compiler/Optimize.py
@@ -32,6 +32,7 @@
 from .StringEncoding import EncodedString, bytes_literal, encoded_string
 from .Errors import error, warning
 from .ParseTreeTransforms import SkipDeclarations
+from .. import Utils
 
 try:
     from __builtin__ import reduce
@@ -4473,9 +4474,11 @@ def visit_BinopNode(self, node):
                        getattr(operand2, 'unsigned', '')
             longness = "LL"[:max(len(getattr(operand1, 'longness', '')),
                                  len(getattr(operand2, 'longness', '')))]
+            value = hex(int(node.constant_result))
+            value = Utils.strip_l_py2(value)
             new_node = ExprNodes.IntNode(pos=node.pos,
                                          unsigned=unsigned, longness=longness,
-                                         value=str(int(node.constant_result)),
+                                         value=value,
                                          constant_result=int(node.constant_result))
             # IntNode is smart about the type it chooses, so we just
             # make sure we were not smarter this time
diff --git a/Cython/Utils.py b/Cython/Utils.py
index ffcee9dc37f..6f3f8712a47 100644
--- a/Cython/Utils.py
+++ b/Cython/Utils.py
@@ -439,6 +439,7 @@ def str_to_number(value):
         literal_type = value[1]  # 0'o' - 0'b' - 0'x'
         if literal_type in 'xX':
             # hex notation ('0x1AF')
+            value = strip_l_py2(value)
             value = int(value[2:], 16)
         elif literal_type in 'oO':
             # Py3 octal notation ('0o136')
@@ -454,6 +455,16 @@ def str_to_number(value):
     return -value if is_neg else value
 
 
+def strip_l_py2(value_str):
+    """
+    Python 2 likes to append 'L' to stringified numbers
+    which in then can't process when converting them to numbers.
+    """
+    if value_str[-1] in 'lL':
+        return value_str[:-1]
+    return value_str
+
+
 def long_literal(value):
     if isinstance(value, basestring):
         value = str_to_number(value)
diff --git a/tests/run/constant_folding.py b/tests/run/constant_folding.py
index 4dd70a625c9..03edd0c8abe 100644
--- a/tests/run/constant_folding.py
+++ b/tests/run/constant_folding.py
@@ -424,20 +424,20 @@ def combined():
 
 
 @cython.test_assert_path_exists(
-    '//IntNode[@value = "2"]',
-    '//IntNode[@value = "4"]',
-    '//IntNode[@value = "5"]',
-    '//IntNode[@value = "7"]',
+    '//IntNode[@base_10_value = "2"]',
+    '//IntNode[@base_10_value = "4"]',
+    '//IntNode[@base_10_value = "5"]',
+    '//IntNode[@base_10_value = "7"]',
     '//BoolBinopNode//PrimaryCmpNode',
-    '//BoolBinopNode[.//PrimaryCmpNode//IntNode[@value = "4"] and .//PrimaryCmpNode//IntNode[@value = "5"]]',
-    '//PrimaryCmpNode[.//IntNode[@value = "2"] and .//IntNode[@value = "4"]]',
-    '//PrimaryCmpNode[.//IntNode[@value = "5"] and .//IntNode[@value = "7"]]',
+    '//BoolBinopNode[.//PrimaryCmpNode//IntNode[@base_10_value = "4"] and .//PrimaryCmpNode//IntNode[@base_10_value = "5"]]',
+    '//PrimaryCmpNode[.//IntNode[@base_10_value = "2"] and .//IntNode[@base_10_value = "4"]]',
+    '//PrimaryCmpNode[.//IntNode[@base_10_value = "5"] and .//IntNode[@base_10_value = "7"]]',
 )
 @cython.test_fail_if_path_exists(
-    '//IntNode[@value = "1"]',
-    '//IntNode[@value = "8"]',
-    '//PrimaryCmpNode[.//IntNode[@value = "4"] and .//IntNode[@value = "5"]]',
-    '//PrimaryCmpNode[.//IntNode[@value = "2"] and .//IntNode[@value = "7"]]',
+    '//IntNode[@base_10_value = "1"]',
+    '//IntNode[@base_10_value = "8"]',
+    '//PrimaryCmpNode[.//IntNode[@base_10_value = "4"] and .//IntNode[@base_10_value = "5"]]',
+    '//PrimaryCmpNode[.//IntNode[@base_10_value = "2"] and .//IntNode[@base_10_value = "7"]]',
     '//BoolNode',
 )
 def cascaded_cmp_with_partial_constants(a, b):
@@ -457,22 +457,22 @@ def cascaded_cmp_with_partial_constants(a, b):
 
 
 @cython.test_assert_path_exists(
-    '//IntNode[@value = "2"]',
-    '//IntNode[@value = "4"]',
-    '//IntNode[@value = "5"]',
-    '//IntNode[@value = "7"]',
+    '//IntNode[@base_10_value = "2"]',
+    '//IntNode[@base_10_value = "4"]',
+    '//IntNode[@base_10_value = "5"]',
+    '//IntNode[@base_10_value = "7"]',
     '//BoolBinopNode',
     '//SingleAssignmentNode//BoolBinopNode',
     '//SingleAssignmentNode//BoolBinopNode//NameNode[@name = "a"]',
     '//SingleAssignmentNode//BoolBinopNode//NameNode[@name = "b"]',
-    '//BoolBinopNode[.//PrimaryCmpNode//IntNode[@value = "4"] and .//PrimaryCmpNode//IntNode[@value = "5"]]',
+    '//BoolBinopNode[.//PrimaryCmpNode//IntNode[@base_10_value = "4"] and .//PrimaryCmpNode//IntNode[@base_10_value = "5"]]',
     '//BoolNode[@value = False]',
 )
 @cython.test_fail_if_path_exists(
     '//SingleAssignmentNode//NameNode[@name = "c"]',
-    '//IntNode[@value = "1"]',
-    '//PrimaryCmpNode[.//IntNode[@value = "4"] and .//IntNode[@value = "5"]]',
-    '//PrimaryCmpNode[.//IntNode[@value = "2"] and .//IntNode[@value = "7"]]',
+    '//IntNode[@base_10_value = "1"]',
+    '//PrimaryCmpNode[.//IntNode[@base_10_value = "4"] and .//IntNode[@base_10_value = "5"]]',
+    '//PrimaryCmpNode[.//IntNode[@base_10_value = "2"] and .//IntNode[@base_10_value = "7"]]',
     '//BoolNode[@value = True]',
 )
 def cascaded_cmp_with_partial_constants_and_false_end(a, b, c):
@@ -493,13 +493,13 @@ def cascaded_cmp_with_partial_constants_and_false_end(a, b, c):
 @cython.test_assert_path_exists(
     '//PrimaryCmpNode',
     '//PrimaryCmpNode//IntNode',
-    '//PrimaryCmpNode//IntNode[@value = "0"]',
-    '//PrimaryCmpNode//IntNode[@value = "4294967296"]',
+    '//PrimaryCmpNode//IntNode[@base_10_value = "0"]',
+    '//PrimaryCmpNode//IntNode[@base_10_value = "4294967296"]',
 )
 @cython.test_fail_if_path_exists(
     '//PrimaryCmpNode//IntBinopNode',
-    '//PrimaryCmpNode//IntNode[@value = "1"]',
-    '//PrimaryCmpNode//IntNode[@value = "32"]',
+    '//PrimaryCmpNode//IntNode[@base_10_value = "1"]',
+    '//PrimaryCmpNode//IntNode[@base_10_value = "32"]',
 )
 def const_in_binop(v):
     """
diff --git a/tests/run/int_literals.pyx b/tests/run/int_literals.pyx
index 26c88430acc..fc47ac52c1c 100644
--- a/tests/run/int_literals.pyx
+++ b/tests/run/int_literals.pyx
@@ -193,3 +193,13 @@ def py_bin():
     (1, -2, 15)
     """
     return 0b01, -0b10, 0b1111
+
+def big_value():
+    """
+    >>> big_value() == (10**10000)
+    True
+    """
+    # Not quite a literal, but Cython expands the binop and inserts the literal
+    # into the C source. Which means it must be converted to a hex string to avoid
+    # hitting Python's integer conversion limits
+    return 10**10000
diff --git a/tests/run/large_integer_T5290.py b/tests/run/large_integer_T5290.py
index 93f06b5ae05..3002ec01f75 100644
--- a/tests/run/large_integer_T5290.py
+++ b/tests/run/large_integer_T5290.py
@@ -1,5 +1,5 @@
-# cython: test_assert_c_code_has = __pyx_int_large_498767777577077770_xxx_709777877895072797
-# cython: test_assert_c_code_has = __pyx_int_large2_498767777577077770_xxx_709777877895072797
+# cython: test_assert_c_code_has = __pyx_int_large_0x16a76f60ab5d456a_xxx_1cd89e1a3713adcc1d
+# cython: test_assert_c_code_has = __pyx_int_large2_0x16a76f60ab5d456a_xxx_1cd89e1a3713adcc1d
 
 """
 >>> print(large_int1)
diff --git a/tests/run/pure_py.py b/tests/run/pure_py.py
index 0cacf642969..cfe51ed4065 100644
--- a/tests/run/pure_py.py
+++ b/tests/run/pure_py.py
@@ -357,7 +357,7 @@ def count_digits_in_carray(digits):
     return counts
 
 
-@cython.test_assert_path_exists("//CFuncDeclaratorNode//IntNode[@value = '-1']")
+@cython.test_assert_path_exists("//CFuncDeclaratorNode//IntNode[@base_10_value = '-1']")
 @cython.ccall
 @cython.returns(cython.long)
 @cython.exceptval(-1)
@@ -374,7 +374,7 @@ def ccall_except(x):
     return x+1
 
 
-@cython.test_assert_path_exists("//CFuncDeclaratorNode//IntNode[@value = '-1']")
+@cython.test_assert_path_exists("//CFuncDeclaratorNode//IntNode[@base_10_value = '-1']")
 @cython.cfunc
 @cython.returns(cython.long)
 @cython.exceptval(-1)
@@ -395,7 +395,7 @@ def call_cdef_except(x):
     return cdef_except(x)
 
 
-@cython.test_assert_path_exists("//CFuncDeclaratorNode//IntNode[@value = '-1']")
+@cython.test_assert_path_exists("//CFuncDeclaratorNode//IntNode[@base_10_value = '-1']")
 @cython.ccall
 @cython.returns(cython.long)
 @cython.exceptval(-1, check=True)
@@ -414,7 +414,7 @@ def ccall_except_check(x):
     return x+1
 
 
-@cython.test_fail_if_path_exists("//CFuncDeclaratorNode//IntNode[@value = '-1']")
+@cython.test_fail_if_path_exists("//CFuncDeclaratorNode//IntNode[@base_10_value = '-1']")
 @cython.test_assert_path_exists("//CFuncDeclaratorNode")
 @cython.ccall
 @cython.returns(cython.long)
@@ -432,7 +432,7 @@ def ccall_except_check_always(x):
     return x+1
 
 
-@cython.test_fail_if_path_exists("//CFuncDeclaratorNode//IntNode[@value = '-1']")
+@cython.test_fail_if_path_exists("//CFuncDeclaratorNode//IntNode[@base_10_value = '-1']")
 @cython.test_assert_path_exists("//CFuncDeclaratorNode")
 @cython.ccall
 @cython.returns(cython.long)


Code review comments:
diff_hunk: @@ -454,6 +455,16 @@ def str_to_number(value):
     return -value if is_neg else value
 
 
+def strip_l_py2(value_str):
path: Cython/Utils.py
text: @user1:
`l` is easy to confuse with `1` and `I` in many fonts, especially `1` in the context of numbers. Maybe `strip_py2_long_suffix`?

diff_hunk: @@ -1436,7 +1446,15 @@ def coerce_to_boolean(self, env):
     def generate_evaluation_code(self, code):
         if self.type.is_pyobject:
             # pre-allocate a Python version of the number
-            plain_integer_string = str(Utils.str_to_number(self.value))
+            # (In hex if sufficiently large to cope with Python's string-to-int limitations.
+            #  We use quite a small value of "sufficiently large" - 10**13 is picked as
+            #  the approximate point where hex strings become shorter)
+            value = Utils.str_to_number(self.value)
+            formatter = hex if value > (10**13) else str
+            plain_integer_string = formatter(value)
+            if plain_integer_string[-1] in 'lL':
+                # Python 2 fix...
+                plain_integer_string = plain_integer_string[:-1]
path: Cython/Compiler/ExprNodes.py
text: @user1:
Can use the utility function here.