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

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

Реверсим «Нейроманта». Часть 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'):

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;

В самой игре глобально объявлен массив как минимум из четырёх структур такого вида. После загрузки очередного .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

R6.ANH.GIF

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

R53.ANH.GIF

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

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

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

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

Huffman.GIF

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

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

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

По процедурам. Функция sub_1ff94 (build_code_table) нужна для загрузки из файла сжатого дерева Хаффмана. Для декодирования статического Хаффмана (бывает и динамический, и на него это требование не распространяется) вместе с сообщением нужно передать кодовое дерево, которое представляет из себя сопоставление кодов Хаффмана реальным кодам символов. Это дерево достаточно большое и поэтому неплохо бы и его как-нибудь эффективно хранить. Наиболее правильный способ — использование канонических кодов (MOAR). Благодаря их свойствам, существует очень интересный и эффективный способ хранения дерева (используется в реализации метода сжатия Deflate архиватора 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) осуществляет чтение бита из потока входных данных. Её анализ позволяет заключить, что отдельные биты выделяются из 16-битного регистра ax, значение в который загружается из памяти инструкцией lodsw, которая грузит два байта из потока, но так как процессор Intel имеет порядок байт little-endian, то 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

Автор: HenadziMatuts

Источник