[libc] implement basic rand and srand

[michaelrj]

Summary

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

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.stdlib.atoll
     libc.src.stdlib.bsearch
     libc.src.stdlib.div
     libc.src.stdlib.labs
     libc.src.stdlib.ldiv
     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
     libc.src.stdlib.strtold
     libc.src.stdlib.strtoll
     libc.src.stdlib.strtoul
     libc.src.stdlib.strtoull
 

libc/include/CMakeLists.txt

 )
 
 add_gen_header(
   stdlib
   DEF_FILE stdlib.h.def
   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
     .llvm-libc-types.ldiv_t
     .llvm-libc-types.lldiv_t
     .llvm-libc-types.size_t
     .llvm-libc-types.__atexithandler_t
 )

libc/include/llvm-libc-macros/CMakeLists.txt

add_header(
   signal_macros
   HDR
     signal-macros.h
   DEPENDS
     .linux.signal_macros
 )
 
 add_header(
+  stdlib_macros
+  HDR
+    stdlib-macros.h
+)
+
+add_header(
   sys_stat_macros
   HDR
     sys-stat-macros.h
   DEPENDS
     .linux.sys_stat_macros
 )
 
 add_header(

libc/include/llvm-libc-macros/stdlib-macros.h

-//===-- C standard library header stdlib.h --------------------------------===//
+//===-- 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_STDLIB_H
-#define LLVM_LIBC_STDLIB_H
+#ifndef __LLVM_LIBC_MACROS_STDLIB_MACROS_H
+#define __LLVM_LIBC_MACROS_STDLIB_MACROS_H
 
-#include <__llvm-libc-common.h>
+#define RAND_MAX 32767
 
-%%public_api()
-
-#endif // LLVM_LIBC_STDLIB_H
+#endif // __LLVM_LIBC_MACROS_STDLIB_MACROS_H

libc/include/stdlib.h.def

 //===-- C standard library header stdlib.h --------------------------------===//
 //
 // 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_STDLIB_H
 #define LLVM_LIBC_STDLIB_H
 
 #include <__llvm-libc-common.h>
+#include <llvm-libc-macros/stdlib-macros.h>
 
 %%public_api()
 
 #endif // LLVM_LIBC_STDLIB_H

libc/spec/spec.td

 class RestrictedPtrType<Type type> : Type {
   Type PointeeType = type;
 }
 
 // Builtin types.
 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">;
 def UnsignedLongLongType : NamedType<"unsigned long long">;
 def FloatType : NamedType<"float">;
 def DoubleType : NamedType<"double">;
 def LongDoubleType : NamedType<"long double">;
 def CharType : NamedType<"char">;

libc/spec/stdc.td

HeaderSpec StdLib = HeaderSpec<
           FunctionSpec<"atoll", RetValSpec<LongLongType>, [ArgSpec<ConstCharPtr>]>,
 
           FunctionSpec<"div", RetValSpec<DivTType>, [ArgSpec<IntType>, ArgSpec<IntType>]>,
           FunctionSpec<"ldiv", RetValSpec<LDivTType>, [ArgSpec<LongType>, ArgSpec<LongType>]>,
           FunctionSpec<"lldiv", RetValSpec<LLDivTType>, [ArgSpec<LongLongType>, ArgSpec<LongLongType>]>,
 
           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>]>,
           FunctionSpec<"strtol", RetValSpec<LongType>, [ArgSpec<ConstCharRestrictedPtr>, ArgSpec<CharRestrictedPtrPtr>, ArgSpec<IntType>]>,
           FunctionSpec<"strtoll", RetValSpec<LongLongType>, [ArgSpec<ConstCharRestrictedPtr>, ArgSpec<CharRestrictedPtrPtr>, ArgSpec<IntType>]>,
           FunctionSpec<"strtoul", RetValSpec<UnsignedLongType>, [ArgSpec<ConstCharRestrictedPtr>, ArgSpec<CharRestrictedPtrPtr>, ArgSpec<IntType>]>,
           FunctionSpec<"strtoull", RetValSpec<UnsignedLongLongType>, [ArgSpec<ConstCharRestrictedPtr>, ArgSpec<CharRestrictedPtrPtr>, ArgSpec<IntType>]>,
 

libc/src/stdlib/CMakeLists.txt

add_entrypoint_object(
   SRCS
     qsort.cpp
   HDRS
     qsort.h
   DEPENDS
     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 "")
 
   include(${LIBC_SOURCE_DIR}/../compiler-rt/cmake/Modules/AllSupportedArchDefs.cmake)
   if(NOT (LIBC_TARGET_ARCHITECTURE IN_LIST ALL_SCUDO_STANDALONE_SUPPORTED_ARCH))
     message(FATAL_ERROR "Architecture ${LIBC_TARGET_ARCHITECTURE} is not supported by SCUDO. 
       Either disable LLVM_LIBC_INCLUDE_SCUDO or change your target architecture.")
   endif()

libc/src/stdlib/rand.h

-//===-- C standard library header stdlib.h --------------------------------===//
+//===-- 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
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_LIBC_STDLIB_H
-#define LLVM_LIBC_STDLIB_H
+#include <stdlib.h>
 
-#include <__llvm-libc-common.h>
+#ifndef LLVM_LIBC_SRC_STDLIB_RAND_H
+#define LLVM_LIBC_SRC_STDLIB_RAND_H
 
-%%public_api()
+namespace __llvm_libc {
 
-#endif // LLVM_LIBC_STDLIB_H
+int rand(void);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STDLIB_RAND_H

libc/src/stdlib/rand.cpp

+//===-- 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

libc/src/stdlib/rand_util.h

+//===-- 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

libc/src/stdlib/rand_util.cpp

-//===-- C standard library header stdlib.h --------------------------------===//
+//===-- 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
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_LIBC_STDLIB_H
-#define LLVM_LIBC_STDLIB_H
+#include "src/stdlib/rand_util.h"
 
-#include <__llvm-libc-common.h>
+namespace __llvm_libc {
 
-%%public_api()
+thread_local unsigned long rand_next;
 
-#endif // LLVM_LIBC_STDLIB_H
+} // namespace __llvm_libc

libc/src/stdlib/srand.h

+//===-- 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

libc/src/stdlib/srand.cpp

-//===-- C standard library header stdlib.h --------------------------------===//
+//===-- 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
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_LIBC_STDLIB_H
-#define LLVM_LIBC_STDLIB_H
+#include "src/stdlib/srand.h"
+#include "src/__support/common.h"
+#include "src/stdlib/rand_util.h"
 
-#include <__llvm-libc-common.h>
+namespace __llvm_libc {
 
-%%public_api()
+LLVM_LIBC_FUNCTION(void, srand, (unsigned int seed)) { rand_next = seed; }
 
-#endif // LLVM_LIBC_STDLIB_H
+} // namespace __llvm_libc

libc/test/src/stdlib/CMakeLists.txt

SUITE
     libc_stdlib_unittests
   SRCS
     qsort_test.cpp
   DEPENDS
     libc.include.stdlib
     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(
     _Exit_test
     SUITE
       libc_stdlib_unittests
     SRCS
       _Exit_test.cpp

libc/test/src/stdlib/rand_test.cpp

+//===-- 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);
+  }
+}