Растровые шрифты и оптимизация занимаемого места

Продолжим разговор о выводе информации на графические дисплеи средствами недорогих микроконтроллеров.

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

Теперь настала пора поговорить про шрифты немножко подробнее.

Любой символ растрового моноширинного шрифта - это фиксированный прямоугольник, ширина и высота которого определяют размеры символов этого шрифта. Моноширинный шрифт - это такой, у которого для всех символов отведено одно и то же пространство по ширине, будь это узкий символ "!" или широкая буква "Ш".

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

Таких символов в таблице ASCII - 256. Первые 32 символа - служебные и непечатаемые символы, потом 96 символов - латиница, цифры, знаки препинания и различные спец.символы.

Вторые 128 символов отведены под региональные символы. В частности, кириллица занимает 72 символа.

Рассмотрим несколько методов сохранения шрифтов.

Метод 1. "Горизонтальный байт".

Наш символ - буква "Н", в данном случае 5 х 7 пикселей. 
7 строчек кодируются в 7 байт. При этом, из-за того, что ширина символа всего 5 пикселей, 3 бита из каждого байта теряются впустую.

Метод 2. "Вертикальный байт".

Все то же самое, только 5 столбцов кодируются в 5 байт. И впустую теряется только один бит каждого байта.

Вроде бы потеря невелика.... Для одного символа. А для 168? Для 256?

Ну а если взять символ побольше? И с "неудобным" размером? Например, 9 х 13 пикселей? 

Тут потери еще больше получаются. Для горизонтального кодирования потеря 7 бит на каждую из 13 строк. Всего 91 бит. 11 с половиной байт впустую. 
Для вертикального кодирования - меньше, "всего" три бита на каждый из 9 столбцов. 27 бит - 3 с половиной байта.

И остается что? Правильно, забыть про деление на байты.

Метод 3. "Битовый поток".

Просто начинаем перебирать пиксели построчно, слева направо, сверху вниз...

 Будем сохранять эти пиксели, как будто они расположены в один ряд. и потом уже поделим их по 8 шт и упакуем в байты. Если не хватит нам пикселей на последний байт - ну тут уж не беда, дополним ноликами. Потеря 7 бит максимум - все равно ж для хранения придется округлять до целого числа байт.

У нас для символа 9 х 13 пикселей получилось 117 бит, это 14 байт и 5 бит. 3 бита гуляет. Округляем до 15 байт.

Первая половина печатных символов ASCII - спец.символы, цифры, большие и маленькие английские буквы - это 96 символов .
Добавим еще 72 символа кириллицы - получим 168 символов.

Для экономии места в памяти нашего микроконтроллера можно попробовать сжать данные для каждого символа. Тем же методом RLE. 

Например, сделать фиксированный кадр - несколько бит. Первый бит определяет значение пикселя - 0 или 1, а остальные биты - количество этих пикселей.

Попробуем на нашей многострадальной букве "Н". Отведем на кадр три бита. Один бит - пиксель, два бита - количество, от 1 до 4.

Перед разделителем "|" обозначим цвет пикселя, после него - количество бит.

Получаем:
1|2, 0|4, 0|1, 1|4, 0|4, 0|1, 1|4, 0|4, 0|1, 1|4,
0|4, 0|1, 1|4, 0|4, 0|1, 1|4, 1|4, 1|4, 1|4, 1|4,
1|2, 0|4, 0|1, 1|4, 0|4, 0|1, 1|4, 0|4, 0|1, 1|4,
0|4, 0|1, 1|4, 0|4, 0|1, 1|2, 0|4, 0|4, 0|1

Итого 39 кадров по три бита. Или 117 бит. Или.... ТЕ ЖЕ 15 БАЙТ!!!

А если кадр сделать 4 бита? Тогда  в него можно упаковать до 8 точек одного цвета. 
Для вышеприведенной литеры "Н" это 25 кадров. По 4 бита. или 13 байт.

