Credit:

• Park Jong Hwi (Wane)

TL;DR

• 기존 Pattern Scanning 알고리즘 $O(NM)$은 발전할 수 있다.
• 이는 FFT를 이용하여 $O(N\log{N})$으로 구현할 수 있다.
• 여기서 더 발전하여, $O(N\log{M})$으로 단축할 수 있다.

1. Introduction

Game Hacking에는 중요한 변수의 할당된 값을 별도의 어려운 과정 없이 구할 수 있는 강력한 기술인 Pattern Scanning (a.k.a. Array of Bytes Searching) 이 있다.

간단히 말해서 Pattern Scanning 이란, 게임 내 메모리 안에서 우리가 찾을 바이트 배열*(이하 AOB)*을 탐색하는 것이다. 여기서 일반적인 문자열 매칭과 다른 점은, Mask라는 개념이 도입된 것이다.

Mask는 AOB에서 와일드카드를 나타낸다. 즉, 무시할 index를 나타낸다. 예를 들어,

$mask = \text{\{ 0, 0, 1, 1, 0, 0, 0 \}}$

$target = \text{\{ 12, 34, 5, 6, 78, 90, 110 \}}$