xref: /inferno-os/appl/lib/inflate.b (revision ce02cfb2169def0df6778d9be67d18545647bff4)

# 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 text
GZFHCRC:	con 1 << 1;		# crc of header included
GZFEXTRA:	con 1 << 2;		# extra header included
GZFNAME:	con 1 << 3;		# name of file included
GZFCOMMENT:	con 1 << 4;		# header comment included
GZFMASK:	con (1 << 5) - 1;	# mask of specified bits

GZXBEST:	con byte 2;		# used maximum compression algorithm
GZXFAST:	con byte 4;		# used fast algorithm little compression

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;

# huffman code table
Huff: adt
{
	bits:		int;		# length of the code
	encode:		int;		# the code
};

# huffman decode table
DeHuff: 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 table
L1: adt
{
	bits:		int;		# length of the code
	decode:		int;		# the symbol
	l2:		array of L2;
};

# second level
L2: adt
{
	bits:		int;		# length of the code
	decode:		int;		# the symbol
};

DeflateUnc:	con 0;			# uncompressed block
DeflateFix:	con 1;			# fixed huffman codes
DeflateDyn:	con 2;			# dynamic huffman codes
DeflateErr:	con 3;			# reserved BTYPE (error)

DeflateEob:	con 256;		# end of block code in lit/len book

LenStart:	con 257;		# start of length codes in litlen
LenEnd:		con 285;		# greatest valid length code
Nlitlen:	con 288;		# number of litlen codes
Noff:		con 30;			# number of offset codes
Nclen:		con 19;			# number of codelen codes

MaxHuffBits:	con 15;			# max bits in a huffman code
RunlenBits:	con 7;			# max bits in a run-length huffman code
MaxOff:		con 32*1024;		# max lempel-ziv distance

Blocksize: con 32 * 1024;

# tables from RFC 1951, section 3.2.5
litlenbase := 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 codes
clenorder := array[Nclen] of
{
	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
};

# fixed huffman tables
litlentab: array of Huff;
offtab: array of Huff;

# their decoding table counterparts
litlendec: ref DeHuff;
offdec: ref DeHuff;

revtab: array of byte;	# bit reversal for endian swap of huffman codes
mask: array of int;		# for masking low-order n bits of an int

Hnone, Hgzip, Hzlib: con iota;  # State.headers
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;		# for gzip trailer
	sum:	big;		# for zlib trailer

	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.sum = big 1;
	s.hist = array[Blocksize] of byte;
	s.headers = Hnone;
	if(params != nil) {
		if(params[0] == 'h')
			s.headers = Hgzip;
		if(params[0] == 'z')
			s.headers = Hzlib;
	}
	if (s.headers == Hgzip)
		s.crctab = mkcrctab(GZCRCPOLY);
	spawn inflate(s);
	return s.c;
}

inflate(s: ref State)
{
	s.c <-= ref Rq.Start(sys->pctl(0, nil));
	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) {
				outblock(s);
				s.c <- = ref Rq.Result(s.obuf[0:s.out], s.rc);
				flag := <- s.rc;
				if (flag == -1)
					exit;
			}
			flushbits(s);
			footer(s);
			s.c <-= ref Rq.Finished(s.ibuf[s.in - s.nbits/8:s.ein]);
			exit;
		}
	}
}

headergzip(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);
	}
}

headerzlib(s: ref State)
{
	Fdict:		con 1<<5;
	CMshift:	con 8;
	CMmask:		con (1<<4)-1;
	CMdeflate:	con 8;

	h := 0;
	h |= getb(s)<<8;
	h |= getb(s);
	if(h % 31 != 0)
		fatal(s, "invalid zlib header");
	if(h&Fdict)
		fatal(s, "preset dictionary not supported");
	if(((h>>CMshift)&CMmask) != CMdeflate)
		fatal(s, "zlib compression method not deflate");
}

