Virtual_machine

After byte-code files are generated, it is time to run the virtual machine.

Launch

To start corewar we have to pass .cor files as arguments:

$ ./corewar batman.cor ant-man.cor iron_man.cor

By the way, it is possible to run the vm passing the same file as parameter for multiple times:

$ ./corewar batman.cor batman.cor batman.cor

Vm doesn't care about players' names. It assigns unique IDs and handles players as Player 1, Player 2 and Player 3.

There is a constant MAX_PLAYERS initialised with value 4. It limits amount of players that can be loaded in a single game.

Flag -n

The order of the players, or rather the order of assigning identification numbers, can be changed using the flag -n.

Original corewar doesn't support this flag, but according to the text of the subject, it must be present in our program.

This flag assigns an id number to the specified champion. And players who did not receive such a number using the flag, first of the unused id-s will be assigned:

-n number sets the number of the next player. If non-existent, the player will have the next available number in the order of the parameters.

For example ...:

$ ./corewar batman.cor -n 1 ant-man.cor iron_man.cor

... Ant-Man will be Player 1, Batman — Player 2, а Iron Man — Player 3.

Important

the number after -n must be bigger than 0, should not exceed amount of players loaded into the game, and must be unique. We can't assign same id to multiple players.

Validation

The virtual machine reads the files with champions' bytecode and checks for the presence of the magic header, whether the code size in header of the file matches the real one, and so on.

The max limit for player's executable code size (682 bytes):

# define MEM_SIZE           (4 * 1024)
// ...
# define CHAMP_MAX_SIZE     (MEM_SIZE / 6)

No min limit is defined, so a champion without executable code is considered valid.

After reading the file vm must have following data:

• unique ID
• champion name
• champion comment
• executable code size
• executable code

Arena initialisation

Vm's memory is a battlefield (or arena) for champions.

If all the files and parameters were validated successfully, champions' executable codes must be loaded into the arena and fight.

Arena size is defined by the MEM_SIZE constant, which is initialised with the value 4096.

The start position of each player is defined as follows:

• divide memory size by amount of champions

• multiply the result by player's id - 1

4096 / 3 = 1365

player1 position **1365 * (1 - 1) = 0**

player2 position **1365 * (2 - 1) = 1365**

player3 position **1365 * (3 - 1) = 2730**

Memory organisation

The virtual machine has a loop-memory. That is, after last cell you get to the first one.

So for memory size 4096, first cell index is 0 and last cell index is 4095.

To avoid addressing out of memory boundaries, we have to use modulo 4096 every time we deal with addresses. And don't forget the negative cases.

Game parameters

Before game starts, the value of the following variables must be set:

• player last reported alive

This is the variable showing the winner. It is initialised with the highest player id, and is updated every time operation live is performed.

• cycles counter
• counter for operation live, to check how many times this operation was performed during the last cycles_to_die cycles.
• cycles_to_die — length of current check period in cycles.

This variable is initialised with the value of constant CYCLES_TO_DIE (1536).

• amount of checks performed

What is a check and how it is performed we will discuss later.

Cursors (processes) initialisation

After champions are loaded into the memory, at their beginnings are placed cursors.

cursors contain following information:

• id - unique.

• carry - flag which can be changed by certain operations and which affects zjmp operation, initialised with value false.

• opcode - operation code, before the battle starts it is not initialised.

• last_live - number of cycle in which current cursor performed operation live last time.

• wait_cycles - amount of cycles to wait before operation execution.

• position - address in memory

• jump - amount of bytes cursor must jump to get to the next operation

• registries [REG_NUMBER] - registries of current cursor

All registries excepting r1 are initialised with 0. r1 is initialised with the negated player id (r1 = -player_id).

Important

Cursor doesn't work for a certain player. It just executes the code it reads from the memory.

During the battle after operations fork or lfork, the new cursor will get all it's values from the parent cursor and not from the player.

Cursor list

All cursors are stored in a list. Cursors will execute operations in the order they are placed in this list.

Cursors are added to the beginning of the list. This means cursor of the last player (with the biggest id) will be executed first.

Cursor 3 (Player 3)
        |
        V
Cursor 2 (Player 2)
        |
        V
Cursor 1 (Player 1)

That's it for the game initialisation.

Player introduction

Before game start players must be introduced:

Introducing contestants...
* Player 1, weighing 22 bytes, "Batman" ("This city needs me") !
* Player 2, weighing 12 bytes, "Ant-Man" ("So small") !
* Player 3, weighing 28 bytes, "Iron Man" ("Jarvis, check all systems!") !

