0000: 2f 2a 0a 2a 2a 20 43 6f 70 79 72 69 67 68 74 20 /*.** Copyright
0010: 28 63 29 20 32 30 30 37 20 44 2e 20 52 69 63 68 (c) 2007 D. Rich
0020: 61 72 64 20 48 69 70 70 0a 2a 2a 0a 2a 2a 20 54 ard Hipp.**.** T
0030: 68 69 73 20 70 72 6f 67 72 61 6d 20 69 73 20 66 his program is f
0040: 72 65 65 20 73 6f 66 74 77 61 72 65 3b 20 79 6f ree software; yo
0050: 75 20 63 61 6e 20 72 65 64 69 73 74 72 69 62 75 u can redistribu
0060: 74 65 20 69 74 20 61 6e 64 2f 6f 72 0a 2a 2a 20 te it and/or.**
0070: 6d 6f 64 69 66 79 20 69 74 20 75 6e 64 65 72 20 modify it under
0080: 74 68 65 20 74 65 72 6d 73 20 6f 66 20 74 68 65 the terms of the
0090: 20 47 4e 55 20 47 65 6e 65 72 61 6c 20 50 75 62 GNU General Pub
00a0: 6c 69 63 0a 2a 2a 20 4c 69 63 65 6e 73 65 20 76 lic.** License v
00b0: 65 72 73 69 6f 6e 20 32 20 61 73 20 70 75 62 6c ersion 2 as publ
00c0: 69 73 68 65 64 20 62 79 20 74 68 65 20 46 72 65 ished by the Fre
00d0: 65 20 53 6f 66 74 77 61 72 65 20 46 6f 75 6e 64 e Software Found
00e0: 61 74 69 6f 6e 2e 0a 2a 2a 0a 2a 2a 20 54 68 69 ation..**.** Thi
00f0: 73 20 70 72 6f 67 72 61 6d 20 69 73 20 64 69 73 s program is dis
0100: 74 72 69 62 75 74 65 64 20 69 6e 20 74 68 65 20 tributed in the
0110: 68 6f 70 65 20 74 68 61 74 20 69 74 20 77 69 6c hope that it wil
0120: 6c 20 62 65 20 75 73 65 66 75 6c 2c 0a 2a 2a 20 l be useful,.**
0130: 62 75 74 20 57 49 54 48 4f 55 54 20 41 4e 59 20 but WITHOUT ANY
0140: 57 41 52 52 41 4e 54 59 3b 20 77 69 74 68 6f 75 WARRANTY; withou
0150: 74 20 65 76 65 6e 20 74 68 65 20 69 6d 70 6c 69 t even the impli
0160: 65 64 20 77 61 72 72 61 6e 74 79 20 6f 66 0a 2a ed warranty of.*
0170: 2a 20 4d 45 52 43 48 41 4e 54 41 42 49 4c 49 54 * MERCHANTABILIT
0180: 59 20 6f 72 20 46 49 54 4e 45 53 53 20 46 4f 52 Y or FITNESS FOR
0190: 20 41 20 50 41 52 54 49 43 55 4c 41 52 20 50 55 A PARTICULAR PU
01a0: 52 50 4f 53 45 2e 20 20 53 65 65 20 74 68 65 20 RPOSE. See the
01b0: 47 4e 55 0a 2a 2a 20 47 65 6e 65 72 61 6c 20 50 GNU.** General P
01c0: 75 62 6c 69 63 20 4c 69 63 65 6e 73 65 20 66 6f ublic License fo
01d0: 72 20 6d 6f 72 65 20 64 65 74 61 69 6c 73 2e 0a r more details..
01e0: 2a 2a 20 0a 2a 2a 20 59 6f 75 20 73 68 6f 75 6c ** .** You shoul
01f0: 64 20 68 61 76 65 20 72 65 63 65 69 76 65 64 20 d have received
0200: 61 20 63 6f 70 79 20 6f 66 20 74 68 65 20 47 4e a copy of the GN
0210: 55 20 47 65 6e 65 72 61 6c 20 50 75 62 6c 69 63 U General Public
0220: 0a 2a 2a 20 4c 69 63 65 6e 73 65 20 61 6c 6f 6e .** License alon
0230: 67 20 77 69 74 68 20 74 68 69 73 20 6c 69 62 72 g with this libr
0240: 61 72 79 3b 20 69 66 20 6e 6f 74 2c 20 77 72 69 ary; if not, wri
0250: 74 65 20 74 6f 20 74 68 65 0a 2a 2a 20 46 72 65 te to the.** Fre
0260: 65 20 53 6f 66 74 77 61 72 65 20 46 6f 75 6e 64 e Software Found
0270: 61 74 69 6f 6e 2c 20 49 6e 63 2e 2c 20 35 39 20 ation, Inc., 59
0280: 54 65 6d 70 6c 65 20 50 6c 61 63 65 20 2d 20 53 Temple Place - S
0290: 75 69 74 65 20 33 33 30 2c 0a 2a 2a 20 42 6f 73 uite 330,.** Bos
02a0: 74 6f 6e 2c 20 4d 41 20 20 30 32 31 31 31 2d 31 ton, MA 02111-1
02b0: 33 30 37 2c 20 55 53 41 2e 0a 2a 2a 0a 2a 2a 20 307, USA..**.**
02c0: 41 75 74 68 6f 72 20 63 6f 6e 74 61 63 74 20 69 Author contact i
02d0: 6e 66 6f 72 6d 61 74 69 6f 6e 3a 0a 2a 2a 20 20 nformation:.**
02e0: 20 64 72 68 40 68 77 61 63 69 2e 63 6f 6d 0a 2a drh@hwaci.com.*
02f0: 2a 20 20 20 68 74 74 70 3a 2f 2f 77 77 77 2e 68 * http://www.h
0300: 77 61 63 69 2e 63 6f 6d 2f 64 72 68 2f 0a 2a 2a waci.com/drh/.**
0310: 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a .***************
0320: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0330: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0340: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0350: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0360: 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 66 69 6c 65 .**.** This file
0370: 20 63 6f 6e 74 61 69 6e 73 20 63 6f 64 65 20 75 contains code u
0380: 73 65 64 20 74 6f 20 63 6f 6d 70 75 74 65 20 61 sed to compute a
0390: 20 22 64 69 66 66 22 20 62 65 74 77 65 65 6e 20 "diff" between
03a0: 74 77 6f 0a 2a 2a 20 74 65 78 74 20 66 69 6c 65 two.** text file
03b0: 73 2e 0a 2a 2f 0a 23 69 6e 63 6c 75 64 65 20 22 s..*/.#include "
03c0: 63 6f 6e 66 69 67 2e 68 22 0a 23 69 6e 63 6c 75 config.h".#inclu
03d0: 64 65 20 22 64 69 66 66 2e 68 22 0a 23 69 6e 63 de "diff.h".#inc
03e0: 6c 75 64 65 20 3c 61 73 73 65 72 74 2e 68 3e 0a lude <assert.h>.
03f0: 0a 0a 23 69 66 20 30 0a 23 64 65 66 69 6e 65 20 ..#if 0.#define
0400: 44 45 42 55 47 28 58 29 20 58 0a 23 65 6c 73 65 DEBUG(X) X.#else
0410: 0a 23 64 65 66 69 6e 65 20 44 45 42 55 47 28 58 .#define DEBUG(X
0420: 29 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20 ).#endif../*.**
0430: 49 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 62 6f 75 Information abou
0440: 74 20 65 61 63 68 20 6c 69 6e 65 20 6f 66 20 61 t each line of a
0450: 20 66 69 6c 65 20 62 65 69 6e 67 20 64 69 66 66 file being diff
0460: 65 64 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6c 6f ed..**.** The lo
0470: 77 65 72 20 32 30 20 62 69 74 73 20 6f 66 20 74 wer 20 bits of t
0480: 68 65 20 68 61 73 68 20 61 72 65 20 74 68 65 20 he hash are the
0490: 6c 65 6e 67 74 68 20 6f 66 20 74 68 65 0a 2a 2a length of the.**
04a0: 20 6c 69 6e 65 2e 20 20 49 66 20 61 6e 79 20 6c line. If any l
04b0: 69 6e 65 20 69 73 20 6c 6f 6e 67 65 72 20 74 68 ine is longer th
04c0: 61 6e 20 31 30 34 38 35 37 35 20 63 68 61 72 61 an 1048575 chara
04d0: 63 74 65 72 73 2c 0a 2a 2a 20 74 68 65 20 66 69 cters,.** the fi
04e0: 6c 65 20 69 73 20 63 6f 6e 73 69 64 65 72 65 64 le is considered
04f0: 20 62 69 6e 61 72 79 2e 0a 2a 2f 0a 74 79 70 65 binary..*/.type
0500: 64 65 66 20 73 74 72 75 63 74 20 44 4c 69 6e 65 def struct DLine
0510: 20 44 4c 69 6e 65 3b 0a 73 74 72 75 63 74 20 44 DLine;.struct D
0520: 4c 69 6e 65 20 7b 0a 20 20 63 6f 6e 73 74 20 63 Line {. const c
0530: 68 61 72 20 2a 7a 3b 20 20 20 20 20 20 20 20 2f har *z; /
0540: 2a 20 54 68 65 20 74 65 78 74 20 6f 66 20 74 68 * The text of th
0550: 65 20 6c 69 6e 65 20 2a 2f 0a 20 20 75 6e 73 69 e line */. unsi
0560: 67 6e 65 64 20 69 6e 74 20 68 3b 20 20 20 20 20 gned int h;
0570: 20 20 2f 2a 20 48 61 73 68 20 6f 66 20 74 68 65 /* Hash of the
0580: 20 6c 69 6e 65 20 2a 2f 0a 20 20 75 6e 73 69 67 line */. unsig
0590: 6e 65 64 20 69 6e 74 20 69 4e 65 78 74 3b 20 20 ned int iNext;
05a0: 20 2f 2a 20 49 6e 64 65 78 2b 31 20 6f 66 20 6e /* Index+1 of n
05b0: 65 78 74 20 6c 69 6e 65 20 77 69 74 68 20 73 61 ext line with sa
05c0: 6d 65 20 74 68 65 20 73 61 6d 65 20 68 61 73 68 me the same hash
05d0: 20 2a 2f 0a 0a 20 20 2f 2a 20 61 6e 20 61 72 72 */.. /* an arr
05e0: 61 79 20 6f 66 20 44 4c 69 6e 65 20 65 6c 65 6d ay of DLine elem
05f0: 65 6e 74 73 20 73 65 72 76 69 63 65 73 20 74 77 ents services tw
0600: 6f 20 70 75 72 70 6f 73 65 73 2e 20 20 54 68 65 o purposes. The
0610: 20 66 69 65 6c 64 73 0a 20 20 2a 2a 20 61 62 6f fields. ** abo
0620: 76 65 20 61 72 65 20 6f 6e 65 20 70 65 72 20 6c ve are one per l
0630: 69 6e 65 20 6f 66 20 69 6e 70 75 74 20 74 65 78 ine of input tex
0640: 74 2e 20 20 42 75 74 20 65 61 63 68 20 65 6e 74 t. But each ent
0650: 72 79 20 69 73 20 61 6c 73 6f 0a 20 20 2a 2a 20 ry is also. **
0660: 61 20 62 75 63 6b 65 74 20 69 6e 20 61 20 68 61 a bucket in a ha
0670: 73 68 20 74 61 62 6c 65 2e 20 2a 2f 0a 20 20 75 sh table. */. u
0680: 6e 73 69 67 6e 65 64 20 69 6e 74 20 69 48 61 73 nsigned int iHas
0690: 68 3b 20 20 20 2f 2a 20 46 69 72 73 74 20 65 6e h; /* First en
06a0: 74 72 79 2b 31 20 69 6e 20 74 68 65 20 68 61 73 try+1 in the has
06b0: 68 20 61 72 72 61 79 20 2a 2f 0a 7d 3b 0a 0a 2f h array */.};../
06c0: 2a 0a 2a 2a 20 4d 61 78 69 6d 75 6d 20 6c 65 6e *.** Maximum len
06d0: 67 74 68 20 6f 66 20 61 20 6c 69 6e 65 20 69 6e gth of a line in
06e0: 20 61 20 74 65 78 74 20 66 69 6c 65 2e 20 20 28 a text file. (
06f0: 38 31 39 32 29 0a 2a 2f 0a 23 64 65 66 69 6e 65 8192).*/.#define
0700: 20 4c 45 4e 47 54 48 5f 4d 41 53 4b 5f 53 5a 20 LENGTH_MASK_SZ
0710: 20 31 33 0a 23 64 65 66 69 6e 65 20 4c 45 4e 47 13.#define LENG
0720: 54 48 5f 4d 41 53 4b 20 20 20 20 20 28 28 31 3c TH_MASK ((1<
0730: 3c 4c 45 4e 47 54 48 5f 4d 41 53 4b 5f 53 5a 29 <LENGTH_MASK_SZ)
0740: 2d 31 29 0a 0a 2f 2a 0a 2a 2a 20 41 20 63 6f 6e -1)../*.** A con
0750: 74 65 78 74 20 66 6f 72 20 72 75 6e 6e 69 6e 67 text for running
0760: 20 61 20 64 69 66 66 2e 0a 2a 2f 0a 74 79 70 65 a diff..*/.type
0770: 64 65 66 20 73 74 72 75 63 74 20 44 43 6f 6e 74 def struct DCont
0780: 65 78 74 20 44 43 6f 6e 74 65 78 74 3b 0a 73 74 ext DContext;.st
0790: 72 75 63 74 20 44 43 6f 6e 74 65 78 74 20 7b 0a ruct DContext {.
07a0: 20 20 69 6e 74 20 2a 61 45 64 69 74 3b 20 20 20 int *aEdit;
07b0: 20 20 20 20 20 2f 2a 20 41 72 72 61 79 20 6f 66 /* Array of
07c0: 20 63 6f 70 79 2f 64 65 6c 65 74 65 2f 69 6e 73 copy/delete/ins
07d0: 65 72 74 20 74 72 69 70 6c 65 73 20 2a 2f 0a 20 ert triples */.
07e0: 20 69 6e 74 20 6e 45 64 69 74 3b 20 20 20 20 20 int nEdit;
07f0: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 /* Number of
0800: 20 69 6e 74 65 67 65 72 73 20 28 33 78 20 6e 75 integers (3x nu
0810: 6d 20 6f 66 20 74 72 69 70 6c 65 73 29 20 69 6e m of triples) in
0820: 20 61 45 64 69 74 5b 5d 20 2a 2f 0a 20 20 69 6e aEdit[] */. in
0830: 74 20 6e 45 64 69 74 41 6c 6c 6f 63 3b 20 20 20 t nEditAlloc;
0840: 20 2f 2a 20 53 70 61 63 65 20 61 6c 6c 6f 63 61 /* Space alloca
0850: 74 65 64 20 66 6f 72 20 61 45 64 69 74 5b 5d 20 ted for aEdit[]
0860: 2a 2f 0a 20 20 44 4c 69 6e 65 20 2a 61 46 72 6f */. DLine *aFro
0870: 6d 3b 20 20 20 20 20 20 2f 2a 20 46 69 6c 65 20 m; /* File
0880: 6f 6e 20 6c 65 66 74 20 73 69 64 65 20 6f 66 20 on left side of
0890: 74 68 65 20 64 69 66 66 20 2a 2f 0a 20 20 69 6e the diff */. in
08a0: 74 20 6e 46 72 6f 6d 3b 20 20 20 20 20 20 20 20 t nFrom;
08b0: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6c 69 /* Number of li
08c0: 6e 65 73 20 69 6e 20 61 46 72 6f 6d 5b 5d 20 2a nes in aFrom[] *
08d0: 2f 0a 20 20 44 4c 69 6e 65 20 2a 61 54 6f 3b 20 /. DLine *aTo;
08e0: 20 20 20 20 20 20 20 2f 2a 20 46 69 6c 65 20 6f /* File o
08f0: 6e 20 72 69 67 68 74 20 73 69 64 65 20 6f 66 20 n right side of
0900: 74 68 65 20 64 69 66 66 20 2a 2f 0a 20 20 69 6e the diff */. in
0910: 74 20 6e 54 6f 3b 20 20 20 20 20 20 20 20 20 20 t nTo;
0920: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6c 69 /* Number of li
0930: 6e 65 73 20 69 6e 20 61 54 6f 5b 5d 20 2a 2f 0a nes in aTo[] */.
0940: 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e };../*.** Return
0950: 20 61 6e 20 61 72 72 61 79 20 6f 66 20 44 4c 69 an array of DLi
0960: 6e 65 20 6f 62 6a 65 63 74 73 20 63 6f 6e 74 61 ne objects conta
0970: 69 6e 69 6e 67 20 61 20 70 6f 69 6e 74 65 72 20 ining a pointer
0980: 74 6f 20 74 68 65 0a 2a 2a 20 73 74 61 72 74 20 to the.** start
0990: 6f 66 20 65 61 63 68 20 6c 69 6e 65 20 61 6e 64 of each line and
09a0: 20 61 20 68 61 73 68 20 6f 66 20 74 68 61 74 20 a hash of that
09b0: 6c 69 6e 65 2e 20 20 54 68 65 20 6c 6f 77 65 72 line. The lower
09c0: 20 0a 2a 2a 20 62 69 74 73 20 6f 66 20 74 68 65 .** bits of the
09d0: 20 68 61 73 68 20 73 74 6f 72 65 20 74 68 65 20 hash store the
09e0: 6c 65 6e 67 74 68 20 6f 66 20 65 61 63 68 20 6c length of each l
09f0: 69 6e 65 2e 0a 2a 2a 0a 2a 2a 20 54 72 61 69 6c ine..**.** Trail
0a00: 69 6e 67 20 77 68 69 74 65 73 70 61 63 65 20 69 ing whitespace i
0a10: 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 65 s removed from e
0a20: 61 63 68 20 6c 69 6e 65 2e 0a 2a 2a 0a 2a 2a 20 ach line..**.**
0a30: 52 65 74 75 72 6e 20 30 20 69 66 20 74 68 65 20 Return 0 if the
0a40: 66 69 6c 65 20 69 73 20 62 69 6e 61 72 79 20 6f file is binary o
0a50: 72 20 63 6f 6e 74 61 69 6e 73 20 61 20 6c 69 6e r contains a lin
0a60: 65 20 74 68 61 74 20 69 73 0a 2a 2a 20 74 6f 6f e that is.** too
0a70: 20 6c 6f 6e 67 2e 0a 2a 2f 0a 73 74 61 74 69 63 long..*/.static
0a80: 20 44 4c 69 6e 65 20 2a 62 72 65 61 6b 5f 69 6e DLine *break_in
0a90: 74 6f 5f 6c 69 6e 65 73 28 63 68 61 72 20 2a 7a to_lines(char *z
0aa0: 2c 20 69 6e 74 20 2a 70 6e 4c 69 6e 65 29 7b 0a , int *pnLine){.
0ab0: 20 20 69 6e 74 20 6e 4c 69 6e 65 2c 20 69 2c 20 int nLine, i,
0ac0: 6a 2c 20 6b 2c 20 78 3b 0a 20 20 75 6e 73 69 67 j, k, x;. unsig
0ad0: 6e 65 64 20 69 6e 74 20 68 2c 20 68 32 3b 0a 20 ned int h, h2;.
0ae0: 20 44 4c 69 6e 65 20 2a 61 3b 0a 0a 20 20 2f 2a DLine *a;.. /*
0af0: 20 43 6f 75 6e 74 20 74 68 65 20 6e 75 6d 62 65 Count the numbe
0b00: 72 20 6f 66 20 6c 69 6e 65 73 2e 20 20 41 6c 6c r of lines. All
0b10: 6f 63 61 74 65 20 73 70 61 63 65 20 74 6f 20 68 ocate space to h
0b20: 6f 6c 64 0a 20 20 2a 2a 20 74 68 65 20 72 65 74 old. ** the ret
0b30: 75 72 6e 65 64 20 61 72 72 61 79 2e 0a 20 20 2a urned array.. *
0b40: 2f 0a 20 20 66 6f 72 28 69 3d 6a 3d 30 2c 20 6e /. for(i=j=0, n
0b50: 4c 69 6e 65 3d 31 3b 20 7a 5b 69 5d 3b 20 69 2b Line=1; z[i]; i+
0b60: 2b 2c 20 6a 2b 2b 29 7b 0a 20 20 20 20 69 6e 74 +, j++){. int
0b70: 20 63 20 3d 20 7a 5b 69 5d 3b 0a 20 20 20 20 69 c = z[i];. i
0b80: 66 28 20 63 3d 3d 30 20 29 7b 0a 20 20 20 20 20 f( c==0 ){.
0b90: 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 20 20 7d return 0;. }
0ba0: 0a 20 20 20 20 69 66 28 20 63 3d 3d 27 5c 6e 27 . if( c=='\n'
0bb0: 20 26 26 20 7a 5b 69 2b 31 5d 21 3d 30 20 29 7b && z[i+1]!=0 ){
0bc0: 0a 20 20 20 20 20 20 6e 4c 69 6e 65 2b 2b 3b 0a . nLine++;.
0bd0: 20 20 20 20 20 20 69 66 28 20 6a 3e 4c 45 4e 47 if( j>LENG
0be0: 54 48 5f 4d 41 53 4b 20 29 7b 0a 20 20 20 20 20 TH_MASK ){.
0bf0: 20 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 20 return 0;.
0c00: 20 20 20 7d 0a 20 20 20 20 20 20 6a 20 3d 20 30 }. j = 0
0c10: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66 ;. }. }. if
0c20: 28 20 6a 3e 4c 45 4e 47 54 48 5f 4d 41 53 4b 20 ( j>LENGTH_MASK
0c30: 29 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 30 3b ){. return 0;
0c40: 0a 20 20 7d 0a 20 20 61 20 3d 20 6d 61 6c 6c 6f . }. a = mallo
0c50: 63 28 20 6e 4c 69 6e 65 2a 73 69 7a 65 6f 66 28 c( nLine*sizeof(
0c60: 61 5b 30 5d 29 20 29 3b 0a 20 20 69 66 28 20 61 a[0]) );. if( a
0c70: 3d 3d 30 20 29 20 66 6f 73 73 69 6c 5f 70 61 6e ==0 ) fossil_pan
0c80: 69 63 28 22 6f 75 74 20 6f 66 20 6d 65 6d 6f 72 ic("out of memor
0c90: 79 22 29 3b 0a 20 20 6d 65 6d 73 65 74 28 61 2c y");. memset(a,
0ca0: 20 30 2c 20 6e 4c 69 6e 65 2a 73 69 7a 65 6f 66 0, nLine*sizeof
0cb0: 28 61 5b 30 5d 29 20 29 3b 0a 0a 20 20 2f 2a 20 (a[0]) );.. /*
0cc0: 46 69 6c 6c 20 69 6e 20 74 68 65 20 61 72 72 61 Fill in the arra
0cd0: 79 20 2a 2f 0a 20 20 66 6f 72 28 69 3d 30 3b 20 y */. for(i=0;
0ce0: 69 3c 6e 4c 69 6e 65 3b 20 69 2b 2b 29 7b 0a 20 i<nLine; i++){.
0cf0: 20 20 20 61 5b 69 5d 2e 7a 20 3d 20 7a 3b 0a 20 a[i].z = z;.
0d00: 20 20 20 66 6f 72 28 6a 3d 30 3b 20 7a 5b 6a 5d for(j=0; z[j]
0d10: 20 26 26 20 7a 5b 6a 5d 21 3d 27 5c 6e 27 3b 20 && z[j]!='\n';
0d20: 6a 2b 2b 29 7b 7d 0a 20 20 20 20 66 6f 72 28 6b j++){}. for(k
0d30: 3d 6a 3b 20 6b 3e 30 20 26 26 20 69 73 73 70 61 =j; k>0 && isspa
0d40: 63 65 28 7a 5b 6b 2d 31 5d 29 3b 20 6b 2d 2d 29 ce(z[k-1]); k--)
0d50: 7b 7d 0a 20 20 20 20 66 6f 72 28 68 3d 30 2c 20 {}. for(h=0,
0d60: 78 3d 30 3b 20 78 3c 6b 3b 20 78 2b 2b 29 7b 0a x=0; x<k; x++){.
0d70: 20 20 20 20 20 20 68 20 3d 20 68 20 5e 20 28 68 h = h ^ (h
0d80: 3c 3c 32 29 20 5e 20 7a 5b 78 5d 3b 0a 20 20 20 <<2) ^ z[x];.
0d90: 20 7d 0a 20 20 20 20 61 5b 69 5d 2e 68 20 3d 20 }. a[i].h =
0da0: 68 20 3d 20 28 68 3c 3c 4c 45 4e 47 54 48 5f 4d h = (h<<LENGTH_M
0db0: 41 53 4b 5f 53 5a 29 20 7c 20 6b 3b 3b 0a 20 20 ASK_SZ) | k;;.
0dc0: 20 20 68 32 20 3d 20 68 20 25 20 6e 4c 69 6e 65 h2 = h % nLine
0dd0: 3b 0a 20 20 20 20 61 5b 69 5d 2e 69 4e 65 78 74 ;. a[i].iNext
0de0: 20 3d 20 61 5b 68 32 5d 2e 69 48 61 73 68 3b 0a = a[h2].iHash;.
0df0: 20 20 20 20 61 5b 68 32 5d 2e 69 48 61 73 68 20 a[h2].iHash
0e00: 3d 20 69 2b 31 3b 0a 20 20 20 20 7a 20 2b 3d 20 = i+1;. z +=
0e10: 6a 2b 31 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 52 j+1;. }.. /* R
0e20: 65 74 75 72 6e 20 72 65 73 75 6c 74 73 20 2a 2f eturn results */
0e30: 0a 20 20 2a 70 6e 4c 69 6e 65 20 3d 20 6e 4c 69 . *pnLine = nLi
0e40: 6e 65 3b 0a 20 20 72 65 74 75 72 6e 20 61 3b 0a ne;. return a;.
0e50: 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 }../*.** Return
0e60: 74 72 75 65 20 69 66 20 74 77 6f 20 44 4c 69 6e true if two DLin
0e70: 65 20 65 6c 65 6d 65 6e 74 73 20 61 72 65 20 69 e elements are i
0e80: 64 65 6e 74 69 63 61 6c 2e 0a 2a 2f 0a 73 74 61 dentical..*/.sta
0e90: 74 69 63 20 69 6e 74 20 73 61 6d 65 5f 64 6c 69 tic int same_dli
0ea0: 6e 65 28 44 4c 69 6e 65 20 2a 70 41 2c 20 44 4c ne(DLine *pA, DL
0eb0: 69 6e 65 20 2a 70 42 29 7b 0a 20 20 72 65 74 75 ine *pB){. retu
0ec0: 72 6e 20 70 41 2d 3e 68 3d 3d 70 42 2d 3e 68 20 rn pA->h==pB->h
0ed0: 26 26 20 6d 65 6d 63 6d 70 28 70 41 2d 3e 7a 2c && memcmp(pA->z,
0ee0: 70 42 2d 3e 7a 2c 70 41 2d 3e 68 20 26 20 4c 45 pB->z,pA->h & LE
0ef0: 4e 47 54 48 5f 4d 41 53 4b 29 3d 3d 30 3b 0a 7d NGTH_MASK)==0;.}
0f00: 0a 0a 2f 2a 0a 2a 2a 20 41 70 70 65 6e 64 20 61 ../*.** Append a
0f10: 20 73 69 6e 67 6c 65 20 6c 69 6e 65 20 6f 66 20 single line of
0f20: 22 64 69 66 66 22 20 6f 75 74 70 75 74 20 74 6f "diff" output to
0f30: 20 70 4f 75 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 pOut..*/.static
0f40: 20 76 6f 69 64 20 61 70 70 65 6e 64 44 69 66 66 void appendDiff
0f50: 4c 69 6e 65 28 42 6c 6f 62 20 2a 70 4f 75 74 2c Line(Blob *pOut,
0f60: 20 63 68 61 72 20 2a 7a 50 72 65 66 69 78 2c 20 char *zPrefix,
0f70: 44 4c 69 6e 65 20 2a 70 4c 69 6e 65 29 7b 0a 20 DLine *pLine){.
0f80: 20 62 6c 6f 62 5f 61 70 70 65 6e 64 28 70 4f 75 blob_append(pOu
0f90: 74 2c 20 7a 50 72 65 66 69 78 2c 20 31 29 3b 0a t, zPrefix, 1);.
0fa0: 20 20 62 6c 6f 62 5f 61 70 70 65 6e 64 28 70 4f blob_append(pO
0fb0: 75 74 2c 20 70 4c 69 6e 65 2d 3e 7a 2c 20 70 4c ut, pLine->z, pL
0fc0: 69 6e 65 2d 3e 68 20 26 20 4c 45 4e 47 54 48 5f ine->h & LENGTH_
0fd0: 4d 41 53 4b 29 3b 0a 20 20 62 6c 6f 62 5f 61 70 MASK);. blob_ap
0fe0: 70 65 6e 64 28 70 4f 75 74 2c 20 22 5c 6e 22 2c pend(pOut, "\n",
0ff0: 20 31 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45 78 1);.}../*.** Ex
1000: 70 61 6e 64 20 74 68 65 20 73 69 7a 65 20 6f 66 pand the size of
1010: 20 61 45 64 69 74 5b 5d 20 61 72 72 61 79 20 74 aEdit[] array t
1020: 6f 20 68 6f 6c 64 20 6e 45 64 69 74 20 65 6c 65 o hold nEdit ele
1030: 6d 65 6e 74 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 ments..*/.static
1040: 20 76 6f 69 64 20 65 78 70 61 6e 64 45 64 69 74 void expandEdit
1050: 28 44 43 6f 6e 74 65 78 74 20 2a 70 2c 20 69 6e (DContext *p, in
1060: 74 20 6e 45 64 69 74 29 7b 0a 20 20 69 6e 74 20 t nEdit){. int
1070: 2a 61 3b 0a 20 20 61 20 3d 20 72 65 61 6c 6c 6f *a;. a = reallo
1080: 63 28 70 2d 3e 61 45 64 69 74 2c 20 6e 45 64 69 c(p->aEdit, nEdi
1090: 74 2a 73 69 7a 65 6f 66 28 69 6e 74 29 29 3b 0a t*sizeof(int));.
10a0: 20 20 69 66 28 20 61 3d 3d 30 20 29 7b 0a 20 20 if( a==0 ){.
10b0: 20 20 66 72 65 65 28 20 70 2d 3e 61 45 64 69 74 free( p->aEdit
10c0: 20 29 3b 0a 20 20 20 20 70 2d 3e 6e 45 64 69 74 );. p->nEdit
10d0: 20 3d 20 30 3b 0a 20 20 20 20 6e 45 64 69 74 20 = 0;. nEdit
10e0: 3d 20 30 3b 0a 20 20 7d 0a 20 20 70 2d 3e 61 45 = 0;. }. p->aE
10f0: 64 69 74 20 3d 20 61 3b 0a 20 20 70 2d 3e 6e 45 dit = a;. p->nE
1100: 64 69 74 41 6c 6c 6f 63 20 3d 20 6e 45 64 69 74 ditAlloc = nEdit
1110: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 41 70 70 65 6e ;.}../*.** Appen
1120: 64 20 61 20 6e 65 77 20 43 4f 50 59 2f 44 45 4c d a new COPY/DEL
1130: 45 54 45 2f 49 4e 53 45 52 54 20 74 72 69 70 6c ETE/INSERT tripl
1140: 65 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 e..*/.static voi
1150: 64 20 61 70 70 65 6e 64 54 72 69 70 6c 65 28 44 d appendTriple(D
1160: 43 6f 6e 74 65 78 74 20 2a 70 2c 20 69 6e 74 20 Context *p, int
1170: 6e 43 6f 70 79 2c 20 69 6e 74 20 6e 44 65 6c 2c nCopy, int nDel,
1180: 20 69 6e 74 20 6e 49 6e 73 29 7b 0a 20 20 2f 2a int nIns){. /*
1190: 20 70 72 69 6e 74 66 28 22 41 50 50 45 4e 44 20 printf("APPEND
11a0: 25 64 2f 25 64 2f 25 64 5c 6e 22 2c 20 6e 43 6f %d/%d/%d\n", nCo
11b0: 70 79 2c 20 6e 44 65 6c 2c 20 6e 49 6e 73 29 3b py, nDel, nIns);
11c0: 20 2a 2f 0a 20 20 69 66 28 20 70 2d 3e 6e 45 64 */. if( p->nEd
11d0: 69 74 3e 3d 33 20 29 7b 0a 20 20 20 20 69 66 28 it>=3 ){. if(
11e0: 20 70 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e 45 64 p->aEdit[p->nEd
11f0: 69 74 2d 31 5d 3d 3d 30 20 29 7b 0a 20 20 20 20 it-1]==0 ){.
1200: 20 20 69 66 28 20 70 2d 3e 61 45 64 69 74 5b 70 if( p->aEdit[p
1210: 2d 3e 6e 45 64 69 74 2d 32 5d 3d 3d 30 20 29 7b ->nEdit-2]==0 ){
1220: 0a 20 20 20 20 20 20 20 20 70 2d 3e 61 45 64 69 . p->aEdi
1230: 74 5b 70 2d 3e 6e 45 64 69 74 2d 33 5d 20 2b 3d t[p->nEdit-3] +=
1240: 20 6e 43 6f 70 79 3b 0a 20 20 20 20 20 20 20 20 nCopy;.
1250: 70 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e 45 64 69 p->aEdit[p->nEdi
1260: 74 2d 32 5d 20 2b 3d 20 6e 44 65 6c 3b 0a 20 20 t-2] += nDel;.
1270: 20 20 20 20 20 20 70 2d 3e 61 45 64 69 74 5b 70 p->aEdit[p
1280: 2d 3e 6e 45 64 69 74 2d 31 5d 20 2b 3d 20 6e 49 ->nEdit-1] += nI
1290: 6e 73 3b 0a 20 20 20 20 20 20 20 20 72 65 74 75 ns;. retu
12a0: 72 6e 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 rn;. }.
12b0: 20 20 69 66 28 20 6e 43 6f 70 79 3d 3d 30 20 29 if( nCopy==0 )
12c0: 7b 0a 20 20 20 20 20 20 20 20 70 2d 3e 61 45 64 {. p->aEd
12d0: 69 74 5b 70 2d 3e 6e 45 64 69 74 2d 32 5d 20 2b it[p->nEdit-2] +
12e0: 3d 20 6e 44 65 6c 3b 0a 20 20 20 20 20 20 20 20 = nDel;.
12f0: 70 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e 45 64 69 p->aEdit[p->nEdi
1300: 74 2d 31 5d 20 2b 3d 20 6e 49 6e 73 3b 0a 20 20 t-1] += nIns;.
1310: 20 20 20 20 20 20 72 65 74 75 72 6e 3b 0a 20 20 return;.
1320: 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 }. }.
1330: 69 66 28 20 6e 43 6f 70 79 3d 3d 30 20 26 26 20 if( nCopy==0 &&
1340: 6e 44 65 6c 3d 3d 30 20 29 7b 0a 20 20 20 20 20 nDel==0 ){.
1350: 20 70 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e 45 64 p->aEdit[p->nEd
1360: 69 74 2d 31 5d 20 2b 3d 20 6e 49 6e 73 3b 0a 20 it-1] += nIns;.
1370: 20 20 20 20 20 72 65 74 75 72 6e 3b 0a 20 20 20 return;.
1380: 20 7d 0a 20 20 7d 20 20 0a 20 20 69 66 28 20 70 }. } . if( p
1390: 2d 3e 6e 45 64 69 74 2b 33 3e 70 2d 3e 6e 45 64 ->nEdit+3>p->nEd
13a0: 69 74 41 6c 6c 6f 63 20 29 7b 0a 20 20 20 20 65 itAlloc ){. e
13b0: 78 70 61 6e 64 45 64 69 74 28 70 2c 20 70 2d 3e xpandEdit(p, p->
13c0: 6e 45 64 69 74 2a 32 20 2b 20 31 35 29 3b 0a 20 nEdit*2 + 15);.
13d0: 20 20 20 69 66 28 20 70 2d 3e 61 45 64 69 74 3d if( p->aEdit=
13e0: 3d 30 20 29 20 72 65 74 75 72 6e 3b 0a 20 20 7d =0 ) return;. }
13f0: 0a 20 20 70 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e . p->aEdit[p->n
1400: 45 64 69 74 2b 2b 5d 20 3d 20 6e 43 6f 70 79 3b Edit++] = nCopy;
1410: 0a 20 20 70 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e . p->aEdit[p->n
1420: 45 64 69 74 2b 2b 5d 20 3d 20 6e 44 65 6c 3b 0a Edit++] = nDel;.
1430: 20 20 70 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e 45 p->aEdit[p->nE
1440: 64 69 74 2b 2b 5d 20 3d 20 6e 49 6e 73 3b 0a 7d dit++] = nIns;.}
1450: 0a 0a 0a 2f 2a 0a 2a 2a 20 47 69 76 65 6e 20 61 .../*.** Given a
1460: 20 64 69 66 66 20 63 6f 6e 74 65 78 74 20 69 6e diff context in
1470: 20 77 68 69 63 68 20 74 68 65 20 61 45 64 69 74 which the aEdit
1480: 5b 5d 20 61 72 72 61 79 20 68 61 73 20 62 65 65 [] array has bee
1490: 6e 20 66 69 6c 6c 65 64 0a 2a 2a 20 69 6e 2c 20 n filled.** in,
14a0: 63 6f 6d 70 75 74 65 20 61 20 63 6f 6e 74 65 78 compute a contex
14b0: 74 20 64 69 66 66 20 69 6e 74 6f 20 70 4f 75 74 t diff into pOut
14c0: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 ..*/.static void
14d0: 20 63 6f 6e 74 65 78 74 44 69 66 66 28 44 43 6f contextDiff(DCo
14e0: 6e 74 65 78 74 20 2a 70 2c 20 42 6c 6f 62 20 2a ntext *p, Blob *
14f0: 70 4f 75 74 2c 20 69 6e 74 20 6e 43 6f 6e 74 65 pOut, int nConte
1500: 78 74 29 7b 0a 20 20 44 4c 69 6e 65 20 2a 41 3b xt){. DLine *A;
1510: 20 20 20 20 20 2f 2a 20 4c 65 66 74 20 73 69 64 /* Left sid
1520: 65 20 6f 66 20 74 68 65 20 64 69 66 66 20 2a 2f e of the diff */
1530: 0a 20 20 44 4c 69 6e 65 20 2a 42 3b 20 20 20 20 . DLine *B;
1540: 20 2f 2a 20 52 69 67 68 74 20 73 69 64 65 20 6f /* Right side o
1550: 66 20 74 68 65 20 64 69 66 66 20 2a 2f 20 20 0a f the diff */ .
1560: 20 20 69 6e 74 20 61 20 3d 20 30 3b 20 20 20 20 int a = 0;
1570: 2f 2a 20 49 6e 64 65 78 20 6f 66 20 6e 65 78 74 /* Index of next
1580: 20 6c 69 6e 65 20 69 6e 20 41 5b 5d 20 2a 2f 0a line in A[] */.
1590: 20 20 69 6e 74 20 62 20 3d 20 30 3b 20 20 20 20 int b = 0;
15a0: 2f 2a 20 49 6e 64 65 78 20 6f 66 20 6e 65 78 74 /* Index of next
15b0: 20 6c 69 6e 65 20 69 6e 20 42 5b 5d 20 2a 2f 0a line in B[] */.
15c0: 20 20 69 6e 74 20 2a 52 3b 20 20 20 20 20 20 20 int *R;
15d0: 2f 2a 20 41 72 72 61 79 20 6f 66 20 43 4f 50 59 /* Array of COPY
15e0: 2f 44 45 4c 45 54 45 2f 49 4e 53 45 52 54 20 74 /DELETE/INSERT t
15f0: 72 69 70 6c 65 73 20 2a 2f 0a 20 20 69 6e 74 20 riples */. int
1600: 72 3b 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 r; /* Ind
1610: 65 78 20 69 6e 74 6f 20 52 5b 5d 20 2a 2f 0a 20 ex into R[] */.
1620: 20 69 6e 74 20 6e 72 3b 20 20 20 20 20 20 20 2f int nr; /
1630: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 43 4f 50 59 * Number of COPY
1640: 2f 44 45 4c 45 54 45 2f 49 4e 53 45 52 54 20 74 /DELETE/INSERT t
1650: 72 69 70 6c 65 73 20 74 6f 20 70 72 6f 63 65 73 riples to proces
1660: 73 20 2a 2f 0a 20 20 69 6e 74 20 6d 78 72 3b 20 s */. int mxr;
1670: 20 20 20 20 20 2f 2a 20 4d 61 78 69 6d 75 6d 20 /* Maximum
1680: 76 61 6c 75 65 20 66 6f 72 20 72 20 2a 2f 0a 20 value for r */.
1690: 20 69 6e 74 20 6e 61 2c 20 6e 62 3b 20 20 20 2f int na, nb; /
16a0: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 * Number of line
16b0: 73 20 73 68 6f 77 6e 20 66 72 6f 6d 20 41 20 61 s shown from A a
16c0: 6e 64 20 42 20 2a 2f 0a 20 20 69 6e 74 20 69 2c nd B */. int i,
16d0: 20 6a 3b 20 20 20 20 20 2f 2a 20 4c 6f 6f 70 20 j; /* Loop
16e0: 63 6f 75 6e 74 65 72 73 20 2a 2f 0a 20 20 69 6e counters */. in
16f0: 74 20 6d 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e t m; /* N
1700: 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 74 umber of lines t
1710: 6f 20 6f 75 74 70 75 74 20 2a 2f 0a 20 20 69 6e o output */. in
1720: 74 20 73 6b 69 70 3b 20 20 20 20 20 2f 2a 20 4e t skip; /* N
1730: 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 74 umber of lines t
1740: 6f 20 73 6b 69 70 20 2a 2f 0a 0a 20 20 41 20 3d o skip */.. A =
1750: 20 70 2d 3e 61 46 72 6f 6d 3b 0a 20 20 42 20 3d p->aFrom;. B =
1760: 20 70 2d 3e 61 54 6f 3b 0a 20 20 52 20 3d 20 70 p->aTo;. R = p
1770: 2d 3e 61 45 64 69 74 3b 0a 20 20 6d 78 72 20 3d ->aEdit;. mxr =
1780: 20 70 2d 3e 6e 45 64 69 74 3b 0a 20 20 69 66 28 p->nEdit;. if(
1790: 20 6d 78 72 3e 32 20 26 26 20 52 5b 6d 78 72 2d mxr>2 && R[mxr-
17a0: 31 5d 3d 3d 30 20 26 26 20 52 5b 6d 78 72 2d 32 1]==0 && R[mxr-2
17b0: 5d 3d 3d 30 20 29 7b 20 6d 78 72 20 2d 3d 20 33 ]==0 ){ mxr -= 3
17c0: 3b 20 7d 0a 20 20 66 6f 72 28 72 3d 30 3b 20 72 ; }. for(r=0; r
17d0: 3c 6d 78 72 3b 20 72 20 2b 3d 20 33 2a 6e 72 29 <mxr; r += 3*nr)
17e0: 7b 0a 20 20 20 20 2f 2a 20 46 69 67 75 72 65 20 {. /* Figure
17f0: 6f 75 74 20 68 6f 77 20 6d 61 6e 79 20 74 72 69 out how many tri
1800: 70 6c 65 73 20 74 6f 20 73 68 6f 77 20 69 6e 20 ples to show in
1810: 61 20 73 69 6e 67 6c 65 20 62 6c 6f 63 6b 20 2a a single block *
1820: 2f 0a 20 20 20 20 66 6f 72 28 6e 72 3d 31 3b 20 /. for(nr=1;
1830: 52 5b 72 2b 6e 72 2a 33 5d 3e 30 20 26 26 20 52 R[r+nr*3]>0 && R
1840: 5b 72 2b 6e 72 2a 33 5d 3c 6e 43 6f 6e 74 65 78 [r+nr*3]<nContex
1850: 74 2a 32 3b 20 6e 72 2b 2b 29 7b 7d 0a 20 20 20 t*2; nr++){}.
1860: 20 44 45 42 55 47 28 20 70 72 69 6e 74 66 28 22 DEBUG( printf("
1870: 72 3d 25 64 20 6e 72 3d 25 64 5c 6e 22 2c 20 72 r=%d nr=%d\n", r
1880: 2c 20 6e 72 29 3b 20 29 0a 0a 20 20 20 20 2f 2a , nr); ).. /*
1890: 20 46 6f 72 20 74 68 65 20 63 75 72 72 65 6e 74 For the current
18a0: 20 62 6c 6f 63 6b 20 63 6f 6d 70 72 69 73 69 6e block comprisin
18b0: 67 20 6e 72 20 74 72 69 70 6c 65 73 2c 20 66 69 g nr triples, fi
18c0: 67 75 72 65 20 6f 75 74 0a 20 20 20 20 2a 2a 20 gure out. **
18d0: 68 6f 77 20 6d 61 6e 79 20 6c 69 6e 65 73 20 6f how many lines o
18e0: 66 20 41 20 61 6e 64 20 42 20 61 72 65 20 74 6f f A and B are to
18f0: 20 62 65 20 64 69 73 70 6c 61 79 65 64 0a 20 20 be displayed.
1900: 20 20 2a 2f 0a 20 20 20 20 69 66 28 20 52 5b 72 */. if( R[r
1910: 5d 3e 6e 43 6f 6e 74 65 78 74 20 29 7b 0a 20 20 ]>nContext ){.
1920: 20 20 20 20 6e 61 20 3d 20 6e 62 20 3d 20 6e 43 na = nb = nC
1930: 6f 6e 74 65 78 74 3b 0a 20 20 20 20 20 20 73 6b ontext;. sk
1940: 69 70 20 3d 20 52 5b 72 5d 20 2d 20 6e 43 6f 6e ip = R[r] - nCon
1950: 74 65 78 74 3b 0a 20 20 20 20 7d 65 6c 73 65 7b text;. }else{
1960: 0a 20 20 20 20 20 20 6e 61 20 3d 20 6e 62 20 3d . na = nb =
1970: 20 52 5b 72 5d 3b 0a 20 20 20 20 20 20 73 6b 69 R[r];. ski
1980: 70 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20 20 p = 0;. }.
1990: 20 66 6f 72 28 69 3d 30 3b 20 69 3c 6e 72 3b 20 for(i=0; i<nr;
19a0: 69 2b 2b 29 7b 0a 20 20 20 20 20 20 6e 61 20 2b i++){. na +
19b0: 3d 20 52 5b 72 2b 69 2a 33 2b 31 5d 3b 0a 20 20 = R[r+i*3+1];.
19c0: 20 20 20 20 6e 62 20 2b 3d 20 52 5b 72 2b 69 2a nb += R[r+i*
19d0: 33 2b 32 5d 3b 0a 20 20 20 20 7d 0a 20 20 20 20 3+2];. }.
19e0: 69 66 28 20 52 5b 72 2b 6e 72 2a 33 5d 3e 6e 43 if( R[r+nr*3]>nC
19f0: 6f 6e 74 65 78 74 20 29 7b 0a 20 20 20 20 20 20 ontext ){.
1a00: 6e 61 20 2b 3d 20 6e 43 6f 6e 74 65 78 74 3b 0a na += nContext;.
1a10: 20 20 20 20 20 20 6e 62 20 2b 3d 20 6e 43 6f 6e nb += nCon
1a20: 74 65 78 74 3b 0a 20 20 20 20 7d 65 6c 73 65 7b text;. }else{
1a30: 0a 20 20 20 20 20 20 6e 61 20 2b 3d 20 52 5b 72 . na += R[r
1a40: 2b 6e 72 2a 33 5d 3b 0a 20 20 20 20 20 20 6e 62 +nr*3];. nb
1a50: 20 2b 3d 20 52 5b 72 2b 6e 72 2a 33 5d 3b 0a 20 += R[r+nr*3];.
1a60: 20 20 20 7d 0a 20 20 20 20 66 6f 72 28 69 3d 31 }. for(i=1
1a70: 3b 20 69 3c 6e 72 3b 20 69 2b 2b 29 7b 0a 20 20 ; i<nr; i++){.
1a80: 20 20 20 20 6e 61 20 2b 3d 20 52 5b 72 2b 69 2a na += R[r+i*
1a90: 33 5d 3b 0a 20 20 20 20 20 20 6e 62 20 2b 3d 20 3];. nb +=
1aa0: 52 5b 72 2b 69 2a 33 5d 3b 0a 20 20 20 20 7d 0a R[r+i*3];. }.
1ab0: 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 6e 64 66 blob_appendf
1ac0: 28 70 4f 75 74 2c 22 40 40 20 2d 25 64 2c 25 64 (pOut,"@@ -%d,%d
1ad0: 20 2b 25 64 2c 25 64 20 40 40 5c 6e 22 2c 20 61 +%d,%d @@\n", a
1ae0: 2b 73 6b 69 70 2b 31 2c 20 6e 61 2c 20 62 2b 73 +skip+1, na, b+s
1af0: 6b 69 70 2b 31 2c 20 6e 62 29 3b 0a 0a 20 20 20 kip+1, nb);..
1b00: 20 2f 2a 20 53 68 6f 77 20 74 68 65 20 69 6e 69 /* Show the ini
1b10: 74 69 61 6c 20 63 6f 6d 6d 6f 6e 20 61 72 65 61 tial common area
1b20: 20 2a 2f 0a 20 20 20 20 61 20 2b 3d 20 73 6b 69 */. a += ski
1b30: 70 3b 0a 20 20 20 20 62 20 2b 3d 20 73 6b 69 70 p;. b += skip
1b40: 3b 0a 20 20 20 20 6d 20 3d 20 52 5b 72 5d 20 2d ;. m = R[r] -
1b50: 20 73 6b 69 70 3b 0a 20 20 20 20 66 6f 72 28 6a skip;. for(j
1b60: 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 =0; j<m; j++){.
1b70: 20 20 20 20 20 61 70 70 65 6e 64 44 69 66 66 4c appendDiffL
1b80: 69 6e 65 28 70 4f 75 74 2c 20 22 20 22 2c 20 26 ine(pOut, " ", &
1b90: 41 5b 61 2b 6a 5d 29 3b 0a 20 20 20 20 7d 0a 20 A[a+j]);. }.
1ba0: 20 20 20 61 20 2b 3d 20 6d 3b 0a 20 20 20 20 62 a += m;. b
1bb0: 20 2b 3d 20 6d 3b 0a 0a 20 20 20 20 2f 2a 20 53 += m;.. /* S
1bc0: 68 6f 77 20 74 68 65 20 64 69 66 66 65 72 65 6e how the differen
1bd0: 63 65 73 20 2a 2f 0a 20 20 20 20 66 6f 72 28 69 ces */. for(i
1be0: 3d 30 3b 20 69 3c 6e 72 3b 20 69 2b 2b 29 7b 0a =0; i<nr; i++){.
1bf0: 20 20 20 20 20 20 6d 20 3d 20 52 5b 72 2b 69 2a m = R[r+i*
1c00: 33 2b 31 5d 3b 0a 20 20 20 20 20 20 66 6f 72 28 3+1];. for(
1c10: 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a j=0; j<m; j++){.
1c20: 20 20 20 20 20 20 20 20 61 70 70 65 6e 64 44 69 appendDi
1c30: 66 66 4c 69 6e 65 28 70 4f 75 74 2c 20 22 2d 22 ffLine(pOut, "-"
1c40: 2c 20 26 41 5b 61 2b 6a 5d 29 3b 0a 20 20 20 20 , &A[a+j]);.
1c50: 20 20 7d 0a 20 20 20 20 20 20 61 20 2b 3d 20 6d }. a += m
1c60: 3b 0a 20 20 20 20 20 20 6d 20 3d 20 52 5b 72 2b ;. m = R[r+
1c70: 69 2a 33 2b 32 5d 3b 0a 20 20 20 20 20 20 66 6f i*3+2];. fo
1c80: 72 28 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 r(j=0; j<m; j++)
1c90: 7b 0a 20 20 20 20 20 20 20 20 61 70 70 65 6e 64 {. append
1ca0: 44 69 66 66 4c 69 6e 65 28 70 4f 75 74 2c 20 22 DiffLine(pOut, "
1cb0: 2b 22 2c 20 26 42 5b 62 2b 6a 5d 29 3b 0a 20 20 +", &B[b+j]);.
1cc0: 20 20 20 20 7d 0a 20 20 20 20 20 20 62 20 2b 3d }. b +=
1cd0: 20 6d 3b 0a 20 20 20 20 20 20 69 66 28 20 69 3c m;. if( i<
1ce0: 6e 72 2d 31 20 29 7b 0a 20 20 20 20 20 20 20 20 nr-1 ){.
1cf0: 6d 20 3d 20 52 5b 72 2b 69 2a 33 2b 33 5d 3b 0a m = R[r+i*3+3];.
1d00: 20 20 20 20 20 20 20 20 66 6f 72 28 6a 3d 30 3b for(j=0;
1d10: 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 j<m; j++){.
1d20: 20 20 20 20 20 20 61 70 70 65 6e 64 44 69 66 66 appendDiff
1d30: 4c 69 6e 65 28 70 4f 75 74 2c 20 22 20 22 2c 20 Line(pOut, " ",
1d40: 26 42 5b 62 2b 6a 5d 29 3b 0a 20 20 20 20 20 20 &B[b+j]);.
1d50: 20 20 7d 0a 20 20 20 20 20 20 20 20 62 20 2b 3d }. b +=
1d60: 20 6d 3b 0a 20 20 20 20 20 20 20 20 61 20 2b 3d m;. a +=
1d70: 20 6d 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 m;. }.
1d80: 7d 0a 0a 20 20 20 20 2f 2a 20 53 68 6f 77 20 74 }.. /* Show t
1d90: 68 65 20 66 69 6e 61 6c 20 63 6f 6d 6d 6f 6e 20 he final common
1da0: 61 72 65 61 20 2a 2f 0a 20 20 20 20 61 73 73 65 area */. asse
1db0: 72 74 28 20 6e 72 3d 3d 69 20 29 3b 0a 20 20 20 rt( nr==i );.
1dc0: 20 6d 20 3d 20 52 5b 72 2b 6e 72 2a 33 5d 3b 0a m = R[r+nr*3];.
1dd0: 20 20 20 20 69 66 28 20 6d 3e 6e 43 6f 6e 74 65 if( m>nConte
1de0: 78 74 20 29 20 6d 20 3d 20 6e 43 6f 6e 74 65 78 xt ) m = nContex
1df0: 74 3b 0a 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 t;. for(j=0;
1e00: 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 j<m; j++){.
1e10: 20 61 70 70 65 6e 64 44 69 66 66 4c 69 6e 65 28 appendDiffLine(
1e20: 70 4f 75 74 2c 20 22 20 22 2c 20 26 42 5b 62 2b pOut, " ", &B[b+
1e30: 6a 5d 29 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 7d j]);. }. }.}
1e40: 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6d 70 61 72 65 20 ../*.** Compare
1e50: 74 77 6f 20 62 6c 6f 63 6b 73 20 6f 66 20 74 65 two blocks of te
1e60: 78 74 20 6f 6e 20 6c 69 6e 65 73 20 69 53 31 20 xt on lines iS1
1e70: 74 68 72 6f 75 67 68 20 69 45 31 2d 31 20 6f 66 through iE1-1 of
1e80: 20 74 68 65 20 61 46 72 6f 6d 5b 5d 0a 2a 2a 20 the aFrom[].**
1e90: 66 69 6c 65 20 61 6e 64 20 6c 69 6e 65 73 20 69 file and lines i
1ea0: 53 32 20 74 68 72 6f 75 67 68 20 69 45 32 2d 31 S2 through iE2-1
1eb0: 20 6f 66 20 74 68 65 20 61 54 6f 5b 5d 20 66 69 of the aTo[] fi
1ec0: 6c 65 2e 20 20 4c 6f 63 61 74 65 20 61 20 73 65 le. Locate a se
1ed0: 71 75 65 6e 63 65 0a 2a 2a 20 6f 66 20 6c 69 6e quence.** of lin
1ee0: 65 73 20 69 6e 20 74 68 65 73 65 20 74 77 6f 20 es in these two
1ef0: 62 6c 6f 63 6b 73 20 74 68 61 74 20 61 72 65 20 blocks that are
1f00: 65 78 61 63 74 6c 79 20 74 68 65 20 73 61 6d 65 exactly the same
1f10: 2e 20 20 52 65 74 75 72 6e 0a 2a 2a 20 74 68 65 . Return.** the
1f20: 20 62 6f 75 6e 64 73 20 6f 66 20 74 68 65 20 6d bounds of the m
1f30: 61 74 63 68 69 6e 67 20 73 65 71 75 65 6e 63 65 atching sequence
1f40: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 ..*/.static void
1f50: 20 6c 6f 6e 67 65 73 74 43 6f 6d 6d 6f 6e 53 65 longestCommonSe
1f60: 71 75 65 6e 63 65 28 0a 20 20 44 43 6f 6e 74 65 quence(. DConte
1f70: 78 74 20 2a 70 2c 20 20 20 20 20 20 20 20 20 20 xt *p,
1f80: 20 20 20 20 20 2f 2a 20 54 77 6f 20 66 69 6c 65 /* Two file
1f90: 73 20 62 65 69 6e 67 20 63 6f 6d 70 61 72 65 64 s being compared
1fa0: 20 2a 2f 0a 20 20 69 6e 74 20 69 53 31 2c 20 69 */. int iS1, i
1fb0: 6e 74 20 69 45 31 2c 20 20 20 20 20 20 20 20 20 nt iE1,
1fc0: 20 2f 2a 20 52 61 6e 67 65 20 6f 66 20 6c 69 6e /* Range of lin
1fd0: 65 73 20 69 6e 20 70 2d 3e 61 46 72 6f 6d 5b 5d es in p->aFrom[]
1fe0: 20 2a 2f 0a 20 20 69 6e 74 20 69 53 32 2c 20 69 */. int iS2, i
1ff0: 6e 74 20 69 45 32 2c 20 20 20 20 20 20 20 20 20 nt iE2,
2000: 20 2f 2a 20 52 61 6e 67 65 20 6f 66 20 6c 69 6e /* Range of lin
2010: 65 73 20 69 6e 20 70 2d 3e 61 54 6f 5b 5d 20 2a es in p->aTo[] *
2020: 2f 0a 20 20 69 6e 74 20 2a 70 69 53 58 2c 20 69 /. int *piSX, i
2030: 6e 74 20 2a 70 69 45 58 2c 20 20 20 20 20 20 2f nt *piEX, /
2040: 2a 20 57 72 69 74 65 20 70 2d 3e 61 46 72 6f 6d * Write p->aFrom
2050: 5b 5d 20 63 6f 6d 6d 6f 6e 20 73 65 67 6d 65 6e [] common segmen
2060: 74 20 68 65 72 65 20 2a 2f 0a 20 20 69 6e 74 20 t here */. int
2070: 2a 70 69 53 59 2c 20 69 6e 74 20 2a 70 69 45 59 *piSY, int *piEY
2080: 20 20 20 20 20 20 20 2f 2a 20 57 72 69 74 65 20 /* Write
2090: 70 2d 3e 61 54 6f 5b 5d 20 63 6f 6d 6d 6f 6e 20 p->aTo[] common
20a0: 73 65 67 6d 65 6e 74 20 68 65 72 65 20 2a 2f 0a segment here */.
20b0: 29 7b 0a 20 20 64 6f 75 62 6c 65 20 62 65 73 74 ){. double best
20c0: 53 63 6f 72 65 20 3d 20 2d 31 65 33 30 3b 20 20 Score = -1e30;
20d0: 2f 2a 20 42 65 73 74 20 73 63 6f 72 65 20 73 65 /* Best score se
20e0: 65 6e 20 73 6f 20 66 61 72 20 2a 2f 0a 20 20 69 en so far */. i
20f0: 6e 74 20 69 2c 20 6a 3b 20 20 20 20 20 20 20 20 nt i, j;
2100: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4c 6f 6f /* Loo
2110: 70 20 63 6f 75 6e 74 65 72 73 20 2a 2f 0a 20 20 p counters */.
2120: 69 6e 74 20 69 53 58 2c 20 69 53 59 2c 20 69 45 int iSX, iSY, iE
2130: 58 2c 20 69 45 59 3b 20 20 20 20 2f 2a 20 43 75 X, iEY; /* Cu
2140: 72 72 65 6e 74 20 6d 61 74 63 68 20 2a 2f 0a 20 rrent match */.
2150: 20 64 6f 75 62 6c 65 20 73 63 6f 72 65 3b 20 20 double score;
2160: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 /* C
2170: 75 72 72 65 6e 74 20 73 63 6f 72 65 20 2a 2f 0a urrent score */.
2180: 20 20 69 6e 74 20 73 6b 65 77 3b 20 20 20 20 20 int skew;
2190: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
21a0: 48 6f 77 20 6c 6f 70 73 69 64 65 64 20 69 73 20 How lopsided is
21b0: 74 68 65 20 6d 61 74 63 68 20 2a 2f 0a 20 20 69 the match */. i
21c0: 6e 74 20 64 69 73 74 3b 20 20 20 20 20 20 20 20 nt dist;
21d0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44 69 73 /* Dis
21e0: 74 61 6e 63 65 20 6f 66 20 6d 61 74 63 68 20 66 tance of match f
21f0: 72 6f 6d 20 63 65 6e 74 65 72 20 2a 2f 0a 20 20 rom center */.
2200: 69 6e 74 20 6d 69 64 3b 20 20 20 20 20 20 20 20 int mid;
2210: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 65 /* Ce
2220: 6e 74 65 72 20 6f 66 20 74 68 65 20 73 70 61 6e nter of the span
2230: 20 2a 2f 0a 20 20 69 6e 74 20 69 53 58 62 2c 20 */. int iSXb,
2240: 69 53 59 62 2c 20 69 45 58 62 2c 20 69 45 59 62 iSYb, iEXb, iEYb
2250: 3b 20 20 20 2f 2a 20 42 65 73 74 20 6d 61 74 63 ; /* Best matc
2260: 68 20 73 6f 20 66 61 72 20 2a 2f 0a 20 20 69 6e h so far */. in
2270: 74 20 69 53 58 70 2c 20 69 53 59 70 2c 20 69 45 t iSXp, iSYp, iE
2280: 58 70 2c 20 69 45 59 70 3b 20 20 20 2f 2a 20 50 Xp, iEYp; /* P
2290: 72 65 76 69 6f 75 73 20 6d 61 74 63 68 20 2a 2f revious match */
22a0: 0a 0a 20 20 69 53 58 62 20 3d 20 69 53 58 70 20 .. iSXb = iSXp
22b0: 3d 20 69 53 31 3b 0a 20 20 69 45 58 62 20 3d 20 = iS1;. iEXb =
22c0: 69 45 58 70 20 3d 20 69 53 31 3b 0a 20 20 69 53 iEXp = iS1;. iS
22d0: 59 62 20 3d 20 69 53 59 70 20 3d 20 69 53 32 3b Yb = iSYp = iS2;
22e0: 0a 20 20 69 45 59 62 20 3d 20 69 45 59 70 20 3d . iEYb = iEYp =
22f0: 20 69 53 32 3b 0a 20 20 6d 69 64 20 3d 20 28 69 iS2;. mid = (i
2300: 45 31 20 2b 20 69 53 31 29 2f 32 3b 0a 20 20 66 E1 + iS1)/2;. f
2310: 6f 72 28 69 3d 69 53 31 3b 20 69 3c 69 45 31 3b or(i=iS1; i<iE1;
2320: 20 69 2b 2b 29 7b 0a 20 20 20 20 69 6e 74 20 6c i++){. int l
2330: 69 6d 69 74 20 3d 20 30 3b 0a 20 20 20 20 6a 20 imit = 0;. j
2340: 3d 20 70 2d 3e 61 54 6f 5b 70 2d 3e 61 46 72 6f = p->aTo[p->aFro
2350: 6d 5b 69 5d 2e 68 20 25 20 70 2d 3e 6e 54 6f 5d m[i].h % p->nTo]
2360: 2e 69 48 61 73 68 3b 0a 20 20 20 20 77 68 69 6c .iHash;. whil
2370: 65 28 20 6a 3e 30 20 0a 20 20 20 20 20 20 26 26 e( j>0 . &&
2380: 20 28 6a 2d 31 3c 69 53 32 20 7c 7c 20 6a 3e 3d (j-1<iS2 || j>=
2390: 69 45 32 20 7c 7c 20 21 73 61 6d 65 5f 64 6c 69 iE2 || !same_dli
23a0: 6e 65 28 26 70 2d 3e 61 46 72 6f 6d 5b 69 5d 2c ne(&p->aFrom[i],
23b0: 20 26 70 2d 3e 61 54 6f 5b 6a 2d 31 5d 29 29 0a &p->aTo[j-1])).
23c0: 20 20 20 20 29 7b 0a 20 20 20 20 20 20 69 66 28 ){. if(
23d0: 20 6c 69 6d 69 74 2b 2b 20 3e 20 31 30 20 29 7b limit++ > 10 ){
23e0: 0a 20 20 20 20 20 20 20 20 6a 20 3d 20 30 3b 0a . j = 0;.
23f0: 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 break;.
2400: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 6a 20 3d }. j =
2410: 20 70 2d 3e 61 54 6f 5b 6a 2d 31 5d 2e 69 4e 65 p->aTo[j-1].iNe
2420: 78 74 3b 0a 20 20 20 20 7d 0a 20 20 20 20 69 66 xt;. }. if
2430: 28 20 6a 3d 3d 30 20 29 20 63 6f 6e 74 69 6e 75 ( j==0 ) continu
2440: 65 3b 0a 20 20 20 20 61 73 73 65 72 74 28 20 69 e;. assert( i
2450: 3e 3d 69 53 58 62 20 26 26 20 69 3e 3d 69 53 58 >=iSXb && i>=iSX
2460: 70 20 29 3b 0a 20 20 20 20 69 66 28 20 69 3c 69 p );. if( i<i
2470: 45 58 62 20 26 26 20 6a 3e 3d 69 53 59 62 20 26 EXb && j>=iSYb &
2480: 26 20 6a 3c 69 45 59 62 20 29 20 63 6f 6e 74 69 & j<iEYb ) conti
2490: 6e 75 65 3b 0a 20 20 20 20 69 66 28 20 69 3c 69 nue;. if( i<i
24a0: 45 58 70 20 26 26 20 6a 3e 3d 69 53 59 70 20 26 EXp && j>=iSYp &
24b0: 26 20 6a 3c 69 45 59 70 20 29 20 63 6f 6e 74 69 & j<iEYp ) conti
24c0: 6e 75 65 3b 0a 20 20 20 20 69 53 58 20 3d 20 69 nue;. iSX = i
24d0: 3b 0a 20 20 20 20 69 53 59 20 3d 20 6a 2d 31 3b ;. iSY = j-1;
24e0: 0a 20 20 20 20 77 68 69 6c 65 28 20 69 53 58 3e . while( iSX>
24f0: 69 53 31 20 26 26 20 69 53 59 3e 69 53 32 20 26 iS1 && iSY>iS2 &
2500: 26 20 73 61 6d 65 5f 64 6c 69 6e 65 28 26 70 2d & same_dline(&p-
2510: 3e 61 46 72 6f 6d 5b 69 53 58 2d 31 5d 2c 26 70 >aFrom[iSX-1],&p
2520: 2d 3e 61 54 6f 5b 69 53 59 2d 31 5d 29 20 29 7b ->aTo[iSY-1]) ){
2530: 0a 20 20 20 20 20 20 69 53 58 2d 2d 3b 0a 20 20 . iSX--;.
2540: 20 20 20 20 69 53 59 2d 2d 3b 0a 20 20 20 20 7d iSY--;. }
2550: 0a 20 20 20 20 69 45 58 20 3d 20 69 2b 31 3b 0a . iEX = i+1;.
2560: 20 20 20 20 69 45 59 20 3d 20 6a 3b 0a 20 20 20 iEY = j;.
2570: 20 77 68 69 6c 65 28 20 69 45 58 3c 69 45 31 20 while( iEX<iE1
2580: 26 26 20 69 45 59 3c 69 45 32 20 26 26 20 73 61 && iEY<iE2 && sa
2590: 6d 65 5f 64 6c 69 6e 65 28 26 70 2d 3e 61 46 72 me_dline(&p->aFr
25a0: 6f 6d 5b 69 45 58 5d 2c 26 70 2d 3e 61 54 6f 5b om[iEX],&p->aTo[
25b0: 69 45 59 5d 29 20 29 7b 0a 20 20 20 20 20 20 69 iEY]) ){. i
25c0: 45 58 2b 2b 3b 0a 20 20 20 20 20 20 69 45 59 2b EX++;. iEY+
25d0: 2b 3b 0a 20 20 20 20 7d 0a 20 20 20 20 73 6b 65 +;. }. ske
25e0: 77 20 3d 20 28 69 53 58 2d 69 53 31 29 20 2d 20 w = (iSX-iS1) -
25f0: 28 69 53 59 2d 69 53 32 29 3b 0a 20 20 20 20 69 (iSY-iS2);. i
2600: 66 28 20 73 6b 65 77 3c 30 20 29 20 73 6b 65 77 f( skew<0 ) skew
2610: 20 3d 20 2d 73 6b 65 77 3b 0a 20 20 20 20 64 69 = -skew;. di
2620: 73 74 20 3d 20 28 69 53 58 2b 69 45 58 29 2f 32 st = (iSX+iEX)/2
2630: 20 2d 20 6d 69 64 3b 0a 20 20 20 20 69 66 28 20 - mid;. if(
2640: 64 69 73 74 3c 30 20 29 20 64 69 73 74 20 3d 20 dist<0 ) dist =
2650: 2d 64 69 73 74 3b 0a 20 20 20 20 73 63 6f 72 65 -dist;. score
2660: 20 3d 20 28 69 45 58 20 2d 20 69 53 58 29 20 2d = (iEX - iSX) -
2670: 20 30 2e 30 35 2a 73 6b 65 77 20 2d 20 30 2e 30 0.05*skew - 0.0
2680: 35 2a 64 69 73 74 3b 0a 20 20 20 20 69 66 28 20 5*dist;. if(
2690: 73 63 6f 72 65 3e 62 65 73 74 53 63 6f 72 65 20 score>bestScore
26a0: 29 7b 0a 20 20 20 20 20 20 62 65 73 74 53 63 6f ){. bestSco
26b0: 72 65 20 3d 20 73 63 6f 72 65 3b 0a 20 20 20 20 re = score;.
26c0: 20 20 69 53 58 62 20 3d 20 69 53 58 3b 0a 20 20 iSXb = iSX;.
26d0: 20 20 20 20 69 53 59 62 20 3d 20 69 53 59 3b 0a iSYb = iSY;.
26e0: 20 20 20 20 20 20 69 45 58 62 20 3d 20 69 45 58 iEXb = iEX
26f0: 3b 0a 20 20 20 20 20 20 69 45 59 62 20 3d 20 69 ;. iEYb = i
2700: 45 59 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 EY;. }else{.
2710: 20 20 20 20 20 69 53 58 70 20 3d 20 69 53 58 3b iSXp = iSX;
2720: 0a 20 20 20 20 20 20 69 53 59 70 20 3d 20 69 53 . iSYp = iS
2730: 59 3b 0a 20 20 20 20 20 20 69 45 58 70 20 3d 20 Y;. iEXp =
2740: 69 45 58 3b 0a 20 20 20 20 20 20 69 45 59 70 20 iEX;. iEYp
2750: 3d 20 69 45 59 3b 0a 20 20 20 20 7d 0a 20 20 7d = iEY;. }. }
2760: 0a 20 20 2a 70 69 53 58 20 3d 20 69 53 58 62 3b . *piSX = iSXb;
2770: 0a 20 20 2a 70 69 53 59 20 3d 20 69 53 59 62 3b . *piSY = iSYb;
2780: 0a 20 20 2a 70 69 45 58 20 3d 20 69 45 58 62 3b . *piEX = iEXb;
2790: 0a 20 20 2a 70 69 45 59 20 3d 20 69 45 59 62 3b . *piEY = iEYb;
27a0: 0a 20 20 2f 2a 20 70 72 69 6e 74 66 28 22 4c 43 . /* printf("LC
27b0: 53 28 25 64 2e 2e 25 64 2f 25 64 2e 2e 25 64 29 S(%d..%d/%d..%d)
27c0: 20 3d 20 25 64 2e 2e 25 64 2f 25 64 2e 2e 25 64 = %d..%d/%d..%d
27d0: 5c 6e 22 2c 20 0a 20 20 20 20 20 69 53 31 2c 20 \n", . iS1,
27e0: 69 45 31 2c 20 69 53 32 2c 20 69 45 32 2c 20 2a iE1, iS2, iE2, *
27f0: 70 69 53 58 2c 20 2a 70 69 45 58 2c 20 2a 70 69 piSX, *piEX, *pi
2800: 53 59 2c 20 2a 70 69 45 59 29 3b 20 20 2a 2f 0a SY, *piEY); */.
2810: 7d 0a 0a 2f 2a 0a 2a 2a 20 44 6f 20 61 20 73 69 }../*.** Do a si
2820: 6e 67 6c 65 20 73 74 65 70 20 69 6e 20 74 68 65 ngle step in the
2830: 20 64 69 66 66 65 72 65 6e 63 65 2e 20 20 43 6f difference. Co
2840: 6d 70 75 74 65 20 61 20 73 65 71 75 65 6e 63 65 mpute a sequence
2850: 20 6f 66 0a 2a 2a 20 63 6f 70 79 2f 64 65 6c 65 of.** copy/dele
2860: 74 65 2f 69 6e 73 65 72 74 20 73 74 65 70 73 20 te/insert steps
2870: 74 68 61 74 20 77 69 6c 6c 20 63 6f 6e 76 65 72 that will conver
2880: 74 20 6c 69 6e 65 73 20 69 53 31 20 74 68 72 6f t lines iS1 thro
2890: 75 67 68 20 69 45 31 2d 31 20 6f 66 0a 2a 2a 20 ugh iE1-1 of.**
28a0: 74 68 65 20 69 6e 70 75 74 20 69 6e 74 6f 20 6c the input into l
28b0: 69 6e 65 73 20 69 53 32 20 74 68 72 6f 75 67 68 ines iS2 through
28c0: 20 69 45 32 2d 31 20 6f 66 20 74 68 65 20 6f 75 iE2-1 of the ou
28d0: 74 70 75 74 20 61 6e 64 20 77 72 69 74 65 0a 2a tput and write.*
28e0: 2a 20 74 68 61 74 20 73 65 71 75 65 6e 63 65 20 * that sequence
28f0: 69 6e 74 6f 20 74 68 65 20 64 69 66 66 65 72 65 into the differe
2900: 6e 63 65 20 63 6f 6e 74 65 78 74 2e 0a 2a 2a 0a nce context..**.
2910: 2a 2a 20 54 68 65 20 61 6c 67 6f 72 69 74 68 6d ** The algorithm
2920: 20 69 73 20 74 6f 20 66 69 6e 64 20 61 20 62 6c is to find a bl
2930: 6f 63 6b 20 6f 66 20 63 6f 6d 6d 6f 6e 20 74 65 ock of common te
2940: 78 74 20 6e 65 61 72 20 74 68 65 20 6d 69 64 64 xt near the midd
2950: 6c 65 0a 2a 2a 20 6f 66 20 74 68 65 20 74 77 6f le.** of the two
2960: 20 73 65 67 6d 65 6e 74 73 20 62 65 69 6e 67 20 segments being
2970: 64 69 66 66 65 64 2e 20 20 54 68 65 6e 20 72 65 diffed. Then re
2980: 63 75 72 73 69 76 65 6c 79 20 63 6f 6d 70 75 74 cursively comput
2990: 65 0a 2a 2a 20 64 69 66 66 65 72 65 6e 63 65 73 e.** differences
29a0: 20 6f 6e 20 74 68 65 20 62 6c 6f 63 6b 73 20 62 on the blocks b
29b0: 65 66 6f 72 65 20 61 6e 64 20 61 66 74 65 72 20 efore and after
29c0: 74 68 61 74 20 63 6f 6d 6d 6f 6e 20 73 65 67 6d that common segm
29d0: 65 6e 74 2e 0a 2a 2a 20 53 70 65 63 69 61 6c 20 ent..** Special
29e0: 63 61 73 65 73 20 61 70 70 6c 79 20 69 66 20 65 cases apply if e
29f0: 69 74 68 65 72 20 69 6e 70 75 74 20 73 65 67 6d ither input segm
2a00: 65 6e 74 20 69 73 20 65 6d 70 74 79 20 6f 72 20 ent is empty or
2a10: 69 66 20 74 68 65 0a 2a 2a 20 74 77 6f 20 73 65 if the.** two se
2a20: 67 6d 65 6e 74 73 20 68 61 76 65 20 6e 6f 20 74 gments have no t
2a30: 65 78 74 20 69 6e 20 63 6f 6d 6d 6f 6e 2e 0a 2a ext in common..*
2a40: 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 64 69 /.static void di
2a50: 66 66 5f 73 74 65 70 28 44 43 6f 6e 74 65 78 74 ff_step(DContext
2a60: 20 2a 70 2c 20 69 6e 74 20 69 53 31 2c 20 69 6e *p, int iS1, in
2a70: 74 20 69 45 31 2c 20 69 6e 74 20 69 53 32 2c 20 t iE1, int iS2,
2a80: 69 6e 74 20 69 45 32 29 7b 0a 20 20 69 6e 74 20 int iE2){. int
2a90: 69 53 58 2c 20 69 45 58 2c 20 69 53 59 2c 20 69 iSX, iEX, iSY, i
2aa0: 45 59 3b 0a 0a 20 20 69 66 28 20 69 45 31 3c 3d EY;.. if( iE1<=
2ab0: 69 53 31 20 29 7b 0a 20 20 20 20 2f 2a 20 54 68 iS1 ){. /* Th
2ac0: 65 20 66 69 72 73 74 20 73 65 67 6d 65 6e 74 20 e first segment
2ad0: 69 73 20 65 6d 70 74 79 20 2a 2f 0a 20 20 20 20 is empty */.
2ae0: 69 66 28 20 69 45 32 3e 69 53 32 20 29 7b 0a 20 if( iE2>iS2 ){.
2af0: 20 20 20 20 20 61 70 70 65 6e 64 54 72 69 70 6c appendTripl
2b00: 65 28 70 2c 20 30 2c 20 30 2c 20 69 45 32 2d 69 e(p, 0, 0, iE2-i
2b10: 53 32 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 S2);. }. r
2b20: 65 74 75 72 6e 3b 0a 20 20 7d 0a 20 20 69 66 28 eturn;. }. if(
2b30: 20 69 45 32 3c 3d 69 53 32 20 29 7b 0a 20 20 20 iE2<=iS2 ){.
2b40: 20 2f 2a 20 54 68 65 20 73 65 63 6f 6e 64 20 73 /* The second s
2b50: 65 67 6d 65 6e 74 20 69 73 20 65 6d 70 74 79 20 egment is empty
2b60: 2a 2f 0a 20 20 20 20 61 70 70 65 6e 64 54 72 69 */. appendTri
2b70: 70 6c 65 28 70 2c 20 30 2c 20 69 45 31 2d 69 53 ple(p, 0, iE1-iS
2b80: 31 2c 20 30 29 3b 0a 20 20 20 20 72 65 74 75 72 1, 0);. retur
2b90: 6e 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 46 69 6e n;. }.. /* Fin
2ba0: 64 20 74 68 65 20 6c 6f 6e 67 65 73 74 20 6d 61 d the longest ma
2bb0: 74 63 68 69 6e 67 20 73 65 67 6d 65 6e 74 20 62 tching segment b
2bc0: 65 74 77 65 65 6e 20 74 68 65 20 74 77 6f 20 73 etween the two s
2bd0: 65 71 75 65 6e 63 65 73 20 2a 2f 0a 20 20 6c 6f equences */. lo
2be0: 6e 67 65 73 74 43 6f 6d 6d 6f 6e 53 65 71 75 65 ngestCommonSeque
2bf0: 6e 63 65 28 70 2c 20 69 53 31 2c 20 69 45 31 2c nce(p, iS1, iE1,
2c00: 20 69 53 32 2c 20 69 45 32 2c 20 26 69 53 58 2c iS2, iE2, &iSX,
2c10: 20 26 69 45 58 2c 20 26 69 53 59 2c 20 26 69 45 &iEX, &iSY, &iE
2c20: 59 29 3b 0a 0a 20 20 69 66 28 20 69 45 58 3e 69 Y);.. if( iEX>i
2c30: 53 58 20 29 7b 0a 20 20 20 20 2f 2a 20 41 20 63 SX ){. /* A c
2c40: 6f 6d 6d 6f 6e 20 73 65 67 65 6d 65 6e 74 20 68 ommon segement h
2c50: 61 73 20 62 65 65 6e 20 66 6f 75 6e 64 2e 0a 20 as been found..
2c60: 20 20 20 2a 2a 20 52 65 63 75 72 73 69 76 65 6c ** Recursivel
2c70: 79 20 64 69 66 66 20 65 69 74 68 65 72 20 73 69 y diff either si
2c80: 64 65 20 6f 66 20 74 68 65 20 6d 61 74 63 68 69 de of the matchi
2c90: 6e 67 20 73 65 67 6d 65 6e 74 20 2a 2f 0a 20 20 ng segment */.
2ca0: 20 20 64 69 66 66 5f 73 74 65 70 28 70 2c 20 69 diff_step(p, i
2cb0: 53 31 2c 20 69 53 58 2c 20 69 53 32 2c 20 69 53 S1, iSX, iS2, iS
2cc0: 59 29 3b 0a 20 20 20 20 69 66 28 20 69 45 58 3e Y);. if( iEX>
2cd0: 69 53 58 20 29 7b 0a 20 20 20 20 20 20 61 70 70 iSX ){. app
2ce0: 65 6e 64 54 72 69 70 6c 65 28 70 2c 20 69 45 58 endTriple(p, iEX
2cf0: 20 2d 20 69 53 58 2c 20 30 2c 20 30 29 3b 0a 20 - iSX, 0, 0);.
2d00: 20 20 20 7d 0a 20 20 20 20 64 69 66 66 5f 73 74 }. diff_st
2d10: 65 70 28 70 2c 20 69 45 58 2c 20 69 45 31 2c 20 ep(p, iEX, iE1,
2d20: 69 45 59 2c 20 69 45 32 29 3b 0a 20 20 7d 65 6c iEY, iE2);. }el
2d30: 73 65 7b 0a 20 20 20 20 2f 2a 20 54 68 65 20 74 se{. /* The t
2d40: 77 6f 20 73 65 67 6d 65 6e 74 73 20 68 61 76 65 wo segments have
2d50: 20 6e 6f 74 68 69 6e 67 20 69 6e 20 63 6f 6d 6d nothing in comm
2d60: 6f 6e 2e 20 20 44 65 6c 65 74 65 20 74 68 65 20 on. Delete the
2d70: 66 69 72 73 74 20 74 68 65 6e 0a 20 20 20 20 2a first then. *
2d80: 2a 20 69 6e 73 65 72 74 20 74 68 65 20 73 65 63 * insert the sec
2d90: 6f 6e 64 2e 20 2a 2f 0a 20 20 20 20 61 70 70 65 ond. */. appe
2da0: 6e 64 54 72 69 70 6c 65 28 70 2c 20 30 2c 20 69 ndTriple(p, 0, i
2db0: 45 31 2d 69 53 31 2c 20 69 45 32 2d 69 53 32 29 E1-iS1, iE2-iS2)
2dc0: 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 ;. }.}../*.** C
2dd0: 6f 6d 70 75 74 65 20 74 68 65 20 64 69 66 66 65 ompute the diffe
2de0: 72 65 6e 63 65 73 20 62 65 74 77 65 65 6e 20 74 rences between t
2df0: 77 6f 20 66 69 6c 65 73 20 61 6c 72 65 61 64 79 wo files already
2e00: 20 6c 6f 61 64 65 64 20 69 6e 74 6f 0a 2a 2a 20 loaded into.**
2e10: 74 68 65 20 44 43 6f 6e 74 65 78 74 20 73 74 72 the DContext str
2e20: 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a 2a 20 41 20 ucture..**.** A
2e30: 64 69 76 69 64 65 20 61 6e 64 20 63 6f 6e 71 75 divide and conqu
2e40: 65 72 20 74 65 63 68 6e 69 71 75 65 20 69 73 20 er technique is
2e50: 75 73 65 64 2e 20 20 57 65 20 6c 6f 6f 6b 20 66 used. We look f
2e60: 6f 72 20 61 20 6c 61 72 67 65 0a 2a 2a 20 62 6c or a large.** bl
2e70: 6f 63 6b 20 6f 66 20 63 6f 6d 6d 6f 6e 20 74 65 ock of common te
2e80: 78 74 20 74 68 61 74 20 69 73 20 69 6e 20 74 68 xt that is in th
2e90: 65 20 6d 69 64 64 6c 65 20 6f 66 20 62 6f 74 68 e middle of both
2ea0: 20 66 69 6c 65 73 2e 20 20 54 68 65 6e 0a 2a 2a files. Then.**
2eb0: 20 63 6f 6d 70 75 74 65 20 74 68 65 20 64 69 66 compute the dif
2ec0: 66 65 72 65 6e 63 65 20 6f 6e 20 74 68 6f 73 65 ference on those
2ed0: 20 70 61 72 74 73 20 6f 66 20 74 68 65 20 66 69 parts of the fi
2ee0: 6c 65 20 62 65 66 6f 72 65 20 61 6e 64 0a 2a 2a le before and.**
2ef0: 20 61 66 74 65 72 20 74 68 65 20 63 6f 6d 6d 6f after the commo
2f00: 6e 20 62 6c 6f 63 6b 2e 20 20 54 68 69 73 20 74 n block. This t
2f10: 65 63 68 6e 69 71 75 65 20 69 73 20 66 61 73 74 echnique is fast
2f20: 2c 20 62 75 74 20 69 74 20 64 6f 65 73 0a 2a 2a , but it does.**
2f30: 20 6e 6f 74 20 6e 65 63 65 73 73 61 72 69 6c 79 not necessarily
2f40: 20 67 65 6e 65 72 61 74 65 20 74 68 65 20 6d 69 generate the mi
2f50: 6e 69 6d 75 6d 20 64 69 66 66 65 72 65 6e 63 65 nimum difference
2f60: 20 73 65 74 2e 20 20 4f 6e 20 74 68 65 0a 2a 2a set. On the.**
2f70: 20 6f 74 68 65 72 20 68 61 6e 64 2c 20 77 65 20 other hand, we
2f80: 64 6f 20 6e 6f 74 20 6e 65 65 64 20 61 20 6d 69 do not need a mi
2f90: 6e 69 6d 75 6d 20 64 69 66 66 65 72 65 6e 63 65 nimum difference
2fa0: 20 73 65 74 2c 20 6f 6e 6c 79 20 6f 6e 65 0a 2a set, only one.*
2fb0: 2a 20 74 68 61 74 20 6d 61 6b 65 73 20 73 65 6e * that makes sen
2fc0: 73 65 20 74 6f 20 68 75 6d 61 6e 20 72 65 61 64 se to human read
2fd0: 65 72 73 2c 20 77 68 69 63 68 20 74 68 69 73 20 ers, which this
2fe0: 61 6c 67 6f 72 69 74 68 6d 20 64 6f 65 73 2e 0a algorithm does..
2ff0: 2a 2a 0a 2a 2a 20 41 6e 79 20 63 6f 6d 6d 6f 6e **.** Any common
3000: 20 74 65 78 74 20 61 74 20 74 68 65 20 62 65 67 text at the beg
3010: 69 6e 6e 69 6e 67 20 61 6e 64 20 65 6e 64 20 6f inning and end o
3020: 66 20 74 68 65 20 74 77 6f 20 66 69 6c 65 73 20 f the two files
3030: 69 73 0a 2a 2a 20 72 65 6d 6f 76 65 64 20 62 65 is.** removed be
3040: 66 6f 72 65 20 73 74 61 72 74 69 6e 67 20 74 68 fore starting th
3050: 65 20 64 69 76 69 64 65 2d 61 6e 64 2d 63 6f 6e e divide-and-con
3060: 71 75 65 72 20 61 6c 67 6f 72 69 74 68 6d 2e 0a quer algorithm..
3070: 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 64 */.static void d
3080: 69 66 66 5f 61 6c 6c 28 44 43 6f 6e 74 65 78 74 iff_all(DContext
3090: 20 2a 70 29 7b 0a 20 20 69 6e 74 20 6d 6e 45 2c *p){. int mnE,
30a0: 20 69 53 2c 20 69 45 31 2c 20 69 45 32 3b 0a 0a iS, iE1, iE2;..
30b0: 20 20 2f 2a 20 43 61 72 76 65 20 6f 66 66 20 74 /* Carve off t
30c0: 68 65 20 63 6f 6d 6d 6f 6e 20 68 65 61 64 65 72 he common header
30d0: 20 61 6e 64 20 66 6f 6f 74 65 72 20 2a 2f 0a 20 and footer */.
30e0: 20 69 45 31 20 3d 20 70 2d 3e 6e 46 72 6f 6d 3b iE1 = p->nFrom;
30f0: 0a 20 20 69 45 32 20 3d 20 70 2d 3e 6e 54 6f 3b . iE2 = p->nTo;
3100: 0a 20 20 77 68 69 6c 65 28 20 69 45 31 3e 30 20 . while( iE1>0
3110: 26 26 20 69 45 32 3e 30 20 26 26 20 73 61 6d 65 && iE2>0 && same
3120: 5f 64 6c 69 6e 65 28 26 70 2d 3e 61 46 72 6f 6d _dline(&p->aFrom
3130: 5b 69 45 31 2d 31 5d 2c 20 26 70 2d 3e 61 54 6f [iE1-1], &p->aTo
3140: 5b 69 45 32 2d 31 5d 29 20 29 7b 0a 20 20 20 20 [iE2-1]) ){.
3150: 69 45 31 2d 2d 3b 0a 20 20 20 20 69 45 32 2d 2d iE1--;. iE2--
3160: 3b 0a 20 20 7d 0a 20 20 6d 6e 45 20 3d 20 69 45 ;. }. mnE = iE
3170: 31 3c 69 45 32 20 3f 20 69 45 31 20 3a 20 69 45 1<iE2 ? iE1 : iE
3180: 32 3b 0a 20 20 66 6f 72 28 69 53 3d 30 3b 20 69 2;. for(iS=0; i
3190: 53 3c 6d 6e 45 20 26 26 20 73 61 6d 65 5f 64 6c S<mnE && same_dl
31a0: 69 6e 65 28 26 70 2d 3e 61 46 72 6f 6d 5b 69 53 ine(&p->aFrom[iS
31b0: 5d 2c 26 70 2d 3e 61 54 6f 5b 69 53 5d 29 3b 20 ],&p->aTo[iS]);
31c0: 69 53 2b 2b 29 7b 7d 0a 0a 20 20 2f 2a 20 64 6f iS++){}.. /* do
31d0: 20 74 68 65 20 64 69 66 66 65 72 65 6e 63 65 20 the difference
31e0: 2a 2f 0a 20 20 69 66 28 20 69 53 3e 30 20 29 7b */. if( iS>0 ){
31f0: 0a 20 20 20 20 61 70 70 65 6e 64 54 72 69 70 6c . appendTripl
3200: 65 28 70 2c 20 69 53 2c 20 30 2c 20 30 29 3b 0a e(p, iS, 0, 0);.
3210: 20 20 7d 0a 20 20 64 69 66 66 5f 73 74 65 70 28 }. diff_step(
3220: 70 2c 20 69 53 2c 20 69 45 31 2c 20 69 53 2c 20 p, iS, iE1, iS,
3230: 69 45 32 29 3b 0a 20 20 69 66 28 20 69 45 31 3c iE2);. if( iE1<
3240: 70 2d 3e 6e 46 72 6f 6d 20 29 7b 0a 20 20 20 20 p->nFrom ){.
3250: 61 70 70 65 6e 64 54 72 69 70 6c 65 28 70 2c 20 appendTriple(p,
3260: 70 2d 3e 6e 46 72 6f 6d 20 2d 20 69 45 31 2c 20 p->nFrom - iE1,
3270: 30 2c 20 30 29 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 0, 0);. }.. /*
3280: 20 54 65 72 6d 69 6e 61 74 65 20 74 68 65 20 43 Terminate the C
3290: 4f 50 59 2f 44 45 4c 45 54 45 2f 49 4e 53 45 52 OPY/DELETE/INSER
32a0: 54 20 74 72 69 70 6c 65 73 20 77 69 74 68 20 74 T triples with t
32b0: 68 72 65 65 20 7a 65 72 6f 73 20 2a 2f 0a 20 20 hree zeros */.
32c0: 65 78 70 61 6e 64 45 64 69 74 28 70 2c 20 70 2d expandEdit(p, p-
32d0: 3e 6e 45 64 69 74 2b 33 29 3b 0a 20 20 69 66 28 >nEdit+3);. if(
32e0: 20 70 2d 3e 61 45 64 69 74 20 29 7b 0a 20 20 20 p->aEdit ){.
32f0: 20 70 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e 45 64 p->aEdit[p->nEd
3300: 69 74 2b 2b 5d 20 3d 20 30 3b 0a 20 20 20 20 70 it++] = 0;. p
3310: 2d 3e 61 45 64 69 74 5b 70 2d 3e 6e 45 64 69 74 ->aEdit[p->nEdit
3320: 2b 2b 5d 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e ++] = 0;. p->
3330: 61 45 64 69 74 5b 70 2d 3e 6e 45 64 69 74 2b 2b aEdit[p->nEdit++
3340: 5d 20 3d 20 30 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a ] = 0;. }.}../*
3350: 0a 2a 2a 20 47 65 6e 65 72 61 74 65 20 61 20 72 .** Generate a r
3360: 65 70 6f 72 74 20 6f 66 20 74 68 65 20 64 69 66 eport of the dif
3370: 66 65 72 65 6e 63 65 73 20 62 65 74 77 65 65 6e ferences between
3380: 20 66 69 6c 65 73 20 70 41 20 61 6e 64 20 70 42 files pA and pB
3390: 2e 0a 2a 2a 20 49 66 20 70 4f 75 74 20 69 73 20 ..** If pOut is
33a0: 6e 6f 74 20 4e 55 4c 4c 20 74 68 65 6e 20 61 20 not NULL then a
33b0: 75 6e 69 66 69 65 64 20 64 69 66 66 20 69 73 20 unified diff is
33c0: 61 70 70 65 6e 64 65 64 20 74 68 65 72 65 2e 20 appended there.
33d0: 20 49 74 0a 2a 2a 20 69 73 20 61 73 73 75 6d 65 It.** is assume
33e0: 64 20 74 68 61 74 20 70 4f 75 74 20 68 61 73 20 d that pOut has
33f0: 61 6c 72 65 61 64 79 20 62 65 65 6e 20 69 6e 69 already been ini
3400: 74 69 61 6c 69 7a 65 64 2e 20 20 49 66 20 70 4f tialized. If pO
3410: 75 74 20 69 73 0a 2a 2a 20 4e 55 4c 4c 2c 20 74 ut is.** NULL, t
3420: 68 65 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f hen a pointer to
3430: 20 61 6e 20 61 72 72 61 79 20 6f 66 20 69 6e 74 an array of int
3440: 65 67 65 72 73 20 69 73 20 72 65 74 75 72 6e 65 egers is returne
3450: 64 2e 20 20 0a 2a 2a 20 54 68 65 20 69 6e 74 65 d. .** The inte
3460: 67 65 72 73 20 63 6f 6d 65 20 69 6e 20 74 72 69 gers come in tri
3470: 70 6c 65 73 2e 20 20 46 6f 72 20 65 61 63 68 20 ples. For each
3480: 74 72 69 70 6c 65 2c 0a 2a 2a 20 74 68 65 20 65 triple,.** the e
3490: 6c 65 6d 65 6e 74 73 20 61 72 65 20 74 68 65 20 lements are the
34a0: 6e 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 number of lines
34b0: 63 6f 70 69 65 64 2c 20 74 68 65 20 6e 75 6d 62 copied, the numb
34c0: 65 72 20 6f 66 0a 2a 2a 20 6c 69 6e 65 73 20 64 er of.** lines d
34d0: 65 6c 65 74 65 64 2c 20 61 6e 64 20 74 68 65 20 eleted, and the
34e0: 6e 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 number of lines
34f0: 69 6e 73 65 72 74 65 64 2e 20 20 54 68 65 20 76 inserted. The v
3500: 65 63 74 6f 72 0a 2a 2a 20 69 73 20 74 65 72 6d ector.** is term
3510: 69 6e 61 74 65 64 20 62 79 20 61 20 74 72 69 70 inated by a trip
3520: 6c 65 20 6f 66 20 61 6c 6c 20 7a 65 72 6f 73 2e le of all zeros.
3530: 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 64 69 66 66 .**.** This diff
3540: 20 75 74 69 6c 69 74 79 20 64 6f 65 73 20 6e 6f utility does no
3550: 74 20 77 6f 72 6b 20 6f 6e 20 62 69 6e 61 72 79 t work on binary
3560: 20 66 69 6c 65 73 2e 20 20 49 66 20 61 20 62 69 files. If a bi
3570: 6e 61 72 79 0a 2a 2a 20 66 69 6c 65 20 69 73 20 nary.** file is
3580: 65 6e 63 6f 75 6e 74 65 72 65 64 2c 20 30 20 69 encountered, 0 i
3590: 73 20 72 65 74 75 72 6e 65 64 20 61 6e 64 20 70 s returned and p
35a0: 4f 75 74 20 69 73 20 77 72 69 74 74 65 6e 20 77 Out is written w
35b0: 69 74 68 0a 2a 2a 20 74 65 78 74 20 22 63 61 6e ith.** text "can
35c0: 6e 6f 74 20 63 6f 6d 70 75 74 65 20 64 69 66 66 not compute diff
35d0: 65 72 65 6e 63 65 20 62 65 74 77 65 65 6e 20 62 erence between b
35e0: 69 6e 61 72 79 20 66 69 6c 65 73 22 2e 0a 2a 2f inary files"..*/
35f0: 0a 69 6e 74 20 2a 74 65 78 74 5f 64 69 66 66 28 .int *text_diff(
3600: 0a 20 20 42 6c 6f 62 20 2a 70 41 5f 42 6c 6f 62 . Blob *pA_Blob
3610: 2c 20 20 20 2f 2a 20 46 52 4f 4d 20 66 69 6c 65 , /* FROM file
3620: 20 2a 2f 0a 20 20 42 6c 6f 62 20 2a 70 42 5f 42 */. Blob *pB_B
3630: 6c 6f 62 2c 20 20 20 2f 2a 20 54 4f 20 66 69 6c lob, /* TO fil
3640: 65 20 2a 2f 0a 20 20 42 6c 6f 62 20 2a 70 4f 75 e */. Blob *pOu
3650: 74 2c 20 20 20 20 20 20 2f 2a 20 57 72 69 74 65 t, /* Write
3660: 20 75 6e 69 66 69 65 64 20 64 69 66 66 20 68 65 unified diff he
3670: 72 65 20 69 66 20 6e 6f 74 20 4e 55 4c 4c 20 2a re if not NULL *
3680: 2f 0a 20 20 69 6e 74 20 6e 43 6f 6e 74 65 78 74 /. int nContext
3690: 20 20 20 20 20 2f 2a 20 41 6d 6f 75 6e 74 20 6f /* Amount o
36a0: 66 20 63 6f 6e 74 65 78 74 20 74 6f 20 75 6e 69 f context to uni
36b0: 66 69 65 64 20 64 69 66 66 20 2a 2f 0a 29 7b 0a fied diff */.){.
36c0: 20 20 44 43 6f 6e 74 65 78 74 20 63 3b 0a 20 0a DContext c;. .
36d0: 20 20 2f 2a 20 50 72 65 70 61 72 65 20 74 68 65 /* Prepare the
36e0: 20 69 6e 70 75 74 20 66 69 6c 65 73 20 2a 2f 0a input files */.
36f0: 20 20 6d 65 6d 73 65 74 28 26 63 2c 20 30 2c 20 memset(&c, 0,
3700: 73 69 7a 65 6f 66 28 63 29 29 3b 0a 20 20 63 2e sizeof(c));. c.
3710: 61 46 72 6f 6d 20 3d 20 62 72 65 61 6b 5f 69 6e aFrom = break_in
3720: 74 6f 5f 6c 69 6e 65 73 28 62 6c 6f 62 5f 73 74 to_lines(blob_st
3730: 72 28 70 41 5f 42 6c 6f 62 29 2c 20 26 63 2e 6e r(pA_Blob), &c.n
3740: 46 72 6f 6d 29 3b 0a 20 20 63 2e 61 54 6f 20 3d From);. c.aTo =
3750: 20 62 72 65 61 6b 5f 69 6e 74 6f 5f 6c 69 6e 65 break_into_line
3760: 73 28 62 6c 6f 62 5f 73 74 72 28 70 42 5f 42 6c s(blob_str(pB_Bl
3770: 6f 62 29 2c 20 26 63 2e 6e 54 6f 29 3b 0a 20 20 ob), &c.nTo);.
3780: 69 66 28 20 63 2e 61 46 72 6f 6d 3d 3d 30 20 7c if( c.aFrom==0 |
3790: 7c 20 63 2e 61 54 6f 3d 3d 30 20 29 7b 0a 20 20 | c.aTo==0 ){.
37a0: 20 20 66 72 65 65 28 63 2e 61 46 72 6f 6d 29 3b free(c.aFrom);
37b0: 0a 20 20 20 20 66 72 65 65 28 63 2e 61 54 6f 29 . free(c.aTo)
37c0: 3b 0a 20 20 20 20 69 66 28 20 70 4f 75 74 20 29 ;. if( pOut )
37d0: 7b 0a 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 70 {. blob_app
37e0: 65 6e 64 66 28 70 4f 75 74 2c 20 22 63 61 6e 6e endf(pOut, "cann
37f0: 6f 74 20 63 6f 6d 70 75 74 65 20 64 69 66 66 65 ot compute diffe
3800: 72 65 6e 63 65 20 62 65 74 77 65 65 6e 20 62 69 rence between bi
3810: 6e 61 72 79 20 66 69 6c 65 73 5c 6e 22 29 3b 0a nary files\n");.
3820: 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e }. return
3830: 20 30 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 43 6f 0;. }.. /* Co
3840: 6d 70 75 74 65 20 74 68 65 20 64 69 66 66 65 72 mpute the differ
3850: 65 6e 63 65 20 2a 2f 0a 20 20 64 69 66 66 5f 61 ence */. diff_a
3860: 6c 6c 28 26 63 29 3b 0a 0a 20 20 69 66 28 20 70 ll(&c);.. if( p
3870: 4f 75 74 20 29 7b 0a 20 20 20 20 2f 2a 20 43 6f Out ){. /* Co
3880: 6d 70 75 74 65 20 61 20 63 6f 6e 74 65 78 74 20 mpute a context
3890: 64 69 66 66 20 69 66 20 72 65 71 75 65 73 74 65 diff if requeste
38a0: 64 20 2a 2f 0a 20 20 20 20 63 6f 6e 74 65 78 74 d */. context
38b0: 44 69 66 66 28 26 63 2c 20 70 4f 75 74 2c 20 6e Diff(&c, pOut, n
38c0: 43 6f 6e 74 65 78 74 29 3b 0a 20 20 20 20 66 72 Context);. fr
38d0: 65 65 28 63 2e 61 46 72 6f 6d 29 3b 0a 20 20 20 ee(c.aFrom);.
38e0: 20 66 72 65 65 28 63 2e 61 54 6f 29 3b 0a 20 20 free(c.aTo);.
38f0: 20 20 66 72 65 65 28 63 2e 61 45 64 69 74 29 3b free(c.aEdit);
3900: 0a 20 20 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 . return 0;.
3910: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2f 2a 20 49 }else{. /* I
3920: 66 20 61 20 63 6f 6e 74 65 78 74 20 64 69 66 66 f a context diff
3930: 20 69 73 20 6e 6f 74 20 72 65 71 75 65 73 74 65 is not requeste
3940: 64 2c 20 74 68 65 6e 20 72 65 74 75 72 6e 20 74 d, then return t
3950: 68 65 0a 20 20 20 20 2a 2a 20 61 72 72 61 79 20 he. ** array
3960: 6f 66 20 43 4f 50 59 2f 44 45 4c 45 54 45 2f 49 of COPY/DELETE/I
3970: 4e 53 45 52 54 20 74 72 69 70 6c 65 73 2e 0a 20 NSERT triples..
3980: 20 20 20 2a 2f 0a 20 20 20 20 66 72 65 65 28 63 */. free(c
3990: 2e 61 46 72 6f 6d 29 3b 0a 20 20 20 20 66 72 65 .aFrom);. fre
39a0: 65 28 63 2e 61 54 6f 29 3b 0a 20 20 20 20 72 65 e(c.aTo);. re
39b0: 74 75 72 6e 20 63 2e 61 45 64 69 74 3b 0a 20 20 turn c.aEdit;.
39c0: 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 4f 4d 4d 41 }.}../*.** COMMA
39d0: 4e 44 3a 20 74 65 73 74 2d 72 61 77 64 69 66 66 ND: test-rawdiff
39e0: 0a 2a 2f 0a 76 6f 69 64 20 74 65 73 74 5f 72 61 .*/.void test_ra
39f0: 77 64 69 66 66 5f 63 6d 64 28 76 6f 69 64 29 7b wdiff_cmd(void){
3a00: 0a 20 20 42 6c 6f 62 20 61 2c 20 62 3b 0a 20 20 . Blob a, b;.
3a10: 69 6e 74 20 72 3b 0a 20 20 69 6e 74 20 69 3b 0a int r;. int i;.
3a20: 20 20 69 6e 74 20 2a 52 3b 0a 20 20 69 66 28 20 int *R;. if(
3a30: 67 2e 61 72 67 63 3c 34 20 29 20 75 73 61 67 65 g.argc<4 ) usage
3a40: 28 22 46 49 4c 45 31 20 46 49 4c 45 32 20 2e 2e ("FILE1 FILE2 ..
3a50: 2e 22 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 61 64 .");. blob_read
3a60: 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 61 2c 20 67 _from_file(&a, g
3a70: 2e 61 72 67 76 5b 32 5d 29 3b 0a 20 20 66 6f 72 .argv[2]);. for
3a80: 28 69 3d 33 3b 20 69 3c 67 2e 61 72 67 63 3b 20 (i=3; i<g.argc;
3a90: 69 2b 2b 29 7b 0a 20 20 20 20 69 66 28 20 69 3e i++){. if( i>
3aa0: 33 20 29 20 70 72 69 6e 74 66 28 22 2d 2d 2d 2d 3 ) printf("----
3ab0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3ac0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 5c 6e 22 29 3b -----------\n");
3ad0: 0a 20 20 20 20 62 6c 6f 62 5f 72 65 61 64 5f 66 . blob_read_f
3ae0: 72 6f 6d 5f 66 69 6c 65 28 26 62 2c 20 67 2e 61 rom_file(&b, g.a
3af0: 72 67 76 5b 69 5d 29 3b 0a 20 20 20 20 52 20 3d rgv[i]);. R =
3b00: 20 74 65 78 74 5f 64 69 66 66 28 26 61 2c 20 26 text_diff(&a, &
3b10: 62 2c 20 30 2c 20 30 29 3b 0a 20 20 20 20 66 6f b, 0, 0);. fo
3b20: 72 28 72 3d 30 3b 20 52 5b 72 5d 20 7c 7c 20 52 r(r=0; R[r] || R
3b30: 5b 72 2b 31 5d 20 7c 7c 20 52 5b 72 2b 32 5d 3b [r+1] || R[r+2];
3b40: 20 72 20 2b 3d 20 33 29 7b 0a 20 20 20 20 20 20 r += 3){.
3b50: 70 72 69 6e 74 66 28 22 20 63 6f 70 79 20 25 34 printf(" copy %4
3b60: 64 20 20 64 65 6c 65 74 65 20 25 34 64 20 20 69 d delete %4d i
3b70: 6e 73 65 72 74 20 25 34 64 5c 6e 22 2c 20 52 5b nsert %4d\n", R[
3b80: 72 5d 2c 20 52 5b 72 2b 31 5d 2c 20 52 5b 72 2b r], R[r+1], R[r+
3b90: 32 5d 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 2f 2]);. }. /
3ba0: 2a 20 66 72 65 65 28 52 29 3b 20 2a 2f 0a 20 20 * free(R); */.
3bb0: 20 20 62 6c 6f 62 5f 72 65 73 65 74 28 26 62 29 blob_reset(&b)
3bc0: 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 ;. }.}../*.** C
3bd0: 4f 4d 4d 41 4e 44 3a 20 74 65 73 74 2d 75 64 69 OMMAND: test-udi
3be0: 66 66 0a 2a 2f 0a 76 6f 69 64 20 74 65 73 74 5f ff.*/.void test_
3bf0: 75 64 69 66 66 5f 63 6d 64 28 76 6f 69 64 29 7b udiff_cmd(void){
3c00: 0a 20 20 42 6c 6f 62 20 61 2c 20 62 2c 20 6f 75 . Blob a, b, ou
3c10: 74 3b 0a 20 20 69 66 28 20 67 2e 61 72 67 63 21 t;. if( g.argc!
3c20: 3d 34 20 29 20 75 73 61 67 65 28 22 46 49 4c 45 =4 ) usage("FILE
3c30: 31 20 46 49 4c 45 32 22 29 3b 0a 20 20 62 6c 6f 1 FILE2");. blo
3c40: 62 5f 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 b_read_from_file
3c50: 28 26 61 2c 20 67 2e 61 72 67 76 5b 32 5d 29 3b (&a, g.argv[2]);
3c60: 0a 20 20 62 6c 6f 62 5f 72 65 61 64 5f 66 72 6f . blob_read_fro
3c70: 6d 5f 66 69 6c 65 28 26 62 2c 20 67 2e 61 72 67 m_file(&b, g.arg
3c80: 76 5b 33 5d 29 3b 0a 20 20 62 6c 6f 62 5f 7a 65 v[3]);. blob_ze
3c90: 72 6f 28 26 6f 75 74 29 3b 0a 20 20 74 65 78 74 ro(&out);. text
3ca0: 5f 64 69 66 66 28 26 61 2c 20 26 62 2c 20 26 6f _diff(&a, &b, &o
3cb0: 75 74 2c 20 33 29 3b 0a 20 20 62 6c 6f 62 5f 77 ut, 3);. blob_w
3cc0: 72 69 74 65 5f 74 6f 5f 66 69 6c 65 28 26 6f 75 rite_to_file(&ou
3cd0: 74 2c 20 22 2d 22 29 3b 0a 7d 0a t, "-");.}.