المهمة: استخدام أصغر مقدار ممكن من الموارد ، وتقديم نص ذي معنى.

• ما مدى صغر حجم الخط القابل للقراءة؟
• كم من الذاكرة سوف يستغرق لتخزينه؟
• كم رمز سوف يستغرق لاستخدامه؟

دعونا نرى ما نحصل عليه. المفسد:

مقدمة في الصور النقطية

أجهزة الكمبيوتر تقديم الصور النقطية مثل الصور النقطية. لا يتعلق الأمر بتنسيق .bmp ، بل يتعلق بتخزين البكسل في الذاكرة. لفهم ما يحدث ، نحتاج إلى تعلم شيء ما بهذه الطريقة.

مجموعة

تحتوي الصورة عادة على عدة طبقات فوق بعضها البعض. في معظم الأحيان تتوافق مع إحداثيات مساحة اللون RGB . طبقة واحدة للأحمر ، واحدة للأخضر وواحدة للأزرق . إذا كان تنسيق الصورة يدعم الشفافية ، يتم إنشاء طبقة رابعة لها ، تسمى عادةً ألفا . بشكل تقريبي ، تكون الصورة الملونة ثلاثة (أو أربعة ، إذا كانت هناك قناة ألفا) بالأبيض والأسود ، وتقع واحدة فوق الأخرى.

• RGB ليست مساحة اللون الوحيدة ؛ يستخدم تنسيق JPEG ، على سبيل المثال ، YUV . لكن في هذه المقالة ، لن نحتاج إلى بقية مساحات الألوان ، لذلك نحن لا نعتبرها.

يمكن تمثيل مجموعة من الطبقات في الذاكرة بطريقتين. إما يتم تخزينها بشكل منفصل ، أو يتم تشذير القيم من طبقات مختلفة. في الحالة الأخيرة ، تسمى الطبقات القنوات ، وهذه هي الطريقة التي تعمل بها التنسيقات الحديثة.

افترض أن لدينا رسم 4x4 يحتوي على ثلاث طبقات: R للأحمر ، G للأخضر و B للمكون الأزرق لكل من البيكسلات. يمكن تمثيله مثل هذا:

  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 . في بعض الأحيان يمكن استخدام ترتيب مختلف (على سبيل المثال ، BGR ) ، ولكن هذا الترتيب هو الأكثر شيوعًا.

من أجل البساطة ، رتبت البيكسل في شكل مصفوفة ثنائية الأبعاد ، لأنه أكثر وضوحًا حيث يوجد هذا أو ذاك الثلاثي في ​​الصورة. ولكن في الواقع ، فإن ذاكرة الكمبيوتر ليست ثنائية الأبعاد ، ولكن أحادية البعد ، لذلك سيتم تخزين صورة 4x4 بالشكل التالي:

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

BPP

يشير الاختصار bpp إلى عدد البتات أو البايتات لكل بكسل (البتات / البايتات لكل بكسل). ربما تكون قد شاهدت 24bpp أو 3bpp . تعني هاتان الخاصيتان نفس الشيء - 24 بت لكل بكسل أو 3 بايت لكل بكسل . نظرًا لوجود 8 بت دائمًا في البايت ، فيمكنك تخمين قيمة الوحدات المعنية.

تمثيل الذاكرة

24bpp ، ويعرف أيضًا باسم 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 

• بايت واحد لـ R وواحد لـ G وواحد لـ B ، بإجمالي ثلاث بايت.
• يحتوي كل منهم على قيمة من 0 إلى 255.

لذا إذا كانت البيكسل المعطى له اللون التالي:

• R 255
• G 80
• B 100

ثم 255 تخزين 255 في البايت الأول ، و 80 في الثانية ، و 100 في الثالثة.

في معظم الأحيان ، يتم تمثيل هذه القيم بالسداسي عشري . قل #ff5064 . هذا أكثر ملاءمةً وصغرًا: R = 0xff (على سبيل المثال ، R=255 في B=0x64 العشرية) ، G = 0x50 (= G=80 ) ، B=0x64 (= B=100 ).

• التمثيل الست عشري له خاصية مفيدة واحدة. نظرًا لأن كل بايت من الألوان يتم تمثيله بحرفين ، فإن كل حرف يقوم بترميز نصف بايت أو أربعة بتات تمامًا. 4 بت ، بالمناسبة ، تسمى nibble .

عرض الخط

