Ква! Как писали код во времена Quake

Как говорил Джон Кармак: "Фокус — это умение определить, на что вы не будете тратить время". Так давайте не будем тратить время на аннотацию и приступим к анализу кода легендарной Quake World.

Анализируя код чужих проектов, можно наткнуться на места, которые послужат отличным примером для коллег-программистов и себя самого, пускай и примером того, как делать не нужно. Может быть, даже выйдет материал для статьи! Но, бывает, в руки попадает такой проект, что пальцы над клавиатурой начинают трястись от волнения. Созданный современными иконами индустрии, он не оставляет ни единого шанса – нужно приниматься за дело немедленно!

Для автора этих строк Quake – тот самый проект. Пускай не первая игра в "полном" 3D (мы с удовольствием приглашаем вас поспорить в комментариях о Descent), она позволила id Software в очередной раз сдвинуть границы возможного за ранее недостижимые пределы.

Работая с таким проектом, не мудрено и забыть, что он сделан такими же людьми (хотя, конечно, искусственное происхождение Кармака является темой, открытой для дискуссий), а люди допускают ошибки.

Так почему бы не поучиться у лучших из нас! Мы приглашаем вас в исследование того, как написан Quake World!

Вам когда-нибудь хотелось хотя бы на день получить способности прямо как у Доктора Стренджа? Прыгать туда-сюда между измерениями и разрезать ткань самого мироздания? Следующий пример вызвал у вашего покорного именно такое желание:

Без контекста, конечно, не до конца понятно, что не так:

Ну, у нас есть двумерный массив, с которым обходятся как с одномерным. "А что такого? Он же всё равно последовательно лежит в памяти!" — скажет внимательный читатель и будет прав как минимум на основании C99, 6.2.5 Types p20:

Но что если мы позволим напомнить нашему внимательному читателю о существовании в языке C типа указатель на массив T? Итак, указатель на что конкретно мы получим, делая первое обращение к массиву?

Первый оператор [] вернёт переменную типа float[4]. После того, как j превысит значение 3, произойдёт чтение элемента массива вне его пределов, что является классическим примером неопределённого поведения (UB).

О, прекрасный мир UB! В голове сразу же рисуется картина того, как компилятор сделал цикл для установления значений только в первом подмассиве, оставив второй без изменений. Не самое страшное, что могло бы случится в наших играх, но зачем допускать и это!

О неопределённом поведении можно говорить часами. Сегодня следование стандарту скорее похвально, особенно, если производительность при этом не страдает. Конечно, компилятор не отформатирует ваш диск, но зачем рисковать?

Что касается предупреждения анализатора, то он выдал информативное:

V557 Array overrun is possible. The value of 'j' index could reach 7.

P.S. Что интересно, в некоторых местах исходного кода разработчики как будто бы признают ошибочность описанной техники и даже делают сознательный выбор в сторону следующего стандарту решения.

Мы бы хотели предостеречь читателей, наиболее чутко относящихся к лучшим практикам: возможно, вам стоит подумать о завершении чтения прямо сейчас!

А вы, храбрец, узрите!

Быть в курсе, когда что-то идёт не так, может быть полезно и даже желательно. Хотелось бы, конечно, чтобы не так ничего не шло вовсе. Поставьте себя на место компилятора – как бедолаге жить с мыслью о том, что длина строки может быть длиннее, чем массив, в который эта строка записывается? Вот и автор статьи на его месте бы не смог такое представить, ведь записывать значения вне рамок массива, как мы уже выяснили ранее, всё равно что вызывать неопределённое поведение. И вот что будет далее – веря, что такое невозможно, компилятор в релизной версии вовсе уберёт сравнение, vsprintf испортит данные другого объекта, а программист отправится в затяжное путешествие по выдаче в окошке отладчика. И поделом!

Наш анализатор, отойдя от шока, выдал следующее предупреждение:

V547 Expression 'strlen(text) > sizeof (text)' is always false.

Это не единственное место, в котором допускались запоздалые проверки. Обратите внимание на следующий пример:

Пока что вроде бы даже неплохо, но впечатление меняется, как только мы читаем чуть дальше:

Что сказать, проверка указателей – сродни добродетели, но только тогда, когда она делается вовремя. Наш анализатор согласен с таким заключением:

V595 The 'value' pointer was utilized before it was verified against nullptr.

А сейчас нам придётся посмотреть сразу на несколько функций:

Автор статьи помнит самый первый совет из самой первой книжки по программированию им прочитанной – никакого состояния функций в глобальных переменных, никаких состояний функций вообще! Функции, задействующие такие переменные, как минимум трудно поддерживать. Как максимум они становятся нереентрабельными и открывают врата в ад (извините, ошибся игрой).

