123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359 |
- #include <u.h>
- #include <libc.h>
- #include <flate.h>
- typedef struct Chain Chain;
- typedef struct Chains Chains;
- typedef struct Dyncode Dyncode;
- typedef struct Huff Huff;
- typedef struct LZblock LZblock;
- typedef struct LZstate LZstate;
- enum
- {
- /*
- * deflate format paramaters
- */
- DeflateUnc = 0, /* uncompressed block */
- DeflateFix = 1, /* fixed huffman codes */
- DeflateDyn = 2, /* dynamic huffman codes */
- 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 */
- EstLitBits = 8,
- EstLenBits = 4,
- EstOffBits = 5,
- };
- /*
- * 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);
- static int mkprecode(Huff*, ulong *, int, int, ulong*);
- static void nextchain(Chains*, int);
- static void leafsort(ulong*, ushort*, 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];
- /* litlen code words LenStart-285 extra bits */
- static int litlenbase[Nlitlen-LenStart];
- static int litlenextra[Nlitlen-LenStart] =
- {
- /* 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
- };
- /* offset code word extra bits */
- static int offbase[Noff];
- static int offextra[] =
- {
- 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,
- };
- /* 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
- };
- /* static huffman tables */
- static Huff litlentab[Nlitlen];
- static Huff offtab[Noff];
- static Huff hofftab[Noff];
- /* bit reversal for brain dead endian swap in huffman codes */
- static uchar revtab[256];
- static ulong nlits;
- static ulong nmatches;
- int
- deflateinit(void)
- {
- ulong bitcount[MaxHuffBits];
- int i, j, ci, n;
- /* byte reverse table */
- for(i=0; i<256; i++)
- for(j=0; j<8; j++)
- if(i & (1<<j))
- revtab[i] |= 0x80 >> j;
- /* static Litlen bit lengths */
- for(i=0; i<144; i++)
- litlentab[i].bits = 8;
- for(i=144; i<256; i++)
- litlentab[i].bits = 9;
- for(i=256; i<280; i++)
- litlentab[i].bits = 7;
- for(i=280; i<Nlitlen; i++)
- litlentab[i].bits = 8;
- memset(bitcount, 0, sizeof(bitcount));
- bitcount[8] += 144 - 0;
- bitcount[9] += 256 - 144;
- bitcount[7] += 280 - 256;
- bitcount[8] += Nlitlen - 280;
- if(!hufftabinit(litlentab, Nlitlen, bitcount, 9))
- return FlateInternal;
- /* static offset bit lengths */
- for(i = 0; i < Noff; i++)
- offtab[i].bits = 5;
- memset(bitcount, 0, sizeof(bitcount));
- bitcount[5] = Noff;
- if(!hufftabinit(offtab, Noff, bitcount, 5))
- return FlateInternal;
- bitcount[0] = 0;
- bitcount[1] = 0;
- if(!mkgzprecode(hofftab, bitcount, 2, MaxHuffBits))
- return FlateInternal;
- /* 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 void
- deflatereset(LZstate *lz, int level, int debug)
- {
- memset(lz->nexts, 0, sizeof lz->nexts);
- memset(lz->hash, 0, sizeof lz->hash);
- lz->totr = 0;
- lz->totw = 0;
- lz->pos = 0;
- lz->avail = 0;
- lz->out = lz->obuf;
- lz->eout = &lz->obuf[DeflateOut];
- lz->prevlen = MinMatch - 1;
- lz->prevoff = 0;
- lz->now = MaxOff + 1;
- lz->dot = lz->now;
- lz->bits = 0;
- lz->nbits = 0;
- lz->maxcheck = (1 << level);
- lz->maxcheck -= lz->maxcheck >> 2;
- if(lz->maxcheck < 2)
- lz->maxcheck = 2;
- else if(lz->maxcheck > 1024)
- lz->maxcheck = 1024;
- lz->debug = debug;
- }
- int
- deflate(void *wr, int (*w)(void*, void*, int), void *rr, int (*r)(void*, void*, int), int level, int debug)
- {
- LZstate *lz;
- LZblock *lzb;
- int ok;
- lz = malloc(sizeof *lz + sizeof *lzb);
- if(lz == nil)
- return FlateNoMem;
- lzb = (LZblock*)&lz[1];
- deflatereset(lz, level, debug);
- lz->w = w;
- lz->wr = wr;
- lz->wbad = 0;
- lz->rbad = 0;
- lz->eof = 0;
- ok = FlateOk;
- while(!lz->eof || lz->avail){
- ok = deflateb(lz, lzb, rr, r);
- if(ok != FlateOk)
- break;
- }
- if(ok == FlateOk && lz->rbad)
- ok = FlateInputFail;
- if(ok == FlateOk && lz->wbad)
- ok = FlateOutputFail;
- free(lz);
- return ok;
- }
- 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;
- memset(lzb->litlencount, 0, sizeof lzb->litlencount);
- memset(lzb->offcount, 0, sizeof lzb->offcount);
- lzb->litlencount[DeflateEob]++;
- lzb->bytes = 0;
- lzb->eparse = lzb->parse;
- lzb->lastv = 0;
- lzb->excost = 0;
- 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;
- if(!mkgzprecode(dlitlentab, lzb->litlencount, Nlitlen, MaxHuffBits)
- || !mkgzprecode(dofftab, lzb->offcount, Noff, MaxHuffBits))
- return FlateInternal;
- ndyn = huffcodes(&dyncode, dlitlentab, dofftab);
- if(ndyn < 0)
- return FlateInternal;
- ndyn += bitcost(dlitlentab, lzb->litlencount, Nlitlen)
- + bitcost(dofftab, lzb->offcount, Noff)
- + lzb->excost;
- memset(litcount, 0, sizeof litcount);
- nslop = nunc;
- if(nslop > &lz->hist[HistSize] - slop)
- nslop = &lz->hist[HistSize] - slop;
- for(i = 0; i < nslop; i++)
- litcount[slop[i]]++;
- hslop = &lz->hist[HistSlop - nslop];
- for(; i < nunc; i++)
- litcount[hslop[i]]++;
- litcount[DeflateEob]++;
- if(!mkgzprecode(hlitlentab, litcount, Nlitlen, MaxHuffBits))
- return FlateInternal;
- nhuff = huffcodes(&hdyncode, hlitlentab, hofftab);
- if(nhuff < 0)
- return FlateInternal;
- nhuff += bitcost(hlitlentab, litcount, Nlitlen);
- nfix = bitcost(litlentab, lzb->litlencount, Nlitlen)
- + bitcost(offtab, lzb->offcount, Noff)
- + lzb->excost;
- lzput(lz, lz->eof && !lz->avail, 1);
- if(lz->debug){
- fprint(2, "block: bytes=%lud entries=%ld extra bits=%d\n\tuncompressed=%lud fixed=%lud dynamic=%lud huffman=%lud\n",
- nunc, lzb->eparse - lzb->parse, lzb->excost, (nunc + 4) * 8, nfix, ndyn, nhuff);
- fprint(2, "\tnlit=%lud matches=%lud eof=%d\n", nlits, nmatches, lz->eof && !lz->avail);
- }
- if((nunc + 4) * 8 < ndyn && (nunc + 4) * 8 < nfix && (nunc + 4) * 8 < nhuff){
- lzput(lz, DeflateUnc, 2);
- lzflushbits(lz);
- lzput(lz, nunc & 0xff, 8);
- lzput(lz, (nunc >> 8) & 0xff, 8);
- lzput(lz, ~nunc & 0xff, 8);
- lzput(lz, (~nunc >> 8) & 0xff, 8);
- lzflush(lz);
- lzwrite(lz, slop, nslop);
- lzwrite(lz, &lz->hist[HistSlop], nunc - nslop);
- }else if(ndyn < nfix && ndyn < nhuff){
- lzput(lz, DeflateDyn, 2);
- wrdyncode(lz, &dyncode);
- wrblock(lz, slop - lz->hist, lzb->parse, lzb->eparse, dlitlentab, dofftab);
- lzput(lz, dlitlentab[DeflateEob].encode, dlitlentab[DeflateEob].bits);
- }else if(nhuff < nfix){
- lzput(lz, DeflateDyn, 2);
- wrdyncode(lz, &hdyncode);
- m = 0;
- for(i = nunc; i > MaxLitRun; i -= MaxLitRun)
- lzb->parse[m++] = MaxLitRun;
- lzb->parse[m++] = i;
- wrblock(lz, slop - lz->hist, lzb->parse, lzb->parse + m, hlitlentab, hofftab);
- lzput(lz, hlitlentab[DeflateEob].encode, hlitlentab[DeflateEob].bits);
- }else{
- lzput(lz, DeflateFix, 2);
- wrblock(lz, slop - lz->hist, lzb->parse, lzb->eparse, litlentab, offtab);
- lzput(lz, litlentab[DeflateEob].encode, litlentab[DeflateEob].bits);
- }
- if(lz->eof && !lz->avail){
- lzflushbits(lz);
- lzflush(lz);
- }
- return FlateOk;
- }
- static void
- lzwrite(LZstate *lz, void *buf, int n)
- {
- int nw;
- if(n && lz->w){
- nw = (*lz->w)(lz->wr, buf, n);
- if(nw != n){
- lz->w = nil;
- lz->wbad = 1;
- }else
- lz->totw += n;
- }
- }
- static void
- lzflush(LZstate *lz)
- {
- lzwrite(lz, lz->obuf, lz->out - lz->obuf);
- lz->out = lz->obuf;
- }
- static void
- lzput(LZstate *lz, ulong bits, int nbits)
- {
- bits = (bits << lz->nbits) | lz->bits;
- for(nbits += lz->nbits; nbits >= 8; nbits -= 8){
- *lz->out++ = bits;
- if(lz->out == lz->eout)
- lzflush(lz);
- bits >>= 8;
- }
- lz->bits = bits;
- lz->nbits = nbits;
- }
- static void
- lzflushbits(LZstate *lz)
- {
- if(lz->nbits)
- lzput(lz, 0, 8 - (lz->nbits & 7));
- }
- /*
- * 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;
- if(out->debug > 2){
- for(off = soff; off < eoff; ){
- offset = *off++;
- run = offset & MaxLitRun;
- if(run){
- for(i = 0; i < run; i++){
- lit = out->hist[litoff & (HistBlock - 1)];
- litoff++;
- fprint(2, "\tlit %.2ux %c\n", lit, lit);
- }
- if(!(offset & LenFlag))
- continue;
- len = offset >> LenShift;
- offset = *off++;
- }else if(offset & LenFlag){
- len = offset >> LenShift;
- offset = *off++;
- }else{
- len = 0;
- offset >>= LenShift;
- }
- litoff += len + MinMatch;
- fprint(2, "\t<%d, %d>\n", offset + 1, len + MinMatch);
- }
- }
- for(off = soff; off < eoff; ){
- offset = *off++;
- run = offset & MaxLitRun;
- if(run){
- for(i = 0; i < run; i++){
- lit = out->hist[litoff & (HistBlock - 1)];
- litoff++;
- lzput(out, litlentab[lit].encode, litlentab[lit].bits);
- }
- if(!(offset & LenFlag))
- continue;
- len = offset >> LenShift;
- offset = *off++;
- }else if(offset & LenFlag){
- len = offset >> LenShift;
- offset = *off++;
- }else{
- len = 0;
- offset >>= LenShift;
- }
- litoff += len + MinMatch;
- c = lencode[len];
- lzput(out, litlentab[c].encode, litlentab[c].bits);
- c -= LenStart;
- if(litlenextra[c])
- lzput(out, len - litlenbase[c], litlenextra[c]);
- if(offset < MaxOffCode)
- c = offcode[offset];
- else
- c = bigoffcode[offset >> 7];
- lzput(out, offtab[c].encode, offtab[c].bits);
- if(offextra[c])
- lzput(out, offset - offbase[c], offextra[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;
- litlencount = lzb->litlencount;
- offcount = lzb->offcount;
- nexts = lz->nexts;
- hash = lz->hash;
- now = lz->now;
- 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));
- cont = (s[0] << 16) | (s[1] << 8) | s[2];
- h = hashit(cont);
- prevoff = 0;
- for(then = hash[h]; ; then = nexts[then & (MaxOff-1)]){
- v = (ushort)(now - then);
- if(v <= prevoff || v >= (MinMatch-1) - i)
- break;
- prevoff = v;
- }
- if(then == (ushort)m)
- continue;
- nexts[m & (MaxOff-1)] = hash[h];
- hash[h] = m;
- }
- for(i = 0; i < n; i++)
- cont = (cont << 8) | p[i];
- /*
- * 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;
- }
- h = hashit(cont);
- runlen = lzmatch(now, hash[h], p, es, nexts, lz->hist, prevlen, lz->maxcheck, &m);
- /*
- * 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++;
- }
- prevoff = m;
- if(runlen < maxdefer){
- prevlen = runlen;
- runlen = 1;
- }else{
- n = runlen - 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];
- 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--;
- lzb->excost += excost;
- lzb->eparse = parse;
- lzb->lastv = v;
- lz->now = now;
- lz->prevlen = prevlen;
- lz->prevoff = prevoff;
- return p - &lz->hist[lz->pos];
- }
- /*
- * 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;
- codetab = dc->codetab;
- codes = dc->codes;
- codeaux = dc->codeaux;
- /*
- * trim the sizes of the tables
- */
- for(nlit = Nlitlen; nlit > 257 && littab[nlit-1].bits == 0; nlit--)
- ;
- for(noff = Noff; noff > 1 && offtab[noff-1].bits == 0; noff--)
- ;
- /*
- * make the code-length code
- */
- for(i = 0; i < nlit; i++)
- codes[i] = littab[i].bits;
- for(i = 0; i < noff; i++)
- codes[i + nlit] = offtab[i].bits;
- /*
- * run-length compress the code-length code
- */
- excost = 0;
- c = 0;
- ncode = nlit+noff;
- for(i = 0; i < ncode; ){
- n = i + 1;
- v = codes[i];
- while(n < ncode && v == codes[n])
- n++;
- n -= i;
- i += n;
- if(v == 0){
- while(n >= 11){
- m = n;
- if(m > 138)
- m = 138;
- codes[c] = 18;
- codeaux[c++] = m - 11;
- n -= m;
- excost += 7;
- }
- if(n >= 3){
- codes[c] = 17;
- codeaux[c++] = n - 3;
- n = 0;
- excost += 3;
- }
- }
- while(n--){
- codes[c++] = v;
- while(n >= 3){
- m = n;
- if(m > 6)
- m = 6;
- codes[c] = 16;
- codeaux[c++] = m - 3;
- n -= m;
- excost += 3;
- }
- }
- }
- memset(codecount, 0, sizeof codecount);
- for(i = 0; i < c; i++)
- codecount[codes[i]]++;
- if(!mkgzprecode(codetab, codecount, Nclen, 8))
- return -1;
- for(nclen = Nclen; nclen > 4 && codetab[clenorder[nclen-1]].bits == 0; nclen--)
- ;
- dc->nlit = nlit;
- dc->noff = noff;
- dc->nclen = nclen;
- dc->ncode = c;
- return 5 + 5 + 4 + nclen * 3 + bitcost(codetab, codecount, Nclen) + excost;
- }
- static void
- wrdyncode(LZstate *out, Dyncode *dc)
- {
- Huff *codetab;
- uchar *codes, *codeaux;
- int i, v, c;
- /*
- * write out header, then code length code lengths,
- * and code lengths
- */
- lzput(out, dc->nlit-257, 5);
- lzput(out, dc->noff-1, 5);
- lzput(out, dc->nclen-4, 4);
- codetab = dc->codetab;
- for(i = 0; i < dc->nclen; i++)
- lzput(out, codetab[clenorder[i]].bits, 3);
- codes = dc->codes;
- codeaux = dc->codeaux;
- c = dc->ncode;
- for(i = 0; i < c; i++){
- v = codes[i];
- lzput(out, codetab[v].encode, codetab[v].bits);
- if(v >= 16){
- if(v == 16)
- lzput(out, codeaux[i], 2);
- else if(v == 17)
- lzput(out, codeaux[i], 3);
- else /* v == 18 */
- lzput(out, codeaux[i], 7);
- }
- }
- }
- static int
- bitcost(Huff *tab, ulong *count, int n)
- {
- ulong tot;
- int i;
- tot = 0;
- for(i = 0; i < n; i++)
- tot += count[i] * tab[i].bits;
- return tot;
- }
- static int
- mkgzprecode(Huff *tab, ulong *count, int n, int maxbits)
- {
- ulong bitcount[MaxHuffBits];
- int i, nbits;
- nbits = mkprecode(tab, count, n, maxbits, bitcount);
- for(i = 0; i < n; i++){
- if(tab[i].bits == -1)
- tab[i].bits = 0;
- else if(tab[i].bits == 0){
- if(nbits != 0 || bitcount[0] != 1)
- return 0;
- bitcount[1] = 1;
- bitcount[0] = 0;
- nbits = 1;
- tab[i].bits = 1;
- }
- }
- if(bitcount[0] != 0)
- return 0;
- return hufftabinit(tab, n, bitcount, nbits);
- }
- static int
- hufftabinit(Huff *tab, int n, ulong *bitcount, int nbits)
- {
- ulong code, nc[MaxHuffBits];
- int i, bits;
- code = 0;
- for(bits = 1; bits <= nbits; bits++){
- code = (code + bitcount[bits-1]) << 1;
- nc[bits] = code;
- }
- for(i = 0; i < n; i++){
- bits = tab[i].bits;
- if(bits){
- code = nc[bits]++ << (16 - bits);
- if(code & ~0xffff)
- return 0;
- tab[i].encode = revtab[code >> 8] | (revtab[code & 0xff] << 8);
- }
- }
- return 1;
- }
- /*
- * 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;
- /*
- * initialize chains for each list
- */
- c = &cs.chains[0];
- c->count = cs.leafcount[0];
- c->leaf = 1;
- c->col = cs.col;
- c->up = nil;
- c->gen = 0;
- cs.chains[1] = cs.chains[0];
- cs.chains[1].leaf = 2;
- cs.chains[1].count = cs.leafcount[1];
- for(i = 0; i < maxbits-1; i++){
- cs.lists[i * 2] = &cs.chains[0];
- cs.lists[i * 2 + 1] = &cs.chains[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;
- oc = cs->lists[list + 1];
- cs->lists[list] = oc;
- if(oc == nil)
- return;
- /*
- * 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;
- j = n/6;
- pi = a + j; /* 1/6 */
- j += j;
- pj = pi + j; /* 1/2 */
- pk = pj + j; /* 5/6 */
- if(c[pi] < c[pj]){
- if(c[pi] < c[pk]){
- if(c[pj] < c[pk])
- return pj;
- return pk;
- }
- return pi;
- }
- if(c[pj] < c[pk]){
- if(c[pi] < c[pk])
- return pi;
- return pk;
- }
- return pj;
- }
- static void
- leafsort(ulong *leafcount, ushort *leafmap, int a, int n)
- {
- ulong t;
- int j, pi, pj, pn;
- while(n > 1){
- if(n > 10){
- pi = pivot(leafcount, a, n);
- }else
- pi = a + (n>>1);
- t = leafcount[pi];
- leafcount[pi] = leafcount[a];
- leafcount[a] = t;
- t = leafmap[pi];
- leafmap[pi] = leafmap[a];
- leafmap[a] = t;
- pi = a;
- pn = a + n;
- pj = pn;
- for(;;){
- do
- pi++;
- while(pi < pn && (leafcount[pi] < leafcount[a] || leafcount[pi] == leafcount[a] && leafmap[pi] > leafmap[a]));
- do
- pj--;
- while(pj > a && (leafcount[pj] > leafcount[a] || leafcount[pj] == leafcount[a] && leafmap[pj] < leafmap[a]));
- if(pj < pi)
- break;
- t = leafcount[pi];
- leafcount[pi] = leafcount[pj];
- leafcount[pj] = t;
- t = leafmap[pi];
- leafmap[pi] = leafmap[pj];
- leafmap[pj] = t;
- }
- t = leafcount[a];
- leafcount[a] = leafcount[pj];
- leafcount[pj] = t;
- t = leafmap[a];
- leafmap[a] = leafmap[pj];
- leafmap[pj] = t;
- j = pj - a;
- n = n-j-1;
- if(j >= n){
- leafsort(leafcount, leafmap, a, j);
- a += j+1;
- }else{
- leafsort(leafcount, leafmap, a + (j+1), n);
- n = j;
- }
- }
- }
|