[libc] Improve the implementation of the rand() function (#66131)

Summary:
This patch improves the implementation of the standard `rand()` function
by implementing it in terms of the xorshift64star pRNG as described in
https://en.wikipedia.org/wiki/Xorshift#xorshift*. This is a good,
general purpose random number generator that is sufficient for most
applications that do not require an extremely long period. This patch
also correctly initializes the seed to be `1` as described by the
standard. We also increase the `RAND_MAX` value to be `INT_MAX` as the
standard only specifies that it can be larger than 32768.

4 files changed, 21 insertions, 7 deletions

diff --git a/libc/include/llvm-libc-macros/stdlib-macros.h b/libc/include/llvm-libc-macros/stdlib-macros.h
index 1c66a43..a7625aa 100644
--- a/libc/include/llvm-libc-macros/stdlib-macros.h
+++ b/libc/include/llvm-libc-macros/stdlib-macros.h
@@ -17,6 +17,6 @@
 #define EXIT_SUCCESS 0
 #define EXIT_FAILURE 1
 
-#define RAND_MAX 32767
+#define RAND_MAX 2147483647
 
 #endif // __LLVM_LIBC_MACROS_STDLIB_MACROS_H
diff --git a/libc/src/stdlib/rand.cpp b/libc/src/stdlib/rand.cpp
index ef6a721..771944f 100644
--- a/libc/src/stdlib/rand.cpp
+++ b/libc/src/stdlib/rand.cpp
@@ -12,11 +12,13 @@
 
 namespace __llvm_libc {
 
-// This rand function is the example implementation from the C standard. It is
-// not cryptographically secure.
-LLVM_LIBC_FUNCTION(int, rand, (void)) { // RAND_MAX is assumed to be 32767
-  rand_next = rand_next * 1103515245 + 12345;
-  return static_cast<unsigned int>((rand_next / 65536) % 32768);
+// An implementation of the xorshift64star pseudo random number generator. This
+// is a good general purpose generator for most non-cryptographics applications.
+LLVM_LIBC_FUNCTION(int, rand, (void)) {
+  rand_next ^= rand_next >> 12;
+  rand_next ^= rand_next << 25;
+  rand_next ^= rand_next >> 27;
+  return static_cast<int>((rand_next * 0x2545F4914F6CDD1Dul) >> 32) & RAND_MAX;
 }
 
 } // namespace __llvm_libc
diff --git a/libc/src/stdlib/rand_util.cpp b/libc/src/stdlib/rand_util.cpp
index 9c29eb8..dac8dca 100644
--- a/libc/src/stdlib/rand_util.cpp
+++ b/libc/src/stdlib/rand_util.cpp
@@ -11,6 +11,8 @@
 
 namespace __llvm_libc {
 
-LIBC_THREAD_LOCAL unsigned long rand_next;
+// C standard 7.10p2: If 'rand' is called before 'srand' it is to proceed as if
+// the 'srand' function was called with a value of '1'.
+LIBC_THREAD_LOCAL unsigned long rand_next = 1;
 
 } // namespace __llvm_libc
diff --git a/libc/test/src/stdlib/rand_test.cpp b/libc/test/src/stdlib/rand_test.cpp
index fcd693c..4bebbe3 100644
--- a/libc/test/src/stdlib/rand_test.cpp
+++ b/libc/test/src/stdlib/rand_test.cpp
@@ -14,11 +14,21 @@
 #include <stdlib.h>
 
 TEST(LlvmLibcRandTest, UnsetSeed) {
+  static int vals[1000];
+
   for (size_t i = 0; i < 1000; ++i) {
     int val = __llvm_libc::rand();
     ASSERT_GE(val, 0);
     ASSERT_LE(val, RAND_MAX);
+    vals[i] = val;
   }
+
+  // The C standard specifies that if 'srand' is never called it should behave
+  // as if 'srand' was called with a value of 1. If we seed the value with 1 we
+  // should get the same sequence as the unseeded version.
+  __llvm_libc::srand(1);
+  for (size_t i = 0; i < 1000; ++i)
+    ASSERT_EQ(__llvm_libc::rand(), vals[i]);
 }
 
 TEST(LlvmLibcRandTest, SetSeed) {