Introduction
I want to build a game where you can draw a circuit and have it be running while you're drawing. The circuit should control some thing in a virtual environment, like a tiny car or traffic lights.
The circuit "language", as designed by realhet, features only 3 building blocks: The wire (any pixel where the R, G or B is >=244), a wire crossing and a not gate.
My first goal is to build the bitmap compiler, where "the game" can only load an image of this CPU made by realhet (which I've slightly modified). It will compile the image and run it as fast as possible.
In this blog, I'll share the development proces of building the bitmap compiler by sharing snippets of code.
About me
I usually write web-applications using languages like Javascript, Ruby and Elixir. I'm not a C programmer. This C code may be unconventional or otherwise wrong.
This blog includes incomplete code samples, including a mix of code from header files (.h) and source files (.c).
Reading an image
To start with, I need to read the image from disk to memory. I'll be using libpng to read the bitmap file to a custom image_data_t-struct.
typedef struct {
uint8_t r;
uint8_t g;
uint8_t b;
} rgb_t;
typedef struct {
uint32_t width;
uint32_t height;
rgb_t *data;
} image_data_t;
For those not familiar with C, a struct is simply an object with predefined fields and no methods.
uint8_tanduint32_tare unsigned (u) integers (int) of 8-bits or 32-bits in size. These integer types are defined instdint.h
With the help of Google and ChatGPT, I've scrambled together an obsene amount of code for reading an image. Every time I encounter code like this, it's a reminder how much is actually happening under the hood for a simple task like reading an image. Because this blog isn't about reading PNG files, I've shared the code here.
I then write a test using a very tiny testing header found here.
image_data_t image_data;
image_data_initialize(&image_data);
image_data_png_read(&image_data, "./assets/fixed-cpu.png");
mu_assert("error, image_data.width != 1024", image_data.width == 1024);
mu_assert("error, image_data.height != 1024", image_data.height == 1024);
Success!
Rules of the bitmap language
Any pixel that has an R, G or B value of >=224 is considered a conductive pixel. Any other pixel is considered non-conductive. Conductive and non-conductive pixels can have any color, it only matters whether they have an R, G or B value of >=224.
For the circuit simulation, a conductive pixel can be powered or unpowered, and it's powered-state can change at most once per tick. Conductive pixels that touch sides share their "powered"-state. This allows the player to draw "wires". Powering the wire at any point powers all the pixels in the whole line at once. A line is powered if it has one or more sources of power.
The wire crossing allows crossing 2 independent wires without connecting them. A 3x3 grid containing 4 conductive pixels in a +-shape is considered a wire crossing. The lines connecting to the upper and lower pixels share state, and the lines connecting to the left and right pixels share state, but otherwise their state is kept separate, because they don't touch.
A NOT-gate acts as a power source, powering the output wire if the input wire is unpowered. Like the wire crossing, the NOT-gate is a 3x3 grid, but with a C-shaped input and a single pixel for the output.
The state of the input is independent from the output, but the output will become powered if the input is unpowered. Once the input wire is powered, the NOT-gate will no longer act as a power source and the output wire might become unpowered if there's no other power source for that wire.
For example, two not-gates with an output connected to a single wire will power the output wire if the input of any not-gate is unpowered. Only if both not-gates are powered, the output wire will be unpowered, basically making a NAND gate. You can connect the outwire wire to another not-gate to make an AND-gate, where the output of that new gate is powered when both input not-gates are powered.
Compiling the image: Finding wires, NOT-gates and crossings
The first step of compiling the image will be finding wires, not-gates and crossings. I'll store these in a struct named nodemap_t. This struct will be like image_data_t, but instead of storing a color per pixel, it will store whether a pixel is "nothing", a conductive wire, the center of a crossing, or the center of some NOT-gate.
For faster processing, I also keep a list of pixel indeces for wire crossings, and pixel indeces for the inputs and outputs for not gates.
typedef struct {
uint32_t size;
uint32_t capacity;
uint32_t *data;
} uint32_list_t;
void uint32_list_add(uint32_list_t *uint32_list, uint32_t value);
typedef struct {
uint32_t width;
uint32_t height;
// for every not-gate, there will be 2 indeces here, one for the in-index and
// one for the out-index.
uint32_list_t not_gate_index_pairs;
// pixel-data with 1 element (byte) per pixel. Value is one of
// the NODE_* constants.
uint8_t *data;
} nodemap_t;
const uint8_t NODE_NONE = 0;
const uint8_t NODE_WIRE = 1;
const uint8_t NODE_CROSSING = 2;
const uint8_t NODE_NOT_EAST = 3;
const uint8_t NODE_NOT_WEST = 4;
const uint8_t NODE_NOT_NORTH = 5;
const uint8_t NODE_NOT_SOUTH = 6;
// Resize nodemap to have a certain width and height, and reallocate to fit
// that amount of data.
void nodemap_resize(nodemap_t *nodemap, uint32_t width, uint32_t height);
void nodemap_put(nodemap_t *nodemap, uint32_t x, uint32_t y, uint8_t value);
// Parse wire-nodes and assign not-gates and crossings, populating
// not_gate_index_pairs.
void nodemap_parse(nodemap_t *nodemap);
bool rgb_is_high(rgb_t rgb);
To start compiling the image, I first scan the image data for conductive pixels and write the result to nodemap_t.data using nodemap_put.
const uint8_t RGB_HIGH = 224;
inline bool rgb_is_high(rgb_t rgb) {
return rgb.r >= RGB_HIGH || rgb.g >= RGB_HIGH || rgb.b >= RGB_HIGH;
}
// Get a pointer to a specific pixel in the image data
rgb_t *image_data_at(image_data_t *image_data, uint32_t x, uint32_t y);
void image_data_to_nodemap(image_data_t *image_data, nodemap_t *nodemap) {
nodemap_resize(nodemap, image_data->width, image_data->height);
for (uint32_t y = 0; y < image_data->height; y++) {
for (uint32_t x = 0; x < image_data->width; x++) {
nodemap_put(nodemap, x, y, rgb_is_high(*image_data_at(image_data, x, y)));
}
}
nodemap_parse(nodemap);
}
I scan the nodemap wire-data to find not-gates and crossings. A NOT-gate will have the same 4 conductive pixels around the center pixel as the wire crossing, so I can start looking at any location that has 4 conductive pixels around a non-conductive center pixel.
// For each pixel (except all pixels at the edge of the image). EG:
// for (y = 1; y < height - 1; y++)
// for (x = 1; x < width - 1; x++)
uint8_t *self = nodemap->data + index;
if (is_wire(self)) continue;
uint8_t *yn = self - width;
uint8_t *yp = self + width;
if (!is_wire(yn) || !is_wire(yp) || !is_wire(self - 1) ||
!is_wire(self + 1))
continue;
// these 4 variables are named based on whether they're relative to the
// YX of self or index: n = -1, p = +1. So pn is a y+1, x-1.
bool nn = is_wire(yn - 1);
bool np = is_wire(yn + 1);
bool pn = is_wire(yp - 1);
bool pp = is_wire(yp + 1);
if (nn && np && !pn && !pp) {
// Write nodemap->data[index] with the node-type (not-gate pointing south)
*self = NODE_NOT_SOUTH;
// Add not-gate input and output index to not_gate_index_pairs
uint32_list_add2(not_gate_index_pairs, index - width, index + width);
} else if (pn && pp && !nn && !np) {
*self = NODE_NOT_NORTH;
uint32_list_add2(not_gate_index_pairs, index + width, index - width);
} else if (nn && pn && !np && !pp) {
*self = NODE_NOT_EAST;
uint32_list_add2(not_gate_index_pairs, index - 1, index + 1);
} else if (np && pp && !nn && !pn) {
*self = NODE_NOT_WEST;
uint32_list_add2(not_gate_index_pairs, index + 1, index - 1);
} else if (!nn && !np && !pn && !pp) {
*self = NODE_CROSSING;
}
Next comes the hard part: Determining which pixels belong to the same wire.
Mapping pixels to wire IDs.
Next, I need to combine conductive pixels that share the same wire somehow. The plan is to assign each wire a unique ID, and give all pixels making a wire that same ID.
Like before, I'm storing the result in an image-like struct.
typedef struct {
uint32_t width;
uint32_t height;
uint32_t max_id;
uint32_t *data;
} wiremap_t;
In this struct, every pixel stores the ID of the wire. If the ID is 0, it is part of no wire. max_id will store the highest wire-id. I'm going to loop through every pixel, and for every unassigned conductive pixel I find, I'm going to assign it a new ID. Then, all adjecent conductive pixels will be given the same ID.
I'm going to use a flood fill algorithm to find all adjecent pixels. I'm going to write a very simple algorithm where I basically walk through every adjecent pixel to see if the pixel is conductive. If I encounter a crossing, I jump it by advancing an extra pixel (2 pixels)
For testing, I'm going to use this slightly more complicated test image. For clarification, the expected result is shown as a colored image where each color represents a wire id.
Let's write the flood fill!
static void _fill(const nodemap_t *nodemap, wiremap_t *wiremap,
uint32_list_t *stack, uint32_t x, uint32_t y,
uint32_t next_id) {
uint32_t width = nodemap->width;
uint32_t height = nodemap->height;
uint32_t width_minus_one = width - 1;
uint32_t height_minus_one = height - 1;
uint32_list_clear(stack);
uint32_list_add2(stack, x, y);
while (stack->size > 0) {
y = uint32_list_pop(stack);
x = uint32_list_pop(stack);
uint32_t index = y * width + x;
if (nodemap->data[index] != NODE_WIRE || wiremap->data[index]) continue;
wiremap->data[index] = next_id;
if (x < width_minus_one) {
uint8_t node = nodemap->data[index + 1];
if (node == NODE_WIRE)
uint32_list_add2(stack, x + 1, y);
else if (node == NODE_CROSSING)
uint32_list_add2(stack, x + 2, y);
}
if (x > 0) {
uint8_t node = nodemap->data[index - 1];
if (node == NODE_WIRE)
uint32_list_add2(stack, x - 1, y);
else if (node == NODE_CROSSING)
uint32_list_add2(stack, x - 2, y);
}
if (y < height_minus_one) {
uint8_t node = nodemap->data[index + width];
if (node == NODE_WIRE)
uint32_list_add2(stack, x, y + 1);
else if (node == NODE_CROSSING)
uint32_list_add2(stack, x, y + 2);
}
if (y > 0) {
uint8_t node = nodemap->data[index - width];
if (node == NODE_WIRE)
uint32_list_add2(stack, x, y - 1);
else if (node == NODE_CROSSING)
uint32_list_add2(stack, x, y - 2);
}
}
}
_fill is called for every XY coordinate that has a conductive pixel and is not yet assigned an ID. next_id is an unused ID to be assigned to the current pixel, and any adjecent conductive pixel.
stack is just an array where I keep track of pixels that need to be visited. I pass it as a param to reuse any allocated memory. Clearing the stack using uint32_list_clear doesn't free memory, it just sets the size to 0.
I'm sure it isn't the most efficient implementation, but it works!
Now the wires have assigned IDs, I can combine the wire IDs with the NOT-gates.
Creating NOT-gates list
For the simulation, the state of a wire is determined by NOT-gates it is connected to. A wire is powered if there is any NOT-gate with an unpowered input.
Therefore, the only thing the simulation needs to be aware of, is the list of NOT-gates attached to a wire, and the powered/unpowered state of a wire.
The powered-state of a wire can simply be an array of booleans. To advance the simulation, I need to iterate through all NOT-gates and change the output of each NOT-gate based on the powered-state of the input wire.
To start with implementing this, I need a list of NOT-gates with the ID of their input and output wires. I'm also going to store the position of each NOT-gate output and input pixel as the index.
typedef struct {
uint32_t in_id;
uint32_t out_id;
uint32_t in_index;
uint32_t out_index;
} not_gate_t;
typedef struct {
uint32_t size;
uint32_t capacity;
not_gate_t *not_gates;
} not_gate_list_t;
void not_gate_list_initialize(not_gate_list_t *not_gate_list);
void not_gate_list_clear(not_gate_list_t *not_gate_list);
void not_gate_list_ensure_capacity(not_gate_list_t *not_gate_list,
uint32_t required_capacity);
void not_gate_list_add(not_gate_list_t *not_gate_list, not_gate_t not_gate);
void not_gate_list_free(not_gate_list_t *not_gate_list);
To populate the not_gate_list, I need the list of NOT-gates and the IDs of wires per pixel. The list of NOT-gates is stored in nodemap's not_gate_index_pairs. The IDs of wires is stored in the wiremap.
I'm going to loop through not_gate_index_pairs and create a not_gate_t for each pair.
void nodemap_wiremap_to_not_gate_list(const nodemap_t *nodemap,
const wiremap_t *wiremap,
not_gate_list_t *not_gate_list) {
const uint32_t size = nodemap->not_gate_index_pairs.size / 2;
not_gate_list_clear(not_gate_list);
not_gate_list_ensure_capacity(not_gate_list, size);
const uint32_t *pair_data = nodemap->not_gate_index_pairs.data;
for (uint32_t i = 0; i < size; i++) {
not_gate_t not_gate;
not_gate.in_index = *(pair_data++);
not_gate.in_id = wiremap->data[not_gate.in_index];
not_gate.out_index = *(pair_data++);
not_gate.out_id = wiremap->data[not_gate.out_index];
not_gate_list_add(not_gate_list, not_gate);
}
}
This list is the last thing I need to finish the compile proces. Now I can use the not_gate_list to create a program.
Creating & Running a program
Loading the program involves clearing any existing program, loading the NOT-gates, randomizing the order of NOT-gates, and making sure the state is initialized (all zeroed)
For efficiency, the not-gates input IDs and output IDs are copied to their own arrays.
typedef uint32_t gate_io_t;
typedef uint8_t gate_state_t;
typedef enum fixed_state {
FIXED_NONE = 0,
FIXED_LOW = 1,
FIXED_HIGH = 2
} fixed_state_t;
typedef struct program_state {
uint32_t id_state_size;
uint32_t id_state_capacity;
bool *id_state;
// The fixed-state status per ID. A fixed state forces the value to either
// FALSE or TRUE of a state at the end of every iteration. If the fixed-state
// is 0, no state is enforced.
fixed_state_t *fixed_state_map;
// Number of high src_gates per ID. If >0, the id_state should be true.
// fixed_state can override the final value.
uint32_t *high_count;
// NotGate sized arrays
uint32_t not_gate_size;
uint32_t not_gate_capacity;
not_gate_t *not_gates;
gate_state_t *gate_state;
float *slow_state;
gate_io_t *in_ids;
gate_io_t *out_ids;
// A set of all state-ids that are affected by fixed_state. Basically, this
// set includes all non-zero IDs in fixed_state_map.
uint32_hash_set_t fixed_state_ids;
// Seed for random. This value can change any time as random values are
// created.
unsigned int random_seed;
} program_state_t;
void program_state_next(program_state_t *program_state) {
const uint32_t not_gate_size = program_state->not_gate_size;
for (uint32_t i = 0; i < not_gate_size; i++)
_update_gate_state(program_state, i, !_get_gate_input(program_state, i));
_force_fixed_state(program_state);
}
Running the program involves checking the state of the input wire of each gate and changing the output if the input is changed. The input is checked using _get_gate_input, and the output is updated using _update_gate_state.
static gate_state_t _get_gate_input(const program_state_t *program_state,
uint32_t index) {
uint32_t in_id = program_state->in_ids[index];
uint8_t fixed_state = program_state->fixed_state_map[in_id];
if (fixed_state > 0) return fixed_state == FIXED_HIGH;
return program_state->high_count[in_id] > 0;
}
_get_gate_input is a function that should return the current state of the input wire for a gate.
If the state of the input wire is fixed by fixed_state, that state is used for the input wire. Otherwise, high_count is used to determine the number of gates with "high" (powered) outputs per wire. If at least one gate powers the output wire, the wire is powered and get_gate_input returns true.
The target state of a gate will be the opposite of the input; If the gate input was false, the target_state will be true, and vice-versa. _update_gate_state is called with the inverse of _get_gate_input:
static void _update_gate_state(program_state_t *program_state, uint32_t index,
gate_state_t target_state) {
gate_state_t *gate_state = program_state->gate_state;
float *slow_state = program_state->slow_state;
if (target_state) {
if (gate_state[index]) return;
if (slow_state[index] >= 0.5f) {
_set_gate_state(program_state, index, true);
return;
}
slow_state[index] +=
random_range_f(&program_state->random_seed, 0.5f, 1.0f);
if (slow_state[index] >= 1.0f) _set_gate_state(program_state, index, true);
} else {
if (!gate_state[index]) return;
if (slow_state[index] <= 0.5f) {
_set_gate_state(program_state, index, false);
return;
}
slow_state[index] -=
random_range_f(&program_state->random_seed, 0.5f, 1.0f);
if (slow_state[index] <= 0.0f) _set_gate_state(program_state, index, false);
}
}
_update_gate_state checks if the target state is different from the current state, and will change slow_state by some random amount. If the slow_state exceeds the 0..1 range, the state-change will be confirmed using _set_gate_state.
The randomness allows the system to end up in a stable state, as the gates will not update simultaneously.
You can play around with (an outdated copy) of the simulation here: https://charperbonaroo.github.io/bls/#0
Originally published at: https://www.bonaroo.nl/2023/10/30/microengineer-compiler.html
Top comments (0)