#include "pymatching-cxx/include/pymatching_rs_bridge.h"
#include "pymatching/rand/rand_gen.h"
#include "pymatching/sparse_blossom/driver/mwpm_decoding.h"
#include "pymatching/sparse_blossom/driver/user_graph.h"
#include <algorithm>
#include <atomic>
#include <chrono>
#include <climits>
#include <cmath>
#include <limits>
#include <mutex>
#include <optional>
#include <set>
#include <span>
#include <stdexcept>
#include <string>
#include <thread>
#include <utility>
#include <vector>
namespace pymatching_rs {
namespace {
auto to_pm_merge_strategy(::MergeStrategy merge_strategy) -> pm::MERGE_STRATEGY {
switch (merge_strategy) {
case ::MergeStrategy::Disallow:
return pm::MERGE_STRATEGY::DISALLOW;
case ::MergeStrategy::Independent:
return pm::MERGE_STRATEGY::INDEPENDENT;
case ::MergeStrategy::SmallestWeight:
return pm::MERGE_STRATEGY::SMALLEST_WEIGHT;
case ::MergeStrategy::KeepOriginal:
return pm::MERGE_STRATEGY::KEEP_ORIGINAL;
case ::MergeStrategy::Replace:
return pm::MERGE_STRATEGY::REPLACE;
}
throw std::invalid_argument("unsupported merge strategy");
}
void collect_detection_events(
pm::UserGraph& graph,
rust::Slice<const std::uint8_t> syndrome,
std::vector<std::uint64_t>& detection_events) {
const auto num_detectors = graph.get_num_detectors();
if (syndrome.size() != num_detectors) {
throw std::invalid_argument(
"syndrome length (" + std::to_string(syndrome.size()) +
") must match the number of detectors (" + std::to_string(num_detectors) + ")");
}
detection_events.clear();
for (std::size_t detector = 0; detector < syndrome.size(); detector++) {
auto value = syndrome[detector];
if (value > 1) {
throw std::invalid_argument("syndrome values must be binary");
}
if (value == 1) {
detection_events.push_back(static_cast<std::uint64_t>(detector));
}
}
}
auto collect_detection_events(pm::UserGraph& graph, rust::Slice<const std::uint8_t> syndrome)
-> std::vector<std::uint64_t> {
std::vector<std::uint64_t> detection_events;
collect_detection_events(graph, syndrome, detection_events);
return detection_events;
}
template <typename T>
auto to_rust_vec(const std::vector<T>& values) -> rust::Vec<T> {
rust::Vec<T> result;
result.reserve(values.size());
for (const auto& value : values) result.push_back(value);
return result;
}
struct GapState {
pm::UserGraph graph;
std::vector<std::uint8_t> detector_mask;
std::vector<std::uint8_t> detector_potential;
std::size_t virtual_zero = 0;
std::size_t virtual_one = 0;
};
struct GapNativeResult {
std::vector<std::uint8_t> prediction;
std::vector<double> gaps;
};
struct GapScratch {
std::vector<std::uint64_t> events;
std::vector<std::uint64_t> branch_events;
std::vector<std::uint8_t> alternate_prediction;
};
auto component_observable_parity(
std::span<const stim::DemTarget> component,
std::size_t observable) -> std::uint8_t {
std::uint8_t parity = 0;
for (const auto& target : component) {
if (target.is_observable_id() && target.raw_id() == observable) parity ^= 1;
}
return parity;
}
struct BoundaryComponent {
std::size_t detector;
std::uint8_t observable_parity;
};
auto make_gap_state(
const stim::DetectorErrorModel& flat,
std::size_t observable,
bool enable_correlations)
-> std::unique_ptr<GapState> {
const std::size_t num_detectors = flat.count_detectors();
std::vector<std::vector<std::pair<std::size_t, std::uint8_t>>> adjacency(num_detectors);
std::vector<BoundaryComponent> boundary_components;
for (const auto& instruction : flat.instructions) {
if (instruction.type != stim::DemInstructionType::DEM_ERROR || instruction.arg_data[0] <= 0) {
continue;
}
instruction.for_separated_targets([&](std::span<const stim::DemTarget> component) {
std::vector<std::size_t> detectors;
for (const auto& target : component) {
if (target.is_relative_detector_id()) detectors.push_back(target.raw_id());
}
const auto parity = component_observable_parity(component, observable);
if (detectors.size() == 2) {
adjacency[detectors[0]].push_back({detectors[1], parity});
adjacency[detectors[1]].push_back({detectors[0], parity});
} else if (detectors.size() == 1) {
boundary_components.push_back({detectors[0], parity});
} else if (detectors.empty() && parity != 0) {
throw std::invalid_argument(
"gap decoding cannot infer a cut for an undetectable logical error");
} else if (detectors.size() > 2) {
throw std::invalid_argument("gap decoding requires a graphlike detector error model");
}
});
}
std::vector<std::size_t> components(num_detectors, SIZE_MAX);
std::vector<std::uint8_t> potentials(num_detectors, 0);
std::size_t num_components = 0;
for (std::size_t root = 0; root < num_detectors; root++) {
if (components[root] != SIZE_MAX) continue;
components[root] = num_components;
std::vector<std::size_t> stack{root};
while (!stack.empty()) {
const auto detector = stack.back();
stack.pop_back();
for (const auto& [neighbor, edge_parity] : adjacency[detector]) {
const auto expected = potentials[detector] ^ edge_parity;
if (components[neighbor] == SIZE_MAX) {
components[neighbor] = num_components;
potentials[neighbor] = expected;
stack.push_back(neighbor);
} else if (potentials[neighbor] != expected) {
throw std::invalid_argument(
"gap decoding requires each logical observable to define a graph cut");
}
}
}
num_components++;
}
std::vector<std::uint8_t> boundary_sides(num_components, 0);
for (const auto& boundary : boundary_components) {
const auto side = potentials[boundary.detector] ^ boundary.observable_parity;
boundary_sides[components[boundary.detector]] |= static_cast<std::uint8_t>(1 << side);
}
std::size_t relevant_component = SIZE_MAX;
for (std::size_t component = 0; component < num_components; component++) {
if (boundary_sides[component] != 3) continue;
if (relevant_component != SIZE_MAX) {
throw std::invalid_argument(
"gap decoding does not support one observable spanning disconnected graph components");
}
relevant_component = component;
}
if (relevant_component == SIZE_MAX) {
throw std::invalid_argument(
"gap decoding could not infer two boundaries for logical observable " +
std::to_string(observable));
}
const std::size_t virtual_zero = num_detectors;
const std::size_t virtual_one = num_detectors + 1;
stim::DetectorErrorModel gap_dem;
std::size_t boundary_edges[2] = {0, 0};
for (const auto& instruction : flat.instructions) {
if (instruction.type != stim::DemInstructionType::DEM_ERROR) {
gap_dem.append_dem_instruction(instruction);
continue;
}
std::vector<stim::DemTarget> targets;
bool first_component = true;
instruction.for_separated_targets([&](std::span<const stim::DemTarget> component) {
if (!first_component) targets.push_back(stim::DemTarget::separator());
first_component = false;
std::size_t detector_count = 0;
std::size_t detector = 0;
for (const auto& target : component) {
if (target.is_relative_detector_id()) {
detector_count++;
detector = target.raw_id();
}
targets.push_back(target);
}
if (detector_count == 1 && components[detector] == relevant_component) {
const auto side = potentials[detector] ^ component_observable_parity(component, observable);
targets.push_back(stim::DemTarget::relative_detector_id(
side == 0 ? virtual_zero : virtual_one));
if (instruction.arg_data[0] > 0) boundary_edges[side]++;
}
});
gap_dem.append_error_instruction(instruction.arg_data[0], targets, instruction.tag);
}
if (boundary_edges[0] == 0 || boundary_edges[1] == 0) {
throw std::logic_error("gap boundary inference produced an empty boundary");
}
auto state = std::make_unique<GapState>();
state->graph = pm::detector_error_model_to_user_graph(
gap_dem, enable_correlations, pm::NUM_DISTINCT_WEIGHTS);
state->detector_mask.assign(num_detectors, 0);
state->detector_potential.assign(num_detectors, 0);
for (std::size_t detector = 0; detector < num_detectors; detector++) {
if (components[detector] != relevant_component) continue;
state->detector_mask[detector] = 1;
state->detector_potential[detector] = potentials[detector];
}
state->virtual_zero = virtual_zero;
state->virtual_one = virtual_one;
return state;
}
void gap_branch_events(
const GapState& state,
const std::vector<std::uint64_t>& events,
std::uint8_t logical_class,
std::vector<std::uint64_t>& branch_events) {
branch_events.assign(events.begin(), events.end());
std::uint8_t event_count_parity = 0;
std::uint8_t event_potential_parity = 0;
for (auto detector : events) {
if (state.detector_mask[detector] == 0) continue;
event_count_parity ^= 1;
event_potential_parity ^= state.detector_potential[detector];
}
const auto boundary_side_parity = logical_class ^ event_potential_parity;
if (event_count_parity != 0) {
branch_events.push_back(
boundary_side_parity == 0 ? state.virtual_zero : state.virtual_one);
} else if (boundary_side_parity != 0) {
branch_events.push_back(state.virtual_zero);
branch_events.push_back(state.virtual_one);
}
}
auto decode_gap_branch(
pm::UserGraph& graph,
const std::vector<std::uint64_t>& events,
bool enable_correlations,
std::vector<std::uint8_t>& prediction) -> double {
auto& mwpm = enable_correlations ? graph.get_mwpm_with_search_graph() : graph.get_mwpm();
prediction.assign(graph.get_num_observables(), 0);
pm::total_weight_int weight = 0;
pm::decode_detection_events(
mwpm, events, prediction.data(), weight, enable_correlations);
return static_cast<double>(weight) / mwpm.flooder.graph.normalising_constant;
}
void validate_batch_shape(pm::UserGraph& graph, std::size_t num_rows, std::size_t num_cols, bool bit_packed_shots) {
const auto expected_size = num_rows * num_cols;
if (num_rows != 0 && expected_size / num_rows != num_cols) {
throw std::invalid_argument("batch dimensions overflow");
}
const auto min_cols = bit_packed_shots ? ((graph.get_num_detectors() + 7) >> 3) : graph.get_num_detectors();
const auto max_cols = bit_packed_shots ? ((graph.get_num_nodes() + 7) >> 3) : graph.get_num_nodes();
const auto column_description = bit_packed_shots
? " columns (ceil(num_detectors/8)) and at most "
: " columns (the number of detectors), and no more than ";
if (num_cols < min_cols || num_cols > max_cols) {
if (bit_packed_shots) {
throw std::invalid_argument(
"bit_packed `shots` array should have at least " + std::to_string(min_cols) +
column_description + std::to_string(max_cols) +
" columns, (ceil(num_nodes/8)). Instead it has " + std::to_string(num_cols) + " columns.");
}
throw std::invalid_argument(
"`shots` array should have at least " + std::to_string(min_cols) +
column_description + std::to_string(max_cols) + " columns (the number of nodes), but instead has " +
std::to_string(num_cols) + " columns");
}
if (expected_size != 0 && expected_size != num_rows * num_cols) {
throw std::invalid_argument("batch dimensions overflow");
}
}
auto decode_detection_events(
pm::UserGraph& graph,
const std::vector<std::uint64_t>& detection_events,
const ::DecodeConfig& config) -> ::DecodeResult {
auto& mwpm = config.enable_correlations ? graph.get_mwpm_with_search_graph() : graph.get_mwpm();
std::vector<std::uint8_t> prediction(graph.get_num_observables(), 0);
pm::total_weight_int weight = 0;
pm::decode_detection_events(
mwpm,
detection_events,
prediction.data(),
weight,
config.enable_correlations);
rust::Vec<std::uint8_t> result_prediction;
for (auto bit : prediction) {
result_prediction.push_back(bit);
}
::DecodeResult result;
result.prediction = std::move(result_prediction);
result.weight = static_cast<double>(weight) / mwpm.flooder.graph.normalising_constant;
result.has_weight = config.return_weight;
return result;
}
auto& noise_rng_mutex() {
static std::mutex mutex;
return mutex;
}
auto& noise_rng_lock_held_for_tests() {
static std::atomic<bool> held = false;
return held;
}
class NoiseRngLockScope {
public:
NoiseRngLockScope() : lock_(noise_rng_mutex()) {
noise_rng_lock_held_for_tests().store(true, std::memory_order_release);
}
~NoiseRngLockScope() {
noise_rng_lock_held_for_tests().store(false, std::memory_order_release);
}
private:
std::lock_guard<std::mutex> lock_;
};
auto make_noise_result(pm::UserGraph& graph) -> ::NoiseResult {
::NoiseResult result;
if (!graph.all_edges_have_error_probabilities()) {
result.has_noise = false;
return result;
}
std::vector<std::uint8_t> errors(graph.get_num_observables(), 0);
std::vector<std::uint8_t> syndrome(graph.get_num_nodes(), 0);
graph.add_noise(errors.data(), syndrome.data());
for (auto value : errors) {
result.errors.push_back(value);
}
for (auto value : syndrome) {
result.syndrome.push_back(value);
}
result.has_noise = true;
return result;
}
template <typename Body>
auto with_locked_noise_rng(const Body& body) -> decltype(body()) {
NoiseRngLockScope scope;
return body();
}
}
struct MatchingHandle::Impl {
auto decode_gap_native(rust::Slice<const std::uint8_t> syndrome) -> const GapNativeResult&;
void invalidate_gap_source() {
dem_text.clear();
gap_states.clear();
gap_states_initialized = false;
empty_gap_result.reset();
}
void ensure_min_num_observables(const rust::Vec<std::uint64_t>& fault_ids) {
std::size_t max_fault_id_plus_one = 0;
for (auto fault_id : fault_ids) {
max_fault_id_plus_one = std::max(max_fault_id_plus_one, static_cast<std::size_t>(fault_id + 1));
}
graph.set_min_num_observables(max_fault_id_plus_one);
}
static auto to_observables(const rust::Vec<std::uint64_t>& fault_ids) -> std::vector<std::size_t> {
std::vector<std::size_t> observables;
observables.reserve(fault_ids.size());
for (auto fault_id : fault_ids) {
observables.push_back(static_cast<std::size_t>(fault_id));
}
return observables;
}
static auto to_boundary_set(rust::Slice<const std::uint64_t> nodes) -> std::set<std::size_t> {
std::set<std::size_t> boundary;
for (auto node : nodes) {
boundary.insert(static_cast<std::size_t>(node));
}
return boundary;
}
static auto to_edge_record(const pm::UserEdge& edge) -> ::EdgeRecord {
rust::Vec<std::uint64_t> fault_ids;
for (auto fault_id : edge.observable_indices) {
fault_ids.push_back(static_cast<std::uint64_t>(fault_id));
}
double error_probability = edge.error_probability;
if (error_probability < 0 || error_probability > 1) {
error_probability = -1.0;
}
::EdgeRecord record;
record.node1 = static_cast<std::uint64_t>(edge.node1);
record.node2 = edge.node2 == SIZE_MAX ? 0 : static_cast<std::uint64_t>(edge.node2);
record.fault_ids = std::move(fault_ids);
record.weight = edge.weight;
record.error_probability = error_probability;
record.is_boundary = edge.node2 == SIZE_MAX;
return record;
}
static auto edge_data_record(const pm::UserGraph& graph, std::size_t node1, std::size_t node2) -> ::EdgeRecord {
if (node1 >= graph.nodes.size()) {
throw std::invalid_argument("node1 (" + std::to_string(node1) + ") not in graph");
}
std::size_t idx = graph.nodes[node1].index_of_neighbor(node2);
if (idx == SIZE_MAX) {
throw std::invalid_argument(
"Edge (" + std::to_string(node1) + ", " + std::to_string(node2) + ") not in graph.");
}
return to_edge_record(*graph.nodes[node1].neighbors[idx].edge_it);
}
static auto boundary_edge_data_record(const pm::UserGraph& graph, std::size_t node) -> ::EdgeRecord {
if (node >= graph.nodes.size()) {
throw std::invalid_argument("node (" + std::to_string(node) + ") not in graph");
}
std::size_t idx = graph.nodes[node].index_of_neighbor(SIZE_MAX);
if (idx == SIZE_MAX) {
throw std::invalid_argument("Boundary edge (" + std::to_string(node) + ",) not in graph.");
}
return to_edge_record(*graph.nodes[node].neighbors[idx].edge_it);
}
mutable pm::UserGraph graph;
std::string dem_text;
bool correlations_enabled = false;
mutable bool gap_states_initialized = false;
mutable std::vector<std::unique_ptr<GapState>> gap_states;
GapScratch gap_scratch;
GapNativeResult gap_result;
std::optional<GapNativeResult> empty_gap_result;
};
MatchingHandle::MatchingHandle() : impl_(std::make_unique<Impl>()) {}
MatchingHandle::~MatchingHandle() = default;
auto MatchingHandle::Impl::decode_gap_native(
rust::Slice<const std::uint8_t> syndrome) -> const GapNativeResult& {
if (dem_text.empty()) {
throw std::invalid_argument(
"gap decoding requires an unmodified detector error model");
}
if (!gap_states_initialized) {
const auto flat = stim::DetectorErrorModel(dem_text).flattened();
gap_states.reserve(graph.get_num_observables());
for (std::size_t observable = 0; observable < graph.get_num_observables(); observable++) {
gap_states.push_back(
make_gap_state(flat, observable, correlations_enabled));
}
gap_states_initialized = true;
}
collect_detection_events(graph, syndrome, gap_scratch.events);
if (gap_scratch.events.empty() && empty_gap_result.has_value()) {
return *empty_gap_result;
}
const auto hard_weight = decode_gap_branch(
graph,
gap_scratch.events,
correlations_enabled,
gap_result.prediction);
gap_result.gaps.clear();
gap_result.gaps.reserve(gap_states.size());
for (std::size_t observable = 0; observable < gap_states.size(); observable++) {
auto& gap_state = *gap_states[observable];
const auto alternate_class = gap_result.prediction[observable] ^ 1;
gap_branch_events(
gap_state,
gap_scratch.events,
alternate_class,
gap_scratch.branch_events);
const auto alternate_weight = decode_gap_branch(
gap_state.graph,
gap_scratch.branch_events,
correlations_enabled,
gap_scratch.alternate_prediction);
if (gap_scratch.alternate_prediction[observable] != alternate_class) {
throw std::logic_error("gap boundary inference returned the wrong logical class");
}
gap_result.gaps.push_back(std::abs(alternate_weight - hard_weight));
}
if (gap_scratch.events.empty()) {
empty_gap_result = gap_result;
return *empty_gap_result;
}
return gap_result;
}
std::unique_ptr<MatchingHandle> matching_from_detector_error_model_text(
rust::Str dem_text,
bool enable_correlations) {
auto matching = std::make_unique<MatchingHandle>();
matching->impl_->dem_text = std::string(dem_text);
matching->impl_->correlations_enabled = enable_correlations;
auto detector_error_model = stim::DetectorErrorModel(matching->impl_->dem_text);
matching->impl_->graph = pm::detector_error_model_to_user_graph(
detector_error_model,
enable_correlations,
pm::NUM_DISTINCT_WEIGHTS);
return matching;
}
void matching_add_edge_with_merge_strategy(
MatchingHandle& matching,
std::uint64_t node1,
std::uint64_t node2,
const ::EdgeInput& edge,
::MergeStrategy merge_strategy) {
auto& state = *matching.impl_;
state.invalidate_gap_source();
state.ensure_min_num_observables(edge.fault_ids);
state.graph.add_or_merge_edge(
static_cast<std::size_t>(node1),
static_cast<std::size_t>(node2),
MatchingHandle::Impl::to_observables(edge.fault_ids),
edge.weight,
edge.error_probability,
to_pm_merge_strategy(merge_strategy));
}
void matching_add_boundary_edge_with_merge_strategy(
MatchingHandle& matching,
std::uint64_t node,
const ::EdgeInput& edge,
::MergeStrategy merge_strategy) {
auto& state = *matching.impl_;
state.invalidate_gap_source();
state.ensure_min_num_observables(edge.fault_ids);
state.graph.add_or_merge_boundary_edge(
static_cast<std::size_t>(node),
MatchingHandle::Impl::to_observables(edge.fault_ids),
edge.weight,
edge.error_probability,
to_pm_merge_strategy(merge_strategy));
}
bool matching_has_edge(const MatchingHandle& matching, std::uint64_t node1, std::uint64_t node2) {
const auto& state = *matching.impl_;
return state.graph.has_edge(static_cast<std::size_t>(node1), static_cast<std::size_t>(node2));
}
bool matching_has_boundary_edge(const MatchingHandle& matching, std::uint64_t node) {
const auto& state = *matching.impl_;
return state.graph.has_boundary_edge(static_cast<std::size_t>(node));
}
std::uint64_t matching_num_nodes(const MatchingHandle& matching) {
return static_cast<std::uint64_t>(matching.impl_->graph.get_num_nodes());
}
std::uint64_t matching_num_edges(const MatchingHandle& matching) {
return static_cast<std::uint64_t>(matching.impl_->graph.get_num_edges());
}
std::uint64_t matching_num_fault_ids(const MatchingHandle& matching) {
return static_cast<std::uint64_t>(matching.impl_->graph.get_num_observables());
}
rust::Vec<std::uint64_t> matching_boundary_nodes(const MatchingHandle& matching) {
rust::Vec<std::uint64_t> nodes;
for (auto node : matching.impl_->graph.get_boundary()) {
nodes.push_back(static_cast<std::uint64_t>(node));
}
return nodes;
}
void matching_set_boundary_nodes(MatchingHandle& matching, rust::Slice<const std::uint64_t> nodes) {
matching.impl_->invalidate_gap_source();
matching.impl_->graph.set_boundary(MatchingHandle::Impl::to_boundary_set(nodes));
}
void matching_ensure_num_fault_ids(MatchingHandle& matching, std::uint64_t min_num_fault_ids) {
matching.impl_->invalidate_gap_source();
matching.impl_->graph.set_min_num_observables(static_cast<std::size_t>(min_num_fault_ids));
}
std::uint64_t matching_num_detectors(const MatchingHandle& matching) {
return static_cast<std::uint64_t>(matching.impl_->graph.get_num_detectors());
}
rust::Vec<::EdgeRecord> matching_edges(const MatchingHandle& matching) {
rust::Vec<::EdgeRecord> edges;
for (const auto& edge : matching.impl_->graph.edges) {
edges.push_back(MatchingHandle::Impl::to_edge_record(edge));
}
return edges;
}
::EdgeRecord matching_edge_data(const MatchingHandle& matching, std::uint64_t node1, std::uint64_t node2) {
return MatchingHandle::Impl::edge_data_record(
matching.impl_->graph,
static_cast<std::size_t>(node1),
static_cast<std::size_t>(node2));
}
::EdgeRecord matching_boundary_edge_data(const MatchingHandle& matching, std::uint64_t node) {
return MatchingHandle::Impl::boundary_edge_data_record(
matching.impl_->graph,
static_cast<std::size_t>(node));
}
rust::Vec<std::uint8_t> matching_decode(
const MatchingHandle& matching,
rust::Slice<const std::uint8_t> syndrome) {
::DecodeConfig config;
auto detection_events = collect_detection_events(matching.impl_->graph, syndrome);
return decode_detection_events(matching.impl_->graph, detection_events, config).prediction;
}
::DecodeResult matching_decode_with_config(
const MatchingHandle& matching,
rust::Slice<const std::uint8_t> syndrome,
const ::DecodeConfig& config) {
auto detection_events = collect_detection_events(matching.impl_->graph, syndrome);
return decode_detection_events(matching.impl_->graph, detection_events, config);
}
::GapDecodeResult matching_decode_gap(
const MatchingHandle& matching,
rust::Slice<const std::uint8_t> syndrome) {
const auto& decoded = matching.impl_->decode_gap_native(syndrome);
::GapDecodeResult result;
result.prediction = to_rust_vec(decoded.prediction);
result.gaps = to_rust_vec(decoded.gaps);
return result;
}
::GapBatchDecodeResult matching_decode_gap_batch(
const MatchingHandle& matching,
rust::Slice<const std::uint8_t> shots,
std::uint64_t num_rows,
std::uint64_t num_cols) {
auto& graph = matching.impl_->graph;
const auto rows = static_cast<std::size_t>(num_rows);
const auto cols = static_cast<std::size_t>(num_cols);
if (cols != graph.get_num_detectors()) {
throw std::invalid_argument(
"gap batch columns must equal the number of detectors");
}
if (rows != 0 && cols > SIZE_MAX / rows) {
throw std::invalid_argument("gap batch dimensions overflow");
}
if (shots.size() != rows * cols) {
throw std::invalid_argument(
"gap batch buffer size must equal num_rows * num_cols");
}
::GapBatchDecodeResult result;
result.rows = rows;
result.cols = graph.get_num_observables();
result.predictions.reserve(rows * result.cols);
result.gaps.reserve(rows * result.cols);
for (std::size_t row = 0; row < rows; row++) {
const auto syndrome = rust::Slice<const std::uint8_t>(
shots.data() + row * cols, cols);
const auto& decoded = matching.impl_->decode_gap_native(syndrome);
for (auto bit : decoded.prediction) result.predictions.push_back(bit);
for (auto gap : decoded.gaps) result.gaps.push_back(gap);
}
return result;
}
::BatchDecodeResult matching_decode_batch(
const MatchingHandle& matching,
rust::Slice<const std::uint8_t> shots,
std::uint64_t num_rows,
std::uint64_t num_cols,
const ::DecodeConfig& config) {
auto& graph = matching.impl_->graph;
const auto rows = static_cast<std::size_t>(num_rows);
const auto cols = static_cast<std::size_t>(num_cols);
validate_batch_shape(graph, rows, cols, config.bit_packed_shots);
const auto expected_size = rows * cols;
if (shots.size() != expected_size) {
throw std::invalid_argument(
"flat `shots` buffer size (" + std::to_string(shots.size()) +
") must match num_rows * num_cols (" + std::to_string(expected_size) + ")");
}
const auto num_prediction_cols = config.bit_packed_predictions
? ((graph.get_num_observables() + 7) >> 3)
: graph.get_num_observables();
std::vector<std::uint8_t> predictions(rows * num_prediction_cols, 0);
std::vector<double> weights;
if (config.return_weight) {
weights.resize(rows, 0.0);
}
auto& mwpm = config.enable_correlations ? graph.get_mwpm_with_search_graph() : graph.get_mwpm();
std::vector<std::uint64_t> detection_events;
std::vector<std::uint8_t> temp_predictions;
if (config.bit_packed_predictions) {
temp_predictions.resize(graph.get_num_observables(), 0);
}
for (std::size_t row = 0; row < rows; row++) {
const auto row_start = row * cols;
if (config.bit_packed_shots) {
for (std::size_t col = 0; col < cols; col++) {
const auto byte = shots[row_start + col];
const auto bit_offset = col << 3;
for (std::size_t bit = 0; bit < 8; bit++) {
if ((byte & (1u << bit)) == 0) {
continue;
}
const auto detector = bit_offset + bit;
if (detector >= graph.get_num_nodes()) {
throw std::invalid_argument(
"detection event index (" + std::to_string(detector) + ") must be less than the number of nodes (" +
std::to_string(graph.get_num_nodes()) + ")");
}
detection_events.push_back(static_cast<std::uint64_t>(detector));
}
}
} else {
for (std::size_t col = 0; col < cols; col++) {
const auto value = shots[row_start + col];
if (value > 1) {
throw std::invalid_argument("syndrome values must be binary");
}
if (value == 1) {
detection_events.push_back(static_cast<std::uint64_t>(col));
}
}
}
pm::total_weight_int solution_weight = 0;
auto* prediction_ptr = predictions.data() + row * num_prediction_cols;
if (config.bit_packed_predictions) {
std::fill(temp_predictions.begin(), temp_predictions.end(), 0);
pm::decode_detection_events(
mwpm,
detection_events,
temp_predictions.data(),
solution_weight,
config.enable_correlations);
for (std::size_t observable = 0; observable < temp_predictions.size(); observable++) {
const auto byte_index = observable >> 3;
prediction_ptr[byte_index] ^= (temp_predictions[observable] << (observable & 7));
}
} else {
pm::decode_detection_events(
mwpm,
detection_events,
prediction_ptr,
solution_weight,
config.enable_correlations);
}
if (config.return_weight) {
weights[row] = static_cast<double>(solution_weight) / mwpm.flooder.graph.normalising_constant;
}
detection_events.clear();
}
rust::Vec<std::uint8_t> rust_predictions;
for (auto value : predictions) {
rust_predictions.push_back(value);
}
rust::Vec<double> rust_weights;
for (auto value : weights) {
rust_weights.push_back(value);
}
::BatchDecodeResult result;
result.predictions = std::move(rust_predictions);
result.prediction_rows = num_rows;
result.prediction_cols = static_cast<std::uint64_t>(num_prediction_cols);
result.weights = std::move(rust_weights);
result.has_weights = config.return_weight;
return result;
}
::Int64Matrix matching_decode_to_edges_array(
const MatchingHandle& matching,
rust::Slice<const std::uint8_t> syndrome,
bool enable_correlations) {
auto detection_events = collect_detection_events(matching.impl_->graph, syndrome);
auto& mwpm = matching.impl_->graph.get_mwpm_with_search_graph();
std::vector<std::int64_t> edges;
if (enable_correlations) {
pm::decode_detection_events_to_edges_with_edge_correlations(mwpm, detection_events, edges);
} else {
pm::decode_detection_events_to_edges(mwpm, detection_events, edges);
}
rust::Vec<std::int64_t> data;
for (auto value : edges) {
data.push_back(value);
}
::Int64Matrix result;
result.data = std::move(data);
result.rows = static_cast<std::uint64_t>(edges.size() / 2);
result.cols = 2;
return result;
}
::Int64Matrix matching_decode_to_matched_dets_array(
const MatchingHandle& matching,
rust::Slice<const std::uint8_t> syndrome) {
auto detection_events = collect_detection_events(matching.impl_->graph, syndrome);
auto& mwpm = matching.impl_->graph.get_mwpm();
pm::decode_detection_events_to_match_edges(mwpm, detection_events);
rust::Vec<std::int64_t> data;
for (const auto& edge : mwpm.flooder.match_edges) {
data.push_back(edge.loc_from - &mwpm.flooder.graph.nodes[0]);
if (edge.loc_to) {
data.push_back(edge.loc_to - &mwpm.flooder.graph.nodes[0]);
} else {
data.push_back(-1);
}
}
::Int64Matrix result;
result.data = std::move(data);
result.rows = static_cast<std::uint64_t>(mwpm.flooder.match_edges.size());
result.cols = 2;
return result;
}
::NoiseResult matching_add_noise(const MatchingHandle& matching) {
return with_locked_noise_rng([&]() {
return make_noise_result(matching.impl_->graph);
});
}
::NoiseResult matching_add_noise_with_seed(const MatchingHandle& matching, std::uint64_t seed) {
if (seed > static_cast<std::uint64_t>(UINT_MAX)) {
throw std::invalid_argument("seed must fit in a 32-bit unsigned integer");
}
return with_locked_noise_rng([&]() {
const auto saved_rng = pm::global_urng();
pm::set_seed(static_cast<unsigned>(seed));
try {
auto result = make_noise_result(matching.impl_->graph);
pm::global_urng() = saved_rng;
return result;
} catch (...) {
pm::global_urng() = saved_rng;
throw;
}
});
}
void set_global_rng_seed_for_tests(std::uint64_t seed) {
if (seed > static_cast<std::uint64_t>(UINT_MAX)) {
throw std::invalid_argument("seed must fit in a 32-bit unsigned integer");
}
pm::set_seed(static_cast<unsigned>(seed));
}
void hold_noise_rng_lock_for_tests(std::uint64_t duration_ms) {
with_locked_noise_rng([&]() {
std::this_thread::sleep_for(std::chrono::milliseconds(duration_ms));
});
}
bool is_noise_rng_lock_held_for_tests() {
return noise_rng_lock_held_for_tests().load(std::memory_order_acquire);
}
std::unique_ptr<MatchingHandle> new_matching_handle() {
return std::make_unique<MatchingHandle>();
}
std::unique_ptr<MatchingHandle> new_matching_handle_with_num_nodes(std::uint64_t num_nodes) {
auto matching = std::make_unique<MatchingHandle>();
matching->impl_->graph = pm::UserGraph(static_cast<std::size_t>(num_nodes));
return matching;
}
}