diff --git a/libc/test/src/string/bcmp_test.cpp b/libc/test/src/string/bcmp_test.cpp --- a/libc/test/src/string/bcmp_test.cpp +++ b/libc/test/src/string/bcmp_test.cpp @@ -37,22 +37,20 @@ ASSERT_NE(__llvm_libc::bcmp(lhs, rhs, 2), 0); } -// Adapt CheckBcmp signature to op implementation signatures. -template -int CmpAdaptor(cpp::span p1, cpp::span p2, size_t size) { - return FnImpl(p1.begin(), p2.begin(), size); +// Adapt CheckBcmp signature to bcmp. +static inline int Adaptor(cpp::span p1, cpp::span 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(span1, span2, size); + const bool OK = CheckBcmp(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 --- 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 @@ ASSERT_MEM_EQ(Buffer, Expected); } -static constexpr int kMaxSize = 512; +// Adapt CheckMemmove signature to bcopy. +static inline void Adaptor(cpp::span dst, cpp::span src, + size_t size) { + __llvm_libc::bcopy(src.begin(), dst.begin(), size); +} TEST(LlvmLibcBcopyTest, SizeSweep) { - using LargeBuffer = array; - 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; + LargeBuffer Buffer; + Randomize(Buffer); + for (int Size = 0; Size < kMaxSize; ++Size) + for (int Overlap = -1; Overlap < Size;) { + ASSERT_TRUE(CheckMemmove(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 --- 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 -void BzeroAdaptor(cpp::span p1, uint8_t value, size_t size) { - FnImpl(p1.begin(), size); +// Adapt CheckMemset signature to bzero. +static inline void Adaptor(cpp::span 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(dst, 0, size))); + ASSERT_TRUE((CheckMemset(dst, 0, size))); } } diff --git a/libc/test/src/string/memcmp_test.cpp b/libc/test/src/string/memcmp_test.cpp --- a/libc/test/src/string/memcmp_test.cpp +++ b/libc/test/src/string/memcmp_test.cpp @@ -37,22 +37,20 @@ EXPECT_GT(__llvm_libc::memcmp(lhs, rhs, 2), 0); } -// Adapt CheckMemcmp signature to op implementation signatures. -template -int CmpAdaptor(cpp::span p1, cpp::span p2, size_t size) { - return FnImpl(p1.begin(), p2.begin(), size); +// Adapt CheckMemcmp signature to memcmp. +static inline int Adaptor(cpp::span p1, cpp::span 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(span1, span2, size); + const bool OK = CheckMemcmp(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 --- 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 -void CopyAdaptor(cpp::span dst, cpp::span src, size_t size) { - FnImpl(dst.begin(), src.begin(), size); +// Adapt CheckMemcpy signature to memcpy. +static inline void Adaptor(cpp::span dst, cpp::span 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(dst, src, size)); + ASSERT_TRUE(CheckMemcpy(dst, src, size)); } } diff --git a/libc/test/src/string/memmove_test.cpp b/libc/test/src/string/memmove_test.cpp --- 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 @@ ASSERT_MEM_EQ(Buffer, Expected); } -static constexpr int kMaxSize = 512; +// Adapt CheckMemmove signature to op implementation signatures. +static inline void Adaptor(cpp::span dst, cpp::span src, + size_t size) { + __llvm_libc::memmove(dst.begin(), src.begin(), size); +} TEST(LlvmLibcMemmoveTest, SizeSweep) { - using LargeBuffer = array; - 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; + LargeBuffer Buffer; + Randomize(Buffer); + for (int Size = 0; Size < kMaxSize; ++Size) + for (int Overlap = -1; Overlap < Size;) { + ASSERT_TRUE(CheckMemmove(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 --- 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 // size_t @@ -76,15 +77,20 @@ dst[i] = src[i]; } +static inline bool IsEqual(const cpp::span a, const cpp::span 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 bool CheckMemcpy(cpp::span dst, cpp::span 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 @@ return true; } -// TODO: Also implement the memmove semantic +uint16_t Checksum(cpp::span 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 +bool CheckMemmove(cpp::span dst, cpp::span 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 +bool CheckMemmove(cpp::span 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 head = buffer.first(half_size + overlap).last(size); + cpp::span tail = buffer.last(half_size).first(size); + LIBC_ASSERT(head.size() == size); + LIBC_ASSERT(tail.size() == size); + // dst before src + if (!CheckMemmove(head, tail)) + return false; + // dst after src + if (!CheckMemmove(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 --- 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 -void SetAdaptor(cpp::span p1, uint8_t value, size_t size) { - FnImpl(p1.begin(), value, size); +// Adapt CheckMemset signature to memset. +static inline void Adaptor(cpp::span 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(dst, value, size))); + ASSERT_TRUE((CheckMemset(dst, value, size))); } } diff --git a/utils/bazel/llvm-project-overlay/libc/test/src/string/BUILD.bazel b/utils/bazel/llvm-project-overlay/libc/test/src/string/BUILD.bazel --- a/utils/bazel/llvm-project-overlay/libc/test/src/string/BUILD.bazel +++ b/utils/bazel/llvm-project-overlay/libc/test/src/string/BUILD.bazel @@ -119,6 +119,7 @@ hdrs = ["memory_utils/memory_check_utils.h"], deps = [ "//libc:__support_cpp_span", + "//libc:__support_libc_assert", "//libc:__support_macros_sanitizer", "//libc:string_memory_utils", ],