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