usr.bin/window/compress.c

   1 /*
   2  * Copyright (c) 1989, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Edward Wang at The University of California, Berkeley.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #ifndef lint
  38 static char sccsid[] = "@(#)compress.c  8.1 (Berkeley) 6/6/93";
  39 #endif /* not lint */
  40
  41 #include "ww.h"
  42 #include "tt.h"
  43
  44         /* special */
  45 #include <stdio.h>
  46 #include <fcntl.h>
  47 int cc_trace = 0;
  48 FILE *cc_trace_fp;
  49
  50         /* tunable parameters */
  51
  52 int cc_reverse = 1;
  53 int cc_sort = 0;
  54 int cc_chop = 0;
  55
  56 int cc_token_max = 8;           /* <= TOKEN_MAX */
  57 int cc_token_min = 2;           /* > tt.tt_put_token_cost */
  58 int cc_npass0 = 1;
  59 int cc_npass1 = 1;
  60
  61 int cc_bufsize = 1024 * 3;      /* XXX, or 80 * 24 * 2 */
  62
  63 int cc_ntoken = 8192;
  64
  65 #define cc_weight XXX
  66 #ifndef cc_weight
  67 int cc_weight = 0;
  68 #endif
  69
  70 #define TOKEN_MAX 16
  71
  72 struct cc {
  73         char string[TOKEN_MAX];
  74         char length;
  75         char flag;
  76 #ifndef cc_weight
  77         short weight;
  78 #endif
  79         long time;              /* time last seen */
  80         short bcount;           /* count in this buffer */
  81         short ccount;           /* count in compression */
  82         short places;           /* places in the buffer */
  83         short code;             /* token code */
  84         struct cc *qforw, *qback;
  85         struct cc *hforw, **hback;
  86 };
  87
  88 short cc_thresholds[TOKEN_MAX + 1];
  89 #define thresh(length) (cc_thresholds[length])
  90 #define threshp(code, count, length) \
  91         ((code) >= 0 || (short) (count) >= cc_thresholds[length])
  92
  93 #ifndef cc_weight
  94 short cc_wthresholds[TOKEN_MAX + 1];
  95 #define wthresh(length) (cc_wthresholds[length])
  96 #define wthreshp(weight, length) ((short) (weight) >= cc_wthresholds[length])
  97 #else
  98 #define wthreshp(weight, length) (0)
  99 #endif
 100
 101 #ifndef cc_weight
 102 short cc_wlimits[TOKEN_MAX + 1];
 103 #define wlimit(length) (cc_wlimits[length])
 104 #endif
 105
 106 #define put_token_score(length) ((length) - tt.tt_put_token_cost)
 107
 108 int cc_score_adjustments[TOKEN_MAX + 1][8]; /* XXX, 8 > max of cc_thresholds */
 109 #define score_adjust(score, p) \
 110         do { \
 111                 int length = (p)->length; \
 112                 int ccount = (p)->ccount; \
 113                 if (threshp((p)->code, ccount, length) || \
 114                     wthreshp((p)->weight, length)) /* XXX */ \
 115                         (score) -= length - tt.tt_put_token_cost; \
 116                 else \
 117                         (score) += cc_score_adjustments[length][ccount]; \
 118         } while (0)
 119
 120 int cc_initial_scores[TOKEN_MAX + 1][8]; /* XXX, 8 > max of cc_thresholds */
 121
 122 struct cc cc_q0a, cc_q0b, cc_q1a, cc_q1b;
 123
 124 #define qinsert(p1, p2) \
 125         do { \
 126                 register struct cc *forw = (p1)->qforw; \
 127                 register struct cc *back = (p1)->qback; \
 128                 back->qforw = forw; \
 129                 forw->qback = back; \
 130                 forw = (p2)->qforw; \
 131                 (p1)->qforw = forw; \
 132                 forw->qback = (p1); \
 133                 (p2)->qforw = (p1); \
 134                 (p1)->qback = (p2); \
 135         } while (0)
 136
 137 #define qinsertq(q, p) \
 138         ((q)->qforw == (q) ? 0 : \
 139          ((q)->qback->qforw = (p)->qforw, \
 140           (p)->qforw->qback = (q)->qback, \
 141           (q)->qforw->qback = (p), \
 142           (p)->qforw = (q)->qforw, \
 143           (q)->qforw = (q), \
 144           (q)->qback = (q)))
 145
 146 #define H               (14)
 147 #define HSIZE           (1 << H)
 148 #define hash(h, c)      ((((h) >> H - 8 | (h) << 8) ^ (c)) & HSIZE - 1)
 149
 150 char *cc_buffer;
 151 struct cc **cc_output;                  /* the output array */
 152 short *cc_places[TOKEN_MAX + 1];
 153 short *cc_hashcodes;                    /* for computing hashcodes */
 154 struct cc **cc_htab;                    /* the hash table */
 155 struct cc **cc_tokens;                  /* holds all the active tokens */
 156 struct cc_undo {
 157         struct cc **pos;
 158         struct cc *val;
 159 } *cc_undo;
 160
 161 long cc_time, cc_time0;
 162
 163 char *cc_tt_ob, *cc_tt_obe;
 164
 165 ccinit()
 166 {
 167         register i, j;
 168         register struct cc *p;
 169
 170         if (tt.tt_token_max > cc_token_max)
 171                 tt.tt_token_max = cc_token_max;
 172         if (tt.tt_token_min < cc_token_min)
 173                 tt.tt_token_min = cc_token_min;
 174         if (tt.tt_token_min > tt.tt_token_max) {
 175                 tt.tt_ntoken = 0;
 176                 return 0;
 177         }
 178         if (tt.tt_ntoken > cc_ntoken / 2)       /* not likely */
 179                 tt.tt_ntoken = cc_ntoken / 2;
 180 #define C(x) (sizeof (x) / sizeof *(x))
 181         for (i = 0; i < C(cc_thresholds); i++) {
 182                 int h = i - tt.tt_put_token_cost;
 183                 if (h > 0)
 184                         cc_thresholds[i] =
 185                                 (tt.tt_set_token_cost + 1 + h - 1) / h + 1;
 186                 else
 187                         cc_thresholds[i] = 0;
 188         }
 189         for (i = 0; i < C(cc_score_adjustments); i++) {
 190                 int t = cc_thresholds[i];
 191                 for (j = 0; j < C(*cc_score_adjustments); j++) {
 192                         if (j >= t)
 193                                 cc_score_adjustments[i][j] =
 194                                         - (i - tt.tt_put_token_cost);
 195                         else if (j < t - 1)
 196                                 cc_score_adjustments[i][j] = 0;
 197                         else
 198                                 /*
 199                                  * cost now is
 200                                  *      length * (ccount + 1)           a
 201                                  * cost before was
 202                                  *      set-token-cost + length +
 203                                  *              ccount * put-token-cost b
 204                                  * the score adjustment is (b - a)
 205                                  */
 206                                 cc_score_adjustments[i][j] =
 207                                         tt.tt_set_token_cost + i +
 208                                                 j * tt.tt_put_token_cost -
 209                                                         i * (j + 1);
 210                         if (j >= t)
 211                                 cc_initial_scores[i][j] = 0;
 212                         else
 213                                 /*
 214                                  * - (set-token-cost +
 215                                  *      (length - put-token-cost) -
 216                                  *      (length - put-token-cost) * ccount)
 217                                  */
 218                                 cc_initial_scores[i][j] =
 219                                         - (tt.tt_set_token_cost +
 220                                            (i - tt.tt_put_token_cost) -
 221                                            (i - tt.tt_put_token_cost) * j);
 222                 }
 223         }
 224 #ifndef cc_weight
 225         for (i = 1; i < C(cc_wthresholds); i++) {
 226                 cc_wthresholds[i] =
 227                         ((tt.tt_set_token_cost + tt.tt_put_token_cost) / i +
 228                                 i / 5 + 1) *
 229                                 cc_weight + 1;
 230                 cc_wlimits[i] = cc_wthresholds[i] + cc_weight;
 231         }
 232 #endif
 233 #undef C
 234         if ((cc_output = (struct cc **)
 235              malloc((unsigned) cc_bufsize * sizeof *cc_output)) == 0)
 236                 goto nomem;
 237         if ((cc_hashcodes = (short *)
 238              malloc((unsigned) cc_bufsize * sizeof *cc_hashcodes)) == 0)
 239                 goto nomem;
 240         if ((cc_htab = (struct cc **) malloc(HSIZE * sizeof *cc_htab)) == 0)
 241                 goto nomem;
 242         if ((cc_tokens = (struct cc **)
 243              malloc((unsigned)
 244                     (cc_ntoken + tt.tt_token_max - tt.tt_token_min + 1) *
 245                     sizeof *cc_tokens)) == 0)
 246                 goto nomem;
 247         if ((cc_undo = (struct cc_undo *)
 248              malloc((unsigned) cc_bufsize * sizeof *cc_undo)) == 0)
 249                 goto nomem;
 250         for (i = tt.tt_token_min; i <= tt.tt_token_max; i++)
 251                 if ((cc_places[i] = (short *)
 252                      malloc((unsigned) cc_bufsize * sizeof **cc_places)) == 0)
 253                         goto nomem;
 254         cc_q0a.qforw = cc_q0a.qback = &cc_q0a;
 255         cc_q0b.qforw = cc_q0b.qback = &cc_q0b;
 256         cc_q1a.qforw = cc_q1a.qback = &cc_q1a;
 257         cc_q1b.qforw = cc_q1b.qback = &cc_q1b;
 258         if ((p = (struct cc *) malloc((unsigned) cc_ntoken * sizeof *p)) == 0)
 259                 goto nomem;
 260         for (i = 0; i < tt.tt_ntoken; i++) {
 261                 p->code = i;
 262                 p->time = -1;
 263                 p->qback = cc_q0a.qback;
 264                 p->qforw = &cc_q0a;
 265                 p->qback->qforw = p;
 266                 cc_q0a.qback = p;
 267                 p++;
 268         }
 269         for (; i < cc_ntoken; i++) {
 270                 p->code = -1;
 271                 p->time = -1;
 272                 p->qback = cc_q1a.qback;
 273                 p->qforw = &cc_q1a;
 274                 p->qback->qforw = p;
 275                 cc_q1a.qback = p;
 276                 p++;
 277         }
 278         cc_tt_ob = tt_ob;
 279         cc_tt_obe = tt_obe;
 280         if ((cc_buffer = malloc((unsigned) cc_bufsize)) == 0)
 281                 goto nomem;
 282         return 0;
 283 nomem:
 284         wwerrno = WWE_NOMEM;
 285         return -1;
 286 }
 287
 288 ccstart()
 289 {
 290         int ccflush();
 291
 292         ttflush();
 293         tt_obp = tt_ob = cc_buffer;
 294         tt_obe = tt_ob + cc_bufsize;
 295         tt.tt_flush = ccflush;
 296         if (cc_trace) {
 297                 cc_trace_fp = fopen("window-trace", "a");
 298                 (void) fcntl(fileno(cc_trace_fp), F_SETFD, 1);
 299         }
 300         ccreset();
 301 }
 302
 303 ccreset()
 304 {
 305         register struct cc *p;
 306
 307         bzero((char *) cc_htab, HSIZE * sizeof *cc_htab);
 308         for (p = cc_q0a.qforw; p != &cc_q0a; p = p->qforw)
 309                 p->hback = 0;
 310         for (p = cc_q1a.qforw; p != &cc_q1a; p = p->qforw)
 311                 p->hback = 0;
 312 }
 313
 314 ccend()
 315 {
 316
 317         ttflush();
 318         tt_obp = tt_ob = cc_tt_ob;
 319         tt_obe = cc_tt_obe;
 320         tt.tt_flush = 0;
 321         if (cc_trace_fp != NULL) {
 322                 (void) fclose(cc_trace_fp);
 323                 cc_trace_fp = NULL;
 324         }
 325 }
 326
 327 ccflush()
 328 {
 329         int bufsize = tt_obp - tt_ob;
 330         int n;
 331
 332         if (tt_ob != cc_buffer)
 333                 abort();
 334         if (cc_trace_fp != NULL) {
 335                 (void) fwrite(tt_ob, 1, bufsize, cc_trace_fp);
 336                 (void) putc(-1, cc_trace_fp);
 337         }
 338         tt.tt_flush = 0;
 339         (*tt.tt_compress)(1);
 340         if (bufsize < tt.tt_token_min) {
 341                 ttflush();
 342                 goto out;
 343         }
 344         tt_obp = tt_ob = cc_tt_ob;
 345         tt_obe = cc_tt_obe;
 346         cc_time0 = cc_time;
 347         cc_time += bufsize;
 348         n = cc_sweep_phase(cc_buffer, bufsize, cc_tokens);
 349         cc_compress_phase(cc_output, bufsize, cc_tokens, n);
 350         cc_output_phase(cc_buffer, cc_output, bufsize);
 351         ttflush();
 352         tt_obp = tt_ob = cc_buffer;
 353         tt_obe = cc_buffer + cc_bufsize;
 354 out:
 355         (*tt.tt_compress)(0);
 356         tt.tt_flush = ccflush;
 357 }
 358
 359 cc_sweep_phase(buffer, bufsize, tokens)
 360         char *buffer;
 361         struct cc **tokens;
 362 {
 363         register struct cc **pp = tokens;
 364         register i, n;
 365 #ifdef STATS
 366         int nn, ii;
 367 #endif
 368
 369 #ifdef STATS
 370         if (verbose >= 0)
 371                 time_begin();
 372         if (verbose > 0)
 373                 printf("Sweep:");
 374 #endif
 375         cc_sweep0(buffer, bufsize, tt.tt_token_min - 1);
 376 #ifdef STATS
 377         ntoken_stat = 0;
 378         nn = 0;
 379         ii = 0;
 380 #endif
 381         for (i = tt.tt_token_min; i <= tt.tt_token_max; i++) {
 382 #ifdef STATS
 383                 if (verbose > 0) {
 384                         if (ii > 7) {
 385                                 printf("\n      ");
 386                                 ii = 0;
 387                         }
 388                         ii++;
 389                         printf(" (%d", i);
 390                         (void) fflush(stdout);
 391                 }
 392 #endif
 393                 n = cc_sweep(buffer, bufsize, pp, i);
 394                 pp += n;
 395 #ifdef STATS
 396                 if (verbose > 0) {
 397                         if (--n > 0) {
 398                                 printf(" %d", n);
 399                                 nn += n;
 400                         }
 401                         putchar(')');
 402                 }
 403 #endif
 404         }
 405         qinsertq(&cc_q1b, &cc_q1a);
 406 #ifdef STATS
 407         if (verbose > 0)
 408                 printf("\n       %d tokens, %d candidates\n",
 409                         ntoken_stat, nn);
 410         if (verbose >= 0)
 411                 time_end();
 412 #endif
 413         return pp - tokens;
 414 }
 415
 416 cc_sweep0(buffer, n, length)
 417         char *buffer;
 418 {
 419         register char *p;
 420         register short *hc;
 421         register i;
 422         register short c;
 423         register short pc = tt.tt_padc;
 424
 425         /* n and length are at least 1 */
 426         p = buffer++;
 427         hc = cc_hashcodes;
 428         i = n;
 429         do {
 430                 if ((*hc++ = *p++) == pc)
 431                         hc[-1] = -1;
 432         } while (--i);
 433         while (--length) {
 434                 p = buffer++;
 435                 hc = cc_hashcodes;
 436                 for (i = n--; --i;) {
 437                         if ((c = *p++) == pc || *hc < 0)
 438                                 c = -1;
 439                         else
 440                                 c = hash(*hc, c);
 441                         *hc++ = c;
 442                 }
 443         }
 444 }
 445
 446 cc_sweep(buffer, bufsize, tokens, length)
 447         char *buffer;
 448         struct cc **tokens;
 449         register length;
 450 {
 451         register struct cc *p;
 452         register char *cp;
 453         register i;
 454         short *hc;
 455         short *places = cc_places[length];
 456         struct cc **pp = tokens;
 457         short threshold = thresh(length);
 458 #ifndef cc_weight
 459         short wthreshold = wthresh(length);
 460         short limit = wlimit(length);
 461 #endif
 462         int time;
 463         short pc = tt.tt_padc;
 464
 465         i = length - 1;
 466         bufsize -= i;
 467         cp = buffer + i;
 468         hc = cc_hashcodes;
 469         time = cc_time0;
 470         for (i = 0; i < bufsize; i++, time++) {
 471                 struct cc **h;
 472
 473                 {
 474                         register short *hc1 = hc;
 475                         register short c = *cp++;
 476                         register short hh;
 477                         if ((hh = *hc1) < 0 || c == pc) {
 478                                 *hc1++ = -1;
 479                                 hc = hc1;
 480                                 continue;
 481                         }
 482                         h = cc_htab + (*hc1++ = hash(hh, c));
 483                         hc = hc1;
 484                 }
 485                 for (p = *h; p != 0; p = p->hforw)
 486                         if (p->length == (char) length) {
 487                                 register char *p1 = p->string;
 488                                 register char *p2 = cp - length;
 489                                 register n = length;
 490                                 do
 491                                         if (*p1++ != *p2++)
 492                                                 goto fail;
 493                                 while (--n);
 494                                 break;
 495                         fail:;
 496                         }
 497                 if (p == 0) {
 498                         p = cc_q1a.qback;
 499                         if (p == &cc_q1a ||
 500                             p->time >= cc_time0 && p->length == (char) length)
 501                                 continue;
 502                         if (p->hback != 0)
 503                                 if ((*p->hback = p->hforw) != 0)
 504                                         p->hforw->hback = p->hback;
 505                         {
 506                                 register char *p1 = p->string;
 507                                 register char *p2 = cp - length;
 508                                 register n = length;
 509                                 do
 510                                         *p1++ = *p2++;
 511                                 while (--n);
 512                         }
 513                         p->length = length;
 514 #ifndef cc_weight
 515                         p->weight = cc_weight;
 516 #endif
 517                         p->time = time;
 518                         p->bcount = 1;
 519                         p->ccount = 0;
 520                         p->flag = 0;
 521                         if ((p->hforw = *h) != 0)
 522                                 p->hforw->hback = &p->hforw;
 523                         *h = p;
 524                         p->hback = h;
 525                         qinsert(p, &cc_q1a);
 526                         places[i] = -1;
 527                         p->places = i;
 528 #ifdef STATS
 529                         ntoken_stat++;
 530 #endif
 531                 } else if (p->time < cc_time0) {
 532 #ifndef cc_weight
 533                         if ((p->weight += p->time - time) < 0)
 534                                 p->weight = cc_weight;
 535                         else if ((p->weight += cc_weight) > limit)
 536                                 p->weight = limit;
 537 #endif
 538                         p->time = time;
 539                         p->bcount = 1;
 540                         p->ccount = 0;
 541                         if (p->code >= 0) {
 542                                 p->flag = 1;
 543                                 *pp++ = p;
 544                         } else
 545 #ifndef cc_weight
 546                         if (p->weight >= wthreshold) {
 547                                 p->flag = 1;
 548                                 *pp++ = p;
 549                                 qinsert(p, &cc_q1b);
 550                         } else
 551 #endif
 552                         {
 553                                 p->flag = 0;
 554                                 qinsert(p, &cc_q1a);
 555                         }
 556                         places[i] = -1;
 557                         p->places = i;
 558 #ifdef STATS
 559                         ntoken_stat++;
 560 #endif
 561                 } else if (p->time + length > time) {
 562                         /*
 563                          * overlapping token, don't count as two and
 564                          * don't update time, but do adjust weight to offset
 565                          * the difference
 566                          */
 567 #ifndef cc_weight
 568                         if (cc_weight != 0) {   /* XXX */
 569                                 p->weight += time - p->time;
 570                                 if (!p->flag && p->weight >= wthreshold) {
 571                                         p->flag = 1;
 572                                         *pp++ = p;
 573                                         qinsert(p, &cc_q1b);
 574                                 }
 575                         }
 576 #endif
 577                         places[i] = p->places;
 578                         p->places = i;
 579                 } else {
 580 #ifndef cc_weight
 581                         if ((p->weight += p->time - time) < 0)
 582                                 p->weight = cc_weight;
 583                         else if ((p->weight += cc_weight) > limit)
 584                                 p->weight = limit;
 585 #endif
 586                         p->time = time;
 587                         p->bcount++;
 588                         if (!p->flag &&
 589                             /* code must be < 0 if flag false here */
 590                             (p->bcount >= threshold
 591 #ifndef cc_weight
 592                              || p->weight >= wthreshold
 593 #endif
 594                              )) {
 595                                 p->flag = 1;
 596                                 *pp++ = p;
 597                                 qinsert(p, &cc_q1b);
 598                         }
 599                         places[i] = p->places;
 600                         p->places = i;
 601                 }
 602         }
 603         if ((i = pp - tokens) > 0) {
 604                 *pp = 0;
 605                 if (cc_reverse)
 606                         cc_sweep_reverse(tokens, places);
 607                 if (cc_sort && i > 1) {
 608                         int cc_token_compare();
 609                         qsort((char *) tokens, i, sizeof *tokens,
 610                               cc_token_compare);
 611                 }
 612                 if (cc_chop) {
 613                         if ((i = i * cc_chop / 100) == 0)
 614                                 i = 1;
 615                         tokens[i] = 0;
 616                 }
 617                 i++;
 618         }
 619         return i;
 620 }
 621
 622 cc_sweep_reverse(pp, places)
 623         register struct cc **pp;
 624         register short *places;
 625 {
 626         register struct cc *p;
 627         register short front, back, t;
 628
 629         while ((p = *pp++) != 0) {
 630                 back = -1;
 631                 t = p->places;
 632                 /* the list is never empty */
 633                 do {
 634                         front = places[t];
 635                         places[t] = back;
 636                         back = t;
 637                 } while ((t = front) >= 0);
 638                 p->places = back;
 639         }
 640 }
 641
 642 cc_compress_phase(output, bufsize, tokens, ntoken)
 643         struct cc **output;
 644         struct cc **tokens;
 645 {
 646         register i;
 647
 648         bzero((char *) output, bufsize * sizeof *output);
 649         for (i = 0; i < cc_npass0; i++)
 650                 cc_compress_phase1(output, tokens, ntoken, 0);
 651         for (i = 0; i < cc_npass1; i++)
 652                 cc_compress_phase1(output, tokens, ntoken, 1);
 653         cc_compress_cleanup(output, bufsize);
 654 }
 655
 656 cc_compress_phase1(output, tokens, ntoken, flag)
 657         register struct cc **output;
 658         struct cc **tokens;
 659 {
 660         register struct cc **pp;
 661 #ifdef STATS
 662         register int i = 0;
 663         int nt = 0, cc = 0, nc = 0;
 664 #endif
 665
 666 #ifdef STATS
 667         if (verbose >= 0)
 668                 time_begin();
 669         if (verbose > 0)
 670                 printf("Compress:");
 671 #endif
 672         pp = tokens;
 673         while (pp < tokens + ntoken) {
 674 #ifdef STATS
 675                 if (verbose > 0) {
 676                         ntoken_stat = 0;
 677                         ccount_stat = 0;
 678                         ncover_stat = 0;
 679                         if (i > 2) {
 680                                 printf("\n         ");
 681                                 i = 0;
 682                         }
 683                         i++;
 684                         printf(" (%d", (*pp)->length);
 685                         (void) fflush(stdout);
 686                 }
 687 #endif
 688                 pp += cc_compress(output, pp, flag);
 689 #ifdef STATS
 690                 if (verbose > 0) {
 691                         printf(" %dt %du %dc)", ntoken_stat, ccount_stat,
 692                                ncover_stat);
 693                         nt += ntoken_stat;
 694                         cc += ccount_stat;
 695                         nc += ncover_stat;
 696                 }
 697 #endif
 698         }
 699 #ifdef STATS
 700         if (verbose > 0)
 701                 printf("\n   total: (%dt %du %dc)\n", nt, cc, nc);
 702         if (verbose >= 0)
 703                 time_end();
 704 #endif
 705 }
 706
 707 cc_compress_cleanup(output, bufsize)
 708         register struct cc **output;
 709 {
 710         register struct cc **end;
 711
 712         /* the previous output phase may have been interrupted */
 713         qinsertq(&cc_q0b, &cc_q0a);
 714         for (end = output + bufsize; output < end;) {
 715                 register struct cc *p;
 716                 register length;
 717                 if ((p = *output) == 0) {
 718                         output++;
 719                         continue;
 720                 }
 721                 length = p->length;
 722                 if (!p->flag) {
 723                 } else if (p->code >= 0) {
 724                         qinsert(p, &cc_q0b);
 725                         p->flag = 0;
 726                 } else if (p->ccount == 0) {
 727                         *output = 0;
 728                 } else if (p->ccount >= thresh(length)
 729 #ifndef cc_weight
 730                            || wthreshp(p->weight, length)
 731 #endif
 732                            ) {
 733                         p->flag = 0;
 734                 } else {
 735                         p->ccount = 0;
 736                         *output = 0;
 737                 }
 738                 output += length;
 739         }
 740 }
 741
 742 cc_compress(output, tokens, flag)
 743         struct cc **output;
 744         struct cc **tokens;
 745         char flag;
 746 {
 747         struct cc **pp = tokens;
 748         register struct cc *p = *pp++;
 749         int length = p->length;
 750         int threshold = thresh(length);
 751 #ifndef cc_weight
 752         short wthreshold = wthresh(length);
 753 #endif
 754         short *places = cc_places[length];
 755         int *initial_scores = cc_initial_scores[length];
 756         int initial_score0 = put_token_score(length);
 757
 758         do {
 759                 int score;
 760                 register struct cc_undo *undop;
 761                 int ccount;
 762 #ifdef STATS
 763                 int ncover;
 764 #endif
 765                 int i;
 766
 767                 ccount = p->ccount;
 768                 if ((short) ccount >= p->bcount)
 769                         continue;
 770                 if (p->code >= 0 || ccount >= threshold)
 771                         score = 0;
 772 #ifndef cc_weight
 773                 else if (p->weight >= wthreshold)
 774                         /* allow one fewer match than normal */
 775                         /* XXX, should adjust for ccount */
 776                         score = - tt.tt_set_token_cost;
 777 #endif
 778                 else
 779                         score = initial_scores[ccount];
 780                 undop = cc_undo;
 781 #ifdef STATS
 782                 ncover = 0;
 783 #endif
 784                 for (i = p->places; i >= 0; i = places[i]) {
 785                         register struct cc **jp;
 786                         register struct cc *x;
 787                         register struct cc **ip = output + i;
 788                         register score0 = initial_score0;
 789                         struct cc **iip = ip + length;
 790                         struct cc_undo *undop1 = undop;
 791
 792                         if ((x = *(jp = ip)) != 0)
 793                                 goto z;
 794                         while (--jp >= output)
 795                                 if ((x = *jp) != 0) {
 796                                         if (jp + x->length > ip)
 797                                                 goto z;
 798                                         break;
 799                                 }
 800                         jp = ip + 1;
 801                         while (jp < iip) {
 802                                 if ((x = *jp) == 0) {
 803                                         jp++;
 804                                         continue;
 805                                 }
 806                         z:
 807                                 if (x == p)
 808                                         goto undo;
 809 #ifdef STATS
 810                                 ncover++;
 811 #endif
 812                                 undop->pos = jp;
 813                                 undop->val = x;
 814                                 undop++;
 815                                 *jp = 0;
 816                                 x->ccount--;
 817                                 score_adjust(score0, x);
 818                                 if (score0 < 0 && flag)
 819                                         goto undo;
 820                                 jp += x->length;
 821                         }
 822                         undop->pos = ip;
 823                         undop->val = 0;
 824                         undop++;
 825                         *ip = p;
 826                         ccount++;
 827                         score += score0;
 828                         continue;
 829                 undo:
 830                         while (--undop >= undop1)
 831                                 if (*undop->pos = x = undop->val)
 832                                         x->ccount++;
 833                         undop++;
 834                 }
 835                 if (score > 0) {
 836 #ifdef STATS
 837                         ccount_stat += ccount - p->ccount;
 838                         ntoken_stat++;
 839                         ncover_stat += ncover;
 840 #endif
 841                         p->ccount = ccount;
 842                 } else {
 843                         register struct cc_undo *u = cc_undo;
 844                         while (--undop >= u) {
 845                                 register struct cc *x;
 846                                 if (*undop->pos = x = undop->val)
 847                                         x->ccount++;
 848                         }
 849                 }
 850         } while ((p = *pp++) != 0);
 851         return pp - tokens;
 852 }
 853
 854 cc_output_phase(buffer, output, bufsize)
 855         register char *buffer;
 856         register struct cc **output;
 857         register bufsize;
 858 {
 859         register i;
 860         register struct cc *p, *p1;
 861
 862         for (i = 0; i < bufsize;) {
 863                 if ((p = output[i]) == 0) {
 864                         ttputc(buffer[i]);
 865                         i++;
 866                 } else if (p->code >= 0) {
 867                         if (--p->ccount == 0)
 868                                 qinsert(p, &cc_q0a);
 869                         (*tt.tt_put_token)(p->code, p->string, p->length);
 870                         wwntokuse++;
 871                         wwntoksave += put_token_score(p->length);
 872                         i += p->length;
 873                 } else if ((p1 = cc_q0a.qback) != &cc_q0a) {
 874                         p->code = p1->code;
 875                         p1->code = -1;
 876                         qinsert(p1, &cc_q1a);
 877                         if (--p->ccount == 0)
 878                                 qinsert(p, &cc_q0a);
 879                         else
 880                                 qinsert(p, &cc_q0b);
 881                         (*tt.tt_set_token)(p->code, p->string, p->length);
 882                         wwntokdef++;
 883                         wwntoksave -= tt.tt_set_token_cost;
 884                         i += p->length;
 885                 } else {
 886                         p->ccount--;
 887                         ttwrite(p->string, p->length);
 888                         wwntokbad++;
 889                         i += p->length;
 890                 }
 891         }
 892         wwntokc += bufsize;
 893 }
 894
 895 cc_token_compare(p1, p2)
 896         struct cc **p1, **p2;
 897 {
 898         return (*p2)->bcount - (*p1)->bcount;
 899 }