PVS-Studio Looked into the Red Dead Redemption's Bullet Engine




Nowadays there is no need to implement the physics of objects from scratch for game development because there are a lot of libraries for this purpose. Bullet was actively used in many AAA games, virtual reality projects, various simulations and machine learning. And it is still used, being, for example, one of the Red Dead Redemption and Red Dead Redemption 2 engines. So why not check the Bullet with PVS-Studio to see what errors static analysis can detect in such a large-scale physics simulation project.

Picture 4

This library is freely distributed, so everyone can use it in their own projects if they wish. In addition to Red Dead Redemption, this physics engine is also used in the film industry to create special effects. For example, it was used in the shooting of Guy Ritchie's "Sherlock Holmes" to calculate collisions.

If this is the first time you meet an article where PVS-Studio checks projects, I will make a small digression. PVS-Studio is a static code analyzer that helps you find errors, defects and potential vulnerabilities in the source code of C, C++, C#, Java programs. Static analysis is a kind of automated code review process.

Warm-up

Example 1:

Let's start with a funny mistake:

V624 There is probably a misprint in '3.141592538' constant. Consider using the M_PI constant from <math.h>. PhysicsClientC_API.cpp 4109

B3_SHARED_API void b3ComputeProjectionMatrixFOV(float fov, ....)
{
  float yScale = 1.0 / tan((3.141592538 / 180.0) * fov / 2);
  ....
}

A small typo in the Pi value (3,141592653...). The 7th digit in the fractional part is missing - it must be equal to 6.

Picture 1

Perhaps, an error in the ten millionth fraction after the decimal point will not lead to any significant consequences, but still you should use the already existing library constants which have no typos. There is an M_PI constant for the Pi number from the math.h header.

Copy-paste

Example 2:

Sometimes the analyzer allows you to find the error indirectly. For example, three related arguments halfExtentsX, halfExtentsY, halfExtentsZ are passed into the function here but the latter is not used anywhere in the function. You may notice that the halfExtentsY variable is used twice when calling the addVertex method. So maybe it is a copypaste error and the forgotten argument should be used here.

V751 Parameter 'halfExtentsZ' is not used inside function body. TinyRenderer.cpp 375

void TinyRenderObjectData::createCube(float halfExtentsX,
                                      float halfExtentsY,
                                      float halfExtentsZ,
                                      ....)
{
  ....
  m_model->addVertex(halfExtentsX * cube_vertices_textured[i * 9],
                     halfExtentsY * cube_vertices_textured[i * 9 + 1],
                     halfExtentsY * cube_vertices_textured[i * 9 + 2],
                     cube_vertices_textured[i * 9 + 4],
                     ....);
  ....
}

Example 3:

The analyzer has also detected the following interesting fragment and I will show it first in the initial form.

Picture 11

See this looooooooooong line?

Picture 12

It is very strange that the programmer decided to write such a long condition into one line. But it is not surprising that an error has most likely slipped into it.

The analyzer generated the following warnings on this line.

V501 There are identical sub-expressions 'rotmat.Column1().Norm() < 1.0001' to the left and to the right of the '&&' operator. LinearR4.cpp 351

V501 There are identical sub-expressions '0.9999 < rotmat.Column1().Norm()' to the left and to the right of the '&&' operator. LinearR4.cpp 351

If we write it all down in a clear "tabular" form, we can see that all the same checks apply to Column1. The last two comparisons show that there are Column1 and Column2. Most likely, the third and fourth comparisons should have checked the value of Column2.

   Column1().Norm() < 1.0001 && 0.9999 < Column1().Norm()
&& Column1().Norm() < 1.0001 && 0.9999 < Column1().Norm()
&&(Column1() ^ Column2()) < 0.001 && (Column1() ^ Column2()) > -0.001
In this form, the same comparisons become much more noticeable.

Example 4:

Error of the same kind:

V501 There are identical sub-expressions 'cs.m_fJacCoeffInv[0] == 0' to the left and to the right of the '&&' operator. b3CpuRigidBodyPipeline.cpp 169

float m_fJacCoeffInv[2];      
static inline void b3SolveFriction(b3ContactConstraint4& cs, ....)
{
  if (cs.m_fJacCoeffInv[0] == 0 && cs.m_fJacCoeffInv[0] == 0)
  {
    return;
  }
  ....
}

