GCC Code Coverage Report

./
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
12 / 12
100.0%
Branches:
4 / 4
100.0%
Functions:
4 / 4
100.0%
src/internal/scan_engine.hpp
Line Branch Exec Source
1 #ifndef DETOURMODKIT_INTERNAL_SCAN_ENGINE_HPP
2 #define DETOURMODKIT_INTERNAL_SCAN_ENGINE_HPP
3
4 /**
5 * @file internal/scan_engine.hpp
6 * @brief Raw AOB matching engine: the compiled-pattern representation, the rarest-byte anchor selector, the
7 * memchr-prefiltered SIMD match loop, and the runtime SIMD-tier report.
8 * @details Never installed. The public scan::Pattern is converted to an EnginePattern through engine_pattern_from(), so
9 * the matcher sees one representation regardless of whether the pattern came from a DSL string or the
10 * value-semantic Pattern.
11 */
12
13 #include "DetourModKit/scan.hpp"
14
15 #include <cstddef>
16 #include <cstdint>
17 #include <limits>
18 #include <optional>
19 #include <string_view>
20 #include <vector>
21
22 namespace DetourModKit
23 {
24 namespace detail
25 {
26 /**
27 * @brief Region-wide ceiling on bounded-jump node visits for one segmented scan (`[B-65]`).
28 * @details @ref SEGMENT_MATCH_STEP_BUDGET caps one start position. This ceiling caps the sum over every start
29 * and suffix continuation of one physical region. A spent ceiling marks the result truncated.
30 */
31 inline constexpr std::size_t SEGMENT_MATCH_REGION_STEP_BUDGET = 1u << 26;
32 static_assert(
33 SEGMENT_MATCH_REGION_STEP_BUDGET >= SEGMENT_MATCH_STEP_BUDGET,
34 "The per-region budget must let at least one start position run to its per-position ceiling."
35 );
36
37 /**
38 * @struct EnginePattern
39 * @brief A heap-backed compiled AOB pattern with separate bytes and mask, plus a cached scan anchor.
40 * @details A position matches when (memory_byte ^ @ref bytes) & @ref mask == 0. @ref PatternBuffer owns the
41 * mask values, and @ref bytes holds values pre-masked to their known bits.
42 */
43 struct EnginePattern
44 {
45 /// Pattern bytes, one per token in the source AOB string, pre-masked to their known bits.
46 std::vector<std::byte> bytes;
47
48 /// Per-byte match mask paralleling @ref bytes; sized identically.
49 std::vector<std::byte> mask;
50
51 /**
52 * @brief Byte offset from pattern start to the point of interest, from the `|` marker (0 if absent).
53 * @details May equal bytes.size() when `|` appears at the end. Signed to match pointer arithmetic.
54 */
55 std::ptrdiff_t offset = 0;
56
57 /**
58 * @brief Index of the byte that the memchr prefilter sweeps for, confined to segment 0 (`[B-55]`).
59 * @details Sentinel values:
60 * - `[0, size())` valid anchor.
61 * - `size()` segment 0 has no fully-known byte, so the scan degenerates.
62 * - `>= size() + 1` no anchor selected yet, so find_pattern() selects one inline (slower path).
63 */
64 std::size_t anchor = std::numeric_limits<std::size_t>::max();
65
66 /**
67 * @brief Bounded-jump gaps between fixed segments, in ascending position order.
68 * @details Empty for a plain pattern, which takes the single fixed-width fast path. Copied verbatim from
69 * the shared parser so the runtime matcher and the compile-time Pattern agree on the segmentation.
70 */
71 std::vector<PatternJump> jumps;
72
73 /// Returns the number of fixed bytes in the pattern (all segments concatenated, gaps excluded).
74 11834151 [[nodiscard]] std::size_t size() const noexcept { return bytes.size(); }
75
76 /// Checks if the pattern has no bytes.
77 6607 [[nodiscard]] bool empty() const noexcept { return bytes.empty(); }
78
79 /// Fewest bytes any match can occupy: the fixed byte count plus every gap's minimum skip.
80 2664 [[nodiscard]] std::size_t min_match_length() const noexcept
81 {
82 2664 std::size_t total = bytes.size();
83
2/2
✓ Branch 16 → 5 taken 2736 times.
✓ Branch 16 → 17 taken 2664 times.
 8064 for (const PatternJump &gap : jumps)
84 {
85 2736 total += gap.min_skip;
86 }
87 2664 return total;
88 }
89
90 /// Most bytes any match can occupy: the fixed byte count plus every gap's maximum skip.
91 28635 [[nodiscard]] std::size_t max_match_length() const noexcept
92 {
93 28635 std::size_t total = bytes.size();
94
2/2
✓ Branch 16 → 5 taken 2654 times.
✓ Branch 16 → 17 taken 28635 times.
 59924 for (const PatternJump &gap : jumps)
95 {
96 2654 total += gap.max_skip;
97 }
98 28635 return total;
99 }
100
101 /**
102 * @brief Selects and stores the rarest fully-known byte's index in segment 0 as the scan anchor.
103 * @details Idempotent. A caller that changes @ref bytes, @ref mask, or @ref jumps must call it again.
104 */
105 void compile_anchor() noexcept;
106 };
107
108 /**
109 * @brief Parses a space-separated AOB string into a compiled EnginePattern.
110 * @param aob_str The AOB pattern string.
111 * @return The compiled pattern, `BadPattern` on a parse failure, or `OutOfMemory` when the heap sink cannot
112 * grow.
113 * @details The heap sink runs the shared grammar with no MAX_PATTERN_BYTES cap. The jump count keeps the
114 * MAX_PATTERN_JUMPS cap.
115 */
116 [[nodiscard]] Result<EnginePattern> parse_aob(std::string_view aob_str);
117
118 /**
119 * @struct RawMatch
120 * @brief A raw match location: the match start, its one-past-last-byte end, and the offset-applied point.
121 * @details All three are reported because a bounded-jump match has a variable span, and a caller doing
122 * exclusion or cross-boundary counting needs the true end rather than a fixed pattern length. All are
123 * null on no match.
124 */
125 struct RawMatch
126 {
127 /// Leftmost match start (segment 0 address), or nullptr on no match.
128 const std::byte *start = nullptr;
129 /// One past the last matched byte (start + actual match length), or nullptr on no match.
130 const std::byte *end = nullptr;
131 /// The offset-applied result address the `|` marker resolves to, or nullptr on no match.
132 const std::byte *point = nullptr;
133 /**
134 * @brief True when the segmented matcher spent its backtracking budget before the scan was exhaustive.
135 * @details A truncated scan cannot prove there is no earlier match, nor that a found match is the leftmost,
136 * so a caller counting occurrences MUST fail closed. Independent of start/end/point: it can be
137 * true on both a found match and a no-match return. The flat matcher never sets it.
138 */
139 bool budget_exhausted = false;
140 };
141
142 /**
143 * @struct SegmentedScanBudget
144 * @brief Bounded-jump work state for one pattern over one physical readable region.
145 * @details Every suffix scan of the region shares it, so the region-wide ceiling cannot reset at a
146 * continuation boundary. Flat patterns ignore it.
147 */
148 struct SegmentedScanBudget
149 {
150 /// Node visits already spent across all segmented suffix scans of the region.
151 std::size_t node_visits = 0;
152 /// True once a per-position or region-wide cap made the occurrence count incomplete.
153 bool exhausted = false;
154 /// True once the region-wide cap prevents any further segmented node visits.
155 bool region_exhausted = false;
156 };
157
158 /**
159 * @brief Builds an EnginePattern from a public value-semantic scan::Pattern.
160 * @param pattern The compiled value Pattern.
161 * @param anchor_index The prefilter position, already in the engine sentinel convention (size() means "no
162 * fully-known byte").
163 * @return The heap-backed engine pattern. Allocates, so a caller on a noexcept path must guard std::bad_alloc.
164 */
165 [[nodiscard]] EnginePattern engine_pattern_from(const scan::Pattern &pattern, std::size_t anchor_index);
166
167 /**
168 * @brief Scans a readable memory region for the first occurrence of a byte pattern.
169 * @param start_address Pointer to the beginning of the region to scan.
170 * @param region_size The size in bytes of the region to scan.
171 * @param pattern The compiled pattern.
172 * @return Pointer to the match (adjusted by pattern.offset), or nullptr if not found.
173 * @warning READABLE-RANGE PRECONDITION: this raw matcher performs no page filtering. The caller MUST guarantee
174 * the entire span is committed and readable; the search reads it with raw memchr/SIMD loads.
175 */
176 [[nodiscard]] const std::byte *
177 find_pattern(const std::byte *start_address, std::size_t region_size, const EnginePattern &pattern);
178
179 /**
180 * @brief Scans a readable region for the Nth occurrence of a byte pattern.
181 * @param start_address Pointer to the beginning of the region to scan.
182 * @param region_size The size in bytes of the region to scan.
183 * @param pattern The compiled pattern.
184 * @param occurrence Which occurrence to return (1-based). Passing 0 returns nullptr.
185 * @return Pointer to the Nth occurrence (adjusted by pattern.offset), or nullptr if fewer than N matches exist.
186 * @warning Same READABLE-RANGE PRECONDITION as the single-occurrence overload.
187 */
188 [[nodiscard]] const std::byte *find_pattern(
189 const std::byte *start_address,
190 std::size_t region_size,
191 const EnginePattern &pattern,
192 std::size_t occurrence
193 );
194
195 /**
196 * @brief Implements an Nth-occurrence scan with caller-owned bounded-jump work state.
197 * @param start_address Pointer to the beginning of the region to scan.
198 * @param region_size The size in bytes of the region to scan.
199 * @param pattern The compiled pattern.
200 * @param occurrence Which occurrence to return (1-based). Passing 0 returns nullptr.
201 * @param segmented_budget Shared bounded-jump work state for all suffix scans of this region.
202 * @return Pointer to the Nth occurrence (adjusted by pattern.offset), or nullptr on a miss or truncated scan.
203 * @warning Same READABLE-RANGE PRECONDITION as the single-occurrence overload.
204 */
205 [[nodiscard]] const std::byte *find_pattern_nth(
206 const std::byte *start_address,
207 std::size_t region_size,
208 const EnginePattern &pattern,
209 std::size_t occurrence,
210 SegmentedScanBudget &segmented_budget
211 );
212
213 /**
214 * @brief Locates the leftmost match and reports its start, end, and resolved point.
215 * @param segmented_budget Optional shared state for bounded-jump suffix continuations of one region.
216 * @details The single dispatch point for both the flat fixed-width fast path and the segmented backtracking
217 * matcher. The offset is baked into RawMatch::point so it is applied exactly once regardless of gap
218 * widths.
219 */
220 [[nodiscard]] RawMatch find_pattern_raw(
221 const std::byte *start_address,
222 std::size_t region_size,
223 const EnginePattern &pattern,
224 SegmentedScanBudget *segmented_budget = nullptr
225 ) noexcept;
226
227 /**
228 * @brief True when @p pattern carries at least one literal (non-wildcard) byte.
229 * @details Shared guard for the "all wildcards matches anywhere" degenerate case the page sweeps screen for.
230 */
231 [[nodiscard]] bool pattern_has_literal_byte(const EnginePattern &pattern) noexcept;
232
233 /**
234 * @brief Reports the SIMD tier find_pattern matching uses at runtime.
235 * @details Reflects compile-time support and runtime CPU detection. Reports Avx512 only on a DMK_ENABLE_AVX512
236 * build on an AVX-512F + AVX-512BW host; otherwise the highest available lower tier.
237 */
238 [[nodiscard]] scan::SimdLevel active_simd_level() noexcept;
239 } // namespace detail
240 } // namespace DetourModKit
241
242 #endif // DETOURMODKIT_INTERNAL_SCAN_ENGINE_HPP
243