Our website uses cookies to enhance your browsing experience.
Accept
to the top
close form

Fill out the form in 2 simple steps below:

Your contact information:

Step 1
Congratulations! This is your promo code!

Desired license type:

Step 2
Team license
Enterprise license
** By clicking this button you agree to our Privacy Policy statement
close form
Request our prices
New License
License Renewal
--Select currency--
USD
EUR
* By clicking this button you agree to our Privacy Policy statement

close form
Free PVS‑Studio license for Microsoft MVP specialists
* By clicking this button you agree to our Privacy Policy statement

close form
To get the licence for your open-source project, please fill out this form
* By clicking this button you agree to our Privacy Policy statement

close form
I am interested to try it on the platforms:
* By clicking this button you agree to our Privacy Policy statement

close form
check circle
Message submitted.

Your message has been sent. We will email you at


If you do not see the email in your inbox, please check if it is filtered to one of the following folders:

  • Promotion
  • Updates
  • Spam

Webinar: C++ semantics - 06.11

>
>
>
Is Everything Ok with the First Doom?

Is Everything Ok with the First Doom?

Aug 27 2019

Recently the news about porting the first Doom on terminals and ATMs flashed in the net. Knowing from the Wikipedia article how many bugs ordinary players have found in this game, we got interested what else can be detected with static analysis of the source code.

0662_Doom/image1.png

About 8 years ago, we analyzed Doom 3. Just a month or two later, John Carmack's article was released, it described his attitude towards coding and static analysis in general. Now there is a reason to get back to the code of this author. Or rather, to his earlier project.

This is my first pen test, so I ask readers not to judge the article strictly. I didn't find any particularly interesting errors in the project, but I wanted to start from some point, and the Doom project seemed like a very suitable project for this.

Doom

Almost everyone knows about the Doom game. It's impossible to overestimate how much this game has contributed to the gaming industry when it appeared. The game has become a cult. People tried porting it to so many platforms: Windows, Linux, and in addition to common ones - AppleWatch, AppleTV, chainsaws, piano and many others.

Unfortunately, the initial source code isn't open source, so I took a port on Linux from the GitHub and checked it with the PVS-Studio analyzer of the version 7.03. We all have our own entertainment. Someone ports Doom to specific platforms. As for us, we check various open projects. Including the old ones. For example, we checked Word 1.1 and the first C++ compiler Cfront. It doesn't make any practical sense, but it's interesting.

Too Many Conditions

In the analyzer, there is a wonderful diagnostic that seems simple and straightforward at a first glance. Perhaps this is the reason why people sometimes don't even perceive warnings about always true/false conditions. Although these warnings let us find some sapid errors (example).

In this case, the error is non-essential. Or rather, it is not even an error at all, but an additional bet-hedging.

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

The first check weeds out all values of the delta variable that lie in the range [-64..64]. The second check weeds out all values of the delta variable, greater than 64.

Accordingly, when checking the third condition, the delta variable in any case will be less than -64. With all other possible values, the function won't be running by this point. That's why the analyzer issues the warning, that the condition is always true.

Authors of the code could have omitted the last check and immediately perform:

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

Accordingly, the caller code of the I_Error function is never executed. The analyzer warns us about it with another diagnostic message:

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

Friend or Enemy?

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

This error has been constantly following C developers for a long time: the attempt to compare a variable of the enum type with a named constant from another enumeration. Due to the lack of types control, a developer has to keep all the enumerations in mind, which certainly becomes a difficulty with the growth of the project. To solve it, one has to be very attentive. But do developers often look into header files after each edit or when writing new code and consistently check the constant presence in the relevant enumeration?

By the way, with the introduction of enum class, the situation is gradually getting straight.

Interesting Comparison

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

This is the case when the code isn't often checked, resulting in weird situations. Let's try to analyze this tiny piece of function, not using anything but our own eyes. Only code review, only hardcore!

What do we see? Somewhere in the middle of the function, a variable is checked for null. Looks pretty usual. But what do you think is commercial? If you think it's a constant, you're right. You can see its definition in the previous piece of code.

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

To be honest, this code baffles me. Probably, it lacks the comparison of the constant with a variable.

Half-error

