Автоматное программирование – новая веха или миф?

Тема автоматного программирования ( AP, АП) уже много лет занимает заметное место в научно-популярных СМИ. Однако, несмотря на это, АП не стало магистральным трендом. Главная причина здесь — недостаточный опыт использования, и как следствие, отсутствие популяризаторов. Нельзя сказать, что недостаточно статей посвященных АП, но круг обсуждаемых в статьях вопросов по большому счёту сводится к описанию UML Statechart, т.е. инструменту описания автоматов, либо к вопросу «Как реализуются программные автоматы?». Это печально но факт, отсутствует обсуждение того, какие перспективы для программистов-профессионалов открываются при использовании данной технологии.

Эта статья – попытка взглянуть на программаты глазами прагматика, на примере задачи, взятой из реальной практики программирования микроконтроллеров. Однако она может заинтересовать не только embedderов, поскольку автоматный подход может эффективно использоваться для создания и драйверов и интерактивных приложений в системах основанных на обработке событий, как например Windows.

Основное преимущество автоматного подхода проявляется на этапе проектирования ПО. Автоматный подход позволяет грамотно и наглядно проектировать программы, которые по окончании проектирования могут быть реализованы совсем не как автоматы (о способах реализации автоматов мы поговорим в следующей части), а как классические структурные конструкции.

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

Рисунок 1. Общая структура цифровых автоматов

Где:

• комбинационная схема (КС) – цифровая логическая схема, не содержащая внутри себя элементов памяти. Т.е. её состояние определяется только тем, что у неё на входе.
• Входы КС условно делятся на две группы I(n) – внешние сигналы (входы автомата), S(n) – внутреннее состояние автомата на текущем шаге. Внутреннее состояние это, образно говоря, некий «режим», определяющий то, как автомат будет преобразовывать внешние сигналы I(n) в сигналы O(n). У классической комбинационной схемы (нет группы входов S(n)) такой «режим» только один.
• Выходы КС тоже делятся на две группы O(n) – сигналы, выходящие вовне, которые собственно и выполняют «полезную работу», S(n+1) внутреннее состояние для следующего шага. То есть, на каждом шаге автомат в зависимости от входного сигнала I(n) не только вычисляет нужный выходной сигнал O(n), но и включает себе режим обработки сигналов на следующий шаг (т.е. сигналов I(n+1) ), причём при необходимости этот режим может быть тем же самым или другим. Иными словами, можно задать требуемые режимы на любые возможные случаи последовательностей входных сигналов, что и делает автоматы столь «всемогущими».
• С целью синхронизации вводится запоминающее устройство (ЗУ, параллельный регистр) которое отделяет в цепи обратной связи слово относящееся к предыдущему шагу, от слова относящегося к следующему. Символы n и n + 1 означают текущий шаг, и следующий шаг, т.е. n соответствует не временной оси, а последовательности шагов. Шаги задаются тактовым сигналом, и через тактовый сигнал осуществляется привязка к временной оси. Шаги могут быть связаны не с периодическим тактовым сигналом, а с событием «приход сигнала I».
• Аналогичное запоминающее устройство, для той же цели вводится в канал входных сигналов I

Если вы не были знакомы с автоматами, при всей ясности объяснения польза от таких устройств не очевидна, но существует математическая абстракция, хорошо иллюстрирующая суть. Работу автомата можно наглядно описать при помощи диаграммы состояний и переходов. Ниже изображена диаграмма, описывающая работу устройства, управляющего лифтом. Это очень упрощённая диаграмма, не учитывающая процессы открытия/закрытия дверей, разгона/остановки, но она даёт наглядное представление о том, как при помощи автоматов моделируется работа объектов реального мира. Над стрелками пишется условие, при котором произойдёт переход, в овале пишется
название_состояния/что_будет_на_выходе_пока_автомат_в_этом_состоянии.

Рисунок 2. Пример диаграммы состояний и переходов

