/* Long (arbitrary precision) integer object implementation */ /* XXX The functional organization of this file is terrible */ #include "Python.h" #include "pycore_bitutils.h" // _Py_popcount32() #include "pycore_initconfig.h" // _PyStatus_OK() #include "pycore_call.h" // _PyObject_MakeTpCall #include "pycore_long.h" // _Py_SmallInts #include "pycore_object.h" // _PyObject_Init() #include "pycore_runtime.h" // _PY_NSMALLPOSINTS #include "pycore_structseq.h" // _PyStructSequence_FiniBuiltin() #include <float.h> // DBL_MANT_DIG #include <stddef.h> // offsetof #include "clinic/longobject.c.h" /*[clinic input] class int "PyObject *" "&PyLong_Type" [clinic start generated code]*/ /*[clinic end generated code: output=da39a3ee5e6b4b0d input=ec0275e3422a36e3]*/ #define medium_value(x) … #define IS_SMALL_INT(ival) … #define IS_SMALL_UINT(ival) … #define _MAX_STR_DIGITS_ERROR_FMT_TO_INT … #define _MAX_STR_DIGITS_ERROR_FMT_TO_STR … /* If defined, use algorithms from the _pylong.py module */ #define WITH_PYLONG_MODULE … // Forward declarations static PyLongObject* long_neg(PyLongObject *v); static PyLongObject *x_divrem(PyLongObject *, PyLongObject *, PyLongObject **); static PyObject* long_long(PyObject *v); static PyObject* long_lshift_int64(PyLongObject *a, int64_t shiftby); static inline void _Py_DECREF_INT(PyLongObject *op) { … } static inline int is_medium_int(stwodigits x) { … } static PyObject * get_small_int(sdigit ival) { … } static PyLongObject * maybe_small_long(PyLongObject *v) { … } /* For int multiplication, use the O(N**2) school algorithm unless * both operands contain more than KARATSUBA_CUTOFF digits (this * being an internal Python int digit, in base BASE). */ #define KARATSUBA_CUTOFF … #define KARATSUBA_SQUARE_CUTOFF … /* For exponentiation, use the binary left-to-right algorithm unless the ^ exponent contains more than HUGE_EXP_CUTOFF bits. In that case, do * (no more than) EXP_WINDOW_SIZE bits at a time. The potential drawback is * that a table of 2**(EXP_WINDOW_SIZE - 1) intermediate results is * precomputed. */ #define EXP_WINDOW_SIZE … #define EXP_TABLE_LEN … /* Suppose the exponent has bit length e. All ways of doing this * need e squarings. The binary method also needs a multiply for * each bit set. In a k-ary method with window width w, a multiply * for each non-zero window, so at worst (and likely!) * ceiling(e/w). The k-ary sliding window method has the same * worst case, but the window slides so it can sometimes skip * over an all-zero window that the fixed-window method can't * exploit. In addition, the windowing methods need multiplies * to precompute a table of small powers. * * For the sliding window method with width 5, 16 precomputation * multiplies are needed. Assuming about half the exponent bits * are set, then, the binary method needs about e/2 extra mults * and the window method about 16 + e/5. * * The latter is smaller for e > 53 1/3. We don't have direct * access to the bit length, though, so call it 60, which is a * multiple of a long digit's max bit length (15 or 30 so far). */ #define HUGE_EXP_CUTOFF … #define SIGCHECK(PyTryBlock) … /* Normalize (remove leading zeros from) an int object. Doesn't attempt to free the storage--in most cases, due to the nature of the algorithms used, this could save at most be one word anyway. */ static PyLongObject * long_normalize(PyLongObject *v) { … } /* Allocate a new int object with size digits. Return NULL and set exception if we run out of memory. */ #if SIZEOF_SIZE_T < 8 #define MAX_LONG_DIGITS … #else /* Guarantee that the number of bits fits in int64_t. This is more than an exbibyte, that is more than many of modern architectures support in principle. -1 is added to avoid overflow in _PyLong_Frexp(). */ #define MAX_LONG_DIGITS … #endif PyLongObject * _PyLong_New(Py_ssize_t size) { … } PyLongObject * _PyLong_FromDigits(int negative, Py_ssize_t digit_count, digit *digits) { … } PyObject * _PyLong_Copy(PyLongObject *src) { … } static PyObject * _PyLong_FromMedium(sdigit x) { … } static PyObject * _PyLong_FromLarge(stwodigits ival) { … } /* Create a new int object from a C word-sized int */ static inline PyLongObject * _PyLong_FromSTwoDigits(stwodigits x) { … } /* If a freshly-allocated int is already shared, it must be a small integer, so negating it must go to PyLong_FromLong */ Py_LOCAL_INLINE(void) _PyLong_Negate(PyLongObject **x_p) { … } /* Create a new int object from a C long int */ PyObject * PyLong_FromLong(long ival) { … } #define PYLONG_FROM_UINT(INT_TYPE, ival) … /* Create a new int object from a C unsigned long int */ PyObject * PyLong_FromUnsignedLong(unsigned long ival) { … } /* Create a new int object from a C unsigned long long int. */ PyObject * PyLong_FromUnsignedLongLong(unsigned long long ival) { … } /* Create a new int object from a C size_t. */ PyObject * PyLong_FromSize_t(size_t ival) { … } /* Create a new int object from a C double */ PyObject * PyLong_FromDouble(double dval) { … } /* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define * anything about what happens when a signed integer operation overflows, * and some compilers think they're doing you a favor by being "clever" * then. The bit pattern for the largest positive signed long is * (unsigned long)LONG_MAX, and for the smallest negative signed long * it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN. * However, some other compilers warn about applying unary minus to an * unsigned operand. Hence the weird "0-". */ #define PY_ABS_LONG_MIN … #define PY_ABS_SSIZE_T_MIN … /* Get a C long int from an int object or any object that has an __index__ method. On overflow, return -1 and set *overflow to 1 or -1 depending on the sign of the result. Otherwise *overflow is 0. For other errors (e.g., TypeError), return -1 and set an error condition. In this case *overflow will be 0. */ long PyLong_AsLongAndOverflow(PyObject *vv, int *overflow) { … } /* Get a C long int from an int object or any object that has an __index__ method. Return -1 and set an error if overflow occurs. */ long PyLong_AsLong(PyObject *obj) { … } /* Get a C int from an int object or any object that has an __index__ method. Return -1 and set an error if overflow occurs. */ int PyLong_AsInt(PyObject *obj) { … } /* Get a Py_ssize_t from an int object. Returns -1 and sets an error condition if overflow occurs. */ Py_ssize_t PyLong_AsSsize_t(PyObject *vv) { … } /* Get a C unsigned long int from an int object. Returns -1 and sets an error condition if overflow occurs. */ unsigned long PyLong_AsUnsignedLong(PyObject *vv) { … } /* Get a C size_t from an int object. Returns (size_t)-1 and sets an error condition if overflow occurs. */ size_t PyLong_AsSize_t(PyObject *vv) { … } /* Get a C unsigned long int from an int object, ignoring the high bits. Returns -1 and sets an error condition if an error occurs. */ static unsigned long _PyLong_AsUnsignedLongMask(PyObject *vv) { … } unsigned long PyLong_AsUnsignedLongMask(PyObject *op) { … } int PyLong_IsPositive(PyObject *obj) { … } int PyLong_IsNegative(PyObject *obj) { … } int PyLong_IsZero(PyObject *obj) { … } int _PyLong_Sign(PyObject *vv) { … } int PyLong_GetSign(PyObject *vv, int *sign) { … } static int bit_length_digit(digit x) { … } int64_t _PyLong_NumBits(PyObject *vv) { … } PyObject * _PyLong_FromByteArray(const unsigned char* bytes, size_t n, int little_endian, int is_signed) { … } int _PyLong_AsByteArray(PyLongObject* v, unsigned char* bytes, size_t n, int little_endian, int is_signed, int with_exceptions) { … } // Refactored out for readability, not reuse static inline int _fits_in_n_bits(Py_ssize_t v, Py_ssize_t n) { … } static inline int _resolve_endianness(int *endianness) { … } Py_ssize_t PyLong_AsNativeBytes(PyObject* vv, void* buffer, Py_ssize_t n, int flags) { … } PyObject * PyLong_FromNativeBytes(const void* buffer, size_t n, int flags) { … } PyObject * PyLong_FromUnsignedNativeBytes(const void* buffer, size_t n, int flags) { … } /* Create a new int object from a C pointer */ PyObject * PyLong_FromVoidPtr(void *p) { … } /* Get a C pointer from an int object. */ void * PyLong_AsVoidPtr(PyObject *vv) { … } /* Initial long long support by Chris Herborth ([email protected]), later * rewritten to use the newer PyLong_{As,From}ByteArray API. */ #define PY_ABS_LLONG_MIN … /* Create a new int object from a C long long int. */ PyObject * PyLong_FromLongLong(long long ival) { … } /* Create a new int object from a C Py_ssize_t. */ PyObject * PyLong_FromSsize_t(Py_ssize_t ival) { … } /* Get a C long long int from an int object or any object that has an __index__ method. Return -1 and set an error if overflow occurs. */ long long PyLong_AsLongLong(PyObject *vv) { … } /* Get a C unsigned long long int from an int object. Return -1 and set an error if overflow occurs. */ unsigned long long PyLong_AsUnsignedLongLong(PyObject *vv) { … } /* Get a C unsigned long int from an int object, ignoring the high bits. Returns -1 and sets an error condition if an error occurs. */ static unsigned long long _PyLong_AsUnsignedLongLongMask(PyObject *vv) { … } unsigned long long PyLong_AsUnsignedLongLongMask(PyObject *op) { … } /* Get a C long long int from an int object or any object that has an __index__ method. On overflow, return -1 and set *overflow to 1 or -1 depending on the sign of the result. Otherwise *overflow is 0. For other errors (e.g., TypeError), return -1 and set an error condition. In this case *overflow will be 0. */ long long PyLong_AsLongLongAndOverflow(PyObject *vv, int *overflow) { … } int _PyLong_UnsignedShort_Converter(PyObject *obj, void *ptr) { … } int _PyLong_UnsignedInt_Converter(PyObject *obj, void *ptr) { … } int _PyLong_UnsignedLong_Converter(PyObject *obj, void *ptr) { … } int _PyLong_UnsignedLongLong_Converter(PyObject *obj, void *ptr) { … } int _PyLong_Size_t_Converter(PyObject *obj, void *ptr) { … } #define CHECK_BINOP(v,w) … /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n] * is modified in place, by adding y to it. Carries are propagated as far as * x[m-1], and the remaining carry (0 or 1) is returned. */ static digit v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n) { … } /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n] * is modified in place, by subtracting y from it. Borrows are propagated as * far as x[m-1], and the remaining borrow (0 or 1) is returned. */ static digit v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n) { … } /* Shift digit vector a[0:m] d bits left, with 0 <= d < PyLong_SHIFT. Put * result in z[0:m], and return the d bits shifted out of the top. */ static digit v_lshift(digit *z, digit *a, Py_ssize_t m, int d) { … } /* Shift digit vector a[0:m] d bits right, with 0 <= d < PyLong_SHIFT. Put * result in z[0:m], and return the d bits shifted out of the bottom. */ static digit v_rshift(digit *z, digit *a, Py_ssize_t m, int d) { … } /* Divide long pin, w/ size digits, by non-zero digit n, storing quotient in pout, and returning the remainder. pin and pout point at the LSD. It's OK for pin == pout on entry, which saves oodles of mallocs/frees in _PyLong_Format, but that should be done with great care since ints are immutable. This version of the code can be 20% faster than the pre-2022 version on todays compilers on architectures like amd64. It evolved from Mark Dickinson observing that a 128:64 divide instruction was always being generated by the compiler despite us working with 30-bit digit values. See the thread for full context: https://mail.python.org/archives/list/[email protected]/thread/ZICIMX5VFCX4IOFH5NUPVHCUJCQ4Q7QM/#NEUNFZU3TQU4CPTYZNF3WCN7DOJBBTK5 If you ever want to change this code, pay attention to performance using different compilers, optimization levels, and cpu architectures. Beware of PGO/FDO builds doing value specialization such as a fast path for //10. :) Verify that 17 isn't specialized and this works as a quick test: python -m timeit -s 'x = 10**1000; r=x//10; assert r == 10**999, r' 'x//17' */ static digit inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n) { … } /* Divide an integer by a digit, returning both the quotient (as function result) and the remainder (through *prem). The sign of a is ignored; n should not be zero. */ static PyLongObject * divrem1(PyLongObject *a, digit n, digit *prem) { … } /* Remainder of long pin, w/ size digits, by non-zero digit n, returning the remainder. pin points at the LSD. */ static digit inplace_rem1(digit *pin, Py_ssize_t size, digit n) { … } /* Get the remainder of an integer divided by a digit, returning the remainder as the result of the function. The sign of a is ignored; n should not be zero. */ static PyLongObject * rem1(PyLongObject *a, digit n) { … } #ifdef WITH_PYLONG_MODULE /* asymptotically faster long_to_decimal_string, using _pylong.py */ static int pylong_int_to_decimal_string(PyObject *aa, PyObject **p_output, _PyUnicodeWriter *writer, _PyBytesWriter *bytes_writer, char **bytes_str) { … } #endif /* WITH_PYLONG_MODULE */ /* Convert an integer to a base 10 string. Returns a new non-shared string. (Return value is non-shared so that callers can modify the returned value if necessary.) */ static int long_to_decimal_string_internal(PyObject *aa, PyObject **p_output, _PyUnicodeWriter *writer, _PyBytesWriter *bytes_writer, char **bytes_str) { … } static PyObject * long_to_decimal_string(PyObject *aa) { … } /* Convert an int object to a string, using a given conversion base, which should be one of 2, 8 or 16. Return a string object. If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x' if alternate is nonzero. */ static int long_format_binary(PyObject *aa, int base, int alternate, PyObject **p_output, _PyUnicodeWriter *writer, _PyBytesWriter *bytes_writer, char **bytes_str) { … } PyObject * _PyLong_Format(PyObject *obj, int base) { … } int _PyLong_FormatWriter(_PyUnicodeWriter *writer, PyObject *obj, int base, int alternate) { … } char* _PyLong_FormatBytesWriter(_PyBytesWriter *writer, char *str, PyObject *obj, int base, int alternate) { … } /* Table of digit values for 8-bit string -> integer conversion. * '0' maps to 0, ..., '9' maps to 9. * 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35. * All other indices map to 37. * Note that when converting a base B string, a char c is a legitimate * base B digit iff _PyLong_DigitValue[Py_CHARPyLong_MASK(c)] < B. */ unsigned char _PyLong_DigitValue[256] = …; /* `start` and `end` point to the start and end of a string of base `base` * digits. base is a power of 2 (2, 4, 8, 16, or 32). An unnormalized int is * returned in *res. The string should be already validated by the caller and * consists only of valid digit characters and underscores. `digits` gives the * number of digit characters. * * The point to this routine is that it takes time linear in the * number of string characters. * * Return values: * -1 on syntax error (exception needs to be set, *res is untouched) * 0 else (exception may be set, in that case *res is set to NULL) */ static int long_from_binary_base(const char *start, const char *end, Py_ssize_t digits, int base, PyLongObject **res) { … } #ifdef WITH_PYLONG_MODULE /* asymptotically faster str-to-long conversion for base 10, using _pylong.py */ static int pylong_int_from_string(const char *start, const char *end, PyLongObject **res) { … } #endif /* WITH_PYLONG_MODULE */ /*** long_from_non_binary_base: parameters and return values are the same as long_from_binary_base. Binary bases can be converted in time linear in the number of digits, because Python's representation base is binary. Other bases (including decimal!) use the simple quadratic-time algorithm below, complicated by some speed tricks. First some math: the largest integer that can be expressed in N base-B digits is B**N-1. Consequently, if we have an N-digit input in base B, the worst- case number of Python digits needed to hold it is the smallest integer n s.t. BASE**n-1 >= B**N-1 [or, adding 1 to both sides] BASE**n >= B**N [taking logs to base BASE] n >= log(B**N)/log(BASE) = N * log(B)/log(BASE) The static array log_base_BASE[base] == log(base)/log(BASE) so we can compute this quickly. A Python int with that much space is reserved near the start, and the result is computed into it. The input string is actually treated as being in base base**i (i.e., i digits are processed at a time), where two more static arrays hold: convwidth_base[base] = the largest integer i such that base**i <= BASE convmultmax_base[base] = base ** convwidth_base[base] The first of these is the largest i such that i consecutive input digits must fit in a single Python digit. The second is effectively the input base we're really using. Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base convmultmax_base[base], the result is "simply" (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1 where B = convmultmax_base[base]. Error analysis: as above, the number of Python digits `n` needed is worst- case n >= N * log(B)/log(BASE) where `N` is the number of input digits in base `B`. This is computed via size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1; below. Two numeric concerns are how much space this can waste, and whether the computed result can be too small. To be concrete, assume BASE = 2**15, which is the default (and it's unlikely anyone changes that). Waste isn't a problem: provided the first input digit isn't 0, the difference between the worst-case input with N digits and the smallest input with N digits is about a factor of B, but B is small compared to BASE so at most one allocated Python digit can remain unused on that count. If N*log(B)/log(BASE) is mathematically an exact integer, then truncating that and adding 1 returns a result 1 larger than necessary. However, that can't happen: whenever B is a power of 2, long_from_binary_base() is called instead, and it's impossible for B**i to be an integer power of 2**15 when B is not a power of 2 (i.e., it's impossible for N*log(B)/log(BASE) to be an exact integer when B is not a power of 2, since B**i has a prime factor other than 2 in that case, but (2**15)**j's only prime factor is 2). The computed result can be too small if the true value of N*log(B)/log(BASE) is a little bit larger than an exact integer, but due to roundoff errors (in computing log(B), log(BASE), their quotient, and/or multiplying that by N) yields a numeric result a little less than that integer. Unfortunately, "how close can a transcendental function get to an integer over some range?" questions are generally theoretically intractable. Computer analysis via continued fractions is practical: expand log(B)/log(BASE) via continued fractions, giving a sequence i/j of "the best" rational approximations. Then j*log(B)/log(BASE) is approximately equal to (the integer) i. This shows that we can get very close to being in trouble, but very rarely. For example, 76573 is a denominator in one of the continued-fraction approximations to log(10)/log(2**15), and indeed: >>> log(10)/log(2**15)*76573 16958.000000654003 is very close to an integer. If we were working with IEEE single-precision, rounding errors could kill us. Finding worst cases in IEEE double-precision requires better-than-double-precision log() functions, and Tim didn't bother. Instead the code checks to see whether the allocated space is enough as each new Python digit is added, and copies the whole thing to a larger int if not. This should happen extremely rarely, and in fact I don't have a test case that triggers it(!). Instead the code was tested by artificially allocating just 1 digit at the start, so that the copying code was exercised for every digit beyond the first. ***/ static int long_from_non_binary_base(const char *start, const char *end, Py_ssize_t digits, int base, PyLongObject **res) { … } /* *str points to the first digit in a string of base `base` digits. base is an * integer from 2 to 36 inclusive. Here we don't need to worry about prefixes * like 0x or leading +- signs. The string should be null terminated consisting * of ASCII digits and separating underscores possibly with trailing whitespace * but we have to validate all of those points here. * * If base is a power of 2 then the complexity is linear in the number of * characters in the string. Otherwise a quadratic algorithm is used for * non-binary bases. * * Return values: * * - Returns -1 on syntax error (exception needs to be set, *res is untouched) * - Returns 0 and sets *res to NULL for MemoryError, OverflowError, or * _pylong.int_from_string() errors. * - Returns 0 and sets *res to an unsigned, unnormalized PyLong (success!). * * Afterwards *str is set to point to the first non-digit (which may be *str!). */ static int long_from_string_base(const char **str, int base, PyLongObject **res) { … } /* Parses an int from a bytestring. Leading and trailing whitespace will be * ignored. * * If successful, a PyLong object will be returned and 'pend' will be pointing * to the first unused byte unless it's NULL. * * If unsuccessful, NULL will be returned. */ PyObject * PyLong_FromString(const char *str, char **pend, int base) { … } /* Since PyLong_FromString doesn't have a length parameter, * check here for possible NULs in the string. * * Reports an invalid literal as a bytes object. */ PyObject * _PyLong_FromBytes(const char *s, Py_ssize_t len, int base) { … } PyObject * PyLong_FromUnicodeObject(PyObject *u, int base) { … } /* Int division with remainder, top-level routine */ static int long_divrem(PyLongObject *a, PyLongObject *b, PyLongObject **pdiv, PyLongObject **prem) { … } /* Int remainder, top-level routine */ static int long_rem(PyLongObject *a, PyLongObject *b, PyLongObject **prem) { … } /* Unsigned int division with remainder -- the algorithm. The arguments v1 and w1 should satisfy 2 <= _PyLong_DigitCount(w1) <= _PyLong_DigitCount(v1). */ static PyLongObject * x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem) { … } /* For a nonzero PyLong a, express a in the form x * 2**e, with 0.5 <= abs(x) < 1.0 and e >= 0; return x and put e in *e. Here x is rounded to DBL_MANT_DIG significant bits using round-half-to-even. If a == 0, return 0.0 and set *e = 0. If the resulting exponent e is larger than PY_SSIZE_T_MAX, raise OverflowError and return -1.0. */ /* attempt to define 2.0**DBL_MANT_DIG as a compile-time constant */ #if DBL_MANT_DIG == 53 #define EXP2_DBL_MANT_DIG … #else #define EXP2_DBL_MANT_DIG … #endif double _PyLong_Frexp(PyLongObject *a, int64_t *e) { … } /* Get a C double from an int object. Rounds to the nearest double, using the round-half-to-even rule in the case of a tie. */ double PyLong_AsDouble(PyObject *v) { … } /* Methods */ /* if a < b, return a negative number if a == b, return 0 if a > b, return a positive number */ static Py_ssize_t long_compare(PyLongObject *a, PyLongObject *b) { … } static PyObject * long_richcompare(PyObject *self, PyObject *other, int op) { … } static void long_dealloc(PyObject *self) { … } static Py_hash_t long_hash(PyObject *obj) { … } /* Add the absolute values of two integers. */ static PyLongObject * x_add(PyLongObject *a, PyLongObject *b) { … } /* Subtract the absolute values of two integers. */ static PyLongObject * x_sub(PyLongObject *a, PyLongObject *b) { … } static PyLongObject * long_add(PyLongObject *a, PyLongObject *b) { … } PyObject * _PyLong_Add(PyLongObject *a, PyLongObject *b) { … } static PyObject * long_add_method(PyObject *a, PyObject *b) { … } static PyLongObject * long_sub(PyLongObject *a, PyLongObject *b) { … } PyObject * _PyLong_Subtract(PyLongObject *a, PyLongObject *b) { … } static PyObject * long_sub_method(PyObject *a, PyObject *b) { … } /* Grade school multiplication, ignoring the signs. * Returns the absolute value of the product, or NULL if error. */ static PyLongObject * x_mul(PyLongObject *a, PyLongObject *b) { … } /* A helper for Karatsuba multiplication (k_mul). Takes an int "n" and an integer "size" representing the place to split, and sets low and high such that abs(n) == (high << size) + low, viewing the shift as being by digits. The sign bit is ignored, and the return values are >= 0. Returns 0 on success, -1 on failure. */ static int kmul_split(PyLongObject *n, Py_ssize_t size, PyLongObject **high, PyLongObject **low) { … } static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b); /* Karatsuba multiplication. Ignores the input signs, and returns the * absolute value of the product (or NULL if error). * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295). */ static PyLongObject * k_mul(PyLongObject *a, PyLongObject *b) { … } /* (*) Why adding t3 can't "run out of room" above. Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts to start with: 1. For any integer i, i = c(i/2) + f(i/2). In particular, bsize = c(bsize/2) + f(bsize/2). 2. shift = f(bsize/2) 3. asize <= bsize 4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this routine, so asize > bsize/2 >= f(bsize/2) in this routine. We allocated asize + bsize result digits, and add t3 into them at an offset of shift. This leaves asize+bsize-shift allocated digit positions for t3 to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) = asize + c(bsize/2) available digit positions. bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has at most c(bsize/2) digits + 1 bit. If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2) digits, and al has at most f(bsize/2) digits in any case. So ah+al has at most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit. The product (ah+al)*(bh+bl) therefore has at most c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits and we have asize + c(bsize/2) available digit positions. We need to show this is always enough. An instance of c(bsize/2) cancels out in both, so the question reduces to whether asize digits is enough to hold (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize, then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4, asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1 digit is enough to hold 2 bits. This is so since PyLong_SHIFT=15 >= 2. If asize == bsize, then we're asking whether bsize digits is enough to hold c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits is enough to hold 2 bits. This is so if bsize >= 2, which holds because bsize >= KARATSUBA_CUTOFF >= 2. Note that since there's always enough room for (ah+al)*(bh+bl), and that's clearly >= each of ah*bh and al*bl, there's always enough room to subtract ah*bh and al*bl too. */ /* b has at least twice the digits of a, and a is big enough that Karatsuba * would pay off *if* the inputs had balanced sizes. View b as a sequence * of slices, each with the same number of digits as a, and multiply the * slices by a, one at a time. This gives k_mul balanced inputs to work with, * and is also cache-friendly (we compute one double-width slice of the result * at a time, then move on, never backtracking except for the helpful * single-width slice overlap between successive partial sums). */ static PyLongObject * k_lopsided_mul(PyLongObject *a, PyLongObject *b) { … } static PyLongObject* long_mul(PyLongObject *a, PyLongObject *b) { … } PyObject * _PyLong_Multiply(PyLongObject *a, PyLongObject *b) { … } static PyObject * long_mul_method(PyObject *a, PyObject *b) { … } /* Fast modulo division for single-digit longs. */ static PyObject * fast_mod(PyLongObject *a, PyLongObject *b) { … } /* Fast floor division for single-digit longs. */ static PyObject * fast_floor_div(PyLongObject *a, PyLongObject *b) { … } #ifdef WITH_PYLONG_MODULE /* asymptotically faster divmod, using _pylong.py */ static int pylong_int_divmod(PyLongObject *v, PyLongObject *w, PyLongObject **pdiv, PyLongObject **pmod) { … } #endif /* WITH_PYLONG_MODULE */ /* The / and % operators are now defined in terms of divmod(). The expression a mod b has the value a - b*floor(a/b). The long_divrem function gives the remainder after division of |a| by |b|, with the sign of a. This is also expressed as a - b*trunc(a/b), if trunc truncates towards zero. Some examples: a b a rem b a mod b 13 10 3 3 -13 10 -3 7 13 -10 3 -7 -13 -10 -3 -3 So, to get from rem to mod, we have to add b if a and b have different signs. We then subtract one from the 'div' part of the outcome to keep the invariant intact. */ /* Compute * *pdiv, *pmod = divmod(v, w) * NULL can be passed for pdiv or pmod, in which case that part of * the result is simply thrown away. The caller owns a reference to * each of these it requests (does not pass NULL for). */ static int l_divmod(PyLongObject *v, PyLongObject *w, PyLongObject **pdiv, PyLongObject **pmod) { … } /* Compute * *pmod = v % w * pmod cannot be NULL. The caller owns a reference to pmod. */ static int l_mod(PyLongObject *v, PyLongObject *w, PyLongObject **pmod) { … } static PyObject * long_div(PyObject *a, PyObject *b) { … } /* PyLong/PyLong -> float, with correctly rounded result. */ #define MANT_DIG_DIGITS … #define MANT_DIG_BITS … static PyObject * long_true_divide(PyObject *v, PyObject *w) { … } static PyObject * long_mod(PyObject *a, PyObject *b) { … } static PyObject * long_divmod(PyObject *a, PyObject *b) { … } /* Compute an inverse to a modulo n, or raise ValueError if a is not invertible modulo n. Assumes n is positive. The inverse returned is whatever falls out of the extended Euclidean algorithm: it may be either positive or negative, but will be smaller than n in absolute value. Pure Python equivalent for long_invmod: def invmod(a, n): b, c = 1, 0 while n: q, r = divmod(a, n) a, b, c, n = n, c, b - q*c, r # at this point a is the gcd of the original inputs if a == 1: return b raise ValueError("Not invertible") */ static PyLongObject * long_invmod(PyLongObject *a, PyLongObject *n) { … } /* pow(v, w, x) */ static PyObject * long_pow(PyObject *v, PyObject *w, PyObject *x) { … } static PyObject * long_invert(PyObject *self) { … } static PyLongObject * long_neg(PyLongObject *v) { … } static PyObject * long_neg_method(PyObject *v) { … } static PyLongObject* long_abs(PyLongObject *v) { … } static PyObject * long_abs_method(PyObject *v) { … } static int long_bool(PyObject *v) { … } /* Inner function for both long_rshift and _PyLong_Rshift, shifting an integer right by PyLong_SHIFT*wordshift + remshift bits. wordshift should be nonnegative. */ static PyObject * long_rshift1(PyLongObject *a, Py_ssize_t wordshift, digit remshift) { … } static PyObject * long_rshift(PyObject *a, PyObject *b) { … } /* Return a >> shiftby. */ PyObject * _PyLong_Rshift(PyObject *a, int64_t shiftby) { … } static PyObject * long_lshift1(PyLongObject *a, Py_ssize_t wordshift, digit remshift) { … } static PyObject * long_lshift_method(PyObject *aa, PyObject *bb) { … } /* Return a << shiftby. */ static PyObject * long_lshift_int64(PyLongObject *a, int64_t shiftby) { … } PyObject * _PyLong_Lshift(PyObject *a, int64_t shiftby) { … } /* Compute two's complement of digit vector a[0:m], writing result to z[0:m]. The digit vector a need not be normalized, but should not be entirely zero. a and z may point to the same digit vector. */ static void v_complement(digit *z, digit *a, Py_ssize_t m) { … } /* Bitwise and/xor/or operations */ static PyObject * long_bitwise(PyLongObject *a, char op, /* '&', '|', '^' */ PyLongObject *b) { … } static PyObject * long_and(PyObject *a, PyObject *b) { … } static PyObject * long_xor(PyObject *a, PyObject *b) { … } static PyObject * long_or(PyObject *a, PyObject *b) { … } static PyObject * long_long(PyObject *v) { … } PyObject * _PyLong_GCD(PyObject *aarg, PyObject *barg) { … } static PyObject * long_float(PyObject *v) { … } static PyObject * long_subtype_new(PyTypeObject *type, PyObject *x, PyObject *obase); /*[clinic input] @classmethod int.__new__ as long_new x: object(c_default="NULL") = 0 / base as obase: object(c_default="NULL") = 10 [clinic start generated code]*/ static PyObject * long_new_impl(PyTypeObject *type, PyObject *x, PyObject *obase) /*[clinic end generated code: output=e47cfe777ab0f24c input=81c98f418af9eb6f]*/ { … } /* Wimpy, slow approach to tp_new calls for subtypes of int: first create a regular int from whatever arguments we got, then allocate a subtype instance and initialize it from the regular int. The regular int is then thrown away. */ static PyObject * long_subtype_new(PyTypeObject *type, PyObject *x, PyObject *obase) { … } /*[clinic input] int.__getnewargs__ [clinic start generated code]*/ static PyObject * int___getnewargs___impl(PyObject *self) /*[clinic end generated code: output=839a49de3f00b61b input=5904770ab1fb8c75]*/ { … } static PyObject * long_get0(PyObject *Py_UNUSED(self), void *Py_UNUSED(context)) { … } static PyObject * long_get1(PyObject *Py_UNUSED(self), void *Py_UNUSED(ignored)) { … } /*[clinic input] int.__format__ format_spec: unicode / Convert to a string according to format_spec. [clinic start generated code]*/ static PyObject * int___format___impl(PyObject *self, PyObject *format_spec) /*[clinic end generated code: output=b4929dee9ae18689 input=d5e1254a47e8d1dc]*/ { … } /* Return a pair (q, r) such that a = b * q + r, and abs(r) <= abs(b)/2, with equality possible only if q is even. In other words, q == a / b, rounded to the nearest integer using round-half-to-even. */ PyObject * _PyLong_DivmodNear(PyObject *a, PyObject *b) { … } /*[clinic input] int.__round__ ndigits as o_ndigits: object = None / Rounding an Integral returns itself. Rounding with an ndigits argument also returns an integer. [clinic start generated code]*/ static PyObject * int___round___impl(PyObject *self, PyObject *o_ndigits) /*[clinic end generated code: output=954fda6b18875998 input=30c2aec788263144]*/ { … } /*[clinic input] int.__sizeof__ -> Py_ssize_t Returns size in memory, in bytes. [clinic start generated code]*/ static Py_ssize_t int___sizeof___impl(PyObject *self) /*[clinic end generated code: output=3303f008eaa6a0a5 input=9b51620c76fc4507]*/ { … } /*[clinic input] int.bit_length Number of bits necessary to represent self in binary. >>> bin(37) '0b100101' >>> (37).bit_length() 6 [clinic start generated code]*/ static PyObject * int_bit_length_impl(PyObject *self) /*[clinic end generated code: output=fc1977c9353d6a59 input=e4eb7a587e849a32]*/ { … } static int popcount_digit(digit d) { … } /*[clinic input] int.bit_count Number of ones in the binary representation of the absolute value of self. Also known as the population count. >>> bin(13) '0b1101' >>> (13).bit_count() 3 [clinic start generated code]*/ static PyObject * int_bit_count_impl(PyObject *self) /*[clinic end generated code: output=2e571970daf1e5c3 input=7e0adef8e8ccdf2e]*/ { … } /*[clinic input] int.as_integer_ratio Return a pair of integers, whose ratio is equal to the original int. The ratio is in lowest terms and has a positive denominator. >>> (10).as_integer_ratio() (10, 1) >>> (-10).as_integer_ratio() (-10, 1) >>> (0).as_integer_ratio() (0, 1) [clinic start generated code]*/ static PyObject * int_as_integer_ratio_impl(PyObject *self) /*[clinic end generated code: output=e60803ae1cc8621a input=384ff1766634bec2]*/ { … } /*[clinic input] int.to_bytes length: Py_ssize_t = 1 Length of bytes object to use. An OverflowError is raised if the integer is not representable with the given number of bytes. Default is length 1. byteorder: unicode(c_default="NULL") = "big" The byte order used to represent the integer. If byteorder is 'big', the most significant byte is at the beginning of the byte array. If byteorder is 'little', the most significant byte is at the end of the byte array. To request the native byte order of the host system, use sys.byteorder as the byte order value. Default is to use 'big'. * signed as is_signed: bool = False Determines whether two's complement is used to represent the integer. If signed is False and a negative integer is given, an OverflowError is raised. Return an array of bytes representing an integer. [clinic start generated code]*/ static PyObject * int_to_bytes_impl(PyObject *self, Py_ssize_t length, PyObject *byteorder, int is_signed) /*[clinic end generated code: output=89c801df114050a3 input=a0103d0e9ad85c2b]*/ { … } /*[clinic input] @classmethod int.from_bytes bytes as bytes_obj: object Holds the array of bytes to convert. The argument must either support the buffer protocol or be an iterable object producing bytes. Bytes and bytearray are examples of built-in objects that support the buffer protocol. byteorder: unicode(c_default="NULL") = "big" The byte order used to represent the integer. If byteorder is 'big', the most significant byte is at the beginning of the byte array. If byteorder is 'little', the most significant byte is at the end of the byte array. To request the native byte order of the host system, use sys.byteorder as the byte order value. Default is to use 'big'. * signed as is_signed: bool = False Indicates whether two's complement is used to represent the integer. Return the integer represented by the given array of bytes. [clinic start generated code]*/ static PyObject * int_from_bytes_impl(PyTypeObject *type, PyObject *bytes_obj, PyObject *byteorder, int is_signed) /*[clinic end generated code: output=efc5d68e31f9314f input=2ff527997fe7b0c5]*/ { … } static PyObject * long_long_meth(PyObject *self, PyObject *Py_UNUSED(ignored)) { … } /*[clinic input] int.is_integer Returns True. Exists for duck type compatibility with float.is_integer. [clinic start generated code]*/ static PyObject * int_is_integer_impl(PyObject *self) /*[clinic end generated code: output=90f8e794ce5430ef input=7e41c4d4416e05f2]*/ { … } static PyObject * long_vectorcall(PyObject *type, PyObject * const*args, size_t nargsf, PyObject *kwnames) { … } static PyMethodDef long_methods[] = …; static PyGetSetDef long_getset[] = …; PyDoc_STRVAR(long_doc, "int([x]) -> integer\n\ int(x, base=10) -> integer\n\ \n\ Convert a number or string to an integer, or return 0 if no arguments\n\ are given. If x is a number, return x.__int__(). For floating-point\n\ numbers, this truncates towards zero.\n\ \n\ If x is not a number or if base is given, then x must be a string,\n\ bytes, or bytearray instance representing an integer literal in the\n\ given base. The literal can be preceded by '+' or '-' and be surrounded\n\ by whitespace. The base defaults to 10. Valid bases are 0 and 2-36.\n\ Base 0 means to interpret the base from the string as an integer literal.\n\ >>> int('0b100', base=0)\n\ 4"); static PyNumberMethods long_as_number = …; PyTypeObject PyLong_Type = …; static PyTypeObject Int_InfoType; PyDoc_STRVAR(int_info__doc__, "sys.int_info\n\ \n\ A named tuple that holds information about Python's\n\ internal representation of integers. The attributes are read only."); static PyStructSequence_Field int_info_fields[] = …; static PyStructSequence_Desc int_info_desc = …; PyObject * PyLong_GetInfo(void) { … } /* runtime lifecycle */ PyStatus _PyLong_InitTypes(PyInterpreterState *interp) { … } void _PyLong_FiniTypes(PyInterpreterState *interp) { … } #undef PyUnstable_Long_IsCompact int PyUnstable_Long_IsCompact(const PyLongObject* op) { … } #undef PyUnstable_Long_CompactValue Py_ssize_t PyUnstable_Long_CompactValue(const PyLongObject* op) { … } PyObject* PyLong_FromInt32(int32_t value) { … } PyObject* PyLong_FromUInt32(uint32_t value) { … } PyObject* PyLong_FromInt64(int64_t value) { … } PyObject* PyLong_FromUInt64(uint64_t value) { … } #define LONG_TO_INT(obj, value, type_name) … int PyLong_AsInt32(PyObject *obj, int32_t *value) { … } int PyLong_AsInt64(PyObject *obj, int64_t *value) { … } #define LONG_TO_UINT(obj, value, type_name) … int PyLong_AsUInt32(PyObject *obj, uint32_t *value) { … } int PyLong_AsUInt64(PyObject *obj, uint64_t *value) { … }
Codebase Browser
cpython