#!/bin/sed -f

########################################################

## bf.sed ##

## ##

## an optimising compiler for brainfuck ##

## produces x86 Linux ELF binaries ##

## written entirely in sed ##

## ##

## usage: bf.sed file.b > prog; chmod +x prog; ./prog ##

########################################################

# slurp in the entire file

:a;$!N;$!ba;

# remove comments (all characters other than []<>+-.,)

s/[^][,.<>+-]//g;

# add a dodgy ELF header and some startup/initialisation code

# see http://www.muppetlabs.com/~breadbox/software/tiny/teensy.html

# since sed inserts newlines whenever there's a linebreak in the s///

# command, the program start address is moved to 0x080a8000, which

# contains a newline character (0x0a).

s/^/\x7fELF\x01\x01\x01zzzzzzzzz\x02z\x03z\x01zzz\x54\x80\

\x08\x34zzzzzzzzzzz\x34z\x20z\x01zzzzzzz\x01zzzzzzzz\x80\n\x08z\x80\

\x08zz\x01zzz\x01z\x05zzzz\x10zz\xfc\x31\xdb\x31\xd2\x42\xb9\x10\x27zz\x04\

\x29\xcc\x89\xe7\x31\xc0\xf3\xaa\x89\xe1/;

# call exit() at the end of the program. use a direct syscall, it's

# easier than finding libc.

s/$/\xb0\x01\xb3z\xcd\x80/

# the registers used are:

# ecx - current cell

# edx - enable bit (see below)

# eax - scratch

# the memory for the cells is allocated on the stack by the startup code

# above. sed can't count, so it's difficult to get [ and ] (looping)

# right. we can't assemble jumps to the end of the loop, so instead of

# jumping over the loop we set edx to 0 and run the loop's code. all of

# the instructions used do nothing if edx is zero, so this gets the same

# effect as a jump over the loop.

# optimisation: [-] (loop until current cell is zero) is optimised to a

# "mov byte [ecx], 0" instruction

s/\[-\]/\xc6\x01z/g;

# +/- come out to add/sub byte [ecx], dl so they inc or dec when edx = 1,

# and are no-ops when edx = 0

s/[+-]/&\x11/g;

# optimisation: handle <+>, <->, >+< and >-< specially. these sequences

# increment or decrement the next or previous cell, and leave the pointer

# where it is. it's faster to use an addressing mode for this than to move

# the pointer back and forth. e.g. <+> is compiled to "add [ecx - 1], dl".

s/<\([+-]\)\x11>/\1\x51\xff/g;

s/>\([+-]\)\x11</\1\x51\x01/g;

# </> come out as add/sub ecx, edx

s/[<>]/&\xd1/g;

# we optimise sequences of 5 +, -, < or > to perform a single add/sub of

# edx*5. why edx*5? because multiplication by 5 can be done in an

# addressing mode (lea eax, [edx + edx * 4]).

s/\(\([<>]\)\xd1\)\1\1\1\1/5\2\xc1/g;

s/\(\([+-]\)\x11\)\1\1\1\1/5\2\x01/g;

s/5/\x8d\x04\x92/g;

# i/o: , and . invoke the read and write syscalls respectively. due to our

# not-entirely-random choice of registers, most of the arguments are

# already in the right locations. in particular, ecx is the buffer to read

# or write (i.e. points to the current cell), and edx is the length of the

# buffer (so if edx = 0, the system call's a no-op)

s/[,.]/\xb3&\x8d\x43\x03\xcd\x80/g;

# looping. [ saves the current edx, pushes its address to the stack, and

# sets edx to 0 if the current cell is zero. this will run until it hits

# the corresponding ], which will either jump to the pushed address or

# restore the old edx and continue, depending on whether the current cell

# is zero.

s/\[/\x52\x38\x31\x0f\x95\xc2\xe8zzzz/g;

s/\]/\x38\x31\x74\x03\xff\x24\x24\x5a\x5a/g;

# the above was done treating +/-, </> and ,/. identically, by just

# setting up addressing modes and parameters. the next line sets up the

# opcodes to distinguish between add/sub and read/write.

y/+-<>,./z()\x01z\x01/;

# a bug in gnu sed means y/// can't handle ascii NUL, so we use s///

s/z/\x00/g;

# the ELF header at the start must include the length of the

# program. there's no arithmetic in sed, so we can't report this

# accurately. instead, we append 64k of garbage to the program and mark

# its length as 64k. as long as the program's actual size is below 64k,

# the system ignores any data past the end (and it never gets run, because

# exit() is called first). this won't work if you write a brainfuck

# program longer than 64k, but if you do that you're even more nuts than

# me.

p

z

s/.*/aaaaaaaaaaaaaaaa/;

s/.*/&&&&&&&&&&&&&&&&/;

s/.*/&&&&&&&&&&&&&&&&/;

s/.*/&&&&&&&&&&&&&&&&/;