deflate/
rle.rs

Help
1use crate::lz77::{buffer_full, ProcessStatus};
2use crate::output_writer::{BufferStatus, DynamicWriter};
3
4use std::cmp;
5use std::ops::Range;
6
7const MIN_MATCH: usize = crate::huffman_table::MIN_MATCH as usize;
8const MAX_MATCH: usize = crate::huffman_table::MAX_MATCH as usize;
9
10/// Simple match function for run-length encoding.
11///
12/// Checks how many of the next bytes from the start of the slice `data` matches prev.
13fn get_match_length_rle(data: &[u8], prev: u8) -> usize {
14    data.iter()
15        .take(MAX_MATCH)
16        .take_while(|&&b| b == prev)
17        .count()
18}
19
20/// L77-Compress data using the RLE(Run-length encoding) strategy
21///
22/// This function simply looks for runs of data of at least length 3.
23pub fn process_chunk_greedy_rle(
24    data: &[u8],
25    iterated_data: &Range<usize>,
26    writer: &mut DynamicWriter,
27) -> (usize, ProcessStatus) {
28    if data.is_empty() {
29        return (0, ProcessStatus::Ok);
30    };
31
32    let end = cmp::min(data.len(), iterated_data.end);
33    // Start on at least byte 1.
34    let start = cmp::max(iterated_data.start, 1);
35    // The previous byte.
36    let mut prev = data[start - 1];
37    // Iterate through the requested range, but avoid going off the end.
38    let current_chunk = &data[cmp::min(start, end)..end];
39    let mut insert_it = current_chunk.iter().enumerate();
40    let mut overlap = 0;
41    // Make sure to output the first byte
42    if iterated_data.start == 0 && !data.is_empty() {
43        write_literal!(writer, data[0], 1);
44    }
45
46    while let Some((n, &b)) = insert_it.next() {
47        let position = n + start;
48        let match_len = if prev == b {
49            //TODO: Avoid comparing with self here.
50            // Would use as_slice() but that doesn't work on an enumerated iterator.
51            get_match_length_rle(&data[position..], prev)
52        } else {
53            0
54        };
55        if match_len >= MIN_MATCH {
56            if position + match_len > end {
57                overlap = position + match_len - end;
58            };
59            let b_status = writer.write_length_rle(match_len as u16);
60            if b_status == BufferStatus::Full {
61                return (overlap, buffer_full(position + match_len));
62            }
63            insert_it.nth(match_len - 2);
64        } else {
65            write_literal!(writer, b, position + 1);
66        }
67        prev = b;
68    }
69
70    (overlap, ProcessStatus::Ok)
71}
72
73#[cfg(test)]
74mod test {
75    use super::*;
76    use crate::lzvalue::{ld, lit, LZValue};
77
78    fn l(c: char) -> LZValue {
79        lit(c as u8)
80    }
81
82    #[test]
83    fn rle_compress() {
84        let input = b"textaaaaaaaaatext";
85        let mut w = DynamicWriter::new();
86        let r = 0..input.len();
87        let (overlap, _) = process_chunk_greedy_rle(input, &r, &mut w);
88        let expected = [
89            l('t'),
90            l('e'),
91            l('x'),
92            l('t'),
93            l('a'),
94            ld(8, 1),
95            l('t'),
96            l('e'),
97            l('x'),
98            l('t'),
99        ];
100        //println!("expected: {:?}", expected);
101        //println!("actual: {:?}", w.get_buffer());
102        assert!(w.get_buffer() == expected);
103        assert_eq!(overlap, 0);
104    }
105}
deflate/rle.rs

deflate/
rle.rs
