Реверсим «Нейроманта». Часть 4: Звук, анимация, Хаффман, гитхаб

Привет, как вы уже поняли, это продолжение моей истории реверс-инжиниринга и портирования «Нейроманта».


-grud_xhetuzh4znt4rbkeakxyi.png

Реверсим «Нейроманта». Часть 1: Спрайты
Реверсим «Нейроманта». Часть 2: Рендерим шрифт
Реверсим «Нейроманта». Часть 3: Добили рендеринг, делаем игру

Сегодня начнём с двух хороших новостей:


  • во-первых, я больше не один — к проекту присоединился и уже успел внести ощутимый вклад пользователь viiri;
  • во-вторых, теперь у нас есть открытый репозиторий на github.

В целом, дела идут очень неплохо и, возможно, скоро мы получим хоть сколько-то играбельный билд. А под катом, как обычно, поговорим о том, чего и каким образом удалось достичь на текущий момент.


Начал разбираться со звуком. Увы, но среди игровых ресурсов не оказалось ничего похожего на аудио, а поскольку я понятия не имел, как музыка работает в MS-DOS, было крайне непонятно, с чего начать. Почитав немного про всякие SoundBlaster-ы, лучшее, что я придумал, это скроллить дизассемблированный код в надежде увидеть какие-нибудь знакомые сигнатуры. А кто ищет, тот обычно находит, даже если и не совсем то, что искал (комментарии проставлены Идой):

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

Прогуглив этот Timer 8253–5 я набрёл на статью, ставшую первым ключом к пониманию происходящего. Ниже я постараюсь объяснить, что к чему.

Так вот, в эпоху IBM-PC, до появления доступных звуковых карт, наиболее распространённым устройством воспроизведения звука был так называемый PC Speaker, также известный как «бипер». Это устройство есть не что иное, как обычный динамик, подключавшийся к материнской плате, в большинстве случаев, через четырёхпиновый разъём. Бипер, по задумке, позволял воспроизводить двухуровневый прямоугольный импульс (соответствующий двум уровням напряжения, обычно это 0V и +5V) и управлялся через 61-й порт контроллера PPI (Programmable Peripheral Interface). Конкретно за управление «спикером» отвечают первые два бита посылаемого в порт значения (смотри комментарии к строкам in al, 61h и out 61h, al).

Как я уже сказал (немного другими словами), наш динамик может находиться в двух состояниях — «in» и «out» («low»-«high», «off»-«on», «выкл»-«вкл», как угодно). Для создания одного импульса, необходимо изменить текущее состояние на противоположное и, через некоторое время, обратно. Это можно сделать напрямую, манипулируя первым битом (считаем с нуля) 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-й порт

Результат выполнения этого кода будет выглядеть cледующим образом:

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

Повторяя PULSE с задержкой, мы получим прямоугольный сигнал:

    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 Mode/Command register). В моём случае — это 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-й порт (8253 Channel 2 data port) значение, равное 1193180 / freq, где freq — это требуемое значение частоты в Герцах.


  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), происходит подмена обработчика восьмого прерывания (Time of Day) на функцию sub_20416 (далее — play_sample). Вскоре выяснилось, что это прерывание генерируется примерно 18.2 раза в секунду и служит для обновления системного времени. Подмена обработчика этого прерывания — распространённая практика, если нужно выполнять некоторое действие 18 раз в секунду (на самом деле, внутри хука также необходимо вызывать оригинальный обработчик, иначе остановится системное время). Исходя из этого получается, что очередная частота заряжается в генератор каждые (1 / 18.2) * 1000 ~ 55мс.

План был такой:


  • поставить брейкпоинт в функции play_sample, на строчке, где извлекается очередной делитель частоты;
  • вычислить частоту по формуле freq = 1193180 / divisor;
  • сгенерировать 55 мс прямоугольного сигнала частоты freq в каком-нибудь аудиоредакторе (я использовал Adobe Audition);
  • повторять первые три шага до накопления хотя бы 3-х секунд.