عندما تنتقل وحدات البكسل واحدة تلو الأخرى وتحتوي كل منها على أكثر من قناة واحدة ، فإن البيانات يمكن الخلط بينها بسهولة. من غير المعروف متى ينتهي أحد الأسطر ويبدأ السطر التالي ، وبالتالي ، فيجب عليك معرفة حجم الصورة و bpp . في حالتنا ، يكون للصورة عرض w = 4 بكسل ويحتوي كل بكسل على 3 بايت ، لذلك يتم تشفير السلسلة بـ 12 بايت (في الحالة العامة w*bpp ).

• لا يتم تشفير السلسلة دائمًا بالبايت w*bpp بالضبط ؛ في كثير من الأحيان ، تضاف إليها وحدات البكسل "المخفية" لجعل عرض الصورة بحجم معين. على سبيل المثال ، يكون تحجيم الصور أسرع وأكثر ملاءمة عندما يكون حجمها بالبكسل مساوياً لقدرة اثنين. لذلك ، قد يحتوي الملف (يمكن للمستخدم الوصول إليه) على صورة بحجم 120 × 120 بكسل ، ولكن يتم تخزينها كصورة 128 × 128. عندما يتم عرض صورة على الشاشة ، يتم تجاهل هذه البكسلات. ومع ذلك ، نحن لسنا بحاجة لمعرفة عنها.

إحداثي أي بكسل (x, y) في التمثيل أحادي البعد هو (y * w + x) * bpp . هذا ، بشكل عام ، واضح: y هو رقم السطر ، ويحتوي كل سطر على w بكسل ، لذلك y * w هي بداية السطر المطلوب ، و +x يأخذنا إلى x المطلوب داخلها. ونظرًا لأن الإحداثيات ليست بالبايتات ، ولكن بالبكسل ، يتم ضرب كل هذا بحجم البايت بكسل ، في هذه الحالة بالبايت. نظرًا لأن حجم البيكسل غير صفري ، يجب عليك قراءة البايتات bpp بالضبط ، بدءًا من الإحداثيات المستلمة ، وسيكون لدينا تمثيل كامل للبكسل المطلوب.

أطلس الخط

في الواقع لا تعرض الشاشات الحالية بكسل ككل ، ولكن ثلاثة وحدات بكسل فرعية - الأحمر والأزرق والأخضر. إذا نظرت إلى الشاشة تحت التكبير ، فسترى شيء مثل هذا:

• رسم ويكيبيديا

نحن مهتمون بشاشات الكريستال السائل ، نظرًا لأنه من المحتمل أن تكون من هذا الشاشة تقرأ هذا النص. بالطبع ، هناك مطبات:

• لا تستخدم جميع المصفوفات بالضبط ترتيب البكسلات الفرعية ، وأحيانًا BGR.
• إذا قمت بتشغيل الشاشة (على سبيل المثال ، أنظر إلى الهاتف في اتجاه أفقي) ، فسيتم تدوير النموذج أيضًا وسيوقف الخط عن العمل.
• ستتطلب اتجاهات المصفوفة المختلفة وترتيب البكسلات الفرعية إعادة صياغة الخط نفسه.
• على وجه الخصوص ، لا يعمل على شاشات AMOLED التي تستخدم تخطيط PenTile . تستخدم شاشات العرض هذه غالبًا في الأجهزة المحمولة.

يسمى استخدام اختراقات البكسل الفرعي لزيادة الدقة تقديم التقسيم الفرعي . يمكنك أن تقرأ عن استخدامه في الطباعة ، على سبيل المثال ، هنا .

لحسن الحظ بالنسبة لنا ، اكتشف Matt Sarnov بالفعل استخدام عرض البكسل الفرعي لإنشاء خط صغير جدًا . يدويا ، ابتكر هذه الصورة الصغيرة:

والتي ، إذا نظرت بعناية فائقة إلى الشاشة ، تبدو كما يلي:

وهنا يتم زيادتها برمجياً بنسبة 12 مرة:

بناءً على عمله ، قمتُ بإنشاء أطلس للخطوط يقابل فيه كل حرف عمودًا 1x5 × 1x5 بكسل. ترتيب الأحرف كالتالي:

 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ 

زاد الأطلس نفسه 12 مرة:

باستخدام 36 حرفًا ، يتم 365 36 × 365 بكسل بالضبط. إذا افترضنا أن كل بكسل يشغل 3 بايت ، فسنحتاج إلى 36*5*3 = 540 بايت لتخزين الصورة بأكملها (approx.per .: في الأصل ، سلسلة مربكة من التعديلات حول قناة ألفا ، وحذف البيانات الوصفية ، وما إلى ذلك). n. في الترجمة ، لقد حذفتها واستخدمت النسخة النهائية فقط من الملف ). يأخذ ملف PNG الذي تم تمريره عبر pngcrush و optipng وقتًا أقل:

 # wc -c < font-crushed.png 390 

