Моделирование структур данных

На примере работы со стеком и кадром хорошо виден главный недостаток программирования в машинных кодах и на языке Ассемблера — отсутствие готовых моделей для популярных абстрактных данных, таких как структуры, связные списки, деревья и т. д. Попытка внедрить такие модели в синтаксис языка ассемблера неминуемо нарушит его главное свойство: «прозрачность» трансляции инструкций в машинные команды.

Однако заниматься моделированием структур данных время от времени приходится. Эта тема не прибавит новых фактов к нашему знанию об архитектуре ЭВМ, зато мы составим представление о том, как абстрактные типы данных могут быть организованы на уровне машинных кодов и линейно адресуемой памяти. Кроме того, необходимо попрактиковаться в написании различных простых алгоритмов перед тем, как мы возьмёмся рассматривать более сложные аппаратные механизмы, в которых эти алгоритмы, возможно, придётся использовать.

Нас будут интересовать два вопроса:

Нет ли в реализации относительно простых типов данных каких-нибудь особенностей, которые накладывает архитектура? (особенности есть)
Насколько трудоёмко делать на языке ассемблера алгоритмическую поддержку более сложных типов данных? (ожидаемо сложно, но выполнимо)

Массивы

Разговаривая о косвенной адресации, мы уже рассматривали массивы простых типов (машинных слов, полуслов и байтов).

Все данные одного размера (более того — одного типа)
- В языке ассемблера нет возможности отличить целое число от вещественного одинарной точности: они имеют одинаковый размер
Все данные размещены в памяти непрерывно
Количество данных строго ограничено т. н. верхним индексом массива — номером последнего элемента, после которого, возможно, находятся другие данные
⇒ операция индексирования (нахождения элемента по номеру) в массиве очень эффективна:
- Адрес_элемента_k = Адрес_начала_массива + k * размер_одного_элемента
- (манипуляция с индексами и размером элемента носит название адресной арифметики)

Массивы можно представлять многомерными, но реализуются они всё равно как непрерывный фрагмент памяти. От одномерного массива многомерный отличается только способом индексации.

Двумерный массив (матрица)

Имеет две координаты — абсциссу x и ординату y
Характеризуется двумя верхними индексами — шириной M и высотой N матрицы
Содержит M*N элементов
Адрес A_xy элемента массива A с координатами x,y:
- A_xy=A+(x+y*M)*b, где b — размер элемента в байтах
- такой массив располагается в памяти построчно (сначала нулевая строка матрицы, потом первая и т. д.)

Для многомерного массива:

Каждый элемент характеризуется группой индексов (координатами) фиксированной для данного массива размерностью d
По каждой из координат зафиксирован наибольший индекс W₀, W₁, …, W_d-1
Адрес элемента массива A_X0X1…Xd-1^= A+(X₀+(X₁+(X₂+…+(X_d-1)*W_d-2)…)*W₁)*W₀))*b

Операция поиска элемента в массиве размера N требует в среднем N/2 сравнений, если елемент в массиве еть, и ровно N сравнений, если его там нет:

   1 .data
   2 arrayN: .word 10                # Длина массива
   3 array:  .word 1 3 5 7 9 11 13 15 17 19 21
   4 
   5 .text
   6         la      a0 array
   7         lw      a1 arrayN
   8         li      a2 13           # Искомый элемент
   9         call    afind           # Вызов подпрограммы
  10         li      a7 1
  11         ecall
  12         li      a7 10
  13         ecall
  14 
  15 # Поиск value в массиве array длиной width
  16 # Возвращается индекс, если элемент найден, иначе — -1
  17 afind:  # array width value → position
  18         li      t1 0            # Инициализация: Индекс
  19 anext:  lw      t0 (a0)         # Очередной элемент массива
  20         beq     t0 a2 adone     # Искомый элемент найден
  21         addi    a0 a0 4         # Изменение: адрес элемента
  22         addi    t1 t1 1         # Изменение: индекс
  23         blt     t1 a1 anext     # Проверка условия: индекс меньше длины
  24         li      t1 -1           # Элемент не найден, надо вернуть  -1
  25 adone:  mv      a0 t1
  26         ret

В этом примере массив имеет длину 10, а в директиве .word — 11 элементов. Значит, последнее число в ней (21) не принадлежит массиву и не должно быть найдено ( проверьте!)

