1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

//! Implementation of the Ziv-Lempel-Welch algorithm
//!
//! Right now data is encoded with 32-bit dictionary in little endian.
//! This might change later to 24-bit
use byteorder::{ReadBytesExt, WriteBytesExt, LE};
use std::{collections::HashMap, error::Error, io::prelude::*};

pub struct LZW;

impl super::Compressor for LZW {
    /// Encodes data with Lempel-Ziv-Welch compression.
    fn encode(input: &mut impl Read, output: &mut impl Write) -> Result<(), Box<dyn Error>> {
        let mut dict = LZW::init_dict();
        let mut current = String::new();
        let mut next = 257;
        for byte in input.bytes() {
            let c = byte.unwrap() as char;
            current.push(c);
            if let None = dict.get(&current) {
                dict.insert(current.clone(), next);
                next += 1;
                current.pop();
                let code = dict.get(&current).unwrap();
                output.write_u32::<LE>(*code)?;
                current = c.to_string();
            }
        }
        output.write_u32::<LE>(*dict.get(&current).unwrap())?;
        Ok(())
    }

    /// Decodes data with Lempel-Ziv-Welch compression.
    fn decode(input: &mut impl Read, output: &mut impl Write) -> Result<(), Box<dyn Error>> {
        let mut dict = LZW::init_rev_dict();
        let mut prev = String::new();
        let mut next = 257;
        while let Ok(integer) = input.read_u32::<LE>() {
            if let None = dict.get(&integer) {
                let mut clone = prev.clone();
                clone.push(char_at(&prev, 0));
                dict.insert(integer, clone);
            }
            let current = dict.get(&integer).unwrap().clone();
            output.write(current.as_bytes())?;
            if !prev.is_empty() {
                let mut clone = prev.clone();
                clone.push(char_at(&current, 0));
                dict.insert(next, clone);
                next += 1;
            }
            prev = current;
        }
        Ok(())
    }
}

impl LZW {
    /// initializes dictionary for encoding
    fn init_dict() -> HashMap<String, u32> {
        let mut dict = HashMap::new();
        for i in 0..256 {
            let c = i as u8 as char;
            dict.insert(c.to_string(), i);
        }
        dict
    }

    /// initializes dictionary for decoding
    fn init_rev_dict() -> HashMap<u32, String> {
        let mut dict = HashMap::new();
        for i in 0..256 {
            let c = i as u8 as char;
            dict.insert(i, c.to_string());
        }
        dict
    }
}

/// returns charatacter from string at index
fn char_at(s: &String, index: usize) -> char {
    s.as_bytes()[index] as char
}

#[cfg(test)]
mod tests {
    use super::super::Compressor;
    use super::LZW;
    use std::fs::File;
    use std::io::{prelude::*, SeekFrom};
    use tempfile::*;

    #[test]
    fn decomp_and_orig_are_same() {
        let mut testfile = File::open("../testfiles/small.txt").unwrap();
        let mut comp = tempfile().unwrap();
        let mut decomp = tempfile().unwrap();

        LZW::encode(&mut testfile, &mut comp).unwrap();
        comp.seek(SeekFrom::Start(0)).unwrap();
        LZW::decode(&mut comp, &mut decomp).unwrap();

        let mut decomp_content = String::new();
        let mut testfile_content = String::new();

        decomp.seek(SeekFrom::Start(0)).unwrap();
        testfile.seek(SeekFrom::Start(0)).unwrap();

        decomp.read_to_string(&mut decomp_content).unwrap();
        testfile.read_to_string(&mut testfile_content).unwrap();

        assert_eq!(testfile_content, decomp_content);
    }

    #[test]
    #[ignore]
    fn compressed_file_is_smaller() {
        let mut testfile = File::open("../testfiles/big.txt").unwrap();
        let mut compressed = tempfile().unwrap();
        LZW::encode(&mut testfile, &mut compressed).unwrap();
        let testfile_meta = testfile.metadata().unwrap();
        let compressed_meta = compressed.metadata().unwrap();
        assert!(compressed_meta.len() < testfile_meta.len());
    }

    #[test]
    fn dict_has_corresponding_character() {
        let dict = LZW::init_dict();
        let num1: u32 = 65;
        let num2: u32 = 66;
        let num3: u32 = 67;
        let s1 = String::from("A");
        let s2 = String::from("B");
        let s3 = String::from("C");
        assert_eq!(dict.get(&s1), Some(&num1));
        assert_eq!(dict.get(&s2), Some(&num2));
        assert_eq!(dict.get(&s3), Some(&num3));
    }
}