### 4 releases

0.1.3 | Sep 25, 2019 |
---|---|

0.1.2 | Dec 17, 2018 |

0.1.1 | Dec 17, 2018 |

0.1.0 | Nov 30, 2018 |

#**262** in Data structures

**50** downloads per month

**MIT**license

81KB

1.5K
SLoC

# bex

A rust library for working with boolean expressions (expression trees, decision diagrams, etc.)

This crate lets you build a complicated abstract syntax tree (or logic circuit schematic, if you prefer) by working with individual Bit structs, or vectors that act like integers. You can also solve these AST structures by converting them into reduced, ordered, binary decision diagrams (ROBDDs) - a normal form consisting of if-then-else triples that essentially act like compressed truth tables. You can also construct and manipulate BDDs directly.

## changelog

### 0.1.3 (2019-09-24)

I got most this working back in December and then put it all aside for a while. It's still pretty messy, but I'm starting to work on it again, so I figured I would ship what I have, and then aim for more frequent, small releases as I continue to tinker with it.

**multi-threaded workers**

- refactored

so that the`bdd`

is now owned by a`BddState`

. Further, both`BddWorker`

and`BddState`

are now traits.`BddWorker` - Moved

implementation into`BddWorker`

.`SimpleBddWorker` - Provided multiple implementations for

-- (so far, one with and one without array bounds checking).`BddState` - Added a multi-core bdd worker:

. Between threading and an out-of-order execution model that results in potential short circuiting,`BddSwarm`

calls that once took 30 or more seconds on my low-end 2-core laptop now run in 0 seconds!`ite``(``)`

**code tuning**

- added

which optimizes the ast→bdd conversion to take only one`solve`sort_by_cost`::`

step per AST node (improved my still-external benchmark script by an order of magnitude).`bdd_refine_one` - in

,`bdd`

now constructs hi/lo nodes directly from input rather than calling`ite_norm`

. This resulted in about a 23% speedup.`when_xx`

**(rudimentary) example programs**

demonstrates one method of using bex to solve arbitrary problems. (Albeit very very slowly, still...)`examples``/`bdd`-`solve`.`rs

is a tiny forth-like interpreter for manipulating expressions interactively.`examples``/`bex`-`shell`.`rs- See exaples/README.md for more details.

**other improvements**

can now simply save the final result instead of showing it (as`solve`ProgressReport`::`

can take a very long time to render it into a png). It also now shows progress as a percentage (though only currently accurate when`dot`

was called)`sort_by_cost`

### 0.1.2 (2018-12-17)

- added

documentation link to docs.rs/bex`Cargo``.`toml - added this changelog

### 0.1.1 (2018-12-17)

- Renamed

to`bex`x32`::`

, used macros to generalize number of bits, added`bex`int`::`

,`times`

, and`lt`

functions`eq` - Added

for converting between ast and bdd representations.`bex`solve`::` - Added distinction between

(input) and`real`

(intermediate) variables in`virtual``bdd``::``NID` - Added graphviz (

) output for`*``.`dot

and improved formatting for`base`Base`::``bdd`BDDBase`::` - Various performance enhancements for

. Most notably:`bex`bdd`::`- switched caches to use the

crate (for about a 40% speedup!)`hashbrown` - added inlining hints for many functions
- re-ordered logic in bottleneck functions (

,`norm`

) to minimize work`ite_norm`

is now a single u64 with redundant information packed into the NID itself. This way, decisions can be made looking at the NID directly, without fetching the actual node.`bdd``::``NID`- Disabled bounds checking for internal node lookups. (unsafe)

- switched caches to use the
- Refactored

in preparation for multi-threading.`bex`bdd`::`- Grouped the internal node lists and the caches by branching variable (VID). This isn't actually an optimization, but I expect(ed?) it to make concurrent solving easier in the future.
- moved all the unsafe, data-mutating operations into a handful of
isolated functions on a single source page. These will likely be
factored out into a new

struct, eventually.`Worker`

### 0.1.0 (2018-11-30)

Initial public version. Work-in-progress code imported from a private repo.

#### Dependencies

~2.1–2.9MB

~55K SLoC