src/dhuf.c

   1 /* ------------------------------------------------------------------------ */
   2 /* LHa for UNIX                                                             */
   3 /*              dhuf.c -- Dynamic Hufffman routine                          */
   4 /*                                                                          */
   5 /*      Modified                H.Yoshizaki                                 */
   6 /*                                                                          */
   7 /*  Ver. 1.14   Source All chagned              1995.01.14  N.Watazaki      */
   8 /* ------------------------------------------------------------------------ */
   9 #include "lha.h"
  10
  11 /* ------------------------------------------------------------------------ */
  12 static short    child[TREESIZE], parent[TREESIZE], block[TREESIZE], edge[TREESIZE], stock[TREESIZE],
  13                 s_node[TREESIZE / 2];   /* Changed N.Watazaki */
  14 /*  node[..] -> s_node[..] */
  15
  16 static unsigned short freq[TREESIZE];
  17
  18 static unsigned short total_p;
  19 static int      avail, n1;
  20 static int      most_p, nn;
  21 static unsigned long nextcount;
  22 /* ------------------------------------------------------------------------ */
  23 void
  24 start_c_dyn( /* void */ )
  25 {
  26     int             i, j, f;
  27
  28     n1 = (n_max >= 256 + maxmatch - THRESHOLD + 1) ? 512 : n_max - 1;
  29     for (i = 0; i < TREESIZE_C; i++) {
  30         stock[i] = i;
  31         block[i] = 0;
  32     }
  33     for (i = 0, j = n_max * 2 - 2; i < n_max; i++, j--) {
  34         freq[j] = 1;
  35         child[j] = ~i;
  36         s_node[i] = j;
  37         block[j] = 1;
  38     }
  39     avail = 2;
  40     edge[1] = n_max - 1;
  41     i = n_max * 2 - 2;
  42     while (j >= 0) {
  43         f = freq[j] = freq[i] + freq[i - 1];
  44         child[j] = i;
  45         parent[i] = parent[i - 1] = j;
  46         if (f == freq[j + 1]) {
  47             edge[block[j] = block[j + 1]] = j;
  48         }
  49         else {
  50             edge[block[j] = stock[avail++]] = j;
  51         }
  52         i -= 2;
  53         j--;
  54     }
  55 }
  56
  57 /* ------------------------------------------------------------------------ */
  58 static void
  59 start_p_dyn( /* void */ )
  60 {
  61     freq[ROOT_P] = 1;
  62     child[ROOT_P] = ~(N_CHAR);
  63     s_node[N_CHAR] = ROOT_P;
  64     edge[block[ROOT_P] = stock[avail++]] = ROOT_P;
  65     most_p = ROOT_P;
  66     total_p = 0;
  67     nn = 1 << dicbit;
  68     nextcount = 64;
  69 }
  70
  71 /* ------------------------------------------------------------------------ */
  72 /* lh2 */
  73 void
  74 decode_start_dyn( /* void */ )
  75 {
  76     n_max = 286;
  77     maxmatch = MAXMATCH;
  78     init_getbits();
  79     init_code_cache();
  80     start_c_dyn();
  81     start_p_dyn();
  82 }
  83
  84 /* ------------------------------------------------------------------------ */
  85 static void
  86 reconst(start, end)
  87     int             start;
  88     int             end;
  89 {
  90     int             i, j, k, l, b;
  91     unsigned int    f, g;
  92
  93     for (i = j = start; i < end; i++) {
  94         if ((k = child[i]) < 0) {
  95             freq[j] = (freq[i] + 1) / 2;
  96             child[j] = k;
  97             j++;
  98         }
  99         if (edge[b = block[i]] == i) {
 100             stock[--avail] = b;
 101         }
 102     }
 103     j--;
 104     i = end - 1;
 105     l = end - 2;
 106     while (i >= start) {
 107         while (i >= l) {
 108             freq[i] = freq[j];
 109             child[i] = child[j];
 110             i--, j--;
 111         }
 112         f = freq[l] + freq[l + 1];
 113         for (k = start; f < freq[k]; k++);
 114         while (j >= k) {
 115             freq[i] = freq[j];
 116             child[i] = child[j];
 117             i--, j--;
 118         }
 119         freq[i] = f;
 120         child[i] = l + 1;
 121         i--;
 122         l -= 2;
 123     }
 124     f = 0;
 125     for (i = start; i < end; i++) {
 126         if ((j = child[i]) < 0)
 127             s_node[~j] = i;
 128         else
 129             parent[j] = parent[j - 1] = i;
 130         if ((g = freq[i]) == f) {
 131             block[i] = b;
 132         }
 133         else {
 134             edge[b = block[i] = stock[avail++]] = i;
 135             f = g;
 136         }
 137     }
 138 }
 139
 140 /* ------------------------------------------------------------------------ */
 141 static int
 142 swap_inc(p)
 143     int             p;
 144 {
 145     int             b, q, r, s;
 146
 147     b = block[p];
 148     if ((q = edge[b]) != p) {   /* swap for leader */
 149         r = child[p];
 150         s = child[q];
 151         child[p] = s;
 152         child[q] = r;
 153         if (r >= 0)
 154             parent[r] = parent[r - 1] = q;
 155         else
 156             s_node[~r] = q;
 157         if (s >= 0)
 158             parent[s] = parent[s - 1] = p;
 159         else
 160             s_node[~s] = p;
 161         p = q;
 162         goto Adjust;
 163     }
 164     else if (b == block[p + 1]) {
 165 Adjust:
 166         edge[b]++;
 167         if (++freq[p] == freq[p - 1]) {
 168             block[p] = block[p - 1];
 169         }
 170         else {
 171             edge[block[p] = stock[avail++]] = p;    /* create block */
 172         }
 173     }
 174     else if (++freq[p] == freq[p - 1]) {
 175         stock[--avail] = b; /* delete block */
 176         block[p] = block[p - 1];
 177     }
 178     return parent[p];
 179 }
 180
 181 /* ------------------------------------------------------------------------ */
 182 static void
 183 update_c(p)
 184     int             p;
 185 {
 186     int             q;
 187
 188     if (freq[ROOT_C] == 0x8000) {
 189         reconst(0, n_max * 2 - 1);
 190     }
 191     freq[ROOT_C]++;
 192     q = s_node[p];
 193     do {
 194         q = swap_inc(q);
 195     } while (q != ROOT_C);
 196 }
 197
 198 /* ------------------------------------------------------------------------ */
 199 static void
 200 update_p(p)
 201     int             p;
 202 {
 203     int             q;
 204
 205     if (total_p == 0x8000) {
 206         reconst(ROOT_P, most_p + 1);
 207         total_p = freq[ROOT_P];
 208         freq[ROOT_P] = 0xffff;
 209     }
 210     q = s_node[p + N_CHAR];
 211     while (q != ROOT_P) {
 212         q = swap_inc(q);
 213     }
 214     total_p++;
 215 }
 216
 217 /* ------------------------------------------------------------------------ */
 218 static void
 219 make_new_node(p)
 220     int             p;
 221 {
 222     int             q, r;
 223
 224     r = most_p + 1;
 225     q = r + 1;
 226     s_node[~(child[r] = child[most_p])] = r;
 227     child[q] = ~(p + N_CHAR);
 228     child[most_p] = q;
 229     freq[r] = freq[most_p];
 230     freq[q] = 0;
 231     block[r] = block[most_p];
 232     if (most_p == ROOT_P) {
 233         freq[ROOT_P] = 0xffff;
 234         edge[block[ROOT_P]]++;
 235     }
 236     parent[r] = parent[q] = most_p;
 237     edge[block[q] = stock[avail++]] = s_node[p + N_CHAR] = most_p = q;
 238     update_p(p);
 239 }
 240
 241 /* ------------------------------------------------------------------------ */
 242 static void
 243 encode_c_dyn(c)
 244     unsigned int    c;
 245 {
 246     unsigned int    bits;
 247     int             p, d, cnt;
 248
 249     d = c - n1;
 250     if (d >= 0) {
 251         c = n1;
 252     }
 253     cnt = bits = 0;
 254     p = s_node[c];
 255     do {
 256         bits >>= 1;
 257         if (p & 1) {
 258             bits |= 0x80000000L;
 259         }
 260         cnt++;
 261     } while ((p = parent[p]) != ROOT_C);
 262     if (cnt <= 16) {
 263         putcode(cnt, bits >> 16);
 264     } else {
 265         putcode(16, bits >> 16);
 266         putbits(cnt - 16, bits);
 267     }
 268     if (d >= 0)
 269         putbits(8, d);
 270     update_c(c);
 271 }
 272
 273 /* ------------------------------------------------------------------------ */
 274 /* lh1, 2 */
 275 unsigned short
 276 decode_c_dyn( /* void */ )
 277 {
 278     int             c;
 279     short           buf, cnt;
 280
 281     c = child[ROOT_C];
 282     buf = bitbuf;
 283     cnt = 0;
 284     do {
 285         c = child[c - (buf < 0)];
 286         buf <<= 1;
 287         if (++cnt == 16) {
 288             fillbuf(16);
 289             buf = bitbuf;
 290             cnt = 0;
 291         }
 292     } while (c > 0);
 293     fillbuf(cnt);
 294     c = ~c;
 295     update_c(c);
 296     if (c == n1)
 297         c += getbits(8);
 298     return c;
 299 }
 300
 301 /* ------------------------------------------------------------------------ */
 302 /* lh2 */
 303 unsigned short
 304 decode_p_dyn( /* void */ )
 305 {
 306     int             c;
 307     short           buf, cnt;
 308
 309     while (decode_count > nextcount) {
 310         make_new_node(nextcount / 64);
 311         if ((nextcount += 64) >= nn)
 312             nextcount = 0xffffffff;
 313     }
 314     c = child[ROOT_P];
 315     buf = bitbuf;
 316     cnt = 0;
 317     while (c > 0) {
 318         c = child[c - (buf < 0)];
 319         buf <<= 1;
 320         if (++cnt == 16) {
 321             fillbuf(16);
 322             buf = bitbuf;
 323             cnt = 0;
 324         }
 325     }
 326     fillbuf(cnt);
 327     c = (~c) - N_CHAR;
 328     update_p(c);
 329
 330     return (c << 6) + getbits(6);
 331 }
 332
 333 /* ------------------------------------------------------------------------ */
 334 /* lh1 */
 335 void
 336 output_dyn(code, pos)
 337     unsigned int    code;
 338     unsigned int    pos;
 339 {
 340     encode_c_dyn(code);
 341     if (code >= 0x100) {
 342         encode_p_st0(pos);
 343     }
 344 }
 345
 346 /* ------------------------------------------------------------------------ */
 347 /* lh1 */
 348 void
 349 encode_end_dyn( /* void */ )
 350 {
 351     putcode(7, 0);
 352 }