К сказанному выше добавлю, что на диаграмме показан автомат Мура. Состояние выходов такого автомата зависит от текущего состояния. Альтернатива – автомат Мили. Его выходной сигнал зависит от последнего совершённого перехода, поэтому что_будет_на_выходе записывается над соответствующей стрелкой. Несмотря на это различие автоматы Мили и Мура математически преобразуются друг в друга. Для наших познавательных целей больше подходят автоматы Мура, но в практике программирования полезны обе абстракции, поэтому в следующей части мы не обойдём вниманием и автоматы Мили.

Все более-менее сложные цифровые схемы проектируются именно как цифровые автоматы. Почему? Незаменимости автоматного подхода при проектировании цифровых схем способствуют три основных преимущества автоматного подхода:

• Декомпозиция.
• Взгляд на процессы не как на последовательность шагов, а как на совокупность всех возможных шагов.
• Математика.

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

Часть 1. Практическая декомпозиция.

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

Мы рассматриваем практическое автоматостроение, поэтому в первой части под декомпозицией будем понимать не математическую декомпозицию, а разбиение автомата в соответствии со здравым смыслом. Во второй части будут даны примеры математической декомпозиции.

Автоматы обычно разбиваются на операционные и на управляющие. Смысл очевиден из названия — операционный автомат это «руки», управляющий – «голова». Причём разбиение может быть многоуровневым: операционный автомат в свою очередь может быть разбит на исполнительную и руководящую части. Т.е. рука-манипулятор, может иметь свой «минимозг», транслирующий общие команды («взять предмет») в набор детальных команд, управляющих каждым «пальцем». Ещё более показательным примером является процессор, имеющий конвейеры, регистры, ALU и FPU – операционные автоматы и микропрограмму – управляющий автомат.

Рисунок 3. Декомпозиция автомата на операционный и управляющий

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

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

a)

б)

в)

Рисунок 4. Требования к модулю вывода на дисплей

Все символы в шрифте одной высоты, но шрифт может быть поменян «на лету», в процессе вывода одной и той же строки. Аналогично могут быть поменяны атрибуты – жирный, курсив, подчёркивание. Для управления параметрами используются esc-последовательности, к которым относится управляющий символ 'n', перевод строки, т.е. текст одной строки может быть выведен на несколько строк на дисплее. Например текст:

"Text 1 33[7m Text 2  33[27m  33[1m Text 3 33[21m n Text 42"

будет отображаться так, как это показано на иллюстрации (рис.4, б)

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

Нам нужно создать функцию, которая всё это реализует, с прототипом

void Out_text(int x0, int y0, int x1, int y1, int x_shift, int y_shift, char * Text);

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

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

Процесс создания программной реализации итерационный, сначала реализуется самый нижний уровень модели (разработанной сверху вниз), затем разрабатывается следующий уровень, параллельно корректируется нижележащий, после чего разработка переходит к более высокому уровню, с корректировкой нижележащих по необходимости. Грамотное проектирование требует минимальной переработки нижележащих уровней, ограничиваясь их дополнением. Окончательная реализация автоматов в виде программного кода осуществляется после составления всех автоматов, но тем не менее наброски алгоритмов выполняются параллельно проектированию автоматов. Все нижележащие выкладки были выполнены мной не после составления программы, как иллюстрация, а до создания программного кода, как важный этап проектирования. Итак, приступим к разработке.

Как следует из условия задачи, исходная последовательность символов в общем случае выглядит как: Текст1 упр1 Текст2 упр2 Текст3 упр3 Текст4 упр4 Текст5
где упрN управляющие esc-последовательности, символы перевода и окончания строки которые отделяют друг от друга текстовые блоки. Разбивка текста на блоки удобна тем, что позволяет в рамках одного блока использовать максимальное количество одинаковых настроек (например высота текста и координаты начала строки).

Разработка пары ОА-УА всегда начинается с разработки ОА. ОА строится на основе наших попыток смоделировать все аспекты процесса, которым будет управлять наш автомат. В случае с дисплеем мы имеем пару самостоятельных аспектов: разбиение текста на разделённые управляющими последовательностями блоки и сборку графических данных в буфере, который будет сброшен в видеопамять. Следовательно, автомат будет состоять из двух подавтоматов, изображённых на рис. 5.

