static void longestCommonSequence(
  DContext *p,               /* Two files being compared */
  int iS1, int iE1,          /* Range of lines in p->aFrom[] */
  int iS2, int iE2,          /* Range of lines in p->aTo[] */
  int *piSX, int *piEX,      /* Write p->aFrom[] common segment here */
  int *piSY, int *piEY       /* Write p->aTo[] common segment here */
){

  int i, j, k;               /* Loop counters */
  int n;                     /* Loop limit */
  DLine *pA, *pB;            /* Pointers to lines */
  int iSX, iSY, iEX, iEY;    /* Current match */

  int skew = 0;              /* How lopsided is the match */
  int dist = 0;              /* Distance of match from center */
  int mid;                   /* Center of the span */
  int iSXb, iSYb, iEXb, iEYb;   /* Best match so far */
  int iSXp, iSYp, iEXp, iEYp;   /* Previous match */
  sqlite3_int64 bestScore;      /* Best score so far */
  sqlite3_int64 score;          /* Score for current candidate LCS */
  int span;                     /* combined width of the input sequences */

  span = (iE1 - iS1) + (iE2 - iS2);
  bestScore = -10000;
  score = 0;
  iSXb = iSXp = iS1;
  iEXb = iEXp = iS1;
  iSYb = iSYp = iS2;
  iEYb = iEYp = iS2;
  mid = (iE1 + iS1)/2;
  for(i=iS1; i<iE1; i++){
    int limit = 0;

    for(k=0; k<n && same_dline(pA,pB); k++, pA++, pB++){}
    iEX += k;
    iEY += k;
    skew = (iSX-iS1) - (iSY-iS2);
    if( skew<0 ) skew = -skew;
    dist = (iSX+iEX)/2 - mid;
    if( dist<0 ) dist = -dist;
    score = (iEX - iSX)*(sqlite3_int64)span - (skew + dist);
    if( score>bestScore ){
      bestScore = score;
      iSXb = iSX;
      iSYb = iSY;
      iEXb = iEX;
      iEYb = iEY;
    }else if( iEX>iEXp ){

    optimalLCS(p, iS1, iE1, iS2, iE2, piSX, piEX, piSY, piEY);
  }else{
    *piSX = iSXb;
    *piSY = iSYb;
    *piEX = iEXb;
    *piEY = iEYb;
  }


}

/*
** Expand the size of aEdit[] array to hold at least nEdit elements.
*/
static void expandEdit(DContext *p, int nEdit){
  p->aEdit = fossil_realloc(p->aEdit, nEdit*sizeof(int));

typedef struct Annotator Annotator;
struct Annotator {
  DContext c;       /* The diff-engine context */
  struct AnnLine {  /* Lines of the original files... */
    const char *z;       /* The text of the line */
    short int n;         /* Number of bytes (omitting trailing space and \n) */
    short int iLevel;    /* Level at which tag was set */
    int iVers;           /* aVers[] entry responsible for this line */
  } *aOrig;
  int nOrig;        /* Number of elements in aOrig[] */
  int nNoSrc;       /* Number of entries where aOrig[].zSrc==NULL */
  int iLevel;       /* Current level */
  int nVers;        /* Number of versions analyzed */
  struct AnnVers {
    const char *zFUuid;   /* File being analyzed */
    const char *zMUuid;   /* Check-in containing the file */
    const char *zUser;    /* User who did the check-in */
    const char *zDate;    /* Date of the check-in */
    const char *zBgColor; /* Suggested background color */
    unsigned cnt;         /* Number of lines contributed by this check-in */
  } *aVers;         /* For each check-in analyzed */
  char **azVers;    /* Names of versions analyzed */
};

/*
** Initialize the annotation process by specifying the file that is
** to be annotated.  The annotator takes control of the input Blob and
** will release it when it is finished with it.
*/
static int annotation_start(Annotator *p, Blob *pInput){
  int i;

  memset(p, 0, sizeof(*p));
  p->c.aTo = break_into_lines(blob_str(pInput), blob_size(pInput),&p->c.nTo,1);
  if( p->c.aTo==0 ){
    return 1;
  }
  p->aOrig = fossil_malloc( sizeof(p->aOrig[0])*p->c.nTo );
  for(i=0; i<p->c.nTo; i++){
    p->aOrig[i].z = p->c.aTo[i].z;
    p->aOrig[i].n = p->c.aTo[i].h & LENGTH_MASK;
    p->aOrig[i].iVers = -1;
  }
  p->nOrig = p->c.nTo;
  return 0;
}

/*
** The input pParent is the next most recent ancestor of the file
** being annotated.  Do another step of the annotation.  Return true
** if additional annotation is required.  zPName is the tag to insert
** on each line of the file being annotated that was contributed by
** pParent.  Memory to hold zPName is leaked.
*/
static int annotation_step(Annotator *p, Blob *pParent, int iVers){
  int i, j;
  int lnTo;



  /* Prepare the parent file to be diffed */
  p->c.aFrom = break_into_lines(blob_str(pParent), blob_size(pParent),
                                &p->c.nFrom, 1);
  if( p->c.aFrom==0 ){
    return 1;
  }

  /* Compute the differences going from pParent to the file being
  ** annotated. */
  diff_all(&p->c);

  /* Where new lines are inserted on this difference, record the
  ** iVers as the source of the new line.
  */

  p->iLevel++;

  for(i=lnTo=0; i<p->c.nEdit; i+=3){
    int nCopy = p->c.aEdit[i];
    int nIns = p->c.aEdit[i+2];
    lnTo += nCopy;
    for(j=0; j<nIns; j++, lnTo++){
      if( p->aOrig[lnTo].iVers<0 ){

        p->aOrig[lnTo].iVers = iVers;
      }
    }

  }

  /* Clear out the diff results */
  fossil_free(p->c.aEdit);
  p->c.aEdit = 0;
  p->c.nEdit = 0;
  p->c.nEditAlloc = 0;

  /* Clear out the from file */
  free(p->c.aFrom);

  /* Return no errors */
  return 0;
}































/* Annotation flags */
#define ANN_FILE_VERS    0x01   /* Show file vers rather than commit vers */
#define ANN_FILE_ANCEST  0x02   /* Prefer check-ins in the ANCESTOR table */

/*
** Compute a complete annotation on a file.  The file is identified
** by its filename number (filename.fnid) and the baseline in which
** it was checked in (mlink.mid).
*/
static void annotate_file(
  Annotator *p,        /* The annotator */
  int fnid,            /* The name of the file to be annotated */
  int mid,             /* Use the version of the file in this check-in */

  int iLimit,          /* Limit the number of levels if greater than zero */
  int annFlags         /* Flags to alter the annotation */
){
  Blob toAnnotate;     /* Text of the final (mid) version of the file */
  Blob step;           /* Text of previous revision */
  int rid;             /* Artifact ID of the file being annotated */
  char *zLabel;        /* Label to apply to a line */

  db_multi_exec(
     "CREATE TEMP TABLE IF NOT EXISTS vseen(rid INTEGER PRIMARY KEY);"
     "DELETE FROM vseen;"
  );

  db_prepare(&ins, "INSERT OR IGNORE INTO vseen(rid) VALUES(:rid)");
  db_prepare(&q,
    "SELECT (SELECT uuid FROM blob WHERE rid=mlink.fid),"
    "       (SELECT uuid FROM blob WHERE rid=mlink.mid),"
    "       date(event.mtime),"
    "       coalesce(event.euser,event.user),"
    "       mlink.pid"
    "  FROM mlink, event"
    " WHERE mlink.fid=:rid"
    "   AND event.objid=mlink.mid"
    "   AND mlink.pid NOT IN vseen"
    " ORDER BY %s event.mtime",

    (annFlags & ANN_FILE_ANCEST)!=0 ?
         "(mlink.mid IN (SELECT rid FROM ancestor)) DESC,":""
  );

  db_bind_int(&q, ":rid", rid);
  if( iLimit==0 ) iLimit = 1000000000;
  while( rid && iLimit>cnt && db_step(&q)==SQLITE_ROW ){
    int prevId = db_column_int(&q, 4);
    p->aVers = fossil_realloc(p->aVers, (p->nVers+1)*sizeof(p->aVers[0]));
    p->aVers[p->nVers].zFUuid = fossil_strdup(db_column_text(&q, 0));
    p->aVers[p->nVers].zMUuid = fossil_strdup(db_column_text(&q, 1));
    p->aVers[p->nVers].zDate = fossil_strdup(db_column_text(&q, 2));
    p->aVers[p->nVers].zUser = fossil_strdup(db_column_text(&q, 3));
    if( p->nVers ){


      content_get(rid, &step);
      annotation_step(p, &step, p->nVers-1);
      blob_reset(&step);

    }
    p->nVers++;




    db_bind_int(&ins, ":rid", rid);
    db_step(&ins);
    db_reset(&ins);

    db_reset(&q);
    rid = prevId;
    db_bind_int(&q, ":rid", prevId);
    cnt++;
  }
  db_finalize(&q);
  db_finalize(&ins);
  db_end_transaction(0);
}

/*
** Return a color from a gradient.
*/
unsigned gradient_color(unsigned c1, unsigned c2, int n, int i){
  unsigned c;   /* Result color */
  unsigned x1, x2;
  x1 = (c1>>16)&0xff;
  x2 = (c2>>16)&0xff;
  c = (x1*(n-i) + x2*i)/n<<16 & 0xff0000;
  x1 = (c1>>8)&0xff;
  x2 = (c2>>8)&0xff;
  c |= (x1*(n-i) + x2*i)/n<<8 & 0xff00;
  x1 = c1&0xff;
  x2 = c2&0xff;
  c |= (x1*(n-i) + x2*i)/n & 0xff;
  return c;
}

/*
** WEBPAGE: annotate
**
** Query parameters:
**
**    checkin=ID          The manifest ID at which to start the annotation

  int annFlags = ANN_FILE_ANCEST;  
  int showLn = 0;        /* True if line numbers should be shown */
  int showLog = 0;       /* True to display the log */
  char zLn[10];          /* Line number buffer */
  char zFormat[10];      /* Format string for line numbers */
  Annotator ann;
  HQuery url;
  struct AnnVers *p;
  unsigned clr1, clr2, clr;

  showLn = atoi(PD("ln","1"));
  showLog = atoi(PD("log","1"));
  login_check_credentials();
  if( !g.perm.Read ){ login_needed(); return; }
  mid = name_to_typed_rid(PD("checkin","0"),"ci");
  fnid = db_int(0, "SELECT fnid FROM filename WHERE name=%Q", P("filename"));

    z2 = sqlite3_mprintf("%d", iLimit+20);
    style_submenu_element(z1, z1, url_render(&url, "limit", z2, 0, 0));
  }
  if( iLimit!=20 ){
    style_submenu_element("20 Ancestors", "20 Ancestors",
       url_render(&url, "limit", "20", 0, 0));
  }
  annotate_file(&ann, fnid, mid, iLimit, annFlags);
  if( db_get_boolean("white-foreground", 0) ){
    clr1 = 0xa04040;
    clr2 = 0x4059a0;
  }else{
    clr1 = 0xffb5b5;  /* Recent changes: red (hot) */
    clr2 = 0xb5e0ff;  /* Older changes: blue (cold) */
  }
  for(p=ann.aVers, i=0; i<ann.nVers; i++, p++){
    clr = gradient_color(clr1, clr2, ann.nVers-1, i);
    ann.aVers[i].zBgColor = mprintf("#%06x", clr);
    ann.aVers[i].zUser = mprintf("%h", ann.aVers[i].zUser);
  }  

  if( showLog ){

    @ <h2>Versions analyzed:</h2>
    @ <ol>
    for(p=ann.aVers, i=0; i<ann.nVers; i++, p++){
      @ <li><span style='background-color:%s(p->zBgColor);'>%s(p->zDate)
      @ check-in %z(href("%R/info/%S",p->zMUuid))%.10s(p->zMUuid)</a>
      @ artifact %z(href("%R/artifact/%S",p->zFUuid))%.10s(p->zFUuid)</a>
      @ </span>
#if 0
      if( i>0 ){
        char *zLink = xhref("target='infowindow'",
                            "%R/fdiff?v1=%S&v2=%S&sbs=1",
                            p->zFUuid,ann.aVers[0].zFUuid);
        @ %z(zLink)[diff-to-top]</a>
        if( i>1 ){
           zLink = xhref("target='infowindow'",
                         "%R/fdiff?v1=%S&v2=%S&sbs=1",
                         p->zFUuid,p[-1].zFUuid);
           @ %z(zLink)[diff-to-previous]</a>
        }
      }
#endif
    }
    @ </ol>
    @ <hr>
  }
  if( iLimit<0 ){
    @ <h2>Annotation:</h2>
    iLimit = ann.nVers+10;
  }else{
    @ <h2>Annotation of %d(iLimit) most recent ancestors:</h2>
  }
  if( showLn ){
    sqlite3_snprintf(sizeof(zLn), zLn, "%d", ann.nOrig+1);
    sqlite3_snprintf(sizeof(zFormat), zFormat, "%%%dd:", strlen(zLn));
  }else{
    zLn[0] = 0;
  }
  @ <pre>
  for(i=0; i<ann.nOrig; i++){
    struct AnnVers *p;
    int iVers = ann.aOrig[i].iVers;
    char *z = (char*)ann.aOrig[i].z;
    int n = ann.aOrig[i].n;
    char zPrefix[300];
    z[n] = 0;
    if( iLimit>ann.nVers && iVers<0 ) iVers = ann.nVers-1;
    if( iVers>=0 ){

      struct AnnVers *p = ann.aVers+iVers;
      char *zLink = xhref("target='infowindow'", "%R/info/%S", p->zMUuid);
      sqlite3_snprintf(sizeof(zPrefix), zPrefix,
           "<span style='background-color:%s'>"
           "%s%.10s</a> %s</span> %4d:",
           p->zBgColor, zLink, p->zMUuid, p->zDate, i+1);
      fossil_free(zLink);
    }else{
      sqlite3_snprintf(sizeof(zPrefix), zPrefix, "%22s%4d:", "", i+1);
    }
    @ %s(zPrefix) %h(z)



  }
  @ </pre>
  style_footer();
}

