RFC3284 日本語訳
3284 The VCDIFF Generic Differencing and Compression Data Format. D.Korn, J. MacDonald, J. Mogul, K. Vo. June 2002. (Format: TXT=64035 bytes) (Status: PROPOSED STANDARD)
プログラムでの自動翻訳です。
英語原文
Network Working Group D. Korn
Request for Comments: 3284 AT&T Labs
Category: Standards Track J. MacDonald
UC Berkeley
J. Mogul
Hewlett-Packard Company
K. Vo
AT&T Labs
June 2002
コメントを求めるワーキンググループD.コルンの要求をネットワークでつないでください: 3284年のAT&T研究室カテゴリ: 標準化過程J.マクドナルドUCバークレーJ.要人ヒューレット・パッカード会社K.Vo AT&T研究室2002年6月
The VCDIFF Generic Differencing and Compression Data Format
VCDIFFジェネリックDifferencingと圧縮データの形式
Status of this Memo
このMemoの状態
This document specifies an Internet standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited.
このドキュメントは、インターネットコミュニティにインターネット標準化過程プロトコルを指定して、改良のために議論と提案を要求します。 このプロトコルの標準化状態と状態への「インターネット公式プロトコル標準」(STD1)の現行版を参照してください。 このメモの分配は無制限です。
Copyright Notice
版権情報
Copyright (C) The Internet Society (2002). All Rights Reserved.
Copyright(C)インターネット協会(2002)。 All rights reserved。
Abstract
要約
This memo describes VCDIFF, a general, efficient and portable data format suitable for encoding compressed and/or differencing data so that they can be easily transported among computers.
このメモはVCDIFF(コンピュータの中で容易にそれらを輸送できるように圧縮される、そして/または、データをdifferencingするコード化に適当な一般的で、効率的で携帯用のデータの形式)について説明します。
Korn, et. al. Standards Track [Page 1] RFC 3284 VCDIFF June 2002
etコルン、アル。 規格はVCDIFF2002年6月にRFC3284を追跡します[1ページ]。
Table of Contents
目次
1. Executive Summary ........................................... 2
2. Conventions ................................................. 4
3. Delta Instructions .......................................... 5
4. Delta File Organization ..................................... 6
5. Delta Instruction Encoding .................................. 12
6. Decoding a Target Window .................................... 20
7. Application-Defined Code Tables ............................. 21
8. Performance ................................................. 22
9. Further Issues .............................................. 24
10. Summary ..................................................... 25
11. Acknowledgements ............................................ 25
12. Security Considerations ..................................... 25
13. Source Code Availability .................................... 25
14. Intellectual Property Rights ................................ 26
15. IANA Considerations ......................................... 26
16. References .................................................. 26
17. Authors' Addresses .......................................... 28
18. Full Copyright Statement .................................... 29
1. 要約… 2 2. コンベンション… 4 3. デルタ指示… 5 4. デルタファイル編成… 6 5. デルタ指示コード化… 12 6. 目標ウィンドウを解読します… 20 7. アプリケーションで定義されたコードテーブル… 21 8. パフォーマンス… 22 9. さらなる問題… 24 10. 概要… 25 11. 承認… 25 12. セキュリティ問題… 25 13. ソースコードの有用性… 25 14. 知的所有権はまっすぐになります… 26 15. IANA問題… 26 16. 参照… 26 17. 作者のアドレス… 28 18. 完全な著作権宣言文… 29
1. Executive Summary
1. 要約
Compression and differencing techniques can greatly improve storage and transmission of files and file versions. Since files are often transported across machines with distinct architectures and performance characteristics, such data should be encoded in a form that is portable and can be decoded with little or no knowledge of the encoders. This document describes Vcdiff, a compact portable encoding format designed for these purposes.
圧縮とdifferencingのテクニックはファイルとファイルバージョンのストレージと送信を大いに改良できます。 ファイルが異なったアーキテクチャと性能の特性があるマシンの向こう側にしばしば輸送されるので、そのようなデータを携帯用であることのフォームでコード化するべきであり、エンコーダに関する知識でまず解読できません。 このドキュメントはVcdiff、これらの目的のために設計されたコンパクトな携帯用のコード化形式について説明します。
Data differencing is the process of computing a compact and invertible encoding of a "target file" given a "source file". Data compression is similar, but without the use of source data. The UNIX utilities diff, compress, and gzip are well-known examples of data differencing and compression tools. For data differencing, the computed encoding is called a "delta file", and for data compression, it is called a "compressed file". Delta and compressed files are good for storage and transmission as they are often smaller than the originals.
データdifferencingは「ソースファイル」と考えて、「目標ファイル」のコンパクト、そして、invertibleコード化を計算するプロセスです。 同様ですがソースデータの使用なしでデータ圧縮。 UNIXユーティリティデフ、湿布、およびgzipはデータdifferencingと圧縮ツールのよく知られる例です。 データdifferencingにおいて、計算されたコード化は「デルタファイル」と呼ばれます、そして、データ圧縮において、それは「圧縮されたファイル」と呼ばれます。 それらがオリジナルよりしばしば小さいようにストレージとトランスミッションに、デルタと圧縮されたファイルは良いです。
Data differencing and data compression are traditionally treated as distinct types of data processing. However, as shown in the Vdelta technique by Korn and Vo [1], compression can be thought of as a special case of differencing in which the source data is empty. The basic idea is to unify the string parsing scheme used in the Lempel- Ziv'77 (LZ'77) style compressors [2] and the block-move technique of Tichy [3]. Loosely speaking, this works as follows:
データdifferencingとデータ圧縮は異なったタイプのデータ処理として伝統的に扱われます。 しかしながら、[1] 特殊なものとして圧縮を考えることができるのがコルンとVoによるVdeltaのテクニックで示されるように、differencingでは、ソースデータがどれであるかで空になってください。 基本的な考え方はLempel- Ziv77年(LZ77年)のスタイルコンプレッサー[2]で使用されるストリング構文解析要項とティチー[3]のブロック移動のテクニックを統一することです。 緩く話すなら、これは以下の通り働いています:
Korn, et. al. Standards Track [Page 2] RFC 3284 VCDIFF June 2002
etコルン、アル。 規格はVCDIFF2002年6月にRFC3284を追跡します[2ページ]。
a. Concatenate source and target data.
b. Parse the data from left to right as in LZ'77 but make sure
that a parsed segment starts the target data.
c. Start to output when reaching target data.
a。 ソースと目標データbを連結してください。 分析されたセグメントが目標データを始めるのを確実にするのを除いて、LZ77年のように左から右までデータを分析してください。. c。 目標データに達するとき出力する始め。
Parsing is based on string matching algorithms, such as suffix trees [4] or hashing with different time and space performance characteristics. Vdelta uses a fast string matching algorithm that requires less memory than other techniques [5,6]. However, even with this algorithm, the memory requirement can still be prohibitive for large files. A common way to deal with memory limitation is to partition an input file into chunks called "windows" and process them separately. Here, except for unpublished work by Vo, little has been done on designing effective windowing schemes. Current techniques, including Vdelta, simply use source and target windows with corresponding addresses across source and target files.
構文解析は、接尾語木[4]などのストリングマッチングアルゴリズムに基づいているか、または異なった時間と空間で性能の特性を論じ尽くしています。 Vdeltaは他のテクニック[5、6]より少ないメモリを必要とする速いストリングマッチングアルゴリズムを使用します。 しかしながら、大きいファイルにおいて、メモリ要件はまだこのアルゴリズムがあっても、禁止である場合があります。 メモリ制限に対処する一般的な方法は、「窓」と呼ばれる塊に入力ファイルを仕切って、別々にそれらを処理することです。 ここで、有効なウインドー体系を設計するとき、Voによる未発表の仕事以外に、少ししかしていません。 Vdeltaを含む現在のテクニックがソースと目標ファイルの向こう側の対応するアドレスと共にソースと目標ウィンドウを単に使用します。
String matching and windowing algorithms have great influence on the compression rate of delta and compressed files. However, it is desirable to have a portable encoding format that is independent of such algorithms. This enables the construction of client-server applications in which a server may serve clients with unknown computing characteristics. Unfortunately, all current differencing and compressing tools, including Vdelta, fall short in this respect. Their storage formats are closely intertwined with the implemented string matching and/or windowing algorithms.
ストリングマッチングとウインドーアルゴリズムはデルタと圧縮されたファイルの圧縮率で睨みが利きます。 しかしながら、そのようなアルゴリズムから独立している携帯用のコード化形式を持っているのは望ましいです。これはサーバが未知のコンピューティングの特性をクライアントに供給するかもしれないクライアント/サーバアプリケーションの工事を可能にします。 残念ながら、すべての現在のdifferencingとVdeltaを含むツールを圧縮するのはこの点で不足します。 実装しているストリングがアルゴリズムに合わせる、そして/または、窓を付けていて、それらのストレージ形式は密接にからみ合います。
The encoding format Vcdiff proposed here addresses the above issues. Vcdiff achieves the characteristics below:
ここで提案されたコード化形式Vcdiffは上記の問題を扱います。 Vcdiffは以下の特性を獲得します:
Output compactness:
The basic encoding format compactly represents compressed or
delta files. Applications can further extend the basic
encoding format with "secondary encoders" to achieve more
compression.
コンパクト性を出力してください: 基本的なコード化形式はコンパクトに圧縮されるかデルタファイルを表します。 アプリケーションは、より多くの圧縮を達成するために「セカンダリエンコーダ」でさらに基本的なコード化形式を広げることができます。
Data portability:
The basic encoding format is free from machine byte order and
word size issues. This allows data to be encoded on one
machine and decoded on a different machine with different
architecture.
データの移植性: 基本的なコード化形式には、マシンバイトオーダーと語長問題がありません。 これは、データが1台のマシンの上でコード化されて、異なったアーキテクチャがある異なったマシンの上で解読されるのを許容します。
Algorithm genericity:
The decoding algorithm is independent from string matching and
windowing algorithms. This allows competition among
implementations of the encoder while keeping the same decoder.
アルゴリズムgenericity: 解読アルゴリズムはストリングマッチングとウインドーアルゴリズムから独立しています。これは同じデコーダを保っている間、エンコーダの実装の中で競争を許します。
Korn, et. al. Standards Track [Page 3] RFC 3284 VCDIFF June 2002
etコルン、アル。 規格はVCDIFF2002年6月にRFC3284を追跡します[3ページ]。
Decoding efficiency:
Except for secondary encoder issues, the decoding algorithm
runs in time proportionate to the size of the target file and
uses space proportionate to the maximal window size. Vcdiff
differs from more conventional compressors in that it uses only
byte-aligned data, thus avoiding bit-level operations, which
improves decoding speed at the slight cost of compression
efficiency.
解読している効率: セカンダリエンコーダ問題を除いて、解読アルゴリズムは、目標ファイルのサイズに比例した時間で稼働していて、最大限度のウィンドウサイズに比例したスペースを使用します。 Vcdiffは圧縮効率のわずかな費用における解読速度を改良するその結果ビットレベル操作を避けるバイトで並べられたデータだけを使用するという点において、より従来のコンプレッサーと異なっています。
The combined differencing and compression method is called "delta compression" [14]. As this way of data processing treats compression as a special case of differencing, we shall use the term "delta file" to indicate the compressed output for both cases.
結合したdifferencingと圧縮方法は「デルタ圧縮」[14]と呼ばれます。 データ処理のこの方法が特殊なものとしてdifferencingしながら圧縮を扱うとき、私たちは、両方のケースのための圧縮された出力を示すのに「デルタファイル」という用語を使用するつもりです。
2. Conventions
2. コンベンション
The basic data unit is a byte. For portability, Vcdiff shall limit a byte to its lower eight bits even on machines with larger bytes. The bits in a byte are ordered from right to left so that the least significant bit (LSB) has value 1, and the most significant bit (MSB), has value 128.
基礎データユニットは1バイトです。 移植性のために、Vcdiffは、より大きいバイトでマシンさえの1バイトから低級8ビットを制限するものとします。 1バイトにおけるビットが左への権利から配置されるので、最下位ビット(LSB)には、1、および最も重要なビット(MSB)で128を評価する値があります。
For purposes of exposition in this document, we adopt the convention that the LSB is numbered 0, and the MSB is numbered 7. Bit numbers never appear in the encoded format itself.
このドキュメントにおける博覧会の目的のために、私たちは7に、番号付でLSBが番号付の0であり、MSBがそのような0であるコンベンションを採用します。 噛み付いている数はコード化された形式自体に決して現れません。
Vcdiff encodes unsigned integer values using a portable, variable- sized format (originally introduced in the Sfio library [7]). This encoding treats an integer as a number in base 128. Then, each digit in this representation is encoded in the lower seven bits of a byte. Except for the least significant byte, other bytes have their most significant bit turned on to indicate that there are still more digits in the encoding. The two key properties of this integer encoding that are beneficial to a data compression format are:
Vcdiffは、携帯用の、そして、可変な大きさで分けられた形式を使用することで符号のない整数値をコード化します。(元々、Sfio図書館[7])で導入します。 このコード化はベース128の中で数として整数を扱います。 そして、この表現における各ケタは1バイトの低級7ビットでコード化されます。 最も重要でないバイトを除いて、他のバイトで、まして、コード化にはケタがあるのを示すので、それらの最上位ビットをつけています。 この整数コード化のデータ圧縮形式に有利な2個の基本性質は以下の通りです。
a. The encoding is portable among systems using 8-bit bytes, and
b. Small values are encoded compactly.
a。 コード化は、システムの中で8ビットのバイト、およびbを使用することで携帯用です。 小さい値はコンパクトにコード化されます。
For example, consider the value 123456789, which can be represented with four 7-bit digits whose values are 58, 111, 26, 21 in order from most to least significant. Below is the 8-bit byte encoding of these digits. Note that the MSBs of 58, 111 and 26 are on.
例えば、値が123456789であると考えてください。(値が大部分から最も重要にならないまでのオーダーで58、111、26、21である7ビットの4ケタで123456789を表すことができます)。 以下に、これらのケタがコード化されながら、8ビットのバイトがあります。 58、111、および26のMSBsがオンであることに注意してください。
+-------------------------------------------+
| 10111010 | 11101111 | 10011010 | 00010101 |
+-------------------------------------------+
MSB+58 MSB+111 MSB+26 0+21
+-------------------------------------------+ | 10111010 | 11101111 | 10011010 | 00010101 | +-------------------------------------------+MSB+58MSB+111MSB+26 0+21
Korn, et. al. Standards Track [Page 4] RFC 3284 VCDIFF June 2002
etコルン、アル。 規格はVCDIFF2002年6月にRFC3284を追跡します[4ページ]。
Henceforth, the terms "byte" and "integer" will refer to a byte and an unsigned integer as described.
今後は、「バイト」という用語と「整数」は説明されるように1バイトと符号のない整数を参照するでしょう。
Algorithms in the C language are occasionally exhibited to clarify the descriptions. Such C code is meant for clarification only, and is not part of the actual specification of the Vcdiff format.
C言語におけるアルゴリズムは、記述をはっきりさせるために時折示されます。 そのようなCコードは、明確化だけのために意味されて、Vcdiff形式の実際の仕様の一部ではありません。
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14, RFC 2119 [12].
キーワード“MUST"、「必須NOT」が「必要です」、“SHALL"、「」、“SHOULD"、「「推薦され」て、「5月」の、そして、「任意」のNOTはBCP14(RFC2119[12])で説明されるように本書では解釈されることであるべきです。
3. Delta Instructions
3. デルタ指示
A large target file is partitioned into non-overlapping sections called "target windows". These target windows are processed separately and sequentially based on their order in the target file.
大きい目標ファイルは「目標ウィンドウ」と呼ばれる非重なっているセクションに仕切られます。 これらの目標ウィンドウは、別々に処理されて、目標ファイルにおける彼らのオーダーに連続して基づいています。
A target window T, of length t, may be compared against some source data segment S, of length s. By construction, this source data segment S comes either from the source file, if one is used, or from a part of the target file earlier than T. In this way, during decoding, S is completely known when T is being decoded.
目標ウィンドウTは長さtについて長さsの何らかのソースデータ・セグメントSに対して比較されるかもしれません。 工事で、このソースデータ・セグメントSは1つが使用されているならソースからファイルするか、またはT.Inより早く目標の一部からこのようにファイルしに来ます、解読の間Tが解読されていると、Sは完全に知られています。
The choices of T, t, S and s are made by some window selection algorithm, which can greatly affect the size of the encoding. However, as seen later, these choices are encoded so that no knowledge of the window selection algorithm is needed during decoding.
何らかの窓の選択アルゴリズムでT、t、S、およびsの選択をします。(それは、コード化のサイズに大いに影響できます)。 しかしながら、これらの選択が後で見られるようにコード化されるので、窓の選択アルゴリズムに関する知識は全く解読の間、必要ではありません。
Assume that S[j] represents the jth byte in S, and T[k] represents the kth byte in T. Then, for the delta instructions, we treat the data windows S and T as substrings of a superstring U, formed by concatenating them like this:
S[j]がSにjthバイトを表すと仮定してください。そうすれば、T[k]はT.にkthバイトを表します。Then、デルタ指示のために、私たちはこのようにそれらを連結することによって形成されたsuperstring Uに関するサブストリングとしてデータ窓のSとTを扱います:
S[0]S[1]...S[s-1]T[0]T[1]...T[t-1]
S[0]S[1]…S[s-1]T[0]T[1]…T[t-1]
The "address" of a byte in S or T is referred to by its location in U. For example, the address of T[k] is s+k.
SかTの1バイトの「アドレス」はU.Forの例の位置によって言及されて、T[k]のアドレスはs+kです。
The instructions to encode and direct the reconstruction of a target window are called delta instructions. There are three types:
目標ウィンドウの再建をコード化して、指示する指示はデルタ指示と呼ばれます。 3つのタイプがあります:
ADD: This instruction has two arguments, a size x and a sequence
of x bytes to be copied.
COPY: This instruction has two arguments, a size x and an address
p in the string U. The arguments specify the substring of U
that must be copied. We shall assert that such a substring
must be entirely contained in either S or T.
追加: この指示には、コピーされるべきxバイトの2つの議論、サイズx、および系列があります。 コピー: この指示はストリングU.に2つの議論、サイズx、およびアドレスpを持っています。議論はコピーしなければならないUに関するサブストリングを指定します。 私たちは、SかTのどちらかにそのようなサブストリングを完全に含まなければならないと断言するつもりです。
Korn, et. al. Standards Track [Page 5] RFC 3284 VCDIFF June 2002
etコルン、アル。 規格はVCDIFF2002年6月にRFC3284を追跡します[5ページ]。
RUN: This instruction has two arguments, a size x and a byte b,
that will be repeated x times.
以下を実行してください。 この指示には、bが2つの議論、サイズx、および1バイトあって、それは繰り返されたx回になるでしょう。
Below are example source and target windows and the delta instructions that encode the target window in terms of the source window.
以下に、ソースウィンドウに関して目標ウィンドウをコード化する例のソース、目標ウィンドウ、およびデルタ指示があります。
a b c d e f g h i j k l m n o p
a b c d w x y z e f g h e f g h e f g h e f g h z z z z
b c d e f g h i j k l m n o pはb c d w x y z e f g h e f g h e f g h e f g h z z z zです。
COPY 4, 0
ADD 4, w x y z
COPY 4, 4
COPY 12, 24
RUN 4, z
COPY4、0ADD4、w x y z COPY4、4COPY12、24RUN4、z
Thus, the first letter 'a' in the target window is at location 16 in the superstring. Note that the fourth instruction, "COPY 12, 24", copies data from T itself since address 24 is position 8 in T. This instruction also shows that it is fine to overlap the data to be copied with the data being copied from, as long as the latter starts earlier. This enables efficient encoding of periodic sequences, i.e., sequences with regularly repeated subsequences. The RUN instruction is a compact way to encode a sequence repeating the same byte even though such a sequence can be thought of as a periodic sequence with period 1.
したがって、目標ウィンドウの最初の手紙'a'が「スーパー-結」びにおける位置16にあります。 それに注意してください。4番目の指示、「アドレス24がまた、T. この指示における位置8は、データ存在が模造した状態でコピーされるためにデータを重ね合わせるのがすばらしいのを示します、後者が、より早く始まる限りことであるので、コピー12(24インチ)はT自体からのデータをコピーします」。 これは定期的に繰り返された続きですなわち、周期的な系列、系列の効率的なコード化を可能にします。 RUN指示は期間1で周期的な系列としてそのような系列を考えることができますが、同じバイトを繰り返す系列をコード化するコンパクトな方法です。
To reconstruct the target window, one simply processes one delta instruction at a time and copies the data, either from the source window or the target window being reconstructed, based on the type of the instruction and the associated address, if any.
1つは、目標ウィンドウを再建するために、一度に、単に1つのデルタの指示を処理して、データをコピーします、指示のタイプと関連アドレスに基づいてもしあれば再建されるソースウィンドウか目標ウィンドウから
4. Delta File Organization
4. デルタファイル編成
A Vcdiff delta file starts with a Header section followed by a sequence of Window sections. The Header section includes magic bytes to identify the file type, and information concerning data processing beyond the basic encoding format. The Window sections encode the target windows.
VcdiffデルタファイルはHeader部から始まります、続いて、Window部の系列から始まります。 Header部は、データ処理に関して基本的なコード化形式を超えてファイルの種類、および情報を特定するために魔法のバイトを含めます。 Window部は目標ウィンドウをコード化します。
Below is the overall organization of a delta file. The indented items refine the ones immediately above them. An item in square brackets may or may not be present in the file depending on the information encoded in the Indicator byte above it.
以下に、デルタファイルの総合的な組織があります。 入り込まれた項目はそれらのすぐ上のものを洗練します。 それの上でIndicatorバイトでコード化された情報によって、角括弧の項目はファイルに存在しているかもしれません。
Korn, et. al. Standards Track [Page 6] RFC 3284 VCDIFF June 2002
etコルン、アル。 規格はVCDIFF2002年6月にRFC3284を追跡します[6ページ]。
Header
Header1 - byte
Header2 - byte
Header3 - byte
Header4 - byte
Hdr_Indicator - byte
[Secondary compressor ID] - byte
[Length of code table data] - integer
[Code table data]
Size of near cache - byte
Size of same cache - byte
Compressed code table data
Window1
Win_Indicator - byte
[Source segment size] - integer
[Source segment position] - integer
The delta encoding of the target window
Length of the delta encoding - integer
The delta encoding
Size of the target window - integer
Delta_Indicator - byte
Length of data for ADDs and RUNs - integer
Length of instructions and sizes - integer
Length of addresses for COPYs - integer
Data section for ADDs and RUNs - array of bytes
Instructions and sizes section - array of bytes
Addresses section for COPYs - array of bytes
Window2
...
同じキャッシュのヘッダーHeader1--バイトHeader2--バイトHeader3--バイトHeader4--バイトHdr_Indicator--バイトSecondaryコンプレッサーID--コードテーブルデータのバイトLength--整数CodeテーブルデータSizeの近いキャッシュ--バイトSize--バイトCompressedコードテーブルデータWindow1Win_Indicator--バイトSourceセグメントサイズ--整数Sourceセグメント位置--整数は目標ウィンドウLengthのデルタコード化です; --コード化して、デルタでは、ADDsのためのデータの目標ウィンドウのSizeをコード化するデルタ--整数デルタ_Indicator--バイトLengthとCOPYs(ADDsとRUNsのための整数Data部)のためのアドレスのRUNs--指示とサイズの整数Length--整数Lengthが整列させるバイトInstructionsとサイズの整数がバイトWindow2の--AddressesがCOPYsのために区分するバイトの勢ぞろい--配列を区分します; ..
4.1 The Header Section
4.1 ヘッダー部分
Each delta file starts with a header section organized as below. Note the convention that square-brackets enclose optional items.
それぞれのデルタファイルは以下で結団されたヘッダー部分から始まります。 それが正方形で腕木を付けるコンベンションが任意の項目を同封することに注意してください。
Header1 - byte = 0xD6
Header2 - byte = 0xC3
Header3 - byte = 0xC4
Header4 - byte
Hdr_Indicator - byte
[Secondary compressor ID] - byte
[Length of code table data] - integer
[Code table data]
Header1--バイト=0xD6 Header2--バイト=0xC3 Header3--バイト=0xC4 Header4--バイトHdr_Indicator--バイト[セカンダリコンプレッサーID]--バイト[コードテーブルデータの長さ]--整数[コードテーブルデータ]
Korn, et. al. Standards Track [Page 7] RFC 3284 VCDIFF June 2002
etコルン、アル。 規格はVCDIFF2002年6月にRFC3284を追跡します[7ページ]。
The first three Header bytes are the ASCII characters 'V', 'C' and 'D' with their most significant bits turned on (in hexadecimal, the values are 0xD6, 0xC3, and 0xC4). The fourth Header byte is currently set to zero. In the future, it might be used to indicate the version of Vcdiff.
最初の3Headerバイトは、ASCII文字'V'と、'C'と彼らの最上位ビットがつけられている'D'(16進では、値は、0xD6と、0xC3と、0xC4である)です。 4番目のHeaderバイトは現在、ゼロに設定されます。 将来、それは、Vcdiffのバージョンを示すのに使用されるかもしれません。
The Hdr_Indicator byte shows if there is any initialization data required to aid in the reconstruction of data in the Window sections. This byte MAY have non-zero values for either, both, or neither of the two bits VCD_DECOMPRESS and VCD_CODETABLE below:
Hdr_Indicatorバイトは、何かデータがWindow部でのデータの再構成で支援するのを必要とした初期化があるかどうかを示します。 このバイトには、2ビットのVCD_DECOMPRESSとVCD_CODETABLEのどちらか、両方、またはどちらものための以下の非ゼロ値があるかもしれません:
7 6 5 4 3 2 1 0
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
^ ^
| |
| +-- VCD_DECOMPRESS
+---- VCD_CODETABLE
7 6 5 4 3 2 1 0 +-+-+-+-+-+-+-+-+ | | | | | | | | | +-+-+-+-+-+-+-+-+ ^ ^ | | | +--VCD_は+を減圧します。---- VCD_CODETABLE
If bit 0 (VCD_DECOMPRESS) is non-zero, this indicates that a secondary compressor may have been used to further compress certain parts of the delta encoding data as described in Sections 4.3 and 6. In that case, the ID of the secondary compressor is given next. If this bit is zero, the compressor ID byte is not included.
ビット0(VCD_DECOMPRESS)が非ゼロであるなら、これは、セカンダリコンプレッサーがさらにデルタがセクション4.3と6で説明されるようにデータを暗号化するある部分を圧縮するのに使用されたかもしれないのを示します。 その場合、次に、セカンダリコンプレッサーのIDを与えます。 このビットがゼロであるなら、コンプレッサーIDバイトは含まれていません。
If bit 1 (VCD_CODETABLE) is non-zero, this indicates that an application-defined code table is to be used for decoding the delta instructions. This table itself is compressed. The length of the data comprising this compressed code table and the data follow next. Section 7 discusses application-defined code tables. If this bit is zero, the code table data length and the code table data are not included.
ビット1(VCD_CODETABLE)が非ゼロであるなら、これは、アプリケーションで定義されたコードテーブルがデルタ指示を解読するのに使用されることになっているのを示します。 このテーブル自体は圧縮されます。 この圧縮コードテーブルを包括するデータの長さとデータは次に従います。 セクション7はアプリケーションで定義されたコードテーブルについて論じます。 このビットがゼロであるなら、コードテーブルデータの長さとコードテーブルデータは含まれていません。
If both bits are set, then the compressor ID byte is included before the code table data length and the code table data.
両方のビットが設定されるなら、コードテーブルデータの長さとコードがデータを見送る前にコンプレッサーIDバイトは含まれています。
4.2 The Format of a Window Section
4.2 ウィンドウ・セクションの形式
Each Window section is organized as follows:
それぞれのWindow部は以下の通り組織化されます:
Win_Indicator - byte
[Source segment length] - integer
[Source segment position] - integer
The delta encoding of the target window
Win_Indicator--バイト[ソースセグメントの長さ]--整数[ソースのセグメント位置]--目標のデルタコード化が窓を付ける整数
Korn, et. al. Standards Track [Page 8] RFC 3284 VCDIFF June 2002
etコルン、アル。 規格はVCDIFF2002年6月にRFC3284を追跡します[8ページ]。
Below are the details of the various items:
以下に、様々な項目の細部があります:
Win_Indicator:
This byte is a set of bits, as shown:
_インディケータを得てください: このバイトは示されるように1セットのビットです:
7 6 5 4 3 2 1 0
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
^ ^
| |
| +-- VCD_SOURCE
+---- VCD_TARGET
7 6 5 4 3 2 1 0 +-+-+-+-+-+-+-+-+ | | | | | | | | | +-+-+-+-+-+-+-+-+ ^ ^ | | | +--VCD_ソース+---- VCD_目標
If bit 0 (VCD_SOURCE) is non-zero, this indicates that a
segment of data from the "source" file was used as the
corresponding source window of data to encode the target
window. The decoder will use this same source data segment to
decode the target window.
ビット0(VCD_SOURCE)が非ゼロであるなら、これは、「ソース」ファイルからのデータのセグメントが目標ウィンドウをコード化するのにデータの対応するソースウィンドウとして使用されたのを示します。 デコーダは、目標ウィンドウを解読するのにこの同じソースデータ・セグメントを使用するでしょう。
If bit 1 (VCD_TARGET) is non-zero, this indicates that a
segment of data from the "target" file was used as the
corresponding source window of data to encode the target
window. As above, this same source data segment is used to
decode the target window.
ビット1(VCD_TARGET)が非ゼロであるなら、これは、「目標」ファイルからのデータのセグメントが目標ウィンドウをコード化するのにデータの対応するソースウィンドウとして使用されたのを示します。 同じくらい上では、この同じソースデータ・セグメントが、目標ウィンドウを解読するのに使用されます。
The Win_Indicator byte MUST NOT have more than one of the bits
set (non-zero). It MAY have none of these bits set.
Win_Indicatorバイトで、ビットの1つ以上は(非ゼロ)を設定してはいけません。 それで、これらのビットのいずれも設定しないかもしれません。
If one of these bits is set, the byte is followed by two
integers to indicate respectively, the length and position of
the source data segment in the relevant file. If the indicator
byte is zero, the target window was compressed by itself
without comparing against another data segment, and these two
integers are not included.
これらのビットの1つが設定されるなら、バイトは関連ファイルのソースデータ・セグメントに関するそれぞれ示す2つの整数、長さ、および見解によって続かれています。 インディケータバイトがゼロであるなら、別のデータ・セグメントに対して比較しないで、目標ウィンドウはそれ自体で圧縮されました、そして、これらの2つの整数は含まれていません。
The delta encoding of the target window:
目標ウィンドウのデルタコード化:
This contains the delta encoding of the target window, either
in terms of the source data segment (i.e., VCD_SOURCE or
VCD_TARGET was set) or by itself if no source window is
specified. This data format is discussed next.
ソースウィンドウが全く指定されないなら、これはソースデータ・セグメント(すなわち、VCD_SOURCEかVCD_TARGETが用意ができていた)かそれ自体で目標ウィンドウのデルタコード化を含んでいます。 次に、このデータの形式について議論します。
Korn, et. al. Standards Track [Page 9] RFC 3284 VCDIFF June 2002
etコルン、アル。 規格はVCDIFF2002年6月にRFC3284を追跡します[9ページ]。
4.3 The Delta Encoding of a Target Window
4.3 目標ウィンドウのデルタコード化
The delta encoding of a target window is organized as follows:
目標ウィンドウのデルタコード化は以下の通り組織化されます:
Length of the delta encoding - integer
The delta encoding
Length of the target window - integer
Delta_Indicator - byte
Length of data for ADDs and RUNs - integer
Length of instructions section - integer
Length of addresses for COPYs - integer
Data section for ADDs and RUNs - array of bytes
Instructions and sizes section - array of bytes
Addresses section for COPYs - array of bytes
デルタコード化の長さ--ADDsのためのデータの目標ウィンドウのLengthをコード化するデルタ--整数デルタ_Indicator--バイトLengthとCOPYs(ADDsとRUNsのための整数Data部)のためのアドレスのRUNs--指示部の整数Length--整数Lengthが整列させるバイトInstructionsの整数とセクション(COPYsのためのバイトAddresses部の配列)が整列させるバイトのサイズ
Length of the delta encoding:
This integer gives the total number of remaining bytes that
comprise the data of the delta encoding for this target
window.
デルタコード化の長さ: この整数はこの目標ウィンドウのためのデルタコード化に関するデータを包括する残っているバイトの総数を与えます。
The delta encoding:
This contains the data representing the delta encoding which
is described next.
デルタコード化: これは次に説明されるデルタコード化を表すデータを含んでいます。
Length of the target window:
This integer indicates the actual size of the target window
after decompression. A decoder can use this value to
allocate memory to store the uncompressed data.
目標ウィンドウの長さ: この整数は減圧の後に目標ウィンドウの実サイズを示します。 デコーダは、解凍されたデータを保存するためにメモリを割り当てるのにこの値を使用できます。
Delta_Indicator:
This byte is a set of bits, as shown:
デルタ_インディケータ: このバイトは示されるように1セットのビットです:
7 6 5 4 3 2 1 0
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
^ ^ ^
| | |
| | +-- VCD_DATACOMP
| +---- VCD_INSTCOMP
+------ VCD_ADDRCOMP
7 6 5 4 3 2 1 0 +-+-+-+-+-+-+-+-+ | | | | | | | | | +-+-+-+-+-+-+-+-+ ^ ^ ^ | | | | | +--VCD_DATACOMP| +---- VCD_INSTCOMP+------ VCD_ADDRCOMP
VCD_DATACOMP: bit value 1.
VCD_INSTCOMP: bit value 2.
VCD_ADDRCOMP: bit value 4.
VCD_DATACOMP: 値1に噛み付きました。 VCD_INSTCOMP: 値2に噛み付きました。 VCD_ADDRCOMP: 値4に噛み付きました。
Korn, et. al. Standards Track [Page 10] RFC 3284 VCDIFF June 2002
etコルン、アル。 規格はVCDIFF2002年6月にRFC3284を追跡します[10ページ]。
As discussed, the delta encoding consists of COPY, ADD and RUN
instructions. The ADD and RUN instructions have accompanying
unmatched data (that is, data that does not specifically match
any data in the source window or in some earlier part of the
target window) and the COPY instructions have addresses of
where the matches occur. OPTIONALLY, these types of data MAY
be further compressed using a secondary compressor. Thus,
Vcdiff separates the encoding of the delta instructions into
three parts:
議論するように、デルタコード化はCOPY、ADD、およびRUN指示から成ります。 ADDとRUN指示で、付随の優れたデータ(すなわち、明確にソースウィンドウか目標ウィンドウのいくつかの以前の一部の少しのデータにも合っていないデータ)とCOPY指示には、マッチが現れるところに関するアドレスがあります。 セカンダリコンプレッサーを使用して、OPTIONALLY、これらのタイプのデータは圧縮されていた状態で、より遠いかもしれません。 したがって、Vcdiffはデルタ指示のコード化を3つの部分に切り離します:
a. The unmatched data in the ADD and RUN instructions,
b. The delta instructions and accompanying sizes, and
c. The addresses of the COPY instructions.
a。 ADDとRUN指示、bの優れたデータ。 デルタ指示、付随のサイズ、およびc。 COPY指示のアドレス。
If the bit VCD_DECOMPRESS (Section 4.1) was on, each of these
sections may have been compressed using the specified secondary
compressor. The bit positions 0 (VCD_DATACOMP), 1
(VCD_INSTCOMP), and 2 (VCD_ADDRCOMP) respectively indicate, if
non-zero, that the corresponding parts are compressed. Then,
these parts MUST be decompressed before decoding the delta
instructions.
ビットVCD_DECOMPRESS(セクション4.1)がオンであったなら、それぞれのこれらのセクションは、指定されたセカンダリコンプレッサーを使用することで圧縮されたかもしれません。 ビットは非ゼロであるなら(VCD_DATACOMP)、1(VCD_INSTCOMP)、および2(VCD_ADDRCOMP)がそれぞれ示す0を置いて、対応する部分は圧縮されます。 そして、デルタ指示を解読する前に、これらの部品を減圧しなければなりません。
Length of data for ADDs and RUNs:
This is the length (in bytes) of the section of data storing
the unmatched data accompanying the ADD and RUN instructions.
ADDsとRUNsのためのデータの長さ: これはADDに同伴する優れたデータを保存するデータとRUN指示のセクションの長さ(バイトによる)です。
Length of instructions section:
This is the length (in bytes) of the delta instructions and
accompanying sizes.
指示部の長さ: これはデルタ指示と付随のサイズの長さ(バイトによる)です。
Length of addresses for COPYs:
This is the length (in bytes) of the section storing the
addresses of the COPY instructions.
COPYsのためのアドレスの長さ: これはCOPY指示のアドレスを保存するセクションの長さ(バイトによる)です。
Data section for ADDs and RUNs:
This sequence of bytes encodes the unmatched data for the ADD
and RUN instructions.
ADDsとRUNsのための資料課: バイトのこの系列はADDとRUN指示のための優れたデータをコード化します。
Instructions and sizes section:
This sequence of bytes encodes the instructions and their
sizes.
指示とサイズ部: バイトのこの系列は指示とそれらのサイズをコード化します。
Addresses section for COPYs:
This sequence of bytes encodes the addresses of the COPY
instructions.
COPYsのためのアドレス部: バイトのこの系列はCOPY指示のアドレスをコード化します。
Korn, et. al. Standards Track [Page 11] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 11] RFC 3284 VCDIFF June 2002
5. Delta Instruction Encoding
5. Delta Instruction Encoding
The delta instructions described in Section 3 represent the results of string matching. For many data differencing applications in which the changes between source and target data are small, any straightforward representation of these instructions would be adequate. However, for applications including differencing of binary files or data compression, it is important to encode these instructions well to achieve good compression rates. The keys to this achievement is to efficiently encode the addresses of COPY instructions and the sizes of all delta instructions.
The delta instructions described in Section 3 represent the results of string matching. For many data differencing applications in which the changes between source and target data are small, any straightforward representation of these instructions would be adequate. However, for applications including differencing of binary files or data compression, it is important to encode these instructions well to achieve good compression rates. The keys to this achievement is to efficiently encode the addresses of COPY instructions and the sizes of all delta instructions.
5.1 Address Encoding Modes of COPY Instructions
5.1 Address Encoding Modes of COPY Instructions
Addresses of COPY instructions are locations of matches and often occur close by or even exactly equal to one another. This is because data in local regions are often replicated with minor changes. In turn, this means that coding a newly matched address against some recently matched addresses can be beneficial. To take advantage of this phenomenon and encode addresses of COPY instructions more efficiently, the Vcdiff data format supports the use of two different types of address caches. Both the encoder and decoder maintain these caches, so that decoder's caches remain synchronized with the encoder's caches.
Addresses of COPY instructions are locations of matches and often occur close by or even exactly equal to one another. This is because data in local regions are often replicated with minor changes. In turn, this means that coding a newly matched address against some recently matched addresses can be beneficial. To take advantage of this phenomenon and encode addresses of COPY instructions more efficiently, the Vcdiff data format supports the use of two different types of address caches. Both the encoder and decoder maintain these caches, so that decoder's caches remain synchronized with the encoder's caches.
a. A "near" cache is an array with "s_near" slots, each containing an
address used for encoding addresses nearby to previously encoded
addresses (in the positive direction only). The near cache also
maintains a "next_slot" index to the near cache. New entries to
the near cache are always inserted in the next_slot index, which
maintains a circular buffer of the s_near most recent addresses.
a. A "near" cache is an array with "s_near" slots, each containing an address used for encoding addresses nearby to previously encoded addresses (in the positive direction only). The near cache also maintains a "next_slot" index to the near cache. New entries to the near cache are always inserted in the next_slot index, which maintains a circular buffer of the s_near most recent addresses.
b. A "same" cache is an array with "s_same", with a multiple of 256
slots, each containing an address. The same cache maintains a
hash table of recent addresses used for repeated encoding of the
exact same address.
b. A "same" cache is an array with "s_same", with a multiple of 256 slots, each containing an address. The same cache maintains a hash table of recent addresses used for repeated encoding of the exact same address.
By default, the parameters s_near and s_same are respectively set to 4 and 3. An encoder MAY modify these values, but then it MUST encode the new values in the encoding itself, as discussed in Section 7, so that the decoder can properly set up its own caches.
By default, the parameters s_near and s_same are respectively set to 4 and 3. An encoder MAY modify these values, but then it MUST encode the new values in the encoding itself, as discussed in Section 7, so that the decoder can properly set up its own caches.
At the start of processing a target window, an implementation (encoder or decoder) initializes all of the slots in both caches to zero. The next_slot pointer of the near cache is set to point to slot zero.
At the start of processing a target window, an implementation (encoder or decoder) initializes all of the slots in both caches to zero. The next_slot pointer of the near cache is set to point to slot zero.
Korn, et. al. Standards Track [Page 12] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 12] RFC 3284 VCDIFF June 2002
Each time a COPY instruction is processed by the encoder or decoder, the implementation's caches are updated as follows, where "addr" is the address in the COPY instruction.
Each time a COPY instruction is processed by the encoder or decoder, the implementation's caches are updated as follows, where "addr" is the address in the COPY instruction.
a. The slot in the near cache referenced by the next_slot index is
set to addr. The next_slot index is then incremented modulo
s_near.
a. The slot in the near cache referenced by the next_slot index is set to addr. The next_slot index is then incremented modulo s_near.
b. The slot in the same cache whose index is addr%(s_same*256) is set
to addr. [We use the C notations of % for modulo and * for
multiplication.]
b. The slot in the same cache whose index is addr%(s_same*256) is set to addr. [We use the C notations of % for modulo and * for multiplication.]
5.2 Example code for maintaining caches
5.2 Example code for maintaining caches
To make clear the above description, below are examples of cache data structures and algorithms to initialize and update them:
To make clear the above description, below are examples of cache data structures and algorithms to initialize and update them:
typedef struct _cache_s
{
int* near; /* array of size s_near */
int s_near;
int next_slot; /* the circular index for near */
int* same; /* array of size s_same*256 */
int s_same;
} Cache_t;
typedef struct _cache_s { int* near; /* array of size s_near */ int s_near; int next_slot; /* the circular index for near */ int* same; /* array of size s_same*256 */ int s_same; } Cache_t;
cache_init(Cache_t* ka)
{
int i;
cache_init(Cache_t* ka) { int i;
ka->next_slot = 0;
for(i = 0; i < ka->s_near; ++i)
ka->near[i] = 0;
ka->next_slot = 0; for(i = 0; i < ka->s_near; ++i) ka->near[i] = 0;
for(i = 0; i < ka->s_same*256; ++i)
ka->same[i] = 0;
}
for(i = 0; i < ka->s_same*256; ++i) ka->same[i] = 0; }
cache_update(Cache_t* ka, int addr)
{
if(ka->s_near > 0)
{ ka->near[ka->next_slot] = addr;
ka->next_slot = (ka->next_slot + 1) % ka->s_near;
}
cache_update(Cache_t* ka, int addr) { if(ka->s_near > 0) { ka->near[ka->next_slot] = addr; ka->next_slot = (ka->next_slot + 1) % ka->s_near; }
if(ka->s_same > 0)
ka->same[addr % (ka->s_same*256)] = addr;
}
if(ka->s_same > 0) ka->same[addr % (ka->s_same*256)] = addr; }
Korn, et. al. Standards Track [Page 13] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 13] RFC 3284 VCDIFF June 2002
5.3 Encoding of COPY instruction addresses
5.3 Encoding of COPY instruction addresses
The address of a COPY instruction is encoded using different modes, depending on the type of cached address used, if any.
The address of a COPY instruction is encoded using different modes, depending on the type of cached address used, if any.
Let "addr" be the address of a COPY instruction to be decoded and "here" be the current location in the target data (i.e., the start of the data about to be encoded or decoded). Let near[j] be the jth element in the near cache, and same[k] be the kth element in the same cache. Below are the possible address modes:
Let "addr" be the address of a COPY instruction to be decoded and "here" be the current location in the target data (i.e., the start of the data about to be encoded or decoded). Let near[j] be the jth element in the near cache, and same[k] be the kth element in the same cache. Below are the possible address modes:
VCD_SELF: This mode has value 0. The address was encoded by
itself as an integer.
VCD_SELF: This mode has value 0. The address was encoded by itself as an integer.
VCD_HERE: This mode has value 1. The address was encoded as the
integer value "here - addr".
VCD_HERE: This mode has value 1. The address was encoded as the integer value "here - addr".
Near modes: The "near modes" are in the range [2,s_near+1]. Let m
be the mode of the address encoding. The address was encoded
as the integer value "addr - near[m-2]".
Near modes: The "near modes" are in the range [2,s_near+1]. Let m be the mode of the address encoding. The address was encoded as the integer value "addr - near[m-2]".
Same modes: The "same modes" are in the range
[s_near+2,s_near+s_same+1]. Let m be the mode of the encoding.
The address was encoded as a single byte b such that "addr ==
same[(m - (s_near+2))*256 + b]".
Same modes: The "same modes" are in the range [s_near+2,s_near+s_same+1]. Let m be the mode of the encoding. The address was encoded as a single byte b such that "addr == same[(m - (s_near+2))*256 + b]".
5.4 Example code for encoding and decoding of COPY instruction addresses
5.4 Example code for encoding and decoding of COPY instruction addresses
We show example algorithms below to demonstrate the use of address modes more clearly. The encoder has the freedom to choose address modes, the sample addr_encode() algorithm merely shows one way of picking the address mode. The decoding algorithm addr_decode() will uniquely decode addresses, regardless of the encoder's algorithm choice.
We show example algorithms below to demonstrate the use of address modes more clearly. The encoder has the freedom to choose address modes, the sample addr_encode() algorithm merely shows one way of picking the address mode. The decoding algorithm addr_decode() will uniquely decode addresses, regardless of the encoder's algorithm choice.
Note that the address caches are updated immediately after an address is encoded or decoded. In this way, the decoder is always synchronized with the encoder.
Note that the address caches are updated immediately after an address is encoded or decoded. In this way, the decoder is always synchronized with the encoder.
Korn, et. al. Standards Track [Page 14] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 14] RFC 3284 VCDIFF June 2002
int addr_encode(Cache_t* ka, int addr, int here, int* mode)
{
int i, d, bestd, bestm;
int addr_encode(Cache_t* ka, int addr, int here, int* mode) { int i, d, bestd, bestm;
/* Attempt to find the address mode that yields the
* smallest integer value for "d", the encoded address
* value, thereby minimizing the encoded size of the
* address. */
/* Attempt to find the address mode that yields the * smallest integer value for "d", the encoded address * value, thereby minimizing the encoded size of the * address. */
bestd = addr; bestm = VCD_SELF; /* VCD_SELF == 0 */
bestd = addr; bestm = VCD_SELF; /* VCD_SELF == 0 */
if((d = here-addr) < bestd)
{ bestd = d; bestm = VCD_HERE; } /* VCD_HERE == 1 */
if((d = here-addr) < bestd) { bestd = d; bestm = VCD_HERE; } /* VCD_HERE == 1 */
for(i = 0; i < ka->s_near; ++i)
if((d = addr - ka->near[i]) >= 0 && d < bestd)
{ bestd = d; bestm = i+2; }
for(i = 0; i < ka->s_near; ++i) if((d = addr - ka->near[i]) >= 0 && d < bestd) { bestd = d; bestm = i+2; }
if(ka->s_same > 0 && ka->same[d = addr%(ka->s_same*256)] == addr)
{ bestd = d%256; bestm = ka->s_near + 2 + d/256; }
if(ka->s_same > 0 && ka->same[d = addr%(ka->s_same*256)] == addr) { bestd = d%256; bestm = ka->s_near + 2 + d/256; }
cache_update(ka,addr);
cache_update(ka,addr);
*mode = bestm; /* this returns the address encoding mode */
return bestd; /* this returns the encoded address */
}
*mode = bestm; /* this returns the address encoding mode */ return bestd; /* this returns the encoded address */ }
Note that the addr_encode() algorithm chooses the best address mode using a local optimization, but that may not lead to the best encoding efficiency because different modes lead to different instruction encodings, as described below.
Note that the addr_encode() algorithm chooses the best address mode using a local optimization, but that may not lead to the best encoding efficiency because different modes lead to different instruction encodings, as described below.
The functions addrint() and addrbyte() used in addr_decode(), obtain from the "Addresses section for COPYs" (Section 4.3), an integer or a byte, respectively. These utilities will not be described here. We simply recall that an integer is represented as a compact variable- sized string of bytes, as described in Section 2 (i.e., base 128).
The functions addrint() and addrbyte() used in addr_decode(), obtain from the "Addresses section for COPYs" (Section 4.3), an integer or a byte, respectively. These utilities will not be described here. We simply recall that an integer is represented as a compact variable- sized string of bytes, as described in Section 2 (i.e., base 128).
Korn, et. al. Standards Track [Page 15] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 15] RFC 3284 VCDIFF June 2002
int addr_decode(Cache_t* ka, int here, int mode)
{ int addr, m;
int addr_decode(Cache_t* ka, int here, int mode) { int addr, m;
if(mode == VCD_SELF)
addr = addrint();
else if(mode == VCD_HERE)
addr = here - addrint();
else if((m = mode - 2) >= 0 && m < ka->s_near) /* near cache */
addr = ka->near[m] + addrint();
else /* same cache */
{ m = mode - (2 + ka->s_near);
addr = ka->same[m*256 + addrbyte()];
}
if(mode == VCD_SELF) addr = addrint(); else if(mode == VCD_HERE) addr = here - addrint(); else if((m = mode - 2) >= 0 && m < ka->s_near) /* near cache */ addr = ka->near[m] + addrint(); else /* same cache */ { m = mode - (2 + ka->s_near); addr = ka->same[m*256 + addrbyte()]; }
cache_update(ka, addr);
cache_update(ka, addr);
return addr;
}
return addr; }
5.4 Instruction Codes
5.4 Instruction Codes
Matches are often short in lengths and separated by small amounts of unmatched data. That is, the lengths of COPY and ADD instructions are often small. This is particularly true of binary data such as executable files or structured data, such as HTML or XML. In such cases, compression can be improved by combining the encoding of the sizes and the instruction types, as well as combining the encoding of adjacent delta instructions with sufficiently small data sizes. Effective choices of when to perform such combinations depend on many factors including the data being processed and the string matching algorithm in use. For example, if many COPY instructions have the same data sizes, it may be worthwhile to encode these instructions more compactly than others.
Matches are often short in lengths and separated by small amounts of unmatched data. That is, the lengths of COPY and ADD instructions are often small. This is particularly true of binary data such as executable files or structured data, such as HTML or XML. In such cases, compression can be improved by combining the encoding of the sizes and the instruction types, as well as combining the encoding of adjacent delta instructions with sufficiently small data sizes. Effective choices of when to perform such combinations depend on many factors including the data being processed and the string matching algorithm in use. For example, if many COPY instructions have the same data sizes, it may be worthwhile to encode these instructions more compactly than others.
The Vcdiff data format is designed so that a decoder does not need to be aware of the choices made in encoding algorithms. This is achieved with the notion of an "instruction code table", containing 256 entries. Each entry defines, either a single delta instruction or a pair of instructions that have been combined. Note that the code table itself only exists in main memory, not in the delta file (unless using an application-defined code table, described in Section 7). The encoded data simply includes the index of each instruction and, since there are only 256 indices, each index can be represented as a single byte.
The Vcdiff data format is designed so that a decoder does not need to be aware of the choices made in encoding algorithms. This is achieved with the notion of an "instruction code table", containing 256 entries. Each entry defines, either a single delta instruction or a pair of instructions that have been combined. Note that the code table itself only exists in main memory, not in the delta file (unless using an application-defined code table, described in Section 7). The encoded data simply includes the index of each instruction and, since there are only 256 indices, each index can be represented as a single byte.
Korn, et. al. Standards Track [Page 16] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 16] RFC 3284 VCDIFF June 2002
Each instruction code entry contains six fields, each of which is a single byte with an unsigned value:
Each instruction code entry contains six fields, each of which is a single byte with an unsigned value:
+-----------------------------------------------+
| inst1 | size1 | mode1 | inst2 | size2 | mode2 |
+-----------------------------------------------+
+-----------------------------------------------+ | inst1 | size1 | mode1 | inst2 | size2 | mode2 | +-----------------------------------------------+
Each triple (inst,size,mode) defines a delta instruction. The meanings of these fields are as follows:
Each triple (inst,size,mode) defines a delta instruction. The meanings of these fields are as follows:
inst: An "inst" field can have one of the four values: NOOP (0),
ADD (1), RUN (2) or COPY (3) to indicate the instruction
types. NOOP means that no instruction is specified. In
this case, both the corresponding size and mode fields will
be zero.
inst: An "inst" field can have one of the four values: NOOP (0), ADD (1), RUN (2) or COPY (3) to indicate the instruction types. NOOP means that no instruction is specified. In this case, both the corresponding size and mode fields will be zero.
size: A "size" field is zero or positive. A value zero means that
the size associated with the instruction is encoded
separately as an integer in the "Instructions and sizes
section" (Section 6). A positive value for "size" defines
the actual data size. Note that since the size is
restricted to a byte, the maximum value for any instruction
with size implicitly defined in the code table is 255.
size: A "size" field is zero or positive. A value zero means that the size associated with the instruction is encoded separately as an integer in the "Instructions and sizes section" (Section 6). A positive value for "size" defines the actual data size. Note that since the size is restricted to a byte, the maximum value for any instruction with size implicitly defined in the code table is 255.
mode: A "mode" field is significant only when the associated delta
instruction is a COPY. It defines the mode used to encode
the associated addresses. For other instructions, this is
always zero.
mode: A "mode" field is significant only when the associated delta instruction is a COPY. It defines the mode used to encode the associated addresses. For other instructions, this is always zero.
5.6 The Code Table
5.6 The Code Table
Following the discussions on address modes and instruction code tables, we define a "Code Table" to have the data below:
Following the discussions on address modes and instruction code tables, we define a "Code Table" to have the data below:
s_near: the size of the near cache,
s_same: the size of the same cache,
i_code: the 256-entry instruction code table.
s_near: the size of the near cache, s_same: the size of the same cache, i_code: the 256-entry instruction code table.
Vcdiff itself defines a "default code table" in which s_near is 4 and s_same is 3. Thus, there are 9 address modes for a COPY instruction. The first two are VCD_SELF (0) and VCD_HERE (1). Modes 2, 3, 4 and 5 are for addresses coded against the near cache. And modes 6, 7 and 8, are for addresses coded against the same cache.
Vcdiff itself defines a "default code table" in which s_near is 4 and s_same is 3. Thus, there are 9 address modes for a COPY instruction. The first two are VCD_SELF (0) and VCD_HERE (1). Modes 2, 3, 4 and 5 are for addresses coded against the near cache. And modes 6, 7 and 8, are for addresses coded against the same cache.
Korn, et. al. Standards Track [Page 17] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 17] RFC 3284 VCDIFF June 2002
TYPE SIZE MODE TYPE SIZE MODE INDEX
---------------------------------------------------------------
1. RUN 0 0 NOOP 0 0 0
2. ADD 0, [1,17] 0 NOOP 0 0 [1,18]
3. COPY 0, [4,18] 0 NOOP 0 0 [19,34]
4. COPY 0, [4,18] 1 NOOP 0 0 [35,50]
5. COPY 0, [4,18] 2 NOOP 0 0 [51,66]
6. COPY 0, [4,18] 3 NOOP 0 0 [67,82]
7. COPY 0, [4,18] 4 NOOP 0 0 [83,98]
8. COPY 0, [4,18] 5 NOOP 0 0 [99,114]
9. COPY 0, [4,18] 6 NOOP 0 0 [115,130]
10. COPY 0, [4,18] 7 NOOP 0 0 [131,146]
11. COPY 0, [4,18] 8 NOOP 0 0 [147,162]
12. ADD [1,4] 0 COPY [4,6] 0 [163,174]
13. ADD [1,4] 0 COPY [4,6] 1 [175,186]
14. ADD [1,4] 0 COPY [4,6] 2 [187,198]
15. ADD [1,4] 0 COPY [4,6] 3 [199,210]
16. ADD [1,4] 0 COPY [4,6] 4 [211,222]
17. ADD [1,4] 0 COPY [4,6] 5 [223,234]
18. ADD [1,4] 0 COPY 4 6 [235,238]
19. ADD [1,4] 0 COPY 4 7 [239,242]
20. ADD [1,4] 0 COPY 4 8 [243,246]
21. COPY 4 [0,8] ADD 1 0 [247,255]
---------------------------------------------------------------
TYPE SIZE MODE TYPE SIZE MODE INDEX --------------------------------------------------------------- 1. RUN 0 0 NOOP 0 0 0 2. ADD 0, [1,17] 0 NOOP 0 0 [1,18] 3. COPY 0, [4,18] 0 NOOP 0 0 [19,34] 4. COPY 0, [4,18] 1 NOOP 0 0 [35,50] 5. COPY 0, [4,18] 2 NOOP 0 0 [51,66] 6. COPY 0, [4,18] 3 NOOP 0 0 [67,82] 7. COPY 0, [4,18] 4 NOOP 0 0 [83,98] 8. COPY 0, [4,18] 5 NOOP 0 0 [99,114] 9. COPY 0, [4,18] 6 NOOP 0 0 [115,130] 10. COPY 0, [4,18] 7 NOOP 0 0 [131,146] 11. COPY 0, [4,18] 8 NOOP 0 0 [147,162] 12. ADD [1,4] 0 COPY [4,6] 0 [163,174] 13. ADD [1,4] 0 COPY [4,6] 1 [175,186] 14. ADD [1,4] 0 COPY [4,6] 2 [187,198] 15. ADD [1,4] 0 COPY [4,6] 3 [199,210] 16. ADD [1,4] 0 COPY [4,6] 4 [211,222] 17. ADD [1,4] 0 COPY [4,6] 5 [223,234] 18. ADD [1,4] 0 COPY 4 6 [235,238] 19. ADD [1,4] 0 COPY 4 7 [239,242] 20. ADD [1,4] 0 COPY 4 8 [243,246] 21. COPY 4 [0,8] ADD 1 0 [247,255] ---------------------------------------------------------------
The default instruction code table is depicted above, in a compact representation that we use only for descriptive purposes. See section 7 for the specification of how an instruction code table is represented in the Vcdiff encoding format. In the depiction, a zero value for size indicates that the size is separately coded. The mode of non-COPY instructions is represented as 0, even though they are not used.
The default instruction code table is depicted above, in a compact representation that we use only for descriptive purposes. See section 7 for the specification of how an instruction code table is represented in the Vcdiff encoding format. In the depiction, a zero value for size indicates that the size is separately coded. The mode of non-COPY instructions is represented as 0, even though they are not used.
In the depiction, each numbered line represents one or more entries
in the actual instruction code table (recall that an entry in the
instruction code table may represent up to two combined delta
instructions.) The last column ("INDEX") shows which index value, or
range of index values, of the entries are covered by that line. (The
notation [i,j] means values from i through j, inclusively.) The
first 6 columns of a line in the depiction, describe the pairs of
instructions used for the corresponding index value(s).
In the depiction, each numbered line represents one or more entries in the actual instruction code table (recall that an entry in the instruction code table may represent up to two combined delta instructions.) The last column ("INDEX") shows which index value, or range of index values, of the entries are covered by that line. (The notation [i,j] means values from i through j, inclusively.) The first 6 columns of a line in the depiction, describe the pairs of instructions used for the corresponding index value(s).
If a line in the depiction includes a column entry using the [i,j] notation, this means that the line is instantiated for each value in the range from i to j, inclusively. The notation "0, [i,j]" means that the line is instantiated for the value 0 and for each value in the range from i to j, inclusively.
If a line in the depiction includes a column entry using the [i,j] notation, this means that the line is instantiated for each value in the range from i to j, inclusively. The notation "0, [i,j]" means that the line is instantiated for the value 0 and for each value in the range from i to j, inclusively.
Korn, et. al. Standards Track [Page 18] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 18] RFC 3284 VCDIFF June 2002
If a line in the depiction includes more than one entry using the [i,j] notation, implying a "nested loop" to convert the line to a range of table entries, the first such [i,j] range specifies the outer loop, and the second specifies the inner loop.
If a line in the depiction includes more than one entry using the [i,j] notation, implying a "nested loop" to convert the line to a range of table entries, the first such [i,j] range specifies the outer loop, and the second specifies the inner loop.
The below examples should make clear the above description:
The below examples should make clear the above description:
Line 1 shows the single RUN instruction with index 0. As the size field is 0, this RUN instruction always has its actual size encoded separately.
Line 1 shows the single RUN instruction with index 0. As the size field is 0, this RUN instruction always has its actual size encoded separately.
Line 2 shows the 18 single ADD instructions. The ADD instruction with size field 0 (i.e., the actual size is coded separately) has index 1. ADD instructions with sizes from 1 to 17 use code indices 2 to 18 and their sizes are as given (so they will not be separately encoded.)
Line 2 shows the 18 single ADD instructions. The ADD instruction with size field 0 (i.e., the actual size is coded separately) has index 1. ADD instructions with sizes from 1 to 17 use code indices 2 to 18 and their sizes are as given (so they will not be separately encoded.)
Following the single ADD instructions are the single COPY instructions ordered by their address encoding modes. For example, line 11 shows the COPY instructions with mode 8, i.e., the last of the same cache. In this case, the COPY instruction with size field 0 has index 147. Again, the actual size of this instruction will be coded separately.
Following the single ADD instructions are the single COPY instructions ordered by their address encoding modes. For example, line 11 shows the COPY instructions with mode 8, i.e., the last of the same cache. In this case, the COPY instruction with size field 0 has index 147. Again, the actual size of this instruction will be coded separately.
Lines 12 to 21 show the pairs of instructions that are combined together. For example, line 12 depicts the 12 entries in which an ADD instruction is combined with an immediately following COPY instruction. The entries with indices 163, 164, 165 represent the pairs in which the ADD instructions all have size 1, while the COPY instructions have mode 0 (VCD_SELF) and sizes 4, 5 and 6 respectively.
Lines 12 to 21 show the pairs of instructions that are combined together. For example, line 12 depicts the 12 entries in which an ADD instruction is combined with an immediately following COPY instruction. The entries with indices 163, 164, 165 represent the pairs in which the ADD instructions all have size 1, while the COPY instructions have mode 0 (VCD_SELF) and sizes 4, 5 and 6 respectively.
The last line, line 21, shows the eight instruction pairs, where the first instruction is a COPY and the second is an ADD. In this case, all COPY instructions have size 4 with mode ranging from 0 to 8 and all the ADD instructions have size 1. Thus, the entry with the largest index 255 combines a COPY instruction of size 4 and mode 8 with an ADD instruction of size 1.
The last line, line 21, shows the eight instruction pairs, where the first instruction is a COPY and the second is an ADD. In this case, all COPY instructions have size 4 with mode ranging from 0 to 8 and all the ADD instructions have size 1. Thus, the entry with the largest index 255 combines a COPY instruction of size 4 and mode 8 with an ADD instruction of size 1.
The choice of the minimum size 4 for COPY instructions in the default code table was made from experiments that showed that excluding small matches (less then 4 bytes long) improved the compression rates.
The choice of the minimum size 4 for COPY instructions in the default code table was made from experiments that showed that excluding small matches (less then 4 bytes long) improved the compression rates.
Korn, et. al. Standards Track [Page 19] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 19] RFC 3284 VCDIFF June 2002
6. Decoding a Target Window
6. Decoding a Target Window
Section 4.3 discusses that the delta instructions and associated data are encoded in three arrays of bytes:
Section 4.3 discusses that the delta instructions and associated data are encoded in three arrays of bytes:
Data section for ADDs and RUNs,
Instructions and sizes section, and
Addresses section for COPYs.
Data section for ADDs and RUNs, Instructions and sizes section, and Addresses section for COPYs.
Further, these data sections may have been further compressed by some secondary compressor. Assuming that any such compressed data has been decompressed so that we now have three arrays:
Further, these data sections may have been further compressed by some secondary compressor. Assuming that any such compressed data has been decompressed so that we now have three arrays:
inst: bytes coding the instructions and sizes.
data: unmatched data associated with ADDs and RUNs.
addr: bytes coding the addresses of COPYs.
inst: bytes coding the instructions and sizes. data: unmatched data associated with ADDs and RUNs. addr: bytes coding the addresses of COPYs.
These arrays are organized as follows:
These arrays are organized as follows:
inst: a sequence of (index, [size1], [size2]) tuples, where
"index" is an index into the instruction code table, and
size1 and size2 are integers that MAY or MAY NOT be included
in the tuple as follows. The entry with the given "index"
in the instruction code table potentially defines two delta
instructions. If the first delta instruction is not a
VCD_NOOP and its size is zero, then size1 MUST be present.
Otherwise, size1 MUST be omitted and the size of the
instruction (if it is not VCD_NOOP) is as defined in the
table. The presence or absence of size2 is defined
similarly with respect to the second delta instruction.
inst: a sequence of (index, [size1], [size2]) tuples, where "index" is an index into the instruction code table, and size1 and size2 are integers that MAY or MAY NOT be included in the tuple as follows. The entry with the given "index" in the instruction code table potentially defines two delta instructions. If the first delta instruction is not a VCD_NOOP and its size is zero, then size1 MUST be present. Otherwise, size1 MUST be omitted and the size of the instruction (if it is not VCD_NOOP) is as defined in the table. The presence or absence of size2 is defined similarly with respect to the second delta instruction.
data: a sequence of data values, encoded as bytes.
data: a sequence of data values, encoded as bytes.
addr: a sequence of address values. Addresses are normally
encoded as integers as described in Section 2 (i.e., base
128). However, since the same cache emits addresses in the
range [0,255], same cache addresses are always encoded as a
single byte.
addr: a sequence of address values. Addresses are normally encoded as integers as described in Section 2 (i.e., base 128). However, since the same cache emits addresses in the range [0,255], same cache addresses are always encoded as a single byte.
To summarize, each tuple in the "inst" array includes an index to some entry in the instruction code table that determines:
To summarize, each tuple in the "inst" array includes an index to some entry in the instruction code table that determines:
a. Whether one or two instructions were encoded and their types.
a. Whether one or two instructions were encoded and their types.
b. If the instructions have their sizes encoded separately, these
sizes will follow, in order, in the tuple.
b. If the instructions have their sizes encoded separately, these sizes will follow, in order, in the tuple.
Korn, et. al. Standards Track [Page 20] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 20] RFC 3284 VCDIFF June 2002
c. If the instructions have accompanying data, i.e., ADDs or RUNs,
their data will be in the array "data".
c. If the instructions have accompanying data, i.e., ADDs or RUNs, their data will be in the array "data".
d. Similarly, if the instructions are COPYs, the coded addresses are
found in the array "addr".
d. Similarly, if the instructions are COPYs, the coded addresses are found in the array "addr".
The decoding procedure simply processes the arrays by reading one code index at a time, looking up the corresponding instruction code entry, then consuming the respective sizes, data and addresses following the directions in this entry. In other words, the decoder maintains an implicit next-element pointer for each array; "consuming" an instruction tuple, data, or address value implies incrementing the associated pointer.
The decoding procedure simply processes the arrays by reading one code index at a time, looking up the corresponding instruction code entry, then consuming the respective sizes, data and addresses following the directions in this entry. In other words, the decoder maintains an implicit next-element pointer for each array; "consuming" an instruction tuple, data, or address value implies incrementing the associated pointer.
For example, if during the processing of the target window, the next unconsumed tuple in the inst array has an index value of 19, then the first instruction is a COPY, whose size is found as the immediately following integer in the inst array. Since the mode of this COPY instruction is VCD_SELF, the corresponding address is found by consuming the next integer in the addr array. The data array is left intact. As the second instruction for code index 19 is a NOOP, this tuple is finished.
For example, if during the processing of the target window, the next unconsumed tuple in the inst array has an index value of 19, then the first instruction is a COPY, whose size is found as the immediately following integer in the inst array. Since the mode of this COPY instruction is VCD_SELF, the corresponding address is found by consuming the next integer in the addr array. The data array is left intact. As the second instruction for code index 19 is a NOOP, this tuple is finished.
7. APPLICATION-DEFINED CODE TABLES
7. APPLICATION-DEFINED CODE TABLES
Although the default code table used in Vcdiff is good for general purpose encoders, there are times when other code tables may perform better. For example, to code a file with many identical segments of data, it may be advantageous to have a COPY instruction with the specific size of these data segments, so that the instruction can be encoded in a single byte. Such a special code table MUST then be encoded in the delta file so that the decoder can reconstruct it before decoding the data.
Although the default code table used in Vcdiff is good for general purpose encoders, there are times when other code tables may perform better. For example, to code a file with many identical segments of data, it may be advantageous to have a COPY instruction with the specific size of these data segments, so that the instruction can be encoded in a single byte. Such a special code table MUST then be encoded in the delta file so that the decoder can reconstruct it before decoding the data.
Vcdiff allows an application-defined code table to be specified in a delta file with the following data:
Vcdiff allows an application-defined code table to be specified in a delta file with the following data:
Size of near cache - byte
Size of same cache - byte
Compressed code table data
Size of near cache - byte Size of same cache - byte Compressed code table data
The "compressed code table data" encodes the delta between the default code table (source) and the new code table (target) in the same manner as described in Section 4.3 for encoding a target window in terms of a source window. This delta is computed using the following steps:
The "compressed code table data" encodes the delta between the default code table (source) and the new code table (target) in the same manner as described in Section 4.3 for encoding a target window in terms of a source window. This delta is computed using the following steps:
Korn, et. al. Standards Track [Page 21] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 21] RFC 3284 VCDIFF June 2002
a. Convert the new instruction code table into a string, "code", of
1536 bytes using the below steps in order:
a. Convert the new instruction code table into a string, "code", of 1536 bytes using the below steps in order:
i. Add in order the 256 bytes representing the types of the first
instructions in the instruction pairs.
ii. Add in order the 256 bytes representing the types of the
second instructions in the instruction pairs.
iii. Add in order the 256 bytes representing the sizes of the first
instructions in the instruction pairs.
iv. Add in order the 256 bytes representing the sizes of the
second instructions in the instruction pairs.
v. Add in order the 256 bytes representing the modes of the first
instructions in the instruction pairs.
vi. Add in order the 256 bytes representing the modes of the
second instructions in the instruction pairs.
i. Add in order the 256 bytes representing the types of the first instructions in the instruction pairs. ii. Add in order the 256 bytes representing the types of the second instructions in the instruction pairs. iii. Add in order the 256 bytes representing the sizes of the first instructions in the instruction pairs. iv. Add in order the 256 bytes representing the sizes of the second instructions in the instruction pairs. v. Add in order the 256 bytes representing the modes of the first instructions in the instruction pairs. vi. Add in order the 256 bytes representing the modes of the second instructions in the instruction pairs.
b. Similarly, convert the default code table into a string "dflt".
b. Similarly, convert the default code table into a string "dflt".
c. Treat the string "code" as a target window and "dflt" as the
corresponding source data and apply an encoding algorithm to
compute the delta encoding of "code" in terms of "dflt". This
computation MUST use the default code table for encoding the delta
instructions.
c. Treat the string "code" as a target window and "dflt" as the corresponding source data and apply an encoding algorithm to compute the delta encoding of "code" in terms of "dflt". This computation MUST use the default code table for encoding the delta instructions.
The decoder can then reverse the above steps to decode the compressed table data using the method of Section 6, employing the default code table, to generate the new code table. Note that the decoder does not need to know about the details of the encoding algorithm used in step (c). It is able to decode the new code table because the Vcdiff format is independent from the choice of encoding algorithm, and because the encoder in step (c) uses the known, default code table.
The decoder can then reverse the above steps to decode the compressed table data using the method of Section 6, employing the default code table, to generate the new code table. Note that the decoder does not need to know about the details of the encoding algorithm used in step (c). It is able to decode the new code table because the Vcdiff format is independent from the choice of encoding algorithm, and because the encoder in step (c) uses the known, default code table.
8. Performance
8. Performance
The encoding format is compact. For compression only, using the LZ- 77 string parsing strategy and without any secondary compressors, the typical compression rate is better than Unix compress and close to gzip. For differencing, the data format is better than all known methods in terms of its stated goal, which is primarily decoding speed and encoding efficiency.
The encoding format is compact. For compression only, using the LZ- 77 string parsing strategy and without any secondary compressors, the typical compression rate is better than Unix compress and close to gzip. For differencing, the data format is better than all known methods in terms of its stated goal, which is primarily decoding speed and encoding efficiency.
We compare the performance of compress, gzip and Vcdiff using the archives of three versions of the Gnu C compiler, gcc-2.95.1.tar, gcc-2.95.2.tar and gcc-2.95.3.tar. Gzip was used at its default compression level. The Vcdiff data were obtained using the Vcodex/Vcdiff software (Section 13).
We compare the performance of compress, gzip and Vcdiff using the archives of three versions of the Gnu C compiler, gcc-2.95.1.tar, gcc-2.95.2.tar and gcc-2.95.3.tar. Gzip was used at its default compression level. The Vcdiff data were obtained using the Vcodex/Vcdiff software (Section 13).
Korn, et. al. Standards Track [Page 22] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 22] RFC 3284 VCDIFF June 2002
Below are the different Vcdiff runs:
Below are the different Vcdiff runs:
Vcdiff: vcdiff is used as a compressor only.
Vcdiff: vcdiff is used as a compressor only.
Vcdiff-d: vcdiff is used as a differencer only. That is, it only
compares target data against source data. Since the files
involved are large, they are broken into windows. In this
case, each target window, starting at some file offset in the
target file, is compared against a source window with the same
file offset (in the source file). The source window is also
slightly larger than the target window to increase matching
opportunities.
Vcdiff-d: vcdiff is used as a differencer only. That is, it only compares target data against source data. Since the files involved are large, they are broken into windows. In this case, each target window, starting at some file offset in the target file, is compared against a source window with the same file offset (in the source file). The source window is also slightly larger than the target window to increase matching opportunities.
Vcdiff-dc: This is similar to Vcdiff-d, but vcdiff can also
compare target data against target data as applicable. Thus,
vcdiff both computes differences and compresses data. The
windowing algorithm is the same as above. However, the above
hint is recinded in this case.
Vcdiff-dc: This is similar to Vcdiff-d, but vcdiff can also compare target data against target data as applicable. Thus, vcdiff both computes differences and compresses data. The windowing algorithm is the same as above. However, the above hint is recinded in this case.
Vcdiff-dcw: This is similar to Vcdiff-dc but the windowing
algorithm uses a content-based heuristic to select a source
window that is more likely to match with a given target window.
Thus, the source data segment selected for a target window
often will not be aligned with the file offsets of this target
window.
Vcdiff-dcw: This is similar to Vcdiff-dc but the windowing algorithm uses a content-based heuristic to select a source window that is more likely to match with a given target window. Thus, the source data segment selected for a target window often will not be aligned with the file offsets of this target window.
gcc-2.95.1 gcc-2.95.2 gcc-2.95.3
---------------------------------------------------------
1. raw size 55,746,560 55,797,760 55,787,520
2. compress - 19,939,390 19,939,453
3. gzip - 12,973,443 12,998,097
4. Vcdiff - 15,358,786 15,371,737
5. Vcdiff-d - 100,971 26,383,849
6. Vcdiff-dc - 97,246 14,461,203
7. Vcdiff-dcw - 256,445 1,248,543
gcc-2.95.1 gcc-2.95.2 gcc-2.95.3 --------------------------------------------------------- 1. raw size 55,746,560 55,797,760 55,787,520 2. compress - 19,939,390 19,939,453 3. gzip - 12,973,443 12,998,097 4. Vcdiff - 15,358,786 15,371,737 5. Vcdiff-d - 100,971 26,383,849 6. Vcdiff-dc - 97,246 14,461,203 7. Vcdiff-dcw - 256,445 1,248,543
The above table shows the raw sizes of the tar files and the sizes of the compressed results. The differencing results in the gcc-2.95.2 column were obtained by compressing gcc-2.95.2, given gcc-2.95.1. The same results for the column gcc-2.95.3 were obtained by compressing gcc-2.95.3, given gcc-2.95.2.
The above table shows the raw sizes of the tar files and the sizes of the compressed results. The differencing results in the gcc-2.95.2 column were obtained by compressing gcc-2.95.2, given gcc-2.95.1. The same results for the column gcc-2.95.3 were obtained by compressing gcc-2.95.3, given gcc-2.95.2.
Rows 2, 3 and 4 show that, for compression only, the compression rate from Vcdiff is worse than gzip and better than compress.
Rows 2, 3 and 4 show that, for compression only, the compression rate from Vcdiff is worse than gzip and better than compress.
Korn, et. al. Standards Track [Page 23] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 23] RFC 3284 VCDIFF June 2002
The last three rows in the column gcc-2.95.2 show that when two file versions are very similar, differencing can give dramatically good compression rates. Vcdiff-d and Vcdiff-dc use the same simple window selection method of aligning by file offsets, but Vcdiff-dc also does compression so its output is slightly smaller. Vcdiff-dcw uses a content-based algorithm to search for source data that likely will match a given target window. Although it does a good job, the algorithm does not always find the best matches, which in this case, are given by the simple algorithm of Vcdiff-d. As a result, the output size for Vcdiff-dcw is slightly larger.
The last three rows in the column gcc-2.95.2 show that when two file versions are very similar, differencing can give dramatically good compression rates. Vcdiff-d and Vcdiff-dc use the same simple window selection method of aligning by file offsets, but Vcdiff-dc also does compression so its output is slightly smaller. Vcdiff-dcw uses a content-based algorithm to search for source data that likely will match a given target window. Although it does a good job, the algorithm does not always find the best matches, which in this case, are given by the simple algorithm of Vcdiff-d. As a result, the output size for Vcdiff-dcw is slightly larger.
The situation is reversed in the gcc-2.95.3 column. Here, the files and their contents were sufficiently rearranged or changed between the making of the gcc-2.95.3.tar archive and the gcc-2.95.2 archive so that the simple method of aligning windows by file offsets no longer works. As a result, Vcdiff-d and Vcdiff-dc do not perform well. By allowing compression, along with differencing, Vcdiff-dc manages to beat Vcdiff-c, which does compression only. The content- based window matching algorithm in Vcdiff-dcw is effective in matching the right source and target windows so that Vcdiff-dcw is the overall winner.
The situation is reversed in the gcc-2.95.3 column. Here, the files and their contents were sufficiently rearranged or changed between the making of the gcc-2.95.3.tar archive and the gcc-2.95.2 archive so that the simple method of aligning windows by file offsets no longer works. As a result, Vcdiff-d and Vcdiff-dc do not perform well. By allowing compression, along with differencing, Vcdiff-dc manages to beat Vcdiff-c, which does compression only. The content- based window matching algorithm in Vcdiff-dcw is effective in matching the right source and target windows so that Vcdiff-dcw is the overall winner.
9. Further Issues
9. Further Issues
This document does not address a few issues:
This document does not address a few issues:
Secondary compressors:
As discussed in Section 4.3, certain sections in the delta
encoding of a window may be further compressed by a secondary
compressor. In our experience, the basic Vcdiff format is
adequate for most purposes so that secondary compressors are
seldom needed. In particular, for normal use of data
differencing, where the files to be compared have long stretches
of matches, much of the gain in compression rate is already
achieved by normal string matching. Thus, the use of secondary
compressors is seldom needed in this case. However, for
applications beyond differencing of such nearly identical files,
secondary compressors may be needed to achieve maximal compressed
results.
Secondary compressors: As discussed in Section 4.3, certain sections in the delta encoding of a window may be further compressed by a secondary compressor. In our experience, the basic Vcdiff format is adequate for most purposes so that secondary compressors are seldom needed. In particular, for normal use of data differencing, where the files to be compared have long stretches of matches, much of the gain in compression rate is already achieved by normal string matching. Thus, the use of secondary compressors is seldom needed in this case. However, for applications beyond differencing of such nearly identical files, secondary compressors may be needed to achieve maximal compressed results.
Therefore, we recommend leaving the Vcdiff data format defined as
in this document so that the use of secondary compressors can be
implemented when they become needed in the future. The formats of
the compressed data via such compressors or any compressors that
may be defined in the future are left open to their
implementations. These could include Huffman encoding, arithmetic
encoding, and splay tree encoding [8,9].
Therefore, we recommend leaving the Vcdiff data format defined as in this document so that the use of secondary compressors can be implemented when they become needed in the future. The formats of the compressed data via such compressors or any compressors that may be defined in the future are left open to their implementations. These could include Huffman encoding, arithmetic encoding, and splay tree encoding [8,9].
Korn, et. al. Standards Track [Page 24] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 24] RFC 3284 VCDIFF June 2002
Large file system vs. small file system:
As discussed in Section 4, a target window in a large file may be
compared against some source window in another file or in the same
file (from some earlier part). In that case, the file offset of
the source window is specified as a variable-sized integer in the
delta encoding. There is a possibility that the encoding was
computed on a system supporting much larger files than in a system
where the data may be decoded (e.g., 64-bit file systems vs. 32-
bit file systems). In that case, some target data may not be
recoverable. This problem could afflict any compression format,
and ought to be resolved with a generic negotiation mechanism in
the appropriate protocol(s).
Large file system vs. small file system: As discussed in Section 4, a target window in a large file may be compared against some source window in another file or in the same file (from some earlier part). In that case, the file offset of the source window is specified as a variable-sized integer in the delta encoding. There is a possibility that the encoding was computed on a system supporting much larger files than in a system where the data may be decoded (e.g., 64-bit file systems vs. 32- bit file systems). In that case, some target data may not be recoverable. This problem could afflict any compression format, and ought to be resolved with a generic negotiation mechanism in the appropriate protocol(s).
10. Summary
10. Summary
We have described Vcdiff, a general and portable encoding format for compression and differencing. The format is good in that it allows implementing a decoder without knowledge of the encoders. Further, ignoring the use of secondary compressors not defined within the format, the decoding algorithms run in linear time and requires working space proportional to window size.
We have described Vcdiff, a general and portable encoding format for compression and differencing. The format is good in that it allows implementing a decoder without knowledge of the encoders. Further, ignoring the use of secondary compressors not defined within the format, the decoding algorithms run in linear time and requires working space proportional to window size.
11. Acknowledgements
11. Acknowledgements
Thanks are due to Balachander Krishnamurthy, Jeff Mogul and Arthur Van Hoff who provided much encouragement to publicize Vcdiff. In particular, Jeff helped in clarifying the description of the data format presented here.
Thanks are due to Balachander Krishnamurthy, Jeff Mogul and Arthur Van Hoff who provided much encouragement to publicize Vcdiff. In particular, Jeff helped in clarifying the description of the data format presented here.
12. Security Considerations
12. Security Considerations
Vcdiff only provides a format to encode compressed and differenced data. It does not address any issues concerning how such data are, in fact, stored in a given file system or the run-time memory of a computer system. Therefore, we do not anticipate any security issues with respect to Vcdiff.
Vcdiff only provides a format to encode compressed and differenced data. It does not address any issues concerning how such data are, in fact, stored in a given file system or the run-time memory of a computer system. Therefore, we do not anticipate any security issues with respect to Vcdiff.
13. Source Code Availability
13. Source Code Availability
Vcdiff is implemented as a data transforming method in Phong Vo's Vcodex library. AT&T Corp. has made the source code for Vcodex available for anyone to use to transmit data via HTTP/1.1 Delta Encoding [10,11]. The source code and according license is accessible at the below URL:
Vcdiff is implemented as a data transforming method in Phong Vo's Vcodex library. AT&T Corp. has made the source code for Vcodex available for anyone to use to transmit data via HTTP/1.1 Delta Encoding [10,11]. The source code and according license is accessible at the below URL:
http://www.research.att.com/sw/tools
http://www.research.att.com/sw/tools
Korn, et. al. Standards Track [Page 25] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 25] RFC 3284 VCDIFF June 2002
14. Intellectual Property Rights
14. Intellectual Property Rights
The IETF has been notified of intellectual property rights claimed in regard to some or all of the specification contained in this document. For more information consult the online list of claimed rights, at <http://www.ietf.org/ipr.html>.
The IETF has been notified of intellectual property rights claimed in regard to some or all of the specification contained in this document. For more information consult the online list of claimed rights, at <http://www.ietf.org/ipr.html>.
The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards-related documentation can be found in BCP 11. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can be obtained from the IETF Secretariat.
The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards-related documentation can be found in BCP 11. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can be obtained from the IETF Secretariat.
15. IANA Considerations
15. IANA Considerations
The Internet Assigned Numbers Authority (IANA) administers the number space for Secondary Compressor ID values. Values and their meaning must be documented in an RFC or other peer-reviewed, permanent, and readily available reference, in sufficient detail so that interoperability between independent implementations is possible. Subject to these constraints, name assignments are First Come, First Served - see RFC 2434 [13]. Legal ID values are in the range 1..255.
The Internet Assigned Numbers Authority (IANA) administers the number space for Secondary Compressor ID values. Values and their meaning must be documented in an RFC or other peer-reviewed, permanent, and readily available reference, in sufficient detail so that interoperability between independent implementations is possible. Subject to these constraints, name assignments are First Come, First Served - see RFC 2434 [13]. Legal ID values are in the range 1..255.
This document does not define any values in this number space.
This document does not define any values in this number space.
16. References
16. References
[1] D.G. Korn and K.P. Vo, Vdelta: Differencing and Compression,
Practical Reusable Unix Software, Editor B. Krishnamurthy, John
Wiley & Sons, Inc., 1995.
[1] D.G. Korn and K.P. Vo, Vdelta: Differencing and Compression, Practical Reusable Unix Software, Editor B. Krishnamurthy, John Wiley & Sons, Inc., 1995.
[2] J. Ziv and A. Lempel, A Universal Algorithm for Sequential Data
Compression, IEEE Trans. on Information Theory, 23(3):337-343,
1977.
[2] J. Ziv and A. Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Trans. on Information Theory, 23(3):337-343, 1977.
[3] W. Tichy, The String-to-String Correction Problem with Block
Moves, ACM Transactions on Computer Systems, 2(4):309-321,
November 1984.
[3] W. Tichy, The String-to-String Correction Problem with Block Moves, ACM Transactions on Computer Systems, 2(4):309-321, November 1984.
Korn, et. al. Standards Track [Page 26] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 26] RFC 3284 VCDIFF June 2002
[4] E.M. McCreight, A Space-Economical Suffix Tree Construction
Algorithm, Journal of the ACM, 23:262-272, 1976.
[4] E.M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM, 23:262-272, 1976.
[5] J.J. Hunt, K.P. Vo, W. Tichy, An Empirical Study of Delta
Algorithms, IEEE Software Configuration and Maintenance
Workshop, 1996.
[5] J.J. Hunt, K.P. Vo, W. Tichy, An Empirical Study of Delta Algorithms, IEEE Software Configuration and Maintenance Workshop, 1996.
[6] J.J. Hunt, K.P. Vo, W. Tichy, Delta Algorithms: An Empirical
Analysis, ACM Trans. on Software Engineering and Methodology,
7:192-214, 1998.
[6] J.J. Hunt, K.P. Vo, W. Tichy, Delta Algorithms: An Empirical Analysis, ACM Trans. on Software Engineering and Methodology, 7:192-214, 1998.
[7] D.G. Korn, K.P. Vo, Sfio: A buffered I/O Library, Proc. of the
Summer '91 Usenix Conference, 1991.
[7] D.G. Korn, K.P. Vo, Sfio: A buffered I/O Library, Proc. of the Summer '91 Usenix Conference, 1991.
[8] D. W. Jones, Application of Splay Trees to Data Compression,
CACM, 31(8):996:1007.
[8] D. W. Jones, Application of Splay Trees to Data Compression, CACM, 31(8):996:1007.
[9] M. Nelson, J. Gailly, The Data Compression Book, ISBN 1-55851-
434-1, M&T Books, New York, NY, 1995.
[9] M. Nelson, J. Gailly, The Data Compression Book, ISBN 1-55851- 434-1, M&T Books, New York, NY, 1995.
[10] J.C. Mogul, F. Douglis, A. Feldmann, and B. Krishnamurthy,
Potential benefits of delta encoding and data compression for
HTTP, SIGCOMM '97, Cannes, France, 1997.
[10] J.C. Mogul, F. Douglis, A. Feldmann, and B. Krishnamurthy, Potential benefits of delta encoding and data compression for HTTP, SIGCOMM '97, Cannes, France, 1997.
[11] Mogul, J., Krishnamurthy, B., Douglis, F., Feldmann, A., Goland,
Y. and A. Van Hoff, "Delta Encoding in HTTP", RFC 3229, January
2002.
[11] Mogul, J., Krishnamurthy, B., Douglis, F., Feldmann, A., Goland, Y. and A. Van Hoff, "Delta Encoding in HTTP", RFC 3229, January 2002.
[12] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
[12] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[13] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA
Considerations Section in RFCs", BCP 26, RFC 2434, October 1998.
[13] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 2434, October 1998.
[14] D.G. Korn and K.P. Vo, Engineering a Differencing and
Compression Data Format, Submitted to Usenix'2002, 2001.
[14] D.G. Korn and K.P. Vo, Engineering a Differencing and Compression Data Format, Submitted to Usenix'2002, 2001.
Korn, et. al. Standards Track [Page 27] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 27] RFC 3284 VCDIFF June 2002
17. Authors' Addresses
17. Authors' Addresses
Kiem-Phong Vo (main contact) AT&T Labs, Room D223 180 Park Avenue Florham Park, NJ 07932
Kiem-Phong Vo (main contact) AT&T Labs, Room D223 180 Park Avenue Florham Park, NJ 07932
Phone: 1 973 360 8630 EMail: kpv@research.att.com
Phone: 1 973 360 8630 EMail: kpv@research.att.com
David G. Korn AT&T Labs, Room D237 180 Park Avenue Florham Park, NJ 07932
David G. Korn AT&T Labs, Room D237 180 Park Avenue Florham Park, NJ 07932
Phone: 1 973 360 8602 EMail: dgk@research.att.com
Phone: 1 973 360 8602 EMail: dgk@research.att.com
Jeffrey C. Mogul Western Research Laboratory Hewlett-Packard Company 1501 Page Mill Road, MS 1251 Palo Alto, California, 94304, U.S.A.
Jeffrey C. Mogul Western Research Laboratory Hewlett-Packard Company 1501 Page Mill Road, MS 1251 Palo Alto, California, 94304, U.S.A.
Phone: 1 650 857 2206 (email preferred) EMail: JeffMogul@acm.org
Phone: 1 650 857 2206 (email preferred) EMail: JeffMogul@acm.org
Joshua P. MacDonald Computer Science Division University of California, Berkeley 345 Soda Hall Berkeley, CA 94720
Joshua P. MacDonald Computer Science Division University of California, Berkeley 345 Soda Hall Berkeley, CA 94720
EMail: jmacd@cs.berkeley.edu
EMail: jmacd@cs.berkeley.edu
Korn, et. al. Standards Track [Page 28] RFC 3284 VCDIFF June 2002
Korn, et. al. Standards Track [Page 28] RFC 3284 VCDIFF June 2002
18. Full Copyright Statement
18. Full Copyright Statement
Copyright (C) The Internet Society (2002). All Rights Reserved.
Copyright (C) The Internet Society (2002). All Rights Reserved.
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Acknowledgement
Funding for the RFC Editor function is currently provided by the Internet Society.
Funding for the RFC Editor function is currently provided by the Internet Society.
Korn, et. al. Standards Track [Page 29]
Korn, et. al. Standards Track [Page 29]
一覧
スポンサーリンク
