عكس السرطان العصبي. الجزء الرابع: الصوت ، الرسوم المتحركة ، هوفمان ، جيثب

مرحبًا ، كما فهمت بالفعل ، هذا استمرار لتاريخي في الهندسة العكسية ونقل Neuromant.

عكس السرطان العصبي. الجزء 1: العفاريت
عكس السرطان العصبي. الجزء 2: خط التقديم
عكس السرطان العصبي. الجزء 3: الانتهاء من العرض ، جعل اللعبة

اليوم ، دعنا نبدأ بخبرين جيدين:

• أولاً ، أنا لست وحيدًا بعد الآن - انضم المستخدم viiri بالفعل إلى المشروع وقدم بالفعل مساهمة كبيرة ؛
• ثانيًا ، لدينا الآن مستودع مفتوح على جيثب .

بشكل عام ، تسير الأمور بشكل جيد للغاية ، وربما سنحصل قريبًا على بعض البناء القابل للتشغيل على الأقل. وتحت الخفض ، كالعادة ، لنتحدث عما وكيف تم تحقيقه في الوقت الحالي.

بدأ التعامل مع الصوت. للأسف ، من بين موارد اللعبة ، لم يكن هناك شيء مشابه للصوت ، وبما أنني لم أكن أعلم كيف تعمل الموسيقى في MS-DOS ، لم يكن من الواضح للغاية من أين أبدأ. بعد قراءة القليل عن جميع أنواع SoundBlaster s ، فإن أفضل ما توصلت إليه هو تمرير الرمز المفكك على أمل رؤية بعض التوقيعات المألوفة. ومن يسعى ، عادة ما يجد ، حتى لو لم يكن بالضبط ما كان يبحث عنه (التعليقات التي كتبها إيدا ):

sub_20416: ... mov ax, [si+8] out 42h, al ; 8253-5 (AT: 8254.2). mov al, ah out 42h, al ; Timer 8253-5 (AT: 8254.2). mov bx, [si+0Ah] and bl, 3 in al, 61h ; PC/XT PPI port B bits: ; 0: Tmr 2 gate ═╦═► OR 03H=spkr ON ; 1: Tmr 2 data ═╝ AND 0fcH=spkr OFF ; 3: 1=read high switches ; 4: 0=enable RAM parity checking ; 5: 0=enable I/O channel check ; 6: 0=hold keyboard clock low ; 7: 0=enable kbrd and al, 0FCh or al, bl out 61h, al ; PC/XT PPI port B bits: ; 0: Tmr 2 gate ═╦═► OR 03H=spkr ON ; 1: Tmr 2 data ═╝ AND 0fcH=spkr OFF ; 3: 1=read high switches ; 4: 0=enable RAM parity checking ; 5: 0=enable I/O channel check ; 6: 0=hold keyboard clock low ; 7: 0=enable kbrd 

بعد أن مررت بهذا المؤقت 8253-5 ، صادفت مقالة أصبحت المفتاح الأول لفهم ما كان يحدث. أدناه سأحاول شرح ما هو.

لذا ، في عصر IBM-PC ، قبل ظهور بطاقات الصوت الميسورة التكلفة ، كان الجهاز الأكثر شيوعًا لإعادة إنتاج الصوت هو ما يسمى مكبر صوت الكمبيوتر ، والمعروف أيضًا باسم "beeper". هذا الجهاز ليس أكثر من مكبر صوت عادي متصل باللوحة الأم ، في معظم الحالات ، من خلال موصل رباعي. وفقا للفكرة ، سمحت الصافرة بإعادة إنتاج نبضة مستطيلة ذات مستويين (تتوافق مع مستويين للجهد ، عادة ما يكونان 0V و + 5V) وتم التحكم فيها من خلال المنفذ 61 من وحدة تحكم PPI (واجهة الطرفية القابلة للبرمجة) . على وجه التحديد ، تكون البتتان الأوليان من القيمة المرسلة إلى المنفذ مسؤولة عن التحكم في "مكبر الصوت" (انظر التعليقات على السطور in al, 61h و out 61h, al ).

