GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 16 / 0 / 16
Functions: 100.0% 6 / 0 / 6
Branches: 100.0% 4 / 0 / 4
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 <span>
20 #include <string_view>
21 #include <vector>
22
23 namespace DetourModKit
24 {
25 namespace detail
26 {
27 /**
28 * @brief Region-wide ceiling on total bounded-jump backtracking node visits for one segmented scan.
29 * @details The per-position @ref SEGMENT_MATCH_STEP_BUDGET caps one start position, but a non-anchored pattern
30 * tries every start in a region and can otherwise degrade to O(region_size x per-position budget).
31 * Work accumulates across all starts and suffix continuations of one physical region; exceeding the
32 * ceiling marks the result truncated rather than spending unbounded time. An over-broad bounded-jump
33 * pattern should add a literal to its leading segment instead.
34 */
35 inline constexpr std::size_t SEGMENT_MATCH_REGION_STEP_BUDGET = 1u << 26;
36 static_assert(
37 SEGMENT_MATCH_REGION_STEP_BUDGET >= SEGMENT_MATCH_STEP_BUDGET,
38 "The per-region budget must let at least one start position run to its per-position ceiling."
39 );
40
41 /**
42 * @struct EnginePattern
43 * @brief A heap-backed compiled AOB pattern with separate bytes and mask, plus a cached scan anchor.
44 * @details A position matches when (memory_byte ^ @ref bytes) & @ref mask == 0, so 0xFF marks a fully literal
45 * byte, 0x00 a wildcard, and 0xF0 / 0x0F a per-nibble token. Byte values are pre-masked to their known
46 * bits, which is what lets one plain compare be correct at every position without special-casing the
47 * wildcard slots.
48 */
49 struct EnginePattern
50 {
51 /// Pattern bytes, one per token in the source AOB string, pre-masked to their known bits.
52 std::vector<std::byte> bytes;
53
54 /// Per-byte match mask paralleling @ref bytes; sized identically.
55 std::vector<std::byte> mask;
56
57 /**
58 * @brief Byte offset from pattern start to the point of interest, from the `|` marker (0 if absent).
59 * @details May equal bytes.size() when `|` appears at the end. Signed to match pointer arithmetic.
60 */
61 std::ptrdiff_t offset = 0;
62
63 /**
64 * @brief Cached anchor index selected by compile_anchor().
65 * @details find_pattern() drives its memchr sweep on the byte at this position. The anchor is confined to
66 * segment 0 (the fixed run before the first bounded jump) because the matcher finds that run and
67 * then extends across the variable gaps; a byte in a later segment sits at a gap-dependent address
68 * the prefilter cannot sweep for.
69 *
70 * Sentinel values:
71 * - `[0, size())` valid anchor.
72 * - `size()` segment 0 has no fully-known byte to anchor on; the scan degenerates.
73 * - `>= size() + 1` anchor not yet selected; find_pattern() picks one inline (slower path).
74 */
75 std::size_t anchor = std::numeric_limits<std::size_t>::max();
76
77 /**
78 * @brief Bounded-jump gaps between fixed segments, in ascending position order.
79 * @details Empty for a plain pattern, which takes the single fixed-width fast path. Copied verbatim from
80 * the shared parser so the runtime matcher and the compile-time Pattern agree on the segmentation.
81 */
82 std::vector<PatternJump> jumps;
83
84 /// Returns the number of fixed bytes in the pattern (all segments concatenated, gaps excluded).
85 9269508 [[nodiscard]] std::size_t size() const noexcept { return bytes.size(); }
86
87 /// Checks if the pattern has no bytes.
88 6331 [[nodiscard]] bool empty() const noexcept { return bytes.empty(); }
89
90 /// Fewest bytes any match can occupy: the fixed byte count plus every gap's minimum skip.
91 2179 [[nodiscard]] std::size_t min_match_length() const noexcept
92 {
93 2179 std::size_t total = bytes.size();
94
2/2
✓ Branch 16 → 5 taken 2251 times.
✓ Branch 16 → 17 taken 2179 times.
 6609 for (const PatternJump &gap : jumps)
95 {
96 2251 total += gap.min_skip;
97 }
98 2179 return total;
99 }
100
101 /// Most bytes any match can occupy: the fixed byte count plus every gap's maximum skip.
102 25934 [[nodiscard]] std::size_t max_match_length() const noexcept
103 {
104 25934 std::size_t total = bytes.size();
105
2/2
✓ Branch 16 → 5 taken 2170 times.
✓ Branch 16 → 17 taken 25933 times.
 54037 for (const PatternJump &gap : jumps)
106 {
107 2170 total += gap.max_skip;
108 }
109 25933 return total;
110 }
111
112 /**
113 * @brief Selects and stores the rarest fully-known byte's index in segment 0 as the scan anchor.
114 * @details Scores each fully-known byte against a small byte-frequency table so one memchr pass produces
115 * far fewer false candidate hits than anchoring on bytes[0]. Partially-masked nibble positions
116 * cannot anchor: the prefilter needs one exact byte value. Ties break by first occurrence.
117 * Idempotent and O(size()). A caller that mutates @ref bytes, @ref mask, or @ref jumps afterwards
118 * MUST call it again or the cached anchor drifts. Not thread-safe with concurrent find_pattern()
119 * on the same instance.
120 */
121 void compile_anchor() noexcept;
122 };
123
124 /**
125 * @brief Parses a space-separated AOB string into a compiled EnginePattern.
126 * @param aob_str The AOB pattern string.
127 * @return The compiled pattern, or std::nullopt on any parse failure.
128 * @details Drives the single shared grammar through a heap-backed sink, so the runtime engine and the
129 * compile-time scan::Pattern can never silently diverge. Unlike the fixed-array Pattern storage this
130 * imposes no MAX_PATTERN_BYTES cap, so a long runtime pattern compiles here even when it would
131 * overflow a literal Pattern; the jump count is still capped at MAX_PATTERN_JUMPS.
132 */
133 [[nodiscard]] std::optional<EnginePattern> parse_aob(std::string_view aob_str);
134
135 /**
136 * @struct RawMatch
137 * @brief A raw match location: the match start, its one-past-last-byte end, and the offset-applied point.
138 * @details All three are reported because a bounded-jump match has a variable span, and a caller doing
139 * exclusion or cross-boundary counting needs the true end rather than a fixed pattern length. All are
140 * null on no match.
141 */
142 struct RawMatch
143 {
144 /// Leftmost match start (segment 0 address), or nullptr on no match.
145 const std::byte *start = nullptr;
146 /// One past the last matched byte (start + actual match length), or nullptr on no match.
147 const std::byte *end = nullptr;
148 /// The offset-applied result address the `|` marker resolves to, or nullptr on no match.
149 const std::byte *point = nullptr;
150 /**
151 * @brief True when the segmented matcher spent its backtracking budget before the scan was exhaustive.
152 * @details A truncated scan cannot prove there is no earlier match, nor that a found match is the leftmost,
153 * so a caller counting occurrences MUST fail closed. Independent of start/end/point: it can be
154 * true on both a found match and a no-match return. The flat matcher never sets it.
155 */
156 bool budget_exhausted = false;
157 };
158
159 /**
160 * @struct SegmentedScanBudget
161 * @brief Shared bounded-jump work state for one pattern over one physical readable region.
162 * @details The Nth-occurrence helpers continue from the byte after each prior match and pass the same state to
163 * every suffix scan, so the region-wide ceiling cannot reset at a continuation boundary. Meaningful
164 * only for one pattern and one contiguous region; flat patterns ignore it.
165 */
166 struct SegmentedScanBudget
167 {
168 /// Node visits already spent across all segmented suffix scans of the region.
169 std::size_t node_visits = 0;
170 /// True once a per-position or region-wide cap made the occurrence count incomplete.
171 bool exhausted = false;
172 /// True once the region-wide cap prevents any further segmented node visits.
173 bool region_exhausted = false;
174 };
175
176 /**
177 * @brief Builds an EnginePattern from a public value-semantic scan::Pattern.
178 * @param pattern The compiled value Pattern.
179 * @param anchor_index The prefilter position, already in the engine sentinel convention (size() means "no
180 * fully-known byte").
181 * @return The heap-backed engine pattern. Allocates, so a caller on a noexcept path must guard std::bad_alloc.
182 */
183 [[nodiscard]] EnginePattern engine_pattern_from(const scan::Pattern &pattern, std::size_t anchor_index);
184
185 /**
186 * @brief Scans a readable memory region for the first occurrence of a byte pattern.
187 * @param start_address Pointer to the beginning of the region to scan.
188 * @param region_size The size in bytes of the region to scan.
189 * @param pattern The compiled pattern.
190 * @return Pointer to the match (adjusted by pattern.offset), or nullptr if not found.
191 * @warning READABLE-RANGE PRECONDITION: this raw matcher performs no page filtering. The caller MUST guarantee
192 * the entire span is committed and readable; the search reads it with raw memchr/SIMD loads.
193 */
194 [[nodiscard]] const std::byte *
195 find_pattern(const std::byte *start_address, std::size_t region_size, const EnginePattern &pattern);
196
197 /**
198 * @brief Scans a readable region for the Nth occurrence of a byte pattern.
199 * @param start_address Pointer to the beginning of the region to scan.
200 * @param region_size The size in bytes of the region to scan.
201 * @param pattern The compiled pattern.
202 * @param occurrence Which occurrence to return (1-based). Passing 0 returns nullptr.
203 * @return Pointer to the Nth occurrence (adjusted by pattern.offset), or nullptr if fewer than N matches exist.
204 * @warning Same READABLE-RANGE PRECONDITION as the single-occurrence overload.
205 */
206 [[nodiscard]] const std::byte *find_pattern(
207 const std::byte *start_address,
208 std::size_t region_size,
209 const EnginePattern &pattern,
210 std::size_t occurrence
211 );
212
213 /**
214 * @brief Implements an Nth-occurrence scan with caller-owned bounded-jump work state.
215 * @param start_address Pointer to the beginning of the region to scan.
216 * @param region_size The size in bytes of the region to scan.
217 * @param pattern The compiled pattern.
218 * @param occurrence Which occurrence to return (1-based). Passing 0 returns nullptr.
219 * @param segmented_budget Shared bounded-jump work state for all suffix scans of this region.
220 * @return Pointer to the Nth occurrence (adjusted by pattern.offset), or nullptr on a miss or truncated scan.
221 * @details Keeping the budget outside the suffix loop is what stops bounded-jump work from resetting after each
222 * prior match. The state must belong to this one pattern and contiguous readable region.
223 * @warning Same READABLE-RANGE PRECONDITION as the single-occurrence overload.
224 */
225 [[nodiscard]] const std::byte *find_pattern_nth(
226 const std::byte *start_address,
227 std::size_t region_size,
228 const EnginePattern &pattern,
229 std::size_t occurrence,
230 SegmentedScanBudget &segmented_budget
231 );
232
233 /// Span convenience over the pointer+size single-occurrence matcher (same READABLE-RANGE precondition).
234 [[nodiscard]] inline const std::byte *
235 2 find_pattern(std::span<const std::byte> region, const EnginePattern &pattern)
236 {
237 2 return find_pattern(region.data(), region.size(), pattern);
238 }
239
240 /// Span convenience over the pointer+size Nth-occurrence matcher (same READABLE-RANGE precondition).
241 [[nodiscard]] inline const std::byte *
242 1 find_pattern(std::span<const std::byte> region, const EnginePattern &pattern, std::size_t occurrence)
243 {
244 1 return find_pattern(region.data(), region.size(), pattern, occurrence);
245 }
246
247 /**
248 * @brief Locates the leftmost match and reports its start, end, and resolved point.
249 * @param segmented_budget Optional shared state for bounded-jump suffix continuations of one region.
250 * @details The single dispatch point for both the flat fixed-width fast path and the segmented backtracking
251 * matcher. The offset is baked into RawMatch::point so it is applied exactly once regardless of gap
252 * widths. When @p segmented_budget is supplied, bounded-jump work accumulates across every suffix
253 * continuation over the same physical region.
254 */
255 [[nodiscard]] RawMatch find_pattern_raw(
256 const std::byte *start_address,
257 std::size_t region_size,
258 const EnginePattern &pattern,
259 SegmentedScanBudget *segmented_budget = nullptr
260 ) noexcept;
261
262 /**
263 * @brief True when @p pattern carries at least one literal (non-wildcard) byte.
264 * @details Shared guard for the "all wildcards matches anywhere" degenerate case the page sweeps screen for.
265 */
266 [[nodiscard]] bool pattern_has_literal_byte(const EnginePattern &pattern) noexcept;
267
268 /**
269 * @brief Reports the SIMD tier find_pattern matching uses at runtime.
270 * @details Reflects compile-time support and runtime CPU detection. Reports Avx512 only on a DMK_ENABLE_AVX512
271 * build on an AVX-512F + AVX-512BW host; otherwise the highest available lower tier.
272 */
273 [[nodiscard]] scan::SimdLevel active_simd_level() noexcept;
274 } // namespace detail
275 } // namespace DetourModKit
276
277 #endif // DETOURMODKIT_INTERNAL_SCAN_ENGINE_HPP
278