asm2bf

From Esolang
Jump to navigation Jump to search
Not to be confused with BFasm.
asm2bf
Paradigm(s) imperative
Designed by Palaiologos
Appeared in 2017
Memory system register,cell,stack
Computational class Turing-complete
Reference implementation asmbf
Influenced by Brainfuck
File extension(s) .asm, .s

asm2bf is the only true brainfuck assembler in active development since 2017. It produces small and efficient brainfuck code based on instruction choice. It's features include a Lua preprocessor, labels, a precise floating point library, conditional branching, dynamic memory allocation procedures, stack-based offsets, instruction-level move semantics, virtual instructions, effective adresses and signed arithmetic. It's possible to define recursive procedures, and do basically everything you'd expect from a normal assembler.

For documentation, check the manual.

Examples

A tiny hello world:

#gen_text("Hello, world!")

calculate 1/n for n in 1 .. 9:

inc r1
psh r1
psh 1

@loop
    inc r1
    psh r1
    psh 1
    fadd
    freduce
    ceq r1, 9
    cjn %q
    jmp %loop
@q
    pop r1
    pop r2
    eq  r1, 7129
    eq  r2, 2520
    and r1, r2
    add r1, .0
    out r1

if you pipe my output into a file, ^C it, and then pipe the file into aplay, you should hear a very simple tune:

; black voodoo magic.
mov r4, 1280
mov r1, 1

raw .[
mov r2, r1
sub r2, r4
bxor r2, r1
shr r2, 10
mov r3, r1
shr r3, 15
mov r5, r3
mod r5, 2
not r5
add r3, r5
add r3, r1
bxor r3, r1
bxor r2, r3
mul r2, r1
out r2
inc r1
raw .]

Sierpinski triangles:

@loop1
    mov r2, 0
    
    @loop2
        mov r3, r1
        band r3, r2
        cge r3, 1
        mov r3, .*
        cmov r3, 32
        out r3
        
        clt r2, 63
        cadd r2, 1
        cjn %loop2
    
    out 10
    
    clt r1, 63
    cadd r1, 1
    cjn %loop1

Explained code example

Let's perform binary reduce a list with a right bias. Given a list of 2 or more strictly positive integers, sum the first and last half of the list, with the middle element being counted only in the right half if the list has an odd number of elements. The code:

@inloop
    in r1
    cne r1, 0
    cadd r2, 1
    cpush r1
    cjn %inloop

    mov r3, r2
    mod r3, 2
    div r2, 2
    mov r4, r2
    add r2, r3

@right
    pop r1
    add r5, r1
    dec r2
    jnz r2, %right

@left
    pop r1
    add r6, r1
    dec r4
    jnz r4, %left

    out r6
    out r5

Invocation examples:

!"#$% => [33, 34, 35, 36, 37] => [33 + 34, 35 + 36 + 37] => [67, 108] => Cl
!"#$ => [33, 34, 35, 36] => [33 + 34, 35 + 36] = [67, 71] => CG

Let's dissect the code.

@inloop
    in r1
    cne r1, 0
    cadd r2, 1
    cpush r1
    cjn %inloop

Some parts are obvious (label declarations for example), some are less. A feature introduced around v1.3.5 named conditional instructions helps us greatly to solve this task.

The conditional pipeline of this fragment follows:

    cne r1, 0     ; if r1 is not zero, set the flag, otherwise clear it
    cadd r2, 1    ; if flag is set, add 1 to r2 (we accumulate the list length)
    cpush r1      ; push the number on the stack if the flag is set.
    cjn %inloop   ; jump to @inloop if the flag is set.

As you can see, it's quite simple to notice, that this tiny block of code will is responsible for:

  • reading the list
  • accumulating it's elements on the stack
  • keeping track of the amount of elements read (in r2)
  • looping until hit EOF

