oddurs › fixpoint [ fixpoint.bmp | source ]

fixpoint: an image that boots and computes itself

oddur sigurdsson ·

a picture of its own consequences.

fixpoint.bmp is an ordinary 320×200 bitmap: open it in anything and it’s an image. write it to a disk and boot it, and the cpu draws the same image again, byte for byte, without looking. unzip it and it hands you its own source. the picture is rule 110 running through its ether, disturbed by 130 bytes of code hiding in the top row, and what you’re looking at is that code’s light cone: everywhere its influence has reached so far.

here it is, booting:

opened as an image, then booted in qemu. every frame of the computation is the real screen, paused under gdb every two rows. (mp4, 925K)

if you want to try it:

qemu-system-i386 -drive format=raw,file=fixpoint.bmp
unzip fixpoint.bmp

what you’re looking at

every row is the row above it, run through rule 110, a one-dimensional cellular automaton that is turing-complete. the top row is where it starts: the last 130 pixels are the program, and the 190 before them are rule 110’s ether, a background pattern that repeats every 14 cells and every 7 generations. the ether is the fabric of matthew cook’s proof that rule 110 is universal: his gliders, the moving structures that carry information, travel through it. here, the only thing travelling is the program.

each pixel is a byte, so every cell holds eight rule 110 universes, one per bit. the ether is the same in all eight. the program’s bits differ from universe to universe, so the program is the only thing that can make them disagree, and the palette shows exactly that:

  • where all eight universes agree, the cell is 00 or FF, drawn in two close, quiet shades. this is the woven dark V: the universe exactly as it would have been if the program weren’t there. it hasn’t heard yet.
  • where they disagree, the cell is in the program’s causal future: its light cone. universe 6 decides whether it’s light (coral to gold) or dark (indigo to plum), so its triangles show through, and the other seven set the hue.

every cell the program hasn’t reached is dark, without exception. inside the cone, 0.93% of cells happen to agree anyway, and look dark too. they look untouched. they aren’t.

the cone’s edges move at about 0.63 cells per generation to the right and 0.49 to the left, close to the speeds of rule 110’s two fastest gliders, which cook calls A and B: 2/3 and 1/2. the left cone is the program’s influence leaving the right edge of the screen and coming back on the left, because the screen is one continuous tape. the diagonal stripes in it are glider trains. and the dark corner at the top right is the program’s own last 14 bytes, which are one period of the ether, so the program ends in the fabric it disturbs.

the screen is treated as one tape, 64,000 cells long, folded into rows of 320. a cell’s neighbours are the three cells 320 positions back, so there’s no edge handling, and the whole computation is one loop:

    mov di, 321             ; cell 320 has no left neighbour on the tape; it stays 0
.cell:
    mov al, [di-321]        ; left
    mov ah, [di-320]        ; centre
    mov dl, [di-319]        ; right
    mov bl, ah
    or bl, dl               ; c | r
    and al, ah
    and al, dl              ; l & c & r
    not al
    and al, bl              ; rule 110 = (c | r) & ~(l & c & r), on 8 bits at once
    stosb
    cmp di, 64000
    jb .cell

booting never reads the picture, apart from the 130 pixels that are the program. it doesn’t need the rest. the bootloader loads three sectors: the header, the palette, and the first row of pixels. the program copies itself into the end of row 0, writes one period of the ether at the start and lets it copy itself across the rest of the row, then computes the other 63,680 pixels.

what “fixpoint” means, exactly

the fixed point is the pixel array. the 64,000 bytes an image viewer draws are exactly the 64,000 bytes the program leaves in video memory, and the program is among them. the header and palette are loaded from the file, not computed. and the program finds its own bytes by reading them from memory, which a quine purist would call cheating. they’d be right. this isn’t a quine; it’s a file that contains its own output.

rule 110 being turing-complete is a property of the rule, not a claim about this picture: the seed is whatever bytes the program happens to be, so the universe isn’t computing anything in particular. it just could.

how one file is a picture, a disk, and an archive

