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 }
 478
 479 /* Local Variables: */
 480 /* mode:c */
 481 /* tab-width:4 */
 482 /* End: */
 483 /* vi: set tabstop=4: */