deq-runtime 0.5.0-rc2

deq: Real-time Quantum Error Correction Decoding System
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208

use crate::util::BitVector;

pub fn pack_bits(array: &[bool]) -> Vec<u8> {
    let mut packed: Vec<u8> = vec![0; bit_vector_len(array.len() as u64)];
    for (i, &bit) in array.iter().enumerate() {
        if bit {
            packed[i / 8] |= 1 << (7 - (i % 8));
        }
    }
    packed
}

pub fn unpack_bits(data: &[u8], size: u64) -> Vec<bool> {
    debug_assert!(data.len() == bit_vector_len(size));
    assert!((size as usize) <= data.len() * 8);
    let mut bits: Vec<bool> = vec![false; size as usize];
    for i in 0..size as usize {
        bits[i] = (data[i / 8] & (1 << (7 - (i % 8)))) != 0;
    }
    bits
}

pub fn xor_bits(a: &BitVector, b: &BitVector) -> BitVector {
    let mut result = a.clone();
    xor_bits_in_place(&mut result, b);
    result
}

pub fn xor_bits_in_place(a: &mut BitVector, b: &BitVector) {
    debug_assert!(a.size == b.size);
    for i in 0..a.data.len() {
        a.data[i] ^= b.data[i];
    }
}

#[inline]
pub fn byte_bit_index(index: u64) -> (usize, u8) {
    let byte_index = (index / 8) as usize;
    let bit_index = 7 - ((index % 8) as u8);
    (byte_index, bit_index)
}

#[inline]
pub fn bit_vector_len(size: u64) -> usize {
    size.div_ceil(8) as usize // (size + 7) / 8
}

pub fn from_sparse_indices(size: u64, indices: &[u64]) -> BitVector {
    let mut data = vec![0u8; bit_vector_len(size)];
    for &idx in indices {
        let (byte_index, bit_index) = byte_bit_index(idx);
        data[byte_index] |= 1 << bit_index;
    }
    BitVector { size, data }
}

pub fn to_sparse_indices(bit_vector: &BitVector) -> Vec<u64> {
    let mut indices = vec![];
    for index in 0..bit_vector.size {
        if get_bit(bit_vector, index) {
            indices.push(index);
        }
    }
    indices
}

/// Return whether every meaningful bit is zero, ignoring unused padding bits in
/// the final byte.
pub fn is_zero(bit_vector: &BitVector) -> bool {
    debug_assert!(crate::misc::validation::validate_data_len(bit_vector, "bit vector").is_ok());
    let full_bytes = (bit_vector.size / 8) as usize;
    if bit_vector.data[..full_bytes].iter().any(|&byte| byte != 0) {
        return false;
    }
    let remainder = bit_vector.size % 8;
    remainder == 0 || bit_vector.data[full_bytes] >> (8 - remainder) == 0
}

pub fn extend_num_bits(bit_vector: &mut BitVector, extending_length: u64) {
    bit_vector.size += extending_length;
    let new_data_len = bit_vector_len(bit_vector.size);
    bit_vector.data.resize(new_data_len, 0u8);
}

pub fn get_bit(bit_vector: &BitVector, index: u64) -> bool {
    debug_assert!(index < bit_vector.size);
    let (byte_index, bit_index) = byte_bit_index(index);
    (bit_vector.data[byte_index] & (1 << bit_index)) != 0
}

pub fn set_bit(bit_vector: &mut BitVector, index: u64, value: bool) {
    debug_assert!(index < bit_vector.size);
    let (byte_index, bit_index) = byte_bit_index(index);
    if value {
        bit_vector.data[byte_index] |= 1 << bit_index;
    } else {
        bit_vector.data[byte_index] &= !(1 << bit_index);
    }
}

pub fn flip_bit(bit_vector: &mut BitVector, index: u64) {
    debug_assert!(index < bit_vector.size);
    let (byte_index, bit_index) = byte_bit_index(index);
    bit_vector.data[byte_index] ^= 1 << bit_index;
}

pub fn bit_vector_to_string(bit_vector: &BitVector) -> String {
    let mut s = String::with_capacity(bit_vector.size as usize);
    for i in 0..bit_vector.size {
        if get_bit(bit_vector, i) {
            s.push('1');
        } else {
            s.push('0');
        }
    }
    s
}

pub fn binar_bitvec_to_bit_vector(bit_vec: &binar::BitVec, length: usize) -> BitVector {
    let mut data = vec![0u8; bit_vector_len(length as u64)];
    for (index, value) in (0..length).zip(bit_vec.iter()) {
        let (byte_index, bit_index) = byte_bit_index(index as u64);
        data[byte_index] |= (value as u8) << bit_index;
    }
    BitVector {
        size: length as u64,
        data,
    }
}

/// Extract a contiguous slice of bits from a BitVector
pub fn slice(bit_vector: &BitVector, start: usize, length: usize) -> BitVector {
    debug_assert!(start + length <= bit_vector.size as usize);
    let mut result = BitVector {
        size: length as u64,
        data: vec![0u8; bit_vector_len(length as u64)],
    };
    for i in 0..length {
        if get_bit(bit_vector, (start + i) as u64) {
            set_bit(&mut result, i as u64, true);
        }
    }
    result
}

/// Append bits from another BitVector to the end of this one
pub fn append(bit_vector: &mut BitVector, other: &BitVector) {
    let original_size = bit_vector.size;
    extend_num_bits(bit_vector, other.size);
    for i in 0..other.size {
        if get_bit(other, i) {
            set_bit(bit_vector, original_size + i, true);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn bits(string: &str) -> Vec<bool> {
        string
            .chars()
            .map(|c| match c {
                '0' => false,
                '1' => true,
                _ => panic!("invalid character in bit string"),
            })
            .collect()
    }

    #[test]
    fn bit_pack() {
        // cargo test bit_pack -- --nocapture

        // np.packbits([1,0,0,0,0,0,0,0]) = array([128], dtype=uint8)
        assert!(pack_bits(&bits("10000000")) == vec![128u8]);
        // np.packbits([1,0,0,0,0,0,0,0,0,1]) = array([128,  64], dtype=uint8)
        assert!(pack_bits(&bits("1000000001")) == vec![128u8, 64u8]);
        // np.packbits([0,0,0,1,0,1,0,0,1,1]) = array([ 20, 192], dtype=uint8)
        assert!(pack_bits(&bits("0001010011")) == vec![20u8, 192u8]);

        assert!(unpack_bits(&[128u8], 8) == bits("10000000"));
        assert!(unpack_bits(&[128u8, 64u8], 10) == bits("1000000001"));
        assert!(unpack_bits(&[20u8, 192u8], 10) == bits("0001010011"));
    }

    #[test]
    fn zero_check_ignores_padding_bits() {
        assert!(is_zero(&BitVector { size: 0, data: vec![] }));
        assert!(is_zero(&BitVector {
            size: 1,
            data: vec![0b0111_1111]
        }));
        assert!(!is_zero(&BitVector {
            size: 1,
            data: vec![0b1000_0000]
        }));
        assert!(is_zero(&BitVector {
            size: 9,
            data: vec![0, 0b0111_1111],
        }));
        assert!(!is_zero(&BitVector {
            size: 9,
            data: vec![0, 0b1000_0000],
        }));
    }
}