Примечание редактора:
Прежде чем мы погрузимся в технические детали, важно понимать, как этот баг проявлялся на практике, ведь он оставался незамеченным 40 лет.
Маскировка под механику: Чтобы спровоцировать ошибку, нужно было бросить в «бесконечной пустыне» около 9 предметов. Но в игре заложен шанс 1/3, что предмет просто «засыпет песком». Игрок думал, что это суровая механика выживания, а не сбой.
Текстовые галлюцинации: При переполнении буфера игра начинала выдавать бессмыслицу. Движок читал координаты предметов как коды из внутреннего словаря сокращений, заменяя обычные слова (например, артикль «the») на случайные фразы.
Зависания: В худшем случае «мусорные» данные совпадали с управляющими битовыми комбинациями, текстовый движок попадал в бесконечный цикл, и игра намертво зависала при попытке вывести любое описание.
Большинство игроков либо не носили с собой кучу предметов в пустую локацию, либо просто списывали странное поведение на «особенности» старых текстовых квестов или сбои эмулятора.
Вчера состоялся публичный релиз Planetfall, но, конечно же, последние несколько недель я был сосредоточен на Infidel. Пару дней назад я наткнулся на самый вопиющий баг, который когда‑либо видел в играх Infocom.
Эту ошибку крайне сложно обнаружить, просто играя в игру. Должно быть, я первый, кто её заметил — просто потому что я первый, кто играл в неё с (аналогом) отладчика на уровне памяти.
Так почему же я называю эту ошибку вопиющей? Большинство людей назвали бы её «тривиальной», поскольку она почти никогда не влияет на игровой процесс. Но посмотрите: это баг с диким указателем (wild pointer), который непреднамеренно перезаписывает память. Как Си‑программист, я по закону обязан считать повреждение памяти тягчайшим из всех возможных грехов. Вдобавок ко всему, это баг компилятора!
Предупреждение: В этой статье будут рассмотрены детали кода ZIL и реализации Z‑машины. Обратите внимание, что я анализирую версию Infidel 22 с серийным номером 840 522 (обновление для Macintosh). В оригинальной версии с серийным номером 830 916 обнаружена та же ошибка, но с немного другими адресами памяти.
Сцена действия
Действие игры Infidel происходит в отдалённой египетской пустыне. Вы начинаете в своём лагере. Нил находится на западе. На востоке расположены девять локаций в пустыне, образующих сетку 3×3. (В одной из них находится погребённая пирамида, которую вы ищете.)
Если вы выйдете за пределы этого региона или покинете свой лагерь в любом другом направлении, вы официально заблудитесь в пустыне. Вы можете путешествовать сколько угодно, но будете находить только новые пустынные места. (Пока вас не настигнет солнечный удар.) Это известный трюк, впервые замеченный в Enchanter: одна комната, называемая ENDLESS-DESERT, представляет собой все не отмеченные на карте пустынные участки. Когда вы перемещаетесь, если вы не вернулись в свой лагерь или на отмеченную область, вы просто возвращаетесь обратно в ENDLESS-DESERT. Игра отслеживает ваши широту и долготу.
Чтобы это выглядело убедительно, игра должна жонглировать объектами. Если вы бросаете предметы в ENDLESS-DESERT, а затем перемещаетесь, эти предметы смещаются за пределы сцены. Их широта и долгота записываются в массив, называемый DESERT-TABLE. Если вы вернётесь к этим координатам позже, игра сможет переместить эти объекты из массива DESERT-TABLE обратно в ENDLESS-DESERT, и вы обнаружите их ожидающими вас.
(Вероятно. Когда вы бросаете предмет в ENDLESS-DESERT, существует один шанс из трёх, что он тут же засыплется песком и будет потерян навсегда. Это здесь не имеет значения, за исключением того, что затрудняет обнаружение ошибки, как мы увидим.)
Итак, пока план выглядит многообещающе. Давайте посмотрим, как он реализован на практике:
Пустыня. Вы находитесь в пустыне, огромной песчаной пустоши, изнывающей от жары. > БРОСИТЬ КИРКУ, ЛОПАТУ. Кирка: уронена. Лопата: уронена. С дюны накатывает короткий, но сильный порыв ветра, хлещущий песком вам в лицо и ослепляющий вас на достаточно долгое время, чтобы вы потеряли из виду лопату. > ВОСТОК Пустыня. Вы находитесь в пустыне, огромной песчаной пустоши, изнывающей от жары. > ЗАПАД Пустыня. Вы находитесь в пустыне, огромной песчаной и жаркой пустоши. Здесь лежит кирка.
Обе локации — это ENDLESS-DESERT, но кирка создаёт иллюзию отдельных комнат.
(Разве не было бы реалистичнее, если бы лопата бесшумно исчезла, зарывшись в песок, пока вы отвернулись? Возможно, это плохо показало себя в ходе тестирования.)
В общем, кажется, всё работает нормально. В чём же ошибка?
Разбор кода
Давайте рассмотрим процедуру DESERT-TO-TABLE, обеспечивающую эту работу:
<ROUTINE DESERT-TO-TABLE ( SLOC "AUX" (TBL ,DESERT-TABLE) (CNT 0) (F <FIRST? ,ENDLESS-DESERT>) N) <REPEAT () <COND (.F <SET N <NEXT? .F>>) (ELSE <RETURN>)> <COND (<EQUAL? .F ,WINNER>) (<FSET? .F ,TAKEBIT> <REPEAT () <COND (<==? <GET .TBL .CNT> 0> <PUT .TBL .CNT .SLOC> <PUT .TBL <+ .CNT 1> .F> <SET CNT <+ .CNT 2>> <REMOVE .F> <RETURN>) (ELSE <SET CNT <+ .CNT 2>>)>)>)> <SET F .N>>>
Существует аналогичная процедура TABLE-TO-DESERT для восстановления данных. Мы сосредоточимся на первой.
Эта процедура имеет один обязательный аргумент: SLOC — координаты широты и долготы. (Они закодированы одним числом, но это не имеет значения.) Затем "AUX" помечаются четыре необязательных аргумента, которые также служат локальными переменными; Z‑машина их не различает. TBL — это адрес массива, в который мы будем записывать данные. По умолчанию он равен DESERT-TABLE. F инициализируется первым объектом в списке содержимого ENDLESS-DESERT. CNT и N инициализируются нулём.
Так уж получилось, что при вызове этой функции игра передаёт только один аргумент — SLOC. Она полагается на значение по умолчанию TBL = DESERT-TABLE. (Если бы в игре было две бесконечные пустыни, она бы вызвала эту процедуру с двумя отдельными таблицами. Но их нет.) DESERT-TABLE — это массив из 100 значений (200 байт), начинающийся с адреса 11129.
В теле функции перебираются все объекты в списке ENDLESS-DESERT (начиная с F). Каждый переносимый объект (за исключением декораций и игрока) удаляется, и мы добавляем в массив TBL два значения: координаты SLOC и идентификатор объекта. В таблице уже могут быть записи (можно размещать объекты в нескольких местах), поэтому мы тщательно ищем пустые места для заполнения. Когда мы достигаем конца списка, мы заканчиваем. Если логика кажется немного запутанной, помните, что мы имеем дело со связанным списком.
Пока всё звучит неплохо? Мне тоже. «Эй, — подумал я про себя, — надо бы отобразить содержимое DESERT-TABLE во вкладке „States“ (Состояния)! Так люди смогут наблюдать за тем, как объекты добавляются и удаляются».
Я это настроил... и это не сработало. Массив DESERT-TABLE оставался совершенно пустым. Я видел, как объекты исчезают и появляются — только посмотрите на эту кирку выше! — но куда они девались?
Любой программист на C, столкнувшись с массивом фиксированного размера, спросит: «А как же переполнение массива?» Но у DESERT-TABLE есть комментарий:
;"length should be 2*number of takeable objects"
Действительно, 100 значений по два значения на элемент — это достаточно места для 50 объектов. Если сложить все переносимые объекты в игре, получится (кажется) 45. В любом случае, в массиве ничего не хранится.
Пора декомпилировать функцию DESERT-TO-TABLE из игрового файла и взглянуть на неё. (Я же предупреждал, что мы будем копать глубоко...)
Routine 109bc, 5 locals (0000, 001e, 0000, 0000, 0000) 109c7: GET_CHILD ENDLESS-DESERT -> .F [TRUE] 109cb 109cb: JZ .F [TRUE] RTRUE 109ce: GET_SIBLING .F -> .N [TRUE] 109d2 109d2: JE .F, G70 [FALSE] 109d9 109d6: JUMP 10a02 109d9: TEST_ATTR .F, #0f [FALSE] 10a02 109dd: LOADW .TBL, .CNT -> -(SP) 109e1: JZ (SP)+ [FALSE] 109fb 109e4: STOREW .TBL, .CNT, .SLOC 109e9: ADD .CNT, #01 -> -(SP) 109ed: STOREW .TBL, (SP)+, .F 109f2: ADD .CNT, #02 -> .CNT 109f6: REMOVE_OBJ .F 109f8: JUMP 10a02 109fb: ADD .CNT, #02 -> .CNT 109ff: JUMP 109dd 10a02: STORE .F, .N 10a05: JUMP 109cb
(Если вы смотрите версию 1 983 года, то эта последовательность действий выполняется по адресу 1051a, но в остальном идентична.)
Я использую инструмент дизассемблирования txd из пакета ztools, но отредактировал вывод, чтобы показать имена переменных. Обратите внимание, что имена опкодов не соответствуют современной терминологии ZIL. Они относятся к началу 1990-х годов. У нас не было руководств по ZIL, поэтому нам пришлось придумать собственные имена опкодов.
Первая строка устанавливает начальное значение F равным первому объекту в комнате (<FIRST? ,ENDLESS-DESERT>). Вторая строка проверяет, равно ли F нулю, что является условием цикла функции REPEAT. Цикл продолжается с этого момента.
Заметили что‑нибудь недостающее? Где мы инициализируем TBL его значением по умолчанию DESERT-TABLE (11129)? Это кажется очевидным упущением.
Ага, говорит ZIL, мы вам поможем. Функция Z‑машины имеет слоты для инициализации своих локальных переменных (или необязательных аргументов) константами. Это показано в строках заголовка:
Routine 109bc, 5 locals (0000, 001e, 0000, 0000, 0000)
CNT инициализируется нулём, как и N (неявно). F не инициализируется из слота, потому что это вычисляемое значение, а не константа. ZIL генерирует строку FIRST? (GET_CHILD) в начале функции. DESERT-TABLE является константой, поэтому...
..Ой. Нет, это не так. DESERT-TABLE — это глобальная переменная. Её значение никогда не изменится — оно будет равно 11 129 на протяжении всей игры — но ZIL этого не знает! TBL инициализируется константным значением 30 (шестнадцатеричное 1e), которое является индексом переменной DESERT-TABLE.
Примечание редактора:
В архитектуре Z‑машины глобальные переменные хранятся в памяти, начиная с адреса0x10(16 в десятичной системе). Каждая переменная занимает 2 байта. Поэтому 15-я глобальная переменная имеет индекс 15 × 2 = 30. Компилятор ошибочно подставил этот индекс вместо реального адреса памяти (11129).
По всей видимости, никто не подумал об этом кейсе (аргумент, значение которого по умолчанию принимается за значение глобальной переменной). Если бы подумали, ZIL либо выдал бы ошибку компилятора («Значение по умолчанию не является константой!»), либо сгенерировал бы инструкцию STORE в начале функции (так же, как инициализируется переменная F). 30 — это просто неправильно.
В итоге, когда DESERT-TO-TABLE начинает запись номеров объектов в память, запись происходит не по адресу 11129. Вместо этого перезаписывается память по адресам 30 и выше. Вот незадача.
Процедура TABLE-TO-DESERT использует глобальный аргумент по умолчанию точно таким же образом. Таким образом, она извлекает список объектов из адреса 30, выдавая, казалось бы, правильные результаты. Но память испорчена.
Что находится по этому адресу?
Первые 64 байта памяти содержат данные заголовка, но используется не весь заголовок. По чистой случайности, в версии Z‑машины 3 значимыми являются только адреса 0–29. Если бы DESERT-TABLE был третьей глобальной переменной (индекс 18), эта ошибка привела бы к повреждению серийного номера игры! Что было бы гораздо очевиднее.
Таким образом, адреса 30–63 не используются, но адрес 64 — это начало данных сокращений (abbreviations). Это часть схемы сжатия текста Z‑машины: список из 96 слов, которые встречаются часто и, следовательно, могут быть извлечены и заменены несколькими битами.
Предположение: если мы бросим девять предметов в пустыню (а затем уйдём), последний из них перезапишет начало таблицы сокращений.
Это довольно хлопотно организовать. Помните, что у упавших предметов есть один шанс из трёх просто исчезнуть. Мне пришлось перетащить туда много вещей и попробовать несколько раз. Но у меня получилось, и следующий текст, который вывела игра, выглядел так:
Вы находитесь в пустыне, огромной песчаной пустоши, изнурительной жарой. Из песка высовывается маленькая ящерица и спрашивает, как ей добраться до Таймс‑сквер по кратчайшему пути. Вы на мгновение чешете затылок, и, вспомнив, какую линию метро ей порекомендовать, замечаете, что она исчезла.
Конечно, это галлюцинация, вызванная перегревом, но обратите внимание, что слово «the» (первое сокращение) заменено на «You» (второе). Это указывает на то, что исходные строковые данные были перезаписаны мусором (garbage data), у которого отсутствует терминатор, поэтому процедура печати продолжается до следующей допустимой строки.
В другом тесте мне удалось вызвать сбой интерпретатора. Я подозреваю, что он перезаписал первое сокращение битами, представляющими это сокращение, поэтому процедура вывода вошла в бесконечный цикл. Ну, вы понимаете. Как это обычно и бывает.
Отлично! Ошибка продемонстрирована! Чему мы научились?
Этот баг был обнаружен, и никто его абсолютно не заметил. Когда я в детстве играл в Infidel и исследовал пустыню, моя игра повреждала память. То же самое происходило со всеми остальными игроками, включая тестировщиков Infocom.
Весьма вероятно, что никто не пытался сбросить в Бесконечной пустыне больше восьми предметов. Зачем? Там ничего нет! Это никуда не ведёт. Весь этот механизм существует лишь для того, чтобы занять игроков, которые ещё не обнаружили пирамиду. Внимание к деталям типично для Infocom, но, похоже, эта область не была тщательно протестирована.
(Я был бы рад просмотреть журналы тестирования Infocom, чтобы увидеть, не обнаружились ли там какие‑либо следы ошибки. В архиве Infocom, похоже, ничего подобного нет. Сообщите, если вы что‑нибудь обнаружите.)
В обновлённой версии игры 1 984 года эта ошибка никак не была исправлена. У Infocom не было ничего подобного Visible Zorker.
Примечание редактора:
Visible Zorker — это современный инструмент отладки для Z‑машины, разработанный самим автором статьи (Zarf), который позволяет в реальном времени наблюдать за состоянием памяти, стека и переменных во время выполнения игры. У Infocom в 80-х таких инструментов, разумеется, не было.
Возможно, у них и были инструменты отладки для проверки памяти, но никому не пришло в голову применить их к этим подпрограммам и их хранилищам.
Я не изучал более поздние игры, чтобы проверить, существует ли подобная ошибка — или корректно ли она обрабатывается компилятором. Буду следить за этим.
Как исправить эту ошибку?
Просто: удалить аргумент default для TBL и вместо этого начать подпрограмму с <SET TBL ,DESERT-TABLE>. Или же передать DESERT-TABLE в качестве второго аргумента подпрограмме. Оба варианта подойдут.
Есть ещё пара процедур PROP-TO-TBL и TBL-TO-PROP, в которых обнаружена аналогичная ошибка с таблицей PROP-TBL (адрес 11329, глобальный номер 22). Честно говоря, я немного озадачен этими процедурами. Похоже, они выполняют аналогичную работу по перемешиванию данных в ямах, которые можно выкопать в песке. (Эти ямы хранятся в пустынных комнатах как свойство CAPACITY.) Но игра не позволяет копать в ENDLESS-DESERT; она выдаёт сообщение: «Здесь слишком твёрдая земля». Так что эти процедуры, похоже, бесполезны. Возможно, это остаток более ранней функции, удалённой во время разработки. Возможно, потому что она повреждала серийный номер!
Если бы я обновлял Infidel (а не просто переделывал его), я бы обязательно вернул возможность копать бесполезные ямы в пустыне. Такие незначительные детали — одна из главных прелестей интерактивной литературы (IF).
