Tarefa: usando a menor quantidade possível de recursos, renderize um texto significativo.

Quão pequena pode ser uma fonte legível?
Quanta memória será necessária para armazená-lo?
Quanto código será necessário para usá-lo?

Vamos ver o que temos. Spoiler

Introdução aos bitmaps

Os computadores apresentam bitmaps como bitmaps. Não se trata do formato .bmp , mas de uma maneira de armazenar pixels na memória. Para entender o que está acontecendo, precisamos aprender algo sobre esse caminho.

Camadas

Uma imagem geralmente contém várias camadas umas sobre as outras. Na maioria das vezes, correspondem às coordenadas do espaço de cores RGB . Uma camada para vermelho , uma para verde e uma para azul . Se o formato da imagem suportar transparência, será criada uma quarta camada, geralmente chamada alfa . Grosso modo, uma imagem colorida é três (ou quatro, se houver um canal alfa) em preto e branco, localizada uma acima da outra.

RGB não é o único espaço de cor; O formato JPEG, por exemplo, usa YUV . Mas neste artigo não precisaremos do restante dos espaços de cores, portanto, não os consideramos.

Um conjunto de camadas pode ser representado na memória de duas maneiras. Eles são armazenados separadamente ou valores de diferentes camadas são intercalados. No último caso, as camadas são chamadas de canais , e é assim que a maioria dos formatos modernos funciona.

Suponha que tenhamos um desenho 4x4 contendo três camadas: R para vermelho, G para verde e B para o componente azul de cada um dos pixels. Pode ser representado assim:

  RRRR RRRR RRRR RRRR GGGG GGGG GGGG GGGG BBBB BBBB BBBB BBBB

Todas as três camadas são armazenadas separadamente. O formato alternado parece diferente:

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

cada triplo de caracteres corresponde exatamente a um pixel
os valores dentro do triplo estão na ordem RGB . Às vezes, uma ordem diferente pode ser usada (por exemplo, BGR ), mas essa é a mais comum.

Para simplificar, organizei os pixels na forma de uma matriz bidimensional, porque é mais claro onde esse ou aquele triplo está na imagem. Mas, na verdade, a memória do computador não é bidimensional, mas unidimensional; portanto, a imagem 4x4 será armazenada assim:

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

bpp

A abreviação bpp refere-se ao número de bits ou bytes por pixel (bits / bytes por pixel). Você pode ter visto 24bpp ou 3bpp . Essas duas características significam a mesma coisa - 24 bits por pixel ou 3 bytes por pixel . Como sempre existem 8 bits em um byte, você pode adivinhar pelo valor de qual das unidades em questão.

Representação de memória

24bpp , também conhecido como 3bpp - o formato mais comum para armazenar flores. É assim que um único pixel na ordem RGB fica no nível de bits individuais.

  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23  RRRRRRRRGGGGGGGGBBBBB BBB

Um byte para R , um para G e um para B , totalizando três bytes.
Cada um deles contém um valor de 0 a 255.

Portanto, se o pixel fornecido tiver a seguinte cor:

R 255
G 80
B 100

Em seguida, 255 armazenados no primeiro byte, 80 no segundo e 100 no terceiro.

Na maioria das vezes, esses valores são representados em hexadecimal . Diga #ff5064 . Isso é muito mais conveniente e compacto: R = 0xff (ou seja, R=255 em decimal), G = 0x50 (= G=80 ), B=0x64 (= B=100 ).

A representação hexadecimal possui uma propriedade útil. Como cada byte de cor é representado por dois caracteres, cada caractere codifica exatamente meio byte ou quatro bits. A propósito, 4 bits são chamados de mordidelas .

Largura da linha

Quando os pixels vão um após o outro e cada um contém mais de um canal, os dados são facilmente confundidos. Não se sabe quando uma linha termina e a seguinte começa, portanto, para interpretar um arquivo com um bitmap, você precisa saber o tamanho da imagem e o bpp . No nosso caso, a imagem tem uma largura de w = 4 pixels e cada um desses pixels contém 3 bytes; portanto, a string é codificada com 12 (no caso geral, w*bpp ) bytes.

