From a13b109bc00487182b13c1d02c03e8910dfb9234 Mon Sep 17 00:00:00 2001 From: Mark Dickinson Date: Sun, 15 Apr 2012 16:30:35 +0100 Subject: Issue 13496: Fix bisect.bisect overflow bug for large collections. --- Lib/test/test_bisect.py | 7 +++++++ Misc/NEWS | 3 +++ Modules/_bisectmodule.c | 10 ++++++++-- 3 files changed, 18 insertions(+), 2 deletions(-) diff --git a/Lib/test/test_bisect.py b/Lib/test/test_bisect.py index 93b8613..c24a1a2 100644 --- a/Lib/test/test_bisect.py +++ b/Lib/test/test_bisect.py @@ -122,6 +122,13 @@ class TestBisect(unittest.TestCase): self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3), self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3), + def test_large_range(self): + # Issue 13496 + mod = self.module + data = range(sys.maxsize-1) + self.assertEqual(mod.bisect_left(data, sys.maxsize-3), sys.maxsize-3) + self.assertEqual(mod.bisect_right(data, sys.maxsize-3), sys.maxsize-2) + def test_random(self, n=25): from random import randrange for i in range(n): diff --git a/Misc/NEWS b/Misc/NEWS index b045742..91b0c65 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -43,6 +43,9 @@ Core and Builtins Library ------- +- Issue #13496: Fix potential overflow in bisect.bisect algorithm when applied + to a collection of size > sys.maxsize / 2. + - Issue #14399: zipfile now recognizes that the archive has been modified even if only the comment is changed. In addition, the TypeError that results from trying to set a non-binary value as a comment is now now raised at the time diff --git a/Modules/_bisectmodule.c b/Modules/_bisectmodule.c index 7fecfc6..93d0eed 100644 --- a/Modules/_bisectmodule.c +++ b/Modules/_bisectmodule.c @@ -21,7 +21,10 @@ internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t return -1; } while (lo < hi) { - mid = (lo + hi) / 2; + /* The (size_t)cast ensures that the addition and subsequent division + are performed as unsigned operations, avoiding difficulties from + signed overflow. (See issue 13496.) */ + mid = ((size_t)lo + hi) / 2; litem = PySequence_GetItem(list, mid); if (litem == NULL) return -1; @@ -121,7 +124,10 @@ internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t h return -1; } while (lo < hi) { - mid = (lo + hi) / 2; + /* The (size_t)cast ensures that the addition and subsequent division + are performed as unsigned operations, avoiding difficulties from + signed overflow. (See issue 13496.) */ + mid = ((size_t)lo + hi) / 2; litem = PySequence_GetItem(list, mid); if (litem == NULL) return -1; -- cgit v0.12