%!PS-Adobe-2.0
%%Creator: dvipsk 5.55a Copyright 1986, 1994 Radical Eye Software
%%Title: rfc-deflate.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.ps deflate.dvi
%DVIPSParameters: dpi=300, compressed, comments removed
%DVIPSSource:  TeX output 1996.05.23:2040
%%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.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)1301
b(P)-5 b(.)12 b(Deutsch)0 252 y(Request)f(for)g(Comments:)k(1951)1049
b(Aladdin)10 b(Enterprises)0 308 y(Category:)k(Informational)1319
b(May)12 b(1996)79 479 y Fi(DEFLA)-8 b(TE)17 b(Compressed)g(Data)g
(Format)g(Speci\256cation)g(version)g(1.3)0 704 y Fh(Status)e(of)g
(This)g(Memo)0 836 y Fj(This)10 b(memo)j(provides)d(information)g(for)i
(the)f(Internet)g(community)m(.)16 b(This)10 b(memo)i(does)f(not)g
(specify)g(an)h(Internet)f(stan-)0 893 y(dard)g(of)g(any)g(kind.)k
(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)e
(on)i(the)g(validity)e(of)i(any)h(Intellectual)e(Property)h(Rights)f
(statements)g(contained)g(in)h(this)0 1257 y(document.)0
1433 y Fh(Notices)0 1565 y Fj(Copyright)208 1564 y(c)196
1565 y Fg(\015)g Fj(1996)e(L.)h(Peter)h(Deutsch)0 1651
y(Permission)h(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)8 b(into)g(other)i(languages)f(and)g
(incorporation)f(into)h(compilations,)g(provided)f(that)h(the)h
(copyright)e(notice)h(and)0 1764 y(this)g(notice)g(are)i(preserved,)g
(and)f(that)f(any)h(substantive)e(changes)i(or)g(deletions)e(from)j
(the)f(original)f(are)h(clearly)g(marked.)0 1850 y(A)i(pointer)f(to)g
(the)h(latest)e(version)h(of)h(this)f(and)g(related)h(documentation)e
(in)i(HTML)f(format)i(can)f(be)g(found)f(at)h(the)f(URL)0
1906 y Ff(<)p Fj(ftp://ftp.uu.net/graphics/)o(png)o(/docu)o(ments/zl)o
(ib/)o(zdoc-index)o(.html)p Ff(>)p Fj(.)0 2083 y Fh(Abstract)0
2217 y Fj(This)i(speci\256cation)h(de\256nes)g(a)g(lossless)f
(compressed)h(data)g(format)h(that)e(compresses)i(data)f(using)f(a)h
(combination)f(of)0 2273 y(the)d(LZ77)f(algorithm)f(and)i(Huf)o(fman)g
(coding,)g(with)e(ef)o(\256ciency)j(comparable)f(to)f(the)h(best)f
(currently)g(available)g(general-)0 2329 y(purpose)h(compression)g
(methods.)k(The)d(data)g(can)g(be)g(produced)f(or)h(consumed,)g(even)g
(for)g(an)g(arbitrarily)f(long)g(sequen-)0 2386 y(tially)d(presented)g
(input)g(data)g(stream,)j(using)c(only)h(an)i Fe(a)e(priori)g
Fj(bounded)f(amount)i(of)g(intermediate)f(storage.)14
b(The)8 b(format)0 2442 y(can)j(be)h(implemented)e(readily)h(in)g(a)g
(manner)h(not)e(covered)i(by)e(patents.)0 2719 y(Deutsch)698
b(Informational)g([Page)12 b(1])p eop
%%Page: 2 2
2 1 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 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(.)g(.)g(.)g(.)64 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(.)g(.)g(.)g(.)64
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(.)
g(.)g(.)g(.)64 b(2)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(.)g(.)g(.)g(.)64 b(2)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(.)g(.)g(.)g(.)64
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(.)g(.)g(.)g(.)64 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(.)g(.)g(.)g(.)64
b(3)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(.)g(.)g(.)g(.)64
b(3)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(.)g(.)g(.)g(.)64 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(.)g(.)g(.)g(.)64 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(.)g(.)g(.)g(.)64 b(4)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(.)g(.)g(.)g(.)64 b(5)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(.)g(.)g(.)g(.)64 b(5)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(.)g(.)g(.)g(.)64 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(.)g(.)g(.)g(.)64 b(7)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(.)g(.)g(.)g(.)64
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(.)g(.)g(.)g(.)64 b(9)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(.)g(.)g(.)g(.)
42 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(.)g(.)g(.)g(.)42 b(10)68 1371 y(3.3)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(.)g(.)g(.)g(.)42 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(.)g(.)g(.)g(.)42 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(.)g(.)g(.)g(.)42
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(.)
g(.)g(.)g(.)42 b(13)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(.)g(.)g(.)g(.)42 b(13)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(.)g(.)g(.)g(.)42
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(.)g(.)g(.)g(.)42 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)12
b(independent)f(of)i(CPU)g(type,)g(operating)e(system,)i(\256le)g
(system,)f(and)h(character)g(set,)g(and)f(hence)h(can)g(be)g(used)114
2283 y(for)e(interchange;)68 2370 y Fg(\017)23 b Fj(Can)13
b(be)f(produced)g(or)g(consumed,)h(even)g(for)f(an)h(arbitrarily)e
(long)h(sequentially)e(presented)i(input)f(data)h(stream,)114
2426 y(using)f(only)h(an)g Fe(a)h(priori)e Fj(bounded)g(amount)i(of)f
(intermediate)h(storage,)f(and)h(hence)g(can)g(be)g(used)f(in)g(data)h
(com-)114 2483 y(munications)c(or)i(similar)g(structures)f(such)h(as)g
(Unix)f(\256lters;)0 2719 y(Deutsch)698 b(Informational)g([Page)12
b(2])p eop
%%Page: 3 3
3 2 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)68 195 y Fg(\017)23 b Fj(Compresses)10 b(data)g(with)f(ef)o
(\256ciency)i(comparable)g(to)f(the)g(best)f(currently)h(available)g
(general-purpose)f(compres-)114 252 y(sion)h(methods,)h(and)g(in)f
(particular)h(considerably)e(better)i(than)g(the)g(\252compress\272)g
(program;)68 337 y Fg(\017)23 b Fj(Can)11 b(be)g(implemented)g(readily)
g(in)g(a)g(manner)h(not)e(covered)h(by)g(patents,)g(and)g(hence)g(can)h
(be)f(practiced)g(freely;)68 423 y Fg(\017)23 b Fj(Is)10
b(compatible)g(with)f(the)h(\256le)h(format)f(produced)g(by)g(the)g
(current)h(widely)e(used)h(gzip)f(utility)m(,)g(in)h(that)g(conforming)
114 479 y(decompressors)g(will)g(be)h(able)h(to)e(read)i(data)f
(produced)f(by)h(the)g(existing)f(gzip)g(compressor)n(.)0
564 y(The)h(data)g(format)h(de\256ned)f(by)g(this)f(speci\256cation)g
(does)h(not)f(attempt)h(to:)68 649 y Fg(\017)23 b Fj(Allow)10
b(random)h(access)g(to)g(compressed)g(data;)68 735 y
Fg(\017)23 b Fj(Compress)10 b(specialized)g(data)h(\(e.g.,)h(raster)f
(graphics\))f(as)h(well)f(as)h(the)g(best)f(currently)g(available)g
(specialized)g(al-)114 791 y(gorithms.)0 876 y(A)e(simple)f(counting)g
(ar)o(gument)h(shows)f(that)g(no)h(lossless)e(compression)h(algorithm)g
(can)h(compress)g(every)g(possible)f(input)0 933 y(data)14
b(set.)23 b(For)15 b(the)e(format)i(de\256ned)f(here,)h(the)f(worst)f
(case)i(expansion)d(is)i(5)g(bytes)f(per)h(32K-byte)f(block,)h(i.e.,)i
(a)e(size)0 989 y(increase)f(of)g(0.015\045)f(for)i(lar)o(ge)f(data)g
(sets.)20 b(English)11 b(text)h(usually)g(compresses)g(by)h(a)g(factor)
h(of)f(2.5)g(to)f(3;)i(executable)0 1046 y(\256les)d(usually)f
(compress)h(somewhat)g(less;)f(graphical)g(data)h(such)g(as)g(raster)h
(images)f(may)g(compress)g(much)h(more.)0 1197 y Fd(1.2)50
b(Intended)12 b(audience)0 1313 y Fj(This)h(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
1369 y(and/or)10 b(decompress)h(data)h(from)f(\252de\257ate\272)h
(format.)0 1454 y(The)e(text)f(of)i(the)e(speci\256cation)g(assumes)h
(a)h(basic)e(background)g(in)h(programming)g(at)g(the)g(level)f(of)h
(bits)f(and)h(other)g(prim-)0 1511 y(itive)g(data)h(representations.)j
(Familiarity)c(with)h(the)f(technique)h(of)g(Huf)o(fman)g(coding)f(is)h
(helpful)f(but)h(not)f(required.)0 1662 y Fd(1.3)50 b(Scope)0
1778 y Fj(The)11 b(speci\256cation)g(speci\256es)g(a)h(method)f(for)h
(representing)e(a)i(sequence)g(of)f(bytes)g(as)h(a)g(\(usually)e
(shorter\))h(sequence)g(of)0 1834 y(bits,)f(and)h(a)h(method)f(for)g
(packing)f(the)h(latter)g(bit)f(sequence)h(into)f(bytes.)0
1986 y Fd(1.4)50 b(Compliance)0 2102 y Fj(Unless)7 b(otherwise)h
(indicated)f(below)m(,)h(a)h(compliant)e(decompressor)h(must)g(be)h
(able)f(to)g(accept)h(and)f(decompress)g(any)g(data)0
2158 y(set)h(that)g(conforms)g(to)g(all)g(the)g(speci\256cations)f
(presented)g(here;)i(a)g(compliant)e(compressor)h(must)g(produce)g
(data)g(sets)g(that)0 2214 y(conform)i(to)g(all)g(the)g
(speci\256cations)f(presented)g(here.)0 2366 y Fd(1.5)63
b(De\256nitions)11 b(of)h(terms)h(and)f(conventions)f(used)0
2482 y Fj(Byte:)k(8)c(bits)f(stored)g(or)i(transmitted)e(as)h(a)g(unit)
g(\(same)g(as)h(an)f(octet\).)k(For)d(this)e(speci\256cation,)g(a)i
(byte)e(is)h(exactly)g(8)g(bits,)0 2538 y(even)g(on)g(machines)g(which)
f(store)g(a)i(character)g(on)e(a)i(number)f(of)g(bits)f(dif)o(ferent)h
(from)g(eight.)j(See)e(below)m(,)f(for)g(the)g(num-)0
2594 y(bering)f(of)i(bits)e(within)f(a)j(byte.)0 2719
y(Deutsch)698 b(Informational)g([Page)12 b(3])p eop
%%Page: 4 4
4 3 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)0 195 y(String:)k(a)d(sequence)g(of)h(arbitrary)e(bytes.)0
345 y Fd(1.6)50 b(Changes)12 b(fr)o(om)h(pr)o(evious)f(versions)0
461 y Fj(There)e(have)h(been)f(no)g(technical)g(changes)g(to)f(the)h
(de\257ate)h(format)g(since)f(version)f(1.1)h(of)h(this)e
(speci\256cation.)14 b(In)c(version)0 517 y(1.2,)i(some)f(terminology)e
(was)i(changed.)k(V)-5 b(ersion)11 b(1.3)g(is)g(a)g(conversion)f(of)h
(the)g(speci\256cation)f(to)h(RFC)h(style.)0 689 y Fh(2)60
b(Compr)o(essed)14 b(r)o(epr)o(esentation)f(overview)0
820 y Fj(A)f(compressed)f(data)h(set)f(consists)f(of)i(a)g(series)g(of)
f(blocks,)h(corresponding)d(to)j(successive)f(blocks)f(of)i(input)e
(data.)17 b(The)0 877 y(block)10 b(sizes)h(are)h(arbitrary)m(,)f
(except)g(that)g(non-compressible)e(blocks)h(are)i(limited)e(to)h
(65,535)f(bytes.)0 961 y(Each)j(block)e(is)h(compressed)h(using)e(a)i
(combination)e(of)i(the)f(LZ77)g(algorithm)f(and)i(Huf)o(fman)g
(coding.)18 b(The)13 b(Huf)o(fman)0 1018 y(trees)c(for)h(each)g(block)e
(are)i(independent)e(of)h(those)g(for)g(previous)f(or)i(subsequent)d
(blocks;)i(the)g(LZ77)f(algorithm)h(may)g(use)0 1074
y(a)j(reference)g(to)f(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
1159 y(Each)h(block)f(consists)f(of)i(two)g(parts:)k(a)c(pair)g(of)g
(Huf)o(fman)g(code)g(trees)g(that)g(describe)f(the)h(representation)f
(of)h(the)g(com-)0 1215 y(pressed)7 b(data)h(part,)h(and)f(a)g
(compressed)g(data)g(part.)14 b(\(The)8 b(Huf)o(fman)h(trees)e
(themselves)h(are)g(compressed)g(using)f(Huf)o(fman)0
1272 y(encoding.\))19 b(The)13 b(compressed)f(data)h(consists)e(of)h(a)
h(series)g(of)g(elements)f(of)h(two)f(types:)17 b(literal)12
b(bytes)g(\(of)h(strings)e(that)0 1328 y(have)e(not)g(been)g(detected)g
(as)g(duplicated)e(within)h(the)h(previous)f(32K)g(input)g(bytes\),)h
(and)g(pointers)f(to)h(duplicated)e(strings,)0 1385 y(where)13
b(a)f(pointer)g(is)g(represented)g(as)g(a)h(pair)f Ff(<)p
Fj(length,)h(backward)f(distance)p Ff(>)p Fj(.)18 b(The)13
b(representation)e(used)h(in)g(the)g(\252de-)0 1441 y(\257ate\272)h
(format)h(limits)d(distances)h(to)g(32K)h(bytes)f(and)g(lengths)g(to)g
(258)g(bytes,)h(but)f(does)g(not)g(limit)g(the)h(size)g(of)f(a)i
(block,)0 1498 y(except)d(for)g(uncompressible)f(blocks,)g(which)h(are)
h(limited)e(as)h(noted)g(above.)0 1582 y(Each)h(type)g(of)h(value)f
(\(literals,)g(distances,)g(and)g(lengths\))f(in)h(the)g(compressed)g
(data)g(is)g(represented)g(using)f(a)i(Huf)o(fman)0 1638
y(code,)g(using)e(one)h(code)h(tree)g(for)f(literals)g(and)g(lengths)f
(and)h(a)h(separate)f(code)h(tree)f(for)h(distances.)18
b(The)12 b(code)h(trees)f(for)0 1695 y(each)g(block)e(appear)h(in)g(a)h
(compact)f(form)h(just)e(before)h(the)g(compressed)g(data)g(for)h(that)
e(block.)0 1867 y Fh(3)60 b(Detailed)13 b(speci\256cation)0
2000 y Fd(3.1)50 b(Overall)12 b(conventions)0 2115 y
Fj(In)f(the)g(diagrams)g(below)m(,)g(a)h(box)e(like)h(this:)114
2200 y Fc(+---+)114 2256 y(|)82 b(|)27 b(<--)h(the)g(vertical)i(bars)e
(might)h(be)f(missing)114 2312 y(+---+)0 2397 y Fj(represents)11
b(one)g(byte;)f(a)h(box)g(like)g(this:)114 2482 y Fc(+==============)q
(+)114 2538 y(|)382 b(|)114 2594 y(+==============)q(+)0
2719 y Fj(Deutsch)698 b(Informational)g([Page)12 b(4])p
eop
%%Page: 5 5
5 4 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)0 195 y(represents)h(a)g(variable)g(number)g(of)g(bytes.)0
282 y(Bytes)g(stored)g(within)f(a)i(computer)f(do)g(not)g(have)h(a)g
(\252bit)f(order)r(\272,)g(since)h(they)f(are)h(always)f(treated)g(as)h
(a)g(unit.)j(However)n(,)0 339 y(a)d(byte)f(considered)f(as)i(an)g
(integer)e(between)i(0)f(and)g(255)g(does)g(have)h(a)f(most-)h(and)f
(least-signi\256cant)e(bit,)j(and)f(since)g(we)0 395
y(write)f(numbers)g(with)f(the)h(most-signi\256cant)e(digit)h(on)g(the)
h(left,)h(we)f(also)g(write)g(bytes)f(with)g(the)h(most-signi\256cant)e
(bit)i(on)0 451 y(the)h(left.)16 b(In)11 b(the)g(diagrams)h(below)m(,)f
(we)g(number)h(the)f(bits)f(of)h(a)h(byte)f(so)g(that)g(bit)f(0)i(is)e
(the)i(least-signi\256cant)d(bit,)i(i.e.,)h(the)0 508
y(bits)e(are)i(numbered:)114 595 y Fc(+--------+)114
651 y(|76543210|)114 708 y(+--------+)0 795 y Fj(W)n(ithin)g(a)h
(computer)n(,)h(a)f(number)h(may)f(occupy)g(multiple)e(bytes.)20
b(All)13 b(multi-byte)e(numbers)i(in)g(the)f(format)i(described)0
851 y(here)d(are)h(stored)e(with)g(the)h(least-signi\256cant)e(byte)i
(\256rst)f(\(at)i(the)e(lower)h(memory)h(address\).)i(For)e(example,)f
(the)g(decimal)0 908 y(number)g(520)g(is)f(stored)h(as:)223
995 y Fc(0)218 b(1)114 1051 y(+--------+-----)q(---)q(+)114
1108 y(|00001000|00000)q(010)q(|)114 1164 y(+--------+-----)q(---)q(+)
141 1221 y(\303)g(\303)141 1277 y(|)g(|)141 1333 y(|)g(+)28
b(more)g(significant)j(byte)d(=)f(2)h(x)g(256)141 1390
y(+)f(less)i(significant)h(byte)e(=)g(8)0 1543 y Fb(3.1.1)45
b(Packing)11 b(into)g(bytes)0 1661 y Fj(This)c(document)g(does)g(not)f
(address)i(the)f(issue)f(of)i(the)f(order)h(in)f(which)g(bits)f(of)i(a)
g(byte)f(are)h(transmitted)e(on)i(a)g(bit-sequential)0
1717 y(medium,)13 b(since)g(the)f(\256nal)g(data)h(format)g(described)f
(here)h(is)f(byte-)g(rather)h(than)f(bit-oriented.)18
b(However)n(,)13 b(we)g(describe)0 1774 y(the)d(compressed)h(block)f
(format)h(in)f(below)m(,)g(as)h(a)g(sequence)g(of)f(data)h(elements)f
(of)h(various)f(bit)g(lengths,)f(not)h(a)h(sequence)0
1830 y(of)f(bytes.)k(W)l(e)d(must)f(therefore)g(specify)g(how)f(to)h
(pack)g(these)g(data)g(elements)g(into)f(bytes)g(to)h(form)g(the)g
(\256nal)g(compressed)0 1886 y(byte)h(sequence:)68 1973
y Fg(\017)23 b Fj(Data)8 b(elements)h(are)g(packed)f(into)g(bytes)f(in)
i(order)f(of)h(increasing)e(bit)h(number)h(within)e(the)h(byte,)h
(i.e.,)h(starting)d(with)114 2030 y(the)k(least-signi\256cant)e(bit)h
(of)h(the)g(byte.)68 2117 y Fg(\017)23 b Fj(Data)12 b(elements)g(other)
g(than)g(Huf)o(fman)h(codes)f(are)h(packed)f(starting)f(with)h(the)g
(least-signi\256cant)e(bit)i(of)g(the)g(data)114 2173
y(element.)68 2260 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 2347 y(In)j(other)f(words,)h(if)f(one)g(were)i(to)e(print)f
(out)h(the)g(compressed)h(data)f(as)h(a)g(sequence)f(of)h(bytes,)f
(starting)f(with)h(the)g(\256rst)0 2404 y(byte)d(at)h(the)g(*right*)e
(mar)o(gin)i(and)g(proceeding)f(to)g(the)h(*left*,)f(with)g(the)h
(most-signi\256cant)e(bit)h(of)h(each)g(byte)f(on)h(the)f(left)0
2460 y(as)k(usual,)g(one)g(would)e(be)i(able)g(to)g(parse)g(the)f
(result)g(from)i(right)e(to)g(left,)i(with)d(\256xed-width)h(elements)h
(in)f(the)h(correct)0 2517 y(MSB-to-LSB)d(order)f(and)g(Huf)o(fman)h
(codes)f(in)f(bit-reversed)h(order)g(\(i.e.,)h(with)e(the)h(\256rst)g
(bit)f(of)h(the)g(code)g(in)g(the)g(relative)0 2573 y(LSB)i
(position\).)0 2719 y(Deutsch)698 b(Informational)g([Page)12
b(5])p eop
%%Page: 6 6
6 5 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 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)c(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)g(each)0 487 y(symbol,)13
b(in)f(a)h(manner)h(such)e(that)g(dif)o(ferent)h(symbols)f(may)h(be)g
(represented)g(by)f(bit)g(sequences)h(of)g(dif)o(ferent)f(lengths,)0
543 y(but)e(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)i(de\256ne)g(a)h
(pre\256x)f(code)f(in)h(terms)g(of)f(a)i(binary)e(tree)h(in)f(which)g
(the)h(two)f(edges)g(descending)g(from)h(each)g(non-leaf)g(node)0
687 y(are)i(labeled)f(0)g(and)h(1)f(and)g(in)g(which)g(the)g(leaf)h
(nodes)e(correspond)h(one-for)o(-one)g(with)g(\(are)h(labeled)f(with\))
f(the)h(symbols)0 743 y(of)g(the)g(alphabet;)f(then)g(the)h(code)g(for)
g(a)g(symbol)f(is)h(the)g(sequence)f(of)h(0')n(s)g(and)f(1')n(s)h(on)f
(the)h(edges)g(leading)f(from)h(the)g(root)0 799 y(to)g(the)g(leaf)g
(labeled)g(with)f(that)g(symbol.)15 b(For)c(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)11 b(parser)f(can)h(decode)g(the)f(next)
g(symbol)g(from)h(an)f(encoded)h(input)e(stream)i(by)f(walking)f(down)h
(the)g(tree)h(from)g(the)f(root,)0 1538 y(at)h(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)14 b(an)h(alphabet)e(with)h(known)f(symbol)h(frequencies,)
h(the)g(Huf)o(fman)g(algorithm)e(allows)h(the)g(construction)e(of)j(an)
0 1681 y(optimal)9 b(pre\256x)h(code)g(\(one)g(which)f(represents)g
(strings)f(with)h(those)g(symbol)g(frequencies)g(using)g(the)g(fewest)h
(bits)f(of)g(any)0 1738 y(possible)f(pre\256x)i(codes)g(for)g(that)f
(alphabet\).)15 b(Such)10 b(a)g(code)g(is)f(called)h(a)g(Huf)o(fman)h
(code.)j(\(See)d(reference)g([1])g(in)e(Chapter)0 1794
y(5,)i(references)i(for)e(additional)e(information)h(on)h(Huf)o(fman)h
(codes.\))0 1881 y(Note)e(that)g(in)g(the)g(\252de\257ate\272)i
(format,)f(the)f(Huf)o(fman)h(codes)f(for)h(the)f(various)g(alphabets)f
(must)h(not)g(exceed)h(certain)g(max-)0 1938 y(imum)g(code)f(lengths.)k
(This)9 b(constraint)g(complicates)h(the)g(algorithm)g(for)g(computing)
f(code)i(lengths)e(from)i(symbol)e(fre-)0 1994 y(quencies.)15
b(Again,)10 b(see)i(Chapter)f(5,)g(references)i(for)e(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)13 b(codes)i(of)f(a)h(given)f(bit)g(length)f(have)i
(lexicographically)d(consecutive)h(values,)j(in)e(the)g(same)h(order)g
(as)f(the)114 2408 y(symbols)c(they)g(represent;)68 2495
y Fg(\017)23 b Fj(Shorter)11 b(codes)g(lexicographically)e(precede)i
(longer)g(codes.)0 2719 y(Deutsch)698 b(Informational)g([Page)12
b(6])p eop
%%Page: 7 7
7 6 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)0 195 y(W)l(e)h(could)f(recode)h(the)f(example)h(above)f(to)h
(follow)e(this)h(rule)g(as)h(follows,)e(assuming)h(that)g(the)g(order)h
(of)g(the)f(alphabet)g(is)0 252 y(ABCD:)114 339 y Fc(Symbol)56
b(Code)114 395 y(------)g(----)114 451 y(A)191 b(10)114
508 y(B)g(0)114 564 y(C)g(110)114 621 y(D)g(111)0 708
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
795 y(Given)j(this)f(rule,)i(we)f(can)h(de\256ne)f(the)g(Huf)o(fman)h
(code)f(for)h(an)f(alphabet)g(just)f(by)h(giving)f(the)h(bit)f(lengths)
g(of)h(the)h(codes)0 851 y(for)e(each)g(symbol)e(of)i(the)f(alphabet)g
(in)g(order;)h(this)e(is)h(suf)o(\256cient)g(to)g(determine)h(the)f
(actual)g(codes.)15 b(In)c(our)f(example,)h(the)0 908
y(code)f(is)g(completely)g(de\256ned)g(by)g(the)g(sequence)h(of)f(bit)g
(lengths)f(\(2,)i(1,)f(3,)h(3\).)k(The)c(following)d(algorithm)h
(generates)h(the)0 964 y(codes)j(as)h(integers,)g(intended)e(to)i(be)f
(read)i(from)f(most-)f(to)h(least-signi\256cant)d(bit.)22
b(The)14 b(code)g(lengths)e(are)i(initially)e(in)0 1021
y(tree[I].Len;)g(the)e(codes)h(are)h(produced)f(in)f(tree[I].Code.)0
1108 y(1\))h(Count)g(the)g(number)h(of)f(codes)g(for)g(each)h(code)g
(length.)i(Let)d(bl)p 1062 1108 14 2 v 16 w(count[N])g(be)g(the)g
(number)h(of)f(codes)g(of)g(length)f(N,)i(N)0 1164 y
Ff(>)p Fj(=)f(1.)0 1251 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
1338 y Fc(code)28 b(=)g(0;)223 1395 y(bl)p 280 1395 V
17 w(count[0])h(=)f(0;)223 1451 y(for)g(\(bits)g(=)g(1;)g(bits)g(<=)g
(MAX)p 934 1451 V 17 w(BITS;)h(bits++\))g Fg(f)332 1507
y Fc(code)f(=)g(\(code)g(+)g(bl)p 798 1507 V 17 w(count[bits-1]\))j(<<)
d(1;)332 1564 y(next)p 443 1564 V 17 w(code[bits])i(=)e(code;)223
1620 y Fg(g)0 1707 y Fj(3\))12 b(Assign)f(numerical)h(values)g(to)g
(all)g(codes,)g(using)f(consecutive)g(values)h(for)g(all)g(codes)g(of)g
(the)g(same)h(length)e(with)g(the)0 1764 y(base)i(values)f(determined)h
(at)g(step)g(2.)21 b(Codes)12 b(that)h(are)h(never)f(used)f(\(which)h
(have)g(a)g(bit)g(length)e(of)j(zero\))f(must)g(not)f(be)0
1820 y(assigned)e(a)h(value.)223 1907 y Fc(for)28 b(\(n)g(=)f(0;)55
b(n)28 b(<=)g(max)p 798 1907 V 17 w(code;)g(n++\))h Fg(f)332
1964 y Fc(len)f(=)f(tree[n].Len;)332 2020 y(if)h(\(len)g(!=)g(0\))g
Fg(f)441 2077 y Fc(tree[n].Code)i(=)e(next)p 961 2077
V 17 w(code[len];)441 2133 y(next)p 552 2133 V 17 w(code[len]++;)332
2190 y Fg(g)223 2246 y(g)0 2333 y Fj(Example:)0 2420
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:)0 2719 y(Deutsch)698 b(Informational)g([Page)12
b(7])p eop
%%Page: 8 8
8 7 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)114 195 y Fc(N)164 b(bl)p 362 195 14 2 v 16 w(count[N])114
252 y(-)g(-----------)114 308 y(2)g(1)114 364 y(3)g(5)114
421 y(4)g(2)0 508 y Fj(Step)11 b(2)g(computes)g(the)g(following)e(next)
p 649 508 V 16 w(code)i(values:)114 595 y Fc(N)164 b(next)p
416 595 V 17 w(code[N])114 651 y(-)g(------------)114
708 y(1)g(0)114 764 y(2)g(0)114 821 y(3)g(2)114 877 y(4)g(14)0
964 y Fj(Step)11 b(3)g(produces)g(the)g(following)e(code)i(values:)114
1051 y Fc(Symbol)29 b(Length)83 b(Code)114 1108 y(------)29
b(------)83 b(----)114 1164 y(A)191 b(3)218 b(010)114
1221 y(B)191 b(3)218 b(011)114 1277 y(C)191 b(3)218 b(100)114
1333 y(D)191 b(3)218 b(101)114 1390 y(E)191 b(3)218 b(110)114
1446 y(F)191 b(2)246 b(00)114 1503 y(G)191 b(4)g(1110)114
1559 y(H)g(4)g(1111)0 1712 y Fb(3.2.3)45 b(Details)11
b(of)g(block)g(format)0 1830 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 1917 y Fc(first)28 b(bit)192 b(BFINAL)114
1973 y(next)28 b(2)g(bits)137 b(BTYPE)0 2060 y Fj(Note)14
b(that)g(the)g(header)g(bits)g(do)g(not)f(necessarily)h(begin)f(on)h(a)
h(byte)f(boundary)m(,)g(since)g(a)h(block)f(does)f(not)h(necessarily)0
2117 y(occupy)d(an)g(integral)f(number)h(of)h(bytes.)0
2204 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 2291 y(BTYPE)g(speci\256es)g
(how)g(the)g(data)g(are)h(compressed,)f(as)g(follows:)114
2378 y Fc(00)27 b(-)h(no)g(compression)114 2434 y(01)f(-)h(compressed)i
(with)e(fixed)h(Huffman)g(codes)114 2491 y(10)e(-)h(compressed)i(with)e
(dynamic)i(Huffman)f(codes)114 2547 y(11)e(-)h(reserved)h(\(error\))0
2719 y Fj(Deutsch)698 b(Informational)g([Page)12 b(8])p
eop
%%Page: 9 9
9 8 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)0 195 y(The)i(only)f(dif)o(ference)h(between)f(the)h(two)f
(compressed)h(cases)g(is)f(how)g(the)h(Huf)o(fman)g(codes)g(for)g(the)f
(literal/length)e(and)0 252 y(distance)h(alphabets)g(are)i(de\256ned.)0
339 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:)114 419 y Fa(do)188
469 y(read)25 b(block)f(header)h(from)f(input)h(stream.)188
519 y(if)g(stored)f(with)h(no)g(compression)263 568 y(skip)g(any)f
(remaining)g(bits)h(in)g(current)f(partially)338 618
y(processed)g(byte)263 668 y(read)h(LEN)f(and)h(NLEN)f(\(see)h(next)f
(section\))263 718 y(copy)h(LEN)f(bytes)h(of)f(data)h(to)g(output)188
768 y(otherwise)263 817 y(if)g(compressed)f(with)g(dynamic)h(Huffman)f
(codes)338 867 y(read)g(representation)g(of)h(code)f(trees)h(\(see)413
917 y(subsection)e(below\))263 967 y(loop)i(\(until)f(end)h(of)f(block)
h(code)f(recognized\))338 1017 y(decode)g(literal/length)g(value)g
(from)h(input)f(stream)338 1066 y(if)h(value)f(<)h(256)413
1116 y(copy)f(value)g(\(literal)h(byte\))f(to)h(output)f(stream)338
1166 y(otherwise)413 1216 y(if)g(value)h(=)f(end)h(of)g(block)f
(\(256\))487 1266 y(break)h(from)f(loop)413 1316 y(otherwise)g(\(value)
g(=)h(257..285\))487 1365 y(decode)g(distance)f(from)g(input)h(stream)
487 1465 y(move)g(backwards)f(distance)g(bytes)g(in)h(the)g(output)487
1515 y(stream,)f(and)h(copy)g(length)f(bytes)g(from)h(this)487
1565 y(position)f(to)h(the)g(output)f(stream.)263 1614
y(end)h(loop)114 1664 y(while)f(not)h(last)f(block)0
1751 y Fj(Note)11 b(that)g(a)h(duplicated)f(string)f(reference)j(may)f
(refer)h(to)e(a)h(string)f(in)g(a)h(previous)e(block;)h(i.e.,)i(the)e
(backward)h(distance)0 1808 y(may)g(cross)f(one)h(or)g(more)g(block)f
(boundaries.)k(However)d(a)g(distance)f(cannot)g(refer)h(past)g(the)f
(beginning)f(of)h(the)h(output)0 1864 y(stream.)j(\(An)9
b(application)e(using)h(a)i(preset)e(dictionary)g(might)g(discard)h
(part)g(of)g(the)g(output)e(stream;)j(a)g(distance)e(can)h(refer)0
1921 y(to)f(that)f(part)h(of)g(the)g(output)f(stream)h(anyway\))g(Note)
g(also)f(that)h(the)g(referenced)h(string)e(may)h(overlap)g(the)g
(current)g(position;)0 1977 y(for)i(example,)h(if)g(the)f(last)f(2)h
(bytes)g(decoded)g(have)g(values)f(X)i(and)f(Y)-6 b(,)10
b(a)h(string)e(reference)j(with)d Ff(<)p Fj(length)g(=)h(5,)h(distance)
e(=)0 2034 y(2)p Ff(>)i Fj(adds)g(X,Y)-6 b(,X,Y)g(,X)12
b(to)f(the)g(output)e(stream.)0 2121 y(W)l(e)j(now)e(specify)h(each)h
(compression)e(method)h(in)f(turn.)0 2274 y Fb(3.2.4)45
b(Non-compr)o(essed)12 b(blocks)f(\(BTYPE=00\))0 2391
y Fj(Any)h(bits)f(of)i(input)e(up)h(to)g(the)g(next)g(byte)g(boundary)f
(are)j(ignored.)k(The)12 b(rest)h(of)f(the)g(block)g(consists)f(of)h
(the)g(following)0 2448 y(information:)0 2719 y(Deutsch)698
b(Informational)g([Page)12 b(9])p eop
%%Page: 10 10
10 9 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)168 195 y Fc(0)82 b(1)g(2)g(3)h(4...)114 252 y(+---+---+---+--)q
(-+=)q(====)q(====)q(===)q(====)q(====)q(===)q(====)q(====)q(=+)114
308 y(|)54 b(LEN)i(|)27 b(NLEN)56 b(|...)28 b(LEN)g(bytes)h(of)f
(literal)h(data...|)114 364 y(+---+---+---+--)q(-+=)q(====)q(====)q
(===)q(====)q(====)q(===)q(====)q(====)q(=+)0 451 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 605 y
Fb(3.2.5)45 b(Compr)o(essed)12 b(blocks)f(\(length)h(and)f(distance)h
(codes\))0 722 y Fj(As)h(noted)g(above,)h(encoded)f(data)h(blocks)e(in)
h(the)g(\252de\257ate\272)h(format)g(consist)e(of)i(sequences)f(of)g
(symbols)f(drawn)i(from)0 779 y(three)k(conceptually)e(distinct)h
(alphabets:)27 b(either)17 b(literal)h(bytes,)h(from)f(the)g(alphabet)f
(of)h(byte)g(values)f(\(0..255\),)j(or)0 835 y Ff(<)p
Fj(length,)10 b(backward)g(distance)p Ff(>)g Fj(pairs,)h(where)f(the)h
(length)e(is)h(drawn)g(from)h(\(3..258\))g(and)f(the)g(distance)g(is)f
(drawn)i(from)0 892 y(\(1..32,768\).)22 b(In)13 b(fact,)i(the)e
(literal)g(and)g(length)f(alphabets)g(are)i(mer)o(ged)g(into)f(a)h
(single)e(alphabet)g(\(0..285\),)j(where)e(val-)0 948
y(ues)d(0..255)g(represent)g(literal)f(bytes,)h(the)g(value)g(256)f
(indicates)g(end-of-block,)h(and)g(values)f(257..285)g(represent)h
(length)0 1004 y(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
1091 y Fc(Extra)410 b(Extra)h(Extra)114 1148 y(Code)28
b(Bits)g(Length\(s\))i(Code)e(Bits)h(Lengths)84 b(Code)28
b(Bits)g(Length\(s\))114 1204 y(----)g(----)g(------)138
b(----)29 b(----)f(-------)84 b(----)28 b(----)h(-------)141
1261 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 1317 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 1374 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
1430 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 1487 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 1543 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 1600 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 1656 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 1712 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 1769 y(266)83
b(1)54 b(13,14)165 b(276)83 b(3)f(59-66)0 1856 y Fj(The)12
b(extra)g(bits)f(should)g(be)h(interpreted)f(as)i(a)f(machine)g
(integer)g(stored)f(with)h(the)f(most-signi\256cant)g(bit)g(\256rst,)i
(e.g.,)g(bits)0 1912 y(1)n(1)n(10)e(represent)g(the)g(value)g(14.)0
2719 y(Deutsch)687 b(Informational)g([Page)11 b(10])p
eop
%%Page: 11 11
11 10 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)277 195 y Fc(Extra)302 b(Extra)410 b(Extra)141
252 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 308 y(----)f(----)h(----)55
b(----)29 b(----)55 b(------)111 b(----)28 b(----)h(--------)195
364 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 421 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 477 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
534 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 590 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 647 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
703 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 760 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 816 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 873 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 1026 y Fb(3.2.6)45 b(Compr)o(ession)11
b(with)g(\256xed)h(Huffman)g(codes)g(\(BTYPE=01\))0 1143
y Fj(The)e(Huf)o(fman)h(codes)g(for)f(the)h(two)e(alphabets)h(are)h
(\256xed,)g(and)f(are)i(not)d(represented)i(explicitly)d(in)i(the)g
(data.)15 b(The)c(Huf)o(f-)0 1200 y(man)h(code)f(lengths)e(for)j(the)f
(literal/length)d(alphabet)j(are:)305 1287 y Fc(Lit)28
b(Value)110 b(Bits)219 b(Codes)305 1343 y(---------)111
b(----)219 b(-----)359 1400 y(0)28 b(-)f(143)137 b(8)273
b(00110000)30 b(through)986 1456 y(10111111)305 1513
y(144)e(-)f(255)137 b(9)273 b(110010000)30 b(through)986
1569 y(111111111)305 1625 y(256)e(-)f(279)137 b(7)273
b(0000000)30 b(through)986 1682 y(0010111)305 1738 y(280)e(-)f(287)137
b(8)273 b(11000000)30 b(through)986 1795 y(11000111)0
1882 y Fj(The)13 b(code)g(lengths)e(are)j(suf)o(\256cient)e(to)h
(generate)g(the)g(actual)f(codes,)i(as)f(described)f(above;)h(we)h
(show)e(the)g(codes)h(in)f(the)0 1938 y(table)g(for)g(added)g(clarity)m
(.)18 b(Literal/length)10 b(values)i(286-287)f(will)g(never)h(actually)
g(occur)g(in)g(the)g(compressed)g(data,)h(but)0 1995
y(participate)d(in)h(the)g(code)g(construction.)0 2082
y(Distance)g(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)g(in)0 2138 y(the)h(table)g(shown)g(in)g(Paragraph)h
(3.2.5,)g(above.)19 b(Note)12 b(that)g(distance)g(codes)g(30-31)g(will)
f(never)i(actually)f(occur)g(in)g(the)0 2195 y(compressed)f(data.)0
2348 y Fb(3.2.7)45 b(Compr)o(ession)11 b(with)g(dynamic)g(Huffman)h
(codes)g(\(BTYPE=10\))0 2465 y Fj(The)g(Huf)o(fman)h(codes)g(for)f(the)
h(two)f(alphabets)f(appear)i(in)f(the)g(block)g(immediately)g(after)h
(the)f(header)h(bits)f(and)g(before)0 2522 y(the)f(actual)h(compressed)
f(data,)i(\256rst)e(the)h(literal/length)d(code)j(and)f(then)h(the)f
(distance)g(code.)17 b(Each)12 b(code)g(is)f(de\256ned)h(by)0
2578 y(a)f(sequence)g(of)g(code)g(lengths,)f(as)h(discussed)e(in)i
(Paragraph)g(3.2.2,)h(above.)j(For)c(even)g(greater)h(compactness,)e
(the)h(code)0 2719 y(Deutsch)688 b(Informational)f([Page)12
b(1)n(1])p eop
%%Page: 12 12
12 11 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)0 195 y(length)k(sequences)g(themselves)g(are)i(compressed)f
(using)e(a)i(Huf)o(fman)h(code.)26 b(The)15 b(alphabet)f(for)h(code)g
(lengths)f(is)g(as)0 252 y(follows:)195 339 y Fc(0)28
b(-)g(15:)g(Represent)h(code)g(lengths)g(of)f(0)f(-)h(15)305
395 y(16:)g(Copy)g(the)g(previous)i(code)e(length)h(3)e(-)h(6)f(times.)
414 451 y(The)h(next)g(2)g(bits)g(indicate)h(repeat)g(length)577
508 y(\(0)f(=)g(3,)f(...)i(,)e(3)h(=)f(6\))495 564 y(Example:)57
b(Codes)29 b(8,)f(16)f(\(+2)i(bits)f(11\),)768 621 y(16)g(\(+2)g(bits)g
(10\))h(will)f(expand)h(to)768 677 y(12)f(code)g(lengths)i(of)d(8)h
(\(1)g(+)f(6)h(+)f(5\))305 734 y(17:)h(Repeat)h(a)e(code)h(length)h(of)
f(0)g(for)g(3)f(-)h(10)g(times.)414 790 y(\(3)f(bits)i(of)f(length\))
305 847 y(18:)g(Repeat)h(a)e(code)h(length)h(of)f(0)g(for)g(11)g(-)f
(138)h(times)414 903 y(\(7)f(bits)i(of)f(length\))0 990
y Fj(A)11 b(code)f(length)g(of)h(0)f(indicates)g(that)g(the)g
(corresponding)f(symbol)h(in)g(the)h(literal/length)d(or)j(distance)e
(alphabet)h(will)g(not)0 1047 y(occur)j(in)f(the)g(block,)h(and)f
(should)f(not)h(participate)g(in)g(the)g(Huf)o(fman)h(code)g
(construction)d(algorithm)i(given)f(earlier)n(.)20 b(If)0
1103 y(only)12 b(one)g(distance)g(code)h(is)f(used,)h(it)f(is)g
(encoded)g(using)f(one)i(bit,)f(not)g(zero)h(bits;)f(in)g(this)g(case)h
(there)g(is)f(a)h(single)e(code)0 1159 y(length)f(of)i(one,)g(with)e
(one)i(unused)e(code.)17 b(One)11 b(distance)g(code)h(of)f(zero)h(bits)
f(means)h(that)f(there)g(are)i(no)e(distance)g(codes)0
1216 y(used)g(at)g(all)g(\(the)g(data)g(is)f(all)h(literals\).)0
1303 y(W)l(e)h(can)f(now)g(de\256ne)g(the)g(format)h(of)f(the)g(block:)
188 1383 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 1433 y(5)h(Bits:)g(HDIST,)f(#)h(of)f
(Distance)h(codes)f(-)h(1)199 b(\(1)25 b(-)g(32\))188
1483 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 1583 y(\(HCLEN)g(+)g(4\))f(x)h(3)g(bits:)f
(code)h(lengths)f(for)h(the)f(code)h(length)263 1632
y(alphabet)f(given)h(just)f(above,)h(in)f(the)h(order:)f(16,)h(17,)f
(18,)263 1682 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 1782 y(These)h(code)f(lengths)g(are)
h(interpreted)f(as)h(3-bit)f(integers)263 1832 y(\(0-7\);)g(as)h
(above,)f(a)h(code)g(length)f(of)h(0)g(means)f(the)263
1881 y(corresponding)g(symbol)g(\(literal/length)g(or)g(distance)g
(code)263 1931 y(length\))g(is)h(not)g(used.)188 2031
y(HLIT)g(+)g(257)f(code)h(lengths)f(for)h(the)f(literal/length)g
(alphabet,)263 2081 y(encoded)g(using)h(the)f(code)h(length)f(Huffman)h
(code)188 2180 y(HDIST)g(+)g(1)f(code)h(lengths)f(for)h(the)f(distance)
h(alphabet,)263 2230 y(encoded)f(using)h(the)f(code)h(length)f(Huffman)
h(code)188 2330 y(The)g(actual)f(compressed)g(data)h(of)g(the)f(block,)
263 2380 y(encoded)g(using)h(the)f(literal/length)g(and)h(distance)f
(Huffman)263 2429 y(codes)188 2529 y(The)h(literal/length)f(symbol)g
(256)h(\(end)f(of)h(data\),)263 2579 y(encoded)f(using)h(the)f
(literal/length)g(Huffman)g(code)0 2719 y Fj(Deutsch)687
b(Informational)g([Page)11 b(12])p eop
%%Page: 13 13
13 12 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)0 195 y(The)g(code)g(length)f(repeat)i(codes)f(can)g(cross)g
(from)g(HLIT)g(+)g(257)g(to)g(the)g(HDIST)g(+)g(1)g(code)g(lengths.)k
(In)c(other)g(words,)g(all)0 252 y(code)h(lengths)f(form)i(a)f(single)f
(sequence)h(of)g(HLIT)g(+)g(HDIST)g(+)g(258)g(values.)0
406 y Fd(3.3)50 b(Compliance)0 524 y Fj(A)14 b(compressor)f(may)h
(limit)f(further)h(the)f(ranges)g(of)h(values)f(speci\256ed)h(in)f(the)
g(previous)g(section)f(and)i(still)e(be)i(compli-)0 580
y(ant;)e(for)h(example,)g(it)f(may)h(limit)e(the)h(range)h(of)f
(backward)g(pointers)f(to)h(some)h(value)f(smaller)g(than)g(32K.)g
(Similarly)m(,)h(a)0 637 y(compressor)e(may)h(limit)e(the)h(size)g(of)g
(blocks)f(so)h(that)f(a)i(compressible)e(block)g(\256ts)h(in)g(memory)m
(.)0 724 y(A)f(compliant)g(decompressor)g(must)g(accept)g(the)g(full)g
(range)h(of)f(possible)e(values)i(de\256ned)g(in)g(the)g(previous)g
(section,)f(and)0 780 y(must)i(accept)g(blocks)f(of)h(arbitrary)g
(size.)0 957 y Fh(4)60 b(Compr)o(ession)14 b(algorithm)f(details)0
1091 y Fj(While)f(it)h(is)f(the)h(intent)e(of)i(this)f(document)h(to)f
(de\256ne)h(the)g(\252de\257ate\272)h(compressed)e(data)h(format)g
(without)e(reference)k(to)0 1147 y(any)f(particular)g(compression)f
(algorithm,)h(the)g(format)g(is)g(related)g(to)g(the)g(compressed)g
(formats)g(produced)f(by)h(LZ77)0 1204 y(\(Lempel-Ziv)7
b(1977,)h(see)g(reference)h([2])f(below\);)g(since)f(many)h(variations)
f(of)g(LZ77)g(are)i(patented,)f(it)f(is)g(strongly)f(recom-)0
1260 y(mended)11 b(that)g(the)f(implementor)h(of)g(a)h(compressor)e
(follow)g(the)h(general)g(algorithm)f(presented)g(here,)i(which)f(is)f
(known)0 1317 y(not)h(to)f(be)i(patented)e(per)i(se.)k(The)11
b(material)g(in)g(this)f(section)h(is)g(not)f(part)h(of)h(the)f
(de\256nition)f(of)h(the)g(speci\256cation)f(per)i(se,)0
1373 y(and)f(a)h(compressor)e(need)i(not)e(follow)g(it)h(in)f(order)i
(to)e(be)i(compliant.)0 1460 y(The)h(compressor)f(terminates)h(a)g
(block)f(when)g(it)g(determines)h(that)f(starting)f(a)i(new)g(block)f
(with)g(fresh)h(trees)f(would)g(be)0 1516 y(useful,)f(or)g(when)g(the)g
(block)f(size)h(\256lls)g(up)g(the)f(compressor)r(')n(s)g(block)h(buf)o
(fer)n(.)0 1603 y(The)h(compressor)g(uses)g(a)g(chained)g(hash)g(table)
g(to)g(\256nd)g(duplicated)f(strings,)g(using)g(a)h(hash)g(function)f
(that)h(operates)g(on)0 1660 y(3-byte)d(sequences.)15
b(At)10 b(any)g(given)f(point)g(during)g(compression,)g(let)h(XYZ)g(be)
g(the)g(next)f(3)h(input)f(bytes)g(to)h(be)g(examined)0
1716 y(\(not)e(necessarily)h(all)f(dif)o(ferent,)i(of)f(course\).)15
b(First,)9 b(the)g(compressor)g(examines)g(the)f(hash)h(chain)g(for)g
(XYZ.)14 b(If)c(the)f(chain)0 1773 y(is)h(empty)m(,)g(the)g(compressor)
g(simply)g(writes)f(out)h(X)g(as)g(a)h(literal)e(byte)h(and)g(advances)
g(one)g(byte)g(in)f(the)h(input.)k(If)d(the)f(hash)0
1829 y(chain)f(is)f(not)g(empty)m(,)i(indicating)d(that)h(the)h
(sequence)g(XYZ)f(\(or)n(,)i(if)f(we)g(are)h(unlucky)m(,)e(some)h
(other)g(3)g(bytes)f(with)g(the)h(same)0 1886 y(hash)h(function)e
(value\))i(has)g(occurred)g(recently)m(,)h(the)e(compressor)h(compares)
h(all)e(strings)g(on)g(the)h(XYZ)g(hash)f(chain)h(with)0
1942 y(the)h(actual)g(input)f(data)h(sequence)g(starting)e(at)j(the)e
(current)i(point,)e(and)h(selects)f(the)h(longest)f(match.)0
2029 y(The)i(compressor)f(searches)i(the)e(hash)h(chains)f(starting)f
(with)h(the)h(most)f(recent)i(strings,)e(to)g(favor)h(small)g
(distances)e(and)0 2086 y(thus)d(take)i(advantage)f(of)g(the)g(Huf)o
(fman)h(encoding.)14 b(The)8 b(hash)g(chains)g(are)h(singly)e(linked.)
13 b(There)c(are)g(no)f(deletions)f(from)0 2142 y(the)i(hash)g(chains;)
f(the)h(algorithm)f(simply)h(discards)f(matches)h(that)g(are)h(too)e
(old.)14 b(T)m(o)9 b(avoid)f(a)i(worst-case)f(situation,)e(very)0
2199 y(long)j(hash)h(chains)f(are)i(arbitrarily)e(truncated)h(at)g(a)h
(certain)f(length,)f(determined)h(by)g(a)g(run-time)g(parameter)n(.)0
2286 y(T)m(o)i(improve)h(overall)f(compression,)h(the)f(compressor)h
(optionally)d(defers)j(the)f(selection)g(of)h(matches)g(\(\252lazy)g
(match-)0 2342 y(ing\272\):)i(after)c(a)h(match)f(of)g(length)f(N)h
(has)g(been)g(found,)g(the)g(compressor)f(searches)i(for)f(a)g(longer)g
(match)g(starting)e(at)i(the)0 2398 y(next)d(input)f(byte.)14
b(If)c(it)f(\256nds)f(a)i(longer)f(match,)h(it)f(truncates)g(the)g
(previous)f(match)h(to)g(a)h(length)e(of)h(one)h(\(thus)e(producing)g
(a)0 2455 y(single)h(literal)g(byte\))g(and)h(then)f(emits)g(the)h
(longer)f(match.)15 b(Otherwise,)9 b(it)h(emits)f(the)h(original)e
(match,)j(and,)f(as)g(described)0 2511 y(above,)h(advances)g(N)g(bytes)
g(before)g(continuing.)0 2719 y(Deutsch)687 b(Informational)g([Page)11
b(13])p eop
%%Page: 14 14
14 13 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)0 195 y(Run-time)i(parameters)i(also)e(control)f(this)g
(\252lazy)i(match\272)g(procedure.)19 b(If)13 b(compression)f(ratio)g
(is)g(most)g(important,)g(the)0 252 y(compressor)d(attempts)g(a)g
(complete)h(second)e(search)i(regardless)f(of)g(the)h(length)e(of)h
(the)g(\256rst)h(match.)15 b(In)9 b(the)g(normal)g(case,)0
308 y(if)j(the)f(current)h(match)g(is)g(\252long)f(enough\272,)g(the)h
(compressor)g(reduces)g(the)f(search)h(for)g(a)h(longer)e(match,)i
(thus)d(speeding)0 364 y(up)f(the)h(process.)k(If)c(speed)g(is)f(most)g
(important,)g(the)h(compressor)f(inserts)g(new)g(strings)f(in)i(the)f
(hash)g(table)h(only)e(when)i(no)0 421 y(match)i(was)g(found,)f(or)h
(when)f(the)h(match)g(is)f(not)g(\252too)h(long\272.)k(This)11
b(degrades)g(the)h(compression)e(ratio)i(but)f(saves)g(time)0
477 y(since)g(there)g(are)h(both)e(fewer)i(insertions)d(and)i(fewer)h
(searches.)0 654 y Fh(5)60 b(Refer)o(ences)0 788 y Fj([1])12
b(Huf)o(fman,)g(D.)g(A.,)h(\252A)f(Method)f(for)g(the)h(Construction)d
(of)j(Minimum)g(Redundancy)f(Codes\272,)h(Proceedings)f(of)g(the)0
844 y(Institute)e(of)j(Radio)f(Engineers,)f(September)i(1952,)e(V)-6
b(olume)11 b(40,)h(Number)f(9,)g(pp.)k(1098-1)n(101.)0
931 y([2])f(Ziv)g(J.,)h(Lempel)g(A.,)g(\252A)g(Universal)e(Algorithm)f
(for)j(Sequential)e(Data)h(Compression\272,)h(IEEE)f(T)n(ransactions)f
(on)0 988 y(Information)d(Theory)m(,)i(V)-6 b(ol.)14
b(23,)e(No.)j(3,)c(pp.)k(337-343.)0 1075 y([3])9 b(Gailly)m(,)g(J.-L.,)
i(and)e(Adler)n(,)g(M.,)i(ZLIB)f(documentation)d(and)i(sources,)g
(available)g(in)g(ftp://ftp.uu.net/pu)o(b/archiv)o(ing)o(/)0
1131 y(zip/doc/)0 1218 y([4])24 b(Gailly)m(,)i(J.-L.,)i(and)c(Adler)n
(,)j(M.,)i(GZIP)24 b(documentation)e(and)i(sources,)j(available)c(as)h
(gzip-*.tar)f(in)h(ftp://)0 1275 y(prep.ai.mit.edu/pub/gnu/)0
1362 y([5])15 b(Schwartz,)h(E.)g(S.,)g(and)f(Kallick,)g(B.)h
(\252Generating)e(a)h(canonical)f(pre\256x)h(encoding.\272)25
b(Comm.)j(ACM,)15 b(7,3)g(\(Mar)n(.)0 1418 y(1964\),)c(pp.)k(166-169.)0
1505 y([6])c(Hirschber)o(g)f(and)g(Lelewer)n(,)i(\252Ef)o(\256cient)e
(decoding)g(of)g(pre\256x)h(codes,\272)g(Comm.)16 b(ACM,)c(33,4,)f
(April)f(1990,)g(pp.)15 b(449-)0 1561 y(459.)0 1738 y
Fh(6)60 b(Security)13 b(Considerations)0 1872 y Fj(Any)e(data)g
(compression)f(method)h(involves)e(the)i(reduction)f(of)h(redundancy)g
(in)f(the)h(data.)k(Consequently)m(,)10 b(any)h(corrup-)0
1928 y(tion)h(of)g(the)h(data)f(is)g(likely)f(to)i(have)f(severe)h(ef)o
(fects)g(and)g(be)f(dif)o(\256cult)g(to)g(correct.)20
b(Uncompressed)12 b(text,)h(on)f(the)h(other)0 1985 y(hand,)e(will)f
(probably)g(still)g(be)h(readable)g(despite)f(the)h(presence)h(of)f
(some)g(corrupted)g(bytes.)0 2072 y(It)g(is)f(recommended)i(that)e
(systems)g(using)f(this)h(data)h(format)g(provide)f(some)h(means)g(of)g
(validating)e(the)h(integrity)g(of)g(the)0 2128 y(compressed)h(data.)k
(See)d(reference)h([3],)e(for)h(example.)0 2305 y Fh(7)60
b(Sour)o(ce)14 b(code)0 2439 y Fj(Source)8 b(code)g(for)g(a)h(C)f
(language)f(implementation)g(of)h(a)g(\252de\257ate\272)h(compliant)e
(compressor)h(and)f(decompressor)h(is)g(avail-)0 2495
y(able)j(within)f(the)h(zlib)f(package)h(at)h(ftp://ftp.uu.net/pu)o
(b/archi)o(ving)o(/zip)o(/zlib)o(/.)0 2719 y(Deutsch)687
b(Informational)g([Page)11 b(14])p eop
%%Page: 15 15
15 14 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)0 195 y Fh(8)60 b(Acknowledgements)0 329 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 416 y(Phil)d(Katz)g(designed)f(the)h(de\257ate)
h(format.)15 b(Jean-Loup)7 b(Gailly)g(and)h(Mark)h(Adler)f(wrote)h(the)
f(related)g(software)g(described)0 472 y(in)j(this)f(speci\256cation.)k
(Glenn)c(Randers-Pehrson)h(converted)g(this)f(document)h(to)f(RFC)j
(and)e(HTML)g(format.)0 649 y Fh(9)60 b(Author)q(')n(s)15
b(Addr)o(ess)0 783 y Fj(L.)c(Peter)h(Deutsch)114 870
y Fc(Aladdin)29 b(Enterprises)114 926 y(203)f(Santa)g(Margarita)i(Ave.)
114 983 y(Menlo)e(Park,)h(CA)f(94025)114 1096 y(Phone:)h(\(415\))f
(322-0103)i(\(AM)e(only\))114 1152 y(FAX:)83 b(\(415\))28
b(322-1734)114 1208 y(EMail:)h(<ghost@aladdin.)q(com>)0
1295 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
1382 y Fc(Jean-Loup)29 b(Gailly)g(<[email protected])q(i.mi)q(t.ed)q(u>)i
(and)114 1439 y(Mark)d(Adler)h(<madler@alumni.)q(cal)q(tech)q(.edu)q(>)
0 1526 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:)114 1613 y Fc(L.)27 b(Peter)i(Deutsch)g
(<ghost@aladd)q(in.c)q(om>)i(and)114 1669 y(Glenn)d(Randers-Pehr)q(son)
j(<randeg@alumni.)q(rpi)q(.edu)q(>)0 2719 y Fj(Deutsch)687
b(Informational)g([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.