n-bit Computers
clean-up #10:
Some 3 years ago I was really into writing code in SuperCollider to emulate/study/sonify various computer systems. Here's a short write-up...
A 1-bit computer can only have two states. In the following code, such a simple computer is emulated. The two possible opcodes 0 and 1 are set to take some basic actions: 0 will stop the program and 1 will post 'hello'.
There are only a total of four programs possible for this computer. With the line ~mem= [0, 0] we can load the first program [0, 0] into memory. That program means halt, halt and when we run it it will make the emulated computer stop right away. The second program [0, 1] will also stop instantaneously, but program three [1, 0] will post once and then halt. Program four [1, 1] in turn will post forever and never halt.
//--all 1bit computer programs
~mem= [0, 0]; //program: halt halt - quits right away
~mem= [0, 1]; //program: halt post - also quits right away
~mem= [1, 0]; //program: post halt - posts hello and then quits
~mem= [1, 1]; //program: post post - posts hello forever
(
//--1bit computer. load a program into memory before run
var pc= 0; //program counter
var reg= 0; //register (unused)
Routine.run{
var op, running= true;
while({running}, {
op= ~mem[pc];
switch(op,
0, {running= false}, //halt
1, {"hello".postln} //post
);
pc= pc+1%~mem.size;
[\pc, pc, \reg, reg, \mem, ~mem].postln;
0.2.wait;
});
("finished with mem="+~mem).postln;
};
""
)
If we take the same simple principle and implement a 2-bit computer, there are four possible opcodes and 256 different programs we can run (if we just fill the memory with unique combinations and call them programs - not many of these will make sense of course). The actions that the emulator below can take are simple (other actions are of course possible - here just a few standard ones)... halt - stops execution, load will take the next byte in the program and put it into the register, incr will increase the register by one and stor writes the content of the register back into the memory position (address) that is found in the next byte.
Most programs will be pointless (at least for the actions implemented here), so I only list five out of 256 programs. The first program [2r10, 2r10, 2r10, 2r00] will increment the register three times and then stop. Program two increments the register, stores that at address 0 and stops. Program three will first load 2r10 into the register, then increment the register twice and stop. The fourth program first loads 2r10 into the register, then increment the register, then stores the register at address 0 and last stops.
So far all the programs have been dull and pointless. But not program five! Here we start to see the potential as it modifies itself as it runs. Program five starts by incrementing the register, then it stores the register at address 3, then again it stores the register but at the address 1! (Note: here the trick is first noticed - although the original program said "store at address 0", at the beginning of the program we overwrote that with address 1), then it loads 2r10 (note: here it wraps around and finds the value at address 0) into the register, then increment the register, then load 2r11 into the register, then store the register at address 1, then load 2r10 into the register, then increase the register, then store the register intro address 3, etc etc. until it finally halts after 16 cycles. Because of the self-modifying program code, the execution is long and complex to follow. Very interesting I find.
//--selected 2bit computer programs
~mem= [2r10, 2r10, 2r10, 2r00]; //program: incr incr incr halt
~mem= [2r10, 2r11, 2r00, 2r00]; //program: incr stor halt halt
~mem= [2r01, 2r10, 2r10, 2r00]; //program: load incr incr halt
~mem= [2r01, 2r10, 2r11, 2r00]; //program: load incr stor halt
~mem= [2r10, 2r11, 2r11, 2r00]; //program: incr stor stor halt
(
//--2bit computer. load a program into memory before run
var pc= 0; //program counter
var reg= 0; //register
var format= {|x| x.collect{|x| x.asBinaryString(2)}};
var rd= {|x| ~mem@@x};
var wr= {|x, y| ~mem.put(x%~mem.size, y)};
Routine.run{
var op, running= true;
while({running}, {
op= ~mem[pc];
switch(op,
2r00, {running= false}, //halt
2r01, {reg= rd.(pc+1)}, //load next addy into reg
2r10, {reg= reg+1%4}, //incr reg
2r11, {wr.(rd.(pc+1), reg)} //stor at addy in next byte
);
pc= pc+1%~mem.size;
[\pc, pc, \reg, reg, \mem, format.value(~mem)].postln;
0.2.wait;
});
("finished with mem="+format.value(~mem)).postln;
};
""
)
One variation of the emulator code above (and also for the following 3-4bit computers) would be to let the load and stor instructions also increase the program counter (pc) by 1. So it takes the following byte as an argument and then skips over that for the next cycle. This would be a more common way to implement instructions like load and stor (I do it in the last example - the 8bit computer).
So if a 2-bit computer can start to mutate its code as it runs, imagine what a 3-bit computer is capable of. 16777216 different programs (8.pow(8)) are possible, 8 opcodes and actions and 8 bytes of memory. The actions implemented in the 3-bit emulator below includes and/or operations as well as a jump instruction. All the example programs are pretty lame. E.g. program four makes an endless loop jumping back and forth. One could write a lot more interesting programs.
//--selected 3bit computer programs
~mem= [2r010, 2r011, 2r111, 2r000, 2r010, 2r011, 2r111, 2r000]; //program: incr stor post halt incr stor post halt
~mem= [2r101, 2r111, 2r110, 2r111, 2r011, 2r000, 2r000, 2r000]; //program: and post or post stor halt halt halt
~mem= [2r100, 2r101, 2r000, 2r000, 2r000, 2r111, 2r000, 2r000]; //program: jump and halt halt halt post halt halt
~mem= [2r100, 2r101, 2r000, 2r000, 2r000, 2r100, 2r000, 2r000]; //program: jump and halt halt halt jump halt halt
(
//--3bit computer. load a program into memory before run
var pc= 0; //program counter
var reg= 0; //register
var format= {|x| x.collect{|x| x.asBinaryString(3)}};
var rd= {|x| ~mem@@x};
var wr= {|x, y| ~mem.put(x%~mem.size, y)};
Routine.run{
var op, running= true;
while({running}, {
op= ~mem[pc];
switch(op,
2r000, {running= false}, //halt
2r001, {reg= rd.(pc+1)}, //load next addy into reg
2r010, {reg= reg+1%8}, //incr reg
2r011, {wr.(rd.(pc+1), reg)}, //stor at addy in next byte
2r100, {pc= rd.(pc+1)-1}, //jump to addy in reg
2r101, {reg= rd.(pc+1)®}, //and reg with next addy
2r110, {reg= rd.(pc+1)|reg}, //or reg with next addy
2r111, {reg.postln} //post reg
);
pc= pc+1%~mem.size;
[\pc, pc, \reg, reg, \mem, format.value(~mem)].postln;
0.2.wait;
});
("finished with mem="+format.value(~mem)).postln;
};
""
)
With a 4-bit computer it starts to get difficult to come up with relevant actions to take for all the 16 opcodes. In the emulator below there is a stack with push and pull opcodes, more math with addition, subtraction and left/right shifts as well as inversion of bits. There is also a random instruction. Again the example programs are really dull - it is possible to write much more interesting programs or why not generate programs at random and see which ones make interesting results? Like this... ~mem= {16.rand}.dup(16);
//--selected 4bit computer programs
~mem= [2r0010, 2r0010, 2r0011, 2r1111, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000];
~mem= [2r0001, 2r1110, 2r0010, 2r1111, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000, 2r0000];
(
//--4bit computer. load a program into memory before run
var pc= 0; //program counter
var sp= 15; //stack pointer
var reg= 0; //register
var format= {|x| x.collect{|x| x.asBinaryString(4)}};
var rd= {|x| ~mem@@x};
var wr= {|x, y| ~mem.put(x%~mem.size, y)};
Routine.run{
var op, running= true;
while({running}, {
op= ~mem[pc];
switch(op,
2r0000, {running= false}, //halt
2r0001, {reg= rd.(pc+1)}, //load next addy into reg
2r0010, {reg= reg+1%16}, //incr reg
2r0011, {wr.(rd.(pc+1), reg)}, //stor at addy in next byte
2r0100, {pc= rd.(pc+1)-1}, //jump to addy in reg
2r0101, {reg= rd.(pc+1)®}, //and reg with next addy
2r0110, {reg= rd.(pc+1)|reg}, //or reg with next addy
2r0111, {reg.postln}, //post reg
2r1000, {wr.(rd.(pc+1), rd.(pc+1).bitXor)},//inv at addy in next byte
2r1001, {wr.(rd.(pc+1), 16.rand)},//rand at addy in next byte
2r1010, {reg= reg.leftShift(1)}, //lsr reg
2r1011, {reg= reg.rightShift(1)}, //rsr reg
2r1100, {reg= reg+rd.(pc+1)%16}, //add reg val at addy in next byte
2r1101, {reg= reg-rd.(pc+1)%16}, //sub reg val at addy in next byte
2r1110, {wr.(sp, reg); sp= sp-1}, //push reg to stack
2r1111, {reg= rd.(sp+1%16); sp= (sp+1).min(15)}//pull to reg from stack
);
pc= pc+1%~mem.size;
[\pc, pc, \reg, reg, \sp, sp, \mem, format.value(~mem)].postln;
0.2.wait;
});
("finished with mem="+format.value(~mem)).postln;
};
""
)
Things are getting really tricky when implementing an 8-bit computer from scratch. In the example below I only implemented 19 out of the 256 possible opcodes. For the actions/instructions set I took inspiration from the 6502 microprocessor. If you know some assembly you should recognise what the opcodes do. The stack pointer is commented out because none of the 19 active opcodes uses it.
~mem= 0.dup(256); "" //clear memory
//--selected 8bit computer programs
//ADC, #0x0F, AND, #0x0A, ORA, #0x0F, EOR, #0x10, BRK
[0x69, 0x0F, 0x29, 0x0A, 0x09, 0x0F, 0x49, 0x0A, 0x00].do{|x, i| ~mem.put(i, x)};
//LDA, #0xFF, STA, #0x20, BRK
[0xA9, 0xFF, 0x85, 0x20, 0x00].do{|x, i| ~mem.put(i, x)};
//INC, 0x20, NOP, DEC, 0x21, BRK
[0xE6, 0x20, 0xEA, 0xC6, 0x21, 0x00].do{|x, i| ~mem.put(i, x)};
//CLC, BCS, #0x07, SEC, BCS, #0x07, BRK, NOP
[0x18, 0xB0, 0x07, 0x38, 0xB0, 0x07, 0x00, 0xEA].do{|x, i| ~mem.put(i, x)};
(
//--8bit computer. load a program into memory before run
//implemented some of the 6502 opcodes and some of its flags
var pc= 0x00; //program counter
//var sp= 0xFF; //stack pointer
var r= 0x00; //register
var c= 0x00; //carry
var format= {|x| x.collect{|x| x.asHexString(2)}};
var rd= {|x| ~mem@@x};
var wr= {|x, y| ~mem.put(x%~mem.size, y)};
Routine.run{
var op, running= true;
while({running}, {
op= ~mem[pc];
switch(op,
0x65, {r= r+rd.(rd.(pc+1))+c%0x100; pc= pc+1}, //ADC aa
0x69, {r= r+rd.(pc+1)+c%0x100; pc= pc+1}, //ADC #aa
0x29, {r= r&rd.(pc+1); pc= pc+1}, //AND #aa
0x25, {r= r&rd.(rd.(pc+1)); pc= pc+1}, //AND aa
0x90, {if(c==0, {pc= rd.(pc+1)-1}, {pc= pc+1})}, //BCC aa
0xB0, {if(c==1, {pc= rd.(pc+1)-1}, {pc= pc+1})}, //BCS aa
0x00, {running= false}, //BRK
0x18, {c= 0}, //CLC
0xC6, {wr.(rd.(pc+1), rd.(rd.(pc+1))-1%0x100); pc= pc+1},//DEC aa
0x49, {r= r.bitXor(rd.(pc+1)); pc= pc+1}, //EOR #aa
0x45, {r= r.bitXor(rd.(rd.(pc+1))); pc= pc+1}, //EOR aa
0xE6, {wr.(rd.(pc+1), rd.(rd.(pc+1))+1%0x100); pc= pc+1},//INC aa
0xA9, {r= rd.(pc+1); pc= pc+1}, //LDA #aa
0xA5, {r= rd.(rd.(pc+1)); pc= pc+1}, //LDA aa
0xEA, {'nop'.postln}, //NOP
0x09, {r= r|rd.(pc+1); pc= pc+1}, //ORA #aa
0x05, {r= r|rd.(rd.(pc+1)); pc= pc+1}, //ORA aa
0x38, {c= 1}, //SEC
0x85, {wr.(rd.(pc+1), r); pc= pc+1}, //STA aa
{("opcode not implemented"+op).warn}
);
pc= pc+1%~mem.size;
[\pc, pc.asHexString(2), \r, r.asHexString(2), \c, c, \op, op.asHexString(2)].postln;
0.2.wait;
});
("finished with mem="+format.value(~mem)).postln;
};
""
)
And here's a disassembler for the emulator above. It will just dump the whole memory (256 bytes) and post which opcode is stored at what address.
(
//--8bit computer disassembler
var res= [], adr= [0];
var putImmediate= {|op, val| res= res++[op+"#"++val.asHexString(2)]};
var putAbsolute= {|op, val| res= res++[op+"$"++val.asHexString(2)]};
var putOpcode= {|op| res= res++[op]};
var i= 0;
while({i<~mem.size}, {
switch(~mem[i],
0x65, {putAbsolute.("ADC", ~mem[i+1]); i= i+2},
0x69, {putImmediate.("ADC", ~mem[i+1]); i= i+2},
0x29, {putImmediate.("AND", ~mem[i+1]); i= i+2},
0x25, {putAbsolute.("AND", ~mem[i+1]); i= i+2},
0x90, {putAbsolute.("BCC", ~mem[i+1]); i= i+2},
0xB0, {putAbsolute.("BCS", ~mem[i+1]); i= i+2},
0x00, {putOpcode.("BRK"); i= i+1},
0x18, {putOpcode.("CLC"); i= i+1},
0xC6, {putAbsolute.("DEC", ~mem[i+1]); i= i+2},
0x49, {putImmediate.("EOR", ~mem[i+1]); i= i+2},
0x45, {putAbsolute.("EOR", ~mem[i+1]); i= i+2},
0xE6, {putAbsolute.("INC", ~mem[i+1]); i= i+2},
0xA9, {putImmediate.("LDA", ~mem[i+1]); i= i+2},
0xA5, {putAbsolute.("LDA", ~mem[i+1]); i= i+2},
0xEA, {putOpcode.("NOP"); i= i+1},
0x09, {putImmediate.("ORA", ~mem[i+1]); i= i+2},
0x05, {putAbsolute.("ORA", ~mem[i+1]); i= i+2},
0x38, {putOpcode.("SEC"); i= i+1},
0x85, {putAbsolute.("STA", ~mem[i+1]); i= i+2},
{("opcode not implemented"+~mem[i]).warn; i= i+1}
);
adr= adr.add(i);
});
"adr: op:\n-----------------".postln;
res.do{|x, i| (" $"++adr[i].asHexString(2)+x).postln};
""
)
I did write a full 6502 emulation that is in a working state. It is written as a class and takes up about 2000 lines of SuperCollider code. I will clean it up and publish it another day. I also did the CPU65C02 version that sits in the AppleIIc computer and the 6510 that is in the Commodore64.
