Lua文字列リテラルの最適化による400バイト削減

Lua文字列リテラルの最適化による400バイト削減 2026年7月2日 ゲスト投稿 これはYuki氏によるゲスト投稿で、共有されているComputerCraftのペットプロジェクトにおけるLuaコード圧縮のために使用しているトリックについて説明しています。以前、この目的のためにbzip2をどのように適応させたかについて書きましたが、この話は同じ文脈で行われる一連の話の一つです。 彼女からもっと多くの記事を読みたい場合は、こちらにAtomフィードとブログがあります。 文脈 私とガールフレンドは、CC:Tweakedのために多くのクールなプログラムを作成しました。CC:TのプログラムはLuaで書かれており、ゲーム内のコンピュータにはディスク容量が限られています。調整されていない制限は、コンピュータ（またはタートル）あたり1MBのディスク容量、フロッピーディスクあたり125KBのディスク容量です。 私たちのプログラムはそれを大幅に超えています。執筆時点では、リポジトリ内のすべてのLuaコードとそのドキュメントを連結したものは440KB強であり、これは単一のフロッピーディスクに収まらず、単純に大きすぎます。 しかし、サイズの問題に対する解決策があります。それは圧縮です。私たちのデータはLuaコードとテキストですが、主にコードです。そして、出力サイズと解凍速度の点で「最高」である圧縮アルゴリズムがいくつかあります。 私たちの目標の一つは、単一ファイル形式の自己解凍アーカイブを作成することでした。これにより、インストールはシェルで`wget https://cc.purplesyringa.moe/initrd.lua startup.lua`と入力するだけで済みます。 置換？ この偉業は、データをLuaリテラルとしてシリアライズすることを必要とします。しかし、それにはいくつかの問題があります。nil、true、false、数値、リストのシリアライズは非常に簡単です。難しいのはテーブルと文字列です。 テーブルには、識別子ベースと式ベースの2つの主要なキー表現があります。 これらのテーブルは同等です： { key = 10 } { ["key"] = 10 } 最初のものは識別子ベースのキーを使用しており、有効な識別子のみが可能で、文字列に変換されます。2番目のものはすべてを網羅するバリアントです。式ベースのキーをすべてに使用することが価値があるかどうかはベンチマークしていませんが、そうではないと感じています。 置換の最終ボスは文字列です。 どれほど難しいか？ 文字列は難しい YAMLで文字列を作成する方法が数十通りあり、それを知らない人にとっては混乱するというミームがあります。この状況は少し似ています。 Luaの文字列（特にCCで使用されているLuaランタイムであるCobaltの文字列）はバイト文字列です。Pythonの`b"meow"`よりも悪い、またはRustの`b"meow"`よりも良いです。文字列を記述するには、主に3つの方法があります： シングルクォート、1行で： 'meow'。バックスラッシュエスケープが機能します。 ダブルクォート、1行で： "meow"。バックスラッシュエスケープが機能します。 生の文字列、複数行可能： `[[meow]]` および `[=[this [[is]] a string]=]`。バックスラッシュは通常の文字として扱われます。 クォートされた文字列はクールです。文字列に改行や特殊文字が含まれていない場合、クォートされた表現はまさに最高です。おそらく、通常の見た目の文字列のほとんどをこのように記述するでしょう。しかし、生の文字列は… 生の文字列 生の文字列は `[=[`（任意の数の `=`）で始まり、`]=]`（同じ数の `=`）で終了し、その開始または終了を含んではいけません。これにより、`[=[meow [=[ mrrp]=]` は無効な文字列になりますが、`[[meow [=[ mrrp]]` は有効です。 「よし、`[=+`|`]=+` の正規表現の最長一致を見つけて、それを上回ろう」と考えるかもしれませんが、それは `[=[==[` で壊れます。 「よし、`[[\]]=*` の一致を次の文字でフィルタリングして、それを上回ろう」と考えるかもしれませんが、それは…ほとんどの場合機能します。 ただし、ニュアンスがあります。 ニュアンス？？？ テーブルキー内の生の文字列は特別で、C++11以前のC++テンプレートのようにスペースが必要です： { [ [[meow]]] = 10 } これは対処するのが最も簡単なニュアンスですが、もっとあります。 改行文字とは何ですか？ 一部の人は、それはシーケンスだとさえ言うかもしれません。Cobaltは、生の文字列で改行シーケンス（CRLF、LFCR、単一CR、単一LF）を単一LFに折りたたみます。これは、PNGに対して`dos2unix`を実行して、破損しないことを期待するようなものです。 そしてCobaltはもう一つことをします。文字列が改行で始まる場合、その改行は削除されます。最初の改行のみが影響を受けるため、これら両方が真です： print("meow" == [[ meow]]) print("\nmeow" == [[ meow]]) CRの処理 結局エスケープが必要になります。しかし、生の文字列は、バックスラッシュを特別な方法で解釈しないため、生のと呼ばれています！どうやってエスケープするのでしょうか？ それに対処するためのツールがあります。それは`gsub`です。 文字列内で使用されていない文字（テキストファイル用の` `のようなもの）がある場合、すべてのCRをこの文字に置き換えてから`gsub`を使用できます。例： print("\r\r\r" == ([[RRR]]):gsub('R','\r')) 注意：この文字を通常の文字列や`gsub`の引数として使用するため、CR自体、バックスラッシュ（通常のバックスラッシュエスケープ文字）、`^$()%.[]*+-?`（パターン文字）、シングルクォート（より読みやすいコードのために文字列境界として使用）など、一部の文字は「エスケープ」文字として禁止されています。 単純なケースは尽き、今やあらゆる種類のバイトを含むバイトシーケンスがあり、それらすべてを保持する必要があります。 それに対処する一つの方法は、CRとエスケープ文字（例：E）の両方を別のものに置き換えることです。例： `Er` CR のために `E` エスケープ文字のために このソリューションは機能しますが、文字列がほぼ均一なバイト分布を持っている場合、文字列のサイズは約1％増加します。 別の方法があります。CRが実際にあるかどうかという情報を帯域外に格納し、`gsub`で適用することができます： ([[string]]):gsub('E', (function(i) return function() i = i + 1 return bit32.btest( ('V'):byte(math.floor(i/7)), 2^(i%7) ) and '\r' end end)(6)) ここでEはエスケープ文字、Vはビット文字列です。 これらの百バイト（読みやすさのためにミニファイされていない）はトリックでパックされています： Vの最下位7ビットのみがアクセスされるため、常に最上位ビットを設定でき、特殊文字にぶつかるのを回避できます。 ` ` はCRをエスケープで置き換えるために使用されます。なぜなら、`gsub`コールバックがnilまたはfalseを返す場合、`gsub`は置換を実行しないからです。 `function(i)` は、呼び出しサイトで6に初期化されるローカル変数を生成します。 `i = 6` は、Luaの1ベースのインデックスを補償するための開始状態です。 これにより、CR/エスケープが16ビットではなく9ビット以上でエンコードされるため、CRのオーバーヘッドがほぼ半分になります。 これをもっと単純化する方法があるかもしれません。もし知っていれば教えてください。 ボーナス：Rust POV もう一つトリックがあります： `core::iter::repeat(0..7).flatten()` は、0, 1, ..., 7, 0, 1, ..., 7, 0, 1, ... のように、埋め込む必要があるビットのインデックスを生成するイテレータを作成します。これは、`% 7` と `.enumerate()` を使用するよりもクリーンに感じます。 完全な文字列シリアライズコードはここでアクセスできます。