Pull to refresh
312.8
PVS-Studio
Static Code Analysis for C, C++, C# and Java

VVVVVV??? VVVVVV!!! :)

Reading time 10 min
Views 2.2K
If you're reading this text, you've either thought that something was wrong with the headline or you've seen the name of a familiar computer game. VVVVVV is an indie platformer game that has stolen the hearts of many players by its pleasant external simplicity and no less pleasant internal complexity. A few days ago, VVVVVV turned 10 years, and the author of the game — Terry Cavanagh — celebrated this holiday by publishing its source code. What mind-boggling things is it hiding? Read the answer in this article.

Рисунок 1

Introduction


Oh, VVVVVV… I remember coming across it shortly after the release and being a big fan of pixel retro games, I was so excited to install it on my computer. I remember my first impressions: «Is that all? Just running around the square rooms?» I thought after a few minutes of playing. I didn't know what was waiting for me at the time. As soon as I got out of the starting location, I found myself in a small but confusing and florid two-dimensional world full of unusual landscapes and pixel artifacts unknown to me.

I got carried away by the game. Eventually, I completely beat the game despite some challenges, like high complexity with skillfully applied game control, for instance — the main character can't jump, but is able to invert the direction of the gravity vector on himself. I have no idea how many times my character died then, but I'm sure the number of deaths is measured in the tens of hundreds. After all, every game has its own unique zest :)

Anyway, let's go back to the source code, posted in honor of the game's anniversary.

At the moment, I'm a developer of the PVS-Studio, which is a static code analyzer for C, C++, C#, and Java. In addition to directly developing, we are also engaged in our product promotion. For us, one of the best ways to do this is to write articles about checking open source projects. Our readers get engaging articles on programming topics, and we get the opportunity to demonstrate the capabilities of PVS-Studio. So when I heard about the opening of the VVVVVV source code, I just couldn't get past it.

In this article, we'll look at some interesting errors found by the PVS-Studio analyzer in the VVVVVV code, and take a detailed look at these errors. Point the gravity vector down and make yourself comfortable — we're just about to start!

Overview of Analyzer Warnings


Warning 1


V512 A call of the 'sprintf' function will lead to overflow of the buffer 'fileSearch'. FileSystemUtils.cpp 307

#define MAX_PATH          260

....

void PLATFORM_migrateSaveData(char *output)
{
  char oldLocation[MAX_PATH];
  char newLocation[MAX_PATH];
  char oldDirectory[MAX_PATH]; 
  char fileSearch[MAX_PATH];

  ....

  /* Same place, different layout. */
  strcpy(oldDirectory, output);

  sprintf(fileSearch, "%s\\*.vvvvvv", oldDirectory);
  
  ....
}

As you can see, the strings fileSearch and oldDirectory are of the same size: 260 characters. After writing the contents of the oldDirectory string in the format string (the third sprintf argument), it will look like:
<i>contents_oldDirectory\*.vvvvvv</i>

This line is 9 characters longer than the original value of oldDirectory. It is this sequence of characters that will be written in fileSearch. What happens if the length of the oldDirectory string is more than 251? The resulting string will be longer than fileSearch could contain, which will lead to violating the array bounds. What data in RAM can be damaged and what result it will lead to is a matter of rhetorical question :)

Warning 2


V519 The 'background' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 1367, 1373. Map.cpp 1373

void mapclass::loadlevel(....)
{
  ....

  case 4: //The Warpzone
    tmap = warplevel.loadlevel(rx, ry, game, obj);
    fillcontent(tmap);
    roomname = warplevel.roomname;
    tileset = 1;
    background = 3;                    // <=
    dwgfx.rcol = warplevel.rcol;
    dwgfx.backgrounddrawn = false;

    warpx = warplevel.warpx;
    warpy = warplevel.warpy;
    background = 5;                    // <=
    if (warpy) background = 4;
    if (warpx) background = 3;
    if (warpx && warpy) background = 5;
    break;

  ....
}

The same variable is assigned a value twice in a row. However, this variable isn't used anywhere between assignments. Which is weird… This sequence may not violate the logic of the program, but such assignments themselves indicate some confusion when writing code. Whether this is a mistake in fact — only the author will be able to say for sure. Although there are more vivid examples of this error in the code:

