Skip to content

PFC - Prefix-Free Codecs

Welcome to the documentation for PFC, a header-only C++20 library for zero-copy, prefix-free data representations with full algebraic type support and STL integration.

Overview

PFC implements a comprehensive suite of prefix-free codecs and data structures that maintain a zero-copy invariant: the in-memory representation is identical to the wire format. This eliminates marshaling overhead while providing powerful compression and type composition capabilities.

Key Features

  • Zero-Copy Invariant: In-memory bytes = wire bytes (no marshaling)
  • Prefix-Free Codes: Self-delimiting, streaming-friendly encodings
  • Algebraic Type System: Sum types, product types, recursive types
  • STL Integration: Works seamlessly with standard algorithms
  • Rich Codec Library: Universal codes, floating point, rationals, and more
  • Compile-Time Composition: Modern C++ concepts and templates
  • Mathematical Rigor: Based on Stepanov's generic programming principles

Test Coverage

The library is thoroughly tested with 86% test suite pass rate (6/7 suites, 3477+ assertions):

  • Core Tests: Codecs, packed values, bit I/O, basic algorithms
  • Advanced Tests: Algebraic types, STL integration, coordinate systems
  • Production Tests: Huffman, LZ77, error handling, custom allocators
  • CRC Tests: CRC8, CRC16, CRC32 checksums
  • Succinct Tests: SuccinctBitVector with rank/select (3167 assertions)
  • New Codecs Tests: VByte, ExpGolomb, EliasOmega (2000 assertions)
  • Stream/Arithmetic Tests: Stream I/O and arithmetic coding

Quick Example

#include <pfc/pfc.hpp>
using namespace pfc;

// Simple compression
std::vector<uint32_t> data = {1, 2, 3, 5, 8, 13, 21};
auto compressed = compress<EliasGamma>(data);
auto decompressed = decompress<EliasGamma, uint32_t>(compressed);

// Algebraic types
using OptionalInt = PackedOptional<Packed<int, Signed<EliasGamma>>>;
OptionalInt some_value = 42;
OptionalInt no_value = std::nullopt;

// STL integration
PackedContainer<uint32_t, EliasGamma> container;
container.push_back(100);
container.push_back(200);
std::sort(container.begin(), container.end());

Why PFC?

Zero-Copy Performance

Traditional serialization libraries copy data between in-memory and wire representations. PFC eliminates this overhead by making them identical:

// Traditional approach (2 copies)
std::vector<int> data = {1, 2, 3};
auto serialized = serialize(data);  // Copy 1
send_over_network(serialized);
auto received = receive_from_network();
auto deserialized = deserialize<std::vector<int>>(received);  // Copy 2

// PFC approach (0 copies)
PackedVector<PackedInt> data = {1, 2, 3};
send_over_network(data.data(), data.byte_size());  // Direct memory access
PackedVector<PackedInt> received(buffer, buffer_size);  // Zero-copy view

Prefix-Free Advantage

Prefix-free codes are self-delimiting, enabling:

  • Streaming processing without lookahead
  • Concatenation without separators
  • Variable-length encoding with guaranteed decoding

Type Safety

Strong typing prevents common serialization errors:

// Type-safe tagged unions
using Response = PackedVariant<
    Packed<Success, SuccessCodec>,
    Packed<Error, ErrorCodec>
>;

// Compiler enforces exhaustive pattern matching
auto result = response.visit(overloaded{
    [](const Success& s) { return process(s); },
    [](const Error& e) { return handle_error(e); }
});

Architecture

PFC is organized into focused modules:

  • Core: Bit I/O primitives (BitReader/BitWriter), concepts, fundamental abstractions
  • Codecs: Universal integer codes (Elias, Fibonacci, Rice, VByte, ExpGolomb)
  • Numeric: Floating point, rational, complex number codecs
  • Packed: Value types and containers with zero-copy semantics
  • Algebraic: Sum and product types for type composition
  • STL Integration: Iterators, algorithms, and standard compatibility
  • Compression: Huffman, LZ77, arithmetic coding (production-ready)
  • Succinct: Space-efficient data structures (SuccinctBitVector with rank/select)
  • Utilities: CRC checksums, stream I/O, error handling

Next Steps

Requirements

  • C++20 compliant compiler (GCC 10+, Clang 12+, MSVC 2019+)
  • CMake 3.15+ (for building tests and examples)
  • Header-only library, no external dependencies required

License

PFC is released under the MIT License. See LICENSE for details.