uLisp

RISC-V assembler examples

These examples will run on the RP2350 RISC-V core, or the K210 RISC-V processor on the MAiX boards.

Get the assembler here: RISC-V assembler in uLisp.

Sections

Numeric examples

Games

List examples

Numeric examples

The following examples illustrate the use of the assembler with integer parameters. Many of them are based on the uLisp Benchmarks.

Fibonacci sequence

The Fibonacci sequence is:

1, 1, 2, 3, 5, 8, 13, 21 ...

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 (< n 3) 1
    (+ (fib (- n 1)) (fib (- n 2)))))

Running the Lisp version on a Raspberry Pi Pico 2:

> (time (fib 27))
196418
Time: 27.7 s

Here's the assembler version:

; Fibonacci sequence
(defcode fib (n)
  fib
  ($addi 'sp 'sp -12)
  ($sw 'ra 0 '(sp))
  ($li 't0 2)
  ($ble 'a0 't0 ret1)
  ($sw 'a0 4 '(sp))
  ($addi 'a0 'a0 -1)
  ($jal fib)
  ($sw 'a0 8 '(sp))
  ($lw 'a0 4 '(sp))
  ($addi 'a0 'a0 -2)
  ($jal fib)
  ($lw 't0 8 '(sp))
  ($add 'a0 'a0 't0)
  ($j ret)
  ret1
  ($li 'a0 1)
  ret
  ($lw 'ra 0 '(sp))
  ($addi 'sp 'sp 12)
  ($ret))

Running the assembler version on a Raspberry Pi Pico 2:

> (time (fib 27))
196418
Time: 43 ms

Factor

This function takes a simple approach to finding the least prime factor of a number:

(defun factor (n)
  (let ((d 2) (i 1))
    (loop
     (when (> (* d d) n) (return n))
     (when (zerop (mod n d)) (return d))
     (incf d i) (setq i 2))))

If the number is prime, factor will print the number itself. To find the least prime factor of 2146654199 (46327 x 46337):

>  (time (factor 2146654199))
46327
Time: 2.3 s

Here's an equivalent assembler version:

; Least prime factor
(defcode factor (x)
  factor
  ($li 'a4 1)
  ($li 'a5 2)
  test
  ($mul 'a3 'a5 'a5)
  ($blt 'a0 'a3 returnn)
  ($rem 'a3 'a0 'a5)
  ($bnez 'a3 add)
  ($mv 'a0 'a5)
  returnn
  ($ret)
  add
  ($add 'a5 'a5 'a4)
  ($li 'a4 2)
  ($j test))

Doing the same test to find the least prime factor of 2146654199 (46327 x 46337):

> (time (factor 2146654199))
46327
Time: 4 ms

Factorize

You can use the above function as the basis for a simple recursive routine to factorize a number into a list of its prime factors:

(defun factorize (n)
  (let ((f (factor n)))
    (if (= n f) (list n) (cons f (factorize (/ n f))))))

For example:

> (factorize 731731731)
(3 17 43 333667)

Takeuchi function

The Takeuchi function is a classic benchmark for comparing implementations of Lisp, originally used by Ikuo Takeuchi of Japan. Here's the Lisp version:

(defun tak (x y z)
  (if (not (< y x))
      z
    (tak
     (tak (1- x) y z)
     (tak (1- y) z x)
     (tak (1- z) x y))))

For example:

> (time (tak 18 12 6))
7
Time: 5.0 s

Here's the assembler version:

; Tak
(defcode tak (x y z)
  tak
  ($addi 'sp 'sp -24)
  ($sw 'ra 0 '(sp))
  ($blt 'a1 'a0 cont)
  ($mv 'a0 'a2)
  ($j ret)
  cont
  ($sw 'a0 4 '(sp)) ; x
  ($sw 'a1 8 '(sp)) ; y
  ($sw 'a2 12 '(sp)) ; z
  ($addi 'a0 'a0 -1)
  ($jal tak)
  ($sw 'a0 16 '(sp))
  ($lw 'a0 8 '(sp))
  ($lw 'a1 12 '(sp))
  ($lw 'a2 4 '(sp))
  ($addi 'a0 'a0 -1)
  ($jal tak)
  ($sw 'a0 20 '(sp))
  ($lw 'a0 12 '(sp))
  ($lw 'a1 4 '(sp))
  ($lw 'a2 8 '(sp))
  ($addi 'a0 'a0 -1)
  ($jal tak)
  ($mv 'a2 'a0)
  ($lw 'a0 16 '(sp))
  ($lw 'a1 20 '(sp))
  ($jal tak)
  ret
  ($lw 'ra 0 '(sp))
  ($addi 'sp 'sp 24)
  ($ret))

Run it as follows:

> (time (tak 18 12 6))
7
Time: 7 ms

Hofstadter Q sequence

This is one of several recursive sequences described in Douglas Hofstadter's book "Gödel, Escher, Bach: an Eternal Golden Braid". It is related to the Fibonacci sequence, except that in this case the two preceding terms specify how far to go back in the sequence to find the two terms to be summed:

(defun q (n)
  (if (<= n 2) 1
    (+
     (q (- n (q (- n 1))))
     (q (- n (q (- n 2)))))))

Running the Lisp version:

> (time (q 21))
12
Time: 1.6 s

Here's the assembler version:

; Hofstadter Q sequence
(defcode q (n)
  q
  ($addi 'sp 'sp -12)
  ($sw 'ra 0 '(sp))
  ($li 'a2 2)
  ($ble 'a0 'a2 ret1)
  ($sw 'a0 4 '(sp))
  ($addi 'a0 'a0 -1)
  ($jal q)
  ($lw 'a1 4 '(sp))
  ($sub 'a0 'a1 'a0)
  ($jal q)
  ($sw 'a0 8 '(sp))
  ($lw 'a0 4 '(sp))
  ($addi 'a0 'a0 -2)
  ($jal q)
  ($lw 'a1 4 '(sp))
  ($sub 'a0 'a1 'a0)
  ($jal q)
  ($lw 'a2 8 '(sp))
  ($add 'a0 'a0 'a2)
  ($j ret)
  ret1
  ($li 'a0 1)
  ret
  ($lw 'ra 0 '(sp))
  ($addi 'sp 'sp 12)
  ($ret))

Running the assembler version:

> (time (q 21))
12
Time: 13 ms

Two-dimensional recursive function Q2

This function Q2 is my two-dimensional extension of the Hofstadter Q sequence ^[1]. Here's the Lisp version:

(defun q2 (x y)
  (if (or (< x 1) (< y 1)) 1
    (+ (q2 (- x (q2 (1- x) y)) y)
       (q2 x (- y (q2 x (1- y)))))))

It's a time-consuming function to calculate. For example:

> (time (q2 8 9))
57
Time: 18.2 s

Here's the RISC-V assembler version:

(defcode q2 (x y)
  q2
  ($addi 'sp 'sp -16)
  ($sw 'ra 0 '(sp))
  ($li 'a2 1)
  ($blt 'a0 'a2 ret1)
  ($blt 'a1 'a2 ret1)
  ($sw 'a0 4 '(sp))
  ($sw 'a1 8 '(sp))
  ($addi 'a0 'a0 -1)
  ($jal q2)
  ($lw 'a1 4 '(sp))
  ($sub 'a0 'a1 'a0)
  ($lw 'a1 8 '(sp))
  ($jal q2)
  ($sw 'a0 12 '(sp))
  ($lw 'a0 4 '(sp))
  ($lw 'a1 8 '(sp))
  ($addi 'a1 'a1 -1)
  ($jal q2)
  ($lw 'a1 8 '(sp))
  ($sub 'a1 'a1 'a0)
  ($lw 'a0 4 '(sp))
  ($jal q2)
  ($lw 'a2 12 '(sp))
  ($add 'a0 'a0 'a2)
  ($j ret)
  ret1
  ($li 'a0 1)
  ret
  ($lw 'ra 0 '(sp))
  ($addi 'sp 'sp 16)
  ($ret))

Running the assembler version:

> (time (q2 8 9))
57
Time: 100 ms

Reversebits

This is a function to efficiently reverse the order of bits in a 32-bit number ^[2]. Here's the uLisp version:

(defun reversebits (x)
  (setq x (logior (ash (logand x #x55555555) 1) (logand (ash x -1) #x55555555)))
  (setq x (logior (ash (logand x #x33333333) 2) (logand (ash x -2) #x33333333)))
  (setq x (logior (ash (logand x #x0f0f0f0f) 4) (logand (ash x -4) #x0f0f0f0f)))
  (setq x (logior (ash x 24) (ash (logand x #xff00) 8)
                  (logand (ash x -8) #xff00) (logand (ash x -24) #xff))))

For example:

> (format t "~b~%" (reversebits #b10110011100011110000111110000011))
11000001111100001111000111001101
nil

Here's the assembler version, which demonstrates the use of the $li pseudo-instruction to load a 32-bit constant into a register:

; Reverse bits in a 32-bit word
(defcode reversebits (n)
  rev
  ; Swap odd and even
  ($li 'a2 #x55555555)
  ($srli 'a1 'a0 1)
  ($and 'a1 'a1 'a2)
  ($and 'a2 'a2 'a0)
  ($slli 'a2 'a2 1)
  ($or 'a0 'a1 'a2)
  ; Swap adjacent pairs
  ($li 'a2 #x33333333)
  ($srli 'a1 'a0 2)
  ($and 'a1 'a1 'a2)
  ($and 'a2 'a2 'a0)
  ($slli 'a2 'a2 2)
  ($or 'a0 'a1 'a2)
  ; Swap adjacent nibbles
  ($li 'a2 #x0f0f0f0f)
  ($srli 'a1 'a0 4)
  ($and 'a1 'a1 'a2)
  ($and 'a2 'a2 'a0)
  ($slli 'a2 'a2 4)
  ($or 'a0 'a1 'a2)
  ; Reverse all bytes
  ($li 'a2 #xff00)
  ($and 'a1 'a0 'a2)
  ($slli 'a3 'a1 8)
  ($srli 'a1 'a0 8)
  ($and 'a2 'a2 'a1)
  ($or 'a1 'a2 'a3)
  ($slli 'a2 'a0 24)
  ($srli 'a3 'a0 24)
  ($or 'a0 'a2 'a3)
  ($or 'a0 'a0 'a1)
  ($ret))

Testing it:

> (format t "~b~%" (reversebits #b10110011100011110000111110000011))
11000001111100001111000111001101
nil

Games

Bulls & Cows

The following bullcow function calculates the score between a guess and a code, represented as hexadecimal numbers with a specified number of digits. The score is returned as a two-digit hexadecimal number, bulls followed by cows, where bulls are digits correct and in the correct position (bull's-eyes), and cows are digits correct but not in the right position. Here's the Lisp version:

(defvar *spectrum* (let (lst) (dotimes (i 16 lst) (push 0 lst))))

(defun bullcow (digits guess code)
  (let ((score 0))
    (dotimes (i 16) (setf (nth i *spectrum*) 0))
    (dotimes (d digits)
      (let ((da (mod guess 16))
            (db (mod code 16)))
        (cond
         ((= da db) (incf score 16))
         (t 
          (when (<= (incf (nth da *spectrum*)) 0) (incf score))
          (when (>= (decf (nth db *spectrum*)) 0) (incf score))))
        (setq guess (truncate guess 16))
        (setq code (truncate code 16))))
    score))

For example:

> (format t "~x" (bullcow 6 #x123456 #x456430))
13

gives the result 13 (hexadecimal) because there is one bull (the 4), and three cows (the 3, 5, and 6).

Here's the assembler version:

; Bulls & Cows
(defcode bullcow (digits guess code)
  ($addi 'sp 'sp -16)
  ($li 'a4 15)
  ($li 'a7 0)
  ($li 'a3 0)
  clear
  ($add 't0 'sp 'a4)
  ($sb 'a7 '(t0))
  ($addi 'a4 'a4 -1)
  ($bgez 'a4 clear)
  digits
  ($andi 'a4 'a1 #xf)
  ($andi 'a5 'a2 #xf)
  ($bne 'a4 'a5 cows)
  bulls
  ($addi 'a3 'a3 #x10)
  ($j no2)
  cows
  ($add 't0 'sp 'a4)
  ($lb 'a6 '(t0))
  ($addi 'a6 'a6 1)
  ($sb 'a6 '(t0))
  ($bgtz 'a6 no1)
  ($addi 'a3 'a3 1)
  no1
  ($add 't0 'sp 'a5)
  ($lb 'a6 '(t0))
  ($addi 'a6 'a6 -1)
  ($sb 'a6 '(t0))
  ($bltz 'a6 no2)
  ($addi 'a3 'a3 1)
  no2
  ($srli 'a1 'a1 4)
  ($srli 'a2 'a2 4)
  ($addi 'a0 'a0 -1)
  ($bnez 'a0 digits)
  ($mv 'a0 'a3)
  ($addi 'sp 'sp 16)
  ($ret))

> (format t "~x" (bullcow 6 #x123456 #x456430))
13

List examples

Any of the arguments to a machine-code function can be a list, in which case the address of the list is passed to the routine in the corresponding register a0 to a3.

For example, if the list is the first parameter its address will be in a0, and you can then load the car of the list into a1 with:

($ld 'a1 0 '(a0))

and the cdr of the list into a1 with:

($ld 'a1 8 '(a0))

Product of list elements

The following example returns the product of all the numbers in a list:

; Product of list elements
(defvar *wordsize* 4)

(defcode product (x)
  ($li 'a2 1)
  repeat
  ($beqz 'a0 finished)
  ($lw 'a1 0 '(a0))
  ($lw 'a1 *wordsize* '(a1))
  ($mul 'a2 'a1 'a2)
  ($lw 'a0 *wordsize* '(a0))
  ($j repeat)
  finished
  ($mv 'a0 'a2)
  ($ret))

The variable *wordsize* should be 4 for the RP2350 and 8 for the K210 on the MAiX boards.

For example:

> (product '(1 2 3 4 5 6))
720

Sum of integers in a tree

The following recursive Lisp program returns the sum of all the integers in a tree:

(defun sum (tree)
  (cond
   ((null tree) 0)
   ((numberp tree) tree)
   (t (+ (sum (car tree)) (sum (cdr tree))))))

For example:

> (sum '(1 2 (3 4 (5 6 (7 8)) 9 10) 11 12))
78

Here's the equivalent assembler version:

(defvar *wordsize* 4)

(defcode sum (tree)
  sum
  ($addi 'sp 'sp -12)
  ($sw 'ra 0 '(sp))
  ($mv 'a4 'a0)
  ($sw 'a4 *wordsize* '(sp))
  ($beqz 'a0 ret)
  ($lw 'a0 0 '(a4))
  ($addi 'a1 'a0 -6)
  ($bnez 'a1 notnumber)
  ($lw 'a0 *wordsize* '(a4))
  ($j ret)
  notnumber
  ($jal sum) ; car
  ($sw 'a0 (* 2 *wordsize*) '(sp))
  ($lw 'a4 *wordsize* '(sp))
  ($lw 'a0 *wordsize* '(a4)) ;cdr
  ($jal sum)
  ($lw 'a1 (* 2 *wordsize*) '(sp))
  ($add 'a0 'a0 'a1)
  ret
  ($lw 'ra 0 '(sp))
  ($addi 'sp 'sp 12)
  ($ret))

Again, *wordsize* should be 4 for the RP2350 and 8 for the K210 on the MAiX boards.

Running the assembler version:

> (sum '(1 2 (3 4 (5 6 (7 8)) 9 10) 11 12))
78

1. ^ An erratic two-dimensional recursive function on Lispology.
2. ^ From "Hacker's Delight" by Henry S. Warren, Jr., page 129.