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