diff --git a/libc/src/string/memchr.cpp b/libc/src/string/memchr.cpp --- a/libc/src/string/memchr.cpp +++ b/libc/src/string/memchr.cpp @@ -17,7 +17,8 @@ // TODO: Look at performance benefits of comparing words. LLVM_LIBC_FUNCTION(void *, memchr, (const void *src, int c, size_t n)) { return internal::find_first_character( - reinterpret_cast(src), c, n); + reinterpret_cast(src), + static_cast(c), n); } } // namespace __llvm_libc diff --git a/libc/src/string/memcpy.cpp b/libc/src/string/memcpy.cpp --- a/libc/src/string/memcpy.cpp +++ b/libc/src/string/memcpy.cpp @@ -30,7 +30,7 @@ // implementation parameters. // - As compilers and processors get better, the generated code is improved // with little change on the code side. -static void memcpy_impl(char *__restrict dst, const char *__restrict src, +static void memcpy_impl(unsigned char *__restrict dst, const unsigned char *__restrict src, size_t count) { // Use scalar strategies (_1, _2, _3 ...) using namespace __llvm_libc::scalar; @@ -61,8 +61,8 @@ LLVM_LIBC_FUNCTION(void *, memcpy, (void *__restrict dst, const void *__restrict src, size_t size)) { - memcpy_impl(reinterpret_cast(dst), - reinterpret_cast(src), size); + memcpy_impl(reinterpret_cast(dst), + reinterpret_cast(src), size); return dst; } diff --git a/libc/src/string/memmove.cpp b/libc/src/string/memmove.cpp --- a/libc/src/string/memmove.cpp +++ b/libc/src/string/memmove.cpp @@ -15,13 +15,13 @@ namespace __llvm_libc { -static inline void move_byte_forward(char *dest_m, const char *src_m, +static inline void move_byte_forward(unsigned char *dest_m, const unsigned 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(unsigned char *dest_m, const unsigned char *src_m, size_t count) { for (size_t offset = count - 1; count; --count, --offset) dest_m[offset] = src_m[offset]; @@ -29,8 +29,11 @@ LLVM_LIBC_FUNCTION(void *, memmove, (void *dest, const void *src, size_t count)) { - char *dest_c = reinterpret_cast(dest); - const char *src_c = reinterpret_cast(src); + if (dest == src) + return dest; + + 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 (integerAbs(src_c - dest_c) >= count), they would not overlap. @@ -58,7 +61,7 @@ // TODO: Optimize `move_byte_xxx(...)` functions. if (dest_c < src_c) move_byte_forward(dest_c, src_c, count); - if (dest_c > src_c) + else // (dest_c > src_c) move_byte_backward(dest_c, src_c, count); return dest; } diff --git a/libc/src/string/memrchr.cpp b/libc/src/string/memrchr.cpp --- a/libc/src/string/memrchr.cpp +++ b/libc/src/string/memrchr.cpp @@ -14,11 +14,10 @@ LLVM_LIBC_FUNCTION(void *, memrchr, (const void *src, int c, size_t n)) { const unsigned char *str = reinterpret_cast(src); - const unsigned char ch = c; + const unsigned char ch = static_cast(c); for (; n != 0; --n) { - const unsigned char *s = str + n - 1; - if (*s == ch) - return const_cast(s); + if (*(--str) == ch) + return const_cast(str); } return nullptr; } diff --git a/libc/src/string/strchr.cpp b/libc/src/string/strchr.cpp --- a/libc/src/string/strchr.cpp +++ b/libc/src/string/strchr.cpp @@ -14,12 +14,12 @@ // TODO: Look at performance benefits of comparing words. LLVM_LIBC_FUNCTION(char *, 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; + const char ch = static_cast(c); + for (; *src != ch; ++src) + if (*src == '\0') + return nullptr; + + return const_cast(src); } } // namespace __llvm_libc diff --git a/libc/src/string/strcpy.cpp b/libc/src/string/strcpy.cpp --- a/libc/src/string/strcpy.cpp +++ b/libc/src/string/strcpy.cpp @@ -14,10 +14,56 @@ namespace __llvm_libc { +// Design rationale +// ================ +// +// Using a profiler to observe size distributions for calls into libc +// functions, it was found most operations act on a small number of bytes. +// This makes it important to favor small sizes. +// +// The tests for `count` are in ascending order so the cost of branching is +// proportional to the cost of copying. +// +// The function is written in C++ for several reasons: +// - The compiler can __see__ the code, this is useful when performing Profile +// Guided Optimization as the optimized code can take advantage of branching +// probabilities. +// - It also allows for easier customization and favors testing multiple +// implementation parameters. +// - As compilers and processors get better, the generated code is improved +// with little change on the code side. +static void strcpy_impl(char *__restrict dst, const char *__restrict src, + size_t count) { + // Use scalar strategies (_1, _2, _3 ...) + using namespace __llvm_libc::scalar; + + if (count == 0) + return; + if (count == 1) + return Copy<_1>(dst, src); + if (count == 2) + return Copy<_2>(dst, src); + if (count == 3) + return Copy<_3>(dst, src); + if (count == 4) + return Copy<_4>(dst, src); + if (count < 8) + return Copy>(dst, src, count); + if (count < 16) + return Copy>(dst, src, count); + if (count < 32) + return Copy>(dst, src, count); + if (count < 64) + return Copy>(dst, src, count); + if (count < 128) + return Copy>(dst, src, count); + return Copy::Then>>(dst, src, count); +} + LLVM_LIBC_FUNCTION(char *, strcpy, (char *__restrict dest, const char *__restrict src)) { - return reinterpret_cast( - __llvm_libc::memcpy(dest, src, internal::string_length(src) + 1)); + strcpy_impl(dest, src, internal::string_length(src) + 1)); + return dst; } } // namespace __llvm_libc diff --git a/libc/src/string/string_utils.h b/libc/src/string/string_utils.h --- a/libc/src/string/string_utils.h +++ b/libc/src/string/string_utils.h @@ -18,30 +18,31 @@ // Returns the length of a string, denoted by the first occurrence // of a null terminator. static inline size_t string_length(const char *src) { - size_t length; - for (length = 0; *src; ++src, ++length) + const char *const initial = src; + for (; *src != '\0'; ++src) ; - return length; + return src - initial; } // Returns the first occurrence of 'ch' within the first 'n' characters of // 'src'. If 'ch' is not found, returns nullptr. static inline void *find_first_character(const unsigned char *src, unsigned char ch, size_t n) { - for (; n && *src != ch; --n, ++src) - ; - return n ? const_cast(src) : nullptr; + for (; n != 0; --n, ++src) + if (*src == ch) + return const_cast(src); + return nullptr; } // Returns the maximum length span that contains only characters not found in // 'segment'. If no characters are found, returns the length of 'src'. static inline size_t complementary_span(const char *src, const char *segment) { - const char *initial = src; + const char *const initial = src; cpp::Bitset<256> bitset; - for (; *segment; ++segment) + for (; *segment != '\0'; ++segment) bitset.set(*segment); - for (; *src && !bitset.test(*src); ++src) + for (; *src != '\0' && !bitset.test(*src); ++src) ; return src - initial; } @@ -59,22 +60,21 @@ const char *__restrict delimiter_string, char **__restrict saveptr) { cpp::Bitset<256> delimiter_set; - for (; *delimiter_string; ++delimiter_string) + for (; *delimiter_string != '\0'; ++delimiter_string) delimiter_set.set(*delimiter_string); src = src ? src : *saveptr; - for (; *src && delimiter_set.test(*src); ++src) + for (; *src != '\0' && delimiter_set.test(*src); ++src) ; - if (!*src) { + if (*src == '\0') { *saveptr = src; return nullptr; } char *token = src; - for (; *src && !delimiter_set.test(*src); ++src) + for (; *src != '\0' && !delimiter_set.test(*src); ++src) ; - if (*src) { - *src = '\0'; - ++src; + if (*src != '\0') { + *src++ = '\0'; } *saveptr = src; return token; diff --git a/libc/src/string/strrchr.cpp b/libc/src/string/strrchr.cpp --- a/libc/src/string/strrchr.cpp +++ b/libc/src/string/strrchr.cpp @@ -13,12 +13,12 @@ namespace __llvm_libc { LLVM_LIBC_FUNCTION(char *, strrchr, (const char *src, int c)) { - const char ch = c; + const char ch = static_cast(c); char *last_occurrence = nullptr; do { if (*src == ch) last_occurrence = const_cast(src); - } while (*src++); + } while (*src++ != '\0'); return last_occurrence; }