Ну сколько раз было такое, читатель, что вы забывали про места, в которых использовали глобальные переменные? Уже не говоря о ситуации, в которой вон тот новенький из чистого любопытства нарушал священное правило по вызову функции А СТРОГО после вызова функции Б?

В то же время присмотритесь к окончанию первой функции – есть ли там присваивание какого-то иного значения этой злосчастной переменной?

V507 Pointer to local array 'spans' is stored outside the scope of this array. Such a pointer will become invalid.

К счастью, наш пример просто попахивает, а не ломает игру. Присваивание происходит только внутри рассматриваемых функций. В этом конкретном случае использование локального массива в других функциях ниже по стеку безопасно. Но один маленький шажок в сторону – и готовьтесь к тому, что компилятор начнёт демоническое вторжения на Землю. Что ему помешает: это, в конце концов, неопределённое поведение!

P.S. Занимательно, что одна из трёх вызываемых функций принимает аргументом этот самый локальный массив, не имея дело с глобальной переменной. Учитывая, что sprite_spans используется только в этом ограниченном контексте, такое разнообразие в вызовах оставляет вопрос – почему бы не передавать значение во все три функции?

Давайте теперь посмотрим на несколько собранных в разных местах примеров.

Например, такой:

Или такой:

И, возможно, один из самых приметных в этой секции:

Поднимите руку те, кто имел удовольствие (табличка сарказм прилагается) иметь дело с ошибками, вызванными подобными сравнениями. Не все числа с плавающей точкой могут быть представлены в двоичном коде, поэтому округлений к ближайшему представлению не избежать. Закономерно, результаты сравнений таких чисел могут быть неточны и в худшем случае невоспроизводимы при переносе кода на другие платформы.

Для исправления подобных ситуаций существуют различные техники, вроде absolute difference checks, edit distance checks, relative distance checks (см, например, тут и тут), которые учитывают особенности сравниваемых объектов. Наш анализатор вносит свою лепту в дело предотвращения ошибок при подобных операциях:

V550 An odd precise comparison. It's probably better to use a comparison with defined precision: fabs(...) > Epsilon.

Но подождите, у нас припасён ещё один пример для наибольших снобов (к которым автор сих строк имеет честь причислить и себя). Попробуйте сказать сходу, что не так со следующим кодом:

"Так ведь непонятно, что конкретно сравнивается!" – начинает появляться надпись в комментариях. Давайте узнаем!

Кучка переменных типа int и пара загадочных vec3_t. Ведём расследование дальше:

Понятно, memcmp сравнивает структуры, содержащие переменные типа float. Не лучшая практика по меркам сегодняшних стандартов. Например, SEI CERT рекомендует воздерживаться от этого (смотри в FLP37-C. Do not use object representations to compare floating-point values). Даже в рамках самого небезызвестного IEEE 754 имеется пространство для ошибок при сравнении нулей с разными знаками или переменных со значением NaN. Но, строго говоря, стандарт языка C и не принуждает к использованию IEEE 754 вовсе (впрочем, если вы, читатель, когда-либо получите доступ к машине с иным представлением таких чисел, обязательно сообщите нам об этом!).

В случае же, если в вашей организации действуют строгие правила по сравнению чисел с плавающей точкой, наш анализатор сможет помочь следующим предупреждением:

V1014 Structures with members of real type are compared byte-wise.

P.S. Учитывая, что разработчики достаточно часто напрямую манипулируют байтами внутри чисел с плавающей запятой, автор статьи выражает сомнения по поводу действительной опасности этого малюсенького вызова memcmp.

Ниже приводятся примеры, которым ваш покорный не удосужился определить отдельное название. Пускай и безымянные, они всё же несут в себе источник вдохновения (для улучшения кода, а не повтора их в нём!). Вот эти фрагменты:

Фрагмент 1

Несмотря на то, что разработчики делают проверку на NULL, они всё же не реагируют на ситуацию, когда указатель ему действительно равен. Зачем так делать – непонятно, но понятно, как это классифицировать:

V575 The null pointer is passed into 'strcpy' function. Inspect the second argument.

P.S. Возможно в else ветке вторым аргументом функции strcpy должна была стать переменная dir, но здесь сложно сказать наверняка.

Фрагмент 2

Чёрная магия нынче вне закона, но раньше, как говорят старожилы, для создания flexible arrays использовался т.н. "struct hack". Эта идиома и тогда вызывала вопросы, хотя и зарекомендовала себя крайне полезной – поэтому её облагородили в C99 (смотри пар. 6.7.2.1 в этом обосновании). Появившись уже после создания Quake, эта фича может быть лучшей альтернативой (см., к примеру, доклад о безопасности ядра Линукс) получению предупреждения от анализатора:

