Imp is the simplest example of a Redcode program that is able to relocate itself in the memory array. It copies the contents of relative address 0 (namely the Imp) to relative address 1, the next address. As the program is executed it moves through the array at a speed of one address per cycle, leaving behind a trail of Imps.”
Dewdney, A. K. Scientific American May 1984.
An imp is a mobile program which copies itself just ahead of its own
instruction pointer. Modern imps often run multiple processes in a ring or spiral pattern and
are usually paired with paper or stone. The
simplest imp (MOV 0,1) was inspired by a
PDP-11 instruction which propagates
itself down thorough memory:
014747: MOV -(PC),-(PC) ; MACRO-11 assembly language
Classic Imp
The classic imp is a single instruction which copies itself one address ahead to create a new imp. Each new imp executes in turn and if left unhindered will eventually fill the entire memory with a trail of imps. A K Dewdney introduced the imp in 1984.
imp mov.i #0, imp+1
Mirrored Imp
A mirrored imp is a pair of imps positioned CORESIZE/2
cells apart. Each imp copies itself just ahead of the next instruction to
execute. The first mirrored imp was demonstrated by Jonathan Roy in May 1992.
dist equ 4000 ; CORESIZE/2
istep equ 4001 ; CORESIZE/2+1
launch mov imp, imp+dist
spl imp+dist
imp mov.i #0, istep
Imp Ring
An imp ring is a multi-process imp with the processes spaced evenly in memory. Each imp copies itself over the next instruction to execute. Extra processes can be added to an imp ring to form a spiral. Anders Ivner published the first imp ring in October 1992.
istep equ 2667 ; (CORESIZE+1)/3
launch spl istep+1
mov launch, launch+istep+1
imp mov.i #0, istep
Vector Launch
A vector launch creates a number of parallel processes then launches them using a jump table. Launching x processes takes approximately 2x−1 cycles and x/2+log₂x+1 instructions. Ting-Yu Hsu developed the modern vector launch in May 1994.
istep equ 2667 ; (CORESIZE+1)/3
spl 1 ; 4 parallel processes
spl 1
spl vector, }0
jmp @vector, }0
vector jmp imp+istep*1,imp+istep*0
jmp imp+istep*3,imp+istep*2
jmp imp+istep*5,imp+istep*4
jmp imp+istep*7,imp+istep*6
imp mov.i #0, istep
Binary Launch
The code for a binary launch is structured like a perfect binary tree.
SPL is a branch node which sends a process to two child nodes.
JMP is a leaf node which launches a process.
Launching x processes takes approximately 2x−1 cycles and
2x−1 instructions. The first binary launch was created by Paul Kline
in October 1992.
istep equ 2667 ; (CORESIZE+1)/3
spl 8
spl 4
spl 2
jmp imp+istep*0
jmp imp+istep*1
spl 2
jmp imp+istep*2
jmp imp+istep*3
spl 4
spl 2
jmp imp+istep*4
jmp imp+istep*5
spl 2
jmp imp+istep*6
jmp imp+istep*7
imp mov.i #0, istep
JMP/ADD Launch
A JMP/ADD or Nimbus launch creates a
number of parallel processes then launches them via a JMP
whose destination is updated after every jump.
Launching x processes takes approximately 5x−1 cycles and
log₂x+3 instructions. Alex MacAulay published the first
JMP/ADD launch in October 1992.
istep equ 2667 ; (CORESIZE+1)/3
spl 1 ; 8 parallel processes
spl 1
spl 1
spl 2
launch jmp imp
add.a #istep, launch
; dat ?, ?
imp mov.i #0, istep
Impfinity Launch
The Impfinity launch is a self-splitting imp pump that builds and continuously adds new processes to an imp spiral. The Impfinity launch was developed by Damien Doligez in November 1996.
istep equ 2667 ; (CORESIZE+1)/3
spl #0, >prime
prime mov imp, imp
add.a #istep+1, launch
launch jmp imp-istep-1
imp mov.i #0, istep
Vortex Launch
The Vortex launch uses x parallel processes in a self-splitting imp pump to build and continuously add processes to x interleaved continuous imp spirals. The first example of a vortex launch was written by John K Wilkinson in January 1996.
istep equ 2667 ; (CORESIZE+1)/3
spl 1 ; 4 parallel processes
spl 1
spl #0
add.a #istep, launch
launch jmp imp-istep*4
imp mov.i #0, istep
Amber Launch
The Amber launch is a self-splitting mirrored imp pump which continuously adds new processes to the imp. The Amber launcher was first used by Inversed in February 2006.
dist equ 4000 ; CORESIZE/2
istep equ 4001 ; CORESIZE/2+1
mov imp, imp+dist
spl #0, }launch1
spl launch2, }launch2
launch1 jmp imp-2, }launch2
launch2 jmp imp+dist-2, }launch1
imp mov.i #0, istep
A-Field vs B-Field
Imps are classed as either a-field or b-field depending which field holds the step. The performance of each variety varies by opponent as most anti-imp strategies are tailored against one kind or the other. Mike Nonemacher published the first a-field imp in September 1994.
impa mov.i #istep, *0 ; a-field imp
impb mov.i #0, istep ; b-field imp
Imp Steps
An imp ring is defined by an imp pair: the number of points where the imp is running and the imp step required to space the points evenly. The number of points should be relatively prime to the size of core and points × impstep ≡ 1 (mod coresize). Imp steps can be calculated using the modular inverse impstep = points ^ -1.
Most imp rings use a fairly small number of points. The first few imp pairs for the most common coresizes are as follows:
| Points | 8000 | 8192 | 55440 |
|---|---|---|---|
| 3 | 2667 | 2731 | |
| 5 | 3277 | ||
| 7 | 1143 | 3511 | |
| 9 | 889 | 3641 | |
| 11 | 5091 | 2979 | |
| 13 | 3077 | 3781 | 34117 |
| 15 | 3823 | ||
| 17 | 2353 | 4337 | 35873 |
| 19 | 7579 | 2587 | 29179 |
| 21 | 381 | 3901 | |
| 23 | 2087 | 6055 | 38567 |
Further Reading
- . "Imps." Core Warrior 29 (13 May 1996).
- . "The Mathematics of Imp Steps." Core Warrior 8 (4 Dec 1995).
- . "Vector Launched Imps." The '94 Warrior 12 (18 Aug 1994).
- . "Imp Launchers & The Hybrid Launcher." Core Warrior 91 (30 Jan 2005).
- . "Imp-Rings." My First Corewar Book. Self-published, 1994.
- "HINTS and HELPS." The '94 Warrior 2 (17 Feb 1994).
- "Mirrored Imps." Core Warrior 37 (8 Jul 1996).