deflate/
rle.rs

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

deflate/
rle.rs
