xdiff: vendor xdiff library from git Vendor git's xdiff library from git commit d7c6c2369d7c6c2369ac21141b7c6cceaebc6414ec3da14ad using GPL2+ license. There is another recent user report that hg diff generates suboptimal result. It seems the fix to issue4074 isn't good enough. I crafted some other interesting cases, and hg diff barely has any advantage compared with gnu diffutils or git diff. | testcase | gnu diffutils | hg diff | git diff | | | lines time | lines time | lines time | | patience | 6 0.00 | 602 0.08 | 6 0.00 | | random | 91772 0.90 | 109462 0.70 | 91772 0.24 | | json | 2 0.03 | 1264814 1.81 | 2 0.29 | "lines" means the size of the output, i.e. the count of "+/-" lines. "time" means seconds needed to do the calculation. Both are the smaller the better. "hg diff" counts Python startup overhead. Git and GNU diffutils generate optimal results. For the "json" case, git can have an optimization that does a scan for common prefix and suffix first, and match them if the length is greater than half of the text. See https://neil.fraser.name/news/2006/03/12/. That would make git the fastest for all above cases. About testcases: patience: Aiming for the weakness of the greedy "patience diff" algorithm. Using git's patience diff option would also get suboptimal result. Generated using the Python script: ``` open('a', 'w').write('\n'.join(list('a' + 'x' * 300 + 'u' + 'x' * 700 + 'a\n'))) open('b', 'w').write('\n'.join(list('b' + 'x' * 700 + 'u' + 'x' * 300 + 'b\n'))) ``` random: Generated using the script in `test-issue4074.t`. It practically makes the algorithm suffer. Impressively, git wins in both performance and diff quality. json: The recent user reported case. It's a single line movement near the end of a very large (800K lines) JSON file. Test Plan: Code taken as-is. Differential Revision: https://phab.mercurial-scm.org/D2572 # no-check-commit for vendored code

     1

/*

     2

 *  LibXDiff by Davide Libenzi ( File Differential Library )

     3

 *  Copyright (C) 2003  Davide Libenzi

     4

 *

     5

 *  This library is free software; you can redistribute it and/or

     6

 *  modify it under the terms of the GNU Lesser General Public

     7

 *  License as published by the Free Software Foundation; either

     8

 *  version 2.1 of the License, or (at your option) any later version.

     9

 *

    10

 *  This library is distributed in the hope that it will be useful,

    11

 *  but WITHOUT ANY WARRANTY; without even the implied warranty of

    12

 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    13

 *  Lesser General Public License for more details.

    14

 *

    15

 *  You should have received a copy of the GNU Lesser General Public

    16

 *  License along with this library; if not, see

    17

 *  <http://www.gnu.org/licenses/>.

    18

 *

    19

 *  Davide Libenzi <davidel@xmailserver.org>

    20

 *

    21

 */

    22

    23

#if !defined(XMACROS_H)

    24

#define XMACROS_H

    25

    26

    27

    28

    29

#define XDL_MIN(a, b) ((a) < (b) ? (a): (b))

    30

#define XDL_MAX(a, b) ((a) > (b) ? (a): (b))

    31

#define XDL_ABS(v) ((v) >= 0 ? (v): -(v))

    32

#define XDL_ISDIGIT(c) ((c) >= '0' && (c) <= '9')

    33

#define XDL_ISSPACE(c) (isspace((unsigned char)(c)))

    34

#define XDL_ADDBITS(v,b)	((v) + ((v) >> (b)))

    35

#define XDL_MASKBITS(b)		((1UL << (b)) - 1)

    36

#define XDL_HASHLONG(v,b)	(XDL_ADDBITS((unsigned long)(v), b) & XDL_MASKBITS(b))

    37

#define XDL_PTRFREE(p) do { if (p) { xdl_free(p); (p) = NULL; } } while (0)

    38

#define XDL_LE32_PUT(p, v) \

    39

do { \

    40

	unsigned char *__p = (unsigned char *) (p); \

    41

	*__p++ = (unsigned char) (v); \

    42

	*__p++ = (unsigned char) ((v) >> 8); \

    43

	*__p++ = (unsigned char) ((v) >> 16); \

    44

	*__p = (unsigned char) ((v) >> 24); \

    45

} while (0)

    46

#define XDL_LE32_GET(p, v) \

    47

do { \

    48

	unsigned char const *__p = (unsigned char const *) (p); \

    49

	(v) = (unsigned long) __p[0] | ((unsigned long) __p[1]) << 8 | \

    50

		((unsigned long) __p[2]) << 16 | ((unsigned long) __p[3]) << 24; \

    51

} while (0)

    52

    53

    54

#endif /* #if !defined(XMACROS_H) */