1/*
2* LibXDiff by Davide Libenzi ( File Differential Library )
3* Copyright (C) 2003 Davide Libenzi
4*
5* This library is free software; you can redistribute it and/or
6* modify it under the terms of the GNU Lesser General Public
7* License as published by the Free Software Foundation; either
8* version 2.1 of the License, or (at your option) any later version.
9*
10* This library is distributed in the hope that it will be useful,
11* but WITHOUT ANY WARRANTY; without even the implied warranty of
12* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13* Lesser General Public License for more details.
14*
15* You should have received a copy of the GNU Lesser General Public
16* License along with this library; if not, write to the Free Software
17* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18*
19* Davide Libenzi <davidel@xmailserver.org>
20*
21*/
2223
#include <limits.h>
24#include <assert.h>
25#include "xinclude.h"
2627
28
29
30
long xdl_bogosqrt(long n) {
31long i;
3233
/*
34* Classical integer square root approximation using shifts.
35*/
36for (i = 1; n > 0; n >>= 2)
37i <<= 1;
3839
return i;
40}
4142
43
int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
44xdemitcb_t *ecb) {
45int i = 2;
46mmbuffer_t mb[3];
4748
mb[0].ptr = (char *) pre;
49mb[0].size = psize;
50mb[1].ptr = (char *) rec;
51mb[1].size = size;
52if (size > 0 && rec[size - 1] != '\n') {
53mb[2].ptr = (char *) "\n\\ No newline at end of file\n";
54mb[2].size = strlen(mb[2].ptr);
55i++;
56}
57if (ecb->outf(ecb->priv, mb, i) < 0) {
5859
return -1;
60}
6162
return 0;
63}
6465
void *xdl_mmfile_first(mmfile_t *mmf, long *size)
66{
67*size = mmf->size;
68return mmf->ptr;
69}
7071
72
long xdl_mmfile_size(mmfile_t *mmf)
73{
74return mmf->size;
75}
7677
78
int xdl_cha_init(chastore_t *cha, long isize, long icount) {
7980
cha->head = cha->tail = NULL;
81cha->isize = isize;
82cha->nsize = icount * isize;
83cha->ancur = cha->sncur = NULL;
84cha->scurr = 0;
8586
return 0;
87}
8889
90
void xdl_cha_free(chastore_t *cha) {
91chanode_t *cur, *tmp;
9293
for (cur = cha->head; (tmp = cur) != NULL;) {
94cur = cur->next;
95xdl_free(tmp);
96}
97}
9899
100
void *xdl_cha_alloc(chastore_t *cha) {
101chanode_t *ancur;
102void *data;
103104
if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) {
105if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {
106107
return NULL;
108}
109ancur->icurr = 0;
110ancur->next = NULL;
111if (cha->tail)
112cha->tail->next = ancur;
113if (!cha->head)
114cha->head = ancur;
115cha->tail = ancur;
116cha->ancur = ancur;
117}
118119
data = (char *) ancur + sizeof(chanode_t) + ancur->icurr;
120ancur->icurr += cha->isize;
121122
return data;
123}
124125
long xdl_guess_lines(mmfile_t *mf, long sample) {
126long nl = 0, size, tsize = 0;
127char const *data, *cur, *top;
128129
if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
130for (top = data + size; nl < sample && cur < top; ) {
131nl++;
132if (!(cur = memchr(cur, '\n', top - cur)))
133cur = top;
134else
135cur++;
136}
137tsize += (long) (cur - data);
138}
139140
if (nl && tsize)
141nl = xdl_mmfile_size(mf) / (tsize / nl);
142143
return nl + 1;
144}
145146
int xdl_blankline(const char *line, long size, long flags)
147{
148long i;
149150
if (!(flags & XDF_WHITESPACE_FLAGS))
151return (size <= 1);
152153
for (i = 0; i < size && XDL_ISSPACE(line[i]); i++)
154;
155156
return (i == size);
157}
158159
int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
160{
161int i1, i2;
162163
if (s1 == s2 && !memcmp(l1, l2, s1))
164return 1;
165if (!(flags & XDF_WHITESPACE_FLAGS))
166return 0;
167168
i1 = 0;
169i2 = 0;
170171
/*
172* -w matches everything that matches with -b, and -b in turn
173* matches everything that matches with --ignore-space-at-eol.
174*
175* Each flavor of ignoring needs different logic to skip whitespaces
176* while we have both sides to compare.
177*/
178if (flags & XDF_IGNORE_WHITESPACE) {
179goto skip_ws;
180while (i1 < s1 && i2 < s2) {
181if (l1[i1++] != l2[i2++])
182return 0;
183skip_ws:
184while (i1 < s1 && XDL_ISSPACE(l1[i1]))
185i1++;
186while (i2 < s2 && XDL_ISSPACE(l2[i2]))
187i2++;
188}
189} else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
190while (i1 < s1 && i2 < s2) {
191if (XDL_ISSPACE(l1[i1]) && XDL_ISSPACE(l2[i2])) {
192/* Skip matching spaces and try again */
193while (i1 < s1 && XDL_ISSPACE(l1[i1]))
194i1++;
195while (i2 < s2 && XDL_ISSPACE(l2[i2]))
196i2++;
197continue;
198}
199if (l1[i1++] != l2[i2++])
200return 0;
201}
202} else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL) {
203while (i1 < s1 && i2 < s2 && l1[i1] == l2[i2]) {
204i1++;
205i2++;
206}
207}
208209
/*
210* After running out of one side, the remaining side must have
211* nothing but whitespace for the lines to match. Note that
212* ignore-whitespace-at-eol case may break out of the loop
213* while there still are characters remaining on both lines.
214*/
215if (i1 < s1) {
216while (i1 < s1 && XDL_ISSPACE(l1[i1]))
217i1++;
218if (s1 != i1)
219return 0;
220}
221if (i2 < s2) {
222while (i2 < s2 && XDL_ISSPACE(l2[i2]))
223i2++;
224return (s2 == i2);
225}
226return 1;
227}
228229
static unsigned long xdl_hash_record_with_whitespace(char const **data,
230char const *top, long flags) {
231unsigned long ha = 5381;
232char const *ptr = *data;
233234
for (; ptr < top && *ptr != '\n'; ptr++) {
235if (XDL_ISSPACE(*ptr)) {
236const char *ptr2 = ptr;
237int at_eol;
238while (ptr + 1 < top && XDL_ISSPACE(ptr[1])
239&& ptr[1] != '\n')
240ptr++;
241at_eol = (top <= ptr + 1 || ptr[1] == '\n');
242if (flags & XDF_IGNORE_WHITESPACE)
243; /* already handled */
244else if (flags & XDF_IGNORE_WHITESPACE_CHANGE
245&& !at_eol) {
246ha += (ha << 5);
247ha ^= (unsigned long) ' ';
248}
249else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL
250&& !at_eol) {
251while (ptr2 != ptr + 1) {
252ha += (ha << 5);
253ha ^= (unsigned long) *ptr2;
254ptr2++;
255}
256}
257continue;
258}
259ha += (ha << 5);
260ha ^= (unsigned long) *ptr;
261}
262*data = ptr < top ? ptr + 1: ptr;
263264
return ha;
265}
266267
unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
268unsigned long ha = 5381;
269char const *ptr = *data;
270271
if (flags & XDF_WHITESPACE_FLAGS)
272return xdl_hash_record_with_whitespace(data, top, flags);
273274
for (; ptr < top && *ptr != '\n'; ptr++) {
275ha += (ha << 5);
276ha ^= (unsigned long) *ptr;
277}
278*data = ptr < top ? ptr + 1: ptr;
279280
return ha;
281}
282283
unsigned int xdl_hashbits(unsigned int size) {
284unsigned int val = 1, bits = 0;
285286
for (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++);
287return bits ? bits: 1;
288}
289290
291
int xdl_num_out(char *out, long val) {
292char *ptr, *str = out;
293char buf[32];
294295
ptr = buf + sizeof(buf) - 1;
296*ptr = '\0';
297if (val < 0) {
298*--ptr = '-';
299val = -val;
300}
301for (; val && ptr > buf; val /= 10)
302*--ptr = "0123456789"[val % 10];
303if (*ptr)
304for (; *ptr; ptr++, str++)
305*str = *ptr;
306else
307*str++ = '0';
308*str = '\0';
309310
return str - out;
311}
312313
int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
314const char *func, long funclen, xdemitcb_t *ecb) {
315int nb = 0;
316mmbuffer_t mb;
317char buf[128];
318319
memcpy(buf, "@@ -", 4);
320nb += 4;
321322
nb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1);
323324
if (c1 != 1) {
325memcpy(buf + nb, ",", 1);
326nb += 1;
327328
nb += xdl_num_out(buf + nb, c1);
329}
330331
memcpy(buf + nb, " +", 2);
332nb += 2;
333334
nb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1);
335336
if (c2 != 1) {
337memcpy(buf + nb, ",", 1);
338nb += 1;
339340
nb += xdl_num_out(buf + nb, c2);
341}
342343
memcpy(buf + nb, " @@", 3);
344nb += 3;
345if (func && funclen) {
346buf[nb++] = ' ';
347if (funclen > sizeof(buf) - nb - 1)
348funclen = sizeof(buf) - nb - 1;
349memcpy(buf + nb, func, funclen);
350nb += funclen;
351}
352buf[nb++] = '\n';
353354
mb.ptr = buf;
355mb.size = nb;
356if (ecb->outf(ecb->priv, &mb, 1) < 0)
357return -1;
358359
return 0;
360}
361362
int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
363int line1, int count1, int line2, int count2)
364{
365/*
366* This probably does not work outside Git, since
367* we have a very simple mmfile structure.
368*
369* Note: ideally, we would reuse the prepared environment, but
370* the libxdiff interface does not (yet) allow for diffing only
371* ranges of lines instead of the whole files.
372*/
373mmfile_t subfile1, subfile2;
374xdfenv_t env;
375376
subfile1.ptr = (char *)diff_env->xdf1.recs[line1 - 1]->ptr;
377subfile1.size = diff_env->xdf1.recs[line1 + count1 - 2]->ptr +
378diff_env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;
379subfile2.ptr = (char *)diff_env->xdf2.recs[line2 - 1]->ptr;
380subfile2.size = diff_env->xdf2.recs[line2 + count2 - 2]->ptr +
381diff_env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;
382if (xdl_do_diff(&subfile1, &subfile2, xpp, &env) < 0)
383return -1;
384385
memcpy(diff_env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);
386memcpy(diff_env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);
387388
xdl_free_env(&env);
389390
return 0;
391}