كما قلت (بكلمات مختلفة قليلاً) ، يمكن أن يكون المتحدث لدينا في حالتين - "في" و "خارج" ( "منخفض" - "مرتفع" ، "إيقاف" - "تشغيل" ، "إيقاف" - "تشغيل" ، أيا كان). لإنشاء دفعة واحدة ، من الضروري تغيير الحالة الحالية إلى عكس ذلك ، وبعد مرور بعض الوقت ، العودة. يمكن القيام بذلك مباشرة عن طريق معالجة البت الأول (العد من البداية) للمنفذ 61 ، على سبيل المثال ، كما يلي:

 PULSE: in al, 61h ;    and al, 11111100b ;    ... or al, 00000010b ;     ... ; ,        0 out 61h, al ;    61-  mov cx, 100 ;   DELAY: loop DELAY ;    in al, 61h ;    and al, 11111100b ;     out 61h, al ;    61-  

ستبدو نتيجة تنفيذ هذا الرمز كما يلي:

  loop DELAY +5V +----------------------+ ! ! 0V ---+ +-------------------------- or al, 00000010b and al, 11111100b out 61h, al out 61h, al 

بتكرار النبض مع تأخير ، نحصل على إشارة مستطيلة:

  mov dx, 100 ;  100  PULSE: ... mov cx, 100 WAIT: loop WAIT dec dx jnz PULSE PULSE +5V +---------+ +---------+ +---------+ ! ! ! ! ! ! 0V ---+ +---------+ +---------+ +--- loop WAIT 

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

هنا يأتي جهاز توقيت اللعبة القابل للبرمجة بثلاث قنوات - Intel 8253 ، القناة الثانية التي (تبدأ من الصفر) متصلة بجهاز التنبيه. يستقبل هذا المؤقت إشارة من ساعة Intel 8254 ، يرسل 1193180 نبضة في الثانية (~ 1.193 ميجا هرتز) ، ويمكن برمجته لرد فعل معين بعد عدد محدد من النبضات. أحد هذه التفاعلات هو إرسال نبضة مربعة إلى السماعة. بمعنى آخر ، يمكن أن يعمل 8253 في شكل مولد لإشارة مستطيلة بتردد قابل للتعديل ، مما يجعل من السهل نسبيًا تركيب مؤثرات صوتية مختلفة على السماعة. وإليك ما تحتاجه لهذا:

1. اضبط القناة الثانية للمؤقت على وضع توليد الإشارة المستطيلة. للقيام بذلك ، اكتب قيمة بايت واحد خاص للمنفذ 43 ( تسجيل الوضع / الأمر 8253 ). في حالتي ، هذا 10110110B (مزيد من التفاصيل هنا ):

 Bits Usage 6 and 7 Select channel : 1 0 = Channel 2 4 and 5 Access mode : 1 1 = Access mode: lobyte/hibyte 1 to 3 Operating mode : 0 1 1 = Mode 3 (square wave generator) 0 BCD/Binary mode: 0 = 16-bit binary 

1. اضبط التردد المطلوب على القناة الثانية. للقيام بذلك ، بايت بايت ، من الأصغر إلى الأقدم ، نرسل إلى المنفذ 42 ( منفذ بيانات القناة 2 8253 ) قيمة تساوي 1193180 / freq ، حيث freq هو قيمة التردد المطلوبة في Hertz.

   
   

2. السماح للسماعة بتلقي نبضات من المؤقت. للقيام بذلك ، قم بتعيين أول بتين من القيمة في المنفذ 61 ( PPI ) إلى الوحدة. والحقيقة هي أنه إذا تم تعيين بت الصفر إلى 1 ، فسيتم تفسير الأول على أنه "مفتاح تبديل":

   
   

 Bit 0 Effect ----------------------------------------------------------------- 0 The state of the speaker will follow bit 1 of port 61h 1 The speaker will be connected to PIT channel 2, bit 1 is used as switch ie 0 = not connected, 1 = connected. 

نتيجة لذلك ، لدينا الصورة التالية:

  mov al, 10110110b out 43h, al ;   mov ax, 02E9Bh ; 1193180 / 100 = ~0x2E9B out 42h, al ;      mov al, ah out 42h, al ;      in al, 61h ;    or al, 00000011b ;      1 out 61h, al ;   ... ;       ~100  in al, 61h and al, 11111100b out 61h, al ;   

