## n-bit Computers

2010-11-24 21:34

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
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
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)&reg},   //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
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)&reg},                    //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
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 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],
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}
);