%!PS-Adobe-2.0
%%Creator: dvipsk 5.55a Copyright 1986, 1994 Radical Eye Software
%%Title: rfc-deflate-a4.ps
%%Pages: 15
%%PageOrder: Ascend
%%BoundingBox: 0 0 612 792
%%DocumentFonts: Times-Roman Times-Bold Times-Italic Courier
%%EndComments
%DVIPSCommandLine: dvips -D 300 -o deflate-a4.ps deflate-a4.dvi
%DVIPSParameters: dpi=300, compressed, comments removed
%DVIPSSource:  TeX output 1996.05.23:2044
%%BeginProcSet: texc.pro
/TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N
/X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72
mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1}
ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale
isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div
hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul
TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if}
forall round exch round exch]setmatrix}N /@landscape{/isls true N}B
/@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B
/FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{
/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N
string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N
end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{
/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]
N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup
length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{
128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub
get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data
dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N
/rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup
/base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx
0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff
setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff
1 sub]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N
/cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id
gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp
add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add
/gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{
dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1
adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2
idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string
putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval
adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg}
{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{
adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2
chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{]
}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup
length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{
cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin
0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul
add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage
userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook
known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X
/IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for
65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0
0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V
{}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7
getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}
ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false
RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1
false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform
round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg
rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail
{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M}
B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{
4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{
p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p
a}B /bos{/SS save N}B /eos{SS restore}B end
%%EndProcSet
%%BeginProcSet: texps.pro
TeXDict begin /rf{findfont dup length 1 add dict begin{1 index /FID ne 2
index /UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll
exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics
exch def dict begin Encoding{exch dup type /integertype ne{pop pop 1 sub
dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def}
ifelse}forall Metrics /Metrics currentdict end def[2 index currentdict
end definefont 3 -1 roll makefont /setfont load]cvx def}def
/ObliqueSlant{dup sin S cos div neg}B /SlantFont{4 index mul add}def
/ExtendFont{3 -1 roll mul exch}def /ReEncodeFont{/Encoding exch def}def
end
%%EndProcSet
TeXDict begin 40258431 52099146 1000 300 300 (deflate-a4.dvi)
@start /Fa 133[25 25 25 25 25 25 25 25 25 1[25 25 25
25 25 25 25 25 25 25 25 25 25 25 25 25 12[25 25 4[25
1[25 2[25 25 2[25 25 25 25 4[25 25 25 25 25 25 25 25
25 25 25 25 25 25 25 25 25 25 25 1[25 25 4[25 35[{}57
41.666668 /Courier rf /Fb 69[23 10[25 25 3[23 48[23 23
33 1[25 15 18 20 1[25 23 25 38 13 25 1[13 25 23 15 20
25 20 25 23 7[33 3[33 30 25 2[28 1[33 5[35 2[30 33 33
30 4[26 5[23 23 23 23 23 23 23 23 1[11 15 3[15 15 40[{}50
45.624989 /Times-Bold rf /Fc 60[27 70[27 1[27 27 27 27
27 27 27 27 27 1[27 27 27 27 27 27 1[27 27 27 27 27 27
27 27 27 3[27 27 27 1[27 27 1[27 1[27 27 27 1[27 1[27
27 27 1[27 27 27 27 27 27 27 27 27 27 27 1[27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 1[27
27 6[27 33[{}73 45.624989 /Courier rf /Fd 81[28 55[25
28 17 19 22 1[28 25 28 41 14 28 1[14 28 25 17 22 28 22
28 25 13[28 2[30 39 5[19 4[36 36 12[25 25 25 25 25 25
2[12 46[{}34 50.000000 /Times-Bold rf /Fe 141[18 1[23
23 5[13 7[23 97[{}5 45.624989 /Times-Italic rf /Ff 2
63 df<EC01C0EC0780EC1E001478EB01E0EB0780010EC7FC133C13F0EA03C0000FC8FC12
3C12F0A2123C120FEA03C0EA00F0133C130E6D7EEB01E0EB0078141EEC0780EC01C01A1A
7C9723>60 D<12E01278121EEA0780EA01E0EA0078131C130FEB03C0EB00F0143C140FEC
03C0A2EC0F00143C14F0EB03C0010FC7FC131C1378EA01E0EA0780001EC8FC127812E01A
1A7C9723>62 D E /Fg 4 104 df<EB01FE90380FFFC090383E01F09038F0003CD801C0
130E48487F48C7EA0380000EEC01C0000C1400001C15E048157000301530A20070153800
601518A200E0151C48150CA96C151C00601518A20070153800301530A2003815706C15E0
000C15C0000E14016CEC03806C6CEB07006C6C130ED800F0133C90383E01F090380FFFC0
D901FEC7FC262B7DA02D>13 D<EA07E0EA1FF8EA3FFCEA7FFEA2B5FCA8EA7FFEA2EA3FFC
EA1FF8EA07E010127D9317>15 D<130F1338136013E0EA01C0AFEA0380EA0700121E12F8
121E1207EA0380EA01C0AFEA00E013601338130F102D7DA117>102
D<12F8121E1207EA0380EA01C0AFEA00E013601338130F1338136013E0EA01C0AFEA0380
EA0700121E12F8102D7DA117>I E /Fh 81[33 52[30 1[43 30
33 20 23 27 1[33 30 33 50 17 33 1[17 33 30 20 27 33 27
33 30 12[40 33 43 3[43 56 3[23 1[47 1[40 43 43 1[43 6[20
30 30 30 30 30 30 30 30 30 9[20 39[{}45 59.999973 /Times-Bold
rf /Fi 81[40 55[36 1[20 28 24 1[36 36 36 56 3[20 3[32
36 32 1[32 12[44 40 6[44 5[40 44 52 48 1[52 13[36 1[36
2[18 46[{}25 72.000000 /Times-Roman rf /Fj 69[20 10[25
25 3[20 47[20 23 23 33 23 23 13 18 15 23 23 23 23 35
13 23 13 13 23 23 15 20 23 20 23 20 3[15 1[15 28 33 33
43 33 33 28 25 30 33 25 33 33 40 28 33 18 15 33 33 25
28 33 30 30 33 3[26 1[13 13 23 23 23 23 23 23 23 23 23
23 13 11 15 11 26 23 15 15 15 1[38 37[{}81 45.624989
/Times-Roman rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 300dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop 0 195 a Fj(Network)10 b(W)l(orking)h(Group)1226
b(P)-5 b(.)12 b(Deutsch)0 252 y(Request)f(for)g(Comments:)k(1951)974
b(Aladdin)10 b(Enterprises)0 308 y(Category:)k(Informational)1244
b(May)12 b(1996)42 479 y Fi(DEFLA)-8 b(TE)17 b(Compressed)f(Data)i
(Format)f(Speci\256cation)f(version)h(1.3)0 704 y Fh(Status)e(of)g
(This)g(Memo)0 836 y Fj(This)d(memo)i(provides)e(information)g(for)h
(the)f(Internet)h(community)m(.)20 b(This)12 b(memo)i(does)f(not)f
(specify)h(an)g(Internet)0 893 y(standard)d(of)i(any)f(kind.)j
(Distribution)8 b(of)j(this)f(memo)i(is)f(unlimited.)0
1068 y Fh(IESG)k(Note:)0 1201 y Fj(The)d(IESG)h(takes)f(no)g(position)f
(on)h(the)g(validity)f(of)h(any)h(Intellectual)e(Property)h(Rights)g
(statements)f(contained)h(in)0 1257 y(this)e(document.)0
1433 y Fh(Notices)0 1565 y Fj(Copyright)208 1564 y(c)196
1565 y Fg(\015)i Fj(1996)e(L.)h(Peter)h(Deutsch)0 1651
y(Permission)c(is)g(granted)g(to)g(copy)f(and)i(distribute)d(this)h
(document)h(for)h(any)f(purpose)g(and)g(without)e(char)o(ge,)k
(including)0 1707 y(translations)e(into)h(other)g(languages)g(and)h
(incorporation)e(into)g(compilations,)h(provided)g(that)g(the)h
(copyright)e(notice)0 1764 y(and)i(this)g(notice)g(are)h(preserved,)g
(and)f(that)g(any)h(substantive)d(changes)i(or)h(deletions)d(from)k
(the)e(original)f(are)i(clearly)0 1820 y(marked.)0 1906
y(A)i(pointer)g(to)g(the)g(latest)f(version)h(of)g(this)f(and)h
(related)h(documentation)d(in)i(HTML)h(format)f(can)h(be)f(found)g(at)g
(the)0 1963 y(URL)e Ff(<)p Fj(ftp://ftp.uu.net/graphics/p)o(ng/)o
(documents)o(/zli)o(b/zdo)o(c-index.ht)o(ml)p Ff(>)p
Fj(.)0 2139 y Fh(Abstract)0 2273 y Fj(This)h(speci\256cation)f
(de\256nes)i(a)g(lossless)d(compressed)i(data)h(format)g(that)f
(compresses)g(data)h(using)e(a)i(combination)0 2329 y(of)f(the)h(LZ77)e
(algorithm)g(and)i(Huf)o(fman)f(coding,)g(with)g(ef)o(\256ciency)h
(comparable)f(to)g(the)g(best)g(currently)g(available)0
2386 y(general-purpose)f(compression)h(methods.)17 b(The)c(data)f(can)g
(be)h(produced)e(or)i(consumed,)f(even)g(for)h(an)f(arbitrarily)0
2442 y(long)g(sequentially)g(presented)g(input)g(data)h(stream,)i
(using)d(only)g(an)i Fe(a)f(priori)e Fj(bounded)i(amount)f(of)i
(intermediate)0 2499 y(storage.)h(The)c(format)g(can)h(be)f
(implemented)g(readily)f(in)h(a)h(manner)f(not)g(covered)g(by)g
(patents.)0 2869 y(Deutsch)661 b(Informational)f([Page)12
b(1])p eop
%%Page: 2 2
2 1 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)0 195 y Fh(Contents)0 298 y Fj(1)104 b(Introduction)32
b(.)23 b(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)
g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)h(.)f(.)g(.)g(.)g(.)g(.)91 b(2)68 355 y(1.1)70 b(Purpose)44
b(.)23 b(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)
g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)h(.)f(.)g(.)g(.)g(.)g(.)91 b(2)68 411 y(1.2)70 b(Intended)11
b(audience)29 b(.)23 b(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g
(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)
f(.)g(.)g(.)g(.)g(.)91 b(3)68 468 y(1.3)70 b(Scope)12
b(.)23 b(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)
g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)91 b(3)68 524 y(1.4)70
b(Compliance)40 b(.)23 b(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)
g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)91 b(3)68 581 y(1.5)82
b(De\256nitions)9 b(of)i(terms)h(and)f(conventions)e(used)26
b(.)d(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h
(.)f(.)g(.)g(.)g(.)g(.)91 b(3)68 637 y(1.6)70 b(Changes)11
b(from)h(previous)e(versions)h(.)24 b(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)
g(.)g(.)91 b(4)0 694 y(2)104 b(Compressed)11 b(representation)f
(overview)28 b(.)23 b(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g
(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)91
b(4)0 750 y(3)104 b(Detailed)11 b(speci\256cation)33
b(.)23 b(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)
g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g
(.)g(.)91 b(4)68 806 y(3.1)70 b(Overall)11 b(conventions)26
b(.)d(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)
91 b(4)173 863 y(3.1.1)54 b(Packing)11 b(into)f(bytes)38
b(.)23 b(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)
g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)91
b(5)68 919 y(3.2)70 b(Compressed)12 b(block)e(format)28
b(.)23 b(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)
g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)91
b(6)173 976 y(3.2.1)54 b(Synopsis)10 b(of)h(pre\256x)g(and)g(Huf)o
(fman)h(coding)31 b(.)23 b(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)91 b(6)173 1032 y(3.2.2)54
b(Use)11 b(of)g(Huf)o(fman)h(coding)e(in)h(the)g(\252de\257ate\272)h
(format)38 b(.)23 b(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g
(.)g(.)g(.)91 b(6)173 1089 y(3.2.3)54 b(Details)10 b(of)i(block)e
(format)20 b(.)j(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)
g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)91
b(8)173 1145 y(3.2.4)54 b(Non-compressed)11 b(blocks)f(\(BTYPE=00\))20
b(.)j(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f
(.)g(.)g(.)g(.)g(.)91 b(9)173 1202 y(3.2.5)54 b(Compressed)11
b(blocks)f(\(length)g(and)h(distance)g(codes\))24 b(.)f(.)g(.)g(.)g(.)g
(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)69 b(10)173
1258 y(3.2.6)54 b(Compression)10 b(with)h(\256xed)g(Huf)o(fman)h(codes)
e(\(BTYPE=01\))42 b(.)23 b(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g
(.)69 b(10)173 1315 y(3.2.7)54 b(Compression)10 b(with)h(dynamic)g(Huf)
o(fman)g(codes)g(\(BTYPE=10\))44 b(.)23 b(.)g(.)g(.)g(.)h(.)f(.)g(.)g
(.)g(.)g(.)70 b(1)n(1)68 1371 y(3.3)g(Compliance)40 b(.)23
b(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g
(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)
g(.)g(.)g(.)69 b(12)0 1427 y(4)104 b(Compression)11 b(algorithm)f
(details)40 b(.)23 b(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)
h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)69
b(12)0 1484 y(5)104 b(References)24 b(.)f(.)g(.)h(.)f(.)g(.)g(.)g(.)g
(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)
f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)69
b(13)0 1540 y(6)104 b(Security)11 b(Considerations)26
b(.)d(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)
69 b(14)0 1597 y(7)104 b(Source)12 b(code)35 b(.)23 b(.)h(.)f(.)g(.)g
(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)
g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g
(.)69 b(14)0 1653 y(8)104 b(Acknowledgements)33 b(.)23
b(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)
g(.)69 b(14)0 1710 y(9)104 b(Author)r(')n(s)9 b(Address)40
b(.)23 b(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)
g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g
(.)g(.)g(.)g(.)69 b(14)0 1886 y Fh(1)60 b(Intr)o(oduction)0
2022 y Fd(1.1)50 b(Purpose)0 2139 y Fj(The)11 b(purpose)f(of)i(this)e
(speci\256cation)g(is)g(to)h(de\256ne)h(a)f(lossless)e(compressed)i
(data)g(format)h(that:)68 2226 y Fg(\017)23 b Fj(Is)14
b(independent)e(of)i(CPU)g(type,)h(operating)d(system,)j(\256le)f
(system,)g(and)g(character)h(set,)f(and)g(hence)g(can)g(be)114
2283 y(used)c(for)i(interchange;)68 2370 y Fg(\017)23
b Fj(Can)18 b(be)g(produced)f(or)h(consumed,)h(even)f(for)g(an)g
(arbitrarily)e(long)h(sequentially)f(presented)h(input)f(data)114
2426 y(stream,)f(using)e(only)g(an)h Fe(a)g(priori)f
Fj(bounded)g(amount)g(of)i(intermediate)e(storage,)i(and)f(hence)g(can)
g(be)h(used)114 2483 y(in)10 b(data)h(communications)f(or)i(similar)e
(structures)g(such)h(as)g(Unix)f(\256lters;)68 2570 y
Fg(\017)23 b Fj(Compresses)10 b(data)g(with)g(ef)o(\256ciency)h
(comparable)f(to)g(the)g(best)g(currently)g(available)f
(general-purpose)h(com-)114 2626 y(pression)f(methods,)i(and)g(in)g
(particular)g(considerably)e(better)i(than)g(the)g(\252compress\272)g
(program;)68 2713 y Fg(\017)23 b Fj(Can)9 b(be)f(implemented)g(readily)
g(in)g(a)h(manner)g(not)f(covered)g(by)g(patents,)h(and)f(hence)h(can)g
(be)f(practiced)g(freely;)0 2869 y(Deutsch)661 b(Informational)f([Page)
12 b(2])p eop
%%Page: 3 3
3 2 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)68 195 y Fg(\017)23 b Fj(Is)13 b(compatible)h(with)e(the)i
(\256le)g(format)g(produced)g(by)f(the)h(current)f(widely)g(used)h
(gzip)f(utility)m(,)g(in)g(that)g(con-)114 252 y(forming)d
(decompressors)h(will)f(be)h(able)g(to)g(read)h(data)f(produced)f(by)h
(the)g(existing)e(gzip)i(compressor)n(.)0 339 y(The)g(data)g(format)h
(de\256ned)f(by)g(this)f(speci\256cation)g(does)h(not)f(attempt)h(to:)
68 426 y Fg(\017)23 b Fj(Allow)10 b(random)h(access)g(to)g(compressed)g
(data;)68 513 y Fg(\017)23 b Fj(Compress)9 b(specialized)g(data)g
(\(e.g.,)i(raster)f(graphics\))f(as)h(well)f(as)g(the)g(best)g
(currently)g(available)g(specialized)114 569 y(algorithms.)0
656 y(A)h(simple)g(counting)e(ar)o(gument)i(shows)f(that)g(no)h
(lossless)e(compression)h(algorithm)g(can)i(compress)f(every)g
(possible)0 712 y(input)g(data)g(set.)15 b(For)c(the)g(format)g
(de\256ned)g(here,)h(the)f(worst)f(case)h(expansion)e(is)i(5)g(bytes)f
(per)h(32K-byte)f(block,)g(i.e.,)0 769 y(a)k(size)g(increase)g(of)f
(0.015\045)h(for)f(lar)o(ge)h(data)g(sets.)23 b(English)11
b(text)j(usually)e(compresses)h(by)h(a)g(factor)g(of)g(2.5)f(to)h(3;)0
825 y(executable)g(\256les)g(usually)f(compress)h(somewhat)g(less;)h
(graphical)f(data)g(such)g(as)h(raster)f(images)g(may)h(compress)0
882 y(much)c(more.)0 1037 y Fd(1.2)50 b(Intended)12 b(audience)0
1154 y Fj(This)c(speci\256cation)g(is)g(intended)g(for)h(use)g(by)g
(implementors)f(of)h(software)g(to)f(compress)h(data)g(into)f
(\252de\257ate\272)i(format)0 1211 y(and/or)g(decompress)h(data)h(from)
f(\252de\257ate\272)h(format.)0 1298 y(The)g(text)g(of)g(the)g
(speci\256cation)f(assumes)h(a)h(basic)e(background)h(in)f(programming)
h(at)g(the)g(level)g(of)g(bits)g(and)g(other)0 1354 y(primitive)f(data)
h(representations.)17 b(Familiarity)12 b(with)f(the)h(technique)f(of)i
(Huf)o(fman)f(coding)f(is)h(helpful)f(but)h(not)g(re-)0
1411 y(quired.)0 1565 y Fd(1.3)50 b(Scope)0 1683 y Fj(The)10
b(speci\256cation)f(speci\256es)g(a)h(method)g(for)g(representing)f(a)h
(sequence)f(of)h(bytes)f(as)h(a)g(\(usually)f(shorter\))g(sequence)0
1739 y(of)i(bits,)g(and)g(a)g(method)g(for)g(packing)g(the)f(latter)h
(bit)g(sequence)g(into)f(bytes.)0 1894 y Fd(1.4)50 b(Compliance)0
2012 y Fj(Unless)8 b(otherwise)g(indicated)g(below)m(,)h(a)g(compliant)
f(decompressor)h(must)g(be)g(able)g(to)f(accept)i(and)f(decompress)f
(any)0 2068 y(data)h(set)g(that)f(conforms)h(to)f(all)h(the)f
(speci\256cations)g(presented)g(here;)i(a)g(compliant)d(compressor)i
(must)g(produce)f(data)0 2125 y(sets)j(that)f(conform)h(to)g(all)g(the)
g(speci\256cations)f(presented)g(here.)0 2280 y Fd(1.5)63
b(De\256nitions)11 b(of)h(terms)h(and)f(conventions)f(used)0
2397 y Fj(Byte:)16 b(8)c(bits)e(stored)h(or)h(transmitted)f(as)g(a)i
(unit)d(\(same)j(as)f(an)g(octet\).)k(For)c(this)f(speci\256cation,)g
(a)i(byte)e(is)g(exactly)g(8)0 2454 y(bits,)g(even)g(on)h(machines)f
(which)g(store)g(a)h(character)g(on)g(a)f(number)h(of)g(bits)e(dif)o
(ferent)i(from)g(eight.)j(See)e(below)m(,)e(for)0 2510
y(the)g(numbering)f(of)h(bits)f(within)g(a)i(byte.)0
2597 y(String:)i(a)d(sequence)g(of)h(arbitrary)e(bytes.)0
2869 y(Deutsch)661 b(Informational)f([Page)12 b(3])p
eop
%%Page: 4 4
4 3 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)0 195 y Fd(1.6)50 b(Changes)12 b(fr)o(om)h(pr)o(evious)f
(versions)0 311 y Fj(There)i(have)h(been)f(no)g(technical)g(changes)f
(to)h(the)g(de\257ate)h(format)g(since)e(version)h(1.1)g(of)g(this)g
(speci\256cation.)23 b(In)0 368 y(version)13 b(1.2,)j(some)f
(terminology)e(was)h(changed.)25 b(V)-5 b(ersion)13 b(1.3)i(is)f(a)h
(conversion)e(of)h(the)h(speci\256cation)e(to)h(RFC)0
424 y(style.)0 598 y Fh(2)60 b(Compr)o(essed)14 b(r)o(epr)o(esentation)
f(overview)0 731 y Fj(A)g(compressed)f(data)g(set)g(consists)f(of)i(a)g
(series)f(of)g(blocks,)g(corresponding)f(to)h(successive)g(blocks)f(of)
i(input)e(data.)0 787 y(The)g(block)f(sizes)h(are)h(arbitrary)m(,)f
(except)g(that)g(non-compressible)e(blocks)h(are)i(limited)e(to)h
(65,535)g(bytes.)0 873 y(Each)d(block)e(is)i(compressed)f(using)f(a)i
(combination)e(of)i(the)f(LZ77)g(algorithm)g(and)g(Huf)o(fman)h
(coding.)13 b(The)8 b(Huf)o(fman)0 930 y(trees)h(for)g(each)h(block)e
(are)i(independent)d(of)i(those)f(for)h(previous)f(or)h(subsequent)f
(blocks;)g(the)h(LZ77)f(algorithm)g(may)0 986 y(use)j(a)g(reference)i
(to)e(a)g(duplicated)f(string)g(occurring)g(in)h(a)h(previous)e(block,)
g(up)h(to)g(32K)f(input)g(bytes)h(before.)0 1072 y(Each)j(block)f
(consists)e(of)j(two)f(parts:)19 b(a)c(pair)e(of)h(Huf)o(fman)g(code)g
(trees)f(that)h(describe)f(the)g(representation)g(of)g(the)0
1128 y(compressed)c(data)g(part,)h(and)g(a)f(compressed)g(data)h(part.)
k(\(The)c(Huf)o(fman)f(trees)h(themselves)e(are)i(compressed)g(using)0
1185 y(Huf)o(fman)h(encoding.\))j(The)d(compressed)f(data)h(consists)e
(of)i(a)g(series)f(of)h(elements)g(of)g(two)f(types:)j(literal)d(bytes)
g(\(of)0 1241 y(strings)h(that)h(have)h(not)f(been)h(detected)f(as)h
(duplicated)e(within)g(the)i(previous)e(32K)i(input)e(bytes\),)i(and)f
(pointers)g(to)0 1298 y(duplicated)d(strings,)g(where)i(a)f(pointer)g
(is)g(represented)g(as)g(a)h(pair)f Ff(<)p Fj(length,)g(backward)g
(distance)p Ff(>)p Fj(.)15 b(The)10 b(represen-)0 1354
y(tation)h(used)h(in)g(the)g(\252de\257ate\272)h(format)g(limits)e
(distances)h(to)g(32K)f(bytes)h(and)g(lengths)f(to)h(258)g(bytes,)g
(but)g(does)g(not)0 1410 y(limit)e(the)h(size)g(of)g(a)h(block,)f
(except)g(for)g(uncompressible)f(blocks,)g(which)h(are)g(limited)g(as)g
(noted)f(above.)0 1496 y(Each)e(type)f(of)g(value)h(\(literals,)f
(distances,)h(and)f(lengths\))g(in)g(the)g(compressed)g(data)h(is)f
(represented)g(using)g(a)h(Huf)o(fman)0 1553 y(code,)13
b(using)d(one)i(code)g(tree)g(for)g(literals)f(and)h(lengths)e(and)i(a)
h(separate)f(code)g(tree)g(for)g(distances.)k(The)c(code)g(trees)0
1609 y(for)f(each)h(block)e(appear)i(in)f(a)g(compact)g(form)h(just)e
(before)i(the)f(compressed)g(data)g(for)g(that)g(block.)0
1783 y Fh(3)60 b(Detailed)13 b(speci\256cation)0 1917
y Fd(3.1)50 b(Overall)12 b(conventions)0 2034 y Fj(In)f(the)g(diagrams)
g(below)m(,)g(a)h(box)e(like)h(this:)114 2119 y Fc(+---+)114
2176 y(|)82 b(|)27 b(<--)h(the)g(vertical)i(bars)e(might)h(be)f
(missing)114 2232 y(+---+)0 2318 y Fj(represents)11 b(one)g(byte;)f(a)h
(box)g(like)g(this:)114 2404 y Fc(+==============)q(+)114
2460 y(|)382 b(|)114 2517 y(+==============)q(+)0 2602
y Fj(represents)11 b(a)g(variable)g(number)g(of)g(bytes.)0
2688 y(Bytes)c(stored)g(within)f(a)i(computer)f(do)g(not)g(have)g(a)h
(\252bit)f(order)r(\272,)h(since)f(they)g(are)h(always)f(treated)h(as)f
(a)h(unit.)13 b(However)n(,)0 2744 y(a)e(byte)g(considered)f(as)h(an)g
(integer)f(between)h(0)f(and)h(255)f(does)h(have)g(a)g(most-)g(and)f
(least-signi\256cant)f(bit,)i(and)g(since)0 2869 y(Deutsch)661
b(Informational)f([Page)12 b(4])p eop
%%Page: 5 5
5 4 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)0 195 y(we)f(write)f(numbers)g(with)g(the)g(most-signi\256cant)f
(digit)g(on)i(the)f(left,)h(we)g(also)f(write)g(bytes)g(with)g(the)g
(most-signi\256cant)0 252 y(bit)k(on)g(the)g(left.)19
b(In)12 b(the)h(diagrams)f(below)m(,)g(we)h(number)f(the)h(bits)e(of)h
(a)h(byte)f(so)g(that)g(bit)g(0)g(is)g(the)g(least-signi\256cant)0
308 y(bit,)f(i.e.,)h(the)f(bits)f(are)i(numbered:)114
395 y Fc(+--------+)114 451 y(|76543210|)114 508 y(+--------+)0
595 y Fj(W)n(ithin)7 b(a)h(computer)n(,)h(a)g(number)f(may)h(occupy)e
(multiple)g(bytes.)14 b(All)7 b(multi-byte)g(numbers)h(in)f(the)h
(format)h(described)0 651 y(here)i(are)g(stored)e(with)h(the)g
(least-signi\256cant)e(byte)i(\256rst)g(\(at)h(the)f(lower)g(memory)h
(address\).)k(For)c(example,)g(the)f(dec-)0 708 y(imal)h(number)g(520)g
(is)g(stored)f(as:)223 795 y Fc(0)218 b(1)114 851 y(+--------+-----)q
(---)q(+)114 908 y(|00001000|00000)q(010)q(|)114 964
y(+--------+-----)q(---)q(+)141 1021 y(\303)g(\303)141
1077 y(|)g(|)141 1134 y(|)g(+)28 b(more)g(significant)j(byte)d(=)f(2)h
(x)g(256)141 1190 y(+)f(less)i(significant)h(byte)e(=)g(8)0
1343 y Fb(3.1.1)45 b(Packing)11 b(into)g(bytes)0 1461
y Fj(This)h(document)h(does)f(not)g(address)h(the)g(issue)f(of)h(the)g
(order)g(in)f(which)h(bits)e(of)i(a)h(byte)e(are)i(transmitted)e(on)g
(a)i(bit-)0 1517 y(sequential)8 b(medium,)j(since)e(the)h(\256nal)f
(data)h(format)g(described)f(here)h(is)f(byte-)h(rather)g(than)f
(bit-oriented.)k(However)n(,)0 1574 y(we)c(describe)g(the)g(compressed)
g(block)g(format)h(in)e(below)m(,)i(as)f(a)h(sequence)f(of)g(data)g
(elements)g(of)h(various)e(bit)g(lengths,)0 1630 y(not)j(a)h(sequence)g
(of)g(bytes.)k(W)l(e)d(must)e(therefore)h(specify)f(how)h(to)f(pack)h
(these)f(data)h(elements)g(into)e(bytes)h(to)h(form)0
1687 y(the)f(\256nal)g(compressed)g(byte)g(sequence:)68
1774 y Fg(\017)23 b Fj(Data)9 b(elements)g(are)i(packed)e(into)f(bytes)
h(in)g(order)h(of)f(increasing)g(bit)f(number)i(within)e(the)h(byte,)h
(i.e.,)h(starting)114 1830 y(with)f(the)h(least-signi\256cant)e(bit)h
(of)i(the)e(byte.)68 1917 y Fg(\017)23 b Fj(Data)13 b(elements)g(other)
g(than)g(Huf)o(fman)h(codes)f(are)h(packed)f(starting)f(with)g(the)h
(least-signi\256cant)f(bit)g(of)h(the)114 1973 y(data)e(element.)68
2060 y Fg(\017)23 b Fj(Huf)o(fman)11 b(codes)g(are)h(packed)f(starting)
f(with)g(the)h(most-signi\256cant)e(bit)i(of)g(the)g(code.)0
2147 y(In)f(other)f(words,)h(if)g(one)g(were)g(to)f(print)g(out)g(the)h
(compressed)f(data)h(as)g(a)g(sequence)g(of)g(bytes,)f(starting)g(with)
g(the)g(\256rst)0 2204 y(byte)h(at)h(the)f(*right*)f(mar)o(gin)i(and)g
(proceeding)e(to)i(the)f(*left*,)g(with)g(the)h(most-signi\256cant)d
(bit)i(of)h(each)g(byte)f(on)g(the)0 2260 y(left)j(as)h(usual,)f(one)g
(would)f(be)i(able)f(to)g(parse)h(the)f(result)f(from)i(right)f(to)g
(left,)h(with)e(\256xed-width)g(elements)i(in)e(the)0
2317 y(correct)e(MSB-to-LSB)i(order)e(and)g(Huf)o(fman)h(codes)e(in)h
(bit-reversed)f(order)i(\(i.e.,)g(with)e(the)h(\256rst)g(bit)f(of)i
(the)f(code)g(in)0 2373 y(the)h(relative)g(LSB)g(position\).)0
2869 y(Deutsch)661 b(Informational)f([Page)12 b(5])p
eop
%%Page: 6 6
6 5 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)0 195 y Fd(3.2)50 b(Compr)o(essed)13 b(block)f(format)0
313 y Fb(3.2.1)45 b(Synopsis)11 b(of)g(pr)o(e\256x)h(and)g(Huffman)g
(coding)0 430 y Fj(Pre\256x)d(coding)f(represents)g(symbols)f(from)j
(an)e Fe(a)h(priori)e Fj(known)g(alphabet)h(by)g(bit)g(sequences)g
(\(codes\),)i(one)e(code)h(for)0 487 y(each)j(symbol,)g(in)f(a)i
(manner)f(such)g(that)f(dif)o(ferent)h(symbols)e(may)j(be)f
(represented)f(by)h(bit)f(sequences)g(of)h(dif)o(ferent)0
543 y(lengths,)e(but)g(a)i(parser)f(can)h(always)e(parse)i(an)f
(encoded)g(string)f(unambiguously)e(symbol-by-symbol.)0
630 y(W)l(e)k(de\256ne)f(a)g(pre\256x)h(code)f(in)f(terms)h(of)g(a)h
(binary)e(tree)h(in)g(which)f(the)h(two)f(edges)h(descending)f(from)h
(each)h(non-leaf)0 687 y(node)e(are)i(labeled)e(0)h(and)f(1)h(and)g(in)
f(which)g(the)g(leaf)h(nodes)f(correspond)g(one-for)o(-one)h(with)f
(\(are)h(labeled)g(with\))e(the)0 743 y(symbols)h(of)i(the)f(alphabet;)
g(then)g(the)g(code)h(for)g(a)g(symbol)f(is)g(the)g(sequence)g(of)h(0')
n(s)f(and)g(1')n(s)g(on)h(the)f(edges)g(leading)0 799
y(from)h(the)f(root)f(to)h(the)g(leaf)g(labeled)g(with)f(that)h
(symbol.)j(For)e(example:)495 886 y Fc(/\\)383 b(Symbol)111
b(Code)468 943 y(0)55 b(1)355 b(------)111 b(----)441
999 y(/)e(\\)437 b(A)164 b(00)414 1056 y(/\\)137 b(B)409
b(B)191 b(1)386 1112 y(0)55 b(1)546 b(C)137 b(011)359
1169 y(/)109 b(\\)519 b(D)137 b(010)332 1225 y(A)f(/\\)468
1282 y(0)55 b(1)441 1338 y(/)109 b(\\)414 1395 y(D)164
b(C)0 1482 y Fj(A)12 b(parser)g(can)g(decode)f(the)h(next)f(symbol)f
(from)j(an)f(encoded)f(input)f(stream)i(by)g(walking)e(down)h(the)g
(tree)h(from)g(the)0 1538 y(root,)f(at)g(each)h(step)e(choosing)g(the)h
(edge)g(corresponding)e(to)i(the)g(next)g(input)e(bit.)0
1625 y(Given)g(an)g(alphabet)f(with)h(known)f(symbol)g(frequencies,)i
(the)f(Huf)o(fman)g(algorithm)g(allows)f(the)h(construction)e(of)i(an)0
1681 y(optimal)g(pre\256x)h(code)g(\(one)g(which)f(represents)g
(strings)f(with)h(those)g(symbol)g(frequencies)h(using)e(the)i(fewest)f
(bits)g(of)0 1738 y(any)h(possible)e(pre\256x)j(codes)e(for)i(that)e
(alphabet\).)15 b(Such)10 b(a)g(code)g(is)g(called)g(a)g(Huf)o(fman)h
(code.)k(\(See)c(reference)g([1])g(in)0 1794 y(Chapter)g(5,)h
(references)g(for)f(additional)e(information)h(on)h(Huf)o(fman)h
(codes.\))0 1881 y(Note)g(that)g(in)f(the)i(\252de\257ate\272)g
(format,)g(the)f(Huf)o(fman)h(codes)f(for)g(the)h(various)e(alphabets)g
(must)h(not)g(exceed)g(certain)0 1938 y(maximum)c(code)g(lengths.)13
b(This)6 b(constraint)h(complicates)g(the)g(algorithm)g(for)h
(computing)e(code)i(lengths)e(from)i(sym-)0 1994 y(bol)i(frequencies.)
15 b(Again,)c(see)h(Chapter)f(5,)g(references)h(for)g(details.)0
2147 y Fb(3.2.2)45 b(Use)11 b(of)h(Huffman)g(coding)f(in)g(the)h
(\252de\257ate\272)g(format)0 2265 y Fj(The)f(Huf)o(fman)h(codes)f
(used)f(for)i(each)f(alphabet)g(in)f(the)h(\252de\257ate\272)h(format)g
(have)f(two)f(additional)g(rules:)68 2352 y Fg(\017)23
b Fj(All)9 b(codes)g(of)h(a)h(given)e(bit)g(length)g(have)h
(lexicographically)d(consecutive)i(values,)h(in)f(the)h(same)g(order)g
(as)g(the)114 2408 y(symbols)g(they)g(represent;)68 2495
y Fg(\017)23 b Fj(Shorter)11 b(codes)g(lexicographically)e(precede)i
(longer)g(codes.)0 2582 y(W)l(e)e(could)f(recode)h(the)g(example)g
(above)f(to)g(follow)g(this)f(rule)i(as)g(follows,)f(assuming)f(that)i
(the)f(order)h(of)g(the)f(alphabet)0 2639 y(is)j(ABCD:)0
2869 y(Deutsch)661 b(Informational)f([Page)12 b(6])p
eop
%%Page: 7 7
7 6 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)114 195 y Fc(Symbol)56 b(Code)114 252 y(------)g(----)114
308 y(A)191 b(10)114 364 y(B)g(0)114 421 y(C)g(110)114
477 y(D)g(111)0 564 y Fj(I.e.,)13 b(0)e(precedes)g(10)g(which)f
(precedes)i(1)n(1x,)f(and)g(1)n(10)g(and)g(1)n(1)n(1)g(are)h
(lexicographically)d(consecutive.)0 651 y(Given)f(this)f(rule,)j(we)e
(can)h(de\256ne)g(the)f(Huf)o(fman)h(code)g(for)g(an)f(alphabet)g(just)
f(by)i(giving)e(the)h(bit)g(lengths)f(of)h(the)h(codes)0
708 y(for)h(each)h(symbol)e(of)h(the)g(alphabet)f(in)h(order;)g(this)f
(is)g(suf)o(\256cient)h(to)f(determine)h(the)g(actual)g(codes.)15
b(In)10 b(our)g(example,)0 764 y(the)h(code)g(is)g(completely)g
(de\256ned)g(by)g(the)g(sequence)g(of)g(bit)g(lengths)f(\(2,)h(1,)h(3,)
g(3\).)k(The)11 b(following)e(algorithm)h(gen-)0 821
y(erates)h(the)f(codes)g(as)h(integers,)f(intended)f(to)h(be)h(read)g
(from)g(most-)f(to)g(least-signi\256cant)e(bit.)15 b(The)10
b(code)h(lengths)e(are)0 877 y(initially)g(in)i(tree[I].Len;)g(the)g
(codes)g(are)h(produced)e(in)h(tree[I].Code.)0 964 y(1\))i(Count)f(the)
g(number)h(of)f(codes)g(for)h(each)g(code)g(length.)18
b(Let)13 b(bl)p 1079 964 14 2 v 15 w(count[N])f(be)h(the)f(number)h(of)
f(codes)h(of)f(length)0 1021 y(N,)g(N)f Ff(>)p Fj(=)g(1.)0
1108 y(2\))g(Find)g(the)g(numerical)g(value)g(of)g(the)g(smallest)f
(code)h(for)h(each)f(code)h(length:)223 1195 y Fc(code)28
b(=)g(0;)223 1251 y(bl)p 280 1251 V 17 w(count[0])h(=)f(0;)223
1308 y(for)g(\(bits)g(=)g(1;)g(bits)g(<=)g(MAX)p 934
1308 V 17 w(BITS;)h(bits++\))g Fg(f)332 1364 y Fc(code)f(=)g(\(code)g
(+)g(bl)p 798 1364 V 17 w(count[bits-1]\))j(<<)d(1;)332
1420 y(next)p 443 1420 V 17 w(code[bits])i(=)e(code;)223
1477 y Fg(g)0 1564 y Fj(3\))12 b(Assign)e(numerical)i(values)f(to)h
(all)f(codes,)h(using)f(consecutive)f(values)i(for)g(all)f(codes)h(of)f
(the)h(same)h(length)d(with)0 1620 y(the)i(base)g(values)g(determined)g
(at)g(step)g(2.)18 b(Codes)12 b(that)g(are)h(never)f(used)g(\(which)g
(have)g(a)h(bit)e(length)g(of)i(zero\))g(must)0 1677
y(not)d(be)i(assigned)e(a)h(value.)223 1764 y Fc(for)28
b(\(n)g(=)f(0;)55 b(n)28 b(<=)g(max)p 798 1764 V 17 w(code;)g(n++\))h
Fg(f)332 1820 y Fc(len)f(=)f(tree[n].Len;)332 1877 y(if)h(\(len)g(!=)g
(0\))g Fg(f)441 1933 y Fc(tree[n].Code)i(=)e(next)p 961
1933 V 17 w(code[len];)441 1990 y(next)p 552 1990 V 17
w(code[len]++;)332 2046 y Fg(g)223 2103 y(g)0 2190 y
Fj(Example:)0 2277 y(Consider)10 b(the)h(alphabet)g(ABCDEFGH,)g(with)g
(bit)f(lengths)g(\(3,)h(3,)h(3,)f(3,)h(3,)f(2,)h(4,)f(4\).)k(After)d
(step)e(1,)i(we)f(have:)114 2364 y Fc(N)164 b(bl)p 362
2364 V 16 w(count[N])114 2420 y(-)g(-----------)114 2476
y(2)g(1)114 2533 y(3)g(5)114 2589 y(4)g(2)0 2676 y Fj(Step)11
b(2)g(computes)g(the)g(following)e(next)p 649 2676 V
16 w(code)i(values:)0 2869 y(Deutsch)661 b(Informational)f([Page)12
b(7])p eop
%%Page: 8 8
8 7 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)114 195 y Fc(N)164 b(next)p 416 195 14 2 v 17
w(code[N])114 252 y(-)g(------------)114 308 y(1)g(0)114
364 y(2)g(0)114 421 y(3)g(2)114 477 y(4)g(14)0 564 y
Fj(Step)11 b(3)g(produces)g(the)g(following)e(code)i(values:)114
651 y Fc(Symbol)29 b(Length)83 b(Code)114 708 y(------)29
b(------)83 b(----)114 764 y(A)191 b(3)218 b(010)114
821 y(B)191 b(3)218 b(011)114 877 y(C)191 b(3)218 b(100)114
934 y(D)191 b(3)218 b(101)114 990 y(E)191 b(3)218 b(110)114
1047 y(F)191 b(2)246 b(00)114 1103 y(G)191 b(4)g(1110)114
1159 y(H)g(4)g(1111)0 1313 y Fb(3.2.3)45 b(Details)11
b(of)g(block)g(format)0 1430 y Fj(Each)g(block)g(of)g(compressed)g
(data)g(begins)f(with)g(3)h(header)h(bits)e(containing)f(the)i
(following)e(data:)114 1517 y Fc(first)28 b(bit)192 b(BFINAL)114
1574 y(next)28 b(2)g(bits)137 b(BTYPE)0 1661 y Fj(Note)10
b(that)f(the)h(header)h(bits)e(do)h(not)f(necessarily)h(begin)f(on)h(a)
h(byte)e(boundary)m(,)h(since)g(a)g(block)g(does)g(not)f(necessarily)0
1717 y(occupy)i(an)g(integral)f(number)h(of)h(bytes.)0
1804 y(BFINAL)f(is)g(set)g(if)g(and)g(only)f(if)h(this)g(is)f(the)h
(last)g(block)f(of)h(the)g(data)g(set.)0 1891 y(BTYPE)g(speci\256es)g
(how)g(the)g(data)g(are)h(compressed,)f(as)g(follows:)114
1978 y Fc(00)27 b(-)h(no)g(compression)114 2035 y(01)f(-)h(compressed)i
(with)e(fixed)h(Huffman)g(codes)114 2091 y(10)e(-)h(compressed)i(with)e
(dynamic)i(Huffman)f(codes)114 2147 y(11)e(-)h(reserved)h(\(error\))0
2234 y Fj(The)12 b(only)f(dif)o(ference)h(between)g(the)g(two)f
(compressed)h(cases)g(is)f(how)h(the)g(Huf)o(fman)g(codes)g(for)g(the)g
(literal/length)0 2291 y(and)f(distance)f(alphabets)g(are)i(de\256ned.)
0 2378 y(In)f(all)g(cases,)h(the)f(decoding)f(algorithm)g(for)h(the)g
(actual)g(data)g(is)g(as)g(follows:)0 2869 y(Deutsch)661
b(Informational)f([Page)12 b(8])p eop
%%Page: 9 9
9 8 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)114 195 y Fa(do)188 245 y(read)25 b(block)f(header)h(from)f
(input)h(stream.)188 295 y(if)g(stored)f(with)h(no)g(compression)263
345 y(skip)g(any)f(remaining)g(bits)h(in)g(current)f(partially)338
394 y(processed)g(byte)263 444 y(read)h(LEN)f(and)h(NLEN)f(\(see)h
(next)f(section\))263 494 y(copy)h(LEN)f(bytes)h(of)f(data)h(to)g
(output)188 544 y(otherwise)263 594 y(if)g(compressed)f(with)g(dynamic)
h(Huffman)f(codes)338 643 y(read)g(representation)g(of)h(code)f(trees)h
(\(see)413 693 y(subsection)e(below\))263 743 y(loop)i(\(until)f(end)h
(of)f(block)h(code)f(recognized\))338 793 y(decode)g(literal/length)g
(value)g(from)h(input)f(stream)338 843 y(if)h(value)f(<)h(256)413
892 y(copy)f(value)g(\(literal)h(byte\))f(to)h(output)f(stream)338
942 y(otherwise)413 992 y(if)g(value)h(=)f(end)h(of)g(block)f(\(256\))
487 1042 y(break)h(from)f(loop)413 1092 y(otherwise)g(\(value)g(=)h
(257..285\))487 1142 y(decode)g(distance)f(from)g(input)h(stream)487
1241 y(move)g(backwards)f(distance)g(bytes)g(in)h(the)g(output)487
1291 y(stream,)f(and)h(copy)g(length)f(bytes)g(from)h(this)487
1341 y(position)f(to)h(the)g(output)f(stream.)263 1391
y(end)h(loop)114 1440 y(while)f(not)h(last)f(block)0
1527 y Fj(Note)12 b(that)f(a)h(duplicated)f(string)g(reference)i(may)f
(refer)h(to)f(a)g(string)f(in)h(a)g(previous)f(block;)g(i.e.,)i(the)f
(backward)g(dis-)0 1584 y(tance)g(may)h(cross)f(one)h(or)f(more)h
(block)f(boundaries.)17 b(However)12 b(a)h(distance)f(cannot)f(refer)j
(past)e(the)g(beginning)e(of)0 1640 y(the)i(output)g(stream.)20
b(\(An)13 b(application)e(using)g(a)i(preset)g(dictionary)e(might)h
(discard)g(part)h(of)g(the)f(output)f(stream;)j(a)0 1697
y(distance)8 b(can)h(refer)h(to)e(that)g(part)h(of)g(the)f(output)g
(stream)h(anyway\))f(Note)h(also)f(that)g(the)g(referenced)i(string)e
(may)h(over)o(-)0 1753 y(lap)i(the)f(current)h(position;)d(for)j
(example,)h(if)e(the)h(last)f(2)h(bytes)f(decoded)g(have)h(values)f(X)h
(and)g(Y)-6 b(,)11 b(a)g(string)f(reference)0 1810 y(with)g
Ff(<)p Fj(length)h(=)g(5,)g(distance)f(=)h(2)p Ff(>)h
Fj(adds)e(X,Y)-6 b(,X,Y)g(,X)13 b(to)d(the)h(output)f(stream.)0
1897 y(W)l(e)i(now)e(specify)h(each)h(compression)e(method)h(in)f
(turn.)0 2050 y Fb(3.2.4)45 b(Non-compr)o(essed)12 b(blocks)f
(\(BTYPE=00\))0 2167 y Fj(Any)d(bits)g(of)h(input)e(up)i(to)f(the)g
(next)h(byte)f(boundary)f(are)j(ignored.)j(The)c(rest)g(of)g(the)f
(block)g(consists)f(of)i(the)f(following)0 2224 y(information:)168
2311 y Fc(0)82 b(1)g(2)g(3)h(4...)114 2367 y(+---+---+---+--)q(-+=)q
(====)q(====)q(===)q(====)q(====)q(===)q(====)q(====)q(=+)114
2424 y(|)54 b(LEN)i(|)27 b(NLEN)56 b(|...)28 b(LEN)g(bytes)h(of)f
(literal)h(data...|)114 2480 y(+---+---+---+--)q(-+=)q(====)q(====)q
(===)q(====)q(====)q(===)q(====)q(====)q(=+)0 2567 y
Fj(LEN)11 b(is)f(the)h(number)h(of)f(data)g(bytes)f(in)h(the)g(block.)j
(NLEN)d(is)g(the)f(one')n(s)h(complement)g(of)g(LEN.)0
2869 y(Deutsch)661 b(Informational)f([Page)12 b(9])p
eop
%%Page: 10 10
10 9 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)0 195 y Fb(3.2.5)45 b(Compr)o(essed)12 b(blocks)f(\(length)h
(and)f(distance)h(codes\))0 313 y Fj(As)c(noted)g(above,)i(encoded)e
(data)h(blocks)f(in)g(the)h(\252de\257ate\272)g(format)g(consist)f(of)g
(sequences)h(of)g(symbols)e(drawn)i(from)0 369 y(three)k(conceptually)f
(distinct)f(alphabets:)17 b(either)c(literal)g(bytes,)g(from)h(the)e
(alphabet)h(of)g(byte)g(values)f(\(0..255\),)i(or)0 426
y Ff(<)p Fj(length,)e(backward)g(distance)p Ff(>)f Fj(pairs,)h(where)h
(the)e(length)g(is)h(drawn)f(from)i(\(3..258\))f(and)g(the)g(distance)f
(is)g(drawn)0 482 y(from)d(\(1..32,768\).)14 b(In)8 b(fact,)h(the)f
(literal)f(and)g(length)g(alphabets)f(are)j(mer)o(ged)f(into)f(a)h
(single)e(alphabet)h(\(0..285\),)i(where)0 538 y(values)g(0..255)g
(represent)h(literal)f(bytes,)g(the)g(value)h(256)f(indicates)f
(end-of-block,)h(and)h(values)f(257..285)f(represent)0
595 y(length)i(codes)h(\(possibly)e(in)i(conjunction)e(with)h(extra)h
(bits)f(following)f(the)i(symbol)f(code\))i(as)f(follows:)250
682 y Fc(Extra)410 b(Extra)h(Extra)114 738 y(Code)28
b(Bits)g(Length\(s\))i(Code)e(Bits)h(Lengths)84 b(Code)28
b(Bits)g(Length\(s\))114 795 y(----)g(----)g(------)138
b(----)29 b(----)f(-------)84 b(----)28 b(----)h(-------)141
851 y(257)83 b(0)136 b(3)191 b(267)83 b(1)f(15,16)138
b(277)82 b(4)h(67-82)141 908 y(258)g(0)136 b(4)191 b(268)83
b(1)f(17,18)138 b(278)82 b(4)h(83-98)141 964 y(259)g(0)136
b(5)191 b(269)83 b(2)f(19-22)138 b(279)82 b(4)h(99-114)141
1021 y(260)g(0)136 b(6)191 b(270)83 b(2)f(23-26)138 b(280)82
b(4)55 b(115-130)141 1077 y(261)83 b(0)136 b(7)191 b(271)83
b(2)f(27-30)138 b(281)82 b(5)55 b(131-162)141 1134 y(262)83
b(0)136 b(8)191 b(272)83 b(2)f(31-34)138 b(282)82 b(5)55
b(163-194)141 1190 y(263)83 b(0)136 b(9)191 b(273)83
b(3)f(35-42)138 b(283)82 b(5)55 b(195-226)141 1246 y(264)83
b(0)109 b(10)191 b(274)83 b(3)f(43-50)138 b(284)82 b(5)55
b(227-257)141 1303 y(265)83 b(1)54 b(11,12)165 b(275)83
b(3)f(51-58)138 b(285)82 b(0)110 b(258)141 1359 y(266)83
b(1)54 b(13,14)165 b(276)83 b(3)f(59-66)0 1446 y Fj(The)12
b(extra)h(bits)e(should)g(be)h(interpreted)g(as)g(a)h(machine)f
(integer)g(stored)g(with)f(the)h(most-signi\256cant)f(bit)g(\256rst,)i
(e.g.,)0 1503 y(bits)d(1)n(1)n(10)h(represent)g(the)g(value)g(14.)277
1590 y Fc(Extra)302 b(Extra)410 b(Extra)141 1646 y(Code)28
b(Bits)h(Dist)55 b(Code)29 b(Bits)83 b(Dist)137 b(Code)28
b(Bits)h(Distance)141 1703 y(----)f(----)h(----)55 b(----)29
b(----)55 b(------)111 b(----)28 b(----)h(--------)195
1759 y(0)83 b(0)109 b(1)137 b(10)82 b(4)137 b(33-48)110
b(20)g(9)82 b(1025-1536)195 1816 y(1)h(0)109 b(2)137
b(11)82 b(4)137 b(49-64)110 b(21)g(9)82 b(1537-2048)195
1872 y(2)h(0)109 b(3)137 b(12)82 b(5)137 b(65-96)110
b(22)82 b(10)h(2049-3072)195 1929 y(3)g(0)109 b(4)137
b(13)82 b(5)137 b(97-128)83 b(23)f(10)h(3073-4096)195
1985 y(4)g(1)f(5,6)110 b(14)82 b(6)109 b(129-192)84 b(24)e(11)h
(4097-6144)195 2041 y(5)g(1)f(7,8)110 b(15)82 b(6)109
b(193-256)84 b(25)e(11)h(6145-8192)195 2098 y(6)g(2)f(9-12)h(16)f(7)109
b(257-384)84 b(26)e(12)55 b(8193-12288)195 2154 y(7)83
b(2)54 b(13-16)84 b(17)e(7)109 b(385-512)84 b(27)e(12)28
b(12289-16384)195 2211 y(8)83 b(3)54 b(17-24)84 b(18)e(8)109
b(513-768)84 b(28)e(13)28 b(16385-24576)195 2267 y(9)83
b(3)54 b(25-32)84 b(19)e(8)g(769-1024)i(29)e(13)28 b(24577-32768)0
2420 y Fb(3.2.6)45 b(Compr)o(ession)11 b(with)g(\256xed)h(Huffman)g
(codes)g(\(BTYPE=01\))0 2538 y Fj(The)g(Huf)o(fman)h(codes)f(for)h(the)
f(two)g(alphabets)g(are)h(\256xed,)g(and)f(are)i(not)d(represented)h
(explicitly)f(in)h(the)g(data.)19 b(The)0 2594 y(Huf)o(fman)12
b(code)f(lengths)e(for)j(the)f(literal/length)d(alphabet)j(are:)0
2869 y(Deutsch)649 b(Informational)h([Page)11 b(10])p
eop
%%Page: 11 11
11 10 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)305 195 y Fc(Lit)28 b(Value)110 b(Bits)219 b(Codes)305
252 y(---------)111 b(----)219 b(-----)359 308 y(0)28
b(-)f(143)137 b(8)273 b(00110000)30 b(through)986 364
y(10111111)305 421 y(144)e(-)f(255)137 b(9)273 b(110010000)30
b(through)986 477 y(111111111)305 534 y(256)e(-)f(279)137
b(7)273 b(0000000)30 b(through)986 590 y(0010111)305
647 y(280)e(-)f(287)137 b(8)273 b(11000000)30 b(through)986
703 y(11000111)0 790 y Fj(The)9 b(code)f(lengths)g(are)h(suf)o
(\256cient)g(to)f(generate)h(the)f(actual)h(codes,)g(as)g(described)f
(above;)h(we)g(show)f(the)h(codes)f(in)g(the)0 847 y(table)k(for)g
(added)g(clarity)m(.)17 b(Literal/length)9 b(values)j(286-287)e(will)h
(never)i(actually)e(occur)h(in)f(the)h(compressed)g(data,)0
903 y(but)e(participate)h(in)f(the)h(code)g(construction.)0
990 y(Distance)e(codes)g(0-31)g(are)h(represented)f(by)g
(\(\256xed-length\))f(5-bit)h(codes,)g(with)g(possible)e(additional)h
(bits)g(as)h(shown)0 1047 y(in)j(the)g(table)f(shown)g(in)h(Paragraph)h
(3.2.5,)g(above.)18 b(Note)11 b(that)h(distance)f(codes)h(30-31)f(will)
g(never)i(actually)e(occur)0 1103 y(in)g(the)g(compressed)g(data.)0
1256 y Fb(3.2.7)45 b(Compr)o(ession)11 b(with)g(dynamic)g(Huffman)h
(codes)g(\(BTYPE=10\))0 1374 y Fj(The)c(Huf)o(fman)h(codes)e(for)i(the)
f(two)f(alphabets)g(appear)i(in)e(the)h(block)f(immediately)h(after)h
(the)e(header)i(bits)e(and)h(before)0 1430 y(the)i(actual)h(compressed)
f(data,)h(\256rst)g(the)f(literal/length)f(code)h(and)h(then)f(the)h
(distance)e(code.)16 b(Each)10 b(code)h(is)f(de\256ned)0
1487 y(by)e(a)h(sequence)g(of)f(code)h(lengths,)f(as)h(discussed)e(in)h
(Paragraph)h(3.2.2,)h(above.)k(For)9 b(even)f(greater)h(compactness,)g
(the)0 1543 y(code)h(length)f(sequences)g(themselves)g(are)h
(compressed)g(using)f(a)h(Huf)o(fman)g(code.)15 b(The)10
b(alphabet)f(for)h(code)g(lengths)0 1600 y(is)h(as)g(follows:)195
1687 y Fc(0)28 b(-)g(15:)g(Represent)h(code)g(lengths)g(of)f(0)f(-)h
(15)305 1743 y(16:)g(Copy)g(the)g(previous)i(code)e(length)h(3)e(-)h(6)
f(times.)414 1799 y(The)h(next)g(2)g(bits)g(indicate)h(repeat)g(length)
577 1856 y(\(0)f(=)g(3,)f(...)i(,)e(3)h(=)f(6\))495 1912
y(Example:)57 b(Codes)29 b(8,)f(16)f(\(+2)i(bits)f(11\),)768
1969 y(16)g(\(+2)g(bits)g(10\))h(will)f(expand)h(to)768
2025 y(12)f(code)g(lengths)i(of)d(8)h(\(1)g(+)f(6)h(+)f(5\))305
2082 y(17:)h(Repeat)h(a)e(code)h(length)h(of)f(0)g(for)g(3)f(-)h(10)g
(times.)414 2138 y(\(3)f(bits)i(of)f(length\))305 2195
y(18:)g(Repeat)h(a)e(code)h(length)h(of)f(0)g(for)g(11)g(-)f(138)h
(times)414 2251 y(\(7)f(bits)i(of)f(length\))0 2338 y
Fj(A)10 b(code)h(length)e(of)h(0)g(indicates)g(that)f(the)h
(corresponding)f(symbol)g(in)h(the)g(literal/length)e(or)i(distance)g
(alphabet)f(will)0 2395 y(not)g(occur)h(in)g(the)g(block,)g(and)f
(should)g(not)g(participate)g(in)h(the)g(Huf)o(fman)g(code)g
(construction)e(algorithm)h(given)g(ear)o(-)0 2451 y(lier)n(.)21
b(If)13 b(only)f(one)h(distance)g(code)g(is)f(used,)i(it)f(is)f
(encoded)h(using)f(one)h(bit,)g(not)f(zero)i(bits;)f(in)f(this)g(case)i
(there)f(is)g(a)0 2507 y(single)c(code)i(length)f(of)h(one,)g(with)e
(one)i(unused)e(code.)16 b(One)10 b(distance)g(code)h(of)g(zero)g(bits)
e(means)i(that)f(there)h(are)h(no)0 2564 y(distance)e(codes)h(used)g
(at)g(all)g(\(the)g(data)g(is)g(all)f(literals\).)0 2651
y(W)l(e)i(can)f(now)g(de\256ne)g(the)g(format)h(of)f(the)g(block:)0
2869 y(Deutsch)650 b(Informational)g([Page)12 b(1)n(1])p
eop
%%Page: 12 12
12 11 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)188 195 y Fa(5)25 b(Bits:)g(HLIT,)f(#)h(of)g(Literal/Length)e
(codes)i(-)f(257)h(\(257)g(-)f(286\))188 245 y(5)h(Bits:)g(HDIST,)f(#)h
(of)f(Distance)h(codes)f(-)h(1)199 b(\(1)25 b(-)g(32\))188
295 y(4)g(Bits:)g(HCLEN,)f(#)h(of)f(Code)h(Length)f(codes)h(-)g(4)124
b(\(4)25 b(-)g(19\))188 394 y(\(HCLEN)g(+)g(4\))f(x)h(3)g(bits:)f(code)
h(lengths)f(for)h(the)f(code)h(length)263 444 y(alphabet)f(given)h
(just)f(above,)h(in)f(the)h(order:)f(16,)h(17,)f(18,)263
494 y(0,)h(8,)g(7,)f(9,)h(6,)g(10,)f(5,)h(11,)g(4,)f(12,)h(3,)g(13,)f
(2,)h(14,)g(1,)f(15)263 594 y(These)h(code)f(lengths)g(are)h
(interpreted)f(as)h(3-bit)f(integers)263 643 y(\(0-7\);)g(as)h(above,)f
(a)h(code)g(length)f(of)h(0)g(means)f(the)263 693 y(corresponding)g
(symbol)g(\(literal/length)g(or)g(distance)g(code)263
743 y(length\))g(is)h(not)g(used.)188 843 y(HLIT)g(+)g(257)f(code)h
(lengths)f(for)h(the)f(literal/length)g(alphabet,)263
892 y(encoded)g(using)h(the)f(code)h(length)f(Huffman)h(code)188
992 y(HDIST)g(+)g(1)f(code)h(lengths)f(for)h(the)f(distance)h
(alphabet,)263 1042 y(encoded)f(using)h(the)f(code)h(length)f(Huffman)h
(code)188 1142 y(The)g(actual)f(compressed)g(data)h(of)g(the)f(block,)
263 1191 y(encoded)g(using)h(the)f(literal/length)g(and)h(distance)f
(Huffman)263 1241 y(codes)188 1341 y(The)h(literal/length)f(symbol)g
(256)h(\(end)f(of)h(data\),)263 1391 y(encoded)f(using)h(the)f
(literal/length)g(Huffman)g(code)0 1478 y Fj(The)9 b(code)g(length)f
(repeat)i(codes)f(can)g(cross)g(from)h(HLIT)f(+)g(257)f(to)h(the)g
(HDIST)g(+)g(1)g(code)g(lengths.)14 b(In)9 b(other)g(words,)0
1534 y(all)i(code)g(lengths)f(form)h(a)h(single)e(sequence)h(of)g(HLIT)
g(+)g(HDIST)g(+)g(258)g(values.)0 1689 y Fd(3.3)50 b(Compliance)0
1806 y Fj(A)9 b(compressor)g(may)h(limit)e(further)h(the)g(ranges)h(of)
f(values)f(speci\256ed)h(in)g(the)g(previous)f(section)g(and)i(still)d
(be)j(compli-)0 1863 y(ant;)g(for)g(example,)h(it)e(may)h(limit)f(the)h
(range)g(of)g(backward)g(pointers)e(to)i(some)g(value)f(smaller)h(than)
g(32K.)f(Similarly)m(,)0 1919 y(a)j(compressor)e(may)i(limit)e(the)h
(size)g(of)h(blocks)e(so)g(that)h(a)g(compressible)g(block)f(\256ts)h
(in)g(memory)m(.)0 2006 y(A)f(compliant)g(decompressor)g(must)g(accept)
h(the)f(full)g(range)g(of)h(possible)d(values)i(de\256ned)h(in)f(the)g
(previous)f(section,)0 2063 y(and)i(must)g(accept)g(blocks)f(of)h
(arbitrary)g(size.)0 2239 y Fh(4)60 b(Compr)o(ession)14
b(algorithm)f(details)0 2373 y Fj(While)8 b(it)g(is)g(the)g(intent)f
(of)i(this)e(document)h(to)g(de\256ne)h(the)f(\252de\257ate\272)i
(compressed)e(data)g(format)h(without)e(reference)j(to)0
2430 y(any)f(particular)f(compression)g(algorithm,)g(the)h(format)g(is)
f(related)h(to)f(the)h(compressed)g(formats)f(produced)h(by)f(LZ77)0
2486 y(\(Lempel-Ziv)j(1977,)h(see)g(reference)i([2])e(below\);)f(since)
h(many)g(variations)e(of)i(LZ77)g(are)g(patented,)g(it)g(is)f(strongly)
0 2543 y(recommended)g(that)e(the)h(implementor)g(of)g(a)g(compressor)g
(follow)f(the)h(general)g(algorithm)f(presented)h(here,)h(which)0
2599 y(is)g(known)f(not)h(to)f(be)i(patented)e(per)i(se.)k(The)11
b(material)g(in)g(this)f(section)g(is)h(not)g(part)g(of)g(the)g
(de\256nition)f(of)h(the)g(speci-)0 2655 y(\256cation)g(per)g(se,)h
(and)f(a)g(compressor)g(need)g(not)g(follow)f(it)g(in)h(order)g(to)g
(be)g(compliant.)0 2869 y(Deutsch)649 b(Informational)h([Page)11
b(12])p eop
%%Page: 13 13
13 12 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)0 195 y(The)h(compressor)h(terminates)f(a)h(block)f(when)g(it)g
(determines)g(that)g(starting)f(a)i(new)g(block)f(with)f(fresh)i(trees)
f(would)0 252 y(be)g(useful,)g(or)g(when)g(the)g(block)f(size)h
(\256lls)g(up)g(the)g(compressor)r(')n(s)f(block)g(buf)o(fer)n(.)0
339 y(The)h(compressor)g(uses)g(a)g(chained)g(hash)g(table)f(to)h
(\256nd)g(duplicated)f(strings,)g(using)g(a)h(hash)g(function)f(that)h
(operates)0 395 y(on)i(3-byte)f(sequences.)20 b(At)13
b(any)g(given)f(point)g(during)g(compression,)h(let)f(XYZ)h(be)g(the)g
(next)g(3)g(input)e(bytes)h(to)h(be)0 451 y(examined)h(\(not)f
(necessarily)g(all)g(dif)o(ferent,)i(of)f(course\).)23
b(First,)14 b(the)g(compressor)f(examines)h(the)f(hash)h(chain)f(for)0
508 y(XYZ.)j(If)11 b(the)h(chain)f(is)f(empty)m(,)i(the)f(compressor)g
(simply)g(writes)f(out)h(X)g(as)h(a)g(literal)e(byte)h(and)g(advances)h
(one)f(byte)0 564 y(in)j(the)f(input.)23 b(If)15 b(the)e(hash)h(chain)g
(is)f(not)h(empty)m(,)h(indicating)d(that)h(the)h(sequence)g(XYZ)g
(\(or)n(,)h(if)f(we)g(are)h(unlucky)m(,)0 621 y(some)d(other)f(3)g
(bytes)g(with)f(the)h(same)h(hash)f(function)g(value\))g(has)g
(occurred)h(recently)m(,)f(the)h(compressor)f(compares)0
677 y(all)h(strings)f(on)h(the)g(XYZ)g(hash)g(chain)g(with)g(the)g
(actual)g(input)f(data)h(sequence)h(starting)e(at)h(the)g(current)h
(point,)e(and)0 734 y(selects)g(the)f(longest)g(match.)0
821 y(The)i(compressor)g(searches)g(the)g(hash)g(chains)f(starting)g
(with)g(the)h(most)f(recent)i(strings,)e(to)g(favor)i(small)e
(distances)0 877 y(and)f(thus)e(take)i(advantage)f(of)h(the)g(Huf)o
(fman)g(encoding.)k(The)9 b(hash)h(chains)f(are)h(singly)f(linked.)k
(There)d(are)h(no)e(dele-)0 934 y(tions)f(from)h(the)g(hash)f(chains;)h
(the)g(algorithm)f(simply)g(discards)g(matches)h(that)g(are)g(too)g
(old.)14 b(T)m(o)8 b(avoid)g(a)i(worst-case)0 990 y(situation,)e(very)h
(long)f(hash)h(chains)g(are)h(arbitrarily)e(truncated)h(at)g(a)h
(certain)f(length,)g(determined)g(by)g(a)h(run-time)f(pa-)0
1047 y(rameter)n(.)0 1134 y(T)m(o)f(improve)f(overall)h(compression,)g
(the)f(compressor)h(optionally)e(defers)i(the)g(selection)e(of)i
(matches)h(\(\252lazy)f(match-)0 1190 y(ing\272\):)15
b(after)d(a)g(match)g(of)g(length)e(N)i(has)g(been)f(found,)h(the)f
(compressor)g(searches)h(for)g(a)g(longer)f(match)h(starting)e(at)0
1246 y(the)j(next)g(input)f(byte.)21 b(If)14 b(it)f(\256nds)g(a)g
(longer)g(match,)i(it)d(truncates)h(the)g(previous)f(match)i(to)f(a)g
(length)g(of)g(one)g(\(thus)0 1303 y(producing)d(a)h(single)f(literal)g
(byte\))h(and)g(then)g(emits)f(the)h(longer)g(match.)k(Otherwise,)c(it)
f(emits)h(the)g(original)f(match,)0 1359 y(and,)h(as)h(described)e
(above,)h(advances)g(N)h(bytes)e(before)h(continuing.)0
1446 y(Run-time)h(parameters)h(also)e(control)g(this)g(\252lazy)i
(match\272)f(procedure.)18 b(If)13 b(compression)e(ratio)h(is)f(most)h
(important,)0 1503 y(the)e(compressor)g(attempts)f(a)i(complete)f
(second)f(search)i(regardless)e(of)i(the)f(length)f(of)h(the)g(\256rst)
g(match.)15 b(In)10 b(the)g(nor)o(-)0 1559 y(mal)j(case,)g(if)f(the)g
(current)g(match)g(is)g(\252long)f(enough\272,)h(the)g(compressor)g
(reduces)g(the)g(search)g(for)h(a)f(longer)g(match,)0
1616 y(thus)e(speeding)g(up)g(the)h(process.)k(If)c(speed)g(is)f(most)h
(important,)f(the)h(compressor)f(inserts)g(new)h(strings)e(in)i(the)g
(hash)0 1672 y(table)d(only)e(when)i(no)g(match)g(was)g(found,)g(or)g
(when)f(the)h(match)g(is)g(not)f(\252too)g(long\272.)14
b(This)7 b(degrades)h(the)f(compression)0 1729 y(ratio)k(but)f(saves)h
(time)g(since)g(there)g(are)h(both)e(fewer)i(insertions)d(and)i(fewer)h
(searches.)0 1905 y Fh(5)60 b(Refer)o(ences)0 2039 y
Fj([1])11 b(Huf)o(fman,)h(D.)g(A.,)f(\252A)h(Method)e(for)i(the)e
(Construction)g(of)h(Minimum)g(Redundancy)f(Codes\272,)i(Proceedings)e
(of)0 2095 y(the)h(Institute)e(of)i(Radio)g(Engineers,)g(September)h
(1952,)e(V)-6 b(olume)11 b(40,)g(Number)h(9,)f(pp.)k(1098-1)n(101.)0
2182 y([2])e(Ziv)g(J.,)h(Lempel)f(A.,)h(\252A)f(Universal)f(Algorithm)g
(for)h(Sequential)f(Data)h(Compression\272,)h(IEEE)e(T)n(ransactions)0
2239 y(on)f(Information)f(Theory)m(,)h(V)-6 b(ol.)15
b(23,)c(No.)k(3,)d(pp.)j(337-343.)0 2326 y([3])j(Gailly)m(,)h(J.-L.,)h
(and)d(Adler)n(,)j(M.,)h(ZLIB)d(documentation)e(and)h(sources,)j
(available)d(in)g(ftp://ftp.uu.net/pub)o(/)0 2382 y(archiving/zip/doc/)
0 2469 y([4])i(Gailly)m(,)h(J.-L.,)i(and)d(Adler)n(,)i(M.,)h(GZIP)d
(documentation)f(and)g(sources,)j(available)d(as)h(gzip-*.tar)g(in)g
(ftp://)0 2526 y(prep.ai.mit.edu/pub/gnu/)0 2613 y([5])11
b(Schwartz,)h(E.)f(S.,)h(and)f(Kallick,)f(B.)i(\252Generating)e(a)i
(canonical)e(pre\256x)h(encoding.\272)j(Comm.)i(ACM,)c(7,3)f(\(Mar)n(.)
0 2669 y(1964\),)g(pp.)k(166-169.)0 2869 y(Deutsch)649
b(Informational)h([Page)11 b(13])p eop
%%Page: 14 14
14 13 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)0 195 y([6])i(Hirschber)o(g)g(and)g(Lelewer)n(,)h(\252Ef)o
(\256cient)f(decoding)f(of)h(pre\256x)h(codes,\272)f(Comm.)19
b(ACM,)14 b(33,4,)e(April)f(1990,)h(pp.)0 252 y(449-459.)0
428 y Fh(6)60 b(Security)13 b(Considerations)0 562 y
Fj(Any)d(data)g(compression)f(method)g(involves)g(the)h(reduction)f(of)
h(redundancy)f(in)h(the)g(data.)15 b(Consequently)m(,)9
b(any)h(cor)o(-)0 618 y(ruption)g(of)h(the)g(data)g(is)f(likely)g(to)h
(have)g(severe)h(ef)o(fects)f(and)g(be)g(dif)o(\256cult)g(to)g
(correct.)k(Uncompressed)c(text,)g(on)f(the)0 675 y(other)h(hand,)g
(will)f(probably)g(still)f(be)j(readable)f(despite)f(the)h(presence)g
(of)h(some)f(corrupted)g(bytes.)0 762 y(It)f(is)g(recommended)h(that)f
(systems)f(using)g(this)g(data)i(format)f(provide)g(some)g(means)h(of)f
(validating)f(the)h(integrity)e(of)0 818 y(the)j(compressed)g(data.)k
(See)d(reference)g([3],)g(for)g(example.)0 995 y Fh(7)60
b(Sour)o(ce)14 b(code)0 1129 y Fj(Source)d(code)g(for)f(a)h(C)g
(language)f(implementation)f(of)i(a)g(\252de\257ate\272)g(compliant)f
(compressor)g(and)g(decompressor)h(is)0 1185 y(available)f(within)g
(the)h(zlib)f(package)i(at)f(ftp://ftp.uu.net/pub)o(/archivi)o(ng/)o
(zip/)o(zlib/)o(.)0 1362 y Fh(8)60 b(Acknowledgements)0
1495 y Fj(T)n(rademarks)12 b(cited)f(in)f(this)g(document)h(are)h(the)f
(property)f(of)h(their)g(respective)g(owners.)0 1582
y(Phil)g(Katz)g(designed)f(the)h(de\257ate)g(format.)16
b(Jean-Loup)10 b(Gailly)g(and)h(Mark)h(Adler)f(wrote)g(the)g(related)g
(software)g(de-)0 1639 y(scribed)c(in)g(this)g(speci\256cation.)13
b(Glenn)7 b(Randers-Pehrson)g(converted)g(this)g(document)g(to)g(RFC)h
(and)g(HTML)f(format.)0 1815 y Fh(9)60 b(Author)q(')n(s)15
b(Addr)o(ess)0 1949 y Fj(L.)c(Peter)h(Deutsch)114 2036
y Fc(Aladdin)29 b(Enterprises)114 2093 y(203)f(Santa)g(Margarita)i
(Ave.)114 2149 y(Menlo)e(Park,)h(CA)f(94025)114 2262
y(Phone:)h(\(415\))f(322-0103)i(\(AM)e(only\))114 2319
y(FAX:)83 b(\(415\))28 b(322-1734)114 2375 y(EMail:)h(<ghost@aladdin.)q
(com>)0 2462 y Fj(Questions)9 b(about)i(the)f(technical)h(content)f(of)
h(this)f(speci\256cation)g(can)i(be)f(sent)g(by)g(email)g(to:)114
2549 y Fc(Jean-Loup)29 b(Gailly)g(<[email protected])q(i.mi)q(t.ed)q(u>)i
(and)114 2606 y(Mark)d(Adler)h(<madler@alumni.)q(cal)q(tech)q(.edu)q(>)
0 2693 y Fj(Editorial)9 b(comments)j(on)e(this)h(speci\256cation)f(can)
h(be)g(sent)g(by)g(email)g(to:)0 2869 y(Deutsch)649 b(Informational)h
([Page)11 b(14])p eop
%%Page: 15 15
15 14 bop 0 46 a Fj(RFC)12 b(1951)283 b(DEFLA)-5 b(TE)10
b(Compressed)h(Data)g(Format)h(Speci\256cation)283 b(April)10
b(1996)114 195 y Fc(L.)27 b(Peter)i(Deutsch)g(<ghost@aladd)q(in.c)q
(om>)i(and)114 252 y(Glenn)d(Randers-Pehr)q(son)j(<randeg@alumni.)q
(rpi)q(.edu)q(>)0 2869 y Fj(Deutsch)649 b(Informational)h([Page)11
b(15])p eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.