Стек

Свой собственный стек (LIFO, Last In — First Out) можно реализовать с помощью массива практически так же, как организован стек для подпрограмм. Если заданный вручную стек будет расти вверх, а не вниз, как системный, к его элементам можно будет обращаться как к элементам обычного массива. Всё, что потребуется дополнительно — это знание о том, сколько элементов находится в нём в данный момент, например, в виде адреса вершины стека (первой незанятой ячейки в нём).

Как и в массиве, операция поиска по стеку, в котором находится N элементов, требует в среднем N/2 сравнений, если искомый элемент в нём есть, и ровно N — если его там нет
Добавление элемента на вершину собственного стека и снятие элемента оттуда так же эффективны, как и в случае системного: достаточно однократно записать / прочитать значение и изменить адрес вершины

Работая со стеком как с хранилищем данных, мы можем захотеть, чтобы указатель на вершину хранился в отдельном регистре, хотя бы временно — тогда его эффективность станет идентична эффективности системного. Платой за это будет запрет на использование этого регистра где бы то ни было ещё.

Стек также можно использовать и как обычный массив, разделяя его ячейки на «занятые» (от корня стека до его вершины) и «свободные» (от вершины до выделенной границы).

Появляется возможность записывать значение не только на вершину стека, но и вообще в произвольное место. Правда, в отличие от работы с вершиной, такая операция будет требовать перестановки сразу нескольких элементов массива (в среднем — половины). В самом деле, чтобы вставить некоторой значение на позицию K в массив из N элементов, необходимо сделать так, чтобы K-я ячейка массива была не занята — «сдвинуть» часть элементов массива:

Увеличить N до N+1
Переставить N-й элемент на N+1-е место
Переставить N-1-й элемент на N-е место
…
Переставить K+1-й элемент на K+2-е место
Переставить K-й элемент на K+1-е место

Только после этого можно на освободившееся K-е место вписывать новое значение.

FrBrGeorge/MyDict/speech_balloon_question.png В алгоритме выше мы начинаем сдвиг с конца массива. А можно ли было начать с K-го элемента и сдвигать до конца?

   1 .eqv    SSIZE   128             # Размер стека (не используется)
   2 
   3 # Положить регистр %register на вершину стека %top
   4 .macro  push    %top %register
   5         addi    %top %top 4
   6         sw      %register -4(%top)
   7 .end_macro
   8 
   9 # Снять с вершины стека %top значение в регистр
  10 .macro  pop     %top %register
  11         lw      %register -4(%top)
  12         addi    %top %top -4
  13 .end_macro
  14 
  15 # Вставить значение %register в массив %stack перед позицией %index
  16 # Массив — это стек, вершина которого указана параметром %top
  17 .macro  insert  %top %index %stack %register
  18         mv      a0 %top
  19         mv      a1 %index
  20         la      a2 %stack
  21         mv      a3 %register
  22         call    insert_sub
  23         mv      %top a0
  24 .end_macro
  25 
  26 # Удалить элемент массива %stack в позиции %index
  27 # Массив — это стек, вершина которого указана параметром %top
  28 .macro  delete  %top %index %stack
  29         mv      a0 %top
  30         mv      a1 %index
  31         la      a2 %stack
  32         call    delete_sub
  33         mv      %top a0
  34 .end_macro
  35 
  36 .data
  37         .align  2
  38 stack:  .space  SSIZE
  39 .text
  40         la      s11 stack               # Указатель на вершину нашего стека
  41         li      t0 16
  42 mloop:  push    s11 t0                  # Положим на стек 16 чисел (16…1)
  43         addi    t0 t0 -1
  44         bgtz    t0 mloop
  45         pop     s11 t0                  # Снимем со стека два значения
  46         pop     s11 t0
  47         li      s2 -5
  48         li      s1 8
  49 miloop: insert  s11 s1 stack s2         # Добавим 5 чисел в позиции 8 (-5…-1)
  50         addi    s2 s2 1
  51         bltz    s2 miloop
  52         li      s2 5
  53         li      s1 4
  54 mdloop: delete  s11 s1 stack            # Удалим 5 чисел в позиции 4
  55         addi    s2 s2 -1
  56         bgtz    s2 mdloop
  57         li      a7 10
  58         ecall
  59 
  60 # Процедура удаления элемента в позиции index из массива stack с вершиной стека в top
  61 delete_sub:     # top index stack
  62         slli    a1 a1 2                 # Превращаем индекс в смещение в байтах
  63         add     a1 a1 a2                # Адрес удаляемого элемента
  64         mv      t1 a1
  65 dloop:  bgeu    t1 a0 ddone             # Пока не добрались до вершины стека…
  66         lw      t0 (t1)                 # Копируем следующий элемент на место предыдущего
  67         sw      t0 -4(t1)
  68         addi    t1 t1 4
  69         j       dloop
  70 ddone:  addi    a0 a0 -4                # Сдвигаем и возвращаем вершину стека
  71         ret
  72 
  73 # Процедура добавления элемента value перед позицией index массива stack с вершиной в top
  74 insert_sub:     # top index stack value
  75         slli    a1 a1 2
  76         add     a1 a1 a2                # Адрес места вставки
  77         mv      t1 a0                   # Начало с вершины стека
  78         addi    a0 a0 4                 # Сдвигаем вершину стека
  79 iloop:  bltu    t1 a1 idone             # Пока не добрались до места вставки
  80         lw      t0 -4(t1)               # Копируем текущий элемент в следующий
  81         sw      t0 (t1)
  82         addi    t1 t1 -4
  83         j       iloop
  84 idone:  sw      a3 (t1)                 # Записываем value в освободившуюся ячейку
  85         ret

