** of the line.  If any line is longer than LENGTH_MASK characters,
** the file is considered binary.
*/
typedef struct DLine DLine;
struct DLine {
  const char *z;          /* The text of the line */
  u64 h;                  /* Hash of the line */
  unsigned short indent;  /* Index of first non-space */
  unsigned short n;       /* number of bytes */
  unsigned short nw;      /* number of bytes without leading/trailing space */
  unsigned int iNext;     /* 1+(Index of next line with same the same hash) */

  /* an array of DLine elements serves two purposes.  The fields
  ** above are one per line of input text.  But each entry is also
  ** a bucket in a hash table, as follows: */
  unsigned int iHash;     /* 1+(first entry in the hash chain) */
};

  int *aEdit;        /* Array of copy/delete/insert triples */
  int nEdit;         /* Number of integers (3x num of triples) in aEdit[] */
  int nEditAlloc;    /* Space allocated for aEdit[] */
  DLine *aFrom;      /* File on left side of the diff */
  int nFrom;         /* Number of lines in aFrom[] */
  DLine *aTo;        /* File on right side of the diff */
  int nTo;           /* Number of lines in aTo[] */
  int (*xDiffer)(DLine*,DLine*); /* comparison function */
};

/* Fast isspace for use by diff */
static const char diffIsSpace[] = {
  0, 0, 0, 0, 0, 0, 0, 0,   1, 1, 1, 0, 1, 1, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  1, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,

  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
};
#define diff_isspace(X)  (diffIsSpace[(unsigned char)(X)])

/*
** Count the number of lines in the input string.  Include the last line
** in the count even if it lacks the \n terminator.  If an empty string
** is specified, the number of lines is zero.  For the purposes of this
** function, a string is considered empty if it contains no characters
** -OR- it contains only NUL characters.

    a[i].z = z;
    k = nn;
    if( diffFlags & DIFF_STRIP_EOLCR ){
      if( k>0 && z[k-1]=='\r' ){ k--; }
    }
    a[i].n = k;
    if( diffFlags & DIFF_IGNORE_EOLWS ){
      while( k>0 && diff_isspace(z[k-1]) ){ k--; }
    }


    if( (diffFlags & DIFF_IGNORE_ALLWS)==DIFF_IGNORE_ALLWS ){
      int numws = 0;
      for(s=0; s<k && z[s]<=' '; s++){}
      a[i].indent = s;
      for(h=0, x=s; x<k; x++){
        char c = z[x];
        if( diff_isspace(c) ){
          ++numws;
        }else{
          h = (h^c)*9000000000000000041LL;
        }
      }
      k -= numws;
      a[i].nw = k - s;
    }else{
      int k2 = k & ~0x7;
      u64 m;
      for(h=x=s=0; x<k2; x += 8){
        memcpy(&m, z+x, 8);
        h = (h^m)*9000000000000000041LL;
      }
      m = 0;
      memcpy(&m, z+x, k-k2);
      h ^= m;
    }

  *pnLine = nLine;
  return a;
}

/*
** Return zero if two DLine elements are identical.
*/
static int compare_dline(DLine *pA, DLine *pB){
  if( pA->h!=pB->h ) return 1;
  return memcmp(pA->z,pB->z, pA->h&LENGTH_MASK);
}

/*
** Return zero if two DLine elements are identical, ignoring
** all whitespace. The indent field of pA/pB already points
** to the first non-space character in the string.
*/

static int compare_dline_ignore_allws(DLine *pA, DLine *pB){
  int a = pA->indent, b = pB->indent;
  if( pA->h==pB->h ){
    while( a<pA->n || b<pB->n ){
      if( a<pA->n && b<pB->n && pA->z[a++] != pB->z[b++] ) return 1;
      while( a<pA->n && diff_isspace(pA->z[a])) ++a;
      while( b<pB->n && diff_isspace(pB->z[b])) ++b;
    }
    return pA->n-a != pB->n-b;
  }
  return 1;
}

