5 typedef struct Huff Huff;
6 typedef struct Mtf Mtf;
7 typedef struct Decode Decode;
11 ZBase = 2, /* base of code to encode 0 runs */
12 LitBase = ZBase-1, /* base of literal values */
15 MaxLeaf = MaxLit+LitBase,
16 MaxHuffBits = 16, /* max bits in a huffman code */
17 MaxFlatbits = 5, /* max bits decoded in flat table */
20 CombSpace = 1 << CombLog, /* mtf speedup indices spacing */
21 CombMask = CombSpace - 1,
26 int maxcomb; /* index of last valid comb */
29 uchar comb[MaxLit / CombSpace + 1];
36 ulong flat[1<<MaxFlatbits];
37 ulong maxcode[MaxHuffBits];
38 ulong last[MaxHuffBits];
39 ulong decode[MaxLeaf];
53 uchar *src; /* input buffer */
54 uchar *smax; /* limit */
57 static void fatal(Decode *dec, char*);
59 static int hdec(Decode*);
60 static void recvtab(Decode*, Huff*, int, ushort*);
61 static ulong bitget(Decode*, int);
62 static int mtf(uchar*, int);
67 mtflistinit(Mtf *m, uchar *front, int n)
69 int last, me, f, i, comb;
75 * add all entries to free list
78 for(i = 0; i < MaxLit; i++){
87 * pull valid entries off free list and enter into mtf list
91 for(i = 0; i < n; i++){
95 m->prev[f] = m->prev[me];
96 m->next[m->prev[f]] = f;
101 if((i & CombMask) == 0)
102 m->comb[comb++] = me;
106 * pad out the list with dummies to the next comb,
109 for(; i & CombMask; i++){
113 m->prev[f] = m->prev[me];
114 m->next[m->prev[f]] = f;
128 mtflist(Mtf *m, int pos)
130 uchar *next, *prev, *mycomb;
131 int c, c0, pc, nc, off;
138 mycomb = &m->comb[pos >> CombLog];
139 off = pos & CombMask;
140 if(off >= CombSpace / 2){
142 for(; off < CombSpace; off++)
155 for(; mycomb > m->comb; mycomb--)
156 *mycomb = prev[*mycomb];
159 mycomb[m->maxcomb] = c;
170 hdecblock(Decode *dec, ulong n, ulong I, uchar *buf, ulong *sums, ulong *prev)
180 while((m = hdec(dec)) == 0 && i + dec->nzero < n)
184 c = dec->mtf.comb[0];
214 c = mtflist(&dec->mtf, m);
230 unsac(uchar *dst, uchar *src, int n, int nsrc)
238 dec = malloc(sizeof *dec);
240 prev = malloc((n+2) * sizeof *prev);
241 front = malloc(MaxLit * sizeof *front);
242 sums = malloc(MaxLit * sizeof *sums);
244 if(dec == nil || buf == nil || prev == nil || front == nil || sums == nil || setjmp(dec->errjmp)){
254 dec->smax = src + nsrc;
259 for(i = 0; i < MaxLit; i++)
265 fatal(dec, "corrupted input");
268 * decode the character usage map
270 for(i = 0; i < MaxLit; i++)
273 for(i = 0; i < MaxLit; ){
274 m = bitget(dec, 8) + 1;
277 fatal(dec, "corrupted char map");
284 * initialize mtf state
287 for(i = 0; i < MaxLit; i++)
290 mtflistinit(&dec->mtf, front, c);
291 dec->maxblocksym = c + LitBase;
294 * huffman decoding, move to front decoding,
295 * along with character counting
298 recvtab(dec, &dec->tab, MaxLeaf, nil);
299 hdecblock(dec, n, I, buf, sums, prev);
302 for(i = 0; i < MaxLit; i++){
309 for(j = n - 2; j >= 0; j--){
310 if(i > n || i < 0 || i == I)
311 fatal(dec, "corrupted data");
314 i = prev[i] + sums[c];
326 bitget(Decode *dec, int nb)
330 while(dec->nbits < nb){
331 if(dec->src >= dec->smax)
332 fatal(dec, "premature eof 1");
339 return (dec->bits >> dec->nbits) & ((1 << nb) - 1);
343 fillbits(Decode *dec)
347 while(dec->nbits < 24){
348 if(dec->src >= dec->smax)
349 fatal(dec, "premature eof 2");
361 hdecsym(Decode *dec, Huff *h, int b)
369 for(; (c = bits >> (nbits - b)) > h->maxcode[b]; b++)
372 fatal(dec, "too many bits consumed");
373 dec->nbits = nbits - b;
374 return h->decode[h->last[b] - c];
383 if(dec->nbits < dec->tab.maxbits)
386 dec->bits &= (1 << nbits) - 1;
387 c = dec->tab.flat[dec->bits >> (nbits - dec->tab.flatbits)];
391 c = hdecsym(dec, &dec->tab, c);
393 dec->nbits = nbits - nb;
396 * reverse funny run-length coding
399 dec->nzero += dec->base << c;
410 hufftab(Decode *dec, Huff *h, char *hb, ulong *bitcount, int maxleaf, int maxbits, int flatbits)
412 ulong c, mincode, code, nc[MaxHuffBits];
415 h->maxbits = maxbits;
421 for(b = 0; b <= maxbits; b++){
426 code = mincode + bitcount[b];
428 fatal(dec, "corrupted huffman table");
429 h->maxcode[b] = code - 1;
430 h->last[b] += code - 1;
432 if(code != (1 << maxbits))
433 fatal(dec, "huffman table not full");
434 if(flatbits > maxbits)
436 h->flatbits = flatbits;
439 for(i = 0; i < b; i++)
443 * initialize the flat table to include the minimum possible
444 * bit length for each code prefix
446 for(b = maxbits; b > flatbits; b--){
447 code = h->maxcode[b];
450 mincode = code + 1 - bitcount[b];
451 mincode >>= b - flatbits;
452 code >>= b - flatbits;
453 for(; mincode <= code; mincode++)
454 h->flat[mincode] = (b << 8) | 0xff;
457 for(i = 0; i < maxleaf; i++){
464 ec = (c + 1) << (flatbits - b);
465 if(ec > (1<<flatbits))
466 fatal(dec, "flat code too big");
467 for(c <<= (flatbits - b); c < ec; c++)
472 fatal(dec, "corrupted huffman table");
479 elimBit(int b, char *tmtf, int maxbits)
483 for(bb = 0; bb < maxbits; bb++)
486 while(++bb <= maxbits)
487 tmtf[bb - 1] = tmtf[bb];
491 elimBits(int b, ulong *bused, char *tmtf, int maxbits)
501 * increase bits counts for all descendants
503 for(bb = b + 1; bb < maxbits; bb++){
504 bused[bb] += 1 << (bb - b);
505 if(bused[bb] == (1 << bb)){
507 elimBit(bb, tmtf, maxbits);
512 * steal bits from parent & check for fullness
516 if(bused[b] == (1 << b)){
518 elimBit(b, tmtf, maxbits);
520 if((bused[b] & 1) == 0)
527 recvtab(Decode *dec, Huff *tab, int maxleaf, ushort *map)
529 ulong bitcount[MaxHuffBits+1], bused[MaxHuffBits+1];
530 char tmtf[MaxHuffBits+1], *hb;
531 int i, b, ttb, m, maxbits, max, elim;
533 hb = malloc(MaxLeaf * sizeof *hb);
535 fatal(dec, "out of memory");
538 * read the tables for the tables
541 for(i = 0; i <= MaxHuffBits; i++){
550 for(i = 0; i <= MaxHuffBits && elim != max; i++){
552 while(max - elim < (1 << (ttb-1)))
554 b = bitget(dec, ttb);
556 fatal(dec, "corrupted huffman table table");
563 elim += elimBits(b, bused, tmtf, max);
566 fatal(dec, "incomplete huffman table table");
567 hufftab(dec, tab, hb, bitcount, i, maxbits, MaxFlatbits);
568 for(i = 0; i <= MaxHuffBits; i++){
574 tmtf[MaxHuffBits] = 0;
577 for(i = 0; i < maxleaf && elim != MaxHuffBits; i++){
578 if(dec->nbits <= tab->maxbits)
580 dec->bits &= (1 << dec->nbits) - 1;
581 m = tab->flat[dec->bits >> (dec->nbits - tab->flatbits)];
585 m = hdecsym(dec, tab, m);
594 fatal(dec, "bit length too big");
602 elim += elimBits(b, bused, tmtf, MaxHuffBits);
604 if(elim != MaxHuffBits && elim != 0)
605 fatal(dec, "incomplete huffman table");
607 for(; i < maxleaf; i++)
610 hufftab(dec, tab, hb, bitcount, i, maxbits, MaxFlatbits);
616 fatal(Decode *dec, char *msg)
618 print("%s: %s\n", argv0, msg);
619 longjmp(dec->errjmp, 1);