HN 日本語サマリー

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

Constrained Programmingで遊ぶ

Fun with Constrained Programming (blog.cmpxchg8b.com)

84 pointsby colejohnson664 コメント

要約

RARアーカイブファイルには、圧縮率を高めるためのデータ変換を行うフィルタ(プリプロセッサ)として機能する、RarVMと呼ばれるシンプルなx86風仮想マシンのバイトコードが含まれることがあります。この記事では、このRarVMの機能を探求し、独自のフィルタを作成するためのツールチェーンとドキュメントを公開しています。特に、WinRARのCRCチェックを回避するために動的なCRC補正アルゴリズムをRarVM上で実装した例を紹介しています。

全文翻訳

信じられないかもしれませんが、RARファイルにはRarVMと呼ばれるシンプルなx86風仮想マシンのバイトコードが含まれることがあります。これは、冗長性を高めて圧縮率を向上させるために、入力データに可逆変換を行うフィルタ(プリプロセッサ)を提供するように設計されています。

例えば、「Intel E8 preprocessing」と呼ばれるフィルタは、x86コードの冗長性を高めるように設計されています(これは、同様の機能を持つ以前のスキームであるLZXに触発されたものと思われます)。

次のようなプログラムを想像してみてください。

mov    foo, bar

cmp    bar, baz

push    foo

**call    write**

push    bar

**call    write**

2つのcall命令は、分岐位置からの相対アドレスであるため、同じ命令でも2つの異なるエンコーディングになります。圧縮時には、これらを絶対アドレスに変換できます。これにより、同じ命令が2回出現するため、より効率的に圧縮できます。アーカイブが解凍されると、この変換は元に戻され、元の状態が復元されます。

WinRARには約1ダースの標準フィルタが含まれており、いくつかの一般的な入力の圧縮を改善しますが、驚くべきことに、アーカイブによって実行時に新しいフィルタを定義することも可能です!

私の知る限り、この機能を探求するためのツールは存在しません。これはあまりにも魅力的すぎるため、私はいくつかを作成しました。これまでのところ、RARツールチェーンと、プログラムの書き方に関するドキュメントが完成しています。

コードといくつかのサンプルプログラムはgithubで確認できます:https://github.com/taviso/rarvmtools。

