1 /** 2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 #ifndef PANDA_RUNTIME_ENTRYPOINTS_STRING_INDEX_OF_H_ 16 #define PANDA_RUNTIME_ENTRYPOINTS_STRING_INDEX_OF_H_ 17 18 #include <cstdint> 19 #include <type_traits> 20 #include "utils/bit_utils.h" 21 #include "runtime/include/coretypes/string.h" 22 23 namespace ark::intrinsics { 24 25 /* CC-OFFNXT(G.FUN.01-CPP) false positive */ 26 #if !defined(PANDA_TARGET_ARM64) && !defined(PANDA_TARGET_ARM32) && !defined(PANDA_TARGET_AMD64) && \ 27 !defined(PANDA_TARGET_X86) 28 #error \ 29 "Unknown target architecture. IndexOf implementation assumes that target architecture is little-endian, \ 30 check it and update the file." 31 #endif 32 33 namespace impl { 34 template <typename CharType, typename LoadType> 35 struct IndexOfConstants { 36 }; 37 38 template <> 39 struct IndexOfConstants<uint8_t, uint64_t> { 40 static constexpr uint64_t XOR_SUB_MASK = 0x0101010101010101ULL; 41 static constexpr uint64_t NXOR_OR_MASK = 0x7F7F7F7F7F7F7F7FULL; 42 static constexpr size_t VECTOR_SIZE = sizeof(uint64_t) / sizeof(uint8_t); 43 static constexpr size_t BITS_PER_CHAR = sizeof(uint8_t) * BITS_PER_BYTE; 44 }; 45 46 template <> 47 struct IndexOfConstants<uint16_t, uint64_t> { 48 static constexpr uint64_t XOR_SUB_MASK = 0x0001000100010001ULL; 49 static constexpr uint64_t NXOR_OR_MASK = 0x7FFF7FFF7FFF7FFFULL; 50 static constexpr size_t VECTOR_SIZE = sizeof(uint64_t) / sizeof(uint16_t); 51 static constexpr size_t BITS_PER_CHAR = sizeof(uint16_t) * BITS_PER_BYTE; 52 }; 53 54 template <typename CharType, typename LoadType> 55 LoadType BuildSearchPattern(CharType character) = delete; 56 57 template <typename T> 58 size_t ClzInSwappedBytes(T val) = delete; 59 60 #if defined(PANDA_TARGET_64) && defined(__SIZEOF_INT128__) 61 __extension__ using PandaWideUintT = unsigned __int128; 62 #else 63 using PandaWideUintT = uint64_t; 64 #endif 65 66 template <typename CharType, typename LoadType> 67 int32_t StringIndexOfSwar(CharType *data, int32_t offset, int32_t length, CharType character) 68 { 69 static_assert(std::is_same_v<uint8_t, CharType> || std::is_same_v<uint16_t, CharType>, 70 "Only uint8_t and uint16_t CharTypes are supported"); 71 auto dataTyped = reinterpret_cast<CharType *>(data); 72 auto end = dataTyped + length; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) 73 74 auto ptr = dataTyped + offset; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) 75 auto prefixEnd = reinterpret_cast<CharType *>( 76 std::min((reinterpret_cast<uintptr_t>(ptr) & ~(sizeof(LoadType) - 1)) + sizeof(LoadType), 77 reinterpret_cast<uintptr_t>(end))); 78 ASSERT(prefixEnd >= ptr); 79 ASSERT(prefixEnd <= end); 80 while (ptr < prefixEnd) { 81 if (*ptr == character) { 82 return ptr - dataTyped; 83 } 84 ++ptr; 85 } 86 auto mainEnd = reinterpret_cast<CharType *>(reinterpret_cast<uintptr_t>(end) & ~(sizeof(LoadType) - 1)); 87 ASSERT(mainEnd <= end); 88 LoadType searchPattern = BuildSearchPattern<CharType, LoadType>(character); 89 while (ptr < mainEnd) { 90 LoadType value = *reinterpret_cast<LoadType *>(ptr); 91 LoadType xoredValue = searchPattern ^ value; 92 LoadType eq = (xoredValue - IndexOfConstants<CharType, LoadType>::XOR_SUB_MASK) & 93 ~(xoredValue | IndexOfConstants<CharType, LoadType>::NXOR_OR_MASK); 94 if (eq != 0) { 95 size_t idx = ClzInSwappedBytes<LoadType>(eq) / IndexOfConstants<CharType, LoadType>::BITS_PER_CHAR; 96 ASSERT(ptr[idx] == character); // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) 97 return ptr + idx - dataTyped; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) 98 } 99 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic) 100 ptr += IndexOfConstants<CharType, LoadType>::VECTOR_SIZE; 101 } 102 while (ptr < end) { 103 if (*ptr == character) { 104 return ptr - dataTyped; 105 } 106 ++ptr; 107 } 108 return -1; 109 } 110 111 template <> 112 inline uint64_t BuildSearchPattern<uint8_t, uint64_t>(uint8_t character) 113 { 114 uint64_t mask = (static_cast<uint64_t>(character) << BITS_PER_BYTE) | character; 115 mask = (mask << BITS_PER_UINT16) | mask; 116 return (mask << BITS_PER_UINT32) | mask; 117 } 118 119 template <> 120 inline uint64_t BuildSearchPattern<uint16_t, uint64_t>(uint16_t character) 121 { 122 uint64_t mask = (static_cast<uint64_t>(character) << BITS_PER_UINT16) | character; 123 return (mask << BITS_PER_UINT32) | mask; 124 } 125 126 template <> 127 inline size_t ClzInSwappedBytes<uint64_t>(uint64_t val) 128 { 129 // Don't use ReverseBytes as it may not be replaced with bswap 130 return Clz(__builtin_bswap64(val)); 131 } 132 133 #if defined(PANDA_TARGET_64) && defined(__SIZEOF_INT128__) 134 template <> 135 struct IndexOfConstants<uint16_t, PandaWideUintT> { 136 static constexpr PandaWideUintT XOR_SUB_MASK = 137 (static_cast<PandaWideUintT>(IndexOfConstants<uint16_t, uint64_t>::XOR_SUB_MASK) << BITS_PER_UINT64) | 138 IndexOfConstants<uint16_t, uint64_t>::XOR_SUB_MASK; 139 static constexpr PandaWideUintT NXOR_OR_MASK = 140 (static_cast<PandaWideUintT>(IndexOfConstants<uint16_t, uint64_t>::NXOR_OR_MASK) << BITS_PER_UINT64) | 141 IndexOfConstants<uint16_t, uint64_t>::NXOR_OR_MASK; 142 static constexpr size_t VECTOR_SIZE = sizeof(PandaWideUintT) / sizeof(uint16_t); 143 static constexpr size_t BITS_PER_CHAR = sizeof(uint16_t) * BITS_PER_BYTE; 144 }; 145 146 template <> 147 inline PandaWideUintT BuildSearchPattern<uint16_t, PandaWideUintT>(uint16_t character) 148 { 149 PandaWideUintT mask = (static_cast<uint64_t>(character) << BITS_PER_UINT16) | character; 150 mask = (mask << BITS_PER_UINT32) | mask; 151 return (mask << BITS_PER_UINT64) | mask; 152 } 153 154 template <> 155 inline size_t ClzInSwappedBytes<PandaWideUintT>(PandaWideUintT val) 156 { 157 uint64_t hi = __builtin_bswap64(static_cast<uint64_t>(val >> BITS_PER_UINT64)); 158 uint64_t lo = __builtin_bswap64(static_cast<uint64_t>(val)); 159 if (lo == 0) { 160 return BITS_PER_UINT64 + Clz(hi); 161 } 162 return Clz(lo); 163 } 164 #endif 165 166 inline ALWAYS_INLINE int32_t Utf8StringIndexOfChar(uint8_t *data, size_t offset, size_t length, uint8_t character) 167 { 168 if ((length - offset) >= IndexOfConstants<uint8_t, uint64_t>::VECTOR_SIZE * 2) { 169 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic) 170 auto pos = reinterpret_cast<uint8_t *>(memchr(data + offset, character, length - offset)); 171 return pos == nullptr ? -1 : pos - data; 172 } 173 return StringIndexOfSwar<uint8_t, uint64_t>(data, offset, length, character); 174 } 175 176 inline ALWAYS_INLINE int32_t Utf16StringIndexOfChar(uint16_t *data, size_t offset, size_t length, uint16_t character) 177 { 178 if constexpr (sizeof(PandaWideUintT) >= sizeof(uint64_t)) { 179 if ((length - offset) >= IndexOfConstants<uint16_t, PandaWideUintT>::VECTOR_SIZE * 2) { 180 return StringIndexOfSwar<uint16_t, PandaWideUintT>(data, offset, length, character); 181 } 182 } 183 return StringIndexOfSwar<uint16_t, uint64_t>(data, offset, length, character); 184 } 185 186 } // namespace impl 187 188 // CC-OFFNXT(G.FUD.06) perf critical 189 inline int32_t StringIndexOfU16(void *str, uint16_t character, int32_t offset) 190 { 191 auto string = reinterpret_cast<ark::coretypes::String *>(str); 192 ASSERT(string != nullptr); 193 bool isUtf8 = string->IsMUtf8(); 194 auto length = string->GetLength(); 195 if (offset < 0) { 196 offset = 0; 197 } 198 199 if (static_cast<uint32_t>(offset) >= length) { 200 return -1; 201 } 202 if (isUtf8) { 203 if (character > std::numeric_limits<uint8_t>::max()) { 204 return -1; 205 } 206 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic) 207 return impl::Utf8StringIndexOfChar(string->GetDataMUtf8(), offset, length, character); 208 } 209 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic) 210 return impl::Utf16StringIndexOfChar(string->GetDataUtf16(), offset, length, character); 211 } 212 213 } // namespace ark::intrinsics 214 215 #endif 216