[libc] implement basic rand and srand

This provides the reference implementation of rand and srand. In future
this will likely be upgraded to something that supports full ints.

Reviewed By: sivachandra

Differential Revision: https://reviews.llvm.org/D135187

16 files changed, 224 insertions, 0 deletions

diff --git a/libc/config/linux/x86_64/entrypoints.txt b/libc/config/linux/x86_64/entrypoints.txt
index c7e6c73..3948220 100644
--- a/libc/config/linux/x86_64/entrypoints.txt
+++ b/libc/config/linux/x86_64/entrypoints.txt
@@ -82,6 +82,8 @@ set(TARGET_LIBC_ENTRYPOINTS
     libc.src.stdlib.llabs
     libc.src.stdlib.lldiv
     libc.src.stdlib.qsort
+    libc.src.stdlib.rand
+    libc.src.stdlib.srand
     libc.src.stdlib.strtod
     libc.src.stdlib.strtof
     libc.src.stdlib.strtol
diff --git a/libc/include/CMakeLists.txt b/libc/include/CMakeLists.txt
index 3998d72..88018ba 100644
--- a/libc/include/CMakeLists.txt
+++ b/libc/include/CMakeLists.txt
@@ -157,6 +157,7 @@ add_gen_header(
   GEN_HDR stdlib.h
   DEPENDS
     .llvm_libc_common_h
+    .llvm-libc-macros.stdlib_macros
     .llvm-libc-types.__bsearchcompare_t
     .llvm-libc-types.__qsortcompare_t
     .llvm-libc-types.div_t
diff --git a/libc/include/llvm-libc-macros/CMakeLists.txt b/libc/include/llvm-libc-macros/CMakeLists.txt
index 740802c..f0d297d 100644
--- a/libc/include/llvm-libc-macros/CMakeLists.txt
+++ b/libc/include/llvm-libc-macros/CMakeLists.txt
@@ -23,6 +23,12 @@ add_header(
 )
 
 add_header(
+  stdlib_macros
+  HDR
+    stdlib-macros.h
+)
+
+add_header(
   sys_stat_macros
   HDR
     sys-stat-macros.h
diff --git a/libc/include/llvm-libc-macros/stdlib-macros.h b/libc/include/llvm-libc-macros/stdlib-macros.h
new file mode 100644
index 0000000..930938d
--- /dev/null
+++ b/libc/include/llvm-libc-macros/stdlib-macros.h
@@ -0,0 +1,14 @@
+//===-- Definition of macros to be used with stdlib functions ----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef __LLVM_LIBC_MACROS_STDLIB_MACROS_H
+#define __LLVM_LIBC_MACROS_STDLIB_MACROS_H
+
+#define RAND_MAX 32767
+
+#endif // __LLVM_LIBC_MACROS_STDLIB_MACROS_H
diff --git a/libc/include/stdlib.h.def b/libc/include/stdlib.h.def
index f4f8c4f..18df71a 100644
--- a/libc/include/stdlib.h.def
+++ b/libc/include/stdlib.h.def
@@ -10,6 +10,7 @@
 #define LLVM_LIBC_STDLIB_H
 
 #include <__llvm-libc-common.h>
+#include <llvm-libc-macros/stdlib-macros.h>
 
 %%public_api()
 
diff --git a/libc/spec/spec.td b/libc/spec/spec.td
index 10c34b9..87974ec 100644
--- a/libc/spec/spec.td
+++ b/libc/spec/spec.td
@@ -39,6 +39,7 @@ class RestrictedPtrType<Type type> : Type {
 def VarArgType : NamedType<"...">;
 def VoidType : NamedType<"void">;
 def IntType : NamedType<"int">;
+def UnsignedIntType : NamedType<"unsigned int">;
 def LongType : NamedType<"long">;
 def UnsignedLongType : NamedType<"unsigned long">;
 def LongLongType : NamedType<"long long">;
diff --git a/libc/spec/stdc.td b/libc/spec/stdc.td
index 11d21ad..8672811 100644
--- a/libc/spec/stdc.td
+++ b/libc/spec/stdc.td
@@ -648,6 +648,9 @@ def StdC : StandardSpec<"stdc"> {
 
           FunctionSpec<"qsort", RetValSpec<VoidType>, [ArgSpec<VoidPtr>, ArgSpec<SizeTType>, ArgSpec<SizeTType>, ArgSpec<QSortCompareT>]>,
 
+          FunctionSpec<"rand", RetValSpec<IntType>, [ArgSpec<VoidType>]>,
+          FunctionSpec<"srand", RetValSpec<VoidType>, [ArgSpec<UnsignedIntType>]>,
+
           FunctionSpec<"strtof", RetValSpec<FloatType>, [ArgSpec<ConstCharRestrictedPtr>, ArgSpec<CharRestrictedPtrPtr>]>,
           FunctionSpec<"strtod", RetValSpec<DoubleType>, [ArgSpec<ConstCharRestrictedPtr>, ArgSpec<CharRestrictedPtrPtr>]>,
           FunctionSpec<"strtold", RetValSpec<LongDoubleType>, [ArgSpec<ConstCharRestrictedPtr>, ArgSpec<CharRestrictedPtrPtr>]>,
diff --git a/libc/src/stdlib/CMakeLists.txt b/libc/src/stdlib/CMakeLists.txt
index 7daecd9..b067e84 100644
--- a/libc/src/stdlib/CMakeLists.txt
+++ b/libc/src/stdlib/CMakeLists.txt
@@ -201,6 +201,36 @@ add_entrypoint_object(
     libc.include.stdlib
 )
 
+add_object_library(
+  rand_util
+  SRCS
+    rand_util.cpp
+  HDRS
+    rand_util.h
+)
+
+add_entrypoint_object(
+  rand
+  SRCS
+    rand.cpp
+  HDRS
+    rand.h
+  DEPENDS
+    .rand_util
+    libc.include.stdlib
+)
+
+add_entrypoint_object(
+  srand
+  SRCS
+    srand.cpp
+  HDRS
+    srand.h
+  DEPENDS
+    .rand_util
+    libc.include.stdlib
+)
+
 if(LLVM_LIBC_INCLUDE_SCUDO)
   set(SCUDO_DEPS "")
 
diff --git a/libc/src/stdlib/rand.cpp b/libc/src/stdlib/rand.cpp
new file mode 100644
index 0000000..ef6a721
--- /dev/null
+++ b/libc/src/stdlib/rand.cpp
@@ -0,0 +1,22 @@
+//===-- Implementation of rand --------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/stdlib/rand.h"
+#include "src/__support/common.h"
+#include "src/stdlib/rand_util.h"
+
+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);
+}
+
+} // namespace __llvm_libc
diff --git a/libc/src/stdlib/rand.h b/libc/src/stdlib/rand.h
new file mode 100644
index 0000000..3f37c57
--- /dev/null
+++ b/libc/src/stdlib/rand.h
@@ -0,0 +1,20 @@
+//===-- Implementation header for rand --------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <stdlib.h>
+
+#ifndef LLVM_LIBC_SRC_STDLIB_RAND_H
+#define LLVM_LIBC_SRC_STDLIB_RAND_H
+
+namespace __llvm_libc {
+
+int rand(void);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STDLIB_RAND_H
diff --git a/libc/src/stdlib/rand_util.cpp b/libc/src/stdlib/rand_util.cpp
new file mode 100644
index 0000000..afa6662
--- /dev/null
+++ b/libc/src/stdlib/rand_util.cpp
@@ -0,0 +1,15 @@
+//===-- Shared utility for rand -------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/stdlib/rand_util.h"
+
+namespace __llvm_libc {
+
+thread_local unsigned long rand_next;
+
+} // namespace __llvm_libc
diff --git a/libc/src/stdlib/rand_util.h b/libc/src/stdlib/rand_util.h
new file mode 100644
index 0000000..6179406
--- /dev/null
+++ b/libc/src/stdlib/rand_util.h
@@ -0,0 +1,18 @@
+//===-- Implementation header for rand utilities ----------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_STDLIB_RAND_UTIL_H
+#define LLVM_LIBC_SRC_STDLIB_RAND_UTIL_H
+
+namespace __llvm_libc {
+
+extern thread_local unsigned long rand_next;
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STDLIB_RAND_UTIL_H
diff --git a/libc/src/stdlib/srand.cpp b/libc/src/stdlib/srand.cpp
new file mode 100644
index 0000000..d93d867
--- /dev/null
+++ b/libc/src/stdlib/srand.cpp
@@ -0,0 +1,17 @@
+//===-- Implementation of srand -------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/stdlib/srand.h"
+#include "src/__support/common.h"
+#include "src/stdlib/rand_util.h"
+
+namespace __llvm_libc {
+
+LLVM_LIBC_FUNCTION(void, srand, (unsigned int seed)) { rand_next = seed; }
+
+} // namespace __llvm_libc
diff --git a/libc/src/stdlib/srand.h b/libc/src/stdlib/srand.h
new file mode 100644
index 0000000..86228b7
--- /dev/null
+++ b/libc/src/stdlib/srand.h
@@ -0,0 +1,20 @@
+//===-- Implementation header for srand -------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <stdlib.h>
+
+#ifndef LLVM_LIBC_SRC_STDLIB_SRAND_H
+#define LLVM_LIBC_SRC_STDLIB_SRAND_H
+
+namespace __llvm_libc {
+
+void srand(unsigned int seed);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STDLIB_SRAND_H
diff --git a/libc/test/src/stdlib/CMakeLists.txt b/libc/test/src/stdlib/CMakeLists.txt
index c31c23c..c05bb94d 100644
--- a/libc/test/src/stdlib/CMakeLists.txt
+++ b/libc/test/src/stdlib/CMakeLists.txt
@@ -202,6 +202,18 @@ add_libc_unittest(
     libc.src.stdlib.qsort
 )
 
+add_libc_unittest(
+  rand_test
+  SUITE
+    libc_stdlib_unittests
+  SRCS
+    rand_test.cpp
+  DEPENDS
+    libc.include.stdlib
+    libc.src.stdlib.rand
+    libc.src.stdlib.srand
+)
+
 if(LLVM_LIBC_FULL_BUILD)
 
   add_libc_unittest(
diff --git a/libc/test/src/stdlib/rand_test.cpp b/libc/test/src/stdlib/rand_test.cpp
new file mode 100644
index 0000000..5b03839
--- /dev/null
+++ b/libc/test/src/stdlib/rand_test.cpp
@@ -0,0 +1,42 @@
+//===-- Unittests for rand ------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/stdlib/rand.h"
+#include "src/stdlib/srand.h"
+#include "utils/UnitTest/Test.h"
+
+#include <stddef.h>
+#include <stdlib.h>
+
+TEST(LlvmLibcRandTest, UnsetSeed) {
+  for (size_t i = 0; i < 1000; ++i) {
+    int val = __llvm_libc::rand();
+    ASSERT_GE(val, 0);
+    ASSERT_LE(val, RAND_MAX);
+  }
+}
+
+TEST(LlvmLibcRandTest, SetSeed) {
+  const unsigned int SEED = 12344321;
+  __llvm_libc::srand(SEED);
+  const size_t NUM_RESULTS = 10;
+  int results[NUM_RESULTS];
+  for (size_t i = 0; i < NUM_RESULTS; ++i) {
+    results[i] = __llvm_libc::rand();
+    ASSERT_GE(results[i], 0);
+    ASSERT_LE(results[i], RAND_MAX);
+  }
+
+  // If the seed is set to the same value, it should give the same sequence.
+  __llvm_libc::srand(SEED);
+
+  for (size_t i = 0; i < NUM_RESULTS; ++i) {
+    int val = __llvm_libc::rand();
+    EXPECT_EQ(results[i], val);
+  }
+}