25903914664-1

// Copyright (C) 2013-2020 Blockstack PBC, a public benefit corporation
// Copyright (C) 2020-2024 Stacks Open Internet Foundation
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#[cfg(feature = "rusqlite")]
use rusqlite::types::{FromSql, FromSqlError, FromSqlResult, ToSql, ToSqlOutput, ValueRef};
use serde::{Deserialize, Serialize};

use crate::codec::{
    read_next, read_next_exact, write_next, Error as CodecError, StacksMessageCodec,
};
use crate::util::hash::{bytes_to_hex, hex_bytes};

#[derive(Clone, PartialEq, Eq, Debug)]
/// This data structure represents a list of booleans
/// as a bitvector.
///
/// The generic argument `MAX_SIZE` specifies the maximum number of
/// elements that the bit vector can hold. It is not the _actual_ size
/// of the bitvec: if there are only 8 entries, the bitvector will
/// just have a single byte, even if the MAX_SIZE is u16::MAX. This
/// type parameter ensures that constructors and deserialization routines
/// error if input data is too long.
pub struct BitVec<const MAX_SIZE: u16> {
    data: Vec<u8>,
    len: u16,
}

impl<const MAX_SIZE: u16> TryFrom<&[bool]> for BitVec<MAX_SIZE> {
    type Error = String;

    fn try_from(value: &[bool]) -> Result<Self, Self::Error> {
        let len = value
            .len()
            .try_into()
            .map_err(|_| "BitVec length must be u16")?;
        if len == 0 {
            return Err("BitVec length must be positive".into());
        }
        if len > MAX_SIZE {
            return Err(format!(
                "BitVec length is too long. Max size = {MAX_SIZE}, Input len = {len}"
            ));
        }
        let mut bitvec = BitVec::zeros(len)?;
        for (ix, bool_value) in value.iter().enumerate() {
            let ix = ix.try_into().map_err(|_| "BitVec length must be u16")?;
            // only need to set the bitvec value if `bool_value` is true,
            // because we initialized with zeros
            if *bool_value {
                bitvec.set(ix, true)?;
            }
        }
        Ok(bitvec)
    }
}

impl<const MAX_SIZE: u16> StacksMessageCodec for BitVec<MAX_SIZE> {
    fn consensus_serialize<W: std::io::Write>(&self, fd: &mut W) -> Result<(), CodecError> {
        write_next(fd, &self.len)?;
        write_next(fd, &self.data)
    }

    fn consensus_deserialize<R: std::io::Read>(fd: &mut R) -> Result<Self, CodecError> {
        let len = read_next(fd)?;
        if len == 0 {
            return Err(CodecError::DeserializeError(
                "BitVec lengths must be positive".to_string(),
            ));
        }
        if len > MAX_SIZE {
            return Err(CodecError::DeserializeError(format!(
                "BitVec length exceeded maximum. Max size = {MAX_SIZE}, len = {len}"
            )));
        }

        let data = read_next_exact(fd, Self::data_len(len).into())?;
        Ok(BitVec { data, len })
    }
}

impl<const MAX_SIZE: u16> Serialize for BitVec<MAX_SIZE> {
    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        let hex = bytes_to_hex(self.serialize_to_vec().as_slice());
        serializer.serialize_str(&hex)
    }
}

impl<'de, const MAX_SIZE: u16> Deserialize<'de> for BitVec<MAX_SIZE> {
    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        let hex: String = Deserialize::deserialize(deserializer)?;
        let bytes = hex_bytes(hex.as_str()).map_err(serde::de::Error::custom)?;
        Self::consensus_deserialize(&mut bytes.as_slice()).map_err(serde::de::Error::custom)
    }
}

#[cfg(feature = "rusqlite")]
impl<const MAX_SIZE: u16> FromSql for BitVec<MAX_SIZE> {
    fn column_result(value: ValueRef<'_>) -> FromSqlResult<Self> {
        let bytes = hex_bytes(value.as_str()?).map_err(|e| FromSqlError::Other(Box::new(e)))?;
        Self::consensus_deserialize(&mut bytes.as_slice())
            .map_err(|e| FromSqlError::Other(Box::new(e)))
    }
}

