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 @@ -35,6 +35,15 @@ Element::Copy(dst, src, size); } +// Fixed-size move from 'src' to 'dst'. +template void Move(char *dst, const char *src) { + Element::Move(dst, src); +} +// Runtime-size move from 'src' to 'dst'. +template void Move(char *dst, const char *src, size_t size) { + Element::Move(dst, src, size); +} + // Fixed-size equality between 'lhs' and 'rhs'. template bool Equals(const char *lhs, const char *rhs) { return Element::Equals(lhs, rhs); @@ -67,6 +76,9 @@ Element::SplatSet(dst, value, size); } +// Stack placeholder for Move operations. +template struct Storage { char bytes[Element::kSize]; }; + // Fixed-size Higher-Order Operations // ---------------------------------- // - Repeated: Repeat the operation several times in a row. @@ -83,6 +95,13 @@ } } + static void Move(char *dst, const char *src) { + const auto Value = Element::Load(src); + Repeated::Move(dst + Element::kSize, + src + Element::kSize); + Element::Store(dst, Value); + } + static bool Equals(const char *lhs, const char *rhs) { for (size_t i = 0; i < ElementCount; ++i) { const size_t offset = i * Element::kSize; @@ -109,6 +128,20 @@ Element::SplatSet(dst + offset, value); } } + + static Storage Load(const char *ptr) { + Storage value; + Copy(reinterpret_cast(&value), ptr); + return value; + } + + static void Store(char *ptr, Storage value) { + Copy(ptr, reinterpret_cast(&value)); + } +}; + +template struct Repeated { + static void Move(char *dst, const char *src) {} }; // Chain the operation of several types. @@ -124,6 +157,12 @@ __llvm_libc::Copy(dst, src); } + static void Move(char *dst, const char *src) { + const auto Value = Head::Load(src); + Chained::Move(dst + Head::kSize, src + Head::kSize); + Head::Store(dst, Value); + } + static bool Equals(const char *lhs, const char *rhs) { if (!__llvm_libc::Equals(lhs, rhs)) return false; @@ -146,6 +185,7 @@ template <> struct Chained<> { static constexpr size_t kSize = 0; static void Copy(char *__restrict dst, const char *__restrict src) {} + static void Move(char *dst, const char *src) {} static bool Equals(const char *lhs, const char *rhs) { return true; } static int ThreeWayCompare(const char *lhs, const char *rhs) { return 0; } static void SplatSet(char *dst, const unsigned char value) {} @@ -166,6 +206,13 @@ ElementB::Copy(dst + kOffset, src + kOffset); } + static void Move(char *dst, const char *src) { + const auto ValueA = ElementA::Load(src); + const auto ValueB = ElementB::Load(src + kOffset); + ElementB::Store(dst + kOffset, ValueB); + ElementA::Store(dst, ValueA); + } + static bool Equals(const char *lhs, const char *rhs) { if (!ElementA::Equals(lhs, rhs)) return false; @@ -241,6 +288,14 @@ Tail::Copy(dst, src, size); } + static void Move(char *dst, const char *src, size_t size) { + const size_t offset = Tail::offset(size); + const auto HeadValue = T::Load(src); + const auto TailValue = T::Load(src + offset); + T::Store(dst + offset, TailValue); + T::Store(dst, HeadValue); + } + static bool Equals(const char *lhs, const char *rhs, size_t size) { if (!T::Equals(lhs, rhs)) return false; @@ -460,6 +515,16 @@ #endif } + static void Move(char *dst, const char *src) { +#if LLVM_LIBC_HAVE_MEMORY_SANITIZER || LLVM_LIBC_HAVE_ADDRESS_SANITIZER + ForLoopMove(dst, src); +#elif __has_builtin(__builtin_memmove) + __builtin_memmove(dst, src, kSize); +#else + ForLoopMove(dst, src); +#endif + } + #if __has_builtin(__builtin_memcmp_inline) #define LLVM_LIBC_MEMCMP __builtin_memcmp_inline #else @@ -486,6 +551,11 @@ for (size_t i = 0; i < kSize; ++i) dst[i] = src[i]; } + + static void ForLoopMove(char *dst, const char *src) { + for (size_t i = 0; i < kSize; ++i) + dst[i] = src[i]; + } }; using _1 = Builtin<1>; @@ -512,6 +582,8 @@ Store(dst, Load(src)); } + static void Move(char *dst, const char *src) { Store(dst, Load(src)); } + static bool Equals(const char *lhs, const char *rhs) { return Load(lhs) == Load(rhs); } @@ -526,15 +598,17 @@ static int ScalarThreeWayCompare(T a, T b); -private: static T Load(const char *ptr) { T value; builtin::Builtin::Copy(reinterpret_cast(&value), ptr); return value; } + static void Store(char *ptr, T value) { builtin::Builtin::Copy(ptr, reinterpret_cast(&value)); } + +private: static T GetSplattedValue(const unsigned char value) { return T(~0) / T(0xFF) * T(value); } diff --git a/libc/src/string/memory_utils/elements_x86.h b/libc/src/string/memory_utils/elements_x86.h --- a/libc/src/string/memory_utils/elements_x86.h +++ b/libc/src/string/memory_utils/elements_x86.h @@ -34,6 +34,10 @@ Base::Store(dst, Base::Load(src)); } + static void Move(char *dst, const char *src) { + Base::Store(dst, Base::Load(src)); + } + static bool Equals(const char *a, const char *b) { return Base::NotEqualMask(Base::Load(a), Base::Load(b)) == 0; } diff --git a/libc/test/src/string/memory_utils/elements_test.cpp b/libc/test/src/string/memory_utils/elements_test.cpp --- a/libc/test/src/string/memory_utils/elements_test.cpp +++ b/libc/test/src/string/memory_utils/elements_test.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "src/__support/CPP/Array.h" +#include "src/__support/CPP/ArrayRef.h" #include "src/string/memory_utils/elements.h" #include "utils/UnitTest/Test.h" @@ -50,11 +51,16 @@ return seed; } +void Randomize(cpp::MutableArrayRef buffer) { + for (auto ¤t : buffer) + current = GetRandomChar(); +} + template using Buffer = cpp::Array; + template Buffer GetRandomBuffer() { Buffer buffer; - for (auto ¤t : buffer) - current = GetRandomChar(); + Randomize(buffer); return buffer; } @@ -66,6 +72,34 @@ EXPECT_EQ(Dst[i], buffer[i]); } +template T Copy(const T &Input) { + T Output; + for (size_t I = 0; I < Input.size(); ++I) + Output[I] = Input[I]; + return Output; +} + +TYPED_TEST(LlvmLibcMemoryElements, Move, FixedSizeTypes) { + constexpr size_t kSize = ParamType::kSize; + using LargeBuffer = cpp::Array; + LargeBuffer GroundTruth; + Randomize(GroundTruth); + // Forward, we move the kSize first bytes from offset 0 to kSize. + for (size_t Offset = 0; Offset < kSize; ++Offset) { + LargeBuffer Buffer = Copy(GroundTruth); + Move(&Buffer[Offset], &Buffer[0]); + for (size_t I = 0; I < kSize; ++I) + EXPECT_EQ(Buffer[I + Offset], GroundTruth[I]); + } + // Backward, we move the kSize last bytes from offset 0 to kSize. + for (size_t Offset = 0; Offset < kSize; ++Offset) { + LargeBuffer Buffer = Copy(GroundTruth); + Move(&Buffer[Offset], &Buffer[kSize]); + for (size_t I = 0; I < kSize; ++I) + EXPECT_EQ(Buffer[I + Offset], GroundTruth[kSize + I]); + } +} + TYPED_TEST(LlvmLibcMemoryElements, Equals, FixedSizeTypes) { const auto buffer = GetRandomBuffer(); EXPECT_TRUE(Equals(buffer.data(), buffer.data()));