header(s: ref State)
{
	case s.headers {
	Hgzip =>	headergzip(s);
	Hzlib =>	headerzlib(s);
	}
}

footergzip(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));
}

footerzlib(s: ref State)
{
	sum := big 0;
	sum = (sum<<8)|big getb(s);
	sum = (sum<<8)|big getb(s);
	sum = (sum<<8)|big getb(s);
	sum = (sum<<8)|big getb(s);
	if(sum != s.sum)
		fatal(s, sys->sprint("adler32 mismatch: computed %bux, expected %bux", s.sum, sum));
}

footer(s: ref State)
{
	case s.headers {
	Hgzip =>	footergzip(s);
	Hzlib =>	footerzlib(s);
	}
}

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;
			nb = 0;
		18 =>
			nr = getn(s, 7, 0) + 11;
			nb = 0;
		* =>
			return nil;
		}
		if(n+nr > nlen)
			return nil;
		while(--nr >= 0)
			lengths[n++] = nb;
	}
	return lengths;
}

#
# (1) read a dynamic huffman code from the input stream
# (2) decode it using the run-length huffman code
# (3) return the decode table for the dynamic huffman code
#
decodedyn(s: ref State, lengths: array of int, nlen, nb1: int): ref DeHuff
{
	hufftab := array[nlen] of Huff;
	count := array[MaxHuffBits+1] of { * => 0 };

	maxnb := 0;
	for(n := 0; n < nlen; n++) {
		c := lengths[n];
		if(c) {
			hufftab[n].bits = c;
			count[c]++;
			if(c > maxnb)
				maxnb = c;
		}else
			hufftab[n].bits = 0;
		hufftab[n].encode = 0;
	}
	hufftabinit(hufftab, nlen, count, maxnb);
	nb2 := 0;
	if(maxnb > nb1)
		nb2 = maxnb - nb1;
	d := decodeinit(hufftab, nlen, nb1, nb2);
	if (d == nil)
		fatal(s, "decodeinit failed");
	return d;
}

#
# RFC 1951, section 3.2.2
#
hufftabinit(tab: array of Huff, n: int, bitcount: array of int, nbits: int)
{
	nc := array[MaxHuffBits+1] of int;

	code := 0;
	for(bits := 1; bits <= nbits; bits++) {
		code = (code + bitcount[bits-1]) << 1;
		nc[bits] = code;
	}

	for(i := 0; i < n; i++) {
		bits = tab[i].bits;
		# differences from Deflate module:
		#  (1) leave huffman code right-justified in encode
		#  (2) don't reverse it
		if(bits != 0)
			tab[i].encode = nc[bits]++;
	}
}

#
# convert 'array of Huff' produced by hufftabinit()
# into 2-level lookup table for decoding
#
# nb1(nb2): number of bits handled by first(second)-level table
#
decodeinit(tab: array of Huff, n, nb1, nb2: int): ref DeHuff
{
	i, j, k, d: int;

	dehuff := ref DeHuff(array[1<<nb1] of { * => L1(0, 0, nil) }, nb1, nb2);
	l1 := dehuff.l1;
	for(i = 0; i < n; i++) {
		bits := tab[i].bits;
		if(bits == 0)
			continue;
		l1x := tab[i].encode;
		if(l1x >= (1 << bits))
			return nil;
		if(bits <= nb1) {
			d = nb1 - bits;
			l1x <<= d;
			k = l1x + mask[d];
			for(j = l1x; j <= k; j++) {
				l1[j].decode = i;
				l1[j].bits = bits;
			}
			continue;
		}
		# advance to second-level table
		d = bits - nb1;
		l2x := l1x & mask[d];
		l1x >>= d;
		if(l1[l1x].l2 == nil)
			l1[l1x].l2 = array[1<<nb2] of { * => L2(0, 0) };
		l2 := l1[l1x].l2;
		d = (nb1 + nb2) - bits;
		l2x <<= d;
		k = l2x + mask[d];
		for(j = l2x; j <= k; j++) {
			l2[j].decode = i;
			l2[j].bits = bits;
		}
	}

	return dehuff;
}