#[cfg(feature = "rusqlite")]
impl<const MAX_SIZE: u16> ToSql for BitVec<MAX_SIZE> {
    fn to_sql(&self) -> rusqlite::Result<ToSqlOutput<'_>> {
        let hex = bytes_to_hex(self.serialize_to_vec().as_slice());
        Ok(hex.into())
    }
}

pub struct BitVecIter<'a, const MAX_SIZE: u16> {
    index: u16,
    byte: Option<&'a u8>,
    bitvec: &'a BitVec<MAX_SIZE>,
}

impl<const MAX_SIZE: u16> Iterator for BitVecIter<'_, MAX_SIZE> {
    type Item = bool;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index >= self.bitvec.len {
            return None;
        }
        let byte = self.byte?;
        let next = (*byte & BitVec::<MAX_SIZE>::bit_index(self.index)) != 0;
        self.index = self.index.saturating_add(1);
        if self.index < self.bitvec.len {
            // check if byte needs to be incremented
            if self.index.is_multiple_of(8) {
                let vec_index = usize::from(self.index / 8);
                self.byte = self.bitvec.data.get(vec_index);
            }
        }
        Some(next)
    }
}

impl<const MAX_SIZE: u16> BitVec<MAX_SIZE> {
    /// Construct a new BitVec with all entries set to `false` and total length `len`
    pub fn zeros(len: u16) -> Result<BitVec<MAX_SIZE>, String> {
        if len > MAX_SIZE {
            return Err(format!(
                "BitVec length is too long. Max size = {MAX_SIZE}, Input len = {len}"
            ));
        }
        let data = vec![0; usize::from(Self::data_len(len))];
        Ok(BitVec { data, len })
    }

    /// Construct a new BitVec with all entries set to `true` and total length `len`
    pub fn ones(len: u16) -> Result<BitVec<MAX_SIZE>, String> {
        let mut bitvec: BitVec<MAX_SIZE> = BitVec::zeros(len)?;
        for i in 0..len {
            bitvec.set(i, true)?;
        }
        Ok(bitvec)
    }

    pub fn iter(&self) -> BitVecIter<'_, MAX_SIZE> {
        let byte = self.data.first();
        BitVecIter {
            index: 0,
            bitvec: self,
            byte,
        }
    }

    pub fn len(&self) -> u16 {
        self.len
    }

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Return the number of bytes needed to store `len` bits.
    fn data_len(len: u16) -> u16 {
        len / 8 + if len.is_multiple_of(8) { 0 } else { 1 }
    }

    /// Get a u8 with the (index % 8)th bit set to 1.
    fn bit_index(index: u16) -> u8 {
        1 << u8::try_from(index % 8).expect("FATAL: remainder 8 returned a non-u8 value")
    }

    pub fn get(&self, i: u16) -> Option<bool> {
        if i >= self.len {
            return None;
        }
        let vec_index = usize::from(i / 8);
        let byte = self.data.get(vec_index)?;
        let bit_index = Self::bit_index(i);
        Some((*byte & bit_index) != 0)
    }

    pub fn set(&mut self, i: u16, val: bool) -> Result<(), String> {
        if i >= self.len {
            return Err(format!(
                "Index `{i}` outside of bitvec length `{}`",
                self.len
            ));
        }
        let vec_index = usize::from(i / 8);
        let Some(byte) = self.data.get_mut(vec_index) else {
            return Err(format!(
                "Index `{i}/8` outside of bitvec data length `{}`",
                self.data.len()
            ));
        };
        let bit_index = Self::bit_index(i);
        if val {
            *byte |= bit_index;
        } else {
            *byte &= !bit_index;
        }
        Ok(())
    }

    /// Set all bits to zero
    pub fn clear(&mut self) {
        for i in 0..self.data.len() {
            self.data[i] = 0;
        }
    }

    /// Serialize a BitVec to a string of 1s and 0s for display
    /// purposes. For example, a BitVec with [true, false, true]
    /// will be serialized to "101".
    pub fn binary_str(&self) -> String {
        self.clone()
            .data
            .into_iter()
            .fold(String::new(), |acc, byte| {
                acc + &format!("{byte:08b}").chars().rev().collect::<String>()
            })
            .chars()
            .take(self.len() as usize)
            .collect::<String>()
    }
}

