This source file includes following definitions.
- diag
- compareseq
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78 #define OFFSET_MAX \
79 ((((OFFSET)1 << (sizeof (OFFSET) * CHAR_BIT - 2)) - 1) * 2 + 1)
80
81
82 #ifndef EARLY_ABORT
83 # define EARLY_ABORT(ctxt) false
84 #endif
85
86 #ifndef NOTE_ORDERED
87 # define NOTE_ORDERED false
88 #endif
89
90
91
92 #ifndef IF_LINT
93 # if defined GCC_LINT || defined lint
94 # define IF_LINT(Code) Code
95 # else
96 # define IF_LINT(Code)
97 # endif
98 #endif
99
100
101
102
103 struct context
104 {
105 #ifdef ELEMENT
106
107 ELEMENT const *xvec;
108 ELEMENT const *yvec;
109 #endif
110
111
112 EXTRA_CONTEXT_FIELDS
113
114
115
116
117 OFFSET *fdiag;
118
119
120
121
122 OFFSET *bdiag;
123
124 #ifdef USE_HEURISTIC
125
126
127
128 bool heuristic;
129 #endif
130
131
132 OFFSET too_expensive;
133
134
135 #define SNAKE_LIMIT 20
136 };
137
138 struct partition
139 {
140
141 OFFSET xmid;
142 OFFSET ymid;
143
144
145 bool lo_minimal;
146
147
148 bool hi_minimal;
149 };
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179 static void
180 diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
181 struct partition *part, struct context *ctxt)
182 {
183 OFFSET *const fd = ctxt->fdiag;
184 OFFSET *const bd = ctxt->bdiag;
185 #ifdef ELEMENT
186 ELEMENT const *const xv = ctxt->xvec;
187 ELEMENT const *const yv = ctxt->yvec;
188 #define XREF_YREF_EQUAL(x,y) EQUAL (xv[x], yv[y])
189 #else
190 #define XREF_YREF_EQUAL(x,y) XVECREF_YVECREF_EQUAL (ctxt, x, y)
191 #endif
192 const OFFSET dmin = xoff - ylim;
193 const OFFSET dmax = xlim - yoff;
194 const OFFSET fmid = xoff - yoff;
195 const OFFSET bmid = xlim - ylim;
196 OFFSET fmin = fmid;
197 OFFSET fmax = fmid;
198 OFFSET bmin = bmid;
199 OFFSET bmax = bmid;
200 OFFSET c;
201 bool odd = (fmid - bmid) & 1;
202
203
204 fd[fmid] = xoff;
205 bd[bmid] = xlim;
206
207 for (c = 1;; ++c)
208 {
209 OFFSET d;
210 bool big_snake = false;
211
212
213 if (fmin > dmin)
214 fd[--fmin - 1] = -1;
215 else
216 ++fmin;
217 if (fmax < dmax)
218 fd[++fmax + 1] = -1;
219 else
220 --fmax;
221 for (d = fmax; d >= fmin; d -= 2)
222 {
223 OFFSET x;
224 OFFSET y;
225 OFFSET tlo = fd[d - 1];
226 OFFSET thi = fd[d + 1];
227 OFFSET x0 = tlo < thi ? thi : tlo + 1;
228
229 for (x = x0, y = x0 - d;
230 x < xlim && y < ylim && XREF_YREF_EQUAL (x, y);
231 x++, y++)
232 continue;
233 if (x - x0 > SNAKE_LIMIT)
234 big_snake = true;
235 fd[d] = x;
236 if (odd && bmin <= d && d <= bmax && bd[d] <= x)
237 {
238 part->xmid = x;
239 part->ymid = y;
240 part->lo_minimal = part->hi_minimal = true;
241 return;
242 }
243 }
244
245
246 if (bmin > dmin)
247 bd[--bmin - 1] = OFFSET_MAX;
248 else
249 ++bmin;
250 if (bmax < dmax)
251 bd[++bmax + 1] = OFFSET_MAX;
252 else
253 --bmax;
254 for (d = bmax; d >= bmin; d -= 2)
255 {
256 OFFSET x;
257 OFFSET y;
258 OFFSET tlo = bd[d - 1];
259 OFFSET thi = bd[d + 1];
260 OFFSET x0 = tlo < thi ? tlo : thi - 1;
261
262 for (x = x0, y = x0 - d;
263 xoff < x && yoff < y && XREF_YREF_EQUAL (x - 1, y - 1);
264 x--, y--)
265 continue;
266 if (x0 - x > SNAKE_LIMIT)
267 big_snake = true;
268 bd[d] = x;
269 if (!odd && fmin <= d && d <= fmax && x <= fd[d])
270 {
271 part->xmid = x;
272 part->ymid = y;
273 part->lo_minimal = part->hi_minimal = true;
274 return;
275 }
276 }
277
278 if (find_minimal)
279 continue;
280
281 #ifdef USE_HEURISTIC
282 bool heuristic = ctxt->heuristic;
283 #else
284 bool heuristic = false;
285 #endif
286
287
288
289
290
291
292
293
294
295 if (200 < c && big_snake && heuristic)
296 {
297 {
298 OFFSET best = 0;
299
300 for (d = fmax; d >= fmin; d -= 2)
301 {
302 OFFSET dd = d - fmid;
303 OFFSET x = fd[d];
304 OFFSET y = x - d;
305 OFFSET v = (x - xoff) * 2 - dd;
306
307 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
308 {
309 if (v > best
310 && xoff + SNAKE_LIMIT <= x && x < xlim
311 && yoff + SNAKE_LIMIT <= y && y < ylim)
312 {
313
314
315 int k;
316
317 for (k = 1; XREF_YREF_EQUAL (x - k, y - k); k++)
318 if (k == SNAKE_LIMIT)
319 {
320 best = v;
321 part->xmid = x;
322 part->ymid = y;
323 break;
324 }
325 }
326 }
327 }
328 if (best > 0)
329 {
330 part->lo_minimal = true;
331 part->hi_minimal = false;
332 return;
333 }
334 }
335
336 {
337 OFFSET best = 0;
338
339 for (d = bmax; d >= bmin; d -= 2)
340 {
341 OFFSET dd = d - bmid;
342 OFFSET x = bd[d];
343 OFFSET y = x - d;
344 OFFSET v = (xlim - x) * 2 + dd;
345
346 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
347 {
348 if (v > best
349 && xoff < x && x <= xlim - SNAKE_LIMIT
350 && yoff < y && y <= ylim - SNAKE_LIMIT)
351 {
352
353
354 int k;
355
356 for (k = 0; XREF_YREF_EQUAL (x + k, y + k); k++)
357 if (k == SNAKE_LIMIT - 1)
358 {
359 best = v;
360 part->xmid = x;
361 part->ymid = y;
362 break;
363 }
364 }
365 }
366 }
367 if (best > 0)
368 {
369 part->lo_minimal = false;
370 part->hi_minimal = true;
371 return;
372 }
373 }
374 }
375
376
377
378 if (c >= ctxt->too_expensive)
379 {
380 OFFSET fxybest;
381 OFFSET fxbest IF_LINT (= 0);
382 OFFSET bxybest;
383 OFFSET bxbest IF_LINT (= 0);
384
385
386 fxybest = -1;
387 for (d = fmax; d >= fmin; d -= 2)
388 {
389 OFFSET x = MIN (fd[d], xlim);
390 OFFSET y = x - d;
391 if (ylim < y)
392 {
393 x = ylim + d;
394 y = ylim;
395 }
396 if (fxybest < x + y)
397 {
398 fxybest = x + y;
399 fxbest = x;
400 }
401 }
402
403
404 bxybest = OFFSET_MAX;
405 for (d = bmax; d >= bmin; d -= 2)
406 {
407 OFFSET x = MAX (xoff, bd[d]);
408 OFFSET y = x - d;
409 if (y < yoff)
410 {
411 x = yoff + d;
412 y = yoff;
413 }
414 if (x + y < bxybest)
415 {
416 bxybest = x + y;
417 bxbest = x;
418 }
419 }
420
421
422 if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff))
423 {
424 part->xmid = fxbest;
425 part->ymid = fxybest - fxbest;
426 part->lo_minimal = true;
427 part->hi_minimal = false;
428 }
429 else
430 {
431 part->xmid = bxbest;
432 part->ymid = bxybest - bxbest;
433 part->lo_minimal = false;
434 part->hi_minimal = true;
435 }
436 return;
437 }
438 }
439 #undef XREF_YREF_EQUAL
440 }
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459 static bool
460 compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
461 bool find_minimal, struct context *ctxt)
462 {
463 #ifdef ELEMENT
464 ELEMENT const *xv = ctxt->xvec;
465 ELEMENT const *yv = ctxt->yvec;
466 #define XREF_YREF_EQUAL(x,y) EQUAL (xv[x], yv[y])
467 #else
468 #define XREF_YREF_EQUAL(x,y) XVECREF_YVECREF_EQUAL (ctxt, x, y)
469 #endif
470
471 while (true)
472 {
473
474 while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xoff, yoff))
475 {
476 xoff++;
477 yoff++;
478 }
479
480
481 while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xlim - 1, ylim - 1))
482 {
483 xlim--;
484 ylim--;
485 }
486
487
488 if (xoff == xlim)
489 {
490 while (yoff < ylim)
491 {
492 NOTE_INSERT (ctxt, yoff);
493 if (EARLY_ABORT (ctxt))
494 return true;
495 yoff++;
496 }
497 break;
498 }
499 if (yoff == ylim)
500 {
501 while (xoff < xlim)
502 {
503 NOTE_DELETE (ctxt, xoff);
504 if (EARLY_ABORT (ctxt))
505 return true;
506 xoff++;
507 }
508 break;
509 }
510
511 struct partition part;
512
513
514 diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
515
516
517 OFFSET xoff1, xlim1, yoff1, ylim1, xoff2, xlim2, yoff2, ylim2;
518 bool find_minimal1, find_minimal2;
519 if (!NOTE_ORDERED
520 && ((xlim + ylim) - (part.xmid + part.ymid)
521 < (part.xmid + part.ymid) - (xoff + yoff)))
522 {
523
524
525
526 xoff1 = part.xmid; xlim1 = xlim;
527 yoff1 = part.ymid; ylim1 = ylim;
528 find_minimal1 = part.hi_minimal;
529
530 xoff2 = xoff; xlim2 = part.xmid;
531 yoff2 = yoff; ylim2 = part.ymid;
532 find_minimal2 = part.lo_minimal;
533 }
534 else
535 {
536 xoff1 = xoff; xlim1 = part.xmid;
537 yoff1 = yoff; ylim1 = part.ymid;
538 find_minimal1 = part.lo_minimal;
539
540 xoff2 = part.xmid; xlim2 = xlim;
541 yoff2 = part.ymid; ylim2 = ylim;
542 find_minimal2 = part.hi_minimal;
543 }
544
545
546 bool early = compareseq (xoff1, xlim1, yoff1, ylim1, find_minimal1, ctxt);
547 if (early)
548 return early;
549
550
551 xoff = xoff2; xlim = xlim2;
552 yoff = yoff2; ylim = ylim2;
553 find_minimal = find_minimal2;
554 }
555
556 return false;
557 #undef XREF_YREF_EQUAL
558 }
559
560 #undef ELEMENT
561 #undef EQUAL
562 #undef OFFSET
563 #undef EXTRA_CONTEXT_FIELDS
564 #undef NOTE_DELETE
565 #undef NOTE_INSERT
566 #undef EARLY_ABORT
567 #undef USE_HEURISTIC
568 #undef XVECREF_YVECREF_EQUAL
569 #undef OFFSET_MAX