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