Victoria Khanieva

Jul 22 2018

Tags:

#Cpp #GameDev

Shocked System: Interesting Errors in the Source Code of the Legendary System Shock

Jul 22 2018

Author: Victoria Khanieva

"How can you challenge a perfect immortal machine?"
Boolean or bitwise operand?
Special loop
Not everything is taken into account
Checking for array index out of bounds + checking for nonnull pointer
We need more comments
Bitwise shift of a negative number
Copy-paste trap
Break
The priority of operations and a poor macro
Overflow when shifting
Conclusion

My name is Victoria and I have recently joined the PVS-Studio team as a C++ developer. One of the ways to get acquainted with the analyzer and its diagnostics is to check a project and sort through the warnings, which it issues. Once I've taken on it, it's worth providing the results as an article. So I'd like to bring to your attention a review of the System Shock code. Enjoy the reading!

"How can you challenge a perfect immortal machine?"

Recently the source code of the legendary game System Shock has been released. The code of that very cyberpunk-shooter, which has affected further development of the whole direction of action adventure and thriller games and became the forerunner of such game series as Bioshock. It also inspired many of game design solutions of Metal Gear Solid, Resident Evil and even Half-Life. This may have been done to draw attention to promising remake of the original first part, which seems to go through bad times. Therefore, when I had to choose which project to check using PVS-Studio, I could not pass up such a titan of the gaming industry.

Sure, it is difficult to avoid errors in such a large project. There are plenty of examples when even highly reliable systems have various shortcomings. The error, which made $370 000 000 blow up alone is enough to demonstrate it.

Game projects also do not avoid this fate. The most interesting bugs found using PVS-Studio in the field of video games are available in our recent article "Static Analysis in Video Game Development: Top 10 Software Bugs".

In this article, we gathered some bugs from source code of games, access to which is open to all wishing on GitHub.

No doubt, the project is old. However, it is worth learning from other people's mistakes, especially since most of the shortcomings are quite typical and repeat in many projects, and besides that, they can lead to serious consequences.

Boolean or bitwise operand?

PVS-Studio warning: V560 A part of conditional expression is always true: 0xffff0000. INTERP.C 355

temp = (((ulong) _view_position.gX)>>16);  // get high 16 bits
if (((temp<<scale) && 0xffff0000)!=0) goto Exit; // overflow
temp = (((ulong) _view_position.gY)>>16);  // get high 16 bits
if (((temp<<scale) && 0xffff0000)!=0) goto Exit; // overflow
temp = (((ulong) _view_position.gZ)>>16);  // get high 16 bits
if (((temp<<scale) && 0xffff0000)!=0) goto Exit; // overflow

There is a confusion between logical and bitwise operands, && and & respectively. Apparently, a developer wanted to check that two high bytes are nonnull. However, instead of applying the bitwise "AND", he uses a Boolean "AND", and eventually a logical multiplication by a non-null constant occurs.

Special loop

PVS-Studio warning: V607 Ownerless expression 'i > 0'. TMAP.C 221

for (i=nverts; i--; i>0)
{
  ....
}

In this case, the error is in the syntax of the operator for: positions of the 2-nd and 3-rd subexpressions are messed up. Moreover, this is not the only error of this kind:

PVS-Studio warning: V607 Ownerless expression 'i >= 0'. INTERP.C 366

for (i=N_RES_POINTS-1; i--; i>=0)
  ....;

Similar warnings:

PVS-Studio warnings:

V607 Ownerless expression 'i > 0'. TMAP.C 532
V607 Ownerless expression 'i > 0'. POLYGON.C 77
V607 Ownerless expression 'i > 0'. POLYGON.C 268

Not everything is taken into account

PVS-Studio warnings:

V614 Potentially uninitialized pointer 'pc1' used. AI.C 597
V614 Potentially uninitialized pointer 'pc2' used. AI.C 609

typedef enum ObjClass {
  CLASS_GUN,
  CLASS_AMMO,
  CLASS_PHYSICS,
  ....
  CLASS_CRITTER,
  ....
} ObjClass;
errtype do_random_loot(ObjID corpse){
 int *pc1, *pc2;
   if (....)
   {
     switch (objs[corpse].obclass)
     {
       case CLASS_CONTAINER:
       ....
       *pc1 = 0;
       *pc2 = 0;
       break;
       case CLASS_SMALLSTUFF:
       ....
        pc1 = &objSmallstuffs[osid].data1;
        pc2 = &objSmallstuffs[osid].data2;
        break;
      }
      if (*pc1 == 0)
      {
        ....
      }
      if (*pc2 == 0)
      {
        ....
      }
   }
....
}

Variables pc1 and pc2 have been assigned values not in all cases, as not all set of behaviors were taken into account. So, specifically in this case objs[corpse].obclass can take a lot more values than CLASS_CONTAINER or CLASS_SMALLSTUFF. If objs[corpse].obclass takes different values, pointers pc1 and pc2 will remain uninitialized, and their dereference below will result in undefined behavior.

