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 (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 }
 353
 354 /* Local Variables: */
 355 /* mode:c */
 356 /* tab-width:4 */
 357 /* End: */
 358 /* vi: set tabstop=4: */