Geekly articles weekly

Fuente más pequeña posible

Tarea: utilizando la menor cantidad posible de recursos, renderice texto significativo.


  • ¿Qué tan pequeña puede ser una fuente legible?
  • ¿Cuánta memoria se necesitará para almacenarlo?
  • ¿Cuánto código se necesitará para usarlo?

Veamos que tenemos. Spoiler



Introducción a los mapas de bits


Las computadoras presentan mapas de bits como mapas de bits. No se trata del formato .bmp , sino de una forma de almacenar píxeles en la memoria. Para entender lo que está sucediendo, necesitamos aprender algo sobre esto.


Capas


Una imagen generalmente contiene varias capas una encima de la otra. Muy a menudo corresponden a las coordenadas del espacio de color RGB . Una capa para rojo , una para verde y otra para azul . Si el formato de imagen admite transparencia, se crea una cuarta capa, generalmente llamada alfa . Hablando en términos generales, una imagen en color es tres (o cuatro, si hay un canal alfa) en blanco y negro, ubicadas una encima de la otra.


  • RGB no es el único espacio de color; El formato JPEG, por ejemplo, usa YUV . Pero en este artículo no necesitaremos el resto de los espacios de color, por lo que no los consideramos.

Un conjunto de capas se puede representar en la memoria de dos maneras. O se almacenan por separado, o los valores de diferentes capas se entrelazan. En el último caso, las capas se llaman canales , y así es como funcionan los formatos más modernos.


Supongamos que tenemos un dibujo 4x4 que contiene tres capas: R para rojo, G para verde y B para el componente azul de cada uno de los píxeles. Se puede representar así:


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

Las tres capas se almacenan por separado. El formato alternativo se ve diferente:


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

  • cada triple de caracteres corresponde exactamente a un píxel
  • Los valores dentro del triple están en orden RGB . A veces se puede usar un orden diferente (por ejemplo, BGR ), pero este es el más común.

Para simplificar, organicé los píxeles en forma de matriz bidimensional, porque es más claro dónde está este o aquel triple en la imagen. Pero, de hecho, la memoria de la computadora no es bidimensional, sino unidimensional, por lo que la imagen 4x4 se almacenará así:


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

bpp


La abreviatura bpp se refiere al número de bits o bytes por píxel (bits / bytes por píxel). Es posible que hayas visto 24bpp o 3bpp . Estas dos características significan lo mismo: 24 bits por píxel o 3 bytes por píxel . Como siempre hay 8 bits en un byte, puede adivinar por el valor de cuál de las unidades en cuestión.


Representación de la memoria


24bpp , también 3bpp como 3bpp : el formato más común para almacenar flores. Así es como se ve un solo píxel en orden RGB en el nivel de bits individuales.


  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

  • Un byte para R , uno para G y otro para B , totalizando tres bytes.
  • Cada uno de ellos contiene un valor de 0 a 255.

Entonces, si el píxel dado tiene el siguiente color:


  • R 255
  • G 80
  • B 100

Entonces 255 almacenan en el primer byte, 80 en el segundo y 100 en el tercero.


Muy a menudo, estos valores se representan en hexadecimal . Di #ff5064 . Esto es mucho más conveniente y compacto: R = 0xff (es decir, R=255 en decimal), G = 0x50 (= G=80 ), B=0x64 (= B=100 ).


  • La representación hexadecimal tiene una propiedad útil. Como cada byte de color está representado por dos caracteres, cada carácter codifica exactamente medio byte o cuatro bits. 4 bits, por cierto, se llaman nibble .

Ancho de línea


