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 0a 20 20 69 6e 74 20 69 53 31 xt *p,. int iS1
1f80: 2c 20 69 6e 74 20 69 45 31 2c 0a 20 20 69 6e 74 , int iE1,. int
1f90: 20 69 53 32 2c 20 69 6e 74 20 69 45 32 2c 0a 20 iS2, int iE2,.
1fa0: 20 69 6e 74 20 2a 70 69 53 58 2c 20 69 6e 74 20 int *piSX, int
1fb0: 2a 70 69 45 58 2c 0a 20 20 69 6e 74 20 2a 70 69 *piEX,. int *pi
1fc0: 53 59 2c 20 69 6e 74 20 2a 70 69 45 59 0a 29 7b SY, int *piEY.){
1fd0: 0a 20 20 69 6e 74 20 62 65 73 74 53 63 6f 72 65 . int bestScore
1fe0: 20 3d 20 2d 31 30 30 30 30 30 30 30 30 30 3b 0a = -1000000000;.
1ff0: 20 20 69 6e 74 20 69 2c 20 6a 3b 0a 20 20 69 6e int i, j;. in
2000: 74 20 69 53 58 2c 20 69 53 59 2c 20 69 45 58 2c t iSX, iSY, iEX,
2010: 20 69 45 59 3b 0a 20 20 69 6e 74 20 73 63 6f 72 iEY;. int scor
2020: 65 2c 20 73 6b 65 77 2c 20 64 69 73 74 2c 20 6d e, skew, dist, m
2030: 69 64 3b 0a 0a 20 20 2a 70 69 53 58 20 3d 20 69 id;.. *piSX = i
2040: 53 31 3b 0a 20 20 2a 70 69 45 58 20 3d 20 69 53 S1;. *piEX = iS
2050: 31 3b 0a 20 20 2a 70 69 53 59 20 3d 20 69 53 32 1;. *piSY = iS2
2060: 3b 0a 20 20 2a 70 69 45 59 20 3d 20 69 53 32 3b ;. *piEY = iS2;
2070: 0a 20 20 6d 69 64 20 3d 20 28 69 45 31 20 2b 20 . mid = (iE1 +
2080: 69 53 31 29 2f 32 3b 0a 20 20 66 6f 72 28 69 3d iS1)/2;. for(i=
2090: 69 53 31 3b 20 69 3c 69 45 31 3b 20 69 2b 2b 29 iS1; i<iE1; i++)
20a0: 7b 0a 20 20 20 20 69 6e 74 20 6c 69 6d 69 74 20 {. int limit
20b0: 3d 20 30 3b 0a 20 20 20 20 6a 20 3d 20 70 2d 3e = 0;. j = p->
20c0: 61 54 6f 5b 70 2d 3e 61 46 72 6f 6d 5b 69 5d 2e aTo[p->aFrom[i].
20d0: 68 20 25 20 70 2d 3e 6e 54 6f 5d 2e 69 48 61 73 h % p->nTo].iHas
20e0: 68 3b 0a 20 20 20 20 77 68 69 6c 65 28 20 6a 3e h;. while( j>
20f0: 30 20 0a 20 20 20 20 20 20 26 26 20 28 6a 2d 31 0 . && (j-1
2100: 3c 69 53 32 20 7c 7c 20 6a 3e 3d 69 45 32 20 7c <iS2 || j>=iE2 |
2110: 7c 20 21 73 61 6d 65 5f 64 6c 69 6e 65 28 26 70 | !same_dline(&p
2120: 2d 3e 61 46 72 6f 6d 5b 69 5d 2c 20 26 70 2d 3e ->aFrom[i], &p->
2130: 61 54 6f 5b 6a 2d 31 5d 29 29 0a 20 20 20 20 29 aTo[j-1])). )
2140: 7b 0a 20 20 20 20 20 20 69 66 28 20 6c 69 6d 69 {. if( limi
2150: 74 2b 2b 20 3e 20 31 30 20 29 7b 0a 20 20 20 20 t++ > 10 ){.
2160: 20 20 20 20 6a 20 3d 20 30 3b 0a 20 20 20 20 20 j = 0;.
2170: 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 break;.
2180: 7d 0a 20 20 20 20 20 20 6a 20 3d 20 70 2d 3e 61 }. j = p->a
2190: 54 6f 5b 6a 2d 31 5d 2e 69 4e 65 78 74 3b 0a 20 To[j-1].iNext;.
21a0: 20 20 20 7d 0a 20 20 20 20 69 66 28 20 6a 3d 3d }. if( j==
21b0: 30 20 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 20 20 0 ) continue;.
21c0: 20 20 69 53 58 20 3d 20 69 3b 0a 20 20 20 20 69 iSX = i;. i
21d0: 53 59 20 3d 20 6a 2d 31 3b 0a 20 20 20 20 77 68 SY = j-1;. wh
21e0: 69 6c 65 28 20 69 53 58 3e 69 53 31 20 26 26 20 ile( iSX>iS1 &&
21f0: 69 53 59 3e 69 53 32 20 26 26 20 73 61 6d 65 5f iSY>iS2 && same_
2200: 64 6c 69 6e 65 28 26 70 2d 3e 61 46 72 6f 6d 5b dline(&p->aFrom[
2210: 69 53 58 2d 31 5d 2c 26 70 2d 3e 61 54 6f 5b 69 iSX-1],&p->aTo[i
2220: 53 59 2d 31 5d 29 20 29 7b 0a 20 20 20 20 20 20 SY-1]) ){.
2230: 69 53 58 2d 2d 3b 0a 20 20 20 20 20 20 69 53 59 iSX--;. iSY
2240: 2d 2d 3b 0a 20 20 20 20 7d 0a 20 20 20 20 69 45 --;. }. iE
2250: 58 20 3d 20 69 2b 31 3b 0a 20 20 20 20 69 45 59 X = i+1;. iEY
2260: 20 3d 20 6a 3b 0a 20 20 20 20 77 68 69 6c 65 28 = j;. while(
2270: 20 69 45 58 3c 69 45 31 20 26 26 20 69 45 59 3c iEX<iE1 && iEY<
2280: 69 45 32 20 26 26 20 73 61 6d 65 5f 64 6c 69 6e iE2 && same_dlin
2290: 65 28 26 70 2d 3e 61 46 72 6f 6d 5b 69 45 58 5d e(&p->aFrom[iEX]
22a0: 2c 26 70 2d 3e 61 54 6f 5b 69 45 59 5d 29 20 29 ,&p->aTo[iEY]) )
22b0: 7b 0a 20 20 20 20 20 20 69 45 58 2b 2b 3b 0a 20 {. iEX++;.
22c0: 20 20 20 20 20 69 45 59 2b 2b 3b 0a 20 20 20 20 iEY++;.
22d0: 7d 0a 20 20 20 20 73 6b 65 77 20 3d 20 28 69 53 }. skew = (iS
22e0: 58 2d 69 53 31 29 20 2d 20 28 69 53 59 2d 69 53 X-iS1) - (iSY-iS
22f0: 32 29 3b 0a 20 20 20 20 69 66 28 20 73 6b 65 77 2);. if( skew
2300: 3c 30 20 29 20 73 6b 65 77 20 3d 20 2d 73 6b 65 <0 ) skew = -ske
2310: 77 3b 0a 20 20 20 20 64 69 73 74 20 3d 20 28 69 w;. dist = (i
2320: 53 58 2b 69 45 58 29 2f 32 20 2d 20 6d 69 64 3b SX+iEX)/2 - mid;
2330: 0a 20 20 20 20 69 66 28 20 64 69 73 74 3c 30 20 . if( dist<0
2340: 29 20 64 69 73 74 20 3d 20 2d 64 69 73 74 3b 0a ) dist = -dist;.
2350: 20 20 20 20 73 63 6f 72 65 20 3d 20 28 69 45 58 score = (iEX
2360: 20 2d 20 69 53 58 29 20 2d 20 30 2e 30 35 2a 73 - iSX) - 0.05*s
2370: 6b 65 77 20 2d 20 30 2e 30 35 2a 64 69 73 74 3b kew - 0.05*dist;
2380: 0a 20 20 20 20 69 66 28 20 73 63 6f 72 65 3e 62 . if( score>b
2390: 65 73 74 53 63 6f 72 65 20 29 7b 0a 20 20 20 20 estScore ){.
23a0: 20 20 62 65 73 74 53 63 6f 72 65 20 3d 20 73 63 bestScore = sc
23b0: 6f 72 65 3b 0a 20 20 20 20 20 20 2a 70 69 53 58 ore;. *piSX
23c0: 20 3d 20 69 53 58 3b 0a 20 20 20 20 20 20 2a 70 = iSX;. *p
23d0: 69 53 59 20 3d 20 69 53 59 3b 0a 20 20 20 20 20 iSY = iSY;.
23e0: 20 2a 70 69 45 58 20 3d 20 69 45 58 3b 0a 20 20 *piEX = iEX;.
23f0: 20 20 20 20 2a 70 69 45 59 20 3d 20 69 45 59 3b *piEY = iEY;
2400: 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 2f 2a 20 . }. }. /*
2410: 70 72 69 6e 74 66 28 22 4c 43 53 28 25 64 2e 2e printf("LCS(%d..
2420: 25 64 2f 25 64 2e 2e 25 64 29 20 3d 20 25 64 2e %d/%d..%d) = %d.
2430: 2e 25 64 2f 25 64 2e 2e 25 64 5c 6e 22 2c 20 0a .%d/%d..%d\n", .
2440: 20 20 20 20 20 69 53 31 2c 20 69 45 31 2c 20 69 iS1, iE1, i
2450: 53 32 2c 20 69 45 32 2c 20 2a 70 69 53 58 2c 20 S2, iE2, *piSX,
2460: 2a 70 69 45 58 2c 20 2a 70 69 53 59 2c 20 2a 70 *piEX, *piSY, *p
2470: 69 45 59 29 3b 20 20 2a 2f 0a 7d 0a 0a 2f 2a 0a iEY); */.}../*.
2480: 2a 2a 20 44 6f 20 61 20 73 69 6e 67 6c 65 20 73 ** Do a single s
2490: 74 65 70 20 69 6e 20 74 68 65 20 64 69 66 66 65 tep in the diffe
24a0: 72 65 6e 63 65 2e 20 20 43 6f 6d 70 75 74 65 20 rence. Compute
24b0: 61 20 73 65 71 75 65 6e 63 65 20 6f 66 0a 2a 2a a sequence of.**
24c0: 20 63 6f 70 79 2f 64 65 6c 65 74 65 2f 69 6e 73 copy/delete/ins
24d0: 65 72 74 20 73 74 65 70 73 20 74 68 61 74 20 77 ert steps that w
24e0: 69 6c 6c 20 63 6f 6e 76 65 72 74 20 6c 69 6e 65 ill convert line
24f0: 73 20 69 53 31 20 74 68 72 6f 75 67 68 20 69 45 s iS1 through iE
2500: 31 2d 31 20 6f 66 0a 2a 2a 20 74 68 65 20 69 6e 1-1 of.** the in
2510: 70 75 74 20 69 6e 74 6f 20 6c 69 6e 65 73 20 69 put into lines i
2520: 53 32 20 74 68 72 6f 75 67 68 20 69 45 32 2d 31 S2 through iE2-1
2530: 20 6f 66 20 74 68 65 20 6f 75 74 70 75 74 20 61 of the output a
2540: 6e 64 20 77 72 69 74 65 0a 2a 2a 20 74 68 61 74 nd write.** that
2550: 20 73 65 71 75 65 6e 63 65 20 69 6e 74 6f 20 74 sequence into t
2560: 68 65 20 64 69 66 66 65 72 65 6e 63 65 20 63 6f he difference co
2570: 6e 74 65 78 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 ntext..*/.static
2580: 20 76 6f 69 64 20 64 69 66 66 5f 73 74 65 70 28 void diff_step(
2590: 44 43 6f 6e 74 65 78 74 20 2a 70 2c 20 69 6e 74 DContext *p, int
25a0: 20 69 53 31 2c 20 69 6e 74 20 69 45 31 2c 20 69 iS1, int iE1, i
25b0: 6e 74 20 69 53 32 2c 20 69 6e 74 20 69 45 32 29 nt iS2, int iE2)
25c0: 7b 0a 20 20 69 6e 74 20 69 53 58 2c 20 69 45 58 {. int iSX, iEX
25d0: 2c 20 69 53 59 2c 20 69 45 59 3b 0a 0a 20 20 69 , iSY, iEY;.. i
25e0: 66 28 20 69 45 31 3c 3d 69 53 31 20 29 7b 0a 20 f( iE1<=iS1 ){.
25f0: 20 20 20 69 66 28 20 69 45 32 3e 69 53 32 20 29 if( iE2>iS2 )
2600: 7b 0a 20 20 20 20 20 20 61 70 70 65 6e 64 54 72 {. appendTr
2610: 69 70 6c 65 28 70 2c 20 30 2c 20 30 2c 20 69 45 iple(p, 0, 0, iE
2620: 32 2d 69 53 32 29 3b 0a 20 20 20 20 7d 0a 20 20 2-iS2);. }.
2630: 20 20 72 65 74 75 72 6e 3b 0a 20 20 7d 0a 20 20 return;. }.
2640: 69 66 28 20 69 45 32 3c 3d 69 53 32 20 29 7b 0a if( iE2<=iS2 ){.
2650: 20 20 20 20 61 70 70 65 6e 64 54 72 69 70 6c 65 appendTriple
2660: 28 70 2c 20 30 2c 20 69 45 31 2d 69 53 31 2c 20 (p, 0, iE1-iS1,
2670: 30 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 3b 0a 0);. return;.
2680: 20 20 7d 0a 0a 20 20 2f 2a 20 46 69 6e 64 20 74 }.. /* Find t
2690: 68 65 20 6c 6f 6e 67 65 73 74 20 6d 61 74 63 68 he longest match
26a0: 69 6e 67 20 73 65 67 6d 65 6e 74 20 62 65 74 77 ing segment betw
26b0: 65 65 6e 20 74 68 65 20 74 77 6f 20 73 65 71 75 een the two sequ
26c0: 65 6e 63 65 73 20 2a 2f 0a 20 20 6c 6f 6e 67 65 ences */. longe
26d0: 73 74 43 6f 6d 6d 6f 6e 53 65 71 75 65 6e 63 65 stCommonSequence
26e0: 28 70 2c 20 69 53 31 2c 20 69 45 31 2c 20 69 53 (p, iS1, iE1, iS
26f0: 32 2c 20 69 45 32 2c 20 26 69 53 58 2c 20 26 69 2, iE2, &iSX, &i
2700: 45 58 2c 20 26 69 53 59 2c 20 26 69 45 59 29 3b EX, &iSY, &iEY);
2710: 0a 0a 20 20 69 66 28 20 69 45 58 3e 69 53 58 20 .. if( iEX>iSX
2720: 29 7b 0a 20 20 20 20 2f 2a 20 52 65 63 75 72 73 ){. /* Recurs
2730: 69 76 65 6c 79 20 64 69 66 66 20 65 69 74 68 65 ively diff eithe
2740: 72 20 73 69 64 65 20 6f 66 20 74 68 65 20 6d 61 r side of the ma
2750: 74 63 68 69 6e 67 20 73 65 67 6d 65 6e 74 20 2a tching segment *
2760: 2f 0a 20 20 20 20 64 69 66 66 5f 73 74 65 70 28 /. diff_step(
2770: 70 2c 20 69 53 31 2c 20 69 53 58 2c 20 69 53 32 p, iS1, iSX, iS2
2780: 2c 20 69 53 59 29 3b 0a 20 20 20 20 69 66 28 20 , iSY);. if(
2790: 69 45 58 3e 69 53 58 20 29 7b 0a 20 20 20 20 20 iEX>iSX ){.
27a0: 20 61 70 70 65 6e 64 54 72 69 70 6c 65 28 70 2c appendTriple(p,
27b0: 20 69 45 58 20 2d 20 69 53 58 2c 20 30 2c 20 30 iEX - iSX, 0, 0
27c0: 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 64 69 66 );. }. dif
27d0: 66 5f 73 74 65 70 28 70 2c 20 69 45 58 2c 20 69 f_step(p, iEX, i
27e0: 45 31 2c 20 69 45 59 2c 20 69 45 32 29 3b 0a 20 E1, iEY, iE2);.
27f0: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 61 70 70 65 }else{. appe
2800: 6e 64 54 72 69 70 6c 65 28 70 2c 20 30 2c 20 69 ndTriple(p, 0, i
2810: 45 31 2d 69 53 31 2c 20 69 45 32 2d 69 53 32 29 E1-iS1, iE2-iS2)
2820: 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 47 ;. }.}../*.** G
2830: 65 6e 65 72 61 74 65 20 61 20 72 65 70 6f 72 74 enerate a report
2840: 20 6f 66 20 74 68 65 20 64 69 66 66 65 72 65 6e of the differen
2850: 63 65 73 20 62 65 74 77 65 65 6e 20 66 69 6c 65 ces between file
2860: 73 20 70 41 20 61 6e 64 20 70 42 2e 0a 2a 2a 20 s pA and pB..**
2870: 49 66 20 70 4f 75 74 20 69 73 20 6e 6f 74 20 4e If pOut is not N
2880: 55 4c 4c 20 74 68 65 6e 20 61 20 75 6e 69 66 69 ULL then a unifi
2890: 65 64 20 64 69 66 66 20 69 73 20 61 70 70 65 6e ed diff is appen
28a0: 64 65 64 20 74 68 65 72 65 2e 20 20 49 74 0a 2a ded there. It.*
28b0: 2a 20 69 73 20 61 73 73 75 6d 65 64 20 74 68 61 * is assumed tha
28c0: 74 20 70 4f 75 74 20 68 61 73 20 61 6c 72 65 61 t pOut has alrea
28d0: 64 79 20 62 65 65 6e 20 69 6e 69 74 69 61 6c 69 dy been initiali
28e0: 7a 65 64 2e 20 20 49 66 20 70 4f 75 74 20 69 73 zed. If pOut is
28f0: 0a 2a 2a 20 4e 55 4c 4c 2c 20 74 68 65 6e 20 61 .** NULL, then a
2900: 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 6e 20 61 pointer to an a
2910: 72 72 61 79 20 6f 66 20 69 6e 74 65 67 65 72 73 rray of integers
2920: 20 69 73 20 72 65 74 75 72 6e 65 64 2e 20 20 0a is returned. .
2930: 2a 2a 20 54 68 65 20 69 6e 74 65 67 65 72 73 20 ** The integers
2940: 63 6f 6d 65 20 69 6e 20 74 72 69 70 6c 65 73 2e come in triples.
2950: 20 20 46 6f 72 20 65 61 63 68 20 74 72 69 70 6c For each tripl
2960: 65 2c 0a 2a 2a 20 74 68 65 20 65 6c 65 6d 65 6e e,.** the elemen
2970: 74 73 20 61 72 65 20 74 68 65 20 6e 75 6d 62 65 ts are the numbe
2980: 72 20 6f 66 20 6c 69 6e 65 73 20 63 6f 70 69 65 r of lines copie
2990: 64 2c 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 d, the number of
29a0: 0a 2a 2a 20 6c 69 6e 65 73 20 64 65 6c 65 74 65 .** lines delete
29b0: 64 2c 20 61 6e 64 20 74 68 65 20 6e 75 6d 62 65 d, and the numbe
29c0: 72 20 6f 66 20 6c 69 6e 65 73 20 69 6e 73 65 72 r of lines inser
29d0: 74 65 64 2e 20 20 54 68 65 20 76 65 63 74 6f 72 ted. The vector
29e0: 0a 2a 2a 20 69 73 20 74 65 72 6d 69 6e 61 74 65 .** is terminate
29f0: 64 20 62 79 20 61 20 74 72 69 70 6c 65 20 6f 66 d by a triple of
2a00: 20 61 6c 6c 20 7a 65 72 6f 73 2e 0a 2a 2a 0a 2a all zeros..**.*
2a10: 2a 20 54 68 69 73 20 64 69 66 66 20 75 74 69 6c * This diff util
2a20: 69 74 79 20 64 6f 65 73 20 6e 6f 74 20 77 6f 72 ity does not wor
2a30: 6b 20 6f 6e 20 62 69 6e 61 72 79 20 66 69 6c 65 k on binary file
2a40: 73 2e 20 20 49 66 20 61 20 62 69 6e 61 72 79 0a s. If a binary.
2a50: 2a 2a 20 66 69 6c 65 20 69 73 20 65 6e 63 6f 75 ** file is encou
2a60: 6e 74 65 72 65 64 2c 20 30 20 69 73 20 72 65 74 ntered, 0 is ret
2a70: 75 72 6e 65 64 20 61 6e 64 20 70 4f 75 74 20 69 urned and pOut i
2a80: 73 20 77 72 69 74 74 65 6e 20 77 69 74 68 0a 2a s written with.*
2a90: 2a 20 74 65 78 74 20 22 63 61 6e 6e 6f 74 20 63 * text "cannot c
2aa0: 6f 6d 70 75 74 65 20 64 69 66 66 65 72 65 6e 63 ompute differenc
2ab0: 65 20 62 65 74 77 65 65 6e 20 62 69 6e 61 72 79 e between binary
2ac0: 20 66 69 6c 65 73 22 2e 0a 2a 2f 0a 69 6e 74 20 files"..*/.int
2ad0: 2a 74 65 78 74 5f 64 69 66 66 28 0a 20 20 42 6c *text_diff(. Bl
2ae0: 6f 62 20 2a 70 41 5f 42 6c 6f 62 2c 20 20 20 2f ob *pA_Blob, /
2af0: 2a 20 46 52 4f 4d 20 66 69 6c 65 20 2a 2f 0a 20 * FROM file */.
2b00: 20 42 6c 6f 62 20 2a 70 42 5f 42 6c 6f 62 2c 20 Blob *pB_Blob,
2b10: 20 20 2f 2a 20 54 4f 20 66 69 6c 65 20 2a 2f 0a /* TO file */.
2b20: 20 20 42 6c 6f 62 20 2a 70 4f 75 74 2c 20 20 20 Blob *pOut,
2b30: 20 20 20 2f 2a 20 57 72 69 74 65 20 75 6e 69 66 /* Write unif
2b40: 69 65 64 20 64 69 66 66 20 68 65 72 65 20 69 66 ied diff here if
2b50: 20 6e 6f 74 20 4e 55 4c 4c 20 2a 2f 0a 20 20 69 not NULL */. i
2b60: 6e 74 20 6e 43 6f 6e 74 65 78 74 20 20 20 20 20 nt nContext
2b70: 2f 2a 20 41 6d 6f 75 6e 74 20 6f 66 20 63 6f 6e /* Amount of con
2b80: 74 65 78 74 20 74 6f 20 75 6e 69 66 69 65 64 20 text to unified
2b90: 64 69 66 66 20 2a 2f 0a 29 7b 0a 20 20 44 43 6f diff */.){. DCo
2ba0: 6e 74 65 78 74 20 63 3b 0a 20 20 69 6e 74 20 6d ntext c;. int m
2bb0: 6e 45 2c 20 69 53 2c 20 69 45 31 2c 20 69 45 32 nE, iS, iE1, iE2
2bc0: 3b 0a 0a 20 20 6d 65 6d 73 65 74 28 26 63 2c 20 ;.. memset(&c,
2bd0: 30 2c 20 73 69 7a 65 6f 66 28 63 29 29 3b 0a 20 0, sizeof(c));.
2be0: 20 63 2e 61 46 72 6f 6d 20 3d 20 62 72 65 61 6b c.aFrom = break
2bf0: 5f 69 6e 74 6f 5f 6c 69 6e 65 73 28 62 6c 6f 62 _into_lines(blob
2c00: 5f 73 74 72 28 70 41 5f 42 6c 6f 62 29 2c 20 26 _str(pA_Blob), &
2c10: 63 2e 6e 46 72 6f 6d 29 3b 0a 20 20 63 2e 61 54 c.nFrom);. c.aT
2c20: 6f 20 3d 20 62 72 65 61 6b 5f 69 6e 74 6f 5f 6c o = break_into_l
2c30: 69 6e 65 73 28 62 6c 6f 62 5f 73 74 72 28 70 42 ines(blob_str(pB
2c40: 5f 42 6c 6f 62 29 2c 20 26 63 2e 6e 54 6f 29 3b _Blob), &c.nTo);
2c50: 0a 20 20 69 66 28 20 63 2e 61 46 72 6f 6d 3d 3d . if( c.aFrom==
2c60: 30 20 7c 7c 20 63 2e 61 54 6f 3d 3d 30 20 29 7b 0 || c.aTo==0 ){
2c70: 0a 20 20 20 20 66 72 65 65 28 63 2e 61 46 72 6f . free(c.aFro
2c80: 6d 29 3b 0a 20 20 20 20 66 72 65 65 28 63 2e 61 m);. free(c.a
2c90: 54 6f 29 3b 0a 20 20 20 20 69 66 28 20 70 4f 75 To);. if( pOu
2ca0: 74 20 29 7b 0a 20 20 20 20 20 20 62 6c 6f 62 5f t ){. blob_
2cb0: 61 70 70 65 6e 64 66 28 70 4f 75 74 2c 20 22 63 appendf(pOut, "c
2cc0: 61 6e 6e 6f 74 20 63 6f 6d 70 75 74 65 20 64 69 annot compute di
2cd0: 66 66 65 72 65 6e 63 65 20 62 65 74 77 65 65 6e fference between
2ce0: 20 62 69 6e 61 72 79 20 66 69 6c 65 73 5c 6e 22 binary files\n"
2cf0: 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 74 );. }. ret
2d00: 75 72 6e 20 30 3b 0a 20 20 7d 0a 0a 20 20 2f 2a urn 0;. }.. /*
2d10: 20 43 61 72 76 65 20 6f 66 66 20 74 68 65 20 63 Carve off the c
2d20: 6f 6d 6d 6f 6e 20 68 65 61 64 65 72 20 61 6e 64 ommon header and
2d30: 20 66 6f 6f 74 65 72 20 2a 2f 0a 20 20 69 45 31 footer */. iE1
2d40: 20 3d 20 63 2e 6e 46 72 6f 6d 3b 0a 20 20 69 45 = c.nFrom;. iE
2d50: 32 20 3d 20 63 2e 6e 54 6f 3b 0a 20 20 77 68 69 2 = c.nTo;. whi
2d60: 6c 65 28 20 69 45 31 3e 30 20 26 26 20 69 45 32 le( iE1>0 && iE2
2d70: 3e 30 20 26 26 20 73 61 6d 65 5f 64 6c 69 6e 65 >0 && same_dline
2d80: 28 26 63 2e 61 46 72 6f 6d 5b 69 45 31 2d 31 5d (&c.aFrom[iE1-1]
2d90: 2c 20 26 63 2e 61 54 6f 5b 69 45 32 2d 31 5d 29 , &c.aTo[iE2-1])
2da0: 20 29 7b 0a 20 20 20 20 69 45 31 2d 2d 3b 0a 20 ){. iE1--;.
2db0: 20 20 20 69 45 32 2d 2d 3b 0a 20 20 7d 0a 20 20 iE2--;. }.
2dc0: 6d 6e 45 20 3d 20 69 45 31 3c 69 45 32 20 3f 20 mnE = iE1<iE2 ?
2dd0: 69 45 31 20 3a 20 69 45 32 3b 0a 20 20 66 6f 72 iE1 : iE2;. for
2de0: 28 69 53 3d 30 3b 20 69 53 3c 6d 6e 45 20 26 26 (iS=0; iS<mnE &&
2df0: 20 73 61 6d 65 5f 64 6c 69 6e 65 28 26 63 2e 61 same_dline(&c.a
2e00: 46 72 6f 6d 5b 69 53 5d 2c 26 63 2e 61 54 6f 5b From[iS],&c.aTo[
2e10: 69 53 5d 29 3b 20 69 53 2b 2b 29 7b 7d 0a 0a 20 iS]); iS++){}..
2e20: 20 2f 2a 20 64 6f 20 74 68 65 20 64 69 66 66 65 /* do the diffe
2e30: 72 65 6e 63 65 20 2a 2f 0a 20 20 69 66 28 20 69 rence */. if( i
2e40: 53 3e 30 20 29 7b 0a 20 20 20 20 61 70 70 65 6e S>0 ){. appen
2e50: 64 54 72 69 70 6c 65 28 26 63 2c 20 69 53 2c 20 dTriple(&c, iS,
2e60: 30 2c 20 30 29 3b 0a 20 20 7d 0a 20 20 64 69 66 0, 0);. }. dif
2e70: 66 5f 73 74 65 70 28 26 63 2c 20 69 53 2c 20 69 f_step(&c, iS, i
2e80: 45 31 2c 20 69 53 2c 20 69 45 32 29 3b 0a 20 20 E1, iS, iE2);.
2e90: 69 66 28 20 69 45 31 3c 63 2e 6e 46 72 6f 6d 20 if( iE1<c.nFrom
2ea0: 29 7b 0a 20 20 20 20 61 70 70 65 6e 64 54 72 69 ){. appendTri
2eb0: 70 6c 65 28 26 63 2c 20 63 2e 6e 46 72 6f 6d 20 ple(&c, c.nFrom
2ec0: 2d 20 69 45 31 2c 20 30 2c 20 30 29 3b 0a 20 20 - iE1, 0, 0);.
2ed0: 7d 0a 0a 20 20 65 78 70 61 6e 64 45 64 69 74 28 }.. expandEdit(
2ee0: 26 63 2c 20 63 2e 6e 45 64 69 74 2b 33 29 3b 0a &c, c.nEdit+3);.
2ef0: 20 20 69 66 28 20 63 2e 61 45 64 69 74 20 29 7b if( c.aEdit ){
2f00: 0a 20 20 20 20 63 2e 61 45 64 69 74 5b 63 2e 6e . c.aEdit[c.n
2f10: 45 64 69 74 2b 2b 5d 20 3d 20 30 3b 0a 20 20 20 Edit++] = 0;.
2f20: 20 63 2e 61 45 64 69 74 5b 63 2e 6e 45 64 69 74 c.aEdit[c.nEdit
2f30: 2b 2b 5d 20 3d 20 30 3b 0a 20 20 20 20 63 2e 61 ++] = 0;. c.a
2f40: 45 64 69 74 5b 63 2e 6e 45 64 69 74 2b 2b 5d 20 Edit[c.nEdit++]
2f50: 3d 20 30 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20 = 0;. }.. if(
2f60: 70 4f 75 74 20 29 7b 0a 20 20 20 20 2f 2a 20 43 pOut ){. /* C
2f70: 6f 6d 70 75 74 65 20 61 20 63 6f 6e 74 65 78 74 ompute a context
2f80: 20 64 69 66 66 20 69 66 20 72 65 71 75 65 73 74 diff if request
2f90: 65 64 20 2a 2f 0a 20 20 20 20 63 6f 6e 74 65 78 ed */. contex
2fa0: 74 44 69 66 66 28 26 63 2c 20 70 4f 75 74 2c 20 tDiff(&c, pOut,
2fb0: 6e 43 6f 6e 74 65 78 74 29 3b 0a 20 20 20 20 66 nContext);. f
2fc0: 72 65 65 28 63 2e 61 46 72 6f 6d 29 3b 0a 20 20 ree(c.aFrom);.
2fd0: 20 20 66 72 65 65 28 63 2e 61 54 6f 29 3b 0a 20 free(c.aTo);.
2fe0: 20 20 20 66 72 65 65 28 63 2e 61 45 64 69 74 29 free(c.aEdit)
2ff0: 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 30 3b 0a ;. return 0;.
3000: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2f 2a 20 }else{. /*
3010: 49 66 20 61 20 63 6f 6e 74 65 78 74 20 64 69 66 If a context dif
3020: 66 20 69 73 20 6e 6f 74 20 72 65 71 75 65 73 74 f is not request
3030: 65 64 2c 20 74 68 65 6e 20 72 65 74 75 72 6e 20 ed, then return
3040: 74 68 65 0a 20 20 20 20 2a 2a 20 61 72 72 61 79 the. ** array
3050: 20 6f 66 20 43 4f 50 59 2f 44 45 4c 45 54 45 2f of COPY/DELETE/
3060: 49 4e 53 45 52 54 20 74 72 69 70 6c 65 73 20 61 INSERT triples a
3070: 66 74 65 72 20 74 65 72 6d 69 6e 61 74 69 6e 67 fter terminating
3080: 20 74 68 65 0a 20 20 20 20 2a 2a 20 61 72 72 61 the. ** arra
3090: 79 20 77 69 74 68 20 61 20 74 72 69 70 6c 65 20 y with a triple
30a0: 6f 66 20 61 6c 6c 20 7a 65 72 6f 73 2e 0a 20 20 of all zeros..
30b0: 20 20 2a 2f 0a 20 20 20 20 66 72 65 65 28 63 2e */. free(c.
30c0: 61 46 72 6f 6d 29 3b 0a 20 20 20 20 66 72 65 65 aFrom);. free
30d0: 28 63 2e 61 54 6f 29 3b 0a 20 20 20 20 72 65 74 (c.aTo);. ret
30e0: 75 72 6e 20 63 2e 61 45 64 69 74 3b 0a 20 20 7d urn c.aEdit;. }
30f0: 0a 7d 0a 0a 23 69 66 20 30 20 20 2f 2a 2a 2a 2a .}..#if 0 /****
3100: 2a 2a 2a 2a 2a 2a 20 44 69 73 61 62 6c 65 64 20 ****** Disabled
3110: 61 6e 64 20 72 65 70 6c 61 63 65 64 20 62 79 20 and replaced by
3120: 63 6f 64 65 20 61 62 6f 76 65 20 2a 2a 2a 2a 2a code above *****
3130: 2a 2a 2a 2a 2a 2a 2a 2f 0a 0a 2f 2a 0a 2a 2a 20 *******/../*.**
3140: 47 65 6e 65 72 61 74 65 20 61 20 72 65 70 6f 72 Generate a repor
3150: 74 20 6f 66 20 74 68 65 20 64 69 66 66 65 72 65 t of the differe
3160: 6e 63 65 73 20 62 65 74 77 65 65 6e 20 66 69 6c nces between fil
3170: 65 73 20 70 41 20 61 6e 64 20 70 42 2e 0a 2a 2a es pA and pB..**
3180: 20 49 66 20 70 4f 75 74 20 69 73 20 6e 6f 74 20 If pOut is not
3190: 4e 55 4c 4c 20 74 68 65 6e 20 61 20 75 6e 69 66 NULL then a unif
31a0: 69 65 64 20 64 69 66 66 20 69 73 20 61 70 70 65 ied diff is appe
31b0: 6e 64 65 64 20 74 68 65 72 65 2e 20 20 49 74 0a nded there. It.
31c0: 2a 2a 20 69 73 20 61 73 73 75 6d 65 64 20 74 68 ** is assumed th
31d0: 61 74 20 70 4f 75 74 20 68 61 73 20 61 6c 72 65 at pOut has alre
31e0: 61 64 79 20 62 65 65 6e 20 69 6e 69 74 69 61 6c ady been initial
31f0: 69 7a 65 64 2e 20 20 49 66 20 70 4f 75 74 20 69 ized. If pOut i
3200: 73 0a 2a 2a 20 4e 55 4c 4c 2c 20 74 68 65 6e 20 s.** NULL, then
3210: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 6e 20 a pointer to an
3220: 61 72 72 61 79 20 6f 66 20 69 6e 74 65 67 65 72 array of integer
3230: 73 20 69 73 20 72 65 74 75 72 6e 65 64 2e 20 20 s is returned.
3240: 0a 2a 2a 20 54 68 65 20 69 6e 74 65 67 65 72 73 .** The integers
3250: 20 63 6f 6d 65 20 69 6e 20 74 72 69 70 6c 65 73 come in triples
3260: 2e 20 20 46 6f 72 20 65 61 63 68 20 74 72 69 70 . For each trip
3270: 6c 65 2c 0a 2a 2a 20 74 68 65 20 65 6c 65 6d 65 le,.** the eleme
3280: 6e 74 73 20 61 72 65 20 74 68 65 20 6e 75 6d 62 nts are the numb
3290: 65 72 20 6f 66 20 6c 69 6e 65 73 20 63 6f 70 69 er of lines copi
32a0: 65 64 2c 20 74 68 65 20 6e 75 6d 62 65 72 20 6f ed, the number o
32b0: 66 0a 2a 2a 20 6c 69 6e 65 73 20 64 65 6c 65 74 f.** lines delet
32c0: 65 64 2c 20 61 6e 64 20 74 68 65 20 6e 75 6d 62 ed, and the numb
32d0: 65 72 20 6f 66 20 6c 69 6e 65 73 20 69 6e 73 65 er of lines inse
32e0: 72 74 65 64 2e 20 20 54 68 65 20 76 65 63 74 6f rted. The vecto
32f0: 72 0a 2a 2a 20 69 73 20 74 65 72 6d 69 6e 61 74 r.** is terminat
3300: 65 64 20 62 79 20 61 20 74 72 69 70 6c 65 20 6f ed by a triple o
3310: 66 20 61 6c 6c 20 7a 65 72 6f 73 2e 0a 2a 2a 0a f all zeros..**.
3320: 2a 2a 20 54 68 69 73 20 64 69 66 66 20 75 74 69 ** This diff uti
3330: 6c 69 74 79 20 64 6f 65 73 20 6e 6f 74 20 77 6f lity does not wo
3340: 72 6b 20 6f 6e 20 62 69 6e 61 72 79 20 66 69 6c rk on binary fil
3350: 65 73 2e 20 20 49 66 20 61 20 62 69 6e 61 72 79 es. If a binary
3360: 0a 2a 2a 20 66 69 6c 65 20 69 73 20 65 6e 63 6f .** file is enco
3370: 75 6e 74 65 72 65 64 2c 20 30 20 69 73 20 72 65 untered, 0 is re
3380: 74 75 72 6e 65 64 20 61 6e 64 20 70 4f 75 74 20 turned and pOut
3390: 69 73 20 77 72 69 74 74 65 6e 20 77 69 74 68 0a is written with.
33a0: 2a 2a 20 74 65 78 74 20 22 63 61 6e 6e 6f 74 20 ** text "cannot
33b0: 63 6f 6d 70 75 74 65 20 64 69 66 66 65 72 65 6e compute differen
33c0: 63 65 20 62 65 74 77 65 65 6e 20 62 69 6e 61 72 ce between binar
33d0: 79 20 66 69 6c 65 73 22 2e 0a 2a 2a 0a 2a 2a 2a y files"..**.***
33e0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
33f0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
3400: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
3410: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
3420: 2a 2a 2a 2a 2a 2a 2a 2a 2a 0a 2a 2a 0a 2a 2a 20 *********.**.**
3430: 54 68 65 20 63 6f 72 65 20 61 6c 67 6f 72 69 74 The core algorit
3440: 68 6d 20 69 73 20 61 20 76 61 72 69 61 74 69 6f hm is a variatio
3450: 6e 20 6f 6e 20 74 68 65 20 63 6c 61 73 73 69 63 n on the classic
3460: 20 57 61 67 6e 65 72 0a 2a 2a 20 6d 69 6e 69 6d Wagner.** minim
3470: 75 6d 20 65 64 69 74 20 64 69 73 74 61 6e 63 65 um edit distance
3480: 20 77 69 74 68 20 65 6e 68 61 6e 63 65 6d 65 6e with enhancemen
3490: 74 73 20 74 6f 20 72 65 64 75 63 65 20 74 68 65 ts to reduce the
34a0: 20 72 75 6e 74 69 6d 65 0a 2a 2a 20 74 6f 20 62 runtime.** to b
34b0: 65 20 61 6c 6d 6f 73 74 20 6c 69 6e 65 61 72 20 e almost linear
34c0: 69 6e 20 74 68 65 20 63 6f 6d 6d 6f 6e 20 63 61 in the common ca
34d0: 73 65 20 77 68 65 72 65 20 74 68 65 20 74 77 6f se where the two
34e0: 20 66 69 6c 65 73 0a 2a 2a 20 68 61 76 65 20 61 files.** have a
34f0: 20 6c 6f 74 20 69 6e 20 63 6f 6d 6d 6f 6e 2e 20 lot in common.
3500: 20 46 6f 72 20 61 64 64 69 74 69 6f 6e 61 6c 20 For additional
3510: 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 73 65 65 0a information see.
3520: 2a 2a 20 45 75 67 65 6e 65 20 57 2e 20 4d 79 65 ** Eugene W. Mye
3530: 72 73 2c 20 22 41 6e 20 4f 28 4e 44 29 20 44 69 rs, "An O(ND) Di
3540: 66 66 65 72 65 6e 63 65 20 41 6c 67 6f 72 69 74 fference Algorit
3550: 68 6d 20 41 6e 64 20 49 74 73 0a 2a 2a 20 56 61 hm And Its.** Va
3560: 72 69 61 74 69 6f 6e 73 22 0a 2a 2a 0a 2a 2a 20 riations".**.**
3570: 43 6f 6e 73 69 64 65 72 20 63 6f 6d 70 61 72 69 Consider compari
3580: 6e 67 20 73 74 72 69 6e 67 73 20 41 20 61 6e 64 ng strings A and
3590: 20 42 2e 20 20 41 3d 61 62 63 61 62 62 61 20 61 B. A=abcabba a
35a0: 6e 64 20 42 3d 63 62 61 62 61 63 0a 2a 2a 20 57 nd B=cbabac.** W
35b0: 65 20 63 6f 6e 73 74 72 75 63 74 20 61 20 22 57 e construct a "W
35c0: 61 67 6e 65 72 22 20 6d 61 74 72 69 78 20 57 20 agner" matrix W
35d0: 77 69 74 68 20 41 20 61 6c 6f 6e 67 20 74 68 65 with A along the
35e0: 20 58 20 61 78 69 73 20 61 6e 64 20 0a 2a 2a 20 X axis and .**
35f0: 42 20 61 6c 6f 6e 67 20 74 68 65 20 59 20 61 78 B along the Y ax
3600: 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20 63 20 is:.**.** c
3610: 36 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6
3620: 2a 0a 2a 2a 20 20 20 20 20 61 20 35 20 20 20 20 *.** a 5
3630: 20 20 20 20 20 20 20 20 20 20 20 2a 0a 2a 2a 20 *.**
3640: 20 20 20 20 62 20 34 20 20 20 20 20 20 20 20 20 b 4
3650: 20 20 2a 20 2a 0a 2a 2a 20 20 20 20 20 61 20 33 * *.** a 3
3660: 20 20 20 20 20 20 20 20 20 2a 0a 2a 2a 20 20 20 *.**
3670: 20 20 62 20 32 20 20 20 20 20 20 20 2a 0a 2a 2a b 2 *.**
3680: 20 20 20 42 20 63 20 31 20 20 20 20 20 20 20 2a B c 1 *
3690: 0a 2a 2a 20 20 20 20 20 20 20 30 20 2a 20 2a 20 .** 0 * *
36a0: 2a 20 0a 2a 2a 20 20 20 20 20 20 20 20 20 30 20 * .** 0
36b0: 31 20 32 20 33 20 34 20 35 20 36 20 37 0a 2a 2a 1 2 3 4 5 6 7.**
36c0: 20 20 20 20 20 20 20 20 20 20 20 61 20 62 20 63 a b c
36d0: 20 61 20 62 20 62 20 61 0a 2a 2a 20 20 20 20 20 a b b a.**
36e0: 20 20 20 20 20 20 41 0a 2a 2a 0a 2a 2a 20 28 4e A.**.** (N
36f0: 6f 74 65 3a 20 77 65 20 64 72 61 77 20 74 68 69 ote: we draw thi
3700: 73 20 57 61 67 6e 65 72 20 6d 61 74 72 69 78 20 s Wagner matrix
3710: 77 69 74 68 20 74 68 65 20 6f 72 69 67 69 6e 20 with the origin
3720: 61 74 20 74 68 65 20 6c 6f 77 65 72 20 0a 2a 2a at the lower .**
3730: 20 6c 65 66 74 20 77 68 65 72 65 61 73 20 4d 79 left whereas My
3740: 65 72 73 20 75 73 65 73 20 74 68 65 20 6f 72 69 ers uses the ori
3750: 67 69 6e 20 61 74 20 74 68 65 20 75 70 70 65 72 gin at the upper
3760: 20 6c 65 66 74 2e 20 20 4f 74 68 65 72 77 69 73 left. Otherwis
3770: 65 2c 0a 2a 2a 20 74 68 65 79 20 61 72 65 20 74 e,.** they are t
3780: 68 65 20 73 61 6d 65 2e 29 0a 2a 2a 0a 2a 2a 20 he same.).**.**
3790: 4c 65 74 20 59 20 62 65 20 74 68 65 20 6d 61 78 Let Y be the max
37a0: 69 6d 75 6d 20 79 20 76 61 6c 75 65 20 6f 72 20 imum y value or
37b0: 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 63 68 the number of ch
37c0: 61 72 61 63 74 65 72 73 20 69 6e 20 42 2e 0a 2a aracters in B..*
37d0: 2a 20 36 20 69 6e 20 74 68 69 73 20 65 78 61 6d * 6 in this exam
37e0: 70 6c 65 2e 20 20 58 20 69 73 20 74 68 65 20 6d ple. X is the m
37f0: 61 78 69 6d 75 6d 20 78 20 76 61 6c 75 65 20 6f aximum x value o
3800: 72 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 0a r the number of.
3810: 2a 2a 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20 41 ** elements in A
3820: 2e 20 20 48 65 72 65 20 37 2e 0a 2a 2a 0a 2a 2a . Here 7..**.**
3830: 20 4f 75 72 20 67 6f 61 6c 20 69 73 20 74 6f 20 Our goal is to
3840: 66 69 6e 64 20 61 20 70 61 74 68 20 66 72 6f 6d find a path from
3850: 20 28 30 2c 30 29 20 74 6f 20 28 58 2c 59 29 2e (0,0) to (X,Y).
3860: 20 20 54 68 65 20 70 61 74 68 20 63 61 6e 0a 2a The path can.*
3870: 2a 20 75 73 65 20 68 6f 72 69 7a 6f 6e 74 61 6c * use horizontal
3880: 2c 20 76 65 72 74 69 63 61 6c 2c 20 6f 72 20 64 , vertical, or d
3890: 69 61 67 6f 6e 61 6c 20 73 74 65 70 73 2e 20 20 iagonal steps.
38a0: 41 20 64 69 61 67 6f 6e 61 6c 20 66 72 6f 6d 0a A diagonal from.
38b0: 2a 2a 20 28 78 2d 31 2c 79 2d 31 29 20 74 6f 20 ** (x-1,y-1) to
38c0: 28 78 2c 79 29 20 69 73 20 6f 6e 6c 79 20 61 6c (x,y) is only al
38d0: 6c 6f 77 65 64 20 69 66 20 41 5b 78 5d 3d 3d 42 lowed if A[x]==B
38e0: 5b 79 5d 2e 20 20 41 20 76 65 72 74 69 63 61 6c [y]. A vertical
38f0: 0a 2a 2a 20 73 74 65 70 73 20 63 6f 72 72 65 73 .** steps corres
3900: 70 6f 6e 64 73 20 74 6f 20 61 6e 20 69 6e 73 65 ponds to an inse
3910: 72 74 69 6f 6e 2e 20 20 41 20 68 6f 72 69 7a 6f rtion. A horizo
3920: 6e 74 61 6c 20 73 74 65 70 20 63 6f 72 72 65 73 ntal step corres
3930: 70 6f 6e 64 73 0a 2a 2a 20 74 6f 20 61 20 64 65 ponds.** to a de
3940: 6c 65 74 69 6f 6e 2e 20 20 57 65 20 77 61 6e 74 letion. We want
3950: 20 74 6f 20 66 69 6e 64 20 74 68 65 20 70 61 74 to find the pat
3960: 68 20 77 69 74 68 20 74 68 65 20 66 65 77 65 73 h with the fewes
3970: 74 0a 2a 2a 20 68 6f 72 69 7a 6f 6e 74 61 6c 20 t.** horizontal
3980: 61 6e 64 20 76 65 72 74 69 63 61 6c 20 73 74 65 and vertical ste
3990: 70 73 2e 0a 2a 2a 0a 2a 2a 20 44 69 61 67 6f 6e ps..**.** Diagon
39a0: 61 6c 20 6b 20 63 6f 6e 73 69 73 74 73 20 6f 66 al k consists of
39b0: 20 61 6c 6c 20 70 6f 69 6e 74 73 20 73 75 63 68 all points such
39c0: 20 74 68 61 74 20 78 2d 79 3d 3d 6b 2e 20 20 44 that x-y==k. D
39d0: 69 61 67 6f 6e 61 6c 0a 2a 2a 20 7a 65 72 6f 20 iagonal.** zero
39e0: 62 65 67 69 6e 73 20 61 74 20 74 68 65 20 6f 72 begins at the or
39f0: 69 67 69 6e 2e 20 20 44 69 61 67 6f 6e 61 6c 20 igin. Diagonal
3a00: 31 20 62 65 67 69 6e 73 20 61 74 20 28 31 2c 30 1 begins at (1,0
3a10: 29 2e 20 20 0a 2a 2a 20 44 69 61 67 6f 6e 61 6c ). .** Diagonal
3a20: 20 2d 31 20 62 65 67 69 6e 73 20 61 74 20 28 30 -1 begins at (0
3a30: 2c 31 29 2e 20 20 41 6c 6c 20 64 69 61 67 6f 6e ,1). All diagon
3a40: 61 6c 73 20 6d 6f 76 65 20 75 70 20 61 6e 64 20 als move up and
3a50: 74 6f 20 74 68 65 0a 2a 2a 20 72 69 67 68 74 20 to the.** right
3a60: 61 74 20 34 35 20 64 65 67 72 65 65 73 2e 20 20 at 45 degrees.
3a70: 44 69 61 67 6f 6e 61 6c 20 6e 75 6d 62 65 72 20 Diagonal number
3a80: 69 6e 63 72 65 61 73 65 20 66 72 6f 6d 20 75 70 increase from up
3a90: 70 65 72 20 6c 65 66 74 0a 2a 2a 20 74 6f 20 6c per left.** to l
3aa0: 6f 77 65 72 20 72 69 67 68 74 2e 0a 2a 2a 20 0a ower right..** .
3ab0: 2a 2a 20 4d 79 65 72 73 20 6d 61 74 72 69 78 20 ** Myers matrix
3ac0: 4d 20 69 73 20 61 20 6c 6f 77 65 72 20 72 69 67 M is a lower rig
3ad0: 68 74 20 74 72 69 61 6e 67 75 6c 61 72 20 6d 61 ht triangular ma
3ae0: 74 72 69 78 20 77 69 74 68 20 69 6e 64 69 63 65 trix with indice
3af0: 73 20 64 0a 2a 2a 20 61 6c 6f 6e 67 20 74 68 65 s d.** along the
3b00: 20 62 6f 74 74 6f 6d 20 61 6e 64 20 69 20 76 65 bottom and i ve
3b10: 72 74 69 63 61 6c 6c 79 3a 0a 2a 2a 0a 2a 2a 20 rtically:.**.**
3b20: 0a 2a 2a 20 20 20 69 3d 34 20 7c 20 20 20 20 20 .** i=4 |
3b30: 20 20 20 20 20 20 20 2b 34 20 20 5c 0a 2a 2a 20 +4 \.**
3b40: 20 20 20 20 33 20 7c 20 20 20 20 20 20 20 20 20 3 |
3b50: 2b 33 20 2b 32 20 20 20 7c 0a 2a 2a 20 20 20 20 +3 +2 |.**
3b60: 20 32 20 7c 20 20 20 20 20 20 2b 32 20 2b 31 20 2 | +2 +1
3b70: 20 30 20 20 20 7c 2d 20 6b 20 76 61 6c 75 65 73 0 |- k values
3b80: 2e 20 20 20 6b 20 3d 20 32 2a 69 2d 64 0a 2a 2a . k = 2*i-d.**
3b90: 20 20 20 20 20 31 20 7c 20 20 20 2b 31 20 20 30 1 | +1 0
3ba0: 20 2d 31 20 2d 32 20 20 20 7c 0a 2a 2a 20 20 20 -1 -2 |.**
3bb0: 20 20 30 20 7c 20 30 20 2d 31 20 2d 32 20 2d 33 0 | 0 -1 -2 -3
3bc0: 20 2d 34 20 20 2f 0a 2a 2a 20 20 20 20 20 20 20 -4 /.**
3bd0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
3be0: 2a 2a 20 20 20 20 20 20 20 20 20 30 20 20 31 20 ** 0 1
3bf0: 20 32 20 20 33 20 20 34 20 3d 20 64 0a 2a 2a 0a 2 3 4 = d.**.
3c00: 2a 2a 20 45 61 63 68 20 65 6c 65 6d 65 6e 74 20 ** Each element
3c10: 6f 66 20 74 68 65 20 4d 79 65 72 73 20 6d 61 74 of the Myers mat
3c20: 72 69 78 20 63 6f 72 72 65 73 70 6f 6e 64 73 20 rix corresponds
3c30: 74 6f 20 61 20 64 69 61 67 6f 6e 61 6c 2e 0a 2a to a diagonal..*
3c40: 2a 20 54 68 65 20 64 69 61 67 6f 6e 61 6c 20 69 * The diagonal i
3c50: 73 20 6b 3d 32 2a 69 2d 64 2e 20 20 54 68 65 20 s k=2*i-d. The
3c60: 64 69 61 67 6f 6e 61 6c 20 76 61 6c 75 65 73 20 diagonal values
3c70: 61 72 65 20 73 68 6f 77 6e 0a 2a 2a 20 69 6e 20 are shown.** in
3c80: 74 68 65 20 74 65 6d 70 6c 61 74 65 20 61 62 6f the template abo
3c90: 76 65 2e 0a 2a 2a 0a 2a 2a 20 45 61 63 68 20 65 ve..**.** Each e
3ca0: 6e 74 72 79 20 69 6e 20 4d 20 72 65 70 72 65 73 ntry in M repres
3cb0: 65 6e 74 73 20 74 68 65 20 65 6e 64 2d 70 6f 69 ents the end-poi
3cc0: 6e 74 20 6f 6e 20 61 20 70 61 74 68 20 66 72 6f nt on a path fro
3cd0: 6d 20 28 30 2c 30 29 2e 0a 2a 2a 20 54 68 65 20 m (0,0)..** The
3ce0: 65 6e 64 2d 70 6f 69 6e 74 20 69 73 20 6f 6e 20 end-point is on
3cf0: 64 69 61 67 6f 6e 61 6c 20 6b 2e 20 20 54 68 65 diagonal k. The
3d00: 20 76 61 6c 75 65 20 73 74 6f 72 65 64 20 69 6e value stored in
3d10: 20 4d 20 69 73 0a 2a 2a 20 71 3d 78 2b 79 20 77 M is.** q=x+y w
3d20: 68 65 72 65 20 28 78 2c 79 29 20 69 73 20 74 68 here (x,y) is th
3d30: 65 20 74 65 72 6d 69 6e 75 73 20 6f 66 20 74 68 e terminus of th
3d40: 65 20 70 61 74 68 2e 20 20 41 20 70 61 74 68 0a e path. A path.
3d50: 2a 2a 20 74 6f 20 4d 5b 64 5d 5b 69 5d 20 77 69 ** to M[d][i] wi
3d60: 6c 6c 20 63 6f 6d 65 20 74 68 72 6f 75 67 68 20 ll come through
3d70: 65 69 74 68 65 72 20 4d 5b 64 2d 31 5d 5b 69 2d either M[d-1][i-
3d80: 31 5d 20 6f 72 0a 2a 2a 20 74 68 6f 75 67 68 20 1] or.** though
3d90: 4d 5b 64 2d 31 5d 5b 69 5d 2c 20 77 68 69 63 68 M[d-1][i], which
3da0: 65 76 65 72 20 68 6f 6c 64 73 20 74 68 65 20 6c ever holds the l
3db0: 61 72 67 65 73 74 20 76 61 6c 75 65 20 6f 66 20 argest value of
3dc0: 71 2e 0a 2a 2a 20 49 66 20 62 6f 74 68 20 65 6c q..** If both el
3dd0: 65 6d 65 6e 74 73 20 68 6f 6c 64 20 74 68 65 20 ements hold the
3de0: 73 61 6d 65 20 76 61 6c 75 65 2c 20 74 68 65 20 same value, the
3df0: 70 61 74 68 20 63 6f 6d 65 73 0a 2a 2a 20 74 68 path comes.** th
3e00: 72 6f 75 67 68 20 4d 5b 64 2d 31 5d 5b 69 2d 31 rough M[d-1][i-1
3e10: 5d 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 76 61 6c ]..**.** The val
3e20: 75 65 20 6f 66 20 64 20 69 73 20 74 68 65 20 6e ue of d is the n
3e30: 75 6d 62 65 72 20 6f 66 20 69 6e 73 65 72 74 69 umber of inserti
3e40: 6f 6e 73 20 61 6e 64 20 64 65 6c 65 74 69 6f 6e ons and deletion
3e50: 73 0a 2a 2a 20 6d 61 64 65 20 73 6f 20 66 61 72 s.** made so far
3e60: 20 6f 6e 20 74 68 65 20 70 61 74 68 2e 20 20 4d on the path. M
3e70: 20 67 72 6f 77 73 20 70 72 6f 67 72 65 73 73 69 grows progressi
3e80: 76 65 6c 79 2e 20 20 53 6f 20 74 68 65 0a 2a 2a vely. So the.**
3e90: 20 73 69 7a 65 20 6f 66 20 74 68 65 20 4d 20 6d size of the M m
3ea0: 61 74 72 69 78 20 69 73 20 70 72 6f 70 6f 72 74 atrix is proport
3eb0: 69 6f 6e 61 6c 20 74 6f 20 64 2a 64 2e 20 20 46 ional to d*d. F
3ec0: 6f 72 20 74 68 65 0a 2a 2a 20 63 6f 6d 6d 6f 6e or the.** common
3ed0: 20 63 61 73 65 20 77 68 65 72 65 20 41 20 61 6e case where A an
3ee0: 64 20 42 20 61 72 65 20 73 69 6d 69 6c 61 72 2c d B are similar,
3ef0: 20 64 20 77 69 6c 6c 20 62 65 20 73 6d 61 6c 6c d will be small
3f00: 0a 2a 2a 20 63 6f 6d 70 61 72 65 64 20 74 6f 20 .** compared to
3f10: 58 20 61 6e 64 20 59 20 73 6f 20 6c 69 74 74 6c X and Y so littl
3f20: 65 20 6d 65 6d 6f 72 79 20 69 73 20 72 65 71 75 e memory is requ
3f30: 69 72 65 64 2e 20 20 54 68 65 0a 2a 2a 20 6f 72 ired. The.** or
3f40: 69 67 69 6e 61 6c 20 57 61 67 6e 65 72 20 61 6c iginal Wagner al
3f50: 67 6f 72 69 74 68 6d 20 72 65 71 75 69 72 65 73 gorithm requires
3f60: 20 58 2a 59 20 6d 65 6d 6f 72 79 2c 20 77 68 69 X*Y memory, whi
3f70: 63 68 20 66 6f 72 0a 2a 2a 20 6c 61 72 67 65 72 ch for.** larger
3f80: 20 66 69 6c 65 73 20 28 31 30 30 4b 20 6c 69 6e files (100K lin
3f90: 65 73 29 20 69 73 20 6d 6f 72 65 20 6d 65 6d 6f es) is more memo
3fa0: 72 79 20 74 68 61 6e 20 77 65 20 68 61 76 65 20 ry than we have
3fb0: 61 74 0a 2a 2a 20 68 61 6e 64 2e 0a 2a 2f 0a 69 at.** hand..*/.i
3fc0: 6e 74 20 2a 74 65 78 74 5f 64 69 66 66 28 0a 20 nt *text_diff(.
3fd0: 20 42 6c 6f 62 20 2a 70 41 5f 42 6c 6f 62 2c 20 Blob *pA_Blob,
3fe0: 20 20 2f 2a 20 46 52 4f 4d 20 66 69 6c 65 20 2a /* FROM file *
3ff0: 2f 0a 20 20 42 6c 6f 62 20 2a 70 42 5f 42 6c 6f /. Blob *pB_Blo
4000: 62 2c 20 20 20 2f 2a 20 54 4f 20 66 69 6c 65 20 b, /* TO file
4010: 2a 2f 0a 20 20 42 6c 6f 62 20 2a 70 4f 75 74 2c */. Blob *pOut,
4020: 20 20 20 20 20 20 2f 2a 20 57 72 69 74 65 20 75 /* Write u
4030: 6e 69 66 69 65 64 20 64 69 66 66 20 68 65 72 65 nified diff here
4040: 20 69 66 20 6e 6f 74 20 4e 55 4c 4c 20 2a 2f 0a if not NULL */.
4050: 20 20 69 6e 74 20 6e 43 6f 6e 74 65 78 74 20 20 int nContext
4060: 20 20 20 2f 2a 20 41 6d 6f 75 6e 74 20 6f 66 20 /* Amount of
4070: 63 6f 6e 74 65 78 74 20 74 6f 20 75 6e 69 66 69 context to unifi
4080: 65 64 20 64 69 66 66 20 2a 2f 0a 29 7b 0a 20 20 ed diff */.){.
4090: 44 4c 69 6e 65 20 2a 41 2c 20 2a 42 3b 20 20 20 DLine *A, *B;
40a0: 20 2f 2a 20 46 69 6c 65 73 20 62 65 69 6e 67 20 /* Files being
40b0: 63 6f 6d 70 61 72 65 64 20 2a 2f 0a 20 20 69 6e compared */. in
40c0: 74 20 58 2c 20 59 3b 20 20 20 20 20 20 20 20 2f t X, Y; /
40d0: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65 6c 65 6d * Number of elem
40e0: 65 6e 74 73 20 69 6e 20 41 20 61 6e 64 20 42 20 ents in A and B
40f0: 2a 2f 0a 20 20 69 6e 74 20 78 2c 20 79 3b 20 20 */. int x, y;
4100: 20 20 20 20 20 20 2f 2a 20 49 6e 64 69 63 65 73 /* Indices
4110: 3a 20 20 41 5b 78 5d 20 61 6e 64 20 42 5b 79 5d : A[x] and B[y]
4120: 20 2a 2f 0a 20 20 69 6e 74 20 73 7a 4d 20 3d 20 */. int szM =
4130: 30 3b 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 0; /* Number
4140: 20 6f 66 20 72 6f 77 73 20 61 6e 64 20 63 6f 6c of rows and col
4150: 75 6d 6e 73 20 69 6e 20 4d 20 2a 2f 0a 20 20 69 umns in M */. i
4160: 6e 74 20 2a 2a 4d 20 3d 20 30 3b 20 20 20 20 20 nt **M = 0;
4170: 2f 2a 20 4d 79 65 72 73 20 6d 61 74 72 69 78 20 /* Myers matrix
4180: 2a 2f 0a 20 20 69 6e 74 20 69 2c 20 64 3b 20 20 */. int i, d;
4190: 20 20 20 20 20 20 2f 2a 20 49 6e 64 69 63 65 73 /* Indices
41a0: 20 6f 6e 20 4d 2e 20 20 4d 5b 64 5d 5b 69 5d 20 on M. M[d][i]
41b0: 2a 2f 0a 20 20 69 6e 74 20 6b 2c 20 71 3b 20 20 */. int k, q;
41c0: 20 20 20 20 20 20 2f 2a 20 44 69 61 67 6f 6e 61 /* Diagona
41d0: 6c 20 6e 75 6d 62 65 72 20 61 6e 64 20 64 69 73 l number and dis
41e0: 74 69 6e 63 74 20 66 72 6f 6d 20 28 30 2c 30 29 tinct from (0,0)
41f0: 20 2a 2f 0a 20 20 69 6e 74 20 4b 2c 20 44 3b 20 */. int K, D;
4200: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 64 69 /* The di
4210: 61 67 6f 6e 61 6c 20 61 6e 64 20 64 20 66 6f 72 agonal and d for
4220: 20 74 68 65 20 66 69 6e 61 6c 20 73 6f 6c 75 74 the final solut
4230: 69 6f 6e 20 2a 2f 20 20 20 20 20 20 20 20 20 20 ion */
4240: 0a 20 20 69 6e 74 20 2a 52 20 3d 20 30 3b 20 20 . int *R = 0;
4250: 20 20 20 20 2f 2a 20 52 65 73 75 6c 74 20 76 65 /* Result ve
4260: 63 74 6f 72 20 2a 2f 0a 20 20 69 6e 74 20 72 3b ctor */. int r;
4270: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4c 6f /* Lo
4280: 6f 70 20 76 61 72 69 61 62 6c 65 73 20 2a 2f 0a op variables */.
4290: 20 20 69 6e 74 20 67 6f 20 3d 20 31 3b 20 20 20 int go = 1;
42a0: 20 20 20 2f 2a 20 4f 75 74 65 72 20 6c 6f 6f 70 /* Outer loop
42b0: 20 63 6f 6e 74 72 6f 6c 20 2a 2f 0a 20 20 69 6e control */. in
42c0: 74 20 4d 41 58 3b 20 20 20 20 20 20 20 20 20 2f t MAX; /
42d0: 2a 20 4c 61 72 67 65 73 74 20 6f 66 20 58 20 61 * Largest of X a
42e0: 6e 64 20 59 20 2a 2f 0a 0a 20 20 2f 2a 20 42 72 nd Y */.. /* Br
42f0: 65 61 6b 20 74 68 65 20 74 77 6f 20 66 69 6c 65 eak the two file
4300: 73 20 62 65 69 6e 67 20 64 69 66 66 65 64 20 69 s being diffed i
4310: 6e 74 6f 20 69 6e 64 69 76 69 64 75 61 6c 20 6c nto individual l
4320: 69 6e 65 73 2e 0a 20 20 2a 2a 20 43 6f 6d 70 75 ines.. ** Compu
4330: 74 65 20 68 61 73 68 65 73 20 6f 6e 20 65 61 63 te hashes on eac
4340: 68 20 6c 69 6e 65 20 66 6f 72 20 66 61 73 74 20 h line for fast
4350: 63 6f 6d 70 61 72 69 73 6f 6e 2e 0a 20 20 2a 2f comparison.. */
4360: 0a 20 20 41 20 3d 20 62 72 65 61 6b 5f 69 6e 74 . A = break_int
4370: 6f 5f 6c 69 6e 65 73 28 62 6c 6f 62 5f 73 74 72 o_lines(blob_str
4380: 28 70 41 5f 42 6c 6f 62 29 2c 20 26 58 29 3b 0a (pA_Blob), &X);.
4390: 20 20 42 20 3d 20 62 72 65 61 6b 5f 69 6e 74 6f B = break_into
43a0: 5f 6c 69 6e 65 73 28 62 6c 6f 62 5f 73 74 72 28 _lines(blob_str(
43b0: 70 42 5f 42 6c 6f 62 29 2c 20 26 59 29 3b 0a 0a pB_Blob), &Y);..
43c0: 20 20 69 66 28 20 41 3d 3d 30 20 7c 7c 20 42 3d if( A==0 || B=
43d0: 3d 30 20 29 7b 0a 20 20 20 20 66 72 65 65 28 41 =0 ){. free(A
43e0: 29 3b 0a 20 20 20 20 66 72 65 65 28 42 29 3b 0a );. free(B);.
43f0: 20 20 20 20 69 66 28 20 70 4f 75 74 20 29 7b 0a if( pOut ){.
4400: 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 6e blob_appen
4410: 64 66 28 70 4f 75 74 2c 20 22 63 61 6e 6e 6f 74 df(pOut, "cannot
4420: 20 63 6f 6d 70 75 74 65 20 64 69 66 66 65 72 65 compute differe
4430: 6e 63 65 20 62 65 74 77 65 65 6e 20 62 69 6e 61 nce between bina
4440: 72 79 20 66 69 6c 65 73 5c 6e 22 29 3b 0a 20 20 ry files\n");.
4450: 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e 20 30 }. return 0
4460: 3b 0a 20 20 7d 0a 0a 20 20 73 7a 4d 20 3d 20 30 ;. }.. szM = 0
4470: 3b 0a 20 20 4d 41 58 20 3d 20 58 3e 59 20 3f 20 ;. MAX = X>Y ?
4480: 58 20 3a 20 59 3b 0a 20 20 69 66 28 20 4d 41 58 X : Y;. if( MAX
4490: 3e 32 30 30 30 20 29 20 4d 41 58 20 3d 20 32 30 >2000 ) MAX = 20
44a0: 30 30 3b 0a 20 20 66 6f 72 28 64 3d 30 3b 20 67 00;. for(d=0; g
44b0: 6f 20 26 26 20 64 3c 3d 4d 41 58 3b 20 64 2b 2b o && d<=MAX; d++
44c0: 29 7b 0a 20 20 20 20 69 66 28 20 73 7a 4d 3c 64 ){. if( szM<d
44d0: 2b 31 20 29 7b 0a 20 20 20 20 20 20 73 7a 4d 20 +1 ){. szM
44e0: 2b 3d 20 73 7a 4d 20 2b 20 31 30 3b 0a 20 20 20 += szM + 10;.
44f0: 20 20 20 4d 20 3d 20 72 65 61 6c 6c 6f 63 28 4d M = realloc(M
4500: 2c 20 73 69 7a 65 6f 66 28 4d 5b 30 5d 29 2a 73 , sizeof(M[0])*s
4510: 7a 4d 29 3b 0a 20 20 20 20 20 20 69 66 28 20 4d zM);. if( M
4520: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 20 20 66 ==0 ){. f
4530: 6f 73 73 69 6c 5f 70 61 6e 69 63 28 22 6f 75 74 ossil_panic("out
4540: 20 6f 66 20 6d 65 6d 6f 72 79 22 29 3b 0a 20 20 of memory");.
4550: 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 }. }.
4560: 4d 5b 64 5d 20 3d 20 6d 61 6c 6c 6f 63 28 20 73 M[d] = malloc( s
4570: 69 7a 65 6f 66 28 4d 5b 64 5d 5b 30 5d 29 2a 28 izeof(M[d][0])*(
4580: 64 2b 31 29 20 29 3b 0a 20 20 20 20 69 66 28 20 d+1) );. if(
4590: 4d 5b 64 5d 3d 3d 30 20 29 7b 0a 20 20 20 20 20 M[d]==0 ){.
45a0: 20 66 6f 73 73 69 6c 5f 70 61 6e 69 63 28 22 6f fossil_panic("o
45b0: 75 74 20 6f 66 20 6d 65 6d 6f 72 79 22 29 3b 0a ut of memory");.
45c0: 20 20 20 20 7d 0a 20 20 20 20 66 6f 72 28 69 3d }. for(i=
45d0: 30 3b 20 69 3c 3d 64 3b 20 69 2b 2b 29 7b 0a 20 0; i<=d; i++){.
45e0: 20 20 20 20 20 6b 20 3d 20 32 2a 69 20 2d 20 64 k = 2*i - d
45f0: 3b 0a 20 20 20 20 20 20 69 66 28 20 64 3d 3d 30 ;. if( d==0
4600: 20 29 7b 0a 20 20 20 20 20 20 20 20 71 20 3d 20 ){. q =
4610: 30 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 20 69 0;. }else i
4620: 66 28 20 69 3d 3d 30 20 29 7b 0a 20 20 20 20 20 f( i==0 ){.
4630: 20 20 20 71 20 3d 20 4d 5b 64 2d 31 5d 5b 30 5d q = M[d-1][0]
4640: 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 20 69 66 ;. }else if
4650: 28 20 69 3c 64 2d 31 20 26 26 20 4d 5b 64 2d 31 ( i<d-1 && M[d-1
4660: 5d 5b 69 2d 31 5d 20 3c 20 4d 5b 64 2d 31 5d 5b ][i-1] < M[d-1][
4670: 69 5d 20 29 7b 0a 20 20 20 20 20 20 20 20 71 20 i] ){. q
4680: 3d 20 4d 5b 64 2d 31 5d 5b 69 5d 3b 0a 20 20 20 = M[d-1][i];.
4690: 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 }else{.
46a0: 20 20 71 20 3d 20 4d 5b 64 2d 31 5d 5b 69 2d 31 q = M[d-1][i-1
46b0: 5d 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 ];. }.
46c0: 20 78 20 3d 20 28 6b 20 2b 20 71 20 2b 20 31 29 x = (k + q + 1)
46d0: 2f 32 3b 0a 20 20 20 20 20 20 79 20 3d 20 78 20 /2;. y = x
46e0: 2d 20 6b 3b 0a 20 20 20 20 20 20 69 66 28 20 78 - k;. if( x
46f0: 3c 30 20 7c 7c 20 78 3e 58 20 7c 7c 20 79 3c 30 <0 || x>X || y<0
4700: 20 7c 7c 20 79 3e 59 20 29 7b 0a 20 20 20 20 20 || y>Y ){.
4710: 20 20 20 78 20 3d 20 79 20 3d 20 30 3b 0a 20 20 x = y = 0;.
4720: 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 }else{.
4730: 20 20 20 77 68 69 6c 65 28 20 78 3c 58 20 26 26 while( x<X &&
4740: 20 79 3c 59 20 26 26 20 73 61 6d 65 5f 64 6c 69 y<Y && same_dli
4750: 6e 65 28 26 41 5b 78 5d 2c 26 42 5b 79 5d 29 20 ne(&A[x],&B[y])
4760: 29 7b 20 78 2b 2b 3b 20 79 2b 2b 3b 20 7d 0a 20 ){ x++; y++; }.
4770: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 4d 5b 64 }. M[d
4780: 5d 5b 69 5d 20 3d 20 78 20 2b 20 79 3b 0a 20 20 ][i] = x + y;.
4790: 20 20 20 20 44 45 42 55 47 28 20 70 72 69 6e 74 DEBUG( print
47a0: 66 28 22 4d 5b 25 64 5d 5b 25 69 5d 20 3d 20 25 f("M[%d][%i] = %
47b0: 64 20 20 6b 3d 25 64 20 28 25 64 2c 25 64 29 5c d k=%d (%d,%d)\
47c0: 6e 22 2c 20 64 2c 20 69 2c 20 78 2b 79 2c 20 6b n", d, i, x+y, k
47d0: 2c 20 78 2c 20 79 29 3b 20 29 0a 20 20 20 20 20 , x, y); ).
47e0: 20 69 66 28 20 78 3d 3d 58 20 26 26 20 79 3d 3d if( x==X && y==
47f0: 59 20 29 7b 0a 20 20 20 20 20 20 20 20 67 6f 20 Y ){. go
4800: 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 62 72 65 = 0;. bre
4810: 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 ak;. }.
4820: 7d 0a 20 20 7d 0a 20 20 69 66 28 20 64 3e 4d 41 }. }. if( d>MA
4830: 58 20 29 7b 0a 20 20 20 20 52 20 3d 20 6d 61 6c X ){. R = mal
4840: 6c 6f 63 28 20 73 69 7a 65 6f 66 28 52 5b 30 5d loc( sizeof(R[0]
4850: 29 2a 37 20 29 3b 0a 20 20 20 20 52 5b 30 5d 20 )*7 );. R[0]
4860: 3d 20 30 3b 0a 20 20 20 20 52 5b 31 5d 20 3d 20 = 0;. R[1] =
4870: 58 3b 0a 20 20 20 20 52 5b 32 5d 20 3d 20 59 3b X;. R[2] = Y;
4880: 0a 20 20 20 20 52 5b 33 5d 20 3d 20 30 3b 0a 20 . R[3] = 0;.
4890: 20 20 20 52 5b 34 5d 20 3d 20 30 3b 0a 20 20 20 R[4] = 0;.
48a0: 20 52 5b 35 5d 20 3d 20 30 3b 0a 20 20 20 20 52 R[5] = 0;. R
48b0: 5b 36 5d 20 3d 20 30 3b 0a 20 20 7d 65 6c 73 65 [6] = 0;. }else
48c0: 7b 0a 20 20 20 20 2f 2a 20 52 65 75 73 65 20 4d {. /* Reuse M
48d0: 5b 5d 20 61 73 20 66 6f 6c 6c 6f 77 73 3a 0a 20 [] as follows:.
48e0: 20 20 20 2a 2a 0a 20 20 20 20 2a 2a 20 20 20 20 **. **
48f0: 20 4d 5b 64 5d 5b 31 5d 20 3d 20 31 20 69 66 20 M[d][1] = 1 if
4900: 61 20 6c 69 6e 65 20 69 73 20 69 6e 73 65 72 74 a line is insert
4910: 65 64 20 6f 72 20 30 20 69 66 20 61 20 6c 69 6e ed or 0 if a lin
4920: 65 20 69 73 20 64 65 6c 65 74 65 64 2e 0a 20 20 e is deleted..
4930: 20 20 2a 2a 20 20 20 20 20 4d 5b 64 5d 5b 30 5d ** M[d][0]
4940: 20 3d 20 6e 75 6d 62 65 72 20 6f 66 20 6c 69 6e = number of lin
4950: 65 73 20 63 6f 70 69 65 64 20 61 66 74 65 72 20 es copied after
4960: 74 68 65 20 69 6e 73 20 6f 72 20 64 65 6c 20 61 the ins or del a
4970: 62 6f 76 65 2e 0a 20 20 20 20 2a 2a 0a 20 20 20 bove.. **.
4980: 20 2a 2f 0a 20 20 20 20 44 20 3d 20 64 20 2d 20 */. D = d -
4990: 31 3b 0a 20 20 20 20 4b 20 3d 20 58 20 2d 20 59 1;. K = X - Y
49a0: 3b 0a 20 20 20 20 66 6f 72 28 64 3d 44 2c 20 69 ;. for(d=D, i
49b0: 3d 28 4b 2b 44 29 2f 32 3b 20 64 3e 30 3b 20 64 =(K+D)/2; d>0; d
49c0: 2d 2d 29 7b 0a 20 20 20 20 20 20 44 45 42 55 47 --){. DEBUG
49d0: 28 20 70 72 69 6e 74 66 28 22 64 3d 25 64 20 69 ( printf("d=%d i
49e0: 3d 25 64 5c 6e 22 2c 20 64 2c 20 69 29 3b 20 29 =%d\n", d, i); )
49f0: 0a 20 20 20 20 20 20 69 66 28 20 69 3d 3d 64 20 . if( i==d
4a00: 7c 7c 20 28 69 3e 30 20 26 26 20 4d 5b 64 2d 31 || (i>0 && M[d-1
4a10: 5d 5b 69 2d 31 5d 20 3e 20 4d 5b 64 2d 31 5d 5b ][i-1] > M[d-1][
4a20: 69 5d 29 20 29 7b 0a 20 20 20 20 20 20 20 20 4d i]) ){. M
4a30: 5b 64 5d 5b 30 5d 20 3d 20 4d 5b 64 5d 5b 69 5d [d][0] = M[d][i]
4a40: 20 2d 20 4d 5b 64 2d 31 5d 5b 69 2d 31 5d 20 2d - M[d-1][i-1] -
4a50: 20 31 3b 0a 20 20 20 20 20 20 20 20 4d 5b 64 5d 1;. M[d]
4a60: 5b 31 5d 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 [1] = 0;.
4a70: 20 69 2d 2d 3b 0a 20 20 20 20 20 20 7d 65 6c 73 i--;. }els
4a80: 65 7b 0a 20 20 20 20 20 20 20 20 4d 5b 64 5d 5b e{. M[d][
4a90: 30 5d 20 3d 20 4d 5b 64 5d 5b 69 5d 20 2d 20 4d 0] = M[d][i] - M
4aa0: 5b 64 2d 31 5d 5b 69 5d 20 2d 20 31 3b 0a 20 20 [d-1][i] - 1;.
4ab0: 20 20 20 20 20 20 4d 5b 64 5d 5b 31 5d 20 3d 20 M[d][1] =
4ac0: 31 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 1;. }. }
4ad0: 0a 20 20 20 20 0a 20 20 20 20 44 45 42 55 47 28 . . DEBUG(
4ae0: 0a 20 20 20 20 20 20 70 72 69 6e 74 66 28 22 2d . printf("-
4af0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 5c 6e --------------\n
4b00: 4d 5b 30 5d 5b 30 5d 20 3d 20 25 35 64 5c 6e 22 M[0][0] = %5d\n"
4b10: 2c 20 4d 5b 30 5d 5b 30 5d 29 3b 0a 20 20 20 20 , M[0][0]);.
4b20: 20 20 66 6f 72 28 64 3d 31 3b 20 64 3c 3d 44 3b for(d=1; d<=D;
4b30: 20 64 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 70 d++){. p
4b40: 72 69 6e 74 66 28 22 4d 5b 25 64 5d 5b 30 5d 20 rintf("M[%d][0]
4b50: 3d 20 25 35 64 20 20 20 20 4d 5b 25 64 5d 5b 31 = %5d M[%d][1
4b60: 5d 20 3d 20 25 64 5c 6e 22 2c 64 2c 4d 5b 64 5d ] = %d\n",d,M[d]
4b70: 5b 30 5d 2c 64 2c 4d 5b 64 5d 5b 31 5d 29 3b 0a [0],d,M[d][1]);.
4b80: 20 20 20 20 20 20 7d 0a 20 20 20 20 29 0a 20 20 }. ).
4b90: 20 20 0a 20 20 20 20 2f 2a 20 41 6c 6c 6f 63 61 . /* Alloca
4ba0: 74 65 20 74 68 65 20 6f 75 74 70 75 74 20 76 65 te the output ve
4bb0: 63 74 6f 72 0a 20 20 20 20 2a 2f 0a 20 20 20 20 ctor. */.
4bc0: 52 20 3d 20 6d 61 6c 6c 6f 63 28 20 73 69 7a 65 R = malloc( size
4bd0: 6f 66 28 52 5b 30 5d 29 2a 28 44 2b 32 29 2a 33 of(R[0])*(D+2)*3
4be0: 20 29 3b 0a 20 20 20 20 69 66 28 20 52 3d 3d 30 );. if( R==0
4bf0: 20 29 7b 0a 20 20 20 20 20 20 66 6f 73 73 69 6c ){. fossil
4c00: 5f 66 61 74 61 6c 28 22 6f 75 74 20 6f 66 20 6d _fatal("out of m
4c10: 65 6d 6f 72 79 22 29 3b 0a 20 20 20 20 7d 0a 20 emory");. }.
4c20: 20 20 20 0a 20 20 20 20 2f 2a 20 50 6f 70 75 6c . /* Popul
4c30: 61 74 65 20 74 68 65 20 6f 75 74 70 75 74 20 76 ate the output v
4c40: 65 63 74 6f 72 0a 20 20 20 20 2a 2f 0a 20 20 20 ector. */.
4c50: 20 64 20 3d 20 72 20 3d 20 30 3b 0a 20 20 20 20 d = r = 0;.
4c60: 77 68 69 6c 65 28 20 64 3c 3d 44 20 29 7b 0a 20 while( d<=D ){.
4c70: 20 20 20 20 20 69 6e 74 20 6e 3b 0a 20 20 20 20 int n;.
4c80: 20 20 52 5b 72 2b 2b 5d 20 3d 20 4d 5b 64 2b 2b R[r++] = M[d++
4c90: 5d 5b 30 5d 2f 32 3b 20 20 20 2f 2a 20 43 4f 50 ][0]/2; /* COP
4ca0: 59 20 2a 2f 0a 20 20 20 20 20 20 69 66 28 20 64 Y */. if( d
4cb0: 3e 44 20 29 7b 0a 20 20 20 20 20 20 20 20 52 5b >D ){. R[
4cc0: 72 2b 2b 5d 20 3d 20 30 3b 0a 20 20 20 20 20 20 r++] = 0;.
4cd0: 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 0a 20 20 R[r++] = 0;.
4ce0: 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 break;.
4cf0: 20 20 20 7d 0a 20 20 20 20 20 20 69 66 28 20 4d }. if( M
4d00: 5b 64 5d 5b 31 5d 3d 3d 30 20 29 7b 0a 20 20 20 [d][1]==0 ){.
4d10: 20 20 20 20 20 6e 20 3d 20 31 3b 0a 20 20 20 20 n = 1;.
4d20: 20 20 20 20 77 68 69 6c 65 28 20 4d 5b 64 5d 5b while( M[d][
4d30: 30 5d 3d 3d 30 20 26 26 20 64 3c 44 20 26 26 20 0]==0 && d<D &&
4d40: 4d 5b 64 2b 31 5d 5b 31 5d 3d 3d 30 20 29 7b 0a M[d+1][1]==0 ){.
4d50: 20 20 20 20 20 20 20 20 20 20 64 2b 2b 3b 0a 20 d++;.
4d60: 20 20 20 20 20 20 20 20 20 6e 2b 2b 3b 0a 20 20 n++;.
4d70: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 }.
4d80: 52 5b 72 2b 2b 5d 20 3d 20 6e 3b 20 20 20 20 20 R[r++] = n;
4d90: 20 20 20 20 20 20 2f 2a 20 44 45 4c 45 54 45 20 /* DELETE
4da0: 2a 2f 0a 20 20 20 20 20 20 20 20 69 66 28 20 64 */. if( d
4db0: 3d 3d 44 20 7c 7c 20 4d 5b 64 5d 5b 30 5d 3e 30 ==D || M[d][0]>0
4dc0: 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 52 5b ){. R[
4dd0: 72 2b 2b 5d 20 3d 20 30 3b 20 20 20 20 20 20 20 r++] = 0;
4de0: 20 20 2f 2a 20 49 4e 53 45 52 54 20 2a 2f 0a 20 /* INSERT */.
4df0: 20 20 20 20 20 20 20 20 20 63 6f 6e 74 69 6e 75 continu
4e00: 65 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 e;. }.
4e10: 20 20 20 20 20 64 2b 2b 3b 0a 20 20 20 20 20 20 d++;.
4e20: 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 52 }else{. R
4e30: 5b 72 2b 2b 5d 20 3d 20 30 3b 20 20 20 20 20 20 [r++] = 0;
4e40: 20 20 20 20 20 2f 2a 20 44 45 4c 45 54 45 20 2a /* DELETE *
4e50: 2f 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 /. }.
4e60: 61 73 73 65 72 74 28 20 4d 5b 64 5d 5b 31 5d 3d assert( M[d][1]=
4e70: 3d 31 20 29 3b 0a 20 20 20 20 20 20 6e 20 3d 20 =1 );. n =
4e80: 31 3b 0a 20 20 20 20 20 20 77 68 69 6c 65 28 20 1;. while(
4e90: 4d 5b 64 5d 5b 30 5d 3d 3d 30 20 26 26 20 64 3c M[d][0]==0 && d<
4ea0: 44 20 26 26 20 4d 5b 64 2b 31 5d 5b 31 5d 3d 3d D && M[d+1][1]==
4eb0: 31 20 29 7b 0a 20 20 20 20 20 20 20 20 64 2b 2b 1 ){. d++
4ec0: 3b 0a 20 20 20 20 20 20 20 20 6e 2b 2b 3b 0a 20 ;. n++;.
4ed0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 52 5b 72 }. R[r
4ee0: 2b 2b 5d 20 3d 20 6e 3b 20 20 20 20 20 20 20 20 ++] = n;
4ef0: 20 20 20 20 2f 2a 20 49 4e 53 45 52 54 20 2a 2f /* INSERT */
4f00: 0a 20 20 20 20 7d 0a 20 20 20 20 52 5b 72 2b 2b . }. R[r++
4f10: 5d 20 3d 20 30 3b 0a 20 20 20 20 52 5b 72 2b 2b ] = 0;. R[r++
4f20: 5d 20 3d 20 30 3b 0a 20 20 20 20 52 5b 72 2b 2b ] = 0;. R[r++
4f30: 5d 20 3d 20 30 3b 0a 20 20 7d 0a 20 20 20 20 0a ] = 0;. }. .
4f40: 20 20 2f 2a 20 46 72 65 65 20 74 68 65 20 4d 79 /* Free the My
4f50: 65 72 73 20 6d 61 74 72 69 78 20 2a 2f 0a 20 20 ers matrix */.
4f60: 66 6f 72 28 64 3d 30 3b 20 64 3c 3d 44 3b 20 64 for(d=0; d<=D; d
4f70: 2b 2b 29 7b 0a 20 20 20 20 66 72 65 65 28 4d 5b ++){. free(M[
4f80: 64 5d 29 3b 0a 20 20 7d 0a 20 20 66 72 65 65 28 d]);. }. free(
4f90: 4d 29 3b 0a 0a 20 20 2f 2a 20 49 66 20 70 4f 75 M);.. /* If pOu
4fa0: 74 20 69 73 20 64 65 66 69 6e 65 64 2c 20 63 6f t is defined, co
4fb0: 6e 73 74 72 75 63 74 20 61 20 75 6e 69 66 69 65 nstruct a unifie
4fc0: 64 20 64 69 66 66 20 69 6e 74 6f 20 70 4f 75 74 d diff into pOut
4fd0: 20 61 6e 64 0a 20 20 2a 2a 20 64 65 6c 65 74 65 and. ** delete
4fe0: 20 52 0a 20 20 2a 2f 0a 20 20 69 66 28 20 70 4f R. */. if( pO
4ff0: 75 74 20 29 7b 0a 20 20 20 20 69 6e 74 20 61 20 ut ){. int a
5000: 3d 20 30 3b 20 20 20 20 2f 2a 20 49 6e 64 65 78 = 0; /* Index
5010: 20 6f 66 20 6e 65 78 74 20 6c 69 6e 65 20 69 6e of next line in
5020: 20 41 5b 5d 20 2a 2f 0a 20 20 20 20 69 6e 74 20 A[] */. int
5030: 62 20 3d 20 30 3b 20 20 20 20 2f 2a 20 49 6e 64 b = 0; /* Ind
5040: 65 78 20 6f 66 20 6e 65 78 74 20 6c 69 6e 65 20 ex of next line
5050: 69 6e 20 42 5b 5d 20 2a 2f 0a 20 20 20 20 69 6e in B[] */. in
5060: 74 20 6e 72 3b 20 20 20 20 20 20 20 2f 2a 20 4e t nr; /* N
5070: 75 6d 62 65 72 20 6f 66 20 43 4f 50 59 2f 44 45 umber of COPY/DE
5080: 4c 45 54 45 2f 49 4e 53 45 52 54 20 74 72 69 70 LETE/INSERT trip
5090: 6c 65 73 20 74 6f 20 70 72 6f 63 65 73 73 20 2a les to process *
50a0: 2f 0a 20 20 20 20 69 6e 74 20 6d 78 72 3b 20 20 /. int mxr;
50b0: 20 20 20 20 2f 2a 20 4d 61 78 69 6d 75 6d 20 76 /* Maximum v
50c0: 61 6c 75 65 20 66 6f 72 20 72 20 2a 2f 0a 20 20 alue for r */.
50d0: 20 20 69 6e 74 20 6e 61 2c 20 6e 62 3b 20 20 20 int na, nb;
50e0: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6c 69 6e /* Number of lin
50f0: 65 73 20 73 68 6f 77 6e 20 66 72 6f 6d 20 41 20 es shown from A
5100: 61 6e 64 20 42 20 2a 2f 0a 20 20 20 20 69 6e 74 and B */. int
5110: 20 69 2c 20 6a 3b 20 20 20 20 20 2f 2a 20 4c 6f i, j; /* Lo
5120: 6f 70 20 63 6f 75 6e 74 65 72 73 20 2a 2f 0a 20 op counters */.
5130: 20 20 20 69 6e 74 20 6d 3b 20 20 20 20 20 20 20 int m;
5140: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6c 69 /* Number of li
5150: 6e 65 73 20 74 6f 20 6f 75 74 70 75 74 20 2a 2f nes to output */
5160: 0a 20 20 20 20 69 6e 74 20 73 6b 69 70 3b 20 20 . int skip;
5170: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 /* Number of
5180: 6c 69 6e 65 73 20 74 6f 20 73 6b 69 70 20 2a 2f lines to skip */
5190: 0a 0a 20 20 20 20 66 6f 72 28 6d 78 72 3d 30 3b .. for(mxr=0;
51a0: 20 52 5b 6d 78 72 2b 31 5d 20 7c 7c 20 52 5b 6d R[mxr+1] || R[m
51b0: 78 72 2b 32 5d 20 7c 7c 20 52 5b 6d 78 72 2b 33 xr+2] || R[mxr+3
51c0: 5d 3b 20 6d 78 72 20 2b 3d 20 33 29 7b 7d 0a 20 ]; mxr += 3){}.
51d0: 20 20 20 66 6f 72 28 72 3d 30 3b 20 72 3c 6d 78 for(r=0; r<mx
51e0: 72 3b 20 72 20 2b 3d 20 33 2a 6e 72 29 7b 0a 20 r; r += 3*nr){.
51f0: 20 20 20 20 20 2f 2a 20 46 69 67 75 72 65 20 6f /* Figure o
5200: 75 74 20 68 6f 77 20 6d 61 6e 79 20 74 72 69 70 ut how many trip
5210: 6c 65 73 20 74 6f 20 73 68 6f 77 20 69 6e 20 61 les to show in a
5220: 20 73 69 6e 67 6c 65 20 62 6c 6f 63 6b 20 2a 2f single block */
5230: 0a 20 20 20 20 20 20 66 6f 72 28 6e 72 3d 31 3b . for(nr=1;
5240: 20 52 5b 72 2b 6e 72 2a 33 5d 3e 30 20 26 26 20 R[r+nr*3]>0 &&
5250: 52 5b 72 2b 6e 72 2a 33 5d 3c 6e 43 6f 6e 74 65 R[r+nr*3]<nConte
5260: 78 74 2a 32 3b 20 6e 72 2b 2b 29 7b 7d 0a 20 20 xt*2; nr++){}.
5270: 20 20 20 20 44 45 42 55 47 28 20 70 72 69 6e 74 DEBUG( print
5280: 66 28 22 72 3d 25 64 20 6e 72 3d 25 64 5c 6e 22 f("r=%d nr=%d\n"
5290: 2c 20 72 2c 20 6e 72 29 3b 20 29 0a 0a 20 20 20 , r, nr); )..
52a0: 20 20 20 2f 2a 20 46 6f 72 20 74 68 65 20 63 75 /* For the cu
52b0: 72 72 65 6e 74 20 62 6c 6f 63 6b 20 63 6f 6d 70 rrent block comp
52c0: 72 69 73 69 6e 67 20 6e 72 20 74 72 69 70 6c 65 rising nr triple
52d0: 73 2c 20 66 69 67 75 72 65 20 6f 75 74 0a 20 20 s, figure out.
52e0: 20 20 20 20 2a 2a 20 68 6f 77 20 6d 61 6e 79 20 ** how many
52f0: 6c 69 6e 65 73 20 6f 66 20 41 20 61 6e 64 20 42 lines of A and B
5300: 20 61 72 65 20 74 6f 20 62 65 20 64 69 73 70 6c are to be displ
5310: 61 79 65 64 0a 20 20 20 20 20 20 2a 2f 0a 20 20 ayed. */.
5320: 20 20 20 20 69 66 28 20 52 5b 72 5d 3e 6e 43 6f if( R[r]>nCo
5330: 6e 74 65 78 74 20 29 7b 0a 20 20 20 20 20 20 20 ntext ){.
5340: 20 6e 61 20 3d 20 6e 62 20 3d 20 6e 43 6f 6e 74 na = nb = nCont
5350: 65 78 74 3b 0a 20 20 20 20 20 20 20 20 73 6b 69 ext;. ski
5360: 70 20 3d 20 52 5b 72 5d 20 2d 20 6e 43 6f 6e 74 p = R[r] - nCont
5370: 65 78 74 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 ext;. }else
5380: 7b 0a 20 20 20 20 20 20 20 20 6e 61 20 3d 20 6e {. na = n
5390: 62 20 3d 20 52 5b 72 5d 3b 0a 20 20 20 20 20 20 b = R[r];.
53a0: 20 20 73 6b 69 70 20 3d 20 30 3b 0a 20 20 20 20 skip = 0;.
53b0: 20 20 7d 0a 20 20 20 20 20 20 66 6f 72 28 69 3d }. for(i=
53c0: 30 3b 20 69 3c 6e 72 3b 20 69 2b 2b 29 7b 0a 20 0; i<nr; i++){.
53d0: 20 20 20 20 20 20 20 6e 61 20 2b 3d 20 52 5b 72 na += R[r
53e0: 2b 69 2a 33 2b 31 5d 3b 0a 20 20 20 20 20 20 20 +i*3+1];.
53f0: 20 6e 62 20 2b 3d 20 52 5b 72 2b 69 2a 33 2b 32 nb += R[r+i*3+2
5400: 5d 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 ];. }.
5410: 20 69 66 28 20 52 5b 72 2b 6e 72 2a 33 5d 3e 6e if( R[r+nr*3]>n
5420: 43 6f 6e 74 65 78 74 20 29 7b 0a 20 20 20 20 20 Context ){.
5430: 20 20 20 6e 61 20 2b 3d 20 6e 43 6f 6e 74 65 78 na += nContex
5440: 74 3b 0a 20 20 20 20 20 20 20 20 6e 62 20 2b 3d t;. nb +=
5450: 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 20 20 20 20 nContext;.
5460: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 }else{.
5470: 6e 61 20 2b 3d 20 52 5b 72 2b 6e 72 2a 33 5d 3b na += R[r+nr*3];
5480: 0a 20 20 20 20 20 20 20 20 6e 62 20 2b 3d 20 52 . nb += R
5490: 5b 72 2b 6e 72 2a 33 5d 3b 0a 20 20 20 20 20 20 [r+nr*3];.
54a0: 7d 0a 20 20 20 20 20 20 66 6f 72 28 69 3d 31 3b }. for(i=1;
54b0: 20 69 3c 6e 72 3b 20 69 2b 2b 29 7b 0a 20 20 20 i<nr; i++){.
54c0: 20 20 20 20 20 6e 61 20 2b 3d 20 52 5b 72 2b 69 na += R[r+i
54d0: 2a 33 5d 3b 0a 20 20 20 20 20 20 20 20 6e 62 20 *3];. nb
54e0: 2b 3d 20 52 5b 72 2b 69 2a 33 5d 3b 0a 20 20 20 += R[r+i*3];.
54f0: 20 20 20 7d 0a 20 20 20 20 20 20 62 6c 6f 62 5f }. blob_
5500: 61 70 70 65 6e 64 66 28 70 4f 75 74 2c 22 40 40 appendf(pOut,"@@
5510: 20 2d 25 64 2c 25 64 20 2b 25 64 2c 25 64 20 40 -%d,%d +%d,%d @
5520: 40 5c 6e 22 2c 20 61 2b 73 6b 69 70 2b 31 2c 20 @\n", a+skip+1,
5530: 6e 61 2c 20 62 2b 73 6b 69 70 2b 31 2c 20 6e 62 na, b+skip+1, nb
5540: 29 3b 0a 0a 20 20 20 20 20 20 2f 2a 20 53 68 6f );.. /* Sho
5550: 77 20 74 68 65 20 69 6e 69 74 69 61 6c 20 63 6f w the initial co
5560: 6d 6d 6f 6e 20 61 72 65 61 20 2a 2f 0a 20 20 20 mmon area */.
5570: 20 20 20 61 20 2b 3d 20 73 6b 69 70 3b 0a 20 20 a += skip;.
5580: 20 20 20 20 62 20 2b 3d 20 73 6b 69 70 3b 0a 20 b += skip;.
5590: 20 20 20 20 20 6d 20 3d 20 52 5b 72 5d 20 2d 20 m = R[r] -
55a0: 73 6b 69 70 3b 0a 20 20 20 20 20 20 66 6f 72 28 skip;. for(
55b0: 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a j=0; j<m; j++){.
55c0: 20 20 20 20 20 20 20 20 61 70 70 65 6e 64 44 69 appendDi
55d0: 66 66 4c 69 6e 65 28 70 4f 75 74 2c 20 22 20 22 ffLine(pOut, " "
55e0: 2c 20 26 41 5b 61 2b 6a 5d 29 3b 0a 20 20 20 20 , &A[a+j]);.
55f0: 20 20 7d 0a 20 20 20 20 20 20 61 20 2b 3d 20 6d }. a += m
5600: 3b 0a 20 20 20 20 20 20 62 20 2b 3d 20 6d 3b 0a ;. b += m;.
5610: 0a 20 20 20 20 20 20 2f 2a 20 53 68 6f 77 20 74 . /* Show t
5620: 68 65 20 64 69 66 66 65 72 65 6e 63 65 73 20 2a he differences *
5630: 2f 0a 20 20 20 20 20 20 66 6f 72 28 69 3d 30 3b /. for(i=0;
5640: 20 69 3c 6e 72 3b 20 69 2b 2b 29 7b 0a 20 20 20 i<nr; i++){.
5650: 20 20 20 20 20 6d 20 3d 20 52 5b 72 2b 69 2a 33 m = R[r+i*3
5660: 2b 31 5d 3b 0a 20 20 20 20 20 20 20 20 66 6f 72 +1];. for
5670: 28 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b (j=0; j<m; j++){
5680: 0a 20 20 20 20 20 20 20 20 20 20 61 70 70 65 6e . appen
5690: 64 44 69 66 66 4c 69 6e 65 28 70 4f 75 74 2c 20 dDiffLine(pOut,
56a0: 22 2d 22 2c 20 26 41 5b 61 2b 6a 5d 29 3b 0a 20 "-", &A[a+j]);.
56b0: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 }.
56c0: 20 61 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 20 20 a += m;.
56d0: 20 6d 20 3d 20 52 5b 72 2b 69 2a 33 2b 32 5d 3b m = R[r+i*3+2];
56e0: 0a 20 20 20 20 20 20 20 20 66 6f 72 28 6a 3d 30 . for(j=0
56f0: 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 ; j<m; j++){.
5700: 20 20 20 20 20 20 20 61 70 70 65 6e 64 44 69 66 appendDif
5710: 66 4c 69 6e 65 28 70 4f 75 74 2c 20 22 2b 22 2c fLine(pOut, "+",
5720: 20 26 42 5b 62 2b 6a 5d 29 3b 0a 20 20 20 20 20 &B[b+j]);.
5730: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 62 20 2b }. b +
5740: 3d 20 6d 3b 0a 20 20 20 20 20 20 20 20 69 66 28 = m;. if(
5750: 20 69 3c 6e 72 2d 31 20 29 7b 0a 20 20 20 20 20 i<nr-1 ){.
5760: 20 20 20 20 20 6d 20 3d 20 52 5b 72 2b 69 2a 33 m = R[r+i*3
5770: 2b 33 5d 3b 0a 20 20 20 20 20 20 20 20 20 20 66 +3];. f
5780: 6f 72 28 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b or(j=0; j<m; j++
5790: 29 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 61 ){. a
57a0: 70 70 65 6e 64 44 69 66 66 4c 69 6e 65 28 70 4f ppendDiffLine(pO
57b0: 75 74 2c 20 22 20 22 2c 20 26 42 5b 62 2b 6a 5d ut, " ", &B[b+j]
57c0: 29 3b 0a 20 20 20 20 20 20 20 20 20 20 7d 0a 20 );. }.
57d0: 20 20 20 20 20 20 20 20 20 62 20 2b 3d 20 6d 3b b += m;
57e0: 0a 20 20 20 20 20 20 20 20 20 20 61 20 2b 3d 20 . a +=
57f0: 6d 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 m;. }.
5800: 20 20 20 7d 0a 0a 20 20 20 20 20 20 2f 2a 20 53 }.. /* S
5810: 68 6f 77 20 74 68 65 20 66 69 6e 61 6c 20 63 6f how the final co
5820: 6d 6d 6f 6e 20 61 72 65 61 20 2a 2f 0a 20 20 20 mmon area */.
5830: 20 20 20 61 73 73 65 72 74 28 20 6e 72 3d 3d 69 assert( nr==i
5840: 20 29 3b 0a 20 20 20 20 20 20 6d 20 3d 20 52 5b );. m = R[
5850: 72 2b 6e 72 2a 33 5d 3b 0a 20 20 20 20 20 20 69 r+nr*3];. i
5860: 66 28 20 6d 3e 6e 43 6f 6e 74 65 78 74 20 29 20 f( m>nContext )
5870: 6d 20 3d 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 20 m = nContext;.
5880: 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c 6d for(j=0; j<m
5890: 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 ; j++){.
58a0: 61 70 70 65 6e 64 44 69 66 66 4c 69 6e 65 28 70 appendDiffLine(p
58b0: 4f 75 74 2c 20 22 20 22 2c 20 26 42 5b 62 2b 6a Out, " ", &B[b+j
58c0: 5d 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 ]);. }.
58d0: 7d 0a 20 20 20 20 66 72 65 65 28 52 29 3b 0a 20 }. free(R);.
58e0: 20 20 20 52 20 3d 20 30 3b 0a 20 20 7d 0a 0a 20 R = 0;. }..
58f0: 20 2f 2a 20 57 65 20 6e 6f 20 6c 6f 6e 67 65 72 /* We no longer
5900: 20 6e 65 65 64 20 74 68 65 20 41 5b 5d 20 61 6e need the A[] an
5910: 64 20 42 5b 5d 20 76 65 63 74 6f 72 73 20 2a 2f d B[] vectors */
5920: 0a 20 20 66 72 65 65 28 41 29 3b 0a 20 20 66 72 . free(A);. fr
5930: 65 65 28 42 29 3b 0a 0a 20 20 2f 2a 20 52 65 74 ee(B);.. /* Ret
5940: 75 72 6e 20 74 68 65 20 72 65 73 75 6c 74 20 2a urn the result *
5950: 2f 0a 20 20 72 65 74 75 72 6e 20 52 3b 0a 7d 0a /. return R;.}.
5960: 23 65 6e 64 69 66 20 2f 2a 2a 2a 2a 2a 2a 2a 2a #endif /********
5970: 2a 2a 2a 2a 2a 2a 2a 2a 2a 20 45 6e 64 20 6f 66 ********* End of
5980: 20 74 68 65 20 57 61 67 6e 65 72 2f 4d 79 65 72 the Wagner/Myer
5990: 73 20 61 6c 67 6f 72 69 74 68 6d 20 2a 2a 2a 2a s algorithm ****
59a0: 2a 2a 2a 2a 2a 2a 2a 2a 2f 0a 0a 2f 2a 0a 2a 2a ********/../*.**
59b0: 20 43 4f 4d 4d 41 4e 44 3a 20 74 65 73 74 2d 72 COMMAND: test-r
59c0: 61 77 64 69 66 66 0a 2a 2f 0a 76 6f 69 64 20 74 awdiff.*/.void t
59d0: 65 73 74 5f 72 61 77 64 69 66 66 5f 63 6d 64 28 est_rawdiff_cmd(
59e0: 76 6f 69 64 29 7b 0a 20 20 42 6c 6f 62 20 61 2c void){. Blob a,
59f0: 20 62 3b 0a 20 20 69 6e 74 20 72 3b 0a 20 20 69 b;. int r;. i
5a00: 6e 74 20 69 3b 0a 20 20 69 6e 74 20 2a 52 3b 0a nt i;. int *R;.
5a10: 20 20 69 66 28 20 67 2e 61 72 67 63 3c 34 20 29 if( g.argc<4 )
5a20: 20 75 73 61 67 65 28 22 46 49 4c 45 31 20 46 49 usage("FILE1 FI
5a30: 4c 45 32 20 2e 2e 2e 22 29 3b 0a 20 20 62 6c 6f LE2 ...");. blo
5a40: 62 5f 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 b_read_from_file
5a50: 28 26 61 2c 20 67 2e 61 72 67 76 5b 32 5d 29 3b (&a, g.argv[2]);
5a60: 0a 20 20 66 6f 72 28 69 3d 33 3b 20 69 3c 67 2e . for(i=3; i<g.
5a70: 61 72 67 63 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 argc; i++){.
5a80: 69 66 28 20 69 3e 33 20 29 20 70 72 69 6e 74 66 if( i>3 ) printf
5a90: 28 22 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ("--------------
5aa0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5ab0: 2d 5c 6e 22 29 3b 0a 20 20 20 20 62 6c 6f 62 5f -\n");. blob_
5ac0: 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 read_from_file(&
5ad0: 62 2c 20 67 2e 61 72 67 76 5b 69 5d 29 3b 0a 20 b, g.argv[i]);.
5ae0: 20 20 20 52 20 3d 20 74 65 78 74 5f 64 69 66 66 R = text_diff
5af0: 28 26 61 2c 20 26 62 2c 20 30 2c 20 30 29 3b 0a (&a, &b, 0, 0);.
5b00: 20 20 20 20 66 6f 72 28 72 3d 30 3b 20 52 5b 72 for(r=0; R[r
5b10: 5d 20 7c 7c 20 52 5b 72 2b 31 5d 20 7c 7c 20 52 ] || R[r+1] || R
5b20: 5b 72 2b 32 5d 3b 20 72 20 2b 3d 20 33 29 7b 0a [r+2]; r += 3){.
5b30: 20 20 20 20 20 20 70 72 69 6e 74 66 28 22 20 63 printf(" c
5b40: 6f 70 79 20 25 34 64 20 20 64 65 6c 65 74 65 20 opy %4d delete
5b50: 25 34 64 20 20 69 6e 73 65 72 74 20 25 34 64 5c %4d insert %4d\
5b60: 6e 22 2c 20 52 5b 72 5d 2c 20 52 5b 72 2b 31 5d n", R[r], R[r+1]
5b70: 2c 20 52 5b 72 2b 32 5d 29 3b 0a 20 20 20 20 7d , R[r+2]);. }
5b80: 0a 20 20 20 20 2f 2a 20 66 72 65 65 28 52 29 3b . /* free(R);
5b90: 20 2a 2f 0a 20 20 20 20 62 6c 6f 62 5f 72 65 73 */. blob_res
5ba0: 65 74 28 26 62 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f et(&b);. }.}../
5bb0: 2a 0a 2a 2a 20 43 4f 4d 4d 41 4e 44 3a 20 74 65 *.** COMMAND: te
5bc0: 73 74 2d 75 64 69 66 66 0a 2a 2f 0a 76 6f 69 64 st-udiff.*/.void
5bd0: 20 74 65 73 74 5f 75 64 69 66 66 5f 63 6d 64 28 test_udiff_cmd(
5be0: 76 6f 69 64 29 7b 0a 20 20 42 6c 6f 62 20 61 2c void){. Blob a,
5bf0: 20 62 2c 20 6f 75 74 3b 0a 20 20 69 66 28 20 67 b, out;. if( g
5c00: 2e 61 72 67 63 21 3d 34 20 29 20 75 73 61 67 65 .argc!=4 ) usage
5c10: 28 22 46 49 4c 45 31 20 46 49 4c 45 32 22 29 3b ("FILE1 FILE2");
5c20: 0a 20 20 62 6c 6f 62 5f 72 65 61 64 5f 66 72 6f . blob_read_fro
5c30: 6d 5f 66 69 6c 65 28 26 61 2c 20 67 2e 61 72 67 m_file(&a, g.arg
5c40: 76 5b 32 5d 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 v[2]);. blob_re
5c50: 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 62 2c ad_from_file(&b,
5c60: 20 67 2e 61 72 67 76 5b 33 5d 29 3b 0a 20 20 62 g.argv[3]);. b
5c70: 6c 6f 62 5f 7a 65 72 6f 28 26 6f 75 74 29 3b 0a lob_zero(&out);.
5c80: 20 20 74 65 78 74 5f 64 69 66 66 28 26 61 2c 20 text_diff(&a,
5c90: 26 62 2c 20 26 6f 75 74 2c 20 33 29 3b 0a 20 20 &b, &out, 3);.
5ca0: 62 6c 6f 62 5f 77 72 69 74 65 5f 74 6f 5f 66 69 blob_write_to_fi
5cb0: 6c 65 28 26 6f 75 74 2c 20 22 2d 22 29 3b 0a 7d le(&out, "-");.}
5cc0: 0a .