The battle

Battle rules

One of the most important game variables is cycle counter.

List of cursors is checked every cycle. Vm acts accordingly to the state of cursor - when needed, it assigns a new opcode, sets or decreases wait_cycles, or performs the operation, on which cursor is placed.

The battle continues while at least one cursor is alive

That means a cursor can die. This happens during the check.

The check

The check is performed once in cycles_to_die cycles if cycles_to_die > 0. After it's value becomes less than 1, the check is performed each cycle.

During the check dead cursors are removed from the list.

How do you know that a cursor is dead?

Cursor is considered dead, if it performed operation live more than cycles_to_die or more cycles ago.

Also, if cycles_to_die <= 0 all carriages are considered dead.

In addition to deletion of cursors, value of variable cycles_to_die is modified during the check.

If during last cycles_to_die cycles operation live was performed NBR_LIVE times or more, cycles_to_die is decreased with CYCLE_DELTA.

See op.h for values of constants.

If operation live was performed less than NBR_LIVE times, vm counts how many checks were performed.

If after MAX_CHECKS checks cycles_to_die was not changed, it gets decreased.

Example:

Cycles	live executed, times	cycles_to_die	Current check counter
1536	5	1536	1
3072	193	1536 -> 1486	2
4558	537	1486 -> 1436	1
5994	1277	1436 -> 1386	1
7380	2314	1386 -> 1336	1
8716	3395	1336 -> 1286	1
...	...	...	...

live counter is being reset after each check.

Current check counter includes all checks (current check as well) since cycles_to_die was changed for the last time.

Another example:

Cycles	live executed, times	cycles_to_die	Current check counter
...	...	...	...
24244	41437	136 -> 86	1
24330	25843	86 -> 36	1
24366	10846	36 -> -14	1
24367	186	-14 -> -64	1

This values can be reproduced with the champion Jinx, from vm_champs.tar archive, path: champs/championships/2014/rabid-on/.

Inside the game loop

In each cycle vm checks the whole list of cursors and performs the following (when needed):

Assigns a new opcode

If cursor has moved in the previous cycle, it gets a new opcode.

During the first cycle all the cursors will obtain an opcode.

To get the opcode vm reads the byte from the memory address cursor stands on.

If read value corresponds to a valid operation code, it is saved in cursor.

wait_cycles must be set in this cycle.

Don't read encoding byte and operation arguments, since they can be overwritten during the wait_cycles.

If read value is not a valid operation code, save value and set wait_cycles = 0.

Decrease wait_cycles

If wait_cycles > 0 decrease it by 1.

Important to execute all these operations in right order within a single cycle

• Assign new opcode

• Set wait_cycles

• Decrease wait_cycles by 1

If there was an operation with wait_cycles == 1, it would be executed in the same cycle it was read.

Execute the operation

If wait_cycles == 0 it's time to execute the operation, that is saved in the cursor.

If saved operation code is a valid code and operation requires encoding byte, validate it.

If encoding byte is valid and there are registries among the arguments, validate registry numbers.

If all the checks were successfully passed, execute the operation and move cursor to the next operation.

If operation code is not valid, move cursor to the next byte.

If operation code is valid, but encoding byte is invalid or one of arguments is not valid. Cursor must be moved to the next operation without execution.

To get to the next operation, cursor must skip operation byte, encoding byte (if present), and arguments saved in the encoding byte.

That is why in the operations table there is T_DIR size even for the operations, which don't use this type of argument.

For example, opcode is 0x04:

Opcode	Name	Argument #1	Argument #2	Argument #3
4	add	T_REG	T_REG	T_REG

Encoding byte is invalid and is equal 0xb6, in binary:

Argument #1	Argument #2	Argument #3	—
10	11	01	10
T_DIR	T_IND	T_REG	T_DIR

Operation has only 3 arguments, so we use only three most left pairs of bits.

For this operation we have to skip 9 bytes: opcode (1 byte) + encoding byte (1 byte) + Argument T_DIR (4 bytes) + Argument T_IND (2 bytes) + Argument T_REG (1 byte)

-dump flag

In general, it's all you have to know about the virtual machine.

Last thing to add is -dump flag.

From subject:

-dump nbr_cycles

at the end of nbr_cycles of executions, dump the memory on the standard output and quit the game. The memory must be dumped in the hexadecimal format with 32 octets per line.

the original vm has a similar flag — -d.

Both flags receive number of cycle, after which vm has to print the memory dump, but -d prints dump 64 bytes wide bump, and -dump - 32 bytes wide.