include/DetourModKit/detail/pattern_core.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #ifndef DETOURMODKIT_DETAIL_PATTERN_CORE_HPP | ||
| 2 | #define DETOURMODKIT_DETAIL_PATTERN_CORE_HPP | ||
| 3 | |||
| 4 | /** | ||
| 5 | * @file pattern_core.hpp | ||
| 6 | * @brief Logger-free, heap-free constexpr core that parses the AOB mini-DSL and selects a rarest-byte anchor. | ||
| 7 | * @details `scan::Pattern::compile()` and the consteval `scan::Pattern::literal()` both parse through this core. It | ||
| 8 | * uses fixed-size arrays because a consteval result cannot own heap storage. The runtime scan engine shares | ||
| 9 | * its grammar and byte/mask encoding. A scan can replace this anchor with a haystack-based one. | ||
| 10 | * @note `scan.hpp` includes this header. docs/design/public-api.md owns the `detail/` placement rule. | ||
| 11 | */ | ||
| 12 | |||
| 13 | #include <array> | ||
| 14 | #include <cstddef> | ||
| 15 | #include <cstdint> | ||
| 16 | #include <span> | ||
| 17 | #include <string_view> | ||
| 18 | |||
| 19 | namespace DetourModKit::detail | ||
| 20 | { | ||
| 21 | /** @brief Inline-storage cap for a compiled pattern, in bytes. `literal()` and `compile()` share this cap. */ | ||
| 22 | inline constexpr std::size_t MAX_PATTERN_BYTES = 128; | ||
| 23 | |||
| 24 | /** @brief Anchor sentinel for "segment 0 has no fully-known byte", one past any valid index. */ | ||
| 25 | inline constexpr std::size_t NO_ANCHOR = MAX_PATTERN_BYTES; | ||
| 26 | |||
| 27 | /** @brief Cap on bounded-jump gaps in one pattern. A pattern with more gaps fails at parse with TooManyJumps. */ | ||
| 28 | inline constexpr std::size_t MAX_PATTERN_JUMPS = 8; | ||
| 29 | |||
| 30 | /** @brief Cap on the maximum skip of one jump gap, in bytes. The parser rejects a larger bound. */ | ||
| 31 | inline constexpr std::size_t MAX_JUMP_SPAN = 256; | ||
| 32 | |||
| 33 | /** @brief Per-start-position cap on matcher node visits. Past the cap, that placement reports no match. */ | ||
| 34 | inline constexpr std::size_t SEGMENT_MATCH_STEP_BUDGET = 1u << 16; | ||
| 35 | static_assert( | ||
| 36 | SEGMENT_MATCH_STEP_BUDGET >= MAX_PATTERN_JUMPS * MAX_JUMP_SPAN, | ||
| 37 | "The per-position work budget must exceed the linear per-position cost of a well-formed pattern." | ||
| 38 | ); | ||
| 39 | |||
| 40 | /** | ||
| 41 | * @brief One bounded gap between two fixed byte runs (segments) of a compiled pattern. | ||
| 42 | * @details @ref position lies strictly inside `(0, length)`. An exact `[N]` jump has `min_skip == max_skip`. | ||
| 43 | */ | ||
| 44 | struct PatternJump | ||
| 45 | { | ||
| 46 | /// Index in the fixed byte stream that the gap precedes: the boundary between segment i and segment i+1. | ||
| 47 | std::size_t position{0}; | ||
| 48 | /// Fewest bytes the gap can skip before the following segment. | ||
| 49 | std::size_t min_skip{0}; | ||
| 50 | /// Most bytes the gap can skip before the following segment, in [min_skip, MAX_JUMP_SPAN]. | ||
| 51 | std::size_t max_skip{0}; | ||
| 52 | }; | ||
| 53 | |||
| 54 | /** @brief Outcome of an AOB DSL parse in the constexpr core. */ | ||
| 55 | enum class PatternStatus : std::uint8_t | ||
| 56 | { | ||
| 57 | /// Parsed successfully into at least one byte. | ||
| 58 | Ok, | ||
| 59 | /// The input held no byte tokens (empty, whitespace-only, or only an offset marker). | ||
| 60 | Empty, | ||
| 61 | /// A token was not a recognized DSL form. | ||
| 62 | InvalidToken, | ||
| 63 | /// The pattern exceeded MAX_PATTERN_BYTES byte tokens. | ||
| 64 | TooLong, | ||
| 65 | /// More than one offset marker was present. | ||
| 66 | DuplicateOffset, | ||
| 67 | /// A `[...]` jump token was malformed, out of range, or illegally placed (leading, trailing, or adjacent). | ||
| 68 | InvalidJump, | ||
| 69 | /// The pattern named more bounded jumps than MAX_PATTERN_JUMPS. | ||
| 70 | TooManyJumps | ||
| 71 | }; | ||
| 72 | |||
| 73 | /** @brief A compiled pattern: segment bytes and masks with no gap bytes, plus offset, jumps, and anchor. */ | ||
| 74 | struct PatternBuffer | ||
| 75 | { | ||
| 76 | /// Pattern byte values. Only entries [0, length) are valid. | ||
| 77 | std::array<std::byte, MAX_PATTERN_BYTES> bytes{}; | ||
| 78 | /// Per-byte match mask (0xFF fully known, 0x00 wildcard, 0xF0 high nibble, 0x0F low nibble). | ||
| 79 | std::array<std::byte, MAX_PATTERN_BYTES> mask{}; | ||
| 80 | /// Number of valid byte entries: all segments concatenated, gaps excluded. | ||
| 81 | std::size_t length{0}; | ||
| 82 | /// Result offset that the `|` marker records, or 0 (the match start) when no marker is present. | ||
| 83 | std::size_t offset{0}; | ||
| 84 | /// Index of the rarest fully-known byte in segment 0, or NO_ANCHOR when segment 0 has none. | ||
| 85 | std::size_t anchor{NO_ANCHOR}; | ||
| 86 | /// Bounded-jump gaps in ascending position order. Only entries [0, jump_count) are valid. | ||
| 87 | std::array<PatternJump, MAX_PATTERN_JUMPS> jumps{}; | ||
| 88 | /// Number of valid jump gaps, 0 for a plain (single-segment) pattern. | ||
| 89 | std::size_t jump_count{0}; | ||
| 90 | }; | ||
| 91 | |||
| 92 | /** @brief A parse status paired with the buffer it produced. */ | ||
| 93 | struct PatternParse | ||
| 94 | { | ||
| 95 | /// Parse outcome. | ||
| 96 | PatternStatus status{PatternStatus::Empty}; | ||
| 97 | /// The compiled representation, meaningful only when @ref status is Ok. | ||
| 98 | PatternBuffer buffer{}; | ||
| 99 | }; | ||
| 100 | |||
| 101 | /// Maps a hex digit to its value 0 to 15, or -1 if @p ch is not a hex digit. | ||
| 102 | 1570974 | [[nodiscard]] constexpr int hex_digit(char ch) noexcept | |
| 103 | { | ||
| 104 | 1570974 | if (ch >= '0' && ch <= '9') | |
| 105 | { | ||
| 106 | 498840 | return ch - '0'; | |
| 107 | } | ||
| 108 | 1072134 | if (ch >= 'a' && ch <= 'f') | |
| 109 | { | ||
| 110 | 138908 | return ch - 'a' + 10; | |
| 111 | } | ||
| 112 | 933226 | if (ch >= 'A' && ch <= 'F') | |
| 113 | { | ||
| 114 | 423951 | return ch - 'A' + 10; | |
| 115 | } | ||
| 116 | 509275 | return -1; | |
| 117 | } | ||
| 118 | |||
| 119 | /// True for a character that separates DSL tokens. | ||
| 120 | 7587711 | [[nodiscard]] constexpr bool is_token_space(char ch) noexcept | |
| 121 | { | ||
| 122 | 7587711 | return ch == ' ' || ch == '\t' || ch == '\r' || ch == '\n' || ch == '\f' || ch == '\v'; | |
| 123 | } | ||
| 124 | |||
| 125 | /** | ||
| 126 | * @brief Scores how common @p value is in typical x64 .text. A lower score is a rarer byte, and 0 is the rarest. | ||
| 127 | * @details The runtime scan engine and `sighealth` score with this same table. | ||
| 128 | */ | ||
| 129 | 14967 | [[nodiscard]] constexpr std::uint8_t byte_frequency_class(std::uint8_t value) noexcept | |
| 130 | { | ||
| 131 | 14967 | switch (value) | |
| 132 | { | ||
| 133 | 165 | case 0x00: | |
| 134 | 165 | return 10; | |
| 135 | 107 | case 0xCC: | |
| 136 | 107 | return 9; | |
| 137 | 134 | case 0x90: | |
| 138 | 134 | return 9; | |
| 139 | 286 | case 0xFF: | |
| 140 | 286 | return 8; | |
| 141 | 287 | case 0x48: | |
| 142 | 287 | return 8; | |
| 143 | 191 | case 0x8B: | |
| 144 | 191 | return 7; | |
| 145 | 28 | case 0x89: | |
| 146 | 28 | return 7; | |
| 147 | 46 | case 0x0F: | |
| 148 | 46 | return 7; | |
| 149 | 38 | case 0xE8: | |
| 150 | 38 | return 6; | |
| 151 | 104 | case 0xE9: | |
| 152 | 104 | return 6; | |
| 153 | 36 | case 0x83: | |
| 154 | 36 | return 6; | |
| 155 | 52 | case 0xC3: | |
| 156 | 52 | return 5; | |
| 157 | 13493 | default: | |
| 158 | 13493 | return 0; | |
| 159 | } | ||
| 160 | } | ||
| 161 | |||
| 162 | /** | ||
| 163 | * @brief Picks the rarest fully-known byte in segment 0 (the run before the first jump) as the prefilter anchor. | ||
| 164 | * @return Its index (the lowest index on a score tie), or NO_ANCHOR when segment 0 has no fully-known byte. | ||
| 165 | */ | ||
| 166 | 20623 | [[nodiscard]] constexpr std::size_t select_anchor(const PatternBuffer &buffer) noexcept | |
| 167 | { | ||
| 168 | 20623 | const std::size_t segment0_end = (buffer.jump_count > 0) ? buffer.jumps[0].position : buffer.length; | |
| 169 | 20623 | std::size_t best = NO_ANCHOR; | |
| 170 | 20623 | std::uint8_t best_score = 0xFF; | |
| 171 | 69936 | for (std::size_t index = 0; index < segment0_end; ++index) | |
| 172 | { | ||
| 173 | 61450 | if (buffer.mask[index] != std::byte{0xFF}) | |
| 174 | { | ||
| 175 | 48243 | continue; | |
| 176 | } | ||
| 177 | 26414 | const std::uint8_t score = byte_frequency_class(std::to_integer<std::uint8_t>(buffer.bytes[index])); | |
| 178 | 13207 | if (score < best_score) | |
| 179 | { | ||
| 180 | 13017 | best = index; | |
| 181 | 13017 | best_score = score; | |
| 182 | 13017 | if (score == 0) | |
| 183 | { | ||
| 184 | 12137 | break; | |
| 185 | } | ||
| 186 | } | ||
| 187 | } | ||
| 188 | 20623 | return best; | |
| 189 | } | ||
| 190 | |||
| 191 | /** @brief Parse outcome of one `[...]` bounded-jump token: a validity flag plus the resolved skip bounds. */ | ||
| 192 | struct JumpParse | ||
| 193 | { | ||
| 194 | /// True when the token was a well-formed, in-range bounded jump. | ||
| 195 | bool ok{false}; | ||
| 196 | /// Fewest bytes the gap skips. | ||
| 197 | std::size_t min_skip{0}; | ||
| 198 | /// Most bytes the gap skips. | ||
| 199 | std::size_t max_skip{0}; | ||
| 200 | }; | ||
| 201 | |||
| 202 | /** | ||
| 203 | * @brief Parses a whitespace-stripped bounded-jump token: `[X]` (exact, `[0]` is a valid no-op) or `[X-Y]` (range). | ||
| 204 | * @details It rejects missing brackets, empty or non-decimal content, trailing junk, an inverted range, a bound | ||
| 205 | * above MAX_JUMP_SPAN, and the unbounded `[X-]` form. | ||
| 206 | */ | ||
| 207 | 125308 | [[nodiscard]] constexpr JumpParse parse_jump_token(std::string_view token) noexcept | |
| 208 | { | ||
| 209 | 125308 | JumpParse result{}; | |
| 210 | 125308 | if (token.size() < 3 || token.front() != '[' || token.back() != ']') | |
| 211 | { | ||
| 212 | 4 | return result; | |
| 213 | } | ||
| 214 | 125304 | const std::string_view inner = token.substr(1, token.size() - 2); | |
| 215 | |||
| 216 | 125304 | std::size_t cursor = 0; | |
| 217 | // A jump always names at least one number. | ||
| 218 | 125304 | if (cursor >= inner.size() || inner[cursor] < '0' || inner[cursor] > '9') | |
| 219 | { | ||
| 220 | 1 | return result; | |
| 221 | } | ||
| 222 | 125303 | std::size_t min_value = 0; | |
| 223 | 447493 | while (cursor < inner.size() && inner[cursor] >= '0' && inner[cursor] <= '9') | |
| 224 | { | ||
| 225 | 322190 | min_value = min_value * 10 + static_cast<std::size_t>(inner[cursor] - '0'); | |
| 226 | 322190 | if (min_value > MAX_JUMP_SPAN) | |
| 227 | { | ||
| 228 | // This early exit also keeps the accumulator far from overflow. | ||
| 229 | ✗ | return result; | |
| 230 | } | ||
| 231 | 322190 | ++cursor; | |
| 232 | } | ||
| 233 | |||
| 234 | 125303 | std::size_t max_value = min_value; | |
| 235 | 125303 | if (cursor < inner.size()) | |
| 236 | { | ||
| 237 | 61984 | if (inner[cursor] != '-') | |
| 238 | { | ||
| 239 | ✗ | return result; | |
| 240 | } | ||
| 241 | 61984 | ++cursor; | |
| 242 | // A dash with no digits after it is the unbounded `[X-]` form, which the parser rejects. | ||
| 243 | 61984 | if (cursor >= inner.size() || inner[cursor] < '0' || inner[cursor] > '9') | |
| 244 | { | ||
| 245 | 2 | return result; | |
| 246 | } | ||
| 247 | 61982 | max_value = 0; | |
| 248 | 242177 | while (cursor < inner.size() && inner[cursor] >= '0' && inner[cursor] <= '9') | |
| 249 | { | ||
| 250 | 180196 | max_value = max_value * 10 + static_cast<std::size_t>(inner[cursor] - '0'); | |
| 251 | 180196 | if (max_value > MAX_JUMP_SPAN) | |
| 252 | { | ||
| 253 | 1 | return result; | |
| 254 | } | ||
| 255 | 180195 | ++cursor; | |
| 256 | } | ||
| 257 | } | ||
| 258 | |||
| 259 | 125300 | if (cursor != inner.size() || max_value < min_value) | |
| 260 | { | ||
| 261 | // Trailing junk after the bounds, or an inverted range. | ||
| 262 | 3 | return result; | |
| 263 | } | ||
| 264 | 125297 | result.ok = true; | |
| 265 | 125297 | result.min_skip = min_value; | |
| 266 | 125297 | result.max_skip = max_value; | |
| 267 | 125297 | return result; | |
| 268 | } | ||
| 269 | |||
| 270 | /** @brief The fixed-array sink of @ref parse_pattern, capped at MAX_PATTERN_BYTES and MAX_PATTERN_JUMPS. */ | ||
| 271 | struct PatternBufferSink | ||
| 272 | { | ||
| 273 | /// The buffer that the parse fills, meaningful only after the parse returns Ok. | ||
| 274 | PatternBuffer buffer{}; | ||
| 275 | |||
| 276 | /// Fixed bytes appended so far. | ||
| 277 | 559766 | [[nodiscard]] constexpr std::size_t length() const noexcept { return buffer.length; } | |
| 278 | /// Jump gaps appended so far. | ||
| 279 | 20624 | [[nodiscard]] constexpr std::size_t jump_count() const noexcept { return buffer.jump_count; } | |
| 280 | |||
| 281 | /// Appends one fixed byte, or returns false at the byte cap (the parser reports TooLong). | ||
| 282 | 1276997 | [[nodiscard]] constexpr bool add_byte(std::byte value, std::byte mask) noexcept | |
| 283 | { | ||
| 284 | 1276997 | if (buffer.length >= MAX_PATTERN_BYTES) | |
| 285 | { | ||
| 286 | 2 | return false; | |
| 287 | } | ||
| 288 | 1276995 | buffer.bytes[buffer.length] = value; | |
| 289 | 1276995 | buffer.mask[buffer.length] = mask; | |
| 290 | 1276995 | ++buffer.length; | |
| 291 | 1276995 | return true; | |
| 292 | } | ||
| 293 | |||
| 294 | /// Records a gap, or returns false at the jump cap (the parser reports TooManyJumps). | ||
| 295 | 125246 | [[nodiscard]] constexpr bool add_jump(std::size_t position, std::size_t min_skip, std::size_t max_skip) noexcept | |
| 296 | { | ||
| 297 | 125246 | if (buffer.jump_count >= MAX_PATTERN_JUMPS) | |
| 298 | { | ||
| 299 | 1 | return false; | |
| 300 | } | ||
| 301 | 125245 | buffer.jumps[buffer.jump_count] = PatternJump{position, min_skip, max_skip}; | |
| 302 | 125245 | ++buffer.jump_count; | |
| 303 | 125245 | return true; | |
| 304 | } | ||
| 305 | |||
| 306 | /// Records the `|` marker position in the fixed byte stream. | ||
| 307 | 19087 | constexpr void set_offset(std::size_t position) noexcept { buffer.offset = position; } | |
| 308 | }; | ||
| 309 | |||
| 310 | /** | ||
| 311 | * @brief The single AOB DSL grammar, which parses into any storage sink (fixed-array or heap-backed). | ||
| 312 | * @param sink A sink that provides add_byte, add_jump, set_offset, length, and jump_count. | ||
| 313 | * @return On Ok, the sink holds the bytes, mask, jumps, and offset. The caller selects the anchor. | ||
| 314 | * @details Whitespace splits the tokens. Recognized tokens: | ||
| 315 | * - two hex digits (`48`): that byte, mask 0xFF (fully known). | ||
| 316 | * - `??` or `?`: any byte, mask 0x00 (full wildcard). | ||
| 317 | * - hex digit then `?` (`4?`): high nibble known, mask 0xF0. | ||
| 318 | * - `?` then hex digit (`?5`): low nibble known, mask 0x0F. | ||
| 319 | * - `[X]` or `[X-Y]`: a bounded jump that skips exactly X, or X to Y, bytes before the next segment. | ||
| 320 | * - `|`: the offset marker, at most once. The result offset is the position of the next byte, or the | ||
| 321 | * length when the marker trails. | ||
| 322 | * | ||
| 323 | * Any other token fails with InvalidToken. A malformed token that opens with `[` fails with InvalidJump. | ||
| 324 | * An input with only whitespace and at most one `|` fails with Empty. A sink that rejects an append fails | ||
| 325 | * with TooLong (byte cap) or TooManyJumps (jump cap). | ||
| 326 | * | ||
| 327 | * Every segment must be a non-empty fixed run, so a jump cannot lead, trail, or be adjacent to another | ||
| 328 | * jump. A violation is InvalidJump. The `|` marker records a position in the fixed byte stream. When the | ||
| 329 | * pattern also has jumps, the runtime scan engine adds the actual gap bytes at match time. | ||
| 330 | * @note It propagates an exception that the sink throws. `parse_aob` catches the `bad_alloc` of its heap-backed | ||
| 331 | * sink and returns `OutOfMemory`. docs/design/resolution.md owns the noexcept rule. | ||
| 332 | */ | ||
| 333 | 21566 | template <class Sink> [[nodiscard]] constexpr PatternStatus parse_pattern_into(std::string_view dsl, Sink &sink) | |
| 334 | { | ||
| 335 | 21566 | bool offset_marked = false; | |
| 336 | |||
| 337 | // The fixed length at the most recent jump, or 0. A new jump needs a fixed byte after this boundary, which | ||
| 338 | // rejects a leading jump and two adjacent jumps. The end-of-parse check against it rejects a trailing jump. | ||
| 339 | 21566 | std::size_t last_boundary = 0; | |
| 340 | |||
| 341 | 21566 | std::size_t cursor = 0; | |
| 342 | 21566 | const std::size_t end = dsl.size(); | |
| 343 | 2887015 | while (cursor < end) | |
| 344 | { | ||
| 345 | 2865531 | if (is_token_space(dsl[cursor])) | |
| 346 | { | ||
| 347 | 1427375 | ++cursor; | |
| 348 | 1571768 | continue; | |
| 349 | } | ||
| 350 | |||
| 351 | 1438156 | const std::size_t token_start = cursor; | |
| 352 | 4732911 | while (cursor < end && !is_token_space(dsl[cursor])) | |
| 353 | { | ||
| 354 | 3294755 | ++cursor; | |
| 355 | } | ||
| 356 | 1438156 | const std::string_view token = dsl.substr(token_start, cursor - token_start); | |
| 357 | |||
| 358 | // Offset marker. | ||
| 359 | 1438156 | if (token.size() == 1 && token[0] == '|') | |
| 360 | { | ||
| 361 | 19103 | if (offset_marked) | |
| 362 | { | ||
| 363 | 45 | return PatternStatus::DuplicateOffset; | |
| 364 | } | ||
| 365 | 19101 | offset_marked = true; | |
| 366 | 19101 | sink.set_offset(sink.length()); | |
| 367 | 19101 | continue; | |
| 368 | } | ||
| 369 | |||
| 370 | // Bounded jump. | ||
| 371 | 1419053 | if (!token.empty() && token.front() == '[') | |
| 372 | { | ||
| 373 | 125308 | const JumpParse jump = parse_jump_token(token); | |
| 374 | 125308 | if (!jump.ok) | |
| 375 | { | ||
| 376 | 16 | return PatternStatus::InvalidJump; | |
| 377 | } | ||
| 378 | 125297 | if (sink.length() == 0 || sink.length() == last_boundary) | |
| 379 | { | ||
| 380 | 4 | return PatternStatus::InvalidJump; | |
| 381 | } | ||
| 382 | 125293 | if (!sink.add_jump(sink.length(), jump.min_skip, jump.max_skip)) | |
| 383 | { | ||
| 384 | 1 | return PatternStatus::TooManyJumps; | |
| 385 | } | ||
| 386 | 125292 | last_boundary = sink.length(); | |
| 387 | 125292 | continue; | |
| 388 | 125292 | } | |
| 389 | |||
| 390 | 1293745 | std::byte byte_value{0x00}; | |
| 391 | 1293745 | std::byte mask_value{0x00}; | |
| 392 | 1293745 | const bool double_wildcard = token.size() == 2 && token[0] == '?' && token[1] == '?'; | |
| 393 | 1293745 | const bool single_wildcard = token.size() == 1 && token[0] == '?'; | |
| 394 | 1293745 | if (double_wildcard || single_wildcard) | |
| 395 | { | ||
| 396 | // Full wildcard: any byte matches, so both value and mask stay zero. | ||
| 397 | } | ||
| 398 | 785492 | else if (token.size() == 2) | |
| 399 | { | ||
| 400 | 785487 | const int high = hex_digit(token[0]); | |
| 401 | 785487 | const int low = hex_digit(token[1]); | |
| 402 | 785487 | if (high >= 0 && low >= 0) | |
| 403 | { | ||
| 404 | 276232 | byte_value = static_cast<std::byte>(static_cast<unsigned char>((high << 4) | low)); | |
| 405 | 276232 | mask_value = std::byte{0xFF}; | |
| 406 | } | ||
| 407 | 509255 | else if (high >= 0 && token[1] == '?') | |
| 408 | { | ||
| 409 | 254810 | byte_value = static_cast<std::byte>(static_cast<unsigned char>(high << 4)); | |
| 410 | 254810 | mask_value = std::byte{0xF0}; | |
| 411 | } | ||
| 412 | 254445 | else if (token[0] == '?' && low >= 0) | |
| 413 | { | ||
| 414 | 254425 | byte_value = static_cast<std::byte>(static_cast<unsigned char>(low)); | |
| 415 | 254425 | mask_value = std::byte{0x0F}; | |
| 416 | } | ||
| 417 | else | ||
| 418 | { | ||
| 419 | 20 | return PatternStatus::InvalidToken; | |
| 420 | } | ||
| 421 | } | ||
| 422 | else | ||
| 423 | { | ||
| 424 | 5 | return PatternStatus::InvalidToken; | |
| 425 | } | ||
| 426 | |||
| 427 | 1293720 | if (!sink.add_byte(byte_value, mask_value)) | |
| 428 | { | ||
| 429 | 2 | return PatternStatus::TooLong; | |
| 430 | } | ||
| 431 | } | ||
| 432 | |||
| 433 | 21484 | if (sink.length() == 0) | |
| 434 | { | ||
| 435 | 6 | return PatternStatus::Empty; | |
| 436 | } | ||
| 437 | |||
| 438 | // A trailing jump, as in "48 8B [2-5]", leaves last_boundary equal to the fixed length. | ||
| 439 | 21478 | if (sink.jump_count() > 0 && last_boundary == sink.length()) | |
| 440 | { | ||
| 441 | 2 | return PatternStatus::InvalidJump; | |
| 442 | } | ||
| 443 | |||
| 444 | 21476 | return PatternStatus::Ok; | |
| 445 | } | ||
| 446 | |||
| 447 | /** @brief Parses @p dsl through @ref parse_pattern_into into scan::Pattern storage, then selects its anchor. */ | ||
| 448 | 20657 | [[nodiscard]] constexpr PatternParse parse_pattern(std::string_view dsl) noexcept | |
| 449 | { | ||
| 450 | 20657 | PatternParse result{}; | |
| 451 | 20657 | PatternBufferSink sink{}; | |
| 452 | 20657 | result.status = parse_pattern_into(dsl, sink); | |
| 453 | 20657 | if (result.status == PatternStatus::Ok) | |
| 454 | { | ||
| 455 | 20623 | result.buffer = sink.buffer; | |
| 456 | 20623 | result.buffer.anchor = select_anchor(result.buffer); | |
| 457 | } | ||
| 458 | 20657 | return result; | |
| 459 | } | ||
| 460 | |||
| 461 | /** @brief The fewest bytes any match of @p buffer can occupy: fixed bytes plus every gap's minimum skip. */ | ||
| 462 | 31 | [[nodiscard]] constexpr std::size_t min_match_length(const PatternBuffer &buffer) noexcept | |
| 463 | { | ||
| 464 | 31 | std::size_t total = buffer.length; | |
| 465 | 84 | for (std::size_t i = 0; i < buffer.jump_count; ++i) | |
| 466 | { | ||
| 467 | 53 | total += buffer.jumps[i].min_skip; | |
| 468 | } | ||
| 469 | 31 | return total; | |
| 470 | } | ||
| 471 | |||
| 472 | /** | ||
| 473 | * @brief The fewest physical bytes from the offset-applied result point through the end of any match. | ||
| 474 | * @details Only gaps after the marker position add their minimum skip. A gap at the marker position precedes the | ||
| 475 | * result point. | ||
| 476 | */ | ||
| 477 | 59 | [[nodiscard]] constexpr std::size_t min_match_suffix_length(const PatternBuffer &buffer) noexcept | |
| 478 | { | ||
| 479 | 59 | if (buffer.offset > buffer.length) | |
| 480 | { | ||
| 481 | ✗ | return 0; | |
| 482 | } | ||
| 483 | 59 | std::size_t total = buffer.length - buffer.offset; | |
| 484 | 65 | for (std::size_t i = 0; i < buffer.jump_count; ++i) | |
| 485 | { | ||
| 486 | 6 | if (buffer.jumps[i].position > buffer.offset) | |
| 487 | { | ||
| 488 | 3 | total += buffer.jumps[i].min_skip; | |
| 489 | } | ||
| 490 | } | ||
| 491 | 59 | return total; | |
| 492 | } | ||
| 493 | |||
| 494 | /** @brief The most bytes any match of @p buffer can occupy: fixed bytes plus every gap's maximum skip. */ | ||
| 495 | 4 | [[nodiscard]] constexpr std::size_t max_match_length(const PatternBuffer &buffer) noexcept | |
| 496 | { | ||
| 497 | 4 | std::size_t total = buffer.length; | |
| 498 | 22 | for (std::size_t i = 0; i < buffer.jump_count; ++i) | |
| 499 | { | ||
| 500 | 18 | total += buffer.jumps[i].max_skip; | |
| 501 | } | ||
| 502 | 4 | return total; | |
| 503 | } | ||
| 504 | |||
| 505 | /** | ||
| 506 | * @brief Masked-compares fixed bytes [@p body_begin, @p body_end) against @p window at offset @p window_pos. | ||
| 507 | * @return True when the run fits in the window and `(memory ^ pattern) & mask == 0` for every byte of the run. | ||
| 508 | */ | ||
| 509 | 131125 | [[nodiscard]] constexpr bool run_matches_at( | |
| 510 | const PatternBuffer &buffer, | ||
| 511 | std::span<const std::byte> window, | ||
| 512 | std::size_t window_pos, | ||
| 513 | std::size_t body_begin, | ||
| 514 | std::size_t body_end | ||
| 515 | ) noexcept | ||
| 516 | { | ||
| 517 | 131125 | const std::size_t run_length = body_end - body_begin; | |
| 518 | 131125 | if (window_pos > window.size() || run_length > window.size() - window_pos) | |
| 519 | { | ||
| 520 | 1 | return false; | |
| 521 | } | ||
| 522 | 131703 | for (std::size_t i = 0; i < run_length; ++i) | |
| 523 | { | ||
| 524 | const std::byte masked_diff = | ||
| 525 | 262294 | (window[window_pos + i] ^ buffer.bytes[body_begin + i]) & buffer.mask[body_begin + i]; | |
| 526 | 131147 | if (masked_diff != std::byte{0x00}) | |
| 527 | { | ||
| 528 | 130568 | return false; | |
| 529 | } | ||
| 530 | } | ||
| 531 | 556 | return true; | |
| 532 | } | ||
| 533 | |||
| 534 | /** | ||
| 535 | * @brief Tests whether segment @p segment_index and every later segment match at @p window_pos. It backtracks. | ||
| 536 | * @param steps The node-visit count for this start position. Start it at 0. See SEGMENT_MATCH_STEP_BUDGET. | ||
| 537 | * @details Recursion depth is at most MAX_PATTERN_JUMPS + 1. | ||
| 538 | */ | ||
| 539 | 131127 | [[nodiscard]] constexpr bool try_segments_at( | |
| 540 | const PatternBuffer &buffer, | ||
| 541 | std::span<const std::byte> window, | ||
| 542 | std::size_t segment_index, | ||
| 543 | std::size_t window_pos, | ||
| 544 | std::size_t &steps | ||
| 545 | ) noexcept | ||
| 546 | { | ||
| 547 | 131127 | if (++steps > SEGMENT_MATCH_STEP_BUDGET) | |
| 548 | { | ||
| 549 | 2 | return false; | |
| 550 | } | ||
| 551 | |||
| 552 | 131125 | const std::size_t segment_begin = (segment_index == 0) ? 0 : buffer.jumps[segment_index - 1].position; | |
| 553 | const std::size_t segment_end = | ||
| 554 | 131125 | (segment_index < buffer.jump_count) ? buffer.jumps[segment_index].position : buffer.length; | |
| 555 | 131125 | if (!run_matches_at(buffer, window, window_pos, segment_begin, segment_end)) | |
| 556 | { | ||
| 557 | 130569 | return false; | |
| 558 | } | ||
| 559 | 556 | if (segment_index == buffer.jump_count) | |
| 560 | { | ||
| 561 | 14 | return true; | |
| 562 | } | ||
| 563 | 542 | const std::size_t after = window_pos + (segment_end - segment_begin); | |
| 564 | 542 | const PatternJump &gap = buffer.jumps[segment_index]; | |
| 565 | 542 | const std::size_t available = window.size() - after; | |
| 566 | 131616 | for (std::size_t skip = gap.min_skip; skip <= gap.max_skip; ++skip) | |
| 567 | { | ||
| 568 | 131103 | if (skip > available) | |
| 569 | { | ||
| 570 | ✗ | break; | |
| 571 | } | ||
| 572 | 131103 | if (try_segments_at(buffer, window, segment_index + 1, after + skip, steps)) | |
| 573 | { | ||
| 574 | 13 | return true; | |
| 575 | } | ||
| 576 | 131090 | if (steps > SEGMENT_MATCH_STEP_BUDGET) | |
| 577 | { | ||
| 578 | 16 | return false; | |
| 579 | } | ||
| 580 | } | ||
| 581 | 513 | return false; | |
| 582 | } | ||
| 583 | |||
| 584 | /** | ||
| 585 | * @brief Tests whether @p buffer, bounded jumps included, matches at the start of @p window. | ||
| 586 | * @return True when a search within SEGMENT_MATCH_STEP_BUDGET finds a placement of every segment and gap that fits | ||
| 587 | * in the window and matches every masked byte. | ||
| 588 | */ | ||
| 589 | [[nodiscard]] constexpr bool | ||
| 590 | 26 | matches_buffer_at(const PatternBuffer &buffer, std::span<const std::byte> window) noexcept | |
| 591 | { | ||
| 592 | 26 | if (buffer.length == 0) | |
| 593 | { | ||
| 594 | ✗ | return false; | |
| 595 | } | ||
| 596 | 26 | if (window.size() < min_match_length(buffer)) | |
| 597 | { | ||
| 598 | 2 | return false; | |
| 599 | } | ||
| 600 | 24 | std::size_t steps = 0; | |
| 601 | 24 | return try_segments_at(buffer, window, 0, 0, steps); | |
| 602 | } | ||
| 603 | |||
| 604 | } // namespace DetourModKit::detail | ||
| 605 | |||
| 606 | #endif // DETOURMODKIT_DETAIL_PATTERN_CORE_HPP | ||
| 607 |