# Writing a digital logic simulator - Part 2

In this post we will define the architecture of the simulator.

# Previous posts

Part 1

The first post was a short introduction to digital logic and Rust, we created a NAND gate, and used it to build an OR gate. But the connections between gates were set implicitly in the code, in this post we will make them real.

# The structural struct

So we need a generic way of representing components and their connections. Here we go:

``````struct Structural {
components: Vec<Component>,
connections: Vec<Connection>,
}
``````

A `Structural` is a collection of components and connections. I gave it this name because a structural architecture is exactly that, interconections between components. The implementation from above looks too simple, but it could work.

If you just want to see the finished implementation, the code is available at the end of this post, but for now let’s think how to implement a `Connection`:

``````struct Connection {
from: Index,
to: Vec<Index>,
value: Bit,
}
``````

Maybe it could be a `Bit` with additional `from` and `to` properties. It is important that one output can be connected to multiple inputs (hence `to` is a `Vec<Index>`), but if two outputs are connected together there could be a short circuit, and that’s bad, so we won’t allow it. But this way, to get all the connections from some `Index` we need to search the entire vector. Since the from field should be unique, we can transform it into:

``````HashMap<Index, (Vec<Index>, Bit)>
// let (to, value) = hashmap[from];
``````

Given an index return all the indexes connected to it. But what is an `Index`? Well, we could just store all the internal signals (the inputs and outputs of all the components) together, as a vector, and then indexing this vector would give us any input or output. Or we could store the signals as a `Vec<Vec<Bit>>` and make the `Index` a pair `(component_id, port_id)` where we first index by `component_id` and then by `port_id`. This way given an index we can see to which component it pertains, and to which input it is connected to, and all the inputs of one component are stored together. Since the only way to interface with internal components is via the `update` method, which requires us to pass all of the inputs together, storing all the inputs as a separated vector will probably be faster than searching all the inputs in a vector or a hashmap.

But we also need to:

• Get all the connections of the inputs from outside.

• Get all the outputs of the `Structural` to outside.

• Given an internal component, get all its inputs.

• Given an internal component, get all the connections of its outputs.

But how do we know how many inputs and outputs does this `Structural` component have? Since it can be any number, we need to store it somewhere. Well, let’s update the definition of the `Component` trait, adding the number of inputs and outputs, and also the name because we will need to identificate components at some point.

``````trait Component {
fn update(&mut self, input: &[Bit]) -> Vec<Bit>;
fn num_inputs(&self) -> usize;
fn num_outputs(&self) -> usize;
fn name(&self) -> &str;
}
``````

After thinking a while, this is what I came up with:

``````struct Structural {
components: Vec<CompIo>,
num_inputs: usize,
num_outputs: usize,
name: String,
}
struct CompIo {
comp: Box<Component>,
input: Vec<Bit>,
output: Vec<Bit>,
connections: Vec<Vec<Index>>,
}
struct Index {
comp_id: usize,
input_id: usize,
}
``````

Maybe I abused the vector container a bit, but this looks like it’s going to work. For every component we create a `CompIo` struct which tracks its inputs, outputs, and connections. Nice! Oh, and since `Component` is a trait we need to `Box` it to be able to store a generic `Component`. A `Box` is just an owned pointer, if that helps. The connections are represented as a `Vec<Vec<Index>>`, so to get the connections of the first output we do ```let con = connections;```, and that returns a `Vec<Index>` of all the connections. The only think left is how to deal with the special case of outputs to the outside, the ones we return on `update`, where do we store them? One solution is to have a special component which doesn’t do anything but we use it as an interface with the outside. This will be the component 0.

But before implementing it, let’s see how we would create components this way. We will try to create the OR from last post: ``````// Create the special component 0
let mut c_zero = CompIo::c_zero(2, 1); // 2 inputs, 1 output, c_id: 0
// Create the actual components
let mut nand_a = CompIo::new(Box::new(Nand::new(1))); // c_id: 1
let mut nand_b = CompIo::new(Box::new(Nand::new(1))); // c_id: 2
let mut nand_c = CompIo::new(Box::new(Nand::new(2))); // c_id: 3

