GCC Code Coverage Report

Directory: ./
File: tasks/muhammadkhon_i_stressen_alg/seq/src/ops_seq.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 104 104 100.0%
Functions: 11 11 100.0%
Branches: 84 148 56.8%
Line Branch Exec Source
1 #include "muhammadkhon_i_stressen_alg/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <stack>
6 #include <utility>
7 #include <vector>
8
9 #include "muhammadkhon_i_stressen_alg/common/include/common.hpp"
10
11 namespace muhammadkhon_i_stressen_alg {
12
13
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 MuhammadkhonIStressenAlgSEQ::MuhammadkhonIStressenAlgSEQ(const InType &in) {
14 SetTypeOfTask(GetStaticTypeOfTask());
15
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
16 GetOutput() = {};
17 48 }
18
19 48 bool MuhammadkhonIStressenAlgSEQ::ValidationImpl() {
20 const auto &in = GetInput();
21
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 48 times.
 48 return in.a_rows > 0 && in.a_cols_b_rows > 0 && in.b_cols > 0 &&
22
2/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 48 times.
 96 in.a.size() == static_cast<size_t>(in.a_rows * in.a_cols_b_rows) &&
23
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 in.b.size() == static_cast<size_t>(in.a_cols_b_rows * in.b_cols);
24 }
25
26 48 bool MuhammadkhonIStressenAlgSEQ::PreProcessingImpl() {
27 GetOutput() = {};
28 const auto &in = GetInput();
29 48 a_rows_ = in.a_rows;
30 48 a_cols_b_rows_ = in.a_cols_b_rows;
31 48 b_cols_ = in.b_cols;
32
33 48 size_t max_dim = std::max({a_rows_, a_cols_b_rows_, b_cols_});
34 48 padded_n_ = 1;
35
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 48 times.
 240 while (padded_n_ < max_dim) {
36 192 padded_n_ *= 2;
37 }
38
39 48 padded_a_.assign(padded_n_ * padded_n_, 0.0);
40 48 padded_b_.assign(padded_n_ * padded_n_, 0.0);
41
42
2/2
✓ Branch 0 taken 1320 times.
✓ Branch 1 taken 48 times.
 1368 for (size_t i = 0; i < a_rows_; ++i) {
43
2/2
✓ Branch 0 taken 67368 times.
✓ Branch 1 taken 1320 times.
 68688 for (size_t j = 0; j < a_cols_b_rows_; ++j) {
44 67368 padded_a_[(i * padded_n_) + j] = in.a[(i * a_cols_b_rows_) + j];
45 }
46 }
47
48
2/2
✓ Branch 0 taken 1240 times.
✓ Branch 1 taken 48 times.
 1288 for (size_t i = 0; i < a_cols_b_rows_; ++i) {
49
2/2
✓ Branch 0 taken 67368 times.
✓ Branch 1 taken 1240 times.
 68608 for (size_t j = 0; j < b_cols_; ++j) {
50 67368 padded_b_[(i * padded_n_) + j] = in.b[(i * b_cols_) + j];
51 }
52 }
53 48 return true;
54 }
55
56 48 bool MuhammadkhonIStressenAlgSEQ::RunImpl() {
57 96 result_c_ = StrassenMultiply(padded_a_, padded_b_, padded_n_);
58
59 auto &out = GetOutput();
60 48 out.assign(a_rows_ * b_cols_, 0.0);
61
62
2/2
✓ Branch 0 taken 1320 times.
✓ Branch 1 taken 48 times.
 1368 for (size_t i = 0; i < a_rows_; ++i) {
63
2/2
✓ Branch 0 taken 68568 times.
✓ Branch 1 taken 1320 times.
 69888 for (size_t j = 0; j < b_cols_; ++j) {
64 68568 out[(i * b_cols_) + j] = result_c_[(i * padded_n_) + j];
65 }
66 }
67 48 return true;
68 }
69
70 48 bool MuhammadkhonIStressenAlgSEQ::PostProcessingImpl() {
71 48 return true;
72 }
73
74 96 std::vector<double> MuhammadkhonIStressenAlgSEQ::Add(const std::vector<double> &mat_a,
75 const std::vector<double> &mat_b) {
76 96 std::vector<double> res(mat_a.size());
77
2/2
✓ Branch 0 taken 98304 times.
✓ Branch 1 taken 96 times.
 98400 for (size_t i = 0; i < mat_a.size(); ++i) {
78 98304 res[i] = mat_a[i] + mat_b[i];
79 }
80 96 return res;
81 }
82
83 64 std::vector<double> MuhammadkhonIStressenAlgSEQ::Subtract(const std::vector<double> &mat_a,
84 const std::vector<double> &mat_b) {
85 64 std::vector<double> res(mat_a.size());
86
2/2
✓ Branch 0 taken 65536 times.
✓ Branch 1 taken 64 times.
 65600 for (size_t i = 0; i < mat_a.size(); ++i) {
87 65536 res[i] = mat_a[i] - mat_b[i];
88 }
89 64 return res;
90 }
91
92 144 std::vector<double> MuhammadkhonIStressenAlgSEQ::BaseMultiply(const std::vector<double> &mat_a,
93 const std::vector<double> &mat_b, size_t n) {
94 144 std::vector<double> res(n * n, 0.0);
95
2/2
✓ Branch 0 taken 3904 times.
✓ Branch 1 taken 144 times.
 4048 for (size_t i = 0; i < n; ++i) {
96
2/2
✓ Branch 0 taken 119040 times.
✓ Branch 1 taken 3904 times.
 122944 for (size_t k = 0; k < n; ++k) {
97
2/2
✓ Branch 0 taken 3736576 times.
✓ Branch 1 taken 119040 times.
 3855616 for (size_t j = 0; j < n; ++j) {
98 3736576 res[(i * n) + j] += mat_a[(i * n) + k] * mat_b[(k * n) + j];
99 }
100 }
101 }
102 144 return res;
103 }
104
105 16 void MuhammadkhonIStressenAlgSEQ::PushStrassenSubtasks(std::stack<StrassenFrame> &frames,
106 const std::vector<double> &mat_a,
107 const std::vector<double> &mat_b, size_t n) {
108 16 size_t h = n / 2;
109 16 size_t sz = h * h;
110 16 std::vector<double> a11(sz);
111
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<double> a12(sz);
112
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<double> a21(sz);
113
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<double> a22(sz);
114
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<double> b11(sz);
115
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<double> b12(sz);
116
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<double> b21(sz);
117
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<double> b22(sz);
118
119
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 16 times.
 528 for (size_t i = 0; i < h; ++i) {
120
2/2
✓ Branch 0 taken 16384 times.
✓ Branch 1 taken 512 times.
 16896 for (size_t j = 0; j < h; ++j) {
121 16384 size_t idx_src = (i * n) + j;
122 16384 size_t idx_dst = (i * h) + j;
123 16384 a11[idx_dst] = mat_a[idx_src];
124 16384 a12[idx_dst] = mat_a[idx_src + h];
125 16384 a21[idx_dst] = mat_a[idx_src + (h * n)];
126 16384 a22[idx_dst] = mat_a[idx_src + (h * n) + h];
127
128 16384 b11[idx_dst] = mat_b[idx_src];
129 16384 b12[idx_dst] = mat_b[idx_src + h];
130 16384 b21[idx_dst] = mat_b[idx_src + (h * n)];
131 16384 b22[idx_dst] = mat_b[idx_src + (h * n) + h];
132 }
133 }
134
135
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 32 frames.push({{}, {}, n, 1});
136
137 16 frames.push({Subtract(a12, a22), Add(b21, b22), h, 0});
138 16 frames.push({Subtract(a21, a11), Add(b11, b12), h, 0});
139 16 frames.push({Add(a11, a12), b22, h, 0});
140 16 frames.push({a22, Subtract(b21, b11), h, 0});
141 16 frames.push({a11, Subtract(b12, b22), h, 0});
142 16 frames.push({Add(a21, a22), b11, h, 0});
143
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 16 frames.push({Add(a11, a22), Add(b11, b22), h, 0});
144
21/42
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 16 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 16 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 16 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 16 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 16 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 16 times.
✗ Branch 20 not taken.
✓ Branch 22 taken 16 times.
✗ Branch 23 not taken.
✓ Branch 25 taken 16 times.
✗ Branch 26 not taken.
✓ Branch 28 taken 16 times.
✗ Branch 29 not taken.
✓ Branch 31 taken 16 times.
✗ Branch 32 not taken.
✓ Branch 34 taken 16 times.
✗ Branch 35 not taken.
✓ Branch 37 taken 16 times.
✗ Branch 38 not taken.
✓ Branch 40 taken 16 times.
✗ Branch 41 not taken.
✓ Branch 43 taken 16 times.
✗ Branch 44 not taken.
✓ Branch 46 taken 16 times.
✗ Branch 47 not taken.
✓ Branch 49 taken 16 times.
✗ Branch 50 not taken.
✓ Branch 52 taken 16 times.
✗ Branch 53 not taken.
✓ Branch 55 taken 16 times.
✗ Branch 56 not taken.
✓ Branch 58 taken 16 times.
✗ Branch 59 not taken.
✓ Branch 61 taken 16 times.
✗ Branch 62 not taken.
 128 }
145
146
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 std::vector<double> MuhammadkhonIStressenAlgSEQ::CombineStrassenResults(std::stack<std::vector<double>> &results,
147 size_t n) {
148 auto p7 = std::move(results.top());
149 results.pop();
150 auto p6 = std::move(results.top());
151 results.pop();
152 auto p5 = std::move(results.top());
153 results.pop();
154 auto p4 = std::move(results.top());
155 results.pop();
156 auto p3 = std::move(results.top());
157 results.pop();
158 auto p2 = std::move(results.top());
159 results.pop();
160 auto p1 = std::move(results.top());
161 results.pop();
162
163 16 size_t h = n / 2;
164
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<double> res(n * n);
165
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 16 times.
 528 for (size_t i = 0; i < h; ++i) {
166
2/2
✓ Branch 0 taken 16384 times.
✓ Branch 1 taken 512 times.
 16896 for (size_t j = 0; j < h; ++j) {
167 16384 size_t idx = (i * h) + j;
168 16384 res[(i * n) + j] = p1[idx] + p4[idx] - p5[idx] + p7[idx];
169 16384 res[(i * n) + j + h] = p3[idx] + p5[idx];
170 16384 res[((i + h) * n) + j] = p2[idx] + p4[idx];
171 16384 res[((i + h) * n) + j + h] = p1[idx] - p2[idx] + p3[idx] + p6[idx];
172 }
173 }
174 16 return res;
175 }
176
177 48 std::vector<double> MuhammadkhonIStressenAlgSEQ::StrassenMultiply(const std::vector<double> &mat_a,
178 const std::vector<double> &mat_b, size_t n) {
179 std::stack<StrassenFrame> frames;
180 std::stack<std::vector<double>> results;
181
182 48 frames.push({mat_a, mat_b, n, 0});
183
184
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 48 times.
 224 while (!frames.empty()) {
185 StrassenFrame current = std::move(frames.top());
186 frames.pop();
187
188
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 16 times.
 176 if (current.stage == 0) {
189
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 16 times.
 160 if (current.n <= 32) {
190
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 288 results.push(BaseMultiply(current.mat_a, current.mat_b, current.n));
191 } else {
192
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 PushStrassenSubtasks(frames, current.mat_a, current.mat_b, current.n);
193 }
194 } else {
195
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 32 results.push(CombineStrassenResults(results, current.n));
196 }
197 176 }
198
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 96 return results.top();
199
3/6
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 48 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 48 times.
✗ Branch 8 not taken.
 48 }
200 } // namespace muhammadkhon_i_stressen_alg
201