#gate #circuit #logic #pull-requests #copy #free #issues

app bascule

Logic circuit simulation where everything is a NAND gate or a D flip-flop

1 unstable release

Uses old Rust 2015

0.0.0 Jul 31, 2022

MIT/Apache

1KB

No Maintenance Intended

This is a hobby project. If anything here is useful to you it’s probably best to copy it into your project (according to the license) as I may or may not respond to issues or pull requests. Feel free to tell me about it though!

Bascule

[Picture of a colorful children’s rocking horse in a public park. In French it is called “cheval à bascule”.]

use bascule::integer::{const_bits, wrapping_add};
use bascule::memory::delayed;
use bascule::{Builder, Signal};

/// Outputs a value of the Fibonacci sequence that advances at each clock tick
pub fn fibonacci_sequence<const BITS: usize>(builder: &Builder) -> Signal<BITS> {
    // The two first integers of the sequence
    let first_value = const_bits(1);
    let second_value = const_bits(1);
    // Chain `delayed` twice to keep two values of the sequence in memory.
    let (wire, next_next_value) = builder.add_wire::<BITS>();
    let next_value = delayed(builder, second_value, next_next_value);
    let value = delayed(builder, first_value, next_value);
    // Sequence definition: s(n+2) = s(n) + s(n+1)
    let added = wrapping_add(builder, value, next_value);
    wire.drive(builder, added);
    value
}

#[test]
fn test_fibonacci() {
    let builder = &Builder::new();
    let signal = fibonacci_sequence::<7>(builder);
    let handle = builder.add_output("fibonacci_sequence", signal);
    let mut simulator = builder.build().simulate();
    let mut previous = 0;
    let values = Vec::from_iter(std::iter::from_fn(|| {
        let value: u32 = simulator.output_int(handle);
        simulator.tick_clock();
        let not_overflowed = value >= previous;
        previous = value;
        not_overflowed.then_some(value)
    }));
    // The next value 144 overflows 7-bit integers
    assert_eq!(values, [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89])
}

What?

Bascule is:

  • A simple model for logic circuits made exclusively of D flip-flops (bascule, in French) and NAND gates.
  • A pseudo-HDL in the form of a Rust API for defining such circuits
  • A Rust library of common components for boolean logic, integer arithmetic, RAM blocks, etc. They are all defined in terms of increasingly simpler components, down to D flip-flops and NANDs.
  • An optimizer that simplifies circuits where possible
  • A simulator where users can set input signals, tick the clock, and read output signals
  • (Eventually, maybe, a RISC-V CPU implemented in Bascule HDL.)

Why?

Computing is all about abstractions. You’re reading this over the internet, and many things were involved to make it happen. We build layers of abstractions to manage this complexity so we can rely on lower layers when building something on top, without thinking constantly about how they work.

Still, having some understanding of lower layers can be useful, especially when things break down. For example reading the generated assembly can help debug or optimize Rust code. What about going all the way down? Can we build a computer from scratch? Let’s assume we’re done inventing the universe with electricity and silicon semi-conductors.

I was inspired by Ben Eater who made educational videos, among other things, on:

… as well as a series on building a programmable 8-bit computer from scratch on breadboards using only simple logic gates.

These videos are very well made, and show that building a computer is not so unattainable. I wanted to build something of my own, but hardware has its downsides so I went with simulation. Now, what’s the simplest possible set of primitives we can reasonably simulate and build a computer out of?

The circuit model

A Bascule circuit contains booleans signals that can vary over time, and is always either true or false. Components are idealized, there is no high-impedance / un-driven / “Z” signal or indeterminate / “X” signal.

A circuit is made of:

  • A single shared clock
  • Input signals that are driven externally
  • NAND logic gates
  • D flip-flops
  • Output signals that are driven by some part of the circuit and made available for external use

The clock does not have an inherent frequency. Instead, its ticks are what define time for this idealized model. We ignore propagation delays and other real-world concerns.

