% divANS Module

Overview

The divANS crate is meant to be used for generic data compression. The algorithm has been tuned to significantly favor gains in compression ratio over performance, operating at line speeds of 150 Mbit/s.

The name originates from "divided-ANS" since the intermediate representation is divided from the ANS codec

More information at https://blogs.dropbox.com/tech/2018/06/building-better-compression-together-with-divans/

Divans should primarily be considered for cold storage and compression research. The compression algorithm is highly modular and new algorithms only need to be written a single time since generic trait specialization constructs optimized variants of the codec for both compression and decompression at compile time.

Rust Usage

Decompression

extern crate divans;
fn main() {
    use std::io;
    let stdin = &mut io::stdin();
    {
        use std::io::{Read, Write};
        let mut reader = divans::DivansDecompressorReader::new(
            stdin,
            4096, // buffer size
        );
        io::copy(&mut reader, &mut io::stdout()).unwrap();
    }   
}

Compression

extern crate divans;
fn main() {
    use std::io;
    let stdout = &mut io::stdout();
    {
        use std::io::{Read, Write};
        let mut writer = divans::DivansBrotliHybridCompressorWriter::new(
            stdout,
            divans::DivansCompressorOptions{
                literal_adaptation:None, // should we override how fast the cdfs converge for literals?
                window_size:Some(22), // log 2 of the window size
                lgblock:None, // should we override how often metablocks are created in brotli
                quality:Some(11), // the quality of brotli commands
                dynamic_context_mixing:Some(2), // if we want to mix together the stride prediction and the context map
                use_brotli:divans::BrotliCompressionSetting::default(), // ignored
                use_context_map:true, // whether we should use the brotli context map in addition to the last 8 bits of each byte as a prior
                force_stride_value: divans::StrideSelection::UseBrotliRec, // if we should use brotli to decide on the stride
            },
            4096, // internal buffer size
        );
        io::copy(&mut io::stdin(), &mut writer).unwrap();
        writer.flush().unwrap();
    }
}

C usage

The C api is a standard compression API like the one that zlib provides. Despite being rust code, no allocations are made unless the CAllocator struct is passed in with the custom_malloc field set to NULL. This means that any user of the divans library may provide their own allocation system and all allocations will go through that allocation system. The pointers returned by custom_malloc must be 32-byte aligned.

Compression

#include "divans/ffi.h"
// compress to stdout
DivansResult compress(const unsigned char *data, size_t len) {
    unsigned char buf[4096];
    struct CAllocator alloc = {custom_malloc, custom_free, custom_alloc_opaque}; // set all 3 to NULL to use rust allocators
    struct DivansCompressorState *state = divans_new_compressor_with_custom_alloc(alloc);
    divans_set_option(state, DIVANS_OPTION_USE_CONTEXT_MAP, 1);
    divans_set_option(state, DIVANS_OPTION_DYNAMIC_CONTEXT_MIXING, 2);
    divans_set_option(state, DIVANS_OPTION_QUALITY, 11);
    while (len) {
        size_t read_offset = 0;
        size_t buf_offset = 0;
        DivansResult res = divans_encode(state,
                                         data, len, &read_offset,
                                         buf, sizeof(buf), &buf_offset);
        if (res == DIVANS_FAILURE) {
            divans_free_compressor(state);
            return res;
        }
        data += read_offset;
        len -= read_offset;
        fwrite(buf, buf_offset, 1, stdout);
    }
    DivansResult res;
    do {
        size_t buf_offset = 0;
        res = divans_encode_flush(state,
                                  buf, sizeof(buf), &buf_offset);
        if (res == DIVANS_FAILURE) {
            divans_free_compressor(state);
            return res;
        }
        fwrite(buf, buf_offset, 1, stdout);
    } while(res != DIVANS_SUCCESS);
    divans_free_compressor(state);
    return DIVANS_SUCCESS;
}

Decompression

#include "divans/ffi.h"
//decompress to stdout
DivansResult decompress(const unsigned char *data, size_t len) {
    unsigned char buf[4096];
    struct CAllocator alloc = {custom_malloc, custom_free, custom_alloc_opaque}; // set all 3 to NULL for using rust allocators
    struct DivansDecompressorState *state = divans_new_decompressor_with_custom_alloc(alloc);
    DivansResult res;
    do {
        size_t read_offset = 0;
        size_t buf_offset = 0;
        res = divans_decode(state,
                            data, len, &read_offset,
                            buf, sizeof(buf), &buf_offset);
        if (res == DIVANS_FAILURE || (res == DIVANS_NEEDS_MORE_INPUT && len == 0)) {
            divans_free_decompressor(state);
            return res;
        }
        data += read_offset;
        len -= read_offset;
        fwrite(buf, buf_offset, 1, stdout);
    } while (res != DIVANS_SUCCESS);
    divans_free_decompressor(state);
    return DIVANS_SUCCESS;
}