In this case, one and the same array element is checked twice. Most likely, the condition must have looked like this: cs.m_fJacCoeffInv[0] == 0 && cs.m_fJacCoeffInv[1] == 0. This is a classic example of a copy-paste error.

Example 5:

It was also discovered that there was such a defect:

V517 The use of 'if (A) {...} else if (A) {...}' pattern was detected. There is a probability of logical error presence. Check lines: 79, 112. main.cpp 79

int main(int argc, char* argv[])
{
  ....
  while (serviceResult > 0)
  {
    serviceResult = enet_host_service(client, &event, 0);
    if (serviceResult > 0)
    {
      ....
    }
    else if (serviceResult > 0)
    {
      puts("Error with servicing the client");
      exit(EXIT_FAILURE);
    }
    ....
  }
  ....
}

The function enet_host_service, the result of which is assigned to serviceResult, returns 1 in case of successful completion and -1 in case of failure. Most likely, the else if branch should have reacted to the negative value of serviceResult, but the check condition was duplicated. Probably it is also a copy-paste error.

There is a similar warning of the analyzer, but there is no point in looking at it more closely in this article.

V517 The use of 'if (A) {...} else if (A) {...}' pattern was detected. There is a probability of logical error presence. Check lines: 151, 190. PhysicsClientUDP.cpp 151

Over the top: exceeding array boundaries

Example 6:

One of the unpleasant errors to search for is the array overrun. This error often occurs because of a complex indexing in a loop.

Here, in the loop condition, the dofIndex variable''s upper limit is 128 and dof''s is 4 inclusive. But m_desiredState also contains only 128 items. As a result, the [dofIndex+dof] index may cause an array overrun.

V557 Array overrun is possible. The value of 'dofIndex + dof' index could reach 130. PhysicsClientC_API.cpp 968

#define MAX_DEGREE_OF_FREEDOM 128 
double m_desiredState[MAX_DEGREE_OF_FREEDOM];

B3_SHARED_API int b3JointControl(int dofIndex,
                                 double* forces,
                                 int dofCount, ....)
{
  ....
  if (   (dofIndex >= 0)
      && (dofIndex < MAX_DEGREE_OF_FREEDOM )
      && dofCount >= 0
      && dofCount <= 4)
  {
    for (int dof = 0; dof < dofCount; dof++)
    {
      command->m_sendState.m_desiredState[dofIndex+dof] = forces[dof];
      ....
    }
  }
  ....
}

Example 7:

A similar error but now it is caused by summing up not when indexing an array but in a condition. If the file has a name with maximal length, the terminal zero will be written outside the array (Off-by-one Error). Of course, the len variable will be equal to MAX_FILENAME_LENGTH only in exceptional cases, but it doesn't eliminate the error but simply makes it rare.

V557 Array overrun is possible. The value of 'len' index could reach 1024. PhysicsClientC_API.cpp 5223

#define MAX_FILENAME_LENGTH MAX_URDF_FILENAME_LENGTH 1024
struct b3Profile
{
  char m_name[MAX_FILENAME_LENGTH];
  int m_durationInMicroSeconds;
};

int len = strlen(name);
if (len >= 0 && len < (MAX_FILENAME_LENGTH + 1))
{
  command->m_type = CMD_PROFILE_TIMING;
  strcpy(command->m_profile.m_name, name);
  command->m_profile.m_name[len] = 0;
}

Measure it once, cut it seven times

Example 8:

In cases when you need to use the result of some function's work many times or use a variable which requires to pass through the whole chain of calls to get access to , you should use temporary variables for optimization and better code readability. The analyzer has found more than 100 places in the code where you can make such a correction.

V807 Decreased performance. Consider creating a pointer to avoid using the 'm_app->m_renderer->getActiveCamera()' expression repeatedly. InverseKinematicsExample.cpp 315

virtual void resetCamera()
{
  ....
  if (....)
  {
    m_app->m_renderer->getActiveCamera()->setCameraDistance(dist);
    m_app->m_renderer->getActiveCamera()->setCameraPitch(pitch);
    m_app->m_renderer->getActiveCamera()->setCameraYaw(yaw);
    m_app->m_renderer->getActiveCamera()->setCameraPosition(....);
  }
}

The same call chain is used many times here and can be replaced with a single pointer.

