Return to Answer

X86_64/Linux Machine Code, 104 101 100 99 98 97 96 95 93 92 91

• Size is measured in machine code (i.e 91 bytes of PROGBITS; .text, .data, etc...)
• -9 bytes if reads input prog from stdin
• -4 more bytes without BF_EXITCLEANLY (it will segfault to exit).
• -2 more bytes with BF_BALANCED (assumes that over course of program data cell returns to start).
• So minimum possible size 76 bytes.
• NOTE Without the ideal bss setup (at address 0x7ffe0000 and BF_IDEAL_BSS defined as seen in compile command above) add +2 bytes.

#define BF_LBRACE   91
#define BF_RBRACE   93

#define BF_DOT  46
#define BF_COMMA    44

#define BF_PLUS 43
#define BF_MINUS    45

#define BF_LSHIFT   60
#define BF_RSHIFT   62

#define BF_READFILE
#define BF_EXITCLEANLY
    // #define BF_IDEAL_BSS
    // #define BF_BALANCED


    .global _start
    .text
_start:
    /* All incoming registers at zero.  */

    /* Large read range. This may cause errors for huge programs
       (which will fail anyways).  */
    decl    %edx
#ifdef BF_READFILE
    /* open.  */
    movb    $2, %al
    /* 3rd argument in rsp is first commandline argument.  */
    pop %rdi
    pop %rdi
    pop %rdi
    /* O_RDONLY is zero.  */
    syscall
    /* Error is okay, we will eventually just exit w.o executing.  */
    xchgl   %eax, %edi

    /* Sets ESI at 2 ** 31. This is an arbitrary address > 65536
       (minimum deref address on linux) < 2 ** 32 - PROG_SPACE
       (PROG_SPACE ~= 262144). We setup bss at 2 ** 31 - 131072 via
       linker script (-Tbss=0x7ffe0000).  */
# ifdef BF_IDEAL_BSS
    bts %edx, %esi
# else
    movl    $(G_mem + 65536), %esi
# endif
    /* bss initialized memory is zero. This is cheapest way to zero
       out eax.  */
    lodsl
#else
# ifdef BF_IDEAL_BSS
    bts %edx, %esi
# else
    movl    $(G_mem + 65536), %esi
# endif
#endif

    /* eax/edi are already zero which happens to match
       SYS_read/STDIN_FILENO.  */
    syscall


    /* Stack of braces grows down from below the program code.  */
    movl    %esi, %esp
    /* Program code grows up.  */
    movl    %esi, %ebx
    /* Assuming no errors, reach stores size in eax. Note errors or
       0-byte reads are okay. The ebx is readable memory and zero-
       initialized (bss), so it its zero-length, it will just be an
       invalid op and we will hit bounds check below. If its error,
       eax is negative so ebx will be negative and likewise we will
       hit bounds check below.  */
    addl    %eax, %esi
#ifndef BF_BALANCED
    movl    %esi, %ebp
#endif

    /* We have -1 in edx, so negative to get 1. 1 is needed in a
       variety of places.  */
    negl    %edx
run_program:
    /* Need to zero eax.  */
    movzbl  (%rbx), %eax
    incl    %ebx
    /* %al contains the program "instruction". Its unique to one of
       8 values so just test each in order. If instruction matches
       execute it then fallthrough (%al can only ever match one).
       We occasionally set al but are sure never to set it to the
       ASCII value of any of our 8 instructions.  */

    /* TODO: Brace handling could probably be smaller.  */
try_lbrace:
    cmpb    $BF_LBRACE, %al
    je  do_brace
try_rbrace:
    cmpb    $BF_RBRACE, %al
    jne try_cont
    /* Popping state (we might repush if we are looping back).  */
    pop %rdx
    pop %rdi
    /* Non-zero cell means loop. Note we have 1 cached in edx.  */
    cmpb    %dl, (%rsi)
    jb  next_insn
    movl    %edi, %ebx
