bzip3/doc/bzip3_format.md

BZip3 Format Specification

Version 1

Headers

The File and Frame formats share a similar structure, differing only in whether they include a block count field.

File Header

+----------------+------------------+--------------------+
| Header         | Chunk 1          | Chunk 2            |
| (9 bytes)      | (variable size)  | (variable size)    |
+----------------+------------------+--------------------+

This is created by the CLI tool.

Frame Header

+----------------+------------------+--------------------+
| Header         | Chunk 1          | Chunk 2            |
| (13 bytes)     | (variable size)  | (variable size)    |
+----------------+------------------+--------------------+

This is created/read by bz3_compress and bz3_decompress.

Header Structure

Field	Type	Description	File Header	Frame Header
Signature	u8[5]	Fixed "BZ3v1" ASCII string	✓	✓
Max Block Size	u32_le	Maximum decompressed block size	✓	✓
Block Count	u32_le	Number of blocks in the stream	✗	✓

Validation Rules

1. Signature: Must exactly match "BZ3v1"
2. Max Block Size:
   • Minimum: 65KiB (66,560 bytes)
   • Maximum: 511MiB (535,822,336 bytes)
3. Block Count (Frame Format only):
   • Must match the actual number of blocks in the stream
   • Should be greater than 0

Example Parser

typedef struct {
    uint32_t max_block_size;
    uint32_t block_count; // Frame Format only
} bzip3_header_t;

bool read_bzip3_header(FILE* fp, bzip3_header_t* header, bool is_frame_format) {
    char signature[6] = {0};
    
    // Read signature
    if (fread(signature, 1, 5, fp) != 5)
        return false;
        
    if (strcmp(signature, "BZ3v1") != 0)
        return false;
        
    // Read max block size
    uint8_t size_bytes[4];
    if (fread(size_bytes, 1, 4, fp) != 4)
        return false;
        
    header->max_block_size = read_neutral_s32(size_bytes);
    
    if (header->max_block_size < 65536 || 
        header->max_block_size > 535822336)
        return false;
    
    // Read block count if Frame Format
    if (is_frame_format) {
        uint8_t count_bytes[4];
        if (fread(count_bytes, 1, 4, fp) != 4)
            return false;
            
        header->block_count = read_neutral_s32(count_bytes);
        
        if (header->block_count == 0)
            return false;
    }
    
    return true;
}

The integers in BZip3 are written unaligned, in little endian format. A portable implementation is below.

// Reading a 32-bit integer
static s32 read_neutral_s32(u8 * data) {
    return ((u32)data[0]) | 
           (((u32)data[1]) << 8) | 
           (((u32)data[2]) << 16) | 
           (((u32)data[3]) << 24);
}

// Writing a 32-bit integer
static void write_neutral_s32(u8 * data, s32 value) {
    data[0] = value & 0xFF;
    data[1] = (value >> 8) & 0xFF;
    data[2] = (value >> 16) & 0xFF;
    data[3] = (value >> 24) & 0xFF;
}

Block Format

After the header, both File and Frame formats contain a sequence of blocks that follow the Block Format specification. Each block is encapsulated in a chunk structure that defines its size.

The blocks (without chunk header) can be encoded/decoded using the bz3_encode_block and bz3_decode_block APIs.

Chunk Structure

// Main block structure
struct Chunk {
    u32_le compressedSize;   // Size of compressed block
    u32_le origSize;         // Original uncompressed size
        
    if (origSize < 64) {
        SmallBlock block;
    } else {
        Block block;
    }
};

Small Block Format (< 64 bytes)

For blocks smaller than 64 bytes, no compression is attempted. The data is stored with just a checksum:

struct SmallBlock {
    u32_le crc32;           // CRC32 checksum
    u32_le literal;         // Always 0xFFFFFFFF for small blocks. This is basically an invalid `bwtIndex`
    u8 data[parent.compressedSize - 8]; // Uncompressed data
};

Regular Block Format (≥ 64 bytes)

Larger blocks use a more complex format that supports multiple compression features:

struct Block {
    u32_le crc32;            // CRC32 checksum of uncompressed data
    u32_le bwtIndex;         // Burrows-Wheeler transform index
    u8  model;            // Compression model flags
    
    if ((model & 0x02) != 0)     
        u32_le lzpSize;      // Size after LZP compression
    if ((model & 0x04) != 0)     
        u32_le rleSize;      // Size after RLE compression
        
    u8 data[parent.compressedSize - (popcnt(model) * 4 + 9)];
};

Compression Model

The model byte in regular blocks indicates which compression features were used:

• 0x02: LZP (Lempel Ziv Prediction) filter
• 0x04: RLE (Run-Length Encoding) filter

External Resources

• BZip3 Pattern for ImHex