| 1 |
#ifndef Py_INTERNAL_LONG_H |
| 2 |
#define Py_INTERNAL_LONG_H |
| 3 |
#ifdef __cplusplus |
| 4 |
extern "C" { |
| 5 |
#endif |
| 6 |
|
| 7 |
#ifndef Py_BUILD_CORE |
| 8 |
# error "this header requires Py_BUILD_CORE define" |
| 9 |
#endif |
| 10 |
|
| 11 |
#include "pycore_bytesobject.h" // _PyBytesWriter |
| 12 |
#include "pycore_runtime.h" // _Py_SINGLETON() |
| 13 |
|
| 14 |
/* |
| 15 |
* Default int base conversion size limitation: Denial of Service prevention. |
| 16 |
* |
| 17 |
* Chosen such that this isn't wildly slow on modern hardware and so that |
| 18 |
* everyone's existing deployed numpy test suite passes before |
| 19 |
* https://github.com/numpy/numpy/issues/22098 is widely available. |
| 20 |
* |
| 21 |
* $ python -m timeit -s 's = "1"*4300' 'int(s)' |
| 22 |
* 2000 loops, best of 5: 125 usec per loop |
| 23 |
* $ python -m timeit -s 's = "1"*4300; v = int(s)' 'str(v)' |
| 24 |
* 1000 loops, best of 5: 311 usec per loop |
| 25 |
* (zen2 cloud VM) |
| 26 |
* |
| 27 |
* 4300 decimal digits fits a ~14284 bit number. |
| 28 |
*/ |
| 29 |
#define _PY_LONG_DEFAULT_MAX_STR_DIGITS 4300 |
| 30 |
/* |
| 31 |
* Threshold for max digits check. For performance reasons int() and |
| 32 |
* int.__str__() don't checks values that are smaller than this |
| 33 |
* threshold. Acts as a guaranteed minimum size limit for bignums that |
| 34 |
* applications can expect from CPython. |
| 35 |
* |
| 36 |
* % python -m timeit -s 's = "1"*640; v = int(s)' 'str(int(s))' |
| 37 |
* 20000 loops, best of 5: 12 usec per loop |
| 38 |
* |
| 39 |
* "640 digits should be enough for anyone." - gps |
| 40 |
* fits a ~2126 bit decimal number. |
| 41 |
*/ |
| 42 |
#define _PY_LONG_MAX_STR_DIGITS_THRESHOLD 640 |
| 43 |
|
| 44 |
#if ((_PY_LONG_DEFAULT_MAX_STR_DIGITS != 0) && \ |
| 45 |
(_PY_LONG_DEFAULT_MAX_STR_DIGITS < _PY_LONG_MAX_STR_DIGITS_THRESHOLD)) |
| 46 |
# error "_PY_LONG_DEFAULT_MAX_STR_DIGITS smaller than threshold." |
| 47 |
#endif |
| 48 |
|
| 49 |
/* runtime lifecycle */ |
| 50 |
|
| 51 |
extern PyStatus _PyLong_InitTypes(PyInterpreterState *); |
| 52 |
extern void _PyLong_FiniTypes(PyInterpreterState *interp); |
| 53 |
|
| 54 |
|
| 55 |
/* other API */ |
| 56 |
|
| 57 |
PyAPI_FUNC(void) _PyLong_ExactDealloc(PyObject *self); |
| 58 |
|
| 59 |
#define _PyLong_SMALL_INTS _Py_SINGLETON(small_ints) |
| 60 |
|
| 61 |
// _PyLong_GetZero() and _PyLong_GetOne() must always be available |
| 62 |
// _PyLong_FromUnsignedChar must always be available |
| 63 |
#if _PY_NSMALLPOSINTS < 257 |
| 64 |
# error "_PY_NSMALLPOSINTS must be greater than or equal to 257" |
| 65 |
#endif |
| 66 |
|
| 67 |
#define _PY_IS_SMALL_INT(val) \ |
| 68 |
(-_PY_NSMALLNEGINTS <= (val) && (val) < _PY_NSMALLPOSINTS) |
| 69 |
|
| 70 |
// Return a reference to the immortal zero singleton. |
| 71 |
// The function cannot return NULL. |
| 72 |
static inline PyObject* _PyLong_GetZero(void) |
| 73 |
{ return (PyObject *)&_PyLong_SMALL_INTS[_PY_NSMALLNEGINTS]; } |
| 74 |
|
| 75 |
// Return a reference to the immortal one singleton. |
| 76 |
// The function cannot return NULL. |
| 77 |
static inline PyObject* _PyLong_GetOne(void) |
| 78 |
{ return (PyObject *)&_PyLong_SMALL_INTS[_PY_NSMALLNEGINTS+1]; } |
| 79 |
|
| 80 |
static inline PyObject* _PyLong_FromUnsignedChar(unsigned char i) |
| 81 |
{ |
| 82 |
return (PyObject *)&_PyLong_SMALL_INTS[_PY_NSMALLNEGINTS+i]; |
| 83 |
} |
| 84 |
|
| 85 |
// _PyLong_Frexp returns a double x and an exponent e such that the |
| 86 |
// true value is approximately equal to x * 2**e. x is |
| 87 |
// 0.0 if and only if the input is 0 (in which case, e and x are both |
| 88 |
// zeroes); otherwise, 0.5 <= abs(x) < 1.0. |
| 89 |
// Always successful. |
| 90 |
// |
| 91 |
// Export for 'math' shared extension |
| 92 |
PyAPI_DATA(double) _PyLong_Frexp(PyLongObject *a, int64_t *e); |
| 93 |
|
| 94 |
extern PyObject* _PyLong_FromBytes(const char *, Py_ssize_t, int); |
| 95 |
|
| 96 |
// _PyLong_DivmodNear. Given integers a and b, compute the nearest |
| 97 |
// integer q to the exact quotient a / b, rounding to the nearest even integer |
| 98 |
// in the case of a tie. Return (q, r), where r = a - q*b. The remainder r |
| 99 |
// will satisfy abs(r) <= abs(b)/2, with equality possible only if q is |
| 100 |
// even. |
| 101 |
// |
| 102 |
// Export for '_datetime' shared extension. |
| 103 |
PyAPI_DATA(PyObject*) _PyLong_DivmodNear(PyObject *, PyObject *); |
| 104 |
|
| 105 |
// _PyLong_Format: Convert the long to a string object with given base, |
| 106 |
// appending a base prefix of 0[box] if base is 2, 8 or 16. |
| 107 |
// Export for '_tkinter' shared extension. |
| 108 |
PyAPI_DATA(PyObject*) _PyLong_Format(PyObject *obj, int base); |
| 109 |
|
| 110 |
// Export for 'math' shared extension |
| 111 |
PyAPI_DATA(PyObject*) _PyLong_Rshift(PyObject *, int64_t); |
| 112 |
|
| 113 |
// Export for 'math' shared extension |
| 114 |
PyAPI_DATA(PyObject*) _PyLong_Lshift(PyObject *, int64_t); |
| 115 |
|
| 116 |
PyAPI_FUNC(PyObject*) _PyLong_Add(PyLongObject *left, PyLongObject *right); |
| 117 |
PyAPI_FUNC(PyObject*) _PyLong_Multiply(PyLongObject *left, PyLongObject *right); |
| 118 |
PyAPI_FUNC(PyObject*) _PyLong_Subtract(PyLongObject *left, PyLongObject *right); |
| 119 |
|
| 120 |
// Export for 'binascii' shared extension. |
| 121 |
PyAPI_DATA(unsigned char) _PyLong_DigitValue[256]; |
| 122 |
|
| 123 |
/* Format the object based on the format_spec, as defined in PEP 3101 |
| 124 |
(Advanced String Formatting). */ |
| 125 |
extern int _PyLong_FormatAdvancedWriter( |
| 126 |
_PyUnicodeWriter *writer, |
| 127 |
PyObject *obj, |
| 128 |
PyObject *format_spec, |
| 129 |
Py_ssize_t start, |
| 130 |
Py_ssize_t end); |
| 131 |
|
| 132 |
extern int _PyLong_FormatWriter( |
| 133 |
_PyUnicodeWriter *writer, |
| 134 |
PyObject *obj, |
| 135 |
int base, |
| 136 |
int alternate); |
| 137 |
|
| 138 |
extern char* _PyLong_FormatBytesWriter( |
| 139 |
_PyBytesWriter *writer, |
| 140 |
char *str, |
| 141 |
PyObject *obj, |
| 142 |
int base, |
| 143 |
int alternate); |
| 144 |
|
| 145 |
// Argument converters used by Argument Clinic |
| 146 |
|
| 147 |
// Export for 'select' shared extension (Argument Clinic code) |
| 148 |
PyAPI_FUNC(int) _PyLong_UnsignedShort_Converter(PyObject *, void *); |
| 149 |
|
| 150 |
// Export for '_testclinic' shared extension (Argument Clinic code) |
| 151 |
PyAPI_FUNC(int) _PyLong_UnsignedInt_Converter(PyObject *, void *); |
| 152 |
|
| 153 |
// Export for '_blake2' shared extension (Argument Clinic code) |
| 154 |
PyAPI_FUNC(int) _PyLong_UnsignedLong_Converter(PyObject *, void *); |
| 155 |
|
| 156 |
// Export for '_blake2' shared extension (Argument Clinic code) |
| 157 |
PyAPI_FUNC(int) _PyLong_UnsignedLongLong_Converter(PyObject *, void *); |
| 158 |
|
| 159 |
// Export for '_testclinic' shared extension (Argument Clinic code) |
| 160 |
PyAPI_FUNC(int) _PyLong_Size_t_Converter(PyObject *, void *); |
| 161 |
|
| 162 |
PyAPI_FUNC(int) _PyLong_UInt8_Converter(PyObject *, void *); |
| 163 |
PyAPI_FUNC(int) _PyLong_UInt16_Converter(PyObject *, void *); |
| 164 |
PyAPI_FUNC(int) _PyLong_UInt32_Converter(PyObject *, void *); |
| 165 |
PyAPI_FUNC(int) _PyLong_UInt64_Converter(PyObject *, void *); |
| 166 |
|
| 167 |
/* Long value tag bits: |
| 168 |
* 0-1: Sign bits value = (1-sign), ie. negative=2, positive=0, zero=1. |
| 169 |
* 2: Set to 1 for the small ints |
| 170 |
* 3+ Unsigned digit count |
| 171 |
*/ |
| 172 |
#define SIGN_MASK 3 |
| 173 |
#define SIGN_ZERO 1 |
| 174 |
#define SIGN_NEGATIVE 2 |
| 175 |
#define NON_SIZE_BITS 3 |
| 176 |
#define IMMORTALITY_BIT_MASK (1 << 2) |
| 177 |
|
| 178 |
/* The functions _PyLong_IsCompact and _PyLong_CompactValue are defined |
| 179 |
* in Include/cpython/longobject.h, since they need to be inline. |
| 180 |
* |
| 181 |
* "Compact" values have at least one bit to spare, |
| 182 |
* so that addition and subtraction can be performed on the values |
| 183 |
* without risk of overflow. |
| 184 |
* |
| 185 |
* The inline functions need tag bits. |
| 186 |
* For readability, rather than do `#define SIGN_MASK _PyLong_SIGN_MASK` |
| 187 |
* we define them to the numbers in both places and then assert that |
| 188 |
* they're the same. |
| 189 |
*/ |
| 190 |
#if SIGN_MASK != _PyLong_SIGN_MASK |
| 191 |
# error "SIGN_MASK does not match _PyLong_SIGN_MASK" |
| 192 |
#endif |
| 193 |
#if NON_SIZE_BITS != _PyLong_NON_SIZE_BITS |
| 194 |
# error "NON_SIZE_BITS does not match _PyLong_NON_SIZE_BITS" |
| 195 |
#endif |
| 196 |
|
| 197 |
/* All *compact" values are guaranteed to fit into |
| 198 |
* a Py_ssize_t with at least one bit to spare. |
| 199 |
* In other words, for 64 bit machines, compact |
| 200 |
* will be signed 63 (or fewer) bit values |
| 201 |
*/ |
| 202 |
|
| 203 |
/* Return 1 if the argument is compact int */ |
| 204 |
static inline int |
| 205 |
_PyLong_IsNonNegativeCompact(const PyLongObject* op) { |
| 206 |
assert(PyLong_Check(op)); |
| 207 |
return ((op->long_value.lv_tag & ~IMMORTALITY_BIT_MASK) <= (1 << NON_SIZE_BITS)); |
| 208 |
} |
| 209 |
|
| 210 |
|
| 211 |
static inline int |
| 212 |
_PyLong_BothAreCompact(const PyLongObject* a, const PyLongObject* b) { |
| 213 |
assert(PyLong_Check(a)); |
| 214 |
assert(PyLong_Check(b)); |
| 215 |
return (a->long_value.lv_tag | b->long_value.lv_tag) < (2 << NON_SIZE_BITS); |
| 216 |
} |
| 217 |
|
| 218 |
static inline bool |
| 219 |
_PyLong_IsZero(const PyLongObject *op) |
| 220 |
{ |
| 221 |
return (op->long_value.lv_tag & SIGN_MASK) == SIGN_ZERO; |
| 222 |
} |
| 223 |
|
| 224 |
static inline bool |
| 225 |
_PyLong_IsNegative(const PyLongObject *op) |
| 226 |
{ |
| 227 |
return (op->long_value.lv_tag & SIGN_MASK) == SIGN_NEGATIVE; |
| 228 |
} |
| 229 |
|
| 230 |
static inline bool |
| 231 |
_PyLong_IsPositive(const PyLongObject *op) |
| 232 |
{ |
| 233 |
return (op->long_value.lv_tag & SIGN_MASK) == 0; |
| 234 |
} |
| 235 |
|
| 236 |
/* Return true if the argument is a small int */ |
| 237 |
static inline bool |
| 238 |
_PyLong_IsSmallInt(const PyLongObject *op) |
| 239 |
{ |
| 240 |
assert(PyLong_Check(op)); |
| 241 |
bool is_small_int = (op->long_value.lv_tag & IMMORTALITY_BIT_MASK) != 0; |
| 242 |
assert(PyLong_CheckExact(op) || (!is_small_int)); |
| 243 |
assert(_Py_IsImmortal(op) || (!is_small_int)); |
| 244 |
assert((_PyLong_IsCompact(op) |
| 245 |
&& _PY_IS_SMALL_INT(_PyLong_CompactValue(op))) |
| 246 |
|| (!is_small_int)); |
| 247 |
return is_small_int; |
| 248 |
} |
| 249 |
|
| 250 |
static inline Py_ssize_t |
| 251 |
_PyLong_DigitCount(const PyLongObject *op) |
| 252 |
{ |
| 253 |
assert(PyLong_Check(op)); |
| 254 |
return (Py_ssize_t)(op->long_value.lv_tag >> NON_SIZE_BITS); |
| 255 |
} |
| 256 |
|
| 257 |
/* Equivalent to _PyLong_DigitCount(op) * _PyLong_NonCompactSign(op) */ |
| 258 |
static inline Py_ssize_t |
| 259 |
_PyLong_SignedDigitCount(const PyLongObject *op) |
| 260 |
{ |
| 261 |
assert(PyLong_Check(op)); |
| 262 |
Py_ssize_t sign = 1 - (op->long_value.lv_tag & SIGN_MASK); |
| 263 |
return sign * (Py_ssize_t)(op->long_value.lv_tag >> NON_SIZE_BITS); |
| 264 |
} |
| 265 |
|
| 266 |
static inline int |
| 267 |
_PyLong_CompactSign(const PyLongObject *op) |
| 268 |
{ |
| 269 |
assert(PyLong_Check(op)); |
| 270 |
assert(_PyLong_IsCompact((PyLongObject *)op)); |
| 271 |
return 1 - (op->long_value.lv_tag & SIGN_MASK); |
| 272 |
} |
| 273 |
|
| 274 |
static inline int |
| 275 |
_PyLong_NonCompactSign(const PyLongObject *op) |
| 276 |
{ |
| 277 |
assert(PyLong_Check(op)); |
| 278 |
assert(!_PyLong_IsCompact((PyLongObject *)op)); |
| 279 |
return 1 - (op->long_value.lv_tag & SIGN_MASK); |
| 280 |
} |
| 281 |
|
| 282 |
/* Do a and b have the same sign? */ |
| 283 |
static inline int |
| 284 |
_PyLong_SameSign(const PyLongObject *a, const PyLongObject *b) |
| 285 |
{ |
| 286 |
return (a->long_value.lv_tag & SIGN_MASK) == (b->long_value.lv_tag & SIGN_MASK); |
| 287 |
} |
| 288 |
|
| 289 |
#define TAG_FROM_SIGN_AND_SIZE(sign, size) \ |
| 290 |
((uintptr_t)(1 - (sign)) | ((uintptr_t)(size) << NON_SIZE_BITS)) |
| 291 |
|
| 292 |
static inline void |
| 293 |
_PyLong_SetSignAndDigitCount(PyLongObject *op, int sign, Py_ssize_t size) |
| 294 |
{ |
| 295 |
assert(size >= 0); |
| 296 |
assert(-1 <= sign && sign <= 1); |
| 297 |
assert(sign != 0 || size == 0); |
| 298 |
op->long_value.lv_tag = TAG_FROM_SIGN_AND_SIZE(sign, size); |
| 299 |
} |
| 300 |
|
| 301 |
static inline void |
| 302 |
_PyLong_SetDigitCount(PyLongObject *op, Py_ssize_t size) |
| 303 |
{ |
| 304 |
assert(size >= 0); |
| 305 |
op->long_value.lv_tag = (((size_t)size) << NON_SIZE_BITS) | (op->long_value.lv_tag & SIGN_MASK); |
| 306 |
} |
| 307 |
|
| 308 |
#define NON_SIZE_MASK ~(uintptr_t)((1 << NON_SIZE_BITS) - 1) |
| 309 |
|
| 310 |
static inline void |
| 311 |
_PyLong_FlipSign(PyLongObject *op) |
| 312 |
{ |
| 313 |
assert(!_PyLong_IsSmallInt(op)); |
| 314 |
unsigned int flipped_sign = 2 - (op->long_value.lv_tag & SIGN_MASK); |
| 315 |
op->long_value.lv_tag &= NON_SIZE_MASK; |
| 316 |
op->long_value.lv_tag |= flipped_sign; |
| 317 |
} |
| 318 |
|
| 319 |
#define _PyLong_DIGIT_INIT(val) \ |
| 320 |
{ \ |
| 321 |
.ob_base = _PyObject_HEAD_INIT(&PyLong_Type), \ |
| 322 |
.long_value = { \ |
| 323 |
.lv_tag = TAG_FROM_SIGN_AND_SIZE( \ |
| 324 |
(val) == 0 ? 0 : ((val) < 0 ? -1 : 1), \ |
| 325 |
(val) == 0 ? 0 : 1) | IMMORTALITY_BIT_MASK, \ |
| 326 |
{ ((val) >= 0 ? (val) : -(val)) }, \ |
| 327 |
} \ |
| 328 |
} |
| 329 |
|
| 330 |
#define _PyLong_FALSE_TAG TAG_FROM_SIGN_AND_SIZE(0, 0) |
| 331 |
#define _PyLong_TRUE_TAG TAG_FROM_SIGN_AND_SIZE(1, 1) |
| 332 |
|
| 333 |
#ifdef __cplusplus |
| 334 |
} |
| 335 |
#endif |
| 336 |
#endif /* !Py_INTERNAL_LONG_H */ |