Здесь мы применили приём «макрос + подпрограмма» — в тексте программы вызов соответствующей операции над массивом занимает одну строку, но макрос всего лишь подготавливает вызов подпрограммы, и обрабатывает результат.
Можно было бы нарисовать красивую диаграмму — как переставляются значения в массиве, но лучше всего — пройти программу пошагово в RARS, наблюдая все эти перестановки в окне «Data Segment».

Переполнение, опустошение и выход за вершину стека

Приведённая выше реализация стека эффективна, однако требует довольно жёсткой дисциплины использования, так как в ней не проверяются различные варианты выхода за его границы.

Выход за границы стека — это ситуация, при которой при работе со стеком данные записываются или читаются по адресам за пределами диапазона от начала до вершины стека.

Можно различить опустошение стека — попытку снять больше данных, чем есть на нём в данный момент (например, pop из пустого стека);
переполнение — попытку положить на стек больше данных, чем помещается в области между вершиной и границей массива, который отведён на стек (например, push в заполненный стек)
выход за пределы стека при чтении из соответствующего массива с ошибочным индексом

Чаще всего сам выход за границы происходит намного позже актуальной ошибки работы со стеком, и в другом месте программы. При работе с системным стеком это настолько опасно, что был изобретён механизм кадра.

Для того, чтобы ваш код не испортил стек, соблюдайте правило:

Кто и сколько на стек кладёт, тот столько оттуда и снимает

FrBrGeorge/MyDict/speech_balloon_question.png В качестве самостоятельного упражнения модифицируйте подпрограммы в примере выше так, чтобы исключить все три ситуации. Насколько изменится их эффективность? (нажмите «Комментарии» в шапке страницы, чтобы прочитать спойлер)

Структура и массив структур

Структура: набор разнотипных данных, размещённых подряд в оперативной памяти.

О структурах имеет смысл говорить по двум причинам.

Во-первых, структуры повсеместно используются для моделирования всевозможных составных данных. Это могут быть учётные карточки (фамилия, имя, год рождения), элементы абстрактных типов данных (узел дерева или связного списка), записи в базе данных (другое название структур — «записи»). Все наборы одной и той же структуры имеют одинаковый размер, поэтому из них удобно составлять массивы, работа с которыми отличается от работы с массивами, например, целых чисел только размером элемента.

Во-вторых, аппаратное представление структуры требует особого внимания, потому что разнотианые данные могут потребовать выравнивания, и это влияет на размер структуры.

3 машинных слова	4 машинных слова	3 машинных слова с упаковкой