وهذا بالضبط ما يفعله الكود الذي اقتبسته في البداية (باستثناء التهيئة ، لكنني وجدته في وظيفة أخرى): في si + 8 يوجد مقسم تردد مرسل إلى المنفذ 42 ، وفي si + 0Ah - تسجيل حالة مكبر الصوت ( "تشغيل" - "إيقاف" ) في المنفذ 61.

آلية التشغيل بسيطة ومباشرة ، ولكن بعد ذلك كان عليك التعامل مع التوقيتات. بعد فحص الرمز القريب ، رأيت أنه في نفس الوظيفة التي يتم فيها تهيئة المؤقت ( sub_2037A ، المشار إليه فيما يلي - init_8253 ) ، يتم استبدال معالج المقاطعة الثامن بالوظيفة sub_20416 (فيما يلي - play_sample ). سرعان ما أصبح واضحًا أن هذه المقاطعة يتم إنشاؤها تقريبًا 18.2 مرة في الثانية وتعمل على تحديث وقت النظام. يعد استبدال معالج هذه المقاطعة ممارسة شائعة إذا كنت بحاجة إلى تنفيذ بعض الإجراءات 18 مرة في الثانية (في الواقع ، يجب أيضًا استدعاء المعالج الأصلي داخل الخطاف ، وإلا سيتوقف وقت النظام). بناءً على ذلك ، اتضح أن التردد التالي يتم تحميله على المولد كل (1 / 18.2) * 1000 ~ 55 .

كانت الخطة على النحو التالي:

• ضع نقطة توقف في دالة play_sample ، على الخط حيث يتم استخراج مقسم التردد التالي ؛
• حساب التردد وفقًا للصيغة freq = 1193180 / divisor ؛
• إنشاء 55 مللي ثانية من إشارة التردد المربعة المربعة في نوع ما من محرر الصوت (استخدمت Adobe Audition ) ؛
• كرر الخطوات الثلاث الأولى حتى يتم تراكم 3 ثوان على الأقل.

لذلك حصلت على بداية اللحن من القائمة الرئيسية ، ولكن لعب بعض الوقت 10 أبطأ من اللازم. ثم قمت بتقليل مدة "العينة" من 55 مللي ثانية إلى 5 مللي ثانية - أصبحت أفضل بكثير ، ولكن لم يتم ذلك. ظلت مشكلة التوقيت مفتوحة حتى وجدت هذه المقالة . اتضح أن المقاطعة الثامنة يتم توليدها عن طريق تغذية نفس 8253 ، قناة صفر متصلة بوحدة تحكم المقاطعة ( PIC ). عند تشغيل الجهاز ، يقوم BIOS بتعيين القناة صفر لتوليد نبضات بتردد 18.2 هرتز (أي يتم إنشاء مقاطعة كل 54.9 مللي ثانية تقريبًا). ومع ذلك ، يمكن إعادة برمجة القناة الصفرية بحيث تولد نبضات بتردد أعلى ، لهذا ، بالقياس مع القناة الثانية ، تحتاج إلى كتابة قيمة تساوي 1193180 / freq إلى المنفذ 40 ، حيث freq هو قيمة التردد المطلوبة في Hertz. يحدث هذا في دالة init_8253 ، ولكن في البداية لم أكن init_8253 بها:

 init_8253: ... mov al, 0B6h ; 10110110b out 43h, al ; Timer 8253-5 (AT: 8254.2). mov ax, 13B1h out 40h, al ; Timer 8253-5 (AT: 8254.2). mov al, ah out 40h, al ; Timer 8253-5 (AT: 8254.2). 

13B1h ترجمة القيمة 13B1h إلى التردد: 1193180 / 13B1h ~ 236.7 ، ثم نحصل تقريبًا على (1 / 236.7) * 1000 ~ 4.2 لكل "عينة". لقد تطور اللغز.