V594 The 'conback->data + 320' pointer steps out of array's bounds.

Фрагмент 3

Говорят, явно задавать границы значений в проверках полезно, чтобы не допускать ошибок, как в примере выше (сразу разобраться тяжело, ответ – 112). Спасибо, анализатор:

V695 Range intersections are possible within conditional expressions. Example: if (A > 0 && A < 5) { ... } else if (A > 3 && A < 9) { ... }.

Фрагмент 4

Самое интересное в приведённом примере заключается в том, что комментарии разработчиков явно различаются. Использовались ли там иные значения – загадка, которую анализатор решает так:

V523 The 'then' statement is equivalent to the 'else' statement.

Фрагмент 5

А тут-то что не так? Говоря откровенно, автор статьи практически потерял веру в единорогов (как минимум в одного конкретного), пока разбирался в этом примере. Дьявол, как всегда, в деталях, или, в нашем случае, в предшествующем коде:

То есть цикл не пойдёт дальше 3-х, да? То есть он прокрутится только один раз, да? То есть и неравенство вычистится только один раз. Что сказать, ошибка небольшая, но предупреждение приятное:

V547 Expression 'i != (c - 1)' is always false.

Фрагмент 6

Возможно, разработчики хотели донести свои мысли максимально понятно, а, возможно, просто имели непонятное анализатору чувство юмора:

V583 The '?:' operator, regardless of its conditional expression, always returns one and the same value.

Фрагмент 7

Ничто не заставит нас молчать, когда значение, возращённое функцией malloc, не проверяется! Опасность не только в том, чтобы незамедлительно обратиться по указателю к несуществующей памяти, положив систему на лопатки. Как вам перспектива испортить данные через арифметику указателей – к NULL же тоже можно что-нибудь прибавить, а потом записать что-то по получившемуся адресу! Даже memcpy, в зависимости от имплементации, может успеть поработать, (начиная с конца участка памяти) если передать аргументом нулевой указатель. Впрочем, об этом уже было сказано достаточно, а мы в очередной раз поблагодарим анализатор за предупреждение:

V575 The potential null pointer is passed into 'memcpy' function. Inspect the first argument.

Фрагмент 8

Выше приведены два фрагмента со схожим настроением. Обратите внимание на второй – в отличие от первого, он может содержать серьёзную ошибку в случае, если программист немного плавал в различии двух операций инкремента. Вполне возможно, плюсики должны были стоять с другой стороны имени переменной:

V1048 The variable was assigned the same value.

Фрагмент 9

Учитывая, какие техники рассматривались выше в данной статье, остаётся только спрашивать – а зачем сомневаться в том, что гарантированно? Анализатор согласен с нами в этом вопросе:

V560 A part of conditional expression is always false: c > 127.

Фрагмент 10

Как пелось в знаменитой песне группы Linkin Park — in the end it doesn't even matter. Не самая большая ошибка, которую можно допустить, делая программы на C, но зачем делать и её, если есть следующая диагностика:

V519 The 'bind_grab' variable is assigned values twice successively. Perhaps this is a mistake.

Фрагмент 11

Комментарии говорят сами за себя, но всё же источник данных побитовых операций покрыт тайной. Становится не легче, если взять в расчёт тип, к которому приводится результат. Он определён как int, но в то же время его название заставляет предположить о лимите в 16 бит на время написания кода. Анализатор хмурит брови:

V673 The '2000 << 24' expression evaluates to 33554432000. 35 bits are required to store the value, but the expression evaluates to the 'int' type which can only hold '32' bits.

Фрагмент 12

Хорошо проверить что-то, если в чём-то не уверен. Проверять что-то по нескольку раз может быть свидетельством беспокойного духа. Более того, вы же помните порядок вычисления логического "И"? Анализатор напоминает:

V560 A part of conditional expression is always true: * p.

Фрагмент 13

Классика копипаста. Ни дать, ни взять – только привести диагностику анализатора:

V778 Two similar code fragments were found. Perhaps, this is a typo and 'sv_fraglogfile' variable should be used instead of 'sv_logfile'.

Что за восхитительное приключение! Иметь возможность прикоснуться к работе мастеров нашего дела бесценно, и мы благодарны id Software за выпуск в свет кодовой базы их игр.

Мы также надеемся, что ваше время, читатель, не прошло даром, и нам удалось как минимум вас повеселить. А если же автору этих строк удалось привнести в ваш мир что-то новое и натолкнуть на интересные мысли, то он будет несомненно рад прочитать об этом в комментариях!

Благодарим, что дошли до конца! El Psy Kongroo.