Uma string nem sempre é codificada com exatamente w*bpp bytes; Freqüentemente, pixels "ocultos" são adicionados a ele para aumentar a largura da imagem. Por exemplo, dimensionar imagens é mais rápido e mais conveniente quando o tamanho em pixels é igual a duas vezes. Portanto, o arquivo pode conter (acessível ao usuário) uma imagem de 120x120 pixels, mas ser armazenado como uma imagem de 128x128. Quando uma imagem é exibida na tela, esses pixels são ignorados. No entanto, não precisamos saber sobre eles.

A coordenada de qualquer pixel (x, y) na representação unidimensional é (y * w + x) * bpp . Isso, em geral, é óbvio: y é o número da linha, cada linha contém w pixels, então y * w é o início da linha desejada e +x nos leva ao x desejado dentro dela. E como as coordenadas não estão em bytes, mas em pixels, tudo isso é multiplicado pelo tamanho do pixel bpp , neste caso em bytes. Como o pixel tem um tamanho diferente de zero, você precisa ler exatamente os bytes de bpp , começando pela coordenada recebida, e teremos uma representação completa do pixel desejado.

Atlas de fontes

Na verdade, os monitores existentes não exibem um pixel como um todo, mas três subpixels - vermelho, azul e verde. Se você olhar para o monitor sob ampliação, verá algo parecido com isto:

Desenho da Wikipedia

Estamos interessados no LCD, pois provavelmente é nesse monitor que você lê este texto. Claro, existem armadilhas:

Nem todas as matrizes usam exatamente essa ordem de subpixels, às vezes BGR.
Se você ligar o monitor (por exemplo, procure o telefone na orientação paisagem), o padrão também será rotacionado e a fonte deixará de funcionar.
Diferentes orientações da matriz e a organização dos subpixels exigirão o retrabalho da própria fonte.
Em particular, ele não funciona em monitores AMOLED que usam o layout PenTile . Esses monitores são mais frequentemente usados em dispositivos móveis.

O uso de hacks de subpixel para aumentar a resolução é chamado de renderização de subpixel . Você pode ler sobre seu uso em tipografia, por exemplo, aqui .

Felizmente para nós, Matt Sarnov já descobriu usando renderização de subpixel para criar uma fonte minúscula de militext . Manualmente, ele criou esta pequena imagem:

Que, se você olhar com muito cuidado para o monitor, fica assim:

E aqui está, programaticamente aumentado em 12 vezes:

Com base em seu trabalho, criei um atlas de fontes no qual cada caractere corresponde a uma coluna de 1x5 pixels. A ordem dos caracteres é a seguinte:

 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

O mesmo atlas aumentou 12 vezes:

Com 36 caracteres usados, são 365 exatamente 365 pixels. Se assumirmos que cada pixel ocupa 3 bytes, precisamos de 36*5*3 = 540 bytes para armazenar a imagem inteira ( aprox. Por: no original, uma série confusa de edições sobre o canal alfa, exclusão de metadados etc.). n. Na tradução, eu o omiti e uso apenas a versão final do arquivo ). Um arquivo PNG passado através de pngcrush e optipng leva ainda menos:

 # wc -c < font-crushed.png 390

Mas você pode obter um tamanho ainda menor se usar uma abordagem ligeiramente diferente

Compressão

O leitor atento pode perceber que o atlas usa apenas 7 cores:

#ffffff
#ff0000
#00ff00
#0000ff
#00ffff
#ff00ff
#ffff00

Paleta

Em tais situações, geralmente é mais fácil criar uma paleta. Então, para cada pixel, você pode armazenar não três bytes de cor, mas apenas o número da cor na paleta. No nosso caso, 3 bits ( 7 < 2^3 ) serão suficientes para escolher entre 7 cores. Se atribuirmos um valor de três bits a cada pixel, o atlas inteiro caberá em 68 bytes .

O leitor, versado em compactação de dados, pode responder que, em geral, existem “bits fracionários” e, no nosso caso, 2.875 bits por pixel são suficientes. Essa densidade pode ser alcançada usando magia negra, conhecida como codificação aritmética . Não faremos isso, porque a codificação aritmética é uma coisa complicada e 68 bytes já é um pouco.

