シンプルなファイルアーカイブフォーマットの設計と実装

こんにちは、久しぶりの投稿となります。

今回は、シンプルな構造で実装が容易なファイルアーカイブフォーマットについて設計と実装を行ったので、その備忘録となります。

背景

だいぶ昔、バイナリファイルを扱うウェブアプリを作成したのですが、ちまちま改良していくうちに、ロードした複数のファイルをひとつにまとめたい場面に遭遇しました。

普通であれば、既存の外部ライブラリ (JSZIP など) を使えば解決なのですが、そのウェブアプリは、小規模ながら暗号ファイルを扱うため、あまり外部ライブラリは使いたくありませんでした。

そこで、コンパクトで全ての処理を把握でき、かつ標準ビルトイン機能のみで完結する、シンプルなアーカイブを実装しよう、と考えたのがきっかけです。

参考にしたもの

とは言っても、右も左も分からない状態からスタートだったので、まずは手始めに、巷で有名なファイルアーカイブの構造を調べることにしました。

無難なところで、ファイルアーカイブの大先輩である tar に狙いを定めました。

Tarの特徴は歴史の古さで、まだハードディスクなどが無い時代から存在しており、その名前の由来となったテープドライブとの親和性を求めたフォーマットとなります。

ゆえに、固定長ブロック構造を持つテープドライブに則り 512 bytes/block というブロック単位での操作を前提とした作りになっています。

設計

まず、今回のファイルアーカイブフォーマットはどのような要件を満たしたいのかを、ざっくり洗い出してみます。

• ウェブアプリでの使用を想定
• 実装は JavaScript/TypeScript
• ソースコードはシングルファイルに収まる程度の規模
• 外部ライブラリへ依存しない

こんな感じでしょうか。

今回の大前提は「全てを見渡せる実装」なので、なるべくシンプルに、手の内へ収まる規模で、外部ライブラリは使用しないことが絶対条件となります。

ざっと tar のバイナリ構造を見た感じ、実装は何とかなりそうだったので、ベースは tar に決定しました。

簡略化

今回、想定する使用環境はウェブアプリに限られるため、いくつかの事項は tar から大幅に簡略化できそうです。

ブロック操作

現代のコンピュータにおいては当たり前ですが、記憶装置のハードウェア都合によりブロック単位での操作が必須、というシーンは少ないと思います。

今回も当然、ブロックを意識する必要はないため、任意の可変長なフォーマットとします。

ファイルヘッダ

ウェブアプリにおいて、ファイルの入出力は File API や Anchor:download属性 を使用しなければならず、それらの API を経由することで、大半のメタデータは削ぎ落とされてしまいます。

参照できるのは「ファイルサイズ」「ファイル名」「MIMEタイプ」「最終更新日時」くらいで、設定できるのは実質的に「ファイル名」のみです。

このように、そもそも扱える項目が少ないため、ファイルヘッダに記述する内容は、必要最低限の「ファイルサイズ」「ハッシュ値」「ファイル名」で充分となります。

ちなみに、メタデータが大きく制限される理由は簡単で、あまり多くのメタデータを扱えてしまうと脆弱性に繋がりかねない、というセキュリティ上の懸念があるためです。

誤り検出

オリジナルの tar は、誤り検出にチェックサムを使用しています。

しかし、ウェブブラウザで暗号機能を扱える WebCrypto API には、そんな大昔の脆弱なアルゴリズムを搭載しているはずもありません。

ここはイマドキらしく SHA2 でハッシュ値を取りたいと思います。

ディレクトリ

ウェブブラウザのファイルシステムにおいて、ディレクトリという概念は存在しないため、単純にファイルのみを格納する単層構造として設計します。

圧縮

圧縮機能についても、フォーマットへ内包する必要はないと判断したため、省略します。

なぜなら、最終的に出力されるバイナリへ対して任意の圧縮機構を通せばよく、それはフォーマットが関与しない外側で発生する処理だからです。

ちょうど tar と gzip のようなイメージです。

バイナリ構造

ファイルアーカイブとして機能させるには、ファイル個数ぶん存在するファイルヘッダと本体を列挙し、最終的にひとつのバイナリへ結合させる必要があります。

その列挙方法について、いくつかのパターンを考えていきます。

パターン1:分離

先にファイルヘッダのみを列挙し、その後に本体を列挙する方法です。

