Snippet for a fast logic gate VM.

gistfile1.cpp

enum class NodeType {
	InactiveNode,
	AndGate,
	OrGate,
	XorGate,
	NotGate,
	NandGate,
	NorGate,
	Input,		// Used for component I/O, and to implement more complicated logic components (buttons, displays, etc)
	Output
};

struct LogicNode {	// Should fit into one 64-bit register (8 bytes)

	// Node type (should be 8-bits)
	NodeType type = NodeType::InactiveNode;

	// Reserved for future use
	uint8 flags = 0x0;

	// Indices/references to current (owned state), left child/input, and right child/input (not used by all nodes)
	uint16 iref = 0, lref = 0, rref = 0;
};

class LogicSim {

protected:
	// Logic gate description and current routing state (for basic logic components)
	std::vector<LogicNode> nodes;

	// // Contains data for more complex nodes/logic components
	// std::vector<LogicComponent> specialNodes;

	// Logic gate state (duplicated 2x like a frame buffer – you have the current, 'active' state that's being used,
	// and then a next, inactive state that can be written to and worked on without altering the read-from state)
	std::vector<bool> nodeState0;	// The stl implements these as bitmask arrays (memory overhead is very low, so
	std::vector<bool> nodeState1;	// we could probably fit even large simulation states into a single 4kb cache line)
	bool curState;

	std::vector<bool> & getCurrentState () {
		return curState ? nodeState0 : nodeState1;
	}

	// Used for internal memory management (keeping track of freed nodes/state entries)
	std::vector<uint> freeNodeStack, freeStateStack;
};


void LogicSim::simulateStep () {

	curState = curState ? false : true;
	auto & currentState = curState ? nodeState0 : nodeState1;
	auto & nextState    = curState ? nodeState1 : nodeState0;

	// Optimization note:
	//	The data is small enough that it can fit entirely within the L1 cache – thus this code (with its heavy
	//	memory i/o) will run extremely fast. Size isn't really a problem since we max out at 65k nodes (uint16
	//	limitation), and the node descriptor (which can be streamed from the L2) is only 400kb for 50k nodes, while
	//	the node *state* – basically two bit arrays – fits in 13k (for 50k nodes) and can just sit on the L1
	//	for the duration of the sim update.

	// Simulate basic, built-in nodes (very fast)
	for (auto node : nodes) {
		switch (node.type) {
			case LogicNode::InactiveNode: break;
			case LogicNode::AndGate:  nextState[node.iref] = currentState[node.lref] & currentState[node.rref]; break;
			case LogicNode::OrGate:   nextState[node.iref] = currentState[node.lref] | currentState[node.rref]; break;
			case LogicNode::XorGate:  nextState[node.iref] = currentState[node.lref] ^ currentState[node.rref]; break;
			case LogicNode::NotGate:  nextState[node.iref] = !(currentState[node.lref]); break;
			case LogicNode::NandGate: nextState[node.iref] = !(currentState[node.lref] & currentState[node.rref]); break;
			case LogicNode::NorGate:  nextState[node.iref] = !(currentState[node.lref] | currentState[node.rref]); break;
			case LogicNode::XnorGate: nextState[node.iref] = !(currentState[node.lref] ^ currentState[node.rref]); break;
			case LogicNode::BufferGate: nextState[node.iref] = currentState[node.lref]; break;
			case LogicNode::Output:		nextState[node.iref] = currentState[node.lref]; break;
			case LogicNode::Input:		break;
		}
	}

	// // Simulate other, custom nodes (components and stuff using Input/Output nodes, etc) that
	// // are too complicated to be represented/simulated by the above.
	// for (auto node : specialNodes) {
	// 	node.simulate(currentState, nextState);
	// }
}


LogicNode & LogicSim::createNode(NodeType type, bool startingState = false) {

	auto & node = freeNodeStack.size() != 0 ? nodes[freeNodeStack.pop_back()]
											: (nodes.push_back(), nodes.back());
	node.type = type;
	node.iref = freeStateStack.size() != 0 ? freeStateStack.pop_back()
										   : (nodeState0.push_back(), nodeState1.push_back(), nodeState0.size() - 1);
	nodeState0[node.iref] = nodeState1[node.iref] = startingState;
	return node;
}

LogicNode & LogicSim::getNode (uint idx) {
	return idx < nodes.size() ? nodes[idx] : nodes[0];
}

bool LogicSim::getNodeState (uint idx) const {
	return idx < nodes.size() ? getCurrentState()[nodes[idx].iref] : false;
}

void LogicSim::deleteNode (uint idx) {
	if (idx >= nodes.size())
		return;
	nodes[idx].type = NodeType::InactiveNode;
	freeStateStack.push_back(nodes[idx]);
	freeNodeStack.push_back(idx);
	nodes[idx].iref = 0;
}

Note: using this approach, each node only takes up two bits for the node state, plus 8 bytes for the logic gate descriptor (node type, associated memory, and two input references), with slightly more for more complex logic components (buttons, displays, etc). Ofc implementing the node references as uint64s restricts the max addressable nodes in a simulation to 65k, but the minimal overhead is worth it (the entire simulation can be loaded into the L1/L2 cache). For example, the node descriptors could be streamed from the L2 cache, but since each node only takes up 2 bits of active state, you could store the entire simulation state of a massive 50k logic gate simulation in 13kb of the L1 cache, which is just... insane.

The rest (node data) could be stored in 400kb-1mb of the L1/L2, depending on overhead for the special logic components. Displaying this to the user via graphics/UI and making the whole thing interactive would be the most expensive/complicated part, though the renderer could be sped up by sticking the (visual) nodes in a scene graph and using occlusion culling – and you could do some tricks like running the simulation multiple times between rendering cycles when in "crunch" mode – ie. to simulate complex structures like ALUs/CPUs and the like (if possible), since the simulation would likely be many times faster than the renderer.

Design approach:
– sim/vm models the relationship between logic nodes, and possesses the node state(s) which are updated each simulation step. Model code doesn't have anything to do with view code, so the simulation can be optimized on its own.
– view code (and view models) are built on top of that, and don't have anything to do with the actual simulation (it just queries the sim for node state and connections so that it can properly render stuff). Can be optimized for rendering on its own, and multiple views / view models could exist that use the same underlying sim code. (eg. could provide a stylized 'tron mode' w/ tons of sweet rendering fx in addition to the regular editor view)
– the controller wires everything together, notably keeping the 'model' and 'view model' data structures synchronized, and handling creation, modification, and destruction of logic nodes as a whole. The controller is event-driven, and the events are dispatched by a FSM that responds to user input (mouse clicks, drag begin/end, etc).