sys/src/cmd/disk/sacfs/unsac.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include "sac.h"
   4
   5 typedef struct Huff     Huff;
   6 typedef struct Mtf      Mtf;
   7 typedef struct Decode   Decode;
   8
   9 enum
  10 {
  11         ZBase           = 2,                    /* base of code to encode 0 runs */
  12         LitBase         = ZBase-1,              /* base of literal values */
  13         MaxLit          = 256,
  14
  15         MaxLeaf         = MaxLit+LitBase,
  16         MaxHuffBits     = 16,                   /* max bits in a huffman code */
  17         MaxFlatbits     = 5,                    /* max bits decoded in flat table */
  18
  19         CombLog         = 4,
  20         CombSpace       = 1 << CombLog,         /* mtf speedup indices spacing */
  21         CombMask        = CombSpace - 1,
  22 };
  23
  24 struct Mtf
  25 {
  26         int     maxcomb;                /* index of last valid comb */
  27         uchar   prev[MaxLit];
  28         uchar   next[MaxLit];
  29         uchar   comb[MaxLit / CombSpace + 1];
  30 };
  31
  32 struct Huff
  33 {
  34         int     maxbits;
  35         int     flatbits;
  36         ulong   flat[1<<MaxFlatbits];
  37         ulong   maxcode[MaxHuffBits];
  38         ulong   last[MaxHuffBits];
  39         ulong   decode[MaxLeaf];
  40 };
  41
  42 struct Decode{
  43         Huff    tab;
  44         Mtf     mtf;
  45         int     nbits;
  46         ulong   bits;
  47         int     nzero;
  48         int     base;
  49         ulong   maxblocksym;
  50
  51         jmp_buf errjmp;
  52
  53         uchar   *src;                           /* input buffer */
  54         uchar   *smax;                          /* limit */
  55 };
  56
  57 static  void    fatal(Decode *dec, char*);
  58
  59 static  int     hdec(Decode*);
  60 static  void    recvtab(Decode*, Huff*, int, ushort*);
  61 static  ulong   bitget(Decode*, int);
  62 static  int     mtf(uchar*, int);
  63
  64 #define FORWARD 0
  65
  66 static void
  67 mtflistinit(Mtf *m, uchar *front, int n)
  68 {
  69         int last, me, f, i, comb;
  70
  71         if(n == 0)
  72                 return;
  73
  74         /*
  75          * add all entries to free list
  76          */
  77         last = MaxLit - 1;
  78         for(i = 0; i < MaxLit; i++){
  79                 m->prev[i] = last;
  80                 m->next[i] = i + 1;
  81                 last = i;
  82         }
  83         m->next[last] = 0;
  84         f = 0;
  85
  86         /*
  87          * pull valid entries off free list and enter into mtf list
  88          */
  89         comb = 0;
  90         last = front[0];
  91         for(i = 0; i < n; i++){
  92                 me = front[i];
  93
  94                 f = m->next[me];
  95                 m->prev[f] = m->prev[me];
  96                 m->next[m->prev[f]] = f;
  97
  98                 m->next[last] = me;
  99                 m->prev[me] = last;
 100                 last = me;
 101                 if((i & CombMask) == 0)
 102                         m->comb[comb++] = me;
 103         }
 104
 105         /*
 106          * pad out the list with dummies to the next comb,
 107          * using free entries
 108          */
 109         for(; i & CombMask; i++){
 110                 me = f;
 111
 112                 f = m->next[me];
 113                 m->prev[f] = m->prev[me];
 114                 m->next[m->prev[f]] = f;
 115
 116                 m->next[last] = me;
 117                 m->prev[me] = last;
 118                 last = me;
 119         }
 120         me = front[0];
 121         m->next[last] = me;
 122         m->prev[me] = last;
 123         m->comb[comb] = me;
 124         m->maxcomb = comb;
 125 }
 126
 127 static int
 128 mtflist(Mtf *m, int pos)
 129 {
 130         uchar *next, *prev, *mycomb;
 131         int c, c0, pc, nc, off;
 132
 133         if(pos == 0)
 134                 return m->comb[0];
 135
 136         next = m->next;
 137         prev = m->prev;
 138         mycomb = &m->comb[pos >> CombLog];
 139         off = pos & CombMask;
 140         if(off >= CombSpace / 2){
 141                 c = mycomb[1];
 142                 for(; off < CombSpace; off++)
 143                         c = prev[c];
 144         }else{
 145                 c = *mycomb;
 146                 for(; off; off--)
 147                         c = next[c];
 148         }
 149
 150         nc = next[c];
 151         pc = prev[c];
 152         prev[nc] = pc;
 153         next[pc] = nc;
 154
 155         for(; mycomb > m->comb; mycomb--)
 156                 *mycomb = prev[*mycomb];
 157         c0 = *mycomb;
 158         *mycomb = c;
 159         mycomb[m->maxcomb] = c;
 160
 161         next[c] = c0;
 162         pc = prev[c0];
 163         prev[c] = pc;
 164         prev[c0] = c;
 165         next[pc] = c;
 166         return c;
 167 }
 168
 169 static void
 170 hdecblock(Decode *dec, ulong n, ulong I, uchar *buf, ulong *sums, ulong *prev)
 171 {
 172         ulong i, nn, sum;
 173         int m, z, zz, c;
 174
 175         nn = I;
 176         n--;
 177         i = 0;
 178 again:
 179         for(; i < nn; i++){
 180                 while((m = hdec(dec)) == 0 && i + dec->nzero < n)
 181                         ;
 182                 if(z = dec->nzero){
 183                         dec->nzero = 0;
 184                         c = dec->mtf.comb[0];
 185                         sum = sums[c];
 186                         sums[c] = sum + z;
 187
 188                         z += i;
 189                         zz = z;
 190                         if(i < I && z > I){
 191                                 zz = I;
 192                                 z++;
 193                         }
 194
 195                 zagain:
 196                         for(; i < zz; i++){
 197                                 buf[i] = c;
 198                                 prev[i] = sum++;
 199                         }
 200                         if(i != z){
 201                                 zz = z;
 202                                 nn = ++n;
 203                                 i++;
 204                                 goto zagain;
 205                         }
 206                         if(i == nn){
 207                                 if(i == n)
 208                                         return;
 209                                 nn = ++n;
 210                                 i++;
 211                         }
 212                 }
 213
 214                 c = mtflist(&dec->mtf, m);
 215
 216                 buf[i] = c;
 217                 sum = sums[c];
 218                 prev[i] = sum++;
 219                 sums[c] = sum;
 220
 221         }
 222         if(i == n)
 223                 return;
 224         nn = ++n;
 225         i++;
 226         goto again;
 227 }
 228
 229 int
 230 unsac(uchar *dst, uchar *src, int n, int nsrc)
 231 {
 232         Decode *dec;
 233         uchar *buf, *front;
 234         ulong *prev, *sums;
 235         ulong sum, i, I;
 236         int m, j, c;
 237
 238         dec = malloc(sizeof *dec);
 239         buf = malloc(n+2);
 240         prev = malloc((n+2) * sizeof *prev);
 241         front = malloc(MaxLit * sizeof *front);
 242         sums = malloc(MaxLit * sizeof *sums);
 243
 244         if(dec == nil || buf == nil || prev == nil || front == nil || sums == nil || setjmp(dec->errjmp)){
 245                 free(dec);
 246                 free(buf);
 247                 free(prev);
 248                 free(front);
 249                 free(sums);
 250                 return -1;
 251         }
 252
 253         dec->src = src;
 254         dec->smax = src + nsrc;
 255
 256         dec->nbits = 0;
 257         dec->bits = 0;
 258         dec->nzero = 0;
 259         for(i = 0; i < MaxLit; i++)
 260                 front[i] = i;
 261
 262         n++;
 263         I = bitget(dec, 16);
 264         if(I >= n)
 265                 fatal(dec, "corrupted input");
 266
 267         /*
 268          * decode the character usage map
 269          */
 270         for(i = 0; i < MaxLit; i++)
 271                 sums[i] = 0;
 272         c = bitget(dec, 1);
 273         for(i = 0; i < MaxLit; ){
 274                 m = bitget(dec, 8) + 1;
 275                 while(m--){
 276                         if(i >= MaxLit)
 277                                 fatal(dec, "corrupted char map");
 278                         front[i++] = c;
 279                 }
 280                 c = c ^ 1;
 281         }
 282
 283         /*
 284          * initialize mtf state
 285          */
 286         c = 0;
 287         for(i = 0; i < MaxLit; i++)
 288                 if(front[i])
 289                         front[c++] = i;
 290         mtflistinit(&dec->mtf, front, c);
 291         dec->maxblocksym = c + LitBase;
 292
 293         /*
 294          * huffman decoding, move to front decoding,
 295          * along with character counting
 296          */
 297         dec->base = 1;
 298         recvtab(dec, &dec->tab, MaxLeaf, nil);
 299         hdecblock(dec, n, I, buf, sums, prev);
 300
 301         sum = 1;
 302         for(i = 0; i < MaxLit; i++){
 303                 c = sums[i];
 304                 sums[i] = sum;
 305                 sum += c;
 306         }
 307
 308         i = 0;
 309         for(j = n - 2; j >= 0; j--){
 310                 if(i > n || i < 0 || i == I)
 311                         fatal(dec, "corrupted data");
 312                 c = buf[i];
 313                 dst[j] = c;
 314                 i = prev[i] + sums[c];
 315         }
 316
 317         free(dec);
 318         free(buf);
 319         free(prev);
 320         free(front);
 321         free(sums);
 322         return n;
 323 }
 324
 325 static ulong
 326 bitget(Decode *dec, int nb)
 327 {
 328         int c;
 329
 330         while(dec->nbits < nb){
 331                 if(dec->src >= dec->smax)
 332                         fatal(dec, "premature eof 1");
 333                 c = *dec->src++;
 334                 dec->bits <<= 8;
 335                 dec->bits |= c;
 336                 dec->nbits += 8;
 337         }
 338         dec->nbits -= nb;
 339         return (dec->bits >> dec->nbits) & ((1 << nb) - 1);
 340 }
 341
 342 static void
 343 fillbits(Decode *dec)
 344 {
 345         int c;
 346
 347         while(dec->nbits < 24){
 348                 if(dec->src >= dec->smax)
 349                         fatal(dec, "premature eof 2");
 350                 c = *dec->src++;
 351                 dec->bits <<= 8;
 352                 dec->bits |= c;
 353                 dec->nbits += 8;
 354         }
 355 }
 356
 357 /*
 358  * decode one symbol
 359  */
 360 static int
 361 hdecsym(Decode *dec, Huff *h, int b)
 362 {
 363         long c;
 364         ulong bits;
 365         int nbits;
 366
 367         bits = dec->bits;
 368         nbits = dec->nbits;
 369         for(; (c = bits >> (nbits - b)) > h->maxcode[b]; b++)
 370                 ;
 371         if(b > h->maxbits)
 372                 fatal(dec, "too many bits consumed");
 373         dec->nbits = nbits - b;
 374         return h->decode[h->last[b] - c];
 375 }
 376
 377 static int
 378 hdec(Decode *dec)
 379 {
 380         ulong c;
 381         int nbits, nb;
 382
 383         if(dec->nbits < dec->tab.maxbits)
 384                 fillbits(dec);
 385         nbits = dec->nbits;
 386         dec->bits &= (1 << nbits) - 1;
 387         c = dec->tab.flat[dec->bits >> (nbits - dec->tab.flatbits)];
 388         nb = c & 0xff;
 389         c >>= 8;
 390         if(nb == 0xff)
 391                 c = hdecsym(dec, &dec->tab, c);
 392         else
 393                 dec->nbits = nbits - nb;
 394
 395         /*
 396          * reverse funny run-length coding
 397          */
 398         if(c < ZBase){
 399                 dec->nzero += dec->base << c;
 400                 dec->base <<= 1;
 401                 return 0;
 402         }
 403
 404         dec->base = 1;
 405         c -= LitBase;
 406         return c;
 407 }
 408
 409 static void
 410 hufftab(Decode *dec, Huff *h, char *hb, ulong *bitcount, int maxleaf, int maxbits, int flatbits)
 411 {
 412         ulong c, mincode, code, nc[MaxHuffBits];
 413         int i, b, ec;
 414
 415         h->maxbits = maxbits;
 416         if(maxbits < 0)
 417                 return;
 418
 419         code = 0;
 420         c = 0;
 421         for(b = 0; b <= maxbits; b++){
 422                 h->last[b] = c;
 423                 c += bitcount[b];
 424                 mincode = code << 1;
 425                 nc[b] = mincode;
 426                 code = mincode + bitcount[b];
 427                 if(code > (1 << b))
 428                         fatal(dec, "corrupted huffman table");
 429                 h->maxcode[b] = code - 1;
 430                 h->last[b] += code - 1;
 431         }
 432         if(code != (1 << maxbits))
 433                 fatal(dec, "huffman table not full");
 434         if(flatbits > maxbits)
 435                 flatbits = maxbits;
 436         h->flatbits = flatbits;
 437
 438         b = 1 << flatbits;
 439         for(i = 0; i < b; i++)
 440                 h->flat[i] = ~0;
 441
 442         /*
 443          * initialize the flat table to include the minimum possible
 444          * bit length for each code prefix
 445          */
 446         for(b = maxbits; b > flatbits; b--){
 447                 code = h->maxcode[b];
 448                 if(code == -1)
 449                         break;
 450                 mincode = code + 1 - bitcount[b];
 451                 mincode >>= b - flatbits;
 452                 code >>= b - flatbits;
 453                 for(; mincode <= code; mincode++)
 454                         h->flat[mincode] = (b << 8) | 0xff;
 455         }
 456
 457         for(i = 0; i < maxleaf; i++){
 458                 b = hb[i];
 459                 if(b == -1)
 460                         continue;
 461                 c = nc[b]++;
 462                 if(b <= flatbits){
 463                         code = (i << 8) | b;
 464                         ec = (c + 1) << (flatbits - b);
 465                         if(ec > (1<<flatbits))
 466                                 fatal(dec, "flat code too big");
 467                         for(c <<= (flatbits - b); c < ec; c++)
 468                                 h->flat[c] = code;
 469                 }else{
 470                         c = h->last[b] - c;
 471                         if(c >= maxleaf)
 472                                 fatal(dec, "corrupted huffman table");
 473                         h->decode[c] = i;
 474                 }
 475         }
 476 }
 477
 478 static void
 479 elimBit(int b, char *tmtf, int maxbits)
 480 {
 481         int bb;
 482
 483         for(bb = 0; bb < maxbits; bb++)
 484                 if(tmtf[bb] == b)
 485                         break;
 486         while(++bb <= maxbits)
 487                 tmtf[bb - 1] = tmtf[bb];
 488 }
 489
 490 static int
 491 elimBits(int b, ulong *bused, char *tmtf, int maxbits)
 492 {
 493         int bb, elim;
 494
 495         if(b < 0)
 496                 return 0;
 497
 498         elim = 0;
 499
 500         /*
 501          * increase bits counts for all descendants
 502          */
 503         for(bb = b + 1; bb < maxbits; bb++){
 504                 bused[bb] += 1 << (bb - b);
 505                 if(bused[bb] == (1 << bb)){
 506                         elim++;
 507                         elimBit(bb, tmtf, maxbits);
 508                 }
 509         }
 510
 511         /*
 512          * steal bits from parent & check for fullness
 513          */
 514         for(; b >= 0; b--){
 515                 bused[b]++;
 516                 if(bused[b] == (1 << b)){
 517                         elim++;
 518                         elimBit(b, tmtf, maxbits);
 519                 }
 520                 if((bused[b] & 1) == 0)
 521                         break;
 522         }
 523         return elim;
 524 }
 525
 526 static void
 527 recvtab(Decode *dec, Huff *tab, int maxleaf, ushort *map)
 528 {
 529         ulong bitcount[MaxHuffBits+1], bused[MaxHuffBits+1];
 530         char tmtf[MaxHuffBits+1], *hb;
 531         int i, b, ttb, m, maxbits, max, elim;
 532
 533         hb = malloc(MaxLeaf * sizeof *hb);
 534         if(hb == nil)
 535                 fatal(dec, "out of memory");
 536
 537         /*
 538          * read the tables for the tables
 539          */
 540         max = 8;
 541         for(i = 0; i <= MaxHuffBits; i++){
 542                 bitcount[i] = 0;
 543                 tmtf[i] = i;
 544                 bused[i] = 0;
 545         }
 546         tmtf[0] = -1;
 547         tmtf[max] = 0;
 548         elim = 0;
 549         maxbits = -1;
 550         for(i = 0; i <= MaxHuffBits && elim != max; i++){
 551                 ttb = 4;
 552                 while(max - elim < (1 << (ttb-1)))
 553                         ttb--;
 554                 b = bitget(dec, ttb);
 555                 if(b > max - elim)
 556                         fatal(dec, "corrupted huffman table table");
 557                 b = tmtf[b];
 558                 hb[i] = b;
 559                 bitcount[b]++;
 560                 if(b > maxbits)
 561                         maxbits = b;
 562
 563                 elim += elimBits(b, bused, tmtf, max);
 564         }
 565         if(elim != max)
 566                 fatal(dec, "incomplete huffman table table");
 567         hufftab(dec, tab, hb, bitcount, i, maxbits, MaxFlatbits);
 568         for(i = 0; i <= MaxHuffBits; i++){
 569                 tmtf[i] = i;
 570                 bitcount[i] = 0;
 571                 bused[i] = 0;
 572         }
 573         tmtf[0] = -1;
 574         tmtf[MaxHuffBits] = 0;
 575         elim = 0;
 576         maxbits = -1;
 577         for(i = 0; i < maxleaf && elim != MaxHuffBits; i++){
 578                 if(dec->nbits <= tab->maxbits)
 579                         fillbits(dec);
 580                 dec->bits &= (1 << dec->nbits) - 1;
 581                 m = tab->flat[dec->bits >> (dec->nbits - tab->flatbits)];
 582                 b = m & 0xff;
 583                 m >>= 8;
 584                 if(b == 0xff)
 585                         m = hdecsym(dec, tab, m);
 586                 else
 587                         dec->nbits -= b;
 588                 b = tmtf[m];
 589                 for(; m > 0; m--)
 590                         tmtf[m] = tmtf[m-1];
 591                 tmtf[0] = b;
 592
 593                 if(b > MaxHuffBits)
 594                         fatal(dec, "bit length too big");
 595                 m = i;
 596                 if(map != nil)
 597                         m = map[m];
 598                 hb[m] = b;
 599                 bitcount[b]++;
 600                 if(b > maxbits)
 601                         maxbits = b;
 602                 elim += elimBits(b, bused, tmtf, MaxHuffBits);
 603         }
 604         if(elim != MaxHuffBits && elim != 0)
 605                 fatal(dec, "incomplete huffman table");
 606         if(map != nil)
 607                 for(; i < maxleaf; i++)
 608                         hb[map[i]] = -1;
 609
 610         hufftab(dec, tab, hb, bitcount, i, maxbits, MaxFlatbits);
 611
 612         free(hb);
 613 }
 614
 615 static void
 616 fatal(Decode *dec, char *msg)
 617 {
 618         print("%s: %s\n", argv0, msg);
 619         longjmp(dec->errjmp, 1);
 620 }