c_zero.add_connection(0, Index::new(1, 0)); // input 0 -> nand_a
c_zero.add_connection(1, Index::new(2, 0)); // input 1 -> nand_b
nand_a.add_connection(0, Index::new(3, 0)); // nand_a -> nand_c(0)
nand_b.add_connection(0, Index::new(3, 1)); // nand_b -> nand_c(1)
nand_c.add_connection(0, Index::new(0, 0)); // output of nand_c == output of or

let c = vec![c_zero, nand_a, nand_b, nand_c];
let mut or_gate = Structural::new(c, 2, 1, "OR2");
``````

First we create the components, we need to box the NAND gates to store them as `Component`s. I annotated the component index (`c_id`) as a comment, that is the index of this component in the `c` vector that we pass to `Structural::new` on the last line. The connections are defined with a simple interface. We pass the `output_id` (with the exception of `c_zero` where we pass the `input_id`), and make an `Index` from the `component_id` and `input_id` where this output will be connected (again with the exception of `c_zero`, if we want to connect something to the output of the structural we call `Index::new(0, 0)`). It isn’t as bad as it looks, we just have to be careful with the indexes. But most importantly, once we `impl Component for Structural` we will be able to nest components like crazy, so let’s begin!

``````impl CompIo {
fn new(comp: Box<Component>) -> CompIo {
let input = vec![Bit::X; comp.num_inputs()];
let output = vec![Bit::X; comp.num_outputs()];
let connections = vec![vec![]; comp.num_outputs()];
CompIo { comp, input, output, connections }
}
fn add_connection(&mut self, output_id: usize, to: Index) {
self.connections[output_id].push(to);
}
}
``````

`CompIo` is pretty straightforward: we allocate the input and output vectors with the given size, and we leave the connections empty. By default, the component will not be connected to anything. We are initializing the inputs as `Bit::X`, a new variant of `Bit` which means undefined. This way we can catch floating pins.

``````enum Bit {
L, // Low, false, 0
H, // High, true, 1
X, // Undefined
}
``````

`X` can be seen as the default state when we power on the circuit: from a programmer’s perpective we can call it uninitialized. It may have a valid value, but we shouldn’t use it. But we can use it, and then it behaves like it’s both 0 and 1 until we observe it. For example, the OR gate with undefined inputs:

``````[H, L] = [H]
[H, H] = [H]
[H, X] = [H]
[L, L] = [L]
[L, H] = [H]
[L, X] = [X]
``````

When one input is 1, the output is always 1, even with an X. But `0 OR X` could be either 1 or 0 so it stays as X. Another interpretation would be a short circuit: if we connect two outputs together, and one output is 0 and the other is 1, then the result is an X. We should also update our NAND gate to deal with undefined inputs, and also implement the new methods of the `Component` trait:

``````impl Component for Nand {
fn update(&mut self, input: &[Bit]) -> Vec<Bit> {
assert_eq!(self.num_inputs, input.len());
let mut x = Bit::L;
for a in input {
match *a {
// If any input is 0, the output is 1
Bit::L => return vec![Bit::H],
// X NAND L = H, but X NAND H = X
Bit::X => x = Bit::X,
Bit::H => {},
}
}

vec![x]
}
fn num_inputs(&self) -> usize {
self.num_inputs
}
fn num_outputs(&self) -> usize {
1
}
fn name(&self) -> &str {
"NAND"
}
}
``````

Now if we test our implementation of the OR gate from the previous post with undefined inputs, we see that it actually works as expected.

``````[X, L] = [X]
[L, X] = [X]
[X, H] = [H]
[H, X] = [H]
``````

It actually works! This means that we can change the `update` of the NAND gate, and since our components are just combinations of NAND gates, they will keep working as expected. But let’s keep working on the `CompIo`. The `CompIo::c_zero` function is identical to the `CompIo::new`, but the “input” of component 0 is the output of the `Structural`, because if we are inside the component, we read the inputs just like we read the outputs of the other components. So we just need to swap num_inputs and num_outputs. And then, in `Structural::new` we verify that assumption.