Checking for array index out of bounds + checking for nonnull pointer

PVS-Studio warning: V781 The value of the 'num_args' variable is checked after it was used. Perhaps there is a mistake in program logic. Check lines: 224, 225. FIX24TST.C 224

#define MAX_ARGS 8
....
bool args_neg[MAX_ARGS];
....
void parse (char *str, bool command)
{
  ....
  args_neg[num_args] = neg = FALSE;
  if (num_args == MAX_ARGS) break;
  ....
}

Logic error, which is able to incur an array index out of bounds. Border check should happen before the access to an element of an array. Similar cases:

PVS-Studio warning: V781 The value of the 'model_num' variable is checked after it was used. Perhaps there is a mistake in program logic. Check lines: 567, 569. RENDTOOL.C 567

uchar model_base_nums[MAX_VTEXT_OBJS];....
void load_model_vtexts(char model_num){
  short curr = model_base_nums[model_num];
  ....
  if (model_num >= MAX_VTEXT_OBJS)
    return;
}

PVS-Studio warning: V595 The 'ch' pointer was utilized before it was verified against nullptr. Check lines: 200, 202. HOTKEY.C 200

  hotkey_link *chain = (hotkey_link*)(ch->keychain.vec);
  if (ch == NULL) return FALSE;

Here are some other similar warnings, for which I will not cite the code:

PVS-Studio warnings:

V595 The 'ch' pointer was utilized before it was verified against nullptr. Check lines: 381, 392. EVENT.C 381
V595 The 'dp' pointer was utilized before it was verified against nullptr. Check lines: 2508, 2522. INVENT.C 2508
V595 The 'mug' pointer was utilized before it was verified against nullptr. Check lines: 702, 704. EMAIL.C 702

We need more comments

PVS-Studio warning: V547 Expression 'len <= 0' is always true. COMPOSE.C 235

len = 0;
//  len = ....;
//  ....
if (len <= 0)
{
  ....
}

One of deficiencies found throughout the code, is the use of variables that have been changed inside the commented block. Their usage when checking certain conditions is eventually meaningless. Another scenario is also possible:

PVS-Studio warning: V785 Constant expression in switch statement. BitmapTest.C 198

c = 0;
//if (....) c = evt.message & charCodeMask;
switch (c) {
case 'i':
  ....
  break;
....
case 'O': 
  ....
  break;
default:
  break;
}

In case if the commented code is not needed, you can simplify the code by removing the conditional operators.

However, in some situations, the problem may be more serious:

PVS-Studio warning: V614 Uninitialized variable 'err' used. EVENT.C 953

errtype err;
....
// err = ui_init_cursors();
....
if (err != OK) return err;

As the code was commented out, the variable err will not be initialized, and its use results in undefined behavior.

But the point was not just about hiding "unnecessary" blocks of code and giving explanations. In different fragments, I found some witty and ironic remarks, and even poetry.

// I'll give you fish, I'll give you candy, 
// I'll give you, everything I have in my hand

// it's a wonderful world, with a lot of strange men
// who are standing around, and they all wearing towels

// Returns whether or not in the humble opinion of the
// sound system, the sample should be politely obliterated 
// out of existence

// that kid from the wrong side came over my house again,
// decapitated all my dolls
// and if you bore me, you lose your soul to me 
// - "Gepetto", Belly, _Star_

//  And here, ladies and gentlemen, 
// is a celebration of C and C++ and their untamed passion...
//  ==================
TerrainData  terrain_info;
//  Now the actual stuff...
//  =======================

// this is all outrageously horrible, as we dont know what
// we really need to deal with here

// And if you thought the hack for papers was bad,
// wait until you see the one for datas... - X

It is certainly not an error, but it seemed to me that a reader would be interested to get acquainted with some of the comments :).

Bitwise shift of a negative number

PVS-Studio warning: V610 Undefined behavior. Check the shift operator '<<'. The left operand is negative ('((rand() % 4000) - 2000)' = [-2000..1999]). STAR.C 407

v.gX = ((rand()%4000) - 2000) << 8;
v.gY = ((rand()%4000) - 2000) << 8;
v.gZ = ((rand()%4000) - 2000) << 8;

It is one of the examples of undefined behavior in bitwise operations. Here, rand()%4000 returns a value in the range [0 ... 3999]. This interval is shifted by 2000, and we get a value in the range [ -2000.. 1999].

According to the latest standard of the C and C++ language, a bitwise shift of a negative number results in undefined behavior.

A similar case:

PVS-Studio warning: V610 Undefined behavior. Check the shift operator '<<'. The left operand is negative ('(axis_x - 1)' = [-1..2147483646]). ALLOC.C 122

short g3_init(short max_points,int user_x_axis,int user_y_axis,int
user_z_axis){
  ....
  long axis_x;
  ....
  if (user_x_axis<0)
  {
    user_x_axis = -user_x_axis;         
  }
  ....
  axis_x = user_x_axis;  
  ....
  axis_x_ofs = ((axis_x-1)<<1) + (axis_x-1);
  ....
}

