(svn r22302) -Codechange: Replace a linear search with a binary search.

1 files changed, 12 insertions, 1 deletions

diff --git a/src/blitter/base.cpp b/src/blitter/base.cpp
index 312ec1025..d8e33cede 100644
--- a/src/blitter/base.cpp
+++ b/src/blitter/base.cpp
@@ -50,8 +50,19 @@ void Blitter::DrawLine(void *video, int x, int y, int x2, int y2, int screen_wid
 
 	int frac_diff = width * max(dx, dy);
 	if (width > 1) {
+		/* compute frac_diff = width * sqrt(dx*dx + dy*dy)
+		 * Start interval:
+		 *    max(dx, dy) <= sqrt(dx*dx + dy*dy) <= sqrt(2) * max(dx, dy) <= 3/2 * max(dx, dy) */
 		int frac_sq = width * width * (dx * dx + dy * dy);
-		while (frac_diff * frac_diff < frac_sq) frac_diff++;
+		int frac_max = 3 * frac_diff / 2;
+		while (frac_diff < frac_max) {
+			int frac_test = (frac_diff + frac_max) / 2;
+			if (frac_test * frac_test < frac_sq) {
+				frac_diff = frac_test + 1;
+			} else {
+				frac_max = frac_test - 1;
+			}
+		}
 	}
 
 	if (dx > dy) {