El reverso del neuromancer. Parte 4: Sonido, Animación, Huffman, Github

Hola, como ya entendiste, esta es una continuación de mi historia de ingeniería inversa y portabilidad de Neuromant.



El reverso del neuromancer. Parte 1: Sprites
El reverso del neuromancer. Parte 2: Renderizar fuente
El reverso del neuromancer. Parte 3: renderizado terminado, haz el juego

Hoy, comencemos con dos buenas noticias:


  • en primer lugar, ya no estoy solo: el usuario de viiri ya se ha unido al proyecto y ya ha hecho una contribución significativa;
  • En segundo lugar, ahora tenemos un repositorio abierto en Github .

En general, las cosas van muy bien, y quizás pronto obtengamos al menos alguna construcción jugable. Y debajo del corte, como de costumbre, hablemos sobre qué y cómo se ha logrado en este momento.




Comenzó a lidiar con el sonido. Por desgracia, entre los recursos del juego no había nada similar al audio, y como no tenía idea de cómo funciona la música en MS-DOS , no estaba muy claro por dónde empezar. Después de leer un poco sobre todo tipo de SoundBlaster , lo mejor que se me ocurrió es desplazar el código desmontado con la esperanza de ver algunas firmas familiares. Y quien busca, generalmente encuentra, incluso si no es exactamente lo que estaba buscando (comentarios de 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 

Después de pasar por este temporizador 8253-5, me encontré con un artículo que se convirtió en la primera clave para comprender lo que estaba sucediendo. A continuación intentaré explicar qué es qué.


Entonces, en la era de IBM-PC , antes del advenimiento de las tarjetas de sonido asequibles, el dispositivo de reproducción de sonido más común era el llamado PC Speaker , también conocido como "beeper". Este dispositivo no es más que un altavoz normal conectado a la placa base, en la mayoría de los casos, a través de un conector de cuatro pines. La señal acústica, de acuerdo con la idea, hizo posible reproducir un pulso rectangular de dos niveles (correspondiente a dos niveles de voltaje, generalmente 0 V y + 5 V) y se controló a través del puerto 61 del controlador PPI (interfaz periférica programable) . Específicamente, los primeros dos bits del valor enviado al puerto son responsables de controlar el "altavoz" (ver comentarios en las líneas in al, 61h y out 61h, al ).


Como dije (en palabras un poco diferentes), nuestro orador puede estar en dos estados: "dentro" y "fuera" ( "bajo" - "alto" , "apagado" - "encendido" , "apagado" - "encendido" , lo que sea) Para crear un impulso, es necesario cambiar el estado actual al opuesto y, después de un tiempo, volver. Esto se puede hacer directamente manipulando el primer bit (recuento desde cero) del puerto 61, por ejemplo, así:


 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-  

El resultado de ejecutar este código se verá así:


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

Repitiendo PULSE con un retraso, obtenemos una señal rectangular:


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

Si en el primer caso apenas hubiéramos escuchado algo, entonces en el segundo obtendremos un tono de frecuencia, dependiendo de la velocidad de la máquina en la que se ejecuta este código. Esto es genial, pero asociado con ciertas dificultades. En cualquier caso, hay una forma más conveniente de controlar el altavoz.


Aquí viene el temporizador programable de tres canales del juego: Intel 8253 , cuyo segundo canal (a partir de cero) está conectado al zumbador. Este temporizador recibe una señal del reloj Intel 8254 , que envía 1193180 pulsos por segundo (~ 1.193 MHz), y puede programarse para una reacción específica después de un número específico de pulsos. Una de estas reacciones es enviar un pulso cuadrado al hablante. En otras palabras, 8253 puede funcionar en forma de un generador de una señal rectangular de frecuencia ajustable, esto hace que sea relativamente fácil sintetizar varios efectos de sonido en el altavoz. Y esto es lo que necesitas para esto:


  1. Establezca el segundo canal del temporizador en el modo de generación de señal rectangular. Para hacer esto, escriba un valor especial de un solo byte en el puerto 43 ( registro de modo / comando 8253 ). En mi caso, esto es 10110110B (más detalles aquí ):

 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. Establezca la frecuencia deseada en el segundo canal. Para hacer esto, byte por bit, desde el más joven hasta el más viejo, enviamos al puerto 42 (puerto de datos 8253 Canal 2 ) un valor igual a 1193180 / freq , donde freq es el valor de frecuencia requerido en hercios.


  2. Permita que el altavoz reciba pulsos del temporizador. Para hacer esto, establezca los dos primeros bits del valor en el puerto 61 ( PPI ) en la unidad. El hecho es que si el bit cero se establece en 1, entonces el primero se interpreta como un "interruptor":



 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. 

Como resultado, tenemos la siguiente imagen:


  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 ;   

Y esto es exactamente lo que hace el código que cité al principio (excepto para la inicialización, pero lo encontré en otra función): en si + 8 hay un divisor de frecuencia enviado al puerto 42, y en si + 0Ah - estado del altavoz ( "encendido" - "apagado" ) grabado en el puerto 61.


El mecanismo de reproducción es simple y directo, pero luego tuvo que lidiar con los tiempos. Después de examinar el código cercano, vi que en la misma función en la que se inicializa el temporizador ( sub_2037A , en adelante - init_8253 ), el octavo controlador de interrupción se reemplaza con la función sub_20416 (en adelante - play_sample ). Pronto quedó claro que esta interrupción se genera aproximadamente 18,2 veces por segundo y sirve para actualizar la hora del sistema. Reemplazar el controlador de esta interrupción es una práctica común si necesita realizar alguna acción 18 veces por segundo (de hecho, el controlador original también debe llamarse dentro del gancho, de lo contrario, la hora del sistema se detendrá). En base a esto, resulta que la siguiente frecuencia se carga al generador cada (1 / 18.2) * 1000 ~ 55 .


El plan era este:


  • ponga un punto de interrupción en la función play_sample , en la línea donde se extrae el siguiente divisor de frecuencia;
  • calcule la frecuencia de acuerdo con la fórmula freq = 1193180 / divisor ;
  • generar 55 ms de señal de frecuencia de frecuencia cuadrada en algún tipo de editor de audio (utilicé Adobe Audition );
  • repita los primeros tres pasos hasta que se acumulen al menos 3 segundos.

Así que obtuve el comienzo de la melodía desde el menú principal, pero tocando un tiempo 10 más lento de lo necesario. Luego reduje la duración de la "muestra" de 55 ms a 5 ms; mejoró mucho, pero aún así no. El problema de tiempo permaneció abierto hasta que encontré este artículo . Resultó que la octava interrupción se genera al alimentar el mismo 8253 , cuyo canal cero está conectado al controlador de interrupción ( PIC ). Cuando la máquina arranca, el BIOS establece el canal cero para generar pulsos con una frecuencia de ~ 18.2 Hz (es decir, se genera una interrupción cada ~ 54.9 ms). Sin embargo, el canal cero se puede reprogramar para que genere pulsos con una frecuencia más alta, para esto, por analogía con el segundo canal, debe escribir un valor igual a 1193180 / freq en el puerto 40, donde freq es el valor de frecuencia requerido en hercios. Esto sucede en la función init_8253 , solo que inicialmente no le init_8253 la debida atención:


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

El valor 13B1h traduce a la frecuencia: 1193180 / 13B1h ~ 236.7 , luego obtenemos aproximadamente (1 / 236.7) * 1000 ~ 4.2 por "muestra". El rompecabezas se ha desarrollado.


Entonces es cuestión de tecnología: implementar una función que extraiga bandas sonoras del juego. Pero aquí está la cosa, los valores de los divisores de frecuencia registrados en el puerto 42 no se almacenan explícitamente. Se calculan mediante un algoritmo complicado, cuyos datos de entrada y el área de trabajo se encuentran directamente en el archivo ejecutable del juego (en el séptimo segmento, según Ida ). Además, de las características, no hay signos del final de la pista, cuando no hay nada más que reproducir, el algoritmo produce infinitamente un estado cero del altavoz. Pero no me molesté y, como en el caso del algoritmo de descompresión (la primera parte ), simplemente transfirí al ensamblador de 64 bits la función de configurar la pista para la reproducción y el algoritmo para obtener la siguiente frecuencia (y tomé el séptimo segmento por completo).


Y funcionó. Después de eso, implementé las funciones de generación de banda sonora para la pista seleccionada ( PCM, 44100 Hz, 8 bits, mono ; hice algo así como un generador utilizado en el emulador de altavoz en DosBox ). Resolví el problema con el signo del fin con un simple contador de silencio: conté un segundo, completamos el algoritmo. Envolviendo la pista resultante en el encabezado WAV y guardando el resultado en un archivo, obtuve exactamente la pista del menú principal. Y 13 pistas más que puedes escuchar a continuación [o en el visor de recursos, que ahora tiene un reproductor incorporado y la capacidad de guardar cualquier pista en .WAV] :



[Al estudiar el tema, aprendí sobre técnicas más avanzadas de "beeper", como el uso de modulación de ancho de pulso para la reproducción de sonido PCM de baja calidad. Al final de este artículo, proporcionaré una lista de materiales de los que puede obtener más información.




En la segunda parte , cuando se consideraron varios formatos de recursos, sugerí que los archivos .ANH contienen animaciones para fondos de ubicación (es decir, para imágenes almacenadas en .PIC ). [Esto es así.] Habiendo terminado con el sonido, decidí comprobarlo. Simplemente asumiendo que la animación se aplica directamente a la imagen de fondo almacenada en la memoria (no en la memoria de video , sino en la cadena de sprites ), decidí volcar esta memoria, respectivamente, antes y después de aplicar la animación (mira donde el cursor apunta a la parte superior cadena de letras 'S'):



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

Exactamente lo que esperaba: el color rojo oscuro (0x4) cambió a rojo brillante (0xC). Ahora puede intentar establecer el punto de interrupción para cambiar el valor en la dirección, por ejemplo, 3DE6:0E28 y, si tiene suerte, realizar un seguimiento inverso. [Tuve suerte.] El punto de ruptura me llevó a una línea que cambia directamente el valor en la dirección dada: xor es:[bx], al . Después de examinar los alrededores, construí fácilmente una cadena de llamadas desde el bucle de nivel principal hasta este punto: sub_1231E (xor es:[bx], al) <- sub_12222 <- sub_105F6 <- sub_1038F ( ) .


No entraré en detalles sobre exactamente cómo revirtí el proceso de animación. Este es un trabajo bastante rutinario y metódico, pero no es muy difícil si los límites están claramente delineados (el seguimiento recibido es estos límites). Pero no puedo evitar hablar de lo que sucedió al final.


Primero sobre el formato .ANH . De hecho, es un conjunto de contenedores, y la primera palabra en el archivo .ANH es la cantidad de contenedores que contiene:


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

El contenedor en sí es una animación tomada por separado del elemento de fondo. Puede seleccionar un encabezado para el contenedor que contenga su tamaño de byte y el número de cuadros en la animación que representa. Junto al encabezado se encuentran los valores de la duración (retraso) del siguiente cuadro y el desplazamiento de bytes del cuadro en sí, en relación con los bytes del primer cuadro. El número de tales pares es obviamente igual al número de cuadros:


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

Un cuadro separado está compuesto por un encabezado de cuatro bytes que contiene sus dimensiones lineales y desplazamientos relativos a la imagen de fondo, y los píxeles del cuadro codificados por el algoritmo que ya me resulta familiar con 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 */ }; 

La "superposición" del marco en el fondo puede verse así:


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

Este es el formato .ANH , pero hay otra estructura que hace que todo funcione:


 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; 

En el juego en sí, una serie de al menos cuatro estructuras de este tipo se declara globalmente. Después de cargar el siguiente archivo .ANH , el número de animaciones dentro también se almacena en una variable global, y los elementos de la matriz se inicializan de la siguiente manera:


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

Finalmente, aplique las animaciones:


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

Y obtenemos lo siguiente [puede ver mucho más en el visor de recursos] :


R2.ANH.GIF

R6.ANH.GIF

Hay un par de problemas con la animación en este momento. La primera es que en mi código reproduzco todas las animaciones disponibles, pero el original comprueba algunas banderas globales que indican si desplazarse a través de la siguiente. Y el segundo, debido al hecho de que algunas animaciones agregan objetos a la pantalla que originalmente no estaban allí. Y dado que los cuadros "pelean" en el fondo, luego con un desplazamiento cíclico, en cada segundo círculo, el objeto simplemente desaparece. Aquí, por ejemplo, cómo se vería:


R53.ANH.GIF

Pero por ahora, dejémoslo como está.




¿Recuerdas el algoritmo de descompresión desconocido de la primera parte ? Habiendo apenas conectado con el desarrollo, viiri no solo determinó qué tipo de algoritmo era, sino que también escribió su propia versión del decodificador, que reemplazó la terrible pieza de ensamblador de tres líneas en la base del código. En este sentido, le pedí a viiri que escribiera un breve ensayo sobre el trabajo realizado. Lo que se hizo, pero antes de darlo, hay que decir algunas palabras sobre la teoría.


Para comprimir recursos, los desarrolladores de Neuromancer utilizaron el código Huffman . Este es uno de los primeros métodos efectivos para codificar información utilizando códigos de prefijo . En la teoría de la codificación, los códigos con una palabra de longitud variable y aquellos en los que ninguna palabra de código es un prefijo de otra se denominan códigos de prefijo . Es decir, si la palabra "a" está incluida en el código del prefijo, entonces la palabra "ab" no existe en el código. Esta propiedad le permite dividir en palabras el mensaje codificado por dicho código.


La idea del algoritmo Huffman es que, conociendo la probabilidad de aparición de caracteres de un determinado alfabeto en el mensaje, podemos describir el procedimiento para construir códigos de longitud variable, que consisten en un número entero de bits. A los símbolos con una probabilidad más alta de ocurrencia se les asignan códigos más cortos, y los símbolos con una probabilidad más baja, por el contrario, los más largos. En general, el procedimiento de codificación se reduce a construir el árbol de código óptimo y, sobre la base, mapear el símbolo del mensaje con el código correspondiente. La propiedad de prefijo del código recibido le permite decodificar de forma exclusiva el mensaje comprimido.


Huffman.GIF

El algoritmo tiene un inconveniente significativo (de hecho, no uno, pero ahora solo este es importante). El hecho es que para recuperar el contenido de un mensaje comprimido, el decodificador debe conocer la tabla de frecuencias de aparición de caracteres utilizados por el codificador. A este respecto, junto con el mensaje codificado, se debe transmitir una tabla de probabilidad o el árbol de códigos (una opción utilizada en el juego). El tamaño de los datos adicionales puede ser relativamente grande, y esto afecta significativamente la eficiencia de la compresión.


Algo sobre cómo puede lidiar con esto, así como sobre su decodificador y el que se implementa en el juego, le dice a viiri :


Vale la pena mencionar que todo el juego fue escrito completamente en Assembler, a mano, por lo que el código contiene soluciones interesantes, trucos y optimizaciones.

De acuerdo a los procedimientos. La función sub_1ff94 ( build_code_table ) es necesaria para cargar un árbol Huffman comprimido desde un archivo. Para decodificar un Huffman estático (a veces dinámico , y este requisito no se aplica a él), junto con el mensaje, se debe transmitir un árbol de códigos, que es un mapeo de códigos Huffman a códigos de caracteres reales. Este árbol es lo suficientemente grande y, por lo tanto, sería bueno almacenarlo de alguna manera eficiente. La forma más correcta es usar códigos canónicos ( MOAR ). Debido a sus propiedades, existe una forma muy interesante y efectiva de almacenar el árbol (utilizado en la implementación del método de compresión Deflate del archivador PKZip ). Pero en el juego, no se utilizan códigos canónicos, en su lugar se realiza un recorrido directo del árbol y para cada vértice se escribe el bit 0 en la secuencia de salida si el nodo no es una hoja, o el bit 1 si el nodo es una hoja, y luego los siguientes 8 bits son el código de caracteres en este nodo. Al decodificar, se realiza un recorrido de árbol similar, que vemos en el juego. Hay un ejemplo y alguna explicación.

build_code_table
 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 ) lee un poco de la secuencia de entrada. Su análisis nos permite concluir que los bits individuales se extraen del registro ax 16 bits, cuyo valor se carga desde la memoria mediante la instrucción lodsw , que carga dos bytes de la secuencia, pero dado que el procesador Intel tiene un orden de bytes little endian , xchg reorganiza la mitad del registro. Además, el orden de los bits en la secuencia es algo ilógico: el primero no es el menor, sino el más significativo. , shl , jb .

getbit
 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 , :


huffman_decompress
 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 . ( ), , :


Código
0 00b1Un
10 0b2B
110 b3C
111 b3D

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


Código
0 00 00b1Un
10 01b1Un
20 10b1Un
30 11b1Un
4 410 0b2B
5 510 1b2B
6 6110 b3C
7 7111 b3D

, 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 2015MASM .


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

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


All Articles