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