Aufgabe: Verwenden Sie möglichst wenig Ressourcen, um aussagekräftigen Text zu rendern.

Wie klein kann eine lesbare Schrift sein?
Wie viel Speicher wird zum Speichern benötigt?
Wie viel Code wird benötigt, um es zu verwenden?

Mal sehen, was wir bekommen. Spoiler

Einführung in Bitmaps

Computer präsentieren Bitmaps als Bitmaps. Es geht nicht um das .bmp Format, sondern um eine Möglichkeit, Pixel im Speicher zu speichern. Um zu verstehen, was passiert, müssen wir etwas darüber lernen.

Ebenen

Ein Bild enthält normalerweise mehrere Ebenen übereinander. Meistens entsprechen sie den Koordinaten des RGB-Farbraums . Eine Schicht für Rot , eine für Grün und eine für Blau . Wenn das Bildformat Transparenz unterstützt, wird eine vierte Ebene dafür erstellt, die normalerweise als Alpha bezeichnet wird . Grob gesagt ist ein Farbbild drei (oder vier, wenn es einen Alphakanal gibt) Schwarzweiß, die übereinander liegen.

RGB ist nicht der einzige Farbraum. Das JPEG-Format verwendet beispielsweise YUV . In diesem Artikel benötigen wir jedoch nicht den Rest der Farbräume, daher berücksichtigen wir sie nicht.

Eine Reihe von Ebenen kann auf zwei Arten im Speicher dargestellt werden. Entweder werden sie separat gespeichert oder Werte aus verschiedenen Ebenen werden verschachtelt. Im letzteren Fall werden Ebenen als Kanäle bezeichnet , und so funktionieren die meisten modernen Formate.

Angenommen, wir haben eine 4x4-Zeichnung mit drei Ebenen: R für Rot, G für Grün und B für die blaue Komponente jedes Pixels. Es kann so dargestellt werden:

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

Alle drei Schichten werden separat gespeichert. Das alternierende Format sieht anders aus:

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

Jedes Dreifach von Zeichen entspricht genau einem Pixel
Die Werte innerhalb des Tripels sind in RGB- Reihenfolge. Manchmal kann eine andere Reihenfolge verwendet werden (z. B. BGR ), aber diese ist die häufigste.

Der Einfachheit halber habe ich die Pixel in Form einer zweidimensionalen Matrix angeordnet, da klarer ist, wo sich dieses oder jenes Tripel im Bild befindet. Tatsächlich ist der Computerspeicher jedoch nicht zweidimensional, sondern eindimensional, sodass das 4x4-Bild folgendermaßen gespeichert wird:

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

bpp

Die Abkürzung bpp bezieht sich auf die Anzahl der Bits oder Bytes pro Pixel (Bits / Bytes pro Pixel). Möglicherweise haben 3bpp 24bpp oder 3bpp . Diese beiden Eigenschaften bedeuten dasselbe - 24 Bit pro Pixel oder 3 Bytes pro Pixel . Da ein Byte immer 8 Bits enthält, können Sie anhand des Werts der betreffenden Einheiten erraten.

Speicherdarstellung

24bpp , auch bekannt als 3bpp - das am häufigsten verwendete Format zum Speichern von Blumen. So sieht ein einzelnes Pixel in RGB- Reihenfolge auf der Ebene einzelner Bits aus.

  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

Ein Byte für R , eines für G und eines für B , insgesamt drei Bytes.
Jeder von ihnen enthält einen Wert von 0 bis 255.

Wenn also das angegebene Pixel die folgende Farbe hat:

R 255
G 80
B 100

Dann werden 255 im ersten Byte, 80 im zweiten und 100 im dritten Byte gespeichert.

Meistens werden diese Werte hexadezimal dargestellt . Sagen Sie #ff5064 . Dies ist viel bequemer und kompakter: R = 0xff (d. H. R=255 in Dezimalzahl), G = 0x50 (= G=80 ), B=0x64 (= B=100 ).

Die hexadezimale Darstellung hat eine nützliche Eigenschaft. Da jedes Farbbyte durch zwei Zeichen dargestellt wird, codiert jedes Zeichen genau ein halbes Byte oder vier Bits. 4 Bits werden übrigens als Knabbern bezeichnet .

Linienbreite

Wenn Pixel nacheinander verlaufen und jeder mehr als einen Kanal enthält, können die Daten leicht verwechselt werden. Es ist nicht bekannt, wann eine Zeile endet und die nächste beginnt. Um eine Datei mit einer Bitmap zu interpretieren, müssen Sie die Bildgröße und den bpp kennen . In unserem Fall hat das Bild eine Breite von w = 4 Pixel und jedes dieser Pixel enthält 3 Bytes, sodass die Zeichenfolge mit 12 (im allgemeinen Fall w*bpp ) Bytes codiert ist.