Рисунок 5. Первоначальное разбиение

Необходимость наличия промежуточного буфера сборки текстового блока обусловлена тем, что часто работа с дисплеями осуществляется по каналу связи с ограниченной по сравнению с RAM пропускной способностью, по протоколу типа:

• сначала послать команду Записать_байт (координаты байта на дисплее)
• после чего, возможно, получить подтверждение,
• и только после этого можно передавать байт.

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

Каждый текстовый блок характеризуется координатами текстового блока x,y(относительно окна вывода), смещением x_shift, y_shift относительно координат x,y текстового блока, шрифтом и атрибутами, такими как инверсный или нет, мигающий, жирный, курсив, подчёркивание и так далее.

Автомат разбивки текста на блоки

Операционная часть автомата разбивки на блоки состоит из входного потока байтов, который разбивается на блоки. Чтобы избежать ненужного копирования, текстовые блоки это части исходной строки, которые передаются в Автомат вывода текстового блока в виде двух указателей Text_begin и Text_end.

Рисунок 6. Пояснение к ОА автомата разбивки на блоки

Автомат разбивки управляет настройками Автомата вывода текстового блока через непосредственный доступ к соответствующим переменным автомата.

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

После того как разработан ОА несложно составить требуемый ему управляющий автомат

Рисунок 7. Диаграмма состояний автомата разбивки на текстовые блоки

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

Автомат вывода текстового блока

Как было показано выше, управляющие последовательности могут в том числе задавать координаты вывода очередного текстового блока. Координаты текущего текстового блока задаются переменными x, y.

Рисунок 8. Используемые при выводе текстового блока координаты

Пояснение к рисунку.

x_max, y_max – размеры дисплея
x0, y0, x1, y1 – координаты окна вывода, параметры функции Out_text
x_shift, y_shift – смещение, может быть положительным и отрицательным, влияет на расположение всех текстовых блоков.
x,y — координаты вывода текущего текстового блока, могут изменяться esc командами. Координаты отсчитываются относительно окна вывода.

Как было отмечено ранее, текст первоначально выводится в строчный буфер, после чего содержимое строчного буфера копируется в видеопамять.

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

Рисунок 9. Вертикальная развёртка при выводе текстового блока

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

$$display$${Height_{символа }* Width_{экрана}/8} = 768 байт$$display$$

Из этих соотношений можно прикинуть, в каком случае экономия окажется значима. В этой статье мы рассмотрим вариант с полным строчным буфером, как более простой, оставив рассмотрение «практичного» варианта за рамками этой статьи.

Поскольку разработка пары ОА-УА всегда начинается с разработки ОА, а разработка ОА начинается с самого нижнего уровня, составим ОА для автомата вывода текста.

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

Рисунок 10. Пояснение работы операционного автомата прорисовки текстового блока.

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

Рисунок 11. Пояснение связи данных в строчном буфере и видеопамяти

Из иллюстрации видно, что границы области вывода на дисплее могут не совпадать с границей байтов, но обмен между строчным буфером и видеопамятью побайтовый, а это означает:

а) существуют пересекающиеся байты — байты которые содержат как старые данные из видеопамяти, так и новые данные из строчного буфера, поэтому пересекающиеся байты видеопамяти и строки из буфера маскируются взаимодополняющими масками, после чего данные пересекающихся байтов накладываются по или. Данные не пересекающихся байтов копируются в видеопамять целиком.
б) вывод текста в строчный буфер всегда начинается с нулевого байта строчного буфера, но не всегда с нулевой позиции, чаще он начинается с некоторого отступа Current_shift_{начальное}.
в) текст, помимо начального сдвига, связанного со значением координаты x может быть смещён за левую границу и часть текста выходящая за неё не отображается.
г) текст может выступать справа, что требует дополнительного маскирования, причём при соответствующих размерах один и тот же символ может выступать и справа и слева.

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

Все символы строки разделены на категории:

