Welcome to PureDarwin’s documentation!¶
Contents:
Introduction¶
puredarwin is a pure Hardware Implementation of CoreWar.
CoreWar ?¶
( corewar.co.uk | corewar.info | corewars.org )
In Corewar, programs are fighting each other in the same memory space, the goal is to kill the other programs by making them execute illegal instructions.
Programs are written in assembly, RedCode is the name of the assembly used.
pure Hardware Implementation ?¶
Our world is made of two kind of people, the one that write software, and the one that design hardware. In the past, the former were slaved by the later, this is less and less true. Anyway, I made my study in the hardware field, and I’m now spending my day at $paying_job writing software.
Our goal here is to achieve a silicon running CoreWar game engine.
Actually, when I speak about an implementation of CoreWar, I am truly speaking about an implementation of MARS (Memory Array Redcode Simulator) ... even if my implementation is everything but a simulator !
This implementation is split into Modules.
The code is written in an unexpected language when in comes to Hardware Design, I choose Python to help me with that task. Bare Python is of course not able to describe Hardware Modules, that’s where MyHDL comes into the scene. MyHDL advertise itself as being able to output VHDL as well as Verilog, I’m curious of the result. Anyway, I don’t own any FPGA, ASIC or even Lattice right now, so gtkwave will be my best guess when it comes to simulation for some time.
Darwin¶
From Wikipedia:
Darwin was a programming game invented in August 1961 by Victor A. Vyssotsky, Robert Morris Sr., and M. Douglas McIlroy. The game was developed at Bell Labs, and played on an IBM 7090 mainframe there. The game was only played for a few weeks before Morris developed an “ultimate” program that eventually brought the game to an end, as no-one managed to produce anything that could defeat it.
RedCode¶
RedCode is the assembly language used to program the MARS Virtual Machine.
We will regard here only the the details we need to look at as hardware designer. The rest is left to the dozen of good tutorials you will find on the Internet. If you don’t know where to start, Google might be your friend that time. That said, don’t expect any easy talk in there.
They are different version of the standard defining the RedCode language, ranging from ‘86, ‘88 and extended (‘94 has never been confirmed as a standard). We will try to implement most of the extended feature, while keeping compatibility with the previous standards.
Instruction Set¶
Address Mode¶
First thing to kno. Is that memory access inside the MARS are relative to the current instruction pointer (noted IP here below). As seen from a program, all addresses are relative to the one of the currently executed instruction.
To keep a low memory footprint, RedCode has 5 address mode:
Name | Relative operation | Absolute operation | A-Notation | B-Notation |
---|---|---|---|---|
Immediate Memory Addressing | 0 | IP | # |
# |
Direct Memory Addressing | x | IP + x | $ |
$ |
Indirect Memory Adressing | [IP + x] | IP + x + [IP + x] | * |
@ |
Post Increment Indirect Memory Addressing | [IP + x]++ | IP + x + [IP + x]++ | { |
< |
Pre Decrement Indirect Memory Addressing | –[IP + x] | IP + x + –[IP + x/] | } |
> |
The last three one actually count double as we can address the first operand or the second operand on those addresses in Memory.
Out of those one, the last two one are pretty unusual, even for an experienced assembly programmer, just because of the fact that those Memory addressing modes modify the memory content instead of just pointing to it.
RedCode Instruction Set¶
One feature of a processor running RedCode is that it has to implement
some OS functionnalities at the silicon level. I’m mainly speacking
here of the SPL
instruction, and derivated ones. That
instruction queue a new task in the task queue. For an unix
developer, it is a fork(2) at the silicon level.
The typical example is:
SPL 0 ; execution starts here
MOV 0, 1
Since the SPL
points to itself, after one cycle the processes will
be like this:
SPL 0 ; second process is here
MOV 0, 1 ; first process is here
After both of the processes have executed, the core will now look like:
SPL 0 ; third process is here
MOV 0, 1 ; second process is here
MOV 0, 1 ; first process is here
So this code evidently launches a series of imps, one after
another. It will keep on doing this until the imps have circled the
whole core and overwrite the SPL
.
IMP¶
;redcode
;name Imp
;author A. K. Dewdney
;assert 1
MOV 0, 1
Dwarf¶
;redcode
;name Dwarf
;author A. K. Dewdney
;assert CORESIZE % 5 == 0
DAT -1
ADD #5, -1 ; start address
MOV #0, @-2
JMP -2
Another version put the Bomb after itself
;redcode
ADD #4, 3
MOV #2, @2
JMP -2
Here is the result of a simulation on my MARS:
Gemini¶
Code¶
;redcode
;name Gemini
;author A. K. Dewdney
;assert 1
DAT 0
DAT 99
MOV @-2, @-1 ; start address
SNE -3, #9
JMP 4
ADD #1, -5
ADD #1, -5
JMP -5
MOV #99, 93
JMP 93
Simulation¶
Modules¶
We have to split the design into modules
- The The Core alias the Memory
- The Task-Queue alias the Scheduler unit
- The The Proc alias the Processing unit
- The pSpace or the Process private Storage space
The Core¶
The Core is the main Memory were the programs fight themselves. (As opposed to each-others, as nothing prevent you to hurt yourself.)
As we can see, the Core is split into RAM modules that each of them store a logical part of the Instructions. there are exactly 6 of them. One for each part:
- OpCode
- Modifier
- AMode
- ANumber
- BMode
- BNumber
Ports¶
Sub-processes¶
The Core has one main combinatorial subprocess that just split the incoming Instruction in chuncks for the RAM modules, and join back the chunks from the RAM modules into one Instruction for the others Modules.
internal Signals¶
Internal signals are only intercommunication signals between the sub-modules.
The RAM¶
Fold¶
Sub-processes¶
This module is composed of three sub-modules:
- Modulo is used to calculate a temporary value
- Folding to Fold the Address into its Read (or Write) boundary.
- Addition to make the Address Absolute. (This step also includes a Modulo)
For the two first steps, the Cref provides the following listing:
/* There is one support function used to limit the range of */
/* reading from Core and writing to Core relative to the */
/* current instruction. Behaviour is as expected (a small */
/* core within Core) only if the limits are factors of the */
/* size of Core. */
static Address Fold(
Address pointer, /* The pointer to fold into the desired range. */
Address limit, /* The range limit. */
Address M /* The size of Core. */
) {
Address result;
result = pointer % limit;
if ( result > (limit/2) ) {
result += M - limit;
};
return(result);
}
Internal Signals¶
We have two internal signals to interconnect our three sub-process. Each one of them representing our output at its different stage of processing.
Task-Queue¶
The task queue is a collection of FiFo
s. One for each Warrior
keeping track of the current tasks running for each Warrior.
The Proc¶
This is the Processing unit. Its main characteristic is that is has to be a state-less Module, as no state should subsist between processes. This same processing unit will be called by each of the Programs to try destroy each other. Every time, with a new instruction, and at the end of the processing, everything is done.
Ports¶
State-machine¶
pSpace¶
Not implemented
ToDo¶
Loader¶
Description of the trouble¶
My main trouble at the moment is to find a way to Load the programms inside the Virtual Machine. The MARS had been designed as a closed system, with absolutely no input, and one output, namely the result of the fight.
That means that my current question doesn’t get answered by design:
How to get the programs in the Core ofpuredarwin
MARS ?
I made a first try with an RS232 Module (self-designed) where the goal would be to load the Programs via a serial line ... I’m not entirely satisfied with that solution. Actually, I’m not sure that it would be practical.
Solution¶
Do not use any loader¶
For the moment, I would advice using rev 548b16a67881
and
traceProc.py as a main to simulate. This testModule also has a
correct simulation implementation for the Queue and the Core. This
shouldn’t be a trouble to test a program on this MARS.
Quality of this solution¶
This solution makes some sense as the MyHDL module are actually not directly intended for synthesis. So, using simulation tricks in order to simulate is not seen as a betrayal.
Status¶
hg log
is your friend ...
Tue Mar 20 20:31:35 CET 2012
¶
Reorganizing everything ...
Wed Dec 2 00:48:03 CET 2009
¶
A good simulation basis¶
I realized the incapacity of MyHDL to synthesize anything. That’s not bad in itself, Actually, I did not ordered my ALTERA yet, so, I’m not able to check any synthesis. And better yet, till now, even If I tried to keep to a synthetizable MyHDL, I never used it. I used MyHDL, (I have to admit it, without realizing it), as a prototyping tool, and thanks to it, I got results !
The current repository also has a good base for simulation, lots of components are there, pSpace is still missing, and some function implementation might also be missing, but a good basis is there.
Try it if you feel you can, and don’t forget to report Issues !