In the words of Mr. John Carmack, "Focus is a matter of deciding what things you're not going to do". Taking inspiration from this quote, let's not waste any time and delve into analyzing the code of Quake World.
When exploring a codebase developed by others, we may get an exciting chance to discover valuable learning experiences from fellow programmers' mistakes. There's even a chance to gather insights that could benefit others and inspire new articles! But every now and then, we may stumble across the project that is like no other -- a true gem, created by a modern-day icon, admired and lauded by generations of successors. It's not a matter of whether to engage in a postmortem, but rather a question of how quickly one should begin!
Indeed, for yours truly Quake is one such masterpiece. Not the first "full 3d" game, as they call it (an argument can be made for Descent - you are welcome to join the debate in the comments), it in turn pushed the boundaries of 3d engines to heights previously unreachable, if not undreamed of.
While dealing with such a colossal creation, it's easy to forget that it was created by humans (though some have speculated about Carmack's artificial origins), and humans are prone to making mistakes.
So, let's learn from the best among us! We invite you to join us as we delve into the investigation of Quake World!
Throughout this article, code snippets include comments. Comments marked with PVS-Studio: or // ... were added by the author, while others are part of the original source code.
You may find the analyzed source code on the official GitHub page of id Software.
Would you find the extraordinary abilities of the one Doctor Strange rather useful in an everyday life? Jumping between dimensions, cutting through the very fabric of reality. The following piece of code may give a strong impression that the developers dived deep into this particular line of thought:
// PVS-Studio: void Mod_LoadTexinfo (lump_t *l)
// PVS-Studio: client/model.c
mtexinfo_t *out;
// ...
for (j=0 ; j<8 ; j++){
out->vecs[0][j] = LittleFloat (in->vecs[0][j]);
}Here is a little bit of context for you to navigate:
// PVS-Studio: client/model.c
typedef struct
{
float vecs[2][4]; // PVS-Studio: see what is wrong here?
float mipadjust;
texture_t *texture;
int flags;
} mtexinfo_t;// PVS-Studio: client/common.h
float (*LittleFloat) (float l);So, there is a 2d array that is treated as a 1d one. "Big deal, it is nonetheless contiguous!", would a watchful reader exclaim. True enough, according to C99, 6.2.5 Types p20:
An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type. The element type shall be complete whenever the array type is specified.
Everything looks good now, but prepare you language lawyer phone number right now!
What if we remind you that C language has a pointer to array-of-T type? So, to what type of pointer shall it decay to, and variable of what type shall we obtain with the first subscription operator?
The first operator[] yields the variable of type float[4]. When j exceeds the value of 3, we access the first array of floats out of its bounds, which leads to undefined behavior.
Ah, the wondrous land of UB! When considering the consequences, one possible scenario comes to mind: the compiler may loop through the first part only, leaving the second subarray untouched. This is certainly not something we would want to happen in our games!
For those skeptical readers who (quite rightfully) are not satisfied until proofs are present, we include the wording of the C99 standard below:
C99, 6.5.2.1/2:
A postfix expression followed by an expression in square brackets [] is a subscripted designation of an element of an array object. The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))). Because of the conversion rules that apply to the binary + operator, if E1 is an array object (equivalently, a pointer to the initial element of an array object) and E2 is an integer, E1[E2] designates the E2-th element of E1 (counting from zero).
C99, 6.5.6/8:
When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i+n-th and i−n-th elements of the array object, provided they exist. Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. If the result points one past the last element of the array object, it shall not be used as the operand of a unary * operator that is evaluated.
Countless discussions center around undefined behavior in C and C++, and many more are yet to come. Being a bit more careful with what standard is saying is rather a virtue today, especially when performance implications are not severe. Of course, it won't format you hard drive, but why take risks anyway?
As for the warnings that our analyzer issued, that was quite a concise one:
V557 Array overrun is possible. The value of 'j' index could reach 7.
P.S. Interestingly enough, there are sections within the code where the developers (seemingly) acknowledge the potential pitfall and explicitly choose a more compliant way:
// PVS-Studio: void Mod_LoadTexinfo (lump_t *l)
// PVS-Studio: server/model.c
#if 0
for (j=0 ; j<8 ; j++)
out->vecs[0][j] = LittleFloat (in->vecs[0][j]);
len1 = Length (in->vecs[0]);
len2 = Length (in->vecs[1]);
#else
for (j=0 ; j<4 ; j++) {
out->vecs[0][j] = LittleFloat (in->vecs[0][j]);
out->vecs[1][j] = LittleFloat (in->vecs[1][j]);
}
len1 = Length (out->vecs[0]);
len2 = Length (out->vecs[1]);
#endifThis would be a good time for individuals who are mindful of coding best practices to consider concluding their reading of this article. That's no joke, close it right now!
And now, you, the brave adventurer, brace yourself!
// PVS-Studio: void Sys_Printf (char *fmt, ...)
// PVS-Studio: client/sys_linux.c, server/sys_linux.c
char text[2048];
va_start (argptr,fmt);
vsprintf (text,fmt,argptr);
va_end (argptr);
if (strlen(text) > sizeof(text))
Sys_Error("memory overwrite in Sys_Printf");It is good to know when you are doing something deeply wrong, but it's even more beneficial to avoid doing this wrong altogether. When it comes to the compiler's viewpoint, the one cannot imagine with its binary brain that the length of a string written to an array may be longer than the size of the array itself. No surprise at all, as writing beyond the array's boundaries invokes undefined behavior — a rather unpleasant type of UB. Consequently, as the optimizing compiler firmly believes such a situation is impossible, the release version of the code may omit this check. As a result, a programmer gets a delightful opportunity to unintentionally corrupt data that might belong to another object. What a joy debugging will be!
Our analyzer was utterly shocked, as exemplified by the following exclamation:
V547 Expression 'strlen(text) > sizeof (text)' is always false.
This is not the only place where delayed checks were done. Take a look at the following snippet:
// PVS-Studio: void Info_SetValueForStarKey (/* ... */)
// PVS-Studio: client/common.c
if (strstr (key, "\\") || strstr (value, "\\") )
{
Con_Printf ("Can't use keys or values with a \\\n");
return;
}So far so good, until the moment we reach the below statement further down the code:
if (!value || !strlen(value))
return;Well, checking your pointers is a virtue, but only when you do it timely. Our analyzer cannot agree more:
V595 The 'value' pointer was utilized before it was verified against nullptr.
We need to look at several functions at the same time now.
// PVS-Studio: client/d_sprite.c
static sspan_t *sprite_spans;
void D_DrawSprite (void)
{
sspan_t spans[MAXHEIGHT+1];
sprite_spans = spans; // PVS-Studio: are you dead sure?
// ...
D_SpriteScanLeftEdge ();
D_SpriteScanRightEdge ();
D_SpriteDrawSpans (sprite_spans);
}
void D_SpriteScanLeftEdge (void)
{
pspan = sprite_spans;
// ...
}
void D_SpriteScanRightEdge (void)
{
pspan = sprite_spans;
// ...
}
void D_SpriteDrawSpans (sspan_t *pspan)
{
// PVS-Studio: pspan is used, among other things
}One of the first things that the author of this article read in his very first programming book was a call against using globals to store the state of functions, a call against storing functions' state altogether! Functions doing so were dubbed hard to manage at least, potentially non-reentrant at all, in the worst case –breaking the gates to hell (ah, sorry, the wrong game).
Being able to cope with this complexity correlates directly with the number of places where a single global is used. At a certain point, even the person who produced the code may forget about the very intention of theirs. And what about that new guy who out of pure curiosity decided to break the sacred rule of using function A ONLY after function B, and not vice versa?
Even more so, look closely at the end of the first function -- can you see the global being assigned some value other, then the one of a local array?
V507 Pointer to local array 'spans' is stored outside the scope of this array. Such a pointer will become invalid.
Fortunately, our example is more of a smell than a nasty mistake. The problematic assignments only occur within the functions under prosecution. So, in this specific case, it is safe to assign the local array to the global variable because the local array is preserved on the stack whenever it is used. But a single tiny little step aside, a single extra call in the wrong place -- and prepare for your compiler to unleash the demon invasion on Earth. It is UB, after all!
P.S. Interestingly, one of three functions accepts local variable as an argument without dealing with the global one. Considering that 'sprite_spans' was used exclusively inside this context, such disparity in calls only raises a question -- why not doing it with all three functions altogether?
Let's examine a series of code snippets that were scrounged across the code of the game:
// PVS-Studio: void CDAudio_Play(byte track, qboolean looping)
// PVS-Studio: client/cd_linux.c, client/cd_win.c
if (cdvolume == 0.0)
CDAudio_Pause ();
static float cdvolume;Or, for example, this one:
// PVS-Studio: void CDAudio_Update(void)
// PVS-Studio: client/cd_linux.c, client/cd_win.c
if (bgmvolume.value != cdvolume)
{
if (cdvolume)
// ...
}And, probably, the most notable of this category of errors:
// PVS-Studio: static qboolean Cam_IsVisible(player_state_t *player, vec3_t vec)
// PVS-Studio: client/cl_cam.c
if (trace.fraction != 1 || trace.inwater)
return 9999;
typedef struct
{
float fraction; // time completed, 1.0 = didn't hit anything
// ...
} pmtrace_t;Raise your hand, those who have experienced the amusement of encountering bugs related to this type of approach to comparisons. Since not all floating-point numbers can be accurately represented in binary, those that cannot will be rounded to the nearest available representation. As a result, the outcomes of these comparisons may be imprecise and, in the worst case, not reproducible under different platforms and/or compile options.
To safeguard your code, you can employ various techniques such as absolute difference checks, edit distance checks, and relative distance checks (look, for example, here and there), which take into account the inherent characteristics of the manipulated objects. Our analyzer also plays its part in preventing floating-point errors and provides the following concise advice:
V550 An odd precise comparison. It's probably better to use a comparison with defined precision: fabs(...) > Epsilon.
But wait a second, there is more for the most snobbish (or as they prefer to call themselves, accurate) programmers in which numbers yours truly tends to include himself. Take a guess what may be wrong with this code:
// PVS-Studio: void CL_Record_f (void)
// PVS-Studio: client/cl_demo.c
entity_state_t *es, blankes;
// ...
if (memcmp(es, &blankes, sizeof(blankes))) {
// ...
}Well, not until we know what is being compared exactly. So, let's figure it out!
// PVS-Studio: client/protocol.h
typedef struct
{
int number; // edict index
int flags; // nolerp, etc
vec3_t origin;
vec3_t angles;
int modelindex;
int frame;
int colormap;
int skinnum;
int effects;
} entity_state_t;Bunch of int and a couple of enigmatic vec3_t variables. Unveiling the mystery further:
// PVS-Studio: client/mathlib.h
typedef float vec_t;
typedef vec_t vec3_t[3];
typedef vec_t vec5_t[5];So, we have a memcmp of structs containing floats. This is not something that today's standards would call a good practice. For example, the SEI CERT recommends against it (see FLP37-C. Do not use object representations to compare floating-point values). Within the IEEE 754 standard, the room for possible failures encompasses the comparison of differently signed zeros, or NaNs, but, strictly speaking, the C standard doesn't mandate the application of IEEE 754 at all. Well, if you ever obtain access to a machine that has some other representation of floats, please let us know!
In case the policy of floats comparisons in your project forbids this kind of actions, the analyzer is ready to cover your back with the following descriptive warning :
V1014 Structures with members of real type are compared byte-wise.
P.S. Considering that the developers directly manipulate bytes of their floats quite often across the checked project, the author seriously doubts that this tiny little memcmp may cause big trouble.
Below are some other examples that the author has left without dedicated titles. Though lacking a name, they still possess a valuable source of inspiration (for improving your code, not for repeating the same mistakes!). Let's now examine a concise description of each sample.
Fragment 1
// PVS-Studio: void COM_AddGameDirectory (char *dir)
// PVS-Studio: client/common.c
char *p;
if ((p = strrchr(dir, '/')) != NULL)
strcpy(gamedirfile, ++p);
else
strcpy(gamedirfile, p);Although it seems that the developers are doing the right thing by checking for NULL, they are still causing trouble if the pointer is indeed NULL. Why doing so is a mystery, but not its classification:
V575 The null pointer is passed into 'strcpy' function. Inspect the second argument.
P.S. Quite possibly 'dir' variable should have been used in else branch instead of 'gamedirfile', but that's hard to say for sure.
Fragment 2
// PVS-Studio: void Draw_ConsoleBackground (int lines)
// PVS-Studio: client/draw.c
qpic_t *conback;
// ...
dest = conback->data + 320 + 320*186 - 11 - 8*strlen(ver);// PVS-Studio: client/wad.h
typedef struct
{
int width, height;
byte data[4]; // variably sized
} qpic_t;Clearly, some dark rituals are practiced on this sober land, especially considering the comment about the array. No surprise, as the state of the art back in the days was somewhat comprised of evil magic altogether. Known as "struct hack", this idiom has always been questionable, though highly useful – that is why flexible array members were standardized in C99 (see p. 6.7.2.1 of this rationale). Absent at the time Quake was done, now this feature may be a good alternative (see this talk on kernel security, for example) for getting this warning from our analyzer:
V594 The 'conback->data + 320' pointer is out of array's bounds.
Fragment 3
// PVS-Studio: void CL_AddFlagModels (entity_t *ent, int team)
// PVS-Studio: client/cl_ents.cif
if (ent->frame >= 103 && ent->frame <= 104) f = f + 6; //nailattack
else if (ent->frame >= 105 && ent->frame <= 106) f = f + 6; //light
else if (ent->frame >= 107 && ent->frame <= 112) f = f + 7; //rocketattack
else if (ent->frame >= 112 && ent->frame <= 118) f = f + 7; //shotattack
}Being explicit in successive boundaries checks is good to avoid the very thing present in the code snippet -- the boundaries are intertwined (it is hard to spot the problem; the answer is 112). Thank you, analyzer:
V695 Range intersections are possible within conditional expressions. Example: if (A > 0 && A < 5) { ... } else if (A > 3 && A < 9) { ... }.
Fragment 4
// PVS-Studio: float CL_KeyState (kbutton_t *key)
// PVS-Studio: client/cl_input.c
if (impulseup && !impulsedown)
if (down)
val = 0; // I_Error ();
else
val = 0; // released this frameWhat's most intriguing here is that the comments clearly differ, leaving us to speculate on the possibility of different values being used in previous versions. But for the time being, our analyzer catches it with the brief:
V523 The 'then' statement is equivalent to the 'else' statement.
Fragment 5
// PVS-Studio: void Key_Bind_f (void)
// PVS-Studio: client/keys.c
cmd[0] = 0; // start out with a null string
for (i=2 ; i< c ; i++)
{
strcat (cmd, Cmd_Argv(i));
if (i != (c-1))
strcat (cmd, " ");
}What is wrong with this one? To be fairly honest, the author almost lost faith in unicorns (or, at least, in the very particular one). The devil is in the details, as usual, or, in our case, in a prior code:
if (c != 2 && c != 3)
{
Con_Printf ("bind <key> [command] : attach a command to a key\n");
return;
}
if (c == 2)
{
// ...
return;
}So, well... the bound of this iteration can only be 3, right? So, it will run only once, right? So, the inequality will be evaluated only once. Essentially, that's what the analyzer is saying. It may not be the most alarming issue we've seen in this article, but it certainly is a useful diagnostic to have:
V547 Expression 'i != (c - 1)' is always false.
Fragment 6
// PVS-Studio: int Sbar_ColorForMap (int m)
// PVS-Studio: client/sbar.c
return m < 128 ? m + 8 : m + 8;Perhaps the developers wanted to ensure their intentions were crystal clear, or they simply possessed a subtle sense of humor, which our analyzer is not quite digging:
V583 The '?:' operator, regardless of its conditional expression, always returns one and the same value: ...
Fragment 7
// PVS-Studio: void CL_StartUpload (byte *data, int size)
// PVS-Studio: client/cl_parse.c
upload_data = malloc(size);
memcpy(upload_data, data, size);We cannot emphasize enough the importance of checking the values returned from malloc! Newly allocated pointers may not only be immediately referenced, leading to program crashes, but also used in pointer arithmetic, potentially causing data corruption. The NULL pointer can be added to something as well, and chances are the resulting address would be valid and open to accept writes. Even memcpy, depending on its implementation, could write into incorrect memory if passed a NULL pointer (if it starts writing from the end). We have extensively investigated this matter, and you can find a thorough explanation in this article. Currently, the analyzer identifies the code above as an error:
V575 The potential null pointer is passed into 'memcpy' function. Inspect the first argument.
Fragment 8
// PVS-Studio: void CL_ParseBeam (model_t *m)
// PVS-Studio: client/cl_tent.c
if (b->entity == ent)
{
b->entity = ent;
// ...
}// PVS-Studio: void Sbar_SortTeams (void)
// PVS-Studio: client/sbar.c
if (j == scoreboardteams) { // must add him
j = scoreboardteams++;
}There are two distinct code sections with a similar vibe. Pay most of your attention to the second example though -- contrary to the first one. Unlike the first one, this could potentially be an error if the programmer was a little vague about the return values of the two different increment operators – probably these two tiny plus signs should be on the other side of the variable. As for the analyzer, it warns us with:
V1048 The variable was assigned the same value.
Fragment 9
// PVS-Studio: void Info_SetValueForStarKey (/* ... */)
// PVS-Studio: client/common.c
c &= 127;
if (c < 32 || c > 127)
continue;Considering the practices shown previously in this article, this place only leaves a glaring question — why checking something that is guaranteed? The analyzer agrees with this line of thought:
V560 A part of conditional expression is always false: c > 127.
Fragment 10
// PVS-Studio: void M_Keys_Key (int k)
// PVS-Studio: client/menu.c
if (bind_grab)
{
// ...
if (k == K_ESCAPE)
{
bind_grab = false;
}
else if (k != '`')
{
// ...
}
bind_grab = false;
}As the song goes -- in the end it doesn't even matter. Not a biggest mistake to make, but why one would commit it today when this diagnostic is available:
V519 The 'bind_grab' variable is assigned values twice successively. Perhaps this is a mistake.
Fragment 11
// PVS-Studio: client/r_edge.c
edge_t edge_sentinel;
// PVS-Studio: void R_ScanEdges (void)
// PVS-Studio: client/r_edge.c
// FIXME: do we need this now that we clamp x in r_draw.c?
edge_sentinel.u = 2000 << 24; // make sure nothing sorts past this// PVS-Studio: client/r_shared.h
// !!! if this is changed, it must be changed in asm_draw.h too !!!
typedef struct edge_s
{
fixed16_t u;
// ...
} edge_t;Well, the comments say it all, but still, this bitwise shift operation remains mysterious. It becomes even more baffling when considering the data type to which the result is saved—it is typedefed to int, yet the name suggests that back in the days, 16 bits were the limit. The analyzer remains equally confused:
V673 The '2000 << 24' expression evaluates to 33554432000. 35 bits are required to store the value, but the expression evaluates to the 'int' type which can only hold '32' bits.
Fragment 12
// PVS-Studio: void SV_ExtractFromUserinfo (client_t *cl)
// PVS-Studio: server/sv_main.c
for (p = newname; (*p == ' ' || *p == '\r' || *p == '\n') && *p; p++)
;Do you happen to recall the order of evaluation in the logical "AND" operator? It should be from left to right, correct? Leaving a left operand only would make a bit more sense, according to our analyzer at least:
V560 A part of conditional expression is always true: * p.
Fragment 13
// PVS-Studio: void SV_Shutdown (void)
// PVS-Studio: server/sv_main.c
if (sv_logfile)
{
fclose (sv_logfile);
sv_logfile = NULL;
}
if (sv_fraglogfile)
{
fclose (sv_fraglogfile);
sv_logfile = NULL;
}A classic case of copy-paste in all its glory. There's really nothing more to add, other than the warning provided by the analyzer:
V778 Two similar code fragments were found. Perhaps, this is a typo and 'sv_fraglogfile' variable should be used instead of 'sv_logfile'.
That was a journey, and a great one for sure! Having the opportunity to explore the works of true masters of our craft is a blessing, and we are grateful to id Software for releasing the codebase of their most renowned games to public.
We sincerely hope that this article has brought you some entertainment and, in the best-case scenario, proven to be useful. And if, by any chance, yours truly has managed to move your soul or contribute in the enhancement of your skills even just a little, please do not hesitate to share your thoughts in the comments!
Thank you for accompanying us until the end! El Psy Kongroo.