Ein String wird nicht immer mit genau w*bpp Bytes codiert. Oft werden "versteckte" Pixel hinzugefügt, um die Bildbreite auf eine bestimmte Größe zu bringen. Zum Beispiel ist das Skalieren von Bildern schneller und bequemer, wenn ihre Größe in Pixel einer Zweierpotenz entspricht. Daher kann die Datei ein Bild von 120 x 120 Pixel enthalten (für den Benutzer zugänglich), das jedoch als Bild von 128 x 128 Pixel gespeichert ist. Wenn ein Bild auf dem Bildschirm angezeigt wird, werden diese Pixel ignoriert. Wir müssen sie jedoch nicht kennen.

Die Koordinate eines beliebigen Pixels (x, y) in der eindimensionalen Darstellung ist (y * w + x) * bpp . Dies ist im Allgemeinen offensichtlich: y ist die Zeilennummer, jede Zeile enthält w Pixel, also ist y * w der Anfang der gewünschten Zeile, und +x führt uns zum gewünschten x darin. Und da die Koordinaten nicht in Bytes, sondern in Pixeln angegeben sind, wird dies alles mit der Größe des bpp Pixels multipliziert, in diesem Fall in Bytes. Da das Pixel eine Größe ungleich Null hat, müssen Sie ausgehend von der empfangenen Koordinate genau bpp Bytes lesen, und wir erhalten eine vollständige Darstellung des gewünschten Pixels.

Schriftatlas

Tatsächlich vorhandene Monitore zeigen nicht ein Pixel als Ganzes an, sondern drei Subpixel - rot, blau und grün. Wenn Sie den Monitor unter Vergrößerung betrachten, sehen Sie ungefähr Folgendes:

Wikipedia Zeichnung

Wir sind an LCD interessiert, da Sie diesen Text höchstwahrscheinlich von einem solchen Monitor aus lesen. Natürlich gibt es Fallstricke:

Nicht alle Matrizen verwenden genau diese Reihenfolge von Subpixeln, manchmal BGR.
Wenn Sie den Monitor drehen (z. B. im Querformat auf das Telefon schauen), dreht sich auch das Muster und die Schriftart funktioniert nicht mehr.
Unterschiedliche Matrixausrichtungen und die Anordnung der Subpixel erfordern eine Überarbeitung der Schriftart.
Insbesondere funktioniert es nicht bei AMOLED-Displays , die das PenTile-Layout verwenden . Solche Anzeigen werden am häufigsten in mobilen Geräten verwendet.

Die Verwendung von Subpixel-Hacks zur Erhöhung der Auflösung wird als Subpixel-Rendering bezeichnet . Hier können Sie beispielsweise über die Verwendung in der Typografie lesen.

Zum Glück hat Matt Sarnov bereits mithilfe von Subpixel-Rendering eine winzige Millitext- Schriftart erstellt. Manuell schuf er dieses winzige Bild:

Was, wenn Sie genau auf den Monitor schauen, so aussieht:

Und hier ist es, programmatisch um das 12-fache erhöht:

Basierend auf seiner Arbeit habe ich einen Schriftatlas erstellt, in dem jedes Zeichen einer Spalte von 1x5 Pixel entspricht. Die Zeichenreihenfolge ist wie folgt:

 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Der gleiche Atlas wurde um das 12-fache erhöht:

Mit 36 verwendeten Zeichen werden genau 36 365 Pixel 365 . Wenn wir davon ausgehen, dass jedes Pixel 3 Bytes belegt, benötigen wir 36*5*3 = 540 Bytes, um das gesamte Bild zu speichern (ca .: im Original eine verwirrende Reihe von Änderungen am Alphakanal, Löschen von Metadaten usw.). n. In der Übersetzung habe ich es weggelassen und nur die endgültige Version der Datei verwendet . Eine PNG-Datei, die durch pngcrush und optipng geleitet wird, benötigt noch weniger:

 # wc -c < font-crushed.png 390

Sie können jedoch eine noch kleinere Größe erzielen, wenn Sie einen etwas anderen Ansatz verwenden

Komprimierung

Der aufmerksame Leser konnte feststellen, dass der Atlas nur 7 Farben verwendet:

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

Palette

In solchen Situationen ist es oft einfacher, eine Palette zu erstellen. Dann können Sie für jedes Pixel nicht drei Bytes Farbe speichern, sondern nur die Farbnummer in der Palette. In unserem Fall reichen 3 Bits ( 7 < 2^3 ) aus, um aus 7 Farben auszuwählen. Wenn wir jedem Pixel einen Drei-Bit-Wert zuweisen, passt der gesamte Atlas in 68 Bytes .

Der Leser, der sich mit Datenkomprimierung auskennt, kann antworten, dass es im Allgemeinen so etwas wie "Bruchbits" gibt und in unserem Fall 2,875 Bits pro Pixel ausreichen. Diese Dichte kann mit schwarzer Magie erreicht werden, die als arithmetische Codierung bekannt ist . Wir werden dies nicht tun, da die arithmetische Codierung eine komplizierte Sache ist und 68 Bytes bereits ein bisschen sind.

Ausrichtung