この方法のメリットは、バイナリの先頭から固定長データが続くため、単純に人間が理解しやすい、というのがあります。

一方でデメリットは、ファイルヘッダ用と本体用で2系統のループもしくはオフセットカウンタを用意しなければならないため、実装が少し複雑になります。

パターン2:ペア

ファイルヘッダと本体をペアにして列挙する方法です。

メリットとデメリットは、そのまま パターン1 と真逆になります。

ファイルヘッダの直後には必ず本体が存在するため、ループもしくはオフセットカウンタは1系統で足りますが、2ファイル目以降のファイルヘッダ位置は前ファイルの本体サイズにより変動するため、視認性は悪くなります。

今回は、実装のシンプルさを優先したいので、処理が少ない パターン2 を採用しようと思います。

仕様

最終的なフォーマットの仕様は以下とします。

項目	値
圧縮	非対応
ディレクトリ	非対応
誤り検出	SHA-512
ファイル容量	4GB / ファイル
ファイル名	半角256文字 / ファイル

バイトシーケンス

項目	bytes
Header (File 1)	324
Body (File 1)	*
Header (File 2)	324
Body (File 2)	*
...	...
Header (File n)	324
Body (File n)	*

バイトシーケンス(Header内訳)

|項目|bytes|
|:--|--:|--:|
|FileSize|4|
|HashValue|64|
|FileName|256|

実装

決定した仕様をもとに、実際のコードへ落とし込みます。

完成したものがこちら。

archive.ts

const FileHeader = {
    Size: 4,
    Hash: 64,
    Name: 256
} as const;

function bufferEqual(source1:BufferSource, source2:BufferSource){
    const dv1 = new DataView(source1 instanceof ArrayBuffer ? source1 : source1.buffer);
    const dv2 = new DataView(source2 instanceof ArrayBuffer ? source2 : source2.buffer);

    return dv1.byteLength !== dv2.byteLength || new Array(dv1.byteLength).fill(null).every((_, i) => dv1.getUint8(i) === dv2.getUint8(i));
}

async function deriveHash(data:BufferSource){
    return crypto.subtle.digest("SHA-512", data);
}

function byteSetQuad(n:number){
    const dv = new DataView(new ArrayBuffer(4));
    dv.setUint32(0, n);

    return dv.buffer;
}

function byteGetQuad(b:ArrayBuffer){
    return new DataView(b).getUint32(0);
}

async function archiveEncode(files:File[]){
    if(files.some(({size, name: {length}}) => size > (0x100 ** FileHeader.Size) || length > FileHeader.Name)){
        throw "File name or file size is too large.";
    }

    const archive = new Uint8Array(Object.values(FileHeader).reduce((a, b) => a + b, 0) * files.length + files.reduce((a, {size}) => a + size, 0));

    let offset:number = 0;
    for(const file of files){
        const data = await file.arrayBuffer();

        archive.set(new Uint8Array(byteSetQuad(file.size)), offset);
        offset += FileHeader.Size;
        archive.set(new Uint8Array(await deriveHash(data)), offset);
        offset += FileHeader.Hash
        archive.set(new TextEncoder().encode(file.name), offset);
        offset += FileHeader.Name
        archive.set(new Uint8Array(data), offset);
        offset += file.size;
    }

    return archive.buffer;
}

async function archiveDecode(archive:ArrayBuffer){
    const files:File[] = [];

    let offset:number = 0;
    while(offset < archive.byteLength){
        const size = byteGetQuad(archive.slice(offset, offset += FileHeader.Size));
        const hash = archive.slice(offset, offset += FileHeader.Hash);
        const name = new TextDecoder().decode(archive.slice(offset, offset += FileHeader.Name)).replace(/\0+$/, "");
        const data = archive.slice(offset, offset += size);

        if(!bufferEqual(hash, await deriveHash(data))){
            throw "Hash values does not match.";
        }

        files.push(new File([data], name));
    }

    return files;
}

コードはたったのこれだけ。
かなりシンプルにできたと思います。

重要なのは archiveEncode() と archiveDecode() のみで、後はユーティリティ的なメソッドなので、コア部分だけクローズアップしてみます。

エンコード