Note: Yes, it's true that you have to set the stack before accessing it, otherwise stack overflow error occurs. In this case, I simply don't make memory accesses, so it's not required to set the stack (because it has nowhere to overflow to).

Between these two loops, there is a tiny block of setup code:

    mov r3, r2     ; r3 = r2
    mod r3, 2      ; r3 = r2 mod 2
    div r2, 2      ; r2 = r2 / 2
    mov r4, r2     ; r4 = r2
    add r2, r3     ; r2 = r2 + r3

This means, the register values are now:

r4 = r2 / 2
r3 = r2 mod 2
r2 = (r2 / 2) + r3

r3 is used as a flag to indicate whenever the middle element is present and it has to be merged to the list on the right (if count mod 2 is 1, then the count is odd, therefore we have a middle element obviously). The flag is added to the r2 register so the following loop will slurp it from the stack.

Next, there are two very simillar loops. Let's dissect these:

@right
    pop r1
    add r5, r1
    dec r2
    jnz r2, %right

@left
    pop r1
    add r6, r1
    dec r4
    jnz r4, %left

@right will execute until r2 is not zero (id est, the amount of elements left to extract from the stack to make the right list). Everytime an element is popped, the pointer (r2) decreases and the popped value is added to r5. This being said, @right will simply extract r2 elements from the stack and sum them up to r5. @left works pretty much the same (it will build the list on the left) returning the result in r6.

And finally, we output both values (sum for the left and the right):

    out r6
    out r5

Changelog

v0.9.0: First appeared publicly: 28 Oct 2017

  • Introduce basic (smallest common denominator) instruction set:
add and dec div eq_ ge_ gt_ in_ inc jmp jnz jz_ lbl le_ lt_ mod mov mul ne_ neg not or_ out pop psh rcl sto sub swp clr ret end stk org db_ txt raw
  • Current (as of late December of 2019) version of the self compiler.
  • Modulus is broken.
  • Labels are introduced just using lbl keyword.
  • No preprocessor.

v0.9.1: First appeared publicly: 19 Oct 2018

  • No changes to instruction set
  • Publicly available documentation for toolchain
  • Hello world example bundled in the source tree.

v0.9.2: First appeared publicly: 20 Oct 2018

  • Brainfuck apache2 module (to be used with asm2bf).
  • Overall formalization of the project
  • The self compiler appeared publicly.

v0.9.3: First appeared publicly: 31 Oct 2018

  • Debugging tools

v0.9.4: First appeared publicly: 31 Mar 2019

  • bfasm-experimental version featuring a new register.
  • Basic preprocessor

v1.0.0: First appeared publicly: 23 Apr 2019

  • rcl and sto with reg, immed construct.
  • Documentation tweaks.

v1.0.1: First appeared publicly: 10 May 2019

  • Inclusion system.
  • Deprecate dbgasm
  • mod and puts procedures in the trunk.
  • Extended interpreter for extended possibilities.
  • "Broken modulus is no more".
  • Self compiler yet again works.

v1.0.2: First appeared publicly: 10 Aug 2019

  • Gisa toolkit birth.
  • bfpp deprecation
  • Rust translation of the toolchain
  • (broken) Malbolge interpreter.
  • Hex counter example.

v1.1.0: First appeared publicly: 2 Oct 2019

  • New tools: strip.pl, bconv
  • New instructions: log, srv
  • Instruction buffer fix.
  • Versioning information.
  • First swallow of newest changes.

v1.1.1: First appeared publicly 12 Oct 2019

  • New instructions: asl, asr
  • Toolchain programs merged into single make, install script.
  • Label preprocessor.
  • Repository separated - background files and the documentation moved out of the root.

v1.1.2: First appeared publicly: 16 Nov 2019

  • Full-featured RLE support.
  • New toolchain tool (derle.pl)
  • Prefix/postfix compression
  • bfi now accepts path starting with / or - (no longer treats them like an option).