Example 9:

V810 Decreased performance. The 'btCos(euler_out.pitch)' function was called several times with identical arguments. The result should possibly be saved to a temporary variable, which then could be used while calling the 'btAtan2' function. btMatrix3x3.h 576

V810 Decreased performance. The 'btCos(euler_out2.pitch)' function was called several times with identical arguments. The result should possibly be saved to a temporary variable, which then could be used while calling the 'btAtan2' function. btMatrix3x3.h 578

void getEulerZYX(....) const
{
  ....
  if (....)
  {
    ....
  }
  else
  {
    ....
    euler_out.roll  = btAtan2(m_el[2].y() / btCos(euler_out.pitch),
                              m_el[2].z() / btCos(euler_out.pitch));
    euler_out2.roll = btAtan2(m_el[2].y() / btCos(euler_out2.pitch),
                              m_el[2].z() / btCos(euler_out2.pitch));
    euler_out.yaw  =  btAtan2(m_el[1].x() / btCos(euler_out.pitch),
                              m_el[0].x() / btCos(euler_out.pitch));
    euler_out2.yaw =  btAtan2(m_el[1].x() / btCos(euler_out2.pitch),
                              m_el[0].x() / btCos(euler_out2.pitch));

  }
  ....
}

In this case, you can create two variables and save the values returned by the btCos function for euler_out.pitch and euler_out2.pitch into them instead of calling the function four times for each argument.

Leak

Example 10:

A lot of errors of the following kind were detected in the project:

V773 Visibility scope of the 'importer' pointer was exited without releasing the memory. A memory leak is possible. SerializeSetup.cpp 94

void SerializeSetup::initPhysics()
{
  ....
  btBulletWorldImporter* importer = new btBulletWorldImporter(m_dynamicsWorld);
  ....
 
  fclose(file);

  m_guiHelper->autogenerateGraphicsObjects(m_dynamicsWorld);
}

Memory has not been released from the importer pointer here. This may result in a memory leak. And for the physical engine it may be a bad trend. To avoid a leak, it is enough to add delete importer after the variable becomes unnecessary. But, of course, it is better to use smart pointers.

C++ lives by its own code

Example 11:

The next error appears in the code because C++ rules do not always coincide with mathematical rules or "common sense". Will you notice where this small code fragment contains an error?

btAlignedObjectArray<btFractureBody*> m_fractureBodies;

void btFractureDynamicsWorld::fractureCallback()
{
  for (int i = 0; i < numManifolds; i++)
  {
    ....
    int f0 = m_fractureBodies.findLinearSearch(....);
    int f1 = m_fractureBodies.findLinearSearch(....);

    if (f0 == f1 == m_fractureBodies.size())
      continue;
    ....
  }
....
}

The analyzer generates the following warning:

V709 Suspicious comparison found: 'f0 == f1 == m_fractureBodies.size()'. Remember that 'a == b == c' is not equal to 'a == b && b == c'. btFractureDynamicsWorld.cpp 483

It would appear that the condition checks that f0 is equal to f1 and is equal to the number of items in m_fractureBodies. It seems that this comparison should have checked whether f0 and f1 are located at the end of the m_fractureBodies array, since they contain the object position found by the findLinearSearch() method. But in fact, this expression turns into a check to see if f0 and f1 are equal to m_fractureBodies.size() and then a check to see if m_fractureBodies.size() is equal to the result f0 == f1. As a result, the third operand here is compared to 0 or 1.

Beautiful mistake! And, fortunately, quite rare. So far, we have only met it in two open source projects, and it is interesting that all of them were game engines.

Example 12:

When working with strings, it is often better to use the features provided by the string class. So, for the next two cases it is better to replace strlen(MyStr.c_str()) and val = "" with MyStr.length() and val.clear(), respectively.

V806 Decreased performance. The expression of strlen(MyStr.c_str()) kind can be rewritten as MyStr.length(). RobotLoggingUtil.cpp 213

FILE* createMinitaurLogFile(const char* fileName,
                            std::string& structTypes,
                            ....)
{
  FILE* f = fopen(fileName, "wb");
  if (f)
  {
    ....
    fwrite(structTypes.c_str(), strlen(structTypes.c_str()), 1, f);
    ....
  }
  ....
}

V815 Decreased performance. Consider replacing the expression 'val = ""' with 'val.clear()'. b3CommandLineArgs.h 40

