Challenge: Unconditionally Conditional

A fun idea came to me a while back: using x86 assembly, could I implement a basic if/else statement that runs arbitrary code without using any conditional instructions? If you care to try out the challenge, I'd recommend using a language that provides low level memory access and then taking a quick break from reading further.

Determining Inequality

The first part of the problem that we need to consider is this: is there any way to tell that whether two values are equal without using the conditional operator? A fair place to start would be with some basic mathematical identities. According to the additive inverse identity, n + (-n) = 0. More simply, n - n = 0. From this we can get that n - m = 0 if and only if n = m.

Using this to solve our problem at hand, we can say that by using x = n - m, we can determine that x will be zero only when n and m are equal. Otherwise if n is greater than m, x will be positive. Lastly, if m is greater than n, x will be negative. This last detail plays to our advantage. When storing our values, the computer uses the left-most bit to represent a value's signedness. If the value is negative, then the bit will be one, otherwise it will be zero.

With this in mind, we can deduce the following: given two numbers, m and n, one and only one of the following will be true:

• The left-most bit of x is 1, given that x = n - m. (m > n)
• The left-most bit of y is 1, given that y = m - n. (m < n)
• The left-most bit of x and y is 0, given the above x and y. (m == n)

Taking this one final step, we can conclude that the left most bit of ((n - m) | (m - n)) will be zero if-and-only-if m and n are equal, and will be one otherwise. ¹ Since the original challenge was assembly, we'll assume that the registers rax, and rbx are the two value we want to compare. ² That gives us the following assembly.

mov rcx,rax ; rcx=rax-rbx
sub rcx,rbx ;

mov rdx,rbx ; rdx=rbx-rax
sub rdx,rax ;

or rcx,rdx ; rcx = rcx | rdx (Logical Or)

Rather than having to look at the last bit, we can constrain our value to zero or one by rotating all of the bits to the left, so that the least significant bit is our target, and then by performing a bitwise-and with one, effectively dropping all other bits.

rol rcx,1 ; Rotate cx left, rotating the sign-bit to the right-most spot
and rcx,1 ; cx = cx & 0x01 (Logical And)

This leaves us in a position where rcx is zero if rax and rbx are equal and one if they are not.

Jumping Based on Inequality

We're going to need some form of flow control but since we can't use any instructions with a conditional behavior, we're going to have to ruled out CMP and the majority of the Jcc family of instructions. The only instructions left that are capable of performing flow control are JMP, RET, CALL, INT, and IRET. Generating an interrupt is not likely to help us get closer to our goal, so we can ignore INT and IRET for now. Additionally, the functionality of CALL and RET can be simulated by using a JMP with a PUSH or POP respectively, so the most logical place to start would be with examination of JMP.

If you're familiar with BASIC, you can think of JMP as a close kin of GOTO. JMP takes one argument that tells it where to place the instruction pointer. With this ability and the register representing inequality created in the previous section, we are actually in a good position to be able to accomplish our task. If we know the addresses of the instructions that we want to jump to and the value of our inequality register we could engineer a register containing the correct jmp address. If we use JMPs for our target instructions, we could use our knowledge of JMP and its instruction length to make a register based jmp land on one of our two targets. Given the code:

jmp rcx ; 
jmp equalbranch ; 
jmp unequalbranch ;

The length of a jmp is two instructions, so if we can make sure that rcx is the current instruction pointer plus two then the result of the first jmp will be that we land on “jmp branch1”. If we can ensure that rcx contains four then the jmp will land us on “jmp branch2”. This is actually quite achievable with only a few actions.

At this point we should be able to find a pattern between what is in rcx and what we need our target address to be: when rcx is zero we want our target to be two instructions past ‘here’, and when it is one, we want it to be four past. We can use a few simple transformations to turn rcx into our target. First, we'll double the contents of rcx to be zero or two so that it fits our instruction boundaries. After that, we'll add an offset to make rcx point at the right location.

rol rcx,1 ; Multiply by two so that rcx either 0 or 2. (Via bit-shifting)

add rcx,$+9 ; Make rcx either 9 or 11 bytes after this instruction
jmp rcx ; Jump to the specified instruction
jmp branch1 ; 9 bytes later
jmp branch2 ; 11 bytes later

If you've followed along so far, it probably feels like the add instruction came out of nowhere. It is part of our transformation though: the dollar-sign refers ‘the current location of the instruction pointer’. Also, since we placed an add instruction in between our calculation of ‘here’ and the JMPs, we had to compensate by making our offset nine rather than two to compensate for the extra instructions.

Final Solution

In order to actually show this off, well modify a basic hello world to show off our functionality. ³

; nasm -f elf64 iffy.asm
; ld -s -o iffy iffy.o
section .text
  global _start     ;must be declared for linker (ld)

_start:         ;tell linker entry point

  ; We want to perform the equivilent of cmp rax,rbx; jeq branch1 jne branch2
  mov rax,42 ; Actual value
  mov rbx,42 ; Expected value

  mov rcx,rax ; cx=ax-bx
  sub rcx,rbx ;

  mov rdx,rbx ; dx=bx-ax
  sub rdx,rax ;

  or rcx,rdx ; cx = cx | dx (Logical Or)
  rol rcx,1 ; Rotate the sign-bit to the right-most spot
  and rcx,1 ; cx = cx & 0x01 (Logical And)

  rol rcx,1 ; Multiply by two so that its either 0 or 2.

  add rcx,$+9 ; Make rcx either 9 or 11 bytes after this instruction
  jmp rcx ; Jump to the specified instruction
  jmp branch1 ; 9 bytes later
  jmp branch2 ; 11 bytes later

branch1:
  mov edx,len ;message length
  mov ecx,msg ;message to write
  mov ebx,1 ;file descriptor (stdout)
  mov eax,4 ;system call number (sys_write)
  int 0x80  ;call kernel

branch2:
  mov eax,1 ;system call number (sys_exit)
  int 0x80  ;call kernel

section .data

  msg db  'Values are equal!',0xa ;our dear string
  len equ $ - msg     ;length of our dear string        

With this, we've completed the challenge of simulating an if-else without using any conditional instruction. And, if nothing else, gained a greater appreciation for the ability to use comparisons.

Footnotes