Andrey Karpov

Nov 25 2011

Tags:

#Cpp #GameDev

PVS-Studio: analyzing Doom 3 code

Nov 25 2011

Author: Andrey Karpov

Fragment 1. Suspicious condition
Fragment 2. Suspicious loop
Fragment 3. One more suspicious loop
Fragment 4. Undefined behavior
Fragment 5. Suspicious array clearing
Fragment 6. One more instance of suspicious array clearing
Fragment 7. Hello, Copy-Paste
Fragment 8. Suspicious pointer handling
Fragment 9. Suspicious string format
Fragment 10. Confusing code

The id Software company possesses a PVS-Studio license. However, we decided to test the source codes of Doom 3 that have been recently laid out on the Internet. The result is the following: we managed to find just few errors, but still they are there. I think it can be explained by the following fact.

A part of the Doom 3 code is still in use, and perhaps developers have fixed errors there. And another part of the code is obsolete and not used now. Most likely, the suspicious code fragments have been found in this very part.

For those who want to know more on the subject, in this article we cite code fragments the PVS-Studio analyzer gave warnings for. As usually, let me remind you that I will speak only on some of the warnings, while the other project fragments require us to know the program's structure, so I did not examine them.

The source code of Doom3 was published on GitHub and official FTP of the company under the GPL v3 license. I used the PVS-Studio 4.39 analyzer for analysis.

Fragment 1. Suspicious condition