async function archiveEncode(files:File[]){
    // 入力されたファイルのサイズとファイル名がヘッダに収まるか
    if(files.some(({size, name: {length}}) => size > (0x100 ** FileHeader.Size) || length > FileHeader.Name)){
        throw "File name or file size is too large.";
    }

    // ArrayBufferは固定長のため、先に全長を計算してアロケーション
    const archive = new Uint8Array(Object.values(FileHeader).reduce((a, b) => a + b, 0) * files.length + files.reduce((a, {size}) => a + size, 0));

    // ファイル個数ぶん繰り返す
    // 何バイト目まで書き込んだかを保持する
    let offset:number = 0;
    for(const file of files){
        const data = await file.arrayBuffer();

        // ファイルサイズを書き込み
        archive.set(new Uint8Array(byteSetQuad(file.size)), offset);
        offset += FileHeader.Size;

        // ハッシュ値を書き込み
        archive.set(new Uint8Array(await deriveHash(data)), offset);
        offset += FileHeader.Hash

        // ファイル名を書き込み
        archive.set(new TextEncoder().encode(file.name), offset);
        offset += FileHeader.Name

        // 本体を書き込み
        archive.set(new Uint8Array(data), offset);
        offset += file.size;
    }

    return archive.buffer;
}

エンコードはとても簡単です。

先に総サイズを計算してバッファ領域を確保した後、ファイル個数ぶんのループでファイルヘッダと本体を順番にバッファへ書き込むだけです。

上述の通り、もし圧縮したければ、ここで出力された ArrayBuffer に対して CompressionStreams API などを通すことで実現可能です。

その場合は、当然ですがデコードの前に伸張してやる必要があります。

デコード

async function archiveDecode(archive:ArrayBuffer){
    // ファイルが何個格納されているか不明なため、可変長配列に追加していく
    const files:File[] = [];

    // 読み込んだバイト数と入力されたバッファのバイト数が同じになるまで繰り返す
    // 1ループでちょうど1ファイルぶんのバイト数を読み進める
    // 何バイト目まで読み込んだかを保持する
    let offset:number = 0;
    while(offset < archive.byteLength){
        // ファイルサイズを読み込み
        const size = byteGetQuad(archive.slice(offset, offset += FileHeader.Size));

        // ハッシュ値を読み込み
        const hash = archive.slice(offset, offset += FileHeader.Hash);

        // ファイル名を読み込み
        const name = new TextDecoder().decode(archive.slice(offset, offset += FileHeader.Name)).replace(/\0+$/, "");

        // 本体を読み込み
        const data = archive.slice(offset, offset += size);

        // エンコード時とデコード時のハッシュ値を比較
        if(!bufferEqual(hash, await deriveHash(data))){
            throw "Hash values does not match.";
        }

        files.push(new File([data], name));
    }

    return files;
}

デコードはひと手間が加わります。

入力されたアーカイブは、格納されているファイル個数が最初から分からないためです。

そこで、まずは位置が確定している最初のファイルヘッダを読み込み、そこからファイルサイズを割り出して本体を読み込み、更にその直後に存在するファイルヘッダを読み込み...という流れを繰り返します。

最終的に、読み込んだバイト数と入力されたアーカイブのサイズが一致していれば、全てのファイルを読み込めたことになります。

実際に使用する

このようなHTMLを作り、簡単な動作検証を行いました。

archive.html

<html>
    <body>
        <input multiple type="file" id="files"></input>
    </body>

    <script async type="module">
        // archive.ts (JavaScriptトランスパイル)

        document.getElementById("files").addEventListener("change", async({target: {files}})=>{
            const encode = await archiveEncode(Array.from(files));
            const decode = await archiveDecode(encode);

            console.log(encode);
            console.log(decode);
        });
    </script>
</html>

検証環境

• Microsoft Windows 7 32bit
• Google Chrome 97 32bit

結果

無事に動きました。

まとめ

ファイルアーカイブは、大昔から現在まで多岐に渡る仕様や実装が存在しており、普段お目に掛からない日は無いほどに恩恵を賜っています。

が、その中身がどうなっているのかについては、これまでほとんど意識してきませんでした。

今回は、その中身について初めて読み解き、簡単ではありますが実際に設計してこの手で実装したことにより、少しだけ新しい世界が広がったように感じました。

今回色々と調べていくうちに、ファイルアーカイブについて興味が湧いてきたので、また何か作るかもしれません。

それではまた。