huf.c

   1 /***********************************************************
   2         huf.c -- static Huffman
   3 ***********************************************************/
   4 #include <stdlib.h>
   5 #include "ar.h"
   6
   7 #define NP (MAXDICBIT + 1)
   8 #define NT (CODE_BIT + 3)
   9 #define PBIT 4                  /* smallest integer such that (1U << PBIT) > NP */
  10 #define TBIT 5                  /* smallest integer such that (1U << TBIT) > NT */
  11 #if NT > NP
  12 #define NPT NT
  13 #else
  14 #define NPT NP
  15 #endif
  16
  17 static uchar c_len[NC], pt_len[NPT];
  18 static ushort c_freq[2 * NC - 1], c_table[4096], c_code[NC],
  19     p_freq[2 * NP - 1], pt_table[256], pt_code[NPT], t_freq[2 * NT - 1];
  20
  21 static int np;
  22 static int pbit;
  23
  24 static void
  25 init_parameter(struct lha_method *m)
  26 {
  27     np   = m->dicbit + 1;
  28     pbit = m->pbit;
  29 }
  30
  31 /***** encoding *****/
  32
  33 static void
  34 count_t_freq(void)
  35 {
  36     int i, k, n, count;
  37
  38     for (i = 0; i < NT; i++)
  39         t_freq[i] = 0;
  40     n = NC;
  41     while (n > 0 && c_len[n - 1] == 0)
  42         n--;
  43     i = 0;
  44     while (i < n) {
  45         k = c_len[i++];
  46         if (k == 0) {
  47             count = 1;
  48             while (i < n && c_len[i] == 0) {
  49                 i++;
  50                 count++;
  51             }
  52             if (count <= 2)
  53                 t_freq[0] += count;
  54             else if (count <= 18)
  55                 t_freq[1]++;
  56             else if (count == 19) {
  57                 t_freq[0]++;
  58                 t_freq[1]++;
  59             }
  60             else
  61                 t_freq[2]++;
  62         }
  63         else
  64             t_freq[k + 2]++;
  65     }
  66 }
  67
  68 static void
  69 write_pt_len(struct lzh_ostream *wp, int n, int nbit, int i_special)
  70 {
  71     int i, k;
  72
  73     while (n > 0 && pt_len[n - 1] == 0)
  74         n--;
  75     putbits(wp, nbit, n);
  76     i = 0;
  77     while (i < n) {
  78         k = pt_len[i++];
  79         if (k <= 6)
  80             putbits(wp, 3, k);
  81         else
  82             putbits(wp, k - 3, (1U << (k - 3)) - 2);
  83         if (i == i_special) {
  84             while (i < 6 && pt_len[i] == 0)
  85                 i++;
  86             putbits(wp, 2, (i - 3) & 3);
  87         }
  88     }
  89 }
  90
  91 static void
  92 write_c_len(struct lzh_ostream *wp)
  93 {
  94     int i, k, n, count;
  95
  96     n = NC;
  97     while (n > 0 && c_len[n - 1] == 0)
  98         n--;
  99     putbits(wp, CBIT, n);
 100     i = 0;
 101     while (i < n) {
 102         k = c_len[i++];
 103         if (k == 0) {
 104             count = 1;
 105             while (i < n && c_len[i] == 0) {
 106                 i++;
 107                 count++;
 108             }
 109             if (count <= 2) {
 110                 for (k = 0; k < count; k++)
 111                     putbits(wp, pt_len[0], pt_code[0]);
 112             }
 113             else if (count <= 18) {
 114                 putbits(wp, pt_len[1], pt_code[1]);
 115                 putbits(wp, 4, count - 3);
 116             }
 117             else if (count == 19) {
 118                 putbits(wp, pt_len[0], pt_code[0]);
 119                 putbits(wp, pt_len[1], pt_code[1]);
 120                 putbits(wp, 4, 15);
 121             }
 122             else {
 123                 putbits(wp, pt_len[2], pt_code[2]);
 124                 putbits(wp, CBIT, count - 20);
 125             }
 126         }
 127         else
 128             putbits(wp, pt_len[k + 2], pt_code[k + 2]);
 129     }
 130 }
 131
 132 static void
 133 encode_c(struct lzh_ostream *wp, int c)
 134 {
 135     putbits(wp, c_len[c], c_code[c]);
 136 }
 137
 138 static void
 139 encode_p(struct lzh_ostream *wp, uint p)
 140 {
 141     uint c, q;
 142
 143     c = 0;
 144     q = p;
 145     while (q) {
 146         q >>= 1;
 147         c++;
 148     }
 149     putbits(wp, pt_len[c], pt_code[c]);
 150     if (c > 1)
 151         putbits(wp, c - 1, p & (0xFFFFU >> (17 - c)));
 152 }
 153
 154 static void
 155 send_block(struct lzh_ostream *wp)
 156 {
 157     uint i, k, flags, root, pos, size;
 158
 159     root = make_tree(NC, c_freq, c_len, c_code);
 160     size = c_freq[root];
 161     putbits(wp, 16, size);
 162     if (root >= NC) {
 163         count_t_freq();
 164         root = make_tree(NT, t_freq, pt_len, pt_code);
 165         if (root >= NT) {
 166             write_pt_len(wp, NT, TBIT, 3);
 167         }
 168         else {
 169             putbits(wp, TBIT, 0);
 170             putbits(wp, TBIT, root);
 171         }
 172         write_c_len(wp);
 173     }
 174     else {
 175         putbits(wp, TBIT, 0);
 176         putbits(wp, TBIT, 0);
 177         putbits(wp, CBIT, 0);
 178         putbits(wp, CBIT, root);
 179     }
 180     root = make_tree(np, p_freq, pt_len, pt_code);
 181     if (root >= np) {
 182         write_pt_len(wp, np, pbit, -1);
 183     }
 184     else {
 185         putbits(wp, pbit, 0);
 186         putbits(wp, pbit, root);
 187     }
 188     pos = 0;
 189     for (i = 0; i < size; i++) {
 190         if (i % CHAR_BIT == 0)
 191             flags = wp->buf[pos++];
 192         else
 193             flags <<= 1;
 194         if (flags & (1U << (CHAR_BIT - 1))) {
 195             encode_c(wp, wp->buf[pos++] + (1U << CHAR_BIT));
 196             k = wp->buf[pos++] << CHAR_BIT;
 197             k += wp->buf[pos++];
 198             encode_p(wp, k);
 199         }
 200         else
 201             encode_c(wp, wp->buf[pos++]);
 202         if (wp->unpackable)
 203             return;
 204     }
 205     for (i = 0; i < NC; i++)
 206         c_freq[i] = 0;
 207     for (i = 0; i < np; i++)
 208         p_freq[i] = 0;
 209 }
 210
 211 static uint output_pos, output_mask;
 212
 213 void
 214 output(struct lzh_ostream *wp, uint c, uint p)
 215 {
 216     static uint cpos;
 217
 218     if ((output_mask >>= 1) == 0) {
 219         output_mask = 1U << (CHAR_BIT - 1);
 220         if (output_pos >= wp->bufsiz - 3 * CHAR_BIT) {
 221             send_block(wp);
 222             if (wp->unpackable)
 223                 return;
 224             output_pos = 0;
 225         }
 226         cpos = output_pos++;
 227         wp->buf[cpos] = 0;
 228     }
 229     wp->buf[output_pos++] = (uchar) c;
 230     c_freq[c]++;
 231     if (c >= (1U << CHAR_BIT)) {
 232         wp->buf[cpos] |= output_mask;
 233         wp->buf[output_pos++] = (uchar) (p >> CHAR_BIT);
 234         wp->buf[output_pos++] = (uchar) p;
 235         c = 0;
 236         while (p) {
 237             p >>= 1;
 238             c++;
 239         }
 240         p_freq[c]++;
 241     }
 242 }
 243
 244 void
 245 huf_encode_start(struct lzh_ostream *wp, struct lha_method *m)
 246 {
 247     int i;
 248
 249     init_parameter(m);
 250
 251     if (wp->buf == 0) {
 252         wp->bufsiz = 16 * 1024U;
 253         while ((wp->buf = malloc(wp->bufsiz)) == NULL) {
 254             wp->bufsiz = (wp->bufsiz / 10U) * 9U;
 255             if (wp->bufsiz < 4 * 1024U)
 256                 error("Out of memory.");
 257         }
 258     }
 259     wp->buf[0] = 0;
 260     for (i = 0; i < NC; i++)
 261         c_freq[i] = 0;
 262     for (i = 0; i < np; i++)
 263         p_freq[i] = 0;
 264     output_pos = output_mask = 0;
 265     init_putbits(wp);
 266 }
 267
 268 void
 269 huf_encode_end(struct lzh_ostream *wp)
 270 {
 271     if (!wp->unpackable) {
 272         send_block(wp);
 273         putbits(wp, CHAR_BIT - 1, 0);       /* flush remaining bits */
 274     }
 275
 276     if (wp->buf) {
 277         free(wp->buf);
 278         wp->buf = NULL;
 279     }
 280 }
 281
 282 /***** decoding *****/
 283
 284 static void
 285 read_pt_len(struct huf_t *huf, struct lzh_istream *rp, int nn, int nbit, int i_special)
 286 {
 287     int i, c, n;
 288     uint mask;
 289
 290     n = getbits(rp, nbit);
 291     if (n == 0) {
 292         c = getbits(rp, nbit);
 293         for (i = 0; i < nn; i++)
 294             pt_len[i] = 0;
 295         for (i = 0; i < 256; i++)
 296             pt_table[i] = c;
 297     }
 298     else {
 299         i = 0;
 300         while (i < n) {
 301             c = rp->bitbuf >> (BITBUFSIZ - 3);
 302             if (c == 7) {
 303                 mask = 1U << (BITBUFSIZ - 1 - 3);
 304                 while (mask & rp->bitbuf) {
 305                     mask >>= 1;
 306                     c++;
 307                 }
 308             }
 309             fillbuf(rp, (c < 7) ? 3 : c - 3);
 310             pt_len[i++] = c;
 311             if (i == i_special) {
 312                 c = getbits(rp, 2);
 313                 while (--c >= 0)
 314                     pt_len[i++] = 0;
 315             }
 316         }
 317         while (i < nn)
 318             pt_len[i++] = 0;
 319         make_table(huf, nn, pt_len, 8, pt_table);
 320     }
 321 }
 322
 323 static void
 324 read_c_len(struct huf_t *huf, struct lzh_istream *rp)
 325 {
 326     int i, c, n;
 327     uint mask;
 328
 329     n = getbits(rp, CBIT);
 330     if (n == 0) {
 331         c = getbits(rp, CBIT);
 332         for (i = 0; i < NC; i++)
 333             c_len[i] = 0;
 334         for (i = 0; i < 4096; i++)
 335             c_table[i] = c;
 336     }
 337     else {
 338         i = 0;
 339         while (i < n) {
 340             c = pt_table[rp->bitbuf >> (BITBUFSIZ - 8)];
 341             if (c >= NT) {
 342                 mask = 1U << (BITBUFSIZ - 1 - 8);
 343                 do {
 344                     if (rp->bitbuf & mask)
 345                         c = huf->right[c];
 346                     else
 347                         c = huf->left[c];
 348                     mask >>= 1;
 349                 } while (c >= NT);
 350             }
 351             fillbuf(rp, pt_len[c]);
 352             if (c <= 2) {
 353                 if (c == 0)
 354                     c = 1;
 355                 else if (c == 1)
 356                     c = getbits(rp, 4) + 3;
 357                 else
 358                     c = getbits(rp, CBIT) + 20;
 359                 while (--c >= 0)
 360                     c_len[i++] = 0;
 361             }
 362             else
 363                 c_len[i++] = c - 2;
 364         }
 365         while (i < NC)
 366             c_len[i++] = 0;
 367         make_table(huf, NC, c_len, 12, c_table);
 368     }
 369 }
 370
 371 uint
 372 decode_c(struct huf_t *huf, struct lzh_istream *rp)
 373 {
 374     uint j, mask;
 375
 376     if (rp->blocksize == 0) {
 377         rp->blocksize = getbits(rp, 16);
 378         read_pt_len(huf, rp, NT, TBIT, 3);
 379         read_c_len(huf, rp);
 380         read_pt_len(huf, rp, np, pbit, -1);
 381     }
 382     rp->blocksize--;
 383     j = c_table[rp->bitbuf >> (BITBUFSIZ - 12)];
 384     if (j >= NC) {
 385         mask = 1U << (BITBUFSIZ - 1 - 12);
 386         do {
 387             if (rp->bitbuf & mask)
 388                 j = huf->right[j];
 389             else
 390                 j = huf->left[j];
 391             mask >>= 1;
 392         } while (j >= NC);
 393     }
 394     fillbuf(rp, c_len[j]);
 395     return j;
 396 }
 397
 398 uint
 399 decode_p(struct huf_t *huf, struct lzh_istream *rp)
 400 {
 401     uint j, mask;
 402
 403     j = pt_table[rp->bitbuf >> (BITBUFSIZ - 8)];
 404     if (j >= np) {
 405         mask = 1U << (BITBUFSIZ - 1 - 8);
 406         do {
 407             if (rp->bitbuf & mask)
 408                 j = huf->right[j];
 409             else
 410                 j = huf->left[j];
 411             mask >>= 1;
 412         } while (j >= np);
 413     }
 414     fillbuf(rp, pt_len[j]);
 415     if (j != 0)
 416         j = (1U << (j - 1)) + getbits(rp, j - 1);
 417     return j;
 418 }
 419
 420 void
 421 huf_decode_start(struct lzh_istream *rp, struct lha_method *m)
 422 {
 423     init_parameter(m);
 424     init_getbits(rp);
 425     rp->blocksize = 0;
 426 }