Tâche: en utilisant le moins de ressources possible, rendez un texte significatif.

Quelle taille peut avoir une police lisible?
Combien de mémoire faut-il pour le stocker?
Combien de code faut-il pour l'utiliser?

Voyons voir ce que nous obtenons. Spoiler

Introduction aux bitmaps

Les ordinateurs présentent les bitmaps sous forme de bitmaps. Il ne s'agit pas du format .bmp , mais d'un moyen de stocker des pixels en mémoire. Pour comprendre ce qui se passe, nous devons apprendre quelque chose de cette façon.

Couches

Une image contient généralement plusieurs couches superposées. Ils correspondent le plus souvent aux coordonnées de l' espace colorimétrique RVB . Une couche pour le rouge , une pour le vert et une pour le bleu . Si le format d'image prend en charge la transparence, un quatrième calque est créé pour lui, généralement appelé alpha . En gros, une image couleur est de trois (ou quatre, s'il y a un canal alpha) en noir et blanc, situées l'une au-dessus de l'autre.

Le RVB n'est pas le seul espace colorimétrique; Le format JPEG, par exemple, utilise YUV . Mais dans cet article, nous n'aurons pas besoin du reste des espaces colorimétriques, nous ne les considérons donc pas.

Un ensemble de couches peut être représenté en mémoire de deux manières. Soit ils sont stockés séparément, soit les valeurs de différentes couches sont entrelacées. Dans ce dernier cas, les couches sont appelées canaux , et c'est ainsi que la plupart des formats modernes fonctionnent.

Supposons que nous ayons un dessin 4x4 contenant trois couches: R pour le rouge, G pour le vert et B pour la composante bleue de chacun des pixels. Il peut être représenté comme ceci:

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

Les trois couches sont stockées séparément. Le format alternatif est différent:

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

chaque triple de caractères correspond exactement à un pixel
les valeurs dans le triple sont dans l'ordre RVB . Parfois, un ordre différent peut être utilisé (par exemple, BGR ), mais celui-ci est le plus courant.

Par souci de simplicité, j'ai disposé les pixels sous la forme d'une matrice à deux dimensions, car il est plus clair où tel ou tel triple est dans l'image. Mais en fait, la mémoire de l'ordinateur n'est pas bidimensionnelle, mais unidimensionnelle, donc l'image 4x4 sera stockée comme ceci:

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

bpp

L'abréviation bpp fait référence au nombre de bits ou d'octets par pixel (bits / octets par pixel). Vous avez peut-être vu 24bpp ou 3 3bpp . Ces deux caractéristiques signifient la même chose - 24 bits par pixel ou 3 octets par pixel . Puisqu'il y a toujours 8 bits dans un octet, vous pouvez deviner par la valeur de laquelle des unités en question.

Représentation de la mémoire

24bpp , alias 3bpp - le format le plus courant pour stocker des fleurs. Voici à quoi ressemble un pixel dans l'ordre RVB au niveau des bits individuels.

  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 octet pour R , un pour G et un pour B , totalisant trois octets.
Chacun d'eux contient une valeur de 0 à 255.

Donc, si le pixel donné a la couleur suivante:

R 255
G 80
B 100

Ensuite, 255 stockés dans le premier octet, 80 dans le second et 100 dans le troisième.

Le plus souvent, ces valeurs sont représentées en hexadécimal . Dites #ff5064 . C'est beaucoup plus pratique et compact: R = 0xff (c'est-à-dire R=255 en décimal), G = 0x50 (= G=80 ), B=0x64 (= B=100 ).

La représentation hexadécimale a une propriété utile. Étant donné que chaque octet de couleur est représenté par deux caractères, chaque caractère code exactement un demi-octet ou quatre bits. Au fait, 4 bits sont appelés grignotage .

Largeur de ligne

Lorsque les pixels se succèdent et contiennent chacun plusieurs canaux, les données sont facilement confondues. On ne sait pas quand une ligne se termine et la suivante commence, donc, pour interpréter un fichier avec un bitmap, vous devez connaître la taille de l'image et bpp . Dans notre cas, l'image a une largeur de w = 4 pixels et chacun de ces pixels contient 3 octets, donc la chaîne est codée avec 12 octets (dans le cas général w*bpp ).

Une chaîne n'est pas toujours codée avec exactement w*bpp octets; Souvent, des pixels «cachés» y sont ajoutés pour amener la largeur de l'image à une certaine taille. Par exemple, la mise à l'échelle des images est plus rapide et plus pratique lorsque leur taille en pixels est égale à une puissance de deux. Par conséquent, le fichier peut contenir (accessible à l'utilisateur) une image de 120x120 pixels, mais être stocké sous la forme d'une image de 128x128. Lorsqu'une image est affichée à l'écran, ces pixels sont ignorés. Cependant, nous n'avons pas besoin de les connaître.

