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 26 26 20 ( z[i]=='\n' &&
06a0: 7a 5b 69 2b 31 5d 21 3d 30 20 29 20 6e 4c 69 6e z[i+1]!=0 ) nLin
06b0: 65 2b 2b 3b 0a 20 20 7d 0a 20 20 61 20 3d 20 6d e++;. }. a = m
06c0: 61 6c 6c 6f 63 28 20 6e 4c 69 6e 65 2a 73 69 7a alloc( nLine*siz
06d0: 65 6f 66 28 61 5b 30 5d 29 20 29 3b 0a 20 20 69 eof(a[0]) );. i
06e0: 66 28 20 61 3d 3d 30 20 29 20 66 6f 73 73 69 6c f( a==0 ) fossil
06f0: 5f 70 61 6e 69 63 28 22 6f 75 74 20 6f 66 20 6d _panic("out of m
0700: 65 6d 6f 72 79 22 29 3b 0a 0a 20 20 2f 2a 20 46 emory");.. /* F
0710: 69 6c 6c 20 69 6e 20 74 68 65 20 61 72 72 61 79 ill in the array
0720: 20 2a 2f 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 */. for(i=0; i
0730: 3c 6e 4c 69 6e 65 3b 20 69 2b 2b 29 7b 0a 20 20 <nLine; i++){.
0740: 20 20 61 5b 69 5d 2e 7a 20 3d 20 7a 3b 0a 20 20 a[i].z = z;.
0750: 20 20 66 6f 72 28 6a 3d 30 3b 20 7a 5b 6a 5d 20 for(j=0; z[j]
0760: 26 26 20 7a 5b 6a 5d 21 3d 27 5c 6e 27 3b 20 6a && z[j]!='\n'; j
0770: 2b 2b 29 7b 7d 0a 20 20 20 20 66 6f 72 28 6b 3d ++){}. for(k=
0780: 6a 3b 20 6b 3e 30 20 26 26 20 69 73 73 70 61 63 j; k>0 && isspac
0790: 65 28 7a 5b 6b 2d 31 5d 29 3b 20 6b 2d 2d 29 7b e(z[k-1]); k--){
07a0: 7d 0a 20 20 20 20 7a 5b 6b 5d 20 3d 20 30 3b 0a }. z[k] = 0;.
07b0: 20 20 20 20 66 6f 72 28 68 3d 30 2c 20 78 3d 30 for(h=0, x=0
07c0: 3b 20 78 3c 6b 3b 20 78 2b 2b 29 7b 0a 20 20 20 ; x<k; x++){.
07d0: 20 20 20 68 20 3d 20 68 20 5e 20 28 68 3c 3c 32 h = h ^ (h<<2
07e0: 29 20 5e 20 7a 5b 78 5d 3b 0a 20 20 20 20 7d 0a ) ^ z[x];. }.
07f0: 20 20 20 20 61 5b 69 5d 2e 68 20 3d 20 68 3b 0a a[i].h = h;.
0800: 20 20 20 20 7a 20 2b 3d 20 6a 2b 31 3b 0a 20 20 z += j+1;.
0810: 7d 0a 0a 20 20 2f 2a 20 52 65 74 75 72 6e 20 72 }.. /* Return r
0820: 65 73 75 6c 74 73 20 2a 2f 0a 20 20 2a 70 6e 4c esults */. *pnL
0830: 69 6e 65 20 3d 20 6e 4c 69 6e 65 3b 0a 20 20 72 ine = nLine;. r
0840: 65 74 75 72 6e 20 61 3b 0a 7d 0a 0a 2f 2a 0a 2a eturn a;.}../*.*
0850: 2a 20 52 65 74 75 72 6e 20 74 72 75 65 20 69 66 * Return true if
0860: 20 74 77 6f 20 44 4c 69 6e 65 20 65 6c 65 6d 65 two DLine eleme
0870: 6e 74 73 20 61 72 65 20 69 64 65 6e 74 69 63 61 nts are identica
0880: 6c 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 l..*/.static int
0890: 20 73 61 6d 65 5f 64 6c 69 6e 65 28 44 4c 69 6e same_dline(DLin
08a0: 65 20 2a 70 41 2c 20 44 4c 69 6e 65 20 2a 70 42 e *pA, DLine *pB
08b0: 29 7b 0a 20 20 72 65 74 75 72 6e 20 70 41 2d 3e ){. return pA->
08c0: 68 3d 3d 70 42 2d 3e 68 20 26 26 20 73 74 72 63 h==pB->h && strc
08d0: 6d 70 28 70 41 2d 3e 7a 2c 70 42 2d 3e 7a 29 3d mp(pA->z,pB->z)=
08e0: 3d 30 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 47 65 6e =0;.}../*.** Gen
08f0: 65 72 61 74 65 20 61 20 72 65 70 6f 72 74 20 6f erate a report o
0900: 66 20 74 68 65 20 64 69 66 66 65 72 65 6e 63 65 f the difference
0910: 73 20 62 65 74 77 65 65 6e 20 66 69 6c 65 73 20 s between files
0920: 70 41 20 61 6e 64 20 70 42 2e 0a 2a 2a 20 54 68 pA and pB..** Th
0930: 65 20 6c 69 6e 65 20 65 6e 64 69 6e 67 20 28 5c e line ending (\
0940: 72 5c 6e 20 76 65 72 73 75 73 20 5c 6e 29 20 69 r\n versus \n) i
0950: 73 20 69 67 6e 6f 72 65 64 20 2d 20 74 68 65 20 s ignored - the
0960: 74 77 6f 20 6c 69 6e 65 0a 2a 2a 20 65 6e 64 69 two line.** endi
0970: 6e 67 73 20 61 72 65 20 63 6f 6e 73 69 64 65 72 ngs are consider
0980: 65 64 20 74 6f 20 62 65 20 65 71 75 69 76 61 6c ed to be equival
0990: 65 6e 74 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 72 ent..**.** The r
09a0: 65 74 75 72 6e 20 69 73 20 61 20 70 6f 69 6e 74 eturn is a point
09b0: 65 72 20 74 6f 20 61 6e 20 61 72 72 61 79 20 6f er to an array o
09c0: 66 20 69 6e 74 65 67 65 72 73 20 74 68 61 74 20 f integers that
09d0: 64 65 73 63 72 69 62 65 73 0a 2a 2a 20 74 68 65 describes.** the
09e0: 20 64 69 66 66 65 72 65 6e 63 65 2e 20 20 49 6e difference. In
09f0: 74 65 67 65 72 73 20 63 6f 6d 65 20 69 6e 20 74 tegers come in t
0a00: 72 69 70 6c 65 73 2e 20 20 46 6f 72 20 65 61 63 riples. For eac
0a10: 68 20 74 72 69 70 6c 65 2c 0a 2a 2a 20 74 68 65 h triple,.** the
0a20: 20 65 6c 65 6d 65 6e 74 73 20 61 72 65 20 74 68 elements are th
0a30: 65 20 6e 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 e number of line
0a40: 73 20 63 6f 70 69 65 64 2c 20 74 68 65 20 6e 75 s copied, the nu
0a50: 6d 62 65 72 20 6f 66 0a 2a 2a 20 6c 69 6e 65 73 mber of.** lines
0a60: 20 64 65 6c 65 74 65 2c 20 61 6e 64 20 74 68 65 delete, and the
0a70: 20 6e 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 number of lines
0a80: 20 69 6e 73 65 72 74 65 64 2e 20 20 54 68 65 20 inserted. The
0a90: 76 65 63 74 6f 72 0a 2a 2a 20 69 73 20 74 65 72 vector.** is ter
0aa0: 6d 69 6e 61 74 65 64 20 62 79 20 61 20 74 72 69 minated by a tri
0ab0: 70 6c 65 20 6f 66 20 61 6c 6c 20 7a 65 72 6f 73 ple of all zeros
0ac0: 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 74 77 6f 20 ..**.** The two
0ad0: 62 6c 6f 62 73 20 69 73 20 64 65 73 74 72 6f 79 blobs is destroy
0ae0: 65 64 20 28 27 5c 30 30 30 27 20 76 61 6c 75 65 ed ('\000' value
0af0: 73 20 61 72 65 20 69 6e 73 65 72 74 65 64 29 0a s are inserted).
0b00: 2a 2a 20 62 79 20 74 68 65 20 64 69 66 66 69 6e ** by the diffin
0b10: 67 20 70 72 6f 63 65 73 73 2e 20 20 0a 2a 2a 0a g process. .**.
0b20: 2a 2a 20 54 68 65 20 63 6f 72 65 20 61 6c 67 6f ** The core algo
0b30: 72 69 74 68 6d 20 69 73 20 61 20 76 61 72 69 61 rithm is a varia
0b40: 74 69 6f 6e 20 6f 6e 20 74 68 65 20 63 6c 61 73 tion on the clas
0b50: 73 69 63 20 57 61 67 6e 65 72 0a 2a 2a 20 6d 69 sic Wagner.** mi
0b60: 6e 69 6d 75 6d 20 65 64 69 74 20 64 69 73 74 61 nimum edit dista
0b70: 6e 63 65 20 77 69 74 68 20 65 6e 68 61 6e 63 65 nce with enhance
0b80: 6d 65 6e 74 73 20 74 6f 20 72 65 64 75 63 65 20 ments to reduce
0b90: 74 68 65 20 72 75 6e 74 69 6d 65 0a 2a 2a 20 74 the runtime.** t
0ba0: 6f 20 62 65 20 61 6c 6d 6f 73 74 20 6c 69 6e 65 o be almost line
0bb0: 61 72 20 69 6e 20 74 68 65 20 63 6f 6d 6d 6f 6e ar in the common
0bc0: 20 63 61 73 65 20 77 68 65 72 65 20 74 68 65 20 case where the
0bd0: 74 77 6f 20 66 69 6c 65 73 0a 2a 2a 20 68 61 76 two files.** hav
0be0: 65 20 61 20 6c 6f 74 20 69 6e 20 63 6f 6d 6d 6f e a lot in commo
0bf0: 6e 2e 20 20 46 6f 72 20 61 64 64 69 74 69 6f 6e n. For addition
0c00: 61 6c 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 73 al information s
0c10: 65 65 0a 2a 2a 20 45 75 67 65 6e 65 20 57 2e 20 ee.** Eugene W.
0c20: 4d 79 65 72 73 2c 20 22 41 6e 20 4f 28 4e 44 29 Myers, "An O(ND)
0c30: 20 44 69 66 66 65 72 65 6e 63 65 20 41 6c 67 6f Difference Algo
0c40: 72 69 74 68 6d 20 41 6e 64 20 49 74 73 0a 2a 2a rithm And Its.**
0c50: 20 56 61 72 69 61 74 69 6f 6e 73 22 0a 2a 2a 0a Variations".**.
0c60: 2a 2a 20 43 6f 6e 73 69 64 65 72 20 63 6f 6d 70 ** Consider comp
0c70: 61 72 69 6e 67 20 73 74 72 69 6e 67 73 20 41 20 aring strings A
0c80: 61 6e 64 20 42 2e 20 20 41 3d 61 62 63 61 62 62 and B. A=abcabb
0c90: 61 20 61 6e 64 20 42 3d 63 62 61 62 61 63 0a 2a a and B=cbabac.*
0ca0: 2a 20 57 65 20 63 6f 6e 73 74 72 75 63 74 20 61 * We construct a
0cb0: 20 22 57 61 67 6e 65 72 22 20 6d 61 74 72 69 78 "Wagner" matrix
0cc0: 20 57 20 77 69 74 68 20 41 20 61 6c 6f 6e 67 20 W with A along
0cd0: 74 68 65 20 58 20 61 78 69 73 20 61 6e 64 20 0a the X axis and .
0ce0: 2a 2a 20 42 20 61 6c 6f 6e 67 20 74 68 65 20 59 ** B along the Y
0cf0: 20 61 78 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 axis:.**.**
0d00: 20 63 20 36 20 20 20 20 20 20 20 20 20 20 20 20 c 6
0d10: 20 20 20 2a 0a 2a 2a 20 20 20 20 20 61 20 35 20 *.** a 5
0d20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2a 0a *.
0d30: 2a 2a 20 20 20 20 20 62 20 34 20 20 20 20 20 20 ** b 4
0d40: 20 20 20 20 20 2a 20 2a 0a 2a 2a 20 20 20 20 20 * *.**
0d50: 61 20 33 20 20 20 20 20 20 20 20 20 2a 0a 2a 2a a 3 *.**
0d60: 20 20 20 20 20 62 20 32 20 20 20 20 20 20 20 2a b 2 *
0d70: 0a 2a 2a 20 20 20 42 20 63 20 31 20 20 20 20 20 .** B c 1
0d80: 20 20 2a 0a 2a 2a 20 20 20 20 20 20 20 30 20 2a *.** 0 *
0d90: 20 2a 20 2a 20 0a 2a 2a 20 20 20 20 20 20 20 20 * * .**
0da0: 20 30 20 31 20 32 20 33 20 34 20 35 20 36 20 37 0 1 2 3 4 5 6 7
0db0: 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 61 20 .** a
0dc0: 62 20 63 20 61 20 62 20 62 20 61 0a 2a 2a 20 20 b c a b b a.**
0dd0: 20 20 20 20 20 20 20 20 20 41 0a 2a 2a 0a 2a 2a A.**.**
0de0: 20 28 4e 6f 74 65 3a 20 77 65 20 64 72 61 77 20 (Note: we draw
0df0: 74 68 69 73 20 57 61 67 6e 65 72 20 6d 61 74 72 this Wagner matr
0e00: 69 78 20 77 69 74 68 20 74 68 65 20 6f 72 69 67 ix with the orig
0e10: 69 6e 20 61 74 20 74 68 65 20 6c 6f 77 65 72 20 in at the lower
0e20: 0a 2a 2a 20 6c 65 66 74 20 77 68 65 72 65 61 73 .** left whereas
0e30: 20 4d 79 65 72 73 20 75 73 65 73 20 74 68 65 20 Myers uses the
0e40: 6f 72 69 67 69 6e 20 61 74 20 74 68 65 20 75 70 origin at the up
0e50: 70 65 72 20 6c 65 66 74 2e 20 20 4f 74 68 65 72 per left. Other
0e60: 77 69 73 65 2c 0a 2a 2a 20 74 68 65 79 20 61 72 wise,.** they ar
0e70: 65 20 74 68 65 20 73 61 6d 65 2e 29 0a 2a 2a 0a e the same.).**.
0e80: 2a 2a 20 4c 65 74 20 59 20 62 65 20 74 68 65 20 ** Let Y be the
0e90: 6d 61 78 69 6d 75 6d 20 79 20 76 61 6c 75 65 20 maximum y value
0ea0: 6f 72 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 or the number of
0eb0: 20 63 68 61 72 61 63 74 65 72 73 20 69 6e 20 42 characters in B
0ec0: 2e 0a 2a 2a 20 36 20 69 6e 20 74 68 69 73 20 65 ..** 6 in this e
0ed0: 78 61 6d 70 6c 65 2e 20 20 58 20 69 73 20 74 68 xample. X is th
0ee0: 65 20 6d 61 78 69 6d 75 6d 20 78 20 76 61 6c 75 e maximum x valu
0ef0: 65 20 6f 72 20 74 68 65 20 6e 75 6d 62 65 72 20 e or the number
0f00: 6f 66 0a 2a 2a 20 65 6c 65 6d 65 6e 74 73 20 69 of.** elements i
0f10: 6e 20 41 2e 20 20 48 65 72 65 20 37 2e 0a 2a 2a n A. Here 7..**
0f20: 0a 2a 2a 20 4f 75 72 20 67 6f 61 6c 20 69 73 20 .** Our goal is
0f30: 74 6f 20 66 69 6e 64 20 61 20 70 61 74 68 20 66 to find a path f
0f40: 72 6f 6d 20 28 30 2c 30 29 20 74 6f 20 28 58 2c rom (0,0) to (X,
0f50: 59 29 2e 20 20 54 68 65 20 70 61 74 68 20 63 61 Y). The path ca
0f60: 6e 0a 2a 2a 20 75 73 65 20 68 6f 72 69 7a 6f 6e n.** use horizon
0f70: 74 61 6c 2c 20 76 65 72 74 69 63 61 6c 2c 20 6f tal, vertical, o
0f80: 72 20 64 69 61 67 6f 6e 61 6c 20 73 74 65 70 73 r diagonal steps
0f90: 2e 20 20 41 20 64 69 61 67 6f 6e 61 6c 20 66 72 . A diagonal fr
0fa0: 6f 6d 0a 2a 2a 20 28 78 2d 31 2c 79 2d 31 29 20 om.** (x-1,y-1)
0fb0: 74 6f 20 28 78 2c 79 29 20 69 73 20 6f 6e 6c 79 to (x,y) is only
0fc0: 20 61 6c 6c 6f 77 65 64 20 69 66 20 41 5b 78 5d allowed if A[x]
0fd0: 3d 3d 42 5b 79 5d 2e 20 20 41 20 76 65 72 74 69 ==B[y]. A verti
0fe0: 63 61 6c 0a 2a 2a 20 73 74 65 70 73 20 63 6f 72 cal.** steps cor
0ff0: 72 65 73 70 6f 6e 64 73 20 74 6f 20 61 6e 20 69 responds to an i
1000: 6e 73 65 72 74 69 6f 6e 2e 20 20 41 20 68 6f 72 nsertion. A hor
1010: 69 7a 6f 6e 74 61 6c 20 73 74 65 70 20 63 6f 72 izontal step cor
1020: 72 65 73 70 6f 6e 64 73 0a 2a 2a 20 74 6f 20 61 responds.** to a
1030: 20 64 65 6c 65 74 69 6f 6e 2e 20 20 57 65 20 77 deletion. We w
1040: 61 6e 74 20 74 6f 20 66 69 6e 64 20 74 68 65 20 ant to find the
1050: 70 61 74 68 20 77 69 74 68 20 74 68 65 20 66 65 path with the fe
1060: 77 65 73 74 0a 2a 2a 20 68 6f 72 69 7a 6f 6e 74 west.** horizont
1070: 61 6c 20 61 6e 64 20 76 65 72 74 69 63 61 6c 20 al and vertical
1080: 73 74 65 70 73 2e 0a 2a 2a 0a 2a 2a 20 44 69 61 steps..**.** Dia
1090: 67 6f 6e 61 6c 20 6b 20 63 6f 6e 73 69 73 74 73 gonal k consists
10a0: 20 6f 66 20 61 6c 6c 20 70 6f 69 6e 74 73 20 73 of all points s
10b0: 75 63 68 20 74 68 61 74 20 78 2d 79 3d 3d 6b 2e uch that x-y==k.
10c0: 20 20 44 69 61 67 6f 6e 61 6c 0a 2a 2a 20 7a 65 Diagonal.** ze
10d0: 72 6f 20 62 65 67 69 6e 73 20 61 74 20 74 68 65 ro begins at the
10e0: 20 6f 72 69 67 69 6e 2e 20 20 44 69 61 67 6f 6e origin. Diagon
10f0: 61 6c 20 31 20 62 65 67 69 6e 73 20 61 74 20 28 al 1 begins at (
1100: 31 2c 30 29 2e 20 20 0a 2a 2a 20 44 69 61 67 6f 1,0). .** Diago
1110: 6e 61 6c 20 2d 31 20 62 65 67 69 6e 73 20 61 74 nal -1 begins at
1120: 20 28 30 2c 31 29 2e 20 20 41 6c 6c 20 64 69 61 (0,1). All dia
1130: 67 6f 6e 61 6c 73 20 6d 6f 76 65 20 75 70 20 61 gonals move up a
1140: 6e 64 20 74 6f 20 74 68 65 0a 2a 2a 20 72 69 67 nd to the.** rig
1150: 68 74 20 61 74 20 34 35 20 64 65 67 72 65 65 73 ht at 45 degrees
1160: 2e 20 20 44 69 61 67 6f 6e 61 6c 20 6e 75 6d 62 . Diagonal numb
1170: 65 72 20 69 6e 63 72 65 61 73 65 20 66 72 6f 6d er increase from
1180: 20 75 70 70 65 72 20 6c 65 66 74 0a 2a 2a 20 74 upper left.** t
1190: 6f 20 6c 6f 77 65 72 20 72 69 67 68 74 2e 0a 2a o lower right..*
11a0: 2a 20 0a 2a 2a 20 4d 79 65 72 73 20 6d 61 74 72 * .** Myers matr
11b0: 69 78 20 4d 20 69 73 20 61 20 6c 6f 77 65 72 20 ix M is a lower
11c0: 72 69 67 68 74 20 74 72 69 61 6e 67 75 6c 61 72 right triangular
11d0: 20 6d 61 74 72 69 78 20 77 69 74 68 20 69 6e 64 matrix with ind
11e0: 69 63 65 73 20 64 0a 2a 2a 20 61 6c 6f 6e 67 20 ices d.** along
11f0: 74 68 65 20 62 6f 74 74 6f 6d 20 61 6e 64 20 69 the bottom and i
1200: 20 76 65 72 74 69 63 61 6c 6c 79 3a 0a 2a 2a 0a vertically:.**.
1210: 2a 2a 20 0a 2a 2a 20 20 20 69 3d 34 20 7c 20 20 ** .** i=4 |
1220: 20 20 20 20 20 20 20 20 20 20 2b 34 20 20 5c 0a +4 \.
1230: 2a 2a 20 20 20 20 20 33 20 7c 20 20 20 20 20 20 ** 3 |
1240: 20 20 20 2b 33 20 2b 32 20 20 20 7c 0a 2a 2a 20 +3 +2 |.**
1250: 20 20 20 20 32 20 7c 20 20 20 20 20 20 2b 32 20 2 | +2
1260: 2b 31 20 20 30 20 20 20 7c 2d 20 6b 20 76 61 6c +1 0 |- k val
1270: 75 65 73 2e 20 20 20 6b 20 3d 20 32 2a 69 2d 64 ues. k = 2*i-d
1280: 0a 2a 2a 20 20 20 20 20 31 20 7c 20 20 20 2b 31 .** 1 | +1
1290: 20 20 30 20 2d 31 20 2d 32 20 20 20 7c 0a 2a 2a 0 -1 -2 |.**
12a0: 20 20 20 20 20 30 20 7c 20 30 20 2d 31 20 2d 32 0 | 0 -1 -2
12b0: 20 2d 33 20 2d 34 20 20 2f 0a 2a 2a 20 20 20 20 -3 -4 /.**
12c0: 20 20 20 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d -------------
12d0: 2d 2d 0a 2a 2a 20 20 20 20 20 20 20 20 20 30 20 --.** 0
12e0: 20 31 20 20 32 20 20 33 20 20 34 20 3d 20 64 0a 1 2 3 4 = d.
12f0: 2a 2a 0a 2a 2a 20 45 61 63 68 20 65 6c 65 6d 65 **.** Each eleme
1300: 6e 74 20 6f 66 20 74 68 65 20 4d 79 65 72 73 20 nt of the Myers
1310: 6d 61 74 72 69 78 20 63 6f 72 72 65 73 70 6f 6e matrix correspon
1320: 64 73 20 74 6f 20 61 20 64 69 61 67 6f 6e 61 6c ds to a diagonal
1330: 2e 0a 2a 2a 20 54 68 65 20 64 69 61 67 6f 6e 61 ..** The diagona
1340: 6c 20 69 73 20 6b 3d 32 2a 69 2d 64 2e 20 20 54 l is k=2*i-d. T
1350: 68 65 20 64 69 61 67 6f 6e 61 6c 20 76 61 6c 75 he diagonal valu
1360: 65 73 20 61 72 65 20 73 68 6f 77 6e 0a 2a 2a 20 es are shown.**
1370: 69 6e 20 74 68 65 20 74 65 6d 70 6c 61 74 65 20 in the template
1380: 61 62 6f 76 65 2e 0a 2a 2a 0a 2a 2a 20 45 61 63 above..**.** Eac
1390: 68 20 65 6e 74 72 79 20 69 6e 20 4d 20 72 65 70 h entry in M rep
13a0: 72 65 73 65 6e 74 73 20 74 68 65 20 65 6e 64 2d resents the end-
13b0: 70 6f 69 6e 74 20 6f 6e 20 61 20 70 61 74 68 20 point on a path
13c0: 66 72 6f 6d 20 28 30 2c 30 29 2e 0a 2a 2a 20 54 from (0,0)..** T
13d0: 68 65 20 65 6e 64 2d 70 6f 69 6e 74 20 69 73 20 he end-point is
13e0: 6f 6e 20 64 69 61 67 6f 6e 61 6c 20 6b 2e 20 20 on diagonal k.
13f0: 54 68 65 20 76 61 6c 75 65 20 73 74 6f 72 65 64 The value stored
1400: 20 69 6e 20 4d 20 69 73 0a 2a 2a 20 71 3d 78 2b in M is.** q=x+
1410: 79 20 77 68 65 72 65 20 28 78 2c 79 29 20 69 73 y where (x,y) is
1420: 20 74 68 65 20 74 65 72 6d 69 6e 75 73 20 6f 66 the terminus of
1430: 20 74 68 65 20 70 61 74 68 2e 20 20 41 20 70 61 the path. A pa
1440: 74 68 0a 2a 2a 20 74 6f 20 4d 5b 64 5d 5b 69 5d th.** to M[d][i]
1450: 20 77 69 6c 6c 20 63 6f 6d 65 20 74 68 72 6f 75 will come throu
1460: 67 68 20 65 69 74 68 65 72 20 4d 5b 64 2d 31 5d gh either M[d-1]
1470: 5b 69 2d 31 5d 20 6f 72 0a 2a 2a 20 74 68 6f 75 [i-1] or.** thou
1480: 67 68 20 4d 5b 64 2d 31 5d 5b 69 5d 2c 20 77 68 gh M[d-1][i], wh
1490: 69 63 68 65 76 65 72 20 68 6f 6c 64 73 20 74 68 ichever holds th
14a0: 65 20 6c 61 72 67 65 73 74 20 76 61 6c 75 65 20 e largest value
14b0: 6f 66 20 71 2e 0a 2a 2a 20 49 66 20 62 6f 74 68 of q..** If both
14c0: 20 65 6c 65 6d 65 6e 74 73 20 68 6f 6c 64 20 74 elements hold t
14d0: 68 65 20 73 61 6d 65 20 76 61 6c 75 65 2c 20 74 he same value, t
14e0: 68 65 20 70 61 74 68 20 63 6f 6d 65 73 0a 2a 2a he path comes.**
14f0: 20 74 68 72 6f 75 67 68 20 4d 5b 64 2d 31 5d 5b through M[d-1][
1500: 69 2d 31 5d 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 i-1]..**.** The
1510: 76 61 6c 75 65 20 6f 66 20 64 20 69 73 20 74 68 value of d is th
1520: 65 20 6e 75 6d 62 65 72 20 6f 66 20 69 6e 73 65 e number of inse
1530: 72 74 69 6f 6e 73 20 61 6e 64 20 64 65 6c 65 74 rtions and delet
1540: 69 6f 6e 73 0a 2a 2a 20 6d 61 64 65 20 73 6f 20 ions.** made so
1550: 66 61 72 20 6f 6e 20 74 68 65 20 70 61 74 68 2e far on the path.
1560: 20 20 4d 20 67 72 6f 77 73 20 70 72 6f 67 72 65 M grows progre
1570: 73 73 69 76 65 6c 79 2e 20 20 53 6f 20 74 68 65 ssively. So the
1580: 0a 2a 2a 20 73 69 7a 65 20 6f 66 20 74 68 65 20 .** size of the
1590: 4d 20 6d 61 74 72 69 78 20 69 73 20 70 72 6f 70 M matrix is prop
15a0: 6f 72 74 69 6f 6e 61 6c 20 74 6f 20 64 2a 64 2e ortional to d*d.
15b0: 20 20 46 6f 72 20 74 68 65 0a 2a 2a 20 63 6f 6d For the.** com
15c0: 6d 6f 6e 20 63 61 73 65 20 77 68 65 72 65 20 41 mon case where A
15d0: 20 61 6e 64 20 42 20 61 72 65 20 73 69 6d 69 6c and B are simil
15e0: 61 72 2c 20 64 20 77 69 6c 6c 20 62 65 20 73 6d ar, d will be sm
15f0: 61 6c 6c 0a 2a 2a 20 63 6f 6d 70 61 72 65 64 20 all.** compared
1600: 74 6f 20 58 20 61 6e 64 20 59 20 73 6f 20 6c 69 to X and Y so li
1610: 74 74 6c 65 20 6d 65 6d 6f 72 79 20 69 73 20 72 ttle memory is r
1620: 65 71 75 69 72 65 64 2e 20 20 54 68 65 0a 2a 2a equired. The.**
1630: 20 6f 72 69 67 69 6e 61 6c 20 57 61 67 6e 65 72 original Wagner
1640: 20 61 6c 67 6f 72 69 74 68 6d 20 72 65 71 75 69 algorithm requi
1650: 72 65 73 20 58 2a 59 20 6d 65 6d 6f 72 79 2c 20 res X*Y memory,
1660: 77 68 69 63 68 20 66 6f 72 0a 2a 2a 20 6c 61 72 which for.** lar
1670: 67 65 72 20 66 69 6c 65 73 20 28 31 30 30 4b 20 ger files (100K
1680: 6c 69 6e 65 73 29 20 69 73 20 6d 6f 72 65 20 6d lines) is more m
1690: 65 6d 6f 72 79 20 74 68 61 6e 20 77 65 20 68 61 emory than we ha
16a0: 76 65 20 61 74 0a 2a 2a 20 68 61 6e 64 2e 0a 2a ve at.** hand..*
16b0: 2f 0a 69 6e 74 20 2a 74 65 78 74 5f 64 69 66 66 /.int *text_diff
16c0: 28 42 6c 6f 62 20 2a 70 41 5f 42 6c 6f 62 2c 20 (Blob *pA_Blob,
16d0: 42 6c 6f 62 20 2a 70 42 5f 42 6c 6f 62 2c 20 42 Blob *pB_Blob, B
16e0: 6c 6f 62 20 2a 70 4f 75 74 2c 20 69 6e 74 20 6e lob *pOut, int n
16f0: 43 6f 6e 74 65 78 74 29 7b 0a 20 20 44 4c 69 6e Context){. DLin
1700: 65 20 2a 41 2c 20 2a 42 3b 20 20 20 20 2f 2a 20 e *A, *B; /*
1710: 46 69 6c 65 73 20 62 65 69 6e 67 20 63 6f 6d 70 Files being comp
1720: 61 72 65 64 20 2a 2f 0a 20 20 69 6e 74 20 58 2c ared */. int X,
1730: 20 59 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 Y; /* Nu
1740: 6d 62 65 72 20 6f 66 20 65 6c 65 6d 65 6e 74 73 mber of elements
1750: 20 69 6e 20 41 20 61 6e 64 20 42 20 2a 2f 0a 20 in A and B */.
1760: 20 69 6e 74 20 78 2c 20 79 3b 20 20 20 20 20 20 int x, y;
1770: 20 20 2f 2a 20 49 6e 64 69 63 65 73 3a 20 20 41 /* Indices: A
1780: 5b 78 5d 20 61 6e 64 20 42 5b 79 5d 20 2a 2f 0a [x] and B[y] */.
1790: 20 20 69 6e 74 20 73 7a 4d 20 3d 20 30 3b 20 20 int szM = 0;
17a0: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 /* Number of
17b0: 72 6f 77 73 20 61 6e 64 20 63 6f 6c 75 6d 6e 73 rows and columns
17c0: 20 69 6e 20 4d 20 2a 2f 0a 20 20 69 6e 74 20 2a in M */. int *
17d0: 2a 4d 20 3d 20 30 3b 20 20 20 20 20 2f 2a 20 4d *M = 0; /* M
17e0: 79 65 72 73 20 6d 61 74 72 69 78 20 2a 2f 0a 20 yers matrix */.
17f0: 20 69 6e 74 20 69 2c 20 64 3b 20 20 20 20 20 20 int i, d;
1800: 20 20 2f 2a 20 49 6e 64 69 63 65 73 20 6f 6e 20 /* Indices on
1810: 4d 2e 20 20 4d 5b 64 5d 5b 69 5d 20 2a 2f 0a 20 M. M[d][i] */.
1820: 20 69 6e 74 20 6b 2c 20 71 3b 20 20 20 20 20 20 int k, q;
1830: 20 20 2f 2a 20 44 69 61 67 6f 6e 61 6c 20 6e 75 /* Diagonal nu
1840: 6d 62 65 72 20 61 6e 64 20 64 69 73 74 69 6e 63 mber and distinc
1850: 74 20 66 72 6f 6d 20 28 30 2c 30 29 20 2a 2f 0a t from (0,0) */.
1860: 20 20 69 6e 74 20 4b 2c 20 44 3b 20 20 20 20 20 int K, D;
1870: 20 20 20 2f 2a 20 54 68 65 20 64 69 61 67 6f 6e /* The diagon
1880: 61 6c 20 61 6e 64 20 64 20 66 6f 72 20 74 68 65 al and d for the
1890: 20 66 69 6e 61 6c 20 73 6f 6c 75 74 69 6f 6e 20 final solution
18a0: 2a 2f 20 20 20 20 20 20 20 20 20 20 0a 20 20 69 */ . i
18b0: 6e 74 20 2a 52 3b 20 20 20 20 20 20 20 20 20 20 nt *R;
18c0: 2f 2a 20 52 65 73 75 6c 74 20 76 65 63 74 6f 72 /* Result vector
18d0: 20 2a 2f 0a 20 20 69 6e 74 20 72 3b 20 20 20 20 */. int r;
18e0: 20 20 20 20 20 20 20 2f 2a 20 4c 6f 6f 70 20 76 /* Loop v
18f0: 61 72 69 61 62 6c 65 73 20 2a 2f 0a 20 20 69 6e ariables */. in
1900: 74 20 67 6f 20 3d 20 31 3b 20 20 20 20 20 20 2f t go = 1; /
1910: 2a 20 4f 75 74 65 72 20 6c 6f 6f 70 20 63 6f 6e * Outer loop con
1920: 74 72 6f 6c 20 2a 2f 0a 20 20 69 6e 74 20 4d 41 trol */. int MA
1930: 58 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 4c 61 X; /* La
1940: 72 67 65 73 74 20 6f 66 20 58 20 61 6e 64 20 59 rgest of X and Y
1950: 20 2a 2f 0a 0a 20 20 2f 2a 20 42 72 65 61 6b 20 */.. /* Break
1960: 74 68 65 20 74 77 6f 20 66 69 6c 65 73 20 62 65 the two files be
1970: 69 6e 67 20 64 69 66 66 65 64 20 69 6e 74 6f 20 ing diffed into
1980: 69 6e 64 69 76 69 64 75 61 6c 20 6c 69 6e 65 73 individual lines
1990: 2e 0a 20 20 2a 2a 20 43 6f 6d 70 75 74 65 20 68 .. ** Compute h
19a0: 61 73 68 65 73 20 6f 6e 20 65 61 63 68 20 6c 69 ashes on each li
19b0: 6e 65 20 66 6f 72 20 66 61 73 74 20 63 6f 6d 70 ne for fast comp
19c0: 61 72 69 73 6f 6e 2e 0a 20 20 2a 2f 0a 20 20 41 arison.. */. A
19d0: 20 3d 20 62 72 65 61 6b 5f 69 6e 74 6f 5f 6c 69 = break_into_li
19e0: 6e 65 73 28 62 6c 6f 62 5f 73 74 72 28 70 41 5f nes(blob_str(pA_
19f0: 42 6c 6f 62 29 2c 20 26 58 29 3b 0a 20 20 42 20 Blob), &X);. B
1a00: 3d 20 62 72 65 61 6b 5f 69 6e 74 6f 5f 6c 69 6e = break_into_lin
1a10: 65 73 28 62 6c 6f 62 5f 73 74 72 28 70 42 5f 42 es(blob_str(pB_B
1a20: 6c 6f 62 29 2c 20 26 59 29 3b 0a 0a 20 20 73 7a lob), &Y);.. sz
1a30: 4d 20 3d 20 30 3b 0a 20 20 4d 41 58 20 3d 20 58 M = 0;. MAX = X
1a40: 3e 59 20 3f 20 58 20 3a 20 59 3b 0a 20 20 66 6f >Y ? X : Y;. fo
1a50: 72 28 64 3d 30 3b 20 67 6f 20 26 26 20 64 3c 3d r(d=0; go && d<=
1a60: 4d 41 58 3b 20 64 2b 2b 29 7b 0a 20 20 20 20 69 MAX; d++){. i
1a70: 66 28 20 73 7a 4d 3c 64 2b 31 20 29 7b 0a 20 20 f( szM<d+1 ){.
1a80: 20 20 20 20 73 7a 4d 20 2b 3d 20 73 7a 4d 20 2b szM += szM +
1a90: 20 31 30 3b 0a 20 20 20 20 20 20 4d 20 3d 20 72 10;. M = r
1aa0: 65 61 6c 6c 6f 63 28 4d 2c 20 73 69 7a 65 6f 66 ealloc(M, sizeof
1ab0: 28 4d 5b 30 5d 29 2a 73 7a 4d 29 3b 0a 20 20 20 (M[0])*szM);.
1ac0: 20 20 20 69 66 28 20 4d 3d 3d 30 20 29 7b 0a 20 if( M==0 ){.
1ad0: 20 20 20 20 20 20 20 66 6f 73 73 69 6c 5f 70 61 fossil_pa
1ae0: 6e 69 63 28 22 6f 75 74 20 6f 66 20 6d 65 6d 6f nic("out of memo
1af0: 72 79 22 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 ry");. }.
1b00: 20 20 7d 0a 20 20 20 20 4d 5b 64 5d 20 3d 20 6d }. M[d] = m
1b10: 61 6c 6c 6f 63 28 20 73 69 7a 65 6f 66 28 4d 5b alloc( sizeof(M[
1b20: 64 5d 5b 30 5d 29 2a 28 64 2b 31 29 20 29 3b 0a d][0])*(d+1) );.
1b30: 20 20 20 20 69 66 28 20 4d 5b 64 5d 3d 3d 30 20 if( M[d]==0
1b40: 29 7b 0a 20 20 20 20 20 20 66 6f 73 73 69 6c 5f ){. fossil_
1b50: 70 61 6e 69 63 28 22 6f 75 74 20 6f 66 20 6d 65 panic("out of me
1b60: 6d 6f 72 79 22 29 3b 0a 20 20 20 20 7d 0a 20 20 mory");. }.
1b70: 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 3d 64 3b for(i=0; i<=d;
1b80: 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 6b 20 3d i++){. k =
1b90: 20 32 2a 69 20 2d 20 64 3b 0a 20 20 20 20 20 20 2*i - d;.
1ba0: 69 66 28 20 64 3d 3d 30 20 29 7b 0a 20 20 20 20 if( d==0 ){.
1bb0: 20 20 20 20 71 20 3d 20 30 3b 0a 20 20 20 20 20 q = 0;.
1bc0: 20 7d 65 6c 73 65 20 69 66 28 20 69 3d 3d 30 20 }else if( i==0
1bd0: 29 7b 0a 20 20 20 20 20 20 20 20 71 20 3d 20 4d ){. q = M
1be0: 5b 64 2d 31 5d 5b 30 5d 3b 0a 20 20 20 20 20 20 [d-1][0];.
1bf0: 7d 65 6c 73 65 20 69 66 28 20 4d 5b 64 2d 31 5d }else if( M[d-1]
1c00: 5b 69 2d 31 5d 20 3c 20 4d 5b 64 2d 31 5d 5b 69 [i-1] < M[d-1][i
1c10: 5d 20 29 7b 0a 20 20 20 20 20 20 20 20 71 20 3d ] ){. q =
1c20: 20 4d 5b 64 2d 31 5d 5b 69 5d 3b 0a 20 20 20 20 M[d-1][i];.
1c30: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 }else{.
1c40: 20 71 20 3d 20 4d 5b 64 2d 31 5d 5b 69 2d 31 5d q = M[d-1][i-1]
1c50: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 ;. }.
1c60: 78 20 3d 20 28 6b 20 2b 20 71 20 2b 20 31 29 2f x = (k + q + 1)/
1c70: 32 3b 0a 20 20 20 20 20 20 79 20 3d 20 78 20 2d 2;. y = x -
1c80: 20 6b 3b 0a 20 20 20 20 20 20 69 66 28 20 78 3c k;. if( x<
1c90: 30 20 7c 7c 20 78 3e 58 20 7c 7c 20 79 3c 30 20 0 || x>X || y<0
1ca0: 7c 7c 20 79 3e 59 20 29 7b 0a 20 20 20 20 20 20 || y>Y ){.
1cb0: 20 20 78 20 3d 20 79 20 3d 20 30 3b 0a 20 20 20 x = y = 0;.
1cc0: 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 }else{.
1cd0: 20 20 77 68 69 6c 65 28 20 78 3c 58 20 26 26 20 while( x<X &&
1ce0: 79 3c 59 20 26 26 20 73 61 6d 65 5f 64 6c 69 6e y<Y && same_dlin
1cf0: 65 28 26 41 5b 78 5d 2c 26 42 5b 79 5d 29 20 29 e(&A[x],&B[y]) )
1d00: 7b 20 78 2b 2b 3b 20 79 2b 2b 3b 20 7d 0a 20 20 { x++; y++; }.
1d10: 20 20 20 20 7d 0a 20 20 20 20 20 20 4d 5b 64 5d }. M[d]
1d20: 5b 69 5d 20 3d 20 78 20 2b 20 79 3b 0a 20 20 20 [i] = x + y;.
1d30: 20 20 20 2f 2a 20 70 72 69 6e 74 66 28 22 4d 5b /* printf("M[
1d40: 25 64 5d 5b 25 69 5d 20 3d 20 25 64 20 20 6b 3d %d][%i] = %d k=
1d50: 25 64 20 28 25 64 2c 25 64 29 5c 6e 22 2c 20 64 %d (%d,%d)\n", d
1d60: 2c 20 69 2c 20 78 2b 79 2c 20 6b 2c 20 78 2c 20 , i, x+y, k, x,
1d70: 79 29 3b 20 2a 2f 0a 20 20 20 20 20 20 69 66 28 y); */. if(
1d80: 20 78 3d 3d 58 20 26 26 20 79 3d 3d 59 20 29 7b x==X && y==Y ){
1d90: 0a 20 20 20 20 20 20 20 20 67 6f 20 3d 20 30 3b . go = 0;
1da0: 0a 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a . break;.
1db0: 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 }. }.
1dc0: 7d 0a 20 20 69 66 28 20 64 3e 4d 41 58 20 29 7b }. if( d>MAX ){
1dd0: 0a 20 20 20 20 52 20 3d 20 6d 61 6c 6c 6f 63 28 . R = malloc(
1de0: 20 73 69 7a 65 6f 66 28 52 5b 30 5d 29 2a 36 20 sizeof(R[0])*6
1df0: 29 3b 0a 20 20 20 20 52 5b 30 5d 20 3d 20 30 3b );. R[0] = 0;
1e00: 0a 20 20 20 20 52 5b 31 5d 20 3d 20 58 3b 0a 20 . R[1] = X;.
1e10: 20 20 20 52 5b 32 5d 20 3d 20 59 3b 0a 20 20 20 R[2] = Y;.
1e20: 20 52 5b 33 5d 20 3d 20 30 3b 0a 20 20 20 20 52 R[3] = 0;. R
1e30: 5b 34 5d 20 3d 20 30 3b 0a 20 20 20 20 52 5b 35 [4] = 0;. R[5
1e40: 5d 20 3d 20 30 3b 0a 20 20 7d 65 6c 73 65 7b 0a ] = 0;. }else{.
1e50: 20 20 20 20 2f 2a 20 52 65 75 73 65 20 4d 5b 5d /* Reuse M[]
1e60: 20 61 73 20 66 6f 6c 6c 6f 77 73 3a 0a 20 20 20 as follows:.
1e70: 20 2a 2a 0a 20 20 20 20 2a 2a 20 20 20 20 20 4d **. ** M
1e80: 5b 64 5d 5b 31 5d 20 3d 20 31 20 69 66 20 61 20 [d][1] = 1 if a
1e90: 6c 69 6e 65 20 69 73 20 69 6e 73 65 72 74 65 64 line is inserted
1ea0: 20 6f 72 20 30 20 69 66 20 61 20 6c 69 6e 65 20 or 0 if a line
1eb0: 69 73 20 64 65 6c 65 74 65 64 2e 0a 20 20 20 20 is deleted..
1ec0: 2a 2a 20 20 20 20 20 4d 5b 64 5d 5b 30 5d 20 3d ** M[d][0] =
1ed0: 20 6e 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 number of lines
1ee0: 20 63 6f 70 69 65 64 20 61 66 74 65 72 20 74 68 copied after th
1ef0: 65 20 69 6e 73 20 6f 72 20 64 65 6c 20 61 62 6f e ins or del abo
1f00: 76 65 2e 0a 20 20 20 20 2a 2a 0a 20 20 20 20 2a ve.. **. *
1f10: 2f 0a 20 20 20 20 44 20 3d 20 64 20 2d 20 31 3b /. D = d - 1;
1f20: 0a 20 20 20 20 4b 20 3d 20 58 20 2d 20 59 3b 0a . K = X - Y;.
1f30: 20 20 20 20 66 6f 72 28 64 3d 44 2c 20 69 3d 28 for(d=D, i=(
1f40: 4b 2b 44 29 2f 32 3b 20 64 3e 30 3b 20 64 2d 2d K+D)/2; d>0; d--
1f50: 29 7b 0a 20 20 20 20 20 20 2f 2a 20 70 72 69 6e ){. /* prin
1f60: 74 66 28 22 64 3d 25 64 20 69 3d 25 64 5c 6e 22 tf("d=%d i=%d\n"
1f70: 2c 20 64 2c 20 69 29 3b 20 2a 2f 0a 20 20 20 20 , d, i); */.
1f80: 20 20 69 66 28 20 69 3d 3d 64 20 7c 7c 20 28 69 if( i==d || (i
1f90: 3e 30 20 26 26 20 4d 5b 64 2d 31 5d 5b 69 2d 31 >0 && M[d-1][i-1
1fa0: 5d 20 3e 20 4d 5b 64 2d 31 5d 5b 69 5d 29 20 29 ] > M[d-1][i]) )
1fb0: 7b 0a 20 20 20 20 20 20 20 20 4d 5b 64 5d 5b 30 {. M[d][0
1fc0: 5d 20 3d 20 4d 5b 64 5d 5b 69 5d 20 2d 20 4d 5b ] = M[d][i] - M[
1fd0: 64 2d 31 5d 5b 69 2d 31 5d 20 2d 20 31 3b 0a 20 d-1][i-1] - 1;.
1fe0: 20 20 20 20 20 20 20 4d 5b 64 5d 5b 31 5d 20 3d M[d][1] =
1ff0: 20 30 3b 0a 20 20 20 20 20 20 20 20 69 2d 2d 3b 0;. i--;
2000: 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 . }else{.
2010: 20 20 20 20 20 20 4d 5b 64 5d 5b 30 5d 20 3d 20 M[d][0] =
2020: 4d 5b 64 5d 5b 69 5d 20 2d 20 4d 5b 64 2d 31 5d M[d][i] - M[d-1]
2030: 5b 69 5d 20 2d 20 31 3b 0a 20 20 20 20 20 20 20 [i] - 1;.
2040: 20 4d 5b 64 5d 5b 31 5d 20 3d 20 31 3b 0a 20 20 M[d][1] = 1;.
2050: 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 }. }.
2060: 0a 20 20 20 20 0a 20 20 20 20 2f 2a 0a 20 20 20 . . /*.
2070: 20 70 72 69 6e 74 66 28 22 2d 2d 2d 2d 2d 2d 2d printf("-------
2080: 2d 2d 2d 2d 2d 2d 2d 2d 5c 6e 4d 5b 30 5d 5b 30 --------\nM[0][0
2090: 5d 20 3d 20 25 35 64 5c 6e 22 2c 20 4d 5b 30 5d ] = %5d\n", M[0]
20a0: 5b 30 5d 29 3b 0a 20 20 20 20 66 6f 72 28 64 3d [0]);. for(d=
20b0: 31 3b 20 64 3c 3d 44 3b 20 64 2b 2b 29 7b 0a 20 1; d<=D; d++){.
20c0: 20 20 20 20 20 70 72 69 6e 74 66 28 22 4d 5b 25 printf("M[%
20d0: 64 5d 5b 30 5d 20 3d 20 25 35 64 20 20 20 20 4d d][0] = %5d M
20e0: 5b 25 64 5d 5b 31 5d 20 3d 20 25 64 5c 6e 22 2c [%d][1] = %d\n",
20f0: 64 2c 4d 5b 64 5d 5b 30 5d 2c 64 2c 4d 5b 64 5d d,M[d][0],d,M[d]
2100: 5b 31 5d 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 [1]);. }.
2110: 2a 2f 0a 20 20 20 20 0a 20 20 20 20 2f 2a 20 41 */. . /* A
2120: 6c 6c 6f 63 61 74 65 20 74 68 65 20 6f 75 74 70 llocate the outp
2130: 75 74 20 76 65 63 74 6f 72 0a 20 20 20 20 2a 2f ut vector. */
2140: 0a 20 20 20 20 52 20 3d 20 6d 61 6c 6c 6f 63 28 . R = malloc(
2150: 20 73 69 7a 65 6f 66 28 52 5b 30 5d 29 2a 28 44 sizeof(R[0])*(D
2160: 2b 32 29 2a 33 20 29 3b 0a 20 20 20 20 69 66 28 +2)*3 );. if(
2170: 20 52 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 66 R==0 ){. f
2180: 6f 73 73 69 6c 5f 66 61 74 61 6c 28 22 6f 75 74 ossil_fatal("out
2190: 20 6f 66 20 6d 65 6d 6f 72 79 22 29 3b 0a 20 20 of memory");.
21a0: 20 20 7d 0a 20 20 20 20 0a 20 20 20 20 2f 2a 20 }. . /*
21b0: 50 6f 70 75 6c 61 74 65 20 74 68 65 20 6f 75 74 Populate the out
21c0: 70 75 74 20 76 65 63 74 6f 72 0a 20 20 20 20 2a put vector. *
21d0: 2f 0a 20 20 20 20 64 20 3d 20 72 20 3d 20 30 3b /. d = r = 0;
21e0: 0a 20 20 20 20 77 68 69 6c 65 28 20 64 3c 3d 44 . while( d<=D
21f0: 20 29 7b 0a 20 20 20 20 20 20 69 6e 74 20 6e 3b ){. int n;
2200: 0a 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 . R[r++] =
2210: 4d 5b 64 2b 2b 5d 5b 30 5d 2f 32 3b 20 20 20 2f M[d++][0]/2; /
2220: 2a 20 43 4f 50 59 20 2a 2f 0a 20 20 20 20 20 20 * COPY */.
2230: 69 66 28 20 64 3e 44 20 29 7b 0a 20 20 20 20 20 if( d>D ){.
2240: 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 0a 20 R[r++] = 0;.
2250: 20 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 R[r++] =
2260: 30 3b 0a 20 20 20 20 20 20 20 20 62 72 65 61 6b 0;. break
2270: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 ;. }.
2280: 69 66 28 20 4d 5b 64 5d 5b 31 5d 3d 3d 30 20 29 if( M[d][1]==0 )
2290: 7b 0a 20 20 20 20 20 20 20 20 6e 20 3d 20 31 3b {. n = 1;
22a0: 0a 20 20 20 20 20 20 20 20 77 68 69 6c 65 28 20 . while(
22b0: 4d 5b 64 5d 5b 30 5d 3d 3d 30 20 26 26 20 64 3c M[d][0]==0 && d<
22c0: 44 20 26 26 20 4d 5b 64 2b 31 5d 5b 31 5d 3d 3d D && M[d+1][1]==
22d0: 30 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 64 0 ){. d
22e0: 2b 2b 3b 0a 20 20 20 20 20 20 20 20 20 20 6e 2b ++;. n+
22f0: 2b 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 +;. }.
2300: 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 6e 3b R[r++] = n;
2310: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44 45 /* DE
2320: 4c 45 54 45 20 2a 2f 0a 20 20 20 20 20 20 20 20 LETE */.
2330: 69 66 28 20 64 3d 3d 44 20 7c 7c 20 4d 5b 64 5d if( d==D || M[d]
2340: 5b 30 5d 3e 30 20 29 7b 0a 20 20 20 20 20 20 20 [0]>0 ){.
2350: 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 20 20 R[r++] = 0;
2360: 20 20 20 20 20 20 20 2f 2a 20 49 4e 53 45 52 54 /* INSERT
2370: 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 63 6f */. co
2380: 6e 74 69 6e 75 65 3b 0a 20 20 20 20 20 20 20 20 ntinue;.
2390: 7d 0a 20 20 20 20 20 20 20 20 64 2b 2b 3b 0a 20 }. d++;.
23a0: 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 }else{.
23b0: 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 20 R[r++] = 0;
23c0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44 45 4c /* DEL
23d0: 45 54 45 20 2a 2f 0a 20 20 20 20 20 20 7d 0a 20 ETE */. }.
23e0: 20 20 20 20 20 61 73 73 65 72 74 28 20 4d 5b 64 assert( M[d
23f0: 5d 5b 31 5d 3d 3d 31 20 29 3b 0a 20 20 20 20 20 ][1]==1 );.
2400: 20 6e 20 3d 20 31 3b 0a 20 20 20 20 20 20 77 68 n = 1;. wh
2410: 69 6c 65 28 20 4d 5b 64 5d 5b 30 5d 3d 3d 30 20 ile( M[d][0]==0
2420: 26 26 20 64 3c 44 20 26 26 20 4d 5b 64 2b 31 5d && d<D && M[d+1]
2430: 5b 31 5d 3d 3d 31 20 29 7b 0a 20 20 20 20 20 20 [1]==1 ){.
2440: 20 20 64 2b 2b 3b 0a 20 20 20 20 20 20 20 20 6e d++;. n
2450: 2b 2b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 ++;. }.
2460: 20 20 52 5b 72 2b 2b 5d 20 3d 20 6e 3b 20 20 20 R[r++] = n;
2470: 20 20 20 20 20 20 20 20 20 2f 2a 20 49 4e 53 45 /* INSE
2480: 52 54 20 2a 2f 0a 20 20 20 20 7d 0a 20 20 20 20 RT */. }.
2490: 52 5b 72 2b 2b 5d 20 3d 20 30 3b 0a 20 20 20 20 R[r++] = 0;.
24a0: 52 5b 72 2b 2b 5d 20 3d 20 30 3b 0a 20 20 20 20 R[r++] = 0;.
24b0: 52 5b 72 2b 2b 5d 20 3d 20 30 3b 0a 20 20 7d 0a R[r++] = 0;. }.
24c0: 20 20 20 20 0a 20 20 2f 2a 20 46 72 65 65 20 74 . /* Free t
24d0: 68 65 20 4d 79 65 72 73 20 6d 61 74 72 69 78 20 he Myers matrix
24e0: 2a 2f 0a 20 20 66 6f 72 28 64 3d 30 3b 20 64 3c */. for(d=0; d<
24f0: 3d 44 3b 20 64 2b 2b 29 7b 0a 20 20 20 20 66 72 =D; d++){. fr
2500: 65 65 28 4d 5b 64 5d 29 3b 0a 20 20 7d 0a 20 20 ee(M[d]);. }.
2510: 66 72 65 65 28 4d 29 3b 0a 0a 20 20 2f 2a 20 49 free(M);.. /* I
2520: 66 20 70 4f 75 74 20 69 73 20 64 65 66 69 6e 65 f pOut is define
2530: 64 2c 20 63 6f 6e 73 74 72 75 63 74 20 61 20 75 d, construct a u
2540: 6e 69 66 69 65 64 20 64 69 66 66 20 69 6e 74 6f nified diff into
2550: 20 70 4f 75 74 20 61 6e 64 0a 20 20 2a 2a 20 64 pOut and. ** d
2560: 65 6c 65 74 65 20 52 0a 20 20 2a 2f 0a 20 20 69 elete R. */. i
2570: 66 28 20 70 4f 75 74 20 29 7b 0a 20 20 20 20 69 f( pOut ){. i
2580: 6e 74 20 61 20 3d 20 30 3b 20 20 20 20 2f 2a 20 nt a = 0; /*
2590: 49 6e 64 65 78 20 6f 66 20 6e 65 78 74 20 6c 69 Index of next li
25a0: 6e 65 20 69 6e 20 41 5b 5d 20 2a 2f 0a 20 20 20 ne in A[] */.
25b0: 20 69 6e 74 20 62 20 3d 20 30 3b 20 20 20 20 2f int b = 0; /
25c0: 2a 20 49 6e 64 65 78 20 6f 66 20 6e 65 78 74 20 * Index of next
25d0: 6c 69 6e 65 20 69 6e 20 42 5b 5d 20 2a 2f 0a 20 line in B[] */.
25e0: 20 20 20 69 6e 74 20 6e 72 3b 20 20 20 20 20 20 int nr;
25f0: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 43 4f /* Number of CO
2600: 50 59 2f 44 45 4c 45 54 45 2f 49 4e 53 45 52 54 PY/DELETE/INSERT
2610: 20 74 72 69 70 6c 65 73 20 74 6f 20 70 72 6f 63 triples to proc
2620: 65 73 73 20 2a 2f 0a 20 20 20 20 69 6e 74 20 6e ess */. int n
2630: 61 2c 20 6e 62 3b 20 20 20 2f 2a 20 4e 75 6d 62 a, nb; /* Numb
2640: 65 72 20 6f 66 20 6c 69 6e 65 73 20 73 68 6f 77 er of lines show
2650: 6e 20 66 72 6f 6d 20 41 20 61 6e 64 20 42 20 2a n from A and B *
2660: 2f 0a 20 20 20 20 69 6e 74 20 69 2c 20 6a 3b 20 /. int i, j;
2670: 20 20 20 20 2f 2a 20 4c 6f 6f 70 20 63 6f 75 6e /* Loop coun
2680: 74 65 72 73 20 2a 2f 0a 20 20 20 20 69 6e 74 20 ters */. int
2690: 6d 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d m; /* Num
26a0: 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 74 6f 20 ber of lines to
26b0: 6f 75 74 70 75 74 20 2a 2f 0a 20 20 20 20 69 6e output */. in
26c0: 74 20 73 6b 69 70 3b 20 20 20 20 20 2f 2a 20 4e t skip; /* N
26d0: 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 74 umber of lines t
26e0: 6f 20 73 6b 69 70 20 2a 2f 0a 0a 20 20 20 20 66 o skip */.. f
26f0: 6f 72 28 72 3d 30 3b 20 52 5b 72 2b 31 5d 20 7c or(r=0; R[r+1] |
2700: 7c 20 52 5b 72 2b 32 5d 20 7c 7c 20 52 5b 72 2b | R[r+2] || R[r+
2710: 33 5d 3b 20 72 20 2b 3d 20 33 2a 6e 72 29 7b 0a 3]; r += 3*nr){.
2720: 20 20 20 20 20 20 2f 2a 20 46 69 67 75 72 65 20 /* Figure
2730: 6f 75 74 20 68 6f 77 20 6d 61 6e 79 20 74 72 69 out how many tri
2740: 70 6c 65 73 20 74 6f 20 73 68 6f 77 20 69 6e 20 ples to show in
2750: 61 20 73 69 6e 67 6c 65 20 62 6c 6f 63 6b 20 2a a single block *
2760: 2f 0a 20 20 20 20 20 20 66 6f 72 28 6e 72 3d 31 /. for(nr=1
2770: 3b 20 52 5b 72 2b 6e 72 2a 33 5d 3e 30 20 26 26 ; R[r+nr*3]>0 &&
2780: 20 52 5b 72 2b 6e 72 2a 33 5d 3c 6e 43 6f 6e 74 R[r+nr*3]<nCont
2790: 65 78 74 2a 32 3b 20 6e 72 2b 2b 29 7b 7d 0a 20 ext*2; nr++){}.
27a0: 20 20 20 20 20 2f 2a 20 70 72 69 6e 74 66 28 22 /* printf("
27b0: 72 3d 25 64 20 6e 72 3d 25 64 5c 6e 22 2c 20 72 r=%d nr=%d\n", r
27c0: 2c 20 6e 72 29 3b 20 2a 2f 0a 0a 20 20 20 20 20 , nr); */..
27d0: 20 2f 2a 20 46 6f 72 20 74 68 65 20 63 75 72 72 /* For the curr
27e0: 65 6e 74 20 62 6c 6f 63 6b 20 63 6f 6d 70 72 69 ent block compri
27f0: 73 69 6e 67 20 6e 72 20 74 72 69 70 6c 65 73 2c sing nr triples,
2800: 20 66 69 67 75 72 65 20 6f 75 74 0a 20 20 20 20 figure out.
2810: 20 20 2a 2a 20 68 6f 77 20 6d 61 6e 79 20 6c 69 ** how many li
2820: 6e 65 73 20 6f 66 20 41 20 61 6e 64 20 42 20 61 nes of A and B a
2830: 72 65 20 74 6f 20 62 65 20 64 69 73 70 6c 61 79 re to be display
2840: 65 64 0a 20 20 20 20 20 20 2a 2f 0a 20 20 20 20 ed. */.
2850: 20 20 69 66 28 20 52 5b 72 5d 3e 6e 43 6f 6e 74 if( R[r]>nCont
2860: 65 78 74 20 29 7b 0a 20 20 20 20 20 20 20 20 6e ext ){. n
2870: 61 20 3d 20 6e 62 20 3d 20 6e 43 6f 6e 74 65 78 a = nb = nContex
2880: 74 3b 0a 20 20 20 20 20 20 20 20 73 6b 69 70 20 t;. skip
2890: 3d 20 52 5b 72 5d 20 2d 20 6e 43 6f 6e 74 65 78 = R[r] - nContex
28a0: 74 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a t;. }else{.
28b0: 20 20 20 20 20 20 20 20 6e 61 20 3d 20 6e 62 20 na = nb
28c0: 3d 20 52 5b 72 5d 3b 0a 20 20 20 20 20 20 20 20 = R[r];.
28d0: 73 6b 69 70 20 3d 20 30 3b 0a 20 20 20 20 20 20 skip = 0;.
28e0: 7d 0a 20 20 20 20 20 20 66 6f 72 28 69 3d 30 3b }. for(i=0;
28f0: 20 69 3c 6e 72 3b 20 69 2b 2b 29 7b 0a 20 20 20 i<nr; i++){.
2900: 20 20 20 20 20 6e 61 20 2b 3d 20 52 5b 72 2b 69 na += R[r+i
2910: 2a 33 2b 31 5d 3b 0a 20 20 20 20 20 20 20 20 6e *3+1];. n
2920: 62 20 2b 3d 20 52 5b 72 2b 69 2a 33 2b 32 5d 3b b += R[r+i*3+2];
2930: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 69 . }. i
2940: 66 28 20 52 5b 72 2b 6e 72 2a 33 5d 3e 6e 43 6f f( R[r+nr*3]>nCo
2950: 6e 74 65 78 74 20 29 7b 0a 20 20 20 20 20 20 20 ntext ){.
2960: 20 6e 61 20 2b 3d 20 6e 43 6f 6e 74 65 78 74 3b na += nContext;
2970: 0a 20 20 20 20 20 20 20 20 6e 62 20 2b 3d 20 6e . nb += n
2980: 43 6f 6e 74 65 78 74 3b 0a 20 20 20 20 20 20 7d Context;. }
2990: 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 6e 61 else{. na
29a0: 20 2b 3d 20 52 5b 72 2b 6e 72 2a 33 5d 3b 0a 20 += R[r+nr*3];.
29b0: 20 20 20 20 20 20 20 6e 62 20 2b 3d 20 52 5b 72 nb += R[r
29c0: 2b 6e 72 2a 33 5d 3b 0a 20 20 20 20 20 20 7d 0a +nr*3];. }.
29d0: 20 20 20 20 20 20 66 6f 72 28 69 3d 31 3b 20 69 for(i=1; i
29e0: 3c 6e 72 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 <nr; i++){.
29f0: 20 20 20 6e 61 20 2b 3d 20 52 5b 72 2b 69 2a 33 na += R[r+i*3
2a00: 5d 3b 0a 20 20 20 20 20 20 20 20 6e 62 20 2b 3d ];. nb +=
2a10: 20 52 5b 72 2b 69 2a 33 5d 3b 0a 20 20 20 20 20 R[r+i*3];.
2a20: 20 7d 0a 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 }. blob_ap
2a30: 70 65 6e 64 66 28 70 4f 75 74 2c 22 40 40 20 2d pendf(pOut,"@@ -
2a40: 25 64 2c 25 64 20 2b 25 64 2c 25 64 20 40 40 5c %d,%d +%d,%d @@\
2a50: 6e 22 2c 20 61 2b 73 6b 69 70 2b 31 2c 20 6e 61 n", a+skip+1, na
2a60: 2c 20 62 2b 73 6b 69 70 2b 31 2c 20 6e 62 29 3b , b+skip+1, nb);
2a70: 0a 0a 20 20 20 20 20 20 2f 2a 20 53 68 6f 77 20 .. /* Show
2a80: 74 68 65 20 69 6e 69 74 69 61 6c 20 63 6f 6d 6d the initial comm
2a90: 6f 6e 20 61 72 65 61 20 2a 2f 0a 20 20 20 20 20 on area */.
2aa0: 20 61 20 2b 3d 20 73 6b 69 70 3b 0a 20 20 20 20 a += skip;.
2ab0: 20 20 62 20 2b 3d 20 73 6b 69 70 3b 0a 20 20 20 b += skip;.
2ac0: 20 20 20 6d 20 3d 20 52 5b 72 5d 20 2d 20 73 6b m = R[r] - sk
2ad0: 69 70 3b 0a 20 20 20 20 20 20 66 6f 72 28 6a 3d ip;. for(j=
2ae0: 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 0; j<m; j++){.
2af0: 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 6e blob_appen
2b00: 64 66 28 70 4f 75 74 2c 22 20 25 73 5c 6e 22 2c df(pOut," %s\n",
2b10: 20 41 5b 61 2b 6a 5d 2e 7a 29 3b 0a 20 20 20 20 A[a+j].z);.
2b20: 20 20 7d 0a 20 20 20 20 20 20 61 20 2b 3d 20 6d }. a += m
2b30: 3b 0a 20 20 20 20 20 20 62 20 2b 3d 20 6d 3b 0a ;. b += m;.
2b40: 0a 20 20 20 20 20 20 2f 2a 20 53 68 6f 77 20 74 . /* Show t
2b50: 68 65 20 64 69 66 66 65 72 65 6e 63 65 73 20 2a he differences *
2b60: 2f 0a 20 20 20 20 20 20 66 6f 72 28 69 3d 30 3b /. for(i=0;
2b70: 20 69 3c 6e 72 3b 20 69 2b 2b 29 7b 0a 20 20 20 i<nr; i++){.
2b80: 20 20 20 20 20 6d 20 3d 20 52 5b 72 2b 69 2a 33 m = R[r+i*3
2b90: 2b 31 5d 3b 0a 20 20 20 20 20 20 20 20 66 6f 72 +1];. for
2ba0: 28 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b (j=0; j<m; j++){
2bb0: 0a 20 20 20 20 20 20 20 20 20 20 62 6c 6f 62 5f . blob_
2bc0: 61 70 70 65 6e 64 66 28 70 4f 75 74 2c 22 2d 25 appendf(pOut,"-%
2bd0: 73 5c 6e 22 2c 20 41 5b 61 2b 6a 5d 2e 7a 29 3b s\n", A[a+j].z);
2be0: 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 . }.
2bf0: 20 20 20 61 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 a += m;.
2c00: 20 20 20 6d 20 3d 20 52 5b 72 2b 69 2a 33 2b 32 m = R[r+i*3+2
2c10: 5d 3b 0a 20 20 20 20 20 20 20 20 66 6f 72 28 6a ];. for(j
2c20: 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 =0; j<m; j++){.
2c30: 20 20 20 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 blob_ap
2c40: 70 65 6e 64 66 28 70 4f 75 74 2c 22 2b 25 73 5c pendf(pOut,"+%s\
2c50: 6e 22 2c 20 42 5b 62 2b 6a 5d 2e 7a 29 3b 0a 20 n", B[b+j].z);.
2c60: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 }.
2c70: 20 62 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 20 20 b += m;.
2c80: 20 69 66 28 20 69 3c 6e 72 2d 31 20 29 7b 0a 20 if( i<nr-1 ){.
2c90: 20 20 20 20 20 20 20 20 20 6d 20 3d 20 52 5b 72 m = R[r
2ca0: 2b 69 2a 33 2b 33 5d 3b 0a 20 20 20 20 20 20 20 +i*3+3];.
2cb0: 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c 6d 3b for(j=0; j<m;
2cc0: 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 20 j++){.
2cd0: 20 20 20 62 6c 6f 62 5f 61 70 70 65 6e 64 66 28 blob_appendf(
2ce0: 70 4f 75 74 2c 22 20 25 73 5c 6e 22 2c 20 42 5b pOut," %s\n", B[
2cf0: 62 2b 6a 5d 2e 7a 29 3b 0a 20 20 20 20 20 20 20 b+j].z);.
2d00: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 62 }. b
2d10: 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 20 20 20 20 += m;.
2d20: 20 61 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 20 20 a += m;.
2d30: 20 7d 0a 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 }. }..
2d40: 20 20 2f 2a 20 53 68 6f 77 20 74 68 65 20 66 69 /* Show the fi
2d50: 6e 61 6c 20 63 6f 6d 6d 6f 6e 20 61 72 65 61 20 nal common area
2d60: 2a 2f 0a 20 20 20 20 20 20 61 73 73 65 72 74 28 */. assert(
2d70: 20 6e 72 3d 3d 69 20 29 3b 0a 20 20 20 20 20 20 nr==i );.
2d80: 6d 20 3d 20 52 5b 72 2b 6e 72 2a 33 5d 3b 0a 20 m = R[r+nr*3];.
2d90: 20 20 20 20 20 69 66 28 20 6d 3e 6e 43 6f 6e 74 if( m>nCont
2da0: 65 78 74 20 29 20 6d 20 3d 20 6e 43 6f 6e 74 65 ext ) m = nConte
2db0: 78 74 3b 0a 20 20 20 20 20 20 66 6f 72 28 6a 3d xt;. for(j=
2dc0: 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 0; j<m; j++){.
2dd0: 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 6e blob_appen
2de0: 64 66 28 70 4f 75 74 2c 22 20 25 73 5c 6e 22 2c df(pOut," %s\n",
2df0: 20 42 5b 62 2b 6a 5d 2e 7a 29 3b 0a 20 20 20 20 B[b+j].z);.
2e00: 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 66 72 }. }. fr
2e10: 65 65 28 52 29 3b 0a 20 20 20 20 52 20 3d 20 30 ee(R);. R = 0
2e20: 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 57 65 20 6e ;. }.. /* We n
2e30: 6f 20 6c 6f 6e 67 65 72 20 6e 65 65 64 20 74 68 o longer need th
2e40: 65 20 41 5b 5d 20 61 6e 64 20 42 5b 5d 20 76 65 e A[] and B[] ve
2e50: 63 74 6f 72 73 20 2a 2f 0a 20 20 66 72 65 65 28 ctors */. free(
2e60: 41 29 3b 0a 20 20 66 72 65 65 28 42 29 3b 0a 0a A);. free(B);..
2e70: 20 20 2f 2a 20 52 65 74 75 72 6e 20 74 68 65 20 /* Return the
2e80: 72 65 73 75 6c 74 20 2a 2f 0a 20 20 72 65 74 75 result */. retu
2e90: 72 6e 20 52 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 rn R;.}../*.** C
2ea0: 4f 4d 4d 41 4e 44 3a 20 74 65 73 74 2d 72 61 77 OMMAND: test-raw
2eb0: 64 69 66 66 0a 2a 2f 0a 76 6f 69 64 20 74 65 73 diff.*/.void tes
2ec0: 74 5f 72 61 77 64 69 66 66 5f 63 6d 64 28 76 6f t_rawdiff_cmd(vo
2ed0: 69 64 29 7b 0a 20 20 42 6c 6f 62 20 61 2c 20 62 id){. Blob a, b
2ee0: 3b 0a 20 20 69 6e 74 20 72 3b 0a 20 20 69 6e 74 ;. int r;. int
2ef0: 20 2a 52 3b 0a 20 20 69 66 28 20 67 2e 61 72 67 *R;. if( g.arg
2f00: 63 21 3d 34 20 29 20 75 73 61 67 65 28 22 46 49 c!=4 ) usage("FI
2f10: 4c 45 31 20 46 49 4c 45 32 22 29 3b 0a 20 20 62 LE1 FILE2");. b
2f20: 6c 6f 62 5f 72 65 61 64 5f 66 72 6f 6d 5f 66 69 lob_read_from_fi
2f30: 6c 65 28 26 61 2c 20 67 2e 61 72 67 76 5b 32 5d le(&a, g.argv[2]
2f40: 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 61 64 5f 66 );. blob_read_f
2f50: 72 6f 6d 5f 66 69 6c 65 28 26 62 2c 20 67 2e 61 rom_file(&b, g.a
2f60: 72 67 76 5b 33 5d 29 3b 0a 20 20 52 20 3d 20 74 rgv[3]);. R = t
2f70: 65 78 74 5f 64 69 66 66 28 26 61 2c 20 26 62 2c ext_diff(&a, &b,
2f80: 20 30 2c 20 30 29 3b 0a 20 20 66 6f 72 28 72 3d 0, 0);. for(r=
2f90: 30 3b 20 52 5b 72 5d 20 7c 7c 20 52 5b 72 2b 31 0; R[r] || R[r+1
2fa0: 5d 20 7c 7c 20 52 5b 72 2b 32 5d 3b 20 72 20 2b ] || R[r+2]; r +
2fb0: 3d 20 33 29 7b 0a 20 20 20 20 70 72 69 6e 74 66 = 3){. printf
2fc0: 28 22 20 63 6f 70 79 20 25 34 64 20 20 64 65 6c (" copy %4d del
2fd0: 65 74 65 20 25 34 64 20 20 69 6e 73 65 72 74 20 ete %4d insert
2fe0: 25 34 64 5c 6e 22 2c 20 52 5b 72 5d 2c 20 52 5b %4d\n", R[r], R[
2ff0: 72 2b 31 5d 2c 20 52 5b 72 2b 32 5d 29 3b 0a 20 r+1], R[r+2]);.
3000: 20 7d 0a 20 20 66 72 65 65 28 52 29 3b 0a 7d 0a }. free(R);.}.
3010: 0a 2f 2a 0a 2a 2a 20 43 4f 4d 4d 41 4e 44 3a 20 ./*.** COMMAND:
3020: 74 65 73 74 2d 75 64 69 66 66 0a 2a 2f 0a 76 6f test-udiff.*/.vo
3030: 69 64 20 74 65 73 74 5f 75 64 69 66 66 5f 63 6d id test_udiff_cm
3040: 64 28 76 6f 69 64 29 7b 0a 20 20 42 6c 6f 62 20 d(void){. Blob
3050: 61 2c 20 62 2c 20 6f 75 74 3b 0a 20 20 69 66 28 a, b, out;. if(
3060: 20 67 2e 61 72 67 63 21 3d 34 20 29 20 75 73 61 g.argc!=4 ) usa
3070: 67 65 28 22 46 49 4c 45 31 20 46 49 4c 45 32 22 ge("FILE1 FILE2"
3080: 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 61 64 5f 66 );. blob_read_f
3090: 72 6f 6d 5f 66 69 6c 65 28 26 61 2c 20 67 2e 61 rom_file(&a, g.a
30a0: 72 67 76 5b 32 5d 29 3b 0a 20 20 62 6c 6f 62 5f rgv[2]);. blob_
30b0: 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 read_from_file(&
30c0: 62 2c 20 67 2e 61 72 67 76 5b 33 5d 29 3b 0a 20 b, g.argv[3]);.
30d0: 20 62 6c 6f 62 5f 7a 65 72 6f 28 26 6f 75 74 29 blob_zero(&out)
30e0: 3b 0a 20 20 74 65 78 74 5f 64 69 66 66 28 26 61 ;. text_diff(&a
30f0: 2c 20 26 62 2c 20 26 6f 75 74 2c 20 33 29 3b 0a , &b, &out, 3);.
3100: 20 20 62 6c 6f 62 5f 77 72 69 74 65 5f 74 6f 5f blob_write_to_
3110: 66 69 6c 65 28 26 6f 75 74 2c 20 22 2d 22 29 3b file(&out, "-");
3120: 0a 7d 0a .}.