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 void
  73 decode_start_dyn( /* void */ )
  74 {
  75         n_max = 286;
  76         maxmatch = MAXMATCH;
  77         init_getbits();
  78         start_c_dyn();
  79         start_p_dyn();
  80 }
  81
  82 /* ------------------------------------------------------------------------ */
  83 static void
  84 reconst(start, end)
  85         int             start;
  86         int             end;
  87 {
  88         int             i, j, k, l, b;
  89         unsigned int    f, g;
  90
  91         for (i = j = start; i < end; i++) {
  92                 if ((k = child[i]) < 0) {
  93                         freq[j] = (freq[i] + 1) / 2;
  94                         child[j] = k;
  95                         j++;
  96                 }
  97                 if (edge[b = block[i]] == i) {
  98                         stock[--avail] = b;
  99                 }
 100         }
 101         j--;
 102         i = end - 1;
 103         l = end - 2;
 104         while (i >= start) {
 105                 while (i >= l) {
 106                         freq[i] = freq[j];
 107                         child[i] = child[j];
 108                         i--, j--;
 109                 }
 110                 f = freq[l] + freq[l + 1];
 111                 for (k = start; f < freq[k]; k++);
 112                 while (j >= k) {
 113                         freq[i] = freq[j];
 114                         child[i] = child[j];
 115                         i--, j--;
 116                 }
 117                 freq[i] = f;
 118                 child[i] = l + 1;
 119                 i--;
 120                 l -= 2;
 121         }
 122         f = 0;
 123         for (i = start; i < end; i++) {
 124                 if ((j = child[i]) < 0)
 125                         s_node[~j] = i;
 126                 else
 127                         parent[j] = parent[j - 1] = i;
 128                 if ((g = freq[i]) == f) {
 129                         block[i] = b;
 130                 }
 131                 else {
 132                         edge[b = block[i] = stock[avail++]] = i;
 133                         f = g;
 134                 }
 135         }
 136 }
 137
 138 /* ------------------------------------------------------------------------ */
 139 static int
 140 swap_inc(p)
 141         int             p;
 142 {
 143         int             b, q, r, s;
 144
 145         b = block[p];
 146         if ((q = edge[b]) != p) {       /* swap for leader */
 147                 r = child[p];
 148                 s = child[q];
 149                 child[p] = s;
 150                 child[q] = r;
 151                 if (r >= 0)
 152                         parent[r] = parent[r - 1] = q;
 153                 else
 154                         s_node[~r] = q;
 155                 if (s >= 0)
 156                         parent[s] = parent[s - 1] = p;
 157                 else
 158                         s_node[~s] = p;
 159                 p = q;
 160                 goto Adjust;
 161         }
 162         else if (b == block[p + 1]) {
 163 Adjust:
 164                 edge[b]++;
 165                 if (++freq[p] == freq[p - 1]) {
 166                         block[p] = block[p - 1];
 167                 }
 168                 else {
 169                         edge[block[p] = stock[avail++]] = p;    /* create block */
 170                 }
 171         }
 172         else if (++freq[p] == freq[p - 1]) {
 173                 stock[--avail] = b;     /* delete block */
 174                 block[p] = block[p - 1];
 175         }
 176         return parent[p];
 177 }
 178
 179 /* ------------------------------------------------------------------------ */
 180 static void
 181 update_c(p)
 182         int             p;
 183 {
 184         int             q;
 185
 186         if (freq[ROOT_C] == 0x8000) {
 187                 reconst(0, n_max * 2 - 1);
 188         }
 189         freq[ROOT_C]++;
 190         q = s_node[p];
 191         do {
 192                 q = swap_inc(q);
 193         } while (q != ROOT_C);
 194 }
 195
 196 /* ------------------------------------------------------------------------ */
 197 static void
 198 update_p(p)
 199         int             p;
 200 {
 201         int             q;
 202
 203         if (total_p == 0x8000) {
 204                 reconst(ROOT_P, most_p + 1);
 205                 total_p = freq[ROOT_P];
 206                 freq[ROOT_P] = 0xffff;
 207         }
 208         q = s_node[p + N_CHAR];
 209         while (q != ROOT_P) {
 210                 q = swap_inc(q);
 211         }
 212         total_p++;
 213 }
 214
 215 /* ------------------------------------------------------------------------ */
 216 static void
 217 make_new_node(p)
 218         int             p;
 219 {
 220         int             q, r;
 221
 222         r = most_p + 1;
 223         q = r + 1;
 224         s_node[~(child[r] = child[most_p])] = r;
 225         child[q] = ~(p + N_CHAR);
 226         child[most_p] = q;
 227         freq[r] = freq[most_p];
 228         freq[q] = 0;
 229         block[r] = block[most_p];
 230         if (most_p == ROOT_P) {
 231                 freq[ROOT_P] = 0xffff;
 232                 edge[block[ROOT_P]]++;
 233         }
 234         parent[r] = parent[q] = most_p;
 235         edge[block[q] = stock[avail++]] = s_node[p + N_CHAR] = most_p = q;
 236         update_p(p);
 237 }
 238
 239 /* ------------------------------------------------------------------------ */
 240 static void
 241 encode_c_dyn(c)
 242         unsigned int    c;
 243 {
 244         unsigned int    bits;
 245         int             p, d, cnt;
 246
 247         d = c - n1;
 248         if (d >= 0) {
 249                 c = n1;
 250         }
 251         cnt = bits = 0;
 252         p = s_node[c];
 253         do {
 254                 bits >>= 1;
 255                 if (p & 1) {
 256                         bits |= 0x8000;
 257                 }
 258                 if (++cnt == 16) {
 259                         putcode(16, bits);
 260                         cnt = bits = 0;
 261                 }
 262         } while ((p = parent[p]) != ROOT_C);
 263         putcode(cnt, bits);
 264         if (d >= 0)
 265                 putbits(8, d);
 266         update_c(c);
 267 }
 268
 269 /* ------------------------------------------------------------------------ */
 270 unsigned short
 271 decode_c_dyn( /* void */ )
 272 {
 273         int             c;
 274         short           buf, cnt;
 275
 276         c = child[ROOT_C];
 277         buf = bitbuf;
 278         cnt = 0;
 279         do {
 280                 c = child[c - (buf < 0)];
 281                 buf <<= 1;
 282                 if (++cnt == 16) {
 283                         fillbuf(16);
 284                         buf = bitbuf;
 285                         cnt = 0;
 286                 }
 287         } while (c > 0);
 288         fillbuf(cnt);
 289         c = ~c;
 290         update_c(c);
 291         if (c == n1)
 292                 c += getbits(8);
 293         return c;
 294 }
 295
 296 /* ------------------------------------------------------------------------ */
 297 unsigned short
 298 decode_p_dyn( /* void */ )
 299 {
 300         int             c;
 301         short           buf, cnt;
 302
 303         while (count > nextcount) {
 304                 make_new_node(nextcount / 64);
 305                 if ((nextcount += 64) >= nn)
 306                         nextcount = 0xffffffff;
 307         }
 308         c = child[ROOT_P];
 309         buf = bitbuf;
 310         cnt = 0;
 311         while (c > 0) {
 312                 c = child[c - (buf < 0)];
 313                 buf <<= 1;
 314                 if (++cnt == 16) {
 315                         fillbuf(16);
 316                         buf = bitbuf;
 317                         cnt = 0;
 318                 }
 319         }
 320         fillbuf(cnt);
 321         c = (~c) - N_CHAR;
 322         update_p(c);
 323
 324         return (c << 6) + getbits(6);
 325 }
 326
 327 /* ------------------------------------------------------------------------ */
 328 void
 329 output_dyn(code, pos)
 330         unsigned int    code;
 331         unsigned int    pos;
 332 {
 333         encode_c_dyn(code);
 334         if (code >= 0x100) {
 335                 encode_p_st0(pos);
 336         }
 337 }
 338
 339 /* ------------------------------------------------------------------------ */
 340 void
 341 encode_end_dyn( /* void */ )
 342 {
 343         putcode(7, 0);
 344 }
 345
 346 /* Local Variables: */
 347 /* mode:c */
 348 /* tab-width:4 */
 349 /* End: */