{"thread":{"id":"3717","subject":"Use a *real* built-in diff generator","startedAt":"2006-03-25T04:13:22Z","lastAt":"2006-03-26T18:20:28Z","messageCount":22,"participants":["Linus Torvalds","Junio C Hamano","Davide Libenzi","Marco Costalba","Alex Riesen","Morten Welinder","Ralf Baechle","Petr Baudis"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"17904","messageId":"Pine.LNX.4.64.0603241938510.15714@g5.osdl.org","threadId":"3717","inReplyTo":null,"subject":"Use a *real* built-in diff generator","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-25T04:13:22Z","receivedAt":"2006-03-25T04:13:22Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis uses a simplified libxdiff setup to generate unified diffs _without_ \ndoing fork/execve of GNU \"diff\".\n\nThis has several huge advantages, for example:\n\nBefore:\n\n\t[torvalds@g5 linux]$ time git diff v2.6.16.. > /dev/null \n\n\treal 0m24.818s\n\tuser 0m13.332s\n\tsys 0m8.664s\n\nAfter:\n\n\t[torvalds@g5 linux]$ time git diff v2.6.16.. > /dev/null \n\t\n\treal 0m4.563s\n\tuser 0m2.944s\n\tsys 0m1.580s\n\nand the fact that this should be a lot more portable (ie we can ignore all \nthe issues with doing fork/execve under Windows).\n\nPerhaps even more importantly, this allows us to do diffs without actually \never writing out the git file contents to a temporary file (and without \nany of the shell quoting issues on filenames etc etc).\n\nNOTE! THIS PATCH DOES NOT DO THAT OPTIMIZATION YET! I was lazy, and the \ncurrent \"diff-core\" code actually will always write the temp-files, \nbecause it used to be something that you simply had to do. So this current \none actually writes a temp-file like before, and then reads it into memory \nagain just to do the diff. Stupid.\n\nBut if this basic infrastructure is accepted, we can start switching over \ndiff-core to not write temp-files, which should speed things up even \nfurther, especially when doing big tree-to-tree diffs.\n\nNow, in the interest of full disclosure, I should also point out a few \ndownsides:\n\n - the libxdiff algorithm is different, and I bet GNU diff has gotten a \n lot more testing. And the thing is, generating a diff is not an exact \n science - you can get two different diffs (and you will), and they can \n both be perfectly valid. So it's not possible to \"validate\" the \n libxdiff output by just comparing it against GNU diff.\n\n - GNU diff does some nice eye-candy, like trying to figure out what the \n last function was, and adding that information to the \"@@ ..\" line. \n libxdiff doesn't do that. \n\n - The libxdiff thing has some known deficiencies. In particular, it gets \n the \"\\No newline at end of file\" case wrong. So this is currently for \n the experimental branch only. I hope Davide will help fix it.\n\nThat said, I think the huge performance advantage, and the fact that it \nintegrates better is definitely worth it. But it should go into a \ndevelopment branch at least due to the missing newline issue.\n\nTechnical note: this is based on libxdiff-0.17, but I did some surgery to \nget rid of the extraneous fat - stuff that git doesn't need, and seriously \ncutting down on mmfile_t, which had much more capabilities than the diff \nalgorithm either needed or used. In this version, \"mmfile_t\" is just a \ntrivial tuple.\n\nThat said, I tried to keep the differences to simple removals, so that you \ncan do a diff between this and the libxdiff origin, and you'll basically \nsee just things getting deleted. Even the mmfile_t simplifications are \nleft in a state where the diffs should be readable.\n\nApologies to Davide, whom I'd love to get feedback on this all from (I \nwrote my own \"fill_mmfile()\" for the new simpler mmfile_t format: the old \ncomplex format had a helper function for that, but I did my surgery with \nthe goal in mind that eventually we _should_ just do\n\n\tmmfile_t mf;\n\n\tbuf = read_sha1_file(sha1, type, &size);\n\tmf->ptr = buf;\n\tmf->size = size;\n\t.. use \"mf\" directly ..\n\nwhich was really a nightmare with the old \"helpful\" mmfile_t, and really \nis that easy with the new cut-down interfaces).\n\n[ Btw, as any hawk-eye can see from the diff, this was actually generated \n with itself, so it is \"self-hosting\". That's about all the testing it \n has gotten, along with the above kernel diff, which eye-balls correctly, \n but shows the newline issue when you double-check it with \"git-apply\" ]\n\nSigned-off-by: Linus Torvalds \n----\n Makefile | 11 +\n diff.c | 79 ++++++++-\n xdiff/xdiff.h | 91 ++++++++++\n xdiff/xdiffi.c | 469 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n xdiff/xdiffi.h | 60 +++++++\n xdiff/xemit.c | 141 ++++++++++++++++\n xdiff/xemit.h | 34 ++++\n xdiff/xinclude.h | 42 +++++\n xdiff/xmacros.h | 53 ++++++\n xdiff/xprepare.c | 436 ++++++++++++++++++++++++++++++++++++++++++++++++++\n xdiff/xprepare.h | 35 ++++\n xdiff/xtypes.h | 68 ++++++++\n xdiff/xutils.c | 265 +++++++++++++++++++++++++++++++\n xdiff/xutils.h | 44 +++++\n 14 files changed, 1820 insertions(+), 8 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 8d45378..0f565eb 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -188,6 +188,7 @@\n \tgitMergeCommon.py\n \n LIB_FILE=libgit.a\n+XDIFF_LIB=xdiff/lib.a\n \n LIB_H = \\\n \tblob.h cache.h commit.h count-delta.h csum-file.h delta.h \\\n@@ -209,7 +210,7 @@\n \tfetch-clone.o revision.o pager.o \\\n \t$(DIFF_OBJS)\n \n-LIBS = $(LIB_FILE)\n+LIBS = $(LIB_FILE) $(XDIFF_LIB)\n LIBS += -lz\n \n #\n@@ -544,11 +545,17 @@\n \t\t-DDEFAULT_GIT_TEMPLATE_DIR='\"$(template_dir_SQ)\"' $*.c\n \n $(LIB_OBJS): $(LIB_H)\n-$(patsubst git-%$X,%.o,$(PROGRAMS)): $(LIB_H)\n+$(patsubst git-%$X,%.o,$(PROGRAMS)): $(LIBS)\n $(DIFF_OBJS): diffcore.h\n \n $(LIB_FILE): $(LIB_OBJS)\n \t$(AR) rcs $@ $(LIB_OBJS)\n+\n+XDIFF_OBJS=xdiff/xdiffi.o xdiff/xprepare.o xdiff/xutils.o xdiff/xemit.o\n+\n+$(XDIFF_LIB): $(XDIFF_OBJS)\n+\t$(AR) rcs $@ $(XDIFF_OBJS)\n+\n \n doc:\n \t$(MAKE) -C Documentation all\ndiff --git a/diff.c b/diff.c\nindex c0548ee..f6a1f5d 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -8,6 +8,7 @@\n #include \"quote.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n+#include \"xdiff/xdiff.h\"\n \n static const char *diff_opts = \"-pu\";\n \n@@ -178,6 +179,49 @@\n \t\tcopy_file('+', temp[1].name);\n }\n \n+static int fill_mmfile(mmfile_t *mf, const char *file)\n+{\n+\tint fd = open(file, O_RDONLY);\n+\tstruct stat st;\n+\tchar *buf;\n+\tunsigned long size;\n+\n+\tmf->ptr = NULL;\n+\tmf->size = 0;\n+\tif (fd < 0)\n+\t\treturn 0;\n+\tfstat(fd, &st);\n+\tsize = st.st_size;\n+\tbuf = xmalloc(size);\n+\tmf->ptr = buf;\n+\tmf->size = size;\n+\twhile (size) {\n+\t\tint retval = read(fd, buf, size);\n+\t\tif (retval < 0) {\n+\t\t\tif (errno == EINTR || errno == EAGAIN)\n+\t\t\t\tcontinue;\n+\t\t\tbreak;\n+\t\t}\n+\t\tif (!retval)\n+\t\t\tbreak;\n+\t\tbuf += retval;\n+\t\tsize -= retval;\n+\t}\n+\tmf->size -= size;\n+\tclose(fd);\n+\treturn 0;\n+}\n+\n+static int fn_out(void *priv, mmbuffer_t *mb, int nbuf)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < nbuf; i++)\n+\t\tif (!fwrite(mb[i].ptr, mb[i].size, 1, stdout))\n+\t\t\treturn -1;\n+\treturn 0;\n+}\n+\n static const char *builtin_diff(const char *name_a,\n \t\t\t const char *name_b,\n \t\t\t struct diff_tempfile *temp,\n@@ -186,6 +230,7 @@\n \t\t\t const char **args)\n {\n \tint i, next_at, cmd_size;\n+\tmmfile_t mf1, mf2;\n \tconst char *const diff_cmd = \"diff -L%s -L%s\";\n \tconst char *const diff_arg = \"-- %s %s||:\"; /* \"||:\" is to return 0 */\n \tconst char *input_name_sq[2];\n@@ -253,14 +298,36 @@\n \t\t\temit_rewrite_diff(name_a, name_b, temp);\n \t\t\treturn NULL;\n \t\t}\n+\t}\n+\n+\t/* Un-quote the paths */\n+\tif (label_path[0][0] != '/')\n+\t\tlabel_path[0] = quote_two(\"a/\", name_a);\n+\tif (label_path[1][0] != '/')\n+\t\tlabel_path[1] = quote_two(\"b/\", name_b);\n+\n+\tprintf(\"--- %s\\n\", label_path[0]);\n+\tprintf(\"+++ %s\\n\", label_path[1]);\n+\n+\tif (fill_mmfile(&mf1, temp[0].name) < 0 ||\n+\t fill_mmfile(&mf2, temp[1].name) < 0)\n+\t\tdie(\"unable to read files to diff\");\n+\n+\t/* Crazy xdl interfaces.. */\n+\t{\n+\t\txpparam_t xpp;\n+\t\txdemitconf_t xecfg;\n+\t\txdemitcb_t ecb;\n+\n+\t\txpp.flags = XDF_NEED_MINIMAL;\n+\t\txecfg.ctxlen = 3;\n+\t\tecb.outf = fn_out;\n+\t\txdl_diff(&mf1, &mf2, &xpp, &xecfg, &ecb);\n \t}\n \n-\t/* This is disgusting */\n-\t*args++ = \"sh\";\n-\t*args++ = \"-c\";\n-\t*args++ = cmd;\n-\t*args = NULL;\n-\treturn \"/bin/sh\";\n+\tfree(mf1.ptr);\n+\tfree(mf2.ptr);\n+\treturn NULL;\n }\n \n struct diff_filespec *alloc_filespec(const char *path)\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nnew file mode 100644\nindex 0000000..d900295\n--- /dev/null\n+++ b/xdiff/xdiff.h\n@@ -0,0 +1,91 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003 Davide Libenzi\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+\n+#if !defined(XDIFF_H)\n+#define XDIFF_H\n+\n+#ifdef __cplusplus\n+extern \"C\" {\n+#endif /* #ifdef __cplusplus */\n+\n+\n+#define XDF_NEED_MINIMAL (1 << 1)\n+\n+#define XDL_PATCH_NORMAL '-'\n+#define XDL_PATCH_REVERSE '+'\n+#define XDL_PATCH_MODEMASK ((1 << 8) - 1)\n+#define XDL_PATCH_IGNOREBSPACE (1 << 8)\n+\t\n+#define XDL_MMB_READONLY (1 << 0)\n+\n+#define XDL_MMF_ATOMIC (1 << 0)\n+\n+#define XDL_BDOP_INS 1\n+#define XDL_BDOP_CPY 2\n+#define XDL_BDOP_INSB 3\n+\n+\n+typedef struct s_mmfile {\n+\tchar *ptr;\n+\tlong size;\n+} mmfile_t;\n+\n+typedef struct s_mmbuffer {\n+\tchar *ptr;\n+\tlong size;\n+} mmbuffer_t;\n+\n+typedef struct s_xpparam {\n+\tunsigned long flags;\n+} xpparam_t;\n+\n+typedef struct s_xdemitcb {\n+\tvoid *priv;\n+\tint (*outf)(void *, mmbuffer_t *, int);\n+} xdemitcb_t;\n+\n+typedef struct s_xdemitconf {\n+\tlong ctxlen;\n+} xdemitconf_t;\n+\n+typedef struct s_bdiffparam {\n+\tlong bsize;\n+} bdiffparam_t;\n+\n+\n+#define xdl_malloc(x) malloc(x)\n+#define xdl_free(ptr) free(ptr)\n+#define xdl_realloc(ptr,x) realloc(ptr,x)\n+\n+void *xdl_mmfile_first(mmfile_t *mmf, long *size);\n+void *xdl_mmfile_next(mmfile_t *mmf, long *size);\n+long xdl_mmfile_size(mmfile_t *mmf);\n+\n+int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n+\t xdemitconf_t const *xecfg, xdemitcb_t *ecb);\n+\n+#ifdef __cplusplus\n+}\n+#endif /* #ifdef __cplusplus */\n+\n+#endif /* #if !defined(XDIFF_H) */\n+\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nnew file mode 100644\nindex 0000000..8ea0483\n--- /dev/null\n+++ b/xdiff/xdiffi.c\n@@ -0,0 +1,469 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003\tDavide Libenzi\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+\n+#include \"xinclude.h\"\n+\n+\n+\n+#define XDL_MAX_COST_MIN 256\n+#define XDL_HEUR_MIN_COST 256\n+#define XDL_LINE_MAX (long)((1UL << (8 * sizeof(long) - 1)) - 1)\n+#define XDL_SNAKE_CNT 20\n+#define XDL_K_HEUR 4\n+\n+\n+\n+typedef struct s_xdpsplit {\n+\tlong i1, i2;\n+\tint min_lo, min_hi;\n+} xdpsplit_t;\n+\n+\n+\n+\n+static long xdl_split(unsigned long const *ha1, long off1, long lim1,\n+\t\t unsigned long const *ha2, long off2, long lim2,\n+\t\t long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,\n+\t\t xdalgoenv_t *xenv);\n+static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2);\n+\n+\n+\n+\n+/*\n+ * See \"An O(ND) Difference Algorithm and its Variations\", by Eugene Myers.\n+ * Basically considers a \"box\" (off1, off2, lim1, lim2) and scan from both\n+ * the forward diagonal starting from (off1, off2) and the backward diagonal\n+ * starting from (lim1, lim2). If the K values on the same diagonal crosses\n+ * returns the furthest point of reach. We might end up having to expensive\n+ * cases using this algorithm is full, so a little bit of heuristic is needed\n+ * to cut the search and to return a suboptimal point.\n+ */\n+static long xdl_split(unsigned long const *ha1, long off1, long lim1,\n+\t\t unsigned long const *ha2, long off2, long lim2,\n+\t\t long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,\n+\t\t xdalgoenv_t *xenv) {\n+\tlong dmin = off1 - lim2, dmax = lim1 - off2;\n+\tlong fmid = off1 - off2, bmid = lim1 - lim2;\n+\tlong odd = (fmid - bmid) & 1;\n+\tlong fmin = fmid, fmax = fmid;\n+\tlong bmin = bmid, bmax = bmid;\n+\tlong ec, d, i1, i2, prev1, best, dd, v, k;\n+\n+\t/*\n+\t * Set initial diagonal values for both forward and backward path.\n+\t */\n+\tkvdf[fmid] = off1;\n+\tkvdb[bmid] = lim1;\n+\n+\tfor (ec = 1;; ec++) {\n+\t\tint got_snake = 0;\n+\n+\t\t/*\n+\t\t * We need to extent the diagonal \"domain\" by one. If the next\n+\t\t * values exits the box boundaries we need to change it in the\n+\t\t * opposite direction because (max - min) must be a power of two.\n+\t\t * Also we initialize the extenal K value to -1 so that we can\n+\t\t * avoid extra conditions check inside the core loop.\n+\t\t */\n+\t\tif (fmin > dmin)\n+\t\t\tkvdf[--fmin - 1] = -1;\n+\t\telse\n+\t\t\t++fmin;\n+\t\tif (fmax < dmax)\n+\t\t\tkvdf[++fmax + 1] = -1;\n+\t\telse\n+\t\t\t--fmax;\n+\n+\t\tfor (d = fmax; d >= fmin; d -= 2) {\n+\t\t\tif (kvdf[d - 1] >= kvdf[d + 1])\n+\t\t\t\ti1 = kvdf[d - 1] + 1;\n+\t\t\telse\n+\t\t\t\ti1 = kvdf[d + 1];\n+\t\t\tprev1 = i1;\n+\t\t\ti2 = i1 - d;\n+\t\t\tfor (; i1 < lim1 && i2 < lim2 && ha1[i1] == ha2[i2]; i1++, i2++);\n+\t\t\tif (i1 - prev1 > xenv->snake_cnt)\n+\t\t\t\tgot_snake = 1;\n+\t\t\tkvdf[d] = i1;\n+\t\t\tif (odd && bmin <= d && d <= bmax && kvdb[d] <= i1) {\n+\t\t\t\tspl->i1 = i1;\n+\t\t\t\tspl->i2 = i2;\n+\t\t\t\tspl->min_lo = spl->min_hi = 1;\n+\t\t\t\treturn ec;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/*\n+\t\t * We need to extent the diagonal \"domain\" by one. If the next\n+\t\t * values exits the box boundaries we need to change it in the\n+\t\t * opposite direction because (max - min) must be a power of two.\n+\t\t * Also we initialize the extenal K value to -1 so that we can\n+\t\t * avoid extra conditions check inside the core loop.\n+\t\t */\n+\t\tif (bmin > dmin)\n+\t\t\tkvdb[--bmin - 1] = XDL_LINE_MAX;\n+\t\telse\n+\t\t\t++bmin;\n+\t\tif (bmax < dmax)\n+\t\t\tkvdb[++bmax + 1] = XDL_LINE_MAX;\n+\t\telse\n+\t\t\t--bmax;\n+\n+\t\tfor (d = bmax; d >= bmin; d -= 2) {\n+\t\t\tif (kvdb[d - 1] < kvdb[d + 1])\n+\t\t\t\ti1 = kvdb[d - 1];\n+\t\t\telse\n+\t\t\t\ti1 = kvdb[d + 1] - 1;\n+\t\t\tprev1 = i1;\n+\t\t\ti2 = i1 - d;\n+\t\t\tfor (; i1 > off1 && i2 > off2 && ha1[i1 - 1] == ha2[i2 - 1]; i1--, i2--);\n+\t\t\tif (prev1 - i1 > xenv->snake_cnt)\n+\t\t\t\tgot_snake = 1;\n+\t\t\tkvdb[d] = i1;\n+\t\t\tif (!odd && fmin <= d && d <= fmax && i1 <= kvdf[d]) {\n+\t\t\t\tspl->i1 = i1;\n+\t\t\t\tspl->i2 = i2;\n+\t\t\t\tspl->min_lo = spl->min_hi = 1;\n+\t\t\t\treturn ec;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (need_min)\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * If the edit cost is above the heuristic trigger and if\n+\t\t * we got a good snake, we sample current diagonals to see\n+\t\t * if some of the, have reached an \"interesting\" path. Our\n+\t\t * measure is a function of the distance from the diagonal\n+\t\t * corner (i1 + i2) penalized with the distance from the\n+\t\t * mid diagonal itself. If this value is above the current\n+\t\t * edit cost times a magic factor (XDL_K_HEUR) we consider\n+\t\t * it interesting.\n+\t\t */\n+\t\tif (got_snake && ec > xenv->heur_min) {\n+\t\t\tfor (best = 0, d = fmax; d >= fmin; d -= 2) {\n+\t\t\t\tdd = d > fmid ? d - fmid: fmid - d;\n+\t\t\t\ti1 = kvdf[d];\n+\t\t\t\ti2 = i1 - d;\n+\t\t\t\tv = (i1 - off1) + (i2 - off2) - dd;\n+\n+\t\t\t\tif (v > XDL_K_HEUR * ec && v > best &&\n+\t\t\t\t off1 + xenv->snake_cnt <= i1 && i1 < lim1 &&\n+\t\t\t\t off2 + xenv->snake_cnt <= i2 && i2 < lim2) {\n+\t\t\t\t\tfor (k = 1; ha1[i1 - k] == ha2[i2 - k]; k++)\n+\t\t\t\t\t\tif (k == xenv->snake_cnt) {\n+\t\t\t\t\t\t\tbest = v;\n+\t\t\t\t\t\t\tspl->i1 = i1;\n+\t\t\t\t\t\t\tspl->i2 = i2;\n+\t\t\t\t\t\t\tbreak;\n+\t\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\tif (best > 0) {\n+\t\t\t\tspl->min_lo = 1;\n+\t\t\t\tspl->min_hi = 0;\n+\t\t\t\treturn ec;\n+\t\t\t}\n+\n+\t\t\tfor (best = 0, d = bmax; d >= bmin; d -= 2) {\n+\t\t\t\tdd = d > bmid ? d - bmid: bmid - d;\n+\t\t\t\ti1 = kvdb[d];\n+\t\t\t\ti2 = i1 - d;\n+\t\t\t\tv = (lim1 - i1) + (lim2 - i2) - dd;\n+\n+\t\t\t\tif (v > XDL_K_HEUR * ec && v > best &&\n+\t\t\t\t off1 < i1 && i1 <= lim1 - xenv->snake_cnt &&\n+\t\t\t\t off2 < i2 && i2 <= lim2 - xenv->snake_cnt) {\n+\t\t\t\t\tfor (k = 0; ha1[i1 + k] == ha2[i2 + k]; k++)\n+\t\t\t\t\t\tif (k == xenv->snake_cnt - 1) {\n+\t\t\t\t\t\t\tbest = v;\n+\t\t\t\t\t\t\tspl->i1 = i1;\n+\t\t\t\t\t\t\tspl->i2 = i2;\n+\t\t\t\t\t\t\tbreak;\n+\t\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\tif (best > 0) {\n+\t\t\t\tspl->min_lo = 0;\n+\t\t\t\tspl->min_hi = 1;\n+\t\t\t\treturn ec;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/*\n+\t\t * Enough is enough. We spent too much time here and now we collect\n+\t\t * the furthest reaching path using the (i1 + i2) measure.\n+\t\t */\n+\t\tif (ec >= xenv->mxcost) {\n+\t\t\tlong fbest, fbest1, bbest, bbest1;\n+\n+\t\t\tfbest = -1;\n+\t\t\tfor (d = fmax; d >= fmin; d -= 2) {\n+\t\t\t\ti1 = XDL_MIN(kvdf[d], lim1);\n+\t\t\t\ti2 = i1 - d;\n+\t\t\t\tif (lim2 < i2)\n+\t\t\t\t\ti1 = lim2 + d, i2 = lim2;\n+\t\t\t\tif (fbest < i1 + i2) {\n+\t\t\t\t\tfbest = i1 + i2;\n+\t\t\t\t\tfbest1 = i1;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tbbest = XDL_LINE_MAX;\n+\t\t\tfor (d = bmax; d >= bmin; d -= 2) {\n+\t\t\t\ti1 = XDL_MAX(off1, kvdb[d]);\n+\t\t\t\ti2 = i1 - d;\n+\t\t\t\tif (i2 < off2)\n+\t\t\t\t\ti1 = off2 + d, i2 = off2;\n+\t\t\t\tif (i1 + i2 < bbest) {\n+\t\t\t\t\tbbest = i1 + i2;\n+\t\t\t\t\tbbest1 = i1;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tif ((lim1 + lim2) - bbest < fbest - (off1 + off2)) {\n+\t\t\t\tspl->i1 = fbest1;\n+\t\t\t\tspl->i2 = fbest - fbest1;\n+\t\t\t\tspl->min_lo = 1;\n+\t\t\t\tspl->min_hi = 0;\n+\t\t\t} else {\n+\t\t\t\tspl->i1 = bbest1;\n+\t\t\t\tspl->i2 = bbest - bbest1;\n+\t\t\t\tspl->min_lo = 0;\n+\t\t\t\tspl->min_hi = 1;\n+\t\t\t}\n+\t\t\treturn ec;\n+\t\t}\n+\t}\n+\n+\treturn -1;\n+}\n+\n+\n+/*\n+ * Rule: \"Divide et Impera\". Recursively split the box in sub-boxes by calling\n+ * the box splitting function. Note that the real job (marking changed lines)\n+ * is done in the two boundary reaching checks.\n+ */\n+int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1,\n+\t\t diffdata_t *dd2, long off2, long lim2,\n+\t\t long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv) {\n+\tunsigned long const *ha1 = dd1->ha, *ha2 = dd2->ha;\n+\n+\t/*\n+\t * Shrink the box by walking through each diagonal snake (SW and NE).\n+\t */\n+\tfor (; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++, off2++);\n+\tfor (; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1]; lim1--, lim2--);\n+\n+\t/*\n+\t * If one dimension is empty, then all records on the other one must\n+\t * be obviously changed.\n+\t */\n+\tif (off1 == lim1) {\n+\t\tchar *rchg2 = dd2->rchg;\n+\t\tlong *rindex2 = dd2->rindex;\n+\n+\t\tfor (; off2 < lim2; off2++)\n+\t\t\trchg2[rindex2[off2]] = 1;\n+\t} else if (off2 == lim2) {\n+\t\tchar *rchg1 = dd1->rchg;\n+\t\tlong *rindex1 = dd1->rindex;\n+\n+\t\tfor (; off1 < lim1; off1++)\n+\t\t\trchg1[rindex1[off1]] = 1;\n+\t} else {\n+\t\tlong ec;\n+\t\txdpsplit_t spl;\n+\n+\t\t/*\n+\t\t * Divide ...\n+\t\t */\n+\t\tif ((ec = xdl_split(ha1, off1, lim1, ha2, off2, lim2, kvdf, kvdb,\n+\t\t\t\t need_min, &spl, xenv)) < 0) {\n+\n+\t\t\treturn -1;\n+\t\t}\n+\n+\t\t/*\n+\t\t * ... et Impera.\n+\t\t */\n+\t\tif (xdl_recs_cmp(dd1, off1, spl.i1, dd2, off2, spl.i2,\n+\t\t\t\t kvdf, kvdb, spl.min_lo, xenv) < 0 ||\n+\t\t xdl_recs_cmp(dd1, spl.i1, lim1, dd2, spl.i2, lim2,\n+\t\t\t\t kvdf, kvdb, spl.min_hi, xenv) < 0) {\n+\n+\t\t\treturn -1;\n+\t\t}\n+\t}\n+\n+\treturn 0;\n+}\n+\n+\n+int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n+\t\txdfenv_t *xe) {\n+\tlong ndiags;\n+\tlong *kvd, *kvdf, *kvdb;\n+\txdalgoenv_t xenv;\n+\tdiffdata_t dd1, dd2;\n+\n+\tif (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {\n+\n+\t\treturn -1;\n+\t}\n+\n+\t/*\n+\t * Allocate and setup K vectors to be used by the differential algorithm.\n+\t * One is to store the forward path and one to store the backward path.\n+\t */\n+\tndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;\n+\tif (!(kvd = (long *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) {\n+\n+\t\txdl_free_env(xe);\n+\t\treturn -1;\n+\t}\n+\tkvdf = kvd;\n+\tkvdb = kvdf + ndiags;\n+\tkvdf += xe->xdf2.nreff + 1;\n+\tkvdb += xe->xdf2.nreff + 1;\n+\n+\t/*\n+\t * Classical integer square root approximation using shifts.\n+\t */\n+\txenv.mxcost = 1;\n+\tfor (; ndiags; ndiags >>= 2)\n+\t\txenv.mxcost <<= 1;\n+\tif (xenv.mxcost < XDL_MAX_COST_MIN)\n+\t\txenv.mxcost = XDL_MAX_COST_MIN;\n+\txenv.snake_cnt = XDL_SNAKE_CNT;\n+\txenv.heur_min = XDL_HEUR_MIN_COST;\n+\n+\tdd1.nrec = xe->xdf1.nreff;\n+\tdd1.ha = xe->xdf1.ha;\n+\tdd1.rchg = xe->xdf1.rchg;\n+\tdd1.rindex = xe->xdf1.rindex;\n+\tdd2.nrec = xe->xdf2.nreff;\n+\tdd2.ha = xe->xdf2.ha;\n+\tdd2.rchg = xe->xdf2.rchg;\n+\tdd2.rindex = xe->xdf2.rindex;\n+\n+\tif (xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec,\n+\t\t\t kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0, &xenv) < 0) {\n+\n+\t\txdl_free(kvd);\n+\t\txdl_free_env(xe);\n+\t\treturn -1;\n+\t}\n+\n+\txdl_free(kvd);\n+\n+\treturn 0;\n+}\n+\n+\n+static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2) {\n+\txdchange_t *xch;\n+\n+\tif (!(xch = (xdchange_t *) xdl_malloc(sizeof(xdchange_t))))\n+\t\treturn NULL;\n+\n+\txch->next = xscr;\n+\txch->i1 = i1;\n+\txch->i2 = i2;\n+\txch->chg1 = chg1;\n+\txch->chg2 = chg2;\n+\n+\treturn xch;\n+}\n+\n+\n+int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {\n+\txdchange_t *cscr = NULL, *xch;\n+\tchar *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg;\n+\tlong i1, i2, l1, l2;\n+\n+\t/*\n+\t * Trivial. Collects \"groups\" of changes and creates an edit script.\n+\t */\n+\tfor (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)\n+\t\tif (rchg1[i1 - 1] || rchg2[i2 - 1]) {\n+\t\t\tfor (l1 = i1; rchg1[i1 - 1]; i1--);\n+\t\t\tfor (l2 = i2; rchg2[i2 - 1]; i2--);\n+\n+\t\t\tif (!(xch = xdl_add_change(cscr, i1, i2, l1 - i1, l2 - i2))) {\n+\t\t\t\txdl_free_script(cscr);\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t\tcscr = xch;\n+\t\t}\n+\n+\t*xscr = cscr;\n+\n+\treturn 0;\n+}\n+\n+\n+void xdl_free_script(xdchange_t *xscr) {\n+\txdchange_t *xch;\n+\n+\twhile ((xch = xscr) != NULL) {\n+\t\txscr = xscr->next;\n+\t\txdl_free(xch);\n+\t}\n+}\n+\n+\n+int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n+\t xdemitconf_t const *xecfg, xdemitcb_t *ecb) {\n+\txdchange_t *xscr;\n+\txdfenv_t xe;\n+\n+\tif (xdl_do_diff(mf1, mf2, xpp, &xe) < 0) {\n+\n+\t\treturn -1;\n+\t}\n+\n+\tif (xdl_build_script(&xe, &xscr) < 0) {\n+\n+\t\txdl_free_env(&xe);\n+\t\treturn -1;\n+\t}\n+\n+\tif (xscr) {\n+\t\tif (xdl_emit_diff(&xe, xscr, ecb, xecfg) < 0) {\n+\n+\t\t\txdl_free_script(xscr);\n+\t\t\txdl_free_env(&xe);\n+\t\t\treturn -1;\n+\t\t}\n+\n+\t\txdl_free_script(xscr);\n+\t}\n+\n+\txdl_free_env(&xe);\n+\n+\treturn 0;\n+}\n+\ndiff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h\nnew file mode 100644\nindex 0000000..dd8f3c9\n--- /dev/null\n+++ b/xdiff/xdiffi.h\n@@ -0,0 +1,60 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003 Davide Libenzi\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+\n+#if !defined(XDIFFI_H)\n+#define XDIFFI_H\n+\n+\n+typedef struct s_diffdata {\n+\tlong nrec;\n+\tunsigned long const *ha;\n+\tlong *rindex;\n+\tchar *rchg;\n+} diffdata_t;\n+\n+typedef struct s_xdalgoenv {\n+\tlong mxcost;\n+\tlong snake_cnt;\n+\tlong heur_min;\n+} xdalgoenv_t;\n+\n+typedef struct s_xdchange {\n+\tstruct s_xdchange *next;\n+\tlong i1, i2;\n+\tlong chg1, chg2;\n+} xdchange_t;\n+\n+\n+\n+int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1,\n+\t\t diffdata_t *dd2, long off2, long lim2,\n+\t\t long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv);\n+int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n+\t\txdfenv_t *xe);\n+int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr);\n+void xdl_free_script(xdchange_t *xscr);\n+int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n+\t\t xdemitconf_t const *xecfg);\n+\n+\n+#endif /* #if !defined(XDIFFI_H) */\n+\ndiff --git a/xdiff/xemit.c b/xdiff/xemit.c\nnew file mode 100644\nindex 0000000..2e5d54c\n--- /dev/null\n+++ b/xdiff/xemit.c\n@@ -0,0 +1,141 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003\tDavide Libenzi\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+\n+#include \"xinclude.h\"\n+\n+\n+\n+\n+static long xdl_get_rec(xdfile_t *xdf, long ri, char const **rec);\n+static int xdl_emit_record(xdfile_t *xdf, long ri, char const *pre, xdemitcb_t *ecb);\n+static xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg);\n+\n+\n+\n+\n+static long xdl_get_rec(xdfile_t *xdf, long ri, char const **rec) {\n+\n+\t*rec = xdf->recs[ri]->ptr;\n+\n+\treturn xdf->recs[ri]->size;\n+}\n+\n+\n+static int xdl_emit_record(xdfile_t *xdf, long ri, char const *pre, xdemitcb_t *ecb) {\n+\tlong size, psize = strlen(pre);\n+\tchar const *rec;\n+\n+\tsize = xdl_get_rec(xdf, ri, &rec);\n+\tif (xdl_emit_diffrec(rec, size, pre, psize, ecb) < 0) {\n+\n+\t\treturn -1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+\n+/*\n+ * Starting at the passed change atom, find the latest change atom to be included\n+ * inside the differential hunk according to the specified configuration.\n+ */\n+static xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg) {\n+\txdchange_t *xch, *xchp;\n+\n+\tfor (xchp = xscr, xch = xscr->next; xch; xchp = xch, xch = xch->next)\n+\t\tif (xch->i1 - (xchp->i1 + xchp->chg1) > 2 * xecfg->ctxlen)\n+\t\t\tbreak;\n+\n+\treturn xchp;\n+}\n+\n+\n+int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n+\t\t xdemitconf_t const *xecfg) {\n+\tlong s1, s2, e1, e2, lctx;\n+\txdchange_t *xch, *xche;\n+\n+\tfor (xch = xche = xscr; xch; xch = xche->next) {\n+\t\txche = xdl_get_hunk(xch, xecfg);\n+\n+\t\ts1 = XDL_MAX(xch->i1 - xecfg->ctxlen, 0);\n+\t\ts2 = XDL_MAX(xch->i2 - xecfg->ctxlen, 0);\n+\n+\t\tlctx = xecfg->ctxlen;\n+\t\tlctx = XDL_MIN(lctx, xe->xdf1.nrec - (xche->i1 + xche->chg1));\n+\t\tlctx = XDL_MIN(lctx, xe->xdf2.nrec - (xche->i2 + xche->chg2));\n+\n+\t\te1 = xche->i1 + xche->chg1 + lctx;\n+\t\te2 = xche->i2 + xche->chg2 + lctx;\n+\n+\t\t/*\n+\t\t * Emit current hunk header.\n+\t\t */\n+\t\tif (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2, ecb) < 0)\n+\t\t\treturn -1;\n+\n+\t\t/*\n+\t\t * Emit pre-context.\n+\t\t */\n+\t\tfor (; s1 < xch->i1; s1++)\n+\t\t\tif (xdl_emit_record(&xe->xdf1, s1, \" \", ecb) < 0)\n+\t\t\t\treturn -1;\n+\n+\t\tfor (s1 = xch->i1, s2 = xch->i2;; xch = xch->next) {\n+\t\t\t/*\n+\t\t\t * Merge previous with current change atom.\n+\t\t\t */\n+\t\t\tfor (; s1 < xch->i1 && s2 < xch->i2; s1++, s2++)\n+\t\t\t\tif (xdl_emit_record(&xe->xdf1, s1, \" \", ecb) < 0)\n+\t\t\t\t\treturn -1;\n+\n+\t\t\t/*\n+\t\t\t * Removes lines from the first file.\n+\t\t\t */\n+\t\t\tfor (s1 = xch->i1; s1 < xch->i1 + xch->chg1; s1++)\n+\t\t\t\tif (xdl_emit_record(&xe->xdf1, s1, \"-\", ecb) < 0)\n+\t\t\t\t\treturn -1;\n+\n+\t\t\t/*\n+\t\t\t * Adds lines from the second file.\n+\t\t\t */\n+\t\t\tfor (s2 = xch->i2; s2 < xch->i2 + xch->chg2; s2++)\n+\t\t\t\tif (xdl_emit_record(&xe->xdf2, s2, \"+\", ecb) < 0)\n+\t\t\t\t\treturn -1;\n+\n+\t\t\tif (xch == xche)\n+\t\t\t\tbreak;\n+\t\t\ts1 = xch->i1 + xch->chg1;\n+\t\t\ts2 = xch->i2 + xch->chg2;\n+\t\t}\n+\n+\t\t/*\n+\t\t * Emit post-context.\n+\t\t */\n+\t\tfor (s1 = xche->i1 + xche->chg1; s1 < e1; s1++)\n+\t\t\tif (xdl_emit_record(&xe->xdf1, s1, \" \", ecb) < 0)\n+\t\t\t\treturn -1;\n+\t}\n+\n+\treturn 0;\n+}\n+\ndiff --git a/xdiff/xemit.h b/xdiff/xemit.h\nnew file mode 100644\nindex 0000000..e629417\n--- /dev/null\n+++ b/xdiff/xemit.h\n@@ -0,0 +1,34 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003 Davide Libenzi\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+\n+#if !defined(XEMIT_H)\n+#define XEMIT_H\n+\n+\n+\n+int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n+\t\t xdemitconf_t const *xecfg);\n+\n+\n+\n+#endif /* #if !defined(XEMIT_H) */\n+\ndiff --git a/xdiff/xinclude.h b/xdiff/xinclude.h\nnew file mode 100644\nindex 0000000..9490fc5\n--- /dev/null\n+++ b/xdiff/xinclude.h\n@@ -0,0 +1,42 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003 Davide Libenzi\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+\n+#if !defined(XINCLUDE_H)\n+#define XINCLUDE_H\n+\n+#include \n+#include \n+#include \n+#include \n+#include \n+\n+#include \"xmacros.h\"\n+#include \"xdiff.h\"\n+#include \"xtypes.h\"\n+#include \"xutils.h\"\n+#include \"xprepare.h\"\n+#include \"xdiffi.h\"\n+#include \"xemit.h\"\n+\n+\n+#endif /* #if !defined(XINCLUDE_H) */\n+\ndiff --git a/xdiff/xmacros.h b/xdiff/xmacros.h\nnew file mode 100644\nindex 0000000..4c2fde8\n--- /dev/null\n+++ b/xdiff/xmacros.h\n@@ -0,0 +1,53 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003 Davide Libenzi\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+\n+#if !defined(XMACROS_H)\n+#define XMACROS_H\n+\n+\n+#define GR_PRIME 0x9e370001UL\n+\n+\n+#define XDL_MIN(a, b) ((a) < (b) ? (a): (b))\n+#define XDL_MAX(a, b) ((a) > (b) ? (a): (b))\n+#define XDL_ABS(v) ((v) >= 0 ? (v): -(v))\n+#define XDL_ISDIGIT(c) ((c) >= '0' && (c) <= '9')\n+#define XDL_HASHLONG(v, b) (((unsigned long)(v) * GR_PRIME) >> ((CHAR_BIT * sizeof(unsigned long)) - (b)))\n+#define XDL_PTRFREE(p) do { if (p) { xdl_free(p); (p) = NULL; } } while (0)\n+#define XDL_LE32_PUT(p, v) \\\n+do { \\\n+\tunsigned char *__p = (unsigned char *) (p); \\\n+\t*__p++ = (unsigned char) (v); \\\n+\t*__p++ = (unsigned char) ((v) >> 8); \\\n+\t*__p++ = (unsigned char) ((v) >> 16); \\\n+\t*__p = (unsigned char) ((v) >> 24); \\\n+} while (0)\n+#define XDL_LE32_GET(p, v) \\\n+do { \\\n+\tunsigned char const *__p = (unsigned char const *) (p); \\\n+\t(v) = (unsigned long) __p[0] | ((unsigned long) __p[1]) << 8 | \\\n+\t\t((unsigned long) __p[2]) << 16 | ((unsigned long) __p[3]) << 24; \\\n+} while (0)\n+\n+\n+#endif /* #if !defined(XMACROS_H) */\n+\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nnew file mode 100644\nindex 0000000..27a0879\n--- /dev/null\n+++ b/xdiff/xprepare.c\n@@ -0,0 +1,436 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003 Davide Libenzi\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+\n+#include \"xinclude.h\"\n+\n+\n+\n+#define XDL_KPDIS_RUN 4\n+\n+\n+\n+typedef struct s_xdlclass {\n+\tstruct s_xdlclass *next;\n+\tunsigned long ha;\n+\tchar const *line;\n+\tlong size;\n+\tlong idx;\n+} xdlclass_t;\n+\n+typedef struct s_xdlclassifier {\n+\tunsigned int hbits;\n+\tlong hsize;\n+\txdlclass_t **rchash;\n+\tchastore_t ncha;\n+\tlong count;\n+} xdlclassifier_t;\n+\n+\n+\n+\n+static int xdl_init_classifier(xdlclassifier_t *cf, long size);\n+static void xdl_free_classifier(xdlclassifier_t *cf);\n+static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,\n+\t\t\t xrecord_t *rec);\n+static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n+\t\t\t xdlclassifier_t *cf, xdfile_t *xdf);\n+static void xdl_free_ctx(xdfile_t *xdf);\n+static int xdl_clean_mmatch(char const *dis, long i, long s, long e);\n+static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2);\n+static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2);\n+static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2);\n+\n+\n+\n+\n+static int xdl_init_classifier(xdlclassifier_t *cf, long size) {\n+\tlong i;\n+\n+\tcf->hbits = xdl_hashbits((unsigned int) size);\n+\tcf->hsize = 1 << cf->hbits;\n+\n+\tif (xdl_cha_init(&cf->ncha, sizeof(xdlclass_t), size / 4 + 1) < 0) {\n+\n+\t\treturn -1;\n+\t}\n+\tif (!(cf->rchash = (xdlclass_t **) xdl_malloc(cf->hsize * sizeof(xdlclass_t *)))) {\n+\n+\t\txdl_cha_free(&cf->ncha);\n+\t\treturn -1;\n+\t}\n+\tfor (i = 0; i < cf->hsize; i++)\n+\t\tcf->rchash[i] = NULL;\n+\n+\tcf->count = 0;\n+\n+\treturn 0;\n+}\n+\n+\n+static void xdl_free_classifier(xdlclassifier_t *cf) {\n+\n+\txdl_free(cf->rchash);\n+\txdl_cha_free(&cf->ncha);\n+}\n+\n+\n+static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,\n+\t\t\t xrecord_t *rec) {\n+\tlong hi;\n+\tchar const *line;\n+\txdlclass_t *rcrec;\n+\n+\tline = rec->ptr;\n+\thi = (long) XDL_HASHLONG(rec->ha, cf->hbits);\n+\tfor (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next)\n+\t\tif (rcrec->ha == rec->ha && rcrec->size == rec->size &&\n+\t\t !memcmp(line, rcrec->line, rec->size))\n+\t\t\tbreak;\n+\n+\tif (!rcrec) {\n+\t\tif (!(rcrec = xdl_cha_alloc(&cf->ncha))) {\n+\n+\t\t\treturn -1;\n+\t\t}\n+\t\trcrec->idx = cf->count++;\n+\t\trcrec->line = line;\n+\t\trcrec->size = rec->size;\n+\t\trcrec->ha = rec->ha;\n+\t\trcrec->next = cf->rchash[hi];\n+\t\tcf->rchash[hi] = rcrec;\n+\t}\n+\n+\trec->ha = (unsigned long) rcrec->idx;\n+\n+\thi = (long) XDL_HASHLONG(rec->ha, hbits);\n+\trec->next = rhash[hi];\n+\trhash[hi] = rec;\n+\n+\treturn 0;\n+}\n+\n+\n+static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n+\t\t\t xdlclassifier_t *cf, xdfile_t *xdf) {\n+\tunsigned int hbits;\n+\tlong i, nrec, hsize, bsize;\n+\tunsigned long hav;\n+\tchar const *blk, *cur, *top, *prev;\n+\txrecord_t *crec;\n+\txrecord_t **recs, **rrecs;\n+\txrecord_t **rhash;\n+\tunsigned long *ha;\n+\tchar *rchg;\n+\tlong *rindex;\n+\n+\tif (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0) {\n+\n+\t\treturn -1;\n+\t}\n+\tif (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) {\n+\n+\t\txdl_cha_free(&xdf->rcha);\n+\t\treturn -1;\n+\t}\n+\n+\thbits = xdl_hashbits((unsigned int) narec);\n+\thsize = 1 << hbits;\n+\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *)))) {\n+\n+\t\txdl_free(recs);\n+\t\txdl_cha_free(&xdf->rcha);\n+\t\treturn -1;\n+\t}\n+\tfor (i = 0; i < hsize; i++)\n+\t\trhash[i] = NULL;\n+\n+\tnrec = 0;\n+\tif ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) {\n+\t\tfor (top = blk + bsize;;) {\n+\t\t\tif (cur >= top) {\n+\t\t\t\tif (!(cur = blk = xdl_mmfile_next(mf, &bsize)))\n+\t\t\t\t\tbreak;\n+\t\t\t\ttop = blk + bsize;\n+\t\t\t}\n+\t\t\tprev = cur;\n+\t\t\thav = xdl_hash_record(&cur, top);\n+\t\t\tif (nrec >= narec) {\n+\t\t\t\tnarec *= 2;\n+\t\t\t\tif (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *)))) {\n+\n+\t\t\t\t\txdl_free(rhash);\n+\t\t\t\t\txdl_free(recs);\n+\t\t\t\t\txdl_cha_free(&xdf->rcha);\n+\t\t\t\t\treturn -1;\n+\t\t\t\t}\n+\t\t\t\trecs = rrecs;\n+\t\t\t}\n+\t\t\tif (!(crec = xdl_cha_alloc(&xdf->rcha))) {\n+\n+\t\t\t\txdl_free(rhash);\n+\t\t\t\txdl_free(recs);\n+\t\t\t\txdl_cha_free(&xdf->rcha);\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t\tcrec->ptr = prev;\n+\t\t\tcrec->size = (long) (cur - prev);\n+\t\t\tcrec->ha = hav;\n+\t\t\trecs[nrec++] = crec;\n+\n+\t\t\tif (xdl_classify_record(cf, rhash, hbits, crec) < 0) {\n+\n+\t\t\t\txdl_free(rhash);\n+\t\t\t\txdl_free(recs);\n+\t\t\t\txdl_cha_free(&xdf->rcha);\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tif (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char)))) {\n+\n+\t\txdl_free(rhash);\n+\t\txdl_free(recs);\n+\t\txdl_cha_free(&xdf->rcha);\n+\t\treturn -1;\n+\t}\n+\tmemset(rchg, 0, (nrec + 2) * sizeof(char));\n+\n+\tif (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long)))) {\n+\n+\t\txdl_free(rchg);\n+\t\txdl_free(rhash);\n+\t\txdl_free(recs);\n+\t\txdl_cha_free(&xdf->rcha);\n+\t\treturn -1;\n+\t}\n+\tif (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long)))) {\n+\n+\t\txdl_free(rindex);\n+\t\txdl_free(rchg);\n+\t\txdl_free(rhash);\n+\t\txdl_free(recs);\n+\t\txdl_cha_free(&xdf->rcha);\n+\t\treturn -1;\n+\t}\n+\n+\txdf->nrec = nrec;\n+\txdf->recs = recs;\n+\txdf->hbits = hbits;\n+\txdf->rhash = rhash;\n+\txdf->rchg = rchg + 1;\n+\txdf->rindex = rindex;\n+\txdf->nreff = 0;\n+\txdf->ha = ha;\n+\txdf->dstart = 0;\n+\txdf->dend = nrec - 1;\n+\n+\treturn 0;\n+}\n+\n+\n+static void xdl_free_ctx(xdfile_t *xdf) {\n+\n+\txdl_free(xdf->rhash);\n+\txdl_free(xdf->rindex);\n+\txdl_free(xdf->rchg - 1);\n+\txdl_free(xdf->ha);\n+\txdl_free(xdf->recs);\n+\txdl_cha_free(&xdf->rcha);\n+}\n+\n+\n+int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n+\t\t xdfenv_t *xe) {\n+\tlong enl1, enl2;\n+\txdlclassifier_t cf;\n+\n+\tenl1 = xdl_guess_lines(mf1) + 1;\n+\tenl2 = xdl_guess_lines(mf2) + 1;\n+\n+\tif (xdl_init_classifier(&cf, enl1 + enl2 + 1) < 0) {\n+\n+\t\treturn -1;\n+\t}\n+\n+\tif (xdl_prepare_ctx(mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {\n+\n+\t\txdl_free_classifier(&cf);\n+\t\treturn -1;\n+\t}\n+\tif (xdl_prepare_ctx(mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {\n+\n+\t\txdl_free_ctx(&xe->xdf1);\n+\t\txdl_free_classifier(&cf);\n+\t\treturn -1;\n+\t}\n+\n+\txdl_free_classifier(&cf);\n+\n+\tif (xdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {\n+\n+\t\txdl_free_ctx(&xe->xdf2);\n+\t\txdl_free_ctx(&xe->xdf1);\n+\t\treturn -1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+\n+void xdl_free_env(xdfenv_t *xe) {\n+\n+\txdl_free_ctx(&xe->xdf2);\n+\txdl_free_ctx(&xe->xdf1);\n+}\n+\n+\n+static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n+\tlong r, rdis, rpdis;\n+\n+\tfor (r = 1, rdis = 0, rpdis = 1; (i - r) >= s; r++) {\n+\t\tif (!dis[i - r])\n+\t\t\trdis++;\n+\t\telse if (dis[i - r] == 2)\n+\t\t\trpdis++;\n+\t\telse\n+\t\t\tbreak;\n+\t}\n+\tfor (r = 1; (i + r) <= e; r++) {\n+\t\tif (!dis[i + r])\n+\t\t\trdis++;\n+\t\telse if (dis[i + r] == 2)\n+\t\t\trpdis++;\n+\t\telse\n+\t\t\tbreak;\n+\t}\n+\n+\treturn rpdis * XDL_KPDIS_RUN < (rpdis + rdis);\n+}\n+\n+\n+/*\n+ * Try to reduce the problem complexity, discard records that have no\n+ * matches on the other file. Also, lines that have multiple matches\n+ * might be potentially discarded if they happear in a run of discardable.\n+ */\n+static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {\n+\tlong i, rhi, nreff;\n+\tunsigned long hav;\n+\txrecord_t **recs;\n+\txrecord_t *rec;\n+\tchar *dis, *dis1, *dis2;\n+\n+\tif (!(dis = (char *) xdl_malloc((xdf1->nrec + xdf2->nrec + 2) * sizeof(char)))) {\n+\n+\t\treturn -1;\n+\t}\n+\tmemset(dis, 0, (xdf1->nrec + xdf2->nrec + 2) * sizeof(char));\n+\tdis1 = dis;\n+\tdis2 = dis1 + xdf1->nrec + 1;\n+\n+\tfor (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {\n+\t\thav = (*recs)->ha;\n+\t\trhi = (long) XDL_HASHLONG(hav, xdf2->hbits);\n+\t\tfor (rec = xdf2->rhash[rhi]; rec; rec = rec->next)\n+\t\t\tif (rec->ha == hav && ++dis1[i] == 2)\n+\t\t\t\tbreak;\n+\t}\n+\n+\tfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {\n+\t\thav = (*recs)->ha;\n+\t\trhi = (long) XDL_HASHLONG(hav, xdf1->hbits);\n+\t\tfor (rec = xdf1->rhash[rhi]; rec; rec = rec->next)\n+\t\t\tif (rec->ha == hav && ++dis2[i] == 2)\n+\t\t\t\tbreak;\n+\t}\n+\n+\tfor (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];\n+\t i <= xdf1->dend; i++, recs++) {\n+\t\tif (dis1[i] == 1 ||\n+\t\t (dis1[i] == 2 && !xdl_clean_mmatch(dis1, i, xdf1->dstart, xdf1->dend))) {\n+\t\t\txdf1->rindex[nreff] = i;\n+\t\t\txdf1->ha[nreff] = (*recs)->ha;\n+\t\t\tnreff++;\n+\t\t} else\n+\t\t\txdf1->rchg[i] = 1;\n+\t}\n+\txdf1->nreff = nreff;\n+\n+\tfor (nreff = 0, i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart];\n+\t i <= xdf2->dend; i++, recs++) {\n+\t\tif (dis2[i] == 1 ||\n+\t\t (dis2[i] == 2 && !xdl_clean_mmatch(dis2, i, xdf2->dstart, xdf2->dend))) {\n+\t\t\txdf2->rindex[nreff] = i;\n+\t\t\txdf2->ha[nreff] = (*recs)->ha;\n+\t\t\tnreff++;\n+\t\t} else\n+\t\t\txdf2->rchg[i] = 1;\n+\t}\n+\txdf2->nreff = nreff;\n+\n+\txdl_free(dis);\n+\n+\treturn 0;\n+}\n+\n+\n+/*\n+ * Early trim initial and terminal matching records.\n+ */\n+static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {\n+\tlong i, lim;\n+\txrecord_t **recs1, **recs2;\n+\n+\trecs1 = xdf1->recs;\n+\trecs2 = xdf2->recs;\n+\tfor (i = 0, lim = XDL_MIN(xdf1->nrec, xdf2->nrec); i < lim;\n+\t i++, recs1++, recs2++)\n+\t\tif ((*recs1)->ha != (*recs2)->ha)\n+\t\t\tbreak;\n+\n+\txdf1->dstart = xdf2->dstart = i;\n+\n+\trecs1 = xdf1->recs + xdf1->nrec - 1;\n+\trecs2 = xdf2->recs + xdf2->nrec - 1;\n+\tfor (lim -= i, i = 0; i < lim; i++, recs1--, recs2--)\n+\t\tif ((*recs1)->ha != (*recs2)->ha)\n+\t\t\tbreak;\n+\n+\txdf1->dend = xdf1->nrec - i - 1;\n+\txdf2->dend = xdf2->nrec - i - 1;\n+\n+\treturn 0;\n+}\n+\n+\n+static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2) {\n+\n+\tif (xdl_trim_ends(xdf1, xdf2) < 0 ||\n+\t xdl_cleanup_records(xdf1, xdf2) < 0) {\n+\n+\t\treturn -1;\n+\t}\n+\n+\treturn 0;\n+}\n+\ndiff --git a/xdiff/xprepare.h b/xdiff/xprepare.h\nnew file mode 100644\nindex 0000000..344c569\n--- /dev/null\n+++ b/xdiff/xprepare.h\n@@ -0,0 +1,35 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003 Davide Libenzi\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+\n+#if !defined(XPREPARE_H)\n+#define XPREPARE_H\n+\n+\n+\n+int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n+\t\t xdfenv_t *xe);\n+void xdl_free_env(xdfenv_t *xe);\n+\n+\n+\n+#endif /* #if !defined(XPREPARE_H) */\n+\ndiff --git a/xdiff/xtypes.h b/xdiff/xtypes.h\nnew file mode 100644\nindex 0000000..3593a66\n--- /dev/null\n+++ b/xdiff/xtypes.h\n@@ -0,0 +1,68 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003 Davide Libenzi\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+\n+#if !defined(XTYPES_H)\n+#define XTYPES_H\n+\n+\n+\n+typedef struct s_chanode {\n+\tstruct s_chanode *next;\n+\tlong icurr;\n+} chanode_t;\n+\n+typedef struct s_chastore {\n+\tchanode_t *head, *tail;\n+\tlong isize, nsize;\n+\tchanode_t *ancur;\n+\tchanode_t *sncur;\n+\tlong scurr;\n+} chastore_t;\n+\n+typedef struct s_xrecord {\n+\tstruct s_xrecord *next;\n+\tchar const *ptr;\n+\tlong size;\n+\tunsigned long ha;\n+} xrecord_t;\n+\n+typedef struct s_xdfile {\n+\tchastore_t rcha;\n+\tlong nrec;\n+\tunsigned int hbits;\n+\txrecord_t **rhash;\n+\tlong dstart, dend;\n+\txrecord_t **recs;\n+\tchar *rchg;\n+\tlong *rindex;\n+\tlong nreff;\n+\tunsigned long *ha;\n+} xdfile_t;\n+\n+typedef struct s_xdfenv {\n+\txdfile_t xdf1, xdf2;\n+} xdfenv_t;\n+\n+\n+\n+#endif /* #if !defined(XTYPES_H) */\n+\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nnew file mode 100644\nindex 0000000..01e6765\n--- /dev/null\n+++ b/xdiff/xutils.c\n@@ -0,0 +1,265 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003\tDavide Libenzi\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+\n+#include \"xinclude.h\"\n+\n+\n+\n+#define XDL_GUESS_NLINES 256\n+\n+\n+\n+\n+int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,\n+\t\t xdemitcb_t *ecb) {\n+\tmmbuffer_t mb[2];\n+\n+\tmb[0].ptr = (char *) pre;\n+\tmb[0].size = psize;\n+\tmb[1].ptr = (char *) rec;\n+\tmb[1].size = size;\n+\n+\tif (ecb->outf(ecb->priv, mb, 2) < 0) {\n+\n+\t\treturn -1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+void *xdl_mmfile_first(mmfile_t *mmf, long *size)\n+{\n+\t*size = mmf->size;\n+\treturn mmf->ptr;\n+}\n+\n+\n+void *xdl_mmfile_next(mmfile_t *mmf, long *size)\n+{\n+\treturn NULL;\n+}\n+\n+\n+long xdl_mmfile_size(mmfile_t *mmf)\n+{\n+\treturn mmf->size;\n+}\n+\n+\n+int xdl_cha_init(chastore_t *cha, long isize, long icount) {\n+\n+\tcha->head = cha->tail = NULL;\n+\tcha->isize = isize;\n+\tcha->nsize = icount * isize;\n+\tcha->ancur = cha->sncur = NULL;\n+\tcha->scurr = 0;\n+\n+\treturn 0;\n+}\n+\n+\n+void xdl_cha_free(chastore_t *cha) {\n+\tchanode_t *cur, *tmp;\n+\n+\tfor (cur = cha->head; (tmp = cur) != NULL;) {\n+\t\tcur = cur->next;\n+\t\txdl_free(tmp);\n+\t}\n+}\n+\n+\n+void *xdl_cha_alloc(chastore_t *cha) {\n+\tchanode_t *ancur;\n+\tvoid *data;\n+\n+\tif (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) {\n+\t\tif (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {\n+\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tancur->icurr = 0;\n+\t\tancur->next = NULL;\n+\t\tif (cha->tail)\n+\t\t\tcha->tail->next = ancur;\n+\t\tif (!cha->head)\n+\t\t\tcha->head = ancur;\n+\t\tcha->tail = ancur;\n+\t\tcha->ancur = ancur;\n+\t}\n+\n+\tdata = (char *) ancur + sizeof(chanode_t) + ancur->icurr;\n+\tancur->icurr += cha->isize;\n+\n+\treturn data;\n+}\n+\n+\n+void *xdl_cha_first(chastore_t *cha) {\n+\tchanode_t *sncur;\n+\n+\tif (!(cha->sncur = sncur = cha->head))\n+\t\treturn NULL;\n+\n+\tcha->scurr = 0;\n+\n+\treturn (char *) sncur + sizeof(chanode_t) + cha->scurr;\n+}\n+\n+\n+void *xdl_cha_next(chastore_t *cha) {\n+\tchanode_t *sncur;\n+\n+\tif (!(sncur = cha->sncur))\n+\t\treturn NULL;\n+\tcha->scurr += cha->isize;\n+\tif (cha->scurr == sncur->icurr) {\n+\t\tif (!(sncur = cha->sncur = sncur->next))\n+\t\t\treturn NULL;\n+\t\tcha->scurr = 0;\n+\t}\n+\n+\treturn (char *) sncur + sizeof(chanode_t) + cha->scurr;\n+}\n+\n+\n+long xdl_guess_lines(mmfile_t *mf) {\n+\tlong nl = 0, size, tsize = 0;\n+\tchar const *data, *cur, *top;\n+\n+\tif ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {\n+\t\tfor (top = data + size; nl < XDL_GUESS_NLINES;) {\n+\t\t\tif (cur >= top) {\n+\t\t\t\ttsize += (long) (cur - data);\n+\t\t\t\tif (!(cur = data = xdl_mmfile_next(mf, &size)))\n+\t\t\t\t\tbreak;\n+\t\t\t\ttop = data + size;\n+\t\t\t}\n+\t\t\tnl++;\n+\t\t\tif (!(cur = memchr(cur, '\\n', top - cur)))\n+\t\t\t\tcur = top;\n+\t\t\telse\n+\t\t\t\tcur++;\n+\t\t}\n+\t\ttsize += (long) (cur - data);\n+\t}\n+\n+\tif (nl && tsize)\n+\t\tnl = xdl_mmfile_size(mf) / (tsize / nl);\n+\n+\treturn nl + 1;\n+}\n+\n+\n+unsigned long xdl_hash_record(char const **data, char const *top) {\n+\tunsigned long ha = 5381;\n+\tchar const *ptr = *data;\n+\n+\tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n+\t\tha += (ha << 5);\n+\t\tha ^= (unsigned long) *ptr;\n+\t}\n+\t*data = ptr < top ? ptr + 1: ptr;\n+\n+\treturn ha;\n+}\n+\n+\n+unsigned int xdl_hashbits(unsigned int size) {\n+\tunsigned int val = 1, bits = 0;\n+\n+\tfor (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++);\n+\treturn bits ? bits: 1;\n+}\n+\n+\n+int xdl_num_out(char *out, long val) {\n+\tchar *ptr, *str = out;\n+\tchar buf[32];\n+\n+\tptr = buf + sizeof(buf) - 1;\n+\t*ptr = '\\0';\n+\tif (val < 0) {\n+\t\t*--ptr = '-';\n+\t\tval = -val;\n+\t}\n+\tfor (; val && ptr > buf; val /= 10)\n+\t\t*--ptr = \"0123456789\"[val % 10];\n+\tif (*ptr)\n+\t\tfor (; *ptr; ptr++, str++)\n+\t\t\t*str = *ptr;\n+\telse\n+\t\t*str++ = '0';\n+\t*str = '\\0';\n+\n+\treturn str - out;\n+}\n+\n+\n+long xdl_atol(char const *str, char const **next) {\n+\tlong val, base;\n+\tchar const *top;\n+\n+\tfor (top = str; XDL_ISDIGIT(*top); top++);\n+\tif (next)\n+\t\t*next = top;\n+\tfor (val = 0, base = 1, top--; top >= str; top--, base *= 10)\n+\t\tval += base * (long)(*top - '0');\n+\treturn val;\n+}\n+\n+\n+int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, xdemitcb_t *ecb) {\n+\tint nb = 0;\n+\tmmbuffer_t mb;\n+\tchar buf[128];\n+\n+\tmemcpy(buf, \"@@ -\", 4);\n+\tnb += 4;\n+\n+\tnb += xdl_num_out(buf + nb, c1 ? s1: 0);\n+\n+\tmemcpy(buf + nb, \",\", 1);\n+\tnb += 1;\n+\n+\tnb += xdl_num_out(buf + nb, c1);\n+\n+\tmemcpy(buf + nb, \" +\", 2);\n+\tnb += 2;\n+\n+\tnb += xdl_num_out(buf + nb, c2 ? s2: 0);\n+\n+\tmemcpy(buf + nb, \",\", 1);\n+\tnb += 1;\n+\n+\tnb += xdl_num_out(buf + nb, c2);\n+\n+\tmemcpy(buf + nb, \" @@\\n\", 4);\n+\tnb += 4;\n+\n+\tmb.ptr = buf;\n+\tmb.size = nb;\n+\tif (ecb->outf(ecb->priv, &mb, 1) < 0)\n+\t\treturn -1;\n+\n+\treturn 0;\n+}\n+\ndiff --git a/xdiff/xutils.h b/xdiff/xutils.h\nnew file mode 100644\nindex 0000000..428a4bb\n--- /dev/null\n+++ b/xdiff/xutils.h\n@@ -0,0 +1,44 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003 Davide Libenzi\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+\n+#if !defined(XUTILS_H)\n+#define XUTILS_H\n+\n+\n+int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,\n+\t\t xdemitcb_t *ecb);\n+int xdl_cha_init(chastore_t *cha, long isize, long icount);\n+void xdl_cha_free(chastore_t *cha);\n+void *xdl_cha_alloc(chastore_t *cha);\n+void *xdl_cha_first(chastore_t *cha);\n+void *xdl_cha_next(chastore_t *cha);\n+long xdl_guess_lines(mmfile_t *mf);\n+unsigned long xdl_hash_record(char const **data, char const *top);\n+unsigned int xdl_hashbits(unsigned int size);\n+int xdl_num_out(char *out, long val);\n+long xdl_atol(char const *str, char const **next);\n+int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, xdemitcb_t *ecb);\n+\n+\n+\n+#endif /* #if !defined(XUTILS_H) */\n+\n"},{"id":"17911","messageId":"7vk6ajxbe5.fsf@assigned-by-dhcp.cox.net","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603241938510.15714@g5.osdl.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-25T06:54:10Z","receivedAt":"2006-03-25T06:54:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> This uses a simplified libxdiff setup to generate unified diffs _without_ \n> doing fork/execve of GNU \"diff\".\n\nGood stuff.\n\n> Now, in the interest of full disclosure, I should also point out a few \n> downsides:\n>\n> - the libxdiff algorithm is different,...\n>\n> - GNU diff does some nice eye-candy, like trying to figure out what the \n> last function was, and adding that information to the \"@@ ..\" line. \n> libxdiff doesn't do that. \n\nThat's kind of sad --- Documentation/SubmittingPatches request\npeople to say \"diff -u -p\".\n\n> - The libxdiff thing has some known deficiencies. In particular, it gets \n> the \"\\No newline at end of file\" case wrong. So this is currently for \n> the experimental branch only. I hope Davide will help fix it.\n\nAnother thing I noticed is that while libxdiff always shows full\nline counts \"-n,m +l,k\" GNU seems to omit them when it can (m,k\n<=1). I am not sure if apply.c is set up to grok what libxdiff\nemits correctly. Running t/t1200 shows some obvious examples.\n"},{"id":"17913","messageId":"7vu09nvuqr.fsf@assigned-by-dhcp.cox.net","threadId":"3717","inReplyTo":"7vk6ajxbe5.fsf@assigned-by-dhcp.cox.net","subject":"Re: Use a *real* built-in diff generator","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-25T07:39:08Z","receivedAt":"2006-03-25T07:39:08Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Linus Torvalds writes:\n>\n>> This uses a simplified libxdiff setup to generate unified diffs _without_ \n>> doing fork/execve of GNU \"diff\".\n>\n> Good stuff.\n\nThe reason I like this is because I was thinking about doing\nin-core diffs for different purpose when I was driving to work\nthis morning [*1*] --- to make pickaxe a more useful building\nblock.\n\nCurrently, pickaxe tries to do an exact match to find the case\nwhere a given substring S appears in the version C of the file\nbut not in the its parent C^n (1 <= n), and then it tells the\ndiffcore to emit the differences. The user (probably only me on\nthis list?) is expected to look at the change, make an\nintelligent decision to feed a matching substring S' found in\nC^n and restart from that commit.\n\nTo be a useful \"content movement tracker\", the process of\nfinding matching 'old shape' in the previous version and\nre-feeding it to pickaxe should be automated if possible, and\nin-core diff machinery would be one component to help that.\n\nFor example, if I wanted to find when I stole 'ls-files -t'\nfeature from Cogito, I would first run less ls-files.c; I see\nthese and am reasonably sure these relate to what I am looking\nfor:\n\n\t...\n static const char *tag_cached = \"\";\n static const char *tag_unmerged = \"\";\n static const char *tag_removed = \"\";\n static const char *tag_other = \"\";\n static const char *tag_killed = \"\";\n static const char *tag_modified = \"\";\n\t...\n\nSo I run:\n\n\t$ git whatchanged -S'static const char *tag_other = \"\";\n static const char *tag_killed = \"\";\n\tstatic const char *tag_modified' -p master -- ls-files.c\n\nwhich finds:\n\n Author: Junio C Hamano \n Date: Mon Sep 19 15:11:15 2005 -0700\n\n Show modified files in git-ls-files\n\t...\n @@ -28,6 +29,7 @@ static const char *tag_unmerged = \"\";\n static const char *tag_removed = \"\";\n static const char *tag_other = \"\";\n static const char *tag_killed = \"\";\n +static const char *tag_modified = \"\";\n\nbut that is not what I am interested in; the matching \"old\nshape\" is the version before the tag_modified was added (and it\nalready had other tag_xxx in there). So with the current\npickaxe, I manually re-run whatchanged starting from the found\ncommit with modified string like this:\n\n\t$ git whatchanged -S'static const char *tag_removed = \"\";\n static const char *tag_other = \"\";\n static const char *tag_killed = \"\";' -p $that_commit -- ls-files.c\n\nin order to further drill down.\n\nA truly useful pickaxe should take two line numbers and a\nfilename (to name the range of lines I am interested in) from\nthe starting version, notice when that range changes shape, and\nafter showing the found commit, replace the range with the one\nmatching from the older commit and continue.\n\n[Footnote]\n\n*1* When you are bogged down in a boring day-job, your brain\ntends to try to compensate by spending as much your waking time\nas possible on thinking about more interesting and more useful\nstuff -- like git ;-).\n"},{"id":"17916","messageId":"Pine.LNX.4.64.0603250025550.1704@alien.or.mcafeemobile.com","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603241938510.15714@g5.osdl.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-03-25T09:03:38Z","receivedAt":"2006-03-25T09:03:38Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Fri, 24 Mar 2006, Linus Torvalds wrote:\n\n> - the libxdiff algorithm is different, and I bet GNU diff has gotten a\n> lot more testing. And the thing is, generating a diff is not an exact\n> science - you can get two different diffs (and you will), and they can\n> both be perfectly valid. So it's not possible to \"validate\" the\n> libxdiff output by just comparing it against GNU diff.\n\nCorrect, the diff(A, B) is not unique. If you look inside the test \ndirectory, there's an xregression binary that does:\n\n1) Random generate A\n2) Create B by random changing A\n3) Create D=A-B\n4) Verify that B+D==A and A-D==B (using the library patch function)\n\nIt does and repeat this operation continuosly, for both text (using text \ndiff/patch) and binary (using binary diff/patch). It ran several days \nw/out finding errors, so I've a good confidence about it.\n\n\n\n> - GNU diff does some nice eye-candy, like trying to figure out what the\n> last function was, and adding that information to the \"@@ ..\" line.\n> libxdiff doesn't do that.\n\nThis, I don't think is a natural part of a generic text/binary diff/patch \nlibrary. If you feel it is important, you could post-process the diff, but \nIMO is kinda bogus.\n\n\n\n> - The libxdiff thing has some known deficiencies. In particular, it gets\n> the \"\\No newline at end of file\" case wrong. So this is currently for\n> the experimental branch only. I hope Davide will help fix it.\n\nThis, need fix. At the moment, in my projects I enforce the final EOL if \nmissing (look inside the file-load function inside the test directory).\n\n\n\n> Technical note: this is based on libxdiff-0.17, but I did some surgery to\n> get rid of the extraneous fat - stuff that git doesn't need, and seriously\n> cutting down on mmfile_t, which had much more capabilities than the diff\n> algorithm either needed or used. In this version, \"mmfile_t\" is just a\n> trivial tuple.\n>\n> That said, I tried to keep the differences to simple removals, so that you\n> can do a diff between this and the libxdiff origin, and you'll basically\n> see just things getting deleted. Even the mmfile_t simplifications are\n> left in a state where the diffs should be readable.\n\nHere you have two options. Either you suck in the libxdiff code and change \nit to drop/change the stuff you don't want (the whole libxdiff library \ncompiled with -O2 is 33KB though). Or you use the library as is, like \nyou'd use libz & co. Once you have your own load-mmfile, you can pretty \nmuch feed libxdiff as is. Not my choice though, so pick the one you think \nbest for your project.\nI see you use XDF_NEED_MINIMAL. You might want to do some experiments with \nand without, to see how diff size changes, versus time.\n\n\n\n> Apologies to Davide, whom I'd love to get feedback on this all from (I\n> wrote my own \"fill_mmfile()\" for the new simpler mmfile_t format: the old\n\nIf you look inside the test directory, I use a similar function. The \nreason of the mmfile born for a use I made of the library inside an \nembedded device where there was no guarantee of contiguos memory, and dat \ncould have been generated in chunks. OTOH an mmfile with a single block is \na perfectly valid mmfile ;)\n\n\n\nPS: Another solution you have is to libify GNU diff by creating a\n diff_main() & co., usual libification wrapping. You'd need to change\n the exit() that diff throws with a setjmp/longjmp, and make it call\n you own mem alloc/free functions, in order to free up memory diff does\n not clear on return. I did it once, not many changes. This solution\n will give you all the GNU diff crud, like function names, etc...\n\n\n\n- Davide\n"},{"id":"17918","messageId":"e5bfff550603250135h42b0da62x84973483798d969c@mail.gmail.com","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603241938510.15714@g5.osdl.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-03-25T09:35:39Z","receivedAt":"2006-03-25T09:35:39Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 3/25/06, Linus Torvalds wrote:\n>\n> This uses a simplified libxdiff setup to generate unified diffs _without_\n> doing fork/execve of GNU \"diff\".\n>\n> This has several huge advantages, for example:\n>\n> Before:\n>\n> [torvalds@g5 linux]$ time git diff v2.6.16.. > /dev/null\n>\n> real 0m24.818s\n> user 0m13.332s\n> sys 0m8.664s\n>\n> After:\n>\n> [torvalds@g5 linux]$ time git diff v2.6.16.. > /dev/null\n>\n> real 0m4.563s\n> user 0m2.944s\n> sys 0m1.580s\n>\n\nCurrently 'getting the diffs' is the second most important time\nconsumer of annotation calculation (just after getting the file\nhistory). On big and heavily modified files, as drivers/net/tg3.c in\nLinux tree, this can be very slow (around 10s on my box).\n\nThe profiling has been done on qgit, but I think it is of general\ninterest because qgit uses git-rev-list and git-diff-tree -p to get\nfile's history and diffs respectively.\n\nSo this patch is more then welcomed! Thanks!\n\nMarco\n"},{"id":"17935","messageId":"81b0412b0603250456o7f5925e6kbbfc0054aec564a1@mail.gmail.com","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603241938510.15714@g5.osdl.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-03-25T12:56:59Z","receivedAt":"2006-03-25T12:56:59Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 3/25/06, Linus Torvalds wrote:\n>\n> This uses a simplified libxdiff setup to generate unified diffs _without_\n> doing fork/execve of GNU \"diff\".\n>\n> This has several huge advantages, for example:\n>\n\nEven more impressive on Cygwin (>50x!):\n\n.../git-win$ time git --exec-path=$(pwd) diff initial.. > /dev/null\nreal 0m1.485s\nuser 0m0.567s\nsys 0m0.840s\n\n../git-win$ time git diff initial.. >/dev/null\nreal 1m20.781s\nuser 0m31.806s\nsys 0m20.717s\n"},{"id":"17936","messageId":"118833cc0603250544h289f385fo683ec7b40cdb0ed@mail.gmail.com","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603241938510.15714@g5.osdl.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Morten Welinder","fromEmail":"mwelinder@gmail.com","sentAt":"2006-03-25T13:44:50Z","receivedAt":"2006-03-25T13:44:50Z","isPatch":false,"sender":{"key":"mwelinder@gmail.com","avatar":null},"body":"The primary correctness concern is that patch understands\nthe output, ie., the libxdiff + patch brings out right back.\n\nIt ought to be fairly easy to script checking every file change\nthat ever went into a git repository. You won't cover evil\ncases that way, but it should provide some assurances that\nnothing is too wrong.\n\nM.\n"},{"id":"17938","messageId":"Pine.LNX.4.64.0603250734130.15714@g5.osdl.org","threadId":"3717","inReplyTo":"118833cc0603250544h289f385fo683ec7b40cdb0ed@mail.gmail.com","subject":"Re: Use a *real* built-in diff generator","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-25T15:36:19Z","receivedAt":"2006-03-25T15:36:19Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 25 Mar 2006, Morten Welinder wrote:\n>\n> The primary correctness concern is that patch understands\n> the output, ie., the libxdiff + patch brings out right back.\n> \n> It ought to be fairly easy to script checking every file change\n> that ever went into a git repository. You won't cover evil\n> cases that way, but it should provide some assurances that\n> nothing is too wrong.\n\nI did _some_ tests, and especially \"git-apply\" is very useful, since it is \nactually a lot more anal than regular \"patch\".\n\nIt all worked fine except for files that don't end with a newline. Davide \npoints out that he just forces the EOLN at the end in his test harness, \nbut that's not exactly acceptable for a real project that actually has \nreal cases.\n\nI'll be taking a look at trying to fix it. \n\n\t\tLinus\n"},{"id":"17939","messageId":"Pine.LNX.4.64.0603250742340.15714@g5.osdl.org","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603250734130.15714@g5.osdl.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-25T15:56:03Z","receivedAt":"2006-03-25T15:56:03Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 25 Mar 2006, Linus Torvalds wrote:\n> \n> I'll be taking a look at trying to fix it. \n\nActually, it ended up being easier than I expected it to be.\n\nThis (on top of the previous patch) should fix it.\n\nAnd yes, with this, I can pass the output of\n\n\tgit diff v2.6.16..\n\nto \"git-apply\" and it not only passes the \"--stat\" thing (which verifies \nthat git-apply is happy with the diff) but it also results in exactly the \nsame tree when applied on top of v2.6.16 (and the patch has two cases \nwhere the \"no newline\" test triggers).\n\nThe speed-up is quite noticeable, especially when doing things like\n\n\tgit diff v2.6.16.. | git-apply --stat\n\nwhich just _used_ to be painfully slow (25 seconds for me) and is now \nunder five seconds. That's the difference between \"twiddling your thumbs\" \nand \"ok, that wasn't too bad\".\n\nNow, to be honest, the real reason I wanted a built-in diff wasn't the \nspeed advantage, but the fact that it's so much more flexible. The lack of \nfork/exec just allows us to do things that weren't practical before.\n\n\t\tLinus\n\n----\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex 01e6765..b68afa2 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -31,14 +31,22 @@\n \n int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,\n \t\t xdemitcb_t *ecb) {\n-\tmmbuffer_t mb[2];\n+\tmmbuffer_t mb[3];\n+\tint i;\n \n \tmb[0].ptr = (char *) pre;\n \tmb[0].size = psize;\n \tmb[1].ptr = (char *) rec;\n \tmb[1].size = size;\n+\ti = 2;\n \n-\tif (ecb->outf(ecb->priv, mb, 2) < 0) {\n+\tif (!size || rec[size-1] != '\\n') {\n+\t\tmb[2].ptr = \"\\n\\\\ No newline at end of file\\n\";\n+\t\tmb[2].size = strlen(mb[2].ptr);\n+\t\ti = 3;\n+\t}\n+\n+\tif (ecb->outf(ecb->priv, mb, i) < 0) {\n \n \t\treturn -1;\n \t}\n"},{"id":"17940","messageId":"Pine.LNX.4.64.0603250759090.15714@g5.osdl.org","threadId":"3717","inReplyTo":"81b0412b0603250456o7f5925e6kbbfc0054aec564a1@mail.gmail.com","subject":"Re: Use a *real* built-in diff generator","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-25T16:09:43Z","receivedAt":"2006-03-25T16:09:43Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 25 Mar 2006, Alex Riesen wrote:\n> \n> Even more impressive on Cygwin (>50x!):\n> \n> .../git-win$ time git --exec-path=$(pwd) diff initial.. > /dev/null\n> real 0m1.485s\n> user 0m0.567s\n> sys 0m0.840s\n> \n> ../git-win$ time git diff initial.. >/dev/null\n> real 1m20.781s\n> user 0m31.806s\n> sys 0m20.717s\n\nYeah. That's the difference between \"unusable\" and \"retty damn good\".\n\nNow, if we didn't even bother to write temporary files (and just did the \nobject entirely in memory) I'd be even happier. I suspect it would help \ncygwin more too.\n\nI've done a \"strace\" on \"git-diff-tree\" doing the 5-second diff of the \nkernel tree, and almost all of it looks like this:\n\n\t..\n\topen(\"/tmp/.diff_WgWi1X\", O_RDWR|O_CREAT|O_EXCL, 0600) = 3\n\twrite(3, \"/*\\n * Driver for Digigram pcxhr \"..., 6121) = 6121\n\tclose(3) = 0\n\topen(\"/tmp/.diff_hCzrFe\", O_RDWR|O_CREAT|O_EXCL, 0600) = 3\n\twrite(3, \"/*\\n * Driver for Digigram pcxhr \"..., 6138) = 6138\n\tclose(3) = 0\n\trt_sigaction(SIGINT, {0x1000f650, [INT], SA_RESTART}, {0x1000f650, [INT], SA_RESTART}, 8) = 0\n\topen(\"/tmp/.diff_WgWi1X\", O_RDONLY) = 3\n\tfstat64(3, {st_mode=S_IFREG|0600, st_size=6121, ...}) = 0\n\tread(3, \"/*\\n * Driver for Digigram pcxhr \"..., 6121) = 6121\n\tclose(3) = 0\n\topen(\"/tmp/.diff_hCzrFe\", O_RDONLY) = 3\n\tfstat64(3, {st_mode=S_IFREG|0600, st_size=6138, ...}) = 0\n\tread(3, \"/*\\n * Driver for Digigram pcxhr \"..., 6138) = 6138\n\tclose(3) = 0\n\tunlink(\"/tmp/.diff_WgWi1X\") = 0\n\tunlink(\"/tmp/.diff_hCzrFe\") = 0\n\t..\n\nwhich is just ridiculous. Those are _literally_ the only system calls we \ndo any more after the conversion, if you ignore a few \"brk()\" calls here \nand there to allocate/free memory and obviously a number of \"write(1,...\" \ncalls to actually write out the result!\n\n(This is with a fully packed tree, so we just set up the object store with \na single mmap at the beginning, which is why there are no reads to read \nthe actual source contents).\n\nNow, Linux is good at temp-files, but still: it adds nothing but overhead \nto first write out and then read back in over three _thousand_ filepairs \n(only to delete them immediately after reading), when the new code \nactually just wants to do the diff in memory anyway.\n\n\t\tLinus\n"},{"id":"17941","messageId":"Pine.LNX.4.64.0603250927410.15714@g5.osdl.org","threadId":"3717","inReplyTo":"7vk6ajxbe5.fsf@assigned-by-dhcp.cox.net","subject":"Re: Use a *real* built-in diff generator","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-25T17:28:47Z","receivedAt":"2006-03-25T17:28:47Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 24 Mar 2006, Junio C Hamano wrote:\n> \n> Another thing I noticed is that while libxdiff always shows full\n> line counts \"-n,m +l,k\" GNU seems to omit them when it can (m,k\n> <=1). I am not sure if apply.c is set up to grok what libxdiff\n> emits correctly. Running t/t1200 shows some obvious examples.\n\nActually, the GNU diff output is the special case, and git-apply handles \nit as such. \n\nWe could make libxdiff do the same @@-shortening, but it doesn't seem to \nbe huge deal.\n\n\t\tLinus\n"},{"id":"17942","messageId":"Pine.LNX.4.64.0603251009500.11968@alien.or.mcafeemobile.com","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603250742340.15714@g5.osdl.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-03-25T18:14:32Z","receivedAt":"2006-03-25T18:14:32Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Sat, 25 Mar 2006, Linus Torvalds wrote:\n\n> On Sat, 25 Mar 2006, Linus Torvalds wrote:\n>>\n>> I'll be taking a look at trying to fix it.\n>\n> Actually, it ended up being easier than I expected it to be.\n>\n> This (on top of the previous patch) should fix it.\n>\n> And yes, with this, I can pass the output of\n>\n> \tgit diff v2.6.16..\n>\n> to \"git-apply\" and it not only passes the \"--stat\" thing (which verifies\n> that git-apply is happy with the diff) but it also results in exactly the\n> same tree when applied on top of v2.6.16 (and the patch has two cases\n> where the \"no newline\" test triggers).\n>\n> The speed-up is quite noticeable, especially when doing things like\n>\n> \tgit diff v2.6.16.. | git-apply --stat\n>\n> which just _used_ to be painfully slow (25 seconds for me) and is now\n> under five seconds. That's the difference between \"twiddling your thumbs\"\n> and \"ok, that wasn't too bad\".\n\nYeah, that works. It has never been an algorithm problem, but a diff \noutput one. And following what GNU diff does looks fine to me. I'll fix \nlibxdiff with that. I also have to teach libxdiff patch algo to recognize \nthe tag and do the right thing during the patch operation.\n\n\n\n> Now, to be honest, the real reason I wanted a built-in diff wasn't the\n> speed advantage, but the fact that it's so much more flexible. The lack of\n> fork/exec just allows us to do things that weren't practical before.\n\nI don't know if git is patch-forkexec sensitive or not, but if it is you \ncan take a look at libxdiff's xdl_patch(), or at libifying GNU patch.\n\n\n\n- Davide\n"},{"id":"17943","messageId":"Pine.LNX.4.64.0603251030340.15714@g5.osdl.org","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603251009500.11968@alien.or.mcafeemobile.com","subject":"Re: Use a *real* built-in diff generator","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-25T18:39:03Z","receivedAt":"2006-03-25T18:39:03Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 25 Mar 2006, Davide Libenzi wrote:\n> \n> > Now, to be honest, the real reason I wanted a built-in diff wasn't the\n> > speed advantage, but the fact that it's so much more flexible. The lack of\n> > fork/exec just allows us to do things that weren't practical before.\n> \n> I don't know if git is patch-forkexec sensitive or not, but if it is you can\n> take a look at libxdiff's xdl_patch(), or at libifying GNU patch.\n\nI don't need \"patch\", since I wrote my own anyway. It's just called \n\"apply\" instead of \"patch\".\n\nDoing \"apply\" is not only much simpler than doing \"diff\", but I needed my \nown much earlier: it's much more timing-critical for me (applying 200 \npatches in one go), and git needed something that could honor renames and \ncopies, and the mode bits too.\n\nBesides, I hate how GNU patch bends over backwards in applying crap that \nisn't a proper patch at all (whitespace-corruption, you name it: GNU patch \nwill accept it). Also, I made \"git-apply\" be all-or-nothing: either it \napplies the _whole_ patch (across many different files) or it applies none \nof it. With GNU patch, if you get an error on the fifth file, the four \nfirst files have been modified already - aarrgghhh..\n\nSee \"apply.c\" for details if you care. It's stupid, but it works (and it \n_only_ handles unified diffs - with the git extensions, of course).\n\n(I also absolutely hate the GNU coding standards, so I'd be very unlikely \nto libify any of the FSF projects. With libxdiff, I can actually read the \ncode: it may be a bit dense at times, but at least the code is written to \nbe readable, unlike most FSF projects).\n\n\t\t\tLinus\n"},{"id":"17944","messageId":"Pine.LNX.4.64.0603251040190.15714@g5.osdl.org","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603251009500.11968@alien.or.mcafeemobile.com","subject":"Re: Use a *real* built-in diff generator","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-25T18:48:03Z","receivedAt":"2006-03-25T18:48:03Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 25 Mar 2006, Davide Libenzi wrote:\n>\n> I also have to teach libxdiff patch algo to recognize the tag and do the\n> right thing during the patch operation.\n\nBtw, git-apply does it, and it's actually quite simple: the code to handle \nthe \"\\ No newline\" case is literally just this:\n\n /*\n * \"plen\" is how much of the line we should use for \n * the actual patch data. Normally we just remove the\n * first character on the line, but if the line is\n * followed by \"\\ No newline\", then we also remove the\n * last one (which is the newline, of course).\n */\n plen = len-1;\n if (len < size && patch[len] == '\\\\')\n plen--;\n\nif we just remove the last '\\n' on a line, if the _next_ line starts with \na '\\\\' (so the git-apply code actually depends on knowing that the patch \ntext is dense, and that it's also padded out so that you can look one byte \npast the end of the diff and it won't be a '\\\\').\n\nI don't know how well that fits into xpatch (I never looked at the patch \nside, since I already had my own ;), but my point being that handling this \nspecial case _can_ be very simple if the data structures are just set up \nfor it.\n\nIt's also important to realize that (a) you can't actually check the \"No \nnewline\" string, because that depends on your locale and (b) it's not \nnecessarily at the _end_ of the patch, because you can have a patch that \nlooks like\n\n\t-\tnext-to-last-line\n\t-\tlast-line\n\t\\ No newline at end of file\n\t+\tnew-end-of-file\n\t+\tnew-last-line\n\t\\ No newline at end of file\n\nie the first \"\\ No newline\" is in the middle, because it relates to the \nlast removed line (while the second one obviously relates to the last \nadded one).\n\nThe xdiff patch I sent out automatically does that when generating these \nthings, of course.\n\n\t\t\tLinus\n"},{"id":"17945","messageId":"7v7j6iwbdk.fsf@assigned-by-dhcp.cox.net","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603250742340.15714@g5.osdl.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-25T19:52:07Z","receivedAt":"2006-03-25T19:52:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Sat, 25 Mar 2006, Linus Torvalds wrote:\n>> \n>> I'll be taking a look at trying to fix it. \n>\n> Actually, it ended up being easier than I expected it to be.\n>\n> This (on top of the previous patch) should fix it.\n>...\n> +\tif (!size || rec[size-1] != '\\n') {\n> +\t\tmb[2].ptr = \"\\n\\\\ No newline at end of file\\n\";\n>... \n\nThanks. Here is what I cooked last night, which I rebased\non top of your two patches, to:\n\n - Punt \"binary\" diff like GNU does;\n\n - Minimally support GIT_DIFF_OPTS to allow passing -u0;\n\n - Omit ---/+++ lines when we do not have any diff output;\n\n - Adjust the tests to \"@@ -k,l +m,n @@\" form.\n\n - Adjust the tests to lack of \"diff -p\".\n\nThe first two are hacks but I think they are good enough hacks\nfor real life. The third one is a real fix. I agree with you\nthat libxdiff form is more rational, and that is the\njustification for the fourth point.\n\n-- >8 --\ndiff --git a/diff.c b/diff.c\nindex f6a1f5d..cd2ce0f 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -212,13 +212,34 @@\n \treturn 0;\n }\n \n+struct emit_callback {\n+\tconst char **label_path;\n+};\n+\n static int fn_out(void *priv, mmbuffer_t *mb, int nbuf)\n {\n \tint i;\n+\tstruct emit_callback *ecbdata = priv;\n \n+\tif (ecbdata->label_path[0]) {\n+\t\tprintf(\"--- %s\\n\", ecbdata->label_path[0]);\n+\t\tprintf(\"+++ %s\\n\", ecbdata->label_path[1]);\n+\t\tecbdata->label_path[0] = ecbdata->label_path[1] = NULL;\n+\t}\n \tfor (i = 0; i < nbuf; i++)\n \t\tif (!fwrite(mb[i].ptr, mb[i].size, 1, stdout))\n \t\t\treturn -1;\n+\treturn 0;\n+}\n+\n+#define FIRST_FEW_BYTES 8000\n+static int mmfile_is_binary(mmfile_t *mf)\n+{\n+\tlong sz = mf->size;\n+\tif (FIRST_FEW_BYTES < sz)\n+\t\tsz = FIRST_FEW_BYTES;\n+\tif (memchr(mf->ptr, 0, sz))\n+\t\treturn 1;\n \treturn 0;\n }\n \n@@ -306,22 +327,32 @@\n \tif (label_path[1][0] != '/')\n \t\tlabel_path[1] = quote_two(\"b/\", name_b);\n \n-\tprintf(\"--- %s\\n\", label_path[0]);\n-\tprintf(\"+++ %s\\n\", label_path[1]);\n-\n \tif (fill_mmfile(&mf1, temp[0].name) < 0 ||\n \t fill_mmfile(&mf2, temp[1].name) < 0)\n \t\tdie(\"unable to read files to diff\");\n \n-\t/* Crazy xdl interfaces.. */\n-\t{\n+\tif (mmfile_is_binary(&mf1) || mmfile_is_binary(&mf2))\n+\t\tprintf(\"Binary files %s and %s differ\\n\",\n+\t\t label_path[0], label_path[1]);\n+\telse {\n+\t\t/* Crazy xdl interfaces.. */\n+\t\tconst char *diffopts = getenv(\"GIT_DIFF_OPTS\");\n \t\txpparam_t xpp;\n \t\txdemitconf_t xecfg;\n \t\txdemitcb_t ecb;\n+\t\tstruct emit_callback ecbdata;\n \n+\t\tecbdata.label_path = label_path;\n \t\txpp.flags = XDF_NEED_MINIMAL;\n \t\txecfg.ctxlen = 3;\n+\t\tif (!diffopts)\n+\t\t\t;\n+\t\telse if (!strncmp(diffopts, \"--unified=\", 10))\n+\t\t\txecfg.ctxlen = strtoul(diffopts + 10, NULL, 10);\n+\t\telse if (!strncmp(diffopts, \"-u\", 2))\n+\t\t\txecfg.ctxlen = strtoul(diffopts + 2, NULL, 10);\n \t\tecb.outf = fn_out;\n+\t\tecb.priv = &ecbdata;\n \t\txdl_diff(&mf1, &mf2, &xpp, &xecfg, &ecb);\n \t}\n \ndiff --git a/t/t1200-tutorial.sh b/t/t1200-tutorial.sh\nindex 1002413..5ac373f 100755\n--- a/t/t1200-tutorial.sh\n+++ b/t/t1200-tutorial.sh\n@@ -22,7 +22,7 @@\n index 557db03..263414f 100644\n --- a/hello\n +++ b/hello\n-@@ -1 +1,2 @@\n+@@ -1,1 +1,2 @@\n Hello World\n +It's a new day for git\n EOF\n@@ -60,14 +60,14 @@\n index 0000000..f24c74a\n --- /dev/null\n +++ b/example\n-@@ -0,0 +1 @@\n+@@ -0,0 +1,1 @@\n +Silly example\n diff --git a/hello b/hello\n new file mode 100644\n index 0000000..557db03\n --- /dev/null\n +++ b/hello\n-@@ -0,0 +1 @@\n+@@ -0,0 +1,1 @@\n +Hello World\n EOF\n \ndiff --git a/t/t4001-diff-rename.sh b/t/t4001-diff-rename.sh\nindex 2e3c20d..08c1131 100755\n--- a/t/t4001-diff-rename.sh\n+++ b/t/t4001-diff-rename.sh\n@@ -49,7 +49,7 @@\n rename to path1\n --- a/path0\n +++ b/path1\n-@@ -8,7 +8,7 @@ Line 7\n+@@ -8,7 +8,7 @@\n Line 8\n Line 9\n Line 10\ndiff --git a/t/t4003-diff-rename-1.sh b/t/t4003-diff-rename-1.sh\nindex 2751970..af744fd 100755\n--- a/t/t4003-diff-rename-1.sh\n+++ b/t/t4003-diff-rename-1.sh\n@@ -36,7 +36,7 @@\n copy to COPYING.1\n --- a/COPYING\n +++ b/COPYING.1\n-@@ -6 +6 @@\n+@@ -6,1 +6,1 @@\n - HOWEVER, in order to allow a migration to GPLv3 if that seems like\n + However, in order to allow a migration to GPLv3 if that seems like\n diff --git a/COPYING b/COPYING.2\n@@ -44,13 +44,13 @@\n rename to COPYING.2\n --- a/COPYING\n +++ b/COPYING.2\n-@@ -2 +2 @@\n+@@ -2,1 +2,1 @@\n - Note that the only valid version of the GPL as far as this project\n + Note that the only valid version of the G.P.L as far as this project\n-@@ -6 +6 @@\n+@@ -6,1 +6,1 @@\n - HOWEVER, in order to allow a migration to GPLv3 if that seems like\n + HOWEVER, in order to allow a migration to G.P.Lv3 if that seems like\n-@@ -12 +12 @@\n+@@ -12,1 +12,1 @@\n -\tThis file is licensed under the GPL v2, or a later version\n +\tThis file is licensed under the G.P.L v2, or a later version\n EOF\n@@ -74,13 +74,13 @@\n diff --git a/COPYING b/COPYING\n --- a/COPYING\n +++ b/COPYING\n-@@ -2 +2 @@\n+@@ -2,1 +2,1 @@\n - Note that the only valid version of the GPL as far as this project\n + Note that the only valid version of the G.P.L as far as this project\n-@@ -6 +6 @@\n+@@ -6,1 +6,1 @@\n - HOWEVER, in order to allow a migration to GPLv3 if that seems like\n + HOWEVER, in order to allow a migration to G.P.Lv3 if that seems like\n-@@ -12 +12 @@\n+@@ -12,1 +12,1 @@\n -\tThis file is licensed under the GPL v2, or a later version\n +\tThis file is licensed under the G.P.L v2, or a later version\n diff --git a/COPYING b/COPYING.1\n@@ -88,7 +88,7 @@\n copy to COPYING.1\n --- a/COPYING\n +++ b/COPYING.1\n-@@ -6 +6 @@\n+@@ -6,1 +6,1 @@\n - HOWEVER, in order to allow a migration to GPLv3 if that seems like\n + However, in order to allow a migration to GPLv3 if that seems like\n EOF\n@@ -116,7 +116,7 @@\n copy to COPYING.1\n --- a/COPYING\n +++ b/COPYING.1\n-@@ -6 +6 @@\n+@@ -6,1 +6,1 @@\n - HOWEVER, in order to allow a migration to GPLv3 if that seems like\n + However, in order to allow a migration to GPLv3 if that seems like\n EOF\ndiff --git a/t/t4004-diff-rename-symlink.sh b/t/t4004-diff-rename-symlink.sh\nindex a23aaa0..04f0147 100755\n--- a/t/t4004-diff-rename-symlink.sh\n+++ b/t/t4004-diff-rename-symlink.sh\n@@ -40,7 +40,7 @@\n new file mode 120000\n --- /dev/null\n +++ b/bozbar\n-@@ -0,0 +1 @@\n+@@ -0,0 +1,1 @@\n +xzzzy\n \\ No newline at end of file\n diff --git a/frotz b/nitfol\n@@ -55,7 +55,7 @@\n deleted file mode 100644\n --- a/yomin\n +++ /dev/null\n-@@ -1 +0,0 @@\n+@@ -1,1 +0,0 @@\n -xyzzy\n \\ No newline at end of file\n EOF\ndiff --git a/t/t4011-diff-symlink.sh b/t/t4011-diff-symlink.sh\nindex 379a831..36ac16d 100755\n--- a/t/t4011-diff-symlink.sh\n+++ b/t/t4011-diff-symlink.sh\n@@ -15,7 +15,7 @@\n index 0000000..7c465af\n --- /dev/null\n +++ b/frotz\n-@@ -0,0 +1 @@\n+@@ -0,0 +1,1 @@\n +xyzzy\n \\ No newline at end of file\n EOF\n@@ -41,7 +41,7 @@\n index 7c465af..0000000\n --- a/frotz\n +++ /dev/null\n-@@ -1 +0,0 @@\n+@@ -1,1 +0,0 @@\n -xyzzy\n \\ No newline at end of file\n EOF\n@@ -68,7 +68,7 @@\n index 7c465af..df1db54 120000\n --- a/frotz\n +++ b/frotz\n-@@ -1 +1 @@\n+@@ -1,1 +1,1 @@\n -xyzzy\n \\ No newline at end of file\n +yxyyz\n"},{"id":"17947","messageId":"7vslp6uvn1.fsf@assigned-by-dhcp.cox.net","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603250742340.15714@g5.osdl.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-25T20:17:22Z","receivedAt":"2006-03-25T20:17:22Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Sat, 25 Mar 2006, Linus Torvalds wrote:\n>> \n>> I'll be taking a look at trying to fix it. \n>\n> Actually, it ended up being easier than I expected it to be.\n>\n> This (on top of the previous patch) should fix it.\n\nThis is a replacement for my previous one, which reduces the\nchanges to the testsuite.\n\nI'll find time to omit prepare_temp_file() calls from diffcore\nemit routines over the weekend. Another useful project would be\nto redo the combine-diff.c using the real built-in diff.\n\n-- >8 --\n[PATCH] built-in diff: minimum tweaks\n\nThis fixes up a couple of minor issues with the real built-in\ndiff to be more usable:\n\n - Omit ---/+++ header unless we emit diff output;\n\n - Detect and punt binary diff like GNU does;\n\n - Honor GIT_DIFF_OPTS minimally (only -u and\n --unified= are currently supported);\n\n - Omit line count of 1 from \"@@ -l,k +m,n @@\" hunk header\n (i.e. when k == 1 or n == 1)\n\n - Adjust testsuite for the lack of -p support.\n\nSigned-off-by: Junio C Hamano \n\n---\n\n diff.c | 41 ++++++++++++++++++++++++++++++++++++-----\n t/t4001-diff-rename.sh | 2 +-\n xdiff/xutils.c | 16 ++++++++++------\n 3 files changed, 47 insertions(+), 12 deletions(-)\n\n6ff2f393f16e56a5d3d611b4d3e8f039994ce0a8\ndiff --git a/diff.c b/diff.c\nindex f6a1f5d..cd2ce0f 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -212,16 +212,37 @@ static int fill_mmfile(mmfile_t *mf, con\n \treturn 0;\n }\n \n+struct emit_callback {\n+\tconst char **label_path;\n+};\n+\n static int fn_out(void *priv, mmbuffer_t *mb, int nbuf)\n {\n \tint i;\n+\tstruct emit_callback *ecbdata = priv;\n \n+\tif (ecbdata->label_path[0]) {\n+\t\tprintf(\"--- %s\\n\", ecbdata->label_path[0]);\n+\t\tprintf(\"+++ %s\\n\", ecbdata->label_path[1]);\n+\t\tecbdata->label_path[0] = ecbdata->label_path[1] = NULL;\n+\t}\n \tfor (i = 0; i < nbuf; i++)\n \t\tif (!fwrite(mb[i].ptr, mb[i].size, 1, stdout))\n \t\t\treturn -1;\n \treturn 0;\n }\n \n+#define FIRST_FEW_BYTES 8000\n+static int mmfile_is_binary(mmfile_t *mf)\n+{\n+\tlong sz = mf->size;\n+\tif (FIRST_FEW_BYTES < sz)\n+\t\tsz = FIRST_FEW_BYTES;\n+\tif (memchr(mf->ptr, 0, sz))\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n static const char *builtin_diff(const char *name_a,\n \t\t\t const char *name_b,\n \t\t\t struct diff_tempfile *temp,\n@@ -306,22 +327,32 @@ static const char *builtin_diff(const ch\n \tif (label_path[1][0] != '/')\n \t\tlabel_path[1] = quote_two(\"b/\", name_b);\n \n-\tprintf(\"--- %s\\n\", label_path[0]);\n-\tprintf(\"+++ %s\\n\", label_path[1]);\n-\n \tif (fill_mmfile(&mf1, temp[0].name) < 0 ||\n \t fill_mmfile(&mf2, temp[1].name) < 0)\n \t\tdie(\"unable to read files to diff\");\n \n-\t/* Crazy xdl interfaces.. */\n-\t{\n+\tif (mmfile_is_binary(&mf1) || mmfile_is_binary(&mf2))\n+\t\tprintf(\"Binary files %s and %s differ\\n\",\n+\t\t label_path[0], label_path[1]);\n+\telse {\n+\t\t/* Crazy xdl interfaces.. */\n+\t\tconst char *diffopts = getenv(\"GIT_DIFF_OPTS\");\n \t\txpparam_t xpp;\n \t\txdemitconf_t xecfg;\n \t\txdemitcb_t ecb;\n+\t\tstruct emit_callback ecbdata;\n \n+\t\tecbdata.label_path = label_path;\n \t\txpp.flags = XDF_NEED_MINIMAL;\n \t\txecfg.ctxlen = 3;\n+\t\tif (!diffopts)\n+\t\t\t;\n+\t\telse if (!strncmp(diffopts, \"--unified=\", 10))\n+\t\t\txecfg.ctxlen = strtoul(diffopts + 10, NULL, 10);\n+\t\telse if (!strncmp(diffopts, \"-u\", 2))\n+\t\t\txecfg.ctxlen = strtoul(diffopts + 2, NULL, 10);\n \t\tecb.outf = fn_out;\n+\t\tecb.priv = &ecbdata;\n \t\txdl_diff(&mf1, &mf2, &xpp, &xecfg, &ecb);\n \t}\n \ndiff --git a/t/t4001-diff-rename.sh b/t/t4001-diff-rename.sh\nindex 2e3c20d..08c1131 100755\n--- a/t/t4001-diff-rename.sh\n+++ b/t/t4001-diff-rename.sh\n@@ -49,7 +49,7 @@ rename from path0\n rename to path1\n --- a/path0\n +++ b/path1\n-@@ -8,7 +8,7 @@ Line 7\n+@@ -8,7 +8,7 @@\n Line 8\n Line 9\n Line 10\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex b68afa2..8221806 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -245,20 +245,24 @@ int xdl_emit_hunk_hdr(long s1, long c1, \n \n \tnb += xdl_num_out(buf + nb, c1 ? s1: 0);\n \n-\tmemcpy(buf + nb, \",\", 1);\n-\tnb += 1;\n+\tif (c1 != 1) {\n+\t\tmemcpy(buf + nb, \",\", 1);\n+\t\tnb += 1;\n \n-\tnb += xdl_num_out(buf + nb, c1);\n+\t\tnb += xdl_num_out(buf + nb, c1);\n+\t}\n \n \tmemcpy(buf + nb, \" +\", 2);\n \tnb += 2;\n \n \tnb += xdl_num_out(buf + nb, c2 ? s2: 0);\n \n-\tmemcpy(buf + nb, \",\", 1);\n-\tnb += 1;\n+\tif (c2 != 1) {\n+\t\tmemcpy(buf + nb, \",\", 1);\n+\t\tnb += 1;\n \n-\tnb += xdl_num_out(buf + nb, c2);\n+\t\tnb += xdl_num_out(buf + nb, c2);\n+\t}\n \n \tmemcpy(buf + nb, \" @@\\n\", 4);\n \tnb += 4;\n-- \n1.2.4.g88d9\n"},{"id":"17950","messageId":"Pine.LNX.4.64.0603251238550.15714@g5.osdl.org","threadId":"3717","inReplyTo":"7vslp6uvn1.fsf@assigned-by-dhcp.cox.net","subject":"Re: Use a *real* built-in diff generator","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-25T20:48:33Z","receivedAt":"2006-03-25T20:48:33Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 25 Mar 2006, Junio C Hamano wrote:\n> \n> This is a replacement for my previous one, which reduces the\n> changes to the testsuite.\n\nLooks good. With this, I think it's certainly ready for the \"next\" branch, \nand with some testing should be quite mergable into the main branch too.\n\nI really didn't have to mess up the libxdiff files very much, so I don't \nthink I introduced any new bugs, and libxdiff itself seems to be pretty \nstable (and that's partly from running the tests, but even more from just \nlooking at the code and not having any 'Ewww! Gross!'-moments).\n\nWhich is not to say that there couldn't be bugs, but I think this is very \nmuch worth merging quickly..\n\n> I'll find time to omit prepare_temp_file() calls from diffcore\n> emit routines over the weekend. Another useful project would be\n> to redo the combine-diff.c using the real built-in diff.\n\nI think the pickaxe improvements would be an even bigger thing..\n\n\t\tLinus\n"},{"id":"17951","messageId":"Pine.LNX.4.64.0603251256330.15714@g5.osdl.org","threadId":"3717","inReplyTo":"7vslp6uvn1.fsf@assigned-by-dhcp.cox.net","subject":"Re: Use a *real* built-in diff generator","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-25T21:06:44Z","receivedAt":"2006-03-25T21:06:44Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 25 Mar 2006, Junio C Hamano wrote:\n> \n> This is a replacement for my previous one, which reduces the\n> changes to the testsuite.\n\nBtw, your comment about the GNU diff @@-line simplification made me look \nat that again.\n\ngit-apply used to believe that a simplified line (ie with a single value) \nmeant \"x,x\". While it seems that it really means \"x,1\".\n\nNow, at worst, this would probably mean that some patches would get \nrejected (rather than mis-applied), so I think we've just never hit it. \nAlso, with the default 3-line context I think that it simply _cannot_ be \nhit (since the only way that the result or source would have only one line \nin the resulting is it was the first line).\n\nBut if the \"x\" shorthand really means \"x,1\" (and I think you're right - \nusing \"-U 1\" I can get that kind of shorthand) then apply.c should be \nfixed as follows (actual patch: removal of two characters).\n\nSigned-off-by: Linus Torvalds \n---\ndiff --git a/apply.c b/apply.c\nindex 2da225a..e80cd15 100644\n--- a/apply.c\n+++ b/apply.c\n@@ -693,7 +693,7 @@ static int parse_range(const char *line,\n \tline += digits;\n \tlen -= digits;\n \n-\t*p2 = *p1;\n+\t*p2 = 1;\n \tif (*line == ',') {\n \t\tdigits = parse_num(line+1, p2);\n \t\tif (!digits)\n"},{"id":"17977","messageId":"Pine.LNX.4.64.0603252005360.12437@alien.or.mcafeemobile.com","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603251030340.15714@g5.osdl.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-03-26T04:11:14Z","receivedAt":"2006-03-26T04:11:14Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Sat, 25 Mar 2006, Linus Torvalds wrote:\n\n> I don't need \"patch\", since I wrote my own anyway. It's just called\n> \"apply\" instead of \"patch\".\n\nOh, ok. I thought you were calling out GNU patch for the task.\n\n\n> Doing \"apply\" is not only much simpler than doing \"diff\", but I needed my\n> own much earlier: it's much more timing-critical for me (applying 200\n> patches in one go), and git needed something that could honor renames and\n> copies, and the mode bits too.\n>\n> Besides, I hate how GNU patch bends over backwards in applying crap that\n> isn't a proper patch at all (whitespace-corruption, you name it: GNU patch\n> will accept it). Also, I made \"git-apply\" be all-or-nothing: either it\n> applies the _whole_ patch (across many different files) or it applies none\n> of it. With GNU patch, if you get an error on the fifth file, the four\n> first files have been modified already - aarrgghhh..\n>\n> See \"apply.c\" for details if you care. It's stupid, but it works (and it\n> _only_ handles unified diffs - with the git extensions, of course).\n\nSo is xdl_patch(). It handles unified diffs, a simple ignore whitespace \nchanges, and all (methink) the fuzzy merge features of GNU patch.\nOkie then, drop me an email if you find bugs in the libxdiff code, so I \ncan fix the main library.\n\n\n\n- Davide\n"},{"id":"17978","messageId":"Pine.LNX.4.64.0603252130190.12437@alien.or.mcafeemobile.com","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603251040190.15714@g5.osdl.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-03-26T05:33:36Z","receivedAt":"2006-03-26T05:33:36Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Sat, 25 Mar 2006, Linus Torvalds wrote:\n\n> Btw, git-apply does it, and it's actually quite simple: the code to handle\n> the \"\\ No newline\" case is literally just this:\n>\n> /*\n> * \"plen\" is how much of the line we should use for\n> * the actual patch data. Normally we just remove the\n> * first character on the line, but if the line is\n> * followed by \"\\ No newline\", then we also remove the\n> * last one (which is the newline, of course).\n> */\n> plen = len-1;\n> if (len < size && patch[len] == '\\\\')\n> plen--;\n>\n> if we just remove the last '\\n' on a line, if the _next_ line starts with\n> a '\\\\' (so the git-apply code actually depends on knowing that the patch\n> text is dense, and that it's also padded out so that you can look one byte\n> past the end of the diff and it won't be a '\\\\').\n>\n> I don't know how well that fits into xpatch (I never looked at the patch\n> side, since I already had my own ;), but my point being that handling this\n> special case _can_ be very simple if the data structures are just set up\n> for it.\n\nYeah, should be a pretty trivial fix in the xpatch parsing code. Thanks \nfor remembering me the missing-eol issue, that fell forgotten somewhere in \nmy todo list :D\n\n\n\n- Davide\n"},{"id":"17988","messageId":"20060326110934.GA3774@linux-mips.org","threadId":"3717","inReplyTo":"Pine.LNX.4.64.0603251030340.15714@g5.osdl.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Ralf Baechle","fromEmail":"ralf@linux-mips.org","sentAt":"2006-03-26T11:09:35Z","receivedAt":"2006-03-26T11:09:35Z","isPatch":false,"sender":{"key":"ralf@linux-mips.org","avatar":null},"body":"On Sat, Mar 25, 2006 at 10:39:03AM -0800, Linus Torvalds wrote:\n\n> Besides, I hate how GNU patch bends over backwards in applying crap that \n> isn't a proper patch at all (whitespace-corruption, you name it: GNU patch \n> will accept it). Also, I made \"git-apply\" be all-or-nothing: either it \n> applies the _whole_ patch (across many different files) or it applies none \n> of it. With GNU patch, if you get an error on the fifth file, the four \n> first files have been modified already - aarrgghhh..\n\nWhich is apply's greatest strength - and weakness. GNU diff doesn't\nunderstand the file renamings bits of git diffs, so they they need to be\nused with apply. So if a patch doesn't apply? Apply doesn't even have\nan option to apply things as good as it can and leave the rest in\nreject files. Yuck.\n\n Ralf\n"},{"id":"18004","messageId":"20060326182028.GP18185@pasky.or.cz","threadId":"3717","inReplyTo":"20060326110934.GA3774@linux-mips.org","subject":"Re: Use a *real* built-in diff generator","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2006-03-26T18:20:28Z","receivedAt":"2006-03-26T18:20:28Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"Dear diary, on Sun, Mar 26, 2006 at 01:09:35PM CEST, I got a letter\nwhere Ralf Baechle said that...\n> On Sat, Mar 25, 2006 at 10:39:03AM -0800, Linus Torvalds wrote:\n> \n> > Besides, I hate how GNU patch bends over backwards in applying crap that \n> > isn't a proper patch at all (whitespace-corruption, you name it: GNU patch \n> > will accept it). Also, I made \"git-apply\" be all-or-nothing: either it \n> > applies the _whole_ patch (across many different files) or it applies none \n> > of it. With GNU patch, if you get an error on the fifth file, the four \n> > first files have been modified already - aarrgghhh..\n> \n> Which is apply's greatest strength - and weakness. GNU diff doesn't\n> understand the file renamings bits of git diffs, so they they need to be\n> used with apply. So if a patch doesn't apply? Apply doesn't even have\n> an option to apply things as good as it can and leave the rest in\n> reject files. Yuck.\n\nI've just updated cg-patch on the master branch today to understand file\nrenames, so it should be possible to use it for applying fuzzy patches.\n(OTOH, cg-patch has grown way too complex and ugly for my taste. It'd be\nnice if git-apply could take over the ugly part of the task.)\n\nNo dice with patches containing copy information, though. We would need\nto perform the copy _before_ applying the patch itself and we have no\ninfrastructure for that (so far it has been enough to do the\ngit-specific stuff after applying the patch itself).\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\nRight now I am having amnesia and deja-vu at the same time. I think\nI have forgotten this before.\n"}]}