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.
Contents
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.
