# Написание программы под процессор CYBERcobra

Чтобы максимально "прочувствовать" принцип работы созданного вами процессора, вам необходимо написать один из [вариантов программ](#индивидуальные-задания). Вариант выдаётся преподавателем.

Порядок выполнения задания следующий:

1. В первую очередь необходимо ознакомиться с заданием и изучить пример, приведённый в конце задания. Если возникли вопросы по заданию или примеру, свяжитесь с преподавателем. Чем лучше вы понимаете, что от вас ожидают, тем проще будет выполнить задание.
2. Составьте алгоритм работы программы (буквально возьмите листочек, и нарисуйте блок-схему). Прежде чем вы погрузитесь в увлекательное приключение с ноликами и единицами, вам нужно составить четкую карту вашего путешествия.
3. Проверьте вашу блок-схему на данных из примера. Если все сошлось, проверьте вашу блок-схему на других данных. Не забывайте про краевые случаи (отрицательные числа, деление на ноль, переполнения и прочее — для каждого задания они могут быть разными).
4. После того как вы убедились в работоспособности алгоритма на всех возможных данных, наступает время претворить его в виде двоичной программы.
5. Программа описывается в текстовом файле. Для удобства был написан специальный конвертер, который будет принимать на вход текстовый файл с комментариями и двоичным кодом, разделённым пробелами, а на выход выдавать текстовый файл, которым можно будет проинициализировать память инструкций. Подробнее о конвертере смотрите в параграфе [cyberconverter](#cyberconverter). Пример текстового файла, который сможет принять конвертер:

    ```text
    //J B WS ALUop  RA1   RA2   const     WA
      0 0 00   11111111111111111111111  00001  // загрузить константу -1 в регистр 1
      0 0 10   00000000000000000000000  00010  // загрузить значение с входа sw_i в регистр 2
      0 0 00   00000000000000000000001  00011  // загрузить константу 1 регистр 3
      0 0 01 00000 00001 00011 00000000 00001  // сложить регистр 1 с регистром 3 и поместить результат в регистр 1
      0 1 00 11110 00001 00010 11111111 00000  // если значение в регистре 1 меньше значения в регистре 2, возврат на 1 инструкцию назад
      1 0 00 00000 00001 00000 00000000 00000  // бесконечное повторение этой инструкции с выводом на out_o значения в регистре 1
    ```

6. При реализации условных переходов следует иметь в виду пару правил:
   1. Блок ветвления (аналог `if/else`) состоит из двух наборов инструкций:
      1. инструкции блока `if` (если условие выполнилось)
      2. инструкции блока `else` (если условие не выполнилось)

      При этом сразу за инструкцией ветвления описываются инструкции блока `else` (т.к. в случае невыполнения условия перехода, `PC` перейдёт к следующей инструкции).  
      Для того, чтобы после выполнения инструкций блока `else` не начались исполняться инструкции блока `if`, в конце блока этих инструкций необходимо добавить безусловный переход на инструкцию, следующую за инструкциями блока `if`.
   2. Если вы реализуете не ветвление (аналог блока `if/else`), а только проверку условия для выполнения какого-то блока инструкций (аналог блока `if` без блока `else`), вы должны помнить, что блок `else` всё равно есть, просто в этом блоке нет инструкций. Однако вы, как и в прошлом правиле, должны добавить безусловный переход на инструкцию, следующую за инструкциями блока `if`.  
      Этого можно избежать, если инвертировать ваше условие. В этом случае, если ваше инвертированное условие выполнится, вы сможете сразу пропустить нужное количество инструкций и начать исполнять инструкцию за пределами вашего блока `if`. Если инвертированное условие не выполнится (т.е. выполнится исходное условие), `PC` перейдёт к следующей инструкции, где и будут находиться ваши инструкции блока `if`.  
      Звучит достаточно запутанно, поэтому давайте рассмотрим пару примеров. Сначала мы запишем нашу идею на языке Си, а затем перенесём её в двоичный код под архитектуру CYBERcobra:

      ```C
      if(reg[1]==reg[5])
      {
        reg[2] = 10;
        reg[3] = 15;
      }
      else
      {
        reg[2] = 7;
        goto if_end;  // Поскольку в памяти программы блок else будет идти
                      // сразу за инструкцией условного перехода, необходимо
                      // добавить в конце инструкцию безусловного перехода,
                      // чтобы не начать исполнять инструкции блока if.
      }
      if_end:
      ```

      Мы хотим проверить на равенство значения в регистровом файле по адресам `1` и `5`. Если это так, записать значения `10` и `15` по адресам `2` и `3` соответственно. В противном случае, записать значение `7` по адресу `2`.  
      Это можно реализовать следующей двоичной программой:

      ```text
      //J B WS ALUop  RA1   RA2   const     WA
        0 1 00 11000 00001 00101 00000011 00000 // Если регистры 1 и 5 равны,
                                                // перемести PC на 3 инструкции вперёд
                                                // (перешагни через две
                                                // инструкции блока else)
      //---------------------------------------
      // блок else
      //---------------------------------------
        0 0 00   00000000000000000000111  00010 // reg[2] = 7
        1 0 00 00000 00000 00000 00000011 00000 // goto if_end
      //---------------------------------------


      //---------------------------------------
      // блок if
      //---------------------------------------
        0 0 00   00000000000000000001010  00010 // reg[2] = 10
        0 0 00   00000000000000000001111  00011 // reg[3] = 15
      //---------------------------------------

        0 0 00   00000000000000000000000  00000 // некая инструкция с меткой if_end
                                                // куда будет перемещен PC после
                                                // выполнения блока else
      ```

      Рассмотрим второй пример, где нет блока `else`:

      ```C
      if(reg[1] == reg[5])
      {
        reg[2] = 10;
        reg[3] = 15;
      }
      ```

      Как упоминалось ранее, можно реализовать этот условный переход по той же схеме (тогда пример программы на Си примет вид):

      ```C
      if(reg[1] == reg[5])
      {
        reg[2] = 10;
        reg[3] = 15;
      }
      else
      {
        goto if_end;
      }
      if_end:
      ```

      А можно инвертировать условие:

      ```C
      if(reg[1] != reg[5])
      {

      }
      else
      {
        reg[2] = 10;
        reg[3] = 15;
      }
      ```

      В этом случае, нет нужды делать безусловный переход на инструкцию, следующую за инструкциями блока `if`, т.к. там нет никаких инструкций.  
      Такое условие можно реализовать следующей двоичной программой:

      ```text
      //J B WS ALUop  RA1   RA2   const     WA
        0 1 00 11001 00010 00101 00000011 00000 // Если регистры 2 и 5 НЕ РАВНЫ,
                                                // перемести PC на 3 инструкции вперед
                                                // (перешагни через две
                                                // инструкции блока else)
      //---------------------------------------
      // блок else
      //---------------------------------------
        0 0 00   00000000000000000001010  00010 // reg[2] = 7
        0 0 00   00000000000000000001111  00011 // reg[3] = 15
      //---------------------------------------
      ```

7. В двоичном программировании, реализация циклов лучше всего делается аналогом `do while` в Си (если вы уверены, что первая итерация цикла гарантированно пройдёт условие выхода из цикла). В этом случае, вы сперва описываете тело цикла, а затем через условный переход возвращаетесь обратно к началу тела цикла. Если условие не выполнилось, вы автоматически выйдете из цикла.
8. Для того, чтобы в конце выполнения программы было легко увидеть результат выполнения, в конец программы необходимо добавить инструкцию безусловного перехода, поле `const` которой равно нулю. В этом случае, будет выполняться `PC=PC+0` что приведёт к повторению этой инструкции снова и снова. При этом в поле `RA1` необходимо указать адрес регистра, где хранится результат. На временной диаграмме это отобразится так, что в какой-то момент все сигналы процессора "замрут", а на выходе `out_o` окажется результат, вычисленный вашей программой.
9. После того, как вы написали программу, её необходимо проверить. Для этого сперва необходимо преобразовать её к формату, принимаемому памятью инструкций с помощью программы [`cyberconverter`](#cyberconverter). При необходимости, заменить данные в файле, инициализирующем память инструкций актуальными данными.
10. Если ваша программа использует данные с внешних устройств, нужно выставить проверяемое вами значение в модуле `testbench` на вход `sw_i` в месте подключения модуля `CYBERcobra`.
11. Проверка работы программы осуществляется аналогично проверке модуля `CYBERcobra` — вы достаете внутренние сигналы модуля, и смотрите за поведением сигналов: `PC`, `read_data` памяти инструкций, `flag` АЛУ, содержимым регистрового файла. Проверяете, что в конце на выходе `out_o` размещено корректное значение.

## cyberconverter

[cyberconverter](cyberconverter.cpp) — это программа, которая преобразует текстовый файл с инструкциями архитектуры CYBERcobra в текстовый файл, который сможет принять память инструкций.

cyberconverter может обрабатывать файлы, содержащие комментарии (начинающиеся с `//`), пробелы и пустые строки, а также наборы символов `0` и `1`. Комментарии, пробелы и пустые строки удаляются, после чего оставшиеся строки из 32 нулей и единиц конвертируются в шестнадцатеричные значения и записываются в выходной файл.

cyberconverter принимает до двух аргументов. Порядок запуска следующий:

1. Вызов справки:

    ```bash
    cyberconverter -h
    cyberconverter --help
    ```

2. Преобразование программы, записанной в файле `test.txt`, с записью результата в файл `program.mem`:

    ```bash
    cyberconverter test.txt program.mem
    ```

3. Если не указан второй аргумент, результат будет записан в файл:
 `<имя_исходного_файла>_converted.<расширение исходного файла>`:

    ```bash
    cyberconverter test.txt
    ```

     Результат будет записан в файл `test_converted.txt`.

4. Если программа будет запущена без аргументов, то исходным файлом будет считаться файл `program.mem`.

В случае отсутствия исходного файла, наличия неподдерживаемых символов или неверной длины инструкции будет выведено сообщение об ошибке.

## Индивидуальные задания

В приведённых ниже заданиях под `a` будет подразумеваться некоторое число, заданное в программе (например в программе прописано `a=10`), под `sw_i` — вход с внешних устройств. "Вывести в `out_o`" — означает, что в конце программы необходимо реализовать бесконечный цикл, с указанием в `RA1` адреса регистра, хранящего результат (см. пункт 8 параграфа "[Написание программы под процессор CYBERcobra](#написание-программы-под-процессор-cybercobra)").

В случае, если задание используется для написания программы на ассемблере, `sw_i` будет обозначать ещё одно число, заданное в программе (как и `a`), а под "Вывести в `out_o`" — запись результата в регистр `x10` (в назначение этого регистра входит возврат результата функции) в конце выполнения программы.

1. Вычислить [циклический сдвиг](https://ru.wikipedia.org/wiki/Битовый_сдвиг#Циклический_сдвиг) вправо `a >> sw_i`.  
Пример: `a = 0...01011`, `sw_i = 0...010`.  
Результат вычислений: `out_o = 110...010`.  

2. Вычислить `a - sw_i` без использования операции вычитания.  
Пример: `sw_i = 0...011`, `a = 0...0100`.  
Результат вычислений: `out_o = 0...001`.

3. Вычислить [циклический сдвиг](https://ru.wikipedia.org/wiki/Битовый_сдвиг#Циклический_сдвиг) влево `a << sw_i`.  
Пример: `a = 10...01011`, `sw_i = 0...10`.  
Результат вычислений: `out_o = 0...0101110`.  

4. Поменять местами `[7:0]` и `[15:8]` биты числа `sw_i`. Вывести результат в `out_o`.  
Пример: `sw_i = 0...010100000_1110010`.  
Результат вычислений: `out_o = 0...011100101_10100000`.   

5. Вычислить приблизительное значение длины вектора `(a;sw_i)`. Вычисляется как `max + min/2`, где `max` и `min` — это большее и меньшее из чисел `a` и `sw_i` соответственно.  
Пример: `a = 0...011`, `sw_i = 0...0100`.   
Результат вычислений: `out_o = 0...0101`.  

---

6. Вычислить `a * sw_i` посредством суммы `sw_i` значений `a`. Вывести результат в `out_o`.  
Пример: `a = 5`, `sw_i = 4`. `5 * 4 == 5 + 5 + 5 + 5 = 20`.  
Результат вычислений: `out_o = 0...010100`.

7. Если `sw_i[1:0] == 00`, то в `out_o` выводится `a`,  если `sw_i[1:0] == 01`, то `b`,  если `sw_i[1:0] == 10`, то `c`,  если `sw_i[1:0] == 11`, то `d`.   
Пример: `a = 0...00`, `b = 0...010`, `c = 0...011`, `d = 0...001`, `sw_i[1:0] = 01`.   
Результат вычислений: `out_o = 0...010`.  

8. Посчитать длину окружности при заданном радиусе `sw_i`, считая, что `pi = 3`. Вывести результат в `out_o`.   
Пример: `sw_i = 0...010`.  
Результат вычислений: `out_o = 0...01100`.  

9. Если `sw_i` является степенью двойки, то вывести `out_o =  0...01`, в противном случае, `out_o = 0...0`.   
Пример 1: `sw_i = 0...0100`. Результат вычислений: `out_o = 0...01`.   
Пример 2: `sw_i = 0...0110`. Результат вычислений: `out_o = 0...00`.

10. Найти количество нулей в двоичном представлении числа `sw_i`. Вывести результат в `out_o`.   
Пример: `sw_i = 1...10110_0010`.   
Результат вычислений: `out_o = 0...0101`.

11. Найти наибольший двоичный разряд числа `sw_i`, значение которого равно `1`. Если такого нет, вывести `32`. Вывести результат в `out_o`.   
Пример: `sw_i = 0...0110`.   
Результат вычислений: `out_o = 0...010`.  

12. Сформировать число, состоящее из чётных двоичных разрядов числа `sw_i`. Вывести результат в `out_o`.   
Пример: `sw_i = 0...011_1011_1000`.   
Результат вычислений `out_o = 0...01_0100`.  

13. Найти количество единиц в двоичном представлении числа `sw_i` (обратите внимание, `sw_i` – знаковое число). Вывести результат в `out_o`.   
Пример: `sw_i = 0...0101_0110`.   
Результат вычислений: `out_o = 0...0100`.  

14. Найти количество двоичных разрядов, в которых различаются числа `sw_i` и `a`. Вывести результат в `out_o`.   
Пример: `sw_i = 0...0110`, `a = 0...01110`.   
Результат вычислений: `out_o = 0...01`.  

15. Вывести в `out_o` подряд все единицы входного числа `sw_i`.   
Пример: `sw_i = 0...01011011011`.   
Результат вычислений:`out_o` = `0...01111111`.  

16. Вывести в `out_o` значение выражения: `out = (k*a + b) + c`, где `k` — это `sw_i[15:12]`, `a` — это `sw_i[11:8]`, `b` — это `sw_i[7:4]`, `c` — это `sw_i[3:0]`.  
Пример: `sw_i = 0...0011_0010_0100_0011`.   
Результат вычислений: `out_o = 0...01101`.   

---

17. Найти остаток от деления `sw_i` на `a`. Вывести результат в `out_o`.   
Пример: `sw_i = 0...0101`, `a = 0...010`.   
Результат вычислений: `out_o = 0...01`.   

18. Найти и вывести в `out_o` количество вхождений `a[2:0]` в `sw_i` без пересечений.   
Пример: `a[2:0] = 010`, `sw_i = 0...01101_0101`.   
Результат вычислений: `out_o = 0...01`.  

19. Определить, сколько раз встречается `11` в двоичном представлении `sw_i` без пересечений. Вывести результат в `out_o`.   
Пример: `sw_i = 0...01110`.    
Результат вычислений: `out_o = 0...01`.  

20. Вывести в `out_o` результат целочисленного деления `a/sw_i`.   
Пример: `sw_i = 0...010`, `a = 0...0111`.   
Результат вычислений: `out_o = 0...011`.  

21. Вывести в `out_o` сумму `sw_i[3:0]` + `sw_i[7:4]` + `sw_i[11:8]` + `sw_i[15:12]`.   
Пример: `sw_i[15:0] = 0001_0010_0011_0000`.    
Результат вычислений: `out_o = 0...0110`.  

22. В числе `sw_i` заменить справа-налево каждое `00` на `11`. Вывести результат в `out_o`.   
Пример: `sw_i = 1...101000`.    
Результат вычислений: `out_o = 1...101011`.  

---

23. Поменять местами чётные биты числа `sw_i` с нечётными битами этого числа (то есть соседние биты поменять местами). Вывести результат в `out_o`.   
Пример: `sw_i = 0...01010_0111`.   
Результат вычислений: `out_o = 0...0101_1011`.  

24. Инвертировать первые `sw_i` бит числа `a`. Вывести результат в `out_o`.   
Пример: `sw_i = 0...011`, `a = 0...01010_0011`.   
Результат вычислений: `out_o = 0...01010_0100`.  

25. Вывести n-ый член [последовательности Фибоначчи](https://ru.wikipedia.org/wiki/Числа_Фибоначчи) Fn. n = `sw_i`. Вывести результат в `out_o`.   
Пример: `sw_i = 0...0100`.   
Результат вычислений: `out_o = 0...010`.  

26. Поменять в числе `a` разряды `i = sw_i[4:0]` и `j = sw_i[9:5]`. Вывести результат в `out_o`.   
Пример: `a = 0...01001`, `sw_i[9:0] = 00000_00001`. Значит, в числе `а` необходимо поменять местами `а[0]` и `a[1]`.   
Результат вычислений: `out_o = 0...01010`.  

---

27. Вычислить `a * sw_i` с использованием операций сложений и сдвига ("в столбик"). Вывести результат в `out_o`.   
[Пример](https://en.wikipedia.org/wiki/Binary_multiplier#Binary_long_multiplication): `a = 0...01011`, `sw_i[9:0] = 0...01110`.   
Результат вычислений: `out_o = 0...010011010`.  
```  
       1011   (11 в двоичном виде)
     x 1110   (14 в двоичном виде)
     ======
       0000   (это 1011 x 0)
      1011    (это 1011 x 1, сдвинутое на 1 влево)
     1011     (это 1011 x 1, сдвинутое на 2 влево)
  + 1011      (это 1011 x 1, сдвинутое на 2 влево)
  =========
   10011010   (154 в двоичном виде)
```

28. Вывести в `out_o` n-ый член [арифметической прогрессии](https://ru.wikipedia.org/wiki/Арифметическая_прогрессия) aN, где `a1 = a`, `d = sw_i[15:8]`, `n = sw_i[7:0]` (d и n неотрицательные).   
Пример: `sw_i[15:8] = 0000_0010`, `sw_i[7:0] = 0000_0011`, `a = 0...01`.   
Результат вычислений: `out_o = 0...0101`.  

<!-- 25. *Зажечь все светодиоды на 50% яркости ([подсказка](http://wiki.amperka.ru/конспект-arduino:шим)) -->

29. Удалить все вхождения `sw_i[2:0]` из `a` со сдвигом вправо (заполняя удалённые области).   
Пример: `a = 0...010011010`, `sw_i[2:0] = 101`.  
Результат вычислений: `out_o = 0...010010`
