commit 125cf4e3c02d9e3e8258f164e73dbcc316d18310
parent 6f4def03127440b59a3f06f4e7ef119fdd1fcf8d
Author: nsz <nszabolcs@gmail.com>
Date: Wed, 17 Jun 2009 09:28:04 +0200
halibut deflate mod (wip)
Diffstat:
2 files changed, 852 insertions(+), 1 deletion(-)
diff --git a/deflate_simple.c b/deflate_simple.c
@@ -0,0 +1,850 @@
+#include <stdlib.h>
+#include <string.h>
+
+typedef unsigned char uchar;
+typedef unsigned short ushort;
+typedef unsigned int uint;
+
+enum {
+ Nmatch = 32,
+ HashSize = 2039,
+ HashChars = 3,
+ WinSize = 1 << 15,
+ WinMask = WinSize - 1,
+ SymSize = 1 << 16,
+};
+
+enum {
+ CodeBits = 16, /* max number of bits in a code + 1 */
+ Nlit = 256, /* number of lit codes */
+ Nlen = 29, /* number of len codes */
+ Nlitlen = Nlit + Nlen + 3, /* litlen codes + block end + 2 unused */
+ Ndist = 30, /* number of distance codes */
+ Nclen = 19 /* number of code length codes */
+};
+
+typedef struct {
+ ushort dist;
+ ushort len;
+} Match;
+
+typedef struct {
+ short next;
+ short prev; /* index within s->win */
+ short hash;
+} Entry;
+
+typedef struct {
+ uchar *len; /* bit length of the code */
+ ushort *code;
+} Huff;
+
+typedef struct {
+ short tab[HashSize]; /* position of hash chain heads */
+ int pos; /* position in win and data */
+ Entry win[WinSize]; /* hash chains */
+ uchar data[WinSize]; /* uncompressed character data */
+ uchar pending[HashChars]; /* characters from previous compress */
+ int npending;
+
+ ushort *symbuf; /* lz77 literal and (len,dist) sequence */
+ int symstart;
+ int symlen;
+
+ uchar *outbuf; /* encoded output */
+ int outpos;
+ int outlen;
+ uint bits;
+ int nbits;
+
+ int type;
+ int firstblock;
+ int lastblock;
+ int finished;
+
+ Huff fixed_litlen;
+ Huff fixed_dist;
+ Huff litlen;
+ Huff dist;
+ Huff clen;
+} State;
+
+/* TODO: globals.. */
+static Huff lhuff; /* fixed lit/len huffman code tree */
+static Huff dhuff; /* fixed distance huffman code tree */
+
+/* base offset and extra bits tables */
+static uchar lenbits[Nlen] = {
+ 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
+};
+static ushort lenbase[Nlen] = {
+ 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
+};
+static uchar distbits[Ndist] = {
+ 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
+};
+static ushort distbase[Ndist] = {
+ 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
+};
+
+/* ordering of code lengths */
+static uchar clenorder[Nclen] = {
+ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
+};
+
+static short hash_chars(uchar *p) {
+ return (257 * p[0] + 263 * p[1] + 269 * p[2]) % HashSize;
+}
+
+static int lz_init(State *s) {
+ int i;
+
+ for (i = 0; i < WinSize; i++)
+ s->win[i].next = s->win[i].prev = s->win[i].hash = -1;
+ for (i = 0; i < HashSize; i++)
+ s->tab[i] = -1;
+ s->pos = 0;
+ s->npending = 0;
+ return 1;
+}
+
+static void lz_advance(State *s, uchar c, int hash) {
+ int pos = s->pos;
+ int next;
+
+ /* remove the hash entry at pos from its chain */
+ if (s->win[pos].prev != -1)
+ s->win[s->win[pos].prev].next = -1;
+ else if (s->win[pos].hash != -1)
+ s->tab[s->win[pos].hash] = -1;
+
+ /* create a new entry at pos */
+ s->win[pos].hash = hash;
+ s->win[pos].prev = -1;
+ s->win[pos].next = next = s->tab[hash];
+ s->tab[hash] = pos;
+ if (next != -1)
+ s->win[next].prev = pos;
+ s->data[pos] = c;
+ s->pos = (pos + 1) & WinMask;
+}
+
+/* s->data[]: past, s->data[s->pos]: present, data[]: future */
+static uchar getbyte(State *s, uchar *data, int n) {
+ return n < 0 ? s->data[(s->pos + n) & WinMask] : data[n];
+}
+
+static void literal(State *s, ushort lit);
+static void match(State *s, ushort dist, ushort len);
+
+static void lz_compress(State *s, uchar *data, int len) {
+ int i, hash, dist, off, nmatch, matchlen, nadvance;
+ Match defermatch, matches[Nmatch];
+ int deferchr;
+ int pos;
+
+ /* add pending characters from previous compress */
+ for (i = 0; i < s->npending; i++) {
+ uchar a[HashChars];
+ int j;
+
+ if (len + s->npending - i < HashChars) {
+ for (j = i; j < s->npending; j++)
+ s->pending[j - i] = s->pending[j];
+ break;
+ }
+ for (j = 0; j < HashChars; j++)
+ a[j] = i + j < s->npending ? s->pending[i + j] : data[i + j - s->npending];
+ lz_advance(s, a[0], hash_chars(a));
+ }
+ s->npending -= i;
+
+ defermatch.len = 0;
+ deferchr = '\0';
+ while (len > 0) {
+ if (len >= HashChars) {
+ /* find matches at least HashChars long */
+ hash = hash_chars(data);
+ nmatch = 0;
+ for (pos = s->tab[hash]; pos != -1; pos = s->win[pos].next) {
+ /* dist = 1 if pos == s->pos - 1 */
+ /* dist = WinSize if pos == s->pos */
+ dist = WinSize - (pos + WinSize - s->pos) & WinMask;
+ for (i = 0; i < HashChars; i++)
+ if (data[i] != getbyte(s, data, i - dist))
+ break;
+ if (i == HashChars) {
+ matches[nmatch].dist = dist;
+ matches[nmatch].len = HashChars;
+ if (++nmatch >= Nmatch)
+ break;
+ }
+ }
+ } else {
+ nmatch = 0;
+ hash = -1;
+ }
+ if (nmatch > 0) {
+ /* nmatch potential matches, we assume longer match is better */
+ matchlen = HashChars;
+ while (matchlen < len) {
+ int j;
+
+ for (i = j = 0; i < nmatch; i++)
+ if (getbyte(s, data, matchlen) == getbyte(s, data, matchlen - matches[i].dist))
+ matches[j++] = matches[i];
+ if (j == 0)
+ break;
+ matchlen++;
+ nmatch = j;
+ }
+ /* among the longest matches favour the shorter distance (matches[0]) */
+ matches[0].len = matchlen;
+ if (defermatch.len > 0) {
+ if (matches[0].len > defermatch.len + 1) {
+ /* We have a better match. Emit the deferred char,
+ * and defer this match. */
+ literal(s, deferchr);
+ defermatch = matches[0];
+ deferchr = data[0];
+ nadvance = 1;
+ } else {
+ /* We don't have a better match. Do the deferred one. */
+ match(s, defermatch.dist, defermatch.len);
+ nadvance = defermatch.len - 1;
+ defermatch.len = 0;
+ }
+ } else {
+ /* There was no deferred match. Defer this one. */
+ defermatch = matches[0];
+ deferchr = data[0];
+ nadvance = 1;
+ }
+ } else {
+ /* no matches, emit the deferred match or a literal. */
+ if (defermatch.len > 0) {
+ match(s, defermatch.dist, defermatch.len);
+ nadvance = defermatch.len - 1;
+ defermatch.len = 0;
+ } else {
+ literal(s, data[0]);
+ nadvance = 1;
+ }
+ }
+ /* advance winpos and keep the window and hash chains consistent. */
+ while (nadvance > 0) {
+ if (len >= HashChars)
+ lz_advance(s, *data, hash_chars(data));
+ else
+ s->pending[s->npending++] = *data;
+ data++;
+ len--;
+ nadvance--;
+ }
+ }
+}
+
+static uint revcode(uint c, int n) {
+ int i;
+ uint r = 0;
+
+ for (i = 0; i < n; i++) {
+ r = (r << 1) | (c & 1);
+ c >>= 1;
+ }
+ return r;
+}
+
+/* huffman codes from code lengths, return max code length */
+static int huffcodes(ushort *codes, const uchar *lens, int n) {
+ int c[CodeBits];
+ int i, left, max;
+
+ /* count code lengths */
+ for (i = 0; i < CodeBits; i++)
+ c[i] = 0;
+ for (i = 0; i < n; i++)
+ c[lens[i]]++;
+
+ /* calc max code lengths */
+ for (i = CodeBits - 1; i > 0; i--)
+ if (c[i])
+ break;
+ max = i;
+
+ /* check if length is over-subscribed or incomplete */
+ for (left = 2, i = 1; i <= max; i++) {
+ left -= c[i];
+ if (left < 0)
+ /* over-subscribed */
+ return -1;
+ left <<= 1;
+ }
+ if (left > 0)
+ /* incomlpete */;
+
+ /* calc first code for each length */
+ for (i = 2; i <= max; i++)
+ c[i] += c[i-1];
+
+ for (i = 0; i < n; i++)
+ if (lens[i])
+ codes[i] = revcode(c[lens[i]]++, lens[i]);
+ else
+ codes[i] = 0;
+ return max;
+}
+
+/* min-heap for buildhuf() */
+
+typedef struct {
+ int key;
+ int value;
+} Item;
+
+static int heapparent(int n) {return (n - 1)/2;}
+static int heapleft(int n) {return 2 * n + 1;}
+static int heapright(int n) {return 2 * n + 2;}
+
+static void heappush(Item *heap, int len, int key, int value) {
+ int n, dad;
+ Item tmp;
+
+ heap[len].key = key;
+ heap[len].value = value;
+ n = len;
+ while (n > 0) {
+ dad = heapparent(n);
+ if (heap[n].key < heap[dad].key) {
+ tmp = heap[n];
+ heap[n] = heap[dad];
+ heap[dad] = tmp;
+ n = dad;
+ } else
+ break;
+ }
+}
+
+static void heappop(Item *heap, int len, int *key, int *value) {
+ int n, lc, rc, child;
+ Item tmp;
+
+ *key = heap[0].key;
+ *value = heap[0].value;
+ heap[0] = heap[--len];
+ n = 0;
+ for (;;) {
+ lc = heapleft(n);
+ rc = heapright(n);
+ if (lc >= len)
+ break;
+ else if (rc >= len || heap[lc].key < heap[rc].key)
+ child = lc;
+ else
+ child = rc;
+ if (heap[n].key > heap[child].key) {
+ tmp = heap[n];
+ heap[n] = heap[child];
+ heap[child] = tmp;
+ } else
+ break;
+ n = child;
+ }
+}
+
+/* symbol frequencies -> code lengths (limited to 255) */
+static void hufflens(const int *freqs, uchar *lens, int nsym) {
+ int parent[2*Nlitlen-1];
+ int clen[2*Nlitlen-1];
+ Item heap[Nlitlen];
+ int n, len;
+ int i, j;
+ int wi, wj;
+
+ if (nsym > Nlitlen)
+ /* TODO: error */;
+
+ for (n = 0; n < nsym; n++)
+ if (freqs[n] > 0)
+ heappush(heap, n, freqs[n], n);
+
+ /* build code tree */
+ for (len = n; len > 1; n++) {
+ heappop(heap, len--, &wi, &i);
+ heappop(heap, len--, &wj, &j);
+ parent[i] = n;
+ parent[j] = n;
+ heappush(heap, len++, wi + wj, n);
+ }
+
+ /* calc code length */
+ clen[--n] = 0;
+ while (n--)
+ clen[n] = 1 + clen[parent[n]];
+
+ /* limit code length to 255 */
+ for (n = 0; n < nsym; n++)
+ lens[n] = clen[n] > 255 ? 255 : clen[n];
+}
+
+/* F_n if n > 0 */
+static int fib(int n) {
+ int a, b, tmp;
+
+ for (a = 0, b = 1; n > 1; n--) {
+ tmp = a;
+ a = b;
+ b += tmp;
+ }
+ return b;
+}
+
+/* might modify freqs, limit code length */
+static void hufflenslimit(int *freqs, uchar *lens, int nsym, int limit) {
+ uint minfreq, sumfreq, nrealsym;
+ int num, den, adjust;
+ int i, maxprob, count;
+
+ /* TODO: fewer than two symbols: add new */
+ if (nsym < 2)
+ /* error */ abort();
+ count = 0;
+ for (i = 0; i < nsym; i++)
+ if (freqs[i] > 0)
+ count++;
+ if (count < 2)
+ for (i = 0; count > 0 && i < nsym; i++)
+ if (freqs[i] == 0) {
+ freqs[i] = 1;
+ count--; /* what? */
+ }
+
+ /* try building the codes without limit */
+ hufflens(freqs, lens, nsym);
+
+ for (i = 0; i < nsym; i++)
+ if (lens[i] > limit)
+ break;
+ if (i == nsym)
+ return;
+
+ /*
+ * The Huffman algorithm can only ever generate a code length
+ * of N bits or more if there is a symbol whose probability is
+ * less than the reciprocal of the (N+2)th Fibonacci number.
+ *
+ * If hufflens() has returned a long code, we add a constant to
+ * all the (non-zero) symbol frequencies, causing them to become
+ * more balanced and call hufflens() again.
+ */
+ maxprob = fib(limit + 3);
+ sumfreq = nrealsym = 0;
+ minfreq = (uint)-1;
+ for (i = 0; i < nsym; i++) {
+ if (freqs[i] == 0)
+ continue;
+ if (minfreq > freqs[i])
+ minfreq = freqs[i];
+ sumfreq += freqs[i];
+ nrealsym++;
+ }
+ if (minfreq > sumfreq / maxprob)
+ /* error */ abort();
+
+ /*
+ * increase freqs with adjust, the smallest integer such that
+ * (sumfreq + nrealsym * adjust)/(minfreq + adjust) < maxprob
+ */
+ num = sumfreq - minfreq * maxprob;
+ den = maxprob - nrealsym;
+ adjust = (num + den - 1) / den;
+ for (i = 0; i < nsym; i++)
+ if (freqs[i] != 0)
+ freqs[i] += adjust;
+
+ /* rebuild the hufftree */
+ hufflens(freqs, lens, nsym);
+ for (i = 0; i < nsym; i++)
+ if (lens[i] > limit)
+ /* error */ abort();
+}
+
+/* adding < 16 bits to outbuf */
+static int outbits(State *s, uint bits, int nbits) {
+ s->bits |= bits << s->nbits;
+ s->nbits += nbits;
+ while (s->nbits >= 8) {
+ if (s->outpos == s->outlen)
+ return -1;
+ s->outbuf[s->outpos++] = s->bits & 0xff;
+ s->bits >>= 8;
+ s->nbits -= 8;
+ }
+ return 0;
+}
+
+static void putsym(State *s, ushort sym) {
+ s->symbuf[(s->symstart + s->symlen++) % SymSize] = sym;
+}
+
+static ushort getsym(State *s, int i) {
+ return s->symbuf[(s->symstart + i) % SymSize];
+}
+
+/* build dynamic block or a fixed block of given length */
+static void block(State *s, int dynlen, int fixlen) {
+ int lfreq[Nlitlen], dfreq[Ndist], cfreq[Nclen];
+ uchar llen[Nlitlen], dlen[Ndist], clen[Nclen];
+ ushort lcode[Nlitlen], dcode[Ndist], ccode[Nclen];
+ int nlit, ndist, nclen, bfinal, btype;
+ int tree[Nlitlen + Ndist];
+ int treesym[Nlitlen + Ndist];
+ int codelen[Nclen];
+ int i, ntree, ntreesym;
+ int dynamic, blocklen;
+
+ memset(lfreq, 0, sizeof(lfreq));
+ memset(dfreq, 0, sizeof(dfreq));
+ lfreq[256] = 1; /* EOB */
+ for (i = 0; i < s->symlen; i++) {
+ ushort sym = getsym(s, i);
+
+ lfreq[sym]++;
+ if (sym > Nlit) {
+ i++; /* extra nbits */
+ i++; /* extra bits */
+ i++; /* dist sym */
+ dfreq[getsym(s, i)]++;
+ i++; /* extra nbits */
+ i++; /* extra bits */
+ }
+ }
+ hufflenslimit(lfreq, llen, Nlitlen, CodeBits-1);
+ hufflenslimit(dfreq, dlen, Ndist, CodeBits-1);
+ huffcodes(lcode, llen, Nlitlen);
+ huffcodes(dcode, dlen, Ndist);
+
+ for (nlit = Nlitlen; nlit > Nlit && llen[nlit-1] == 0; nlit--);
+ for (ndist = Ndist; ndist > 1 && dlen[ndist-1] == 0; ndist--);
+
+ ntree = 0;
+ for (i = 0; i < nlit; i++)
+ tree[ntree++] = llen[i];
+ for (i = 0; i < ndist; i++)
+ tree[ntree++] = dlen[i];
+ ntreesym = 0;
+ for (i = 0; i < ntree;) {
+ int j = 1;
+ int k;
+
+ /* get run length of the same item */
+ while (i+j < ntree && tree[i+j] == tree[i])
+ j++;
+
+ /* encode economically */
+ k = j;
+ if (tree[i] == 0) {
+ if (k < 3)
+ while (k--)
+ treesym[ntreesym++] = 0;
+ else
+ while (k > 0) {
+ int r = k < 138 ? k : 138;
+
+ if (r > k - 3 && r < k)
+ r = k - 3;
+ if (r < 11) {
+ treesym[ntreesym++] = 17;
+ treesym[ntreesym++] = 3;
+ treesym[ntreesym++] = r - 3;
+ } else {
+ treesym[ntreesym++] = 18;
+ treesym[ntreesym++] = 7;
+ treesym[ntreesym++] = r - 11;
+ }
+ k -= r;
+ }
+ } else {
+ treesym[ntreesym++] = tree[i];
+ k--;
+ if (k < 3)
+ while (k--)
+ treesym[ntreesym++] = tree[i];
+ else
+ while (k > 0) {
+ int r = k < 6 ? k : 6;
+
+ if (r > k - 3 && r < k)
+ r = k - 3;
+ treesym[ntreesym++] = 16;
+ treesym[ntreesym++] = 2;
+ treesym[ntreesym++] = r - 3;
+ k -= r;
+ }
+ }
+ i += j;
+ }
+
+ memset(cfreq, 0, sizeof(cfreq));
+ for (i = 0; i < ntreesym; i++) {
+ uint sym = treesym[i];
+
+ cfreq[sym]++;
+ if (sym >= 16)
+ i += 2;
+ }
+ hufflenslimit(cfreq, clen, Nclen, 7);
+ huffcodes(ccode, clen, Nclen);
+
+ /* reorder */
+ for (i = 0; i < Nclen; i++)
+ codelen[i] = clen[clenorder[i]];
+ for (nclen = Nclen; nclen > 4 && codelen[nclen-1] == 0; nclen--);
+
+ /* exact size of dynamic and fixed block */
+ {
+ int fsize, dsize;
+
+ /* dynamic block */
+ dsize = 3 + 5 + 5 + 4; /* 3-bit header, nlit, ndist, nclen */
+ dsize += 3 * nclen; /* code-length-alphabet code lengths */
+ /* code lengths */
+ for (i = 0; i < ntreesym; i++) {
+ uint sym = treesym[i];
+
+ dsize += clen[sym];
+ if (sym >= 16) {
+ i++;
+ dsize += treesym[i];
+ i++;
+ }
+ }
+ /* block data */
+ for (i = 0; i < dynlen; i++) {
+ ushort sym = getsym(s, i);
+
+ dsize += llen[sym];
+ if (sym > Nlit) {
+ i++; /* extra nbits */
+ dsize += getsym(s, i);
+ i++; /* extra bits */
+ i++; /* dist sym */
+ dsize += dlen[getsym(s, i)];
+ i++; /* extra nbits */
+ dsize += getsym(s, i);
+ i++; /* extra bits */
+ }
+ }
+ /* EOB */
+ dsize += llen[256];
+
+ /* fixed block.. TODO */
+ fsize = 3;
+ /* The actual block data */
+ for (i = 0; i < fixlen; i++) {
+ uint sym = getsym(s, i);
+
+ fsize += fixedllen[sym];
+ if (sym > Nlit) {
+ i++; /* extra nbits */
+ fsize += getsym(s, i);
+ i++; /* extra bits */
+ i++; /* dist sym */
+ fsize += fixeddlen[getsym(s, i)];
+ i++; /* extra nbits */
+ fsize += getsym(s, i);
+ i++; /* extra bits */
+ }
+ }
+ /* EOB */
+ fsize += fixedllen[256];
+
+ dynamic = (long long)fsize * dynlen > (long long)dsize * fixlen;
+ blocklen = dynamic ? dlen : fixlen;
+ }
+
+ /* transmit the block */
+
+ /* 3-bit block header */
+ bfinal = s->lastblock ? 1 : 0;
+ btype = dynamic ? 2 : 1;
+ outbits(s, bfinal, 1);
+ outbits(s, btype, 2);
+
+ if (dynamic) {
+ outbits(s, nlit - 257, 5);
+ outbits(s, ndist - 1, 5);
+ outbits(s, nclen - 4, 4);
+
+ /* Code lengths for the auxiliary tree */
+ for (i = 0; i < nclen; i++)
+ outbits(s, codelen[i], 3);
+
+ /* Code lengths for the literal/length and distance trees */
+ for (i = 0; i < ntreesym; i++)
+ writesym(s, treesym[i], ht);
+ }
+
+ /* Output the actual symbols from the buffer */
+ for (i = 0; i < blocklen; i++)
+ writesym(s, getsym(s, i), ht);
+
+ /* Output the end-of-data symbol */
+ writesym(s, 256, ht);
+
+ s->symstart = (s->symstart + blocklen) % SymSize;
+ s->symlen -= blocklen;
+}
+
+/* rounded 8 * log2(n) */
+static int log2_8(uint n) {
+ int r = 31*8;
+
+ /* 8 * int log2() */
+ if (n < 1U<<16) n <<= 16, r -= 16*8;
+ if (n < 1U<<24) n <<= 8, r -= 8*8;
+ if (n < 1U<<28) n <<= 4, r -= 4*8;
+ if (n < 1U<<30) n <<= 2, r -= 2*8;
+ if (n < 1U<<31) n <<= 1, r -= 1*8;
+
+ /*
+ * result is in [r,r+8), to determine the bottom 3 digits:
+ * thresholds are 1<<31 times an odd power of 2^(1/16)
+ */
+ if (n <= 0xAD583EEAU) {
+ if (n <= 0x91C3D373U)
+ r += (n <= 0x85AAC367U ? 0 : 1);
+ else
+ r += (n <= 0x9EF53260U ? 2 : 3);
+ } else {
+ if (n <= 0xCE248C15U)
+ r += (n <= 0xBD08A39FU ? 4 : 5);
+ else
+ r += (n <= 0xE0CCDEECU ? 6 : n <= 0xF5257D15L ? 7 : 8);
+ }
+ return r;
+}
+
+static void chooseblock(State *s) {
+ int lfreq[Nlitlen], dfreq[Ndist];
+ int i, len, bestlen, longestlen = 0;
+ int ltotal, dtotal;
+ int bestvfm;
+
+ memset(lfreq, 0, sizeof(lfreq));
+ memset(dfreq, 0, sizeof(dfreq));
+ lfreq[256] = 1; /* we're bound to need one EOB */
+ ltotal = 1;
+ dtotal = 0;
+
+ /*
+ * Iterate over all possible block lengths, computing the
+ * entropic coding approximation to the final length at every
+ * stage. We divide the result by the number of symbols
+ * encoded, to determine the `value for money' (overall
+ * bits-per-symbol count) of a block of that length.
+ */
+ bestlen = -1;
+ bestvfm = 0;
+
+ len = 300 * 8; /* very approximate size of the Huffman trees */
+
+ for (i = 0; i < s->symlen; i++) {
+ ushort sym = getsym(s, i);
+
+ if (i > 0 && sym < Nlit) {
+ /*
+ * This is a viable point at which to end the block.
+ * Compute the value for money.
+ */
+ int vfm = i * 32768 / len; /* symbols encoded per bit */
+
+ if (bestlen < 0 || vfm > bestvfm) {
+ bestlen = i;
+ bestvfm = vfm;
+ }
+
+ longestlen = i;
+ }
+
+ /*
+ * Increment the occurrence counter for this symbol, if
+ * it's in one of the Huffman alphabets and isn't extra
+ * bits.
+ */
+ len += lfreq[sym] * approxlog2(lfreq[sym]);
+ len -= ltotal * approxlog2(ltotal);
+ lfreq[sym]++;
+ ltotal++;
+ len -= lfreq[sym] * approxlog2(lfreq[sym]);
+ len += ltotal * approxlog2(ltotal);
+ if (sym > Nlit) {
+ i++;
+ sym = getsym(s, i);
+ len += 8 * sym;
+ i++;
+ i++;
+ sym = getsym(s, i);
+ len += dfreq[sym] * approxlog2(dfreq[sym]);
+ len -= dtotal * approxlog2(dtotal);
+ dfreq[sym]++;
+ dtotal++;
+ len -= dfreq[sym] * approxlog2(dfreq[sym]);
+ len += dtotal * approxlog2(dtotal);
+ i++;
+ sym = getsym(s, i);
+ len += 8 * sym;
+ i++;
+ }
+ }
+ block(s, bestlen, longestlen);
+}
+
+static int bisect(ushort *base, int len, int n) {
+ int lo = 0;
+ int hi = len;
+ int k;
+
+ while (lo < hi) {
+ k = (lo + hi) / 2;
+ if (n < base[k])
+ hi = k;
+ else
+ lo = k + 1;
+ }
+ return lo - 1;
+}
+
+/* place a symbol into the symbuf */
+static void literal(State *s, ushort lit) {
+ if (s->symlen == SymSize)
+ chooseblock(s);
+ putsym(s, lit);
+}
+
+static void match(State *s, ushort dist, ushort len) {
+ if (s->symlen + 5 >= SymSize)
+ chooseblock(s);
+ while (len > 0) {
+ int n;
+ int i;
+
+ /* match length can be 3..258 */
+ n = len > 260 ? 258 : len <= 258 ? len : len - 3;
+ len -= n;
+
+ i = bisect(lenbase, Nlen, n);
+ /* len symbol */
+ putsym(s, Nlit + i + 1);
+ /* len extra */
+ putsym(s, lenbits[i]);
+ putsym(s, n - lenbase[i]);
+
+ i = bisect(distbase, Ndist, dist);
+ /* dist symbol */
+ putsym(s, i);
+ /* dist extra */
+ putsym(s, distbits[i]);
+ putsym(s, dist - distbase[i]);
+ }
+}
diff --git a/inflate.c b/inflate.c
@@ -84,7 +84,7 @@ typedef struct {
Huff dhuff; /* dynamic distance huffman code tree */
} State;
-/* TODO: these globals are initialized in a lazy way (not thread safe) */
+/* TODO: globals.. initialization is not thread safe */
static Huff lhuff; /* fixed lit/len huffman code tree */
static Huff dhuff; /* fixed distance huffman code tree */
@@ -329,6 +329,7 @@ static uint decode_symbol(State *s, Huff *huff) {
nbits += 8;
} while (nbits < huffbits);
}
+ /* decode bits */
entry = huff->table[bits & mask];
if (entry.len > 0) {
s->bits = bits >> entry.len;
