lz_string/
lib.rs

1#[macro_use]
2mod utils;
3
4mod base64;
5mod bitreader;
6mod error;
7
8use bitreader::RevBitReader;
9use std::char::decode_utf16;
10use std::result;
11
12pub use error::{Error, Result};
13
14#[derive(Default)]
15struct State {
16    n_bits: u8,
17    enlarge_in: u64,
18    dict: Vec<Vec<u16>>,
19    res: Vec<u16>,
20    last: (usize, usize),
21}
22
23impl State {
24    fn reset(&mut self) {
25        self.n_bits = 2;
26        self.enlarge_in = 5;
27        self.dict.clear();
28        for i in 0..3 {
29            self.dict.push(vec![i]);
30        }
31        self.res.clear();
32        self.last = (0, 0);
33    }
34}
35
36pub struct Decoder {
37    state: State,
38}
39
40impl Decoder {
41    pub fn new() -> Self {
42        let state = State::default();
43        Decoder { state }
44    }
45
46    pub fn decode_base64_to(&mut self, input: &str, dst: &mut String) -> Result<()> {
47        let reader = RevBitReader::from_iter(base64::DecodeIterator::from_str(input));
48        self.decode_impl(reader, dst)
49    }
50
51    pub fn decode_base64(&mut self, input: &str) -> Result<String> {
52        let mut dst = String::new();
53        self.decode_base64_to(input, &mut dst).and(Ok(dst))
54    }
55
56    pub fn decode_to(&mut self, input: &[u8], dst: &mut String) -> Result<()> {
57        let reader = RevBitReader::from_bytes(input);
58        self.decode_impl(reader, dst)
59    }
60
61    pub fn decode(&mut self, input: &[u8]) -> Result<String> {
62        let mut dst = String::new();
63        self.decode_to(input, &mut dst).and(Ok(dst))
64    }
65
66    pub fn decode_impl<I, E>(&mut self, mut reader: RevBitReader<I>, dst: &mut String) -> Result<()>
67    where
68        E: Into<Error>,
69        I: Iterator<Item = result::Result<u8, E>>,
70    {
71        self.state.reset();
72
73        let slice = self.state.next(&mut reader)?;
74        if slice.is_empty() {
75            return Ok(());
76        }
77
78        self.state.last = (0, 1);
79        self.state.n_bits += 1;
80
81        loop {
82            let before = self.state.res.len();
83            let slice = self.state.next(&mut reader)?;
84            if slice.is_empty() {
85                return self.flush(dst);
86            }
87
88            let mut last = self.state.res[self.state.last.0..self.state.last.1].to_owned();
89            last.push(slice[0]);
90            self.state.add_to_dict(&last);
91
92            self.state.last = (before, self.state.res.len());
93        }
94    }
95
96    fn flush(&mut self, dst: &mut String) -> Result<()> {
97        let chars = self.state.res.iter().map(|u| *u);
98        for chr in decode_utf16(chars) {
99            let chr = chr?;
100            dst.push(chr);
101        }
102
103        Ok(())
104    }
105}
106
107impl State {
108    fn next<I, E>(&mut self, reader: &mut RevBitReader<I>) -> Result<Vec<u16>>
109    where
110        E: Into<Error>,
111        I: Iterator<Item = result::Result<u8, E>>,
112    {
113        let bits = take(reader, self.n_bits)?;
114
115        match bits {
116            0 => self.litteral(reader, 8),
117            1 => self.litteral(reader, 16),
118            2 => Ok(vec![]),
119            c if (c as usize) < self.dict.len() => self.dict_entry(c as usize),
120            c if (c as usize) == self.dict.len() => self.repeat_last(),
121            c => Err(Error::InvalidHeader(c)),
122        }
123    }
124
125    fn litteral<I, E>(&mut self, reader: &mut RevBitReader<I>, n_bits: u8) -> Result<Vec<u16>>
126    where
127        E: Into<Error>,
128        I: Iterator<Item = result::Result<u8, E>>,
129    {
130        let bits = take(reader, n_bits)? as u16;
131        self.add_to_dict(&[bits]);
132        self.res.push(bits);
133        Ok(self.res[self.res.len() - 1..].to_owned())
134    }
135
136    fn dict_entry(&mut self, idx: usize) -> Result<Vec<u16>> {
137        let entry = &self.dict[idx];
138        self.res.extend(entry);
139        Ok(entry.to_owned())
140    }
141
142    fn repeat_last(&mut self) -> Result<Vec<u16>> {
143        let mut value = self.res[self.last.0..self.last.1].to_owned();
144        value.push(value[0]);
145        self.res.extend(value.iter());
146        Ok(value)
147    }
148
149    fn add_to_dict(&mut self, entry: &[u16]) {
150        self.dict.push(entry.to_owned());
151        self.enlarge_in -= 1;
152        if self.enlarge_in == 0 {
153            self.enlarge_in = 1 << self.n_bits;
154            self.n_bits += 1;
155        }
156    }
157}
158
159fn take<I, E>(reader: &mut RevBitReader<I>, n: u8) -> Result<u64>
160where
161    E: Into<Error>,
162    I: Iterator<Item = result::Result<u8, E>>,
163{
164    reader
165        .take(n)
166        .map(|r| r.map_err(Into::into))
167        .unwrap_or(Err(Error::UnexpectedEof))
168}
lz_string/lib.rs

lz_string/
lib.rs
