Хабрахабр

[Перевод] Минимальный возможный шрифт

Задача: используя наименьшее возможное количество ресурсов, отрендерить осмысленный текст.

  • Насколько маленьким может быть читаемый шрифт?
  • Сколько памяти понадобится, чтобы его хранить?
  • Сколько кода понадобится, чтобы его использовать?

Спойлер: Посмотрим, что у нас получится.

Введение в битмэпы

Речь не о формате .bmp, а о способе хранения пикселей в памяти. Компьютеры представляют растровые изображения в виде битмэпов. Для понимания происходящего нам надо кое-что про этот способ узнать.

Слои

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

  • RGB — не единственное цветовое пространство; формат JPEG, например, использует YUV. Но в этой статье остальные цветовые пространства нам не понадобятся, поэтому мы их не рассматриваем.

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

Он может быть представлен вот так: Допустим, у нас есть рисунок 4x4, содержащий три слоя: R для красного, G для зелёного и B для синего компонента каждого из пикселей.

R R R R R R R R R R R R R R R R G G G G G G G G G G G G G G G G B B B B B B B B B B B B B B B B

Перемежающийся формат выглядит иначе: Все три слоя хранятся по отдельности.

RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB

  • каждая тройка символов соответствует ровно одному пикселю
  • значения в пределах тройки идут в порядке RGB. Иногда может использоваться и другой порядок (например, BGR), но этот — самый распространённый.

Но на самом деле память компьютера не двумерная, а одномерная, поэтому рисунок 4х4 будет храниться вот так: Для простоты я расположил пиксели в виде двухмерной матрицы, потому что так понятнее, где в изображении находится та или иная тройка.

RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB

bpp

Вам могло где-то попадаться на глаза 24bpp или 3bpp. Аббревиатурой bpp обозначается количество битов или байт на пиксель (bits/bytes per pixel). Так как в байте всегда 8 бит, по величине значения можно догадаться, о какой из единиц идёт речь. Эти две характеристики означают одно и то же — 24 бита на пиксель или 3 байта на пиксель.

Представление в памяти

Вот так на уровне отдельных битов выглядит один пиксель в порядке RGB. 24bpp, он же 3bpp — самый распостранённый формат для хранения цветов.

бит 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
пиксель R R R R R R R R G G G G G G G G B B B B B B B B

  • Один байт для R, один для G и один для B, итого три байта.
  • Каждый из них содержит значение от 0 до 255.

Так что если данный пиксель имеет следующий цвет:

  • R 255
  • G 80
  • B 100

Тогда в первом байте хранится 255, во втором 80, а в третьем — 100.

Скажем, #ff5064. Чаще всего эти значения представляются в шестнадцатеричном виде. R=255 в десятеричном представлении), G = 0x50 (=G=80), B=0x64 (=B=100). Так гораздо удобнее и компактнее: R = 0xff (т.е.

  • У шестнадцатеричного представления есть одно полезное свойство. Так как каждый байт цвета представлен двумя символами, каждый символ кодирует ровно пол-байта, или четыре бита. 4 бита, кстати, называются ниббл.

Ширина строки

Неизвестно, когда заканчивается одна строка и начинается следующая, поэтому для интерпретации файла с битмэпом нужно знать размер изображения и bpp. Когда пиксели идут один за другим и каждый содержит больше одного канала, в данных легко запутаться. В нашем случае рисунок имеет ширину w = 4 пикселя и каждый из этих пикселей содержит 3 байта, поэтому строка кодируется 12 (в общем случае w*bpp) байтами.

  • Строка не всегда кодируется ровно w*bpp байтами; часто в неё добавляются "скрытые" пиксели, чтобы довести ширину изображения до какой-то величины. Например, масштабировать рисунки быстрее и удобнее, когда их размер в пикселях равен степени двойки. Поэтому файл может содержать (доступное пользователю) изображение 120х120 пикселей, но храниться как изображение 128х128. При выводе изображения на экран эти пиксели игнорируются. Впрочем, нам о них знать не обязательно.

Это, в общем-то, очевидно: y — номер строки, каждая строка содержит w пикселей, так что y * w — это начало нужной строки, а+x переносит нас к нужному x в её пределах. Координата любого пикселя (x, y) в одномерном представлении — (y * w + x) * bpp. Так как пиксель имеет ненулевой размер, нужно прочитать ровно bpp байт, начиная с полученной координаты, и у нас будет полное представление нужного пикселя. А так как координаты не в байтах, а в пикселях, всё это умножается на размер пикселя bpp, в данном случае в байтах.

Атлас шрифта

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

Разумеется, есть подводные камни: Нас интересует LCD, так как, скорее всего, именно с такого монитора вы и читаете этот текст.

  • Не все матрицы используют именно такой порядок субпикселей, бывает и BGR.
  • Если повернуть монитор (например, смотреть на телефоне в альбомной ориентации), то паттерн тоже повернётся и шрифт перестанет работать.
  • Разные ориентации матрицы и расположение субпикселей потребуют переделки самого шрифта.
  • В частности, он не работает на AMOLED-дисплеях, использующих расположение PenTile. Такие дисплеи чаще всего используются в мобильных устройствах.

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

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

