aboutsummaryrefslogtreecommitdiff
path: root/src/libflate/inflate.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/libflate/inflate.c')
-rw-r--r--src/libflate/inflate.c693
1 files changed, 693 insertions, 0 deletions
diff --git a/src/libflate/inflate.c b/src/libflate/inflate.c
new file mode 100644
index 00000000..f979084c
--- /dev/null
+++ b/src/libflate/inflate.c
@@ -0,0 +1,693 @@
+#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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-02 20:11:04 +0000