Lines Matching +full:2 +full:k
33 /* Myers' diff algorithm [1] is nicely explained in [2].
35 * [2] https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ ff.
41 * 2000 * 2000 ints of state, about 16 Mb of RAM to figure out 2 kb of text.
61 * k-1 0 1 2 3 4 5
67 * 2 o-o-o-o-o-o
90 * d: the step number, starting with 0, a.k.a. the distance from the starting
92 * k: relative index in the state array for the forward scan, indicating on
99 * | d= 0 1 2 3 2 1 0
101 * k= | c=
104 * 3 | 3,0 5,2 2
106 * 2 | 2,0 5,3 1
112 * -1 | 0,1 1,2 3,4 -2
114 * -2 | 0,2 -3
128 * Also note that from the diagonal index k and the x coordinate, the y
130 * y = x - k
141 * 0 1 2 3 4 5
147 * 2 o-o-o-o-o
155 * 0 1 2 3 4 5
160 * B \ f: then forward d=2 reaches here (sliding down the snake)
161 * 2 o As result, the box from b to f is found to be identical;
171 * 0 1 2 3 4 5
177 * 2 o -E
185 #define xk_to_y(X, K) ((X) - (K)) argument
187 #define k_to_c(K, DELTA) ((K) + (DELTA)) argument
218 int k; in diff_divide_myers_forward() local
225 for (k = d; k >= -d; k -= 2) { in diff_divide_myers_forward()
226 if (k < -(int)right->atoms.len || k > (int)left->atoms.len) { in diff_divide_myers_forward()
229 if (k < 0) { in diff_divide_myers_forward()
245 prev_y = xk_to_y(x, k); in diff_divide_myers_forward()
249 * For this, all k should derive from k - 1, only the bottom in diff_divide_myers_forward()
250 * most k derive from k + 1: in diff_divide_myers_forward()
252 * | d= 0 1 2 in diff_divide_myers_forward()
254 * k= | in diff_divide_myers_forward()
255 * 2 | 2,0 <-- from prev_k = 2 - 1 = 1 in diff_divide_myers_forward()
263 * -2 | 0,2 <-- bottom most for d=2 from in diff_divide_myers_forward()
264 * prev_k = -2 + 1 = -1 in diff_divide_myers_forward()
266 * Except when a k + 1 from a previous run already means a in diff_divide_myers_forward()
268 * If k == d, there is no k + 1 and k - 1 is the only option. in diff_divide_myers_forward()
269 * If k < d, use k + 1 in case that yields a larger x. Also use in diff_divide_myers_forward()
270 * k + 1 if k - 1 is outside the graph. in diff_divide_myers_forward()
272 else if (k > -d in diff_divide_myers_forward()
273 && (k == d in diff_divide_myers_forward()
274 || (k - 1 >= -(int)right->atoms.len in diff_divide_myers_forward()
275 && kd_forward[k - 1] >= kd_forward[k + 1]))) { in diff_divide_myers_forward()
276 /* Advance from k - 1. in diff_divide_myers_forward()
280 int prev_k = k - 1; in diff_divide_myers_forward()
288 * Incrementing y is achieved by decrementing k while in diff_divide_myers_forward()
290 * (since we're deriving y from y = x - k). in diff_divide_myers_forward()
292 int prev_k = k + 1; in diff_divide_myers_forward()
300 while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len) { in diff_divide_myers_forward()
305 xk_to_y(x, k)]); in diff_divide_myers_forward()
312 kd_forward[k] = x; in diff_divide_myers_forward()
321 for (fi = d; fi >= k; fi--) { in diff_divide_myers_forward()
330 || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len) in diff_divide_myers_forward()
338 * | d= 0 1 2 1 0 in diff_divide_myers_forward()
340 * k= | c= in diff_divide_myers_forward()
343 * 3 | 2 in diff_divide_myers_forward()
345 * 2 | 2,0====5,3 1 in diff_divide_myers_forward()
351 * -1 | 0,1 -2 in diff_divide_myers_forward()
353 * -2 | 0,2 -3 in diff_divide_myers_forward()
359 * | d= 0 1 2 1 0 in diff_divide_myers_forward()
364 * 2 | 2,0 off 2 in diff_divide_myers_forward()
372 * -2 | 0,2 -2 in diff_divide_myers_forward()
388 * c == k. in diff_divide_myers_forward()
390 * traversal starts on a different diagonal, and c = k shifted in diff_divide_myers_forward()
393 int c = k_to_c(k, delta); in diff_divide_myers_forward()
401 /* Current k is on a diagonal that exists in in diff_divide_myers_forward()
454 .right_end = xk_to_y(x, k), in diff_divide_myers_forward()
467 .right_end = xk_to_y(x, k), in diff_divide_myers_forward()
524 for (c = d; c >= -d; c -= 2) { in diff_divide_myers_backward()
549 * 2 1 0 in diff_divide_myers_backward()
554 * from prev_c = c - 1 --> 5,2 2 in diff_divide_myers_backward()
562 * bottom most for d=2 --> 3,4 -2 in diff_divide_myers_backward()
653 * | d= 0 1 2 2 1 0 in diff_divide_myers_backward()
655 * k= | c= in diff_divide_myers_backward()
660 * 2 | 2,0====5,2 2 in diff_divide_myers_backward()
668 * -2 | 0,2 -2 in diff_divide_myers_backward()
683 * and c = k shifted by the difference in length. in diff_divide_myers_backward()
685 int k = c_to_k(c, delta); in diff_divide_myers_backward() local
692 if (k >= -forwards_d && k <= forwards_d) { in diff_divide_myers_backward()
736 int forward_x = kd_forward[k]; in diff_divide_myers_backward()
744 .right_end = xk_to_y(x_before_slide, k), in diff_divide_myers_backward()
781 for (i = 1; val > 0; val >>= 2) in shift_sqrt()
826 int max_effort = shift_sqrt(max/2); in diff_algo_myers_divide()
831 /* The 'k' axis in Myers spans positive and negative indexes, so point in diff_algo_myers_divide()
833 * It is then possible to index from -max/2 .. max/2. */ in diff_algo_myers_divide()
834 kd_forward += max/2; in diff_algo_myers_divide()
835 kd_backward += max/2; in diff_algo_myers_divide()
840 for (d = 0; d <= (max/2); d++) { in diff_algo_myers_divide()
886 for (i = d; i >= -d; i -= 2) { in diff_algo_myers_divide()
1122 /* The 'k' axis in Myers spans positive and negative indexes, so point in diff_algo_myers()
1131 int k; in diff_algo_myers() local
1136 for (k = d; k >= -d; k -= 2) { in diff_algo_myers()
1137 if (k < -(int)right->atoms.len in diff_algo_myers()
1138 || k > (int)left->atoms.len) { in diff_algo_myers()
1141 if (k < -(int)right->atoms.len) in diff_algo_myers()
1142 debug(" %d k <" in diff_algo_myers()
1144 k, -(int)right->atoms.len); in diff_algo_myers()
1146 debug(" %d k > left->atoms.len %d\n", k, in diff_algo_myers()
1148 if (k < 0) { in diff_algo_myers()
1169 * For this, all k should derive from k - 1, in diff_algo_myers()
1170 * only the bottom most k derive from k + 1: in diff_algo_myers()
1172 * | d= 0 1 2 in diff_algo_myers()
1174 * k= | in diff_algo_myers()
1175 * 2 | 2,0 <-- from in diff_algo_myers()
1176 * | / prev_k = 2 - 1 = 1 in diff_algo_myers()
1183 * -2 | 0,2 <-- bottom most for in diff_algo_myers()
1184 * d=2 from in diff_algo_myers()
1185 * prev_k = -2+1 = -1 in diff_algo_myers()
1187 * Except when a k + 1 from a previous run in diff_algo_myers()
1190 * If k == d, there is no k + 1 and k - 1 is the in diff_algo_myers()
1192 * If k < d, use k + 1 in case that yields a in diff_algo_myers()
1193 * larger x. Also use k + 1 if k - 1 is outside in diff_algo_myers()
1196 if (k > -d in diff_algo_myers()
1197 && (k == d in diff_algo_myers()
1198 || (k - 1 >= -(int)right->atoms.len in diff_algo_myers()
1199 && kd_prev_column[k - 1] in diff_algo_myers()
1200 >= kd_prev_column[k + 1]))) { in diff_algo_myers()
1201 /* Advance from k - 1. in diff_algo_myers()
1205 int prev_k = k - 1; in diff_algo_myers()
1213 * decrementing k while keeping the same in diff_algo_myers()
1215 * x - k). in diff_algo_myers()
1217 int prev_k = k + 1; in diff_algo_myers()
1225 && xk_to_y(x, k) < right->atoms.len) { in diff_algo_myers()
1230 xk_to_y(x, k)]); in diff_algo_myers()
1237 kd_column[k] = x; in diff_algo_myers()
1240 && xk_to_y(x, k) == right->atoms.len) { in diff_algo_myers()
1243 backtrack_k = k; in diff_algo_myers()
1244 debug("Reached the end at d = %d, k = %d\n", in diff_algo_myers()
1258 * | d= 0 1 2 3 4 in diff_algo_myers()
1260 * k= | in diff_algo_myers()
1263 * 2 | 2,0 in diff_algo_myers()
1271 * -2 | 0,2 in diff_algo_myers()
1277 for (d = backtrack_d, k = backtrack_k; d >= 0; d--) { in diff_algo_myers()
1278 x = kd_column[k]; in diff_algo_myers()
1279 y = xk_to_y(x, k); in diff_algo_myers()
1297 /* When y == 0, backtracking downwards (k-1) is the only way. in diff_algo_myers()
1298 * When x == 0, backtracking upwards (k+1) is the only way. in diff_algo_myers()
1300 * | d= 0 1 2 3 4 in diff_algo_myers()
1302 * k= | in diff_algo_myers()
1305 * 2 | 2,0 in diff_algo_myers()
1313 * -2 | 0,2__ in diff_algo_myers()
1318 && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) { in diff_algo_myers()
1319 k = k - 1; in diff_algo_myers()
1320 debug("prev k=k-1=%d x=%d y=%d\n", in diff_algo_myers()
1321 k, kd_prev_column[k], in diff_algo_myers()
1322 xk_to_y(kd_prev_column[k], k)); in diff_algo_myers()
1324 k = k + 1; in diff_algo_myers()
1325 debug("prev k=k+1=%d x=%d y=%d\n", in diff_algo_myers()
1326 k, kd_prev_column[k], in diff_algo_myers()
1327 xk_to_y(kd_prev_column[k], k)); in diff_algo_myers()