My home page
Back to my software experience page
Back to my portfolio
The CIRCUIT-SIM package implements a relatively simple digital circuit simulator similar to that described in Abelson & Sussman's Structure and Interpretation of Computer Programs ("SICP").
The variable CIRCUIT-SIM:*AGENDA* contains a queue of time-stamped events. The functions CIRCUIT-SIM:PROPAGATE and CIRCUIT-SIM:PROPAGATE-UNTIL process the events in that queue, either until the queue is empty or the specified time has been reached, respectively.
The basic signals are carried on circuit elements created by CIRCUIT-SIM:MAKE-WIRE and CIRCUIT-SIM:MAKE-BUS. Wires have arbitrary values, but only 0/1 or NIL/T have definite logical values. (The idea is that values such as :invalid or :floating might be used to represent states that result from missing a setup time requirement, or floating connections, or other unusual states. These values could be propagated through gates, representing indeterminate circuit behavior.) Busses can be parsed into separate wires using CIRCUIT-SIM:NTH-WIRE, or interpreted as integers, one bit from each wire.
Wires also have a list of "actions"; functions called when the state of the wire changes. These are the basic mechanism for circuit behavior to be represented.
Interesting circuit components such as CIRCUIT-SIM:INVERTER, CIRCUIT-SIM:MAKE-ROM, etc., act by placing "actions" on the input wires which calculate the effect (usually at a slightly later time) of the changed input, and place those resulting actions on the output wires.
CIRCUIT-SIM:PROBE and other assorted functions place actions on wires that result in printing information about events on the wire.
CIRCUIT-SIM:AT-TIME is a macro allowing for arbitrary code, usually representing external system inputs, to be executed at specific times in the simulation.
The simple example from SICP is that of a single-bit half-adder circuit.
It consists of two AND gates, an OR gate, and an inverter.
D = IN1 OR IN2
Carry = IN1 AND IN2
E = NOT Carry
Sum = D AND E
This is implemented in circuit-components.lisp
(defun half-adder (in1 in2 s c or-prop-delay and-prop-delay inv-prop-delay)
(let ((d (make-wire))
(e (make-wire)))
(or-gate in1 in2 d or-prop-delay)
(and-gate in1 in2 c and-prop-delay)
(inverter c e inv-prop-delay)
(and-gate d e s and-prop-delay)))
(in-package "CIRCUIT")
(defun sicp-example ()
(let ((inv-delay 2)
(and-delay 3)
(or-delay 5)
(in1 (make-wire))
(in2 (make-wire))
(sum (make-wire))
(carry (make-wire)))
(setf *agenda* (make-agenda 0))
(probe sum "sum")
(probe carry "carry")
(half-adder in1 in2 sum carry or-delay and-delay inv-delay)
(set-signal in1 1)
(propagate)
(set-signal in2 1)
(propagate)))
(sicp-example)
sum Time: 0 New Value: 0
carry Time: 0 New Value: 0 [the initial values]
carry Time: 3 New Value: NIL [in1 = 1 propagates through carry]
sum Time: 3 New Value: NIL [initial value of wire E has propagated]
sum Time: 8 New Value: T [in1 = 1 has propagated through OR and AND gates]
[ at this point, the first propagate has finished; in2 is set to 1]
carry Time: 11 New Value: T [in2 = 1 propagates through carry]
sum Time: 16 New Value: NIL [in2 = 1 has propagated through OR and AND gates.]
DONE
This demonstrates that the sum line has a propagation delay of 8 time units (OR+AND and AND+INV+AND are both 8), and the carry has a delay of 3.
The "Woz Machine" is the state-machine floppy-disk controller designed by Steve Wozniak for the Apple II microcomputer. It was a brilliant and classic design, much simpler and lower cost than the standard floppy controller. The introduction of low-cost floppy storage into the microcomputer market was possibly the most important event that made these machines practical tools for home and business, as opposed to toys for tinkerers and hobbyists.
The Disk II controller is actually quite subtle in several places. The reader is not expected to understand this fully from my description. Truly interested readers should find a copy of Jim Sather's Understanding the Apple IIe for a full treatment.
For reading, the sequencer assembles disk pulses into complete bytes, where a byte always starts with a most-significant-bit of 1. Because the disk reading process can begin at any point in a circular track, the disk data must be written with self-synchronizing patterns and distinct markers at appropriate places to allow the CPU to reliably locate data. Then, the CPU must read data without interruption until a complete sector has been read; if more than a dozen microseconds or so are missed, data will be lost, although in a properly formatted disk, the controller will maintain byte synchronization.
The sequencer similarly shifts out write data, one bit per 4 microsecond interval; MSB first. A `1' bit results in a write pulse, a `0' in no pulse. The CPU must provide data on 32-microsecond intervals or extra zeros will result. (These are deliberately introduced for writing self-synchronizing patterns.) One tricky point is that the write pulse is generated by the high-bit of the sequencer address, not by an opcode.
The basic control of the sequencer is through two bits controlled by the CPU (READ/WRITE, SHIFT/LOAD) the read pulse from the disk head (after being fed through a circuit synchronizing the transitions to the 2 MHz sequencer clock), and the high bit of the data register (QA).
The file woz-machine-hw-sim.lisp simulates the sequencer ROM, the data latch, the control latch, and some glue logic on the chip. It only partially implements the analog timer the Disk II controller uses to control the disk motor, and ignores the ROM containing bootstrap code, which is used only by the CPU.
The function LIST-P6-SEQUENCER walks the address lines on the P6 ROM and formats the output opcodes in a table
(asdf:oos 'asdf:load-op "woz-machine")
(woz-machine:list-p6-sequencer)
Data Dump of Woz Machine Floppy Disk Controller Sequence P6 ROM
Byte format: <next SEQ><opcode nibble>-<opcode symbol>
Opcodes:
NOP no-operation
CLR: clear data latch to zero
SL0: shift 0 bit left into data latch
SL1: shift 1 bit left into data latch
LD: load data latch from Apple II data bus
SR: shift state of write-protect bit right into data latch
READ PULSE=RP represents flux transition for 1 bit
SHIFT, LOAD, QA, READ/WRITE MODE are control bits
WRITE MODE
*-----------READ PULSE-------------*-----------NO READ PULSE----------*
*-----SHIFT------*------LOAD-------*------SHIFT------*------LOAD------*
SEQ *--QA'--*---QA---*--QA'---*---QA---*--QA'---*---QA---*--QA'---*---QA--*
0- 18-NOP 18-NOP 18-NOP 18-NOP 18-NOP 18-NOP 18-NOP 18-NOP
1- 28-NOP 28-NOP 28-NOP 28-NOP 28-NOP 28-NOP 28-NOP 28-NOP
2- 39-SL0 39-SL0 3B-LD 3B-LD 39-SL0 39-SL0 3B-LD 3B-LD
3- 48-NOP 48-NOP 48-NOP 48-NOP 48-NOP 48-NOP 48-NOP 48-NOP
4- 58-NOP 58-NOP 58-NOP 58-NOP 58-NOP 58-NOP 58-NOP 58-NOP
5- 68-NOP 68-NOP 68-NOP 68-NOP 68-NOP 68-NOP 68-NOP 68-NOP
6- 78-NOP 78-NOP 78-NOP 78-NOP 78-NOP 78-NOP 78-NOP 78-NOP
7- 08-NOP 88-NOP 08-NOP 88-NOP 08-NOP 88-NOP 08-NOP 88-NOP
8- 98-NOP 98-NOP 98-NOP 98-NOP 98-NOP 98-NOP 98-NOP 98-NOP
9- A8-NOP A8-NOP A8-NOP A8-NOP A8-NOP A8-NOP A8-NOP A8-NOP
A- B9-SL0 B9-SL0 BB-LD BB-LD B9-SL0 B9-SL0 BB-LD BB-LD
B- C8-NOP C8-NOP C8-NOP C8-NOP C8-NOP C8-NOP C8-NOP C8-NOP
C- D8-NOP D8-NOP D8-NOP D8-NOP D8-NOP D8-NOP D8-NOP D8-NOP
D- E8-NOP E8-NOP E8-NOP E8-NOP E8-NOP E8-NOP E8-NOP E8-NOP
E- F8-NOP F8-NOP F8-NOP F8-NOP F8-NOP F8-NOP F8-NOP F8-NOP
F- 88-NOP 08-NOP 88-NOP 08-NOP 88-NOP 08-NOP 88-NOP 08-NOP
READ MODE
*--------------SHIFT---------------*----------------LOAD--------------*
*------QA'-------*-------QA--------*-------QA'-------*-------QA-------*
SEQ *---RP--*-NO RP--*---RP---*-NO RP--*---RP---*-NO RP--*---RP---*-NO RP-*
0- 18-NOP 18-NOP 18-NOP 18-NOP 0A-SR 0A-SR 0A-SR 0A-SR
1- 2D-SL1 2D-SL1 38-NOP 38-NOP 0A-SR 0A-SR 0A-SR 0A-SR
2- D8-NOP 38-NOP 08-NOP 28-NOP 0A-SR 0A-SR 0A-SR 0A-SR
3- D8-NOP 48-NOP 48-NOP 48-NOP 0A-SR 0A-SR 0A-SR 0A-SR
4- D8-NOP 58-NOP D8-NOP 58-NOP 0A-SR 0A-SR 0A-SR 0A-SR
5- D8-NOP 68-NOP D8-NOP 68-NOP 0A-SR 0A-SR 0A-SR 0A-SR
6- D8-NOP 78-NOP D8-NOP 78-NOP 0A-SR 0A-SR 0A-SR 0A-SR
7- D8-NOP 88-NOP D8-NOP 88-NOP 0A-SR 0A-SR 0A-SR 0A-SR
8- D8-NOP 98-NOP D8-NOP 98-NOP 0A-SR 0A-SR 0A-SR 0A-SR
9- D8-NOP 29-SL0 D8-NOP A8-NOP 0A-SR 0A-SR 0A-SR 0A-SR
A- CD-SL1 BD-SL1 D8-NOP B8-NOP 0A-SR 0A-SR 0A-SR 0A-SR
B- D9-SL0 59-SL0 D8-NOP C8-NOP 0A-SR 0A-SR 0A-SR 0A-SR
C- D9-SL0 D9-SL0 D8-NOP A0-CLR 0A-SR 0A-SR 0A-SR 0A-SR
D- D8-NOP 08-NOP E8-NOP E8-NOP 0A-SR 0A-SR 0A-SR 0A-SR
E- FD-SL1 FD-SL1 F8-NOP F8-NOP 0A-SR 0A-SR 0A-SR 0A-SR
F- DD-SL1 4D-SL1 E0-CLR E0-CLR 0A-SR 0A-SR 0A-SR 0A-SR
CIRCUIT::DONE
The function WOZ-MACHINE:READ-DISK-BIT-STREAM demonstrates the action of the read sequencer on a series of read data pulses. (Which can be used, for instance, to demonstrate the effect of certain copy protection schemes which use unusually formatted bit streams to defeat ordinary read algorithms.)
The following example demonstrates the self-synchronizing sequence of eight 1's followed by two 0's, followed by the standard address header (hex) D5 AA 96. The times are in nsec, and represent the times when the CPU may be reading the data bus. In real code, of course, the CPU is reading the assembler code from memory; only one cycle in 7 can actually be read by the CPU in the usual read loop which polls for a 1 to appear in the MSB of the data. Many lines of output have been omitted. Note the beginning of the bit stream is only seven ones out of eight, representing the reader being out of sync by one bit.
(woz-machine:read-disk-bit-stream #b1111111001111111100111111110011111111001111111100110101011010101010010110)
;; truncated FF sync, 4 full FF sync, D5 AA, 966502 read Time: 0 New Value: 00000000 6502 read Time: 980 New Value: 00000001 6502 read Time: 1960 New Value: 00000001 6502 read Time: 2940 New Value: 00000001 6502 read Time: 3920 New Value: 00000001 6502 read Time: 4900 New Value: 00000010 6502 read Time: 5880 New Value: 00000010 6502 read Time: 6860 New Value: 00000010 6502 read Time: 7840 New Value: 00000010 6502 read Time: 8820 New Value: 00000101 6502 read Time: 9800 New Value: 00000101(Note the interesting start-up transient here.)
6502 read Time: 10780 New Value: 00000101 6502 read Time: 11760 New Value: 00000101 6502 read Time: 12740 New Value: 00001011 6502 read Time: 13720 New Value: 00001011 6502 read Time: 14700 New Value: 00001011 6502 read Time: 15680 New Value: 00001011 6502 read Time: 16660 New Value: 00010111
...finally, the first one bit gets to the MSB, and the sequencer tries to hold that byte for as long as possible, so the CPU will have a chance to read it. Unfortunately, being out of sync, this byte is garbage.
6502 read Time: 28420 New Value: 10111111 6502 read Time: 29400 New Value: 10111111 6502 read Time: 30380 New Value: 10111111 6502 read Time: 31360 New Value: 10111111 6502 read Time: 32340 New Value: 10111111 6502 read Time: 33320 New Value: 10111111 6502 read Time: 34300 New Value: 10111111 6502 read Time: 35280 New Value: 10111111 6502 read Time: 36260 New Value: 10111111 6502 read Time: 37240 New Value: 00000001
Now, the register is cleared, and shifts in the next byte.
6502 read Time: 38220 New Value: 00000010 ... 6502 read Time: 59780 New Value: 01001111 6502 read Time: 60760 New Value: 10011111 ... 6502 read Time: 91140 New Value: 01110011 6502 read Time: 92120 New Value: 11100111 ... 6502 read Time: 123480 New Value: 01111100 6502 read Time: 124460 New Value: 11111001 ... 6502 read Time: 155820 New Value: 01111111 6502 read Time: 156800 New Value: 11111110 ... 6502 read Time: 192080 New Value: 01111111 6502 read Time: 193060 New Value: 11111111
Finally, the machine is in sync.
6502 read Time: 194040 New Value: 11111111 ... 6502 read Time: 207760 New Value: 11111111 6502 read Time: 208740 New Value: 00000001 ... 6502 read Time: 231280 New Value: 01101010 6502 read Time: 232260 New Value: 11010101
Hex D5, which is held in the register for 9 cycles of the 6502.
... 6502 read Time: 240100 New Value: 11010101 6502 read Time: 241080 New Value: 00000001 ... 6502 read Time: 263620 New Value: 01010101 6502 read Time: 264600 New Value: 10101010
Hex AA
6502 read Time: 272440 New Value: 10101010 6502 read Time: 273420 New Value: 00000001 ... 6502 read Time: 295960 New Value: 01001011 6502 read Time: 296940 New Value: 10010110
Hex 96.