GCC Code Coverage Report

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