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 = peekbits(3);
 333             if (c != 7)
 334                 fillbuf(3);
 335             else {
 336                 unsigned short  mask = 1 << (16 - 4);
 337                 while (mask & bitbuf) {
 338                     mask >>= 1;
 339                     c++;
 340                 }
 341                 fillbuf(c - 3);         /* fillbuf(c - 7 + 3); ??? */
 342             }
 343
 344             pt_len[i++] = c;
 345             if (i == i_special) {
 346                 c = getbits(2);
 347                 while (--c >= 0)
 348                     pt_len[i++] = 0;
 349             }
 350         }
 351         while (i < nn)
 352             pt_len[i++] = 0;
 353         make_table(nn, pt_len, 8, pt_table);
 354     }
 355 }
 356
 357 /* ------------------------------------------------------------------------ */
 358 static void
 359 read_c_len( /* void */ )
 360 {
 361     short           i, c, n;
 362
 363     n = getbits(CBIT);
 364     if (n == 0) {
 365         c = getbits(CBIT);
 366         for (i = 0; i < NC; i++)
 367             c_len[i] = 0;
 368         for (i = 0; i < 4096; i++)
 369             c_table[i] = c;
 370     } else {
 371         i = 0;
 372         while (i < n) {
 373             c = pt_table[peekbits(8)];
 374             if (c >= NT) {
 375                 unsigned short  mask = 1 << (16 - 9);
 376                 do {
 377                     if (bitbuf & mask)
 378                         c = right[c];
 379                     else
 380                         c = left[c];
 381                     mask >>= 1;
 382                 } while (c >= NT);
 383             }
 384             fillbuf(pt_len[c]);
 385             if (c <= 2) {
 386                 if (c == 0)
 387                     c = 1;
 388                 else if (c == 1)
 389                     c = getbits(4) + 3;
 390                 else
 391                     c = getbits(CBIT) + 20;
 392                 while (--c >= 0)
 393                     c_len[i++] = 0;
 394             }
 395             else
 396                 c_len[i++] = c - 2;
 397         }
 398         while (i < NC)
 399             c_len[i++] = 0;
 400         make_table(NC, c_len, 12, c_table);
 401     }
 402 }
 403
 404 /* ------------------------------------------------------------------------ */
 405 /* lh4, 5, 6, 7 */
 406 unsigned short
 407 decode_c_st1( /*void*/ )
 408 {
 409     unsigned short  j, mask;
 410
 411     if (blocksize == 0) {
 412         blocksize = getbits(16);
 413         read_pt_len(NT, TBIT, 3);
 414         read_c_len();
 415         read_pt_len(np, pbit, -1);
 416     }
 417     blocksize--;
 418     j = c_table[peekbits(12)];
 419     if (j < NC)
 420         fillbuf(c_len[j]);
 421     else {
 422         fillbuf(12);
 423         mask = 1 << (16 - 1);
 424         do {
 425             if (bitbuf & mask)
 426                 j = right[j];
 427             else
 428                 j = left[j];
 429             mask >>= 1;
 430         } while (j >= NC);
 431         fillbuf(c_len[j] - 12);
 432     }
 433     return j;
 434 }
 435
 436 /* ------------------------------------------------------------------------ */
 437 /* lh4, 5, 6, 7 */
 438 unsigned short
 439 decode_p_st1( /* void */ )
 440 {
 441     unsigned short  j, mask;
 442
 443     j = pt_table[peekbits(8)];
 444     if (j < np)
 445         fillbuf(pt_len[j]);
 446     else {
 447         fillbuf(8);
 448         mask = 1 << (16 - 1);
 449         do {
 450             if (bitbuf & mask)
 451                 j = right[j];
 452             else
 453                 j = left[j];
 454             mask >>= 1;
 455         } while (j >= np);
 456         fillbuf(pt_len[j] - 8);
 457     }
 458     if (j != 0)
 459         j = (1 << (j - 1)) + getbits(j - 1);
 460     return j;
 461 }
 462
 463 /* ------------------------------------------------------------------------ */
 464 /* lh4, 5, 6, 7 */
 465 void
 466 decode_start_st1( /* void */ )
 467 {
 468     switch (dicbit) {
 469     case LZHUFF4_DICBIT:
 470     case LZHUFF5_DICBIT: pbit = 4; np = LZHUFF5_DICBIT + 1; break;
 471     case LZHUFF6_DICBIT: pbit = 5; np = LZHUFF6_DICBIT + 1; break;
 472     case LZHUFF7_DICBIT: pbit = 5; np = LZHUFF7_DICBIT + 1; break;
 473     default:
 474         assert(0);
 475     }
 476
 477     init_getbits();
 478     init_code_cache();
 479     blocksize = 0;
 480 }