GCC Code Coverage Report

Directory: ./
File: tasks/kamalagin_a_binary_image_convex_hull/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 177 179 98.9%
Functions: 20 20 100.0%
Branches: 147 224 65.6%
Line Branch Exec Source
1 #include "kamalagin_a_binary_image_convex_hull/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <array>
8 #include <cstddef>
9 #include <cstdint>
10 #include <utility>
11 #include <vector>
12
13 #include "kamalagin_a_binary_image_convex_hull/common/include/common.hpp"
14
15 namespace kamalagin_a_binary_image_convex_hull {
16
17 namespace {
18
19 constexpr std::array<std::pair<int, int>, 4> kFourNeighbors = {{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}};
20
21 int64_t Cross(const Point &o, const Point &a, const Point &b) {
22 33 return (static_cast<int64_t>(a.x - o.x) * (b.y - o.y)) - (static_cast<int64_t>(a.y - o.y) * (b.x - o.x));
23 }
24
25 int64_t DistSq(const Point &a, const Point &b) {
26 14 const int dx = a.x - b.x;
27 14 const int dy = a.y - b.y;
28 14 return (static_cast<int64_t>(dx) * dx) + (static_cast<int64_t>(dy) * dy);
29 }
30
31 3 size_t GrahamFindPivot(std::vector<Point> &pts) {
32 size_t pivot = 0;
33 const size_t n = pts.size();
34
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 3 times.
 16 for (size_t i = 1; i < n; ++i) {
35
4/6
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 7 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 6 times.
 13 if (pts[i].y < pts[pivot].y || (pts[i].y == pts[pivot].y && pts[i].x < pts[pivot].x)) {
36 pivot = i;
37 }
38 }
39 3 return pivot;
40 }
41
42 3 void GrahamCollinearReduce(std::vector<Point> &pts) {
43 size_t m = 1;
44 const size_t n = pts.size();
45
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 3 times.
 13 for (size_t i = 2; i < n; ++i) {
46
4/4
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 3 times.
 18 while (m > 0 && Cross(pts[m - 1], pts[m], pts[i]) == 0) {
47 --m;
48 }
49 10 ++m;
50 10 pts[m] = pts[i];
51 }
52 3 pts.resize(m + 1);
53 3 }
54
55
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 void GrahamScan(std::vector<Point> &pts, Hull &out) {
56 out.push_back(pts[0]);
57
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 times.
 3 if (pts.size() <= 2) {
58
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 if (pts.size() == 2) {
59 out.push_back(pts[1]);
60 }
61 2 return;
62 }
63 out.push_back(pts[1]);
64
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 times.
 3 for (size_t i = 2; i < pts.size(); ++i) {
65
2/4
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
 2 while (out.size() >= 2 && Cross(out[out.size() - 2], out.back(), pts[i]) <= 0) {
66 out.pop_back();
67 }
68 out.push_back(pts[i]);
69 }
70 }
71
72
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 void GrahamHull(std::vector<Point> &pts, Hull &out) {
73 out.clear();
74 const size_t n = pts.size();
75
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 3 times.
 8 if (n <= 1) {
76
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 if (n == 1) {
77 out.push_back(pts[0]);
78 }
79 5 return;
80 }
81 3 const size_t pivot = GrahamFindPivot(pts);
82 std::swap(pts[0], pts[pivot]);
83 const Point &p0 = pts[0];
84 23 std::sort(pts.begin() + 1, pts.end(), [&p0](const Point &a, const Point &b) {
85 20 const int64_t c = Cross(p0, a, b);
86
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 14 times.
 20 if (c != 0) {
87 6 return c > 0;
88 }
89 14 return DistSq(p0, a) < DistSq(p0, b);
90 });
91 3 GrahamCollinearReduce(pts);
92 3 GrahamScan(pts, out);
93 }
94
95 8 void FloodFillComponent(const BinaryImage &img, int start_row, int start_col, std::vector<int> &label,
96 std::vector<Point> &component_pts) {
97 8 const int rows = img.rows;
98
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 6 times.
 8 const int cols = img.cols;
99 component_pts.clear();
100 8 std::vector<std::pair<int, int>> stack;
101
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 stack.emplace_back(start_row, start_col);
102 8 const size_t start_idx = img.Index(start_row, start_col);
103 8 label[start_idx] = 1;
104
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 8 times.
 29 while (!stack.empty()) {
105 const auto [cur_r, cur_c] = stack.back();
106 stack.pop_back();
107
1/4
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 21 component_pts.push_back(Point{.x = cur_c, .y = cur_r});
108
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 21 times.
 105 for (const auto &[dr, dc] : kFourNeighbors) {
109 84 const int nr = cur_r + dr;
110 84 const int nc = cur_c + dc;
111
8/8
✓ Branch 0 taken 71 times.
✓ Branch 1 taken 13 times.
✓ Branch 2 taken 58 times.
✓ Branch 3 taken 13 times.
✓ Branch 4 taken 47 times.
✓ Branch 5 taken 11 times.
✓ Branch 6 taken 11 times.
✓ Branch 7 taken 36 times.
 84 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
112 48 continue;
113 }
114 const size_t nidx = img.Index(nr, nc);
115
4/4
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 13 times.
✓ Branch 3 taken 17 times.
 36 if (img.data[nidx] != 0 && label[nidx] == 0) {
116 13 label[nidx] = 1;
117
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 stack.emplace_back(nr, nc);
118 }
119 }
120 }
121 8 }
122
123 7 std::vector<std::vector<Point>> ExtractComponents(const BinaryImage &img) {
124 7 std::vector<std::vector<Point>> components;
125
3/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 7 if (img.rows <= 0 || img.cols <= 0) {
126 return components;
127 }
128
129 6 const size_t total = static_cast<size_t>(img.rows) * static_cast<size_t>(img.cols);
130
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 std::vector<int> label(total, 0);
131 6 std::vector<Point> component_pts;
132
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 component_pts.reserve(total);
133
134
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 6 times.
 19 for (int row = 0; row < img.rows; ++row) {
135
2/2
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 13 times.
 44 for (int col = 0; col < img.cols; ++col) {
136 const size_t idx = img.Index(row, col);
137
4/4
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 10 times.
✓ Branch 2 taken 13 times.
✓ Branch 3 taken 8 times.
 31 if (img.data[idx] == 0 || label[idx] != 0) {
138 23 continue;
139 }
140
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 FloodFillComponent(img, row, col, label, component_pts);
141
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 components.push_back(component_pts);
142 }
143 }
144 return components;
145 ✗ }
146
147 28 std::vector<int> FlattenComponents(const std::vector<std::vector<Point>> &comps) {
148 28 std::vector<int> flat;
149
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 28 times.
 44 for (const auto &comp : comps) {
150
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 flat.push_back(static_cast<int>(comp.size()));
151
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 16 times.
 50 for (const auto &p : comp) {
152
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 16 times.
 34 flat.push_back(p.x);
153
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 26 times.
 34 flat.push_back(p.y);
154 }
155 }
156 28 return flat;
157 }
158
159 28 std::vector<std::vector<Point>> UnflattenComponents(const std::vector<int> &flat) {
160 28 std::vector<std::vector<Point>> comps;
161 std::size_t pos = 0;
162
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 28 times.
 52 while (pos < flat.size()) {
163
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 const int cnt = flat[pos++];
164
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<Point> comp;
165
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 comp.reserve(static_cast<std::size_t>(std::max(0, cnt)));
166
3/4
✓ Branch 0 taken 47 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 47 times.
✗ Branch 3 not taken.
 71 for (int i = 0; i < cnt && (pos + 1) < flat.size(); ++i) {
167
1/4
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 47 comp.push_back(Point{.x = flat[pos], .y = flat[pos + 1]});
168 47 pos += 2;
169 }
170 comps.push_back(std::move(comp));
171 }
172 28 return comps;
173 ✗ }
174
175 14 std::vector<int> MakeDispls(const std::vector<int> &counts) {
176 14 std::vector<int> displs(counts.size(), 0);
177
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
 28 for (std::size_t i = 1; i < counts.size(); ++i) {
178 14 displs[i] = displs[i - 1] + counts[i - 1];
179 }
180 14 return displs;
181 }
182
183 7 std::vector<int> MakeComponentCounts(int total_components, int proc_count) {
184 7 std::vector<int> comp_counts(static_cast<std::size_t>(proc_count), 0);
185
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 7 times.
 21 for (int i = 0; i < proc_count; ++i) {
186 14 comp_counts[static_cast<std::size_t>(i)] =
187
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 4 times.
 24 (total_components / proc_count) + ((i < (total_components % proc_count)) ? 1 : 0);
188 }
189 7 return comp_counts;
190 }
191
192 7 std::vector<int> FlattenDistributedComponents(const std::vector<std::vector<Point>> &all_components,
193 const std::vector<int> &comp_counts, std::vector<int> &send_counts) {
194 7 std::vector<int> flat_send;
195 int comp_offset = 0;
196
197
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 7 times.
 21 for (std::size_t proc = 0; proc < comp_counts.size(); ++proc) {
198
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 std::vector<std::vector<Point>> part;
199
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 part.reserve(static_cast<std::size_t>(comp_counts[proc]));
200
201
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 14 times.
 22 for (int j = 0; j < comp_counts[proc]; ++j) {
202
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 const auto comp_index = static_cast<std::size_t>(comp_offset) + static_cast<std::size_t>(j);
203
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 part.push_back(all_components[comp_index]);
204 }
205
206 14 comp_offset += comp_counts[proc];
207
208
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 const std::vector<int> flat_part = FlattenComponents(part);
209
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 send_counts[proc] = static_cast<int>(flat_part.size());
210
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 6 times.
 14 flat_send.insert(flat_send.end(), flat_part.begin(), flat_part.end());
211 14 }
212
213 7 return flat_send;
214 }
215
216 14 HullList BuildLocalHulls(std::vector<std::vector<Point>> local_components) {
217 14 HullList local_hulls(local_components.size());
218 14 const int local_count = static_cast<int>(local_components.size());
219
220 14 #pragma omp parallel for default(none) shared(local_components, local_hulls, local_count) schedule(static)
221 for (int i = 0; i < local_count; ++i) {
222 const auto idx = static_cast<std::size_t>(i);
223 std::vector<Point> pts = std::move(local_components[idx]);
224 GrahamHull(pts, local_hulls[idx]);
225 }
226
227 14 return local_hulls;
228 }
229
230 14 std::vector<int> GatherFlatHulls(const std::vector<int> &flat_local_hulls, int rank, int size) {
231 14 const int local_hulls_size = static_cast<int>(flat_local_hulls.size());
232
233
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 std::vector<int> recv_hull_counts(static_cast<std::size_t>(size), 0);
234
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Gather(&local_hulls_size, 1, MPI_INT, recv_hull_counts.data(), 1, MPI_INT, 0, MPI_COMM_WORLD);
235
236 14 std::vector<int> recv_hull_displs;
237 14 std::vector<int> flat_hulls_root;
238
239
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank == 0) {
240
2/6
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 7 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 14 recv_hull_displs = MakeDispls(recv_hull_counts);
241
242 int total_size = 0;
243
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 if (!recv_hull_counts.empty()) {
244 const auto last_idx = recv_hull_counts.size() - 1;
245 7 total_size = recv_hull_displs[last_idx] + recv_hull_counts[last_idx];
246 }
247
248
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 flat_hulls_root.resize(static_cast<std::size_t>(total_size));
249 }
250
251
3/4
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
✓ Branch 3 taken 14 times.
✗ Branch 4 not taken.
 21 MPI_Gatherv(flat_local_hulls.data(), local_hulls_size, MPI_INT, rank == 0 ? flat_hulls_root.data() : nullptr,
252 recv_hull_counts.data(), rank == 0 ? recv_hull_displs.data() : nullptr, MPI_INT, 0, MPI_COMM_WORLD);
253
254 14 return flat_hulls_root;
255 }
256
257 HullList FlatToHullList(const std::vector<int> &flat) {
258
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 return UnflattenComponents(flat);
259 }
260
261 14 HullList SolveAllMpi(const BinaryImage &img) {
262 14 int rank = 0;
263 14 int size = 1;
264 14 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
265 14 MPI_Comm_size(MPI_COMM_WORLD, &size);
266
267 14 std::vector<int> send_counts(static_cast<std::size_t>(size), 0);
268
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<int> send_displs(static_cast<std::size_t>(size), 0);
269 14 std::vector<int> flat_send;
270
271
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank == 0) {
272
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 const auto all_components = ExtractComponents(img);
273 7 const int total_components = static_cast<int>(all_components.size());
274
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 const auto comp_counts = MakeComponentCounts(total_components, size);
275
276
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 flat_send = FlattenDistributedComponents(all_components, comp_counts, send_counts);
277
2/6
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 7 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 14 send_displs = MakeDispls(send_counts);
278 7 }
279
280
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 int recv_count = 0;
281
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Scatter(send_counts.data(), 1, MPI_INT, &recv_count, 1, MPI_INT, 0, MPI_COMM_WORLD);
282
283
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<int> flat_recv(static_cast<std::size_t>(recv_count));
284
3/4
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
✓ Branch 3 taken 14 times.
✗ Branch 4 not taken.
 21 MPI_Scatterv(rank == 0 ? flat_send.data() : nullptr, send_counts.data(), send_displs.data(), MPI_INT,
285 flat_recv.data(), recv_count, MPI_INT, 0, MPI_COMM_WORLD);
286
287
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 auto local_components = UnflattenComponents(flat_recv);
288
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 const HullList local_hulls = BuildLocalHulls(std::move(local_components));
289
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 const std::vector<int> flat_local_hulls = FlattenComponents(local_hulls);
290
291 14 std::vector<int> flat_broadcast;
292
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank == 0) {
293
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 14 flat_broadcast = GatherFlatHulls(flat_local_hulls, rank, size);
294 } else {
295
1/4
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 GatherFlatHulls(flat_local_hulls, rank, size);
296 }
297
298 14 int broadcast_size = 0;
299
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank == 0) {
300 7 broadcast_size = static_cast<int>(flat_broadcast.size());
301 }
302
303
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Bcast(&broadcast_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
304
305
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank != 0) {
306
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 flat_broadcast.resize(static_cast<std::size_t>(broadcast_size));
307 }
308
309
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Bcast(flat_broadcast.data(), broadcast_size, MPI_INT, 0, MPI_COMM_WORLD);
310
311 14 return FlatToHullList(flat_broadcast);
312 14 }
313
314 } // namespace
315
316
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 KamalaginABinaryImageConvexHullALL::KamalaginABinaryImageConvexHullALL(const InType &in) {
317 SetTypeOfTask(GetStaticTypeOfTask());
318 GetInput() = in;
319 14 GetOutput() = HullList{};
320 14 }
321
322 14 bool KamalaginABinaryImageConvexHullALL::ValidationImpl() {
323 const auto &img = GetInput();
324
2/4
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 if (img.rows < 0 || img.cols < 0) {
325 return false;
326 }
327
3/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12 times.
 14 if (img.rows == 0 || img.cols == 0) {
328 2 return img.data.empty();
329 }
330
2/4
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 12 if (img.rows > 8192 || img.cols > 8192) {
331 return false;
332 }
333 12 return (static_cast<size_t>(img.rows) * static_cast<size_t>(img.cols)) == img.data.size();
334 }
335
336
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14 times.
 14 bool KamalaginABinaryImageConvexHullALL::PreProcessingImpl() {
337 GetOutput().clear();
338 14 return true;
339 }
340
341 14 bool KamalaginABinaryImageConvexHullALL::RunImpl() {
342 14 GetOutput() = SolveAllMpi(GetInput());
343 14 return true;
344 }
345
346 14 bool KamalaginABinaryImageConvexHullALL::PostProcessingImpl() {
347 14 return true;
348 }
349
350 } // namespace kamalagin_a_binary_image_convex_hull
351