GCC Code Coverage Report

Directory: ./
File: tasks/marin_l_mark_components/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 123 141 87.2%
Functions: 14 16 87.5%
Branches: 92 156 59.0%
Line Branch Exec Source
1 #include "marin_l_mark_components/tbb/include/ops_tbb.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <utility>
7 #include <vector>
8
9 #include "marin_l_mark_components/common/include/common.hpp"
10 #include "oneapi/tbb/blocked_range.h"
11 #include "oneapi/tbb/parallel_for.h"
12 #include "oneapi/tbb/task_arena.h"
13
14 namespace marin_l_mark_components {
15
16 namespace {
17
18 constexpr std::uint64_t kMaxPixels = 100000000ULL;
19 constexpr int kMinRowsPerStripe = 64;
20
21 struct StripeSetup {
22 int num_stripes = 1;
23 int total_max_labels = 1;
24 std::vector<int> stripe_bounds;
25 std::vector<int> stripe_base_label;
26 };
27
28 int FindRoot(std::vector<int> &parent, int x) {
29 int root = x;
30
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 372 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 372 while (parent[root] != root) {
31 root = parent[root];
32 }
33
34 int current = x;
35
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 372 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 372 while (current != root) {
36 ✗ const int next = parent[current];
37 ✗ parent[current] = root;
38 current = next;
39 }
40
41 return root;
42 }
43
44 ✗ void UnionLabels(std::vector<int> &parent, int a, int b) {
45 const int root_a = FindRoot(parent, a);
46 const int root_b = FindRoot(parent, b);
47 ✗ if (root_a == root_b) {
48 return;
49 }
50
51 ✗ if (root_a < root_b) {
52 ✗ parent[root_b] = root_a;
53 } else {
54 ✗ parent[root_a] = root_b;
55 }
56 }
57
58 24 StripeSetup BuildStripeSetup(int height, int width) {
59
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 StripeSetup setup;
60
61
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 setup.num_stripes = std::min(height, oneapi::tbb::this_task_arena::max_concurrency() * 2);
62
2/4
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 if (setup.num_stripes > 0 && height / setup.num_stripes < kMinRowsPerStripe) {
63
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 48 setup.num_stripes = std::max(1, height / kMinRowsPerStripe);
64 }
65 24 setup.num_stripes = std::max(1, setup.num_stripes);
66
67
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 setup.stripe_bounds.assign(static_cast<std::size_t>(setup.num_stripes) + 1ULL, 0);
68
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 24 times.
 72 for (int stripe = 0; stripe <= setup.num_stripes; ++stripe) {
69 48 setup.stripe_bounds[static_cast<std::size_t>(stripe)] = (stripe * height) / setup.num_stripes;
70 }
71
72
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 setup.stripe_base_label.assign(static_cast<std::size_t>(setup.num_stripes), 0);
73
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 for (int stripe = 0; stripe < setup.num_stripes; ++stripe) {
74 24 setup.stripe_base_label[static_cast<std::size_t>(stripe)] = setup.total_max_labels;
75 24 const int stripe_height = setup.stripe_bounds[static_cast<std::size_t>(stripe) + 1ULL] -
76 24 setup.stripe_bounds[static_cast<std::size_t>(stripe)];
77 24 setup.total_max_labels += ((stripe_height * width) / 2) + 1;
78 }
79
80 24 return setup;
81 ✗ }
82
83 void InitializeParents(std::vector<int> &parent, int total_max_labels) {
84 48 tbb::parallel_for(tbb::blocked_range<int>(0, total_max_labels), [&](const tbb::blocked_range<int> &range) {
85
4/4
✓ Branch 0 taken 488 times.
✓ Branch 1 taken 488 times.
✓ Branch 2 taken 500 times.
✓ Branch 3 taken 500 times.
 1976 for (int label = range.begin(); label != range.end(); ++label) {
86 988 parent[static_cast<std::size_t>(label)] = label;
87 }
88 });
89 }
90
91 580 void AssignPixelLabel(std::vector<int> &labels_flat, std::vector<int> &parent, std::size_t idx, int left_label,
92 int top_label, int &next_label) {
93
4/4
✓ Branch 0 taken 432 times.
✓ Branch 1 taken 148 times.
✓ Branch 2 taken 372 times.
✓ Branch 3 taken 60 times.
 580 if (left_label == 0 && top_label == 0) {
94 372 labels_flat[idx] = next_label++;
95 372 return;
96 }
97
4/4
✓ Branch 0 taken 148 times.
✓ Branch 1 taken 60 times.
✓ Branch 2 taken 52 times.
✓ Branch 3 taken 96 times.
 208 if (left_label != 0 && top_label == 0) {
98 52 labels_flat[idx] = left_label;
99 52 return;
100 }
101
3/4
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 96 times.
✓ Branch 2 taken 60 times.
✗ Branch 3 not taken.
 156 if (left_label == 0 && top_label != 0) {
102 60 labels_flat[idx] = top_label;
103 60 return;
104 }
105
106 const int min_label = std::min(left_label, top_label);
107 96 labels_flat[idx] = min_label;
108
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 if (left_label != top_label) {
109 ✗ UnionLabels(parent, left_label, top_label);
110 }
111 }
112
113 24 void LabelStripe(const std::vector<std::uint8_t> &binary_flat, std::vector<int> &labels_flat, std::vector<int> &parent,
114 const std::vector<int> &stripe_bounds, const std::vector<int> &stripe_base_label,
115 std::vector<int> &stripe_max_used, int width, int stripe) {
116 24 const int start_row = stripe_bounds[static_cast<std::size_t>(stripe)];
117 24 const int end_row = stripe_bounds[static_cast<std::size_t>(stripe) + 1ULL];
118 24 int next_label = stripe_base_label[static_cast<std::size_t>(stripe)];
119
120
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 24 times.
 224 for (int row = start_row; row < end_row; ++row) {
121 200 const auto row_offset = static_cast<std::size_t>(row) * static_cast<std::size_t>(width);
122 200 const auto prev_row_offset = static_cast<std::size_t>(row - 1) * static_cast<std::size_t>(width);
123
124
2/2
✓ Branch 0 taken 1888 times.
✓ Branch 1 taken 200 times.
 2088 for (int col = 0; col < width; ++col) {
125
2/2
✓ Branch 0 taken 1308 times.
✓ Branch 1 taken 580 times.
 1888 const auto idx = row_offset + static_cast<std::size_t>(col);
126
2/2
✓ Branch 0 taken 1308 times.
✓ Branch 1 taken 580 times.
 1888 if (binary_flat[idx] == 0U) {
127 1308 continue;
128 }
129
130
2/2
✓ Branch 0 taken 528 times.
✓ Branch 1 taken 52 times.
 580 const int left_label = (col > 0) ? labels_flat[idx - 1ULL] : 0;
131
2/2
✓ Branch 0 taken 524 times.
✓ Branch 1 taken 56 times.
 580 const int top_label = (row > start_row) ? labels_flat[prev_row_offset + static_cast<std::size_t>(col)] : 0;
132 580 AssignPixelLabel(labels_flat, parent, idx, left_label, top_label, next_label);
133 }
134 }
135
136 24 stripe_max_used[static_cast<std::size_t>(stripe)] = next_label;
137 24 }
138
139 24 void MergeStripeBorders(const std::vector<std::uint8_t> &binary_flat, const std::vector<int> &stripe_bounds,
140 std::vector<int> &labels_flat, std::vector<int> &parent, int width, int num_stripes) {
141
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 for (int stripe = 0; stripe < num_stripes - 1; ++stripe) {
142 ✗ const int boundary_row = stripe_bounds[static_cast<std::size_t>(stripe) + 1ULL];
143 ✗ const auto row_offset = static_cast<std::size_t>(boundary_row) * static_cast<std::size_t>(width);
144 ✗ const auto prev_row_offset = static_cast<std::size_t>(boundary_row - 1) * static_cast<std::size_t>(width);
145
146 ✗ for (int col = 0; col < width; ++col) {
147 ✗ const auto bottom_idx = row_offset + static_cast<std::size_t>(col);
148 ✗ const auto top_idx = prev_row_offset + static_cast<std::size_t>(col);
149 ✗ if (binary_flat[bottom_idx] == 1U && binary_flat[top_idx] == 1U) {
150 ✗ UnionLabels(parent, labels_flat[bottom_idx], labels_flat[top_idx]);
151 }
152 }
153 }
154 24 }
155
156 24 std::vector<int> BuildCompactedLabels(std::vector<int> &parent, const std::vector<int> &stripe_base_label,
157 const std::vector<int> &stripe_max_used, int total_max_labels, int num_stripes) {
158 24 std::vector<int> compacted(static_cast<std::size_t>(total_max_labels), 0);
159 int next_compact_id = 1;
160
161
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 for (int stripe = 0; stripe < num_stripes; ++stripe) {
162 396 for (int label = stripe_base_label[static_cast<std::size_t>(stripe)];
163
2/2
✓ Branch 0 taken 372 times.
✓ Branch 1 taken 24 times.
 396 label < stripe_max_used[static_cast<std::size_t>(stripe)]; ++label) {
164 const int root = FindRoot(parent, label);
165
1/2
✓ Branch 0 taken 372 times.
✗ Branch 1 not taken.
 372 if (compacted[static_cast<std::size_t>(root)] == 0) {
166 372 compacted[static_cast<std::size_t>(root)] = next_compact_id++;
167 }
168 372 compacted[static_cast<std::size_t>(label)] = compacted[static_cast<std::size_t>(root)];
169 }
170 }
171
172 24 return compacted;
173 }
174
175 void ApplyCompactedLabels(std::vector<int> &labels_flat, const std::vector<int> &compacted,
176 const std::vector<int> &stripe_bounds, int width, int num_stripes) {
177 24 tbb::parallel_for(tbb::blocked_range<int>(0, num_stripes), [&](const tbb::blocked_range<int> &range) {
178
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 for (int stripe = range.begin(); stripe != range.end(); ++stripe) {
179 24 const int start_row = stripe_bounds[static_cast<std::size_t>(stripe)];
180 24 const int end_row = stripe_bounds[static_cast<std::size_t>(stripe) + 1ULL];
181
182
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 24 times.
 224 for (int row = start_row; row < end_row; ++row) {
183 200 const auto row_offset = static_cast<std::size_t>(row) * static_cast<std::size_t>(width);
184
2/2
✓ Branch 0 taken 1888 times.
✓ Branch 1 taken 200 times.
 2088 for (int col = 0; col < width; ++col) {
185 1888 const auto idx = row_offset + static_cast<std::size_t>(col);
186
2/2
✓ Branch 0 taken 580 times.
✓ Branch 1 taken 1308 times.
 1888 const int label = labels_flat[idx];
187
2/2
✓ Branch 0 taken 580 times.
✓ Branch 1 taken 1308 times.
 1888 if (label != 0) {
188 580 labels_flat[idx] = compacted[static_cast<std::size_t>(label)];
189 }
190 }
191 }
192 }
193 24 });
194 }
195
196 } // namespace
197
198
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 MarinLMarkComponentsTBB::MarinLMarkComponentsTBB(const InType &in) {
199 SetTypeOfTask(GetStaticTypeOfTask());
200 GetInput() = in;
201 24 }
202
203 ✗ bool MarinLMarkComponentsTBB::IsBinary(const Image &img) {
204
2/4
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 224 for (const auto &row : img) {
205
2/4
✓ Branch 0 taken 1888 times.
✓ Branch 1 taken 200 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 2088 for (int pixel : row) {
206
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 1888 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 1888 if (pixel != 0 && pixel != 1) {
207 return false;
208 }
209 }
210 }
211 return true;
212 }
213
214
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 bool MarinLMarkComponentsTBB::ValidationImpl() {
215 const auto &img = GetInput().binary;
216
2/4
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
 24 if (img.empty() || img.front().empty()) {
217 return false;
218 }
219
220 const std::size_t width = img.front().size();
221
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 24 times.
 224 for (const auto &row : img) {
222
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 200 times.
 200 if (row.size() != width) {
223 return false;
224 }
225 }
226
227 return IsBinary(img);
228 }
229
230 24 bool MarinLMarkComponentsTBB::PreProcessingImpl() {
231
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 const auto &img = GetInput().binary;
232 24 height_ = static_cast<int>(img.size());
233 24 width_ = static_cast<int>(img.front().size());
234
235
2/4
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 if (height_ <= 0 || width_ <= 0) {
236 return false;
237 }
238
239 24 const std::uint64_t total_pixels = static_cast<std::uint64_t>(height_) * static_cast<std::uint64_t>(width_);
240
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (total_pixels > kMaxPixels) {
241 return false;
242 }
243
244 24 binary_flat_.assign(static_cast<std::size_t>(total_pixels), 0);
245
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
 24 labels_flat_.assign(static_cast<std::size_t>(total_pixels), 0);
246 labels_out_.clear();
247
248 224 tbb::parallel_for(tbb::blocked_range<int>(0, height_), [&](const tbb::blocked_range<int> &range) {
249
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 200 times.
 400 for (int row = range.begin(); row != range.end(); ++row) {
250 200 const auto row_offset = static_cast<std::size_t>(row) * static_cast<std::size_t>(width_);
251
2/2
✓ Branch 0 taken 1888 times.
✓ Branch 1 taken 200 times.
 2088 for (int col = 0; col < width_; ++col) {
252 1888 binary_flat_[row_offset + static_cast<std::size_t>(col)] =
253 1888 static_cast<std::uint8_t>(img[static_cast<std::size_t>(row)][static_cast<std::size_t>(col)]);
254 }
255 }
256 200 });
257
258 24 return true;
259 }
260
261 24 bool MarinLMarkComponentsTBB::RunImpl() {
262
2/4
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 if (height_ == 0 || width_ == 0) {
263 return true;
264 }
265
266 24 const StripeSetup setup = BuildStripeSetup(height_, width_);
267
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<int> parent(static_cast<std::size_t>(setup.total_max_labels), 0);
268
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 InitializeParents(parent, setup.total_max_labels);
269
270
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int> stripe_max_used(static_cast<std::size_t>(setup.num_stripes), 0);
271
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 tbb::parallel_for(tbb::blocked_range<int>(0, setup.num_stripes), [&](const tbb::blocked_range<int> &range) {
272
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 for (int stripe = range.begin(); stripe != range.end(); ++stripe) {
273 24 LabelStripe(binary_flat_, labels_flat_, parent, setup.stripe_bounds, setup.stripe_base_label, stripe_max_used,
274 width_, stripe);
275 }
276 24 });
277
278 24 MergeStripeBorders(binary_flat_, setup.stripe_bounds, labels_flat_, parent, width_, setup.num_stripes);
279 const std::vector<int> compacted =
280
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 BuildCompactedLabels(parent, setup.stripe_base_label, stripe_max_used, setup.total_max_labels, setup.num_stripes);
281
2/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
 24 ApplyCompactedLabels(labels_flat_, compacted, setup.stripe_bounds, width_, setup.num_stripes);
282
283 return true;
284 24 }
285
286
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 bool MarinLMarkComponentsTBB::PostProcessingImpl() {
287 labels_out_.clear();
288 24 labels_out_.resize(static_cast<std::size_t>(height_));
289
290 224 tbb::parallel_for(tbb::blocked_range<int>(0, height_), [&](const tbb::blocked_range<int> &range) {
291
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 200 times.
 400 for (int row = range.begin(); row != range.end(); ++row) {
292 200 labels_out_[static_cast<std::size_t>(row)].resize(static_cast<std::size_t>(width_));
293 200 const auto row_offset = static_cast<std::size_t>(row) * static_cast<std::size_t>(width_);
294 200 std::copy(labels_flat_.begin() + static_cast<std::ptrdiff_t>(row_offset),
295 labels_flat_.begin() + static_cast<std::ptrdiff_t>(row_offset) + width_,
296 labels_out_[static_cast<std::size_t>(row)].begin());
297 }
298 200 });
299
300 24 GetOutput().labels = std::move(labels_out_);
301 24 return true;
302 }
303
304 } // namespace marin_l_mark_components
305