]>
Commit | Line | Data |
---|---|---|
3443546f LT |
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 | */ | |
22 | ||
6942efcf TR |
23 | #include <limits.h> |
24 | #include <assert.h> | |
3443546f LT |
25 | #include "xinclude.h" |
26 | ||
27 | ||
28 | ||
3443546f | 29 | |
ca557aff DL |
30 | long xdl_bogosqrt(long n) { |
31 | long i; | |
32 | ||
33 | /* | |
34 | * Classical integer square root approximation using shifts. | |
35 | */ | |
36 | for (i = 1; n > 0; n >>= 2) | |
37 | i <<= 1; | |
38 | ||
39 | return i; | |
40 | } | |
41 | ||
42 | ||
3443546f LT |
43 | int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize, |
44 | xdemitcb_t *ecb) { | |
d281786f | 45 | int i = 2; |
621c53cc | 46 | mmbuffer_t mb[3]; |
3443546f LT |
47 | |
48 | mb[0].ptr = (char *) pre; | |
49 | mb[0].size = psize; | |
50 | mb[1].ptr = (char *) rec; | |
51 | mb[1].size = size; | |
d281786f JH |
52 | if (size > 0 && rec[size - 1] != '\n') { |
53 | mb[2].ptr = (char *) "\n\\ No newline at end of file\n"; | |
621c53cc | 54 | mb[2].size = strlen(mb[2].ptr); |
d281786f | 55 | i++; |
621c53cc | 56 | } |
621c53cc | 57 | if (ecb->outf(ecb->priv, mb, i) < 0) { |
3443546f LT |
58 | |
59 | return -1; | |
60 | } | |
61 | ||
62 | return 0; | |
63 | } | |
64 | ||
65 | void *xdl_mmfile_first(mmfile_t *mmf, long *size) | |
66 | { | |
67 | *size = mmf->size; | |
68 | return mmf->ptr; | |
69 | } | |
70 | ||
71 | ||
3443546f LT |
72 | long xdl_mmfile_size(mmfile_t *mmf) |
73 | { | |
74 | return mmf->size; | |
75 | } | |
76 | ||
77 | ||
78 | int xdl_cha_init(chastore_t *cha, long isize, long icount) { | |
79 | ||
80 | cha->head = cha->tail = NULL; | |
81 | cha->isize = isize; | |
82 | cha->nsize = icount * isize; | |
83 | cha->ancur = cha->sncur = NULL; | |
84 | cha->scurr = 0; | |
85 | ||
86 | return 0; | |
87 | } | |
88 | ||
89 | ||
90 | void xdl_cha_free(chastore_t *cha) { | |
91 | chanode_t *cur, *tmp; | |
92 | ||
93 | for (cur = cha->head; (tmp = cur) != NULL;) { | |
94 | cur = cur->next; | |
95 | xdl_free(tmp); | |
96 | } | |
97 | } | |
98 | ||
99 | ||
100 | void *xdl_cha_alloc(chastore_t *cha) { | |
101 | chanode_t *ancur; | |
102 | void *data; | |
103 | ||
104 | if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) { | |
105 | if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) { | |
106 | ||
107 | return NULL; | |
108 | } | |
109 | ancur->icurr = 0; | |
110 | ancur->next = NULL; | |
111 | if (cha->tail) | |
112 | cha->tail->next = ancur; | |
113 | if (!cha->head) | |
114 | cha->head = ancur; | |
115 | cha->tail = ancur; | |
116 | cha->ancur = ancur; | |
117 | } | |
118 | ||
119 | data = (char *) ancur + sizeof(chanode_t) + ancur->icurr; | |
120 | ancur->icurr += cha->isize; | |
121 | ||
122 | return data; | |
123 | } | |
124 | ||
86abba80 | 125 | long xdl_guess_lines(mmfile_t *mf, long sample) { |
3443546f LT |
126 | long nl = 0, size, tsize = 0; |
127 | char const *data, *cur, *top; | |
128 | ||
129 | if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) { | |
739864b1 | 130 | for (top = data + size; nl < sample && cur < top; ) { |
3443546f LT |
131 | nl++; |
132 | if (!(cur = memchr(cur, '\n', top - cur))) | |
133 | cur = top; | |
134 | else | |
135 | cur++; | |
136 | } | |
137 | tsize += (long) (cur - data); | |
138 | } | |
139 | ||
140 | if (nl && tsize) | |
141 | nl = xdl_mmfile_size(mf) / (tsize / nl); | |
142 | ||
143 | return nl + 1; | |
144 | } | |
145 | ||
36617af7 AP |
146 | int xdl_blankline(const char *line, long size, long flags) |
147 | { | |
148 | long i; | |
149 | ||
150 | if (!(flags & XDF_WHITESPACE_FLAGS)) | |
151 | return (size <= 1); | |
152 | ||
153 | for (i = 0; i < size && XDL_ISSPACE(line[i]); i++) | |
154 | ; | |
155 | ||
156 | return (i == size); | |
157 | } | |
158 | ||
0d21efa5 JS |
159 | int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags) |
160 | { | |
161 | int i1, i2; | |
162 | ||
b4cf0f17 DR |
163 | if (s1 == s2 && !memcmp(l1, l2, s1)) |
164 | return 1; | |
3b5ef0e2 | 165 | if (!(flags & XDF_WHITESPACE_FLAGS)) |
b4cf0f17 | 166 | return 0; |
3b5ef0e2 JH |
167 | |
168 | i1 = 0; | |
169 | i2 = 0; | |
170 | ||
171 | /* | |
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 | */ | |
0d21efa5 | 178 | if (flags & XDF_IGNORE_WHITESPACE) { |
3b5ef0e2 JH |
179 | goto skip_ws; |
180 | while (i1 < s1 && i2 < s2) { | |
181 | if (l1[i1++] != l2[i2++]) | |
2344d47f | 182 | return 0; |
3b5ef0e2 | 183 | skip_ws: |
349362cc | 184 | while (i1 < s1 && XDL_ISSPACE(l1[i1])) |
3b5ef0e2 | 185 | i1++; |
349362cc | 186 | while (i2 < s2 && XDL_ISSPACE(l2[i2])) |
3b5ef0e2 | 187 | i2++; |
0d21efa5 | 188 | } |
0d21efa5 | 189 | } else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) { |
3b5ef0e2 | 190 | while (i1 < s1 && i2 < s2) { |
349362cc | 191 | if (XDL_ISSPACE(l1[i1]) && XDL_ISSPACE(l2[i2])) { |
3b5ef0e2 | 192 | /* Skip matching spaces and try again */ |
349362cc | 193 | while (i1 < s1 && XDL_ISSPACE(l1[i1])) |
859f9c45 | 194 | i1++; |
349362cc | 195 | while (i2 < s2 && XDL_ISSPACE(l2[i2])) |
859f9c45 | 196 | i2++; |
3b5ef0e2 | 197 | continue; |
859f9c45 | 198 | } |
3b5ef0e2 JH |
199 | if (l1[i1++] != l2[i2++]) |
200 | return 0; | |
201 | } | |
202 | } else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL) { | |
203 | while (i1 < s1 && i2 < s2 && l1[i1++] == l2[i2++]) | |
204 | ; /* keep going */ | |
205 | } | |
206 | ||
207 | /* | |
208 | * After running out of one side, the remaining side must have | |
209 | * nothing but whitespace for the lines to match. Note that | |
210 | * ignore-whitespace-at-eol case may break out of the loop | |
211 | * while there still are characters remaining on both lines. | |
212 | */ | |
213 | if (i1 < s1) { | |
349362cc | 214 | while (i1 < s1 && XDL_ISSPACE(l1[i1])) |
859f9c45 | 215 | i1++; |
3b5ef0e2 JH |
216 | if (s1 != i1) |
217 | return 0; | |
218 | } | |
219 | if (i2 < s2) { | |
349362cc | 220 | while (i2 < s2 && XDL_ISSPACE(l2[i2])) |
859f9c45 | 221 | i2++; |
3b5ef0e2 JH |
222 | return (s2 == i2); |
223 | } | |
224 | return 1; | |
0d21efa5 | 225 | } |
3443546f | 226 | |
824f782c JS |
227 | static unsigned long xdl_hash_record_with_whitespace(char const **data, |
228 | char const *top, long flags) { | |
3443546f LT |
229 | unsigned long ha = 5381; |
230 | char const *ptr = *data; | |
231 | ||
232 | for (; ptr < top && *ptr != '\n'; ptr++) { | |
349362cc | 233 | if (XDL_ISSPACE(*ptr)) { |
859f9c45 | 234 | const char *ptr2 = ptr; |
78ed710f | 235 | int at_eol; |
349362cc | 236 | while (ptr + 1 < top && XDL_ISSPACE(ptr[1]) |
2344d47f | 237 | && ptr[1] != '\n') |
0d21efa5 | 238 | ptr++; |
78ed710f | 239 | at_eol = (top <= ptr + 1 || ptr[1] == '\n'); |
6d12acef KC |
240 | if (flags & XDF_IGNORE_WHITESPACE) |
241 | ; /* already handled */ | |
242 | else if (flags & XDF_IGNORE_WHITESPACE_CHANGE | |
78ed710f | 243 | && !at_eol) { |
0d21efa5 JS |
244 | ha += (ha << 5); |
245 | ha ^= (unsigned long) ' '; | |
246 | } | |
6d12acef | 247 | else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL |
78ed710f | 248 | && !at_eol) { |
859f9c45 JS |
249 | while (ptr2 != ptr + 1) { |
250 | ha += (ha << 5); | |
251 | ha ^= (unsigned long) *ptr2; | |
252 | ptr2++; | |
253 | } | |
254 | } | |
0d21efa5 JS |
255 | continue; |
256 | } | |
3443546f LT |
257 | ha += (ha << 5); |
258 | ha ^= (unsigned long) *ptr; | |
259 | } | |
260 | *data = ptr < top ? ptr + 1: ptr; | |
261 | ||
262 | return ha; | |
263 | } | |
264 | ||
6942efcf TR |
265 | #ifdef XDL_FAST_HASH |
266 | ||
9322ce21 RS |
267 | #define REPEAT_BYTE(x) ((~0ul / 0xff) * (x)) |
268 | ||
269 | #define ONEBYTES REPEAT_BYTE(0x01) | |
270 | #define NEWLINEBYTES REPEAT_BYTE(0x0a) | |
271 | #define HIGHBITS REPEAT_BYTE(0x80) | |
6942efcf TR |
272 | |
273 | /* Return the high bit set in the first byte that is a zero */ | |
274 | static inline unsigned long has_zero(unsigned long a) | |
275 | { | |
276 | return ((a - ONEBYTES) & ~a) & HIGHBITS; | |
277 | } | |
278 | ||
6942efcf TR |
279 | static inline long count_masked_bytes(unsigned long mask) |
280 | { | |
6f1af028 TR |
281 | if (sizeof(long) == 8) { |
282 | /* | |
283 | * Jan Achrenius on G+: microoptimized version of | |
284 | * the simpler "(mask & ONEBYTES) * ONEBYTES >> 56" | |
285 | * that works for the bytemasks without having to | |
286 | * mask them first. | |
287 | */ | |
6f1af028 | 288 | /* |
7e356a97 | 289 | * return mask * 0x0001020304050608 >> 56; |
6f1af028 | 290 | * |
7e356a97 | 291 | * Doing it like this avoids warnings on 32-bit machines. |
6f1af028 | 292 | */ |
7e356a97 RS |
293 | long a = (REPEAT_BYTE(0x01) / 0xff + 1); |
294 | return mask * a >> (sizeof(long) * 7); | |
6f1af028 | 295 | } else { |
8072766c RS |
296 | /* Carl Chatfield / Jan Achrenius G+ version for 32-bit */ |
297 | /* (000000 0000ff 00ffff ffffff) -> ( 1 1 2 3 ) */ | |
298 | long a = (0x0ff0001 + mask) >> 23; | |
299 | /* Fix the 1 for 00 case */ | |
300 | return a & mask; | |
6f1af028 | 301 | } |
6942efcf TR |
302 | } |
303 | ||
6942efcf TR |
304 | unsigned long xdl_hash_record(char const **data, char const *top, long flags) |
305 | { | |
306 | unsigned long hash = 5381; | |
307 | unsigned long a = 0, mask = 0; | |
308 | char const *ptr = *data; | |
309 | char const *end = top - sizeof(unsigned long) + 1; | |
310 | ||
311 | if (flags & XDF_WHITESPACE_FLAGS) | |
312 | return xdl_hash_record_with_whitespace(data, top, flags); | |
313 | ||
314 | ptr -= sizeof(unsigned long); | |
315 | do { | |
316 | hash += hash << 5; | |
317 | hash ^= a; | |
318 | ptr += sizeof(unsigned long); | |
319 | if (ptr >= end) | |
320 | break; | |
321 | a = *(unsigned long *)ptr; | |
322 | /* Do we have any '\n' bytes in this word? */ | |
323 | mask = has_zero(a ^ NEWLINEBYTES); | |
324 | } while (!mask); | |
325 | ||
326 | if (ptr >= end) { | |
327 | /* | |
328 | * There is only a partial word left at the end of the | |
329 | * buffer. Because we may work with a memory mapping, | |
330 | * we have to grab the rest byte by byte instead of | |
331 | * blindly reading it. | |
332 | * | |
333 | * To avoid problems with masking in a signed value, | |
334 | * we use an unsigned char here. | |
335 | */ | |
336 | const char *p; | |
337 | for (p = top - 1; p >= ptr; p--) | |
338 | a = (a << 8) + *((const unsigned char *)p); | |
339 | mask = has_zero(a ^ NEWLINEBYTES); | |
340 | if (!mask) | |
341 | /* | |
342 | * No '\n' found in the partial word. Make a | |
343 | * mask that matches what we read. | |
344 | */ | |
345 | mask = 1UL << (8 * (top - ptr) + 7); | |
346 | } | |
347 | ||
348 | /* The mask *below* the first high bit set */ | |
349 | mask = (mask - 1) & ~mask; | |
350 | mask >>= 7; | |
351 | hash += hash << 5; | |
352 | hash ^= a & mask; | |
353 | ||
354 | /* Advance past the last (possibly partial) word */ | |
355 | ptr += count_masked_bytes(mask); | |
356 | ||
357 | if (ptr < top) { | |
358 | assert(*ptr == '\n'); | |
359 | ptr++; | |
360 | } | |
361 | ||
362 | *data = ptr; | |
363 | ||
364 | return hash; | |
365 | } | |
366 | ||
367 | #else /* XDL_FAST_HASH */ | |
3443546f | 368 | |
824f782c JS |
369 | unsigned long xdl_hash_record(char const **data, char const *top, long flags) { |
370 | unsigned long ha = 5381; | |
371 | char const *ptr = *data; | |
372 | ||
373 | if (flags & XDF_WHITESPACE_FLAGS) | |
374 | return xdl_hash_record_with_whitespace(data, top, flags); | |
375 | ||
376 | for (; ptr < top && *ptr != '\n'; ptr++) { | |
377 | ha += (ha << 5); | |
378 | ha ^= (unsigned long) *ptr; | |
379 | } | |
380 | *data = ptr < top ? ptr + 1: ptr; | |
381 | ||
382 | return ha; | |
383 | } | |
384 | ||
6942efcf | 385 | #endif /* XDL_FAST_HASH */ |
824f782c | 386 | |
3443546f LT |
387 | unsigned int xdl_hashbits(unsigned int size) { |
388 | unsigned int val = 1, bits = 0; | |
389 | ||
390 | for (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++); | |
391 | return bits ? bits: 1; | |
392 | } | |
393 | ||
394 | ||
395 | int xdl_num_out(char *out, long val) { | |
396 | char *ptr, *str = out; | |
397 | char buf[32]; | |
398 | ||
399 | ptr = buf + sizeof(buf) - 1; | |
400 | *ptr = '\0'; | |
401 | if (val < 0) { | |
402 | *--ptr = '-'; | |
403 | val = -val; | |
404 | } | |
405 | for (; val && ptr > buf; val /= 10) | |
406 | *--ptr = "0123456789"[val % 10]; | |
407 | if (*ptr) | |
408 | for (; *ptr; ptr++, str++) | |
409 | *str = *ptr; | |
410 | else | |
411 | *str++ = '0'; | |
412 | *str = '\0'; | |
413 | ||
414 | return str - out; | |
415 | } | |
416 | ||
acb72577 MW |
417 | int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, |
418 | const char *func, long funclen, xdemitcb_t *ecb) { | |
3443546f LT |
419 | int nb = 0; |
420 | mmbuffer_t mb; | |
421 | char buf[128]; | |
422 | ||
423 | memcpy(buf, "@@ -", 4); | |
424 | nb += 4; | |
425 | ||
ca557aff | 426 | nb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1); |
3443546f | 427 | |
3ce8f089 JH |
428 | if (c1 != 1) { |
429 | memcpy(buf + nb, ",", 1); | |
430 | nb += 1; | |
3443546f | 431 | |
3ce8f089 JH |
432 | nb += xdl_num_out(buf + nb, c1); |
433 | } | |
3443546f LT |
434 | |
435 | memcpy(buf + nb, " +", 2); | |
436 | nb += 2; | |
437 | ||
ca557aff | 438 | nb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1); |
3443546f | 439 | |
3ce8f089 JH |
440 | if (c2 != 1) { |
441 | memcpy(buf + nb, ",", 1); | |
442 | nb += 1; | |
3443546f | 443 | |
3ce8f089 JH |
444 | nb += xdl_num_out(buf + nb, c2); |
445 | } | |
3443546f | 446 | |
acb72577 MW |
447 | memcpy(buf + nb, " @@", 3); |
448 | nb += 3; | |
449 | if (func && funclen) { | |
450 | buf[nb++] = ' '; | |
451 | if (funclen > sizeof(buf) - nb - 1) | |
452 | funclen = sizeof(buf) - nb - 1; | |
453 | memcpy(buf + nb, func, funclen); | |
454 | nb += funclen; | |
455 | } | |
456 | buf[nb++] = '\n'; | |
3443546f LT |
457 | |
458 | mb.ptr = buf; | |
459 | mb.size = nb; | |
460 | if (ecb->outf(ecb->priv, &mb, 1) < 0) | |
461 | return -1; | |
462 | ||
463 | return 0; | |
464 | } | |
1d26b252 TRC |
465 | |
466 | int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, | |
467 | int line1, int count1, int line2, int count2) | |
468 | { | |
469 | /* | |
470 | * This probably does not work outside Git, since | |
471 | * we have a very simple mmfile structure. | |
472 | * | |
473 | * Note: ideally, we would reuse the prepared environment, but | |
474 | * the libxdiff interface does not (yet) allow for diffing only | |
475 | * ranges of lines instead of the whole files. | |
476 | */ | |
477 | mmfile_t subfile1, subfile2; | |
478 | xdfenv_t env; | |
479 | ||
480 | subfile1.ptr = (char *)diff_env->xdf1.recs[line1 - 1]->ptr; | |
481 | subfile1.size = diff_env->xdf1.recs[line1 + count1 - 2]->ptr + | |
482 | diff_env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr; | |
483 | subfile2.ptr = (char *)diff_env->xdf2.recs[line2 - 1]->ptr; | |
484 | subfile2.size = diff_env->xdf2.recs[line2 + count2 - 2]->ptr + | |
485 | diff_env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr; | |
486 | if (xdl_do_diff(&subfile1, &subfile2, xpp, &env) < 0) | |
487 | return -1; | |
488 | ||
489 | memcpy(diff_env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1); | |
490 | memcpy(diff_env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2); | |
491 | ||
492 | xdl_free_env(&env); | |
493 | ||
494 | return 0; | |
495 | } |