Skip to main content

enxame_bitfield/
lib.rs

1//! Typed BitTorrent piece bitfield ([BEP-3]).
2//!
3//! A [`Bitfield`] tracks which of a torrent's pieces a party holds. On
4//! the wire (the `bitfield` peer message) it is MSB-first: bit 0 is the
5//! high bit of byte 0, so piece `i` lives at byte `i / 8`, bit
6//! `7 - (i % 8)`. Spare trailing bits (when `num_pieces` isn't a
7//! multiple of 8) MUST be zero — a peer that sets them is misbehaving,
8//! and [`Bitfield::from_bytes`] rejects it.
9//!
10//! Part of the ENXAME suite (`theory/ENXAME.md`): the peer protocol
11//! sends/receives bitfields, the engine keeps one for "what we have" and
12//! folds peers' bitfields into a per-piece availability count for
13//! rarest-first selection. Pure + allocation-stable; the kind of generic
14//! BitTorrent bookkeeping the suite reuses everywhere.
15//!
16//! [BEP-3]: https://www.bittorrent.org/beps/bep_0003.html
17
18#![forbid(unsafe_code)]
19
20/// A fixed-length set of `num_pieces` bits, MSB-first per BEP-3.
21#[derive(Debug, Clone, PartialEq, Eq)]
22pub struct Bitfield {
23    bytes: Vec<u8>,
24    num_pieces: usize,
25}
26
27/// A typed bitfield decode failure.
28#[derive(Debug, Clone, PartialEq, Eq)]
29pub enum Error {
30    /// The byte length didn't match `ceil(num_pieces / 8)`.
31    WrongByteLength { got: usize, expected: usize },
32    /// A spare trailing bit (beyond `num_pieces`) was set — a protocol
33    /// violation.
34    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    /// An all-zero bitfield for `num_pieces` pieces (we have nothing).
56    #[must_use]
57    pub fn new(num_pieces: usize) -> Self {
58        Self { bytes: vec![0u8; byte_len(num_pieces)], num_pieces }
59    }
60
61    /// Decode a wire bitfield, validating the byte length and that no
62    /// spare trailing bits are set.
63    ///
64    /// # Errors
65    /// [`Error::WrongByteLength`] / [`Error::SpareBitsSet`].
66    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        // Validate spare bits in the final byte.
72        let spare = expected * 8 - num_pieces;
73        if spare > 0 {
74            if let Some(&last) = bytes.last() {
75                let mask = (1u8 << spare) - 1; // low `spare` bits
76                if last & mask != 0 {
77                    return Err(Error::SpareBitsSet);
78                }
79            }
80        }
81        Ok(Self { bytes: bytes.to_vec(), num_pieces })
82    }
83
84    /// The wire bytes (MSB-first, spare bits zero).
85    #[must_use]
86    pub fn as_bytes(&self) -> &[u8] {
87        &self.bytes
88    }
89
90    /// Number of pieces this bitfield covers.
91    #[must_use]
92    pub fn len(&self) -> usize {
93        self.num_pieces
94    }
95
96    /// True if it covers zero pieces.
97    #[must_use]
98    pub fn is_empty(&self) -> bool {
99        self.num_pieces == 0
100    }
101
102    /// Whether piece `i` is set. Out-of-range indices are `false`.
103    #[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    /// Set piece `i` (no-op if out of range).
112    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    /// Clear piece `i` (no-op if out of range).
119    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    /// How many pieces are set.
126    #[must_use]
127    pub fn count(&self) -> usize {
128        self.bytes.iter().map(|b| b.count_ones() as usize).sum()
129    }
130
131    /// Whether every piece is set (a seed).
132    #[must_use]
133    pub fn is_complete(&self) -> bool {
134        self.count() == self.num_pieces
135    }
136
137    /// Iterator over the indices of the set pieces.
138    pub fn iter_set(&self) -> impl Iterator<Item = usize> + '_ {
139        (0..self.num_pieces).filter(move |&i| self.has(i))
140    }
141
142    /// Iterator over the indices of the missing pieces.
143    pub fn iter_missing(&self) -> impl Iterator<Item = usize> + '_ {
144        (0..self.num_pieces).filter(move |&i| !self.has(i))
145    }
146
147    /// Pieces this bitfield has that `other` lacks — "what I can offer
148    /// you" / drives the `Interested` decision.
149    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); // ceil(10/8)
163        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); // high bit of byte 0
179        assert_eq!(b.as_bytes(), &[0x80]);
180        b.set(7); // low bit of byte 0
181        assert_eq!(b.as_bytes(), &[0x81]);
182    }
183
184    #[test]
185    fn from_bytes_validates_length_and_spare_bits() {
186        // 10 pieces → 2 bytes; spare = 6 low bits of byte 1 must be 0.
187        assert!(Bitfield::from_bytes(&[0xff, 0xc0], 10).is_ok()); // pieces 8,9 set, spare clear
188        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), // a spare bit set
194            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        /// from_bytes(to_bytes) is identity for any in-range set of bits.
212        #[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}