NAND gates define all combinatorial logic in the circuit. They each have two boolean inputs and one boolean output with the truth table below. NAND is sufficient to express any boolean function as it is is functionally complete. The directed graph of connections where a NAND gate input is driven by a NAND gate output must be acyclic. That is, the circuit must not have feedback thet does not go through a D flip-flop. This helps simplify the model and simulation.

a b NAND(a, b)
0 0 1
1 0 1
0 1 1
1 1 0

D flip-flops define all stateful parts of the circuit and make it capable of sequential logic. They each have one boolean input and one boolean input. They are implicitly driven by the shared clock. The output is initially false until the first clock tick. Whenever the clock ticks, the output takes the current value of the input and keeps until the next tick, even if the input value changes in the meantime. In effect, each flip-flop stores one bit of memory.

The data structure below would be sufficient to define a Bascule circuit:

struct CircuitDefinition {
    input_count: usize,
    nand_gate_inputs: Vec<[SignalSource; 2]>,
    flip_flop_next_values: Vec<SignalSource>,
    output_signals: Vec<SignalSource>,
}

enum SignalSource {
    Constant { value: bool },
    Input { index: usize },
    NandGateOutput { index: usize },
    FlipFlopOutput { index: usize },
}

I believe this model is sufficient to represent any finite-state machine.

Why not an even simpler model?

Ben Eater’s 8-bit computer series shows how a latch and then a flip-flop can be built out of NAND gates, so we could simplify the model by making D flip-flops a library component rather than a primitive. However this requires connecting NAND gates with signal feedback, which we’ve explicitly banned from the model. Lifting this restriction would make simulation more difficult (for example: what if a circuit is astable?) compared to keeping the stateful parts to an explicit primitive.

The HDL

The Bascule Hardware Definition Language is not actually a language, since the language is Rust. The bascule crate provides a Builder type that you incrementally add stuff to in order to build up a circuit definition.

For example:

use bascule::boolean::xor;
use bascule::memory::delayed;
use bascule::{Builder, Signal};

fn delayed_xor(builder: &Builder, a: Signal<1>, b: Signal<1>) -> Signal<1> {
    let initial = [false];
    delayed(builder, initial, xor(builder, a, b))
}

let builder = &Builder::new();
let (_a_handle, a) = builder.add_input("a");
let (_b_handle, b) = builder.add_input("b");
let _out_handle = builder.add_output("delayed xor", delayed_xor(builder, a, b));
print!("{}", builder.build().graphviz());

Piping the Graphviz output to dot -T svg -o delayed-xor.svg produces the visualization below. Circles are NAND gates, diamonds are D flip-flops, rectangles are inputs and outputs.

On top of the base model, Bascule HDL adds two core concepts: multi-bit signals and wires.

Instead of manipulating 1-bit boolean signals individually we group them in sequences with the Signal<const WIDTH: usize> type. The width of a signal is its number of bits. The convention for interpreting a signal as an integer is least-significant bit first.

As shown above, the convention for reusable components is to define a Rust function that takes &Builder and some input signals as parameters (possibly among other parameters like delayed’s initial), and return output signals. The bascule crate provides such functions for some common components.

Sometimes the input signals you want to give to a compoent may depend on its outputs, or there may be some other kind of cycle between components. (Again, the model only allows such cycles if they go through D flip-flops or components based on them such as those in the bascule::memory module.) To help with this, the wire method returns a placholder signal that can be used now and handle that needs to be driven by some other signal later. The fibonacci sequence circuit above is an example of using a wire.

The optimizer

Combining components often produces a circuit with redudant NAND gates (or D-flip-flops, more rarely). Bascule provides an optimizer to simplify such redundancy. It only uses local reasoning, but runs in a loop until finding a fixed point.

Below is the visualization of a 3-bit ripple-carry adder, before and after optimization. Circles are NAND gates, inputs and outputs are shown least-significant bit first left to right.

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.

No runtime deps