do_brace:
    /* Restore loop state.  */

    push    %rbx
    push    %rdx

    /* If cell is zero, then we are skipping till RBRACE. Note we
       have 1 cached in edx.  */
    cmpb    %dl, (%rsi)
    /* -1 if we want to start skipping.  */
    sbb %dh, %dh
try_cont:
    orb %dh, %al
    /* we have set ah s.t its either zero or has a value that makes
       any further matches impossible.  */

    /* For the rest of the ops we take advantage of the fact that
       the ascii values of the pairs '<'/'>', '+'/'-', and '.',','
       are all 2 apart. This allows use to test a pair with the
       following formula: `((al - PAIR_LO) & -3) == 0`. This will
       always leave the pair as 0/2 and will match only the pair.
       It turns out 0/2 are useful and can be used to do all the
       rest of the operations w.o extra branches.  */

try_lshift:
    subb    $BF_LSHIFT, %al
    testb   $-3, %al
    jnz try_comma
    addl    %eax, %esi
    decl    %esi
try_comma:
try_dot:
    subb    $(BF_PLUS - BF_LSHIFT), %al

    /* We have 0/1/2/3 for '+'/','/'-'/'.' so check if we remaining
       valid opcode.  */
    cmpb    $3, %al
    ja  next_insn

    /* 0/2 are '+'/'-' so check low bits. TODO: There may be a way
       to just care from `shr $1, %al' which would save us an
       instruction. But it messes up the '+'/'-' case.  */
    testb   $-3, %al
    jz  try_minus

    /* al is either 3/1. Shift by 1 to get 1/0 for our syscall number.  */
    shrb    $1, %al

    // btsq    $, %rax
    /* SYS_write == STDOUT_FILENO, SYS_read == STDIN_FILENO.  */
    movl    %eax, %edi
    /* We already have 1 in rdx.  */
    syscall
    /* Assuming no io error, eax is 1. We will subtract 1 from eax
       in try_minus/try_plus so it will be +/- 0 which does
       nothing.  */
try_minus:
try_plus:
    /* If not coming from syscall eax is 0/2. 0 --> plus, 2 -->
       minus. So (rsi - eax + 1) translates.  */
    // setbe   %cl
    
    subb    %al, (%rsi)
    incb    (%rsi)

next_insn:
#ifdef BF_BALANCED
    /* If BF_BALANCED is set, we assume that the program will have
       shifted back columns to start before exiting.  */
    cmpl    %ebx, %esi
#else
    cmpl    %ebx, %ebp
#endif
    jg  run_program

#ifdef BF_EXITCLEANLY
    /* eax has zero upper 24 bits so we can cheat and use movb here.
       (This isn't exact correct, assuming no IO errors on last
       instruction).  */
    movb    $60, %al
    syscall
#endif

    .section .bss
    .align  32
G_mem:  .space(65536 * 4)

X86_64/Linux Machine Code, 104 101 100 99 98 97 96 95 93 92 91 89

• Size is measured in machine code (i.e 89 bytes of PROGBITS; .text, .data, etc...)
• -9 bytes if reads input prog from stdin
• -4 more bytes without BF_EXITCLEANLY (it will segfault to exit).
• -2 more bytes with BF_BALANCED (assumes that over course of program data cell returns to start).
• So minimum possible size 74 bytes.
• NOTE Without the ideal bss setup (at address 0x7ffe0000 and BF_IDEAL_BSS defined as seen in compile command above) add +2 bytes.

#define BF_LBRACE   91
#define BF_RBRACE   93

#define BF_DOT  46
#define BF_COMMA    44

#define BF_PLUS 43
#define BF_MINUS    45

#define BF_LSHIFT   60
#define BF_RSHIFT   62

#define BF_READFILE
#define BF_EXITCLEANLY
    // #define BF_IDEAL_BSS
    // #define BF_BALANCED


    .global _start
    .text
