plan9port

inflate.c (13119B)

---

 #include <u.h>
 #include <libc.h>
 #include <flate.h>
 
 enum {
 	HistorySize=	32*1024,
 	BufSize=	4*1024,
 	MaxHuffBits=	17,	/* maximum bits in a encoded code */
 	Nlitlen=	288,	/* number of litlen codes */
 	Noff=		32,	/* number of offset codes */
 	Nclen=		19,	/* number of codelen codes */
 	LenShift=	10,	/* code = len<<LenShift|code */
 	LitlenBits=	7,	/* number of bits in litlen decode table */
 	OffBits=	6,	/* number of bits in offset decode table */
 	ClenBits=	6,	/* number of bits in code len decode table */
 	MaxFlatBits=	LitlenBits,
 	MaxLeaf=	Nlitlen
 };
 
 typedef struct Input	Input;
 typedef struct History	History;
 typedef struct Huff	Huff;
 
 struct Input
 {
 	int	error;		/* first error encountered, or FlateOk */
 	void	*wr;
 	int	(*w)(void*, void*, int);
 	void	*getr;
 	int	(*get)(void*);
 	ulong	sreg;
 	int	nbits;
 };
 
 struct History
 {
 	uchar	his[HistorySize];
 	uchar	*cp;		/* current pointer in history */
 	int	full;		/* his has been filled up at least once */
 };
 
 struct Huff
 {
 	int	maxbits;	/* max bits for any code */
 	int	minbits;	/* min bits to get before looking in flat */
 	int	flatmask;	/* bits used in "flat" fast decoding table */
 	ulong	flat[1<<MaxFlatBits];
 	ulong	maxcode[MaxHuffBits];
 	ulong	last[MaxHuffBits];
 	ulong	decode[MaxLeaf];
 };
 
 /* litlen code words 257-285 extra bits */
 static int litlenextra[Nlitlen-257] =
 {
 /* 257 */	0, 0, 0,
 /* 260 */	0, 0, 0, 0, 0, 1, 1, 1, 1, 2,
 /* 270 */	2, 2, 2, 3, 3, 3, 3, 4, 4, 4,
 /* 280 */	4, 5, 5, 5, 5, 0, 0, 0
 };
 
 static int litlenbase[Nlitlen-257];
 
 /* offset code word extra bits */
 static int offextra[Noff] =
 {
 	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,
 };
 static int offbase[Noff];
 
 /* order code lengths */
 static int clenorder[Nclen] =
 {
         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
 };
 
 /* for static huffman tables */
 static	Huff	litlentab;
 static	Huff	offtab;
 static	uchar	revtab[256];
 
 static int	uncblock(Input *in, History*);
 static int	fixedblock(Input *in, History*);
 static int	dynamicblock(Input *in, History*);
 static int	sregfill(Input *in, int n);
 static int	sregunget(Input *in);
 static int	decode(Input*, History*, Huff*, Huff*);
 static int	hufftab(Huff*, char*, int, int);
 static int	hdecsym(Input *in, Huff *h, int b);
 
 int
 inflateinit(void)
 {
 	char *len;
 	int i, j, base;
 
 	/* byte reverse table */
 	for(i=0; i<256; i++)
 		for(j=0; j<8; j++)
 			if(i & (1<<j))
 				revtab[i] |= 0x80 >> j;
 
 	for(i=257,base=3; i<Nlitlen; i++) {
 		litlenbase[i-257] = base;
 		base += 1<<litlenextra[i-257];
 	}
 	/* strange table entry in spec... */
 	litlenbase[285-257]--;
 
 	for(i=0,base=1; i<Noff; i++) {
 		offbase[i] = base;
 		base += 1<<offextra[i];
 	}
 
 	len = malloc(MaxLeaf);
 	if(len == nil)
 		return FlateNoMem;
 
 	/* static Litlen bit lengths */
 	for(i=0; i<144; i++)
 		len[i] = 8;
 	for(i=144; i<256; i++)
 		len[i] = 9;
 	for(i=256; i<280; i++)
 		len[i] = 7;
 	for(i=280; i<Nlitlen; i++)
 		len[i] = 8;
 
 	if(!hufftab(&litlentab, len, Nlitlen, MaxFlatBits))
 		return FlateInternal;
 
 	/* static Offset bit lengths */
 	for(i=0; i<Noff; i++)
 		len[i] = 5;
 
 	if(!hufftab(&offtab, len, Noff, MaxFlatBits))
 		return FlateInternal;
 	free(len);
 
 	return FlateOk;
 }
 
 int
 inflate(void *wr, int (*w)(void*, void*, int), void *getr, int (*get)(void*))
 {
 	History *his;
 	Input in;
 	int final, type;
 
 	his = malloc(sizeof(History));
 	if(his == nil)
 		return FlateNoMem;
 	his->cp = his->his;
 	his->full = 0;
 	in.getr = getr;
 	in.get = get;
 	in.wr = wr;
 	in.w = w;
 	in.nbits = 0;
 	in.sreg = 0;
 	in.error = FlateOk;
 
 	do {
 		if(!sregfill(&in, 3))
 			goto bad;
 		final = in.sreg & 0x1;
 		type = (in.sreg>>1) & 0x3;
 		in.sreg >>= 3;
 		in.nbits -= 3;
 		switch(type) {
 		default:
 			in.error = FlateCorrupted;
 			goto bad;
 		case 0:
 			/* uncompressed */
 			if(!uncblock(&in, his))
 				goto bad;
 			break;
 		case 1:
 			/* fixed huffman */
 			if(!fixedblock(&in, his))
 				goto bad;
 			break;
 		case 2:
 			/* dynamic huffman */
 			if(!dynamicblock(&in, his))
 				goto bad;
 			break;
 		}
 	} while(!final);
 
 	if(his->cp != his->his && (*w)(wr, his->his, his->cp - his->his) != his->cp - his->his) {
 		in.error = FlateOutputFail;
 		goto bad;
 	}
 
 	if(!sregunget(&in))
 		goto bad;
 
 	free(his);
 	if(in.error != FlateOk)
 		return FlateInternal;
 	return FlateOk;
 
 bad:
 	free(his);
 	if(in.error == FlateOk)
 		return FlateInternal;
 	return in.error;
 }
 
 static int
 uncblock(Input *in, History *his)
 {
 	int len, nlen, c;
 	uchar *hs, *hp, *he;
 
 	if(!sregunget(in))
 		return 0;
 	len = (*in->get)(in->getr);
 	len |= (*in->get)(in->getr)<<8;
 	nlen = (*in->get)(in->getr);
 	nlen |= (*in->get)(in->getr)<<8;
 	if(len != (~nlen&0xffff)) {
 		in->error = FlateCorrupted;
 		return 0;
 	}
 
 	hp = his->cp;
 	hs = his->his;
 	he = hs + HistorySize;
 
 	while(len > 0) {
 		c = (*in->get)(in->getr);
 		if(c < 0)
 			return 0;
 		*hp++ = c;
 		if(hp == he) {
 			his->full = 1;
 			if((*in->w)(in->wr, hs, HistorySize) != HistorySize) {
 				in->error = FlateOutputFail;
 				return 0;
 			}
 			hp = hs;
 		}
 		len--;
 	}
 
 	his->cp = hp;
 
 	return 1;
 }
 
 static int
 fixedblock(Input *in, History *his)
 {
 	return decode(in, his, &litlentab, &offtab);
 }
 
 static int
 dynamicblock(Input *in, History *his)
 {
 	Huff *lentab, *offtab;
 	char *len;
 	int i, j, n, c, nlit, ndist, nclen, res, nb;
 
 	if(!sregfill(in, 14))
 		return 0;
 	nlit = (in->sreg&0x1f) + 257;
 	ndist = ((in->sreg>>5) & 0x1f) + 1;
 	nclen = ((in->sreg>>10) & 0xf) + 4;
 	in->sreg >>= 14;
 	in->nbits -= 14;
 
 	if(nlit > Nlitlen || ndist > Noff || nlit < 257) {
 		in->error = FlateCorrupted;
 		return 0;
 	}
 
 	/* huff table header */
 	len = malloc(Nlitlen+Noff);
 	lentab = malloc(sizeof(Huff));
 	offtab = malloc(sizeof(Huff));
 	if(len == nil || lentab == nil || offtab == nil){
 		in->error = FlateNoMem;
 		goto bad;
 	}
 	for(i=0; i < Nclen; i++)
 		len[i] = 0;
 	for(i=0; i<nclen; i++) {
 		if(!sregfill(in, 3))
 			goto bad;
 		len[clenorder[i]] = in->sreg & 0x7;
 		in->sreg >>= 3;
 		in->nbits -= 3;
 	}
 
 	if(!hufftab(lentab, len, Nclen, ClenBits)){
 		in->error = FlateCorrupted;
 		goto bad;
 	}
 
 	n = nlit+ndist;
 	for(i=0; i<n;) {
 		nb = lentab->minbits;
 		for(;;){
 			if(in->nbits<nb && !sregfill(in, nb))
 				goto bad;
 			c = lentab->flat[in->sreg & lentab->flatmask];
 			nb = c & 0xff;
 			if(nb > in->nbits){
 				if(nb != 0xff)
 					continue;
 				c = hdecsym(in, lentab, c);
 				if(c < 0)
 					goto bad;
 			}else{
 				c >>= 8;
 				in->sreg >>= nb;
 				in->nbits -= nb;
 			}
 			break;
 		}
 
 		if(c < 16) {
 			j = 1;
 		} else if(c == 16) {
 			if(in->nbits<2 && !sregfill(in, 2))
 				goto bad;
 			j = (in->sreg&0x3)+3;
 			in->sreg >>= 2;
 			in->nbits -= 2;
 			if(i == 0) {
 				in->error = FlateCorrupted;
 				goto bad;
 			}
 			c = len[i-1];
 		} else if(c == 17) {
 			if(in->nbits<3 && !sregfill(in, 3))
 				goto bad;
 			j = (in->sreg&0x7)+3;
 			in->sreg >>= 3;
 			in->nbits -= 3;
 			c = 0;
 		} else if(c == 18) {
 			if(in->nbits<7 && !sregfill(in, 7))
 				goto bad;
 			j = (in->sreg&0x7f)+11;
 			in->sreg >>= 7;
 			in->nbits -= 7;
 			c = 0;
 		} else {
 			in->error = FlateCorrupted;
 			goto bad;
 		}
 
 		if(i+j > n) {
 			in->error = FlateCorrupted;
 			goto bad;
 		}
 
 		while(j) {
 			len[i] = c;
 			i++;
 			j--;
 		}
 	}
 
 	if(!hufftab(lentab, len, nlit, LitlenBits)
 	|| !hufftab(offtab, &len[nlit], ndist, OffBits)){
 		in->error = FlateCorrupted;
 		goto bad;
 	}
 
 	res = decode(in, his, lentab, offtab);
 
 	free(len);
 	free(lentab);
 	free(offtab);
 
 	return res;
 
 bad:
 	free(len);
 	free(lentab);
 	free(offtab);
 	return 0;
 }
 
 static int
 decode(Input *in, History *his, Huff *litlentab, Huff *offtab)
 {
 	int len, off;
 	uchar *hs, *hp, *hq, *he;
 	int c;
 	int nb;
 
 	hs = his->his;
 	he = hs + HistorySize;
 	hp = his->cp;
 
 	for(;;) {
 		nb = litlentab->minbits;
 		for(;;){
 			if(in->nbits<nb && !sregfill(in, nb))
 				return 0;
 			c = litlentab->flat[in->sreg & litlentab->flatmask];
 			nb = c & 0xff;
 			if(nb > in->nbits){
 				if(nb != 0xff)
 					continue;
 				c = hdecsym(in, litlentab, c);
 				if(c < 0)
 					return 0;
 			}else{
 				c >>= 8;
 				in->sreg >>= nb;
 				in->nbits -= nb;
 			}
 			break;
 		}
 
 		if(c < 256) {
 			/* literal */
 			*hp++ = c;
 			if(hp == he) {
 				his->full = 1;
 				if((*in->w)(in->wr, hs, HistorySize) != HistorySize) {
 					in->error = FlateOutputFail;
 					return 0;
 				}
 				hp = hs;
 			}
 			continue;
 		}
 
 		if(c == 256)
 			break;
 
 		if(c > 285) {
 			in->error = FlateCorrupted;
 			return 0;
 		}
 
 		c -= 257;
 		nb = litlenextra[c];
 		if(in->nbits < nb && !sregfill(in, nb))
 			return 0;
 		len = litlenbase[c] + (in->sreg & ((1<<nb)-1));
 		in->sreg >>= nb;
 		in->nbits -= nb;
 
 		/* get offset */
 		nb = offtab->minbits;
 		for(;;){
 			if(in->nbits<nb && !sregfill(in, nb))
 				return 0;
 			c = offtab->flat[in->sreg & offtab->flatmask];
 			nb = c & 0xff;
 			if(nb > in->nbits){
 				if(nb != 0xff)
 					continue;
 				c = hdecsym(in, offtab, c);
 				if(c < 0)
 					return 0;
 			}else{
 				c >>= 8;
 				in->sreg >>= nb;
 				in->nbits -= nb;
 			}
 			break;
 		}
 
 		if(c > 29) {
 			in->error = FlateCorrupted;
 			return 0;
 		}
 
 		nb = offextra[c];
 		if(in->nbits < nb && !sregfill(in, nb))
 			return 0;
 
 		off = offbase[c] + (in->sreg & ((1<<nb)-1));
 		in->sreg >>= nb;
 		in->nbits -= nb;
 
 		hq = hp - off;
 		if(hq < hs) {
 			if(!his->full) {
 				in->error = FlateCorrupted;
 				return 0;
 			}
 			hq += HistorySize;
 		}
 
 		/* slow but correct */
 		while(len) {
 			*hp = *hq;
 			hq++;
 			hp++;
 			if(hq >= he)
 				hq = hs;
 			if(hp == he) {
 				his->full = 1;
 				if((*in->w)(in->wr, hs, HistorySize) != HistorySize) {
 					in->error = FlateOutputFail;
 					return 0;
 				}
 				hp = hs;
 			}
 			len--;
 		}
 
 	}
 
 	his->cp = hp;
 
 	return 1;
 }
 
 static int
 revcode(int c, int b)
 {
 	/* shift encode up so it starts on bit 15 then reverse */
 	c <<= (16-b);
 	c = revtab[c>>8] | (revtab[c&0xff]<<8);
 	return c;
 }
 
 /*
  * construct the huffman decoding arrays and a fast lookup table.
  * the fast lookup is a table indexed by the next flatbits bits,
  * which returns the symbol matched and the number of bits consumed,
  * or the minimum number of bits needed and 0xff if more than flatbits
  * bits are needed.
  *
  * flatbits can be longer than the smallest huffman code,
  * because shorter codes are assigned smaller lexical prefixes.
  * this means assuming zeros for the next few bits will give a
  * conservative answer, in the sense that it will either give the
  * correct answer, or return the minimum number of bits which
  * are needed for an answer.
  */
 static int
 hufftab(Huff *h, char *hb, int maxleaf, int flatbits)
 {
 	ulong bitcount[MaxHuffBits];
 	ulong c, fc, ec, mincode, code, nc[MaxHuffBits];
 	int i, b, minbits, maxbits;
 
 	for(i = 0; i < MaxHuffBits; i++)
 		bitcount[i] = 0;
 	maxbits = -1;
 	minbits = MaxHuffBits + 1;
 	for(i=0; i < maxleaf; i++){
 		b = hb[i];
 		if(b){
 			bitcount[b]++;
 			if(b < minbits)
 				minbits = b;
 			if(b > maxbits)
 				maxbits = b;
 		}
 	}
 
 	h->maxbits = maxbits;
 	if(maxbits <= 0){
 		h->maxbits = 0;
 		h->minbits = 0;
 		h->flatmask = 0;
 		return 1;
 	}
 	code = 0;
 	c = 0;
 	for(b = 0; b <= maxbits; b++){
 		h->last[b] = c;
 		c += bitcount[b];
 		mincode = code << 1;
 		nc[b] = mincode;
 		code = mincode + bitcount[b];
 		if(code > (1 << b))
 			return 0;
 		h->maxcode[b] = code - 1;
 		h->last[b] += code - 1;
 	}
 
 	if(flatbits > maxbits)
 		flatbits = maxbits;
 	h->flatmask = (1 << flatbits) - 1;
 	if(minbits > flatbits)
 		minbits = flatbits;
 	h->minbits = minbits;
 
 	b = 1 << flatbits;
 	for(i = 0; i < b; i++)
 		h->flat[i] = ~0;
 
 	/*
 	 * initialize the flat table to include the minimum possible
 	 * bit length for each code prefix
 	 */
 	for(b = maxbits; b > flatbits; b--){
 		code = h->maxcode[b];
 		if(code == -1)
 			break;
 		mincode = code + 1 - bitcount[b];
 		mincode >>= b - flatbits;
 		code >>= b - flatbits;
 		for(; mincode <= code; mincode++)
 			h->flat[revcode(mincode, flatbits)] = (b << 8) | 0xff;
 	}
 
 	for(i = 0; i < maxleaf; i++){
 		b = hb[i];
 		if(b <= 0)
 			continue;
 		c = nc[b]++;
 		if(b <= flatbits){
 			code = (i << 8) | b;
 			ec = (c + 1) << (flatbits - b);
 			if(ec > (1<<flatbits))
 				return 0;	/* this is actually an internal error */
 			for(fc = c << (flatbits - b); fc < ec; fc++)
 				h->flat[revcode(fc, flatbits)] = code;
 		}
 		if(b > minbits){
 			c = h->last[b] - c;
 			if(c >= maxleaf)
 				return 0;
 			h->decode[c] = i;
 		}
 	}
 	return 1;
 }
 
 static int
 hdecsym(Input *in, Huff *h, int nb)
 {
 	long c;
 
 	if((nb & 0xff) == 0xff)
 		nb = nb >> 8;
 	else
 		nb = nb & 0xff;
 	for(; nb <= h->maxbits; nb++){
 		if(in->nbits<nb && !sregfill(in, nb))
 			return -1;
 		c = revtab[in->sreg&0xff]<<8;
 		c |= revtab[(in->sreg>>8)&0xff];
 		c >>= (16-nb);
 		if(c <= h->maxcode[nb]){
 			in->sreg >>= nb;
 			in->nbits -= nb;
 			return h->decode[h->last[nb] - c];
 		}
 	}
 	in->error = FlateCorrupted;
 	return -1;
 }
 
 static int
 sregfill(Input *in, int n)
 {
 	int c;
 
 	while(n > in->nbits) {
 		c = (*in->get)(in->getr);
 		if(c < 0){
 			in->error = FlateInputFail;
 			return 0;
 		}
 		in->sreg |= c<<in->nbits;
 		in->nbits += 8;
 	}
 	return 1;
 }
 
 static int
 sregunget(Input *in)
 {
 	if(in->nbits >= 8) {
 		in->error = FlateInternal;
 		return 0;
 	}
 
 	/* throw other bits on the floor */
 	in->nbits = 0;
 	in->sreg = 0;
 	return 1;
 }