В первом случае нам «повезло», и два полуслова «упаковались» в одно машинное слово без выравнивания. Размер струтуры оказался 12 байтов, а смещение полей «ширина», «цвет», «№» и «высота» внутри неё — 0, 4, 6 и 8 байтов соответственно (обратите внимание на порядок!)
Во втором случае для каждого полуслова ассемблер автоматически подставил ещё полуслово заполнителя, потому что целочисленные поля нуждаются в выравнивании адреса на границу, кратную 4. Смещения полей внутри структуры — 0, 4, 8 и 12, а суммарный размер — 16 байтов.
Третий случай — нестандартный. Мы можем программно «запихать» целое число в четыре байта, начиная с адреса, не кратного 4. В нашем случае для этого число надо разбить на два полуслова и записывать их по отдельности. Так же по отдельности будет реализовано и чтение из такой структуры. Бывает изредка нужно для экономии байтов данных.

В ассемблере RARS нет возможности уведомить программиста о том, происходило ли выравнивание или нет, и какими оказались смещения, так что рассчитывать приходится только на знания. То же самое относится и к суммарному размеру структуры.

   1 # Смещения в структуре card
   2 .eqv    card.width      0
   3 .eqv    card.color      4
   4 .eqv    card.num        6
   5 .eqv    card.height     8
   6 .eqv    card            12      # Размер всей структуры
   7 
   8 .macro  randint %min %max
   9         li      a0 0
  10         li      a1 %max
  11         addi    a1 a1 -%min
  12         li      a7 42
  13         addi    a0 a0 %min
  14         ecall
  15 .end_macro
  16 
  17 .data
  18         .align  2
  19 array:  .space  60              # Массив структур
  20 .text
  21         li      t1 5
  22         la      t2 array
  23 loop:   randint 500 1000
  24         sw      a0 card.width(t2)
  25         randint 0 255
  26         sh      a0 card.color(t2)
  27         randint 1 300
  28         sh      a0 card.num(t2)
  29         randint 1000 2000
  30         sw      a0 card.height(t2)
  31         ecall
  32         addi    t2 t2 card
  33         addi    t1 t1 -1
  34         bgtz    t1 loop

Пройдите эту программу пошагово и посмотрите, как заполняется оперативная память

Кольцевой буфер: очередь

Классический стек с очень большой натяжкой подходит для моделирования другого абстрактного типа данных — очереди (FIFO, First In — First Out). Дело в том, что в очереди определены две операции — добавление в хвост и снятие с головы¹. И если взять из очереди так же эффективно, как снять со стека, то добавить в корень стека «стоит» довольно дорого: предварительно на до сдвигать все его элементы.

Поможет простая, но остроумная идея — т. н. кольцевой буфер.

Кольцевой буфер

Массив фиксированного размера N, в котором определены два адреса: начало буфера head и конец буфера tail.

Операция добавления в буфер — это заполнение элемента в позиции tail и перестановка tail на следующий элемент
Операция взятия из буфера — это чтение элемента в позиции head и перестановка head на следующий элемент
Если после увеличения head или tail выходит за пределы массива, он начинает указывать на его начало

Таким образом в кольцевом буфере есть «занятое» место, между head и tail, и свободное, между tail и head, причём одно из них «перваливает» через конец буфера, продолжаясь в начале:

Добавление и взятие из очереди	Добавление с перестановкой хвоста очереди в начало

Строго говоря, у кольцевого буфера больше эффективных операций, чем у очереди: и добавление, и взятие элементов с обоих сторон буфера требует фиксированного числа команд, и не зависит от количества элементов в нём.

