[libc] add memmove basic building blocks
Differential Revision: https://reviews.llvm.org/D113321
GitOrigin-RevId: 1b927b68b66ef54d5cdc36eeecfe9a006e976f1b
diff --git a/src/string/memory_utils/elements.h b/src/string/memory_utils/elements.h
index 119e819..ff47f61 100644
--- a/src/string/memory_utils/elements.h
+++ b/src/string/memory_utils/elements.h
@@ -35,6 +35,15 @@
Element::Copy(dst, src, size);
}
+// Fixed-size move from 'src' to 'dst'.
+template <typename Element> void Move(char *dst, const char *src) {
+ Element::Move(dst, src);
+}
+// Runtime-size move from 'src' to 'dst'.
+template <typename Element> void Move(char *dst, const char *src, size_t size) {
+ Element::Move(dst, src, size);
+}
+
// Fixed-size equality between 'lhs' and 'rhs'.
template <typename Element> 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 <typename Element> struct Storage { char bytes[Element::kSize]; };
+
// Fixed-size Higher-Order Operations
// ----------------------------------
// - Repeated<Type, ElementCount>: 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<Element, ElementCount - 1>::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<Element> Load(const char *ptr) {
+ Storage<Element> value;
+ Copy(reinterpret_cast<char *>(&value), ptr);
+ return value;
+ }
+
+ static void Store(char *ptr, Storage<Element> value) {
+ Copy(ptr, reinterpret_cast<const char *>(&value));
+ }
+};
+
+template <typename Element> struct Repeated<Element, 0> {
+ static void Move(char *dst, const char *src) {}
};
// Chain the operation of several types.
@@ -124,6 +157,12 @@
__llvm_libc::Copy<Head>(dst, src);
}
+ static void Move(char *dst, const char *src) {
+ const auto Value = Head::Load(src);
+ Chained<Tail...>::Move(dst + Head::kSize, src + Head::kSize);
+ Head::Store(dst, Value);
+ }
+
static bool Equals(const char *lhs, const char *rhs) {
if (!__llvm_libc::Equals<Head>(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<T>::Copy(dst, src, size);
}
+ static void Move(char *dst, const char *src, size_t size) {
+ const size_t offset = Tail<T>::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<kSize>::Copy(reinterpret_cast<char *>(&value), ptr);
return value;
}
+
static void Store(char *ptr, T value) {
builtin::Builtin<kSize>::Copy(ptr, reinterpret_cast<const char *>(&value));
}
+
+private:
static T GetSplattedValue(const unsigned char value) {
return T(~0) / T(0xFF) * T(value);
}
diff --git a/src/string/memory_utils/elements_x86.h b/src/string/memory_utils/elements_x86.h
index 3b45275..b67569b 100644
--- a/src/string/memory_utils/elements_x86.h
+++ b/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/test/src/string/memory_utils/elements_test.cpp b/test/src/string/memory_utils/elements_test.cpp
index b081a28..3c269ac 100644
--- a/test/src/string/memory_utils/elements_test.cpp
+++ b/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;
}
-template <typename Element> using Buffer = cpp::Array<char, Element::kSize>;
-template <typename Element> Buffer<Element> GetRandomBuffer() {
- Buffer<Element> buffer;
+void Randomize(cpp::MutableArrayRef<char> buffer) {
for (auto ¤t : buffer)
current = GetRandomChar();
+}
+
+template <typename Element> using Buffer = cpp::Array<char, Element::kSize>;
+
+template <typename Element> Buffer<Element> GetRandomBuffer() {
+ Buffer<Element> buffer;
+ Randomize(buffer);
return buffer;
}
@@ -66,6 +72,34 @@
EXPECT_EQ(Dst[i], buffer[i]);
}
+template <typename T> 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<char, kSize * 2>;
+ 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<ParamType>(&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<ParamType>(&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<ParamType>();
EXPECT_TRUE(Equals<ParamType>(buffer.data(), buffer.data()));