La coordonnée de tout pixel (x, y) dans la représentation unidimensionnelle est (y * w + x) * bpp . Ceci, en général, est évident: y est le numéro de ligne, chaque ligne contient w pixels, donc y * w est le début de la ligne souhaitée, et +x nous amène au x souhaité en son sein. Et comme les coordonnées ne sont pas en octets, mais en pixels, tout cela est multiplié par la taille du pixel bpp , en l'occurrence en octets. Étant donné que le pixel a une taille non nulle, vous devez lire exactement les octets bpp , à partir des coordonnées reçues, et nous aurons une représentation complète du pixel souhaité.

Atlas des polices

En fait, les moniteurs existants n'affichent pas un pixel dans son ensemble, mais trois sous-pixels - rouge, bleu et vert. Si vous regardez le moniteur sous grossissement, vous verrez quelque chose comme ceci:

Dessin Wikipédia

Nous nous intéressons à l'écran LCD, car c'est probablement à partir d'un tel moniteur que vous lisez ce texte. Bien sûr, il y a des écueils:

Toutes les matrices n'utilisent pas exactement cet ordre de sous-pixels, parfois BGR.
Si vous tournez le moniteur (par exemple, regardez le téléphone en orientation paysage), le motif pivotera également et la police cessera de fonctionner.
Différentes orientations de matrice et la disposition des sous-pixels nécessiteront de retravailler la police elle-même.
En particulier, il ne fonctionne pas sur les écrans AMOLED qui utilisent la disposition PenTile . Ces écrans sont le plus souvent utilisés dans les appareils mobiles.

L'utilisation de hacks de sous-pixels pour augmenter la résolution est appelée rendu de sous-pixels . Vous pouvez lire sur son utilisation en typographie, par exemple, ici .

Heureusement pour nous, Matt Sarnov a déjà compris en utilisant le rendu sous-pixel pour créer une petite police millitext . Manuellement, il a créé cette petite image:

Ce qui, si vous regardez attentivement le moniteur, ressemble à ceci:

Et le voici, multiplié par 12 par programme:

Sur la base de son travail, j'ai créé un atlas de polices dans lequel chaque caractère correspond à une colonne de 1x5 pixels. L'ordre des caractères est le suivant:

 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Le même atlas a été multiplié par 12:

Avec 36 caractères utilisés, exactement 365 pixels sont 365 . Si nous supposons que chaque pixel occupe 3 octets, nous avons besoin de 36*5*3 = 540 octets pour stocker l'image entière (environ par .: Dans l'original, une série confuse de modifications sur le canal alpha, la suppression des métadonnées, etc.). n. Dans la traduction, je l'ai omis et n'utilise que la version finale du fichier ). Un fichier PNG passé par pngcrush et optipng prend encore moins:

 # wc -c < font-crushed.png 390

Mais vous pouvez atteindre une taille encore plus petite si vous utilisez une approche légèrement différente

La compression

Le lecteur attentif a pu remarquer que l'atlas n'utilise que 7 couleurs:

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

Palette

Dans de telles situations, il est souvent plus facile de créer une palette. Ensuite, pour chaque pixel, vous pouvez stocker non pas trois octets de couleur, mais uniquement le numéro de couleur dans la palette. Dans notre cas, 3 bits ( 7 < 2^3 ) suffiront pour choisir parmi 7 couleurs. Si nous attribuons une valeur à trois bits à chaque pixel, alors l'ensemble de l'atlas tiendra en 68 octets .

Le lecteur, versé dans la compression de données, peut répondre qu'en général, il existe des «bits fractionnaires» et dans notre cas 2,875 bits par pixel suffisent. Cette densité peut être obtenue en utilisant la magie noire, connue sous le nom de codage arithmétique . Nous ne le ferons pas, car le codage arithmétique est une chose compliquée, et 68 octets, c'est déjà un peu.

