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