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