v1.1.3: First appeared publicly: 17 Nov 2019

  • Offsets.
  • New instruction: seg
  • Unit testbed
  • -DNO_CHECKS bfi variant
  • Remove experimental version of bfasm.

v1.1.4: First appeared publicly: 21 Nov 2019

  • Digits allowed in label names.
  • cpp is now the bfasm preprocessor.
  • Newlines allowed inside macros.
  • strip no longer trashes breakpoints.
  • New instructions: amp, smp

v1.2.0: First appeared publicly: 25 Nov 2019

  • Debugger simplified
  • More recent hello world example.

v1.2.4: First appeared publicly: 28 Dec 2019

  • New instruction: nav
  • r5 - new GPR
  • Enhanced stripper.
  • Immediate optimalization.

v1.2.5: First appeared publicly: 29 Dec 2019

  • New example: Branchless interpreter bitness check.
  • pow optimalization
  • -DDISABLE_OPT - disable immediate optimalization.
  • Uppercase instruction names.

v1.2.6: First appeared publicly: 30 Dec 2019

  • New bfi.
  • Bugfix: register uppercase names (e.g. R2) now work.

v1.2.7: First appeared publicly: 31 Dec 2019

  • Two new registers.

v1.2.8a: First appeared publicly: 23 Jan 2020

  • Alpha version.
  • Separate preprocessor for data labels. Not merged to the mainline yet.
  • `seg` now clears previous `org` value, setting it to 0. Can be treated like a bugfix from v1.1.3.

v1.2.9: First appeared publicly: 29 Feb 2020

  • Important bugfixes regarding registers - r5 and r6 temporairly removed.

v1.3.0: First appeared publicly: 13 Mar 2020

  • Milestone release, bugfixes.

v1.3.1: First appeared publicly: 10 Apr 2020

  • Milestone release, bugfixes.

v1.3.2: First appeared publicly: 13 Apr 2020

  • Minor project structure cleanup.
  • Documentation files removed from the repository.
  • Repository contains a mirror of the article.

v1.3.3: First appeared publicly: 14 Apr 2020

  • bfvm (rave) - a brainfuck interpreter targeted at optimizing, running and debugging asm2bf code at high speed.
  • new installation system (fixes a critical bug occuring without a ASMBF_DIR set)

v1.3.4: First appeared publicly: 16 Apr 2020

  • the floor character (_) at the end of an instruction is optional.

v1.3.5: First appeared publicly: 17 Apr 2020

  • Now, asm2bf has an internal flag register (inaccessible via normal means),
  • The flag register can be set by the following: ceq cne cle clt cge cgt (equivalent to eq, ne, le, lt, ge, gt). For instance:
mov r1, 23
ceq r1, 23
; will set the flag register to 1.
ceq r1, 0
; nope, didn't succeed, now clears the flag register.
  • New jumps: cjn cjz, that depend on the state of the flag register. For example:
; Old way (trashes r3):
mov r3, r1
eq_ r3, 10
jnz r3, %target

; New way (no trashes):
ceq r1, 10
cjn %target
  • New instructions! All of these execute, whenever the flag register is set to 1:
Conditional variant: cad csu cmu cdi cmd csl csr cpw cps cpo csw crv cmo crc cst
Classic variant:     add sub mul div mod asl asr pow psh pop swp srv mov rcl sto
  • b2bf (coined by comrade Maviek) - a B to asm2bf compiler. It's an initial release, so a few things in b2bf may be rigged, but it's able to produce decent code (just three times bigger than the handcoded and optimized assembly equivalent).

v1.3.6: First appeared publicly: 18 Apr 2020

  • purely bugfix-related update.
  • optimized modulus
  • (now working) r5 and r6 due to a programming error introduced while implementing conditional instructions.

v1.3.7: First appeared publicly: 15 May 2020

  • constpp is a new preprocessor introduced alongside asm2bf. It can be used to alias instruction and register names, like so:
