Андрей Коростин

27 Авг 2019

Теги:

#Cpp #GameDev

Все ли в порядке с первым Doom

27 Авг 2019

Автор: Андрей Коростин

Doom
Слишком много условий
Свой или чужой?
Интересное сравнение
Полуошибка
Сохранение указателей на временные переменные
Undefined Behavior
Неудачный рефакторинг
Неудачный цикл
Еще одна ошибка
Десерт
Заключение

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

Примерно 8 лет назад мы подвергли анализу Doom 3 и после этого буквально через месяц или два вышла статья Джона Кармака, в которой было описано его отношение к написанию кода и статическому анализу в целом. Сейчас есть повод ещё раз вернуться к коду этого автора. Вернее, к его более раннему проекту.

Это моя первая проба пера, поэтому прошу читателей не судить статью строго. Особенно интересных ошибок в проекте я не нашёл, но ведь надо с чего-то начинать, и проект Doom показался очень хорошим проектом для этого.

Doom

Об игре Doom знают практически все. Невозможно переоценить, как много эта игра привнесла в игровую индустрию в момент своего появления. Игра стала культовой. На какие платформы ее только не пытались портировать: Windows, Linux, и помимо обычных - AppleWatch, AppleTV, бензопилы, пианино и многие другие.

К сожалению, изначальный исходный код не находится в открытом доступе, поэтому я взял порт на Linux, располагающийся на GitHub, и проверил его анализатором PVS-Studio версии 7.03. У каждого свои развлечения. Кто-то портирует Doom на специфические платформы, а мы проверяем различные открытые проекты. В том числе и старые. Например, мы проверяли Word 1.1 и первый C++ компилятор Cfront. В этом нет практического смысла, но зато интересно.

Слишком много условий

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

В данном случае ошибка несущественна. Вернее, это даже вообще не ошибка, а излишняя перестраховка.

int ExpandTics (int low)
{
  int delta;
  delta = low - (maketic&0xff);

  if (delta >= -64 && delta <= 64)
    return (maketic&~0xff) + low;
  if (delta > 64)
    return (maketic&~0xff) - 256 + low;
  if (delta < -64)
    return (maketic&~0xff) + 256 + low;

  I_Error ("ExpandTics: strange value %i at maketic %i",low,maketic);
  return 0;
}

V547 [CWE-571] Expression 'delta < - 64' is always true. d_net.c 130

Первая проверка отсеивает все значения переменной delta, лежащие в диапазоне [-64..64]. Вторая проверка отсеивает все значения переменной delta, больше 64.

Соответственно, при проверке третьего условия, переменная delta в любом случае уже будет меньше минус 64. При всех других возможных значениях, функция к этому моменту уже прекратит свою работу. Именно поэтому анализатор и выдаёт предупреждение, что условие всегда истинно.

Можно было бы не писать последнюю проверку и сразу выполнить:

return (maketic&~0xff) + 256 + low;

Соответственно код, вызывающий функцию I_Error вообще никогда не выполняется, о чём и предупреждает анализатор уже другим диагностическим сообщением:

V779 [CWE-561] Unreachable code detected. It is possible that an error is present. d_net.c 133

Свой или чужой?

typedef enum
{
  ....
  pack_tnt,
  pack_plut,
} GameMission_t;

enum
{
  commercial,
  ....
} gamemode;

void G_DoLoadLevel (void) 
{
  if ((gamemode == commercial)
    ||(gamemode == pack_tnt)
    ||(gamemode == pack_plut))
  {
    ....
  }
}

V556 [CWE-697] The values of different enum types are compared: gamemode == pack_tnt. g_game.c 459

V556 [CWE-697] The values of different enum types are compared: gamemode == pack_plut. g_game.c 460

Эта ошибка преследует С программистов достаточно давно: попытка сравнить переменную типа enum с именованной константой из другого перечисления. Из-за отсутствия контроля типов программист должен все перечисления держать в голове, что, безусловно, имеет определенную сложность с ростом проекта. Это можно решить внимательностью, но часто ли программисты заглядывают в заголовочные файлы после каждой правки или во время написания нового кода и методично проверяют наличие константы в соответствующем перечислении?

Кстати, в языке C++ с появлением enum class ситуация постепенно исправляется.

Интересное сравнение

void WI_drawAnimatedBack(void)
{
  ....
  if (commercial)
    return;
  ....
}

Тот самый случай, когда написанный код редко тестируется, из-за чего могут сложиться странные ситуации. Попробуем проанализировать этот малюсенький кусочек функции, не пользуюсь ничем, кроме собственных глаз. Только code review, только hardcore!

Что мы видим? Где-то в середине функции проверяется на ноль какая-то переменная. Вроде бы ничего необычного. Но как вы думаете, что такое commercial? Если вы считаете, что это константа, вы правы. Вы можете увидеть ее определение в предыдущем фрагменте кода.