Но тут возникает проблема. Разные символы могут быть ужаты по разному. На символ точки уйдет одно количество кадров, на литеру "@" - совершенно другое. И возникает вопрос поиска нужного нам символа в блоке данных шрифта. Ведь каждый символ занимает разное количество байт. И придется жертвовать еще одним байтом, в котором мы будем хранить количество кадров на символ. И при выводе символа каждый раз перебирать весь блок данных. И чем ближе к концу кодовой таблицы будет наш символ, тем больше времени придется потратить. 

Поэтому я даже и не пробовал реализовывать такое сжатие для шрифтов.

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

Hello, world!
Hello, world!

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

Но все же, как не стараться, но простыми способами ужать 168 символов шрифта менше определенного размера не получится. Если символ состоит из 35 пикселей - то 35 бит для каждого символа вынь и положь.

И если вдруг нам нужно вывести на весь дисплей огромное слово "ОШИБКА!" большими красными буквами, то тут или нужно эту надпись сохранить в виде картинки, или сохранить в памяти МК весь шрифт. А это большой шрифт. 168 символов. А места мало. А из всех 168 символов нам надо всего 7. А 161 - не нужен.

Для таких случаев действительно, можно пожертвовать одним дополнительным байтом на символ и скоростью поиска символа. И перед набором данных каждого символа ставить код этого символа.
Тогда можно сохранить только нужные нам символы. А ненужные - не сохранять.

Как то вот так.

Сначала коды символов, по возрастанию, потом данные символа.
В конце нулевой байт для корректного завершения поиска.
Да, в этом случае есть накладные расходы в виде лишнего байта на символ и в виде процедуры поиска символа. Но для нашего шрифта 9х13 пикселей и 15 байт на символ сохранить 7 символов по 15 байт + по байту на символ и завершающий байт - это 15х7 + 7 + 1 = 113 байт. Или весь шрифт 168 символов х 15 байт = 2520 байт. Разница есть.

Формат описания и хранения шрифта.

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

Поэтому у каждого шрифта должен быть заголовок.

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

Еще у меня сохранено количество байт на столбец/строку, эта информация применяется для методов кодирования "горизонтальный байт" и "вертикальный байт". Это сделано было для выбора размера переменной под буфер - 8, 16 или 32 бита. Потому что любимая серия микроконтроллеров AVR - восьмибитная... (Теоретически, от этого байта можно отказаться, вычисляя это количество из размера символа. Но так уже сложилось, что в моих шрифтах этот байт присутствует.)

Ну и далее уже можно сохранять байты описания символов.

Все описание шрифта можно вынести в отдельный заголовочный файл в многострочное определение (дефайн).

Вот как то вот так:

Это определение по сути - просто длинная-предлинная строка с числами через запятую, обрамленная фигурными скобками {}.

Первый байт - ширина символа - 3 пикселя.
Второй байт - высота символа - 5 пикселей.
Третий - идентификатор набора символов, в данном случае это спец.символы и цифры, всего 32 символа.
Четвертый  - метод кодирования, в данном случае вертикальный байт, младший бит сверху.
Пятый - число байт на столбец.
Далее идут сами данные , по три байта на символ.

В основной программе достаточно подгрузить заголовочный файл со шрифтом, а потом написать

const __flash__ uint8_t miniFont[] = FONT_3X5_ULTRASMALL_DIGITS;

и у нас в памяти контроллера будет организован массив miniFont, в котором будут храниться данные для нашего шрифта.

Модификатор __flash__ - это такой костыль для компилятора GCC для семейства AVR, который указывает, что данный массив нужно хранить не в ОЗУ, а во флеш-памяти.
У старых добрых AVR-ок гарвардская архитектура и программная память - flash - не доступна в адресном пространстве ОЗУ, но к ней можно обращаться посредством специальных средств.
Для других архитектур (например, ARM), где программная память и ОЗУ находятся в одном адресном пространстве - он не нужен.