DOOM을 정규 표현으로 직접 다시 쓰지 않았다. 정규 표현 기반 검색과 치환만으로 작동하는 경량의 32비트 가상 CPU “RVM-1”을 만들고, 그 가상 CPU에서 DOOM을 실행하고 있다. DOOM 본체는, 이식하기 쉬운 형태로 정리된 구현체인 doomgeneric을 C 컴파일러 8cc와 ELVM을 사용하여 RVM-1의 명령어열로 변환한 것이다.
다음 GIF 애니메이션에서는 왼쪽에서 DOOM 화면 1 프레임이 렌더링되고, 오른쪽에서는 실행 중인 치환 규칙이 흘러나간다. 왼쪽에서 밝게 빛나는 초록색은 그 시점의 치환에 의해 쓰여지고 있는 픽셀이다. 벽은 가로 1열씩, 바닥은 세로 방향의 덩어리씩 칠해지고, 붓이 멈춰있는 동안은 BSP 트리를 따라가 다음 그릴 대상(target)을 결정한다.
정규 표현 기반 치환을 반복하는 메커니즘은 고전적인 계산 모델 중 하나인 마르코프 알고리즘 자체이며, 이론적으로는 일반적인 컴퓨터와 같은 종류의 계산을 실행할 수 있는 “튜링 완전”한 메커니즘이다. 따라서 정규 표현만으로 DOOM을 실행할 수 있는 것은 본래 가능한 것이었다고 리틴 경은 주장한다. 실제로 물어볼 가치가 있었던 것은 우주가 열적 죽음을 맞이하기 전에 움직일 수 있는지, 그리고 중간에 속임수를 쓰고 있지 않은지 증명하는 두 가지였다고 리틴 경은 말했다.
가상 컴퓨터의 상태는 약 96.6MB에 달하는 하나의 거대한 문자열로 저장된다. 이 문자열에는 CPU 레지스터, RAM, 실행하는 프로그램, 화면을 유지하는 프레임 버퍼, DOOM의 게임 엔진, 스테이지와 그래픽 등을 담은 WAD 데이터, 입출력 영역 등이 모두 평문으로 저장되어 있다.
실행 시에는, 드라이버가 544개의 정규 표현 기반 치환 규칙을 정해진 순서대로 반복적으로 확인한다. 그 시점에서 처음으로 조건이 일치한 규칙을 1회만 적용하고, 문자열의 일부를 다른 문자로 대체하는 것이 가상 컴퓨터의 1단계에 해당한다. 규칙을 삭제하면 남는 것은 동작하지 않는 거대한 텍스트 파일뿐이다. 계산이나 명령어 해석을 외부 프로그램에 맡기고 있지 않다고 리틴 경은 설명한다.
예를 들어, 가상 CPU가 숫자를 더하는 경우, 512 항목으로 구성된 덧셈용 표를 정규 표현으로 참조하고, 자리올림을 이어가며 계산한다. 메모리 접근에서는, 주소를 구성하는 각 비트(bit)에 따라 점프 거리를 조립하고, 이진 트리와 같은 메커니즘으로 약 96.6MB의 문자열 내에 있는 목적의 위치로 직접 이동한다. 문자열 전체를 매번 처음부터 검색하지 않음으로써 처리 시간을 단축한다.
다음 이미지에서 초록색으로 표시된 부분은 정규 표현 기반 치환 처리 중 현재 갱신되고 있는 픽셀이다. 화면은 한 번에 생성되는 것이 아니라, 벽이나 바닥과 같은 영역이 조금씩 그려진다.
그리고 다음과 같이 가상 CPU를 작동시키는 정규 표현 규칙이 나열되어 있으며, “fetch”나 “mov”와 같은 처리들이 치환 규칙으로 재현된다.
초기 동작 시 웠동한 버전의 처리 속도는 매초 7회에 불과한 수준이었으며, 1프레임 내에서 마지막 29만 5천 회의 치환을 처리하는 데만도 12시간이 소요되었습니다. 이후 주소의 각 자릿수를 따라 목적 지점으로 직접 점프하는 방식 도입, 메모리 영역의 플랫화, 치환해도 변하지 않는 긴 앞부분 부분을 복사하지 않는 등의 노력을 통해 PCRE2의 JIT 컴파일을 활성화하면서 처리 속도는 1코어당 매초 약 8만 회까지 개선되었습니다. 약 1399만 회의 치환 처리를 거쳐 완성된 DOOM의 1프레임은, 이는 DOOM의 첫 번째 스테이지인 “E1M1”의 타임 데모의 60번째 프레임에 해당하며, 리트킨 씨에 따르면 일반적인 DOOM이 묘각한 동일한 프레임과 바이트 단위로 일치하고, SHA-256의 해시 값도 일치했습니다. 더 나아가, 1프레임만으로는 맹목적인 가능성이 있을 수 있다고 판단하여, 동일한 타임 데모의 160번째 프레임부터 259번째 프레임까지 100프레임을 계산했으며, 약 12억 5천만 회의 치환을 소비한 후 100프레임 모두가 일반적인 DOOM과 바이트 단위로 일치했다고 주장했습니다.
최종적인 계산은 5대의 머신에 분산되어 실행되어 약 3분에 1프레임이 생성됩니다. 일반적인 게임이 1초에 수십 프레임을 표시하는 것을 고려했을 때 극단적으로 느리지만, 리트킨 씨이 작동감에 대해 “반사 신경이 요구되는 슈팅 게임이라기보다는 샷건을 사용한 폰트 앤 체스와 유사하다”고 설명합니다. Windows용으로는 실제 정규 표현 머신을 실행할 수 있는 데모도 공개되었습니다. WASD 키 또는 방향 키로 이동하고, Ctrl 키로 사격하고, Space 키로 문을 열 수 있으며, 입력 내용은 파일에 기록된 후, 가상 CPU의 입출력 명령을 통해 DOOM으로 전달됩니다. 데모 화면에서는 DOOM의 렌더링과 함께 어떤 치환 규칙이 실행되고, 무엇을 읽고, 어떤 문자를 썼는지도 실시간으로 확인할 수 있습니다. , 리트킨 씨정확하게 동작하고 있음을 보장하기 위해 동일한 명령어 세트를 Python으로 구현한 레퍼런스 에뮬레이터를 준비하고, 1회 치환할 때마다 문자열이 에뮬레이터의 상태와 바이트 단위로 일치하는지 테스트로 검증하고 있습니다. 리트킨 씨、고정된 정규 표현 규칙을 순환적으로 적용하고, DOOM과 같은 게임이나 영상을 동작시킨 기존의 예시는 입니다. DOOM on regex는 소스 코드가 GitHub에 공개되어 있으며, 데모도 출시되었습니다.
원문 보기 | 출처: Gigazine