File: rfc3284.txt

package info (click to toggle)
doc-rfc 20181229-2
  • links: PTS, VCS
  • area: non-free
  • in suites: buster
  • size: 570,944 kB
  • sloc: xml: 285,646; sh: 107; python: 90; perl: 42; makefile: 14
file content (1627 lines) | stat: -rw-r--r-- 64,035 bytes parent folder | download | duplicates (5)
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
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627






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).

   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


   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:

   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.)

   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.

   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.









Korn, et. al.               Standards Track                    [Page 19]

RFC 3284                         VCDIFF                        June 2002


6. Decoding a Target Window

   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.

   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.

   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.

      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.

   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.

   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


   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".

   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.

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.

   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

   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


   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.

   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.

   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

   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).





Korn, et. al.               Standards Track                    [Page 22]

RFC 3284                         VCDIFF                        June 2002


   Below are the different Vcdiff runs:

      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-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.

                       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.

   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


   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.

9. Further 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.

      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


   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

   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

   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

   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

   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





Korn, et. al.               Standards Track                    [Page 25]

RFC 3284                         VCDIFF                        June 2002


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 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

   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.

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.

   [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.





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.

   [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.

   [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.

   [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.

   [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.

   [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.















Korn, et. al.               Standards Track                    [Page 27]

RFC 3284                         VCDIFF                        June 2002


17. Authors' Addresses

   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


   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


   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


   Joshua P. MacDonald
   Computer Science Division
   University of California, Berkeley
   345 Soda Hall
   Berkeley, CA 94720

   EMail: jmacd@cs.berkeley.edu














Korn, et. al.               Standards Track                    [Page 28]

RFC 3284                         VCDIFF                        June 2002


18.  Full Copyright Statement

   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.

   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.

Acknowledgement

   Funding for the RFC Editor function is currently provided by the
   Internet Society.



















Korn, et. al.               Standards Track                    [Page 29]