GCC Code Coverage Report

Directory: ./
File: tasks/nalitov_d_binary/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 245 248 98.8%
Functions: 19 19 100.0%
Branches: 220 300 73.3%
Line Branch Exec Source
1 #include "nalitov_d_binary/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <array>
7 #include <cstddef>
8 #include <cstdint>
9 #include <limits>
10 #include <numeric>
11 #include <queue>
12 #include <ranges>
13 #include <utility>
14 #include <vector>
15
16 #include "nalitov_d_binary/common/include/common.hpp"
17
18 namespace nalitov_d_binary {
19
20 namespace {
21
22 constexpr uint8_t kThreshold = 128;
23
24 [[nodiscard]] size_t ToIndex(int x, int y, int width) {
25
6/6
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 164 times.
✓ Branch 2 taken 63 times.
✓ Branch 3 taken 164 times.
✓ Branch 4 taken 125 times.
✓ Branch 5 taken 123 times.
 702 return (static_cast<size_t>(y) * static_cast<size_t>(width)) + static_cast<size_t>(x);
26 }
27
28 int64_t Cross(const GridPoint &a, const GridPoint &b, const GridPoint &c) {
29 340 const int64_t abx = static_cast<int64_t>(b.x) - static_cast<int64_t>(a.x);
30 340 const int64_t aby = static_cast<int64_t>(b.y) - static_cast<int64_t>(a.y);
31 340 const int64_t bcx = static_cast<int64_t>(c.x) - static_cast<int64_t>(b.x);
32 340 const int64_t bcy = static_cast<int64_t>(c.y) - static_cast<int64_t>(b.y);
33 340 return (abx * bcy) - (aby * bcx);
34 }
35
36 332 void TryVisitNeighborExtended(const std::vector<uint8_t> &extended_pixels, int width, int extended_height,
37 int start_row, int ncol, int nrow, std::vector<bool> &visited,
38 std::queue<GridPoint> &frontier) {
39 332 const int ext_nrow = nrow - start_row + 1;
40
2/2
✓ Branch 0 taken 319 times.
✓ Branch 1 taken 13 times.
 332 if (ext_nrow < 0 || ext_nrow >= extended_height) {
41 return;
42 }
43
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 319 times.
 319 const size_t neighbor_idx = ToIndex(ncol, ext_nrow, width);
44
4/4
✓ Branch 0 taken 156 times.
✓ Branch 1 taken 163 times.
✓ Branch 2 taken 79 times.
✓ Branch 3 taken 77 times.
 319 if (visited[neighbor_idx] || extended_pixels[neighbor_idx] == 0) {
45 return;
46 }
47 visited[neighbor_idx] = true;
48 frontier.emplace(ncol, nrow);
49 }
50
51 6 void BFSCollectGlobal(BinaryImage &image, int start_col, int start_row, std::vector<bool> &visited,
52 std::vector<GridPoint> &out_component) {
53 6 const int width = image.width;
54 6 const int height = image.height;
55
56 6 const std::array<std::pair<int, int>, 4> k_directions = {{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}};
57
58 std::queue<GridPoint> frontier;
59 frontier.emplace(start_col, start_row);
60
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 visited[ToIndex(start_col, start_row, width)] = true;
61
62
2/2
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 6 times.
 69 while (!frontier.empty()) {
63 63 const GridPoint current = frontier.front();
64 frontier.pop();
65 out_component.push_back(current);
66
67
2/2
✓ Branch 0 taken 252 times.
✓ Branch 1 taken 63 times.
 315 for (const auto &d : k_directions) {
68 252 const int ncol = current.x + d.first;
69 252 const int nrow = current.y + d.second;
70
71
8/8
✓ Branch 0 taken 251 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 250 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 249 times.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 1 times.
✓ Branch 7 taken 248 times.
 252 if (ncol < 0 || ncol >= width || nrow < 0 || nrow >= height) {
72 195 continue;
73 }
74
75 const size_t nidx = ToIndex(ncol, nrow, width);
76
4/4
✓ Branch 0 taken 125 times.
✓ Branch 1 taken 123 times.
✓ Branch 2 taken 68 times.
✓ Branch 3 taken 57 times.
 248 if (visited[nidx] || image.pixels[nidx] == 0) {
77 191 continue;
78 }
79
80 visited[nidx] = true;
81 frontier.emplace(ncol, nrow);
82 }
83 }
84 6 }
85
86 8 void BFSCollectExtended(const std::vector<uint8_t> &extended_pixels, int width, int extended_height, int start_ext_col,
87 int start_ext_row, int start_row_global, int start_row, int end_row, std::vector<bool> &visited,
88 std::vector<GridPoint> &out_component, bool &out_touches_local, int &out_min_row) {
89 8 const std::array<std::pair<int, int>, 4> k_directions = {{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}};
90
91 std::queue<GridPoint> frontier;
92
93 frontier.emplace(start_ext_col, start_row_global);
94
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 visited[ToIndex(start_ext_col, start_ext_row, width)] = true;
95
96 8 out_touches_local = false;
97 8 out_min_row = std::numeric_limits<int>::max();
98
99 8 const int max_valid_global_row = start_row + (extended_height - 1);
100
101
2/2
✓ Branch 0 taken 87 times.
✓ Branch 1 taken 8 times.
 95 while (!frontier.empty()) {
102 87 const GridPoint current = frontier.front();
103 frontier.pop();
104 out_component.push_back(current);
105
106
4/4
✓ Branch 0 taken 74 times.
✓ Branch 1 taken 13 times.
✓ Branch 2 taken 63 times.
✓ Branch 3 taken 11 times.
 87 if (current.y >= start_row && current.y < end_row) {
107 63 out_touches_local = true;
108 }
109 87 out_min_row = std::min(out_min_row, current.y);
110
111
2/2
✓ Branch 0 taken 348 times.
✓ Branch 1 taken 87 times.
 435 for (const auto &d : k_directions) {
112 348 const int ncol = current.x + d.first;
113 348 const int nrow = current.y + d.second;
114
115
4/4
✓ Branch 0 taken 344 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 332 times.
 348 if (ncol < 0 || ncol >= width || nrow < 0 || nrow >= max_valid_global_row) {
116 16 continue;
117 }
118
119
1/2
✓ Branch 1 taken 332 times.
✗ Branch 2 not taken.
 332 TryVisitNeighborExtended(extended_pixels, width, extended_height, start_row, ncol, nrow, visited, frontier);
120 }
121 }
122 8 }
123
124 5 void DiscoverGlobalComponents(BinaryImage &image) {
125 5 const int width = image.width;
126 5 const int height = image.height;
127 5 const size_t total_pixels = static_cast<size_t>(width) * static_cast<size_t>(height);
128
129
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 5 times.
 5 std::vector<bool> visited(total_pixels, false);
130 image.components.clear();
131
132
2/2
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 5 times.
 36 for (int row = 0; row < height; ++row) {
133
2/2
✓ Branch 0 taken 227 times.
✓ Branch 1 taken 31 times.
 258 for (int col = 0; col < width; ++col) {
134 const size_t idx = ToIndex(col, row, width);
135
4/4
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 164 times.
✓ Branch 2 taken 57 times.
✓ Branch 3 taken 6 times.
 227 if (image.pixels[idx] == 0 || visited[idx]) {
136 221 continue;
137 }
138 6 std::vector<GridPoint> component;
139
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 BFSCollectGlobal(image, col, row, visited, component);
140
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (!component.empty()) {
141
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 image.components.push_back(std::move(component));
142 }
143 }
144 }
145 5 }
146
147 5 std::vector<int> SerializeHullsToPackedPoints(const BinaryImage &output, const std::vector<int> &hull_sizes) {
148 const int total_pts = static_cast<int>(std::accumulate(hull_sizes.begin(), hull_sizes.end(), 0));
149 5 std::vector<int> packed_points;
150
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 packed_points.reserve(static_cast<size_t>(total_pts) * 2U);
151
152
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 5 times.
 11 for (const auto &hull : output.convex_hulls) {
153
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 6 times.
 19 for (const auto &pt : hull) {
154
1/2
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
 13 packed_points.push_back(pt.x);
155
1/2
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
 13 packed_points.push_back(pt.y);
156 }
157 }
158 5 return packed_points;
159 }
160
161
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 5 void ReconstructHullsFromPackedPoints(BinaryImage &output, const std::vector<int> &packed_points,
162 const std::vector<int> &hull_sizes) {
163 output.convex_hulls.clear();
164 5 output.convex_hulls.reserve(hull_sizes.size());
165
166 size_t offset = 0;
167
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 5 times.
 11 for (int hull_size : hull_sizes) {
168 6 std::vector<GridPoint> hull;
169
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 hull.reserve(static_cast<size_t>(hull_size));
170
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 6 times.
 19 for (int j = 0; j < hull_size; ++j) {
171
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 const int x = packed_points[offset++];
172 13 const int y = packed_points[offset++];
173
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 hull.emplace_back(x, y);
174 }
175 output.convex_hulls.push_back(std::move(hull));
176 }
177 5 }
178
179 } // namespace
180
181
2/4
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
 10 NalitovDBinaryMPI::NalitovDBinaryMPI(const InType &in) : full_image_(in), local_image_() {
182 SetTypeOfTask(GetStaticTypeOfTask());
183
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 GetInput() = in;
184
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Comm_rank(MPI_COMM_WORLD, &rank_);
185
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Comm_size(MPI_COMM_WORLD, &size_);
186 10 }
187
188 10 bool NalitovDBinaryMPI::ValidationImpl() {
189
2/4
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 10 if (GetInput().width <= 0 || GetInput().height <= 0) {
190 return false;
191 }
192 10 const size_t expected_size = static_cast<size_t>(GetInput().width) * static_cast<size_t>(GetInput().height);
193 10 return GetInput().pixels.size() == expected_size;
194 }
195
196 10 bool NalitovDBinaryMPI::PreProcessingImpl() {
197
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank_ == 0) {
198 5 full_image_ = GetInput();
199
2/2
✓ Branch 0 taken 227 times.
✓ Branch 1 taken 5 times.
 232 for (auto &pixel : full_image_.pixels) {
200
2/2
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 63 times.
 391 pixel = pixel > kThreshold ? static_cast<uint8_t>(255) : static_cast<uint8_t>(0);
201 }
202 }
203
204 10 BroadcastDimensions();
205 10 ScatterPixels();
206 10 ThresholdLocalPixels();
207 10 return true;
208 }
209
210 10 bool NalitovDBinaryMPI::RunImpl() {
211 10 FindLocalComponents();
212
213 local_image_.convex_hulls.clear();
214 10 local_image_.convex_hulls.reserve(local_image_.components.size());
215
216
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 10 times.
 16 for (const auto &component : local_image_.components) {
217
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (component.empty()) {
218 ✗ continue;
219 }
220
221
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (component.size() <= 2U) {
222 3 local_image_.convex_hulls.push_back(component);
223 } else {
224
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 local_image_.convex_hulls.push_back(BuildConvexHull(component));
225 }
226 }
227
228 10 CollectGlobalHulls();
229 10 return true;
230 }
231
232 10 bool NalitovDBinaryMPI::PostProcessingImpl() {
233
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank_ == 0) {
234 5 GetOutput() = full_image_;
235 } else {
236 5 GetOutput() = BinaryImage{};
237 }
238 10 BroadcastOutput();
239 10 return true;
240 }
241
242 10 void NalitovDBinaryMPI::BroadcastDimensions() {
243 10 std::array<int, 2> dims = {0, 0};
244
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank_ == 0) {
245 5 dims[0] = full_image_.width;
246 5 dims[1] = full_image_.height;
247 }
248
249 10 MPI_Bcast(dims.data(), static_cast<int>(dims.size()), MPI_INT, 0, MPI_COMM_WORLD);
250 10 local_image_.width = dims[0];
251 10 local_image_.height = dims[1];
252 10 }
253
254 10 void NalitovDBinaryMPI::ScatterPixels() {
255 10 const int width = local_image_.width;
256 10 const int height = local_image_.height;
257
258 10 counts_.assign(size_, 0);
259 10 displs_.assign(size_, 0);
260
261 10 const int base_rows = height / size_;
262 10 const int remainder = height % size_;
263
264 int displacement = 0;
265
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 10 times.
 30 for (int proc = 0; proc < size_; ++proc) {
266
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 6 times.
 20 const int rows = base_rows + (proc < remainder ? 1 : 0);
267
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 counts_[proc] = rows * width;
268 20 displs_[proc] = displacement;
269 20 displacement += counts_[proc];
270
271
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc == rank_) {
272 10 start_row_ = (base_rows * proc) + std::min(proc, remainder);
273 10 end_row_ = start_row_ + rows;
274 }
275 }
276
277 10 local_image_.pixels.resize(static_cast<size_t>(counts_[rank_]));
278
279
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 15 MPI_Scatterv(rank_ == 0 ? full_image_.pixels.data() : nullptr, counts_.data(), displs_.data(), MPI_BYTE,
280
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 local_image_.pixels.data(), counts_[rank_], MPI_BYTE, 0, MPI_COMM_WORLD);
281 10 }
282
283
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 void NalitovDBinaryMPI::ThresholdLocalPixels() {
284 local_image_.components.clear();
285 local_image_.convex_hulls.clear();
286 10 }
287
288 10 void NalitovDBinaryMPI::FindLocalComponents() {
289 10 const int width = local_image_.width;
290 10 const int local_rows = end_row_ - start_row_;
291
292 10 const int extended_height = local_rows + 2;
293 10 std::vector<uint8_t> extended_pixels(static_cast<size_t>(extended_height) * static_cast<size_t>(width), 0);
294
295 using DiffT = std::vector<uint8_t>::difference_type;
296
297
2/2
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 10 times.
 41 for (int row = 0; row < local_rows; ++row) {
298 31 const size_t src_offset = static_cast<size_t>(row) * static_cast<size_t>(width);
299 31 const size_t dst_offset = static_cast<size_t>(row + 1) * static_cast<size_t>(width);
300 31 std::copy_n(local_image_.pixels.begin() + static_cast<DiffT>(src_offset), static_cast<size_t>(width),
301 extended_pixels.begin() + static_cast<DiffT>(dst_offset));
302 }
303
304
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 ExchangeBoundaryRows(extended_pixels, extended_height);
305
306
2/6
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 10 std::vector<bool> visited(extended_pixels.size(), false);
307 local_image_.components.clear();
308
309
2/2
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 10 times.
 41 for (int ext_row = 1; ext_row <= local_rows; ++ext_row) {
310
2/2
✓ Branch 0 taken 227 times.
✓ Branch 1 taken 31 times.
 258 for (int col = 0; col < width; ++col) {
311 const size_t idx = ToIndex(col, ext_row, width);
312
4/4
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 164 times.
✓ Branch 2 taken 55 times.
✓ Branch 3 taken 8 times.
 227 if (extended_pixels[idx] == 0 || visited[idx]) {
313 219 continue;
314 }
315
316 8 const int global_row = start_row_ + ext_row - 1;
317
318 8 std::vector<GridPoint> component;
319 8 bool touches_local = false;
320 8 int min_row = std::numeric_limits<int>::max();
321
322
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 BFSCollectExtended(extended_pixels, width, extended_height, col, ext_row, global_row, start_row_, end_row_,
323 visited, component, touches_local, min_row);
324
325
4/6
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 6 times.
✓ Branch 5 taken 2 times.
 8 if (!component.empty() && touches_local && min_row >= start_row_) {
326
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 local_image_.components.push_back(std::move(component));
327 }
328 }
329 }
330 10 }
331
332 10 void NalitovDBinaryMPI::ExchangeBoundaryRows(std::vector<uint8_t> &extended_pixels, int extended_height) const {
333 10 const int width = local_image_.width;
334 10 const int local_rows = end_row_ - start_row_;
335
336 10 std::vector<MPI_Request> requests;
337
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 requests.reserve(4);
338
339 10 std::vector<uint8_t> top_send_buffer;
340 10 std::vector<uint8_t> bottom_send_buffer;
341
342
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank_ > 0) {
343 requests.emplace_back();
344
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 MPI_Irecv(extended_pixels.data(), width, MPI_BYTE, rank_ - 1, 0, MPI_COMM_WORLD, &requests.back());
345
346
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 top_send_buffer.resize(static_cast<size_t>(width), 0);
347
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 if (local_rows > 0) {
348 5 std::copy_n(local_image_.pixels.begin(), static_cast<size_t>(width), top_send_buffer.begin());
349 }
350
351 requests.emplace_back();
352
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 MPI_Isend(top_send_buffer.data(), width, MPI_BYTE, rank_ - 1, 1, MPI_COMM_WORLD, &requests.back());
353 }
354
355
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank_ < size_ - 1) {
356 requests.emplace_back();
357 5 MPI_Irecv(extended_pixels.data() + (static_cast<size_t>(extended_height - 1) * static_cast<size_t>(width)), width,
358
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 MPI_BYTE, rank_ + 1, 1, MPI_COMM_WORLD, &requests.back());
359
360
1/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 5 bottom_send_buffer.resize(static_cast<size_t>(width), 0);
361
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 if (local_rows > 0) {
362 5 const size_t begin_idx = static_cast<size_t>(local_rows - 1) * static_cast<size_t>(width);
363 const auto begin_it = local_image_.pixels.begin() + static_cast<std::vector<uint8_t>::difference_type>(begin_idx);
364 5 std::copy_n(begin_it, static_cast<size_t>(width), bottom_send_buffer.begin());
365 }
366
367 requests.emplace_back();
368
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 MPI_Isend(bottom_send_buffer.data(), width, MPI_BYTE, rank_ + 1, 0, MPI_COMM_WORLD, &requests.back());
369 }
370
371
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (!requests.empty()) {
372
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Waitall(static_cast<int>(requests.size()), requests.data(), MPI_STATUSES_IGNORE);
373 }
374 10 }
375
376
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 void NalitovDBinaryMPI::CollectGlobalHulls() {
377
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 15 MPI_Gatherv(local_image_.pixels.data(), counts_[rank_], MPI_BYTE, rank_ == 0 ? full_image_.pixels.data() : nullptr,
378 counts_.data(), displs_.data(), MPI_BYTE, 0, MPI_COMM_WORLD);
379
380
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank_ == 0) {
381 5 DiscoverGlobalComponents(full_image_);
382
383 full_image_.convex_hulls.clear();
384 5 full_image_.convex_hulls.reserve(full_image_.components.size());
385
386
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 5 times.
 11 for (const auto &component : full_image_.components) {
387
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (component.empty()) {
388 ✗ continue;
389 }
390
391
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (component.size() <= 2U) {
392 3 full_image_.convex_hulls.push_back(component);
393 } else {
394
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 full_image_.convex_hulls.push_back(BuildConvexHull(component));
395 }
396 }
397 }
398 10 }
399
400
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 void NalitovDBinaryMPI::BroadcastOutput() {
401 BinaryImage &output = GetOutput();
402
403 10 std::array<int, 2> dims = {0, 0};
404
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank_ == 0) {
405 5 dims[0] = output.width;
406 5 dims[1] = output.height;
407 }
408 10 MPI_Bcast(dims.data(), static_cast<int>(dims.size()), MPI_INT, 0, MPI_COMM_WORLD);
409
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank_ != 0) {
410 5 output.width = dims[0];
411 5 output.height = dims[1];
412 }
413
414
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 int hull_count = rank_ == 0 ? static_cast<int>(output.convex_hulls.size()) : 0;
415 10 MPI_Bcast(&hull_count, 1, MPI_INT, 0, MPI_COMM_WORLD);
416
417 10 std::vector<int> hull_sizes;
418
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank_ == 0) {
419
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 hull_sizes.reserve(static_cast<size_t>(hull_count));
420
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 5 times.
 11 for (const auto &hull : output.convex_hulls) {
421
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 hull_sizes.push_back(static_cast<int>(hull.size()));
422 }
423 } else {
424
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 hull_sizes.resize(hull_count);
425 }
426
427
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (hull_count > 0) {
428
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Bcast(hull_sizes.data(), hull_count, MPI_INT, 0, MPI_COMM_WORLD);
429 }
430
431 int total_points = 0;
432
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 10 times.
 22 for (const auto size : hull_sizes) {
433 12 total_points += size;
434 }
435
436 10 std::vector<int> packed_points;
437
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank_ == 0) {
438
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 10 packed_points = SerializeHullsToPackedPoints(output, hull_sizes);
439 } else {
440
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 packed_points.resize(static_cast<size_t>(total_points) * 2U);
441 }
442
443
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (total_points > 0) {
444
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Bcast(packed_points.data(), total_points * 2, MPI_INT, 0, MPI_COMM_WORLD);
445 }
446
447
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank_ != 0) {
448
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 ReconstructHullsFromPackedPoints(output, packed_points, hull_sizes);
449
450
2/6
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 5 output.pixels.assign(static_cast<size_t>(output.width) * static_cast<size_t>(output.height), 0);
451 output.components.clear();
452 }
453 10 }
454
455
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 std::vector<GridPoint> NalitovDBinaryMPI::BuildConvexHull(const std::vector<GridPoint> &points) {
456
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (points.size() <= 2U) {
457 ✗ return points;
458 }
459
460 6 std::vector<GridPoint> sorted_points = points;
461 std::ranges::sort(sorted_points, [](const GridPoint &lhs, const GridPoint &rhs) {
462
18/26
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 49 times.
✓ Branch 5 taken 19 times.
✓ Branch 6 taken 61 times.
✓ Branch 7 taken 15 times.
✓ Branch 8 taken 4 times.
✓ Branch 9 taken 1 times.
✓ Branch 10 taken 1 times.
✓ Branch 11 taken 1 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 1 times.
✓ Branch 14 taken 3 times.
✗ Branch 15 not taken.
✓ Branch 16 taken 2 times.
✓ Branch 17 taken 1 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✓ Branch 20 taken 132 times.
✓ Branch 21 taken 72 times.
✓ Branch 22 taken 54 times.
✓ Branch 23 taken 6 times.
✓ Branch 24 taken 111 times.
✓ Branch 25 taken 56 times.
 589 if (lhs.x != rhs.x) {
463 417 return lhs.x < rhs.x;
464 }
465 172 return lhs.y < rhs.y;
466 });
467
468 const auto unique_range = std::ranges::unique(sorted_points);
469 sorted_points.erase(unique_range.begin(), sorted_points.end());
470
471
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (sorted_points.size() <= 2U) {
472 return sorted_points;
473 }
474
475 6 std::vector<GridPoint> lower;
476
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 std::vector<GridPoint> upper;
477
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 lower.reserve(sorted_points.size());
478
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 upper.reserve(sorted_points.size());
479
480
2/2
✓ Branch 0 taken 107 times.
✓ Branch 1 taken 6 times.
 113 for (const auto &pt : sorted_points) {
481
4/4
✓ Branch 0 taken 169 times.
✓ Branch 1 taken 29 times.
✓ Branch 2 taken 91 times.
✓ Branch 3 taken 78 times.
 198 while (lower.size() >= 2U && Cross(lower[lower.size() - 2U], lower.back(), pt) <= 0) {
482 lower.pop_back();
483 }
484 lower.push_back(pt);
485 }
486
487
2/2
✓ Branch 0 taken 107 times.
✓ Branch 1 taken 6 times.
 113 for (const auto &sorted_point : std::ranges::reverse_view(sorted_points)) {
488
4/4
✓ Branch 0 taken 171 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 81 times.
✓ Branch 3 taken 90 times.
 197 while (upper.size() >= 2U && Cross(upper[upper.size() - 2U], upper.back(), sorted_point) <= 0) {
489 upper.pop_back();
490 }
491 upper.push_back(sorted_point);
492 }
493
494 lower.pop_back();
495 upper.pop_back();
496
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 lower.insert(lower.end(), upper.begin(), upper.end());
497 return lower;
498 }
499
500 } // namespace nalitov_d_binary
501