| 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, see |
| 17 | * <http://www.gnu.org/licenses/>. |
| 18 | * |
| 19 | * Davide Libenzi <davidel@xmailserver.org> |
| 20 | * |
| 21 | */ |
| 22 | |
| 23 | #include "xinclude.h" |
| 24 | |
| 25 | |
| 26 | #define XDL_KPDIS_RUN 4 |
| 27 | #define XDL_MAX_EQLIMIT 1024 |
| 28 | #define XDL_SIMSCAN_WINDOW 100 |
| 29 | #define XDL_GUESS_NLINES1 256 |
| 30 | #define XDL_GUESS_NLINES2 20 |
| 31 | |
| 32 | #define DISCARD 0 |
| 33 | #define KEEP 1 |
| 34 | #define INVESTIGATE 2 |
| 35 | |
| 36 | typedef struct s_xdlclass { |
| 37 | uint64_t line_hash; |
| 38 | struct s_xdlclass *next; |
| 39 | const uint8_t *ptr; |
| 40 | size_t size; |
| 41 | long idx; |
| 42 | long len1, len2; |
| 43 | } xdlclass_t; |
| 44 | |
| 45 | typedef struct s_xdlclassifier { |
| 46 | unsigned int hbits; |
| 47 | long hsize; |
| 48 | xdlclass_t **rchash; |
| 49 | chastore_t ncha; |
| 50 | xdlclass_t **rcrecs; |
| 51 | long alloc; |
| 52 | long count; |
| 53 | long flags; |
| 54 | } xdlclassifier_t; |
| 55 | |
| 56 | |
| 57 | |
| 58 | |
| 59 | static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) { |
| 60 | cf->flags = flags; |
| 61 | |
| 62 | cf->hbits = xdl_hashbits((unsigned int) size); |
| 63 | cf->hsize = 1 << cf->hbits; |
| 64 | |
| 65 | if (xdl_cha_init(&cf->ncha, sizeof(xdlclass_t), size / 4 + 1) < 0) { |
| 66 | |
| 67 | return -1; |
| 68 | } |
| 69 | if (!XDL_CALLOC_ARRAY(cf->rchash, cf->hsize)) { |
| 70 | |
| 71 | xdl_cha_free(&cf->ncha); |
| 72 | return -1; |
| 73 | } |
| 74 | |
| 75 | cf->alloc = size; |
| 76 | if (!XDL_ALLOC_ARRAY(cf->rcrecs, cf->alloc)) { |
| 77 | |
| 78 | xdl_free(cf->rchash); |
| 79 | xdl_cha_free(&cf->ncha); |
| 80 | return -1; |
| 81 | } |
| 82 | |
| 83 | cf->count = 0; |
| 84 | |
| 85 | return 0; |
| 86 | } |
| 87 | |
| 88 | |
| 89 | static void xdl_free_classifier(xdlclassifier_t *cf) { |
| 90 | |
| 91 | xdl_free(cf->rcrecs); |
| 92 | xdl_free(cf->rchash); |
| 93 | xdl_cha_free(&cf->ncha); |
| 94 | } |
| 95 | |
| 96 | |
| 97 | static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t *rec, |
| 98 | uint64_t line_hash) { |
| 99 | size_t hi; |
| 100 | xdlclass_t *rcrec; |
| 101 | |
| 102 | hi = XDL_HASHLONG(line_hash, cf->hbits); |
| 103 | for (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next) |
| 104 | if (rcrec->line_hash == line_hash && |
| 105 | xdl_recmatch((const char *)rcrec->ptr, (long)rcrec->size, |
| 106 | (const char *)rec->ptr, (long)rec->size, cf->flags)) |
| 107 | break; |
| 108 | |
| 109 | if (!rcrec) { |
| 110 | if (!(rcrec = xdl_cha_alloc(&cf->ncha))) { |
| 111 | |
| 112 | return -1; |
| 113 | } |
| 114 | rcrec->idx = cf->count++; |
| 115 | if (XDL_ALLOC_GROW(cf->rcrecs, cf->count, cf->alloc)) |
| 116 | return -1; |
| 117 | cf->rcrecs[rcrec->idx] = rcrec; |
| 118 | rcrec->line_hash = line_hash; |
| 119 | rcrec->ptr = rec->ptr; |
| 120 | rcrec->size = rec->size; |
| 121 | rcrec->len1 = rcrec->len2 = 0; |
| 122 | rcrec->next = cf->rchash[hi]; |
| 123 | cf->rchash[hi] = rcrec; |
| 124 | } |
| 125 | |
| 126 | (pass == 1) ? rcrec->len1++ : rcrec->len2++; |
| 127 | |
| 128 | rec->minimal_perfect_hash = (size_t)rcrec->idx; |
| 129 | |
| 130 | return 0; |
| 131 | } |
| 132 | |
| 133 | |
| 134 | static void xdl_free_ctx(xdfile_t *xdf) |
| 135 | { |
| 136 | xdl_free(xdf->reference_index); |
| 137 | xdl_free(xdf->changed - 1); |
| 138 | xdl_free(xdf->recs); |
| 139 | } |
| 140 | |
| 141 | |
| 142 | static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp, |
| 143 | xdlclassifier_t *cf, xdfile_t *xdf) { |
| 144 | long bsize; |
| 145 | uint64_t hav; |
| 146 | uint8_t const *blk, *cur, *top, *prev; |
| 147 | xrecord_t *crec; |
| 148 | |
| 149 | xdf->reference_index = NULL; |
| 150 | xdf->changed = NULL; |
| 151 | xdf->recs = NULL; |
| 152 | |
| 153 | if (!XDL_ALLOC_ARRAY(xdf->recs, narec)) |
| 154 | goto abort; |
| 155 | |
| 156 | xdf->nrec = 0; |
| 157 | if ((cur = blk = xdl_mmfile_first(mf, &bsize))) { |
| 158 | for (top = blk + bsize; cur < top; ) { |
| 159 | prev = cur; |
| 160 | hav = xdl_hash_record(&cur, top, xpp->flags); |
| 161 | if (XDL_ALLOC_GROW(xdf->recs, (long)xdf->nrec + 1, narec)) |
| 162 | goto abort; |
| 163 | crec = &xdf->recs[xdf->nrec++]; |
| 164 | crec->ptr = prev; |
| 165 | crec->size = cur - prev; |
| 166 | if (xdl_classify_record(pass, cf, crec, hav) < 0) |
| 167 | goto abort; |
| 168 | } |
| 169 | } |
| 170 | |
| 171 | if (!XDL_CALLOC_ARRAY(xdf->changed, xdf->nrec + 2)) |
| 172 | goto abort; |
| 173 | |
| 174 | xdf->changed += 1; |
| 175 | xdf->nreff = 0; |
| 176 | xdf->dstart = 0; |
| 177 | xdf->dend = xdf->nrec - 1; |
| 178 | |
| 179 | return 0; |
| 180 | |
| 181 | abort: |
| 182 | xdl_free_ctx(xdf); |
| 183 | return -1; |
| 184 | } |
| 185 | |
| 186 | |
| 187 | void xdl_free_env(xdfenv_t *xe) { |
| 188 | |
| 189 | xdl_free_ctx(&xe->xdf2); |
| 190 | xdl_free_ctx(&xe->xdf1); |
| 191 | } |
| 192 | |
| 193 | |
| 194 | static bool xdl_clean_mmatch(uint8_t const *action, ptrdiff_t i, ptrdiff_t len) { |
| 195 | ptrdiff_t r, rdis0, rpdis0, rdis1, rpdis1; |
| 196 | ptrdiff_t s = 0, e = len - 1; |
| 197 | |
| 198 | /* |
| 199 | * Limits the window that is examined during the similar-lines |
| 200 | * scan. The loops below stops when action[i - r] == KEEP |
| 201 | * (line that has no match), but there are corner cases where |
| 202 | * the loop proceed all the way to the extremities by causing |
| 203 | * huge performance penalties in case of big files. |
| 204 | */ |
| 205 | if (i - s > XDL_SIMSCAN_WINDOW) |
| 206 | s = i - XDL_SIMSCAN_WINDOW; |
| 207 | if (e - i > XDL_SIMSCAN_WINDOW) |
| 208 | e = i + XDL_SIMSCAN_WINDOW; |
| 209 | |
| 210 | /* |
| 211 | * Scans the lines before 'i' to find a run of lines that either |
| 212 | * have no match (action[j] == DISCARD) or have multiple matches |
| 213 | * (action[j] == INVESTIGATE). Note that we always call this |
| 214 | * function with action[i] == INVESTIGATE, so the current line |
| 215 | * (i) is already a multimatch line. |
| 216 | */ |
| 217 | for (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) { |
| 218 | if (action[i - r] == DISCARD) |
| 219 | rdis0++; |
| 220 | else if (action[i - r] == INVESTIGATE) |
| 221 | rpdis0++; |
| 222 | else if (action[i - r] == KEEP) |
| 223 | break; |
| 224 | else |
| 225 | BUG("Illegal value for action[i - r]"); |
| 226 | } |
| 227 | /* |
| 228 | * If the run before the line 'i' found only multimatch lines, |
| 229 | * we return false and hence we don't make the current line (i) |
| 230 | * discarded. We want to discard multimatch lines only when |
| 231 | * they appear in the middle of runs with nomatch lines |
| 232 | * (action[j] == DISCARD). |
| 233 | */ |
| 234 | if (rdis0 == 0) |
| 235 | return 0; |
| 236 | for (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) { |
| 237 | if (action[i + r] == DISCARD) |
| 238 | rdis1++; |
| 239 | else if (action[i + r] == INVESTIGATE) |
| 240 | rpdis1++; |
| 241 | else if (action[i + r] == KEEP) |
| 242 | break; |
| 243 | else |
| 244 | BUG("Illegal value for action[i + r]"); |
| 245 | } |
| 246 | /* |
| 247 | * If the run after the line 'i' found only multimatch lines, |
| 248 | * we return false and hence we don't make the current line (i) |
| 249 | * discarded. |
| 250 | */ |
| 251 | if (rdis1 == 0) |
| 252 | return false; |
| 253 | rdis1 += rdis0; |
| 254 | rpdis1 += rpdis0; |
| 255 | |
| 256 | return rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1); |
| 257 | } |
| 258 | |
| 259 | |
| 260 | /* |
| 261 | * Try to reduce the problem complexity, discard records that have no |
| 262 | * matches on the other file. Also, lines that have multiple matches |
| 263 | * might be potentially discarded if they appear in a run of discardable. |
| 264 | */ |
| 265 | static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) { |
| 266 | ptrdiff_t i, nm, mlim1, mlim2; |
| 267 | xdlclass_t *rcrec; |
| 268 | uint8_t *action1 = NULL, *action2 = NULL; |
| 269 | bool need_min = !!(cf->flags & XDF_NEED_MINIMAL); |
| 270 | int ret = 0; |
| 271 | ptrdiff_t off = xdf1->dstart; |
| 272 | ptrdiff_t len1 = xdf1->dend - off + 1; |
| 273 | ptrdiff_t len2 = xdf2->dend - off + 1; |
| 274 | |
| 275 | /* |
| 276 | * Create temporary arrays that will help us decide if |
| 277 | * changed[i] should remain false, or become true. |
| 278 | */ |
| 279 | if (!XDL_CALLOC_ARRAY(action1, len1) || |
| 280 | !XDL_CALLOC_ARRAY(action2, len2) || |
| 281 | !XDL_ALLOC_ARRAY(xdf1->reference_index, len1) || |
| 282 | !XDL_ALLOC_ARRAY(xdf2->reference_index, len2)) |
| 283 | { |
| 284 | ret = -1; |
| 285 | goto cleanup; |
| 286 | } |
| 287 | |
| 288 | /* |
| 289 | * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE. |
| 290 | */ |
| 291 | if (need_min) { |
| 292 | /* i.e. infinity */ |
| 293 | mlim1 = PTRDIFF_MAX; |
| 294 | } else { |
| 295 | mlim1 = xdl_bogosqrt((uint64_t)xdf1->nrec); |
| 296 | if (mlim1 > XDL_MAX_EQLIMIT) |
| 297 | mlim1 = XDL_MAX_EQLIMIT; |
| 298 | } |
| 299 | for (i = 0; i < len1; i++) { |
| 300 | size_t mph1 = xdf1->recs[i + off].minimal_perfect_hash; |
| 301 | rcrec = cf->rcrecs[mph1]; |
| 302 | nm = rcrec ? rcrec->len2 : 0; |
| 303 | if (nm == 0) |
| 304 | action1[i] = DISCARD; |
| 305 | else if (nm < mlim1) |
| 306 | action1[i] = KEEP; |
| 307 | else /* nm >= mlim1 */ |
| 308 | action1[i] = INVESTIGATE; |
| 309 | } |
| 310 | |
| 311 | if (need_min) { |
| 312 | /* i.e. infinity */ |
| 313 | mlim2 = PTRDIFF_MAX; |
| 314 | } else { |
| 315 | mlim2 = xdl_bogosqrt((uint64_t)xdf2->nrec); |
| 316 | if (mlim2 > XDL_MAX_EQLIMIT) |
| 317 | mlim2 = XDL_MAX_EQLIMIT; |
| 318 | } |
| 319 | for (i = 0; i < len2; i++) { |
| 320 | size_t mph2 = xdf2->recs[i + off].minimal_perfect_hash; |
| 321 | rcrec = cf->rcrecs[mph2]; |
| 322 | nm = rcrec ? rcrec->len1 : 0; |
| 323 | if (nm == 0) |
| 324 | action2[i] = DISCARD; |
| 325 | else if (nm < mlim2) |
| 326 | action2[i] = KEEP; |
| 327 | else /* nm >= mlim2 */ |
| 328 | action2[i] = INVESTIGATE; |
| 329 | } |
| 330 | |
| 331 | /* |
| 332 | * Use temporary arrays to decide if changed[i] should remain |
| 333 | * false, or become true. |
| 334 | */ |
| 335 | xdf1->nreff = 0; |
| 336 | for (i = 0; i < len1; i++) { |
| 337 | uint8_t action = action1[i]; |
| 338 | |
| 339 | if (action == INVESTIGATE) { |
| 340 | if (!xdl_clean_mmatch(action1, i, len1)) |
| 341 | action = KEEP; |
| 342 | else |
| 343 | action = DISCARD; |
| 344 | } |
| 345 | |
| 346 | if (action == KEEP) { |
| 347 | xdf1->reference_index[xdf1->nreff++] = i + off; |
| 348 | /* changed[i] remains false */ |
| 349 | } else if (action == DISCARD) { |
| 350 | xdf1->changed[i + off] = true; |
| 351 | } else { |
| 352 | BUG("Illegal state for action"); |
| 353 | } |
| 354 | } |
| 355 | |
| 356 | xdf2->nreff = 0; |
| 357 | for (i = 0; i < len2; i++) { |
| 358 | uint8_t action = action2[i]; |
| 359 | |
| 360 | if (action == INVESTIGATE) { |
| 361 | if (!xdl_clean_mmatch(action2, i, len2)) |
| 362 | action = KEEP; |
| 363 | else |
| 364 | action = DISCARD; |
| 365 | } |
| 366 | |
| 367 | if (action == KEEP) { |
| 368 | xdf2->reference_index[xdf2->nreff++] = i + off; |
| 369 | /* changed[i] remains false */ |
| 370 | } else if (action == DISCARD) { |
| 371 | xdf2->changed[i + off] = true; |
| 372 | } else { |
| 373 | BUG("Illegal state for action"); |
| 374 | } |
| 375 | } |
| 376 | |
| 377 | cleanup: |
| 378 | xdl_free(action1); |
| 379 | xdl_free(action2); |
| 380 | |
| 381 | return ret; |
| 382 | } |
| 383 | |
| 384 | |
| 385 | /* |
| 386 | * Early trim initial and terminal matching records. |
| 387 | */ |
| 388 | static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) { |
| 389 | long i, lim; |
| 390 | xrecord_t *recs1, *recs2; |
| 391 | |
| 392 | recs1 = xdf1->recs; |
| 393 | recs2 = xdf2->recs; |
| 394 | for (i = 0, lim = (long)XDL_MIN(xdf1->nrec, xdf2->nrec); i < lim; |
| 395 | i++, recs1++, recs2++) |
| 396 | if (recs1->minimal_perfect_hash != recs2->minimal_perfect_hash) |
| 397 | break; |
| 398 | |
| 399 | xdf1->dstart = xdf2->dstart = i; |
| 400 | |
| 401 | recs1 = xdf1->recs + xdf1->nrec - 1; |
| 402 | recs2 = xdf2->recs + xdf2->nrec - 1; |
| 403 | for (lim -= i, i = 0; i < lim; i++, recs1--, recs2--) |
| 404 | if (recs1->minimal_perfect_hash != recs2->minimal_perfect_hash) |
| 405 | break; |
| 406 | |
| 407 | xdf1->dend = (long)xdf1->nrec - i - 1; |
| 408 | xdf2->dend = (long)xdf2->nrec - i - 1; |
| 409 | |
| 410 | return 0; |
| 411 | } |
| 412 | |
| 413 | |
| 414 | static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) { |
| 415 | |
| 416 | if (xdl_trim_ends(xdf1, xdf2) < 0 || |
| 417 | xdl_cleanup_records(cf, xdf1, xdf2) < 0) { |
| 418 | |
| 419 | return -1; |
| 420 | } |
| 421 | |
| 422 | return 0; |
| 423 | } |
| 424 | |
| 425 | int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, |
| 426 | xdfenv_t *xe) { |
| 427 | long enl1, enl2, sample; |
| 428 | xdlclassifier_t cf; |
| 429 | |
| 430 | memset(&cf, 0, sizeof(cf)); |
| 431 | |
| 432 | /* |
| 433 | * For histogram diff, we can afford a smaller sample size and |
| 434 | * thus a poorer estimate of the number of lines, as the hash |
| 435 | * table (rhash) won't be filled up/grown. The number of lines |
| 436 | * (nrecs) will be updated correctly anyway by |
| 437 | * xdl_prepare_ctx(). |
| 438 | */ |
| 439 | sample = (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF |
| 440 | ? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1); |
| 441 | |
| 442 | enl1 = xdl_guess_lines(mf1, sample) + 1; |
| 443 | enl2 = xdl_guess_lines(mf2, sample) + 1; |
| 444 | |
| 445 | if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) |
| 446 | return -1; |
| 447 | |
| 448 | if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) { |
| 449 | |
| 450 | xdl_free_classifier(&cf); |
| 451 | return -1; |
| 452 | } |
| 453 | if (xdl_prepare_ctx(2, mf2, enl2, xpp, &cf, &xe->xdf2) < 0) { |
| 454 | |
| 455 | xdl_free_ctx(&xe->xdf1); |
| 456 | xdl_free_classifier(&cf); |
| 457 | return -1; |
| 458 | } |
| 459 | |
| 460 | if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) && |
| 461 | (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) && |
| 462 | xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) { |
| 463 | |
| 464 | xdl_free_ctx(&xe->xdf2); |
| 465 | xdl_free_ctx(&xe->xdf1); |
| 466 | xdl_free_classifier(&cf); |
| 467 | return -1; |
| 468 | } |
| 469 | |
| 470 | xdl_free_classifier(&cf); |
| 471 | |
| 472 | return 0; |
| 473 | } |