| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "sannikov_i_shtrassen_algorithm/seq/include/ops_seq.hpp" | ||
| 2 | |||
| 3 | #include <cstddef> | ||
| 4 | #include <tuple> | ||
| 5 | #include <utility> | ||
| 6 | #include <vector> | ||
| 7 | |||
| 8 | #include "sannikov_i_shtrassen_algorithm/common/include/common.hpp" | ||
| 9 | |||
| 10 | namespace sannikov_i_shtrassen_algorithm { | ||
| 11 | |||
| 12 | namespace { | ||
| 13 | |||
| 14 | using Matrix = std::vector<std::vector<double>>; | ||
| 15 | using Flat = std::vector<double>; | ||
| 16 | |||
| 17 | constexpr std::size_t kClassicThreshold = 2; | ||
| 18 | |||
| 19 | std::size_t NextPow2(std::size_t value) { | ||
| 20 | std::size_t pow2 = 1; | ||
| 21 |
2/2✓ Branch 0 taken 160 times.
✓ Branch 1 taken 96 times.
|
256 | while (pow2 < value) { |
| 22 | 160 | pow2 <<= 1U; | |
| 23 | } | ||
| 24 | return pow2; | ||
| 25 | } | ||
| 26 | |||
| 27 | std::size_t Idx(std::size_t row, std::size_t col, std::size_t ld) { | ||
| 28 | 9112 | return (row * ld) + col; | |
| 29 | } | ||
| 30 | |||
| 31 | struct View { | ||
| 32 | const double *data = nullptr; | ||
| 33 | std::size_t ld = 0; | ||
| 34 | std::size_t row0 = 0; | ||
| 35 | std::size_t col0 = 0; | ||
| 36 | std::size_t n = 0; | ||
| 37 | }; | ||
| 38 | |||
| 39 | View MakeView(const Flat &buf, std::size_t n) { | ||
| 40 |
1/2✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
|
96 | View v; |
| 41 | 96 | v.data = buf.data(); | |
| 42 | 96 | v.ld = n; | |
| 43 | v.row0 = 0; | ||
| 44 | v.col0 = 0; | ||
| 45 | 96 | v.n = n; | |
| 46 | return v; | ||
| 47 | } | ||
| 48 | |||
| 49 | View SubView(const View &parent, std::size_t dr, std::size_t dc, std::size_t n) { | ||
| 50 | View v; | ||
| 51 | 224 | v.data = parent.data; | |
| 52 | 224 | v.ld = parent.ld; | |
| 53 | 224 | v.row0 = parent.row0 + dr; | |
| 54 | 224 | v.col0 = parent.col0 + dc; | |
| 55 | v.n = n; | ||
| 56 | return v; | ||
| 57 | } | ||
| 58 | |||
| 59 | double At(const View &v, std::size_t req, std::size_t ceq) { | ||
| 60 | 28960 | return v.data[Idx(v.row0 + req, v.col0 + ceq, v.ld)]; | |
| 61 | } | ||
| 62 | |||
| 63 | 192 | void PackPadToFlat(const Matrix &src, std::size_t n0, std::size_t m, Flat *out_flat) { | |
| 64 | 192 | out_flat->assign(m * m, 0.0); | |
| 65 |
2/2✓ Branch 0 taken 656 times.
✓ Branch 1 taken 192 times.
|
848 | for (std::size_t row = 0; row < n0; ++row) { |
| 66 |
2/2✓ Branch 0 taken 3024 times.
✓ Branch 1 taken 656 times.
|
3680 | for (std::size_t col = 0; col < n0; ++col) { |
| 67 | 3024 | (*out_flat)[Idx(row, col, m)] = src[row][col]; | |
| 68 | } | ||
| 69 | } | ||
| 70 | 192 | } | |
| 71 | |||
| 72 | 96 | Matrix UnpackCropFromFlat(const Flat &flat, std::size_t m, std::size_t n0) { | |
| 73 |
1/2✓ Branch 2 taken 96 times.
✗ Branch 3 not taken.
|
96 | Matrix out(n0, std::vector<double>(n0, 0.0)); |
| 74 |
2/2✓ Branch 0 taken 328 times.
✓ Branch 1 taken 96 times.
|
424 | for (std::size_t row = 0; row < n0; ++row) { |
| 75 |
2/2✓ Branch 0 taken 1512 times.
✓ Branch 1 taken 328 times.
|
1840 | for (std::size_t col = 0; col < n0; ++col) { |
| 76 | 1512 | out[row][col] = flat[Idx(row, col, m)]; | |
| 77 | } | ||
| 78 | } | ||
| 79 | 96 | return out; | |
| 80 | } | ||
| 81 | |||
| 82 | struct OwnedView { | ||
| 83 | Flat buf; | ||
| 84 | View view; | ||
| 85 | }; | ||
| 86 | |||
| 87 | 1344 | void FillAdd(const View &a, const View &b, Flat *out) { | |
| 88 | 1344 | const std::size_t n = a.n; | |
| 89 | 1344 | out->assign(n * n, 0.0); | |
| 90 |
2/2✓ Branch 0 taken 2976 times.
✓ Branch 1 taken 1344 times.
|
4320 | for (std::size_t req = 0; req < n; ++req) { |
| 91 |
2/2✓ Branch 0 taken 7104 times.
✓ Branch 1 taken 2976 times.
|
10080 | for (std::size_t ceq = 0; ceq < n; ++ceq) { |
| 92 | 7104 | (*out)[Idx(req, ceq, n)] = At(a, req, ceq) + At(b, req, ceq); | |
| 93 | } | ||
| 94 | } | ||
| 95 | 1344 | } | |
| 96 | |||
| 97 | 896 | void FillSub(const View &a, const View &b, Flat *out) { | |
| 98 | 896 | const std::size_t n = a.n; | |
| 99 | 896 | out->assign(n * n, 0.0); | |
| 100 |
2/2✓ Branch 0 taken 1984 times.
✓ Branch 1 taken 896 times.
|
2880 | for (std::size_t req = 0; req < n; ++req) { |
| 101 |
2/2✓ Branch 0 taken 4736 times.
✓ Branch 1 taken 1984 times.
|
6720 | for (std::size_t ceq = 0; ceq < n; ++ceq) { |
| 102 | 4736 | (*out)[Idx(req, ceq, n)] = At(a, req, ceq) - At(b, req, ceq); | |
| 103 | } | ||
| 104 | } | ||
| 105 | 896 | } | |
| 106 | |||
| 107 | 1440 | Flat MultiplyClassicView(const View &a, const View &b) { | |
| 108 | 1440 | const std::size_t n = a.n; | |
| 109 | 1440 | Flat ceq(n * n, 0.0); | |
| 110 | |||
| 111 |
2/2✓ Branch 0 taken 2864 times.
✓ Branch 1 taken 1440 times.
|
4304 | for (std::size_t req = 0; req < n; ++req) { |
| 112 | double *crow = &ceq[Idx(req, 0, n)]; | ||
| 113 |
2/2✓ Branch 0 taken 5712 times.
✓ Branch 1 taken 2864 times.
|
8576 | for (std::size_t k = 0; k < n; ++k) { |
| 114 | const double aik = At(a, req, k); | ||
| 115 |
2/2✓ Branch 0 taken 11408 times.
✓ Branch 1 taken 5712 times.
|
17120 | for (std::size_t col = 0; col < n; ++col) { |
| 116 | 11408 | crow[col] += aik * At(b, k, col); | |
| 117 | } | ||
| 118 | } | ||
| 119 | } | ||
| 120 | 1440 | return ceq; | |
| 121 | } | ||
| 122 | |||
| 123 | void PlaceBlockFlat(const Flat &blk, std::size_t blk_n, Flat *dst, std::size_t dst_n, std::size_t row0, | ||
| 124 | std::size_t col0) { | ||
| 125 |
8/8✓ Branch 0 taken 496 times.
✓ Branch 1 taken 224 times.
✓ Branch 2 taken 496 times.
✓ Branch 3 taken 224 times.
✓ Branch 4 taken 496 times.
✓ Branch 5 taken 224 times.
✓ Branch 6 taken 496 times.
✓ Branch 7 taken 224 times.
|
2880 | for (std::size_t req = 0; req < blk_n; ++req) { |
| 126 |
8/8✓ Branch 0 taken 1184 times.
✓ Branch 1 taken 496 times.
✓ Branch 2 taken 1184 times.
✓ Branch 3 taken 496 times.
✓ Branch 4 taken 1184 times.
✓ Branch 5 taken 496 times.
✓ Branch 6 taken 1184 times.
✓ Branch 7 taken 496 times.
|
6720 | for (std::size_t ceq = 0; ceq < blk_n; ++ceq) { |
| 127 | 4736 | (*dst)[Idx(row0 + req, col0 + ceq, dst_n)] = blk[Idx(req, ceq, blk_n)]; | |
| 128 | } | ||
| 129 | } | ||
| 130 | } | ||
| 131 | |||
| 132 | struct Frame { | ||
| 133 | OwnedView a_owned; | ||
| 134 | OwnedView b_owned; | ||
| 135 | View a; | ||
| 136 | View b; | ||
| 137 | std::size_t n = 0; | ||
| 138 | bool has_parent = false; | ||
| 139 | std::size_t parent_idx = 0; | ||
| 140 | int parent_slot = 0; | ||
| 141 | int stage = 0; | ||
| 142 | Flat res; | ||
| 143 | bool split_ready = false; | ||
| 144 | View a11, a12, a21, a22; | ||
| 145 | View b11, b12, b21, b22; | ||
| 146 | |||
| 147 | Flat m1, m2, m3, m4, m5, m6, m7; | ||
| 148 | }; | ||
| 149 | |||
| 150 | bool IsLeaf(const Frame &f) { | ||
| 151 | 3232 | return f.n <= kClassicThreshold; | |
| 152 | } | ||
| 153 | |||
| 154 | 1792 | void EnsureSplit(Frame *f) { | |
| 155 |
2/2✓ Branch 0 taken 224 times.
✓ Branch 1 taken 1568 times.
|
1792 | if (f->split_ready) { |
| 156 | return; | ||
| 157 | } | ||
| 158 | 224 | const std::size_t half = f->n / 2; | |
| 159 | 224 | f->a11 = SubView(f->a, 0, 0, half); | |
| 160 | 224 | f->a12 = SubView(f->a, 0, half, half); | |
| 161 | 224 | f->a21 = SubView(f->a, half, 0, half); | |
| 162 | 224 | f->a22 = SubView(f->a, half, half, half); | |
| 163 | |||
| 164 | 224 | f->b11 = SubView(f->b, 0, 0, half); | |
| 165 | 224 | f->b12 = SubView(f->b, 0, half, half); | |
| 166 | 224 | f->b21 = SubView(f->b, half, 0, half); | |
| 167 | 224 | f->b22 = SubView(f->b, half, half, half); | |
| 168 | |||
| 169 | 224 | f->split_ready = true; | |
| 170 | 224 | f->stage = 1; | |
| 171 | } | ||
| 172 | |||
| 173 | 1568 | void AssignToParent(std::vector<Frame> *stack, const Frame &child) { | |
| 174 |
1/2✓ Branch 0 taken 1568 times.
✗ Branch 1 not taken.
|
1568 | if (!child.has_parent) { |
| 175 | return; | ||
| 176 | } | ||
| 177 | |||
| 178 |
7/7✓ Branch 0 taken 224 times.
✓ Branch 1 taken 224 times.
✓ Branch 2 taken 224 times.
✓ Branch 3 taken 224 times.
✓ Branch 4 taken 224 times.
✓ Branch 5 taken 224 times.
✓ Branch 6 taken 224 times.
|
1568 | Frame &parent = (*stack)[child.parent_idx]; |
| 179 |
7/7✓ Branch 0 taken 224 times.
✓ Branch 1 taken 224 times.
✓ Branch 2 taken 224 times.
✓ Branch 3 taken 224 times.
✓ Branch 4 taken 224 times.
✓ Branch 5 taken 224 times.
✓ Branch 6 taken 224 times.
|
1568 | const int slot = child.parent_slot; |
| 180 | |||
| 181 | if (slot == 1) { | ||
| 182 | 224 | parent.m1 = child.res; | |
| 183 | } else if (slot == 2) { | ||
| 184 | 224 | parent.m2 = child.res; | |
| 185 | } else if (slot == 3) { | ||
| 186 | 224 | parent.m3 = child.res; | |
| 187 | } else if (slot == 4) { | ||
| 188 | 224 | parent.m4 = child.res; | |
| 189 | } else if (slot == 5) { | ||
| 190 | 224 | parent.m5 = child.res; | |
| 191 | } else if (slot == 6) { | ||
| 192 | 224 | parent.m6 = child.res; | |
| 193 | } else { | ||
| 194 | 224 | parent.m7 = child.res; | |
| 195 | } | ||
| 196 | } | ||
| 197 | |||
| 198 | 1568 | Frame MakeChild(const Frame &parent, std::size_t parent_idx, int slot) { | |
| 199 | 1568 | const std::size_t half = parent.n / 2; | |
| 200 | |||
| 201 | 1568 | Frame child; | |
| 202 | 1568 | child.has_parent = true; | |
| 203 | 1568 | child.parent_idx = parent_idx; | |
| 204 | 1568 | child.parent_slot = slot; | |
| 205 | child.stage = 0; | ||
| 206 | child.split_ready = false; | ||
| 207 |
7/7✓ Branch 0 taken 224 times.
✓ Branch 1 taken 224 times.
✓ Branch 2 taken 224 times.
✓ Branch 3 taken 224 times.
✓ Branch 4 taken 224 times.
✓ Branch 5 taken 224 times.
✓ Branch 6 taken 224 times.
|
1568 | child.n = half; |
| 208 | child.a_owned.buf.clear(); | ||
| 209 | child.b_owned.buf.clear(); | ||
| 210 | auto set_from_buf = [&](Flat *buf, OwnedView *ov) { | ||
| 211 | 1568 | ov->buf = std::move(*buf); | |
| 212 | 2240 | ov->view.data = ov->buf.data(); | |
| 213 | 2240 | ov->view.ld = half; | |
| 214 | 2240 | ov->view.row0 = 0; | |
| 215 | 2240 | ov->view.col0 = 0; | |
| 216 | 672 | ov->view.n = half; | |
| 217 | }; | ||
| 218 | |||
| 219 | if (slot == 1) { | ||
| 220 | 224 | Flat tmp_a; | |
| 221 | 224 | Flat tmp_b; | |
| 222 |
1/2✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
|
224 | FillAdd(parent.a11, parent.a22, &tmp_a); |
| 223 |
1/2✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
|
224 | FillAdd(parent.b11, parent.b22, &tmp_b); |
| 224 | set_from_buf(&tmp_a, &child.a_owned); | ||
| 225 | set_from_buf(&tmp_b, &child.b_owned); | ||
| 226 | 224 | child.a = child.a_owned.view; | |
| 227 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 224 times.
|
224 | child.b = child.b_owned.view; |
| 228 | return child; | ||
| 229 | } | ||
| 230 | |||
| 231 | if (slot == 2) { | ||
| 232 | 224 | Flat tmp_a; | |
| 233 |
1/2✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
|
224 | FillAdd(parent.a21, parent.a22, &tmp_a); |
| 234 | set_from_buf(&tmp_a, &child.a_owned); | ||
| 235 | 224 | child.a = child.a_owned.view; | |
| 236 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 224 times.
|
224 | child.b = parent.b11; |
| 237 | return child; | ||
| 238 | } | ||
| 239 | |||
| 240 | if (slot == 3) { | ||
| 241 | 224 | Flat tmp_b; | |
| 242 |
1/2✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
|
224 | FillSub(parent.b12, parent.b22, &tmp_b); |
| 243 | set_from_buf(&tmp_b, &child.b_owned); | ||
| 244 | 224 | child.a = parent.a11; | |
| 245 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 224 times.
|
224 | child.b = child.b_owned.view; |
| 246 | return child; | ||
| 247 | } | ||
| 248 | |||
| 249 | if (slot == 4) { | ||
| 250 | 224 | Flat tmp_b; | |
| 251 |
1/2✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
|
224 | FillSub(parent.b21, parent.b11, &tmp_b); |
| 252 | set_from_buf(&tmp_b, &child.b_owned); | ||
| 253 | 224 | child.a = parent.a22; | |
| 254 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 224 times.
|
224 | child.b = child.b_owned.view; |
| 255 | return child; | ||
| 256 | } | ||
| 257 | if (slot == 5) { | ||
| 258 | 224 | Flat tmp_a; | |
| 259 |
1/2✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
|
224 | FillAdd(parent.a11, parent.a12, &tmp_a); |
| 260 | set_from_buf(&tmp_a, &child.a_owned); | ||
| 261 | 224 | child.a = child.a_owned.view; | |
| 262 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 224 times.
|
224 | child.b = parent.b22; |
| 263 | return child; | ||
| 264 | } | ||
| 265 | if (slot == 6) { | ||
| 266 | 224 | Flat tmp_a; | |
| 267 | 224 | Flat tmp_b; | |
| 268 |
1/2✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
|
224 | FillSub(parent.a21, parent.a11, &tmp_a); |
| 269 |
1/2✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
|
224 | FillAdd(parent.b11, parent.b12, &tmp_b); |
| 270 | set_from_buf(&tmp_a, &child.a_owned); | ||
| 271 | set_from_buf(&tmp_b, &child.b_owned); | ||
| 272 | 224 | child.a = child.a_owned.view; | |
| 273 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 224 times.
|
224 | child.b = child.b_owned.view; |
| 274 | return child; | ||
| 275 | } | ||
| 276 | { | ||
| 277 | 224 | Flat tmp_a; | |
| 278 | 224 | Flat tmp_b; | |
| 279 |
1/2✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
|
224 | FillSub(parent.a12, parent.a22, &tmp_a); |
| 280 |
1/2✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
|
224 | FillAdd(parent.b21, parent.b22, &tmp_b); |
| 281 | set_from_buf(&tmp_a, &child.a_owned); | ||
| 282 | set_from_buf(&tmp_b, &child.b_owned); | ||
| 283 | 224 | child.a = child.a_owned.view; | |
| 284 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 224 times.
|
224 | child.b = child.b_owned.view; |
| 285 | return child; | ||
| 286 | } | ||
| 287 | ✗ | } | |
| 288 | |||
| 289 | 224 | void Combine(Frame *f) { | |
| 290 | 224 | const std::size_t half = f->n / 2; | |
| 291 | 224 | const std::size_t kk = half * half; | |
| 292 | |||
| 293 | 224 | Flat c11(kk, 0.0); | |
| 294 |
1/4✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
|
224 | Flat c12(kk, 0.0); |
| 295 |
1/4✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
|
224 | Flat c21(kk, 0.0); |
| 296 |
1/4✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
|
224 | Flat c22(kk, 0.0); |
| 297 | |||
| 298 |
2/2✓ Branch 0 taken 1184 times.
✓ Branch 1 taken 224 times.
|
1408 | for (std::size_t i = 0; i < kk; ++i) { |
| 299 | 1184 | c11[i] = f->m1[i] + f->m4[i] - f->m5[i] + f->m7[i]; | |
| 300 | } | ||
| 301 |
2/2✓ Branch 0 taken 1184 times.
✓ Branch 1 taken 224 times.
|
1408 | for (std::size_t i = 0; i < kk; ++i) { |
| 302 | 1184 | c12[i] = f->m3[i] + f->m5[i]; | |
| 303 | } | ||
| 304 |
2/2✓ Branch 0 taken 1184 times.
✓ Branch 1 taken 224 times.
|
1408 | for (std::size_t i = 0; i < kk; ++i) { |
| 305 | 1184 | c21[i] = f->m2[i] + f->m4[i]; | |
| 306 | } | ||
| 307 |
2/2✓ Branch 0 taken 1184 times.
✓ Branch 1 taken 224 times.
|
1408 | for (std::size_t i = 0; i < kk; ++i) { |
| 308 | 1184 | c22[i] = f->m1[i] - f->m2[i] + f->m3[i] + f->m6[i]; | |
| 309 | } | ||
| 310 | |||
| 311 |
1/4✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
|
224 | f->res.assign(f->n * f->n, 0.0); |
| 312 | 224 | PlaceBlockFlat(c11, half, &f->res, f->n, 0, 0); | |
| 313 | PlaceBlockFlat(c12, half, &f->res, f->n, 0, half); | ||
| 314 | PlaceBlockFlat(c21, half, &f->res, f->n, half, 0); | ||
| 315 | PlaceBlockFlat(c22, half, &f->res, f->n, half, half); | ||
| 316 | 224 | } | |
| 317 | |||
| 318 | 96 | Flat Shtrassen(const View &a0, const View &b0) { | |
| 319 | 96 | std::vector<Frame> stack; | |
| 320 |
1/2✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
|
96 | stack.reserve(64); |
| 321 | |||
| 322 | 96 | Frame root; | |
| 323 | 96 | root.a = a0; | |
| 324 | 96 | root.b = b0; | |
| 325 |
1/2✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
|
96 | root.n = a0.n; |
| 326 | root.has_parent = false; | ||
| 327 | root.stage = 0; | ||
| 328 | root.split_ready = false; | ||
| 329 | stack.push_back(std::move(root)); | ||
| 330 | |||
| 331 |
1/2✓ Branch 0 taken 3232 times.
✗ Branch 1 not taken.
|
3232 | while (!stack.empty()) { |
| 332 | Frame &cur = stack.back(); | ||
| 333 | |||
| 334 |
2/2✓ Branch 0 taken 1440 times.
✓ Branch 1 taken 1792 times.
|
3232 | if (IsLeaf(cur)) { |
| 335 |
1/2✓ Branch 1 taken 1440 times.
✗ Branch 2 not taken.
|
1440 | cur.res = MultiplyClassicView(cur.a, cur.b); |
| 336 |
1/2✓ Branch 1 taken 1440 times.
✗ Branch 2 not taken.
|
1440 | const Frame finished = cur; |
| 337 | stack.pop_back(); | ||
| 338 | |||
| 339 |
2/2✓ Branch 0 taken 40 times.
✓ Branch 1 taken 1400 times.
|
1440 | if (stack.empty()) { |
| 340 |
1/2✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
|
40 | return finished.res; |
| 341 | } | ||
| 342 | |||
| 343 |
1/2✓ Branch 1 taken 1400 times.
✗ Branch 2 not taken.
|
1400 | AssignToParent(&stack, finished); |
| 344 | continue; | ||
| 345 | 1440 | } | |
| 346 | |||
| 347 | 1792 | EnsureSplit(&cur); | |
| 348 | |||
| 349 |
2/2✓ Branch 0 taken 1568 times.
✓ Branch 1 taken 224 times.
|
1792 | if (cur.stage >= 1 && cur.stage <= 7) { |
| 350 | const int slot = cur.stage; | ||
| 351 | 1568 | const std::size_t parent_idx = stack.size() - 1; | |
| 352 | |||
| 353 |
1/2✓ Branch 1 taken 1568 times.
✗ Branch 2 not taken.
|
1568 | Frame child = MakeChild(cur, parent_idx, slot); |
| 354 |
1/2✓ Branch 1 taken 1568 times.
✗ Branch 2 not taken.
|
1568 | cur.stage += 1; |
| 355 | stack.push_back(std::move(child)); | ||
| 356 | continue; | ||
| 357 | 1568 | } | |
| 358 | |||
| 359 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 224 times.
|
224 | if (cur.stage != 8) { |
| 360 | ✗ | cur.stage = 8; | |
| 361 | ✗ | continue; | |
| 362 | } | ||
| 363 | |||
| 364 |
1/2✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
|
224 | Combine(&cur); |
| 365 | |||
| 366 |
1/2✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
|
224 | const Frame finished = cur; |
| 367 | stack.pop_back(); | ||
| 368 | |||
| 369 |
2/2✓ Branch 0 taken 56 times.
✓ Branch 1 taken 168 times.
|
224 | if (stack.empty()) { |
| 370 |
1/2✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
|
56 | return finished.res; |
| 371 | } | ||
| 372 | |||
| 373 |
1/2✓ Branch 1 taken 168 times.
✗ Branch 2 not taken.
|
168 | AssignToParent(&stack, finished); |
| 374 | 224 | } | |
| 375 | |||
| 376 | ✗ | return Flat{}; | |
| 377 | 96 | } | |
| 378 | |||
| 379 | } // namespace | ||
| 380 | |||
| 381 |
1/2✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
|
96 | SannikovIShtrassenAlgorithmSEQ::SannikovIShtrassenAlgorithmSEQ(const InType &in) { |
| 382 | SetTypeOfTask(GetStaticTypeOfTask()); | ||
| 383 | auto &input_buffer = GetInput(); | ||
| 384 | InType tmp(in); | ||
| 385 | input_buffer.swap(tmp); | ||
| 386 | GetOutput().clear(); | ||
| 387 | 96 | } | |
| 388 | |||
| 389 |
1/2✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
|
96 | bool SannikovIShtrassenAlgorithmSEQ::ValidationImpl() { |
| 390 | (void)this; | ||
| 391 | const auto &input = GetInput(); | ||
| 392 | const auto &mat_a = std::get<0>(input); | ||
| 393 | const auto &mat_b = std::get<1>(input); | ||
| 394 | |||
| 395 |
2/4✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 96 times.
|
96 | if (mat_a.empty() || mat_b.empty()) { |
| 396 | return false; | ||
| 397 | } | ||
| 398 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
|
96 | if (mat_a.size() != mat_b.size()) { |
| 399 | return false; | ||
| 400 | } | ||
| 401 |
2/4✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 96 times.
|
96 | if (mat_a.front().empty() || mat_b.front().empty()) { |
| 402 | return false; | ||
| 403 | } | ||
| 404 | |||
| 405 | const auto n = mat_a.size(); | ||
| 406 |
2/2✓ Branch 0 taken 328 times.
✓ Branch 1 taken 96 times.
|
424 | for (const auto &row : mat_a) { |
| 407 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 328 times.
|
328 | if (row.size() != n) { |
| 408 | return false; | ||
| 409 | } | ||
| 410 | } | ||
| 411 |
2/2✓ Branch 0 taken 328 times.
✓ Branch 1 taken 96 times.
|
424 | for (const auto &row : mat_b) { |
| 412 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 328 times.
|
328 | if (row.size() != n) { |
| 413 | return false; | ||
| 414 | } | ||
| 415 | } | ||
| 416 | |||
| 417 | 96 | return GetOutput().empty(); | |
| 418 | } | ||
| 419 | |||
| 420 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
|
96 | bool SannikovIShtrassenAlgorithmSEQ::PreProcessingImpl() { |
| 421 | (void)this; | ||
| 422 | GetOutput().clear(); | ||
| 423 | 96 | return true; | |
| 424 | } | ||
| 425 | |||
| 426 | 96 | bool SannikovIShtrassenAlgorithmSEQ::RunImpl() { | |
| 427 | (void)this; | ||
| 428 | const auto &input = GetInput(); | ||
| 429 | const auto &a_in = std::get<0>(input); | ||
| 430 | const auto &b_in = std::get<1>(input); | ||
| 431 | |||
| 432 | const std::size_t n0 = a_in.size(); | ||
| 433 | const std::size_t m = NextPow2(n0); | ||
| 434 | 96 | Flat a_flat; | |
| 435 | 96 | Flat b_flat; | |
| 436 |
1/2✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
|
96 | PackPadToFlat(a_in, n0, m, &a_flat); |
| 437 |
1/2✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
|
96 | PackPadToFlat(b_in, n0, m, &b_flat); |
| 438 | const View a0 = MakeView(a_flat, m); | ||
| 439 | const View b0 = MakeView(b_flat, m); | ||
| 440 |
1/2✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
|
96 | const Flat c_flat = Shtrassen(a0, b0); |
| 441 |
2/6✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 96 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
96 | GetOutput() = UnpackCropFromFlat(c_flat, m, n0); |
| 442 | |||
| 443 |
1/2✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
|
192 | return !GetOutput().empty(); |
| 444 | } | ||
| 445 | |||
| 446 | 96 | bool SannikovIShtrassenAlgorithmSEQ::PostProcessingImpl() { | |
| 447 | (void)this; | ||
| 448 | 96 | return !GetOutput().empty(); | |
| 449 | } | ||
| 450 | |||
| 451 | } // namespace sannikov_i_shtrassen_algorithm | ||
| 452 |