Die Rückseite des Neuromancers. Teil 4: Sound, Animation, Huffman, Github

Hallo, wie Sie bereits verstanden haben, ist dies eine Fortsetzung meiner Geschichte des Reverse Engineering und der Portierung von Neuromant.

Die Rückseite des Neuromancers. Teil 1: Sprites
Die Rückseite des Neuromancers. Teil 2: Schriftart rendern
Die Rückseite des Neuromancers. Teil 3: Fertiges Rendern, mach das Spiel

Beginnen wir heute mit zwei guten Nachrichten:

• Erstens bin ich nicht mehr allein - der viiri- Benutzer hat sich bereits dem Projekt angeschlossen und bereits einen bedeutenden Beitrag geleistet.
• Zweitens haben wir jetzt ein offenes Repository auf Github .

Im Allgemeinen laufen die Dinge sehr gut, und vielleicht werden wir bald zumindest einen spielbaren Build bekommen. Und lassen Sie uns wie üblich unter dem Schnitt darüber sprechen, was und wie im Moment erreicht wurde.

Er begann sich mit Geräuschen zu beschäftigen. Leider gab es unter den Spielressourcen nichts Ähnliches wie Audio, und da ich keine Ahnung hatte, wie die Musik unter MS-DOS funktioniert, war es äußerst unklar, wo ich anfangen sollte. Nachdem ich ein wenig über alle Arten von SoundBlaster gelesen hatte, war das Beste, was ich mir ausgedacht habe , den zerlegten Code zu scrollen, in der Hoffnung, einige bekannte Signaturen zu sehen. Und wer sucht, findet er normalerweise, auch wenn er nicht ganz das ist, wonach er gesucht hat (Kommentare von Ida ):

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 

Nachdem ich diesen Timer 8253-5 durchgesehen hatte, stieß ich auf einen Artikel , der der erste Schlüssel zum Verständnis des Geschehens war. Im Folgenden werde ich versuchen zu erklären, was was ist.

In der Ära von IBM-PC , also vor dem Aufkommen erschwinglicher Soundkarten, war der sogenannte PC-Lautsprecher , auch als „Piepser“ bekannt, das am häufigsten verwendete Gerät zur Klangwiedergabe. Dieses Gerät ist nichts anderes als ein normaler Lautsprecher, der in den meisten Fällen über einen vierpoligen Anschluss mit dem Motherboard verbunden ist. Der Piepser ermöglichte es der Idee, einen Rechteckimpuls mit zwei Pegeln (entsprechend zwei Spannungspegeln, normalerweise 0 V und + 5 V) zu reproduzieren, und wurde über den 61. Port des PPI- Controllers (Programmable Peripheral Interface) gesteuert. Insbesondere sind die ersten beiden Bits des an den Port gesendeten Werts für die Steuerung des „Lautsprechers“ verantwortlich (siehe Kommentare zu den Zeilen in al, 61h und out 61h, al ).

Wie ich bereits sagte (mit etwas anderen Worten), kann sich unser Sprecher in zwei Zuständen befinden - "in" und "out" ( "niedrig" - "hoch" , "aus" - "ein" , "aus" - "ein") . was auch immer). Um einen Impuls zu erzeugen, muss der aktuelle Zustand in den entgegengesetzten und nach einiger Zeit zurück geändert werden. Dies kann direkt erfolgen, indem das erste Bit (Anzahl von Grund auf neu) von Port 61 wie folgt manipuliert wird:

 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-  

Das Ergebnis der Ausführung dieses Codes sieht folgendermaßen aus:

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

Wenn wir PULSE mit einer Verzögerung wiederholen, erhalten wir ein rechteckiges Signal:

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

Wenn wir im ersten Fall kaum etwas gehört hätten, erhalten wir im zweiten Fall einen Frequenzton, abhängig von der Geschwindigkeit der Maschine, auf der dieser Code ausgeführt wird. Das ist großartig, aber mit gewissen Schwierigkeiten verbunden. In jedem Fall gibt es eine bequemere Möglichkeit, den Lautsprecher zu steuern.

