DeflateEob = 256, /* end of block code in lit/len book */
DeflateMaxBlock = 64*1024-1, /* maximum size of uncompressed block */
DeflateMaxExp = 10, /* maximum expansion for a block */
LenStart = 257, /* start of length codes in litlen */
Nlitlen = 288, /* number of litlen codes */
Noff = 30, /* number of offset codes */
Nclen = 19, /* number of codelen codes */
MaxOff = 32*1024,
MinMatch = 3, /* shortest match possible */
MaxMatch = 258, /* longest match possible */
/*
* huffman code paramaters
*/
MaxLeaf = Nlitlen,
MaxHuffBits = 16, /* max bits in a huffman code */
ChainMem = 2 * (MaxHuffBits - 1) * MaxHuffBits,
/*
* coding of the lz parse
*/
LenFlag = 1 << 3,
LenShift = 4, /* leaves enough space for MinMatchMaxOff */
MaxLitRun = LenFlag - 1,
/*
* internal lz paramaters
*/
DeflateOut = 4096, /* output buffer size */
BlockSize = 8192, /* attempted input read quanta */
DeflateBlock = DeflateMaxBlock & ~(BlockSize - 1),
MinMatchMaxOff = 4096, /* max profitable offset for small match;
* assumes 8 bits for len, 5+10 for offset
* DONT CHANGE WITHOUT CHANGING LZPARSE CONSTANTS
*/
HistSlop = 512, /* must be at lead MaxMatch */
HistBlock = 64*1024,
HistSize = HistBlock + HistSlop,
HashLog = 13,
HashSize = 1<<HashLog,
MaxOffCode = 256, /* biggest offset looked up in direct table */
/*
* knuth vol. 3 multiplicative hashing
* each byte x chosen according to rules
* 1/4 < x < 3/10, 1/3 x < < 3/7, 4/7 < x < 2/3, 7/10 < x < 3/4
* with reasonable spread between the bytes & their complements
*
* the 3 byte value appears to be as almost good as the 4 byte value,
* and might be faster on some machines
*/
/*
#define hashit(c) (((ulong)(c) * 0x6b43a9) >> (24 - HashLog))
*/
#define hashit(c) ((((ulong)(c) & 0xffffff) * 0x6b43a9b5) >> (32 - HashLog))
/*
* lempel-ziv style compression state
*/
struct LZstate
{
uchar hist[HistSize];
ulong pos; /* current location in history buffer */
ulong avail; /* data available after pos */
int eof;
ushort hash[HashSize]; /* hash chains */
ushort nexts[MaxOff];
int now; /* pos in hash chains */
int dot; /* dawn of time in history */
int prevlen; /* lazy matching state */
int prevoff;
int maxcheck; /* compressor tuning */
uchar obuf[DeflateOut];
uchar *out; /* current position in the output buffer */
uchar *eout;
ulong bits; /* bit shift register */
int nbits;
int rbad; /* got an error reading the buffer */
int wbad; /* got an error writing the buffer */
int (*w)(void*, void*, int);
void *wr;
ulong totr; /* total input size */
ulong totw; /* total output size */
int debug;
};
struct LZblock
{
ushort parse[DeflateMaxBlock / 2 + 1];
int lastv; /* value being constucted for parse */
ulong litlencount[Nlitlen];
ulong offcount[Noff];
ushort *eparse; /* limit for parse table */
int bytes; /* consumed from the input */
int excost; /* cost of encoding extra len & off bits */
};
/*
* huffman code table
*/
struct Huff
{
short bits; /* length of the code */
ushort encode; /* the code */
};
/*
* encoding of dynamic huffman trees
*/
struct Dyncode
{
int nlit;
int noff;
int nclen;
int ncode;
Huff codetab[Nclen];
uchar codes[Nlitlen+Noff];
uchar codeaux[Nlitlen+Noff];
};
static int deflateb(LZstate *lz, LZblock *lzb, void *rr, int (*r)(void*, void*, int));
static int lzcomp(LZstate*, LZblock*, uchar*, ushort*, int finish);
static void wrblock(LZstate*, int, ushort*, ushort*, Huff*, Huff*);
static int bitcost(Huff*, ulong*, int);
static int huffcodes(Dyncode*, Huff*, Huff*);
static void wrdyncode(LZstate*, Dyncode*);
static void lzput(LZstate*, ulong bits, int nbits);
static void lzflushbits(LZstate*);
static void lzflush(LZstate *lz);
static void lzwrite(LZstate *lz, void *buf, int n);
static int hufftabinit(Huff*, int, ulong*, int);
static int mkgzprecode(Huff*, ulong *, int, int);
/* conversion from len to code word */
static int lencode[MaxMatch];
/*
* conversion from off to code word
* off <= MaxOffCode ? offcode[off] : bigoffcode[off >> 7]
*/
static int offcode[MaxOffCode];
static int bigoffcode[256];
/* conversion tables for lens & offs to codes */
ci = 0;
for(i = LenStart; i < 286; i++){
n = ci + (1 << litlenextra[i - LenStart]);
litlenbase[i - LenStart] = ci;
for(; ci < n; ci++)
lencode[ci] = i;
}
/* patch up special case for len MaxMatch */
lencode[MaxMatch-MinMatch] = 285;
litlenbase[285-LenStart] = MaxMatch-MinMatch;
ci = 0;
for(i = 0; i < 16; i++){
n = ci + (1 << offextra[i]);
offbase[i] = ci;
for(; ci < n; ci++)
offcode[ci] = i;
}
ci = ci >> 7;
for(; i < 30; i++){
n = ci + (1 << (offextra[i] - 7));
offbase[i] = ci << 7;
for(; ci < n; ci++)
bigoffcode[ci] = i;
}
return FlateOk;
}
static int
deflateb(LZstate *lz, LZblock *lzb, void *rr, int (*r)(void*, void*, int))
{
Dyncode dyncode, hdyncode;
Huff dlitlentab[Nlitlen], dofftab[Noff], hlitlentab[Nlitlen];
ulong litcount[Nlitlen];
long nunc, ndyn, nfix, nhuff;
uchar *slop, *hslop;
ulong ep;
int i, n, m, mm, nslop;
slop = &lz->hist[lz->pos];
n = lz->avail;
while(n < DeflateBlock && (!lz->eof || lz->avail)){
/*
* fill the buffer as much as possible,
* while leaving room for MaxOff history behind lz->pos,
* and not reading more than we can handle.
*
* make sure we read at least HistSlop bytes.
*/
if(!lz->eof){
ep = lz->pos + lz->avail;
if(ep >= HistBlock)
ep -= HistBlock;
m = HistBlock - MaxOff - lz->avail;
if(m > HistBlock - n)
m = HistBlock - n;
if(m > (HistBlock + HistSlop) - ep)
m = (HistBlock + HistSlop) - ep;
if(m & ~(BlockSize - 1))
m &= ~(BlockSize - 1);
/*
* be nice to the caller: stop reads that are too small.
* can only get here when we've already filled the buffer some
*/
if(m < HistSlop){
if(!m || !lzb->bytes)
return FlateInternal;
break;
}
mm = (*r)(rr, &lz->hist[ep], m);
if(mm > 0){
/*
* wrap data to end if we're read it from the beginning
* this way, we don't have to wrap searches.
*
* wrap reads past the end to the beginning.
* this way, we can guarantee minimum size reads.
*/
if(ep < HistSlop)
memmove(&lz->hist[ep + HistBlock], &lz->hist[ep], HistSlop - ep);
else if(ep + mm > HistBlock)
memmove(&lz->hist[0], &lz->hist[HistBlock], ep + mm - HistBlock);
lz->totr += mm;
n += mm;
lz->avail += mm;
}else{
if(mm < 0)
lz->rbad = 1;
lz->eof = 1;
}
}
ep = lz->pos + lz->avail;
if(ep > HistSize)
ep = HistSize;
if(lzb->bytes + ep - lz->pos > DeflateMaxBlock)
ep = lz->pos + DeflateMaxBlock - lzb->bytes;
m = lzcomp(lz, lzb, &lz->hist[ep], lzb->eparse, lz->eof);
lzb->bytes += m;
lz->pos = (lz->pos + m) & (HistBlock - 1);
lz->avail -= m;
}
if(lzb->lastv)
*lzb->eparse++ = lzb->lastv;
if(lzb->eparse > lzb->parse + nelem(lzb->parse))
return FlateInternal;
nunc = lzb->bytes;
/*
* write out a block of n samples,
* given lz encoding and counts for huffman tables
*/
static void
wrblock(LZstate *out, int litoff, ushort *soff, ushort *eoff, Huff *litlentab, Huff *offtab)
{
ushort *off;
int i, run, offset, lit, len, c;
/*
* look for the longest, closest string which matches
* the next prefix. the clever part here is looking for
* a string 1 longer than the previous best match.
*
* follows the recommendation of limiting number of chains
* which are checked. this appears to be the best heuristic.
*/
static int
lzmatch(int now, int then, uchar *p, uchar *es, ushort *nexts, uchar *hist, int runlen, int check, int *m)
{
uchar *s, *t;
int ml, off, last;
ml = check;
if(runlen >= 8)
check >>= 2;
*m = 0;
if(p + runlen >= es)
return runlen;
last = 0;
for(; check-- > 0; then = nexts[then & (MaxOff-1)]){
off = (ushort)(now - then);
if(off <= last || off > MaxOff)
break;
s = p + runlen;
t = hist + (((p - hist) - off) & (HistBlock-1));
t += runlen;
for(; s >= p; s--){
if(*s != *t)
goto matchloop;
t--;
}
/*
* we have a new best match.
* extend it to it's maximum length
*/
t += runlen + 2;
s += runlen + 2;
for(; s < es; s++){
if(*s != *t)
break;
t++;
}
runlen = s - p;
*m = off - 1;
if(s == es || runlen > ml)
break;
matchloop:;
last = off;
}
return runlen;
}
static int
lzcomp(LZstate *lz, LZblock *lzb, uchar *ep, ushort *parse, int finish)
{
ulong cont, excost, *litlencount, *offcount;
uchar *p, *q, *s, *es;
ushort *nexts, *hash;
int v, i, h, runlen, n, now, then, m, prevlen, prevoff, maxdefer;
p = &lz->hist[lz->pos];
if(lz->prevlen != MinMatch - 1)
p++;
/*
* hash in the links for any hanging link positions,
* and calculate the hash for the current position.
*/
n = MinMatch;
if(n > ep - p)
n = ep - p;
cont = 0;
for(i = 0; i < n - 1; i++){
m = now - ((MinMatch-1) - i);
if(m < lz->dot)
continue;
s = lz->hist + (((p - lz->hist) - (now - m)) & (HistBlock-1));
/*
* now must point to the index in the nexts array
* corresponding to p's position in the history
*/
prevlen = lz->prevlen;
prevoff = lz->prevoff;
maxdefer = lz->maxcheck >> 2;
excost = 0;
v = lzb->lastv;
for(;;){
es = p + MaxMatch;
if(es > ep){
if(!finish || p >= ep)
break;
es = ep;
}
/*
* back out of small matches too far in the past
*/
if(runlen == MinMatch && m >= MinMatchMaxOff){
runlen = MinMatch - 1;
m = 0;
}
/*
* record the encoding and increment counts for huffman trees
* if we get a match, defer selecting it until we check for
* a longer match at the next position.
*/
if(prevlen >= runlen && prevlen != MinMatch - 1){
/*
* old match at least as good; use that one
*/
n = prevlen - MinMatch;
if(v || n){
*parse++ = v | LenFlag | (n << LenShift);
*parse++ = prevoff;
}else
*parse++ = prevoff << LenShift;
v = 0;
n = lencode[n];
litlencount[n]++;
excost += litlenextra[n - LenStart];
if(prevoff < MaxOffCode)
n = offcode[prevoff];
else
n = bigoffcode[prevoff >> 7];
offcount[n]++;
excost += offextra[n];
runlen = prevlen - 1;
prevlen = MinMatch - 1;
nmatches++;
}else if(runlen == MinMatch - 1){
/*
* no match; just put out the literal
*/
if(++v == MaxLitRun){
*parse++ = v;
v = 0;
}
litlencount[*p]++;
nlits++;
runlen = 1;
}else{
if(prevlen != MinMatch - 1){
/*
* longer match now. output previous literal,
* update current match, and try again
*/
if(++v == MaxLitRun){
*parse++ = v;
v = 0;
}
litlencount[p[-1]]++;
nlits++;
}
n = lencode[n];
litlencount[n]++;
excost += litlenextra[n - LenStart];
if(prevoff < MaxOffCode)
n = offcode[prevoff];
else
n = bigoffcode[prevoff >> 7];
offcount[n]++;
excost += offextra[n];
prevlen = MinMatch - 1;
nmatches++;
}
}
/*
* update the hash for the newly matched data
* this is constructed so the link for the old
* match in this position must be at the end of a chain,
* and will expire when this match is added, ie it will
* never be examined by the match loop.
* add to the hash chain only if we have the real hash data.
*/
for(q = p + runlen; p != q; p++){
if(p + MinMatch <= ep){
h = hashit(cont);
nexts[now & (MaxOff-1)] = hash[h];
hash[h] = now;
if(p + MinMatch < ep)
cont = (cont << 8) | p[MinMatch];
}
now++;
}
}
/*
* we can just store away the lazy state and
* pick it up next time. the last block will have finish set
* so we won't have any pending matches
* however, we need to correct for how much we've encoded
*/
if(prevlen != MinMatch - 1)
p--;
/*
* make up the dynamic code tables, and return the number of bits
* needed to transmit them.
*/
static int
huffcodes(Dyncode *dc, Huff *littab, Huff *offtab)
{
Huff *codetab;
uchar *codes, *codeaux;
ulong codecount[Nclen], excost;
int i, n, m, v, c, nlit, noff, ncode, nclen;
/*
* this should be in a library
*/
struct Chain
{
ulong count; /* occurances of everything in the chain */
ushort leaf; /* leaves to the left of chain, or leaf value */
char col; /* ref count for collecting unused chains */
char gen; /* need to generate chains for next lower level */
Chain *up; /* Chain up in the lists */
};
struct Chains
{
Chain *lists[(MaxHuffBits - 1) * 2];
ulong leafcount[MaxLeaf]; /* sorted list of leaf counts */
ushort leafmap[MaxLeaf]; /* map to actual leaf number */
int nleaf; /* number of leaves */
Chain chains[ChainMem];
Chain *echains;
Chain *free;
char col;
int nlists;
};
/*
* fast, low space overhead algorithm for max depth huffman type codes
*
* J. Katajainen, A. Moffat and A. Turpin, "A fast and space-economical
* algorithm for length-limited coding," Proc. Intl. Symp. on Algorithms
* and Computation, Cairns, Australia, Dec. 1995, Lecture Notes in Computer
* Science, Vol 1004, J. Staples, P. Eades, N. Katoh, and A. Moffat, eds.,
* pp 12-21, Springer Verlag, New York, 1995.
*/
static int
mkprecode(Huff *tab, ulong *count, int n, int maxbits, ulong *bitcount)
{
Chains cs;
Chain *c;
int i, m, em, bits;
/*
* set up the sorted list of leaves
*/
m = 0;
for(i = 0; i < n; i++){
tab[i].bits = -1;
tab[i].encode = 0;
if(count[i] != 0){
cs.leafcount[m] = count[i];
cs.leafmap[m] = i;
m++;
}
}
if(m < 2){
if(m != 0){
tab[cs.leafmap[0]].bits = 0;
bitcount[0] = 1;
}else
bitcount[0] = 0;
return 0;
}
cs.nleaf = m;
leafsort(cs.leafcount, cs.leafmap, 0, m);
for(i = 0; i < m; i++)
cs.leafcount[i] = count[cs.leafmap[i]];
/*
* set up free list
*/
cs.free = &cs.chains[2];
cs.echains = &cs.chains[ChainMem];
cs.col = 1;
cs.nlists = 2 * (maxbits - 1);
m = 2 * m - 2;
for(i = 2; i < m; i++)
nextchain(&cs, cs.nlists - 2);
bits = 0;
bitcount[0] = cs.nleaf;
for(c = cs.lists[cs.nlists - 1]; c != nil; c = c->up){
m = c->leaf;
bitcount[bits++] -= m;
bitcount[bits] = m;
}
m = 0;
for(i = bits; i >= 0; i--)
for(em = m + bitcount[i]; m < em; m++)
tab[cs.leafmap[m]].bits = i;
return bits;
}
/*
* calculate the next chain on the list
* we can always toss out the old chain
*/
static void
nextchain(Chains *cs, int list)
{
Chain *c, *oc;
int i, nleaf, sumc;
/*
* make sure we have all chains needed to make sumc
* note it is possible to generate only one of these,
* use twice that value for sumc, and then generate
* the second if that preliminary sumc would be chosen.
* however, this appears to be slower on current tests
*/
if(oc->gen){
nextchain(cs, list - 2);
nextchain(cs, list - 2);
oc->gen = 0;
}
/*
* pick up the chain we're going to add;
* collect unused chains no free ones are left
*/
for(c = cs->free; ; c++){
if(c >= cs->echains){
cs->col++;
for(i = 0; i < cs->nlists; i++)
for(c = cs->lists[i]; c != nil; c = c->up)
c->col = cs->col;
c = cs->chains;
}
if(c->col != cs->col)
break;
}
/*
* pick the cheapest of
* 1) the next package from the previous list
* 2) the next leaf
*/
nleaf = oc->leaf;
sumc = 0;
if(list > 0 && cs->lists[list-1] != nil)
sumc = cs->lists[list-2]->count + cs->lists[list-1]->count;
if(sumc != 0 && (nleaf >= cs->nleaf || cs->leafcount[nleaf] > sumc)){
c->count = sumc;
c->leaf = oc->leaf;
c->up = cs->lists[list-1];
c->gen = 1;
}else if(nleaf >= cs->nleaf){
cs->lists[list + 1] = nil;
return;
}else{
c->leaf = nleaf + 1;
c->count = cs->leafcount[nleaf];
c->up = oc->up;
c->gen = 0;
}
cs->free = c + 1;
cs->lists[list + 1] = c;
c->col = cs->col;
}
static int
pivot(ulong *c, int a, int n)
{
int j, pi, pj, pk;
