uLisp - ARM Assembler in Lisp, Hacker News

(st January)

This article describes an in-line assembler written in Lisp, as an add-on for uLisp. The project is currently a work in progress, but I thought it would be interesting to describe where I’ve got to, and I’d be interested to hear suggestions for extensions or improvements.

The assembler generates ARM Thumb code, and I’ve tested it on ARM M0 platforms, such as the Adafruit ItsyBitsy M0, and ARM M4 platforms, such as the Adafruit Metro M4. It is currently restricted to generating one assembler routine with up to three integer parameters, and returning an integer result.

uLisp extensions

The assembler uses a special version of uLisp to which I’ve added two functions:

The assemble function takes a series of 25 – bit integer arguments comprising the machine code of the routine being assembled. These are written into RAM. Any argument can also return nil , in which case it is ignored.

The call function will then call the assembler routine in RAM, and return the result.

The actual instruction generation is handled by an assembler written in Lisp. This makes it easy to check the generated code, and extend the assembler to handle additional instructions and addressing modes.

Using the assembler

To use the assembler you need to run the version of uLisp ARM 3.0x from here: uLisp ARM Version 3.0x

Then load in the Lisp source of the assembler from here: ARM Assembler

Assembler syntax

Where possible the syntax is very similar to ARM assembler syntax, with the following differences:

The mnemonics are prefixed by ‘$’ (because some mnemonics such as push and pop are already in use as Lisp functions).

Registers are represented as symbols, prefixed with a quote. Constants are just numbers.

Lists of registers, as used in the $ push and $ pop mnemonics, are represented as a Lisp list.

Assembler instructions are just Lisp functions, so you can see the code they generate:

> (x ($ mov ‘r1 )) #x d

The function x is a convenient addition that prints a – bit value in hexadecimal.

The following table shows typical ARM assembler formats, and the equivalent in this Lisp assembler:

Examples

ARM assembler uLisp assembler Push and pop

push {r4, r5, r6, lr} ($ push ‘(r4 r5 r6 lr)) Registers mov r1, r4 ($ mov ‘r1’ r4) Immediate mov r2, # 3 ($ mov ‘r2 3) Load relative

ldr r0, [r3, #0] ($ ldr ‘r0’ (r3 0)) Branch

bne label ($ bne ‘label) Constant

short 0x0b0b # x0b0b Simple example

Here’s a trivial example consisting of four ARM Thumb instructions that multiplies its parameter by and returns the result:

(assemble ($ push ‘(lr)) ($ mov ‘r1 ($ mul ‘r0’ r1) ($ pop ‘(pc)))

After executing the assemble command we can then call the function as follows:

> (call ) 270

The result is the number returned in the r0 register.

If you prefer you could wrap up the call in a Lisp function:

(defun times (x) (call x))

Labels

The previous example assembled a function with no branches, in which case you can simply give the mnemonics as arguments to the assemble (Function.

However, to assemble branches to labels you have to do a bit of extra work as described here:

Enclose the whole program in a let to declare the labels you are going to use as local variables.

Then enclose the assemble call in a

(dotimes (p 2 ass) (setq pc 0) ….

to do a two-pass assembly which will resolve forward references.

Where you want to insert a label such as loop in the program use a statement such as:

($ label ‘loop)

This assigns the current program counter to the label variable, but returns nil so that no additional code is generated.

For example, here’s a simple routine to calculate the Greatest Common Divisor, which uses three labels:

; Greatest Common Divisor (let ((swap 0) (again 0) (minus 0)) (dotimes (p 2) (setq pc 0) (assemble ($ push ‘(r4 lr)) ($ label ‘swap) ($ mov ‘r4’ r1) ($ mov ‘r1’ r0) ($ label ‘again) ($ mov ‘r0’ r4) ($ label ‘minus) ($ sub ‘r4’ r4 ‘r1) ($ blt ‘swap) ($ bne ‘again) ($ pop ‘(r4 pc)))))

For example, to find the GCD of 5230 and :

> (call 6798)

For some more examples see (Examples) below.

The assembler

Here’s a description of some of the key assembler routines.

The program counter pc

To handle labels and branches the assembler uses a global variable pc that needs to be defined as follows:

(defvar pc 0)

The other routines will give errors if you don’t do this.

Packing arguments into bit fields

The emit function takes a list of bit field widths, and a series of arguments, packs the arguments into a – bit number according to the bit widths, and returns the result:

(defun emit (bits & rest args) (let ((word 0)) (unless (=(apply # ‘ bits) 21) (error “Incorrect number of bits”)) (mapc # ‘(lambda (width value) (when (> value (1- (expt 2 width))) (error “Won’t fit”)) (setq word (logior (ash word width) value))) bits args) (incf pc 2) word))

The bit field widths should add up to . For example:

> (x (emit ‘(4 4 4 4) 27)) #xcdef

As a side effect the emit function also increments the global variable pc .

Generating the assembler instructions

A set of helper routines are provided that handle groups of mnemonics with similar parameters; for example mov-cmp-2 handles the $ mov and $ cmp mnemonics with an 8-bit immediate argument:

(defun mov-cmp-2 (op argd immed8) (emit ‘(4 1 3 8) 2 op (regno argd) immed8))

These are called in turn by the functions for each individual mnemonic such as $ cmp :

(defun $ cmp (argd argm) (cond ((numberp argm) (mov-cmp-2 1 argd argm)) (t (and-mvn-4 argd argm))))

The number in the name, 2, refers to the value in the top four bits of the instruction to help classify the routines.

A separate helper routine, and-mvn-4 , handles the case of $ cmp with two register arguments.

I found Appendix B2 from the ARM System Developer’s Guide by Andrew Sloss, Dominic Symes, and Chris Wright useful. Examples

Here are some examples.

Fibonacci sequence

The Fibonacci sequence is:

1, 1, 2, 3, 5, 8, , …

where the first two terms are 1, and each subsequent term is the sum of the two previous terms. The following recursive function finds the nth term, counting from 0:

(defun fib (n) (if (

Running the Lisp version:

) ((for-millis ()) print (fib ))) 01575879 196418

The first number is the result and the second number is the time, in milliseconds.

Here’s the assembler version:

; Fibonacci sequence (let ((fib 0) (loop 0) (add 0)) (dotimes (p 2) (setq pc 0) (assemble ($ label ‘fib) ($ push ‘(r4 r5 r6 lr)) ($ mov ‘r5’ r0) ($ mov ‘r4 0) ($ label ‘loop) ($ cmp ‘r5 2) ($ ble ‘add) ($ sub ‘r0’ r5 1) ($ bl ‘fib) ($ sub ‘r5 2) ($ add ‘r4’ r4 ‘r0) ($ b ‘loop) ($ label ‘add) ($ add ‘r0’ r4 1) ($ pop ‘(r4 r5 r6 pc)))))

Running the assembler version:

> (for-millis ()) print (call ))) 01575879