कार्य: संसाधनों की सबसे छोटी संभव राशि का उपयोग करते हुए, सार्थक पाठ प्रस्तुत करना।

एक पठनीय फ़ॉन्ट कितना छोटा हो सकता है?
इसे स्टोर करने में कितनी मेमोरी लगेगी?
इसका उपयोग करने के लिए कितना कोड लगेगा?

देखते हैं कि हमें क्या मिलता है। स्पॉइलर:

बिटमैप्स का परिचय

कंप्यूटर बिटमैप के रूप में बिटमैप प्रस्तुत करते हैं। यह .bmp प्रारूप के बारे में नहीं है, लेकिन मेमोरी में पिक्सेल को स्टोर करने के तरीके के बारे में है। यह समझने के लिए कि क्या हो रहा है, हमें इस तरह से कुछ सीखने की जरूरत है।

समूहों

एक छवि में आमतौर पर एक दूसरे के ऊपर कई परतें होती हैं । ज्यादातर वे आरजीबी रंग अंतरिक्ष के निर्देशांक के अनुरूप होते हैं । एक परत लाल के लिए , एक हरी के लिए और एक नीली के लिए । यदि छवि प्रारूप पारदर्शिता का समर्थन करता है, तो इसके लिए एक चौथी परत बनाई जाती है, जिसे आमतौर पर अल्फा कहा जाता है। मोटे तौर पर, एक रंग की छवि तीन (या चार, अगर एक अल्फा चैनल है) काले और सफेद, एक के ऊपर एक स्थित है।

RGB केवल रंग स्थान नहीं है; उदाहरण के लिए, JPEG प्रारूप, YUV का उपयोग करता है। लेकिन इस लेख में हमें बाकी रंग स्थानों की आवश्यकता नहीं होगी, इसलिए हम उन पर विचार नहीं करते हैं।

परतों का एक सेट मेमोरी में दो तरीकों से दर्शाया जा सकता है। या तो उन्हें अलग से संग्रहीत किया जाता है, या अलग-अलग परतों से मानों को इंटरलेय किया जाता है। बाद के मामले में, परतों को चैनल कहा जाता है , और यह है कि सबसे आधुनिक प्रारूप कैसे काम करते हैं।

मान लें कि हमारे पास एक 4x4 ड्राइंग है जिसमें तीन परतें हैं: आर लाल के लिए, जी हरे रंग के लिए और बी प्रत्येक पिक्सेल के नीले घटक के लिए। इसे इस तरह दर्शाया जा सकता है:

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

तीनों परतों को अलग-अलग संग्रहीत किया जाता है। वैकल्पिक स्वरूप अलग दिखता है:

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

पात्रों के प्रत्येक ट्रिपल बिल्कुल एक पिक्सेल से मेल खाती है
ट्रिपल के भीतर के मान RGB क्रम में हैं। कभी-कभी एक अलग आदेश का उपयोग किया जा सकता है (उदाहरण के लिए, बीजीआर ), लेकिन यह सबसे आम है।

सादगी के लिए, मैंने पिक्सल को दो-आयामी मैट्रिक्स के रूप में व्यवस्थित किया, क्योंकि यह अधिक स्पष्ट है कि यह या वह ट्रिपल छवि में कहां है। लेकिन वास्तव में, कंप्यूटर मेमोरी दो-आयामी नहीं है, लेकिन एक-आयामी है, इसलिए 4x4 चित्र इस तरह संग्रहीत किया जाएगा:

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

bpp

संक्षिप्त नाम bpp बिट्स या बाइट्स प्रति पिक्सेल (बिट्स / बाइट्स प्रति पिक्सेल) की संख्या को संदर्भित करता है। आपने 3bpp 24bpp या 3 3bpp देखा 3bpp । इन दोनों विशेषताओं का एक ही मतलब है - 24 बिट प्रति पिक्सेल या 3 बाइट प्रति पिक्सेल । चूंकि एक बाइट में हमेशा 8 बिट्स होते हैं, इसलिए आप प्रश्न में इकाइयों में से किस के मूल्य से अनुमान लगा सकते हैं।

