#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);
}

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.