#[cfg(test)]
mod test {
    use serde_json;

    use super::BitVec;
    use crate::codec::StacksMessageCodec;

    fn check_set_get(mut input: BitVec<{ u16::MAX }>) {
        let original_input = input.clone();
        for i in 0..input.len() {
            let original_value = input.get(i).unwrap();
            input.set(i, false).unwrap();
            assert_eq!(input.len(), original_input.len());
            for j in 0..input.len() {
                if j == i {
                    continue;
                }
                assert_eq!(original_input.get(j), input.get(j));
            }
            assert_eq!(input.get(i), Some(false));
            input.set(i, true).unwrap();
            for j in 0..input.len() {
                if j == i {
                    continue;
                }
                assert_eq!(original_input.get(j), input.get(j));
            }
            assert_eq!(input.get(i), Some(true));
            input.set(i, original_value).unwrap();
            assert_eq!(input.get(i), Some(original_value));
        }
        assert_eq!(input, original_input);
        assert!(input.set(input.len(), false).is_err());
    }

    fn check_iter(input: &BitVec<{ u16::MAX }>) {
        let mut checked = 0;
        for (ix, entry) in input.iter().enumerate() {
            checked += 1;
            assert_eq!(input.get(u16::try_from(ix).unwrap()).unwrap(), entry);
        }
        assert_eq!(checked, input.len());
    }

    fn check_serialization(input: &BitVec<{ u16::MAX }>) {
        let byte_ser = input.serialize_to_vec();
        let deserialized = BitVec::consensus_deserialize(&mut byte_ser.as_slice()).unwrap();
        assert_eq!(input, &deserialized);
    }

    fn check_ok_vector(input: &[bool]) {
        let bitvec = BitVec::try_from(input).unwrap();
        assert_eq!(bitvec.len(), input.len() as u16);
        for (ix, value) in input.iter().enumerate() {
            assert_eq!(bitvec.get(u16::try_from(ix).unwrap()), Some(*value));
        }
        // check that a length check will fail
        let passed_len_2_check = BitVec::<2>::try_from(input).is_ok();
        if input.len() <= 2 {
            assert!(
                passed_len_2_check,
                "BitVec should pass assembly in length-2 max because input is length-2"
            );
        } else {
            assert!(!passed_len_2_check, "BitVec should fail assembly in length-2 max because input is greater that length-2");
        }
        // check that a length check will fail on deserialization
        let serialization = bitvec.serialize_to_vec();
        let passed_len_2_deser =
            BitVec::<2>::consensus_deserialize(&mut serialization.as_slice()).is_ok();
        if input.len() <= 2 {
            assert!(
                passed_len_2_deser,
                "BitVec should pass assembly in length-2 max because input is length-2"
            );
        } else {
            assert!(!passed_len_2_deser, "BitVec should fail assembly in length-2 max because input is greater that length-2");
        }

        check_serialization(&bitvec);
        check_iter(&bitvec);
        check_set_get(bitvec);
    }

    #[test]
    fn zeros_constructor() {
        let bitvec_zero_10 = BitVec::<10>::zeros(10).unwrap();
        for i in 0..10 {
            assert!(
                !bitvec_zero_10.get(i).unwrap(),
                "All values of zero vec should be false"
            );
        }
        assert!(
            BitVec::<2>::zeros(3).is_err(),
            "Should fail to construct a length 3 zero vec when bound to bitlength 2"
        );
    }

    #[test]
    fn binary_str_serialization() {
        let mut bitvec_zero_10 = BitVec::<10>::zeros(10).unwrap();
        bitvec_zero_10.set(0, true).unwrap();
        bitvec_zero_10.set(5, true).unwrap();
        bitvec_zero_10.set(3, true).unwrap();
        assert_eq!(
            bitvec_zero_10.binary_str(),
            "1001010000",
            "Binary string should be 1001010000"
        );
    }

    #[test]
    fn bitvec_ones() {
        let bitvec_ones_10 = BitVec::<10>::ones(10).unwrap();
        for i in 0..10 {
            assert!(
                bitvec_ones_10.get(i).unwrap(),
                "All values of ones vec should be true"
            );
        }
        info!("bitvec_ones_10: {:?}", bitvec_ones_10.binary_str());
    }

