Geekly articles weekly

Font sekecil mungkin

Tugas: menggunakan sumber daya sekecil mungkin, render teks yang bermakna.


  • Seberapa kecil font yang bisa dibaca?
  • Berapa banyak memori yang dibutuhkan untuk menyimpannya?
  • Berapa banyak kode yang diperlukan untuk menggunakannya?

Mari kita lihat apa yang kita dapatkan. Spoiler



Pengantar Bitmap


Komputer menghadirkan bitmap sebagai bitmap. Ini bukan tentang format .bmp , tetapi tentang cara untuk menyimpan piksel dalam memori. Untuk memahami apa yang terjadi, kita perlu belajar sesuatu tentang cara ini.


Layers


Suatu gambar biasanya berisi beberapa lapisan di atas satu sama lain. Paling sering mereka sesuai dengan koordinat ruang warna RGB . Satu lapisan untuk merah , satu untuk hijau dan satu untuk biru . Jika format gambar mendukung transparansi, maka lapisan keempat dibuat untuk itu, biasanya disebut alpha . Secara kasar, gambar berwarna adalah tiga (atau empat, jika ada saluran alfa) hitam dan putih, terletak satu di atas yang lain.


  • RGB bukan satu-satunya ruang warna; Format JPEG, misalnya, menggunakan YUV . Tetapi dalam artikel ini kita tidak perlu sisa ruang warna, jadi kita tidak mempertimbangkannya.

Seperangkat lapisan dapat direpresentasikan dalam memori dengan dua cara. Entah mereka disimpan secara terpisah, atau nilai-nilai dari lapisan yang berbeda disisipkan. Dalam kasus terakhir, layer disebut saluran , dan itulah cara sebagian besar format modern bekerja.


Misalkan kita memiliki gambar 4x4 yang mengandung tiga lapisan: R untuk merah, G untuk hijau dan B untuk komponen biru dari masing-masing piksel. Itu bisa direpresentasikan seperti ini:


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

Ketiga lapisan disimpan secara terpisah. Format bolak-balik terlihat berbeda:


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

  • setiap tiga karakter sesuai dengan tepat satu piksel
  • nilai dalam triple berada dalam urutan RGB . Kadang-kadang urutan yang berbeda dapat digunakan (misalnya, BGR ), tetapi yang ini adalah yang paling umum.

Untuk kesederhanaan, saya mengatur piksel dalam bentuk matriks dua dimensi, karena lebih jelas di mana triple ini atau itu ada dalam gambar. Namun pada kenyataannya, memori komputer bukan dua dimensi, tetapi satu dimensi, sehingga gambar 4x4 akan disimpan seperti ini:


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

bpp


Singkatan bpp mengacu pada jumlah bit atau byte per piksel (bit / byte per piksel). Anda mungkin melihat 24bpp atau 3bpp . Kedua karakteristik ini memiliki arti yang sama - 24 bit per piksel atau 3 byte per piksel . Karena selalu ada 8 bit dalam satu byte, Anda dapat menebak dengan nilai unit mana yang dimaksud.


Representasi memori


24bpp , alias 3bpp - format yang paling umum untuk menyimpan bunga. Ini adalah bagaimana satu piksel dalam urutan RGB terlihat pada tingkat bit individual.


  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

  • Satu byte untuk R , satu untuk G dan satu untuk B , totalnya tiga byte.
  • Masing-masing berisi nilai dari 0 hingga 255.

Jadi jika piksel yang diberikan memiliki warna berikut:


  • R 255
  • G 80
  • B 100

Kemudian 255 disimpan di byte pertama, 80 di byte kedua, dan 100 di byte ketiga.


Paling sering, nilai-nilai ini direpresentasikan dalam heksadesimal . Katakan #ff5064 . Ini jauh lebih nyaman dan kompak: R = 0xff (mis. R=255 dalam desimal), G = 0x50 (= G=80 ), B=0x64 (= B=100 ).


  • Representasi heksadesimal memiliki satu properti yang bermanfaat. Karena setiap byte warna diwakili oleh dua karakter, masing-masing karakter mengkodekan tepat setengah byte, atau empat bit. 4 bit, omong-omong, disebut nibble .

Lebar garis


