Кадр стека и системные вызовы

Зачем нужен кадр

Как правило, подпрограмме необходимо хранить какие-то данные в памяти. Это, во-первых, сохраняемые значения регистров, во-вторых — параметры и возвращаемые значения подпрограммы, если их больше, чем соответствующих регистров, а в-третьих — разнообразные значения, для которых в процессе планирования вычислений не оказалось свободного регистра. Данные, которые подпрограмма временно хранит в памяти, называются локальными переменными.

Если подпрограмма использует много локальных переменных, описанная ранее конвенция оказывается довольно неудобной:

   1 .text
   2 # подпрограмма, вычисляющая сумму и произведение двух чисел,
   3 # и хранящая их все на стеке без использования кадра, ПОТОМУ ЧТО ТАК НАДО
   4 main:   li      a7 5
   5         ecall
   6         mv      s0 a0
   7         li      a7 5
   8         ecall
   9         mv      a1 s0
  10         jal     mulsum
  11         mv      a1 s0
  12         li      a7 1
  13         ecall
  14         mv      a0 s0
  15         li      a7 1
  16         ecall
  17         li      a7 10
  18         ecall
  19 
  20 mulsum: addi    sp sp -4
  21         sw      ra (sp)         # Адрес возврата
  22         addi    sp sp -4
  23         sw      a0 (sp)         # Первая переменная
  24         addi    sp sp -4
  25         sw      a1 (sp)         # Вторая переменная
  26         # Какой-то код, который портит регистры
  27         lw      t0 4(sp)        # Первая переменная
  28         lw      t1 (sp)         # Вторая переменная
  29         add     t2 t0 t1
  30         addi    sp sp -4
  31         sw      t2 (sp)         # Сумма (смещения переменных поехали)
  32         # Какой-то код, который портит регистры
  33         lw      t0 8(sp)        # Первая переменная (да-да!)
  34         lw      t1 4(sp)        # Вторая переменная (ну хоть тут понятно)
  35         mul     t2 t0 t1
  36         addi    sp sp -4
  37         sw      t2 (sp)         # Произведение
  38         # Какой-то код, который портит регистры
  39         lw      a1 (sp)         # Произведение
  40         lw      a0 4(sp)        # Сумма
  41         lw      ra 20(sp)       # Эммм… сколько там переменных было?
  42         addi    sp sp 20        # Вроде не ошибся!
  43         addi    sp sp 4
  44         ret

Возникает идея хранить в специально отведённом регистре (он называется Frame Pointer, fp) состояние sp на момент вызова функции. Тогда для восстановления sp перед возвратом из функции достаточно будет переложить туда значение fp. Предыдущее значение fp при этом тоже надо будет сохранять на стеке, т. к. кадр локален для каждого вызова функции.

Пример конвенции с использованием кадра

Как обычно, в конвенции присутствует преамбула и восстановление стека, то есть код, дополнительно выполняемый вызывающей стороной, а также пролог и эпилог, то есть код, дополнительно выполняемый подпрограммой. Они заметно расширились — за удобство платим объёмом кода.

  1. (преамбула) Передаваемые подпрограмме значения надо заносить в регистры a*

  2. (преамбула) Если передаваемых параметров больше 8, все остальные необходимо положить в стек в обратном порядке (последний, предпоследний, … десятый, девятый)
  3. Вызов подпрограммы должен производиться командой jal или jalr

  4. Никакая вызываемая подпрограмма не модифицирует содержимое стека выше того указателя, который она получила в момент вызова (напомним, что «выше» — это ближе к началу)
  5. (пролог) Подпрограмма обязана сохранить на стеке значение fp (старый кадр) в первую очередь. Сохранение производится стандартно: расширить стек на 4, записать fp.

  6. (пролог) Значение sp, каким оно на этот момент стало, подпрограмма обязана записать в fp

  7. (пролог) Подпрограмма обязана сохранить на стеке значения ra и всех используемых ею регистров типа s*

  8. (пролог) Подпрограмма обязана выделить на стеке память для всех локальных переменных
  9. Подпрограмма может хранить на стеке произвольное количество временных данных. Количество этих данных и занимаемого ими места на стеке не оговаривается и может меняться в процессе работы подпрограммы. Такие данные, например, могут образоваться в преамбуле вызова подпрограммы при размещении параметров в стеке. Локальные переменные рекомендуется размещать в пределах кадра.

  10. Возвращаемое подпрограммой значение надо заносить в регистры a0,1

  11. (эпилог) Подпрограмма обязана восстановить из стека сохранённые значения всех регистров, кроме fp

  12. (эпилог) Подпрограмма обязана сбросить кадр путём восстановления sp из fp

  13. (эпилог) Подпрограмма обязана восстановить из стека сохранённое значение fp. Восстановление производится стандартно: прочитать значение fp, передвинуть вершину стека на 4.

  14. Возврат из подпрограммы должен производиться командой ret

  15. (очистка стека) Если передаваемых параметров было больше 8, необходимо поднять указатель стека на нужное смещение