Die Drei-Bit-Codierung hat einen schwerwiegenden Nachteil. Pixel können nicht gleichmäßig auf 8-Bit-Bytes verteilt werden. Dies ist wichtig, da Bytes der kleinste adressierbare Speicherbereich sind. Angenommen, wir möchten drei Pixel speichern:

ABC

Wenn jedes 3 Bits benötigt, werden 2 Bytes benötigt, um sie zu speichern ( - zeigt nicht verwendete Bits an):

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

Wichtig ist, dass Pixel C nicht nur einen leeren Raum hinterlässt. Es wird zwischen zwei Bytes gerissen . Wenn wir die folgenden Pixel hinzufügen, können sie beliebig relativ zu den Bytegrenzen positioniert werden. Die einfachste Lösung wäre die Verwendung von Nibble pro Pixel, da 8 perfekt durch 4 geteilt ist und Sie genau zwei Pixel in jedem Byte platzieren können. Dies erhöht jedoch die Größe des Atlas um ein Drittel von 68 Byte auf 90 Byte .

Tatsächlich kann die Datei mithilfe von Palindromcodierung, Intervallcodierung und anderen Komprimierungstechniken noch kleiner gemacht werden. Wie bei der arithmetischen Codierung verschieben wir diese Techniken auf den nächsten Artikel.

Bitpuffer

Glücklicherweise ist die Arbeit mit 3-Bit-Werten grundsätzlich nicht unmöglich. Sie müssen nur überwachen, an welcher Position innerhalb des Bytes wir gerade schreiben oder lesen. Die folgende einfache Klasse konvertiert einen 3-Bit-Datenstrom in ein Array von Bytes.

Aus Gründen der Lesbarkeit ist der Code in JS geschrieben, aber dieselbe Methode wird auf andere Sprachen verallgemeinert.
Verwendete Reihenfolge von Low Byte bis High ( 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(''); } };

Laden Sie die Atlas-Datei herunter und codieren Sie sie:

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

Wie erwartet passt der Atlas auf 68 Bytes , was sechsmal kleiner ist als die PNG-Datei.

( Anmerkung per.: Der Autor ist etwas unaufrichtig: Er hat die Palette und die Bildgröße nicht gespeichert, was nach meinen Schätzungen 23 Bytes mit einer festen Palettengröße erfordert und die Bildgröße auf 91 Bytes erhöht. )

Nun konvertieren wir das Bild in eine Zeichenfolge, damit Sie es in den Quellcode einfügen können. Im Wesentlichen macht die to_string Methode dies: Sie repräsentiert den Inhalt jedes Bytes als Hexadezimalzahl.

 305000000c0328d6d4b24cb46d516d4ddab669926a0ddab651db76150060009c0285 e6a0752db59054655bd7b569d26a4ddba053892a003060400d232850b40a6b61ad00

Die resultierende Zeichenfolge ist jedoch immer noch ziemlich lang, da wir uns auf ein Alphabet mit 16 Zeichen beschränkt haben. Sie können es durch base64 ersetzen, in dem viermal so viele Zeichen vorhanden sind.

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

In base64 sieht der Atlas folgendermaßen aus:

 MFAAAAwDKNbUsky0bVFtTdq2aZJqDdq2Udt2FQBgAJwCheagdS21kFRlW9e1adJqTdugU4kqADBgQA0jKFC0CmthrQA=

Diese Zeile kann fest in das JS-Modul codiert und zum Rastern des Texts verwendet werden.

Rasterisierung

Um Speicherplatz zu sparen, wird jeweils nur ein Buchstabe dekodiert.

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

Die decode nimmt ein Zeichen als Eingabe und gibt die entsprechende Spalte im Quellbild zurück. Was hier beeindruckend ist, ist, dass es nur 5 Bytes Speicher benötigt, um ein einzelnes Zeichen zu decodieren, plus ~ 1,875 Bytes, um das gewünschte Stück des Arrays zu lesen, d. H. durchschnittlich 6,875 pro Brief. Wenn Sie 68 Bytes zum Speichern des Arrays und 36 Bytes zum Speichern des Alphabets hinzufügen, stellt sich heraus, dass Sie theoretisch Text mit 128 Bytes RAM rendern können.

Dies ist möglich, wenn Sie den Code in C oder Assembler neu schreiben. Vor dem Hintergrund des JS-Overheads bedeutet dies eine Einsparung von Übereinstimmungen.

Es bleibt nur, diese Spalten zu einem Ganzen zusammenzufassen und ein Bild mit Text zurückzugeben.

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

Dies ist die kleinstmögliche Schriftart.

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

Fügen Sie einen kleinen Imagemagick hinzu , um das Bild in einem lesbaren Format zu erhalten:

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

Und hier ist das Endergebnis:

Es wird auch um das 12-fache erhöht:

Es wurde von einem schlecht kalibrierten Monitormakro aufgenommen:

Und schließlich ist es auf dem Monitor besser:

Kleinstmögliche Schriftart