void addArgs(int argc, char **argv)
{
  ....
  std::string val;
  ....
  val = "";
  ....
}

There were other warnings, but I think we can stop here. As you see, static code analysis can detect a wide range of various errors.

It is interesting to read about one-time project checks, but it is not the proper way to use static code analyzers. And we will speak about it below.

Errors found before us

It was interesting to try to find bugs or defects which have already been fixed but which a static analyzer could detect in the light of the recent article "Errors which are not found by static code analysis because it is not being used".

Picture 2

There were not many pull requests in the repository and many of them are related to the internal logic of the engine. But there were also errors that the analyzer could detect.

Example 13:

char m_deviceExtensions[B3_MAX_STRING_LENGTH];

void b3OpenCLUtils_printDeviceInfo(cl_device_id device)
{
  b3OpenCLDeviceInfo info;
  b3OpenCLUtils::getDeviceInfo(device, &info);
  ....
  if (info.m_deviceExtensions != 0)
  {
    ....
  }
}

The comment for the request says that you needed to check the array for the fact that it was not empty, but instead a meaningless pointer check was performed, which always returned true. This is what PVS-Studio's warning about the original check tells you:

V600 Consider inspecting the condition. The 'info.m_deviceExtensions' pointer is always not equal to NULL. b3OpenCLUtils.cpp 551

Example 14:

Can you find out what the problem is with the next function?

inline void Matrix4x4::SetIdentity()
{
  m12 = m13 = m14 = m21 = m23 = m24 = m13 = m23 = m41 = m42 = m43 = 0.0;
  m11 = m22 = m33 = m44 = 1.0;
}

The analyzer generates the following warnings:

V570 The same value is assigned twice to the 'm23' variable. LinearR4.h 627

V570 The same value is assigned twice to the 'm13' variable. LinearR4.h 627

Repeated assignments in this form of recording are difficult to track with the naked eye and, as a result, some of the matrix elements did not get the initial value. This error was corrected by the tabular form of assignment recording:

m12 = m13 = m14 =
m21 = m23 = m24 =
m31 = m32 = m34 =
m41 = m42 = m43 = 0.0;

Example 15:

The following error in one of the conditions of the btSoftBody function::addAeroForceToNode() led to an evident bug. According to the comment in the pull request, the forces were applied to the objects from the wrong side.

struct eAeroModel
{
  enum _
  {
    V_Point,             
    V_TwoSided,
    ....
    END
  };
};

void btSoftBody::addAeroForceToNode(....)
{
  ....
  if (....)
  {
    if (btSoftBody::eAeroModel::V_TwoSided)
    {
      ....
    }
    ....
  }
....
}

PVS-Studio could also find this error and generate the following warning:

V768 The enumeration constant 'V_TwoSided' is used as a variable of a Boolean-type. btSoftBody.cpp 542

Fixed check looks like this:

if (m_cfg.aeromodel == btSoftBody::eAeroModel::V_TwoSided)
{
  ....
}

Instead of equivalence of an object's property to one of the enumerators, the V_TwoSided enumerator itself was checked.

It's clear that I didn't look at all the pull-requests, because that wasn't the point. I just wanted to show you that regular use of a static code analyzer can detect errors at the very early stage. This is the right way to use static code analysis. Static analysis must be built into the DevOps process and be the primary bug filter. All this is well described in the article "Introduce Static Analysis in the Process, Don't Just Search for Bugs with It".

Conclusion

Picture 6

Judging by some pull-requests, a project is sometimes checked through various code analysis tools but corrections are made not gradually but in groups and with large intervals. In some requests, the comment indicates that the changes were made only to suppress warnings. This approach to using analysis significantly reduces its usefulness because it is the regular checks of the project that allow you to correct errors right away rather than waiting for any explicit bugs to appear.

Follow us and subscribe to our social media accounts and channels: Instagram, Twitter, Facebook, Telegram. We'd love to be with you wherever you are and to keep you on the loop.



Use PVS-Studio to search for bugs in C, C++, C# and Java

We offer you to check your project code with PVS-Studio. Just one bug found in the project will show you the benefits of the static code analysis methodology better than a dozen of the articles.

goto PVS-Studio;


Bugs Found

Checked Projects
346
Collected Errors
13 188