Рисунок 12. Категории символов, выводимых на экран, в зависимости от расположения относительно окна вывода.

Каждая категория подразумевает свой режим обработки:

• Символы не попавшие в окно вывода (1) просто игнорируются.
• Первый символ частично или целиком попавший в окно вывода (2) может требовать дополнительного по сравнению с типом 3 сдвига влево, чтобы отсечь выступающие за область вывода пикселы. Выпавшие байты и биты просто теряются.

Рисунок 13. Пояснение механизма начального сдвига. Цифры показывают порядковый номер пикселов в изображении символа.

• Символы полностью попавшие в область вывода (3) как и символы тип (2) требуют сдвига вправо, величина которого зависит от координаты символа.

Рисунок 14. Пояснение механизма скользящего сдвига

Для первого символа выполняется и сдвиг влево и сдвиг вправо, поэтому появляется возможность сэкономить – осуществлять фактический сдвиг на разность соответствующих величин с дополнительным маскированием «выпавших» пикселов. Маска получается табличным способом, поэтому практически не требует дополнительных вычислений, но такой подход позволяет экономить до 7 сдвигов на каждый байт первого символа, что при размере символа 16*24 даёт экономию до 336 сдвигов.

Рисунок 15. Исключение двойного сдвига

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

Рисунок 16. Заполнение строчного буфера.

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

Рисунок 17. Обработка символов 2’ и 3’.

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

Как было показано выше, шлифовка программной реализации происходит на последнем этапе, тем не менее, для ясности я буду приводить исходники в их окончательном виде, несмотря на то, что идея исключения двойного сдвига возникла уже в процессе оптимизации, после того, как весь модуль был отлажен, причём для этого пришлось лишь слегка изменить функцию Out_symbol. То же касается использования переменных Start_line и End_line, которые появятся лишь при разработке вышележащей функции Out_text, но при этом их добавление лишь немного повлияло на вид функции Out_symbol.

Полная версия исходника находится по ссылке, в файле Display.h/Display.cpp. Там же находится откомпилированный пример(Project1.exe). Сам проект под Builder 6

  class tShift_register Symbol_buffer;
  vector< tShift_register > Line_buffer;

  // Значения всех этих переменных задаются на вышележащем уровне
  int Start_line, End_line;
  int Left_shift, Current_shift, Current_byte;
  // Указатель на массив шириной Width байтов - битовое поле выводимого символа
  u1x * Symbol_array;
  int Width;
  int bytes_Width;
  //Может на байт превосходить bytes_Width, в зависимости от величины сдвига
  int bytes_Width_after_shift;

  inline void Out_symbol ()
  {

    for(int Current_line = Start_line; Current_line <= End_line; Current_line++)
    {

      Symbol_buffer.Clear();

      ////////////////////////
      // Для типов 2 и 3 используется один метод Out_symbol, это фактически выбор типа символа
      if(Left_shift)// тип 2
      {
        
        // Если сдвиг больше чем 8 бит имеет смысл заменить его сдвигом на целый байт
        int Start_symbol_byte = Left_shift >> 3;

        // void tShift_register::Load(int Start_index_in_destination, u1x * Source, int Width);
        Symbol_buffer.Load(0,Symbol_array + bytes_Width * Current_line + Start_symbol_byte,
                                                                  bytes_Width - Start_symbol_byte);

        // рис.15
        // void tShift_register::Shift(int Start, int End, int Amount);
        Symbol_buffer.Shift (0, bytes_Width_after_shift,   Current_shift - (Left_shift & 7)  );
        Symbol_buffer[0] &= Masks_array__left_for_line_buffer[ Current_shift ];

        // рис.16
        Line_buffer[Current_line].Or(Current_byte, &Symbol_buffer[0], bytes_Width_after_shift );

      }
      else // тип 3
      {
       
        Symbol_buffer.Load(0,Symbol_array + bytes_Width * Current_line, bytes_Width);

        // рис.14
        Symbol_buffer.Shift(0, bytes_Width_after_shift, Current_shift);

        // рис.16
        Line_buffer[Current_line].Or(Current_byte, &Symbol_buffer[0], bytes_Width_after_shift );

      }

    }// for(int Current_line = Start_line, Current_line <= End_line, Current_line++)

  }// inline void Out_symbol ()

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

