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