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