diff --git a/libc/src/__support/CPP/ArrayRef.h b/libc/src/__support/CPP/ArrayRef.h --- a/libc/src/__support/CPP/ArrayRef.h +++ b/libc/src/__support/CPP/ArrayRef.h @@ -131,6 +131,10 @@ public: // From Array. template MutableArrayRef(Array &Arr) : Impl(Arr.Data, N) {} + + operator ArrayRef() const { + return ArrayRef(this->data(), this->size()); + } }; } // namespace cpp diff --git a/libc/src/string/CMakeLists.txt b/libc/src/string/CMakeLists.txt --- a/libc/src/string/CMakeLists.txt +++ b/libc/src/string/CMakeLists.txt @@ -401,7 +401,6 @@ HDRS ${LIBC_SOURCE_DIR}/src/string/memmove.h DEPENDS .memory_utils.memory_utils - .memory_utils.memcpy_implementation libc.include.string COMPILE_OPTIONS -fno-builtin diff --git a/libc/src/string/memmove.cpp b/libc/src/string/memmove.cpp --- a/libc/src/string/memmove.cpp +++ b/libc/src/string/memmove.cpp @@ -10,59 +10,43 @@ #include "src/__support/common.h" #include "src/__support/integer_operations.h" -#include "src/string/memory_utils/memcpy_implementations.h" +#include "src/string/memory_utils/elements.h" #include // size_t, ptrdiff_t namespace __llvm_libc { -static inline void move_byte_forward(char *dest_m, const char *src_m, - size_t count) { - for (size_t offset = 0; count; --count, ++offset) - dest_m[offset] = src_m[offset]; -} - -static inline void move_byte_backward(char *dest_m, const char *src_m, - size_t count) { - for (size_t offset = count - 1; count; --count, --offset) - dest_m[offset] = src_m[offset]; +static inline void inline_memmove(char *dst, const char *src, size_t count) { + using namespace __llvm_libc::scalar; + if (count == 0) + return; + if (count == 1) + return move<_1>(dst, src); + if (count < 4) + return move>(dst, src, count); + if (count == 4) + return move<_4>(dst, src); + if (count < 8) + return move>(dst, src, count); + if (count <= 16) + return move>(dst, src, count); + if (count <= 32) + return move>(dst, src, count); + if (count <= 64) + return move>(dst, src, count); + if (count <= 128) + return move>(dst, src, count); + + using AlignedMoveLoop = Align<_32, Arg::Src>::Then>; + if (dst < src) + return move(dst, src, count); + else if (dst > src) + return move_backward(dst, src, count); } LLVM_LIBC_FUNCTION(void *, memmove, (void *dst, const void *src, size_t count)) { - char *dest_c = reinterpret_cast(dst); - const char *src_c = reinterpret_cast(src); - - // If the distance between `src_c` and `dest_c` is equal to or greater - // than `count` (integerAbs(src_c - dest_c) >= count), they would not overlap. - // e.g. greater equal overlapping - // [12345678] [12345678] [12345678] - // src_c: [_ab_____] [_ab_____] [_ab_____] - // dest_c:[_____yz_] [___yz___] [__yz____] - - // Call `memcpy` if `src_c` and `dest_c` do not overlap. - if (__llvm_libc::integer_abs(src_c - dest_c) >= - static_cast(count)) { - inline_memcpy(dest_c, src_c, count); - return dest_c; - } - - // Overlapping cases. - // If `dest_c` starts before `src_c` (dest_c < src_c), copy - // forward(pointer add 1) from beginning to end. - // If `dest_c` starts after `src_c` (dest_c > src_c), copy - // backward(pointer add -1) from end to beginning. - // If `dest_c` and `src_c` start at the same address (dest_c == src_c), - // just return dest. - // e.g. forward backward - // *-> <-* - // src_c : [___abcde_] [_abcde___] - // dest_c: [_abc--___] [___--cde_] - - // TODO: Optimize `move_byte_xxx(...)` functions. - if (dest_c < src_c) - move_byte_forward(dest_c, src_c, count); - if (dest_c > src_c) - move_byte_backward(dest_c, src_c, count); + inline_memmove(reinterpret_cast(dst), + reinterpret_cast(src), count); return dst; } diff --git a/libc/src/string/memory_utils/elements.h b/libc/src/string/memory_utils/elements.h --- a/libc/src/string/memory_utils/elements.h +++ b/libc/src/string/memory_utils/elements.h @@ -43,6 +43,11 @@ template void move(char *dst, const char *src, size_t size) { Element::move(dst, src, size); } +// Runtime-size move from 'src' to 'dst'. +template +void move_backward(char *dst, const char *src, size_t size) { + Element::move_backward(dst, src, size); +} // Fixed-size equality between 'lhs' and 'rhs'. template bool equals(const char *lhs, const char *rhs) { @@ -341,6 +346,55 @@ Tail::copy(dst, src, size); } + // Move forward suitable when dst < src. We load the tail bytes before + // handling the loop. + // + // e.g. Moving two bytes + // [ | | | | |] + // [___XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX___] + // [_________________________LLLLLLLL___] + // [___LLLLLLLL_________________________] + // [_SSSSSSSS___________________________] + // [___________LLLLLLLL_________________] + // [_________SSSSSSSS___________________] + // [___________________LLLLLLLL_________] + // [_________________SSSSSSSS___________] + // [_______________________SSSSSSSS_____] + static void move(char *dst, const char *src, size_t size) { + const size_t tail_offset = Tail::offset(size); + const auto tail_value = TailT::load(src + tail_offset); + size_t offset = 0; + do { + T::move(dst + offset, src + offset); + offset += T::SIZE; + } while (offset < size - T::SIZE); + TailT::store(dst + tail_offset, tail_value); + } + + // Move forward suitable when dst > src. We load the head bytes before + // handling the loop. + // + // e.g. Moving two bytes + // [ | | | | |] + // [___XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX___] + // [___LLLLLLLL_________________________] + // [_________________________LLLLLLLL___] + // [___________________________SSSSSSSS_] + // [_________________LLLLLLLL___________] + // [___________________SSSSSSSS_________] + // [_________LLLLLLLL___________________] + // [___________SSSSSSSS_________________] + // [_____SSSSSSSS_______________________] + static void move_backward(char *dst, const char *src, size_t size) { + const auto head_value = TailT::load(src); + ptrdiff_t offset = size - T::SIZE; + do { + T::move(dst + offset, src + offset); + offset -= T::SIZE; + } while (offset >= 0); + TailT::store(dst, head_value); + } + static bool equals(const char *lhs, const char *rhs, size_t size) { size_t offset = 0; do { @@ -375,30 +429,38 @@ namespace internal { -// Provides a specialized bump function that adjusts pointers and size so first -// argument (resp. second argument) gets aligned to Alignment. -// We make sure the compiler knows about the adjusted pointer alignment. -template struct AlignHelper {}; +template struct ArgSelector {}; -template struct AlignHelper { +template <> struct ArgSelector { template - static void bump(T1 *__restrict &p1ref, T2 *__restrict &p2ref, size_t &size) { - const intptr_t offset = offset_to_next_aligned(p1ref); - p1ref += offset; - p2ref += offset; - size -= offset; - p1ref = assume_aligned(p1ref); + static T1 *__restrict &Select(T1 *__restrict &p1ref, T2 *__restrict &p2ref) { + return p1ref; + } +}; + +template <> struct ArgSelector { + template + static T2 *__restrict &Select(T1 *__restrict &p1ref, T2 *__restrict &p2ref) { + return p2ref; } }; -template struct AlignHelper { +// Provides a specialized bump function that adjusts pointers and size so first +// argument (resp. second argument) gets aligned to Alignment. +// We make sure the compiler knows about the adjusted pointer alignment. +// The 'additional_bumps' parameter allows to reach previous / next aligned +// pointers. +template struct Align { template - static void bump(T1 *__restrict &p1ref, T2 *__restrict &p2ref, size_t &size) { - const intptr_t offset = offset_to_next_aligned(p2ref); + static void bump(T1 *__restrict &p1ref, T2 *__restrict &p2ref, size_t &size, + int additional_bumps = 0) { + auto &aligned_ptr = ArgSelector::Select(p1ref, p2ref); + auto offset = offset_to_next_aligned(aligned_ptr); + offset += additional_bumps * Alignment; p1ref += offset; p2ref += offset; size -= offset; - p2ref = assume_aligned(p2ref); + aligned_ptr = assume_aligned(aligned_ptr); } }; @@ -423,14 +485,70 @@ static void copy(char *__restrict dst, const char *__restrict src, size_t size) { AlignmentT::copy(dst, src); - internal::AlignHelper::bump(dst, src, size); + internal::Align::bump(dst, src, size); NextT::copy(dst, src, size); } + // Move forward suitable when dst < src. The alignment is performed with an + // HeadTail operation of size ∈ [Alignment, 2 x Alignment]. + // + // e.g. Moving two bytes and making sure src is then aligned. + // [ | | | | ] + // [____XXXXXXXXXXXXXXXXXXXXXXXXXXXX_] + // [____LLLLLLLL_____________________] + // [___________LLLLLLLL______________] + // [_SSSSSSSS________________________] + // [________SSSSSSSS_________________] + // + // e.g. Moving two bytes and making sure dst is then aligned. + // [ | | | | ] + // [____XXXXXXXXXXXXXXXXXXXXXXXXXXXX_] + // [____LLLLLLLL_____________________] + // [______LLLLLLLL___________________] + // [_SSSSSSSS________________________] + // [___SSSSSSSS______________________] + static void move(char *dst, const char *src, size_t size) { + char *next_dst = dst; + const char *next_src = src; + size_t next_size = size; + internal::Align::bump(next_dst, next_src, next_size, + 1); + HeadTail::move(dst, src, size - next_size); + NextT::move(next_dst, next_src, next_size); + } + + // Move backward suitable when dst > src. The alignment is performed with an + // HeadTail operation of size ∈ [Alignment, 2 x Alignment]. + // + // e.g. Moving two bytes backward and making sure src is then aligned. + // [ | | | | ] + // [____XXXXXXXXXXXXXXXXXXXXXXXX_____] + // [ _________________LLLLLLLL_______] + // [ ___________________LLLLLLLL_____] + // [____________________SSSSSSSS_____] + // [______________________SSSSSSSS___] + // + // e.g. Moving two bytes and making sure dst is then aligned. + // [ | | | | ] + // [____XXXXXXXXXXXXXXXXXXXXXXXX_____] + // [ _______________LLLLLLLL_________] + // [ ___________________LLLLLLLL_____] + // [__________________SSSSSSSS_______] + // [______________________SSSSSSSS___] + static void move_backward(char *dst, const char *src, size_t size) { + char *headtail_dst = dst + size; + const char *headtail_src = src + size; + size_t headtail_size = 0; + internal::Align::bump(headtail_dst, headtail_src, + headtail_size, -2); + HeadTail::move(headtail_dst, headtail_src, headtail_size); + NextT::move_backward(dst, src, size - headtail_size); + } + static bool equals(const char *lhs, const char *rhs, size_t size) { if (!AlignmentT::equals(lhs, rhs)) return false; - internal::AlignHelper::bump(lhs, rhs, size); + internal::Align::bump(lhs, rhs, size); return NextT::equals(lhs, rhs, size); } @@ -438,14 +556,14 @@ size_t size) { if (!AlignmentT::equals(lhs, rhs)) return AlignmentT::three_way_compare(lhs, rhs); - internal::AlignHelper::bump(lhs, rhs, size); + internal::Align::bump(lhs, rhs, size); return NextT::three_way_compare(lhs, rhs, size); } static void splat_set(char *dst, const unsigned char value, size_t size) { AlignmentT::splat_set(dst, value); char *dummy = nullptr; - internal::AlignHelper::bump(dst, dummy, size); + internal::Align::bump(dst, dummy, size); NextT::splat_set(dst, value, size); } }; diff --git a/libc/test/src/string/CMakeLists.txt b/libc/test/src/string/CMakeLists.txt --- a/libc/test/src/string/CMakeLists.txt +++ b/libc/test/src/string/CMakeLists.txt @@ -261,6 +261,8 @@ ${LIBC_COMPILE_OPTIONS_NATIVE} ${ARGN} ) + get_fq_target_name(${fq_config_name}_test fq_target_name) + target_link_libraries(${fq_target_name} PRIVATE LibcMemoryHelpers) else() message(STATUS "Skipping test for '${fq_config_name}' insufficient host cpu features '${required_cpu_features}'") endif() 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 @@ -8,64 +8,106 @@ #include "src/__support/CPP/ArrayRef.h" #include "src/string/memmove.h" +#include "utils/UnitTest/MemoryMatcher.h" #include "utils/UnitTest/Test.h" -class LlvmLibcMemmoveTest : public __llvm_libc::testing::Test { -public: - void check_memmove(void *dst, const void *src, size_t count, - const unsigned char *str, - const __llvm_libc::cpp::ArrayRef expected) { - void *result = __llvm_libc::memmove(dst, src, count); - // Making sure the pointer returned is same with `dst`. - EXPECT_EQ(result, dst); - // `expected` is designed according to `str`. - // `dst` and `src` might be part of `str`. - // Making sure `str` is same with `expected`. - for (size_t i = 0; i < expected.size(); ++i) - EXPECT_EQ(str[i], expected[i]); - } -}; +using __llvm_libc::cpp::Array; +using __llvm_libc::cpp::ArrayRef; +using __llvm_libc::cpp::MutableArrayRef; -TEST_F(LlvmLibcMemmoveTest, MoveZeroByte) { - unsigned char dst[] = {'a', 'b'}; - const unsigned char src[] = {'y', 'z'}; - const unsigned char expected[] = {'a', 'b'}; - check_memmove(dst, src, 0, dst, expected); +TEST(LlvmLibcMemmoveTest, MoveZeroByte) { + char Buffer[] = {'a', 'b', 'y', 'z'}; + const char Expected[] = {'a', 'b', 'y', 'z'}; + void *const Dst = Buffer; + void *const Ret = __llvm_libc::memmove(Dst, Buffer + 2, 0); + EXPECT_EQ(Ret, Dst); + EXPECT_MEM_EQ(Buffer, Expected); } -TEST_F(LlvmLibcMemmoveTest, OverlapThatDstAndSrcPointToSameAddress) { - unsigned char str[] = {'a', 'b'}; - const unsigned char expected[] = {'a', 'b'}; - check_memmove(str, str, 1, str, expected); +TEST(LlvmLibcMemmoveTest, DstAndSrcPointToSameAddress) { + char Buffer[] = {'a', 'b'}; + const char Expected[] = {'a', 'b'}; + void *const Dst = Buffer; + void *const Ret = __llvm_libc::memmove(Dst, Buffer, 1); + EXPECT_EQ(Ret, Dst); + EXPECT_MEM_EQ(Buffer, Expected); } -TEST_F(LlvmLibcMemmoveTest, OverlapThatDstStartsBeforeSrc) { +TEST(LlvmLibcMemmoveTest, DstStartsBeforeSrc) { // Set boundary at beginning and end for not overstepping when // copy forward or backward. - unsigned char str[] = {'z', 'a', 'b', 'c', 'z'}; - const unsigned char expected[] = {'z', 'b', 'c', 'c', 'z'}; - // `dst` is `&str[1]`. - check_memmove(&str[1], &str[2], 2, str, expected); + char Buffer[] = {'z', 'a', 'b', 'c', 'z'}; + const char Expected[] = {'z', 'b', 'c', 'c', 'z'}; + void *const Dst = Buffer + 1; + void *const Ret = __llvm_libc::memmove(Dst, Buffer + 2, 2); + EXPECT_EQ(Ret, Dst); + EXPECT_MEM_EQ(Buffer, Expected); } -TEST_F(LlvmLibcMemmoveTest, OverlapThatDstStartsAfterSrc) { - unsigned char str[] = {'z', 'a', 'b', 'c', 'z'}; - const unsigned char expected[] = {'z', 'a', 'a', 'b', 'z'}; - check_memmove(&str[2], &str[1], 2, str, expected); +TEST(LlvmLibcMemmoveTest, DstStartsAfterSrc) { + char Buffer[] = {'z', 'a', 'b', 'c', 'z'}; + const char Expected[] = {'z', 'a', 'a', 'b', 'z'}; + void *const Dst = Buffer + 2; + void *const Ret = __llvm_libc::memmove(Dst, Buffer + 1, 2); + EXPECT_EQ(Ret, Dst); + EXPECT_MEM_EQ(Buffer, Expected); } -// e.g. `dst` follow `src`. +// e.g. `Dst` follow `src`. // str: [abcdefghij] // [__src_____] -// [_____dst__] -TEST_F(LlvmLibcMemmoveTest, SrcFollowDst) { - unsigned char str[] = {'z', 'a', 'b', 'z'}; - const unsigned char expected[] = {'z', 'b', 'b', 'z'}; - check_memmove(&str[1], &str[2], 1, str, expected); +// [_____Dst__] +TEST(LlvmLibcMemmoveTest, SrcFollowDst) { + char Buffer[] = {'z', 'a', 'b', 'z'}; + const char Expected[] = {'z', 'b', 'b', 'z'}; + void *const Dst = Buffer + 1; + void *const Ret = __llvm_libc::memmove(Dst, Buffer + 2, 1); + EXPECT_EQ(Ret, Dst); + EXPECT_MEM_EQ(Buffer, Expected); +} + +TEST(LlvmLibcMemmoveTest, DstFollowSrc) { + char Buffer[] = {'z', 'a', 'b', 'z'}; + const char Expected[] = {'z', 'a', 'a', 'z'}; + void *const Dst = Buffer + 2; + void *const Ret = __llvm_libc::memmove(Dst, Buffer + 1, 1); + EXPECT_EQ(Ret, Dst); + EXPECT_MEM_EQ(Buffer, Expected); } -TEST_F(LlvmLibcMemmoveTest, DstFollowSrc) { - unsigned char str[] = {'z', 'a', 'b', 'z'}; - const unsigned char expected[] = {'z', 'a', 'a', 'z'}; - check_memmove(&str[2], &str[1], 1, str, expected); +static constexpr int kMaxSize = 512; + +char GetRandomChar() { + static constexpr const uint64_t A = 1103515245; + static constexpr const uint64_t C = 12345; + static constexpr const uint64_t M = 1ULL << 31; + static uint64_t Seed = 123456789; + Seed = (A * Seed + C) % M; + return Seed; +} + +void Randomize(MutableArrayRef Buffer) { + for (auto ¤t : Buffer) + current = GetRandomChar(); +} + +TEST(LlvmLibcMemmoveTest, Thorough) { + using LargeBuffer = Array; + LargeBuffer GroundTruth; + 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); + EXPECT_MEM_EQ(Buffer, Expected); + } + } } diff --git a/libc/utils/UnitTest/CMakeLists.txt b/libc/utils/UnitTest/CMakeLists.txt --- a/libc/utils/UnitTest/CMakeLists.txt +++ b/libc/utils/UnitTest/CMakeLists.txt @@ -32,3 +32,16 @@ libc.src.__support.CPP.standalone_cpp libc.src.__support.FPUtil.fputil ) + +add_library( + LibcMemoryHelpers + MemoryMatcher.h + MemoryMatcher.cpp +) +target_include_directories(LibcMemoryHelpers PUBLIC ${LIBC_SOURCE_DIR}) +target_link_libraries(LibcMemoryHelpers LibcUnitTest) +add_dependencies( + LibcMemoryHelpers + LibcUnitTest + libc.src.__support.CPP.standalone_cpp +) diff --git a/libc/utils/UnitTest/MemoryMatcher.h b/libc/utils/UnitTest/MemoryMatcher.h new file mode 100644 --- /dev/null +++ b/libc/utils/UnitTest/MemoryMatcher.h @@ -0,0 +1,41 @@ +//===-- MemoryMatcher.h -----------------------------------------*- 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_UTILS_UNITTEST_MEMORY_MATCHER_H +#define LLVM_LIBC_UTILS_UNITTEST_MEMORY_MATCHER_H + +#include "src/__support/CPP/ArrayRef.h" + +#include "utils/UnitTest/Test.h" + +namespace __llvm_libc { +namespace memory { +namespace testing { + +using MemoryView = __llvm_libc::cpp::ArrayRef; + +class MemoryMatcher : public __llvm_libc::testing::Matcher { + MemoryView expected; + MemoryView actual; + +public: + MemoryMatcher(MemoryView expectedValue) : expected(expectedValue) {} + + bool match(MemoryView actualValue); + + void explainError(testutils::StreamWrapper &stream) override; +}; + +} // namespace testing +} // namespace memory +} // namespace __llvm_libc + +#define EXPECT_MEM_EQ(expected, actual) \ + EXPECT_THAT(actual, __llvm_libc::memory::testing::MemoryMatcher(expected)) + +#endif // LLVM_LIBC_UTILS_UNITTEST_MEMORY_MATCHER_H diff --git a/libc/utils/UnitTest/MemoryMatcher.cpp b/libc/utils/UnitTest/MemoryMatcher.cpp new file mode 100644 --- /dev/null +++ b/libc/utils/UnitTest/MemoryMatcher.cpp @@ -0,0 +1,46 @@ +//===-- MemoryMatcher.cpp ---------------------------------------*- 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 "MemoryMatcher.h" + +namespace __llvm_libc { +namespace memory { +namespace testing { + +bool MemoryMatcher::match(MemoryView actualValue) { + actual = actualValue; + return expected.equals(actual); +} + +void display(testutils::StreamWrapper &Stream, char C) { + const auto print = [&Stream](unsigned char I) { + Stream << static_cast(I < 10 ? '0' + I : 'A' + I - 10); + }; + print(static_cast(C) / 16); + print(static_cast(C) & 15); +} + +void display(testutils::StreamWrapper &Stream, MemoryView View) { + for (auto C : View) { + Stream << ' '; + display(Stream, C); + } +} + +void MemoryMatcher::explainError(testutils::StreamWrapper &Stream) { + Stream << "expected :"; + display(Stream, expected); + Stream << '\n'; + Stream << "actual :"; + display(Stream, actual); + Stream << '\n'; +} + +} // namespace testing +} // namespace memory +} // namespace __llvm_libc