GCC Code Coverage Report

Directory: ./
File: tasks/kondrashova_v_marking_components/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 28 168 16.7%
Functions: 5 14 35.7%
Branches: 10 204 4.9%
Line Branch Exec Source
1 #include "kondrashova_v_marking_components/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <cstdint>
8 #include <vector>
9
10 #include "kondrashova_v_marking_components/common/include/common.hpp"
11 #include "util/include/util.hpp"
12
13 namespace kondrashova_v_marking_components {
14
15
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 KondrashovaVTaskALL::KondrashovaVTaskALL(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17 GetInput() = in;
18 52 GetOutput() = {};
19 26 }
20
21 26 bool KondrashovaVTaskALL::ValidationImpl() {
22 26 return true;
23 }
24
25 26 bool KondrashovaVTaskALL::PreProcessingImpl() {
26 26 MPI_Comm_rank(MPI_COMM_WORLD, &rank_);
27 26 MPI_Comm_size(MPI_COMM_WORLD, &world_size_);
28
29
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 if (rank_ == 0) {
30 const auto &in = GetInput();
31 13 width_ = in.width;
32 13 height_ = in.height;
33 13 image_ = in.data;
34 }
35
36 26 MPI_Bcast(&width_, 1, MPI_INT, 0, MPI_COMM_WORLD);
37 26 MPI_Bcast(&height_, 1, MPI_INT, 0, MPI_COMM_WORLD);
38
39 26 int has_valid_input = 0;
40
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 if (rank_ == 0) {
41
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 26 has_valid_input = (width_ > 0 && height_ > 0 && static_cast<int>(image_.size()) == (width_ * height_)) ? 1 : 0;
42 }
43 26 MPI_Bcast(&has_valid_input, 1, MPI_INT, 0, MPI_COMM_WORLD);
44
45
1/2
✓ Branch 0 taken 26 times.
✗ Branch 1 not taken.
 26 if (has_valid_input == 0) {
46 image_.clear();
47 labels_1d_.clear();
48
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 26 times.
 26 GetOutput().count = 0;
49 GetOutput().labels.clear();
50 26 return true;
51 }
52
53 ✗ if (rank_ != 0) {
54 ✗ image_.resize(static_cast<size_t>(width_) * static_cast<size_t>(height_));
55 }
56
57 ✗ MPI_Bcast(image_.data(), width_ * height_, MPI_UNSIGNED_CHAR, 0, MPI_COMM_WORLD);
58
59 ✗ labels_1d_.assign(static_cast<size_t>(width_) * static_cast<size_t>(height_), 0);
60
61 ✗ GetOutput().count = 0;
62 GetOutput().labels.clear();
63 return true;
64 }
65
66 namespace {
67
68 int Find(std::vector<int> &parent, int xx) {
69 ✗ while (parent[static_cast<size_t>(xx)] != xx) {
70 ✗ parent[static_cast<size_t>(xx)] = parent[static_cast<size_t>(parent[static_cast<size_t>(xx)])];
71 xx = parent[static_cast<size_t>(xx)];
72 }
73 return xx;
74 }
75
76 ✗ void Unite(std::vector<int> &parent, std::vector<int> &rnk, int aa, int bb) {
77 aa = Find(parent, aa);
78 bb = Find(parent, bb);
79 ✗ if (aa == bb) {
80 return;
81 }
82 ✗ if (rnk[static_cast<size_t>(aa)] < rnk[static_cast<size_t>(bb)]) {
83 std::swap(aa, bb);
84 }
85 ✗ parent[static_cast<size_t>(bb)] = aa;
86 ✗ if (rnk[static_cast<size_t>(aa)] == rnk[static_cast<size_t>(bb)]) {
87 ✗ rnk[static_cast<size_t>(aa)]++;
88 }
89 }
90
91 int GetNeighborLabel(int ii, int jj, int di, int dj, int row_start, int row_end, int width,
92 const std::vector<uint8_t> &image, const std::vector<int> &local_labels) {
93 ✗ int ni = ii + di;
94 ✗ int nj = jj + dj;
95 ✗ if (ni < row_start || ni >= row_end || nj < 0 || nj >= width) {
96 return 0;
97 }
98 ✗ auto nidx = (static_cast<size_t>(ni) * static_cast<size_t>(width)) + static_cast<size_t>(nj);
99 ✗ if (image[nidx] == 0) {
100 ✗ return local_labels[nidx];
101 }
102 return 0;
103 }
104
105 ✗ void ScanStripe(int row_start, int row_end, int width, int label_offset, const std::vector<uint8_t> &image,
106 std::vector<int> &local_labels) {
107 int current_label = label_offset;
108 ✗ for (int ii = row_start; ii < row_end; ++ii) {
109 ✗ for (int jj = 0; jj < width; ++jj) {
110 ✗ auto idx = (static_cast<size_t>(ii) * static_cast<size_t>(width)) + static_cast<size_t>(jj);
111 ✗ if (image[idx] != 0) {
112 ✗ continue;
113 }
114
115 ✗ int left_label = GetNeighborLabel(ii, jj, 0, -1, row_start, row_end, width, image, local_labels);
116 ✗ int top_label = GetNeighborLabel(ii, jj, -1, 0, row_start, row_end, width, image, local_labels);
117
118 ✗ if (left_label == 0 && top_label == 0) {
119 ✗ local_labels[idx] = ++current_label;
120 ✗ } else if (left_label != 0 && top_label == 0) {
121 ✗ local_labels[idx] = left_label;
122 ✗ } else if (left_label == 0) {
123 ✗ local_labels[idx] = top_label;
124 } else {
125 ✗ local_labels[idx] = std::min(left_label, top_label);
126 }
127 }
128 }
129 ✗ }
130
131 ✗ void MergeHorizontal(int height, int width, const std::vector<int> &local_labels, std::vector<int> &parent,
132 std::vector<int> &rnk) {
133 ✗ for (int ii = 0; ii < height; ++ii) {
134 ✗ for (int jj = 1; jj < width; ++jj) {
135 ✗ auto idx = (static_cast<size_t>(ii) * static_cast<size_t>(width)) + static_cast<size_t>(jj);
136 ✗ auto lidx = (static_cast<size_t>(ii) * static_cast<size_t>(width)) + static_cast<size_t>(jj - 1);
137 ✗ if (local_labels[idx] != 0 && local_labels[lidx] != 0 && local_labels[idx] != local_labels[lidx]) {
138 ✗ Unite(parent, rnk, local_labels[idx], local_labels[lidx]);
139 }
140 }
141 }
142 ✗ }
143
144 ✗ void MergeVertical(int height, int width, const std::vector<int> &local_labels, std::vector<int> &parent,
145 std::vector<int> &rnk) {
146 ✗ for (int ii = 1; ii < height; ++ii) {
147 ✗ for (int jj = 0; jj < width; ++jj) {
148 ✗ auto idx = (static_cast<size_t>(ii) * static_cast<size_t>(width)) + static_cast<size_t>(jj);
149 ✗ auto tidx = (static_cast<size_t>(ii - 1) * static_cast<size_t>(width)) + static_cast<size_t>(jj);
150 ✗ if (local_labels[idx] != 0 && local_labels[tidx] != 0 && local_labels[idx] != local_labels[tidx]) {
151 ✗ Unite(parent, rnk, local_labels[idx], local_labels[tidx]);
152 }
153 }
154 }
155 ✗ }
156
157 ✗ void MergeBoundaries(int row_start, int row_end, int width, int num_threads, const std::vector<int> &local_labels,
158 std::vector<int> &parent, std::vector<int> &rnk) {
159 ✗ const int rows = row_end - row_start;
160 ✗ for (int tid = 1; tid < num_threads; ++tid) {
161 ✗ const int boundary_row = row_start + ((tid * rows) / num_threads);
162 ✗ if (boundary_row <= row_start || boundary_row >= row_end) {
163 ✗ continue;
164 }
165 ✗ for (int jj = 0; jj < width; ++jj) {
166 ✗ auto idx = (static_cast<size_t>(boundary_row) * static_cast<size_t>(width)) + static_cast<size_t>(jj);
167 ✗ auto tidx = (static_cast<size_t>(boundary_row - 1) * static_cast<size_t>(width)) + static_cast<size_t>(jj);
168 ✗ if (local_labels[idx] != 0 && local_labels[tidx] != 0 && local_labels[idx] != local_labels[tidx]) {
169 ✗ Unite(parent, rnk, local_labels[idx], local_labels[tidx]);
170 }
171 }
172 }
173 ✗ }
174
175 ✗ int Relabel(int total, const std::vector<int> &local_labels, std::vector<int> &parent, std::vector<int> &relabel_map,
176 std::vector<int> &labels_1d) {
177 int count = 0;
178 ✗ for (int ii = 0; ii < total; ++ii) {
179 ✗ auto idx = static_cast<size_t>(ii);
180 ✗ if (local_labels[idx] == 0) {
181 ✗ continue;
182 }
183 int root = Find(parent, local_labels[idx]);
184 ✗ if (relabel_map[static_cast<size_t>(root)] == 0) {
185 ✗ relabel_map[static_cast<size_t>(root)] = ++count;
186 }
187 ✗ labels_1d[idx] = relabel_map[static_cast<size_t>(root)];
188 }
189 ✗ return count;
190 }
191
192 void FillRowLabels(int width, int row, const std::vector<int> &local_labels, std::vector<int> &row_labels) {
193 ✗ for (int jj = 0; jj < width; ++jj) {
194 ✗ row_labels[static_cast<size_t>(jj)] =
195 ✗ local_labels[(static_cast<size_t>(row) * static_cast<size_t>(width)) + static_cast<size_t>(jj)];
196 }
197 }
198
199 ✗ void MergeBoundaryLabels(int width, const std::vector<int> &send_row, const std::vector<int> &recv_row,
200 std::vector<int> &parent, std::vector<int> &rnk) {
201 ✗ for (int jj = 0; jj < width; ++jj) {
202 ✗ const int label_cur = send_row[static_cast<size_t>(jj)];
203 ✗ const int label_neighbor = recv_row[static_cast<size_t>(jj)];
204 ✗ if (label_cur != 0 && label_neighbor != 0 && label_cur != label_neighbor) {
205 ✗ Unite(parent, rnk, label_cur, label_neighbor);
206 }
207 }
208 ✗ }
209
210 ✗ void ExchangeAndMergeRow(int width, int neighbor_rank, int send_tag, int recv_tag, bool has_rows, int row_index,
211 const std::vector<int> &local_labels, std::vector<int> &parent, std::vector<int> &rnk) {
212 ✗ std::vector<int> send_row(static_cast<size_t>(width), 0);
213 ✗ std::vector<int> recv_row(static_cast<size_t>(width));
214
215 ✗ if (has_rows) {
216 FillRowLabels(width, row_index, local_labels, send_row);
217 }
218
219 ✗ MPI_Sendrecv(send_row.data(), width, MPI_INT, neighbor_rank, send_tag, recv_row.data(), width, MPI_INT, neighbor_rank,
220 recv_tag, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
221
222 ✗ MergeBoundaryLabels(width, send_row, recv_row, parent, rnk);
223 ✗ }
224
225 ✗ void MergeMPIBoundaries(int width, int rank, int world_size, int local_row_start, int local_row_end,
226 const std::vector<int> &local_labels, std::vector<int> &parent, std::vector<int> &rnk) {
227 ✗ const bool has_rows = local_row_start < local_row_end;
228 const int first_row = local_row_start;
229 ✗ const int last_row = has_rows ? (local_row_end - 1) : local_row_start;
230
231 ✗ if (rank > 0) {
232 ✗ ExchangeAndMergeRow(width, rank - 1, 0, 1, has_rows, first_row, local_labels, parent, rnk);
233 }
234
235 ✗ if (rank < world_size - 1) {
236 ✗ ExchangeAndMergeRow(width, rank + 1, 1, 0, has_rows, last_row, local_labels, parent, rnk);
237 }
238 ✗ }
239
240 } // namespace
241
242 26 bool KondrashovaVTaskALL::RunImpl() {
243
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 26 if (width_ <= 0 || height_ <= 0 || image_.empty()) {
244 26 GetOutput().count = 0;
245 26 return true;
246 }
247
248 ✗ const int total = width_ * height_;
249 ✗ const int num_threads = ppc::util::GetNumThreads();
250
251 ✗ const int mpi_row_start = (rank_ * height_) / world_size_;
252 ✗ const int mpi_row_end = ((rank_ + 1) * height_) / world_size_;
253 ✗ const int mpi_rows = mpi_row_end - mpi_row_start;
254
255 ✗ const int max_rows_per_rank = (height_ + world_size_ - 1) / world_size_;
256 ✗ const int max_labels_per_thread = (max_rows_per_rank * width_) + 1;
257
258 ✗ std::vector<int> local_labels(static_cast<size_t>(total), 0);
259
260 ✗ const int width = width_;
261 ✗ const std::vector<uint8_t> image = image_;
262
263 ✗ #pragma omp parallel num_threads(num_threads) default(none) shared(local_labels, width, image, num_threads) \
264 firstprivate(mpi_row_start, mpi_rows, max_labels_per_thread)
265 {
266 const int tid = omp_get_thread_num();
267 const int omp_row_start = mpi_row_start + ((tid * mpi_rows) / num_threads);
268 const int omp_row_end = mpi_row_start + (((tid + 1) * mpi_rows) / num_threads);
269 const int label_offset = (rank_ * num_threads * max_labels_per_thread) + (tid * max_labels_per_thread);
270 ScanStripe(omp_row_start, omp_row_end, width, label_offset, image, local_labels);
271 }
272
273 ✗ const int global_max_labels = (world_size_ * num_threads * max_labels_per_thread) + 1;
274 ✗ std::vector<int> parent(static_cast<size_t>(global_max_labels));
275 ✗ std::vector<int> rnk(static_cast<size_t>(global_max_labels), 0);
276 ✗ for (int ii = 0; ii < global_max_labels; ++ii) {
277 ✗ parent[static_cast<size_t>(ii)] = ii;
278 }
279
280 ✗ MergeHorizontal(height_, width_, local_labels, parent, rnk);
281 ✗ MergeVertical(height_, width_, local_labels, parent, rnk);
282 ✗ MergeBoundaries(mpi_row_start, mpi_row_end, width_, num_threads, local_labels, parent, rnk);
283
284 ✗ MergeMPIBoundaries(width_, rank_, world_size_, mpi_row_start, mpi_row_end, local_labels, parent, rnk);
285
286 ✗ MPI_Barrier(MPI_COMM_WORLD);
287
288 ✗ std::vector<int> all_local_labels(static_cast<size_t>(total), 0);
289 ✗ MPI_Allreduce(local_labels.data(), all_local_labels.data(), total, MPI_INT, MPI_MAX, MPI_COMM_WORLD);
290
291 ✗ if (rank_ == 0) {
292 ✗ std::vector<int> global_parent(static_cast<size_t>(global_max_labels));
293 ✗ std::vector<int> global_rnk(static_cast<size_t>(global_max_labels), 0);
294 ✗ for (int ii = 0; ii < global_max_labels; ++ii) {
295 ✗ global_parent[static_cast<size_t>(ii)] = ii;
296 }
297
298 ✗ MergeHorizontal(height_, width_, all_local_labels, global_parent, global_rnk);
299 ✗ MergeVertical(height_, width_, all_local_labels, global_parent, global_rnk);
300
301 ✗ std::vector<int> relabel_map(static_cast<size_t>(global_max_labels), 0);
302 ✗ GetOutput().count = Relabel(total, all_local_labels, global_parent, relabel_map, labels_1d_);
303 }
304
305 ✗ int global_count = GetOutput().count;
306 ✗ MPI_Bcast(&global_count, 1, MPI_INT, 0, MPI_COMM_WORLD);
307 ✗ GetOutput().count = global_count;
308 if (total > 0) {
309 ✗ if (labels_1d_.size() != static_cast<size_t>(total)) {
310 ✗ labels_1d_.assign(static_cast<size_t>(total), 0);
311 }
312 ✗ MPI_Bcast(labels_1d_.data(), total, MPI_INT, 0, MPI_COMM_WORLD);
313 }
314
315 return true;
316 }
317
318 26 bool KondrashovaVTaskALL::PostProcessingImpl() {
319
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 26 if (width_ <= 0 || height_ <= 0) {
320 GetOutput().labels.clear();
321 26 return true;
322 }
323
324 ✗ GetOutput().labels.assign(height_, std::vector<int>(width_, 0));
325 ✗ for (int ii = 0; ii < height_; ++ii) {
326 ✗ for (int jj = 0; jj < width_; ++jj) {
327 ✗ auto idx = (static_cast<size_t>(ii) * static_cast<size_t>(width_)) + static_cast<size_t>(jj);
328 ✗ GetOutput().labels[ii][jj] = labels_1d_[idx];
329 }
330 }
331 return true;
332 }
333
334 } // namespace kondrashova_v_marking_components
335