?r6=sp
; and now
sub sp, 4
; is equal to
sub r6, 4
; No spaces are allowed after and before =, no spaces are allowed inside aliases,
; no spaces are allowed after the question mark (?).
  • Rave has now a 16-bit compatibility option.
  • Raw left and right bracket fix for Rave (oops)
  • Now the bitness example has the correct brackets used to create a while loop.
  • smp and amp micropatch
  • Removed dependency on -lfl

v1.3.8: First appeared publicly: 15 May 2020

  • This release features a tool to alias registers and instruction names. Example:
?bp=r1
?sp=r2
mov bp, sp
  • List of aliases:
?push=psh
?xchg=swp
?cadd=cad
?csub=csu
?cmul=cmu
?cdiv=cdi
?cmod=cmd
?casl=csl
?casr=csr
?cpow=cpw
?cpush=cps
?cpsh=cps
?cpop=cpo
?cxchg=csw
?cswp=csw
?csrv=crv
?cmov=cmo
?crcl=crc
?csto=cst
  • Instruction alias example:
push r1
xchg r1, r2
out r2

v1.3.9: First appeared publicly: 16 May 2020

  • New instructions:
band - bit and
bor - bit or
bxor - bit xor
shl - shift left (e.g. shl r1, 3)
shr - shift right (e.g. shr r1, 3)
cflip - flip the conditional execution flag register.

v1.4.0: First appeared publicly: 12 June 2020

  • 30 new instructions.
  • Enlargened local permanent generation size.
  • Optimized nearly every microcode snippet.
  • shr, shl, cout, cin
  • dup, cdup, additional conditional instructions in form of: c[xor/or/and][eq/lt/gt/ne/ge/le].
  • Error messages!
  • Fixed bfi-derle
  • bfi: added decimal flag.
  • Rave has became obsolete and removed.
  • New bfmake, with less bugs and more Perl!
  • bfasm crashed? generate_report is here.
  • around 13 new tests.
  • test timeout (20s).

v1.4.1: First appeared publicly: 23 June 2020

  • Effective adresses:
txt "abcdefghijklmnop"

mov r5, 2
mov r6, 3
rcl r1, 1(r6,r5,4)
out r1

; mov r1, 2(r3, r4, 4) => mov r1, [r4 * 4 + r3 + 2]
  • ots, cots as sto with reversed parameter order.
  • all registers are transparent from now.
  • remove bfintd
  • add dsc - discard the element on the top of the stack
  • add incunabulum

v1.4.2: First appeared publicly: 7 August 2020

  • -c switch for bfi, which will count the amount of cycles taken by the brainfuck program.
  • Various changes regarding to effective adresses; stack-based ones; effective adress priming.
  • stack gets / stack sets / stack length query (O(N)).
  • vxcall
  • bfvm prototype
  • remove obsolete toolkit elements.

v1.4.3: First appeared publicly: 2 October 2020

  • small size optimizations for db
  • escape sequences inside txt
  • better error reporting
  • asm2bf manual with a complete instruction set outline
  • many bfvm microcode patches
  • redpower (the asm2bf bootable kernel loader)
  • two new instructions (fps/fpo, for pushing and popping the flag register state)
  • a signed arithmetic polyfill draft,
  • more examples
  • autoconf migration.

v1.4.4: First appeared publicly: 4 October 2020

  • extension update to v1.4.3
  • refreshed bfstrip, with optional linebreak insertion in the file (wrap to width using --with-line-width=n while calling ./configure).
  • manual in the trunk
  • reorganized microcode for bfasm
  • smarter bfmake (detecing the installed bfasm version).
  • fcpush, fcpop, fcpsh aliases.
  • lib-bfm stub changes
  • bfvm jamming protector.
  • fixed a single memory leak regarding effective
  • fixed two buffer overflows
  • fix the double-nocopy switch

