Core War ett projektarbete i PINK gjort 1995-05-21 vid Institutionen för Datavetenskap, Linköpings tekniska Högskola av: Leif Lindgren Joakim Malm Lars Sundberg Inledning Som projektuppgift i PINK våren '95 valde vi någort som heter Core Wars. Denna uppgift går ut på att skriva en enkel emulator där man kan köra två program som tävlar mot varandra genom att helt enkelt försöka få det andra programmet att sluta att exekvera. Emulatorn består av ett cirkulärt minne, där varje minnescell innehåller ett ord, dvs både en instruktion och data, och emulatorn klarar av ett antal enkla maskinkodsinstruktioner. Tidsplan Vi har utgått ifrån följande tidsplan och denna har faktiskt visat sig vara ganska korrekt. Inläsning i ämnet 20h Planering, specifisering 10h Systemering 60h Kodning inklusive testning 60h Dokumentation 10h * 160h Specifikation Sedan vi läst in oss i ämnet och rett ut hur våran processor skulle fungera var det största problemet hur vi skulle representera minnet och processköerna i lisp. Vi kom dock fram till att minnet borde bestå utav en array där varje element är en struktur och processorköerna av listor. Valet utav minnesrepresentation är egentligen ganska naturligt eftersom vi vill snabbt kunna få access till specifika minnespositioner. Att varje element, eller om man så vill ord, i minnet är en struktur för med sig att det blir väldigt enkelt att beskriva varje del av detta, och antalet primitiver för att läsa och skriva till dessa delar blir väldigt få på grund av hur defstruct fungerar. Sedan detta stora problem var löst försökte vi att strukturera upp vilka delar som programmet skulle bestå utav och hur dessa skulle fungera. Ganska snabbt kom vi fram till att vi måste ha en kompilator, och en massa primitiver som hanterar de olika datatyperna, en slags initieringsrutin, och en loop som utför själva emuleringen. Dessa specifierade vi snabbt och delade sedan upp kodningen emellan oss. Värt att notera är att vi bara behövt lägga till en variabel och tre funktioner sedan den ursprungliga specifikationen. Emulatorn som vi gör ska klara av att läsa in två assemblerprogram (skrivna i Redcode) från filer, omvandla dessa program till maskinkod och sedan låta programmen exekveras tills ett utav dem stannar. Strukturen på emulatorn ska vara sådan att man enkalt kan ändra de instruktioner som ingår i Redcode, vars standard ändras ofta, och det ska även gå relativt enkelt att lägga till andra saker såsom t.ex. möjligheten att köra fler än två Redcode-program. Begränsningar För att inte få ett allt för stort projekt beslöt vi oss för att göra vissa begränsningar. Dessa förändrar dock inte funktionen på emulatorn nämnvärt och eftersom standarden varierar från år till år så är det inte så lätt att säga vilka instruktioner som skall ingå. De begränsningar vi gjort är: 1. Kompilatorn klarar varken av "labels", "pseudo-instructions" eller operatorer. Detta påverkar dock inte möjligheterna i Redcode-programmen. 2. Vi har bara implementerat adresseringstyperna "direct", "indirect" och "immediate". Inte "predecrement" 3. Emulatorn klarar endast av två program 4. Följande tio instruktioner är implementerade: DAT, MOV ,ADD, SUB, JMP, JMZ, JMG, DJZ, CMP och SPL Core War User Manual and Documentation Department of Computer and Information Science, Linköping University by: Leif Lindgren Joakim Malm Lars Sundberg User Manual The emulator is a so called MARS (Memory Array Redcode Simulator) which is used for running CoreWar. CoreWar is a game where you write two programs in the assembler language Redcode and then you let them enter a circular memory array. MARS will then alter the execution rights between the two programs which are being allowed to do one execution per cycle. The game is over when one program has no executable processes running or when the maximum number of cycles have been reached. How to make programs in Redcode Redcode has ten different instructions. Every instruction has one or two arguments. The arguments describes two things: an addressing mode and a data value. There are three different addressing modes: Direct, Indirect, and Immediate. All three use relative addressing, which means the address depends on where in the memory array you are. Here is the Redcode instruction set that we use. Encoded Mnemonic Argument Action Form Symbol ---------------------------------------------------------------------------- 0 DAT A B Initialize locations to the values A and B. 1 MOV A B Move A into location B. 2 ADD A B Add operand A to contents of location B and store result in location B. 3 SUB A B Subtract operand A from contents of location B and store result in location B. 4 JMP A Jump to location A. 5 JMZ A B If operand A is 0, jump to location B; otherwise continue with next instruction. 6 JMG A B Jump if greater. 7 DJZ A B Decrement contents of location A by 1. If location A now holds 0, jump to location B; otherwise continue with next instruction. 8 CMP A B Compare operand A with operand B. If they are not equal, skip next instruction; otherwise continue with next instruction. 9 SPL A Creates a new process. If A is not Immediate a new process is created at the effective address of A. User Manual The three addressing modes are identified by symbols placed before the argument: Encoded Mnemonic Name Meaning Form Symbol ---------------------------------------------------------------------------- 0 # Immediate The number following this symbol is the operand. 1 Direct The number specifies an offset from or $ the current instruction. Mars adds the offset to the address of the current instruction; the number stored at the location reached in this way is the operand. 2 @ Indirect The number following this symbol specifies an offset from the current instruction to a location where the relative address of the operand is found. Mars adds the offset to the address of the current instruction and retrieves the number stored at the specified location; this number is then interpreted as an offset from its own address. The number found at this second location is the operand. All address arithmetic is done modulo the size of CORE. The MOD operator is the remainder after division, and so 5096 MOD 4096 is 1000. Thus if your CORE array has 4096 locations, a reference to location 5096 is taken as a reference to location 1000. Because a program can never refer to an absolute address, some addressing modes for some operands do not make sense. For example, in the instruction MOV #5 #0 the operand to be moved is the immediate value 5, but the argument indicating where it is to be moved is not an address but the immediate value 0, which has no clear interpretation. Here is an example of a short program: ; impgun spl 2 jmp -1 ; comments mov 0 1 ; comments User Manual To run the emulator To run the emulator you first have to evaluate the sourcecode in your LISP system and then simply call the CoreWar function with two filenames as arguments: > (CoreWar filename1 filename2) Options You have four global variables that you can change for configuration of the CoreWar environment. They are: *MaxProgramLength* Describes how many instructions a Redcode program is allowed to have. Default is 40. *MaxNumberOfCycles* Describes how many instructions the programs are allowed to execute. If MaxNumberOfCycles is reached under a game, it is a tie. Default is 15000. *MaxNumberOfTasks* Describes have many tasks (processes) each program is allowed to have in the programs task que. Default is 20. *CoreSize* Describes the number of memory cells in the array. Default is 8000. To change one of these variables you simply use setq at the toploop: > (setq *MaxNumberOfTasks* 20) Example (impstomp.red vs imp.red) ;impstomp.red jmp 2 dat 0 0 mov -1 -2 jmp -1 ;imp.red mov 0 1 USER(4): (setq *coresize* 300) 300 USER(5): (CoreWar "~/pink/projekt/impstomp.red" "~/pink/projekt/imp.red") Cycle:1 Address p1:0 Address p2:119 Cycle:2 Address p1:2 Address p2:120 Cycle:3 Address p1:3 Address p2:121 Cycle:4 Address p1:2 Address p2:122 Cycle:5 Address p1:3 Address p2:123 Cycle:6 Address p1:2 Address p2:124 Cycle:7 Address p1:3 Address p2:125 Cycle:8 Address p1:2 Address p2:126 Cycle:9 Address p1:3 Address p2:127 Cycle:10 Address p1:2 Address p2:128 User Manual . . . Cycle:169 Address p1:3 Address p2:287 Cycle:170 Address p1:2 Address p2:288 Cycle:171 Address p1:3 Address p2:289 Cycle:172 Address p1:2 Address p2:290 Cycle:173 Address p1:3 Address p2:291 Cycle:174 Address p1:2 Address p2:292 Cycle:175 Address p1:3 Address p2:293 Cycle:176 Address p1:2 Address p2:294 Cycle:177 Address p1:3 Address p2:295 Cycle:178 Address p1:2 Address p2:296 Cycle:179 Address p1:3 Address p2:297 Cycle:180 Address p1:2 Address p2:298 Cycle:181 Address p1:3 Address p2:299 Cycle:182 Address p1:2 Address p2:0 Cycle:183 Address p1:3 The loser is number 2 USER(6): Documentation Head functions and algorithms Head functions and algorithms The main function The main program is called "CoreWar" and is a function that needs two arguments, simply the filenames (including paths) of the two programs to run. This function consists both of initializing functions and the main loop that executes the competing programs. The initializing procedure begins with compiling and placing the first program into memory, starting at address 0. This address is also placed in TaskQueProg1. For the other program the starting address have to be calculated, and this adress must be randomly chosen. The formula used for this is: max-program-length + a random number between 0 and (core-size - 2 x max-program-length) This ensures that the programs not are stored at the same adress and in most cases there will be some space between them. In the main loop the program uses two global variables; CurrentPlayer (1 or 2) and CurrentCycle. CurrentPlayer switches between 1 and 2 every cycle (one cycle is one execution of the main loop) and CurrentCycle starts at 1 increases with one every cycle. After the current player is set, the next address to execute is placed in a local variable. If the current Taskque should be empty or if current task has reached the maximum number of tasks plus two, the loop is terminated and the player that is not current has won. Otherwise the corecell at this address is placed in a local variable and its opcode is evaluated. Depending of the opcode the right "opcode function" is called. Except for if the opcode is "DAT" then nothing is done. Before the end of the loop current cycle, execution address for program one and execution address for program two is printed on the screen. When the program has leaved the loop one of two things must have happened: One program has stopped executing or current task has exceeded Max number of tasks. In the latter case the match was a tie and otherwise the program which not is the current one has won. The compiler The compiler function, CompileToList, takes one argument, a filename. The file specified by the argument is read and interpreted to machine code which is placed in a list. If there is an error in the Redcode the compiler notifies the user on which line the error occurred. The PlaceProgramInMemory function This function needs two arguments an address and a list with machine code. The function reads five elements from the code list and creates a corecell that are placed at memory position address. This is repeated until the whole list is read. The opcode functions The opcode functions are called Coreopcode (CoreMOV, CoreADD, etc) and takes two arguments; the current corecell and the current address. Inside the functions the different parts of the corecell are placed in local variables and evaluated depending on which Redcode instruction currently being emulated. Some of the opcode functions are sharing the same code and uses a third argument that tells what operation should be done. These are called Coresomething-else to be departed from the other opcode functions. Example: ADD and SUB shares the same code that is placed in the function CoreADD/SUB. Still both the CoreADD and the CoreSUB functions exists but these just call the function with the shared code with a operator (plus or minus). The opcode functions also put the next address or addresses in the current task que. Documentation Head functions and algorithms The Eval-functions Included in the code are three functions that evaluates arguments to addresses. These are called EvalDirect, EvalIndirect and EvalToAdress. The last one takes three arguments; a mode, data and an address and checks what the mode is (direct, indirect or immediate). If the mode is immediate the function result is nil and otherwise it use one of the other to calculate the address to return. The +mod and -mod functions Because of the circular memory all arithmetic operations must be modulo the size of the memory. +mod and -mod are simply the ordinary + and - modulo *CoreSize*. Both functions take any number of arguments and these are evaluated from left to right. Documentation Data structures The memory (the CoreArray) is built up by an array from 0 to CoreSize - 1 of structures (CoreCells). This brings fast access to each and every memory cell and makes it easy to handle each part of it. Each CoreCell consists of five elements: Opcode 0-9 A-mode 0-2 A-data integer B-mode 0-2 B-data integer For every element in the structure there are primitives for reading and writing it. For handling the process scheduling we have one task que per program. The task ques are simply lists with integers and uses the FIFO (FirstInFirstOut) principle. Here follows an examples where the 10 closest cells to the cell being executed are listed every cycle. This shows how the memory and the program works. (imp.red vs killemall.red) ;imp.red mov 0 1 ;killemall.red jmp 2 dat 0 0 mov -1 -4 mov -2 -5 mov -3 -6 mov -4 -7 mov -5 -11 jmg -5 -12 jmp -1 USER(4): (setq *CoreSize* 200) 200 USER(5): (Corewar "~/pink/projekt/imp.red" "~/pink/projekt/killemall.red") Cycle #1 imp.red: 195 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 196 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 197 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 198 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 199 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 0 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) <=== 1 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) Documentation Data structures 2 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 3 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 4 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) killemall.red: 68 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 69 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 70 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 71 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 72 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 73 #S(corecell :opcode 4 :a-mode 1 :a-data 2 :b-mode 1 :b-data 0) <=== 74 #S(corecell :opcode 0 :a-mode 1 :a-data 0 :b-mode 1 :b-data 0) 75 #S(corecell :opcode 1 :a-mode 1 :a-data -1 :b-mode 1 :b-data -4) 76 #S(corecell :opcode 1 :a-mode 1 :a-data -2 :b-mode 1 :b-data -5) 77 #S(corecell :opcode 1 :a-mode 1 :a-data -3 :b-mode 1 :b-data -6) Cycle #2 imp.red: 196 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 197 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 198 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 199 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 0 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 1 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) <=== 2 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 3 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 4 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 5 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) killemall.red 70 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 71 #S(corecell :opcode 0 :a-mode 1 :a-data 0 :b-mode 1 :b-data 0) 72 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 73 #S(corecell :opcode 4 :a-mode 1 :a-data 2 :b-mode 1 :b-data 0) 74 #S(corecell :opcode 0 :a-mode 1 :a-data 0 :b-mode 1 :b-data 0) 75 #S(corecell :opcode 1 :a-mode 1 :a-data -1 :b-mode 1 :b-data -4) <=== 76 #S(corecell :opcode 1 :a-mode 1 :a-data -2 :b-mode 1 :b-data -5) 77 #S(corecell :opcode 1 :a-mode 1 :a-data -3 :b-mode 1 :b-data -6) 78 #S(corecell :opcode 1 :a-mode 1 :a-data -4 :b-mode 1 :b-data -7) 79 #S(corecell :opcode 1 :a-mode 1 :a-data -5 :b-mode 1 :b-data -11) . . . . Cyckle #70 imp.red: Documentation Data structures 64 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 65 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 66 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 67 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 68 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 69 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) <=== 70 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 71 #S(corecell :opcode 0 :a-mode 1 :a-data 0 :b-mode 1 :b-data 0) 72 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 73 #S(corecell :opcode 4 :a-mode 1 :a-data 2 :b-mode 1 :b-data 0) killemall.red: 70 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 71 #S(corecell :opcode 0 :a-mode 1 :a-data 0 :b-mode 1 :b-data 0) 72 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 73 #S(corecell :opcode 4 :a-mode 1 :a-data 2 :b-mode 1 :b-data 0) 74 #S(corecell :opcode 0 :a-mode 1 :a-data 0 :b-mode 1 :b-data 0) 75 #S(corecell :opcode 1 :a-mode 1 :a-data -1 :b-mode 1 :b-data -4) <=== 76 #S(corecell :opcode 1 :a-mode 1 :a-data -2 :b-mode 1 :b-data -5) 77 #S(corecell :opcode 1 :a-mode 1 :a-data -3 :b-mode 1 :b-data -6) 78 #S(corecell :opcode 1 :a-mode 1 :a-data -4 :b-mode 1 :b-data -7) 79 #S(corecell :opcode 1 :a-mode 1 :a-data -5 :b-mode 1 :b-data -11) Cycle #71 imp.red: 65 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 66 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 67 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 68 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 69 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 70 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) <=== 71 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 72 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 73 #S(corecell :opcode 4 :a-mode 1 :a-data 2 :b-mode 1 :b-data 0) 74 #S(corecell :opcode 0 :a-mode 1 :a-data 0 :b-mode 1 :b-data 0) killemall.red: 71 #S(corecell :opcode 0 :a-mode 1 :a-data 0 :b-mode 1 :b-data 0) 72 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 73 #S(corecell :opcode 4 :a-mode 1 :a-data 2 :b-mode 1 :b-data 0) 74 #S(corecell :opcode 0 :a-mode 1 :a-data 0 :b-mode 1 :b-data 0) 75 #S(corecell :opcode 1 :a-mode 1 :a-data -1 :b-mode 1 :b-data -4) 76 #S(corecell :opcode 1 :a-mode 1 :a-data -2 :b-mode 1 :b-data -5) <=== 77 #S(corecell :opcode 1 :a-mode 1 :a-data -3 :b-mode 1 :b-data -6) 78 #S(corecell :opcode 1 :a-mode 1 :a-data -4 :b-mode 1 :b-data -7) 79 #S(corecell :opcode 1 :a-mode 1 :a-data -5 :b-mode 1 :b-data -11) Documentation Data structures 80 #S(corecell :opcode 6 :a-mode 1 :a-data -5 :b-mode 1 :b-data -12) Cycle #72 imp.red: 66 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 67 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 68 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 69 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 70 #S(corecell :opcode 1 :a-mode 1 :a-data 0 :b-mode 1 :b-data 1) 71 #S(corecell :opcode 0 :a-mode 1 :a-data 0 :b-mode 1 :b-data 0) <=== 72 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 73 #S(corecell :opcode 4 :a-mode 1 :a-data 2 :b-mode 1 :b-data 0) 74 #S(corecell :opcode 0 :a-mode 1 :a-data 0 :b-mode 1 :b-data 0) 75 #S(corecell :opcode 1 :a-mode 1 :a-data -1 :b-mode 1 :b-data -4) killemall.red: 72 #S(corecell :opcode 0 :a-mode 0 :a-data 0 :b-mode 0 :b-data 0) 73 #S(corecell :opcode 4 :a-mode 1 :a-data 2 :b-mode 1 :b-data 0) 74 #S(corecell :opcode 0 :a-mode 1 :a-data 0 :b-mode 1 :b-data 0) 75 #S(corecell :opcode 1 :a-mode 1 :a-data -1 :b-mode 1 :b-data -4) 76 #S(corecell :opcode 1 :a-mode 1 :a-data -2 :b-mode 1 :b-data -5) 77 #S(corecell :opcode 1 :a-mode 1 :a-data -3 :b-mode 1 :b-data -6) <=== 78 #S(corecell :opcode 1 :a-mode 1 :a-data -4 :b-mode 1 :b-data -7) 79 #S(corecell :opcode 1 :a-mode 1 :a-data -5 :b-mode 1 :b-data -11) 80 #S(corecell :opcode 6 :a-mode 1 :a-data -5 :b-mode 1 :b-data -12) 81 #S(corecell :opcode 4 :a-mode 1 :a-data -1 :b-mode 1 :b-data 0) (78) The loser is number 1 [3c] USER(6): Documentation Global variables GLOBAL VARIABLES: CoreArray array from 0 to (CoreSize - 1) of CoreCells CoreCell structure with 5 integers: Opcode 0-9 (0=dat 1=mov 2=add 3=sub 4=jmp 5=jmz 6=jmg 7=djz 8=cmp 9=spl) A-mode 0-2 (1=direct 2=indirect 0=immediate) A-data B-mode 0-2 B-data TaskQueProg1 list (with adressintegers: (int ... int)) TaskQueProg2 list (with adressintegers: (int ... int)) CurrentPlayer integer (1 or 2) CurrentAdress integer (from 0 to *CoreSize* -1) *MaxProgramLength* integer "Max number of REDCODE instructions" *MaxNumberOfCycles* integer "Max number of cycles for a program" *MaxNumberOfTasks* integer "Max number of records in the task que" *CoreSize* integer "The size of the core-memory" *Direct* 1 "Code for the direct mode" *Indirect* 2 "Code for the indirect mode" *Immediate* 0 "Code for the immediate mode" *DAT* 0 "The DATa machine code instuction" *MOV* 1 "The MOVe machine code instuction" *ADD* 2 "The ADD machine code instruction" *SUB* 3 "The SUBstract machine code instruction" *JMP* 4 "The JuMP machine code instruction" *JMZ* 5 "The JuMp if Zero machine code instruction" *JMG* 6 "The JuMp if Greater machine code instruction" *DJZ* 7 "The Decrement and Jump if Zero instr" *CMP* 8 "The CoMPare machine code instruction" *SPL* 9 "The SPLit machinecode instruction" Documentation Primtiv functions PRIMITIV FUNCTIONS: CoreArray: CreateCoreArray out:: T ReadCoreCell in: adress out: CoreCell WriteCoreCell in: adress CoreCell out: T or NIL CoreCell: CreateCoreCell in: &rest out: CoreCell (default is (0 # 0 # 0) WriteOpcode in: CoreCell NewOpcode out: CoreCell ReadOpcode in: CoreCell out: Opcode WriteA-mode in: CoreCell NewA-mode out: CoreCell ReadA-mode in: CoreCell out: A-mode WriteA-data in: CoreCell NewA-data out: CoreCell ReadA-data in: CoreCell out: A-data WriteB-mode in: CoreCell NewB-mode out: CoreCell ReadB-mode in: CoreCell out: B-mode WriteB-data in: CoreCell NewB-data out: CoreCell ReadB-data in: CoreCell out: B-data Documentation Primtiv functions TaskQue: PopTask in: out: adress or NIL (NIL when empty que) PushTask in: adress out: T or NIL (NIL when que is full) CreateTaskQue out: TaskQue (empty list) Adress: IncAdress in: adress number out: adress DecAdress in: adress number out: adress Documentation Functions FUNCTIONS: CoreWar in: filename filename out: CompileToList in: filename out: list (with maschinecode: (a b c d e f ...)) or NIL (NIL when error in code) PlaceProgramInMemory in: startadress list out: T or NIL (NIL when program length > MaxProgramLength) EvalToAdress in: mode data adress out: adress or NIL EvalDirect in: data adress out: adress EvalIndirect in: data adress out: adress or NIL CoreDAT in: CoreCell Adress out: T or NIL CoreMOV in: CoreCell Adress out: T or NIL CoreADD in: CoreCell Adress out: T or NIL CoreSUB in: CoreCell Adress out: T or NIL CoreJMP in: CoreCell Adress out: T or NIL CoreJMZ in: CoreCell Adress out: T or NIL CoreJMG in: CoreCell Adress out: T or NIL CoreDJZ in: CoreCell Adress out: T or NIL Documentation Functions CoreCMP in: CoreCell Adress out: T or NIL CoreSPL in: CoreCell Adress out: T or NIL CoreADD/SUB in: corecell adress fn out: T or NIL CoreJMP-test in: corecell adress fn out: T or NIL +mod in: &rest (integers) out: integer -mod in: &rest (integers) out: integer ;;; Filename : corewar.lsp ;;; Date : 95-05-21 ;;; Authors : Leif Lindgren, Joakim Malm and Lars Sundberg at Linköping ;;; University, Sweden. ;;; Contents : An executive program written in CommonLISP. The program is a so ;;; called MARS (Memory Array Redcode Simulator) which is used for ;;; running CoreWar programs written in Redcode. ;;;*************************************************************************** ;;; GLOBAL VARIABLES ;;;*************************************************************************** (setq *MaxProgramLength* 40) "Max number of REDCODE instructions" (setq *MaxNumberOfCycles* 15000) Max number of cycles for a program" (setq *MaxNumberOfTasks* 20) "Max number of records in the task que" (setq *CoreSize* 8000) "The size of the core-memory" (defconstant *Direct* 1 "Code for the direct mode") (defconstant *Indirect* 2 "Code for the indirect mode") (defconstant *Immediate* 0 "Code for the immediate mode") (defconstant *DAT* 0 "The DATa machine code instuction") (defconstant *MOV* 1 "The MOVe machine code instuction") (defconstant *ADD* 2 "The ADD machine code instruction") (defconstant *SUB* 3 "The SUBstract machine code instruction") (defconstant *JMP* 4 "The JuMP machine code instruction") (defconstant *JMZ* 5 "The JuMp if Zero machine code instruction") (defconstant *JMG* 6 "The JuMp if Greater machine code instruction") (defconstant *DJZ* 7 "The Decrement and Jump if Zero instr") (defconstant *CMP* 8 "The CoMPare machine code instruction") (defconstant *SPL* 9 "The SPLit machinecode instruction") ;;;*************************************************************************** ;;;* PRIMITIV FUNCTIONS ;;;*************************************************************************** ;;;********************** Primitives for CoreCell **************************** (defstruct ( CoreCell (:constructor CreateCoreCell) (:conc-name Read) (:copier CopyCoreCell)) (Opcode 0) (A-mode *Immediate*) (A-data 0) (B-mode *Immediate*) (B-data 0)) (defun WriteOpcode ( CoreCell NewOpcode) "CoreCell X Opcode => CoreCell" (let ((CC (CopyCoreCell CoreCell))) (progn (setf (ReadOpcode CC) NewOpcode) CC))) (defun WriteA-mode ( CoreCell NewA-mode) "CoreCell X A-mode => CoreCell" (let ((CC (CopyCoreCell CoreCell))) (progn (setf (ReadA-mode CC) NewA-mode) CC))) (defun WriteA-data ( CoreCell NewA-data) "CoreCell X A-data => CoreCell" (let ((CC (CopyCoreCell CoreCell))) (progn (setf (ReadA-data CC) NewA-data) CC))) (defun WriteB-mode ( CoreCell NewB-mode) "CoreCell X B-mode => CoreCell" (let ((CC (CopyCoreCell CoreCell))) (progn (setf (ReadB-mode CC) NewB-mode) CC))) (defun WriteB-data ( CoreCell NewB-data) "CoreCell X B-data => CoreCell" (let ((CC (CopyCoreCell CoreCell))) (progn (setf (ReadB-data CC) NewB-data) CC))) ;;;*********************** Primitives for TaskQue *************************** (defun CreateTaskQue () " => TaskQue" '()) (defun PopTask () " => adress (or NIL)" ;; PopTask checks which program that is the Current one, and then it takes out ;; the first task in that programs Task Que. If the programs Task Que is empty, ;; NIL is returned. (cond ((= CurrentPlayer 1) (if (eq TaskQueProg1 '()) nil (let ((Adress (first TaskQueProg1))) (setq TaskQueProg1 (rest TaskqueProg1)) Adress))) ((= CurrentPlayer 2) (if (eq TaskQueProg2 '()) nil (let ((Adress (first TaskQueProg2))) (setq TaskQueProg2 (rest TaskQueProg2)) Adress))))) (defun PushTask (Adress) "adress => T or NIL" ;; This functions takes an address and puts in last in the Task Que of the ;; Current program. If the Task Que is full the new task (the address) is ;; ignored and PushTask returns NIL. (cond ((= CurrentPlayer 1) (if (>= (list-length TaskQueProg1) *MaxNumberOfTasks*) nil (progn (setq TaskQueProg1 (append TaskQueProg1 (list Adress))) t) )) ((= CurrentPlayer 2) (if (>= (list-length TaskQueProg2) *MaxNumberOfTasks*) nil (progn (setq TaskQueProg2 (append TaskQueProg2 (list Adress))) t) )))) ;;;***************** Primitives for CoreArray ******************************** (defun CreateCoreArray () " => T" (setq CoreArray (make-array *CoreSize* :initial-element (CreateCoreCell)))) (defun ReadCoreCell (Adress) "adress => CoreCell" (aref CoreArray Adress)) (defun WriteCoreCell (Adress CoreCell) "adress X CoreCell => T or NIL" (if (> Adress *CoreSize* ) nil (progn (setf (aref CoreArray Adress) CoreCell) t))) ;;;********************** Primitives for Adress ****************************** (defun IncAdress (adress number) "adress x integer -> adress" (+mod adress number)) (defun DecAdress (adress number) "adress x integer -> adress" (-mod adress number)) ;;;************************************************************************** ;;; FUNCTIONS ;;;************************************************************************** ;;;*************************** modulo functions ***************************** ;; Because of the circular memory all arithmetic operations must be modulo the ;; size of the memory. +mod and -mod are simply the ordinary + and - modulo ;; *CoreSize*. Both functions take any number of arguments and these are ;; evaluated from left to right. (defun +mod (&rest numbers) "integer X integer X ... X integer => integer" ;; Performs addition modulo *CoreSize* (labels ((add (numbers) (if (endp numbers) 0 (+ (first numbers) (add (rest numbers)))))) (mod (add numbers) *CoreSize*))) (defun -mod (&rest numbers) "integer X integer X ... X integer => integer" ;; Performs subtraction modulo *CoreSize* (labels ((sub (numbers) (if (endp numbers) 0 (- (first numbers) (sub (rest numbers)))))) (mod (sub numbers) *CoreSize*))) ;;;********************* Adress evaluating functions ************************ ;; These three functions evaluates arguments to addresses. ;; They are called EvalDirect, EvalIndirect and EvalToAdress. The last one takes ;; three arguments: a mode, data and an address and checks what the mode is ;; (direct, indirect or immediate). If the mode is immidiate the function result ;; is nil and otherwise it use one of the other to calculate the address to return. (defun EvalDirect (data adress) "data x adress -> adress" (+mod data adress)) (defun EvalIndirect (data adress) "data x adress -> adress" (let ((nextcell (ReadCoreCell (EvalDirect data adress )))) (+mod adress data (ReadB-data nextcell)) )) (defun EvalToAdress (mode data adress) "mode x data x adress -> adress or NIL if failure" (cond ((eq mode *indirect*) (EvalIndirect data adress)) ((eq mode *Direct*) (EvalDirect data adress)) (t nil))) ;;;************* Functions that execute the machinecode instructions ******** ;; The opcode functions are called Coreopcode (CoreMOV, CoreADD, etc) and takes ;; two arguments: the current corecell and the current address. Inside the ;; functions the different parts of the corcell are placed in local variables ;; and evaluated depending on which Redcode instruction currently beeing emulated. ;; Some of the opcode functions are sharing the same code and uses a third ;; argument that tells what operation should be done. These are called ;; Coresomthing-else to be departed from the other opcode functions. Example: ;; ADD and SUB shares the same code that is placed in the function CoreADD/SUB. ;; Still both the CoreADD and the CoreSUB functions exists but these just call ;; the function with the shared code with a operator (plus or minus). ;; The opcode functions also put the next address or addresses in the current ;; task que. (defun CoreMOV (corecell adress) "corecell x adress -> t or nil" (let* ((A-mode (ReadA-mode corecell)) (A-data (ReadA-data corecell)) (B-mode (ReadB-mode corecell)) (B-data (ReadB-data corecell)) (newadress (EvalToAdress B-mode B-data adress)) (newcell (let ((adress/? (EvalToAdress A-mode A-data adress))) (if (eq adress/? nil) (if (eq newadress nil) nil (WriteB-data (ReadCoreCell newadress) A-data)) (ReadCoreCell adress/?)) ))) (progn (PushTask (IncAdress adress 1)) (if (or (eq newadress nil) (eq newcell nil)) nil (WriteCoreCell newadress newcell)) ))) (defun CoreJMP (corecell adress) "corecell x adress -> t or nil" (let* ((A-mode (ReadA-mode corecell)) (A-data (ReadA-data corecell)) (newadress (EvalToAdress A-mode A-data adress))) (if (eq newadress nil) (progn (PushTask (IncAdress adress 1)) nil) (progn (PushTask newadress) t)))) (defun CoreADD/SUB (corecell adress fn) "corecell x adress x fn -> t or nil" ;; fn is supposed to add or subtract (let* ((A-mode (ReadA-mode corecell)) (A-data (ReadA-data corecell)) (B-mode (ReadB-mode corecell)) (B-data (ReadB-data corecell)) (newadress (EvalToAdress B-mode B-data adress)) (newcell (let ((adress/? (EvalToAdress A-mode A-data adress))) (if (eq newadress nil) nil (let* ((Bcell (ReadCoreCell newadress)) (BA-data (ReadA-data Bcell)) (BB-data (ReadB-data Bcell))) (if (eq adress/? nil) (WriteB-data Bcell (funcall fn BB-data A-data)) (let* ((Acell (ReadCoreCell adress/?)) (AA-data (ReadA-data Acell)) (AB-data (ReadB-data Acell))) (WriteA-data (WriteB-data Bcell (funcall fn AB-data BB-data)) (funcall fn AA-data BA-data)) ))))))) (progn (PushTask (IncAdress adress 1)) (if (eq newadress nil) nil (WriteCoreCell newadress newcell))))) (defun CoreAdd (corecell adress) "corecell adress -> t or nil" (CoreAdd/SUB corecell adress '+mod)) (defun CoreSUB (corecell adress) "corecell adress -> t or nil" (CoreADD/SUB corecell adress '-mod)) (defun CoreJMP-test(corecell adress fn) "corecell x adress x fn -> t or nil" ;; fn is supposed to compare a number to zero, eg >,<,= etc (let* ((A-mode (ReadA-mode corecell)) (A-data (ReadA-data corecell)) (B-mode (ReadB-mode corecell)) (B-data (ReadB-data corecell)) (newadress (EvalToAdress A-mode A-data adress)) (value (let ((tmpadress (EvalToAdress B-mode B-data adress))) (if (eq tmpadress nil) B-data (ReadB-data (ReadCoreCell tmpadress)))))) (if (and newadress (funcall fn value 0)) (progn (PushTask newadress) t) (progn (PushTask (IncAdress adress 1)) nil) ))) (defun CoreJMZ (corecell adress) "corecell x adress -> t or nil" (CoreJMP-test corecell adress '=)) (defun CoreJMG (corecell adress) "corecell x adress -> t or nil" (CoreJMP-test corecell adress '>)) (defun CoreCMP (corecell adress) "corecell x adress -> t or nil" (let* ((A-mode (ReadA-mode corecell)) (A-data (ReadA-data corecell)) (B-mode (ReadB-mode corecell)) (B-data (ReadB-data corecell)) (Badress (EvalToAdress B-mode B-data adress)) (Bcell (if Badress (ReadCoreCell Badress) nil)) (BB-data (if Badress (ReadB-data Bcell) nil)) (cmp? (if (eq Badress nil) nil (let ((tmpadress (EvalToAdress A-mode A-data adress))) (if (eq tmpadress nil) (eq A-data BB-data) (let ((tmpcell (ReadCoreCell tmpadress))) (eq tmpcell Bcell) )))) )) (if cmp? (progn (PushTask (IncAdress adress 2)) t) (progn (PushTask (IncAdress adress 1)) nil)))) (defun CoreDJZ (corecell adress) "corecell x adress -> t or nil" (labels ((decrement (corecell adress) (let* ((B-mode (ReadB-mode corecell)) (B-data (ReadB-data corecell)) (adress/? (EvalToAdress B-mode B-data adress))) (if (eq adress/? nil) (WriteCoreCell adress (WriteB-data corecell (-mod B-data 1))) (let* ((newCell (ReadCoreCell adress/?)) (newData (ReadB-data newCell))) (WriteCoreCell adress/? (WriteB-data newCell (-mod newData 1)))))))) (progn (decrement corecell adress) (let ((newcell (ReadCoreCell adress))) (CoreJMP-test newcell adress '=))) )) (defun CoreSPL (corecell adress) "corecell x adress ->t or nil" (let* ((A-mode (ReadA-mode corecell)) (A-data (ReadA-data corecell)) (newadress (EvalToAdress A-mode A-data adress))) (progn (PushTask (IncAdress adress 1)) (if newadress (PushTask newadress) nil)))) ;;;**************************** Compile function **************************** (defun CompileToList (filename) "assembler file => list with machinecode (or NIL when error in the code)" ;; This function takes a filename as argument and it creates a list with ;; machinecode. Every instruction puts five integers in the list. The first ;; one describes which instruction it is. The second one describes the A-mode, ;; the third the A-data value, the fourth the B-mode and the fifth describes ;; the B-data value. If the instruction only has one argument (eg SPL has ;; only a A-arg) the function will add 0 0 for the other argument to the list. (let ((codelist '()) (linecounter 0)) (catch 'ErrorOccurrence (with-open-file (infile (translate-logical-pathname filename) :direction :input) (labels ( (MyError () (Format t "~%Error at line ~a in program ~a. Empty lines not counted." linecounter CurrentPlayer) (throw 'ErrorOccurrence nil)) (AddArgumentToCodelist (arg) (if (listp arg) (setq codelist (append codelist arg)) (setq codelist (append codelist (list *Direct* arg))))) (ReadTwoArgs (instruction) (setq codelist (append codelist (list instruction))) (AddArgumentToCodelist (ReadArgument)) (AddArgumentToCodelist (ReadArgument))) (ReadA-arg (instruction) (setq codelist (append codelist (list instruction))) (AddArgumentToCodelist (ReadArgument)) (AddArgumentToCodelist 0)) (ReadB-arg (instruction) (setq codelist (append codelist (list instruction))) (AddArgumentToCodelist 0) (AddArgumentToCodelist (ReadArgument))) (ReadArgument () (let* ((nextchar (peek-char t infile))) (cond ((equal nextchar #\@) (read-char infile) (list *Indirect* (ReadData))) ((equal nextchar #\#) (read-char infile) (list *Immediate* (ReadData))) ((equal nextchar #\$) (read-char infile) (list *Direct* (ReadData))) (t (ReadData))))) (ReadData () (let ((newdata (read infile nil '==eof==))) (if (numberp newdata) newdata (MyError))))) (loop (setq linecounter (1+ linecounter)) (let ((InObject (read infile nil '==eof==))) (cond ((equal InObject 'DAT) (ReadTwoArgs *dat*)) ((equal InObject 'MOV) (ReadTwoArgs *mov*)) ((equal InObject 'ADD) (ReadTwoArgs *add*)) ((equal InObject 'SUB) (ReadTwoArgs *sub*)) ((equal InObject 'JMP) (ReadA-arg *jmp*)) ((equal InObject 'JMZ) (ReadTwoArgs *jmz*)) ((equal InObject 'JMG) (ReadTwoArgs *jmg*)) ((equal InObject 'DJZ) (ReadTwoArgs *djz*)) ((equal InObject 'CMP) (ReadTwoArgs *cmp*)) ((equal InObject 'SPL) (ReadA-arg *spl*)) ((equal InObject '==eof==) (return codelist)) (t (if (equal #\Newline (peek-char nil infile)) t (read-line infile))))))))))) ;;;****** Function for placing a machinecode program in the CoreArray ******* (defun PlaceProgramInMemory (adress codelist) "adress X codelist (list with machinecode) => T or NIL" ;; This function takes a codelist (a list created by the CompileToList ;; function) and puts it into the CoreArray with adress as startaddress. (cond ((> (/ (length codelist) 5) *MaxProgramLength* ) (progn (format t "~%Program ~a is too long." CurrentPlayer) NIL)) ((endp codelist) t) (t (WriteCoreCell adress (CreateCoreCell :opcode (first codelist) :A-mode (second codelist) :A-data (third codelist) :B-mode (fourth codelist) :B-data (fifth codelist))) (PlaceProgramInMemory (+mod (IncAdress adress 1)) (nthcdr 5 codelist))))) ;;;************************ Main function *********************************** (defun CoreWar (file1 file2) " => " ;; This is the main function. It takes to filenames as parameters and it ;; compiles the two programs and puts them into the CoreArray by calling ;; the CompileToList and PlaceProgramInMemory functions. Then the CoreWar has ;; a loop which runs until MaxNumberOfCycles are reached or one program ;; doesn't have any processes left. (let ((CurrentCycle 1)) (progn (CreateCoreArray) (setq CurrentPlayer 1) (PlaceProgramInMemory 0 (CompileToList file1)) (setq TaskQueProg1 (CreateTaskQue)) (PushTask 0) (Setq CurrentPlayer 2) (let ((other-adress (+ *MaxProgramLength* (random (- *CoreSize* (* 2 *MaxProgramLength*)))) )) (Progn (PlaceProgramInMemory other-adress (CompileToList file2)) (setq TaskQueProg2 (CreateTaskQue)) (PushTask other-adress) (values))) (loop (if (= CurrentPlayer 1) (setq CurrentPlayer 2) (setq CurrentPlayer 1)) (setq CurrentAdress (PopTask)) (if (or (equal CurrentAdress nil) (= CurrentCycle (+ 1 *MaxNumberOfCycles*))) (return)) (let* ((CurrentCell (ReadCoreCell CurrentAdress)) (CurrentOpCode (ReadOpCode CurrentCell))) (Cond ((= CurrentOpCode *MOV*) (CoreMOV CurrentCell CurrentAdress)) ((= CurrentOpCode *ADD*) (CoreADD CurrentCell CurrentAdress)) ((= CurrentOpCode *SUB*) (CoreSUB CurrentCell CurrentAdress)) ((= CurrentOpCode *JMP*) (CoreJMP CurrentCell CurrentAdress)) ((= CurrentOpCode *JMZ*) (CoreJMZ CurrentCell CurrentAdress)) ((= CurrentOpCode *JMG*) (CoreJMG CurrentCell CurrentAdress)) ((= CurrentOpCode *DJZ*) (CoreDJZ CurrentCell CurrentAdress)) ((= CurrentOpCode *CMP*) (CoreCMP CurrentCell CurrentAdress)) ((= CurrentOpCode *SPL*) (CoreSPL CurrentCell CurrentAdress)) ( t nil)) ) (if (= CurrentPlayer 1) (format t "~%Cycle:~7a Address p1:~7a"CurrentCycle CurrentAdress) (progn (format t "Address p2:~7a" CurrentAdress) (setq CurrentCycle (+ CurrentCycle 1))))) (if (> CurrentCycle *MaxNumberOfCycles*) (progn (format t "~%The match was a tie.") (values)) (progn (format t "~%The loser is number ~a" CurrentPlayer) (values))))))