src/huf.c

   1 /* ------------------------------------------------------------------------ */
   2 /* LHa for UNIX                                                             */
   3 /*              huf.c -- new static Huffman                                 */
   4 /*                                                                          */
   5 /*      Modified                Nobutaka Watazaki                           */
   6 /*                                                                          */
   7 /*  Ver. 1.14   Source All chagned              1995.01.14  N.Watazaki      */
   8 /*  Ver. 1.14i  Support LH7 & Bug Fixed         2000.10. 6  t.okamoto       */
   9 /* ------------------------------------------------------------------------ */
  10 #include "lha.h"
  11
  12 #include <assert.h>
  13
  14 #if HAVE_SYS_PARAM_H
  15 #include <sys/param.h>
  16 #endif
  17
  18 #if STDC_HEADERS
  19 #include <stdlib.h>
  20 #else
  21 extern char *malloc ();
  22 #endif
  23
  24 /* ------------------------------------------------------------------------ */
  25 unsigned short  left[2 * NC - 1], right[2 * NC - 1];
  26 unsigned char   c_len[NC], pt_len[NPT];
  27 unsigned short  c_freq[2 * NC - 1], c_table[4096], c_code[NC], p_freq[2 * NP - 1],
  28                 pt_table[256], pt_code[NPT], t_freq[2 * NT - 1];
  29
  30 static unsigned char *buf;
  31 static unsigned int bufsiz;
  32 static unsigned short blocksize;
  33 static unsigned short output_pos, output_mask;
  34 static          int   pbit;
  35 static          int   np;
  36 /* ------------------------------------------------------------------------ */
  37 /*                              Encording                                   */
  38 /* ------------------------------------------------------------------------ */
  39 static void
  40 count_t_freq(/*void*/)
  41 {
  42     short           i, k, n, count;
  43
  44     for (i = 0; i < NT; i++)
  45         t_freq[i] = 0;
  46     n = NC;
  47     while (n > 0 && c_len[n - 1] == 0)
  48         n--;
  49     i = 0;
  50     while (i < n) {
  51         k = c_len[i++];
  52         if (k == 0) {
  53             count = 1;
  54             while (i < n && c_len[i] == 0) {
  55                 i++;
  56                 count++;
  57             }
  58             if (count <= 2)
  59                 t_freq[0] += count;
  60             else if (count <= 18)
  61                 t_freq[1]++;
  62             else if (count == 19) {
  63                 t_freq[0]++;
  64                 t_freq[1]++;
  65             }
  66             else
  67                 t_freq[2]++;
  68         } else
  69             t_freq[k + 2]++;
  70     }
  71 }
  72
  73 /* ------------------------------------------------------------------------ */
  74 static void
  75 write_pt_len(n, nbit, i_special)
  76     short           n;
  77     short           nbit;
  78     short           i_special;
  79 {
  80     short           i, k;
  81
  82     while (n > 0 && pt_len[n - 1] == 0)
  83         n--;
  84     putbits(nbit, n);
  85     i = 0;
  86     while (i < n) {
  87         k = pt_len[i++];
  88         if (k <= 6)
  89             putbits(3, k);
  90         else
  91             putbits(k - 3, USHRT_MAX << 1);
  92         if (i == i_special) {
  93             while (i < 6 && pt_len[i] == 0)
  94                 i++;
  95             putbits(2, i - 3);
  96         }
  97     }
  98 }
  99
 100 /* ------------------------------------------------------------------------ */
 101 static void
 102 write_c_len(/*void*/)
 103 {
 104     short           i, k, n, count;
 105
 106     n = NC;
 107     while (n > 0 && c_len[n - 1] == 0)
 108         n--;
 109     putbits(CBIT, n);
 110     i = 0;
 111     while (i < n) {
 112         k = c_len[i++];
 113         if (k == 0) {
 114             count = 1;
 115             while (i < n && c_len[i] == 0) {
 116                 i++;
 117                 count++;
 118             }
 119             if (count <= 2) {
 120                 for (k = 0; k < count; k++)
 121                     putcode(pt_len[0], pt_code[0]);
 122             }
 123             else if (count <= 18) {
 124                 putcode(pt_len[1], pt_code[1]);
 125                 putbits(4, count - 3);
 126             }
 127             else if (count == 19) {
 128                 putcode(pt_len[0], pt_code[0]);
 129                 putcode(pt_len[1], pt_code[1]);
 130                 putbits(4, 15);
 131             }
 132             else {
 133                 putcode(pt_len[2], pt_code[2]);
 134                 putbits(CBIT, count - 20);
 135             }
 136         }
 137         else
 138             putcode(pt_len[k + 2], pt_code[k + 2]);
 139     }
 140 }
 141
 142 /* ------------------------------------------------------------------------ */
 143 static void
 144 encode_c(c)
 145     short           c;
 146 {
 147     putcode(c_len[c], c_code[c]);
 148 }
 149
 150 /* ------------------------------------------------------------------------ */
 151 static void
 152 encode_p(p)
 153     unsigned short  p;
 154 {
 155     unsigned short  c, q;
 156
 157     c = 0;
 158     q = p;
 159     while (q) {
 160         q >>= 1;
 161         c++;
 162     }
 163     putcode(pt_len[c], pt_code[c]);
 164     if (c > 1)
 165         putbits(c - 1, p);
 166 }
 167
 168 /* ------------------------------------------------------------------------ */
 169 static void
 170 send_block( /* void */ )
 171 {
 172     unsigned char   flags;
 173     unsigned short  i, k, root, pos, size;
 174
 175     root = make_tree(NC, c_freq, c_len, c_code);
 176     size = c_freq[root];
 177     putbits(16, size);
 178     if (root >= NC) {
 179         count_t_freq();
 180         root = make_tree(NT, t_freq, pt_len, pt_code);
 181         if (root >= NT) {
 182             write_pt_len(NT, TBIT, 3);
 183         } else {
 184             putbits(TBIT, 0);
 185             putbits(TBIT, root);
 186         }
 187         write_c_len();
 188     } else {
 189         putbits(TBIT, 0);
 190         putbits(TBIT, 0);
 191         putbits(CBIT, 0);
 192         putbits(CBIT, root);
 193     }
 194     root = make_tree(np, p_freq, pt_len, pt_code);
 195     if (root >= np) {
 196         write_pt_len(np, pbit, -1);
 197     }
 198     else {
 199         putbits(pbit, 0);
 200         putbits(pbit, root);
 201     }
 202     pos = 0;
 203     for (i = 0; i < size; i++) {
 204         if (i % CHAR_BIT == 0)
 205             flags = buf[pos++];
 206         else
 207             flags <<= 1;
 208         if (flags & (1 << (CHAR_BIT - 1))) {
 209             encode_c(buf[pos++] + (1 << CHAR_BIT));
 210             k = buf[pos++] << CHAR_BIT;
 211             k += buf[pos++];
 212             encode_p(k);
 213         } else
 214             encode_c(buf[pos++]);
 215         if (unpackable)
 216             return;
 217     }
 218     for (i = 0; i < NC; i++)
 219         c_freq[i] = 0;
 220     for (i = 0; i < np; i++)
 221         p_freq[i] = 0;
 222 }
 223
 224 /* ------------------------------------------------------------------------ */
 225 /* lh4, 5, 6 */
 226 void
 227 output_st1(c, p)
 228     unsigned short  c;
 229     unsigned short  p;
 230 {
 231     static unsigned short cpos;
 232
 233     output_mask >>= 1;
 234     if (output_mask == 0) {
 235         output_mask = 1 << (CHAR_BIT - 1);
 236         if (output_pos >= bufsiz - 3 * CHAR_BIT) {
 237             send_block();
 238             if (unpackable)
 239                 return;
 240             output_pos = 0;
 241         }
 242         cpos = output_pos++;
 243         buf[cpos] = 0;
 244     }
 245     buf[output_pos++] = (unsigned char) c;
 246     c_freq[c]++;
 247     if (c >= (1 << CHAR_BIT)) {
 248         buf[cpos] |= output_mask;
 249         buf[output_pos++] = (unsigned char) (p >> CHAR_BIT);
 250         buf[output_pos++] = (unsigned char) p;
 251         c = 0;
 252         while (p) {
 253             p >>= 1;
 254             c++;
 255         }
 256         p_freq[c]++;
 257     }
 258 }
 259
 260 /* ------------------------------------------------------------------------ */
 261 unsigned char  *
 262 alloc_buf( /* void */ )
 263 {
 264     bufsiz = 16 * 1024 *2;  /* 65408U; */ /* t.okamoto */
 265     while ((buf = (unsigned char *) malloc(bufsiz)) == NULL) {
 266         bufsiz = (bufsiz / 10) * 9;
 267         if (bufsiz < 4 * 1024)
 268             fatal_error("Not enough memory");
 269     }
 270     return buf;
 271 }
 272
 273 /* ------------------------------------------------------------------------ */
 274 /* lh4, 5, 6 */
 275 void
 276 encode_start_st1( /* void */ )
 277 {
 278     int             i;
 279
 280     switch (dicbit) {
 281     case LZHUFF4_DICBIT:
 282     case LZHUFF5_DICBIT: pbit = 4; np = LZHUFF5_DICBIT + 1; break;
 283     case LZHUFF6_DICBIT: pbit = 5; np = LZHUFF6_DICBIT + 1; break;
 284     case LZHUFF7_DICBIT: pbit = 5; np = LZHUFF7_DICBIT + 1; break;
 285     default:
 286         assert(0);
 287     }
 288
 289     for (i = 0; i < NC; i++)
 290         c_freq[i] = 0;
 291     for (i = 0; i < np; i++)
 292         p_freq[i] = 0;
 293     output_pos = output_mask = 0;
 294     init_putbits();
 295     init_code_cache();
 296     buf[0] = 0;
 297 }
 298
 299 /* ------------------------------------------------------------------------ */
 300 /* lh4, 5, 6 */
 301 void
 302 encode_end_st1( /* void */ )
 303 {
 304     if (!unpackable) {
 305         send_block();
 306         putbits(CHAR_BIT - 1, 0);   /* flush remaining bits */
 307     }
 308 }
 309
 310 /* ------------------------------------------------------------------------ */
 311 /*                              decoding                                    */
 312 /* ------------------------------------------------------------------------ */
 313 static void
 314 read_pt_len(nn, nbit, i_special)
 315     short           nn;
 316     short           nbit;
 317     short           i_special;
 318 {
 319     int           i, c, n;
 320
 321     n = getbits(nbit);
 322     if (n == 0) {
 323         c = getbits(nbit);
 324         for (i = 0; i < nn; i++)
 325             pt_len[i] = 0;
 326         for (i = 0; i < 256; i++)
 327             pt_table[i] = c;
 328     }
 329     else {
 330         i = 0;
 331         while (i < n) {
 332             c = bitbuf >> (16 - 3);
 333             if (c == 7) {
 334                 unsigned short  mask = 1 << (16 - 4);
 335                 while (mask & bitbuf) {
 336                     mask >>= 1;
 337                     c++;
 338                 }
 339             }
 340             fillbuf((c < 7) ? 3 : c - 3);
 341             pt_len[i++] = c;
 342             if (i == i_special) {
 343                 c = getbits(2);
 344                 while (--c >= 0)
 345                     pt_len[i++] = 0;
 346             }
 347         }
 348         while (i < nn)
 349             pt_len[i++] = 0;
 350         make_table(nn, pt_len, 8, pt_table);
 351     }
 352 }
 353
 354 /* ------------------------------------------------------------------------ */
 355 static void
 356 read_c_len( /* void */ )
 357 {
 358     short           i, c, n;
 359
 360     n = getbits(CBIT);
 361     if (n == 0) {
 362         c = getbits(CBIT);
 363         for (i = 0; i < NC; i++)
 364             c_len[i] = 0;
 365         for (i = 0; i < 4096; i++)
 366             c_table[i] = c;
 367     } else {
 368         i = 0;
 369         while (i < n) {
 370             c = pt_table[bitbuf >> (16 - 8)];
 371             if (c >= NT) {
 372                 unsigned short  mask = 1 << (16 - 9);
 373                 do {
 374                     if (bitbuf & mask)
 375                         c = right[c];
 376                     else
 377                         c = left[c];
 378                     mask >>= 1;
 379                 } while (c >= NT);
 380             }
 381             fillbuf(pt_len[c]);
 382             if (c <= 2) {
 383                 if (c == 0)
 384                     c = 1;
 385                 else if (c == 1)
 386                     c = getbits(4) + 3;
 387                 else
 388                     c = getbits(CBIT) + 20;
 389                 while (--c >= 0)
 390                     c_len[i++] = 0;
 391             }
 392             else
 393                 c_len[i++] = c - 2;
 394         }
 395         while (i < NC)
 396             c_len[i++] = 0;
 397         make_table(NC, c_len, 12, c_table);
 398     }
 399 }
 400
 401 /* ------------------------------------------------------------------------ */
 402 /* lh4, 5, 6, 7 */
 403 unsigned short
 404 decode_c_st1( /*void*/ )
 405 {
 406     unsigned short  j, mask;
 407
 408     if (blocksize == 0) {
 409         blocksize = getbits(16);
 410         read_pt_len(NT, TBIT, 3);
 411         read_c_len();
 412         read_pt_len(np, pbit, -1);
 413     }
 414     blocksize--;
 415     j = c_table[bitbuf >> 4];
 416     if (j < NC)
 417         fillbuf(c_len[j]);
 418     else {
 419         fillbuf(12);
 420         mask = 1 << (16 - 1);
 421         do {
 422             if (bitbuf & mask)
 423                 j = right[j];
 424             else
 425                 j = left[j];
 426             mask >>= 1;
 427         } while (j >= NC);
 428         fillbuf(c_len[j] - 12);
 429     }
 430     return j;
 431 }
 432
 433 /* ------------------------------------------------------------------------ */
 434 /* lh4, 5, 6, 7 */
 435 unsigned short
 436 decode_p_st1( /* void */ )
 437 {
 438     unsigned short  j, mask;
 439
 440     j = pt_table[bitbuf >> (16 - 8)];
 441     if (j < np)
 442         fillbuf(pt_len[j]);
 443     else {
 444         fillbuf(8);
 445         mask = 1 << (16 - 1);
 446         do {
 447             if (bitbuf & mask)
 448                 j = right[j];
 449             else
 450                 j = left[j];
 451             mask >>= 1;
 452         } while (j >= np);
 453         fillbuf(pt_len[j] - 8);
 454     }
 455     if (j != 0)
 456         j = (1 << (j - 1)) + getbits(j - 1);
 457     return j;
 458 }
 459
 460 /* ------------------------------------------------------------------------ */
 461 /* lh4, 5, 6, 7 */
 462 void
 463 decode_start_st1( /* void */ )
 464 {
 465     switch (dicbit) {
 466     case LZHUFF4_DICBIT:
 467     case LZHUFF5_DICBIT: pbit = 4; np = LZHUFF5_DICBIT + 1; break;
 468     case LZHUFF6_DICBIT: pbit = 5; np = LZHUFF6_DICBIT + 1; break;
 469     case LZHUFF7_DICBIT: pbit = 5; np = LZHUFF7_DICBIT + 1; break;
 470     default:
 471         assert(0);
 472     }
 473
 474     init_getbits();
 475     init_code_cache();
 476     blocksize = 0;
 477 }