From c8034514edadbafc4376f107e2a4ba52b7b17ff4 Mon Sep 17 00:00:00 2001
From: Nikita Popov <nikita.ppv@gmail.com>
Date: Sun, 2 Apr 2017 13:19:32 +0200
Subject: [PATCH] Fixed bug #74361

---
 NEWS                                     |  3 +++
 ext/standard/array.c                     | 27 +++++++++++++++---------
 ext/standard/tests/array/bug74361.phpt   | 11 ++++++++++
 ext/standard/tests/array/bug74361_2.phpt | 24 +++++++++++++++++++++
 4 files changed, 55 insertions(+), 10 deletions(-)
 create mode 100644 ext/standard/tests/array/bug74361.phpt
 create mode 100644 ext/standard/tests/array/bug74361_2.phpt

diff --git a/NEWS b/NEWS
index a655dd36e0..635a51b835 100644
--- a/NEWS
+++ b/NEWS
@@ -13,6 +13,9 @@ PHP                                                                        NEWS
   . Fixed bug #74341 (openssl_x509_parse fails to parse ASN.1 UTCTime without
     seconds). (Moritz Fain)
 
+- Standard:
+  . Fixed bug #74361 (Compaction in array_rand() violates COW). (Nikita)
+
 13 Apr 2017, PHP 7.1.4
 
 - Core:
diff --git a/ext/standard/array.c b/ext/standard/array.c
index 0dd0f3a98d..966e0a3af2 100644
--- a/ext/standard/array.c
+++ b/ext/standard/array.c
@@ -5016,19 +5016,26 @@ PHP_FUNCTION(array_rand)
 	if (num_req == 1) {
 		HashTable *ht = Z_ARRVAL_P(input);
 
-		/* Compact the hashtable if less than 3/4 of elements are used */
-		if (num_avail < ht->nNumUsed - (ht->nNumUsed>>2)) {
-			if (ht->u.flags & HASH_FLAG_PACKED) {
-				zend_hash_packed_to_hash(ht);
-			} else {
-				zend_hash_rehash(ht);
-			}
+		if (num_avail < ht->nNumUsed - (ht->nNumUsed>>1)) {
+			/* If less than 1/2 of elements are used, don't sample. Instead search for a
+			 * specific offset using linear scan. */
+			zend_long i = 0, randval = php_mt_rand_range(0, num_avail - 1);
+			ZEND_HASH_FOREACH_KEY(Z_ARRVAL_P(input), num_key, string_key) {
+				if (i == randval) {
+					if (string_key) {
+						RETURN_STR_COPY(string_key);
+					} else {
+						RETURN_LONG(num_key);
+					}
+				}
+				i++;
+			} ZEND_HASH_FOREACH_END();
 		}
 
 		/* Sample random buckets until we hit one that is not empty.
-		 * The worst case probability of hitting an empty element is 1-3/4. The worst case
-		 * probability of hitting N empty elements in a row is (1-3/4)**N.
-		 * For N=5 this becomes smaller than 0.1%. */
+		 * The worst case probability of hitting an empty element is 1-1/2. The worst case
+		 * probability of hitting N empty elements in a row is (1-1/2)**N.
+		 * For N=10 this becomes smaller than 0.1%. */
 		do {
 			zend_long randval = php_mt_rand_range(0, ht->nNumUsed - 1);
 			Bucket *bucket = &ht->arData[randval];
diff --git a/ext/standard/tests/array/bug74361.phpt b/ext/standard/tests/array/bug74361.phpt
new file mode 100644
index 0000000000..6e7459024c
--- /dev/null
+++ b/ext/standard/tests/array/bug74361.phpt
@@ -0,0 +1,11 @@
+--TEST--
+Bug #74361: Compaction in array_rand() violates COW
+--FILE--
+<?php
+
+$array = [4 => 4];
+var_dump(array_rand($array));
+
+?>
+--EXPECT--
+int(4)
diff --git a/ext/standard/tests/array/bug74361_2.phpt b/ext/standard/tests/array/bug74361_2.phpt
new file mode 100644
index 0000000000..4f4bdcf5a4
--- /dev/null
+++ b/ext/standard/tests/array/bug74361_2.phpt
@@ -0,0 +1,24 @@
+--TEST--
+Bug #74361: Compaction in array_rand() violates COW (variation)
+--FILE--
+<?php
+
+$array = range(0, 15);
+for ($i = 0; $i <= 8; $i++) {
+    unset($array[$i]);
+}
+
+foreach ($array as $x) {
+    var_dump($x);
+    array_rand($array, 1);
+}
+
+?>
+--EXPECT--
+int(9)
+int(10)
+int(11)
+int(12)
+int(13)
+int(14)
+int(15)
-- 
2.50.1