implode/
symbol.rs

1use std::result;
2
3#[derive(Debug)]
4#[derive(PartialEq)]
5#[derive(Copy)]
6#[derive(Clone)]
7/// Represents a symbol in the Implode bit stream.
8pub enum Symbol {
9    /// A literal byte or ASCII character.
10    Literal(u8),
11    /// A length/distance pair, according to LZ77.
12    Pair {distance: u32, length: u32},
13    /// The end symbol. Represents the end of the Implode data.
14    End
15}
16
17impl Eq for Symbol {}
18
19/// A simple trait that allows an object to be converted to bit form.
20pub trait ToBits {
21    /// Serializes this structure to at most 32 bits.
22    fn to_bits(&self) -> u32;
23    /// Returns the amount of bits in this structure when serialized.
24    fn size_bits(&self) -> u32;
25}
26
27macro_rules! bitmask {
28	($bits:expr) => ((1<<$bits)-1)
29}
30
31#[derive(Debug)]
32/// Represents the output of bit decoding.
33pub struct BitDecodeOutput<T> {
34    /// The decoded object.
35    pub decoded: T,
36    /// Amount of bits consumed from the bit stream.
37    pub used_bits: u32
38}
39
40#[derive(Debug)]
41/// Represents an error decoding bits.
42pub enum BitDecodeError {
43    /// Error when the available bits are insufficent.
44    /// Contains the amount of additional bits needed.
45    NotEnoughBits(u32)
46}
47
48/// Result of calling an implode function.
49pub type Result<T> = result::Result<T, BitDecodeError>;
50
51/// Initialization data for the Length decode table.
52pub struct LenInit {
53    pub len_bits: [u8; 16],
54    pub len_code: [u8; 16]
55}
56
57/// Initialization data for the Distance decode table.
58pub struct DistInit {
59    pub dist_bits: [u8; 64],
60    pub dist_code: [u8; 64]
61}
62
63/// Initialization data for the Shannon-Fano literal decode table.
64pub struct ShannonInit {
65    /// Amount of bits for each code.
66    pub shan_bits: [u8; 256],
67    /// The codes.
68    /// Use the byte you want to encode as the index.
69    pub shan_code: [u16; 256]
70}
71
72/// Contains decoding data, used in decode_bits.
73pub struct CodeTable {
74    pub extra_len_bits: [u8; 16],
75    pub len_base: [u16; 16],
76    pub len_add: [u16; 16],
77    pub len_bits: [u8; 16],
78    pub len_codes: [u8; 256],
79
80    pub dist_bits: [u8; 64],
81    pub dist_codes: [u8; 256],
82    
83    pub shan_lut: [u8; 256],
84    pub shan_4_lut: [u8; 256],
85    pub shan_6_lut: [u8; 128],
86    pub shan_8_lut: [u8; 256], 
87}
88
89/// Contains encoding data.
90pub struct EncodeTable {
91    pub lit_bits: [u8; 256],
92    pub lit_code: [u16; 256],
93    pub len_bits: [u8; 518],
94    pub len_code: [u16; 518],
95    pub dist_bits: [u8; 64],
96    pub dist_code: [u8; 64],
97    pub dict_bits: u32
98}
99
100/// The default code table, contains settings used by the standard PKWARE DCL.
101/// Use this if you need to read files compressed by the DCL.
102pub static DEFAULT_CODE_TABLE: CodeTable = CodeTable {
103    extra_len_bits: [0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8],
104    len_base:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 14, 22, 38, 70, 134, 262],
105    len_add:  [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 11, 26, 57, 120, 247],
106    len_bits:  [3, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 7],
107    len_codes: [15, 2, 5, 1, 8, 0, 3, 1, 10, 2, 4, 1, 6, 0, 3, 1, 12, 2, 5, 1, 7, 0, 3, 1, 9, 2, 4, 1, 6, 0, 3, 1, 
108                13, 2, 5, 1, 8, 0, 3, 1, 10, 2, 4, 1, 6, 0, 3, 1, 11, 2, 5, 1, 7, 0, 3, 1, 9, 2, 4, 1, 6, 0, 3, 1, 
109                14, 2, 5, 1, 8, 0, 3, 1, 10, 2, 4, 1, 6, 0, 3, 1, 12, 2, 5, 1, 7, 0, 3, 1, 9, 2, 4, 1, 6, 0, 3, 1, 
110                13, 2, 5, 1, 8, 0, 3, 1, 10, 2, 4, 1, 6, 0, 3, 1, 11, 2, 5, 1, 7, 0, 3, 1, 9, 2, 4, 1, 6, 0, 3, 1, 
111                15, 2, 5, 1, 8, 0, 3, 1, 10, 2, 4, 1, 6, 0, 3, 1, 12, 2, 5, 1, 7, 0, 3, 1, 9, 2, 4, 1, 6, 0, 3, 1, 
112                13, 2, 5, 1, 8, 0, 3, 1, 10, 2, 4, 1, 6, 0, 3, 1, 11, 2, 5, 1, 7, 0, 3, 1, 9, 2, 4, 1, 6, 0, 3, 1, 
113                14, 2, 5, 1, 8, 0, 3, 1, 10, 2, 4, 1, 6, 0, 3, 1, 12, 2, 5, 1, 7, 0, 3, 1, 9, 2, 4, 1, 6, 0, 3, 1, 
114                13, 2, 5, 1, 8, 0, 3, 1, 10, 2, 4, 1, 6, 0, 3, 1, 11, 2, 5, 1, 7, 0, 3, 1, 9, 2, 4, 1, 6, 0, 3, 1],
115
116    dist_bits:  [2, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
117                 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8],    
118    dist_codes: [63, 6, 23, 0, 39, 2, 14, 0, 47, 4, 18, 0, 31, 1, 10, 0, 55, 5, 20, 0, 35, 2, 12, 0, 43, 3, 16, 0, 27, 1, 8, 0, 
119				 59, 6, 21, 0, 37, 2, 13, 0, 45, 4, 17, 0, 29, 1, 9,  0, 51, 5, 19, 0, 33, 2, 11, 0, 41, 3, 15, 0, 25, 1, 7, 0, 
120				 61, 6, 22, 0, 38, 2, 14, 0, 46, 4, 18, 0, 30, 1, 10, 0, 53, 5, 20, 0, 34, 2, 12, 0, 42, 3, 16, 0, 26, 1, 8, 0, 
121				 57, 6, 21, 0, 36, 2, 13, 0, 44, 4, 17, 0, 28, 1, 9,  0, 49, 5, 19, 0, 32, 2, 11, 0, 40, 3, 15, 0, 24, 1, 7, 0, 
122				 62, 6, 23, 0, 39, 2, 14, 0, 47, 4, 18, 0, 31, 1, 10, 0, 54, 5, 20, 0, 35, 2, 12, 0, 43, 3, 16, 0, 27, 1, 8, 0, 
123				 58, 6, 21, 0, 37, 2, 13, 0, 45, 4, 17, 0, 29, 1, 9,  0, 50, 5, 19, 0, 33, 2, 11, 0, 41, 3, 15, 0, 25, 1, 7, 0, 
124				 60, 6, 22, 0, 38, 2, 14, 0, 46, 4, 18, 0, 30, 1, 10, 0, 52, 5, 20, 0, 34, 2, 12, 0, 42, 3, 16, 0, 26, 1, 8, 0, 
125				 56, 6, 21, 0, 36, 2, 13, 0, 44, 4, 17, 0, 28, 1, 9,  0, 48, 5, 19, 0, 32, 2, 11, 0, 40, 3, 15, 0, 24, 1, 7, 0],
126    
127    shan_lut: [0; 256], //todo
128    shan_4_lut: [0; 256],//todo
129    shan_6_lut: [0; 128],//todo
130    shan_8_lut: [0; 256],//todo
131};
132
133/// Length value of end literal
134pub const END: u32 = 517;
135
136/*pub fn symbol_to_bits(symbol: Symbol, _table: &EncodeTable) -> u32 {
137    match symbol {
138        Symbol::Literal(byte) => ((byte as u32) << 1) | 1,
139        Symbol::Pair{ distance, length} => unimplemented!(),
140        Symbol::End => unimplemented!()
141    }
142}
143
144pub fn symbol_bits(symbol: Symbol, table: &EncodeTable) -> u32 {
145    match symbol {
146        Symbol::Literal(byte) => table.lit_bits[byte as usize] as u32,
147        Symbol::Pair{distance: dist, length: len} => {
148            (table.len_bits[(len as usize)-1] as u32) + 
149            if len==2 {
150                (table.dist_bits[(dist >> 2) as usize] as u32) + 2
151            } else {
152                (table.dist_bits[(dist >> table.dict_bits) as usize] as u32) + table.dict_bits
153            }
154        },
155        Symbol::End => table.len_bits[517] as u32
156    }
157}*/
158
159/// Decodes the input bits into a symbol.
160///
161/// decode_bits is the core of the decompression. It takes in the bit buffer, code table, and dict_bits, and outputs 1 decoded symbol.
162/// nbits should reflect the amount of bits in the bit buffer, but is only used for error checking. dict_bits is the real dict_bits - 6,
163/// because it represents the literal dict bits. (6 bits are always coded using Shannon Fano codes.) For example, a dictionary size of 4096 (2^12)
164/// would have a dict_bits value of 6 because 12 - 6 is 6. Beware that this value is limited from 4 to 6 in the PKWARE® implementation.
165/// This implementation has no such restriction.
166///
167/// # Examples
168///
169/// ```
170/// use implode;
171/// 
172/// assert_eq!(implode::Symbol::Literal(0), implode::decode_bits(0, 9, &implode::DEFAULT_CODE_TABLE));
173/// ```
174///
175/// # Errors
176/// 
177/// If nbits is less than 1, returns BitDecodeError::NotEnoughBits(1).
178/// If the bit stream indicates a literal, and nbits is less than 9, returns BitDecodeError::NotEnoughBits(9-nbits).
179/// 
180pub fn decode_bits(bits: u64, nbits: u32, table: &CodeTable, dict_bits: u32) -> Result<BitDecodeOutput<Symbol>> {
181    let is_pair: u64 = bits&1;
182    let next_byte: u64 = (bits>>1)&0xFF;
183	let mut used_bits;
184
185    let sym = if is_pair==1 {
186	    let code: u32 = table.len_codes[next_byte as usize] as u32;
187	    let code_bits: u32 = table.len_bits[code as usize] as u32;
188	    let extra_bits: u32 = table.extra_len_bits[code as usize] as u32;
189	    
190		used_bits = code_bits + extra_bits + 1;
191	    
192		//Shift the bits over by 1+code_bits (used bits so far), and then create a bitmask from extra_bits.
193		let extra: u64 = (bits>>(1+code_bits)) & bitmask!(extra_bits);
194        
195	    let length = if extra_bits>0 {table.len_add[code as usize] as u32} else {0} + code + (extra as u32);
196        
197        if length == END {
198        	if nbits<used_bits {
199		        return Err(BitDecodeError::NotEnoughBits(used_bits-nbits))
200		    }
201        	
202        	return Ok(BitDecodeOutput::<Symbol>{decoded: Symbol::End, used_bits: used_bits})
203        }
204        
205        // Now decode the distance. This is encoded like DEFLATE distances,
206        // where there is a coded part and a literal part.
207        
208        let dist_code: u8 = table.dist_codes[((bits>>used_bits)&0xFF) as usize];
209        
210        let add_bits: u32 = if length==0 {2} else {dict_bits};
211        used_bits = used_bits+(table.dist_bits[dist_code as usize] as u32);
212        
213        let distance: u32 = ((dist_code as u32) << add_bits) | (((bits>>used_bits) & bitmask!(add_bits)) as u32);
214        
215        used_bits = used_bits + add_bits;
216        Symbol::Pair{distance: distance + 1, length: length + 2}
217    } else {
218    	used_bits = 9;
219        Symbol::Literal(next_byte as u8)
220    };
221
222	if nbits<used_bits {
223        return Err(BitDecodeError::NotEnoughBits(used_bits-nbits))
224    }
225
226    Ok(BitDecodeOutput::<Symbol>{decoded: sym, used_bits: used_bits})
227}
implode/symbol.rs

implode/
symbol.rs
