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 movuscator repo contains an example compiler from brainfuck to mov instructions. The author also wrote a 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