GCC Code Coverage Report

Directory: ./
File: tasks/titaev_m_sortirovka_betchera/seq/src/ops_seq.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 55 60 91.7%
Functions: 9 10 90.0%
Branches: 42 62 67.7%
Line Branch Exec Source
1 #include "titaev_m_sortirovka_betchera/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstdint>
5 #include <cstring>
6 #include <vector>
7
8 #include "titaev_m_sortirovka_betchera/common/include/common.hpp"
9
10 namespace titaev_m_sortirovka_betchera {
11
12 namespace {
13
14 uint64_t DoubleToOrderedUint(double value) {
15 uint64_t bits = 0;
16 std::memcpy(&bits, &value, sizeof(double));
17 constexpr uint64_t kSignMask = (1ULL << 63);
18
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 1352 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 1352 if ((bits & kSignMask) != 0ULL) {
19 ✗ bits = ~bits;
20 } else {
21 1352 bits ^= kSignMask;
22 }
23 return bits;
24 }
25
26 double OrderedUintToDouble(uint64_t bits) {
27 constexpr uint64_t kSignMask = (1ULL << 63);
28 1352 if ((bits & kSignMask) != 0ULL) {
29 1352 bits ^= kSignMask;
30 } else {
31 ✗ bits = ~bits;
32 }
33 double result = 0.0;
34 std::memcpy(&result, &bits, sizeof(double));
35 return result;
36 }
37
38 } // namespace
39
40
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 TitaevSortirovkaBetcheraSEQ::TitaevSortirovkaBetcheraSEQ(const InType &in) {
41 SetTypeOfTask(GetStaticTypeOfTask());
42
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 GetInput() = in;
43 GetOutput().clear();
44 64 }
45
46 64 bool TitaevSortirovkaBetcheraSEQ::ValidationImpl() {
47 64 return !GetInput().empty();
48 }
49
50 64 bool TitaevSortirovkaBetcheraSEQ::PreProcessingImpl() {
51 64 GetOutput() = GetInput();
52 64 return true;
53 }
54
55 ✗ void TitaevSortirovkaBetcheraSEQ::ConvertToKeys(const InType &input, std::vector<uint64_t> &keys) {
56 const std::size_t n = input.size();
57
2/4
✓ Branch 0 taken 1352 times.
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 1408 for (std::size_t i = 0; i < n; i++) {
58
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 1352 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 2704 keys[i] = DoubleToOrderedUint(input[i]);
59 }
60 ✗ }
61
62
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 void TitaevSortirovkaBetcheraSEQ::RadixSort(std::vector<uint64_t> &keys) {
63 const std::size_t n = keys.size();
64
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (n <= 1) {
65 ✗ return;
66 }
67
68 constexpr int kBits = 8;
69 constexpr int kBuckets = 1 << kBits;
70 constexpr int kPasses = 64 / kBits;
71
72 56 std::vector<uint64_t> tmp(n);
73
74
2/2
✓ Branch 0 taken 448 times.
✓ Branch 1 taken 56 times.
 504 for (int pass = 0; pass < kPasses; pass++) {
75
1/4
✓ Branch 1 taken 448 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 448 std::vector<std::size_t> count(kBuckets, 0);
76
77
2/2
✓ Branch 0 taken 10816 times.
✓ Branch 1 taken 448 times.
 11264 for (std::size_t i = 0; i < n; i++) {
78 10816 const std::size_t bucket = (keys[i] >> (pass * kBits)) & (kBuckets - 1);
79 10816 count[bucket]++;
80 }
81
82
2/2
✓ Branch 0 taken 114240 times.
✓ Branch 1 taken 448 times.
 114688 for (int i = 1; i < kBuckets; i++) {
83 114240 count[i] += count[i - 1];
84 }
85
86
2/2
✓ Branch 0 taken 10816 times.
✓ Branch 1 taken 448 times.
 11264 for (std::size_t i = n; i-- > 0;) {
87 10816 const std::size_t bucket = (keys[i] >> (pass * kBits)) & (kBuckets - 1);
88 10816 tmp[--count[bucket]] = keys[i];
89 }
90
91 keys.swap(tmp);
92 }
93 }
94
95 56 void TitaevSortirovkaBetcheraSEQ::ConvertFromKeys(const std::vector<uint64_t> &keys, OutType &output) {
96 const std::size_t n = keys.size();
97 56 output.resize(n);
98
2/2
✓ Branch 0 taken 1352 times.
✓ Branch 1 taken 56 times.
 1408 for (std::size_t i = 0; i < n; i++) {
99
1/2
✓ Branch 0 taken 1352 times.
✗ Branch 1 not taken.
 2704 output[i] = OrderedUintToDouble(keys[i]);
100 }
101 56 }
102
103 280 void TitaevSortirovkaBetcheraSEQ::BatcherStage(OutType &result, std::size_t array_size, std::size_t block,
104 std::size_t step) {
105
2/2
✓ Branch 0 taken 5616 times.
✓ Branch 1 taken 280 times.
 5896 for (std::size_t i = 0; i < array_size; i++) {
106 5616 const std::size_t partner = i ^ step;
107
2/2
✓ Branch 0 taken 2808 times.
✓ Branch 1 taken 2808 times.
 5616 if (partner <= i) {
108 2808 continue;
109 }
110 2808 const bool ascending = ((i & block) == 0);
111
2/2
✓ Branch 0 taken 1920 times.
✓ Branch 1 taken 888 times.
 2808 const bool need_swap = ascending ? (result[i] > result[partner]) : (result[i] < result[partner]);
112
2/2
✓ Branch 0 taken 1280 times.
✓ Branch 1 taken 1528 times.
 2808 if (need_swap) {
113 std::swap(result[i], result[partner]);
114 }
115 }
116 280 }
117
118
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 void TitaevSortirovkaBetcheraSEQ::BatcherSort() {
119 auto &result = GetOutput();
120 const std::size_t n = result.size();
121
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (n < 2) {
122 return;
123 }
124
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 40 times.
 160 for (std::size_t block = 2; block <= n; block <<= 1) {
125
2/2
✓ Branch 0 taken 280 times.
✓ Branch 1 taken 120 times.
 400 for (std::size_t step = block >> 1; step > 0; step >>= 1) {
126 280 BatcherStage(result, n, block, step);
127 }
128 }
129 }
130
131
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 8 times.
 64 bool TitaevSortirovkaBetcheraSEQ::RunImpl() {
132 auto &input = GetInput();
133 const std::size_t n = input.size();
134
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 8 times.
 64 if (n <= 1) {
135 return true;
136 }
137
138 56 std::vector<uint64_t> keys(n);
139 ConvertToKeys(input, keys);
140
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 RadixSort(keys);
141
142
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 ConvertFromKeys(keys, GetOutput());
143
144
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 16 times.
 56 if ((n & (n - 1)) == 0) {
145 40 BatcherSort();
146 }
147
148 return true;
149 }
150
151 64 bool TitaevSortirovkaBetcheraSEQ::PostProcessingImpl() {
152 64 return true;
153 }
154
155 } // namespace titaev_m_sortirovka_betchera
156