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