Understanding Seekable Bitstreams and Independent Block Decompression in Kanzi

Kanzi's C++ implementation treats compressed files as sequences of independent blocks, enabling O(1) random access and parallel decompression through the kanzi::Seekable interface and self-contained block codecs.

The Kanzi compression library (flanglet/kanzi-cpp) achieves high-performance data processing by implementing seekable bitstreams and independent block decompression. This architecture allows decompressors to jump to arbitrary blocks without processing preceding data, while enabling trivial parallelization across multiple CPU cores. Understanding these mechanisms requires examining the Seekable abstraction, the self-describing block format, and the thread-pool orchestration in the decompression pipeline.

The Seekable Interface and Bitstream Abstraction

Random-access support in Kanzi centers on the kanzi::Seekable interface defined in src/Seekable.hpp. This abstract base class establishes the contract for bit-level positioning:

// src/Seekable.hpp
class Seekable
{
public:
    virtual int64 tell() = 0;          // current position in bits
    virtual bool  seek(int64 pos) = 0; // move to a new bit position
    virtual ~Seekable() {}
};

Both the default input and output bit-stream implementations inherit from this base, providing the foundation for non-sequential access patterns.

DefaultInputBitStream Implementation

The DefaultInputBitStream class in src/bitstream/DefaultInputBitStream.hpp reads bits from an underlying InputStream while maintaining a byte buffer and bit cursor. Its seek() implementation can jump to any byte-aligned position (where pos & 7 == 0), flushing internal buffers and repositioning the file descriptor. This allows the decompressor to abandon the current block and reposition to the start of any other block without reading intermediate data.

DefaultOutputBitStream Implementation

Similarly, DefaultOutputBitStream in src/bitstream/DefaultOutputBitStream.hpp handles write operations. When seek() is invoked, the implementation flushes the internal buffer, aligns to the nearest byte boundary, and moves the underlying stream position. This symmetry ensures that compressed files can be both read and written with random access capabilities during construction.

Block Layout and Self-Contained Structure

A Kanzi file consists of a global header followed by one or more compressed blocks. Each block contains its own codec configuration—including the BWT primary index size—making it entirely self-contained. The global header supplies metadata such as the total number of blocks and the uniform block size used during compression, enabling the decompressor to calculate exact byte offsets for any block index.

Independent Block Decompression Architecture

The BlockDecompressor class orchestrates the per-block workflow without maintaining state between blocks. This independence is crucial for both seekability and parallelism.

BlockDecompressor Workflow

The decompression process follows a strict pipeline as implemented in src/app/BlockDecompressor.cpp:

• Header parsing: The decompress method (lines 64-90) reads the global block size and total block count from the file header.
• Task creation: For each input file, the decompressor instantiates a FileDecompressTask (lines 31-34), which internally constructs a CompressedInputStream capable of block-by-block reading.
• Block decoding: Inside FileDecompressTask::run, the stream reads individual blocks and invokes the associated transform codec. Because each block carries its own decoding parameters, no state is shared between sequential or concurrent block operations (lines 644-680).
• Parallel distribution: When jobs > 1, a ThreadPool distributes FileDecompressTask instances across worker threads (lines 334-363), with each task processing its assigned blocks sequentially.

BWTBlockCodec and Self-Describing Blocks

The BWTBlockCodec class in src/transform/BWTBlockCodec.hpp implements the transform layer for individual blocks:

class BWTBlockCodec FINAL : public Transform<byte> {
public:
    BWTBlockCodec(Context& ctx);
    bool forward(SliceArray<byte>& input, SliceArray<byte>& output, int length);
    bool inverse(SliceArray<byte>& input, SliceArray<byte>& output, int length);
    int getMaxEncodedLength(int srcLen) const { return srcLen + 1 + 32; }
private:
    BWT* _pBWT;
    int  _bsVersion;
};

The forward method applies the Burrows-Wheeler Transform during compression, storing the primary index within the block header. The inverse method reconstructs the original data using only this block's contents. Since the BWT primary index travels with the block data, the algorithm can decode any block in isolation without reference to previous blocks.

Random Access and Seek Mechanics

When an application requires specific block data (e.g., extracting block 5 from a compressed archive), Kanzi leverages the seekable infrastructure:

1. Open the file with DefaultInputBitStream (or allow CompressedInputStream to manage it internally).
2. Calculate the byte offset using the formula headerSize + blockIndex * (blockSize + overhead), or invoke seekBlock() (provided by CompressedInputStream in src/io/CompressedInputStream.hpp), which uses the block table stored in the file header.
3. Invoke the block decoder (e.g., BWTBlockCodec::inverse), which reads only the data belonging to that specific block.

Because DefaultInputBitStream::seek flushes buffers and moves the underlying file descriptor directly, the subsequent readBits operation fetches from the new byte-aligned location, achieving O(1) random access per block.

