| Line | Branch | Decision | Exec | Source |
|---|---|---|---|---|
| 1 | // Copyright 2019-2022 Cambridge Quantum Computing | |||
| 2 | // | |||
| 3 | // Licensed under the Apache License, Version 2.0 (the "License"); | |||
| 4 | // you may not use this file except in compliance with the License. | |||
| 5 | // You may obtain a copy of the License at | |||
| 6 | // | |||
| 7 | // http://www.apache.org/licenses/LICENSE-2.0 | |||
| 8 | // | |||
| 9 | // Unless required by applicable law or agreed to in writing, software | |||
| 10 | // distributed under the License is distributed on an "AS IS" BASIS, | |||
| 11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |||
| 12 | // See the License for the specific language governing permissions and | |||
| 13 | // limitations under the License. | |||
| 14 | ||||
| 15 | #include "BitOperations.hpp" | |||
| 16 | ||||
| 17 | #include <stdexcept> | |||
| 18 | #include <tkassert/Assert.hpp> | |||
| 19 | ||||
| 20 | namespace tket { | |||
| 21 | namespace tket_sim { | |||
| 22 | namespace internal { | |||
| 23 | ||||
| 24 | // We want to push back to ExpansionData, but check if it can be combined | |||
| 25 | // into an existing element. | |||
| 26 | 1031267 | static void push_back( | ||
| 27 | ExpansionData& result, SimUInt single_bit, unsigned left_shift_argument) { | |||
| 28 |
6/6✓ Branch 1 taken 840231 times.
✓ Branch 2 taken 191036 times.
✓ Branch 4 taken 732493 times.
✓ Branch 5 taken 107738 times.
✓ Branch 6 taken 732493 times.
✓ Branch 7 taken 298774 times.
|
2/2✓ Decision 'true' taken 732493 times.
✓ Decision 'false' taken 298774 times.
|
1031267 | if (!result.empty() && left_shift_argument == result.back().second) { |
| 29 | // Since the left shift arguments agree, | |||
| 30 | // they can be combined into a single operation, | |||
| 31 | // which is more efficient. | |||
| 32 | 732493 | result.back().first |= single_bit; | ||
| 33 | 732493 | return; | ||
| 34 | } | |||
| 35 | 298774 | result.emplace_back(single_bit, left_shift_argument); | ||
| 36 | } | |||
| 37 | ||||
| 38 | 191037 | ExpansionData get_expansion_data( | ||
| 39 | SimUInt forbidden_bits, unsigned number_of_free_bits) { | |||
| 40 | 191037 | ExpansionData result; | ||
| 41 | 191037 | SimUInt next_bit = 1; | ||
| 42 | ||||
| 43 |
2/2✓ Branch 0 taken 1031267 times.
✓ Branch 1 taken 191037 times.
|
2/2✓ Decision 'true' taken 1031267 times.
✓ Decision 'false' taken 191037 times.
|
1222304 | for (unsigned bits_count = 0; bits_count < number_of_free_bits; |
| 44 | ++bits_count) { | |||
| 45 | 1031267 | auto test_bit = next_bit; | ||
| 46 | 1031267 | for (unsigned left_shift_arg = 0;; ++left_shift_arg) { | ||
| 47 |
2/2✓ Branch 0 taken 1031267 times.
✓ Branch 1 taken 1225975 times.
|
2/2✓ Decision 'true' taken 1031267 times.
✓ Decision 'false' taken 1225975 times.
|
2257242 | if ((test_bit & forbidden_bits) == 0) { |
| 48 | TKET_ASSERT(test_bit != 0); | |||
| 49 | // A free space has been found. | |||
| 50 |
1/2✓ Branch 1 taken 1031267 times.
✗ Branch 2 not taken.
|
1031267 | push_back(result, next_bit, left_shift_arg); | |
| 51 | 1031267 | forbidden_bits |= test_bit; | ||
| 52 | 1031267 | break; | ||
| 53 | } | |||
| 54 | 1225975 | test_bit <<= 1; | ||
| 55 | 1225975 | } | ||
| 56 | 1031267 | next_bit <<= 1; | ||
| 57 | } | |||
| 58 | 191037 | return result; | ||
| 59 | } | |||
| 60 | ||||
| 61 | 8255694 | SimUInt get_expanded_bits(const ExpansionData& expansion_data, SimUInt bits) { | ||
| 62 | 8255694 | SimUInt result = 0; | ||
| 63 |
2/2✓ Branch 4 taken 15015775 times.
✓ Branch 5 taken 8255694 times.
|
2/2✓ Decision 'true' taken 15015775 times.
✓ Decision 'false' taken 8255694 times.
|
23271469 | for (const auto& entry : expansion_data) { |
| 64 | 15015775 | SimUInt block = bits & entry.first; | ||
| 65 | 15015775 | block <<= entry.second; | ||
| 66 | 15015775 | result |= block; | ||
| 67 | } | |||
| 68 | 8255694 | return result; | ||
| 69 | } | |||
| 70 | ||||
| 71 | } // namespace internal | |||
| 72 | } // namespace tket_sim | |||
| 73 | } // namespace tket | |||
| 74 |