The random selection in function linear() could deliver a value equal to max

if geqo_rand() returns exactly 1.0, resulting in failure due to indexing
off the end of the pool array.  Also, since this is using inexact float math,
it seems wise to guard against roundoff error producing values slightly
outside the expected range.  Per report from bug@zedware.org.

1 files changed, 25 insertions, 12 deletions

diff --git a/src/backend/optimizer/geqo/geqo_selection.c b/src/backend/optimizer/geqo/geqo_selection.c
index f956759e7e..c6a635ac95 100644
--- a/src/backend/optimizer/geqo/geqo_selection.c
+++ b/src/backend/optimizer/geqo/geqo_selection.c
@@ -6,7 +6,7 @@
  * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: geqo_selection.c,v 1.12 2001/01/24 19:42:57 momjian Exp $
+ * $Id: geqo_selection.c,v 1.12.4.1 2005/06/14 14:21:43 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -43,10 +43,11 @@
 
 static int	linear(int max, double bias);
 
-/* geqo_selection
- *
+
+/*
+ * geqo_selection
  *	 according to bias described by input parameters,
- *	 second genes are selected from the pool
+ *	 first and second genes are selected from the pool
  */
 void
 geqo_selection(Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)
@@ -54,28 +55,27 @@ geqo_selection(Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)
 	int			first,
 				second;
 
-	first = (int) linear(pool->size, bias);
-	second = (int) linear(pool->size, bias);
+	first = linear(pool->size, bias);
+	second = linear(pool->size, bias);
 
 	if (pool->size > 1)
 	{
 		while (first == second)
-			second = (int) linear(pool->size, bias);
+			second = linear(pool->size, bias);
 	}
 
 	geqo_copy(momma, &pool->data[first], pool->string_length);
 	geqo_copy(daddy, &pool->data[second], pool->string_length);
 }
 
-/* linear
+/*
+ * linear
  *	  generates random integer between 0 and input max number
  *	  using input linear bias
  *
  *	  probability distribution function is: f(x) = bias - 2(bias - 1)x
  *			 bias = (prob of first rule) / (prob of middle rule)
- *
  */
-
 static int
 linear(int pool_size, double bias)		/* bias is y-intercept of linear
 										 * distribution */
@@ -83,8 +83,21 @@ linear(int pool_size, double bias)		/* bias is y-intercept of linear
 	double		index;			/* index between 0 and pop_size */
 	double		max = (double) pool_size;
 
-	index = max * (bias - sqrt((bias * bias) - 4.0 * (bias - 1.0) * geqo_rand()))
-		/ 2.0 / (bias - 1.0);
+	/*
+	 * If geqo_rand() returns exactly 1.0 then we will get exactly max from
+	 * this equation, whereas we need 0 <= index < max.  Also it seems possible
+	 * that roundoff error might deliver values slightly outside the range;
+	 * in particular avoid passing a value slightly less than 0 to sqrt().
+	 * If we get a bad value just try again.
+	 */
+	do {
+		double	sqrtval;
+
+		sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand();
+		if (sqrtval > 0.0)
+			sqrtval = sqrt(sqrtval);
+		index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
+	} while (index < 0.0 || index >= max);
 
 	return (int) index;
 }