Figure 1: the first 512 bytes of fixpoint.bmp, read as bmp headers and a palette, with the path the cpu takes through them and its instructions entry 00, #0a0c16, 9,279 pixels entry 01, #47307b, 144 pixels entry 02, #47307b, 422 pixels entry 03, #54337e, 79 pixels entry 04, #47307b, 403 pixels entry 05, #54337e, 78 pixels entry 06, #54337e, 735 pixels entry 07, #613781, 99 pixels entry 08, #47307b, 52 pixels entry 09, #54337e, 117 pixels entry 0A, #4f00b6, 67 pixels entry 0B, #6a4590, 77 pixels entry 0C, #0001b9, 41 pixels entry 0D, #613763, 101 pixels entry 0E, #613781, 110 pixels entry 0F, #6f3b83, 122 pixels entry 10, #47307b, 427 pixels entry 11, #54337e, 88 pixels entry 12, #54337e, 401 pixels entry 13, #613781, 213 pixels entry 14, #54337e, 54 pixels entry 15, #613781, 89 pixels entry 16, #613781, 1,030 pixels entry 17, #6f3b83, 76 pixels entry 18, #54337e, 78 pixels entry 19, #613781, 130 pixels entry 1A, #613781, 127 pixels entry 1B, #6f3b83, 133 pixels entry 1C, #613781, 92 pixels entry 1D, #6f3b83, 69 pixels entry 1E, #6f3b83, 186 pixels entry 1F, #7c3f86, 170 pixels entry 20, #47307b, 63 pixels entry 21, #54337e, 72 pixels entry 22, #54337e, 203 pixels entry 23, #613781, 68 pixels entry 24, #54337e, 95 pixels entry 25, #613781, 168 pixels entry 26, #8000bb, 44 pixels entry 27, #b002b4, 92 pixels entry 28, #7213cd, 37 pixels entry 29, #4f4590, 105 pixels entry 2A, #613746, 70 pixels entry 2B, #6f3b83, 78 pixels entry 2C, #613781, 59 pixels entry 2D, #6f3b83, 83 pixels entry 2E, #6f3b83, 147 pixels entry 2F, #7c3f86, 217 pixels entry 30, #54337e, 50 pixels entry 31, #613781, 85 pixels entry 32, #613781, 46 pixels entry 33, #6f3b83, 56 pixels entry 34, #613781, 75 pixels entry 35, #6f3b83, 110 pixels entry 36, #6f3b83, 140 pixels entry 37, #7c3f86, 341 pixels entry 38, #613781, 45 pixels entry 39, #6f3b83, 113 pixels entry 3A, #6f3b83, 80 pixels entry 3B, #7c3f86, 116 pixels entry 3C, #0084f4, 37 pixels entry 3D, #7c3f86, 206 pixels entry 3E, #7c3f86, 123 pixels entry 3F, #894289, 343 pixels entry 40, #ff7860, 137 pixels entry 41, #ff8566, 71 pixels entry 42, #ff8566, 104 pixels entry 43, #ff936d, 69 pixels entry 44, #ff8566, 320 pixels entry 45, #ff936d, 93 pixels entry 46, #ff936d, 91 pixels entry 47, #ffa073, 165 pixels entry 48, #ff8566, 64 pixels entry 49, #ff936d, 45 pixels entry 4A, #ff936d, 66 pixels entry 4B, #ffa073, 91 pixels entry 4C, #ff936d, 76 pixels entry 4D, #ffa073, 46 pixels entry 4E, #ffa073, 118 pixels entry 4F, #ffae79, 92 pixels entry 50, #ff8566, 119 pixels entry 51, #ff936d, 96 pixels entry 52, #ff936d, 174 pixels entry 53, #ffa073, 112 pixels entry 54, #ff936d, 118 pixels entry 55, #ffa073, 149 pixels entry 56, #ffa073, 81 pixels entry 57, #ffae79, 130 pixels entry 58, #ff936d, 91 pixels entry 59, #ffa073, 106 pixels entry 5A, #ffa073, 151 pixels entry 5B, #ffae79, 241 pixels entry 5C, #ffa073, 112 pixels entry 5D, #ffae79, 80 pixels entry 5E, #ffae79, 216 pixels entry 5F, #ffbb7f, 178 pixels entry 60, #ff8566, 363 pixels entry 61, #ff936d, 117 pixels entry 62, #ff9380, 63 pixels entry 63, #ffa073, 146 pixels entry 64, #ff936d, 410 pixels entry 65, #ffa073, 138 pixels entry 66, #ffa080, 316 pixels entry 67, #ffae79, 173 pixels entry 68, #ff936d, 66 pixels entry 69, #ffa073, 90 pixels entry 6A, #ffa080, 58 pixels entry 6B, #ffae79, 101 pixels entry 6C, #ffa073, 43 pixels entry 6D, #ffae79, 80 pixels entry 6E, #ffae80, 126 pixels entry 6F, #ffbb7f, 177 pixels entry 70, #ff936d, 105 pixels entry 71, #ffa073, 147 pixels entry 72, #ffaa55, 107 pixels inc dx, bytes 0–0 dec bp, bytes 1–1 jmp short, bytes 2–3 dec dx, bytes 93–93 mov dh, 0, bytes 94–95 dec di; nop; nop; inc bp, bytes 96–99 push byte 0, bytes 100–101 mov cx, 0x0001, bytes 102–104 jmp short, bytes 105–106 mov bx, 0x8000, bytes 206–208 pop es, bytes 209–209 mov ah, 2, bytes 210–211 mov al, 3, bytes 212–213 int 0x13, bytes 214–215 jc read, bytes 216–217 nop; inc bp; dec di, bytes 218–220 jmp short, bytes 221–222 jmp 0x0000:0x84F4, bytes 293–297