मेमोरी का प्रतिनिधित्व

24bpp , उर्फ 3 3bpp - फूलों के भंडारण के लिए सबसे आम प्रारूप। यह है कि RGB ऑर्डर में एक एकल पिक्सेल व्यक्तिगत बिट्स के स्तर पर कैसे दिखता है।

  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

आर के लिए एक बाइट, जी के लिए एक और बी के लिए एक, कुल तीन बाइट्स।
उनमें से प्रत्येक में 0 से 255 तक का मान है।

इसलिए यदि दिए गए पिक्सेल में निम्नलिखित रंग है:

R 255
G 80
B 100

फिर 255 पहले बाइट में संग्रहीत किए 255 , दूसरे में 80 और तीसरे में 100 ।

सबसे अधिक बार, इन मूल्यों को हेक्साडेसिमल में दर्शाया गया है। कहो #ff5064 यह बहुत अधिक सुविधाजनक और कॉम्पैक्ट है: R = 0xff (यानी दशमलव में R=255 ), G = 0x50 (= G=80 ), B=0x64 (= B=100 )।

हेक्साडेसिमल प्रतिनिधित्व में एक उपयोगी संपत्ति है। चूंकि रंग के प्रत्येक बाइट को दो वर्णों द्वारा दर्शाया जाता है, इसलिए प्रत्येक वर्ण ठीक आधा बाइट या चार बिट्स को एन्कोड करता है । 4 बिट्स, वैसे, निबल कहा जाता है।

लाइन की चौड़ाई

जब पिक्सेल एक के बाद एक जाते हैं और प्रत्येक में एक से अधिक चैनल होते हैं, तो डेटा आसानी से भ्रमित होता है। यह ज्ञात नहीं है कि एक पंक्ति कब समाप्त होती है और अगली शुरू होती है, इसलिए, बिटमैप के साथ एक फ़ाइल की व्याख्या करने के लिए, आपको छवि का आकार और bpp जानने की आवश्यकता है। हमारे मामले में, चित्र में w = 4 पिक्सेल की चौड़ाई है और इनमें से प्रत्येक पिक्सेल में 3 बाइट्स हैं, इसलिए स्ट्रिंग 12 के साथ एन्कोडेड है (सामान्य स्थिति w*bpp ) बाइट्स में।

एक स्ट्रिंग हमेशा w*bpp बाइट्स के साथ एन्कोड नहीं किया जाता है; छवि की चौड़ाई को कुछ आकार में लाने के लिए अक्सर, "छिपे हुए" पिक्सल को इसमें जोड़ा जाता है। उदाहरण के लिए, चित्रों को स्केल करना तब और अधिक सुविधाजनक होता है जब पिक्सेल में उनका आकार दो की शक्ति के बराबर होता है। इसलिए, फ़ाइल में 120x120 पिक्सेल की छवि (उपयोगकर्ता के लिए सुलभ) हो सकती है, लेकिन 128x128 की छवि के रूप में संग्रहीत की जा सकती है। जब कोई चित्र स्क्रीन पर प्रदर्शित होता है, तो इन पिक्सेल को अनदेखा कर दिया जाता है। हालांकि, हमें उनके बारे में जानने की जरूरत नहीं है।

एक आयामी प्रतिनिधित्व में किसी भी पिक्सेल (x, y) का समन्वय है (y * w + x) * bpp । यह, सामान्य रूप से, स्पष्ट है: y लाइन नंबर है, प्रत्येक पंक्ति में w पिक्सेल हैं, इसलिए y * w वांछित लाइन की शुरुआत है, और +x हमें इसके भीतर वांछित x जाता है। और चूंकि निर्देशांक बाइट्स में नहीं हैं, लेकिन पिक्सेल में, यह सब बाइट पिक्सेल के आकार से गुणा किया जाता है, इस मामले में बाइट्स में। चूंकि पिक्सेल में एक गैर-आकार का आकार होता है, आपको प्राप्त निर्देशांक से शुरू करते हुए, वास्तव में bpp बाइट्स पढ़ने की आवश्यकता होती है, और हमारे पास वांछित पिक्सेल का पूरा प्रतिनिधित्व होगा।