Hier kommt der spielprogrammierbare Dreikanal-Timer - Intel 8253 , dessen zweiter Kanal (ab Null) mit dem Piepser verbunden ist. Dieser Timer empfängt ein Signal vom Intel 8254- Takt, sendet 1193180 Impulse pro Sekunde (~ 1,193 MHz) und kann nach einer bestimmten Anzahl von Impulsen für eine bestimmte Reaktion programmiert werden. Eine dieser Reaktionen ist das Senden eines Rechteckimpulses an den Lautsprecher. Mit anderen Worten, 8253 kann in Form eines Generators eines rechteckigen Signals mit einstellbarer Frequenz arbeiten, was es relativ einfach macht, verschiedene Soundeffekte auf dem Lautsprecher zu synthetisieren. Und hier ist was Sie dafür brauchen:

1. Stellen Sie den zweiten Kanal des Timers auf den rechteckigen Signalerzeugungsmodus. Schreiben Sie dazu einen speziellen Einzelbyte-Wert in Port 43 ( 8253 Mode / Command Register ). In meinem Fall ist dies 10110110B (weitere Details hier ):

 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. Stellen Sie die gewünschte Frequenz auf dem zweiten Kanal ein. Dazu senden wir byteweise vom jüngsten zum ältesten einen Wert von 1193180 / freq an den 42. Port ( 8253 Channel 2-Datenport ), wobei freq der erforderliche Frequenzwert in Hertz ist.

   
   

2. Lassen Sie den Lautsprecher Impulse vom Timer empfangen. Setzen Sie dazu die ersten beiden Bits des Wertes in Port 61 ( PPI ) auf Eins. Tatsache ist, dass wenn das Nullbit auf 1 gesetzt ist, das erste als „Schalter“ interpretiert wird:

   
   

 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. 

Als Ergebnis haben wir folgendes Bild:

  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 ;   

Und genau das tut der Code, den ich ganz am Anfang zitiert habe (mit Ausnahme der Initialisierung, aber ich habe ihn in einer anderen Funktion gefunden): Bei si + 8 wird ein Frequenzteiler an Port 42 gesendet, und bei si + 0Ah - Lautsprecherstatus ( „Ein“ - „Aus“ ), aufgezeichnet in Port 61.

Der Wiedergabemechanismus ist einfach und unkompliziert, aber dann musste man sich mit Timings befassen. Nachdem ich den Code in der Nähe studiert hatte, sah ich, dass in derselben Funktion, in der der Timer initialisiert wird ( sub_2037A , dann init_8253 ), der achte Interrupt- Handler durch die Funktion sub_20416 wird (im Folgenden - play_sample ). Es wurde schnell klar, dass dieser Interrupt ungefähr 18,2 Mal pro Sekunde generiert wird und dazu dient, die Systemzeit zu aktualisieren. Das Ersetzen des Handlers dieses Interrupts ist eine gängige Praxis, wenn Sie 18 Mal pro Sekunde eine Aktion ausführen müssen (tatsächlich muss der ursprüngliche Handler auch innerhalb des Hooks aufgerufen werden, da sonst die Systemzeit stoppt). Auf dieser Grundlage stellt sich heraus, dass die nächste Frequenz alle (1 / 18.2) * 1000 ~ 55 an den Generator (1 / 18.2) * 1000 ~ 55 .

Der Plan war folgender:

• play_sample einen Haltepunkt in die Funktion play_sample in die Zeile, in der der nächste Frequenzteiler extrahiert wird.
• Berechnen Sie die Frequenz nach der Formel freq = 1193180 / divisor ;
• Erzeugen von freq ms quadratischem Frequenzfrequenzsignal in einer Art Audio-Editor (ich habe Adobe Audition verwendet );
• Wiederholen Sie die ersten drei Schritte, bis sich mindestens 3 Sekunden angesammelt haben.

