Warning: This file is not a C or C++ file. It does not have highlighting.
| 1 | //===-- Generic implementation of memory function building blocks ---------===// |
|---|---|
| 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-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | // |
| 9 | // This file provides generic C++ building blocks. |
| 10 | // Depending on the requested size, the block operation uses unsigned integral |
| 11 | // types, vector types or an array of the type with the maximum size. |
| 12 | // |
| 13 | // The maximum size is passed as a template argument. For instance, on x86 |
| 14 | // platforms that only supports integral types the maximum size would be 8 |
| 15 | // (corresponding to uint64_t). On this platform if we request the size 32, this |
| 16 | // would be treated as a cpp::array<uint64_t, 4>. |
| 17 | // |
| 18 | // On the other hand, if the platform is x86 with support for AVX the maximum |
| 19 | // size is 32 and the operation can be handled with a single native operation. |
| 20 | // |
| 21 | //===----------------------------------------------------------------------===// |
| 22 | |
| 23 | #ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_OP_GENERIC_H |
| 24 | #define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_OP_GENERIC_H |
| 25 | |
| 26 | #include "src/__support/CPP/array.h" |
| 27 | #include "src/__support/CPP/type_traits.h" |
| 28 | #include "src/__support/common.h" |
| 29 | #include "src/__support/endian_internal.h" |
| 30 | #include "src/__support/macros/attributes.h" // LIBC_INLINE |
| 31 | #include "src/__support/macros/config.h" // LIBC_NAMESPACE_DECL |
| 32 | #include "src/__support/macros/optimization.h" |
| 33 | #include "src/__support/macros/properties/types.h" // LIBC_TYPES_HAS_INT64 |
| 34 | #include "src/string/memory_utils/op_builtin.h" |
| 35 | #include "src/string/memory_utils/utils.h" |
| 36 | |
| 37 | #include <stdint.h> |
| 38 | |
| 39 | static_assert((UINTPTR_MAX == 4294967295U) || |
| 40 | (UINTPTR_MAX == 18446744073709551615UL), |
| 41 | "We currently only support 32- or 64-bit platforms"); |
| 42 | |
| 43 | namespace LIBC_NAMESPACE_DECL { |
| 44 | // Compiler types using the vector attributes. |
| 45 | using generic_v128 = uint8_t __attribute__((__vector_size__(16))); |
| 46 | using generic_v256 = uint8_t __attribute__((__vector_size__(32))); |
| 47 | using generic_v512 = uint8_t __attribute__((__vector_size__(64))); |
| 48 | } // namespace LIBC_NAMESPACE_DECL |
| 49 | |
| 50 | namespace LIBC_NAMESPACE_DECL { |
| 51 | namespace generic { |
| 52 | |
| 53 | // We accept three types of values as elements for generic operations: |
| 54 | // - scalar : unsigned integral types, |
| 55 | // - vector : compiler types using the vector attributes or platform builtins, |
| 56 | // - array : a cpp::array<T, N> where T is itself either a scalar or a vector. |
| 57 | // The following traits help discriminate between these cases. |
| 58 | |
| 59 | template <typename T> struct is_scalar : cpp::false_type {}; |
| 60 | template <> struct is_scalar<uint8_t> : cpp::true_type {}; |
| 61 | template <> struct is_scalar<uint16_t> : cpp::true_type {}; |
| 62 | template <> struct is_scalar<uint32_t> : cpp::true_type {}; |
| 63 | #ifdef LIBC_TYPES_HAS_INT64 |
| 64 | template <> struct is_scalar<uint64_t> : cpp::true_type {}; |
| 65 | #endif // LIBC_TYPES_HAS_INT64 |
| 66 | // Meant to match std::numeric_limits interface. |
| 67 | // NOLINTNEXTLINE(readability-identifier-naming) |
| 68 | template <typename T> constexpr bool is_scalar_v = is_scalar<T>::value; |
| 69 | |
| 70 | template <typename T> struct is_vector : cpp::false_type {}; |
| 71 | template <> struct is_vector<generic_v128> : cpp::true_type {}; |
| 72 | template <> struct is_vector<generic_v256> : cpp::true_type {}; |
| 73 | template <> struct is_vector<generic_v512> : cpp::true_type {}; |
| 74 | // Meant to match std::numeric_limits interface. |
| 75 | // NOLINTNEXTLINE(readability-identifier-naming) |
| 76 | template <typename T> constexpr bool is_vector_v = is_vector<T>::value; |
| 77 | |
| 78 | template <class T> struct is_array : cpp::false_type {}; |
| 79 | template <class T, size_t N> struct is_array<cpp::array<T, N>> { |
| 80 | // Meant to match std::numeric_limits interface. |
| 81 | // NOLINTNEXTLINE(readability-identifier-naming) |
| 82 | static constexpr bool value = is_scalar_v<T> || is_vector_v<T>; |
| 83 | }; |
| 84 | // Meant to match std::numeric_limits interface. |
| 85 | // NOLINTNEXTLINE(readability-identifier-naming) |
| 86 | template <typename T> constexpr bool is_array_v = is_array<T>::value; |
| 87 | |
| 88 | // Meant to match std::numeric_limits interface. |
| 89 | // NOLINTBEGIN(readability-identifier-naming) |
| 90 | template <typename T> |
| 91 | constexpr bool is_element_type_v = |
| 92 | is_scalar_v<T> || is_vector_v<T> || is_array_v<T>; |
| 93 | // NOLINTEND(readability-identifier-naming) |
| 94 | |
| 95 | // Helper struct to retrieve the number of elements of an array. |
| 96 | template <class T> struct array_size {}; |
| 97 | template <class T, size_t N> |
| 98 | struct array_size<cpp::array<T, N>> : cpp::integral_constant<size_t, N> {}; |
| 99 | // Meant to match std::numeric_limits interface. |
| 100 | // NOLINTNEXTLINE(readability-identifier-naming) |
| 101 | template <typename T> constexpr size_t array_size_v = array_size<T>::value; |
| 102 | |
| 103 | // Generic operations for the above type categories. |
| 104 | |
| 105 | template <typename T> T load(CPtr src) { |
| 106 | static_assert(is_element_type_v<T>); |
| 107 | if constexpr (is_scalar_v<T> || is_vector_v<T>) { |
| 108 | return ::LIBC_NAMESPACE::load<T>(src); |
| 109 | } else if constexpr (is_array_v<T>) { |
| 110 | using value_type = typename T::value_type; |
| 111 | T value; |
| 112 | for (size_t i = 0; i < array_size_v<T>; ++i) |
| 113 | value[i] = load<value_type>(src + (i * sizeof(value_type))); |
| 114 | return value; |
| 115 | } |
| 116 | } |
| 117 | |
| 118 | template <typename T> void store(Ptr dst, T value) { |
| 119 | static_assert(is_element_type_v<T>); |
| 120 | if constexpr (is_scalar_v<T> || is_vector_v<T>) { |
| 121 | ::LIBC_NAMESPACE::store<T>(dst, value); |
| 122 | } else if constexpr (is_array_v<T>) { |
| 123 | using value_type = typename T::value_type; |
| 124 | for (size_t i = 0; i < array_size_v<T>; ++i) |
| 125 | store<value_type>(dst + (i * sizeof(value_type)), value[i]); |
| 126 | } |
| 127 | } |
| 128 | |
| 129 | template <typename T> T splat(uint8_t value) { |
| 130 | static_assert(is_scalar_v<T> || is_vector_v<T>); |
| 131 | if constexpr (is_scalar_v<T>) |
| 132 | return T(~0) / T(0xFF) * T(value); |
| 133 | else if constexpr (is_vector_v<T>) { |
| 134 | T out; |
| 135 | // This for loop is optimized out for vector types. |
| 136 | for (size_t i = 0; i < sizeof(T); ++i) |
| 137 | out[i] = value; |
| 138 | return out; |
| 139 | } |
| 140 | } |
| 141 | |
| 142 | /////////////////////////////////////////////////////////////////////////////// |
| 143 | // Memset |
| 144 | /////////////////////////////////////////////////////////////////////////////// |
| 145 | |
| 146 | template <typename T> struct Memset { |
| 147 | static_assert(is_element_type_v<T>); |
| 148 | static constexpr size_t SIZE = sizeof(T); |
| 149 | |
| 150 | LIBC_INLINE static void block(Ptr dst, uint8_t value) { |
| 151 | if constexpr (is_scalar_v<T> || is_vector_v<T>) { |
| 152 | store<T>(dst, splat<T>(value)); |
| 153 | } else if constexpr (is_array_v<T>) { |
| 154 | using value_type = typename T::value_type; |
| 155 | const auto Splat = splat<value_type>(value); |
| 156 | for (size_t i = 0; i < array_size_v<T>; ++i) |
| 157 | store<value_type>(dst + (i * sizeof(value_type)), Splat); |
| 158 | } |
| 159 | } |
| 160 | |
| 161 | LIBC_INLINE static void tail(Ptr dst, uint8_t value, size_t count) { |
| 162 | block(dst + count - SIZE, value); |
| 163 | } |
| 164 | |
| 165 | LIBC_INLINE static void head_tail(Ptr dst, uint8_t value, size_t count) { |
| 166 | block(dst, value); |
| 167 | tail(dst, value, count); |
| 168 | } |
| 169 | |
| 170 | LIBC_INLINE static void loop_and_tail_offset(Ptr dst, uint8_t value, |
| 171 | size_t count, size_t offset) { |
| 172 | static_assert(SIZE > 1, "a loop of size 1 does not need tail"); |
| 173 | do { |
| 174 | block(dst + offset, value); |
| 175 | offset += SIZE; |
| 176 | } while (offset < count - SIZE); |
| 177 | tail(dst, value, count); |
| 178 | } |
| 179 | |
| 180 | LIBC_INLINE static void loop_and_tail(Ptr dst, uint8_t value, size_t count) { |
| 181 | return loop_and_tail_offset(dst, value, count, 0); |
| 182 | } |
| 183 | }; |
| 184 | |
| 185 | template <typename T, typename... TS> struct MemsetSequence { |
| 186 | static constexpr size_t SIZE = (sizeof(T) + ... + sizeof(TS)); |
| 187 | LIBC_INLINE static void block(Ptr dst, uint8_t value) { |
| 188 | Memset<T>::block(dst, value); |
| 189 | if constexpr (sizeof...(TS) > 0) |
| 190 | return MemsetSequence<TS...>::block(dst + sizeof(T), value); |
| 191 | } |
| 192 | }; |
| 193 | |
| 194 | /////////////////////////////////////////////////////////////////////////////// |
| 195 | // Memmove |
| 196 | /////////////////////////////////////////////////////////////////////////////// |
| 197 | |
| 198 | template <typename T> struct Memmove { |
| 199 | static_assert(is_element_type_v<T>); |
| 200 | static constexpr size_t SIZE = sizeof(T); |
| 201 | |
| 202 | LIBC_INLINE static void block(Ptr dst, CPtr src) { |
| 203 | store<T>(dst, load<T>(src)); |
| 204 | } |
| 205 | |
| 206 | LIBC_INLINE static void head_tail(Ptr dst, CPtr src, size_t count) { |
| 207 | const size_t offset = count - SIZE; |
| 208 | // The load and store operations can be performed in any order as long as |
| 209 | // they are not interleaved. More investigations are needed to determine |
| 210 | // the best order. |
| 211 | const auto head = load<T>(src); |
| 212 | const auto tail = load<T>(src + offset); |
| 213 | store<T>(dst, head); |
| 214 | store<T>(dst + offset, tail); |
| 215 | } |
| 216 | |
| 217 | // Align forward suitable when dst < src. The alignment is performed with |
| 218 | // an HeadTail operation of count ∈ [Alignment, 2 x Alignment]. |
| 219 | // |
| 220 | // e.g. Moving two bytes forward, we make sure src is aligned. |
| 221 | // [ | | | | ] |
| 222 | // [____XXXXXXXXXXXXXXXXXXXXXXXXXXXX_] |
| 223 | // [____LLLLLLLL_____________________] |
| 224 | // [___________LLLLLLLA______________] |
| 225 | // [_SSSSSSSS________________________] |
| 226 | // [________SSSSSSSS_________________] |
| 227 | // |
| 228 | // e.g. Moving two bytes forward, we make sure dst is aligned. |
| 229 | // [ | | | | ] |
| 230 | // [____XXXXXXXXXXXXXXXXXXXXXXXXXXXX_] |
| 231 | // [____LLLLLLLL_____________________] |
| 232 | // [______LLLLLLLL___________________] |
| 233 | // [_SSSSSSSS________________________] |
| 234 | // [___SSSSSSSA______________________] |
| 235 | template <Arg AlignOn> |
| 236 | LIBC_INLINE static void align_forward(Ptr &dst, CPtr &src, size_t &count) { |
| 237 | Ptr prev_dst = dst; |
| 238 | CPtr prev_src = src; |
| 239 | size_t prev_count = count; |
| 240 | align_to_next_boundary<SIZE, AlignOn>(dst, src, count); |
| 241 | adjust(SIZE, dst, src, count); |
| 242 | head_tail(prev_dst, prev_src, prev_count - count); |
| 243 | } |
| 244 | |
| 245 | // Align backward suitable when dst > src. The alignment is performed with |
| 246 | // an HeadTail operation of count ∈ [Alignment, 2 x Alignment]. |
| 247 | // |
| 248 | // e.g. Moving two bytes backward, we make sure src is aligned. |
| 249 | // [ | | | | ] |
| 250 | // [____XXXXXXXXXXXXXXXXXXXXXXXX_____] |
| 251 | // [ _________________ALLLLLLL_______] |
| 252 | // [ ___________________LLLLLLLL_____] |
| 253 | // [____________________SSSSSSSS_____] |
| 254 | // [______________________SSSSSSSS___] |
| 255 | // |
| 256 | // e.g. Moving two bytes backward, we make sure dst is aligned. |
| 257 | // [ | | | | ] |
| 258 | // [____XXXXXXXXXXXXXXXXXXXXXXXX_____] |
| 259 | // [ _______________LLLLLLLL_________] |
| 260 | // [ ___________________LLLLLLLL_____] |
| 261 | // [__________________ASSSSSSS_______] |
| 262 | // [______________________SSSSSSSS___] |
| 263 | template <Arg AlignOn> |
| 264 | LIBC_INLINE static void align_backward(Ptr &dst, CPtr &src, size_t &count) { |
| 265 | Ptr headtail_dst = dst + count; |
| 266 | CPtr headtail_src = src + count; |
| 267 | size_t headtail_size = 0; |
| 268 | align_to_next_boundary<SIZE, AlignOn>(headtail_dst, headtail_src, |
| 269 | headtail_size); |
| 270 | adjust(-2 * SIZE, headtail_dst, headtail_src, headtail_size); |
| 271 | head_tail(headtail_dst, headtail_src, headtail_size); |
| 272 | count -= headtail_size; |
| 273 | } |
| 274 | |
| 275 | // Move forward suitable when dst < src. We load the tail bytes before |
| 276 | // handling the loop. |
| 277 | // |
| 278 | // e.g. Moving two bytes |
| 279 | // [ | | | | |] |
| 280 | // [___XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX___] |
| 281 | // [_________________________LLLLLLLL___] |
| 282 | // [___LLLLLLLL_________________________] |
| 283 | // [_SSSSSSSS___________________________] |
| 284 | // [___________LLLLLLLL_________________] |
| 285 | // [_________SSSSSSSS___________________] |
| 286 | // [___________________LLLLLLLL_________] |
| 287 | // [_________________SSSSSSSS___________] |
| 288 | // [_______________________SSSSSSSS_____] |
| 289 | LIBC_INLINE static void loop_and_tail_forward(Ptr dst, CPtr src, |
| 290 | size_t count) { |
| 291 | static_assert(SIZE > 1, "a loop of size 1 does not need tail"); |
| 292 | const size_t tail_offset = count - SIZE; |
| 293 | const auto tail_value = load<T>(src + tail_offset); |
| 294 | size_t offset = 0; |
| 295 | LIBC_LOOP_NOUNROLL |
| 296 | do { |
| 297 | block(dst + offset, src + offset); |
| 298 | offset += SIZE; |
| 299 | } while (offset < count - SIZE); |
| 300 | store<T>(dst + tail_offset, tail_value); |
| 301 | } |
| 302 | |
| 303 | // Move backward suitable when dst > src. We load the head bytes before |
| 304 | // handling the loop. |
| 305 | // |
| 306 | // e.g. Moving two bytes |
| 307 | // [ | | | | |] |
| 308 | // [___XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX___] |
| 309 | // [___LLLLLLLL_________________________] |
| 310 | // [_________________________LLLLLLLL___] |
| 311 | // [___________________________SSSSSSSS_] |
| 312 | // [_________________LLLLLLLL___________] |
| 313 | // [___________________SSSSSSSS_________] |
| 314 | // [_________LLLLLLLL___________________] |
| 315 | // [___________SSSSSSSS_________________] |
| 316 | // [_____SSSSSSSS_______________________] |
| 317 | LIBC_INLINE static void loop_and_tail_backward(Ptr dst, CPtr src, |
| 318 | size_t count) { |
| 319 | static_assert(SIZE > 1, "a loop of size 1 does not need tail"); |
| 320 | const auto head_value = load<T>(src); |
| 321 | ptrdiff_t offset = count - SIZE; |
| 322 | LIBC_LOOP_NOUNROLL |
| 323 | do { |
| 324 | block(dst + offset, src + offset); |
| 325 | offset -= SIZE; |
| 326 | } while (offset >= 0); |
| 327 | store<T>(dst, head_value); |
| 328 | } |
| 329 | }; |
| 330 | |
| 331 | /////////////////////////////////////////////////////////////////////////////// |
| 332 | // Low level operations for Bcmp and Memcmp that operate on memory locations. |
| 333 | /////////////////////////////////////////////////////////////////////////////// |
| 334 | |
| 335 | // Same as load above but with an offset to the pointer. |
| 336 | // Making the offset explicit hints the compiler to use relevant addressing mode |
| 337 | // consistently. |
| 338 | template <typename T> LIBC_INLINE T load(CPtr ptr, size_t offset) { |
| 339 | return ::LIBC_NAMESPACE::load<T>(ptr + offset); |
| 340 | } |
| 341 | |
| 342 | // Same as above but also makes sure the loaded value is in big endian format. |
| 343 | // This is useful when implementing lexicograhic comparisons as big endian |
| 344 | // scalar comparison directly maps to lexicographic byte comparisons. |
| 345 | template <typename T> LIBC_INLINE T load_be(CPtr ptr, size_t offset) { |
| 346 | return Endian::to_big_endian(load<T>(ptr, offset)); |
| 347 | } |
| 348 | |
| 349 | // Equality: returns true iff values at locations (p1 + offset) and (p2 + |
| 350 | // offset) compare equal. |
| 351 | template <typename T> LIBC_INLINE bool eq(CPtr p1, CPtr p2, size_t offset); |
| 352 | |
| 353 | // Not equals: returns non-zero iff values at locations (p1 + offset) and (p2 + |
| 354 | // offset) differ. |
| 355 | template <typename T> LIBC_INLINE uint32_t neq(CPtr p1, CPtr p2, size_t offset); |
| 356 | |
| 357 | // Lexicographic comparison: |
| 358 | // - returns 0 iff values at locations (p1 + offset) and (p2 + offset) compare |
| 359 | // equal. |
| 360 | // - returns a negative value if value at location (p1 + offset) is |
| 361 | // lexicographically less than value at (p2 + offset). |
| 362 | // - returns a positive value if value at location (p1 + offset) is |
| 363 | // lexicographically greater than value at (p2 + offset). |
| 364 | template <typename T> |
| 365 | LIBC_INLINE MemcmpReturnType cmp(CPtr p1, CPtr p2, size_t offset); |
| 366 | |
| 367 | // Lexicographic comparison of non-equal values: |
| 368 | // - returns a negative value if value at location (p1 + offset) is |
| 369 | // lexicographically less than value at (p2 + offset). |
| 370 | // - returns a positive value if value at location (p1 + offset) is |
| 371 | // lexicographically greater than value at (p2 + offset). |
| 372 | template <typename T> |
| 373 | LIBC_INLINE MemcmpReturnType cmp_neq(CPtr p1, CPtr p2, size_t offset); |
| 374 | |
| 375 | /////////////////////////////////////////////////////////////////////////////// |
| 376 | // Memcmp implementation |
| 377 | // |
| 378 | // When building memcmp, not all types are considered equals. |
| 379 | // |
| 380 | // For instance, the lexicographic comparison of two uint8_t can be implemented |
| 381 | // as a simple subtraction, but for wider operations the logic can be much more |
| 382 | // involving, especially on little endian platforms. |
| 383 | // |
| 384 | // For such wider types it is a good strategy to test for equality first and |
| 385 | // only do the expensive lexicographic comparison if necessary. |
| 386 | // |
| 387 | // Decomposing the algorithm like this for wider types allows us to have |
| 388 | // efficient implementation of higher order functions like 'head_tail' or |
| 389 | // 'loop_and_tail'. |
| 390 | /////////////////////////////////////////////////////////////////////////////// |
| 391 | |
| 392 | // Type traits to decide whether we can use 'cmp' directly or if we need to |
| 393 | // split the computation. |
| 394 | template <typename T> struct cmp_is_expensive; |
| 395 | |
| 396 | template <typename T> struct Memcmp { |
| 397 | static_assert(is_element_type_v<T>); |
| 398 | static constexpr size_t SIZE = sizeof(T); |
| 399 | |
| 400 | private: |
| 401 | LIBC_INLINE static MemcmpReturnType block_offset(CPtr p1, CPtr p2, |
| 402 | size_t offset) { |
| 403 | if constexpr (cmp_is_expensive<T>::value) { |
| 404 | if (!eq<T>(p1, p2, offset)) |
| 405 | return cmp_neq<T>(p1, p2, offset); |
| 406 | return MemcmpReturnType::zero(); |
| 407 | } else { |
| 408 | return cmp<T>(p1, p2, offset); |
| 409 | } |
| 410 | } |
| 411 | |
| 412 | public: |
| 413 | LIBC_INLINE static MemcmpReturnType block(CPtr p1, CPtr p2) { |
| 414 | return block_offset(p1, p2, 0); |
| 415 | } |
| 416 | |
| 417 | LIBC_INLINE static MemcmpReturnType tail(CPtr p1, CPtr p2, size_t count) { |
| 418 | return block_offset(p1, p2, count - SIZE); |
| 419 | } |
| 420 | |
| 421 | LIBC_INLINE static MemcmpReturnType head_tail(CPtr p1, CPtr p2, |
| 422 | size_t count) { |
| 423 | if constexpr (cmp_is_expensive<T>::value) { |
| 424 | if (!eq<T>(p1, p2, 0)) |
| 425 | return cmp_neq<T>(p1, p2, 0); |
| 426 | } else { |
| 427 | if (const auto value = cmp<T>(p1, p2, 0)) |
| 428 | return value; |
| 429 | } |
| 430 | return tail(p1, p2, count); |
| 431 | } |
| 432 | |
| 433 | LIBC_INLINE static MemcmpReturnType loop_and_tail(CPtr p1, CPtr p2, |
| 434 | size_t count) { |
| 435 | return loop_and_tail_offset(p1, p2, count, 0); |
| 436 | } |
| 437 | |
| 438 | LIBC_INLINE static MemcmpReturnType |
| 439 | loop_and_tail_offset(CPtr p1, CPtr p2, size_t count, size_t offset) { |
| 440 | if constexpr (SIZE > 1) { |
| 441 | const size_t limit = count - SIZE; |
| 442 | LIBC_LOOP_NOUNROLL |
| 443 | for (; offset < limit; offset += SIZE) { |
| 444 | if constexpr (cmp_is_expensive<T>::value) { |
| 445 | if (!eq<T>(p1, p2, offset)) |
| 446 | return cmp_neq<T>(p1, p2, offset); |
| 447 | } else { |
| 448 | if (const auto value = cmp<T>(p1, p2, offset)) |
| 449 | return value; |
| 450 | } |
| 451 | } |
| 452 | return block_offset(p1, p2, limit); // tail |
| 453 | } else { |
| 454 | // No need for a tail operation when SIZE == 1. |
| 455 | LIBC_LOOP_NOUNROLL |
| 456 | for (; offset < count; offset += SIZE) |
| 457 | if (auto value = cmp<T>(p1, p2, offset)) |
| 458 | return value; |
| 459 | return MemcmpReturnType::zero(); |
| 460 | } |
| 461 | } |
| 462 | |
| 463 | LIBC_INLINE static MemcmpReturnType |
| 464 | loop_and_tail_align_above(size_t threshold, CPtr p1, CPtr p2, size_t count) { |
| 465 | const AlignHelper<sizeof(T)> helper(p1); |
| 466 | if (LIBC_UNLIKELY(count >= threshold) && helper.not_aligned()) { |
| 467 | if (auto value = block(p1, p2)) |
| 468 | return value; |
| 469 | adjust(helper.offset, p1, p2, count); |
| 470 | } |
| 471 | return loop_and_tail(p1, p2, count); |
| 472 | } |
| 473 | }; |
| 474 | |
| 475 | template <typename T, typename... TS> struct MemcmpSequence { |
| 476 | static constexpr size_t SIZE = (sizeof(T) + ... + sizeof(TS)); |
| 477 | LIBC_INLINE static MemcmpReturnType block(CPtr p1, CPtr p2) { |
| 478 | // TODO: test suggestion in |
| 479 | // https://reviews.llvm.org/D148717?id=515724#inline-1446890 |
| 480 | // once we have a proper way to check memory operation latency. |
| 481 | if constexpr (cmp_is_expensive<T>::value) { |
| 482 | if (!eq<T>(p1, p2, 0)) |
| 483 | return cmp_neq<T>(p1, p2, 0); |
| 484 | } else { |
| 485 | if (auto value = cmp<T>(p1, p2, 0)) |
| 486 | return value; |
| 487 | } |
| 488 | if constexpr (sizeof...(TS) > 0) |
| 489 | return MemcmpSequence<TS...>::block(p1 + sizeof(T), p2 + sizeof(T)); |
| 490 | else |
| 491 | return MemcmpReturnType::zero(); |
| 492 | } |
| 493 | }; |
| 494 | |
| 495 | /////////////////////////////////////////////////////////////////////////////// |
| 496 | // Bcmp |
| 497 | /////////////////////////////////////////////////////////////////////////////// |
| 498 | template <typename T> struct Bcmp { |
| 499 | static_assert(is_element_type_v<T>); |
| 500 | static constexpr size_t SIZE = sizeof(T); |
| 501 | |
| 502 | LIBC_INLINE static BcmpReturnType block(CPtr p1, CPtr p2) { |
| 503 | return neq<T>(p1, p2, 0); |
| 504 | } |
| 505 | |
| 506 | LIBC_INLINE static BcmpReturnType tail(CPtr p1, CPtr p2, size_t count) { |
| 507 | const size_t tail_offset = count - SIZE; |
| 508 | return neq<T>(p1, p2, tail_offset); |
| 509 | } |
| 510 | |
| 511 | LIBC_INLINE static BcmpReturnType head_tail(CPtr p1, CPtr p2, size_t count) { |
| 512 | if (const auto value = neq<T>(p1, p2, 0)) |
| 513 | return value; |
| 514 | return tail(p1, p2, count); |
| 515 | } |
| 516 | |
| 517 | LIBC_INLINE static BcmpReturnType loop_and_tail(CPtr p1, CPtr p2, |
| 518 | size_t count) { |
| 519 | return loop_and_tail_offset(p1, p2, count, 0); |
| 520 | } |
| 521 | |
| 522 | LIBC_INLINE static BcmpReturnType |
| 523 | loop_and_tail_offset(CPtr p1, CPtr p2, size_t count, size_t offset) { |
| 524 | if constexpr (SIZE > 1) { |
| 525 | const size_t limit = count - SIZE; |
| 526 | LIBC_LOOP_NOUNROLL |
| 527 | for (; offset < limit; offset += SIZE) |
| 528 | if (const auto value = neq<T>(p1, p2, offset)) |
| 529 | return value; |
| 530 | return tail(p1, p2, count); |
| 531 | } else { |
| 532 | // No need for a tail operation when SIZE == 1. |
| 533 | LIBC_LOOP_NOUNROLL |
| 534 | for (; offset < count; offset += SIZE) |
| 535 | if (const auto value = neq<T>(p1, p2, offset)) |
| 536 | return value; |
| 537 | return BcmpReturnType::zero(); |
| 538 | } |
| 539 | } |
| 540 | |
| 541 | LIBC_INLINE static BcmpReturnType |
| 542 | loop_and_tail_align_above(size_t threshold, CPtr p1, CPtr p2, size_t count) { |
| 543 | static_assert(SIZE > 1, |
| 544 | "No need to align when processing one byte at a time"); |
| 545 | const AlignHelper<sizeof(T)> helper(p1); |
| 546 | if (LIBC_UNLIKELY(count >= threshold) && helper.not_aligned()) { |
| 547 | if (auto value = block(p1, p2)) |
| 548 | return value; |
| 549 | adjust(helper.offset, p1, p2, count); |
| 550 | } |
| 551 | return loop_and_tail(p1, p2, count); |
| 552 | } |
| 553 | }; |
| 554 | |
| 555 | template <typename T, typename... TS> struct BcmpSequence { |
| 556 | static constexpr size_t SIZE = (sizeof(T) + ... + sizeof(TS)); |
| 557 | LIBC_INLINE static BcmpReturnType block(CPtr p1, CPtr p2) { |
| 558 | if (auto value = neq<T>(p1, p2, 0)) |
| 559 | return value; |
| 560 | if constexpr (sizeof...(TS) > 0) |
| 561 | return BcmpSequence<TS...>::block(p1 + sizeof(T), p2 + sizeof(T)); |
| 562 | else |
| 563 | return BcmpReturnType::zero(); |
| 564 | } |
| 565 | }; |
| 566 | |
| 567 | /////////////////////////////////////////////////////////////////////////////// |
| 568 | // Specializations for uint8_t |
| 569 | template <> struct cmp_is_expensive<uint8_t> : public cpp::false_type {}; |
| 570 | template <> LIBC_INLINE bool eq<uint8_t>(CPtr p1, CPtr p2, size_t offset) { |
| 571 | return load<uint8_t>(p1, offset) == load<uint8_t>(p2, offset); |
| 572 | } |
| 573 | template <> LIBC_INLINE uint32_t neq<uint8_t>(CPtr p1, CPtr p2, size_t offset) { |
| 574 | return load<uint8_t>(p1, offset) ^ load<uint8_t>(p2, offset); |
| 575 | } |
| 576 | template <> |
| 577 | LIBC_INLINE MemcmpReturnType cmp<uint8_t>(CPtr p1, CPtr p2, size_t offset) { |
| 578 | return static_cast<int32_t>(load<uint8_t>(p1, offset)) - |
| 579 | static_cast<int32_t>(load<uint8_t>(p2, offset)); |
| 580 | } |
| 581 | template <> |
| 582 | LIBC_INLINE MemcmpReturnType cmp_neq<uint8_t>(CPtr p1, CPtr p2, size_t offset); |
| 583 | |
| 584 | } // namespace generic |
| 585 | } // namespace LIBC_NAMESPACE_DECL |
| 586 | |
| 587 | #endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_OP_GENERIC_H |
| 588 |
Warning: This file is not a C or C++ file. It does not have highlighting.
