144b87433SJohn Marino /* Analyze differences between two vectors.
244b87433SJohn Marino
3*6ea1f93eSDaniel Fojt Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2018 Free Software
444b87433SJohn Marino Foundation, Inc.
544b87433SJohn Marino
644b87433SJohn Marino This program is free software: you can redistribute it and/or modify
744b87433SJohn Marino it under the terms of the GNU General Public License as published by
844b87433SJohn Marino the Free Software Foundation; either version 3 of the License, or
944b87433SJohn Marino (at your option) any later version.
1044b87433SJohn Marino
1144b87433SJohn Marino This program is distributed in the hope that it will be useful,
1244b87433SJohn Marino but WITHOUT ANY WARRANTY; without even the implied warranty of
1344b87433SJohn Marino MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1444b87433SJohn Marino GNU General Public License for more details.
1544b87433SJohn Marino
1644b87433SJohn Marino You should have received a copy of the GNU General Public License
17*6ea1f93eSDaniel Fojt along with this program. If not, see <https://www.gnu.org/licenses/>. */
1844b87433SJohn Marino
1944b87433SJohn Marino
2044b87433SJohn Marino /* The basic idea is to consider two vectors as similar if, when
2144b87433SJohn Marino transforming the first vector into the second vector through a
2244b87433SJohn Marino sequence of edits (inserts and deletes of one element each),
2344b87433SJohn Marino this sequence is short - or equivalently, if the ordered list
2444b87433SJohn Marino of elements that are untouched by these edits is long. For a
2544b87433SJohn Marino good introduction to the subject, read about the "Levenshtein
2644b87433SJohn Marino distance" in Wikipedia.
2744b87433SJohn Marino
2844b87433SJohn Marino The basic algorithm is described in:
29*6ea1f93eSDaniel Fojt "An O(ND) Difference Algorithm and its Variations", Eugene W. Myers,
30*6ea1f93eSDaniel Fojt Algorithmica Vol. 1, 1986, pp. 251-266,
31*6ea1f93eSDaniel Fojt <http://dx.doi.org/10.1007/BF01840446>.
32*6ea1f93eSDaniel Fojt See especially section 4.2, which describes the variation used below.
3344b87433SJohn Marino
3444b87433SJohn Marino The basic algorithm was independently discovered as described in:
35*6ea1f93eSDaniel Fojt "Algorithms for Approximate String Matching", Esko Ukkonen,
36*6ea1f93eSDaniel Fojt Information and Control Vol. 64, 1985, pp. 100-118,
37*6ea1f93eSDaniel Fojt <http://dx.doi.org/10.1016/S0019-9958(85)80046-2>.
3844b87433SJohn Marino
3944b87433SJohn Marino Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE
4044b87433SJohn Marino heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)
4144b87433SJohn Marino at the price of producing suboptimal output for large inputs with
4244b87433SJohn Marino many differences. */
4344b87433SJohn Marino
4444b87433SJohn Marino /* Before including this file, you need to define:
4544b87433SJohn Marino ELEMENT The element type of the vectors being compared.
4644b87433SJohn Marino EQUAL A two-argument macro that tests two elements for
4744b87433SJohn Marino equality.
4844b87433SJohn Marino OFFSET A signed integer type sufficient to hold the
4944b87433SJohn Marino difference between two indices. Usually
50*6ea1f93eSDaniel Fojt something like ptrdiff_t.
5144b87433SJohn Marino EXTRA_CONTEXT_FIELDS Declarations of fields for 'struct context'.
5244b87433SJohn Marino NOTE_DELETE(ctxt, xoff) Record the removal of the object xvec[xoff].
5344b87433SJohn Marino NOTE_INSERT(ctxt, yoff) Record the insertion of the object yvec[yoff].
5444b87433SJohn Marino EARLY_ABORT(ctxt) (Optional) A boolean expression that triggers an
5544b87433SJohn Marino early abort of the computation.
5644b87433SJohn Marino USE_HEURISTIC (Optional) Define if you want to support the
5744b87433SJohn Marino heuristic for large vectors.
5844b87433SJohn Marino It is also possible to use this file with abstract arrays. In this case,
5944b87433SJohn Marino xvec and yvec are not represented in memory. They only exist conceptually.
6044b87433SJohn Marino In this case, the list of defines above is amended as follows:
6144b87433SJohn Marino ELEMENT Undefined.
6244b87433SJohn Marino EQUAL Undefined.
6344b87433SJohn Marino XVECREF_YVECREF_EQUAL(ctxt, xoff, yoff)
6444b87433SJohn Marino A three-argument macro: References xvec[xoff] and
6544b87433SJohn Marino yvec[yoff] and tests these elements for equality.
6644b87433SJohn Marino Before including this file, you also need to include:
6744b87433SJohn Marino #include <limits.h>
6844b87433SJohn Marino #include <stdbool.h>
6944b87433SJohn Marino #include "minmax.h"
7044b87433SJohn Marino */
7144b87433SJohn Marino
7244b87433SJohn Marino /* Maximum value of type OFFSET. */
7344b87433SJohn Marino #define OFFSET_MAX \
7444b87433SJohn Marino ((((OFFSET)1 << (sizeof (OFFSET) * CHAR_BIT - 2)) - 1) * 2 + 1)
7544b87433SJohn Marino
7644b87433SJohn Marino /* Default to no early abort. */
7744b87433SJohn Marino #ifndef EARLY_ABORT
7844b87433SJohn Marino # define EARLY_ABORT(ctxt) false
7944b87433SJohn Marino #endif
8044b87433SJohn Marino
814536c563SJohn Marino /* Use this to suppress gcc's "...may be used before initialized" warnings.
8244b87433SJohn Marino Beware: The Code argument must not contain commas. */
8344b87433SJohn Marino #ifndef IF_LINT
84*6ea1f93eSDaniel Fojt # if defined GCC_LINT || defined lint
8544b87433SJohn Marino # define IF_LINT(Code) Code
8644b87433SJohn Marino # else
8744b87433SJohn Marino # define IF_LINT(Code) /* empty */
8844b87433SJohn Marino # endif
8944b87433SJohn Marino #endif
9044b87433SJohn Marino
9144b87433SJohn Marino /* As above, but when Code must contain one comma. */
9244b87433SJohn Marino #ifndef IF_LINT2
93*6ea1f93eSDaniel Fojt # if defined GCC_LINT || defined lint
9444b87433SJohn Marino # define IF_LINT2(Code1, Code2) Code1, Code2
9544b87433SJohn Marino # else
9644b87433SJohn Marino # define IF_LINT2(Code1, Code2) /* empty */
9744b87433SJohn Marino # endif
9844b87433SJohn Marino #endif
9944b87433SJohn Marino
10044b87433SJohn Marino /*
10144b87433SJohn Marino * Context of comparison operation.
10244b87433SJohn Marino */
10344b87433SJohn Marino struct context
10444b87433SJohn Marino {
10544b87433SJohn Marino #ifdef ELEMENT
10644b87433SJohn Marino /* Vectors being compared. */
10744b87433SJohn Marino ELEMENT const *xvec;
10844b87433SJohn Marino ELEMENT const *yvec;
10944b87433SJohn Marino #endif
11044b87433SJohn Marino
11144b87433SJohn Marino /* Extra fields. */
11244b87433SJohn Marino EXTRA_CONTEXT_FIELDS
11344b87433SJohn Marino
11444b87433SJohn Marino /* Vector, indexed by diagonal, containing 1 + the X coordinate of the point
11544b87433SJohn Marino furthest along the given diagonal in the forward search of the edit
11644b87433SJohn Marino matrix. */
11744b87433SJohn Marino OFFSET *fdiag;
11844b87433SJohn Marino
11944b87433SJohn Marino /* Vector, indexed by diagonal, containing the X coordinate of the point
12044b87433SJohn Marino furthest along the given diagonal in the backward search of the edit
12144b87433SJohn Marino matrix. */
12244b87433SJohn Marino OFFSET *bdiag;
12344b87433SJohn Marino
12444b87433SJohn Marino #ifdef USE_HEURISTIC
125*6ea1f93eSDaniel Fojt /* This corresponds to the diff --speed-large-files flag. With this
126*6ea1f93eSDaniel Fojt heuristic, for vectors with a constant small density of changes,
127*6ea1f93eSDaniel Fojt the algorithm is linear in the vector size. */
12844b87433SJohn Marino bool heuristic;
12944b87433SJohn Marino #endif
13044b87433SJohn Marino
13144b87433SJohn Marino /* Edit scripts longer than this are too expensive to compute. */
13244b87433SJohn Marino OFFSET too_expensive;
13344b87433SJohn Marino
1344536c563SJohn Marino /* Snakes bigger than this are considered "big". */
13544b87433SJohn Marino #define SNAKE_LIMIT 20
13644b87433SJohn Marino };
13744b87433SJohn Marino
13844b87433SJohn Marino struct partition
13944b87433SJohn Marino {
14044b87433SJohn Marino /* Midpoints of this partition. */
14144b87433SJohn Marino OFFSET xmid;
14244b87433SJohn Marino OFFSET ymid;
14344b87433SJohn Marino
14444b87433SJohn Marino /* True if low half will be analyzed minimally. */
14544b87433SJohn Marino bool lo_minimal;
14644b87433SJohn Marino
14744b87433SJohn Marino /* Likewise for high half. */
14844b87433SJohn Marino bool hi_minimal;
14944b87433SJohn Marino };
15044b87433SJohn Marino
15144b87433SJohn Marino
15244b87433SJohn Marino /* Find the midpoint of the shortest edit script for a specified portion
15344b87433SJohn Marino of the two vectors.
15444b87433SJohn Marino
15544b87433SJohn Marino Scan from the beginnings of the vectors, and simultaneously from the ends,
15644b87433SJohn Marino doing a breadth-first search through the space of edit-sequence.
15744b87433SJohn Marino When the two searches meet, we have found the midpoint of the shortest
15844b87433SJohn Marino edit sequence.
15944b87433SJohn Marino
16044b87433SJohn Marino If FIND_MINIMAL is true, find the minimal edit script regardless of
16144b87433SJohn Marino expense. Otherwise, if the search is too expensive, use heuristics to
16244b87433SJohn Marino stop the search and report a suboptimal answer.
16344b87433SJohn Marino
16444b87433SJohn Marino Set PART->(xmid,ymid) to the midpoint (XMID,YMID). The diagonal number
16544b87433SJohn Marino XMID - YMID equals the number of inserted elements minus the number
16644b87433SJohn Marino of deleted elements (counting only elements before the midpoint).
16744b87433SJohn Marino
16844b87433SJohn Marino Set PART->lo_minimal to true iff the minimal edit script for the
16944b87433SJohn Marino left half of the partition is known; similarly for PART->hi_minimal.
17044b87433SJohn Marino
17144b87433SJohn Marino This function assumes that the first elements of the specified portions
17244b87433SJohn Marino of the two vectors do not match, and likewise that the last elements do not
17344b87433SJohn Marino match. The caller must trim matching elements from the beginning and end
17444b87433SJohn Marino of the portions it is going to specify.
17544b87433SJohn Marino
17644b87433SJohn Marino If we return the "wrong" partitions, the worst this can do is cause
17744b87433SJohn Marino suboptimal diff output. It cannot cause incorrect diff output. */
17844b87433SJohn Marino
17944b87433SJohn Marino static void
diag(OFFSET xoff,OFFSET xlim,OFFSET yoff,OFFSET ylim,bool find_minimal,struct partition * part,struct context * ctxt)18044b87433SJohn Marino diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
18144b87433SJohn Marino struct partition *part, struct context *ctxt)
18244b87433SJohn Marino {
18344b87433SJohn Marino OFFSET *const fd = ctxt->fdiag; /* Give the compiler a chance. */
18444b87433SJohn Marino OFFSET *const bd = ctxt->bdiag; /* Additional help for the compiler. */
18544b87433SJohn Marino #ifdef ELEMENT
18644b87433SJohn Marino ELEMENT const *const xv = ctxt->xvec; /* Still more help for the compiler. */
18744b87433SJohn Marino ELEMENT const *const yv = ctxt->yvec; /* And more and more . . . */
18844b87433SJohn Marino #define XREF_YREF_EQUAL(x,y) EQUAL (xv[x], yv[y])
18944b87433SJohn Marino #else
19044b87433SJohn Marino #define XREF_YREF_EQUAL(x,y) XVECREF_YVECREF_EQUAL (ctxt, x, y)
19144b87433SJohn Marino #endif
19244b87433SJohn Marino const OFFSET dmin = xoff - ylim; /* Minimum valid diagonal. */
19344b87433SJohn Marino const OFFSET dmax = xlim - yoff; /* Maximum valid diagonal. */
19444b87433SJohn Marino const OFFSET fmid = xoff - yoff; /* Center diagonal of top-down search. */
19544b87433SJohn Marino const OFFSET bmid = xlim - ylim; /* Center diagonal of bottom-up search. */
19644b87433SJohn Marino OFFSET fmin = fmid;
19744b87433SJohn Marino OFFSET fmax = fmid; /* Limits of top-down search. */
19844b87433SJohn Marino OFFSET bmin = bmid;
19944b87433SJohn Marino OFFSET bmax = bmid; /* Limits of bottom-up search. */
20044b87433SJohn Marino OFFSET c; /* Cost. */
20144b87433SJohn Marino bool odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd
20244b87433SJohn Marino diagonal with respect to the northwest. */
20344b87433SJohn Marino
20444b87433SJohn Marino fd[fmid] = xoff;
20544b87433SJohn Marino bd[bmid] = xlim;
20644b87433SJohn Marino
20744b87433SJohn Marino for (c = 1;; ++c)
20844b87433SJohn Marino {
20944b87433SJohn Marino OFFSET d; /* Active diagonal. */
21044b87433SJohn Marino bool big_snake = false;
21144b87433SJohn Marino
21244b87433SJohn Marino /* Extend the top-down search by an edit step in each diagonal. */
21344b87433SJohn Marino if (fmin > dmin)
21444b87433SJohn Marino fd[--fmin - 1] = -1;
21544b87433SJohn Marino else
21644b87433SJohn Marino ++fmin;
21744b87433SJohn Marino if (fmax < dmax)
21844b87433SJohn Marino fd[++fmax + 1] = -1;
21944b87433SJohn Marino else
22044b87433SJohn Marino --fmax;
22144b87433SJohn Marino for (d = fmax; d >= fmin; d -= 2)
22244b87433SJohn Marino {
22344b87433SJohn Marino OFFSET x;
22444b87433SJohn Marino OFFSET y;
22544b87433SJohn Marino OFFSET tlo = fd[d - 1];
22644b87433SJohn Marino OFFSET thi = fd[d + 1];
22744b87433SJohn Marino OFFSET x0 = tlo < thi ? thi : tlo + 1;
22844b87433SJohn Marino
22944b87433SJohn Marino for (x = x0, y = x0 - d;
23044b87433SJohn Marino x < xlim && y < ylim && XREF_YREF_EQUAL (x, y);
23144b87433SJohn Marino x++, y++)
23244b87433SJohn Marino continue;
23344b87433SJohn Marino if (x - x0 > SNAKE_LIMIT)
23444b87433SJohn Marino big_snake = true;
23544b87433SJohn Marino fd[d] = x;
23644b87433SJohn Marino if (odd && bmin <= d && d <= bmax && bd[d] <= x)
23744b87433SJohn Marino {
23844b87433SJohn Marino part->xmid = x;
23944b87433SJohn Marino part->ymid = y;
24044b87433SJohn Marino part->lo_minimal = part->hi_minimal = true;
24144b87433SJohn Marino return;
24244b87433SJohn Marino }
24344b87433SJohn Marino }
24444b87433SJohn Marino
24544b87433SJohn Marino /* Similarly extend the bottom-up search. */
24644b87433SJohn Marino if (bmin > dmin)
24744b87433SJohn Marino bd[--bmin - 1] = OFFSET_MAX;
24844b87433SJohn Marino else
24944b87433SJohn Marino ++bmin;
25044b87433SJohn Marino if (bmax < dmax)
25144b87433SJohn Marino bd[++bmax + 1] = OFFSET_MAX;
25244b87433SJohn Marino else
25344b87433SJohn Marino --bmax;
25444b87433SJohn Marino for (d = bmax; d >= bmin; d -= 2)
25544b87433SJohn Marino {
25644b87433SJohn Marino OFFSET x;
25744b87433SJohn Marino OFFSET y;
25844b87433SJohn Marino OFFSET tlo = bd[d - 1];
25944b87433SJohn Marino OFFSET thi = bd[d + 1];
26044b87433SJohn Marino OFFSET x0 = tlo < thi ? tlo : thi - 1;
26144b87433SJohn Marino
26244b87433SJohn Marino for (x = x0, y = x0 - d;
26344b87433SJohn Marino xoff < x && yoff < y && XREF_YREF_EQUAL (x - 1, y - 1);
26444b87433SJohn Marino x--, y--)
26544b87433SJohn Marino continue;
26644b87433SJohn Marino if (x0 - x > SNAKE_LIMIT)
26744b87433SJohn Marino big_snake = true;
26844b87433SJohn Marino bd[d] = x;
26944b87433SJohn Marino if (!odd && fmin <= d && d <= fmax && x <= fd[d])
27044b87433SJohn Marino {
27144b87433SJohn Marino part->xmid = x;
27244b87433SJohn Marino part->ymid = y;
27344b87433SJohn Marino part->lo_minimal = part->hi_minimal = true;
27444b87433SJohn Marino return;
27544b87433SJohn Marino }
27644b87433SJohn Marino }
27744b87433SJohn Marino
27844b87433SJohn Marino if (find_minimal)
27944b87433SJohn Marino continue;
28044b87433SJohn Marino
28144b87433SJohn Marino #ifdef USE_HEURISTIC
282*6ea1f93eSDaniel Fojt bool heuristic = ctxt->heuristic;
283*6ea1f93eSDaniel Fojt #else
284*6ea1f93eSDaniel Fojt bool heuristic = false;
285*6ea1f93eSDaniel Fojt #endif
286*6ea1f93eSDaniel Fojt
28744b87433SJohn Marino /* Heuristic: check occasionally for a diagonal that has made lots
28844b87433SJohn Marino of progress compared with the edit distance. If we have any
28944b87433SJohn Marino such, find the one that has made the most progress and return it
29044b87433SJohn Marino as if it had succeeded.
29144b87433SJohn Marino
29244b87433SJohn Marino With this heuristic, for vectors with a constant small density
29344b87433SJohn Marino of changes, the algorithm is linear in the vector size. */
29444b87433SJohn Marino
295*6ea1f93eSDaniel Fojt if (200 < c && big_snake && heuristic)
29644b87433SJohn Marino {
29744b87433SJohn Marino {
29844b87433SJohn Marino OFFSET best = 0;
29944b87433SJohn Marino
30044b87433SJohn Marino for (d = fmax; d >= fmin; d -= 2)
30144b87433SJohn Marino {
30244b87433SJohn Marino OFFSET dd = d - fmid;
30344b87433SJohn Marino OFFSET x = fd[d];
30444b87433SJohn Marino OFFSET y = x - d;
30544b87433SJohn Marino OFFSET v = (x - xoff) * 2 - dd;
30644b87433SJohn Marino
30744b87433SJohn Marino if (v > 12 * (c + (dd < 0 ? -dd : dd)))
30844b87433SJohn Marino {
30944b87433SJohn Marino if (v > best
31044b87433SJohn Marino && xoff + SNAKE_LIMIT <= x && x < xlim
31144b87433SJohn Marino && yoff + SNAKE_LIMIT <= y && y < ylim)
31244b87433SJohn Marino {
31344b87433SJohn Marino /* We have a good enough best diagonal; now insist
31444b87433SJohn Marino that it end with a significant snake. */
31544b87433SJohn Marino int k;
31644b87433SJohn Marino
31744b87433SJohn Marino for (k = 1; XREF_YREF_EQUAL (x - k, y - k); k++)
31844b87433SJohn Marino if (k == SNAKE_LIMIT)
31944b87433SJohn Marino {
32044b87433SJohn Marino best = v;
32144b87433SJohn Marino part->xmid = x;
32244b87433SJohn Marino part->ymid = y;
32344b87433SJohn Marino break;
32444b87433SJohn Marino }
32544b87433SJohn Marino }
32644b87433SJohn Marino }
32744b87433SJohn Marino }
32844b87433SJohn Marino if (best > 0)
32944b87433SJohn Marino {
33044b87433SJohn Marino part->lo_minimal = true;
33144b87433SJohn Marino part->hi_minimal = false;
33244b87433SJohn Marino return;
33344b87433SJohn Marino }
33444b87433SJohn Marino }
33544b87433SJohn Marino
33644b87433SJohn Marino {
33744b87433SJohn Marino OFFSET best = 0;
33844b87433SJohn Marino
33944b87433SJohn Marino for (d = bmax; d >= bmin; d -= 2)
34044b87433SJohn Marino {
34144b87433SJohn Marino OFFSET dd = d - bmid;
34244b87433SJohn Marino OFFSET x = bd[d];
34344b87433SJohn Marino OFFSET y = x - d;
34444b87433SJohn Marino OFFSET v = (xlim - x) * 2 + dd;
34544b87433SJohn Marino
34644b87433SJohn Marino if (v > 12 * (c + (dd < 0 ? -dd : dd)))
34744b87433SJohn Marino {
34844b87433SJohn Marino if (v > best
34944b87433SJohn Marino && xoff < x && x <= xlim - SNAKE_LIMIT
35044b87433SJohn Marino && yoff < y && y <= ylim - SNAKE_LIMIT)
35144b87433SJohn Marino {
35244b87433SJohn Marino /* We have a good enough best diagonal; now insist
35344b87433SJohn Marino that it end with a significant snake. */
35444b87433SJohn Marino int k;
35544b87433SJohn Marino
35644b87433SJohn Marino for (k = 0; XREF_YREF_EQUAL (x + k, y + k); k++)
35744b87433SJohn Marino if (k == SNAKE_LIMIT - 1)
35844b87433SJohn Marino {
35944b87433SJohn Marino best = v;
36044b87433SJohn Marino part->xmid = x;
36144b87433SJohn Marino part->ymid = y;
36244b87433SJohn Marino break;
36344b87433SJohn Marino }
36444b87433SJohn Marino }
36544b87433SJohn Marino }
36644b87433SJohn Marino }
36744b87433SJohn Marino if (best > 0)
36844b87433SJohn Marino {
36944b87433SJohn Marino part->lo_minimal = false;
37044b87433SJohn Marino part->hi_minimal = true;
37144b87433SJohn Marino return;
37244b87433SJohn Marino }
37344b87433SJohn Marino }
37444b87433SJohn Marino }
37544b87433SJohn Marino
37644b87433SJohn Marino /* Heuristic: if we've gone well beyond the call of duty, give up
37744b87433SJohn Marino and report halfway between our best results so far. */
37844b87433SJohn Marino if (c >= ctxt->too_expensive)
37944b87433SJohn Marino {
38044b87433SJohn Marino OFFSET fxybest;
38144b87433SJohn Marino OFFSET fxbest IF_LINT (= 0);
38244b87433SJohn Marino OFFSET bxybest;
38344b87433SJohn Marino OFFSET bxbest IF_LINT (= 0);
38444b87433SJohn Marino
38544b87433SJohn Marino /* Find forward diagonal that maximizes X + Y. */
38644b87433SJohn Marino fxybest = -1;
38744b87433SJohn Marino for (d = fmax; d >= fmin; d -= 2)
38844b87433SJohn Marino {
38944b87433SJohn Marino OFFSET x = MIN (fd[d], xlim);
39044b87433SJohn Marino OFFSET y = x - d;
39144b87433SJohn Marino if (ylim < y)
39244b87433SJohn Marino {
39344b87433SJohn Marino x = ylim + d;
39444b87433SJohn Marino y = ylim;
39544b87433SJohn Marino }
39644b87433SJohn Marino if (fxybest < x + y)
39744b87433SJohn Marino {
39844b87433SJohn Marino fxybest = x + y;
39944b87433SJohn Marino fxbest = x;
40044b87433SJohn Marino }
40144b87433SJohn Marino }
40244b87433SJohn Marino
40344b87433SJohn Marino /* Find backward diagonal that minimizes X + Y. */
40444b87433SJohn Marino bxybest = OFFSET_MAX;
40544b87433SJohn Marino for (d = bmax; d >= bmin; d -= 2)
40644b87433SJohn Marino {
40744b87433SJohn Marino OFFSET x = MAX (xoff, bd[d]);
40844b87433SJohn Marino OFFSET y = x - d;
40944b87433SJohn Marino if (y < yoff)
41044b87433SJohn Marino {
41144b87433SJohn Marino x = yoff + d;
41244b87433SJohn Marino y = yoff;
41344b87433SJohn Marino }
41444b87433SJohn Marino if (x + y < bxybest)
41544b87433SJohn Marino {
41644b87433SJohn Marino bxybest = x + y;
41744b87433SJohn Marino bxbest = x;
41844b87433SJohn Marino }
41944b87433SJohn Marino }
42044b87433SJohn Marino
42144b87433SJohn Marino /* Use the better of the two diagonals. */
42244b87433SJohn Marino if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff))
42344b87433SJohn Marino {
42444b87433SJohn Marino part->xmid = fxbest;
42544b87433SJohn Marino part->ymid = fxybest - fxbest;
42644b87433SJohn Marino part->lo_minimal = true;
42744b87433SJohn Marino part->hi_minimal = false;
42844b87433SJohn Marino }
42944b87433SJohn Marino else
43044b87433SJohn Marino {
43144b87433SJohn Marino part->xmid = bxbest;
43244b87433SJohn Marino part->ymid = bxybest - bxbest;
43344b87433SJohn Marino part->lo_minimal = false;
43444b87433SJohn Marino part->hi_minimal = true;
43544b87433SJohn Marino }
43644b87433SJohn Marino return;
43744b87433SJohn Marino }
43844b87433SJohn Marino }
43944b87433SJohn Marino #undef XREF_YREF_EQUAL
44044b87433SJohn Marino }
44144b87433SJohn Marino
44244b87433SJohn Marino
44344b87433SJohn Marino /* Compare in detail contiguous subsequences of the two vectors
44444b87433SJohn Marino which are known, as a whole, to match each other.
44544b87433SJohn Marino
44644b87433SJohn Marino The subsequence of vector 0 is [XOFF, XLIM) and likewise for vector 1.
44744b87433SJohn Marino
44844b87433SJohn Marino Note that XLIM, YLIM are exclusive bounds. All indices into the vectors
44944b87433SJohn Marino are origin-0.
45044b87433SJohn Marino
45144b87433SJohn Marino If FIND_MINIMAL, find a minimal difference no matter how
45244b87433SJohn Marino expensive it is.
45344b87433SJohn Marino
45444b87433SJohn Marino The results are recorded by invoking NOTE_DELETE and NOTE_INSERT.
45544b87433SJohn Marino
45644b87433SJohn Marino Return false if terminated normally, or true if terminated through early
45744b87433SJohn Marino abort. */
45844b87433SJohn Marino
45944b87433SJohn Marino static bool
compareseq(OFFSET xoff,OFFSET xlim,OFFSET yoff,OFFSET ylim,bool find_minimal,struct context * ctxt)46044b87433SJohn Marino compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
46144b87433SJohn Marino bool find_minimal, struct context *ctxt)
46244b87433SJohn Marino {
46344b87433SJohn Marino #ifdef ELEMENT
46444b87433SJohn Marino ELEMENT const *xv = ctxt->xvec; /* Help the compiler. */
46544b87433SJohn Marino ELEMENT const *yv = ctxt->yvec;
46644b87433SJohn Marino #define XREF_YREF_EQUAL(x,y) EQUAL (xv[x], yv[y])
46744b87433SJohn Marino #else
46844b87433SJohn Marino #define XREF_YREF_EQUAL(x,y) XVECREF_YVECREF_EQUAL (ctxt, x, y)
46944b87433SJohn Marino #endif
47044b87433SJohn Marino
47144b87433SJohn Marino /* Slide down the bottom initial diagonal. */
47244b87433SJohn Marino while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xoff, yoff))
47344b87433SJohn Marino {
47444b87433SJohn Marino xoff++;
47544b87433SJohn Marino yoff++;
47644b87433SJohn Marino }
47744b87433SJohn Marino
47844b87433SJohn Marino /* Slide up the top initial diagonal. */
47944b87433SJohn Marino while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xlim - 1, ylim - 1))
48044b87433SJohn Marino {
48144b87433SJohn Marino xlim--;
48244b87433SJohn Marino ylim--;
48344b87433SJohn Marino }
48444b87433SJohn Marino
48544b87433SJohn Marino /* Handle simple cases. */
48644b87433SJohn Marino if (xoff == xlim)
48744b87433SJohn Marino while (yoff < ylim)
48844b87433SJohn Marino {
48944b87433SJohn Marino NOTE_INSERT (ctxt, yoff);
49044b87433SJohn Marino if (EARLY_ABORT (ctxt))
49144b87433SJohn Marino return true;
49244b87433SJohn Marino yoff++;
49344b87433SJohn Marino }
49444b87433SJohn Marino else if (yoff == ylim)
49544b87433SJohn Marino while (xoff < xlim)
49644b87433SJohn Marino {
49744b87433SJohn Marino NOTE_DELETE (ctxt, xoff);
49844b87433SJohn Marino if (EARLY_ABORT (ctxt))
49944b87433SJohn Marino return true;
50044b87433SJohn Marino xoff++;
50144b87433SJohn Marino }
50244b87433SJohn Marino else
50344b87433SJohn Marino {
50444b87433SJohn Marino struct partition part IF_LINT2 (= { .xmid = 0, .ymid = 0 });
50544b87433SJohn Marino
50644b87433SJohn Marino /* Find a point of correspondence in the middle of the vectors. */
50744b87433SJohn Marino diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
50844b87433SJohn Marino
50944b87433SJohn Marino /* Use the partitions to split this problem into subproblems. */
51044b87433SJohn Marino if (compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt))
51144b87433SJohn Marino return true;
51244b87433SJohn Marino if (compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt))
51344b87433SJohn Marino return true;
51444b87433SJohn Marino }
51544b87433SJohn Marino
51644b87433SJohn Marino return false;
51744b87433SJohn Marino #undef XREF_YREF_EQUAL
51844b87433SJohn Marino }
51944b87433SJohn Marino
52044b87433SJohn Marino #undef ELEMENT
52144b87433SJohn Marino #undef EQUAL
52244b87433SJohn Marino #undef OFFSET
52344b87433SJohn Marino #undef EXTRA_CONTEXT_FIELDS
52444b87433SJohn Marino #undef NOTE_DELETE
52544b87433SJohn Marino #undef NOTE_INSERT
52644b87433SJohn Marino #undef EARLY_ABORT
52744b87433SJohn Marino #undef USE_HEURISTIC
52844b87433SJohn Marino #undef XVECREF_YVECREF_EQUAL
52944b87433SJohn Marino #undef OFFSET_MAX
530