use crossbeam::{channel,Receiver,Sender};
pub struct Options
{
pub dynamic_block_size: bool,
pub block_size: usize,
pub probe_max: usize,
pub lazy_match: bool
}
pub struct Compressor
{
pub options: Options,
pub pool: scoped_threadpool::Pool
}
impl Compressor
{
pub fn new() -> Compressor
{
Compressor
{
options: Options
{
dynamic_block_size: false,
block_size: 0x2000,
probe_max: 10,
lazy_match: true
},
pool: scoped_threadpool::Pool::new(2)
}
}
pub fn deflate( &mut self, inp: &[u8] ) -> Vec<u8>
{
let mut out = BitStream::new( inp.len() );
let ( mtx, mrx ) = channel::bounded(1000);
let ( ctx, crx ) = channel::bounded(1);
let opts = &self.options;
self.pool.scoped( |s|
{
s.execute( || { find_matches( inp, mtx , &opts ); } );
s.execute( || { ctx.send( adler32( &inp ) ).unwrap(); } );
write_blocks( inp, mrx, crx, &mut out, &opts );
} );
out.bytes
}
}
fn write_blocks( inp: &[u8], mrx: Receiver<Match>, crx: Receiver<u32>, out: &mut BitStream, opt: &Options )
{
out.write( 16, 0x9c78 );
let len = inp.len();
let mut block_start = 0;
let mut match_start = 0;
let mut match_position = 0;
let mut mlist : Vec<Match> = Vec::new();
loop
{
let mut block_size = len - block_start;
let mut target_size = opt.block_size;
if block_size > target_size { block_size = target_size; }
let mut b = Block::new( block_start, block_size, match_start );
match_position = get_matches( match_position, b.input_end, &mrx, &mut mlist );
b.init( &inp, &mlist );
if opt.dynamic_block_size
{
let mut bits = b.bit_size( out );
loop
{
block_size = len - b.input_end;
if block_size == 0 { break; }
target_size = b.input_end - b.input_start;
if block_size > target_size { block_size = target_size; }
let mut b2 = Block::new( b.input_end, block_size, b.match_end );
match_position = get_matches( match_position, b2.input_end, &mrx, &mut mlist );
b2.init( &inp, &mlist );
let mut b3 = Block::new( b.input_start, b2.input_end - b.input_start, b.match_start );
b3.init( &inp, &mlist );
let bits2 = b2.bit_size( out );
let bits3 = b3.bit_size( out );
if bits3 > bits + bits2
{
break;
}
b = b3;
bits = bits3;
}
}
block_start = b.input_end;
match_start = b.match_end;
b.write( &inp, &mlist, out, block_start == len );
if b.input_end == len { break; }
}
out.pad(8);
out.write( 32, crx.recv().unwrap() as u64 );
out.flush();
}
fn get_matches( mut match_position: usize, to_position: usize, mrx: &Receiver<Match>, mlist: &mut Vec<Match> ) -> usize
{
while match_position < to_position
{
match mrx.recv()
{
Ok( m ) =>
{
match_position = m.position;
mlist.push( m );
},
Err( _err ) => match_position = usize::MAX
}
}
match_position
}
fn adler32( input: &[u8] ) -> u32
{
let mut s1 = 1;
let mut s2 = 0;
for b in input
{
s1 = ( s1 + *b as u32 ) % 65521;
s2 = ( s2 + s1 ) % 65521;
}
s2 * 65536 + s1
}
struct Match
{
pub position: usize,
pub length: u16,
pub distance: u16
}
fn find_matches( input: &[u8], output: Sender<Match>, opts: &Options )
{
let len = input.len();
if len > MIN_MATCH
{
let mut m = Matcher::new( len, opts );
m.find( input, output );
}
}
const MIN_MATCH : usize = 3;
const MAX_MATCH : usize = 258;
const MAX_DISTANCE : usize = 0x8000;
const ENCODE_POSITION : usize = MAX_DISTANCE + 1;
struct Matcher
{
hash_shift: usize,
hash_mask: usize,
hash_table: Vec<usize>,
probe_max: usize,
lazy_match: bool
}
impl Matcher
{
fn new( len: usize, opts: &Options ) -> Matcher
{
let hash_shift = calc_hash_shift( len * 2 );
let hash_mask = ( 1 << ( MIN_MATCH * hash_shift ) ) - 1;
Matcher{
hash_shift,
hash_mask,
hash_table: vec![ 0; hash_mask + 1 ],
probe_max: opts.probe_max,
lazy_match: opts.lazy_match
}
}
fn find( &mut self, input: &[u8], output: Sender<Match> )
{
let limit = input.len() - 2;
let mut link : Vec<usize> = vec!(0; limit);
let mut position = 0;
let mut hash = ( ( input[ 0 ] as usize ) << self.hash_shift ) + input[ 1 ] as usize;
while position < limit
{
hash = ( ( hash << self.hash_shift ) + input[ position + 2 ] as usize ) & self.hash_mask;
let mut hash_entry = self.hash_table[ hash ];
self.hash_table[ hash ] = position + ENCODE_POSITION;
if position >= hash_entry
{
position += 1;
continue;
}
link[ position ] = hash_entry;
let ( mut match1, mut distance1 ) = self.best_match( input, position, hash_entry - ENCODE_POSITION, &mut link );
position += 1;
if match1 < MIN_MATCH { continue; }
while position < limit
{
hash = ( ( hash << self.hash_shift ) + input[ position + 2 ] as usize ) & self.hash_mask;
hash_entry = self.hash_table[ hash ];
self.hash_table[ hash ] = position + ENCODE_POSITION;
if position >= hash_entry { break; }
link[ position ] = hash_entry;
if !self.lazy_match { break; }
let ( match2, distance2 ) = self.best_match( input, position, hash_entry - ENCODE_POSITION, &mut link );
if match2 > match1 || match2 == match1 && distance2 < distance1
{
match1 = match2;
distance1 = distance2;
position += 1;
}
else { break; }
}
output.send( Match{ position:position-1, length:match1 as u16, distance:distance1 as u16 } ).unwrap();
let mut copy_end = position - 1 + match1;
if copy_end > limit { copy_end = limit; }
position += 1;
while position < copy_end
{
hash = ( ( hash << self.hash_shift ) + input[ position + 2 ] as usize ) & self.hash_mask;
link[ position ] = self.hash_table[ hash ];
self.hash_table[ hash ] = position + ENCODE_POSITION;
position += 1;
}
}
}
fn best_match( &mut self, input: &[u8], position: usize, mut old_position: usize, link: &mut Vec<usize> ) -> ( usize, usize )
{
let mut avail = input.len() - position;
if avail > MAX_MATCH { avail = MAX_MATCH; }
let mut best_match = 0; let mut best_distance = 0;
let mut key_byte = input[ position + best_match ];
let mut probe_max: usize = self.probe_max;
while probe_max > 0
{
if input[ old_position + best_match ] == key_byte
{
let mut mat = 0;
while mat < avail && input[ position + mat ] == input[ old_position + mat ]
{
mat += 1;
}
if mat > best_match
{
best_match = mat;
best_distance = position - old_position;
if best_match == avail || ! self.match_possible( input, position, best_match ) { break; }
key_byte = input[ position + best_match ];
}
}
old_position = link[ old_position ];
if old_position <= position { break; }
old_position -= ENCODE_POSITION;
probe_max -= 1;
}
( best_match, best_distance )
}
fn match_possible( &mut self, input: &[u8], mut position: usize, best_match: usize ) -> bool
{
position = ( position + best_match ) - 2;
let mut hash = ( ( input[ position ] as usize ) << self.hash_shift ) + input[ position + 1 ] as usize;
hash = ( ( hash << self.hash_shift ) + input[ position + 2 ] as usize ) & self.hash_mask;
position < self.hash_table[ hash ]
}
}
fn calc_hash_shift( n: usize ) -> usize
{
let mut p = 1;
let mut result = 0;
while n > p
{
p <<= MIN_MATCH;
result += 1;
if result == 6 { break; }
}
result
}
struct Block
{
pub input_start: usize,
pub input_end: usize,
pub match_start: usize,
pub match_end: usize,
lit: BitCoder, dist: BitCoder, len: LenCoder,
len_symbols: usize,
bits_computed: bool,
}
impl Block
{
pub fn new( input_start: usize, input_count: usize, match_start: usize ) -> Block
{
Block
{
input_start,
input_end: input_start + input_count,
match_start,
match_end: 0,
lit: BitCoder::new( 15, 288 ),
dist: BitCoder::new( 15, 32 ),
len: LenCoder::new( 7, 19 ),
len_symbols: 0,
bits_computed: false,
}
}
pub fn init( &mut self, input: &[u8], mlist: &[Match] )
{
let mut position : usize = self.input_start;
let mut mi = self.match_start;
loop
{
if mi == mlist.len() { break; }
let mat = &mlist[ mi ];
if mat.position >= self.input_end { break; }
while position < mat.position
{
self.lit.used[ input[ position ] as usize ] += 1;
position += 1;
}
position += mat.length as usize;
let mut mc = 0; while mat.length as u16 >= MATCH_OFF[ mc ] { mc += 1; } mc -= 1;
let mut dc = 29; while mat.distance < DIST_OFF[ dc ] { dc -= 1; }
self.lit.used[ 257 + mc ] += 1;
self.dist.used[ dc ] += 1;
mi += 1;
}
self.match_end = mi;
while position < self.input_end
{
self.lit.used[ input[ position ] as usize ] += 1;
position += 1;
}
self.input_end = position;
self.lit.used[ 256 ] += 1;
}
pub fn bit_size( &mut self, output: &mut BitStream ) -> usize
{
self.compute_bits( output );
17 + 3 * self.len_symbols + self.len.bc.total() + self.lit.total() + self.dist.total()
}
pub fn write( &mut self, input: &[u8], mlist: &[Match], output: &mut BitStream, last: bool )
{
self.bit_size( output );
self.lit.compute_codes();
self.dist.compute_codes();
self.len.bc.compute_codes();
output.write( 1, if last {1} else {0} );
output.write( 2, 2 );
output.write( 5, ( self.lit.symbols - 257 ) as u64 );
output.write( 5, ( self.dist.symbols - 1 ) as u64 );
output.write( 4, ( self.len_symbols - 4 ) as u64 );
for alp in &CLEN_ALPHABET[..self.len_symbols]
{
output.write( 3, self.len.bc.bits[ *alp as usize ] as u64 );
}
self.length_pass( true, output );
self.put_codes( input, mlist, output );
output.write( self.lit.bits[ 256 ], self.lit.code[ 256 ] as u64 );
}
fn put_codes( &mut self, input: &[u8], mlist: &[Match], output: &mut BitStream )
{
let mut position = self.input_start;
for mat in &mlist[self.match_start .. self.match_end]
{
while position < mat.position
{
let ib = input[ position ] as usize;
output.write( self.lit.bits[ ib ], self.lit.code[ ib ] as u64 );
position += 1;
}
position += mat.length as usize;
let mut mc = 0; while mat.length >= MATCH_OFF[ mc ] { mc += 1; } mc -= 1;
let mut dc = 29; while mat.distance < DIST_OFF[ dc ] { dc -= 1; }
output.write( self.lit.bits[ 257 + mc ], self.lit.code[ 257 + mc ] as u64 );
output.write( MATCH_EXTRA[ mc ], (mat.length - MATCH_OFF[ mc ]) as u64 );
output.write( self.dist.bits[ dc ], self.dist.code[ dc ] as u64 );
output.write( DIST_EXTRA[ dc ], (mat.distance - DIST_OFF[ dc ]) as u64 );
}
while position < self.input_end
{
let ib = input[ position ] as usize;
output.write( self.lit.bits[ ib ], self.lit.code[ ib ] as u64 );
position += 1;
}
}
fn compute_bits( &mut self, output: &mut BitStream )
{
if self.bits_computed { return; }
self.lit.compute_bits();
self.dist.compute_bits();
if self.dist.symbols == 0 { self.dist.symbols = 1; }
self.length_pass( false, output );
self.len.bc.compute_bits();
self.len_symbols = 19;
while self.len_symbols > 4
&& self.len.bc.bits[ CLEN_ALPHABET[ self.len_symbols - 1 ] as usize ] == 0
{
self.len_symbols -= 1;
}
self.bits_computed = true;
}
fn length_pass( &mut self, last_pass: bool, output: &mut BitStream )
{
self.len.last_pass = last_pass;
self.len.encode_lengths( true, self.lit.symbols, &self.lit.bits, output );
self.len.encode_lengths( false, self.dist.symbols, &self.dist.bits, output );
}
}
struct BitCoder
{
pub symbols: usize,
pub used: Vec<u32>,
pub bits: Vec<u8>,
pub code: Vec<u16>,
lim_bits: usize,
max_bits: usize,
left: Vec<u16>, right: Vec<u16>,
}
impl BitCoder
{
pub fn new( lim_bits: usize, symbols: usize ) -> BitCoder
{
BitCoder
{
symbols,
lim_bits,
max_bits: 0,
used: vec![0;symbols],
bits: vec![0;symbols],
left: vec![0;symbols],
right: vec![0;symbols],
code: Vec::with_capacity( symbols ),
}
}
pub fn compute_bits( &mut self )
{
const USEDBITS : u8 = 32;
const DEPTHBITS : u8 = 8;
const IDBITS : u8 = 16;
const USEDMASK : u64 = ( ( 1 << USEDBITS ) - 1 ) << ( IDBITS + DEPTHBITS );
const DEPTHMASK : u64 = ( ( 1 << DEPTHBITS ) - 1 ) << IDBITS;
const DEPTHONE : u64 = 1 << IDBITS;
const IDMASK : u64 = ( 1 << IDBITS ) - 1;
let mut heap = Heap::<u64>::new( self.symbols as usize );
for id in 0..self.symbols
{
let used = self.used[ id ];
if used > 0
{
heap.add( ( used as u64 ) << ( IDBITS + DEPTHBITS ) | id as u64 );
}
}
heap.make();
let non_zero : usize = heap.count();
match non_zero
{
0 => {}
1 =>
{
self.get_bits( ( heap.remove() & IDMASK ) as usize, 1 );
self.max_bits = 1;
}
_ =>
{
let mut node = 0;
loop
{
let left = heap.remove();
self.left[ node ] = ( left & IDMASK ) as u16;
let right = heap.remove();
self.right[ node ] = ( right & IDMASK ) as u16;
let depth_left = left & DEPTHMASK;
let depth_right = right & DEPTHMASK;
let depth = DEPTHONE + std::cmp::max(depth_left,depth_right);
heap.insert( ( left + right ) & USEDMASK | depth | ( self.symbols + node ) as u64 );
node += 1;
if heap.count() < 2 { break }
}
let root = ( heap.remove() & ( DEPTHMASK | IDMASK ) ) as usize;
self.max_bits = root >> IDBITS;
if self.max_bits <= self.lim_bits
{
self.get_bits( root & IDMASK as usize, 0 );
} else {
self.max_bits = self.lim_bits;
self.package_merge( non_zero );
}
}
}
while self.symbols > 0 && self.bits[ self.symbols - 1 ] == 0
{
self.symbols -= 1;
}
}
fn get_bits( &mut self, mut tree_node: usize, mut depth:u8 )
{
if tree_node < self.symbols
{
self.bits[ tree_node ] = depth;
} else {
tree_node -= self.symbols;
depth += 1;
self.get_bits( self.left[ tree_node ] as usize, depth );
self.get_bits( self.right[ tree_node ] as usize, depth );
}
}
fn package_merge( &mut self, non_zero : usize )
{
const IDBITS : i32 = 16;
const IDMASK : u64 = ( 1 << IDBITS ) - 1;
const USEDBITS : i32 = 32;
const USEDMASK : u64 = ( ( 1 << USEDBITS ) - 1 ) << IDBITS;
let tree_size = self.symbols * self.lim_bits;
self.left = vec![ 0; tree_size ];
self.right = vec![ 0; tree_size ];
let mut leaves : Vec<u64> = Vec::with_capacity( non_zero );
for i in 0..self.symbols
{
let used = self.used[ i ];
if used != 0
{
leaves.push( (used as u64) << IDBITS | i as u64 );
}
}
leaves.sort();
let mut merged = Vec::<u64>::with_capacity( self.symbols );
let mut next = Vec::<u64>::with_capacity( self.symbols );
let mut package : usize = self.symbols;
for _i in 0..self.lim_bits
{
let mut lix = 0;
let mut mix = 0;
let llen = leaves.len();
let mlen = merged.len();
let mut total = ( llen + mlen ) / 2;
while total > 0
{
let mut left : u64;
if mix < mlen
{
left = merged[ mix ];
if lix < llen
{
let leaf = leaves[ lix ];
if left < leaf { mix += 1; }
else { left = leaf; lix += 1; }
}
else { mix += 1; }
}
else { left = leaves[ lix ]; lix += 1; }
let mut right : u64;
if mix < mlen
{
right = merged[ mix ];
if lix < llen
{
let leaf = leaves[ lix ];
if right < leaf { mix += 1; }
else { right = leaf; lix += 1; }
}
else { mix += 1; }
}
else { right = leaves[ lix ]; lix += 1; }
self.left[ package ] = ( left & IDMASK ) as u16;
self.right[ package ] = ( right & IDMASK ) as u16;
next.push( ( left + right ) & USEDMASK | package as u64 );
package += 1;
total -= 1;
}
std::mem::swap( &mut merged, &mut next );
next.clear();
}
for node in merged
{
self.merge_get_bits( ( node & IDMASK ) as usize );
}
}
fn merge_get_bits( &mut self, node : usize )
{
if node < self.symbols
{
self.bits[ node ] += 1;
} else {
self.merge_get_bits( self.left[ node ] as usize );
self.merge_get_bits( self.right[ node ] as usize );
}
}
pub fn total( &mut self ) -> usize
{
let mut result = 0;
for i in 0..self.symbols
{
result += self.used[ i ] as usize * self.bits[ i ] as usize;
}
result
}
pub fn compute_codes( &mut self )
{
let mut bl_count : Vec<u16> = vec![ 0; self.max_bits + 1 ];
for sym in 0..self.symbols
{
bl_count[ self.bits[ sym ] as usize ] += 1;
}
let mut next_code : Vec<u16> = Vec::with_capacity( self.max_bits + 1 );
let mut code : u16 = 0;
bl_count[ 0 ] = 0;
next_code.push( 0 );
for bc in bl_count
{
code = ( code + bc ) << 1;
next_code.push( code );
}
for sym in 0..self.symbols
{
let length = self.bits[ sym ] as usize;
self.code.push( reverse( next_code[ length ] as usize, length ) as u16 );
next_code[ length ] += 1;
}
}
}
struct LenCoder
{
pub bc: BitCoder,
pub last_pass: bool,
previous_length: usize, zero_run: usize, repeat: usize,
}
impl LenCoder
{
pub fn new( limit:usize, symbols:usize ) -> LenCoder
{
LenCoder
{
bc: BitCoder::new( limit, symbols ),
last_pass: false,
previous_length: 0,
zero_run: 0,
repeat: 0,
}
}
pub fn encode_lengths( &mut self, is_lit: bool, count: usize, lengths: &[u8], output: &mut BitStream )
{
if is_lit
{
self.previous_length = 0;
self.zero_run = 0;
self.repeat = 0;
}
for len in &lengths[..count]
{
let length = *len as usize;
if length == 0
{
if self.repeat > 0 { self.encode_repeat( output ); }
self.zero_run += 1;
self.previous_length = 0;
} else if length == self.previous_length {
self.repeat += 1;
} else {
if self.zero_run > 0 { self.encode_zero_run( output ); }
if self.repeat > 0 { self.encode_repeat( output ); }
self.put_length( length, output );
self.previous_length = length;
}
}
if !is_lit
{
self.encode_zero_run( output );
self.encode_repeat( output );
}
}
fn put_length( &mut self, val: usize, output: &mut BitStream )
{
if self.last_pass
{
output.write( self.bc.bits[ val ], self.bc.code[ val ] as u64 );
} else {
self.bc.used[ val ] += 1;
}
}
fn encode_repeat( &mut self, output: &mut BitStream )
{
while self.repeat > 0
{
if self.repeat < 3
{
self.put_length( self.previous_length, output );
self.repeat -= 1;
} else {
let mut x = self.repeat;
if x > 6 { x = 6; }
self.put_length( 16, output );
if self.last_pass
{
output.write( 2, ( x - 3 ) as u64 );
}
self.repeat -= x;
}
}
}
fn encode_zero_run( &mut self, output: &mut BitStream )
{
while self.zero_run > 0
{
if self.zero_run < 3
{
self.put_length( 0, output );
self.zero_run -= 1;
}
else if self.zero_run < 11
{
self.put_length( 17, output );
if self.last_pass { output.write( 3, ( self.zero_run - 3 ) as u64 ); }
self.zero_run = 0;
} else {
let mut x = self.zero_run;
if x > 138 { x = 138; }
self.put_length( 18, output );
if self.last_pass { output.write( 7, ( x - 11 ) as u64 ); }
self.zero_run -= x;
}
}
}
}
struct BitStream
{
buffer: u64,
bits_in_buffer : u8,
pub bytes: Vec<u8>,
}
impl BitStream
{
pub fn new( capacity: usize ) -> BitStream
{
BitStream
{
buffer: 0,
bits_in_buffer: 0,
bytes: Vec::with_capacity( capacity )
}
}
pub fn write( &mut self, mut n: u8, mut value: u64 )
{
if n + self.bits_in_buffer >= 64
{
self.save( value << self.bits_in_buffer | self.buffer );
let space = 64 - self.bits_in_buffer;
value >>= space;
n -= space;
self.buffer = 0;
self.bits_in_buffer = 0;
}
self.buffer |= value << self.bits_in_buffer;
self.bits_in_buffer += n;
}
pub fn pad( &mut self, n: u8 )
{
let w = self.bits_in_buffer % n;
if w > 0 { self.write( n - w, 0 ); }
}
pub fn flush( &mut self )
{
self.pad( 8 );
let mut w = self.buffer;
while self.bits_in_buffer > 0
{
self.bytes.push( ( w & 255 ) as u8 );
w >>= 8;
self.bits_in_buffer -= 8;
}
}
fn save( &mut self, mut w: u64 )
{
let b = &mut self.bytes;
b.push( ( w & 255 ) as u8 ); w >>= 8;
b.push( ( w & 255 ) as u8 ); w >>= 8;
b.push( ( w & 255 ) as u8 ); w >>= 8;
b.push( ( w & 255 ) as u8 ); w >>= 8;
b.push( ( w & 255 ) as u8 ); w >>= 8;
b.push( ( w & 255 ) as u8 ); w >>= 8;
b.push( ( w & 255 ) as u8 ); w >>= 8;
b.push( ( w & 255 ) as u8 );
}
}
struct Heap<T>{ vec: Vec<T> }
impl<T: Ord+Copy> Heap<T>
{
pub fn new( capacity : usize ) -> Heap<T>
{
Heap{ vec: Vec::with_capacity( capacity ) }
}
pub fn count( & self ) -> usize
{
self.vec.len()
}
pub fn add( &mut self, x: T )
{
self.vec.push( x );
}
pub fn make( &mut self )
{
let count = self.vec.len();
let mut parent = count / 2;
while parent > 0
{
parent -= 1;
let mut check = parent;
let elem : T = self.vec[ check ];
loop
{
let mut child = check * 2 + 1;
if child >= count { break }
let mut ce: T = self.vec[ child ];
if child + 1 < count
{
let ce2: T = self.vec[ child + 1 ];
if ce2 < ce { child += 1; ce = ce2; }
}
if ce >= elem { break }
self.vec[ check ] = ce;
check = child;
}
self.vec[ check ] = elem;
}
}
pub fn insert( &mut self, elem: T )
{
let mut child = self.vec.len();
self.vec.push( elem );
while child > 0
{
let parent = ( child - 1 ) >> 1;
let pe: T = self.vec[ parent ];
if elem >= pe { break }
self.vec[ child ] = pe;
child = parent;
}
self.vec[ child ] = elem;
}
pub fn remove ( &mut self ) -> T
{
let result = self.vec[ 0 ];
let last = self.vec.len() - 1;
let elem = self.vec[ last ];
self.vec.pop();
if last > 0
{
let mut parent = 0;
loop
{
let mut child = parent * 2 + 1;
if child >= last { break }
let mut ce = self.vec[ child ];
if child + 1 < last
{
let ce2 = self.vec[ child + 1 ];
if ce2 < ce
{
child += 1;
ce = ce2;
}
}
if ce >= elem { break }
self.vec[ parent ] = ce;
parent = child;
}
self.vec[ parent ] = elem;
}
result
}
}
pub fn inflate( data: &[u8] ) -> Vec<u8>
{
let mut input = InputBitStream::new( &data );
let mut output = Vec::with_capacity( 2 * data.len() );
let _flags = input.get_bits( 16 );
loop
{
let last_block = input.get_bit();
let block_type = input.get_bits( 2 );
match block_type
{
2 => dyn_block( &mut input, &mut output ),
1 => fixed_block( &mut input, &mut output ),
0 => copy_block( &mut input, &mut output ),
_ => ()
}
if last_block != 0 { break; }
}
input.pad( 8 );
let check_sum = input.get_bits(32) as u32;
if adler32( &output ) != check_sum { panic!( "Bad checksum" ) }
output
}
fn dyn_block( input: &mut InputBitStream, output: &mut Vec<u8> )
{
let n_lit = 257 + input.get_bits( 5 );
let n_dist = 1 + input.get_bits( 5 );
let n_len = 4 + input.get_bits( 4 );
let mut len = LenDecoder::new( n_len, input );
let lit : BitDecoder = len.get_decoder( n_lit, input );
let dist : BitDecoder = len.get_decoder( n_dist, input );
loop
{
let x : usize = lit.decode( input );
match x
{
0..=255 => output.push( x as u8 ),
256 => break,
_ =>
{
let mc = x - 257;
let length = MATCH_OFF[ mc ] as usize + input.get_bits( MATCH_EXTRA[ mc ] as usize );
let dc = dist.decode( input );
let distance = DIST_OFF[ dc ] as usize + input.get_bits( DIST_EXTRA[ dc ] as usize );
copy( output, distance, length );
}
}
}
}
fn copy( output: &mut Vec<u8>, distance: usize, mut length: usize )
{
let mut i = output.len() - distance;
while length > 0
{
output.push( output[ i ] );
i += 1;
length -= 1;
}
}
struct BitDecoder
{
nsym: usize,
bits: Vec<u8>,
maxbits: usize,
peekbits: usize,
lookup: Vec<usize>
}
const PEEK : usize = 8;
impl BitDecoder
{
fn new( nsym: usize ) -> BitDecoder
{
BitDecoder
{
nsym,
bits: vec![0; nsym],
maxbits: 0,
peekbits: 0,
lookup: Vec::new()
}
}
fn decode( &self, input: &mut InputBitStream ) -> usize
{
let mut sym = self.lookup[ input.peek( self.peekbits ) ];
if sym >= self.nsym
{
sym = self.lookup[ sym - self.nsym + ( input.peek( self.maxbits ) >> self.peekbits ) ];
}
input.advance( self.bits[ sym ] as usize );
sym
}
fn init_lookup( &mut self )
{
let mut max_bits : usize = 0;
for bp in &self.bits
{
let bits = *bp as usize;
if bits > max_bits { max_bits = bits; }
}
self.maxbits = max_bits;
self.peekbits = if max_bits > PEEK { PEEK } else { max_bits };
self.lookup.resize( 1 << self.peekbits, 0 );
let mut bl_count : Vec<usize> = vec![ 0; max_bits + 1 ];
for sym in 0..self.nsym { bl_count[ self.bits[ sym ] as usize ] += 1; }
let mut next_code : Vec<usize> = vec![ 0; max_bits + 1 ];
let mut code = 0;
bl_count[ 0 ] = 0;
for i in 0..max_bits
{
code = ( code + bl_count[ i ] ) << 1;
next_code[ i + 1 ] = code;
}
for sym in 0..self.nsym
{
let length = self.bits[ sym ] as usize;
if length != 0
{
self.setup_code( sym, length, next_code[ length ] );
next_code[ length ] += 1;
}
}
}
fn setup_code( &mut self, sym: usize, len: usize, mut code: usize )
{
if len <= self.peekbits
{
let diff = self.peekbits - len;
code <<= diff;
for i in code..code + (1 << diff)
{
self.lookup[ reverse( i, self.peekbits ) ] = sym;
}
} else {
let peekbits2 = self.maxbits - self.peekbits;
let diff1 = len - self.peekbits;
let key = reverse( code >> diff1, self.peekbits );
code &= ( 1 << diff1 ) - 1;
let mut base = self.lookup[ key ];
if base == 0
{
base = self.lookup.len();
self.lookup.resize( base + ( 1 << peekbits2 ), 0 );
self.lookup[ key ] = self.nsym + base;
} else {
base -= self.nsym;
}
let diff = self.maxbits - len;
code <<= diff;
for i in code..code + (1<<diff)
{
self.lookup[ base + reverse( i, peekbits2 ) ] = sym;
}
}
}
}
struct LenDecoder
{
plenc: u8,
rep: usize,
bd: BitDecoder
}
impl LenDecoder
{
fn new( n_len: usize, input: &mut InputBitStream ) -> LenDecoder
{
let mut result = LenDecoder { plenc: 0, rep:0, bd: BitDecoder::new( 19 ) };
for i in CLEN_ALPHABET.iter().take( n_len )
{
result.bd.bits[ *i as usize ] = input.get_bits(3) as u8;
}
result.bd.init_lookup();
result
}
fn get_decoder( &mut self, nsym: usize, input: &mut InputBitStream ) -> BitDecoder
{
let mut result = BitDecoder::new( nsym );
let bits = &mut result.bits;
let mut i = 0;
while self.rep > 0 { bits[ i ] = self.plenc; i += 1; self.rep -= 1; }
while i < nsym
{
let lenc = self.bd.decode( input ) as u8;
if lenc < 16
{
bits[ i ] = lenc;
i += 1;
self.plenc = lenc;
} else {
if lenc == 16 { self.rep = 3 + input.get_bits(2); }
else if lenc == 17 { self.rep = 3 + input.get_bits(3); self.plenc=0; }
else if lenc == 18 { self.rep = 11 + input.get_bits(7); self.plenc=0; }
while i < nsym && self.rep > 0 { bits[ i ] = self.plenc; i += 1; self.rep -= 1; }
}
}
result.init_lookup();
result
}
}
struct InputBitStream<'a>
{
data: &'a [u8],
pos: usize,
buf: usize,
got: usize,
}
impl <'a> InputBitStream<'a>
{
fn new( data: &'a [u8] ) -> InputBitStream
{
InputBitStream { data, pos: 0, buf: 1, got: 0 }
}
fn peek( &mut self, n: usize ) -> usize
{
while self.got < n
{
self.buf |= ( self.data[ self.pos ] as usize ) << self.got;
self.pos += 1;
self.got += 8;
}
self.buf & ( ( 1 << n ) - 1 )
}
fn advance( &mut self, n:usize )
{
self.buf >>= n;
self.got -= n;
}
fn get_bit( &mut self ) -> usize
{
if self.got == 0 { self.peek( 1 ); }
let result = self.buf & 1;
self.advance( 1 );
result
}
fn get_bits( &mut self, n: usize ) -> usize
{
let result = self.peek( n );
self.advance( n );
result
}
fn get_huff( &mut self, mut n: usize ) -> usize
{
let mut result = 0;
while n > 0
{
result = ( result << 1 ) + self.get_bit();
n -= 1;
}
result
}
fn pad( &mut self, n: usize )
{
self.got -= self.got % n;
}
}
fn reverse( mut x:usize, mut n: usize ) -> usize
{
let mut result: usize = 0;
while n > 0
{
result = ( result << 1 ) | ( x & 1 );
x >>= 1;
n -= 1;
}
result
}
fn copy_block( input: &mut InputBitStream, output: &mut Vec<u8> )
{
input.pad( 8 );
let mut n = input.get_bits( 16 );
let _n1 = input.get_bits( 16 );
while n > 0 { output.push( input.data[ input.pos ] ); n -= 1; input.pos += 1; }
}
fn fixed_block( input: &mut InputBitStream, output: &mut Vec<u8> )
{
loop
{
let mut x = input.get_huff( 7 );
if x <= 23
{
x += 256;
} else {
x = ( x << 1 ) + input.get_bit();
if x <= 191 { x -= 48; }
else if x <= 199 { x += 88; }
else { x = ( x << 1 ) + input.get_bit() - 256; }
}
match x
{
0..=255 => { output.push( x as u8 ); }
256 => { break; }
_ =>
{
x -= 257;
let length = MATCH_OFF[x] as usize + input.get_bits( MATCH_EXTRA[ x ] as usize );
let dcode = input.get_huff( 5 );
let distance = DIST_OFF[dcode] as usize + input.get_bits( DIST_EXTRA[dcode] as usize );
copy( output, distance, length );
}
}
}
}
static CLEN_ALPHABET : [u8; 19] = [ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 ];
static MATCH_OFF : [u16; 30] = [ 3,4,5,6, 7,8,9,10, 11,13,15,17, 19,23,27,31, 35,43,51,59,
67,83,99,115, 131,163,195,227, 258, 0xffff ];
static MATCH_EXTRA : [u8; 29] = [ 0,0,0,0, 0,0,0,0, 1,1,1,1, 2,2,2,2, 3,3,3,3, 4,4,4,4, 5,5,5,5, 0 ];
static DIST_OFF : [u16; 30] = [ 1,2,3,4, 5,7,9,13, 17,25,33,49, 65,97,129,193, 257,385,513,769,
1025,1537,2049,3073, 4097,6145,8193,12289, 16385,24577 ];
static DIST_EXTRA : [u8; 30] = [ 0,0,0,0, 1,1,2,2, 3,3,4,4, 5,5,6,6, 7,7,8,8, 9,9,10,10, 11,11,12,12, 13,13 ];