_start:
    /* All incoming registers at zero.  */

    /* Large read range. This may cause errors for huge programs
       (which will fail anyways).  */
    decl    %edx
#ifdef BF_READFILE
    /* open.  */
    movb    $2, %al
    /* 3rd argument in rsp is first commandline argument.  */
    pop %rdi
    pop %rdi
    pop %rdi
    /* O_RDONLY is zero.  */
    syscall
    /* Error is okay, we will eventually just exit w.o executing.  */
    xchgl   %eax, %edi

    /* Sets ESI at 2 ** 31. This is an arbitrary address > 65536
       (minimum deref address on linux) < 2 ** 32 - PROG_SPACE
       (PROG_SPACE ~= 262144). We setup bss at 2 ** 31 - 131072 via
       linker script (-Tbss=0x7ffe0000).  */
# ifdef BF_IDEAL_BSS
    bts %edx, %esi
# else
    movl    $(G_mem + 65536), %esi
# endif
    /* bss initialized memory is zero. This is cheapest way to zero
       out eax.  */
    lodsl
#else
# ifdef BF_IDEAL_BSS
    bts %edx, %esi
# else
    movl    $(G_mem + 65536), %esi
# endif
#endif

    /* eax/edi are already zero which happens to match
       SYS_read/STDIN_FILENO.  */
    syscall


    /* Usage linux' pre-allocated stack for braces.  */

    /* Program code grows up.  */
    movl    %esi, %ebx
    /* Assuming no errors, reach stores size in eax. Note errors or
       0-byte reads are okay. The ebx is readable memory and zero-
       initialized (bss), so it its zero-length, it will just be an
       invalid op and we will hit bounds check below. If its error,
       eax is negative so ebx will be negative and likewise we will
       hit bounds check below.  */

#ifdef BF_BALANCED
    addl    %eax, %esi
    xchgl   %eax, %ebp
#else
    addl    %esi, %eax
    xchgl   %eax, %ebp
    movl    %ebp, %esi
#endif

    /* We have -1 in edx, so negative to get 1. 1 is needed in a
       variety of places.  */
    negl    %edx
run_program:
    /* Need to zero eax.  */
    movb    (%rbx), %al
    incl    %ebx
 
    /* %al contains the program "instruction". Its unique to one of
       8 values so just test each in order. If instruction matches
       execute it then fallthrough (%al can only ever match one).
       We occasionally set al but are sure never to set it to the
       ASCII value of any of our 8 instructions.  */

    /* TODO: Brace handling could probably be smaller.  */
try_lbrace:
    cmpb    $BF_LBRACE, %al
    je  do_lbrace
try_rbrace:
    cmpb    $BF_RBRACE, %al
    jne try_cont
do_rbrace:
    /* Popping state (we might repush if we are looping back).  */
    pop %rdx
    pop %rdi
    /* Non-zero cell means loop. Note we have 1 cached in edx.  */
    cmpb    %dl, (%rsi)
    jb  next_insn
    movl    %edi, %ebx
do_lbrace:
    /* Restore loop state.  */

    push    %rbx
    push    %rdx

    /* If cell is zero, then we are skipping till RBRACE. Note we
       have 1 cached in edx.  */
    cmpb    %dl, (%rsi)
    /* -1 if we want to start skipping.  */
    sbb %dh, %dh
try_cont:
    orb %dh, %al
    /* we have set ah s.t its either zero or has a value that makes
       any further matches impossible.  */

    /* For the rest of the ops we take advantage of the fact that
       the ascii values of the pairs '<'/'>', '+'/'-', and '.',','
       are all 2 apart. This allows use to test a pair with the
       following formula: `((al - PAIR_LO) & -3) == 0`. This will
       always leave the pair as 0/2 and will match only the pair.
       It turns out 0/2 are useful and can be used to do all the
       rest of the operations w.o extra branches.  */

