279 lines · c
1//===-- String utils --------------------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Standalone string utility functions. Utilities requiring memory allocations10// should be placed in allocating_string_utils.h instead.11//12//===----------------------------------------------------------------------===//13 14#ifndef LLVM_LIBC_SRC_STRING_STRING_UTILS_H15#define LLVM_LIBC_SRC_STRING_STRING_UTILS_H16 17#include "hdr/limits_macros.h"18#include "hdr/stdint_proxy.h" // uintptr_t19#include "hdr/types/size_t.h"20#include "src/__support/CPP/bitset.h"21#include "src/__support/CPP/type_traits.h" // cpp::is_same_v22#include "src/__support/macros/attributes.h"23#include "src/__support/macros/config.h"24#include "src/__support/macros/optimization.h" // LIBC_UNLIKELY25#include "src/string/memory_utils/inline_memcpy.h"26 27#if defined(LIBC_COPT_STRING_UNSAFE_WIDE_READ)28#if LIBC_HAS_VECTOR_TYPE29#include "src/string/memory_utils/generic/inline_strlen.h"30#elif defined(LIBC_TARGET_ARCH_IS_X86)31#include "src/string/memory_utils/x86_64/inline_strlen.h"32#elif defined(LIBC_TARGET_ARCH_IS_AARCH64) && defined(__ARM_NEON)33#include "src/string/memory_utils/aarch64/inline_strlen.h"34#else35namespace string_length_impl = LIBC_NAMESPACE::wide_read;36#endif37#endif // defined(LIBC_COPT_STRING_UNSAFE_WIDE_READ)38 39namespace LIBC_NAMESPACE_DECL {40namespace internal {41 42template <typename Word> LIBC_INLINE constexpr Word repeat_byte(Word byte) {43 static_assert(CHAR_BIT == 8, "repeat_byte assumes a byte is 8 bits.");44 constexpr size_t BITS_IN_BYTE = CHAR_BIT;45 constexpr size_t BYTE_MASK = 0xff;46 Word result = 0;47 byte = byte & BYTE_MASK;48 for (size_t i = 0; i < sizeof(Word); ++i)49 result = (result << BITS_IN_BYTE) | byte;50 return result;51}52 53// The goal of this function is to take in a block of arbitrary size and return54// if it has any bytes equal to zero without branching. This is done by55// transforming the block such that zero bytes become non-zero and non-zero56// bytes become zero.57// The first transformation relies on the properties of carrying in arithmetic58// subtraction. Specifically, if 0x01 is subtracted from a byte that is 0x00,59// then the result for that byte must be equal to 0xff (or 0xfe if the next byte60// needs a carry as well).61// The next transformation is a simple mask. All zero bytes will have the high62// bit set after the subtraction, so each byte is masked with 0x80. This narrows63// the set of bytes that result in a non-zero value to only zero bytes and bytes64// with the high bit and any other bit set.65// The final transformation masks the result of the previous transformations66// with the inverse of the original byte. This means that any byte that had the67// high bit set will no longer have it set, narrowing the list of bytes which68// result in non-zero values to just the zero byte.69template <typename Word> LIBC_INLINE constexpr bool has_zeroes(Word block) {70 constexpr unsigned int LOW_BITS = repeat_byte<Word>(0x01);71 constexpr Word HIGH_BITS = repeat_byte<Word>(0x80);72 Word subtracted = block - LOW_BITS;73 Word inverted = ~block;74 return (subtracted & inverted & HIGH_BITS) != 0;75}76 77template <typename Word>78LIBC_INLINE size_t string_length_wide_read(const char *src) {79 const char *char_ptr = src;80 // Step 1: read 1 byte at a time to align to block size81 for (; reinterpret_cast<uintptr_t>(char_ptr) % sizeof(Word) != 0;82 ++char_ptr) {83 if (*char_ptr == '\0')84 return static_cast<size_t>(char_ptr - src);85 }86 // Step 2: read blocks87 for (const Word *block_ptr = reinterpret_cast<const Word *>(char_ptr);88 !has_zeroes<Word>(*block_ptr); ++block_ptr) {89 char_ptr = reinterpret_cast<const char *>(block_ptr);90 }91 // Step 3: find the zero in the block92 for (; *char_ptr != '\0'; ++char_ptr) {93 ;94 }95 return static_cast<size_t>(char_ptr - src);96}97 98namespace wide_read {99LIBC_INLINE size_t string_length(const char *src) {100 // Unsigned int is the default size for most processors, and on x86-64 it101 // performs better than larger sizes when the src pointer can't be assumed to102 // be aligned to a word boundary, so it's the size we use for reading the103 // string a block at a time.104 return string_length_wide_read<unsigned int>(src);105}106 107} // namespace wide_read108 109// Returns the length of a string, denoted by the first occurrence110// of a null terminator.111template <typename T> LIBC_INLINE size_t string_length(const T *src) {112#ifdef LIBC_COPT_STRING_UNSAFE_WIDE_READ113 if constexpr (cpp::is_same_v<T, char>)114 return string_length_impl::string_length(src);115#endif116 size_t length;117 for (length = 0; *src; ++src, ++length)118 ;119 return length;120}121 122template <typename Word>123LIBC_NO_SANITIZE_OOB_ACCESS LIBC_INLINE void *124find_first_character_wide_read(const unsigned char *src, unsigned char ch,125 size_t n) {126 const unsigned char *char_ptr = src;127 size_t cur = 0;128 129 // Step 1: read 1 byte at a time to align to block size130 for (; cur < n && reinterpret_cast<uintptr_t>(char_ptr) % sizeof(Word) != 0;131 ++cur, ++char_ptr) {132 if (*char_ptr == ch)133 return const_cast<unsigned char *>(char_ptr);134 }135 136 const Word ch_mask = repeat_byte<Word>(ch);137 138 // Step 2: read blocks139 const Word *block_ptr = reinterpret_cast<const Word *>(char_ptr);140 for (; cur < n && !has_zeroes<Word>((*block_ptr) ^ ch_mask);141 cur += sizeof(Word), ++block_ptr)142 ;143 char_ptr = reinterpret_cast<const unsigned char *>(block_ptr);144 145 // Step 3: find the match in the block146 for (; cur < n && *char_ptr != ch; ++cur, ++char_ptr) {147 ;148 }149 150 if (cur >= n || *char_ptr != ch)151 return static_cast<void *>(nullptr);152 153 return const_cast<unsigned char *>(char_ptr);154}155 156LIBC_INLINE void *find_first_character_byte_read(const unsigned char *src,157 unsigned char ch, size_t n) {158 for (; n && *src != ch; --n, ++src)159 ;160 return n ? const_cast<unsigned char *>(src) : nullptr;161}162 163// Returns the first occurrence of 'ch' within the first 'n' characters of164// 'src'. If 'ch' is not found, returns nullptr.165LIBC_INLINE void *find_first_character(const unsigned char *src,166 unsigned char ch, size_t max_strlen) {167#ifdef LIBC_COPT_STRING_UNSAFE_WIDE_READ168 // If the maximum size of the string is small, the overhead of aligning to a169 // word boundary and generating a bitmask of the appropriate size may be170 // greater than the gains from reading larger chunks. Based on some testing,171 // the crossover point between when it's faster to just read bytewise and read172 // blocks is somewhere between 16 and 32, so 4 times the size of the block173 // should be in that range.174 // Unsigned int is used for the same reason as in strlen.175 using BlockType = unsigned int;176 if (max_strlen > (sizeof(BlockType) * 4)) {177 return find_first_character_wide_read<BlockType>(src, ch, max_strlen);178 }179#endif180 return find_first_character_byte_read(src, ch, max_strlen);181}182 183// Returns the maximum length span that contains only characters not found in184// 'segment'. If no characters are found, returns the length of 'src'.185LIBC_INLINE size_t complementary_span(const char *src, const char *segment) {186 const char *initial = src;187 cpp::bitset<256> bitset;188 189 for (; *segment; ++segment)190 bitset.set(*reinterpret_cast<const unsigned char *>(segment));191 for (; *src && !bitset.test(*reinterpret_cast<const unsigned char *>(src));192 ++src)193 ;194 return static_cast<size_t>(src - initial);195}196 197// Given the similarities between strtok and strtok_r, we can implement both198// using a utility function. On the first call, 'src' is scanned for the199// first character not found in 'delimiter_string'. Once found, it scans until200// the first character in the 'delimiter_string' or the null terminator is201// found. We define this span as a token. The end of the token is appended with202// a null terminator, and the token is returned. The point where the last token203// is found is then stored within 'context' for subsequent calls. Subsequent204// calls will use 'context' when a nullptr is passed in for 'src'. Once the null205// terminating character is reached, returns a nullptr.206template <bool SkipDelim = true>207LIBC_INLINE char *string_token(char *__restrict src,208 const char *__restrict delimiter_string,209 char **__restrict context) {210 // Return nullptr immediately if both src AND context are nullptr211 if (LIBC_UNLIKELY(src == nullptr && ((src = *context) == nullptr)))212 return nullptr;213 214 static_assert(CHAR_BIT == 8, "bitset of 256 assumes char is 8 bits");215 cpp::bitset<256> delims;216 for (; *delimiter_string != '\0'; ++delimiter_string)217 delims.set(*reinterpret_cast<const unsigned char *>(delimiter_string));218 219 unsigned char *tok_start = reinterpret_cast<unsigned char *>(src);220 if constexpr (SkipDelim)221 while (*tok_start != '\0' && delims.test(*tok_start))222 ++tok_start;223 if (*tok_start == '\0' && SkipDelim) {224 *context = nullptr;225 return nullptr;226 }227 228 unsigned char *tok_end = tok_start;229 while (*tok_end != '\0' && !delims.test(*tok_end))230 ++tok_end;231 232 if (*tok_end == '\0') {233 *context = nullptr;234 } else {235 *tok_end = '\0';236 *context = reinterpret_cast<char *>(tok_end + 1);237 }238 return reinterpret_cast<char *>(tok_start);239}240 241LIBC_INLINE size_t strlcpy(char *__restrict dst, const char *__restrict src,242 size_t size) {243 size_t len = internal::string_length(src);244 if (!size)245 return len;246 size_t n = len < size - 1 ? len : size - 1;247 inline_memcpy(dst, src, n);248 dst[n] = '\0';249 return len;250}251 252template <bool ReturnNull = true>253LIBC_INLINE constexpr static char *strchr_implementation(const char *src,254 int c) {255 char ch = static_cast<char>(c);256 for (; *src && *src != ch; ++src)257 ;258 char *ret = ReturnNull ? nullptr : const_cast<char *>(src);259 return *src == ch ? const_cast<char *>(src) : ret;260}261 262LIBC_INLINE constexpr static char *strrchr_implementation(const char *src,263 int c) {264 char ch = static_cast<char>(c);265 char *last_occurrence = nullptr;266 while (true) {267 if (*src == ch)268 last_occurrence = const_cast<char *>(src);269 if (!*src)270 return last_occurrence;271 ++src;272 }273}274 275} // namespace internal276} // namespace LIBC_NAMESPACE_DECL277 278#endif // LLVM_LIBC_SRC_STRING_STRING_UTILS_H279