Avoid use of rand()

8 files changed, 83 insertions, 69 deletions

diff --git a/benchmark/.clang-tidy b/benchmark/.clang-tidy
index 06febc0..2c16e13 100644
--- a/benchmark/.clang-tidy
+++ b/benchmark/.clang-tidy
@@ -7,10 +7,6 @@ Checks: >
   -bugprone-suspicious-string-compare,
   -cert-dcl37-c,
   -cert-dcl51-cpp,
-  -cert-msc30-c,
-  -cert-msc32-c,
-  -cert-msc50-cpp,
-  -cert-msc51-cpp,
   -clang-analyzer-security.insecureAPI.DeprecatedOrUnsafeBufferHandling,
   -hicpp-multiway-paths-covered,
   -llvm-header-guard,
diff --git a/benchmark/dict_bench.c b/benchmark/dict_bench.c
index 4a82a8f..4a77257 100644
--- a/benchmark/dict_bench.c
+++ b/benchmark/dict_bench.c
@@ -39,6 +39,16 @@ typedef struct {
   size_t len;
 } ZixChunk;
 
+/// Linear Congruential Generator for making random 64-bit integers
+static inline uint64_t
+lcg64(const uint64_t i)
+{
+  static const uint64_t a = 6364136223846793005ull;
+  static const uint64_t c = 1ull;
+
+  return (a * i) + c;
+}
+
 static uint32_t
 zix_chunk_hash(const ZixChunk* const chunk)
 {
@@ -151,10 +161,9 @@ main(int argc, char** argv)
     // Benchmark search
 
     // GHashTable
-    srand(seed);
     struct timespec search_start = bench_start();
     for (size_t i = 0; i < n; ++i) {
-      const size_t index = rand() % n;
+      const size_t index = lcg64(seed + i) % n;
       char*        match = (char*)g_hash_table_lookup(hash, strings[index]);
       if (strcmp(match, strings[index])) {
         return test_fail("Bad match for `%s'\n", strings[index]);
@@ -163,10 +172,9 @@ main(int argc, char** argv)
     fprintf(search_dat, "\t%lf", bench_end(&search_start));
 
     // ZixHash
-    srand(seed);
     search_start = bench_start();
     for (size_t i = 0; i < n; ++i) {
-      const size_t    index = rand() % n;
+      const size_t    index = lcg64(seed + i) % n;
       const ZixChunk  key   = {strings[index], lengths[index] + 1};
       const ZixChunk* match = NULL;
       if (!(match = (const ZixChunk*)zix_hash_find(zhash, &key))) {
diff --git a/benchmark/tree_bench.c b/benchmark/tree_bench.c
index bd274b1..9e399ba 100644
--- a/benchmark/tree_bench.c
+++ b/benchmark/tree_bench.c
@@ -17,6 +17,8 @@
 #include "bench.h"
 #include "warnings.h"
 
+#include "../test/test_data.h"
+
 #include "zix/btree.h"
 #include "zix/common.h"
 #include "zix/tree.h"
@@ -35,22 +37,6 @@ ZIX_RESTORE_WARNINGS
 
 // #define BENCH_SORTED_ARRAY 1
 
-// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates
-static size_t
-unique_rand(size_t i)
-{
-  i ^= 0x5CA1AB1Eu; // Juggle bits to avoid linear clumps
-
-  // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4)
-  static const size_t prime = 4294967291;
-  if (i >= prime) {
-    return i; // Values >= prime are mapped to themselves
-  }
-
-  const size_t residue = ((uint64_t)i * i) % prime;
-  return (i <= prime / 2) ? residue : prime - residue;
-}
-
 static int
 int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data))
 {
diff --git a/test/.clang-tidy b/test/.clang-tidy
index 9424c6a..036a68c 100644
--- a/test/.clang-tidy
+++ b/test/.clang-tidy
@@ -8,8 +8,6 @@ Checks: >
   -bugprone-suspicious-string-compare,
   -cert-dcl37-c,
   -cert-dcl51-cpp,
-  -cert-msc30-c,
-  -cert-msc50-cpp,
   -clang-analyzer-security.insecureAPI.DeprecatedOrUnsafeBufferHandling,
   -cppcoreguidelines-avoid-non-const-global-variables,
   -google-readability-casting,
diff --git a/test/btree_test.c b/test/btree_test.c
index ccb0cbc..5184392 100644
--- a/test/btree_test.c
+++ b/test/btree_test.c
@@ -18,6 +18,7 @@
 
 #include "zix/btree.h"
 
+#include "test_data.h"
 #include "test_malloc.h"
 
 #include "zix/common.h"
@@ -32,22 +33,6 @@
 
 static bool expect_failure = false;
 
-// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates
-static uintptr_t
-unique_rand(size_t i)
-{
-  i ^= 0x00005CA1Eu; // Juggle bits to avoid linear clumps
-
-  // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4)
-  static const uint32_t prime = 4294967291;
-  if (i >= prime) {
-    return i; // Values >= prime are mapped to themselves
-  }
-
-  const uint64_t residue = ((uint64_t)i * i) % prime;
-  return (uintptr_t)((i <= prime / 2) ? residue : prime - residue);
-}
-
 static int
 int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data))
 {
@@ -413,7 +398,7 @@ stress(const unsigned test_num, const size_t n_elems)
 
   // Delete some elements in a random order
   for (size_t e = 0; e < zix_btree_size(t) / 2; e++) {
-    r = ith_elem(test_num, n_elems, rand() % n_elems);
+    r = ith_elem(test_num, n_elems, unique_rand(e) % n_elems);
 
     uintptr_t removed = 0;
     ZixStatus rst     = zix_btree_remove(t, (void*)r, (void**)&removed, &next);
diff --git a/test/sorted_array_test.c b/test/sorted_array_test.c
index 9256118..cc87619 100644
--- a/test/sorted_array_test.c
+++ b/test/sorted_array_test.c
@@ -14,6 +14,8 @@
   OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
+#include "test_data.h"
+
 #include "zix/common.h"
 #include "zix/sorted_array.h"
 
@@ -45,7 +47,7 @@ ith_elem(unsigned test_num, unsigned n_elems, unsigned i)
     return n_elems - i; // Decreasing (worse case)
   case 2:
   default:
-    return rand() % 100; // Random
+    return lcg64(seed + i) % 100u; // Pseudo-random
   }
 }
 
@@ -64,8 +66,6 @@ stress(unsigned test_num, unsigned n_elems)
   ZixSortedArray* t =
     zix_sorted_array_new(true, int_cmp, NULL, sizeof(intptr_t));
 
-  srand(seed);
-
   // Insert n_elems elements
   for (unsigned i = 0; i < n_elems; ++i) {
     r          = ith_elem(test_num, n_elems, i);
@@ -84,8 +84,6 @@ stress(unsigned test_num, unsigned n_elems)
     }
   }
 
-  srand(seed);
-
   // Search for all elements
   for (unsigned i = 0; i < n_elems; ++i) {
     r = ith_elem(test_num, n_elems, i);
@@ -103,8 +101,6 @@ stress(unsigned test_num, unsigned n_elems)
     }
   }
 
