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