Alinhamento

A codificação de três bits tem uma séria desvantagem. Os pixels não podem ser distribuídos uniformemente pelos bytes de 8 bits, o que é importante porque os bytes são a menor área de memória endereçável. Digamos que queremos salvar três pixels:

ABC

Se cada um receber 3 bits, serão necessários 2 bytes para armazená-los ( - indica bits não utilizados):

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

É importante ressaltar que o pixel C não deixa apenas um monte de espaço vazio; está dividido entre dois bytes. Quando começamos a adicionar os seguintes pixels, eles podem ser posicionados arbitrariamente em relação aos limites de bytes. A solução mais simples seria usar mordiscar por pixel, porque 8 é perfeitamente dividido por 4 e permite que você coloque exatamente dois pixels em cada byte. Mas isso aumentará o tamanho do atlas em um terço, de 68 bytes para 90 bytes .

De fato, o arquivo pode ser ainda menor usando a codificação palíndromo, codificação por intervalo e outras técnicas de compactação. Como a codificação aritmética, adiamos essas técnicas para o próximo artigo.

Buffer de bits

Felizmente, não há nada fundamentalmente impossível no trabalho com valores de 3 bits. Você só precisa monitorar qual posição dentro do byte estamos escrevendo ou lendo no momento. A classe simples a seguir converte um fluxo de dados de 3 bits em uma matriz de bytes.

Por motivos de legibilidade, o código é escrito em JS, mas o mesmo método é generalizado para outros idiomas.
Pedido usado de byte baixo a alto ( 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 ie remainder of dividing by 8 const bit_offset = this.offset & 7; // byte offset for a given bit offset, ie 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(''); } };

Vamos baixar e codificar o arquivo atlas:

 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()));

Como esperado, o atlas se encaixa em 68 bytes , 6 vezes menor que o arquivo PNG.

( faixa aproximada: o autor é um tanto falso: ele não salvou o tamanho da paleta e da imagem, o que, de acordo com minhas estimativas, exigirá 23 bytes com um tamanho fixo de paleta e aumentará o tamanho da imagem para 91 bytes )

Agora vamos converter a imagem em uma string para que você possa colá-la no código fonte. Em essência, o método to_string seguinte: representa o conteúdo de cada byte como um número hexadecimal.

 305000000c0328d6d4b24cb46d516d4ddab669926a0ddab651db76150060009c0285 e6a0752db59054655bd7b569d26a4ddba053892a003060400d232850b40a6b61ad00

Mas a sequência resultante ainda é bastante longa, porque nos limitamos a um alfabeto de 16 caracteres. Você pode substituí-lo por base64 , no qual há quatro vezes mais caracteres.

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

Em base64, o atlas é assim:

 MFAAAAwDKNbUsky0bVFtTdq2aZJqDdq2Udt2FQBgAJwCheagdS21kFRlW9e1adJqTdugU4kqADBgQA0jKFC0CmthrQA=

Essa linha pode ser codificada no módulo JS e usada para rasterizar o texto.

Rasterização

Para economizar memória, apenas uma letra será decodificada por vez.

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

A função de decode pega um caractere como entrada e retorna a coluna correspondente na imagem de origem. O que é impressionante aqui é que são necessários apenas 5 bytes de memória para decodificar um único caractere, além de ~ 1,875 bytes para ler a parte desejada da matriz, ou seja, uma média de 6,875 por letra. Se você adicionar 68 bytes para armazenar a matriz e 36 bytes para armazenar o alfabeto, acontece que teoricamente você pode renderizar texto com 128 bytes de RAM.

Isso é possível se você reescrever o código em C ou assembler. No contexto da sobrecarga de JS, isso economiza em correspondências.

Resta apenas coletar essas colunas em um único todo e retornar uma imagem com texto.

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

Essa será a menor fonte possível.

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

Adicione uma pequena imagem para obter a imagem em um formato legível:

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

E aqui está o resultado final:

Também é aumentado em 12 vezes:

É filmado a partir de uma macro de monitor mal calibrada:

E, finalmente, é melhor no monitor:

Menor fonte possível