[m-rev.] for review: fix possible integer overflow in binary search

[Sebastian Godelet]

In this discussion:
http://www.mercurylang.org/list-archives/reviews/2014-December/017547.html
It was argued that an integer overflow for calculating Mid cannot
happen:
> If you are worried about integer overflow when calculating Mid,
> the standard fix for that is to compute it as Lo + (Hi - Lo) / 2.
> However, since all our ints are signed, there is no need for that;
But in the current Mercury implementation this is not the case,
as demonstrated in this gist:
https://gist.github.com/sebgod/ee1172fd736289aaeaa8

The implementations in the specific grades are taken from this
article:
http://googleresearch.blogspot.de/2006/06/extra-extra-read-all-about-it-nearly.html
But this diff uses the
> the standard fix for that is to compute it as Lo + (Hi - Lo) / 2.
together with the >> 1 optimisation.
Maybe a mid_rounding_down/2 or similar could be included in the int
module.

library/array.m:
library/bt_array.m:
    see above.

Sebastian.

--

diff --git a/library/array.m b/library/array.m
index 4beecec..baf978d 100644
--- a/library/array.m
+++ b/library/array.m
@@ -2078,7 +2078,10 @@ array.bsearch_2(Array, Lo, Hi, El, Compare,
Result) :- ;
             % Otherwise find the middle element of the range
             % and check against that.
-            Mid = (Lo + Hi) >> 1,   % `>> 1' is hand-optimized `div 2'.
+            % NOTE: Use Lo + (Hi - Lo) >> 1 instead of (Lo + Hi) >> 1
to
+            % prevent an integer overflow.
+
+            Mid = Lo + (Hi - Lo) >> 1,   % `>> 1' is hand-optimized
`div 2'. array.lookup(Array, Mid, XMid),
             Compare(XMid, El, Comp),
             (
diff --git a/library/bt_array.m b/library/bt_array.m
index 315b62e..3fec7a7 100644
--- a/library/bt_array.m
+++ b/library/bt_array.m
@@ -417,8 +417,10 @@ bsearch_2(A, Lo, Hi, El, Compare, I) :-
         % little more expensive, and we know that we're always dividing
         % by a power of 2. Until such time as we implement strength
reduction, % the >> 1 stays.
+        % NOTE: Use Lo + (Hi - Lo) >> 1 instead of (Lo + Hi) >> 1 to
prevent
+        % an integer overlow.
 
-        Mid = (Lo + Hi) >> 1,
+        Mid = Lo + (Hi - Lo) >> 1,
         lookup(A, Mid, XMid),
         Compare(XMid, El, Comp),
         ( Comp = (<),