ثم إنها مسألة تقنية - لتنفيذ وظيفة تستخرج الموسيقى التصويرية من اللعبة. ولكن هنا الشيء ، لا يتم تخزين قيم فواصل التردد المسجلة في المنفذ 42 بشكل صريح. يتم حسابها من خلال بعض الخوارزميات الصعبة ، وبيانات الإدخال ومنطقة العمل التي تقع مباشرة في الملف القابل للتنفيذ للعبة (في الجزء السابع ، وفقًا لـ Ida ). أيضًا ، من الميزات ، لا توجد علامة على نهاية المسار ، عندما لا يكون هناك المزيد للعب ، تنتج الخوارزمية بلا حدود حالة الصفر للمتكلم. لكنني لم أزعجني ، وكما هو الحال في خوارزمية إلغاء الضغط ( الجزء الأول ) ، قمت فقط بنقل إلى مُجمِّع 64 بت وظيفة تعيين المسار للتشغيل وخوارزمية الحصول على التردد التالي (وأخذت الجزء السابع بالكامل).

وعملت. بعد ذلك ، قمت بتنفيذ وظائف إنشاء مسار صوتي للمسار المحدد ( PCM ، 44100 هرتز ، 8 بت ، أحادية ؛ فعلت شيئًا مثل المولد المستخدم في محاكي السماعات في DosBox ). لقد قمت بحل المشكلة بعلامة النهاية من خلال عداد بسيط من الصمت: عدت ثانية - نكمل الخوارزمية. عند التفاف المسار الناتج في رأس WAV وحفظ النتيجة في ملف ، حصلت على المسار بالضبط من القائمة الرئيسية. و 13 مسارًا إضافيًا يمكنك الاستماع إليها أدناه [أو في عارض الموارد ، الذي يحتوي الآن على مشغل مضمن والقدرة على حفظ أي مسار في .WAV] :

[أثناء دراسة المشكلة ، تعرفت على تقنيات "تنبيه صوتي" أكثر تقدمًا ، مثل استخدام تعديل عرض النبض لاستنساخ صوت PCM رديء الجودة. في نهاية هذه المقالة ، سأقدم قائمة بالمواد التي يمكنك من خلالها معرفة المزيد.]

في الجزء الثاني ، عندما تم النظر في تنسيقات الموارد المختلفة ، اقترحت أن تحتوي ملفات .ANH على رسوم متحركة لخلفيات الموقع (أي للصور المخزنة في .PIC ). [هذا هو.] بعد الانتهاء من الصوت ، قررت التحقق من ذلك. بحتة على افتراض أن الرسوم المتحركة يتم تطبيقها مباشرة على صورة الخلفية المخزنة في الذاكرة (ليس في ذاكرة الفيديو ، ولكن في سلسلة الرموز المتحركة) ، قررت التخلص من هذه الذاكرة ، على التوالي ، قبل وبعد تطبيق الرسوم المتحركة (انظر حيث يشير المؤشر إلى الأعلى سلسلة الحرف 'S'):

 3DE6:0E26 03 B4 44 B3 ... ;   3DE6:0E26 03 BC CC B3 ... ;   

بالضبط ما توقعته - تغير اللون الأحمر الداكن (0x4) إلى الأحمر الفاتح (0xC). يمكنك الآن محاولة تعيين نقطة التوقف لتغيير القيمة في العنوان ، على سبيل المثال ، 3DE6:0E28 ، وإذا كنت محظوظًا ، قم بإجراء تتبع عكسي. [كنت محظوظاً.] قادني نقطة التوقف إلى خط يغير القيمة مباشرة في العنوان المحدد: xor es:[bx], al . بعد فحص المناطق المحيطة ، قمت بسهولة ببناء سلسلة من المكالمات من حلقة المستوى الرئيسي إلى هذه النقطة: sub_1231E (xor es:[bx], al) <- sub_12222 <- sub_105F6 <- sub_1038F ( ) .

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

