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

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

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

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

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

По ходу статьи мы используем примеры кода. Комментарии в них, обозначенные как PVS-Studio: или // ... были добавлены автором статьи, остальные же – часть исходного кода.

Сами исходники можно найти на официальном Гитхабе id Software.

Мультивселенная безумия

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

// PVS-Studio: void Mod_LoadTexinfo (lump_t *l)
// PVS-Studio: client/model.c

mtexinfo_t *out;
// ... 
for (j=0 ; j<8 ; j++){
    ut->vecs[0][j] = LittleFloat (in->vecs[0][j]);
}

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

// PVS-Studio: client/model.c

typedef struct
{
    float       vecs[2][4]; // PVS-Studio: see what is wrong here?
    float       mipadjust;
    texture_t   *texture;
    int         flags;
} mtexinfo_t;

// PVS-Studio: client/common.h

float (*LittleFloat) (float l);

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

An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type. The element type shall be complete whenever the array type is specified.

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

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

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

Самым скептически настроенным читателям (что можно только приветствовать) мы предлагаем ознакомиться с содержимым пунктов 6.5.2.1/2 и 6.5.6/8 стандарта С99:

Нажми меня:

C99, 6\.5\.2\.1/2:

A postfix expression followed by an expression in square brackets [] is a subscripted designation of an element of an array object. The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))). Because of the conversion rules that apply to the binary + operator, if E1 is an array object (equivalently, a pointer to the initial element of an array object) and E2 is an integer, E1[E2] designates the E2-th element of E1 (counting from zero).

C99, 6.5.6/8:

When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i+n-th and i−n-th elements of the array object, provided they exist. Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. If the result points one past the last element of the array object, it shall not be used as the operand of a unary * operator that is evaluated.

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

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

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

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

// PVS-Studio: void Mod_LoadTexinfo (lump_t *l)
// PVS-Studio: server/model.c

#if 0
    for (j=0 ; j<8 ; j++)
        out->vecs[0][j] = LittleFloat (in->vecs[0][j]);
    len1 = Length (in->vecs[0]);
    len2 = Length (in->vecs[1]);
#else
    for (j=0 ; j<4 ; j++) {
        out->vecs[0][j] = LittleFloat (in->vecs[0][j]);
        out->vecs[1][j] = LittleFloat (in->vecs[1][j]);
    }
    len1 = Length (out->vecs[0]);
    len2 = Length (out->vecs[1]);
#endif

Не грози местному бару, попивая боржоми в санатории

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

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

// PVS-Studio: void Sys_Printf (char *fmt, ...)
// PVS-Studio: client/sys_linux.c, server/sys_linux.c

char text[2048];

va_start (argptr,fmt);
vsprintf (text,fmt,argptr);
va_end (argptr);

if (strlen(text) > sizeof(text))
    Sys_Error("memory overwrite in Sys_Printf");

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

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

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

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

// PVS-Studio: void Info_SetValueForStarKey (/* ... */)
// PVS-Studio: client/common.c

if (strstr (key, "\\") || strstr (value, "\\") )
{
    Con_Printf ("Can't use keys or values with a \\\n");
    return;
}

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

if (!value || !strlen(value))
    return;

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

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

Чем это попахивает?

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

// PVS-Studio: client/d_sprite.c

static sspan_t  *sprite_spans;

void D_DrawSprite (void)
{
    sspan_t     spans[MAXHEIGHT+1];
    sprite_spans = spans; // PVS-Studio: are you dead sure?
    // ...
    D_SpriteScanLeftEdge ();
    D_SpriteScanRightEdge ();
    D_SpriteDrawSpans (sprite_spans);
}

void D_SpriteScanLeftEdge (void)
{
    pspan = sprite_spans;
    // ...
}

void D_SpriteScanRightEdge (void)
{
    pspan = sprite_spans;
    // ...
}

void D_SpriteDrawSpans (sspan_t *pspan)
{
    // PVS-Studio: pspan is used, among other things
}

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

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

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

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

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

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

Великий уравнитель

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

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

// PVS-Studio: void CDAudio_Play(byte track, qboolean looping)
// PVS-Studio: client/cd_linux.c, client/cd_win.c

if (cdvolume == 0.0)
    CDAudio_Pause ();

static float    cdvolume;

Или такой:

// PVS-Studio: void CDAudio_Update(void)
// PVS-Studio: client/cd_linux.c, client/cd_win.c

if (bgmvolume.value != cdvolume)
{
    if (cdvolume)
    // ...
}

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

// PVS-Studio: static qboolean Cam_IsVisible(player_state_t *player, vec3_t vec)
// PVS-Studio: client/cl_cam.c

if (trace.fraction != 1 || trace.inwater)
    return 9999;
typedef struct
{
    float       fraction;       // time completed, 1.0 = didn't hit anything
    // ...
} pmtrace_t;

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

Для исправления подобных ситуаций существуют различные техники, вроде 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.

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

// PVS-Studio: void CL_Record_f (void)
// PVS-Studio: client/cl_demo.c

entity_state_t *es, blankes;
// ...
if (memcmp(es, &blankes, sizeof(blankes))) {
    // ...
}

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

// PVS-Studio: client/protocol.h