void Game::loadquick(....)
{
  ....

  else if (pKey == "frames")
  {
    frames = atoi(pText);
    frames = 0;
  }

  ....
}

In this case, it's clear that an error is hiding somewhere either in logic or in redundant assignment. Perhaps, the second line was written temporarily for debugging, and then was just left forgotten. In total, PVS-Studio issued 8 warnings about such cases.

Warning 3


V808 'pKey' object of 'basic_string' type was created but was not utilized. editor.cpp 1866

void editorclass::load(std::string &_path)
{
  ....

  std::string pKey(pElem->Value());

  ....

  if (pKey == "edEntities")
  {
    int i = 0;
    for (TiXmlElement *edEntityEl = pElem->FirstChildElement();
         edEntityEl;
         edEntityEl = edEntityEl->NextSiblingElement())
    {
      std::string pKey(edEntityEl->Value());                         // <=
      //const char* pText = edEntityEl->GetText() ;
      if (edEntityEl->GetText() != NULL)
      {
        edentity[i].scriptname = std::string(edEntityEl->GetText());
      }
      edEntityEl->QueryIntAttribute("x", &edentity[i].x);
      edEntityEl->QueryIntAttribute("y", &edentity[i].y);
      edEntityEl->QueryIntAttribute("t", &edentity[i].t);

      edEntityEl->QueryIntAttribute("p1", &edentity[i].p1);
      edEntityEl->QueryIntAttribute("p2", &edentity[i].p2);
      edEntityEl->QueryIntAttribute("p3", &edentity[i].p3);
      edEntityEl->QueryIntAttribute("p4", &edentity[i].p4);
      edEntityEl->QueryIntAttribute("p5", &edentity[i].p5);
      edEntityEl->QueryIntAttribute("p6", &edentity[i].p6);

      i++;

    }

    EditorData::GetInstance().numedentities = i;
  }

  ....
}

This code is very strange. The analyzer warns about the created but not used variable pKey, but in reality, the problem was more interesting. I intentionally highlighted the line triggered the warning with an arrow, as this function contains more than one string definition with the name pKey. That's right, another such variable is declared inside the for loop. It overlaps the one that's declared outside of the loop.

Thus, if you refer to the value of the pKey string outside the for loop, you'll get the value equal to pElem->Value(), but when doing the same inside the loop, you'll get the value equal to edEntityEl->Value(). Overlapping names is a rather rough error, which might be very difficult to find on your own during code review.

Warning 4


V805 Decreased performance. It is inefficient to identify an empty string by using 'strlen(str) > 0' construct. A more efficient way is to check: str[0] != '\0'. physfs.c 1604

static char *prefDir = NULL;

....

const char *PHYSFS_getPrefDir(const char *org, const char *app)
{
  ....

  assert(strlen(prefDir) > 0);

  ...

  return prefDir;
} /* PHYSFS_getPrefDir */

The analyzer found a fragment for potential micro-optimization. It uses the strlen function to check if the string is empty. This function traverses all string elements and checks each of them for a null-terminator ('\0'). If we get a long string, its each character will be compared with a null-terminator.

But we just need to check that the string is empty! All you need to do is to find out if the first string character is a terminal null. Therefore, to optimize this check inside the assert, it's worth writing:

str[0] != '\0'

That's the recommendation the analyzer gives us. Sure, the call of the strlen function is in condition of the assert macro, therefore it will only be executed in the debugging version, where the speed isn't that important. In the release version, the call of the function and the code will execute fast. Despite this, I wanted to demonstrate what our analyzer can suggest in terms of micro-optimizations.

Warning 5


To demonstrate the essence of another error, I have to cite two code fragments here: the entclass class declaration and its constructor. Let's start with the declaration:

class entclass
{
public:
  entclass();

  void clear();

  bool outside();

public:
  //Fundamentals
  bool active, invis;
  int type, size, tile, rule;
  int state, statedelay;
  int behave, animate;
  float para;
  int life, colour;

  //Position and velocity
  int oldxp, oldyp;
  float ax, ay, vx, vy;
  int cx, cy, w, h;
  float newxp, newyp;
  bool isplatform;
  int x1, y1, x2, y2;
  //Collision Rules
  int onentity;
  bool harmful;
  int onwall, onxwall, onywall;