أولاً حول تنسيق .ANH . في الواقع ، هي مجموعة من الحاويات ، والكلمة الأولى في ملف .ANH هي عدد الحاويات في الداخل:

 typedef struct anh_hdr_t { uint16_t anh_entries; /* first entry hdr */ } anh_hdr_t; 

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

 typedef struct anh_entry_hdr_t { uint16_t entry_size; uint16_t total_frames; /* anh_frame_data_t first_frame_data */ /* another frames data */ /* anh_frame_hdr first_frame_hdr */ /* another frames */ } anh_entry_hdr_t; typedef struct anh_frame_data_t { uint16_t frame_sleep; uint16_t frame_offset; } anh_frame_data_t; ... extern uint8_t *anh; anh_hdr_t *hdr = (anh_hdr_t*)anh; anh_entry_hdr_t *entry = (anh_entry_hdr_t*)(anh + sizeof(anh_hdr_t)); for (uint16_t u = 0; u < anh->anh_entries; u++) { uint8_t *p = (uint8_t*)entry; anh_frame_data_t *first_frame_data = (anh_frame_data_t*)(p + sizeof(anh_entry_hdr_t)); uint8_t *first_frame_bytes = p + (entry->total_frames * sizeof(anh_frame_data_t)); for (uint16_t k = 0; k < entry->total_frames; k++) { anh_frame_data_t *frame_data = first_frame_data + k; uint8_t *frame_bytes = first_frame_bytes + frame_data->frame_offset; ... } /* plus 2 bytes of padding */ p += (entry->entry_size + 2); entry = (anh_entry_hdr_t*)p; } 

يتكون الإطار المنفصل من رأس رباعي البايت يحتوي على أبعاده الخطية وحالات الإزاحة بالنسبة لصورة الخلفية ، ووحدات بكسل الإطار المشفرة بواسطة الخوارزمية المألوفة لي من قبل Run Length :

 typedef struct anh_frame_hdr { uint8_t bg_x_offt; uint8_t bg_y_offt; uint8_t frame_width; uint8_t frame_height; /* rle encoded frame bytes */ }; 

يمكن أن يبدو "تراكب" الإطار الموجود في الخلفية على النحو التالي:

 extern uint8_t *level_bg; uint8_t frame_pix[8192]; anh_frame_hdr *hdr = (anh_frame_hdr*)frame_bytes; uint16_t frame_len = hdr->frame_width * hdr->frame_height; decode_rle(frame + sizeof(anh_frame_hdr), frame_len, frame_pix); /* 0xFB4E - some magic value, have no idea what is it */ uint16_t bg_offt = (hdr->bg_y_offt * 152) + hdr->bg_x_offt + 0xFB4E; uint16_t bg_skip = 152 - hdr->frame_width; uint8_t *p1 = frame_pix, *p2 = level_bg; for (uint16_t i = hdr->frame_height; i != 0; i--) { for (uint16_t j = hdr->frame_width; j != 0; j--) { *p2++ ^= *p1++; } p2 += bg_skip; } 

هذا هو تنسيق ANH . ولكن هناك هيكل آخر يجعل كل شيء يعمل:

 typedef struct bg_animation_control_table_t { uint16_t total_frames; uint8_t *first_frame_data; uint8_t *first_frame_bytes; uint16_t sleep; uint16_t curr_frame; } bg_animation_control_table_t; 

في اللعبة نفسها ، يتم الإعلان عن مجموعة من أربعة هياكل على الأقل من هذا النوع على مستوى العالم. بعد تحميل ملف ANAN التالي ، يتم أيضًا تخزين عدد الرسوم المتحركة في الداخل في متغير عام ، وتتم تهيئة عناصر الصفيف على النحو التالي:

 extern uint8_t *anh; uint16_t g_anim_amount = 0; bg_animation_control_table_t g_anim_ctl[4]; ... anh_hdr_t *hdr = (anh_hdr_t*)anh; anh_entry_hdr_t *entry = (anh_entry_hdr_t*)(anh + sizeof(anh_hdr_t)); g_anim_amount = hdr->anh_entries; for (uint16_t u = 0; u < g_anim_amount; u++) { uint8_t *p = (uint8_t*)entry; g_anim_ctl[u].total_frames = entry->total_frames; g_anim_ctl[u].first_frame_data = p + sizeof(anh_entry_hdr_t); g_anim_ctl[u].first_frame_bytes = g_anim_ctl[u].first_frame_data + (entry->total_frames * sizeof(anh_frame_data_t)); g_anim_ctl[u].sleep = *(uint16_t*)(g_animation_control[u].first_frame_data); g_anim_ctl[u].curr_frame = 0; /* plus 2 bytes of padding */ p += (entry->entry_size + 2); entry = (anh_entry_hdr_t*)p; } 

