HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

Optimizing Lua string literals to save 400 bytes (purplesyringa.moe)

19 pointsby ibobev2 コメント

要約

この記事は、ComputerCraftのような限られたディスク容量を持つ環境でLuaコードを圧縮する際の、文字列リテラルの最適化手法について解説しています。Luaの文字列表現の複雑さ、特に改行コードや特殊文字の扱いに焦点を当て、`gsub`関数とビット操作を用いた効率的なシリアライズ方法を探求しています。

全文翻訳

Lua文字列リテラルを最適化して400バイト節約する方法

2026年7月2日 ゲスト投稿 Hacker News

この記事は、Yukiによるゲスト投稿です。彼らが共有しているComputerCraftのペットプロジェクトでLuaコード圧縮のために使用しているテクニックについて説明します。以前、この目的のためにbzip2をどのように適応させたかについて書きましたが、この話はその文脈における続編です。

彼女の他の記事をもっと読みたい場合は、Atomフィードとブログをご覧ください。

7月20日更新: 生文字列のシリアライゼーションのニュアンスを修正

コンテキスト

私とガールフレンドは、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'。バックスラッシュエスケープが機能します。
  2. ダブルクォート、単一行: "meow"。バックスラッシュエスケープが機能します。
  3. 生文字列、複数行可能: [[meow]] および [=[this [[is]] a string]=]。バックスラッシュは通常の文字として扱われます。

クォートされた文字列はクールです。文字列に改行や特殊文字が含まれていない場合、クォートされた表現は単に最高です。おそらく、通常の見た目の文字列のほとんどをこのように記述するでしょう。しかし、生文字列は…

生文字列

生文字列は[=[(任意の数の=)で始まり、]=](同じ数の=)で終了し、その終端文字を含んではいけません。さらに、Lua 5.1とCobaltは、[[で始まる生文字列に[[が含まれている場合にエラーになります。

[=[meow [=[ mrrp]=] -- 有効
[[meow [=[ mrrp]] -- 有効
[[meow [[ mrrp]] -- Lua 5.1とCobaltでは禁止

「\[\[|\]=*」という正規表現の最も長いマッチを見つけて、それより長くすればよいと思うかもしれませんが、それは]=]==]で壊れます。

「\[|\=*」のマッチを次の文字でフィルタリングし、それより長くすればうまくいくと思うかもしれませんが…ほとんどの場合うまくいきます。

ただし、ニュアンスがあります。

ニュアンス???

その次の文字は「文字列の終わり」である可能性があります。例えば]で、閉じ括弧]]と一緒になると、1文字早く閉じ括弧]]を形成してしまいます。

-- 正しい
[=[]]=]
-- 間違い
[[]]]

この問題は文字列の末尾でのみ発生します。私はこのニュアンスを投稿の最初のバージョンで見落としていました。

さらに、テーブルキー内の生文字列は特別で、C++11以前のC++テンプレートのようにスペースが必要です。

{ [ [[meow]]] = 10 }

これは最も対処しやすいニュアンスですが、他にもあります。

改行文字とは何でしょうか?人によっては、それはシーケンスだとさえ言うかもしれません。Cobaltは、生文字列内の改行シーケンス(CRLF、LFCR、単一CR、単一LF)を単一のLFに折りたたみます。これは、PNGに対してdos2unixを実行して、破損しないことを期待するようなものです。

そしてCobaltはもう一つ行います。文字列が改行で始まる場合、その改行は削除されます。最初の改行のみが影響を受けるため、これら両方が真です。

print("meow" == [[ 
meow]])
print("\nmeow" == [[ 

meow]])
CRの処理

したがって、結局エスケープが必要になります。しかし、生文字列はバックスラッシュを特別に解釈しないため、生と呼ばれているのです!どうやってエスケープするのでしょうか?

そのためのツールがあり、それはgsubと呼ばれます。

文字列内で使用されていない文字(テキストファイル用の\0のようなもの)がある場合、すべてのCRをこの文字に置き換えてからgsubを使用できます。

print("\r\r\r" == ([[RRR]]):gsub('R','\r'))

通常の文字列とgsubへの引数としてその文字を使用するため、いくつかの文字は「エスケープ」文字として禁止されていることに注意してください。

  • CR自体
  • \、通常のバックスラッシュエスケープ文字
  • ^$()%.[]*+-? のいずれか(これらはパターンの特殊文字です)
  • シングルクォート(Rust側でより読みやすいコードのために文字列の境界として使用しています)

単純なケースは尽きてしまい、今やCRを含むあらゆる種類のバイトを含むバイトシーケンスがあり、これらすべてを保持する必要があります。

対処法の一つは、CRとエスケープ文字(例: E)の両方を別のものに置き換えることです。

  • Er は CR 用
  • E] はエスケープ文字自体用

このソリューションは機能しますが、文字列がほぼ均一なバイト分布を持っている場合、文字列のサイズは約1%増加します。

別の方法があります。CRが実際に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ビットのみがアクセスされるため、最上位ビットを常に設定でき、特殊文字にぶつかるのを回避できます。
  • and '\r'は、gsubコールバックがnilまたはfalseを返すとgsubが置換を実行しないため、エスケープをCRに置き換えるために使用されます。
  • 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()を使用するよりもクリーンに感じます。

完全な文字列シリアライゼーションコードはこちらでアクセスできます。