pub(crate) fn decode(input: &[u8]) -> Result<Vec<u8>, String> {
let mut out = Vec::new();
let mut pos = 0;
loop {
if pos >= input.len() {
break;
}
let l = input[pos];
pos += 1;
match l {
128 => {
break;
}
0..=127 => {
let count = usize::from(l) + 1;
if pos + count > input.len() {
return Err(format!(
"RunLengthDecode: truncated literal run: need {} bytes at position {}, only {} remain",
count,
pos,
input.len() - pos,
));
}
out.extend_from_slice(&input[pos..pos + count]);
pos += count;
}
129..=255 => {
let count = usize::from(257u16 - u16::from(l));
if pos >= input.len() {
return Err(format!(
"RunLengthDecode: truncated repeat run: no byte at position {pos}"
));
}
let byte = input[pos];
pos += 1;
for _ in 0..count {
out.push(byte);
}
}
}
}
Ok(out)
}
pub(crate) fn encode(input: &[u8]) -> Vec<u8> {
let mut out = Vec::new();
let mut i = 0;
while i < input.len() {
let run_byte = input[i];
let mut run_len = 1;
while i + run_len < input.len() && input[i + run_len] == run_byte && run_len < 128 {
run_len += 1;
}
if run_len >= 3 {
out.push((257u16 - run_len as u16) as u8); out.push(run_byte);
i += run_len;
} else {
let lit_start = i;
let mut lit_len = 0;
while i < input.len() && lit_len < 128 {
let peek_byte = input[i];
let mut peek_run = 1;
while i + peek_run < input.len()
&& input[i + peek_run] == peek_byte
&& peek_run < 128
{
peek_run += 1;
}
if peek_run >= 3 {
break;
}
let take = (peek_run).min(128 - lit_len);
i += take;
lit_len += take;
}
if lit_len > 0 {
out.push(lit_len as u8 - 1);
out.extend_from_slice(&input[lit_start..lit_start + lit_len]);
}
}
}
out.push(0x80);
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn decode_empty_just_eod() {
assert_eq!(decode(&[0x80]).unwrap(), b"");
}
#[test]
fn decode_short_literal() {
let input = [0x02, b'A', b'B', b'C', 0x80];
assert_eq!(decode(&input).unwrap(), b"ABC");
}
#[test]
fn decode_short_repeat() {
let input = [0xFE, 0x41, 0x80];
assert_eq!(decode(&input).unwrap(), &[0x41, 0x41, 0x41]);
}
#[test]
fn decode_mixed_literal_and_repeat() {
let input = [0x01, b'X', b'Y', 0xFD, b'Z', 0x00, b'W', 0x80];
let expected: Vec<u8> = [b'X', b'Y', b'Z', b'Z', b'Z', b'Z', b'W'].to_vec();
assert_eq!(decode(&input).unwrap(), expected);
}
#[test]
fn decode_max_literal_128_bytes() {
let mut input = vec![0x7Fu8];
for i in 0u8..128 {
input.push(i);
}
input.push(0x80); let result = decode(&input).unwrap();
assert_eq!(result.len(), 128);
for (i, &b) in result.iter().enumerate() {
assert_eq!(b, i as u8);
}
}
#[test]
fn decode_max_repeat_128_copies() {
let input = [0x81, 0xAB, 0x80];
let result = decode(&input).unwrap();
assert_eq!(result.len(), 128);
assert!(result.iter().all(|&b| b == 0xAB));
}
#[test]
fn decode_rejects_truncated_literal() {
let input = [0x05, b'A', b'B', b'C']; let result = decode(&input);
assert!(result.is_err(), "expected error for truncated literal");
let err = result.unwrap_err();
assert!(
err.starts_with("RunLengthDecode:"),
"error should have RunLengthDecode: prefix, got: {err}"
);
}
#[test]
fn decode_rejects_truncated_repeat() {
let input = [0xFD];
let result = decode(&input);
assert!(result.is_err(), "expected error for truncated repeat");
let err = result.unwrap_err();
assert!(
err.starts_with("RunLengthDecode:"),
"error should have RunLengthDecode: prefix, got: {err}"
);
}
#[test]
fn decode_implicit_eod_at_boundary() {
let input = [0x00, b'A']; let result = decode(&input).unwrap();
assert_eq!(result, b"A");
}
fn round_trip(raw: &[u8]) {
let encoded = encode(raw);
let decoded = decode(&encoded).unwrap();
assert_eq!(
decoded,
raw,
"round-trip failed for input of length {}",
raw.len()
);
}
#[test]
fn round_trip_empty() {
round_trip(b"");
}
#[test]
fn round_trip_127_bytes_one_max_literal_minus_one() {
let data: Vec<u8> = (0u8..127).collect();
round_trip(&data);
}
#[test]
fn round_trip_128_bytes_one_max_literal() {
let data: Vec<u8> = (0u8..128).collect();
round_trip(&data);
}
#[test]
fn round_trip_129_bytes_max_literal_plus_one() {
let data: Vec<u8> = (0u8..=128).collect();
round_trip(&data);
}
#[test]
fn round_trip_all_same_128_bytes_one_max_repeat() {
let data = vec![0xA5u8; 128];
round_trip(&data);
}
#[test]
fn round_trip_all_same_129_bytes() {
let data = vec![0xA5u8; 129];
round_trip(&data);
}
#[test]
fn round_trip_alternating_bytes_all_literals() {
let data: Vec<u8> = (0u8..128).map(|i| i % 2).collect();
round_trip(&data);
}
#[test]
fn round_trip_mixed_runs_and_literals() {
let mut data = vec![0x10u8, 0x20, 0x30, 0x40, 0x50]; data.extend(vec![0xBBu8; 10]); data.extend([0x61u8, 0x62, 0x63]); data.extend(vec![0xFFu8; 8]); round_trip(&data);
}
#[test]
fn round_trip_all_bytes() {
let data: Vec<u8> = (0u8..=255).collect();
round_trip(&data);
}
#[test]
fn round_trip_deterministic_pseudo_random() {
fn xorshift32(state: &mut u32) -> u8 {
*state ^= *state << 13;
*state ^= *state >> 17;
*state ^= *state << 5;
(*state & 0xFF) as u8
}
let mut state: u32 = 0xDEAD_BEEF;
let data: Vec<u8> = (0..512).map(|_| xorshift32(&mut state)).collect();
round_trip(&data);
}
}