V768 [CWE-571] The enumeration constant 'commercial' is used as a variable of a Boolean-type. wi_stuff.c 588

Честно сказать, подобный код ставит меня в тупик. Возможно, пропущено сравнение константы с какой-нибудь переменной.

Полуошибка

#define MAXSWITCHES 50
void P_InitSwitchList(void)
{
  ....
  for (int index = 0, i = 0; i < MAXSWITCHES; i++)
  {
    if (!alphSwitchList[i].episode)
    {
      ....
      break;
    }
    if (alphSwitchList[i].episode <= episode)
    {
      .... = R_TextureNumForName(alphSwitchList[i].name1);
      .... = R_TextureNumForName(alphSwitchList[i].name2);
    }
  }
  ....
}

Анализатор предупреждает нас о выходе за границу массива. Нужно разобраться.

Давайте посмотрим, как же объявлен массив alphSwitchList. Только в рамках данной статьи будет неуместно показывать массив, инициализированный 41-м элементом, поэтому оставлю только первый и последний элемент.

switchlist_t alphSwitchList[] =
{
  {"SW1BRCOM",   "SW2BRCOM", 1},
  ...
  {"\0", "\0", 0}
};

V557 [CWE-119] Array overrun is possible. The value of 'i' index could reach 49. p_switch.c 123

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

Тем не менее, код и использование константы MAXSWITCHES (которая равна значению 50) выглядит весьма подозрительно и как-то ненадёжно.

Сохранение указателей на временные переменные

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

short *mfloorclip;
short *mceilingclip;
void R_DrawSprite (vissprite_t* spr)
{
  short clipbot[SCREENWIDTH];
  short cliptop[SCREENWIDTH];
  ....
  mfloorclip = clipbot;
  mceilingclip = cliptop;
  R_DrawVisSprite (spr, spr->x1, spr->x2);
}

V507 [CWE-562] Pointer to local array 'clipbot' is stored outside the scope of this array. Such a pointer will become invalid. r_things.c 947

V507 [CWE-562] Pointer to local array 'cliptop' is stored outside the scope of this array. Such a pointer will become invalid. r_things.c 948

Сложно сказать, используются ли глобальные переменные mfloorclip и mceilingclip где-то вне функции R_DrawVisSprite. Если нет, то код будет работать, хотя и написан в плохом стиле. А если будут, то перед нами серьезная ошибка, так как переменные будут хранить указатели на уже несуществующие буферы, которые создавались на стеке.

Undefined Behavior

Проект Doom портирован на большее количество платформ. И есть большое подозрение, что код приведённый ниже будет давать разные результаты в зависимости от компилятора, настроек, платформы.

void D_PostEvent (event_t* ev)
{
  events[eventhead] = *ev;
  eventhead = (++eventhead)&(MAXEVENTS-1);
}

V567 [CWE-758] Undefined behavior. The 'eventhead' variable is modified while being used twice between sequence points. d_main.c 153

Есть и другие места:

void D_ProcessEvents (void)
{
  ....
  for ( ; ....; eventtail = (++eventtail)&(MAXEVENTS-1) )
  {
    ....
  }
}

V567 [CWE-758] Undefined behavior. The 'eventtail' variable is modified while being used twice between sequence points. d_main.c 170

void CheckAbort (void)
{
  ....
  for ( ; ....; eventtail = (++eventtail)&(MAXEVENTS-1) ) 
  { 
    ....
  } 
}

V567 [CWE-758] Undefined behavior. The 'eventtail' variable is modified while being used twice between sequence points. d_net.c 464

Неудачный рефакторинг

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

void G_DoLoadLevel (void) 
{
  ....
  memset (mousebuttons, 0, sizeof(mousebuttons)); 
  memset (joybuttons, 0, sizeof(joybuttons));
}

Что здесь не так? Для ответа на этот вопрос посмотрим, как объявлены mousebuttons и joybuttons.

typedef enum {false, true} boolean; 
boolean mousearray[4];
boolean joyarray[5];
boolean* mousebuttons = &mousearray[1];
boolean* joybuttons = &joyarray[1];

V579 [CWE-687] The memset function receives the pointer and its size as arguments. It is possibly a mistake. Inspect the third argument. g_game.c 495

V579 [CWE-687] The memset function receives the pointer and its size as arguments. It is possibly a mistake. Inspect the third argument. g_game.c 496

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

заполнили массив не полностью, а оставшаяся часть осталась неинициализированной;
обнулили память, лежащую после этого массива;
обнулили массив идеально.

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

Скорее всего, изначально разработчики работали с массивами, а потом решили использовать указатели, что и привело к этому. Другим словами высока вероятность, что ошибка была внесена в ходе рефакторинга кода. Скорее всего, чтобы исправить ошибку, следует написать:

