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