Примеры

В этой Лекции рассматриваются более продвинутые темы программирования под RISC-V на примере использования структур данных (реализуется связный список) и работы с числами с плавающей запятой. Цель этой лекции - показать, как реализуются базовые алгоритмы, применяемые в вычислительной технике.

После прочтения этой лекции вы должны быть способны:

Примеры

Связный список

Связанный список - простейшая структура данных. Связный список состоит из элементов, содержащих данные, и указателей на другие аналогичные элементы. Указатель - специальная переменная, которая хранит адрес в памяти, в данном случае - адрес элемента списка. Элементы списка упорядочены в том смысле, что у каждого элемента есть потомок, связанный с текущим элементом по указателю. Есть первый элемент, называемый головой списка - указатель на самый первый элемент списка. Есть последний элемент, называемый хвостом списка - задаётся элементом без потомка, указатель на потомка у такого элемента равен нулю (нулевой указатель).

Рассмотрим список, состоящий из двух элементов, имеющих значения 0x32 и 0x12. Первый элемент расположен в памяти по адресу 0x32c0, а второй - по адресу 0x32a0. Каждый элемент содержит значение и указатель на следующий элемент (он может быть нулевым). Голова списка указывает на самый первый элемент: head = 0x32c0:

Адрес           Значение    Указатель
0x32c0:         0x32        0x32a0 
0x32a0:         0x12    0x0000

Самый простой способ вставить элемент в список - затолкнуть его в голову, при этом для каждого нового элемента требуется выделить место в памяти, что обычно делается динамически через менеджер памяти и область динамической памяти, называемой "куча". В процессе удаления элемента из списка (выталкивание) должна освободиться память. Для решения задач выделения и освобождения памяти используются C-функции malloc и free.

Элемент списка на языке Assembler может быть задан с помощью полей, которые предоставляют доступ к значению элемента списка и указателю на следующий элемент. Это делается в примере:

# linkedlist_struct.s
# offset to value
.equ node_val, 0
# offset to pointer(address) of next element
.equ node_next, 8
# size of one element
.equ node_size, 16

# calls:
# linkedlist_push 
# input> a0: head, a1: value
# output< a0: head or -1 if error

# linkedlist_pop
# input> a0: head
# output< a0: head, a1: value

# linkedlist_print
# input> a0: head

В этом примере для работы со связным список реализованы три функции: для добавления элемента в список (операция заталкивания, push), для удаления элемента из списка (операция выталкивания, pop), и для печати значений всех элементов списка от головы до хвоста. Функция push создаёт новый элемент, при этом бывшая голова списка становится потомком для только что созданного элемента, а голова (указатель на начало списка) теперь указывает на созданный элемент. Функция pop инвертирует это действие, голова списка начинает указывать на потомок текущего элемента, а сам элемент, ранее бывший головой списка, удаляется. Функция print печатает все элементы.

# linkedlist.s
.include "src/linkedlist_struct.s"
.section .text
.globl linkedlist_push
linkedlist_push:
    addi sp, sp, -24
    sd ra, 16(sp)
    sd a0, 8(sp)
    sd a1, 0(sp)

    # alloc memory
    li a0, node_size
    call malloc
    beqz a0, .L0err

    # value
    ld t1, 0(sp)
    sd t1, node_val(a0)
    # insert as new head head
    ld t0, 8(sp)
    sd t0, node_next(a0)

    # || val | next ->|| -> || ... | ... ||
    j .L0exit
.L0err:
    li a0, -1
.L0exit:
    ld ra, 16(sp)
    addi sp, sp, 24
    ret

.globl linkedlist_pop
linkedlist_pop:
    addi sp, sp, -16
    sd ra, 8(sp)
    sd s0, 0(sp)
    # if head is zero
    beqz a0, .L1err

    # return value
    ld a1, node_val(a0)
    # pointer to next element will be new head
    ld s0, node_next(a0)

    # free memory
    call free

    # return new head
    mv a0, s0
    j .L1exit
.L1err:
    li a0, -1
.L1exit:
    ld s0, 0(sp)
    ld ra, 8(sp)
    addi sp, sp, 16 
    ret

.globl linkedlist_print
linkedlist_print:
    addi sp, sp, -24
    sd ra, 16(sp)
    sd a0, 8(sp)
    sd a0, 0(sp)
.L2loop:
    beqz a0, .L2exit

    sd a0, 0(sp)
    ld a1, node_val(a0)
    la a0, .L2prompt
    call printf

    ld a0, 0(sp)
    ld a0, node_next(a0)
    j .L2loop

