home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume4 / uemacs / part1 / display.c < prev    next >
Encoding:
C/C++ Source or Header  |  1986-11-30  |  19.2 KB  |  764 lines
  1. /*
  2.  * Name:    MicroEMACS
  3.  *        Gosling style redisplay.
  4.  * Version:    30
  5.  * Last edit:    10-Feb-86
  6.  * By:        rex::conroy
  7.  *        decvax!decwrl!dec-rhea!dec-rex!conroy
  8.  *
  9.  * The functions in this file handle redisplay. The
  10.  * redisplay system knows almost nothing about the editing
  11.  * process; the editing functions do, however, set some
  12.  * hints to eliminate a lot of the grinding. There is more
  13.  * that can be done; the "vtputc" interface is a real
  14.  * pig. Two conditional compilation flags; the GOSLING
  15.  * flag enables dynamic programming redisplay, using the
  16.  * algorithm published by Jim Gosling in SIGOA. The MEMMAP
  17.  * changes things around for memory mapped video. With
  18.  * both off, the terminal is a VT52.
  19.  */
  20. #include    "def.h"
  21.  
  22. /*
  23.  * You can change these back to the types
  24.  * implied by the name if you get tight for space. If you
  25.  * make both of them "int" you get better code on the VAX.
  26.  * They do nothing if this is not Gosling redisplay, except
  27.  * for change the size of a structure that isn't used.
  28.  * A bit of a cheat.
  29.  */
  30. #define    XCHAR    int
  31. #define    XSHORT    int
  32.  
  33. /*
  34.  * A video structure always holds
  35.  * an array of characters whose length is equal to
  36.  * the longest line possible. Only some of this is
  37.  * used if "ncol" isn't the same as "NCOL".
  38.  */
  39. typedef    struct    {
  40.     short    v_hash;            /* Hash code, for compares.    */
  41.     short    v_flag;            /* Flag word.            */
  42.     short    v_color;        /* Color of the line.        */
  43.     XSHORT    v_cost;            /* Cost of display.        */
  44.     char    v_text[NCOL];        /* The actual characters.    */
  45. }    VIDEO;
  46.  
  47. #define    VFCHG    0x0001            /* Changed.            */
  48. #define    VFHBAD    0x0002            /* Hash and cost are bad.    */
  49.  
  50. /*
  51.  * SCORE structures hold the optimal
  52.  * trace trajectory, and the cost of redisplay, when
  53.  * the dynamic programming redisplay code is used.
  54.  * If no fancy redisplay, this isn't used. The trace index
  55.  * fields can be "char", and the score a "short", but
  56.  * this makes the code worse on the VAX.
  57.  */
  58. typedef    struct    {
  59.     XCHAR    s_itrace;        /* "i" index for track back.    */
  60.     XCHAR    s_jtrace;        /* "j" index for trace back.    */
  61.     XSHORT    s_cost;            /* Display cost.        */
  62. }    SCORE;
  63.  
  64. int    sgarbf    = TRUE;            /* TRUE if screen is garbage.    */
  65. int    vtrow    = 0;            /* Virtual cursor row.        */
  66. int    vtcol    = 0;            /* Virtual cursor column.    */
  67. int    tthue    = CNONE;        /* Current color.        */
  68. int    ttrow    = HUGE;            /* Physical cursor row.        */
  69. int    ttcol    = HUGE;            /* Physical cursor column.    */
  70. int    tttop    = HUGE;            /* Top of scroll region.    */
  71. int    ttbot    = HUGE;            /* Bottom of scroll region.    */
  72.  
  73. VIDEO    *vscreen[NROW-1];        /* Edge vector, virtual.    */
  74. VIDEO    *pscreen[NROW-1];        /* Edge vector, physical.    */
  75. VIDEO    video[2*(NROW-1)];        /* Actual screen data.        */
  76. VIDEO    blanks;                /* Blank line image.        */
  77.  
  78. #if    GOSLING
  79. /*
  80.  * This matrix is written as an array because
  81.  * we do funny things in the "setscores" routine, which
  82.  * is very compute intensive, to make the subscripts go away.
  83.  * It would be "SCORE    score[NROW][NROW]" in old speak.
  84.  * Look at "setscores" to understand what is up.
  85.  */
  86. SCORE    score[NROW*NROW];
  87. #endif
  88.  
  89. /*
  90.  * Initialize the data structures used
  91.  * by the display code. The edge vectors used
  92.  * to access the screens are set up. The operating
  93.  * system's terminal I/O channel is set up. Fill the
  94.  * "blanks" array with ASCII blanks. The rest is done
  95.  * at compile time. The original window is marked
  96.  * as needing full update, and the physical screen
  97.  * is marked as garbage, so all the right stuff happens
  98.  * on the first call to redisplay.
  99.  */
  100. vtinit()
  101. {
  102.     register VIDEO    *vp;
  103.     register int    i;
  104.  
  105.     ttopen();
  106.     ttinit();
  107.     vp = &video[0];
  108.     for (i=0; i<NROW-1; ++i) {
  109.         vscreen[i] = vp;
  110.         ++vp;
  111.         pscreen[i] = vp;
  112.         ++vp;
  113.     }
  114.     blanks.v_color = CTEXT;
  115.     for (i=0; i<NCOL; ++i)
  116.         blanks.v_text[i] = ' ';
  117. }
  118.  
  119. /*
  120.  * Tidy up the virtual display system
  121.  * in anticipation of a return back to the host
  122.  * operating system. Right now all we do is position
  123.  * the cursor to the last line, erase the line, and
  124.  * close the terminal channel.
  125.  */
  126. vttidy()
  127. {
  128.     ttcolor(CTEXT);
  129.     ttnowindow();                /* No scroll window.    */
  130.     ttmove(nrow-1, 0);            /* Echo line.        */
  131.     tteeol();
  132.     tttidy();
  133.     ttflush();
  134.     ttclose();
  135. }
  136.  
  137. /*
  138.  * Move the virtual cursor to an origin
  139.  * 0 spot on the virtual display screen. I could
  140.  * store the column as a character pointer to the spot
  141.  * on the line, which would make "vtputc" a little bit
  142.  * more efficient. No checking for errors.
  143.  */
  144. vtmove(row, col)
  145. {
  146.     vtrow = row;
  147.     vtcol = col;
  148. }
  149.  
  150. /*
  151.  * Write a character to the virtual display,
  152.  * dealing with long lines and the display of unprintable
  153.  * things like control characters. Also expand tabs every 8
  154.  * columns. This code only puts printing characters into 
  155.  * the virtual display image. Special care must be taken when
  156.  * expanding tabs. On a screen whose width is not a multiple
  157.  * of 8, it is possible for the virtual cursor to hit the
  158.  * right margin before the next tab stop is reached. This
  159.  * makes the tab code loop if you are not careful.
  160.  * Three guesses how we found this.
  161.  */
  162. vtputc(c)
  163. register int    c;
  164. {
  165.     register VIDEO    *vp;
  166.  
  167.     vp = vscreen[vtrow];
  168.     if (vtcol >= ncol)
  169.         vp->v_text[ncol-1] = '$';
  170.     else if (c == '\t') {
  171.         do {
  172.             vtputc(' ');
  173.         } while (vtcol<ncol && (vtcol&0x07)!=0);
  174.     } else if (ISCTRL(c) != FALSE) {
  175.         vtputc('^');
  176.         vtputc(c ^ 0x40);
  177.     } else
  178.         vp->v_text[vtcol++] = c;        
  179. }
  180.  
  181. /*
  182.  * Erase from the end of the
  183.  * software cursor to the end of the
  184.  * line on which the software cursor is
  185.  * located. The display routines will decide
  186.  * if a hardware erase to end of line command
  187.  * should be used to display this.
  188.  */
  189. vteeol()
  190. {
  191.     register VIDEO    *vp;
  192.  
  193.     vp = vscreen[vtrow];
  194.     while (vtcol < ncol)
  195.         vp->v_text[vtcol++] = ' ';
  196. }
  197.  
  198. /*
  199.  * Make sure that the display is
  200.  * right. This is a three part process. First,
  201.  * scan through all of the windows looking for dirty
  202.  * ones. Check the framing, and refresh the screen.
  203.  * Second, make sure that "currow" and "curcol" are
  204.  * correct for the current window. Third, make the
  205.  * virtual and physical screens the same.
  206.  */
  207. update()
  208. {
  209.     register LINE    *lp;
  210.     register WINDOW    *wp;
  211.     register VIDEO    *vp1;
  212.     register VIDEO    *vp2;
  213.     register int    i;
  214.     register int    j;
  215.     register int    c;
  216.     register int    hflag;
  217.     register int    currow;
  218.     register int    curcol;
  219.     register int    offs;
  220.     register int    size;
  221.  
  222.     if (curmsgf!=FALSE || newmsgf!=FALSE) {
  223.         wp = wheadp;
  224.         while (wp != NULL) {
  225.             wp->w_flag |= WFMODE;    /* Must do mode lines.    */
  226.             wp = wp->w_wndp;
  227.         }
  228.     }
  229.     curmsgf = newmsgf;            /* Sync. up right now.    */
  230.     hflag = FALSE;                /* Not hard.        */
  231.     wp = wheadp;
  232.     while (wp != NULL) {
  233.         if (wp->w_flag != 0) {        /* Need update.        */
  234.             if ((wp->w_flag&WFFORCE) == 0) {
  235.                 lp = wp->w_linep;
  236.                 for (i=0; i<wp->w_ntrows; ++i) {
  237.                     if (lp == wp->w_dotp)
  238.                         goto out;
  239.                     if (lp == wp->w_bufp->b_linep)
  240.                         break;
  241.                     lp = lforw(lp);
  242.                 }
  243.             }
  244.             i = wp->w_force;    /* Reframe this one.    */
  245.             if (i > 0) {
  246.                 --i;
  247.                 if (i >= wp->w_ntrows)
  248.                     i = wp->w_ntrows-1;
  249.             } else if (i < 0) {
  250.                 i += wp->w_ntrows;
  251.                 if (i < 0)
  252.                     i = 0;
  253.             } else
  254.                 i = wp->w_ntrows/2;
  255.             lp = wp->w_dotp;
  256.             while (i!=0 && lback(lp)!=wp->w_bufp->b_linep) {
  257.                 --i;
  258.                 lp = lback(lp);
  259.             }
  260.             wp->w_linep = lp;
  261.             wp->w_flag |= WFHARD;    /* Force full.        */
  262.         out:
  263.             lp = wp->w_linep;    /* Try reduced update.    */
  264.             i  = wp->w_toprow;
  265.             if ((wp->w_flag&~WFMODE) == WFEDIT) {
  266.                 while (lp != wp->w_dotp) {
  267.                     ++i;
  268.                     lp = lforw(lp);
  269.                 }
  270.                 vscreen[i]->v_color = CTEXT;
  271.                 vscreen[i]->v_flag |= (VFCHG|VFHBAD);
  272.                 vtmove(i, 0);
  273.                 for (j=0; j<llength(lp); ++j)
  274.                     vtputc(lgetc(lp, j));
  275.                 vteeol();
  276.             } else if ((wp->w_flag&(WFEDIT|WFHARD)) != 0) {
  277.                 hflag = TRUE;
  278.                 while (i < wp->w_toprow+wp->w_ntrows) {
  279.                     vscreen[i]->v_color = CTEXT;
  280.                     vscreen[i]->v_flag |= (VFCHG|VFHBAD);
  281.                     vtmove(i, 0);
  282.                     if (lp != wp->w_bufp->b_linep) {
  283.                         for (j=0; j<llength(lp); ++j)
  284.                             vtputc(lgetc(lp, j));
  285.                         lp = lforw(lp);
  286.                     }
  287.                     vteeol();
  288.                     ++i;
  289.                 }
  290.             }
  291.             if ((wp->w_flag&WFMODE) != 0)
  292.                 modeline(wp);
  293.             wp->w_flag  = 0;
  294.             wp->w_force = 0;
  295.         }        
  296.         wp = wp->w_wndp;
  297.     }
  298.     lp = curwp->w_linep;            /* Cursor location.    */
  299.     currow = curwp->w_toprow;
  300.     while (lp != curwp->w_dotp) {
  301.         ++currow;
  302.         lp = lforw(lp);
  303.     }
  304.     curcol = 0;
  305.     i = 0;
  306.     while (i < curwp->w_doto) {
  307.         c = lgetc(lp, i++);
  308.         if (c == '\t')
  309.             curcol |= 0x07;
  310.         else if (ISCTRL(c) != FALSE)
  311.             ++curcol;
  312.         ++curcol;
  313.     }
  314.     if (curcol >= ncol)            /* Long line.        */
  315.         curcol = ncol-1;
  316.     if (sgarbf != FALSE) {            /* Screen is garbage.    */
  317.         sgarbf = FALSE;            /* Erase-page clears    */
  318.         epresf = FALSE;            /* the message area.    */
  319.         tttop  = HUGE;            /* Forget where you set    */
  320.         ttbot  = HUGE;            /* scroll region.    */
  321.         tthue  = CNONE;            /* Color unknown.    */
  322.         ttmove(0, 0);
  323.         tteeop();
  324.         for (i=0; i<nrow-1; ++i) {
  325.             uline(i, vscreen[i], &blanks);
  326.             ucopy(vscreen[i], pscreen[i]);
  327.         }
  328.         ttmove(currow, curcol);
  329.         ttflush();
  330.         return;
  331.     }
  332. #if    GOSLING
  333.     if (hflag != FALSE) {            /* Hard update?        */
  334.         for (i=0; i<nrow-1; ++i) {    /* Compute hash data.    */
  335.             hash(vscreen[i]);
  336.             hash(pscreen[i]);
  337.         }
  338.         offs = 0;            /* Get top match.    */
  339.         while (offs != nrow-1) {
  340.             vp1 = vscreen[offs];
  341.             vp2 = pscreen[offs];
  342.             if (vp1->v_color != vp2->v_color
  343.             ||  vp1->v_hash  != vp2->v_hash)
  344.                 break;
  345.             uline(offs, vp1, vp2);
  346.             ucopy(vp1, vp2);
  347.             ++offs;
  348.         }
  349.         if (offs == nrow-1) {        /* Might get it all.    */
  350.             ttmove(currow, curcol);
  351.             ttflush();
  352.             return;
  353.         }
  354.         size = nrow-1;            /* Get bottom match.    */
  355.         while (size != offs) {
  356.             vp1 = vscreen[size-1];
  357.             vp2 = pscreen[size-1];
  358.             if (vp1->v_color != vp2->v_color
  359.             ||  vp1->v_hash  != vp2->v_hash)
  360.                 break;
  361.             uline(size-1, vp1, vp2);
  362.             ucopy(vp1, vp2);
  363.             --size;
  364.         }
  365.         if ((size -= offs) == 0)    /* Get screen size.    */
  366.             abort();
  367.         setscores(offs, size);        /* Do hard update.    */
  368.         traceback(offs, size, size, size);
  369.         for (i=0; i<size; ++i)
  370.             ucopy(vscreen[offs+i], pscreen[offs+i]);
  371.         ttmove(currow, curcol);
  372.         ttflush();
  373.         return;            
  374.     }
  375. #endif
  376.     for (i=0; i<nrow-1; ++i) {        /* Easy update.        */
  377.         vp1 = vscreen[i];
  378.         vp2 = pscreen[i];
  379.         if ((vp1->v_flag&VFCHG) != 0) {
  380.             uline(i, vp1, vp2);
  381.             ucopy(vp1, vp2);
  382.         }
  383.     }
  384.     ttmove(currow, curcol);
  385.     ttflush();
  386. }
  387.  
  388. /*
  389.  * Update a saved copy of a line,
  390.  * kept in a VIDEO structure. The "vvp" is
  391.  * the one in the "vscreen". The "pvp" is the one
  392.  * in the "pscreen". This is called to make the
  393.  * virtual and physical screens the same when
  394.  * display has done an update.
  395.  */
  396. ucopy(vvp, pvp)
  397. register VIDEO    *vvp;
  398. register VIDEO    *pvp;
  399. {
  400.     register int    i;
  401.  
  402.     vvp->v_flag &= ~VFCHG;            /* Changes done.    */
  403.     pvp->v_flag  = vvp->v_flag;        /* Update model.    */
  404.     pvp->v_hash  = vvp->v_hash;
  405.     pvp->v_cost  = vvp->v_cost;
  406.     pvp->v_color = vvp->v_color;
  407.     for (i=0; i<ncol; ++i)
  408.         pvp->v_text[i] = vvp->v_text[i];
  409. }
  410.  
  411. /*
  412.  * Update a single line. This routine only
  413.  * uses basic functionality (no insert and delete character,
  414.  * but erase to end of line). The "vvp" points at the VIDEO
  415.  * structure for the line on the virtual screen, and the "pvp"
  416.  * is the same for the physical screen. Avoid erase to end of
  417.  * line when updating CMODE color lines, because of the way that
  418.  * reverse video works on most terminals.
  419.  */
  420. uline(row, vvp, pvp)
  421. VIDEO    *vvp;
  422. VIDEO    *pvp;
  423. {
  424. #if    MEMMAP
  425.     putline(row+1, 1, &vvp->v_text[0]);
  426. #else
  427.     register char    *cp1;
  428.     register char    *cp2;
  429.     register char    *cp3;
  430.     register char    *cp4;
  431.     register char    *cp5;
  432.     register int    nbflag;
  433.  
  434.     if (vvp->v_color != pvp->v_color) {    /* Wrong color, do a    */
  435.         ttmove(row, 0);            /* full redraw.        */
  436.         ttcolor(vvp->v_color);
  437.         cp1 = &vvp->v_text[0];
  438.         cp2 = &vvp->v_text[ncol];
  439.         while (cp1 != cp2) {
  440.             ttputc(*cp1++);
  441.             ++ttcol;
  442.         }
  443.         return;
  444.     }
  445.     cp1 = &vvp->v_text[0];            /* Compute left match.    */
  446.     cp2 = &pvp->v_text[0];
  447.     while (cp1!=&vvp->v_text[ncol] && cp1[0]==cp2[0]) {
  448.         ++cp1;
  449.         ++cp2;
  450.     }
  451.     if (cp1 == &vvp->v_text[ncol])        /* All equal.        */
  452.         return;
  453.     nbflag = FALSE;
  454.     cp3 = &vvp->v_text[ncol];        /* Compute right match.    */
  455.     cp4 = &pvp->v_text[ncol];
  456.     while (cp3[-1] == cp4[-1]) {
  457.         --cp3;
  458.         --cp4;
  459.         if (cp3[0] != ' ')        /* Note non-blanks in    */
  460.             nbflag = TRUE;        /* the right match.    */
  461.     }
  462.     cp5 = cp3;                /* Is erase good?    */
  463.     if (nbflag==FALSE && vvp->v_color==CTEXT) {
  464.         while (cp5!=cp1 && cp5[-1]==' ')
  465.             --cp5;
  466.         /* Alcyon hack */
  467.         if ((int)(cp3-cp5) <= tceeol)
  468.             cp5 = cp3;
  469.     }
  470.     /* Alcyon hack */
  471.     ttmove(row, (int)(cp1-&vvp->v_text[0]));
  472.     ttcolor(vvp->v_color);
  473.     while (cp1 != cp5) {
  474.         ttputc(*cp1++);
  475.         ++ttcol;
  476.     }
  477.     if (cp5 != cp3)                /* Do erase.        */
  478.         tteeol();
  479. #endif
  480. }
  481.  
  482. /*
  483.  * Redisplay the mode line for
  484.  * the window pointed to by the "wp".
  485.  * This is the only routine that has any idea
  486.  * of how the modeline is formatted. You can
  487.  * change the modeline format by hacking at
  488.  * this routine. Called by "update" any time
  489.  * there is a dirty window.
  490.  */
  491. modeline(wp)
  492. register WINDOW    *wp;
  493. {
  494.     register char    *cp;
  495.     register int    c;
  496.     register int    n;
  497.     register BUFFER    *bp;
  498.  
  499.     n = wp->w_toprow+wp->w_ntrows;        /* Location.        */
  500.     vscreen[n]->v_color = CMODE;        /* Mode line color.    */
  501.     vscreen[n]->v_flag |= (VFCHG|VFHBAD);    /* Recompute, display.    */
  502.     vtmove(n, 0);                /* Seek to right line.    */
  503.     bp = wp->w_bufp;
  504.     if ((bp->b_flag&BFCHG) != 0)        /* "*" if changed.    */
  505.         vtputc('*');
  506.     else
  507.         vtputc(' ');
  508.     n  = 1;
  509.     cp = "MicroEMACS";            /* Buffer name.        */
  510.     while ((c = *cp++) != 0) {
  511.         vtputc(c);
  512.         ++n;
  513.     }
  514.     if (bp->b_bname[0] != 0) {
  515.         vtputc(' ');
  516.         ++n;
  517.         cp = &bp->b_bname[0];
  518.         while ((c = *cp++) != 0) {
  519.             vtputc(c);
  520.             ++n;
  521.         }
  522.     }
  523.     if (bp->b_fname[0] != 0) {        /* File name.        */
  524.         vtputc(' ');
  525.         ++n;
  526.         cp = "File:";
  527.         while ((c = *cp++) != 0) {
  528.             vtputc(c);
  529.             ++n;
  530.         }
  531.         cp = &bp->b_fname[0];
  532.         while ((c = *cp++) != 0) {
  533.             vtputc(c);
  534.             ++n;
  535.         }
  536.     }
  537.     if (curmsgf != FALSE            /* Message alert.    */
  538.     && wp->w_wndp == NULL) {
  539.         while (n < ncol-5-1) {
  540.             vtputc(' ');
  541.             ++n;
  542.         }
  543.         cp = "[Msg]";            /* Sizeof("[Msg]") = 5.    */
  544.         while ((c = *cp++) != 0) {
  545.             vtputc(c);
  546.             ++n;
  547.         }
  548.     }
  549.     while (n < ncol) {            /* Pad out.        */
  550.         vtputc(' ');
  551.         ++n;
  552.     }
  553. }
  554.  
  555. #if    GOSLING
  556. /*
  557.  * Compute the hash code for
  558.  * the line pointed to by the "vp". Recompute
  559.  * it if necessary. Also set the approximate redisplay
  560.  * cost. The validity of the hash code is marked by
  561.  * a flag bit. The cost understand the advantages
  562.  * of erase to end of line. Tuned for the VAX
  563.  * by Bob McNamara; better than it used to be on
  564.  * just about any machine.
  565.  */
  566. hash(vp)
  567. register VIDEO    *vp;
  568. {
  569.     register int    i;
  570.     register int    n;
  571.     register char    *s;
  572.  
  573.     if ((vp->v_flag&VFHBAD) != 0) {        /* Hash bad.        */
  574.         s = &vp->v_text[ncol-1];
  575.         for (i=ncol; i!=0; --i, --s)
  576.             if (*s != ' ')
  577.                 break;
  578.         n = ncol-i;            /* Erase cheaper?    */
  579.         if (n > tceeol)
  580.             n = tceeol;
  581.         vp->v_cost = i+n;        /* Bytes + blanks.    */
  582.         for (n=0; i!=0; --i, --s)
  583.             n = (n<<5) + n + *s;
  584.         vp->v_hash = n;            /* Hash code.        */
  585.         vp->v_flag &= ~VFHBAD;        /* Flag as all done.    */
  586.     }
  587. }
  588.  
  589. /*
  590.  * Compute the Insert-Delete
  591.  * cost matrix. The dynamic programming algorithm
  592.  * described by James Gosling is used. This code assumes
  593.  * that the line above the echo line is the last line involved
  594.  * in the scroll region. This is easy to arrange on the VT100
  595.  * because of the scrolling region. The "offs" is the origin 0
  596.  * offset of the first row in the virtual/physical screen that
  597.  * is being updated; the "size" is the length of the chunk of
  598.  * screen being updated. For a full screen update, use offs=0
  599.  * and size=nrow-1.
  600.  *
  601.  * Older versions of this code implemented the score matrix by
  602.  * a two dimensional array of SCORE nodes. This put all kinds of
  603.  * multiply instructions in the code! This version is written to
  604.  * use a linear array and pointers, and contains no multiplication
  605.  * at all. The code has been carefully looked at on the VAX, with
  606.  * only marginal checking on other machines for efficiency. In
  607.  * fact, this has been tuned twice! Bob McNamara tuned it even
  608.  * more for the VAX, which is a big issue for him because of
  609.  * the 66 line X displays.
  610.  *
  611.  * On some machines, replacing the "for (i=1; i<=size; ++i)" with
  612.  * i = 1; do { } while (++i <=size)" will make the code quite a
  613.  * bit better; but it looks ugly.
  614.  */
  615. setscores(offs, size)
  616. {
  617.     register SCORE    *sp;
  618.     register int    tempcost;
  619.     register int    bestcost;
  620.     register int    j;
  621.     register int    i;
  622.     register VIDEO    **vp;
  623.     register VIDEO    **pp;
  624.     register SCORE    *sp1;
  625.     register VIDEO    **vbase;
  626.     register VIDEO    **pbase;
  627.  
  628.     vbase = &vscreen[offs-1];        /* By hand CSE's.    */
  629.     pbase = &pscreen[offs-1];
  630.     score[0].s_itrace = 0;            /* [0, 0]        */
  631.     score[0].s_jtrace = 0;
  632.     score[0].s_cost   = 0;
  633.     sp = &score[1];                /* Row 0, inserts.    */
  634.     tempcost = 0;
  635.     vp = &vbase[1];
  636.     for (j=1; j<=size; ++j) {
  637.         sp->s_itrace = 0;
  638.         sp->s_jtrace = j-1;
  639.         tempcost += tcinsl;
  640.         tempcost += (*vp)->v_cost;
  641.         sp->s_cost = tempcost;
  642.         ++vp;
  643.         ++sp;
  644.     }
  645.     sp = &score[NROW];            /* Column 0, deletes.    */
  646.     tempcost = 0;
  647.     for (i=1; i<=size; ++i) {
  648.         sp->s_itrace = i-1;
  649.         sp->s_jtrace = 0;
  650.         tempcost  += tcdell;
  651.         sp->s_cost = tempcost;
  652.         sp += NROW;
  653.     }
  654.     sp1 = &score[NROW+1];            /* [1, 1].        */
  655.     pp = &pbase[1];
  656.     for (i=1; i<=size; ++i) {
  657.         sp = sp1;
  658.         vp = &vbase[1];
  659.         for (j=1; j<=size; ++j) {
  660.             sp->s_itrace = i-1;
  661.             sp->s_jtrace = j;
  662.             bestcost = (sp-NROW)->s_cost;
  663.             if (j != size)        /* Cd(A[i])=0 @ Dis.    */
  664.                 bestcost += tcdell;
  665.             tempcost = (sp-1)->s_cost;
  666.             tempcost += (*vp)->v_cost;
  667.             if (i != size)        /* Ci(B[j])=0 @ Dsj.    */
  668.                 tempcost += tcinsl;
  669.             if (tempcost < bestcost) {
  670.                 sp->s_itrace = i;
  671.                 sp->s_jtrace = j-1;
  672.                 bestcost = tempcost;
  673.             }
  674.             tempcost = (sp-NROW-1)->s_cost;
  675.             if ((*pp)->v_color != (*vp)->v_color
  676.             ||  (*pp)->v_hash  != (*vp)->v_hash)
  677.                 tempcost += (*vp)->v_cost;
  678.             if (tempcost < bestcost) {
  679.                 sp->s_itrace = i-1;
  680.                 sp->s_jtrace = j-1;
  681.                 bestcost = tempcost;
  682.             }
  683.             sp->s_cost = bestcost;
  684.             ++sp;            /* Next column.        */
  685.             ++vp;
  686.         }
  687.         ++pp;
  688.         sp1 += NROW;            /* Next row.        */
  689.     }
  690. }
  691.  
  692. /*
  693.  * Trace back through the dynamic programming cost
  694.  * matrix, and update the screen using an optimal sequence
  695.  * of redraws, insert lines, and delete lines. The "offs" is
  696.  * the origin 0 offset of the chunk of the screen we are about to
  697.  * update. The "i" and "j" are always started in the lower right
  698.  * corner of the matrix, and imply the size of the screen.
  699.  * A full screen traceback is called with offs=0 and i=j=nrow-1.
  700.  * There is some do-it-yourself double subscripting here,
  701.  * which is acceptable because this routine is much less compute
  702.  * intensive then the code that builds the score matrix!
  703.  */
  704. traceback(offs, size, i, j)
  705. {
  706.     register int    itrace;
  707.     register int    jtrace;
  708.     register int    k;
  709.     register int    ninsl;
  710.     register int    ndraw;
  711.     register int    ndell;
  712.  
  713.     if (i==0 && j==0)            /* End of update.    */
  714.         return;
  715.     itrace = score[(NROW*i) + j].s_itrace;
  716.     jtrace = score[(NROW*i) + j].s_jtrace;
  717.     if (itrace == i) {            /* [i, j-1]        */
  718.         ninsl = 0;            /* Collect inserts.    */
  719.         if (i != size)
  720.             ninsl = 1;
  721.         ndraw = 1;
  722.         while (itrace!=0 || jtrace!=0) {
  723.             if (score[(NROW*itrace) + jtrace].s_itrace != itrace)
  724.                 break;
  725.             jtrace = score[(NROW*itrace) + jtrace].s_jtrace;
  726.             if (i != size)
  727.                 ++ninsl;
  728.             ++ndraw;
  729.         }
  730.         traceback(offs, size, itrace, jtrace);
  731.         if (ninsl != 0) {
  732.             ttcolor(CTEXT);
  733.             ttinsl(offs+j-ninsl, offs+size-1, ninsl);
  734.         }
  735.         do {                /* B[j], A[j] blank.    */
  736.             k = offs+j-ndraw;
  737.             uline(k, vscreen[k], &blanks);
  738.         } while (--ndraw);
  739.         return;
  740.     }
  741.     if (jtrace == j) {            /* [i-1, j]        */
  742.         ndell = 0;            /* Collect deletes.    */
  743.         if (j != size)
  744.             ndell = 1;
  745.         while (itrace!=0 || jtrace!=0) {
  746.             if (score[(NROW*itrace) + jtrace].s_jtrace != jtrace)
  747.                 break;
  748.             itrace = score[(NROW*itrace) + jtrace].s_itrace;
  749.             if (j != size)
  750.                 ++ndell;
  751.         }
  752.         if (ndell != 0) {
  753.             ttcolor(CTEXT);
  754.             ttdell(offs+i-ndell, offs+size-1, ndell);
  755.         }
  756.         traceback(offs, size, itrace, jtrace);
  757.         return;
  758.     }
  759.     traceback(offs, size, itrace, jtrace);
  760.     k = offs+j-1;
  761.     uline(k, vscreen[k], pscreen[offs+i-1]);
  762. }
  763. #endif
  764.