ref: 556618eb07d1ac6e2c629a60acd53c45d53261be
dir: /sys/src/cmd/disk/sacfs/unsac.c/
#include <u.h> #include <libc.h> #include "sac.h" typedef struct Huff Huff; typedef struct Mtf Mtf; typedef struct Decode Decode; enum { ZBase = 2, /* base of code to encode 0 runs */ LitBase = ZBase-1, /* base of literal values */ MaxLit = 256, MaxLeaf = MaxLit+LitBase, MaxHuffBits = 16, /* max bits in a huffman code */ MaxFlatbits = 5, /* max bits decoded in flat table */ CombLog = 4, CombSpace = 1 << CombLog, /* mtf speedup indices spacing */ CombMask = CombSpace - 1, }; struct Mtf { int maxcomb; /* index of last valid comb */ uchar prev[MaxLit]; uchar next[MaxLit]; uchar comb[MaxLit / CombSpace + 1]; }; struct Huff { int maxbits; int flatbits; ulong flat[1<<MaxFlatbits]; ulong maxcode[MaxHuffBits]; ulong last[MaxHuffBits]; ulong decode[MaxLeaf]; }; struct Decode{ Huff tab; Mtf mtf; int nbits; ulong bits; int nzero; int base; ulong maxblocksym; jmp_buf errjmp; uchar *src; /* input buffer */ uchar *smax; /* limit */ }; static void fatal(Decode *dec, char*); static int hdec(Decode*); static void recvtab(Decode*, Huff*, int, ushort*); static ulong bitget(Decode*, int); static int mtf(uchar*, int); #define FORWARD 0 static void mtflistinit(Mtf *m, uchar *front, int n) { int last, me, f, i, comb; if(n == 0) return; /* * add all entries to free list */ last = MaxLit - 1; for(i = 0; i < MaxLit; i++){ m->prev[i] = last; m->next[i] = i + 1; last = i; } m->next[last] = 0; f = 0; /* * pull valid entries off free list and enter into mtf list */ comb = 0; last = front[0]; for(i = 0; i < n; i++){ me = front[i]; f = m->next[me]; m->prev[f] = m->prev[me]; m->next[m->prev[f]] = f; m->next[last] = me; m->prev[me] = last; last = me; if((i & CombMask) == 0) m->comb[comb++] = me; } /* * pad out the list with dummies to the next comb, * using free entries */ for(; i & CombMask; i++){ me = f; f = m->next[me]; m->prev[f] = m->prev[me]; m->next[m->prev[f]] = f; m->next[last] = me; m->prev[me] = last; last = me; } me = front[0]; m->next[last] = me; m->prev[me] = last; m->comb[comb] = me; m->maxcomb = comb; } static int mtflist(Mtf *m, int pos) { uchar *next, *prev, *mycomb; int c, c0, pc, nc, off; if(pos == 0) return m->comb[0]; next = m->next; prev = m->prev; mycomb = &m->comb[pos >> CombLog]; off = pos & CombMask; if(off >= CombSpace / 2){ c = mycomb[1]; for(; off < CombSpace; off++) c = prev[c]; }else{ c = *mycomb; for(; off; off--) c = next[c]; } nc = next[c]; pc = prev[c]; prev[nc] = pc; next[pc] = nc; for(; mycomb > m->comb; mycomb--) *mycomb = prev[*mycomb]; c0 = *mycomb; *mycomb = c; mycomb[m->maxcomb] = c; next[c] = c0; pc = prev[c0]; prev[c] = pc; prev[c0] = c; next[pc] = c; return c; } static void hdecblock(Decode *dec, ulong n, ulong I, uchar *buf, ulong *sums, ulong *prev) { ulong i, nn, sum; int m, z, zz, c; nn = I; n--; i = 0; again: for(; i < nn; i++){ while((m = hdec(dec)) == 0 && i + dec->nzero < n) ; if(z = dec->nzero){ dec->nzero = 0; c = dec->mtf.comb[0]; sum = sums[c]; sums[c] = sum + z; z += i; zz = z; if(i < I && z > I){ zz = I; z++; } zagain: for(; i < zz; i++){ buf[i] = c; prev[i] = sum++; } if(i != z){ zz = z; nn = ++n; i++; goto zagain; } if(i == nn){ if(i == n) return; nn = ++n; i++; } } c = mtflist(&dec->mtf, m); buf[i] = c; sum = sums[c]; prev[i] = sum++; sums[c] = sum; } if(i == n) return; nn = ++n; i++; goto again; } int unsac(uchar *dst, uchar *src, int n, int nsrc) { Decode *dec; uchar *buf, *front; ulong *prev, *sums; ulong sum, i, I; int m, j, c; dec = malloc(sizeof *dec); buf = malloc(n+2); prev = malloc((n+2) * sizeof *prev); front = malloc(MaxLit * sizeof *front); sums = malloc(MaxLit * sizeof *sums); if(dec == nil || buf == nil || prev == nil || front == nil || sums == nil || setjmp(dec->errjmp)){ free(dec); free(buf); free(prev); free(front); free(sums); return -1; } dec->src = src; dec->smax = src + nsrc; dec->nbits = 0; dec->bits = 0; dec->nzero = 0; for(i = 0; i < MaxLit; i++) front[i] = i; n++; I = bitget(dec, 16); if(I >= n) fatal(dec, "corrupted input"); /* * decode the character usage map */ for(i = 0; i < MaxLit; i++) sums[i] = 0; c = bitget(dec, 1); for(i = 0; i < MaxLit; ){ m = bitget(dec, 8) + 1; while(m--){ if(i >= MaxLit) fatal(dec, "corrupted char map"); front[i++] = c; } c = c ^ 1; } /* * initialize mtf state */ c = 0; for(i = 0; i < MaxLit; i++) if(front[i]) front[c++] = i; mtflistinit(&dec->mtf, front, c); dec->maxblocksym = c + LitBase; /* * huffman decoding, move to front decoding, * along with character counting */ dec->base = 1; recvtab(dec, &dec->tab, MaxLeaf, nil); hdecblock(dec, n, I, buf, sums, prev); sum = 1; for(i = 0; i < MaxLit; i++){ c = sums[i]; sums[i] = sum; sum += c; } i = 0; for(j = n - 2; j >= 0; j--){ if(i > n || i < 0 || i == I) fatal(dec, "corrupted data"); c = buf[i]; dst[j] = c; i = prev[i] + sums[c]; } free(dec); free(buf); free(prev); free(front); free(sums); return n; } static ulong bitget(Decode *dec, int nb) { int c; while(dec->nbits < nb){ if(dec->src >= dec->smax) fatal(dec, "premature eof 1"); c = *dec->src++; dec->bits <<= 8; dec->bits |= c; dec->nbits += 8; } dec->nbits -= nb; return (dec->bits >> dec->nbits) & ((1 << nb) - 1); } static void fillbits(Decode *dec) { int c; while(dec->nbits < 24){ if(dec->src >= dec->smax) fatal(dec, "premature eof 2"); c = *dec->src++; dec->bits <<= 8; dec->bits |= c; dec->nbits += 8; } } /* * decode one symbol */ static int hdecsym(Decode *dec, Huff *h, int b) { long c; ulong bits; int nbits; bits = dec->bits; nbits = dec->nbits; for(; (c = bits >> (nbits - b)) > h->maxcode[b]; b++) ; if(b > h->maxbits) fatal(dec, "too many bits consumed"); dec->nbits = nbits - b; return h->decode[h->last[b] - c]; } static int hdec(Decode *dec) { ulong c; int nbits, nb; if(dec->nbits < dec->tab.maxbits) fillbits(dec); nbits = dec->nbits; dec->bits &= (1 << nbits) - 1; c = dec->tab.flat[dec->bits >> (nbits - dec->tab.flatbits)]; nb = c & 0xff; c >>= 8; if(nb == 0xff) c = hdecsym(dec, &dec->tab, c); else dec->nbits = nbits - nb; /* * reverse funny run-length coding */ if(c < ZBase){ dec->nzero += dec->base << c; dec->base <<= 1; return 0; } dec->base = 1; c -= LitBase; return c; } static void hufftab(Decode *dec, Huff *h, char *hb, ulong *bitcount, int maxleaf, int maxbits, int flatbits) { ulong c, mincode, code, nc[MaxHuffBits]; int i, b, ec; h->maxbits = maxbits; if(maxbits < 0) return; 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)) fatal(dec, "corrupted huffman table"); h->maxcode[b] = code - 1; h->last[b] += code - 1; } if(code != (1 << maxbits)) fatal(dec, "huffman table not full"); if(flatbits > maxbits) flatbits = maxbits; h->flatbits = flatbits; 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[mincode] = (b << 8) | 0xff; } for(i = 0; i < maxleaf; i++){ b = hb[i]; if(b == -1) continue; c = nc[b]++; if(b <= flatbits){ code = (i << 8) | b; ec = (c + 1) << (flatbits - b); if(ec > (1<<flatbits)) fatal(dec, "flat code too big"); for(c <<= (flatbits - b); c < ec; c++) h->flat[c] = code; }else{ c = h->last[b] - c; if(c >= maxleaf) fatal(dec, "corrupted huffman table"); h->decode[c] = i; } } } static void elimBit(int b, char *tmtf, int maxbits) { int bb; for(bb = 0; bb < maxbits; bb++) if(tmtf[bb] == b) break; while(++bb <= maxbits) tmtf[bb - 1] = tmtf[bb]; } static int elimBits(int b, ulong *bused, char *tmtf, int maxbits) { int bb, elim; if(b < 0) return 0; elim = 0; /* * increase bits counts for all descendants */ for(bb = b + 1; bb < maxbits; bb++){ bused[bb] += 1 << (bb - b); if(bused[bb] == (1 << bb)){ elim++; elimBit(bb, tmtf, maxbits); } } /* * steal bits from parent & check for fullness */ for(; b >= 0; b--){ bused[b]++; if(bused[b] == (1 << b)){ elim++; elimBit(b, tmtf, maxbits); } if((bused[b] & 1) == 0) break; } return elim; } static void recvtab(Decode *dec, Huff *tab, int maxleaf, ushort *map) { ulong bitcount[MaxHuffBits+1], bused[MaxHuffBits+1]; char tmtf[MaxHuffBits+1], *hb; int i, b, ttb, m, maxbits, max, elim; hb = malloc(MaxLeaf * sizeof *hb); if(hb == nil) fatal(dec, "out of memory"); /* * read the tables for the tables */ max = 8; for(i = 0; i <= MaxHuffBits; i++){ bitcount[i] = 0; tmtf[i] = i; bused[i] = 0; } tmtf[0] = -1; tmtf[max] = 0; elim = 0; maxbits = -1; for(i = 0; i <= MaxHuffBits && elim != max; i++){ ttb = 4; while(max - elim < (1 << (ttb-1))) ttb--; b = bitget(dec, ttb); if(b > max - elim) fatal(dec, "corrupted huffman table table"); b = tmtf[b]; hb[i] = b; bitcount[b]++; if(b > maxbits) maxbits = b; elim += elimBits(b, bused, tmtf, max); } if(elim != max) fatal(dec, "incomplete huffman table table"); hufftab(dec, tab, hb, bitcount, i, maxbits, MaxFlatbits); for(i = 0; i <= MaxHuffBits; i++){ tmtf[i] = i; bitcount[i] = 0; bused[i] = 0; } tmtf[0] = -1; tmtf[MaxHuffBits] = 0; elim = 0; maxbits = -1; for(i = 0; i < maxleaf && elim != MaxHuffBits; i++){ if(dec->nbits <= tab->maxbits) fillbits(dec); dec->bits &= (1 << dec->nbits) - 1; m = tab->flat[dec->bits >> (dec->nbits - tab->flatbits)]; b = m & 0xff; m >>= 8; if(b == 0xff) m = hdecsym(dec, tab, m); else dec->nbits -= b; b = tmtf[m]; for(; m > 0; m--) tmtf[m] = tmtf[m-1]; tmtf[0] = b; if(b > MaxHuffBits) fatal(dec, "bit length too big"); m = i; if(map != nil) m = map[m]; hb[m] = b; bitcount[b]++; if(b > maxbits) maxbits = b; elim += elimBits(b, bused, tmtf, MaxHuffBits); } if(elim != MaxHuffBits && elim != 0) fatal(dec, "incomplete huffman table"); if(map != nil) for(; i < maxleaf; i++) hb[map[i]] = -1; hufftab(dec, tab, hb, bitcount, i, maxbits, MaxFlatbits); free(hb); } static void fatal(Decode *dec, char *msg) { print("%s: %s\n", argv0, msg); longjmp(dec->errjmp, 1); }