-
Notifications
You must be signed in to change notification settings - Fork 0
Virtual machine
After receiving the Champions bytecode files, it is time for the virtual machine to work.
When starting the corewar program, we specify the .cor champions files as arguments:
$ ./corewar batman.cor ant-man.cor iron_man.cor
By the way, it does not have to be three different files with three different champions. We could start the virtual machine by specifying the same file in the parameters three times. For example, batman.cor.
The program makes absolutely no difference. It distinguishes players not by their names, but by using unique numbers that it assigns to each one of them.
For the VM, three batman.cor are Player 1, Player 2 and Player 3.
The maximum number of champions who can simultaneously fight in memory is monitored by the constant MAX_PLAYERS. In the sample file, it is initialized with the value 4.
That is, no more than 4 players can be loaded into the virtual machine at a time.
The order of players, or rather the order of assigning identification numbers, can be changed using the -n flag.
In the original corewar virtual machine, support for this flag is not implemented, but according to the text of the task, it should be present in our program.
This flag assigns an identification number to the specified champion player. And for those players who did not receive such a number using the flag, the first of the unoccupied numbers will be assigned:
-n numbersets the number of the next player. If non-existent, the player will have the next available number in the order of the parameters.
That is, if you run this command ...:
$ ./corewar batman.cor -n 1 ant-man.cor iron_man.cor
... Ant-Man becomes Player 1, Batman - Player 2, and Iron Man - Player 3.
The only thing to watch out for in this case is the number that appears after the -n. It must be greater than or equal to 1, but not exceed the total number of players who take part in the battle.
Also, this number must be unique within the battle, so several players cannot have the same number.
The virtual machine reads the received champions bytecode files and checks for the presence of a magic header, whether the specified code size matches the real one, and so on.
By the way, if the translator program did not attach value to the maximum size of the executable code, then for the virtual machine this parameter has a value and cannot exceed 682 bytes:
# define MEM_SIZE (4 * 1024)
// ...
# define CHAMP_MAX_SIZE (MEM_SIZE / 6)
The virtual machine does not have a minimum limit on the size of executable code, so it may be completely absent.
After processing the received data of each of the players, the virtual machine should know the following:
- unique identification number
- champion name
- champion comment
- size of executable code in bytes
- executable code
After the program is convinced that everything is fine with the provided files of the players, it is necessary to initialize the arena, where the champions executable codes will be placed.
The size of the arena in bytes is determined by the constant MEM_SIZE, the value of which in the example is 4096.
To understand where the executable code of a particular player will be located, it is necessary to divide the total amount of memory by the number of participants in the battle.
The result will be equal to the amount of memory in bytes, at the beginning of each of which will be located the executable code of the corresponding champion:
4096/3 = 1365
That is, the code of the first player will be located starting from the zero memory cell and beyond. The code of the second is from the 1365th cell. And the third - from the 2730th.
The memory in the virtual machine is organized by the principle of a ring or cycle. That is, the last cell follows the first.
And if the total amount of memory is 4096 cells, then the number of the first cell will be equal to 0, and the last - 4095.
In the case of a cell with a number greater than 4095, the remainder of the division modulo 4096 will be taken as a valid number. Thus, there's no way to go out of the memory limits.
Also, before starting to work, you need to set the value of the following variables:
- player who was last told that he was alive
It is with this variable that the winner of the battle will be announced. This variable is initialized with a pointer to the player with the highest identification number, and is updated in the live statement.
- the number of cycles that have passed since the beginning of the game
- the number of completed
livestatements for the last period, with lengthcycles_to_die -
cycles_to_die- the length of the period before validation
It is initialized with the value of the constant CYCLES_TO_DIE, which is equal to 1536.
- number of checks performed
What is check and what is its role in the statement of a virtual machine will be discussed later.
After the champions executable codes were placed in the arena, a carriage is placed at the beginning of each one of them.
Inside it contains the following data:
- unique carriage number
-
carry:
A flag that some statements may modify. Initially, its value is false.
- The statement code on which the carriage stands:
Prior to the battle, the value of this variable is not set.
- the cycle in which the statement
liveperformed last - the number of cycles remaining until the statement on which the carriage stands
- current carriage position
- the number of bytes that will need to be "crossed" to get to the next statement
- registrys, the number of which is specified in the constant
REG_NUMBER
When the carriage is initialized, the valuesof its registrys are set at the beginning of the game. In
r1will be recorded the identification number of the player on whose code the carriage stands. Only with a minus sign. And all other registrys will be initialized with zeros.
It is important to understand that the carriage does not work for a specific player.
It simply executes the code it appears on. Regardless of who it belongs to.
From the point of view of the visualizer provided, the carriage knows which player it came from. Therefore, if at the beginning of the game it was located on the executable code of the "green" player or if such a carriage gave birth to it, then it will also be written in green using the statements st / sti. Regardless of what color code it is on at the moment.
But from the point of view of the virtual machine, the only moment when the carriage and the player are somehow connected is the beginning of the game. At this moment, the player’s identification number is written in the first carriage registry, only with a minus sign.
Further, during the execution of the fork or lfork statements, the values of all the registrys of the “newborn” carriage will be received from the parent carriage, and not the player.
All carriages form a list. And it is precisely in the order in this list that they will be executed.
Adding new items to the list is done by pasting to the beginning. Therefore, before the start of the battle, the top will be a carriage, which is on the code of the last player (the player with the highest identification number):
Cursor 3 (Player 3)
|
V
Cursor 2 (Player 2)
|
V
Cursor 1 (Player 1)
On this, all the preparatory work can be considered done.
Players must be announced before the battle:
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!")!
#Battle
One of the most important variables in a battle is the number of cycles that have passed since the start.
The entire list of carriages is scanned during each cycle. Depending on the state of the carriage, certain actions are performed - a new statement code is set, the number of cycles before execution is reduced, or the statement itself, on which the carriage stands, is performed.
The battle continues as long as at least one living carriage remains.
That is, the carriage can die or someone can kill it?
Yes, the carriage may die. This happens during an event such as check.
A check occurs every cycles_to_die cycles while the value of cycles_to_die is greater than zero. And after its value becomes less than or equal to zero, the check begins to be carried out after each cycle.
During this check, carriages that are dead are removed from the list.
How to determine if a carriage is dead?
A carriage that performed the statement live cycles_to_die cycles back or more is considered dead.
Also, any carriage is considered dead if cycles_to_die <= 0.
In addition to deleting carriages during the check, the value of cycles_to_die is modified.
If the number of live statements performed during cycles_to_die period is greater than or equal to NBR_LIVE, the value of cycles_to_die is reduced by CYCLE_DELTA.
The value of the NBR_LIVE constant in the provided file is 21, and the value of CYCLE_DELTA is 50.
If the number of live statements performed is less than the set limit, then the virtual machine simply remembers that the check was performed.
If the MAX_CHECKS of checks after the value of cycles_to_die does not change, then it will be forcibly reduced by the value of CYCLE_DELTA.
The value of MAX_CHECKS in the example file op.h is equal to 10.
To better understand when a check occurs and what it changes, consider an example:
| Cycles | Number of statements live
|
cycles_to_die |
Current number of checks |
|---|---|---|---|
| 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 |
| ... | ... | ... | ... |
The number of
livestatements is reset after each check, regardless of its results.
"Current number of checks" includes the ongoing check.
It will also be useful to consider another battle scenario. Only in this case we are only interested in the latest battle cycles:
| Cycles | Number of statements live
|
cycles_to_die |
Current number of checks |
|---|---|---|---|
| ... | ... | ... | ... |
| 24244 | 41437 | 136 -> 86 | 1 |
| 24330 | 25843 | 86 -> 36 | 1 |
| 24366 | 10846 | 36 -> -14 | 1 |
| 24367 | 186 | -14 -> -64 | 1 |
Such data can be obtained during the execution of the Jinx champion, which is located in the
vm_champs.tararchive along the pathchamps/championships/2014/rabid-on/.
Now let's take a closer look at what happens inside the cycle.
In each cycle, the virtual machine scans the list of carriages and performs the necessary actions on each of them:
If during the last cycle the carriage moved, then it is necessary to establish on the code of what statement it is now.
By the way, a variable storing the number of cycles until the statement is executed can indicate that the carriage was moving on the previous execution cycle. If its value is zero, then the movement took place and the carriage needs to set the code of the statement on which it now appeared.
During the very first execution cycle, all carriages will receive statement code value. That's because it is not installed during initialization.
To find out the statement code, it is necessary to read the byte on which the carriage is located.
If the received number corresponds to the code of the real statement, then it must be remembered.
You also need to set the value of a variable that stores the number of cycles until the statement is completed.
No other statement data (argument type code, arguments) need to be read and stored. They must be received at the time of the statement.
If you remember them earlier, the virtual machine will not work correctly. Indeed, during the waiting time, the corresponding cells in the memory can be overwritten with new values.
What if the read number does not fall into the range [0x01; 0x10], that is, the received code indicates a non-existent statement? What to do in this situation?
In this case, it is necessary to remember the read code, and leave the value of the variable storing the number of cycles before execution equal to zero.
If the number of cycles before execution is greater than zero, it must be reduced by 1.
It is important that during the cycle all the checks and actions described are carried out strictly in the specified sequence.
Thats because in one cycle a carriage can receive a new statement code, set the number of cycles before its execution and also reduce this amount by one.
If there was a statement with only one wait cycle, then it would also be performed during this one cycle.
If the number of cycles before execution is zero, then it is time to perform the statement whose code the carriage stores.
If the stored code corresponds to an existing statement, then it is necessary to check the validity of the code containing the types of arguments.
If this code is correct and indicates that there is a registry among the statement arguments, you must also verify that the registry number is correct.
If all the necessary checks have been successfully completed, you need to perform the statement and move the carriage to the next position.
If the statement code is wrong, you just need to move the carriage to the next byte.
If everything is normal with the code itself, but the argument type code or the registry number is incorrect, you must skip this statement together with the argument type code and the arguments themselves.
Everything is easy with skipping the incorrect statement code: you just need to move to the next byte. Moving after the statement is completed is still clear: the types of arguments are known, and their sizes too. However, in the case of an incorrect argument type code, one question arises: "How to skip statement arguments if the argument type code is incorrect?"
You need to skip the statement code, the type code of the arguments, as well as the arguments specified in the type code.
That is why the sizes of the
T_DIRarguments were indicated in the statement table even for those statements that do not accept such arguments.
Let's say our statement code is 0x04:
| Statement Code | Statement Name | Argument # 1 | Argument # 2 | Argument # 3 |
|---|---|---|---|---|
| 4 | add |
T_REG |
T_REG |
T_REG |
The value of the byte containing the argument types is 0xb6:
| Argument # 1 | Argument # 2 | Argument # 3 | - |
|---|---|---|---|
10 |
11 |
01 |
10 |
T_DIR |
T_IND |
T_REG |
T_DIR |
Since this statement takes three arguments, we consider the values of only the first three pairs of bits in the type code. The values of the remaining pairs do not interest us.
After a short calculation, we find out that in this situation the following 9 bytes must be skipped: statement code (1 byte) + byte with types (1 byte) + Argument of type T_DIR (4 bytes) + Argument of type T_IND (2 bytes) + An argument of type T_REG (1 byte).
In general, this is all you need to know about the work of the virtual machine. But there is another important flag that can stop the operation. This is the -dump flag.
Its work is described in the text of the subject:
-dump nbr_cyclesat the end of
nbr_cyclesof 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.
An analogue of this flag is also present in the original virtual machine. Only under a different name - -d.
Both flags receive a cycle number, after which it is necessary to display the memory status on the screen and stop the program corewar. But the display modes of the arena content for these two flags are slightly different.
The -d flag prints 64 octets in a row. And the -dump flag only 32 octets.