Espresso Logic Minimizer

A Rust wrapper for the Espresso heuristic logic minimizer, a classic tool from UC Berkeley for minimizing Boolean functions.

Overview

Espresso takes a Boolean function represented as a sum-of-products and produces a minimal or near-minimal equivalent representation. This Rust crate provides safe, idiomatic bindings to the original C implementation.

Use cases:

Digital logic synthesis
PLA (Programmable Logic Array) minimization
Boolean function simplification
Logic optimization in CAD tools
Teaching Boolean algebra and logic design

Features

✅ Safe Rust API - Memory-safe wrappers around the C library
✅ Boolean Expressions - High-level API with parsing, operator overloading, and expr! macro
✅ Thread-Safe - Concurrent execution via C11 thread-local storage
✅ Command Line Interface - Compatible with original Espresso CLI
✅ PLA File Support - Read and write Berkeley PLA format files
✅ Flexible Input - Boolean expressions, programmatic covers, or PLA files
✅ Multiple Algorithms - Both heuristic (fast) and exact (optimal) minimization
✅ Zero-cost Abstractions - Minimal overhead compared to direct C usage
✅ Well Documented - Comprehensive API documentation and examples

Quick Start

Add this to your Cargo.toml:

[dependencies]
espresso-logic = "2.6"

Command Line Usage

# Build the CLI
cargo build --release --bin espresso

# Minimize a PLA file
./target/release/espresso input.pla > output.pla

# With summary
./target/release/espresso -s input.pla

# Exact minimization
./target/release/espresso --do exact input.pla

Boolean Expressions (High-Level API)

use espresso_logic::{BoolExpr, expr};

fn main() -> std::io::Result<()> {
    // Create variables
    let a = BoolExpr::variable("a");
    let b = BoolExpr::variable("b");
    let c = BoolExpr::variable("c");
    
    // Build expression with expr! macro for clean syntax
    let expr = expr!(a * b + a * b * c);  // Redundant term
    
    // Minimize directly
    let minimized = expr.minimize()?;
    println!("Minimized: {}", minimized);  // Output: (a * b)
    
    // Or parse from string
    let parsed = BoolExpr::parse("(a + b) * (c + d)")?;
    let result = parsed.minimize()?;
    
    Ok(())
}

Library API Example (Low-Level)

use espresso_logic::Cover;

fn main() -> std::io::Result<()> {
    // Create a cover for a 2-input, 1-output function
    let mut cover = Cover::<2, 1>::new();
    
    // Build a truth table (XOR function)
    cover.add_cube(&[Some(false), Some(true)], &[true]); // 01 -> 1
    cover.add_cube(&[Some(true), Some(false)], &[true]); // 10 -> 1
    
    // Minimize - thread-safe via thread-local storage
    cover.minimize()?;
    
    println!("Minimized! Cubes: {}", cover.num_cubes());
    Ok(())
}

Working with PLA Files

use espresso_logic::{PLA, PLAType};

fn main() -> std::io::Result<()> {
    // Read a PLA file
    let pla = PLA::from_file("input.pla")?;
    pla.print_summary();
    
    // Minimize it
    let minimized = pla.minimize();
    
    // Write the result
    minimized.to_file("output.pla", PLAType::F)?;
    
    Ok(())
}

Concurrent Execution (Thread-Safe)

Thread-safe by default - the C library uses C11 thread-local storage for all global state:

use espresso_logic::Cover;
use std::thread;

fn main() -> std::io::Result<()> {
    // Spawn multiple threads - each executes Espresso independently
    let handles: Vec<_> = (0..4).map(|_| {
        thread::spawn(move || {
            let mut cover = Cover::<2, 1>::new();
            cover.add_cube(&[Some(false), Some(true)], &[true]);
            cover.add_cube(&[Some(true), Some(false)], &[true]);
            
            // Thread-safe - each thread executes with independent global state
            cover.minimize()?;
            Ok(cover.num_cubes())
        })
    }).collect();
    
    for handle in handles {
        let num_cubes = handle.join().unwrap()?;
        println!("Result: {} cubes", num_cubes);
    }
    Ok(())
}

Key benefits:

✅ Thread-safe by default - no synchronization needed
✅ Independent state per thread via thread-local storage
✅ True parallelism - each thread executes Espresso concurrently
✅ Simple API with const generics for compile-time safety
✅ Direct C calls - no IPC overhead

See docs/THREAD_LOCAL_IMPLEMENTATION.md for technical details.

Installation

Prerequisites

Rust 1.70 or later
C compiler (gcc, clang, or msvc)
libclang (for bindgen during build)

macOS:

xcode-select --install

Ubuntu/Debian:

sudo apt-get install build-essential libclang-dev

Windows:

Install Visual Studio Build Tools with C++ support
Or use MSYS2 with mingw-w64

Building

cargo build --release

The build script automatically compiles the C source code and generates FFI bindings.

Examples

The crate includes several examples demonstrating different use cases:

# Boolean expressions (high-level API) - NEW!
cargo run --example boolean_expressions

# Basic minimization
cargo run --example minimize

# XOR function (classic example)
cargo run --example xor_function

# PLA file processing
cargo run --example pla_file

# PLA file with output
cargo run --example pla_file output.pla

# Transparent thread-safe API
cargo run --example transparent_api

# Concurrent execution
cargo run --example concurrent_transparent

