Instantly share code, notes, and snippets.

# TIS-100's "Unconditional": solve SIGNAL COMPARATOR without conditional jumps

I did it, somehow. I'm writing these notes to save somewhere how that thing work.

# Why?

I looked at the achievements, and it looked cool.

Solve SIGNAL COMPARATOR without using the JGZ, JLZ, JEZ, or JNZ instructions.

The problem is the first example of conditional jumps in the game, so... why not? Let's do this, then!

# The first bit: JRO instruction

When in doubt, read the Manual.
Fortunately, the TIS-100 has a very small instruction set, and a good manual. One of the instructions captured me: `JRO`.

As defined in the manual, `JRO <value>` jumps at the `<value>` instruction before or after the JRO instruction. If the parameter is negative, it would make the node jump `value` instructions before, if positive it'd jump ahead.

If you see the screenshot, you'll see it's used a lot.

# The spark: reduce input size for last nodes

No conditionals and a fixed set of instructions per node(!) means I need a straightforward way to jump to the right instruction.

JRO is a powerful instruction, but you have to check what you feed it with: handling 5 different values was easy in the naive solution (using jgz, jez or jlz), but now we need to make the "program counter" jump to the right instruction. Make it simple and assume you'll always get normalized values: {-1, 0, 1}.

So, let's start explaining the code inside the 3 right-most blocks

# The output nodes' code

Let's explain the code inside Block 6 - the one with a downward arrow and "OUT.G" written below it-.

``````START:
MOV LEFT, ACC    # Save the received value (-1, 0, 1)
MOV ACC, RIGHT   # and pass it to the next node
JRO ACC          # Let's jump somewhere... (-1, 0, 1) => (1, 2, 3)
JMP JUMPZERO     # -1 > 0 is false, so we jump and write zero on the output
JMP JUMPZERO     # 0 > 0 is false, so we jump and write zero
JMP JUMPONE      # 1 > 0 is true, so we jump and write one!
JUMPZERO:
MOV 0, DOWN      # write 0 on OUT.G
JMP START        # ... and to back to the top, ready to read a new value!
JUMPONE:
MOV 1, DOWN      # write 1 on OUT.G
JMP START        # ... and go back to the top
``````

Let's think of that as a function OUT.G : {-1, 0, 1} => {0, 1}. As we set the domain of OUT.G (the set of parameters), we perform a trick: add 2 to the parameter. It will let us use JRO to jump to the correct instruction:

• -1 => 1 => JMP JUMPZERO => write 0 on the output port
• 0 => 2 => JMP JUMPZERO => write 0 on the output port
• 1 => 3 => JMP JUMPONE => write 1 on the output port

After a jump, everything is simple and easy again. For the other nodes, you can just copy-paste the OUT.G implementation and modify the jumps to make it generate the right values.

# The input nodes

So... the output part is now done. How do we constrain, normalize the input? Fortunately, the program will only use values between -2 and 2, so it's possible, even if it is not very easy.

Before reading/commenting the code, I want to do a mathematical-like explanation.
We can consider the three nodes as three functions that operate "on cascade", composed. The output of the Result function is what feeds the output nodes, is the constrained input.

``````UpperNode: {-2, -1, 0, 1, 2} -> {-5, -4, -3, 0}
MiddleNode: {-5, -4, -3, 0} -> {-2, -1, 0, 1}
LowerNode: {-2, -1, 0, 1} -> {-1, 0, 1}

Result: {-2, -1, 0, 1, 2} -> {-1, 0, 1}
Result: LowerNode(MiddleNode(UpperNode(IN)))
``````

Each function (UpperNode, MiddleNode and LowerNode) takes the input, perform a sum (ADD) or a subtraction (SUB) operation on it and then use `JRO` to double-jump to the right operation set and move on to the next input.

UpperNode does something like that:

``````let UpperNode(IN) = match (IN-3) with
-5 -> -5,
-4 -> -4,
-3 -> -3,
-2 ->  0,
-1 ->  0
``````

Essentially, it compresses the values 1 and 2 inside a single value, 0. The co-domain chosen for this will be clear in a moment:

``````JMP COPY             # At start, jump to COPY
JMP SENDD # IN=-2
JMP SENDD # IN=-1
JMP SENDD # IN=0
JMP SEND1 # IN=1
JMP SEND1 # IN=2
TEST: JRO ACC        # Jump backwards ACC instructions
COPY: MOV UP, ACC    # Save the input inside the ACC register
SUB 3                # Subtract 3 from ACC
SEND1: MOV 0,DOWN    # 1, 2 are reduced to 0 here
JMP COPY             # go back to start, ready to ready a new input
SENDD: #SEND DOWN    # zero or negative: send them as calculated (-5, -4, -3)
MOV ACC, DOWN        # zero or negative: send them as calculated (-5, -4, -3)
JMP COPY             # go back to start
``````

We need the co-domain to contain -5, -4 and -3 because these are the offset for the zero-and-negative jumps. As said before, there is a limit on the instructions that a node can contain, so we are forced to push these values down by the game.

That's not a problem, though, MiddleNode is perfectly capable of handling these values... with a bit of clever trickery.

``````let MiddleNode(IN) = match (IN+2) with
-3 -> -2
-2 -> -1
-1 -> 0
2 -> 1
``````

MiddleNode is the function responsible for creating a real "zero" value in the co-domain and let LowerNode to compress the negative values. To make it possible to use JRO in this case and stay in the instruction limit, this time we need to ADD 2 to the node input.

``````JMP COPY
JMP SENDN             # IN = -5, the offset is -3
JMP SENDN             # IN = -4, the offset is -2
JMP SEND0             # IN = -3, the offset is -1
NOP # NO ZERO!        # BEWARE! no -1 to be transmuted into 1, so we don't perform any op here!
MOV 1, DOWN           # IN = 0, the offset is 2. Send 1 to LowerNode. trickery trick.
COPY: MOV UP, ACC     # Save the input inside the ACC register
ADD 2                 # Add 2 to ACC, to perform the JRO/offset trickery
SEND0: MOV 0, DOWN    # Recognize the real zero and send it to LowerNode
JMP COPY              # Go back to start
SENDN: ADD 1          # Perform some pre-normalization before sending negative values to LowerNode
MOV ACC, DOWN         # Send the negative values to LowerNode (-2, -1)
JMP COPY              # Go back to start
``````

Now, it's the time to read the last and the easiest function in the triple: LowerNode.

``````let LowerNode(IN) = match (IN-2) with
-4 -> -1
-3 -> -1
-2 -> 0
-1 -> 1
``````

LowerNode is the function that, finally, compresses the negative values to -1.

``````JMP COPY
JMP SENDN           # IN = -2, the offset is -4
JMP SENDN           # IN = -1, the offset is -3
JMP SEND0           # IN =  0, the offset is -2
JMP SEND1           # IN =  1, the offset is -1
COPY: MOV UP, ACC   # Save the input inside the ACC register
SUB 2               # Subtract 2 to perform the offset calculatio
SEND1: MOV 1,RIGHT  # the original IN is positive => send 1 to the output nodes
JMP COPY
SEND0: MOV 0,RIGHT  # the original IN is zero => send 0 to the output nodes
JMP COPY
SENDN:MOV -1,RIGHT  # the original IN is negative => send -1 to the output nodes
JMP COPY
``````

# Conclusions

I don't want to claim it is an original/novel solution to the problem: I'm sure that lots of players did that too, and maybe there are more efficient solutions out there, already published on the internet. The only thing I want to say here is that I solved the problem, and have explained how.