/*
** Return true if the regular expression *pRe matches any of the
** N dlines
*/
static int re_dline_match(
  ReCompiled *pRe,      /* The regular expression to be matched */
  DLine *aDLine,  /* First of N DLines to compare against */
  int N                 /* Number of DLines to check */
){
  while( N-- ){
    if( re_match(pRe, (const unsigned char *)aDLine->z, LENGTH(aDLine)) ){
      return 1;
    }
    aDLine++;

}

/*
** Return true if the string starts with n spaces
*/
static int allSpaces(const char *z, int n){
  int i;
  for(i=0; i<n && diff_isspace(z[i]); i++){}
  return i==n;
}

/*
** Try to improve the human-readability of the LineChange p.
**
** (1)  If the first change span shows a change of indentation, try to

** Given two lines of text, pFrom and pTo, compute a set of changes
** between those two lines, for enhanced display purposes.
**
** The result is written into the LineChange object given by the
** third parameter.
*/
static void oneLineChange(
  DLine *pLeft,  /* Left line of the change */
  DLine *pRight, /* Right line of the change */
  LineChange *p        /* OUTPUT: Write the results here */
){
  int nLeft;           /* Length of left line in bytes */
  int nRight;          /* Length of right line in bytes */
  int nShort;          /* Shortest of left and right */
  int nPrefix;         /* Length of common prefix */
  int nSuffix;         /* Length of common suffix */

    int iBestVal = -1;
    int i;
    int nLong = nLeft<nRight ? nRight : nLeft;
    int nGap = nLong - nShort;
    for(i=nShort-nSuffix; i<=nPrefix; i++){
       int iVal = 0;
       char c = zLeft[i];
       if( diff_isspace(c) ){
         iVal += 5;
       }else if( !fossil_isalnum(c) ){
         iVal += 2;
       }
       c = zLeft[i+nGap-1];
       if( diff_isspace(c) ){
         iVal += 5;
       }else if( !fossil_isalnum(c) ){
         iVal += 2;
       }
       if( iVal>iBestVal ){
         iBestVal = iVal;
         iBest = i;

**
** To subclass, create an instance of the DiffBuilder object and fill
** in appropriate method implementations.
*/ 
typedef struct DiffBuilder DiffBuilder;
struct DiffBuilder {
  void (*xSkip)(DiffBuilder*, unsigned int, int);
  void (*xCommon)(DiffBuilder*,DLine*);
  void (*xInsert)(DiffBuilder*,DLine*);
  void (*xDelete)(DiffBuilder*,DLine*);
  void (*xReplace)(DiffBuilder*,DLine*, DLine*);
  void (*xEdit)(DiffBuilder*,DLine*,DLine*);
  void (*xEnd)(DiffBuilder*);
  unsigned int lnLeft;              /* Lines seen on the left (delete) side */
  unsigned int lnRight;             /* Lines seen on the right (insert) side */
  unsigned int nPending;            /* Number of pending lines */
  int eState;                       /* State of the output */
  int width;                        /* Display width */
  Blob *pOut;                       /* Output blob */

static void dfdebugSkip(DiffBuilder *p, unsigned int n, int isFinal){
  blob_appendf(p->pOut, "SKIP %d (%d..%d left and %d..%d right)%s\n",
                n, p->lnLeft+1, p->lnLeft+n, p->lnRight+1, p->lnRight+n,
                isFinal ? " FINAL" : "");
  p->lnLeft += n;
  p->lnRight += n;
}
static void dfdebugCommon(DiffBuilder *p, DLine *pLine){
  p->lnLeft++;
  p->lnRight++;
  blob_appendf(p->pOut, "COMMON  %8u %8u %.*s\n",
      p->lnLeft, p->lnRight, (int)pLine->n, pLine->z);
}
static void dfdebugInsert(DiffBuilder *p, DLine *pLine){
  p->lnRight++;
  blob_appendf(p->pOut, "INSERT           %8d %.*s\n",
      p->lnRight, (int)pLine->n, pLine->z);
}
static void dfdebugDelete(DiffBuilder *p, DLine *pLine){
  p->lnLeft++;
  blob_appendf(p->pOut, "DELETE  %8u          %.*s\n",
      p->lnLeft, (int)pLine->n, pLine->z);
}
static void dfdebugReplace(DiffBuilder *p, DLine *pX, DLine *pY){
  p->lnLeft++;
  p->lnRight++;
  blob_appendf(p->pOut, "REPLACE %8u          %.*s\n",
      p->lnLeft, (int)pX->n, pX->z);
  blob_appendf(p->pOut, "            %8u %.*s\n",
      p->lnRight, (int)pY->n, pY->z);
}
static void dfdebugEdit(DiffBuilder *p, DLine *pX, DLine *pY){
  int i, j;
  int x;
  LineChange chng;
  p->lnLeft++;
  p->lnRight++;
  blob_appendf(p->pOut, "EDIT    %8u          %.*s\n",
               p->lnLeft, (int)pX->n, pX->z);

** will be an empty string.  (1) might be empty for the first triple if
** the line begins with an edit.  After all triples, there might be one
** additional string which is a common suffix.
*/
static void dftclSkip(DiffBuilder *p, unsigned int n, int isFinal){
  blob_appendf(p->pOut, "SKIP %u\n", n);
}
static void dftclCommon(DiffBuilder *p, DLine *pLine){
  blob_appendf(p->pOut, "COM ");
  blob_append_tcl_literal(p->pOut, pLine->z, pLine->n);
  blob_append_char(p->pOut, '\n');
}
static void dftclInsert(DiffBuilder *p, DLine *pLine){
  blob_append(p->pOut, "INS ", -1);
  blob_append_tcl_literal(p->pOut, pLine->z, pLine->n);
  blob_append_char(p->pOut, '\n');
}
static void dftclDelete(DiffBuilder *p, DLine *pLine){
  blob_append(p->pOut, "DEL ", -1);
  blob_append_tcl_literal(p->pOut, pLine->z, pLine->n);
  blob_append_char(p->pOut, '\n');
}
static void dftclReplace(DiffBuilder *p, DLine *pX, DLine *pY){
  blob_append(p->pOut, "EDIT \"\" ", -1);
  blob_append_tcl_literal(p->pOut, pX->z, pX->n);
  blob_append_char(p->pOut, ' ');
  blob_append_tcl_literal(p->pOut, pY->z, pY->n);
  blob_append_char(p->pOut, '\n');
}
static void dftclEdit(DiffBuilder *p, DLine *pX, DLine *pY){
  int i, x;
  LineChange chng;
  blob_append(p->pOut, "EDIT", 4);
  oneLineChange(pX, pY, &chng);
  for(i=x=0; i<chng.n; i++){
    blob_append_char(p->pOut, ' ');
    blob_append_tcl_literal(p->pOut, pX->z + x, chng.a[i].iStart1 - x);

** represent common-text, left-text, and right-text.  The last string
** in SUBARRAY is the common-suffix.  Any string can be empty if it does
** not apply.
*/
static void dfjsonSkip(DiffBuilder *p, unsigned int n, int isFinal){
  blob_appendf(p->pOut, "1,%u,\n", n);
}
static void dfjsonCommon(DiffBuilder *p, DLine *pLine){
  blob_append(p->pOut, "2,",2);
  blob_append_json_literal(p->pOut, pLine->z, (int)pLine->n);
  blob_append(p->pOut, ",\n",2);
}
static void dfjsonInsert(DiffBuilder *p, DLine *pLine){
  blob_append(p->pOut, "3,",2);
  blob_append_json_literal(p->pOut, pLine->z, (int)pLine->n);
  blob_append(p->pOut, ",\n",2);
}
static void dfjsonDelete(DiffBuilder *p, DLine *pLine){
  blob_append(p->pOut, "4,",2);
  blob_append_json_literal(p->pOut, pLine->z, (int)pLine->n);
  blob_append(p->pOut, ",\n",2);
}
static void dfjsonReplace(DiffBuilder *p, DLine *pX, DLine *pY){
  blob_append(p->pOut, "5,[\"\",",-1);
  blob_append_json_literal(p->pOut, pX->z, (int)pX->n);
  blob_append(p->pOut, ",",1);
  blob_append_json_literal(p->pOut, pY->z, (int)pY->n);
  blob_append(p->pOut, ",\"\"],\n",-1);
}
static void dfjsonEdit(DiffBuilder *p, DLine *pX, DLine *pY){
  int i, x;
  LineChange chng;
  blob_append(p->pOut, "5,[", 3);
  oneLineChange(pX, pY, &chng);
  for(i=x=0; i<chng.n; i++){
    if(i>0){
      blob_append_char(p->pOut, ',');

    blob_append(p->pOut, "<tr>", 4);
  }
  blob_append(p->pOut, "<td class=\"diffln difflne\">"
                       "&#xfe19;</td><td></td><td></td></tr>\n", -1);
  p->lnLeft += n;
  p->lnRight += n;
}
static void dfunifiedCommon(DiffBuilder *p, DLine *pLine){
  dfunifiedStartRow(p);
  dfunifiedFinishDelete(p);
  dfunifiedFinishInsert(p);
  p->lnLeft++;
  p->lnRight++;
  blob_appendf(p->pOut,"%d\n", p->lnLeft);
  blob_appendf(&p->aCol[0],"%d\n",p->lnRight);
  blob_append_char(&p->aCol[1], '\n');
  htmlize_to_blob(&p->aCol[2], pLine->z, (int)pLine->n);
  blob_append_char(&p->aCol[2], '\n');
}
static void dfunifiedInsert(DiffBuilder *p, DLine *pLine){
  dfunifiedStartRow(p);
  p->lnRight++;
  blob_appendf(&p->aCol[3],"%d\n", p->lnRight);
  blob_append(&p->aCol[4], "<ins>", 5);
  htmlize_to_blob(&p->aCol[4], pLine->z, (int)pLine->n);
  blob_append(&p->aCol[4], "</ins>\n", 7);
  p->nPending++;
}
static void dfunifiedDelete(DiffBuilder *p, DLine *pLine){
  dfunifiedStartRow(p);
  dfunifiedFinishInsert(p);
  if( p->eState==0 ){
    dfunifiedFinishInsert(p);
    blob_append(p->pOut, "<del>", 5);
    blob_append(&p->aCol[2], "<del>", 5);
    p->eState = 1;
  }
  p->lnLeft++;
  blob_appendf(p->pOut,"%d\n", p->lnLeft);
  blob_append_char(&p->aCol[0],'\n');
  blob_append(&p->aCol[1],"-\n",2);
  blob_append(&p->aCol[2], "<del>", 5);
  htmlize_to_blob(&p->aCol[2], pLine->z, (int)pLine->n);
  blob_append(&p->aCol[2], "</del>\n", 7);
}
static void dfunifiedReplace(DiffBuilder *p, DLine *pX, DLine *pY){
  dfunifiedStartRow(p);
  if( p->eState==0 ){
    dfunifiedFinishInsert(p);
    blob_append(p->pOut, "<del>", 5);
    blob_append(&p->aCol[2], "<del>", 5);
    p->eState = 1;
  }

  blob_appendf(&p->aCol[3],"%d\n", p->lnRight);

  htmlize_to_blob(&p->aCol[4], pY->z,  pY->n);
  blob_append_char(&p->aCol[4], '\n');
  p->nPending++;
}
static void dfunifiedEdit(DiffBuilder *p, DLine *pX, DLine *pY){
  int i;
  int x;
  LineChange chng;
  oneLineChange(pX, pY, &chng);
  dfunifiedStartRow(p);
  if( p->eState==0 ){
    dfunifiedFinishInsert(p);

       "<td class=\"diffln difflnl difflne\">&#xfe19;</td>"
       "<td></td><td></td>"
       "<td class=\"diffln difflnr difflne\">&#xfe19;</td>"
       "<td/td></tr>\n", -1);
  p->lnLeft += n;
  p->lnRight += n;
}
static void dfsplitCommon(DiffBuilder *p, DLine *pLine){
  dfsplitStartRow(p);
  dfsplitChangeState(p, 0);
  p->lnLeft++;
  p->lnRight++;
  blob_appendf(p->pOut,"%d\n", p->lnLeft);
  htmlize_to_blob(&p->aCol[0], pLine->z, (int)pLine->n);
  blob_append_char(&p->aCol[0], '\n');
  blob_append_char(&p->aCol[1], '\n');
  blob_appendf(&p->aCol[2],"%d\n",p->lnRight);
  htmlize_to_blob(&p->aCol[3], pLine->z, (int)pLine->n);
  blob_append_char(&p->aCol[3], '\n');
}
static void dfsplitInsert(DiffBuilder *p, DLine *pLine){
  dfsplitStartRow(p);
  dfsplitChangeState(p, 2);
  p->lnRight++;
  blob_append_char(p->pOut, '\n');
  blob_append_char(&p->aCol[0], '\n');
  blob_append(&p->aCol[1], "&gt;\n", -1);
  blob_appendf(&p->aCol[2],"%d\n", p->lnRight);
  blob_append(&p->aCol[3], "<ins>", 5);
  htmlize_to_blob(&p->aCol[3], pLine->z, (int)pLine->n);
  blob_append(&p->aCol[3], "</ins>\n", 7);
}
static void dfsplitDelete(DiffBuilder *p, DLine *pLine){
  dfsplitStartRow(p);
  dfsplitChangeState(p, 1);
  p->lnLeft++;
  blob_appendf(p->pOut,"%d\n", p->lnLeft);
  blob_append(&p->aCol[0], "<del>", 5);
  htmlize_to_blob(&p->aCol[0], pLine->z, (int)pLine->n);
  blob_append(&p->aCol[0], "</del>\n", 7);
  blob_append(&p->aCol[1], "&lt;\n", -1);
  blob_append_char(&p->aCol[2],'\n');
  blob_append_char(&p->aCol[3],'\n');
}
static void dfsplitReplace(DiffBuilder *p, DLine *pX, DLine *pY){
  dfsplitStartRow(p);
  dfsplitChangeState(p, 3);
  p->lnLeft++;
  p->lnRight++;
  blob_appendf(p->pOut,"%d\n", p->lnLeft);
  htmlize_to_blob(&p->aCol[0], pX->z,  pX->n);
  blob_append_char(&p->aCol[0], '\n');

  blob_append(&p->aCol[1], "|\n", 2);

  blob_appendf(&p->aCol[2],"%d\n", p->lnRight);

  htmlize_to_blob(&p->aCol[3], pY->z,  pY->n);
  blob_append_char(&p->aCol[3], '\n');
}
static void dfsplitEdit(DiffBuilder *p, DLine *pX, DLine *pY){
  int i;
  int x;
  LineChange chng;
  oneLineChange(pX, pY, &chng);
  dfsplitStartRow(p);
  dfsplitChangeState(p, 3);
  p->lnLeft++;

/*
** Append at least iMin characters (not bytes) and at most iMax characters
** from pX onto the into of p.
**
** This comment contains multibyte unicode characters (ü, Æ, ð) in order
** to test the ability of the diff code to handle such characters.
*/
static void sbs_append_chars(Blob *p, int iMin, int iMax, DLine *pX){
  int i;
  const char *z = pX->z;
  for(i=0; i<iMax && i<pX->n; i++){
    char c = z[i];
    blob_append_char(p, c);
    if( (c&0xc0)==0x80 ){ iMin++; iMax++; }
  }
  while( i<iMin ){
    blob_append_char(p, ' ');
    i++;
  }
}

static void dfsbsCommon(DiffBuilder *p, DLine *pLine){
  p->lnLeft++;
  p->lnRight++;
  blob_appendf(p->pOut,"%6u ", p->lnLeft);
  sbs_append_chars(p->pOut, p->width, p->width, pLine);
  blob_appendf(p->pOut,"   %6u ", p->lnRight);
  sbs_append_chars(p->pOut, 0, p->width, pLine);
  blob_append_char(p->pOut, '\n');
}
static void dfsbsInsert(DiffBuilder *p, DLine *pLine){
  p->lnRight++;
  blob_appendf(p->pOut,"%6s %*s > %6u ",
     "", p->width, "", p->lnRight);
  sbs_append_chars(p->pOut, 0, p->width, pLine);
  blob_append_char(p->pOut, '\n');
}
static void dfsbsDelete(DiffBuilder *p, DLine *pLine){
  p->lnLeft++;
  blob_appendf(p->pOut,"%6u ", p->lnLeft);
  sbs_append_chars(p->pOut, p->width, p->width, pLine);
  blob_append(p->pOut," <\n", 3);
}
static void dfsbsEdit(DiffBuilder *p, DLine *pX, DLine *pY){
  p->lnLeft++;
  p->lnRight++;
  blob_appendf(p->pOut,"%6u ", p->lnLeft);
  sbs_append_chars(p->pOut, p->width, p->width, pX);
  blob_appendf(p->pOut, " | %6u ", p->lnRight);
  sbs_append_chars(p->pOut, 0, p->width, pY);
  blob_append_char(p->pOut, '\n');

** (1) Remove leading and trailing whitespace.
** (2) Truncate both strings to at most 250 characters
** (3) If the two strings have a common prefix, measure that prefix
** (4) Find the length of the longest common subsequence that is
**     at least 150% longer than the common prefix.
** (5) Longer common subsequences yield lower scores.
*/
static int match_dline(DLine *pA, DLine *pB){
  const char *zA;            /* Left string */
  const char *zB;            /* right string */
  int nA;                    /* Bytes in zA[] */
  int nB;                    /* Bytes in zB[] */
  int nMin;
  int nPrefix;
  int avg;                   /* Average length of A and B */
  int i, j, k;               /* Loop counters */
  int best = 0;              /* Longest match found so far */
  int score;                 /* Final score.  0..100 */
  unsigned char c;           /* Character being examined */
  unsigned char aFirst[256]; /* aFirst[X] = index in zB[] of first char X */
  unsigned char aNext[252];  /* aNext[i] = index in zB[] of next zB[i] char */

  zA = pA->z;
  if( pA->nw==0 && pA->n ){
    for(i=0; i<pA->n && diff_isspace(zA[i]); i++){}
    pA->indent = i;
    for(j=pA->n-1; j>i && diff_isspace(zA[j]); j--){}
    pA->nw = j - i + 1;
  }
  zA += pA->indent;
  nA = pA->nw;

  zB = pB->z;
  if( pB->nw==0 && pB->n ){
    for(i=0; i<pB->n && diff_isspace(zB[i]); i++){}
    pB->indent = i;
    for(j=pB->n-1; j>i && diff_isspace(zB[j]); j--){}
    pB->nw = j - i + 1;
  }
  zB += pB->indent;
  nB = pB->nw;


  if( nA>250 ) nA = 250;
  if( nB>250 ) nB = 250;
  avg = (nA+nB)/2;
  if( avg==0 ) return 0;
  nMin = nA;
  if( nB<nMin ) nMin = nB;
  if( nMin==0 ) return 68;

** Algorithm:  Wagner's minimum edit-distance algorithm, modified by
** adding a cost to each match based on how well the two rows match
** each other.  Insertion and deletion costs are 50.  Match costs
** are between 0 and 100 where 0 is a perfect match 100 is a complete
** mismatch.
*/
static unsigned char *diffBlockAlignment(
  DLine *aLeft, int nLeft,     /* Text on the left */
  DLine *aRight, int nRight,   /* Text on the right */
  DiffConfig *pCfg,                  /* Configuration options */
  int *pNResult                      /* OUTPUT: Bytes of result */
){
  int i, j, k;                 /* Loop counters */
  int *a;                      /* One row of the Wagner matrix */
  int *pToFree;                /* Space that needs to be freed */
  unsigned char *aM;           /* Wagner result matrix */

  /* For large alignments, use a divide and conquer algorithm that is
  ** O(NlogN).  The result is not as precise, but this whole thing is an
  ** approximation anyhow, and the faster response time is an acceptable
  ** trade-off for reduced precision.
  */
  if( nLeft*nRight>DIFF_ALIGN_MX && (pCfg->diffFlags & DIFF_SLOW_SBS)==0 ){
    DLine *aSmall;   /* The smaller of aLeft and aRight */
    DLine *aBig;     /* The larger of aLeft and aRight */
    int nSmall, nBig;      /* Size of aSmall and aBig.  nSmall<=nBig */
    int iDivSmall, iDivBig;  /* Divider point for aSmall and aBig */
    int iDivLeft, iDivRight; /* Divider point for aLeft and aRight */
    unsigned char *a1, *a2;  /* Results of the alignments on two halves */
    int n1, n2;              /* Number of entries in a1 and a2 */
    int score, bestScore;    /* Score and best score seen so far */
    if( nLeft>nRight ){

** Format a diff using a DiffBuilder object
*/
static void formatDiff(
  DContext *p,           /* The computed diff */
  DiffConfig *pCfg,      /* Configuration options */
  DiffBuilder *pBuilder  /* The formatter object */
){
  DLine *A;        /* Left side of the diff */
  DLine *B;        /* Right side of the diff */
  unsigned int a = 0;    /* Index of next line in A[] */
  unsigned int b = 0;    /* Index of next line in B[] */
  const int *R;          /* Array of COPY/DELETE/INSERT triples */
  unsigned int r;        /* Index into R[] */
  unsigned int nr;       /* Number of COPY/DELETE/INSERT triples to process */
  unsigned int mxr;      /* Maximum value for r */
  unsigned int na, nb;   /* Number of lines shown from A and B */