source: soft/giet_vm/applications/rosenfeld/src-par/mca_rosenfeld.c @ 821

Last change on this file since 821 was 821, checked in by meunier, 8 years ago
  • Added several versions of rosenfeld: { SLOW, FAST } x { FEATURES, NO_FEATURES }
  • Added native linux compilation support
  • Added a script to check results natively
  • Started to refactor nrc code
File size: 65.0 KB
Line 
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
46extern pthread_barrier_t main_barrier;
47extern int display_features;
48
49CLOCK_DEC;
50
51
52// -----------------------------------------
53static 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    if (r == 0) {
64        printf("e = %d\n",e);
65        assert(0);
66    }
67    return r;
68}
69
70
71// ----------------------------------------------------------
72static uint32 FindRoot_Dist(uint32 ** D, uint32 r, int shift)
73// ----------------------------------------------------------
74{
75    uint32 e;
76    uint32 e1;
77    uint32 e0;
78
79    assert(r != 0);
80   
81    int mask = (1 << shift) - 1;
82   
83    MCA_VERBOSE2(printf("%s(%d, %d) \n", __func__, r, shift));
84    do {
85        e  = r;
86        e1 = r >> shift;
87        e0 = r & mask;
88        r = D[e1][e0];
89        MCA_VERBOSE2(printf("%s: D(%d) = D[%d,%d] = %d (alpha = %d)\n", __func__, e, e1, e0, r, shift));
90    } while (r < e);
91    MCA_VERBOSE2(printf("%s = %d \n\n", __func__, r));
92    assert(r != 0);
93    return r;
94}
95
96
97#if !FEATURES
98// --------------------------------------------------------------------------------
99static void SetRoot_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift)
100// --------------------------------------------------------------------------------
101{
102    int mask = (1 << shift) - 1;
103    assert(root != 0 && eps != 0);
104   
105    uint32 r1 = root >> shift;
106    uint32 r0 = root & mask;
107   
108    D[r1][r0] = eps;
109}
110#endif // !FEATURES
111
112
113#if FEATURES && !PARMERGE
114// ----------------------------------------------------------------------------------------------------
115void SetRoot_Features_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F)
116// ----------------------------------------------------------------------------------------------------
117{
118    assert(root != 0 && eps != 0);
119
120    MCA_VERBOSE2(printf("F(%d) += F(%d)\n", eps, root));
121   
122    int mask = (1 << shift) - 1;
123
124    // SetRoot_Rosenfeld_Dist
125    uint32 r1 = root >> shift;
126    uint32 r0 = root & mask;
127   
128    D[r1][r0] = eps;
129   
130    uint32 e1 = eps >> shift;
131    uint32 e0 = eps & mask;
132   
133    // version Dist de "RegionStats_Accumulate_Stats1_From_Index"
134   
135    // F(eps) = F(eps) U F(root)
136   
137    F[e1][e0].xmin = ui16min2(F[e1][e0].xmin, F[r1][r0].xmin);
138    F[e1][e0].xmax = ui16max2(F[e1][e0].xmax, F[r1][r0].xmax);
139    F[e1][e0].ymin = ui16min2(F[e1][e0].ymin, F[r1][r0].ymin);
140    F[e1][e0].ymax = ui16max2(F[e1][e0].ymax, F[r1][r0].ymax);
141   
142    F[e1][e0].S  += F[r1][r0].S;
143    F[e1][e0].Sx += F[r1][r0].Sx;
144    F[e1][e0].Sy += F[r1][r0].Sy;
145}
146#endif // FEATURES && !PARMERGE
147
148
149#if FEATURES && PARMERGE
150// -------------------------------------------------------------------------------------------------------------
151bool SetRoot_Parallel_Features_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F)
152// -------------------------------------------------------------------------------------------------------------
153{
154    assert(root != 0 && eps != 0);
155
156    MCA_VERBOSE2(printf("F(%d) += F(%d)\n", eps, root));
157   
158    int mask = (1 << shift) - 1;
159
160    // SetRoot_Rosenfeld_Dist
161    uint32 r1 = root >> shift;
162    uint32 r0 = root & mask;
163   
164    uint32 e1 = eps >> shift;
165    uint32 e0 = eps & mask;
166
167    // Locking towards the root (first root, then eps)
168    pthread_spin_lock(&F[r1][r0].lock);
169    pthread_spin_lock(&F[e1][e0].lock);
170    // FIXME: merge these conditions later, when they both appear
171    if (D[e1][e0] != eps) {
172        // Someone change the root of epsilon, need to find the new root
173        printf("race cond 1\n");
174        pthread_spin_unlock(&F[e1][e0].lock);
175        pthread_spin_unlock(&F[r1][r0].lock);
176        return false;
177    }
178    if (D[r1][r0] != root) {
179        // Someone change the root of epsilon, need to find the new root
180        printf("race cond 2\n");
181        pthread_spin_unlock(&F[e1][e0].lock);
182        pthread_spin_unlock(&F[r1][r0].lock);
183        return false;
184    }
185
186    D[r1][r0] = eps;
187   
188    // F(eps) = F(eps) U F(root)
189    F[e1][e0].xmin = ui16min2(F[e1][e0].xmin, F[r1][r0].xmin);
190    F[e1][e0].xmax = ui16max2(F[e1][e0].xmax, F[r1][r0].xmax);
191    F[e1][e0].ymin = ui16min2(F[e1][e0].ymin, F[r1][r0].ymin);
192    F[e1][e0].ymax = ui16max2(F[e1][e0].ymax, F[r1][r0].ymax);
193   
194    F[e1][e0].S  += F[r1][r0].S;
195    F[e1][e0].Sx += F[r1][r0].Sx;
196    F[e1][e0].Sy += F[r1][r0].Sy;
197
198    pthread_spin_unlock(&F[e1][e0].lock);
199    pthread_spin_unlock(&F[r1][r0].lock);
200    return true;
201}
202#endif // FEATURES && PARMERGE
203
204
205
206#if FAST
207// --------------------------------------------------------
208static uint32 QuickUnion2(uint32 * T, uint32 e1, uint32 e2)
209// --------------------------------------------------------
210{
211    // version QU de Union2
212    uint32 r1 = FindRoot(T, e1);
213    uint32 r2 = FindRoot(T, e2);
214   
215    assert(e1 != 0 && e2 != 0 && r1 != 0 && r2 != 0);
216    uint32 eps = ui32Min2(r1, r2);
217
218    if (r1 > eps) {
219        T[r1] = eps; // SetRoot sans besoin de remonter
220    }
221    if (r2 > eps) {
222        T[r2] = eps; // SetRoot sans besoin de remonter
223    }
224    assert(e1 != 0 && e2 != 0 && r1 != 0 && r2 != 0);
225   
226    return eps;
227}
228#endif // FAST
229
230
231#if FAST
232// ---------------------------------------------------
233static uint32 use1_QU_Rosenfeld(uint32 e1, uint32 * T)
234// ---------------------------------------------------
235{
236    return FindRoot(T, e1);
237}
238#endif // FAST
239
240
241#if FAST
242// --------------------------------------------------------------
243static uint32 use2_QU_Rosenfeld(uint32 e1, uint32 e2, uint32 * T)
244// --------------------------------------------------------------
245{
246    return QuickUnion2(T, e1, e2);
247}
248#endif // FAST
249
250
251#if FAST && !FEATURES
252// ---------------------------------------------------------------------------------------
253static void vuse2_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha)
254// ---------------------------------------------------------------------------------------
255{
256    uint32 rd = FindRoot_Dist(D, ed, alpha);
257   
258    uint32 rl = T[el]; // car le premier acces est local
259    rl = FindRoot_Dist(D, rl, alpha);
260   
261    assert(ed != 0 && el != 0 && rd != 0 && rl != 0);
262    if (rd == rl) {
263        return; // evite la backdoor
264    }
265   
266    // forcement positifs car appel depuis optimizedBorder
267    // qui a fait un test
268    if (rd < rl) {
269        SetRoot_Rosenfeld_Dist(D, rl, rd, alpha);
270    }
271    else {
272        SetRoot_Rosenfeld_Dist(D, rd, rl, alpha);
273    }
274}
275#endif // FAST && !FEATURES
276
277
278#if FAST && !FEATURES
279// -----------------------------------------------------------------------------------------------------
280static void vuse3_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha)
281// -----------------------------------------------------------------------------------------------------
282{
283    uint32 r1 = FindRoot_Dist(D, ed1, alpha);
284    uint32 r2 = FindRoot_Dist(D, ed2, alpha);
285   
286    // QM
287    //uint32 r3 = FindRoot(T, el3); // local - distant
288    uint32 r3 = T[el3]; // local - distant
289    r3 = FindRoot_Dist(D, r3, alpha);
290
291    assert(ed1 != 0 && ed2 != 0 && el3 != 0 && r1 != 0 && r2 != 0 && r3 != 0);
292   
293    if (r1 == r2 && r2 == r3) {
294        return;
295    }
296   
297    uint32 eps = ui32Min3(r1, r2, r3);  // forcement positifs car appel depuis optimizedBorder qui a fait un test
298   
299    if (r1 > eps) {
300        SetRoot_Rosenfeld_Dist(D, r1, eps, alpha);
301    }
302    //r2 = T[r2]; // @QM est-ce indispensable s'il n'y a pas de features ? (cf. slow no features)
303    // comment est-on sur que r2 (ou r3) est local ???
304    if (r2 > eps) {
305        SetRoot_Rosenfeld_Dist(D, r2, eps, alpha);
306    }
307    //r3 = T[r3];
308    if (r3 > eps) {
309        SetRoot_Rosenfeld_Dist(D, r3, eps, alpha);
310    }
311}
312#endif // FAST && !FEATURES
313
314
315#if FAST && FEATURES && !PARMERGE
316// -----------------------------------------------------------------------------------------------------------
317void vuse2_Features_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
318// -----------------------------------------------------------------------------------------------------------
319{
320    assert(ed != 0 && el != 0);
321
322    uint32 rd = FindRoot_Dist(D, ed, alpha);
323   
324    uint32 rl = T[el]; // car le premier acces est local
325    assert(rl != 0);
326    rl = FindRoot_Dist(D, rl, alpha);
327   
328    assert(rd != 0 && rl != 0);
329
330    if (rd == rl) {
331        return; // evite la backdoor
332    }
333   
334    // forcement positifs car appel depuis optimizedBorder
335    // qui a fait un test
336    if (rd < rl) {
337        SetRoot_Features_Rosenfeld_Dist(D, rl, rd, alpha, F);
338    }
339    else {
340        SetRoot_Features_Rosenfeld_Dist(D, rd, rl, alpha, F);
341    }
342}
343#endif // FAST && FEATURES && !PARMERGE
344
345
346#if FAST && FEATURES && !PARMERGE
347// -------------------------------------------------------------------------------------------------------------------------
348void vuse3_Features_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
349// -------------------------------------------------------------------------------------------------------------------------
350{
351    assert(ed1 != 0 && ed2 != 0 && el3 != 0);
352
353    uint32 r1 = FindRoot_Dist(D, ed1, alpha);
354    uint32 r2 = FindRoot_Dist(D, ed2, alpha);
355   
356    //uint32 r3 = FindRoot(T, el3); // local - distant
357    uint32 r3 = T[el3]; // local - distant
358    assert(r3 != 0);
359    r3 = FindRoot_Dist(D, r3, alpha);
360   
361    assert(r1 != 0 && r2 != 0 && r3 != 0);
362
363    if (r1 == r2 && r2 == r3) {
364        return;
365    }
366   
367    uint32 eps = ui32Min3(r1, r2, r3);  // forcement positifs car appel depuis optimizedBorder qui a fait un test
368   
369    if (r1 > eps) {
370        SetRoot_Features_Rosenfeld_Dist(D, r1, eps, alpha, F);
371    }
372    //r2 = T[r2];
373    if (r2 > eps && r2 != r1) {
374        SetRoot_Features_Rosenfeld_Dist(D, r2, eps, alpha, F);
375    }
376    //r3 = T[r3];
377    if (r3 > eps && r3 != r2 && r3 != r1) {
378        SetRoot_Features_Rosenfeld_Dist(D, r3, eps, alpha, F);
379    }
380}
381#endif // FAST && FEATURES && !PARMERGE
382
383
384#if FAST && FEATURES && PARMERGE
385// --------------------------------------------------------------------------------------------------------------------
386void vuse2_Parallel_Features_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
387// --------------------------------------------------------------------------------------------------------------------
388{
389    bool ok;
390    assert(ed != 0 && el != 0);
391    uint32 rl = T[el]; // car le premier acces est local
392    assert(rl != 0);
393
394    uint32 rd;
395   
396    do {
397        rd = FindRoot_Dist(D, ed, alpha); // no lock
398        rl = FindRoot_Dist(D, rl, alpha);
399
400        assert(rd != 0 && rl != 0);
401
402        if (rd == rl) {
403            return; // evite la backdoor
404        }
405
406        // forcement positifs car appel depuis optimizedBorder
407        // qui a fait un test
408        if (rd < rl) {
409            ok = SetRoot_Parallel_Features_Rosenfeld_Dist(D, rl, rd, alpha, F);
410        }
411        else {
412            ok = SetRoot_Parallel_Features_Rosenfeld_Dist(D, rd, rl, alpha, F);
413        }
414    } while (!ok);
415}
416#endif // FAST && FEATURES && PARMERGE
417
418
419#if FAST && FEATURES && PARMERGE
420// ----------------------------------------------------------------------------------------------------------------------------------
421void vuse3_Parallel_Features_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
422// ----------------------------------------------------------------------------------------------------------------------------------
423{
424    bool ok1, ok2, ok3;
425    assert(ed1 != 0 && ed2 != 0 && el3 != 0);
426
427    uint32 r1;
428    uint32 r2;
429    uint32 r3 = T[el3]; // local - distant
430    assert(r3 != 0);
431
432    do {
433        r1 = FindRoot_Dist(D, ed1, alpha);
434        r2 = FindRoot_Dist(D, ed2, alpha);
435        r3 = FindRoot_Dist(D, r3, alpha);
436   
437        assert(r1 != 0 && r2 != 0 && r3 != 0);
438
439        if (r1 == r2 && r2 == r3) {
440            return;
441        }
442   
443        uint32 eps = ui32Min3(r1, r2, r3);  // forcement positifs car appel depuis optimizedBorder qui a fait un test
444   
445        ok1 = true;
446        ok2 = true;
447        ok3 = true;
448        if (r1 > eps) {
449            ok1 = SetRoot_Parallel_Features_Rosenfeld_Dist(D, r1, eps, alpha, F);
450        }
451        if (r2 > eps && r2 != r1) {
452            ok2 = SetRoot_Parallel_Features_Rosenfeld_Dist(D, r2, eps, alpha, F);
453        }
454        if (r3 > eps && r3 != r2 && r3 != r1) {
455            ok3 = SetRoot_Parallel_Features_Rosenfeld_Dist(D, r3, eps, alpha, F);
456        }
457    } while (!(ok1 && ok2 && ok3));
458}
459#endif // FAST && FEATURES && PARMERGE
460
461
462
463
464#if FAST && !FEATURES
465// ------------------------------------------------------------------------------------------------------
466static void optimizedBorder_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha)
467// ------------------------------------------------------------------------------------------------------
468{
469    uint32 a, b, c, x;
470   
471    x = E[i][j];
472    if (x) {
473        b = E[i - 1][j];
474        if (b) {
475            vuse2_Rosenfeld_Dist(b, x, T, D, alpha); // dist, local
476        }
477        else {
478            c = E[i - 1][j + 1];
479            if (c) {
480                a = E[i - 1][j - 1];
481                if (a) {
482                    vuse3_Rosenfeld_Dist(a, c, x, T, D, alpha); // dist, local
483                }
484                else {
485                    vuse2_Rosenfeld_Dist(c, x, T, D, alpha); // dist, local
486                }
487            }
488            else {
489                a = E[i - 1][j - 1];
490                if (a) {
491                    vuse2_Rosenfeld_Dist(a, x, T, D, alpha); // dist, local
492                }
493            }
494        }
495    }
496}
497#endif // FAST && !FEATURES
498
499
500#if FAST && !FEATURES
501// ---------------------------------------------------------------------------------------------------
502static void optimizedBorderLeft_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha)
503// ---------------------------------------------------------------------------------------------------
504{
505    uint32 x = E[i][j];
506    if (x) {
507        uint32 b = E[i - 1][j];
508        if (b) {
509            vuse2_Rosenfeld_Dist(b, x, T, D, alpha); // dist, local
510        }
511        else {
512            uint32 c = E[i - 1][j + 1];
513            if (c) {
514                vuse2_Rosenfeld_Dist(c, x, T, D, alpha); // dist, local
515            }
516        }
517    }
518}
519#endif // FAST && !FEATURES
520
521
522#if FAST && !FEATURES
523// -----------------------------------------------------------------------------------------------------------
524static void optimizedBorderRight_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha)
525// -----------------------------------------------------------------------------------------------------------
526{
527    // copie de optimizedBorder_Rosenfeld
528    // test d'existance de ex en local local
529
530    uint32 b = E[i - 1][j];
531    uint32 x = E[i][j];
532   
533    if (x) {
534        if (b) {
535            vuse2_Rosenfeld_Dist(b, x, T, D, alpha); // dist, local
536        }
537        else {
538            uint32 a = E[i - 1][j - 1];
539            if (a) {
540                vuse2_Rosenfeld_Dist(a, x, T, D, alpha); // dist, local
541            }
542        }
543    }
544}
545#endif // FAST && !FEATURES
546
547
548#if FAST && !FEATURES
549// ------------------------------------------------------------------------------------------------------------------------
550static void borderMerging_Fast_Rosenfeld_Dist(uint8 **X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha)
551// ------------------------------------------------------------------------------------------------------------------------
552{
553    // Prologue
554    optimizedBorderLeft_Rosenfeld_Dist(E, i, 0, T, D, alpha);
555    // Boucle principale
556    for (int j = 1; j < width - 1; j++) {
557        optimizedBorder_Rosenfeld_Dist(E, i, j, T, D, alpha);
558    }
559    // Epilogue
560    optimizedBorderRight_Rosenfeld_Dist(E, i, width - 1, T, D, alpha);
561}
562#endif // FAST && !FEATURES
563
564
565#if SLOW && !FEATURES
566// -------------------------------------------------------------------------------------------------------------------------
567static void borderMerging_Slow_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha)
568// -------------------------------------------------------------------------------------------------------------------------
569{
570    int j;
571   
572    uint32 eps;
573    uint32 e1, e2, e3, ex;
574    uint32 r1, r2, r3, rx;
575   
576    // --------------
577    // -- prologue --
578    // --------------
579    MCA_VERBOSE2(printf("[%s] i = %d\n", __func__, i));
580   
581    j = 0;
582    ex = E[i][j];
583   
584    if (ex) {
585       
586        MCA_VERBOSE2(printf("[%s] j = %d\n", __func__, j));
587       
588        e2 = E[i - 1][j];
589        e3 = E[i - 1][j + 1];
590
591        // test pour eviter acces distant
592        r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0;
593        r3 = e3 ? FindRoot_Dist(D, e3, alpha) : 0;
594
595        rx = T[ex];
596        rx = FindRoot_Dist(D, rx, alpha);
597 
598        MCA_VERBOSE2(printf("\n"));
599        MCA_VERBOSE2(printf("e2 = %4d -> %4d\n", e2, r2));
600        MCA_VERBOSE2(printf("e3 = %4d -> %4d\n", e3, r3));
601        MCA_VERBOSE2(printf("ex = %4d -> %4d\n", ex, rx));
602       
603        eps = ui32MinNonNul3(r2, r3, rx);
604       
605        // Quick-Union
606        if (r2 > eps) {
607            SetRoot_Rosenfeld_Dist(D, r2, eps, alpha);
608            MCA_VERBOSE2(printf("D[%4d] <- %d\n", r2, eps));
609        }
610        if (r3 > eps) {
611            SetRoot_Rosenfeld_Dist(D, r3, eps, alpha);
612            MCA_VERBOSE2(printf("D[%4d] <- %d\n", r3, eps));
613        }
614        if (rx > eps) {
615            SetRoot_Rosenfeld_Dist(D, rx, eps, alpha);
616            MCA_VERBOSE2(printf("D[%4d] <- %d\n", rx, eps));
617        }
618        MCA_VERBOSE2(printf("\n"));
619    }
620   
621    // -----------------------
622    // -- boucle principale --
623    // -----------------------
624   
625    for (j = 0 + 1; j < width - 1; j++) {
626   
627        ex = E[i][j];
628       
629        // que le cas general (pour faire un code simple)
630        if (ex) {
631            MCA_VERBOSE2(printf("[%s] j = %d\n", __func__, j));
632           
633            e1 = E[i - 1][j - 1];
634            e2 = E[i - 1][j];
635            e3 = E[i - 1][j + 1];
636       
637            // test pour eviter acces distant
638            r1 = e1 ? FindRoot_Dist(D, e1, alpha) : 0;
639            r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0;
640            r3 = e3 ? FindRoot_Dist(D, e3, alpha) : 0;
641
642            rx = T[ex];
643            rx = FindRoot_Dist(D, rx, alpha);
644
645            MCA_VERBOSE2(printf("\n"));
646            MCA_VERBOSE2(printf("e1 = %4d -> %4d\n", e1, r1));
647            MCA_VERBOSE2(printf("e2 = %4d -> %4d\n", e2, r2));
648            MCA_VERBOSE2(printf("e3 = %4d -> %4d\n", e3, r3));
649            MCA_VERBOSE2(printf("ex = %4d -> %4d\n", ex, rx));
650           
651            eps = ui32MinNonNul4(r1, r2, r3, rx);
652           
653            // Quick-Union
654            if (r1 > eps) {
655                SetRoot_Rosenfeld_Dist(D, r1, eps, alpha);
656                MCA_VERBOSE2(printf("D[%4d] <- %d\n", r1, eps));
657            }
658            if (r2 > eps) {
659                SetRoot_Rosenfeld_Dist(D, r2, eps, alpha);
660                MCA_VERBOSE2(printf("D[%4d] <- %d\n", r2, eps));
661            }
662            if (r3 > eps) {
663                SetRoot_Rosenfeld_Dist(D, r3, eps, alpha);
664                MCA_VERBOSE2(printf("D[%4d] <- %d\n", r3, eps));
665            }
666            if (rx > eps) {
667                SetRoot_Rosenfeld_Dist(D, rx, eps, alpha);
668                MCA_VERBOSE2(printf("D[%4d] <- %d\n", rx, eps));
669            }
670            MCA_VERBOSE2(printf("\n"));
671            // attention SetRoot fait un while inutile
672        }
673    }
674   
675    // --------------
676    // -- epilogue --
677    // --------------
678   
679    j = width - 1;
680    ex = E[i][j];
681   
682    if (ex) {
683       
684        MCA_VERBOSE2(printf("[%s] j = %d\n", __func__, j));
685       
686        e1 = E[i - 1][j - 1];
687        e2 = E[i - 1][j];
688
689        // test pour eviter acces distant
690        r1 = e1 ? FindRoot_Dist(D, e1, alpha) : 0;
691        r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0;
692
693        rx = T[ex];
694        rx = FindRoot_Dist(D, rx, alpha);
695
696        MCA_VERBOSE2(printf("\n"));
697        MCA_VERBOSE2(printf("e1 = %4d -> %4d\n", e1, r1));
698        MCA_VERBOSE2(printf("e2 = %4d -> %4d\n", e2, r2));
699        MCA_VERBOSE2(printf("ex = %4d -> %4d\n", ex, rx));
700       
701        eps = ui32MinNonNul3(r1, r2, rx);
702       
703        // Quick-Union
704        if (r1 > eps) {
705            SetRoot_Rosenfeld_Dist(D, r1, eps, alpha);
706            MCA_VERBOSE2(printf("D[%4d] <- %d\n", r1, eps));
707        }
708        if (r2 > eps) {
709            SetRoot_Rosenfeld_Dist(D, r2, eps, alpha);
710            MCA_VERBOSE2(printf("D[%4d] <- %d\n", r2, eps));
711        }
712        if (rx > eps) {
713            SetRoot_Rosenfeld_Dist(D, rx, eps, alpha);
714            MCA_VERBOSE2(printf("D[%4d] <- %d\n", rx, eps));
715        }
716        MCA_VERBOSE2(printf("\n"));
717    }
718    return;
719}
720#endif // SLOW && !FEATURES
721
722
723#if SLOW && FEATURES
724// ----------------------------------------------------------------------------------------------------------------------------------------------------
725static void borderMerging_Slow_Features_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
726// ----------------------------------------------------------------------------------------------------------------------------------------------------
727{
728    int j = 0;
729   
730    uint32 eps;
731   
732    uint32 e1, e2, e3, ex;
733    uint32 r1, r2, r3, rx;
734   
735    // --------------
736    // -- prologue --
737    // --------------
738    MCA_VERBOSE2(printf("[%s] i = %d\n", __func__, i));
739   
740    ex = E[i][j];
741   
742    if (ex) {
743       
744        MCA_VERBOSE2(printf("[%s] j = %d\n", __func__, j));
745       
746        e2 = E[i - 1][j];
747        e3 = E[i - 1][j + 1];
748       
749        if (e2 || e3) {
750       
751            // test pour eviter acces distant
752            r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0;
753            r3 = e3 ? FindRoot_Dist(D, e3, alpha) : 0;
754
755            rx = T[ex];
756            rx = FindRoot_Dist(D, rx, alpha);
757           
758            eps = ui32MinNonNul3(r2, r3, rx);
759           
760            MCA_VERBOSE2(printf("\n"));
761            MCA_VERBOSE2(printf("e2  = %5d -> r2 = %5d\n", e2, r2));
762            MCA_VERBOSE2(printf("e3  = %5d -> r3 = %5d\n", e3, r3));
763            MCA_VERBOSE2(printf("ex  = %5d -> rx = %5d\n", ex, rx));
764            MCA_VERBOSE2(printf("eps = %5d\n", eps));
765           
766            // Quick-Union
767            // @QM
768            if (r2 > eps) {
769                SetRoot_Features_Rosenfeld_Dist(D, r2, eps, alpha, F);
770                MCA_VERBOSE2(printf("D[%5d] <- %d\n", r2, eps));
771            }
772            if (r3 > 0) {
773                r3 = FindRoot_Dist(D, r3, alpha);
774            }
775            // Pour le cas où r2 == r3, il ne faut pas ajouter deux fois les features
776            //if (r3 > eps && r3 != r2) {
777            if (r3 > eps) {
778                SetRoot_Features_Rosenfeld_Dist(D, r3, eps, alpha, F);
779                MCA_VERBOSE2(printf("D[%5d] <- %d\n", r3, eps));
780            }
781            rx = FindRoot_Dist(D, rx, alpha);
782            //if (rx > eps && rx != r3 && rx != r2) {
783            if (rx > eps) {
784                SetRoot_Features_Rosenfeld_Dist(D, rx, eps, alpha, F);
785                MCA_VERBOSE2(printf("D[%5d] <- %d\n", rx, eps));
786            }
787            MCA_VERBOSE2(printf("---------------------------\n"));
788        }
789    }
790   
791    // -----------------------
792    // -- boucle principale --
793    // -----------------------
794   
795    for (j = 0 + 1; j < width - 1; j++) {
796       
797        ex = E[i][j];
798       
799        if (ex) {
800           
801            MCA_VERBOSE2(printf("[%s] j = %d\n", __func__, j));
802           
803            e1 = E[i - 1][j - 1];
804            e2 = E[i - 1][j];
805            e3 = E[i - 1][j + 1];
806           
807            if (e1 || e2 || e3) {
808                // test pour eviter un acces distant
809                r1 = e1 ? FindRoot_Dist(D, e1, alpha) : 0;
810                r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0;
811                r3 = e3 ? FindRoot_Dist(D, e3, alpha) : 0;
812
813                rx = T[ex];
814                rx = FindRoot_Dist(D, rx, alpha);
815               
816                eps = ui32MinNonNul4(r1, r2, r3, rx);
817
818                MCA_VERBOSE2(printf("\n"));
819                MCA_VERBOSE2(printf("e1  = %5d -> r1 = %5d\n", e1, r1));
820                MCA_VERBOSE2(printf("e2  = %5d -> r2 = %5d\n", e2, r2));
821                MCA_VERBOSE2(printf("e3  = %5d -> r3 = %5d\n", e3, r3));
822                MCA_VERBOSE2(printf("ex  = %5d -> rx = %5d\n", ex, rx));
823                MCA_VERBOSE2(printf("eps = %5d\n", eps));
824               
825                // Quick-Union
826                // @QM
827                if (r1 > eps) {
828                    SetRoot_Features_Rosenfeld_Dist(D, r1, eps, alpha, F);
829                    MCA_VERBOSE2(printf("D[%5d] <- %d\n", r1, eps));
830                }
831                if (r2 > 0) {
832                    r2 = FindRoot_Dist(D, r2, alpha);
833                }
834                //if (r2 > eps && r2 != r1) {
835                if (r2 > eps) {
836                    SetRoot_Features_Rosenfeld_Dist(D, r2, eps, alpha, F);
837                    MCA_VERBOSE2(printf("D[%5d] <- %d\n", r2, eps));
838                }
839                if (r3 > 0) {
840                    r3 = FindRoot_Dist(D, r3, alpha);
841                }
842                //if (r3 > eps && r3 != r2 && r3 != r1) {
843                if (r3 > eps) {
844                    SetRoot_Features_Rosenfeld_Dist(D, r3, eps, alpha, F);
845                    MCA_VERBOSE2(printf("D[%5d] <- %d\n", r3, eps));
846                }
847                rx = FindRoot_Dist(D, rx, alpha);
848                //if (rx > eps && rx != r3 && rx != r2 && rx != r1) {
849                if (rx > eps) {
850                    SetRoot_Features_Rosenfeld_Dist(D, rx, eps, alpha, F);
851                    MCA_VERBOSE2(printf("D[%5d] <- %d\n", rx, eps));
852                }
853                MCA_VERBOSE2(puts("---------------------------\n"));
854               
855                // attention SetRoot fait un while inutile
856            }
857        }
858    }
859   
860    // --------------
861    // -- epilogue --
862    // --------------
863   
864    j = width - 1;
865    ex = E[i][j];
866   
867    if (ex) {
868       
869        MCA_VERBOSE2(printf("[%s] j = %d\n", __func__, j));
870       
871        e1 = E[i - 1][j - 1];
872        e2 = E[i - 1][j];
873       
874        if (e1 || e2) {
875       
876            // test pour eviter acces distant
877            r1 = e1 ? FindRoot_Dist(D, e1, alpha) : 0;
878            r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0;
879
880            rx = T[ex];
881            rx = FindRoot_Dist(D, rx, alpha);
882           
883            eps = ui32MinNonNul3(r1, r2, rx);
884           
885            MCA_VERBOSE2(printf("\n"));
886            MCA_VERBOSE2(printf("e1  = %5d -> r1 = %5d\n", e1, r1));
887            MCA_VERBOSE2(printf("e2  = %5d -> r2 = %5d\n", e2, r2));
888            MCA_VERBOSE2(printf("ex  = %5d -> rx = %5d\n", ex, rx));
889            MCA_VERBOSE2(printf("eps = %5d\n", eps));
890           
891            // Quick-Union
892            if (r1 > eps) {
893                SetRoot_Features_Rosenfeld_Dist(D, r1, eps, alpha, F);
894                MCA_VERBOSE2(printf("D[%5d] <- %d\n", r1, eps));
895            }
896            if (r2 > 0) {
897                r2 = FindRoot_Dist(D, r2, alpha);
898            }
899            //if (r2 > eps && r2 != r1) {
900            if (r2 > eps) {
901                SetRoot_Features_Rosenfeld_Dist(D, r2, eps, alpha, F);
902                MCA_VERBOSE2(printf("D[%5d] <- %d\n", r2, eps));
903            }
904            rx = FindRoot_Dist(D, rx, alpha);
905            //if (rx > eps && rx != r2 && rx != r1) {
906            if (rx > eps) {
907                SetRoot_Features_Rosenfeld_Dist(D, rx, eps, alpha, F);
908                MCA_VERBOSE2(printf("D[%5d] <- %d\n", rx, eps));
909            }
910            MCA_VERBOSE2(printf("---------------------------\n"));
911        }
912    }
913    return;
914}
915#endif // SLOW && FEATURES
916
917
918#if FAST && FEATURES && !PARMERGE
919// --------------------------------------------------------------------------------------------------------------------------
920void optimizedBorder_Features_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
921// --------------------------------------------------------------------------------------------------------------------------
922{
923    // copie de optimizedBorder_Rosenfeld
924    uint32 a, b, c, x;
925   
926    x = E[i][j];
927   
928    if (x) {
929        b = E[i - 1][j];
930        if (b) {
931            vuse2_Features_Rosenfeld_Dist(b, x, T, D, alpha, F); // dist, local
932        }
933        else {
934            c = E[i - 1][j + 1];
935            if (c) {
936                a = E[i - 1][j - 1];
937                if (a) {
938                    vuse3_Features_Rosenfeld_Dist(a, c, x, T, D, alpha, F); // dist, local
939                }
940                else {
941                    vuse2_Features_Rosenfeld_Dist(c, x, T, D, alpha, F); // dist, local
942                }
943            }
944            else {
945                a = E[i - 1][j - 1];
946                if (a) {
947                    vuse2_Features_Rosenfeld_Dist(a, x, T, D, alpha, F); // dist, local
948                }
949            }
950        }
951    }
952}
953#endif // FAST && FEATURES && !PARMERGE
954
955
956#if FAST && FEATURES && !PARMERGE
957// ------------------------------------------------------------------------------------------------------------------------------
958void optimizedBorderLeft_Features_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
959// ------------------------------------------------------------------------------------------------------------------------------
960{
961    uint32 x = E[i][j];
962   
963    if (x) {
964        uint32 b = E[i - 1][j];
965        if (b) {
966            vuse2_Features_Rosenfeld_Dist(b, x, T, D, alpha, F); // dist, local
967        }
968        else {
969            uint32 c = E[i - 1][j + 1];
970            if (c) {
971                vuse2_Features_Rosenfeld_Dist(c, x, T, D, alpha, F); // dist, local
972            }
973        }
974    }
975}
976#endif // FAST && FEATURES && !PARMERGE
977
978
979#if FAST && FEATURES && !PARMERGE
980// -------------------------------------------------------------------------------------------------------------------------------
981void optimizedBorderRight_Features_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
982// -------------------------------------------------------------------------------------------------------------------------------
983{
984    // copie de optimizedBorder_Rosenfeld
985    // test d'existance de ex en local local
986   
987    uint32 x = E[i][j];
988   
989    if (x) {
990        uint32 b = E[i - 1][j];
991        if (b) {
992            vuse2_Features_Rosenfeld_Dist(b, x, T, D, alpha, F); // dist, local
993        }
994        else {
995            uint32 a = E[i - 1][j - 1];
996            if (a) {
997                vuse2_Features_Rosenfeld_Dist(a, x, T, D, alpha, F); // dist, local
998            }
999        }
1000    }
1001}
1002#endif // FAST && FEATURES && !PARMERGE
1003
1004
1005#if FAST && FEATURES && PARMERGE
1006// -----------------------------------------------------------------------------------------------------------------------------------
1007void optimizedBorder_Parallel_Features_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
1008// -----------------------------------------------------------------------------------------------------------------------------------
1009{
1010    // copie de optimizedBorder_Rosenfeld
1011    uint32 a, b, c, x;
1012   
1013    x = E[i][j];
1014   
1015    if (x) {
1016        b = E[i - 1][j];
1017        if (b) {
1018            vuse2_Parallel_Features_Rosenfeld_Dist(b, x, T, D, alpha, F); // dist, local
1019        }
1020        else {
1021            c = E[i - 1][j + 1];
1022            if (c) {
1023                a = E[i - 1][j - 1];
1024                if (a) {
1025                    vuse3_Parallel_Features_Rosenfeld_Dist(a, c, x, T, D, alpha, F); // dist, local
1026                }
1027                else {
1028                    vuse2_Parallel_Features_Rosenfeld_Dist(c, x, T, D, alpha, F); // dist, local
1029                }
1030            }
1031            else {
1032                a = E[i - 1][j - 1];
1033                if (a) {
1034                    vuse2_Parallel_Features_Rosenfeld_Dist(a, x, T, D, alpha, F); // dist, local
1035                }
1036            }
1037        }
1038    }
1039}
1040#endif // FAST && FEATURES && PARMERGE
1041
1042
1043#if FAST && FEATURES && PARMERGE
1044// ---------------------------------------------------------------------------------------------------------------------------------------
1045void optimizedBorderLeft_Parallel_Features_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
1046// ---------------------------------------------------------------------------------------------------------------------------------------
1047{
1048    uint32 x = E[i][j];
1049   
1050    if (x) {
1051        uint32 b = E[i - 1][j];
1052        if (b) {
1053            vuse2_Parallel_Features_Rosenfeld_Dist(b, x, T, D, alpha, F); // dist, local
1054        }
1055        else {
1056            uint32 c = E[i - 1][j + 1];
1057            if (c) {
1058                vuse2_Parallel_Features_Rosenfeld_Dist(c, x, T, D, alpha, F); // dist, local
1059            }
1060        }
1061    }
1062}
1063#endif // FAST && FEATURES && PARMERGE
1064
1065
1066#if FAST && FEATURES && PARMERGE
1067// ----------------------------------------------------------------------------------------------------------------------------------------
1068void optimizedBorderRight_Parallel_Features_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
1069// ----------------------------------------------------------------------------------------------------------------------------------------
1070{
1071    // copie de optimizedBorder_Rosenfeld
1072    // test d'existance de ex en local local
1073   
1074    uint32 x = E[i][j];
1075   
1076    if (x) {
1077        uint32 b = E[i - 1][j];
1078        if (b) {
1079            vuse2_Parallel_Features_Rosenfeld_Dist(b, x, T, D, alpha, F); // dist, local
1080        }
1081        else {
1082            uint32 a = E[i - 1][j - 1];
1083            if (a) {
1084                vuse2_Parallel_Features_Rosenfeld_Dist(a, x, T, D, alpha, F); // dist, local
1085            }
1086        }
1087    }
1088}
1089#endif // FAST && FEATURES && PARMERGE
1090
1091
1092#if FAST && FEATURES
1093// ---------------------------------------------------------------------------------------------------------------------------------------------
1094void borderMerging_Fast_Features_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
1095// ---------------------------------------------------------------------------------------------------------------------------------------------
1096{
1097    MCA_VERBOSE2(printf("[%s]", __func__));
1098   
1099#if PARMERGE
1100    optimizedBorderLeft_Parallel_Features_Rosenfeld_Dist(E, i, 0, T, D, alpha, F);
1101#else
1102    optimizedBorderLeft_Features_Rosenfeld_Dist(E, i, 0, T, D, alpha, F);
1103#endif
1104   
1105    for (int j = 1; j < width - 1; j++) {
1106#if PARMERGE
1107        optimizedBorder_Parallel_Features_Rosenfeld_Dist(E, i, j, T, D, alpha, F);
1108#else
1109        optimizedBorder_Features_Rosenfeld_Dist(E, i, j, T, D, alpha, F);
1110#endif
1111    }
1112   
1113#if PARMERGE
1114    optimizedBorderRight_Parallel_Features_Rosenfeld_Dist(E, i, width - 1, T, D, alpha, F);
1115#else
1116    optimizedBorderRight_Features_Rosenfeld_Dist(E, i, width - 1, T, D, alpha, F);
1117#endif
1118}
1119#endif // FAST && FEATURES
1120
1121
1122#if !FEATURES
1123// --------------------------------------------------------------------------------------------------------------------
1124static void borderMerging_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha)
1125// --------------------------------------------------------------------------------------------------------------------
1126{
1127#if SLOW
1128    borderMerging_Slow_Rosenfeld_Dist(X, i, width, E, T, D, alpha);
1129#elif FAST
1130    borderMerging_Fast_Rosenfeld_Dist(X, i, width, E, T, D, alpha);
1131#else
1132#error "Please define SLOW or FAST for the Rosenfeld version"
1133#endif
1134}
1135#endif // !FEATURES
1136
1137
1138#if FEATURES
1139// -----------------------------------------------------------------------------------------------------------------------------------------------
1140static void borderMerging_Features_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
1141// -----------------------------------------------------------------------------------------------------------------------------------------------
1142{
1143#if SLOW
1144    borderMerging_Slow_Features_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);
1145#elif FAST
1146    borderMerging_Fast_Features_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);
1147#else
1148#error "Please define SLOW or FAST for the Rosenfeld version"
1149#endif
1150}
1151#endif // FEATURES
1152
1153
1154// ----------------------------------------------------------------------------------------------------
1155static uint32 line0Labeling_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne)
1156// ----------------------------------------------------------------------------------------------------
1157{
1158    int j;
1159    uint8 x;
1160    uint32 e4;
1161    uint32 r4;
1162   
1163    // prologue : j = 0
1164    x = X[i][0];
1165    if (x) {
1166        E[i][0] = ++ne;
1167    }
1168    else {
1169        E[i][0] = 0;
1170    }
1171   
1172    // boucle et epilogue j = [1..width-1]
1173    for (j = 1; j <= width - 1; j++) {
1174        x = X[i][j];
1175        if (x)  {
1176            e4 = E[i][j - 1];
1177           
1178            if (e4 == 0) {
1179                E[i][j] = ++ne;
1180            }
1181            else {
1182                E[i][j] = e4;
1183            }
1184        }
1185        else {
1186            E[i][j] = 0;
1187        }
1188    }
1189    return ne;
1190}
1191
1192
1193#if SLOW
1194// --------------------------------------------------------------------------------------------------------
1195static uint32 lineLabeling_Slow_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne)
1196// --------------------------------------------------------------------------------------------------------
1197{
1198    // version lineLabeling_Rosenfeld_UF_QU_8C avec Quick-Union
1199   
1200    int j;
1201   
1202    uint8 x;
1203    uint32 e;
1204    uint32 e1, e2, e3, e4;
1205    uint32 r1, r2, r3, r4;
1206   
1207    // --------------
1208    // -- prologue --
1209    // --------------
1210   
1211    j = 0;
1212    x = X[i][j];
1213   
1214    if (x) {
1215       
1216        e2 = E[i - 1][j];
1217        e3 = E[i - 1][j + 1];
1218       
1219        // nouvel element
1220        if (e2 == 0 && e3 == 0) {
1221            e = ++ne;
1222            E[i][j] = e;
1223        }
1224        else {
1225            // etiquettes identiques
1226            if (e2 == e3) {
1227                e = e2;
1228                E[i][j] = e; 
1229            }
1230            else {   
1231                // cas general
1232                r2 = (e2 == 0) ? 0 : FindRoot(T, e2);
1233                r3 = (e3 == 0) ? 0 : FindRoot(T, e3);
1234               
1235                e = ui32MinNonNul2(r2, r3);
1236               
1237                // Quick-Union
1238                if (r2 > e) {
1239                    T[r2] = e;
1240                }
1241                if (r3 > e) {
1242                    T[r3] = e;
1243                }
1244                E[i][j] = e;
1245            }
1246        }
1247    }
1248    else {
1249        E[i][j] = 0;
1250    } // x
1251   
1252    // -----------------------
1253    // -- boucle principale --
1254    // -----------------------
1255   
1256    for (j = 0 + 1; j < width - 1; j++) {
1257       
1258        x = X[i][j];
1259       
1260        if (x)  {
1261            e1 = E[i - 1][j - 1];
1262            e2 = E[i - 1][j];
1263            e3 = E[i - 1][j + 1];
1264            e4 = E[i][j - 1];
1265           
1266            // nouvel element
1267            if (e1 == 0 && e2 == 0 && e3 == 0 && e4 == 0) {
1268                e = ++ne;
1269                E[i][j] = e;
1270            }
1271            else {
1272                // etiquettes identiques
1273                if (e1 == e2 && e1 == e3 && e1 == e4) {
1274                    e = e1;
1275                    E[i][j] = e;
1276                }
1277                else {
1278                    // cas general
1279                    r1 = (e1 == 0) ? 0 : FindRoot(T, e1);
1280                    r2 = (e2 == 0) ? 0 : FindRoot(T, e2);
1281                    r3 = (e3 == 0) ? 0 : FindRoot(T, e3);
1282                    r4 = (e4 == 0) ? 0 : FindRoot(T, e4);
1283                   
1284                    e = ui32MinNonNul4(r1, r2, r3, r4);
1285                   
1286                    // Quick-Union
1287                    if (r1 > e) {
1288                        T[r1] = e;
1289                    }
1290                    if (r2 > e) {
1291                        T[r2] = e;
1292                    }
1293                    if (r3 > e) {
1294                        T[r3] = e;
1295                    }
1296                    if (r4 > e) {
1297                        T[r4] = e;
1298                    }
1299                    E[i][j] = e;
1300                }
1301            }
1302        }
1303        else {
1304            E[i][j] = 0;
1305        } // x
1306    } // j
1307   
1308    // --------------
1309    // -- epilogue --
1310    // --------------
1311    j = width - 1;
1312    x = X[i][j];
1313   
1314    if (x) {
1315        e1 = E[i - 1][j - 1];
1316        e2 = E[i - 1][j];
1317        e4 = E[i][j - 1];
1318       
1319        // nouvel element
1320        if (e1 == 0 && e2 == 0 && e4 == 0) {
1321            e = ++ne;
1322            E[i][j] = e;
1323        }
1324        else {
1325            // etiquettes identiques
1326            if (e1 == e2 && e1 == e4) {
1327                e = e1;
1328                E[i][j] = e;
1329            }
1330            else {
1331                // cas general
1332                r1 = (e1 == 0) ? 0 : FindRoot(T, e1);
1333                r2 = (e2 == 0) ? 0 : FindRoot(T, e2);
1334                r4 = (e4 == 0) ? 0 : FindRoot(T, e4);
1335               
1336                e = ui32MinNonNul3(r1, r2, r4);
1337               
1338                // Quick-Union
1339                if (r1 > e) {
1340                    T[r1] = e;
1341                }
1342                if (r2 > e) {
1343                    T[r2] = e;
1344                }
1345                if (r4 > e) {
1346                    T[r4] = e;
1347                }
1348                E[i][j] = e;
1349            }
1350        }
1351    }
1352    else {
1353        E[i][j] = 0;
1354    } // x
1355   
1356    return ne;
1357}
1358#endif // SLOW
1359
1360
1361#if FAST
1362// ---------------------------------------------------------------------------------------------
1363static uint32 optimizedAccessLeft_DT_Rosenfeld(uint32 ** E, int i, int j, uint32 * T, uint32 ne)
1364// ---------------------------------------------------------------------------------------------
1365{
1366    // Decision Tree 8-connexe avec Quick-Union
1367    uint32 b, c, e;
1368   
1369    b = E[i - 1][j];
1370    if (b) {
1371        e = use1_QU_Rosenfeld(b, T);
1372    }
1373    else {
1374        c = E[i - 1][j + 1];
1375        if (c) {
1376            e = use1_QU_Rosenfeld(c, T);
1377        }
1378        else {
1379            e = ++ne;
1380        }
1381    }
1382    E[i][j] = e;
1383    return ne;
1384}
1385#endif // FAST
1386
1387
1388#if FAST
1389// ----------------------------------------------------------------------------------------------
1390static uint32 optimizedAccessRight_DT_Rosenfeld(uint32 ** E, int i, int j, uint32 * T, uint32 ne)
1391// ----------------------------------------------------------------------------------------------
1392{
1393    // Decision Tree 8-connexe avec Quick-Union
1394    uint32 a, b, d, e;
1395   
1396    b = E[i - 1][j];
1397    if (b) {
1398        e = use1_QU_Rosenfeld(b, T);
1399    }
1400    else {
1401        a = E[i - 1][j - 1];
1402        if (a) {
1403            e = use1_QU_Rosenfeld(a, T);
1404        }
1405        else {
1406            d = E[i][j - 1];
1407            if (d) {
1408                e = use1_QU_Rosenfeld(d, T);
1409            }
1410            else {
1411                e = ++ne;
1412            }
1413        }
1414    }
1415    E[i][j] = e;
1416    return ne;
1417}
1418#endif // FAST
1419
1420
1421#if FAST
1422// -----------------------------------------------------------------------------------------
1423static uint32 optimizedAccess_DT_Rosenfeld(uint32 ** E, int i, int j, uint32 * T, uint32 ne)
1424// -----------------------------------------------------------------------------------------
1425{
1426    // Decision Tree 8-connexe avec Quick-Union
1427    uint32 a, b, c, d, e;
1428   
1429    b = E[i - 1][j];
1430    if (b) {
1431        e = use1_QU_Rosenfeld(b, T);
1432    }
1433    else {
1434        c = E[i - 1][j + 1];
1435        if (c) {
1436            a = E[i - 1][j - 1];
1437            if (a) {
1438                e = use2_QU_Rosenfeld(a, c, T);
1439            }
1440            else {
1441                d = E[i][j - 1];
1442                if (d) {
1443                    e = use2_QU_Rosenfeld(c, d, T);
1444                }
1445                else {
1446                    e = use1_QU_Rosenfeld(c, T);
1447                }
1448            }
1449        }
1450        else {
1451            a = E[i - 1][j - 1];
1452            if (a) {
1453                e = use1_QU_Rosenfeld(a, T);
1454            }
1455            else {
1456                d = E[i][j - 1];
1457                if (d) {
1458                    e = use1_QU_Rosenfeld(d, T);
1459                }
1460                else {
1461                    e = ++ne;
1462                }
1463            }
1464        }
1465    }
1466    E[i][j] = e;
1467    return ne;
1468}
1469#endif // FAST
1470
1471
1472
1473#if FAST
1474// --------------------------------------------------------------------------------------------------------
1475static uint32 lineLabeling_Fast_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne)
1476// --------------------------------------------------------------------------------------------------------
1477{
1478    uint8 x;
1479    // avec DT et QU
1480    // Left Border
1481    x = X[i][0];
1482    if (x) {
1483        ne = optimizedAccessLeft_DT_Rosenfeld(E, i, 0, T, ne);
1484    }
1485    else {
1486        E[i][0] = 0;
1487    }
1488    // Middle
1489    for (int j = 1; j < width - 1; j++) {
1490        uint8 x = X[i][j];
1491        if (x) {
1492            ne = optimizedAccess_DT_Rosenfeld(E, i, j, T, ne);
1493        }
1494        else {
1495            E[i][j] = 0;
1496        }
1497    }
1498    // Right Border
1499    x = X[i][width - 1];
1500    if (x) {
1501        ne = optimizedAccessRight_DT_Rosenfeld(E, i, width - 1, T, ne);
1502    }
1503    else {
1504        E[i][width - 1] = 0;
1505    }
1506    return ne;
1507}
1508#endif // FAST
1509
1510
1511// ---------------------------------------------------------------------------------------------------
1512static uint32 lineLabeling_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne)
1513// ---------------------------------------------------------------------------------------------------
1514{
1515#if SLOW
1516    return lineLabeling_Slow_Rosenfeld(X, i, width, E, T, ne);
1517#elif FAST
1518    return lineLabeling_Fast_Rosenfeld(X, i, width, E, T, ne);
1519#else
1520#error "Please define SLOW or FAST for the Rosenfeld version"
1521#endif
1522}
1523
1524
1525// -----------------------------------------------------------------------
1526static uint32 countTable_Range_Rosenfeld(uint32 * T, uint32 e0, uint32 e1)
1527// -----------------------------------------------------------------------
1528{
1529    uint32 e;
1530    uint32 nr = 0; // nombre de racines = de composantes connexes
1531   
1532    for (e = e0; e <= e1; e++) {
1533        if (e == T[e]) {
1534            nr += 1;
1535        }
1536    }
1537    return nr;
1538}
1539
1540
1541#if !FEATURES
1542// ---------------------------------------------------------------------
1543static void solveTable_Range_Rosenfeld(uint32 * T, uint32 e0, uint32 e1)
1544// ---------------------------------------------------------------------
1545{
1546    uint32 e, r;
1547   
1548    for (e = e0; e <= e1; e++) {
1549        r = T[T[e]];
1550        if (r < e) {
1551            T[e] = r; // racine de la classe d'equivalence
1552        }
1553    }
1554}
1555#endif // !FEATURES
1556
1557
1558#if FEATURES
1559// ----------------------------------------------------------------------------------------------------------
1560static void solveTable_solveFeatures_Range_Rosenfeld(uint32 * T, uint32 e0, uint32 e1, RegionStats * Stats)
1561// ----------------------------------------------------------------------------------------------------------
1562{
1563    uint32 e, r;
1564   
1565    for (e = e0; e <= e1; e++) {
1566        r = T[T[e]];
1567        assert(r != 0);
1568        if (r < e) {
1569            T[e] = r; // racine de la classe d'equivalence
1570            RegionStats_Accumulate_Stats1_From_Index(Stats, r, e);
1571        }
1572    }
1573}
1574#endif // FEATURES
1575
1576
1577#if !FEATURES
1578// -------------------------------------
1579void MCA_Label_Rosenfeld_PAR1(MCA * mca)
1580// -------------------------------------
1581{
1582    if (mca->p == 0) { 
1583        printf("*** %s ***\n", __func__);
1584    }
1585   
1586    CLOCK_THREAD_START_STEP(mca->p, 0);
1587
1588    int i0 = mca->i0;
1589    int i1 = mca->i1;
1590    int width = mca->width; 
1591    uint32 e0 = mca->e0;
1592    uint32 e1 = mca->e1;
1593    uint32 ne = e0 - 1;
1594    uint32 nr = 0;
1595
1596    // local memory zones
1597    uint8 **  X = mca->X;
1598    uint32 ** E = mca->E;
1599    uint32 *  T = mca->T;
1600
1601    if (mca->p == 0) {
1602        set_ui32vector_j(T, e0 - 1, e1); // car e0 = 1, on a besoin que T[0] = 0 pour FindRoot
1603    }
1604    else {
1605        set_ui32vector_j(T, e0, e1);
1606    }
1607
1608    MCA_VERBOSE2(display_ui8matrix_positive(X, i0, i1, 0, width - 1, 5, "Xp"); printf("\n"));
1609
1610    ne = line0Labeling_Rosenfeld(X, i0, width, E, T, ne);
1611    for (int i = i0 + 1; i <= i1; i++) {
1612        ne = lineLabeling_Rosenfeld(X, i, width, E, T, ne);
1613    }
1614
1615    MCA_VERBOSE2(display_ui32matrix_positive(E, i0, i1, 0, width - 1, 5, "Ep"); printf("\n"));
1616    if (mca->p == 0) {
1617        MCA_VERBOSE2(display_ui32vector_number(T, e0, ne, "%5d", "Tp_avant"));
1618    }
1619
1620    // fermeture transitive sans pack
1621    solveTable_Range_Rosenfeld(T, e0, ne);
1622    mca->ne = ne; // Plus grande etiquette de l'intervalle [e0..e1]
1623
1624    MCA_VERBOSE2(nr = countTable_Range_Rosenfeld(T, e0, ne));
1625    MCA_VERBOSE2(printf("p = %d : e = [%d..%d] -> ne = %d -> nr = %d\n", mca->p, e0, ne, (ne - e0 + 1), nr));
1626    if (mca->p == 0) {
1627        MCA_VERBOSE2(display_ui32vector_number(T, e0, ne, "%5d", "Tp_apres"));
1628    }
1629   
1630    CLOCK_THREAD_END_STEP(mca->p, 0);
1631}
1632#endif // !FEATURES
1633
1634
1635#if !FEATURES
1636// -------------------------------------
1637void MCA_Label_Rosenfeld_PYR2(MCA * mca)
1638// -------------------------------------
1639{
1640    // input
1641    int p = mca->p;
1642    int nb_level = mca->nb_level;
1643
1644    if (mca->p == 0) {
1645        printf("*** %s ***\n", __func__);
1646    }
1647   
1648    // ------------------------------
1649    // -- pyramidal border merging --
1650    // ------------------------------
1651   
1652    // local variables
1653    int i = mca->i0;
1654    int width = mca->width;
1655    int alpha = mca->alpha;
1656    uint32 e0 = mca->e0;
1657    uint32 e1 = mca->ne;
1658
1659    // local memory zones
1660    uint8 **  X = mca->X;
1661    uint32 ** E = mca->E;
1662    uint32 *  T = mca->T;
1663    uint32 ** D = mca->D;
1664
1665    CLOCK_THREAD_START_STEP(p, 1);
1666#if PYR_BARRIERS
1667    // Version optimisée qui fait faire un break aux processeurs qui n'ont plus
1668    // à faire de merge.
1669    // Implique de pré-calculer le nombre de threads à chaque barriÚre
1670    if (p != 0) { // thread 0 never has any merge to do
1671        int been_active = 0;
1672        for (int level = 0; level < nb_level; level++) {
1673            if ((p + (1 << level)) % (1 << (level + 1)) == 0) {
1674                borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha);  // en (i) et (i-1)
1675                been_active = 1;
1676            }
1677            else if (been_active) {
1678                break;
1679            }
1680            pthread_barrier_wait(&mca->barriers[level]);
1681        }
1682    }
1683    pthread_barrier_wait(&main_barrier);
1684#else
1685    for (int level = 1; level <= nb_level; level++) {
1686        if ((p + (1 << (level - 1))) % (1 << level) == 0) {
1687            // thread actif
1688            borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha);  // en (i) et (i-1)
1689        }
1690        pthread_barrier_wait(&main_barrier);
1691    }
1692#endif
1693    CLOCK_THREAD_END_STEP(p, 1);
1694   
1695
1696    // ---------------------------------
1697    // -- parallel transitive closure --
1698    // ---------------------------------
1699   
1700    CLOCK_THREAD_START_STEP(p, 2);
1701    for (uint32 e = e0; e <= e1; e++) {
1702        uint32 r = T[e]; // acces local
1703        if (r < e) {
1704            r = FindRoot_Dist(D, e, alpha); // acces distant
1705            T[e] = r; // @QM était en dehors du "if" (je pense que déjà demandé)
1706        }
1707        MCA_VERBOSE2(printf("p%d : T[%d] <- %d\n", p, e, r));
1708    }
1709    CLOCK_THREAD_END_STEP(p, 2);
1710}
1711#endif // !FEATURES
1712
1713
1714// -------------------------------------
1715void MCA_Label_Rosenfeld_PAR3(MCA * mca)
1716// -------------------------------------
1717{
1718    // input
1719    if (mca->p == 0) {
1720        printf("*** %s ***\n", __func__);
1721    }
1722   
1723    int i0 = mca->i0;
1724    int i1 = mca->i1;
1725    int j0 = 0;
1726    int j1 = mca->width - 1;
1727
1728    uint32 ** E = mca->E;
1729    uint32 * T = mca->T;
1730
1731    CLOCK_THREAD_START_STEP(mca->p, 3);
1732    for (int i = i0; i <= i1; i++) {
1733        for (int j = j0; j <= j1; j++) {
1734            uint32 e = E[i][j];
1735            if (e != 0) {
1736                E[i][j] = T[e];
1737            }
1738        }
1739    }
1740    CLOCK_THREAD_END_STEP(mca->p, 3);
1741}
1742
1743
1744#if FEATURES
1745// -----------------------------------------------------
1746static void MCA_Label_Features_Rosenfeld_PAR1(MCA * mca)
1747// -----------------------------------------------------
1748{
1749    if (mca->p == 0) { 
1750        printf("*** %s ***\n", __func__);
1751    }
1752   
1753    CLOCK_THREAD_START_STEP(mca->p, 0);
1754
1755    int i0 = mca->i0;
1756    int i1 = mca->i1;
1757    int width = mca->width;
1758
1759    uint32 e0 = mca->e0;
1760    uint32 e1 = mca->e1;
1761    uint32 ne = e0 - 1;
1762    uint32 nr = 0;
1763
1764    // local memory zones
1765    uint8 **  X = mca->X;
1766    uint32 ** E = mca->E;
1767    uint32 *  T = mca->T;
1768
1769    RegionStats * stats = mca->stats;
1770
1771    // reset sous optimal (pour le moment = voir region32)
1772    if (mca->p == 0) {
1773        set_ui32vector_j(T, e0 - 1, e1); // car e0 = 1, on a besoin que T[0] = 0 pour FindRoot
1774        zero_RegionStatsVector(stats, e0 - 1, e1);
1775    }
1776    else {
1777        set_ui32vector_j(T, e0, e1);
1778        zero_RegionStatsVector(stats, e0, e1);
1779    }
1780
1781    if (mca->p == 0) {
1782        MCA_DISPLAY2(display_ui8matrix_positive(X, i0, i1, 0, width - 1, 5, "Xp"); printf("\n"));
1783    }
1784
1785    // ---------------------------- //
1786    // -- Etiquetage d'une bande -- //
1787    // ---------------------------- //
1788
1789    ne = line0Labeling_Rosenfeld(X, i0, width, E, T, ne);
1790    lineFeaturesComputation(E, i0, width, stats);
1791
1792    for (int i = i0 + 1; i <= i1; i++) {
1793        ne = lineLabeling_Rosenfeld(X, i, width, E, T, ne); // Slow or Fast
1794        lineFeaturesComputation(E, i, width, stats);
1795    }
1796    mca->ne = ne; //plus grande etiquette de l'intervalle [e0..e1]
1797
1798    if (mca->p == 0) {
1799        MCA_VERBOSE2(printf("ne = %d\n", ne));
1800        MCA_DISPLAY2(display_ui32matrix_positive(E, i0, i1, 0, width - 1, 5, "Ep"); printf("\n"));
1801        MCA_DISPLAY2(display_ui32vector_number(T, e0, ne, "%5d", "Tp_avant"));
1802    }
1803
1804    // ------------------------------------------------------ //
1805    // -- Fermeture transitive sans pack de chaque table T -- //
1806    // ------------------------------------------------------ //
1807
1808    solveTable_solveFeatures_Range_Rosenfeld(T, e0, ne, stats);
1809
1810    if (mca->p == 0) {
1811        MCA_VERBOSE2(nr = countTable_Range_Rosenfeld(T, e0, ne);
1812                printf("p = %d : e = [%d..%d] -> ne = %d -> nr = %d\n", mca->p, e0, ne, (ne - e0 + 1), nr));
1813        MCA_DISPLAY2(display_ui32vector_number(T, e0, ne, "%5d", "Tp_apres"));
1814    }
1815    CLOCK_THREAD_END_STEP(mca->p, 0);
1816}
1817#endif // FEATURES
1818
1819
1820#if FEATURES && !PARMERGE
1821// -----------------------------------------------------
1822static void MCA_Label_Features_Rosenfeld_PYR2(MCA * mca)
1823// -----------------------------------------------------
1824{
1825    int p = mca->p;
1826    int nb_level = mca->nb_level;
1827
1828    if (mca->p == 0) {
1829        printf("*** %s ***\n", __func__);
1830    }
1831   
1832    // ------------------------------
1833    // -- pyramidal border merging --
1834    // ------------------------------
1835   
1836    // local variables
1837    int i = mca->i0;
1838    int width = mca->width;
1839    int alpha = mca->alpha;
1840    uint32 e0 = mca->e0;
1841    uint32 e1 = mca->ne;
1842
1843    // local memory zones
1844    uint8 **  X = mca->X;
1845    uint32 ** E = mca->E;
1846    uint32 *  T = mca->T;
1847    uint32 ** D = mca->D;
1848    RegionStats ** F = mca->F;
1849
1850    CLOCK_THREAD_START_STEP(p, 1);
1851#if PYR_BARRIERS
1852    // Version optimisée qui fait faire un break aux processeurs qui n'ont plus
1853    // à faire de merge.
1854    // Implique de pré-calculer le nombre de threads à chaque barriÚre
1855    if (p != 0) { // thread 0 never has any merge to do
1856        int been_active = 0;
1857        for (int level = 0; level < nb_level; level++) {
1858            if ((p + (1 << level)) % (1 << (level + 1)) == 0) {
1859                borderMerging_Features_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);  // (i) et (i-1)
1860                been_active = 1;
1861            }
1862            else if (been_active) {
1863                break;
1864            }
1865            pthread_barrier_wait(&mca->barriers[level]);
1866        }
1867    }
1868    pthread_barrier_wait(&main_barrier);
1869#else
1870    for (int level = 1; level <= nb_level; level++) {
1871        if ((p + (1 << (level - 1))) % (1 << level) == 0) {
1872            // thread actif
1873            borderMerging_Features_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);  // (i) et (i-1)
1874        }
1875        pthread_barrier_wait(&main_barrier);
1876    }
1877#endif
1878    CLOCK_THREAD_END_STEP(p, 1);
1879
1880
1881    /**
1882     * To remove?
1883    // -- Affichage de debug
1884    if (mca->p == 0) {
1885        MCA_VERBOSE1(puts("-----------------------------"));
1886        MCA_VERBOSE1(puts("[PYR2]: avant pack sequentiel"));
1887        MCA_VERBOSE1(puts("-----------------------------"));
1888   
1889        for (int p = 0; p < mca->np; p++) {
1890   
1891            MCA* mca_par = mcas[p];
1892            uint32 e0 = mca_par->e0;
1893            uint32 e1 = mca_par->ne;
1894           
1895            uint32*  T = mca_par->T;
1896            RegionStats* Stats = mca_par->Stats;
1897       
1898            RegionStats_DisplayStats_Sparse(T, e0, e1, Stats, NULL);
1899            puts("");
1900        }
1901    }
1902    */
1903
1904    // ---------------------------------
1905    // -- parallel transitive closure --
1906    // ---------------------------------
1907    // identique a la version sans Features
1908     
1909    CLOCK_THREAD_START_STEP(p, 2);
1910    for (uint32 e = e0; e <= e1; e++) {
1911        uint32 r = T[e]; // acces local
1912        if (r < e) {
1913            r = FindRoot_Dist(D, e, alpha); // acces distant
1914            T[e] = r;
1915        }
1916        MCA_VERBOSE2(printf("p%d : T[%d] <- %d\n", p, e, r));
1917    }
1918    CLOCK_THREAD_END_STEP(p, 2);
1919
1920    // To avoid uninitialized accesses
1921    CLOCK_THREAD_START_STEP(p, 3);
1922    CLOCK_THREAD_END_STEP(p, 3);
1923}
1924#endif // FEATURES && !PARMERGE
1925
1926
1927#if FEATURES && PARMERGE
1928// -----------------------------------------------------
1929static void MCA_Label_Features_Rosenfeld_PAR2(MCA * mca)
1930// -----------------------------------------------------
1931{
1932    int p = mca->p;
1933    int nb_level = mca->nb_level;
1934
1935    if (mca->p == 0) {
1936        printf("*** %s ***\n", __func__);
1937    }
1938   
1939    // ------------------------------
1940    // -- parallel border merging --
1941    // ------------------------------
1942   
1943    // local variables
1944    int i = mca->i0;
1945    int width = mca->width;
1946    int alpha = mca->alpha;
1947    uint32 e0 = mca->e0;
1948    uint32 e1 = mca->ne;
1949
1950    // local memory zones
1951    uint8 **  X = mca->X;
1952    uint32 ** E = mca->E;
1953    uint32 *  T = mca->T;
1954    uint32 ** D = mca->D;
1955    RegionStats ** F = mca->F;
1956
1957    CLOCK_THREAD_START_STEP(p, 1);
1958    if (p != 0) { // thread 0 never has any merge to do
1959        borderMerging_Features_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);  // (i) et (i-1)
1960    }
1961    pthread_barrier_wait(&main_barrier);
1962    CLOCK_THREAD_END_STEP(p, 1);
1963
1964
1965    // ---------------------------------
1966    // -- parallel transitive closure --
1967    // ---------------------------------
1968    // identique a la version sans Features
1969     
1970    CLOCK_THREAD_START_STEP(p, 2);
1971    for (uint32 e = e0; e <= e1; e++) {
1972        uint32 r = T[e]; // acces local
1973        if (r < e) {
1974            r = FindRoot_Dist(D, e, alpha); // acces distant
1975            T[e] = r;
1976        }
1977        MCA_VERBOSE2(printf("p%d : T[%d] <- %d\n", p, e, r));
1978    }
1979    CLOCK_THREAD_END_STEP(p, 2);
1980
1981    // To avoid uninitialized accesses
1982    CLOCK_THREAD_START_STEP(p, 3);
1983    CLOCK_THREAD_END_STEP(p, 3);
1984}
1985#endif // FEATURES
1986
1987
1988
1989
1990#if !FEATURES
1991// =============================================================
1992#if TARGET_OS == GIETVM
1993__attribute__((constructor)) void MCA_Label_Rosenfeld(MCA * mca)
1994#else
1995void MCA_Label_Rosenfeld(MCA * mca)
1996#endif
1997// =============================================================
1998{
1999#if TARGET_OS == GIETVM
2000    unsigned int x, y, lpid;
2001    giet_proc_xyp(&x, &y, &lpid);
2002    // Mettre à jour mca->p en fonction de x, y, lpid
2003    // pour que les allocations faites par le main soient locales,
2004    // i.e.
2005    mca->p = (x * Y_SIZE + y) * NB_PROCS_MAX + lpid;
2006    // We have :
2007    // mca->p = 4 pour (x = 0, y = 1, lpid = 0)
2008    // mca->p = 5 pour (x = 0, y = 1, lpid = 1)
2009    MCA_VERBOSE2(printf("mca->p = %d pour (x = %d, y = %d, lpid = %d)\n", mca->p, x, y, lpid));
2010#endif
2011
2012    CLOCK_THREAD_START(mca->p);
2013    CLOCK_THREAD_COMPUTE_START(mca->p);
2014
2015    MCA_Scatter_ImageX(mca);
2016    pthread_barrier_wait(&main_barrier);
2017
2018    MCA_Label_Rosenfeld_PAR1(mca);
2019    pthread_barrier_wait(&main_barrier);
2020   
2021    MCA_Label_Rosenfeld_PYR2(mca);
2022    pthread_barrier_wait(&main_barrier);
2023   
2024    MCA_Label_Rosenfeld_PAR3(mca);
2025    pthread_barrier_wait(&main_barrier);
2026
2027    MCA_Gather_ImageL(mca);
2028    pthread_barrier_wait(&main_barrier);
2029
2030    CLOCK_THREAD_COMPUTE_END(mca->p);
2031    CLOCK_THREAD_END(mca->p);
2032
2033#if TARGET_OS == GIETVM
2034    if (mca->p != 0) {
2035        exit(0);
2036    }
2037#endif
2038}
2039#endif // !FEATURES
2040
2041
2042#if FEATURES
2043// ======================================================================
2044#if TARGET_OS == GIETVM
2045__attribute__((constructor)) void * MCA_Label_Features_Rosenfeld(void * arg)
2046#else
2047void * MCA_Label_Features_Rosenfeld(void * arg)
2048#endif
2049// ======================================================================
2050{
2051    MCA * mca = (MCA *) arg;
2052#if TARGET_OS == GIETVM
2053    unsigned int x, y, lpid;
2054    giet_proc_xyp(&x, &y, &lpid);
2055    // Mettre à jour mca->p en fonction de x, y, lpid
2056    // pour que les allocations faites par le main soient locales,
2057    // i.e.
2058    mca->p = (x * Y_SIZE + y) * NB_PROCS_MAX + lpid;
2059    // We have :
2060    // mca->p = 4 pour (x = 0, y = 1, lpid = 0)
2061    // mca->p = 5 pour (x = 0, y = 1, lpid = 1)
2062    MCA_VERBOSE2(printf("mca->p = %d pour (x = %d, y = %d, lpid = %d)\n", mca->p, x, y, lpid));
2063#endif
2064
2065    CLOCK_THREAD_START(mca->p);
2066    CLOCK_THREAD_COMPUTE_START(mca->p);
2067
2068    MCA_Scatter_ImageX(mca);
2069    pthread_barrier_wait(&main_barrier);
2070
2071    MCA_Label_Features_Rosenfeld_PAR1(mca);
2072    pthread_barrier_wait(&main_barrier);
2073   
2074#if PARMERGE
2075    MCA_Label_Features_Rosenfeld_PAR2(mca);
2076#else
2077    MCA_Label_Features_Rosenfeld_PYR2(mca);
2078#endif
2079    pthread_barrier_wait(&main_barrier);
2080   
2081    MCA_Label_Rosenfeld_PAR3(mca);
2082    pthread_barrier_wait(&main_barrier);
2083
2084    MCA_Gather_ImageL(mca);
2085    pthread_barrier_wait(&main_barrier);
2086
2087    CLOCK_THREAD_COMPUTE_END(mca->p);
2088 
2089    if (display_features) {
2090        if (mca->p == 0) {
2091            int i = 1;
2092            printf("[STATS]\n");
2093            for (int p = 0; p < mca->np; p++) {
2094                MCA * mca_par = mca->mca->mcas[p];
2095                uint32 e0 = mca_par->e0;
2096                uint32 ne = mca_par->ne - mca_par->e0; // number of elements
2097                uint32 * T = mca_par->T;
2098                RegionStats * stats = mca_par->stats;
2099                RegionStats_DisplayStats_Sparse(T, e0, e0 + ne, stats, NULL, &i);
2100            }
2101            printf("[/STATS]\n");
2102        }
2103    }
2104
2105    CLOCK_THREAD_END(mca->p);
2106
2107#if TARGET_OS == GIETVM
2108    if (mca->p != 0) {
2109        exit(0);
2110    }
2111#endif
2112
2113    return NULL;
2114}
2115#endif // FEATURES
2116
2117
2118// Local Variables:
2119// tab-width: 4
2120// c-basic-offset: 4
2121// c-file-offsets:((innamespace . 0)(inline-open . 0))
2122// indent-tabs-mode: nil
2123// End:
2124
2125// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
2126
Note: See TracBrowser for help on using the repository browser.