diff options
| author | Tim Peters <tim.peters@gmail.com> | 2002-08-12 19:30:26 (GMT) |
|---|---|---|
| committer | Tim Peters <tim.peters@gmail.com> | 2002-08-12 19:30:26 (GMT) |
| commit | d8b2173ef97edecadcc171dc5fce95ee13ee9d3d (patch) | |
| tree | c8ef60a075973bfecf6b8e67c6eb8ad40e8f4eae | |
| parent | 3747a0f04c1dbe5abb47ce80abea39ed02c01aa2 (diff) | |
| download | cpython-d8b2173ef97edecadcc171dc5fce95ee13ee9d3d.zip cpython-d8b2173ef97edecadcc171dc5fce95ee13ee9d3d.tar.gz cpython-d8b2173ef97edecadcc171dc5fce95ee13ee9d3d.tar.bz2 | |
k_mul(): White-box testing turned up that (ah+al)*(bh+bl) can, in rare
cases, overflow the allocated result object by 1 bit. In such cases,
it would have been brought back into range if we subtracted al*bl and
ah*bh from it first, but I don't want to do that because it hurts cache
behavior. Instead we just ignore the excess bit when it appears -- in
effect, this is forcing unsigned mod BASE**(asize + bsize) arithmetic
in a case where that doesn't happen all by itself.
| -rw-r--r-- | Objects/longobject.c | 14 |
1 files changed, 11 insertions, 3 deletions
diff --git a/Objects/longobject.c b/Objects/longobject.c index 0801e64..0f4910e 100644 --- a/Objects/longobject.c +++ b/Objects/longobject.c @@ -1663,7 +1663,7 @@ k_mul(PyLongObject *a, PyLongObject *b) */ /* 1. Allocate result space. */ - ret = _PyLong_New(asize + bsize); + ret = _PyLong_New(asize + bsize + 1); if (ret == NULL) goto fail; #ifdef Py_DEBUG /* Fill with trash, to catch reference to uninitialized digits. */ @@ -1727,7 +1727,15 @@ k_mul(PyLongObject *a, PyLongObject *b) Py_DECREF(t2); if (t3 == NULL) goto fail; - /* Add t3. */ + /* Add t3. Caution: t3 can spill one bit beyond the allocated + * result space; it's t3-al*bl-ah*bh that always fits. We have + * to arrange to ignore the hight bit. + */ + if (t3->ob_size > i) { + assert(t3->ob_size == i+1); /* just one digit over */ + assert(t3->ob_digit[t3->ob_size - 1] == 1); /* & just one bit */ + --t3->ob_size; /* ignore the overflow bit */ + } (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, t3->ob_size); Py_DECREF(t3); @@ -1761,7 +1769,7 @@ long_mul(PyLongObject *v, PyLongObject *w) return Py_NotImplemented; } -#if 0 +#if 1 if (Py_GETENV("KARAT") != NULL) z = k_mul(a, b); else |