.L2exit:
    ld a0, 8(sp)
    ld ra, 16(sp)
    addi sp, sp, 24
    ret
.section .rodata
.L2prompt: 
    .asciz "%u \n"

Использование связного списка показано в основном коде. Элементы добавляются, удаляются, печатаются.

# main.s
.include "src/linkedlist_struct.s"
.section .text
.globl main
main:
    addi sp, sp, -8
    sd ra, 0(sp)
    # new head of list
    li s0, 0

    mv a0, s0
    li a1, 0x12
    call linkedlist_push

    li a1, 0x23
    call linkedlist_push

    li a1, 0x45
    call linkedlist_push

    call linkedlist_pop

    li a1, 0x56
    call linkedlist_push

    call linkedlist_print

    call linkedlist_pop
    call linkedlist_pop
    call linkedlist_pop

    ld ra, 0(sp)
    addi sp, sp, 8
    ret

Подсчёт среднего значения

Следующий пример показывает использование регистров для работы с числами с плавающей запятой. Она начинается с чтения дробных чисел с помощью функции scanf (строки 09-19) в память (по метке buffer). Числа с плавающей запятой занимают 4 байта. Программа в ходе своей работы подсчитывает сумму всех значений, для этой цели используются специальные регистры для работы с числами с плавающей запятой ft0, ft1 и ft3. Целочисленные значения могут быть сконвертированы в числа с плавающей запятой инструкцией fcvt.s.w (конвертирует знаковое целое длинной в слово в дробное значение), это происходит на строках 24 и 25. Второй цикл (строки 26-36) вычисляет сумму путём загрузки чисел с плавающей запятой из памяти (строка 34) и суммируя числа с сохранением результата в регистре ft1 (строка 35). Среднее значение вычисляется благодаря операции деления (строка 38). В итоге, результат печатается с использованием функции printf. Функция printf требует аргумент в виде числа двойной точности, загруженного в регистр a1, эта операция реализуется в строчках 41 и 42. Программе нужны расширения F и D, описанные в спецификации. Программе на стандартный ввод можно перенаправить данные из файла используя возможности перенаправления потоков операционной системы: average < numbers.txt.

00 # average.s
01 .equ maxNb, 100         # maximal numbers to be read
02 .section .text
03 .globl main             # run in C 'environment' 
04 main:
05     addi sp, sp, -16    # store ra (return address) and saved regs on stack
06     sd ra, 0(sp)
07     sd s0, 8(sp)
08 
09     li s0, 0            # counter numbers: i
10 .L0input:               # read in numbers
11     la a0, scanfmt
12     la a1, buffer
13     slli t0, s0, 2      # next input in buffer+4*i
14     add a1, a1, t0
15     call scanf          # read float number
16     blez a0, .L0avg    # if no number could be read anymore, continue..
17     addi s0, s0, 1      # count numbers read in s0: i = i + 1
18     li t0, maxNb        # if i < maxNb, continue reading
19     blt s0, t0, .L0input
20 
21 .L0avg:
22     beqz s0, .L0err # check if at least one number is read, else exit
23 
24     fcvt.s.w ft0, s0    # divider: convert from int in s0 to float
25     fcvt.s.w ft1, x0    # sum: init with zero, convert from x0
26 .L0avgloop:
27     beqz s0, .L0out     # count down s0 to zero: i = i - 1
28     addi s0, s0, -1
29 
30     slli t1, s0, 2      # compute address to float number in memory
31     la t0, buffer
32     add  t0, t0, t1
33 
34     flw ft2, 0(t0)      # load from memory to float register ft2
35     fadd.s ft1, ft1, ft2    # sum in ft1
36     j .L0avgloop
37 .L0out:
38     fdiv.s ft1, ft1, ft0    # average in ft1
39 
40     la a0, resultfmt    # print result using printf
41     fcvt.d.s ft1, ft1   # need to prepare for printf, expand to double size
42     fmv.x.d a1, ft1     # move from ft1 to a1
43     call printf         # and print
44 
45 .L0err:
46     li a0, 0
47 
48     ld s0, 8(sp)
49     ld ra, 0(sp)        # restore ra
50     addi sp, sp,16
51     ret                 # return to caller
52 
53 .section .rodata
54 scanfmt:
55 .asciz "%f"
56 resultfmt:
57 .asciz "Average: %f\n"
58 
59 .section .bss
60 buffer:
61 .zero 4*maxNb