Alignement

Le codage à trois bits présente un sérieux inconvénient. Les pixels ne peuvent pas être répartis uniformément sur des octets 8 bits, ce qui est important car les octets sont la plus petite zone de mémoire adressable. Disons que nous voulons économiser trois pixels:

ABC

Si chacun prend 3 bits, il faudra alors 2 octets pour les stocker ( - indique les bits inutilisés):

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

Surtout, le pixel C ne laisse pas seulement un tas d'espace vide; il est déchiré entre deux octets. Lorsque nous commençons à ajouter les pixels suivants, ils peuvent être positionnés arbitrairement par rapport aux limites d'octets. La solution la plus simple serait d'utiliser un quartet par pixel, car 8 est parfaitement divisé par 4 et vous permet de placer exactement deux pixels dans chaque octet. Mais cela augmentera la taille de l'atlas d'un tiers, de 68 octets à 90 octets .

En fait, le fichier peut être encore plus petit en utilisant le codage palindrome, le codage d'intervalle et d'autres techniques de compression. Comme le codage arithmétique, nous reportons ces techniques au prochain article.

Tampon de bits

Heureusement, il n'y a rien de fondamentalement impossible à travailler avec des valeurs 3 bits. Il vous suffit de surveiller la position à l'intérieur de l'octet que nous écrivons ou lisons en ce moment. La classe simple suivante convertit un flux de données 3 bits en un tableau d'octets.

Pour des raisons de lisibilité, le code est écrit en JS, mais la même méthode est généralisée à d'autres langages.
Ordre utilisé de l'octet bas au haut ( 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(''); } };

Téléchargeons et encodons le fichier 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()));

Comme prévu, l'atlas contient 68 octets , ce qui est 6 fois plus petit que le fichier PNG.

( piste approximative: l'auteur est un peu malhonnête: il n'a pas enregistré la palette et la taille de l'image, ce qui, selon mes estimations, nécessitera 23 octets avec une taille de palette fixe et augmentera la taille de l'image à 91 octets )

Convertissons maintenant l'image en chaîne afin de pouvoir la coller dans le code source. En substance, la méthode to_string cela: elle représente le contenu de chaque octet sous la forme d'un nombre hexadécimal.

 305000000c0328d6d4b24cb46d516d4ddab669926a0ddab651db76150060009c0285 e6a0752db59054655bd7b569d26a4ddba053892a003060400d232850b40a6b61ad00

Mais la chaîne résultante est encore assez longue, car nous nous sommes limités à un alphabet de 16 caractères. Vous pouvez le remplacer par base64 , dans lequel il y a quatre fois plus de caractères.

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

En base64, l'atlas ressemble à ceci:

 MFAAAAwDKNbUsky0bVFtTdq2aZJqDdq2Udt2FQBgAJwCheagdS21kFRlW9e1adJqTdugU4kqADBgQA0jKFC0CmthrQA=

Cette ligne peut être codée en dur sur le module JS et utilisée pour pixelliser le texte.

Rastérisation

Pour économiser de la mémoire, une seule lettre sera décodée à la fois.

 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 fonction de decode prend un caractère en entrée et renvoie la colonne correspondante dans l'image source. Ce qui est impressionnant ici, c'est qu'il ne faut que 5 octets de mémoire pour décoder un seul caractère, plus ~ 1,875 octets pour lire la partie souhaitée du tableau, c'est-à-dire une moyenne de 6.875 par lettre. Si vous ajoutez 68 octets pour stocker le tableau et 36 octets pour stocker l'alphabet, il s'avère que théoriquement, vous pouvez rendre le texte avec 128 octets de RAM.

Ceci est possible si vous réécrivez le code en C ou en assembleur. Dans le contexte de la surcharge JS, il s'agit d'une économie sur les correspondances.

Il ne reste plus qu'à rassembler ces colonnes en un seul ensemble et à renvoyer une image avec du texte.

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

Ce sera la police la plus petite possible.

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

Ajoutez un petit imagemagick pour obtenir l'image dans un format lisible:

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

Et voici le résultat final:

Il est également augmenté de 12 fois:

Elle a été prise à partir d'une macro de moniteur mal calibrée:

Et enfin, c'est mieux sur le moniteur:

Police la plus petite possible