summaryrefslogtreecommitdiffstats
path: root/Objects/longobject.c
Commit message (Collapse)AuthorAgeFilesLines
* [3.11] gh-101266: Revert fix __sizeof__ for subclasses of int (#101638)Mark Dickinson2023-02-071-4/+7
| | | | | Revert "[3.11] gh-101266: Fix __sizeof__ for subclasses of int (GH-101394) (#101579)" This reverts commit cf89c16486a4cc297413e17d32082ec4f389d725.
* [3.11] gh-101266: Fix __sizeof__ for subclasses of int (GH-101394) (#101579)Mark Dickinson2023-02-051-7/+4
| | | | | | | | Fix the behaviour of the `__sizeof__` method (and hence the results returned by `sys.getsizeof`) for subclasses of `int`. Previously, `int` subclasses gave identical results to the `int` base class, ignoring the presence of the instance dictionary. (Manual backport of #101394 to the Python 3.11 branch.)
* [3.11] gh-101037: Fix potential memory underallocation for zeros of int ↵Miss Islington (bot)2023-01-211-0/+5
| | | | | | | | | | | | | | subtypes (GH-101038) (#101219) gh-101037: Fix potential memory underallocation for zeros of int subtypes (GH-101038) This PR fixes object allocation in long_subtype_new to ensure that there's at least one digit in all cases, and makes sure that the value of that digit is copied over from the source long. Needs backport to 3.11, but not any further: the change to require at least one digit was only introduced for Python 3.11. Fixes GH-101037. (cherry picked from commit 401fdf9c851eb61229250ebffa942adca99b36d1) Co-authored-by: Mark Dickinson <dickinsm@gmail.com>
* [3.11] gh-100637: Fix int and bool __sizeof__ calculation to include the 1 ↵Miss Islington (bot)2023-01-031-1/+4
| | | | | | | | | | | | element ob_digit array for 0 and False (GH-100663) (#100717) gh-100637: Fix int and bool __sizeof__ calculation to include the 1 element ob_digit array for 0 and False (GH-100663) Fixes behaviour where int (and subtypes like bool) __sizeof__ under-reports true size as it did not take into account the size 1 `ob_digit` array for the zero int. (cherry picked from commit d7e7f79ca7c2029e46a06d21a7a5abea631b5d13) Co-authored-by: Ionite <dev@ionite.io> Co-authored-by: Mark Dickinson <dickinsm@gmail.com>
* clarify the 4300-digit limit on int-str conversion (GH-100175)Miss Islington (bot)2022-12-121-2/+2
| | | | | (cherry picked from commit 935ef593211a627526b2b869ce1fc2a5e67e6cdd) Co-authored-by: Ned Batchelder <ned@nedbatchelder.com>
* gh-95778: Mention sys.set_int_max_str_digits() in error message (GH-96874)Miss Islington (bot)2022-09-161-2/+2
| | | | | | | When ValueError is raised if an integer is larger than the limit, mention sys.set_int_max_str_digits() in the error message. (cherry picked from commit e841ffc915e82e5ea6e3b473205417d63494808d) Co-authored-by: Victor Stinner <vstinner@python.org>
* gh-95778: Correctly pre-check for int-to-str conversion (GH-96537)Miss Islington (bot)2022-09-041-4/+22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Converting a large enough `int` to a decimal string raises `ValueError` as expected. However, the raise comes _after_ the quadratic-time base-conversion algorithm has run to completion. For effective DOS prevention, we need some kind of check before entering the quadratic-time loop. Oops! =) The quick fix: essentially we catch _most_ values that exceed the threshold up front. Those that slip through will still be on the small side (read: sufficiently fast), and will get caught by the existing check so that the limit remains exact. The justification for the current check. The C code check is: ```c max_str_digits / (3 * PyLong_SHIFT) <= (size_a - 11) / 10 ``` In GitHub markdown math-speak, writing $M$ for `max_str_digits`, $L$ for `PyLong_SHIFT` and $s$ for `size_a`, that check is: $$\left\lfloor\frac{M}{3L}\right\rfloor \le \left\lfloor\frac{s - 11}{10}\right\rfloor$$ From this it follows that $$\frac{M}{3L} < \frac{s-1}{10}$$ hence that $$\frac{L(s-1)}{M} > \frac{10}{3} > \log_2(10).$$ So $$2^{L(s-1)} > 10^M.$$ But our input integer $a$ satisfies $|a| \ge 2^{L(s-1)}$, so $|a|$ is larger than $10^M$. This shows that we don't accidentally capture anything _below_ the intended limit in the check. <!-- gh-issue-number: gh-95778 --> * Issue: gh-95778 <!-- /gh-issue-number --> Co-authored-by: Gregory P. Smith [Google LLC] <greg@krypto.org> (cherry picked from commit b126196838bbaf5f4d35120e0e6bcde435b0b480) Co-authored-by: Mark Dickinson <dickinsm@gmail.com>
* [3.11] gh-95778: CVE-2020-10735: Prevent DoS by very large int() (#96500)Gregory P. Smith2022-09-021-1/+44
| | | | | | | | | | | | | | | | | | Integer to and from text conversions via CPython's bignum `int` type is not safe against denial of service attacks due to malicious input. Very large input strings with hundred thousands of digits can consume several CPU seconds. This PR comes fresh from a pile of work done in our private PSRT security response team repo. This backports https://github.com/python/cpython/pull/96499 aka 511ca9452033ef95bc7d7fc404b8161068226002 Signed-off-by: Christian Heimes [Red Hat] <christian@python.org> Tons-of-polishing-up-by: Gregory P. Smith [Google] <greg@krypto.org> Reviews via the private PSRT repo via many others (see the NEWS entry in the PR). <!-- gh-issue-number: gh-95778 --> * Issue: gh-95778 <!-- /gh-issue-number --> I wrote up [a one pager for the release managers](https://docs.google.com/document/d/1KjuF_aXlzPUxTK4BMgezGJ2Pn7uevfX7g0_mvgHlL7Y/edit#).
* gh-90213: Speed up right shifts of negative integers (GH-30277)Mark Dickinson2022-05-021-29/+69
|
* gh-91731: Replace Py_BUILD_ASSERT() with static_assert() (#91730)Victor Stinner2022-04-201-2/+5
| | | | | | | | | | | | Python 3.11 now uses C11 standard which adds static_assert() to <assert.h>. * In pytime.c, replace Py_BUILD_ASSERT() with preprocessor checks on SIZEOF_TIME_T with #error. * On macOS, py_mach_timebase_info() now accepts timebase members with the same size than _PyTime_t. * py_get_monotonic_clock() now saturates GetTickCount64() to _PyTime_MAX: GetTickCount64() is unsigned, whereas _PyTime_t is signed.
* Cast to (destructor) to fix compiler warnings (GH-91711)Dennis Sweeney2022-04-201-1/+1
|
* gh-90667: Add specializations of Py_DECREF when types are known (GH-30872)Dennis Sweeney2022-04-191-15/+23
|
* gh-91117: Ensure integer mod and pow operations use cached small ints (GH-31843)Dennis Sweeney2022-04-111-0/+2
|
* bpo-46311: Clean up PyLong_FromLong and PyLong_FromLongLong (GH-30496)Mark Dickinson2022-03-011-41/+31
|
* bpo-46541: Replace core use of _Py_IDENTIFIER() with statically initialized ↵Eric Snow2022-02-081-7/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | global objects. (gh-30928) We're no longer using _Py_IDENTIFIER() (or _Py_static_string()) in any core CPython code. It is still used in a number of non-builtin stdlib modules. The replacement is: PyUnicodeObject (not pointer) fields under _PyRuntimeState, statically initialized as part of _PyRuntime. A new _Py_GET_GLOBAL_IDENTIFIER() macro facilitates lookup of the fields (along with _Py_GET_GLOBAL_STRING() for non-identifier strings). https://bugs.python.org/issue46541#msg411799 explains the rationale for this change. The core of the change is in: * (new) Include/internal/pycore_global_strings.h - the declarations for the global strings, along with the macros * Include/internal/pycore_runtime_init.h - added the static initializers for the global strings * Include/internal/pycore_global_objects.h - where the struct in pycore_global_strings.h is hooked into _PyRuntimeState * Tools/scripts/generate_global_objects.py - added generation of the global string declarations and static initializers I've also added a --check flag to generate_global_objects.py (along with make check-global-objects) to check for unused global strings. That check is added to the PR CI config. The remainder of this change updates the core code to use _Py_GET_GLOBAL_IDENTIFIER() instead of _Py_IDENTIFIER() and the related _Py*Id functions (likewise for _Py_GET_GLOBAL_STRING() instead of _Py_static_string()). This includes adding a few functions where there wasn't already an alternative to _Py*Id(), replacing the _Py_Identifier * parameter with PyObject *. The following are not changed (yet): * stop using _Py_IDENTIFIER() in the stdlib modules * (maybe) get rid of _Py_IDENTIFIER(), etc. entirely -- this may not be doable as at least one package on PyPI using this (private) API * (maybe) intern the strings during runtime init https://bugs.python.org/issue46541
* bpo-46407: Fix long_mod refleak (GH-31025)Ken Jin2022-01-311-1/+1
|
* bpo-46407: Optimizing some modulo operations (GH-30653)Crowthebird2022-01-281-9/+106
| | | | | | | Added new internal functions to compute mod without also computing the quotient. The loops can be leaner then, which leads to modestly but reliably faster execution in contexts that know they don't need the quotient. Code by Jeremiah Vivian (Pascual).
* bpo-46504: faster code for trial quotient in x_divrem() (GH-30856)Tim Peters2022-01-251-1/+8
| | | | | | | | | | * bpo-46504: faster code for trial quotient in x_divrem() This brings x_divrem() back into synch with x_divrem1(), which was changed in bpo-46406 to generate faster code to find machine-word division quotients and remainders. Modern processors compute both with a single machine instruction, but convincing C to exploit that requires writing _less_ "clever" C code.
* bpo-46406: Faster single digit int division. (#30626)Gregory P. Smith2022-01-231-10/+26
| | | | | | | | | * bpo-46406: Faster single digit int division. This expresses the algorithm in a more basic manner resulting in better instruction generation by todays compilers. See https://mail.python.org/archives/list/python-dev@python.org/thread/ZICIMX5VFCX4IOFH5NUPVHCUJCQ4Q7QM/#NEUNFZU3TQU4CPTYZNF3WCN7DOJBBTK5
* bpo-46417: _curses uses PyStructSequence_NewType() (GH-30736)Victor Stinner2022-01-211-0/+1
| | | | | | | | The _curses module now creates its ncurses_version type as a heap type using PyStructSequence_NewType(), rather than using a static type. * Move _PyStructSequence_FiniType() definition to pycore_structseq.h. * test.pythoninfo: log curses.ncurses_version.
* bpo-46417: Finalize structseq types at exit (GH-30645)Victor Stinner2022-01-211-0/+11
| | | | | | | | | | | | | | | | | | Add _PyStructSequence_FiniType() and _PyStaticType_Dealloc() functions to finalize a structseq static type in Py_Finalize(). Currrently, these functions do nothing if Python is built in release mode. Clear static types: * AsyncGenHooksType: sys.set_asyncgen_hooks() * FlagsType: sys.flags * FloatInfoType: sys.float_info * Hash_InfoType: sys.hash_info * Int_InfoType: sys.int_info * ThreadInfoType: sys.thread_info * UnraisableHookArgsType: sys.unraisablehook * VersionInfoType: sys.version * WindowsVersionType: sys.getwindowsversion()
* bpo-46361: Fix "small" `int` caching (GH-30583)Brandt Bucher2022-01-161-1/+1
|
* bpo-46020: Optimize long_pow for the common case (GH-30555)Tim Peters2022-01-121-6/+13
| | | | This cuts a bit of overhead by not initializing the table of small odd powers unless it's needed for a large exponent.
* bpo-46233: Minor speedup for bigint squaring (GH-30345)Tim Peters2022-01-041-5/+19
| | | | | | | x_mul()'s squaring code can do some redundant and/or useless work at the end of each digit pass. A more careful analysis of worst-case carries at various digit positions allows making that code leaner.
* bpo-46218: Change long_pow() to sliding window algorithm (GH-30319)Tim Peters2022-01-021-24/+84
| | | | | | | | | | | * bpo-46218: Change long_pow() to sliding window algorithm The primary motivation is to eliminate long_pow's reliance on that the number of bits in a long "digit" is a multiple of 5. Now it no longer cares how many bits are in a digit. But the sliding window approach also allows cutting the precomputed table of small powers in half, which reduces initialization overhead enough that the approach pays off for smaller exponents too. Depending on exponent bit patterns, a sliding window may also be able to save some bigint multiplies (sometimes when at least 5 consecutive exponent bits are 0, regardless of their starting bit position modulo 5). Note: boosting the window width to 6 didn't work well overall. It give marginal speed improvements for huge exponents, but the increased overhead (the small-power table needs twice as many entries) made it a loss for smaller exponents. Co-authored-by: Oleg Iarygin <dralife@yandex.ru>
* bpo-46055: Speed up binary shifting operators (GH-30044)Xinhang Xu2021-12-271-1/+16
| | | Co-authored-by: Mark Dickinson <dickinsm@gmail.com>
* bpo-46055: Streamline inner loop for right shifts (#30243)Mark Dickinson2021-12-271-7/+8
|
* bpo-45953: Statically initialize the small ints. (gh-30092)Eric Snow2021-12-141-29/+0
| | | | | | | The array of small PyLong objects has been statically declared. Here I also statically initialize them. Consequently they are no longer initialized dynamically during runtime init. I've also moved them under a new sub-struct in _PyRuntimeState, in preparation for static allocation and initialization of other global objects. https://bugs.python.org/issue45953
* bpo-46008: Make runtime-global object/type lifecycle functions and state ↵Eric Snow2021-12-091-16/+37
| | | | | | | | | | | | consistent. (gh-29998) This change is strictly renames and moving code around. It helps in the following ways: * ensures type-related init functions focus strictly on one of the three aspects (state, objects, types) * passes in PyInterpreterState * to all those functions, simplifying work on moving types/objects/state to the interpreter * consistent naming conventions help make what's going on more clear * keeping API related to a type in the corresponding header file makes it more obvious where to look for it https://bugs.python.org/issue46008
* bpo-45510: Specialize BINARY_SUBTRACT (GH-29523)Dong-hee Na2021-11-181-5/+9
|
* bpo-45691: Make array of small ints static to fix use-after-free error. ↵Mark Shannon2021-11-031-16/+14
| | | | (GH-29366)
* Store actual ints, not pointers to them in the interpreter state. (GH-29274)Mark Shannon2021-10-281-15/+6
|
* bpo-35134: Move classobject.h to Include/cpython/ (GH-28968)Victor Stinner2021-10-151-1/+0
| | | | | | | | | Move classobject.h, context.h, genobject.h and longintrepr.h header files from Include/ to Include/cpython/. Remove redundant "#ifndef Py_LIMITED_API" in context.h. Remove explicit #include "longintrepr.h" in C files. It's not needed, Python.h already includes it.
* bpo-45367: Specialize BINARY_MULTIPLY (GH-28727)Dennis Sweeney2021-10-141-4/+9
|
* bpo-45434: pyport.h no longer includes <stdlib.h> (GH-28914)Victor Stinner2021-10-131-1/+2
| | | | | Include <stdlib.h> explicitly in C files. Python.h includes <wchar.h>.
* bpo-45155 : Default arguments for int.to_bytes(length=1, ↵Barry Warsaw2021-09-161-10/+15
| | | | | | | byteorder=sys.byteorder) (#28265) Add default arguments for int.to_bytes() and int.from_bytes() Co-authored-by: Brandt Bucher <brandtbucher@gmail.com>
* bpo-44945: Specialize BINARY_ADD (GH-27967)Mark Shannon2021-08-271-6/+12
|
* bpo-44946: Streamline operators and creation of ints for common case of ↵Mark Shannon2021-08-251-92/+160
| | | | single 'digit'. (GH-27832)
* Fix a potential reference-counting bug in long_pow (GH-26690)Mark Dickinson2021-06-131-0/+1
|
* bpo-44376 - reduce pow() overhead for small exponents (GH-26662)Tim Peters2021-06-121-5/+45
| | | | Greatly reduce pow() overhead for small exponents.
* bpo-43687: Py_Initialize() creates singletons earlier (GH-25147)Victor Stinner2021-04-021-8/+11
| | | | | Reorganize pycore_interp_init() to initialize singletons before the the first PyType_Ready() call. Fix an issue when Python is configured using --without-doc-strings.
* bpo-42128: Structural Pattern Matching (PEP 634) (GH-22917)Brandt Bucher2021-02-261-1/+2
| | | | | Co-authored-by: Guido van Rossum <guido@python.org> Co-authored-by: Talin <viridia@gmail.com> Co-authored-by: Pablo Galindo <pablogsal@gmail.com>
* bpo-43268: Pass interp rather than tstate to internal functions (GH-24580)Victor Stinner2021-02-191-5/+5
| | | | | | | | | | | | | | | Pass the current interpreter (interp) rather than the current Python thread state (tstate) to internal functions which only use the interpreter. Modified functions: * _PyXXX_Fini() and _PyXXX_ClearFreeList() functions * _PyEval_SignalAsyncExc(), make_pending_calls() * _PySys_GetObject(), sys_set_object(), sys_set_object_id(), sys_set_object_str() * should_audit(), set_flags_from_config(), make_flags() * _PyAtExit_Call() * init_stdio_encoding() * etc.
* bpo-43268: _Py_IsMainInterpreter() now expects interp (GH-24577)Victor Stinner2021-02-191-1/+1
| | | | The _Py_IsMainInterpreter() function now expects interp rather than tstate.
* bpo-42519: Replace PyObject_MALLOC() with PyObject_Malloc() (GH-23587)Victor Stinner2020-12-011-1/+1
| | | | | | | | | No longer use deprecated aliases to functions: * Replace PyObject_MALLOC() with PyObject_Malloc() * Replace PyObject_REALLOC() with PyObject_Realloc() * Replace PyObject_FREE() with PyObject_Free() * Replace PyObject_Del() with PyObject_Free() * Replace PyObject_DEL() with PyObject_Free()
* bpo-42161: Remove private _PyLong_Zero and _PyLong_One (GH-23003)Victor Stinner2020-10-271-18/+0
| | | | | Use PyLong_FromLong(0) and PyLong_FromLong(1) of the public C API instead. For Python internals, _PyLong_GetZero() and _PyLong_GetOne() of pycore_long.h can be used.
* bpo-42161: Add _PyLong_GetZero() and _PyLong_GetOne() (GH-22993)Victor Stinner2020-10-261-23/+14
| | | | | | Add _PyLong_GetZero() and _PyLong_GetOne() functions and a new internal pycore_long.h header file. Python cannot be built without small integer singletons anymore.
* Revert "bpo-26680: Incorporate is_integer in all built-in and standard ↵Raymond Hettinger2020-10-071-14/+0
| | | | | library numeric types (GH-6121)" (GH-22584) This reverts commit 58a7da9e125422323f79c4ee95ac5549989d8162.
* bpo-26680: Incorporate is_integer in all built-in and standard library ↵Robert Smallshire2020-10-011-0/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | numeric types (GH-6121) * bpo-26680: Adds support for int.is_integer() for compatibility with float.is_integer(). The int.is_integer() method always returns True. * bpo-26680: Adds a test to ensure that False.is_integer() and True.is_integer() are always True. * bpo-26680: Adds Real.is_integer() with a trivial implementation using conversion to int. This default implementation is intended to reduce the workload for subclass implementers. It is not robust in the presence of infinities or NaNs and may have suboptimal performance for other types. * bpo-26680: Adds Rational.is_integer which returns True if the denominator is one. This implementation assumes the Rational is represented in it's lowest form, as required by the class docstring. * bpo-26680: Adds Integral.is_integer which always returns True. * bpo-26680: Adds tests for Fraction.is_integer called as an instance method. The tests for the Rational abstract base class use an unbound method to sidestep the inability to directly instantiate Rational. These tests check that everything works correct as an instance method. * bpo-26680: Updates documentation for Real.is_integer and built-ins int and float. The call x.is_integer() is now listed in the table of operations which apply to all numeric types except complex, with a reference to the full documentation for Real.is_integer(). Mention of is_integer() has been removed from the section 'Additional Methods on Float'. The documentation for Real.is_integer() describes its purpose, and mentions that it should be overridden for performance reasons, or to handle special values like NaN. * bpo-26680: Adds Decimal.is_integer to the Python and C implementations. The C implementation of Decimal already implements and uses mpd_isinteger internally, we just expose the existing function to Python. The Python implementation uses internal conversion to integer using to_integral_value(). In both cases, the corresponding context methods are also implemented. Tests and documentation are included. * bpo-26680: Updates the ACKS file. * bpo-26680: NEWS entries for int, the numeric ABCs and Decimal. Co-authored-by: Robert Smallshire <rob@sixty-north.com>
* bpo-41342: Convert int.__round__ to Argument Clinic (GH-21549)Serhiy Storchaka2020-07-201-7/+15
|
generated by cgit v0.12 at 2025-09-15 13:18:06 (GMT)