Skip to main content

kermit_proto/
codec.rs

1//! Packet framing: character transforms, block checks, packet encoding and the
2//! byte-stream deframer.
3
4/// Start-of-header byte that begins every packet.
5pub const SOH: u8 = 0x01;
6/// Carriage return, the default end-of-line byte.
7pub const CR: u8 = 0x0D;
8/// Largest LEN value a (short) packet can carry: `tochar(94)` is `~`.
9pub const MAX_LEN: usize = 94;
10
11/// Turn a small number (0..=94) into a printable character.
12pub const fn tochar(x: u8) -> u8 {
13    x.wrapping_add(32)
14}
15
16/// Inverse of [`tochar`].
17pub const fn unchar(x: u8) -> u8 {
18    x.wrapping_sub(32)
19}
20
21/// Toggle bit 6, mapping control characters to printable ones and back.
22pub const fn ctl(x: u8) -> u8 {
23    x ^ 64
24}
25
26/// Block check type.
27#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
28#[non_exhaustive]
29pub enum BlockCheck {
30    /// Single-character arithmetic checksum.
31    Type1,
32    /// Two-character 12-bit checksum.
33    Type2,
34    /// Three-character CRC-16/KERMIT.
35    #[default]
36    Type3,
37}
38
39impl BlockCheck {
40    /// Number of check characters on the wire (1, 2 or 3).
41    #[allow(clippy::len_without_is_empty)]
42    pub fn len(self) -> usize {
43        match self {
44            BlockCheck::Type1 => 1,
45            BlockCheck::Type2 => 2,
46            BlockCheck::Type3 => 3,
47        }
48    }
49
50    /// Parse the CHKT Send-Init field (`b'1'`, `b'2'`, `b'3'`).
51    pub fn from_char(c: u8) -> Option<Self> {
52        match c {
53            b'1' => Some(BlockCheck::Type1),
54            b'2' => Some(BlockCheck::Type2),
55            b'3' => Some(BlockCheck::Type3),
56            _ => None,
57        }
58    }
59
60    /// The CHKT Send-Init field for this check type.
61    pub fn to_char(self) -> u8 {
62        match self {
63            BlockCheck::Type1 => b'1',
64            BlockCheck::Type2 => b'2',
65            BlockCheck::Type3 => b'3',
66        }
67    }
68
69    /// Compute the check characters over `body` (LEN through the end of DATA).
70    pub fn compute(self, body: &[u8]) -> Vec<u8> {
71        match self {
72            BlockCheck::Type1 => {
73                let s: u32 = body.iter().map(|&b| u32::from(b)).sum();
74                vec![tochar(((s + ((s & 192) >> 6)) & 63) as u8)]
75            }
76            BlockCheck::Type2 => {
77                let s: u32 = body.iter().map(|&b| u32::from(b)).sum::<u32>() & 0xFFF;
78                vec![tochar(((s >> 6) & 63) as u8), tochar((s & 63) as u8)]
79            }
80            BlockCheck::Type3 => {
81                let crc = crc16(body);
82                vec![
83                    tochar(((crc >> 12) & 15) as u8),
84                    tochar(((crc >> 6) & 63) as u8),
85                    tochar((crc & 63) as u8),
86                ]
87            }
88        }
89    }
90}
91
92/// CRC-16/KERMIT (init 0) as used by the type 3 block check.
93pub fn crc16(body: &[u8]) -> u16 {
94    let mut crc: u16 = 0;
95    for &b in body {
96        let b = u16::from(b);
97        crc = (crc >> 4) ^ (((crc ^ b) & 15) * 0x1081);
98        crc = (crc >> 4) ^ (((crc ^ (b >> 4)) & 15) * 0x1081);
99    }
100    crc
101}
102
103/// One packet; `data` is the already prefix-encoded data field.
104#[derive(Clone, Debug, PartialEq, Eq)]
105pub struct Packet {
106    /// Sequence number, 0..=63.
107    pub seq: u8,
108    /// Packet type, e.g. `b'D'`.
109    pub kind: u8,
110    /// Encoded data field.
111    pub data: Vec<u8>,
112}
113
114impl Packet {
115    /// Build a packet; `seq` is stored modulo 64.
116    pub fn new(seq: u8, kind: u8, data: Vec<u8>) -> Self {
117        Packet {
118            seq: seq % 64,
119            kind,
120            data,
121        }
122    }
123
124    /// Longest data field that fits in a packet whose LEN may be at most
125    /// `maxl` (capped at [`MAX_LEN`]) with block check `check`.
126    pub fn max_data(maxl: usize, check: BlockCheck) -> usize {
127        maxl.min(MAX_LEN).saturating_sub(2 + check.len())
128    }
129
130    /// NPAD x PADC, SOH, LEN, SEQ, TYPE, DATA, CHECK, EOL.
131    ///
132    /// Fails if the data field does not fit in a (short) packet:
133    /// `data.len()` must be at most `Packet::max_data(MAX_LEN, check)`.
134    pub fn encode(&self, check: BlockCheck, framing: &Framing) -> Result<Vec<u8>, EncodeError> {
135        let max = Packet::max_data(MAX_LEN, check);
136        if self.data.len() > max {
137            return Err(EncodeError {
138                len: self.data.len(),
139                max,
140            });
141        }
142        Ok(self.wire(check, framing))
143    }
144
145    /// [`Packet::encode`] for data the caller has already fitted (the
146    /// client sizes every data field with [`Packet::max_data`]). Should the
147    /// invariant break, LEN saturates at `~` rather than wrapping into a
148    /// different, valid-looking length.
149    pub(crate) fn wire(&self, check: BlockCheck, framing: &Framing) -> Vec<u8> {
150        let len = 2 + self.data.len() + check.len();
151        debug_assert!(
152            len <= MAX_LEN,
153            "packet data too long: LEN {len} exceeds {MAX_LEN}"
154        );
155        let len_char = u8::try_from(len.min(MAX_LEN)).map_or(tochar(94), tochar);
156        let mut out = Vec::with_capacity(usize::from(framing.npad) + len + 3);
157        out.extend(std::iter::repeat_n(framing.padc, usize::from(framing.npad)));
158        out.push(SOH);
159        let body_start = out.len();
160        out.push(len_char);
161        out.push(tochar(self.seq % 64));
162        out.push(self.kind);
163        out.extend_from_slice(&self.data);
164        let chk = check.compute(&out[body_start..]);
165        out.extend_from_slice(&chk);
166        out.push(framing.eol);
167        out
168    }
169}
170
171/// [`Packet::encode`] was given a data field that does not fit in a packet.
172#[derive(Clone, Copy, Debug, PartialEq, Eq)]
173pub struct EncodeError {
174    /// Length of the data field.
175    pub len: usize,
176    /// Longest data field that fits with the block check used.
177    pub max: usize,
178}
179
180impl std::fmt::Display for EncodeError {
181    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
182        write!(
183            f,
184            "packet data too long: {} bytes, at most {} fit",
185            self.len, self.max
186        )
187    }
188}
189
190impl std::error::Error for EncodeError {}
191
192/// What the peer asked us to put around each packet.
193#[derive(Clone, Copy, Debug, PartialEq, Eq)]
194pub struct Framing {
195    /// Number of pad bytes before each packet.
196    pub npad: u8,
197    /// The pad byte.
198    pub padc: u8,
199    /// End-of-line byte after each packet.
200    pub eol: u8,
201}
202
203impl Default for Framing {
204    fn default() -> Self {
205        Framing {
206            npad: 0,
207            padc: 0,
208            eol: CR,
209        }
210    }
211}
212
213/// Reasons a frame is rejected by [`parse_frame`].
214#[derive(Clone, Copy, Debug, PartialEq, Eq)]
215#[non_exhaustive]
216pub enum FrameError {
217    /// LEN out of range or inconsistent with the frame size.
218    BadLength,
219    /// The block check does not match.
220    BadCheck,
221}
222
223/// Accumulates raw input bytes and splits out complete frames.
224#[derive(Debug, Default)]
225pub struct Deframer {
226    buf: Vec<u8>,
227}
228
229impl Deframer {
230    /// Empty deframer.
231    pub fn new() -> Self {
232        Self::default()
233    }
234
235    /// Append received bytes.
236    pub fn push(&mut self, bytes: &[u8]) {
237        self.buf.extend_from_slice(bytes);
238    }
239
240    /// Next complete frame: from SOH through the last CHECK byte (EOL and anything
241    /// between frames is dropped). Rules: discard bytes before the first SOH; if
242    /// unchar(LEN) is < 3 or > 94, drop that SOH and rescan; if another SOH appears
243    /// before the frame is complete, restart at the new SOH (all control chars are
244    /// prefixed, so a bare SOH always starts a packet). Returns None if incomplete.
245    ///
246    /// Linear in the buffered input: the scan moves a cursor and the buffer is
247    /// shifted once per call, so a long run of SOH bytes costs no more than
248    /// any other noise.
249    pub fn next_frame(&mut self) -> Option<Vec<u8>> {
250        let mut from = 0;
251        loop {
252            let Some(s) = self
253                .buf
254                .get(from..)
255                .and_then(|rest| rest.iter().position(|&b| b == SOH))
256                .map(|i| from + i)
257            else {
258                self.buf.clear();
259                return None;
260            };
261            let Some(&len_byte) = self.buf.get(s + 1) else {
262                self.buf.drain(..s);
263                return None;
264            };
265            let len = usize::from(unchar(len_byte));
266            if !(3..=94).contains(&len) {
267                from = s + 1;
268                continue;
269            }
270            let total = 2 + len;
271            let end = (s + total).min(self.buf.len());
272            if let Some(j) = self.buf[s + 1..end].iter().position(|&b| b == SOH) {
273                from = s + 1 + j;
274                continue;
275            }
276            if self.buf.len() < s + total {
277                self.buf.drain(..s);
278                return None;
279            }
280            let frame = self.buf[s..s + total].to_vec();
281            self.buf.drain(..s + total);
282            return Some(frame);
283        }
284    }
285
286    /// Drop all buffered input.
287    pub fn clear(&mut self) {
288        self.buf.clear();
289    }
290}
291
292/// Verify the check and split a frame from [`Deframer::next_frame`].
293/// `check` is used except for kind b'N': a NAK has no data, so its check length is
294/// unchar(LEN) - 2 (Kermit manual p. 30) when that is 1..=3.
295pub fn parse_frame(frame: &[u8], check: BlockCheck) -> Result<Packet, FrameError> {
296    if frame.len() < 5 || frame[0] != SOH {
297        return Err(FrameError::BadLength);
298    }
299    let len = usize::from(unchar(frame[1]));
300    if !(3..=94).contains(&len) || frame.len() != 2 + len {
301        return Err(FrameError::BadLength);
302    }
303    let kind = frame[3];
304    let check = if kind == b'N' {
305        match len - 2 {
306            1 => BlockCheck::Type1,
307            2 => BlockCheck::Type2,
308            3 => BlockCheck::Type3,
309            _ => check,
310        }
311    } else {
312        check
313    };
314    let cl = check.len();
315    if len < 2 + cl {
316        return Err(FrameError::BadLength);
317    }
318    let split = frame.len() - cl;
319    if check.compute(&frame[1..split]) != frame[split..] {
320        return Err(FrameError::BadCheck);
321    }
322    Ok(Packet::new(
323        unchar(frame[2]),
324        kind,
325        frame[4..split].to_vec(),
326    ))
327}
328
329#[cfg(test)]
330#[allow(clippy::unwrap_used, clippy::expect_used)]
331mod tests {
332    use super::*;
333
334    /// (wire bytes incl. CR, seq, kind, data)
335    const VECTORS: &[(&[u8], u8, u8, &[u8])] = &[
336        (b"\x01, I~* @-#Y3~Z\r", 0, b'I', b"~* @-#Y3~"),
337        (b"\x01+ Y~& @-# 3,\r", 0, b'Y', b"~& @-# 3"),
338        (b"\x01( C6 7 *C\r", 0, b'C', b"6 7 *"),
339        (b"\x01+ S~* @-#Y3$\r", 0, b'S', b"~* @-#Y3"),
340        (b"\x01# N3\r", 0, b'N', b""),
341        (b"\x01#!X>\r", 1, b'X', b""),
342        (b"\x01#!Y?\r", 1, b'Y', b""),
343        (
344            b"\x01?\"D1:                    42#M#J6\r",
345            2,
346            b'D',
347            b"1:                    42#M#J",
348        ),
349    ];
350
351    #[test]
352    fn char_transforms() {
353        assert_eq!(tochar(0), b' ');
354        assert_eq!(tochar(94), b'~');
355        assert_eq!(unchar(b'~'), 94);
356        assert_eq!(unchar(tochar(17)), 17);
357        assert_eq!(ctl(0), b'@');
358        assert_eq!(ctl(b'M'), CR);
359        assert_eq!(ctl(0x7F), b'?');
360    }
361
362    #[test]
363    fn crc_vector() {
364        assert_eq!(crc16(b"123456789"), 0x2189);
365        assert_eq!(crc16(b""), 0);
366    }
367
368    #[test]
369    fn check_types() {
370        assert_eq!(BlockCheck::Type1.compute(b"# N"), b"3");
371        let s: u32 = b"abc".iter().map(|&b| u32::from(b)).sum();
372        assert_eq!(
373            BlockCheck::Type2.compute(b"abc"),
374            vec![tochar(((s >> 6) & 63) as u8), tochar((s & 63) as u8)]
375        );
376        let c = crc16(b"123456789");
377        assert_eq!(
378            BlockCheck::Type3.compute(b"123456789"),
379            vec![
380                tochar((c >> 12) as u8 & 15),
381                tochar((c >> 6) as u8 & 63),
382                tochar(c as u8 & 63)
383            ]
384        );
385        for t in [BlockCheck::Type1, BlockCheck::Type2, BlockCheck::Type3] {
386            assert_eq!(BlockCheck::from_char(t.to_char()), Some(t));
387            assert_eq!(t.compute(b"xyz").len(), t.len());
388        }
389        assert_eq!(BlockCheck::from_char(b'4'), None);
390        assert_eq!(BlockCheck::default(), BlockCheck::Type3);
391    }
392
393    #[test]
394    fn wire_vectors_round_trip() {
395        for &(wire, seq, kind, data) in VECTORS {
396            let frame = &wire[..wire.len() - 1];
397            let p = parse_frame(frame, BlockCheck::Type1).unwrap();
398            assert_eq!(p, Packet::new(seq, kind, data.to_vec()), "{wire:?}");
399            assert_eq!(
400                p.encode(BlockCheck::Type1, &Framing::default()),
401                Ok(wire.to_vec())
402            );
403        }
404    }
405
406    #[test]
407    fn type2_type3_round_trip() {
408        let p = Packet::new(70, b'D', b"hello #M#J world".to_vec());
409        assert_eq!(p.seq, 6);
410        for t in [BlockCheck::Type1, BlockCheck::Type2, BlockCheck::Type3] {
411            let wire = p.encode(t, &Framing::default()).unwrap();
412            let frame = &wire[..wire.len() - 1];
413            assert_eq!(parse_frame(frame, t).unwrap(), p);
414        }
415    }
416
417    #[test]
418    fn max_data_and_longest_packet() {
419        assert_eq!(Packet::max_data(80, BlockCheck::Type1), 77);
420        assert_eq!(Packet::max_data(94, BlockCheck::Type3), 89);
421        assert_eq!(Packet::max_data(200, BlockCheck::Type3), 89);
422        assert_eq!(Packet::max_data(3, BlockCheck::Type3), 0);
423        let p = Packet::new(0, b'D', vec![b'x'; 89]);
424        let wire = p.encode(BlockCheck::Type3, &Framing::default()).unwrap();
425        assert_eq!(wire[1], b'~');
426        let frame = &wire[..wire.len() - 1];
427        assert_eq!(parse_frame(frame, BlockCheck::Type3).unwrap(), p);
428    }
429
430    #[test]
431    fn oversized_packet_is_an_error() {
432        let p = Packet::new(0, b'D', vec![b'x'; 90]);
433        let err = p.encode(BlockCheck::Type3, &Framing::default());
434        assert_eq!(err, Err(EncodeError { len: 90, max: 89 }));
435        let p = Packet::new(0, b'D', vec![b'x'; 91]);
436        assert!(p.encode(BlockCheck::Type1, &Framing::default()).is_ok());
437        let p = Packet::new(0, b'D', vec![b'x'; 92]);
438        assert!(p.encode(BlockCheck::Type1, &Framing::default()).is_err());
439    }
440
441    #[test]
442    fn padding_and_eol() {
443        let f = Framing {
444            npad: 2,
445            padc: 0,
446            eol: b'\n',
447        };
448        let wire = Packet::new(1, b'Y', vec![])
449            .encode(BlockCheck::Type1, &f)
450            .unwrap();
451        assert_eq!(wire, b"\0\0\x01#!Y?\n");
452    }
453
454    #[test]
455    fn bad_check_detected() {
456        let wire = Packet::new(3, b'D', b"abcdef".to_vec())
457            .encode(BlockCheck::Type3, &Framing::default())
458            .unwrap();
459        let mut frame = wire[..wire.len() - 1].to_vec();
460        frame[6] ^= 1;
461        assert_eq!(
462            parse_frame(&frame, BlockCheck::Type3),
463            Err(FrameError::BadCheck)
464        );
465    }
466
467    #[test]
468    fn bad_length() {
469        assert_eq!(
470            parse_frame(b"\x01$ Y?", BlockCheck::Type1),
471            Err(FrameError::BadLength)
472        );
473        assert_eq!(
474            parse_frame(b"\x01\" Y?", BlockCheck::Type1),
475            Err(FrameError::BadLength)
476        );
477        // LEN 3 with a type 3 check leaves no room.
478        assert_eq!(
479            parse_frame(b"\x01# Y?", BlockCheck::Type3),
480            Err(FrameError::BadLength)
481        );
482    }
483
484    #[test]
485    fn nak_check_length_heuristic() {
486        let nak = Packet::new(5, b'N', vec![]);
487        for t in [BlockCheck::Type1, BlockCheck::Type2, BlockCheck::Type3] {
488            let wire = nak.encode(t, &Framing::default()).unwrap();
489            let frame = &wire[..wire.len() - 1];
490            assert_eq!(parse_frame(frame, BlockCheck::Type1).unwrap(), nak);
491            assert_eq!(parse_frame(frame, BlockCheck::Type3).unwrap(), nak);
492        }
493    }
494
495    fn drain(d: &mut Deframer) -> Vec<Vec<u8>> {
496        let mut v = Vec::new();
497        while let Some(f) = d.next_frame() {
498            v.push(f);
499        }
500        v
501    }
502
503    #[test]
504    fn deframer_byte_by_byte() {
505        let mut d = Deframer::new();
506        let mut frames = Vec::new();
507        let input: Vec<u8> = VECTORS.iter().flat_map(|v| v.0.iter().copied()).collect();
508        for b in input {
509            d.push(&[b]);
510            frames.extend(drain(&mut d));
511        }
512        assert_eq!(frames.len(), VECTORS.len());
513        for (f, v) in frames.iter().zip(VECTORS) {
514            assert_eq!(f.as_slice(), &v.0[..v.0.len() - 1]);
515        }
516    }
517
518    #[test]
519    fn deframer_garbage_and_two_packets() {
520        let mut d = Deframer::new();
521        d.push(b"noise\r\n\x01# N3\r\x01#!Y?\r");
522        assert_eq!(
523            drain(&mut d),
524            vec![b"\x01# N3".to_vec(), b"\x01#!Y?".to_vec()]
525        );
526        d.push(b"only garbage");
527        assert_eq!(d.next_frame(), None);
528    }
529
530    #[test]
531    fn deframer_invalid_len_skipped() {
532        let mut d = Deframer::new();
533        d.push(b"\x01\x7f\x01\"x\x01#!Y?\r");
534        assert_eq!(drain(&mut d), vec![b"\x01#!Y?".to_vec()]);
535    }
536
537    #[test]
538    fn deframer_resync_on_truncated() {
539        let mut d = Deframer::new();
540        d.push(b"\x01?\"D1:   ");
541        assert_eq!(d.next_frame(), None);
542        d.push(b"\x01#!Y?\r");
543        assert_eq!(drain(&mut d), vec![b"\x01#!Y?".to_vec()]);
544    }
545
546    #[test]
547    fn deframer_soh_run_is_linear() {
548        // 1 MiB of SOH: every LEN byte is SOH (invalid). Quadratic resync
549        // would take minutes; one linear pass is milliseconds.
550        let mut d = Deframer::new();
551        d.push(&vec![SOH; 1 << 20]);
552        let t = std::time::Instant::now();
553        assert_eq!(d.next_frame(), None);
554        assert!(t.elapsed() < std::time::Duration::from_secs(2));
555        // The trailing SOH may still start a packet.
556        d.push(b"#!Y?\r");
557        assert_eq!(drain(&mut d), vec![b"\x01#!Y?".to_vec()]);
558        // A run of valid-looking SOH LEN pairs, each cut short by the next SOH.
559        let mut d = Deframer::new();
560        d.push(&b"\x01~".repeat(1 << 19));
561        let t = std::time::Instant::now();
562        assert_eq!(d.next_frame(), None);
563        assert!(t.elapsed() < std::time::Duration::from_secs(2));
564    }
565
566    #[test]
567    fn deframer_clear() {
568        let mut d = Deframer::new();
569        d.push(b"\x01#!Y");
570        d.clear();
571        d.push(b"?\r");
572        assert_eq!(d.next_frame(), None);
573    }
574}