Fix RAND_RANGE for mt_rand

1 files changed, 54 insertions, 48 deletions

diff --git a/ext/standard/mt_rand.c b/ext/standard/mt_rand.c
index a684c5cf72..04f4f8ea0c 100644
--- a/ext/standard/mt_rand.c
+++ b/ext/standard/mt_rand.c
@@ -167,6 +167,10 @@ PHPAPI uint32_t php_mt_rand(void)
 
 	register uint32_t s1;
 
+	if (UNEXPECTED(!BG(mt_rand_is_seeded))) {
+		php_mt_srand(GENERATE_SEED());
+	}
+
 	if (BG(left) == 0) {
 		php_mt_reload();
 	}
@@ -196,31 +200,46 @@ PHP_FUNCTION(mt_srand)
 }
 /* }}} */
 
-/*
- * A bit of tricky math here.  We want to avoid using a modulus because
- * that simply tosses the high-order bits and might skew the distribution
- * of random values over the range.  Instead we map the range directly.
- *
- * We need to map the range from 0...M evenly to the range a...b
- * Let n = the random number and n' = the mapped random number
- *
- * Then we have: n' = a + n(b-a)/M
- *
- * We have a problem here in that only n==M will get mapped to b which
- # means the chances of getting b is much much less than getting any of
- # the other values in the range.  We can fix this by increasing our range
- # artificially and using:
- #
- #               n' = a + n(b-a+1)/M
- *
- # Now we only have a problem if n==M which would cause us to produce a
- # number of b+1 which would be bad.  So we bump M up by one to make sure
- # this will never happen, and the final algorithm looks like this:
- #
- #               n' = a + n(b-a+1)/(M+1)
- *
- * -RL
+/* {{{ php_mt_rand_range
  */
+PHPAPI zend_long php_mt_rand_range(zend_long min, zend_long max)
+{
+	zend_ulong umax = max - min;
+	zend_ulong limit;
+	zend_ulong result;
+
+#if ZEND_ULONG_MAX > UINT32_MAX
+	result = ((zend_ulong)php_mt_rand() << 32) | php_mt_rand();
+#else
+	result = php_mt_rand();
+#endif
+
+	/* Special case where no modulus is required */
+	if (UNEXPECTED(umax == ZEND_ULONG_MAX)) {
+		return (zend_long)result;
+	}
+
+	/* Increment the max so the range is inclusive of max */
+	umax++;
+
+	/* Powers of two are not biased */
+	if (EXPECTED((umax & (umax - 1)) != 0)) {
+		/* Ceiling under which ZEND_LONG_MAX % max == 0 */
+		limit = ZEND_ULONG_MAX - (ZEND_ULONG_MAX % umax) - 1;
+
+		/* Discard numbers over the limit to avoid modulo bias */
+		while (UNEXPECTED(result > limit)) {
+#if ZEND_ULONG_MAX > UINT32_MAX
+			result = (result << 32) | php_mt_rand();
+#else
+			result = php_mt_rand();
+#endif
+		}
+	}
+
+	return (zend_long)((result % umax) + min);
+}
+/* }}} */
 
 /* {{{ proto int mt_rand([int min, int max])
    Returns a random number from Mersenne Twister */
@@ -228,36 +247,23 @@ PHP_FUNCTION(mt_rand)
 {
 	zend_long min;
 	zend_long max;
-	zend_long number;
-	int  argc = ZEND_NUM_ARGS();
-
-	if (argc != 0) {
-		if (zend_parse_parameters(argc, "ll", &min, &max) == FAILURE) {
-			return;
-		} else if (max < min) {
-			php_error_docref(NULL, E_WARNING, "max(" ZEND_LONG_FMT ") is smaller than min(" ZEND_LONG_FMT ")", max, min);
-			RETURN_FALSE;
-		}
+	int argc = ZEND_NUM_ARGS();
+
+	if (argc == 0) {
+		// genrand_int31 in mt19937ar.c performs a right shift
+		RETURN_LONG(php_mt_rand() >> 1);
 	}
 
-	if (!BG(mt_rand_is_seeded)) {
-		php_mt_srand(GENERATE_SEED());
+	if (zend_parse_parameters(argc, "ll", &min, &max) == FAILURE) {
+		return;
 	}
 
-	/*
-	 * Melo: hmms.. randomMT() returns 32 random bits...
-	 * Yet, the previous php_rand only returns 31 at most.
-	 * So I put a right shift to loose the lsb. It *seems*
-	 * better than clearing the msb.
-	 * Update:
-	 * I talked with Cokus via email and it won't ruin the algorithm
-	 */
-	number = (zend_long) (php_mt_rand() >> 1);
-	if (argc == 2) {
-		RAND_RANGE(number, min, max, PHP_MT_RAND_MAX);
+	if (UNEXPECTED(max < min)) {
+		php_error_docref(NULL, E_WARNING, "max(" ZEND_LONG_FMT ") is smaller than min(" ZEND_LONG_FMT ")", max, min);
+		RETURN_FALSE;
 	}
 
-	RETURN_LONG(number);
+	RETURN_LONG(php_mt_rand_range(min, max));
 }
 /* }}} */