Parallel Decompression Implementation

BlockDecompressor exploits block independence to scale across multiple cores. The implementation creates a ThreadPool with _jobs + 1 workers and a BoundedConcurrentQueue to hold FileDecompressTask pointers. Worker threads (FileDecompressWorker) pop tasks and execute task->run(), with each task processing either an independent file or a specific range of blocks within a file.

Since blocks neither share state nor require synchronization for decoding, the parallelization overhead is limited to task distribution and queue management, allowing near-linear scaling with CPU core count.

Practical Code Examples

Random-Access Block Reading

This example demonstrates seeking to a specific block and decoding it in isolation:

#include "bitstream/DefaultInputBitStream.hpp"
#include "io/CompressedInputStream.hpp"
#include "transform/BWTBlockCodec.hpp"

using namespace kanzi;

int main() {
    // Open the underlying file stream
    std::ifstream ifs("sample.knz", std::ios::binary);
    DefaultInputBitStream bis(ifs);          // Seekable input bitstream
    Context ctx;                              // Default context

    // Build the compressed stream (parses header, knows block size)
    CompressedInputStream cis(bis, ctx);

    // Seek to block #3 (zero-based)
    int blockIdx = 3;
    cis.seekBlock(blockIdx);                  // moves to start of block

    // Decode the block
    BWTBlockCodec codec(ctx);
    SliceArray<byte> inBuf(/*...*/);   
    SliceArray<byte> outBuf(/*...*/);
    int blockSize = cis.getBlockSize();       // size of compressed block
    cis.read(reinterpret_cast<char*>(inBuf._array), blockSize);
    codec.inverse(inBuf, outBuf, blockSize);

    // outBuf now contains the original data of block #3
}

Parallel Directory Decompression

This example uses BlockDecompressor to process multiple files concurrently:

#include "app/BlockDecompressor.hpp"
#include "Context.hpp"

int main(int argc, char* argv[]) {
    kanzi::Context ctx;
    ctx.putString("inputName",  "data/");          // directory with *.knz files
    ctx.putString("outputName", "out/");           // destination directory
    ctx.putInt("jobs", 4);                         // 4 worker threads
    ctx.putInt("verbosity", 1);

    kanzi::BlockDecompressor dec(ctx);
    uint64 totalRead = 0;
    int rc = dec.decompress(totalRead);

    if (rc != 0) {
        std::cerr << "Decompression failed, code " << rc << std::endl;
        return rc;
    }
    std::cout << "Decompressed " << totalRead << " bytes." << std::endl;
    return 0;
}

The BlockDecompressor automatically creates FileDecompressTask instances for each .knz file and distributes them across the thread pool.

Summary

• The kanzi::Seekable interface in src/Seekable.hpp provides the tell() and seek() methods that enable byte-aligned random access in bitstreams.
• DefaultInputBitStream and DefaultOutputBitStream implement this interface, allowing O(1) repositioning within compressed files.
• Kanzi files consist of self-describing blocks, each containing codec configuration data (such as BWT primary indices) that enables independent decompression.
• BlockDecompressor leverages block independence to distribute work across a ThreadPool, achieving parallel processing without inter-task synchronization.
• Classes like BWTBlockCodec and CompressedInputStream encapsulate block-level logic, exposing methods like seekBlock() for direct random access.

Frequently Asked Questions

What makes Kanzi's bitstreams "seekable"?

Kanzi bitstreams implement the kanzi::Seekable interface, providing tell() to return the current bit position and seek(int64 pos) to reposition the stream. The DefaultInputBitStream implementation supports jumping to any byte-aligned position by flushing internal buffers and moving the underlying file descriptor, enabling random access to specific blocks without sequential reading.

How does independent block decompression enable parallelism?

Each block contains its own codec configuration and transformation metadata (such as the BWT primary index), making it self-contained. Because BlockDecompressor does not share state between blocks, it can distribute blocks or file ranges to multiple FileDecompressTask instances running in a ThreadPool. Workers process their assigned blocks sequentially without synchronization, scaling efficiently across CPU cores.

What information does each block header contain?

Individual block headers contain codec-specific parameters required to decode that specific block. For BWT-compressed blocks, this includes the primary index necessary for the inverse transform. The global file header (parsed by BlockDecompressor::decompress) stores metadata including total block count and uniform block size, allowing calculation of byte offsets for any block index.

Can I seek to arbitrary bit positions or only byte-aligned positions?

The current implementation supports seeking only to byte-aligned positions (where the bit position is divisible by 8). Both DefaultInputBitStream and DefaultOutputBitStream align seeks to byte boundaries, flushing partial bits in the buffer before repositioning. This design optimizes for block-based access while maintaining compatibility with standard byte-oriented file I/O.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}