[libc] Some clean work with memmove.

[cheng.w]

Summary

• Replace move_byte_forward() with memcpy. In memcpy implementation,

it copies bytes forward from beginning to end. Otherwise, memmove unit
tests will break.

• Make memmove unit tests work.

[cheng.w]

libc/src/string/memmove.cpp

52–62

@gchatelet Is it possible to have an elementary operation CopyBackward? It copies aligned kBlockSize bytes backward.
Acting like:

CopyBackward<kBlockSize>(dst, src, count) {
  for (size_t i = count / kBlockSize; i > 0; --i)
    Copy(dst + i * kBlockSize, src + i * kBlockSize, kBlockSize)
}

[gchatelet]

libc/src/string/memmove.cpp

52–62

The current framework uses the following API to perform an align copy (code in context)

Copy<Align<Element, Arg::Dst>::Then<Loop<Element>>>(dst, src, count);

To make it backward, we would need to provide ReverseAlign and ReverseLoop operations. It's doable but quite unique to memmove. I'll have a look in the next few days.

[gchatelet]

libc/src/string/memmove.cpp

52–62

Let's submit this as is. memmove is the next function I'll be working on so I'll add the relevant facilities when I start working on it.

libc/src/string/CMakeLists.txt

SRCS
     memchr.cpp
   HDRS
     memchr.h
   DEPENDS
     .string_utils
 )
 
 add_entrypoint_object(
-  memmove
-  SRCS
-    memmove.cpp
-  HDRS
-    memmove.h
-  DEPENDS
-    libc.src.__support.integer_operations
-    libc.src.string.memcpy
-)
-
-add_entrypoint_object(
   memrchr
   SRCS
     memrchr.cpp
   HDRS
     memrchr.h
 )
 
 add_entrypoint_object(
elseif(${LIBC_TARGET_ARCHITECTURE_IS_AARCH64})
   add_memcpy(memcpy                   COMPILE_OPTIONS "SHELL:-mllvm --tail-merge-threshold=0")
 else()
   set(MEMCPY_SRC ${LIBC_SOURCE_DIR}/src/string/memcpy.cpp)
   add_memcpy(memcpy_opt_host          COMPILE_OPTIONS ${LIBC_COMPILE_OPTIONS_NATIVE})
   add_memcpy(memcpy)
 endif()
 
 # ------------------------------------------------------------------------------
+# memmove
+# ------------------------------------------------------------------------------
+
+function(add_memmove memmove_name)
+  add_implementation(memmove ${memmove_name}
+          SRCS ${MEMMOVE_SRC}
+          HDRS ${LIBC_SOURCE_DIR}/src/string/memmove.h
+          DEPENDS
+          .memory_utils.memory_utils
+          libc.src.__support.integer_operations
+          libc.src.string.memcpy
+          COMPILE_OPTIONS
+          -fno-builtin-memmove
+          ${ARGN}
+          )
+endfunction()
+
+set(MEMMOVE_SRC ${LIBC_SOURCE_DIR}/src/string/memmove.cpp)
+add_memmove(memmove)
+
+# ------------------------------------------------------------------------------
 # memset
 # ------------------------------------------------------------------------------
 
 function(add_memset memset_name)
   add_implementation(memset ${memset_name}
     SRCS ${LIBC_SOURCE_DIR}/src/string/memset.cpp
     HDRS ${LIBC_SOURCE_DIR}/src/string/memset.h
     DEPENDS

libc/src/string/memmove.cpp

 
 #include "src/__support/common.h"
 #include "src/__support/integer_operations.h"
 #include "src/string/memcpy.h"
 #include <stddef.h> // 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,
+static inline void move_byte_backward(char *dst, const char *src,
                                       size_t count) {
   for (size_t offset = count - 1; count; --count, --offset)
-    dest_m[offset] = src_m[offset];
+    dst[offset] = src[offset];
 }
 
-LLVM_LIBC_FUNCTION(void *, memmove,
-                   (void *dest, const void *src, size_t count)) {
-  char *dest_c = reinterpret_cast<char *>(dest);
-  const char *src_c = reinterpret_cast<const char *>(src);
+static void memmove_impl(char *dst, const char *src, size_t count) {
 
-  // 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____]
+  // If the distance between `src` and `dst` is equal to or greater
+  // than count (integerAbs(src - dst) >= count), they would not overlap.
+  // e.g. greater     equal       overlapping
+  //      [12345678]  [12345678]  [12345678]
+  // src: [_ab_____]  [_ab_____]  [_ab_____]
+  // dst: [_____yz_]  [___yz___]  [__yz____]
 
-  // Use memcpy if src_c and dest_c do not overlap.
-  if (__llvm_libc::integerAbs(src_c - dest_c) >= static_cast<ptrdiff_t>(count))
-    return __llvm_libc::memcpy(dest_c, src_c, count);
+  // Call `memcpy` when `src` and `dst` do not overlap.
+  if (__llvm_libc::integerAbs(src - dst) >= static_cast<ptrdiff_t>(count))
+    __llvm_libc::memcpy(dst, src, count);
 
   // Overlap 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_]
+  // If `dst` starts before `src` (dst < src), copy forward from beginning to
+  // end. If `dst` starts after `src` (dst > src), copy backward from end to
+  // beginning. If `dst` and `src` start at the same address (dst == src), do
+  // nothing.
+  // e.g. forward      backward
+  //             *->    <-*
+  // src: [___abcde_]  [_abcde___]
+  // dst: [_abc--___]  [___--cde_]
+
+  // In `memcpy` implementation, it copies bytes forward from beginning to
+  // end. Otherwise, `memmove` unit tests will break.
+  if (dst < src)
+    __llvm_libc::memcpy(dst, src, count);
 
   // 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);
-  return dest;
+  if (dst > src)
+    move_byte_backward(dst, src, count);
+}
+
+LLVM_LIBC_FUNCTION(void *, memmove,
+                   (void *dst, const void *src, size_t count)) {
+  memmove_impl(reinterpret_cast<char *>(dst),
+               reinterpret_cast<const char *>(src), count);
+  return dst;
 }
 
 } // namespace __llvm_libc

libc/test/src/string/memmove_test.cpp

 //===-- Unittests for memmove ---------------------------------------------===//
 //
 // 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 "src/string/memcmp.h"
 #include "src/string/memmove.h"
 #include "utils/CPP/ArrayRef.h"
 #include "utils/UnitTest/Test.h"
 
 class LlvmLibcMemmoveTest : public __llvm_libc::testing::Test {
 public:
-  void check_memmove(void *dest, const void *src, size_t count, const void *str,
+  void check_memmove(void *dst, const void *src, size_t count,
+                     const unsigned char *str,
                      const __llvm_libc::cpp::ArrayRef<unsigned char> expected) {
-    void *result = __llvm_libc::memmove(dest, src, count);
-    // Making sure the pointer returned is same with dest.
-    EXPECT_EQ(result, dest);
-    // expected is designed according to str.
-    // dest and src might be part of str.
-    // Making sure the str is same with expected.
-    EXPECT_EQ(__llvm_libc::memcmp(str, expected.data(), expected.size()), 0);
+    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]);
   }
 };
 
 TEST_F(LlvmLibcMemmoveTest, MoveZeroByte) {
-  unsigned char dest[] = {'a', 'b'};
+  unsigned char dst[] = {'a', 'b'};
   const unsigned char src[] = {'y', 'z'};
   const unsigned char expected[] = {'a', 'b'};
-  check_memmove(dest, src, 0, dest, expected);
+  check_memmove(dst, src, 0, dst, expected);
 }
 
-TEST_F(LlvmLibcMemmoveTest, OverlapThatDestAndSrcPointToSameAddress) {
+TEST_F(LlvmLibcMemmoveTest, OverlapThatDstAndSrcPointToSameAddress) {
   unsigned char str[] = {'a', 'b'};
   const unsigned char expected[] = {'a', 'b'};
   check_memmove(str, str, 1, str, expected);
 }
 
-TEST_F(LlvmLibcMemmoveTest, OverlapThatDestStartsBeforeSrc) {
+TEST_F(LlvmLibcMemmoveTest, OverlapThatDstStartsBeforeSrc) {
   // 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'};
-  // dest is &str[1].
+  // `dst` is `&str[1]`.
   check_memmove(&str[1], &str[2], 2, str, expected);
 }
 
-TEST_F(LlvmLibcMemmoveTest, OverlapThatDestStartsAfterSrc) {
+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);
 }
 
-// e.g. dest follow src.
+// e.g. `dst` follow `src`.
 // str: [abcdefghij]
 //      [__src_____]
-//      [_____dest_]
-TEST_F(LlvmLibcMemmoveTest, SrcFollowDest) {
+//      [_____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);
 }
 
-TEST_F(LlvmLibcMemmoveTest, DestFollowSrc) {
+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);
 }