# Understanding Seekable Bitstreams and Independent Block Decompression in Kanzi

> Explore Kanzi's seekable bitstreams and independent block decompression for O(1) random access and parallel decompression with the kanzi::Seekable interface.

- Repository: [flanglet/kanzi-cpp](https://github.com/flanglet/kanzi-cpp)
- Tags: deep-dive
- Published: 2026-03-02

---

**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`](https://github.com/flanglet/kanzi-cpp/blob/main/src/Seekable.hpp). This abstract base class establishes the contract for bit-level positioning:

```cpp
// 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`](https://github.com/flanglet/kanzi-cpp/blob/main/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`](https://github.com/flanglet/kanzi-cpp/blob/main/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`](https://github.com/flanglet/kanzi-cpp/blob/main/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`](https://github.com/flanglet/kanzi-cpp/blob/main/src/transform/BWTBlockCodec.hpp) implements the transform layer for individual blocks:

```cpp
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`](https://github.com/flanglet/kanzi-cpp/blob/main/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:

```cpp
#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:

```cpp
#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`](https://github.com/flanglet/kanzi-cpp/blob/main/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.