أخيرًا ، قم بتطبيق الرسوم المتحركة:

 for (uint16_t u = 0; u < g_anim_amount; u++) { bg_animation_control_table_t *anim = &g_anim_ctl[u]; if (anim->sleep-- == 0) { anh_frame_data_t *data = (anh_frame_data_t*)anim->first_frame_data + anim->curr_frame; /*    */ ... if (++anim->curr_frame == anim->total_frames) { anim->curr_frame = 0; data = (anh_frame_data_t*)anim->first_frame_data; } else { data++; } anim->sleep = data->frame_sleep; } } 

ونحصل على ما يلي [يمكنك أن ترى المزيد في عارض الموارد] :

R2.ANH.GIF

R6.ANH.GIF

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

R53.ANH.GIF

لكن الآن ، لنترك الأمر كما هو.

هل تتذكر خوارزمية الضغط غير المعروفة من الجزء الأول ؟ بعد أن بالكاد اتصل بالتطوير ، لم يحدد viiri فقط نوع الخوارزمية التي كان عليها ، ولكنه كتب أيضًا نسخته الخاصة من وحدة فك الترميز ، لتحل محل قطعة Assembler الرهيبة المكونة من ثلاثة أسطر في قاعدة التعليمات البرمجية. في هذا الصدد ، طلبت من viiri كتابة مقال قصير عن العمل المنجز. وقد تم ذلك ، ولكن قبل أن أعطيها ، يجب أن نقول بضع كلمات حول النظرية.

لضغط الموارد ، استخدم مطورو Neuromancer رمز Huffman . هذه واحدة من أولى الطرق الفعالة لترميز المعلومات باستخدام رموز البادئة . في نظرية التشفير ، تسمى الرموز التي تحتوي على كلمة متغيرة الطول وتلك التي لا توجد فيها كلمة مشفرة بادئة لأخرى رموز الشفرات. بمعنى أنه إذا تم تضمين كلمة "a" في كود البادئة ، فإن كلمة "ab" غير موجودة في الكود. تسمح لك هذه الخاصية باقتحام الكلمات المشفرة بواسطة هذا الرمز بشكل فريد.

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

هوفمان. GIF

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

شيء ما حول كيفية التعامل مع هذا ، وكذلك حول جهاز فك التشفير الخاص بك والذي تم تنفيذه في اللعبة ، يخبر viiri :

من الجدير بالذكر أن اللعبة بالكامل مكتوبة بالكامل بلغة Assembler ، لذا فإن الشفرة تحتوي على حلول وحيل مثيرة للاهتمام وتحسينات.

حسب الإجراءات. sub_1ff94 ( build_code_table ) مطلوبة لتحميل شجرة هوفمان المضغوطة من ملف. لفك شفرة Huffman ثابتة ( ديناميكية في بعض الأحيان ، ولا ينطبق هذا الشرط عليها) ، إلى جانب الرسالة ، يجب إرسال شجرة رمز ، وهو تعيين رموز Huffman إلى رموز الأحرف الحقيقية. هذه الشجرة كبيرة بما يكفي وبالتالي سيكون من الجيد تخزينها بطريقة ما بطريقة فعالة. الطريقة الصحيحة هي استخدام الرموز القانونية ( MOAR ). نظرًا لخصائصها ، هناك طريقة مثيرة للاهتمام وفعالة جدًا لتخزين الشجرة (المستخدمة في تنفيذ طريقة ضغط الانكماش لأرشيف PKZip ). ولكن لا يتم استخدام الرموز الأساسية في اللعبة ، وبدلاً من ذلك يتم اجتياز شجرة مباشرة ويتم كتابة كل بتة قمة 0 إلى دفق الإخراج إذا لم تكن العقدة ورقة ، أو بت 1 إذا كانت العقدة ورقة ، ثم وحدات البت 8 التالية هي رمز الحرف في هذا العقدة. عند فك التشفير ، يتم إجراء اجتياز شجرة مماثل ، والذي نراه في اللعبة. هناك مثال وبعض التفسير.

 build_code_table proc near call getbit ;     jb short loc_1FFA9 ;   ... shl dx, 1 inc bx call build_code_table ;  build_code_table    or dl, 1 call build_code_table ;  build_code_table    shr dx, 1 dec bx ret loc_1FFA9: call sub_1FFC2 ;      (8 ) ... ;     ret sub_1FF94 endp sub_1FFC2 proc near sub di, di mov ch, 8 loc_1FFC6: call getbit rcl di, 1 dec ch jnz short loc_1FFC6 retn sub_1FFC2 endp 

