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