Ketika piksel berjalan satu demi satu dan masing-masing berisi lebih dari satu saluran, datanya mudah bingung. Tidak diketahui kapan satu baris berakhir dan selanjutnya dimulai, oleh karena itu, untuk menafsirkan file dengan bitmap, Anda perlu mengetahui ukuran gambar dan bpp . Dalam kasus kami, gambar memiliki lebar w = 4 piksel dan masing-masing piksel ini mengandung 3 byte, sehingga string dikodekan dengan 12 (dalam kasus umum w*bpp ) byte.


  • Sebuah string tidak selalu dikodekan dengan byte w*bpp ; Seringkali, piksel "tersembunyi" ditambahkan ke dalamnya untuk membawa lebar gambar ke beberapa ukuran. Misalnya, penskalaan gambar lebih cepat dan lebih nyaman ketika ukurannya dalam piksel sama dengan kekuatan dua. Oleh karena itu, file tersebut mungkin berisi (dapat diakses oleh pengguna) gambar 120x120 piksel, tetapi disimpan sebagai gambar 128x128. Saat gambar ditampilkan di layar, piksel ini diabaikan. Namun, kita tidak perlu tahu tentang mereka.

Koordinat piksel apa pun (x, y) dalam representasi satu dimensi adalah (y * w + x) * bpp . Ini, secara umum, jelas: y adalah nomor baris, setiap baris berisi w piksel, jadi y * w adalah awal dari baris yang diinginkan, dan +x membawa kita ke x diinginkan di dalamnya. Dan karena koordinat tidak dalam byte, tetapi dalam piksel, semua ini dikalikan dengan ukuran piksel bpp , dalam hal ini dalam byte. Karena piksel memiliki ukuran bukan nol, Anda perlu membaca byte bpp tepat, mulai dari koordinat yang diterima, dan kami akan memiliki representasi lengkap dari piksel yang diinginkan.


Atlas font


Sebenarnya monitor yang ada tidak menampilkan piksel secara keseluruhan, tetapi tiga subpiksel - merah, biru dan hijau. Jika Anda melihat monitor dalam pembesaran, Anda akan melihat sesuatu seperti ini:




Kami tertarik pada LCD, karena kemungkinan besar dari monitor itulah Anda membaca teks ini. Tentu saja, ada jebakan:


  • Tidak semua matriks menggunakan urutan subpiksel ini, terkadang BGR.
  • Jika Anda memutar monitor (misalnya, lihat telepon dalam orientasi mendatar), polanya juga akan berputar dan font akan berhenti bekerja.
  • Orientasi matriks yang berbeda dan pengaturan subpiksel akan membutuhkan pengerjaan ulang font itu sendiri.
  • Secara khusus, ini tidak berfungsi pada layar AMOLED yang menggunakan tata letak PenTile . Tampilan seperti itu paling sering digunakan di perangkat seluler.

Menggunakan peretasan subpixel untuk meningkatkan resolusi disebut rendering subpixel . Anda dapat membaca tentang penggunaannya dalam tipografi, misalnya di sini .


Untungnya bagi kami, Matt Sarnov sudah menemukan menggunakan rendering subpixel untuk membuat font millitext kecil. Secara manual, ia menciptakan gambar kecil ini:



Yang, jika Anda melihat monitor dengan sangat hati-hati, terlihat seperti ini:



Dan ini dia, secara pemrograman meningkat 12 kali:



Berdasarkan karyanya, saya membuat atlas font di mana setiap karakter sesuai dengan kolom 1x5 piksel. Urutan karakter adalah sebagai berikut:


 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ


Atlas yang sama meningkat 12 kali:



Dengan 36 karakter yang digunakan, tepatnya 365 piksel 365 . Jika kita mengasumsikan bahwa setiap piksel menempati 3 byte, maka kita membutuhkan 36*5*3 = 540 byte untuk menyimpan seluruh gambar (kira-kira .: Dalam aslinya, serangkaian suntingan yang membingungkan tentang saluran alfa, menghapus metadata, dll.). n. Dalam terjemahan, saya menghapusnya dan hanya menggunakan versi final file ). File PNG yang melewati pngcrush dan optipng membutuhkan waktu lebih sedikit:


 # wc -c < font-crushed.png 390

Tetapi Anda dapat mencapai ukuran yang lebih kecil jika Anda menggunakan pendekatan yang sedikit berbeda


Kompresi


Pembaca yang penuh perhatian dapat memperhatikan bahwa atlas hanya menggunakan 7 warna:


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

Palet


Dalam situasi seperti itu, seringkali lebih mudah untuk membuat palet. Kemudian untuk setiap piksel Anda dapat menyimpan bukan tiga byte warna, tetapi hanya nomor warna dalam palet. Dalam kasus kami, 3 bit ( 7 < 2^3 ) akan cukup untuk dipilih dari 7 warna. Jika kita menetapkan nilai tiga bit untuk setiap piksel, maka seluruh atlas akan muat dalam 68 byte .


  • Pembaca, berpengalaman dalam kompresi data, dapat menjawab bahwa secara umum ada hal seperti "bit fraksional" dan dalam kasus kami 2,875 bit per piksel sudah cukup. Kepadatan ini dapat dicapai dengan menggunakan ilmu hitam, yang dikenal sebagai kode aritmatika . Kami tidak akan melakukan ini, karena pengkodean aritmatika adalah hal yang rumit, dan 68 byte sudah sedikit.

