huf.c

   1 /***********************************************************
   2         huf.c -- static Huffman
   3 ***********************************************************/
   4 #include <stdlib.h>
   5 #include "ar.h"
   6
   7 /***** encoding *****/
   8
   9 static void
  10 count_t_freq(struct lzh_ostream *wp, uchar *c_len, ushort *t_freq)
  11 {
  12     int i, k, n, count;
  13
  14     for (i = 0; i < NT; i++)
  15         t_freq[i] = 0;
  16     n = NC;
  17     while (n > 0 && c_len[n - 1] == 0)
  18         n--;
  19     i = 0;
  20     while (i < n) {
  21         k = c_len[i++];
  22         if (k == 0) {
  23             count = 1;
  24             while (i < n && c_len[i] == 0) {
  25                 i++;
  26                 count++;
  27             }
  28             if (count <= 2)
  29                 t_freq[0] += count;
  30             else if (count <= 18)
  31                 t_freq[1]++;
  32             else if (count == 19) {
  33                 t_freq[0]++;
  34                 t_freq[1]++;
  35             }
  36             else
  37                 t_freq[2]++;
  38         }
  39         else
  40             t_freq[k + 2]++;
  41     }
  42 }
  43
  44 static void
  45 write_pt_len(struct lzh_ostream *wp, int n, int nbit, int i_special,
  46              uchar *pt_len)
  47 {
  48     int i, k;
  49
  50     while (n > 0 && pt_len[n - 1] == 0)
  51         n--;
  52     putbits(wp, nbit, n);
  53     i = 0;
  54     while (i < n) {
  55         k = pt_len[i++];
  56         if (k <= 6)
  57             putbits(wp, 3, k);
  58         else
  59             putbits(wp, k - 3, (1U << (k - 3)) - 2);
  60         if (i == i_special) {
  61             while (i < 6 && pt_len[i] == 0)
  62                 i++;
  63             putbits(wp, 2, (i - 3) & 3);
  64         }
  65     }
  66 }
  67
  68 static void
  69 write_c_len(struct lzh_ostream *wp, uchar *c_len, uchar *t_len, ushort *t_code)
  70 {
  71     int i, k, n, count;
  72
  73     n = NC;
  74     while (n > 0 && c_len[n - 1] == 0)
  75         n--;
  76     putbits(wp, CBIT, n);
  77     i = 0;
  78     while (i < n) {
  79         k = c_len[i++];
  80         if (k == 0) {
  81             count = 1;
  82             while (i < n && c_len[i] == 0) {
  83                 i++;
  84                 count++;
  85             }
  86             if (count <= 2) {
  87                 for (k = 0; k < count; k++)
  88                     putbits(wp, t_len[0], t_code[0]);
  89             }
  90             else if (count <= 18) {
  91                 putbits(wp, t_len[1], t_code[1]);
  92                 putbits(wp, 4, count - 3);
  93             }
  94             else if (count == 19) {
  95                 putbits(wp, t_len[0], t_code[0]);
  96                 putbits(wp, t_len[1], t_code[1]);
  97                 putbits(wp, 4, 15);
  98             }
  99             else {
 100                 putbits(wp, t_len[2], t_code[2]);
 101                 putbits(wp, CBIT, count - 20);
 102             }
 103         }
 104         else
 105             putbits(wp, t_len[k + 2], t_code[k + 2]);
 106     }
 107 }
 108
 109 static void
 110 encode_c(struct lzh_ostream *wp, int c, uchar *c_len, ushort *c_code)
 111 {
 112     putbits(wp, c_len[c], c_code[c]);
 113 }
 114
 115 static void
 116 encode_p(struct lzh_ostream *wp, uint p, uchar *p_len, ushort *p_code)
 117 {
 118     uint c, q;
 119
 120     c = 0;
 121     q = p;
 122     while (q) {
 123         q >>= 1;
 124         c++;
 125     }
 126     putbits(wp, p_len[c], p_code[c]);
 127     if (c > 1)
 128         putbits(wp, c - 1, p & (0xFFFFU >> (17 - c)));
 129 }
 130
 131 /*
 132     size        frequency       bitlength       Huffman coding
 133    -----------------------------------------------------------
 134      NC         c_freq          c_len           c_code
 135      NT         t_freq          t_len           t_code
 136      np         p_freq          p_len           p_code
 137
 138   output format for a block.
 139
 140     +-----------+
 141     | blocksize |
 142     +-----------+
 143      16bit
 144
 145     +-----+--------------------+
 146     | len |       t_len        | Huffman tree for c_len[]
 147     +-----+--------------------+
 148       5bit        ?? bit
 149       TBIT
 150
 151     +-------+------------------+
 152     |  len  |     c_len        | Huffman tree for characters and length
 153     +-------+------------------+
 154       9bit        ?? bit
 155       CBIT
 156
 157     +---------+--------------------+
 158     |   len   |   p_len            | Huffman tree for offset
 159     +---------+--------------------+
 160      pbit         ?? bit
 161                                (pbit=4bit(lh4,5) or 5bit(lh6,7))
 162
 163     +---------------------+
 164     |  encoding text      |
 165     +---------------------+
 166
 167
 168   In special case, only one kind characters in a block.
 169
 170                   TBIT: 5 bits
 171                   CBIT: 9 bits
 172
 173     +-----------+
 174     | blocksize |
 175     +-----------+
 176      16bit
 177
 178     +-----+-----+
 179     |  0  |  0  | Huffman tree for c_len[]
 180     +-----+-----+
 181       TBIT  TBIT
 182
 183     +-------+-------+
 184     |  0    |  0    | Huffman tree for characters and length
 185     +-------+-------+
 186       CBIT    CBIT
 187
 188     +---------+--------------+
 189     |  0      | offset value | Huffman tree for offset
 190     +---------+--------------+
 191      pbit         pbit
 192                                (pbit=4bit(lh4,5) or 5bit(lh6,7))
 193
 194     +---------------------+
 195     |  encoding text      |
 196     +---------------------+
 197  */
 198 static void
 199 send_block(struct lzh_ostream *wp)
 200 {
 201     uint i, k, flags, root, pos, size;
 202
 203     uchar c_len[NC];
 204     ushort c_code[NC];
 205
 206     uchar t_len[NT];
 207     ushort t_code[NT];
 208
 209     uchar p_len[NP];
 210     ushort p_code[NP];
 211
 212     /* make Huffman tree for characters and length */
 213     root = make_tree(NC, wp->c_freq, c_len, c_code);
 214     size = wp->c_freq[root];
 215     putbits(wp, 16, size);
 216     if (root >= NC) {
 217         ushort t_freq[2 * NT - 1];
 218
 219         /* make Huffman tree for c_len */
 220         count_t_freq(wp, c_len, t_freq);
 221         root = make_tree(NT, t_freq, t_len, t_code);
 222         if (root >= NT) {
 223             write_pt_len(wp, NT, TBIT, 3, t_len);
 224         }
 225         else {
 226             /* only one kind */
 227             putbits(wp, TBIT, 0);
 228             putbits(wp, TBIT, root);
 229         }
 230         write_c_len(wp, c_len, t_len, t_code);
 231     }
 232     else {
 233         /* only one kind */
 234         putbits(wp, TBIT, 0);
 235         putbits(wp, TBIT, 0);
 236         putbits(wp, CBIT, 0);
 237         putbits(wp, CBIT, root);
 238     }
 239
 240     /* make Huffman tree for offset */
 241     root = make_tree(wp->np, wp->p_freq, p_len, p_code);
 242     if (root >= wp->np) {
 243         write_pt_len(wp, wp->np, wp->pbit, -1, p_len);
 244     }
 245     else {
 246         putbits(wp, wp->pbit, 0);
 247         putbits(wp, wp->pbit, root);
 248     }
 249
 250     /* write Huffman encoding */
 251     pos = 0;
 252     for (i = 0; i < size; i++) {
 253         if (i % CHAR_BIT == 0)
 254             flags = wp->buf[pos++];
 255         else
 256             flags <<= 1;
 257         if (flags & (1U << (CHAR_BIT - 1))) {
 258             /* write length */
 259             encode_c(wp, wp->buf[pos++] + (1U << CHAR_BIT), c_len, c_code);
 260             /* write offset */
 261             k = wp->buf[pos++] << CHAR_BIT;
 262             k += wp->buf[pos++];
 263             encode_p(wp, k, p_len, p_code);
 264         }
 265         else {
 266             /* write character */
 267             encode_c(wp, wp->buf[pos++], c_len, c_code);
 268         }
 269         if (wp->unpackable)
 270             return;
 271     }
 272
 273     /* clear frequency table */
 274     for (i = 0; i < NC; i++)
 275         wp->c_freq[i] = 0;
 276     for (i = 0; i < wp->np; i++)
 277         wp->p_freq[i] = 0;
 278 }
 279
 280 /*
 281   call with output(wp, c, 0)        c <  256
 282          or output(wp, len, off)  len >= 256
 283
 284
 285 one block:
 286
 287 output_mask
 288              128  64   32             16   8              4    2    1
 289         +----+----+----+----+----+----+----+----+----+----+----+----+----+
 290 buf     | 40 | c1 | c2 |len |   off   | c4 |len |   off   | c6 | c7 | c8 |
 291         +----+----+----+----+----+----+----+----+----+----+----+----+----+
 292         cpos                                                            /
 293                                                                        /
 294                                                                output_pos
 295    buf[cpos] = 32 + 8 (it points <len, off>)
 296
 297 c_freq[] has frequency of cN and len.
 298 p_freq[] has frequency of length of off bits.
 299 */
 300 void
 301 output(struct lzh_ostream *wp, uint c, uint p)
 302 {
 303     wp->output_mask >>= 1;
 304     if (wp->output_mask == 0) {
 305         wp->output_mask = 128;
 306         /* max byte size of one block: 3 * CHAR_BIT + 1 */
 307         if (wp->output_pos > wp->bufsiz - (3 * CHAR_BIT + 1)) {
 308             send_block(wp);
 309             if (wp->unpackable)
 310                 return;
 311             wp->output_pos = 0;
 312         }
 313         wp->cpos = wp->output_pos++;
 314         wp->buf[wp->cpos] = 0;
 315     }
 316     wp->buf[wp->output_pos++] = (uchar) c; /* char or length */
 317     wp->c_freq[c]++;
 318
 319     if (c >= (1U << CHAR_BIT)) {
 320         /* c is length, p is offset */
 321         wp->buf[wp->cpos] |= wp->output_mask;
 322         wp->buf[wp->output_pos++] = (uchar) (p >> CHAR_BIT);
 323         wp->buf[wp->output_pos++] = (uchar) p;
 324
 325         {
 326             /* count frequency of p's bit length */
 327             int n = 0;          /* max of n is np-1 */
 328             while (p) {
 329                 p >>= 1;
 330                 n++;
 331             }
 332             wp->p_freq[n]++;
 333         }
 334     }
 335 }
 336
 337 static void
 338 init_enc_parameter(struct lzh_ostream *wp, struct lha_method *m)
 339 {
 340     wp->np   = m->dicbit + 1;
 341     wp->pbit = m->pbit;
 342 }
 343
 344 void
 345 huf_encode_start(struct lzh_ostream *wp, struct lha_method *m)
 346 {
 347     int i;
 348
 349     init_enc_parameter(wp, m);
 350     wp->output_pos = wp->output_mask = wp->cpos = 0;
 351
 352     if (wp->buf == 0) {
 353         wp->bufsiz = 16 * 1024U;
 354         while ((wp->buf = malloc(wp->bufsiz)) == NULL) {
 355             wp->bufsiz = (wp->bufsiz / 10U) * 9U;
 356             if (wp->bufsiz < 4 * 1024U)
 357                 error("Out of memory.");
 358         }
 359     }
 360     wp->buf[0] = 0;
 361     for (i = 0; i < NC; i++)
 362         wp->c_freq[i] = 0;
 363     for (i = 0; i < wp->np; i++)
 364         wp->p_freq[i] = 0;
 365
 366     init_putbits(wp);
 367 }
 368
 369 void
 370 huf_encode_end(struct lzh_ostream *wp)
 371 {
 372     if (!wp->unpackable) {
 373         send_block(wp);
 374         putbits(wp, CHAR_BIT - 1, 0);       /* flush remaining bits */
 375     }
 376
 377     if (wp->buf) {
 378         free(wp->buf);
 379         wp->buf = NULL;
 380     }
 381 }
 382
 383 /***** decoding *****/
 384
 385 static void
 386 read_pt_len(struct huf_t *huf, struct lzh_istream *rp, int nn, int nbit,
 387             int i_special, uchar *pt_len, ushort *pt_table)
 388 {
 389     int i, c, n;
 390     uint mask;
 391
 392     n = getbits(rp, nbit);
 393     if (n == 0) {
 394         c = getbits(rp, nbit);
 395         for (i = 0; i < nn; i++)
 396             pt_len[i] = 0;
 397         for (i = 0; i < 256; i++)
 398             pt_table[i] = c;
 399     }
 400     else {
 401         i = 0;
 402         while (i < n) {
 403             c = rp->bitbuf >> (BITBUFSIZ - 3);
 404             if (c == 7) {
 405                 mask = 1U << (BITBUFSIZ - 1 - 3);
 406                 while (mask & rp->bitbuf) {
 407                     mask >>= 1;
 408                     c++;
 409                 }
 410             }
 411             fillbuf(rp, (c < 7) ? 3 : c - 3);
 412             pt_len[i++] = c;
 413             if (i == i_special) {
 414                 c = getbits(rp, 2);
 415                 while (--c >= 0)
 416                     pt_len[i++] = 0;
 417             }
 418         }
 419         while (i < nn)
 420             pt_len[i++] = 0;
 421         make_table(huf, nn, pt_len, 8, pt_table);
 422     }
 423 }
 424
 425 static void
 426 read_c_len(struct huf_t *huf, struct lzh_istream *rp, uchar *t_len, ushort *t_table)
 427 {
 428     int i, c, n;
 429     uint mask;
 430
 431     n = getbits(rp, CBIT);
 432     if (n == 0) {
 433         c = getbits(rp, CBIT);
 434         for (i = 0; i < NC; i++)
 435             rp->c_len[i] = 0;
 436         for (i = 0; i < 4096; i++)
 437             rp->c_table[i] = c;
 438     }
 439     else {
 440         i = 0;
 441         while (i < n) {
 442             c = t_table[rp->bitbuf >> (BITBUFSIZ - 8)];
 443             if (c >= NT) {
 444                 mask = 1U << (BITBUFSIZ - 1 - 8);
 445                 do {
 446                     if (rp->bitbuf & mask)
 447                         c = huf->right[c];
 448                     else
 449                         c = huf->left[c];
 450                     mask >>= 1;
 451                 } while (c >= NT);
 452             }
 453             fillbuf(rp, t_len[c]);
 454             if (c <= 2) {
 455                 if (c == 0)
 456                     c = 1;
 457                 else if (c == 1)
 458                     c = getbits(rp, 4) + 3;
 459                 else
 460                     c = getbits(rp, CBIT) + 20;
 461                 while (--c >= 0)
 462                     rp->c_len[i++] = 0;
 463             }
 464             else
 465                 rp->c_len[i++] = c - 2;
 466         }
 467         while (i < NC)
 468             rp->c_len[i++] = 0;
 469         make_table(huf, NC, rp->c_len, 12, rp->c_table);
 470     }
 471 }
 472
 473 uint
 474 decode_c(struct huf_t *huf, struct lzh_istream *rp)
 475 {
 476     uint j, mask;
 477
 478     if (rp->blocksize == 0) {
 479         uchar t_len[NT];
 480         unsigned short t_table[256];
 481
 482         rp->blocksize = getbits(rp, 16);
 483         read_pt_len(huf, rp, NT, TBIT, 3, t_len, t_table);
 484         read_c_len(huf, rp, t_len, t_table);
 485         read_pt_len(huf, rp, rp->np, rp->pbit, -1, rp->p_len, rp->p_table);
 486     }
 487     rp->blocksize--;
 488     j = rp->c_table[rp->bitbuf >> (BITBUFSIZ - 12)];
 489     if (j >= NC) {
 490         mask = 1U << (BITBUFSIZ - 1 - 12);
 491         do {
 492             if (rp->bitbuf & mask)
 493                 j = huf->right[j];
 494             else
 495                 j = huf->left[j];
 496             mask >>= 1;
 497         } while (j >= NC);
 498     }
 499     fillbuf(rp, rp->c_len[j]);
 500     return j;
 501 }
 502
 503 uint
 504 decode_p(struct huf_t *huf, struct lzh_istream *rp)
 505 {
 506     uint j, mask;
 507
 508     j = rp->p_table[rp->bitbuf >> (BITBUFSIZ - 8)];
 509     if (j >= rp->np) {
 510         mask = 1U << (BITBUFSIZ - 1 - 8);
 511         do {
 512             if (rp->bitbuf & mask)
 513                 j = huf->right[j];
 514             else
 515                 j = huf->left[j];
 516             mask >>= 1;
 517         } while (j >= rp->np);
 518     }
 519     fillbuf(rp, rp->p_len[j]);
 520     if (j != 0)
 521         j = (1U << (j - 1)) + getbits(rp, j - 1);
 522     return j;
 523 }
 524
 525 static void
 526 init_dec_parameter(struct lzh_istream *rp, struct lha_method *m)
 527 {
 528     rp->np   = m->dicbit + 1;
 529     rp->pbit = m->pbit;
 530 }
 531
 532 void
 533 huf_decode_start(struct lzh_istream *rp, struct lha_method *m)
 534 {
 535     init_dec_parameter(rp, m);
 536     init_getbits(rp);
 537     rp->blocksize = 0;
 538 }