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 47 65 6e 65 72 61 74 65 20 61 20 72 65 70 6f Generate a repo
0b00: 72 74 20 6f 66 20 74 68 65 20 64 69 66 66 65 72 rt of the differ
0b10: 65 6e 63 65 73 20 62 65 74 77 65 65 6e 20 66 69 ences between fi
0b20: 6c 65 73 20 70 41 20 61 6e 64 20 70 42 2e 0a 2a les pA and pB..*
0b30: 2a 20 49 66 20 70 4f 75 74 20 69 73 20 6e 6f 74 * If pOut is not
0b40: 20 4e 55 4c 4c 20 74 68 65 6e 20 61 20 75 6e 69 NULL then a uni
0b50: 66 69 65 64 20 64 69 66 66 20 69 73 20 61 70 70 fied diff is app
0b60: 65 6e 64 65 64 20 74 68 65 72 65 2e 20 20 49 74 ended there. It
0b70: 0a 2a 2a 20 69 73 20 61 73 73 75 6d 65 64 20 74 .** is assumed t
0b80: 68 61 74 20 70 4f 75 74 20 68 61 73 20 61 6c 72 hat pOut has alr
0b90: 65 61 64 79 20 62 65 65 6e 20 69 6e 69 74 69 61 eady been initia
0ba0: 6c 69 7a 65 64 2e 20 20 49 66 20 70 4f 75 74 20 lized. If pOut
0bb0: 69 73 0a 2a 2a 20 4e 55 4c 4c 2c 20 74 68 65 6e is.** NULL, then
0bc0: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 6e a pointer to an
0bd0: 20 61 72 72 61 79 20 6f 66 20 69 6e 74 65 67 65 array of intege
0be0: 72 73 20 69 73 20 72 65 74 75 72 6e 65 64 2e 20 rs is returned.
0bf0: 20 0a 2a 2a 20 54 68 65 20 69 6e 74 65 67 65 72 .** The integer
0c00: 73 20 63 6f 6d 65 20 69 6e 20 74 72 69 70 6c 65 s come in triple
0c10: 73 2e 20 20 46 6f 72 20 65 61 63 68 20 74 72 69 s. For each tri
0c20: 70 6c 65 2c 0a 2a 2a 20 74 68 65 20 65 6c 65 6d ple,.** the elem
0c30: 65 6e 74 73 20 61 72 65 20 74 68 65 20 6e 75 6d ents are the num
0c40: 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 63 6f 70 ber of lines cop
0c50: 69 65 64 2c 20 74 68 65 20 6e 75 6d 62 65 72 20 ied, the number
0c60: 6f 66 0a 2a 2a 20 6c 69 6e 65 73 20 64 65 6c 65 of.** lines dele
0c70: 74 65 64 2c 20 61 6e 64 20 74 68 65 20 6e 75 6d ted, and the num
0c80: 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 69 6e 73 ber of lines ins
0c90: 65 72 74 65 64 2e 20 20 54 68 65 20 76 65 63 74 erted. The vect
0ca0: 6f 72 0a 2a 2a 20 69 73 20 74 65 72 6d 69 6e 61 or.** is termina
0cb0: 74 65 64 20 62 79 20 61 20 74 72 69 70 6c 65 20 ted by a triple
0cc0: 6f 66 20 61 6c 6c 20 7a 65 72 6f 73 2e 0a 2a 2a of all zeros..**
0cd0: 0a 2a 2a 20 54 68 69 73 20 64 69 66 66 20 75 74 .** This diff ut
0ce0: 69 6c 69 74 79 20 64 6f 65 73 20 6e 6f 74 20 77 ility does not w
0cf0: 6f 72 6b 20 6f 6e 20 62 69 6e 61 72 79 20 66 69 ork on binary fi
0d00: 6c 65 73 2e 20 20 49 66 20 61 20 62 69 6e 61 72 les. If a binar
0d10: 79 0a 2a 2a 20 66 69 6c 65 20 69 73 20 65 6e 63 y.** file is enc
0d20: 6f 75 6e 74 65 72 65 64 2c 20 30 20 69 73 20 72 ountered, 0 is r
0d30: 65 74 75 72 6e 65 64 20 61 6e 64 20 70 4f 75 74 eturned and pOut
0d40: 20 69 73 20 77 72 69 74 74 65 6e 20 77 69 74 68 is written with
0d50: 0a 2a 2a 20 74 65 78 74 20 22 63 61 6e 6e 6f 74 .** text "cannot
0d60: 20 63 6f 6d 70 75 74 65 20 64 69 66 66 65 72 65 compute differe
0d70: 6e 63 65 20 62 65 74 77 65 65 6e 20 62 69 6e 61 nce between bina
0d80: 72 79 20 66 69 6c 65 73 22 2e 0a 2a 2a 0a 2a 2a ry files"..**.**
0d90: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0da0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0db0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0dc0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0dd0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 0a 2a 2a 0a 2a 2a **********.**.**
0de0: 20 54 68 65 20 63 6f 72 65 20 61 6c 67 6f 72 69 The core algori
0df0: 74 68 6d 20 69 73 20 61 20 76 61 72 69 61 74 69 thm is a variati
0e00: 6f 6e 20 6f 6e 20 74 68 65 20 63 6c 61 73 73 69 on on the classi
0e10: 63 20 57 61 67 6e 65 72 0a 2a 2a 20 6d 69 6e 69 c Wagner.** mini
0e20: 6d 75 6d 20 65 64 69 74 20 64 69 73 74 61 6e 63 mum edit distanc
0e30: 65 20 77 69 74 68 20 65 6e 68 61 6e 63 65 6d 65 e with enhanceme
0e40: 6e 74 73 20 74 6f 20 72 65 64 75 63 65 20 74 68 nts to reduce th
0e50: 65 20 72 75 6e 74 69 6d 65 0a 2a 2a 20 74 6f 20 e runtime.** to
0e60: 62 65 20 61 6c 6d 6f 73 74 20 6c 69 6e 65 61 72 be almost linear
0e70: 20 69 6e 20 74 68 65 20 63 6f 6d 6d 6f 6e 20 63 in the common c
0e80: 61 73 65 20 77 68 65 72 65 20 74 68 65 20 74 77 ase where the tw
0e90: 6f 20 66 69 6c 65 73 0a 2a 2a 20 68 61 76 65 20 o files.** have
0ea0: 61 20 6c 6f 74 20 69 6e 20 63 6f 6d 6d 6f 6e 2e a lot in common.
0eb0: 20 20 46 6f 72 20 61 64 64 69 74 69 6f 6e 61 6c For additional
0ec0: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 73 65 65 information see
0ed0: 0a 2a 2a 20 45 75 67 65 6e 65 20 57 2e 20 4d 79 .** Eugene W. My
0ee0: 65 72 73 2c 20 22 41 6e 20 4f 28 4e 44 29 20 44 ers, "An O(ND) D
0ef0: 69 66 66 65 72 65 6e 63 65 20 41 6c 67 6f 72 69 ifference Algori
0f00: 74 68 6d 20 41 6e 64 20 49 74 73 0a 2a 2a 20 56 thm And Its.** V
0f10: 61 72 69 61 74 69 6f 6e 73 22 0a 2a 2a 0a 2a 2a ariations".**.**
0f20: 20 43 6f 6e 73 69 64 65 72 20 63 6f 6d 70 61 72 Consider compar
0f30: 69 6e 67 20 73 74 72 69 6e 67 73 20 41 20 61 6e ing strings A an
0f40: 64 20 42 2e 20 20 41 3d 61 62 63 61 62 62 61 20 d B. A=abcabba
0f50: 61 6e 64 20 42 3d 63 62 61 62 61 63 0a 2a 2a 20 and B=cbabac.**
0f60: 57 65 20 63 6f 6e 73 74 72 75 63 74 20 61 20 22 We construct a "
0f70: 57 61 67 6e 65 72 22 20 6d 61 74 72 69 78 20 57 Wagner" matrix W
0f80: 20 77 69 74 68 20 41 20 61 6c 6f 6e 67 20 74 68 with A along th
0f90: 65 20 58 20 61 78 69 73 20 61 6e 64 20 0a 2a 2a e X axis and .**
0fa0: 20 42 20 61 6c 6f 6e 67 20 74 68 65 20 59 20 61 B along the Y a
0fb0: 78 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20 63 xis:.**.** c
0fc0: 20 36 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6
0fd0: 20 2a 0a 2a 2a 20 20 20 20 20 61 20 35 20 20 20 *.** a 5
0fe0: 20 20 20 20 20 20 20 20 20 20 20 20 2a 0a 2a 2a *.**
0ff0: 20 20 20 20 20 62 20 34 20 20 20 20 20 20 20 20 b 4
1000: 20 20 20 2a 20 2a 0a 2a 2a 20 20 20 20 20 61 20 * *.** a
1010: 33 20 20 20 20 20 20 20 20 20 2a 0a 2a 2a 20 20 3 *.**
1020: 20 20 20 62 20 32 20 20 20 20 20 20 20 2a 0a 2a b 2 *.*
1030: 2a 20 20 20 42 20 63 20 31 20 20 20 20 20 20 20 * B c 1
1040: 2a 0a 2a 2a 20 20 20 20 20 20 20 30 20 2a 20 2a *.** 0 * *
1050: 20 2a 20 0a 2a 2a 20 20 20 20 20 20 20 20 20 30 * .** 0
1060: 20 31 20 32 20 33 20 34 20 35 20 36 20 37 0a 2a 1 2 3 4 5 6 7.*
1070: 2a 20 20 20 20 20 20 20 20 20 20 20 61 20 62 20 * a b
1080: 63 20 61 20 62 20 62 20 61 0a 2a 2a 20 20 20 20 c a b b a.**
1090: 20 20 20 20 20 20 20 41 0a 2a 2a 0a 2a 2a 20 28 A.**.** (
10a0: 4e 6f 74 65 3a 20 77 65 20 64 72 61 77 20 74 68 Note: we draw th
10b0: 69 73 20 57 61 67 6e 65 72 20 6d 61 74 72 69 78 is Wagner matrix
10c0: 20 77 69 74 68 20 74 68 65 20 6f 72 69 67 69 6e with the origin
10d0: 20 61 74 20 74 68 65 20 6c 6f 77 65 72 20 0a 2a at the lower .*
10e0: 2a 20 6c 65 66 74 20 77 68 65 72 65 61 73 20 4d * left whereas M
10f0: 79 65 72 73 20 75 73 65 73 20 74 68 65 20 6f 72 yers uses the or
1100: 69 67 69 6e 20 61 74 20 74 68 65 20 75 70 70 65 igin at the uppe
1110: 72 20 6c 65 66 74 2e 20 20 4f 74 68 65 72 77 69 r left. Otherwi
1120: 73 65 2c 0a 2a 2a 20 74 68 65 79 20 61 72 65 20 se,.** they are
1130: 74 68 65 20 73 61 6d 65 2e 29 0a 2a 2a 0a 2a 2a the same.).**.**
1140: 20 4c 65 74 20 59 20 62 65 20 74 68 65 20 6d 61 Let Y be the ma
1150: 78 69 6d 75 6d 20 79 20 76 61 6c 75 65 20 6f 72 ximum y value or
1160: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 63 the number of c
1170: 68 61 72 61 63 74 65 72 73 20 69 6e 20 42 2e 0a haracters in B..
1180: 2a 2a 20 36 20 69 6e 20 74 68 69 73 20 65 78 61 ** 6 in this exa
1190: 6d 70 6c 65 2e 20 20 58 20 69 73 20 74 68 65 20 mple. X is the
11a0: 6d 61 78 69 6d 75 6d 20 78 20 76 61 6c 75 65 20 maximum x value
11b0: 6f 72 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 or the number of
11c0: 0a 2a 2a 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20 .** elements in
11d0: 41 2e 20 20 48 65 72 65 20 37 2e 0a 2a 2a 0a 2a A. Here 7..**.*
11e0: 2a 20 4f 75 72 20 67 6f 61 6c 20 69 73 20 74 6f * Our goal is to
11f0: 20 66 69 6e 64 20 61 20 70 61 74 68 20 66 72 6f find a path fro
1200: 6d 20 28 30 2c 30 29 20 74 6f 20 28 58 2c 59 29 m (0,0) to (X,Y)
1210: 2e 20 20 54 68 65 20 70 61 74 68 20 63 61 6e 0a . The path can.
1220: 2a 2a 20 75 73 65 20 68 6f 72 69 7a 6f 6e 74 61 ** use horizonta
1230: 6c 2c 20 76 65 72 74 69 63 61 6c 2c 20 6f 72 20 l, vertical, or
1240: 64 69 61 67 6f 6e 61 6c 20 73 74 65 70 73 2e 20 diagonal steps.
1250: 20 41 20 64 69 61 67 6f 6e 61 6c 20 66 72 6f 6d A diagonal from
1260: 0a 2a 2a 20 28 78 2d 31 2c 79 2d 31 29 20 74 6f .** (x-1,y-1) to
1270: 20 28 78 2c 79 29 20 69 73 20 6f 6e 6c 79 20 61 (x,y) is only a
1280: 6c 6c 6f 77 65 64 20 69 66 20 41 5b 78 5d 3d 3d llowed if A[x]==
1290: 42 5b 79 5d 2e 20 20 41 20 76 65 72 74 69 63 61 B[y]. A vertica
12a0: 6c 0a 2a 2a 20 73 74 65 70 73 20 63 6f 72 72 65 l.** steps corre
12b0: 73 70 6f 6e 64 73 20 74 6f 20 61 6e 20 69 6e 73 sponds to an ins
12c0: 65 72 74 69 6f 6e 2e 20 20 41 20 68 6f 72 69 7a ertion. A horiz
12d0: 6f 6e 74 61 6c 20 73 74 65 70 20 63 6f 72 72 65 ontal step corre
12e0: 73 70 6f 6e 64 73 0a 2a 2a 20 74 6f 20 61 20 64 sponds.** to a d
12f0: 65 6c 65 74 69 6f 6e 2e 20 20 57 65 20 77 61 6e eletion. We wan
1300: 74 20 74 6f 20 66 69 6e 64 20 74 68 65 20 70 61 t to find the pa
1310: 74 68 20 77 69 74 68 20 74 68 65 20 66 65 77 65 th with the fewe
1320: 73 74 0a 2a 2a 20 68 6f 72 69 7a 6f 6e 74 61 6c st.** horizontal
1330: 20 61 6e 64 20 76 65 72 74 69 63 61 6c 20 73 74 and vertical st
1340: 65 70 73 2e 0a 2a 2a 0a 2a 2a 20 44 69 61 67 6f eps..**.** Diago
1350: 6e 61 6c 20 6b 20 63 6f 6e 73 69 73 74 73 20 6f nal k consists o
1360: 66 20 61 6c 6c 20 70 6f 69 6e 74 73 20 73 75 63 f all points suc
1370: 68 20 74 68 61 74 20 78 2d 79 3d 3d 6b 2e 20 20 h that x-y==k.
1380: 44 69 61 67 6f 6e 61 6c 0a 2a 2a 20 7a 65 72 6f Diagonal.** zero
1390: 20 62 65 67 69 6e 73 20 61 74 20 74 68 65 20 6f begins at the o
13a0: 72 69 67 69 6e 2e 20 20 44 69 61 67 6f 6e 61 6c rigin. Diagonal
13b0: 20 31 20 62 65 67 69 6e 73 20 61 74 20 28 31 2c 1 begins at (1,
13c0: 30 29 2e 20 20 0a 2a 2a 20 44 69 61 67 6f 6e 61 0). .** Diagona
13d0: 6c 20 2d 31 20 62 65 67 69 6e 73 20 61 74 20 28 l -1 begins at (
13e0: 30 2c 31 29 2e 20 20 41 6c 6c 20 64 69 61 67 6f 0,1). All diago
13f0: 6e 61 6c 73 20 6d 6f 76 65 20 75 70 20 61 6e 64 nals move up and
1400: 20 74 6f 20 74 68 65 0a 2a 2a 20 72 69 67 68 74 to the.** right
1410: 20 61 74 20 34 35 20 64 65 67 72 65 65 73 2e 20 at 45 degrees.
1420: 20 44 69 61 67 6f 6e 61 6c 20 6e 75 6d 62 65 72 Diagonal number
1430: 20 69 6e 63 72 65 61 73 65 20 66 72 6f 6d 20 75 increase from u
1440: 70 70 65 72 20 6c 65 66 74 0a 2a 2a 20 74 6f 20 pper left.** to
1450: 6c 6f 77 65 72 20 72 69 67 68 74 2e 0a 2a 2a 20 lower right..**
1460: 0a 2a 2a 20 4d 79 65 72 73 20 6d 61 74 72 69 78 .** Myers matrix
1470: 20 4d 20 69 73 20 61 20 6c 6f 77 65 72 20 72 69 M is a lower ri
1480: 67 68 74 20 74 72 69 61 6e 67 75 6c 61 72 20 6d ght triangular m
1490: 61 74 72 69 78 20 77 69 74 68 20 69 6e 64 69 63 atrix with indic
14a0: 65 73 20 64 0a 2a 2a 20 61 6c 6f 6e 67 20 74 68 es d.** along th
14b0: 65 20 62 6f 74 74 6f 6d 20 61 6e 64 20 69 20 76 e bottom and i v
14c0: 65 72 74 69 63 61 6c 6c 79 3a 0a 2a 2a 0a 2a 2a ertically:.**.**
14d0: 20 0a 2a 2a 20 20 20 69 3d 34 20 7c 20 20 20 20 .** i=4 |
14e0: 20 20 20 20 20 20 20 20 2b 34 20 20 5c 0a 2a 2a +4 \.**
14f0: 20 20 20 20 20 33 20 7c 20 20 20 20 20 20 20 20 3 |
1500: 20 2b 33 20 2b 32 20 20 20 7c 0a 2a 2a 20 20 20 +3 +2 |.**
1510: 20 20 32 20 7c 20 20 20 20 20 20 2b 32 20 2b 31 2 | +2 +1
1520: 20 20 30 20 20 20 7c 2d 20 6b 20 76 61 6c 75 65 0 |- k value
1530: 73 2e 20 20 20 6b 20 3d 20 32 2a 69 2d 64 0a 2a s. k = 2*i-d.*
1540: 2a 20 20 20 20 20 31 20 7c 20 20 20 2b 31 20 20 * 1 | +1
1550: 30 20 2d 31 20 2d 32 20 20 20 7c 0a 2a 2a 20 20 0 -1 -2 |.**
1560: 20 20 20 30 20 7c 20 30 20 2d 31 20 2d 32 20 2d 0 | 0 -1 -2 -
1570: 33 20 2d 34 20 20 2f 0a 2a 2a 20 20 20 20 20 20 3 -4 /.**
1580: 20 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ---------------
1590: 0a 2a 2a 20 20 20 20 20 20 20 20 20 30 20 20 31 .** 0 1
15a0: 20 20 32 20 20 33 20 20 34 20 3d 20 64 0a 2a 2a 2 3 4 = d.**
15b0: 0a 2a 2a 20 45 61 63 68 20 65 6c 65 6d 65 6e 74 .** Each element
15c0: 20 6f 66 20 74 68 65 20 4d 79 65 72 73 20 6d 61 of the Myers ma
15d0: 74 72 69 78 20 63 6f 72 72 65 73 70 6f 6e 64 73 trix corresponds
15e0: 20 74 6f 20 61 20 64 69 61 67 6f 6e 61 6c 2e 0a to a diagonal..
15f0: 2a 2a 20 54 68 65 20 64 69 61 67 6f 6e 61 6c 20 ** The diagonal
1600: 69 73 20 6b 3d 32 2a 69 2d 64 2e 20 20 54 68 65 is k=2*i-d. The
1610: 20 64 69 61 67 6f 6e 61 6c 20 76 61 6c 75 65 73 diagonal values
1620: 20 61 72 65 20 73 68 6f 77 6e 0a 2a 2a 20 69 6e are shown.** in
1630: 20 74 68 65 20 74 65 6d 70 6c 61 74 65 20 61 62 the template ab
1640: 6f 76 65 2e 0a 2a 2a 0a 2a 2a 20 45 61 63 68 20 ove..**.** Each
1650: 65 6e 74 72 79 20 69 6e 20 4d 20 72 65 70 72 65 entry in M repre
1660: 73 65 6e 74 73 20 74 68 65 20 65 6e 64 2d 70 6f sents the end-po
1670: 69 6e 74 20 6f 6e 20 61 20 70 61 74 68 20 66 72 int on a path fr
1680: 6f 6d 20 28 30 2c 30 29 2e 0a 2a 2a 20 54 68 65 om (0,0)..** The
1690: 20 65 6e 64 2d 70 6f 69 6e 74 20 69 73 20 6f 6e end-point is on
16a0: 20 64 69 61 67 6f 6e 61 6c 20 6b 2e 20 20 54 68 diagonal k. Th
16b0: 65 20 76 61 6c 75 65 20 73 74 6f 72 65 64 20 69 e value stored i
16c0: 6e 20 4d 20 69 73 0a 2a 2a 20 71 3d 78 2b 79 20 n M is.** q=x+y
16d0: 77 68 65 72 65 20 28 78 2c 79 29 20 69 73 20 74 where (x,y) is t
16e0: 68 65 20 74 65 72 6d 69 6e 75 73 20 6f 66 20 74 he terminus of t
16f0: 68 65 20 70 61 74 68 2e 20 20 41 20 70 61 74 68 he path. A path
1700: 0a 2a 2a 20 74 6f 20 4d 5b 64 5d 5b 69 5d 20 77 .** to M[d][i] w
1710: 69 6c 6c 20 63 6f 6d 65 20 74 68 72 6f 75 67 68 ill come through
1720: 20 65 69 74 68 65 72 20 4d 5b 64 2d 31 5d 5b 69 either M[d-1][i
1730: 2d 31 5d 20 6f 72 0a 2a 2a 20 74 68 6f 75 67 68 -1] or.** though
1740: 20 4d 5b 64 2d 31 5d 5b 69 5d 2c 20 77 68 69 63 M[d-1][i], whic
1750: 68 65 76 65 72 20 68 6f 6c 64 73 20 74 68 65 20 hever holds the
1760: 6c 61 72 67 65 73 74 20 76 61 6c 75 65 20 6f 66 largest value of
1770: 20 71 2e 0a 2a 2a 20 49 66 20 62 6f 74 68 20 65 q..** If both e
1780: 6c 65 6d 65 6e 74 73 20 68 6f 6c 64 20 74 68 65 lements hold the
1790: 20 73 61 6d 65 20 76 61 6c 75 65 2c 20 74 68 65 same value, the
17a0: 20 70 61 74 68 20 63 6f 6d 65 73 0a 2a 2a 20 74 path comes.** t
17b0: 68 72 6f 75 67 68 20 4d 5b 64 2d 31 5d 5b 69 2d hrough M[d-1][i-
17c0: 31 5d 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 76 61 1]..**.** The va
17d0: 6c 75 65 20 6f 66 20 64 20 69 73 20 74 68 65 20 lue of d is the
17e0: 6e 75 6d 62 65 72 20 6f 66 20 69 6e 73 65 72 74 number of insert
17f0: 69 6f 6e 73 20 61 6e 64 20 64 65 6c 65 74 69 6f ions and deletio
1800: 6e 73 0a 2a 2a 20 6d 61 64 65 20 73 6f 20 66 61 ns.** made so fa
1810: 72 20 6f 6e 20 74 68 65 20 70 61 74 68 2e 20 20 r on the path.
1820: 4d 20 67 72 6f 77 73 20 70 72 6f 67 72 65 73 73 M grows progress
1830: 69 76 65 6c 79 2e 20 20 53 6f 20 74 68 65 0a 2a ively. So the.*
1840: 2a 20 73 69 7a 65 20 6f 66 20 74 68 65 20 4d 20 * size of the M
1850: 6d 61 74 72 69 78 20 69 73 20 70 72 6f 70 6f 72 matrix is propor
1860: 74 69 6f 6e 61 6c 20 74 6f 20 64 2a 64 2e 20 20 tional to d*d.
1870: 46 6f 72 20 74 68 65 0a 2a 2a 20 63 6f 6d 6d 6f For the.** commo
1880: 6e 20 63 61 73 65 20 77 68 65 72 65 20 41 20 61 n case where A a
1890: 6e 64 20 42 20 61 72 65 20 73 69 6d 69 6c 61 72 nd B are similar
18a0: 2c 20 64 20 77 69 6c 6c 20 62 65 20 73 6d 61 6c , d will be smal
18b0: 6c 0a 2a 2a 20 63 6f 6d 70 61 72 65 64 20 74 6f l.** compared to
18c0: 20 58 20 61 6e 64 20 59 20 73 6f 20 6c 69 74 74 X and Y so litt
18d0: 6c 65 20 6d 65 6d 6f 72 79 20 69 73 20 72 65 71 le memory is req
18e0: 75 69 72 65 64 2e 20 20 54 68 65 0a 2a 2a 20 6f uired. The.** o
18f0: 72 69 67 69 6e 61 6c 20 57 61 67 6e 65 72 20 61 riginal Wagner a
1900: 6c 67 6f 72 69 74 68 6d 20 72 65 71 75 69 72 65 lgorithm require
1910: 73 20 58 2a 59 20 6d 65 6d 6f 72 79 2c 20 77 68 s X*Y memory, wh
1920: 69 63 68 20 66 6f 72 0a 2a 2a 20 6c 61 72 67 65 ich for.** large
1930: 72 20 66 69 6c 65 73 20 28 31 30 30 4b 20 6c 69 r files (100K li
1940: 6e 65 73 29 20 69 73 20 6d 6f 72 65 20 6d 65 6d nes) is more mem
1950: 6f 72 79 20 74 68 61 6e 20 77 65 20 68 61 76 65 ory than we have
1960: 20 61 74 0a 2a 2a 20 68 61 6e 64 2e 0a 2a 2f 0a at.** hand..*/.
1970: 69 6e 74 20 2a 74 65 78 74 5f 64 69 66 66 28 0a int *text_diff(.
1980: 20 20 42 6c 6f 62 20 2a 70 41 5f 42 6c 6f 62 2c Blob *pA_Blob,
1990: 20 20 20 2f 2a 20 46 52 4f 4d 20 66 69 6c 65 20 /* FROM file
19a0: 2a 2f 0a 20 20 42 6c 6f 62 20 2a 70 42 5f 42 6c */. Blob *pB_Bl
19b0: 6f 62 2c 20 20 20 2f 2a 20 54 4f 20 66 69 6c 65 ob, /* TO file
19c0: 20 2a 2f 0a 20 20 42 6c 6f 62 20 2a 70 4f 75 74 */. Blob *pOut
19d0: 2c 20 20 20 20 20 20 2f 2a 20 57 72 69 74 65 20 , /* Write
19e0: 75 6e 69 66 69 65 64 20 64 69 66 66 20 68 65 72 unified diff her
19f0: 65 20 69 66 20 6e 6f 74 20 4e 55 4c 4c 20 2a 2f e if not NULL */
1a00: 0a 20 20 69 6e 74 20 6e 43 6f 6e 74 65 78 74 20 . int nContext
1a10: 20 20 20 20 2f 2a 20 41 6d 6f 75 6e 74 20 6f 66 /* Amount of
1a20: 20 63 6f 6e 74 65 78 74 20 74 6f 20 75 6e 69 66 context to unif
1a30: 69 65 64 20 64 69 66 66 20 2a 2f 0a 29 7b 0a 20 ied diff */.){.
1a40: 20 44 4c 69 6e 65 20 2a 41 2c 20 2a 42 3b 20 20 DLine *A, *B;
1a50: 20 20 2f 2a 20 46 69 6c 65 73 20 62 65 69 6e 67 /* Files being
1a60: 20 63 6f 6d 70 61 72 65 64 20 2a 2f 0a 20 20 69 compared */. i
1a70: 6e 74 20 58 2c 20 59 3b 20 20 20 20 20 20 20 20 nt X, Y;
1a80: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65 6c 65 /* Number of ele
1a90: 6d 65 6e 74 73 20 69 6e 20 41 20 61 6e 64 20 42 ments in A and B
1aa0: 20 2a 2f 0a 20 20 69 6e 74 20 78 2c 20 79 3b 20 */. int x, y;
1ab0: 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 69 63 65 /* Indice
1ac0: 73 3a 20 20 41 5b 78 5d 20 61 6e 64 20 42 5b 79 s: A[x] and B[y
1ad0: 5d 20 2a 2f 0a 20 20 69 6e 74 20 73 7a 4d 20 3d ] */. int szM =
1ae0: 20 30 3b 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 0; /* Numbe
1af0: 72 20 6f 66 20 72 6f 77 73 20 61 6e 64 20 63 6f r of rows and co
1b00: 6c 75 6d 6e 73 20 69 6e 20 4d 20 2a 2f 0a 20 20 lumns in M */.
1b10: 69 6e 74 20 2a 2a 4d 20 3d 20 30 3b 20 20 20 20 int **M = 0;
1b20: 20 2f 2a 20 4d 79 65 72 73 20 6d 61 74 72 69 78 /* Myers matrix
1b30: 20 2a 2f 0a 20 20 69 6e 74 20 69 2c 20 64 3b 20 */. int i, d;
1b40: 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 69 63 65 /* Indice
1b50: 73 20 6f 6e 20 4d 2e 20 20 4d 5b 64 5d 5b 69 5d s on M. M[d][i]
1b60: 20 2a 2f 0a 20 20 69 6e 74 20 6b 2c 20 71 3b 20 */. int k, q;
1b70: 20 20 20 20 20 20 20 2f 2a 20 44 69 61 67 6f 6e /* Diagon
1b80: 61 6c 20 6e 75 6d 62 65 72 20 61 6e 64 20 64 69 al number and di
1b90: 73 74 69 6e 63 74 20 66 72 6f 6d 20 28 30 2c 30 stinct from (0,0
1ba0: 29 20 2a 2f 0a 20 20 69 6e 74 20 4b 2c 20 44 3b ) */. int K, D;
1bb0: 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 64 /* The d
1bc0: 69 61 67 6f 6e 61 6c 20 61 6e 64 20 64 20 66 6f iagonal and d fo
1bd0: 72 20 74 68 65 20 66 69 6e 61 6c 20 73 6f 6c 75 r the final solu
1be0: 74 69 6f 6e 20 2a 2f 20 20 20 20 20 20 20 20 20 tion */
1bf0: 20 0a 20 20 69 6e 74 20 2a 52 20 3d 20 30 3b 20 . int *R = 0;
1c00: 20 20 20 20 20 2f 2a 20 52 65 73 75 6c 74 20 76 /* Result v
1c10: 65 63 74 6f 72 20 2a 2f 0a 20 20 69 6e 74 20 72 ector */. int r
1c20: 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4c ; /* L
1c30: 6f 6f 70 20 76 61 72 69 61 62 6c 65 73 20 2a 2f oop variables */
1c40: 0a 20 20 69 6e 74 20 67 6f 20 3d 20 31 3b 20 20 . int go = 1;
1c50: 20 20 20 20 2f 2a 20 4f 75 74 65 72 20 6c 6f 6f /* Outer loo
1c60: 70 20 63 6f 6e 74 72 6f 6c 20 2a 2f 0a 20 20 69 p control */. i
1c70: 6e 74 20 4d 41 58 3b 20 20 20 20 20 20 20 20 20 nt MAX;
1c80: 2f 2a 20 4c 61 72 67 65 73 74 20 6f 66 20 58 20 /* Largest of X
1c90: 61 6e 64 20 59 20 2a 2f 0a 0a 20 20 2f 2a 20 42 and Y */.. /* B
1ca0: 72 65 61 6b 20 74 68 65 20 74 77 6f 20 66 69 6c reak the two fil
1cb0: 65 73 20 62 65 69 6e 67 20 64 69 66 66 65 64 20 es being diffed
1cc0: 69 6e 74 6f 20 69 6e 64 69 76 69 64 75 61 6c 20 into individual
1cd0: 6c 69 6e 65 73 2e 0a 20 20 2a 2a 20 43 6f 6d 70 lines.. ** Comp
1ce0: 75 74 65 20 68 61 73 68 65 73 20 6f 6e 20 65 61 ute hashes on ea
1cf0: 63 68 20 6c 69 6e 65 20 66 6f 72 20 66 61 73 74 ch line for fast
1d00: 20 63 6f 6d 70 61 72 69 73 6f 6e 2e 0a 20 20 2a comparison.. *
1d10: 2f 0a 20 20 41 20 3d 20 62 72 65 61 6b 5f 69 6e /. A = break_in
1d20: 74 6f 5f 6c 69 6e 65 73 28 62 6c 6f 62 5f 73 74 to_lines(blob_st
1d30: 72 28 70 41 5f 42 6c 6f 62 29 2c 20 26 58 29 3b r(pA_Blob), &X);
1d40: 0a 20 20 42 20 3d 20 62 72 65 61 6b 5f 69 6e 74 . B = break_int
1d50: 6f 5f 6c 69 6e 65 73 28 62 6c 6f 62 5f 73 74 72 o_lines(blob_str
1d60: 28 70 42 5f 42 6c 6f 62 29 2c 20 26 59 29 3b 0a (pB_Blob), &Y);.
1d70: 0a 20 20 69 66 28 20 41 3d 3d 30 20 7c 7c 20 42 . if( A==0 || B
1d80: 3d 3d 30 20 29 7b 0a 20 20 20 20 66 72 65 65 28 ==0 ){. free(
1d90: 41 29 3b 0a 20 20 20 20 66 72 65 65 28 42 29 3b A);. free(B);
1da0: 0a 20 20 20 20 69 66 28 20 70 4f 75 74 20 29 7b . if( pOut ){
1db0: 0a 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 . blob_appe
1dc0: 6e 64 66 28 70 4f 75 74 2c 20 22 63 61 6e 6e 6f ndf(pOut, "canno
1dd0: 74 20 63 6f 6d 70 75 74 65 20 64 69 66 66 65 72 t compute differ
1de0: 65 6e 63 65 20 62 65 74 77 65 65 6e 20 62 69 6e ence between bin
1df0: 61 72 79 20 66 69 6c 65 73 5c 6e 22 29 3b 0a 20 ary files\n");.
1e00: 20 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e 20 }. return
1e10: 30 3b 0a 20 20 7d 0a 0a 20 20 73 7a 4d 20 3d 20 0;. }.. szM =
1e20: 30 3b 0a 20 20 4d 41 58 20 3d 20 58 3e 59 20 3f 0;. MAX = X>Y ?
1e30: 20 58 20 3a 20 59 3b 0a 20 20 66 6f 72 28 64 3d X : Y;. for(d=
1e40: 30 3b 20 67 6f 20 26 26 20 64 3c 3d 4d 41 58 3b 0; go && d<=MAX;
1e50: 20 64 2b 2b 29 7b 0a 20 20 20 20 69 66 28 20 73 d++){. if( s
1e60: 7a 4d 3c 64 2b 31 20 29 7b 0a 20 20 20 20 20 20 zM<d+1 ){.
1e70: 73 7a 4d 20 2b 3d 20 73 7a 4d 20 2b 20 31 30 3b szM += szM + 10;
1e80: 0a 20 20 20 20 20 20 4d 20 3d 20 72 65 61 6c 6c . M = reall
1e90: 6f 63 28 4d 2c 20 73 69 7a 65 6f 66 28 4d 5b 30 oc(M, sizeof(M[0
1ea0: 5d 29 2a 73 7a 4d 29 3b 0a 20 20 20 20 20 20 69 ])*szM);. i
1eb0: 66 28 20 4d 3d 3d 30 20 29 7b 0a 20 20 20 20 20 f( M==0 ){.
1ec0: 20 20 20 66 6f 73 73 69 6c 5f 70 61 6e 69 63 28 fossil_panic(
1ed0: 22 6f 75 74 20 6f 66 20 6d 65 6d 6f 72 79 22 29 "out of memory")
1ee0: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a ;. }. }.
1ef0: 20 20 20 20 4d 5b 64 5d 20 3d 20 6d 61 6c 6c 6f M[d] = mallo
1f00: 63 28 20 73 69 7a 65 6f 66 28 4d 5b 64 5d 5b 30 c( sizeof(M[d][0
1f10: 5d 29 2a 28 64 2b 31 29 20 29 3b 0a 20 20 20 20 ])*(d+1) );.
1f20: 69 66 28 20 4d 5b 64 5d 3d 3d 30 20 29 7b 0a 20 if( M[d]==0 ){.
1f30: 20 20 20 20 20 66 6f 73 73 69 6c 5f 70 61 6e 69 fossil_pani
1f40: 63 28 22 6f 75 74 20 6f 66 20 6d 65 6d 6f 72 79 c("out of memory
1f50: 22 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 66 6f ");. }. fo
1f60: 72 28 69 3d 30 3b 20 69 3c 3d 64 3b 20 69 2b 2b r(i=0; i<=d; i++
1f70: 29 7b 0a 20 20 20 20 20 20 6b 20 3d 20 32 2a 69 ){. k = 2*i
1f80: 20 2d 20 64 3b 0a 20 20 20 20 20 20 69 66 28 20 - d;. if(
1f90: 64 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 20 20 d==0 ){.
1fa0: 71 20 3d 20 30 3b 0a 20 20 20 20 20 20 7d 65 6c q = 0;. }el
1fb0: 73 65 20 69 66 28 20 69 3d 3d 30 20 29 7b 0a 20 se if( i==0 ){.
1fc0: 20 20 20 20 20 20 20 71 20 3d 20 4d 5b 64 2d 31 q = M[d-1
1fd0: 5d 5b 30 5d 3b 0a 20 20 20 20 20 20 7d 65 6c 73 ][0];. }els
1fe0: 65 20 69 66 28 20 69 3c 64 2d 31 20 26 26 20 4d e if( i<d-1 && M
1ff0: 5b 64 2d 31 5d 5b 69 2d 31 5d 20 3c 20 4d 5b 64 [d-1][i-1] < M[d
2000: 2d 31 5d 5b 69 5d 20 29 7b 0a 20 20 20 20 20 20 -1][i] ){.
2010: 20 20 71 20 3d 20 4d 5b 64 2d 31 5d 5b 69 5d 3b q = M[d-1][i];
2020: 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 . }else{.
2030: 20 20 20 20 20 20 71 20 3d 20 4d 5b 64 2d 31 5d q = M[d-1]
2040: 5b 69 2d 31 5d 3b 0a 20 20 20 20 20 20 7d 0a 20 [i-1];. }.
2050: 20 20 20 20 20 78 20 3d 20 28 6b 20 2b 20 71 20 x = (k + q
2060: 2b 20 31 29 2f 32 3b 0a 20 20 20 20 20 20 79 20 + 1)/2;. y
2070: 3d 20 78 20 2d 20 6b 3b 0a 20 20 20 20 20 20 69 = x - k;. i
2080: 66 28 20 78 3c 30 20 7c 7c 20 78 3e 58 20 7c 7c f( x<0 || x>X ||
2090: 20 79 3c 30 20 7c 7c 20 79 3e 59 20 29 7b 0a 20 y<0 || y>Y ){.
20a0: 20 20 20 20 20 20 20 78 20 3d 20 79 20 3d 20 30 x = y = 0
20b0: 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 ;. }else{.
20c0: 20 20 20 20 20 20 20 77 68 69 6c 65 28 20 78 3c while( x<
20d0: 58 20 26 26 20 79 3c 59 20 26 26 20 73 61 6d 65 X && y<Y && same
20e0: 5f 64 6c 69 6e 65 28 26 41 5b 78 5d 2c 26 42 5b _dline(&A[x],&B[
20f0: 79 5d 29 20 29 7b 20 78 2b 2b 3b 20 79 2b 2b 3b y]) ){ x++; y++;
2100: 20 7d 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 }. }.
2110: 20 4d 5b 64 5d 5b 69 5d 20 3d 20 78 20 2b 20 79 M[d][i] = x + y
2120: 3b 0a 20 20 20 20 20 20 44 45 42 55 47 28 20 70 ;. DEBUG( p
2130: 72 69 6e 74 66 28 22 4d 5b 25 64 5d 5b 25 69 5d rintf("M[%d][%i]
2140: 20 3d 20 25 64 20 20 6b 3d 25 64 20 28 25 64 2c = %d k=%d (%d,
2150: 25 64 29 5c 6e 22 2c 20 64 2c 20 69 2c 20 78 2b %d)\n", d, i, x+
2160: 79 2c 20 6b 2c 20 78 2c 20 79 29 3b 20 29 0a 20 y, k, x, y); ).
2170: 20 20 20 20 20 69 66 28 20 78 3d 3d 58 20 26 26 if( x==X &&
2180: 20 79 3d 3d 59 20 29 7b 0a 20 20 20 20 20 20 20 y==Y ){.
2190: 20 67 6f 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 go = 0;.
21a0: 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 7d 0a break;. }.
21b0: 20 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20 }. }. if(
21c0: 64 3e 4d 41 58 20 29 7b 0a 20 20 20 20 52 20 3d d>MAX ){. R =
21d0: 20 6d 61 6c 6c 6f 63 28 20 73 69 7a 65 6f 66 28 malloc( sizeof(
21e0: 52 5b 30 5d 29 2a 36 20 29 3b 0a 20 20 20 20 52 R[0])*6 );. R
21f0: 5b 30 5d 20 3d 20 30 3b 0a 20 20 20 20 52 5b 31 [0] = 0;. R[1
2200: 5d 20 3d 20 58 3b 0a 20 20 20 20 52 5b 32 5d 20 ] = X;. R[2]
2210: 3d 20 59 3b 0a 20 20 20 20 52 5b 33 5d 20 3d 20 = Y;. R[3] =
2220: 30 3b 0a 20 20 20 20 52 5b 34 5d 20 3d 20 30 3b 0;. R[4] = 0;
2230: 0a 20 20 20 20 52 5b 35 5d 20 3d 20 30 3b 0a 20 . R[5] = 0;.
2240: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2f 2a 20 52 }else{. /* R
2250: 65 75 73 65 20 4d 5b 5d 20 61 73 20 66 6f 6c 6c euse M[] as foll
2260: 6f 77 73 3a 0a 20 20 20 20 2a 2a 0a 20 20 20 20 ows:. **.
2270: 2a 2a 20 20 20 20 20 4d 5b 64 5d 5b 31 5d 20 3d ** M[d][1] =
2280: 20 31 20 69 66 20 61 20 6c 69 6e 65 20 69 73 20 1 if a line is
2290: 69 6e 73 65 72 74 65 64 20 6f 72 20 30 20 69 66 inserted or 0 if
22a0: 20 61 20 6c 69 6e 65 20 69 73 20 64 65 6c 65 74 a line is delet
22b0: 65 64 2e 0a 20 20 20 20 2a 2a 20 20 20 20 20 4d ed.. ** M
22c0: 5b 64 5d 5b 30 5d 20 3d 20 6e 75 6d 62 65 72 20 [d][0] = number
22d0: 6f 66 20 6c 69 6e 65 73 20 63 6f 70 69 65 64 20 of lines copied
22e0: 61 66 74 65 72 20 74 68 65 20 69 6e 73 20 6f 72 after the ins or
22f0: 20 64 65 6c 20 61 62 6f 76 65 2e 0a 20 20 20 20 del above..
2300: 2a 2a 0a 20 20 20 20 2a 2f 0a 20 20 20 20 44 20 **. */. D
2310: 3d 20 64 20 2d 20 31 3b 0a 20 20 20 20 4b 20 3d = d - 1;. K =
2320: 20 58 20 2d 20 59 3b 0a 20 20 20 20 66 6f 72 28 X - Y;. for(
2330: 64 3d 44 2c 20 69 3d 28 4b 2b 44 29 2f 32 3b 20 d=D, i=(K+D)/2;
2340: 64 3e 30 3b 20 64 2d 2d 29 7b 0a 20 20 20 20 20 d>0; d--){.
2350: 20 44 45 42 55 47 28 20 70 72 69 6e 74 66 28 22 DEBUG( printf("
2360: 64 3d 25 64 20 69 3d 25 64 5c 6e 22 2c 20 64 2c d=%d i=%d\n", d,
2370: 20 69 29 3b 20 29 0a 20 20 20 20 20 20 69 66 28 i); ). if(
2380: 20 69 3d 3d 64 20 7c 7c 20 28 69 3e 30 20 26 26 i==d || (i>0 &&
2390: 20 4d 5b 64 2d 31 5d 5b 69 2d 31 5d 20 3e 20 4d M[d-1][i-1] > M
23a0: 5b 64 2d 31 5d 5b 69 5d 29 20 29 7b 0a 20 20 20 [d-1][i]) ){.
23b0: 20 20 20 20 20 4d 5b 64 5d 5b 30 5d 20 3d 20 4d M[d][0] = M
23c0: 5b 64 5d 5b 69 5d 20 2d 20 4d 5b 64 2d 31 5d 5b [d][i] - M[d-1][
23d0: 69 2d 31 5d 20 2d 20 31 3b 0a 20 20 20 20 20 20 i-1] - 1;.
23e0: 20 20 4d 5b 64 5d 5b 31 5d 20 3d 20 30 3b 0a 20 M[d][1] = 0;.
23f0: 20 20 20 20 20 20 20 69 2d 2d 3b 0a 20 20 20 20 i--;.
2400: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 }else{.
2410: 20 4d 5b 64 5d 5b 30 5d 20 3d 20 4d 5b 64 5d 5b M[d][0] = M[d][
2420: 69 5d 20 2d 20 4d 5b 64 2d 31 5d 5b 69 5d 20 2d i] - M[d-1][i] -
2430: 20 31 3b 0a 20 20 20 20 20 20 20 20 4d 5b 64 5d 1;. M[d]
2440: 5b 31 5d 20 3d 20 31 3b 0a 20 20 20 20 20 20 7d [1] = 1;. }
2450: 0a 20 20 20 20 7d 0a 20 20 20 20 0a 20 20 20 20 . }. .
2460: 44 45 42 55 47 28 0a 20 20 20 20 20 20 70 72 69 DEBUG(. pri
2470: 6e 74 66 28 22 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ntf("-----------
2480: 2d 2d 2d 2d 5c 6e 4d 5b 30 5d 5b 30 5d 20 3d 20 ----\nM[0][0] =
2490: 25 35 64 5c 6e 22 2c 20 4d 5b 30 5d 5b 30 5d 29 %5d\n", M[0][0])
24a0: 3b 0a 20 20 20 20 20 20 66 6f 72 28 64 3d 31 3b ;. for(d=1;
24b0: 20 64 3c 3d 44 3b 20 64 2b 2b 29 7b 0a 20 20 20 d<=D; d++){.
24c0: 20 20 20 20 20 70 72 69 6e 74 66 28 22 4d 5b 25 printf("M[%
24d0: 64 5d 5b 30 5d 20 3d 20 25 35 64 20 20 20 20 4d d][0] = %5d M
24e0: 5b 25 64 5d 5b 31 5d 20 3d 20 25 64 5c 6e 22 2c [%d][1] = %d\n",
24f0: 64 2c 4d 5b 64 5d 5b 30 5d 2c 64 2c 4d 5b 64 5d d,M[d][0],d,M[d]
2500: 5b 31 5d 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 [1]);. }.
2510: 20 20 29 0a 20 20 20 20 0a 20 20 20 20 2f 2a 20 ). . /*
2520: 41 6c 6c 6f 63 61 74 65 20 74 68 65 20 6f 75 74 Allocate the out
2530: 70 75 74 20 76 65 63 74 6f 72 0a 20 20 20 20 2a put vector. *
2540: 2f 0a 20 20 20 20 52 20 3d 20 6d 61 6c 6c 6f 63 /. R = malloc
2550: 28 20 73 69 7a 65 6f 66 28 52 5b 30 5d 29 2a 28 ( sizeof(R[0])*(
2560: 44 2b 32 29 2a 33 20 29 3b 0a 20 20 20 20 69 66 D+2)*3 );. if
2570: 28 20 52 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 ( R==0 ){.
2580: 66 6f 73 73 69 6c 5f 66 61 74 61 6c 28 22 6f 75 fossil_fatal("ou
2590: 74 20 6f 66 20 6d 65 6d 6f 72 79 22 29 3b 0a 20 t of memory");.
25a0: 20 20 20 7d 0a 20 20 20 20 0a 20 20 20 20 2f 2a }. . /*
25b0: 20 50 6f 70 75 6c 61 74 65 20 74 68 65 20 6f 75 Populate the ou
25c0: 74 70 75 74 20 76 65 63 74 6f 72 0a 20 20 20 20 tput vector.
25d0: 2a 2f 0a 20 20 20 20 64 20 3d 20 72 20 3d 20 30 */. d = r = 0
25e0: 3b 0a 20 20 20 20 77 68 69 6c 65 28 20 64 3c 3d ;. while( d<=
25f0: 44 20 29 7b 0a 20 20 20 20 20 20 69 6e 74 20 6e D ){. int n
2600: 3b 0a 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d ;. R[r++] =
2610: 20 4d 5b 64 2b 2b 5d 5b 30 5d 2f 32 3b 20 20 20 M[d++][0]/2;
2620: 2f 2a 20 43 4f 50 59 20 2a 2f 0a 20 20 20 20 20 /* COPY */.
2630: 20 69 66 28 20 64 3e 44 20 29 7b 0a 20 20 20 20 if( d>D ){.
2640: 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 0a R[r++] = 0;.
2650: 20 20 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d R[r++] =
2660: 20 30 3b 0a 20 20 20 20 20 20 20 20 62 72 65 61 0;. brea
2670: 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 k;. }.
2680: 20 69 66 28 20 4d 5b 64 5d 5b 31 5d 3d 3d 30 20 if( M[d][1]==0
2690: 29 7b 0a 20 20 20 20 20 20 20 20 6e 20 3d 20 31 ){. n = 1
26a0: 3b 0a 20 20 20 20 20 20 20 20 77 68 69 6c 65 28 ;. while(
26b0: 20 4d 5b 64 5d 5b 30 5d 3d 3d 30 20 26 26 20 64 M[d][0]==0 && d
26c0: 3c 44 20 26 26 20 4d 5b 64 2b 31 5d 5b 31 5d 3d <D && M[d+1][1]=
26d0: 3d 30 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 =0 ){.
26e0: 64 2b 2b 3b 0a 20 20 20 20 20 20 20 20 20 20 6e d++;. n
26f0: 2b 2b 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 ++;. }.
2700: 20 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 6e R[r++] = n
2710: 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44 ; /* D
2720: 45 4c 45 54 45 20 2a 2f 0a 20 20 20 20 20 20 20 ELETE */.
2730: 20 69 66 28 20 64 3d 3d 44 20 7c 7c 20 4d 5b 64 if( d==D || M[d
2740: 5d 5b 30 5d 3e 30 20 29 7b 0a 20 20 20 20 20 20 ][0]>0 ){.
2750: 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 20 R[r++] = 0;
2760: 20 20 20 20 20 20 20 20 2f 2a 20 49 4e 53 45 52 /* INSER
2770: 54 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 63 T */. c
2780: 6f 6e 74 69 6e 75 65 3b 0a 20 20 20 20 20 20 20 ontinue;.
2790: 20 7d 0a 20 20 20 20 20 20 20 20 64 2b 2b 3b 0a }. d++;.
27a0: 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 }else{.
27b0: 20 20 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b R[r++] = 0;
27c0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44 45 /* DE
27d0: 4c 45 54 45 20 2a 2f 0a 20 20 20 20 20 20 7d 0a LETE */. }.
27e0: 20 20 20 20 20 20 61 73 73 65 72 74 28 20 4d 5b assert( M[
27f0: 64 5d 5b 31 5d 3d 3d 31 20 29 3b 0a 20 20 20 20 d][1]==1 );.
2800: 20 20 6e 20 3d 20 31 3b 0a 20 20 20 20 20 20 77 n = 1;. w
2810: 68 69 6c 65 28 20 4d 5b 64 5d 5b 30 5d 3d 3d 30 hile( M[d][0]==0
2820: 20 26 26 20 64 3c 44 20 26 26 20 4d 5b 64 2b 31 && d<D && M[d+1
2830: 5d 5b 31 5d 3d 3d 31 20 29 7b 0a 20 20 20 20 20 ][1]==1 ){.
2840: 20 20 20 64 2b 2b 3b 0a 20 20 20 20 20 20 20 20 d++;.
2850: 6e 2b 2b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 n++;. }.
2860: 20 20 20 52 5b 72 2b 2b 5d 20 3d 20 6e 3b 20 20 R[r++] = n;
2870: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 4e 53 /* INS
2880: 45 52 54 20 2a 2f 0a 20 20 20 20 7d 0a 20 20 20 ERT */. }.
2890: 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 0a 20 20 20 R[r++] = 0;.
28a0: 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 0a 20 20 20 R[r++] = 0;.
28b0: 20 52 5b 72 2b 2b 5d 20 3d 20 30 3b 0a 20 20 7d R[r++] = 0;. }
28c0: 0a 20 20 20 20 0a 20 20 2f 2a 20 46 72 65 65 20 . . /* Free
28d0: 74 68 65 20 4d 79 65 72 73 20 6d 61 74 72 69 78 the Myers matrix
28e0: 20 2a 2f 0a 20 20 66 6f 72 28 64 3d 30 3b 20 64 */. for(d=0; d
28f0: 3c 3d 44 3b 20 64 2b 2b 29 7b 0a 20 20 20 20 66 <=D; d++){. f
2900: 72 65 65 28 4d 5b 64 5d 29 3b 0a 20 20 7d 0a 20 ree(M[d]);. }.
2910: 20 66 72 65 65 28 4d 29 3b 0a 0a 20 20 2f 2a 20 free(M);.. /*
2920: 49 66 20 70 4f 75 74 20 69 73 20 64 65 66 69 6e If pOut is defin
2930: 65 64 2c 20 63 6f 6e 73 74 72 75 63 74 20 61 20 ed, construct a
2940: 75 6e 69 66 69 65 64 20 64 69 66 66 20 69 6e 74 unified diff int
2950: 6f 20 70 4f 75 74 20 61 6e 64 0a 20 20 2a 2a 20 o pOut and. **
2960: 64 65 6c 65 74 65 20 52 0a 20 20 2a 2f 0a 20 20 delete R. */.
2970: 69 66 28 20 70 4f 75 74 20 29 7b 0a 20 20 20 20 if( pOut ){.
2980: 69 6e 74 20 61 20 3d 20 30 3b 20 20 20 20 2f 2a int a = 0; /*
2990: 20 49 6e 64 65 78 20 6f 66 20 6e 65 78 74 20 6c Index of next l
29a0: 69 6e 65 20 69 6e 20 41 5b 5d 20 2a 2f 0a 20 20 ine in A[] */.
29b0: 20 20 69 6e 74 20 62 20 3d 20 30 3b 20 20 20 20 int b = 0;
29c0: 2f 2a 20 49 6e 64 65 78 20 6f 66 20 6e 65 78 74 /* Index of next
29d0: 20 6c 69 6e 65 20 69 6e 20 42 5b 5d 20 2a 2f 0a line in B[] */.
29e0: 20 20 20 20 69 6e 74 20 6e 72 3b 20 20 20 20 20 int nr;
29f0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 43 /* Number of C
2a00: 4f 50 59 2f 44 45 4c 45 54 45 2f 49 4e 53 45 52 OPY/DELETE/INSER
2a10: 54 20 74 72 69 70 6c 65 73 20 74 6f 20 70 72 6f T triples to pro
2a20: 63 65 73 73 20 2a 2f 0a 20 20 20 20 69 6e 74 20 cess */. int
2a30: 6e 61 2c 20 6e 62 3b 20 20 20 2f 2a 20 4e 75 6d na, nb; /* Num
2a40: 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 73 68 6f ber of lines sho
2a50: 77 6e 20 66 72 6f 6d 20 41 20 61 6e 64 20 42 20 wn from A and B
2a60: 2a 2f 0a 20 20 20 20 69 6e 74 20 69 2c 20 6a 3b */. int i, j;
2a70: 20 20 20 20 20 2f 2a 20 4c 6f 6f 70 20 63 6f 75 /* Loop cou
2a80: 6e 74 65 72 73 20 2a 2f 0a 20 20 20 20 69 6e 74 nters */. int
2a90: 20 6d 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 m; /* Nu
2aa0: 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 74 6f mber of lines to
2ab0: 20 6f 75 74 70 75 74 20 2a 2f 0a 20 20 20 20 69 output */. i
2ac0: 6e 74 20 73 6b 69 70 3b 20 20 20 20 20 2f 2a 20 nt skip; /*
2ad0: 4e 75 6d 62 65 72 20 6f 66 20 6c 69 6e 65 73 20 Number of lines
2ae0: 74 6f 20 73 6b 69 70 20 2a 2f 0a 0a 20 20 20 20 to skip */..
2af0: 66 6f 72 28 72 3d 30 3b 20 52 5b 72 2b 31 5d 20 for(r=0; R[r+1]
2b00: 7c 7c 20 52 5b 72 2b 32 5d 20 7c 7c 20 52 5b 72 || R[r+2] || R[r
2b10: 2b 33 5d 3b 20 72 20 2b 3d 20 33 2a 6e 72 29 7b +3]; r += 3*nr){
2b20: 0a 20 20 20 20 20 20 2f 2a 20 46 69 67 75 72 65 . /* Figure
2b30: 20 6f 75 74 20 68 6f 77 20 6d 61 6e 79 20 74 72 out how many tr
2b40: 69 70 6c 65 73 20 74 6f 20 73 68 6f 77 20 69 6e iples to show in
2b50: 20 61 20 73 69 6e 67 6c 65 20 62 6c 6f 63 6b 20 a single block
2b60: 2a 2f 0a 20 20 20 20 20 20 66 6f 72 28 6e 72 3d */. for(nr=
2b70: 31 3b 20 52 5b 72 2b 6e 72 2a 33 5d 3e 30 20 26 1; R[r+nr*3]>0 &
2b80: 26 20 52 5b 72 2b 6e 72 2a 33 5d 3c 6e 43 6f 6e & R[r+nr*3]<nCon
2b90: 74 65 78 74 2a 32 3b 20 6e 72 2b 2b 29 7b 7d 0a text*2; nr++){}.
2ba0: 20 20 20 20 20 20 44 45 42 55 47 28 20 70 72 69 DEBUG( pri
2bb0: 6e 74 66 28 22 72 3d 25 64 20 6e 72 3d 25 64 5c ntf("r=%d nr=%d\
2bc0: 6e 22 2c 20 72 2c 20 6e 72 29 3b 20 29 0a 0a 20 n", r, nr); )..
2bd0: 20 20 20 20 20 2f 2a 20 46 6f 72 20 74 68 65 20 /* For the
2be0: 63 75 72 72 65 6e 74 20 62 6c 6f 63 6b 20 63 6f current block co
2bf0: 6d 70 72 69 73 69 6e 67 20 6e 72 20 74 72 69 70 mprising nr trip
2c00: 6c 65 73 2c 20 66 69 67 75 72 65 20 6f 75 74 0a les, figure out.
2c10: 20 20 20 20 20 20 2a 2a 20 68 6f 77 20 6d 61 6e ** how man
2c20: 79 20 6c 69 6e 65 73 20 6f 66 20 41 20 61 6e 64 y lines of A and
2c30: 20 42 20 61 72 65 20 74 6f 20 62 65 20 64 69 73 B are to be dis
2c40: 70 6c 61 79 65 64 0a 20 20 20 20 20 20 2a 2f 0a played. */.
2c50: 20 20 20 20 20 20 69 66 28 20 52 5b 72 5d 3e 6e if( R[r]>n
2c60: 43 6f 6e 74 65 78 74 20 29 7b 0a 20 20 20 20 20 Context ){.
2c70: 20 20 20 6e 61 20 3d 20 6e 62 20 3d 20 6e 43 6f na = nb = nCo
2c80: 6e 74 65 78 74 3b 0a 20 20 20 20 20 20 20 20 73 ntext;. s
2c90: 6b 69 70 20 3d 20 52 5b 72 5d 20 2d 20 6e 43 6f kip = R[r] - nCo
2ca0: 6e 74 65 78 74 3b 0a 20 20 20 20 20 20 7d 65 6c ntext;. }el
2cb0: 73 65 7b 0a 20 20 20 20 20 20 20 20 6e 61 20 3d se{. na =
2cc0: 20 6e 62 20 3d 20 52 5b 72 5d 3b 0a 20 20 20 20 nb = R[r];.
2cd0: 20 20 20 20 73 6b 69 70 20 3d 20 30 3b 0a 20 20 skip = 0;.
2ce0: 20 20 20 20 7d 0a 20 20 20 20 20 20 66 6f 72 28 }. for(
2cf0: 69 3d 30 3b 20 69 3c 6e 72 3b 20 69 2b 2b 29 7b i=0; i<nr; i++){
2d00: 0a 20 20 20 20 20 20 20 20 6e 61 20 2b 3d 20 52 . na += R
2d10: 5b 72 2b 69 2a 33 2b 31 5d 3b 0a 20 20 20 20 20 [r+i*3+1];.
2d20: 20 20 20 6e 62 20 2b 3d 20 52 5b 72 2b 69 2a 33 nb += R[r+i*3
2d30: 2b 32 5d 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 +2];. }.
2d40: 20 20 20 69 66 28 20 52 5b 72 2b 6e 72 2a 33 5d if( R[r+nr*3]
2d50: 3e 6e 43 6f 6e 74 65 78 74 20 29 7b 0a 20 20 20 >nContext ){.
2d60: 20 20 20 20 20 6e 61 20 2b 3d 20 6e 43 6f 6e 74 na += nCont
2d70: 65 78 74 3b 0a 20 20 20 20 20 20 20 20 6e 62 20 ext;. nb
2d80: 2b 3d 20 6e 43 6f 6e 74 65 78 74 3b 0a 20 20 20 += nContext;.
2d90: 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 }else{.
2da0: 20 20 6e 61 20 2b 3d 20 52 5b 72 2b 6e 72 2a 33 na += R[r+nr*3
2db0: 5d 3b 0a 20 20 20 20 20 20 20 20 6e 62 20 2b 3d ];. nb +=
2dc0: 20 52 5b 72 2b 6e 72 2a 33 5d 3b 0a 20 20 20 20 R[r+nr*3];.
2dd0: 20 20 7d 0a 20 20 20 20 20 20 66 6f 72 28 69 3d }. for(i=
2de0: 31 3b 20 69 3c 6e 72 3b 20 69 2b 2b 29 7b 0a 20 1; i<nr; i++){.
2df0: 20 20 20 20 20 20 20 6e 61 20 2b 3d 20 52 5b 72 na += R[r
2e00: 2b 69 2a 33 5d 3b 0a 20 20 20 20 20 20 20 20 6e +i*3];. n
2e10: 62 20 2b 3d 20 52 5b 72 2b 69 2a 33 5d 3b 0a 20 b += R[r+i*3];.
2e20: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 62 6c 6f }. blo
2e30: 62 5f 61 70 70 65 6e 64 66 28 70 4f 75 74 2c 22 b_appendf(pOut,"
2e40: 40 40 20 2d 25 64 2c 25 64 20 2b 25 64 2c 25 64 @@ -%d,%d +%d,%d
2e50: 20 40 40 5c 6e 22 2c 20 61 2b 73 6b 69 70 2b 31 @@\n", a+skip+1
2e60: 2c 20 6e 61 2c 20 62 2b 73 6b 69 70 2b 31 2c 20 , na, b+skip+1,
2e70: 6e 62 29 3b 0a 0a 20 20 20 20 20 20 2f 2a 20 53 nb);.. /* S
2e80: 68 6f 77 20 74 68 65 20 69 6e 69 74 69 61 6c 20 how the initial
2e90: 63 6f 6d 6d 6f 6e 20 61 72 65 61 20 2a 2f 0a 20 common area */.
2ea0: 20 20 20 20 20 61 20 2b 3d 20 73 6b 69 70 3b 0a a += skip;.
2eb0: 20 20 20 20 20 20 62 20 2b 3d 20 73 6b 69 70 3b b += skip;
2ec0: 0a 20 20 20 20 20 20 6d 20 3d 20 52 5b 72 5d 20 . m = R[r]
2ed0: 2d 20 73 6b 69 70 3b 0a 20 20 20 20 20 20 66 6f - skip;. fo
2ee0: 72 28 6a 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 r(j=0; j<m; j++)
2ef0: 7b 0a 20 20 20 20 20 20 20 20 62 6c 6f 62 5f 61 {. blob_a
2f00: 70 70 65 6e 64 66 28 70 4f 75 74 2c 22 20 25 2e ppendf(pOut," %.
2f10: 2a 73 5c 6e 22 2c 20 41 5b 61 2b 6a 5d 2e 68 20 *s\n", A[a+j].h
2f20: 26 20 4c 45 4e 47 54 48 5f 4d 41 53 4b 2c 20 41 & LENGTH_MASK, A
2f30: 5b 61 2b 6a 5d 2e 7a 29 3b 0a 20 20 20 20 20 20 [a+j].z);.
2f40: 7d 0a 20 20 20 20 20 20 61 20 2b 3d 20 6d 3b 0a }. a += m;.
2f50: 20 20 20 20 20 20 62 20 2b 3d 20 6d 3b 0a 0a 20 b += m;..
2f60: 20 20 20 20 20 2f 2a 20 53 68 6f 77 20 74 68 65 /* Show the
2f70: 20 64 69 66 66 65 72 65 6e 63 65 73 20 2a 2f 0a differences */.
2f80: 20 20 20 20 20 20 66 6f 72 28 69 3d 30 3b 20 69 for(i=0; i
2f90: 3c 6e 72 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 <nr; i++){.
2fa0: 20 20 20 6d 20 3d 20 52 5b 72 2b 69 2a 33 2b 31 m = R[r+i*3+1
2fb0: 5d 3b 0a 20 20 20 20 20 20 20 20 66 6f 72 28 6a ];. for(j
2fc0: 3d 30 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 =0; j<m; j++){.
2fd0: 20 20 20 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 blob_ap
2fe0: 70 65 6e 64 66 28 70 4f 75 74 2c 22 2d 25 2e 2a pendf(pOut,"-%.*
2ff0: 73 5c 6e 22 2c 20 41 5b 61 2b 6a 5d 2e 68 20 26 s\n", A[a+j].h &
3000: 20 4c 45 4e 47 54 48 5f 4d 41 53 4b 2c 20 41 5b LENGTH_MASK, A[
3010: 61 2b 6a 5d 2e 7a 29 3b 0a 20 20 20 20 20 20 20 a+j].z);.
3020: 20 7d 0a 20 20 20 20 20 20 20 20 61 20 2b 3d 20 }. a +=
3030: 6d 3b 0a 20 20 20 20 20 20 20 20 6d 20 3d 20 52 m;. m = R
3040: 5b 72 2b 69 2a 33 2b 32 5d 3b 0a 20 20 20 20 20 [r+i*3+2];.
3050: 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c 6d 3b for(j=0; j<m;
3060: 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 20 j++){.
3070: 20 62 6c 6f 62 5f 61 70 70 65 6e 64 66 28 70 4f blob_appendf(pO
3080: 75 74 2c 22 2b 25 2e 2a 73 5c 6e 22 2c 20 42 5b ut,"+%.*s\n", B[
3090: 62 2b 6a 5d 2e 68 20 26 20 4c 45 4e 47 54 48 5f b+j].h & LENGTH_
30a0: 4d 41 53 4b 2c 20 42 5b 62 2b 6a 5d 2e 7a 29 3b MASK, B[b+j].z);
30b0: 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 . }.
30c0: 20 20 20 62 20 2b 3d 20 6d 3b 0a 20 20 20 20 20 b += m;.
30d0: 20 20 20 69 66 28 20 69 3c 6e 72 2d 31 20 29 7b if( i<nr-1 ){
30e0: 0a 20 20 20 20 20 20 20 20 20 20 6d 20 3d 20 52 . m = R
30f0: 5b 72 2b 69 2a 33 2b 33 5d 3b 0a 20 20 20 20 20 [r+i*3+3];.
3100: 20 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c for(j=0; j<
3110: 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 20 m; j++){.
3120: 20 20 20 20 20 62 6c 6f 62 5f 61 70 70 65 6e 64 blob_append
3130: 66 28 70 4f 75 74 2c 22 20 25 2e 2a 73 5c 6e 22 f(pOut," %.*s\n"
3140: 2c 20 42 5b 62 2b 6a 5d 2e 68 20 26 20 4c 45 4e , B[b+j].h & LEN
3150: 47 54 48 5f 4d 41 53 4b 2c 20 42 5b 62 2b 6a 5d GTH_MASK, B[b+j]
3160: 2e 7a 29 3b 0a 20 20 20 20 20 20 20 20 20 20 7d .z);. }
3170: 0a 20 20 20 20 20 20 20 20 20 20 62 20 2b 3d 20 . b +=
3180: 6d 3b 0a 20 20 20 20 20 20 20 20 20 20 61 20 2b m;. a +
3190: 3d 20 6d 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 = m;. }.
31a0: 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 2f 2a }.. /*
31b0: 20 53 68 6f 77 20 74 68 65 20 66 69 6e 61 6c 20 Show the final
31c0: 63 6f 6d 6d 6f 6e 20 61 72 65 61 20 2a 2f 0a 20 common area */.
31d0: 20 20 20 20 20 61 73 73 65 72 74 28 20 6e 72 3d assert( nr=
31e0: 3d 69 20 29 3b 0a 20 20 20 20 20 20 6d 20 3d 20 =i );. m =
31f0: 52 5b 72 2b 6e 72 2a 33 5d 3b 0a 20 20 20 20 20 R[r+nr*3];.
3200: 20 69 66 28 20 6d 3e 6e 43 6f 6e 74 65 78 74 20 if( m>nContext
3210: 29 20 6d 20 3d 20 6e 43 6f 6e 74 65 78 74 3b 0a ) m = nContext;.
3220: 20 20 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a for(j=0; j
3230: 3c 6d 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 <m; j++){.
3240: 20 20 62 6c 6f 62 5f 61 70 70 65 6e 64 66 28 70 blob_appendf(p
3250: 4f 75 74 2c 22 20 25 2e 2a 73 5c 6e 22 2c 20 42 Out," %.*s\n", B
3260: 5b 62 2b 6a 5d 2e 68 20 26 20 4c 45 4e 47 54 48 [b+j].h & LENGTH
3270: 5f 4d 41 53 4b 2c 20 42 5b 62 2b 6a 5d 2e 7a 29 _MASK, B[b+j].z)
3280: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a ;. }. }.
3290: 20 20 20 20 66 72 65 65 28 52 29 3b 0a 20 20 20 free(R);.
32a0: 20 52 20 3d 20 30 3b 0a 20 20 7d 0a 0a 20 20 2f R = 0;. }.. /
32b0: 2a 20 57 65 20 6e 6f 20 6c 6f 6e 67 65 72 20 6e * We no longer n
32c0: 65 65 64 20 74 68 65 20 41 5b 5d 20 61 6e 64 20 eed the A[] and
32d0: 42 5b 5d 20 76 65 63 74 6f 72 73 20 2a 2f 0a 20 B[] vectors */.
32e0: 20 66 72 65 65 28 41 29 3b 0a 20 20 66 72 65 65 free(A);. free
32f0: 28 42 29 3b 0a 0a 20 20 2f 2a 20 52 65 74 75 72 (B);.. /* Retur
3300: 6e 20 74 68 65 20 72 65 73 75 6c 74 20 2a 2f 0a n the result */.
3310: 20 20 72 65 74 75 72 6e 20 52 3b 0a 7d 0a 0a 2f return R;.}../
3320: 2a 0a 2a 2a 20 43 4f 4d 4d 41 4e 44 3a 20 74 65 *.** COMMAND: te
3330: 73 74 2d 72 61 77 64 69 66 66 0a 2a 2f 0a 76 6f st-rawdiff.*/.vo
3340: 69 64 20 74 65 73 74 5f 72 61 77 64 69 66 66 5f id test_rawdiff_
3350: 63 6d 64 28 76 6f 69 64 29 7b 0a 20 20 42 6c 6f cmd(void){. Blo
3360: 62 20 61 2c 20 62 3b 0a 20 20 69 6e 74 20 72 3b b a, b;. int r;
3370: 0a 20 20 69 6e 74 20 69 3b 0a 20 20 69 6e 74 20 . int i;. int
3380: 2a 52 3b 0a 20 20 69 66 28 20 67 2e 61 72 67 63 *R;. if( g.argc
3390: 3c 34 20 29 20 75 73 61 67 65 28 22 46 49 4c 45 <4 ) usage("FILE
33a0: 31 20 46 49 4c 45 32 20 2e 2e 2e 22 29 3b 0a 20 1 FILE2 ...");.
33b0: 20 62 6c 6f 62 5f 72 65 61 64 5f 66 72 6f 6d 5f blob_read_from_
33c0: 66 69 6c 65 28 26 61 2c 20 67 2e 61 72 67 76 5b file(&a, g.argv[
33d0: 32 5d 29 3b 0a 20 20 66 6f 72 28 69 3d 33 3b 20 2]);. for(i=3;
33e0: 69 3c 67 2e 61 72 67 63 3b 20 69 2b 2b 29 7b 0a i<g.argc; i++){.
33f0: 20 20 20 20 69 66 28 20 69 3e 33 20 29 20 70 72 if( i>3 ) pr
3400: 69 6e 74 66 28 22 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d intf("----------
3410: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3420: 2d 2d 2d 2d 2d 5c 6e 22 29 3b 0a 20 20 20 20 62 -----\n");. b
3430: 6c 6f 62 5f 72 65 61 64 5f 66 72 6f 6d 5f 66 69 lob_read_from_fi
3440: 6c 65 28 26 62 2c 20 67 2e 61 72 67 76 5b 69 5d le(&b, g.argv[i]
3450: 29 3b 0a 20 20 20 20 52 20 3d 20 74 65 78 74 5f );. R = text_
3460: 64 69 66 66 28 26 61 2c 20 26 62 2c 20 30 2c 20 diff(&a, &b, 0,
3470: 30 29 3b 0a 20 20 20 20 66 6f 72 28 72 3d 30 3b 0);. for(r=0;
3480: 20 52 5b 72 5d 20 7c 7c 20 52 5b 72 2b 31 5d 20 R[r] || R[r+1]
3490: 7c 7c 20 52 5b 72 2b 32 5d 3b 20 72 20 2b 3d 20 || R[r+2]; r +=
34a0: 33 29 7b 0a 20 20 20 20 20 20 70 72 69 6e 74 66 3){. printf
34b0: 28 22 20 63 6f 70 79 20 25 34 64 20 20 64 65 6c (" copy %4d del
34c0: 65 74 65 20 25 34 64 20 20 69 6e 73 65 72 74 20 ete %4d insert
34d0: 25 34 64 5c 6e 22 2c 20 52 5b 72 5d 2c 20 52 5b %4d\n", R[r], R[
34e0: 72 2b 31 5d 2c 20 52 5b 72 2b 32 5d 29 3b 0a 20 r+1], R[r+2]);.
34f0: 20 20 20 7d 0a 20 20 20 20 2f 2a 20 66 72 65 65 }. /* free
3500: 28 52 29 3b 20 2a 2f 0a 20 20 20 20 62 6c 6f 62 (R); */. blob
3510: 5f 72 65 73 65 74 28 26 62 29 3b 0a 20 20 7d 0a _reset(&b);. }.
3520: 7d 0a 0a 2f 2a 0a 2a 2a 20 43 4f 4d 4d 41 4e 44 }../*.** COMMAND
3530: 3a 20 74 65 73 74 2d 75 64 69 66 66 0a 2a 2f 0a : test-udiff.*/.
3540: 76 6f 69 64 20 74 65 73 74 5f 75 64 69 66 66 5f void test_udiff_
3550: 63 6d 64 28 76 6f 69 64 29 7b 0a 20 20 42 6c 6f cmd(void){. Blo
3560: 62 20 61 2c 20 62 2c 20 6f 75 74 3b 0a 20 20 69 b a, b, out;. i
3570: 66 28 20 67 2e 61 72 67 63 21 3d 34 20 29 20 75 f( g.argc!=4 ) u
3580: 73 61 67 65 28 22 46 49 4c 45 31 20 46 49 4c 45 sage("FILE1 FILE
3590: 32 22 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 61 64 2");. blob_read
35a0: 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 61 2c 20 67 _from_file(&a, g
35b0: 2e 61 72 67 76 5b 32 5d 29 3b 0a 20 20 62 6c 6f .argv[2]);. blo
35c0: 62 5f 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 b_read_from_file
35d0: 28 26 62 2c 20 67 2e 61 72 67 76 5b 33 5d 29 3b (&b, g.argv[3]);
35e0: 0a 20 20 62 6c 6f 62 5f 7a 65 72 6f 28 26 6f 75 . blob_zero(&ou
35f0: 74 29 3b 0a 20 20 74 65 78 74 5f 64 69 66 66 28 t);. text_diff(
3600: 26 61 2c 20 26 62 2c 20 26 6f 75 74 2c 20 33 29 &a, &b, &out, 3)
3610: 3b 0a 20 20 62 6c 6f 62 5f 77 72 69 74 65 5f 74 ;. blob_write_t
3620: 6f 5f 66 69 6c 65 28 26 6f 75 74 2c 20 22 2d 22 o_file(&out, "-"
3630: 29 3b 0a 7d 0a );.}.