Cuando los píxeles van uno tras otro y cada uno contiene más de un canal, los datos se confunden fácilmente. No se sabe cuándo termina una línea y comienza la siguiente, por lo tanto, para interpretar un archivo con un mapa de bits, debe conocer el tamaño de la imagen y el bpp . En nuestro caso, la imagen tiene un ancho de w = 4 píxeles y cada uno de estos píxeles contiene 3 bytes, por lo que la cadena está codificada con 12 bytes (en general w*bpp ).


  • Una cadena no siempre está codificada con exactamente w*bpp bytes; A menudo, se le agregan píxeles "ocultos" para que el ancho de la imagen tenga algún tamaño. Por ejemplo, escalar imágenes es más rápido y más conveniente cuando su tamaño en píxeles es igual a una potencia de dos. Por lo tanto, el archivo puede contener (accesible para el usuario) una imagen de 120x120 píxeles, pero puede almacenarse como una imagen de 128x128. Cuando se muestra una imagen en la pantalla, estos píxeles se ignoran. Sin embargo, no necesitamos saber sobre ellos.

La coordenada de cualquier píxel (x, y) en la representación unidimensional es (y * w + x) * bpp . Esto, en general, es obvio: y es el número de línea, cada línea contiene w píxeles, por lo que y * w es el comienzo de la línea deseada, y +x nos lleva a la x deseada dentro de ella. Y dado que las coordenadas no están en bytes, sino en píxeles, todo esto se multiplica por el tamaño del píxel bpp , en este caso en bytes. Como el píxel tiene un tamaño distinto de cero, debe leer exactamente los bytes bpp , comenzando desde la coordenada recibida, y tendremos una representación completa del píxel deseado.


Atlas de fuentes


En realidad, los monitores existentes no muestran un píxel en su conjunto, sino tres subpíxeles: rojo, azul y verde. Si observa el monitor con aumento, verá algo como esto:




Estamos interesados ​​en la pantalla LCD, ya que lo más probable es que sea de un monitor que leas este texto. Por supuesto, hay dificultades:


  • No todas las matrices usan exactamente este orden de subpíxeles, a veces BGR.
  • Si gira el monitor (por ejemplo, mire el teléfono en orientación horizontal), el patrón también rotará y la fuente dejará de funcionar.
  • Las diferentes orientaciones matriciales y la disposición de los subpíxeles requerirán volver a trabajar la fuente en sí.
  • En particular, no funciona en pantallas AMOLED que usan el diseño PenTile . Tales pantallas se usan con mayor frecuencia en dispositivos móviles.

El uso de hacks de subpíxeles para aumentar la resolución se denomina renderizado de subpíxeles . Puede leer sobre su uso en tipografía, por ejemplo, aquí .


Afortunadamente para nosotros, Matt Sarnov ya descubrió el uso de la representación de subpíxeles para crear una pequeña fuente de militexto . Manualmente, creó esta pequeña imagen:



Lo cual, si observa con mucho cuidado el monitor, se ve así:



Y aquí está, aumentado programáticamente en 12 veces:



Basado en su trabajo, creé un atlas de fuentes en el que cada personaje corresponde a una columna de 1x5 píxeles. El orden de los caracteres es el siguiente:


 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ


El mismo atlas aumentó 12 veces:



Con 36 caracteres utilizados, se 365 exactamente 365 píxeles. Si suponemos que cada píxel ocupa 3 bytes, entonces necesitamos 36*5*3 = 540 bytes para almacenar la imagen completa (aprox . Por: en el original, una serie confusa de ediciones sobre el canal alfa, borrando metadatos, etc.). n. En la traducción, lo omití y uso solo la versión final del archivo ). Un archivo PNG pasado a través de pngcrush y optipng toma aún menos:


 # wc -c < font-crushed.png 390

Pero puede lograr un tamaño aún más pequeño si usa un enfoque ligeramente diferente


Compresión


El lector atento podría notar que el atlas usa solo 7 colores:


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

Paleta


En tales situaciones, a menudo es más fácil crear una paleta. Luego, para cada píxel, puede almacenar no tres bytes de color, sino solo el número de color en la paleta. En nuestro caso, 3 bits ( 7 < 2^3 ) serán suficientes para elegir entre 7 colores. Si asignamos un valor de tres bits a cada píxel, entonces todo el atlas se ajustará en 68 bytes .


  • El lector, versado en la compresión de datos, puede responder que, en general, existen "bits fraccionarios" y en nuestro caso son suficientes 2.875 bits por píxel . Esta densidad se puede lograr usando magia negra, conocida como codificación aritmética . No haremos esto, porque la codificación aritmética es algo complicado, y 68 bytes ya es un poco.