Рисунок 18. Диаграмма состояний – хорошая альтернатива классическим блок схемам.

По алгоритму записанному этой диаграммой состояний несложно составить программный код, состоящий из классических структурных конструкций — циклов и ветвлений. Это оказывается несложно в частности потому что этот направленный граф, в общем, не циклический ( то есть не содержит переходы в предыдущие состояния). Исключение составляет пара петель (состояния Тип 1 и Тип 3), которые легко разворачиваются в циклы. Однако даже для тех автоматов, которые описываются более сложным графом с циклическими путями обхода узлов, тоже можно написать структурную программу, хотя на первый взгляд эта задача может показаться трудноразрешимой и громоздкой. Прошу акцентировать внимание: поскольку диаграмма состояний имеет дело с абсолютно идентичными с точки зрения программного процесса блоками-состояниями, связи между которыми ясно и однозначно определены, это позволяет использовать для перехода между состояниями оператор goto, не нарушая структурности языка. То есть, если оператор goto будет использован для совершения переходов между состояниями автомата, это само по себе новая структура, такая же как циклы и ветвления. Эта структура называется переход между состояниями, и она обогащает инструментарий программирования. В то же время, следует понимать, что использование оператора goto вне рамок этой программной структуры по-прежнему остаётся неструктурным, т.е. ломающим стандартные структуры из которых строится программный код. Это важный момент. Возможно, потребуется время, чтобы люди привыкли и перестали бояться, но хочется верить, что новая структурная конструкция займёт достойное место в инструментарии программистов.

Управляющий автомат вывода текстового блока реализуется следующим кодом:

  class tShift_register Symbol_buffer;
  vector< tShift_register > Line_buffer;
  tVideomemory Videomemory;
  
  // Значения этих переменных задаются на вышележащем уровне
  int Start_line, End_line;
  // НАЧАЛЬНЫЕ значения этих переменных задаются на вышележащем уровне
  int Left_shift, Current_shift, Current_byte;

  // Значения этих переменных задаются на вышележащем уровне
  u1x * Text;
  u1x * Text_end;
  tFont * Current_font;

  // Эти переменные полностью контролируются функцией Out_text_block 
  // Указатель на массив шириной Width байтов - битовое поле выводимого символа
  u1x * Symbol_array;
  int Width;
  int bytes_Width;
  //Может на байт превосходить bytes_Width, в зависимости от величины сдвига
  int bytes_Width_after_shift;

  // Значения этих переменных задаются на вышележащем уровне
  // Полная длина текста в пикселах
  int Line_width;


  ////////////////////////////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////////////////////////////
  inline void Out_text_block ()
  {

    Clear_line_buffer();

  ////////////////////////////////////////
  // Далее всё как показано в диаграмме состояний
  Type_1:

    // Пока не конец строки
    while(Text < Text_end)
    {

      Width = Current_font->Width_for(*Text);
      
      // Прокручиваем символы пока не попадём в область отображения
      if(Left_shift >= Width)
      {
        Left_shift  -= Width;
        Text++;
      }
      else
      
        goto Type_2;

    }// while(Text < Text_end)

    // Конец строки
    return;

  ////////////////////////////////////////
  Type_2:

    // Инициализируем
    Current_byte  = Current_shift >> 3;
    Current_shift = Current_shift & 7;

    Symbol_array = Current_font->Image_for(*Text);
    bytes_Width  = (Width + 7) >> 3;
    bytes_Width_after_shift  = (Width + Current_shift + 7) >> 3;

    Line_width     -= (Width - Left_shift);

    // Достигли границы?
    if(Line_width <= 0)
    {

      Width -= Left_shift;
    
      goto Type_4;

    }

    Out_symbol();
    
    // Компенсируем Left_shift
    Width -= Left_shift;
    Left_shift   =  0;

    // Любой следующий символ
    Text++;

  ////////////////////////////////////////
  Type_3:

    // Конец строки?
    while(Text < Text_end)
    {

      //Сдвигаем Current_byte, Current_shift на величину уже выведенного символа.
      Current_shift += Width;
      Current_byte  += (Current_shift >> 3);
      Current_shift =  Current_shift & 0x7;

      // Прокручиваем на следующий символ
      Width        = Current_font->Width_for(*Text);
      Symbol_array = Current_font->Image_for(*Text);
      bytes_Width  = (Width + 7) >> 3;
      bytes_Width_after_shift  = (Width + Current_shift + 7) >> 3;

      Line_width     -= Width;

      // Достигли границы?
      if(Line_width <= 0)

        goto Type_4;

      Out_symbol();

      Text++;

    }// while(*Text < Text_end)

    Current_shift += Width;
    Current_byte  += (Current_shift >> 3);
    Current_shift =  Current_shift & 0x7;

    // Конец строки
    goto Finalize;

  ////////////////////////////////////////
  // фактически типа 4 нет это символы тип 2' и 3'   
Type_4:

    Out_symbol();

    Current_shift += (Width + Line_width);
    Current_byte  += (Current_shift >> 3);
    Current_shift =  Current_shift & 0x7;

    for(int Current_line = Start_line; Current_line <= End_line; Current_line++)
    {

      Line_buffer[Current_line][Current_byte] &= Masks_array__right_for_line_buffer[Current_shift];

    }

Finalize:

    Out_line_buffer_in_videomemory();

    return;

  }// inline void Out_text_block ()