फ़ॉन्ट एटलस

वास्तव में मौजूदा मॉनिटर एक पिक्सेल को पूरे के रूप में प्रदर्शित नहीं करते हैं, लेकिन तीन उपप्रिक्सल - लाल, नीला और हरा। यदि आप मॉनिटर को आवर्धन के आधार पर देखते हैं, तो आपको कुछ इस तरह दिखाई देगा:

विकिपीडिया ड्राइंग

हम एलसीडी में रुचि रखते हैं, क्योंकि इस तरह के मॉनिटर से सबसे अधिक संभावना है कि आप इस पाठ को पढ़ते हैं। बेशक, नुकसान हैं:

सभी मैट्रिसेस सबपिक्सल के इस क्रम का उपयोग नहीं करते हैं, कभी-कभी बीजीआर।
यदि आप मॉनिटर को बदलते हैं (उदाहरण के लिए, लैंडस्केप ओरिएंटेशन में फोन को देखें), तो पैटर्न भी घूम जाएगा और फ़ॉन्ट काम करना बंद कर देगा।
विभिन्न मैट्रिक्स ओरिएंटेशन और सबपिक्सल की व्यवस्था को स्वयं फॉन्ट को रिवाइज करने की आवश्यकता होगी।
विशेष रूप से, यह AMOLED डिस्प्ले पर काम नहीं करता है जो पेनटाइल लेआउट का उपयोग करते हैं। इस तरह के डिस्प्ले मोबाइल डिवाइस में सबसे अधिक उपयोग किए जाते हैं।

रिज़ॉल्यूशन बढ़ाने के लिए सबपिक्सल हैक्स का उपयोग करना सबपिक्सल रेंडरिंग कहलाता है । आप टाइपोग्राफी में इसके उपयोग के बारे में पढ़ सकते हैं, उदाहरण के लिए, यहाँ ।

सौभाग्य से हमारे लिए, मैट सरनोव ने पहले ही एक छोटे मिलिटेक्स फ़ॉन्ट बनाने के लिए सबपिक्सल रेंडरिंग का उपयोग करके पता लगा लिया। मैन्युअल रूप से, उन्होंने यह छोटी तस्वीर बनाई:

जो, यदि आप मॉनिटर को बहुत ध्यान से देखते हैं, तो ऐसा दिखता है:

और यहाँ यह, प्रोग्रामेटिक रूप से 12 गुना बढ़ा है:

उनके काम के आधार पर, मैंने एक फॉन्ट एटलस बनाया, जिसमें प्रत्येक वर्ण 1x5 पिक्सेल के कॉलम से मेल खाता है। वर्ण क्रम इस प्रकार है:

 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

वही एटलस 12 गुना बढ़ गया:

उपयोग किए गए 36 वर्णों के साथ, वास्तव में 365 पिक्सेल 365 होते हैं। यदि हम मानते हैं कि प्रत्येक पिक्सेल 3 बाइट्स पर कब्जा कर लेता है, तो हमें पूरी तस्वीर (लगभग) को स्टोर करने के लिए 36*5*3 = 540 बाइट्स की आवश्यकता होती है । मूल में, अल्फा चैनल के बारे में संपादन की एक भ्रामक श्रृंखला, मेटाडेटा को हटाने, आदि)। n। अनुवाद में, मैंने इसे छोड़ दिया और केवल फ़ाइल के अंतिम संस्करण का उपयोग किया )। PNG फाइल पींगक्रश और ऑप्टिपंग से होकर गुजरती है और भी कम लगती है:

 # wc -c < font-crushed.png 390