Согласно такой конвенции:

Стоит заметить, что и эта конвенция

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

Более того, использование кадра удобно в первую очередь для программирования на языке ассемблера «вручную». Именно восстановление стека из fp позволяет в процессе работы подпрограммы сохранять на нём произвольное количество дополнительных данных. Это может потребоваться при разработке сложного алгоритма, когда регистров общего назначения внезапно перестало хватать.

Однако компилятор с любого языка программирования более высокого уровня планирует регистры автоматически, и, как следствие, всегда заранее знает, сколько места на стеке потребуется данной подпрограмме. В таком случае в использовании fp нет нужды: в прологе sp увеличивается на вычисленную константу — планируемый объём памяти на стеке, а в эпилоге — уменьшается.

Подпрограмма с использованием кадра

Это подпрограмма, сортирующая методом обмена массив целых размером a0 байтов (т. е. a0/4 элементов), лежащий по адресу a1. Подпрограмма не концевая — она вызывает ещё одну подпрограмму, поиск минимального элемента в массиве.

   1 sort:   # общая подпрограмма
   2         # a0 — размер массива
   3         # a1 — начало массива
   4         # a0 — размер выходного массива (того же самого :)
   5         # a1 — начало выходного массива
   6 .eqv    .RA     -4(fp)          # Смещения в кадре
   7 .eqv    .S1     -8(fp)          #   для сохраняемых регистров
   8 .eqv    .S2     -12(fp)
   9 .eqv    .ARR    -16(fp)         # Смещения в кадре
  10 .eqv    .SIZE   -20(fp)         #   для локальных переменных
  11 .eqv    FSIZE   20              # Размер кадра (+ 4 на сам fp)
  12         addi    sp sp -4        # Сохраним кадр
  13         sw      fp (sp)
  14         mv      fp sp           # Зададим новый кадр
  15         addi    sp sp -FSIZE    # Переставляем стек
  16         sw      ra .RA          # Сохраняем регистры
  17         sw      s2 .S2     
  18         sw      s1 .S1     
  19 
  20         sw      a0 .SIZE        # Размер массива
  21         sw      a1 .ARR         # Адрес массива
  22 
  23         mv      s2 a0           # Регистры типа s* не меняются
  24         mv      s1 a1           # при вызовах функций
  25 fnext:  mv      a0 s2
  26         mv      a1 s1
  27         jal     getmin
  28         lw      t0 (a0)
  29         lw      t1 (s1)
  30         sw      t0 (s1)
  31         sw      t1 (a0)
  32         addi    s1 s1 4
  33         addi    s2 s2 -4
  34         bgtz    s2 fnext
  35 
  36         lw      a0 .SIZE        # Обращаемся к локальным переменным
  37         lw      a1 .ARR
  38 
  39         lw      ra .RA          # Восстанавливаем регистры
  40         lw      s2 .S2     
  41         lw      s1 .S1     
  42         mv      sp fp           # Восстанавливаем стек
  43         lw      fp (sp)         # Восстанавливаем предыдущий кадр
  44         addi    sp sp 4
  45         ret

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

   1 getmin: # концевая подпрограмма
   2         # a0 — размер массива
   3         # a1 — начало массива
   4         # a0 — адрес минимального элемента
   5         lw      t0 (a1)
   6         mv      t2 a1
   7 gmnext: addi    a0 a0 -4
   8         addi    a1 a1 4
   9         blez    a0 gmfin
  10         lw      t1 (a1)
  11         bge     t1 t0 gmnext
  12         mv      t0 t1
  13         mv      t2 a1
  14         j       gmnext
  15 gmfin:  mv      a0 t2
  16         ret

