huf.c

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