1 /* Myers diff algorithm implementation, invented by Eugene W. Myers [1].
2  * Implementations of both the Myers Divide Et Impera (using linear space)
3  * and the canonical Myers algorithm (using quadratic space). */
4 /*
5  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
6  *
7  * Permission to use, copy, modify, and distribute this software for any
8  * purpose with or without fee is hereby granted, provided that the above
9  * copyright notice and this permission notice appear in all copies.
10  *
11  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18  */
19 
20 #include <inttypes.h>
21 #include <stdbool.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <stdio.h>
25 #include <errno.h>
26 
27 #include <arraylist.h>
28 #include <diff_main.h>
29 
30 #include "diff_internal.h"
31 #include "diff_debug.h"
32 
33 /* Myers' diff algorithm [1] is nicely explained in [2].
34  * [1] http://www.xmailserver.org/diff2.pdf
35  * [2] https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ ff.
36  *
37  * Myers approaches finding the smallest diff as a graph problem.
38  * The crux is that the original algorithm requires quadratic amount of memory:
39  * both sides' lengths added, and that squared. So if we're diffing lines of
40  * text, two files with 1000 lines each would blow up to a matrix of about
41  * 2000 * 2000 ints of state, about 16 Mb of RAM to figure out 2 kb of text.
42  * The solution is using Myers' "divide and conquer" extension algorithm, which
43  * does the original traversal from both ends of the files to reach a middle
44  * where these "snakes" touch, hence does not need to backtrace the traversal,
45  * and so gets away with only keeping a single column of that huge state matrix
46  * in memory.
47  */
48 
49 struct diff_box {
50 	unsigned int left_start;
51 	unsigned int left_end;
52 	unsigned int right_start;
53 	unsigned int right_end;
54 };
55 
56 /* If the two contents of a file are A B C D E and X B C Y,
57  * the Myers diff graph looks like:
58  *
59  *   k0  k1
60  *    \   \
61  * k-1     0 1 2 3 4 5
62  *   \      A B C D E
63  *     0   o-o-o-o-o-o
64  *      X  | | | | | |
65  *     1   o-o-o-o-o-o
66  *      B  | |\| | | |
67  *     2   o-o-o-o-o-o
68  *      C  | | |\| | |
69  *     3   o-o-o-o-o-o
70  *      Y  | | | | | |\
71  *     4   o-o-o-o-o-o c1
72  *                  \ \
73  *                 c-1 c0
74  *
75  * Moving right means delete an atom from the left-hand-side,
76  * Moving down means add an atom from the right-hand-side.
77  * Diagonals indicate identical atoms on both sides, the challenge is to use as
78  * many diagonals as possible.
79  *
80  * The original Myers algorithm walks all the way from the top left to the
81  * bottom right, remembers all steps, and then backtraces to find the shortest
82  * path. However, that requires keeping the entire graph in memory, which needs
83  * quadratic space.
84  *
85  * Myers adds a variant that uses linear space -- note, not linear time, only
86  * linear space: walk forward and backward, find a meeting point in the middle,
87  * and recurse on the two separate sections. This is called "divide and
88  * conquer".
89  *
90  * d: the step number, starting with 0, a.k.a. the distance from the starting
91  *    point.
92  * k: relative index in the state array for the forward scan, indicating on
93  *    which diagonal through the diff graph we currently are.
94  * c: relative index in the state array for the backward scan, indicating the
95  *    diagonal number from the bottom up.
96  *
97  * The "divide and conquer" traversal through the Myers graph looks like this:
98  *
99  *      | d=   0   1   2   3      2   1   0
100  *  ----+--------------------------------------------
101  *  k=  |                                      c=
102  *   4  |                                       3
103  *      |
104  *   3  |                 3,0    5,2            2
105  *      |                /          \
106  *   2  |             2,0            5,3        1
107  *      |            /                 \
108  *   1  |         1,0     4,3 >= 4,3    5,4<--  0
109  *      |        /       /          \  /
110  *   0  |  -->0,0     3,3            4,4       -1
111  *      |        \   /              /
112  *  -1  |         0,1     1,2    3,4           -2
113  *      |            \   /
114  *  -2  |             0,2                      -3
115  *      |                \
116  *      |                 0,3
117  *      |  forward->                 <-backward
118  *
119  * x,y pairs here are the coordinates in the Myers graph:
120  * x = atom index in left-side source, y = atom index in the right-side source.
121  *
122  * Only one forward column and one backward column are kept in mem, each need at
123  * most left.len + 1 + right.len items.  Note that each d step occupies either
124  * the even or the odd items of a column: if e.g. the previous column is in the
125  * odd items, the next column is formed in the even items, without overwriting
126  * the previous column's results.
127  *
128  * Also note that from the diagonal index k and the x coordinate, the y
129  * coordinate can be derived:
130  *    y = x - k
131  * Hence the state array only needs to keep the x coordinate, i.e. the position
132  * in the left-hand file, and the y coordinate, i.e. position in the right-hand
133  * file, is derived from the index in the state array.
134  *
135  * The two traces meet at 4,3, the first step (here found in the forward
136  * traversal) where a forward position is on or past a backward traced position
137  * on the same diagonal.
138  *
139  * This divides the problem space into:
140  *
141  *         0 1 2 3 4 5
142  *          A B C D E
143  *     0   o-o-o-o-o
144  *      X  | | | | |
145  *     1   o-o-o-o-o
146  *      B  | |\| | |
147  *     2   o-o-o-o-o
148  *      C  | | |\| |
149  *     3   o-o-o-o-*-o   *: forward and backward meet here
150  *      Y          | |
151  *     4           o-o
152  *
153  * Doing the same on each section lead to:
154  *
155  *         0 1 2 3 4 5
156  *          A B C D E
157  *     0   o-o
158  *      X  | |
159  *     1   o-b    b: backward d=1 first reaches here (sliding up the snake)
160  *      B     \   f: then forward d=2 reaches here (sliding down the snake)
161  *     2       o     As result, the box from b to f is found to be identical;
162  *      C       \    leaving a top box from 0,0 to 1,1 and a bottom trivial
163  *     3         f-o tail 3,3 to 4,3.
164  *
165  *     3           o-*
166  *      Y            |
167  *     4             o   *: forward and backward meet here
168  *
169  * and solving the last top left box gives:
170  *
171  *         0 1 2 3 4 5
172  *          A B C D E           -A
173  *     0   o-o                  +X
174  *      X    |                   B
175  *     1     o                   C
176  *      B     \                 -D
177  *     2       o                -E
178  *      C       \               +Y
179  *     3         o-o-o
180  *      Y            |
181  *     4             o
182  *
183  */
184 
185 #define xk_to_y(X, K) ((X) - (K))
186 #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
187 #define k_to_c(K, DELTA) ((K) + (DELTA))
188 #define c_to_k(C, DELTA) ((C) - (DELTA))
189 
190 /* Do one forwards step in the "divide and conquer" graph traversal.
191  * left: the left side to diff.
192  * right: the right side to diff against.
193  * kd_forward: the traversal state for forwards traversal, modified by this
194  *             function.
195  *             This is carried over between invocations with increasing d.
196  *             kd_forward points at the center of the state array, allowing
197  *             negative indexes.
198  * kd_backward: the traversal state for backwards traversal, to find a meeting
199  *              point.
200  *              Since forwards is done first, kd_backward will be valid for d -
201  *              1, not d.
202  *              kd_backward points at the center of the state array, allowing
203  *              negative indexes.
204  * d: Step or distance counter, indicating for what value of d the kd_forward
205  *    should be populated.
206  *    For d == 0, kd_forward[0] is initialized, i.e. the first invocation should
207  *    be for d == 0.
208  * meeting_snake: resulting meeting point, if any.
209  * Return true when a meeting point has been identified.
210  */
211 static int
212 diff_divide_myers_forward(bool *found_midpoint,
213 			  struct diff_data *left, struct diff_data *right,
214 			  int *kd_forward, int *kd_backward, int d,
215 			  struct diff_box *meeting_snake)
216 {
217 	int delta = (int)right->atoms.len - (int)left->atoms.len;
218 	int k;
219 	int x;
220 	int prev_x;
221 	int prev_y;
222 	int x_before_slide;
223 	*found_midpoint = false;
224 
225 	debug("-- %s d=%d\n", __func__, d);
226 
227 	for (k = d; k >= -d; k -= 2) {
228 		if (k < -(int)right->atoms.len || k > (int)left->atoms.len) {
229 			/* This diagonal is completely outside of the Myers
230 			 * graph, don't calculate it. */
231 			if (k < -(int)right->atoms.len)
232 				debug(" %d k < -(int)right->atoms.len %d\n", k,
233 				      -(int)right->atoms.len);
234 			else
235 				debug(" %d k > left->atoms.len %d\n", k,
236 				      left->atoms.len);
237 			if (k < 0) {
238 				/* We are traversing negatively, and already
239 				 * below the entire graph, nothing will come of
240 				 * this. */
241 				debug(" break\n");
242 				break;
243 			}
244 			debug(" continue\n");
245 			continue;
246 		}
247 		debug("- k = %d\n", k);
248 		if (d == 0) {
249 			/* This is the initializing step. There is no prev_k
250 			 * yet, get the initial x from the top left of the Myers
251 			 * graph. */
252 			x = 0;
253 			prev_x = x;
254 			prev_y = xk_to_y(x, k);
255 		}
256 		/* Favoring "-" lines first means favoring moving rightwards in
257 		 * the Myers graph.
258 		 * For this, all k should derive from k - 1, only the bottom
259 		 * most k derive from k + 1:
260 		 *
261 		 *      | d=   0   1   2
262 		 *  ----+----------------
263 		 *  k=  |
264 		 *   2  |             2,0 <-- from prev_k = 2 - 1 = 1
265 		 *      |            /
266 		 *   1  |         1,0
267 		 *      |        /
268 		 *   0  |  -->0,0     3,3
269 		 *      |       \\   /
270 		 *  -1  |         0,1 <-- bottom most for d=1 from
271 		 *      |           \\    prev_k = -1 + 1 = 0
272 		 *  -2  |             0,2 <-- bottom most for d=2 from
273 		 *                            prev_k = -2 + 1 = -1
274 		 *
275 		 * Except when a k + 1 from a previous run already means a
276 		 * further advancement in the graph.
277 		 * If k == d, there is no k + 1 and k - 1 is the only option.
278 		 * If k < d, use k + 1 in case that yields a larger x. Also use
279 		 * k + 1 if k - 1 is outside the graph.
280 		 */
281 		else if (k > -d
282 			 && (k == d
283 			     || (k - 1 >= -(int)right->atoms.len
284 				 && kd_forward[k - 1] >= kd_forward[k + 1]))) {
285 			/* Advance from k - 1.
286 			 * From position prev_k, step to the right in the Myers
287 			 * graph: x += 1.
288 			 */
289 			int prev_k = k - 1;
290 			prev_x = kd_forward[prev_k];
291 			prev_y = xk_to_y(prev_x, prev_k);
292 			x = prev_x + 1;
293 		} else {
294 			/* The bottom most one.
295 			 * From position prev_k, step to the bottom in the Myers
296 			 * graph: y += 1.
297 			 * Incrementing y is achieved by decrementing k while
298 			 * keeping the same x.
299 			 * (since we're deriving y from y = x - k).
300 			 */
301 			int prev_k = k + 1;
302 			prev_x = kd_forward[prev_k];
303 			prev_y = xk_to_y(prev_x, prev_k);
304 			x = prev_x;
305 		}
306 
307 		x_before_slide = x;
308 		/* Slide down any snake that we might find here. */
309 		while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len) {
310 			bool same;
311 			int r = diff_atom_same(&same,
312 					       &left->atoms.head[x],
313 					       &right->atoms.head[
314 						xk_to_y(x, k)]);
315 			if (r)
316 				return r;
317 			if (!same)
318 				break;
319 			x++;
320 		}
321 		kd_forward[k] = x;
322 		if (x_before_slide != x) {
323 			debug("  down %d similar lines\n", x - x_before_slide);
324 		}
325 
326 #if DEBUG
327 		{
328 			int fi;
329 			for (fi = d; fi >= k; fi--) {
330 				debug("kd_forward[%d] = (%d, %d)\n", fi,
331 				      kd_forward[fi], kd_forward[fi] - fi);
332 			}
333 		}
334 #endif
335 
336 		if (x < 0 || x > left->atoms.len
337 		    || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len)
338 			continue;
339 
340 		/* Figured out a new forwards traversal, see if this has gone
341 		 * onto or even past a preceding backwards traversal.
342 		 *
343 		 * If the delta in length is odd, then d and backwards_d hit the
344 		 * same state indexes:
345 		 *      | d=   0   1   2      1   0
346 		 *  ----+----------------    ----------------
347 		 *  k=  |                              c=
348 		 *   4  |                               3
349 		 *      |
350 		 *   3  |                               2
351 		 *      |                same
352 		 *   2  |             2,0====5,3        1
353 		 *      |            /          \
354 		 *   1  |         1,0            5,4<-- 0
355 		 *      |        /              /
356 		 *   0  |  -->0,0     3,3====4,4       -1
357 		 *      |        \   /
358 		 *  -1  |         0,1                  -2
359 		 *      |            \
360 		 *  -2  |             0,2              -3
361 		 *      |
362 		 *
363 		 * If the delta is even, they end up off-by-one, i.e. on
364 		 * different diagonals:
365 		 *
366 		 *      | d=   0   1   2    1   0
367 		 *  ----+----------------  ----------------
368 		 *      |                            c=
369 		 *   3  |                             3
370 		 *      |
371 		 *   2  |             2,0 off         2
372 		 *      |            /   \\
373 		 *   1  |         1,0      4,3        1
374 		 *      |        /       //   \
375 		 *   0  |  -->0,0     3,3      4,4<-- 0
376 		 *      |        \   /        /
377 		 *  -1  |         0,1      3,4       -1
378 		 *      |            \   //
379 		 *  -2  |             0,2            -2
380 		 *      |
381 		 *
382 		 * So in the forward path, we can only match up diagonals when
383 		 * the delta is odd.
384 		 */
385 		if ((delta & 1) == 0)
386 			continue;
387 		 /* Forwards is done first, so the backwards one was still at
388 		  * d - 1. Can't do this for d == 0. */
389 		int backwards_d = d - 1;
390 		if (backwards_d < 0)
391 			continue;
392 
393 		debug("backwards_d = %d\n", backwards_d);
394 
395 		/* If both sides have the same length, forward and backward
396 		 * start on the same diagonal, meaning the backwards state index
397 		 * c == k.
398 		 * As soon as the lengths are not the same, the backwards
399 		 * traversal starts on a different diagonal, and c = k shifted
400 		 * by the difference in length.
401 		 */
402 		int c = k_to_c(k, delta);
403 
404 		/* When the file sizes are very different, the traversal trees
405 		 * start on far distant diagonals.
406 		 * They don't necessarily meet straight on. See whether this
407 		 * forward value is on a diagonal that is also valid in
408 		 * kd_backward[], and match them if so. */
409 		if (c >= -backwards_d && c <= backwards_d) {
410 			/* Current k is on a diagonal that exists in
411 			 * kd_backward[]. If the two x positions have met or
412 			 * passed (forward walked onto or past backward), then
413 			 * we've found a midpoint / a mid-box.
414 			 *
415 			 * When forwards and backwards traversals meet, the
416 			 * endpoints of the mid-snake are not the two points in
417 			 * kd_forward and kd_backward, but rather the section
418 			 * that was slid (if any) of the current
419 			 * forward/backward traversal only.
420 			 *
421 			 * For example:
422 			 *
423 			 *   o
424 			 *    \
425 			 *     o
426 			 *      \
427 			 *       o
428 			 *        \
429 			 *         o
430 			 *          \
431 			 *       X o o
432 			 *       | | |
433 			 *     o-o-o o
434 			 *          \|
435 			 *           M
436 			 *            \
437 			 *             o
438 			 *              \
439 			 *               A o
440 			 *               | |
441 			 *             o-o-o
442 			 *
443 			 * The forward traversal reached M from the top and slid
444 			 * downwards to A.  The backward traversal already
445 			 * reached X, which is not a straight line from M
446 			 * anymore, so picking a mid-snake from M to X would
447 			 * yield a mistake.
448 			 *
449 			 * The correct mid-snake is between M and A. M is where
450 			 * the forward traversal hit the diagonal that the
451 			 * backward traversal has already passed, and A is what
452 			 * it reaches when sliding down identical lines.
453 			 */
454 			int backward_x = kd_backward[c];
455 			debug("Compare:  k=%d c=%d  is (%d,%d) >= (%d,%d)?\n",
456 			      k, c, x, xk_to_y(x, k), backward_x,
457 			      xc_to_y(backward_x, c, delta));
458 			if (x >= backward_x) {
459 				if (x_before_slide != x) {
460 					/* met after sliding up a mid-snake */
461 					*meeting_snake = (struct diff_box){
462 						.left_start = x_before_slide,
463 						.left_end = x,
464 						.right_start = xc_to_y(x_before_slide,
465 								       c, delta),
466 						.right_end = xk_to_y(x, k),
467 					};
468 				} else {
469 					/* met after a side step, non-identical
470 					 * line. Mark that as box divider
471 					 * instead. This makes sure that
472 					 * myers_divide never returns the same
473 					 * box that came as input, avoiding
474 					 * "infinite" looping. */
475 					*meeting_snake = (struct diff_box){
476 						.left_start = prev_x,
477 						.left_end = x,
478 						.right_start = prev_y,
479 						.right_end = xk_to_y(x, k),
480 					};
481 				}
482 				debug("HIT x=(%u,%u) - y=(%u,%u)\n",
483 				      meeting_snake->left_start,
484 				      meeting_snake->right_start,
485 				      meeting_snake->left_end,
486 				      meeting_snake->right_end);
487 				debug_dump_myers_graph(left, right, NULL,
488 						       kd_forward, d,
489 						       kd_backward, d-1);
490 				*found_midpoint = true;
491 				return 0;
492 			}
493 		}
494 	}
495 
496 	debug_dump_myers_graph(left, right, NULL, kd_forward, d,
497 			       kd_backward, d-1);
498 	return 0;
499 }
500 
501 /* Do one backwards step in the "divide and conquer" graph traversal.
502  * left: the left side to diff.
503  * right: the right side to diff against.
504  * kd_forward: the traversal state for forwards traversal, to find a meeting
505  *             point.
506  *             Since forwards is done first, after this, both kd_forward and
507  *             kd_backward will be valid for d.
508  *             kd_forward points at the center of the state array, allowing
509  *             negative indexes.
510  * kd_backward: the traversal state for backwards traversal, to find a meeting
511  *              point.
512  *              This is carried over between invocations with increasing d.
513  *              kd_backward points at the center of the state array, allowing
514  *              negative indexes.
515  * d: Step or distance counter, indicating for what value of d the kd_backward
516  *    should be populated.
517  *    Before the first invocation, kd_backward[0] shall point at the bottom
518  *    right of the Myers graph (left.len, right.len).
519  *    The first invocation will be for d == 1.
520  * meeting_snake: resulting meeting point, if any.
521  * Return true when a meeting point has been identified.
522  */
523 static int
524 diff_divide_myers_backward(bool *found_midpoint,
525 			   struct diff_data *left, struct diff_data *right,
526 			   int *kd_forward, int *kd_backward, int d,
527 			   struct diff_box *meeting_snake)
528 {
529 	int delta = (int)right->atoms.len - (int)left->atoms.len;
530 	int c;
531 	int x;
532 	int prev_x;
533 	int prev_y;
534 	int x_before_slide;
535 
536 	*found_midpoint = false;
537 
538 	debug("-- %s d=%d\n", __func__, d);
539 
540 	for (c = d; c >= -d; c -= 2) {
541 		if (c < -(int)left->atoms.len || c > (int)right->atoms.len) {
542 			/* This diagonal is completely outside of the Myers
543 			 * graph, don't calculate it. */
544 			if (c < -(int)left->atoms.len)
545 				debug(" %d c < -(int)left->atoms.len %d\n", c,
546 				      -(int)left->atoms.len);
547 			else
548 				debug(" %d c > right->atoms.len %d\n", c,
549 				      right->atoms.len);
550 			if (c < 0) {
551 				/* We are traversing negatively, and already
552 				 * below the entire graph, nothing will come of
553 				 * this. */
554 				debug(" break\n");
555 				break;
556 			}
557 			debug(" continue\n");
558 			continue;
559 		}
560 		debug("- c = %d\n", c);
561 		if (d == 0) {
562 			/* This is the initializing step. There is no prev_c
563 			 * yet, get the initial x from the bottom right of the
564 			 * Myers graph. */
565 			x = left->atoms.len;
566 			prev_x = x;
567 			prev_y = xc_to_y(x, c, delta);
568 		}
569 		/* Favoring "-" lines first means favoring moving rightwards in
570 		 * the Myers graph.
571 		 * For this, all c should derive from c - 1, only the bottom
572 		 * most c derive from c + 1:
573 		 *
574 		 *                                  2   1   0
575 		 *  ---------------------------------------------------
576 		 *                                               c=
577 		 *                                                3
578 		 *
579 		 *         from prev_c = c - 1 --> 5,2            2
580 		 *                                    \
581 		 *                                     5,3        1
582 		 *                                        \
583 		 *                                 4,3     5,4<-- 0
584 		 *                                    \   /
585 		 *  bottom most for d=1 from c + 1 --> 4,4       -1
586 		 *                                    /
587 		 *         bottom most for d=2 --> 3,4           -2
588 		 *
589 		 * Except when a c + 1 from a previous run already means a
590 		 * further advancement in the graph.
591 		 * If c == d, there is no c + 1 and c - 1 is the only option.
592 		 * If c < d, use c + 1 in case that yields a larger x.
593 		 * Also use c + 1 if c - 1 is outside the graph.
594 		 */
595 		else if (c > -d && (c == d
596 				    || (c - 1 >= -(int)right->atoms.len
597 					&& kd_backward[c - 1] <= kd_backward[c + 1]))) {
598 			/* A top one.
599 			 * From position prev_c, step upwards in the Myers
600 			 * graph: y -= 1.
601 			 * Decrementing y is achieved by incrementing c while
602 			 * keeping the same x. (since we're deriving y from
603 			 * y = x - c + delta).
604 			 */
605 			int prev_c = c - 1;
606 			prev_x = kd_backward[prev_c];
607 			prev_y = xc_to_y(prev_x, prev_c, delta);
608 			x = prev_x;
609 		} else {
610 			/* The bottom most one.
611 			 * From position prev_c, step to the left in the Myers
612 			 * graph: x -= 1.
613 			 */
614 			int prev_c = c + 1;
615 			prev_x = kd_backward[prev_c];
616 			prev_y = xc_to_y(prev_x, prev_c, delta);
617 			x = prev_x - 1;
618 		}
619 
620 		/* Slide up any snake that we might find here (sections of
621 		 * identical lines on both sides). */
622 		debug("c=%d x-1=%d Yb-1=%d-1=%d\n", c, x-1, xc_to_y(x, c,
623 								    delta),
624 		      xc_to_y(x, c, delta)-1);
625 		if (x > 0) {
626 			debug("  l=");
627 			debug_dump_atom(left, right, &left->atoms.head[x-1]);
628 		}
629 		if (xc_to_y(x, c, delta) > 0) {
630 			debug("  r=");
631 			debug_dump_atom(right, left,
632 				&right->atoms.head[xc_to_y(x, c, delta)-1]);
633 		}
634 		x_before_slide = x;
635 		while (x > 0 && xc_to_y(x, c, delta) > 0) {
636 			bool same;
637 			int r = diff_atom_same(&same,
638 					       &left->atoms.head[x-1],
639 					       &right->atoms.head[
640 						xc_to_y(x, c, delta)-1]);
641 			if (r)
642 				return r;
643 			if (!same)
644 				break;
645 			x--;
646 		}
647 		kd_backward[c] = x;
648 		if (x_before_slide != x) {
649 			debug("  up %d similar lines\n", x_before_slide - x);
650 		}
651 
652 		if (DEBUG) {
653 			int fi;
654 			for (fi = d; fi >= c; fi--) {
655 				debug("kd_backward[%d] = (%d, %d)\n",
656 				      fi,
657 				      kd_backward[fi],
658 				      kd_backward[fi] - fi + delta);
659 			}
660 		}
661 
662 		if (x < 0 || x > left->atoms.len
663 		    || xc_to_y(x, c, delta) < 0
664 		    || xc_to_y(x, c, delta) > right->atoms.len)
665 			continue;
666 
667 		/* Figured out a new backwards traversal, see if this has gone
668 		 * onto or even past a preceding forwards traversal.
669 		 *
670 		 * If the delta in length is even, then d and backwards_d hit
671 		 * the same state indexes -- note how this is different from in
672 		 * the forwards traversal, because now both d are the same:
673 		 *
674 		 *      | d=   0   1   2      2   1   0
675 		 *  ----+----------------    --------------------
676 		 *  k=  |                                  c=
677 		 *   4  |
678 		 *      |
679 		 *   3  |                                   3
680 		 *      |                same
681 		 *   2  |             2,0====5,2            2
682 		 *      |            /          \
683 		 *   1  |         1,0            5,3        1
684 		 *      |        /              /  \
685 		 *   0  |  -->0,0     3,3====4,3    5,4<--  0
686 		 *      |        \   /             /
687 		 *  -1  |         0,1            4,4       -1
688 		 *      |            \
689 		 *  -2  |             0,2                  -2
690 		 *      |
691 		 *                                      -3
692 		 * If the delta is odd, they end up off-by-one, i.e. on
693 		 * different diagonals.
694 		 * So in the backward path, we can only match up diagonals when
695 		 * the delta is even.
696 		 */
697 		if ((delta & 1) != 0)
698 			continue;
699 		/* Forwards was done first, now both d are the same. */
700 		int forwards_d = d;
701 
702 		/* As soon as the lengths are not the same, the
703 		 * backwards traversal starts on a different diagonal,
704 		 * and c = k shifted by the difference in length.
705 		 */
706 		int k = c_to_k(c, delta);
707 
708 		/* When the file sizes are very different, the traversal trees
709 		 * start on far distant diagonals.
710 		 * They don't necessarily meet straight on. See whether this
711 		 * backward value is also on a valid diagonal in kd_forward[],
712 		 * and match them if so. */
713 		if (k >= -forwards_d && k <= forwards_d) {
714 			/* Current c is on a diagonal that exists in
715 			 * kd_forward[]. If the two x positions have met or
716 			 * passed (backward walked onto or past forward), then
717 			 * we've found a midpoint / a mid-box.
718 			 *
719 			 * When forwards and backwards traversals meet, the
720 			 * endpoints of the mid-snake are not the two points in
721 			 * kd_forward and kd_backward, but rather the section
722 			 * that was slid (if any) of the current
723 			 * forward/backward traversal only.
724 			 *
725 			 * For example:
726 			 *
727 			 *   o-o-o
728 			 *   | |
729 			 *   o A
730 			 *   |  \
731 			 *   o   o
732 			 *        \
733 			 *         M
734 			 *         |\
735 			 *         o o-o-o
736 			 *         | | |
737 			 *         o o X
738 			 *          \
739 			 *           o
740 			 *            \
741 			 *             o
742 			 *              \
743 			 *               o
744 			 *
745 			 * The backward traversal reached M from the bottom and
746 			 * slid upwards.  The forward traversal already reached
747 			 * X, which is not a straight line from M anymore, so
748 			 * picking a mid-snake from M to X would yield a
749 			 * mistake.
750 			 *
751 			 * The correct mid-snake is between M and A. M is where
752 			 * the backward traversal hit the diagonal that the
753 			 * forwards traversal has already passed, and A is what
754 			 * it reaches when sliding up identical lines.
755 			 */
756 
757 			int forward_x = kd_forward[k];
758 			debug("Compare:  k=%d c=%d  is (%d,%d) >= (%d,%d)?\n",
759 			      k, c, forward_x, xk_to_y(forward_x, k),
760 			      x, xc_to_y(x, c, delta));
761 			if (forward_x >= x) {
762 				if (x_before_slide != x) {
763 					/* met after sliding down a mid-snake */
764 					*meeting_snake = (struct diff_box){
765 						.left_start = x,
766 						.left_end = x_before_slide,
767 						.right_start = xc_to_y(x, c, delta),
768 						.right_end = xk_to_y(x_before_slide, k),
769 					};
770 				} else {
771 					/* met after a side step, non-identical
772 					 * line. Mark that as box divider
773 					 * instead. This makes sure that
774 					 * myers_divide never returns the same
775 					 * box that came as input, avoiding
776 					 * "infinite" looping. */
777 					*meeting_snake = (struct diff_box){
778 						.left_start = x,
779 						.left_end = prev_x,
780 						.right_start = xc_to_y(x, c, delta),
781 						.right_end = prev_y,
782 					};
783 				}
784 				debug("HIT x=%u,%u - y=%u,%u\n",
785 				      meeting_snake->left_start,
786 				      meeting_snake->right_start,
787 				      meeting_snake->left_end,
788 				      meeting_snake->right_end);
789 				debug_dump_myers_graph(left, right, NULL,
790 						       kd_forward, d,
791 						       kd_backward, d);
792 				*found_midpoint = true;
793 				return 0;
794 			}
795 		}
796 	}
797 	debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward,
798 			       d);
799 	return 0;
800 }
801 
802 /* Integer square root approximation */
803 static int
804 shift_sqrt(int val)
805 {
806 	int i;
807         for (i = 1; val > 0; val >>= 2)
808 		i <<= 1;
809         return i;
810 }
811 
812 /* Myers "Divide et Impera": tracing forwards from the start and backwards from
813  * the end to find a midpoint that divides the problem into smaller chunks.
814  * Requires only linear amounts of memory. */
815 int
816 diff_algo_myers_divide(const struct diff_algo_config *algo_config,
817 		       struct diff_state *state)
818 {
819 	int rc = ENOMEM;
820 	struct diff_data *left = &state->left;
821 	struct diff_data *right = &state->right;
822 	int *kd_buf;
823 
824 	debug("\n** %s\n", __func__);
825 	debug("left:\n");
826 	debug_dump(left);
827 	debug("right:\n");
828 	debug_dump(right);
829 	debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
830 
831 	/* Allocate two columns of a Myers graph, one for the forward and one
832 	 * for the backward traversal. */
833 	unsigned int max = left->atoms.len + right->atoms.len;
834 	size_t kd_len = max + 1;
835 	size_t kd_buf_size = kd_len << 1;
836 
837 	if (state->kd_buf_size < kd_buf_size) {
838 		kd_buf = reallocarray(state->kd_buf, kd_buf_size,
839 		    sizeof(int));
840 		if (!kd_buf)
841 			return ENOMEM;
842 		state->kd_buf = kd_buf;
843 		state->kd_buf_size = kd_buf_size;
844 	} else
845 		kd_buf = state->kd_buf;
846 	int i;
847 	for (i = 0; i < kd_buf_size; i++)
848 		kd_buf[i] = -1;
849 	int *kd_forward = kd_buf;
850 	int *kd_backward = kd_buf + kd_len;
851 	int max_effort = shift_sqrt(max/2);
852 
853 	/* The 'k' axis in Myers spans positive and negative indexes, so point
854 	 * the kd to the middle.
855 	 * It is then possible to index from -max/2 .. max/2. */
856 	kd_forward += max/2;
857 	kd_backward += max/2;
858 
859 	int d;
860 	struct diff_box mid_snake = {};
861 	bool found_midpoint = false;
862 	for (d = 0; d <= (max/2); d++) {
863 		int r;
864 		debug("-- d=%d\n", d);
865 		r = diff_divide_myers_forward(&found_midpoint, left, right,
866 					      kd_forward, kd_backward, d,
867 					      &mid_snake);
868 		if (r)
869 			return r;
870 		if (found_midpoint)
871 			break;
872 		r = diff_divide_myers_backward(&found_midpoint, left, right,
873 					       kd_forward, kd_backward, d,
874 					       &mid_snake);
875 		if (r)
876 			return r;
877 		if (found_midpoint)
878 			break;
879 
880 		/* Limit the effort spent looking for a mid snake. If files have
881 		 * very few lines in common, the effort spent to find nice mid
882 		 * snakes is just not worth it, the diff result will still be
883 		 * essentially minus everything on the left, plus everything on
884 		 * the right, with a few useless matches here and there. */
885 		if (d > max_effort) {
886 			/* pick the furthest reaching point from
887 			 * kd_forward and kd_backward, and use that as a
888 			 * midpoint, to not step into another diff algo
889 			 * recursion with unchanged box. */
890 			int delta = (int)right->atoms.len - (int)left->atoms.len;
891 			int x = 0;
892 			int y;
893 			int i;
894 			int best_forward_i = 0;
895 			int best_forward_distance = 0;
896 			int best_backward_i = 0;
897 			int best_backward_distance = 0;
898 			int distance;
899 			int best_forward_x;
900 			int best_forward_y;
901 			int best_backward_x;
902 			int best_backward_y;
903 
904 			debug("~~~ HIT d = %d > max_effort = %d\n", d, max_effort);
905 			debug_dump_myers_graph(left, right, NULL,
906 					       kd_forward, d,
907 					       kd_backward, d);
908 
909 			for (i = d; i >= -d; i -= 2) {
910 				if (i >= -(int)right->atoms.len && i <= (int)left->atoms.len) {
911 					x = kd_forward[i];
912 					y = xk_to_y(x, i);
913 					distance = x + y;
914 					if (distance > best_forward_distance) {
915 						best_forward_distance = distance;
916 						best_forward_i = i;
917 					}
918 				}
919 
920 				if (i >= -(int)left->atoms.len && i <= (int)right->atoms.len) {
921 					x = kd_backward[i];
922 					y = xc_to_y(x, i, delta);
923 					distance = (right->atoms.len - x)
924 						+ (left->atoms.len - y);
925 					if (distance >= best_backward_distance) {
926 						best_backward_distance = distance;
927 						best_backward_i = i;
928 					}
929 				}
930 			}
931 
932 			/* The myers-divide didn't meet in the middle. We just
933 			 * figured out the places where the forward path
934 			 * advanced the most, and the backward path advanced the
935 			 * most. Just divide at whichever one of those two is better.
936 			 *
937 			 *   o-o
938 			 *     |
939 			 *     o
940 			 *      \
941 			 *       o
942 			 *        \
943 			 *         F <-- cut here
944 			 *
945 			 *
946 			 *
947 			 *           or here --> B
948 			 *                        \
949 			 *                         o
950 			 *                          \
951 			 *                           o
952 			 *                           |
953 			 *                           o-o
954 			 */
955 			best_forward_x = kd_forward[best_forward_i];
956 			best_forward_y = xk_to_y(best_forward_x, best_forward_i);
957 			best_backward_x = kd_backward[best_backward_i];
958 			best_backward_y = xc_to_y(best_backward_x, best_backward_i, delta);
959 
960 			if (best_forward_distance >= best_backward_distance) {
961 				x = best_forward_x;
962 				y = best_forward_y;
963 			} else {
964 				x = best_backward_x;
965 				y = best_backward_y;
966 			}
967 
968 			debug("max_effort cut at x=%d y=%d\n", x, y);
969 			if (x < 0 || y < 0
970 			    || x > left->atoms.len || y > right->atoms.len)
971 				break;
972 
973 			found_midpoint = true;
974 			mid_snake = (struct diff_box){
975 				.left_start = x,
976 				.left_end = x,
977 				.right_start = y,
978 				.right_end = y,
979 			};
980 			break;
981 		}
982 	}
983 
984 	if (!found_midpoint) {
985 		/* Divide and conquer failed to find a meeting point. Use the
986 		 * fallback_algo defined in the algo_config (leave this to the
987 		 * caller). This is just paranoia/sanity, we normally should
988 		 * always find a midpoint.
989 		 */
990 		debug(" no midpoint \n");
991 		rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
992 		goto return_rc;
993 	} else {
994 		debug(" mid snake L: %u to %u of %u   R: %u to %u of %u\n",
995 		      mid_snake.left_start, mid_snake.left_end, left->atoms.len,
996 		      mid_snake.right_start, mid_snake.right_end,
997 		      right->atoms.len);
998 
999 		/* Section before the mid-snake.  */
1000 		debug("Section before the mid-snake\n");
1001 
1002 		struct diff_atom *left_atom = &left->atoms.head[0];
1003 		unsigned int left_section_len = mid_snake.left_start;
1004 		struct diff_atom *right_atom = &right->atoms.head[0];
1005 		unsigned int right_section_len = mid_snake.right_start;
1006 
1007 		if (left_section_len && right_section_len) {
1008 			/* Record an unsolved chunk, the caller will apply
1009 			 * inner_algo() on this chunk. */
1010 			if (!diff_state_add_chunk(state, false,
1011 						  left_atom, left_section_len,
1012 						  right_atom,
1013 						  right_section_len))
1014 				goto return_rc;
1015 		} else if (left_section_len && !right_section_len) {
1016 			/* Only left atoms and none on the right, they form a
1017 			 * "minus" chunk, then. */
1018 			if (!diff_state_add_chunk(state, true,
1019 						  left_atom, left_section_len,
1020 						  right_atom, 0))
1021 				goto return_rc;
1022 		} else if (!left_section_len && right_section_len) {
1023 			/* No left atoms, only atoms on the right, they form a
1024 			 * "plus" chunk, then. */
1025 			if (!diff_state_add_chunk(state, true,
1026 						  left_atom, 0,
1027 						  right_atom,
1028 						  right_section_len))
1029 				goto return_rc;
1030 		}
1031 		/* else: left_section_len == 0 and right_section_len == 0, i.e.
1032 		 * nothing before the mid-snake. */
1033 
1034 		if (mid_snake.left_end > mid_snake.left_start
1035 		    || mid_snake.right_end > mid_snake.right_start) {
1036 			/* The midpoint is a section of identical data on both
1037 			 * sides, or a certain differing line: that section
1038 			 * immediately becomes a solved chunk. */
1039 			debug("the mid-snake\n");
1040 			if (!diff_state_add_chunk(state, true,
1041 				  &left->atoms.head[mid_snake.left_start],
1042 				  mid_snake.left_end - mid_snake.left_start,
1043 				  &right->atoms.head[mid_snake.right_start],
1044 				  mid_snake.right_end - mid_snake.right_start))
1045 				goto return_rc;
1046 		}
1047 
1048 		/* Section after the mid-snake. */
1049 		debug("Section after the mid-snake\n");
1050 		debug("  left_end %u  right_end %u\n",
1051 		      mid_snake.left_end, mid_snake.right_end);
1052 		debug("  left_count %u  right_count %u\n",
1053 		      left->atoms.len, right->atoms.len);
1054 		left_atom = &left->atoms.head[mid_snake.left_end];
1055 		left_section_len = left->atoms.len - mid_snake.left_end;
1056 		right_atom = &right->atoms.head[mid_snake.right_end];
1057 		right_section_len = right->atoms.len - mid_snake.right_end;
1058 
1059 		if (left_section_len && right_section_len) {
1060 			/* Record an unsolved chunk, the caller will apply
1061 			 * inner_algo() on this chunk. */
1062 			if (!diff_state_add_chunk(state, false,
1063 						  left_atom, left_section_len,
1064 						  right_atom,
1065 						  right_section_len))
1066 				goto return_rc;
1067 		} else if (left_section_len && !right_section_len) {
1068 			/* Only left atoms and none on the right, they form a
1069 			 * "minus" chunk, then. */
1070 			if (!diff_state_add_chunk(state, true,
1071 						  left_atom, left_section_len,
1072 						  right_atom, 0))
1073 				goto return_rc;
1074 		} else if (!left_section_len && right_section_len) {
1075 			/* No left atoms, only atoms on the right, they form a
1076 			 * "plus" chunk, then. */
1077 			if (!diff_state_add_chunk(state, true,
1078 						  left_atom, 0,
1079 						  right_atom,
1080 						  right_section_len))
1081 				goto return_rc;
1082 		}
1083 		/* else: left_section_len == 0 and right_section_len == 0, i.e.
1084 		 * nothing after the mid-snake. */
1085 	}
1086 
1087 	rc = DIFF_RC_OK;
1088 
1089 return_rc:
1090 	debug("** END %s\n", __func__);
1091 	return rc;
1092 }
1093 
1094 /* Myers Diff tracing from the start all the way through to the end, requiring
1095  * quadratic amounts of memory. This can fail if the required space surpasses
1096  * algo_config->permitted_state_size. */
1097 int
1098 diff_algo_myers(const struct diff_algo_config *algo_config,
1099 		struct diff_state *state)
1100 {
1101 	/* do a diff_divide_myers_forward() without a _backward(), so that it
1102 	 * walks forward across the entire files to reach the end. Keep each
1103 	 * run's state, and do a final backtrace. */
1104 	int rc = ENOMEM;
1105 	struct diff_data *left = &state->left;
1106 	struct diff_data *right = &state->right;
1107 	int *kd_buf;
1108 
1109 	debug("\n** %s\n", __func__);
1110 	debug("left:\n");
1111 	debug_dump(left);
1112 	debug("right:\n");
1113 	debug_dump(right);
1114 	debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
1115 
1116 	/* Allocate two columns of a Myers graph, one for the forward and one
1117 	 * for the backward traversal. */
1118 	unsigned int max = left->atoms.len + right->atoms.len;
1119 	size_t kd_len = max + 1 + max;
1120 	size_t kd_buf_size = kd_len * kd_len;
1121 	size_t kd_state_size = kd_buf_size * sizeof(int);
1122 	debug("state size: %zu\n", kd_state_size);
1123 	if (kd_buf_size < kd_len /* overflow? */
1124 	    || kd_state_size > algo_config->permitted_state_size) {
1125 		debug("state size %zu > permitted_state_size %zu, use fallback_algo\n",
1126 		      kd_state_size, algo_config->permitted_state_size);
1127 		return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
1128 	}
1129 
1130 	if (state->kd_buf_size < kd_buf_size) {
1131 		kd_buf = reallocarray(state->kd_buf, kd_buf_size,
1132 		    sizeof(int));
1133 		if (!kd_buf)
1134 			return ENOMEM;
1135 		state->kd_buf = kd_buf;
1136 		state->kd_buf_size = kd_buf_size;
1137 	} else
1138 		kd_buf = state->kd_buf;
1139 
1140 	int i;
1141 	for (i = 0; i < kd_buf_size; i++)
1142 		kd_buf[i] = -1;
1143 
1144 	/* The 'k' axis in Myers spans positive and negative indexes, so point
1145 	 * the kd to the middle.
1146 	 * It is then possible to index from -max .. max. */
1147 	int *kd_origin = kd_buf + max;
1148 	int *kd_column = kd_origin;
1149 
1150 	int d;
1151 	int backtrack_d = -1;
1152 	int backtrack_k = 0;
1153 	int k;
1154 	int x, y;
1155 	for (d = 0; d <= max; d++, kd_column += kd_len) {
1156 		debug("-- d=%d\n", d);
1157 
1158 		debug("-- %s d=%d\n", __func__, d);
1159 
1160 		for (k = d; k >= -d; k -= 2) {
1161 			if (k < -(int)right->atoms.len
1162 			    || k > (int)left->atoms.len) {
1163 				/* This diagonal is completely outside of the
1164 				 * Myers graph, don't calculate it. */
1165 				if (k < -(int)right->atoms.len)
1166 					debug(" %d k <"
1167 					      " -(int)right->atoms.len %d\n",
1168 					      k, -(int)right->atoms.len);
1169 				else
1170 					debug(" %d k > left->atoms.len %d\n", k,
1171 					      left->atoms.len);
1172 				if (k < 0) {
1173 					/* We are traversing negatively, and
1174 					 * already below the entire graph,
1175 					 * nothing will come of this. */
1176 					debug(" break\n");
1177 					break;
1178 				}
1179 				debug(" continue\n");
1180 				continue;
1181 			}
1182 
1183 			debug("- k = %d\n", k);
1184 			if (d == 0) {
1185 				/* This is the initializing step. There is no
1186 				 * prev_k yet, get the initial x from the top
1187 				 * left of the Myers graph. */
1188 				x = 0;
1189 			} else {
1190 				int *kd_prev_column = kd_column - kd_len;
1191 
1192 				/* Favoring "-" lines first means favoring
1193 				 * moving rightwards in the Myers graph.
1194 				 * For this, all k should derive from k - 1,
1195 				 * only the bottom most k derive from k + 1:
1196 				 *
1197 				 *      | d=   0   1   2
1198 				 *  ----+----------------
1199 				 *  k=  |
1200 				 *   2  |             2,0 <-- from
1201 				 *      |            /        prev_k = 2 - 1 = 1
1202 				 *   1  |         1,0
1203 				 *      |        /
1204 				 *   0  |  -->0,0     3,3
1205 				 *      |       \\   /
1206 				 *  -1  |         0,1 <-- bottom most for d=1
1207 				 *      |           \\    from prev_k = -1+1 = 0
1208 				 *  -2  |             0,2 <-- bottom most for
1209 				 *                            d=2 from
1210 				 *                            prev_k = -2+1 = -1
1211 				 *
1212 				 * Except when a k + 1 from a previous run
1213 				 * already means a further advancement in the
1214 				 * graph.
1215 				 * If k == d, there is no k + 1 and k - 1 is the
1216 				 * only option.
1217 				 * If k < d, use k + 1 in case that yields a
1218 				 * larger x. Also use k + 1 if k - 1 is outside
1219 				 * the graph.
1220 				 */
1221 				if (k > -d
1222 				    && (k == d
1223 					|| (k - 1 >= -(int)right->atoms.len
1224 					    && kd_prev_column[k - 1]
1225 					       >= kd_prev_column[k + 1]))) {
1226 					/* Advance from k - 1.
1227 					 * From position prev_k, step to the
1228 					 * right in the Myers graph: x += 1.
1229 					 */
1230 					int prev_k = k - 1;
1231 					int prev_x = kd_prev_column[prev_k];
1232 					x = prev_x + 1;
1233 				} else {
1234 					/* The bottom most one.
1235 					 * From position prev_k, step to the
1236 					 * bottom in the Myers graph: y += 1.
1237 					 * Incrementing y is achieved by
1238 					 * decrementing k while keeping the same
1239 					 * x. (since we're deriving y from y =
1240 					 * x - k).
1241 					 */
1242 					int prev_k = k + 1;
1243 					int prev_x = kd_prev_column[prev_k];
1244 					x = prev_x;
1245 				}
1246 			}
1247 
1248 			/* Slide down any snake that we might find here. */
1249 			while (x < left->atoms.len
1250 			       && xk_to_y(x, k) < right->atoms.len) {
1251 				bool same;
1252 				int r = diff_atom_same(&same,
1253 						       &left->atoms.head[x],
1254 						       &right->atoms.head[
1255 							xk_to_y(x, k)]);
1256 				if (r)
1257 					return r;
1258 				if (!same)
1259 					break;
1260 				x++;
1261 			}
1262 			kd_column[k] = x;
1263 
1264 			if (DEBUG) {
1265 				int fi;
1266 				for (fi = d; fi >= k; fi-=2) {
1267 					debug("kd_column[%d] = (%d, %d)\n", fi,
1268 					      kd_column[fi],
1269 					      kd_column[fi] - fi);
1270 				}
1271 			}
1272 
1273 			if (x == left->atoms.len
1274 			    && xk_to_y(x, k) == right->atoms.len) {
1275 				/* Found a path */
1276 				backtrack_d = d;
1277 				backtrack_k = k;
1278 				debug("Reached the end at d = %d, k = %d\n",
1279 				      backtrack_d, backtrack_k);
1280 				break;
1281 			}
1282 		}
1283 
1284 		if (backtrack_d >= 0)
1285 			break;
1286 	}
1287 
1288 	debug_dump_myers_graph(left, right, kd_origin, NULL, 0, NULL, 0);
1289 
1290 	/* backtrack. A matrix spanning from start to end of the file is ready:
1291 	 *
1292 	 *      | d=   0   1   2   3   4
1293 	 *  ----+---------------------------------
1294 	 *  k=  |
1295 	 *   3  |
1296 	 *      |
1297 	 *   2  |             2,0
1298 	 *      |            /
1299 	 *   1  |         1,0     4,3
1300 	 *      |        /       /   \
1301 	 *   0  |  -->0,0     3,3     4,4 --> backtrack_d = 4, backtrack_k = 0
1302 	 *      |        \   /   \
1303 	 *  -1  |         0,1     3,4
1304 	 *      |            \
1305 	 *  -2  |             0,2
1306 	 *      |
1307 	 *
1308 	 * From (4,4) backwards, find the previous position that is the largest, and remember it.
1309 	 *
1310 	 */
1311 	for (d = backtrack_d, k = backtrack_k; d >= 0; d--) {
1312 		x = kd_column[k];
1313 		y = xk_to_y(x, k);
1314 
1315 		/* When the best position is identified, remember it for that
1316 		 * kd_column.
1317 		 * That kd_column is no longer needed otherwise, so just
1318 		 * re-purpose kd_column[0] = x and kd_column[1] = y,
1319 		 * so that there is no need to allocate more memory.
1320 		 */
1321 		kd_column[0] = x;
1322 		kd_column[1] = y;
1323 		debug("Backtrack d=%d: xy=(%d, %d)\n",
1324 		      d, kd_column[0], kd_column[1]);
1325 
1326 		/* Don't access memory before kd_buf */
1327 		if (d == 0)
1328 			break;
1329 		int *kd_prev_column = kd_column - kd_len;
1330 
1331 		/* When y == 0, backtracking downwards (k-1) is the only way.
1332 		 * When x == 0, backtracking upwards (k+1) is the only way.
1333 		 *
1334 		 *      | d=   0   1   2   3   4
1335 		 *  ----+---------------------------------
1336 		 *  k=  |
1337 		 *   3  |
1338 		 *      |                ..y == 0
1339 		 *   2  |             2,0
1340 		 *      |            /
1341 		 *   1  |         1,0     4,3
1342 		 *      |        /       /   \
1343 		 *   0  |  -->0,0     3,3     4,4 --> backtrack_d = 4,
1344 		 *      |        \   /   \            backtrack_k = 0
1345 		 *  -1  |         0,1     3,4
1346 		 *      |            \
1347 		 *  -2  |             0,2__
1348 		 *      |                  x == 0
1349 		 */
1350 		if (y == 0
1351 		    || (x > 0
1352 			&& kd_prev_column[k - 1] >= kd_prev_column[k + 1])) {
1353 			k = k - 1;
1354 			debug("prev k=k-1=%d x=%d y=%d\n",
1355 			      k, kd_prev_column[k],
1356 			      xk_to_y(kd_prev_column[k], k));
1357 		} else {
1358 			k = k + 1;
1359 			debug("prev k=k+1=%d x=%d y=%d\n",
1360 			      k, kd_prev_column[k],
1361 			      xk_to_y(kd_prev_column[k], k));
1362 		}
1363 		kd_column = kd_prev_column;
1364 	}
1365 
1366 	/* Forwards again, this time recording the diff chunks.
1367 	 * Definitely start from 0,0. kd_column[0] may actually point to the
1368 	 * bottom of a snake starting at 0,0 */
1369 	x = 0;
1370 	y = 0;
1371 
1372 	kd_column = kd_origin;
1373 	for (d = 0; d <= backtrack_d; d++, kd_column += kd_len) {
1374 		int next_x = kd_column[0];
1375 		int next_y = kd_column[1];
1376 		debug("Forward track from xy(%d,%d) to xy(%d,%d)\n",
1377 		      x, y, next_x, next_y);
1378 
1379 		struct diff_atom *left_atom = &left->atoms.head[x];
1380 		int left_section_len = next_x - x;
1381 		struct diff_atom *right_atom = &right->atoms.head[y];
1382 		int right_section_len = next_y - y;
1383 
1384 		rc = ENOMEM;
1385 		if (left_section_len && right_section_len) {
1386 			/* This must be a snake slide.
1387 			 * Snake slides have a straight line leading into them
1388 			 * (except when starting at (0,0)). Find out whether the
1389 			 * lead-in is horizontal or vertical:
1390 			 *
1391 			 *     left
1392 			 *  ---------->
1393 			 *  |
1394 			 * r|   o-o        o
1395 			 * i|      \       |
1396 			 * g|       o      o
1397 			 * h|        \      \
1398 			 * t|         o      o
1399 			 *  v
1400 			 *
1401 			 * If left_section_len > right_section_len, the lead-in
1402 			 * is horizontal, meaning first remove one atom from the
1403 			 * left before sliding down the snake.
1404 			 * If right_section_len > left_section_len, the lead-in
1405 			 * is vetical, so add one atom from the right before
1406 			 * sliding down the snake. */
1407 			if (left_section_len == right_section_len + 1) {
1408 				if (!diff_state_add_chunk(state, true,
1409 							  left_atom, 1,
1410 							  right_atom, 0))
1411 					goto return_rc;
1412 				left_atom++;
1413 				left_section_len--;
1414 			} else if (right_section_len == left_section_len + 1) {
1415 				if (!diff_state_add_chunk(state, true,
1416 							  left_atom, 0,
1417 							  right_atom, 1))
1418 					goto return_rc;
1419 				right_atom++;
1420 				right_section_len--;
1421 			} else if (left_section_len != right_section_len) {
1422 				/* The numbers are making no sense. Should never
1423 				 * happen. */
1424 				rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
1425 				goto return_rc;
1426 			}
1427 
1428 			if (!diff_state_add_chunk(state, true,
1429 						  left_atom, left_section_len,
1430 						  right_atom,
1431 						  right_section_len))
1432 				goto return_rc;
1433 		} else if (left_section_len && !right_section_len) {
1434 			/* Only left atoms and none on the right, they form a
1435 			 * "minus" chunk, then. */
1436 			if (!diff_state_add_chunk(state, true,
1437 						  left_atom, left_section_len,
1438 						  right_atom, 0))
1439 				goto return_rc;
1440 		} else if (!left_section_len && right_section_len) {
1441 			/* No left atoms, only atoms on the right, they form a
1442 			 * "plus" chunk, then. */
1443 			if (!diff_state_add_chunk(state, true,
1444 						  left_atom, 0,
1445 						  right_atom,
1446 						  right_section_len))
1447 				goto return_rc;
1448 		}
1449 
1450 		x = next_x;
1451 		y = next_y;
1452 	}
1453 
1454 	rc = DIFF_RC_OK;
1455 
1456 return_rc:
1457 	debug("** END %s rc=%d\n", __func__, rc);
1458 	return rc;
1459 }