Building High-Performance Compression Systems

bzip3 and Beyond

Introduction

1. The Economics of Compression
2. The Compression Landscape
3. Why bzip3 Matters
4. What This Book Is Not
5. How to Use This Book

Chapter 1: Information Theory Foundations

1. Entropy and Its Meaning
2. Shannon’s Source Coding Theorem
3. Measuring Compression: Ratio, Bits-per-Byte, and Entropy Gap
4. The Gap Between Theory and Practice
5. Practical Implications for Compressor Design

Chapter 2: Symbol Coding: Huffman and Beyond

1. Prefix Codes and the Kraft-McMillan Theorem
2. Building a Huffman Tree
3. Canonical Huffman Codes
4. Arithmetic Coding: The Idea
5. Range Coding: Why It Is Better Than Arithmetic Coding

Chapter 3: Dictionary Methods and LZ Algorithms

1. LZ77: Sliding Window and Match Vectors
2. LZ78 and the LZ Family Tree
3. Deflate’s Approach to Dictionary Compression
4. Match Finding: Hash Chains vs Binary Search vs FM-Index
5. The Cost of Match Finding

Chapter 4: Block Transformations: BWT and MTF

1. Why Transform Before Compressing
2. The Burrows-Wheeler Transform Explained
3. Inverting the BWT: The LF-Mapping Property
4. Move-to-Front Coding
5. How BWT+MTF Creates Compressible Distributions

Chapter 5: The bzip2 Architecture

1. Block Size as a Design Parameter
2. Sorting Runs: The In-place Suffix Sort
3. Run-Length Encoding Before BWT
4. Huffman Coding with Multiple Passes
5. Where bzip2 Falls Short

Chapter 6: Block-Based Design Principles

1. Why Blocks at All
2. Block Size vs Compression Ratio vs Memory
3. Independence and Parallelism
4. Streaming with Blocks
5. Error Localization and Recovery
6. Summary: The Block Philosophy

Chapter 7: Range Coding Implementation

1. The 64-bit Range Coder
2. Handling Underflow and Renormalization
3. Byte Output Buffering
4. The Decoder Mirror
5. Testing Range Coder Correctness
6. Optimization Notes

Chapter 8: Context Modeling

1. Order-0 vs Order-N Models
2. Context Mixing and Blending
3. Adaptive Probability Updates
4. State Machines in Context Modeling
5. Context Modeling for BWT Output
6. The Cost of Context Modeling

Chapter 9: bzip3 Design Philosophy

1. Motivations Behind bzip3
2. The Modular Pipeline Approach
3. LZH vs BWT Modes
4. Choosing Between Pretransformation Strategies
5. The Role of Preprocessing

Chapter 10: The bzip3 Compression Pipeline

1. Chunking and Block Partitioning
2. Pretransformation and Dictionary Compression
3. Transform Selection and Encoding
4. Context Modeling the Transformed Stream
5. Range Encoding to Final Bits
6. Why This Pipeline Works

Chapter 11: Implementing a Reference bzip3-style Compressor

1. Project Layout and Build System
2. The Block Structure and API
3. BWT Implementation in C
4. MTF and Context Modeling Code
5. Putting It All Together

Chapter 12: SIMD and Vectorization

1. Where SIMD Helps in Compression
2. Vectorizing Match Finding
3. SIMD-Accelerated Sorting
4. Vectorized Range Coding
5. Portability and Auto-Vectorization
6. Measuring SIMD Benefits

Chapter 13: Parallel Compression Architectures

1. Parallel Patterns in Compression
2. Block-Level Parallelism
3. Shared Memory and Lock-Free Queues
4. Producer-Consumer Pipeline Design
5. Scaling Limits and Amdahl’s Law

Chapter 14: Streaming Compression Design

1. Stream vs Block: Reconciling the Tension
2. Chunk Boundaries and Backreferences
3. Flushing and Partial Results
4. Seeking and Indexing
5. Handling Stream Corruption
6. API Design for Streaming

Chapter 15: Memory Engineering

1. Memory Footprint Analysis
2. Cache Line Behavior and Data Layout
3. Arena Allocators and Pooling
4. Reducing Allocation in Hot Paths
5. Low-Memory Mode Trade-offs
6. Memory and Parallelism

Chapter 16: I/O and System Integration

1. The I/O Bottleneck
2. Buffering Strategies
3. Asynchronous I/O with Compression
4. Pipe and Network Throughput
5. Compression on the Fly vs Batch

Chapter 17: File Format Design

1. Magic Numbers and Headers
2. Metadata and Flags
3. CRC and Integrity Checking
4. Forward Compatibility
5. bzip3 Format Decoded

Chapter 18: Benchmarking and Profiling

1. Compression Benchmarks: Tools and Standards
2. Designing Fair Comparisons
3. Measuring Throughput and Latency
4. Profiling with perf and Valgrind
5. Interpreting Benchmark Results

Chapter 19: The Broader Landscape

1. LZ4 and the Speed Extreme
2. Zstandard: Adaptive Compression
3. Brotli: Static Dictionary Power
4. xz/LZMA: Ratio Focused
5. When to Use Which Compressor

Chapter 20: Security and Correctness

1. Decompression Bombs and Limits
2. Bounds Checking Everywhere
3. Integer Overflow and Wraparound
4. Fuzz Testing Compression Code
5. Side Channels in Compression
6. CVEs and Real-World Vulnerabilities

Chapter 21: API Design and Library Engineering

1. Stream vs Batch APIs
2. Error Handling Semantics
3. Thread Safety and Initialization
4. ABI Stability
5. Example API Design

Chapter 22: Production Deployment

1. Compression on Servers and Storage
2. Network Compression Trade-offs
3. Choosing Levels and Parameters
4. Monitoring and Alerting
5. Migration Strategies

Chapter 23: Beyond bzip3

1. Neural and Learned Compression
2. Compression for Non-Text Workloads
3. Hardware Acceleration
4. The End of the Compression Line
5. Open Problems

Conclusion

References