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 #if !defined(PANDA_TARGET_ARM64) && !defined(PANDA_TARGET_ARM32) && !defined(PANDA_TARGET_AMD64) && \ 26 !defined(PANDA_TARGET_X86) 27 #error \ 28 "Unknown target architecture. IndexOf implementation assumes that target architecture is little-endian, check it and update the file." 29 #endif 30 31 namespace impl { 32 template <typename CharType, typename LoadType> 33 struct IndexOfConstants { 34 }; 35 36 template <> 37 struct IndexOfConstants<uint8_t, uint64_t> { 38 static constexpr uint64_t XOR_SUB_MASK = 0x0101010101010101ULL; 39 static constexpr uint64_t NXOR_OR_MASK = 0x7F7F7F7F7F7F7F7FULL; 40 static constexpr size_t VECTOR_SIZE = sizeof(uint64_t) / sizeof(uint8_t); 41 static constexpr size_t BITS_PER_CHAR = sizeof(uint8_t) * BITS_PER_BYTE; 42 }; 43 44 template <> 45 struct IndexOfConstants<uint16_t, uint64_t> { 46 static constexpr uint64_t XOR_SUB_MASK = 0x0001000100010001ULL; 47 static constexpr uint64_t NXOR_OR_MASK = 0x7FFF7FFF7FFF7FFFULL; 48 static constexpr size_t VECTOR_SIZE = sizeof(uint64_t) / sizeof(uint16_t); 49 static constexpr size_t BITS_PER_CHAR = sizeof(uint16_t) * BITS_PER_BYTE; 50 }; 51 52 template <typename CharType, typename LoadType> 53 LoadType BuildSearchPattern(CharType character) = delete; 54 55 template <typename T> 56 size_t ClzInSwappedBytes(T val) = delete; 57 58 #if defined(PANDA_TARGET_64) && defined(__SIZEOF_INT128__) 59 __extension__ using PandaWideUintT = unsigned __int128; 60 #else 61 using PandaWideUintT = uint64_t; 62 #endif 63 64 template <typename CharType, typename LoadType> 65 int32_t StringIndexOfSwar(CharType *data, int32_t offset, int32_t length, CharType character) 66 { 67 static_assert(std::is_same_v<uint8_t, CharType> || std::is_same_v<uint16_t, CharType>, 68 "Only uint8_t and uint16_t CharTypes are supported"); 69 auto dataTyped = reinterpret_cast<CharType *>(data); 70 auto end = dataTyped + length; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) 71 72 auto ptr = dataTyped + offset; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) 73 auto prefixEnd = reinterpret_cast<CharType *>( 74 std::min((reinterpret_cast<uintptr_t>(ptr) & ~(sizeof(LoadType) - 1)) + sizeof(LoadType), 75 reinterpret_cast<uintptr_t>(end))); 76 ASSERT(prefixEnd >= ptr); 77 ASSERT(prefixEnd <= end); 78 while (ptr < prefixEnd) { 79 if (*ptr == character) { 80 return ptr - dataTyped; 81 } 82 ++ptr; 83 } 84 auto mainEnd = reinterpret_cast<CharType *>(reinterpret_cast<uintptr_t>(end) & ~(sizeof(LoadType) - 1)); 85 ASSERT(mainEnd <= end); 86 LoadType searchPattern = BuildSearchPattern<CharType, LoadType>(character); 87 while (ptr < mainEnd) { 88 LoadType value = *reinterpret_cast<LoadType *>(ptr); 89 LoadType xoredValue = searchPattern ^ value; 90 LoadType eq = (xoredValue - IndexOfConstants<CharType, LoadType>::XOR_SUB_MASK) & 91 ~(xoredValue | IndexOfConstants<CharType, LoadType>::NXOR_OR_MASK); 92 if (eq != 0) { 93 size_t idx = ClzInSwappedBytes<LoadType>(eq) / IndexOfConstants<CharType, LoadType>::BITS_PER_CHAR; 94 ASSERT(ptr[idx] == character); // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) 95 return ptr + idx - dataTyped; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) 96 } 97 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic) 98 ptr += IndexOfConstants<CharType, LoadType>::VECTOR_SIZE; 99 } 100 while (ptr < end) { 101 if (*ptr == character) { 102 return ptr - dataTyped; 103 } 104 ++ptr; 105 } 106 return -1; 107 } 108 109 template <> 110 inline uint64_t BuildSearchPattern<uint8_t, uint64_t>(uint8_t character) 111 { 112 uint64_t mask = (static_cast<uint64_t>(character) << BITS_PER_BYTE) | character; 113 mask = (mask << BITS_PER_UINT16) | mask; 114 return (mask << BITS_PER_UINT32) | mask; 115 } 116 117 template <> 118 inline uint64_t BuildSearchPattern<uint16_t, uint64_t>(uint16_t character) 119 { 120 uint64_t mask = (static_cast<uint64_t>(character) << BITS_PER_UINT16) | character; 121 return (mask << BITS_PER_UINT32) | mask; 122 } 123 124 template <> 125 inline size_t ClzInSwappedBytes<uint64_t>(uint64_t val) 126 { 127 // Don't use ReverseBytes as it may not be replaced with bswap 128 return Clz(__builtin_bswap64(val)); 129 } 130 131 #if defined(PANDA_TARGET_64) && defined(__SIZEOF_INT128__) 132 template <> 133 struct IndexOfConstants<uint16_t, PandaWideUintT> { 134 static constexpr PandaWideUintT XOR_SUB_MASK = 135 (static_cast<PandaWideUintT>(IndexOfConstants<uint16_t, uint64_t>::XOR_SUB_MASK) << BITS_PER_UINT64) | 136 IndexOfConstants<uint16_t, uint64_t>::XOR_SUB_MASK; 137 static constexpr PandaWideUintT NXOR_OR_MASK = 138 (static_cast<PandaWideUintT>(IndexOfConstants<uint16_t, uint64_t>::NXOR_OR_MASK) << BITS_PER_UINT64) | 139 IndexOfConstants<uint16_t, uint64_t>::NXOR_OR_MASK; 140 static constexpr size_t VECTOR_SIZE = sizeof(PandaWideUintT) / sizeof(uint16_t); 141 static constexpr size_t BITS_PER_CHAR = sizeof(uint16_t) * BITS_PER_BYTE; 142 }; 143 144 template <> 145 inline PandaWideUintT BuildSearchPattern<uint16_t, PandaWideUintT>(uint16_t character) 146 { 147 PandaWideUintT mask = (static_cast<uint64_t>(character) << BITS_PER_UINT16) | character; 148 mask = (mask << BITS_PER_UINT32) | mask; 149 return (mask << BITS_PER_UINT64) | mask; 150 } 151 152 template <> 153 inline size_t ClzInSwappedBytes<PandaWideUintT>(PandaWideUintT val) 154 { 155 uint64_t hi = __builtin_bswap64(static_cast<uint64_t>(val >> BITS_PER_UINT64)); 156 uint64_t lo = __builtin_bswap64(static_cast<uint64_t>(val)); 157 if (lo == 0) { 158 return BITS_PER_UINT64 + Clz(hi); 159 } 160 return Clz(lo); 161 } 162 #endif 163 164 inline ALWAYS_INLINE int32_t Utf8StringIndexOfChar(uint8_t *data, size_t offset, size_t length, uint8_t character) 165 { 166 if ((length - offset) >= IndexOfConstants<uint8_t, uint64_t>::VECTOR_SIZE * 2) { 167 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic) 168 auto pos = reinterpret_cast<uint8_t *>(memchr(data + offset, character, length - offset)); 169 return pos == nullptr ? -1 : pos - data; 170 } 171 return StringIndexOfSwar<uint8_t, uint64_t>(data, offset, length, character); 172 } 173 174 inline ALWAYS_INLINE int32_t Utf16StringIndexOfChar(uint16_t *data, size_t offset, size_t length, uint16_t character) 175 { 176 if constexpr (sizeof(PandaWideUintT) >= sizeof(uint64_t)) { 177 if ((length - offset) >= IndexOfConstants<uint16_t, PandaWideUintT>::VECTOR_SIZE * 2) { 178 return StringIndexOfSwar<uint16_t, PandaWideUintT>(data, offset, length, character); 179 } 180 } 181 return StringIndexOfSwar<uint16_t, uint64_t>(data, offset, length, character); 182 } 183 184 } // namespace impl 185 186 inline int32_t StringIndexOfU16(void *str, uint16_t character, int32_t offset) 187 { 188 auto string = reinterpret_cast<ark::coretypes::String *>(str); 189 ASSERT(string != nullptr); 190 bool isUtf8 = string->IsMUtf8(); 191 auto length = string->GetLength(); 192 if (offset < 0) { 193 offset = 0; 194 } 195 196 if (static_cast<uint32_t>(offset) >= length) { 197 return -1; 198 } 199 if (isUtf8) { 200 if (character > std::numeric_limits<uint8_t>::max()) { 201 return -1; 202 } 203 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic) 204 return impl::Utf8StringIndexOfChar(string->GetDataMUtf8(), offset, length, character); 205 } 206 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic) 207 return impl::Utf16StringIndexOfChar(string->GetDataUtf16(), offset, length, character); 208 } 209 210 } // namespace ark::intrinsics 211 212 #endif 213