]>
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 | ||
125 | ||
126 | void *xdl_cha_first(chastore_t *cha) { | |
127 | chanode_t *sncur; | |
128 | ||
129 | if (!(cha->sncur = sncur = cha->head)) | |
130 | return NULL; | |
131 | ||
132 | cha->scurr = 0; | |
133 | ||
134 | return (char *) sncur + sizeof(chanode_t) + cha->scurr; | |
135 | } | |
136 | ||
137 | ||
138 | void *xdl_cha_next(chastore_t *cha) { | |
139 | chanode_t *sncur; | |
140 | ||
141 | if (!(sncur = cha->sncur)) | |
142 | return NULL; | |
143 | cha->scurr += cha->isize; | |
144 | if (cha->scurr == sncur->icurr) { | |
145 | if (!(sncur = cha->sncur = sncur->next)) | |
146 | return NULL; | |
147 | cha->scurr = 0; | |
148 | } | |
149 | ||
150 | return (char *) sncur + sizeof(chanode_t) + cha->scurr; | |
151 | } | |
152 | ||
153 | ||
86abba80 | 154 | long xdl_guess_lines(mmfile_t *mf, long sample) { |
3443546f LT |
155 | long nl = 0, size, tsize = 0; |
156 | char const *data, *cur, *top; | |
157 | ||
158 | if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) { | |
739864b1 | 159 | for (top = data + size; nl < sample && cur < top; ) { |
3443546f LT |
160 | nl++; |
161 | if (!(cur = memchr(cur, '\n', top - cur))) | |
162 | cur = top; | |
163 | else | |
164 | cur++; | |
165 | } | |
166 | tsize += (long) (cur - data); | |
167 | } | |
168 | ||
169 | if (nl && tsize) | |
170 | nl = xdl_mmfile_size(mf) / (tsize / nl); | |
171 | ||
172 | return nl + 1; | |
173 | } | |
174 | ||
0d21efa5 JS |
175 | int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags) |
176 | { | |
177 | int i1, i2; | |
178 | ||
b4cf0f17 DR |
179 | if (s1 == s2 && !memcmp(l1, l2, s1)) |
180 | return 1; | |
3b5ef0e2 | 181 | if (!(flags & XDF_WHITESPACE_FLAGS)) |
b4cf0f17 | 182 | return 0; |
3b5ef0e2 JH |
183 | |
184 | i1 = 0; | |
185 | i2 = 0; | |
186 | ||
187 | /* | |
188 | * -w matches everything that matches with -b, and -b in turn | |
189 | * matches everything that matches with --ignore-space-at-eol. | |
190 | * | |
191 | * Each flavor of ignoring needs different logic to skip whitespaces | |
192 | * while we have both sides to compare. | |
193 | */ | |
0d21efa5 | 194 | if (flags & XDF_IGNORE_WHITESPACE) { |
3b5ef0e2 JH |
195 | goto skip_ws; |
196 | while (i1 < s1 && i2 < s2) { | |
197 | if (l1[i1++] != l2[i2++]) | |
2344d47f | 198 | return 0; |
3b5ef0e2 | 199 | skip_ws: |
349362cc | 200 | while (i1 < s1 && XDL_ISSPACE(l1[i1])) |
3b5ef0e2 | 201 | i1++; |
349362cc | 202 | while (i2 < s2 && XDL_ISSPACE(l2[i2])) |
3b5ef0e2 | 203 | i2++; |
0d21efa5 | 204 | } |
0d21efa5 | 205 | } else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) { |
3b5ef0e2 | 206 | while (i1 < s1 && i2 < s2) { |
349362cc | 207 | if (XDL_ISSPACE(l1[i1]) && XDL_ISSPACE(l2[i2])) { |
3b5ef0e2 | 208 | /* Skip matching spaces and try again */ |
349362cc | 209 | while (i1 < s1 && XDL_ISSPACE(l1[i1])) |
859f9c45 | 210 | i1++; |
349362cc | 211 | while (i2 < s2 && XDL_ISSPACE(l2[i2])) |
859f9c45 | 212 | i2++; |
3b5ef0e2 | 213 | continue; |
859f9c45 | 214 | } |
3b5ef0e2 JH |
215 | if (l1[i1++] != l2[i2++]) |
216 | return 0; | |
217 | } | |
218 | } else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL) { | |
219 | while (i1 < s1 && i2 < s2 && l1[i1++] == l2[i2++]) | |
220 | ; /* keep going */ | |
221 | } | |
222 | ||
223 | /* | |
224 | * After running out of one side, the remaining side must have | |
225 | * nothing but whitespace for the lines to match. Note that | |
226 | * ignore-whitespace-at-eol case may break out of the loop | |
227 | * while there still are characters remaining on both lines. | |
228 | */ | |
229 | if (i1 < s1) { | |
349362cc | 230 | while (i1 < s1 && XDL_ISSPACE(l1[i1])) |
859f9c45 | 231 | i1++; |
3b5ef0e2 JH |
232 | if (s1 != i1) |
233 | return 0; | |
234 | } | |
235 | if (i2 < s2) { | |
349362cc | 236 | while (i2 < s2 && XDL_ISSPACE(l2[i2])) |
859f9c45 | 237 | i2++; |
3b5ef0e2 JH |
238 | return (s2 == i2); |
239 | } | |
240 | return 1; | |
0d21efa5 | 241 | } |
3443546f | 242 | |
824f782c JS |
243 | static unsigned long xdl_hash_record_with_whitespace(char const **data, |
244 | char const *top, long flags) { | |
3443546f LT |
245 | unsigned long ha = 5381; |
246 | char const *ptr = *data; | |
247 | ||
248 | for (; ptr < top && *ptr != '\n'; ptr++) { | |
349362cc | 249 | if (XDL_ISSPACE(*ptr)) { |
859f9c45 | 250 | const char *ptr2 = ptr; |
78ed710f | 251 | int at_eol; |
349362cc | 252 | while (ptr + 1 < top && XDL_ISSPACE(ptr[1]) |
2344d47f | 253 | && ptr[1] != '\n') |
0d21efa5 | 254 | ptr++; |
78ed710f | 255 | at_eol = (top <= ptr + 1 || ptr[1] == '\n'); |
6d12acef KC |
256 | if (flags & XDF_IGNORE_WHITESPACE) |
257 | ; /* already handled */ | |
258 | else if (flags & XDF_IGNORE_WHITESPACE_CHANGE | |
78ed710f | 259 | && !at_eol) { |
0d21efa5 JS |
260 | ha += (ha << 5); |
261 | ha ^= (unsigned long) ' '; | |
262 | } | |
6d12acef | 263 | else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL |
78ed710f | 264 | && !at_eol) { |
859f9c45 JS |
265 | while (ptr2 != ptr + 1) { |
266 | ha += (ha << 5); | |
267 | ha ^= (unsigned long) *ptr2; | |
268 | ptr2++; | |
269 | } | |
270 | } | |
0d21efa5 JS |
271 | continue; |
272 | } | |
3443546f LT |
273 | ha += (ha << 5); |
274 | ha ^= (unsigned long) *ptr; | |
275 | } | |
276 | *data = ptr < top ? ptr + 1: ptr; | |
277 | ||
278 | return ha; | |
279 | } | |
280 | ||
6942efcf TR |
281 | #ifdef XDL_FAST_HASH |
282 | ||
283 | #define ONEBYTES 0x0101010101010101ul | |
284 | #define NEWLINEBYTES 0x0a0a0a0a0a0a0a0aul | |
285 | #define HIGHBITS 0x8080808080808080ul | |
286 | ||
287 | /* Return the high bit set in the first byte that is a zero */ | |
288 | static inline unsigned long has_zero(unsigned long a) | |
289 | { | |
290 | return ((a - ONEBYTES) & ~a) & HIGHBITS; | |
291 | } | |
292 | ||
293 | #if __WORDSIZE == 64 | |
294 | ||
295 | /* | |
296 | * Jan Achrenius on G+: microoptimized version of | |
297 | * the simpler "(mask & ONEBYTES) * ONEBYTES >> 56" | |
298 | * that works for the bytemasks without having to | |
299 | * mask them first. | |
300 | */ | |
301 | static inline long count_masked_bytes(unsigned long mask) | |
302 | { | |
303 | return mask * 0x0001020304050608 >> 56; | |
304 | } | |
305 | ||
306 | #else /* 32-bit case */ | |
307 | ||
308 | /* Modified Carl Chatfield G+ version for 32-bit */ | |
309 | static inline long count_masked_bytes(long mask) | |
310 | { | |
311 | /* | |
312 | * (a) gives us | |
313 | * -1 (0, ff), 0 (ffff) or 1 (ffffff) | |
314 | * (b) gives us | |
315 | * 0 for 0, 1 for (ff ffff ffffff) | |
316 | * (a+b+1) gives us | |
317 | * correct 0-3 bytemask count result | |
318 | */ | |
319 | long a = (mask - 256) >> 23; | |
320 | long b = mask & 1; | |
321 | return a + b + 1; | |
322 | } | |
323 | ||
324 | #endif | |
325 | ||
326 | unsigned long xdl_hash_record(char const **data, char const *top, long flags) | |
327 | { | |
328 | unsigned long hash = 5381; | |
329 | unsigned long a = 0, mask = 0; | |
330 | char const *ptr = *data; | |
331 | char const *end = top - sizeof(unsigned long) + 1; | |
332 | ||
333 | if (flags & XDF_WHITESPACE_FLAGS) | |
334 | return xdl_hash_record_with_whitespace(data, top, flags); | |
335 | ||
336 | ptr -= sizeof(unsigned long); | |
337 | do { | |
338 | hash += hash << 5; | |
339 | hash ^= a; | |
340 | ptr += sizeof(unsigned long); | |
341 | if (ptr >= end) | |
342 | break; | |
343 | a = *(unsigned long *)ptr; | |
344 | /* Do we have any '\n' bytes in this word? */ | |
345 | mask = has_zero(a ^ NEWLINEBYTES); | |
346 | } while (!mask); | |
347 | ||
348 | if (ptr >= end) { | |
349 | /* | |
350 | * There is only a partial word left at the end of the | |
351 | * buffer. Because we may work with a memory mapping, | |
352 | * we have to grab the rest byte by byte instead of | |
353 | * blindly reading it. | |
354 | * | |
355 | * To avoid problems with masking in a signed value, | |
356 | * we use an unsigned char here. | |
357 | */ | |
358 | const char *p; | |
359 | for (p = top - 1; p >= ptr; p--) | |
360 | a = (a << 8) + *((const unsigned char *)p); | |
361 | mask = has_zero(a ^ NEWLINEBYTES); | |
362 | if (!mask) | |
363 | /* | |
364 | * No '\n' found in the partial word. Make a | |
365 | * mask that matches what we read. | |
366 | */ | |
367 | mask = 1UL << (8 * (top - ptr) + 7); | |
368 | } | |
369 | ||
370 | /* The mask *below* the first high bit set */ | |
371 | mask = (mask - 1) & ~mask; | |
372 | mask >>= 7; | |
373 | hash += hash << 5; | |
374 | hash ^= a & mask; | |
375 | ||
376 | /* Advance past the last (possibly partial) word */ | |
377 | ptr += count_masked_bytes(mask); | |
378 | ||
379 | if (ptr < top) { | |
380 | assert(*ptr == '\n'); | |
381 | ptr++; | |
382 | } | |
383 | ||
384 | *data = ptr; | |
385 | ||
386 | return hash; | |
387 | } | |
388 | ||
389 | #else /* XDL_FAST_HASH */ | |
3443546f | 390 | |
824f782c JS |
391 | unsigned long xdl_hash_record(char const **data, char const *top, long flags) { |
392 | unsigned long ha = 5381; | |
393 | char const *ptr = *data; | |
394 | ||
395 | if (flags & XDF_WHITESPACE_FLAGS) | |
396 | return xdl_hash_record_with_whitespace(data, top, flags); | |
397 | ||
398 | for (; ptr < top && *ptr != '\n'; ptr++) { | |
399 | ha += (ha << 5); | |
400 | ha ^= (unsigned long) *ptr; | |
401 | } | |
402 | *data = ptr < top ? ptr + 1: ptr; | |
403 | ||
404 | return ha; | |
405 | } | |
406 | ||
6942efcf | 407 | #endif /* XDL_FAST_HASH */ |
824f782c | 408 | |
3443546f LT |
409 | unsigned int xdl_hashbits(unsigned int size) { |
410 | unsigned int val = 1, bits = 0; | |
411 | ||
412 | for (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++); | |
413 | return bits ? bits: 1; | |
414 | } | |
415 | ||
416 | ||
417 | int xdl_num_out(char *out, long val) { | |
418 | char *ptr, *str = out; | |
419 | char buf[32]; | |
420 | ||
421 | ptr = buf + sizeof(buf) - 1; | |
422 | *ptr = '\0'; | |
423 | if (val < 0) { | |
424 | *--ptr = '-'; | |
425 | val = -val; | |
426 | } | |
427 | for (; val && ptr > buf; val /= 10) | |
428 | *--ptr = "0123456789"[val % 10]; | |
429 | if (*ptr) | |
430 | for (; *ptr; ptr++, str++) | |
431 | *str = *ptr; | |
432 | else | |
433 | *str++ = '0'; | |
434 | *str = '\0'; | |
435 | ||
436 | return str - out; | |
437 | } | |
438 | ||
439 | ||
440 | long xdl_atol(char const *str, char const **next) { | |
441 | long val, base; | |
442 | char const *top; | |
443 | ||
444 | for (top = str; XDL_ISDIGIT(*top); top++); | |
445 | if (next) | |
446 | *next = top; | |
447 | for (val = 0, base = 1, top--; top >= str; top--, base *= 10) | |
448 | val += base * (long)(*top - '0'); | |
449 | return val; | |
450 | } | |
451 | ||
452 | ||
acb72577 MW |
453 | int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, |
454 | const char *func, long funclen, xdemitcb_t *ecb) { | |
3443546f LT |
455 | int nb = 0; |
456 | mmbuffer_t mb; | |
457 | char buf[128]; | |
458 | ||
459 | memcpy(buf, "@@ -", 4); | |
460 | nb += 4; | |
461 | ||
ca557aff | 462 | nb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1); |
3443546f | 463 | |
3ce8f089 JH |
464 | if (c1 != 1) { |
465 | memcpy(buf + nb, ",", 1); | |
466 | nb += 1; | |
3443546f | 467 | |
3ce8f089 JH |
468 | nb += xdl_num_out(buf + nb, c1); |
469 | } | |
3443546f LT |
470 | |
471 | memcpy(buf + nb, " +", 2); | |
472 | nb += 2; | |
473 | ||
ca557aff | 474 | nb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1); |
3443546f | 475 | |
3ce8f089 JH |
476 | if (c2 != 1) { |
477 | memcpy(buf + nb, ",", 1); | |
478 | nb += 1; | |
3443546f | 479 | |
3ce8f089 JH |
480 | nb += xdl_num_out(buf + nb, c2); |
481 | } | |
3443546f | 482 | |
acb72577 MW |
483 | memcpy(buf + nb, " @@", 3); |
484 | nb += 3; | |
485 | if (func && funclen) { | |
486 | buf[nb++] = ' '; | |
487 | if (funclen > sizeof(buf) - nb - 1) | |
488 | funclen = sizeof(buf) - nb - 1; | |
489 | memcpy(buf + nb, func, funclen); | |
490 | nb += funclen; | |
491 | } | |
492 | buf[nb++] = '\n'; | |
3443546f LT |
493 | |
494 | mb.ptr = buf; | |
495 | mb.size = nb; | |
496 | if (ecb->outf(ecb->priv, &mb, 1) < 0) | |
497 | return -1; | |
498 | ||
499 | return 0; | |
500 | } | |
1d26b252 TRC |
501 | |
502 | int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, | |
503 | int line1, int count1, int line2, int count2) | |
504 | { | |
505 | /* | |
506 | * This probably does not work outside Git, since | |
507 | * we have a very simple mmfile structure. | |
508 | * | |
509 | * Note: ideally, we would reuse the prepared environment, but | |
510 | * the libxdiff interface does not (yet) allow for diffing only | |
511 | * ranges of lines instead of the whole files. | |
512 | */ | |
513 | mmfile_t subfile1, subfile2; | |
514 | xdfenv_t env; | |
515 | ||
516 | subfile1.ptr = (char *)diff_env->xdf1.recs[line1 - 1]->ptr; | |
517 | subfile1.size = diff_env->xdf1.recs[line1 + count1 - 2]->ptr + | |
518 | diff_env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr; | |
519 | subfile2.ptr = (char *)diff_env->xdf2.recs[line2 - 1]->ptr; | |
520 | subfile2.size = diff_env->xdf2.recs[line2 + count2 - 2]->ptr + | |
521 | diff_env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr; | |
522 | if (xdl_do_diff(&subfile1, &subfile2, xpp, &env) < 0) | |
523 | return -1; | |
524 | ||
525 | memcpy(diff_env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1); | |
526 | memcpy(diff_env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2); | |
527 | ||
528 | xdl_free_env(&env); | |
529 | ||
530 | return 0; | |
531 | } |