``````impl Structural {
fn new(components: Vec<CompIo>, num_inputs: usize, num_outputs: usize,
name: &str) -> Structural {
// Component 0 must have been created using CompIo::c_zero
assert_eq!(components.input.len(), num_outputs);
assert_eq!(components.output.len(), num_inputs);
assert_eq!(components.connections.len(), num_inputs);
// TODO: check that all the connections are valid
let name = name.to_string();
Structural { components, num_inputs, num_outputs, name }
}
}
``````

We already have the information about the number of inputs and outputs stored in component 0, but we pass it to `new` as a form of error checking. So let’s `impl Component for Structural`:

``````impl Component for Structural {
fn update(&mut self, input: &[Bit]) -> Vec<Bit> {
assert_eq!(input.len(), self.num_inputs());
// Propagate input
self.propagate_input(input);
// Update components
self.update_components();
// Propagate internal signals
self.propagate_signals();
// Return the component output
self.output()
}
fn num_inputs(&self) -> usize {
self.num_inputs
}
fn num_outputs(&self) -> usize {
self.num_outputs
}
fn name(&self) -> &str {
&self.name
}
}
``````

“Hey what’s with all that useless comments? I want to see the actual implementation!” Don’t worry, there is a reason why I structured it that way.

# The order of the updates

It’s very important that the order of the updates doesn’t affect the end result. In our OR gate the 2-input NAND must be updated the last, after the signal of the 1-input NANDs arrives to it. If we first updated the 2-input NAND, the output wouldn’t match our expectations. But how do we know the right order? Well, we could go left to right but the truth is that we don’t know, there may be loops in the circuit and then there isn’t a right order. So we give up, and follow some order that won’t affect the result. That order is the following:

• Propagate input: so the components have the correct input when updated

• Update components: but don’t propagate the updates yet

• Propagate signals: after updating all the components, propagate the changes

This way we make sure our simulator is “commutative”. The order in which we update the components doesn’t affect the result. This means that we can update all the components at once and get that sweet multi-thread performance bonus. Maybe later. For now, let’s see how these functions are implemented.

``````fn propagate(&mut self, c_id: usize) {
// TODO: avoid this clone
let connections = self.components[c_id].connections.clone();
for (out_id, to) in connections.iter().enumerate() {
for i in to {
self.components[i.comp_id]
.input[i.input_id] = self.components[c_id].output[out_id];
}
}
}
fn propagate_input(&mut self, input: &[Bit]) {
// The input is an output when seen from inside
self.components.output = input.to_vec();
self.propagate(0);
}
fn propagate_signals(&mut self) {
for c in 1..self.components.len() {
self.propagate(c);
}
}
fn output(&self) -> Vec<Bit> {
self.components.input.clone()
}
fn update_components(&mut self) {
for c in 1..self.components.len() {
// Magic pattern matching to make the borrow checker happy
let CompIo {
ref mut comp,
ref input,
ref mut output,
connections: _
} = self.components[c];
*output = comp.update(input);
}
}
``````

The code may be a bit long but it’s self explanatory, especially the `update_components` function which is just beautiful. Note that we skip the component 0, because it isn’t meant to be updated. Calling `update` on it should result in a panic. Oh, I forgot to mention what exactly is the component 0… It’s just a 0-input NAND. So it will indeed panic when updated with more than 0 inputs. As for the propagate function, it just iterates every output and updates all of its possible connections.

# Structural OR

Alright, let’s finally see the truth table of our new Structural OR gate:

``````[L, L] = [X]
[L, H] = [L]
[H, L] = [H]
[H, H] = [H]
``````

Well… That isn’t quite an OR gate. What’s happening? Well, remember that specific order of updates I mentioned earlier? It turns out that since all the components are updated at once, they can’t interact with each other. But don’t worry, that’s not a problem, because we just need to wait one update more for the signal to propagate. If we execute every input 3 times…

``````[L, L] = [X]
[L, L] = [L]
[L, L] = [L]
[L, H] = [L]
[L, H] = [H]
[L, H] = [H]
[H, L] = [H]
[H, L] = [H]
[H, L] = [H]
[H, H] = [H]
[H, H] = [H]
[H, H] = [H]
``````

