この文書は、W3C 標準情報 (TR) の覚書 (NOTE)、"Generic Diff Format" <http://www.w3.org/TR/NOTE-gdiff-19970901> を ToyFish.Net が独自に翻訳したものです。この仕様書の正式なものは W3C のサイトにある英語版であり、その著作権は W3C が保有しています。また、翻訳に誤りがある可能性に留意してください。
翻訳の最終更新日: 1999 年 10 月 20 日
NOTE-GDIFF
この文書は議論のためのみに W3 Consortium が公開している NOTE です。 従って、その内容、ないし、同 Consortium が現在・過去・未来において この NOTE で示されている問題に何らかの資源を割り当てることを保証するものでは ありません。
この文書は Marimba から W3C への提案です。その意向については、 受理された W3C への提案 を参照してください。
この文書は、2 つのファイルの差異を表現するための汎用的なファイル形式の仕様を 提供します。
1. Introduction
2. The Generic Diff Format
3. Conclusion
3.1 References
この文書では、汎用 Diff 形式 (Generic Diff Format、GDIFF) について説明します。 GDIFF 形式は、任意の 2 つのファイルの差異を効率的に書き表すのに 使うことができます。この形式はファイルの種類や内容について何ら仮定を 置いていないので、テキストファイル同様にバイナリファイルの差異も記述できます。 GDIFF 形式はそれ自体がバイナリファイル形式です。
この提案書では、2 つのファイルの差異をどのように算出するかについては述べていません。 この文書が定義するのは、算出された差異を効率的かつ汎用的なやり方で記述する方法 だけです。この提案書は、GDIFF 形式とその解釈方法について述べています。
GDIFF 形式は、主に、2 つの版のファイル同士で差異を算出するアプリケーションで 有用です。算出された差異を GDIFF 形式を使ってファイルに保存することができます。 GDIFF ファイルによって記述された差異は、後で古い方のファイルに適用して 新しい版のファイルを得ることができます。
GDIFF 形式は、新しい版のファイル全体を配布するよりもそのファイルの 2 つの版の 差異を配布する方が効率的であるような状況で特に有用です。
ファイルの旧版と新版の差異を算出するのは、どんなファイル差異検出アルゴリズムでもかまいません。 一例を挙げれば、 rsync アルゴリズム があります。その結果を、ここで説明している GDIFF 形式で表現できるのです。
GDIFF ファイルを適用するには、旧版のファイルへのランダムアクセスと、GDIFF ファイルへの シーケンシャルアクセスが必要です。新しい版のファイルは出力ストリームに生成されます。
GDIFF 形式はバイナリ形式です。GDIFF ファイルの MIME タイプ は "application/gdiff" です。GDIFF ファイル中のすべてのバイナリ数値は、 ビッグエンディアン (上位バイトが最初にくる) 形式です。
それぞれの diff ストリームは 4 バイトのマジックナンバー (値 0xd1ffd1ff) で
始まり、1 バイトのバージョン番号 (値 4) が続きます。
バージョン番号の後には順番に解釈される 1 バイトのコマンドが続きます。
ストリームの最後のコマンドはファイル終端コマンド (値 0) です。
GDIFF コマンドは、次の表に上げた通りです。
| 名称 |
コマンド |
後続内容 |
動作 |
|
EOF |
0 |
|
ファイル終端 |
|
DATA |
1 |
1 バイト |
1 データバイトの追加 |
|
DATA |
2 |
2 バイト |
2 データバイトの追加 |
|
DATA |
<n> |
<n> バイト |
<n> データバイトの追加 |
|
DATA |
246 |
246 バイト |
246 データバイトの追加 |
|
DATA |
247 |
ushort、<n> バイト |
<n> データバイトの追加 |
|
DATA |
248 |
int、<n> バイト |
<n> データバイトの追加 |
|
COPY |
249 |
ushort、ubyte |
<位置> から <長さ> だけ複写 |
|
COPY |
250 |
ushort、ushort |
<位置> から <長さ> だけ複写 |
|
COPY |
251 |
ushort、int |
<位置> から <長さ> だけ複写 |
|
COPY |
252 |
int、ubyte |
<位置> から <長さ> だけ複写 |
|
COPY |
253 |
int、ushort |
<位置> から <長さ> だけ複写 |
|
COPY |
254 |
int、int |
<位置> から <長さ> だけ複写 |
|
COPY |
255 |
long、int |
<位置> から <長さ> だけ複写 |
GDIFF コマンドには 2 種類あります。最初の種類は、DATA コマンド (1〜248) です。 各データコマンドに、出力ストリームに複写される、ある数のデータバイトが続きます。
もう一方の種類の GDIFF コマンドは、COPY コマンド (249〜255) です。 各 COPY コマンドに、2 つの引数、位置と長さが続きます。この引数は、旧版のファイルのうち 出力ストリームに複写しなければならない部分を示します。
int の引数のみをとるコマンドで 1^31-1 バイトよりも大きな数が
必要な場合は、そのコマンドは複数のコマンドに分割されなければなりません。
これは非常に大きなファイルを扱う場合に必要になることがあります。
GDIFF 形式の使い方を例示するために、旧および新という 2 つの 入力ストリームを使い、手でシンプルな GDIFF ファイルを作成して見ることにしましょう。
0 1 2 3 4 5 6 7 8 9
----------------------------------------------
旧: A B C D E F G
新: A B X Y C D B C D E
|
diff アルゴリズムは新旧のファイルに共通して現れるパターンを発見でき、 GDIFF コマンドの組は次のように算出できます。
| 説明 | GDIFF | 出力 |
magic version COPY 0, 2 DATA "XY" COPY 2, 2 COPY 1, 4 EOF |
0xd1, 0xff, 0xd1, 0xff 4 249, 0, 0, 2 2, 'X', 'Y' 249, 0, 2, 2 249, 0, 1, 4 0 |
A, B X, Y C, D B, C, D, E |
この場合では結果の GDIFF ファイルが新しいファイルより大きいことに注意してください。 ファイルが大きくなる場合には、こうなることは通常ありません。 また、同じ結果になる GDIFF ファイルが何種類もあることにも注意してください。 作成された GDIFF ファイルのサイズは、おおまかに言って、2 つの入力ファイルが どれくらい似ているかと、最適な差異の組を見つける diff アルゴリズムの能力によります。
GDIFF 形式は、あらゆる種類の 2 つのファイル同士の差異を効率的に記述できる シンプルな diff 形式です。GDIFF 形式は、バイナリの差異検出についての シンプルな相互互換の形式を提供するために、この提案書で定義されたものです。