Skip to main content

scionic_merkletree/
wire.rs

1//! What a receiver asks, and the frames that answer it.
2//!
3//! A receiver asks from the top down: for the record of a root, for a folder's
4//! entries, for a file's list, and for chunks. It asks for chunks by the
5//! file's hash and their numbers in it, or for one chunk by its hash.
6//!
7//! An answer is one frame, or for chunks one frame for each chunk. A frame
8//! never says which hash it belongs under: the receiver works the hash out
9//! from the frame's bytes, and holds it against a hash it already trusts.
10//!
11//! A request and a frame each start with one byte that says what they are.
12//! Numbers are big-endian.
13
14use crate::format::{
15    check_name, FileBranch, FolderBranch, Reader, MAX_CHUNK_BYTES, MAX_NAME_BYTES, RECORD_MARK,
16};
17use crate::hash::{Hash, Root};
18use crate::tree::MAX_LIST_ITEMS;
19use crate::{Error, Result};
20use std::io::{ErrorKind, Read, Write};
21
22/// A tree's record. The frame is the record itself, whose first byte this is.
23pub const FRAME_RECORD: u8 = RECORD_MARK;
24/// A file's whole list.
25pub const FRAME_FILE_LIST: u8 = 0x21;
26/// A folder's whole list.
27pub const FRAME_FOLDER_LIST: u8 = 0x22;
28/// A branch of a file's list, with the nodes that stand for the rest.
29pub const FRAME_FILE_BRANCH: u8 = 0x23;
30/// A branch of a folder's list, with the nodes that stand for the rest.
31pub const FRAME_FOLDER_BRANCH: u8 = 0x24;
32/// A chunk's bytes.
33pub const FRAME_CHUNK: u8 = 0x25;
34/// Which chunks of a file a peer holds.
35pub const FRAME_HAVE: u8 = 0x26;
36/// The peer does not answer, and why.
37pub const FRAME_REFUSED: u8 = 0x27;
38
39const ASK_RECORD: u8 = 0x30;
40const ASK_FOLDER: u8 = 0x31;
41const ASK_FOLDER_BRANCH: u8 = 0x32;
42const ASK_FOLDER_NAME: u8 = 0x33;
43const ASK_FILE: u8 = 0x34;
44const ASK_FILE_BRANCH: u8 = 0x35;
45const ASK_FILE_BYTES: u8 = 0x36;
46const ASK_CHUNKS: u8 = 0x37;
47const ASK_CHUNK: u8 = 0x38;
48const ASK_HAVE: u8 = 0x39;
49
50/// What starts a bundle: a tree written out as one stream of frames.
51pub const BUNDLE_MAGIC: [u8; 8] = *b"SCIONIC\x01";
52
53/// The most bytes a request may take. The longest one asks for a name in a
54/// folder: its first byte, the folder's hash, and the longest name with its
55/// length.
56pub const MAX_REQUEST_BYTES: usize = 35 + MAX_NAME_BYTES;
57
58/// The most bytes that are set aside for a frame before they have come. A
59/// stream that claims a long frame and then sends nothing costs its reader
60/// no more than this.
61const READ_STEP_BYTES: usize = 1 << 20;
62
63fn invalid(detail: &str) -> Error {
64    Error::InvalidData {
65        detail: detail.to_owned(),
66    }
67}
68
69/// What a receiver asks a peer for.
70#[derive(Clone, Debug, Eq, PartialEq)]
71pub enum Request {
72    /// The record of a root.
73    Record(Root),
74    /// All of a folder's entries.
75    Folder(Hash),
76    /// `count` of a folder's entries, from place `start`.
77    FolderBranch {
78        folder: Hash,
79        start: u64,
80        count: u32,
81    },
82    /// What is under one name in a folder, or that the name is not there.
83    FolderName { folder: Hash, name: String },
84    /// All of a file's list.
85    File(Hash),
86    /// `count` items of a file's list, from chunk number `start`.
87    FileBranch { file: Hash, start: u64, count: u32 },
88    /// The items of a file's list that hold `length` bytes from `offset`.
89    FileBytes {
90        file: Hash,
91        offset: u64,
92        length: u64,
93    },
94    /// `count` chunks of a file, from chunk number `start`.
95    Chunks { file: Hash, start: u64, count: u32 },
96    /// One chunk, by its hash.
97    Chunk(Hash),
98    /// Which chunks of a file the peer holds.
99    Have(Hash),
100}
101
102impl Request {
103    pub fn encode(&self) -> Vec<u8> {
104        let mut out = Vec::with_capacity(49);
105        let ranged = |out: &mut Vec<u8>, tag: u8, hash: &Hash, start: u64, count: u32| {
106            out.push(tag);
107            out.extend_from_slice(hash.as_bytes());
108            out.extend_from_slice(&start.to_be_bytes());
109            out.extend_from_slice(&count.to_be_bytes());
110        };
111        let one = |out: &mut Vec<u8>, tag: u8, hash: &Hash| {
112            out.push(tag);
113            out.extend_from_slice(hash.as_bytes());
114        };
115        match self {
116            Self::Record(root) => one(&mut out, ASK_RECORD, root.as_hash()),
117            Self::Folder(folder) => one(&mut out, ASK_FOLDER, folder),
118            Self::FolderBranch {
119                folder,
120                start,
121                count,
122            } => ranged(&mut out, ASK_FOLDER_BRANCH, folder, *start, *count),
123            Self::FolderName { folder, name } => {
124                one(&mut out, ASK_FOLDER_NAME, folder);
125                out.extend_from_slice(&(name.len() as u16).to_be_bytes());
126                out.extend_from_slice(name.as_bytes());
127            }
128            Self::File(file) => one(&mut out, ASK_FILE, file),
129            Self::FileBranch { file, start, count } => {
130                ranged(&mut out, ASK_FILE_BRANCH, file, *start, *count);
131            }
132            Self::FileBytes {
133                file,
134                offset,
135                length,
136            } => {
137                one(&mut out, ASK_FILE_BYTES, file);
138                out.extend_from_slice(&offset.to_be_bytes());
139                out.extend_from_slice(&length.to_be_bytes());
140            }
141            Self::Chunks { file, start, count } => {
142                ranged(&mut out, ASK_CHUNKS, file, *start, *count);
143            }
144            Self::Chunk(chunk) => one(&mut out, ASK_CHUNK, chunk),
145            Self::Have(file) => one(&mut out, ASK_HAVE, file),
146        }
147        out
148    }
149
150    /// Reads a request. One that asks for nothing, or for a name that no
151    /// folder can hold, is refused here.
152    pub fn decode(bytes: &[u8]) -> Result<Self> {
153        let mut reader = Reader::new(bytes, "a request");
154        let tag = reader.u8()?;
155        let hash = reader.hash()?;
156        let request = match tag {
157            ASK_RECORD => Self::Record(Root::from_hash(hash)),
158            ASK_FOLDER => Self::Folder(hash),
159            ASK_FILE => Self::File(hash),
160            ASK_CHUNK => Self::Chunk(hash),
161            ASK_HAVE => Self::Have(hash),
162            ASK_FOLDER_BRANCH | ASK_FILE_BRANCH | ASK_CHUNKS => {
163                let start = reader.u64()?;
164                let count = reader.u32()?;
165                if count == 0 || start >= MAX_LIST_ITEMS {
166                    return Err(invalid("a request asks for nothing, or beyond any list"));
167                }
168                match tag {
169                    ASK_FOLDER_BRANCH => Self::FolderBranch {
170                        folder: hash,
171                        start,
172                        count,
173                    },
174                    ASK_FILE_BRANCH => Self::FileBranch {
175                        file: hash,
176                        start,
177                        count,
178                    },
179                    _ => Self::Chunks {
180                        file: hash,
181                        start,
182                        count,
183                    },
184                }
185            }
186            ASK_FOLDER_NAME => {
187                let length = usize::from(reader.u16()?);
188                let name = std::str::from_utf8(reader.take(length)?)
189                    .map_err(|_| invalid("a name is not UTF-8"))?;
190                check_name(name)?;
191                Self::FolderName {
192                    folder: hash,
193                    name: name.to_owned(),
194                }
195            }
196            ASK_FILE_BYTES => {
197                let offset = reader.u64()?;
198                let length = reader.u64()?;
199                if length == 0 || offset.checked_add(length).is_none() {
200                    return Err(invalid("a request asks for no bytes, or beyond any file"));
201                }
202                Self::FileBytes {
203                    file: hash,
204                    offset,
205                    length,
206                }
207            }
208            _ => return Err(invalid("a request of an unknown kind")),
209        };
210        reader.finish()?;
211        Ok(request)
212    }
213}
214
215/// Why a peer does not answer.
216#[derive(Clone, Copy, Debug, Eq, PartialEq)]
217pub enum Refusal {
218    /// It does not hold what was asked for.
219    NotHeld,
220    /// What was asked for lies outside the list or the file.
221    OutOfRange,
222}
223
224impl Refusal {
225    fn byte(self) -> u8 {
226        match self {
227            Self::NotHeld => 1,
228            Self::OutOfRange => 2,
229        }
230    }
231}
232
233/// Which chunks of a file a peer holds: one bit a chunk, in the file's
234/// order. A peer says this about itself, and nothing proves it.
235#[derive(Clone, Debug, Eq, PartialEq)]
236pub struct HaveMap {
237    count: u64,
238    bits: Vec<u8>,
239}
240
241impl HaveMap {
242    /// A map for a file of `count` chunks, with none held.
243    pub fn new(count: u64) -> Result<Self> {
244        if count > MAX_LIST_ITEMS {
245            return Err(invalid("a map for more chunks than a file can have"));
246        }
247        let length = count.div_ceil(8) as usize;
248        let mut bits = Vec::new();
249        bits.try_reserve_exact(length)
250            .map_err(|_| Error::AllocationFailed {
251                resource: "a map of held chunks",
252                requested: length as u64,
253            })?;
254        bits.resize(length, 0);
255        Ok(Self { count, bits })
256    }
257
258    /// How many chunks the file has.
259    pub fn count(&self) -> u64 {
260        self.count
261    }
262
263    /// Whether chunk `index` is held. A chunk beyond the count is not.
264    pub fn get(&self, index: u64) -> bool {
265        index < self.count && self.bits[(index / 8) as usize] & (0x80 >> (index % 8)) != 0
266    }
267
268    /// Marks chunk `index` as held.
269    pub fn set(&mut self, index: u64) -> Result<()> {
270        if index >= self.count {
271            return Err(invalid("a chunk beyond the end of the file"));
272        }
273        self.bits[(index / 8) as usize] |= 0x80 >> (index % 8);
274        Ok(())
275    }
276
277    /// How many chunks are held.
278    pub fn held(&self) -> u64 {
279        self.bits
280            .iter()
281            .map(|byte| u64::from(byte.count_ones()))
282            .sum()
283    }
284
285    pub fn encode(&self) -> Vec<u8> {
286        let mut out = Vec::with_capacity(8 + self.bits.len());
287        out.extend_from_slice(&self.count.to_be_bytes());
288        out.extend_from_slice(&self.bits);
289        out
290    }
291
292    /// Reads a map. It has one bit for each chunk and no more, and the bits
293    /// left over in its last byte are zero.
294    pub fn decode(bytes: &[u8]) -> Result<Self> {
295        let mut reader = Reader::new(bytes, "a map of held chunks");
296        let count = reader.u64()?;
297        if count > MAX_LIST_ITEMS || reader.remaining() as u64 != count.div_ceil(8) {
298            return Err(invalid("a map of held chunks does not fit its count"));
299        }
300        let bits = reader.take(reader.remaining())?.to_vec();
301        let spare = (8 - count % 8) % 8;
302        if bits
303            .last()
304            .is_some_and(|last| last & ((1_u8 << spare) - 1) != 0)
305        {
306            return Err(invalid("a map of held chunks has bits past its count"));
307        }
308        Ok(Self { count, bits })
309    }
310}
311
312/// A frame, read.
313#[derive(Clone, Debug, Eq, PartialEq)]
314pub enum Frame<'a> {
315    /// A record: the whole frame.
316    Record(&'a [u8]),
317    /// A file's whole list.
318    FileList(&'a [u8]),
319    /// A folder's whole list.
320    FolderList(&'a [u8]),
321    FileBranch(FileBranch),
322    FolderBranch(FolderBranch),
323    /// A chunk's bytes.
324    Chunk(&'a [u8]),
325    Have(HaveMap),
326    Refused(Refusal),
327}
328
329impl<'a> Frame<'a> {
330    /// Reads a frame. This says what kind of frame it is and that it is well
331    /// formed. It does not say that the frame is true: that is checked
332    /// against a hash the receiver trusts.
333    pub fn decode(bytes: &'a [u8]) -> Result<Self> {
334        let (&tag, body) = bytes
335            .split_first()
336            .ok_or_else(|| invalid("a frame is empty"))?;
337        Ok(match tag {
338            FRAME_RECORD => Self::Record(bytes),
339            FRAME_FILE_LIST => Self::FileList(body),
340            FRAME_FOLDER_LIST => Self::FolderList(body),
341            FRAME_FILE_BRANCH => Self::FileBranch(FileBranch::decode(body)?),
342            FRAME_FOLDER_BRANCH => Self::FolderBranch(FolderBranch::decode(body)?),
343            FRAME_CHUNK => {
344                if body.is_empty() || body.len() > MAX_CHUNK_BYTES {
345                    return Err(invalid("a chunk does not hold 1 byte to 8 MiB"));
346                }
347                Self::Chunk(body)
348            }
349            FRAME_HAVE => Self::Have(HaveMap::decode(body)?),
350            FRAME_REFUSED => match body {
351                [1] => Self::Refused(Refusal::NotHeld),
352                [2] => Self::Refused(Refusal::OutOfRange),
353                _ => return Err(invalid("a refusal of an unknown kind")),
354            },
355            _ => return Err(invalid("a frame of an unknown kind")),
356        })
357    }
358}
359
360fn framed(tag: u8, body: &[u8]) -> Vec<u8> {
361    let mut frame = Vec::with_capacity(1 + body.len());
362    frame.push(tag);
363    frame.extend_from_slice(body);
364    frame
365}
366
367/// The frame for a file's whole list.
368pub fn file_list_frame(list: &[u8]) -> Vec<u8> {
369    framed(FRAME_FILE_LIST, list)
370}
371
372/// The frame for a folder's whole list.
373pub fn folder_list_frame(list: &[u8]) -> Vec<u8> {
374    framed(FRAME_FOLDER_LIST, list)
375}
376
377pub fn file_branch_frame(branch: &FileBranch) -> Vec<u8> {
378    framed(FRAME_FILE_BRANCH, &branch.encode())
379}
380
381pub fn folder_branch_frame(branch: &FolderBranch) -> Vec<u8> {
382    framed(FRAME_FOLDER_BRANCH, &branch.encode())
383}
384
385/// The frame for a chunk's bytes.
386pub fn chunk_frame(chunk: &[u8]) -> Vec<u8> {
387    framed(FRAME_CHUNK, chunk)
388}
389
390pub fn have_frame(map: &HaveMap) -> Vec<u8> {
391    framed(FRAME_HAVE, &map.encode())
392}
393
394pub fn refused_frame(why: Refusal) -> Vec<u8> {
395    vec![FRAME_REFUSED, why.byte()]
396}
397
398/// Writes one frame to a stream: its length as four bytes, then the frame.
399pub fn write_frame(out: &mut dyn Write, frame: &[u8]) -> Result<()> {
400    let length = u32::try_from(frame.len()).map_err(|_| Error::LimitExceeded {
401        what: "a frame",
402        limit: u64::from(u32::MAX),
403        requested: frame.len() as u64,
404    })?;
405    let failed = |source| Error::Stream {
406        operation: "write a frame",
407        source,
408    };
409    out.write_all(&length.to_be_bytes()).map_err(failed)?;
410    out.write_all(frame).map_err(failed)
411}
412
413/// Writes the frame that `tag` and `body` make, without making it: the body
414/// of a chunk's frame is megabytes long, and is written from where it is.
415pub(crate) fn write_framed(out: &mut dyn Write, tag: u8, body: &[u8]) -> Result<()> {
416    let length = u32::try_from(body.len() + 1).map_err(|_| Error::LimitExceeded {
417        what: "a frame",
418        limit: u64::from(u32::MAX),
419        requested: body.len() as u64 + 1,
420    })?;
421    let failed = |source| Error::Stream {
422        operation: "write a frame",
423        source,
424    };
425    let mut head = [0; 5];
426    head[..4].copy_from_slice(&length.to_be_bytes());
427    head[4] = tag;
428    out.write_all(&head).map_err(failed)?;
429    out.write_all(body).map_err(failed)
430}
431
432/// What comes next on a stream of frames.
433pub(crate) enum Next {
434    /// A frame, which is in the buffer that was given to read it into.
435    Frame,
436    /// A length of zero. Where answers are sent, it ends one answer.
437    End,
438    /// The stream has ended, between two frames.
439    Closed,
440}
441
442/// Writes a length of zero to a stream: the end of an answer.
443pub(crate) fn write_end(out: &mut dyn Write) -> Result<()> {
444    out.write_all(&[0; 4]).map_err(|source| Error::Stream {
445        operation: "write a frame",
446        source,
447    })
448}
449
450/// Reads what comes next on a stream, a frame into `frame`, which is emptied
451/// first. One buffer serves frame after frame, so that memory is not taken
452/// afresh for each: memory that is used again costs much less than fresh
453/// memory, which a system has to find and clear first.
454///
455/// A frame longer than `limit` is refused before any of it is read, and a
456/// stream that ends inside a frame is an error. A frame's bytes are set aside
457/// as they come, a megabyte at a time, so that what a peer only says it will
458/// send costs nothing until it is sent.
459pub(crate) fn read_next(input: &mut dyn Read, limit: usize, frame: &mut Vec<u8>) -> Result<Next> {
460    frame.clear();
461    read_next_onto(input, limit, frame)
462}
463
464/// Reads what comes next on a stream as [`read_next`] does, and adds a frame
465/// to the end of `frames`, after what they hold already. Nothing is added
466/// unless a whole frame is.
467pub(crate) fn read_next_onto(
468    input: &mut dyn Read,
469    limit: usize,
470    frames: &mut Vec<u8>,
471) -> Result<Next> {
472    let start = frames.len();
473    let next = read_onto(input, limit, frames, start);
474    if !matches!(next, Ok(Next::Frame)) {
475        frames.truncate(start);
476    }
477    next
478}
479
480/// Reads what comes next on a stream, a frame into `frames` from `start` on.
481fn read_onto(
482    input: &mut dyn Read,
483    limit: usize,
484    frames: &mut Vec<u8>,
485    start: usize,
486) -> Result<Next> {
487    let failed = |source| Error::Stream {
488        operation: "read a frame",
489        source,
490    };
491    let cut_short = |error: std::io::Error| {
492        if error.kind() == ErrorKind::UnexpectedEof {
493            invalid("a stream ends inside a frame")
494        } else {
495            failed(error)
496        }
497    };
498    let mut header = [0_u8; 4];
499    let mut filled = 0;
500    while filled < header.len() {
501        match input.read(&mut header[filled..]) {
502            Ok(0) if filled == 0 => return Ok(Next::Closed),
503            Ok(0) => return Err(invalid("a stream ends inside a frame")),
504            Ok(count) => filled += count,
505            Err(error) if error.kind() == ErrorKind::Interrupted => {}
506            Err(error) => return Err(failed(error)),
507        }
508    }
509    let length = u32::from_be_bytes(header) as usize;
510    if length == 0 {
511        return Ok(Next::End);
512    }
513    if length > limit {
514        return Err(Error::LimitExceeded {
515            what: "a frame",
516            limit: limit as u64,
517            requested: length as u64,
518        });
519    }
520    let end = start.checked_add(length).ok_or(Error::AllocationFailed {
521        resource: "a frame",
522        requested: length as u64,
523    })?;
524    while frames.len() < end {
525        let held = frames.len();
526        let more = (end - held).min(READ_STEP_BYTES);
527        frames
528            .try_reserve(more)
529            .map_err(|_| Error::AllocationFailed {
530                resource: "a frame",
531                requested: length as u64,
532            })?;
533        frames.resize(held + more, 0);
534        input.read_exact(&mut frames[held..]).map_err(cut_short)?;
535    }
536    Ok(Next::Frame)
537}
538
539/// Reads one frame from a stream, or nothing when the stream has ended. A
540/// frame longer than `limit` is refused before any of it is read, and a
541/// stream that ends inside a frame is an error.
542pub fn read_frame(input: &mut dyn Read, limit: usize) -> Result<Option<Vec<u8>>> {
543    let mut frame = Vec::new();
544    match read_next(input, limit, &mut frame)? {
545        Next::Frame => Ok(Some(frame)),
546        Next::End => Err(invalid("a frame is empty")),
547        Next::Closed => Ok(None),
548    }
549}
550
551#[cfg(test)]
552mod tests {
553    use super::*;
554
555    fn every_request() -> Vec<Request> {
556        let hash = Hash::of(b"x");
557        vec![
558            Request::Record(Root::from_hash(hash)),
559            Request::Folder(hash),
560            Request::FolderBranch {
561                folder: hash,
562                start: 3,
563                count: 9,
564            },
565            Request::FolderName {
566                folder: hash,
567                name: "model.safetensors".to_owned(),
568            },
569            Request::File(hash),
570            Request::FileBranch {
571                file: hash,
572                start: 100,
573                count: 100,
574            },
575            Request::FileBytes {
576                file: hash,
577                offset: 500 << 30,
578                length: 1 << 30,
579            },
580            Request::Chunks {
581                file: hash,
582                start: 100,
583                count: 101,
584            },
585            Request::Chunk(hash),
586            Request::Have(hash),
587        ]
588    }
589
590    #[test]
591    fn every_request_reads_back_and_is_read_in_one_way_only() {
592        for request in every_request() {
593            let bytes = request.encode();
594            assert_eq!(Request::decode(&bytes).unwrap(), request);
595            for cut in 0..bytes.len() {
596                assert!(
597                    Request::decode(&bytes[..cut]).is_err(),
598                    "{request:?} cut at {cut}"
599                );
600            }
601            assert!(Request::decode(&[bytes.clone(), vec![0]].concat()).is_err());
602        }
603        let mut tags: Vec<u8> = every_request()
604            .iter()
605            .map(|request| request.encode()[0])
606            .collect();
607        tags.dedup();
608        assert_eq!(tags, (0x30..=0x39).collect::<Vec<u8>>());
609        // "Chunks 100 to 200 of this file" is 45 bytes, whatever the file.
610        assert_eq!(every_request()[7].encode().len(), 45);
611    }
612
613    #[test]
614    fn a_request_for_nothing_or_for_a_name_no_folder_holds_is_refused() {
615        let hash = Hash::of(b"x");
616        let ranged = |tag: u8, start: u64, count: u32| {
617            let mut bytes = vec![tag];
618            bytes.extend_from_slice(hash.as_bytes());
619            bytes.extend_from_slice(&start.to_be_bytes());
620            bytes.extend_from_slice(&count.to_be_bytes());
621            Request::decode(&bytes)
622        };
623        for tag in [0x32, 0x35, 0x37] {
624            assert!(ranged(tag, 0, 1).is_ok());
625            assert!(ranged(tag, 0, 0).is_err());
626            assert!(ranged(tag, MAX_LIST_ITEMS, 1).is_err());
627        }
628        let named = |name: &[u8]| {
629            let mut bytes = vec![0x33];
630            bytes.extend_from_slice(hash.as_bytes());
631            bytes.extend_from_slice(&(name.len() as u16).to_be_bytes());
632            bytes.extend_from_slice(name);
633            Request::decode(&bytes)
634        };
635        assert!(named(b"a").is_ok());
636        for name in [&b""[..], b".", b"..", b"a/b", b"a\0", &[0xff]] {
637            assert!(named(name).is_err(), "{name:?}");
638        }
639        let stretch = |offset: u64, length: u64| {
640            let mut bytes = vec![0x36];
641            bytes.extend_from_slice(hash.as_bytes());
642            bytes.extend_from_slice(&offset.to_be_bytes());
643            bytes.extend_from_slice(&length.to_be_bytes());
644            Request::decode(&bytes)
645        };
646        assert!(stretch(0, 1).is_ok());
647        assert!(stretch(0, 0).is_err());
648        assert!(stretch(u64::MAX, 1).is_err());
649        let mut unknown = vec![0x3a];
650        unknown.extend_from_slice(hash.as_bytes());
651        assert!(Request::decode(&unknown).is_err());
652    }
653
654    #[test]
655    fn a_map_of_held_chunks_has_one_bit_a_chunk() {
656        let mut map = HaveMap::new(11).unwrap();
657        assert_eq!(map.encode().len(), 8 + 2);
658        for index in [0, 3, 10] {
659            map.set(index).unwrap();
660        }
661        assert!(map.set(11).is_err());
662        assert_eq!(map.held(), 3);
663        let held: Vec<u64> = (0..16).filter(|index| map.get(*index)).collect();
664        assert_eq!(held, [0, 3, 10]);
665        let bytes = map.encode();
666        assert_eq!(&bytes[8..], [0b1001_0000, 0b0010_0000]);
667        assert_eq!(HaveMap::decode(&bytes).unwrap(), map);
668
669        // A bit past the count, a byte too many and a byte too few.
670        let mut past = bytes.clone();
671        past[9] |= 0b0001_0000;
672        assert!(HaveMap::decode(&past).is_err());
673        assert!(HaveMap::decode(&[bytes.clone(), vec![0]].concat()).is_err());
674        assert!(HaveMap::decode(&bytes[..9]).is_err());
675        // A terabyte file's map is about 60 KB.
676        let big = HaveMap::new(500_000).unwrap();
677        assert_eq!(big.encode().len(), 8 + 62_500);
678        assert_eq!(
679            HaveMap::decode(&HaveMap::new(0).unwrap().encode())
680                .unwrap()
681                .count(),
682            0
683        );
684        assert_eq!(
685            HaveMap::decode(&HaveMap::new(8).unwrap().encode())
686                .unwrap()
687                .count(),
688            8
689        );
690    }
691
692    #[test]
693    fn frames_are_told_apart_by_their_first_byte() {
694        assert_eq!(
695            Frame::decode(&chunk_frame(b"abc")).unwrap(),
696            Frame::Chunk(b"abc")
697        );
698        assert_eq!(
699            Frame::decode(&file_list_frame(&[7; 36])).unwrap(),
700            Frame::FileList(&[7; 36])
701        );
702        assert_eq!(
703            Frame::decode(&folder_list_frame(&[])).unwrap(),
704            Frame::FolderList(&[])
705        );
706        assert_eq!(
707            Frame::decode(&refused_frame(Refusal::NotHeld)).unwrap(),
708            Frame::Refused(Refusal::NotHeld)
709        );
710        assert_eq!(
711            Frame::decode(&refused_frame(Refusal::OutOfRange)).unwrap(),
712            Frame::Refused(Refusal::OutOfRange)
713        );
714        let map = HaveMap::new(3).unwrap();
715        assert_eq!(Frame::decode(&have_frame(&map)).unwrap(), Frame::Have(map));
716        assert_eq!(
717            Frame::decode(&[0x20, 1]).unwrap(),
718            Frame::Record(&[0x20, 1])
719        );
720        for bad in [
721            &[][..],
722            &[0x25],
723            &[0x27],
724            &[0x27, 0],
725            &[0x27, 3],
726            &[0x27, 1, 1],
727            &[0x28],
728            &[0x1f],
729        ] {
730            assert!(Frame::decode(bad).is_err(), "{bad:?}");
731        }
732        let too_long = chunk_frame(&vec![0; MAX_CHUNK_BYTES + 1]);
733        assert!(Frame::decode(&too_long).is_err());
734        assert!(Frame::decode(&chunk_frame(&vec![0; MAX_CHUNK_BYTES])).is_ok());
735    }
736
737    #[test]
738    fn frames_go_through_a_stream_whole_or_not_at_all() {
739        let mut stream = Vec::new();
740        write_frame(&mut stream, b"one").unwrap();
741        write_frame(&mut stream, b"three").unwrap();
742        let mut input = stream.as_slice();
743        assert_eq!(read_frame(&mut input, 16).unwrap().unwrap(), b"one");
744        assert_eq!(read_frame(&mut input, 16).unwrap().unwrap(), b"three");
745        assert!(read_frame(&mut input, 16).unwrap().is_none());
746
747        // A frame over the limit is refused before it is read.
748        let mut input = stream.as_slice();
749        assert!(matches!(
750            read_frame(&mut input, 2),
751            Err(Error::LimitExceeded { .. })
752        ));
753        // A stream that ends inside a length or inside a frame.
754        for cut in [1, 3, 5, 6] {
755            let mut input = &stream[..cut];
756            assert!(read_frame(&mut input, 16).is_err(), "cut at {cut}");
757        }
758        let mut empty = &[0_u8, 0, 0, 0][..];
759        assert!(read_frame(&mut empty, 16).is_err());
760    }
761}