#
# get next byte from reg
# assumptions:
#  (1) flushbits() has been called
#  (2) ungetn() won't be called after a getb()
#
getb(s: ref State): int
{
	if(s.nbits < 8)
		need(s, 8);
	b := byte s.reg;
	s.reg >>= 8;
	s.nbits -= 8;
	return int b;
}

#
# get next n bits from reg; if r != 0, reverse the bits
#
getn(s: ref State, n, r: int): int
{
	if(s.nbits < n)
		need(s, n);
	s.svreg = s.reg;
	s.svn = n;
	i := s.reg & mask[n];
	s.reg >>= n;
	s.nbits -= n;
	if(r) {
		if(n <= 8) {
			i = int revtab[i];
			i >>= 8 - n;
		} else {
			i = ((int revtab[i & 16rff]) << 8)
				| (int revtab[i >> 8]);
			i >>= 16 - n;
		}
	}
	return i;
}

#
# ensure that at least n bits are available in reg
#
need(s: ref State, n: int)
{
	while(s.nbits < n) {
		if(s.in >= s.ein) {
			s.c <-= ref Rq.Fill(s.ibuf, s.rc);
			s.ein = <- s.rc;
			if (s.ein < 0)
				exit;
			if (s.ein == 0)
				fatal(s, "premature end of stream");
			s.in = 0;
		}
		s.reg = ((int s.ibuf[s.in++]) << s.nbits) | s.reg;
		s.nbits += 8;
	}
}

#
# if partial byte consumed from reg, dispose of remaining bits
#
flushbits(s: ref State)
{
	drek := s.nbits % 8;
	if(drek) {
		s.reg >>= drek;
		s.nbits -= drek;
	}
}

#
# output buffer is full, so flush it
#
flushout(s: ref State)
{
	outblock(s);
	s.c <-= ref Rq.Result(s.obuf[0:s.out], s.rc);
	flag := <- s.rc;
	if (flag == -1)
		exit;
	buf := s.hist;
	s.hist = s.obuf;
	s.usehist = 1;
	s.obuf = buf;
	s.out = 0;
}

mkcrctab(poly: int): array of int
{
	crctab := array[256] of int;
	for(i := 0; i < 256; i++){
		crc := i;
		for(j := 0; j < 8; j++){
			c := crc & 1;
			crc = (crc >> 1) & 16r7fffffff;
			if(c)
				crc ^= poly;
		}
		crctab[i] = crc;
	}
	return crctab;
}

outblockgzip(s: ref State)
{
	buf := s.obuf;
	n := s.out;
	crc := s.crc;
	crc ^= int 16rffffffff;
	for(i := 0; i < n; i++)
		crc = s.crctab[int(byte crc ^ buf[i])] ^ ((crc >> 8) & 16r00ffffff);
	s.crc = crc ^ int 16rffffffff;
	s.tot += n;
}

outblockzlib(s: ref State)
{
	ZLADLERBASE:	con big 65521;

	buf := s.obuf;
	n := s.out;

	s1 := s.sum & big 16rffff;
	s2 := (s.sum>>16) & big 16rffff;

	for(i := 0; i < n; i++) {
		s1 = (s1 + big buf[i]) % ZLADLERBASE;
		s2 = (s2 + s1) % ZLADLERBASE;
	}
	s.sum = (s2<<16) + s1;
}

outblock(s: ref State)
{
	case s.headers {
	Hgzip =>	outblockgzip(s);
	Hzlib =>	outblockzlib(s);
	}
}

#
# irrecoverable error; invariably denotes data corruption
#
fatal(s: ref State, e: string)
{
	s.c <-= ref Rq.Error(e);
	exit;
}