Import sources from 2011-03-30 iso image

9 files changed, 3061 insertions, 0 deletions

diff --git a/sys/src/cmd/disk/sacfs/mkfile b/sys/src/cmd/disk/sacfs/mkfile
new file mode 100755
index 000000000..3a6a9436b
--- /dev/null
+++ b/sys/src/cmd/disk/sacfs/mkfile
@@ -0,0 +1,20 @@
+</$objtype/mkfile
+
+HFILES=sac.h\
+	ssort.h\
+	sacfs.h\
+
+TARG=mksacfs\
+	sacfs\
+
+OFILES=
+
+PROGS=${TARG:%=$O.%}
+
+BIN=/$objtype/bin/disk
+
+< /sys/src/cmd/mkmany
+
+$O.mksacfs:	sac.$O ssort6.$O
+
+$O.sacfs:	unsac.$O
diff --git a/sys/src/cmd/disk/sacfs/mksacfs.c b/sys/src/cmd/disk/sacfs/mksacfs.c
new file mode 100755
index 000000000..c0c28dd57
--- /dev/null
+++ b/sys/src/cmd/disk/sacfs/mksacfs.c
@@ -0,0 +1,295 @@
+#include <u.h>
+#include <libc.h>
+#include "sac.h"
+#include "sacfs.h"
+
+enum {
+	NCACHE = 1024,	/* must be power of two */
+	OffsetSize = 4,	/* size of block offset */
+};
+
+int	warn(char *);
+int	seen(Dir *);
+void usage(void);
+void outwrite(void *buf, int n, long off);
+void putl(void *p, uint v);
+void *emalloc(int size);
+void sacfs(char *root);
+void sacfile(char *name, Dir *dir, SacDir *sd);
+void sacdir(char *name, Dir *dir, SacDir *sd);
+
+int	uflag=0;
+int	fflag=0;
+long blocksize = 4*1024;
+
+struct Out
+{
+	int	fd;
+	long size;
+} out;
+
+typedef	struct	Cache	Cache;
+struct	Cache
+{
+	Dir*	cache;
+	int	n;
+	int	max;
+} cache[NCACHE];
+
+void
+main(int argc, char *argv[])
+{
+	char *s, *ss;
+	char *outfile = nil;
+
+	ARGBEGIN {
+	case 'u':
+		uflag=1;
+		break;
+	case 'o':
+		outfile = ARGF();
+		break;
+	case 'b':
+		s = ARGF();
+		if(s) {
+			blocksize = strtoul(s, &ss, 0);
+			if(s == ss)
+				usage();
+			if(*ss == 'k')
+				blocksize *= 1024;
+		}
+		if(blocksize < sizeof(SacDir))
+			sysfatal("blocksize too small");
+		break;
+	} ARGEND
+
+	if(outfile == nil) {
+		sysfatal("still to do: need to create temp file");
+	} else {
+		out.fd = create(outfile, OWRITE|OTRUNC, 0664);
+		if(out.fd < 0)
+			sysfatal("could not create file: %s: %r", outfile);
+	}
+
+	if(argc==0)
+		sacfs(".");
+	else
+		sacfs(argv[0]);
+
+	close(out.fd);
+
+	exits(0);
+}
+
+void
+usage(void)
+{
+	fprint(2, "usage: %s [-u] [-b blocksize] -o output [root]\n", argv0);
+	exits("usage");
+}
+
+void
+sacfs(char *root)
+{
+	Dir *dir;
+	long offset;
+	SacHeader hdr;
+	SacDir sd;
+
+	dir = dirstat(root);
+	if(dir == nil)
+		sysfatal("could not stat root: %s: %r", root);
+	offset = out.size;
+	out.size += sizeof(SacHeader) + sizeof(SacDir);
+	memset(&hdr, 0, sizeof(hdr));
+	putl(hdr.magic, Magic);
+	putl(hdr.blocksize, blocksize);
+	if(dir->mode & DMDIR)
+		sacdir(root, dir, &sd);
+	else
+		sacfile(root, dir, &sd);
+	putl(hdr.length, out.size);
+	outwrite(&hdr, sizeof(hdr), offset);
+	outwrite(&sd, sizeof(sd), offset+sizeof(SacHeader));
+	free(dir);
+}
+
+void
+setsd(SacDir *sd, Dir *dir, long length, long blocks)
+{
+	static qid = 1;
+
+	memset(sd, 0, sizeof(SacDir));
+	strncpy(sd->name, dir->name, NAMELEN);
+	strncpy(sd->uid, dir->uid, NAMELEN);
+	strncpy(sd->gid, dir->gid, NAMELEN);
+	putl(sd->qid, qid++|(dir->mode&DMDIR));
+	putl(sd->mode, dir->mode);
+	putl(sd->atime, dir->atime);
+	putl(sd->mtime, dir->mtime);
+	putl(sd->length, length);
+	putl(sd->blocks, blocks);
+}
+
+
+void
+sacfile(char *name, Dir *dir, SacDir *sd)
+{
+	int fd, i, n, nn;
+	long nblock;
+	uchar *blocks;
+	uchar *buf, *cbuf;
+	long offset;
+	long block;
+
+	fd = open(name, OREAD);
+	if(fd < 0)
+		sysfatal("could not open file: %s: %r", name);
+	nblock = (dir->length + blocksize-1)/blocksize;
+	blocks = emalloc((nblock+1)*OffsetSize);
+	buf = emalloc(blocksize);
+	cbuf = emalloc(blocksize);
+	offset = out.size;
+	out.size += (nblock+1)*OffsetSize;
+	for(i=0; i<nblock; i++) {
+		n = read(fd, buf, blocksize);
+		if(n < 0)
+			sysfatal("read failed: %s: %r", name);
+		if(n == 0)
+			sysfatal("unexpected eof: %s", name);
+		if(n < blocksize && i != nblock-1)
+			sysfatal("short read: %s: got %d", name, n);
+		block = out.size;
+		nn = sac(cbuf, buf, n);
+		if(nn < 0 || uflag) {
+			outwrite(buf, n, out.size);
+			out.size += n;
+		} else {
+			block = -block;
+			outwrite(cbuf, nn, out.size);
+			out.size += nn;
+		}
+		putl(blocks+i*OffsetSize, block);
+	}
+	putl(blocks+i*OffsetSize, out.size);
+	outwrite(blocks, (nblock+1)*OffsetSize, offset);
+	setsd(sd, dir, dir->length, offset);
+	close(fd);
+	free(buf);
+	free(cbuf);
+	free(blocks);
+}
+
+void
+sacdir(char *name, Dir *dir, SacDir *sd)
+{
+	Dir *dirs, *p;
+	int i, n, nn, per;
+	SacDir *sds;
+	int ndir, fd, nblock;
+	long offset, block;
+	uchar *blocks, *cbuf;
+	char file[512];
+
+	fd = open(name, OREAD);
+	if(fd < 0)
+		sysfatal("could not open directory: %s: %r", name);
+	ndir = dirreadall(fd, &dirs);
+	if(ndir < 0)
+		sysfatal("could not read directory: %s: %r", name);
+	close(fd);
+	per = blocksize/sizeof(SacDir);
+	nblock = (ndir+per-1)/per;
+	sds = emalloc(nblock*per*sizeof(SacDir));
+	p = dirs;
+	for(i=0; i<ndir; i++,p++) {
+		sprint(file, "%s/%s", name, p->name);
+		if(p->mode & DMDIR)
+			sacdir(file, p, sds+i);
+		else
+			sacfile(file, p, sds+i);
+	}
+	free(dirs);
+	blocks = emalloc((nblock+1)*OffsetSize);
+	offset = out.size;
+	out.size += (nblock+1)*OffsetSize;
+	n = per*sizeof(SacDir);
+	cbuf = emalloc(n);
+	for(i=0; i<nblock; i++) {
+		block = out.size;
+		if(n > (ndir-i*per)*sizeof(SacDir))
+			n = (ndir-i*per)*sizeof(SacDir);
+		nn = sac(cbuf, (uchar*)(sds+i*per), n);
+		if(nn < 0 || uflag) {
+			outwrite(sds+i*per, n, out.size);
+			out.size += n;
+		} else {
+			block = -block;
+			outwrite(cbuf, nn, out.size);
+			out.size += nn;
+		}
+		putl(blocks+i*OffsetSize, block);
+	}
+	free(cbuf);
+	putl(blocks+i*OffsetSize, out.size);
+	outwrite(blocks, (nblock+1)*OffsetSize, offset);
+	setsd(sd, dir, ndir, offset);
+	free(sds);
+	free(blocks);
+}
+
+int
+seen(Dir *dir)
+{
+	Dir *dp;
+	int i;
+	Cache *c;
+
+	c = &cache[dir->qid.path&(NCACHE-1)];
+	dp = c->cache;
+	for(i=0; i<c->n; i++, dp++)
+		if(dir->qid.path == dp->qid.path &&
+		   dir->type == dp->type &&
+		   dir->dev == dp->dev)
+			return 1;
+	if(c->n == c->max){
+		c->cache = realloc(c->cache, (c->max+=20)*sizeof(Dir));
+		if(cache == 0)
+			sysfatal("malloc failure");
+	}
+	c->cache[c->n++] = *dir;
+	return 0;
+}
+
+void
+outwrite(void *buf, int n, long offset)
+{
+	if(seek(out.fd, offset, 0) < 0)
+		sysfatal("seek failed: %r");
+	if(write(out.fd, buf, n) < n)
+		sysfatal("write failed: %r");
+}
+
+void
+putl(void *p, uint v)
+{
+	uchar *a;
+
+	a = p;
+	a[0] = v>>24;
+	a[1] = v>>16;
+	a[2] = v>>8;
+	a[3] = v;
+}
+
+void *
+emalloc(int size)
+{
+	void *p;
+
+	p = malloc(size);
+	if(p == nil)
+		sysfatal("malloc failed");
+	memset(p, 0, size);
+	return p;
+}
diff --git a/sys/src/cmd/disk/sacfs/sac.c b/sys/src/cmd/disk/sacfs/sac.c
new file mode 100755
index 000000000..abe775a7a
--- /dev/null
+++ b/sys/src/cmd/disk/sacfs/sac.c
@@ -0,0 +1,792 @@
+#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);
+}
diff --git a/sys/src/cmd/disk/sacfs/sac.h b/sys/src/cmd/disk/sacfs/sac.h
new file mode 100755
index 000000000..7caaa476c
--- /dev/null
+++ b/sys/src/cmd/disk/sacfs/sac.h
@@ -0,0 +1,2 @@
+int	sac(uchar *dst, uchar *src, int blocksize);
+int unsac(uchar *dst, uchar *src, int n, int nsrc);
diff --git a/sys/src/cmd/disk/sacfs/sacfs.c b/sys/src/cmd/disk/sacfs/sacfs.c
new file mode 100755
index 000000000..0824143a4
--- /dev/null
+++ b/sys/src/cmd/disk/sacfs/sacfs.c
@@ -0,0 +1,882 @@
+#include <u.h>
+#include <libc.h>
+#include <auth.h>
+#include <fcall.h>
+#include "sac.h"
+#include "sacfs.h"
+
+/*
+ * Rather than reading /adm/users, which is a lot of work for
+ * a toy program, we assume all groups have the form
+ *	NNN:user:user:
+ * meaning that each user is the leader of his own group.
+ */
+
+enum
+{
+	OPERM	= 0x3,		/* mask of all permission types in open mode */
+	Nram	= 512,
+	OffsetSize = 4,		/* size in bytes of an offset */
+	CacheSize = 20,
+};
+
+typedef struct Fid Fid;
+typedef struct Path Path;
+typedef struct Sac Sac;
+typedef struct Cache Cache;
+
+struct Fid
+{
+	short busy;
+	short open;
+	int fid;
+	char *user;
+	Qid qid;
+	Sac *sac;
+	Fid	*next;
+};
+
+struct Sac
+{
+	SacDir;
+	Path *path;
+};
+
+struct Path
+{
+	int ref;
+	Path *up;
+	long blocks;
+	int entry;
+	int nentry;
+};
+
+struct Cache
+{
+	long block;
+	ulong age;
+	uchar *data;
+};
+
+enum
+{
+	Pexec =		1,
+	Pwrite = 	2,
+	Pread = 	4,
+	Pother = 	1,
+	Pgroup = 	8,
+	Powner =	64,
+};
+
+Fid	*fids;
+uchar *data;
+int	mfd[2];
+char	user[NAMELEN];
+char	mdata[MAXMSG+MAXFDATA];
+Fcall	rhdr;
+Fcall	thdr;
+int blocksize;
+Sac root;
+Cache cache[CacheSize];
+ulong cacheage;
+
+Fid *	newfid(int);
+void	sacstat(SacDir*, char*);
+void	error(char*);
+void	io(void);
+void	*erealloc(void*, ulong);
+void	*emalloc(ulong);
+void	usage(void);
+int	perm(Fid*, Sac*, int);
+ulong	getl(void *p);
+void	init(char*);
+Sac	*saccpy(Sac *s);
+Sac *saclookup(Sac *s, char *name);
+int sacdirread(Sac *s, char *p, long off, long cnt);
+void loadblock(void *buf, uchar *offset, int blocksize);
+void sacfree(Sac*);
+
+char	*rflush(Fid*), *rnop(Fid*), *rsession(Fid*),
+	*rattach(Fid*), *rclone(Fid*), *rwalk(Fid*),
+	*rclwalk(Fid*), *ropen(Fid*), *rcreate(Fid*),
+	*rread(Fid*), *rwrite(Fid*), *rclunk(Fid*),
+	*rremove(Fid*), *rstat(Fid*), *rwstat(Fid*);
+
+char 	*(*fcalls[])(Fid*) = {
+	[Tflush]	rflush,
+	[Tsession]	rsession,
+	[Tnop]		rnop,
+	[Tattach]	rattach,
+	[Tclone]	rclone,
+	[Twalk]		rwalk,
+	[Tclwalk]	rclwalk,
+	[Topen]		ropen,
+	[Tcreate]	rcreate,
+	[Tread]		rread,
+	[Twrite]	rwrite,
+	[Tclunk]	rclunk,
+	[Tremove]	rremove,
+	[Tstat]		rstat,
+	[Twstat]	rwstat,
+};
+
+char	Eperm[] =	"permission denied";
+char	Enotdir[] =	"not a directory";
+char	Enoauth[] =	"no authentication in ramfs";
+char	Enotexist[] =	"file does not exist";
+char	Einuse[] =	"file in use";
+char	Eexist[] =	"file exists";
+char	Enotowner[] =	"not owner";
+char	Eisopen[] = 	"file already open for I/O";
+char	Excl[] = 	"exclusive use file already open";
+char	Ename[] = 	"illegal name";
+char	Erdonly[] = 	"read only file system";
+
+int debug;
+
+void
+notifyf(void *a, char *s)
+{
+	USED(a);
+	if(strncmp(s, "interrupt", 9) == 0)
+		noted(NCONT);
+	noted(NDFLT);
+}
+
+void
+main(int argc, char *argv[])
+{
+	char *defmnt;
+	int p[2];
+	char buf[12];
+	int fd;
+	int stdio = 0;
+
+	defmnt = "/n/c:";
+	ARGBEGIN{
+	case 'd':
+		debug = 1;
+		break;
+	case 'i':
+		defmnt = 0;
+		stdio = 1;
+		mfd[0] = 0;
+		mfd[1] = 1;
+		break;
+	case 's':
+		defmnt = 0;
+		break;
+	case 'm':
+		defmnt = ARGF();
+		break;
+	default:
+		usage();
+	}ARGEND
+
+	if(argc != 1)
+		usage();
+
+	init(argv[0]);
+	
+	if(pipe(p) < 0)
+		error("pipe failed");
+	if(!stdio){
+		mfd[0] = p[0];
+		mfd[1] = p[0];
+		if(defmnt == 0){
+			fd = create("#s/sacfs", OWRITE, 0666);
+			if(fd < 0)
+				error("create of /srv/sacfs failed");
+			sprint(buf, "%d", p[1]);
+			if(write(fd, buf, strlen(buf)) < 0)
+				error("writing /srv/sacfs");
+		}
+	}
+
+	if(debug)
+		fmtinstall('F', fcallconv);
+	switch(rfork(RFFDG|RFPROC|RFNAMEG|RFNOTEG)){
+	case -1:
+		error("fork");
+	case 0:
+		close(p[1]);
+		io();
+		break;
+	default:
+		close(p[0]);	/* don't deadlock if child fails */
+		if(defmnt && mount(p[1], defmnt, MREPL|MCREATE, "") < 0)
+			error("mount failed");
+	}
+	exits(0);
+}
+
+char*
+rnop(Fid *f)
+{
+	USED(f);
+	return 0;
+}
+
+char*
+rsession(Fid *unused)
+{
+	Fid *f;
+
+	USED(unused);
+
+	for(f = fids; f; f = f->next)
+		if(f->busy)
+			rclunk(f);
+	memset(thdr.authid, 0, sizeof(thdr.authid));
+	memset(thdr.authdom, 0, sizeof(thdr.authdom));
+	memset(thdr.chal, 0, sizeof(thdr.chal));
+	return 0;
+}
+
+char*
+rflush(Fid *f)
+{
+	USED(f);
+	return 0;
+}
+
+char*
+rattach(Fid *f)
+{
+	/* no authentication! */
+	f->busy = 1;
+	f->qid = (Qid){getl(root.qid), 0};
+	f->sac = saccpy(&root);
+	thdr.qid = f->qid;
+	if(rhdr.uname[0])
+		f->user = strdup(rhdr.uname);
+	else
+		f->user = "none";
+	return 0;
+}
+
+char*
+rclone(Fid *f)
+{
+	Fid *nf;
+
+	if(f->open)
+		return Eisopen;
+	if(f->busy == 0)
+		return Enotexist;
+	nf = newfid(rhdr.newfid);
+	nf->busy = 1;
+	nf->open = 0;
+	nf->qid = f->qid;
+	nf->sac = saccpy(f->sac);
+	nf->user = strdup(f->user);
+	return 0;
+}
+
+char*
+rwalk(Fid *f)
+{
+	char *name;
+	Sac *sac;
+
+	if((f->qid.path & CHDIR) == 0)
+		return Enotdir;
+	if(f->busy == 0)
+		return Enotexist;
+	name = rhdr.name;
+	sac = f->sac;
+	if(strcmp(name, ".") == 0){
+		thdr.qid = f->qid;
+		return 0;
+	}
+	if(!perm(f, sac, Pexec))
+		return Eperm;
+	sac = saclookup(sac, name);
+	if(sac == nil)
+		return Enotexist;
+	f->sac = sac;
+	f->qid = (Qid){getl(sac->qid), 0};
+	thdr.qid = f->qid;
+	return 0;
+}
+
+char *
+rclwalk(Fid *f)
+{
+	Fid *nf;
+	char *err;
+
+	nf = newfid(rhdr.newfid);
+	nf->busy = 1;
+	nf->sac = saccpy(f->sac);
+	nf->user = strdup(f->user);
+	if(err = rwalk(nf))
+		rclunk(nf);
+	return err;
+}
+
+char *
+ropen(Fid *f)
+{
+	int mode, trunc;
+
+	if(f->open)
+		return Eisopen;
+	if(f->busy == 0)
+		return Enotexist;
+	mode = rhdr.mode;
+	if(f->qid.path & CHDIR){
+		if(mode != OREAD)
+			return Eperm;
+		thdr.qid = f->qid;
+		return 0;
+	}
+	if(mode & ORCLOSE)
+		return Erdonly;
+	trunc = mode & OTRUNC;
+	mode &= OPERM;
+	if(mode==OWRITE || mode==ORDWR || trunc)
+		return Erdonly;
+	if(mode==OREAD)
+		if(!perm(f, f->sac, Pread))
+			return Eperm;
+	if(mode==OEXEC)
+		if(!perm(f, f->sac, Pexec))
+			return Eperm;
+	thdr.qid = f->qid;
+	f->open = 1;
+	return 0;
+}
+
+char *
+rcreate(Fid *f)
+{
+	if(f->open)
+		return Eisopen;
+	if(f->busy == 0)
+		return Enotexist;
+	return Erdonly;
+}
+
+char*
+rread(Fid *f)
+{
+	Sac *sac;
+	char *buf, *buf2;
+	long off;
+	int n, cnt, i, j;
+	uchar *blocks;
+	long length;
+
+	if(f->busy == 0)
+		return Enotexist;
+	sac = f->sac;
+	thdr.count = 0;
+	off = rhdr.offset;
+	buf = thdr.data;
+	cnt = rhdr.count;
+	if(f->qid.path & CHDIR){
+		cnt = (rhdr.count/DIRLEN)*DIRLEN;
+		if(off%DIRLEN)
+			return "i/o error";
+		thdr.count = sacdirread(sac, buf, off, cnt);
+		return 0;
+	}
+	length = getl(sac->length);
+	if(off >= length) {
+		rhdr.count = 0;
+		return 0;
+	}
+	if(cnt > length-off)
+		cnt = length-off;
+	thdr.count = cnt;
+	if(cnt == 0)
+		return 0;
+	blocks = data + getl(sac->blocks);
+	buf2 = malloc(blocksize);
+	if(buf2 == nil)
+		sysfatal("malloc failed");
+	while(cnt > 0) {
+		i = off/blocksize;
+		n = blocksize;
+		if(n > length-i*blocksize)
+			n = length-i*blocksize;
+		loadblock(buf2, blocks+i*OffsetSize, n);
+		j = off-i*blocksize;
+		n = blocksize-j;
+		if(n > cnt)
+			n = cnt;
+		memmove(buf, buf2+j, n);
+		cnt -= n;
+		off += n;
+		buf += n;
+	}
+	free(buf2);
+	return 0;
+}
+
+char*
+rwrite(Fid *f)
+{
+	if(f->busy == 0)
+		return Enotexist;
+	return Erdonly;
+}
+
+char *
+rclunk(Fid *f)
+{
+	f->busy = 0;
+	f->open = 0;
+	free(f->user);
+	sacfree(f->sac);
+	return 0;
+}
+
+char *
+rremove(Fid *f)
+{
+	f->busy = 0;
+	f->open = 0;
+	free(f->user);
+	sacfree(f->sac);
+	return Erdonly;
+}
+
+char *
+rstat(Fid *f)
+{
+	if(f->busy == 0)
+		return Enotexist;
+	sacstat(f->sac, thdr.stat);
+	return 0;
+}
+
+char *
+rwstat(Fid *f)
+{
+	if(f->busy == 0)
+		return Enotexist;
+	return Erdonly;
+}
+
+Sac*
+saccpy(Sac *s)
+{
+	Sac *ss;
+	
+	ss = emalloc(sizeof(Sac));
+	*ss = *s;
+	if(ss->path)
+		ss->path->ref++;
+	return ss;
+}
+
+Path *
+pathalloc(Path *p, long blocks, int entry, int nentry)
+{
+	Path *pp = emalloc(sizeof(Path));
+
+	pp->ref = 1;
+	pp->blocks = blocks;
+	pp->entry = entry;
+	pp->nentry = nentry;
+	pp->up = p;
+	return pp;
+}
+
+void
+pathfree(Path *p)
+{
+	if(p == nil)
+		return;
+	p->ref--;
+	if(p->ref > 0)
+		return;
+
+	pathfree(p->up);
+	free(p);
+}
+
+
+void
+sacfree(Sac *s)
+{
+	pathfree(s->path);
+	free(s);
+}
+
+void
+sacstat(SacDir *s, char *buf)
+{
+	Dir dir;
+
+	memmove(dir.name, s->name, NAMELEN);
+	dir.qid = (Qid){getl(s->qid), 0};
+	dir.mode = getl(s->mode);
+	dir.length = getl(s->length);
+	if(dir.mode &CHDIR)
+		dir.length *= DIRLEN;
+	memmove(dir.uid, s->uid, NAMELEN);
+	memmove(dir.gid, s->gid, NAMELEN);
+	dir.atime = getl(s->atime);
+	dir.mtime = getl(s->mtime);
+	convD2M(&dir, buf);
+}
+
+void
+loadblock(void *buf, uchar *offset, int blocksize)
+{
+	long block, n;
+	ulong age;
+	int i, j;
+
+	block = getl(offset);
+	if(block < 0) {
+		block = -block;
+		cacheage++;
+		// age has wraped
+		if(cacheage == 0) {
+			for(i=0; i<CacheSize; i++)
+				cache[i].age = 0;
+		}
+		j = 0;
+		age = cache[0].age;
+		for(i=0; i<CacheSize; i++) {
+			if(cache[i].age < age) {
+				age = cache[i].age;
+				j = i;
+			}
+			if(cache[i].block != block)
+				continue;
+			memmove(buf, cache[i].data, blocksize);
+			cache[i].age = cacheage;
+			return;
+		}
+
+		n = getl(offset+OffsetSize);
+		if(n < 0)
+			n = -n;
+		n -= block;
+		if(unsac(buf, data+block, blocksize, n)<0)
+			sysfatal("unsac failed!");
+		memmove(cache[j].data, buf, blocksize);
+		cache[j].age = cacheage;
+		cache[j].block = block;
+	} else {
+		memmove(buf, data+block, blocksize);
+	}
+}
+
+Sac*
+sacparent(Sac *s)
+{
+	uchar *blocks;
+	SacDir *buf;
+	int per, i, n;
+	Path *p;
+
+	p = s->path;
+	if(p == nil || p->up == nil) {
+		pathfree(p);
+		*s = root;
+		return s;
+	}
+	p = p->up;
+
+	blocks = data + p->blocks;
+	per = blocksize/sizeof(SacDir);
+	i = p->entry/per;
+	n = per;
+	if(n > p->nentry-i*per)
+		n = p->nentry-i*per;
+	buf = emalloc(per*sizeof(SacDir));
+	loadblock(buf, blocks + i*OffsetSize, n*sizeof(SacDir));
+	s->SacDir = buf[p->entry-i*per];
+	free(buf);
+	p->ref++;
+	pathfree(s->path);
+	s->path = p;
+	return s;
+}
+
+int
+sacdirread(Sac *s, char *p, long off, long cnt)
+{
+	uchar *blocks;
+	SacDir *buf;
+	int iblock, per, i, j, ndir, n;
+
+	blocks = data + getl(s->blocks);
+	per = blocksize/sizeof(SacDir);
+	ndir = getl(s->length);
+	off /= DIRLEN;
+	cnt /= DIRLEN;
+	if(off >= ndir)
+		return 0;
+	if(cnt > ndir-off)
+		cnt = ndir-off;
+	iblock = -1;
+	buf = emalloc(per*sizeof(SacDir));
+	for(i=off; i<off+cnt; i++) {
+		j = i/per;
+		if(j != iblock) {
+			n = per;
+			if(n > ndir-j*per)
+				n = ndir-j*per;
+			loadblock(buf, blocks + j*OffsetSize, n*sizeof(SacDir));
+			iblock = j;
+		}
+		sacstat(buf+i-j*per, p);
+		p += DIRLEN;
+	}
+	free(buf);
+	return cnt*DIRLEN;
+}
+
+Sac*
+saclookup(Sac *s, char *name)
+{
+	int ndir;
+	int top, bot, i, j, k, n, per;
+	uchar *blocks;
+	SacDir *buf;
+	int iblock;
+	SacDir *sd;
+	
+	if(strcmp(name, "..") == 0)
+		return sacparent(s);
+	blocks = data + getl(s->blocks);
+	per = blocksize/sizeof(SacDir);
+	ndir = getl(s->length);
+	buf = malloc(per*sizeof(SacDir));
+	if(buf == nil)
+		sysfatal("malloc failed");
+	iblock = -1;
+
+	if(1) {
+		// linear search
+		for(i=0; i<ndir; i++) {
+			j = i/per;
+			if(j != iblock) {
+				n = per;
+				if(n > ndir-j*per)
+					n = ndir-j*per;
+				loadblock(buf, blocks + j*OffsetSize, n*sizeof(SacDir));
+				iblock = j;
+			}
+			sd = buf+i-j*per;
+			k = strcmp(name, sd->name);
+			if(k == 0) {
+				s->path = pathalloc(s->path, getl(s->blocks), i, ndir);
+				s->SacDir = *sd;
+				free(buf);
+				return s;
+			}
+		}
+		free(buf);
+		return 0;
+	}
+
+	// binary search
+	top = ndir;
+	bot = 0;
+	while(bot != top){
+		i = (bot+top)>>1;
+		j = i/per;
+		if(j != iblock) {
+			n = per;
+			if(n > ndir-j*per)
+				n = ndir-j*per;
+			loadblock(buf, blocks + j*OffsetSize, n*sizeof(SacDir));
+			iblock = j;
+		}
+		j *= per;
+		sd = buf+i-j;
+		k = strcmp(name, sd->name);
+		if(k == 0) {
+			s->path = pathalloc(s->path, getl(s->blocks), i, ndir);
+			s->SacDir = *sd;
+			free(buf);
+		}
+		if(k < 0) {
+			top = i;
+			sd = buf;
+			if(strcmp(name, sd->name) < 0)
+				top = j;
+		} else {
+			bot = i+1;
+			if(ndir-j < per)
+				i = ndir-j;
+			else
+				i = per;
+			sd = buf+i-1;
+			if(strcmp(name, sd->name) > 0)
+				bot = j+i;
+		}
+	}
+	return 0;
+}
+
+Fid *
+newfid(int fid)
+{
+	Fid *f, *ff;
+
+	ff = 0;
+	for(f = fids; f; f = f->next)
+		if(f->fid == fid)
+			return f;
+		else if(!ff && !f->busy)
+			ff = f;
+	if(ff){
+		ff->fid = fid;
+		return ff;
+	}
+	f = emalloc(sizeof *f);
+	memset(f, 0 , sizeof(Fid));
+	f->fid = fid;
+	f->next = fids;
+	fids = f;
+	return f;
+}
+
+void
+io(void)
+{
+	char *err;
+	int n;
+
+	for(;;){
+		/*
+		 * reading from a pipe or a network device
+		 * will give an error after a few eof reads
+		 * however, we cannot tell the difference
+		 * between a zero-length read and an interrupt
+		 * on the processes writing to us,
+		 * so we wait for the error
+		 */
+		n = read(mfd[0], mdata, sizeof mdata);
+		if(n == 0)
+			continue;
+		if(n < 0)
+			error("mount read");
+		if(convM2S(mdata, &rhdr, n) == 0)
+			continue;
+
+		if(debug)
+			fprint(2, "sacfs:<-%F\n", &rhdr);
+
+		thdr.data = mdata + MAXMSG;
+		if(!fcalls[rhdr.type])
+			err = "bad fcall type";
+		else
+			err = (*fcalls[rhdr.type])(newfid(rhdr.fid));
+		if(err){
+			thdr.type = Rerror;
+			strncpy(thdr.ename, err, ERRLEN);
+		}else{
+			thdr.type = rhdr.type + 1;
+			thdr.fid = rhdr.fid;
+		}
+		thdr.tag = rhdr.tag;
+		if(debug)
+			fprint(2, "ramfs:->%F\n", &thdr);/**/
+		n = convS2M(&thdr, mdata);
+		if(write(mfd[1], mdata, n) != n)
+			error("mount write");
+	}
+}
+
+int
+perm(Fid *f, Sac *s, int p)
+{
+	ulong perm = getl(s->mode);
+	if((p*Pother) & perm)
+		return 1;
+	if(strcmp(f->user, s->gid)==0 && ((p*Pgroup) & perm))
+		return 1;
+	if(strcmp(f->user, s->uid)==0 && ((p*Powner) & perm))
+		return 1;
+	return 0;
+}
+
+void
+init(char *file)
+{
+	SacHeader *hdr;
+	Dir dir;
+	int fd;
+	int i;
+	uchar *p;
+
+	notify(notifyf);
+	strcpy(user, getuser());
+
+
+	if(dirstat(file, &dir) < 0)
+		error("bad file");
+	data = emalloc(dir.length);
+	fd = open(file, OREAD);
+	if(fd < 0)
+		error("opening file");
+	if(read(fd, data, dir.length) < dir.length)
+		error("reading file");
+	hdr = (SacHeader*)data;
+	if(getl(hdr->magic) != Magic)
+		error("bad magic");
+	if(getl(hdr->length) != (ulong)(dir.length))
+		error("bad length");
+	blocksize = getl(hdr->blocksize);
+	root.SacDir = *(SacDir*)(data + sizeof(SacHeader));
+	p = malloc(CacheSize*blocksize);
+	if(p == nil)
+		error("allocating cache");
+	for(i=0; i<CacheSize; i++) {
+		cache[i].data = p;
+		p += blocksize;
+	}
+}
+
+void
+error(char *s)
+{
+	fprint(2, "%s: %s: %r\n", argv0, s);
+	exits(s);
+}
+
+void *
+emalloc(ulong n)
+{
+	void *p;
+
+	p = malloc(n);
+	if(!p)
+		error("out of memory");
+	return p;
+}
+
+void *
+erealloc(void *p, ulong n)
+{
+	p = realloc(p, n);
+	if(!p)
+		error("out of memory");
+	return p;
+}
+
+void
+usage(void)
+{
+	fprint(2, "usage: %s [-i infd outfd] [-s] [-m mountpoint] sacfsfile\n", argv0);
+	exits("usage");
+}
+
+ulong
+getl(void *p)
+{
+	uchar *a = p;
+
+	return (a[0]<<24) | (a[1]<<16) | (a[2]<<8) | a[3];
+}
+
diff --git a/sys/src/cmd/disk/sacfs/sacfs.h b/sys/src/cmd/disk/sacfs/sacfs.h
new file mode 100755
index 000000000..90c8b6ee8
--- /dev/null
+++ b/sys/src/cmd/disk/sacfs/sacfs.h
@@ -0,0 +1,29 @@
+typedef struct SacHeader SacHeader;
+typedef struct SacDir SacDir;
+
+enum {
+	Magic = 0x5acf5,
+	NAMELEN = 28,
+};
+
+struct SacDir
+{
+	char	name[NAMELEN];
+	char	uid[NAMELEN];
+	char	gid[NAMELEN];
+	uchar	qid[4];
+	uchar	mode[4];
+	uchar	atime[4];
+	uchar	mtime[4];
+	uchar	length[8];
+	uchar	blocks[8];
+};
+
+struct SacHeader
+{
+	uchar	magic[4];
+	uchar	length[8];
+	uchar	blocksize[4];
+	uchar	md5[16];
+};
+
diff --git a/sys/src/cmd/disk/sacfs/ssort.h b/sys/src/cmd/disk/sacfs/ssort.h
new file mode 100755
index 000000000..3f9193942
--- /dev/null
+++ b/sys/src/cmd/disk/sacfs/ssort.h
@@ -0,0 +1,2 @@
+int	ssortbyte(uchar a[], int p[], int shared[], int n);
+int	ssort(int a[], int s[], int);
diff --git a/sys/src/cmd/disk/sacfs/ssort6.c b/sys/src/cmd/disk/sacfs/ssort6.c
new file mode 100755
index 000000000..a5032ec07
--- /dev/null
+++ b/sys/src/cmd/disk/sacfs/ssort6.c
@@ -0,0 +1,419 @@
+#include <u.h>
+#include <libc.h>
+#include "ssort.h"
+
+#define pred(i, h) ((t=(i)-(h))<0?  t+n: t)
+#define succ(i, h) ((t=(i)+(h))>=n? t-n: t)
+
+enum
+{
+	BUCK = ~(~0u>>1),	/* high bit */
+	MAXI = ~0u>>1,		/* biggest int */
+};
+
+typedef int	Elem;
+static	void	qsort2(Elem*, Elem*, int n);
+static	int	ssortit(int a[], int p[], int s[], int q[], int n, int h, int *pe, int nbuck);
+static  void	lift(int si, int q[], int i);
+int	sharedlen(int i, int j, int s[], int q[]);
+
+int
+ssort(int a[], int s[], int n)
+{
+	int i, l;
+	int c, cc, ncc, lab, cum, nbuck;
+	int k;
+	int *p = 0;
+	int result = 0;
+	int *q = 0;
+	int *al;
+	int *pl;
+
+#	define finish(r)  if(1){result=r; goto out;}else
+
+	for(k=0,i=0; i<n; i++)	
+		if(a[i] > k)
+			k = a[i];	/* max element */
+	k++;
+	if(k>n)
+		finish(2);
+
+	nbuck = 0;
+	p = malloc(n*sizeof(int));
+	if(p == 0)
+		finish(1);
+
+	if(s) {					/* shared lengths */
+		q = malloc(((n+1)>>1)*sizeof(int));
+		if(q == 0)
+			finish(1);
+		for(i=0; i<n; i++)
+			s[i] = q[i>>1] = MAXI;
+		q[i>>1] = MAXI;
+	}
+
+	pl = p + n - k;
+	al = a;
+	memset(pl, -1, k*sizeof(int));
+
+	for(i=0; i<n; i++) {		/* (1) link */
+		l = a[i];
+		al[i] = pl[l];
+		pl[l] = i;
+	}
+
+	for(i=0; i<k; i++)		/* check input - no holes */
+		if(pl[i]<0)
+			finish(2);
+
+	
+	lab = 0;			/* (2) create p and label a */
+	cum = 0;
+	i = 0;
+	for(c = 0; c < k; c++){	
+		for(cc = pl[c]; cc != -1; cc = ncc){
+			ncc = al[cc];
+			al[cc] = lab;
+			cum++;
+			p[i++] = cc;
+		}
+		if(lab + 1 == cum) {
+			i--;
+		} else {
+			p[i-1] |= BUCK;
+			nbuck++;
+		}
+		if(s) {
+			s[lab] = 0;
+			lift(0, q, lab);
+		}
+		lab = cum;
+	}
+
+	ssortit(a, p, s, q, n, 1, p+i, nbuck);
+	memcpy(a, p, n*sizeof(int));
+	
+out:
+	free(p);
+	free(q);
+	return result;
+}
+
+/*
+ * calculate the suffix array for the bytes in buf,
+ * terminated by a unique end marker less than any character in buf
+ * returns the index of the identity permutation,
+ * and -1 if there was an error.
+ */
+int
+ssortbyte(uchar buf[], int p[], int s[], int n)
+{
+	int *a, *q, buckets[256*256];
+	int i, last, lastc, cum, c, cc, ncc, lab, id, nbuck;
+
+	a = malloc((n+1)*sizeof(int));
+	if(a == nil)
+		return -1;
+
+	q = nil;
+	if(s) {					/* shared lengths */
+		q = malloc(((n+2)>>1)*sizeof(int));
+		if(q == nil){
+			free(a);
+			return -1;
+		}
+		for(i=0; i<n+1; i++)
+			s[i] = q[i>>1] = MAXI;
+		q[i>>1] = MAXI;
+	}
+
+	memset(buckets, -1, sizeof(buckets));
+	c = buf[n-1] << 8;
+	last = c;
+	for(i = n - 2; i >= 0; i--){
+		c = (buf[i] << 8) | (c >> 8);
+		a[i] = buckets[c];
+		buckets[c] = i;
+	}
+
+	/*
+	 * end of string comes before anything else
+	 */
+	a[n] = 0;
+	if(s) {
+		s[0] = 0;
+		lift(0, q, 0);
+	}
+
+	lab = 1;
+	cum = 1;
+	i = 0;
+	lastc = 1;		/* won't match c & 0xff00 for any c */
+	nbuck = 0;
+	for(c = 0; c < 256*256; c++) {
+		/*
+		 * last character is followed by unique end of string
+		 */
+		if(c == last) {
+			a[n-1] = lab;
+			if(s) {
+				s[lab] = 0;
+				lift(0, q, lab);
+			}
+			cum++;
+			lab++;
+			lastc = c & 0xff00;
+		}
+
+		for(cc = buckets[c]; cc != -1; cc = ncc) {
+			ncc = a[cc];
+			a[cc] = lab;
+			cum++;
+			p[i++] = cc;
+		}
+		if(lab == cum)
+			continue;
+		if(lab + 1 == cum)
+			i--;
+		else {
+			p[i - 1] |= BUCK;
+			nbuck++;
+		}
+		if(s) {
+			cc = (c & 0xff00) == lastc;
+			s[lab] = cc;
+			lift(cc, q, lab);
+		}
+		lastc = c & 0xff00;
+		lab = cum;
+	}
+
+	id = ssortit(a, p, s, q, n+1, 2, p+i, nbuck);
+	free(a);
+	free(q);
+	return id;
+}
+
+/*
+ * can get an interval for the shared lengths from [h,3h) by recording h
+ * rather than h + sharedlen(..) when relabelling.  if so, no calls to lift are needed.
+ */
+static int
+ssortit(int a[], int p[], int shared[], int q[], int n, int h, int *pe, int nbuck)
+{
+	int *s, *ss, *packing, *sorting;
+	int v, sv, vv, packed, lab, t, i;
+
+	for(; h < n && p < pe; h=2*h) {
+		packing = p;
+		nbuck = 0;
+
+		for(sorting = p; sorting < pe; sorting = s){
+			/*
+			 * find length of stuff to sort
+			 */
+			lab = a[*sorting];
+			for(s = sorting; ; s++) {
+				sv = *s;
+				v = a[succ(sv & ~BUCK, h)];
+				if(v & BUCK)
+					v = lab;
+				a[sv & ~BUCK] = v | BUCK;
+				if(sv & BUCK)
+					break;
+			}
+			*s++ &= ~BUCK;
+			nbuck++;
+
+			qsort2(sorting, a, s - sorting);
+
+			v = a[*sorting];
+			a[*sorting] = lab;
+			packed = 0;
+			for(ss = sorting + 1; ss < s; ss++) {
+				sv = *ss;
+				vv = a[sv];
+				if(vv == v) {
+					*packing++ = ss[-1];
+					packed++;
+				} else {
+					if(packed) {
+						*packing++ = ss[-1] | BUCK;
+					}
+					lab += packed + 1;
+					if(shared) {
+						v = h + sharedlen(v&~BUCK, vv&~BUCK, shared, q);
+						shared[lab] = v;
+						lift(v, q, lab);
+					}
+					packed = 0;
+					v = vv;
+				}
+				a[sv] = lab;
+			}
+			if(packed) {
+				*packing++ = ss[-1] | BUCK;
+			}
+		}
+		pe = packing;
+	}
+
+	/*
+	 * reconstuct the permutation matrix
+	 * return index of the entire string
+	 */
+	v = a[0];
+	for(i = 0; i < n; i++)
+		p[a[i]] = i;
+
+	return v;
+}
+
+/* Propagate a new entry s[i], with value si, into q[]. */
+static void
+lift(int si, int q[], int i)
+{
+	for(i >>= 1; q[i] > si; i &= ~-i)		/* squash the low 1-bit */
+		q[i] = si;
+}
+
+/*
+ * Find in s[] the minimum value over the interval i<=k<=j, using
+ * tree q[] to do logarithmic, rather than linear search
+ */
+int
+sharedlen(int i, int j, int s[], int q[])
+{
+	int k, v;
+	int min = MAXI;
+	int max = 0;
+
+	if(i > j) {		/* swap i & j */
+		i ^= j;
+		j ^= i;
+		i ^= j;
+	}
+	i++;
+	while(i <= j && min > max) {
+		k = i & -i;
+		if(i & 1)
+			v = s[i];
+		else
+			v = q[i>>1];
+		if(i+k > j+1) {
+			if(v > max)
+				max = v;
+			if(s[i] < min)
+				min = s[i];
+			i++;
+		} else {
+			if(v < min)
+				min = v;
+			i += k;
+		}
+	}
+	return min;
+}
+
+/*
+ * qsort specialized for sorting permutations based on successors
+ */
+static void
+vecswap2(Elem *a, Elem *b, int n)
+{
+	while (n-- > 0) {
+        	Elem t = *a;
+		*a++ = *b;
+		*b++ = t;
+	}
+}
+
+#define swap2(a, b) { t = *(a); *(a) = *(b); *(b) = t; }
+#define ptr2char(i, asucc) (asucc[*(i)])
+
+static Elem*
+med3(Elem *a, Elem *b, Elem *c, Elem *asucc)
+{
+	Elem va, vb, vc;
+
+	if ((va=ptr2char(a, asucc)) == (vb=ptr2char(b, asucc)))
+		return a;
+	if ((vc=ptr2char(c, asucc)) == va || vc == vb)
+		return c;	   
+	return va < vb ?
+		  (vb < vc ? b : (va < vc ? c : a))
+		: (vb > vc ? b : (va < vc ? a : c));
+}
+
+static void
+inssort(Elem *a, Elem *asucc, int n)
+{
+	Elem *pi, *pj, t;
+
+	for (pi = a + 1; --n > 0; pi++)
+		for (pj = pi; pj > a; pj--) {
+			if(ptr2char(pj-1, asucc) <= ptr2char(pj, asucc))
+				break;
+			swap2(pj, pj-1);
+		}
+}
+
+static void
+qsort2(Elem *a, Elem *asucc, int n)
+{
+	Elem d, r, partval;
+	Elem *pa, *pb, *pc, *pd, *pl, *pm, *pn, t;
+
+	if (n < 15) {
+		inssort(a, asucc, n);
+		return;
+	}
+	pl = a;
+	pm = a + (n >> 1);
+	pn = a + (n-1);
+	if (n > 30) { /* On big arrays, pseudomedian of 9 */
+		d = (n >> 3);
+		pl = med3(pl, pl+d, pl+2*d, asucc);
+		pm = med3(pm-d, pm, pm+d, asucc);
+		pn = med3(pn-2*d, pn-d, pn, asucc);
+	}
+	pm = med3(pl, pm, pn, asucc);
+	swap2(a, pm);
+	partval = ptr2char(a, asucc);
+	pa = pb = a + 1;
+	pc = pd = a + n-1;
+	for (;;) {
+		while (pb <= pc && (r = ptr2char(pb, asucc)-partval) <= 0) {
+			if (r == 0) {
+				swap2(pa, pb);
+				pa++;
+			}
+			pb++;
+		}
+		while (pb <= pc && (r = ptr2char(pc, asucc)-partval) >= 0) {
+			if (r == 0) {
+				swap2(pc, pd);
+				pd--;
+			}
+			pc--;
+		}
+		if (pb > pc)
+			break;
+		swap2(pb, pc);
+		pb++;
+		pc--;
+	}
+	pn = a + n;
+	r = pa-a;
+	if(pb-pa < r)
+		r = pb-pa;
+	vecswap2(a, pb-r, r);
+	r = pn-pd-1;
+	if(pd-pc < r)
+		r = pd-pc;
+	vecswap2(pb, pn-r, r);
+	if ((r = pb-pa) > 1)
+		qsort2(a, asucc, r);
+	if ((r = pd-pc) > 1)
+		qsort2(a + n-r, asucc, r);
+}
diff --git a/sys/src/cmd/disk/sacfs/unsac.c b/sys/src/cmd/disk/sacfs/unsac.c
new file mode 100755
index 000000000..e3f1ab09c
--- /dev/null
+++ b/sys/src/cmd/disk/sacfs/unsac.c
@@ -0,0 +1,620 @@
+#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);
+}