This is my latest effort on RFC 1951 compression ( the widely-supported compression standard ) in Rust. It uses 2 extra threads to compute the LZ77 matches and the checksum in parallel with the Huffman coding. Currently it appears to out-perform the standard Rust library by some margin. On my standard test ( compressing a font file one hundred times ) I get:
flate2 compressed size=149398
flate2 test completed ok, n=100 time elapsed=1235 milli sec.
flate3 compressed size=147204
flate3 test completed ok, n=100 time elapsed=815 milli sec.
( here I have used "flate3" to refer to my implementation ). Incidentally my best effort in C# took ~1700 milli-seconds, so Rust does appear to have a performance edge over C#.
For review, my main question is "how can I make this perform better?", either by going faster, or by compressing better.
This is the main entry point:
use crossbeam::{channel,Receiver};
use crate::matcher;
use crate::matcher::Match;
use crate::bit::BitStream;
use crate::block::Block;
pub struct Options
{
pub dynamic_block_size: bool,
pub block_size: usize,
pub probe_max: usize,
pub lazy_match: bool
}
pub struct Config
{
pub options: Options,
pub pool: scoped_threadpool::Pool
}
impl Config
{
pub fn new() -> Config
{
Config
{
options: Options
{
dynamic_block_size: false,
block_size: 0x2000,
probe_max: 10,
lazy_match: true
},
pool: scoped_threadpool::Pool::new(2)
}
}
}
/// Example:
/// let config = compress::Config::new();
/// let data = [ 1,2,3,4,1,2,3 ];
/// let cb : Vec<u8> = compress::compress( &data, &mut config );
/// println!( "compressed size={}", cb.len() );
pub fn compress( inp: &[u8], c: &mut Config ) -> Vec<u8>
{
let mut out = BitStream::new();
let ( mtx, mrx ) = channel::bounded(1000); // channel for matches
let ( ctx, crx ) = channel::bounded(1); // channel for checksum
let opts = &c.options;
// Execute the match finding, checksum computation and block output in parallel using the scoped thread pool.
c.pool.scoped( |s|
{
s.execute( || { matcher::find( inp, mtx , &opts ); } );
s.execute( || { ctx.send( adler32( &inp ) ).unwrap(); } );
write_blocks( inp, mrx, crx, &mut out, &opts );
} );
out.bytes
}
pub 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; // start of next block
let mut match_start = 0; // start of matches for next block
let mut match_position = 0; // latest match position
let mut mlist : Vec<Match> = Vec::new(); // list of matches
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 // Investigate larger block size.
{
let mut bits = b.bit_size( out );
loop
{
// b2 is a block which starts just after b, same size.
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 );
// b3 covers b and b2 exactly as one block.
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
{
// tune_boundary( b, b2 );
break;
}
b = b3;
bits = bits3;
}
}
block_start = b.input_end;
match_start = b.match_end;
// println!( "block size={} start={} end={}", b.input_end - b.input_start, b.input_start, b.input_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();
}
/// Get matches up to position.
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
}
/// Checksum function per RFC 1950.
pub 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
}
Other modules: Block
use crate::matcher::Match;
use crate::bit::BitStream;
use crate::bit::BitCoder;
use crate::bit::LenCoder;
use crate::inflate::CLEN_ALPHABET;
use crate::inflate::MATCH_OFF;
use crate::inflate::MATCH_EXTRA;
use crate::inflate::DIST_OFF;
use crate::inflate::DIST_EXTRA;
/// Compression of RFC 1951 blocks.
pub 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] )
{
// Counts how many times each symbol is used, also determines exact end of block.
let mut position : usize = self.input_start;
let mut mi = self.match_start;
loop // Through the applicable matches.
{
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;
}
// Compute match and distance codes.
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; // End of block code.
}
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 ); // block type 2 = block encoded with dynamic Huffman codes.
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 ); // End of block code
}
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;
}
// Compute match and distance codes.
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 match info.
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; }
// Compute length encoding.
self.length_pass( false, output );
self.len.bc.compute_bits();
// The length codes are permuted before being stored ( so that # of trailing zeroes is likely to be more ).
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 );
}
} // end impl Block
BitCoder, LenCoder, BitStream )
use crate::col::Heap;
use crate::inflate::reverse;
/// RFC 1951 length-limited Huffman coding.
pub struct BitCoder
{
pub symbols: usize, // Number of symbols to be encoded (input/output).
pub used: Vec<u32>, // Number of times each symbol is used in the block being encoded ( input ).
pub bits: Vec<u8>, // Number of bits used to encode each symbol ( output ).
pub code: Vec<u16>, // Code for each symbol (output).
lim_bits: usize, // Limit on code length ( 15 or 7 for RFC 1951 ).
max_bits: usize, // Maximum code length.
left: Vec<u16>, right: Vec<u16>, // Tree storage.
}
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 ) // Compute bits from used.
{
// First try to compute a Huffman code.
// Most of the time this succeeds, but sometime lim_bits is exceeeded in which case package_merge is used.
// Tree nodes are encoded in a u64 using 32 bits for used count, 8 bits for the tree depth, 16 bits for the id.
// Constants for accessing the bitfields.
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;
// First compute the number of bits to encode each symbol (self.bits), using a Heap.
let mut heap = Heap::<u64>::new( self.symbols as usize );
// Add the leaf nodes to the heap.
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();
// Construct the binary (non-leaf) nodes of the tree.
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 // Keep pairing the lowest frequency (least used) tree nodes.
{
let left = heap.remove();
self.left[ node ] = ( left & IDMASK ) as u16;
let right = heap.remove();
self.right[ node ] = ( right & IDMASK ) as u16;
// Extract depth of left and right nodes ( still shifted though ).
let depth_left = left & DEPTHMASK;
let depth_right = right & DEPTHMASK;
// New node depth is 1 + larger of depth_left and depth_right.
let depth = DEPTHONE + std::cmp::max(depth_left,depth_right);
// Add the new tree node to the heap, as above, Used | Depth | Id
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 );
}
}
}
// Reduce symbol count if there are unused trailing symbols.
while self.symbols > 0 && self.bits[ self.symbols - 1 ] == 0
{
self.symbols -= 1;
}
/*
println!( "computed bits" );
for i in 0..self.symbols
{
if self.bits[i] > 0
{
println!( "symbol={} used={} bits={}", i, self.used[i], self.bits[i] );
}
}
*/
}
fn get_bits( &mut self, mut tree_node: usize, mut depth:u8 )
{
// Walk the tree reading off the number of bits to encode each symbol ( which is depth of tree ).
if tree_node < self.symbols // node is a leaf.
{
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 )
{
// Tree nodes are encoded in a ulong using 16 bits for the id, 32 bits for Used.
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;
// Tree storage.
self.left = vec![ 0; tree_size ];
self.right = vec![ 0; tree_size ];
// First create the leaf nodes for the tree and sort.
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; // Allocator for package (tree node) ids.
for _i in 0..self.lim_bits
{
let mut lix = 0; // Index into leaves.
let mut mix = 0; // Index into merged.
let llen = leaves.len();
let mlen = merged.len();
let mut total = ( llen + mlen ) / 2;
while total > 0
{
// Compute left.
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; }
// Compute right.
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; }
// Package left and right.
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;
}
// Swap merged and next.
std::mem::swap( &mut merged, &mut next );
next.clear();
}
// Calculate the number of bits to encode each symbol.
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 )
{
// Code below is from RFC 1951 page 7.
// bl_count[N] is the number of symbols encoded with N bits.
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;
}
// Find the numerical value of the smallest code for each code length.
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 );
}
// Calculate the result.
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;
}
/*
println!( "computed codes" );
for i in 0..self.symbols
{
if self.bits[i] > 0
{
println!( "symbol={} used={} bits={} code={}", i, self.used[i], self.bits[i], self.code[i] );
}
}
*/
}
} // end impl BitCoder
/// RFC 1951 encoding of lengths.
pub 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,
}
}
// Run length encoding of code lengths - RFC 1951, page 13.
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;
}
}
}
} // end impl LenCoder
/// Output bit stream.
pub struct BitStream
{
buffer: u64,
bits_in_buffer : u8,
pub bytes: Vec<u8>,
}
impl BitStream
{
pub fn new() -> BitStream
{
BitStream
{
buffer: 0,
bits_in_buffer: 0,
bytes: Vec::new()
}
}
/// Write first n bits of value to BitStream, least significant bit is written first.
/// Unused bits of value must be zero, i.e. value must be in range 0 .. 2^n-1.
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;
}
/// Pad output with zero bits to n bit boundary where n is power of 2 in range 1,2,4..64, typically n=8.
pub fn pad( &mut self, n: u8 )
{
let w = self.bits_in_buffer % n;
if w > 0 { self.write( n - w, 0 ); }
}
/// Flush bit buffer to bytes.
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 );
}
} // end impl BitStream
Match, find
use crossbeam::channel::Sender;
use crate::compress;
pub struct Match
{
pub position: usize,
pub length: usize,
pub distance: usize
}
pub fn find( input: &[u8], output: Sender<Match>, opts: &compress::Options )
{
let len = input.len();
if len > MIN_MATCH
{
let mut m = Matcher::new( len );
m.find( input, output, opts );
}
}
// RFC 1951 match ( LZ77 ) limits.
const MIN_MATCH : usize = 3; // The smallest match eligible for LZ77 encoding.
const MAX_MATCH : usize = 258; // The largest match eligible for LZ77 encoding.
const MAX_DISTANCE : usize = 0x8000; // The largest distance backwards in input from current position that can be encoded.
const ENCODE_POSITION : usize = MAX_DISTANCE + 1;
struct Matcher
{
hash_shift: usize,
hash_mask: usize,
hash_table: Vec<usize>
}
impl Matcher
{
fn new( len: usize ) -> 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 ]
}
}
fn find( &mut self, input: &[u8], output: Sender<Match>, opts: &compress::Options ) // LZ77 compression.
{
let limit = input.len() - 2;
let mut link : Vec<usize> = vec!(0; limit);
let mut position = 0; // position in input.
// hash will be hash of three bytes starting at position.
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 // Equivalent to position - ( hash_entry - ENCODE_POSITION ) > MAX_DISTANCE.
{
position += 1;
continue;
}
link[ position ] = hash_entry;
let ( mut match1, mut distance1 ) = self.best_match( input, position, hash_entry - ENCODE_POSITION, &mut link, opts.probe_max );
position += 1;
if match1 < MIN_MATCH { continue; }
// "Lazy matching" RFC 1951 p.15 : if there are overlapping matches, there is a choice over which of the match to use.
// Example: "abc012bc345.... abc345". Here abc345 can be encoded as either [abc][345] or as a[bc345].
// Since a range typically needs more bits to encode than a single literal, choose the latter.
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 !opts.lazy_match { break; }
let ( match2, distance2 ) = self.best_match( input, position, hash_entry - ENCODE_POSITION, &mut link, opts.probe_max );
if match2 > match1 || match2 == match1 && distance2 < distance1
{
match1 = match2;
distance1 = distance2;
position += 1;
}
else { break; }
}
output.send( Match{ position:position-1, length:match1, distance:distance1 } ).unwrap();
let mut copy_end = position - 1 + match1;
if copy_end > limit { copy_end = limit; }
position += 1;
// Advance to end of copied section.
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;
}
}
}
// best_match finds the best match starting at position.
// old_position is from hash table, link [] is linked list of older positions.
fn best_match( &mut self, input: &[u8], position: usize, mut old_position: usize, link: &mut Vec<usize>, mut probe_max: 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 ];
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 )
}
// match_possible is used to try and shorten the best_match search by checking whether
// there is a hash entry for the last 3 bytes of the next longest possible match.
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 ]
}
} // end impl Matcher
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
}
Heap:
/// Heap is an array organised so the smallest element can be efficiently removed.
pub struct Heap<T>{ vec: Vec<T> }
impl<T: Ord+Copy> Heap<T> // Ord+Copy means T can be compared and copied.
{
/* Diagram showing numbering of tree elements.
0
1 2
3 4 5 6
The fundamental invariant is that a parent element is not greater than either child.
H[N] <= H[N*2+1] and H[N] <= H[N*2+2]
*/
/// Create a new heap.
pub fn new( capacity : usize ) -> Heap<T>
{
Heap{ vec: Vec::with_capacity( capacity ) }
}
/// Get the number of elements in the heap.
pub fn count( & self ) -> usize
{
self.vec.len()
}
// add and make allow the heap to be efficiently initialised.
/// Add an element to the array ( not yet a heap ).
pub fn add( &mut self, x: T )
{
self.vec.push( x );
}
/// Make the array into a heap.
pub fn make( &mut self )
{
// Initialise the heap by making every parent not greater than both it's children.
let count = self.vec.len();
let mut parent = count / 2;
while parent > 0
{
parent -= 1;
let mut check = parent;
// Move element at check down while it is greater than a child element.
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;
}
}
/// Insert a new element into the heap.
pub fn insert( &mut self, elem: T )
{
let mut child = self.vec.len();
self.vec.push( elem );
// Move the new element up the tree until it is not less than it's parent.
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;
}
/// Remove and return the smallest element.
pub fn remove ( &mut self ) -> T
{
// The result is element 0.
// The last element in the heap is moved to 0, then moved down until it is not greater than a child.
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
}
} // end impl Heap