try_lshift:
    subb    $BF_LSHIFT, %al
    testb   $-3, %al
    jnz try_comma
    addl    %eax, %esi
    decl    %esi
try_comma:
try_dot:
    subb    $(BF_PLUS - BF_LSHIFT), %al

    /* We have 0/1/2/3 for '+'/','/'-'/'.' so check if we remaining
       valid opcode.  */
    cmpb    $3, %al
    ja  next_insn

    /* 0/2 are '+'/'-' so check low bits. TODO: There may be a way
       to just care from `shr $1, %al' which would save us an
       instruction. But it messes up the '+'/'-' case.  */
    testb   $-3, %al
    jz  try_minus

    /* al is either 3/1. Shift by 1 to get 1/0 for our syscall number.  */
    shrb    $1, %al

    // btsq    $, %rax
    /* SYS_write == STDOUT_FILENO, SYS_read == STDIN_FILENO.  */
    movl    %eax, %edi
    /* We already have 1 in rdx.  */
    syscall
    /* Assuming no io error, eax is 1. We will subtract 1 from eax
       in try_minus/try_plus so it will be +/- 0 which does
       nothing.  */
try_minus:
try_plus:
    /* If not coming from syscall eax is 0/2. 0 --> plus, 2 -->
       minus. So (rsi - eax + 1) translates.  */
    // setbe   %cl

    subb    %al, (%rsi)
    incb    (%rsi)

next_insn:
#ifdef BF_BALANCED
    /* If BF_BALANCED is set, we assume that the program will have
       shifted back columns to start before exiting.  */
    cmpl    %ebx, %esi
#else
    cmpl    %ebx, %ebp
#endif
    jg  run_program

#ifdef BF_EXITCLEANLY
    /* eax has zero upper 24 bits so we can cheat and use movb here.
       (This isn't exact correct, assuming no IO errors on last
       instruction).  */
    movb    $60, %al
    syscall
#endif

    .section .bss
    .align  32
G_mem:  .space(65536 * 4)

X86_64/Linux Machine Code, 104 101 100 99 98 97 96 95 93 92

• Size is measured in machine code (i.e 92 bytes of PROGBITS; .text, .data, etc...)
• -10 bytes if reads input prog from stdin
• -4 more bytes without BF_EXITCLEANLY (it will segfault to exit).
• -2 more bytes with BF_BALANCED (assumes that over course of program data cell returns to start).
• So minimum possible size 76 bytes.
• NOTE Without the ideal bss setup (at address 0x7ffe0000 and BF_IDEAL_BSS defined) add +2 bytes.

#define BF_LBRACE   91
#define BF_RBRACE   93

#define BF_DOT  46
#define BF_COMMA    44

#define BF_PLUS 43
#define BF_MINUS    45

#define BF_LSHIFT   60
#define BF_RSHIFT   62

#define BF_READFILE
#define BF_EXITCLEANLY
    // #define BF_IDEAL_BSS
    // #define BF_BALANCED


    .global _start
    .text
_start:
    /* All incoming registers at zero.  */

    /* Large read range. This may cause errors for huge programs
       (which will fail anyways).  */
    decl    %edx
#ifdef BF_READFILE
    /* open.  */
    movb    $2, %al
    /* 3rd argument in rsp is first commandline argument.  */
    pop %rdi
    pop %rdi
    pop %rdi
    /* O_RDONLY is zero.  */
    syscall
    /* Error is okay, we will eventually just exit w.o executing.  */
    movl    %eax, %edi

    /* Sets ESI at 2 ** 31. This is an arbitrary address > 65536
       (minimum deref address on linux) < 2 ** 32 - PROG_SPACE
       (PROG_SPACE ~= 262144). We setup bss at 2 ** 31 - 131072 via
       linker script (-Tbss=0x7ffe0000).  */
