src/internal/scan_engine.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /** | ||
| 2 | * @file internal/scan_engine.cpp | ||
| 3 | * @brief Raw AOB matching engine: anchor selection, the memchr-prefiltered SIMD match loop, parse_aob, and runtime | ||
| 4 | * SIMD-tier detection. | ||
| 5 | * @details The matcher is logger-free and backend-free: the public scan module screens inputs and reports diagnostics; | ||
| 6 | * this engine only finds bytes. The SIMD verify tiers (SSE2 baseline, runtime-gated AVX2, opt-in runtime-gated | ||
| 7 | * AVX-512) sit behind an ASan-safe self-provided memchr prefilter, so the hot path never calls into a libc | ||
| 8 | * interceptor that would inspect the scanner's deliberate cross-region reads. | ||
| 9 | */ | ||
| 10 | |||
| 11 | #include "internal/scan_engine.hpp" | ||
| 12 | |||
| 13 | #include "DetourModKit/defines.hpp" | ||
| 14 | #include "DetourModKit/detail/pattern_core.hpp" | ||
| 15 | |||
| 16 | #include <cstddef> | ||
| 17 | #include <cstdint> | ||
| 18 | #include <new> | ||
| 19 | #include <optional> | ||
| 20 | #include <vector> | ||
| 21 | |||
| 22 | // DMK_ARCH_X64 in defines.hpp rejects every other target, so SSE2 and the AVX2 intrinsic headers are always present | ||
| 23 | // and only the compiler differs. GCC and Clang need a per-function target attribute, which keeps the rest of this | ||
| 24 | // translation unit SSE2-only and runnable on any x86-64 CPU. MSVC exposes the intrinsics unconditionally. Every tier | ||
| 25 | // above SSE2 stays behind its runtime CPUID gate. | ||
| 26 | #include <emmintrin.h> | ||
| 27 | #include <immintrin.h> | ||
| 28 | #if defined(__GNUC__) || defined(__clang__) | ||
| 29 | #include <cpuid.h> | ||
| 30 | #define DMK_AVX2_TARGET __attribute__((target("avx2"))) | ||
| 31 | #else | ||
| 32 | #include <intrin.h> | ||
| 33 | #define DMK_AVX2_TARGET | ||
| 34 | #endif | ||
| 35 | |||
| 36 | // AVX-512 verify tier: opt-in through the DMK_ENABLE_AVX512 build option rather than a global /arch:AVX512 or | ||
| 37 | // -mavx512 flag. A global flag lets the compiler emit AVX-512 across the whole translation unit, and that code faults | ||
| 38 | // with #UD on the majority of CPUs that lack AVX-512. Byte-granular masked compare (_mm512_test_epi8_mask) is an | ||
| 39 | // AVX-512BW instruction, so cpu_has_avx512() requires AVX-512F and AVX-512BW, not F alone. | ||
| 40 | #if defined(DMK_ENABLE_AVX512) | ||
| 41 | #define DMK_HAS_AVX512 1 | ||
| 42 | #if defined(__GNUC__) || defined(__clang__) | ||
| 43 | #define DMK_AVX512_TARGET __attribute__((target("avx512f,avx512bw"))) | ||
| 44 | #else | ||
| 45 | #define DMK_AVX512_TARGET | ||
| 46 | #endif | ||
| 47 | #endif | ||
| 48 | |||
| 49 | // AddressSanitizer poisons the shadow of this process's own committed, readable memory - the redzones around stack | ||
| 50 | // locals and instrumented globals. The AOB scanner deliberately reads across whole readable regions, so under ASan its | ||
| 51 | // in-bounds, never-faulting reads land on poisoned shadow and are reported as overflows. DMK_NO_SANITIZE_ADDRESS | ||
| 52 | // removes the compiler's load instrumentation from such a function, so the read runs exactly as a release build does. | ||
| 53 | // It does NOT stop ASan's libc interceptors (memchr/memcpy are hot-patched at runtime); the scanner therefore routes | ||
| 54 | // the prefilter through a self-provided dmk_memchr that does its own byte comparisons and never calls into libc. The | ||
| 55 | // attribute also covers the verify path's instrumented SIMD/scalar loads. ASan links only under MSVC here (mingw-w64 | ||
| 56 | // ships no sanitizer runtime), so the attribute is the MSVC __declspec form; the macro is empty in every other build, | ||
| 57 | // leaving release codegen unchanged. | ||
| 58 | #if defined(_MSC_VER) && defined(__SANITIZE_ADDRESS__) | ||
| 59 | #define DMK_NO_SANITIZE_ADDRESS __declspec(no_sanitize_address) | ||
| 60 | #else | ||
| 61 | #define DMK_NO_SANITIZE_ADDRESS | ||
| 62 | #endif | ||
| 63 | |||
| 64 | namespace DetourModKit | ||
| 65 | { | ||
| 66 | namespace | ||
| 67 | { | ||
| 68 | constexpr unsigned int CPUID_ECX_XSAVE = 1u << 26; | ||
| 69 | constexpr unsigned int CPUID_ECX_OSXSAVE = 1u << 27; | ||
| 70 | constexpr unsigned int CPUID_ECX_AVX = 1u << 28; | ||
| 71 | constexpr unsigned int XCR0_SSE = 1u << 1; | ||
| 72 | constexpr unsigned int XCR0_AVX = 1u << 2; | ||
| 73 | #if defined(DMK_HAS_AVX512) | ||
| 74 | constexpr unsigned int XCR0_OPMASK = 1u << 5; | ||
| 75 | constexpr unsigned int XCR0_ZMM_HI256 = 1u << 6; | ||
| 76 | constexpr unsigned int XCR0_HI16_ZMM = 1u << 7; | ||
| 77 | constexpr unsigned int XCR0_AVX512_STATE = XCR0_SSE | XCR0_AVX | XCR0_OPMASK | XCR0_ZMM_HI256 | XCR0_HI16_ZMM; | ||
| 78 | #endif | ||
| 79 | |||
| 80 | /** | ||
| 81 | * @brief Tests CPUID leaf 1 ECX feature bits. | ||
| 82 | * @param required_bits Bit mask that must be present in ECX. | ||
| 83 | * @return True when every requested leaf 1 ECX feature bit is set. | ||
| 84 | */ | ||
| 85 | 692 | bool cpu_leaf1_ecx_has(unsigned int required_bits) noexcept | |
| 86 | { | ||
| 87 | #if defined(__GNUC__) || defined(__clang__) | ||
| 88 | 692 | unsigned int eax = 0, ebx = 0, ecx = 0, edx = 0; | |
| 89 |
1/2✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 692 times.
|
692 | if (!__get_cpuid(1, &eax, &ebx, &ecx, &edx)) |
| 90 | ✗ | return false; | |
| 91 | 692 | return (ecx & required_bits) == required_bits; | |
| 92 | #elif defined(_MSC_VER) | ||
| 93 | int cpui[4]{}; | ||
| 94 | __cpuidex(cpui, 1, 0); | ||
| 95 | const unsigned int ecx = static_cast<unsigned int>(cpui[2]); | ||
| 96 | return (ecx & required_bits) == required_bits; | ||
| 97 | #else | ||
| 98 | return false; | ||
| 99 | #endif | ||
| 100 | } | ||
| 101 | |||
| 102 | /** | ||
| 103 | * @brief Tests whether the OS has enabled the requested XCR0 SIMD register state. | ||
| 104 | * @param required_mask XCR0 bit mask that must be enabled by the OS. | ||
| 105 | * @return True when XGETBV is legal to execute and XCR0 contains every requested bit. | ||
| 106 | */ | ||
| 107 | 346 | bool xcr0_has_enabled_state(unsigned int required_mask) noexcept | |
| 108 | { | ||
| 109 |
1/2✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 346 times.
|
346 | if (!cpu_leaf1_ecx_has(CPUID_ECX_XSAVE | CPUID_ECX_OSXSAVE)) |
| 110 | { | ||
| 111 | ✗ | return false; | |
| 112 | } | ||
| 113 | |||
| 114 | #if defined(__GNUC__) || defined(__clang__) | ||
| 115 | 346 | unsigned int xcr0_lo = 0, xcr0_hi = 0; | |
| 116 | 346 | __asm__ volatile("xgetbv" : "=a"(xcr0_lo), "=d"(xcr0_hi) : "c"(0)); | |
| 117 | (void)xcr0_hi; | ||
| 118 | 346 | return (xcr0_lo & required_mask) == required_mask; | |
| 119 | #elif defined(_MSC_VER) | ||
| 120 | const unsigned long long xcr0 = _xgetbv(0); | ||
| 121 | return (xcr0 & required_mask) == required_mask; | ||
| 122 | #else | ||
| 123 | return false; | ||
| 124 | #endif | ||
| 125 | } | ||
| 126 | |||
| 127 | /** | ||
| 128 | * @brief Detects AVX2 support at runtime via CPUID. | ||
| 129 | * @details Checks CPUID leaf 1 ECX bit 28 (AVX) plus CPUID leaf 7 subleaf 0 EBX bit 5 (AVX2), then verifies | ||
| 130 | * that | ||
| 131 | * the OS has enabled SSE and AVX register state in XCR0. Result is cached in a function-local static. | ||
| 132 | */ | ||
| 133 | 27366 | bool cpu_has_avx2() noexcept | |
| 134 | { | ||
| 135 | 347 | static const bool result = []() -> bool | |
| 136 | { | ||
| 137 | #if defined(__GNUC__) || defined(__clang__) | ||
| 138 | 346 | unsigned int eax = 0, ebx = 0, ecx = 0, edx = 0; | |
| 139 |
1/2✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 346 times.
|
346 | if (!__get_cpuid_count(7, 0, &eax, &ebx, &ecx, &edx)) |
| 140 | ✗ | return false; | |
| 141 | 346 | const bool avx2_flag = (ebx & (1u << 5)) != 0; | |
| 142 | |||
| 143 |
3/6✓ Branch 6 → 7 taken 346 times.
✗ Branch 6 → 11 not taken.
✓ Branch 7 → 8 taken 346 times.
✗ Branch 7 → 11 not taken.
✓ Branch 9 → 10 taken 346 times.
✗ Branch 9 → 11 not taken.
|
346 | return cpu_leaf1_ecx_has(CPUID_ECX_AVX) && avx2_flag && xcr0_has_enabled_state(XCR0_SSE | XCR0_AVX); |
| 144 | #elif defined(_MSC_VER) | ||
| 145 | int cpui[4]{}; | ||
| 146 | __cpuidex(cpui, 7, 0); | ||
| 147 | const bool avx2_flag = (cpui[1] & (1 << 5)) != 0; | ||
| 148 | |||
| 149 | return cpu_leaf1_ecx_has(CPUID_ECX_AVX) && avx2_flag && xcr0_has_enabled_state(XCR0_SSE | XCR0_AVX); | ||
| 150 | #else | ||
| 151 | return false; | ||
| 152 | #endif | ||
| 153 |
3/4✓ Branch 2 → 3 taken 346 times.
✓ Branch 2 → 8 taken 27020 times.
✓ Branch 4 → 5 taken 346 times.
✗ Branch 4 → 8 not taken.
|
27366 | }(); |
| 154 | 27367 | return result; | |
| 155 | } | ||
| 156 | /** | ||
| 157 | * @brief Verifies a pattern match using AVX2 (32 bytes per iteration). | ||
| 158 | * @param pattern_start Start of the candidate region in memory. | ||
| 159 | * @param pattern The compiled pattern to verify against. | ||
| 160 | * @param start_offset Byte offset to start verification from (may be non-zero if a previous tier partially | ||
| 161 | * verified). | ||
| 162 | * @return The next byte offset to resume verification from on success (equal to pattern.size() when the AVX2 | ||
| 163 | * tier | ||
| 164 | * covered the whole pattern), or std::nullopt when a 32-byte chunk did not match and the caller must | ||
| 165 | * abandon this candidate position. | ||
| 166 | * @note This function is compiled with AVX2 codegen via target attribute on | ||
| 167 | * GCC/Clang. On MSVC, intrinsics are always available. | ||
| 168 | */ | ||
| 169 | DMK_AVX2_TARGET | ||
| 170 | DMK_NO_SANITIZE_ADDRESS | ||
| 171 | 8405609 | std::optional<std::size_t> verify_pattern_avx2( | |
| 172 | const std::byte *pattern_start, | ||
| 173 | const detail::EnginePattern &pattern, | ||
| 174 | std::size_t start_offset | ||
| 175 | ) noexcept | ||
| 176 | { | ||
| 177 | 8405609 | const std::size_t pattern_size = pattern.size(); | |
| 178 | 8405608 | std::size_t j = start_offset; | |
| 179 | |||
| 180 |
2/2✓ Branch 25 → 4 taken 1171121 times.
✓ Branch 25 → 26 taken 7234549 times.
|
8405670 | for (; j + 32 <= pattern_size; j += 32) |
| 181 | { | ||
| 182 | 1171121 | const __m256i mem = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(pattern_start + j)); | |
| 183 | 1171121 | const __m256i pat = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(pattern.bytes.data() + j)); | |
| 184 | 2342242 | const __m256i msk = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(pattern.mask.data() + j)); | |
| 185 | |||
| 186 | 1171121 | const __m256i xored = _mm256_xor_si256(mem, pat); | |
| 187 | 1171121 | const __m256i masked = _mm256_and_si256(xored, msk); | |
| 188 | 2342242 | const __m256i cmp = _mm256_cmpeq_epi8(masked, _mm256_setzero_si256()); | |
| 189 | |||
| 190 |
2/2✓ Branch 22 → 23 taken 1171059 times.
✓ Branch 22 → 24 taken 62 times.
|
1171121 | if (static_cast<unsigned int>(_mm256_movemask_epi8(cmp)) != 0xFFFFFFFFu) |
| 191 | { | ||
| 192 | 1171059 | return std::nullopt; | |
| 193 | } | ||
| 194 | } | ||
| 195 | |||
| 196 | 7234549 | return j; | |
| 197 | } | ||
| 198 | |||
| 199 | #ifdef DMK_HAS_AVX512 | ||
| 200 | /** | ||
| 201 | * @brief Detects AVX-512F + AVX-512BW support at runtime via CPUID and XGETBV. | ||
| 202 | * @details Checks CPUID leaf 7 subleaf 0, EBX bit 16 (AVX-512F) and bit 30 (AVX-512BW). Byte-granular masked | ||
| 203 | * compare is a BW instruction, so both are required. Also verifies the OS has enabled the full opmask | ||
| 204 | * / ZMM register state via XGETBV (XCR0 bits 1,2,5,6,7); a CPU that reports AVX-512 while the OS has | ||
| 205 | * not enabled the state must fail closed. Result is cached in a function-local static. | ||
| 206 | */ | ||
| 207 | bool cpu_has_avx512() noexcept | ||
| 208 | { | ||
| 209 | static const bool result = []() -> bool | ||
| 210 | { | ||
| 211 | #if defined(__GNUC__) || defined(__clang__) | ||
| 212 | unsigned int eax = 0, ebx = 0, ecx = 0, edx = 0; | ||
| 213 | if (!__get_cpuid_count(7, 0, &eax, &ebx, &ecx, &edx)) | ||
| 214 | return false; | ||
| 215 | const bool avx512f = (ebx & (1u << 16)) != 0; | ||
| 216 | const bool avx512bw = (ebx & (1u << 30)) != 0; | ||
| 217 | |||
| 218 | return cpu_leaf1_ecx_has(CPUID_ECX_AVX) && avx512f && avx512bw && | ||
| 219 | xcr0_has_enabled_state(XCR0_AVX512_STATE); | ||
| 220 | #elif defined(_MSC_VER) | ||
| 221 | int cpui[4]{}; | ||
| 222 | __cpuidex(cpui, 7, 0); | ||
| 223 | const bool avx512f = (cpui[1] & (1 << 16)) != 0; | ||
| 224 | const bool avx512bw = (cpui[1] & (1 << 30)) != 0; | ||
| 225 | |||
| 226 | return cpu_leaf1_ecx_has(CPUID_ECX_AVX) && avx512f && avx512bw && | ||
| 227 | xcr0_has_enabled_state(XCR0_AVX512_STATE); | ||
| 228 | #else | ||
| 229 | return false; | ||
| 230 | #endif | ||
| 231 | }(); | ||
| 232 | return result; | ||
| 233 | } | ||
| 234 | |||
| 235 | /** | ||
| 236 | * @brief Verifies a pattern match using AVX-512 (64 bytes per iteration). | ||
| 237 | * @param pattern_start Start of the candidate region in memory. | ||
| 238 | * @param pattern The compiled pattern to verify against. | ||
| 239 | * @param start_offset Byte offset to start verification from (may be non-zero if a previous tier partially | ||
| 240 | * verified). | ||
| 241 | * @return The next byte offset to resume verification from on success (equal to start_offset plus a multiple of | ||
| 242 | * 64 once the AVX-512 tier covered whole 64-byte chunks), or std::nullopt when a 64-byte chunk did not | ||
| 243 | * match and the caller must abandon this candidate position. | ||
| 244 | * @note Compiled with AVX-512F + AVX-512BW codegen via target attribute on GCC/Clang; on MSVC the intrinsics | ||
| 245 | * are | ||
| 246 | * always available. Only entered after cpu_has_avx512() has confirmed CPU and OS support. | ||
| 247 | */ | ||
| 248 | DMK_AVX512_TARGET | ||
| 249 | DMK_NO_SANITIZE_ADDRESS | ||
| 250 | std::optional<std::size_t> verify_pattern_avx512( | ||
| 251 | const std::byte *pattern_start, | ||
| 252 | const detail::EnginePattern &pattern, | ||
| 253 | std::size_t start_offset | ||
| 254 | ) noexcept | ||
| 255 | { | ||
| 256 | const std::size_t pattern_size = pattern.size(); | ||
| 257 | std::size_t j = start_offset; | ||
| 258 | |||
| 259 | for (; j + 64 <= pattern_size; j += 64) | ||
| 260 | { | ||
| 261 | const __m512i mem = _mm512_loadu_si512(reinterpret_cast<const void *>(pattern_start + j)); | ||
| 262 | const __m512i pat = _mm512_loadu_si512(reinterpret_cast<const void *>(pattern.bytes.data() + j)); | ||
| 263 | const __m512i msk = _mm512_loadu_si512(reinterpret_cast<const void *>(pattern.mask.data() + j)); | ||
| 264 | |||
| 265 | // (mem ^ pat) & mask is zero in every matching byte: a wildcard lane (mask 0x00) clears to zero, and a | ||
| 266 | // literal lane (mask 0xFF) keeps the xor, which is zero only on an exact byte match. test_epi8_mask | ||
| 267 | // sets a bit per byte whose masked value is nonzero (a mismatch), so any nonzero result fails the | ||
| 268 | // chunk. | ||
| 269 | const __m512i xored = _mm512_xor_si512(mem, pat); | ||
| 270 | const __m512i masked = _mm512_and_si512(xored, msk); | ||
| 271 | if (_mm512_test_epi8_mask(masked, masked) != 0) | ||
| 272 | { | ||
| 273 | return std::nullopt; | ||
| 274 | } | ||
| 275 | } | ||
| 276 | |||
| 277 | return j; | ||
| 278 | } | ||
| 279 | #endif // DMK_HAS_AVX512 | ||
| 280 | |||
| 281 | /** | ||
| 282 | * @brief Picks the rarest fully-known byte's index in segment 0 of a compiled pattern. | ||
| 283 | * @return The byte index in segment 0 with the lowest frequency score, or `pattern.size()` when segment 0 has | ||
| 284 | * no | ||
| 285 | * fully-known literal byte (every position is a wildcard or only partially masked). | ||
| 286 | * @details Confined to segment 0 (the fixed run before the first bounded jump; the whole pattern when | ||
| 287 | * jump-free) | ||
| 288 | * because the matcher locates that run first and extends across the variable gaps, so only a segment-0 | ||
| 289 | * byte sits at a fixed offset the memchr prefilter can sweep for. | ||
| 290 | */ | ||
| 291 | 885 | std::size_t select_pattern_anchor(const detail::EnginePattern &pattern) noexcept | |
| 292 | { | ||
| 293 | 885 | const std::size_t pattern_size = pattern.size(); | |
| 294 |
2/2✓ Branch 4 → 5 taken 865 times.
✓ Branch 4 → 6 taken 20 times.
|
884 | const std::size_t segment0_end = pattern.jumps.empty() ? pattern_size : pattern.jumps.front().position; |
| 295 | 885 | std::size_t best = pattern_size; | |
| 296 | 885 | std::uint8_t best_score = UINT8_MAX; | |
| 297 |
2/2✓ Branch 21 → 9 taken 1270 times.
✓ Branch 21 → 22 taken 46 times.
|
1316 | for (std::size_t i = 0; i < segment0_end; ++i) |
| 298 | { | ||
| 299 | // Only a fully-known byte (mask 0xFF) can anchor the memchr / SIMD prefilter, which searches for one | ||
| 300 | // exact byte value. A wildcard (mask 0x00) or a partially-masked nibble byte (0xF0 / 0x0F) carries no | ||
| 301 | // single byte value to scan for, so it is never an anchor candidate. | ||
| 302 |
2/2✓ Branch 10 → 11 taken 144 times.
✓ Branch 10 → 12 taken 1125 times.
|
1270 | if (pattern.mask[i] != std::byte{0xFF}) |
| 303 | { | ||
| 304 | 144 | continue; | |
| 305 | } | ||
| 306 | const std::uint8_t score = | ||
| 307 | 2250 | detail::byte_frequency_class(std::to_integer<std::uint8_t>(pattern.bytes[i])); | |
| 308 |
4/4✓ Branch 16 → 17 taken 262 times.
✓ Branch 16 → 18 taken 864 times.
✓ Branch 17 → 18 taken 104 times.
✓ Branch 17 → 20 taken 158 times.
|
1126 | if (best == pattern_size || score < best_score) |
| 309 | { | ||
| 310 | 968 | best = i; | |
| 311 | 968 | best_score = score; | |
| 312 |
2/2✓ Branch 18 → 19 taken 839 times.
✓ Branch 18 → 20 taken 129 times.
|
968 | if (score == 0) |
| 313 | { | ||
| 314 | 839 | break; | |
| 315 | } | ||
| 316 | } | ||
| 317 | } | ||
| 318 | 885 | return best; | |
| 319 | } | ||
| 320 | } // anonymous namespace | ||
| 321 | |||
| 322 | 875 | void detail::EnginePattern::compile_anchor() noexcept | |
| 323 | { | ||
| 324 | 875 | anchor = select_pattern_anchor(*this); | |
| 325 | 876 | } | |
| 326 | |||
| 327 | 16 | bool detail::pattern_has_literal_byte(const detail::EnginePattern &pattern) noexcept | |
| 328 | { | ||
| 329 |
2/2✓ Branch 17 → 4 taken 28 times.
✓ Branch 17 → 18 taken 9 times.
|
53 | for (const std::byte mask_byte : pattern.mask) |
| 330 | { | ||
| 331 |
2/2✓ Branch 6 → 7 taken 7 times.
✓ Branch 6 → 8 taken 21 times.
|
28 | if (mask_byte != std::byte{0x00}) |
| 332 | 7 | return true; | |
| 333 | } | ||
| 334 | 9 | return false; | |
| 335 | } | ||
| 336 | |||
| 337 | namespace | ||
| 338 | { | ||
| 339 | // Heap-backed storage sink for the runtime AOB parse. It drives the one shared grammar | ||
| 340 | // (detail::parse_pattern_into) so the runtime engine and the compile-time scan::Pattern can never diverge on | ||
| 341 | // the DSL, but, unlike the fixed-array compile-time sink, it imposes no byte cap: the growable EnginePattern | ||
| 342 | // has none, so a long runtime pattern (for example the byte pattern find_string_xref builds from a long search | ||
| 343 | // string) compiles here even though the same length would overflow the literal Pattern's MAX_PATTERN_BYTES | ||
| 344 | // inline storage. The jump count is still capped at MAX_PATTERN_JUMPS because the segmented matcher indexes a | ||
| 345 | // fixed-size segment-start array bounded by it. | ||
| 346 | struct EnginePatternSink | ||
| 347 | { | ||
| 348 | detail::EnginePattern pattern; | ||
| 349 | |||
| 350 | 1068 | [[nodiscard]] std::size_t length() const noexcept { return pattern.bytes.size(); } | |
| 351 | 838 | [[nodiscard]] std::size_t jump_count() const noexcept { return pattern.jumps.size(); } | |
| 352 | |||
| 353 | 16103 | [[nodiscard]] bool add_byte(std::byte value, std::byte mask) | |
| 354 | { | ||
| 355 | 16103 | pattern.bytes.push_back(value); | |
| 356 | 16103 | pattern.mask.push_back(mask); | |
| 357 | 16103 | return true; | |
| 358 | } | ||
| 359 | |||
| 360 | 47 | [[nodiscard]] bool add_jump(std::size_t position, std::size_t min_skip, std::size_t max_skip) | |
| 361 | { | ||
| 362 |
1/2✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 47 times.
|
47 | if (pattern.jumps.size() >= detail::MAX_PATTERN_JUMPS) |
| 363 | { | ||
| 364 | ✗ | return false; | |
| 365 | } | ||
| 366 |
1/2✓ Branch 5 → 6 taken 47 times.
✗ Branch 5 → 8 not taken.
|
47 | pattern.jumps.push_back(detail::PatternJump{position, min_skip, max_skip}); |
| 367 | 47 | return true; | |
| 368 | } | ||
| 369 | |||
| 370 | 14 | void set_offset(std::size_t position) noexcept { pattern.offset = static_cast<std::ptrdiff_t>(position); } | |
| 371 | }; | ||
| 372 | } // namespace | ||
| 373 | |||
| 374 | 857 | std::optional<detail::EnginePattern> detail::parse_aob(std::string_view aob_str) | |
| 375 | { | ||
| 376 | // Parse through the shared grammar into a heap-backed sink so the runtime engine and scan::Pattern accept the | ||
| 377 | // same DSL, while long runtime patterns keep using growable storage instead of the literal type's fixed cap. | ||
| 378 | // The heap-backed sink grows the pattern vectors as it parses, so an adversarial or very long AOB (a string of | ||
| 379 | // arbitrary length routed here by find_string_xref) can exhaust memory. Catch that here and fail closed to | ||
| 380 | // nullopt rather than letting bad_alloc escape. The parse_aob callers already treat nullopt as an unusable | ||
| 381 | // pattern, so this degrades to a clean scan miss instead of terminating the host. | ||
| 382 | try | ||
| 383 | { | ||
| 384 | 857 | EnginePatternSink sink; | |
| 385 |
4/4✓ Branch 2 → 3 taken 855 times.
✓ Branch 2 → 12 taken 1 time.
✓ Branch 3 → 4 taken 19 times.
✓ Branch 3 → 5 taken 836 times.
|
857 | if (detail::parse_pattern_into(aob_str, sink) != detail::PatternStatus::Ok) |
| 386 | { | ||
| 387 | 19 | return std::nullopt; | |
| 388 | } | ||
| 389 | // The anchor is storage-specific, so it is computed here rather than in the shared grammar: select it over | ||
| 390 | // segment 0 with the engine's size() "no fully-known byte" sentinel. | ||
| 391 | 836 | sink.pattern.compile_anchor(); | |
| 392 | 837 | return std::move(sink.pattern); | |
| 393 | 857 | } | |
| 394 |
1/2✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 1 time.
|
1 | catch (const std::bad_alloc &) |
| 395 | { | ||
| 396 | 1 | return std::nullopt; | |
| 397 | 1 | } | |
| 398 | } | ||
| 399 | |||
| 400 | 543 | detail::EnginePattern detail::engine_pattern_from(const scan::Pattern &pattern, std::size_t anchor_index) | |
| 401 | { | ||
| 402 | 543 | const std::span<const std::byte> bytes = pattern.bytes(); | |
| 403 | 543 | const std::span<const std::byte> mask = pattern.mask(); | |
| 404 | 542 | const detail::PatternBuffer &data = detail::pattern_buffer(pattern); | |
| 405 | 542 | const std::span<const detail::PatternJump> jumps(data.jumps.data(), data.jump_count); | |
| 406 | 543 | EnginePattern compiled; | |
| 407 |
1/2✓ Branch 9 → 10 taken 543 times.
✗ Branch 9 → 19 not taken.
|
543 | compiled.bytes.assign(bytes.begin(), bytes.end()); |
| 408 |
1/2✓ Branch 12 → 13 taken 543 times.
✗ Branch 12 → 19 not taken.
|
543 | compiled.mask.assign(mask.begin(), mask.end()); |
| 409 |
1/2✓ Branch 15 → 16 taken 543 times.
✗ Branch 15 → 19 not taken.
|
543 | compiled.jumps.assign(jumps.begin(), jumps.end()); |
| 410 | 543 | compiled.offset = static_cast<std::ptrdiff_t>(pattern.offset()); | |
| 411 | 543 | compiled.anchor = anchor_index; | |
| 412 | 543 | return compiled; | |
| 413 | ✗ | } | |
| 414 | |||
| 415 | namespace | ||
| 416 | { | ||
| 417 | // Self-provided memchr over [haystack, haystack + n) for the anchor byte. libc memchr works in release. ASan's | ||
| 418 | // runtime interceptor checks the whole range against shadow and reports a false overflow on this process's own | ||
| 419 | // committed memory. The interceptor bypasses no_sanitize_address on the caller, so the function itself must do | ||
| 420 | // the byte comparisons. The needle search uses the same tiers as the verify path: SSE2 baseline and AVX2 behind | ||
| 421 | // cpu_has_avx2(). It keeps libc memchr's "lowest address wins" contract and never calls into libc. Unaligned | ||
| 422 | // loads prevent a type-punned qword load that clang-cl TBAA can miscompile. | ||
| 423 | |||
| 424 | /// Count-trailing-zeros over a known-nonzero movemask result; yields the first matching byte's lane index. | ||
| 425 | 9560715 | inline unsigned dmk_movemask_first_index(unsigned int mask) noexcept | |
| 426 | { | ||
| 427 | #if defined(_MSC_VER) && !defined(__clang__) | ||
| 428 | unsigned long index = 0; | ||
| 429 | _BitScanForward(&index, mask); | ||
| 430 | return static_cast<unsigned>(index); | ||
| 431 | #else | ||
| 432 | 9560715 | return static_cast<unsigned>(__builtin_ctz(mask)); | |
| 433 | #endif | ||
| 434 | } | ||
| 435 | |||
| 436 | // SSE2 needle search over [p, p + n): a 16-byte body plus a scalar tail. No runtime gate is needed, because | ||
| 437 | // SSE2 is part of the x86-64 baseline. | ||
| 438 | DMK_NO_SANITIZE_ADDRESS | ||
| 439 | 541 | const unsigned char *dmk_memchr_sse2(const unsigned char *p, unsigned char needle, std::size_t n) noexcept | |
| 440 | { | ||
| 441 | 541 | const __m128i needle_vec = _mm_set1_epi8(static_cast<char>(needle)); | |
| 442 |
2/2✓ Branch 17 → 7 taken 237 times.
✓ Branch 17 → 18 taken 430 times.
|
667 | for (; n >= 16; p += 16, n -= 16) |
| 443 | { | ||
| 444 | 237 | const __m128i chunk = _mm_loadu_si128(reinterpret_cast<const __m128i *>(p)); | |
| 445 | const unsigned int mask = | ||
| 446 | 237 | static_cast<unsigned int>(_mm_movemask_epi8(_mm_cmpeq_epi8(chunk, needle_vec))); | |
| 447 |
2/2✓ Branch 13 → 14 taken 111 times.
✓ Branch 13 → 16 taken 126 times.
|
237 | if (mask != 0) |
| 448 | { | ||
| 449 | 111 | return p + dmk_movemask_first_index(mask); | |
| 450 | } | ||
| 451 | } | ||
| 452 |
2/2✓ Branch 22 → 19 taken 2031 times.
✓ Branch 22 → 23 taken 210 times.
|
2241 | for (; n > 0; ++p, --n) |
| 453 | { | ||
| 454 |
2/2✓ Branch 19 → 20 taken 220 times.
✓ Branch 19 → 21 taken 1811 times.
|
2031 | if (*p == needle) |
| 455 | { | ||
| 456 | 220 | return p; | |
| 457 | } | ||
| 458 | } | ||
| 459 | 210 | return nullptr; | |
| 460 | } | ||
| 461 | |||
| 462 | // AVX2 needle search over [p, p + n): a 32-byte body plus a scalar tail. Compiled with AVX2 codegen via the | ||
| 463 | // target attribute on GCC/Clang so the rest of the TU stays SSE2-only, and only entered after cpu_has_avx2() | ||
| 464 | // has confirmed both the CPU and the OS support the instructions. The tail is scalar rather than an SSE2 call | ||
| 465 | // so the body emits no legacy-SSE encoding and the compiler has no VEX/legacy transition to reconcile on the | ||
| 466 | // way out. | ||
| 467 | DMK_AVX2_TARGET | ||
| 468 | DMK_NO_SANITIZE_ADDRESS | ||
| 469 | 9586307 | const unsigned char *dmk_memchr_avx2(const unsigned char *p, unsigned char needle, std::size_t n) noexcept | |
| 470 | { | ||
| 471 | 9586307 | const __m256i needle_vec = _mm256_set1_epi8(static_cast<char>(needle)); | |
| 472 |
2/2✓ Branch 17 → 7 taken 207470639 times.
✓ Branch 17 → 18 taken 25703 times.
|
207496342 | for (; n >= 32; p += 32, n -= 32) |
| 473 | { | ||
| 474 | 207470639 | const __m256i chunk = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(p)); | |
| 475 | const unsigned int mask = | ||
| 476 | 207470639 | static_cast<unsigned int>(_mm256_movemask_epi8(_mm256_cmpeq_epi8(chunk, needle_vec))); | |
| 477 |
2/2✓ Branch 13 → 14 taken 9560604 times.
✓ Branch 13 → 16 taken 197910035 times.
|
207470639 | if (mask != 0) |
| 478 | { | ||
| 479 | 9560604 | return p + dmk_movemask_first_index(mask); | |
| 480 | } | ||
| 481 | } | ||
| 482 |
2/2✓ Branch 22 → 19 taken 269728 times.
✓ Branch 22 → 23 taken 25675 times.
|
295403 | for (; n > 0; ++p, --n) |
| 483 | { | ||
| 484 |
2/2✓ Branch 19 → 20 taken 28 times.
✓ Branch 19 → 21 taken 269700 times.
|
269728 | if (*p == needle) |
| 485 | { | ||
| 486 | 28 | return p; | |
| 487 | } | ||
| 488 | } | ||
| 489 | 25675 | return nullptr; | |
| 490 | } | ||
| 491 | |||
| 492 | // use_avx2 is hoisted by find_pattern_raw so the per-anchor-hit sweep never re-reads the cpu_has_avx2() static. | ||
| 493 | DMK_NO_SANITIZE_ADDRESS | ||
| 494 | 9586848 | const void *dmk_memchr(const void *haystack, unsigned char needle, std::size_t n, bool use_avx2) noexcept | |
| 495 | { | ||
| 496 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 9586848 times.
|
9586848 | if (n == 0) |
| 497 | { | ||
| 498 | ✗ | return nullptr; | |
| 499 | } | ||
| 500 | 9586848 | const auto *p = static_cast<const unsigned char *>(haystack); | |
| 501 | |||
| 502 | // The 32-byte body pays for itself only when a full vector remains. | ||
| 503 | // Shorter spans use the SSE2 body and avoid a target switch near the end of the sweep. | ||
| 504 |
4/4✓ Branch 4 → 5 taken 9586847 times.
✓ Branch 4 → 7 taken 1 time.
✓ Branch 5 → 6 taken 9586305 times.
✓ Branch 5 → 7 taken 542 times.
|
9586848 | if (use_avx2 && n >= 32) |
| 505 | { | ||
| 506 | 9586305 | return dmk_memchr_avx2(p, needle, n); | |
| 507 | } | ||
| 508 | 543 | return dmk_memchr_sse2(p, needle, n); | |
| 509 | } | ||
| 510 | |||
| 511 | // memchr over [begin, end] for the anchor byte. Routes through the self-provided dmk_memchr above so the ASan | ||
| 512 | // runtime cannot intercept the call. dmk_memchr returns a pointer into the range or nullptr; the wrapper | ||
| 513 | // re-establishes the [begin, end] inclusive contract the scanner expects. use_avx2 is the caller's hoisted | ||
| 514 | // cpu_has_avx2() result, threaded through so the prefilter does not re-read the static on every anchor hit. | ||
| 515 | DMK_NO_SANITIZE_ADDRESS | ||
| 516 | const std::byte * | ||
| 517 | 9586848 | scan_for_byte(const std::byte *begin, const std::byte *end, unsigned char target, bool use_avx2) noexcept | |
| 518 | { | ||
| 519 | 9586848 | const std::size_t n = static_cast<std::size_t>(end - begin + 1); | |
| 520 | 9586848 | return static_cast<const std::byte *>(dmk_memchr(begin, target, n, use_avx2)); | |
| 521 | } | ||
| 522 | } // anonymous namespace | ||
| 523 | |||
| 524 | // Flat single-segment matcher: the memchr-anchored SIMD body, returning the match START (no offset applied). | ||
| 525 | // Every jump-free pattern dispatches here, so the overwhelmingly common case runs the direct fixed-width fast path. | ||
| 526 | DMK_NO_SANITIZE_ADDRESS | ||
| 527 | 25201 | static const std::byte *find_pattern_flat_start( | |
| 528 | const std::byte *start_address, | ||
| 529 | std::size_t region_size, | ||
| 530 | const detail::EnginePattern &pattern | ||
| 531 | ) noexcept | ||
| 532 | { | ||
| 533 | 25201 | const std::size_t pattern_size = pattern.size(); | |
| 534 | |||
| 535 |
3/6✓ Branch 3 → 4 taken 25200 times.
✗ Branch 3 → 6 not taken.
✓ Branch 4 → 5 taken 25200 times.
✗ Branch 4 → 6 not taken.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 25200 times.
|
25200 | if (pattern_size == 0 || !start_address || region_size < pattern_size) |
| 536 | { | ||
| 537 | ✗ | return nullptr; | |
| 538 | } | ||
| 539 | |||
| 540 | // Anchor selection: parse_aob() pre-populates pattern.anchor, so the common path is a single load. Manually | ||
| 541 | // constructed patterns fall back to inline selection without mutating the input (preserves the const-by-design | ||
| 542 | // contract). | ||
| 543 | const std::size_t best_anchor = | ||
| 544 |
2/2✓ Branch 7 → 8 taken 25192 times.
✓ Branch 7 → 9 taken 8 times.
|
25200 | (pattern.anchor <= pattern_size) ? pattern.anchor : select_pattern_anchor(pattern); |
| 545 | |||
| 546 | // No fully-known byte to anchor on. Two sub-cases: | ||
| 547 | // - The pattern is entirely wildcards (no mask bit set anywhere): the search degenerates to | ||
| 548 | // "always match at region start", the defined result for an all-wildcard pattern. | ||
| 549 | // - The pattern carries only partially-masked (nibble) bytes: there is no exact byte for the | ||
| 550 | // memchr / SIMD prefilter, so fall back to a masked compare at every candidate position. This | ||
| 551 | // path is rare (a real signature almost always carries at least one full literal byte), so a | ||
| 552 | // scalar verify is acceptable; correctness, not throughput, is the concern here. | ||
| 553 |
2/2✓ Branch 10 → 11 taken 16 times.
✓ Branch 10 → 33 taken 25185 times.
|
25201 | if (best_anchor == pattern_size) |
| 554 | { | ||
| 555 |
2/2✓ Branch 12 → 13 taken 9 times.
✓ Branch 12 → 14 taken 7 times.
|
16 | if (!pattern_has_literal_byte(pattern)) |
| 556 | { | ||
| 557 | 9 | return start_address; | |
| 558 | } | ||
| 559 | 7 | const std::byte *const last_start = start_address + (region_size - pattern_size); | |
| 560 |
2/2✓ Branch 31 → 15 taken 1836 times.
✓ Branch 31 → 32 taken 3 times.
|
1839 | for (const std::byte *pos = start_address; pos <= last_start; ++pos) |
| 561 | { | ||
| 562 | 1836 | bool match_found = true; | |
| 563 |
2/2✓ Branch 27 → 16 taken 1839 times.
✓ Branch 27 → 28 taken 4 times.
|
1843 | for (std::size_t j = 0; j < pattern_size; ++j) |
| 564 | { | ||
| 565 | 1839 | const auto mem = std::to_integer<unsigned>(pos[j]); | |
| 566 | 1839 | const auto pat = std::to_integer<unsigned>(pattern.bytes[j]); | |
| 567 | 1839 | const auto msk = std::to_integer<unsigned>(pattern.mask[j]); | |
| 568 |
2/2✓ Branch 24 → 25 taken 1832 times.
✓ Branch 24 → 26 taken 7 times.
|
1839 | if (((mem ^ pat) & msk) != 0) |
| 569 | { | ||
| 570 | 1832 | match_found = false; | |
| 571 | 1832 | break; | |
| 572 | } | ||
| 573 | } | ||
| 574 |
2/2✓ Branch 28 → 29 taken 4 times.
✓ Branch 28 → 30 taken 1832 times.
|
1836 | if (match_found) |
| 575 | { | ||
| 576 | 4 | return pos; | |
| 577 | } | ||
| 578 | } | ||
| 579 | 3 | return nullptr; | |
| 580 | } | ||
| 581 | |||
| 582 | 25185 | const std::byte target_byte = pattern.bytes[best_anchor]; | |
| 583 | 25184 | const unsigned char target_val = static_cast<unsigned char>(target_byte); | |
| 584 | |||
| 585 | 25184 | const std::byte *search_start = start_address + best_anchor; | |
| 586 | 25184 | const std::byte *const search_end = start_address + (region_size - pattern_size) + best_anchor; | |
| 587 | |||
| 588 | // Hoist runtime CPU detection. The query itself is a function-local static behind a one-shot init, but | ||
| 589 | // reading it on every memchr hit and every verify adds an indirect load per false candidate. Caching it | ||
| 590 | // once here lets both the prefilter sweep and the per-candidate verify branch use a register-resident bool. | ||
| 591 | 25184 | const bool use_avx2 = cpu_has_avx2(); | |
| 592 | #ifdef DMK_HAS_AVX512 | ||
| 593 | const bool use_avx512 = cpu_has_avx512(); | ||
| 594 | #endif | ||
| 595 | |||
| 596 |
2/2✓ Branch 89 → 36 taken 8429352 times.
✓ Branch 89 → 90 taken 4 times.
|
8429356 | while (search_start <= search_end) |
| 597 | { | ||
| 598 | 8429352 | const std::byte *current_scan_ptr = scan_for_byte(search_start, search_end, target_val, use_avx2); | |
| 599 | |||
| 600 |
2/2✓ Branch 37 → 38 taken 20053 times.
✓ Branch 37 → 39 taken 8405608 times.
|
8425661 | if (!current_scan_ptr) |
| 601 | { | ||
| 602 | 20053 | break; | |
| 603 | } | ||
| 604 | 8405608 | const std::byte *pattern_start = current_scan_ptr - best_anchor; | |
| 605 | |||
| 606 | // Verify the full pattern at this position. SIMD tiers run widest-first: AVX-512 (64B) -> AVX2 (32B) -> | ||
| 607 | // SSE2 (16B) -> scalar (1B). Each tier resumes from the offset the previous one reached (start_offset | ||
| 608 | // j), so the widest available tiers cover the bulk and the scalar loop only ever finishes a sub-16-byte | ||
| 609 | // tail. | ||
| 610 | 8405608 | bool match_found = true; | |
| 611 | 8405608 | std::size_t j = 0; | |
| 612 | |||
| 613 | #ifdef DMK_HAS_AVX512 | ||
| 614 | if (use_avx512) | ||
| 615 | { | ||
| 616 | const auto next_j = verify_pattern_avx512(pattern_start, pattern, j); | ||
| 617 | if (next_j.has_value()) | ||
| 618 | { | ||
| 619 | j = *next_j; | ||
| 620 | } | ||
| 621 | else | ||
| 622 | { | ||
| 623 | match_found = false; | ||
| 624 | } | ||
| 625 | } | ||
| 626 | #endif // DMK_HAS_AVX512 | ||
| 627 | |||
| 628 |
2/4✓ Branch 39 → 40 taken 8405608 times.
✗ Branch 39 → 48 not taken.
✓ Branch 40 → 41 taken 8405608 times.
✗ Branch 40 → 48 not taken.
|
8405608 | if (match_found && use_avx2) |
| 629 | { | ||
| 630 | 8405608 | const auto next_j = verify_pattern_avx2(pattern_start, pattern, j); | |
| 631 |
2/2✓ Branch 43 → 44 taken 7234550 times.
✓ Branch 43 → 46 taken 1171059 times.
|
8405609 | if (next_j.has_value()) |
| 632 | { | ||
| 633 | 7234550 | j = *next_j; | |
| 634 | } | ||
| 635 | else | ||
| 636 | { | ||
| 637 | 1171059 | match_found = false; | |
| 638 | } | ||
| 639 | } | ||
| 640 | |||
| 641 |
4/4✓ Branch 70 → 71 taken 7235500 times.
✓ Branch 70 → 72 taken 1171060 times.
✓ Branch 71 → 49 taken 7061041 times.
✓ Branch 71 → 72 taken 174459 times.
|
8406560 | for (; match_found && j + 16 <= pattern_size; j += 16) |
| 642 | { | ||
| 643 | 7061041 | const __m128i mem = _mm_loadu_si128(reinterpret_cast<const __m128i *>(pattern_start + j)); | |
| 644 | 7061041 | const __m128i pat = _mm_loadu_si128(reinterpret_cast<const __m128i *>(pattern.bytes.data() + j)); | |
| 645 | 14122081 | const __m128i msk = _mm_loadu_si128(reinterpret_cast<const __m128i *>(pattern.mask.data() + j)); | |
| 646 | |||
| 647 | 7061041 | const __m128i xored = _mm_xor_si128(mem, pat); | |
| 648 | 7061041 | const __m128i masked = _mm_and_si128(xored, msk); | |
| 649 | 14122082 | const __m128i cmp = _mm_cmpeq_epi8(masked, _mm_setzero_si128()); | |
| 650 | |||
| 651 |
2/2✓ Branch 67 → 68 taken 7060090 times.
✓ Branch 67 → 69 taken 951 times.
|
7061041 | if (_mm_movemask_epi8(cmp) != 0xFFFF) |
| 652 | { | ||
| 653 | 7060090 | match_found = false; | |
| 654 | 7060090 | break; | |
| 655 | } | ||
| 656 | } | ||
| 657 | |||
| 658 |
4/4✓ Branch 84 → 85 taken 353292 times.
✓ Branch 84 → 86 taken 8404173 times.
✓ Branch 85 → 73 taken 351855 times.
✓ Branch 85 → 86 taken 1437 times.
|
8757465 | for (; match_found && j < pattern_size; ++j) |
| 659 | { | ||
| 660 | // Masked compare so a partially-masked nibble byte checks only its known nibble: (mem ^ pat) & mask | ||
| 661 | // is zero exactly when every bit the mask selects agrees. A wildcard (mask 0x00) is trivially | ||
| 662 | // satisfied, a full literal (0xFF) compares the whole byte, and a nibble (0xF0 / 0x0F) compares one | ||
| 663 | // nibble. | ||
| 664 | 351855 | const auto mem = std::to_integer<unsigned>(pattern_start[j]); | |
| 665 | 351855 | const auto pat = std::to_integer<unsigned>(pattern.bytes[j]); | |
| 666 | 351857 | const auto msk = std::to_integer<unsigned>(pattern.mask[j]); | |
| 667 |
2/2✓ Branch 81 → 82 taken 173023 times.
✓ Branch 81 → 83 taken 178833 times.
|
351856 | if (((mem ^ pat) & msk) != 0) |
| 668 | { | ||
| 669 | 173023 | match_found = false; | |
| 670 | } | ||
| 671 | } | ||
| 672 | |||
| 673 |
2/2✓ Branch 86 → 87 taken 1437 times.
✓ Branch 86 → 88 taken 8404173 times.
|
8405610 | if (match_found) |
| 674 | { | ||
| 675 | 1437 | return pattern_start; | |
| 676 | } | ||
| 677 | |||
| 678 | // No match, continue searching from next position. | ||
| 679 | 8404173 | search_start = current_scan_ptr + 1; | |
| 680 | } | ||
| 681 | |||
| 682 | 20057 | return nullptr; | |
| 683 | } | ||
| 684 | |||
| 685 | // Masked-compares one fixed segment run [body_begin, body_end) of the pattern against memory at addr. The caller | ||
| 686 | // guarantees [addr, addr + (body_end - body_begin)) is inside the scanned region, so this does no bounds check. The | ||
| 687 | // per-byte test is the same (mem ^ pat) & mask == 0 the flat verify uses, so wildcard and nibble bytes behave | ||
| 688 | // identically here. | ||
| 689 | DMK_NO_SANITIZE_ADDRESS | ||
| 690 | 1943154 | static bool segment_run_matches( | |
| 691 | const std::byte *addr, | ||
| 692 | const detail::EnginePattern &pattern, | ||
| 693 | std::size_t body_begin, | ||
| 694 | std::size_t body_end | ||
| 695 | ) noexcept | ||
| 696 | { | ||
| 697 |
2/2✓ Branch 14 → 3 taken 2049029 times.
✓ Branch 14 → 15 taken 3560 times.
|
2052589 | for (std::size_t i = body_begin; i < body_end; ++i) |
| 698 | { | ||
| 699 | 2049029 | const auto mem = std::to_integer<unsigned>(addr[i - body_begin]); | |
| 700 | 2049029 | const auto pat = std::to_integer<unsigned>(pattern.bytes[i]); | |
| 701 | 2049029 | const auto msk = std::to_integer<unsigned>(pattern.mask[i]); | |
| 702 |
2/2✓ Branch 11 → 12 taken 1939594 times.
✓ Branch 11 → 13 taken 109435 times.
|
2049029 | if (((mem ^ pat) & msk) != 0) |
| 703 | { | ||
| 704 | 1939594 | return false; | |
| 705 | } | ||
| 706 | } | ||
| 707 | 3560 | return true; | |
| 708 | } | ||
| 709 | |||
| 710 | // Backtracking segment extension for a bounded-jump pattern. Tries to place segment `segment_index` (and every | ||
| 711 | // segment after it) starting at `addr`, staying within [.., region_end). On success it records each segment's | ||
| 712 | // absolute start in segment_starts and returns true. Gap widths are tried in ascending order, so the first success | ||
| 713 | // is the leftmost feasible placement; backtracking is required because a nearer gap position can strand a later | ||
| 714 | // segment a farther position would satisfy. Recursion DEPTH is bounded by the segment count (<= jumps + 1); total | ||
| 715 | // WORK is bounded by the per-position @p steps counter and the shared region-wide @p budget. A cap fails the | ||
| 716 | // current tree closed before it performs an over-budget node visit. Each segment run fails fast on its first | ||
| 717 | // literal byte, so a real signature prunes to near-linear and never approaches either cap. | ||
| 718 | DMK_NO_SANITIZE_ADDRESS | ||
| 719 | 1943182 | static bool extend_segments( | |
| 720 | const detail::EnginePattern &pattern, | ||
| 721 | const std::byte *addr, | ||
| 722 | const std::byte *region_end, | ||
| 723 | std::size_t segment_index, | ||
| 724 | const std::byte **segment_starts, | ||
| 725 | std::size_t &steps, | ||
| 726 | detail::SegmentedScanBudget &budget, | ||
| 727 | bool &position_exhausted | ||
| 728 | ) noexcept | ||
| 729 | { | ||
| 730 | // Refuse to enter a node that would exceed either ceiling. A per-position truncation still allows the outer | ||
| 731 | // sweep to try a later start; a region truncation stops all later starts and suffix scans for this region. | ||
| 732 |
2/2✓ Branch 2 → 3 taken 9 times.
✓ Branch 2 → 4 taken 1943173 times.
|
1943182 | if (steps >= detail::SEGMENT_MATCH_STEP_BUDGET) |
| 733 | { | ||
| 734 | 9 | budget.exhausted = true; | |
| 735 | 9 | position_exhausted = true; | |
| 736 | 9 | return false; | |
| 737 | } | ||
| 738 |
2/2✓ Branch 4 → 5 taken 1 time.
✓ Branch 4 → 6 taken 1943172 times.
|
1943173 | if (budget.node_visits >= detail::SEGMENT_MATCH_REGION_STEP_BUDGET) |
| 739 | { | ||
| 740 | 1 | budget.exhausted = true; | |
| 741 | 1 | budget.region_exhausted = true; | |
| 742 | 1 | return false; | |
| 743 | } | ||
| 744 | 1943172 | ++steps; | |
| 745 | 1943172 | ++budget.node_visits; | |
| 746 | |||
| 747 | 1943172 | const std::size_t jump_count = pattern.jumps.size(); | |
| 748 |
2/2✓ Branch 7 → 8 taken 787754 times.
✓ Branch 7 → 10 taken 1155418 times.
|
1943172 | const std::size_t segment_begin = (segment_index == 0) ? 0 : pattern.jumps[segment_index - 1].position; |
| 749 | const std::size_t segment_end = | ||
| 750 |
2/2✓ Branch 11 → 12 taken 1158826 times.
✓ Branch 11 → 14 taken 784346 times.
|
1943172 | (segment_index < jump_count) ? pattern.jumps[segment_index].position : pattern.size(); |
| 751 | 1943172 | const std::size_t segment_length = segment_end - segment_begin; | |
| 752 | |||
| 753 | // The segment run must fit in the bytes that remain before region_end. | ||
| 754 |
2/2✓ Branch 15 → 16 taken 18 times.
✓ Branch 15 → 17 taken 1943154 times.
|
1943172 | if (segment_length > static_cast<std::size_t>(region_end - addr)) |
| 755 | { | ||
| 756 | 18 | return false; | |
| 757 | } | ||
| 758 |
2/2✓ Branch 18 → 19 taken 1939594 times.
✓ Branch 18 → 20 taken 3560 times.
|
1943154 | if (!segment_run_matches(addr, pattern, segment_begin, segment_end)) |
| 759 | { | ||
| 760 | 1939594 | return false; | |
| 761 | } | ||
| 762 | 3560 | segment_starts[segment_index] = addr; | |
| 763 |
2/2✓ Branch 20 → 21 taken 35 times.
✓ Branch 20 → 22 taken 3525 times.
|
3560 | if (segment_index == jump_count) |
| 764 | { | ||
| 765 | // The last segment matched, so the whole pattern is placed. | ||
| 766 | 35 | return true; | |
| 767 | } | ||
| 768 | |||
| 769 | 3525 | const std::byte *const after = addr + segment_length; | |
| 770 | 3525 | const detail::PatternJump &gap = pattern.jumps[segment_index]; | |
| 771 | 3525 | const std::size_t available = static_cast<std::size_t>(region_end - after); | |
| 772 |
2/2✓ Branch 33 → 24 taken 787775 times.
✓ Branch 33 → 34 taken 3365 times.
|
791140 | for (std::size_t skip = gap.min_skip; skip <= gap.max_skip; ++skip) |
| 773 | { | ||
| 774 | // Once the gap alone overruns the region no larger skip can fit either. Checking skip against the available | ||
| 775 | // bytes before forming the pointer keeps the arithmetic in-bounds (never past region_end). | ||
| 776 |
2/2✓ Branch 24 → 25 taken 12 times.
✓ Branch 24 → 26 taken 787763 times.
|
787775 | if (skip > available) |
| 777 | { | ||
| 778 | 12 | break; | |
| 779 | } | ||
| 780 |
2/2✓ Branch 27 → 28 taken 76 times.
✓ Branch 27 → 29 taken 787687 times.
|
787763 | if (extend_segments( |
| 781 | pattern, | ||
| 782 | after + skip, | ||
| 783 | region_end, | ||
| 784 | segment_index + 1, | ||
| 785 | segment_starts, | ||
| 786 | steps, | ||
| 787 | budget, | ||
| 788 | position_exhausted | ||
| 789 | )) | ||
| 790 | { | ||
| 791 | 76 | return true; | |
| 792 | } | ||
| 793 | // Propagate only an actual refused visit. Merely reaching a ceiling on the final feasible branch is still | ||
| 794 | // exhaustive, so the caller may return a confident miss instead of falsely marking it incomplete. | ||
| 795 |
3/4✓ Branch 29 → 30 taken 787615 times.
✓ Branch 29 → 31 taken 72 times.
✗ Branch 30 → 31 not taken.
✓ Branch 30 → 32 taken 787615 times.
|
787687 | if (position_exhausted || budget.region_exhausted) |
| 796 | { | ||
| 797 | 72 | return false; | |
| 798 | } | ||
| 799 | } | ||
| 800 | 3377 | return false; | |
| 801 | } | ||
| 802 | |||
| 803 | // Resolves the offset-applied result point and the one-past-end pointer for a placed bounded-jump match. The `|` | ||
| 804 | // marker records a fixed-byte index; the run-time point is the address of that fixed byte, which lives in whichever | ||
| 805 | // segment contains the index (or the end when the marker is trailing). `end` is one past the final segment's last | ||
| 806 | // byte - the match's true span, which varies with the gap widths chosen. | ||
| 807 | static detail::RawMatch | ||
| 808 | 35 | segmented_result(const detail::EnginePattern &pattern, const std::byte *const *segment_starts) noexcept | |
| 809 | { | ||
| 810 | 35 | const std::size_t jump_count = pattern.jumps.size(); | |
| 811 | 35 | const std::size_t last_index = jump_count; // segment count is jump_count + 1 | |
| 812 | 35 | const std::size_t last_begin = pattern.jumps.back().position; | |
| 813 | 35 | const std::byte *const end = segment_starts[last_index] + (pattern.size() - last_begin); | |
| 814 | |||
| 815 | 35 | const std::size_t marker = static_cast<std::size_t>(pattern.offset); | |
| 816 | 35 | const std::byte *point = end; // trailing marker (offset == size()) resolves to the end | |
| 817 |
1/2✓ Branch 6 → 7 taken 35 times.
✗ Branch 6 → 22 not taken.
|
35 | if (marker < pattern.size()) |
| 818 | { | ||
| 819 |
1/2✓ Branch 20 → 8 taken 41 times.
✗ Branch 20 → 21 not taken.
|
41 | for (std::size_t segment_index = 0; segment_index <= jump_count; ++segment_index) |
| 820 | { | ||
| 821 |
2/2✓ Branch 8 → 9 taken 6 times.
✓ Branch 8 → 11 taken 35 times.
|
41 | const std::size_t segment_begin = (segment_index == 0) ? 0 : pattern.jumps[segment_index - 1].position; |
| 822 | const std::size_t segment_end = | ||
| 823 |
2/2✓ Branch 12 → 13 taken 37 times.
✓ Branch 12 → 15 taken 4 times.
|
41 | (segment_index < jump_count) ? pattern.jumps[segment_index].position : pattern.size(); |
| 824 |
3/4✓ Branch 16 → 17 taken 41 times.
✗ Branch 16 → 19 not taken.
✓ Branch 17 → 18 taken 35 times.
✓ Branch 17 → 19 taken 6 times.
|
41 | if (marker >= segment_begin && marker < segment_end) |
| 825 | { | ||
| 826 | 35 | point = segment_starts[segment_index] + (marker - segment_begin); | |
| 827 | 35 | break; | |
| 828 | } | ||
| 829 | } | ||
| 830 | } | ||
| 831 | 35 | return detail::RawMatch{segment_starts[0], end, point}; | |
| 832 | } | ||
| 833 | |||
| 834 | // Segmented backtracking matcher for a bounded-jump pattern. Locates segment 0 with the same memchr anchor sweep | ||
| 835 | // the flat matcher uses (or scans every start position when segment 0 has no literal anchor), then extends across | ||
| 836 | // the gaps. Returns the leftmost match: the smallest segment-0 start that admits a full placement. Sets | ||
| 837 | // RawMatch::budget_exhausted when the per-position or region-wide backtracking budget was spent before the sweep | ||
| 838 | // was exhaustive, so a caller counting occurrences fails closed rather than trusting a truncated verdict. | ||
| 839 | DMK_NO_SANITIZE_ADDRESS | ||
| 840 | 2178 | static detail::RawMatch find_pattern_segmented( | |
| 841 | const std::byte *start_address, | ||
| 842 | std::size_t region_size, | ||
| 843 | const detail::EnginePattern &pattern, | ||
| 844 | detail::SegmentedScanBudget &budget, | ||
| 845 | bool use_avx2 | ||
| 846 | ) noexcept | ||
| 847 | { | ||
| 848 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 2178 times.
|
2178 | if (budget.region_exhausted) |
| 849 | { | ||
| 850 | ✗ | detail::RawMatch result{}; | |
| 851 | ✗ | result.budget_exhausted = true; | |
| 852 | ✗ | return result; | |
| 853 | } | ||
| 854 | 2178 | const std::size_t min_length = pattern.min_match_length(); | |
| 855 |
1/2✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 2178 times.
|
2178 | if (region_size < min_length) |
| 856 | { | ||
| 857 | ✗ | return detail::RawMatch{}; | |
| 858 | } | ||
| 859 | 2178 | const std::byte *const region_end = start_address + region_size; | |
| 860 | // A segment-0 start must leave room for at least a minimum-length match. | ||
| 861 | 2178 | const std::byte *const last_candidate = start_address + (region_size - min_length); | |
| 862 | 2178 | const std::size_t segment0_end = pattern.jumps.front().position; | |
| 863 | |||
| 864 | // Segment count is bounded by MAX_PATTERN_JUMPS + 1, so a fixed local array avoids any allocation on the match | ||
| 865 | // path. Value-initialized so a compiler cannot flag a maybe-uninitialized read through the recursive fill: | ||
| 866 | // segmented_result runs only after extend_segments has written every index, but that write crosses a call | ||
| 867 | // boundary the optimizer may not see through. | ||
| 868 | 2178 | const std::byte *segment_starts[detail::MAX_PATTERN_JUMPS + 1] = {}; | |
| 869 | |||
| 870 | // The shared state accumulates every start position AND every suffix continuation that an Nth-occurrence scan | ||
| 871 | // performs over this physical region. A per-position truncation leaves budget.exhausted latched while this call | ||
| 872 | // still looks for a later match; that later result carries the flag and every pointer/counting surface fails | ||
| 873 | // closed rather than mistaking it for a proven leftmost occurrence. | ||
| 874 | |||
| 875 | 2178 | const std::size_t anchor = pattern.anchor; | |
| 876 |
2/2✓ Branch 8 → 9 taken 2175 times.
✓ Branch 8 → 25 taken 3 times.
|
2178 | if (anchor < segment0_end) |
| 877 | { | ||
| 878 | // Anchored sweep: memchr for the segment-0 anchor byte, then try to extend from each hit. The anchor sits | ||
| 879 | // `anchor` bytes into segment 0, so a hit at H means a candidate segment-0 start at H - anchor. | ||
| 880 | 2175 | const auto target = static_cast<unsigned char>(pattern.bytes[anchor]); | |
| 881 | 2175 | const std::byte *const search_hi = last_candidate + anchor; // inclusive, mirrors the flat matcher | |
| 882 | 2175 | const std::byte *search_start = start_address + anchor; | |
| 883 |
1/2✓ Branch 22 → 11 taken 1157495 times.
✗ Branch 22 → 23 not taken.
|
1157495 | while (search_start <= search_hi) |
| 884 | { | ||
| 885 | 1157495 | const std::byte *const hit = scan_for_byte(search_start, search_hi, target, use_avx2); | |
| 886 |
2/2✓ Branch 12 → 13 taken 2141 times.
✓ Branch 12 → 14 taken 1155354 times.
|
1157495 | if (!hit) |
| 887 | { | ||
| 888 | 2142 | break; | |
| 889 | } | ||
| 890 | 1155354 | const std::byte *const candidate = hit - anchor; | |
| 891 | // The per-position budget is reset at each start so one position's pathological backtracking can never | ||
| 892 | // starve a later, genuine match; the region-wide budget below still bounds their sum. | ||
| 893 | 1155354 | std::size_t steps = 0; | |
| 894 | 1155354 | bool position_exhausted = false; | |
| 895 | 1155354 | const bool matched = extend_segments( | |
| 896 | pattern, | ||
| 897 | candidate, | ||
| 898 | region_end, | ||
| 899 | 0, | ||
| 900 | segment_starts, | ||
| 901 | steps, | ||
| 902 | budget, | ||
| 903 | position_exhausted | ||
| 904 | ); | ||
| 905 |
2/2✓ Branch 15 → 16 taken 33 times.
✓ Branch 15 → 18 taken 1155321 times.
|
1155354 | if (matched) |
| 906 | { | ||
| 907 | // A found match is only provably the leftmost if no earlier start position was truncated, so carry | ||
| 908 | // the exhaustion flag onto it: a uniqueness / occurrence caller then still fails closed. | ||
| 909 | 33 | detail::RawMatch match = segmented_result(pattern, segment_starts); | |
| 910 | 33 | match.budget_exhausted = budget.exhausted; | |
| 911 | 33 | return match; | |
| 912 | } | ||
| 913 |
2/2✓ Branch 18 → 19 taken 1 time.
✓ Branch 18 → 20 taken 1155320 times.
|
1155321 | if (budget.region_exhausted) |
| 914 | { | ||
| 915 | // The region-wide budget is spent; stop sweeping and fail the region's segmented scan closed. | ||
| 916 | 1 | budget.exhausted = true; | |
| 917 | 1 | break; | |
| 918 | } | ||
| 919 | 1155320 | search_start = hit + 1; | |
| 920 | } | ||
| 921 | 2142 | detail::RawMatch result{}; | |
| 922 | 2142 | result.budget_exhausted = budget.exhausted; | |
| 923 | 2142 | return result; | |
| 924 | } | ||
| 925 | |||
| 926 | // No literal byte in segment 0 (all wildcard or nibble-only): fall back to trying every start position. Rare -- | ||
| 927 | // a real signature almost always carries a literal byte in its leading run. This is the path the region-wide | ||
| 928 | // budget most protects: with no anchor to make candidates sparse, every byte is a start position, so an | ||
| 929 | // unbudgeted wide-gap wildcard pattern would visit O(region_size x per-position budget) nodes. | ||
| 930 |
2/2✓ Branch 33 → 26 taken 65 times.
✓ Branch 33 → 34 taken 1 time.
|
66 | for (const std::byte *candidate = start_address; candidate <= last_candidate; ++candidate) |
| 931 | { | ||
| 932 | // Per-candidate work budget (see the anchored sweep above): reset at each start position. | ||
| 933 | 65 | std::size_t steps = 0; | |
| 934 | 65 | bool position_exhausted = false; | |
| 935 | const bool matched = | ||
| 936 | 65 | extend_segments(pattern, candidate, region_end, 0, segment_starts, steps, budget, position_exhausted); | |
| 937 |
2/2✓ Branch 27 → 28 taken 2 times.
✓ Branch 27 → 30 taken 63 times.
|
65 | if (matched) |
| 938 | { | ||
| 939 | 2 | detail::RawMatch match = segmented_result(pattern, segment_starts); | |
| 940 | 2 | match.budget_exhausted = budget.exhausted; | |
| 941 | 2 | return match; | |
| 942 | } | ||
| 943 |
1/2✗ Branch 30 → 31 not taken.
✓ Branch 30 → 32 taken 63 times.
|
63 | if (budget.region_exhausted) |
| 944 | { | ||
| 945 | ✗ | budget.exhausted = true; | |
| 946 | ✗ | break; | |
| 947 | } | ||
| 948 | } | ||
| 949 | 1 | detail::RawMatch result{}; | |
| 950 | 1 | result.budget_exhausted = budget.exhausted; | |
| 951 | 1 | return result; | |
| 952 | } | ||
| 953 | |||
| 954 | 27387 | detail::RawMatch detail::find_pattern_raw( | |
| 955 | const std::byte *start_address, | ||
| 956 | std::size_t region_size, | ||
| 957 | const detail::EnginePattern &pattern, | ||
| 958 | detail::SegmentedScanBudget *segmented_budget | ||
| 959 | ) noexcept | ||
| 960 | { | ||
| 961 | 27387 | const std::size_t pattern_size = pattern.size(); | |
| 962 |
4/6✓ Branch 3 → 4 taken 27387 times.
✗ Branch 3 → 6 not taken.
✓ Branch 4 → 5 taken 27387 times.
✗ Branch 4 → 6 not taken.
✓ Branch 5 → 6 taken 8 times.
✓ Branch 5 → 7 taken 27379 times.
|
27386 | if (pattern_size == 0 || !start_address || region_size < pattern_size) |
| 963 | { | ||
| 964 | 7 | return RawMatch{}; | |
| 965 | } | ||
| 966 | |||
| 967 |
2/2✓ Branch 8 → 9 taken 25201 times.
✓ Branch 8 → 13 taken 2178 times.
|
27379 | if (pattern.jumps.empty()) |
| 968 | { | ||
| 969 | // Plain pattern: the flat fixed-width fast path. end is the fixed span; point applies the constant | ||
| 970 | // offset. | ||
| 971 | 25201 | const std::byte *const start = find_pattern_flat_start(start_address, region_size, pattern); | |
| 972 |
2/2✓ Branch 10 → 11 taken 20060 times.
✓ Branch 10 → 12 taken 1450 times.
|
21510 | if (!start) |
| 973 | { | ||
| 974 | 20060 | return RawMatch{}; | |
| 975 | } | ||
| 976 | 1450 | return RawMatch{start, start + pattern_size, start + pattern.offset}; | |
| 977 | } | ||
| 978 | |||
| 979 | // Bounded-jump pattern: hoist the AVX2 gate once for the segmented sweep's memchr, then run the segmented | ||
| 980 | // matcher, which applies the offset itself because a jump match's marker delta is not a constant. | ||
| 981 | 2178 | const bool use_avx2 = cpu_has_avx2(); | |
| 982 | 2178 | detail::SegmentedScanBudget local_budget{}; | |
| 983 |
2/2✓ Branch 14 → 15 taken 16 times.
✓ Branch 14 → 16 taken 2162 times.
|
2178 | detail::SegmentedScanBudget &budget = segmented_budget != nullptr ? *segmented_budget : local_budget; |
| 984 | 2178 | return find_pattern_segmented(start_address, region_size, pattern, budget, use_avx2); | |
| 985 | } | ||
| 986 | |||
| 987 | const std::byte * | ||
| 988 | 97 | detail::find_pattern(const std::byte *start_address, std::size_t region_size, const detail::EnginePattern &pattern) | |
| 989 | { | ||
| 990 |
6/6✓ Branch 3 → 4 taken 96 times.
✓ Branch 3 → 5 taken 1 time.
✓ Branch 4 → 5 taken 3 times.
✓ Branch 4 → 6 taken 93 times.
✓ Branch 7 → 8 taken 4 times.
✓ Branch 7 → 9 taken 93 times.
|
97 | if (pattern.empty() || !start_address) |
| 991 | { | ||
| 992 | 4 | return nullptr; | |
| 993 | } | ||
| 994 | |||
| 995 | // find_pattern_raw bakes the offset into point (constant for a plain pattern, gap-dependent for a jump one), so | ||
| 996 | // point is the final result address and is nullptr when there is no match. | ||
| 997 | 93 | const RawMatch match = find_pattern_raw(start_address, region_size, pattern); | |
| 998 | // A later match is not a proven first match when an earlier bounded-jump placement was truncated. The raw | ||
| 999 | // pointer surface has no incomplete flag, so it must fail closed instead of returning a possibly-wrong point. | ||
| 1000 |
2/2✓ Branch 10 → 11 taken 2 times.
✓ Branch 10 → 12 taken 91 times.
|
93 | return match.budget_exhausted ? nullptr : match.point; |
| 1001 | } | ||
| 1002 | |||
| 1003 | 23 | const std::byte *detail::find_pattern( | |
| 1004 | const std::byte *start_address, | ||
| 1005 | std::size_t region_size, | ||
| 1006 | const detail::EnginePattern &pattern, | ||
| 1007 | std::size_t occurrence | ||
| 1008 | ) | ||
| 1009 | { | ||
| 1010 | 23 | SegmentedScanBudget segmented_budget{}; | |
| 1011 | 23 | return find_pattern_nth(start_address, region_size, pattern, occurrence, segmented_budget); | |
| 1012 | } | ||
| 1013 | |||
| 1014 | 24 | const std::byte *detail::find_pattern_nth( | |
| 1015 | const std::byte *start_address, | ||
| 1016 | std::size_t region_size, | ||
| 1017 | const detail::EnginePattern &pattern, | ||
| 1018 | std::size_t occurrence, | ||
| 1019 | SegmentedScanBudget &segmented_budget | ||
| 1020 | ) | ||
| 1021 | { | ||
| 1022 |
2/2✓ Branch 2 → 3 taken 2 times.
✓ Branch 2 → 4 taken 22 times.
|
24 | if (occurrence == 0) |
| 1023 | { | ||
| 1024 | 2 | return nullptr; | |
| 1025 | } | ||
| 1026 |
6/6✓ Branch 5 → 6 taken 21 times.
✓ Branch 5 → 7 taken 1 time.
✓ Branch 6 → 7 taken 1 time.
✓ Branch 6 → 8 taken 20 times.
✓ Branch 9 → 10 taken 2 times.
✓ Branch 9 → 11 taken 20 times.
|
22 | if (pattern.empty() || !start_address) |
| 1027 | { | ||
| 1028 | 2 | return nullptr; | |
| 1029 | } | ||
| 1030 | |||
| 1031 | 20 | const std::byte *cursor = start_address; | |
| 1032 | 20 | std::size_t remaining = region_size; | |
| 1033 | 20 | std::size_t found_count = 0; | |
| 1034 | |||
| 1035 | // Iterate via the raw helper so the continuation advances past each match START (RawMatch::start), which is | ||
| 1036 | // correct regardless of the pattern's offset marker or its variable jump span. The offset-applied result | ||
| 1037 | // (RawMatch::point) is returned only for the Nth hit. A jump pattern needs at least min_match_length() bytes; | ||
| 1038 | // the weaker size() loop guard is a safe lower bound, and find_pattern_raw fails closed on a short tail. | ||
| 1039 |
2/2✓ Branch 22 → 12 taken 37 times.
✓ Branch 22 → 23 taken 1 time.
|
38 | while (remaining >= pattern.size()) |
| 1040 | { | ||
| 1041 | 37 | const RawMatch match = find_pattern_raw(cursor, remaining, pattern, &segmented_budget); | |
| 1042 |
2/2✓ Branch 13 → 14 taken 2 times.
✓ Branch 13 → 15 taken 35 times.
|
37 | if (match.budget_exhausted) |
| 1043 | { | ||
| 1044 | // The current suffix was truncated before its leftmost result was proven, so neither this occurrence | ||
| 1045 | // nor any later one is trustworthy through the pointer-only unchecked surface. | ||
| 1046 | 17 | return nullptr; | |
| 1047 | } | ||
| 1048 |
2/2✓ Branch 15 → 16 taken 2 times.
✓ Branch 15 → 17 taken 33 times.
|
35 | if (!match.start) |
| 1049 | { | ||
| 1050 | 2 | break; | |
| 1051 | } | ||
| 1052 |
2/2✓ Branch 17 → 18 taken 15 times.
✓ Branch 17 → 19 taken 18 times.
|
33 | if (++found_count == occurrence) |
| 1053 | { | ||
| 1054 | 15 | return match.point; | |
| 1055 | } | ||
| 1056 | 18 | const std::size_t advance = static_cast<std::size_t>(match.start - cursor) + 1; | |
| 1057 | 18 | cursor += advance; | |
| 1058 | 18 | remaining -= advance; | |
| 1059 | } | ||
| 1060 | |||
| 1061 | 3 | return nullptr; | |
| 1062 | } | ||
| 1063 | |||
| 1064 | 4 | scan::SimdLevel detail::active_simd_level() noexcept | |
| 1065 | { | ||
| 1066 | #ifdef DMK_HAS_AVX512 | ||
| 1067 | if (cpu_has_avx512()) | ||
| 1068 | return scan::SimdLevel::Avx512; | ||
| 1069 | #endif | ||
| 1070 |
1/2✓ Branch 3 → 4 taken 4 times.
✗ Branch 3 → 5 not taken.
|
4 | if (cpu_has_avx2()) |
| 1071 | 4 | return scan::SimdLevel::Avx2; | |
| 1072 | ✗ | return scan::SimdLevel::Sse2; | |
| 1073 | } | ||
| 1074 | } // namespace DetourModKit | ||
| 1075 |