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