लेकिन अगर आप थोड़ा अलग दृष्टिकोण अपनाते हैं तो आप और भी छोटे आकार हासिल कर सकते हैं

दबाव

चौकस पाठक देख सकता है कि एटलस केवल 7 रंगों का उपयोग करता है:

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

पैलेट

ऐसी स्थितियों में, पैलेट बनाना अक्सर आसान होता है। फिर प्रत्येक पिक्सेल के लिए आप तीन बाइट्स रंग नहीं जमा कर सकते हैं, लेकिन केवल पैलेट में रंग संख्या। हमारे मामले में, 3 बिट्स ( 7 < 2^3 ) 7 रंगों में से चुनने के लिए पर्याप्त होंगे। यदि हम प्रत्येक पिक्सेल को तीन-बिट मान असाइन करते हैं, तो संपूर्ण एटलस 68 बाइट्स में फिट होगा।

पाठक, डेटा संपीड़न में निपुण, उत्तर दे सकता है कि सामान्य तौर पर "अंश बिट्स" जैसी कोई चीज है और हमारे मामले में प्रति पिक्सेल 2.875 बिट्स पर्याप्त हैं। यह घनत्व काला जादू का उपयोग करके प्राप्त किया जा सकता है, जिसे अंकगणित कोडिंग के रूप में जाना जाता है। हम ऐसा नहीं करेंगे, क्योंकि अंकगणित कोडिंग एक जटिल बात है, और 68 बाइट्स पहले से ही एक सा है।

संरेखण

तीन-बिट कोडिंग में एक गंभीर खामी है। पिक्सेल समान रूप से 8-बिट बाइट्स में वितरित नहीं किए जा सकते हैं, जो महत्वपूर्ण है क्योंकि बाइट्स सबसे छोटे पते योग्य मेमोरी क्षेत्र हैं। मान लीजिए कि हम तीन पिक्सेल बचाना चाहते हैं:

ABC

यदि प्रत्येक 3 बिट्स लेता है, तो उन्हें स्टोर करने के लिए 2 बाइट्स लगेंगे ( - अप्रयुक्त बिट्स को इंगित करता है):

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

महत्वपूर्ण रूप से, पिक्सेल सी खाली जगह का एक गुच्छा नहीं छोड़ता है; यह दो बाइट्स के बीच फटा हुआ है। जब हम निम्नलिखित पिक्सेल जोड़ना शुरू करते हैं, तो उन्हें बाइट सीमाओं के सापेक्ष मनमाने ढंग से तैनात किया जा सकता है। सबसे सरल समाधान प्रति पिक्सेल निबल का उपयोग करना होगा, क्योंकि 8 को 4 से पूरी तरह से विभाजित किया गया है और आपको प्रत्येक बाइट में बिल्कुल दो पिक्सेल रखने की अनुमति देता है। लेकिन इससे एटलस का आकार एक तिहाई बढ़ जाएगा, 68 बाइट्स से 90 बाइट्स तक ।

वास्तव में, फाइल को palindrome कोडिंग, अंतराल कोडिंग और अन्य संपीड़न तकनीकों का उपयोग करके और भी छोटा किया जा सकता है। अंकगणित कोडिंग की तरह, हम अगले लेख तक इन तकनीकों को स्थगित कर देते हैं।

बिट बफर

सौभाग्य से, 3-बिट मूल्यों के साथ काम करने में मौलिक रूप से असंभव कुछ भी नहीं है। आपको बस इस बात की निगरानी करने की आवश्यकता है कि बाइट के अंदर हम किस स्थिति में लिख रहे हैं या पढ़ रहे हैं। निम्न साधारण वर्ग 3-बिट डेटा स्ट्रीम बाइट्स के एक सरणी में कनवर्ट करता है।