> $ **cat helloworld.rs**
> #include <constants.rh>
> #include <util .rh>
> ; vim: syntax=fasm
> ; Test RAR assembly file.
> \_start:
>     ; Install our message in the output buffer
>     mov     r3, #0x1000                 ; Output buffer.
>     mov     [r3+#0], #0x6c6c6548        ; 'lleH'
>     mov     [r3+#4], #0x57202c6f        ; 'W ,o'
>     mov     [r3+#8], #0x646c726f        ; 'dlro'
>     mov     [r3+#12], #0x00000a21       ; '!\n'
>     mov     [VMADDR_NEWBLOCKPOS],  r3   ; Pointer
>     mov     [VMADDR_NEWBLOCKSIZE], #14  ; Size
>     call    $\_success
> $ **make helloworld.rar**
> cpp -I../stdlib < helloworld.rs > helloworld.ri
> ../raras -o helloworld.ro helloworld.ri
> ../rarld helloworld.ro > helloworld.rar
> rm helloworld.ri helloworld.ro
> $ **unrar p -inul helloworld.rar**
> Hello, World!

現時点では、ツールチェーンは最小限のリンカとアセンブラで構成されています。コンパイラ(LLVMバックエンドやGCCターゲットなど)を移植することも考えていますが、そこまで狂っているかはわかりません。


言うまでもなく、WinRARのようなものをプログラムするのは興味深い課題ですが、それが広く普及しているという事実は、楽しい可能性を秘めています。以下にアーキテクチャの概要を示します。

x86(できればIntelアセンブリ構文)に精通していると有利です。VMは明らかにx86に触発されているからです。r0からr7と呼ばれる8つの名前付きレジスタがあります。

r7は、スタック関連の操作(push、call、popなど)に使用され、スタックポインタとして機能し、下方に成長します。RarVMフィルタは最大250,000,000命令実行できますが、それを超えると終了します。ただし、ファイルに含まれるフィルタの数に制限はないため、タスクを複数の250Mサイクルチャンクに分割するだけです。命令ポインタがコードセグメントの外に出た場合、プログラムは正常に完了したと見なされます。

フィルタは0x40000バイトのアドレス空間を持ち、3つのステータスフラグ(ZF(ゼロ)、CF(キャリー)、SF(サイン))にアクセスできます。これらは、条件分岐命令またはpushf/popf(x86と同様)を介してアクセスできます。

サポートされているオペランドタイプは次のとおりです。

  • レジスタ(r0、r1、...、r7)
  • メモリ参照([#0x12345])
  • レジスタ間接参照([r0])
  • ベース+インデックス間接参照([r4+#0x1234])
  • 即値(#0x12312)

便宜上、アセンブラはシンボリック参照もサポートしており、これらはコンパイル時に即値に解決されます。先頭に$を付けます。

  • シンボリック参照(jnz $next_loop)

Intelのようなメモリ参照の数に制限はないため、これは合法です。

> mov [r0+#0x1234], [r7-#12]

RARプログラムは、独自の初期レジスタ値を提供するか、いくつかのステータス情報を含むデフォルトセットを使用できます。独自のレジスタを指定しない場合、これらが設定されます。

  • r3: グローバルメモリバッファのアドレス
  • r4: フィルタブロック長
  • r5: フィルタ実行カウント
  • r7: アドレス空間のトップ(したがってスタックは下方に成長します)。
動的出力

ここからが面白い部分です。RARはアーカイブユーティリティでありプログラミング環境ではないため、WinRARのWindowsバージョンでは、プログラムの出力がボリュームヘッダーに格納されているCRCと一致する必要があります...痛いですね。

[画像]

これは通常、コンパイル時に出力が予測できないプログラムを書くことができないことを意味し、面白みに欠けます。しかし、簡単に諦める必要はありません。

Julienは動的なCRC補正アルゴリズム(フランス語ですが、コードは理解できます)に関する論文を書きました。私は彼のアルゴリズムをRarVMに移植したので、動的出力を生成し、固定CRCに一致するように自身の出力を実行時に補正できる、自己ホスト型のRARファイルが作成できるようになりました。

はい、これはかなり馬鹿げています。

以下はCRC補正コードの一部です。

; バッファの最初の7バイト内のいくつかのバイトを変更して、CRC32を指定された値に一致させます。このプロセス用にバッファの最初の数バイトを予約する必要があります。
; 元の実装はJulien Tinnesの論文に基づいています。
\_compensate\_crc:
        ; [r6+#16]  target     // 望ましいCRC値。
        ; [r6+#12]  length     // バッファのサイズ。
        ; [r6+#8]   buffer     // 補正するバッファへのポインタ。
        ; [r6+#4]   r
        ; [r6+#0]   s
        ; [r6-#4]   modlen     // Length % 4
        push    r6                          ; フレームポインタを保存
        mov     r6, r7                      ; 新しいフレームを作成
        sub     r7, #4                      ; 変数を割り当て
        push    [r6+#12]                    ; 長さ
        push    [r6+#8]                     ; バッファ
        call    $\_crc\_block                 ; \_crc\_block(buffer, length)
        xor     [r6+#16], r0                ; target ^= currentcrc
        push    #4                          ; 除数
        push    [r6+#12]                    ; 長さ
        call    $\_mod                       ; \_mod(length, 4)
        mov     [r6-#4], r0                 ; この計算を保存
        sub     [r6+#12], [r6-#4]           ; length -= modlen
        div     [r6+#12], #4                ; 4で割る
        sub     [r6+#12], #1                ; \_find\_vector\_x の行を計算
        push    [r6+#12]                    ; 行
        push    [r6+#16]                    ; target
        call    $\_find\_vector\_x             ; \_find\_vector\_x(target, row)
        push    r0                          ; 値
        call    $\_bswap                     ; 結果をバイトスワップ
        add     [r6+#8], [r6-#4]            ; 変更するオフセットを計算
        mov     r1, [r6+#8]                 ; アドレスをロード
        xor     [r1], r0                    ; CRCを補正
        xor     r0, r0                      ; リターンコード
        mov     r7, r6                      ; フレームをクリア
        pop     r6
        ret

そして結果は以下の通りです。

> $ **cat sample.rs** 

#include

#include

#include

#include

; vim: syntax=fasm

; Test RAR assembly file that just demonstrates the syntax.

\_start:

    ; Install our message in the output buffer

    mov     r3,       #0x1000            ; Output buffer.

    mov     [r3+#0],  #0x41414141        ; Padding for compensation

    mov     [r3+#4],  #0x0a414141        ; Padding for compensation

    mov     [r3+#8],  #0x6c6c6548        ; 'lleH'

    mov     [r3+#12], #0x57202c6f        ; 'W ,o'

    mov     [r3+#16], #0x646c726f        ; 'dlro'

    mov     [r3+#20], #0x00000a21        ; '!\n'

    mov     [VMADDR_NEWBLOCKPOS],  #0x00001000

    mov     [VMADDR_NEWBLOCKSIZE], #22

    ; Compensate to required CRC

    push    RAR_FILECRC

    push    [VMADDR_NEWBLOCKSIZE]

    push    [VMADDR_NEWBLOCKPOS]

    call    $\_compensate\_crc

    test    r0, r0

    jz      $finished

    call    $\_error
finished:

    call    $\_success

$ **make sample.rar**

cpp -Istdlib < sample.rs > sample.ri

./raras -o sample.ro sample.ri

./rarld sample.ro > sample.rar

rm sample.ri sample.ro

$ **unrar p -idq sample.rar** 

AAc��!A

Hello, World!

[[画像]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLRicEwTMUGoYGceggrQpRFbrR18yK3_U9Su4_4nePfCABKvKP2A7qs0xoSk-g9UtTNID3T5nIJgleyddsxOZOIKinRtbACciL9Ed-1k9oWHSR9RBYtHtqkiTGxH12bdRXRquT9XLXTPQ/s1600/Windows+7+x64+@+2012-09-29+00:12:24.png)

#### 結論。

これはすべてかなり役に立ちませんが、それが楽しい理由です :-)