Also habe ich den Anfang der Melodie aus dem Hauptmenü bekommen, aber einige Zeit 10 langsamer als nötig gespielt. Dann habe ich die Dauer des „Samples“ von 55 ms auf 5 ms reduziert - es wurde viel besser, aber das ist immer noch nicht so. Das Timing-Problem blieb offen, bis ich diesen Artikel fand . Es stellte sich heraus, dass der achte Interrupt durch Einspeisung desselben 8253 erzeugt wird, dessen Nullkanal mit dem Interrupt-Controller ( PIC ) verbunden ist. Wenn die Maschine startet, setzt das BIOS den Kanal auf Null, um Impulse mit einer Frequenz von ~ 18,2 Hz zu erzeugen (dh alle ~ 54,9 ms wird ein Interrupt erzeugt). Der Nullkanal kann jedoch so umprogrammiert werden, dass er Impulse mit einer höheren Frequenz erzeugt. Dazu müssen Sie analog zum zweiten Kanal einen Wert von 1193180 / freq in den 40. Port schreiben, wobei freq der erforderliche Frequenzwert in Hertz ist. Dies geschieht in der Funktion init_8253 , nur anfangs habe ich nicht darauf geachtet:

 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). 

Der Wert 13B1h in die Frequenz übersetzt: 1193180 / 13B1h ~ 236.7 , dann erhalten wir ungefähr (1 / 236.7) * 1000 ~ 4.2 pro "Probe". Das Puzzle hat sich entwickelt.

Dann ist es eine Frage der Technologie, eine Funktion zu implementieren, die Soundtracks aus dem Spiel extrahiert. Aber hier ist die Sache, die Werte der Frequenzteiler, die im 42. Port aufgezeichnet sind, werden nicht explizit gespeichert. Sie werden durch einen kniffligen Algorithmus berechnet, dessen Eingabedaten und Arbeitsbereich direkt in der ausführbaren Datei des Spiels liegen (im siebten Segment laut Ida ). Von den Merkmalen gibt es auch keine Anzeichen für das Ende des Titels. Wenn nichts mehr zu spielen ist, erzeugt der Algorithmus unendlich einen Nullzustand des Lautsprechers. Aber ich habe mich nicht darum gekümmert und wie im Fall des Dekomprimierungsalgorithmus ( erster Teil ) habe ich nur die Funktion zum Einstellen der Spur für die Wiedergabe und den Algorithmus zum Erhalten der nächsten Frequenz auf den 64-Bit-Assembler portiert (und das siebte Segment vollständig übernommen).

Und es hat funktioniert. Danach habe ich die Soundtrack-Generierungsfunktionen für die ausgewählte Spur implementiert ( PCM, 44100 Hz, 8 Bit, Mono ; habe so etwas wie einen Generator gemacht, der im Lautsprecheremulator in DosBox verwendet wird ). Ich habe das Problem mit dem Zeichen des Endes mit einem einfachen Zähler der Stille gelöst: eine Sekunde gezählt - wir vervollständigen den Algorithmus. Wenn ich die resultierende Spur in den WAV- Header einwickle und das Ergebnis in einer Datei speichere, habe ich genau die Spur aus dem Hauptmenü erhalten. Und 13 weitere Titel, die Sie unten anhören können [oder im Ressourcen-Viewer, der jetzt über einen integrierten Player verfügt und jeden Titel in .WAV speichern kann] :

[Als ich das Problem studierte, lernte ich fortgeschrittenere „Piepser“ -Techniken kennen, beispielsweise die Verwendung der Pulsweitenmodulation für die PCM-Klangwiedergabe von schlechter Qualität. Am Ende dieses Artikels werde ich eine Liste von Materialien bereitstellen, aus denen Sie mehr erfahren können.]

Im zweiten Teil , als verschiedene Ressourcenformate berücksichtigt wurden, schlug ich vor, dass .ANH- Dateien Animationen für Standorthintergründe enthalten ( dh für in .PIC gespeicherte Bilder ). [Das ist so.] Nachdem ich mit dem Sound fertig war, beschloss ich, ihn auszuprobieren. Rein unter der Annahme, dass die Animation direkt auf das im Speicher gespeicherte Hintergrundbild angewendet wird (nicht im Videospeicher , sondern in der Sprite-Kette ), habe ich mich entschlossen, diesen Speicher vor bzw. nach dem Anwenden der Animation zu sichern (schauen Sie, wo der Cursor nach oben zeigt Buchstabenfolge 'S'):

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

