fbz 0.1.15

Fast parallel compression and decompression for bzip2, gzip, LZ4, tar, and ZIP
Documentation
use std::{hash::Hasher as _, io::{self, Read, Write}, mem};

use twox_hash::XxHash32;

use crate::{EncodeOptions, Error, Result, matchfinder::{HashChain, LatestMatch, match_length}, pipeline::StreamingOrdered};

const MAGIC: u32 = 0x184d_2204;
const WINDOW_SIZE: usize = u16::MAX as usize;
const TARGET_BLOCK_SIZE: usize = 4 * 1024 * 1024;
const MIN_BLOCK_SIZE: usize = 64 * 1024;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct EncodeReport { pub input_len: u64, pub output_len: u64, pub blocks: u64 }

fn invalid(message: impl Into<String>) -> Error { Error::InvalidConfiguration(message.into()) }

fn xxhash32(data: &[u8]) -> u32 {
    let mut hasher = XxHash32::with_seed(0);
    hasher.write(data);
    hasher.finish() as u32
}

fn chain_depth(level: u8) -> usize { match level { 1..=6 => 1, 7 => 4, 8 => 16, 9 => 64, _ => unreachable!() } }

fn write_length(output: &mut Vec<u8>, mut length: usize) {
    while length >= 255 {
        output.push(255);
        length -= 255;
    }
    output.push(length as u8);
}

fn write_sequence(output: &mut Vec<u8>, literals: &[u8], distance: usize, match_length: usize) {
    let literal_nibble = literals.len().min(15);
    let match_base = match_length - 4;
    let match_nibble = match_base.min(15);
    output.push(((literal_nibble << 4) | match_nibble) as u8);
    if literals.len() >= 15 { write_length(output, literals.len() - 15); }
    output.extend_from_slice(literals);
    output.extend_from_slice(&(distance as u16).to_le_bytes());
    if match_base >= 15 { write_length(output, match_base - 15); }
}

fn write_last_literals(output: &mut Vec<u8>, literals: &[u8]) {
    let literal_nibble = literals.len().min(15);
    output.push((literal_nibble << 4) as u8);
    if literals.len() >= 15 { write_length(output, literals.len() - 15); }
    output.extend_from_slice(literals);
}

fn compress_block_fast(input: &[u8]) -> Vec<u8> {
    let mut output = Vec::with_capacity(input.len() / 2);
    let mut finder = LatestMatch::new(WINDOW_SIZE);
    let mut anchor = 0;
    let mut position = 0;
    while position + 12 <= input.len() {
        let max_length = input.len() - position - 5;
        let Some(mut candidate) = finder.insert_and_find(input, position) else { position += 1 + ((position - anchor) >> 6); continue; };
        let distance = position - candidate;
        let mut length = match_length(input, position, candidate, max_length);
        while position > anchor && candidate > 0 && input[position - 1] == input[candidate - 1] {
            position -= 1;
            candidate -= 1;
            length += 1;
        }
        write_sequence(&mut output, &input[anchor..position], distance, length);
        let end = position + length;
        if end >= 2 { finder.insert(input, end - 2); }
        position = end;
        anchor = end;
    }
    write_last_literals(&mut output, &input[anchor..]);
    output
}

fn compress_block_high(input: &[u8], level: u8) -> Vec<u8> {
    let mut output = Vec::with_capacity(input.len() / 2);
    let max_chain = chain_depth(level);
    let mut finder = HashChain::new(input.len(), WINDOW_SIZE, max_chain);
    let mut anchor = 0;
    let mut position = 0;
    while position + 12 <= input.len() {
        let max_length = input.len() - position - 5;
        let (mut length, distance) = finder.best_match(input, position, max_length, 4, max_chain);
        if length == 0 {
            finder.insert(input, position);
            position += 1;
            continue;
        }
        let mut candidate = position - distance;
        while position > anchor && candidate > 0 && input[position - 1] == input[candidate - 1] {
            position -= 1;
            candidate -= 1;
            length += 1;
        }
        write_sequence(&mut output, &input[anchor..position], distance, length);
        let end = position + length;
        if end >= 2 { finder.insert(input, end - 2); }
        position = end;
        anchor = end;
    }
    write_last_literals(&mut output, &input[anchor..]);
    output
}

fn compress_block(input: &[u8], level: u8) -> Vec<u8> { if level <= 6 { compress_block_fast(input) } else { compress_block_high(input, level) } }

struct Block { bytes: Vec<u8>, input_len: usize, stored: bool }

fn encode_block(input: Vec<u8>, level: u8) -> Block {
    let input_len = input.len();
    let encoded = compress_block(&input, level);
    if encoded.len() < input.len() { Block { bytes: encoded, input_len, stored: false } } else { Block { bytes: input, input_len, stored: true } }
}