#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);
    }
  }
  ....
}

The analyzer warns us about an array index out of bounds. We need to figure it out.

Let's see how the alphSwitchList array is declared. In terms of this article, it'll be inappropriate to cite an array, initialized by 41 elements, so I'll leave only the first and last elements.

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

However, there is no real error here again, and it is rather the analyzer's false positive. The tool couldn't puzzle out what was the matter. The point is that the loop will stop at the last terminal array element and an array index out of bounds won't happen.

However, the code and usage of the MAXSWITCHES constant (which is 50) looks rather suspicious and quite unreliable.

Storing Pointers as Temporary Variables

The following code is not necessarily incorrect, but rather dangerous.

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

It's hard to tell whether mfloorclip and mceilingclip global variables are used somewhere outside the R_DrawVisSprite function. If not, the code will still work, even being written in a bad style. If yes, we have a serious error here, as variables will store pointers to no-existing buffers, created on the stack.

Undefined Behavior

The Doom project was ported to a great number of platforms. And there is a great suspicion that the code below will give different results depending on the compiler, settings, platform.

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

There are also other places:

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

Faulty Refactoring

How many times do we need to rewrite the code to make it perfect? Of course, there is no definite answer. Unfortunately, when rewriting the code, it might not only improve, but also get worse. This seems to be an example of this situation:

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

What's wrong with that? To answer this question, let's see how mousebuttons and joybuttons are declared.

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

The problem is that when arrays are nullified, pointer sizes, not array sizes in bytes are used. There may be several outcomes depending on the size of pointers and enumerations:

  • an array wasn't filled completely, the remaining part was left uninitialized;
  • the memory after this array was nullified;
  • the array was nullified perfectly.

The latter option is unreachable, as it's impossible to nullify two different-length arrays, using one and the same value (pointer size).

Most likely, initially developers were working with arrays, and then decided to use pointers, which led to this. In other words, it's very likely that the error is introduced when refactoring the code. Probably this error should be fixed as follows:

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

Faulty Loop

I suggest that you check out this fragment of code.

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

In the loop, the variable player->pendingweapon isn't assigned the value wp_nochange anywhere. Accordingly, the loop will perform only one iteration.

Another Error

Try to figure out yourself what is wrong with this function.

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]);
  }
}

I'll insert this nice picture here so that you couldn't immediately see the answer beforehand.

0662_Doom/image2.png

Did you manage to figure out what's wrong with this code? The problem is in the constant commercial. Yes, that constant again. It is difficult to say whether this can be called an error or not.

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

Dessert

I left the most interesting error (in my opinion) for last. Let's get straight to the code.

#define SCREENWIDTH 320
void F_BunnyScroll (void)
{
  int scrolled;
  ....
  scrolled = ....; /* Evaluations related to  
  a global variable aren't interesting for us. */
  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);
  }
  ....
}

What can we see here? The scrolled variable before calling the function will lie in the range [0; 320], its sum with the loop counter will have the range: [0; 640]. Then comes one of two calls.

  • The sum is < 320 meaning that the formal parameter is in the range [0; 319];
  • Otherwise, we'll subtract the value 320 from the range [320; 640] and get [0; 320].

Let's see how the callee function handles this argument:

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

Here the array is accessed using the index, which can be in one of the ranges that we got above. So what do we get? An array of 319 elements, and in one case an index gets out of bounds? Everything is MUCH more tangled! Here's columnofs:

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

There are cases when an array index gets out of bounds for one or two elements - in most cases this might not affect the program's work. But here the index might get almost in the otherworldly dimension. Perhaps, such situation happened due to frequent rewriting or may be because of something else. Anyway, even a very attentive person could have missed this during the 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

Conclusion

Doom has made a tremendous contribution to the gaming industry and still has a bunch of fans and adorers. To all effects and purposes, I was unable to find buttloads of epic bugs during the code analysis. Anyway, I think you were interested in looking at the code of this project with me. Thank you for your attention. Don't hesitate to try checking your code using PVS-Studio, if you haven't done it before. Even if you've done some experiments before, there are many reasons to try it again. Because the analyzer keeps developing very fast.

Popular related articles


Comments (0)

Next comments next comments
close comment form