पठनीयता कारणों के लिए, कोड को JS में लिखा गया है, लेकिन अन्य भाषाओं के लिए समान विधि सामान्यीकृत है।
कम बाइट से उच्च ( लिटिल एंडियन ) के लिए प्रयुक्त आदेश

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

आइए एटलस फ़ाइल को डाउनलोड और एनकोड करें:

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

जैसा कि अपेक्षित था, एटलस 68 बाइट्स फिट बैठता है, जो पीएनजी फ़ाइल से 6 गुना छोटा है।

( ध्यान दें: लेखक कुछ हद तक असभ्य है: उसने पैलेट और छवि आकार को नहीं बचाया, जो मेरे अनुमानों के अनुसार, एक निश्चित पैलेट आकार के साथ 23 बाइट्स की आवश्यकता होगी और छवि का आकार 91 बाइट्स तक बढ़ा देगा )

अब इमेज को स्ट्रिंग में बदलते हैं ताकि आप इसे सोर्स कोड में पेस्ट कर सकें। संक्षेप में, to_string विधि to_string : यह एक हेक्साडेसिमल संख्या के रूप में प्रत्येक बाइट की सामग्री का प्रतिनिधित्व to_string ।

 305000000c0328d6d4b24cb46d516d4ddab669926a0ddab651db76150060009c0285 e6a0752db59054655bd7b569d26a4ddba053892a003060400d232850b40a6b61ad00

लेकिन परिणामी स्ट्रिंग अभी भी काफी लंबी है, क्योंकि हमने खुद को 16 वर्णों की वर्णमाला तक सीमित कर लिया है। आप इसे बेस 64 से बदल सकते हैं, जिसमें कई पात्रों के चार गुना हैं।

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

Base64 में, एटलस इस तरह दिखता है:

 MFAAAAwDKNbUsky0bVFtTdq2aZJqDdq2Udt2FQBgAJwCheagdS21kFRlW9e1adJqTdugU4kqADBgQA0jKFC0CmthrQA=

इस लाइन को जेएस मॉड्यूल में हार्डकोड किया जा सकता है और इसका उपयोग टेक्स्ट को तेज करने के लिए किया जा सकता है।

रैस्टराइज़ेशन

स्मृति को बचाने के लिए, एक बार में केवल एक अक्षर को डिकोड किया जाएगा।

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

decode फ़ंक्शन एक चरित्र को इनपुट के रूप में लेता है और स्रोत छवि में संबंधित कॉलम लौटाता है। यहां जो प्रभावशाली है वह यह है कि एकल वर्ण को डिकोड करने के लिए केवल 5 बाइट्स लगते हैं, साथ ही सरणी के वांछित टुकड़े को पढ़ने के लिए ~ 1.875 बाइट्स, अर्थात्। प्रति अक्षर औसत 6.875 । यदि आप वर्णमाला को संग्रहीत करने के लिए सरणी और 36 बाइट्स को संग्रहीत करने के लिए 68 बाइट्स जोड़ते हैं, तो यह पता चलता है कि सैद्धांतिक रूप से आप 128 बाइट्स रैम के साथ पाठ को प्रस्तुत कर सकते हैं।

यह संभव है यदि आप सी या कोडांतरक में कोड को फिर से लिखते हैं। जेएस ओवरहेड की पृष्ठभूमि के खिलाफ, यह मैचों पर बचत है।

यह केवल इन स्तंभों को एक एकल में इकट्ठा करने और पाठ के साथ एक तस्वीर वापस करने के लिए बनी हुई है।

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

यह सबसे छोटा संभव फ़ॉन्ट होगा।

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

एक पठनीय प्रारूप में छवि प्राप्त करने के लिए थोड़ा सा इमेजमैजिक जोड़ें:

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

और यहाँ अंतिम परिणाम है:

यह भी 12 गुना बढ़ा है:

यह खराब कैलिब्रेटेड मॉनिटर मैक्रो से शूट किया गया है:

और अंत में, यह मॉनिटर पर बेहतर है:

सबसे छोटा संभव फ़ॉन्ट