Genau das, was ich erwartet hatte - die dunkelrote Farbe (0x4) änderte sich zu hellrot (0xC). Jetzt können Sie versuchen, den Haltepunkt 3DE6:0E28 , um den Wert an der Adresse zu ändern, z. B. 3DE6:0E28 und mit etwas Glück eine umgekehrte Ablaufverfolgung durchführen. [Ich hatte Glück.] Der Haltepunkt führte mich zu einer Zeile, die den Wert an der angegebenen Adresse direkt ändert: xor es:[bx], al . Nachdem ich die Umgebung untersucht hatte, baute ich leicht eine Kette von Anrufen von der Hauptschleife bis zu diesem Punkt auf: sub_1231E (xor es:[bx], al) <- sub_12222 <- sub_105F6 <- sub_1038F ( ) .

Ich werde nicht näher darauf eingehen, wie ich den Animationsprozess umgekehrt habe. Dies ist eine ziemlich routinemäßige und methodische Arbeit, aber nicht sehr schwierig, wenn die Grenzen klar abgegrenzt sind (der empfangene Backtrack sind diese Grenzen). Aber ich kann nicht anders, als darüber zu sprechen, was am Ende passiert ist.

Zunächst zum .ANH- Format. Tatsächlich handelt es sich um eine Reihe von Containern, und das erste Wort in der ANH- Datei ist die Anzahl der darin enthaltenen Container:

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

Der Container selbst ist eine separat aufgenommene Animation des Hintergrundelements. Sie können einen Header für den Container auswählen, der seine Bytegröße und die Anzahl der Frames in der Animation enthält, die er darstellt. Neben dem Header befinden sich die Werte der Dauer (Verzögerung) des nächsten Frames und des Versatzes der Bytes des Frames selbst relativ zu den Bytes des ersten Frames. Die Anzahl solcher Paare entspricht offensichtlich der Anzahl der Frames:

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

Ein separater Frame besteht aus einem 4-Byte-Header, der seine linearen Abmessungen und Verschiebungen relativ zum Hintergrundbild sowie die Frame-Pixel enthält, die von dem Algorithmus codiert wurden, der mir bereits durch Run Length bekannt ist :

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

Die „Überlagerung“ des Rahmens auf dem Hintergrund kann folgendermaßen aussehen:

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

Dies ist das .ANH-Format , aber es gibt eine andere Struktur, mit der alles funktioniert:

 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; 

Im Spiel selbst wird ein Array von mindestens vier Strukturen dieser Art global deklariert. Nach dem Laden der nächsten ANH- Datei wird die Anzahl der darin enthaltenen Animationen ebenfalls in einer globalen Variablen gespeichert, und die Elemente des Arrays werden wie folgt initialisiert:

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

Wenden Sie zum Schluss die Animationen an:

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

Und wir erhalten Folgendes [Sie können viel mehr im Ressourcen-Viewer sehen] :

R2.ANH.GIF

R6.ANH.GIF

Derzeit gibt es einige Probleme mit der Animation. Das erste ist, dass ich in meinem Code alle verfügbaren Animationen wiedergebe, aber das Original sucht nach einigen globalen Flags, die angeben, ob durch die nächste gescrollt werden soll. Und das zweite, weil einige Animationen dem Bildschirm Objekte hinzufügen, die ursprünglich nicht vorhanden waren. Und da sich die Frames im Hintergrund „streiten“, verschwindet das Objekt bei jedem zweiten Kreis mit einem zyklischen Bildlauf einfach. Hier zum Beispiel, wie es aussehen könnte:

R53.ANH.GIF

Aber jetzt lassen wir es so wie es ist.

Erinnern Sie sich an den unbekannten Dekomprimierungsalgorithmus aus dem ersten Teil ? Nachdem viiri kaum mit der Entwicklung verbunden war, bestimmte er nicht nur, um welche Art von Algorithmus es sich handelte, sondern schrieb auch eine eigene Version des Decoders und ersetzte das schreckliche dreizeilige Stück Assembler in der Codebasis. In diesem Zusammenhang bat ich viiri , einen kurzen Aufsatz über die geleistete Arbeit zu schreiben. Was getan wurde, aber bevor ich es gebe, müssen ein paar Worte über die Theorie gesagt werden.

Um Ressourcen zu komprimieren, verwendeten die Entwickler von Neuromancer den Huffman-Code . Dies ist eine der ersten effektiven Methoden zum Codieren von Informationen mithilfe von Präfixcodes . In der Codierungstheorie werden Codes mit einem Wort variabler Länge und solche, bei denen kein Codewort ein Präfix eines anderen ist, Präfixcodes genannt . Das heißt, wenn das Wort "a" im Präfixcode enthalten ist, ist das Wort "ab" im Code nicht vorhanden. Mit dieser Eigenschaft können Sie die von einem solchen Code codierte Nachricht eindeutig in Wörter aufteilen.

