[libc] Adds implementation for memrchr.

[lntue]

libc/src/string/memrchr.cpp

19

I think this will be a trouble if n == 0 because n is unsigned.

[cgyurgyik]

libc/src/string/memrchr.cpp

19

You're right. Good catch, thanks.

[cgyurgyik]

libc/src/string/memrchr.cpp

19

Fixed, and added a test where size is 0.

[sivachandra]

This is a GNU extension. So, you need to add entry to https://github.com/llvm/llvm-project/blob/master/libc/spec/gnu_ext.td and linux's api.td.

libc/src/string/memrchr.cpp

19

For better readability, may be:

for (; n != 0; --n) {
  ...
}

[cgyurgyik]

libc/src/string/memrchr.cpp

19

Are you looking for something along these lines:

for (; n != 0; --n) {
      if (str[n] == ch) return const_cast<unsigned char *>(str + n);
  }
  return str[0] == ch ? const_cast<unsigned char *>(str) : nullptr;

Or, am I missing something simpler here?

[cgyurgyik]

In D84469#2172726, @sivachandra wrote:

This is a GNU extension. So, you need to add entry to https://github.com/llvm/llvm-project/blob/master/libc/spec/gnu_ext.td and linux's api.td.

Done. libc.include.string, check-libc, and libc-integration-test all passed.

[sivachandra]

libc/src/string/memrchr.cpp

19

Very close:

for (; n != 0; --n) {
  const unsigned char *s = str + n - 1;
  if (*s == ch)
    return const_cast<unsigned char *>(s);
}
return nullptr;

The post decrement you have currently makes it easy miss that n - 1 offset.

[sivachandra]

libc/config/linux/aarch64/entrypoints.txt

16

I missed in the previous reviews, but can you please sort these lists alphabetically.

[cgyurgyik]

libc/config/linux/aarch64/entrypoints.txt

16

Are you OK with me doing this in a separate commit?

[sivachandra]

libc/config/linux/aarch64/entrypoints.txt

16

OK.

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
     libc.src.string.strstr
     libc.src.string.strnlen
+    libc.src.string.memrchr
 )
 
 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/api.td