v1.5.0: First appeared publicly: 13 October 2020

  • basic signed arithmetic - sgadd, sgsub, sgmul, sgdiv, sgmod, sneg (signed negation), abs, sgn (signum).
  • faster builds, better tests.
  • asm2bf passes the magical amount of 35 000 lines of code, 130 instructions and 900 commits.
  • enhanced error reporting.
  • minor bugfixes
  • cbegin and cend blocks for conditional instructions!

v1.5.1: First appeared publicly: 25 November 2020

  • rewritten bflabels / bfdata
  • far pointers
  • forward data declarations
  • optimizing code label system
  • tiny mode to bfasm (-t)
  • most compile-time switches present before are now available as runtime flags.
  • performance graphs
  • #emit macro
  • [bits N] construct preprocessed by bfdata.
  • automatic warnings about bitwidth exceeding.
  • bts core instruction (emitted by [bits N]).

v1.5.2: First appeared publicly: 10 December 2020

  • optimized stores to r4 (size)
  • a few more examples
  • gen_text macro
  • dp2, dup2, fdup instructions
  • axl - approximate with low precision
  • sgeq, sgne
  • xgt, xle - signed greater than & signed less or equal

v1.5.3: First appeared: 20 March 2021 Consider this more of a bugfix/stability release, with most features originating from the first three months of 2021. Featuring:

  • removing obsolete `generate_report`
  • `xlt`
  • `xge`, `xle` optimized
  • `xge`
  • multiline `constpp` macros
  • many new instructions implemented for `bfvm`
  • a new ucode compiler.
  • bugfixes to bfadbg (more edge-case handling in edit mode)
  • improved compatibility with weird systems
  • `lbl imm` optimization
  • `bfdata` and `bflabel` performance improvements
  • SK calculus evaluator example
  • `vxcall` patch; `bfdata` addressing bugfixes.
  • merged `vxcall` and `constpp`, `bfdata` and `bflabels`.
  • `sle` now works correctly on an empty stack
  • multiple `bfvm` bugfixes
  • `bfmake` no longer requires `-b` to go along `-c`.
  • `bfvm` output is more portable
  • inline brainfuck is now supported by `bfvm` (although it's not optimized yet).
  • linear-bounded automata optimizer in Java (remotely useful for asm2bf programs).

v1.5.3a: First appeared: 30 March 2021 A hotfix for the following:

  • bfvm reading 0xFF on EOF
  • constpp undefined behaviour
  • tab-separated mnemonic + operand combination resulting in an error.

v1.5.4: First appeared: 12 April 2021

  • fix: `tps` is now `vxcall`able.
  • feature: `u2s` and `s2u` - casting between unsigned and signed numbers, both ways.
  • updated manual
  • bfvm rewrite; real segmentation mode / scale factor support.
  • fix: `cret` now works correctly.
  • move semantics support for `and`, `add`, `div`, `eq`, `lt`, `gt`, `jmp`, `jnz` and `jz` (introduced with `^` before instruction name).

v1.5.4a: First appeared: 4 May 2021

  • more tests for move semantics; move semantics implemented for `le, mod, mov, ne, psh`.
  • `mbegin .. mend` construct (implicit move semantics inside the block).
  • bfstrip now doesn't strip unrecognized commands if bfmake flag `-q` is supplied.
  • move semantics for sub, rcl and sto.
  • countless manual updates.
  • bfmake preserves files on failed build.
  • the makefile works on Mach/BSD (thanks to @sech1p)
  • optimization for `mul reg, imm`
  • translation to and from trivial brainfuck substitutions (`subst.pl`)
  • `lods`, `stos`, `scas` (check the manual/discord server for more).
  • a `full` make target to build, install and test asm2bf.
  • change the apperiance of hello-fancy.asm in the examples directory.
  • alias `_` to print in `lib-bfm`
  • x64 Darwin binaries (@sech1p)

See also