Mov

Mov is an x86 assembly instruction identified to be Turing-complete by Stephen Dolan in mov is Turing-complete [1] and developed further by xoreaxeaxeax in Movfuscator [2]. It may also be considered the basis of a one instruction set computer archtecture which (unlike Subleq) does not have to use self modifying code.

About the Mov instruction

The mov instruction has a number of different forms. Let r1,r2 denote registers, then for example:

• mov r1, 42  % store the number 42 in r1
• mov r1, r2  % fetch the value in r2 and store it in r1
• mov [r1], 42  % store the number 42 in the address the register r1 points to
• mov r1, [r2]  % fetch the value the address in register r2 points to and store it in r1
• mov [r1], r2  % store the value register r2 in the address the register r1 points to

The expressions in brackets can also include +offsets or even adding two register together. All of these features are made use of in different encodings.

Equality Test

To test equality of 'x' and 'y':

  mov [x], 0
  mov [y], 1
  mov result, [x]

This works by having a large array which is written into and read back out from. If x = y the readback will give 1 and it would be 0 otherwise.

Arithmetic and Logic

Arithmetic and logic gates can be encoded using lookup tables. For example to find the xor of x and y we have the following lookup tables

  xor_xy: dd xor_0y, xor_1y
  xor_0y: dd 0, 1
  xor_1y: dd 1, 0

and the code is

  mov r1,[xor_xy+x]
  mov r2,[y]
  mov result,[r1+r2]

As a compilation target

The movfuscator repo contains an example compiler from brainfuck to mov instructions. The author also wrote an lcc (C compiler) backend for it. The result is extremely long linear code with no branches which can cause reverse engineering tools to crash.

References

• [1] mov is Turing-complete - Stephen Dolan (from the Wayback Machine; retrieved on 31 March 2019)
• [2] movfuscator