Structure of the divANS codebase

Top Level Modules

| Module | Purpose | |:------: |-------| | probability | Optimized implementations of 16-wide 4-bit CDF's that support online training and renormalization | | codec/interface | CrossCommandState tracks data to be kept between brotli commands. Examples include CDF's, the previous few bytes, the ring buffer for copies, etc | | codec/dict | Encode/decode parts of the file that may arise from the included brotli dictionary | | codec/copy | Encode/decode parts of the file that have already been seen before and are still in the ring buffer | | codec/block_type | Encode/decode markers in the file which divans can use as a prior for literals, distances or even command type | | codec/context_map | Encode/decode the brotli context_map which remaps the previous 6 bits and literal_block_type to a prior between 0 and 255 | | codec/literal | Encode/decode new raw data that appears in the file. This can use a number of strategies or combinations of strategies to encode each nibble | | codec/priors | Structs defining the size of the tables that contain dynamically-trained CDF holding statistics about past-data. | | codec/weights | struct that blend between multiple CDFs based on prior efficacy | | codec/specializations | Optimization system to generate separate codepaths for currently-running nibble-decode or encode path, based on which priors were selected | | codec | Encode/decode the overall commands themselves and track the state of the compression of the overall file and if it is complete | | divans_decompressor | Implementation of Decompressor trait that parses divans headers and translates the ANS stream into commands and into raw data | | brotli_ir_gen | Implementation of Compressor trait that calls into the brotli codec and extracts the command array per metablock to be encoded | | divans_compressor | Alternate implementation of Compressor trait that calls into raw_to_cmd instead of brotli to get the command array per metablock | | divans_to_raw | DecoderSpecialization for the codec to assume default input commands and incrementally populate them | | cmd_to_divans | EncoderSpecialization for the codec to take input commands and produce divans | | raw_to_cmd | Future: a substitute for the Brotli compressor to generate commands | | cmd_to_raw | Interpret a list of Brotli commands and produce the uncompressed file | | arithmetic_coder | Define EntropyEncoder and EntropyDecoder arithmetic coder traits | | ans | Fast implementation of EntropyEncoder and EntropyDecoder interfaces | | billing | Plugin to add attribution to an ArithmeticEncoderOrDecoder by providing the same interface and wrapping the en/decoder | | alloc_util | Allocator that reuses a single slice of memory over many allocations | | slice_util | A mechanism to borrow and reference an existing slice that can be frozen, unborrowing the slice, when divans returns to the caller to request more input or output space | | resizable_buffer | Simple resizing byte buffer that can hold the raw input and output streams being processed | | reader | Read implementation for both encoding and decoding of divans | | writer | Write implementation for both encoding and decoding of divans |

Overall flow

To Encode a file,

• a writer::DivansBrotliHybridCompressorWriter instantiates a brotli_ir_gen::BrotliDivansHybridCompressor
• The compressor has both a brotli::BrotliEncoderStateStruct from the brotli crate as well as a codec::DivansCodec<ANSEncoder, EncodeSpecialization>.
• Using brotli_ir_gen::BrotliDivansHybridCompressor::encode, the compressor feeds input data into the brotli::BrotliEncoderStateStruct
  • by calling brotli::BrotliEncoderCompressStream
• brotli::BrotliEncoderCompressStream can trigger a callback into brotli_ir_gen::BrotliDivansHybridCompressor::divans_encode_commands
  • The callback will consist of a slice of brotli::interface::Command items
  • These items are fed into the codec::DivansCodec<ANSEncoder, EncodeSpecialization>::encode_or_decode, which encodes them into divans format.
    • codec::DivansCodec<ANSEncoder, cmd_to_divans::EncoderSpecialization>::encode_or_decode accomplishes this by using the EncoderSpecialization to pull input commands as the source of truth
    • unfortunately brotli can pass as much data as it wishes to the caller, up to the maximum metablock size of 16 megs.