#define BIT( num ) ( 1 << ( num ) )
const int BUTTON_ATTACK = BIT(0);
void idTarget_WaitForButton::Think( void ) {
  ...
  if ( player &&
      ( !player->oldButtons & BUTTON_ATTACK ) &&
      ( player->usercmd.buttons & BUTTON_ATTACK ) ) {
  ...
}

PVS-Studio diagnostic message: V564 The '&' operator is applied to bool type value. You've probably forgotten to include parentheses or intended to use the '&&' operator. Game target.cpp 257

Note the fragment "!player->oldButtons & BUTTON_ATTACK". The developers intended to check here that the least significant bit is equal to 0. But the priority of the '!' operator is higher than that of the '&' operator. It means that the condition works according to the following algorithm:

(!player->oldButtons) & 1

It turns out that the condition is true only when all the bits equal zero. This is the correct code:

if ( player &&
    ( ! ( player->oldButtons & BUTTON_ATTACK ) ) &&
    ( player->usercmd.buttons & BUTTON_ATTACK ) ) {

Fragment 2. Suspicious loop

void idSurface_Polytope::FromPlanes(...)
{
  ...
  for ( j = 0; j < w.GetNumPoints(); j++ ) {
    for ( k = 0; k < verts.Num(); j++ ) {
      if ( verts[k].xyz.Compare(w[j].ToVec3(),
                                POLYTOPE_VERTEX_EPSILON ) ) {
        break;
      }
    }
    ...
  }
  ...
}

PVS-Studio diagnostic message: V533 It is likely that a wrong variable is being incremented inside the 'for' operator. Consider reviewing 'j'. idLib surface_polytope.cpp 65

The nested loop increments the 'j' variable instead of 'k'. The 'k' variable is not incremented at all. Results of such a loop cannot be predicted. This is the correct code:

for ( k = 0; k < verts.Num(); k++ ) {

Fragment 3. One more suspicious loop

bool idMatX::IsOrthonormal( const float epsilon ) const {
  ...
  for ( int i = 0; i < numRows; i++ ) {
    ...
    for ( i = 1; i < numRows; i++ ) {
      ...
    }
    if ( idMath::Fabs( sum ) > epsilon ) {
      return false;
    }
  }
  return true;
}

PVS-Studio diagnostic message: V535 The variable 'i' is being used for this loop and for the outer loop. idLib matrix.cpp 3128

One and the same variable is used to arrange both the outer loop and the nested loop. The both loops have the same loop end condition: i < numRows. It turns out that the outer loop always performs only one iteration. To fix the code you may use another variable in the nested loop.

Fragment 4. Undefined behavior

int idFileSystemLocal::ListOSFiles(...)
{
  ...
  dir_cache_index = (++dir_cache_index) % MAX_CACHED_DIRS;
  ...
}

PVS-Studio diagnostic message: V567 Undefined behavior. The 'dir_cache_index' variable is modified while being used twice between sequence points. TypeInfo filesystem.cpp 1877

The "dir_cache_index" variable is changed twice in one sequence point. It does not matter that the prefix increment is used and, theoretically, nothing prevents the compiler from creating the following code:

A = dir_cache_index;
A = A + 1;
B = A % MAX_CACHED_DIRS;
dir_cache_index = B;
dir_cache_index = A;

Of course, the expression is most likely calculated as it should be. But you cannot be absolutely sure because the result is determined by the type and version of the compiler as well as optimization settings. This is the correct code:

dir_cache_index = (dir_cache_index + 1) % MAX_CACHED_DIRS;

Fragment 5. Suspicious array clearing

void idMegaTexture::GenerateMegaMipMaps() {
  ...
  byte *newBlock = (byte *)_alloca( tileSize );
  ...
  memset( newBlock, 0, sizeof( newBlock ) );
  ...
}

PVS-Studio diagnostic message: V579 The memset function receives the pointer and its size as arguments. It is possibly a mistake. Inspect the third argument. DoomDLL megatexture.cpp 542

Only part of the 'newBlock' array is filled with nulls. Most likely, it is an incorrect situation. It seems to me that this fragment looked like this earlier:

byte newBlock[ CONST_ARRAY_SIZE ];
...
memset( newBlock, 0, sizeof( newBlock ) );

Then the requirements changed and the size of the 'newBlock' array started to change too, but the programmers forgot about the function clearing it. This is the correct code:

memset( newBlock, 0, tileSize );

Fragment 6. One more instance of suspicious array clearing

void Sys_GetCurrentMemoryStatus( sysMemoryStats_t &stats ) {
  ...
  memset( &statex, sizeof( statex ), 0 );
  ...
}

PVS-Studio diagnostic message: V575 The 'memset' function processes '0' elements. Inspect the third argument. DoomDLL win_shared.cpp 177

Arguments are mixed up when calling the 'memset' function. The function clears 0 bytes. By the way, this error is rather widely-spread. I came across it in many projects.

This is the correct function call:

memset( &statex, 0, sizeof( statex ) );

Fragment 7. Hello, Copy-Paste

void idAASFileLocal::DeleteClusters( void ) {
  ...
  memset( &portal, 0, sizeof( portal ) );
  portals.Append( portal );

  memset( &cluster, 0, sizeof( portal ) );
  clusters.Append( cluster );
}

PVS-Studio diagnostic message: V512 A call of the 'memset' function will lead to underflow of the buffer '& cluster'. DoomDLL aasfile.cpp 1312

Note the similarity between the two upper and the two lower code lines. The last two lines must have been written through Copy-Paste. This is the thing that caused the error here. The programmer forgot to replace the word 'portal' with the word 'cluster' in one place. As a result, only a part of the structure is cleared. This is the correct code:

memset( &cluster, 0, sizeof( cluster ) );

There were some other incompletely cleared arrays in the code, but they are not of much interest.

Fragment 8. Suspicious pointer handling

void idBrushBSP::FloodThroughPortals_r(idBrushBSPNode *node, ...)
{
  ...
  if ( node->occupied ) {
    common->Error( "FloodThroughPortals_r: node already occupied\n" );
  }
  if ( !node ) {
    common->Error( "FloodThroughPortals_r: NULL node\n" );
  }
  ...
}

PVS-Studio diagnostic message: V595 The 'node' pointer was utilized before it was verified against nullptr. Check lines: 1421, 1424. DoomDLL brushbsp.cpp 1421

The 'node' pointer is dereferenced first: node->occupied. And then it is suddenly checked if it is not equal to NULL. This is a very suspicious code. I do not know how to fix it because I do not know the logic of the function operation. Perhaps it is just enough to write it that way:

if ( node && node->occupied ) {

Fragment 9. Suspicious string format

struct gameVersion_s {
  gameVersion_s( void )
  {
    sprintf(string, "%s.%d%s %s %s",
            ENGINE_VERSION, BUILD_NUMBER, BUILD_DEBUG,
            BUILD_STRING, __DATE__, __TIME__ );
  }
  char string[256];
} gameVersion;

PVS-Studio diagnostic message: V576 Incorrect format. A different number of actual arguments is expected while calling 'sprintf' function. Expected: 7. Present: 8. Game syscvar.cpp 54

What is suspicious about this is that the '__TIME__' argument is not used in any way.

Fragment 10. Confusing code

There are several code fragments which seem to work properly but look strange. I will cite only one example of this code.

static bool R_ClipLineToLight(..., const idPlane frustum[4], ...)
{
  ...
  for ( j = 0 ; j < 6 ; j++ ) {
    d1 = frustum[j].Distance( p1 );
    d2 = frustum[j].Distance( p2 );
    ...
  }
  ...
}

As a tip, the programmer has written that the 'frustum' array consists of 4 items. But there are 6 items being processed. If you look at the 'R_ClipLineToLight' call, the array there consists of 6 items. That is, everything must work as intended but the code makes you feel uneasy about it.

What other errors and defects are concerned, you can see them launching the PVS-Studio analyzer. By the way, taking the opportunity, I want to give my best regards to John Carmack and tell him that we will soon fix the flaw that does not allow the id Software company to use PVS-Studio at full.

This flaw is the analyzer's low operation speed. Taking into account the large size of the source code the company deals with, this is a crucial limitation. In PVS-Studio 4.50 that will be released in this year, you will be able to use Clang as a preprocessor instead of the Visual C++ preprocessor. This will provide a significant speed-up of project analysis. For example, the Doom 3 source codes are checked within 26 minutes when using the Visual C++ preprocessor. With the Clang preprocessor, it will be 16 minutes. Well, this example is not very good because the analysis speed boost will be much more significant for most other projects.

But for now you will have to use the Visual C++ preprocessor by default - Clang still has some issues of incompatibility and defects concerning the Windows-platform. So, only 80% of projects are checked successfully with the new preprocessor.

#Cpp #GameDev