From a4f0c58c6e3f4ec0f5bb8c5232a77dd452df0fb5 Mon Sep 17 00:00:00 2001 From: cgyurgyik Date: Fri, 10 Jul 2020 14:28:20 -0400 Subject: [PATCH] [libc] Add strchr implementation. Fixes bug in memchr. Summary: [libc] Adds strchr implementation with unit tests. Fixes signed character bug in memchr. Reviewers: sivachandra, PaulkaToast Reviewed By: sivachandra Subscribers: mgorny, tschuett, ecnelises, libc-commits Tags: #libc-project Differential Revision: https://reviews.llvm.org/D83353 --- libc/config/linux/aarch64/entrypoints.txt | 1 + libc/config/linux/x86_64/entrypoints.txt | 1 + libc/src/string/CMakeLists.txt | 9 ++++ libc/src/string/memchr.cpp | 3 +- libc/src/string/strchr.cpp | 26 +++++++++ libc/src/string/strchr.h | 18 +++++++ libc/test/src/string/CMakeLists.txt | 10 ++++ libc/test/src/string/memchr_test.cpp | 9 ++++ libc/test/src/string/strchr_test.cpp | 87 +++++++++++++++++++++++++++++++ 9 files changed, 163 insertions(+), 1 deletion(-) create mode 100644 libc/src/string/strchr.cpp create mode 100644 libc/src/string/strchr.h create mode 100644 libc/test/src/string/strchr_test.cpp diff --git a/libc/config/linux/aarch64/entrypoints.txt b/libc/config/linux/aarch64/entrypoints.txt index 1eb9e8a9951..5d607b82892 100644 --- a/libc/config/linux/aarch64/entrypoints.txt +++ b/libc/config/linux/aarch64/entrypoints.txt @@ -10,6 +10,7 @@ set(TARGET_LIBC_ENTRYPOINTS libc.src.string.strcat libc.src.string.strlen libc.src.string.memchr + libc.src.string.strchr ) set(TARGET_LIBM_ENTRYPOINTS diff --git a/libc/config/linux/x86_64/entrypoints.txt b/libc/config/linux/x86_64/entrypoints.txt index 322bf050c71..fc62fbb880b 100644 --- a/libc/config/linux/x86_64/entrypoints.txt +++ b/libc/config/linux/x86_64/entrypoints.txt @@ -28,6 +28,7 @@ set(TARGET_LIBC_ENTRYPOINTS libc.src.string.strlen libc.src.string.strcmp libc.src.string.memchr + libc.src.string.strchr # sys/mman.h entrypoints libc.src.sys.mman.mmap diff --git a/libc/src/string/CMakeLists.txt b/libc/src/string/CMakeLists.txt index 05deee10d71..8d22a139006 100644 --- a/libc/src/string/CMakeLists.txt +++ b/libc/src/string/CMakeLists.txt @@ -52,6 +52,15 @@ add_entrypoint_object( memchr.h ) +add_entrypoint_object( + strchr + SRCS + strchr.cpp + HDRS + strchr.h + DEPENDS + .strlen +) # Helper to define a function with multiple implementations # - Computes flags to satisfy required/rejected features and arch, diff --git a/libc/src/string/memchr.cpp b/libc/src/string/memchr.cpp index eee3d4971ed..303f78185f4 100644 --- a/libc/src/string/memchr.cpp +++ b/libc/src/string/memchr.cpp @@ -15,7 +15,8 @@ namespace __llvm_libc { // TODO: Look at performance benefits of comparing words. void *LLVM_LIBC_ENTRYPOINT(memchr)(const void *src, int c, size_t n) { const unsigned char *str = reinterpret_cast(src); - for (; n && *str != c; --n, ++str) + const unsigned char ch = c; + for (; n && *str != ch; --n, ++str) ; return n ? const_cast(str) : nullptr; } diff --git a/libc/src/string/strchr.cpp b/libc/src/string/strchr.cpp new file mode 100644 index 00000000000..73dc7e7b1c9 --- /dev/null +++ b/libc/src/string/strchr.cpp @@ -0,0 +1,26 @@ +//===-- Implementation of strchr ------------------------------------------===// +// +// 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/strchr.h" +#include "src/string/strlen.h" + +#include "src/__support/common.h" + +namespace __llvm_libc { + +// TODO: Look at performance benefits of comparing words. +char *LLVM_LIBC_ENTRYPOINT(strchr)(const char *src, int c) { + unsigned char *str = + const_cast(reinterpret_cast(src)); + const unsigned char ch = c; + for (; *str && *str != ch; ++str) + ; + return *str == ch ? reinterpret_cast(str) : nullptr; +} + +} // namespace __llvm_libc diff --git a/libc/src/string/strchr.h b/libc/src/string/strchr.h new file mode 100644 index 00000000000..6f106afaf69 --- /dev/null +++ b/libc/src/string/strchr.h @@ -0,0 +1,18 @@ +//===-- Implementation header for strchr ------------------------*- 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_STRCHR_H +#define LLVM_LIBC_SRC_STRING_STRCHR_H + +namespace __llvm_libc { + +char *strchr(const char *src, int c); + +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SRC_STRING_STRCHR_H diff --git a/libc/test/src/string/CMakeLists.txt b/libc/test/src/string/CMakeLists.txt index 0055591be5c..be483681821 100644 --- a/libc/test/src/string/CMakeLists.txt +++ b/libc/test/src/string/CMakeLists.txt @@ -52,6 +52,16 @@ add_libc_unittest( libc.src.string.memchr ) +add_libc_unittest( + strchr_test + SUITE + libc_string_unittests + SRCS + strchr_test.cpp + DEPENDS + libc.src.string.strchr +) + # Tests all implementations that can run on the host. function(add_libc_multi_impl_test name) get_property(fq_implementations GLOBAL PROPERTY ${name}_implementations) diff --git a/libc/test/src/string/memchr_test.cpp b/libc/test/src/string/memchr_test.cpp index 370aa2fa9f1..005e02c6b3d 100644 --- a/libc/test/src/string/memchr_test.cpp +++ b/libc/test/src/string/memchr_test.cpp @@ -111,3 +111,12 @@ TEST(MemChrTest, SingleRepeatedCharacterShouldReturnFirst) { // Should return original string since X is first character. ASSERT_STREQ(call_memchr(dups, 'X', size), dups); } + +TEST(MemChrTest, SignedCharacterFound) { + char c = -1; + const size_t size = 1; + char src[size] = {c}; + const char *actual = call_memchr(src, c, size); + // Should find the first character 'c'. + ASSERT_EQ(actual[0], c); +} diff --git a/libc/test/src/string/strchr_test.cpp b/libc/test/src/string/strchr_test.cpp new file mode 100644 index 00000000000..37b37338579 --- /dev/null +++ b/libc/test/src/string/strchr_test.cpp @@ -0,0 +1,87 @@ +//===-- Unittests for strchr ----------------------------------------------===// +// +// 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/strchr.h" +#include "utils/UnitTest/Test.h" + +TEST(StrChrTest, FindsFirstCharacter) { + const char *src = "abcde"; + const char *src_copy = src; + + // Should return original string since 'a' is the first character. + ASSERT_STREQ(__llvm_libc::strchr(src, 'a'), "abcde"); + // Source string should not change. + ASSERT_STREQ(src, src_copy); +} + +TEST(StrChrTest, FindsMiddleCharacter) { + const char *src = "abcde"; + const char *src_copy = src; + + // Should return characters after (and including) 'c'. + ASSERT_STREQ(__llvm_libc::strchr(src, 'c'), "cde"); + // Source string should not change. + ASSERT_STREQ(src, src_copy); +} + +TEST(StrChrTest, FindsLastCharacterThatIsNotNullTerminator) { + const char *src = "abcde"; + const char *src_copy = src; + + // Should return 'e' and null-terminator. + ASSERT_STREQ(__llvm_libc::strchr(src, 'e'), "e"); + // Source string should not change. + ASSERT_STREQ(src, src_copy); +} + +TEST(StrChrTest, FindsNullTerminator) { + const char *src = "abcde"; + const char *src_copy = src; + + // Should return null terminator. + ASSERT_STREQ(__llvm_libc::strchr(src, '\0'), ""); + // Source string should not change. + ASSERT_STREQ(src, src_copy); +} + +TEST(StrChrTest, CharacterNotWithinStringShouldReturnNullptr) { + // Since 'z' is not within the string, should return nullptr. + ASSERT_STREQ(__llvm_libc::strchr("123?", 'z'), nullptr); +} + +TEST(StrChrTest, TheSourceShouldNotChange) { + const char *src = "abcde"; + const char *src_copy = src; + // When the character is found, the source string should not change. + __llvm_libc::strchr(src, 'd'); + ASSERT_STREQ(src, src_copy); + // Same case for when the character is not found. + __llvm_libc::strchr(src, 'z'); + ASSERT_STREQ(src, src_copy); + // Same case for when looking for nullptr. + __llvm_libc::strchr(src, '\0'); + ASSERT_STREQ(src, src_copy); +} + +TEST(StrChrTest, ShouldFindFirstOfDuplicates) { + // '1' is duplicated in the string, but it should find the first copy. + ASSERT_STREQ(__llvm_libc::strchr("abc1def1ghi", '1'), "1def1ghi"); + + const char *dups = "XXXXX"; + // Should return original string since 'X' is the first character. + ASSERT_STREQ(__llvm_libc::strchr(dups, 'X'), dups); +} + +TEST(StrChrTest, EmptyStringShouldOnlyMatchNullTerminator) { + // Null terminator should match. + ASSERT_STREQ(__llvm_libc::strchr("", '\0'), ""); + // All other characters should not match. + ASSERT_STREQ(__llvm_libc::strchr("", 'Z'), nullptr); + ASSERT_STREQ(__llvm_libc::strchr("", '3'), nullptr); + ASSERT_STREQ(__llvm_libc::strchr("", '*'), nullptr); +} -- 2.11.0