use std::vec::Vec;
pub const MAX_RUN: usize = 4 + 255;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Group {
pub byte: u8,
pub raw_len: usize,
}
impl Group {
pub fn encoded_len(self) -> usize {
if self.raw_len >= 4 { 5 } else { self.raw_len }
}
pub fn write_into(self, out: &mut Vec<u8>) {
let b = self.byte;
if self.raw_len >= 4 {
out.extend_from_slice(&[b, b, b, b]);
out.push((self.raw_len - 4) as u8);
} else {
for _ in 0..self.raw_len {
out.push(b);
}
}
}
}
pub struct Splitter {
byte: u8,
len: usize,
}
impl Splitter {
pub fn new() -> Splitter {
Splitter { byte: 0, len: 0 }
}
#[inline]
pub fn push(&mut self, b: u8) -> Option<Group> {
if self.len > 0 && b == self.byte && self.len < MAX_RUN {
self.len += 1;
return None;
}
let done = self.take();
self.byte = b;
self.len = 1;
done
}
pub fn finish(&mut self) -> Option<Group> {
self.take()
}
fn take(&mut self) -> Option<Group> {
if self.len == 0 {
return None;
}
let group = Group { byte: self.byte, raw_len: self.len };
self.len = 0;
Some(group)
}
}
impl Default for Splitter {
fn default() -> Self {
Splitter::new()
}
}
#[cfg(test)]
mod tests {
use std::vec;
use super::*;
fn encode(input: &[u8]) -> Vec<u8> {
let mut out = Vec::new();
let mut split = Splitter::new();
let mut raw = 0usize;
for &b in input {
if let Some(g) = split.push(b) {
g.write_into(&mut out);
raw += g.raw_len;
}
}
if let Some(g) = split.finish() {
g.write_into(&mut out);
raw += g.raw_len;
}
assert_eq!(raw, input.len(), "groups must account for every input byte");
out
}
fn decode(enc: &[u8]) -> Vec<u8> {
let mut out = Vec::new();
let mut prev: i32 = -1;
let mut count = 0u32;
for &b in enc {
if count == 4 {
for _ in 0..b {
out.push(prev as u8);
}
count = 0;
prev = -1;
} else {
out.push(b);
if b as i32 == prev {
count += 1;
} else {
prev = b as i32;
count = 1;
}
}
}
out
}
#[test]
fn passes_short_runs_through() {
assert_eq!(encode(b"abcaaabbb"), b"abcaaabbb");
assert_eq!(decode(&encode(b"abcaaabbb")), b"abcaaabbb");
}
#[test]
fn encodes_a_run_of_exactly_four() {
assert_eq!(encode(b"aaaa"), b"aaaa\x00");
assert_eq!(decode(&encode(b"aaaa")), b"aaaa");
}
#[test]
fn encodes_a_run_of_five() {
assert_eq!(encode(b"aaaaa"), b"aaaa\x01");
assert_eq!(decode(&encode(b"aaaaa")), b"aaaaa");
}
#[test]
fn splits_runs_longer_than_the_cap() {
let input = vec![b'z'; 300];
let enc = encode(&input);
assert_eq!(&enc[..5], b"zzzz\xff");
assert_eq!(&enc[5..10], &[b'z', b'z', b'z', b'z', 41 - 4]);
assert_eq!(enc.len(), 10);
assert_eq!(decode(&enc), input);
}
#[test]
fn splits_a_run_of_exactly_262() {
let input = vec![b'q'; 262];
assert_eq!(encode(&input), b"qqqq\xffqqq");
assert_eq!(decode(&encode(&input)), input);
}
#[test]
fn group_sizes_are_reported_correctly() {
for raw_len in 1..=MAX_RUN {
let g = Group { byte: 7, raw_len };
let mut out = Vec::new();
g.write_into(&mut out);
assert_eq!(out.len(), g.encoded_len(), "raw_len {raw_len}");
assert_eq!(decode(&out), vec![7u8; raw_len]);
}
}
#[test]
fn handles_empty_input() {
assert!(encode(b"").is_empty());
}
#[test]
fn a_run_never_exceeds_the_cap() {
let input = vec![b'k'; 5000];
let mut split = Splitter::new();
let mut groups = Vec::new();
for &b in &input {
if let Some(g) = split.push(b) {
groups.push(g);
}
}
if let Some(g) = split.finish() {
groups.push(g);
}
assert!(groups.iter().all(|g| g.raw_len <= MAX_RUN));
assert_eq!(groups.iter().map(|g| g.raw_len).sum::<usize>(), 5000);
}
#[test]
fn round_trips_a_gnarly_input() {
let mut input = Vec::new();
for i in 0..2000u32 {
let b = (i / 7 % 5) as u8;
for _ in 0..(i % 9) {
input.push(b);
}
}
for cut in [0, 1, 2, 3, 4, 5, 100, 1000, input.len()] {
let slice = &input[..cut.min(input.len())];
assert_eq!(decode(&encode(slice)), slice);
}
}
}