    #[test]
    fn vectors() {
        let mut inputs = vec![
            vec![true; 8],
            vec![false; 8],
            vec![true; 12],
            vec![false; 12],
            vec![false],
            vec![true],
            vec![false, true],
            vec![true, false],
        ];
        for i in 0..8 {
            let mut single_set_vec = vec![false; 8];
            let mut single_unset_vec = vec![true; 8];
            single_unset_vec[i] = false;
            single_set_vec[i] = true;
            inputs.push(single_set_vec);
            inputs.push(single_unset_vec);
        }
        let large_set_vec = vec![false; u16::MAX.into()];
        let large_unset_vec = vec![true; u16::MAX.into()];
        inputs.push(large_set_vec);
        inputs.push(large_unset_vec);

        for i in 1..128 {
            let mut bool_vec = vec![false; i];
            for (j, val) in bool_vec.iter_mut().enumerate() {
                *val = j % 2 == 0;
            }
            inputs.push(bool_vec);
        }

        for i in inputs.into_iter() {
            check_ok_vector(i.as_slice());
        }
    }

    #[test]
    fn test_serde() {
        let mut bitvec_zero_10 = BitVec::<10>::zeros(10).unwrap();
        bitvec_zero_10.set(0, true).unwrap();
        bitvec_zero_10.set(5, true).unwrap();
        bitvec_zero_10.set(3, true).unwrap();
        assert_eq!(
            bitvec_zero_10.binary_str(),
            "1001010000",
            "Binary string should be 1001010000"
        );

        let serde_bitvec_json = serde_json::to_string(&bitvec_zero_10).unwrap();
        let serde_bitvec: BitVec<10> = serde_json::from_str(&serde_bitvec_json).unwrap();
        assert_eq!(serde_bitvec, bitvec_zero_10);
    }
}