# ifdef BF_IDEAL_BSS
    bts %edx, %esi
# else
    movl    $(G_mem + 65536), %esi
# endif
    /* bss initialized memory is zero. This is cheapest way to zero
       out eax.  */
    lodsl
#else
# ifdef BF_IDEAL_BSS
    bts %edx, %esi
# else
    movl    $(G_mem + 65536), %esi
# endif
#endif

    /* eax/edi are already zero which happens to match
       SYS_read/STDIN_FILENO.  */
    syscall


    /* Stack of braces grows down from below the program code.  */
    movl    %esi, %esp
    /* Program code grows up.  */
    movl    %esi, %ebx
    /* Assuming no errors, reach stores size in eax. Note errors or
       0-byte reads are okay. The ebx is readable memory and zero-
       initialized (bss), so it its zero-length, it will just be an
       invalid op and we will hit bounds check below. If its error,
       eax is negative so ebx will be negative and likewise we will
       hit bounds check below.  */
    addl    %eax, %esi
#ifndef BF_BALANCED
    movl    %esi, %ebp
#endif

    /* We have -1 in edx, so negative to get 1. 1 is needed in a
       variety of places.  */
    negl    %edx
run_program:
    /* Need to zero eax.  */
    movzbl  (%rbx), %eax
    incl    %ebx
    /* %al contains the program "instruction". Its unique to one of
       8 values so just test each in order. If instruction matches
       execute it then fallthrough (%al can only ever match one).
       We occasionally set al but are sure never to set it to the
       ASCII value of any of our 8 instructions.  */

    /* TODO: Brace handling could probably be smaller.  */
try_lbrace:
    cmpb    $BF_LBRACE, %al
    je  do_brace
try_rbrace:
    cmpb    $BF_RBRACE, %al
    jne try_cont
    /* Popping state (we might repush if we are looping back).  */
    pop %rdx
    pop %rdi
    /* Non-zero cell means loop. Note we have 1 cached in edx.  */
    cmpb    %dl, (%rsi)
    jb  next_insn
    movl    %edi, %ebx
do_brace:
    /* Restore loop state.  */

    push    %rbx
    push    %rdx

    /* If cell is zero, then we are skipping till RBRACE. Note we
       have 1 cached in edx.  */
    cmpb    %dl, (%rsi)
    /* -1 if we want to start skipping.  */
    sbb %dh, %dh
try_cont:
    orb %dh, %al
    /* we have set ah s.t its either zero or has a value that makes
       any further matches impossible.  */

    /* For the rest of the ops we take advantage of the fact that
       the ascii values of the pairs '<'/'>', '+'/'-', and '.',','
       are all 2 apart. This allows use to test a pair with the
       following formula: `((al - PAIR_LO) & -3) == 0`. This will
       always leave the pair as 0/2 and will match only the pair.
       It turns out 0/2 are useful and can be used to do all the
       rest of the operations w.o extra branches.  */

try_lshift:
    subb    $BF_LSHIFT, %al
    testb   $-3, %al
    jnz try_comma

     addl    %eax, %esi
    decl    %esi
try_comma:
try_dot:
    subb    $(BF_PLUS - BF_LSHIFT), %al
    /* We have 0/1/2/3 for '+'/','/'-'/'.' so check if we remaining
       valid opcode.  */
    cmpb    $3, %al
    ja  next_insn
    /* 0/2 are '+'/'-' so check low bits. TODO: There may be a way
       to just care from `shr $1, %al' which would save us an
       instruction. But it messes up the '+'/'-' case.  */
    testb   $1, %al
    jz  try_minus

    /* al is either 3/1. Shift by 1 to get 1/0 for our syscall number.  */
    shrb    $1, %al
    /* SYS_write == STDOUT_FILENO, SYS_read == STDIN_FILENO.  */
    movl    %eax, %edi
    /* We already have 1 in rdx.  */
    syscall
    /* Assuming no io error, eax is 1. We will subtract 1 from eax
       in try_minus/try_plus so it will be +/- 0 which does
       nothing.  */
