[libc][test] Drastically reduce mem test runtime

Reviewed By: lntue

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

8 files changed, 126 insertions, 74 deletions

diff --git a/libc/test/src/string/bcmp_test.cpp b/libc/test/src/string/bcmp_test.cpp
index 0559ab0..72037c7 100644
--- a/libc/test/src/string/bcmp_test.cpp
+++ b/libc/test/src/string/bcmp_test.cpp
@@ -37,22 +37,20 @@ TEST(LlvmLibcBcmpTest, LhsAfterRhsLexically) {
   ASSERT_NE(__llvm_libc::bcmp(lhs, rhs, 2), 0);
 }
 
-// Adapt CheckBcmp signature to op implementation signatures.
-template <auto FnImpl>
-int CmpAdaptor(cpp::span<char> p1, cpp::span<char> p2, size_t size) {
-  return FnImpl(p1.begin(), p2.begin(), size);
+// Adapt CheckBcmp signature to bcmp.
+static inline int Adaptor(cpp::span<char> p1, cpp::span<char> p2, size_t size) {
+  return __llvm_libc::bcmp(p1.begin(), p2.begin(), size);
 }
 
 TEST(LlvmLibcBcmpTest, SizeSweep) {
-  static constexpr size_t kMaxSize = 1024;
-  static constexpr auto Impl = CmpAdaptor<__llvm_libc::bcmp>;
+  static constexpr size_t kMaxSize = 400;
   Buffer Buffer1(kMaxSize);
   Buffer Buffer2(kMaxSize);
   Randomize(Buffer1.span());
   for (size_t size = 0; size < kMaxSize; ++size) {
     auto span1 = Buffer1.span().subspan(0, size);
     auto span2 = Buffer2.span().subspan(0, size);
-    const bool OK = CheckBcmp<Impl>(span1, span2, size);
+    const bool OK = CheckBcmp<Adaptor>(span1, span2, size);
     if (!OK)
       testing::tlog << "Failed at size=" << size << '\n';
     ASSERT_TRUE(OK);
diff --git a/libc/test/src/string/bcopy_test.cpp b/libc/test/src/string/bcopy_test.cpp
index affd23b..a0c14bc 100644
--- a/libc/test/src/string/bcopy_test.cpp
+++ b/libc/test/src/string/bcopy_test.cpp
@@ -16,6 +16,8 @@
 using __llvm_libc::cpp::array;
 using __llvm_libc::cpp::span;
 
+namespace __llvm_libc {
+
 TEST(LlvmLibcBcopyTest, MoveZeroByte) {
   char Buffer[] = {'a', 'b', 'y', 'z'};
   const char Expected[] = {'a', 'b', 'y', 'z'};
@@ -70,23 +72,27 @@ TEST(LlvmLibcBcopyTest, DstFollowSrc) {
   ASSERT_MEM_EQ(Buffer, Expected);
 }
 
-static constexpr int kMaxSize = 512;
+// Adapt CheckMemmove signature to bcopy.
+static inline void Adaptor(cpp::span<char> dst, cpp::span<char> src,
+                           size_t size) {
+  __llvm_libc::bcopy(src.begin(), dst.begin(), size);
+}
 
 TEST(LlvmLibcBcopyTest, SizeSweep) {
-  using LargeBuffer = array<char, 3 * kMaxSize>;
-  LargeBuffer GroundTruth;
-  __llvm_libc::Randomize(GroundTruth);
-  for (int Size = 0; Size < kMaxSize; ++Size) {
-    for (int Offset = -Size; Offset < Size; ++Offset) {
-      LargeBuffer Buffer = GroundTruth;
-      LargeBuffer Expected = GroundTruth;
-      size_t DstOffset = kMaxSize;
-      size_t SrcOffset = kMaxSize + Offset;
-      for (int I = 0; I < Size; ++I)
-        Expected[DstOffset + I] = GroundTruth[SrcOffset + I];
-      void *const Dst = Buffer.data() + DstOffset;
-      __llvm_libc::bcopy(Buffer.data() + SrcOffset, Dst, Size);
-      ASSERT_MEM_EQ(Buffer, Expected);
+  static constexpr int kMaxSize = 400;
+  static constexpr int kDenseOverlap = 15;
+  using LargeBuffer = array<char, 2 * kMaxSize + 1>;
+  LargeBuffer Buffer;
+  Randomize(Buffer);
+  for (int Size = 0; Size < kMaxSize; ++Size)
+    for (int Overlap = -1; Overlap < Size;) {
+      ASSERT_TRUE(CheckMemmove<Adaptor>(Buffer, Size, Overlap));
+      // Prevent quadratic behavior by skipping offset above kDenseOverlap.
+      if (Overlap > kDenseOverlap)
+        Overlap *= 2;
+      else
+        ++Overlap;
     }
-  }
 }
+
+} // namespace __llvm_libc
diff --git a/libc/test/src/string/bzero_test.cpp b/libc/test/src/string/bzero_test.cpp
index e809506..d3ee64d 100644
--- a/libc/test/src/string/bzero_test.cpp
+++ b/libc/test/src/string/bzero_test.cpp
@@ -12,19 +12,17 @@
 
 namespace __llvm_libc {
 
-// Adapt CheckMemset signature to op implementation signatures.
-template <auto FnImpl>
-void BzeroAdaptor(cpp::span<char> p1, uint8_t value, size_t size) {
-  FnImpl(p1.begin(), size);
+// Adapt CheckMemset signature to bzero.
+static inline void Adaptor(cpp::span<char> p1, uint8_t value, size_t size) {
+  __llvm_libc::bzero(p1.begin(), size);
 }
 
 TEST(LlvmLibcBzeroTest, SizeSweep) {
-  static constexpr size_t kMaxSize = 1024;
-  static constexpr auto Impl = BzeroAdaptor<__llvm_libc::bzero>;
+  static constexpr size_t kMaxSize = 400;
   Buffer DstBuffer(kMaxSize);
   for (size_t size = 0; size < kMaxSize; ++size) {
     auto dst = DstBuffer.span().subspan(0, size);
-    ASSERT_TRUE((CheckMemset<Impl>(dst, 0, size)));
+    ASSERT_TRUE((CheckMemset<Adaptor>(dst, 0, size)));
   }
 }
 
diff --git a/libc/test/src/string/memcmp_test.cpp b/libc/test/src/string/memcmp_test.cpp
index 24434a9..ac26fd4 100644
--- a/libc/test/src/string/memcmp_test.cpp
+++ b/libc/test/src/string/memcmp_test.cpp
@@ -37,22 +37,20 @@ TEST(LlvmLibcMemcmpTest, LhsAfterRhsLexically) {
   EXPECT_GT(__llvm_libc::memcmp(lhs, rhs, 2), 0);
 }
 
-// Adapt CheckMemcmp signature to op implementation signatures.
-template <auto FnImpl>
-int CmpAdaptor(cpp::span<char> p1, cpp::span<char> p2, size_t size) {
-  return FnImpl(p1.begin(), p2.begin(), size);
+// Adapt CheckMemcmp signature to memcmp.
+static inline int Adaptor(cpp::span<char> p1, cpp::span<char> p2, size_t size) {
+  return __llvm_libc::memcmp(p1.begin(), p2.begin(), size);
 }
 
 TEST(LlvmLibcMemcmpTest, SizeSweep) {
-  static constexpr size_t kMaxSize = 1024;
-  static constexpr auto Impl = CmpAdaptor<__llvm_libc::memcmp>;
+  static constexpr size_t kMaxSize = 400;
   Buffer Buffer1(kMaxSize);
   Buffer Buffer2(kMaxSize);
   Randomize(Buffer1.span());
   for (size_t size = 0; size < kMaxSize; ++size) {
     auto span1 = Buffer1.span().subspan(0, size);
     auto span2 = Buffer2.span().subspan(0, size);
-    const bool OK = CheckMemcmp<Impl>(span1, span2, size);
+    const bool OK = CheckMemcmp<Adaptor>(span1, span2, size);
     if (!OK)
       testing::tlog << "Failed at size=" << size << '\n';
     ASSERT_TRUE(OK);
diff --git a/libc/test/src/string/memcpy_test.cpp b/libc/test/src/string/memcpy_test.cpp
index e9863e6..7fe0921 100644
--- a/libc/test/src/string/memcpy_test.cpp
+++ b/libc/test/src/string/memcpy_test.cpp
@@ -12,22 +12,21 @@
 
 namespace __llvm_libc {
 
-// Adapt CheckMemcpy signature to op implementation signatures.
-template <auto FnImpl>
-void CopyAdaptor(cpp::span<char> dst, cpp::span<char> src, size_t size) {
-  FnImpl(dst.begin(), src.begin(), size);
+// Adapt CheckMemcpy signature to memcpy.
+static inline void Adaptor(cpp::span<char> dst, cpp::span<char> src,
+                           size_t size) {
+  __llvm_libc::memcpy(dst.begin(), src.begin(), size);
 }
 
 TEST(LlvmLibcMemcpyTest, SizeSweep) {
-  static constexpr size_t kMaxSize = 1024;
-  static constexpr auto Impl = CopyAdaptor<__llvm_libc::memcpy>;
+  static constexpr size_t kMaxSize = 400;
   Buffer SrcBuffer(kMaxSize);
   Buffer DstBuffer(kMaxSize);
   Randomize(SrcBuffer.span());
   for (size_t size = 0; size < kMaxSize; ++size) {
     auto src = SrcBuffer.span().subspan(0, size);
     auto dst = DstBuffer.span().subspan(0, size);
-    ASSERT_TRUE(CheckMemcpy<Impl>(dst, src, size));
+    ASSERT_TRUE(CheckMemcpy<Adaptor>(dst, src, size));
   }
 }
 
diff --git a/libc/test/src/string/memmove_test.cpp b/libc/test/src/string/memmove_test.cpp
index dad834c..49a5cce 100644
--- a/libc/test/src/string/memmove_test.cpp
+++ b/libc/test/src/string/memmove_test.cpp
@@ -16,6 +16,8 @@
 using __llvm_libc::cpp::array;
 using __llvm_libc::cpp::span;
 
+namespace __llvm_libc {
+
 TEST(LlvmLibcMemmoveTest, MoveZeroByte) {
   char Buffer[] = {'a', 'b', 'y', 'z'};
   const char Expected[] = {'a', 'b', 'y', 'z'};
@@ -76,25 +78,27 @@ TEST(LlvmLibcMemmoveTest, DstFollowSrc) {
   ASSERT_MEM_EQ(Buffer, Expected);
 }
 
-static constexpr int kMaxSize = 512;
+// Adapt CheckMemmove signature to op implementation signatures.
+static inline void Adaptor(cpp::span<char> dst, cpp::span<char> src,
+                           size_t size) {
+  __llvm_libc::memmove(dst.begin(), src.begin(), size);
+}
 
 TEST(LlvmLibcMemmoveTest, SizeSweep) {
-  using LargeBuffer = array<char, 3 * kMaxSize>;
-  LargeBuffer GroundTruth;
-  __llvm_libc::Randomize(GroundTruth);
-  for (int Size = 0; Size < kMaxSize; ++Size) {
-    for (int Offset = -Size; Offset < Size; ++Offset) {
-      LargeBuffer Buffer = GroundTruth;
-      LargeBuffer Expected = GroundTruth;
-      size_t DstOffset = kMaxSize;
-      size_t SrcOffset = kMaxSize + Offset;
-      for (int I = 0; I < Size; ++I)
-        Expected[DstOffset + I] = GroundTruth[SrcOffset + I];
-      void *const Dst = Buffer.data() + DstOffset;
-      void *const Ret =
-          __llvm_libc::memmove(Dst, Buffer.data() + SrcOffset, Size);
-      EXPECT_EQ(Ret, Dst);
-      ASSERT_MEM_EQ(Buffer, Expected);
+  static constexpr int kMaxSize = 400;
+  static constexpr int kDenseOverlap = 15;
+  using LargeBuffer = array<char, 2 * kMaxSize + 1>;
+  LargeBuffer Buffer;
+  Randomize(Buffer);
+  for (int Size = 0; Size < kMaxSize; ++Size)
+    for (int Overlap = -1; Overlap < Size;) {
+      ASSERT_TRUE(CheckMemmove<Adaptor>(Buffer, Size, Overlap));
+      // Prevent quadratic behavior by skipping offset above kDenseOverlap.
+      if (Overlap > kDenseOverlap)
+        Overlap *= 2;
+      else
+        ++Overlap;
     }
-  }
 }
+
+} // namespace __llvm_libc
diff --git a/libc/test/src/string/memory_utils/memory_check_utils.h b/libc/test/src/string/memory_utils/memory_check_utils.h
index c2b910e..789b538 100644
--- a/libc/test/src/string/memory_utils/memory_check_utils.h
+++ b/libc/test/src/string/memory_utils/memory_check_utils.h
@@ -10,6 +10,7 @@
 #define LIBC_TEST_SRC_STRING_MEMORY_UTILS_MEMORY_CHECK_UTILS_H
 
 #include "src/__support/CPP/span.h"
+#include "src/__support/libc_assert.h"
 #include "src/__support/macros/sanitizer.h"
 #include "src/string/memory_utils/utils.h"
 #include <stddef.h> // size_t
@@ -76,15 +77,20 @@ static inline void ReferenceCopy(cpp::span<char> dst,
     dst[i] = src[i];
 }
 
+static inline bool IsEqual(const cpp::span<char> a, const cpp::span<char> b) {
+  LIBC_ASSERT(a.size() == b.size());
+  for (size_t i = 0; i < a.size(); ++i)
+    if (a[i] != b[i])
+      return false;
+  return true;
+}
+
 // Checks that FnImpl implements the memcpy semantic.
 template <auto FnImpl>
 bool CheckMemcpy(cpp::span<char> dst, cpp::span<char> src, size_t size) {
   Randomize(dst);
   FnImpl(dst, src, size);
-  for (size_t i = 0; i < size; ++i)
-    if (dst[i] != src[i])
-      return false;
-  return true;
+  return IsEqual(dst, src);
 }
 
 // Checks that FnImpl implements the memset semantic.
@@ -144,7 +150,52 @@ bool CheckMemcmp(cpp::span<char> span1, cpp::span<char> span2, size_t size) {
   return true;
 }
 
-// TODO: Also implement the memmove semantic
+uint16_t Checksum(cpp::span<char> dst) {
+  // We use Fletcher16 as it is trivial to implement.
+  uint16_t sum1 = 0;
+  uint16_t sum2 = 0;
+  for (char c : dst) {
+    sum1 = (sum1 + c) % 255U;
+    sum2 = (sum2 + sum1) % 255U;
+  }
+  return (sum2 << 8) | sum1;
+}
+
+template <auto FnImpl>
+bool CheckMemmove(cpp::span<char> dst, cpp::span<char> src) {
+  LIBC_ASSERT(dst.size() == src.size());
+  // Memmove can override the src buffer. Technically we should save it into a
+  // temporary buffer so we can check that 'dst' is equal to what 'src' was
+  // before we called the function. To save on allocation and copy we use a
+  // checksum instead.
+  const auto src_checksum = Checksum(src);
+  FnImpl(dst, src, dst.size());
+  return Checksum(dst) == src_checksum;
+}
+
+// Checks that FnImpl implements the memmove semantic.
+//  - Buffer size should be greater than 2 * size + 1.
+//  - Overlap refers to the number of bytes in common between the two buffers:
+//    - Negative means buffers are disjoint
+//    - zero mean they overlap exactly
+//  - Caller is responsible for randomizing the buffer.
+template <auto FnImpl>
+bool CheckMemmove(cpp::span<char> buffer, size_t size, int overlap) {
+  LIBC_ASSERT(buffer.size() > (2 * size + 1));
+  const size_t half_size = buffer.size() / 2;
+  LIBC_ASSERT((size_t)(overlap >= 0 ? overlap : -overlap) < half_size);
+  cpp::span<char> head = buffer.first(half_size + overlap).last(size);
+  cpp::span<char> tail = buffer.last(half_size).first(size);
+  LIBC_ASSERT(head.size() == size);
+  LIBC_ASSERT(tail.size() == size);
+  // dst before src
+  if (!CheckMemmove<FnImpl>(head, tail))
+    return false;
+  // dst after src
+  if (!CheckMemmove<FnImpl>(tail, head))
+    return false;
+  return true;
+}
 
 } // namespace __llvm_libc
 
diff --git a/libc/test/src/string/memset_test.cpp b/libc/test/src/string/memset_test.cpp
index eab85e3..1aa8edd 100644
--- a/libc/test/src/string/memset_test.cpp
+++ b/libc/test/src/string/memset_test.cpp
@@ -12,20 +12,18 @@
 
 namespace __llvm_libc {
 
-// Adapt CheckMemset signature to op implementation signatures.
-template <auto FnImpl>
-void SetAdaptor(cpp::span<char> p1, uint8_t value, size_t size) {
-  FnImpl(p1.begin(), value, size);
+// Adapt CheckMemset signature to memset.
+static inline void Adaptor(cpp::span<char> p1, uint8_t value, size_t size) {
+  __llvm_libc::memset(p1.begin(), value, size);
 }
 
 TEST(LlvmLibcMemsetTest, SizeSweep) {
-  static constexpr size_t kMaxSize = 1024;
-  static constexpr auto Impl = SetAdaptor<__llvm_libc::memset>;
+  static constexpr size_t kMaxSize = 400;
   Buffer DstBuffer(kMaxSize);
   for (size_t size = 0; size < kMaxSize; ++size) {
     const char value = size % 10;
     auto dst = DstBuffer.span().subspan(0, size);
-    ASSERT_TRUE((CheckMemset<Impl>(dst, value, size)));
+    ASSERT_TRUE((CheckMemset<Adaptor>(dst, value, size)));
   }
 }