ولكن يمكنك تحقيق حجم أصغر إذا كنت تستخدم طريقة مختلفة قليلاً

ضغط

قد يلاحظ القارئ اليقظ أن الأطلس يستخدم فقط 7 ألوان:

1. #ffffff
2. #ff0000
3. #00ff00
4. #0000ff
5. #00ffff
6. #ff00ff
7. #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 - - - - - - - 

الأهم من ذلك ، بكسل لا يترك مجرد مجموعة من مساحة فارغة. ممزقة بين وحدتي بايت. عندما نبدأ في إضافة وحدات البكسل التالية ، يمكن وضعها بشكل تعسفي بالنسبة إلى حدود البايت. سيكون الحل الأبسط هو استخدام nibble لكل بكسل ، لأن 8 مقسومة تمامًا على 4 وتتيح لك وضع بكسلين بالضبط في كل بايت. لكن هذا سيزيد من حجم الأطلس بمقدار الثلث ، من 68 بايت إلى 90 بايت .

• في الواقع ، يمكن جعل الملف أصغر باستخدام ترميز palindrome ، وترميز الفاصل ، وتقنيات الضغط الأخرى. مثل الترميز الحسابي ، نحن نؤجل هذه التقنيات حتى المادة التالية.

عازلة قليلا

لحسن الحظ ، لا يوجد شيء مستحيل بشكل أساسي في العمل مع قيم 3 بت. تحتاج فقط إلى مراقبة الموقف داخل البايت الذي نكتبه أو نقرأه في الوقت الحالي. يحول الفصل البسيط التالي دفق بيانات 3 بت إلى صفيف وحدات البايت.

• لأسباب قابلية القراءة ، يتم كتابة التعليمات البرمجية في JS ، ولكن نفس الأسلوب معمم إلى لغات أخرى.
• طلب مستعملة من البايت المنخفض إلى الأعلى ( 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(''); } }; 

لنقم بتنزيل وترميز ملف الأطلس:

 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 مرات من ملف PNG.

( ملاحظة لكل شخص: المؤلف غير واضح إلى حد ما: لم يحفظ لوحة الألوان وحجم الصورة ، والتي حسب تقديري ، ستتطلب 23 بايت بحجم لوحة ثابت ويزيد حجم الصورة إلى 91 بايت )

الآن ، دعونا نحول الصورة إلى سلسلة بحيث يمكنك لصقها في الكود المصدري. في جوهرها ، تقوم طريقة to_string بهذا: فهي تمثل محتويات كل بايت كرقم ست عشري.

 305000000c0328d6d4b24cb46d516d4ddab669926a0ddab651db76150060009c0285 e6a0752db59054655bd7b569d26a4ddba053892a003060400d232850b40a6b61ad00 

لكن السلسلة الناتجة لا تزال طويلة للغاية ، لأننا قصرنا على الأبجدية المكونة من 16 حرفًا. يمكنك استبداله بـ base64 ، حيث يوجد أربعة أضعاف عدد الأحرف.

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

في base64 ، يبدو الأطلس كما يلي:

 MFAAAAwDKNbUsky0bVFtTdq2aZJqDdq2Udt2FQBgAJwCheagdS21kFRlW9e1adJqTdugU4kqADBgQA0jKFC0CmthrQA= 

يمكن تشفير هذا الخط في وحدة JS واستخدامه في تنقيط النص.

التنقيط

لحفظ الذاكرة ، سيتم فك شفرة حرف واحد فقط في كل مرة.

 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 لكل حرف. إذا قمت بإضافة 68 بايت لتخزين المصفوفة و 36 بايت لتخزين الأبجدية ، اتضح أنه من الناحية النظرية يمكنك تقديم نص مع 128 بايت من ذاكرة الوصول العشوائي.

• هذا ممكن إذا قمت بإعادة كتابة الكود في C أو المجمع. على خلفية النفقات العامة JS ، وهذا هو توفير في المباريات.

يبقى فقط لجمع هذه الأعمدة في كل واحد وإرجاع صورة مع النص.

 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 مرة:

تم تصويره من ماكرو شاشة سيئة المعايرة:

وأخيراً ، من الأفضل على الشاشة: