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 36 20 29 3b 0a 20 eof(R[0])*6 );.
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 7d 65 6c 73 65 7b 0a 20 20 20 20 0;. }else{.
2360: 2f 2a 20 52 65 75 73 65 20 4d 5b 5d 20 61 73 20 /* Reuse M[] as
2370: 66 6f 6c 6c 6f 77 73 3a 0a 20 20 20 20 2a 2a 0a follows:. **.
2380: 20 20 20 20 2a 2a 20 20 20 20 20 4d 5b 64 5d 5b ** M[d][
2390: 31 5d 20 3d 20 31 20 69 66 20 61 20 6c 69 6e 65 1] = 1 if a line
23a0: 20 69 73 20 69 6e 73 65 72 74 65 64 20 6f 72 20 is inserted or
23b0: 30 20 69 66 20 61 20 6c 69 6e 65 20 69 73 20 64 0 if a line is d
23c0: 65 6c 65 74 65 64 2e 0a 20 20 20 20 2a 2a 20 20 eleted.. **
23d0: 20 20 20 4d 5b 64 5d 5b 30 5d 20 3d 20 6e 75 6d M[d][0] = num
23e0: 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 63 6f 70 ber of lines cop
23f0: 69 65 64 20 61 66 74 65 72 20 74 68 65 20 69 6e ied after the in
2400: 73 20 6f 72 20 64 65 6c 20 61 62 6f 76 65 2e 0a s or del above..
2410: 20 20 20 20 2a 2a 0a 20 20 20 20 2a 2f 0a 20 20 **. */.
2420: 20 20 44 20 3d 20 64 20 2d 20 31 3b 0a 20 20 20 D = d - 1;.
2430: 20 4b 20 3d 20 58 20 2d 20 59 3b 0a 20 20 20 20 K = X - Y;.
2440: 66 6f 72 28 64 3d 44 2c 20 69 3d 28 4b 2b 44 29 for(d=D, i=(K+D)
2450: 2f 32 3b 20 64 3e 30 3b 20 64 2d 2d 29 7b 0a 20 /2; d>0; d--){.
2460: 20 20 20 20 20 44 45 42 55 47 28 20 70 72 69 6e DEBUG( prin
2470: 74 66 28 22 64 3d 25 64 20 69 3d 25 64 5c 6e 22 tf("d=%d i=%d\n"
2480: 2c 20 64 2c 20 69 29 3b 20 29 0a 20 20 20 20 20 , d, i); ).
2490: 20 69 66 28 20 69 3d 3d 64 20 7c 7c 20 28 69 3e if( i==d || (i>
24a0: 30 20 26 26 20 4d 5b 64 2d 31 5d 5b 69 2d 31 5d 0 && M[d-1][i-1]
24b0: 20 3e 20 4d 5b 64 2d 31 5d 5b 69 5d 29 20 29 7b > M[d-1][i]) ){
24c0: 0a 20 20 20 20 20 20 20 20 4d 5b 64 5d 5b 30 5d . M[d][0]
24d0: 20 3d 20 4d 5b 64 5d 5b 69 5d 20 2d 20 4d 5b 64 = M[d][i] - M[d
24e0: 2d 31 5d 5b 69 2d 31 5d 20 2d 20 31 3b 0a 20 20 -1][i-1] - 1;.
24f0: 20 20 20 20 20 20 4d 5b 64 5d 5b 31 5d 20 3d 20 M[d][1] =
2500: 30 3b 0a 20 20 20 20 20 20 20 20 69 2d 2d 3b 0a 0;. i--;.
2510: 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 }else{.
2520: 20 20 20 20 20 4d 5b 64 5d 5b 30 5d 20 3d 20 4d M[d][0] = M
2530: 5b 64 5d 5b 69 5d 20 2d 20 4d 5b 64 2d 31 5d 5b [d][i] - M[d-1][
2540: 69 5d 20 2d 20 31 3b 0a 20 20 20 20 20 20 20 20 i] - 1;.
2550: 4d 5b 64 5d 5b 31 5d 20 3d 20 31 3b 0a 20 20 20 M[d][1] = 1;.
2560: 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 0a }. }. .
2570: 20 20 20 20 44 45 42 55 47 28 0a 20 20 20 20 20 DEBUG(.
2580: 20 70 72 69 6e 74 66 28 22 2d 2d 2d 2d 2d 2d 2d printf("-------
2590: 2d 2d 2d 2d 2d 2d 2d 2d 5c 6e 4d 5b 30 5d 5b 30 --------\nM[0][0
25a0: 5d 20 3d 20 25 35 64 5c 6e 22 2c 20 4d 5b 30 5d ] = %5d\n", M[0]
25b0: 5b 30 5d 29 3b 0a 20 20 20 20 20 20 66 6f 72 28 [0]);. for(
25c0: 64 3d 31 3b 20 64 3c 3d 44 3b 20 64 2b 2b 29 7b d=1; d<=D; d++){
25d0: 0a 20 20 20 20 20 20 20 20 70 72 69 6e 74 66 28 . printf(
25e0: 22 4d 5b 25 64 5d 5b 30 5d 20 3d 20 25 35 64 20 "M[%d][0] = %5d
25f0: 20 20 20 4d 5b 25 64 5d 5b 31 5d 20 3d 20 25 64 M[%d][1] = %d
2600: 5c 6e 22 2c 64 2c 4d 5b 64 5d 5b 30 5d 2c 64 2c \n",d,M[d][0],d,
2610: 4d 5b 64 5d 5b 31 5d 29 3b 0a 20 20 20 20 20 20 M[d][1]);.
2620: 7d 0a 20 20 20 20 29 0a 20 20 20 20 0a 20 20 20 }. ). .
2630: 20 2f 2a 20 41 6c 6c 6f 63 61 74 65 20 74 68 65 /* Allocate the
2640: 20 6f 75 74 70 75 74 20 76 65 63 74 6f 72 0a 20 output vector.
2650: 20 20 20 2a 2f 0a 20 20 20 20 52 20 3d 20 6d 61 */. R = ma
2660: 6c 6c 6f 63 28 20 73 69 7a 65 6f 66 28 52 5b 30 lloc( sizeof(R[0
2670: 5d 29 2a 28 44 2b 32 29 2a 33 20 29 3b 0a 20 20 ])*(D+2)*3 );.
2680: 20 20 69 66 28 20 52 3d 3d 30 20 29 7b 0a 20 20 if( R==0 ){.
2690: 20 20 20 20 66 6f 73 73 69 6c 5f 66 61 74 61 6c fossil_fatal
26a0: 28 22 6f 75 74 20 6f 66 20 6d 65 6d 6f 72 79 22 ("out of memory"
26b0: 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 0a 20 20 );. }. .
26c0: 20 20 2f 2a 20 50 6f 70 75 6c 61 74 65 20 74 68 /* Populate th
26d0: 65 20 6f 75 74 70 75 74 20 76 65 63 74 6f 72 0a e output vector.
26e0: 20 20 20 20 2a 2f 0a 20 20 20 20 64 20 3d 20 72 */. d = r
26f0: 20 3d 20 30 3b 0a 20 20 20 20 77 68 69 6c 65 28 = 0;. while(
2700: 20 64 3c 3d 44 20 29 7b 0a 20 20 20 20 20 20 69 d<=D ){. i
2710: 6e 74 20 6e 3b 0a 20 20 20 20 20 20 52 5b 72 2b nt n;. R[r+
2720: 2b 5d 20 3d 20 4d 5b 64 2b 2b 5d 5b 30 5d 2f 32 +] = M[d++][0]/2
2730: 3b 20 20 20 2f 2a 20 43 4f 50 59 20 2a 2f 0a 20 ; /* COPY */.
2740: 20 20 20 20 20 69 66 28 20 64 3e 44 20 29 7b 0a if( d>D ){.
2750: 20 20 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d R[r++] =
2760: 20 30 3b 0a 20 20 20 20 20 20 20 20 52 5b 72 2b 0;. R[r+
2770: 2b 5d 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 +] = 0;.
2780: 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 break;. }.
2790: 20 20 20 20 20 69 66 28 20 4d 5b 64 5d 5b 31 5d if( M[d][1]
27a0: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 20 20 6e ==0 ){. n
27b0: 20 3d 20 31 3b 0a 20 20 20 20 20 20 20 20 77 68 = 1;. wh
27c0: 69 6c 65 28 20 4d 5b 64 5d 5b 30 5d 3d 3d 30 20 ile( M[d][0]==0
27d0: 26 26 20 64 3c 44 20 26 26 20 4d 5b 64 2b 31 5d && d<D && M[d+1]
27e0: 5b 31 5d 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 [1]==0 ){.
27f0: 20 20 20 20 64 2b 2b 3b 0a 20 20 20 20 20 20 20 d++;.
2800: 20 20 20 6e 2b 2b 3b 0a 20 20 20 20 20 20 20 20 n++;.
2810: 7d 0a 20 20 20 20 20 20 20 20 52 5b 72 2b 2b 5d }. R[r++]
2820: 20 3d 20 6e 3b 20 20 20 20 20 20 20 20 20 20 20 = n;
2830: 2f 2a 20 44 45 4c 45 54 45 20 2a 2f 0a 20 20 20 /* DELETE */.
2840: 20 20 20 20 20 69 66 28 20 64 3d 3d 44 20 7c 7c if( d==D ||
2850: 20 4d 5b 64 5d 5b 30 5d 3e 30 20 29 7b 0a 20 20 M[d][0]>0 ){.
2860: 20 20 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d R[r++] =
2870: 20 30 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 49 0; /* I
2880: 4e 53 45 52 54 20 2a 2f 0a 20 20 20 20 20 20 20 NSERT */.
2890: 20 20 20 63 6f 6e 74 69 6e 75 65 3b 0a 20 20 20 continue;.
28a0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 64 }. d
28b0: 2b 2b 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b ++;. }else{
28c0: 0a 20 20 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 . R[r++]
28d0: 3d 20 30 3b 20 20 20 20 20 20 20 20 20 20 20 2f = 0; /
28e0: 2a 20 44 45 4c 45 54 45 20 2a 2f 0a 20 20 20 20 * DELETE */.
28f0: 20 20 7d 0a 20 20 20 20 20 20 61 73 73 65 72 74 }. assert
2900: 28 20 4d 5b 64 5d 5b 31 5d 3d 3d 31 20 29 3b 0a ( M[d][1]==1 );.
2910: 20 20 20 20 20 20 6e 20 3d 20 31 3b 0a 20 20 20 n = 1;.
2920: 20 20 20 77 68 69 6c 65 28 20 4d 5b 64 5d 5b 30 while( M[d][0
2930: 5d 3d 3d 30 20 26 26 20 64 3c 44 20 26 26 20 4d ]==0 && d<D && M
2940: 5b 64 2b 31 5d 5b 31 5d 3d 3d 31 20 29 7b 0a 20 [d+1][1]==1 ){.
2950: 20 20 20 20 20 20 20 64 2b 2b 3b 0a 20 20 20 20 d++;.
2960: 20 20 20 20 6e 2b 2b 3b 0a 20 20 20 20 20 20 7d n++;. }
2970: 0a 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 . R[r++] =
2980: 6e 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a n; /*
2990: 20 49 4e 53 45 52 54 20 2a 2f 0a 20 20 20 20 7d INSERT */. }
29a0: 0a 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b . R[r++] = 0;
29b0: 0a 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b . R[r++] = 0;
29c0: 0a 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b . R[r++] = 0;
29d0: 0a 20 20 7d 0a 20 20 20 20 0a 20 20 2f 2a 20 46 . }. . /* F
29e0: 72 65 65 20 74 68 65 20 4d 79 65 72 73 20 6d 61 ree the Myers ma
29f0: 74 72 69 78 20 2a 2f 0a 20 20 66 6f 72 28 64 3d trix */. for(d=
2a00: 30 3b 20 64 3c 3d 44 3b 20 64 2b 2b 29 7b 0a 20 0; d<=D; d++){.
2a10: 20 20 20 66 72 65 65 28 4d 5b 64 5d 29 3b 0a 20 free(M[d]);.
2a20: 20 7d 0a 20 20 66 72 65 65 28 4d 29 3b 0a 0a 20 }. free(M);..
2a30: 20 2f 2a 20 49 66 20 70 4f 75 74 20 69 73 20 64 /* If pOut is d
2a40: 65 66 69 6e 65 64 2c 20 63 6f 6e 73 74 72 75 63 efined, construc
2a50: 74 20 61 20 75 6e 69 66 69 65 64 20 64 69 66 66 t a unified diff
2a60: 20 69 6e 74 6f 20 70 4f 75 74 20 61 6e 64 0a 20 into pOut and.
2a70: 20 2a 2a 20 64 65 6c 65 74 65 20 52 0a 20 20 2a ** delete R. *
2a80: 2f 0a 20 20 69 66 28 20 70 4f 75 74 20 29 7b 0a /. if( pOut ){.
2a90: 20 20 20 20 69 6e 74 20 61 20 3d 20 30 3b 20 20 int a = 0;
2aa0: 20 20 2f 2a 20 49 6e 64 65 78 20 6f 66 20 6e 65 /* Index of ne
2ab0: 78 74 20 6c 69 6e 65 20 69 6e 20 41 5b 5d 20 2a xt line in A[] *
2ac0: 2f 0a 20 20 20 20 69 6e 74 20 62 20 3d 20 30 3b /. int b = 0;
2ad0: 20 20 20 20 2f 2a 20 49 6e 64 65 78 20 6f 66 20 /* Index of
2ae0: 6e 65 78 74 20 6c 69 6e 65 20 69 6e 20 42 5b 5d next line in B[]
2af0: 20 2a 2f 0a 20 20 20 20 69 6e 74 20 6e 72 3b 20 */. int nr;
2b00: 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 /* Number
2b10: 6f 66 20 43 4f 50 59 2f 44 45 4c 45 54 45 2f 49 of COPY/DELETE/I
2b20: 4e 53 45 52 54 20 74 72 69 70 6c 65 73 20 74 6f NSERT triples to
2b30: 20 70 72 6f 63 65 73 73 20 2a 2f 0a 20 20 20 20 process */.
2b40: 69 6e 74 20 6d 78 72 3b 20 20 20 20 20 20 2f 2a int mxr; /*
2b50: 20 4d 61 78 69 6d 75 6d 20 76 61 6c 75 65 20 66 Maximum value f
2b60: 6f 72 20 72 20 2a 2f 0a 20 20 20 20 69 6e 74 20 or r */. int
2b70: 6e 61 2c 20 6e 62 3b 20 20 20 2f 2a 20 4e 75 6d na, nb; /* Num
2b80: 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 73 68 6f ber of lines sho
2b90: 77 6e 20 66 72 6f 6d 20 41 20 61 6e 64 20 42 20 wn from A and B
2ba0: 2a 2f 0a 20 20 20 20 69 6e 74 20 69 2c 20 6a 3b */. int i, j;
2bb0: 20 20 20 20 20 2f 2a 20 4c 6f 6f 70 20 63 6f 75 /* Loop cou
2bc0: 6e 74 65 72 73 20 2a 2f 0a 20 20 20 20 69 6e 74 nters */. int
2bd0: 20 6d 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 m; /* Nu
2be0: 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 74 6f mber of lines to
2bf0: 20 6f 75 74 70 75 74 20 2a 2f 0a 20 20 20 20 69 output */. i
2c00: 6e 74 20 73 6b 69 70 3b 20 20 20 20 20 2f 2a 20 nt skip; /*
2c10: 4e 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 Number of lines
2c20: 74 6f 20 73 6b 69 70 20 2a 2f 0a 0a 20 20 20 20 to skip */..
2c30: 66 6f 72 28 6d 78 72 3d 30 3b 20 52 5b 6d 78 72 for(mxr=0; R[mxr
2c40: 2b 31 5d 20 7c 7c 20 52 5b 6d 78 72 2b 32 5d 20 +1] || R[mxr+2]
2c50: 7c 7c 20 52 5b 6d 78 72 2b 33 5d 3b 20 6d 78 72 || R[mxr+3]; mxr
2c60: 20 2b 3d 20 33 29 7b 7d 0a 20 20 20 20 66 6f 72 += 3){}. for
2c70: 28 72 3d 30 3b 20 72 3c 6d 78 72 3b 20 72 20 2b (r=0; r<mxr; r +
2c80: 3d 20 33 2a 6e 72 29 7b 0a 20 20 20 20 20 20 2f = 3*nr){. /
2c90: 2a 20 46 69 67 75 72 65 20 6f 75 74 20 68 6f 77 * Figure out how
2ca0: 20 6d 61 6e 79 20 74 72 69 70 6c 65 73 20 74 6f many triples to
2cb0: 20 73 68 6f 77 20 69 6e 20 61 20 73 69 6e 67 6c show in a singl
2cc0: 65 20 62 6c 6f 63 6b 20 2a 2f 0a 20 20 20 20 20 e block */.
2cd0: 20 66 6f 72 28 6e 72 3d 31 3b 20 52 5b 72 2b 6e for(nr=1; R[r+n
2ce0: 72 2a 33 5d 3e 30 20 26 26 20 52 5b 72 2b 6e 72 r*3]>0 && R[r+nr
2cf0: 2a 33 5d 3c 6e 43 6f 6e 74 65 78 74 2a 32 3b 20 *3]<nContext*2;
2d00: 6e 72 2b 2b 29 7b 7d 0a 20 20 20 20 20 20 44 45 nr++){}. DE
2d10: 42 55 47 28 20 70 72 69 6e 74 66 28 22 72 3d 25 BUG( printf("r=%
2d20: 64 20 6e 72 3d 25 64 5c 6e 22 2c 20 72 2c 20 6e d nr=%d\n", r, n
2d30: 72 29 3b 20 29 0a 0a 20 20 20 20 20 20 2f 2a 20 r); ).. /*
2d40: 46 6f 72 20 74 68 65 20 63 75 72 72 65 6e 74 20 For the current
2d50: 62 6c 6f 63 6b 20 63 6f 6d 70 72 69 73 69 6e 67 block comprising
2d60: 20 6e 72 20 74 72 69 70 6c 65 73 2c 20 66 69 67 nr triples, fig
2d70: 75 72 65 20 6f 75 74 0a 20 20 20 20 20 20 2a 2a ure out. **
2d80: 20 68 6f 77 20 6d 61 6e 79 20 6c 69 6e 65 73 20 how many lines
2d90: 6f 66 20 41 20 61 6e 64 20 42 20 61 72 65 20 74 of A and B are t
2da0: 6f 20 62 65 20 64 69 73 70 6c 61 79 65 64 0a 20 o be displayed.
2db0: 20 20 20 20 20 2a 2f 0a 20 20 20 20 20 20 69 66 */. if
2dc0: 28 20 52 5b 72 5d 3e 6e 43 6f 6e 74 65 78 74 20 ( R[r]>nContext
2dd0: 29 7b 0a 20 20 20 20 20 20 20 20 6e 61 20 3d 20 ){. na =
2de0: 6e 62 20 3d 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 nb = nContext;.
2df0: 20 20 20 20 20 20 20 73 6b 69 70 20 3d 20 52 5b skip = R[
2e00: 72 5d 20 2d 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 r] - nContext;.
2e10: 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 }else{.
2e20: 20 20 20 20 6e 61 20 3d 20 6e 62 20 3d 20 52 5b na = nb = R[
2e30: 72 5d 3b 0a 20 20 20 20 20 20 20 20 73 6b 69 70 r];. skip
2e40: 20 3d 20 30 3b 0a 20 20 20 20 20 20 7d 0a 20 20 = 0;. }.
2e50: 20 20 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 6e for(i=0; i<n
2e60: 72 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 20 r; i++){.
2e70: 20 6e 61 20 2b 3d 20 52 5b 72 2b 69 2a 33 2b 31 na += R[r+i*3+1
2e80: 5d 3b 0a 20 20 20 20 20 20 20 20 6e 62 20 2b 3d ];. nb +=
2e90: 20 52 5b 72 2b 69 2a 33 2b 32 5d 3b 0a 20 20 20 R[r+i*3+2];.
2ea0: 20 20 20 7d 0a 20 20 20 20 20 20 69 66 28 20 52 }. if( R
2eb0: 5b 72 2b 6e 72 2a 33 5d 3e 6e 43 6f 6e 74 65 78 [r+nr*3]>nContex
2ec0: 74 20 29 7b 0a 20 20 20 20 20 20 20 20 6e 61 20 t ){. na
2ed0: 2b 3d 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 20 20 += nContext;.
2ee0: 20 20 20 20 20 6e 62 20 2b 3d 20 6e 43 6f 6e 74 nb += nCont
2ef0: 65 78 74 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 ext;. }else
2f00: 7b 0a 20 20 20 20 20 20 20 20 6e 61 20 2b 3d 20 {. na +=
2f10: 52 5b 72 2b 6e 72 2a 33 5d 3b 0a 20 20 20 20 20 R[r+nr*3];.
2f20: 20 20 20 6e 62 20 2b 3d 20 52 5b 72 2b 6e 72 2a nb += R[r+nr*
2f30: 33 5d 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 3];. }.
2f40: 20 20 66 6f 72 28 69 3d 31 3b 20 69 3c 6e 72 3b for(i=1; i<nr;
2f50: 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 6e i++){. n
2f60: 61 20 2b 3d 20 52 5b 72 2b 69 2a 33 5d 3b 0a 20 a += R[r+i*3];.
2f70: 20 20 20 20 20 20 20 6e 62 20 2b 3d 20 52 5b 72 nb += R[r
2f80: 2b 69 2a 33 5d 3b 0a 20 20 20 20 20 20 7d 0a 20 +i*3];. }.
2f90: 20 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 6e 64 blob_append
2fa0: 66 28 70 4f 75 74 2c 22 40 40 20 2d 25 64 2c 25 f(pOut,"@@ -%d,%
2fb0: 64 20 2b 25 64 2c 25 64 20 40 40 5c 6e 22 2c 20 d +%d,%d @@\n",
2fc0: 61 2b 73 6b 69 70 2b 31 2c 20 6e 61 2c 20 62 2b a+skip+1, na, b+
2fd0: 73 6b 69 70 2b 31 2c 20 6e 62 29 3b 0a 0a 20 20 skip+1, nb);..
2fe0: 20 20 20 20 2f 2a 20 53 68 6f 77 20 74 68 65 20 /* Show the
2ff0: 69 6e 69 74 69 61 6c 20 63 6f 6d 6d 6f 6e 20 61 initial common a
3000: 72 65 61 20 2a 2f 0a 20 20 20 20 20 20 61 20 2b rea */. a +
3010: 3d 20 73 6b 69 70 3b 0a 20 20 20 20 20 20 62 20 = skip;. b
3020: 2b 3d 20 73 6b 69 70 3b 0a 20 20 20 20 20 20 6d += skip;. m
3030: 20 3d 20 52 5b 72 5d 20 2d 20 73 6b 69 70 3b 0a = R[r] - skip;.
3040: 20 20 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a for(j=0; j
3050: 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 <m; j++){.
3060: 20 20 61 70 70 65 6e 64 44 69 66 66 4c 69 6e 65 appendDiffLine
3070: 28 70 4f 75 74 2c 20 22 20 22 2c 20 26 41 5b 61 (pOut, " ", &A[a
3080: 2b 6a 5d 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 +j]);. }.
3090: 20 20 20 20 61 20 2b 3d 20 6d 3b 0a 20 20 20 20 a += m;.
30a0: 20 20 62 20 2b 3d 20 6d 3b 0a 0a 20 20 20 20 20 b += m;..
30b0: 20 2f 2a 20 53 68 6f 77 20 74 68 65 20 64 69 66 /* Show the dif
30c0: 66 65 72 65 6e 63 65 73 20 2a 2f 0a 20 20 20 20 ferences */.
30d0: 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 6e 72 3b for(i=0; i<nr;
30e0: 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 6d i++){. m
30f0: 20 3d 20 52 5b 72 2b 69 2a 33 2b 31 5d 3b 0a 20 = R[r+i*3+1];.
3100: 20 20 20 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 for(j=0;
3110: 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 j<m; j++){.
3120: 20 20 20 20 20 61 70 70 65 6e 64 44 69 66 66 4c appendDiffL
3130: 69 6e 65 28 70 4f 75 74 2c 20 22 2d 22 2c 20 26 ine(pOut, "-", &
3140: 41 5b 61 2b 6a 5d 29 3b 0a 20 20 20 20 20 20 20 A[a+j]);.
3150: 20 7d 0a 20 20 20 20 20 20 20 20 61 20 2b 3d 20 }. a +=
3160: 6d 3b 0a 20 20 20 20 20 20 20 20 6d 20 3d 20 52 m;. m = R
3170: 5b 72 2b 69 2a 33 2b 32 5d 3b 0a 20 20 20 20 20 [r+i*3+2];.
3180: 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c 6d 3b for(j=0; j<m;
3190: 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 20 j++){.
31a0: 20 61 70 70 65 6e 64 44 69 66 66 4c 69 6e 65 28 appendDiffLine(
31b0: 70 4f 75 74 2c 20 22 2b 22 2c 20 26 42 5b 62 2b pOut, "+", &B[b+
31c0: 6a 5d 29 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 j]);. }.
31d0: 20 20 20 20 20 20 20 62 20 2b 3d 20 6d 3b 0a 20 b += m;.
31e0: 20 20 20 20 20 20 20 69 66 28 20 69 3c 6e 72 2d if( i<nr-
31f0: 31 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 6d 1 ){. m
3200: 20 3d 20 52 5b 72 2b 69 2a 33 2b 33 5d 3b 0a 20 = R[r+i*3+3];.
3210: 20 20 20 20 20 20 20 20 20 66 6f 72 28 6a 3d 30 for(j=0
3220: 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 ; j<m; j++){.
3230: 20 20 20 20 20 20 20 20 20 61 70 70 65 6e 64 44 appendD
3240: 69 66 66 4c 69 6e 65 28 70 4f 75 74 2c 20 22 20 iffLine(pOut, "
3250: 22 2c 20 26 42 5b 62 2b 6a 5d 29 3b 0a 20 20 20 ", &B[b+j]);.
3260: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 }.
3270: 20 20 20 62 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 b += m;.
3280: 20 20 20 20 20 61 20 2b 3d 20 6d 3b 0a 20 20 20 a += m;.
3290: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 7d 0a 0a }. }..
32a0: 20 20 20 20 20 20 2f 2a 20 53 68 6f 77 20 74 68 /* Show th
32b0: 65 20 66 69 6e 61 6c 20 63 6f 6d 6d 6f 6e 20 61 e final common a
32c0: 72 65 61 20 2a 2f 0a 20 20 20 20 20 20 61 73 73 rea */. ass
32d0: 65 72 74 28 20 6e 72 3d 3d 69 20 29 3b 0a 20 20 ert( nr==i );.
32e0: 20 20 20 20 6d 20 3d 20 52 5b 72 2b 6e 72 2a 33 m = R[r+nr*3
32f0: 5d 3b 0a 20 20 20 20 20 20 69 66 28 20 6d 3e 6e ];. if( m>n
3300: 43 6f 6e 74 65 78 74 20 29 20 6d 20 3d 20 6e 43 Context ) m = nC
3310: 6f 6e 74 65 78 74 3b 0a 20 20 20 20 20 20 66 6f ontext;. fo
3320: 72 28 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 r(j=0; j<m; j++)
3330: 7b 0a 20 20 20 20 20 20 20 20 61 70 70 65 6e 64 {. append
3340: 44 69 66 66 4c 69 6e 65 28 70 4f 75 74 2c 20 22 DiffLine(pOut, "
3350: 20 22 2c 20 26 42 5b 62 2b 6a 5d 29 3b 0a 20 20 ", &B[b+j]);.
3360: 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 }. }.
3370: 66 72 65 65 28 52 29 3b 0a 20 20 20 20 52 20 3d free(R);. R =
3380: 20 30 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 57 65 0;. }.. /* We
3390: 20 6e 6f 20 6c 6f 6e 67 65 72 20 6e 65 65 64 20 no longer need
33a0: 74 68 65 20 41 5b 5d 20 61 6e 64 20 42 5b 5d 20 the A[] and B[]
33b0: 76 65 63 74 6f 72 73 20 2a 2f 0a 20 20 66 72 65 vectors */. fre
33c0: 65 28 41 29 3b 0a 20 20 66 72 65 65 28 42 29 3b e(A);. free(B);
33d0: 0a 0a 20 20 2f 2a 20 52 65 74 75 72 6e 20 74 68 .. /* Return th
33e0: 65 20 72 65 73 75 6c 74 20 2a 2f 0a 20 20 72 65 e result */. re
33f0: 74 75 72 6e 20 52 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a turn R;.}../*.**
3400: 20 43 4f 4d 4d 41 4e 44 3a 20 74 65 73 74 2d 72 COMMAND: test-r
3410: 61 77 64 69 66 66 0a 2a 2f 0a 76 6f 69 64 20 74 awdiff.*/.void t
3420: 65 73 74 5f 72 61 77 64 69 66 66 5f 63 6d 64 28 est_rawdiff_cmd(
3430: 76 6f 69 64 29 7b 0a 20 20 42 6c 6f 62 20 61 2c void){. Blob a,
3440: 20 62 3b 0a 20 20 69 6e 74 20 72 3b 0a 20 20 69 b;. int r;. i
3450: 6e 74 20 69 3b 0a 20 20 69 6e 74 20 2a 52 3b 0a nt i;. int *R;.
3460: 20 20 69 66 28 20 67 2e 61 72 67 63 3c 34 20 29 if( g.argc<4 )
3470: 20 75 73 61 67 65 28 22 46 49 4c 45 31 20 46 49 usage("FILE1 FI
3480: 4c 45 32 20 2e 2e 2e 22 29 3b 0a 20 20 62 6c 6f LE2 ...");. blo
3490: 62 5f 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 b_read_from_file
34a0: 28 26 61 2c 20 67 2e 61 72 67 76 5b 32 5d 29 3b (&a, g.argv[2]);
34b0: 0a 20 20 66 6f 72 28 69 3d 33 3b 20 69 3c 67 2e . for(i=3; i<g.
34c0: 61 72 67 63 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 argc; i++){.
34d0: 69 66 28 20 69 3e 33 20 29 20 70 72 69 6e 74 66 if( i>3 ) printf
34e0: 28 22 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ("--------------
34f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3500: 2d 5c 6e 22 29 3b 0a 20 20 20 20 62 6c 6f 62 5f -\n");. blob_
3510: 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 read_from_file(&
3520: 62 2c 20 67 2e 61 72 67 76 5b 69 5d 29 3b 0a 20 b, g.argv[i]);.
3530: 20 20 20 52 20 3d 20 74 65 78 74 5f 64 69 66 66 R = text_diff
3540: 28 26 61 2c 20 26 62 2c 20 30 2c 20 30 29 3b 0a (&a, &b, 0, 0);.
3550: 20 20 20 20 66 6f 72 28 72 3d 30 3b 20 52 5b 72 for(r=0; R[r
3560: 5d 20 7c 7c 20 52 5b 72 2b 31 5d 20 7c 7c 20 52 ] || R[r+1] || R
3570: 5b 72 2b 32 5d 3b 20 72 20 2b 3d 20 33 29 7b 0a [r+2]; r += 3){.
3580: 20 20 20 20 20 20 70 72 69 6e 74 66 28 22 20 63 printf(" c
3590: 6f 70 79 20 25 34 64 20 20 64 65 6c 65 74 65 20 opy %4d delete
35a0: 25 34 64 20 20 69 6e 73 65 72 74 20 25 34 64 5c %4d insert %4d\
35b0: 6e 22 2c 20 52 5b 72 5d 2c 20 52 5b 72 2b 31 5d n", R[r], R[r+1]
35c0: 2c 20 52 5b 72 2b 32 5d 29 3b 0a 20 20 20 20 7d , R[r+2]);. }
35d0: 0a 20 20 20 20 2f 2a 20 66 72 65 65 28 52 29 3b . /* free(R);
35e0: 20 2a 2f 0a 20 20 20 20 62 6c 6f 62 5f 72 65 73 */. blob_res
35f0: 65 74 28 26 62 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f et(&b);. }.}../
3600: 2a 0a 2a 2a 20 43 4f 4d 4d 41 4e 44 3a 20 74 65 *.** COMMAND: te
3610: 73 74 2d 75 64 69 66 66 0a 2a 2f 0a 76 6f 69 64 st-udiff.*/.void
3620: 20 74 65 73 74 5f 75 64 69 66 66 5f 63 6d 64 28 test_udiff_cmd(
3630: 76 6f 69 64 29 7b 0a 20 20 42 6c 6f 62 20 61 2c void){. Blob a,
3640: 20 62 2c 20 6f 75 74 3b 0a 20 20 69 66 28 20 67 b, out;. if( g
3650: 2e 61 72 67 63 21 3d 34 20 29 20 75 73 61 67 65 .argc!=4 ) usage
3660: 28 22 46 49 4c 45 31 20 46 49 4c 45 32 22 29 3b ("FILE1 FILE2");
3670: 0a 20 20 62 6c 6f 62 5f 72 65 61 64 5f 66 72 6f . blob_read_fro
3680: 6d 5f 66 69 6c 65 28 26 61 2c 20 67 2e 61 72 67 m_file(&a, g.arg
3690: 76 5b 32 5d 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 v[2]);. blob_re
36a0: 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 62 2c ad_from_file(&b,
36b0: 20 67 2e 61 72 67 76 5b 33 5d 29 3b 0a 20 20 62 g.argv[3]);. b
36c0: 6c 6f 62 5f 7a 65 72 6f 28 26 6f 75 74 29 3b 0a lob_zero(&out);.
36d0: 20 20 74 65 78 74 5f 64 69 66 66 28 26 61 2c 20 text_diff(&a,
36e0: 26 62 2c 20 26 6f 75 74 2c 20 33 29 3b 0a 20 20 &b, &out, 3);.
36f0: 62 6c 6f 62 5f 77 72 69 74 65 5f 74 6f 5f 66 69 blob_write_to_fi
3700: 6c 65 28 26 6f 75 74 2c 20 22 2d 22 29 3b 0a 7d le(&out, "-");.}
3710: 0a .