[libc] Add strchr implementation.

[cgyurgyik]

Summary

[libc] Adds strchr implementation with unit tests. Fixes signed character bug in memchr.

[PaulkaToast]

libc/src/string/strchr.cpp

23

nit: you could put continue here but not strictly necessary (:

[sivachandra]

libc/src/string/strchr.cpp

19

Whats the benefit of doing this check? Wouldn't the return statement already handle this case?

22

To prevent the behavior of this function to depend on the signedness of the char type, unsigned values should be compared. It should be exactly like in the memchr implementation. But, I just went looking and it looks like you removed casting c to unsigned char over there. Left a note about this over there as well.

libc/test/src/string/strchr_test.cpp

38

Instead of a separate test set, test this in all of the above tests?

63

You should probably put the test here under ShouldFindFirstOfDuplicates above.

[cgyurgyik]

Fix cast to unsigned char in memchr

libc/src/string/strchr.cpp

19

It would, but using strlen requires only a single comparison with 0 while the loop below requires a comparison with 0 and a comparison with ch.

22

Fixed memchr and added a test as well.

23

I will leave it like this for consistency, and I find it slightly more elegant without the continue statement. If you are strongly opposed I can change it.

libc/test/src/string/strchr_test.cpp

38

Is there a benefit to doing this? I want to keep different behavioral components as separate as possible, so that if someone breaks behavior X, only unit test for behavior X breaks, rather than all tests. WDYT?

[sivachandra]

Since the scope of this change has widened, please update the commit message accordingly. Also, if you are not using arcanist, add the link to the phabricator review page in the commit message. You will have to do this on this review page as well as in your local commit.

libc/src/string/strchr.cpp

19

I would expect that a much higher percentage of calls to strchr would be with a non-zero c. In which case, this seems like an optimization for a very special case. For the higher percentage case, it would be an additional conditional.

libc/test/src/string/strchr_test.cpp

38

That the source should not change is required in all cases. Likewise, that the result is correct is required in all cases. So, checking that source does not change separately seems incomplete.

[cgyurgyik]

In D83353#2144598, @sivachandra wrote:

Since the scope of this change has widened, please update the commit message accordingly. Also, if you are not using arcanist, add the link to the phabricator review page in the commit message. You will have to do this on this review page as well as in your local commit.

Done.

libc/src/string/strchr.cpp

19

Removed.

[sivachandra]

libc/src/string/strchr.cpp

18

The comparison should be for two values with the same sign. So, this should be:

unsigned char *str = const_cast<unsigned char *>(reinterpret_cast<const unsigned char *>(src));

When returning, reinterpret_cast it back to char *.

libc/config/linux/aarch64/entrypoints.txt

 set(TARGET_LIBC_ENTRYPOINTS
     # errno.h entrypoints
     libc.src.errno.__errno_location
 
     # string.h entrypoints
     libc.src.string.bzero
     libc.src.string.memcpy
     libc.src.string.memset
     libc.src.string.strcpy
     libc.src.string.strcat
     libc.src.string.strlen
     libc.src.string.memchr
+    libc.src.string.strchr
 )
 
 set(TARGET_LIBM_ENTRYPOINTS
     # math.h entrypoints
     libc.src.math.copysign
     libc.src.math.copysignf
     libc.src.math.copysignl
     libc.src.math.ceil

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.bzero
     libc.src.string.memcpy
     libc.src.string.memset
     libc.src.string.strcpy
     libc.src.string.strcat
     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
     libc.src.sys.mman.munmap
 
     # threads.h entrypoints
     libc.src.threads.call_once
     libc.src.threads.mtx_init

libc/src/string/CMakeLists.txt

 add_entrypoint_object(
   memchr
   SRCS
     memchr.cpp
   HDRS
     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,
 # - Declares an entry point,
 # - Attach the REQUIRE_CPU_FEATURES property to the target,
 # - Add the fully qualified target to `${name}_implementations` global property for tests.
 function(add_implementation name impl_name)
   cmake_parse_arguments(

libc/src/string/memchr.cpp

 #include "src/__support/common.h"
 #include <stddef.h>
 
 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<const unsigned char *>(src);
-  for (; n && *str != c; --n, ++str)
+  const unsigned char ch = c;
+  for (; n && *str != ch; --n, ++str)
     ;
   return n ? const_cast<unsigned char *>(str) : nullptr;
 }
 
 } // namespace __llvm_libc

libc/src/string/strchr.h

+//===-- 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

libc/src/string/strchr.cpp

-//===-- Implementation of memchr ------------------------------------------===//
+//===-- 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/memchr.h"
+#include "src/string/strchr.h"
+#include "src/string/strlen.h"
+
 #include "src/__support/common.h"
-#include <stddef.h>
 
 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<const unsigned char *>(src);
-  for (; n && *str != c; --n, ++str)
+char *LLVM_LIBC_ENTRYPOINT(strchr)(const char *src, int c) {
+  unsigned char *str =
+      const_cast<unsigned char *>(reinterpret_cast<const unsigned char *>(src));
+  const unsigned char ch = c;
+  for (; *str && *str != ch; ++str)
     ;
-  return n ? const_cast<unsigned char *>(str) : nullptr;
+  return *str == ch ? reinterpret_cast<char *>(str) : nullptr;
 }
 
 } // namespace __llvm_libc

libc/test/src/string/CMakeLists.txt

add_libc_unittest(
   SUITE
     libc_string_unittests
   SRCS
     memchr_test.cpp
   DEPENDS
     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)
   foreach(fq_config_name IN LISTS fq_implementations)
     get_target_property(required_cpu_features ${fq_config_name} REQUIRE_CPU_FEATURES)
     host_supports(can_run "${required_cpu_features}")
     if(can_run)
       add_libc_unittest(

libc/test/src/string/memchr_test.cpp

 }
 
 TEST(MemChrTest, SingleRepeatedCharacterShouldReturnFirst) {
   const char *dups = "XXXXX";
   const size_t size = 6; // 5 characters + null terminator.
   // 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);
+}

libc/test/src/string/strchr_test.cpp

+//===-- 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);
+}