Этот алгоритм легко и органично, буквально 1 в 1, реализуется и на ассемблере.

Такие величины как Start_line, End_line, начальные значения Left_shift, Current_shift, Current_byte задаются на этапе инициализации процесса вывода блока. Это происходит ещё в автомате разбиения на блоки. Рассмотрим как это происходит. Напомню, что одна строка может выводиться не единственным блоком а несколькими, поэтому при выводе каждого блока мы имеем дело с параметрами показанными на рис.8.

Координаты каждого текстового блока (x,y) могут задаваться индивидуально (esc последовательности, однако есть и различие – координаты курсора задаются не в знакоместах а в пикселах). Они отсчитываются относительно координат окна вывода (x0,y0,x1,y1). Смещение x_shift, y_shift влияет на координаты каждого текстового блока. Все текстовые блоки целиком попадающие в окно вывода не обрезаются даже если задано отрицательное смещение.Обрезается только то, что не попадает в окно вывода, т.е. отрицательное смещение само по себе не критерий обрезки текстовых блоков. Для реализации описанного поведения вывод каждого текстового блока сопровождается следующими преобразованиями.

Вычисление параметров по горизонтали иллюстрирует рис. 19

Рис 19. Пояснение к вычислению параметров по горизонтали

Значение x_shift не показано, оно компенсируется добавлением к x. Параметры x_byte и Start_shift используются во время вывода в видеопамять, который осуществляется по схеме показанной на рис. 20

Рисунок 20. Вывод в видеопамять.

Процесс вывода очевиден, но не будут излишними пояснения:

• Если левый байт пересекающийся, то читается соответствующий байт видеопамяти, маскируется и накладывается на крайний левый байт строчного буфера (который уже и так замаскирован в процессе вывода в строчный буфер).
• Если правый крайний байт пересекающийся то читается соответствующий байт видеопамяти, маскируется, после чего накладывается на крайний правый байт строчного буфера (который при этом маскируется дополняющей маской).
• После этого весь строчный буфер потоком копируется в видеопамять, причём строка Start_line строчного буфера идёт в строку y буфера, и так далее вплоть до End_line и y + End_line — Start_line, соответственно, как это показано на рис 20.

Параметры Start_line и End_line определяются исходя из соображений показанных на
рис. 21.

Рис. 21. Определение параметров по вертикали.