fn reservation(block_size: usize) -> usize { block_size.saturating_mul(6).saturating_add((1 << 16) * size_of::<u32>()) }

fn selected_block_size(memory_limit: usize) -> Result<usize> {
    let mut size = TARGET_BLOCK_SIZE;
    while size > MIN_BLOCK_SIZE && reservation(size) > memory_limit { size /= 4; }
    if reservation(size) > memory_limit { return Err(invalid(format!("compression memory limit must be at least {} bytes", reservation(size)))); }
    Ok(size)
}

fn descriptor_code(block_size: usize) -> u8 { match block_size { 64_000..=65_536 => 4, 65_537..=262_144 => 5, 262_145..=1_048_576 => 6, _ => 7 } }

pub struct Encoder<W: Write> {
    output: Option<W>, pipeline: StreamingOrdered<Block>, options: EncodeOptions, buffer: Vec<u8>, block_size: usize, reservation: usize,
    content_hash: XxHash32, input_len: u64, output_len: u64, blocks: u64
}

impl<W: Write> Encoder<W> {
    pub fn new(mut output: W, options: EncodeOptions) -> Result<Self> {
        let options = options.validate()?;
        let options = EncodeOptions { level: Some(options.level_or(1)), ..options };
        let block_size = selected_block_size(options.memory_limit)?;
        let reservation = reservation(block_size);
        let workers = options.resolved_threads().min((options.memory_limit / reservation).max(1));
        let flg = 0x64_u8;
        let bd = descriptor_code(block_size) << 4;
        let checksum = (xxhash32(&[flg, bd]) >> 8) as u8;
        output.write_all(&MAGIC.to_le_bytes())?;
        output.write_all(&[flg, bd, checksum])?;
        Ok(Self { output: Some(output), pipeline: StreamingOrdered::new(workers, options.memory_limit, "fbz-lz4-encode")?, options,
            buffer: Vec::with_capacity(block_size), block_size, reservation, content_hash: XxHash32::with_seed(0), input_len: 0, output_len: 7, blocks: 0 })
    }

    fn commit_next(&mut self) -> Result<()> {
        let block = self.pipeline.take_next()?;
        let mut size = block.bytes.len() as u32;
        if block.stored { size |= 1 << 31; }
        let output = self.output.as_mut().unwrap();
        output.write_all(&size.to_le_bytes())?;
        output.write_all(&block.bytes)?;
        self.input_len += block.input_len as u64;
        self.output_len += 4 + block.bytes.len() as u64;
        self.blocks += 1;
        Ok(())
    }

    fn submit_buffer(&mut self) -> Result<()> {
        if self.buffer.is_empty() { return Ok(()); }
        while !self.pipeline.can_submit(self.reservation) { self.commit_next()?; }
        let input = mem::replace(&mut self.buffer, Vec::with_capacity(self.block_size));
        let level = self.options.level.unwrap();
        self.pipeline.submit(self.reservation, move || encode_block(input, level))
    }

    fn flush_blocks(&mut self) -> Result<()> {
        self.submit_buffer()?;
        while self.pipeline.has_pending() { self.commit_next()?; }
        Ok(())
    }

    pub fn finish(mut self) -> Result<(W, EncodeReport)> {
        self.flush_blocks()?;
        let output = self.output.as_mut().unwrap();
        output.write_all(&0_u32.to_le_bytes())?;
        output.write_all(&(self.content_hash.finish() as u32).to_le_bytes())?;
        output.flush()?;
        self.output_len += 8;
        let report = EncodeReport { input_len: self.input_len, output_len: self.output_len, blocks: self.blocks };
        Ok((self.output.take().unwrap(), report))
    }
}

impl<W: Write> Write for Encoder<W> {
    fn write(&mut self, mut bytes: &[u8]) -> io::Result<usize> {
        let total = bytes.len();
        self.content_hash.write(bytes);
        while !bytes.is_empty() {
            let take = bytes.len().min(self.block_size - self.buffer.len());
            self.buffer.extend_from_slice(&bytes[..take]);
            bytes = &bytes[take..];
            if self.buffer.len() == self.block_size { self.submit_buffer().map_err(Error::into_io)?; }
        }
        Ok(total)
    }

    fn flush(&mut self) -> io::Result<()> { self.flush_blocks().map_err(Error::into_io)?; self.output.as_mut().unwrap().flush() }
}

pub fn compress(data: &[u8], options: EncodeOptions) -> Result<Vec<u8>> {
    let mut output = Vec::new();
    compress_to_writer(&mut io::Cursor::new(data), &mut output, options)?;
    Ok(output)
}

pub fn compress_to_writer(input: &mut impl Read, output: &mut impl Write, options: EncodeOptions) -> Result<EncodeReport> {
    let mut encoder = Encoder::new(output, options)?;
    io::copy(input, &mut encoder)?;
    let (_, report) = encoder.finish()?;
    Ok(report)
}