Regex 點靠 544 條搜尋取代規則，砌出一部跑到 Doom 嘅虛擬電腦

真正做緊運算嘅係規則

「用 regex 跑 Doom」聽落好似寫咗一條巨大 pattern，match 到遊戲之後畫幅圖出嚟。實際結構精密好多：開發者 Artem Lytkin 準備咗 544 條固定、排好次序嘅搜尋取代規則，driver 由頭檢查，第一條成功 match 嘅規則每次只改寫一次，跟住再由頭行過。規則喺開始前已用 SHA-256 鎖定，運行途中唔會按 Doom 狀態偷偷加新邏輯。

呢種做法屬於 iterated string rewriting，概念接近經典 Markov algorithm。只要規則可以按狀態分支，又可以反覆改寫字串，理論上已經做到通用運算。Turing complete 只代表表達能力夠，冇承諾速度合理；doom-regex 有趣嘅位，係作者真係將抽象理論砌成一部跑得郁大型程式嘅虛擬電腦，仲花大量工夫證明結果冇出蠱惑。

圖片：doom-regex 項目頁

96.6 MB 文字就係整部機

虛擬 CPU 叫 RVM-1，成個 machine state 係一串 96.6 MB 純文字。開頭 header 擺 program counter、register、clock 同運算階段，後面再分成 lookup table、平面 RAM、程式、framebuffer、WAD、高位記憶體同 I/O 區。換句話講，某個 register 入面嘅數字、牆身下一點畫咩顏色，以至 Doom 關卡資料，都只係字串入面唔同位置嘅字符。

一條規則改寫 program counter，另一條就按新地址攞 instruction；load、store、加減數同輸入輸出亦係同一套路。加法用 512 項 full-adder lookup table，八次 lookahead 逐段處理 32-bit 數值，carry 就靠 capture group 傳落去。乘除法拆成多個 micro-phase，header 入面嘅 PH 欄位記住行到邊一步。呢啲結構其實好似用文字同 pattern 手砌 microcode。

RAM 點解唔使每次掃足 96 MB

最棘手嘅部分係 memory access。每次 load 都由頭掃過近百 MB 文字，速度肯定捱唔住。作者將地址每一位變成 regex conditional jump，砌成一棵 binary tree，再按地址計出要跨過幾多字符，直接跳到 RAM slot；instruction fetch 亦用相同方法按 program counter 搵 opcode。配合 PCRE2 JIT、dotall jump、平面記憶體區同避免重複複製長字串前綴，速度先由初版每秒 7 次改寫，升到作者錄得嘅每核心約 80,000 次。

Doom 點樣變成呢串文字

作者冇逐條 regex 重寫 Doom。項目先用方便移植嘅 doomgeneric，再經修改版 8cc 將 C code 編成 ELVM IR，跟住轉成 RVM-1 明白嘅 instruction。544 條規則扮演固定 CPU，編譯後嘅 Doom 就係 CPU 要執行嘅程式資料；程式大咗主要會令 state 字串變長，規則數量唔使跟住增加。ELVM 本身正正係用簡化 IR，將 C 程式送去各種古怪語言或運算模型，呢次加個 regex CPU backend 亦相當順理成章。

呢條編譯鏈亦解釋咗點解項目有意思。好多「某某裝置跑到 Doom」其實靠串流畫面、藏起 emulator，或者只播預先生成內容。doom-regex 個 driver 當然仍然靠正常電腦同 PCRE2 JIT 搵 match，但改變 machine state 嘅算術、跳轉同記憶體操作都寫喺固定規則內；刪走 ruleset，剩低嘅 96.6 MB 文字就唔識自己行。

每幀三分鐘，數字要睇清測試條件

作者公開嘅 E1M1 timedemo 第 60 幀，要 13,994,067 次 substitution。按項目用 PCRE2 JIT 製作片段時錄得嘅速度，每個 CPU core 每秒大約做到 80,000 次改寫，計出嚟約需 175 秒，亦即接近官方所講三分鐘一幀。製作 100 幀片段就用咗約 12.5 億次改寫，production jobs 分散到五部電腦處理。呢啲數字受 CPU、PCRE2 build、JIT 同工作分配影響，唔應該當成所有電腦都會有嘅固定 benchmark；不過每一步都要等上一個 state 完成，單一執行流程始終冇得並行。

項目亦有兩層核對。作者話 Python reference emulator 會執行同一套 instruction set，每一次 substitution 之後都逐 byte 比較完整 state；畫好之後，再將 framebuffer 嘅 SHA-256 同 native build 對照。公開測試連續核對 100 幀，結果全部一致。呢套驗證比「個畫面睇落似 Doom」扎實得多，亦令項目由趣味 demo 變成一個幾完整嘅 computation model 實作。

呢個實驗證明咗咩

Regex 喺呢度冇突然變成實用 game engine，PCRE2 JIT 同現代 CPU 亦幫手做咗大量高速 pattern matching。不過項目清楚展示：CPU 本質上可以理解成一套按狀態套用、逐步改寫資料嘅規則，register、RAM 同 framebuffer 只係大家同意點樣解讀嘅編碼。對開發者嚟講，最值得睇係作者點樣處理 state layout、random access、compiler backend 同 lockstep verification；Doom 主要負責提供一個夠複雜、人人一眼認得嘅測試程式。

參考來源

• Tom's Hardware — Daring coder gets Doom running with regular expressions at 180 seconds per frame, like playing 'correspondence chess with a shotgun' — nearly 14 million substitutions to render a frame at 80,000 substitutions per second — original report
• doom-regex GitHub repository — 作者項目原始碼同技術說明，涵蓋 RVM-1、544 條規則、速度、驗證方法及授權
• DOOM on regex 互動項目頁 — 作者展示 machine state、rewrite rules、framebuffer 同運行數據嘅官方頁面
• ELVM Compiler Infrastructure — ELVM 官方項目，解釋修改版 8cc、ELVM IR 同 esoteric-language backend 編譯流程
• doomgeneric — doom-regex 採用嘅 Doom 移植層，交代 framebuffer、輸入同平台接口來源

本文根據原文及公開資料整理；資料有出入時，以原文及官方資料為準。