Так я получил начало мелодии из главного меню, но играющее раз эдак в 10 медленнее, чем нужно. Тогда я сократил длительность «сэмпла» с 55 мс до 5 мс — стало гораздо лучше, но всё ещё не то. Вопрос с таймингами оставался открытым, пока я не нашёл вот эту статью. Оказалось, что восьмое прерывание генерируется с подачи всё того же 8253, нулевой канал которого подключен к контроллеру прерываний (PIC). Во время загрузки машины BIOS настраивает нулевой канал на генерацию импульсов с частотой ~18.2 Гц (то есть прерывание генерируется каждые ~54.9 мс). Однако нулевой канал можно перепрограммировать так, чтобы он генерировал импульсы с большей частотой, для этого, по аналогии со вторым каналом, в 40-й порт нужно записать значение, равное 1193180 / freq, где freq — это требуемое значение частоты в Герцах. Это и происходит в функции 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 переводим в частоту: 1193180 / 13B1h ~ 236.7Гц, тогда получаем примерно (1 / 236.7) * 1000 ~ 4.2мс на «сэмпл». Пазл сложился.

Дальше уже дело техники — реализовать функцию, извлекающую звуковые дорожки из игры. Но вот в чём дело, значения делителей частоты, записываемые в 42-й порт, не хранятся в явном виде. Они вычисляются неким хитрым алгоритмом, входные данные и рабочая область которого лежат прямо в исполняемом файле игры (в седьмом сегменте по версии Иды). Ещё, из особенностей, здесь не предусмотрено признака окончания трека, когда играть больше нечего, алгоритм бесконечно выдаёт нулевое состояние динамика. Но я не стал заморачиваться и, как и в случае с алгоритмом декомпрессии (первая часть), просто портировал на 64-битный ассемблер функцию установки трека на воспроизведение и алгоритм получения очередной частоты (а седьмой сегмент я забрал целиком).

И это сработало. После, я реализовал функции генерации звуковой дорожки для выбранного трека (PCM, 44100 Hz, 8 bit, mono; сделал нечто наподобие генератора, используемого в эмуляторе спикера в DosBox). Проблему с признаком окончания я решил простым счётчиком тишины: насчитали секунду — завершаем алгоритм. Завернув полученную дорожку в WAV-заголовок и сохранив результат в файл, я получил в точности трек из главного меню. И ещё 13 треков, которые вы можете прослушать ниже [или в просмотрщике ресурсов, в котором теперь есть встроенный плеер и возможность сохранить любой трек в .WAV]:

[Изучая вопрос, я узнал и про более продвинутые техники «игры на бипере», вроде использования широтно-импульсной модуляции для низкокачественного воспроизведения PCM-звука. В конце этой статьи я приведу список материалов, из которых можно узнать больше.]


Во второй части, когда рассматривались различные форматы ресурсов, я предположил, что в .ANH-файлах лежат анимации для бэкграундов локаций (то есть для изображений, хранящихся в .PIC). [Это так.] Закончив со звуком, я решил это проверить. Чисто исходя из предположения, что анимация применяется прямо на изображение задника, хранящееся в памяти (не в видеопамяти, а в спрайт-чейне), я решил сделать дампы этой памяти соответственно до и после применения анимации (смотрим туда, куда указывает курсор — на верхнюю строку буквы 'S'):

zp9aqnvcvi-gn3pp0t1puzvhpti.gifjz9ligummo9j_xwwatid-s0vcri.pngszpduyzc7lgsqum_np9sbvrq4qo.png

3DE6:0E26     03 B4 44 B3 ...   ; первый кадр
3DE6:0E26     03 BC CC B3 ...   ; второй кадр

