diff --git a/libc/config/linux/aarch64/entrypoints.txt b/libc/config/linux/aarch64/entrypoints.txt --- a/libc/config/linux/aarch64/entrypoints.txt +++ b/libc/config/linux/aarch64/entrypoints.txt @@ -28,6 +28,7 @@ libc.src.string.memchr libc.src.string.memcmp libc.src.string.memcpy + libc.src.string.memmove libc.src.string.memset libc.src.string.memrchr libc.src.string.strcat diff --git a/libc/config/linux/x86_64/entrypoints.txt b/libc/config/linux/x86_64/entrypoints.txt --- a/libc/config/linux/x86_64/entrypoints.txt +++ b/libc/config/linux/x86_64/entrypoints.txt @@ -50,6 +50,7 @@ libc.src.string.memchr libc.src.string.memcmp libc.src.string.memcpy + libc.src.string.memmove libc.src.string.memrchr libc.src.string.memset libc.src.string.strcat 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 @@ -66,6 +66,17 @@ memcmp.h ) +add_entrypoint_object( + memmove + SRCS + memmove.cpp + HDRS + memmove.h + DEPENDS + libc.src.stdlib.abs_utils + libc.src.string.memcpy +) + add_entrypoint_object( strchr SRCS diff --git a/libc/src/string/memmove.h b/libc/src/string/memmove.h new file mode 100644 --- /dev/null +++ b/libc/src/string/memmove.h @@ -0,0 +1,20 @@ +//===-- Implementation header for memmove -----------------------*- 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_SRC_STRING_MEMMOVE_H +#define LLVM_LIBC_SRC_STRING_MEMMOVE_H + +#include // size_t + +namespace __llvm_libc { + +void *memmove(void *dest, const void *src, size_t count); + +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SRC_STRING_MEMMOVE_H diff --git a/libc/src/string/memmove.cpp b/libc/src/string/memmove.cpp new file mode 100644 --- /dev/null +++ b/libc/src/string/memmove.cpp @@ -0,0 +1,61 @@ +//===-- Implementation of 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/memmove.h" +#include "src/__support/common.h" +#include "src/stdlib/abs_utils.h" +#include "src/string/memcpy.h" +#include // size_t, ptrdiff_t +#include // ssize_t + +namespace __llvm_libc { + +// src_m and dest_m might be the beginning or end. +static inline void move_byte(unsigned char *dest_m, const unsigned char *src_m, + size_t count, ssize_t direction) { + for (ssize_t offset = 0; count; --count, offset += direction) + dest_m[offset] = src_m[offset]; +} + +LLVM_LIBC_FUNCTION(void *, memmove, + (void *dest, const void *src, size_t count)) { + unsigned char *dest_c = reinterpret_cast(dest); + const unsigned char *src_c = reinterpret_cast(src); + + // If the distance between src_c and dest_c is equal to or greater + // than count (labs(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____] + + // Use memcpy if src_c and dest_c do not overlap. + if (__llvm_libc::integer_abs(src_c - dest_c) >= static_cast(count)) + return __llvm_libc::memcpy(dest_c, src_c, 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_] + + // TODO: Optimize `move_byte(...)` function. + if (dest_c < src_c) + move_byte(dest_c, src_c, count, /*pointer add*/ 1); + if (dest_c > src_c) + move_byte(dest_c + count - 1, src_c + count - 1, count, /*pointer add*/ -1); + return dest; +} + +} // namespace __llvm_libc 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 @@ -62,6 +62,17 @@ libc.src.string.memcmp ) +add_libc_unittest( + memmove_test + SUITE + libc_string_unittests + SRCS + memmove_test.cpp + DEPENDS + libc.src.string.memcmp + libc.src.string.memmove +) + add_libc_unittest( strchr_test SUITE diff --git a/libc/test/src/string/memmove_test.cpp b/libc/test/src/string/memmove_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/string/memmove_test.cpp @@ -0,0 +1,70 @@ +//===-- 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 MemmoveTest : public __llvm_libc::testing::Test { +public: + void check_memmove(void *dest, const void *src, size_t count, const void *str, + const __llvm_libc::cpp::ArrayRef 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); + } +}; + +TEST_F(MemmoveTest, MoveZeroByte) { + unsigned char dest[] = {'a', 'b'}; + const unsigned char src[] = {'y', 'z'}; + const unsigned char expected[] = {'a', 'b'}; + check_memmove(dest, src, 0, dest, expected); +} + +TEST_F(MemmoveTest, OverlapThatDestAndSrcPointToSameAddress) { + unsigned char str[] = {'a', 'b'}; + const unsigned char expected[] = {'a', 'b'}; + check_memmove(str, str, 1, str, expected); +} + +TEST_F(MemmoveTest, OverlapThatDestStartsBeforeSrc) { + // 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]. + check_memmove(&str[1], &str[2], 2, str, expected); +} + +TEST_F(MemmoveTest, OverlapThatDestStartsAfterSrc) { + 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. +// str: [abcdefghij] +// [__src_____] +// [_____dest_] +TEST_F(MemmoveTest, SrcFollowDest) { + 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(MemmoveTest, DestFollowSrc) { + unsigned char str[] = {'z', 'a', 'b', 'z'}; + const unsigned char expected[] = {'z', 'a', 'a', 'z'}; + check_memmove(&str[2], &str[1], 1, str, expected); +}