Perataan


Pengkodean tiga bit memiliki satu kelemahan serius. Pixel tidak dapat didistribusikan secara merata melintasi 8-bit byte, yang penting karena byte adalah area memori terkecil yang dapat dialamatkan. Katakanlah kita ingin menyimpan tiga piksel:


 ABC

Jika masing-masing membutuhkan 3 bit, maka akan dibutuhkan 2 byte untuk menyimpannya ( - menunjukkan bit yang tidak digunakan):


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

Yang penting, pixel C tidak hanya meninggalkan banyak ruang kosong; itu terbelah antara dua byte. Ketika kami mulai menambahkan piksel berikut, piksel dapat diposisikan secara sewenang-wenang relatif terhadap batas byte. Solusi paling sederhana adalah dengan menggunakan nibble per pixel, karena 8 dibagi dengan sempurna oleh 4 dan memungkinkan Anda untuk menempatkan tepat dua pixel di setiap byte. Tetapi ini akan meningkatkan ukuran atlas sebesar sepertiga, dari 68 byte menjadi 90 byte .


  • Bahkan, file dapat dibuat lebih kecil lagi menggunakan palindrome coding, interval coding, dan teknik kompresi lainnya. Seperti pengkodean aritmatika, kami menunda teknik ini hingga artikel selanjutnya.

Buffer bit


Untungnya, pada dasarnya tidak ada yang mustahil dalam bekerja dengan nilai 3-bit. Anda hanya perlu memantau posisi di dalam byte yang sedang kita tulis atau baca saat ini. Kelas sederhana berikut mengubah aliran data 3-bit menjadi array byte.


  • Untuk alasan keterbacaan, kode ini ditulis dalam JS, tetapi metode yang sama digeneralisasikan ke bahasa lain.
  • Pesanan bekas dari byte rendah ke tinggi ( 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(''); } };

Mari mengunduh dan menyandikan file 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()));

Seperti yang diharapkan, atlas cocok dengan 68 byte , yang 6 kali lebih kecil dari file PNG.


( catatan per .: penulis agak tidak jujur: ia tidak menyimpan palet dan ukuran gambar, yang, menurut perkiraan saya, akan membutuhkan 23 byte dengan ukuran palet tetap dan meningkatkan ukuran gambar menjadi 91 byte )


Sekarang mari kita konversi gambar ke string sehingga Anda dapat menempelkannya ke kode sumber. Intinya, metode to_string ini: ia merepresentasikan konten setiap byte sebagai angka heksadesimal.


 305000000c0328d6d4b24cb46d516d4ddab669926a0ddab651db76150060009c0285 e6a0752db59054655bd7b569d26a4ddba053892a003060400d232850b40a6b61ad00

Tetapi string yang dihasilkan masih cukup panjang, karena kami membatasi diri pada alfabet 16 karakter. Anda dapat menggantinya dengan base64 , yang karakternya empat kali lebih banyak.


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

Di base64, atlasnya terlihat seperti ini:


 MFAAAAwDKNbUsky0bVFtTdq2aZJqDdq2Udt2FQBgAJwCheagdS21kFRlW9e1adJqTdugU4kqADBgQA0jKFC0CmthrQA=

Baris ini dapat dikodekan ke modul JS dan digunakan untuk meraster teks.


Rasterisasi


Untuk menghemat memori, hanya satu huruf yang akan diterjemahkan secara bersamaan.


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

Fungsi decode mengambil karakter sebagai input dan mengembalikan kolom yang sesuai di gambar sumber. Yang mengesankan di sini adalah bahwa hanya dibutuhkan 5 byte memori untuk mendekodekan satu karakter, ditambah ~ 1.875 byte untuk membaca bagian array yang diinginkan, mis. rata-rata 6,875 per surat. Jika Anda menambahkan 68 byte untuk menyimpan array dan 36 byte untuk menyimpan alfabet, ternyata secara teoritis Anda dapat merender teks dengan 128 byte RAM.


  • Ini dimungkinkan jika Anda menulis ulang kode dalam C atau assembler. Terhadap latar belakang overhead JS, ini adalah penghematan pada pertandingan.

Tinggal mengumpulkan kolom-kolom ini menjadi satu kesatuan dan mengembalikan gambar dengan teks.


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

Ini akan menjadi font sekecil mungkin.


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

Tambahkan sedikit imagemagick untuk mendapatkan gambar dalam format yang dapat dibaca:


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

Dan inilah hasil akhirnya:



Ini juga meningkat 12 kali:



Tembakan dari makro monitor yang tidak dikalibrasi:



Dan akhirnya, lebih baik di monitor:


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

More articles:


All Articles