Вся программа

Обратите внимание на последовательную реализацию пункта конвенции «сначала сохранить fp, потом разместить кадр». Сделать это одним действием, как в примере пролога ниже, нельзя:

   1 # пример некорректного пролога функции
   2         sw      fp -4(sp)       # сохраним fp
   3         addi    sp sp FSIZE     # разместим кадр

Дело в том, что sp в любой момент работы программы обязан указывать или на вершину стека, или за неё — иными словами, мы не можем рассчитывать на сохранность данных за пределами текущего стека. Это связано с механизмом асинхронных прерываний (он будет в нашем курсе).

При обработке прерывания выполнение программы приостанавливается в произвольном месте, и управление передаётся отдельно объявленной подпрограмме-обработчику, а после её завершения выполнение текущей программы возобновляется с того же места. При использовании плоской модели памяти и в отсутствие режима супервизора (как в RARS и других малых архитектурах, например, на микроконтроллерах) обработчику доступна та же самая память, и что более важно — тот же самый стек, что и основной программе. Если в примере выше прерывание произойдёт между инструкциями sw и addi, и обработчик решит положить что-то на стек, лежащее в этом месте значение fp будет затёрто.

Промышленные конвенции

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

Правда, даже для таких условий эти конвенции неполны:

Чем сложнее описываемый конвенцией случай, тем сложнее изобрести универсальную договорённость. Ниже пример нескольких документов, содержащий несколько версий «живых» ABI (application binary inverface), что соответствует части конвенций по вызову подпрограмм и запуску программ.

Наконец, полноценный ABI, в отличие от «договорённостей» предназначен не только и не столько для людей-программистов, сколько для системных программ, занимающихся исходным и машинным кодом

Системные вызовы

Строго говоря, не вполне понятно, кто именно исполняет ecall: никакие регистры (кроме оговоренных) не меняются, код вызываемой подпрограммы нам недоступен и т. п. Например, в RARS ecall — это вообще функции Java.

В большинстве случаев ecall — это обращение к ядру «операционной системы», однако что именно называется операционной системой — такой же код, только в режиме супервизора, обращение к системе виртуализации в обход ядра, непосредственно к аппаратуре и т. п.

В целом можно сказать, что программа запрашивает какие-то данные из «окружения», в котором она выполняется. Отсюда и название — Environment Call.

Операционная система

Задачи операционной системы: унификация, разделение и учёт ресурсов компьютера. Для взаимодействия с ОС программа следует некоторым соглашениям, называемым ABI (Application Binary Interface).

Под ресурсами поминаются оперативная память, процессорное время и разнообразные внешние устройства.

Программный интерфейс использования ресурсов — системные вызовы — предоставляет т. н. ядро ОС

Ядро операционной системы — программный код, постоянно находящийся в памяти, имеющий доступ ко всем ресурсам компьютера и реализующий дисциплину их использования.

Аппаратная поддержка

Итак:

Вариант: «системный вызов»

Вариант с обобщением «функция окружения», или ecall:

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

И в случае syscall, и в случае ecall эта функция обычно реализована аппаратно, отдельной инструкцией.

Функции окружения RARS

Описаны в документации по RARS.

TODO Есть HTML?

Время от времени будем называть ecall по-старинке: cистемный вызов сист— механизм программного обращения к ядру операционной системы. На архитектурах, имеющих аппаратную поддержку режима ядра, реализован отдельной инструкцией.

Конвенции по вызову ecall в RISC-V

  1. В регистр a7 помещается номер системной функции (service number)

  2. В регистры a* или fa* (для вещественных чисел) помещаются параметры системного вызова, если есть

  3. Инструкция ecall передаёт управление операционной системе (обычно ядру, но, например, в RARS это может быть сразу сам RARS)

  4. Возврат из системного вызова — по аналогии с возвратом из подпрограммы, на следующую после ecall инструкцию

  5. Возвращаемые значения (если есть) помещаются в a* или в fa0 в соответствии с работой вызванной системной функции