try_minus:
try_plus:
    /* If not coming from syscall eax is 0/2. 0 --> plus, 2 -->
       minus. So (rsi) - (eax - 1) translates.  */
    decb    %al
    subb    %al, (%rsi)


next_insn:
#ifdef BF_BALANCED
    /* If BF_BALANCED is set, we assume that the program will have
       shifted back columns to start before exiting.  */
    cmpl    %ebx, %esi
#else
    cmpl    %ebx, %ebp
#endif
    jg  run_program

#ifdef BF_EXITCLEANLY
    /* eax has zero upper 24 bits so we can cheat and use movb here.
       (This isn't exact correct, assuming no IO errors on last
       instruction).  */
    movb    $60, %al
    syscall
#endif

    .section .bss
    .align  32
G_mem:  .space(65536 * 4)

 

Edit: Just for fun, here a compliant 270 byte fully contained ELF file that implements brainfuck on Linux/X86_64:

00000000  7f 45 4c 46 02 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
00000010  02 00 3e 00 01 00 00 00  b0 10 40 00 00 00 00 00  |..>.......@.....|
00000020  40 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |@...............|
00000030  00 00 00 00 40 00 38 00  02 00 00 00 00 00 00 00  |[email protected].........|
00000040  01 00 00 00 05 00 00 00  00 00 00 00 00 00 00 00  |................|
00000050  00 10 40 00 00 00 00 00  00 10 40 00 00 00 00 00  |..@.......@.....|
00000060  ce 00 00 00 00 00 00 00  ce 00 00 00 00 00 00 00  |................|
00000070  00 00 00 00 00 00 00 00  01 00 00 00 06 00 00 00  |................|
00000080  00 00 00 00 00 00 00 00  00 00 fe 7f 00 00 00 00  |................|
00000090  00 00 fe 7f 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000000a0  00 00 04 00 00 00 00 00  20 00 00 00 00 00 00 00  |........ .......|
000000b0  ff ca b0 02 5f 5f 5f 0f  05 89 c7 0f ab d6 ad 0f  |....___.........|
000000c0  05 89 f4 89 f3 01 c6 89  f5 f7 da 0f b6 03 ff c3  |................|
000000d0  3c 5b 74 0c 3c 5d 75 0e  5a 5f 38 16 72 28 89 fb  |<[t.<]u.Z_8.r(..|
000000e0  53 52 38 16 18 f6 08 f0  2c 3c a8 fd 75 04 01 c6  |SR8.....,<..u...|
000000f0  ff ce 2c ef 3c 03 77 0e  a8 01 74 06 d0 e8 89 c7  |..,.<.w...t.....|
00000100  0f 05 fe c8 28 06 39 dd  7f c1 b0 3c 0f 05        |....(.9....<..|
0000010e

X86_64/Linux Machine Code, 104 101 100 99 98 97 96 95 93 92 91

• Size is measured in machine code (i.e 91 bytes of PROGBITS; .text, .data, etc...)
• -9 bytes if reads input prog from stdin
• -4 more bytes without BF_EXITCLEANLY (it will segfault to exit).
• -2 more bytes with BF_BALANCED (assumes that over course of program data cell returns to start).
• So minimum possible size 76 bytes.
• NOTE Without the ideal bss setup (at address 0x7ffe0000 and BF_IDEAL_BSS defined as seen in compile command above) add +2 bytes.

#define BF_LBRACE   91
#define BF_RBRACE   93

#define BF_DOT  46
#define BF_COMMA    44

#define BF_PLUS 43
#define BF_MINUS    45

#define BF_LSHIFT   60
#define BF_RSHIFT   62

#define BF_READFILE
#define BF_EXITCLEANLY
    // #define BF_IDEAL_BSS
    // #define BF_BALANCED


    .global _start
    .text
_start:
    /* All incoming registers at zero.  */

    /* Large read range. This may cause errors for huge programs
       (which will fail anyways).  */
    decl    %edx
#ifdef BF_READFILE
    /* open.  */
    movb    $2, %al
    /* 3rd argument in rsp is first commandline argument.  */
    pop %rdi
    pop %rdi
    pop %rdi
    /* O_RDONLY is zero.  */
    syscall
    /* Error is okay, we will eventually just exit w.o executing.  */
    xchgl   %eax, %edi

    /* Sets ESI at 2 ** 31. This is an arbitrary address > 65536
       (minimum deref address on linux) < 2 ** 32 - PROG_SPACE
       (PROG_SPACE ~= 262144). We setup bss at 2 ** 31 - 131072 via
       linker script (-Tbss=0x7ffe0000).  */
# ifdef BF_IDEAL_BSS
    bts %edx, %esi
# else
    movl    $(G_mem + 65536), %esi
# endif
    /* bss initialized memory is zero. This is cheapest way to zero
       out eax.  */
    lodsl
#else
# ifdef BF_IDEAL_BSS
    bts %edx, %esi
# else
    movl    $(G_mem + 65536), %esi
# endif
#endif

    /* eax/edi are already zero which happens to match
       SYS_read/STDIN_FILENO.  */
    syscall


    /* Stack of braces grows down from below the program code.  */
    movl    %esi, %esp
    /* Program code grows up.  */
    movl    %esi, %ebx
    /* Assuming no errors, reach stores size in eax. Note errors or
       0-byte reads are okay. The ebx is readable memory and zero-
       initialized (bss), so it its zero-length, it will just be an
       invalid op and we will hit bounds check below. If its error,
       eax is negative so ebx will be negative and likewise we will
       hit bounds check below.  */
    addl    %eax, %esi
#ifndef BF_BALANCED
    movl    %esi, %ebp
#endif

    /* We have -1 in edx, so negative to get 1. 1 is needed in a
       variety of places.  */
    negl    %edx
run_program:
    /* Need to zero eax.  */
    movzbl  (%rbx), %eax
    incl    %ebx
    /* %al contains the program "instruction". Its unique to one of
       8 values so just test each in order. If instruction matches
       execute it then fallthrough (%al can only ever match one).
       We occasionally set al but are sure never to set it to the
       ASCII value of any of our 8 instructions.  */

    /* TODO: Brace handling could probably be smaller.  */
try_lbrace:
    cmpb    $BF_LBRACE, %al
    je  do_brace
try_rbrace:
    cmpb    $BF_RBRACE, %al
    jne try_cont
    /* Popping state (we might repush if we are looping back).  */
    pop %rdx
    pop %rdi
    /* Non-zero cell means loop. Note we have 1 cached in edx.  */
    cmpb    %dl, (%rsi)
    jb  next_insn
    movl    %edi, %ebx
do_brace:
    /* Restore loop state.  */

    push    %rbx
    push    %rdx

    /* If cell is zero, then we are skipping till RBRACE. Note we
       have 1 cached in edx.  */
    cmpb    %dl, (%rsi)
    /* -1 if we want to start skipping.  */
    sbb %dh, %dh
try_cont:
    orb %dh, %al
    /* we have set ah s.t its either zero or has a value that makes
       any further matches impossible.  */

    /* For the rest of the ops we take advantage of the fact that
       the ascii values of the pairs '<'/'>', '+'/'-', and '.',','
       are all 2 apart. This allows use to test a pair with the
       following formula: `((al - PAIR_LO) & -3) == 0`. This will
       always leave the pair as 0/2 and will match only the pair.
       It turns out 0/2 are useful and can be used to do all the
       rest of the operations w.o extra branches.  */

try_lshift:
    subb    $BF_LSHIFT, %al
    testb   $-3, %al
    jnz try_comma
    addl    %eax, %esi
    decl    %esi
try_comma:
try_dot:
    subb    $(BF_PLUS - BF_LSHIFT), %al
 
    /* We have 0/1/2/3 for '+'/','/'-'/'.' so check if we remaining
       valid opcode.  */
    cmpb    $3, %al
    ja  next_insn
 
    /* 0/2 are '+'/'-' so check low bits. TODO: There may be a way
       to just care from `shr $1, %al' which would save us an
       instruction. But it messes up the '+'/'-' case.  */
    testb   $-3, %al
    jz  try_minus

    /* al is either 3/1. Shift by 1 to get 1/0 for our syscall number.  */
    shrb    $1, %al

    // btsq    $, %rax
    /* SYS_write == STDOUT_FILENO, SYS_read == STDIN_FILENO.  */
    movl    %eax, %edi
    /* We already have 1 in rdx.  */
    syscall
    /* Assuming no io error, eax is 1. We will subtract 1 from eax
       in try_minus/try_plus so it will be +/- 0 which does
       nothing.  */
try_minus:
try_plus:
    /* If not coming from syscall eax is 0/2. 0 --> plus, 2 -->
       minus. So (rsi - eax + 1) translates.  */
    // setbe   %cl
    
    subb    %al, (%rsi)
    incb    (%rsi)

next_insn:
#ifdef BF_BALANCED
    /* If BF_BALANCED is set, we assume that the program will have
       shifted back columns to start before exiting.  */
    cmpl    %ebx, %esi
#else
    cmpl    %ebx, %ebp
#endif
    jg  run_program

#ifdef BF_EXITCLEANLY
    /* eax has zero upper 24 bits so we can cheat and use movb here.
       (This isn't exact correct, assuming no IO errors on last
       instruction).  */
    movb    $60, %al
    syscall
#endif

    .section .bss
    .align  32
G_mem:  .space(65536 * 4)

Edit: Just for fun, here a compliant 269 byte fully contained ELF file that implements brainfuck on Linux/X86_64:

00000000  7f 45 4c 46 02 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
00000010  02 00 3e 00 01 00 00 00  b0 10 40 00 00 00 00 00  |..>.......@.....|
00000020  40 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |@...............|
00000030  00 00 00 00 40 00 38 00  02 00 00 00 00 00 00 00  |[email protected].........|
00000040  01 00 00 00 05 00 00 00  00 00 00 00 00 00 00 00  |................|
00000050  00 10 40 00 00 00 00 00  00 10 40 00 00 00 00 00  |..@.......@.....|
00000060  cd 00 00 00 00 00 00 00  cd 00 00 00 00 00 00 00  |................|
00000070  00 00 00 00 00 00 00 00  01 00 00 00 06 00 00 00  |................|
00000080  00 00 00 00 00 00 00 00  00 00 fe 7f 00 00 00 00  |................|
00000090  00 00 fe 7f 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000000a0  00 00 04 00 00 00 00 00  20 00 00 00 00 00 00 00  |........ .......|
000000b0  ff ca b0 02 5f 5f 5f 0f  05 97 0f ab d6 ad 0f 05  |....___.........|
000000c0  89 f4 89 f3 01 c6 89 f5  f7 da 0f b6 03 ff c3 3c  |...............<|
000000d0  5b 74 0c 3c 5d 75 0e 5a  5f 38 16 72 28 89 fb 53  |[t.<]u.Z_8.r(..S|
000000e0  52 38 16 18 f6 08 f0 2c  3c a8 fd 75 04 01 c6 ff  |R8.....,<..u....|
000000f0  ce 2c ef 3c 03 77 0e a8  fd 74 06 d0 e8 89 c7 0f  |.,.<.w...t......|
00000100  05 28 06 fe 06 39 dd 7f  c1 b0 3c 0f 05           |.(...9....<..|
0000010d