1#![forbid(unsafe_code)]
19
20#[derive(Debug, Clone, PartialEq, Eq)]
22pub struct Bitfield {
23 bytes: Vec<u8>,
24 num_pieces: usize,
25}
26
27#[derive(Debug, Clone, PartialEq, Eq)]
29pub enum Error {
30 WrongByteLength { got: usize, expected: usize },
32 SpareBitsSet,
35}
36
37impl std::fmt::Display for Error {
38 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
39 match self {
40 Error::WrongByteLength { got, expected } => {
41 write!(f, "bitfield is {got} bytes, expected {expected}")
42 }
43 Error::SpareBitsSet => write!(f, "spare trailing bits are set"),
44 }
45 }
46}
47
48impl std::error::Error for Error {}
49
50const fn byte_len(num_pieces: usize) -> usize {
51 num_pieces.div_ceil(8)
52}
53
54impl Bitfield {
55 #[must_use]
57 pub fn new(num_pieces: usize) -> Self {
58 Self { bytes: vec![0u8; byte_len(num_pieces)], num_pieces }
59 }
60
61 pub fn from_bytes(bytes: &[u8], num_pieces: usize) -> Result<Self, Error> {
67 let expected = byte_len(num_pieces);
68 if bytes.len() != expected {
69 return Err(Error::WrongByteLength { got: bytes.len(), expected });
70 }
71 let spare = expected * 8 - num_pieces;
73 if spare > 0 {
74 if let Some(&last) = bytes.last() {
75 let mask = (1u8 << spare) - 1; if last & mask != 0 {
77 return Err(Error::SpareBitsSet);
78 }
79 }
80 }
81 Ok(Self { bytes: bytes.to_vec(), num_pieces })
82 }
83
84 #[must_use]
86 pub fn as_bytes(&self) -> &[u8] {
87 &self.bytes
88 }
89
90 #[must_use]
92 pub fn len(&self) -> usize {
93 self.num_pieces
94 }
95
96 #[must_use]
98 pub fn is_empty(&self) -> bool {
99 self.num_pieces == 0
100 }
101
102 #[must_use]
104 pub fn has(&self, i: usize) -> bool {
105 if i >= self.num_pieces {
106 return false;
107 }
108 self.bytes[i / 8] & (0x80 >> (i % 8)) != 0
109 }
110
111 pub fn set(&mut self, i: usize) {
113 if i < self.num_pieces {
114 self.bytes[i / 8] |= 0x80 >> (i % 8);
115 }
116 }
117
118 pub fn clear(&mut self, i: usize) {
120 if i < self.num_pieces {
121 self.bytes[i / 8] &= !(0x80 >> (i % 8));
122 }
123 }
124
125 #[must_use]
127 pub fn count(&self) -> usize {
128 self.bytes.iter().map(|b| b.count_ones() as usize).sum()
129 }
130
131 #[must_use]
133 pub fn is_complete(&self) -> bool {
134 self.count() == self.num_pieces
135 }
136
137 pub fn iter_set(&self) -> impl Iterator<Item = usize> + '_ {
139 (0..self.num_pieces).filter(move |&i| self.has(i))
140 }
141
142 pub fn iter_missing(&self) -> impl Iterator<Item = usize> + '_ {
144 (0..self.num_pieces).filter(move |&i| !self.has(i))
145 }
146
147 pub fn difference<'a>(&'a self, other: &'a Bitfield) -> impl Iterator<Item = usize> + 'a {
150 (0..self.num_pieces).filter(move |&i| self.has(i) && !other.has(i))
151 }
152}
153
154#[cfg(test)]
155mod tests {
156 use super::*;
157
158 #[test]
159 fn set_has_count_round_trip() {
160 let mut b = Bitfield::new(10);
161 assert_eq!(b.len(), 10);
162 assert_eq!(b.as_bytes().len(), 2); assert!(b.is_empty() == false);
164 b.set(0);
165 b.set(7);
166 b.set(9);
167 assert!(b.has(0) && b.has(7) && b.has(9));
168 assert!(!b.has(1) && !b.has(8));
169 assert_eq!(b.count(), 3);
170 assert_eq!(b.iter_set().collect::<Vec<_>>(), vec![0, 7, 9]);
171 assert_eq!(b.iter_missing().count(), 7);
172 assert!(!b.is_complete());
173 }
174
175 #[test]
176 fn msb_first_layout_matches_bep3() {
177 let mut b = Bitfield::new(8);
178 b.set(0); assert_eq!(b.as_bytes(), &[0x80]);
180 b.set(7); assert_eq!(b.as_bytes(), &[0x81]);
182 }
183
184 #[test]
185 fn from_bytes_validates_length_and_spare_bits() {
186 assert!(Bitfield::from_bytes(&[0xff, 0xc0], 10).is_ok()); assert_eq!(
189 Bitfield::from_bytes(&[0xff], 10),
190 Err(Error::WrongByteLength { got: 1, expected: 2 })
191 );
192 assert_eq!(
193 Bitfield::from_bytes(&[0xff, 0xff], 10), Err(Error::SpareBitsSet)
195 );
196 }
197
198 #[test]
199 fn complete_and_difference() {
200 let mut seed = Bitfield::new(4);
201 for i in 0..4 {
202 seed.set(i);
203 }
204 assert!(seed.is_complete());
205 let mut me = Bitfield::new(4);
206 me.set(1);
207 assert_eq!(seed.difference(&me).collect::<Vec<_>>(), vec![0, 2, 3]);
208 }
209
210 proptest::proptest! {
211 #[test]
213 fn wire_round_trip(num in 0usize..256, idxs in proptest::collection::vec(0usize..256, 0..40)) {
214 let mut b = Bitfield::new(num);
215 for i in idxs {
216 b.set(i % num.max(1));
217 }
218 let bytes = b.as_bytes().to_vec();
219 let parsed = Bitfield::from_bytes(&bytes, num).unwrap();
220 proptest::prop_assert_eq!(parsed, b);
221 }
222 }
223}