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