Главное усложнение по сравнению с реализацией стека: если для стека в примитивном случае достаточно одного выделенного регистра, то для очереди и двух будет мало: каждая операция должна проверять, не перевалил ли индекс за границу очереди, и переставлять его в начало. Поэтому опишем структуру, состоящую из размера очереди, её головы, хвоста и массива с элементами. Макросы и подпрограммы будут получать адрес такой структуры.

   1 .macro  queue   %size
   2 .data
   3         .word   %size           # Размер
   4         .word   0               # Индекс головы
   5         .word   0               # Индекс хвоста
   6         .space  %size           # Массив элементов
   7         .space  %size
   8         .space  %size
   9         .space  %size
  10 .end_macro
  11 
  12 # Поставить константу %i в очередь %queue
  13 .macro  puti    %queue %i
  14         la      a0 %queue
  15         li      a1 %i
  16         call    put_q
  17 .end_macro
  18 
  19 # Взять из очереди %queue значение и тут же его вывести
  20 .macro  getout  %queue
  21         la      a0 %queue
  22         call    get_q
  23         li      a7 1
  24         ecall
  25         li      a0 '\n'
  26         li      a7 11
  27         ecall
  28 .end_macro
  29 
  30 .data
  31 Q:      queue   8
  32 .text
  33         puti    Q 11
  34         puti    Q 12
  35         puti    Q 13
  36         getout  Q
  37         puti    Q 14
  38         puti    Q 15
  39         puti    Q 16
  40         getout  Q
  41         getout  Q
  42         puti    Q 17
  43         puti    Q 18
  44         puti    Q 19
  45         getout  Q
  46         li      a7 10
  47         ecall
  48 
  49 put_q:  # queue value
  50         lw      t1 (a0)         # размер
  51         lw      t2 8(a0)        # хвост
  52         addi    t3 a0 12        # массив
  53         slli    t4 t2 2         # смещение в массиве
  54         add     t3 t3 t4        # адрес хвоста
  55         sw      a1 (t3)
  56         addi    t2 t2 1         # сдвиг хвоста
  57         blt     t2 t1 putn      # не превысили размер
  58         li      t2 0            # перевалили за конец
  59 putn:   sw      t2 8(a0)        # обновили хвост
  60         ret
  61 
  62 get_q:  # queue
  63         lw      t1 (a0)         # размер
  64         lw      t2 4(a0)        # голова
  65         addi    t3 a0 12        # массив
  66         slli    t4 t2 2         # смещение в массиве
  67         add     t3 t3 t4        # адрес головы
  68         addi    t2 t2 1         # сдвиг головы
  69         blt     t2 t1 getn      # не превысили размер
  70         li      t2 0            # перевалили за конец
  71 getn:   sw      t2 4(a0)        # обновили голову
  72         lw      a0 (t3)         # Прочитаем элемент
  73         ret

В ассемблере RARS нет вычислений периода компиляции — чтобы получить массив из %size четырёхбайтных элементов, просто повторим .space %size четырежды.

TODO FrBrGeorge/MyDict/speech_balloon_question.png Чтобы более наглядно увидеть под отладчиком, как «вращается» кольцевой буфер, добавьте в процедуру get_q «затирание» взятого из очереди элемента (например, заполните только что освобождённую ячейку значением -1).

Понятие «кода ошибки»

При работе с очередью (в отличие от стека) ситуации переполнения и опустошения — штатные. Очередь используется, если нельзя предсказать как часто и когда именно элементы будут в неё вставать и выходить. Пользователя надо предупреждать о том, что операция закончилась неуспешно. С другой стороны, если дисциплина программирования достаточно жёсткая, в таком предупреждении необходимости нет. Следовательно, вариант «с предупреждением» должен быть совместимым по API² с простым вариантом.

Вспомним, что согласно конвенции о передаче параметров возвращаемых значений может быть два — в регистре a0 и в регистре a1. Используем регистр a1 для передачи т. н. кода ошибки — информации о том, был ли вызов успешен (в этом случае возвращается 0) или нет (в этом случае возвращается число, соответствующее типу нештатной ситуации).

FrBrGeorge/MyDict/speech_balloon_question.png Модифицируйте функции из примера выше так, чтобы put_q возвращало в a1 число 1 при попытке переполнить очередь (в остальных случаях — 0), а get_q возвращало в a1 число 1 при попытке взять элемент из пустой очереди (в остальных случаях — 0).

FrBrGeorge/MyDict/speech_balloon_question.png Какие ещё нештатные ситуации могут возникнуть при вызове этих функций? (нажмите «Комментарии» в шапке страницы, чтобы прочитать спойлер)

Во избежание двусмысленности мы не будем применять термины «начало» и «конец» очереди, ибо мнения о том, что из них — голова, а что — хвост, различаются! (1)
API, application programming interface, в нашем случае — конвенция о передаче параметров в конкретную подпрограмму и возврате значений (2)

LecturesCMC/ArchitectureAssemblerProject/15_DataStructures (последним исправлял пользователь FrBrGeorge 2024-08-21 11:08:49)