PLA File Format

Espresso uses the Berkeley PLA format. Here's a simple example:

.i 2        # 2 inputs
.o 1        # 1 output
.ilb a b    # input labels
.ob f       # output label
.p 2        # 2 product terms
01 1        # a=0, b=1 => f=1
10 1        # a=1, b=0 => f=1
.e          # end

Notation:

0 - Variable must be 0
1 - Variable must be 1
- - Don't care

API Overview

Core Types

High-Level API (Boolean Expressions)

BoolExpr - Boolean expression with operator overloading
ExprCover - Cover representation for boolean expressions
expr! - Macro for clean expression syntax

Low-Level API (Cubes and Covers)

Cover<I, O> - Generic cover with compile-time dimensions
CoverBuilder<I, O> - Builder for constructing covers programmatically
PLACover - Dynamic cover for PLA files
PLAType - Output format specifier

Key Methods

// Boolean expressions (high-level)
let a = BoolExpr::variable("a");
let b = BoolExpr::variable("b");
let expr = expr!(a * b + !a * !b);
let minimized = expr.minimize()?;

// Or parse from string
let expr = BoolExpr::parse("(a + b) * c")?;

// Low-level cover API
let mut cover = CoverBuilder::<2, 1>::new();
cover.add_cube(&[Some(true), Some(false)], &[Some(true)]);
cover.minimize()?;

// PLA file operations
let mut pla = PLACover::from_pla_file("file.pla")?;
pla.minimize()?;
pla.to_pla_file("out.pla", PLAType::F)?;

See docs/API.md for complete API documentation.

Performance

The Rust wrapper has negligible overhead compared to the C library:

Heuristic minimization is fast and suitable for most use cases
Exact minimization guarantees optimality but is slower
Large functions (>1000 cubes) may require significant time

Architecture

The crate is organized into three layers:

C Library (espresso-src/) - Modified Espresso implementation with C11 thread-local storage
FFI Bindings (src/sys.rs) - Auto-generated by bindgen
Safe API (src/lib.rs) - Idiomatic Rust wrappers

Memory management is handled automatically through RAII patterns.

C Code Modifications: The original Espresso C code has been modified to use C11 _Thread_local for all global variables (~50+ variables across 16 files), enabling safe concurrent execution. Accessor functions provide Rust FFI compatibility.

Testing

Unit and Integration Tests

Run the Rust test suite:

cargo test

Run with verbose output:

cargo test -- --nocapture

Regression Tests (CLI)

The project includes regression tests that validate the Rust CLI against the original C implementation:

# Quick regression test (4 cases, ~1 second)
./tests/quick_regression.sh

# Comprehensive regression test (38 cases, ~5 seconds)
./tests/comprehensive_regression.sh

Status: ✅ 38/38 tests passing - Rust CLI produces identical output to C CLI

Documentation

Generate and view the API documentation:

cargo doc --open

Additional documentation:

Boolean Expressions Guide - Comprehensive guide to the expression API
API Reference - Complete API documentation
Command Line Interface - CLI usage guide
Thread-Local Implementation - Thread-safe concurrent execution
Process Isolation (Historical) - Previous implementation (pre-2.6.2)
Contributing Guidelines
Original Espresso README

Compatibility

Rust: 1.70 or later
Platforms: Linux, macOS, Windows
Espresso Version: 2.3 (Release date 01/31/88)
Wrapper Version: 2.3.0 (matches Espresso version)

Limitations

Very large Boolean functions may exhaust memory
PLA file format has some limitations compared to modern formats

Contributing

Contributions are welcome! Please see CONTRIBUTING.md for guidelines.

References

Espresso Paper - Original research paper
UC Berkeley Espresso Page
Wikipedia Article
Brayton, R. K., et al. "Logic minimization algorithms for VLSI synthesis." (1984)

License

This project contains three layers of licensed work:

Original Espresso: Copyright (c) 1988, 1989, Regents of the University of California (UC Berkeley License)

All are permissive licenses. See LICENSE for complete terms and ACKNOWLEDGMENTS.md for attribution details.

Acknowledgments

The Espresso logic minimizer was developed by Robert K. Brayton and his team at UC Berkeley. This Rust wrapper builds upon their excellent work to make it accessible to the Rust ecosystem.

Special thanks to:

The original Espresso developers at UC Berkeley (Brayton, Hachtel, McMullen, Sangiovanni-Vincentelli)
The Electronics Research Laboratory at UC Berkeley
Sébastien Cottinet for the 2016 MIT-licensed modernized C version
classabbyamp for maintaining the modernized C codebase
The Rust community for excellent FFI tools (bindgen, cc crate)
Contributors to this wrapper

For complete acknowledgments and license compliance information, see ACKNOWLEDGMENTS.md

Citation

If you use this library in academic work, please cite the original Espresso paper:

@article{brayton1984logic,
  title={Logic minimization algorithms for VLSI synthesis},
  author={Brayton, Robert K and Hachtel, Gary D and McMullen, Curtis T and Sangiovanni-Vincentelli, Alberto L},
  journal={Kluwer Academic Publishers},
  year={1984}
}

Related Projects

ABC - A modern logic synthesis tool from UC Berkeley
Yosys - Open-source synthesis suite
PLA Tools - Other PLA manipulation tools

Support

Made with ❤️ for the Rust and digital logic communities.

espresso-logic 2.6.2