point at an instruction or a byte of the path to find the other.open figure 1 on its own, full size

offset as a bmp as a disk
0 BM signature inc dx; dec bp
2 file size: EB 59 01 00 = 88,555 jmp short into the palette
6 reserved, zero
54 256-colour palette the bootloader, woven between colours
446 palette entries 0x62–0x71 the partition table, with legal status bytes
510 palette entry 0x72 55 AA, the boot signature
1,078 pixels row 0: the ether, then the program
65,078 padding, so the size field is true a zip of the source, for unzip

ask file what it is and it says DOS/MBR boot sector, with four partitions, all active. it doesn’t mention the picture.

  • the file size is a jump instruction. its low byte is EB, jmp short, and the next byte is the distance into the palette. the file is padded until the size it claims is true, and the padding holds a zip of main.asm, stub.asm, and build.py, so the file carries its own source.
  • the boot sector is palette colours. the signature 55 AA is the blue and green of entry 0x72, and the four partition status bytes are blue channels, set to 80, one of the two values a status byte may hold, because some bioses refuse a disk whose table holds anything else. all four say active, which a strict reading of the format wouldn’t allow. all five entries have bit 6 set, so they’re already warm colours: the boot sector moves them by at most 30 levels in any channel. the two bytes every bios looks for first are one of the oranges in the cone. they appear 107 times in the picture, if you know where to look.
  • the bootloader is woven into the palette. its 36 bytes would otherwise be 36 wrong colours. build.py runs a dynamic program over instruction orders, alternate encodings, harmless fillers (nop, inc bp, dec di), and jmp short hops over colours it would rather leave alone, and picks the layout whose bytes disturb the picture least: 10 colours shift, about 1% of the pixels. the saturated blue and magenta specks you can find are the bootloader showing through; in figure 1 above, they’re the swatches the traced path runs through. stub.asm writes out every palette entry it hops over, with its colour.
  • it doesn’t care where it starts. until its final far jump, the bootloader uses only relative jumps, so it runs the same whether the bios starts it at 0000:7C00 or 07C0:0000.
  • it stays clear of the bpb. a bios booting a usb stick as a floppy may rewrite bytes 11–61 in memory. nothing executable lives there, and the program reads the palette from a fresh copy off the disk.
  • it retries. a failed disk read loops back to the read, instead of jumping into whatever happened to be in memory.
  • B is inc dx. the bios leaves the boot drive number in dl, so the first thing the bootloader does is dec dx: it puts back what the B took, before it touches anything else in dx.

lineage

files that are several things at once have a long, strange history; ange albertini’s funky file formats is the map. the ether, the gliders, and the proof that they can compute anything are matthew cook’s.

the files

namelast modifiedsizewhat it is
fixpoint.bmp86Kthe image, the disk, the archive
main.asm3Kthe program, 130 bytes of it
stub.asm4Kthe bootloader, woven into the palette
build.py15Klays out the file, places the stub
verify.py8Kchecks every claim, then boots it
demo/record.py7Krecords the video under gdb
demo/figures.py22Kdraws figure 1 from the file
docs/anatomy.svg247Kfigure 1
demo.mp4925Kthe video

last modified
fixpoint.bmp is 88,555 bytes and mit licensed. this page has no javascript and no cookies. it’s set in latin modern.