Die Idee des Huffman-Algorithmus besteht darin, dass wir, wenn wir die Wahrscheinlichkeit des Auftretens von Zeichen eines bestimmten Alphabets in der Nachricht kennen, das Verfahren zum Konstruieren von Codes variabler Länge beschreiben können, die aus einer ganzzahligen Anzahl von Bits bestehen. Symbole mit einer höheren Eintrittswahrscheinlichkeit erhalten kürzere Codes und Symbole mit einer geringeren Wahrscheinlichkeit längere Codes. Im Allgemeinen wird die Codierungsprozedur darauf reduziert, den optimalen Codebaum zu erstellen und auf seiner Basis das Nachrichtensymbol dem entsprechenden Code zuzuordnen. Mit der Präfix-Eigenschaft des empfangenen Codes können Sie die komprimierte Nachricht eindeutig dekodieren.

Huffman.GIF

Der Algorithmus hat einen wesentlichen Nachteil (in der Tat nicht einen, aber jetzt ist nur dieser wichtig). Tatsache ist, dass der Decodierer die Tabelle der Häufigkeit des Auftretens von Zeichen, die vom Codierer verwendet werden, kennen muss, um den Inhalt einer komprimierten Nachricht wiederherzustellen. In dieser Hinsicht muss zusammen mit der codierten Nachricht entweder eine Wahrscheinlichkeitstabelle oder der Codebaum selbst (eine im Spiel verwendete Option) übertragen werden. Die Größe zusätzlicher Daten kann relativ groß sein, was die Komprimierungseffizienz erheblich beeinflusst.

Etwas darüber, wie Sie damit umgehen können, sowie über Ihren Decoder und den im Spiel implementierten, sagt viiri :

Es ist erwähnenswert, dass das gesamte Spiel vollständig von Hand in Assembler geschrieben wurde, sodass der Code interessante Lösungen, Tricks und Optimierungen enthält.

Nach den Verfahren. Die Funktion sub_1ff94 ( build_code_table ) wird benötigt, um einen komprimierten Huffman-Baum aus einer Datei zu laden. Um einen statischen Huffman (manchmal dynamisch , und diese Anforderung gilt nicht für ihn) zu dekodieren, muss zusammen mit der Nachricht ein Codebaum übertragen werden, bei dem Huffman-Codes realen Zeichencodes zugeordnet werden. Dieser Baum ist groß genug und daher wäre es schön, ihn irgendwie effizient zu speichern. Am korrektesten ist es, kanonische Codes ( MOAR ) zu verwenden. Aufgrund ihrer Eigenschaften gibt es eine sehr interessante und effektive Möglichkeit, den Baum zu speichern (verwendet bei der Implementierung der Deflate- Komprimierungsmethode des PKZip- Archivierers). Im Spiel werden jedoch keine kanonischen Codes verwendet, sondern es wird eine direkte Baumdurchquerung durchgeführt und für jedes Scheitelpunktbit wird 0 in den Ausgabestream geschrieben, wenn der Knoten kein Blatt ist, oder Bit 1, wenn der Knoten ein Blatt ist, und dann sind die nächsten 8 Bits der Zeichencode in diesem Knoten. Beim Dekodieren wird eine ähnliche Baumdurchquerung durchgeführt, die wir im Spiel sehen. Es gibt ein Beispiel und eine Erklärung.

 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 ) liest ein Bit aus dem Eingabestream. Ihre Analyse lässt den Schluss zu, dass einzelne Bits aus dem 16-Bit- lodsw extrahiert werden, dessen Wert durch den lodsw , der zwei Bytes aus dem Stream lädt, aus dem Speicher geladen wird. Da der Intel-Prozessor jedoch eine Little-Endian- Bytereihenfolge hat, ordnet xchg die Hälfte des Registers neu an. Ferner ist die Reihenfolge der Bits im Strom etwas unlogisch - das erste ist nicht das kleinste, sondern das höchstwertige Bit. , 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 ).

? Richtig! ! , . ( ): . , 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