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 32 2e 68 22 0a 23 69 6e de "diff2.h".#in
03e0: 63 6c 75 64 65 20 3c 61 73 73 65 72 74 2e 68 3e clude <assert.h>
03f0: 0a 0a 2f 2a 0a 2a 2a 20 49 6e 66 6f 72 6d 61 74 ../*.** Informat
0400: 69 6f 6e 20 61 62 6f 75 74 20 65 61 63 68 20 6c ion about each l
0410: 69 6e 65 20 6f 66 20 61 20 66 69 6c 65 20 62 65 ine of a file be
0420: 69 6e 67 20 64 69 66 66 65 64 2e 0a 2a 2f 0a 74 ing diffed..*/.t
0430: 79 70 65 64 65 66 20 73 74 72 75 63 74 20 44 4c ypedef struct DL
0440: 69 6e 65 20 44 4c 69 6e 65 3b 0a 73 74 72 75 63 ine DLine;.struc
0450: 74 20 44 4c 69 6e 65 20 7b 0a 20 20 63 6f 6e 73 t DLine {. cons
0460: 74 20 63 68 61 72 20 2a 7a 3b 20 20 20 20 2f 2a t char *z; /*
0470: 20 54 68 65 20 74 65 78 74 20 6f 66 20 74 68 65 The text of the
0480: 20 6c 69 6e 65 20 2a 2f 0a 20 20 75 6e 73 69 67 line */. unsig
0490: 6e 65 64 20 69 6e 74 20 68 3b 20 20 20 2f 2a 20 ned int h; /*
04a0: 48 61 73 68 20 6f 66 20 74 68 65 20 6c 69 6e 65 Hash of the line
04b0: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 42 72 */.};../*.** Br
04c0: 65 61 6b 20 61 20 62 6c 6f 62 20 69 6e 74 6f 20 eak a blob into
04d0: 6c 69 6e 65 73 20 62 79 20 63 6f 6e 76 65 72 74 lines by convert
04e0: 69 6e 67 20 69 6e 73 65 72 74 69 6e 67 20 5c 30 ing inserting \0
04f0: 30 30 20 63 68 61 72 61 63 74 65 72 73 2e 0a 2a 00 characters..*
0500: 2a 20 52 65 74 75 72 6e 20 61 6e 20 61 72 72 61 * Return an arra
0510: 79 20 6f 66 20 44 4c 69 6e 65 20 6f 62 6a 65 63 y of DLine objec
0520: 74 73 20 63 6f 6e 74 61 69 6e 69 6e 67 20 61 20 ts containing a
0530: 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 0a 2a pointer to the.*
0540: 2a 20 73 74 61 72 74 20 6f 66 20 65 61 63 68 20 * start of each
0550: 6c 69 6e 65 20 61 6e 64 20 61 20 68 61 73 68 20 line and a hash
0560: 6f 66 20 74 68 61 74 20 6c 69 6e 65 2e 0a 2a 2a of that line..**
0570: 0a 2a 2a 20 54 72 61 69 6c 69 6e 67 20 77 68 69 .** Trailing whi
0580: 74 65 73 70 61 63 65 20 69 73 20 72 65 6d 6f 76 tespace is remov
0590: 65 64 20 66 72 6f 6d 20 65 61 63 68 20 6c 69 6e ed from each lin
05a0: 65 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 44 4c 69 e..*/.static DLi
05b0: 6e 65 20 2a 62 72 65 61 6b 5f 69 6e 74 6f 5f 6c ne *break_into_l
05c0: 69 6e 65 73 28 63 68 61 72 20 2a 7a 2c 20 69 6e ines(char *z, in
05d0: 74 20 2a 70 6e 4c 69 6e 65 29 7b 0a 20 20 69 6e t *pnLine){. in
05e0: 74 20 6e 4c 69 6e 65 2c 20 69 2c 20 6a 2c 20 6b t nLine, i, j, k
05f0: 2c 20 78 3b 0a 20 20 75 6e 73 69 67 6e 65 64 20 , x;. unsigned
0600: 69 6e 74 20 68 3b 0a 20 20 44 4c 69 6e 65 20 2a int h;. DLine *
0610: 61 3b 0a 0a 20 20 2f 2a 20 43 6f 75 6e 74 20 74 a;.. /* Count t
0620: 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 6c 69 6e he number of lin
0630: 65 73 2e 20 20 41 6c 6c 6f 63 61 74 65 20 73 70 es. Allocate sp
0640: 61 63 65 20 74 6f 20 68 6f 6c 64 0a 20 20 2a 2a ace to hold. **
0650: 20 74 68 65 20 72 65 74 75 72 6e 65 64 20 61 72 the returned ar
0660: 72 61 79 2e 0a 20 20 2a 2f 0a 20 20 66 6f 72 28 ray.. */. for(
0670: 69 3d 30 2c 20 6e 4c 69 6e 65 3d 31 3b 20 7a 5b i=0, nLine=1; z[
0680: 69 5d 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 69 66 i]; i++){. if
0690: 28 20 7a 5b 69 5d 3d 3d 27 5c 6e 27 20 29 20 6e ( z[i]=='\n' ) n
06a0: 4c 69 6e 65 2b 2b 3b 0a 20 20 7d 0a 20 20 61 20 Line++;. }. a
06b0: 3d 20 6d 61 6c 6c 6f 63 28 20 6e 4c 69 6e 65 2a = malloc( nLine*
06c0: 73 69 7a 65 6f 66 28 61 5b 30 5d 29 20 29 3b 0a sizeof(a[0]) );.
06d0: 20 20 69 66 28 20 61 3d 3d 30 20 29 20 66 6f 73 if( a==0 ) fos
06e0: 73 69 6c 5f 70 61 6e 69 63 28 22 6f 75 74 20 6f sil_panic("out o
06f0: 66 20 6d 65 6d 6f 72 79 22 29 3b 0a 0a 20 20 2f f memory");.. /
0700: 2a 20 46 69 6c 6c 20 69 6e 20 74 68 65 20 61 72 * Fill in the ar
0710: 72 61 79 20 2a 2f 0a 20 20 66 6f 72 28 69 3d 30 ray */. for(i=0
0720: 3b 20 69 3c 6e 4c 69 6e 65 3b 20 69 2b 2b 29 7b ; i<nLine; i++){
0730: 0a 20 20 20 20 61 5b 69 5d 2e 7a 20 3d 20 7a 3b . a[i].z = z;
0740: 0a 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 7a 5b . for(j=0; z[
0750: 6a 5d 20 26 26 20 7a 5b 6a 5d 21 3d 27 5c 6e 27 j] && z[j]!='\n'
0760: 3b 20 6a 2b 2b 29 7b 7d 0a 20 20 20 20 66 6f 72 ; j++){}. for
0770: 28 6b 3d 6a 3b 20 6b 3e 30 20 26 26 20 69 73 73 (k=j; k>0 && iss
0780: 70 61 63 65 28 7a 5b 6b 2d 31 5d 29 3b 20 6b 2d pace(z[k-1]); k-
0790: 2d 29 7b 7d 0a 20 20 20 20 7a 5b 6b 5d 20 3d 20 -){}. z[k] =
07a0: 30 3b 0a 20 20 20 20 66 6f 72 28 68 3d 30 2c 20 0;. for(h=0,
07b0: 78 3d 30 3b 20 78 3c 6b 3b 20 78 2b 2b 29 7b 0a x=0; x<k; x++){.
07c0: 20 20 20 20 20 20 68 20 3d 20 68 20 5e 20 28 68 h = h ^ (h
07d0: 3c 3c 32 29 20 5e 20 7a 5b 78 5d 3b 0a 20 20 20 <<2) ^ z[x];.
07e0: 20 7d 0a 20 20 20 20 61 5b 69 5d 2e 68 20 3d 20 }. a[i].h =
07f0: 68 3b 0a 20 20 20 20 7a 20 2b 3d 20 6a 2b 31 3b h;. z += j+1;
0800: 0a 20 20 7d 0a 0a 20 20 2f 2a 20 52 65 74 75 72 . }.. /* Retur
0810: 6e 20 72 65 73 75 6c 74 73 20 2a 2f 0a 20 20 2a n results */. *
0820: 70 6e 4c 69 6e 65 20 3d 20 6e 4c 69 6e 65 3b 0a pnLine = nLine;.
0830: 20 20 72 65 74 75 72 6e 20 61 3b 0a 7d 0a 0a 2f return a;.}../
0840: 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 74 72 75 65 *.** Return true
0850: 20 69 66 20 74 77 6f 20 44 4c 69 6e 65 20 65 6c if two DLine el
0860: 65 6d 65 6e 74 73 20 61 72 65 20 69 64 65 6e 74 ements are ident
0870: 69 63 61 6c 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 ical..*/.static
0880: 69 6e 74 20 73 61 6d 65 5f 64 6c 69 6e 65 28 44 int same_dline(D
0890: 4c 69 6e 65 20 2a 70 41 2c 20 44 4c 69 6e 65 20 Line *pA, DLine
08a0: 2a 70 42 29 7b 0a 20 20 72 65 74 75 72 6e 20 70 *pB){. return p
08b0: 41 2d 3e 68 3d 3d 70 42 2d 3e 68 20 26 26 20 73 A->h==pB->h && s
08c0: 74 72 63 6d 70 28 70 41 2d 3e 7a 2c 70 42 2d 3e trcmp(pA->z,pB->
08d0: 7a 29 3d 3d 30 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 z)==0;.}../*.**
08e0: 47 65 6e 65 72 61 74 65 20 61 20 72 65 70 6f 72 Generate a repor
08f0: 74 20 6f 66 20 74 68 65 20 64 69 66 66 65 72 65 t of the differe
0900: 6e 63 65 73 20 62 65 74 77 65 65 6e 20 66 69 6c nces between fil
0910: 65 73 20 70 41 20 61 6e 64 20 70 42 2e 0a 2a 2a es pA and pB..**
0920: 20 54 68 65 20 6c 69 6e 65 20 65 6e 64 69 6e 67 The line ending
0930: 20 28 5c 72 5c 6e 20 76 65 72 73 75 73 20 5c 6e (\r\n versus \n
0940: 29 20 69 73 20 69 67 6e 6f 72 65 64 20 2d 20 74 ) is ignored - t
0950: 68 65 20 74 77 6f 20 6c 69 6e 65 0a 2a 2a 20 65 he two line.** e
0960: 6e 64 69 6e 67 73 20 61 72 65 20 63 6f 6e 73 69 ndings are consi
0970: 64 65 72 65 64 20 74 6f 20 62 65 20 65 71 75 69 dered to be equi
0980: 76 61 6c 65 6e 74 2e 0a 2a 2a 0a 2a 2a 20 54 68 valent..**.** Th
0990: 65 20 72 65 74 75 72 6e 20 69 73 20 61 20 70 6f e return is a po
09a0: 69 6e 74 65 72 20 74 6f 20 61 6e 20 61 72 72 61 inter to an arra
09b0: 79 20 6f 66 20 69 6e 74 65 67 65 72 73 20 74 68 y of integers th
09c0: 61 74 20 64 65 73 63 72 69 62 65 73 0a 2a 2a 20 at describes.**
09d0: 74 68 65 20 64 69 66 66 65 72 65 6e 63 65 2e 20 the difference.
09e0: 20 49 6e 74 65 67 65 72 73 20 63 6f 6d 65 20 69 Integers come i
09f0: 6e 20 74 72 69 70 6c 65 73 2e 20 20 46 6f 72 20 n triples. For
0a00: 65 61 63 68 20 74 72 69 70 6c 65 2c 0a 2a 2a 20 each triple,.**
0a10: 74 68 65 20 65 6c 65 6d 65 6e 74 73 20 61 72 65 the elements are
0a20: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 6c the number of l
0a30: 69 6e 65 73 20 63 6f 70 69 65 64 2c 20 74 68 65 ines copied, the
0a40: 20 6e 75 6d 62 65 72 20 6f 66 0a 2a 2a 20 6c 69 number of.** li
0a50: 6e 65 73 20 64 65 6c 65 74 65 2c 20 61 6e 64 20 nes delete, and
0a60: 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 6c 69 the number of li
0a70: 6e 65 73 20 69 6e 73 65 72 74 65 64 2e 20 20 54 nes inserted. T
0a80: 68 65 20 76 65 63 74 6f 72 0a 2a 2a 20 69 73 20 he vector.** is
0a90: 74 65 72 6d 69 6e 61 74 65 64 20 62 79 20 61 20 terminated by a
0aa0: 74 72 69 70 6c 65 20 6f 66 20 61 6c 6c 20 7a 65 triple of all ze
0ab0: 72 6f 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 74 ros..**.** The t
0ac0: 77 6f 20 62 6c 6f 62 73 20 69 73 20 64 65 73 74 wo blobs is dest
0ad0: 72 6f 79 65 64 20 28 27 5c 30 30 30 27 20 76 61 royed ('\000' va
0ae0: 6c 75 65 73 20 61 72 65 20 69 6e 73 65 72 74 65 lues are inserte
0af0: 64 29 0a 2a 2a 20 62 79 20 74 68 65 20 64 69 66 d).** by the dif
0b00: 66 69 6e 67 20 70 72 6f 63 65 73 73 2e 20 20 0a fing process. .
0b10: 2a 2a 0a 2a 2a 20 54 68 65 20 63 6f 72 65 20 61 **.** The core a
0b20: 6c 67 6f 72 69 74 68 6d 20 69 73 20 61 20 76 61 lgorithm is a va
0b30: 72 69 61 74 69 6f 6e 20 6f 6e 20 74 68 65 20 63 riation on the c
0b40: 6c 61 73 73 69 63 20 57 61 67 6e 65 72 0a 2a 2a lassic Wagner.**
0b50: 20 6d 69 6e 69 6d 75 6d 20 65 64 69 74 20 64 69 minimum edit di
0b60: 73 74 61 6e 63 65 20 77 69 74 68 20 65 6e 68 61 stance with enha
0b70: 6e 63 65 6d 65 6e 74 73 20 74 6f 20 72 65 64 75 ncements to redu
0b80: 63 65 20 74 68 65 20 72 75 6e 74 69 6d 65 0a 2a ce the runtime.*
0b90: 2a 20 74 6f 20 62 65 20 61 6c 6d 6f 73 74 20 6c * to be almost l
0ba0: 69 6e 65 61 72 20 69 6e 20 74 68 65 20 63 6f 6d inear in the com
0bb0: 6d 6f 6e 20 63 61 73 65 20 77 68 65 72 65 20 74 mon case where t
0bc0: 68 65 20 74 77 6f 20 66 69 6c 65 73 0a 2a 2a 20 he two files.**
0bd0: 68 61 76 65 20 61 20 6c 6f 74 20 69 6e 20 63 6f have a lot in co
0be0: 6d 6d 6f 6e 2e 20 20 46 6f 72 20 61 64 64 69 74 mmon. For addit
0bf0: 69 6f 6e 61 6c 20 69 6e 66 6f 72 6d 61 74 69 6f ional informatio
0c00: 6e 20 73 65 65 0a 2a 2a 20 45 75 67 65 6e 65 20 n see.** Eugene
0c10: 57 2e 20 4d 79 65 72 73 2c 20 22 41 6e 20 4f 28 W. Myers, "An O(
0c20: 4e 44 29 20 44 69 66 66 65 72 65 6e 63 65 20 41 ND) Difference A
0c30: 6c 67 6f 72 69 74 68 6d 20 41 6e 64 20 49 74 73 lgorithm And Its
0c40: 0a 2a 2a 20 56 61 72 69 61 74 69 6f 6e 73 22 0a .** Variations".
0c50: 2a 2a 0a 2a 2a 20 43 6f 6e 73 69 64 65 72 20 63 **.** Consider c
0c60: 6f 6d 70 61 72 69 6e 67 20 73 74 72 69 6e 67 73 omparing strings
0c70: 20 41 20 61 6e 64 20 42 2e 20 20 41 3d 61 62 63 A and B. A=abc
0c80: 61 62 62 61 20 61 6e 64 20 42 3d 63 62 61 62 61 abba and B=cbaba
0c90: 63 0a 2a 2a 20 57 65 20 63 6f 6e 73 74 72 75 63 c.** We construc
0ca0: 74 20 61 20 22 57 61 67 6e 65 72 22 20 6d 61 74 t a "Wagner" mat
0cb0: 72 69 78 20 57 20 77 69 74 68 20 41 20 61 6c 6f rix W with A alo
0cc0: 6e 67 20 74 68 65 20 58 20 61 78 69 73 20 61 6e ng the X axis an
0cd0: 64 20 0a 2a 2a 20 42 20 61 6c 6f 6e 67 20 74 68 d .** B along th
0ce0: 65 20 59 20 61 78 69 73 3a 0a 2a 2a 0a 2a 2a 20 e Y axis:.**.**
0cf0: 20 20 20 20 63 20 36 20 20 20 20 20 20 20 20 20 c 6
0d00: 20 20 20 20 20 20 2a 0a 2a 2a 20 20 20 20 20 61 *.** a
0d10: 20 35 20 20 20 20 20 20 20 20 20 20 20 20 20 20 5
0d20: 20 2a 0a 2a 2a 20 20 20 20 20 62 20 34 20 20 20 *.** b 4
0d30: 20 20 20 20 20 20 20 20 2a 20 2a 0a 2a 2a 20 20 * *.**
0d40: 20 20 20 61 20 33 20 20 20 20 20 20 20 20 20 2a a 3 *
0d50: 0a 2a 2a 20 20 20 20 20 62 20 32 20 20 20 20 20 .** b 2
0d60: 20 20 2a 0a 2a 2a 20 20 20 42 20 63 20 31 20 20 *.** B c 1
0d70: 20 20 20 20 20 2a 0a 2a 2a 20 20 20 20 20 20 20 *.**
0d80: 30 20 2a 20 2a 20 2a 20 0a 2a 2a 20 20 20 20 20 0 * * * .**
0d90: 20 20 20 20 30 20 31 20 32 20 33 20 34 20 35 20 0 1 2 3 4 5
0da0: 36 20 37 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 6 7.**
0db0: 20 61 20 62 20 63 20 61 20 62 20 62 20 61 0a 2a a b c a b b a.*
0dc0: 2a 20 20 20 20 20 20 20 20 20 20 20 41 0a 2a 2a * A.**
0dd0: 0a 2a 2a 20 28 4e 6f 74 65 3a 20 77 65 20 64 72 .** (Note: we dr
0de0: 61 77 20 74 68 69 73 20 57 61 67 6e 65 72 20 6d aw this Wagner m
0df0: 61 74 72 69 78 20 77 69 74 68 20 74 68 65 20 6f atrix with the o
0e00: 72 69 67 69 6e 20 61 74 20 74 68 65 20 6c 6f 77 rigin at the low
0e10: 65 72 20 0a 2a 2a 20 6c 65 66 74 20 77 68 65 72 er .** left wher
0e20: 65 61 73 20 4d 79 65 72 73 20 75 73 65 73 20 74 eas Myers uses t
0e30: 68 65 20 6f 72 69 67 69 6e 20 61 74 20 74 68 65 he origin at the
0e40: 20 75 70 70 65 72 20 6c 65 66 74 2e 20 20 4f 74 upper left. Ot
0e50: 68 65 72 77 69 73 65 2c 0a 2a 2a 20 74 68 65 79 herwise,.** they
0e60: 20 61 72 65 20 74 68 65 20 73 61 6d 65 2e 29 0a are the same.).
0e70: 2a 2a 0a 2a 2a 20 4c 65 74 20 59 20 62 65 20 74 **.** Let Y be t
0e80: 68 65 20 6d 61 78 69 6d 75 6d 20 79 20 76 61 6c he maximum y val
0e90: 75 65 20 6f 72 20 74 68 65 20 6e 75 6d 62 65 72 ue or the number
0ea0: 20 6f 66 20 63 68 61 72 61 63 74 65 72 73 20 69 of characters i
0eb0: 6e 20 42 2e 0a 2a 2a 20 36 20 69 6e 20 74 68 69 n B..** 6 in thi
0ec0: 73 20 65 78 61 6d 70 6c 65 2e 20 20 58 20 69 73 s example. X is
0ed0: 20 74 68 65 20 6d 61 78 69 6d 75 6d 20 78 20 76 the maximum x v
0ee0: 61 6c 75 65 20 6f 72 20 74 68 65 20 6e 75 6d 62 alue or the numb
0ef0: 65 72 20 6f 66 0a 2a 2a 20 65 6c 65 6d 65 6e 74 er of.** element
0f00: 73 20 69 6e 20 41 2e 20 20 48 65 72 65 20 37 2e s in A. Here 7.
0f10: 0a 2a 2a 0a 2a 2a 20 4f 75 72 20 67 6f 61 6c 20 .**.** Our goal
0f20: 69 73 20 74 6f 20 66 69 6e 64 20 61 20 70 61 74 is to find a pat
0f30: 68 20 66 72 6f 6d 20 28 30 2c 30 29 20 74 6f 20 h from (0,0) to
0f40: 28 58 2c 59 29 2e 20 20 54 68 65 20 70 61 74 68 (X,Y). The path
0f50: 20 63 61 6e 0a 2a 2a 20 75 73 65 20 68 6f 72 69 can.** use hori
0f60: 7a 6f 6e 74 61 6c 2c 20 76 65 72 74 69 63 61 6c zontal, vertical
0f70: 2c 20 6f 72 20 64 69 61 67 6f 6e 61 6c 20 73 74 , or diagonal st
0f80: 65 70 73 2e 20 20 41 20 64 69 61 67 6f 6e 61 6c eps. A diagonal
0f90: 20 66 72 6f 6d 0a 2a 2a 20 28 78 2d 31 2c 79 2d from.** (x-1,y-
0fa0: 31 29 20 74 6f 20 28 78 2c 79 29 20 69 73 20 6f 1) to (x,y) is o
0fb0: 6e 6c 79 20 61 6c 6c 6f 77 65 64 20 69 66 20 41 nly allowed if A
0fc0: 5b 78 5d 3d 3d 42 5b 79 5d 2e 20 20 41 20 76 65 [x]==B[y]. A ve
0fd0: 72 74 69 63 61 6c 0a 2a 2a 20 73 74 65 70 73 20 rtical.** steps
0fe0: 63 6f 72 72 65 73 70 6f 6e 64 73 20 74 6f 20 61 corresponds to a
0ff0: 6e 20 69 6e 73 65 72 74 69 6f 6e 2e 20 20 41 20 n insertion. A
1000: 68 6f 72 69 7a 6f 6e 74 61 6c 20 73 74 65 70 20 horizontal step
1010: 63 6f 72 72 65 73 70 6f 6e 64 73 0a 2a 2a 20 74 corresponds.** t
1020: 6f 20 61 20 64 65 6c 65 74 69 6f 6e 2e 20 20 57 o a deletion. W
1030: 65 20 77 61 6e 74 20 74 6f 20 66 69 6e 64 20 74 e want to find t
1040: 68 65 20 70 61 74 68 20 77 69 74 68 20 74 68 65 he path with the
1050: 20 66 65 77 65 73 74 0a 2a 2a 20 68 6f 72 69 7a fewest.** horiz
1060: 6f 6e 74 61 6c 20 61 6e 64 20 76 65 72 74 69 63 ontal and vertic
1070: 61 6c 20 73 74 65 70 73 2e 0a 2a 2a 0a 2a 2a 20 al steps..**.**
1080: 44 69 61 67 6f 6e 61 6c 20 6b 20 63 6f 6e 73 69 Diagonal k consi
1090: 73 74 73 20 6f 66 20 61 6c 6c 20 70 6f 69 6e 74 sts of all point
10a0: 73 20 73 75 63 68 20 74 68 61 74 20 78 2d 79 3d s such that x-y=
10b0: 3d 6b 2e 20 20 44 69 61 67 6f 6e 61 6c 0a 2a 2a =k. Diagonal.**
10c0: 20 7a 65 72 6f 20 62 65 67 69 6e 73 20 61 74 20 zero begins at
10d0: 74 68 65 20 6f 72 69 67 69 6e 2e 20 20 44 69 61 the origin. Dia
10e0: 67 6f 6e 61 6c 20 31 20 62 65 67 69 6e 73 20 61 gonal 1 begins a
10f0: 74 20 28 31 2c 30 29 2e 20 20 0a 2a 2a 20 44 69 t (1,0). .** Di
1100: 61 67 6f 6e 61 6c 20 2d 31 20 62 65 67 69 6e 73 agonal -1 begins
1110: 20 61 74 20 28 30 2c 31 29 2e 20 20 41 6c 6c 20 at (0,1). All
1120: 64 69 61 67 6f 6e 61 6c 73 20 6d 6f 76 65 20 75 diagonals move u
1130: 70 20 61 6e 64 20 74 6f 20 74 68 65 0a 2a 2a 20 p and to the.**
1140: 72 69 67 68 74 20 61 74 20 34 35 20 64 65 67 72 right at 45 degr
1150: 65 65 73 2e 20 20 44 69 61 67 6f 6e 61 6c 20 6e ees. Diagonal n
1160: 75 6d 62 65 72 20 69 6e 63 72 65 61 73 65 20 66 umber increase f
1170: 72 6f 6d 20 75 70 70 65 72 20 6c 65 66 74 0a 2a rom upper left.*
1180: 2a 20 74 6f 20 6c 6f 77 65 72 20 72 69 67 68 74 * to lower right
1190: 2e 0a 2a 2a 20 0a 2a 2a 20 4d 79 65 72 73 20 6d ..** .** Myers m
11a0: 61 74 72 69 78 20 4d 20 69 73 20 61 20 6c 6f 77 atrix M is a low
11b0: 65 72 20 72 69 67 68 74 20 74 72 69 61 6e 67 75 er right triangu
11c0: 6c 61 72 20 6d 61 74 72 69 78 20 77 69 74 68 20 lar matrix with
11d0: 69 6e 64 69 63 65 73 20 64 0a 2a 2a 20 61 6c 6f indices d.** alo
11e0: 6e 67 20 74 68 65 20 62 6f 74 74 6f 6d 20 61 6e ng the bottom an
11f0: 64 20 69 20 76 65 72 74 69 63 61 6c 6c 79 3a 0a d i vertically:.
1200: 2a 2a 0a 2a 2a 20 0a 2a 2a 20 20 20 69 3d 34 20 **.** .** i=4
1210: 7c 20 20 20 20 20 20 20 20 20 20 20 20 2b 34 20 | +4
1220: 20 5c 0a 2a 2a 20 20 20 20 20 33 20 7c 20 20 20 \.** 3 |
1230: 20 20 20 20 20 20 2b 33 20 2b 32 20 20 20 7c 0a +3 +2 |.
1240: 2a 2a 20 20 20 20 20 32 20 7c 20 20 20 20 20 20 ** 2 |
1250: 2b 32 20 2b 31 20 20 30 20 20 20 7c 2d 20 6b 20 +2 +1 0 |- k
1260: 76 61 6c 75 65 73 2e 20 20 20 6b 20 3d 20 32 2a values. k = 2*
1270: 69 2d 64 0a 2a 2a 20 20 20 20 20 31 20 7c 20 20 i-d.** 1 |
1280: 20 2b 31 20 20 30 20 2d 31 20 2d 32 20 20 20 7c +1 0 -1 -2 |
1290: 0a 2a 2a 20 20 20 20 20 30 20 7c 20 30 20 2d 31 .** 0 | 0 -1
12a0: 20 2d 32 20 2d 33 20 2d 34 20 20 2f 0a 2a 2a 20 -2 -3 -4 /.**
12b0: 20 20 20 20 20 20 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------
12c0: 2d 2d 2d 2d 2d 0a 2a 2a 20 20 20 20 20 20 20 20 -----.**
12d0: 20 30 20 20 31 20 20 32 20 20 33 20 20 34 20 3d 0 1 2 3 4 =
12e0: 20 64 0a 2a 2a 0a 2a 2a 20 45 61 63 68 20 65 6c d.**.** Each el
12f0: 65 6d 65 6e 74 20 6f 66 20 74 68 65 20 4d 79 65 ement of the Mye
1300: 72 73 20 6d 61 74 72 69 78 20 63 6f 72 72 65 73 rs matrix corres
1310: 70 6f 6e 64 73 20 74 6f 20 61 20 64 69 61 67 6f ponds to a diago
1320: 6e 61 6c 2e 0a 2a 2a 20 54 68 65 20 64 69 61 67 nal..** The diag
1330: 6f 6e 61 6c 20 69 73 20 6b 3d 32 2a 69 2d 64 2e onal is k=2*i-d.
1340: 20 20 54 68 65 20 64 69 61 67 6f 6e 61 6c 20 76 The diagonal v
1350: 61 6c 75 65 73 20 61 72 65 20 73 68 6f 77 6e 0a alues are shown.
1360: 2a 2a 20 69 6e 20 74 68 65 20 74 65 6d 70 6c 61 ** in the templa
1370: 74 65 20 61 62 6f 76 65 2e 0a 2a 2a 0a 2a 2a 20 te above..**.**
1380: 45 61 63 68 20 65 6e 74 72 79 20 69 6e 20 4d 20 Each entry in M
1390: 72 65 70 72 65 73 65 6e 74 73 20 74 68 65 20 65 represents the e
13a0: 6e 64 2d 70 6f 69 6e 74 20 6f 6e 20 61 20 70 61 nd-point on a pa
13b0: 74 68 20 66 72 6f 6d 20 28 30 2c 30 29 2e 0a 2a th from (0,0)..*
13c0: 2a 20 54 68 65 20 65 6e 64 2d 70 6f 69 6e 74 20 * The end-point
13d0: 69 73 20 6f 6e 20 64 69 61 67 6f 6e 61 6c 20 6b is on diagonal k
13e0: 2e 20 20 54 68 65 20 76 61 6c 75 65 20 73 74 6f . The value sto
13f0: 72 65 64 20 69 6e 20 4d 20 69 73 0a 2a 2a 20 71 red in M is.** q
1400: 3d 78 2b 79 20 77 68 65 72 65 20 28 78 2c 79 29 =x+y where (x,y)
1410: 20 69 73 20 74 68 65 20 74 65 72 6d 69 6e 75 73 is the terminus
1420: 20 6f 66 20 74 68 65 20 70 61 74 68 2e 20 20 41 of the path. A
1430: 20 70 61 74 68 0a 2a 2a 20 74 6f 20 4d 5b 64 5d path.** to M[d]
1440: 5b 69 5d 20 77 69 6c 6c 20 63 6f 6d 65 20 74 68 [i] will come th
1450: 72 6f 75 67 68 20 65 69 74 68 65 72 20 4d 5b 64 rough either M[d
1460: 2d 31 5d 5b 69 2d 31 5d 20 6f 72 0a 2a 2a 20 74 -1][i-1] or.** t
1470: 68 6f 75 67 68 20 4d 5b 64 2d 31 5d 5b 69 5d 2c hough M[d-1][i],
1480: 20 77 68 69 63 68 65 76 65 72 20 68 6f 6c 64 73 whichever holds
1490: 20 74 68 65 20 6c 61 72 67 65 73 74 20 76 61 6c the largest val
14a0: 75 65 20 6f 66 20 71 2e 0a 2a 2a 20 49 66 20 62 ue of q..** If b
14b0: 6f 74 68 20 65 6c 65 6d 65 6e 74 73 20 68 6f 6c oth elements hol
14c0: 64 20 74 68 65 20 73 61 6d 65 20 76 61 6c 75 65 d the same value
14d0: 2c 20 74 68 65 20 70 61 74 68 20 63 6f 6d 65 73 , the path comes
14e0: 0a 2a 2a 20 74 68 72 6f 75 67 68 20 4d 5b 64 2d .** through M[d-
14f0: 31 5d 5b 69 2d 31 5d 2e 0a 2a 2a 0a 2a 2a 20 54 1][i-1]..**.** T
1500: 68 65 20 76 61 6c 75 65 20 6f 66 20 64 20 69 73 he value of d is
1510: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 69 the number of i
1520: 6e 73 65 72 74 69 6f 6e 73 20 61 6e 64 20 64 65 nsertions and de
1530: 6c 65 74 69 6f 6e 73 0a 2a 2a 20 6d 61 64 65 20 letions.** made
1540: 73 6f 20 66 61 72 20 6f 6e 20 74 68 65 20 70 61 so far on the pa
1550: 74 68 2e 20 20 4d 20 67 72 6f 77 73 20 70 72 6f th. M grows pro
1560: 67 72 65 73 73 69 76 65 6c 79 2e 20 20 53 6f 20 gressively. So
1570: 74 68 65 0a 2a 2a 20 73 69 7a 65 20 6f 66 20 74 the.** size of t
1580: 68 65 20 4d 20 6d 61 74 72 69 78 20 69 73 20 70 he M matrix is p
1590: 72 6f 70 6f 72 74 69 6f 6e 61 6c 20 74 6f 20 64 roportional to d
15a0: 2a 64 2e 20 20 46 6f 72 20 74 68 65 0a 2a 2a 20 *d. For the.**
15b0: 63 6f 6d 6d 6f 6e 20 63 61 73 65 20 77 68 65 72 common case wher
15c0: 65 20 41 20 61 6e 64 20 42 20 61 72 65 20 73 69 e A and B are si
15d0: 6d 69 6c 61 72 2c 20 64 20 77 69 6c 6c 20 62 65 milar, d will be
15e0: 20 73 6d 61 6c 6c 0a 2a 2a 20 63 6f 6d 70 61 72 small.** compar
15f0: 65 64 20 74 6f 20 58 20 61 6e 64 20 59 20 73 6f ed to X and Y so
1600: 20 6c 69 74 74 6c 65 20 6d 65 6d 6f 72 79 20 69 little memory i
1610: 73 20 72 65 71 75 69 72 65 64 2e 20 20 54 68 65 s required. The
1620: 0a 2a 2a 20 6f 72 69 67 69 6e 61 6c 20 57 61 67 .** original Wag
1630: 6e 65 72 20 61 6c 67 6f 72 69 74 68 6d 20 72 65 ner algorithm re
1640: 71 75 69 72 65 73 20 58 2a 59 20 6d 65 6d 6f 72 quires X*Y memor
1650: 79 2c 20 77 68 69 63 68 20 66 6f 72 0a 2a 2a 20 y, which for.**
1660: 6c 61 72 67 65 72 20 66 69 6c 65 73 20 28 31 30 larger files (10
1670: 30 4b 20 6c 69 6e 65 73 29 20 69 73 20 6d 6f 72 0K lines) is mor
1680: 65 20 6d 65 6d 6f 72 79 20 74 68 61 6e 20 77 65 e memory than we
1690: 20 68 61 76 65 20 61 74 0a 2a 2a 20 68 61 6e 64 have at.** hand
16a0: 2e 0a 2a 2f 0a 69 6e 74 20 2a 74 65 78 74 5f 64 ..*/.int *text_d
16b0: 69 66 66 28 42 6c 6f 62 20 2a 70 41 5f 42 6c 6f iff(Blob *pA_Blo
16c0: 62 2c 20 42 6c 6f 62 20 2a 70 42 5f 42 6c 6f 62 b, Blob *pB_Blob
16d0: 2c 20 42 6c 6f 62 20 2a 70 4f 75 74 2c 20 69 6e , Blob *pOut, in
16e0: 74 20 6e 43 6f 6e 74 65 78 74 29 7b 0a 20 20 44 t nContext){. D
16f0: 4c 69 6e 65 20 2a 41 2c 20 2a 42 3b 20 20 20 20 Line *A, *B;
1700: 2f 2a 20 46 69 6c 65 73 20 62 65 69 6e 67 20 63 /* Files being c
1710: 6f 6d 70 61 72 65 64 20 2a 2f 0a 20 20 69 6e 74 ompared */. int
1720: 20 58 2c 20 59 3b 20 20 20 20 20 20 20 20 2f 2a X, Y; /*
1730: 20 4e 75 6d 62 65 72 20 6f 66 20 65 6c 65 6d 65 Number of eleme
1740: 6e 74 73 20 69 6e 20 41 20 61 6e 64 20 42 20 2a nts in A and B *
1750: 2f 0a 20 20 69 6e 74 20 78 2c 20 79 3b 20 20 20 /. int x, y;
1760: 20 20 20 20 20 2f 2a 20 49 6e 64 69 63 65 73 3a /* Indices:
1770: 20 20 41 5b 78 5d 20 61 6e 64 20 42 5b 79 5d 20 A[x] and B[y]
1780: 2a 2f 0a 20 20 69 6e 74 20 73 7a 4d 20 3d 20 30 */. int szM = 0
1790: 3b 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 ; /* Number
17a0: 6f 66 20 72 6f 77 73 20 61 6e 64 20 63 6f 6c 75 of rows and colu
17b0: 6d 6e 73 20 69 6e 20 4d 20 2a 2f 0a 20 20 69 6e mns in M */. in
17c0: 74 20 2a 2a 4d 20 3d 20 30 3b 20 20 20 20 20 2f t **M = 0; /
17d0: 2a 20 4d 79 65 72 73 20 6d 61 74 72 69 78 20 2a * Myers matrix *
17e0: 2f 0a 20 20 69 6e 74 20 69 2c 20 64 3b 20 20 20 /. int i, d;
17f0: 20 20 20 20 20 2f 2a 20 49 6e 64 69 63 65 73 20 /* Indices
1800: 6f 6e 20 4d 2e 20 20 4d 5b 64 5d 5b 69 5d 20 2a on M. M[d][i] *
1810: 2f 0a 20 20 69 6e 74 20 6b 2c 20 71 3b 20 20 20 /. int k, q;
1820: 20 20 20 20 20 2f 2a 20 44 69 61 67 6f 6e 61 6c /* Diagonal
1830: 20 6e 75 6d 62 65 72 20 61 6e 64 20 64 69 73 74 number and dist
1840: 69 6e 63 74 20 66 72 6f 6d 20 28 30 2c 30 29 20 inct from (0,0)
1850: 2a 2f 0a 20 20 69 6e 74 20 4b 2c 20 44 3b 20 20 */. int K, D;
1860: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 64 69 61 /* The dia
1870: 67 6f 6e 61 6c 20 61 6e 64 20 64 20 66 6f 72 20 gonal and d for
1880: 74 68 65 20 66 69 6e 61 6c 20 73 6f 6c 75 74 69 the final soluti
1890: 6f 6e 20 2a 2f 20 20 20 20 20 20 20 20 20 20 0a on */ .
18a0: 20 20 69 6e 74 20 2a 52 3b 20 20 20 20 20 20 20 int *R;
18b0: 20 20 20 2f 2a 20 52 65 73 75 6c 74 20 76 65 63 /* Result vec
18c0: 74 6f 72 20 2a 2f 0a 20 20 69 6e 74 20 72 3b 20 tor */. int r;
18d0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4c 6f 6f /* Loo
18e0: 70 20 76 61 72 69 61 62 6c 65 73 20 2a 2f 0a 20 p variables */.
18f0: 20 69 6e 74 20 67 6f 20 3d 20 31 3b 20 20 20 20 int go = 1;
1900: 20 20 2f 2a 20 4f 75 74 65 72 20 6c 6f 6f 70 20 /* Outer loop
1910: 63 6f 6e 74 72 6f 6c 20 2a 2f 0a 0a 20 20 2f 2a control */.. /*
1920: 20 42 72 65 61 6b 20 74 68 65 20 74 77 6f 20 66 Break the two f
1930: 69 6c 65 73 20 62 65 69 6e 67 20 64 69 66 66 65 iles being diffe
1940: 64 20 69 6e 74 6f 20 69 6e 64 69 76 69 64 75 61 d into individua
1950: 6c 20 6c 69 6e 65 73 2e 0a 20 20 2a 2a 20 43 6f l lines.. ** Co
1960: 6d 70 75 74 65 20 68 61 73 68 65 73 20 6f 6e 20 mpute hashes on
1970: 65 61 63 68 20 6c 69 6e 65 20 66 6f 72 20 66 61 each line for fa
1980: 73 74 20 63 6f 6d 70 61 72 69 73 6f 6e 2e 0a 20 st comparison..
1990: 20 2a 2f 0a 20 20 41 20 3d 20 62 72 65 61 6b 5f */. A = break_
19a0: 69 6e 74 6f 5f 6c 69 6e 65 73 28 62 6c 6f 62 5f into_lines(blob_
19b0: 73 74 72 28 70 41 5f 42 6c 6f 62 29 2c 20 26 58 str(pA_Blob), &X
19c0: 29 3b 0a 20 20 42 20 3d 20 62 72 65 61 6b 5f 69 );. B = break_i
19d0: 6e 74 6f 5f 6c 69 6e 65 73 28 62 6c 6f 62 5f 73 nto_lines(blob_s
19e0: 74 72 28 70 42 5f 42 6c 6f 62 29 2c 20 26 59 29 tr(pB_Blob), &Y)
19f0: 3b 0a 0a 20 20 73 7a 4d 20 3d 20 30 3b 0a 20 20 ;.. szM = 0;.
1a00: 66 6f 72 28 64 3d 30 3b 20 67 6f 3b 20 64 2b 2b for(d=0; go; d++
1a10: 29 7b 0a 20 20 20 20 69 66 28 20 73 7a 4d 3c 64 ){. if( szM<d
1a20: 2b 31 20 29 7b 0a 20 20 20 20 20 20 73 7a 4d 20 +1 ){. szM
1a30: 2b 3d 20 73 7a 4d 20 2b 20 31 30 3b 0a 20 20 20 += szM + 10;.
1a40: 20 20 20 4d 20 3d 20 72 65 61 6c 6c 6f 63 28 4d M = realloc(M
1a50: 2c 20 73 69 7a 65 6f 66 28 4d 5b 30 5d 29 2a 73 , sizeof(M[0])*s
1a60: 7a 4d 29 3b 0a 20 20 20 20 20 20 69 66 28 20 4d zM);. if( M
1a70: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 20 20 66 ==0 ){. f
1a80: 6f 73 73 69 6c 5f 70 61 6e 69 63 28 22 6f 75 74 ossil_panic("out
1a90: 20 6f 66 20 6d 65 6d 6f 72 79 22 29 3b 0a 20 20 of memory");.
1aa0: 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 }. }.
1ab0: 4d 5b 64 5d 20 3d 20 6d 61 6c 6c 6f 63 28 20 73 M[d] = malloc( s
1ac0: 69 7a 65 6f 66 28 4d 5b 64 5d 5b 30 5d 29 2a 28 izeof(M[d][0])*(
1ad0: 64 2b 31 29 20 29 3b 0a 20 20 20 20 69 66 28 20 d+1) );. if(
1ae0: 4d 5b 64 5d 3d 3d 30 20 29 7b 0a 20 20 20 20 20 M[d]==0 ){.
1af0: 20 66 6f 73 73 69 6c 5f 70 61 6e 69 63 28 22 6f fossil_panic("o
1b00: 75 74 20 6f 66 20 6d 65 6d 6f 72 79 22 29 3b 0a ut of memory");.
1b10: 20 20 20 20 7d 0a 20 20 20 20 66 6f 72 28 69 3d }. for(i=
1b20: 30 3b 20 69 3c 3d 64 3b 20 69 2b 2b 29 7b 0a 20 0; i<=d; i++){.
1b30: 20 20 20 20 20 6b 20 3d 20 32 2a 69 20 2d 20 64 k = 2*i - d
1b40: 3b 0a 20 20 20 20 20 20 69 66 28 20 64 3d 3d 30 ;. if( d==0
1b50: 20 29 7b 0a 20 20 20 20 20 20 20 20 71 20 3d 20 ){. q =
1b60: 30 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 20 69 0;. }else i
1b70: 66 28 20 69 3d 3d 30 20 29 7b 0a 20 20 20 20 20 f( i==0 ){.
1b80: 20 20 20 71 20 3d 20 4d 5b 64 2d 31 5d 5b 30 5d q = M[d-1][0]
1b90: 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 20 69 66 ;. }else if
1ba0: 28 20 4d 5b 64 2d 31 5d 5b 69 2d 31 5d 20 3c 20 ( M[d-1][i-1] <
1bb0: 4d 5b 64 2d 31 5d 5b 69 5d 20 29 7b 0a 20 20 20 M[d-1][i] ){.
1bc0: 20 20 20 20 20 71 20 3d 20 4d 5b 64 2d 31 5d 5b q = M[d-1][
1bd0: 69 5d 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b i];. }else{
1be0: 0a 20 20 20 20 20 20 20 20 71 20 3d 20 4d 5b 64 . q = M[d
1bf0: 2d 31 5d 5b 69 2d 31 5d 3b 0a 20 20 20 20 20 20 -1][i-1];.
1c00: 7d 0a 20 20 20 20 20 20 78 20 3d 20 28 6b 20 2b }. x = (k +
1c10: 20 71 20 2b 20 31 29 2f 32 3b 0a 20 20 20 20 20 q + 1)/2;.
1c20: 20 79 20 3d 20 78 20 2d 20 6b 3b 0a 20 20 20 20 y = x - k;.
1c30: 20 20 77 68 69 6c 65 28 20 78 3c 58 20 26 26 20 while( x<X &&
1c40: 79 3c 59 20 26 26 20 73 61 6d 65 5f 64 6c 69 6e y<Y && same_dlin
1c50: 65 28 26 41 5b 78 5d 2c 26 42 5b 79 5d 29 20 29 e(&A[x],&B[y]) )
1c60: 7b 20 78 2b 2b 3b 20 79 2b 2b 3b 20 7d 0a 20 20 { x++; y++; }.
1c70: 20 20 20 20 4d 5b 64 5d 5b 69 5d 20 3d 20 78 20 M[d][i] = x
1c80: 2b 20 79 3b 0a 20 20 20 20 20 20 69 66 28 20 78 + y;. if( x
1c90: 3d 3d 58 20 26 26 20 79 3d 3d 59 20 29 7b 0a 20 ==X && y==Y ){.
1ca0: 20 20 20 20 20 20 20 67 6f 20 3d 20 30 3b 0a 20 go = 0;.
1cb0: 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 break;.
1cc0: 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a }. }. }.
1cd0: 0a 20 20 2f 2a 20 52 65 75 73 65 20 4d 5b 5d 20 . /* Reuse M[]
1ce0: 61 73 20 66 6f 6c 6c 6f 77 73 3a 0a 20 20 2a 2a as follows:. **
1cf0: 0a 20 20 2a 2a 20 20 20 20 20 4d 5b 64 5d 5b 31 . ** M[d][1
1d00: 5d 20 3d 20 31 20 69 66 20 61 20 6c 69 6e 65 20 ] = 1 if a line
1d10: 69 73 20 69 6e 73 65 72 74 65 64 20 6f 72 20 31 is inserted or 1
1d20: 20 69 66 20 61 20 6c 69 6e 65 20 69 73 20 64 65 if a line is de
1d30: 6c 65 74 65 64 2e 0a 20 20 2a 2a 20 20 20 20 20 leted.. **
1d40: 4d 5b 64 5d 5b 30 5d 20 3d 20 6e 75 6d 62 65 72 M[d][0] = number
1d50: 20 6f 66 20 6c 69 6e 65 73 20 63 6f 70 69 65 64 of lines copied
1d60: 20 61 74 20 74 68 69 73 20 73 74 65 70 2e 0a 20 at this step..
1d70: 20 2a 2a 0a 20 20 2a 2f 0a 20 20 44 20 3d 20 64 **. */. D = d
1d80: 20 2d 20 31 3b 0a 20 20 4b 20 3d 20 58 20 2d 20 - 1;. K = X -
1d90: 59 3b 0a 20 20 66 6f 72 28 64 3d 44 2c 20 69 3d Y;. for(d=D, i=
1da0: 28 4b 2b 44 29 2f 32 3b 20 64 3e 30 3b 20 64 2d (K+D)/2; d>0; d-
1db0: 2d 29 7b 0a 20 20 20 20 69 66 28 20 69 3d 3d 64 -){. if( i==d
1dc0: 20 7c 7c 20 4d 5b 64 2d 31 5d 5b 69 2d 31 5d 20 || M[d-1][i-1]
1dd0: 3e 20 4d 5b 64 2d 31 5d 5b 69 5d 20 29 7b 0a 20 > M[d-1][i] ){.
1de0: 20 20 20 20 20 4d 5b 64 5d 5b 30 5d 20 3d 20 4d M[d][0] = M
1df0: 5b 64 5d 5b 69 5d 20 2d 20 4d 5b 64 2d 31 5d 5b [d][i] - M[d-1][
1e00: 69 2d 31 5d 20 2d 20 31 3b 0a 20 20 20 20 20 20 i-1] - 1;.
1e10: 4d 5b 64 5d 5b 31 5d 20 3d 20 30 3b 0a 20 20 20 M[d][1] = 0;.
1e20: 20 20 20 69 2d 2d 3b 0a 20 20 20 20 7d 65 6c 73 i--;. }els
1e30: 65 7b 0a 20 20 20 20 20 20 4d 5b 64 5d 5b 30 5d e{. M[d][0]
1e40: 20 3d 20 4d 5b 64 5d 5b 69 5d 20 2d 20 4d 5b 64 = M[d][i] - M[d
1e50: 2d 31 5d 5b 69 5d 20 2d 20 31 3b 0a 20 20 20 20 -1][i] - 1;.
1e60: 20 20 4d 5b 64 5d 5b 31 5d 20 3d 20 31 3b 0a 20 M[d][1] = 1;.
1e70: 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 2f 2a 20 41 }. }.. /* A
1e80: 6c 6c 6f 63 61 74 65 20 74 68 65 20 6f 75 74 70 llocate the outp
1e90: 75 74 20 76 65 63 74 6f 72 0a 20 20 2a 2f 0a 20 ut vector. */.
1ea0: 20 52 20 3d 20 6d 61 6c 6c 6f 63 28 20 73 69 7a R = malloc( siz
1eb0: 65 6f 66 28 52 5b 30 5d 29 2a 28 44 2b 32 29 2a eof(R[0])*(D+2)*
1ec0: 33 20 29 3b 0a 20 20 69 66 28 20 52 3d 3d 30 20 3 );. if( R==0
1ed0: 29 7b 0a 20 20 20 20 66 6f 73 73 69 6c 5f 66 61 ){. fossil_fa
1ee0: 74 61 6c 28 22 6f 75 74 20 6f 66 20 6d 65 6d 6f tal("out of memo
1ef0: 72 79 22 29 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 ry");. }.. /*
1f00: 50 6f 70 75 6c 61 74 65 20 74 68 65 20 6f 75 74 Populate the out
1f10: 70 75 74 20 76 65 63 74 6f 72 0a 20 20 2a 2f 0a put vector. */.
1f20: 20 20 64 20 3d 20 72 20 3d 20 30 3b 0a 20 20 77 d = r = 0;. w
1f30: 68 69 6c 65 28 20 64 3c 3d 44 20 29 7b 0a 20 20 hile( d<=D ){.
1f40: 20 20 69 6e 74 20 6e 3b 0a 20 20 20 20 52 5b 72 int n;. R[r
1f50: 2b 2b 5d 20 3d 20 4d 5b 64 2b 2b 5d 5b 30 5d 2f ++] = M[d++][0]/
1f60: 32 3b 20 20 20 2f 2a 20 43 4f 50 59 20 2a 2f 0a 2; /* COPY */.
1f70: 20 20 20 20 69 66 28 20 64 3e 44 20 29 7b 0a 20 if( d>D ){.
1f80: 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b R[r++] = 0;
1f90: 0a 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 . R[r++] =
1fa0: 30 3b 0a 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 0;. break;.
1fb0: 20 20 20 20 7d 0a 20 20 20 20 69 66 28 20 4d 5b }. if( M[
1fc0: 64 5d 5b 31 5d 3d 3d 30 20 29 7b 0a 20 20 20 20 d][1]==0 ){.
1fd0: 20 20 6e 20 3d 20 31 3b 0a 20 20 20 20 20 20 77 n = 1;. w
1fe0: 68 69 6c 65 28 20 4d 5b 64 5d 5b 30 5d 3d 3d 30 hile( M[d][0]==0
1ff0: 20 26 26 20 64 3c 44 20 26 26 20 4d 5b 64 2b 31 && d<D && M[d+1
2000: 5d 5b 31 5d 3d 3d 30 20 29 7b 0a 20 20 20 20 20 ][1]==0 ){.
2010: 20 20 20 64 2b 2b 3b 0a 20 20 20 20 20 20 20 20 d++;.
2020: 6e 2b 2b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 n++;. }.
2030: 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 6e 3b 20 20 R[r++] = n;
2040: 20 20 20 20 20 20 20 20 20 2f 2a 20 44 45 4c 45 /* DELE
2050: 54 45 20 2a 2f 0a 20 20 20 20 20 20 69 66 28 20 TE */. if(
2060: 64 3d 3d 44 20 7c 7c 20 4d 5b 64 5d 5b 30 5d 3e d==D || M[d][0]>
2070: 30 20 29 7b 0a 20 20 20 20 20 20 20 20 52 5b 72 0 ){. R[r
2080: 2b 2b 5d 20 3d 20 30 3b 20 20 20 20 20 20 20 20 ++] = 0;
2090: 20 2f 2a 20 49 4e 53 45 52 54 20 2a 2f 0a 20 20 /* INSERT */.
20a0: 20 20 20 20 20 20 63 6f 6e 74 69 6e 75 65 3b 0a continue;.
20b0: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 64 2b }. d+
20c0: 2b 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 +;. }else{.
20d0: 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 20 R[r++] = 0;
20e0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44 45 4c /* DEL
20f0: 45 54 45 20 2a 2f 0a 20 20 20 20 7d 0a 20 20 20 ETE */. }.
2100: 20 61 73 73 65 72 74 28 20 4d 5b 64 5d 5b 31 5d assert( M[d][1]
2110: 3d 3d 31 20 29 3b 0a 20 20 20 20 6e 20 3d 20 31 ==1 );. n = 1
2120: 3b 0a 20 20 20 20 77 68 69 6c 65 28 20 4d 5b 64 ;. while( M[d
2130: 5d 5b 30 5d 3d 3d 30 20 26 26 20 64 3c 44 20 26 ][0]==0 && d<D &
2140: 26 20 4d 5b 64 2b 31 5d 5b 31 5d 3d 3d 31 20 29 & M[d+1][1]==1 )
2150: 7b 0a 20 20 20 20 20 20 64 2b 2b 3b 0a 20 20 20 {. d++;.
2160: 20 20 20 6e 2b 2b 3b 0a 20 20 20 20 7d 0a 20 20 n++;. }.
2170: 20 20 52 5b 72 2b 2b 5d 20 3d 20 6e 3b 20 20 20 R[r++] = n;
2180: 20 20 20 20 20 20 20 20 20 2f 2a 20 49 4e 53 45 /* INSE
2190: 52 54 20 2a 2f 0a 20 20 7d 0a 20 20 52 5b 72 2b RT */. }. R[r+
21a0: 2b 5d 20 3d 20 30 3b 0a 20 20 52 5b 72 2b 2b 5d +] = 0;. R[r++]
21b0: 20 3d 20 30 3b 0a 20 20 52 5b 72 2b 2b 5d 20 3d = 0;. R[r++] =
21c0: 20 30 3b 0a 0a 20 20 2f 2a 20 46 72 65 65 20 74 0;.. /* Free t
21d0: 68 65 20 4d 79 65 72 73 20 6d 61 74 72 69 78 20 he Myers matrix
21e0: 2a 2f 0a 20 20 66 6f 72 28 64 3d 30 3b 20 64 3c */. for(d=0; d<
21f0: 3d 44 3b 20 64 2b 2b 29 7b 0a 20 20 20 20 66 72 =D; d++){. fr
2200: 65 65 28 4d 5b 64 5d 29 3b 0a 20 20 7d 0a 20 20 ee(M[d]);. }.
2210: 66 72 65 65 28 4d 29 3b 0a 0a 20 20 2f 2a 20 49 free(M);.. /* I
2220: 66 20 70 4f 75 74 20 69 73 20 64 65 66 69 6e 65 f pOut is define
2230: 64 2c 20 63 6f 6e 73 74 72 75 63 74 20 61 20 75 d, construct a u
2240: 6e 69 66 69 65 64 20 64 69 66 66 20 69 6e 74 6f nified diff into
2250: 20 70 4f 75 74 20 61 6e 64 0a 20 20 2a 2a 20 64 pOut and. ** d
2260: 65 6c 65 74 65 20 52 0a 20 20 2a 2f 0a 20 20 69 elete R. */. i
2270: 66 28 20 70 4f 75 74 20 29 7b 0a 20 20 20 20 69 f( pOut ){. i
2280: 6e 74 20 61 20 3d 20 30 3b 20 20 20 20 2f 2a 20 nt a = 0; /*
2290: 49 6e 64 65 78 20 6f 66 20 6e 65 78 74 20 6c 69 Index of next li
22a0: 6e 65 20 69 6e 20 41 5b 5d 20 2a 2f 0a 20 20 20 ne in A[] */.
22b0: 20 69 6e 74 20 62 20 3d 20 30 3b 20 20 20 20 2f int b = 0; /
22c0: 2a 20 49 6e 64 65 78 20 6f 66 20 6e 65 78 74 20 * Index of next
22d0: 6c 69 6e 65 20 69 6e 20 42 5b 5d 20 2a 2f 0a 20 line in B[] */.
22e0: 20 20 20 69 6e 74 20 6e 72 3b 20 20 20 20 20 20 int nr;
22f0: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 43 4f /* Number of CO
2300: 50 59 2f 44 45 4c 45 54 45 2f 49 4e 53 45 52 54 PY/DELETE/INSERT
2310: 20 74 72 69 70 6c 65 73 20 74 6f 20 70 72 6f 63 triples to proc
2320: 65 73 73 20 2a 2f 0a 20 20 20 20 69 6e 74 20 6e ess */. int n
2330: 61 2c 20 6e 62 3b 20 20 20 2f 2a 20 4e 75 6d 62 a, nb; /* Numb
2340: 65 72 20 6f 66 20 6c 69 6e 65 73 20 73 68 6f 77 er of lines show
2350: 6e 20 66 72 6f 6d 20 41 20 61 6e 64 20 42 20 2a n from A and B *
2360: 2f 0a 20 20 20 20 69 6e 74 20 69 2c 20 6a 3b 20 /. int i, j;
2370: 20 20 20 20 2f 2a 20 4c 6f 6f 70 20 63 6f 75 6e /* Loop coun
2380: 74 65 72 73 20 2a 2f 0a 20 20 20 20 69 6e 74 20 ters */. int
2390: 6d 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d m; /* Num
23a0: 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 74 6f 20 ber of lines to
23b0: 6f 75 74 70 75 74 20 2a 2f 0a 20 20 20 20 69 6e output */. in
23c0: 74 20 73 6b 69 70 3b 20 20 20 20 20 2f 2a 20 4e t skip; /* N
23d0: 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 74 umber of lines t
23e0: 6f 20 73 6b 69 70 20 2a 2f 0a 0a 20 20 20 20 66 o skip */.. f
23f0: 6f 72 28 72 3d 30 3b 20 52 5b 72 2b 33 5d 3b 20 or(r=0; R[r+3];
2400: 72 20 2b 3d 20 33 2a 6e 72 29 7b 0a 20 20 20 20 r += 3*nr){.
2410: 20 20 2f 2a 20 46 69 67 75 72 65 20 6f 75 74 20 /* Figure out
2420: 68 6f 77 20 6d 61 6e 79 20 74 72 69 70 6c 65 73 how many triples
2430: 20 74 6f 20 73 68 6f 77 20 69 6e 20 61 20 73 69 to show in a si
2440: 6e 67 6c 65 20 62 6c 6f 63 6b 20 2a 2f 0a 20 20 ngle block */.
2450: 20 20 20 20 66 6f 72 28 6e 72 3d 31 3b 20 52 5b for(nr=1; R[
2460: 72 2b 6e 72 2a 33 5d 3e 30 20 26 26 20 52 5b 72 r+nr*3]>0 && R[r
2470: 2b 6e 72 2a 33 5d 3c 6e 43 6f 6e 74 65 78 74 2a +nr*3]<nContext*
2480: 32 3b 20 6e 72 2b 2b 29 7b 7d 0a 0a 20 20 20 20 2; nr++){}..
2490: 20 20 2f 2a 20 46 6f 72 20 74 68 65 20 63 75 72 /* For the cur
24a0: 72 65 6e 74 20 62 6c 6f 63 6b 20 63 6f 6d 70 72 rent block compr
24b0: 69 73 69 6e 67 20 6e 72 20 74 72 69 70 6c 65 73 ising nr triples
24c0: 2c 20 66 69 67 75 72 65 20 6f 75 74 0a 20 20 20 , figure out.
24d0: 20 20 20 2a 2a 20 68 6f 77 20 6d 61 6e 79 20 6c ** how many l
24e0: 69 6e 65 73 20 6f 66 20 41 20 61 6e 64 20 42 20 ines of A and B
24f0: 61 72 65 20 74 6f 20 62 65 20 64 69 73 70 6c 61 are to be displa
2500: 79 65 64 0a 20 20 20 20 20 20 2a 2f 0a 20 20 20 yed. */.
2510: 20 20 20 69 66 28 20 52 5b 72 5d 3e 6e 43 6f 6e if( R[r]>nCon
2520: 74 65 78 74 20 29 7b 0a 20 20 20 20 20 20 20 20 text ){.
2530: 6e 61 20 3d 20 6e 62 20 3d 20 6e 43 6f 6e 74 65 na = nb = nConte
2540: 78 74 3b 0a 20 20 20 20 20 20 20 20 73 6b 69 70 xt;. skip
2550: 20 3d 20 52 5b 72 5d 20 2d 20 6e 43 6f 6e 74 65 = R[r] - nConte
2560: 78 74 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b xt;. }else{
2570: 0a 20 20 20 20 20 20 20 20 6e 61 20 3d 20 6e 62 . na = nb
2580: 20 3d 20 52 5b 72 5d 3b 0a 20 20 20 20 20 20 20 = R[r];.
2590: 20 73 6b 69 70 20 3d 20 30 3b 0a 20 20 20 20 20 skip = 0;.
25a0: 20 7d 0a 20 20 20 20 20 20 66 6f 72 28 69 3d 30 }. for(i=0
25b0: 3b 20 69 3c 6e 72 3b 20 69 2b 2b 29 7b 0a 20 20 ; i<nr; i++){.
25c0: 20 20 20 20 20 20 6e 61 20 2b 3d 20 52 5b 72 2b na += R[r+
25d0: 69 2a 33 2b 31 5d 3b 0a 20 20 20 20 20 20 20 20 i*3+1];.
25e0: 6e 62 20 2b 3d 20 52 5b 72 2b 69 2a 33 2b 32 5d nb += R[r+i*3+2]
25f0: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 ;. }.
2600: 69 66 28 20 52 5b 72 2b 69 2a 33 5d 3e 6e 43 6f if( R[r+i*3]>nCo
2610: 6e 74 65 78 74 20 29 7b 0a 20 20 20 20 20 20 20 ntext ){.
2620: 20 6e 61 20 2b 3d 20 6e 43 6f 6e 74 65 78 74 3b na += nContext;
2630: 0a 20 20 20 20 20 20 20 20 6e 62 20 2b 3d 20 6e . nb += n
2640: 43 6f 6e 74 65 78 74 3b 0a 20 20 20 20 20 20 7d Context;. }
2650: 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 6e 61 else{. na
2660: 20 2b 3d 20 52 5b 72 2b 69 2a 33 5d 3b 0a 20 20 += R[r+i*3];.
2670: 20 20 20 20 20 20 6e 62 20 2b 3d 20 52 5b 72 2b nb += R[r+
2680: 69 2a 33 5d 3b 0a 20 20 20 20 20 20 7d 0a 20 20 i*3];. }.
2690: 20 20 20 20 66 6f 72 28 69 3d 31 3b 20 69 3c 6e for(i=1; i<n
26a0: 72 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 20 r; i++){.
26b0: 20 6e 61 20 2b 3d 20 52 5b 72 2b 69 2a 33 5d 3b na += R[r+i*3];
26c0: 0a 20 20 20 20 20 20 20 20 6e 62 20 2b 3d 20 52 . nb += R
26d0: 5b 72 2b 69 2a 33 5d 3b 0a 20 20 20 20 20 20 7d [r+i*3];. }
26e0: 0a 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 . blob_appe
26f0: 6e 64 66 28 70 4f 75 74 2c 22 40 40 20 2d 25 64 ndf(pOut,"@@ -%d
2700: 2c 25 64 20 2b 25 64 2c 25 64 20 40 40 5c 6e 22 ,%d +%d,%d @@\n"
2710: 2c 20 61 2b 73 6b 69 70 2b 31 2c 20 6e 61 2c 20 , a+skip+1, na,
2720: 62 2b 73 6b 69 70 2b 31 2c 20 6e 62 29 3b 0a 0a b+skip+1, nb);..
2730: 20 20 20 20 20 20 2f 2a 20 53 68 6f 77 20 74 68 /* Show th
2740: 65 20 69 6e 69 74 69 61 6c 20 63 6f 6d 6d 6f 6e e initial common
2750: 20 61 72 65 61 20 2a 2f 0a 20 20 20 20 20 20 61 area */. a
2760: 20 2b 3d 20 73 6b 69 70 3b 0a 20 20 20 20 20 20 += skip;.
2770: 62 20 2b 3d 20 73 6b 69 70 3b 0a 20 20 20 20 20 b += skip;.
2780: 20 6d 20 3d 20 52 5b 72 5d 20 2d 20 73 6b 69 70 m = R[r] - skip
2790: 3b 0a 20 20 20 20 20 20 66 6f 72 28 6a 3d 30 3b ;. for(j=0;
27a0: 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 j<m; j++){.
27b0: 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 6e 64 66 blob_appendf
27c0: 28 70 4f 75 74 2c 22 20 25 73 5c 6e 22 2c 20 41 (pOut," %s\n", A
27d0: 5b 61 2b 6a 5d 2e 7a 29 3b 0a 20 20 20 20 20 20 [a+j].z);.
27e0: 7d 0a 20 20 20 20 20 20 61 20 2b 3d 20 6d 3b 0a }. a += m;.
27f0: 20 20 20 20 20 20 62 20 2b 3d 20 6d 3b 0a 0a 20 b += m;..
2800: 20 20 20 20 20 2f 2a 20 53 68 6f 77 20 74 68 65 /* Show the
2810: 20 64 69 66 66 65 72 65 6e 63 65 73 20 2a 2f 0a differences */.
2820: 20 20 20 20 20 20 66 6f 72 28 69 3d 30 3b 20 69 for(i=0; i
2830: 3c 6e 72 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 <nr; i++){.
2840: 20 20 20 6d 20 3d 20 52 5b 72 2b 69 2a 33 2b 31 m = R[r+i*3+1
2850: 5d 3b 0a 20 20 20 20 20 20 20 20 66 6f 72 28 6a ];. for(j
2860: 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 =0; j<m; j++){.
2870: 20 20 20 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 blob_ap
2880: 70 65 6e 64 66 28 70 4f 75 74 2c 22 2d 25 73 5c pendf(pOut,"-%s\
2890: 6e 22 2c 20 41 5b 61 2b 6a 5d 2e 7a 29 3b 0a 20 n", A[a+j].z);.
28a0: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 }.
28b0: 20 61 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 20 20 a += m;.
28c0: 20 6d 20 3d 20 52 5b 72 2b 69 2a 33 2b 32 5d 3b m = R[r+i*3+2];
28d0: 0a 20 20 20 20 20 20 20 20 66 6f 72 28 6a 3d 30 . for(j=0
28e0: 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 ; j<m; j++){.
28f0: 20 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 blob_appe
2900: 6e 64 66 28 70 4f 75 74 2c 22 2b 25 73 5c 6e 22 ndf(pOut,"+%s\n"
2910: 2c 20 42 5b 62 2b 6a 5d 2e 7a 29 3b 0a 20 20 20 , B[b+j].z);.
2920: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 62 }. b
2930: 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 20 20 20 69 += m;. i
2940: 66 28 20 69 3c 6e 72 2d 31 20 29 7b 0a 20 20 20 f( i<nr-1 ){.
2950: 20 20 20 20 20 20 20 6d 20 3d 20 52 5b 72 2b 69 m = R[r+i
2960: 2a 33 2b 33 5d 3b 0a 20 20 20 20 20 20 20 20 20 *3+3];.
2970: 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a for(j=0; j<m; j
2980: 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 20 20 20 ++){.
2990: 20 62 6c 6f 62 5f 61 70 70 65 6e 64 66 28 70 4f blob_appendf(pO
29a0: 75 74 2c 22 20 25 73 5c 6e 22 2c 20 42 5b 62 2b ut," %s\n", B[b+
29b0: 6a 5d 2e 7a 29 3b 0a 20 20 20 20 20 20 20 20 20 j].z);.
29c0: 20 7d 0a 20 20 20 20 20 20 20 20 20 20 62 20 2b }. b +
29d0: 3d 20 6d 3b 0a 20 20 20 20 20 20 20 20 20 20 61 = m;. a
29e0: 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 20 20 20 7d += m;. }
29f0: 0a 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 . }..
2a00: 2f 2a 20 53 68 6f 77 20 74 68 65 20 66 69 6e 61 /* Show the fina
2a10: 6c 20 63 6f 6d 6d 6f 6e 20 61 72 65 61 20 2a 2f l common area */
2a20: 0a 20 20 20 20 20 20 61 73 73 65 72 74 28 20 6e . assert( n
2a30: 72 3d 3d 69 20 29 3b 0a 20 20 20 20 20 20 6d 20 r==i );. m
2a40: 3d 20 52 5b 72 2b 6e 72 2a 33 5d 3b 0a 20 20 20 = R[r+nr*3];.
2a50: 20 20 20 69 66 28 20 6d 3e 6e 43 6f 6e 74 65 78 if( m>nContex
2a60: 74 20 29 20 6d 20 3d 20 6e 43 6f 6e 74 65 78 74 t ) m = nContext
2a70: 3b 0a 20 20 20 20 20 20 66 6f 72 28 6a 3d 30 3b ;. for(j=0;
2a80: 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 j<m; j++){.
2a90: 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 6e 64 66 blob_appendf
2aa0: 28 70 4f 75 74 2c 22 20 25 73 5c 6e 22 2c 20 42 (pOut," %s\n", B
2ab0: 5b 62 2b 6a 5d 2e 7a 29 3b 0a 20 20 20 20 20 20 [b+j].z);.
2ac0: 7d 0a 20 20 20 20 7d 0a 20 20 20 20 66 72 65 65 }. }. free
2ad0: 28 52 29 3b 0a 20 20 20 20 52 20 3d 20 30 3b 0a (R);. R = 0;.
2ae0: 20 20 7d 0a 0a 20 20 2f 2a 20 57 65 20 6e 6f 20 }.. /* We no
2af0: 6c 6f 6e 67 65 72 20 6e 65 65 64 20 74 68 65 20 longer need the
2b00: 41 5b 5d 20 61 6e 64 20 42 5b 5d 20 76 65 63 74 A[] and B[] vect
2b10: 6f 72 73 20 2a 2f 0a 20 20 66 72 65 65 28 41 29 ors */. free(A)
2b20: 3b 0a 20 20 66 72 65 65 28 42 29 3b 0a 0a 20 20 ;. free(B);..
2b30: 2f 2a 20 52 65 74 75 72 6e 20 74 68 65 20 72 65 /* Return the re
2b40: 73 75 6c 74 20 2a 2f 0a 20 20 72 65 74 75 72 6e sult */. return
2b50: 20 52 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 4f 4d R;.}../*.** COM
2b60: 4d 41 4e 44 3a 20 74 65 73 74 2d 72 61 77 64 69 MAND: test-rawdi
2b70: 66 66 0a 2a 2f 0a 76 6f 69 64 20 74 65 73 74 5f ff.*/.void test_
2b80: 72 61 77 64 69 66 66 5f 63 6d 64 28 76 6f 69 64 rawdiff_cmd(void
2b90: 29 7b 0a 20 20 42 6c 6f 62 20 61 2c 20 62 3b 0a ){. Blob a, b;.
2ba0: 20 20 69 6e 74 20 72 3b 0a 20 20 69 6e 74 20 2a int r;. int *
2bb0: 52 3b 0a 20 20 69 66 28 20 67 2e 61 72 67 63 21 R;. if( g.argc!
2bc0: 3d 34 20 29 20 75 73 61 67 65 28 22 46 49 4c 45 =4 ) usage("FILE
2bd0: 31 20 46 49 4c 45 32 22 29 3b 0a 20 20 62 6c 6f 1 FILE2");. blo
2be0: 62 5f 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 b_read_from_file
2bf0: 28 26 61 2c 20 67 2e 61 72 67 76 5b 32 5d 29 3b (&a, g.argv[2]);
2c00: 0a 20 20 62 6c 6f 62 5f 72 65 61 64 5f 66 72 6f . blob_read_fro
2c10: 6d 5f 66 69 6c 65 28 26 62 2c 20 67 2e 61 72 67 m_file(&b, g.arg
2c20: 76 5b 33 5d 29 3b 0a 20 20 52 20 3d 20 74 65 78 v[3]);. R = tex
2c30: 74 5f 64 69 66 66 28 26 61 2c 20 26 62 2c 20 30 t_diff(&a, &b, 0
2c40: 2c 20 30 29 3b 0a 20 20 66 6f 72 28 72 3d 30 3b , 0);. for(r=0;
2c50: 20 52 5b 72 5d 20 7c 7c 20 52 5b 72 2b 31 5d 20 R[r] || R[r+1]
2c60: 7c 7c 20 52 5b 72 2b 32 5d 3b 20 72 20 2b 3d 20 || R[r+2]; r +=
2c70: 33 29 7b 0a 20 20 20 20 70 72 69 6e 74 66 28 22 3){. printf("
2c80: 20 63 6f 70 79 20 25 34 64 20 20 64 65 6c 65 74 copy %4d delet
2c90: 65 20 25 34 64 20 20 69 6e 73 65 72 74 20 25 34 e %4d insert %4
2ca0: 64 5c 6e 22 2c 20 52 5b 72 5d 2c 20 52 5b 72 2b d\n", R[r], R[r+
2cb0: 31 5d 2c 20 52 5b 72 2b 32 5d 29 3b 0a 20 20 7d 1], R[r+2]);. }
2cc0: 0a 20 20 66 72 65 65 28 52 29 3b 0a 7d 0a 0a 2f . free(R);.}../
2cd0: 2a 0a 2a 2a 20 43 4f 4d 4d 41 4e 44 3a 20 74 65 *.** COMMAND: te
2ce0: 73 74 2d 75 64 69 66 66 0a 2a 2f 0a 76 6f 69 64 st-udiff.*/.void
2cf0: 20 74 65 73 74 5f 75 64 69 66 66 5f 63 6d 64 28 test_udiff_cmd(
2d00: 76 6f 69 64 29 7b 0a 20 20 42 6c 6f 62 20 61 2c void){. Blob a,
2d10: 20 62 2c 20 6f 75 74 3b 0a 20 20 69 66 28 20 67 b, out;. if( g
2d20: 2e 61 72 67 63 21 3d 34 20 29 20 75 73 61 67 65 .argc!=4 ) usage
2d30: 28 22 46 49 4c 45 31 20 46 49 4c 45 32 22 29 3b ("FILE1 FILE2");
2d40: 0a 20 20 62 6c 6f 62 5f 72 65 61 64 5f 66 72 6f . blob_read_fro
2d50: 6d 5f 66 69 6c 65 28 26 61 2c 20 67 2e 61 72 67 m_file(&a, g.arg
2d60: 76 5b 32 5d 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 v[2]);. blob_re
2d70: 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 62 2c ad_from_file(&b,
2d80: 20 67 2e 61 72 67 76 5b 33 5d 29 3b 0a 20 20 62 g.argv[3]);. b
2d90: 6c 6f 62 5f 7a 65 72 6f 28 26 6f 75 74 29 3b 0a lob_zero(&out);.
2da0: 20 20 74 65 78 74 5f 64 69 66 66 28 26 61 2c 20 text_diff(&a,
2db0: 26 62 2c 20 26 6f 75 74 2c 20 33 29 3b 0a 20 20 &b, &out, 3);.
2dc0: 62 6c 6f 62 5f 77 72 69 74 65 5f 74 6f 5f 66 69 blob_write_to_fi
2dd0: 6c 65 28 26 6f 75 74 2c 20 22 2d 22 29 3b 0a 7d le(&out, "-");.}
2de0: 0a .