typedef struct
{
    int     number;         // edict index
    int     flags;          // nolerp, etc
    vec3_t  origin;
    vec3_t  angles;
    int     modelindex;
    int     frame;
    int     colormap;
    int     skinnum;
    int     effects;
} entity_state_t;

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

// PVS-Studio: client/mathlib.h

typedef float vec_t;
typedef vec_t vec3_t[3];
typedef vec_t vec5_t[5];

Понятно, 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

// PVS-Studio: void COM_AddGameDirectory (char *dir)
// PVS-Studio: client/common.c

char *p;
  
if ((p = strrchr(dir, '/')) != NULL)
    strcpy(gamedirfile, ++p);
else
    strcpy(gamedirfile, p);

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

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

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

Фрагмент 2

// PVS-Studio: void Draw_ConsoleBackground (int lines)
// PVS-Studio: client/draw.c

qpic_t      *conback;
// ...
dest = conback->data + 320 + 320*186 - 11 - 8*strlen(ver);

// PVS-Studio: client/wad.h

typedef struct
{
    int         width, height;
    byte        data[4];            // variably sized
} qpic_t;

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

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

Фрагмент 3

// PVS-Studio: void CL_AddFlagModels (entity_t *ent, int team)
// PVS-Studio: client/cl_ents.cif 

if (ent->frame >= 103 && ent->frame <= 104) f = f + 6;   //nailattack
  else if (ent->frame >= 105 && ent->frame <= 106) f = f + 6;  //light
  else if (ent->frame >= 107 && ent->frame <= 112) f = f + 7;  //rocketattack
  else if (ent->frame >= 112 && ent->frame <= 118) f = f + 7;  //shotattack
}

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

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

Фрагмент 4

// PVS-Studio: float CL_KeyState (kbutton_t *key)
// PVS-Studio: client/cl_input.c

if (impulseup && !impulsedown)
    if (down)
        val = 0;    // I_Error ();
    else
        val = 0;    // released this frame

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

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

Фрагмент 5

// PVS-Studio: void Key_Bind_f (void)
// PVS-Studio: client/keys.c

cmd[0] = 0;     // start out with a null string
for (i=2 ; i< c ; i++)
{
    strcat (cmd, Cmd_Argv(i));
    if (i != (c-1))
        strcat (cmd, " ");
}

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

if (c != 2 && c != 3)
{
    Con_Printf ("bind <key> [command] : attach a command to a key\n");
    return;
}
if (c == 2)
{
    // ...
    return;
}

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

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

Фрагмент 6

// PVS-Studio: int Sbar_ColorForMap (int m)
// PVS-Studio: client/sbar.c

return m < 128 ? m + 8 : m + 8;

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

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

Фрагмент 7

// PVS-Studio: void CL_StartUpload (byte *data, int size)
// PVS-Studio: client/cl_parse.c

upload_data = malloc(size);
memcpy(upload_data, data, size);

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

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

Фрагмент 8

// PVS-Studio: void CL_ParseBeam (model_t *m)
// PVS-Studio: client/cl_tent.c

if (b->entity == ent)
{
    b->entity = ent;
    // ...
}

// PVS-Studio: void Sbar_SortTeams (void)
// PVS-Studio: client/sbar.c

if (j == scoreboardteams) { // must add him
    j = scoreboardteams++;

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

V1048 The variable was assigned the same value.

Фрагмент 9

// PVS-Studio: void Info_SetValueForStarKey (/* ... */)
// PVS-Studio: client/common.c

c &= 127;
if (c < 32 || c > 127)
    continue;

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

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

Фрагмент 10

// PVS-Studio: void M_Keys_Key (int k)
// PVS-Studio: client/menu.c

if (bind_grab)
{  
    // ...
    if (k == K_ESCAPE)
    {
        bind_grab = false;
    }
    else if (k != '`')
    {
        // ...
    }
    bind_grab = false;
}

Как пелось в знаменитой песне группы 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

// PVS-Studio: client/r_edge.c

edge_t  edge_sentinel;

// PVS-Studio: void R_ScanEdges (void)
// PVS-Studio: client/r_edge.c

// FIXME: do we need this now that we clamp x in r_draw.c?
edge_sentinel.u = 2000 << 24;       // make sure nothing sorts past this

// PVS-Studio: client/r_shared.h

// !!! if this is changed, it must be changed in asm_draw.h too !!!
typedef struct edge_s
{
    fixed16_t       u;
    // ...
} edge_t;

Комментарии говорят сами за себя, но всё же источник данных побитовых операций покрыт тайной. Становится не легче, если взять в расчёт тип, к которому приводится результат. Он определён как 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

// PVS-Studio: void SV_ExtractFromUserinfo (client_t *cl)
// PVS-Studio: server/sv_main.c

for (p = newname; (*p == ' ' || *p == '\r' || *p == '\n') && *p; p++) 
    ;

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

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

Фрагмент 13

// PVS-Studio: void SV_Shutdown (void)
// PVS-Studio: server/sv_main.c

if (sv_logfile)
{
    fclose (sv_logfile);
    sv_logfile = NULL;
}

if (sv_fraglogfile)
{
    fclose (sv_fraglogfile);
    sv_logfile = NULL;
}

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

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.

Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Anton Tretyakov. Oh my C! How they wrote code back in the Quake days.