0000: 2f 2a 0a 2a 2a 20 43 6f 70 79 72 69 67 68 74 20 /*.** Copyright
0010: 28 63 29 20 32 30 30 37 20 44 2e 20 52 69 63 68 (c) 2007 D. Rich
0020: 61 72 64 20 48 69 70 70 0a 2a 2a 0a 2a 2a 20 54 ard Hipp.**.** T
0030: 68 69 73 20 70 72 6f 67 72 61 6d 20 69 73 20 66 his program is f
0040: 72 65 65 20 73 6f 66 74 77 61 72 65 3b 20 79 6f ree software; yo
0050: 75 20 63 61 6e 20 72 65 64 69 73 74 72 69 62 75 u can redistribu
0060: 74 65 20 69 74 20 61 6e 64 2f 6f 72 0a 2a 2a 20 te it and/or.**
0070: 6d 6f 64 69 66 79 20 69 74 20 75 6e 64 65 72 20 modify it under
0080: 74 68 65 20 74 65 72 6d 73 20 6f 66 20 74 68 65 the terms of the
0090: 20 47 4e 55 20 47 65 6e 65 72 61 6c 20 50 75 62 GNU General Pub
00a0: 6c 69 63 0a 2a 2a 20 4c 69 63 65 6e 73 65 20 76 lic.** License v
00b0: 65 72 73 69 6f 6e 20 32 20 61 73 20 70 75 62 6c ersion 2 as publ
00c0: 69 73 68 65 64 20 62 79 20 74 68 65 20 46 72 65 ished by the Fre
00d0: 65 20 53 6f 66 74 77 61 72 65 20 46 6f 75 6e 64 e Software Found
00e0: 61 74 69 6f 6e 2e 0a 2a 2a 0a 2a 2a 20 54 68 69 ation..**.** Thi
00f0: 73 20 70 72 6f 67 72 61 6d 20 69 73 20 64 69 73 s program is dis
0100: 74 72 69 62 75 74 65 64 20 69 6e 20 74 68 65 20 tributed in the
0110: 68 6f 70 65 20 74 68 61 74 20 69 74 20 77 69 6c hope that it wil
0120: 6c 20 62 65 20 75 73 65 66 75 6c 2c 0a 2a 2a 20 l be useful,.**
0130: 62 75 74 20 57 49 54 48 4f 55 54 20 41 4e 59 20 but WITHOUT ANY
0140: 57 41 52 52 41 4e 54 59 3b 20 77 69 74 68 6f 75 WARRANTY; withou
0150: 74 20 65 76 65 6e 20 74 68 65 20 69 6d 70 6c 69 t even the impli
0160: 65 64 20 77 61 72 72 61 6e 74 79 20 6f 66 0a 2a ed warranty of.*
0170: 2a 20 4d 45 52 43 48 41 4e 54 41 42 49 4c 49 54 * MERCHANTABILIT
0180: 59 20 6f 72 20 46 49 54 4e 45 53 53 20 46 4f 52 Y or FITNESS FOR
0190: 20 41 20 50 41 52 54 49 43 55 4c 41 52 20 50 55 A PARTICULAR PU
01a0: 52 50 4f 53 45 2e 20 20 53 65 65 20 74 68 65 20 RPOSE. See the
01b0: 47 4e 55 0a 2a 2a 20 47 65 6e 65 72 61 6c 20 50 GNU.** General P
01c0: 75 62 6c 69 63 20 4c 69 63 65 6e 73 65 20 66 6f ublic License fo
01d0: 72 20 6d 6f 72 65 20 64 65 74 61 69 6c 73 2e 0a r more details..
01e0: 2a 2a 20 0a 2a 2a 20 59 6f 75 20 73 68 6f 75 6c ** .** You shoul
01f0: 64 20 68 61 76 65 20 72 65 63 65 69 76 65 64 20 d have received
0200: 61 20 63 6f 70 79 20 6f 66 20 74 68 65 20 47 4e a copy of the GN
0210: 55 20 47 65 6e 65 72 61 6c 20 50 75 62 6c 69 63 U General Public
0220: 0a 2a 2a 20 4c 69 63 65 6e 73 65 20 61 6c 6f 6e .** License alon
0230: 67 20 77 69 74 68 20 74 68 69 73 20 6c 69 62 72 g with this libr
0240: 61 72 79 3b 20 69 66 20 6e 6f 74 2c 20 77 72 69 ary; if not, wri
0250: 74 65 20 74 6f 20 74 68 65 0a 2a 2a 20 46 72 65 te to the.** Fre
0260: 65 20 53 6f 66 74 77 61 72 65 20 46 6f 75 6e 64 e Software Found
0270: 61 74 69 6f 6e 2c 20 49 6e 63 2e 2c 20 35 39 20 ation, Inc., 59
0280: 54 65 6d 70 6c 65 20 50 6c 61 63 65 20 2d 20 53 Temple Place - S
0290: 75 69 74 65 20 33 33 30 2c 0a 2a 2a 20 42 6f 73 uite 330,.** Bos
02a0: 74 6f 6e 2c 20 4d 41 20 20 30 32 31 31 31 2d 31 ton, MA 02111-1
02b0: 33 30 37 2c 20 55 53 41 2e 0a 2a 2a 0a 2a 2a 20 307, USA..**.**
02c0: 41 75 74 68 6f 72 20 63 6f 6e 74 61 63 74 20 69 Author contact i
02d0: 6e 66 6f 72 6d 61 74 69 6f 6e 3a 0a 2a 2a 20 20 nformation:.**
02e0: 20 64 72 68 40 68 77 61 63 69 2e 63 6f 6d 0a 2a drh@hwaci.com.*
02f0: 2a 20 20 20 68 74 74 70 3a 2f 2f 77 77 77 2e 68 * http://www.h
0300: 77 61 63 69 2e 63 6f 6d 2f 64 72 68 2f 0a 2a 2a waci.com/drh/.**
0310: 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a .***************
0320: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0330: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0340: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0350: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0360: 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 66 69 6c 65 .**.** This file
0370: 20 63 6f 6e 74 61 69 6e 73 20 63 6f 64 65 20 75 contains code u
0380: 73 65 64 20 74 6f 20 63 6f 6d 70 75 74 65 20 61 sed to compute a
0390: 20 22 64 69 66 66 22 20 62 65 74 77 65 65 6e 20 "diff" between
03a0: 74 77 6f 0a 2a 2a 20 74 65 78 74 20 66 69 6c 65 two.** text file
03b0: 73 2e 0a 2a 2f 0a 23 69 6e 63 6c 75 64 65 20 22 s..*/.#include "
03c0: 63 6f 6e 66 69 67 2e 68 22 0a 23 69 6e 63 6c 75 config.h".#inclu
03d0: 64 65 20 22 64 69 66 66 2e 68 22 0a 23 69 6e 63 de "diff.h".#inc
03e0: 6c 75 64 65 20 3c 61 73 73 65 72 74 2e 68 3e 0a lude <assert.h>.
03f0: 0a 0a 23 69 66 20 30 0a 23 64 65 66 69 6e 65 20 ..#if 0.#define
0400: 44 45 42 55 47 28 58 29 20 58 0a 23 65 6c 73 65 DEBUG(X) X.#else
0410: 0a 23 64 65 66 69 6e 65 20 44 45 42 55 47 28 58 .#define DEBUG(X
0420: 29 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20 ).#endif../*.**
0430: 49 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 62 6f 75 Information abou
0440: 74 20 65 61 63 68 20 6c 69 6e 65 20 6f 66 20 61 t each line of a
0450: 20 66 69 6c 65 20 62 65 69 6e 67 20 64 69 66 66 file being diff
0460: 65 64 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6c 6f ed..**.** The lo
0470: 77 65 72 20 32 30 20 62 69 74 73 20 6f 66 20 74 wer 20 bits of t
0480: 68 65 20 68 61 73 68 20 61 72 65 20 74 68 65 20 he hash are the
0490: 6c 65 6e 67 74 68 20 6f 66 20 74 68 65 0a 2a 2a length of the.**
04a0: 20 6c 69 6e 65 2e 20 20 49 66 20 61 6e 79 20 6c line. If any l
04b0: 69 6e 65 20 69 73 20 6c 6f 6e 67 65 72 20 74 68 ine is longer th
04c0: 61 6e 20 31 30 34 38 35 37 35 20 63 68 61 72 61 an 1048575 chara
04d0: 63 74 65 72 73 2c 0a 2a 2a 20 74 68 65 20 66 69 cters,.** the fi
04e0: 6c 65 20 69 73 20 63 6f 6e 73 69 64 65 72 65 64 le is considered
04f0: 20 62 69 6e 61 72 79 2e 0a 2a 2f 0a 74 79 70 65 binary..*/.type
0500: 64 65 66 20 73 74 72 75 63 74 20 44 4c 69 6e 65 def struct DLine
0510: 20 44 4c 69 6e 65 3b 0a 73 74 72 75 63 74 20 44 DLine;.struct D
0520: 4c 69 6e 65 20 7b 0a 20 20 63 6f 6e 73 74 20 63 Line {. const c
0530: 68 61 72 20 2a 7a 3b 20 20 20 20 2f 2a 20 54 68 har *z; /* Th
0540: 65 20 74 65 78 74 20 6f 66 20 74 68 65 20 6c 69 e text of the li
0550: 6e 65 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64 ne */. unsigned
0560: 20 69 6e 74 20 68 3b 20 20 20 2f 2a 20 48 61 73 int h; /* Has
0570: 68 20 6f 66 20 74 68 65 20 6c 69 6e 65 20 2a 2f h of the line */
0580: 0a 7d 3b 0a 0a 23 64 65 66 69 6e 65 20 4c 45 4e .};..#define LEN
0590: 47 54 48 5f 4d 41 53 4b 20 20 30 78 30 30 30 66 GTH_MASK 0x000f
05a0: 66 66 66 66 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 ffff../*.** Retu
05b0: 72 6e 20 61 6e 20 61 72 72 61 79 20 6f 66 20 44 rn an array of D
05c0: 4c 69 6e 65 20 6f 62 6a 65 63 74 73 20 63 6f 6e Line objects con
05d0: 74 61 69 6e 69 6e 67 20 61 20 70 6f 69 6e 74 65 taining a pointe
05e0: 72 20 74 6f 20 74 68 65 0a 2a 2a 20 73 74 61 72 r to the.** star
05f0: 74 20 6f 66 20 65 61 63 68 20 6c 69 6e 65 20 61 t of each line a
0600: 6e 64 20 61 20 68 61 73 68 20 6f 66 20 74 68 61 nd a hash of tha
0610: 74 20 6c 69 6e 65 2e 20 20 54 68 65 20 6c 6f 77 t line. The low
0620: 65 72 20 0a 2a 2a 20 62 69 74 73 20 6f 66 20 74 er .** bits of t
0630: 68 65 20 68 61 73 68 20 73 74 6f 72 65 20 74 68 he hash store th
0640: 65 20 6c 65 6e 67 74 68 20 6f 66 20 65 61 63 68 e length of each
0650: 20 6c 69 6e 65 2e 0a 2a 2a 0a 2a 2a 20 54 72 61 line..**.** Tra
0660: 69 6c 69 6e 67 20 77 68 69 74 65 73 70 61 63 65 iling whitespace
0670: 20 69 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d is removed from
0680: 20 65 61 63 68 20 6c 69 6e 65 2e 0a 2a 2a 0a 2a each line..**.*
0690: 2a 20 52 65 74 75 72 6e 20 30 20 69 66 20 74 68 * Return 0 if th
06a0: 65 20 66 69 6c 65 20 69 73 20 62 69 6e 61 72 79 e file is binary
06b0: 20 6f 72 20 63 6f 6e 74 61 69 6e 73 20 61 20 6c or contains a l
06c0: 69 6e 65 20 74 68 61 74 20 69 73 0a 2a 2a 20 6c ine that is.** l
06d0: 6f 6e 67 65 72 20 74 68 61 6e 20 31 30 34 38 35 onger than 10485
06e0: 37 35 20 62 79 74 65 73 2e 0a 2a 2f 0a 73 74 61 75 bytes..*/.sta
06f0: 74 69 63 20 44 4c 69 6e 65 20 2a 62 72 65 61 6b tic DLine *break
0700: 5f 69 6e 74 6f 5f 6c 69 6e 65 73 28 63 68 61 72 _into_lines(char
0710: 20 2a 7a 2c 20 69 6e 74 20 2a 70 6e 4c 69 6e 65 *z, int *pnLine
0720: 29 7b 0a 20 20 69 6e 74 20 6e 4c 69 6e 65 2c 20 ){. int nLine,
0730: 69 2c 20 6a 2c 20 6b 2c 20 78 3b 0a 20 20 75 6e i, j, k, x;. un
0740: 73 69 67 6e 65 64 20 69 6e 74 20 68 3b 0a 20 20 signed int h;.
0750: 44 4c 69 6e 65 20 2a 61 3b 0a 0a 20 20 2f 2a 20 DLine *a;.. /*
0760: 43 6f 75 6e 74 20 74 68 65 20 6e 75 6d 62 65 72 Count the number
0770: 20 6f 66 20 6c 69 6e 65 73 2e 20 20 41 6c 6c 6f of lines. Allo
0780: 63 61 74 65 20 73 70 61 63 65 20 74 6f 20 68 6f cate space to ho
0790: 6c 64 0a 20 20 2a 2a 20 74 68 65 20 72 65 74 75 ld. ** the retu
07a0: 72 6e 65 64 20 61 72 72 61 79 2e 0a 20 20 2a 2f rned array.. */
07b0: 0a 20 20 66 6f 72 28 69 3d 6a 3d 30 2c 20 6e 4c . for(i=j=0, nL
07c0: 69 6e 65 3d 31 3b 20 7a 5b 69 5d 3b 20 69 2b 2b ine=1; z[i]; i++
07d0: 2c 20 6a 2b 2b 29 7b 0a 20 20 20 20 69 6e 74 20 , j++){. int
07e0: 63 20 3d 20 7a 5b 69 5d 3b 0a 20 20 20 20 69 66 c = z[i];. if
07f0: 28 20 63 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 ( c==0 ){.
0800: 72 65 74 75 72 6e 20 30 3b 0a 20 20 20 20 7d 0a return 0;. }.
0810: 20 20 20 20 69 66 28 20 63 3d 3d 27 5c 6e 27 20 if( c=='\n'
0820: 26 26 20 7a 5b 69 2b 31 5d 21 3d 30 20 29 7b 0a && z[i+1]!=0 ){.
0830: 20 20 20 20 20 20 6e 4c 69 6e 65 2b 2b 3b 0a 20 nLine++;.
0840: 20 20 20 20 20 69 66 28 20 6a 3e 31 30 34 38 35 if( j>10485
0850: 37 35 20 29 7b 0a 20 20 20 20 20 20 20 20 72 65 75 ){. re
0860: 74 75 72 6e 20 30 3b 0a 20 20 20 20 20 20 7d 0a turn 0;. }.
0870: 20 20 20 20 20 20 6a 20 3d 20 30 3b 0a 20 20 20 j = 0;.
0880: 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20 6a 3e 31 }. }. if( j>1
0890: 30 34 38 35 37 35 20 29 7b 0a 20 20 20 20 72 65 048575 ){. re
08a0: 74 75 72 6e 20 30 3b 0a 20 20 7d 0a 20 20 61 20 turn 0;. }. a
08b0: 3d 20 6d 61 6c 6c 6f 63 28 20 6e 4c 69 6e 65 2a = malloc( nLine*
08c0: 73 69 7a 65 6f 66 28 61 5b 30 5d 29 20 29 3b 0a sizeof(a[0]) );.
08d0: 20 20 69 66 28 20 61 3d 3d 30 20 29 20 66 6f 73 if( a==0 ) fos
08e0: 73 69 6c 5f 70 61 6e 69 63 28 22 6f 75 74 20 6f sil_panic("out o
08f0: 66 20 6d 65 6d 6f 72 79 22 29 3b 0a 0a 20 20 2f f memory");.. /
0900: 2a 20 46 69 6c 6c 20 69 6e 20 74 68 65 20 61 72 * Fill in the ar
0910: 72 61 79 20 2a 2f 0a 20 20 66 6f 72 28 69 3d 30 ray */. for(i=0
0920: 3b 20 69 3c 6e 4c 69 6e 65 3b 20 69 2b 2b 29 7b ; i<nLine; i++){
0930: 0a 20 20 20 20 61 5b 69 5d 2e 7a 20 3d 20 7a 3b . a[i].z = z;
0940: 0a 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 7a 5b . for(j=0; z[
0950: 6a 5d 20 26 26 20 7a 5b 6a 5d 21 3d 27 5c 6e 27 j] && z[j]!='\n'
0960: 3b 20 6a 2b 2b 29 7b 7d 0a 20 20 20 20 66 6f 72 ; j++){}. for
0970: 28 6b 3d 6a 3b 20 6b 3e 30 20 26 26 20 69 73 73 (k=j; k>0 && iss
0980: 70 61 63 65 28 7a 5b 6b 2d 31 5d 29 3b 20 6b 2d pace(z[k-1]); k-
0990: 2d 29 7b 7d 0a 20 20 20 20 66 6f 72 28 68 3d 30 -){}. for(h=0
09a0: 2c 20 78 3d 30 3b 20 78 3c 6b 3b 20 78 2b 2b 29 , x=0; x<k; x++)
09b0: 7b 0a 20 20 20 20 20 20 68 20 3d 20 68 20 5e 20 {. h = h ^
09c0: 28 68 3c 3c 32 29 20 5e 20 7a 5b 78 5d 3b 0a 20 (h<<2) ^ z[x];.
09d0: 20 20 20 7d 0a 20 20 20 20 61 5b 69 5d 2e 68 20 }. a[i].h
09e0: 3d 20 28 68 3c 3c 32 30 29 20 7c 20 6b 3b 3b 0a = (h<<20) | k;;.
09f0: 20 20 20 20 7a 20 2b 3d 20 6a 2b 31 3b 0a 20 20 z += j+1;.
0a00: 7d 0a 0a 20 20 2f 2a 20 52 65 74 75 72 6e 20 72 }.. /* Return r
0a10: 65 73 75 6c 74 73 20 2a 2f 0a 20 20 2a 70 6e 4c esults */. *pnL
0a20: 69 6e 65 20 3d 20 6e 4c 69 6e 65 3b 0a 20 20 72 ine = nLine;. r
0a30: 65 74 75 72 6e 20 61 3b 0a 7d 0a 0a 2f 2a 0a 2a eturn a;.}../*.*
0a40: 2a 20 52 65 74 75 72 6e 20 74 72 75 65 20 69 66 * Return true if
0a50: 20 74 77 6f 20 44 4c 69 6e 65 20 65 6c 65 6d 65 two DLine eleme
0a60: 6e 74 73 20 61 72 65 20 69 64 65 6e 74 69 63 61 nts are identica
0a70: 6c 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 l..*/.static int
0a80: 20 73 61 6d 65 5f 64 6c 69 6e 65 28 44 4c 69 6e same_dline(DLin
0a90: 65 20 2a 70 41 2c 20 44 4c 69 6e 65 20 2a 70 42 e *pA, DLine *pB
0aa0: 29 7b 0a 20 20 72 65 74 75 72 6e 20 70 41 2d 3e ){. return pA->
0ab0: 68 3d 3d 70 42 2d 3e 68 20 26 26 20 6d 65 6d 63 h==pB->h && memc
0ac0: 6d 70 28 70 41 2d 3e 7a 2c 70 42 2d 3e 7a 2c 70 mp(pA->z,pB->z,p
0ad0: 41 2d 3e 68 20 26 20 4c 45 4e 47 54 48 5f 4d 41 A->h & LENGTH_MA
0ae0: 53 4b 29 3d 3d 30 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a SK)==0;.}../*.**
0af0: 20 41 70 70 65 6e 64 20 61 20 73 69 6e 67 6c 65 Append a single
0b00: 20 6c 69 6e 65 20 6f 66 20 22 64 69 66 66 22 20 line of "diff"
0b10: 6f 75 74 70 75 74 20 74 6f 20 70 4f 75 74 2e 0a output to pOut..
0b20: 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 61 */.static void a
0b30: 70 70 65 6e 64 44 69 66 66 4c 69 6e 65 28 42 6c ppendDiffLine(Bl
0b40: 6f 62 20 2a 70 4f 75 74 2c 20 63 68 61 72 20 2a ob *pOut, char *
0b50: 7a 50 72 65 66 69 78 2c 20 44 4c 69 6e 65 20 2a zPrefix, DLine *
0b60: 70 4c 69 6e 65 29 7b 0a 20 20 62 6c 6f 62 5f 61 pLine){. blob_a
0b70: 70 70 65 6e 64 28 70 4f 75 74 2c 20 7a 50 72 65 ppend(pOut, zPre
0b80: 66 69 78 2c 20 31 29 3b 0a 20 20 62 6c 6f 62 5f fix, 1);. blob_
0b90: 61 70 70 65 6e 64 28 70 4f 75 74 2c 20 70 4c 69 append(pOut, pLi
0ba0: 6e 65 2d 3e 7a 2c 20 70 4c 69 6e 65 2d 3e 68 20 ne->z, pLine->h
0bb0: 26 20 4c 45 4e 47 54 48 5f 4d 41 53 4b 29 3b 0a & LENGTH_MASK);.
0bc0: 20 20 62 6c 6f 62 5f 61 70 70 65 6e 64 28 70 4f blob_append(pO
0bd0: 75 74 2c 20 22 5c 6e 22 2c 20 31 29 3b 0a 7d 0a ut, "\n", 1);.}.
0be0: 0a 0a 2f 2a 0a 2a 2a 20 47 65 6e 65 72 61 74 65 ../*.** Generate
0bf0: 20 61 20 72 65 70 6f 72 74 20 6f 66 20 74 68 65 a report of the
0c00: 20 64 69 66 66 65 72 65 6e 63 65 73 20 62 65 74 differences bet
0c10: 77 65 65 6e 20 66 69 6c 65 73 20 70 41 20 61 6e ween files pA an
0c20: 64 20 70 42 2e 0a 2a 2a 20 49 66 20 70 4f 75 74 d pB..** If pOut
0c30: 20 69 73 20 6e 6f 74 20 4e 55 4c 4c 20 74 68 65 is not NULL the
0c40: 6e 20 61 20 75 6e 69 66 69 65 64 20 64 69 66 66 n a unified diff
0c50: 20 69 73 20 61 70 70 65 6e 64 65 64 20 74 68 65 is appended the
0c60: 72 65 2e 20 20 49 74 0a 2a 2a 20 69 73 20 61 73 re. It.** is as
0c70: 73 75 6d 65 64 20 74 68 61 74 20 70 4f 75 74 20 sumed that pOut
0c80: 68 61 73 20 61 6c 72 65 61 64 79 20 62 65 65 6e has already been
0c90: 20 69 6e 69 74 69 61 6c 69 7a 65 64 2e 20 20 49 initialized. I
0ca0: 66 20 70 4f 75 74 20 69 73 0a 2a 2a 20 4e 55 4c f pOut is.** NUL
0cb0: 4c 2c 20 74 68 65 6e 20 61 20 70 6f 69 6e 74 65 L, then a pointe
0cc0: 72 20 74 6f 20 61 6e 20 61 72 72 61 79 20 6f 66 r to an array of
0cd0: 20 69 6e 74 65 67 65 72 73 20 69 73 20 72 65 74 integers is ret
0ce0: 75 72 6e 65 64 2e 20 20 0a 2a 2a 20 54 68 65 20 urned. .** The
0cf0: 69 6e 74 65 67 65 72 73 20 63 6f 6d 65 20 69 6e integers come in
0d00: 20 74 72 69 70 6c 65 73 2e 20 20 46 6f 72 20 65 triples. For e
0d10: 61 63 68 20 74 72 69 70 6c 65 2c 0a 2a 2a 20 74 ach triple,.** t
0d20: 68 65 20 65 6c 65 6d 65 6e 74 73 20 61 72 65 20 he elements are
0d30: 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 6c 69 the number of li
0d40: 6e 65 73 20 63 6f 70 69 65 64 2c 20 74 68 65 20 nes copied, the
0d50: 6e 75 6d 62 65 72 20 6f 66 0a 2a 2a 20 6c 69 6e number of.** lin
0d60: 65 73 20 64 65 6c 65 74 65 64 2c 20 61 6e 64 20 es deleted, and
0d70: 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 6c 69 the number of li
0d80: 6e 65 73 20 69 6e 73 65 72 74 65 64 2e 20 20 54 nes inserted. T
0d90: 68 65 20 76 65 63 74 6f 72 0a 2a 2a 20 69 73 20 he vector.** is
0da0: 74 65 72 6d 69 6e 61 74 65 64 20 62 79 20 61 20 terminated by a
0db0: 74 72 69 70 6c 65 20 6f 66 20 61 6c 6c 20 7a 65 triple of all ze
0dc0: 72 6f 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 ros..**.** This
0dd0: 64 69 66 66 20 75 74 69 6c 69 74 79 20 64 6f 65 diff utility doe
0de0: 73 20 6e 6f 74 20 77 6f 72 6b 20 6f 6e 20 62 69 s not work on bi
0df0: 6e 61 72 79 20 66 69 6c 65 73 2e 20 20 49 66 20 nary files. If
0e00: 61 20 62 69 6e 61 72 79 0a 2a 2a 20 66 69 6c 65 a binary.** file
0e10: 20 69 73 20 65 6e 63 6f 75 6e 74 65 72 65 64 2c is encountered,
0e20: 20 30 20 69 73 20 72 65 74 75 72 6e 65 64 20 61 0 is returned a
0e30: 6e 64 20 70 4f 75 74 20 69 73 20 77 72 69 74 74 nd pOut is writt
0e40: 65 6e 20 77 69 74 68 0a 2a 2a 20 74 65 78 74 20 en with.** text
0e50: 22 63 61 6e 6e 6f 74 20 63 6f 6d 70 75 74 65 20 "cannot compute
0e60: 64 69 66 66 65 72 65 6e 63 65 20 62 65 74 77 65 difference betwe
0e70: 65 6e 20 62 69 6e 61 72 79 20 66 69 6c 65 73 22 en binary files"
0e80: 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ..**.***********
0e90: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0ea0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0eb0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0ec0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0ed0: 2a 0a 2a 2a 0a 2a 2a 20 54 68 65 20 63 6f 72 65 *.**.** The core
0ee0: 20 61 6c 67 6f 72 69 74 68 6d 20 69 73 20 61 20 algorithm is a
0ef0: 76 61 72 69 61 74 69 6f 6e 20 6f 6e 20 74 68 65 variation on the
0f00: 20 63 6c 61 73 73 69 63 20 57 61 67 6e 65 72 0a classic Wagner.
0f10: 2a 2a 20 6d 69 6e 69 6d 75 6d 20 65 64 69 74 20 ** minimum edit
0f20: 64 69 73 74 61 6e 63 65 20 77 69 74 68 20 65 6e distance with en
0f30: 68 61 6e 63 65 6d 65 6e 74 73 20 74 6f 20 72 65 hancements to re
0f40: 64 75 63 65 20 74 68 65 20 72 75 6e 74 69 6d 65 duce the runtime
0f50: 0a 2a 2a 20 74 6f 20 62 65 20 61 6c 6d 6f 73 74 .** to be almost
0f60: 20 6c 69 6e 65 61 72 20 69 6e 20 74 68 65 20 63 linear in the c
0f70: 6f 6d 6d 6f 6e 20 63 61 73 65 20 77 68 65 72 65 ommon case where
0f80: 20 74 68 65 20 74 77 6f 20 66 69 6c 65 73 0a 2a the two files.*
0f90: 2a 20 68 61 76 65 20 61 20 6c 6f 74 20 69 6e 20 * have a lot in
0fa0: 63 6f 6d 6d 6f 6e 2e 20 20 46 6f 72 20 61 64 64 common. For add
0fb0: 69 74 69 6f 6e 61 6c 20 69 6e 66 6f 72 6d 61 74 itional informat
0fc0: 69 6f 6e 20 73 65 65 0a 2a 2a 20 45 75 67 65 6e ion see.** Eugen
0fd0: 65 20 57 2e 20 4d 79 65 72 73 2c 20 22 41 6e 20 e W. Myers, "An
0fe0: 4f 28 4e 44 29 20 44 69 66 66 65 72 65 6e 63 65 O(ND) Difference
0ff0: 20 41 6c 67 6f 72 69 74 68 6d 20 41 6e 64 20 49 Algorithm And I
1000: 74 73 0a 2a 2a 20 56 61 72 69 61 74 69 6f 6e 73 ts.** Variations
1010: 22 0a 2a 2a 0a 2a 2a 20 43 6f 6e 73 69 64 65 72 ".**.** Consider
1020: 20 63 6f 6d 70 61 72 69 6e 67 20 73 74 72 69 6e comparing strin
1030: 67 73 20 41 20 61 6e 64 20 42 2e 20 20 41 3d 61 gs A and B. A=a
1040: 62 63 61 62 62 61 20 61 6e 64 20 42 3d 63 62 61 bcabba and B=cba
1050: 62 61 63 0a 2a 2a 20 57 65 20 63 6f 6e 73 74 72 bac.** We constr
1060: 75 63 74 20 61 20 22 57 61 67 6e 65 72 22 20 6d uct a "Wagner" m
1070: 61 74 72 69 78 20 57 20 77 69 74 68 20 41 20 61 atrix W with A a
1080: 6c 6f 6e 67 20 74 68 65 20 58 20 61 78 69 73 20 long the X axis
1090: 61 6e 64 20 0a 2a 2a 20 42 20 61 6c 6f 6e 67 20 and .** B along
10a0: 74 68 65 20 59 20 61 78 69 73 3a 0a 2a 2a 0a 2a the Y axis:.**.*
10b0: 2a 20 20 20 20 20 63 20 36 20 20 20 20 20 20 20 * c 6
10c0: 20 20 20 20 20 20 20 20 2a 0a 2a 2a 20 20 20 20 *.**
10d0: 20 61 20 35 20 20 20 20 20 20 20 20 20 20 20 20 a 5
10e0: 20 20 20 2a 0a 2a 2a 20 20 20 20 20 62 20 34 20 *.** b 4
10f0: 20 20 20 20 20 20 20 20 20 20 2a 20 2a 0a 2a 2a * *.**
1100: 20 20 20 20 20 61 20 33 20 20 20 20 20 20 20 20 a 3
1110: 20 2a 0a 2a 2a 20 20 20 20 20 62 20 32 20 20 20 *.** b 2
1120: 20 20 20 20 2a 0a 2a 2a 20 20 20 42 20 63 20 31 *.** B c 1
1130: 20 20 20 20 20 20 20 2a 0a 2a 2a 20 20 20 20 20 *.**
1140: 20 20 30 20 2a 20 2a 20 2a 20 0a 2a 2a 20 20 20 0 * * * .**
1150: 20 20 20 20 20 20 30 20 31 20 32 20 33 20 34 20 0 1 2 3 4
1160: 35 20 36 20 37 0a 2a 2a 20 20 20 20 20 20 20 20 5 6 7.**
1170: 20 20 20 61 20 62 20 63 20 61 20 62 20 62 20 61 a b c a b b a
1180: 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 41 0a .** A.
1190: 2a 2a 0a 2a 2a 20 28 4e 6f 74 65 3a 20 77 65 20 **.** (Note: we
11a0: 64 72 61 77 20 74 68 69 73 20 57 61 67 6e 65 72 draw this Wagner
11b0: 20 6d 61 74 72 69 78 20 77 69 74 68 20 74 68 65 matrix with the
11c0: 20 6f 72 69 67 69 6e 20 61 74 20 74 68 65 20 6c origin at the l
11d0: 6f 77 65 72 20 0a 2a 2a 20 6c 65 66 74 20 77 68 ower .** left wh
11e0: 65 72 65 61 73 20 4d 79 65 72 73 20 75 73 65 73 ereas Myers uses
11f0: 20 74 68 65 20 6f 72 69 67 69 6e 20 61 74 20 74 the origin at t
1200: 68 65 20 75 70 70 65 72 20 6c 65 66 74 2e 20 20 he upper left.
1210: 4f 74 68 65 72 77 69 73 65 2c 0a 2a 2a 20 74 68 Otherwise,.** th
1220: 65 79 20 61 72 65 20 74 68 65 20 73 61 6d 65 2e ey are the same.
1230: 29 0a 2a 2a 0a 2a 2a 20 4c 65 74 20 59 20 62 65 ).**.** Let Y be
1240: 20 74 68 65 20 6d 61 78 69 6d 75 6d 20 79 20 76 the maximum y v
1250: 61 6c 75 65 20 6f 72 20 74 68 65 20 6e 75 6d 62 alue or the numb
1260: 65 72 20 6f 66 20 63 68 61 72 61 63 74 65 72 73 er of characters
1270: 20 69 6e 20 42 2e 0a 2a 2a 20 36 20 69 6e 20 74 in B..** 6 in t
1280: 68 69 73 20 65 78 61 6d 70 6c 65 2e 20 20 58 20 his example. X
1290: 69 73 20 74 68 65 20 6d 61 78 69 6d 75 6d 20 78 is the maximum x
12a0: 20 76 61 6c 75 65 20 6f 72 20 74 68 65 20 6e 75 value or the nu
12b0: 6d 62 65 72 20 6f 66 0a 2a 2a 20 65 6c 65 6d 65 mber of.** eleme
12c0: 6e 74 73 20 69 6e 20 41 2e 20 20 48 65 72 65 20 nts in A. Here
12d0: 37 2e 0a 2a 2a 0a 2a 2a 20 4f 75 72 20 67 6f 61 7..**.** Our goa
12e0: 6c 20 69 73 20 74 6f 20 66 69 6e 64 20 61 20 70 l is to find a p
12f0: 61 74 68 20 66 72 6f 6d 20 28 30 2c 30 29 20 74 ath from (0,0) t
1300: 6f 20 28 58 2c 59 29 2e 20 20 54 68 65 20 70 61 o (X,Y). The pa
1310: 74 68 20 63 61 6e 0a 2a 2a 20 75 73 65 20 68 6f th can.** use ho
1320: 72 69 7a 6f 6e 74 61 6c 2c 20 76 65 72 74 69 63 rizontal, vertic
1330: 61 6c 2c 20 6f 72 20 64 69 61 67 6f 6e 61 6c 20 al, or diagonal
1340: 73 74 65 70 73 2e 20 20 41 20 64 69 61 67 6f 6e steps. A diagon
1350: 61 6c 20 66 72 6f 6d 0a 2a 2a 20 28 78 2d 31 2c al from.** (x-1,
1360: 79 2d 31 29 20 74 6f 20 28 78 2c 79 29 20 69 73 y-1) to (x,y) is
1370: 20 6f 6e 6c 79 20 61 6c 6c 6f 77 65 64 20 69 66 only allowed if
1380: 20 41 5b 78 5d 3d 3d 42 5b 79 5d 2e 20 20 41 20 A[x]==B[y]. A
1390: 76 65 72 74 69 63 61 6c 0a 2a 2a 20 73 74 65 70 vertical.** step
13a0: 73 20 63 6f 72 72 65 73 70 6f 6e 64 73 20 74 6f s corresponds to
13b0: 20 61 6e 20 69 6e 73 65 72 74 69 6f 6e 2e 20 20 an insertion.
13c0: 41 20 68 6f 72 69 7a 6f 6e 74 61 6c 20 73 74 65 A horizontal ste
13d0: 70 20 63 6f 72 72 65 73 70 6f 6e 64 73 0a 2a 2a p corresponds.**
13e0: 20 74 6f 20 61 20 64 65 6c 65 74 69 6f 6e 2e 20 to a deletion.
13f0: 20 57 65 20 77 61 6e 74 20 74 6f 20 66 69 6e 64 We want to find
1400: 20 74 68 65 20 70 61 74 68 20 77 69 74 68 20 74 the path with t
1410: 68 65 20 66 65 77 65 73 74 0a 2a 2a 20 68 6f 72 he fewest.** hor
1420: 69 7a 6f 6e 74 61 6c 20 61 6e 64 20 76 65 72 74 izontal and vert
1430: 69 63 61 6c 20 73 74 65 70 73 2e 0a 2a 2a 0a 2a ical steps..**.*
1440: 2a 20 44 69 61 67 6f 6e 61 6c 20 6b 20 63 6f 6e * Diagonal k con
1450: 73 69 73 74 73 20 6f 66 20 61 6c 6c 20 70 6f 69 sists of all poi
1460: 6e 74 73 20 73 75 63 68 20 74 68 61 74 20 78 2d nts such that x-
1470: 79 3d 3d 6b 2e 20 20 44 69 61 67 6f 6e 61 6c 0a y==k. Diagonal.
1480: 2a 2a 20 7a 65 72 6f 20 62 65 67 69 6e 73 20 61 ** zero begins a
1490: 74 20 74 68 65 20 6f 72 69 67 69 6e 2e 20 20 44 t the origin. D
14a0: 69 61 67 6f 6e 61 6c 20 31 20 62 65 67 69 6e 73 iagonal 1 begins
14b0: 20 61 74 20 28 31 2c 30 29 2e 20 20 0a 2a 2a 20 at (1,0). .**
14c0: 44 69 61 67 6f 6e 61 6c 20 2d 31 20 62 65 67 69 Diagonal -1 begi
14d0: 6e 73 20 61 74 20 28 30 2c 31 29 2e 20 20 41 6c ns at (0,1). Al
14e0: 6c 20 64 69 61 67 6f 6e 61 6c 73 20 6d 6f 76 65 l diagonals move
14f0: 20 75 70 20 61 6e 64 20 74 6f 20 74 68 65 0a 2a up and to the.*
1500: 2a 20 72 69 67 68 74 20 61 74 20 34 35 20 64 65 * right at 45 de
1510: 67 72 65 65 73 2e 20 20 44 69 61 67 6f 6e 61 6c grees. Diagonal
1520: 20 6e 75 6d 62 65 72 20 69 6e 63 72 65 61 73 65 number increase
1530: 20 66 72 6f 6d 20 75 70 70 65 72 20 6c 65 66 74 from upper left
1540: 0a 2a 2a 20 74 6f 20 6c 6f 77 65 72 20 72 69 67 .** to lower rig
1550: 68 74 2e 0a 2a 2a 20 0a 2a 2a 20 4d 79 65 72 73 ht..** .** Myers
1560: 20 6d 61 74 72 69 78 20 4d 20 69 73 20 61 20 6c matrix M is a l
1570: 6f 77 65 72 20 72 69 67 68 74 20 74 72 69 61 6e ower right trian
1580: 67 75 6c 61 72 20 6d 61 74 72 69 78 20 77 69 74 gular matrix wit
1590: 68 20 69 6e 64 69 63 65 73 20 64 0a 2a 2a 20 61 h indices d.** a
15a0: 6c 6f 6e 67 20 74 68 65 20 62 6f 74 74 6f 6d 20 long the bottom
15b0: 61 6e 64 20 69 20 76 65 72 74 69 63 61 6c 6c 79 and i vertically
15c0: 3a 0a 2a 2a 0a 2a 2a 20 0a 2a 2a 20 20 20 69 3d :.**.** .** i=
15d0: 34 20 7c 20 20 20 20 20 20 20 20 20 20 20 20 2b 4 | +
15e0: 34 20 20 5c 0a 2a 2a 20 20 20 20 20 33 20 7c 20 4 \.** 3 |
15f0: 20 20 20 20 20 20 20 20 2b 33 20 2b 32 20 20 20 +3 +2
1600: 7c 0a 2a 2a 20 20 20 20 20 32 20 7c 20 20 20 20 |.** 2 |
1610: 20 20 2b 32 20 2b 31 20 20 30 20 20 20 7c 2d 20 +2 +1 0 |-
1620: 6b 20 76 61 6c 75 65 73 2e 20 20 20 6b 20 3d 20 k values. k =
1630: 32 2a 69 2d 64 0a 2a 2a 20 20 20 20 20 31 20 7c 2*i-d.** 1 |
1640: 20 20 20 2b 31 20 20 30 20 2d 31 20 2d 32 20 20 +1 0 -1 -2
1650: 20 7c 0a 2a 2a 20 20 20 20 20 30 20 7c 20 30 20 |.** 0 | 0
1660: 2d 31 20 2d 32 20 2d 33 20 2d 34 20 20 2f 0a 2a -1 -2 -3 -4 /.*
1670: 2a 20 20 20 20 20 20 20 2d 2d 2d 2d 2d 2d 2d 2d * --------
1680: 2d 2d 2d 2d 2d 2d 2d 0a 2a 2a 20 20 20 20 20 20 -------.**
1690: 20 20 20 30 20 20 31 20 20 32 20 20 33 20 20 34 0 1 2 3 4
16a0: 20 3d 20 64 0a 2a 2a 0a 2a 2a 20 45 61 63 68 20 = d.**.** Each
16b0: 65 6c 65 6d 65 6e 74 20 6f 66 20 74 68 65 20 4d element of the M
16c0: 79 65 72 73 20 6d 61 74 72 69 78 20 63 6f 72 72 yers matrix corr
16d0: 65 73 70 6f 6e 64 73 20 74 6f 20 61 20 64 69 61 esponds to a dia
16e0: 67 6f 6e 61 6c 2e 0a 2a 2a 20 54 68 65 20 64 69 gonal..** The di
16f0: 61 67 6f 6e 61 6c 20 69 73 20 6b 3d 32 2a 69 2d agonal is k=2*i-
1700: 64 2e 20 20 54 68 65 20 64 69 61 67 6f 6e 61 6c d. The diagonal
1710: 20 76 61 6c 75 65 73 20 61 72 65 20 73 68 6f 77 values are show
1720: 6e 0a 2a 2a 20 69 6e 20 74 68 65 20 74 65 6d 70 n.** in the temp
1730: 6c 61 74 65 20 61 62 6f 76 65 2e 0a 2a 2a 0a 2a late above..**.*
1740: 2a 20 45 61 63 68 20 65 6e 74 72 79 20 69 6e 20 * Each entry in
1750: 4d 20 72 65 70 72 65 73 65 6e 74 73 20 74 68 65 M represents the
1760: 20 65 6e 64 2d 70 6f 69 6e 74 20 6f 6e 20 61 20 end-point on a
1770: 70 61 74 68 20 66 72 6f 6d 20 28 30 2c 30 29 2e path from (0,0).
1780: 0a 2a 2a 20 54 68 65 20 65 6e 64 2d 70 6f 69 6e .** The end-poin
1790: 74 20 69 73 20 6f 6e 20 64 69 61 67 6f 6e 61 6c t is on diagonal
17a0: 20 6b 2e 20 20 54 68 65 20 76 61 6c 75 65 20 73 k. The value s
17b0: 74 6f 72 65 64 20 69 6e 20 4d 20 69 73 0a 2a 2a tored in M is.**
17c0: 20 71 3d 78 2b 79 20 77 68 65 72 65 20 28 78 2c q=x+y where (x,
17d0: 79 29 20 69 73 20 74 68 65 20 74 65 72 6d 69 6e y) is the termin
17e0: 75 73 20 6f 66 20 74 68 65 20 70 61 74 68 2e 20 us of the path.
17f0: 20 41 20 70 61 74 68 0a 2a 2a 20 74 6f 20 4d 5b A path.** to M[
1800: 64 5d 5b 69 5d 20 77 69 6c 6c 20 63 6f 6d 65 20 d][i] will come
1810: 74 68 72 6f 75 67 68 20 65 69 74 68 65 72 20 4d through either M
1820: 5b 64 2d 31 5d 5b 69 2d 31 5d 20 6f 72 0a 2a 2a [d-1][i-1] or.**
1830: 20 74 68 6f 75 67 68 20 4d 5b 64 2d 31 5d 5b 69 though M[d-1][i
1840: 5d 2c 20 77 68 69 63 68 65 76 65 72 20 68 6f 6c ], whichever hol
1850: 64 73 20 74 68 65 20 6c 61 72 67 65 73 74 20 76 ds the largest v
1860: 61 6c 75 65 20 6f 66 20 71 2e 0a 2a 2a 20 49 66 alue of q..** If
1870: 20 62 6f 74 68 20 65 6c 65 6d 65 6e 74 73 20 68 both elements h
1880: 6f 6c 64 20 74 68 65 20 73 61 6d 65 20 76 61 6c old the same val
1890: 75 65 2c 20 74 68 65 20 70 61 74 68 20 63 6f 6d ue, the path com
18a0: 65 73 0a 2a 2a 20 74 68 72 6f 75 67 68 20 4d 5b es.** through M[
18b0: 64 2d 31 5d 5b 69 2d 31 5d 2e 0a 2a 2a 0a 2a 2a d-1][i-1]..**.**
18c0: 20 54 68 65 20 76 61 6c 75 65 20 6f 66 20 64 20 The value of d
18d0: 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 is the number of
18e0: 20 69 6e 73 65 72 74 69 6f 6e 73 20 61 6e 64 20 insertions and
18f0: 64 65 6c 65 74 69 6f 6e 73 0a 2a 2a 20 6d 61 64 deletions.** mad
1900: 65 20 73 6f 20 66 61 72 20 6f 6e 20 74 68 65 20 e so far on the
1910: 70 61 74 68 2e 20 20 4d 20 67 72 6f 77 73 20 70 path. M grows p
1920: 72 6f 67 72 65 73 73 69 76 65 6c 79 2e 20 20 53 rogressively. S
1930: 6f 20 74 68 65 0a 2a 2a 20 73 69 7a 65 20 6f 66 o the.** size of
1940: 20 74 68 65 20 4d 20 6d 61 74 72 69 78 20 69 73 the M matrix is
1950: 20 70 72 6f 70 6f 72 74 69 6f 6e 61 6c 20 74 6f proportional to
1960: 20 64 2a 64 2e 20 20 46 6f 72 20 74 68 65 0a 2a d*d. For the.*
1970: 2a 20 63 6f 6d 6d 6f 6e 20 63 61 73 65 20 77 68 * common case wh
1980: 65 72 65 20 41 20 61 6e 64 20 42 20 61 72 65 20 ere A and B are
1990: 73 69 6d 69 6c 61 72 2c 20 64 20 77 69 6c 6c 20 similar, d will
19a0: 62 65 20 73 6d 61 6c 6c 0a 2a 2a 20 63 6f 6d 70 be small.** comp
19b0: 61 72 65 64 20 74 6f 20 58 20 61 6e 64 20 59 20 ared to X and Y
19c0: 73 6f 20 6c 69 74 74 6c 65 20 6d 65 6d 6f 72 79 so little memory
19d0: 20 69 73 20 72 65 71 75 69 72 65 64 2e 20 20 54 is required. T
19e0: 68 65 0a 2a 2a 20 6f 72 69 67 69 6e 61 6c 20 57 he.** original W
19f0: 61 67 6e 65 72 20 61 6c 67 6f 72 69 74 68 6d 20 agner algorithm
1a00: 72 65 71 75 69 72 65 73 20 58 2a 59 20 6d 65 6d requires X*Y mem
1a10: 6f 72 79 2c 20 77 68 69 63 68 20 66 6f 72 0a 2a ory, which for.*
1a20: 2a 20 6c 61 72 67 65 72 20 66 69 6c 65 73 20 28 * larger files (
1a30: 31 30 30 4b 20 6c 69 6e 65 73 29 20 69 73 20 6d 100K lines) is m
1a40: 6f 72 65 20 6d 65 6d 6f 72 79 20 74 68 61 6e 20 ore memory than
1a50: 77 65 20 68 61 76 65 20 61 74 0a 2a 2a 20 68 61 we have at.** ha
1a60: 6e 64 2e 0a 2a 2f 0a 69 6e 74 20 2a 74 65 78 74 nd..*/.int *text
1a70: 5f 64 69 66 66 28 0a 20 20 42 6c 6f 62 20 2a 70 _diff(. Blob *p
1a80: 41 5f 42 6c 6f 62 2c 20 20 20 2f 2a 20 46 52 4f A_Blob, /* FRO
1a90: 4d 20 66 69 6c 65 20 2a 2f 0a 20 20 42 6c 6f 62 M file */. Blob
1aa0: 20 2a 70 42 5f 42 6c 6f 62 2c 20 20 20 2f 2a 20 *pB_Blob, /*
1ab0: 54 4f 20 66 69 6c 65 20 2a 2f 0a 20 20 42 6c 6f TO file */. Blo
1ac0: 62 20 2a 70 4f 75 74 2c 20 20 20 20 20 20 2f 2a b *pOut, /*
1ad0: 20 57 72 69 74 65 20 75 6e 69 66 69 65 64 20 64 Write unified d
1ae0: 69 66 66 20 68 65 72 65 20 69 66 20 6e 6f 74 20 iff here if not
1af0: 4e 55 4c 4c 20 2a 2f 0a 20 20 69 6e 74 20 6e 43 NULL */. int nC
1b00: 6f 6e 74 65 78 74 20 20 20 20 20 2f 2a 20 41 6d ontext /* Am
1b10: 6f 75 6e 74 20 6f 66 20 63 6f 6e 74 65 78 74 20 ount of context
1b20: 74 6f 20 75 6e 69 66 69 65 64 20 64 69 66 66 20 to unified diff
1b30: 2a 2f 0a 29 7b 0a 20 20 44 4c 69 6e 65 20 2a 41 */.){. DLine *A
1b40: 2c 20 2a 42 3b 20 20 20 20 2f 2a 20 46 69 6c 65 , *B; /* File
1b50: 73 20 62 65 69 6e 67 20 63 6f 6d 70 61 72 65 64 s being compared
1b60: 20 2a 2f 0a 20 20 69 6e 74 20 58 2c 20 59 3b 20 */. int X, Y;
1b70: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 /* Number
1b80: 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20 of elements in
1b90: 41 20 61 6e 64 20 42 20 2a 2f 0a 20 20 69 6e 74 A and B */. int
1ba0: 20 78 2c 20 79 3b 20 20 20 20 20 20 20 20 2f 2a x, y; /*
1bb0: 20 49 6e 64 69 63 65 73 3a 20 20 41 5b 78 5d 20 Indices: A[x]
1bc0: 61 6e 64 20 42 5b 79 5d 20 2a 2f 0a 20 20 69 6e and B[y] */. in
1bd0: 74 20 73 7a 4d 20 3d 20 30 3b 20 20 20 20 20 2f t szM = 0; /
1be0: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 72 6f 77 73 * Number of rows
1bf0: 20 61 6e 64 20 63 6f 6c 75 6d 6e 73 20 69 6e 20 and columns in
1c00: 4d 20 2a 2f 0a 20 20 69 6e 74 20 2a 2a 4d 20 3d M */. int **M =
1c10: 20 30 3b 20 20 20 20 20 2f 2a 20 4d 79 65 72 73 0; /* Myers
1c20: 20 6d 61 74 72 69 78 20 2a 2f 0a 20 20 69 6e 74 matrix */. int
1c30: 20 69 2c 20 64 3b 20 20 20 20 20 20 20 20 2f 2a i, d; /*
1c40: 20 49 6e 64 69 63 65 73 20 6f 6e 20 4d 2e 20 20 Indices on M.
1c50: 4d 5b 64 5d 5b 69 5d 20 2a 2f 0a 20 20 69 6e 74 M[d][i] */. int
1c60: 20 6b 2c 20 71 3b 20 20 20 20 20 20 20 20 2f 2a k, q; /*
1c70: 20 44 69 61 67 6f 6e 61 6c 20 6e 75 6d 62 65 72 Diagonal number
1c80: 20 61 6e 64 20 64 69 73 74 69 6e 63 74 20 66 72 and distinct fr
1c90: 6f 6d 20 28 30 2c 30 29 20 2a 2f 0a 20 20 69 6e om (0,0) */. in
1ca0: 74 20 4b 2c 20 44 3b 20 20 20 20 20 20 20 20 2f t K, D; /
1cb0: 2a 20 54 68 65 20 64 69 61 67 6f 6e 61 6c 20 61 * The diagonal a
1cc0: 6e 64 20 64 20 66 6f 72 20 74 68 65 20 66 69 6e nd d for the fin
1cd0: 61 6c 20 73 6f 6c 75 74 69 6f 6e 20 2a 2f 20 20 al solution */
1ce0: 20 20 20 20 20 20 20 20 0a 20 20 69 6e 74 20 2a . int *
1cf0: 52 20 3d 20 30 3b 20 20 20 20 20 20 2f 2a 20 52 R = 0; /* R
1d00: 65 73 75 6c 74 20 76 65 63 74 6f 72 20 2a 2f 0a esult vector */.
1d10: 20 20 69 6e 74 20 72 3b 20 20 20 20 20 20 20 20 int r;
1d20: 20 20 20 2f 2a 20 4c 6f 6f 70 20 76 61 72 69 61 /* Loop varia
1d30: 62 6c 65 73 20 2a 2f 0a 20 20 69 6e 74 20 67 6f bles */. int go
1d40: 20 3d 20 31 3b 20 20 20 20 20 20 2f 2a 20 4f 75 = 1; /* Ou
1d50: 74 65 72 20 6c 6f 6f 70 20 63 6f 6e 74 72 6f 6c ter loop control
1d60: 20 2a 2f 0a 20 20 69 6e 74 20 4d 41 58 3b 20 20 */. int MAX;
1d70: 20 20 20 20 20 20 20 2f 2a 20 4c 61 72 67 65 73 /* Larges
1d80: 74 20 6f 66 20 58 20 61 6e 64 20 59 20 2a 2f 0a t of X and Y */.
1d90: 0a 20 20 2f 2a 20 42 72 65 61 6b 20 74 68 65 20 . /* Break the
1da0: 74 77 6f 20 66 69 6c 65 73 20 62 65 69 6e 67 20 two files being
1db0: 64 69 66 66 65 64 20 69 6e 74 6f 20 69 6e 64 69 diffed into indi
1dc0: 76 69 64 75 61 6c 20 6c 69 6e 65 73 2e 0a 20 20 vidual lines..
1dd0: 2a 2a 20 43 6f 6d 70 75 74 65 20 68 61 73 68 65 ** Compute hashe
1de0: 73 20 6f 6e 20 65 61 63 68 20 6c 69 6e 65 20 66 s on each line f
1df0: 6f 72 20 66 61 73 74 20 63 6f 6d 70 61 72 69 73 or fast comparis
1e00: 6f 6e 2e 0a 20 20 2a 2f 0a 20 20 41 20 3d 20 62 on.. */. A = b
1e10: 72 65 61 6b 5f 69 6e 74 6f 5f 6c 69 6e 65 73 28 reak_into_lines(
1e20: 62 6c 6f 62 5f 73 74 72 28 70 41 5f 42 6c 6f 62 blob_str(pA_Blob
1e30: 29 2c 20 26 58 29 3b 0a 20 20 42 20 3d 20 62 72 ), &X);. B = br
1e40: 65 61 6b 5f 69 6e 74 6f 5f 6c 69 6e 65 73 28 62 eak_into_lines(b
1e50: 6c 6f 62 5f 73 74 72 28 70 42 5f 42 6c 6f 62 29 lob_str(pB_Blob)
1e60: 2c 20 26 59 29 3b 0a 0a 20 20 69 66 28 20 41 3d , &Y);.. if( A=
1e70: 3d 30 20 7c 7c 20 42 3d 3d 30 20 29 7b 0a 20 20 =0 || B==0 ){.
1e80: 20 20 66 72 65 65 28 41 29 3b 0a 20 20 20 20 66 free(A);. f
1e90: 72 65 65 28 42 29 3b 0a 20 20 20 20 69 66 28 20 ree(B);. if(
1ea0: 70 4f 75 74 20 29 7b 0a 20 20 20 20 20 20 62 6c pOut ){. bl
1eb0: 6f 62 5f 61 70 70 65 6e 64 66 28 70 4f 75 74 2c ob_appendf(pOut,
1ec0: 20 22 63 61 6e 6e 6f 74 20 63 6f 6d 70 75 74 65 "cannot compute
1ed0: 20 64 69 66 66 65 72 65 6e 63 65 20 62 65 74 77 difference betw
1ee0: 65 65 6e 20 62 69 6e 61 72 79 20 66 69 6c 65 73 een binary files
1ef0: 5c 6e 22 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 \n");. }.
1f00: 72 65 74 75 72 6e 20 30 3b 0a 20 20 7d 0a 0a 20 return 0;. }..
1f10: 20 73 7a 4d 20 3d 20 30 3b 0a 20 20 4d 41 58 20 szM = 0;. MAX
1f20: 3d 20 58 3e 59 20 3f 20 58 20 3a 20 59 3b 0a 20 = X>Y ? X : Y;.
1f30: 20 69 66 28 20 4d 41 58 3e 32 30 30 30 20 29 20 if( MAX>2000 )
1f40: 4d 41 58 20 3d 20 32 30 30 30 3b 0a 20 20 66 6f MAX = 2000;. fo
1f50: 72 28 64 3d 30 3b 20 67 6f 20 26 26 20 64 3c 3d r(d=0; go && d<=
1f60: 4d 41 58 3b 20 64 2b 2b 29 7b 0a 20 20 20 20 69 MAX; d++){. i
1f70: 66 28 20 73 7a 4d 3c 64 2b 31 20 29 7b 0a 20 20 f( szM<d+1 ){.
1f80: 20 20 20 20 73 7a 4d 20 2b 3d 20 73 7a 4d 20 2b szM += szM +
1f90: 20 31 30 3b 0a 20 20 20 20 20 20 4d 20 3d 20 72 10;. M = r
1fa0: 65 61 6c 6c 6f 63 28 4d 2c 20 73 69 7a 65 6f 66 ealloc(M, sizeof
1fb0: 28 4d 5b 30 5d 29 2a 73 7a 4d 29 3b 0a 20 20 20 (M[0])*szM);.
1fc0: 20 20 20 69 66 28 20 4d 3d 3d 30 20 29 7b 0a 20 if( M==0 ){.
1fd0: 20 20 20 20 20 20 20 66 6f 73 73 69 6c 5f 70 61 fossil_pa
1fe0: 6e 69 63 28 22 6f 75 74 20 6f 66 20 6d 65 6d 6f nic("out of memo
1ff0: 72 79 22 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 ry");. }.
2000: 20 20 7d 0a 20 20 20 20 4d 5b 64 5d 20 3d 20 6d }. M[d] = m
2010: 61 6c 6c 6f 63 28 20 73 69 7a 65 6f 66 28 4d 5b alloc( sizeof(M[
2020: 64 5d 5b 30 5d 29 2a 28 64 2b 31 29 20 29 3b 0a d][0])*(d+1) );.
2030: 20 20 20 20 69 66 28 20 4d 5b 64 5d 3d 3d 30 20 if( M[d]==0
2040: 29 7b 0a 20 20 20 20 20 20 66 6f 73 73 69 6c 5f ){. fossil_
2050: 70 61 6e 69 63 28 22 6f 75 74 20 6f 66 20 6d 65 panic("out of me
2060: 6d 6f 72 79 22 29 3b 0a 20 20 20 20 7d 0a 20 20 mory");. }.
2070: 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 3d 64 3b for(i=0; i<=d;
2080: 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 6b 20 3d i++){. k =
2090: 20 32 2a 69 20 2d 20 64 3b 0a 20 20 20 20 20 20 2*i - d;.
20a0: 69 66 28 20 64 3d 3d 30 20 29 7b 0a 20 20 20 20 if( d==0 ){.
20b0: 20 20 20 20 71 20 3d 20 30 3b 0a 20 20 20 20 20 q = 0;.
20c0: 20 7d 65 6c 73 65 20 69 66 28 20 69 3d 3d 30 20 }else if( i==0
20d0: 29 7b 0a 20 20 20 20 20 20 20 20 71 20 3d 20 4d ){. q = M
20e0: 5b 64 2d 31 5d 5b 30 5d 3b 0a 20 20 20 20 20 20 [d-1][0];.
20f0: 7d 65 6c 73 65 20 69 66 28 20 69 3c 64 2d 31 20 }else if( i<d-1
2100: 26 26 20 4d 5b 64 2d 31 5d 5b 69 2d 31 5d 20 3c && M[d-1][i-1] <
2110: 20 4d 5b 64 2d 31 5d 5b 69 5d 20 29 7b 0a 20 20 M[d-1][i] ){.
2120: 20 20 20 20 20 20 71 20 3d 20 4d 5b 64 2d 31 5d q = M[d-1]
2130: 5b 69 5d 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 [i];. }else
2140: 7b 0a 20 20 20 20 20 20 20 20 71 20 3d 20 4d 5b {. q = M[
2150: 64 2d 31 5d 5b 69 2d 31 5d 3b 0a 20 20 20 20 20 d-1][i-1];.
2160: 20 7d 0a 20 20 20 20 20 20 78 20 3d 20 28 6b 20 }. x = (k
2170: 2b 20 71 20 2b 20 31 29 2f 32 3b 0a 20 20 20 20 + q + 1)/2;.
2180: 20 20 79 20 3d 20 78 20 2d 20 6b 3b 0a 20 20 20 y = x - k;.
2190: 20 20 20 69 66 28 20 78 3c 30 20 7c 7c 20 78 3e if( x<0 || x>
21a0: 58 20 7c 7c 20 79 3c 30 20 7c 7c 20 79 3e 59 20 X || y<0 || y>Y
21b0: 29 7b 0a 20 20 20 20 20 20 20 20 78 20 3d 20 79 ){. x = y
21c0: 20 3d 20 30 3b 0a 20 20 20 20 20 20 7d 65 6c 73 = 0;. }els
21d0: 65 7b 0a 20 20 20 20 20 20 20 20 77 68 69 6c 65 e{. while
21e0: 28 20 78 3c 58 20 26 26 20 79 3c 59 20 26 26 20 ( x<X && y<Y &&
21f0: 73 61 6d 65 5f 64 6c 69 6e 65 28 26 41 5b 78 5d same_dline(&A[x]
2200: 2c 26 42 5b 79 5d 29 20 29 7b 20 78 2b 2b 3b 20 ,&B[y]) ){ x++;
2210: 79 2b 2b 3b 20 7d 0a 20 20 20 20 20 20 7d 0a 20 y++; }. }.
2220: 20 20 20 20 20 4d 5b 64 5d 5b 69 5d 20 3d 20 78 M[d][i] = x
2230: 20 2b 20 79 3b 0a 20 20 20 20 20 20 44 45 42 55 + y;. DEBU
2240: 47 28 20 70 72 69 6e 74 66 28 22 4d 5b 25 64 5d G( printf("M[%d]
2250: 5b 25 69 5d 20 3d 20 25 64 20 20 6b 3d 25 64 20 [%i] = %d k=%d
2260: 28 25 64 2c 25 64 29 5c 6e 22 2c 20 64 2c 20 69 (%d,%d)\n", d, i
2270: 2c 20 78 2b 79 2c 20 6b 2c 20 78 2c 20 79 29 3b , x+y, k, x, y);
2280: 20 29 0a 20 20 20 20 20 20 69 66 28 20 78 3d 3d ). if( x==
2290: 58 20 26 26 20 79 3d 3d 59 20 29 7b 0a 20 20 20 X && y==Y ){.
22a0: 20 20 20 20 20 67 6f 20 3d 20 30 3b 0a 20 20 20 go = 0;.
22b0: 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 break;.
22c0: 20 20 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 }. }. }.
22d0: 69 66 28 20 64 3e 4d 41 58 20 29 7b 0a 20 20 20 if( d>MAX ){.
22e0: 20 52 20 3d 20 6d 61 6c 6c 6f 63 28 20 73 69 7a R = malloc( siz
22f0: 65 6f 66 28 52 5b 30 5d 29 2a 37 20 29 3b 0a 20 eof(R[0])*7 );.
2300: 20 20 20 52 5b 30 5d 20 3d 20 30 3b 0a 20 20 20 R[0] = 0;.
2310: 20 52 5b 31 5d 20 3d 20 58 3b 0a 20 20 20 20 52 R[1] = X;. R
2320: 5b 32 5d 20 3d 20 59 3b 0a 20 20 20 20 52 5b 33 [2] = Y;. R[3
2330: 5d 20 3d 20 30 3b 0a 20 20 20 20 52 5b 34 5d 20 ] = 0;. R[4]
2340: 3d 20 30 3b 0a 20 20 20 20 52 5b 35 5d 20 3d 20 = 0;. R[5] =
2350: 30 3b 0a 20 20 20 20 52 5b 36 5d 20 3d 20 30 3b 0;. R[6] = 0;
2360: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2f 2a . }else{. /*
2370: 20 52 65 75 73 65 20 4d 5b 5d 20 61 73 20 66 6f Reuse M[] as fo
2380: 6c 6c 6f 77 73 3a 0a 20 20 20 20 2a 2a 0a 20 20 llows:. **.
2390: 20 20 2a 2a 20 20 20 20 20 4d 5b 64 5d 5b 31 5d ** M[d][1]
23a0: 20 3d 20 31 20 69 66 20 61 20 6c 69 6e 65 20 69 = 1 if a line i
23b0: 73 20 69 6e 73 65 72 74 65 64 20 6f 72 20 30 20 s inserted or 0
23c0: 69 66 20 61 20 6c 69 6e 65 20 69 73 20 64 65 6c if a line is del
23d0: 65 74 65 64 2e 0a 20 20 20 20 2a 2a 20 20 20 20 eted.. **
23e0: 20 4d 5b 64 5d 5b 30 5d 20 3d 20 6e 75 6d 62 65 M[d][0] = numbe
23f0: 72 20 6f 66 20 6c 69 6e 65 73 20 63 6f 70 69 65 r of lines copie
2400: 64 20 61 66 74 65 72 20 74 68 65 20 69 6e 73 20 d after the ins
2410: 6f 72 20 64 65 6c 20 61 62 6f 76 65 2e 0a 20 20 or del above..
2420: 20 20 2a 2a 0a 20 20 20 20 2a 2f 0a 20 20 20 20 **. */.
2430: 44 20 3d 20 64 20 2d 20 31 3b 0a 20 20 20 20 4b D = d - 1;. K
2440: 20 3d 20 58 20 2d 20 59 3b 0a 20 20 20 20 66 6f = X - Y;. fo
2450: 72 28 64 3d 44 2c 20 69 3d 28 4b 2b 44 29 2f 32 r(d=D, i=(K+D)/2
2460: 3b 20 64 3e 30 3b 20 64 2d 2d 29 7b 0a 20 20 20 ; d>0; d--){.
2470: 20 20 20 44 45 42 55 47 28 20 70 72 69 6e 74 66 DEBUG( printf
2480: 28 22 64 3d 25 64 20 69 3d 25 64 5c 6e 22 2c 20 ("d=%d i=%d\n",
2490: 64 2c 20 69 29 3b 20 29 0a 20 20 20 20 20 20 69 d, i); ). i
24a0: 66 28 20 69 3d 3d 64 20 7c 7c 20 28 69 3e 30 20 f( i==d || (i>0
24b0: 26 26 20 4d 5b 64 2d 31 5d 5b 69 2d 31 5d 20 3e && M[d-1][i-1] >
24c0: 20 4d 5b 64 2d 31 5d 5b 69 5d 29 20 29 7b 0a 20 M[d-1][i]) ){.
24d0: 20 20 20 20 20 20 20 4d 5b 64 5d 5b 30 5d 20 3d M[d][0] =
24e0: 20 4d 5b 64 5d 5b 69 5d 20 2d 20 4d 5b 64 2d 31 M[d][i] - M[d-1
24f0: 5d 5b 69 2d 31 5d 20 2d 20 31 3b 0a 20 20 20 20 ][i-1] - 1;.
2500: 20 20 20 20 4d 5b 64 5d 5b 31 5d 20 3d 20 30 3b M[d][1] = 0;
2510: 0a 20 20 20 20 20 20 20 20 69 2d 2d 3b 0a 20 20 . i--;.
2520: 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 }else{.
2530: 20 20 20 4d 5b 64 5d 5b 30 5d 20 3d 20 4d 5b 64 M[d][0] = M[d
2540: 5d 5b 69 5d 20 2d 20 4d 5b 64 2d 31 5d 5b 69 5d ][i] - M[d-1][i]
2550: 20 2d 20 31 3b 0a 20 20 20 20 20 20 20 20 4d 5b - 1;. M[
2560: 64 5d 5b 31 5d 20 3d 20 31 3b 0a 20 20 20 20 20 d][1] = 1;.
2570: 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 0a 20 20 }. }. .
2580: 20 20 44 45 42 55 47 28 0a 20 20 20 20 20 20 70 DEBUG(. p
2590: 72 69 6e 74 66 28 22 2d 2d 2d 2d 2d 2d 2d 2d 2d rintf("---------
25a0: 2d 2d 2d 2d 2d 2d 5c 6e 4d 5b 30 5d 5b 30 5d 20 ------\nM[0][0]
25b0: 3d 20 25 35 64 5c 6e 22 2c 20 4d 5b 30 5d 5b 30 = %5d\n", M[0][0
25c0: 5d 29 3b 0a 20 20 20 20 20 20 66 6f 72 28 64 3d ]);. for(d=
25d0: 31 3b 20 64 3c 3d 44 3b 20 64 2b 2b 29 7b 0a 20 1; d<=D; d++){.
25e0: 20 20 20 20 20 20 20 70 72 69 6e 74 66 28 22 4d printf("M
25f0: 5b 25 64 5d 5b 30 5d 20 3d 20 25 35 64 20 20 20 [%d][0] = %5d
2600: 20 4d 5b 25 64 5d 5b 31 5d 20 3d 20 25 64 5c 6e M[%d][1] = %d\n
2610: 22 2c 64 2c 4d 5b 64 5d 5b 30 5d 2c 64 2c 4d 5b ",d,M[d][0],d,M[
2620: 64 5d 5b 31 5d 29 3b 0a 20 20 20 20 20 20 7d 0a d][1]);. }.
2630: 20 20 20 20 29 0a 20 20 20 20 0a 20 20 20 20 2f ). . /
2640: 2a 20 41 6c 6c 6f 63 61 74 65 20 74 68 65 20 6f * Allocate the o
2650: 75 74 70 75 74 20 76 65 63 74 6f 72 0a 20 20 20 utput vector.
2660: 20 2a 2f 0a 20 20 20 20 52 20 3d 20 6d 61 6c 6c */. R = mall
2670: 6f 63 28 20 73 69 7a 65 6f 66 28 52 5b 30 5d 29 oc( sizeof(R[0])
2680: 2a 28 44 2b 32 29 2a 33 20 29 3b 0a 20 20 20 20 *(D+2)*3 );.
2690: 69 66 28 20 52 3d 3d 30 20 29 7b 0a 20 20 20 20 if( R==0 ){.
26a0: 20 20 66 6f 73 73 69 6c 5f 66 61 74 61 6c 28 22 fossil_fatal("
26b0: 6f 75 74 20 6f 66 20 6d 65 6d 6f 72 79 22 29 3b out of memory");
26c0: 0a 20 20 20 20 7d 0a 20 20 20 20 0a 20 20 20 20 . }. .
26d0: 2f 2a 20 50 6f 70 75 6c 61 74 65 20 74 68 65 20 /* Populate the
26e0: 6f 75 74 70 75 74 20 76 65 63 74 6f 72 0a 20 20 output vector.
26f0: 20 20 2a 2f 0a 20 20 20 20 64 20 3d 20 72 20 3d */. d = r =
2700: 20 30 3b 0a 20 20 20 20 77 68 69 6c 65 28 20 64 0;. while( d
2710: 3c 3d 44 20 29 7b 0a 20 20 20 20 20 20 69 6e 74 <=D ){. int
2720: 20 6e 3b 0a 20 20 20 20 20 20 52 5b 72 2b 2b 5d n;. R[r++]
2730: 20 3d 20 4d 5b 64 2b 2b 5d 5b 30 5d 2f 32 3b 20 = M[d++][0]/2;
2740: 20 20 2f 2a 20 43 4f 50 59 20 2a 2f 0a 20 20 20 /* COPY */.
2750: 20 20 20 69 66 28 20 64 3e 44 20 29 7b 0a 20 20 if( d>D ){.
2760: 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 R[r++] = 0
2770: 3b 0a 20 20 20 20 20 20 20 20 52 5b 72 2b 2b 5d ;. R[r++]
2780: 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 62 72 = 0;. br
2790: 65 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 eak;. }.
27a0: 20 20 20 69 66 28 20 4d 5b 64 5d 5b 31 5d 3d 3d if( M[d][1]==
27b0: 30 20 29 7b 0a 20 20 20 20 20 20 20 20 6e 20 3d 0 ){. n =
27c0: 20 31 3b 0a 20 20 20 20 20 20 20 20 77 68 69 6c 1;. whil
27d0: 65 28 20 4d 5b 64 5d 5b 30 5d 3d 3d 30 20 26 26 e( M[d][0]==0 &&
27e0: 20 64 3c 44 20 26 26 20 4d 5b 64 2b 31 5d 5b 31 d<D && M[d+1][1
27f0: 5d 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 20 20 ]==0 ){.
2800: 20 20 64 2b 2b 3b 0a 20 20 20 20 20 20 20 20 20 d++;.
2810: 20 6e 2b 2b 3b 0a 20 20 20 20 20 20 20 20 7d 0a n++;. }.
2820: 20 20 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d R[r++] =
2830: 20 6e 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a n; /*
2840: 20 44 45 4c 45 54 45 20 2a 2f 0a 20 20 20 20 20 DELETE */.
2850: 20 20 20 69 66 28 20 64 3d 3d 44 20 7c 7c 20 4d if( d==D || M
2860: 5b 64 5d 5b 30 5d 3e 30 20 29 7b 0a 20 20 20 20 [d][0]>0 ){.
2870: 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 R[r++] = 0
2880: 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 49 4e 53 ; /* INS
2890: 45 52 54 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 ERT */.
28a0: 20 63 6f 6e 74 69 6e 75 65 3b 0a 20 20 20 20 20 continue;.
28b0: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 64 2b 2b }. d++
28c0: 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 ;. }else{.
28d0: 20 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 R[r++] =
28e0: 30 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 0; /*
28f0: 44 45 4c 45 54 45 20 2a 2f 0a 20 20 20 20 20 20 DELETE */.
2900: 7d 0a 20 20 20 20 20 20 61 73 73 65 72 74 28 20 }. assert(
2910: 4d 5b 64 5d 5b 31 5d 3d 3d 31 20 29 3b 0a 20 20 M[d][1]==1 );.
2920: 20 20 20 20 6e 20 3d 20 31 3b 0a 20 20 20 20 20 n = 1;.
2930: 20 77 68 69 6c 65 28 20 4d 5b 64 5d 5b 30 5d 3d while( M[d][0]=
2940: 3d 30 20 26 26 20 64 3c 44 20 26 26 20 4d 5b 64 =0 && d<D && M[d
2950: 2b 31 5d 5b 31 5d 3d 3d 31 20 29 7b 0a 20 20 20 +1][1]==1 ){.
2960: 20 20 20 20 20 64 2b 2b 3b 0a 20 20 20 20 20 20 d++;.
2970: 20 20 6e 2b 2b 3b 0a 20 20 20 20 20 20 7d 0a 20 n++;. }.
2980: 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 6e 3b R[r++] = n;
2990: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 /* I
29a0: 4e 53 45 52 54 20 2a 2f 0a 20 20 20 20 7d 0a 20 NSERT */. }.
29b0: 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 0a 20 R[r++] = 0;.
29c0: 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 0a 20 R[r++] = 0;.
29d0: 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 0a 20 R[r++] = 0;.
29e0: 20 7d 0a 20 20 20 20 0a 20 20 2f 2a 20 46 72 65 }. . /* Fre
29f0: 65 20 74 68 65 20 4d 79 65 72 73 20 6d 61 74 72 e the Myers matr
2a00: 69 78 20 2a 2f 0a 20 20 66 6f 72 28 64 3d 30 3b ix */. for(d=0;
2a10: 20 64 3c 3d 44 3b 20 64 2b 2b 29 7b 0a 20 20 20 d<=D; d++){.
2a20: 20 66 72 65 65 28 4d 5b 64 5d 29 3b 0a 20 20 7d free(M[d]);. }
2a30: 0a 20 20 66 72 65 65 28 4d 29 3b 0a 0a 20 20 2f . free(M);.. /
2a40: 2a 20 49 66 20 70 4f 75 74 20 69 73 20 64 65 66 * If pOut is def
2a50: 69 6e 65 64 2c 20 63 6f 6e 73 74 72 75 63 74 20 ined, construct
2a60: 61 20 75 6e 69 66 69 65 64 20 64 69 66 66 20 69 a unified diff i
2a70: 6e 74 6f 20 70 4f 75 74 20 61 6e 64 0a 20 20 2a nto pOut and. *
2a80: 2a 20 64 65 6c 65 74 65 20 52 0a 20 20 2a 2f 0a * delete R. */.
2a90: 20 20 69 66 28 20 70 4f 75 74 20 29 7b 0a 20 20 if( pOut ){.
2aa0: 20 20 69 6e 74 20 61 20 3d 20 30 3b 20 20 20 20 int a = 0;
2ab0: 2f 2a 20 49 6e 64 65 78 20 6f 66 20 6e 65 78 74 /* Index of next
2ac0: 20 6c 69 6e 65 20 69 6e 20 41 5b 5d 20 2a 2f 0a line in A[] */.
2ad0: 20 20 20 20 69 6e 74 20 62 20 3d 20 30 3b 20 20 int b = 0;
2ae0: 20 20 2f 2a 20 49 6e 64 65 78 20 6f 66 20 6e 65 /* Index of ne
2af0: 78 74 20 6c 69 6e 65 20 69 6e 20 42 5b 5d 20 2a xt line in B[] *
2b00: 2f 0a 20 20 20 20 69 6e 74 20 6e 72 3b 20 20 20 /. int nr;
2b10: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 /* Number of
2b20: 20 43 4f 50 59 2f 44 45 4c 45 54 45 2f 49 4e 53 COPY/DELETE/INS
2b30: 45 52 54 20 74 72 69 70 6c 65 73 20 74 6f 20 70 ERT triples to p
2b40: 72 6f 63 65 73 73 20 2a 2f 0a 20 20 20 20 69 6e rocess */. in
2b50: 74 20 6d 78 72 3b 20 20 20 20 20 20 2f 2a 20 4d t mxr; /* M
2b60: 61 78 69 6d 75 6d 20 76 61 6c 75 65 20 66 6f 72 aximum value for
2b70: 20 72 20 2a 2f 0a 20 20 20 20 69 6e 74 20 6e 61 r */. int na
2b80: 2c 20 6e 62 3b 20 20 20 2f 2a 20 4e 75 6d 62 65 , nb; /* Numbe
2b90: 72 20 6f 66 20 6c 69 6e 65 73 20 73 68 6f 77 6e r of lines shown
2ba0: 20 66 72 6f 6d 20 41 20 61 6e 64 20 42 20 2a 2f from A and B */
2bb0: 0a 20 20 20 20 69 6e 74 20 69 2c 20 6a 3b 20 20 . int i, j;
2bc0: 20 20 20 2f 2a 20 4c 6f 6f 70 20 63 6f 75 6e 74 /* Loop count
2bd0: 65 72 73 20 2a 2f 0a 20 20 20 20 69 6e 74 20 6d ers */. int m
2be0: 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 ; /* Numb
2bf0: 65 72 20 6f 66 20 6c 69 6e 65 73 20 74 6f 20 6f er of lines to o
2c00: 75 74 70 75 74 20 2a 2f 0a 20 20 20 20 69 6e 74 utput */. int
2c10: 20 73 6b 69 70 3b 20 20 20 20 20 2f 2a 20 4e 75 skip; /* Nu
2c20: 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 74 6f mber of lines to
2c30: 20 73 6b 69 70 20 2a 2f 0a 0a 20 20 20 20 66 6f skip */.. fo
2c40: 72 28 6d 78 72 3d 30 3b 20 52 5b 6d 78 72 2b 31 r(mxr=0; R[mxr+1
2c50: 5d 20 7c 7c 20 52 5b 6d 78 72 2b 32 5d 20 7c 7c ] || R[mxr+2] ||
2c60: 20 52 5b 6d 78 72 2b 33 5d 3b 20 6d 78 72 20 2b R[mxr+3]; mxr +
2c70: 3d 20 33 29 7b 7d 0a 20 20 20 20 66 6f 72 28 72 = 3){}. for(r
2c80: 3d 30 3b 20 72 3c 6d 78 72 3b 20 72 20 2b 3d 20 =0; r<mxr; r +=
2c90: 33 2a 6e 72 29 7b 0a 20 20 20 20 20 20 2f 2a 20 3*nr){. /*
2ca0: 46 69 67 75 72 65 20 6f 75 74 20 68 6f 77 20 6d Figure out how m
2cb0: 61 6e 79 20 74 72 69 70 6c 65 73 20 74 6f 20 73 any triples to s
2cc0: 68 6f 77 20 69 6e 20 61 20 73 69 6e 67 6c 65 20 how in a single
2cd0: 62 6c 6f 63 6b 20 2a 2f 0a 20 20 20 20 20 20 66 block */. f
2ce0: 6f 72 28 6e 72 3d 31 3b 20 52 5b 72 2b 6e 72 2a or(nr=1; R[r+nr*
2cf0: 33 5d 3e 30 20 26 26 20 52 5b 72 2b 6e 72 2a 33 3]>0 && R[r+nr*3
2d00: 5d 3c 6e 43 6f 6e 74 65 78 74 2a 32 3b 20 6e 72 ]<nContext*2; nr
2d10: 2b 2b 29 7b 7d 0a 20 20 20 20 20 20 44 45 42 55 ++){}. DEBU
2d20: 47 28 20 70 72 69 6e 74 66 28 22 72 3d 25 64 20 G( printf("r=%d
2d30: 6e 72 3d 25 64 5c 6e 22 2c 20 72 2c 20 6e 72 29 nr=%d\n", r, nr)
2d40: 3b 20 29 0a 0a 20 20 20 20 20 20 2f 2a 20 46 6f ; ).. /* Fo
2d50: 72 20 74 68 65 20 63 75 72 72 65 6e 74 20 62 6c r the current bl
2d60: 6f 63 6b 20 63 6f 6d 70 72 69 73 69 6e 67 20 6e ock comprising n
2d70: 72 20 74 72 69 70 6c 65 73 2c 20 66 69 67 75 72 r triples, figur
2d80: 65 20 6f 75 74 0a 20 20 20 20 20 20 2a 2a 20 68 e out. ** h
2d90: 6f 77 20 6d 61 6e 79 20 6c 69 6e 65 73 20 6f 66 ow many lines of
2da0: 20 41 20 61 6e 64 20 42 20 61 72 65 20 74 6f 20 A and B are to
2db0: 62 65 20 64 69 73 70 6c 61 79 65 64 0a 20 20 20 be displayed.
2dc0: 20 20 20 2a 2f 0a 20 20 20 20 20 20 69 66 28 20 */. if(
2dd0: 52 5b 72 5d 3e 6e 43 6f 6e 74 65 78 74 20 29 7b R[r]>nContext ){
2de0: 0a 20 20 20 20 20 20 20 20 6e 61 20 3d 20 6e 62 . na = nb
2df0: 20 3d 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 20 20 = nContext;.
2e00: 20 20 20 20 20 73 6b 69 70 20 3d 20 52 5b 72 5d skip = R[r]
2e10: 20 2d 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 20 20 - nContext;.
2e20: 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 }else{.
2e30: 20 20 6e 61 20 3d 20 6e 62 20 3d 20 52 5b 72 5d na = nb = R[r]
2e40: 3b 0a 20 20 20 20 20 20 20 20 73 6b 69 70 20 3d ;. skip =
2e50: 20 30 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 0;. }.
2e60: 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 6e 72 3b for(i=0; i<nr;
2e70: 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 6e i++){. n
2e80: 61 20 2b 3d 20 52 5b 72 2b 69 2a 33 2b 31 5d 3b a += R[r+i*3+1];
2e90: 0a 20 20 20 20 20 20 20 20 6e 62 20 2b 3d 20 52 . nb += R
2ea0: 5b 72 2b 69 2a 33 2b 32 5d 3b 0a 20 20 20 20 20 [r+i*3+2];.
2eb0: 20 7d 0a 20 20 20 20 20 20 69 66 28 20 52 5b 72 }. if( R[r
2ec0: 2b 6e 72 2a 33 5d 3e 6e 43 6f 6e 74 65 78 74 20 +nr*3]>nContext
2ed0: 29 7b 0a 20 20 20 20 20 20 20 20 6e 61 20 2b 3d ){. na +=
2ee0: 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 20 20 20 20 nContext;.
2ef0: 20 20 20 6e 62 20 2b 3d 20 6e 43 6f 6e 74 65 78 nb += nContex
2f00: 74 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a t;. }else{.
2f10: 20 20 20 20 20 20 20 20 6e 61 20 2b 3d 20 52 5b na += R[
2f20: 72 2b 6e 72 2a 33 5d 3b 0a 20 20 20 20 20 20 20 r+nr*3];.
2f30: 20 6e 62 20 2b 3d 20 52 5b 72 2b 6e 72 2a 33 5d nb += R[r+nr*3]
2f40: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 ;. }.
2f50: 66 6f 72 28 69 3d 31 3b 20 69 3c 6e 72 3b 20 69 for(i=1; i<nr; i
2f60: 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 6e 61 20 ++){. na
2f70: 2b 3d 20 52 5b 72 2b 69 2a 33 5d 3b 0a 20 20 20 += R[r+i*3];.
2f80: 20 20 20 20 20 6e 62 20 2b 3d 20 52 5b 72 2b 69 nb += R[r+i
2f90: 2a 33 5d 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 *3];. }.
2fa0: 20 20 20 62 6c 6f 62 5f 61 70 70 65 6e 64 66 28 blob_appendf(
2fb0: 70 4f 75 74 2c 22 40 40 20 2d 25 64 2c 25 64 20 pOut,"@@ -%d,%d
2fc0: 2b 25 64 2c 25 64 20 40 40 5c 6e 22 2c 20 61 2b +%d,%d @@\n", a+
2fd0: 73 6b 69 70 2b 31 2c 20 6e 61 2c 20 62 2b 73 6b skip+1, na, b+sk
2fe0: 69 70 2b 31 2c 20 6e 62 29 3b 0a 0a 20 20 20 20 ip+1, nb);..
2ff0: 20 20 2f 2a 20 53 68 6f 77 20 74 68 65 20 69 6e /* Show the in
3000: 69 74 69 61 6c 20 63 6f 6d 6d 6f 6e 20 61 72 65 itial common are
3010: 61 20 2a 2f 0a 20 20 20 20 20 20 61 20 2b 3d 20 a */. a +=
3020: 73 6b 69 70 3b 0a 20 20 20 20 20 20 62 20 2b 3d skip;. b +=
3030: 20 73 6b 69 70 3b 0a 20 20 20 20 20 20 6d 20 3d skip;. m =
3040: 20 52 5b 72 5d 20 2d 20 73 6b 69 70 3b 0a 20 20 R[r] - skip;.
3050: 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c 6d for(j=0; j<m
3060: 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 ; j++){.
3070: 61 70 70 65 6e 64 44 69 66 66 4c 69 6e 65 28 70 appendDiffLine(p
3080: 4f 75 74 2c 20 22 20 22 2c 20 26 41 5b 61 2b 6a Out, " ", &A[a+j
3090: 5d 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 ]);. }.
30a0: 20 20 61 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 20 a += m;.
30b0: 62 20 2b 3d 20 6d 3b 0a 0a 20 20 20 20 20 20 2f b += m;.. /
30c0: 2a 20 53 68 6f 77 20 74 68 65 20 64 69 66 66 65 * Show the diffe
30d0: 72 65 6e 63 65 73 20 2a 2f 0a 20 20 20 20 20 20 rences */.
30e0: 66 6f 72 28 69 3d 30 3b 20 69 3c 6e 72 3b 20 69 for(i=0; i<nr; i
30f0: 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 6d 20 3d ++){. m =
3100: 20 52 5b 72 2b 69 2a 33 2b 31 5d 3b 0a 20 20 20 R[r+i*3+1];.
3110: 20 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c for(j=0; j<
3120: 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 20 m; j++){.
3130: 20 20 20 61 70 70 65 6e 64 44 69 66 66 4c 69 6e appendDiffLin
3140: 65 28 70 4f 75 74 2c 20 22 2d 22 2c 20 26 41 5b e(pOut, "-", &A[
3150: 61 2b 6a 5d 29 3b 0a 20 20 20 20 20 20 20 20 7d a+j]);. }
3160: 0a 20 20 20 20 20 20 20 20 61 20 2b 3d 20 6d 3b . a += m;
3170: 0a 20 20 20 20 20 20 20 20 6d 20 3d 20 52 5b 72 . m = R[r
3180: 2b 69 2a 33 2b 32 5d 3b 0a 20 20 20 20 20 20 20 +i*3+2];.
3190: 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a for(j=0; j<m; j
31a0: 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 20 20 61 ++){. a
31b0: 70 70 65 6e 64 44 69 66 66 4c 69 6e 65 28 70 4f ppendDiffLine(pO
31c0: 75 74 2c 20 22 2b 22 2c 20 26 42 5b 62 2b 6a 5d ut, "+", &B[b+j]
31d0: 29 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 );. }.
31e0: 20 20 20 20 20 62 20 2b 3d 20 6d 3b 0a 20 20 20 b += m;.
31f0: 20 20 20 20 20 69 66 28 20 69 3c 6e 72 2d 31 20 if( i<nr-1
3200: 29 7b 0a 20 20 20 20 20 20 20 20 20 20 6d 20 3d ){. m =
3210: 20 52 5b 72 2b 69 2a 33 2b 33 5d 3b 0a 20 20 20 R[r+i*3+3];.
3220: 20 20 20 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 for(j=0;
3230: 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 j<m; j++){.
3240: 20 20 20 20 20 20 20 61 70 70 65 6e 64 44 69 66 appendDif
3250: 66 4c 69 6e 65 28 70 4f 75 74 2c 20 22 20 22 2c fLine(pOut, " ",
3260: 20 26 42 5b 62 2b 6a 5d 29 3b 0a 20 20 20 20 20 &B[b+j]);.
3270: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 }.
3280: 20 62 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 20 20 b += m;.
3290: 20 20 20 61 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 a += m;.
32a0: 20 20 20 7d 0a 20 20 20 20 20 20 7d 0a 0a 20 20 }. }..
32b0: 20 20 20 20 2f 2a 20 53 68 6f 77 20 74 68 65 20 /* Show the
32c0: 66 69 6e 61 6c 20 63 6f 6d 6d 6f 6e 20 61 72 65 final common are
32d0: 61 20 2a 2f 0a 20 20 20 20 20 20 61 73 73 65 72 a */. asser
32e0: 74 28 20 6e 72 3d 3d 69 20 29 3b 0a 20 20 20 20 t( nr==i );.
32f0: 20 20 6d 20 3d 20 52 5b 72 2b 6e 72 2a 33 5d 3b m = R[r+nr*3];
3300: 0a 20 20 20 20 20 20 69 66 28 20 6d 3e 6e 43 6f . if( m>nCo
3310: 6e 74 65 78 74 20 29 20 6d 20 3d 20 6e 43 6f 6e ntext ) m = nCon
3320: 74 65 78 74 3b 0a 20 20 20 20 20 20 66 6f 72 28 text;. for(
3330: 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a j=0; j<m; j++){.
3340: 20 20 20 20 20 20 20 20 61 70 70 65 6e 64 44 69 appendDi
3350: 66 66 4c 69 6e 65 28 70 4f 75 74 2c 20 22 20 22 ffLine(pOut, " "
3360: 2c 20 26 42 5b 62 2b 6a 5d 29 3b 0a 20 20 20 20 , &B[b+j]);.
3370: 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 66 72 }. }. fr
3380: 65 65 28 52 29 3b 0a 20 20 20 20 52 20 3d 20 30 ee(R);. R = 0
3390: 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 57 65 20 6e ;. }.. /* We n
33a0: 6f 20 6c 6f 6e 67 65 72 20 6e 65 65 64 20 74 68 o longer need th
33b0: 65 20 41 5b 5d 20 61 6e 64 20 42 5b 5d 20 76 65 e A[] and B[] ve
33c0: 63 74 6f 72 73 20 2a 2f 0a 20 20 66 72 65 65 28 ctors */. free(
33d0: 41 29 3b 0a 20 20 66 72 65 65 28 42 29 3b 0a 0a A);. free(B);..
33e0: 20 20 2f 2a 20 52 65 74 75 72 6e 20 74 68 65 20 /* Return the
33f0: 72 65 73 75 6c 74 20 2a 2f 0a 20 20 72 65 74 75 result */. retu
3400: 72 6e 20 52 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 rn R;.}../*.** C
3410: 4f 4d 4d 41 4e 44 3a 20 74 65 73 74 2d 72 61 77 OMMAND: test-raw
3420: 64 69 66 66 0a 2a 2f 0a 76 6f 69 64 20 74 65 73 diff.*/.void tes
3430: 74 5f 72 61 77 64 69 66 66 5f 63 6d 64 28 76 6f t_rawdiff_cmd(vo
3440: 69 64 29 7b 0a 20 20 42 6c 6f 62 20 61 2c 20 62 id){. Blob a, b
3450: 3b 0a 20 20 69 6e 74 20 72 3b 0a 20 20 69 6e 74 ;. int r;. int
3460: 20 69 3b 0a 20 20 69 6e 74 20 2a 52 3b 0a 20 20 i;. int *R;.
3470: 69 66 28 20 67 2e 61 72 67 63 3c 34 20 29 20 75 if( g.argc<4 ) u
3480: 73 61 67 65 28 22 46 49 4c 45 31 20 46 49 4c 45 sage("FILE1 FILE
3490: 32 20 2e 2e 2e 22 29 3b 0a 20 20 62 6c 6f 62 5f 2 ...");. blob_
34a0: 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 read_from_file(&
34b0: 61 2c 20 67 2e 61 72 67 76 5b 32 5d 29 3b 0a 20 a, g.argv[2]);.
34c0: 20 66 6f 72 28 69 3d 33 3b 20 69 3c 67 2e 61 72 for(i=3; i<g.ar
34d0: 67 63 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 69 66 gc; i++){. if
34e0: 28 20 69 3e 33 20 29 20 70 72 69 6e 74 66 28 22 ( i>3 ) printf("
34f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3500: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 5c ---------------\
3510: 6e 22 29 3b 0a 20 20 20 20 62 6c 6f 62 5f 72 65 n");. blob_re
3520: 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 62 2c ad_from_file(&b,
3530: 20 67 2e 61 72 67 76 5b 69 5d 29 3b 0a 20 20 20 g.argv[i]);.
3540: 20 52 20 3d 20 74 65 78 74 5f 64 69 66 66 28 26 R = text_diff(&
3550: 61 2c 20 26 62 2c 20 30 2c 20 30 29 3b 0a 20 20 a, &b, 0, 0);.
3560: 20 20 66 6f 72 28 72 3d 30 3b 20 52 5b 72 5d 20 for(r=0; R[r]
3570: 7c 7c 20 52 5b 72 2b 31 5d 20 7c 7c 20 52 5b 72 || R[r+1] || R[r
3580: 2b 32 5d 3b 20 72 20 2b 3d 20 33 29 7b 0a 20 20 +2]; r += 3){.
3590: 20 20 20 20 70 72 69 6e 74 66 28 22 20 63 6f 70 printf(" cop
35a0: 79 20 25 34 64 20 20 64 65 6c 65 74 65 20 25 34 y %4d delete %4
35b0: 64 20 20 69 6e 73 65 72 74 20 25 34 64 5c 6e 22 d insert %4d\n"
35c0: 2c 20 52 5b 72 5d 2c 20 52 5b 72 2b 31 5d 2c 20 , R[r], R[r+1],
35d0: 52 5b 72 2b 32 5d 29 3b 0a 20 20 20 20 7d 0a 20 R[r+2]);. }.
35e0: 20 20 20 2f 2a 20 66 72 65 65 28 52 29 3b 20 2a /* free(R); *
35f0: 2f 0a 20 20 20 20 62 6c 6f 62 5f 72 65 73 65 74 /. blob_reset
3600: 28 26 62 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a (&b);. }.}../*.
3610: 2a 2a 20 43 4f 4d 4d 41 4e 44 3a 20 74 65 73 74 ** COMMAND: test
3620: 2d 75 64 69 66 66 0a 2a 2f 0a 76 6f 69 64 20 74 -udiff.*/.void t
3630: 65 73 74 5f 75 64 69 66 66 5f 63 6d 64 28 76 6f est_udiff_cmd(vo
3640: 69 64 29 7b 0a 20 20 42 6c 6f 62 20 61 2c 20 62 id){. Blob a, b
3650: 2c 20 6f 75 74 3b 0a 20 20 69 66 28 20 67 2e 61 , out;. if( g.a
3660: 72 67 63 21 3d 34 20 29 20 75 73 61 67 65 28 22 rgc!=4 ) usage("
3670: 46 49 4c 45 31 20 46 49 4c 45 32 22 29 3b 0a 20 FILE1 FILE2");.
3680: 20 62 6c 6f 62 5f 72 65 61 64 5f 66 72 6f 6d 5f blob_read_from_
3690: 66 69 6c 65 28 26 61 2c 20 67 2e 61 72 67 76 5b file(&a, g.argv[
36a0: 32 5d 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 61 64 2]);. blob_read
36b0: 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 62 2c 20 67 _from_file(&b, g
36c0: 2e 61 72 67 76 5b 33 5d 29 3b 0a 20 20 62 6c 6f .argv[3]);. blo
36d0: 62 5f 7a 65 72 6f 28 26 6f 75 74 29 3b 0a 20 20 b_zero(&out);.
36e0: 74 65 78 74 5f 64 69 66 66 28 26 61 2c 20 26 62 text_diff(&a, &b
36f0: 2c 20 26 6f 75 74 2c 20 33 29 3b 0a 20 20 62 6c , &out, 3);. bl
3700: 6f 62 5f 77 72 69 74 65 5f 74 6f 5f 66 69 6c 65 ob_write_to_file
3710: 28 26 6f 75 74 2c 20 22 2d 22 29 3b 0a 7d 0a (&out, "-");.}.