let Functions = [
     "strcspn",
     "strpbrk",
     "strrchr",
     "strspn",
     "strstr",
     "strtok",
     "strerror",
     "strlen",
-    "strnlen"
+    "strnlen",
+    "memrchr"
   ];
 
   let TypeDeclarations = [
     SizeT,
   ];
 
   let Macros = [
     NullMacro,

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.strcpy
     libc.src.string.strcat
     libc.src.string.strlen
     libc.src.string.strcmp
     libc.src.string.memchr
     libc.src.string.strchr
     libc.src.string.strstr
     libc.src.string.strnlen
+    libc.src.string.memrchr
 
     # 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/spec/gnu_ext.td

 def GnuExtensions : StandardSpec<"GNUExtensions"> {
   HeaderSpec Math = HeaderSpec<
       "math.h",
       [], // Macros
       [], // Types
       [], // Enumerations
       [
         FunctionSpec<
             "sincosf",
             RetValSpec<VoidType>,
             [ArgSpec<FloatType>, ArgSpec<FloatPtr>, ArgSpec<FloatPtr>]
         >,
       ]
   >;
   
+  HeaderSpec String = HeaderSpec<
+      "string.h",
+      [], // Macros
+      [], // Types
+      [], // Enumerations
+      [ 
+        FunctionSpec<
+            "memrchr",
+            RetValSpec<VoidPtr>,
+            [ArgSpec<VoidPtr>, ArgSpec<IntType>, ArgSpec<SizeTType>]
+        >,
+      ]
+  >;
+
   let Headers = [
-    Math,
+    Math, String,
   ];
 }

libc/src/string/CMakeLists.txt

add_entrypoint_object(
   SRCS
     strnlen.cpp
   HDRS
     strnlen.h
   DEPENDS
     .memchr
 )
 
+add_entrypoint_object(
+  memrchr
+  SRCS
+    memrchr.cpp
+  HDRS
+    memrchr.h
+)
+
 # 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(
     "ADD_IMPL"

libc/src/string/memrchr.h

+//===-- Implementation header for memrchr -----------------------*- 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_MEMRCHR_H
+#define LLVM_LIBC_SRC_STRING_MEMRCHR_H
+
+#include <stddef.h>
+
+namespace __llvm_libc {
+
+void *memrchr(const void *src, int c, size_t n);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_MEMRCHR_H

libc/src/string/memrchr.cpp

+//===-- Implementation of memrchr -----------------------------------------===//
+//
+// 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/memrchr.h"
+#include "src/__support/common.h"
+#include <stddef.h>
+
+namespace __llvm_libc {
+
+void *LLVM_LIBC_ENTRYPOINT(memrchr)(const void *src, int c, size_t n) {
+  const unsigned char *str = reinterpret_cast<const unsigned char *>(src);
+  const unsigned char ch = c;
+  for (; n != 0; --n) {
+    const unsigned char *s = str + n - 1;
+    if (*s == ch)
+      return const_cast<unsigned char *>(s);
+  }
+  return nullptr;
+}
+
+} // namespace __llvm_libc

libc/test/src/string/CMakeLists.txt

add_libc_unittest(
   SUITE
     libc_string_unittests
   SRCS
     strnlen_test.cpp
   DEPENDS
     libc.src.string.strnlen
 )
 
+add_libc_unittest(
+  memrchr_test
+  SUITE
+    libc_string_unittests
+  SRCS
+    memrchr_test.cpp
+  DEPENDS
+    libc.src.string.memrchr
+)
+
 # 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/memrchr_test.cpp

+//===-- Unittests for memrchr ---------------------------------------------===//
+//
+// 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/memrchr.h"
+#include "utils/UnitTest/Test.h"
+#include <stddef.h>
+
+// A helper function that calls memrchr and abstracts away the explicit cast for
+// readability purposes.
+const char *call_memrchr(const void *src, int c, size_t size) {
+  return reinterpret_cast<const char *>(__llvm_libc::memrchr(src, c, size));
+}
+
+TEST(MemRChrTest, FindsCharacterAfterNullTerminator) {
+  // memrchr should continue searching after a null terminator.
+  const size_t size = 6;
+  const unsigned char src[size] = {'a', '\0', 'b', 'c', 'd', '\0'};
+  // Should return 'b', 'c', 'd', '\0' even when after null terminator.
+  ASSERT_STREQ(call_memrchr(src, 'b', size), "bcd");
+}
+
+TEST(MemRChrTest, FindsCharacterInNonNullTerminatedCollection) {
+  const size_t size = 3;
+  const unsigned char src[size] = {'a', 'b', 'c'};
+  // Should return 'b', 'c'.
+  const char *ret = call_memrchr(src, 'b', size);
+  ASSERT_EQ(ret[0], 'b');
+  ASSERT_EQ(ret[1], 'c');
+}
+
+TEST(MemRChrTest, FindsFirstCharacter) {
+  const size_t size = 6;
+  const unsigned char src[size] = {'a', 'b', 'c', 'd', 'e', '\0'};
+  // Should return original array since 'a' is the first character.
+  ASSERT_STREQ(call_memrchr(src, 'a', size), "abcde");
+}
+
+TEST(MemRChrTest, FindsMiddleCharacter) {
+  const size_t size = 6;
+  const unsigned char src[size] = {'a', 'b', 'c', 'd', 'e', '\0'};
+  // Should return characters after (and including) 'c'.
+  ASSERT_STREQ(call_memrchr(src, 'c', size), "cde");
+}
+
+TEST(MemRChrTest, FindsLastCharacterThatIsNotNullTerminator) {
+  const size_t size = 6;
+  const unsigned char src[size] = {'a', 'b', 'c', 'd', 'e', '\0'};
+  // Should return 'e' and null-terminator.
+  ASSERT_STREQ(call_memrchr(src, 'e', size), "e");
+}
+
+TEST(MemRChrTest, FindsNullTerminator) {
+  const size_t size = 6;
+  const unsigned char src[size] = {'a', 'b', 'c', 'd', 'e', '\0'};
+  // Should return null terminator.
+  ASSERT_STREQ(call_memrchr(src, '\0', size), "");
+}
+
+TEST(MemRChrTest, CharacterNotWithinStringShouldReturnNullptr) {
+  const size_t size = 4;
+  const unsigned char src[size] = {'1', '2', '3', '?'};
+  // Since 'z' is not within 'characters', should return nullptr.
+  ASSERT_STREQ(call_memrchr(src, 'z', size), nullptr);
+}
+
+TEST(MemRChrTest, CharacterNotWithinSizeShouldReturnNullptr) {
+  const unsigned char src[5] = {'1', '2', '3', '4', '\0'};
+  // Since '4' is not within the first 2 characters, this should return nullptr.
+  const size_t size = 2;
+  ASSERT_STREQ(call_memrchr(src, '4', size), nullptr);
+}
+
+TEST(MemRChrTest, ShouldFindLastOfDuplicates) {
+  size_t size = 12; // 11 characters + null terminator.
+  const char *dups = "abc1def1ghi";
+  // 1 is duplicated in 'dups', but it should find the last copy.
+  ASSERT_STREQ(call_memrchr(dups, '1', size), "1ghi");
+
+  const char *repeated = "XXXXX";
+  size = 6; // 5 characters + null terminator.
+  // Should return the last X with the null terminator.
+  ASSERT_STREQ(call_memrchr(repeated, 'X', size), "X");
+}
+
+TEST(MemRChrTest, EmptyStringShouldOnlyMatchNullTerminator) {
+  const size_t size = 1; // Null terminator.
+  const char *empty_string = "";
+  // Null terminator should match.
+  ASSERT_STREQ(call_memrchr(empty_string, '\0', size), "");
+  // All other characters should not match.
+  ASSERT_STREQ(call_memrchr(empty_string, 'A', size), nullptr);
+  ASSERT_STREQ(call_memrchr(empty_string, '9', size), nullptr);
+  ASSERT_STREQ(call_memrchr(empty_string, '?', size), nullptr);
+}
+
+TEST(MemRChrTest, SignedCharacterFound) {
+  char c = -1;
+  const size_t size = 1;
+  char src[size] = {c};
+  const char *actual = call_memrchr(src, c, size);
+  // Should find the last character 'c'.
+  ASSERT_EQ(actual[0], c);
+}
+
+TEST(MemRChrTest, ZeroLengthShouldReturnNullptr) {
+  const unsigned char src[4] = {'a', 'b', 'c', '\0'};
+  // This will iterate over exactly zero characters, so should return nullptr.
+  ASSERT_STREQ(call_memrchr(src, 'd', 0), nullptr);
+}