Механизм работы ecall со стороны ядра ОС может быть разным.

Пример: вывести на консоль число, лежащее в регистре t0

   1     li  a7 1            # Функция 1 — вывод числа
   2     mv  a0 t0
   3     ecall               # Введённое число помещается в a0

Некоторые системные вызовы RARS

Функция

Тип
a7

Параметры

Возвращаемое значение

вывод целого

1

a0 = целое

вывод вещественного

2

fa0 = вещественное

вывод вещественного двойной длины

3

fa0 = двойное вещественное

вывод строки

4

a0 = адрес ASCIIZ-строки

ввод целого

5

a0 — введённое целое (word)

ввод вещественного

6

fa0 — введённое вещественное (float)

ввод двойного вещественного

7

fa0 — введенное двойное вещественное (double)

ввод строки

8

a0 = адрес памяти для размещения строки
a1 = размер буфера

Если строка короче буфера, все её символы записываются в буфер (включая '\n', если он был), после чего туда дописывается нулевой байт. Если строка не короче буфера, в него записывается первые a1-1 символов, а в последний оставшийся байт записывается 0 Таким образом формируется ASCIZ-строка

выделение памяти в Куче (sbrk)

9

a0 = размер требуемой памяти в байтах

a0 ­— адрес требуемой памяти

останов (exit)

10

вывод символа

11

a0 = символ

Некоторые управляющие символы, например, перевод строки (код 10) тоже имеет смысл выводить

ввод символа

12

a0 — считанный символ (традиционно в RARS работает отвратительно, не рекомендуется ☹)

системное время (time)

30

Время выдаётся в милисекундах с начала мира (полночь на 1 января 1970 года), так что помещается как длинное целое в два слова a1 = старшее слово a0 = младшее слово

приостановка выполнения (sleep)

32

a0 = время простоя в милисекундах.

вывод шестнадцатеричного

34

a0 = целое

вывод двоичного

35

a0 = целое

вывод беззнакового

36

a0 = целое

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

Однако в RARS есть и уже совсем откровенные обращения к «вышестоящему окружению»: работа с устройствами и сущностями, полностью отсутствующими в архитектуре ЭВМ, на которой работает программа.

Например:

Работа со строками

Пример работы со строками: подсчёт количества пробелов во введённой строке.

   1 .eqv    SIZE 100                # размер буфера
   2 .data
   3 str:    .space SIZE             # буфер
   4 .text
   5         la      a0 str          # считаем строку в буфер
   6         li      a1 SIZE
   7         li      a7 8
   8         ecall
   9         mv      t0 zero         # счётчик пробелов
  10         li      t2 0x20         # пробел
  11 loop:   lb      t1 (a0)         # очередной символ
  12         beqz    t1 fin          # нулевой — конец строки
  13         bne     t1 t2 nosp      # не пробел — обойдём счётчик
  14         addi    t0 t0 1         # пробел — увеличим счётчик
  15 nosp:   addi    a0 a0 1         # следующий символ
  16         b       loop
  17 fin:    mv      a0 t0           # выведем счётчик
  18         li      a7 1
  19         ecall
  20         li      a7 10
  21         ecall

В качестве эксперимента можно попробовать воспользоваться вызовом 54 для ввода строки и вызовом 56 для вывода целого.

Заказ памяти у системы

Статическая память выделяется при трансляции секций .data . В результате трансляции в определённых областях оперативной памяти (по умолчанию — начиная с 0x10010000) резервируются области, которые затем доступны с помощью меток или непосредственно по адресам. Области могут быть инициализированы начальными значениям (как в .word, .asciz и т. п.), а могут остаться без изменения (как в .space). Добавление новых директив резервирования памяти в секцию .data приведёт к тому, что соответствующие ячейки окажутся после уже отведённых.

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

В других случаях память необходимо выделять на всё время работы программы, но размер их заранее неизвестен. Один раз это можно сделать, воспользовавшись в качестве базового адреса началом кучи — 0x10040000. Однако в дальнейшем придётся где-то хранить вершину кучи, чтобы следующая область динамически выделяемой на куче памяти не пересекалась с предыдущей.

