## diffname mpc/unsac.c 1999/0608
## diff -e /dev/null /n/emeliedump/1999/0608/sys/src/brazil/mpc/unsac.c
0a
#include "u.h"
#include "../port/lib.h"
#include "mem.h"
#include "dat.h"
#include "fns.h"
#include "io.h"
typedef struct Huff Huff;
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 = 15, /* max bits in a huffman code */
MaxSelHuffBits = 15, /* max bits for a table selector huffman code */
Nhuffblock = 16*1024, /* symbols encoded before output */
Nhuffslop = 64, /* slop for stuffing zeros, etc. */
};
struct Huff
{
int minbits;
int maxbits;
int flatbits;
ulong flat[1<<8];
ulong maxcode[MaxHuffBits+1];
ulong last[MaxHuffBits+1];
ulong decode[MaxLeaf];
};
struct Decode{
Huff tab;
int ndec;
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 hflush(Decode*);
static void hbflush(Decode*);
static ulong bitget(Decode*, int);
static int mtf(uchar*, int);
int
unsac(uchar *dst, uchar *src, int n, int nsrc)
{
Decode dec;
uchar *buf, front[256];
ulong *suflink, sums[256];
ulong sum;
int i, m, I, j, c;
buf = malloc(n+2);
suflink = malloc((n+2) * sizeof *suflink);
if(waserror()) {
free(buf);
free(suflink);
nexterror();
}
dec.src = src;
dec.smax = src + nsrc;
dec.nbits = 0;
dec.bits = 0;
dec.nzero = 0;
for(i = 0; i < 256; i++)
front[i] = i;
n++;
I = bitget(&dec, 16);
if(I >= n)
fatal(&dec, "corrupted input file: n=%d I=%d", n, I);
/*
* decode the character usage map
*/
for(i = 0; i < 256; i++)
sums[i] = 0;
c = bitget(&dec, 1);
for(i = 0; i < 256; ){
m = bitget(&dec, 8) + 1;
while(m--){
if(i >= 256)
fatal(&dec, "bad format encoding char map %d", m);
front[i++] = c;
}
c = c ^ 1;
}
/*
* initialize mtf state
*/
c = 0;
for(i = 0; i < 256; i++)
if(front[i])
front[c++] = i;
dec.maxblocksym = c + LitBase;
/*
* huffman decoding, move to front decoding,
* along with character counting
*/
hbflush(&dec);
for(i = 0; i < n; i++){
if(i == I)
continue;
m = hdec(&dec);
/*
* move to front
*/
c = front[m];
for(; m > 0; m--)
front[m] = front[m-1];
front[0] = c;
buf[i] = c;
sums[c]++;
}
sum = 1;
for(i = 0; i < 256; i++){
c = sums[i];
sums[i] = sum;
sum += c;
}
/*
* calculate the row step for column step array
* by calculating it for backwards moves and inverting it
*/
suflink[0] = I;
for(j = 0; j < I; j++)
suflink[sums[buf[j]]++] = j;
for(j++; j < n; j++)
suflink[sums[buf[j]]++] = j;
/*
* to recover the suffix array, aka suffix array for input
* j = 0;
* for(i = I; i != 0; i = suflink[i])
* sarray[i] = j++;
* sarray[i] = j++;
* note that suflink[i] = sarrayinv[sarray[i] + 1]
*/
/*
* produce the decoded data forwards
*/
n--;
i = I;
for(j = 0; j < n; j++){
i = suflink[i];
dst[j] = buf[i];
}
poperror();
free(buf);
free(suflink);
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: nbits %d", dec->nbits);
c = *dec->src++;
dec->bits <<= 8;
dec->bits |= c;
dec->nbits += 8;
}
}
/*
* decode one symbol
*/
static int
hdecsym(Decode *dec, Huff *h)
{
long c;
int b;
dec->bits &= (1 << dec->nbits) - 1;
for(b = h->flatbits; (c = dec->bits >> (dec->nbits - b)) > h->maxcode[b]; b++)
;
if(b > h->maxbits)
fatal(dec, "too many bits consumed: b=%d minbits=%d maxbits=%d", b, h->minbits, h->maxbits);
dec->nbits -= b;
c = h->decode[h->last[b] - c];
return c;
}
static int
hdec(Decode *dec)
{
ulong c;
dec->ndec++;
if(dec->nzero){
dec->nzero--;
return 0;
}
if(dec->nbits < dec->tab.maxbits)
fillbits(dec);
dec->bits &= (1 << dec->nbits) - 1;
c = dec->tab.flat[dec->bits >> (dec->nbits - dec->tab.flatbits)];
if(c == ~0)
c = hdecsym(dec, &dec->tab);
else{
dec->nbits -= c & 0xff;
c >>= 8;
}
/*
* reverse funny run-length coding
*/
if(c < ZBase){
dec->nzero = dec->base << c;
dec->base <<= 1;
dec->nzero--;
return 0;
}
dec->base = 1;
c -= LitBase;
return c;
}
static void
hbflush(Decode *dec)
{
dec->base = 1;
dec->ndec = 0;
hflush(dec);
}
static void
hufftab(Decode *dec, Huff *h, ulong *hb, ulong *bitcount, int maxleaf, int maxbits, int flatbits)
{
ulong c, code, nc[MaxHuffBits+1];
int i, b, ec;
code = 0;
c = 0;
h->minbits = maxbits;
for(b = 1; b <= maxbits; b++){
h->last[b] = c;
if(c == 0)
h->minbits = b;
c += bitcount[b];
nc[b] = code << 1;
code = (code << 1) + 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 %d %d", code, 1<<maxbits);
h->maxbits = b;
if(flatbits > b)
flatbits = b;
h->flatbits = flatbits;
b = 1 << flatbits;
for(i = 0; i < b; i++)
h->flat[i] = ~0;
for(i = 0; i < maxleaf; i++){
b = hb[i];
if(b == 0)
continue;
c = nc[b]++;
if(b <= flatbits){
if(c > (1<<(b+1)))fatal(dec, "xx1");
code = (i << 8) | b;
ec = (c + 1) << (flatbits - b);
if(ec > (1<<flatbits))
fatal(dec, "too big: ec=%d c=%d %d b=%d nc=%d\n", ec, c, c & ((1<<b)-1), b, nc[b]);
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: c=%d maxleaf=%d i=%d b=%d maxbits=%d last=%d, nc=%d",
c, maxleaf, i, b, maxbits, h->last[b], nc[b]);
h->decode[c] = i;
}
}
}
static void
hflush(Decode *dec)
{
Huff codetab;
ulong bitcount[MaxHuffBits+1], hb[MaxLeaf];
uchar tmtf[MaxHuffBits+1];
int i, b, m, maxbits;
/*
* read the tables for the tables
*/
for(i = 0; i <= MaxHuffBits; i++)
bitcount[i] = 0;
maxbits = 0;
for(i = 0; i <= MaxHuffBits; i++){
b = bitget(dec, 4);
hb[i] = b;
bitcount[b]++;
if(b > maxbits)
maxbits = b;
}
hufftab(dec, &codetab, hb, bitcount, MaxHuffBits+1, maxbits, 8);
for(i = 0; i <= MaxHuffBits; i++)
tmtf[i] = i;
for(i = 0; i <= MaxHuffBits; i++)
bitcount[i] = 0;
maxbits = 0;
for(i = 0; i < dec->maxblocksym; i++){
if(dec->nbits <= codetab.maxbits)
fillbits(dec);
dec->bits &= (1 << dec->nbits) - 1;
m = codetab.flat[dec->bits >> (dec->nbits - codetab.flatbits)];
if(m == ~0)
m = hdecsym(dec, &codetab);
else{
dec->nbits -= m & 0xff;
m >>= 8;
}
b = tmtf[m];
for(; m > 0; m--)
tmtf[m] = tmtf[m-1];
tmtf[0] = b;
if(b > MaxHuffBits)
fatal(dec, "bit length %d too large, max %d i %d maxval %d", b, MaxHuffBits, i, dec->maxblocksym);
hb[i] = b;
bitcount[b]++;
if(b > maxbits)
maxbits = b;
}
for(; i < MaxLeaf; i++)
hb[i] = 0;
hufftab(dec, &dec->tab, hb, bitcount, MaxLeaf, maxbits, 8);
}
static void
fatal(Decode *dec, char *fmt, ...)
{
char buf[128];
va_list arg;
va_start(arg, fmt);
doprint(buf, buf+sizeof(buf), fmt, arg);
va_end(arg);
print("devsac: %s\n", buf);
error(buf);
}
.
## diffname mpc/unsac.c 1999/0609
## diff -e /n/emeliedump/1999/0608/sys/src/brazil/mpc/unsac.c /n/emeliedump/1999/0609/sys/src/brazil/mpc/unsac.c
46,47d
## diffname mpc/unsac.c 1999/0610
## diff -e /n/emeliedump/1999/0609/sys/src/brazil/mpc/unsac.c /n/emeliedump/1999/0610/sys/src/brazil/mpc/unsac.c
390,398c
USED(dec);
print("unsac: %s\n", msg);
error(msg);
.
388c
fatal(Decode *dec, char *msg)
.
384c
hufftab(dec, &dec->tab, hb, bitcount, MaxLeaf, maxbits, MaxFlatbits);
poperror();
free(hb);
.
375c
fatal(dec, "bit length too big");
.
364c
m = hdecsym(dec, &dec->tab);
.
362c
m = dec->tab.flat[dec->bits >> (dec->nbits - dec->tab.flatbits)];
.
359c
if(dec->nbits <= dec->tab.maxbits)
.
356a
}
.
355d
352,353c
hufftab(dec, &dec->tab, hb, bitcount, MaxHuffBits+1, maxbits, MaxFlatbits);
for(i = 0; i <= MaxHuffBits; i++){
.
338a
dec->base = 1;
dec->ndec = 0;
hb = malloc(MaxLeaf * sizeof *hb);
if(waserror()) {
free(hb);
nexterror();
}
.
334,336c
ulong bitcount[MaxHuffBits+1];
uchar tmtf[MaxHuffBits+1], *hb;
.
332c
hbflush(Decode *dec)
.
324,325c
fatal(dec, "corrupted huffman table");
.
318c
fatal(dec, "flat code too big");
.
314d
298c
fatal(dec, "huffman table not full");
.
271,278d
269c
hufftab(Decode *dec, Huff *h, uchar *hb, ulong *bitcount, int maxleaf, int maxbits, int flatbits)
.
224c
fatal(dec, "too many bits consumed");
.
203c
fatal(dec, "premature eof 2");
.
175a
free(front);
free(sums);
.
173a
free(dec);
.
123c
m = hdec(dec);
.
119c
hbflush(dec);
.
113c
dec->maxblocksym = c + LitBase;
.
100c
fatal(dec, "corrupted char map");
.
97c
m = bitget(dec, 8) + 1;
.
95c
c = bitget(dec, 1);
.
88c
fatal(dec, "corrupted input");
.
86c
I = bitget(dec, 16);
.
79,81c
dec->nbits = 0;
dec->bits = 0;
dec->nzero = 0;
.
76,77c
dec->src = src;
dec->smax = src + nsrc;
.
72a
free(front);
free(sums);
.
70c
if(waserror()){
free(dec);
.
68a
front = malloc(256 * sizeof *front);
sums = malloc(256 * sizeof *sums);
.
66a
dec = malloc(sizeof *dec);
.
61,63c
Decode *dec;
uchar *buf, *front;
ulong *suflink, *sums;
.
53d
50c
static void fatal(Decode *dec, char*);
.
31c
ulong flat[1<<MaxFlatbits];
.
20c
MaxFlatbits = 4, /* max bits decoded in flat table */
.
## diffname mpc/unsac.c 1999/0812
## diff -e /n/emeliedump/1999/0610/sys/src/brazil/mpc/unsac.c /n/emeliedump/1999/0812/sys/src/brazil/mpc/unsac.c
390c
hufftab(dec, tab, hb, bitcount, i, maxbits, MaxFlatbits);
.
387,388c
if(elim != MaxHuffBits && elim != 0)
fatal(dec, "incomplete huffman table");
if(map != nil)
for(; i < maxleaf; i++)
hb[map[i]] = -1;
.
385a
elim += elimBits(b, bused, tmtf, MaxHuffBits);
.
382c
m = i;
if(map != nil)
m = map[m];
hb[m] = b;
.
370c
m = hdecsym(dec, tab);
.
368c
m = tab->flat[dec->bits >> (dec->nbits - tab->flatbits)];
.
363,365c
tmtf[0] = -1;
tmtf[MaxHuffBits] = 0;
elim = 0;
maxbits = -1;
for(i = 0; i < maxleaf && elim != MaxHuffBits; i++){
if(dec->nbits <= tab->maxbits)
.
361a
bused[i] = 0;
.
358c
if(elim != max)
fatal(dec, "incomplete huffman table table");
hufftab(dec, tab, hb, bitcount, i, maxbits, MaxFlatbits);
.
356a
elim += elimBits(b, bused, tmtf, max);
.
352c
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];
.
348,350c
max = 8;
.
338a
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;
.
336,337c
for(bb = 0; bb < maxbits; bb++)
if(tmtf[bb] == b)
break;
while(++bb <= maxbits)
tmtf[bb - 1] = tmtf[bb];
}
.
332,334c
int bb;
.
330c
elimBit(int b, char *tmtf, int maxbits)
.
310c
if(b == -1)
.
299,301c
if(flatbits > maxbits)
flatbits = maxbits;
.
287,288d
284,285c
for(b = 0; b <= maxbits; b++){
.
281a
h->maxbits = maxbits;
if(maxbits < 0)
return;
.
279c
ulong c, code, nc[MaxHuffBits];
.
277c
hufftab(Decode *dec, Huff *h, char *hb, ulong *bitcount, int maxleaf, int maxbits, int flatbits)
.
267d
265c
dec->nzero += dec->base << c;
.
257c
dec->nbits = nbits - (c & 0xff);
.
252,253c
nbits = dec->nbits;
dec->bits &= (1 << nbits) - 1;
c = dec->tab.flat[dec->bits >> (nbits - dec->tab.flatbits)];
.
244,249d
242a
int nbits;
.
233,236c
dec->nbits = nbits;
return h->decode[h->last[b] - c];
.
228,230c
bits = dec->bits;
b = h->flatbits;
nbits = dec->nbits - b;
for(; (c = bits >> nbits) > h->maxcode[b]; b++)
nbits--;
.
226c
ulong bits;
int b, nbits;
.
181c
free(prev);
.
178a
.
149,175c
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];
.
143c
for(i = 0; i < MaxLit; i++){
.
130,141d
124,128c
dec->base = 1;
recvtab(dec, &dec->tab, MaxLeaf, nil);
hdecblock(dec, n, I, buf, sums, prev);
.
117a
mtflistinit(&dec->mtf, front, c);
.
115c
for(i = 0; i < MaxLit; i++)
.
104c
if(i >= MaxLit)
.
101c
for(i = 0; i < MaxLit; ){
.
98c
for(i = 0; i < MaxLit; i++)
.
87c
for(i = 0; i < MaxLit; i++)
.
75c
free(prev);
.
68,70c
prev = malloc((n+2) * sizeof *prev);
front = malloc(MaxLit * sizeof *front);
sums = malloc(MaxLit * sizeof *sums);
.
62,64c
ulong *prev, *sums;
ulong sum, i, I;
int m, j, c;
.
57a
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
.
56a
#define FORWARD 0
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;
}
.
53c
static void recvtab(Decode*, Huff*, int, ushort*);
.
39c
Mtf mtf;
.
32,33c
ulong maxcode[MaxHuffBits];
ulong last[MaxHuffBits];
.
28d
25a
struct Mtf
{
int maxcomb; /* index of last valid comb */
uchar prev[MaxLit];
uchar next[MaxLit];
uchar comb[MaxLit / CombSpace + 1];
};
.
22,23c
CombLog = 4,
CombSpace = 1 << CombLog, /* mtf speedup indices spacing */
CombMask = CombSpace - 1,
.
19,20c
MaxHuffBits = 16, /* max bits in a huffman code */
MaxFlatbits = 5, /* max bits decoded in flat table */
.
9c
typedef struct Mtf Mtf;
.
## diffname mpc/unsac.c 2000/0729
## diff -e /n/emeliedump/1999/0812/sys/src/brazil/mpc/unsac.c /n/emeliedump/2000/0729/sys/src/9/mpc/unsac.c
572,577c
b = m & 0xff;
m >>= 8;
if(b == 0xff)
m = hdecsym(dec, tab, m);
else
dec->nbits -= b;
.
444a
/*
* 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];
mincode = code + 1 - bitcount[b];
mincode >>= b - flatbits;
code >>= b - flatbits;
for(; code >= mincode; code--)
h->flat[code] = (b << 8) | 0xff;
}
.
428,429c
mincode = code << 1;
nc[b] = mincode;
code = mincode + bitcount[b];
.
416c
ulong c, mincode, code, nc[MaxHuffBits];
.
392,397c
nb = c & 0xff;
c >>= 8;
if(nb == 0xff)
c = hdecsym(dec, &dec->tab, c);
else
dec->nbits = nbits - nb;
.
385c
int nbits, nb;
.
377c
dec->nbits = nbits - b;
.
371,374c
nbits = dec->nbits;
for(; (c = bits >> (nbits - b)) > h->maxcode[b]; b++)
;
.
368c
int nbits;
.
364c
hdecsym(Decode *dec, Huff *h, int b)
.
128c
static int
.
67c
static void
.
## diffname mpc/unsac.c 2000/0811
## diff -e /n/emeliedump/2000/0729/sys/src/9/mpc/unsac.c /n/emeliedump/2000/0811/sys/src/9/mpc/unsac.c
454,455c
for(; mincode <= code; mincode++)
h->flat[mincode] = (b << 8) | 0xff;
.
450a
if(code == -1)
break;
.
## diffname mpc/unsac.c 2001/0527 # deleted
## diff -e /n/emeliedump/2000/0811/sys/src/9/mpc/unsac.c /n/emeliedump/2001/0527/sys/src/9/mpc/unsac.c
1,627d
|
