GCC Code Coverage Report

Directory: ./
File: tasks/marin_l_mark_components/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 146 173 84.4%
Functions: 20 22 90.9%
Branches: 101 188 53.7%
Line Branch Exec Source
1 #include "marin_l_mark_components/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <exception>
7 #include <functional>
8 #include <mutex>
9 #include <thread>
10 #include <vector>
11
12 #include "marin_l_mark_components/common/include/common.hpp"
13 #include "util/include/util.hpp"
14
15 namespace marin_l_mark_components {
16
17 namespace {
18
19 constexpr std::uint64_t kMaxPixels = 100000000ULL;
20 constexpr int kMinRowsPerStripe = 64;
21
22 int FindRoot(std::vector<int> &parent, int x) {
23 int root = x;
24
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 744 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 744 while (parent[static_cast<std::size_t>(root)] != root) {
25 root = parent[static_cast<std::size_t>(root)];
26 }
27
28 int current = x;
29
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 744 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 744 while (current != root) {
30 ✗ const int next = parent[static_cast<std::size_t>(current)];
31 ✗ parent[static_cast<std::size_t>(current)] = root;
32 current = next;
33 }
34
35 return root;
36 }
37
38 ✗ void UnionLabels(std::vector<int> &parent, int a, int b) {
39 const int root_a = FindRoot(parent, a);
40 const int root_b = FindRoot(parent, b);
41 ✗ if (root_a == root_b) {
42 return;
43 }
44
45 ✗ if (root_a < root_b) {
46 ✗ parent[static_cast<std::size_t>(root_b)] = root_a;
47 } else {
48 ✗ parent[static_cast<std::size_t>(root_a)] = root_b;
49 }
50 }
51
52 1160 int MergeLabels(std::vector<int> &parent, int left_label, int top_label, int &next_label) {
53
4/4
✓ Branch 0 taken 864 times.
✓ Branch 1 taken 296 times.
✓ Branch 2 taken 744 times.
✓ Branch 3 taken 120 times.
 1160 if (left_label == 0 && top_label == 0) {
54 744 parent[static_cast<std::size_t>(next_label)] = next_label;
55 744 return next_label++;
56 }
57
58
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 296 times.
 416 if (left_label == 0) {
59 120 return top_label;
60 }
61
62
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 104 times.
 296 if (top_label == 0) {
63 return left_label;
64 }
65
66 const int merged_label = std::min(left_label, top_label);
67
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 192 times.
 192 if (left_label != top_label) {
68 ✗ UnionLabels(parent, left_label, top_label);
69 }
70
71 return merged_label;
72 }
73
74
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 240 void RunParallelWorkers(int worker_count, const std::function<void(int, int)> &fn) {
75 240 const int total_workers = std::max(1, worker_count);
76 240 std::vector<std::thread> threads;
77
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 240 threads.reserve(static_cast<std::size_t>(std::max(0, total_workers - 1)));
78
79 std::exception_ptr thread_error;
80 240 std::mutex error_mutex;
81
82
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 240 times.
 384 for (int worker = 1; worker < total_workers; ++worker) {
83
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 threads.emplace_back([&, worker]() {
84 try {
85
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 144 times.
 288 fn(worker, total_workers);
86 ✗ } catch (...) {
87 ✗ std::scoped_lock lock(error_mutex);
88 ✗ if (thread_error == nullptr) {
89 ✗ thread_error = std::current_exception();
90 }
91 ✗ }
92 144 });
93 }
94
95 try {
96 240 fn(0, total_workers);
97 ✗ } catch (...) {
98 std::scoped_lock lock(error_mutex);
99 ✗ if (thread_error == nullptr) {
100 ✗ thread_error = std::current_exception();
101 }
102 ✗ }
103
104
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 240 times.
 384 for (auto &thread : threads) {
105
1/2
✓ Branch 0 taken 144 times.
✗ Branch 1 not taken.
 144 if (thread.joinable()) {
106
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 thread.join();
107 }
108 }
109
110
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 240 times.
 240 if (thread_error != nullptr) {
111 ✗ std::rethrow_exception(thread_error);
112 }
113 240 }
114
115 240 void ParallelForBlocks(int total_items, int worker_count, const std::function<void(int, int)> &fn) {
116
1/2
✓ Branch 0 taken 240 times.
✗ Branch 1 not taken.
 240 if (total_items <= 0) {
117 return;
118 }
119
120 const int actual_workers = std::min(std::max(1, worker_count), total_items);
121
3/8
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 5 taken 240 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 240 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 240 times.
✗ Branch 13 not taken.
 960 RunParallelWorkers(actual_workers, [fn, total_items](int worker, int total_workers) {
122 384 const int begin = (worker * total_items) / total_workers;
123 384 const int end = ((worker + 1) * total_items) / total_workers;
124
1/2
✓ Branch 0 taken 384 times.
✗ Branch 1 not taken.
 384 if (begin < end) {
125 384 fn(begin, end);
126 }
127 384 });
128 }
129
130
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 void InitializeParents(std::vector<int> &parent, int total_max_labels, int worker_count) {
131
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ParallelForBlocks(total_max_labels, worker_count, [&](int begin, int end) {
132
2/2
✓ Branch 0 taken 1976 times.
✓ Branch 1 taken 120 times.
 2096 for (int label = begin; label < end; ++label) {
133 1976 parent[static_cast<std::size_t>(label)] = label;
134 }
135 });
136 48 }
137
138 48 void ProcessStripe(const std::vector<std::uint8_t> &binary, std::vector<int> &labels_flat, std::vector<int> &parent,
139 const std::vector<int> &stripe_bounds, const std::vector<int> &stripe_base_label,
140 std::vector<int> &stripe_used_label_end, int width, int stripe) {
141 48 const int row_begin = stripe_bounds[static_cast<std::size_t>(stripe)];
142 48 const int row_end = stripe_bounds[static_cast<std::size_t>(stripe) + 1ULL];
143 48 int next_label = stripe_base_label[static_cast<std::size_t>(stripe)];
144
145
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 48 times.
 448 for (int row = row_begin; row < row_end; ++row) {
146 400 const std::size_t row_offset = static_cast<std::size_t>(row) * static_cast<std::size_t>(width);
147 400 const std::size_t top_row_offset = row_offset - static_cast<std::size_t>(width);
148
149
2/2
✓ Branch 0 taken 3776 times.
✓ Branch 1 taken 400 times.
 4176 for (int col = 0; col < width; ++col) {
150
2/2
✓ Branch 0 taken 2616 times.
✓ Branch 1 taken 1160 times.
 3776 const std::size_t idx = row_offset + static_cast<std::size_t>(col);
151
2/2
✓ Branch 0 taken 2616 times.
✓ Branch 1 taken 1160 times.
 3776 if (binary[idx] == 0U) {
152 2616 continue;
153 }
154
155
2/2
✓ Branch 0 taken 1056 times.
✓ Branch 1 taken 104 times.
 1160 const int left_label = (col > 0) ? labels_flat[idx - 1ULL] : 0;
156
2/2
✓ Branch 0 taken 1048 times.
✓ Branch 1 taken 112 times.
 1160 const int top_label = (row > row_begin) ? labels_flat[top_row_offset + static_cast<std::size_t>(col)] : 0;
157 1160 labels_flat[idx] = MergeLabels(parent, left_label, top_label, next_label);
158 }
159 }
160
161 48 stripe_used_label_end[static_cast<std::size_t>(stripe)] = next_label;
162 48 }
163
164 48 std::vector<int> BuildCompactedLabels(std::vector<int> &parent, const std::vector<int> &stripe_base_label,
165 const std::vector<int> &stripe_used_label_end) {
166 48 std::vector<int> compacted(parent.size(), 0);
167 int next_compact_id = 1;
168
169
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
 96 for (std::size_t stripe = 0; stripe < stripe_base_label.size(); ++stripe) {
170
2/2
✓ Branch 0 taken 744 times.
✓ Branch 1 taken 48 times.
 792 for (int label = stripe_base_label[stripe]; label < stripe_used_label_end[stripe]; ++label) {
171 const int root = FindRoot(parent, label);
172
1/2
✓ Branch 0 taken 744 times.
✗ Branch 1 not taken.
 744 if (compacted[static_cast<std::size_t>(root)] == 0) {
173 744 compacted[static_cast<std::size_t>(root)] = next_compact_id++;
174 }
175 744 compacted[static_cast<std::size_t>(label)] = compacted[static_cast<std::size_t>(root)];
176 }
177 }
178
179 48 return compacted;
180 }
181
182 } // namespace
183
184
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 MarinLMarkComponentsSTL::MarinLMarkComponentsSTL(const InType &in) {
185 SetTypeOfTask(GetStaticTypeOfTask());
186 GetInput() = in;
187 48 }
188
189 ✗ bool MarinLMarkComponentsSTL::IsBinary(const Image &img) {
190
2/4
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 448 for (const auto &row : img) {
191
2/4
✓ Branch 0 taken 3776 times.
✓ Branch 1 taken 400 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 4176 for (int pixel : row) {
192
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 3776 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 3776 if (pixel != 0 && pixel != 1) {
193 return false;
194 }
195 }
196 }
197 return true;
198 }
199
200
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 bool MarinLMarkComponentsSTL::ValidationImpl() {
201 const auto &img = GetInput().binary;
202
2/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 48 times.
 48 if (img.empty() || img.front().empty()) {
203 return false;
204 }
205
206 const std::size_t width = img.front().size();
207
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 48 times.
 448 for (const auto &row : img) {
208
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 400 times.
 400 if (row.size() != width) {
209 return false;
210 }
211 }
212
213 return IsBinary(img);
214 }
215
216 48 bool MarinLMarkComponentsSTL::PreProcessingImpl() {
217
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 const auto &input_binary = GetInput().binary;
218 48 height_ = static_cast<int>(input_binary.size());
219 48 width_ = static_cast<int>(input_binary.front().size());
220
221
2/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 if (height_ <= 0 || width_ <= 0) {
222 return false;
223 }
224
225 48 const std::uint64_t pixels = static_cast<std::uint64_t>(height_) * static_cast<std::uint64_t>(width_);
226
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (pixels > kMaxPixels) {
227 return false;
228 }
229
230 48 const int requested_threads = std::max(1, ppc::util::GetNumThreads());
231
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 stripe_count_ = std::min(height_, requested_threads * 2);
232
2/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 if (stripe_count_ > 0 && height_ / stripe_count_ < kMinRowsPerStripe) {
233
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 96 stripe_count_ = std::max(1, height_ / kMinRowsPerStripe);
234 }
235 48 stripe_count_ = std::max(1, stripe_count_);
236
237 48 stripe_bounds_.assign(static_cast<std::size_t>(stripe_count_) + 1ULL, 0);
238
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 48 times.
 144 for (int stripe = 0; stripe <= stripe_count_; ++stripe) {
239 96 stripe_bounds_[static_cast<std::size_t>(stripe)] = (stripe * height_) / stripe_count_;
240 }
241
242 48 stripe_base_label_.assign(static_cast<std::size_t>(stripe_count_), 0);
243 48 stripe_used_label_end_.assign(static_cast<std::size_t>(stripe_count_), 0);
244 48 total_max_labels_ = 1;
245
246
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
 96 for (int stripe = 0; stripe < stripe_count_; ++stripe) {
247 48 stripe_base_label_[static_cast<std::size_t>(stripe)] = total_max_labels_;
248 const int stripe_height =
249 48 stripe_bounds_[static_cast<std::size_t>(stripe) + 1ULL] - stripe_bounds_[static_cast<std::size_t>(stripe)];
250 48 total_max_labels_ += ((stripe_height * width_) / 2) + 1;
251 }
252
253 48 binary_.assign(static_cast<std::size_t>(pixels), 0);
254
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
 48 labels_flat_.assign(static_cast<std::size_t>(pixels), 0);
255 labels_.clear();
256 48 parent_.assign(static_cast<std::size_t>(total_max_labels_), 0);
257 48 root_to_compact_.assign(static_cast<std::size_t>(total_max_labels_), 0);
258
259 48 InitializeParents(parent_, total_max_labels_, requested_threads);
260
261
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ParallelForBlocks(height_, requested_threads, [&](int row_begin, int row_end) {
262
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 120 times.
 520 for (int row = row_begin; row < row_end; ++row) {
263 400 const std::size_t row_offset = static_cast<std::size_t>(row) * static_cast<std::size_t>(width_);
264
2/2
✓ Branch 0 taken 3776 times.
✓ Branch 1 taken 400 times.
 4176 for (int col = 0; col < width_; ++col) {
265 3776 binary_[row_offset + static_cast<std::size_t>(col)] =
266 3776 static_cast<std::uint8_t>(input_binary[static_cast<std::size_t>(row)][static_cast<std::size_t>(col)]);
267 }
268 }
269 120 });
270
271 48 return true;
272 }
273
274 48 bool MarinLMarkComponentsSTL::RunImpl() {
275
2/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 if (height_ == 0 || width_ == 0) {
276 return true;
277 }
278
279 48 FirstPassSTL();
280 48 MergeStripeBorders();
281 48 SecondPassSTL();
282 48 return true;
283 }
284
285
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 void MarinLMarkComponentsSTL::FirstPassSTL() {
286 std::ranges::fill(labels_flat_, 0);
287
288
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ParallelForBlocks(stripe_count_, stripe_count_, [&](int stripe_begin, int stripe_end) {
289
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
 96 for (int stripe = stripe_begin; stripe < stripe_end; ++stripe) {
290 48 ProcessStripe(binary_, labels_flat_, parent_, stripe_bounds_, stripe_base_label_, stripe_used_label_end_, width_,
291 stripe);
292 }
293 48 });
294 48 }
295
296 48 void MarinLMarkComponentsSTL::MergeStripeBorders() {
297
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 for (int stripe = 0; stripe < stripe_count_ - 1; ++stripe) {
298 ✗ const int boundary_row = stripe_bounds_[static_cast<std::size_t>(stripe) + 1ULL];
299 ✗ const std::size_t top_row_offset = static_cast<std::size_t>(boundary_row - 1) * static_cast<std::size_t>(width_);
300 ✗ const std::size_t bottom_row_offset = static_cast<std::size_t>(boundary_row) * static_cast<std::size_t>(width_);
301
302 ✗ for (int col = 0; col < width_; ++col) {
303 ✗ const std::size_t top_idx = top_row_offset + static_cast<std::size_t>(col);
304 ✗ const std::size_t bottom_idx = bottom_row_offset + static_cast<std::size_t>(col);
305
306 ✗ if (binary_[top_idx] == 1U && binary_[bottom_idx] == 1U) {
307 ✗ UnionLabels(parent_, labels_flat_[top_idx], labels_flat_[bottom_idx]);
308 }
309 }
310 }
311 48 }
312
313 48 void MarinLMarkComponentsSTL::SecondPassSTL() {
314
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (total_max_labels_ <= 1) {
315 return;
316 }
317
318
1/2
✓ Branch 3 taken 48 times.
✗ Branch 4 not taken.
 96 root_to_compact_ = BuildCompactedLabels(parent_, stripe_base_label_, stripe_used_label_end_);
319
320
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 96 ParallelForBlocks(static_cast<int>(labels_flat_.size()), stripe_count_, [&](int pixel_begin, int pixel_end) {
321
2/2
✓ Branch 0 taken 3776 times.
✓ Branch 1 taken 48 times.
 3824 for (int idx = pixel_begin; idx < pixel_end; ++idx) {
322
2/2
✓ Branch 0 taken 2616 times.
✓ Branch 1 taken 1160 times.
 3776 const int label = labels_flat_[static_cast<std::size_t>(idx)];
323
2/2
✓ Branch 0 taken 2616 times.
✓ Branch 1 taken 1160 times.
 3776 if (label == 0) {
324 2616 continue;
325 }
326
327 1160 labels_flat_[static_cast<std::size_t>(idx)] = root_to_compact_[static_cast<std::size_t>(label)];
328 }
329 });
330 }
331
332 48 bool MarinLMarkComponentsSTL::PostProcessingImpl() {
333 48 ConvertLabelsToOutput();
334 48 OutType out;
335
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 out.labels = labels_;
336 GetOutput() = out;
337 48 return true;
338 }
339
340
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 void MarinLMarkComponentsSTL::ConvertLabelsToOutput() {
341 labels_.clear();
342 48 labels_.resize(static_cast<std::size_t>(height_));
343
344
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ParallelForBlocks(height_, stripe_count_, [&](int row_begin, int row_end) {
345
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 48 times.
 448 for (int row = row_begin; row < row_end; ++row) {
346 400 labels_[static_cast<std::size_t>(row)].resize(static_cast<std::size_t>(width_));
347 400 const std::size_t row_offset = static_cast<std::size_t>(row) * static_cast<std::size_t>(width_);
348
2/2
✓ Branch 0 taken 3776 times.
✓ Branch 1 taken 400 times.
 4176 for (int col = 0; col < width_; ++col) {
349 3776 labels_[static_cast<std::size_t>(row)][static_cast<std::size_t>(col)] =
350 3776 labels_flat_[row_offset + static_cast<std::size_t>(col)];
351 }
352 }
353 48 });
354 48 }
355
356 } // namespace marin_l_mark_components
357