Alineación


La codificación de tres bits tiene un serio inconveniente. Los píxeles no se pueden distribuir uniformemente en bytes de 8 bits, lo cual es importante porque los bytes son el área de memoria direccionable más pequeña. Digamos que queremos guardar tres píxeles:


 ABC

Si cada uno toma 3 bits, se necesitarán 2 bytes para almacenarlos ( - indica bits no utilizados):


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

Es importante destacar que el píxel C no solo deja un montón de espacio vacío; Está dividido entre dos bytes. Cuando comenzamos a agregar los siguientes píxeles, se pueden colocar de forma arbitraria en relación con los límites de bytes. La solución más simple sería usar nibble por píxel, porque 8 está perfectamente dividido por 4 y le permite colocar exactamente dos píxeles en cada byte. Pero esto aumentará el tamaño del atlas en un tercio, de 68 bytes a 90 bytes .


  • De hecho, el archivo se puede hacer aún más pequeño utilizando la codificación de palíndromo, la codificación por intervalos y otras técnicas de compresión. Al igual que la codificación aritmética, posponemos estas técnicas hasta el próximo artículo.

Bit buffer


Afortunadamente, no hay nada fundamentalmente imposible al trabajar con valores de 3 bits. Solo necesita controlar qué posición dentro del byte estamos escribiendo o leyendo en este momento. La siguiente clase simple convierte un flujo de datos de 3 bits en una matriz de bytes.


  • Por razones de legibilidad, el código está escrito en JS, pero el mismo método está generalizado a otros idiomas.
  • Orden usada de byte bajo 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(''); } };

Descarguemos y codifiquemos el archivo 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 se esperaba, el atlas se ajusta a 68 bytes , que es 6 veces más pequeño que el archivo PNG.


)


Ahora, convierta la imagen en una cadena para que pueda pegarla en el código fuente. En esencia, el método to_string esto: representa el contenido de cada byte como un número hexadecimal.


 305000000c0328d6d4b24cb46d516d4ddab669926a0ddab651db76150060009c0285 e6a0752db59054655bd7b569d26a4ddba053892a003060400d232850b40a6b61ad00

Pero la cadena resultante todavía es bastante larga, porque nos limitamos a un alfabeto de 16 caracteres. Puede reemplazarlo con base64 , en el que hay cuatro veces más caracteres.


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

En base64, el atlas se ve así:


 MFAAAAwDKNbUsky0bVFtTdq2aZJqDdq2Udt2FQBgAJwCheagdS21kFRlW9e1adJqTdugU4kqADBgQA0jKFC0CmthrQA=

Esta línea se puede codificar al módulo JS y usar para rasterizar el texto.


Rasterización


Para ahorrar memoria, solo se decodificará una letra a la 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; }

La función de decode toma un carácter como entrada y devuelve la columna correspondiente en la imagen de origen. Lo que es impresionante aquí es que solo se necesitan 5 bytes de memoria para decodificar un solo carácter, más ~ 1.875 bytes para leer la parte deseada de la matriz, es decir. un promedio de 6.875 por letra. Si agrega 68 bytes para almacenar la matriz y 36 bytes para almacenar el alfabeto, resulta que, en teoría , puede representar texto con 128 bytes de RAM.


  • Esto es posible si reescribe el código en C o ensamblador. En el contexto de la sobrecarga de JS, esto es un ahorro en las coincidencias.

Solo queda reunir estas columnas en un solo conjunto y devolver una imagen con 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}; };

Esta será la fuente más pequeña posible.


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

Agregue una pequeña imagen para obtener la imagen en un formato legible:


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

Y aquí está el resultado final:



También se incrementa en 12 veces:



Está tomada desde una macro de monitor mal calibrada:



Y finalmente, es mejor en el monitor:


Source: https://habr.com/ru/post/460697/

More articles:


All Articles