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