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

## References

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