TIS-100 - puzzle about multi-threaded assembler that no one was waiting for

Surprisingly, no one wrote anything about the TIS-100 toy , which recently appeared on Steam (it costs only 150 rubles, already 460 positive reviews against 6 negative).

I’ll make a reservation right away that I don’t have any relation to the authors of the game, but this game itself is a great tool for all programmers who want to fight each other in optimizing code in a fictitious artful assembler.

So what is the game about?

The bottom line is that you are given the task that you need to complete. For example, “read the number from IN.A, compare with the number from IN.B and if IN.A> IN.B, write to the output IN.A-IN.B, otherwise - IN.B-IN.A.

In fact, it is very simple and everyone can master the assembler here. He has two chips.

1. He is terribly minimalistic and therefore inconvenient
2. It is multithreaded. Here, those blocks that you see on the screen - they are all executed simultaneously.

In order to understand what is here and how - here is the very first level:



The task is simple. Read from the entrance, double, write to the exit.

Here is my (most straightforward) solution:



The code in the first block:

MOV UP, ACC       // читаем число из верхнего входа и кладем его в аккумулятор
ADD ACC           // прибавляем к аккумулятору аккумулятор
MOV ACC, DOWN     // отправляем значение аккумулятора вниз

Further, just a number is thrown between the outputs.

We start, the program passes the control test, everything is OK. And we see the result:



Left shows what your decision is regarding other players. We see that by the number of nodes and instructions used, we are the most optimal. But someone solved this problem in fewer cycles. How? Here the second stage of interest is already included - not only to solve the problem, but also to solve it optimally for each of the 3 parameters.

A few words about assembler.

First, the operands. Actually, everything is simple here. These are the expected LEFT, RIGHT, DOWN, UP, ACC. As well as ANY (which reads from any port) and LAST (reads from the last port). There is also NIL for a “garbage” port.

Also, in addition to the battery, there is also a backup (BAK). You cannot work with it directly, only through swaps (see below).

Next is a list of commands.

• NOP - does nothing
• MOV [1], [2] - record from [1] to [2]
• ADD [1] and SUB [1] - add / subtract to the battery [1]
• NEG - inverting the value in the battery
• SWP - exchange battery and BAK values
• SAV - save battery to BAK
• JMP - unconditional jump to the label (labels are indicated as “LABEL:“)
• JEZ (equal zero), JNZ (not zero), JGZ (greater zero), JLZ (less zero) - conditional transitions (the argument of comparison is the battery)
• JRO [1] - relative transition (forward / backward to [1] instructions)

Actually, that’s all. Those. in fact, you have only 1 register (plus 1 spare, which is not so easy to get to) and several teams.

The most inconvenient thing in this assembler is that the comparison for the transition conditions is done on the battery. In “real” assemblers (which I saw), the condition is checked using the flag register, which in turn is set only by a special comparison command, or after an arithmetic operation. Those. you can write like this:

CMP 2
MOV 1, ACC // это на выход
JE LABEL

As a result, we will only go through LABEL if the input parameter was 2, and at the same time we put one in the battery (since operation “MOV” does not change the flag register).

In the TIS-100, this is not so. To do something like this, you have to do this:

SWP // сохраняем значение аккумулятора
MOV 1, ACC // это на выход
SWP // меняем назад
SUB 2
JEZ LABEL

And this despite the fact that we ruined the original value of the battery. If you then have to compare it with another number, we will experience problems.

Actually, this is the whole game. There are tasks, there is just a sandbox.

I think a programmer should be interested. Especially missing hardcore times.