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

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

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

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

Компьютеры представляют растровые изображения в виде битмэпов. Речь не о формате .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

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

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

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

бит     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 = 0xff (т.е. R=255 в десятеричном представлении), G = 0x50 (=G=80), B=0x64 (=B=100).

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

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

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

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

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

Атлас шрифта

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

• Рисунок с википедии

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

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

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

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

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

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

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

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

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

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

# wc -c < font-crushed.png
390

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

Сжатие

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

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

Палитра

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

• Читатель, разбирающийся в сжатии данных, может ответить, что вообще-то есть такая штука как "дробные биты" и в нашем случае достаточно 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 не просто оставляет кучу пустого места; он разорван между двумя байтами. Когда мы начнём добавлять следующие пиксели, они могут быть расположены как угодно относительно границ байтов. Простейшим решением будет использовать по нибблу на пиксель, потому что 8 прекрасно делится на 4 и позволяет помещать в каждый байт ровно по два пикселя. Но это увеличит размер атласа на треть, с 68 байт до 90 байт.

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

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

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

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

class BitBuffer {
  constructor(bytes) {
    this.data = new Uint8Array(bytes);
    this.offset = 0;
  }
  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

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

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;
}

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

• Такое возможно, если переписать код на 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 раз:

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

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