getbit ( sub_1ffd0 ) قليلاً من دفق الإدخال. يسمح لنا تحليلها باستنتاج أن البتات الفردية يتم استخراجها من سجل ax 16 بت ، الذي يتم تحميل قيمته من الذاكرة بواسطة تعليمات lodsw ، التي تقوم بتحميل وحدتي بايت من الدفق ، ولكن نظرًا لأن معالج Intel يحتوي على ترتيب بايت صغير ، فإن xchg يعيد ترتيب نصف التسجيل. علاوة على ذلك ، فإن ترتيب البتات في الدفق غير منطقي إلى حد ما - الأول ليس الأقل ، ولكن الأكثر أهمية. , shl , jb .

 getbit proc near or cl, cl jz short loc_1FFD9 dec cl shl ax, 1 retn loc_1FFD9: cmp si, 27B6h jz short loc_1FFE7 ;   lodsw xchg al, ah mov cl, 0Fh shl ax, 1 retn loc_1FFE7: call sub_202FC ;      lodsw xchg al, ah mov cl, 0Fh shl ax, 1 retn getbit endp 

viiri , :

 typedef struct node_t { uint8_t value; struct node_t *left, *right; } node_t; static uint8_t *g_src = NULL; static int getbits(int numbits) { ... } static uint32_t getl_le() { /*       4-    */ } static node_t* build_tree(void) { node_t *node = (node_t*)calloc(1, sizeof(node_t)); if (getbits(1)) { node->right = NULL; node->left = NULL; node->value = getbits(8); } else { node->right = build_tree(); node->left = build_tree(); node->value = 0; } return node; } int huffman_decompress(uint8_t *src, uint8_t *dst) { int length, i = 0; node_t *root, *node; g_src = src; length = getl_le(); node = root = build_tree(); while (i < length) { node = getbits(1) ? node->left : node->right; if (!node->left) { dst[i++] = node->value; node = root; } } ... } 

:

build_code_table . , , . , . , , , — ( huffman_decompress ).

? ! ! , . ( ): . , 3- , N , (3 — N) .

ABCD : A - 0b, B - 10b, C - 110b, D - 111b . ( ), , :

, . , , , 010b — . . , 'A' 0b , , . :

, 011010111b :

• : 011b ;
• , 011b (3) , A , ;
• 011b 1, , : 110b ;
• , 110b (6) , , ;
• , .

«» 8- . 256 . 8 . , , :

: — , . , . 4 — 32- .

, . .

, github . , , , - [ , README.md] .

, , 2015- :

• LibNeuroRoutines (, MASM) — , , . ( neuro_routines.h ) , . , :
  
  • ( huffman_decompression.c , decompression.c );
  • ( cp437.c );
  • ( dialog.c );
  • ( audio.c ).
• NeuromancerWin64 () — . . , «» , , . CSFML ( SFML C ).
• ResourceBrowser (C++) — . MFC -, .DAT -. :
  
  • BMP (8bpp) ( IMH , PIC );
  • ( ANH );
  • WAV (PCM, 44100Hz, 8bps, mono) ( SOUND ).

LibNeuroRoutines . LibNeuroRoutines CSFML ( ResourceBrowser SFML ).

64- Windows . , LibNeuroRoutines 64- MASM (Microsoft Macro Assembler) . — , 64- . , NASM FASM , , . VS 2015 — MASM .

, . C . , ( , MFC ).

, . - , .

. ? , . , . - , . , , , . ().

1. Make sound from the speaker using assembly
2. Programming the PC Speaker
3. PC Speaker
4. Programmable Interval Timer
5. Making C Sing
6. Beyond Beep-Boop: Mastering the PC Speaker