1 | /* ----------------------- */ |
---|
2 | /* --- mca_rosenfeld.c --- */ |
---|
3 | /* ----------------------- */ |
---|
4 | |
---|
5 | /* |
---|
6 | * Copyright (c) 2016 Lionel Lacassagne, LIP6, UPMC, CNRS |
---|
7 | * Init : 2016/03/03 |
---|
8 | */ |
---|
9 | |
---|
10 | #include <stdio.h> |
---|
11 | #include <stdlib.h> |
---|
12 | #include <string.h> |
---|
13 | #include <math.h> |
---|
14 | #include <assert.h> |
---|
15 | #if PARMERGE |
---|
16 | #include <pthread.h> |
---|
17 | #endif |
---|
18 | |
---|
19 | #include "nrc_os_config.h" |
---|
20 | #include "config.h" |
---|
21 | #include "nrc.h" |
---|
22 | |
---|
23 | #if TARGET_OS == GIETVM |
---|
24 | #include <user_barrier.h> |
---|
25 | #include <user_lock.h> |
---|
26 | #include <giet_config.h> |
---|
27 | #else |
---|
28 | #include <stdbool.h> |
---|
29 | #endif |
---|
30 | |
---|
31 | |
---|
32 | #include "util.h" |
---|
33 | #include "ecc_common.h" |
---|
34 | #include "palette.h" |
---|
35 | #include "bmpNR.h" |
---|
36 | #include "clock.h" |
---|
37 | #include "str_ext.h" |
---|
38 | #include "ecc_features.h" |
---|
39 | |
---|
40 | // ----------- |
---|
41 | // -- local -- |
---|
42 | // ----------- |
---|
43 | |
---|
44 | #include "mca.h" |
---|
45 | |
---|
46 | extern pthread_barrier_t main_barrier; |
---|
47 | extern int display_features; |
---|
48 | |
---|
49 | CLOCK_DEC; |
---|
50 | |
---|
51 | |
---|
52 | // ----------------------------------------- |
---|
53 | static uint32 FindRoot(uint32 * T, uint32 e) |
---|
54 | // ----------------------------------------- |
---|
55 | { |
---|
56 | uint32 r; |
---|
57 | |
---|
58 | assert(e != 0); |
---|
59 | r = e; |
---|
60 | while (T[r] < r) { |
---|
61 | r = T[r]; |
---|
62 | } |
---|
63 | |
---|
64 | assert(r != 0); |
---|
65 | return r; |
---|
66 | } |
---|
67 | |
---|
68 | |
---|
69 | // ---------------------------------------------------------- |
---|
70 | static uint32 FindRoot_Dist(uint32 ** D, uint32 r, int shift) |
---|
71 | // ---------------------------------------------------------- |
---|
72 | { |
---|
73 | uint32 e; |
---|
74 | uint32 e1; |
---|
75 | uint32 e0; |
---|
76 | |
---|
77 | assert(r != 0); |
---|
78 | |
---|
79 | int mask = (1 << shift) - 1; |
---|
80 | |
---|
81 | MCA_VERBOSE3(printf("%s(%d, %d) \n", __func__, r, shift)); |
---|
82 | do { |
---|
83 | e = r; |
---|
84 | e1 = r >> shift; |
---|
85 | e0 = r & mask; |
---|
86 | r = D[e1][e0]; |
---|
87 | MCA_VERBOSE3(printf("%s: D(%d) = D[%d,%d] = %d (alpha = %d)\n", __func__, e, e1, e0, r, shift)); |
---|
88 | } while (r < e); |
---|
89 | MCA_VERBOSE3(printf("%s = %d \n\n", __func__, r)); |
---|
90 | assert(r != 0); |
---|
91 | return r; |
---|
92 | } |
---|
93 | |
---|
94 | |
---|
95 | #if !FEATURES |
---|
96 | // -------------------------------------------------------------------------------- |
---|
97 | static void SetRoot_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift) |
---|
98 | // -------------------------------------------------------------------------------- |
---|
99 | { |
---|
100 | int mask = (1 << shift) - 1; |
---|
101 | assert(root != 0 && eps != 0); |
---|
102 | |
---|
103 | uint32 r1 = root >> shift; |
---|
104 | uint32 r0 = root & mask; |
---|
105 | |
---|
106 | D[r1][r0] = eps; |
---|
107 | } |
---|
108 | #endif // !FEATURES |
---|
109 | |
---|
110 | |
---|
111 | #if FEATURES && !PARMERGE |
---|
112 | // ----------------------------------------------------------------------------------------------------------- |
---|
113 | static void SetRoot_Features_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F) |
---|
114 | // ----------------------------------------------------------------------------------------------------------- |
---|
115 | { |
---|
116 | assert(root != 0 && eps != 0); |
---|
117 | |
---|
118 | MCA_VERBOSE3(printf("F(%d) += F(%d)\n", eps, root)); |
---|
119 | |
---|
120 | int mask = (1 << shift) - 1; |
---|
121 | |
---|
122 | uint32 r1 = root >> shift; |
---|
123 | uint32 r0 = root & mask; |
---|
124 | |
---|
125 | D[r1][r0] = eps; |
---|
126 | |
---|
127 | uint32 e1 = eps >> shift; |
---|
128 | uint32 e0 = eps & mask; |
---|
129 | |
---|
130 | // version Dist de "RegionStats_Accumulate_Stats1_From_Index" |
---|
131 | |
---|
132 | // F(eps) = F(eps) U F(root) |
---|
133 | |
---|
134 | F[e1][e0].xmin = ui16min2(F[e1][e0].xmin, F[r1][r0].xmin); |
---|
135 | F[e1][e0].xmax = ui16max2(F[e1][e0].xmax, F[r1][r0].xmax); |
---|
136 | F[e1][e0].ymin = ui16min2(F[e1][e0].ymin, F[r1][r0].ymin); |
---|
137 | F[e1][e0].ymax = ui16max2(F[e1][e0].ymax, F[r1][r0].ymax); |
---|
138 | |
---|
139 | F[e1][e0].S += F[r1][r0].S; |
---|
140 | F[e1][e0].Sx += F[r1][r0].Sx; |
---|
141 | F[e1][e0].Sy += F[r1][r0].Sy; |
---|
142 | } |
---|
143 | #endif // FEATURES && !PARMERGE |
---|
144 | |
---|
145 | |
---|
146 | #if FEATURES && PARMERGE |
---|
147 | // -------------------------------------------------------------------------------------------------------------------- |
---|
148 | static bool SetRoot_Parallel_Features_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F) |
---|
149 | // -------------------------------------------------------------------------------------------------------------------- |
---|
150 | { |
---|
151 | assert(root != 0 && eps != 0); |
---|
152 | |
---|
153 | MCA_VERBOSE3(printf("F(%d) += F(%d)\n", eps, root)); |
---|
154 | |
---|
155 | int mask = (1 << shift) - 1; |
---|
156 | |
---|
157 | uint32 r1 = root >> shift; |
---|
158 | uint32 r0 = root & mask; |
---|
159 | |
---|
160 | uint32 e1 = eps >> shift; |
---|
161 | uint32 e0 = eps & mask; |
---|
162 | |
---|
163 | // Locking towards the root (first root, then eps) |
---|
164 | pthread_spin_lock(&F[r1][r0].lock); |
---|
165 | pthread_spin_lock(&F[e1][e0].lock); |
---|
166 | // FIXME: merge these conditions later, when they both appear |
---|
167 | if (D[e1][e0] != eps) { |
---|
168 | // Someone change the root of epsilon, need to find the new root |
---|
169 | printf("race cond 1\n"); |
---|
170 | pthread_spin_unlock(&F[e1][e0].lock); |
---|
171 | pthread_spin_unlock(&F[r1][r0].lock); |
---|
172 | return false; |
---|
173 | } |
---|
174 | if (D[r1][r0] != root) { |
---|
175 | // Someone change the root of "root", need to find the new root |
---|
176 | printf("race cond 2\n"); |
---|
177 | pthread_spin_unlock(&F[e1][e0].lock); |
---|
178 | pthread_spin_unlock(&F[r1][r0].lock); |
---|
179 | return false; |
---|
180 | } |
---|
181 | |
---|
182 | D[r1][r0] = eps; |
---|
183 | |
---|
184 | // F(eps) = F(eps) U F(root) |
---|
185 | F[e1][e0].xmin = ui16min2(F[e1][e0].xmin, F[r1][r0].xmin); |
---|
186 | F[e1][e0].xmax = ui16max2(F[e1][e0].xmax, F[r1][r0].xmax); |
---|
187 | F[e1][e0].ymin = ui16min2(F[e1][e0].ymin, F[r1][r0].ymin); |
---|
188 | F[e1][e0].ymax = ui16max2(F[e1][e0].ymax, F[r1][r0].ymax); |
---|
189 | |
---|
190 | F[e1][e0].S += F[r1][r0].S; |
---|
191 | F[e1][e0].Sx += F[r1][r0].Sx; |
---|
192 | F[e1][e0].Sy += F[r1][r0].Sy; |
---|
193 | |
---|
194 | pthread_spin_unlock(&F[e1][e0].lock); |
---|
195 | pthread_spin_unlock(&F[r1][r0].lock); |
---|
196 | return true; |
---|
197 | } |
---|
198 | #endif // FEATURES && PARMERGE |
---|
199 | |
---|
200 | |
---|
201 | |
---|
202 | #if FAST |
---|
203 | // -------------------------------------------------------- |
---|
204 | static uint32 QuickUnion2(uint32 * T, uint32 e1, uint32 e2) |
---|
205 | // -------------------------------------------------------- |
---|
206 | { |
---|
207 | // version QU de Union2 |
---|
208 | uint32 r1 = FindRoot(T, e1); |
---|
209 | uint32 r2 = FindRoot(T, e2); |
---|
210 | |
---|
211 | assert(e1 != 0 && e2 != 0 && r1 != 0 && r2 != 0); |
---|
212 | uint32 eps = ui32Min2(r1, r2); |
---|
213 | |
---|
214 | if (r1 > eps) { |
---|
215 | T[r1] = eps; // SetRoot sans besoin de remonter |
---|
216 | } |
---|
217 | if (r2 > eps) { |
---|
218 | T[r2] = eps; // SetRoot sans besoin de remonter |
---|
219 | } |
---|
220 | assert(e1 != 0 && e2 != 0 && r1 != 0 && r2 != 0); |
---|
221 | |
---|
222 | return eps; |
---|
223 | } |
---|
224 | #endif // FAST |
---|
225 | |
---|
226 | |
---|
227 | #if FAST |
---|
228 | // --------------------------------------------------- |
---|
229 | static uint32 use1_QU_Rosenfeld(uint32 e1, uint32 * T) |
---|
230 | // --------------------------------------------------- |
---|
231 | { |
---|
232 | return FindRoot(T, e1); |
---|
233 | } |
---|
234 | #endif // FAST |
---|
235 | |
---|
236 | |
---|
237 | #if FAST |
---|
238 | // -------------------------------------------------------------- |
---|
239 | static uint32 use2_QU_Rosenfeld(uint32 e1, uint32 e2, uint32 * T) |
---|
240 | // -------------------------------------------------------------- |
---|
241 | { |
---|
242 | return QuickUnion2(T, e1, e2); |
---|
243 | } |
---|
244 | #endif // FAST |
---|
245 | |
---|
246 | |
---|
247 | #if FAST && !FEATURES && !PARMERGE && !ARSP |
---|
248 | // --------------------------------------------------------------------------------------- |
---|
249 | static void vuse2_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha) |
---|
250 | // --------------------------------------------------------------------------------------- |
---|
251 | { |
---|
252 | uint32 rd = FindRoot_Dist(D, ed, alpha); |
---|
253 | |
---|
254 | uint32 rl = T[el]; // car le premier acces est local |
---|
255 | rl = FindRoot_Dist(D, rl, alpha); |
---|
256 | |
---|
257 | assert(ed != 0 && el != 0 && rd != 0 && rl != 0); |
---|
258 | if (rd == rl) { |
---|
259 | return; // evite la backdoor |
---|
260 | } |
---|
261 | |
---|
262 | // forcement positifs car appel depuis optimizedBorder |
---|
263 | // qui a fait un test |
---|
264 | if (rd < rl) { |
---|
265 | SetRoot_Rosenfeld_Dist(D, rl, rd, alpha); |
---|
266 | } |
---|
267 | else { |
---|
268 | SetRoot_Rosenfeld_Dist(D, rd, rl, alpha); |
---|
269 | } |
---|
270 | } |
---|
271 | |
---|
272 | // FAST && !FEATURES && !PARMERGE && !ARSP |
---|
273 | |
---|
274 | // ----------------------------------------------------------------------------------------------------- |
---|
275 | static void vuse3_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha) |
---|
276 | // ----------------------------------------------------------------------------------------------------- |
---|
277 | { |
---|
278 | uint32 r1 = FindRoot_Dist(D, ed1, alpha); |
---|
279 | uint32 r2 = FindRoot_Dist(D, ed2, alpha); |
---|
280 | |
---|
281 | uint32 r3 = T[el3]; // local - distant |
---|
282 | r3 = FindRoot_Dist(D, r3, alpha); |
---|
283 | |
---|
284 | assert(ed1 != 0 && ed2 != 0 && el3 != 0 && r1 != 0 && r2 != 0 && r3 != 0); |
---|
285 | |
---|
286 | if (r1 == r2 && r2 == r3) { |
---|
287 | return; |
---|
288 | } |
---|
289 | |
---|
290 | uint32 eps = ui32Min3(r1, r2, r3); // forcement positifs car appel depuis optimizedBorder qui a fait un test |
---|
291 | |
---|
292 | // On ne fait pas le test car on peut faire le SetRoot plusieurs fois sur le même élément (on n'accumule pas de stats) |
---|
293 | if (r1 > eps) { |
---|
294 | SetRoot_Rosenfeld_Dist(D, r1, eps, alpha); |
---|
295 | } |
---|
296 | if (r2 > eps) { |
---|
297 | SetRoot_Rosenfeld_Dist(D, r2, eps, alpha); |
---|
298 | } |
---|
299 | if (r3 > eps) { |
---|
300 | SetRoot_Rosenfeld_Dist(D, r3, eps, alpha); |
---|
301 | } |
---|
302 | } |
---|
303 | #endif // FAST && !FEATURES && !PARMERGE && !ARSP |
---|
304 | |
---|
305 | |
---|
306 | #if FAST && FEATURES && !PARMERGE && !ARSP |
---|
307 | // ------------------------------------------------------------------------------------------------------------------ |
---|
308 | static void vuse2_Features_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
309 | // ------------------------------------------------------------------------------------------------------------------ |
---|
310 | { |
---|
311 | assert(ed != 0 && el != 0); |
---|
312 | |
---|
313 | uint32 rd = FindRoot_Dist(D, ed, alpha); |
---|
314 | |
---|
315 | uint32 rl = T[el]; // car le premier acces est local |
---|
316 | assert(rl != 0); |
---|
317 | rl = FindRoot_Dist(D, rl, alpha); |
---|
318 | |
---|
319 | assert(rd != 0 && rl != 0); |
---|
320 | |
---|
321 | if (rd == rl) { |
---|
322 | return; // evite la backdoor |
---|
323 | } |
---|
324 | |
---|
325 | // forcement positifs car appel depuis optimizedBorder |
---|
326 | // qui a fait un test |
---|
327 | if (rd < rl) { |
---|
328 | SetRoot_Features_Rosenfeld_Dist(D, rl, rd, alpha, F); |
---|
329 | } |
---|
330 | else { |
---|
331 | SetRoot_Features_Rosenfeld_Dist(D, rd, rl, alpha, F); |
---|
332 | } |
---|
333 | } |
---|
334 | |
---|
335 | // FAST && FEATURES && !PARMERGE && !ARSP |
---|
336 | |
---|
337 | // -------------------------------------------------------------------------------------------------------------------------------- |
---|
338 | static void vuse3_Features_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
339 | // -------------------------------------------------------------------------------------------------------------------------------- |
---|
340 | { |
---|
341 | assert(ed1 != 0 && ed2 != 0 && el3 != 0); |
---|
342 | |
---|
343 | uint32 r1 = FindRoot_Dist(D, ed1, alpha); |
---|
344 | uint32 r2 = FindRoot_Dist(D, ed2, alpha); |
---|
345 | |
---|
346 | uint32 r3 = T[el3]; // local - distant |
---|
347 | assert(r3 != 0); |
---|
348 | r3 = FindRoot_Dist(D, r3, alpha); |
---|
349 | |
---|
350 | assert(r1 != 0 && r2 != 0 && r3 != 0); |
---|
351 | |
---|
352 | if (r1 == r2 && r2 == r3) { |
---|
353 | return; |
---|
354 | } |
---|
355 | |
---|
356 | uint32 eps = ui32Min3(r1, r2, r3); // forcement positifs car appel depuis optimizedBorder qui a fait un test |
---|
357 | |
---|
358 | if (r1 > eps) { |
---|
359 | SetRoot_Features_Rosenfeld_Dist(D, r1, eps, alpha, F); |
---|
360 | } |
---|
361 | if (r2 > eps && r2 != r1) { |
---|
362 | SetRoot_Features_Rosenfeld_Dist(D, r2, eps, alpha, F); |
---|
363 | } |
---|
364 | if (r3 > eps && r3 != r2 && r3 != r1) { |
---|
365 | SetRoot_Features_Rosenfeld_Dist(D, r3, eps, alpha, F); |
---|
366 | } |
---|
367 | } |
---|
368 | #endif // FAST && FEATURES && !PARMERGE && !ARSP |
---|
369 | |
---|
370 | |
---|
371 | #if FAST && !FEATURES && PARMERGE && ARSP |
---|
372 | // ---------------------------------------------------------------------------------------------------------------- |
---|
373 | static bool SetRoot_Parallel_Arsp_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F) |
---|
374 | // ---------------------------------------------------------------------------------------------------------------- |
---|
375 | { |
---|
376 | assert(root != 0 && eps != 0); |
---|
377 | |
---|
378 | MCA_VERBOSE3(printf("F(%d) += F(%d)\n", eps, root)); |
---|
379 | |
---|
380 | uint32_t mask = (1 << shift) - 1; |
---|
381 | |
---|
382 | uint32_t r1 = root >> shift; |
---|
383 | uint32_t r0 = root & mask; |
---|
384 | |
---|
385 | pthread_spin_lock(&F[r1][r0].lock); |
---|
386 | if (D[r1][r0] != root) { |
---|
387 | pthread_spin_unlock(&F[r1][r0].lock); |
---|
388 | return false; |
---|
389 | } |
---|
390 | |
---|
391 | D[r1][r0] = eps; |
---|
392 | |
---|
393 | pthread_spin_unlock(&F[r1][r0].lock); |
---|
394 | return true; |
---|
395 | } |
---|
396 | |
---|
397 | // FAST && !FEATURES && PARMERGE && ARSP |
---|
398 | |
---|
399 | // ------------------------------------------------------------------------------------------------------------------------------ |
---|
400 | static inline bool FindSmallerAncestor_Link(uint32 ** D, uint32_t rl, uint32_t el, uint32_t rd, uint32_t shift, RegionStats ** F) |
---|
401 | // ------------------------------------------------------------------------------------------------------------------------------ |
---|
402 | { |
---|
403 | bool ok; |
---|
404 | uint32_t el1, el0; |
---|
405 | uint32_t mask = (1 << shift) - 1; |
---|
406 | while (rl < el && rl > rd) { |
---|
407 | el = rl; |
---|
408 | el1 = rl >> shift; |
---|
409 | el0 = rl & mask; |
---|
410 | rl = D[el1][el0]; |
---|
411 | } |
---|
412 | if (rd != rl) { |
---|
413 | if (rl == el && rl > rd) { |
---|
414 | // L'ordre s'est inversé : on fait pointer rl vers rd |
---|
415 | ok = SetRoot_Parallel_Arsp_Rosenfeld_Dist(D, rl, rd, shift, F); |
---|
416 | } |
---|
417 | else { |
---|
418 | // On fait pointer rd vers rl |
---|
419 | ok = SetRoot_Parallel_Arsp_Rosenfeld_Dist(D, rd, rl, shift, F); |
---|
420 | } |
---|
421 | } |
---|
422 | else { |
---|
423 | ok = true; |
---|
424 | } |
---|
425 | return ok; |
---|
426 | } |
---|
427 | |
---|
428 | // FAST && !FEATURES && PARMERGE && ARSP |
---|
429 | |
---|
430 | // ----------------------------------------------------------------------------------------------------------------------- |
---|
431 | static void vuse2_Parallel_Arsp_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
432 | // ----------------------------------------------------------------------------------------------------------------------- |
---|
433 | { |
---|
434 | assert(ed != 0 && el != 0); |
---|
435 | |
---|
436 | uint32_t shift = alpha; |
---|
437 | uint32_t mask = (1 << shift) - 1; |
---|
438 | |
---|
439 | uint32_t rd = ed; |
---|
440 | uint32_t rl = el; |
---|
441 | |
---|
442 | uint32_t ed1; |
---|
443 | uint32_t el1; |
---|
444 | uint32_t ed0; |
---|
445 | uint32_t el0; |
---|
446 | |
---|
447 | bool ok; |
---|
448 | |
---|
449 | // Fusion ed - el |
---|
450 | do { |
---|
451 | do { |
---|
452 | ed = rd; |
---|
453 | el = rl; |
---|
454 | ed1 = rd >> shift; |
---|
455 | el1 = rl >> shift; |
---|
456 | ed0 = rd & mask; |
---|
457 | el0 = rl & mask; |
---|
458 | rd = D[ed1][ed0]; |
---|
459 | rl = D[el1][el0]; |
---|
460 | } while (rl < el && rd < ed); |
---|
461 | |
---|
462 | assert(rl != 0 && rd != 0); |
---|
463 | |
---|
464 | if (rd != rl) { |
---|
465 | if (rd == ed) { |
---|
466 | ok = FindSmallerAncestor_Link(D, rl, el, rd, shift, F); |
---|
467 | } |
---|
468 | else { |
---|
469 | assert(rl == el); |
---|
470 | ok = FindSmallerAncestor_Link(D, rd, ed, rl, shift, F); |
---|
471 | } |
---|
472 | } |
---|
473 | else { |
---|
474 | ok = true; |
---|
475 | } |
---|
476 | } while (!ok); |
---|
477 | } |
---|
478 | |
---|
479 | // FAST && !FEATURES && PARMERGE && ARSP |
---|
480 | |
---|
481 | // ------------------------------------------------------------------------------------------------------------------------------------- |
---|
482 | static void vuse3_Parallel_Arsp_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
483 | // ------------------------------------------------------------------------------------------------------------------------------------- |
---|
484 | { |
---|
485 | assert(ed1 != 0 && ed2 != 0 && el3 != 0); |
---|
486 | |
---|
487 | uint32_t shift = alpha; |
---|
488 | uint32_t mask = (1 << shift) - 1; |
---|
489 | |
---|
490 | uint32_t r1 = ed1; |
---|
491 | uint32_t r2 = ed2; |
---|
492 | uint32_t r3 = el3; |
---|
493 | |
---|
494 | uint32_t e11; |
---|
495 | uint32_t e21; |
---|
496 | uint32_t e31; |
---|
497 | uint32_t e10; |
---|
498 | uint32_t e20; |
---|
499 | uint32_t e30; |
---|
500 | |
---|
501 | uint32_t r0; |
---|
502 | uint32_t ed0; |
---|
503 | uint32_t e00; |
---|
504 | uint32_t e01; |
---|
505 | |
---|
506 | // Pas d'init pour que valgrind détecte une erreur si bool est lu sans être affecté |
---|
507 | bool ok; |
---|
508 | |
---|
509 | // Fusion ed1 - ed2 |
---|
510 | do { |
---|
511 | do { |
---|
512 | ed1 = r1; |
---|
513 | ed2 = r2; |
---|
514 | e11 = r1 >> shift; |
---|
515 | e21 = r2 >> shift; |
---|
516 | e10 = r1 & mask; |
---|
517 | e20 = r2 & mask; |
---|
518 | r1 = D[e11][e10]; |
---|
519 | r2 = D[e21][e20]; |
---|
520 | } while (r1 < ed1 && r2 < ed2); |
---|
521 | |
---|
522 | assert(r1 != 0 && r2 != 0); |
---|
523 | |
---|
524 | if (r1 != r2) { |
---|
525 | if (r1 == ed1) { |
---|
526 | ok = FindSmallerAncestor_Link(D, r2, ed2, r1, shift, F); |
---|
527 | } |
---|
528 | else { |
---|
529 | assert(r2 == ed2); |
---|
530 | ok = FindSmallerAncestor_Link(D, r1, ed1, r2, shift, F); |
---|
531 | } |
---|
532 | } |
---|
533 | else { |
---|
534 | ok = true; |
---|
535 | } |
---|
536 | } while (!ok); |
---|
537 | |
---|
538 | // Fusion r0 = min(r1, r2) avec r3 |
---|
539 | if (r1 < r2) { |
---|
540 | r0 = r1; |
---|
541 | ed0 = r1; |
---|
542 | e00 = e10; |
---|
543 | e01 = e11; |
---|
544 | } |
---|
545 | else { |
---|
546 | r0 = r2; |
---|
547 | ed0 = r2; |
---|
548 | e00 = e20; |
---|
549 | e01 = e21; |
---|
550 | } |
---|
551 | |
---|
552 | // r0 est déjà une racine |
---|
553 | goto r0_is_root; |
---|
554 | do { |
---|
555 | do { |
---|
556 | ed0 = r0; |
---|
557 | el3 = r3; |
---|
558 | e01 = r0 >> shift; |
---|
559 | e31 = r3 >> shift; |
---|
560 | e00 = r0 & mask; |
---|
561 | e30 = r3 & mask; |
---|
562 | r0 = D[e01][e00]; |
---|
563 | r3 = D[e31][e30]; |
---|
564 | } while (r0 < ed0 && r3 < el3); |
---|
565 | |
---|
566 | assert(r0 != 0 && r3 != 0); |
---|
567 | |
---|
568 | if (r0 != r3) { |
---|
569 | if (r0 == ed0) { |
---|
570 | r0_is_root: |
---|
571 | ok = FindSmallerAncestor_Link(D, r3, el3, r0, shift, F); |
---|
572 | } |
---|
573 | else { |
---|
574 | assert(r3 == el3); |
---|
575 | ok = FindSmallerAncestor_Link(D, r0, ed0, r3, shift, F); |
---|
576 | } |
---|
577 | } |
---|
578 | else { |
---|
579 | ok = true; |
---|
580 | } |
---|
581 | } while (!ok); |
---|
582 | } |
---|
583 | #endif // FAST && !FEATURES && PARMERGE && ARSP |
---|
584 | |
---|
585 | |
---|
586 | |
---|
587 | #if FAST && FEATURES && PARMERGE && !ARSP |
---|
588 | // --------------------------------------------------------------------------------------------------------------------------- |
---|
589 | static void vuse2_Parallel_Features_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
590 | // --------------------------------------------------------------------------------------------------------------------------- |
---|
591 | { |
---|
592 | bool ok; |
---|
593 | assert(ed != 0 && el != 0); |
---|
594 | uint32 rl = T[el]; // car le premier acces est local |
---|
595 | assert(rl != 0); |
---|
596 | |
---|
597 | uint32 rd; |
---|
598 | |
---|
599 | do { |
---|
600 | rd = FindRoot_Dist(D, ed, alpha); // no lock |
---|
601 | rl = FindRoot_Dist(D, rl, alpha); |
---|
602 | |
---|
603 | assert(rd != 0 && rl != 0); |
---|
604 | |
---|
605 | if (rd == rl) { |
---|
606 | return; // evite la backdoor |
---|
607 | } |
---|
608 | |
---|
609 | // forcement positifs car appel depuis optimizedBorder |
---|
610 | // qui a fait un test |
---|
611 | if (rd < rl) { |
---|
612 | ok = SetRoot_Parallel_Features_Rosenfeld_Dist(D, rl, rd, alpha, F); |
---|
613 | } |
---|
614 | else { |
---|
615 | ok = SetRoot_Parallel_Features_Rosenfeld_Dist(D, rd, rl, alpha, F); |
---|
616 | } |
---|
617 | } while (!ok); |
---|
618 | } |
---|
619 | |
---|
620 | // FAST && FEATURES && PARMERGE && !ARSP |
---|
621 | |
---|
622 | // ----------------------------------------------------------------------------------------------------------------------------------------- |
---|
623 | static void vuse3_Parallel_Features_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
624 | // ----------------------------------------------------------------------------------------------------------------------------------------- |
---|
625 | { |
---|
626 | bool ok1, ok2, ok3; |
---|
627 | assert(ed1 != 0 && ed2 != 0 && el3 != 0); |
---|
628 | |
---|
629 | uint32 r1; |
---|
630 | uint32 r2; |
---|
631 | uint32 r3 = T[el3]; // local - distant |
---|
632 | assert(r3 != 0); |
---|
633 | |
---|
634 | do { |
---|
635 | r1 = FindRoot_Dist(D, ed1, alpha); |
---|
636 | r2 = FindRoot_Dist(D, ed2, alpha); |
---|
637 | r3 = FindRoot_Dist(D, r3, alpha); |
---|
638 | |
---|
639 | assert(r1 != 0 && r2 != 0 && r3 != 0); |
---|
640 | |
---|
641 | if (r1 == r2 && r2 == r3) { |
---|
642 | return; |
---|
643 | } |
---|
644 | |
---|
645 | uint32 eps = ui32Min3(r1, r2, r3); // forcement positifs car appel depuis optimizedBorder qui a fait un test |
---|
646 | |
---|
647 | ok1 = true; |
---|
648 | ok2 = true; |
---|
649 | ok3 = true; |
---|
650 | if (r1 > eps) { |
---|
651 | ok1 = SetRoot_Parallel_Features_Rosenfeld_Dist(D, r1, eps, alpha, F); |
---|
652 | } |
---|
653 | if (r2 > eps && r2 != r1) { |
---|
654 | ok2 = SetRoot_Parallel_Features_Rosenfeld_Dist(D, r2, eps, alpha, F); |
---|
655 | } |
---|
656 | if (r3 > eps && r3 != r2 && r3 != r1) { |
---|
657 | ok3 = SetRoot_Parallel_Features_Rosenfeld_Dist(D, r3, eps, alpha, F); |
---|
658 | } |
---|
659 | } while (!(ok1 && ok2 && ok3)); |
---|
660 | } |
---|
661 | #endif // FAST && FEATURES && PARMERGE && !ARSP |
---|
662 | |
---|
663 | |
---|
664 | |
---|
665 | #if FAST |
---|
666 | // ------------------------------------------------------------------------------------------------------------------------ |
---|
667 | static void optimizedBorder_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
668 | // ------------------------------------------------------------------------------------------------------------------------ |
---|
669 | { |
---|
670 | uint32 a, b, c, x; |
---|
671 | |
---|
672 | x = E[i][j]; |
---|
673 | if (x) { |
---|
674 | b = E[i - 1][j]; |
---|
675 | if (b) { |
---|
676 | vuse2_Rosenfeld(b, x, T, D, alpha, F); // dist, local |
---|
677 | } |
---|
678 | else { |
---|
679 | c = E[i - 1][j + 1]; |
---|
680 | if (c) { |
---|
681 | a = E[i - 1][j - 1]; |
---|
682 | if (a) { |
---|
683 | vuse3_Rosenfeld(a, c, x, T, D, alpha, F); // dist, local |
---|
684 | } |
---|
685 | else { |
---|
686 | vuse2_Rosenfeld(c, x, T, D, alpha, F); // dist, local |
---|
687 | } |
---|
688 | } |
---|
689 | else { |
---|
690 | a = E[i - 1][j - 1]; |
---|
691 | if (a) { |
---|
692 | vuse2_Rosenfeld(a, x, T, D, alpha, F); // dist, local |
---|
693 | } |
---|
694 | } |
---|
695 | } |
---|
696 | } |
---|
697 | } |
---|
698 | |
---|
699 | // FAST |
---|
700 | |
---|
701 | // ---------------------------------------------------------------------------------------------------------------------------- |
---|
702 | static void optimizedBorderLeft_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
703 | // ---------------------------------------------------------------------------------------------------------------------------- |
---|
704 | { |
---|
705 | uint32 x = E[i][j]; |
---|
706 | if (x) { |
---|
707 | uint32 b = E[i - 1][j]; |
---|
708 | if (b) { |
---|
709 | vuse2_Rosenfeld(b, x, T, D, alpha, F); // dist, local |
---|
710 | } |
---|
711 | else { |
---|
712 | uint32 c = E[i - 1][j + 1]; |
---|
713 | if (c) { |
---|
714 | vuse2_Rosenfeld(c, x, T, D, alpha, F); // dist, local |
---|
715 | } |
---|
716 | } |
---|
717 | } |
---|
718 | } |
---|
719 | |
---|
720 | // FAST |
---|
721 | |
---|
722 | // ----------------------------------------------------------------------------------------------------------------------------- |
---|
723 | static void optimizedBorderRight_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
724 | // ----------------------------------------------------------------------------------------------------------------------------- |
---|
725 | { |
---|
726 | // copie de optimizedBorder_Rosenfeld |
---|
727 | // test d'existance de ex en local local |
---|
728 | |
---|
729 | uint32 b = E[i - 1][j]; |
---|
730 | uint32 x = E[i][j]; |
---|
731 | |
---|
732 | if (x) { |
---|
733 | if (b) { |
---|
734 | vuse2_Rosenfeld(b, x, T, D, alpha, F); // dist, local |
---|
735 | } |
---|
736 | else { |
---|
737 | uint32 a = E[i - 1][j - 1]; |
---|
738 | if (a) { |
---|
739 | vuse2_Rosenfeld(a, x, T, D, alpha, F); // dist, local |
---|
740 | } |
---|
741 | } |
---|
742 | } |
---|
743 | } |
---|
744 | |
---|
745 | // FAST |
---|
746 | |
---|
747 | // ------------------------------------------------------------------------------------------------------------------------------------------- |
---|
748 | static void borderMerging_Fast_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
749 | // ------------------------------------------------------------------------------------------------------------------------------------------- |
---|
750 | { |
---|
751 | // Prologue |
---|
752 | optimizedBorderLeft_Rosenfeld_Dist(E, i, 0, T, D, alpha, F); |
---|
753 | // Boucle principale |
---|
754 | for (int j = 1; j < width - 1; j++) { |
---|
755 | optimizedBorder_Rosenfeld_Dist(E, i, j, T, D, alpha, F); |
---|
756 | } |
---|
757 | // Epilogue |
---|
758 | optimizedBorderRight_Rosenfeld_Dist(E, i, width - 1, T, D, alpha, F); |
---|
759 | } |
---|
760 | #endif // FAST |
---|
761 | |
---|
762 | |
---|
763 | |
---|
764 | #if SLOW |
---|
765 | // ------------------------------------------------------------------------------------------------------------------------------------------- |
---|
766 | static void borderMerging_Slow_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
767 | // ------------------------------------------------------------------------------------------------------------------------------------------- |
---|
768 | { |
---|
769 | int j = 0; |
---|
770 | |
---|
771 | uint32 eps; |
---|
772 | uint32 e1, e2, e3, ex; |
---|
773 | uint32 r1, r2, r3, rx; |
---|
774 | |
---|
775 | // -------------- |
---|
776 | // -- prologue -- |
---|
777 | // -------------- |
---|
778 | MCA_VERBOSE3(printf("[%s] i = %d\n", __func__, i)); |
---|
779 | |
---|
780 | ex = E[i][j]; |
---|
781 | |
---|
782 | if (ex) { |
---|
783 | |
---|
784 | MCA_VERBOSE3(printf("[%s] j = %d\n", __func__, j)); |
---|
785 | |
---|
786 | e2 = E[i - 1][j]; |
---|
787 | e3 = E[i - 1][j + 1]; |
---|
788 | |
---|
789 | if (e2 || e3) { |
---|
790 | |
---|
791 | // test pour eviter acces distant |
---|
792 | r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0; |
---|
793 | r3 = e3 ? FindRoot_Dist(D, e3, alpha) : 0; |
---|
794 | |
---|
795 | rx = T[ex]; |
---|
796 | rx = FindRoot_Dist(D, rx, alpha); |
---|
797 | |
---|
798 | eps = ui32MinNonNul3(r2, r3, rx); |
---|
799 | |
---|
800 | MCA_VERBOSE3(printf("\n")); |
---|
801 | MCA_VERBOSE3(printf("e2 = %5d -> r2 = %5d\n", e2, r2)); |
---|
802 | MCA_VERBOSE3(printf("e3 = %5d -> r3 = %5d\n", e3, r3)); |
---|
803 | MCA_VERBOSE3(printf("ex = %5d -> rx = %5d\n", ex, rx)); |
---|
804 | MCA_VERBOSE3(printf("eps = %5d\n", eps)); |
---|
805 | |
---|
806 | // Quick-Union |
---|
807 | if (r2 > eps) { |
---|
808 | SetRoot_Rosenfeld(D, r2, eps, alpha, F); |
---|
809 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r2, eps)); |
---|
810 | } |
---|
811 | // Pour le cas où r2 == r3, il ne faut pas ajouter deux fois les features |
---|
812 | //if (r3 > 0) { |
---|
813 | // r3 = FindRoot_Dist(D, r3, alpha); |
---|
814 | //} |
---|
815 | //if (r3 > eps) { |
---|
816 | if (r3 > eps && r3 != r2) { |
---|
817 | SetRoot_Rosenfeld(D, r3, eps, alpha, F); |
---|
818 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r3, eps)); |
---|
819 | } |
---|
820 | //rx = FindRoot_Dist(D, rx, alpha); |
---|
821 | //if (rx > eps) { |
---|
822 | if (rx > eps && rx != r3 && rx != r2) { |
---|
823 | SetRoot_Rosenfeld(D, rx, eps, alpha, F); |
---|
824 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", rx, eps)); |
---|
825 | } |
---|
826 | MCA_VERBOSE3(printf("---------------------------\n")); |
---|
827 | } |
---|
828 | } |
---|
829 | |
---|
830 | // ----------------------- |
---|
831 | // -- boucle principale -- |
---|
832 | // ----------------------- |
---|
833 | |
---|
834 | for (j = 0 + 1; j < width - 1; j++) { |
---|
835 | |
---|
836 | ex = E[i][j]; |
---|
837 | |
---|
838 | if (ex) { |
---|
839 | |
---|
840 | MCA_VERBOSE3(printf("[%s] j = %d\n", __func__, j)); |
---|
841 | |
---|
842 | e1 = E[i - 1][j - 1]; |
---|
843 | e2 = E[i - 1][j]; |
---|
844 | e3 = E[i - 1][j + 1]; |
---|
845 | |
---|
846 | if (e1 || e2 || e3) { |
---|
847 | // test pour eviter un acces distant |
---|
848 | r1 = e1 ? FindRoot_Dist(D, e1, alpha) : 0; |
---|
849 | r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0; |
---|
850 | r3 = e3 ? FindRoot_Dist(D, e3, alpha) : 0; |
---|
851 | |
---|
852 | rx = T[ex]; |
---|
853 | rx = FindRoot_Dist(D, rx, alpha); |
---|
854 | |
---|
855 | eps = ui32MinNonNul4(r1, r2, r3, rx); |
---|
856 | |
---|
857 | MCA_VERBOSE3(printf("\n")); |
---|
858 | MCA_VERBOSE3(printf("e1 = %5d -> r1 = %5d\n", e1, r1)); |
---|
859 | MCA_VERBOSE3(printf("e2 = %5d -> r2 = %5d\n", e2, r2)); |
---|
860 | MCA_VERBOSE3(printf("e3 = %5d -> r3 = %5d\n", e3, r3)); |
---|
861 | MCA_VERBOSE3(printf("ex = %5d -> rx = %5d\n", ex, rx)); |
---|
862 | MCA_VERBOSE3(printf("eps = %5d\n", eps)); |
---|
863 | |
---|
864 | |
---|
865 | // Quick-Union |
---|
866 | if (r1 > eps) { |
---|
867 | SetRoot_Rosenfeld(D, r1, eps, alpha, F); |
---|
868 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r1, eps)); |
---|
869 | } |
---|
870 | //if (r2 > 0) { |
---|
871 | // r2 = FindRoot_Dist(D, r2, alpha); |
---|
872 | //} |
---|
873 | if (r2 > eps && r2 != r1) { |
---|
874 | //if (r2 > eps) { |
---|
875 | SetRoot_Rosenfeld(D, r2, eps, alpha, F); |
---|
876 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r2, eps)); |
---|
877 | } |
---|
878 | //if (r3 > 0) { |
---|
879 | // r3 = FindRoot_Dist(D, r3, alpha); |
---|
880 | //} |
---|
881 | if (r3 > eps && r3 != r2 && r3 != r1) { |
---|
882 | //if (r3 > eps) { |
---|
883 | SetRoot_Rosenfeld(D, r3, eps, alpha, F); |
---|
884 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r3, eps)); |
---|
885 | } |
---|
886 | //rx = FindRoot_Dist(D, rx, alpha); |
---|
887 | if (rx > eps && rx != r3 && rx != r2 && rx != r1) { |
---|
888 | //if (rx > eps) { |
---|
889 | SetRoot_Rosenfeld(D, rx, eps, alpha, F); |
---|
890 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", rx, eps)); |
---|
891 | } |
---|
892 | MCA_VERBOSE3(puts("---------------------------\n")); |
---|
893 | } |
---|
894 | } |
---|
895 | } |
---|
896 | |
---|
897 | // -------------- |
---|
898 | // -- epilogue -- |
---|
899 | // -------------- |
---|
900 | |
---|
901 | j = width - 1; |
---|
902 | ex = E[i][j]; |
---|
903 | |
---|
904 | if (ex) { |
---|
905 | |
---|
906 | MCA_VERBOSE3(printf("[%s] j = %d\n", __func__, j)); |
---|
907 | |
---|
908 | e1 = E[i - 1][j - 1]; |
---|
909 | e2 = E[i - 1][j]; |
---|
910 | |
---|
911 | if (e1 || e2) { |
---|
912 | |
---|
913 | // test pour eviter acces distant |
---|
914 | r1 = e1 ? FindRoot_Dist(D, e1, alpha) : 0; |
---|
915 | r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0; |
---|
916 | |
---|
917 | rx = T[ex]; |
---|
918 | rx = FindRoot_Dist(D, rx, alpha); |
---|
919 | |
---|
920 | eps = ui32MinNonNul3(r1, r2, rx); |
---|
921 | |
---|
922 | MCA_VERBOSE3(printf("\n")); |
---|
923 | MCA_VERBOSE3(printf("e1 = %5d -> r1 = %5d\n", e1, r1)); |
---|
924 | MCA_VERBOSE3(printf("e2 = %5d -> r2 = %5d\n", e2, r2)); |
---|
925 | MCA_VERBOSE3(printf("ex = %5d -> rx = %5d\n", ex, rx)); |
---|
926 | MCA_VERBOSE3(printf("eps = %5d\n", eps)); |
---|
927 | |
---|
928 | // Quick-Union |
---|
929 | if (r1 > eps) { |
---|
930 | SetRoot_Rosenfeld(D, r1, eps, alpha, F); |
---|
931 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r1, eps)); |
---|
932 | } |
---|
933 | //if (r2 > 0) { |
---|
934 | // r2 = FindRoot_Dist(D, r2, alpha); |
---|
935 | //} |
---|
936 | if (r2 > eps && r2 != r1) { |
---|
937 | //if (r2 > eps) { |
---|
938 | SetRoot_Rosenfeld(D, r2, eps, alpha, F); |
---|
939 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r2, eps)); |
---|
940 | } |
---|
941 | //rx = FindRoot_Dist(D, rx, alpha); |
---|
942 | if (rx > eps && rx != r2 && rx != r1) { |
---|
943 | //if (rx > eps) { |
---|
944 | SetRoot_Rosenfeld(D, rx, eps, alpha, F); |
---|
945 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", rx, eps)); |
---|
946 | } |
---|
947 | MCA_VERBOSE3(printf("---------------------------\n")); |
---|
948 | } |
---|
949 | } |
---|
950 | } |
---|
951 | #endif // SLOW |
---|
952 | |
---|
953 | |
---|
954 | |
---|
955 | // -------------------------------------------------------------------------------------------------------------------------------------- |
---|
956 | static void borderMerging_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
957 | // -------------------------------------------------------------------------------------------------------------------------------------- |
---|
958 | { |
---|
959 | #if FAST |
---|
960 | borderMerging_Fast_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F); |
---|
961 | #endif // FAST |
---|
962 | #if SLOW |
---|
963 | borderMerging_Slow_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F); |
---|
964 | #endif // SLOW |
---|
965 | } |
---|
966 | |
---|
967 | |
---|
968 | // ---------------------------------------------------------------------------------------------------- |
---|
969 | static uint32 line0Labeling_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne) |
---|
970 | // ---------------------------------------------------------------------------------------------------- |
---|
971 | { |
---|
972 | int j; |
---|
973 | uint8 x; |
---|
974 | uint32 e4; |
---|
975 | uint32 r4; |
---|
976 | |
---|
977 | // prologue : j = 0 |
---|
978 | x = X[i][0]; |
---|
979 | if (x) { |
---|
980 | E[i][0] = ++ne; |
---|
981 | } |
---|
982 | else { |
---|
983 | E[i][0] = 0; |
---|
984 | } |
---|
985 | |
---|
986 | // boucle et epilogue j = [1..width-1] |
---|
987 | for (j = 1; j <= width - 1; j++) { |
---|
988 | x = X[i][j]; |
---|
989 | if (x) { |
---|
990 | e4 = E[i][j - 1]; |
---|
991 | |
---|
992 | if (e4 == 0) { |
---|
993 | E[i][j] = ++ne; |
---|
994 | } |
---|
995 | else { |
---|
996 | E[i][j] = e4; |
---|
997 | } |
---|
998 | } |
---|
999 | else { |
---|
1000 | E[i][j] = 0; |
---|
1001 | } |
---|
1002 | } |
---|
1003 | return ne; |
---|
1004 | } |
---|
1005 | |
---|
1006 | |
---|
1007 | #if SLOW |
---|
1008 | // -------------------------------------------------------------------------------------------------------- |
---|
1009 | static uint32 lineLabeling_Slow_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne) |
---|
1010 | // -------------------------------------------------------------------------------------------------------- |
---|
1011 | { |
---|
1012 | // version lineLabeling_Rosenfeld_UF_QU_8C avec Quick-Union |
---|
1013 | |
---|
1014 | int j; |
---|
1015 | |
---|
1016 | uint8 x; |
---|
1017 | uint32 e; |
---|
1018 | uint32 e1, e2, e3, e4; |
---|
1019 | uint32 r1, r2, r3, r4; |
---|
1020 | |
---|
1021 | // -------------- |
---|
1022 | // -- prologue -- |
---|
1023 | // -------------- |
---|
1024 | |
---|
1025 | j = 0; |
---|
1026 | x = X[i][j]; |
---|
1027 | |
---|
1028 | if (x) { |
---|
1029 | |
---|
1030 | e2 = E[i - 1][j]; |
---|
1031 | e3 = E[i - 1][j + 1]; |
---|
1032 | |
---|
1033 | // nouvel element |
---|
1034 | if (e2 == 0 && e3 == 0) { |
---|
1035 | e = ++ne; |
---|
1036 | E[i][j] = e; |
---|
1037 | } |
---|
1038 | else { |
---|
1039 | // etiquettes identiques |
---|
1040 | if (e2 == e3) { |
---|
1041 | e = e2; |
---|
1042 | E[i][j] = e; |
---|
1043 | } |
---|
1044 | else { |
---|
1045 | // cas general |
---|
1046 | r2 = (e2 == 0) ? 0 : FindRoot(T, e2); |
---|
1047 | r3 = (e3 == 0) ? 0 : FindRoot(T, e3); |
---|
1048 | |
---|
1049 | e = ui32MinNonNul2(r2, r3); |
---|
1050 | |
---|
1051 | // Quick-Union |
---|
1052 | if (r2 > e) { |
---|
1053 | T[r2] = e; |
---|
1054 | } |
---|
1055 | if (r3 > e) { |
---|
1056 | T[r3] = e; |
---|
1057 | } |
---|
1058 | E[i][j] = e; |
---|
1059 | } |
---|
1060 | } |
---|
1061 | } |
---|
1062 | else { |
---|
1063 | E[i][j] = 0; |
---|
1064 | } // x |
---|
1065 | |
---|
1066 | // ----------------------- |
---|
1067 | // -- boucle principale -- |
---|
1068 | // ----------------------- |
---|
1069 | |
---|
1070 | for (j = 0 + 1; j < width - 1; j++) { |
---|
1071 | |
---|
1072 | x = X[i][j]; |
---|
1073 | |
---|
1074 | if (x) { |
---|
1075 | e1 = E[i - 1][j - 1]; |
---|
1076 | e2 = E[i - 1][j]; |
---|
1077 | e3 = E[i - 1][j + 1]; |
---|
1078 | e4 = E[i][j - 1]; |
---|
1079 | |
---|
1080 | // nouvel element |
---|
1081 | if (e1 == 0 && e2 == 0 && e3 == 0 && e4 == 0) { |
---|
1082 | e = ++ne; |
---|
1083 | E[i][j] = e; |
---|
1084 | } |
---|
1085 | else { |
---|
1086 | // etiquettes identiques |
---|
1087 | if (e1 == e2 && e1 == e3 && e1 == e4) { |
---|
1088 | e = e1; |
---|
1089 | E[i][j] = e; |
---|
1090 | } |
---|
1091 | else { |
---|
1092 | // cas general |
---|
1093 | r1 = (e1 == 0) ? 0 : FindRoot(T, e1); |
---|
1094 | r2 = (e2 == 0) ? 0 : FindRoot(T, e2); |
---|
1095 | r3 = (e3 == 0) ? 0 : FindRoot(T, e3); |
---|
1096 | r4 = (e4 == 0) ? 0 : FindRoot(T, e4); |
---|
1097 | |
---|
1098 | e = ui32MinNonNul4(r1, r2, r3, r4); |
---|
1099 | |
---|
1100 | // Quick-Union |
---|
1101 | if (r1 > e) { |
---|
1102 | T[r1] = e; |
---|
1103 | } |
---|
1104 | if (r2 > e) { |
---|
1105 | T[r2] = e; |
---|
1106 | } |
---|
1107 | if (r3 > e) { |
---|
1108 | T[r3] = e; |
---|
1109 | } |
---|
1110 | if (r4 > e) { |
---|
1111 | T[r4] = e; |
---|
1112 | } |
---|
1113 | E[i][j] = e; |
---|
1114 | } |
---|
1115 | } |
---|
1116 | } |
---|
1117 | else { |
---|
1118 | E[i][j] = 0; |
---|
1119 | } // x |
---|
1120 | } // j |
---|
1121 | |
---|
1122 | // -------------- |
---|
1123 | // -- epilogue -- |
---|
1124 | // -------------- |
---|
1125 | j = width - 1; |
---|
1126 | x = X[i][j]; |
---|
1127 | |
---|
1128 | if (x) { |
---|
1129 | e1 = E[i - 1][j - 1]; |
---|
1130 | e2 = E[i - 1][j]; |
---|
1131 | e4 = E[i][j - 1]; |
---|
1132 | |
---|
1133 | // nouvel element |
---|
1134 | if (e1 == 0 && e2 == 0 && e4 == 0) { |
---|
1135 | e = ++ne; |
---|
1136 | E[i][j] = e; |
---|
1137 | } |
---|
1138 | else { |
---|
1139 | // etiquettes identiques |
---|
1140 | if (e1 == e2 && e1 == e4) { |
---|
1141 | e = e1; |
---|
1142 | E[i][j] = e; |
---|
1143 | } |
---|
1144 | else { |
---|
1145 | // cas general |
---|
1146 | r1 = (e1 == 0) ? 0 : FindRoot(T, e1); |
---|
1147 | r2 = (e2 == 0) ? 0 : FindRoot(T, e2); |
---|
1148 | r4 = (e4 == 0) ? 0 : FindRoot(T, e4); |
---|
1149 | |
---|
1150 | e = ui32MinNonNul3(r1, r2, r4); |
---|
1151 | |
---|
1152 | // Quick-Union |
---|
1153 | if (r1 > e) { |
---|
1154 | T[r1] = e; |
---|
1155 | } |
---|
1156 | if (r2 > e) { |
---|
1157 | T[r2] = e; |
---|
1158 | } |
---|
1159 | if (r4 > e) { |
---|
1160 | T[r4] = e; |
---|
1161 | } |
---|
1162 | E[i][j] = e; |
---|
1163 | } |
---|
1164 | } |
---|
1165 | } |
---|
1166 | else { |
---|
1167 | E[i][j] = 0; |
---|
1168 | } // x |
---|
1169 | |
---|
1170 | return ne; |
---|
1171 | } |
---|
1172 | #endif // SLOW |
---|
1173 | |
---|
1174 | |
---|
1175 | #if FAST |
---|
1176 | // --------------------------------------------------------------------------------------------- |
---|
1177 | static uint32 optimizedAccessLeft_DT_Rosenfeld(uint32 ** E, int i, int j, uint32 * T, uint32 ne) |
---|
1178 | // --------------------------------------------------------------------------------------------- |
---|
1179 | { |
---|
1180 | // Decision Tree 8-connexe avec Quick-Union |
---|
1181 | uint32 b, c, e; |
---|
1182 | |
---|
1183 | b = E[i - 1][j]; |
---|
1184 | if (b) { |
---|
1185 | e = use1_QU_Rosenfeld(b, T); |
---|
1186 | } |
---|
1187 | else { |
---|
1188 | c = E[i - 1][j + 1]; |
---|
1189 | if (c) { |
---|
1190 | e = use1_QU_Rosenfeld(c, T); |
---|
1191 | } |
---|
1192 | else { |
---|
1193 | e = ++ne; |
---|
1194 | } |
---|
1195 | } |
---|
1196 | E[i][j] = e; |
---|
1197 | return ne; |
---|
1198 | } |
---|
1199 | |
---|
1200 | // FAST |
---|
1201 | |
---|
1202 | // ---------------------------------------------------------------------------------------------- |
---|
1203 | static uint32 optimizedAccessRight_DT_Rosenfeld(uint32 ** E, int i, int j, uint32 * T, uint32 ne) |
---|
1204 | // ---------------------------------------------------------------------------------------------- |
---|
1205 | { |
---|
1206 | // Decision Tree 8-connexe avec Quick-Union |
---|
1207 | uint32 a, b, d, e; |
---|
1208 | |
---|
1209 | b = E[i - 1][j]; |
---|
1210 | if (b) { |
---|
1211 | e = use1_QU_Rosenfeld(b, T); |
---|
1212 | } |
---|
1213 | else { |
---|
1214 | a = E[i - 1][j - 1]; |
---|
1215 | if (a) { |
---|
1216 | e = use1_QU_Rosenfeld(a, T); |
---|
1217 | } |
---|
1218 | else { |
---|
1219 | d = E[i][j - 1]; |
---|
1220 | if (d) { |
---|
1221 | e = use1_QU_Rosenfeld(d, T); |
---|
1222 | } |
---|
1223 | else { |
---|
1224 | e = ++ne; |
---|
1225 | } |
---|
1226 | } |
---|
1227 | } |
---|
1228 | E[i][j] = e; |
---|
1229 | return ne; |
---|
1230 | } |
---|
1231 | |
---|
1232 | // FAST |
---|
1233 | |
---|
1234 | // ----------------------------------------------------------------------------------------- |
---|
1235 | static uint32 optimizedAccess_DT_Rosenfeld(uint32 ** E, int i, int j, uint32 * T, uint32 ne) |
---|
1236 | // ----------------------------------------------------------------------------------------- |
---|
1237 | { |
---|
1238 | // Decision Tree 8-connexe avec Quick-Union |
---|
1239 | uint32 a, b, c, d, e; |
---|
1240 | |
---|
1241 | b = E[i - 1][j]; |
---|
1242 | if (b) { |
---|
1243 | e = use1_QU_Rosenfeld(b, T); |
---|
1244 | } |
---|
1245 | else { |
---|
1246 | c = E[i - 1][j + 1]; |
---|
1247 | if (c) { |
---|
1248 | a = E[i - 1][j - 1]; |
---|
1249 | if (a) { |
---|
1250 | e = use2_QU_Rosenfeld(a, c, T); |
---|
1251 | } |
---|
1252 | else { |
---|
1253 | d = E[i][j - 1]; |
---|
1254 | if (d) { |
---|
1255 | e = use2_QU_Rosenfeld(c, d, T); |
---|
1256 | } |
---|
1257 | else { |
---|
1258 | e = use1_QU_Rosenfeld(c, T); |
---|
1259 | } |
---|
1260 | } |
---|
1261 | } |
---|
1262 | else { |
---|
1263 | a = E[i - 1][j - 1]; |
---|
1264 | if (a) { |
---|
1265 | e = use1_QU_Rosenfeld(a, T); |
---|
1266 | } |
---|
1267 | else { |
---|
1268 | d = E[i][j - 1]; |
---|
1269 | if (d) { |
---|
1270 | e = use1_QU_Rosenfeld(d, T); |
---|
1271 | } |
---|
1272 | else { |
---|
1273 | e = ++ne; |
---|
1274 | } |
---|
1275 | } |
---|
1276 | } |
---|
1277 | } |
---|
1278 | E[i][j] = e; |
---|
1279 | return ne; |
---|
1280 | } |
---|
1281 | |
---|
1282 | // FAST |
---|
1283 | |
---|
1284 | // -------------------------------------------------------------------------------------------------------- |
---|
1285 | static uint32 lineLabeling_Fast_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne) |
---|
1286 | // -------------------------------------------------------------------------------------------------------- |
---|
1287 | { |
---|
1288 | uint8 x; |
---|
1289 | // avec DT et QU |
---|
1290 | // Left Border |
---|
1291 | x = X[i][0]; |
---|
1292 | if (x) { |
---|
1293 | ne = optimizedAccessLeft_DT_Rosenfeld(E, i, 0, T, ne); |
---|
1294 | } |
---|
1295 | else { |
---|
1296 | E[i][0] = 0; |
---|
1297 | } |
---|
1298 | // Middle |
---|
1299 | for (int j = 1; j < width - 1; j++) { |
---|
1300 | uint8 x = X[i][j]; |
---|
1301 | if (x) { |
---|
1302 | ne = optimizedAccess_DT_Rosenfeld(E, i, j, T, ne); |
---|
1303 | } |
---|
1304 | else { |
---|
1305 | E[i][j] = 0; |
---|
1306 | } |
---|
1307 | } |
---|
1308 | // Right Border |
---|
1309 | x = X[i][width - 1]; |
---|
1310 | if (x) { |
---|
1311 | ne = optimizedAccessRight_DT_Rosenfeld(E, i, width - 1, T, ne); |
---|
1312 | } |
---|
1313 | else { |
---|
1314 | E[i][width - 1] = 0; |
---|
1315 | } |
---|
1316 | return ne; |
---|
1317 | } |
---|
1318 | #endif // FAST |
---|
1319 | |
---|
1320 | |
---|
1321 | // --------------------------------------------------------------------------------------------------- |
---|
1322 | static uint32 lineLabeling_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne) |
---|
1323 | // --------------------------------------------------------------------------------------------------- |
---|
1324 | { |
---|
1325 | #if SLOW |
---|
1326 | return lineLabeling_Slow_Rosenfeld(X, i, width, E, T, ne); |
---|
1327 | #elif FAST |
---|
1328 | return lineLabeling_Fast_Rosenfeld(X, i, width, E, T, ne); |
---|
1329 | #endif |
---|
1330 | } |
---|
1331 | |
---|
1332 | |
---|
1333 | // ----------------------------------------------------------------------- |
---|
1334 | static uint32 countTable_Range_Rosenfeld(uint32 * T, uint32 e0, uint32 e1) |
---|
1335 | // ----------------------------------------------------------------------- |
---|
1336 | { |
---|
1337 | uint32 e; |
---|
1338 | uint32 nr = 0; // nombre de racines = de composantes connexes |
---|
1339 | |
---|
1340 | for (e = e0; e <= e1; e++) { |
---|
1341 | if (e == T[e]) { |
---|
1342 | nr += 1; |
---|
1343 | } |
---|
1344 | } |
---|
1345 | return nr; |
---|
1346 | } |
---|
1347 | |
---|
1348 | |
---|
1349 | // ------------------------------------------------------------------------------------------ |
---|
1350 | static void solveTable_Range_Rosenfeld(uint32 * T, uint32 e0, uint32 e1, RegionStats * Stats) |
---|
1351 | // ------------------------------------------------------------------------------------------ |
---|
1352 | { |
---|
1353 | uint32 e, r; |
---|
1354 | |
---|
1355 | for (e = e0; e <= e1; e++) { |
---|
1356 | r = T[T[e]]; |
---|
1357 | assert(r != 0); |
---|
1358 | if (r < e) { |
---|
1359 | T[e] = r; // racine de la classe d'equivalence |
---|
1360 | #if FEATURES |
---|
1361 | RegionStats_Accumulate_Stats1_From_Index(Stats, r, e); |
---|
1362 | #endif |
---|
1363 | } |
---|
1364 | } |
---|
1365 | } |
---|
1366 | |
---|
1367 | |
---|
1368 | // -------------------------------------------- |
---|
1369 | static void MCA_Label_Rosenfeld_PAR1(MCA * mca) |
---|
1370 | // -------------------------------------------- |
---|
1371 | { |
---|
1372 | if (mca->p == 0) { |
---|
1373 | MCA_VERBOSE2(printf("*** %s ***\n", __func__)); |
---|
1374 | } |
---|
1375 | |
---|
1376 | |
---|
1377 | int i0 = mca->i0; |
---|
1378 | int i1 = mca->i1; |
---|
1379 | int width = mca->width; |
---|
1380 | |
---|
1381 | uint32 e0 = mca->e0; |
---|
1382 | uint32 e1 = mca->e1; |
---|
1383 | uint32 ne = e0 - 1; |
---|
1384 | uint32 nr = 0; |
---|
1385 | |
---|
1386 | // local memory zones |
---|
1387 | uint8 ** X = mca->X; |
---|
1388 | uint32 ** E = mca->E; |
---|
1389 | uint32 * T = mca->T; |
---|
1390 | RegionStats * stats = mca->stats; |
---|
1391 | |
---|
1392 | // reset sous optimal (pour le moment = voir region32) |
---|
1393 | if (mca->p == 0) { |
---|
1394 | set_ui32vector_j(T, e0 - 1, e1); // car e0 = 1, on a besoin que T[0] = 0 pour FindRoot |
---|
1395 | #if FEATURES |
---|
1396 | zero_RegionStatsVector(stats, e0 - 1, e1); |
---|
1397 | #endif |
---|
1398 | } |
---|
1399 | else { |
---|
1400 | set_ui32vector_j(T, e0, e1); |
---|
1401 | #if FEATURES |
---|
1402 | zero_RegionStatsVector(stats, e0, e1); |
---|
1403 | #endif |
---|
1404 | } |
---|
1405 | |
---|
1406 | if (mca->p == 0) { |
---|
1407 | MCA_VERBOSE3(display_ui8matrix_positive(X, i0, i1, 0, width - 1, 5, "Xp"); printf("\n")); |
---|
1408 | } |
---|
1409 | |
---|
1410 | // ---------------------------- // |
---|
1411 | // -- Etiquetage d'une bande -- // |
---|
1412 | // ---------------------------- // |
---|
1413 | |
---|
1414 | CLOCK_THREAD_START_STEP(mca->p, 0); |
---|
1415 | |
---|
1416 | ne = line0Labeling_Rosenfeld(X, i0, width, E, T, ne); |
---|
1417 | #if FEATURES |
---|
1418 | lineFeaturesComputation(E, i0, width, stats); |
---|
1419 | #endif |
---|
1420 | |
---|
1421 | for (int i = i0 + 1; i <= i1; i++) { |
---|
1422 | ne = lineLabeling_Rosenfeld(X, i, width, E, T, ne); // Slow or Fast |
---|
1423 | #if FEATURES |
---|
1424 | lineFeaturesComputation(E, i, width, stats); |
---|
1425 | #endif |
---|
1426 | } |
---|
1427 | mca->ne = ne; //plus grande etiquette de l'intervalle [e0..e1] |
---|
1428 | |
---|
1429 | if (mca->p == 0) { |
---|
1430 | MCA_VERBOSE3(printf("ne = %d\n", ne)); |
---|
1431 | MCA_VERBOSE3(display_ui32matrix_positive(E, i0, i1, 0, width - 1, 5, "Ep"); printf("\n")); |
---|
1432 | MCA_VERBOSE3(display_ui32vector_number(T, e0, ne, "%5d", "Tp_avant")); |
---|
1433 | } |
---|
1434 | |
---|
1435 | // ------------------------------------------------------ // |
---|
1436 | // -- Fermeture transitive sans pack de chaque table T -- // |
---|
1437 | // ------------------------------------------------------ // |
---|
1438 | |
---|
1439 | solveTable_Range_Rosenfeld(T, e0, ne, stats); |
---|
1440 | |
---|
1441 | if (mca->p == 0) { |
---|
1442 | MCA_VERBOSE3(nr = countTable_Range_Rosenfeld(T, e0, ne); |
---|
1443 | printf("p = %d : e = [%d..%d] -> ne = %d -> nr = %d\n", mca->p, e0, ne, (ne - e0 + 1), nr)); |
---|
1444 | MCA_VERBOSE3(display_ui32vector_number(T, e0, ne, "%5d", "Tp_apres")); |
---|
1445 | } |
---|
1446 | CLOCK_THREAD_END_STEP(mca->p, 0); |
---|
1447 | } |
---|
1448 | |
---|
1449 | |
---|
1450 | |
---|
1451 | #if PARMERGE |
---|
1452 | // ----------------------------------------------------- |
---|
1453 | static void MCA_Label_Rosenfeld_PAR2(MCA * mca) |
---|
1454 | // ----------------------------------------------------- |
---|
1455 | { |
---|
1456 | int p = mca->p; |
---|
1457 | int nb_level = mca->nb_level; |
---|
1458 | |
---|
1459 | if (mca->p == 0) { |
---|
1460 | MCA_VERBOSE2(printf("*** %s ***\n", __func__)); |
---|
1461 | } |
---|
1462 | |
---|
1463 | // ------------------------------ |
---|
1464 | // -- parallel border merging -- |
---|
1465 | // ------------------------------ |
---|
1466 | |
---|
1467 | // local variables |
---|
1468 | int i = mca->i0; |
---|
1469 | int width = mca->width; |
---|
1470 | int alpha = mca->alpha; |
---|
1471 | uint32 e0 = mca->e0; |
---|
1472 | uint32 e1 = mca->ne; |
---|
1473 | |
---|
1474 | // local memory zones |
---|
1475 | uint8 ** X = mca->X; |
---|
1476 | uint32 ** E = mca->E; |
---|
1477 | uint32 * T = mca->T; |
---|
1478 | uint32 ** D = mca->D; |
---|
1479 | RegionStats ** F = mca->F; |
---|
1480 | |
---|
1481 | CLOCK_THREAD_START_STEP(p, 1); |
---|
1482 | if (p != 0) { // thread 0 never has any merge to do |
---|
1483 | borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F); // (i) et (i-1) |
---|
1484 | } |
---|
1485 | pthread_barrier_wait(&main_barrier); |
---|
1486 | CLOCK_THREAD_END_STEP(p, 1); |
---|
1487 | |
---|
1488 | |
---|
1489 | // --------------------------------- |
---|
1490 | // -- parallel transitive closure -- |
---|
1491 | // --------------------------------- |
---|
1492 | // identique a la version sans Features |
---|
1493 | |
---|
1494 | CLOCK_THREAD_START_STEP(p, 2); |
---|
1495 | for (uint32 e = e0; e <= e1; e++) { |
---|
1496 | uint32 r = T[e]; // acces local |
---|
1497 | if (r < e) { |
---|
1498 | r = FindRoot_Dist(D, e, alpha); // acces distant |
---|
1499 | T[e] = r; |
---|
1500 | } |
---|
1501 | MCA_VERBOSE3(printf("p%d : T[%d] <- %d\n", p, e, r)); |
---|
1502 | } |
---|
1503 | CLOCK_THREAD_END_STEP(p, 2); |
---|
1504 | |
---|
1505 | // To avoid uninitialized accesses |
---|
1506 | CLOCK_THREAD_START_STEP(p, 3); |
---|
1507 | CLOCK_THREAD_END_STEP(p, 3); |
---|
1508 | } |
---|
1509 | #endif // PARMERGE |
---|
1510 | |
---|
1511 | |
---|
1512 | #if !PARMERGE |
---|
1513 | // -------------------------------------------- |
---|
1514 | static void MCA_Label_Rosenfeld_PYR2(MCA * mca) |
---|
1515 | // -------------------------------------------- |
---|
1516 | { |
---|
1517 | // input |
---|
1518 | int p = mca->p; |
---|
1519 | int nb_level = mca->nb_level; |
---|
1520 | |
---|
1521 | if (mca->p == 0) { |
---|
1522 | MCA_VERBOSE2(printf("*** %s ***\n", __func__)); |
---|
1523 | } |
---|
1524 | |
---|
1525 | // ------------------------------ |
---|
1526 | // -- pyramidal border merging -- |
---|
1527 | // ------------------------------ |
---|
1528 | |
---|
1529 | // local variables |
---|
1530 | int i = mca->i0; |
---|
1531 | int width = mca->width; |
---|
1532 | int alpha = mca->alpha; |
---|
1533 | uint32 e0 = mca->e0; |
---|
1534 | uint32 e1 = mca->ne; |
---|
1535 | |
---|
1536 | // local memory zones |
---|
1537 | uint8 ** X = mca->X; |
---|
1538 | uint32 ** E = mca->E; |
---|
1539 | uint32 * T = mca->T; |
---|
1540 | uint32 ** D = mca->D; |
---|
1541 | RegionStats ** F = mca->F; |
---|
1542 | |
---|
1543 | CLOCK_THREAD_START_STEP(p, 1); |
---|
1544 | #if PYR_BARRIERS |
---|
1545 | // Version optimisée qui fait faire un break aux processeurs qui n'ont plus |
---|
1546 | // Ã faire de merge. |
---|
1547 | // Implique de pré-calculer le nombre de threads à chaque barriÚre |
---|
1548 | if (p != 0) { // thread 0 never has any merge to do |
---|
1549 | int been_active = 0; |
---|
1550 | for (int level = 0; level < nb_level; level++) { |
---|
1551 | if ((p + (1 << level)) % (1 << (level + 1)) == 0) { |
---|
1552 | borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F); // (i) et (i-1) |
---|
1553 | been_active = 1; |
---|
1554 | } |
---|
1555 | else if (been_active) { |
---|
1556 | break; |
---|
1557 | } |
---|
1558 | pthread_barrier_wait(&mca->barriers[level]); |
---|
1559 | } |
---|
1560 | } |
---|
1561 | pthread_barrier_wait(&main_barrier); |
---|
1562 | #else |
---|
1563 | for (int level = 1; level <= nb_level; level++) { |
---|
1564 | if ((p + (1 << (level - 1))) % (1 << level) == 0) { |
---|
1565 | // thread actif |
---|
1566 | borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F); // (i) et (i-1) |
---|
1567 | } |
---|
1568 | pthread_barrier_wait(&main_barrier); |
---|
1569 | } |
---|
1570 | #endif |
---|
1571 | CLOCK_THREAD_END_STEP(p, 1); |
---|
1572 | |
---|
1573 | |
---|
1574 | // --------------------------------- |
---|
1575 | // -- parallel transitive closure -- |
---|
1576 | // --------------------------------- |
---|
1577 | |
---|
1578 | CLOCK_THREAD_START_STEP(p, 2); |
---|
1579 | for (uint32 e = e0; e <= e1; e++) { |
---|
1580 | uint32 r = T[e]; // acces local |
---|
1581 | if (r < e) { |
---|
1582 | r = FindRoot_Dist(D, e, alpha); // acces distant |
---|
1583 | T[e] = r; |
---|
1584 | } |
---|
1585 | MCA_VERBOSE3(printf("p%d : T[%d] <- %d\n", p, e, r)); |
---|
1586 | } |
---|
1587 | CLOCK_THREAD_END_STEP(p, 2); |
---|
1588 | } |
---|
1589 | #endif // !FEATURES |
---|
1590 | |
---|
1591 | |
---|
1592 | // ------------------------------------- |
---|
1593 | void MCA_Label_Rosenfeld_PAR3(MCA * mca) |
---|
1594 | // ------------------------------------- |
---|
1595 | { |
---|
1596 | // input |
---|
1597 | if (mca->p == 0) { |
---|
1598 | MCA_VERBOSE2(printf("*** %s ***\n", __func__)); |
---|
1599 | } |
---|
1600 | |
---|
1601 | int i0 = mca->i0; |
---|
1602 | int i1 = mca->i1; |
---|
1603 | int j0 = 0; |
---|
1604 | int j1 = mca->width - 1; |
---|
1605 | |
---|
1606 | uint32 ** E = mca->E; |
---|
1607 | uint32 * T = mca->T; |
---|
1608 | |
---|
1609 | CLOCK_THREAD_START_STEP(mca->p, 3); |
---|
1610 | for (int i = i0; i <= i1; i++) { |
---|
1611 | for (int j = j0; j <= j1; j++) { |
---|
1612 | uint32 e = E[i][j]; |
---|
1613 | if (e != 0) { |
---|
1614 | E[i][j] = T[e]; |
---|
1615 | } |
---|
1616 | } |
---|
1617 | } |
---|
1618 | CLOCK_THREAD_END_STEP(mca->p, 3); |
---|
1619 | } |
---|
1620 | |
---|
1621 | |
---|
1622 | |
---|
1623 | // ====================================================================== |
---|
1624 | #if TARGET_OS == GIETVM |
---|
1625 | __attribute__((constructor)) void * MCA_Label_Rosenfeld(void * arg) |
---|
1626 | #else |
---|
1627 | void * MCA_Label_Rosenfeld(void * arg) |
---|
1628 | #endif |
---|
1629 | // ====================================================================== |
---|
1630 | { |
---|
1631 | MCA * mca = (MCA *) arg; |
---|
1632 | #if TARGET_OS == GIETVM |
---|
1633 | unsigned int x, y, lpid; |
---|
1634 | giet_proc_xyp(&x, &y, &lpid); |
---|
1635 | // Mettre à jour mca->p en fonction de x, y, lpid |
---|
1636 | // pour que les allocations faites par le main soient locales, |
---|
1637 | // i.e. |
---|
1638 | mca->p = (x * Y_SIZE + y) * NB_PROCS_MAX + lpid; |
---|
1639 | // We have : |
---|
1640 | // mca->p = 4 pour (x = 0, y = 1, lpid = 0) |
---|
1641 | // mca->p = 5 pour (x = 0, y = 1, lpid = 1) |
---|
1642 | MCA_VERBOSE3(printf("mca->p = %d pour (x = %d, y = %d, lpid = %d)\n", mca->p, x, y, lpid)); |
---|
1643 | #endif |
---|
1644 | |
---|
1645 | CLOCK_THREAD_START(mca->p); |
---|
1646 | CLOCK_THREAD_COMPUTE_START(mca->p); |
---|
1647 | |
---|
1648 | MCA_Scatter_ImageX(mca); |
---|
1649 | pthread_barrier_wait(&main_barrier); |
---|
1650 | |
---|
1651 | MCA_Label_Rosenfeld_PAR1(mca); |
---|
1652 | pthread_barrier_wait(&main_barrier); |
---|
1653 | |
---|
1654 | #if PARMERGE |
---|
1655 | MCA_Label_Rosenfeld_PAR2(mca); |
---|
1656 | #else |
---|
1657 | MCA_Label_Rosenfeld_PYR2(mca); |
---|
1658 | #endif |
---|
1659 | pthread_barrier_wait(&main_barrier); |
---|
1660 | |
---|
1661 | MCA_Label_Rosenfeld_PAR3(mca); |
---|
1662 | pthread_barrier_wait(&main_barrier); |
---|
1663 | |
---|
1664 | MCA_Gather_ImageL(mca); |
---|
1665 | pthread_barrier_wait(&main_barrier); |
---|
1666 | |
---|
1667 | CLOCK_THREAD_COMPUTE_END(mca->p); |
---|
1668 | |
---|
1669 | #if FEATURES |
---|
1670 | if (display_features) { |
---|
1671 | if (mca->p == 0) { |
---|
1672 | int i = 1; |
---|
1673 | MCA_VERBOSE1(printf("[STATS]\n")); |
---|
1674 | for (int p = 0; p < mca->np; p++) { |
---|
1675 | MCA * mca_par = mca->mca->mcas[p]; |
---|
1676 | uint32 e0 = mca_par->e0; |
---|
1677 | uint32 ne = mca_par->ne - mca_par->e0; // number of elements |
---|
1678 | uint32 * T = mca_par->T; |
---|
1679 | RegionStats * stats = mca_par->stats; |
---|
1680 | MCA_VERBOSE1(RegionStats_DisplayStats_Sparse(T, e0, e0 + ne, stats, NULL, &i)); |
---|
1681 | } |
---|
1682 | MCA_VERBOSE1(printf("[/STATS]\n")); |
---|
1683 | } |
---|
1684 | } |
---|
1685 | #endif |
---|
1686 | |
---|
1687 | CLOCK_THREAD_END(mca->p); |
---|
1688 | |
---|
1689 | #if TARGET_OS == GIETVM |
---|
1690 | if (mca->p != 0) { |
---|
1691 | exit(0); |
---|
1692 | } |
---|
1693 | #endif |
---|
1694 | |
---|
1695 | return NULL; |
---|
1696 | } |
---|
1697 | |
---|
1698 | |
---|
1699 | // Local Variables: |
---|
1700 | // tab-width: 4 |
---|
1701 | // c-basic-offset: 4 |
---|
1702 | // c-file-offsets:((innamespace . 0)(inline-open . 0)) |
---|
1703 | // indent-tabs-mode: nil |
---|
1704 | // End: |
---|
1705 | |
---|
1706 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4 |
---|
1707 | |
---|