1	// Copyright (C) 2013-2020 Blockstack PBC, a public benefit corporation
2	// Copyright (C) 2020-2024 Stacks Open Internet Foundation
3	//
4	// This program is free software: you can redistribute it and/or modify
5	// it under the terms of the GNU General Public License as published by
6	// the Free Software Foundation, either version 3 of the License, or
7	// (at your option) any later version.
8	//
9	// This program is distributed in the hope that it will be useful,
10	// but WITHOUT ANY WARRANTY; without even the implied warranty of
11	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12	// GNU General Public License for more details.
13	//
14	// You should have received a copy of the GNU General Public License
15	// along with this program. If not, see <http://www.gnu.org/licenses/>.
16
17	#[cfg(feature = "rusqlite")]
18	use rusqlite::types::{FromSql, FromSqlError, FromSqlResult, ToSql, ToSqlOutput, ValueRef};
19	use serde::{Deserialize, Serialize};
20
21	use crate::codec::{
22	read_next, read_next_exact, write_next, Error as CodecError, StacksMessageCodec,
23	};
24	use crate::util::hash::{bytes_to_hex, hex_bytes};
25
26	#[derive(Clone, PartialEq, Eq, Debug)]
27	/// This data structure represents a list of booleans
28	/// as a bitvector.
29	///
30	/// The generic argument `MAX_SIZE` specifies the maximum number of
31	/// elements that the bit vector can hold. It is not the _actual_ size
32	/// of the bitvec: if there are only 8 entries, the bitvector will
33	/// just have a single byte, even if the MAX_SIZE is u16::MAX. This
34	/// type parameter ensures that constructors and deserialization routines
35	/// error if input data is too long.
36	pub struct BitVec<const MAX_SIZE: u16> {
37	data: Vec<u8>,
38	len: u16,
39	}
40
41	impl<const MAX_SIZE: u16> TryFrom<&[bool]> for BitVec<MAX_SIZE> {
42	type Error = String;
43
44	fn try_from(value: &[bool]) -> Result<Self, Self::Error> {	219,096✔
45	let len = value	219,096✔
46	.len()	219,096✔
47	.try_into()	219,096✔
48	.map_err(\|_\| "BitVec length must be u16")?;	219,096✔
49	if len == 0 {	219,096✔
50	return Err("BitVec length must be positive".into());	×
51	}	219,096✔
52	if len > MAX_SIZE {	219,096✔
53	return Err(format!(	×
54	"BitVec length is too long. Max size = {MAX_SIZE}, Input len = {len}"	×
55	));	×
56	}	219,096✔
57	let mut bitvec = BitVec::zeros(len)?;	219,096✔
58	for (ix, bool_value) in value.iter().enumerate() {	5,567,616✔
59	let ix = ix.try_into().map_err(\|_\| "BitVec length must be u16")?;	5,567,616✔
60	// only need to set the bitvec value if `bool_value` is true,
61	// because we initialized with zeros
62	if *bool_value {	5,567,616✔
63	bitvec.set(ix, true)?;	250,947✔
64	}	5,316,669✔
65	}
66	Ok(bitvec)	219,096✔
67	}	219,096✔
68	}
69
70	impl<const MAX_SIZE: u16> StacksMessageCodec for BitVec<MAX_SIZE> {
71	fn consensus_serialize<W: std::io::Write>(&self, fd: &mut W) -> Result<(), CodecError> {	10,980,253✔
72	write_next(fd, &self.len)?;	10,980,253✔
73	write_next(fd, &self.data)	10,980,253✔
74	}	10,980,253✔
75
76	fn consensus_deserialize<R: std::io::Read>(fd: &mut R) -> Result<Self, CodecError> {	13,778,730✔
77	let len = read_next(fd)?;	13,778,730✔
78	if len == 0 {	13,778,730✔
79	return Err(CodecError::DeserializeError(	×
80	"BitVec lengths must be positive".to_string(),	×
81	));	×
82	}	13,778,730✔
83	if len > MAX_SIZE {	13,778,730✔
84	return Err(CodecError::DeserializeError(format!(	×
85	"BitVec length exceeded maximum. Max size = {MAX_SIZE}, len = {len}"	×
86	)));	×
87	}	13,778,730✔
88
89	let data = read_next_exact(fd, Self::data_len(len).into())?;	13,778,730✔
90	Ok(BitVec { data, len })	13,778,730✔
91	}	13,778,730✔
92	}
93
94	impl<const MAX_SIZE: u16> Serialize for BitVec<MAX_SIZE> {
95	fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {	622,467✔
96	let hex = bytes_to_hex(self.serialize_to_vec().as_slice());	622,467✔
97	serializer.serialize_str(&hex)	622,467✔
98	}	622,467✔
99	}
100
101	impl<'de, const MAX_SIZE: u16> Deserialize<'de> for BitVec<MAX_SIZE> {
102	fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {	527,673✔
103	let hex: String = Deserialize::deserialize(deserializer)?;	527,673✔
104	let bytes = hex_bytes(hex.as_str()).map_err(serde::de::Error::custom)?;	527,673✔
105	Self::consensus_deserialize(&mut bytes.as_slice()).map_err(serde::de::Error::custom)	527,673✔
106	}	527,673✔
107	}
108
109	#[cfg(feature = "rusqlite")]
110	impl<const MAX_SIZE: u16> FromSql for BitVec<MAX_SIZE> {
111	fn column_result(value: ValueRef<'_>) -> FromSqlResult<Self> {	11,555,250✔
112	let bytes = hex_bytes(value.as_str()?).map_err(\|e\| FromSqlError::Other(Box::new(e)))?;	11,555,250✔
113	Self::consensus_deserialize(&mut bytes.as_slice())	11,555,250✔
114	.map_err(\|e\| FromSqlError::Other(Box::new(e)))	11,555,250✔
115	}	11,555,250✔
116	}
117
118	#[cfg(feature = "rusqlite")]
119	impl<const MAX_SIZE: u16> ToSql for BitVec<MAX_SIZE> {
120	fn to_sql(&self) -> rusqlite::Result<ToSqlOutput<'_>> {	26,039✔
121	let hex = bytes_to_hex(self.serialize_to_vec().as_slice());	26,039✔
122	Ok(hex.into())	26,039✔
123	}	26,039✔
124	}
125
126	pub struct BitVecIter<'a, const MAX_SIZE: u16> {
127	index: u16,
128	byte: Option<&'a u8>,
129	bitvec: &'a BitVec<MAX_SIZE>,
130	}
131
132	impl<const MAX_SIZE: u16> Iterator for BitVecIter<'_, MAX_SIZE> {
133	type Item = bool;
134
135	fn next(&mut self) -> Option<Self::Item> {	611,025✔
136	if self.index >= self.bitvec.len {	611,025✔
137	return None;	16,938✔
138	}	594,087✔
139	let byte = self.byte?;	594,087✔
140	let next = (*byte & BitVec::<MAX_SIZE>::bit_index(self.index)) != 0;	594,087✔
141	self.index = self.index.saturating_add(1);	594,087✔
142	if self.index < self.bitvec.len {	594,087✔
143	// check if byte needs to be incremented
144	if self.index.is_multiple_of(8) {	577,149✔
145	let vec_index = usize::from(self.index / 8);	64,218✔
146	self.byte = self.bitvec.data.get(vec_index);	64,218✔
147	}	512,931✔
148	}	16,938✔
149	Some(next)	594,087✔
150	}	611,025✔
151	}
152
153	impl<const MAX_SIZE: u16> BitVec<MAX_SIZE> {
154	/// Construct a new BitVec with all entries set to `false` and total length `len`
155	pub fn zeros(len: u16) -> Result<BitVec<MAX_SIZE>, String> {	320,646✔
156	if len > MAX_SIZE {	320,646✔
157	return Err(format!(	×
158	"BitVec length is too long. Max size = {MAX_SIZE}, Input len = {len}"	×
159	));	×
160	}	320,646✔
161	let data = vec![0; usize::from(Self::data_len(len))];	320,646✔
162	Ok(BitVec { data, len })	320,646✔
163	}	320,646✔
164
165	/// Construct a new BitVec with all entries set to `true` and total length `len`
166	pub fn ones(len: u16) -> Result<BitVec<MAX_SIZE>, String> {	101,496✔
167	let mut bitvec: BitVec<MAX_SIZE> = BitVec::zeros(len)?;	101,496✔
168	for i in 0..len {	3,475,232✔
169	bitvec.set(i, true)?;	3,475,232✔
170	}
171	Ok(bitvec)	101,496✔
172	}	101,496✔
173
174	pub fn iter(&self) -> BitVecIter<'_, MAX_SIZE> {	16,938✔
175	let byte = self.data.first();	16,938✔
176	BitVecIter {	16,938✔
177	index: 0,	16,938✔
178	bitvec: self,	16,938✔
179	byte,	16,938✔
180	}	16,938✔
181	}	16,938✔
182
183	pub fn len(&self) -> u16 {	36,902✔
184	self.len	36,902✔
185	}	36,902✔
186
187	pub fn is_empty(&self) -> bool {	×
188	self.len == 0	×
189	}	×
190
191	/// Return the number of bytes needed to store `len` bits.
192	fn data_len(len: u16) -> u16 {	14,099,376✔
193	len / 8 + if len.is_multiple_of(8) { 0 } else { 1 }	14,099,376✔
194	}	14,099,376✔
195
196	/// Get a u8 with the (index % 8)th bit set to 1.
197	fn bit_index(index: u16) -> u8 {	30,894,581✔
198	1 << u8::try_from(index % 8).expect("FATAL: remainder 8 returned a non-u8 value")	30,894,581✔
199	}	30,894,581✔
200
201	pub fn get(&self, i: u16) -> Option<bool> {	25,472,181✔
202	if i >= self.len {	25,472,181✔
203	return None;	86,040✔
204	}	25,386,141✔
205	let vec_index = usize::from(i / 8);	25,386,141✔
206	let byte = self.data.get(vec_index)?;	25,386,141✔
207	let bit_index = Self::bit_index(i);	25,386,141✔
208	Some((*byte & bit_index) != 0)	25,386,141✔
209	}	25,472,181✔
210
211	pub fn set(&mut self, i: u16, val: bool) -> Result<(), String> {	3,726,179✔
212	if i >= self.len {	3,726,179✔
213	return Err(format!(	×
214	"Index `{i}` outside of bitvec length `{}`",	×
215	self.len	×
216	));	×
217	}	3,726,179✔
218	let vec_index = usize::from(i / 8);	3,726,179✔
219	let Some(byte) = self.data.get_mut(vec_index) else {	3,726,179✔
220	return Err(format!(	×
221	"Index `{i}/8` outside of bitvec data length `{}`",	×
222	self.data.len()	×
223	));	×
224	};
225	let bit_index = Self::bit_index(i);	3,726,179✔
226	if val {	3,726,179✔
227	*byte \|= bit_index;	3,726,179✔
228	} else {	3,726,179✔
229	*byte &= !bit_index;	×
230	}	×
231	Ok(())	3,726,179✔
232	}	3,726,179✔
233
234	/// Set all bits to zero
235	pub fn clear(&mut self) {	×
236	for i in 0..self.data.len() {	×
237	self.data[i] = 0;	×
238	}	×
239	}	×
240
241	/// Serialize a BitVec to a string of 1s and 0s for display
242	/// purposes. For example, a BitVec with [true, false, true]
243	/// will be serialized to "101".
244	pub fn binary_str(&self) -> String {	×
245	self.clone()	×
246	.data	×
247	.into_iter()	×
248	.fold(String::new(), \|acc, byte\| {	×
249	acc + &format!("{byte:08b}").chars().rev().collect::<String>()	×
250	})	×
251	.chars()	×
252	.take(self.len() as usize)	×
253	.collect::<String>()	×
254	}	×
255	}
256
257	#[cfg(test)]
258	mod test {
259	use serde_json;
260
261	use super::BitVec;
262	use crate::codec::StacksMessageCodec;
263
264	fn check_set_get(mut input: BitVec<{ u16::MAX }>) {	×
265	let original_input = input.clone();	×
266	for i in 0..input.len() {	×
267	let original_value = input.get(i).unwrap();	×
268	input.set(i, false).unwrap();	×
269	assert_eq!(input.len(), original_input.len());	×
270	for j in 0..input.len() {	×
271	if j == i {	×
272	continue;	×
273	}	×
274	assert_eq!(original_input.get(j), input.get(j));	×
275	}
276	assert_eq!(input.get(i), Some(false));	×
277	input.set(i, true).unwrap();	×
278	for j in 0..input.len() {	×
279	if j == i {	×
280	continue;	×
281	}	×
282	assert_eq!(original_input.get(j), input.get(j));	×
283	}
284	assert_eq!(input.get(i), Some(true));	×
285	input.set(i, original_value).unwrap();	×
286	assert_eq!(input.get(i), Some(original_value));	×
287	}
288	assert_eq!(input, original_input);	×
289	assert!(input.set(input.len(), false).is_err());	×
290	}	×
291
292	fn check_iter(input: &BitVec<{ u16::MAX }>) {	×
293	let mut checked = 0;	×
294	for (ix, entry) in input.iter().enumerate() {	×
295	checked += 1;	×
296	assert_eq!(input.get(u16::try_from(ix).unwrap()).unwrap(), entry);	×
297	}
298	assert_eq!(checked, input.len());	×
299	}	×
300
301	fn check_serialization(input: &BitVec<{ u16::MAX }>) {	×
302	let byte_ser = input.serialize_to_vec();	×
303	let deserialized = BitVec::consensus_deserialize(&mut byte_ser.as_slice()).unwrap();	×
304	assert_eq!(input, &deserialized);	×
305	}	×
306
307	fn check_ok_vector(input: &[bool]) {	×
308	let bitvec = BitVec::try_from(input).unwrap();	×
309	assert_eq!(bitvec.len(), input.len() as u16);	×
310	for (ix, value) in input.iter().enumerate() {	×
311	assert_eq!(bitvec.get(u16::try_from(ix).unwrap()), Some(*value));	×
312	}
313	// check that a length check will fail
314	let passed_len_2_check = BitVec::<2>::try_from(input).is_ok();	×
315	if input.len() <= 2 {	×
316	assert!(	×
317	passed_len_2_check,	×
318	"BitVec should pass assembly in length-2 max because input is length-2"
319	);
320	} else {
321	assert!(!passed_len_2_check, "BitVec should fail assembly in length-2 max because input is greater that length-2");	×
322	}
323	// check that a length check will fail on deserialization
324	let serialization = bitvec.serialize_to_vec();	×
325	let passed_len_2_deser =	×
326	BitVec::<2>::consensus_deserialize(&mut serialization.as_slice()).is_ok();	×
327	if input.len() <= 2 {	×
328	assert!(	×
329	passed_len_2_deser,	×
330	"BitVec should pass assembly in length-2 max because input is length-2"
331	);
332	} else {
333	assert!(!passed_len_2_deser, "BitVec should fail assembly in length-2 max because input is greater that length-2");	×
334	}
335
336	check_serialization(&bitvec);	×
337	check_iter(&bitvec);	×
338	check_set_get(bitvec);	×
339	}	×
340
341	#[test]
342	fn zeros_constructor() {	×
343	let bitvec_zero_10 = BitVec::<10>::zeros(10).unwrap();	×
344	for i in 0..10 {	×
345	assert!(	×
346	!bitvec_zero_10.get(i).unwrap(),	×
347	"All values of zero vec should be false"
348	);
349	}
350	assert!(	×
351	BitVec::<2>::zeros(3).is_err(),	×
352	"Should fail to construct a length 3 zero vec when bound to bitlength 2"
353	);
354	}	×
355
356	#[test]
357	fn binary_str_serialization() {	×
358	let mut bitvec_zero_10 = BitVec::<10>::zeros(10).unwrap();	×
359	bitvec_zero_10.set(0, true).unwrap();	×
360	bitvec_zero_10.set(5, true).unwrap();	×
361	bitvec_zero_10.set(3, true).unwrap();	×
362	assert_eq!(	×
363	bitvec_zero_10.binary_str(),	×
364	"1001010000",
365	"Binary string should be 1001010000"
366	);
367	}	×
368
369	#[test]
370	fn bitvec_ones() {	×
371	let bitvec_ones_10 = BitVec::<10>::ones(10).unwrap();	×
372	for i in 0..10 {	×
373	assert!(	×
374	bitvec_ones_10.get(i).unwrap(),	×
375	"All values of ones vec should be true"
376	);
377	}
378	info!("bitvec_ones_10: {:?}", bitvec_ones_10.binary_str());	×
379	}	×
380
381	#[test]
382	fn vectors() {	×
383	let mut inputs = vec![	×
384	vec![true; 8],	×
385	vec![false; 8],	×
386	vec![true; 12],	×
387	vec![false; 12],	×
388	vec![false],	×
389	vec![true],	×
390	vec![false, true],	×
391	vec![true, false],	×
392	];
393	for i in 0..8 {	×
394	let mut single_set_vec = vec![false; 8];	×
395	let mut single_unset_vec = vec![true; 8];	×
396	single_unset_vec[i] = false;	×
397	single_set_vec[i] = true;	×
398	inputs.push(single_set_vec);	×
399	inputs.push(single_unset_vec);	×
400	}	×
401	let large_set_vec = vec![false; u16::MAX.into()];	×
402	let large_unset_vec = vec![true; u16::MAX.into()];	×
403	inputs.push(large_set_vec);	×
404	inputs.push(large_unset_vec);	×
405
406	for i in 1..128 {	×
407	let mut bool_vec = vec![false; i];	×
408	for (j, val) in bool_vec.iter_mut().enumerate() {	×
409	*val = j % 2 == 0;	×
410	}	×
411	inputs.push(bool_vec);	×
412	}
413
414	for i in inputs.into_iter() {	×
415	check_ok_vector(i.as_slice());	×
416	}	×
417	}	×
418
419	#[test]
420	fn test_serde() {	×
421	let mut bitvec_zero_10 = BitVec::<10>::zeros(10).unwrap();	×
422	bitvec_zero_10.set(0, true).unwrap();	×
423	bitvec_zero_10.set(5, true).unwrap();	×
424	bitvec_zero_10.set(3, true).unwrap();	×
425	assert_eq!(	×
426	bitvec_zero_10.binary_str(),	×
427	"1001010000",
428	"Binary string should be 1001010000"
429	);
430
431	let serde_bitvec_json = serde_json::to_string(&bitvec_zero_10).unwrap();	×
432	let serde_bitvec: BitVec<10> = serde_json::from_str(&serde_bitvec_json).unwrap();	×
433	assert_eq!(serde_bitvec, bitvec_zero_10);	×
434	}	×
435	}

stacks-network / stacks-core / 25903914664-1

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous