1 /* 2 * Copyright (C) 2010, Google Inc. 3 * and other copyright owners as documented in JGit's IP log. 4 * 5 * This program and the accompanying materials are made available 6 * under the terms of the Eclipse Distribution License v1.0 which 7 * accompanies this distribution, is reproduced below, and is 8 * available at http://www.eclipse.org/org/documents/edl-v10.php 9 * 10 * All rights reserved. 11 * 12 * Redistribution and use in source and binary forms, with or 13 * without modification, are permitted provided that the following 14 * conditions are met: 15 * 16 * - Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * 19 * - Redistributions in binary form must reproduce the above 20 * copyright notice, this list of conditions and the following 21 * disclaimer in the documentation and/or other materials provided 22 * with the distribution. 23 * 24 * - Neither the name of the Eclipse Foundation, Inc. nor the 25 * names of its contributors may be used to endorse or promote 26 * products derived from this software without specific prior 27 * written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 30 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, 31 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 33 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 34 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 36 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 37 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 38 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 40 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 41 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 42 */ 43 44 #include "xinclude.h" 45 #include "xtypes.h" 46 #include "xdiff.h" 47 48 #define MAX_PTR INT_MAX 49 #define MAX_CNT INT_MAX 50 51 #define LINE_END(n) (line##n + count##n - 1) 52 #define LINE_END_PTR(n) (*line##n + *count##n - 1) 53 54 struct histindex { 55 struct record { 56 unsigned int ptr, cnt; 57 struct record *next; 58 } **records, /* an occurrence */ 59 **line_map; /* map of line to record chain */ 60 chastore_t rcha; 61 unsigned int *next_ptrs; 62 unsigned int table_bits, 63 records_size, 64 line_map_size; 65 66 unsigned int max_chain_length, 67 key_shift, 68 ptr_shift; 69 70 unsigned int cnt, 71 has_common; 72 73 xdfenv_t *env; 74 xpparam_t const *xpp; 75 }; 76 77 struct region { 78 unsigned int begin1, end1; 79 unsigned int begin2, end2; 80 }; 81 82 #define LINE_MAP(i, a) (i->line_map[(a) - i->ptr_shift]) 83 84 #define NEXT_PTR(index, ptr) \ 85 (index->next_ptrs[(ptr) - index->ptr_shift]) 86 87 #define CNT(index, ptr) \ 88 ((LINE_MAP(index, ptr))->cnt) 89 90 #define REC(env, s, l) \ 91 (env->xdf##s.recs[l - 1]) 92 93 static int cmp_recs(xpparam_t const *xpp, 94 xrecord_t *r1, xrecord_t *r2) 95 { 96 return r1->ha == r2->ha && 97 xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size, 98 xpp->flags); 99 } 100 101 #define CMP_ENV(xpp, env, s1, l1, s2, l2) \ 102 (cmp_recs(xpp, REC(env, s1, l1), REC(env, s2, l2))) 103 104 #define CMP(i, s1, l1, s2, l2) \ 105 (cmp_recs(i->xpp, REC(i->env, s1, l1), REC(i->env, s2, l2))) 106 107 #define TABLE_HASH(index, side, line) \ 108 XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits) 109 110 static int scanA(struct histindex *index, int line1, int count1) 111 { 112 int ptr, tbl_idx; 113 unsigned int chain_len; 114 struct record **rec_chain, *rec; 115 116 for (ptr = LINE_END(1); line1 <= ptr; ptr--) { 117 tbl_idx = TABLE_HASH(index, 1, ptr); 118 rec_chain = index->records + tbl_idx; 119 rec = *rec_chain; 120 121 chain_len = 0; 122 while (rec) { 123 if (CMP(index, 1, rec->ptr, 1, ptr)) { 124 /* 125 * ptr is identical to another element. Insert 126 * it onto the front of the existing element 127 * chain. 128 */ 129 NEXT_PTR(index, ptr) = rec->ptr; 130 rec->ptr = ptr; 131 /* cap rec->cnt at MAX_CNT */ 132 rec->cnt = XDL_MIN(MAX_CNT, rec->cnt + 1); 133 LINE_MAP(index, ptr) = rec; 134 goto continue_scan; 135 } 136 137 rec = rec->next; 138 chain_len++; 139 } 140 141 if (chain_len == index->max_chain_length) 142 return -1; 143 144 /* 145 * This is the first time we have ever seen this particular 146 * element in the sequence. Construct a new chain for it. 147 */ 148 if (!(rec = xdl_cha_alloc(&index->rcha))) 149 return -1; 150 rec->ptr = ptr; 151 rec->cnt = 1; 152 rec->next = *rec_chain; 153 *rec_chain = rec; 154 LINE_MAP(index, ptr) = rec; 155 156 continue_scan: 157 ; /* no op */ 158 } 159 160 return 0; 161 } 162 163 static int try_lcs(struct histindex *index, struct region *lcs, int b_ptr, 164 int line1, int count1, int line2, int count2) 165 { 166 unsigned int b_next = b_ptr + 1; 167 struct record *rec = index->records[TABLE_HASH(index, 2, b_ptr)]; 168 unsigned int as, ae, bs, be, np, rc; 169 int should_break; 170 171 for (; rec; rec = rec->next) { 172 if (rec->cnt > index->cnt) { 173 if (!index->has_common) 174 index->has_common = CMP(index, 1, rec->ptr, 2, b_ptr); 175 continue; 176 } 177 178 as = rec->ptr; 179 if (!CMP(index, 1, as, 2, b_ptr)) 180 continue; 181 182 index->has_common = 1; 183 for (;;) { 184 should_break = 0; 185 np = NEXT_PTR(index, as); 186 bs = b_ptr; 187 ae = as; 188 be = bs; 189 rc = rec->cnt; 190 191 while (line1 < (int)as && line2 < (int)bs 192 && CMP(index, 1, as - 1, 2, bs - 1)) { 193 as--; 194 bs--; 195 if (1 < rc) 196 rc = XDL_MIN(rc, CNT(index, as)); 197 } 198 while ((int)ae < LINE_END(1) && (int)be < LINE_END(2) 199 && CMP(index, 1, ae + 1, 2, be + 1)) { 200 ae++; 201 be++; 202 if (1 < rc) 203 rc = XDL_MIN(rc, CNT(index, ae)); 204 } 205 206 if (b_next <= be) 207 b_next = be + 1; 208 if (lcs->end1 - lcs->begin1 < ae - as || rc < index->cnt) { 209 lcs->begin1 = as; 210 lcs->begin2 = bs; 211 lcs->end1 = ae; 212 lcs->end2 = be; 213 index->cnt = rc; 214 } 215 216 if (np == 0) 217 break; 218 219 while (np <= ae) { 220 np = NEXT_PTR(index, np); 221 if (np == 0) { 222 should_break = 1; 223 break; 224 } 225 } 226 227 if (should_break) 228 break; 229 230 as = np; 231 } 232 } 233 return b_next; 234 } 235 236 static int fall_back_to_classic_diff(xpparam_t const *xpp, xdfenv_t *env, 237 int line1, int count1, int line2, int count2) 238 { 239 xpparam_t xpparam; 240 xpparam.flags = xpp->flags & ~XDF_DIFF_ALGORITHM_MASK; 241 242 return xdl_fall_back_diff(env, &xpparam, 243 line1, count1, line2, count2); 244 } 245 246 static inline void free_index(struct histindex *index) 247 { 248 xdl_free(index->records); 249 xdl_free(index->line_map); 250 xdl_free(index->next_ptrs); 251 xdl_cha_free(&index->rcha); 252 } 253 254 static int find_lcs(xpparam_t const *xpp, xdfenv_t *env, 255 struct region *lcs, 256 int line1, int count1, int line2, int count2) 257 { 258 int b_ptr; 259 int sz, ret = -1; 260 struct histindex index; 261 262 memset(&index, 0, sizeof(index)); 263 264 index.env = env; 265 index.xpp = xpp; 266 267 index.records = NULL; 268 index.line_map = NULL; 269 /* in case of early xdl_cha_free() */ 270 index.rcha.head = NULL; 271 272 index.table_bits = xdl_hashbits(count1); 273 sz = index.records_size = 1 << index.table_bits; 274 sz *= sizeof(struct record *); 275 if (!(index.records = (struct record **) xdl_malloc(sz))) 276 goto cleanup; 277 memset(index.records, 0, sz); 278 279 sz = index.line_map_size = count1; 280 sz *= sizeof(struct record *); 281 if (!(index.line_map = (struct record **) xdl_malloc(sz))) 282 goto cleanup; 283 memset(index.line_map, 0, sz); 284 285 sz = index.line_map_size; 286 sz *= sizeof(unsigned int); 287 if (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz))) 288 goto cleanup; 289 memset(index.next_ptrs, 0, sz); 290 291 /* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */ 292 if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0) 293 goto cleanup; 294 295 index.ptr_shift = line1; 296 index.max_chain_length = 64; 297 298 if (scanA(&index, line1, count1)) 299 goto cleanup; 300 301 index.cnt = index.max_chain_length + 1; 302 303 for (b_ptr = line2; b_ptr <= LINE_END(2); ) 304 b_ptr = try_lcs(&index, lcs, b_ptr, line1, count1, line2, count2); 305 306 if (index.has_common && index.max_chain_length < index.cnt) 307 ret = 1; 308 else 309 ret = 0; 310 311 cleanup: 312 free_index(&index); 313 return ret; 314 } 315 316 static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env, 317 int line1, int count1, int line2, int count2) 318 { 319 struct region lcs; 320 int lcs_found; 321 int result; 322 redo: 323 result = -1; 324 325 if (count1 <= 0 && count2 <= 0) 326 return 0; 327 328 if (LINE_END(1) >= MAX_PTR) 329 return -1; 330 331 if (!count1) { 332 while(count2--) 333 env->xdf2.rchg[line2++ - 1] = 1; 334 return 0; 335 } else if (!count2) { 336 while(count1--) 337 env->xdf1.rchg[line1++ - 1] = 1; 338 return 0; 339 } 340 341 memset(&lcs, 0, sizeof(lcs)); 342 lcs_found = find_lcs(xpp, env, &lcs, line1, count1, line2, count2); 343 if (lcs_found < 0) 344 goto out; 345 else if (lcs_found) 346 result = fall_back_to_classic_diff(xpp, env, line1, count1, line2, count2); 347 else { 348 if (lcs.begin1 == 0 && lcs.begin2 == 0) { 349 while (count1--) 350 env->xdf1.rchg[line1++ - 1] = 1; 351 while (count2--) 352 env->xdf2.rchg[line2++ - 1] = 1; 353 result = 0; 354 } else { 355 result = histogram_diff(xpp, env, 356 line1, lcs.begin1 - line1, 357 line2, lcs.begin2 - line2); 358 if (result) 359 goto out; 360 /* 361 * result = histogram_diff(xpp, env, 362 * lcs.end1 + 1, LINE_END(1) - lcs.end1, 363 * lcs.end2 + 1, LINE_END(2) - lcs.end2); 364 * but let's optimize tail recursion ourself: 365 */ 366 count1 = LINE_END(1) - lcs.end1; 367 line1 = lcs.end1 + 1; 368 count2 = LINE_END(2) - lcs.end2; 369 line2 = lcs.end2 + 1; 370 goto redo; 371 } 372 } 373 out: 374 return result; 375 } 376 377 int xdl_do_histogram_diff(mmfile_t *file1, mmfile_t *file2, 378 xpparam_t const *xpp, xdfenv_t *env) 379 { 380 if (xdl_prepare_env(file1, file2, xpp, env) < 0) 381 return -1; 382 383 return histogram_diff(xpp, env, 384 env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1, 385 env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1); 386 } 387