1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
|
//===-- String Length -------------------------------------------*- 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
//
//===----------------------------------------------------------------------===//
//
// Basic implementation and dispatch mechanism for performance-sensitive string-
// related code.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_LIBC_SRC_STRING_STRING_LENGTH_H
#define LLVM_LIBC_SRC_STRING_STRING_LENGTH_H
#include "hdr/limits_macros.h"
#include "hdr/stdint_proxy.h" // uintptr_t
#include "hdr/types/size_t.h"
#include "src/__support/CPP/type_traits.h" // cpp::is_same_v
#if LIBC_HAS_VECTOR_TYPE
#include "src/string/memory_utils/generic/inline_strlen.h"
#endif
#if defined(LIBC_TARGET_ARCH_IS_X86)
#include "src/string/memory_utils/x86_64/inline_strlen.h"
#elif defined(LIBC_TARGET_ARCH_IS_AARCH64) && \
(defined(LIBC_TARGET_CPU_HAS_SVE) || defined(__ARM_NEON))
#include "src/string/memory_utils/aarch64/inline_strlen.h"
#endif
// Set sensible defaults
#ifndef LIBC_COPT_STRING_LENGTH_IMPL
#define LIBC_COPT_STRING_LENGTH_IMPL element
#endif
#ifndef LIBC_COPT_FIND_FIRST_CHARACTER_IMPL
#define LIBC_COPT_FIND_FIRST_CHARACTER_IMPL element
#endif
namespace LIBC_NAMESPACE_DECL {
namespace internal {
#if !LIBC_HAS_VECTOR_TYPE
// Forward any clang vector impls to architecture specific ones
namespace arch_vector {}
namespace clang_vector = arch_vector;
#endif
namespace element {
// Element-by-element (usually a byte, but wider for wchar) implementations of
// functions that search for data. Slow, but easy to understand and analyze.
// Returns the length of a string, denoted by the first occurrence
// of a null terminator.
LIBC_INLINE size_t string_length(const char *src) {
size_t length;
for (length = 0; *src; ++src, ++length)
;
return length;
}
template <typename T> LIBC_INLINE size_t string_length_element(const T *src) {
size_t length;
for (length = 0; *src; ++src, ++length)
;
return length;
}
LIBC_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<unsigned char *>(src) : nullptr;
}
} // namespace element
namespace word {
// Non-vector, implementations of functions that search for data by reading from
// memory word-by-word.
template <typename Word> LIBC_INLINE constexpr Word repeat_byte(Word byte) {
static_assert(CHAR_BIT == 8, "repeat_byte assumes a byte is 8 bits.");
constexpr size_t BITS_IN_BYTE = CHAR_BIT;
constexpr size_t BYTE_MASK = 0xff;
Word result = 0;
byte = byte & BYTE_MASK;
for (size_t i = 0; i < sizeof(Word); ++i)
result = (result << BITS_IN_BYTE) | byte;
return result;
}
// The goal of this function is to take in a block of arbitrary size and return
// if it has any bytes equal to zero without branching. This is done by
// transforming the block such that zero bytes become non-zero and non-zero
// bytes become zero.
// The first transformation relies on the properties of carrying in arithmetic
// subtraction. Specifically, if 0x01 is subtracted from a byte that is 0x00,
// then the result for that byte must be equal to 0xff (or 0xfe if the next byte
// needs a carry as well).
// The next transformation is a simple mask. All zero bytes will have the high
// bit set after the subtraction, so each byte is masked with 0x80. This narrows
// the set of bytes that result in a non-zero value to only zero bytes and bytes
// with the high bit and any other bit set.
// The final transformation masks the result of the previous transformations
// with the inverse of the original byte. This means that any byte that had the
// high bit set will no longer have it set, narrowing the list of bytes which
// result in non-zero values to just the zero byte.
template <typename Word> LIBC_INLINE constexpr bool has_zeroes(Word block) {
constexpr unsigned int LOW_BITS = repeat_byte<Word>(0x01);
constexpr Word HIGH_BITS = repeat_byte<Word>(0x80);
Word subtracted = block - LOW_BITS;
Word inverted = ~block;
return (subtracted & inverted & HIGH_BITS) != 0;
}
// Unsigned int is the default size for most processors, and on x86-64 it
// performs better than larger sizes when the src pointer can't be assumed to
// be aligned to a word boundary, so it's the size we use for reading the
// string a block at a time.
LIBC_INLINE size_t string_length(const char *src) {
using Word = unsigned int;
const char *char_ptr = src;
// Step 1: read 1 byte at a time to align to block size
for (; reinterpret_cast<uintptr_t>(char_ptr) % sizeof(Word) != 0;
++char_ptr) {
if (*char_ptr == '\0')
return static_cast<size_t>(char_ptr - src);
}
// Step 2: read blocks
for (const Word *block_ptr = reinterpret_cast<const Word *>(char_ptr);
!has_zeroes<Word>(*block_ptr); ++block_ptr) {
char_ptr = reinterpret_cast<const char *>(block_ptr);
}
// Step 3: find the zero in the block
for (; *char_ptr != '\0'; ++char_ptr) {
;
}
return static_cast<size_t>(char_ptr - src);
}
LIBC_NO_SANITIZE_OOB_ACCESS LIBC_INLINE void *
find_first_character(const unsigned char *src, unsigned char ch,
size_t max_strlen = cpp::numeric_limits<size_t>::max()) {
using Word = unsigned int;
const unsigned char *char_ptr = src;
size_t cur = 0;
// If the maximum size of the string is small, the overhead of aligning to a
// word boundary and generating a bitmask of the appropriate size may be
// greater than the gains from reading larger chunks. Based on some testing,
// the crossover point between when it's faster to just read bytewise and read
// blocks is somewhere between 16 and 32, so 4 times the size of the block
// should be in that range.
if (max_strlen < (sizeof(Word) * 4)) {
return element::find_first_character(src, ch, max_strlen);
}
size_t n = max_strlen;
// Step 1: read 1 byte at a time to align to block size
for (; cur < n && reinterpret_cast<uintptr_t>(char_ptr) % sizeof(Word) != 0;
++cur, ++char_ptr) {
if (*char_ptr == ch)
return const_cast<unsigned char *>(char_ptr);
}
const Word ch_mask = repeat_byte<Word>(ch);
// Step 2: read blocks
const Word *block_ptr = reinterpret_cast<const Word *>(char_ptr);
for (; cur < n && !has_zeroes<Word>((*block_ptr) ^ ch_mask);
cur += sizeof(Word), ++block_ptr)
;
char_ptr = reinterpret_cast<const unsigned char *>(block_ptr);
// Step 3: find the match in the block
for (; cur < n && *char_ptr != ch; ++cur, ++char_ptr) {
;
}
if (cur >= n || *char_ptr != ch)
return static_cast<void *>(nullptr);
return const_cast<unsigned char *>(char_ptr);
}
} // namespace word
// Dispatch mechanism for implementations of performance-sensitive
// functions. Always measure, but generally from lower- to higher-performance
// order:
//
// 1. element - read char-by-char or wchar-by-wchar
// 3. word - read word-by-word
// 3. clang_vector - read using clang's internal vector types
// 4. arch_vector - hand-coded per architecture. Possibly in asm, or with
// intrinsics.
//
// The called implemenation is chosen at build-time by setting
// LIBC_CONF_{FUNC}_IMPL in config.json
static constexpr auto &string_length_impl =
LIBC_COPT_STRING_LENGTH_IMPL::string_length;
static constexpr auto &find_first_character_impl =
LIBC_COPT_FIND_FIRST_CHARACTER_IMPL::find_first_character;
template <typename T> LIBC_INLINE size_t string_length(const T *src) {
if constexpr (cpp::is_same_v<T, char>)
return string_length_impl(src);
return element::string_length_element<T>(src);
}
} // namespace internal
} // namespace LIBC_NAMESPACE_DECL
#endif // LLVM_LIBC_SRC_STRING_STRING_LENGTH_H
|
