# gzip-compatible decompression 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 1 << 0;		# file is textGZFHCRC:	con 1 << 1;		# crc of header includedGZFEXTRA:	con 1 << 2;		# extra header includedGZFNAME:	con 1 << 3;		# name of file includedGZFCOMMENT:	con 1 << 4;		# header comment includedGZFMASK:	con (1 << 5) - 1;	# mask of specified bits GZXBEST:	con byte 2;		# used maximum compression algorithmGZXFAST:	con byte 4;		# used fast algorithm little compression 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; # huffman code tableHuff: adt{	bits:		int;		# length of the code	encode:		int;		# the code}; # huffman decode tableDeHuff: adt{	l1:		array of L1;	# the table	nb1:		int;		# no. of bits in first level	nb2:		int;		# no. of bits in second level}; # first level of decode tableL1: adt{	bits:		int;		# length of the code	decode:		int;		# the symbol	l2:		array of L2;}; # second levelL2: adt{	bits:		int;		# length of the code	decode:		int;		# the symbol}; DeflateUnc:	con 0;			# uncompressed blockDeflateFix:	con 1;			# fixed huffman codesDeflateDyn:	con 2;			# dynamic huffman codesDeflateErr:	con 3;			# reserved BTYPE (error) DeflateEob:	con 256;		# end of block code in lit/len book LenStart:	con 257;		# start of length codes in litlenLenEnd:		con 285;		# greatest valid length codeNlitlen:	con 288;		# number of litlen codesNoff:		con 30;			# number of offset codesNclen:		con 19;			# number of codelen codes MaxHuffBits:	con 15;			# max bits in a huffman codeRunlenBits:	con 7;			# max bits in a run-length huffman codeMaxOff:		con 32*1024;		# max lempel-ziv distance Blocksize: con 32 * 1024; # tables from RFC 1951, section 3.2.5litlenbase := array[Noff] of{	3, 4, 5, 6, 7, 8, 9, 10, 11, 13,	15, 17, 19, 23, 27, 31, 35, 43, 51, 59,	67, 83, 99, 115, 131, 163, 195, 227, 258}; litlenextra := array[Noff] 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}; offbase := array[Noff] of{	1, 2, 3, 4, 5, 7, 9, 13, 17, 25,	33, 49, 65, 97, 129, 193, 257, 385, 513, 769,	1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577}; offextra := array[Noff] 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}; # order of run-length codesclenorder := array[Nclen] of{	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; # fixed huffman tableslitlentab: array of Huff;offtab: array of Huff; # their decoding table counterpartslitlendec: ref DeHuff;offdec: ref DeHuff; revtab: array of byte;	# bit reversal for endian swap of huffman codesmask: array of int;		# for masking low-order n bits of an int State: adt {	ibuf, obuf: array of byte;	c: chan of ref Rq;	rc: chan of int;	in: int;		# next byte to consume from input buffer	ein: int;		# valid bytes in input buffer	out: int;		# valid bytes in output buffer	hist: array of byte;	# history buffer for lempel-ziv backward references	usehist: int;		# == 1 if 'hist' is valid	crctab: array of int;	crc, tot: int;		reg: int;		# 24-bit shift register	nbits: int;		# number of valid bits in reg	svreg: int;		# save reg for efficient ungets	svn: int;		# number of bits gotten in last call to getn()	# reg bits are consumed from right to left	# so low-order byte of reg came first in the input stream	headers: int;};  init(){	sys = load Sys Sys->PATH; 	# 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;		}	} 	# bit-masking table	mask = array[MaxHuffBits+1] of int;	for(i = 0; i <= MaxHuffBits; i++)		mask[i] = (1 << i) - 1; 	litlentab = array[Nlitlen] of Huff; 	# 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; 	bitcount := array[MaxHuffBits+1] of { * => 0 };	bitcount[8] += 144 - 0;	bitcount[9] += 256 - 144;	bitcount[7] += 280 - 256;	bitcount[8] += Nlitlen - 280; 	hufftabinit(litlentab, Nlitlen, bitcount, 9);	litlendec = decodeinit(litlentab, Nlitlen, 9, 0); 	offtab = array[Noff] of Huff; 	# 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);	offdec = decodeinit(offtab, Noff, 5, 0);} start(params: string): chan of ref Rq{	s := ref State;	s.c = chan of ref Rq;	s.rc = chan of int;	s.ibuf = array[Blocksize] of byte;	s.obuf = array[Blocksize] of byte;	s.in = 0;	s.ein = 0;	s.out = 0;	s.usehist = 0;	s.reg = 0;	s.nbits = 0;	s.crc = 0;	s.tot = 0;	s.hist = array[Blocksize] of byte;	s.headers = (params != nil && params[0] == 'h');	if (s.headers)		s.crctab = mkcrctab(GZCRCPOLY);	spawn inflate(s);	return s.c;} inflate(s: ref State){	s.c <-= ref Rq.Start(sys->pctl(0, nil));	if (s.headers)		header(s); 	for(;;) {		bfinal := getn(s, 1, 0);		btype := getn(s, 2, 0);		case(btype) {		DeflateUnc =>			flushbits(s);			unclen := getb(s);			unclen |= getb(s) << 8;			nlen := getb(s);			nlen |= getb(s) << 8;			if(unclen != (~nlen & 16rFFFF))				fatal(s, "corrupted data");			for(; unclen > 0; unclen--) {				# inline putb(s, getb(s));				b := byte getb(s);				if(s.out >= MaxOff)					flushout(s);				s.obuf[s.out++] = b;			}		DeflateFix =>			decodeblock(s, litlendec, offdec);		DeflateDyn =>			dynhuff(s);		DeflateErr =>			fatal(s, "bad block type");		}		if(bfinal) {			if(s.out) {				if (s.headers)					outblock(s);				s.c <- = ref Rq.Result(s.obuf[0:s.out], s.rc);				flag := <- s.rc;				if (flag == -1)					exit;			}			flushbits(s);			if (s.headers)				footer(s);			s.c <-= ref Rq.Finished(s.ibuf[s.in - s.nbits/8:s.ein]);			exit;		}	}} header(s: ref State){	if(byte getb(s) != GZMAGIC1 || byte getb(s) != GZMAGIC2)		fatal(s, "not a gzip file"); 	if(byte getb(s) != GZDEFLATE)		fatal(s, "not compressed with deflate"); 	flags := getb(s);	if(flags & ~GZFMASK)		fatal(s, "reserved flag bits set"); 	# read modification time (ignored)	mtime := getb(s);	mtime |= (getb(s) << 8);	mtime |= (getb(s) << 16);	mtime |= (getb(s) << 24);	s.c <-= ref Rq.Info("mtime " + string mtime);	getb(s);	# xfl	getb(s);	# os 	# skip optional "extra field"	if(flags & GZFEXTRA) {		skip := getb(s);		skip |= getb(s) << 8;		while (skip-- > 0)			getb(s);	} 	# read optional filename (ignored)	file: string;	if(flags & GZFNAME){		n := 0;		while(c := getb(s))			file[n++] = c;		s.c <-= ref Rq.Info("file " + file);	} 	# skip optional comment	if(flags & GZFCOMMENT) {		while(getb(s))			;	} 	# skip optional CRC16 field	if(flags & GZFHCRC) {		getb(s);		getb(s);	}} footer(s: ref State){	fcrc := getword(s);	if(s.crc != fcrc)		fatal(s, sys->sprint("crc mismatch: computed %ux, expected %ux", s.crc, fcrc));	ftot := getword(s);	if(s.tot != ftot)		fatal(s, sys->sprint("byte count mismatch: computed %d, expected %d", s.tot, ftot));} getword(s: ref State): int{	n := 0;	for(i := 0; i < 4; i++)		n |= getb(s) << (8 * i);	return n;} ## uncompress a block using given huffman decoding tables#decodeblock(s: ref State, litlendec, offdec: ref DeHuff){	b: byte; 	for(;;) {		sym := decodesym(s, litlendec);		if(sym < DeflateEob) {		# literal byte			# inline putb(s, byte sym);			b = byte sym;			if(s.out >= MaxOff)				flushout(s);			s.obuf[s.out++] = b;		} else if(sym == DeflateEob) {	# End-of-block			break;		} else {			# lempel-ziv <length, distance>			if(sym > LenEnd)				fatal(s, "symbol too long");			xbits := litlenextra[sym - LenStart];			xtra := 0;			if(xbits)				xtra = getn(s, xbits, 0);			length := litlenbase[sym - LenStart] + xtra; 			sym = decodesym(s, offdec);			if(sym >= Noff)				fatal(s, "symbol too long");			xbits = offextra[sym];			if(xbits)				xtra = getn(s, xbits, 0);			else				xtra = 0;			dist := offbase[sym] + xtra;			if(dist > s.out && s.usehist == 0)				fatal(s, "corrupted data");			for(i := 0; i < length; i++) {				# inline putb(lzbyte(dist));				ix := s.out - dist;				if(dist <= s.out)					b = s.obuf[ix];				else					b = s.hist[MaxOff + ix];				if(s.out >= MaxOff)					flushout(s);				s.obuf[s.out++] = b;			}		}	}} ## decode next symbol in input stream using given huffman decoding table#decodesym(s: ref State, dec: ref DeHuff): int{	code, bits, n: int; 	l1 := dec.l1;	nb1 := dec.nb1;	nb2 := dec.nb2; 	code = getn(s, nb1, 1);	l2 := l1[code].l2;	if(l2 == nil) {		# first level table has answer		bits = l1[code].bits;		if(bits == 0)			fatal(s, "corrupt data");		if(nb1 > bits) {			# inline ungetn(nb1 - bits);			n = nb1 - bits;			s.reg = s.svreg >> (s.svn - n);			s.nbits += n;		}		return l1[code].decode;	}	# must advance to second-level table	code = getn(s, nb2, 1);	bits = l2[code].bits;	if(bits == 0)		fatal(s, "corrupt data");	if(nb1 + nb2 > bits) {		# inline ungetn(nb1 + nb2 - bits);		n = nb1 + nb2 - bits;		s.reg = s.svreg >> (s.svn - n);		s.nbits += n;	}	return l2[code].decode;} ## uncompress a block that was encoded with dynamic huffman codes# RFC 1951, section 3.2.7#dynhuff(s: ref State){	hlit := getn(s, 5, 0) + 257;	hdist := getn(s, 5, 0) + 1;	hclen := getn(s, 4, 0) + 4;	if(hlit > Nlitlen || hlit < 257 || hdist > Noff)		fatal(s, "corrupt data"); 	runlentab := array[Nclen] of { * => Huff(0, 0) };	count := array[RunlenBits+1] of { * => 0 };	for(i := 0; i < hclen; i++) {		nb := getn(s, 3, 0);		if(nb) {			runlentab[clenorder[i]].bits = nb;			count[nb]++;		}	}	hufftabinit(runlentab, Nclen, count, RunlenBits);	runlendec := decodeinit(runlentab, Nclen, RunlenBits, 0);	if(runlendec == nil)		fatal(s, "corrupt data"); 	lengths := decodelen(s, runlendec, hlit+hdist);	if(lengths == nil)		fatal(s, "corrupt length table"); 	dlitlendec := decodedyn(s, lengths[0:hlit], hlit, 9);	doffdec := decodedyn(s, lengths[hlit:], hdist, 5);	decodeblock(s, dlitlendec, doffdec);} ## return the decoded combined length table for literal and distance alphabets#decodelen(s: ref State, runlendec: ref DeHuff, nlen: int): array of int{	lengths := array[nlen] of int;	for(n := 0; n < nlen;) {		nb := decodesym(s, runlendec);		nr := 1;		case nb {		0 to 15 =>			;		16 =>			nr = getn(s, 2, 0) + 3;			if(n == 0)				return nil;			nb = lengths[n-1];		17 =>			nr = getn(s, 3, 0) + 3;

Lines 1–500 of 745. Load more