← Back to branch summary

~ubuntu-branches/ubuntu/karmic/python3.0/karmic

« back to all changes in this revision

Viewing changes to Objects/longobject.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2009-02-16 17:18:23 UTC
  • mfrom: (1.1.4 upstream)
  • Revision ID: james.westby@ubuntu.com-20090216171823-1d5cm5qnnjvmnzzm
Tags: 3.0.1-0ubuntu1
New upstream version.

Show diffs side-by-side

added added

removed removed

Lines of Context:
Objects/longobject.c
44
44
}
45
45
#define CHECK_SMALL_INT(ival) \
46
46
        do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
47
 
                return get_small_int(ival); \
 
47
                return get_small_int((int)ival); \
48
48
        } while(0)
49
49
 
50
50
static PyLongObject * 
175
175
PyLong_FromLong(long ival)
176
176
{
177
177
        PyLongObject *v;
178
 
        unsigned long abs_ival;
 
178
        unsigned long abs_ival;
179
179
        unsigned long t;  /* unsigned so >> doesn't propagate sign bit */
180
180
        int ndigits = 0;
181
181
        int sign = 1;
183
183
        CHECK_SMALL_INT(ival);
184
184
 
185
185
        if (ival < 0) {
186
 
                /* if LONG_MIN == -LONG_MAX-1 (true on most platforms) then
187
 
                   ANSI C says that the result of -ival is undefined when ival
188
 
                   == LONG_MIN.  Hence the following workaround. */
189
 
                abs_ival = (unsigned long)(-1-ival) + 1;
 
186
                /* negate: can't write this as abs_ival = -ival since that
 
187
                   invokes undefined behaviour when ival is LONG_MIN */
 
188
                abs_ival = 0U-(unsigned long)ival;
190
189
                sign = -1;
191
190
        }
192
191
        else {
193
192
                abs_ival = (unsigned long)ival;
194
193
        }
195
194
 
196
 
        /* Fast path for single-digits ints */
197
 
        if (!(ival>>PyLong_SHIFT)) {
 
195
        /* Fast path for single-digit ints */
 
196
        if (!(abs_ival >> PyLong_SHIFT)) {
198
197
                v = _PyLong_New(1);
199
198
                if (v) {
200
199
                        Py_SIZE(v) = sign;
201
 
                        v->ob_digit[0] = ival;
 
200
                        v->ob_digit[0] = Py_SAFE_DOWNCAST(
 
201
                                abs_ival, unsigned long, digit);
202
202
                }
203
203
                return (PyObject*)v;
204
204
        }
205
205
 
206
206
        /* 2 digits */
207
 
        if (!(ival >> 2*PyLong_SHIFT)) {
 
207
        if (!(abs_ival >> 2*PyLong_SHIFT)) {
208
208
                v = _PyLong_New(2);
209
209
                if (v) {
210
210
                        Py_SIZE(v) = 2*sign;
211
 
                        v->ob_digit[0] = (digit)ival & PyLong_MASK;
212
 
                        v->ob_digit[1] = ival >> PyLong_SHIFT;
 
211
                        v->ob_digit[0] = Py_SAFE_DOWNCAST(
 
212
                                abs_ival & PyLong_MASK, unsigned long, digit);
 
213
                        v->ob_digit[1] = Py_SAFE_DOWNCAST(
 
214
                              abs_ival >> PyLong_SHIFT, unsigned long, digit);
213
215
                }
214
216
                return (PyObject*)v;
215
217
        }
226
228
                Py_SIZE(v) = ndigits*sign;
227
229
                t = abs_ival;
228
230
                while (t) {
229
 
                        *p++ = (digit)(t & PyLong_MASK);
 
231
                        *p++ = Py_SAFE_DOWNCAST(
 
232
                                t & PyLong_MASK, unsigned long, digit);
230
233
                        t >>= PyLong_SHIFT;
231
234
                }
232
235
        }
739
742
                        /* Because we're going LSB to MSB, thisbyte is
740
743
                           more significant than what's already in accum,
741
744
                           so needs to be prepended to accum. */
742
 
                        accum |= thisbyte << accumbits;
 
745
                        accum |= (twodigits)thisbyte << accumbits;
743
746
                        accumbits += 8;
744
747
                        if (accumbits >= PyLong_SHIFT) {
745
748
                                /* There's enough to fill a Python digit. */
768
771
                    unsigned char* bytes, size_t n,
769
772
                    int little_endian, int is_signed)
770
773
{
771
 
        int i;                  /* index into v->ob_digit */
 
774
        Py_ssize_t i;           /* index into v->ob_digit */
772
775
        Py_ssize_t ndigits;             /* |v->ob_size| */
773
776
        twodigits accum;        /* sliding register */
774
777
        unsigned int accumbits; /* # bits in accum */
775
778
        int do_twos_comp;       /* store 2's-comp?  is_signed and v < 0 */
776
 
        twodigits carry;        /* for computing 2's-comp */
 
779
        digit carry;            /* for computing 2's-comp */
777
780
        size_t j;               /* # bytes filled */
778
781
        unsigned char* p;       /* pointer to next byte in bytes */
779
782
        int pincr;              /* direction to move p */
813
816
        accumbits = 0;
814
817
        carry = do_twos_comp ? 1 : 0;
815
818
        for (i = 0; i < ndigits; ++i) {
816
 
                twodigits thisdigit = v->ob_digit[i];
 
819
                digit thisdigit = v->ob_digit[i];
817
820
                if (do_twos_comp) {
818
821
                        thisdigit = (thisdigit ^ PyLong_MASK) + carry;
819
822
                        carry = thisdigit >> PyLong_SHIFT;
822
825
                /* Because we're going LSB to MSB, thisdigit is more
823
826
                   significant than what's already in accum, so needs to be
824
827
                   prepended to accum. */
825
 
                accum |= thisdigit << accumbits;
826
 
                accumbits += PyLong_SHIFT;
 
828
                accum |= (twodigits)thisdigit << accumbits;
827
829
 
828
830
                /* The most-significant digit may be (probably is) at least
829
831
                   partly empty. */
830
832
                if (i == ndigits - 1) {
831
833
                        /* Count # of sign bits -- they needn't be stored,
832
834
                         * although for signed conversion we need later to
833
 
                         * make sure at least one sign bit gets stored.
834
 
                         * First shift conceptual sign bit to real sign bit.
835
 
                         */
836
 
                        stwodigits s = (stwodigits)(thisdigit <<
837
 
                                (8*sizeof(stwodigits) - PyLong_SHIFT));
838
 
                        unsigned int nsignbits = 0;
839
 
                        while ((s < 0) == do_twos_comp && nsignbits < PyLong_SHIFT) {
840
 
                                ++nsignbits;
841
 
                                s <<= 1;
 
835
                         * make sure at least one sign bit gets stored. */
 
836
                        digit s = do_twos_comp ? thisdigit ^ PyLong_MASK :
 
837
                                                thisdigit;
 
838
                        while (s != 0) {
 
839
                                s >>= 1;
 
840
                                accumbits++;
842
841
                        }
843
 
                        accumbits -= nsignbits;
844
842
                }
 
843
                else
 
844
                        accumbits += PyLong_SHIFT;
845
845
 
846
846
                /* Store as many bytes as possible. */
847
847
                while (accumbits >= 8) {
1103
1103
        int ndigits = 0;
1104
1104
 
1105
1105
        if (ival < PyLong_BASE)
1106
 
                return PyLong_FromLong(ival);
 
1106
                return PyLong_FromLong((long)ival);
1107
1107
        /* Count the number of Python digits. */
1108
1108
        t = (unsigned PY_LONG_LONG)ival;
1109
1109
        while (t) {
1361
1361
static digit
1362
1362
v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
1363
1363
{
1364
 
        int i;
 
1364
        Py_ssize_t i;
1365
1365
        digit carry = 0;
1366
1366
 
1367
1367
        assert(m >= n);
1387
1387
static digit
1388
1388
v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
1389
1389
{
1390
 
        int i;
 
1390
        Py_ssize_t i;
1391
1391
        digit borrow = 0;
1392
1392
 
1393
1393
        assert(m >= n);
1453
1453
                digit hi;
1454
1454
                rem = (rem << PyLong_SHIFT) + *--pin;
1455
1455
                *--pout = hi = (digit)(rem / n);
1456
 
                rem -= hi * n;
 
1456
                rem -= (twodigits)hi * n;
1457
1457
        }
1458
1458
        return (digit)rem;
1459
1459
}
1712
1712
        while (--p >= start) {
1713
1713
                int k = _PyLong_DigitValue[Py_CHARMASK(*p)];
1714
1714
                assert(k >= 0 && k < base);
1715
 
                accum |= (twodigits)(k << bits_in_accum);
 
1715
                accum |= (twodigits)k << bits_in_accum;
1716
1716
                bits_in_accum += bits_per_char;
1717
1717
                if (bits_in_accum >= PyLong_SHIFT) {
1718
1718
                        *pdigit++ = (digit)(accum & PyLong_MASK);
1719
 
                        assert(pdigit - z->ob_digit <= (int)n);
 
1719
                        assert(pdigit - z->ob_digit <= n);
1720
1720
                        accum >>= PyLong_SHIFT;
1721
1721
                        bits_in_accum -= PyLong_SHIFT;
1722
1722
                        assert(bits_in_accum < PyLong_SHIFT);
1725
1725
        if (bits_in_accum) {
1726
1726
                assert(bits_in_accum <= PyLong_SHIFT);
1727
1727
                *pdigit++ = (digit)accum;
1728
 
                assert(pdigit - z->ob_digit <= (int)n);
 
1728
                assert(pdigit - z->ob_digit <= n);
1729
1729
        }
1730
1730
        while (pdigit - z->ob_digit < n)
1731
1731
                *pdigit++ = 0;
1990
1990
                goto onError;
1991
1991
        if (sign < 0)
1992
1992
                Py_SIZE(z) = -(Py_SIZE(z));
1993
 
        if (*str == 'L' || *str == 'l')
1994
 
                str++;
1995
1993
        while (*str && isspace(Py_CHARMASK(*str)))
1996
1994
                str++;
1997
1995
        if (*str != '\0')
2122
2120
                digit vj = (j >= size_v) ? 0 : v->ob_digit[j];
2123
2121
                twodigits q;
2124
2122
                stwodigits carry = 0;
2125
 
                int i;
 
2123
                Py_ssize_t i;
2126
2124
 
2127
2125
                SIGCHECK({
2128
2126
                        Py_DECREF(a);
2232
2230
        return sign < 0 ? -1 : sign > 0 ? 1 : 0;
2233
2231
}
2234
2232
 
 
2233
#define TEST_COND(cond) \
 
2234
        ((cond) ? Py_True : Py_False)
 
2235
 
2235
2236
static PyObject *
2236
2237
long_richcompare(PyObject *self, PyObject *other, int op)
2237
2238
{
2238
 
        PyObject *result;
 
2239
        int result;
 
2240
        PyObject *v;
2239
2241
        CHECK_BINOP(self, other);
2240
 
        result = Py_CmpToRich(op, long_compare((PyLongObject*)self, 
2241
 
                                               (PyLongObject*)other));
2242
 
        return result;
 
2242
        if (self == other)
 
2243
                result = 0;
 
2244
        else
 
2245
                result = long_compare((PyLongObject*)self, (PyLongObject*)other);
 
2246
        /* Convert the return value to a Boolean */
 
2247
        switch (op) {
 
2248
        case Py_EQ:
 
2249
                v = TEST_COND(result == 0);
 
2250
                break;
 
2251
        case Py_NE:
 
2252
                v = TEST_COND(result != 0);
 
2253
                break;
 
2254
        case Py_LE:
 
2255
                v = TEST_COND(result <= 0);
 
2256
                break;
 
2257
        case Py_GE:
 
2258
                v = TEST_COND(result >= 0);
 
2259
                break;
 
2260
        case Py_LT:
 
2261
                v = TEST_COND(result == -1);
 
2262
                break;
 
2263
        case Py_GT:
 
2264
                v = TEST_COND(result == 1);
 
2265
                break;
 
2266
        default:
 
2267
                PyErr_BadArgument();
 
2268
                return NULL;
 
2269
        }
 
2270
        Py_INCREF(v);
 
2271
        return v;
2243
2272
}
2244
2273
 
2245
2274
static long
2246
2275
long_hash(PyLongObject *v)
2247
2276
{
2248
 
        long x;
 
2277
        unsigned long x;
2249
2278
        Py_ssize_t i;
2250
2279
        int sign;
2251
2280
 
2265
2294
                i = -(i);
2266
2295
        }
2267
2296
#define LONG_BIT_PyLong_SHIFT   (8*sizeof(long) - PyLong_SHIFT)
2268
 
        /* The following loop produces a C long x such that (unsigned long)x
2269
 
           is congruent to the absolute value of v modulo ULONG_MAX.  The
 
2297
        /* The following loop produces a C unsigned long x such that x is
 
2298
           congruent to the absolute value of v modulo ULONG_MAX.  The
2270
2299
           resulting x is nonzero if and only if v is. */
2271
2300
        while (--i >= 0) {
2272
2301
                /* Force a native long #-bits (32 or 64) circular shift */
2273
 
                x = ((x << PyLong_SHIFT) & ~PyLong_MASK) | ((x >> LONG_BIT_PyLong_SHIFT) & PyLong_MASK);
 
2302
                x = ((x << PyLong_SHIFT) & ~PyLong_MASK) |
 
2303
                        ((x >> LONG_BIT_PyLong_SHIFT) & PyLong_MASK);
2274
2304
                x += v->ob_digit[i];
2275
 
                /* If the addition above overflowed (thinking of x as
2276
 
                   unsigned), we compensate by incrementing.  This preserves
2277
 
                   the value modulo ULONG_MAX. */
2278
 
                if ((unsigned long)x < v->ob_digit[i])
 
2305
                /* If the addition above overflowed we compensate by
 
2306
                   incrementing.  This preserves the value modulo
 
2307
                   ULONG_MAX. */
 
2308
                if (x < v->ob_digit[i])
2279
2309
                        x++;
2280
2310
        }
2281
2311
#undef LONG_BIT_PyLong_SHIFT
2293
2323
{
2294
2324
        Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2295
2325
        PyLongObject *z;
2296
 
        int i;
 
2326
        Py_ssize_t i;
2297
2327
        digit carry = 0;
2298
2328
 
2299
2329
        /* Ensure a is the larger of the two: */
3613
3643
                                      PyUnicode_GET_SIZE(format_spec));
3614
3644
}
3615
3645
 
3616
 
 
3617
3646
static PyObject *
3618
3647
long_round(PyObject *self, PyObject *args)
3619
3648
{
3620
 
#define UNDEF_NDIGITS (-0x7fffffff) /* Unlikely ndigits value */
3621
 
        int ndigits = UNDEF_NDIGITS;
3622
 
        double x;
3623
 
        PyObject *res;
3624
 
        
3625
 
        if (!PyArg_ParseTuple(args, "|i", &ndigits))
3626
 
                return NULL;
3627
 
 
3628
 
        if (ndigits == UNDEF_NDIGITS)
3629
 
                return long_long(self);
3630
 
 
3631
 
        /* If called with two args, defer to float.__round__(). */
3632
 
        x = PyLong_AsDouble(self);
3633
 
        if (x == -1.0 && PyErr_Occurred())
3634
 
                return NULL;
3635
 
        self = PyFloat_FromDouble(x);
 
3649
        PyObject *o_ndigits=NULL, *temp;
 
3650
        PyLongObject *pow=NULL, *q=NULL, *r=NULL, *ndigits=NULL, *one;
 
3651
        int errcode;
 
3652
        digit q_mod_4;
 
3653
 
 
3654
        /* Notes on the algorithm: to round to the nearest 10**n (n positive),
 
3655
           the straightforward method is:
 
3656
 
 
3657
              (1) divide by 10**n
 
3658
              (2) round to nearest integer (round to even in case of tie)
 
3659
              (3) multiply result by 10**n.
 
3660
 
 
3661
           But the rounding step involves examining the fractional part of the
 
3662
           quotient to see whether it's greater than 0.5 or not.  Since we
 
3663
           want to do the whole calculation in integer arithmetic, it's
 
3664
           simpler to do:
 
3665
 
 
3666
              (1) divide by (10**n)/2
 
3667
              (2) round to nearest multiple of 2 (multiple of 4 in case of tie)
 
3668
              (3) multiply result by (10**n)/2.
 
3669
 
 
3670
           Then all we need to know about the fractional part of the quotient
 
3671
           arising in step (2) is whether it's zero or not.
 
3672
 
 
3673
           Doing both a multiplication and division is wasteful, and is easily
 
3674
           avoided if we just figure out how much to adjust the original input
 
3675
           by to do the rounding.
 
3676
 
 
3677
           Here's the whole algorithm expressed in Python.
 
3678
 
 
3679
            def round(self, ndigits = None):
 
3680
                """round(int, int) -> int"""
 
3681
                if ndigits is None or ndigits >= 0:
 
3682
                    return self
 
3683
                pow = 10**-ndigits >> 1
 
3684
                q, r = divmod(self, pow)
 
3685
                self -= r
 
3686
                if (q & 1 != 0):
 
3687
                    if (q & 2 == r == 0):
 
3688
                        self -= pow
 
3689
                    else:
 
3690
                        self += pow
 
3691
                return self
 
3692
 
 
3693
        */
 
3694
        if (!PyArg_ParseTuple(args, "|O", &o_ndigits))
 
3695
                return NULL;
 
3696
        if (o_ndigits == NULL)
 
3697
                return long_long(self);
 
3698
 
 
3699
        ndigits = (PyLongObject *)PyNumber_Index(o_ndigits);
 
3700
        if (ndigits == NULL)
 
3701
                return NULL;
 
3702
 
 
3703
        if (Py_SIZE(ndigits) >= 0) {
 
3704
                Py_DECREF(ndigits);
 
3705
                return long_long(self);
 
3706
        }
 
3707
 
 
3708
        Py_INCREF(self); /* to keep refcounting simple */
 
3709
        /* we now own references to self, ndigits */
 
3710
 
 
3711
        /* pow = 10 ** -ndigits >> 1 */
 
3712
        pow = (PyLongObject *)PyLong_FromLong(10L);
 
3713
        if (pow == NULL)
 
3714
                goto error;
 
3715
        temp = long_neg(ndigits);
 
3716
        Py_DECREF(ndigits);
 
3717
        ndigits = (PyLongObject *)temp;
 
3718
        if (ndigits == NULL)
 
3719
                goto error;
 
3720
        temp = long_pow((PyObject *)pow, (PyObject *)ndigits, Py_None);
 
3721
        Py_DECREF(pow);
 
3722
        pow = (PyLongObject *)temp;
 
3723
        if (pow == NULL)
 
3724
                goto error;
 
3725
        assert(PyLong_Check(pow)); /* check long_pow returned a long */
 
3726
        one = (PyLongObject *)PyLong_FromLong(1L);
 
3727
        if (one == NULL)
 
3728
                goto error;
 
3729
        temp = long_rshift(pow, one);
 
3730
        Py_DECREF(one);
 
3731
        Py_DECREF(pow);
 
3732
        pow = (PyLongObject *)temp;
 
3733
        if (pow == NULL)
 
3734
                goto error;
 
3735
 
 
3736
        /* q, r = divmod(self, pow) */
 
3737
        errcode = l_divmod((PyLongObject *)self, pow, &q, &r);
 
3738
        if (errcode == -1)
 
3739
                goto error;
 
3740
 
 
3741
        /* self -= r */
 
3742
        temp = long_sub((PyLongObject *)self, r);
 
3743
        Py_DECREF(self);
 
3744
        self = temp;
3636
3745
        if (self == NULL)
3637
 
                return NULL;
3638
 
        res = PyObject_CallMethod(self, "__round__", "i", ndigits);
3639
 
        Py_DECREF(self);
3640
 
        return res;
3641
 
#undef UNDEF_NDIGITS
 
3746
                goto error;
 
3747
 
 
3748
        /* get value of quotient modulo 4 */
 
3749
        if (Py_SIZE(q) == 0)
 
3750
                q_mod_4 = 0;
 
3751
        else if (Py_SIZE(q) > 0)
 
3752
                q_mod_4 = q->ob_digit[0] & 3;
 
3753
        else
 
3754
                q_mod_4 = (PyLong_BASE-q->ob_digit[0]) & 3;
 
3755
 
 
3756
        if ((q_mod_4 & 1) == 1) {
 
3757
                /* q is odd; round self up or down by adding or subtracting pow */
 
3758
                if (q_mod_4 == 1 && Py_SIZE(r) == 0)
 
3759
                        temp = (PyObject *)long_sub((PyLongObject *)self, pow);
 
3760
                else
 
3761
                        temp = (PyObject *)long_add((PyLongObject *)self, pow);
 
3762
                Py_DECREF(self);
 
3763
                self = temp;
 
3764
                if (self == NULL)
 
3765
                        goto error;
 
3766
        }
 
3767
        Py_DECREF(q);
 
3768
        Py_DECREF(r);
 
3769
        Py_DECREF(pow);
 
3770
        Py_DECREF(ndigits);
 
3771
        return self;
 
3772
 
 
3773
  error:
 
3774
        Py_XDECREF(q);
 
3775
        Py_XDECREF(r);
 
3776
        Py_XDECREF(pow);
 
3777
        Py_XDECREF(self);
 
3778
        Py_XDECREF(ndigits);
 
3779
        return NULL;
3642
3780
}
3643
3781
 
3644
3782
static PyObject *
3672
3810
        {"__ceil__",    (PyCFunction)long_long, METH_NOARGS,
3673
3811
         "Ceiling of an Integral returns itself."},
3674
3812
        {"__round__",   (PyCFunction)long_round, METH_VARARGS,
3675
 
         "Rounding an Integral returns itself.\n"
3676
 
         "Rounding with an ndigits arguments defers to float.__round__."},
 
3813
         "Rounding an Integral returns itself.\n"
 
3814
         "Rounding with an ndigits argument also returns an integer."},
3677
3815
        {"__getnewargs__",      (PyCFunction)long_getnewargs,   METH_NOARGS},
3678
3816
        {"__format__", (PyCFunction)long__format__, METH_VARARGS},
3679
3817
        {"__sizeof__",  (PyCFunction)long_sizeof, METH_NOARGS,
3728
3866
                        long_xor,       /*nb_xor*/
3729
3867
                        long_or,        /*nb_or*/
3730
3868
                        long_long,      /*nb_int*/
3731
 
                        long_long,      /*nb_long*/
 
3869
        0,                              /*nb_reserved*/
3732
3870
                        long_float,     /*nb_float*/
3733
3871
        0,                              /* nb_inplace_add */
3734
3872
        0,                              /* nb_inplace_subtract */
3758
3896
        0,                                      /* tp_print */
3759
3897
        0,                                      /* tp_getattr */
3760
3898
        0,                                      /* tp_setattr */
3761
 
        0,                                      /* tp_compare */
 
3899
        0,                                      /* tp_reserved */
3762
3900
        long_repr,                              /* tp_repr */
3763
3901
        &long_as_number,                        /* tp_as_number */
3764
3902
        0,                                      /* tp_as_sequence */