The value of axis_x as a result of conversions can take on values of the range [0.. 2147483647]. In case if axis_x = 0, (axis_x-1) will be set to -1, which will result in undefined behavior described above.

And identical cases for axes Y and Z:

PVS-Studio warnings:

V610 Undefined behavior. Check the shift operator '<<'. The left operand is negative ('(axis_y - 1)' = [-1..2147483646]). ALLOC.C 123
V610 Undefined behavior. Check the shift operator '<<'. The left operand is negative ('(axis_z - 1)' = [-1..2147483646]). ALLOC.C 124

Copy-paste trap

PVS-Studio warning: V751 Parameter 'Y' is not used inside function body. BTEST.C 67

fix Terrain( fix X, fix Y, int deriv ) {
  if( deriv == 0 )
    return fix_mul(...., (X - ....) );
  if( deriv == 1 )
    return fix_mul(...., (X - ....) );
  if( deriv == 2 ) return 0;
    return 0;
}

Judging by the fact that both X and Y are passed into function and also two different conditions have the same body, one can assume that the second condition had to use Y, but when copying similar lines of code this point has been missed.

Break

PVS-Studio warning: V796 It is possible that 'break' statement is missing in switch statement. OLH.C 142

switch (objs[obj].obclass)
{
  case CLASS_DOOR:
    ....
    break;
  case CLASS_BIGSTUFF:
    ....
    if (....)
    {
      ....
      break;
    }
  case CLASS_SMALLSTUFF:
    ....
    if (....)
    {
      ....
      break;
    }
  // smallstuff falls through to default. 
  default:
    ....
    break;
}

Break switch is present within the conditions in both branches and, as a result, if none of them is executed, fallthrough will occur. In the second case, it is specified that it was made intentionally but in the first case there is no such a comment, therefore, it is very likely that this is a logical error.

A similar warning:

PVS-Studio warning:

V796 It is possible that 'break' statement is missing in switch statement. GAMEREND.C 777

The priority of operations and a poor macro

PVS-Studio warning: V634 The priority of the '-' operation is higher than that of the '<<' operation. It's possible that parentheses should be used in the expression. FRCLIP.C 256

#define span_right(y,s) \
  (x_span_lists[((y)<<SPAN_SHIFT)+(s<<1)+SPAN_RIGHT])
void fr_span_parse(void)
{
....
if (....span_right(y,(*cur_span_cnt)-1)....)>frpipe_dist)
  ....
....
}

In working of the preprocessor we'll get the code as follows:

x_span_lists[((y)<<SPAN_SHIFT)+((*cur_span_cnt)-1<<1)+SPAN_RIGHT]

Macros are a great way to shoot yourself in the foot. A priority of the shift operator is lower than the priority of the subtraction operator. Therefore, in this particular case there is no error. The programmer was lucky that the shift operator is applied to the expression (*cur_span_cnt)-1, not to the literal 1.

However, if you write ....span_right(y,(*cur_span_cnt) & 1)...., then the code will work differently than a programmer expects. Therefore, you must enclose all the arguments of macros in parentheses. Here is the correct version of a macro:

#define span_right(y,s) \
  (x_span_lists[((y)<<SPAN_SHIFT)+((s)<<1)+SPAN_RIGHT])

Overflow when shifting

PVS-Studio warning: V610 Undefined behavior. Check the shift operator '<<'. The right operand ('i' = [1..64]) is greater than or equal to the length in bits of the promoted left operand. CARDMFD.C 121

ulong bits;
....
for (i = 1; i <= sizeof(ulong)*8; i++)
{
  if (bits & (1 << i))
  {
    ...
  }
}

The error is difficult to explain, it would be better to consider it separately for 32-bit and 64-bit systems.

In a 32-bit system, the last step of a loop causes undefined behavior, because the shift is implemented by more than 31 bits. Description: numeric literal 1 is of 32-bit type int.

In a 64-bit system it will be even more interesting. Yes, the project System Shock has never been compiled for 64-bit systems, but let's still consider this option.

If a type long is 32-bit (data model LLP64), the situation is exactly the same as in the 32-bit program: undefined behavior will occur. In practice, however, such code can work as expected due to luck :).

If long is 64-bit (LP64), then the probability that the undefined behavior will lead to the correct execution is much smaller :). The numeric literal 1 is of the 32-bit type int. Which means, that it is impossible to obtain the value outside the range [INT_MIN..INT_MAX] as a result of the shift. Of course, undefined behavior can be anything but it is clearly not worth waiting for a good outcome from it.

Here is the correct version of code:

for (i = 1; i < sizeof(ulong)*8; i++)
{
  if (bits & (1ul << i))
  {
    ...
  }
}

Here the literal 1 is replaced by 1ul, and the <= operator is replaced by <.

Conclusion

We can conclude that if a static code analyzer had been available to the authors, many errors could have been avoided and it could have saved many of players' nerve cells, as a large number of logical errors probably resulted in a strange game behavior.

#Cpp #GameDev