ref: 41d4cecf6d55af3ee0ced4c45d34450f4501608b
dir: /sys/src/libflate/inflate.c/
#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];
int 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;
}
}
if(maxbits <= 0){
h->maxbits = 0;
h->minbits = 0;
h->flatmask = 0;
h->maxleaf = 0;
return 1;
}
h->maxbits = maxbits;
if(maxbits >= MaxHuffBits || minbits <= 0)
return 0;
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;
}
h->maxleaf = maxleaf;
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)
{
ulong 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]){
c = h->last[nb] - c;
if(c >= h->maxleaf)
break;
in->sreg >>= nb;
in->nbits -= nb;
return h->decode[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;
}