Each line is an `or_gate.update(&i)`, and they are executed sequentally, so we see the correct output after one update. From now on, we will call every update a “tick”, so our OR gate has a 1-tick delay. Let’s put a few OR gates in series to see how they behave.

# OR-OR-OR ``````let mut c_zero = CompIo::c_zero(1, 1); // c_id: 0
let mut or_a = CompIo::new(boxed_or_gate()); // c_id: 1
let mut or_b = CompIo::new(boxed_or_gate()); // c_id: 2
let mut or_c = CompIo::new(boxed_or_gate()); // c_id: 3

c_zero.add_connection(0, Index::new(1, 0)); // input 0 -> or_a
c_zero.add_connection(0, Index::new(1, 1)); // input 0 -> or_a
or_a.add_connection(0, Index::new(2, 0)); // or_a -> or_b
or_a.add_connection(0, Index::new(2, 1)); // or_a -> or_b
or_b.add_connection(0, Index::new(3, 0)); // or_b -> or_c
or_b.add_connection(0, Index::new(3, 1)); // or_b -> or_c
``````

Now thanks to this new syntax, with just a few changes we have created something completely different. The `boxed_or_gate` is just a function that returns the OR gate we defined at the beginning. For simplicity, I just connected the same input twice to every gate, so our OR gate is now a simple buffer. We have put 3 OR gates in series, so the expected delay should be 3 ticks:

``````[L] = [X]
[L] = [X]
[L] = [X]
[H] = [X]
[H] = [X]
[H] = [L]
[L] = [L]
[L] = [L]
[L] = [H]
[H] = [H]
[H] = [H]
[H] = [L]
``````

Whaaat? 5 ticks? Why? Well, let’s see what’s happening: assume every `>` is an OR gate:

``````t=0  0>X>X>X
t=1  0>0>X>X
t=2  0>0>X>X
t=3  1>0>0>X
t=4  1>1>0>X
t=5  1>1>0>0
``````

Since we first update the gates and then propagate the signals, the output of the first gate is only avaliable to the second gate at t=2. Well, it is there at t=1, but then the second gate has already updated its state. This means that every connection adds 1 tick of delay, which should have been obvious because our NAND gates are 0-tick and combining 2 of them in series made a 1-tick OR gate. This isn’t a problem because we can just scale everything up, make our inputs change only once per 100 ticks and only display the output at that time. Also, this approach is more realistic, because real logic gates have a small propagation delay (known as tpd, usually arround 10ns).

As a side note, we could use this triple OR buffer as a memory device, it can store a total of 5 bits, 1 per tick. We will explore the different memory storage strategies in a future post.

But let’s see why we have chosen this approach instead of recursively updating all the components that need updates. What happens if we make a loop? ``````let mut c_zero = CompIo::c_zero(1, 1); // c_id: 0
let mut nand_a = CompIo::new(Box::new(Nand::new(2))); // c_id: 1

c_zero.add_connection(0, Index::new(1, 0)); // input 0 -> nand_a
nand_a.add_connection(0, Index::new(1, 1)); // nand_a -> nand_a
nand_a.add_connection(0, Index::new(0, 0)); // nand_a -> out
``````

And let’s see the truth table:

``````[L] = [H]
[L] = [H]
[L] = [H]
[L] = [H]
[L] = [H]
[L] = [H]
[H] = [L]
[H] = [H]
[H] = [L]
[H] = [H]
[H] = [L]
[H] = [H]
``````

See, when the input is 0, the output is 1 and everything is fine, but when the output is 1 and we set the input to 1, the output should be 0 but if it’s 0 then the NAND gate’s input is 0 and the output is 1 and everything breaks. In our implementation this means that the output keeps changing between 0 and 1 on every update, which isn’t ideal but it’s better than a crash. While it should be possible to detect this loops and just set the connections to X, it is harder than it sounds, sometimes these loops span hundreds of components, finding them would require a sophisticated analysis of the circuit as a whole.

# Conclusion

That should be enough for now. In the next post we will improve the simulation experience, because looking at a series of `[L] = [H]` lines isn’t very user friendly.

If you want to see the full implementation, the code is available online: Playground link

# Other posts

Written on February 14, 2018