Приведённым на чертежах рис 20, рис 21 преобразованиям соответствует алгоритм

    // Стартовая инициализация 

    // Проверяем корректность параметров окна
    ////////////////////////////////////////////////////////////////////////////////////
    if(x1 < x0)
    {
       int temp = x0;
       x0 = x1;
       x1 = temp;
    }

    if(y1 < y0)
    {
       int temp = y0;
       y0 = y1;
       y1 = temp;
    }

    if(x0 < 0)
    {
      x_shift += x0;
      x0 = 0;
    }

    if(y0 < 0)
    {
      y_shift += y0;
      y0 = 0;
    }

    if(x1 > x_max)
    {
      x1 = x_max;
    }

    if(y1 > y_max)
    {
      y1 = y_max;
    }
 
// для каждого блока
inline bool Init_text_block()
{
    // Компенсируем сдвиг
    ////////////////////////////////////////////////////////////////////////////////////
    x += ( x0 + x_shift);
    y += ( y0 + y_shift);

    // по горизонтали
    ////////////////////////////////////////////////////////////////////////////////////
    if (x < x0)
    {
      Left_shift = x - x0;
      x = x0;
    }
    else
    {
      Left_shift = 0;
    }

    if(x >= x1)

      return false;

    x_byte =  x >> 3;
    Start_shift = Current_shift = x & 7; 
    Current_byte = 0;

    Line_width = x1-x;

    // по вертикали
    ////////////////////////////////////////////////////////////////////////////////////
    if (y < y0)
    {
      Start_line = y0 - y;
      y = y0;
    }
    else

      Start_line = 0;

    if(Start_line >= Current_font->Height())

      return false;

    if( (Current_font->Height() - Start_line) < ( y1 - y) )

      End_line = Current_font->Height() - 1;

    else

      End_line = Start_line + (y1 - y) - 1;

    return true;

}

Следует добавить, что фактически выводится только содержимое текстового блока, а не всего окна вывода, ограниченного координатами x0,y0,x1,y1. При необходимости можно предварительно очищать всё окно отдельно.

Автомат разбивки исходного текста на блоки.

Диаграмма состояний и переходов уже была приведена на рис.7 и по ней несложно составить следующий алгоритм.

  ///////////////////////////////////////////////////////////////////////////////////
  ///////////////////////////////////////////////////////////////////////////////////
  ///////////////////////////////////////////////////////////////////////////////////
  ///////////////////////////////////////////////////////////////////////////////////
  ///////////////////////////////////////////////////////////////////////////////////
  ///////////////////////////////////////////////////////////////////////////////////
  // Описана выше
  void Out_text_block ();

  inline void Control_processing ();
  

  void Out_text (int arg_x0, int arg_y0,
                 int arg_x1, int arg_y1,
                 int arg_x_shift, int arg_y_shift,
                 unsigned char * argText)
  {


    // Инициализация
    // ...

    while(*Text_end)
    {


//////////////////////////////////////
state__Inside_text_block:

      while(1)
      {

        switch(*Text_end)
        {

		  // Пока только два кода в следующей части рассмотрим этот вопрос подробнее
          case '':
          case 'n':

            goto state__Out_text_block;

        } 

        Text_end++;

      }


//////////////////////////////////////
state__Out_text_block:

      if( (Text_begin != Text_end) && Init_text_block())

        Out_text_block();

      Text_begin = Text_end;

//////////////////////////////////////
state__Control_processing:

      if(*Text_end == 0)

        return;

      // Стоит выделить в отдельную функцию
      Control_processing();

    }//while(*Text_end)

  }//void Out_text (int arg_x0, int arg_y0,

Так в общих чертах выглядит решение задачи. По ссылке вы можете увидеть исходники и рабочую версию программы(файл Project1.exe). Единственный вопрос, который остался не раскрыт – структура функции Control_processing, которая разбирает esc-последовательности и выполняет команды. В её основе лежит ещё один тип автоматов, который заметно отличается от рассмотренных выше, но которые в то же время классика программных автоматов – символьные автоматы. Мы рассмотрим реализацию функции и автомата в следующей части и там же проведём обзор преимуществ автоматного подхода.

Автор: Dr_Dash

Источник