Espresso Logic Minimizer

A powerful Rust library for minimizing Boolean functions using the classic Espresso heuristic logic minimizer from UC Berkeley.

Why Espresso Logic?

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 with modern features.

Key Contributions:

• Thread-Safe Execution - The original Espresso C code used global state, making concurrent execution unsafe. This crate implements C11 thread-local storage for all globals, enabling safe parallel minimization across threads.
• Safe Rust API - Memory-safe wrappers with proper resource management
• Modern Features - Boolean expression parsing, operator overloading, and procedural macros

Perfect for:

• Digital logic synthesis and optimization
• PLA (Programmable Logic Array) minimization
• Boolean function simplification in CAD tools
• Concurrent logic minimization in multi-threaded applications
• Teaching Boolean algebra and logic design
• Research in logic optimization

✨ Features

• Thread-Safe Concurrent Execution - Unlike original Espresso, safely run minimization in parallel threads via C11 thread-local storage
• Safe Rust API - Memory-safe wrappers with zero-cost abstractions
• Boolean Expressions - High-level API with parsing, operator overloading, and expr! macro
• PLA File Support - Read and write Berkeley PLA format files
• Minimal Dependencies - Core library uses only libc and lalrpop-util
• Command Line Tool - Compatible with original Espresso CLI (optional)
• Well Documented - Comprehensive API documentation and examples

🚀 Quick Start

Add this to your Cargo.toml:

[dependencies]
espresso-logic = "3.0"

Simple Example

use espresso_logic::{BoolExpr, expr};

fn main() -> std::io::Result<()> {
    // Build expression using string literals - no variable declarations needed!
    let xor = expr!("a" * "b" + !"a" * !"b");
    println!("Original: {}", xor);
    
    // Minimize it
    let minimized = xor.minimize()?;
    println!("Minimized: {}", minimized);
    
    Ok(())
}

Working with Variables

use espresso_logic::{BoolExpr, expr};

fn main() -> std::io::Result<()> {
    let a = BoolExpr::variable("a");
    let b = BoolExpr::variable("b");
    let c = BoolExpr::variable("c");
    
    // Build complex expression with redundant terms
    let expr = expr!(a * b + a * b * c + a * c);
    
    // Minimize automatically removes redundancy
    let minimized = expr.minimize()?;
    println!("Simplified: {}", minimized);
    
    // Check logical equivalence
    assert!(expr.equivalent_to(&minimized));
    
    Ok(())
}

📚 Common Use Cases

Truth Table Minimization

use espresso_logic::{Cover, CoverType};

fn main() -> std::io::Result<()> {
    let mut cover = Cover::new(CoverType::F);
    
    // XOR function: output is 1 when inputs differ
    cover.add_cube(&[Some(false), Some(true)], &[Some(true)]);  // 01 -> 1
    cover.add_cube(&[Some(true), Some(false)], &[Some(true)]);  // 10 -> 1
    
    cover.minimize()?;
    println!("Minimized to {} cubes", cover.num_cubes());
    
    Ok(())
}

Multiple Outputs

use espresso_logic::{Cover, CoverType, BoolExpr, expr};

fn main() -> std::io::Result<()> {
    let mut cover = Cover::new(CoverType::F);
    let a = BoolExpr::variable("a");
    let b = BoolExpr::variable("b");
    
    // Define multiple outputs
    cover.add_expr(expr!(a * b), "and_gate")?;
    cover.add_expr(expr!(a + b), "or_gate")?;
    
    cover.minimize()?;
    
    // Get minimized results
    for (name, expr) in cover.to_exprs() {
        println!("{}: {}", name, expr);
    }
    
    Ok(())
}

PLA Files

use espresso_logic::{Cover, CoverType};

fn main() -> std::io::Result<()> {
    // Read, minimize, and write back
    let mut cover = Cover::from_pla_file("input.pla")?;
    cover.minimize()?;
    cover.to_pla_file("output.pla", CoverType::F)?;
    
    println!("Minimized {} inputs, {} outputs", 
             cover.num_inputs(), cover.num_outputs());
    
    Ok(())
}

🎯 API Overview

This crate provides two API levels to suit different needs:

High-Level API (Recommended)

Use BoolExpr and Cover for most applications:

