ref: 38ea1ac105f4484f02bba3bfbc790ebe4f18f016
dir: /sys/src/cmd/disk/sacfs/sac.c/
#include <u.h> #include <libc.h> #include <bio.h> #include "sac.h" #include "ssort.h" typedef struct Chain Chain; typedef struct Chains Chains; typedef struct Huff Huff; enum { ZBase = 2, /* base of code to encode 0 runs */ LitBase = ZBase-1, /* base of literal values */ MaxLit = 256, MaxLeaf = MaxLit+LitBase, MaxHuffBits = 16, /* limit of bits in a huffman code */ ChainMem = 2 * (MaxHuffBits - 1) * MaxHuffBits, }; /* * huffman code table */ struct Huff { short bits; /* length of the code */ ulong encode; /* the code */ }; 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; }; static jmp_buf errjmp; static uchar *bout; static int bmax; static int bpos; static ulong leafcount[MaxLeaf]; static ulong nzero; static ulong *hbuf; static int hbpos; static ulong nzero; static ulong maxblocksym; static void henc(int); static void hbflush(void); static void mkprecode(Huff*, ulong *, int, int); static ulong sendtab(Huff *tab, int maxleaf, ushort *map); static int elimBits(int b, ulong *bused, char *tmtf, int maxbits); static void elimBit(int b, char *tmtf, int maxbits); static void nextchain(Chains*, int); static void hufftabinit(Huff*, int, ulong*, int); static void leafsort(ulong*, ushort*, int, int); static void bitput(int, int); static int mtf(uchar*, int); static void fatal(char*, ...); static ulong headerbits; static ulong charmapbits; static ulong hufftabbits; static ulong databits; static ulong nbits; static ulong bits; int sac(uchar *dst, uchar *src, int n) { uchar front[256]; ulong *perm, cmap[256]; long i, c, rev; rev = 0; perm = nil; if(setjmp(errjmp)){ free(perm); if(rev){ for(i = 0; i < n/2; i++){ c = src[i]; src[i] = src[n-i-1]; src[n-i-1] = c; } } return -1; } /* * set up the output buffer */ bout = dst; bmax = n; bpos = 0; perm = malloc((n+1)*sizeof *perm); if(perm == nil) return -1; hbuf = perm; hbpos = 0; nbits = 0; nzero = 0; for(i = 0; i < MaxLeaf; i++) leafcount[i] = 0; if(rev){ for(i = 0; i < n/2; i++){ c = src[i]; src[i] = src[n-i-1]; src[n-i-1] = c; } } i = ssortbyte(src, (int*)perm, nil, n); headerbits += 16; bitput(i, 16); /* * send the map of chars which occur in this block */ for(i = 0; i < 256; i++) cmap[i] = 0; for(i = 0; i < n; i++) cmap[src[i]] = 1; charmapbits += 1; bitput(cmap[0] != 0, 1); for(i = 0; i < 256; i = c){ for(c = i + 1; c < 256 && (cmap[c] != 0) == (cmap[i] != 0); c++) ; charmapbits += 8; bitput(c - i - 1, 8); } /* * initialize mtf state */ c = 0; for(i = 0; i < 256; i++){ if(cmap[i]){ cmap[i] = c; front[c] = i; c++; } } maxblocksym = c + LitBase; for(i = 0; i <= n; i++){ c = perm[i] - 1; if(c < 0) continue; henc(mtf(front, src[c])); } hbflush(); bitput(0, 24); bitput(0, 8 - nbits); free(perm); return bpos; } static void bitput(int c, int n) { bits <<= n; bits |= c; for(nbits += n; nbits >= 8; nbits -= 8){ c = bits << (32 - nbits); if(bpos >= bmax) longjmp(errjmp, 1); bout[bpos++] = c >> 24; } } static int mtf(uchar *front, int c) { int i, v; for(i = 0; front[i] != c; i++) ; for(v = i; i > 0; i--) front[i] = front[i - 1]; front[0] = c; return v; } /* * encode a run of zeros * convert to funny run length coding: * add one, omit implicit top 1 bit. */ static void zenc(void) { int m; nzero++; while(nzero != 1){ m = nzero & 1; hbuf[hbpos++] = m; leafcount[m]++; nzero >>= 1; } nzero = 0; } /* * encode one symbol */ static void henc(int c) { if(c == 0){ nzero++; return; } if(nzero) zenc(); c += LitBase; leafcount[c]++; hbuf[hbpos++] = c; } static void hbflush(void) { Huff tab[MaxLeaf]; int i, b, s; if(nzero) zenc(); if(hbpos == 0) return; mkprecode(tab, leafcount, maxblocksym, MaxHuffBits); hufftabbits += sendtab(tab, maxblocksym, nil); /* * send the data */ for(i = 0; i < hbpos; i++){ s = hbuf[i]; b = tab[s].bits; if(b == 0) fatal("bad tables %d", i); databits += b; bitput(tab[s].encode, b); } } static ulong sendtab(Huff *tab, int maxleaf, ushort *map) { ulong ccount[MaxHuffBits+1], bused[MaxHuffBits+1]; Huff codetab[MaxHuffBits+1]; char tmtf[MaxHuffBits+1]; ulong bits; int i, b, max, ttb, s, elim; /* * make up the table table * over cleverness: the data is known to be a huffman table * check for fullness at each bit level, and wipe it out from * the possibilities; when nothing exists except 0, stop. */ for(i = 0; i <= MaxHuffBits; i++){ tmtf[i] = i; ccount[i] = 0; bused[i] = 0; } tmtf[0] = -1; tmtf[MaxHuffBits] = 0; elim = 0; for(i = 0; i < maxleaf && elim != MaxHuffBits; i++){ b = i; if(map) b = map[b]; b = tab[b].bits; for(s = 0; tmtf[s] != b; s++) if(s >= MaxHuffBits) fatal("bitlength not found"); ccount[s]++; for(; s > 0; s--) tmtf[s] = tmtf[s-1]; tmtf[0] = b; elim += elimBits(b, bused, tmtf, MaxHuffBits); } if(elim != MaxHuffBits && elim != 0) fatal("incomplete huffman table"); /* * make up and send the table table */ max = 8; mkprecode(codetab, ccount, MaxHuffBits+1, max); for(i = 0; i <= max; i++){ tmtf[i] = i; bused[i] = 0; } tmtf[0] = -1; tmtf[max] = 0; elim = 0; bits = 0; for(i = 0; i <= MaxHuffBits && elim != max; i++){ b = codetab[i].bits; for(s = 0; tmtf[s] != b; s++) if(s > max) fatal("bitlength not found"); ttb = 4; while(max - elim < (1 << (ttb-1))) ttb--; bits += ttb; bitput(s, ttb); elim += elimBits(b, bused, tmtf, max); } if(elim != max) fatal("incomplete huffman table table"); /* * send the table */ for(i = 0; i <= MaxHuffBits; i++){ tmtf[i] = i; bused[i] = 0; } tmtf[0] = -1; tmtf[MaxHuffBits] = 0; elim = 0; for(i = 0; i < maxleaf && elim != MaxHuffBits; i++){ b = i; if(map) b = map[b]; b = tab[b].bits; for(s = 0; tmtf[s] != b; s++) if(s >= MaxHuffBits) fatal("bitlength not found"); ttb = codetab[s].bits; if(ttb < 0) fatal("bad huffman table table"); bits += ttb; bitput(codetab[s].encode, ttb); for(; s > 0; s--) tmtf[s] = tmtf[s-1]; tmtf[0] = b; elim += elimBits(b, bused, tmtf, MaxHuffBits); } if(elim != MaxHuffBits && elim != 0) fatal("incomplete huffman table"); return bits; } 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 elimBit(int b, char *tmtf, int maxbits) { int bb; for(bb = 0; bb < maxbits; bb++) if(tmtf[bb] == b) break; if(tmtf[bb] != b) fatal("elim bit not found"); while(++bb <= maxbits) tmtf[bb - 1] = tmtf[bb]; } /* * fast?, in-place huffman codes * * A. Moffat, J. Katajainen, "In-Place Calculation of Minimum-Redundancy Codes", * * counts must be sorted, and may be aliased to bitlens */ static int fmkprecode(ulong *bitcount, ulong *bitlen, ulong *counts, int n, int maxbits) { int leaf, tree, treet, depth, nodes, internal; /* * form the internal tree structure: * [0, tree) are parent pointers, * [tree, treet) are weights of internal nodes, * [leaf, n) are weights of remaining leaves. * * note that at the end, there are n-1 internal nodes */ leaf = 0; tree = 0; for(treet = 0; treet != n - 1; treet++){ if(leaf >= n || tree < treet && bitlen[tree] < counts[leaf]){ bitlen[treet] = bitlen[tree]; bitlen[tree++] = treet; }else bitlen[treet] = counts[leaf++]; if(leaf >= n || tree < treet && bitlen[tree] < counts[leaf]){ bitlen[treet] += bitlen[tree]; bitlen[tree++] = treet; }else bitlen[treet] += counts[leaf++]; } if(tree != treet - 1) fatal("bad fast mkprecode"); /* * calculate depth of internal nodes */ bitlen[n - 2] = 0; for(tree = n - 3; tree >= 0; tree--) bitlen[tree] = bitlen[bitlen[tree]] + 1; /* * calculate depth of leaves: * at each depth, leaves(depth) = nodes(depth) - internal(depth) * and nodes(depth+1) = 2 * internal(depth) */ leaf = n; tree = n - 2; depth = 0; for(nodes = 1; nodes > 0; nodes = 2 * internal){ internal = 0; while(tree >= 0 && bitlen[tree] == depth){ tree--; internal++; } nodes -= internal; if(depth < maxbits) bitcount[depth] = nodes; while(nodes-- > 0) bitlen[--leaf] = depth; depth++; } if(leaf != 0 || tree != -1) fatal("bad leaves in fast mkprecode"); return depth - 1; } /* * 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 void mkprecode(Huff *tab, ulong *count, int n, int maxbits) { Chains cs; Chain *c; ulong bitcount[MaxHuffBits]; 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){ m = cs.leafmap[0]; tab[m].bits = 0; tab[m].encode = 0; } return; } cs.nleaf = m; leafsort(cs.leafcount, cs.leafmap, 0, m); /* * try fast code */ bits = fmkprecode(bitcount, cs.leafcount, cs.leafcount, m, maxbits); if(bits < maxbits){ for(i = 0; i < m; i++) tab[cs.leafmap[i]].bits = cs.leafcount[i]; bitcount[0] = 0; }else{ 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; } hufftabinit(tab, n, bitcount, 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 void 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 > 0) tab[i].encode = nc[bits]++; } } 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; } } } static void fatal(char *fmt, ...) { char buf[512]; va_list arg; va_start(arg, fmt); doprint(buf, buf+sizeof(buf), fmt, arg); va_end(arg); longjmp(errjmp, 1); }