Execute Computer/Zero: Difference between revisions
(→{{header|J}}: alternate approach) |
|||
| Line 190: | Line 190: | ||
pc=: 32|pc+1 |
pc=: 32|pc+1 |
||
select. cod |
select. cod |
||
case. 0 do. |
case. 0 do. NB. NOP |
||
case. 1 do. acc=: val{mem |
case. 1 do. acc=: val{mem NB. LDA |
||
case. 2 do. mem=: acc val} mem |
case. 2 do. mem=: acc val} mem NB. STA |
||
case. 3 do. acc=: 256|acc+val{mem |
case. 3 do. acc=: 256|acc+val{mem NB. ADD |
||
case. 4 do. acc=: 256|acc-val{mem |
case. 4 do. acc=: 256|acc-val{mem NB. SUB |
||
case. 5 do. pc=: 32|pc[^:(*acc) val |
case. 5 do. pc=: 32|pc[^:(*acc) val NB. BRZ |
||
case. 6 do. pc=: 32|val |
case. 6 do. pc=: 32|val NB. JMP |
||
case. 7 do. pc=: __ |
case. 7 do. pc=: __ NB. STP |
||
end. |
end. |
||
}} |
}} |
||
Revision as of 23:59, 27 June 2022
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Create a Computer/zero Assembly emulator. You may consider this webpage as a reference implementation. Output the results of the sample programs "2+2" and "7*8" found there.
- The virtual machine "bytecode" needs to be able to modify itself (or at least act as though it can) while the virtual machine is running, to be consistent with the reference implementation.
- For output, it is sufficient to have the implementation of the
STPopcode return the accumulator to your actual language, and then use your standard printing routines to output it.
- Bonus Points
- Run all 5 sample programs at the aforementioned website and output their results.
ALGOL 68
<lang algol68>BEGIN # execute some ComputerZero programs #
# instructions #
INT nop = 0, lda = 1, sta = 2, add = 3, sub = 4, brz = 5, jmp = 6, stp = 7;
PROC instr = ( INT op, v )INT: ( 32 * op ) + v;
OP NOP = ( INT v )INT: instr( nop, v );
OP LDA = ( INT v )INT: instr( lda, v );
OP STA = ( INT v )INT: instr( sta, v );
OP ADD = ( INT v )INT: instr( add, v );
OP SUB = ( INT v )INT: instr( sub, v );
OP BRZ = ( INT v )INT: instr( brz, v );
OP JMP = ( INT v )INT: instr( jmp, v );
OP STP = ( INT v )INT: instr( stp, v );
# executes the program named name #
PROC execute = ( STRING name, []INT program )VOID:
BEGIN
[ 0 : 31 ]INT m; # the computer 32 has bytes of memory #
FOR i FROM LWB m TO UPB m DO m[ i ] := 0 OD;
# "assemble" the program #
INT m pos := -1;
FOR i FROM LWB program TO UPB program DO
m[ m pos +:= 1 ] := program[ i ]
OD;
# execute the program #
BOOL running := TRUE;
INT pc := 0;
INT a := 0;
WHILE running DO
INT op := m[ pc ] OVER 32;
INT operand := m[ pc ] MOD 32;
pc +:= 1 MODAB 32;
IF op = nop THEN SKIP
ELIF op = lda THEN a := m[ operand ]
ELIF op = sta THEN m[ operand ] := a
ELIF op = add THEN a +:= m[ operand ] MODAB 256
ELIF op = sub THEN a -:= m[ operand ] MODAB 256
ELIF op = brz THEN IF a = 0 THEN pc := operand FI
ELIF op = jmp THEN pc := operand
ELSE # stp #
running := FALSE;
print( ( " " * ( 12 - ( ( UPB name - LWB name ) + 1 ) ) ) );
print( ( name, ": ", whole( a, -3 ), newline ) )
FI
OD
END # execute # ;
# task test programs (from the Computer Zero website) #
# the unary NOP, LDA, STA, etc. operators are used to construct the #
# instructions; as parameterless operators aren't allowed, NOP and STP #
# must have a dummy parameter #
execute( "2+2", ( LDA 3, ADD 4, STP 0, 2, 2 )
);
execute( "7*8"
, ( LDA 12, ADD 10, STA 12, LDA 11, SUB 13, STA 11, BRZ 8, JMP 0
, LDA 12, STP 0, 8, 7, 0, 1
)
);
execute( "fibonacci"
, ( LDA 14, STA 15, ADD 13, STA 14, LDA 15, STA 13, LDA 16, SUB 17
, BRZ 11, STA 16, JMP 0, LDA 14, STP 0, 1, 1, 0
, 8, 1
)
);
execute( "linkedList"
, ( LDA 13, ADD 15, STA 5, ADD 16, STA 7, NOP 0, STA 14, NOP 0
, BRZ 11, STA 15, JMP 0, LDA 14, STP 0, LDA 0, 0, 28
, 1, 0, 0, 0, 6, 0, 2, 26
, 5, 20, 3, 30, 1, 22, 4, 24
)
);
execute( "prisoner"
, ( NOP 0, NOP 0, STP 0, 0, LDA 3, SUB 29, BRZ 18, LDA 3
, STA 29, BRZ 14, LDA 1, ADD 31, STA 1, JMP 2, LDA 0, ADD 31
, STA 0, JMP 2, LDA 3, STA 29, LDA 1, ADD 30, ADD 3, STA 1
, LDA 0, ADD 30, ADD 3, STA 0, JMP 2, 0, 1, 3
)
);
# subtractions yielding negative results #
execute( "0-255", ( LDA 3, SUB 4, STP 0, 0, 255 ) );
execute( "0-1", ( LDA 3, SUB 4, STP 0, 0, 1 ) );
# overflow on addition #
execute( "1+255", ( LDA 3, ADD 4, STP 0, 1, 255 ) )
END </lang>
- Output:
2+2: 4
7*8: 56
fibonacci: 55
linkedList: 6
prisoner: 0
0-255: 1
0-1: 255
1+255: 0
J
The reference programs are not supplied in source code form, so in its current form this task is a bit unclear.
Here's one approach which might be sufficiently close to the task requirements:
<lang J>OPS=: 'nop lda sta add sub brz jmp stp'
assemble1=: {{
y=. tolower y
ins=. {.;:y-.":i.10
cod=. 8|(;:OPS) i. ins
val=. {.0".y-.OPS
if. *cod do.
assert. 32>val
val+32*cod
else.
assert. 256>val
val
end.
}}
assemble=: {{
if. 0=L. y do.
delim=. {.((tolower y)-.(":i.10),;OPS),LF
y=. delim cut y
end.
code=. assemble1@> y
mem=: code (i.#code)} 32#0
}}
exec1=: Template:'cod val'=. 0 32
exec=: {{
pc=: acc=: 0 while. 0<:pc do. exec1 end. acc
}}</lang>
With this implementation, we can assemble and run representations of the five suggested programs:
<lang J> exec assemble 'LDA 3; ADD 4; STP; 2; 2' 4
exec assemble 'LDA 12; ADD 10; STA 12; LDA 11; SUB 13; STA 11; BRZ 8; JMP; LDA 12; STP; 8; 7; 0; 1'
56
exec assemble 'LDA 14; STA 15; ADD 13; STA 14; LDA 15; STA 13; LDA 16; SUB 17; BRZ 11; STA 16; JMP; LDA 14; STP; 1; 1; 0; 8; 1'
55
exec assemble 'LDA 13; ADD 15; STA 5; ADD 16; STA 7; NOP; STA 14; NOP; BRZ 11; STA 15; JMP; LDA 14; STP; LDA; 0; 28; 1; 0; 0; 0; 6; 0; 2; 26; 5; 20; 3; 30; 1; 22; 4; 24'
6
exec assemble 'NOP; NOP; STP; NOP; LDA 3; SUB 29; BRZ 18; LDA 3; STA 29; BRZ 14; LDA 1; ADD 31; STA 1; JMP 2; LDA; ADD 31; STA; JMP 2; LDA 3; STA 29; LDA 1; ADD 30; ADD 3; STA 1; LDA; ADD 30; ADD 3; STA; JMP 2; 0; 1; 3'
0</lang>
Alternate approach
Another approach would be to eliminate the 'assemble' command and implement the opcodes as native J commands (which build a representation of the memory space). To conform with J syntax, the right arguments of these opcodes is required (so you need a 0 even for NOP and STP). The implementation of exec remains much the same as before, but it's convenient to have exec save the code to memory. In other words:
<lang J>opcode=: {{
(m+{.y),}.y
32{.x,m opcode y
}}
(Template:((x)=: y opcode)0&>32*i.@#);:'NOP LDA STA ADD SUB BRZ JMP STP'
exec1=: Template:'cod val'=. 0 32
exec=: {{
mem=: y pc=: acc=: 0 while. 0<:pc do. exec1 end. acc
}}</lang>
and:
<lang J> exec LDA 3 ADD 4 STP 0 2 2 4
exec LDA 12 ADD 10 STA 12 LDA 11 SUB 13 STA 11 BRZ 8 JMP 0 LDA 12 STP 0 8 7 0 1
56
exec LDA 14 STA 15 ADD 13 STA 14 LDA 15 STA 13 LDA 16 SUB 17 BRZ 11 STA 16 JMP 0 LDA 14 STP 0 1 1 0 8 1
55
exec LDA 13 ADD 15 STA 5 ADD 16 STA 7 NOP 0 STA 14 NOP 0 BRZ 11 STA 15 JMP 0 LDA 14 STP 0 LDA 0 0 28 1 0 0 0 6 0 2 26 5 20 3 30 1 22 4 24
6
exec NOP 0 NOP 0 STP 0 NOP 0 LDA 3 SUB 29 BRZ 18 LDA 3 STA 29 BRZ 14 LDA 1 ADD 31 STA 1 JMP 2 LDA 0 ADD 31 STA 0 JMP 2 LDA 3 STA 29 LDA 1 ADD 30 ADD 3 STA 1 LDA 0 ADD 30 ADD 3 STA 0 JMP 2 0 1 3
0</lang>
Julia
<lang ruby>mutable struct ComputerZero
ip::Int
ram::Vector{UInt8}
accum::UInt8
isready::Bool
end function ComputerZero(program)
memory = zeros(UInt8, 32)
for i in 1:min(32, length(program))
memory[i] = program[i]
end
return ComputerZero(1, memory, 0, true)
end
NOP(c) = (c.ip = mod1(c.ip + 1, 32)) LDA(c) = (c.accum = c.ram[c.ram[c.ip] & 0b00011111 + 1]; c.ip = mod1(c.ip + 1, 32)) STA(c) = (c.ram[c.ram[c.ip] & 0b00011111 + 1] = c.accum; c.ip = mod1(c.ip + 1, 32)) ADD(c) = (c.accum += c.ram[c.ram[c.ip] & 0b00011111 + 1]; c.ip = mod1(c.ip + 1, 32)) SUB(c) = (c.accum -= c.ram[c.ram[c.ip] & 0b00011111 + 1]; c.ip = mod1(c.ip + 1, 32)) BRZ(c) = (c.ip = (c.accum == 0) ? c.ram[c.ip] & 0b00011111 + 1 : mod1(c.ip + 1, 32)) JMP(c) = (c.ip = c.ram[c.ip] & 0b00011111 + 1) STP(c) = (println("Program completed with accumulator value $(c.accum).\n"); c.isready = false)
const step = [NOP, LDA, STA, ADD, SUB, BRZ, JMP, STP] const instructions = ["NOP", "LDA", "STA", "ADD", "SUB", "BRZ", "JMP", "STP"] const assemblywords = Dict(s => i - 1 for (i, s) in pairs(instructions))
function run(compzero::ComputerZero, debug = false)
while compzero.isready
instruction = compzero.ram[compzero.ip]
opcode, operand = instruction >> 5 + 1, instruction & 0b00011111
debug && println("op $(instructions[opcode]), operand $operand")
step[opcode](compzero)
end
return compzero.accum
end run(program::Vector, debug = false) = run(ComputerZero(program), debug)
function compile(text::String)
bin, lines = UInt8[], 0
for line in strip.(split(text, "\n"))
lines += 1
if isempty(line)
push!(bin, 0)
elseif (m = match(r"(\w\w\w)\s+(\d\d?)", line)) != nothing
push!(bin, UInt8((assemblywords[m.captures[1]] << 5) | parse(UInt8, m.captures[2])))
elseif (m = match(r"(\w\w\w)", line)) != nothing
push!(bin, UInt8(assemblywords[m.match] << 5))
elseif (m = match(r"\d\d?", line)) != nothing
push!(bin, parse(UInt8, m.match))
else
error("Compilation error at line $lines: error parsing <$line>")
end
end
println("Compiled $lines lines.")
return bin
end
const testprograms = [
"""
LDA 3
ADD 4
STP
2
2
""",
"""
LDA 12
ADD 10
STA 12
LDA 11
SUB 13
STA 11
BRZ 8
JMP 0
LDA 12
STP
8
7
0
1
""",
"""
LDA 14
STA 15
ADD 13
STA 14
LDA 15
STA 13
LDA 16
SUB 17
BRZ 11
STA 16
JMP 0
LDA 14
STP
1
1
0
8
1
""",
"""
LDA 13
ADD 15
STA 5
ADD 16
STA 7
NOP
STA 14
NOP
BRZ 11
STA 15
JMP 0
LDA 14
STP
LDA 0
0
28
1
6
0
2
26
5
20
3
30
1
22
4
24
""",
"""
0
0
STP
NOP
LDA 3
SUB 29
BRZ 18
LDA 3
STA 29
BRZ 14
LDA 1
ADD 31
STA 1
JMP 2
LDA 0
ADD 31
STA 0
JMP 2
LDA 3
STA 29
LDA 0
ADD 30
ADD 3
STA 0
LDA 1
ADD 30
ADD 3
STA 1
JMP 2
0
1
3
"""
]
for t in testprograms
run(compile(t))
end
</lang>
- Output:
Compiled 6 lines. Program completed with accumulator value 4. Compiled 15 lines. Program completed with accumulator value 56. Compiled 19 lines. Program completed with accumulator value 55. Compiled 33 lines. Program completed with accumulator value 6. Compiled 33 lines. Program completed with accumulator value 0.
Phix
Assumes there is no need for an "assembler", just a runtime interpreter. Output matches Algol 68.
with javascript_semantics constant NOP = 0b000_00000, -- no operation LDA = 0b001_00000, -- load accumulator, a := memory [xxxxx] STA = 0b010_00000, -- store accumulator, memory [xxxxx] := a ADD = 0b011_00000, -- add, a := a + memory [xxxxx] SUB = 0b100_00000, -- subtract, a := a – memory [xxxxx] BRZ = 0b101_00000, -- branch on zero, if a = 0 then goto xxxxx JMP = 0b110_00000, -- jump, goto xxxxx STP = 0b111_00000, -- stop OP = 0b111_00000, -- operator mask ARG = 0b000_11111 -- memory location (0 based) procedure execute(string name, sequence program) sequence memory = deep_copy(program) integer pc = 1, a = 0 while true do integer ppc = memory[pc], op = and_bitsu(ppc,OP), arg = and_bits(ppc,ARG)+1 pc += 1 switch op do case NOP: break case LDA: a = memory[arg] case STA: memory[arg] = a case ADD: a = and_bitsu(a+memory[arg],#FF) case SUB: a = and_bitsu(a-memory[arg],#FF) case BRZ: if a=0 then pc = arg end if case JMP: pc = arg case STP: printf(1,"%12s: %3d\n",{name,a}) return end switch end while end procedure execute("2+2",{LDA+3, ADD+4, STP, 2,2}) execute("7*8",{LDA+12, ADD+10, STA+12, LDA+11, SUB+13, STA+11, BRZ+8, JMP+0, LDA+12, STP, 8,7,0,1}) execute("fibonacci",{LDA+14, STA+15, ADD+13, STA+14, LDA+15, STA+13, LDA+16, SUB+17, BRZ+11, STA+16, JMP+0, LDA+14, STP, 1,1,0,8,1}) execute("linkedList",{LDA+13, ADD+15, STA+5, ADD+16, STA+7, NOP, STA+14, NOP, BRZ+11, STA+15, JMP+0, LDA+14, STP, LDA+0, 0,28,1,0,0, 0,6,0,2,26,5,20,3,30,1,22,4,24}) execute("prisoner",{NOP, NOP, STP, 0, LDA+3, SUB+29, BRZ+18, LDA+3, STA+29, BRZ+14, LDA+1, ADD+31, STA+1, JMP+2, LDA+0, ADD+31, STA+0, JMP+2, LDA+3, STA+29, LDA+1, ADD+30, ADD+3, STA+1, LDA+0, ADD+30, ADD+3, STA+0, JMP+2, 0, 1, 3}) -- subtractions yielding negative results execute("0-255",{LDA+3,SUB+4,STP, 0,255}) execute("0-1",{LDA+3, SUB+4, STP, 0,1}) -- overflow on addition execute("1+255",{LDA+3, ADD+4, STP, 1, 255})
You could of course define the programs using (say) 0b001_00011 instead of LDA+3.
- Output:
2+2: 4
7*8: 56
fibonacci: 55
linkedList: 6
prisoner: 0
0-255: 1
0-1: 255
1+255: 0
Wren
As I'm unclear whether the interpreter should be able to deal with labels, the programs all use literal memory addresses for now. Output is in decimal.
Although I've entered the fifth program, it just returns 0 when reaching the STP instruction. I'm unclear how we can make it interactive without having another instruction though possibly, if STP had address bits other than 0, this could signal that user input was required. <lang ecmascript>var NOP = 0 var LDA = 1 var STA = 2 var ADD = 3 var SUB = 4 var BRZ = 5 var JMP = 6 var STP = 7
var ops = {"NOP": NOP, "LDA": LDA, "STA": STA, "ADD": ADD,
"SUB": SUB, "BRZ": BRZ, "JMP": JMP, "STP": STP}
var load = Fn.new { |prog|
var mem = List.filled(32, 0)
var lines = prog.trimEnd().split("\n")
for (i in 0...lines.count) {
var line = lines[i].trim()
var split = line.split(" ")
var instr = split[0]
var addr = 0
if (split.count == 2) addr = Num.fromString(split[1])
if (ops[instr]) {
mem[i] = ops[instr] * 32 + addr
} else {
var v = Num.fromString(instr)
if (v) mem[i] = v
}
}
return mem
}
var output = Fn.new { |acc|
System.print(acc)
}
var interp = Fn.new { |prog|
var acc = 0
var pc = 0
var mem = load.call(prog)
while (true) {
var instr = mem[pc] >> 5
var addr = mem[pc] % 32
pc = pc + 1
if (instr == LDA) {
acc = mem[addr]
} else if (instr == STA) {
mem[addr] = acc
} else if (instr == ADD) {
acc = acc + mem[addr]
if (acc > 255) acc = acc - 256
} else if (instr == SUB) {
acc = acc - mem[addr]
if (acc < 0) acc = acc + 256
} else if (instr == BRZ) {
if (acc == 0) pc = addr
} else if (instr == JMP) {
pc = addr
}
if (instr == STP || pc > 31) break
}
output.call(acc)
}
var progs = [
"""
LDA 3
ADD 4
STP
2
2
""",
"""
LDA 12
ADD 10
STA 12
LDA 11
SUB 13
STA 11
BRZ 8
JMP 0
LDA 12
STP
8
7
0
1
""",
"""
LDA 14
STA 15
ADD 13
STA 14
LDA 15
STA 13
LDA 16
SUB 17
BRZ 11
STA 16
JMP 0
LDA 14
STP
1
1
0
8
1
""",
"""
LDA 13
ADD 15
STA 5
ADD 16
STA 7
NOP
STA 14
NOP
BRZ 11
STA 15
JMP 0
LDA 14
STP
LDA 0
0
28
1
6
0
2
26
5
20
3
30
1
22
4
24
""",
"""
0
0
STP
NOP
LDA 3
SUB 29
BRZ 18
LDA 3
STA 29
BRZ 14
LDA 1
ADD 31
STA 1
JMP 2
LDA 0
ADD 31
STA 0
JMP 2
LDA 3
STA 29
LDA 0
ADD 30
ADD 3
STA 0
LDA 1
ADD 30
ADD 3
STA 1
JMP 2
0
1
3
"""
] for (prog in progs) interp.call(prog)</lang>
- Output:
4 56 55 6 0
Z80 Assembly
Output is in hexadecimal but is otherwise correct. <lang z80>org &1000 PrintChar equ &BB5A
- reg usage
- DE = VM'S Program Counter
- IXL = VM's Accumulator
main: ld ixl,0 ld de,Computer_Zero_RAM_2_plus_2 call Computer_Zero_VM ld a,ixl call ShowHex ;output to Amstrad CPC's screen call NewLine
ld ixl,0 ld de,Computer_Zero_RAM_7x8 call Computer_Zero_VM ld a,ixl jp ShowHex ;output and return to basic.
- these two functions are related to displaying the output
- and have nothing to do with the virtual machine itself.
ShowHex: push af and %11110000 rrca rrca rrca rrca call PrintHexChar pop af and %00001111 ;call PrintHexChar ;execution flows into it naturally. PrintHexChar: ;converts hex to ascii or a ;Clear Carry Flag daa add a,&F0 adc a,&40 jp PrintChar
NewLine: push af ld a,13 call PrintChar ld a,10 call PrintChar pop af ret
Computer_Zero_VM: ld a,(de) ;opcode fetch call UnpackOpcode ;stores opcode in B, operand in C push de ld de,Opcode_Table ld a,b rlca ;index times 2 for word data
ld e,a ld a,(de) ld L,a inc de ld a,(de) ld h,a ;LD HL,(DE)
pop de jp (hl)
- register state after this jump
- DE = program counter
- HL = address of instruction implementation
- C = operand of the instruction we're about to execute
- IXL = accumulator
overhead: ld a,e inc a and %00011111 ;ensures we stay within the 32 byte address space. ld e,a jp Computer_Zero_VM
UnpackOpcode:
push af
and %11100000
rlca
rlca
rlca
ld b,a ;opcode in B
pop af
and %00011111
ld c,a ;operand in C
dummy:
ret
align 256 ;ensures the following table is page-aligned
- this lets us index it much faster.
Opcode_Table: dw vmNOP dw vmLDA dw vmSTA dw vmADD dw vmSUB dw vmBRZ dw vmJMP dw vmSTP
vmNOP: jp overhead ;do nothing vmLDA: push de ld e,c ;offset DE by the operand ld a,(de) ;load from that address ld ixl,a ;and store it in the accumulator pop de jp overhead vmSTA: push de ld e,c ;offset DE by the operand ld a,ixl ;get the accumulator ld (de),a ;store it into (DE) pop de jp overhead vmADD: push de ld e,c ;offset DE by the operand ld a,(de) ;load from that address add ixl ;and add that value to the accumulator ld ixl,a ;then set the new accumulator pop de jp overhead vmSUB: push de ld e,c ;offset DE by the operand ld a,(de) ld b,a ld a,ixl sub b ld ixl,a pop de noBRZ: jp overhead vmBRZ: ld a,ixl or a jr nz, noBRZ vmJMP: ld e,c jp Computer_Zero_VM vmSTP: ret ;return to main
align 256 Computer_Zero_RAM_2_plus_2: db %00100011,%01100100 db %11100000,%00000010 db %00000010,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 align 256 Computer_Zero_RAM_7x8: db %00101100,%01101010 db %01001100,%00101011 db %10001101,%01001011 db %10101000,%11000000 db %00101100,%11100000 db %00001000,%00000111 db %00000000,%00000001 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000 db %00000000,%00000000</lang>
- Output:
04 38