/*
** COMMAND: annotate

  mid = db_int(0, "SELECT mlink.mid FROM mlink, ancestor "
          " WHERE mlink.fid=%d AND mlink.fnid=%d AND mlink.mid=ancestor.rid"
          " ORDER BY ancestor.generation ASC LIMIT 1",
          fid, fnid);
  if( mid==0 ){
    fossil_panic("unable to find manifest");
  }

  annFlags |= ANN_FILE_ANCEST;
  annotate_file(&ann, fnid, mid, iLimit, annFlags);
  if( showLog ){
    struct AnnVers *p;
    for(p=ann.aVers, i=0; i<ann.nVers; i++, p++){
      fossil_print("version %3d: %s %.10s file %.10s\n",
                   i+1, p->zDate, p->zMUuid, p->zFUuid);
    }
    fossil_print("---------------------------------------------------\n");
  }
  for(i=0; i<ann.nOrig; i++){
    struct AnnVers *p;
    int iVers = ann.aOrig[i].iVers;
    char *z = (char*)ann.aOrig[i].z;
    int n = ann.aOrig[i].n;
    char zPrefix[200];
    z[n] = 0;
    if( iLimit>ann.nVers && iVers<0 ) iVers = ann.nVers-1;
    if( iVers>=0 ){
      struct AnnVers *p = ann.aVers+iVers;
      sqlite3_snprintf(sizeof(zPrefix), zPrefix, "%.10s %s",
           fileVers ? p->zFUuid : p->zMUuid, p->zDate);
    }else{
      zPrefix[0] = 0;
    }
    fossil_print("%21s %4d: %.*s\n", zPrefix, i+1, n, z);

  }
}

/*
** COMMAND: test-looks-like-utf
**
** Usage:  %fossil test-looks-like-utf FILENAME