В RARS этим занимается операционная система. Системный вызов 9, которому в a0 передаётся объём заказываемой памяти, отведёт на куче соответствующую область и вернёт в a0 её адрес. Следующий вызов ecall 9 вернёт адрес после уже заказанной области и т. д.

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

Подпрограмма принимает в a0 объём памяти, а возвращает в a0 выделенный адрес, выводя сообщение об этом.

   1 newmem: li      a7 9            # Закажем память (объём уже в a0)
   2         ecall
   3         addi    sp sp -4
   4         sw      a0 (sp)         # Сохраним адрес
   5         li      a7 34           # Выведем адрес (a0 уже задан)
   6         ecall                   # как 16-ричное число
   7         li      a0 10           # Выведем перевод строки
   8         li      a7 11
   9         ecall
  10         lw      a0 (sp)         # Вспомним адрес
  11         addi    sp sp 4
  12         ret

Напишем программу, которая трижды просит у системы память, причём один раз — нечётного объёма в байтах:

   1 .globl main
   2 main:   li      a0 0x100       # Закажем 256 байтов
   3         jal     newmem
   4         li      a0 0x101       # закажем 257 байтов
   5         jal     newmem
   6         li      a0 0x100       # Закажем опять 256 байтов
   7         jal     newmem

Несмотря на кажущуюся простоту операции, освобождать память в куче для повторного использования намного сложнее. Рассмотрим общую задачу выделения/освобождения памяти (т. н. memory management).

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

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

Д/З

Для решения задач можно использовать связку «макрос+подпрограмма», а можно не использовать. Советую всё-таки использовать — чтобы убедиться в том, насколько структуризация и повторное использование делает исходные тексты понятнее и сопровождаемее.

  1. Написать комплект «макрос+подпрограмма» для функция работы со строками. Формат вызова, точный список функций и логика их работы на ваше усмотрение.
    • Пример реализации (все параметры — это регистры, которые перед вызовом подпрограммы копируются в соответствующие a*-регистры):

      Макрокоманда

      Параметр 1

      Параметр 2

      Описание

      a0

      a1

      strlen

      Адрес

      Определение длины ASCIZ-строки

      Длина строки

      strget

      Ввод ASCIZ-строки длиной не более 100 байтов. Ввод происходит в статический буфер, далее для строки выделяется соответствующее место на куче, и она копируется туда (\n, если есть, из строки удаляется, в конец обязательно записывается 0)

      Адрес выделенной памяти

      Длина строки

      strcpy

      Приёмник

      Источник

      (Небезопасно) копирует ASCIZ-источник по адрсу «приёмник»

      Приёмник

      Длина строки

      strcmp

      Адрес 1

      Адрес 2

      Лексикографическое сравнение ASCIZ-строк. Возвращает отрицательное число, если первая строка меньше, положительное, если больше и ноль, если строки равны.

      Результат

      strchr

      Адрес 1

      Байт

      Возвращает адрес первого вхождения символа char в строку по адресу addr1 или 0, если символ в строке отсутствует

      Адрес 2

    • Напоминаю, что в ecall 8 параметр a1 — это именно размер буфера, включая \0 в его конце. Символов вводится при этом на 1 меньше.

    • Ещё один вариант — отказаться от использования a*-регистров в тексте программы и предусмотреть в макросах копирование результатов оттуда. Например strlen %регистр_адреса %регистр_длины будет копировать %регистр_адреса в a0, вызывать внутреннюю подпрограмму, реализующую strlen, получать в a0 длину и записывать её в %регистр_длины

    • В части с макросами можно понаписать всякого удобного: отладочную выдачу, push/pop, ecall одной строкой (причём с разным количеством параметров!) и, разумеется, пролог и эпилог подпрограммы

    • Макросы, библиотеку подпрограмм и основной текст main (не забываем про .globl main) удобно хранить в разных файлах и использовать многофайловую сборку, однако в силу специфики EJudge для решения Д/З всё надо складывать в один файл.

