forked from pleonex/xdelta-sharp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
rfc3284.txt
1627 lines (1087 loc) · 62.5 KB
/
rfc3284.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
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
The VCDIFF Generic Differencing and Compression Data Format
Status of this 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.
Copyright Notice
Copyright (C) The Internet Society (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.
Korn, et. al. Standards Track [Page 1]
RFC 3284 VCDIFF June 2002
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. Executive Summary
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.
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.
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:
Korn, et. al. Standards Track [Page 2]
RFC 3284 VCDIFF June 2002
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.
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.
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.
The encoding format Vcdiff proposed here addresses the above issues.
Vcdiff achieves the characteristics below:
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.
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.
Korn, et. al. Standards Track [Page 3]
RFC 3284 VCDIFF June 2002
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.
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.
2. Conventions
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.
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.
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:
a. The encoding is portable among systems using 8-bit bytes, and
b. Small values are encoded compactly.
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.
+-------------------------------------------+
| 10111010 | 11101111 | 10011010 | 00010101 |
+-------------------------------------------+
MSB+58 MSB+111 MSB+26 0+21
Korn, et. al. Standards Track [Page 4]
RFC 3284 VCDIFF June 2002
Henceforth, the terms "byte" and "integer" will refer to a byte and
an unsigned integer as described.
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.
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].
3. Delta Instructions
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.
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.
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[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.
The instructions to encode and direct the reconstruction of a target
window are called delta instructions. There are three types:
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.
Korn, et. al. Standards Track [Page 5]
RFC 3284 VCDIFF June 2002
RUN: This instruction has two arguments, a size x and a byte b,
that will be repeated x times.
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
COPY 4, 0
ADD 4, w x y z
COPY 4, 4
COPY 12, 24
RUN 4, 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.
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.
4. Delta File Organization
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.
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.
Korn, et. al. Standards Track [Page 6]
RFC 3284 VCDIFF June 2002
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
...
4.1 The Header Section
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]
Korn, et. al. Standards Track [Page 7]
RFC 3284 VCDIFF June 2002
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.
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:
7 6 5 4 3 2 1 0
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
^ ^
| |
| +-- VCD_DECOMPRESS
+---- 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.
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.
If both bits are set, then the compressor ID byte is included before
the code table data length and the code table data.
4.2 The Format of a Window Section
Each Window section is organized as follows:
Win_Indicator - byte
[Source segment length] - integer
[Source segment position] - integer
The delta encoding of the target window
Korn, et. al. Standards Track [Page 8]
RFC 3284 VCDIFF June 2002
Below are the details of the various items:
Win_Indicator:
This byte is a set of bits, as shown:
7 6 5 4 3 2 1 0
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
^ ^
| |
| +-- VCD_SOURCE
+---- VCD_TARGET
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.
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.
The Win_Indicator byte MUST NOT have more than one of the bits
set (non-zero). It MAY have none of these bits set.
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.
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.
Korn, et. al. Standards Track [Page 9]
RFC 3284 VCDIFF June 2002
4.3 The Delta Encoding of a Target Window
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
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:
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.
Korn, et. al. Standards Track [Page 10]
RFC 3284 VCDIFF June 2002
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:
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.
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.
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.
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.
Data section for ADDs and RUNs:
This sequence of bytes encodes the unmatched data for the ADD
and RUN instructions.
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.
Korn, et. al. Standards Track [Page 11]
RFC 3284 VCDIFF June 2002
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.
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.
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.
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.
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.
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.]
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:
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;
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;
}
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;
}
Korn, et. al. Standards Track [Page 13]
RFC 3284 VCDIFF June 2002
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.
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_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]".
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
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.
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;
/* 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 */
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; }
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);
*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.
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
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()];
}
cache_update(ka, addr);
return addr;
}
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.
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
Each instruction code entry contains six fields, each of which is a
single byte with an unsigned value:
+-----------------------------------------------+
| inst1 | size1 | mode1 | inst2 | size2 | mode2 |
+-----------------------------------------------+
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.
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.
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:
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.
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]
---------------------------------------------------------------
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).