-  srand(seed);
-
   // Iterate over all elements
   unsigned i    = 0;
   intptr_t last = -1;
@@ -137,8 +133,6 @@ stress(unsigned test_num, unsigned n_elems)
     return test_fail();
   }
 
-  srand(seed);
-
   // Iterate over all elements by index
   last = -1;
   for (i = 0; i < zix_sorted_array_size(t); ++i) {
@@ -156,8 +150,6 @@ stress(unsigned test_num, unsigned n_elems)
     last = iter_data;
   }
 
-  srand(seed);
-
   // Delete all elements
   for (unsigned e = 0; e < n_elems; e++) {
     r = ith_elem(test_num, n_elems, e);
@@ -205,7 +197,8 @@ main(int argc, char** argv)
     return 1;
   }
 
-  printf("Running %u tests with %u elements (seed %u)\n", n_tests, n_elems, seed);
+  printf(
+    "Running %u tests with %u elements (seed %u)\n", n_tests, n_elems, seed);
 
   for (unsigned i = 0; i < n_tests; ++i) {
     printf(".");
diff --git a/test/test_data.h b/test/test_data.h
new file mode 100644
index 0000000..9c9a51d
--- /dev/null
+++ b/test/test_data.h
@@ -0,0 +1,59 @@
+/*
+  Copyright 2011-2021 David Robillard <d@drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#ifndef ZIX_TEST_DATA_H
+#define ZIX_TEST_DATA_H
+
+#include <stddef.h>
+#include <stdint.h>
+
+/// Linear Congruential Generator for making random 32-bit integers
+static inline uint32_t
+lcg32(const uint32_t i)
+{
+  static const uint32_t a = 134775813u;
+  static const uint32_t c = 1u;
+
+  return (a * i) + c;
+}
+
+/// Linear Congruential Generator for making random 64-bit integers
+static inline uint64_t
+lcg64(const uint64_t i)
+{
+  static const uint64_t a = 6364136223846793005ull;
+  static const uint64_t c = 1ull;
+
+  return (a * i) + c;
+}
+
+/// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates
+static inline size_t
+unique_rand(size_t i)
+{
+  i ^= 0x5CA1AB1Eu; // Juggle bits to avoid linear clumps
+
+  // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4)
+  static const size_t prime = 4294967291u;
+  if (i >= prime) {
+    return i; // Values >= prime are mapped to themselves
+  }
+
+  const size_t residue = ((uint64_t)i * i) % prime;
+  return (i <= prime / 2) ? residue : prime - residue;
+}
+
+#endif // ZIX_TEST_DATA_H
diff --git a/test/tree_test.c b/test/tree_test.c
index eb0eddc..4b044a1 100644
--- a/test/tree_test.c
+++ b/test/tree_test.c
@@ -14,9 +14,10 @@
   OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
-#include "zix/tree.h"
+#include "test_data.h"
 
 #include "zix/common.h"
+#include "zix/tree.h"
 
 #include <inttypes.h>
 #include <stdbool.h>
@@ -46,7 +47,7 @@ ith_elem(unsigned test_num, size_t n_elems, size_t i)
     return n_elems - i; // Decreasing (worse case)
   case 2:
   default:
-    return rand() % 100; // Random
+    return lcg64(seed + i) % 100; // Random
   }
 }
 
@@ -63,8 +64,6 @@ stress(unsigned test_num, size_t n_elems)
   ZixTreeIter* ti = NULL;
   ZixTree*     t  = zix_tree_new(true, int_cmp, NULL, NULL);
 
-  srand(seed);
-
   // Insert n_elems elements
   for (size_t i = 0; i < n_elems; ++i) {
     r          = ith_elem(test_num, n_elems, i);
@@ -91,8 +90,6 @@ stress(unsigned test_num, size_t n_elems)
     return test_fail();
   }
 
-  srand(seed);
-
   // Search for all elements
   for (size_t i = 0; i < n_elems; ++i) {
     r = ith_elem(test_num, n_elems, i);
@@ -109,8 +106,6 @@ stress(unsigned test_num, size_t n_elems)
     }
   }
 
-  srand(seed);
-
   // Iterate over all elements
   size_t   i    = 0;
   intptr_t last = -1;
@@ -134,8 +129,6 @@ stress(unsigned test_num, size_t n_elems)
     return test_fail();
   }
 
-  srand(seed);
-
   // Iterate over all elements backwards
   i    = 0;
   last = INTPTR_MAX;
@@ -152,8 +145,6 @@ stress(unsigned test_num, size_t n_elems)
     last = iter_data;
   }
 
-  srand(seed);
-
   // Delete all elements
   for (size_t e = 0; e < n_elems; e++) {
     r = ith_elem(test_num, n_elems, e);
@@ -174,8 +165,6 @@ stress(unsigned test_num, size_t n_elems)
     return test_fail();
   }
 
-  srand(seed);
-
   // Insert n_elems elements again (to test non-empty destruction)
   for (size_t e = 0; e < n_elems; ++e) {
     r          = ith_elem(test_num, n_elems, e);