longobject.c revision 3886026beda0ffb87bbf0bf20a96efb8e520e45d
1edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/*********************************************************** 2edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectCopyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam, 3edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectThe Netherlands. 4edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 5edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project All Rights Reserved 6edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 7edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectPermission to use, copy, modify, and distribute this software and its 8edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectdocumentation for any purpose and without fee is hereby granted, 9edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectprovided that the above copyright notice appear in all copies and that 10edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectboth that copyright notice and this permission notice appear in 11edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectsupporting documentation, and that the names of Stichting Mathematisch 12edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectCentrum or CWI or Corporation for National Research Initiatives or 13edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectCNRI not be used in advertising or publicity pertaining to 14edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectdistribution of the software without specific, written prior 15edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectpermission. 16edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 17edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectWhile CWI is the initial source for this software, a modified version 18edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectis made available by the Corporation for National Research Initiatives 19edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project(CNRI) at the Internet address ftp://ftp.python.org. 20edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 21a67932fe6864ac346e7f78b86df11cf6c5344137Mathias AgopianSTICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH 22076b1cc3a9b90aa5b381a1ed268ca0b548444c9bMathias AgopianREGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF 23a67932fe6864ac346e7f78b86df11cf6c5344137Mathias AgopianMERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH 24edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectCENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL 25edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectDAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR 26edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectPROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER 27edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectTORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 28edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectPERFORMANCE OF THIS SOFTWARE. 293330b203039dea366d4981db1408a460134b2d2cMathias Agopian 30edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project******************************************************************/ 319cce325fae8adcf7560a28eef394489f09bad74dMathias Agopian 329cce325fae8adcf7560a28eef394489f09bad74dMathias Agopian/* Long (arbitrary precision) integer object implementation */ 33edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 34edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* XXX The functional organization of this file is terrible */ 35a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 36a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian#include "Python.h" 371f7bec634f19c123410a5155c8d282e177c01930Mathias Agopian#include "longintrepr.h" 38edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include "mymath.h" 39edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 40a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian#include <assert.h> 41edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <ctype.h> 42edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 43edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#define ABS(x) ((x) < 0 ? -(x) : (x)) 44edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 45edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* Forward */ 46edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatic PyLongObject *long_normalize Py_PROTO((PyLongObject *)); 47edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatic PyLongObject *mul1 Py_PROTO((PyLongObject *, wdigit)); 48edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatic PyLongObject *muladd1 Py_PROTO((PyLongObject *, wdigit, wdigit)); 4996f0819f81293076e652792794a961543e6750d7Mathias Agopianstatic PyLongObject *divrem1 Py_PROTO((PyLongObject *, wdigit, digit *)); 5096f0819f81293076e652792794a961543e6750d7Mathias Agopianstatic PyObject *long_format Py_PROTO((PyObject *aa, int base)); 5196f0819f81293076e652792794a961543e6750d7Mathias Agopian 52a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopianstatic int ticker; /* XXX Could be shared with ceval? */ 53a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 54a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian#define SIGCHECK(PyTryBlock) \ 55933389f75814bb62e8153528f9cff2cb329b77dfMathias Agopian if (--ticker < 0) { \ 56a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian ticker = 100; \ 575bf3abefb2745bf0c45b0814cfd44b4682060a6cMathias Agopian if (PyErr_CheckSignals()) { PyTryBlock; } \ 581f7bec634f19c123410a5155c8d282e177c01930Mathias Agopian } 59a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 60d606de6bb6877dc4ab93ec0be0c6bda4a8ee1ce8Mathias Agopian/* Normalize (remove leading zeros from) a long int object. 61b7e930db175c192464cebdeb49eb56cf6dd60114Mathias Agopian Doesn't attempt to free the storage--in most cases, due to the nature 62933389f75814bb62e8153528f9cff2cb329b77dfMathias Agopian of the algorithms used, this could save at most be one word anyway. */ 63edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 64a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopianstatic PyLongObject * 65a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopianlong_normalize(v) 66d606de6bb6877dc4ab93ec0be0c6bda4a8ee1ce8Mathias Agopian register PyLongObject *v; 67d606de6bb6877dc4ab93ec0be0c6bda4a8ee1ce8Mathias Agopian{ 68a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian int j = ABS(v->ob_size); 6996f0819f81293076e652792794a961543e6750d7Mathias Agopian register int i = j; 70a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 71ddc31c3e2bc6ffe66695c385d23e8ccc3c6dad06Mathias Agopian while (i > 0 && v->ob_digit[i-1] == 0) 72a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian --i; 73a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian if (i != j) 74a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian v->ob_size = (v->ob_size < 0) ? -(i) : i; 75a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian return v; 76a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian} 77a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 78a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian/* Allocate a new long int object with size digits. 79a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian Return NULL and set exception if we run out of memory. */ 80a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 81a67932fe6864ac346e7f78b86df11cf6c5344137Mathias AgopianPyLongObject * 82a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian_PyLong_New(size) 83a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian int size; 84a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian{ 85a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size); 86a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian} 87b7e930db175c192464cebdeb49eb56cf6dd60114Mathias Agopian 8896f0819f81293076e652792794a961543e6750d7Mathias Agopian/* Create a new long int object from a C long int */ 89a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 90b7e930db175c192464cebdeb49eb56cf6dd60114Mathias AgopianPyObject * 91118d0245ee0a3b107055782aa8b555404b6f0280Mathias AgopianPyLong_FromLong(ival) 92118d0245ee0a3b107055782aa8b555404b6f0280Mathias Agopian long ival; 9396f0819f81293076e652792794a961543e6750d7Mathias Agopian{ 9496f0819f81293076e652792794a961543e6750d7Mathias Agopian /* Assume a C long fits in at most 5 'digits' */ 95a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian /* Works on both 32- and 64-bit machines */ 963d8063b02e06020c8062addcc9ec49048d3bdb9aJamie Gennis PyLongObject *v = _PyLong_New(5); 973d8063b02e06020c8062addcc9ec49048d3bdb9aJamie Gennis if (v != NULL) { 98579b3f88d03d06b897b778bd11818f5104677d1dMathias Agopian unsigned long t = ival; 99579b3f88d03d06b897b778bd11818f5104677d1dMathias Agopian int i; 100d606de6bb6877dc4ab93ec0be0c6bda4a8ee1ce8Mathias Agopian if (ival < 0) { 101d606de6bb6877dc4ab93ec0be0c6bda4a8ee1ce8Mathias Agopian t = -ival; 102d606de6bb6877dc4ab93ec0be0c6bda4a8ee1ce8Mathias Agopian v->ob_size = -(v->ob_size); 103d606de6bb6877dc4ab93ec0be0c6bda4a8ee1ce8Mathias Agopian } 104dbe6486ca151d0eb1950be0aae347f0eb8ed3442Jamie Gennis for (i = 0; i < 5; i++) { 10548d819a1315f7d1b5abfec9d4fd34fb5aed27b1dMathias Agopian v->ob_digit[i] = (digit) (t & MASK); 106cbb288bfe89f585bf48371bd31b2d4aafa32f32eMathias Agopian t >>= SHIFT; 107a249f2d11249ff37c48119020b797ad437ddef2cJamie Gennis } 108a249f2d11249ff37c48119020b797ad437ddef2cJamie Gennis v = long_normalize(v); 109a249f2d11249ff37c48119020b797ad437ddef2cJamie Gennis } 110a249f2d11249ff37c48119020b797ad437ddef2cJamie Gennis return (PyObject *)v; 111a249f2d11249ff37c48119020b797ad437ddef2cJamie Gennis} 112a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 113edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* Create a new long int object from a C unsigned long int */ 114a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 115a67932fe6864ac346e7f78b86df11cf6c5344137Mathias AgopianPyObject * 116a67932fe6864ac346e7f78b86df11cf6c5344137Mathias AgopianPyLong_FromUnsignedLong(ival) 117a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian unsigned long ival; 118a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian{ 119a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian /* Assume a C long fits in at most 5 'digits' */ 120a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian /* Works on both 32- and 64-bit machines */ 121a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian PyLongObject *v = _PyLong_New(5); 122a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian if (v != NULL) { 123a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian unsigned long t = ival; 124a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian int i; 125a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian for (i = 0; i < 5; i++) { 126a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian v->ob_digit[i] = (digit) (t & MASK); 127a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian t >>= SHIFT; 128a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian } 129a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian v = long_normalize(v); 130a1f47b90ab53af978be45b8bda16c5d084ae66e6Mathias Agopian } 131edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return (PyObject *)v; 132edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 133582270d69db94286a248bd829f1ae6f910d45124Jamie Gennis 134582270d69db94286a248bd829f1ae6f910d45124Jamie Gennis/* Create a new long int object from a C double */ 135582270d69db94286a248bd829f1ae6f910d45124Jamie Gennis 136582270d69db94286a248bd829f1ae6f910d45124Jamie GennisPyObject * 137582270d69db94286a248bd829f1ae6f910d45124Jamie Gennis#ifdef MPW 138f9d932774e06d5122c48b47d8cabd791783f56d2Mathias AgopianPyLong_FromDouble(double dval) 139edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#else 140edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectPyLong_FromDouble(dval) 141401c257fba770a267f637184b1f532b4e03bed20Mathias Agopian double dval; 142edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#endif /* MPW */ 143edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 144edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project PyLongObject *v; 145edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project double frac; 146401c257fba770a267f637184b1f532b4e03bed20Mathias Agopian int i, ndig, expo, neg; 147401c257fba770a267f637184b1f532b4e03bed20Mathias Agopian neg = 0; 148ca99fb8f65f3ea249c56fb6dccefffb54e87696eMathias Agopian if (dval < 0.0) { 149ca99fb8f65f3ea249c56fb6dccefffb54e87696eMathias Agopian neg = 1; 150ca99fb8f65f3ea249c56fb6dccefffb54e87696eMathias Agopian dval = -dval; 151ca99fb8f65f3ea249c56fb6dccefffb54e87696eMathias Agopian } 152ca99fb8f65f3ea249c56fb6dccefffb54e87696eMathias Agopian frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */ 153ca99fb8f65f3ea249c56fb6dccefffb54e87696eMathias Agopian if (expo <= 0) 154ca99fb8f65f3ea249c56fb6dccefffb54e87696eMathias Agopian return PyLong_FromLong(0L); 155ca99fb8f65f3ea249c56fb6dccefffb54e87696eMathias Agopian ndig = (expo-1) / SHIFT + 1; /* Number of 'digits' in result */ 156ca99fb8f65f3ea249c56fb6dccefffb54e87696eMathias Agopian v = _PyLong_New(ndig); 157401c257fba770a267f637184b1f532b4e03bed20Mathias Agopian if (v == NULL) 158401c257fba770a267f637184b1f532b4e03bed20Mathias Agopian return NULL; 159a4b740ed89074cda898a30eb1b029b0d3a5de1a5Mathias Agopian frac = ldexp(frac, (expo-1) % SHIFT + 1); 160a4b740ed89074cda898a30eb1b029b0d3a5de1a5Mathias Agopian for (i = ndig; --i >= 0; ) { 161cbb288bfe89f585bf48371bd31b2d4aafa32f32eMathias Agopian long bits = (long)frac; 162eff062c49e858d0dd94a1e57f6115bc84dba103eMathias Agopian v->ob_digit[i] = (digit) bits; 1633330b203039dea366d4981db1408a460134b2d2cMathias Agopian frac = frac - (double)bits; 16416f0453fee84c6aad59fe0d1c7d36f061d46cffcGlenn Kasten frac = ldexp(frac, SHIFT); 165a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian } 166a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian if (neg) 167a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian v->ob_size = -(v->ob_size); 168a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian return (PyObject *)v; 169a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian} 170ca99fb8f65f3ea249c56fb6dccefffb54e87696eMathias Agopian 171401c257fba770a267f637184b1f532b4e03bed20Mathias Agopian/* Get a C long int from a long int object. 172401c257fba770a267f637184b1f532b4e03bed20Mathias Agopian Returns -1 and sets an error condition if overflow occurs. */ 173401c257fba770a267f637184b1f532b4e03bed20Mathias Agopian 174401c257fba770a267f637184b1f532b4e03bed20Mathias Agopianlong 175401c257fba770a267f637184b1f532b4e03bed20Mathias AgopianPyLong_AsLong(vv) 176edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project PyObject *vv; 177edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 178edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* This version by Tim Peters */ 179a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian register PyLongObject *v; 180a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian unsigned long x, prev; 181a537c0f42e8077baafcbc65844adf1ec8397c040Mathias Agopian int i, sign; 182a537c0f42e8077baafcbc65844adf1ec8397c040Mathias Agopian 183a537c0f42e8077baafcbc65844adf1ec8397c040Mathias Agopian if (vv == NULL || !PyLong_Check(vv)) { 184a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian PyErr_BadInternalCall(); 185a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian return -1; 186a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian } 187a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian v = (PyLongObject *)vv; 188a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian i = v->ob_size; 189a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian sign = 1; 190a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian x = 0; 19129a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian if (i < 0) { 19229a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian sign = -1; 19329a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian i = -(i); 19429a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian } 19529a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian while (--i >= 0) { 196d992db3827016388e8069f5793b031153d423501Mathias Agopian prev = x; 19729a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian x = (x << SHIFT) + v->ob_digit[i]; 19829a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian if ((x >> SHIFT) != prev) 19929a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian goto overflow; 20029a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian } 201d992db3827016388e8069f5793b031153d423501Mathias Agopian /* Haven't lost any bits, but if the sign bit is set we're in 20229a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian * trouble *unless* this is the min negative number. So, 20329a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian * trouble iff sign bit set && (positive || some bit set other 20429a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian * than the sign bit). 20529a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian */ 206a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian if ((long)x < 0 && (sign > 0 || (x << 1) != 0)) 20729a367bb7c14c916e991a6a0028727bd06c1e16eMathias Agopian goto overflow; 208a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian return (long)x * sign; 209a537c0f42e8077baafcbc65844adf1ec8397c040Mathias Agopian 210a537c0f42e8077baafcbc65844adf1ec8397c040Mathias Agopian overflow: 211a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian PyErr_SetString(PyExc_OverflowError, 212f345069099a13f0c2dd91f1fa92786643e4becb0Mathias Agopian "long int too long to convert"); 213a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian return -1; 214a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian} 215a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 216a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian/* Get a C long int from a long int object. 217a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian Returns -1 and sets an error condition if overflow occurs. */ 218f345069099a13f0c2dd91f1fa92786643e4becb0Mathias Agopian 219c7f3381c3b2945e441747130eae88214435d0819Mathias Agopianunsigned long 220f345069099a13f0c2dd91f1fa92786643e4becb0Mathias AgopianPyLong_AsUnsignedLong(vv) 221f345069099a13f0c2dd91f1fa92786643e4becb0Mathias Agopian PyObject *vv; 222e8067a7d996105d9e03d75e6593e28b795fa9336Mathias Agopian{ 223e8067a7d996105d9e03d75e6593e28b795fa9336Mathias Agopian register PyLongObject *v; 224e8067a7d996105d9e03d75e6593e28b795fa9336Mathias Agopian unsigned long x, prev; 225e8067a7d996105d9e03d75e6593e28b795fa9336Mathias Agopian int i; 226e8067a7d996105d9e03d75e6593e28b795fa9336Mathias Agopian 227e8067a7d996105d9e03d75e6593e28b795fa9336Mathias Agopian if (vv == NULL || !PyLong_Check(vv)) { 228e8067a7d996105d9e03d75e6593e28b795fa9336Mathias Agopian PyErr_BadInternalCall(); 229f345069099a13f0c2dd91f1fa92786643e4becb0Mathias Agopian return (unsigned long) -1; 230a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian } 231a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian v = (PyLongObject *)vv; 232c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian i = v->ob_size; 233c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian x = 0; 234c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian if (i < 0) { 235c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian PyErr_SetString(PyExc_OverflowError, 236c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian "can't convert negative value to unsigned long"); 237c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian return (unsigned long) -1; 238c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian } 239c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian while (--i >= 0) { 240c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian prev = x; 241c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian x = (x << SHIFT) + v->ob_digit[i]; 242c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian if ((x >> SHIFT) != prev) { 243c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian PyErr_SetString(PyExc_OverflowError, 244c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian "long int too long to convert"); 245edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return (unsigned long) -1; 246edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 247a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian } 248edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return x; 249179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian} 250179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian 251179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian/* Get a C double from a long int object. */ 252179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian 253179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopiandouble 254179169e88e05261196b76d7ddf94aa870aafaf9aMathias AgopianPyLong_AsDouble(vv) 255179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian PyObject *vv; 256179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian{ 257179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian register PyLongObject *v; 258f7ae69d4bd292110da976c8ae766a8ef083d731fMathias Agopian double x; 259f7ae69d4bd292110da976c8ae766a8ef083d731fMathias Agopian double multiplier = (double) (1L << SHIFT); 260179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian int i, sign; 261179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian 262179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian if (vv == NULL || !PyLong_Check(vv)) { 263179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian PyErr_BadInternalCall(); 264179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian return -1; 265179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian } 266179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian v = (PyLongObject *)vv; 267179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian i = v->ob_size; 268179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian sign = 1; 269179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian x = 0.0; 2700a91775c4df380d6a5b7f3ccad5127388ac01306Mathias Agopian if (i < 0) { 271179169e88e05261196b76d7ddf94aa870aafaf9aMathias Agopian sign = -1; 272edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project i = -(i); 273edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 274a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian while (--i >= 0) { 2759575f60722f7a4f54384fe0be6938a8de48dc23aJamie Gennis x = x*multiplier + (double)v->ob_digit[i]; 276c492e67810814bf86301abffe1d31598b775cf45Mathias Agopian } 277c492e67810814bf86301abffe1d31598b775cf45Mathias Agopian return x * sign; 2789575f60722f7a4f54384fe0be6938a8de48dc23aJamie Gennis} 2799575f60722f7a4f54384fe0be6938a8de48dc23aJamie Gennis 280c492e67810814bf86301abffe1d31598b775cf45Mathias Agopian/* Create a new long (or int) object from a C pointer */ 2819575f60722f7a4f54384fe0be6938a8de48dc23aJamie Gennis 282c492e67810814bf86301abffe1d31598b775cf45Mathias AgopianPyObject * 283c492e67810814bf86301abffe1d31598b775cf45Mathias AgopianPyLong_FromVoidPtr(p) 2849575f60722f7a4f54384fe0be6938a8de48dc23aJamie Gennis void *p; 2859575f60722f7a4f54384fe0be6938a8de48dc23aJamie Gennis{ 2869575f60722f7a4f54384fe0be6938a8de48dc23aJamie Gennis#if SIZEOF_VOID_P == SIZEOF_LONG 287c492e67810814bf86301abffe1d31598b775cf45Mathias Agopian return PyInt_FromLong((long)p); 288c492e67810814bf86301abffe1d31598b775cf45Mathias Agopian#else 289a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian /* optimize null pointers */ 290c492e67810814bf86301abffe1d31598b775cf45Mathias Agopian if ( p == NULL ) 2919575f60722f7a4f54384fe0be6938a8de48dc23aJamie Gennis return PyInt_FromLong(0); 2929575f60722f7a4f54384fe0be6938a8de48dc23aJamie Gennis 2939575f60722f7a4f54384fe0be6938a8de48dc23aJamie Gennis /* we can assume that HAVE_LONG_LONG is true. if not, then the 294c492e67810814bf86301abffe1d31598b775cf45Mathias Agopian configuration process should have bailed (having big pointers 295c492e67810814bf86301abffe1d31598b775cf45Mathias Agopian without long longs seems non-sensical) */ 296a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian return PyLong_FromLongLong((LONG_LONG)p); 297a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian#endif /* SIZEOF_VOID_P == SIZEOF_LONG */ 298a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian} 299a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 300c492e67810814bf86301abffe1d31598b775cf45Mathias Agopian/* Get a C pointer from a long object (or an int object in some cases) */ 301c492e67810814bf86301abffe1d31598b775cf45Mathias Agopian 302edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid * 303edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectPyLong_AsVoidPtr(vv) 304ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold PyObject *vv; 305ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold{ 306ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold /* This function will allow int or long objects. If vv is neither, 307ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold then the PyLong_AsLong*() functions will raise the exception: 308ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold PyExc_SystemError, "bad argument to internal function" 309ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold */ 310ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold 311a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian#if SIZEOF_VOID_P == SIZEOF_LONG 312ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold long x; 313a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 314a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian if ( PyInt_Check(vv) ) 315ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold x = PyInt_AS_LONG(vv); 316a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian else 317a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian x = PyLong_AsLong(vv); 318a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian#else 319a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian /* we can assume that HAVE_LONG_LONG is true. if not, then the 320ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold configuration process should have bailed (having big pointers 321ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold without long longs seems non-sensical) */ 322ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold LONG_LONG x; 323a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 324a7f669256f93a593c723f05784ef04d3c7d052bbMathias Agopian if ( PyInt_Check(vv) ) 325a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian x = PyInt_AS_LONG(vv); 326a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian else 327db5230f4441fa8f120f15bdd6fcfc6e75d9c27d0Jamie Gennis x = PyLong_AsLongLong(vv); 328a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian#endif /* SIZEOF_VOID_P == SIZEOF_LONG */ 329db5230f4441fa8f120f15bdd6fcfc6e75d9c27d0Jamie Gennis 330a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian if (x == -1 && PyErr_Occurred()) 331a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian return NULL; 332a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian return (void *)x; 333a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian} 334a7f669256f93a593c723f05784ef04d3c7d052bbMathias Agopian 335a7f669256f93a593c723f05784ef04d3c7d052bbMathias Agopian#ifdef HAVE_LONG_LONG 3367a4d0dfd43558c299e6af6c4910ef76db9db3172Jamie Gennis/* 3377a4d0dfd43558c299e6af6c4910ef76db9db3172Jamie Gennis * LONG_LONG support by Chris Herborth (chrish@qnx.com) 338a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian * 3397a4d0dfd43558c299e6af6c4910ef76db9db3172Jamie Gennis * For better or worse :-), I tried to follow the coding style already 3407a4d0dfd43558c299e6af6c4910ef76db9db3172Jamie Gennis * here. 3417a4d0dfd43558c299e6af6c4910ef76db9db3172Jamie Gennis */ 342b5b7f260da2c1a2a82e0311e2015d49a82f43667Mathias Agopian 343edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#ifdef HAVE_LIMITS_H 344edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <limits.h> 345edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#endif 346edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 347edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* Hopefully this is portable... */ 348a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian#ifndef LONG_MAX 349a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian#define LONG_MAX 2147483647L 350a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian#endif 351a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian#ifndef ULONG_MAX 352cbb288bfe89f585bf48371bd31b2d4aafa32f32eMathias Agopian#define ULONG_MAX 4294967295U 353edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#endif 3543fbce7c56082e4e0d23f1c1c89983d3841853ed7Mathias Agopian#ifndef LONGLONG_MAX 355a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian#define LONGLONG_MAX 9223372036854775807LL 3563fbce7c56082e4e0d23f1c1c89983d3841853ed7Mathias Agopian#endif 357a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian#ifndef ULONGLONG_MAX 358a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian#define ULONGLONG_MAX 0xffffffffffffffffULL 359a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian#endif 3603fbce7c56082e4e0d23f1c1c89983d3841853ed7Mathias Agopian 361a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian/* Create a new long int object from a C LONG_LONG int */ 362a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian 363a138f89c5e78b7e8994823e97d6e860869762837Mathias AgopianPyObject * 364a138f89c5e78b7e8994823e97d6e860869762837Mathias AgopianPyLong_FromLongLong(ival) 365a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian LONG_LONG ival; 366a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian{ 367a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian#if SIZEOF_LONG_LONG == SIZEOF_LONG 368a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian /* In case the compiler is faking it. */ 369a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian return PyLong_FromLong( (long)ival ); 370a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian#else 371a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian if( ival <= (LONG_LONG)LONG_MAX ) { 372a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian return PyLong_FromLong( (long)ival ); 373edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 374caa600c4a1af1eefd108cf2ec3d86068af35111fMathias Agopian else if( ival <= (unsigned LONG_LONG)ULONG_MAX ) { 375a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian return PyLong_FromUnsignedLong( (unsigned long)ival ); 376a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian } 377a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian else { 378a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian /* Assume a C LONG_LONG fits in at most 10 'digits'. 379a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian * Should be OK if we're assuming long fits in 5. 380a138f89c5e78b7e8994823e97d6e860869762837Mathias Agopian */ 3812a0d5b608447a880beff5149805425f02691442bJamie Gennis PyLongObject *v = _PyLong_New(10); 3822a0d5b608447a880beff5149805425f02691442bJamie Gennis 3832a0d5b608447a880beff5149805425f02691442bJamie Gennis if (v != NULL) { 3842a0d5b608447a880beff5149805425f02691442bJamie Gennis unsigned LONG_LONG t = ival; 3852a0d5b608447a880beff5149805425f02691442bJamie Gennis int i; 386edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (ival < 0) { 387cbb288bfe89f585bf48371bd31b2d4aafa32f32eMathias Agopian t = -ival; 388edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project v->ob_size = -(v->ob_size); 389edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 390edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 391edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project for (i = 0; i < 10; i++) { 392edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project v->ob_digit[i] = (digit) (t & MASK); 393edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project t >>= SHIFT; 394edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 395edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 396edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project v = long_normalize(v); 397edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 398edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 399a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian return (PyObject *)v; 400933389f75814bb62e8153528f9cff2cb329b77dfMathias Agopian } 401a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian#endif 402a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian} 403a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 404a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian/* Create a new long int object from a C unsigned LONG_LONG int */ 405a138f89c5e78b7e8994823e97d6e860869762837Mathias AgopianPyObject * 406a138f89c5e78b7e8994823e97d6e860869762837Mathias AgopianPyLong_FromUnsignedLongLong(ival) 407edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project unsigned LONG_LONG ival; 408edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 409edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#if SIZEOF_LONG_LONG == SIZEOF_LONG 410edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* In case the compiler is faking it. */ 411edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return PyLong_FromUnsignedLong( (unsigned long)ival ); 412edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#else 4133d8063b02e06020c8062addcc9ec49048d3bdb9aJamie Gennis if( ival <= (unsigned LONG_LONG)ULONG_MAX ) { 414351a513b12622781de9580b3c96fd0a8578b563bJamie Gennis return PyLong_FromUnsignedLong( (unsigned long)ival ); 415db5230f4441fa8f120f15bdd6fcfc6e75d9c27d0Jamie Gennis } 416351a513b12622781de9580b3c96fd0a8578b563bJamie Gennis else { 417db5230f4441fa8f120f15bdd6fcfc6e75d9c27d0Jamie Gennis /* Assume a C long fits in at most 10 'digits'. */ 4183d8063b02e06020c8062addcc9ec49048d3bdb9aJamie Gennis PyLongObject *v = _PyLong_New(10); 4193d8063b02e06020c8062addcc9ec49048d3bdb9aJamie Gennis 4203d8063b02e06020c8062addcc9ec49048d3bdb9aJamie Gennis if (v != NULL) { 4213d8063b02e06020c8062addcc9ec49048d3bdb9aJamie Gennis unsigned LONG_LONG t = ival; 4223d8063b02e06020c8062addcc9ec49048d3bdb9aJamie Gennis int i; 423a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian for (i = 0; i < 10; i++) { 424a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian v->ob_digit[i] = (digit) (t & MASK); 425a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian t >>= SHIFT; 426a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian } 427a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 428d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian v = long_normalize(v); 429351a513b12622781de9580b3c96fd0a8578b563bJamie Gennis } 430351a513b12622781de9580b3c96fd0a8578b563bJamie Gennis 431ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold return (PyObject *)v; 432a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian } 433a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian#endif 434933389f75814bb62e8153528f9cff2cb329b77dfMathias Agopian} 435933389f75814bb62e8153528f9cff2cb329b77dfMathias Agopian 436933389f75814bb62e8153528f9cff2cb329b77dfMathias Agopian/* Get a C LONG_LONG int from a long int object. 437933389f75814bb62e8153528f9cff2cb329b77dfMathias Agopian Returns -1 and sets an error condition if overflow occurs. */ 438933389f75814bb62e8153528f9cff2cb329b77dfMathias Agopian 439a67932fe6864ac346e7f78b86df11cf6c5344137Mathias AgopianLONG_LONG 440a67932fe6864ac346e7f78b86df11cf6c5344137Mathias AgopianPyLong_AsLongLong(vv) 441933389f75814bb62e8153528f9cff2cb329b77dfMathias Agopian PyObject *vv; 442a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian{ 443a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian#if SIZEOF_LONG_LONG == SIZEOF_LONG 444da9584dc295cc5e6d0b49a97c1e45159249d650bMathias Agopian /* In case the compiler is faking it. */ 445c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian return (LONG_LONG)PyLong_AsLong( vv ); 446c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian#else 447c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian register PyLongObject *v; 448c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian LONG_LONG x, prev; 449c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian int i, sign; 450c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian 451c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian if (vv == NULL || !PyLong_Check(vv)) { 452351a513b12622781de9580b3c96fd0a8578b563bJamie Gennis PyErr_BadInternalCall(); 453351a513b12622781de9580b3c96fd0a8578b563bJamie Gennis return -1; 454351a513b12622781de9580b3c96fd0a8578b563bJamie Gennis } 455351a513b12622781de9580b3c96fd0a8578b563bJamie Gennis 456351a513b12622781de9580b3c96fd0a8578b563bJamie Gennis v = (PyLongObject *)vv; 457c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian i = v->ob_size; 458c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian sign = 1; 459c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian x = 0; 460c7f3381c3b2945e441747130eae88214435d0819Mathias Agopian 461351a513b12622781de9580b3c96fd0a8578b563bJamie Gennis if (i < 0) { 462db5230f4441fa8f120f15bdd6fcfc6e75d9c27d0Jamie Gennis sign = -1; 463ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold i = -(i); 464ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold } 465ac45e6bff1b41acd35c981291b37b23f8e083ceeEric Hassold 466f7ae69d4bd292110da976c8ae766a8ef083d731fMathias Agopian while (--i >= 0) { 467f7ae69d4bd292110da976c8ae766a8ef083d731fMathias Agopian prev = x; 468d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian x = (x << SHIFT) + v->ob_digit[i]; 469d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian if ((x >> SHIFT) != prev) { 470d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian PyErr_SetString(PyExc_OverflowError, 471a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian "long int too long to convert"); 472a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian return -1; 473a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian } 474a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian } 47597c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopian 47697c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopian return x * sign; 477df3e0b934f2822ea0a334777e51e681f04a64d7cMathias Agopian#endif 47897c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopian} 47997c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopian 48097c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopianunsigned LONG_LONG 48197c602c5af5f3ffd69009bf496d86347b71a2b4cMathias AgopianPyLong_AsUnsignedLongLong(vv) 48297c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopian PyObject *vv; 48397c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopian{ 48497c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopian#if SIZEOF_LONG_LONG == 4 48597c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopian /* In case the compiler is faking it. */ 48697c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopian return (unsigned LONG_LONG)PyLong_AsUnsignedLong( vv ); 487d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian#else 488d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian register PyLongObject *v; 489d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian unsigned LONG_LONG x, prev; 490d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian int i; 491d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian 492d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian if (vv == NULL || !PyLong_Check(vv)) { 493d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian PyErr_BadInternalCall(); 494d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian return (unsigned LONG_LONG) -1; 495d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian } 496d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian 497d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian v = (PyLongObject *)vv; 498d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian i = v->ob_size; 499d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian x = 0; 500d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian 501d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian if (i < 0) { 502d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian PyErr_SetString(PyExc_OverflowError, 503d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian "can't convert negative value to unsigned long"); 504d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian return (unsigned LONG_LONG) -1; 505d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian } 5068f2d50521653f24c2a5e77b627dc015c7fbd656aMathias Agopian 50797c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopian while (--i >= 0) { 50897c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopian prev = x; 50997c602c5af5f3ffd69009bf496d86347b71a2b4cMathias Agopian x = (x << SHIFT) + v->ob_digit[i]; 5103fbce7c56082e4e0d23f1c1c89983d3841853ed7Mathias Agopian if ((x >> SHIFT) != prev) { 5113fbce7c56082e4e0d23f1c1c89983d3841853ed7Mathias Agopian PyErr_SetString(PyExc_OverflowError, 5123fbce7c56082e4e0d23f1c1c89983d3841853ed7Mathias Agopian "long int too long to convert"); 5133fbce7c56082e4e0d23f1c1c89983d3841853ed7Mathias Agopian return (unsigned LONG_LONG) -1; 5143fbce7c56082e4e0d23f1c1c89983d3841853ed7Mathias Agopian } 5153fbce7c56082e4e0d23f1c1c89983d3841853ed7Mathias Agopian } 5163fbce7c56082e4e0d23f1c1c89983d3841853ed7Mathias Agopian 5173fbce7c56082e4e0d23f1c1c89983d3841853ed7Mathias Agopian return x; 518d343e3d5e3177806205b9452b0b43907e28afd9aMathias Agopian#endif 519e700501d0e888ead9ac6456c0a6fd74d634aa5fbMathias Agopian} 520edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#endif /* HAVE_LONG_LONG */ 521edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 522edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* Multiply by a single digit, ignoring the sign. */ 523edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 524edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatic PyLongObject * 525edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectmul1(a, n) 526edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project PyLongObject *a; 527edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project wdigit n; 528edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 529edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return muladd1(a, n, (digit)0); 530edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 531edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 532edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* Multiply by a single digit and add a single digit, ignoring the sign. */ 533edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 534edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatic PyLongObject * 535edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectmuladd1(a, n, extra) 536edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project PyLongObject *a; 537edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project wdigit n; 538edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project wdigit extra; 539edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 540edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project int size_a = ABS(a->ob_size); 541c61de17f143b5f806c5bab9cc58910a322302b70Mathias Agopian PyLongObject *z = _PyLong_New(size_a+1); 542c61de17f143b5f806c5bab9cc58910a322302b70Mathias Agopian twodigits carry = extra; 5431b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopian int i; 544c61de17f143b5f806c5bab9cc58910a322302b70Mathias Agopian 545c61de17f143b5f806c5bab9cc58910a322302b70Mathias Agopian if (z == NULL) 546edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return NULL; 547edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project for (i = 0; i < size_a; ++i) { 5481b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopian carry += (twodigits)a->ob_digit[i] * n; 5491b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopian z->ob_digit[i] = (digit) (carry & MASK); 5501b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopian carry >>= SHIFT; 5511b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopian } 552a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian z->ob_digit[i] = (digit) carry; 553a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian return long_normalize(z); 5541b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopian} 5551b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopian 5561b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopian/* Divide a long integer by a digit, returning both the quotient 5571b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopian (as function result) and the remainder (through *prem). 558a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian The sign of a is ignored; n should not be zero. */ 5591b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopian 5601b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopianstatic PyLongObject * 5611b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopiandivrem1(a, n, prem) 562ad795baecccf239621cbffa0249c8e855296cae6Mathias Agopian PyLongObject *a; 563a45836466c301d49d8df286b5317dfa99cb83b70Mathias Agopian wdigit n; 564a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian digit *prem; 565a45836466c301d49d8df286b5317dfa99cb83b70Mathias Agopian{ 5661b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopian int size = ABS(a->ob_size); 5671b5e1021b8c9b87113b70d94dfb7b50f8c5b01b8Mathias Agopian PyLongObject *z; 568d606de6bb6877dc4ab93ec0be0c6bda4a8ee1ce8Mathias Agopian int i; 569a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian twodigits rem = 0; 570a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian 571bb641244d7d73312dc65b8e338df18b22e335107Mathias Agopian assert(n > 0 && n <= MASK); 572d606de6bb6877dc4ab93ec0be0c6bda4a8ee1ce8Mathias Agopian z = _PyLong_New(size); 573d606de6bb6877dc4ab93ec0be0c6bda4a8ee1ce8Mathias Agopian if (z == NULL) 574a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian return NULL; 575b5b7f260da2c1a2a82e0311e2015d49a82f43667Mathias Agopian for (i = size; --i >= 0; ) { 576a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian rem = (rem << SHIFT) + a->ob_digit[i]; 577a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian z->ob_digit[i] = (digit) (rem/n); 578a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian rem %= n; 579a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian } 580b5b7f260da2c1a2a82e0311e2015d49a82f43667Mathias Agopian *prem = (digit) rem; 5813599bf2c0727bc33e8136f5163eee6f398545e05Jamie Gennis return long_normalize(z); 582a67932fe6864ac346e7f78b86df11cf6c5344137Mathias Agopian} 583b5b7f260da2c1a2a82e0311e2015d49a82f43667Mathias Agopian 584b5b7f260da2c1a2a82e0311e2015d49a82f43667Mathias Agopian/* Convert a long int object to a string, using a given conversion base. 585a45836466c301d49d8df286b5317dfa99cb83b70Mathias Agopian Return a string object. 586a45836466c301d49d8df286b5317dfa99cb83b70Mathias Agopian If base is 8 or 16, add the proper prefix '0' or '0x'. 587a45836466c301d49d8df286b5317dfa99cb83b70Mathias Agopian External linkage: used in bltinmodule.c by hex() and oct(). */ 5888d91b425078083d0e4967dcd8d669d9f7196123aJamie Gennis 589a45836466c301d49d8df286b5317dfa99cb83b70Mathias Agopianstatic PyObject * 590a45836466c301d49d8df286b5317dfa99cb83b70Mathias Agopianlong_format(aa, base) 591a45836466c301d49d8df286b5317dfa99cb83b70Mathias Agopian PyObject *aa; 592a45836466c301d49d8df286b5317dfa99cb83b70Mathias Agopian int base; 593a45836466c301d49d8df286b5317dfa99cb83b70Mathias Agopian{ 594a45836466c301d49d8df286b5317dfa99cb83b70Mathias Agopian register PyLongObject *a = (PyLongObject *)aa; 595a45836466c301d49d8df286b5317dfa99cb83b70Mathias Agopian PyStringObject *str; 596edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project int i; 597edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project int size_a = ABS(a->ob_size); 598edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project char *p; 599edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project int bits; 600 char sign = '\0'; 601 602 if (a == NULL || !PyLong_Check(a)) { 603 PyErr_BadInternalCall(); 604 return NULL; 605 } 606 assert(base >= 2 && base <= 36); 607 608 /* Compute a rough upper bound for the length of the string */ 609 i = base; 610 bits = 0; 611 while (i > 1) { 612 ++bits; 613 i >>= 1; 614 } 615 i = 6 + (size_a*SHIFT + bits-1) / bits; 616 str = (PyStringObject *) PyString_FromStringAndSize((char *)0, i); 617 if (str == NULL) 618 return NULL; 619 p = PyString_AS_STRING(str) + i; 620 *p = '\0'; 621 *--p = 'L'; 622 if (a->ob_size < 0) 623 sign = '-'; 624 625 if (a->ob_size == 0) { 626 *--p = '0'; 627 } 628 else if ((base & (base - 1)) == 0) { 629 /* JRH: special case for power-of-2 bases */ 630 twodigits temp = a->ob_digit[0]; 631 int bitsleft = SHIFT; 632 int rem; 633 int last = abs(a->ob_size); 634 int basebits = 1; 635 i = base; 636 while ((i >>= 1) > 1) ++basebits; 637 638 i = 0; 639 for (;;) { 640 while (bitsleft >= basebits) { 641 if ((temp == 0) && (i >= last - 1)) break; 642 rem = temp & (base - 1); 643 if (rem < 10) 644 rem += '0'; 645 else 646 rem += 'A' - 10; 647 assert(p > PyString_AS_STRING(str)); 648 *--p = (char) rem; 649 bitsleft -= basebits; 650 temp >>= basebits; 651 } 652 if (++i >= last) { 653 if (temp == 0) break; 654 bitsleft = 99; 655 /* loop again to pick up final digits */ 656 } 657 else { 658 temp = (a->ob_digit[i] << bitsleft) | temp; 659 bitsleft += SHIFT; 660 } 661 } 662 } 663 else { 664 Py_INCREF(a); 665 do { 666 digit rem; 667 PyLongObject *temp = divrem1(a, (digit)base, &rem); 668 if (temp == NULL) { 669 Py_DECREF(a); 670 Py_DECREF(str); 671 return NULL; 672 } 673 if (rem < 10) 674 rem += '0'; 675 else 676 rem += 'A'-10; 677 assert(p > PyString_AS_STRING(str)); 678 *--p = (char) rem; 679 Py_DECREF(a); 680 a = temp; 681 SIGCHECK({ 682 Py_DECREF(a); 683 Py_DECREF(str); 684 return NULL; 685 }) 686 } while (ABS(a->ob_size) != 0); 687 Py_DECREF(a); 688 } 689 690 if (base == 8) { 691 if (size_a != 0) 692 *--p = '0'; 693 } 694 else if (base == 16) { 695 *--p = 'x'; 696 *--p = '0'; 697 } 698 else if (base != 10) { 699 *--p = '#'; 700 *--p = '0' + base%10; 701 if (base > 10) 702 *--p = '0' + base/10; 703 } 704 if (sign) 705 *--p = sign; 706 if (p != PyString_AS_STRING(str)) { 707 char *q = PyString_AS_STRING(str); 708 assert(p > q); 709 do { 710 } while ((*q++ = *p++) != '\0'); 711 q--; 712 _PyString_Resize((PyObject **)&str, 713 (int) (q - PyString_AS_STRING(str))); 714 } 715 return (PyObject *)str; 716} 717 718#if 0 719/* Convert a string to a long int object, in a given base. 720 Base zero implies a default depending on the number. 721 External linkage: used in compile.c and stropmodule.c. */ 722 723PyObject * 724long_scan(str, base) 725 char *str; 726 int base; 727{ 728 return PyLong_FromString(str, (char **)NULL, base); 729} 730#endif 731 732PyObject * 733PyLong_FromString(str, pend, base) 734 char *str; 735 char **pend; 736 int base; 737{ 738 int sign = 1; 739 char *start; 740 PyLongObject *z; 741 742 if ((base != 0 && base < 2) || base > 36) { 743 PyErr_SetString(PyExc_ValueError, 744 "invalid base for long literal"); 745 return NULL; 746 } 747 while (*str != '\0' && isspace(Py_CHARMASK(*str))) 748 str++; 749 if (*str == '+') 750 ++str; 751 else if (*str == '-') { 752 ++str; 753 sign = -1; 754 } 755 while (*str != '\0' && isspace(Py_CHARMASK(*str))) 756 str++; 757 if (base == 0) { 758 if (str[0] != '0') 759 base = 10; 760 else if (str[1] == 'x' || str[1] == 'X') 761 base = 16; 762 else 763 base = 8; 764 } 765 if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X')) 766 str += 2; 767 z = _PyLong_New(0); 768 start = str; 769 for ( ; z != NULL; ++str) { 770 int k = -1; 771 PyLongObject *temp; 772 773 if (*str <= '9') 774 k = *str - '0'; 775 else if (*str >= 'a') 776 k = *str - 'a' + 10; 777 else if (*str >= 'A') 778 k = *str - 'A' + 10; 779 if (k < 0 || k >= base) 780 break; 781 temp = muladd1(z, (digit)base, (digit)k); 782 Py_DECREF(z); 783 z = temp; 784 } 785 if (z == NULL) 786 return NULL; 787 if (str == start) { 788 PyErr_SetString(PyExc_ValueError, 789 "no digits in long int constant"); 790 return NULL; 791 } 792 if (sign < 0 && z != NULL && z->ob_size != 0) 793 z->ob_size = -(z->ob_size); 794 if (pend) 795 *pend = str; 796 return (PyObject *) z; 797} 798 799static PyLongObject *x_divrem 800 Py_PROTO((PyLongObject *, PyLongObject *, PyLongObject **)); 801static PyObject *long_pos Py_PROTO((PyLongObject *)); 802static int long_divrem Py_PROTO((PyLongObject *, PyLongObject *, 803 PyLongObject **, PyLongObject **)); 804 805/* Long division with remainder, top-level routine */ 806 807static int 808long_divrem(a, b, pdiv, prem) 809 PyLongObject *a, *b; 810 PyLongObject **pdiv; 811 PyLongObject **prem; 812{ 813 int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); 814 PyLongObject *z; 815 816 if (size_b == 0) { 817 PyErr_SetString(PyExc_ZeroDivisionError, 818 "long division or modulo"); 819 return -1; 820 } 821 if (size_a < size_b || 822 (size_a == size_b && 823 a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) { 824 /* |a| < |b|. */ 825 *pdiv = _PyLong_New(0); 826 Py_INCREF(a); 827 *prem = (PyLongObject *) a; 828 return 0; 829 } 830 if (size_b == 1) { 831 digit rem = 0; 832 z = divrem1(a, b->ob_digit[0], &rem); 833 if (z == NULL) 834 return -1; 835 *prem = (PyLongObject *) PyLong_FromLong((long)rem); 836 } 837 else { 838 z = x_divrem(a, b, prem); 839 if (z == NULL) 840 return -1; 841 } 842 /* Set the signs. 843 The quotient z has the sign of a*b; 844 the remainder r has the sign of a, 845 so a = b*z + r. */ 846 if ((a->ob_size < 0) != (b->ob_size < 0)) 847 z->ob_size = -(z->ob_size); 848 if (a->ob_size < 0 && (*prem)->ob_size != 0) 849 (*prem)->ob_size = -((*prem)->ob_size); 850 *pdiv = z; 851 return 0; 852} 853 854/* Unsigned long division with remainder -- the algorithm */ 855 856static PyLongObject * 857x_divrem(v1, w1, prem) 858 PyLongObject *v1, *w1; 859 PyLongObject **prem; 860{ 861 int size_v = ABS(v1->ob_size), size_w = ABS(w1->ob_size); 862 digit d = (digit) ((twodigits)BASE / (w1->ob_digit[size_w-1] + 1)); 863 PyLongObject *v = mul1(v1, d); 864 PyLongObject *w = mul1(w1, d); 865 PyLongObject *a; 866 int j, k; 867 868 if (v == NULL || w == NULL) { 869 Py_XDECREF(v); 870 Py_XDECREF(w); 871 return NULL; 872 } 873 874 assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */ 875 assert(v->ob_refcnt == 1); /* Since v will be used as accumulator! */ 876 assert(size_w == ABS(w->ob_size)); /* That's how d was calculated */ 877 878 size_v = ABS(v->ob_size); 879 a = _PyLong_New(size_v - size_w + 1); 880 881 for (j = size_v, k = a->ob_size-1; a != NULL && k >= 0; --j, --k) { 882 digit vj = (j >= size_v) ? 0 : v->ob_digit[j]; 883 twodigits q; 884 stwodigits carry = 0; 885 int i; 886 887 SIGCHECK({ 888 Py_DECREF(a); 889 a = NULL; 890 break; 891 }) 892 if (vj == w->ob_digit[size_w-1]) 893 q = MASK; 894 else 895 q = (((twodigits)vj << SHIFT) + v->ob_digit[j-1]) / 896 w->ob_digit[size_w-1]; 897 898 while (w->ob_digit[size_w-2]*q > 899 (( 900 ((twodigits)vj << SHIFT) 901 + v->ob_digit[j-1] 902 - q*w->ob_digit[size_w-1] 903 ) << SHIFT) 904 + v->ob_digit[j-2]) 905 --q; 906 907 for (i = 0; i < size_w && i+k < size_v; ++i) { 908 twodigits z = w->ob_digit[i] * q; 909 digit zz = (digit) (z >> SHIFT); 910 carry += v->ob_digit[i+k] - z 911 + ((twodigits)zz << SHIFT); 912 v->ob_digit[i+k] = carry & MASK; 913 carry = (carry >> SHIFT) - zz; 914 } 915 916 if (i+k < size_v) { 917 carry += v->ob_digit[i+k]; 918 v->ob_digit[i+k] = 0; 919 } 920 921 if (carry == 0) 922 a->ob_digit[k] = (digit) q; 923 else { 924 assert(carry == -1); 925 a->ob_digit[k] = (digit) q-1; 926 carry = 0; 927 for (i = 0; i < size_w && i+k < size_v; ++i) { 928 carry += v->ob_digit[i+k] + w->ob_digit[i]; 929 v->ob_digit[i+k] = carry & MASK; 930 carry >>= SHIFT; 931 } 932 } 933 } /* for j, k */ 934 935 if (a == NULL) 936 *prem = NULL; 937 else { 938 a = long_normalize(a); 939 *prem = divrem1(v, d, &d); 940 /* d receives the (unused) remainder */ 941 if (*prem == NULL) { 942 Py_DECREF(a); 943 a = NULL; 944 } 945 } 946 Py_DECREF(v); 947 Py_DECREF(w); 948 return a; 949} 950 951/* Methods */ 952 953/* Forward */ 954static void long_dealloc Py_PROTO((PyObject *)); 955static PyObject *long_repr Py_PROTO((PyObject *)); 956static int long_compare Py_PROTO((PyLongObject *, PyLongObject *)); 957static long long_hash Py_PROTO((PyLongObject *)); 958 959static PyObject *long_add Py_PROTO((PyLongObject *, PyLongObject *)); 960static PyObject *long_sub Py_PROTO((PyLongObject *, PyLongObject *)); 961static PyObject *long_mul Py_PROTO((PyLongObject *, PyLongObject *)); 962static PyObject *long_div Py_PROTO((PyLongObject *, PyLongObject *)); 963static PyObject *long_mod Py_PROTO((PyLongObject *, PyLongObject *)); 964static PyObject *long_divmod Py_PROTO((PyLongObject *, PyLongObject *)); 965static PyObject *long_pow 966 Py_PROTO((PyLongObject *, PyLongObject *, PyLongObject *)); 967static PyObject *long_neg Py_PROTO((PyLongObject *)); 968static PyObject *long_pos Py_PROTO((PyLongObject *)); 969static PyObject *long_abs Py_PROTO((PyLongObject *)); 970static int long_nonzero Py_PROTO((PyLongObject *)); 971static PyObject *long_invert Py_PROTO((PyLongObject *)); 972static PyObject *long_lshift Py_PROTO((PyLongObject *, PyLongObject *)); 973static PyObject *long_rshift Py_PROTO((PyLongObject *, PyLongObject *)); 974static PyObject *long_and Py_PROTO((PyLongObject *, PyLongObject *)); 975static PyObject *long_xor Py_PROTO((PyLongObject *, PyLongObject *)); 976static PyObject *long_or Py_PROTO((PyLongObject *, PyLongObject *)); 977 978static void 979long_dealloc(v) 980 PyObject *v; 981{ 982 PyMem_DEL(v); 983} 984 985static PyObject * 986long_repr(v) 987 PyObject *v; 988{ 989 return long_format(v, 10); 990} 991 992static int 993long_compare(a, b) 994 PyLongObject *a, *b; 995{ 996 int sign; 997 998 if (a->ob_size != b->ob_size) { 999 if (ABS(a->ob_size) == 0 && ABS(b->ob_size) == 0) 1000 sign = 0; 1001 else 1002 sign = a->ob_size - b->ob_size; 1003 } 1004 else { 1005 int i = ABS(a->ob_size); 1006 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) 1007 ; 1008 if (i < 0) 1009 sign = 0; 1010 else { 1011 sign = (int)a->ob_digit[i] - (int)b->ob_digit[i]; 1012 if (a->ob_size < 0) 1013 sign = -sign; 1014 } 1015 } 1016 return sign < 0 ? -1 : sign > 0 ? 1 : 0; 1017} 1018 1019static long 1020long_hash(v) 1021 PyLongObject *v; 1022{ 1023 long x; 1024 int i, sign; 1025 1026 /* This is designed so that Python ints and longs with the 1027 same value hash to the same value, otherwise comparisons 1028 of mapping keys will turn out weird */ 1029 i = v->ob_size; 1030 sign = 1; 1031 x = 0; 1032 if (i < 0) { 1033 sign = -1; 1034 i = -(i); 1035 } 1036 while (--i >= 0) { 1037 /* Force a 32-bit circular shift */ 1038 x = ((x << SHIFT) & ~MASK) | ((x >> (32-SHIFT)) & MASK); 1039 x += v->ob_digit[i]; 1040 } 1041 x = x * sign; 1042 if (x == -1) 1043 x = -2; 1044 return x; 1045} 1046 1047 1048/* Add the absolute values of two long integers. */ 1049 1050static PyLongObject *x_add Py_PROTO((PyLongObject *, PyLongObject *)); 1051static PyLongObject * 1052x_add(a, b) 1053 PyLongObject *a, *b; 1054{ 1055 int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); 1056 PyLongObject *z; 1057 int i; 1058 digit carry = 0; 1059 1060 /* Ensure a is the larger of the two: */ 1061 if (size_a < size_b) { 1062 { PyLongObject *temp = a; a = b; b = temp; } 1063 { int size_temp = size_a; 1064 size_a = size_b; 1065 size_b = size_temp; } 1066 } 1067 z = _PyLong_New(size_a+1); 1068 if (z == NULL) 1069 return NULL; 1070 for (i = 0; i < size_b; ++i) { 1071 carry += a->ob_digit[i] + b->ob_digit[i]; 1072 z->ob_digit[i] = carry & MASK; 1073 /* The following assumes unsigned shifts don't 1074 propagate the sign bit. */ 1075 carry >>= SHIFT; 1076 } 1077 for (; i < size_a; ++i) { 1078 carry += a->ob_digit[i]; 1079 z->ob_digit[i] = carry & MASK; 1080 carry >>= SHIFT; 1081 } 1082 z->ob_digit[i] = carry; 1083 return long_normalize(z); 1084} 1085 1086/* Subtract the absolute values of two integers. */ 1087 1088static PyLongObject *x_sub Py_PROTO((PyLongObject *, PyLongObject *)); 1089static PyLongObject * 1090x_sub(a, b) 1091 PyLongObject *a, *b; 1092{ 1093 int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); 1094 PyLongObject *z; 1095 int i; 1096 int sign = 1; 1097 digit borrow = 0; 1098 1099 /* Ensure a is the larger of the two: */ 1100 if (size_a < size_b) { 1101 sign = -1; 1102 { PyLongObject *temp = a; a = b; b = temp; } 1103 { int size_temp = size_a; 1104 size_a = size_b; 1105 size_b = size_temp; } 1106 } 1107 else if (size_a == size_b) { 1108 /* Find highest digit where a and b differ: */ 1109 i = size_a; 1110 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) 1111 ; 1112 if (i < 0) 1113 return _PyLong_New(0); 1114 if (a->ob_digit[i] < b->ob_digit[i]) { 1115 sign = -1; 1116 { PyLongObject *temp = a; a = b; b = temp; } 1117 } 1118 size_a = size_b = i+1; 1119 } 1120 z = _PyLong_New(size_a); 1121 if (z == NULL) 1122 return NULL; 1123 for (i = 0; i < size_b; ++i) { 1124 /* The following assumes unsigned arithmetic 1125 works module 2**N for some N>SHIFT. */ 1126 borrow = a->ob_digit[i] - b->ob_digit[i] - borrow; 1127 z->ob_digit[i] = borrow & MASK; 1128 borrow >>= SHIFT; 1129 borrow &= 1; /* Keep only one sign bit */ 1130 } 1131 for (; i < size_a; ++i) { 1132 borrow = a->ob_digit[i] - borrow; 1133 z->ob_digit[i] = borrow & MASK; 1134 borrow >>= SHIFT; 1135 } 1136 assert(borrow == 0); 1137 if (sign < 0) 1138 z->ob_size = -(z->ob_size); 1139 return long_normalize(z); 1140} 1141 1142static PyObject * 1143long_add(a, b) 1144 PyLongObject *a; 1145 PyLongObject *b; 1146{ 1147 PyLongObject *z; 1148 1149 if (a->ob_size < 0) { 1150 if (b->ob_size < 0) { 1151 z = x_add(a, b); 1152 if (z != NULL && z->ob_size != 0) 1153 z->ob_size = -(z->ob_size); 1154 } 1155 else 1156 z = x_sub(b, a); 1157 } 1158 else { 1159 if (b->ob_size < 0) 1160 z = x_sub(a, b); 1161 else 1162 z = x_add(a, b); 1163 } 1164 return (PyObject *)z; 1165} 1166 1167static PyObject * 1168long_sub(a, b) 1169 PyLongObject *a; 1170 PyLongObject *b; 1171{ 1172 PyLongObject *z; 1173 1174 if (a->ob_size < 0) { 1175 if (b->ob_size < 0) 1176 z = x_sub(a, b); 1177 else 1178 z = x_add(a, b); 1179 if (z != NULL && z->ob_size != 0) 1180 z->ob_size = -(z->ob_size); 1181 } 1182 else { 1183 if (b->ob_size < 0) 1184 z = x_add(a, b); 1185 else 1186 z = x_sub(a, b); 1187 } 1188 return (PyObject *)z; 1189} 1190 1191static PyObject * 1192long_mul(a, b) 1193 PyLongObject *a; 1194 PyLongObject *b; 1195{ 1196 int size_a; 1197 int size_b; 1198 PyLongObject *z; 1199 int i; 1200 1201 size_a = ABS(a->ob_size); 1202 size_b = ABS(b->ob_size); 1203 z = _PyLong_New(size_a + size_b); 1204 if (z == NULL) 1205 return NULL; 1206 for (i = 0; i < z->ob_size; ++i) 1207 z->ob_digit[i] = 0; 1208 for (i = 0; i < size_a; ++i) { 1209 twodigits carry = 0; 1210 twodigits f = a->ob_digit[i]; 1211 int j; 1212 1213 SIGCHECK({ 1214 Py_DECREF(z); 1215 return NULL; 1216 }) 1217 for (j = 0; j < size_b; ++j) { 1218 carry += z->ob_digit[i+j] + b->ob_digit[j] * f; 1219 z->ob_digit[i+j] = (digit) (carry & MASK); 1220 carry >>= SHIFT; 1221 } 1222 for (; carry != 0; ++j) { 1223 assert(i+j < z->ob_size); 1224 carry += z->ob_digit[i+j]; 1225 z->ob_digit[i+j] = (digit) (carry & MASK); 1226 carry >>= SHIFT; 1227 } 1228 } 1229 if (a->ob_size < 0) 1230 z->ob_size = -(z->ob_size); 1231 if (b->ob_size < 0) 1232 z->ob_size = -(z->ob_size); 1233 return (PyObject *) long_normalize(z); 1234} 1235 1236/* The / and % operators are now defined in terms of divmod(). 1237 The expression a mod b has the value a - b*floor(a/b). 1238 The long_divrem function gives the remainder after division of 1239 |a| by |b|, with the sign of a. This is also expressed 1240 as a - b*trunc(a/b), if trunc truncates towards zero. 1241 Some examples: 1242 a b a rem b a mod b 1243 13 10 3 3 1244 -13 10 -3 7 1245 13 -10 3 -7 1246 -13 -10 -3 -3 1247 So, to get from rem to mod, we have to add b if a and b 1248 have different signs. We then subtract one from the 'div' 1249 part of the outcome to keep the invariant intact. */ 1250 1251static int l_divmod Py_PROTO((PyLongObject *, PyLongObject *, 1252 PyLongObject **, PyLongObject **)); 1253static int 1254l_divmod(v, w, pdiv, pmod) 1255 PyLongObject *v; 1256 PyLongObject *w; 1257 PyLongObject **pdiv; 1258 PyLongObject **pmod; 1259{ 1260 PyLongObject *div, *mod; 1261 1262 if (long_divrem(v, w, &div, &mod) < 0) 1263 return -1; 1264 if ((mod->ob_size < 0 && w->ob_size > 0) || 1265 (mod->ob_size > 0 && w->ob_size < 0)) { 1266 PyLongObject *temp; 1267 PyLongObject *one; 1268 temp = (PyLongObject *) long_add(mod, w); 1269 Py_DECREF(mod); 1270 mod = temp; 1271 if (mod == NULL) { 1272 Py_DECREF(div); 1273 return -1; 1274 } 1275 one = (PyLongObject *) PyLong_FromLong(1L); 1276 if (one == NULL || 1277 (temp = (PyLongObject *) long_sub(div, one)) == NULL) { 1278 Py_DECREF(mod); 1279 Py_DECREF(div); 1280 Py_XDECREF(one); 1281 return -1; 1282 } 1283 Py_DECREF(one); 1284 Py_DECREF(div); 1285 div = temp; 1286 } 1287 *pdiv = div; 1288 *pmod = mod; 1289 return 0; 1290} 1291 1292static PyObject * 1293long_div(v, w) 1294 PyLongObject *v; 1295 PyLongObject *w; 1296{ 1297 PyLongObject *div, *mod; 1298 if (l_divmod(v, w, &div, &mod) < 0) 1299 return NULL; 1300 Py_DECREF(mod); 1301 return (PyObject *)div; 1302} 1303 1304static PyObject * 1305long_mod(v, w) 1306 PyLongObject *v; 1307 PyLongObject *w; 1308{ 1309 PyLongObject *div, *mod; 1310 if (l_divmod(v, w, &div, &mod) < 0) 1311 return NULL; 1312 Py_DECREF(div); 1313 return (PyObject *)mod; 1314} 1315 1316static PyObject * 1317long_divmod(v, w) 1318 PyLongObject *v; 1319 PyLongObject *w; 1320{ 1321 PyObject *z; 1322 PyLongObject *div, *mod; 1323 if (l_divmod(v, w, &div, &mod) < 0) 1324 return NULL; 1325 z = PyTuple_New(2); 1326 if (z != NULL) { 1327 PyTuple_SetItem(z, 0, (PyObject *) div); 1328 PyTuple_SetItem(z, 1, (PyObject *) mod); 1329 } 1330 else { 1331 Py_DECREF(div); 1332 Py_DECREF(mod); 1333 } 1334 return z; 1335} 1336 1337static PyObject * 1338long_pow(a, b, c) 1339 PyLongObject *a; 1340 PyLongObject *b; 1341 PyLongObject *c; 1342{ 1343 PyLongObject *z, *div, *mod; 1344 int size_b, i; 1345 1346 size_b = b->ob_size; 1347 if (size_b < 0) { 1348 PyErr_SetString(PyExc_ValueError, 1349 "long integer to the negative power"); 1350 return NULL; 1351 } 1352 z = (PyLongObject *)PyLong_FromLong(1L); 1353 Py_INCREF(a); 1354 for (i = 0; i < size_b; ++i) { 1355 digit bi = b->ob_digit[i]; 1356 int j; 1357 1358 for (j = 0; j < SHIFT; ++j) { 1359 PyLongObject *temp; 1360 1361 if (bi & 1) { 1362 temp = (PyLongObject *)long_mul(z, a); 1363 Py_DECREF(z); 1364 if ((PyObject*)c!=Py_None && temp!=NULL) { 1365 l_divmod(temp, c, &div, &mod); 1366 Py_XDECREF(div); 1367 Py_DECREF(temp); 1368 temp = mod; 1369 } 1370 z = temp; 1371 if (z == NULL) 1372 break; 1373 } 1374 bi >>= 1; 1375 if (bi == 0 && i+1 == size_b) 1376 break; 1377 temp = (PyLongObject *)long_mul(a, a); 1378 Py_DECREF(a); 1379 if ((PyObject*)c!=Py_None && temp!=NULL) { 1380 l_divmod(temp, c, &div, &mod); 1381 Py_XDECREF(div); 1382 Py_DECREF(temp); 1383 temp = mod; 1384 } 1385 a = temp; 1386 if (a == NULL) { 1387 Py_DECREF(z); 1388 z = NULL; 1389 break; 1390 } 1391 } 1392 if (a == NULL || z == NULL) 1393 break; 1394 } 1395 Py_XDECREF(a); 1396 if ((PyObject*)c!=Py_None && z!=NULL) { 1397 l_divmod(z, c, &div, &mod); 1398 Py_XDECREF(div); 1399 Py_DECREF(z); 1400 z=mod; 1401 } 1402 return (PyObject *)z; 1403} 1404 1405static PyObject * 1406long_invert(v) 1407 PyLongObject *v; 1408{ 1409 /* Implement ~x as -(x+1) */ 1410 PyLongObject *x; 1411 PyLongObject *w; 1412 w = (PyLongObject *)PyLong_FromLong(1L); 1413 if (w == NULL) 1414 return NULL; 1415 x = (PyLongObject *) long_add(v, w); 1416 Py_DECREF(w); 1417 if (x == NULL) 1418 return NULL; 1419 if (x->ob_size != 0) 1420 x->ob_size = -(x->ob_size); 1421 return (PyObject *)x; 1422} 1423 1424static PyObject * 1425long_pos(v) 1426 PyLongObject *v; 1427{ 1428 Py_INCREF(v); 1429 return (PyObject *)v; 1430} 1431 1432static PyObject * 1433long_neg(v) 1434 PyLongObject *v; 1435{ 1436 PyLongObject *z; 1437 int i, n; 1438 n = ABS(v->ob_size); 1439 if (n == 0) { 1440 /* -0 == 0 */ 1441 Py_INCREF(v); 1442 return (PyObject *) v; 1443 } 1444 z = _PyLong_New(ABS(n)); 1445 if (z == NULL) 1446 return NULL; 1447 for (i = 0; i < n; i++) 1448 z->ob_digit[i] = v->ob_digit[i]; 1449 z->ob_size = -(v->ob_size); 1450 return (PyObject *)z; 1451} 1452 1453static PyObject * 1454long_abs(v) 1455 PyLongObject *v; 1456{ 1457 if (v->ob_size < 0) 1458 return long_neg(v); 1459 else { 1460 Py_INCREF(v); 1461 return (PyObject *)v; 1462 } 1463} 1464 1465static int 1466long_nonzero(v) 1467 PyLongObject *v; 1468{ 1469 return ABS(v->ob_size) != 0; 1470} 1471 1472static PyObject * 1473long_rshift(a, b) 1474 PyLongObject *a; 1475 PyLongObject *b; 1476{ 1477 PyLongObject *z; 1478 long shiftby; 1479 int newsize, wordshift, loshift, hishift, i, j; 1480 digit lomask, himask; 1481 1482 if (a->ob_size < 0) { 1483 /* Right shifting negative numbers is harder */ 1484 PyLongObject *a1, *a2, *a3; 1485 a1 = (PyLongObject *) long_invert(a); 1486 if (a1 == NULL) return NULL; 1487 a2 = (PyLongObject *) long_rshift(a1, b); 1488 Py_DECREF(a1); 1489 if (a2 == NULL) return NULL; 1490 a3 = (PyLongObject *) long_invert(a2); 1491 Py_DECREF(a2); 1492 return (PyObject *) a3; 1493 } 1494 1495 shiftby = PyLong_AsLong((PyObject *)b); 1496 if (shiftby == -1L && PyErr_Occurred()) 1497 return NULL; 1498 if (shiftby < 0) { 1499 PyErr_SetString(PyExc_ValueError, "negative shift count"); 1500 return NULL; 1501 } 1502 wordshift = shiftby / SHIFT; 1503 newsize = ABS(a->ob_size) - wordshift; 1504 if (newsize <= 0) { 1505 z = _PyLong_New(0); 1506 return (PyObject *)z; 1507 } 1508 loshift = shiftby % SHIFT; 1509 hishift = SHIFT - loshift; 1510 lomask = ((digit)1 << hishift) - 1; 1511 himask = MASK ^ lomask; 1512 z = _PyLong_New(newsize); 1513 if (z == NULL) 1514 return NULL; 1515 if (a->ob_size < 0) 1516 z->ob_size = -(z->ob_size); 1517 for (i = 0, j = wordshift; i < newsize; i++, j++) { 1518 z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask; 1519 if (i+1 < newsize) 1520 z->ob_digit[i] |= 1521 (a->ob_digit[j+1] << hishift) & himask; 1522 } 1523 return (PyObject *) long_normalize(z); 1524} 1525 1526static PyObject * 1527long_lshift(a, b) 1528 PyLongObject *a; 1529 PyLongObject *b; 1530{ 1531 /* This version due to Tim Peters */ 1532 PyLongObject *z; 1533 long shiftby; 1534 int oldsize, newsize, wordshift, remshift, i, j; 1535 twodigits accum; 1536 1537 shiftby = PyLong_AsLong((PyObject *)b); 1538 if (shiftby == -1L && PyErr_Occurred()) 1539 return NULL; 1540 if (shiftby < 0) { 1541 PyErr_SetString(PyExc_ValueError, "negative shift count"); 1542 return NULL; 1543 } 1544 if ((long)(int)shiftby != shiftby) { 1545 PyErr_SetString(PyExc_ValueError, 1546 "outrageous left shift count"); 1547 return NULL; 1548 } 1549 /* wordshift, remshift = divmod(shiftby, SHIFT) */ 1550 wordshift = (int)shiftby / SHIFT; 1551 remshift = (int)shiftby - wordshift * SHIFT; 1552 1553 oldsize = ABS(a->ob_size); 1554 newsize = oldsize + wordshift; 1555 if (remshift) 1556 ++newsize; 1557 z = _PyLong_New(newsize); 1558 if (z == NULL) 1559 return NULL; 1560 if (a->ob_size < 0) 1561 z->ob_size = -(z->ob_size); 1562 for (i = 0; i < wordshift; i++) 1563 z->ob_digit[i] = 0; 1564 accum = 0; 1565 for (i = wordshift, j = 0; j < oldsize; i++, j++) { 1566 accum |= a->ob_digit[j] << remshift; 1567 z->ob_digit[i] = (digit)(accum & MASK); 1568 accum >>= SHIFT; 1569 } 1570 if (remshift) 1571 z->ob_digit[newsize-1] = (digit)accum; 1572 else 1573 assert(!accum); 1574 return (PyObject *) long_normalize(z); 1575} 1576 1577 1578/* Bitwise and/xor/or operations */ 1579 1580#define MAX(x, y) ((x) < (y) ? (y) : (x)) 1581#define MIN(x, y) ((x) > (y) ? (y) : (x)) 1582 1583static PyObject *long_bitwise Py_PROTO((PyLongObject *, int, PyLongObject *)); 1584static PyObject * 1585long_bitwise(a, op, b) 1586 PyLongObject *a; 1587 int op; /* '&', '|', '^' */ 1588 PyLongObject *b; 1589{ 1590 digit maska, maskb; /* 0 or MASK */ 1591 int negz; 1592 int size_a, size_b, size_z; 1593 PyLongObject *z; 1594 int i; 1595 digit diga, digb; 1596 PyObject *v; 1597 1598 if (a->ob_size < 0) { 1599 a = (PyLongObject *) long_invert(a); 1600 maska = MASK; 1601 } 1602 else { 1603 Py_INCREF(a); 1604 maska = 0; 1605 } 1606 if (b->ob_size < 0) { 1607 b = (PyLongObject *) long_invert(b); 1608 maskb = MASK; 1609 } 1610 else { 1611 Py_INCREF(b); 1612 maskb = 0; 1613 } 1614 1615 negz = 0; 1616 switch (op) { 1617 case '^': 1618 if (maska != maskb) { 1619 maska ^= MASK; 1620 negz = -1; 1621 } 1622 break; 1623 case '&': 1624 if (maska && maskb) { 1625 op = '|'; 1626 maska ^= MASK; 1627 maskb ^= MASK; 1628 negz = -1; 1629 } 1630 break; 1631 case '|': 1632 if (maska || maskb) { 1633 op = '&'; 1634 maska ^= MASK; 1635 maskb ^= MASK; 1636 negz = -1; 1637 } 1638 break; 1639 } 1640 1641 /* JRH: The original logic here was to allocate the result value (z) 1642 as the longer of the two operands. However, there are some cases 1643 where the result is guaranteed to be shorter than that: AND of two 1644 positives, OR of two negatives: use the shorter number. AND with 1645 mixed signs: use the positive number. OR with mixed signs: use the 1646 negative number. After the transformations above, op will be '&' 1647 iff one of these cases applies, and mask will be non-0 for operands 1648 whose length should be ignored. 1649 */ 1650 1651 size_a = a->ob_size; 1652 size_b = b->ob_size; 1653 size_z = op == '&' 1654 ? (maska 1655 ? size_b 1656 : (maskb ? size_a : MIN(size_a, size_b))) 1657 : MAX(size_a, size_b); 1658 z = _PyLong_New(size_z); 1659 if (a == NULL || b == NULL || z == NULL) { 1660 Py_XDECREF(a); 1661 Py_XDECREF(b); 1662 Py_XDECREF(z); 1663 return NULL; 1664 } 1665 1666 for (i = 0; i < size_z; ++i) { 1667 diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska; 1668 digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb; 1669 switch (op) { 1670 case '&': z->ob_digit[i] = diga & digb; break; 1671 case '|': z->ob_digit[i] = diga | digb; break; 1672 case '^': z->ob_digit[i] = diga ^ digb; break; 1673 } 1674 } 1675 1676 Py_DECREF(a); 1677 Py_DECREF(b); 1678 z = long_normalize(z); 1679 if (negz == 0) 1680 return (PyObject *) z; 1681 v = long_invert(z); 1682 Py_DECREF(z); 1683 return v; 1684} 1685 1686static PyObject * 1687long_and(a, b) 1688 PyLongObject *a; 1689 PyLongObject *b; 1690{ 1691 return long_bitwise(a, '&', b); 1692} 1693 1694static PyObject * 1695long_xor(a, b) 1696 PyLongObject *a; 1697 PyLongObject *b; 1698{ 1699 return long_bitwise(a, '^', b); 1700} 1701 1702static PyObject * 1703long_or(a, b) 1704 PyLongObject *a; 1705 PyLongObject *b; 1706{ 1707 return long_bitwise(a, '|', b); 1708} 1709 1710static int 1711long_coerce(pv, pw) 1712 PyObject **pv; 1713 PyObject **pw; 1714{ 1715 if (PyInt_Check(*pw)) { 1716 *pw = PyLong_FromLong(PyInt_AsLong(*pw)); 1717 Py_INCREF(*pv); 1718 return 0; 1719 } 1720 return 1; /* Can't do it */ 1721} 1722 1723static PyObject * 1724long_int(v) 1725 PyObject *v; 1726{ 1727 long x; 1728 x = PyLong_AsLong(v); 1729 if (PyErr_Occurred()) 1730 return NULL; 1731 return PyInt_FromLong(x); 1732} 1733 1734static PyObject * 1735long_long(v) 1736 PyObject *v; 1737{ 1738 Py_INCREF(v); 1739 return v; 1740} 1741 1742static PyObject * 1743long_float(v) 1744 PyObject *v; 1745{ 1746 double result; 1747 PyFPE_START_PROTECT("long_float", return 0) 1748 result = PyLong_AsDouble(v); 1749 PyFPE_END_PROTECT(result) 1750 return PyFloat_FromDouble(result); 1751} 1752 1753static PyObject * 1754long_oct(v) 1755 PyObject *v; 1756{ 1757 return long_format(v, 8); 1758} 1759 1760static PyObject * 1761long_hex(v) 1762 PyObject *v; 1763{ 1764 return long_format(v, 16); 1765} 1766 1767 1768#define UF (unaryfunc) 1769#define BF (binaryfunc) 1770#define TF (ternaryfunc) 1771#define IF (inquiry) 1772 1773static PyNumberMethods long_as_number = { 1774 BF long_add, /*nb_add*/ 1775 BF long_sub, /*nb_subtract*/ 1776 BF long_mul, /*nb_multiply*/ 1777 BF long_div, /*nb_divide*/ 1778 BF long_mod, /*nb_remainder*/ 1779 BF long_divmod, /*nb_divmod*/ 1780 TF long_pow, /*nb_power*/ 1781 UF long_neg, /*nb_negative*/ 1782 UF long_pos, /*tp_positive*/ 1783 UF long_abs, /*tp_absolute*/ 1784 IF long_nonzero,/*tp_nonzero*/ 1785 UF long_invert, /*nb_invert*/ 1786 BF long_lshift, /*nb_lshift*/ 1787 BF long_rshift, /*nb_rshift*/ 1788 BF long_and, /*nb_and*/ 1789 BF long_xor, /*nb_xor*/ 1790 BF long_or, /*nb_or*/ 1791 (int (*) Py_FPROTO((PyObject **, PyObject **))) 1792 (coercion)long_coerce, /*nb_coerce*/ 1793 UF long_int, /*nb_int*/ 1794 UF long_long, /*nb_long*/ 1795 UF long_float, /*nb_float*/ 1796 UF long_oct, /*nb_oct*/ 1797 UF long_hex, /*nb_hex*/ 1798}; 1799 1800PyTypeObject PyLong_Type = { 1801 PyObject_HEAD_INIT(&PyType_Type) 1802 0, 1803 "long int", 1804 sizeof(PyLongObject) - sizeof(digit), 1805 sizeof(digit), 1806 (destructor)long_dealloc, /*tp_dealloc*/ 1807 0, /*tp_print*/ 1808 0, /*tp_getattr*/ 1809 0, /*tp_setattr*/ 1810 (int (*) Py_FPROTO((PyObject *, PyObject *))) 1811 (cmpfunc)long_compare, /*tp_compare*/ 1812 (reprfunc)long_repr, /*tp_repr*/ 1813 &long_as_number,/*tp_as_number*/ 1814 0, /*tp_as_sequence*/ 1815 0, /*tp_as_mapping*/ 1816 (long (*) Py_FPROTO((PyObject *))) 1817 (hashfunc)long_hash, /*tp_hash*/ 1818}; 1819