memset (mousebuttons, 0, sizeof(mousearray) - sizeof(*mousearray));
memset (joybuttons, 0, sizeof(joyarray) - sizeof(*joyarray));

Неудачный цикл

Предлагаю к рассмотрению следующий кусочек кода.

boolean P_CheckAmmo (player_t* player)
{
  ....
  do {
    if (....)
    {
      player->pendingweapon = wp_plasma;
    }
    else .... if (....)
    {
      player->pendingweapon = wp_bfg;
    }
    else
    {
      player->pendingweapon = wp_fist;
    }
  } while (player->pendingweapon == wp_nochange);
  ....
}

V654 [CWE-834] The condition 'player->pendingweapon == wp_nochange' of loop is always false. p_pspr.c 232

В цикле нет места, где переменной player->pendingweapon присваивалось бы значение wp_nochange. Соответственно, цикл выполнит только одну итерацию.

Еще одна ошибка

Попробуйте самостоятельно определить, что не так в этой функции.

static int NUMANIMS[....] =
{
  sizeof(....)/sizeof(....),
  sizeof(....)/sizeof(....),
  sizeof(....)/sizeof(....)
};
typedef struct
{
  int epsd; // episode # (0-2)
  ....
} wbstartstruct_t;
static wbstartstruct_t *wbs;
void WI_drawAnimatedBack(void)
{
  int       i;
  anim_t*   a;

  if (commercial)
    return;

  if (wbs->epsd > 2)
    return;

  for (i=0 ; i<NUMANIMS[wbs->epsd] ; i++)
  {
    a = &anims[wbs->epsd][i];

    if (a->ctr >= 0)
      V_DrawPatch(a->loc.x, a->loc.y, FB, a->p[a->ctr]);
  }
}

Чтобы вы не увидели ответ раньше времени, пожалуй, сюда вставлю картинку.

Сумели ли вы найти что не так с этим кодом? Проблема заключается в константе commercial. Да, опять та самая константа. Сложно сказать, можно ли это назвать ошибкой или нет.

V779 [CWE-561] Unreachable code detected. It is possible that an error is present. wi_stuff.c 591

Десерт

Самую интересную на мой взгляд ошибочку я оставил напоследок. Давайте без предисловий сразу к коду.

#define SCREENWIDTH 320
void F_BunnyScroll (void)
{
  int scrolled;
  ....
  scrolled = ....; /* Вычисления, связанные 
  с глобальной переменной, нам не интересны. */
  if (scrolled > 320)
    scrolled = 320;
  if (scrolled < 0)
    scrolled = 0;

  for (x=0; x<SCREENWIDTH; x++)
  {
    if (x+scrolled < 320)
      F_DrawPatchCol (...., x+scrolled);
    else
      F_DrawPatchCol (...., x+scrolled - 320);
  }
  ....
}

Что мы здесь можем увидеть? Переменная scrolled перед вызовом функции будет в диапазоне [0; 320], а ее сумма со счетчиком цикла будет иметь диапазон: [0; 640]. Дальше идет один из двух вызовов.

Сумма < 320, значит формальный параметр находится в диапазоне значений [0; 319];
Иначе, вычитаем из диапазона [320; 640] значение 320 и получаем [0; 320].

Посмотрим, как с этим аргументом работает вызываемая функция:

void F_DrawPatchCol (...., int col)
{
  column_t *column;
  ....
  column = .... + LONG(patch->columnofs[col]));
  ....
}

Здесь обращаются к массиву, используя индекс, который может быть в одном из диапазонов, что мы и получили выше. И что же получается? Массив на 319 элементов, и в одном случае мы выходим за границу? Все НАМНОГО интереснее! Вот что такое columnofs:

typedef struct 
{ 
  ....
  int columnofs[8];
} patch_t;

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

V557 [CWE-628] Array overrun is possible. The 'F_DrawPatchCol' function processes value '[0..319]'. Inspect the third argument. Check lines: 621, 668. f_finale.c 621

V557 [CWE-628] Array overrun is possible. The 'F_DrawPatchCol' function processes value '[0..319]'. Inspect the third argument. Check lines: 621, 670. f_finale.c 621

Заключение

Doom внес грандиозный вклад в игровую индустрию и до сих пор имеет кучу фанатов и обожателей. К сожалению, или к радости, мне не удалось найти множество эпичных багов в ходе анализа кода. В любом случае, думаю вам было интересно вместе со мной заглянуть в код этого проекта. Спасибо за внимание. И не забудьте попробовать проверить свой код с помощью PVS-Studio, если ещё не разу этого не делали. И даже если вы уже ставили такие эксперименты, всё равно ещё раз попробуйте. Анализатор развивается очень быстро.

#Cpp #GameDev