pamoja_serial/cobs.rs
1//! COBS framing, Consistent Overhead Byte Stuffing.
2//!
3//! COBS (Cheshire and Baker, 1999) frames a packet by removing every zero byte from it, so
4//! a single zero byte, the [`DELIMITER`], can mark the end of a frame and never be confused
5//! with data. It encodes each run of up to 254 non-zero bytes as a length code followed by
6//! the bytes themselves; a code of `0xFF` marks a full run of 254 non-zero bytes with no
7//! zero after it, and a code from `0x01` to `0xFE` marks a shorter run that ended at a zero.
8//!
9//! Its appeal over [SLIP](crate::slip) is the overhead: where SLIP can double a worst-case
10//! payload, COBS adds at most one byte per 254 (see [`max_encoded_len`]), which is why
11//! motor-control and robotics links that care about predictable framing cost prefer it.
12//!
13//! [`encode`] produces the encoded block followed by the trailing zero delimiter, ready for
14//! the wire; [`decode`] accepts a frame with or without that delimiter.
15
16use crate::SerialError;
17
18/// The COBS frame delimiter: a single zero byte, the one value the encoding removes from
19/// the payload so it can mark a frame boundary unambiguously.
20pub const DELIMITER: u8 = 0x00;
21
22/// The largest run of non-zero bytes a single COBS code can cover.
23const MAX_RUN: usize = 254;
24
25/// Returns an output length that is always large enough to hold the COBS encoding of a
26/// payload of `payload_len` bytes, including the trailing [`DELIMITER`].
27///
28/// COBS adds one code byte for every run of up to 254 bytes, plus the one delimiter, so the
29/// overhead is bounded and small. This rounds the run count up and so may return one byte
30/// more than the tightest possible encoding, which only ever over-allocates the buffer.
31///
32/// # Arguments
33///
34/// * `payload_len` - the length of the payload to be encoded.
35///
36/// # Returns
37///
38/// The maximum number of bytes [`encode`] can write for that payload.
39///
40/// # Examples
41///
42/// ```
43/// use pamoja_serial::cobs;
44///
45/// // A short payload costs one code byte and one delimiter on top of the data.
46/// assert_eq!(cobs::max_encoded_len(10), 12);
47/// ```
48#[must_use]
49pub const fn max_encoded_len(payload_len: usize) -> usize {
50 payload_len + payload_len / MAX_RUN + 2
51}
52
53/// Encodes a payload into a COBS frame, terminated by the [`DELIMITER`] byte.
54///
55/// The encoded bytes are guaranteed to contain no zero except the trailing delimiter, so a
56/// receiver can split a stream into frames on the zero byte alone.
57///
58/// # Arguments
59///
60/// * `payload` - the bytes to frame.
61/// * `output` - the buffer the frame is written into; size it with [`max_encoded_len`].
62///
63/// # Returns
64///
65/// The number of bytes written to `output`, including the trailing [`DELIMITER`].
66///
67/// # Errors
68///
69/// Returns [`SerialError::BufferTooSmall`] if `output` cannot hold the whole frame.
70///
71/// # Examples
72///
73/// ```
74/// use pamoja_serial::cobs;
75///
76/// // The canonical example: a single zero byte encodes to 01 01, then the 00 delimiter.
77/// let mut frame = [0u8; 4];
78/// let n = cobs::encode(&[0x00], &mut frame)?;
79/// assert_eq!(&frame[..n], &[0x01, 0x01, 0x00]);
80/// # Ok::<(), pamoja_serial::SerialError>(())
81/// ```
82pub fn encode(payload: &[u8], output: &mut [u8]) -> Result<usize, SerialError> {
83 // Reserve output[0] for the first run's code byte; data follows from index 1.
84 if output.len() < 2 {
85 return Err(SerialError::BufferTooSmall);
86 }
87 let mut write = 1usize;
88 // The index of the code byte for the run currently being built, or `None` once a full
89 // 0xFF run has closed at the exact end of the payload (such a run owes no further code).
90 let mut code_index: Option<usize> = Some(0);
91 let mut code: u8 = 1;
92 let n = payload.len();
93
94 let mut i = 0usize;
95 while i < n {
96 let byte = payload[i];
97 i += 1;
98 if byte != DELIMITER {
99 write_at(output, write, byte)?;
100 write += 1;
101 code += 1;
102 if code == 0xFF {
103 // A run of 254 non-zero bytes is full; close it with a 0xFF code.
104 set_code(output, code_index, 0xFF);
105 code = 1;
106 if i < n {
107 // More payload follows, so start a fresh run.
108 reserve(output, &mut write, &mut code_index)?;
109 } else {
110 // The payload ends exactly here; a 0xFF run carries no trailing zero,
111 // so there is no further code byte to write.
112 code_index = None;
113 }
114 }
115 } else {
116 // A zero ends the current run; its code records the run length.
117 set_code(output, code_index, code);
118 code = 1;
119 reserve(output, &mut write, &mut code_index)?;
120 }
121 }
122 set_code(output, code_index, code);
123 write_at(output, write, DELIMITER)?;
124 write += 1;
125 Ok(write)
126}
127
128/// Decodes a single COBS frame, recovering the original payload.
129///
130/// Decoding stops at the [`DELIMITER`] that closes the frame, or at the end of the slice if
131/// it carries no trailing delimiter.
132///
133/// # Arguments
134///
135/// * `frame` - the encoded bytes, with or without the trailing [`DELIMITER`].
136/// * `output` - the buffer the payload is written into; it never needs more room than
137/// `frame`.
138///
139/// # Returns
140///
141/// The number of payload bytes written to `output`.
142///
143/// # Errors
144///
145/// Returns [`SerialError::TruncatedFrame`] if a code byte claims more data than the frame
146/// carries (which also catches a stray zero inside a run), and
147/// [`SerialError::BufferTooSmall`] if `output` cannot hold the payload.
148///
149/// # Examples
150///
151/// ```
152/// use pamoja_serial::cobs;
153///
154/// let mut payload = [0u8; 4];
155/// let n = cobs::decode(&[0x03, 0x11, 0x22, 0x02, 0x33, 0x00], &mut payload)?;
156/// assert_eq!(&payload[..n], &[0x11, 0x22, 0x00, 0x33]);
157/// # Ok::<(), pamoja_serial::SerialError>(())
158/// ```
159pub fn decode(frame: &[u8], output: &mut [u8]) -> Result<usize, SerialError> {
160 let mut write = 0usize;
161 // Bytes still owed by the current run, and the code of the run just finished. Starting
162 // `code` at 0xFF suppresses an implied zero before the very first run.
163 let mut owed: u8 = 0;
164 let mut code: u8 = 0xFF;
165 for &byte in frame {
166 if byte == DELIMITER {
167 // A well-formed frame reaches the delimiter with the current run satisfied.
168 if owed != 0 {
169 return Err(SerialError::TruncatedFrame);
170 }
171 return Ok(write);
172 }
173 if owed != 0 {
174 write_at(output, write, byte)?;
175 write += 1;
176 owed -= 1;
177 } else {
178 // `byte` is the next run's code. A finished run shorter than 0xFF ended at a
179 // zero in the original data, so emit that implied zero before the new run.
180 if code != 0xFF {
181 write_at(output, write, DELIMITER)?;
182 write += 1;
183 }
184 code = byte;
185 owed = byte - 1;
186 }
187 }
188 if owed != 0 {
189 return Err(SerialError::TruncatedFrame);
190 }
191 Ok(write)
192}
193
194/// A streaming COBS decoder that reassembles whole frames from a serial byte stream.
195///
196/// Like [`SlipDecoder`](crate::slip::SlipDecoder), this is what a real serial receive loop
197/// uses: it buffers up to `N` payload bytes and [`push`](CobsDecoder::push) returns the
198/// finished payload when the zero [`DELIMITER`] closes a frame, or `None` while one is
199/// still being assembled.
200///
201/// # Examples
202///
203/// ```
204/// use pamoja_serial::cobs::{CobsDecoder, DELIMITER};
205///
206/// let mut decoder: CobsDecoder<32> = CobsDecoder::new();
207/// // The encoding of the payload 11 22 00 33, followed by the delimiter.
208/// let stream = [0x03, 0x11, 0x22, 0x02, 0x33, DELIMITER];
209/// let mut got = None;
210/// for &byte in &stream {
211/// if let Some(frame) = decoder.push(byte)? {
212/// got = Some(frame.to_vec());
213/// }
214/// }
215/// assert_eq!(got.as_deref(), Some(&[0x11, 0x22, 0x00, 0x33][..]));
216/// # Ok::<(), pamoja_serial::SerialError>(())
217/// ```
218#[derive(Debug)]
219pub struct CobsDecoder<const N: usize> {
220 buffer: [u8; N],
221 len: usize,
222 owed: u8,
223 code: u8,
224 complete: bool,
225}
226
227impl<const N: usize> CobsDecoder<N> {
228 /// Creates an empty decoder with room for an `N`-byte payload.
229 ///
230 /// # Returns
231 ///
232 /// A decoder ready to receive the first byte.
233 #[must_use]
234 pub const fn new() -> Self {
235 Self {
236 buffer: [0u8; N],
237 len: 0,
238 owed: 0,
239 code: 0xFF,
240 complete: false,
241 }
242 }
243
244 /// Discards any partly assembled frame, returning the decoder to its initial state.
245 pub fn reset(&mut self) {
246 self.len = 0;
247 self.owed = 0;
248 self.code = 0xFF;
249 self.complete = false;
250 }
251
252 /// Feeds one byte from the stream into the decoder.
253 ///
254 /// # Arguments
255 ///
256 /// * `byte` - the next byte received on the serial line.
257 ///
258 /// # Returns
259 ///
260 /// `Some(payload)` when this byte's [`DELIMITER`] completed a frame, or `None` while a
261 /// frame is still being assembled.
262 ///
263 /// # Errors
264 ///
265 /// Returns [`SerialError::TruncatedFrame`] if the delimiter arrives before a run's data
266 /// is complete, and [`SerialError::BufferTooSmall`] if the payload exceeds `N` bytes.
267 /// After any error the partial frame is discarded and the decoder resumes at the next
268 /// byte.
269 pub fn push(&mut self, byte: u8) -> Result<Option<&[u8]>, SerialError> {
270 if self.complete {
271 self.reset();
272 }
273 if byte == DELIMITER {
274 if self.owed != 0 {
275 self.reset();
276 return Err(SerialError::TruncatedFrame);
277 }
278 self.complete = true;
279 return Ok(Some(&self.buffer[..self.len]));
280 }
281 if self.owed != 0 {
282 self.store(byte)?;
283 self.owed -= 1;
284 } else {
285 if self.code != 0xFF {
286 self.store(DELIMITER)?;
287 }
288 self.code = byte;
289 self.owed = byte - 1;
290 }
291 Ok(None)
292 }
293
294 fn store(&mut self, byte: u8) -> Result<(), SerialError> {
295 if self.len >= N {
296 self.reset();
297 return Err(SerialError::BufferTooSmall);
298 }
299 self.buffer[self.len] = byte;
300 self.len += 1;
301 Ok(())
302 }
303}
304
305impl<const N: usize> Default for CobsDecoder<N> {
306 fn default() -> Self {
307 Self::new()
308 }
309}
310
311/// Writes `byte` into `output[index]`, or reports the buffer is full.
312fn write_at(output: &mut [u8], index: usize, byte: u8) -> Result<(), SerialError> {
313 if index >= output.len() {
314 return Err(SerialError::BufferTooSmall);
315 }
316 output[index] = byte;
317 Ok(())
318}
319
320/// Records a run's length code at a previously reserved index, if one is pending.
321///
322/// The index was reserved by [`reserve`] (or is the initial code slot), so it is always in
323/// bounds; a `None` index means a full 0xFF run already closed the encoding.
324fn set_code(output: &mut [u8], code_index: Option<usize>, code: u8) {
325 if let Some(index) = code_index {
326 output[index] = code;
327 }
328}
329
330/// Reserves the next code slot at `write`, advancing `write` past it, and points
331/// `code_index` at it.
332fn reserve(
333 output: &[u8],
334 write: &mut usize,
335 code_index: &mut Option<usize>,
336) -> Result<(), SerialError> {
337 if *write >= output.len() {
338 return Err(SerialError::BufferTooSmall);
339 }
340 *code_index = Some(*write);
341 *write += 1;
342 Ok(())
343}
344
345#[cfg(test)]
346mod tests {
347 use super::*;
348
349 /// Builds the inclusive byte range `start..=end` as a vector.
350 fn range(start: u8, end: u8) -> Vec<u8> {
351 (start..=end).collect()
352 }
353
354 /// The canonical encoding examples from the COBS specification (Cheshire and Baker),
355 /// each as (unencoded payload, encoded frame including the trailing zero delimiter).
356 fn canonical_vectors() -> Vec<(Vec<u8>, Vec<u8>)> {
357 let mut v: Vec<(Vec<u8>, Vec<u8>)> = vec![
358 (vec![0x00], vec![0x01, 0x01, 0x00]),
359 (vec![0x00, 0x00], vec![0x01, 0x01, 0x01, 0x00]),
360 (vec![0x00, 0x11, 0x00], vec![0x01, 0x02, 0x11, 0x01, 0x00]),
361 (
362 vec![0x11, 0x22, 0x00, 0x33],
363 vec![0x03, 0x11, 0x22, 0x02, 0x33, 0x00],
364 ),
365 (
366 vec![0x11, 0x22, 0x33, 0x44],
367 vec![0x05, 0x11, 0x22, 0x33, 0x44, 0x00],
368 ),
369 (
370 vec![0x11, 0x00, 0x00, 0x00],
371 vec![0x02, 0x11, 0x01, 0x01, 0x01, 0x00],
372 ),
373 ];
374
375 // Example 7: 254 non-zero bytes 01..FE encode to a single 0xFF run, no phantom code.
376 let mut e7 = vec![0xFF];
377 e7.extend(range(0x01, 0xFE));
378 e7.push(0x00);
379 v.push((range(0x01, 0xFE), e7));
380
381 // Example 8: a leading zero, then 01..FE (255 bytes).
382 let mut p8 = vec![0x00];
383 p8.extend(range(0x01, 0xFE));
384 let mut e8 = vec![0x01, 0xFF];
385 e8.extend(range(0x01, 0xFE));
386 e8.push(0x00);
387 v.push((p8, e8));
388
389 // Example 9: 01..FF (255 non-zero bytes) splits into a full run plus a trailing one.
390 let mut e9 = vec![0xFF];
391 e9.extend(range(0x01, 0xFE));
392 e9.extend([0x02, 0xFF, 0x00]);
393 v.push((range(0x01, 0xFF), e9));
394
395 // Example 10: 02..FF then a trailing zero (255 bytes).
396 let mut p10 = range(0x02, 0xFF);
397 p10.push(0x00);
398 let mut e10 = vec![0xFF];
399 e10.extend(range(0x02, 0xFF));
400 e10.extend([0x01, 0x01, 0x00]);
401 v.push((p10, e10));
402
403 // Example 11: 03..FF, a zero, then 01 (255 bytes).
404 let mut p11 = range(0x03, 0xFF);
405 p11.extend([0x00, 0x01]);
406 let mut e11 = vec![0xFE];
407 e11.extend(range(0x03, 0xFF));
408 e11.extend([0x02, 0x01, 0x00]);
409 v.push((p11, e11));
410
411 v
412 }
413
414 #[test]
415 fn encode_matches_the_canonical_vectors() {
416 for (payload, expected) in canonical_vectors() {
417 let mut out = vec![0u8; max_encoded_len(payload.len())];
418 let n = encode(&payload, &mut out).unwrap();
419 assert_eq!(&out[..n], &expected[..], "payload {payload:02x?}");
420 }
421 }
422
423 #[test]
424 fn decode_matches_the_canonical_vectors() {
425 for (payload, encoded) in canonical_vectors() {
426 let mut out = vec![0u8; payload.len()];
427 let n = decode(&encoded, &mut out).unwrap();
428 assert_eq!(&out[..n], &payload[..], "encoded {encoded:02x?}");
429 }
430 }
431
432 #[test]
433 fn the_encoding_never_contains_an_interior_zero() {
434 for (payload, _) in canonical_vectors() {
435 let mut out = vec![0u8; max_encoded_len(payload.len())];
436 let n = encode(&payload, &mut out).unwrap();
437 // Every byte except the final delimiter must be non-zero.
438 assert!(out[..n - 1].iter().all(|&b| b != 0));
439 assert_eq!(out[n - 1], DELIMITER);
440 }
441 }
442
443 #[test]
444 fn empty_payload_round_trips() {
445 let mut frame = [0u8; 4];
446 let n = encode(&[], &mut frame).unwrap();
447 assert_eq!(&frame[..n], &[0x01, 0x00]);
448 let mut out = [0u8; 4];
449 let m = decode(&frame[..n], &mut out).unwrap();
450 assert_eq!(m, 0);
451 }
452
453 #[test]
454 fn round_trips_payloads_across_the_run_boundary() {
455 // Lengths around 254/255 and a mix of zero and non-zero content stress the run
456 // splitting and the implied-zero handling.
457 for len in [0usize, 1, 2, 253, 254, 255, 256, 509, 510, 511] {
458 for &fill in &[0x00u8, 0x41, 0xFF] {
459 let payload = vec![fill; len];
460 let mut frame = vec![0u8; max_encoded_len(len)];
461 let n = encode(&payload, &mut frame).unwrap();
462 let mut out = vec![0u8; len];
463 let m = decode(&frame[..n], &mut out).unwrap();
464 assert_eq!(&out[..m], &payload[..], "len {len} fill {fill:#04x}");
465 }
466 }
467 }
468
469 #[test]
470 fn round_trips_a_mixed_payload_with_scattered_zeros() {
471 let payload: Vec<u8> = (0..600u16).map(|i| (i % 7) as u8).collect();
472 let mut frame = vec![0u8; max_encoded_len(payload.len())];
473 let n = encode(&payload, &mut frame).unwrap();
474 let mut out = vec![0u8; payload.len()];
475 let m = decode(&frame[..n], &mut out).unwrap();
476 assert_eq!(&out[..m], &payload[..]);
477 }
478
479 #[test]
480 fn decode_tolerates_a_missing_trailing_delimiter() {
481 // The same bytes as example 4 without the closing zero.
482 let mut out = [0u8; 4];
483 let n = decode(&[0x03, 0x11, 0x22, 0x02, 0x33], &mut out).unwrap();
484 assert_eq!(&out[..n], &[0x11, 0x22, 0x00, 0x33]);
485 }
486
487 #[test]
488 fn a_code_that_overruns_the_frame_is_truncated() {
489 // Code 0x03 claims two data bytes but only one precedes the delimiter.
490 let mut out = [0u8; 4];
491 assert_eq!(
492 decode(&[0x03, 0x11, 0x00], &mut out),
493 Err(SerialError::TruncatedFrame)
494 );
495 }
496
497 #[test]
498 fn encode_reports_a_full_buffer() {
499 let mut frame = [0u8; 3];
500 assert_eq!(
501 encode(&[0x11, 0x22, 0x33], &mut frame),
502 Err(SerialError::BufferTooSmall)
503 );
504 }
505
506 #[test]
507 fn decode_reports_a_full_buffer() {
508 let mut out = [0u8; 1];
509 assert_eq!(
510 decode(&[0x03, 0x11, 0x22, 0x00], &mut out),
511 Err(SerialError::BufferTooSmall)
512 );
513 }
514
515 #[test]
516 fn streaming_decoder_matches_the_canonical_vectors() {
517 for (payload, encoded) in canonical_vectors() {
518 let mut decoder: CobsDecoder<512> = CobsDecoder::new();
519 let mut produced = false;
520 for &byte in &encoded {
521 if let Some(frame) = decoder.push(byte).unwrap() {
522 assert_eq!(frame, &payload[..], "encoded {encoded:02x?}");
523 produced = true;
524 }
525 }
526 assert!(produced, "no frame for {encoded:02x?}");
527 }
528 }
529
530 #[test]
531 fn streaming_decoder_reports_overflow_then_recovers() {
532 let mut decoder: CobsDecoder<2> = CobsDecoder::new();
533 // Encoding of three non-zero bytes overflows a two-byte buffer.
534 assert!(decoder.push(0x04).unwrap().is_none());
535 assert!(decoder.push(0x11).unwrap().is_none());
536 assert!(decoder.push(0x22).unwrap().is_none());
537 assert_eq!(decoder.push(0x33), Err(SerialError::BufferTooSmall));
538 // A following frame (two bytes) decodes cleanly.
539 assert!(decoder.push(0x03).unwrap().is_none());
540 assert!(decoder.push(0xAA).unwrap().is_none());
541 assert!(decoder.push(0xBB).unwrap().is_none());
542 assert_eq!(decoder.push(DELIMITER).unwrap(), Some(&[0xAA, 0xBB][..]));
543 }
544}