Которая, если очень внимательно вглядываться в монитор, выглядит вот так:

А вот она же, программно увеличенная в 12 раз:

Порядок символов следующий: Отталкиваясь от его работы, я создал атлас шрифта, в котором каждому символу соответствует колонка 1x5 пикселей.

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Тот же атлас, увеличенный в 12 раз:

Если считать, что каждый пиксель занимает 3 байта, то нам нужно 36*5*3 = 540 байт на то, чтобы хранить весь рисуонк (прим. С 36 используемыми символами получается ровно 36х5 пикселей. В переводе я её опустил и использую только окончательный вариант файла). пер.: в оригинале запутанная серия правок по поводу альфа-канала, удаления метаданных и т.п. PNG-файл, пропущенный через pngcrush и optipng, занимает даже меньше:

# wc -c < font-crushed.png
390

Но можно добиться ещё меньшего размера, если использовать слегка другой подход

Внимательный читатель мог заметить, что атлас использует всего 7 цветов:

  1. #ffffff
  2. #ff0000
  3. #00ff00
  4. #0000ff
  5. #00ffff
  6. #ff00ff
  7. #ffff00

Палитра

Тогда для каждого пикселя можно хранить не три байта цвета, а только номер цвета в палитре. В таких ситуациях часто проще создать палитру. Если каждому пикселю сопоставить трёхбитное значение, то весь атлас поместится в 68 байт. В нашем случае для выбора из 7 цветов будет достаточно 3 бит (7 < 2^3).

  • Читатель, разбирающийся в сжатии данных, может ответить, что вообще-то есть такая штука как "дробные биты" и в нашем случае достаточно 2.875 бит на пиксель. Такой плотности можно добиться с помощью чёрной магии, известной как арифметическое кодирование. Мы этого делать не будем, потому что арифметическое кодирование — сложная штука, а 68 байт — это и так немного.

Выравнивание

Пиксели не могут быть равномерно распределены по 8-битным байтам, что важно, потому что байт — минимальный адресуемый участок памяти. У трёхбитного кодирования есть один серьёзный недостаток. Допустим, мы хотим сохранить три пикселя:

A B C

Если каждый занимает 3 бита, то на их хранение уйдёт 2 байта (- обозначает неиспользуемые биты):

bit 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
pixel A A A B B B C C C - - - - - - -

Когда мы начнём добавлять следующие пиксели, они могут быть расположены как угодно относительно границ байтов. Что важно, пиксель C не просто оставляет кучу пустого места; он разорван между двумя байтами. Но это увеличит размер атласа на треть, с 68 байт до 90 байт. Простейшим решением будет использовать по нибблу на пиксель, потому что 8 прекрасно делится на 4 и позволяет помещать в каждый байт ровно по два пикселя.

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

Битовый буфер

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

  • Из соображений читаемости код написан на JS, но тот же метод генерализуется на другие языки.
  • Используется порядок от младшего байта к старшему (Little Endian)

