Espresso Logic Minimizer

A Rust library for minimizing Boolean functions using the classic Espresso heuristic logic minimizer from UC Berkeley. Perfect for digital logic synthesis, PLA optimization, and Boolean function simplification.

Why Espresso?

Espresso takes Boolean functions in sum-of-products form and produces minimal or near-minimal equivalents. This Rust crate provides safe, thread-safe bindings with modern features like expression parsing and operator overloading.

Features

• Thread-Safe - Safe concurrent execution via C11 thread-local storage
• Boolean Expressions - High-level API with parsing, operators, and expr! macro
• Binary Decision Diagrams - Canonical representation with efficient operations and automatic caching
• Flexible Parser - Supports both mathematical (*, +) and logical (&, |) operator notations
• Expression Composition - Seamlessly compose parsed, minimized, and constructed expressions
• Both Algorithms - Exposes both heuristic and exact minimization algorithms from Espresso
• PLA File Support - Read and write Berkeley PLA format
• Two API Levels - High-level for ease of use, low-level for maximum control
• Well Documented - Comprehensive API docs and examples

Quick Start

Add to your Cargo.toml:

[dependencies]
espresso-logic = "3.1"

Boolean Expression Minimization

use espresso_logic::{BoolExpr, expr};

fn main() -> std::io::Result<()> {
    // Build expression with redundant terms
    let redundant = expr!("a" * "b" + "a" * "b" * "c");
    println!("Original: {}", redundant);
    
    // Minimize it
    let minimized = redundant.minimize()?;
    println!("Minimized: {}", minimized);  // Output: a * b
    
    Ok(())
}

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(())
}

PLA File Processing

use espresso_logic::{Cover, CoverType, PLAReader, PLAWriter};

fn main() -> std::io::Result<()> {
    let mut cover = Cover::from_pla_file("input.pla")?;
    cover.minimize()?;
    cover.to_pla_file("output.pla", CoverType::F)?;
    Ok(())
}

Binary Decision Diagrams

use espresso_logic::{BoolExpr, Bdd};

fn main() {
    let a = BoolExpr::variable("a");
    let b = BoolExpr::variable("b");
    let c = BoolExpr::variable("c");
    let expr = a.and(&b).or(&b.and(&c));
    
    // Convert to BDD for canonical representation
    let bdd = expr.to_bdd();
    println!("BDD has {} nodes", bdd.node_count());
    
    // BDDs support efficient operations
    let bdd_c = c.to_bdd();
    let combined = bdd.and(&bdd_c);
    
    // Convert back to expression
    let result = combined.to_expr();
    println!("Result: {}", result);
}

API Overview

High-Level API (Recommended)

Use BoolExpr, Bdd, and Cover for most applications:

• Automatic memory management and dimension tracking
• Thread-safe by design
• Clean, idiomatic Rust API
• BDD caching for efficient repeated operations

use espresso_logic::{BoolExpr, expr};

// Parse with flexible notation: * or & for AND, + or | for OR
let xor = expr!("a" * !"b" + !"a" * "b");
let xor_alt = BoolExpr::parse("a & !b | !a & b")?;

// Minimize and get canonical BDD representation
let minimized = xor.minimize()?;
let bdd = xor.to_bdd();  // Cached for efficiency

Low-Level API (Advanced)

Direct espresso::Espresso access for specialized needs:

• Access to intermediate covers (ON-set, don't-care, OFF-set)
• Custom don't-care/off-set optimization
• Maximum performance (~5-10% faster)

See the espresso module documentation for details.

Installation

Prerequisites: Rust 1.70+, C compiler, libclang

# macOS
xcode-select --install

# Ubuntu/Debian
sudo apt-get install build-essential libclang-dev

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

Command Line Tool

Install the optional CLI:

cargo install espresso-logic --features cli

Usage:

espresso input.pla > output.pla
espresso -s input.pla  # Show statistics

See docs/CLI.md for more options.

Examples

Run included examples:

cargo run --example boolean_expressions
cargo run --example xor_function
cargo run --example pla_file
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
• PLA Format - PLA file format specification
• CLI Guide - Command-line usage
• Installation - Platform-specific setup

Testing

cargo test

See TESTING.md for comprehensive testing documentation.

Contributing

Contributions welcome! See CONTRIBUTING.md for guidelines.

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 developers and Sébastien Cottinet for the modernized C version.

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}
}

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