  //Platforming specific
  bool jumping;
  bool gravity;
  int onground, onroof;
  int jumpframe;
  //Animation
  int framedelay, drawframe, walkingframe, dir, actionframe;
  int yp; int xp;
};

This class constructor looks as follows:

entclass::entclass()
{
  clear();
}

void entclass::clear()
{
  // Set all values to a default,
  // required for creating a new entity
  active = false;
  invis = false;
  type = 0;
  size = 0;
  tile = 0;
  rule = 0;
  state = 0;
  statedelay = 0;
  life = 0;
  colour = 0;
  para = 0;
  behave = 0;
  animate = 0;

  xp = 0;
  yp = 0;
  ax = 0;
  ay = 0;
  vx = 0;
  vy = 0;
  w = 16;
  h = 16;
  cx = 0;
  cy = 0;
  newxp = 0;
  newyp = 0;

  x1 = 0;
  y1 = 0;
  x2 = 320;
  y2 = 240;

  jumping = false;
  gravity = false;
  onground = 0;
  onroof = 0;
  jumpframe = 0;

  onentity = 0;
  harmful = false;
  onwall = 0;
  onxwall = 0;
  onywall = 0;
  isplatform = false;

  framedelay = 0;
  drawframe = 0;
  walkingframe = 0;
  dir = 0;
  actionframe = 0;
}

Quite many fields, wouldn't you say? It's no wonder, PVS-Studio issued a warning for a bug, hiding here:

V730 It is possible that not all members of a class are initialized inside the constructor. Consider inspecting: oldxp, oldyp. Ent.cpp 3

As you can see, two class fields initializations got lost in such a long list. As a result, their values remained undefined, so they can be incorrectly read and used somewhere else in the program. It is very difficult to detect such a mistake just by reviewing.

Рисунок 4


Warning 6


Look at this code:

void mapclass::loadlevel(....)
{
  ....

  std::vector<std::string> tmap;

  ....

  tmap = otherlevel.loadlevel(rx, ry, game, obj);
  fillcontent(tmap);

  .... // The tmap vector gets changed again many times.
}

PVS-Studio warning: V688 The 'tmap' local variable possesses the same name as one of the class members, which can result in a confusion. Map.cpp 1192

Indeed, looking inside the mapclass class, you can find the same vector with the same name there:

class mapclass
{
public:
  ....

    std::vector <int> roomdeaths;
    std::vector <int> roomdeathsfinal;
    std::vector <int> areamap;
    std::vector <int> contents;
    std::vector <int> explored;
    std::vector <int> vmult;
    std::vector <std::string> tmap;       // <=

  ....
};

Unfortunately, same name vector declaration inside the function makes the vector declared in the class invisible. In turns out that the tmap vector gets changed only inside of the loadlevel function. The vector declared in the class remains the same!

Interestingly, PVS-Studio has found 20 of such code fragments! For the most part, they relate to temporary variables that have been declared «for convenience» as class members. The game author (and its only developer) wrote about himself that he used to have this bad habit. You can read about it in the post — the link is given at the beginning of the article.

He also noted that such names led to harmful bugs that were difficult to detect. Well, such errors may be really destructive, but catching them becomes less difficult if you use static analysis :)

Warning 7


V601 The integer type is implicitly cast to the char type. Game.cpp 4997

void Game::loadquick(....)
{
  ....

  else if (pKey == "totalflips")
  {
      totalflips = atoi(pText);
  }
  else if (pKey == "hardestroom")
  {
      hardestroom = atoi(pText);        // <=
  }
  else if (pKey == "hardestroomdeaths")
  {
      hardestroomdeaths = atoi(pText);
  }

  ....
}

To understand what's going on, let's take a look at the variables' definitions from the given part of code:

//Some stats:
int totalflips;
std::string hardestroom;
int hardestroomdeaths;

totalflips and hardestroomdeaths variables are integer, so it's perfectly normal to assign them the result of the atoi function. But what happens if you assign an integer value to std::string? Such assignment turns out to be valid from the language perspective. As a result, an unclear value will be written in the hardestroom variable!

Warning 8


V1004 The 'pElem' pointer was used unsafely after it was verified against nullptr. Check lines: 1739, 1744. editor.cpp 1744