• ✅ Thread-safe by design - No manual synchronization needed
• ✅ Automatic memory management - RAII handles cleanup
• ✅ Clean syntax - expr! macro and operator overloading
• ✅ Dynamic dimensions - Automatic dimension management
• ✅ Easy to use - Idiomatic Rust API

Perfect for:

• Application development
• Logic synthesis tools
• Educational projects
• Rapid prototyping

Low-Level API (Advanced)

Direct espresso::Espresso and espresso::EspressoCover access for specialized needs:

• 📊 Access to intermediate covers - Get ON-set (F), don't-care (D), OFF-set (R) separately
• 🎯 Custom don't-care/off-sets - Provide your own D and R covers for optimization
• ⚡ Maximum performance - ~5-10% faster than high-level API, minimal overhead
• 🔧 Explicit instance control - Manually manage Espresso instance lifecycle

Use when you need:

• Access to all three covers (F, D, R) from minimization
• To provide custom don't-care or off-set covers
• Absolute maximum performance (5-10% speedup)
• Explicit control over instance creation/destruction

Note: Algorithm configuration via EspressoConfig works with both APIs - if you only need to tune algorithm parameters, use the high-level Cover::minimize_with_config() instead.

⚠️ Important Constraints:

• All covers on a thread must use the same dimensions until dropped
• Requires manual dimension management
• More complex error handling

use espresso_logic::espresso::{Espresso, EspressoCover, CubeType};
use espresso_logic::EspressoConfig;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Custom configuration
    let mut config = EspressoConfig::default();
    config.single_expand = true;
    let _esp = Espresso::new(2, 1, &config);
    
    // Create and minimize
    let cubes = vec![(vec![0, 1], vec![1]), (vec![1, 0], vec![1])];
    let cover = EspressoCover::from_cubes(cubes, 2, 1)?;
    let (f, d, r) = cover.minimize(None, None);
    
    println!("Minimized to {} cubes", f.to_cubes(2, 1, CubeType::F).len());
    Ok(())
}

See docs/API.md for complete API documentation and the espresso module documentation for detailed safety guidelines.

🛠️ Command Line Usage

Install the CLI tool (optional):

cargo install espresso-logic --features cli

Basic usage:

# Minimize a PLA file
espresso input.pla > output.pla

# Show statistics
espresso -s input.pla

# Exact minimization (slower but optimal)
espresso --do exact input.pla

See docs/CLI.md for more options.

📦 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

See docs/INSTALLATION.md for detailed platform-specific instructions.

🎓 Examples

Run included examples to see different features:

# Boolean expressions
cargo run --example boolean_expressions

# XOR minimization
cargo run --example xor_function

# PLA file processing
cargo run --example pla_file

# Concurrent execution
cargo run --example concurrent_transparent

See docs/EXAMPLES.md for comprehensive code examples.

📖 Documentation

• API Reference - Complete API documentation
• Examples Guide - Comprehensive usage examples
• Boolean Expressions - Expression API details
• CLI Guide - Command-line usage
• Installation - Platform-specific setup
• Testing Guide - How to run tests
• Contributing - How to contribute

🧪 Testing

cargo test

For comprehensive testing including memory safety and regression tests, see TESTING.md.

🌐 Compatibility

• Rust: 1.70+
• Platforms: Linux, macOS, Windows
• Espresso Version: 2.3 (01/31/88)

🤝 Contributing

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

📚 References

• Original Espresso Paper
• UC Berkeley Espresso Page
• Wikipedia Article

📄 License

This project contains three layers of licensed work:

• Original Espresso: UC Berkeley (permissive license)
• Modernized C Code: Sébastien Cottinet (MIT)
• Rust Wrapper: Marcos Sartori (MIT)

See LICENSE and ACKNOWLEDGMENTS.md for details.

🙏 Acknowledgments

Espresso was developed by Robert K. Brayton and his team at UC Berkeley. Special thanks to:

• The original Espresso developers (Brayton, Hachtel, McMullen, Sangiovanni-Vincentelli)
• Sébastien Cottinet for the MIT-licensed modernized C version
• The Rust community for excellent FFI tools

For complete acknowledgments, see ACKNOWLEDGMENTS.md.

📊 Citation

If you use this library in academic work, please cite:

@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 - Modern logic synthesis tool
• Yosys - Open-source synthesis suite

💬 Support

• 🐛 Report a bug
• 💡 Request a feature
• 📖 View documentation
• 💬 Ask a question

---

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