TODO EJudge

  1. EJudge: SameLines 'Повторение строк'

    Ввести строку-шаблон, затем вводить строки примеры; окончание ввода — пустая строка. Вывести в виде «Duplicates: число» количество строк-примеров, совпадающих с шаблоном. Все входные строки короче 100 байтов.

    Input:

    QWEqwe
    as
    QWEqwe!
    QWEqw
    QWEqwe
    a
    QWEqwe
    QWEqweQWEqwe
    Output:

    Duplicates: 2
    • Вот так выглядит моё решение (без макросов и библиотеки):
         1 .include        "string.inc"    # В Д/З сюда надо вставить string.inc и string.asm
         2 .globl  main
         3 .data
         4 buf:    .space  STRSIZE         # 101
         5 .text
         6 main:   li      s3 0
         7         strget  s1 s2           # jal _strget; a0→s1 (aдрес), a2→s2 (длина)
         8         la      s4 buf
         9         li      s5 STRSIZE      # 101
        10 loop:   syscall 8 s4 s5         # s4→a0, s5→a1; ecall 8
        11         strip   s4 '\n'         # Вспомогательная процедура удаления хвостового '\n'
        12         strlen  s4 t6           # s4→a0; jal _strlen; a0→t6
        13         beqz    t6 done
        14         strcmp  s1 s4 t0        # s1→a0, s4→a1; jal _strcmp; a0→t0
        15         bnez    t0 loop
        16         addi    s3 s3 1
        17         b       loop
        18 done:   print.w "Duplicates: " s3 # Удобно для отладки, но и тут пригодилось
        19         syscall 10
      
      • Я воспользовался собственным советом и включил в параметры макросов регистры, в которые сохраняется результат
  2. EJudge: LongestLine 'Наибольшая среди длинных'

    Вводить строки (длина строки не превышает 100, последняя строка пустая). Вывести строку наибольшей длины. Если таких несколько, вывести лексикографически наибольшую.

    Input:

    QWER
    qwerqwer
    as
    asdfsdff
    wqerq
    qwerzxcv
    asdf
    sdf
    Output:

    qwerzxcv
  3. EJudge: FindChars 'Символы из строки'

    Ввести строку-шаблон, а затем вводить строки-примеры; конец ввода — пустая строка. Вывести все строки-примеры, в которых есть хотя бы один символ из строки-шаблона. длина строк меньше 100.

    Input:

    qwetyuqweuqwuer
    asdfhashdfasdhf
    zxcbvzbxcvbzxcrvb
    asdhfashdfasdh
    zxcbvzxbcvbzxcvq
    asdfasdfasdf
    zxcvzxcvzxcv
    fasfasfasdef
    tqtqeerqwerqwe
    zxcvzxvczxcv
    wefqwefqwef
    czxcvzxcvzxc
    Output:

    zxcbvzbxcvbzxcrvb
    zxcbvzxbcvbzxcvq
    fasfasfasdef
    tqtqeerqwerqwe
    wefqwefqwef
  4. EJudge: StringSort 'Сортировка строк'

    Старая добрая сортировка обменом. Ввести натуральное число N — количество строк, а затем — N строк. Вывести их в лексикографическом порядке возрастания. Длина строк меньше 100.

    Input:

    12
    qwetyuqweuqwuer
    asdfhashdfasdhf
    zxcbvzbxcvbzxcrvb
    asdhfashdfasdh
    zxcbvzxbcvbzxcvq
    asdfasdfasdf
    zxcvzxcvzxcv
    fasfasfasdef
    tqtqeerqwerqwe
    zxcvzxvczxcv
    wefqwefqwef
    czxcvzxcvzxc
    Output:

    asdfasdfasdf
    asdfhashdfasdhf
    asdhfashdfasdh
    czxcvzxcvzxc
    fasfasfasdef
    qwetyuqweuqwuer
    tqtqeerqwerqwe
    wefqwefqwef
    zxcbvzbxcvbzxcrvb
    zxcbvzxbcvbzxcvq
    zxcvzxcvzxcv
    zxcvzxvczxcv

LecturesCMC/ArchitectureAssembler2022/05_FrameSyscalls (last edited 2022-04-25 07:25:43 by FrBrGeorge)