void editorclass::load(std::string &_path)
{
  ....

  TiXmlHandle hDoc(&doc);
  TiXmlElement *pElem;
  TiXmlHandle hRoot(0);
  version = 0;

  {
    pElem = hDoc.FirstChildElement().Element();
    // should always have a valid root
    // but handle gracefully if it does
    if (!pElem)
    {
      printf("No valid root! Corrupt level file?\n");
    }

    pElem->QueryIntAttribute("version", &version);    // <=
    // save this for later
    hRoot = TiXmlHandle(pElem);
  }

  ....
}

The analyzer warns that the pElem pointer is unsafely used right after its checking for nullptr. To make sure the analyzer is right, let's check out the definition of the Element() function which returns the value which, in turns, initializes the pElem poiter:

/** @deprecated use ToElement.
  Return the handle as a TiXmlElement. This may return null.
*/
TiXmlElement *Element() const
{
  return ToElement();
}

As we can see from the comment, this function might return null.

Now imagine that it really happened. What will happen in this case? The fact is that this situation won't be handled in any way. Yes, there will be a message that something went wrong, but the incorrect pointer will be dereferenced just one line below. Such dereferencing will result in either the program crash or undefined behavior. This is a pretty serious mistake.

Warning 9


This code fragment triggered four PVS-Studio analyzer warnings:

  • V560 A part of conditional expression is always true: x >= 0. editor.cpp 1137
  • V560 A part of conditional expression is always true: y >= 0. editor.cpp 1137
  • V560 A part of conditional expression is always true: x < 40. editor.cpp 1137
  • V560 A part of conditional expression is always true: y < 30. editor.cpp 1137

int editorclass::at( int x, int y )
{
  if(x<0) return at(0,y);
  if(y<0) return at(x,0);
  if(x>=40) return at(39,y);
  if(y>=30) return at(x,29);

  if(x>=0 && y>=0 && x<40 && y<30)
  {
      return contents[x+(levx*40)+vmult[y+(levy*30)]];
  }
  return 0;
}

All warnings relate to the last if statement. The problem is that all four checks, performed in it, will always return true. I wouldn't say it's a serious mistake, but it's quite funny. The author decided to take this function seriously and just in case checked each variable again :)

He could have removed this check, as the execution flow won't get to the expression "return 0;" anyway. It won't change the program logic, but will help to get rid of redundant checks and dead code.

Warning 10


In his article on the game's anniversary, Terry ironically noted that one of the elements that controlled the game's logic was the huge switch from the Game::updatestate() function, responsible for a large number of different states of the game at the same time. And it was quite expected that I would find the following warning:

V2008 Cyclomatic complexity: 548. Consider refactoring the 'Game::updatestate' function. Game.cpp 612

Yes, you got it right: PVS-Studio gave the function the following complexity rating — 548. Five hundred and forty-eight!!! This is how the «neat code» looks like. And this is despite the fact that, except for the switch statement there is almost nothing else in the function. In the switch itself, I counted more than 300 case-expressions.

You know, in our company we have a small competition for the longest article. I'd love to bring the entire function code (3,450 lines) here, but such a win would be unfair, so I'll just limit myself to the link to the giant switch. I recommend that you follow the link and see its length for yourself! For the matter of that, in addition to Game::updatestate(), PVS-Studio has also found 44 functions with inflated cyclomatic complexity, 10 of which had a complexity number of more than 200.

Рисунок 5


Conclusion


I think the above errors are enough for this article. Yes, there were a lot of errors in the project, but it's a kind of a feature. By opening his code, Terry Cavanagh showed that you don't have to be a perfect programmer to write a great game. Now, 10 years later, Terry recalls those times with irony. It's important to learn from your mistakes, and practice is the best way to do it. And if your practice can give rise to a game like VVVVVV, it's just magnificent! Well… It's high time to play it one more time :)

These weren't all errors found in the game code. If you want to see for yourself what else can be found — I suggest that you download and try PVS-Studio! Also, don't forget that we provide open source projects with free licenses.
Tags:
Hubs:
+3
Comments 0
Comments Leave a comment

Articles

Information

Website
pvs-studio.com
Registered
Founded
2008
Employees
31–50 employees