Именно то, чего я ожидал — тёмно-красный цвет (0×4) сменился на ярко-красный (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;

В самой игре глобально объявлен массив как минимум из четырёх структур такого вида. После загрузки очередного .ANH-файла, количество анимаций внутри также сохраняется в глобальную переменную, а элементы массива инициализируются следующим образом:

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
p7lvfn5ytpjm5nsoctsumdncuaa.gif


R6.ANH.GIF
j6nbxpj29jlrikbmjl8f62s4xmc.gif

На данный момент с анимацией есть пара проблем. Первая заключается в том, что в своём коде я проигрываю все имеющиеся анимации, однако оригинал проверяет некие глобальные флаги, указывающие нужно ли прокручивать очередную. И вторая, связанная с тем, что некоторые анимации добавляют на экран объекты, которых изначально там нет. А поскольку кадры «ксорятся» на бэкграунд, то при циклическом прокручивании, на каждом втором круге объект просто пропадает. Вот, например, как это может выглядеть:


R53.ANH.GIF
d35liujvu6ash9gcdrecvoq9kuc.gif

Но пока оставим всё как есть.


Помните неизвестный алгоритм декомпрессии из первой части? Едва только подключившись к разработке, viiri не только определил, что именно это за алгоритм, но и написал свой вариант декодера, заменивший в кодовой базе ужасный трёхсотстрочный кусок Ассемблера. В связи с этим, я попросил viiri написать небольшой очерк о проделанной работе. Что и было сделано, но перед тем, как я его приведу, пару слов нужно сказать о теории.

Для сжатия ресурсов разработчики «Нейроманта» использовали код Хаффмана. Это один из первых эффективных методов кодирования информации, использующий префиксные коды. В теории кодирования префиксными называют коды со словом переменной длины и такие, в которых ни одно кодовое слово не является префиксом другого. То есть, если в состав префиксного кода входит слово «a», то слова «ab» в коде не существует. Это свойство позволяет однозначно разбивать на слова сообщение, закодированное таким кодом.

Идея алгоритма Хаффмана состоит в том, что, зная вероятности появления символов некоторого алфавита в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью появления ставятся в соответствие более короткие коды, а символам с меньшей вероятностью — наоборот, более длинные. В целом, процедура кодирования сводится к построению оптимального кодового дерева и, на его основе, отображению символа сообщения на соответствующий код. Свойство префиксности полученного кода позволяет однозначно декодировать сжатое им собщение.


Huffman.GIF
faishbcvf0flxiao-mfmnx3llvu.gif

У алгоритма есть один существенный недостаток (на самом деле не один, но сейчас важен только этот). Дело в том, что для того, чтобы восстановить содержимое сжатого сообщения, декодер должен знать таблицу частот появления символов, которой пользовался кодер. В связи с этим, вместе с закодированным сообщением должна передаваться либо таблица вероятностей, либо само кодовое дерево (вариант, используемый в игре). Размеры дополнительных данных могут быть относительно велики, а это существенно бъёт по эффективности сжатия.

Кое-что о том, как с этим можно бороться, а так же про свой декодер и тот, который реализован в игре, рассказывает viiri:


Сразу стоит упомянуть, что вся игра была полностью написана на Ассемблере, руками, поэтому код содержит интересные решения, трюки и оптимизации.

По процедурам. Функция sub_1ff94 (build_code_table) нужна для загрузки из файла сжатого дерева Хаффмана. Для декодирования статического Хаффмана (бывает и динамический, и на него это требование не распространяется) вместе с сообщением нужно передать кодовое дерево, которое представляет из себя сопоставление кодов Хаффмана реальным кодам символов. Это дерево достаточно большое и поэтому неплохо бы и его как-нибудь эффективно хранить. Наиболее правильный способ — использование канонических кодов (MOAR). Благодаря их свойствам, существует очень интересный и эффективный способ хранения дерева (используется в реализации метода сжатия Deflate архиватора PKZip). Но в игре канонические коды не используются, вместо этого осуществляется прямой обход дерева и для каждой вершины в выходной поток записывается бит 0, если узел не является листом, или бит 1, если узел является листом, и тогда следующие 8 бит являются кодом символа в этом узле. При декодировании осуществляется аналогичный обход дерева, который мы и видим в игре. Тут есть пример и некоторое объяснение.


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) осуществляет чтение бита из потока входных данных. Её анализ позволяет заключить, что отдельные биты выделяются из 16-битного регистра ax, значение в который загружается из памяти инструкцией lodsw, которая грузит два байта из потока, но так как процессор Intel имеет порядок байт little-endian, то xchg переставляет половины регистра. Далее, порядок битов в потоке на вид несколько нелогичен — первым является не младший, а старший бит. Это сделано потому, что инструкция shl выталкивает старший бит во флаг переноса, который потом удобно проверять командой условного перехода jb.


build_code_table
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. Сдвинем коды символов до упора влево (в трёхбитном слове), и занесём в таблицу получившийся код, длину кода и соответсвующий символ:


Код Длина Символ
000b 1 A
100b 2 B
110b 3 C
111b 3 D

Считывая по три бита из входного потока, мы можем использовать итоговое значение как индекс в этой таблице для быстрого получения соответствующего символа. Но что, если, например, мы прочитаем из потока значение 010b — такого кода в таблице нет. И вот тут себя проявляет свойство префиксности. Ведь то, что символу 'A' соответсвует код 0b означает, что оставшимся символам алфавита не может соответствовать код, начинающийся с нулевого бита. Тогда таблица дополняется следующим образом:


Индекс Код Длина Символ
0 000b 1 A
1 001b 1 A
2 010b 1 A
3 011b 1 A
4 100b 2 B
5 101b 2 B
6 110b 3 C
7 111b 3 D

Допустим, есть входная последовательность 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

© Habrahabr.ru