RISC-V assembler examples

Numeric examples

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

21st March 2020: Added the example Sum of integers in a tree.

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 Maixduino:

> (for-millis () (print (fib 27)))

196418 
8548

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

Here's the assembler version:

; Fibonacci sequence
(defcode fib (n)
  fib
  ($addi 'sp 'sp -24)
  ($sd 'ra 0 '(sp))
  ($li 't0 2)
  ($ble 'a0 't0 ret1)
  ($sd 'a0 8 '(sp))
  ($addi 'a0 'a0 -1)
  ($jal fib)
  ($sd 'a0 16 '(sp))
  ($ld 'a0 8 '(sp))
  ($addi 'a0 'a0 -2)
  ($jal fib)
  ($ld 't0 16 '(sp))
  ($addw 'a0 'a0 't0)
  ($j ret)
  ret1
  ($li 'a0 1)
  ret
  ($ld 'ra 0 '(sp))
  ($addi 'sp 'sp 24)
  ($ret))

Running the assembler version on a Maixduino:

> (for-millis () (print (fib 27)))

196418 
14

The assembler version is approximately a factor of 600 faster.

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):

> (for-millis () (print (factor 2146654199)))

46327 
687

Here's an equivalent assembler version:

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

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

> (for-millis () (print (factor 2146654199)))

46327 
3

In other words, approximately 230 times faster.

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:

> (for-millis () (print (tak 18 12 6)))

7 
1670

Here's the assembler version:

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

Run it as follows:

> (for-millis () (print (tak 18 12 6)))

7 
2

The assembler version is nearly a factor of 1000 faster.

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:

> (for-millis () (print (q 21)))

12 
2395

Here's the assembler version:

; Hofstadter Q sequence
(defcode q (n)
  q
  ($addi 'sp 'sp -24)
  ($sd 'ra 0 '(sp))
  ($li 'a2 2)
  ($ble 'a0 'a2 ret1)
  ($sd 'a0 8 '(sp))
  ($addi 'a0 'a0 -1)
  ($jal q)
  ($ld 'a1 8 '(sp))
  ($sub 'a0 'a1 'a0)
  ($jal q)
  ($sd 'a0 16 '(sp))
  ($ld 'a0 8 '(sp))
  ($addi 'a0 'a0 -2)
  ($jal q)
  ($ld 'a1 8 '(sp))
  ($sub 'a0 'a1 'a0)
  ($jal q)
  ($ld 'a2 16 '(sp))
  ($addw 'a0 'a0 'a2)
  ($j ret)
  ret1
  ($li 'a0 1)
  ret
  ($ld 'ra 0 '(sp))
  ($addi 'sp 'sp 24)
  ($ret))

Running the assembler version:

> (for-millis () (print (q 21)))

12 
4

In other words, about 600 times faster.

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:

> (for-millis () (print (q2 8 9)))

57 
14751

Here's the RISC-V assembler version:

(defcode q2 (x y)
  q2
  ($addi 'sp 'sp -32)
  ($sd 'ra 0 '(sp))
  ($li 'a2 1)
  ($blt 'a0 'a2 ret1)
  ($blt 'a1 'a2 ret1)
  ($sd 'a0 8 '(sp))
  ($sd 'a1 16 '(sp))
  ($addi 'a0 'a0 -1)
  ($jal q2)
  ($ld 'a1 8 '(sp))
  ($sub 'a0 'a1 'a0)
  ($ld 'a1 16 '(sp))
  ($jal q2)
  ($sd 'a0 24 '(sp))
  ($ld 'a0 8 '(sp))
  ($ld 'a1 16 '(sp))
  ($addi 'a1 'a1 -1)
  ($jal q2)
  ($ld 'a1 16 '(sp))
  ($sub 'a1 'a1 'a0)
  ($ld 'a0 8 '(sp))
  ($jal q2)
  ($ld 'a2 24 '(sp))
  ($addw 'a0 'a0 'a2)
  ($j ret)
  ret1
  ($li 'a0 1)
  ret
  ($ld 'ra 0 '(sp))
  ($addi 'sp 'sp 32)
  ($ret))

Running the assembler version:

> (for-millis () (print (q2 8 9)))

57 
34

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) (ash x -24))))

For example:

> (reversebits #x12345678)
510274632

where 510274632 is #x1E6A2C48, which you'll see is the right answer.

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:

> (reversebits #x12345678)
510274632

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:

> (bullcow 6 #x123456 #x456430)

gives the result #x13 (19) 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)
  clear
  ($add 't0 'sp 'a4)
  ($sb 'a7 0 '(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 0 '(t0))
  ($addi 'a6 'a6 1)
  ($sb 'a6 0 '(t0))
  ($bgtz 'a6 no1)
  ($addi 'a3 'a3 1)
  no1
  ($add 't0 'sp 'a5)
  ($lb 'a6 0 '(t0))
  ($addi 'a6 'a6 -1)
  ($sb 'a6 0 '(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))

 For more information about the game Bulls & Cows, and a uLisp program to play the game, see Bulls & Cows game.

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 r0 to r3.

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

($ldr 'r1 '(r0 0))

and the cdr of the list into r1 with:

($ldr 'r1 '(r0 4))

Product of list elements

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

; Product of list elements
(defcode product (x)
  ($li 'a2 1)
  repeat
  ($beqz 'a0 finished)
  ($ld 'a1 0 '(a0))
  ($ld 'a1 8 '(a1))
  ($mul 'a2 'a1 'a2)
  ($ld 'a0 8 '(a0))
  ($j repeat)
  finished
  ($mv 'a0 'a2)
  ($ret))

For example:

> (product '(1 2 3 4 5 6))
720
It works by multiplying the number pointed to by the car of the list by the running product (in a2), and then taking the cdr of the list, until the list is nil (zero), indicating the end of the list.

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:

(defcode sum (tree)
  sum
  ($addi 'sp 'sp -24)
  ($sd 'ra 0 '(sp))
  ($mv 'a4 'a0)
  ($sd 'a4 8 '(sp))
  ($beqz 'a0 ret)
  ($ld 'a0 0 '(a4))
  ($addi 'a1 'a0 -6)
  ($bnez 'a1 notnumber)
  ($ld 'a0 8 '(a4))
  ($j ret)
  notnumber
  ($jal sum) ; car
  ($sd 'a0 16 '(sp))
  ($ld 'a4 8 '(sp))
  ($ld 'a0 8 '(a4)) ;cdr
  ($jal sum)
  ($ld 'a1 16 '(sp))
  ($add 'a0 'a0 'a1)
  ret
  ($ld 'ra 0 '(sp))
  ($addi 'sp 'sp 24)
  ($ret))

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