# gzip-compatible compression filter. implement Filter; include "sys.m"; sys: Sys; include "filter.m"; GZMAGIC1: con byte 16r1f;GZMAGIC2: con byte 16r8b; GZDEFLATE: con byte 8; GZFTEXT: con byte 1 << 0; # file is textGZFHCRC: con byte 1 << 1; # crc of header includedGZFEXTRA: con byte 1 << 2; # extra header includedGZFNAME: con byte 1 << 3; # name of file includedGZFCOMMENT: con byte 1 << 4; # header comment includedGZFMASK: con (byte 1 << 5) - byte 1; # mask of specified bits GZXFAST: con byte 2; # used fast algorithm little compressionGZXBEST: con byte 4; # used maximum compression algorithm GZOSFAT: con byte 0; # FAT file systemGZOSAMIGA: con byte 1; # AmigaGZOSVMS: con byte 2; # VMS or OpenVMSGZOSUNIX: con byte 3; # UnixGZOSVMCMS: con byte 4; # VM/CMSGZOSATARI: con byte 5; # Atari TOSGZOSHPFS: con byte 6; # HPFS file systemGZOSMAC: con byte 7; # MacintoshGZOSZSYS: con byte 8; # Z-SystemGZOSCPM: con byte 9; # CP/MGZOSTOPS20: con byte 10; # TOPS-20GZOSNTFS: con byte 11; # NTFS file systemGZOSQDOS: con byte 12; # QDOSGZOSACORN: con byte 13; # Acorn RISCOSGZOSUNK: con byte 255; GZCRCPOLY: con int 16redb88320;GZOSINFERNO: con GZOSUNIX; Hnone, Hgzip, Hzlib: con iota; # LZstate.headersLZstate: adt{ hist: array of byte; # [HistSize]; epos: int; # end of history buffer pos: int; # current location in history buffer eof: int; hash: array of int; # [Nhash] hash chains nexts: array of int; # [MaxOff] me: int; # pos in hash chains dot: int; # dawn of time in history prevlen: int; # lazy matching state prevoff: int; maxchars: int; # compressor tuning maxdefer: int; level: int; crctab: array of int; # for gzip trailer crc: int; tot: int; sum: big; # for zlib trailer headers: int; # which header to print, if any outbuf: array of byte; # current output buffer; out: int; # current position in the output buffer bits: int; # bit shift register nbits: int; verbose: int; debug: int; lzb: ref LZblock; slop: array of byte; dlitlentab: array of Huff; # [Nlitlen] dofftab: array of Huff; # [Noff]; hlitlentab: array of Huff; # [Nlitlen]; dyncode: ref Dyncode; hdyncode: ref Dyncode; c: chan of ref Rq; rc: chan of int;}; ## lempel-ziv compressed block#LZblock: adt{ litlen: array of byte; # [MaxUncBlock+1]; off: array of int; # [MaxUncBlock+1]; litlencount: array of int; # [Nlitlen]; offcount: array of int; # [Noff]; entries: int; # entries in litlen & off tables bytes: int; # consumed from the input excost: int; # cost of encoding extra len & off bits}; ## encoding of dynamic huffman trees#Dyncode: adt{ nlit: int; noff: int; nclen: int; ncode: int; codetab: array of Huff; # [Nclen]; codes: array of byte; # [Nlitlen+Noff]; codeaux: array of byte; # [Nlitlen+Noff];}; ## huffman code table#Huff: adt{ bits: int; # length of the code encode: int; # the code}; DeflateBlock: con 64*1024-258-1;DeflateOut: con 258+10; DeflateUnc: con 0; # uncompressed blockDeflateFix: con 1; # fixed huffman codesDeflateDyn: con 2; # dynamic huffman codes DeflateEob: con 256; # end of block code in lit/len book LenStart: con 257; # start of length codes in litlenNlitlen: con 288; # number of litlen codesNoff: con 30; # number of offset codesNclen: con 19; # number of codelen codes MaxLeaf: con Nlitlen;MaxHuffBits: con 15; # max bits in a huffman codeChainMem: con 2 * MaxHuffBits * (MaxHuffBits + 1); MaxUncBlock: con 64*1024-1; # maximum size of uncompressed block MaxOff: con 32*1024;MinMatch: con 3; # shortest match possibleMaxMatch: con 258; # longest match possibleMinMatchMaxOff: con 4096; # max profitable offset for small match; # assumes 8 bits for len; 5+10 for offsetHistSlop: con 4096; # slop for fewer calls to lzcompHistSize: con MaxOff + 2*HistSlop; Hshift: con 4; # nice compromise between space & timeNhash: con 1<<(Hshift*MinMatch);Hmask: con Nhash-1; MaxOffCode: con 256; # biggest offset looked up in direct table EstLitBits: con 8;EstLenBits: con 4;EstOffBits: con 5; # conversion from len to code wordlencode := array[MaxMatch] of int; ## conversion from off to code word# off <= MaxOffCode ? offcode[off] : bigoffcode[(off-1) >> 7]#offcode := array[MaxOffCode + 1] of int;bigoffcode := array[256] of int; # litlen code words LenStart-285 extra bitslitlenbase := array[Nlitlen-LenStart] of int;litlenextra := array[Nlitlen-LenStart] of{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 0, 0}; # offset code word extra bitsoffbase := array[Noff] of int;offextra := array[] of{ 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 0, 0,}; # order code lengthsclenorder := array[Nclen] of{ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; # static huffman tableslitlentab : array of Huff;offtab : array of Huff;hofftab : array of Huff; # bit reversal for brain dead endian swap in huffman codesrevtab: array of byte; init(){ sys = load Sys Sys->PATH; bitcount := array[MaxHuffBits] of int; i, j, ci, n: int; # byte reverse table revtab = array[256] of byte; for(i=0; i<256; i++){ revtab[i] = byte 0; for(j=0; j<8; j++) if(i & (1<<j)) revtab[i] |= byte 16r80 >> j; } litlentab = array[Nlitlen] of Huff; offtab = array[Noff] of Huff; hofftab = array[Noff] of { * => Huff(0, 0) }; # static Litlen bit lengths for(i=0; i<144; i++) litlentab[i].bits = 8; for(i=144; i<256; i++) litlentab[i].bits = 9; for(i=256; i<280; i++) litlentab[i].bits = 7; for(i=280; i<Nlitlen; i++) litlentab[i].bits = 8; for(i = 0; i < 10; i++) bitcount[i] = 0; bitcount[8] += 144 - 0; bitcount[9] += 256 - 144; bitcount[7] += 280 - 256; bitcount[8] += Nlitlen - 280; hufftabinit(litlentab, Nlitlen, bitcount, 9); # static offset bit lengths for(i = 0; i < Noff; i++) offtab[i].bits = 5; for(i = 0; i < 5; i++) bitcount[i] = 0; bitcount[5] = Noff; hufftabinit(offtab, Noff, bitcount, 5); bitcount[0] = 0; bitcount[1] = 0; mkprecode(hofftab, bitcount, 2, MaxHuffBits); # conversion tables for lens & offs to codes ci = 0; for(i = LenStart; i < 286; i++){ n = ci + (1 << litlenextra[i - LenStart]); litlenbase[i - LenStart] = ci; for(; ci < n; ci++) lencode[ci] = i; } # patch up special case for len MaxMatch lencode[MaxMatch-MinMatch] = 285; litlenbase[285-LenStart] = MaxMatch-MinMatch; ci = 1; for(i = 0; i < 16; i++){ n = ci + (1 << offextra[i]); offbase[i] = ci; for(; ci < n; ci++) offcode[ci] = i; } ci = (LenStart - 1) >> 7; for(; i < 30; i++){ n = ci + (1 << (offextra[i] - 7)); offbase[i] = (ci << 7) + 1; for(; ci < n; ci++) bigoffcode[ci] = i; }} start(param: string): chan of ref Rq{ # param contains flags: # [0-9] - compression level # h gzip header/trailer # z zlib header/trailer # v verbose # d debug lz := ref LZstate; lz.level = 6; lz.verbose = lz.debug = 0; lz.headers = Hnone; lz.crc = lz.tot = 0; lz.sum = big 1; # XXX could also put filename and modification time in param for (i := 0; i < len param; i++) { case param[i] { '0' to '9' => lz.level = param[i] - '0'; 'v' => lz.verbose = 1; 'h' => lz.headers = Hgzip; 'z' => lz.headers = Hzlib; 'd' => lz.debug = 1; } } lz.hist = array[HistSize] of byte; lz.hash = array[Nhash] of int; lz.nexts = array[MaxOff] of int; lz.slop = array[2*MaxMatch] of byte; lz.dlitlentab = array[Nlitlen] of Huff; lz.dofftab = array[Noff] of Huff; lz.hlitlentab = array[Nlitlen] of Huff; lz.lzb = ref LZblock; lzb := lz.lzb; lzb.litlen = array[MaxUncBlock+1] of byte; lzb.off = array[MaxUncBlock+1] of int; lzb.litlencount = array[Nlitlen] of int; lzb.offcount = array[Noff] of int; lz.dyncode = ref Dyncode; lz.dyncode.codetab =array[Nclen] of Huff; lz.dyncode.codes =array[Nlitlen+Noff] of byte; lz.dyncode.codeaux = array[Nlitlen+Noff] of byte; lz.hdyncode = ref Dyncode; lz.hdyncode.codetab =array[Nclen] of Huff; lz.hdyncode.codes =array[Nlitlen+Noff] of byte; lz.hdyncode.codeaux = array[Nlitlen+Noff] of byte; for(i = 0; i < MaxOff; i++) lz.nexts[i] = 0; for(i = 0; i < Nhash; i++) lz.hash[i] = 0; lz.pos = 0; lz.epos = 0; lz.prevlen = MinMatch - 1; lz.prevoff = 0; lz.eof = 0; lz.me = 4 * MaxOff; lz.dot = lz.me; lz.bits = 0; lz.nbits = 0; if(lz.level < 5) { lz.maxchars = 1; lz.maxdefer = 0; } else if(lz.level == 9) { lz.maxchars = 4000; lz.maxdefer = MaxMatch; } else { lz.maxchars = 200; lz.maxdefer = MaxMatch / 4; } if (lz.headers == Hgzip) lz.crctab = mkcrctab(GZCRCPOLY); lz.c = chan of ref Rq; lz.rc = chan of int; spawn deflate(lz); return lz.c;} # return (eof, nbytes)fillbuf(lz: ref LZstate, buf: array of byte): (int, int){ n := 0; while (n < len buf) { lz.c <-= ref Rq.Fill(buf[n:], lz.rc); nr := <-lz.rc; if (nr == -1) exit; if (nr == 0) return (1, n); n += nr; } return (0, n);} deflate(lz: ref LZstate){ lz.c <-= ref Rq.Start(sys->pctl(0, nil)); header(lz); buf := array[DeflateBlock] of byte; out := array[DeflateBlock + DeflateOut] of byte; eof := 0; for (;;) { nslop := lz.epos - lz.pos; nbuf := 0; if (!eof) { (eof, nbuf) = fillbuf(lz, buf); inblock(lz, buf[0:nbuf]); } if(eof && nbuf == 0 && nslop == 0) { if(lz.nbits) { out[0] = byte lz.bits; lz.nbits = 0; lz.c <-= ref Rq.Result(out[0:1], lz.rc); if (<-lz.rc == -1) exit; continue; } footer(lz); lz.c <-= ref Rq.Finished(nil); exit; } lz.outbuf = out; if(nslop > 2*MaxMatch) { lz.c <-= ref Rq.Error(sys->sprint("slop too large: %d", nslop)); exit; } lz.slop[0:] = lz.hist[lz.pos:lz.epos]; # memmove(slop, lz.pos, nslop); lzb := lz.lzb; for(i := 0; i < Nlitlen; i++) lzb.litlencount[i] = 0; for(i = 0; i < Noff; i++) lzb.offcount[i] = 0; lzb.litlencount[DeflateEob]++; lzb.bytes = 0; lzb.entries = 0; lzb.excost = 0; lz.eof = 0; n := 0; while(n < nbuf || eof && !lz.eof){ if(!lz.eof) { if(lz.pos >= MaxOff + HistSlop) { lz.pos -= MaxOff + HistSlop; lz.epos -= MaxOff + HistSlop; lz.hist[:] = lz.hist[MaxOff + HistSlop: MaxOff + HistSlop + lz.epos]; } m := HistSlop - (lz.epos - lz.pos); if(lz.epos + m > HistSize) { lz.c <-= ref Rq.Error("read too long"); exit; } if(m >= nbuf - n) { m = nbuf - n; lz.eof = eof; } lz.hist[lz.epos:] = buf[n:n+m]; n += m; lz.epos += m; } lzcomp(lz, lzb, lz.epos - lz.pos); } lz.outbuf = out; lz.out = 0; nunc := lzb.bytes; if(nunc < nslop) nslop = nunc; mkprecode(lz.dlitlentab, lzb.litlencount, Nlitlen, MaxHuffBits); mkprecode(lz.dofftab, lzb.offcount, Noff, MaxHuffBits); ndyn := huffcodes(lz.dyncode, lz.dlitlentab, lz.dofftab) + bitcost(lz.dlitlentab, lzb.litlencount, Nlitlen) + bitcost(lz.dofftab, lzb.offcount, Noff) + lzb.excost; litcount := array[Nlitlen] of int; for(i = 0; i < Nlitlen; i++) litcount[i] = 0; for(i = 0; i < nslop; i++) litcount[int lz.slop[i]]++; for(i = 0; i < nunc-nslop; i++) litcount[int buf[i]]++; litcount[DeflateEob]++; mkprecode(lz.hlitlentab, litcount, Nlitlen, MaxHuffBits); nhuff := huffcodes(lz.hdyncode, lz.hlitlentab, hofftab) + bitcost(lz.hlitlentab, litcount, Nlitlen); nfix := bitcost(litlentab, lzb.litlencount, Nlitlen) + bitcost(offtab, lzb.offcount, Noff) + lzb.excost; lzput(lz, lz.eof && lz.pos == lz.epos, 1); if(lz.verbose) { lz.c <-= ref Rq.Info(sys->sprint("block: %d bytes %d entries %d extra bits", nunc, lzb.entries, lzb.excost)); lz.c <-= ref Rq.Info(sys->sprint("\tuncompressed %d fixed %d dynamic %d huffman %d",Lines 1–500 of 1453. Load more
# gzip-compatible compression filter. implement Filter; include "sys.m"; sys: Sys; include "filter.m"; GZMAGIC1: con byte 16r1f; GZMAGIC2: con byte 16r8b; GZDEFLATE: con byte 8; GZFTEXT: con byte 1 << 0; # file is text GZFHCRC: con byte 1 << 1; # crc of header included GZFEXTRA: con byte 1 << 2; # extra header included GZFNAME: con byte 1 << 3; # name of file included GZFCOMMENT: con byte 1 << 4; # header comment included GZFMASK: con (byte 1 << 5) - byte 1; # mask of specified bits GZXFAST: con byte 2; # used fast algorithm little compression GZXBEST: con byte 4; # used maximum compression algorithm GZOSFAT: con byte 0; # FAT file system GZOSAMIGA: con byte 1; # Amiga GZOSVMS: con byte 2; # VMS or OpenVMS GZOSUNIX: con byte 3; # Unix GZOSVMCMS: con byte 4; # VM/CMS GZOSATARI: con byte 5; # Atari TOS GZOSHPFS: con byte 6; # HPFS file system GZOSMAC: con byte 7; # Macintosh GZOSZSYS: con byte 8; # Z-System GZOSCPM: con byte 9; # CP/M GZOSTOPS20: con byte 10; # TOPS-20 GZOSNTFS: con byte 11; # NTFS file system GZOSQDOS: con byte 12; # QDOS GZOSACORN: con byte 13; # Acorn RISCOS GZOSUNK: con byte 255; GZCRCPOLY: con int 16redb88320; GZOSINFERNO: con GZOSUNIX; Hnone, Hgzip, Hzlib: con iota; # LZstate.headers LZstate: adt { hist: array of byte; # [HistSize]; epos: int; # end of history buffer pos: int; # current location in history buffer eof: int; hash: array of int; # [Nhash] hash chains nexts: array of int; # [MaxOff] me: int; # pos in hash chains dot: int; # dawn of time in history prevlen: int; # lazy matching state prevoff: int; maxchars: int; # compressor tuning maxdefer: int; level: int; crctab: array of int; # for gzip trailer crc: int; tot: int; sum: big; # for zlib trailer headers: int; # which header to print, if any outbuf: array of byte; # current output buffer; out: int; # current position in the output buffer bits: int; # bit shift register nbits: int; verbose: int; debug: int; lzb: ref LZblock; slop: array of byte; dlitlentab: array of Huff; # [Nlitlen] dofftab: array of Huff; # [Noff]; hlitlentab: array of Huff; # [Nlitlen]; dyncode: ref Dyncode; hdyncode: ref Dyncode; c: chan of ref Rq; rc: chan of int; }; # # lempel-ziv compressed block # LZblock: adt { litlen: array of byte; # [MaxUncBlock+1]; off: array of int; # [MaxUncBlock+1]; litlencount: array of int; # [Nlitlen]; offcount: array of int; # [Noff]; entries: int; # entries in litlen & off tables bytes: int; # consumed from the input excost: int; # cost of encoding extra len & off bits }; # # encoding of dynamic huffman trees # Dyncode: adt { nlit: int; noff: int; nclen: int; ncode: int; codetab: array of Huff; # [Nclen]; codes: array of byte; # [Nlitlen+Noff]; codeaux: array of byte; # [Nlitlen+Noff]; }; # # huffman code table # Huff: adt { bits: int; # length of the code encode: int; # the code }; DeflateBlock: con 64*1024-258-1; DeflateOut: con 258+10; DeflateUnc: con 0; # uncompressed block DeflateFix: con 1; # fixed huffman codes DeflateDyn: con 2; # dynamic huffman codes DeflateEob: con 256; # end of block code in lit/len book LenStart: con 257; # start of length codes in litlen Nlitlen: con 288; # number of litlen codes Noff: con 30; # number of offset codes Nclen: con 19; # number of codelen codes MaxLeaf: con Nlitlen; MaxHuffBits: con 15; # max bits in a huffman code ChainMem: con 2 * MaxHuffBits * (MaxHuffBits + 1); MaxUncBlock: con 64*1024-1; # maximum size of uncompressed block MaxOff: con 32*1024; MinMatch: con 3; # shortest match possible MaxMatch: con 258; # longest match possible MinMatchMaxOff: con 4096; # max profitable offset for small match; # assumes 8 bits for len; 5+10 for offset HistSlop: con 4096; # slop for fewer calls to lzcomp HistSize: con MaxOff + 2*HistSlop; Hshift: con 4; # nice compromise between space & time Nhash: con 1<<(Hshift*MinMatch); Hmask: con Nhash-1; MaxOffCode: con 256; # biggest offset looked up in direct table EstLitBits: con 8; EstLenBits: con 4; EstOffBits: con 5; # conversion from len to code word lencode := array[MaxMatch] of int; # # conversion from off to code word # off <= MaxOffCode ? offcode[off] : bigoffcode[(off-1) >> 7] # offcode := array[MaxOffCode + 1] of int; bigoffcode := array[256] of int; # litlen code words LenStart-285 extra bits litlenbase := array[Nlitlen-LenStart] of int; litlenextra := array[Nlitlen-LenStart] of { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 0, 0 }; # offset code word extra bits offbase := array[Noff] of int; offextra := array[] of { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 0, 0, }; # order code lengths clenorder := array[Nclen] of { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; # static huffman tables litlentab : array of Huff; offtab : array of Huff; hofftab : array of Huff; # bit reversal for brain dead endian swap in huffman codes revtab: array of byte; init() { sys = load Sys Sys->PATH; bitcount := array[MaxHuffBits] of int; i, j, ci, n: int; # byte reverse table revtab = array[256] of byte; for(i=0; i<256; i++){ revtab[i] = byte 0; for(j=0; j<8; j++) if(i & (1<<j)) revtab[i] |= byte 16r80 >> j; } litlentab = array[Nlitlen] of Huff; offtab = array[Noff] of Huff; hofftab = array[Noff] of { * => Huff(0, 0) }; # static Litlen bit lengths for(i=0; i<144; i++) litlentab[i].bits = 8; for(i=144; i<256; i++) litlentab[i].bits = 9; for(i=256; i<280; i++) litlentab[i].bits = 7; for(i=280; i<Nlitlen; i++) litlentab[i].bits = 8; for(i = 0; i < 10; i++) bitcount[i] = 0; bitcount[8] += 144 - 0; bitcount[9] += 256 - 144; bitcount[7] += 280 - 256; bitcount[8] += Nlitlen - 280; hufftabinit(litlentab, Nlitlen, bitcount, 9); # static offset bit lengths for(i = 0; i < Noff; i++) offtab[i].bits = 5; for(i = 0; i < 5; i++) bitcount[i] = 0; bitcount[5] = Noff; hufftabinit(offtab, Noff, bitcount, 5); bitcount[0] = 0; bitcount[1] = 0; mkprecode(hofftab, bitcount, 2, MaxHuffBits); # conversion tables for lens & offs to codes ci = 0; for(i = LenStart; i < 286; i++){ n = ci + (1 << litlenextra[i - LenStart]); litlenbase[i - LenStart] = ci; for(; ci < n; ci++) lencode[ci] = i; } # patch up special case for len MaxMatch lencode[MaxMatch-MinMatch] = 285; litlenbase[285-LenStart] = MaxMatch-MinMatch; ci = 1; for(i = 0; i < 16; i++){ n = ci + (1 << offextra[i]); offbase[i] = ci; for(; ci < n; ci++) offcode[ci] = i; } ci = (LenStart - 1) >> 7; for(; i < 30; i++){ n = ci + (1 << (offextra[i] - 7)); offbase[i] = (ci << 7) + 1; for(; ci < n; ci++) bigoffcode[ci] = i; } } start(param: string): chan of ref Rq { # param contains flags: # [0-9] - compression level # h gzip header/trailer # z zlib header/trailer # v verbose # d debug lz := ref LZstate; lz.level = 6; lz.verbose = lz.debug = 0; lz.headers = Hnone; lz.crc = lz.tot = 0; lz.sum = big 1; # XXX could also put filename and modification time in param for (i := 0; i < len param; i++) { case param[i] { '0' to '9' => lz.level = param[i] - '0'; 'v' => lz.verbose = 1; 'h' => lz.headers = Hgzip; 'z' => lz.headers = Hzlib; 'd' => lz.debug = 1; } } lz.hist = array[HistSize] of byte; lz.hash = array[Nhash] of int; lz.nexts = array[MaxOff] of int; lz.slop = array[2*MaxMatch] of byte; lz.dlitlentab = array[Nlitlen] of Huff; lz.dofftab = array[Noff] of Huff; lz.hlitlentab = array[Nlitlen] of Huff; lz.lzb = ref LZblock; lzb := lz.lzb; lzb.litlen = array[MaxUncBlock+1] of byte; lzb.off = array[MaxUncBlock+1] of int; lzb.litlencount = array[Nlitlen] of int; lzb.offcount = array[Noff] of int; lz.dyncode = ref Dyncode; lz.dyncode.codetab =array[Nclen] of Huff; lz.dyncode.codes =array[Nlitlen+Noff] of byte; lz.dyncode.codeaux = array[Nlitlen+Noff] of byte; lz.hdyncode = ref Dyncode; lz.hdyncode.codetab =array[Nclen] of Huff; lz.hdyncode.codes =array[Nlitlen+Noff] of byte; lz.hdyncode.codeaux = array[Nlitlen+Noff] of byte; for(i = 0; i < MaxOff; i++) lz.nexts[i] = 0; for(i = 0; i < Nhash; i++) lz.hash[i] = 0; lz.pos = 0; lz.epos = 0; lz.prevlen = MinMatch - 1; lz.prevoff = 0; lz.eof = 0; lz.me = 4 * MaxOff; lz.dot = lz.me; lz.bits = 0; lz.nbits = 0; if(lz.level < 5) { lz.maxchars = 1; lz.maxdefer = 0; } else if(lz.level == 9) { lz.maxchars = 4000; lz.maxdefer = MaxMatch; } else { lz.maxchars = 200; lz.maxdefer = MaxMatch / 4; } if (lz.headers == Hgzip) lz.crctab = mkcrctab(GZCRCPOLY); lz.c = chan of ref Rq; lz.rc = chan of int; spawn deflate(lz); return lz.c; } # return (eof, nbytes) fillbuf(lz: ref LZstate, buf: array of byte): (int, int) { n := 0; while (n < len buf) { lz.c <-= ref Rq.Fill(buf[n:], lz.rc); nr := <-lz.rc; if (nr == -1) exit; if (nr == 0) return (1, n); n += nr; } return (0, n); } deflate(lz: ref LZstate) { lz.c <-= ref Rq.Start(sys->pctl(0, nil)); header(lz); buf := array[DeflateBlock] of byte; out := array[DeflateBlock + DeflateOut] of byte; eof := 0; for (;;) { nslop := lz.epos - lz.pos; nbuf := 0; if (!eof) { (eof, nbuf) = fillbuf(lz, buf); inblock(lz, buf[0:nbuf]); } if(eof && nbuf == 0 && nslop == 0) { if(lz.nbits) { out[0] = byte lz.bits; lz.nbits = 0; lz.c <-= ref Rq.Result(out[0:1], lz.rc); if (<-lz.rc == -1) exit; continue; } footer(lz); lz.c <-= ref Rq.Finished(nil); exit; } lz.outbuf = out; if(nslop > 2*MaxMatch) { lz.c <-= ref Rq.Error(sys->sprint("slop too large: %d", nslop)); exit; } lz.slop[0:] = lz.hist[lz.pos:lz.epos]; # memmove(slop, lz.pos, nslop); lzb := lz.lzb; for(i := 0; i < Nlitlen; i++) lzb.litlencount[i] = 0; for(i = 0; i < Noff; i++) lzb.offcount[i] = 0; lzb.litlencount[DeflateEob]++; lzb.bytes = 0; lzb.entries = 0; lzb.excost = 0; lz.eof = 0; n := 0; while(n < nbuf || eof && !lz.eof){ if(!lz.eof) { if(lz.pos >= MaxOff + HistSlop) { lz.pos -= MaxOff + HistSlop; lz.epos -= MaxOff + HistSlop; lz.hist[:] = lz.hist[MaxOff + HistSlop: MaxOff + HistSlop + lz.epos]; } m := HistSlop - (lz.epos - lz.pos); if(lz.epos + m > HistSize) { lz.c <-= ref Rq.Error("read too long"); exit; } if(m >= nbuf - n) { m = nbuf - n; lz.eof = eof; } lz.hist[lz.epos:] = buf[n:n+m]; n += m; lz.epos += m; } lzcomp(lz, lzb, lz.epos - lz.pos); } lz.outbuf = out; lz.out = 0; nunc := lzb.bytes; if(nunc < nslop) nslop = nunc; mkprecode(lz.dlitlentab, lzb.litlencount, Nlitlen, MaxHuffBits); mkprecode(lz.dofftab, lzb.offcount, Noff, MaxHuffBits); ndyn := huffcodes(lz.dyncode, lz.dlitlentab, lz.dofftab) + bitcost(lz.dlitlentab, lzb.litlencount, Nlitlen) + bitcost(lz.dofftab, lzb.offcount, Noff) + lzb.excost; litcount := array[Nlitlen] of int; for(i = 0; i < Nlitlen; i++) litcount[i] = 0; for(i = 0; i < nslop; i++) litcount[int lz.slop[i]]++; for(i = 0; i < nunc-nslop; i++) litcount[int buf[i]]++; litcount[DeflateEob]++; mkprecode(lz.hlitlentab, litcount, Nlitlen, MaxHuffBits); nhuff := huffcodes(lz.hdyncode, lz.hlitlentab, hofftab) + bitcost(lz.hlitlentab, litcount, Nlitlen); nfix := bitcost(litlentab, lzb.litlencount, Nlitlen) + bitcost(offtab, lzb.offcount, Noff) + lzb.excost; lzput(lz, lz.eof && lz.pos == lz.epos, 1); if(lz.verbose) { lz.c <-= ref Rq.Info(sys->sprint("block: %d bytes %d entries %d extra bits", nunc, lzb.entries, lzb.excost)); lz.c <-= ref Rq.Info(sys->sprint("\tuncompressed %d fixed %d dynamic %d huffman %d",