class BitBuffer write(value) { for (let i = 0; i < 3; ) { // bits remaining const remaining = 3 - i; // bit offset in the byte i.e remainder of dividing by 8 const bit_offset = this.offset & 7; // byte offset for a given bit offset, i.e divide by 8 const byte_offset = this.offset >> 3; // max number of bits we can write to the current byte const wrote = Math.min(remaining, 8 - bit_offset); // mask with the correct bit-width const mask = ~(0xff << wrote); // shift the bits we want to the start of the byte and mask off the rest const write_bits = value & mask; // destination mask to zero all the bits we're changing first const dest_mask = ~(mask << bit_offset); value >>= wrote; // write it this.data[byte_offset] = (this.data[byte_offset] & dest_mask) | (write_bits << bit_offset); // advance this.offset += wrote; i += wrote; } } to_string() { return Array.from(this.data, (byte) => ('0' + (byte & 0xff).toString(16)).slice(-2)).join(''); }
};

Давайте загрузим и закодируем файл с атласом:

const PNG = require('png-js');
const fs = require('fs'); // this is our palette of colors
const Palette = [ [0xff, 0xff, 0xff], [0xff, 0x00, 0x00], [0x00, 0xff, 0x00], [0x00, 0x00, 0xff], [0x00, 0xff, 0xff], [0xff, 0x00, 0xff], [0xff, 0xff, 0x00]
]; // given a color represented as [R, G, B], find the index in palette where that color is
function find_palette_index(color) { const [sR, sG, sB] = color; for (let i = 0; i < Palette.length; i++) { const [aR, aG, aB] = Palette[i]; if (sR === aR && sG === aG && sB === aB) { return i; } } return -1;
} // build the bit buffer representation
function build(cb) { const data = fs.readFileSync('subpixels.png'); const image = new PNG(data); image.decode(function(pixels) { // we need 3 bits per pixel, so w*h*3 gives us the # of bits for our buffer // however BitBuffer can only allocate bytes, dividing this by 8 (bits for a byte) // gives us the # of bytes, but that division can result in 67.5 ... Math.ceil // just rounds up to 68. this will give the right amount of storage for any // size atlas. let result = new BitBuffer(Math.ceil((image.width * image.height * 3) / 8)); for (let y = 0; y < image.height; y++) { for (let x = 0; x < image.width; x++) { // 1D index as described above const index = (y * image.width + x) * 4; // extract the RGB pixel value, ignore A (alpha) const color = Array.from(pixels.slice(index, index + 3)); // write out 3-bit palette index to the bit buffer result.write(find_palette_index(color)); } } cb(result); });
} build((result) => console.log(result.to_string()));

Как и ожидалось, атлас поместился в 68 байт, что в 6 раз меньше PNG-файла.

пер.: автор несколько лукавит: он не сохранил палитру и размер изображения, что по моим прикидкам потребует 23 байт при фиксированном размере палитры и увеличит размер изображения до 91 байта) (прим.

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

305000000c0328d6d4b24cb46d516d4ddab669926a0ddab651db76150060009c0285
e6a0752db59054655bd7b569d26a4ddba053892a003060400d232850b40a6b61ad00

Можно заменить его на base64, в котором символов вчетверо больше. Но получившаяся строка всё ещё довольно длинная, потому что мы ограничили себя алфавитом из 16 символов.

to_string() { return Buffer.from(this.data).toString('base64');
}

В base64 атлас выглядит вот так:

MFAAAAwDKNbUsky0bVFtTdq2aZJqDdq2Udt2FQBgAJwCheagdS21kFRlW9e1adJqTdugU4kqADBgQA0jKFC0CmthrQA=

Эту строку можно захардкодить в JS-модуль и использовать для растеризации текста.

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

const Alphabet = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
const Atlas = Uint8Array.from(Buffer.from('MFAAAAwDKNbUsky0bVFtTdq2aZJqDdq2Udt2FQBgAJwCheagdS21kFRlW9e1adJqTdugU4kqADBgQA0jKFC0CmthrQA=', 'base64'));
const Palette = [ [0xff, 0xff, 0xff], [0xff, 0x00, 0x00], [0x00, 0xff, 0x00], [0x00, 0x00, 0xff], [0x00, 0xff, 0xff], [0xff, 0x00, 0xff], [0xff, 0xff, 0x00]
]; // at the given bit offset |offset| read a 3-bit value from the Atlas
read = (offset) => { let value = 0; for (let i = 0; i < 3; ) { const bit_offset = offset & 7; const read = Math.min(3 - i, 8 - bit_offset); const read_bits = (Atlas[offset >> 3] >> bit_offset) & (~(0xff << read)); value |= read_bits << i; offset += read; i += read; } return value;
}; // for a given glyph |g| unpack the palette indices for the 5 vertical pixels
unpack = (g) => { return (new Uint8Array(5)).map((_, i) => read(Alphabet.length*3*i + Alphabet.indexOf(g)*3));
}; // for given glyph |g| decode the 1x5 vertical RGB strip
decode = (g) => { const rgb = new Uint8Array(5*3); unpack(g).forEach((value, index) => rgb.set(Palette[value], index*3)); return rgb;
}

Впечатляет тут то, что на декодирование одного символа уходит всего 5 байт памяти, плюс ~1. Функция decode принимает на вход символ и возвращает соответствующий столбец исходного изображения. в среднем 6. 875 байт на то, чтобы прочитать нужный кусок массива, т.е. Если прибавить 68 байт на хранение массива и 36 байт на хранение алфавита, то получится, что теоретически можно рендерить текст со 128 байтами RAM. 875 на букву.

  • Такое возможно, если переписать код на C или ассемблере. На фоне оверхеда JS это экономия на спичках.

Осталось только собрать эти столбцы в единое целое и вернуть картинку с текстом.

print = (t) => { const c = t.toUpperCase().replace(/[^\w\d ]/g, ''); const w = c.length * 2 - 1, h = 5, bpp = 3; // * 2 for whitespace const b = new Uint8Array(w * h * bpp); [...c].forEach((g, i) => { if (g !== ' ') for (let y = 0; y < h; y++) { // copy each 1x1 pixel row to the the bitmap b.set(decode(g).slice(y * bpp, y * bpp + bpp), (y * w + i * 2) * bpp); } }); return {w: w, h: h, data: b};
};

Это и будет минимальный возможный шрифт.

const fs = require('fs');
const result = print("Breaking the physical limits of fonts");
fs.writeFileSync(`${result.w}x${result.h}.bin`, result.data);

Добавим немножко imagemagick, чтоб получить изображение в читаемом формате:

# convert -size 73x5 -depth 8 rgb:73x5.bin done.png

И вот финальный результат:

Оно же, увеличенное в 12 раз:

Оно же, снятое макросъёмкой с плохо откалиброванного монитора:

И наконец, оно же на мониторе получше:

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть