September 16th, 2011

Quake 2 Source Code Review 1/4

I spent about a month in my spare time reading the source code of Quake II. It was a wonderful learning experience since one major improvement in idTech3 engine was to unify Quake 1, Quake World and QuakeGL into one beautiful code architecture. The way modularity was achieved even though the C programming language doesn't feature polymorphism was especially interesting.

In a lot of regards Quake II is a shining piece of software history since it is the most popular (in term of licensing) 3D engine of all time. Powering more than 30 games but also marking the gaming industry's departure from software/8bits color system to hardware/24bits color system that occured around 1997.

For all those reasons, I highly recommend anyone that appreciate programming to dive into it. As usual I took numerous notes, cleaned them up and publish them as it may save a few hours to someone.

I got a bit carried away with the "cleanup" process since there is more than 40MB of videos,screenshots and drawings in this article. In the end I am not sure it was worth it and I may just publish my raw ASCII notes in the future (I am thinking of Quake3 and Doom3 source), let me know what you think.

Quake 2 Source Code Review 1/4 (Intro)
Quake 2 Source Code Review 2/4 (Polymorphism)
Quake 2 Source Code Review 3/4 (Software Renderer)
Quake 2 Source Code Review 4/4 (OpenGL Renderer)

EDIT : Seems this article inspired someone at geek.com since they just wrote an article "John Carmack coded Quake on a 28-inch 16:9 1080p monitor in 1995" (mirror).

EDIT (Oct 11,2011): Wow, 120,000 hits, 75,000 readers and a lot of kind comments/emails: Thanks guys ;) !


First contact and compiling

The source code is available for free on id software ftp website. The project can be opened with Visual Studio Express 2008, also available for free on Microsoft website.

The first striking thing is that the Visual Studio 6 workspace is not made of one project but five. This is because Quake2 is designed to be modular (I will detail this later). Here is a summary of the building targets:

ProjectsBuilds
ctfgamex86.dll
gamegamex86.dll
quake2quake.exe
ref_softref_soft.dll
ref_glref_gl.dll



Note   : "ctf" and "game" projects overwrite each other, more about this later.

Note 2: Building failed at first because of DirectX header missing:


    fatal error C1083: Cannot open include file: 'dsound.h': No such file or directory

Installed Direct3D SDK and Microsoft SDK (for MFC) and the thing compiled fine.

Software erosion: It seems that what happened to Quake codebase has started to happen with Quake 2: You cannot open the workspace with Visual Studio 2010. You will need to use VS 2008 :(.


Note : If after compiling you run into the error: "Couldn't fall back to software refresh!" it means the renderer DLL failed to load properly, this is easy to fix:

Quake2 kernel loads its two dlls using win32 API: LoadLibrary. If the DLL is not exactly what it was expecting or if the DLL dependencies cannot be resolved it will fail silently instead of displaying the error message. So:

If you are using the quake2 release from id software it should fix the issue.


Quake2 architecture

When I read Quake 1 source code I divided it in three part: Network, Prediction and Rendition. This approach would have been valid for Quake 2 because the engine is not fundamentally different but it was easier to spot the improvements by dividing it by the three main project types:


Project typeProject details
Main engine (.exe)Kernel calling modules and performing client/server network communications. This is the quake2 project in the workspace.
Renderer module (.dll)In charge of rendition. A software renderer (ref_soft) and an OpenGL renderer (ref_gl) are available in the workspace.
Game module (.dll)In charge of the player experience (Game content, weapons,monsters behavior...). Singleplayer (game) and Capture The Flag (ctf) are available in the workspace.


Quake2 is mono-threaded, the entry point can be found in win32/sys_win.c. WinMain method can be summarized as follow: 

	

  game_export_t   *ge;	// Contains function pointers to game dll
  refexport_t      re;  // Contains function pointers to renderer dll

  WinMain()	//From quake2.exe
  {
	  
        Qcommon_Init (argc, argv);
	
        while(1)
        {
            Qcommon_Frame
            {
                SV_Frame()  //Server Code
                {
                    //In network mode do not act as a server
                    if (!svs.initialized) 
                       return;
                       
                    // Jump into game.dll via function pointer
                    ge->RunFrame();
                }
            	
                CL_Frame()  //Client code
                {
                    //If server only do not render anything
                    if (dedicated->value) 
                       return;    
                       
                    // Jump into rendere.dll via function pointer
                    re.BeginFrame();
                    //[...]
                    re.EndFrame();
                }	
            	
            }
        }
  }

Fully unrolled loop in my raw notes.


We may ask "why such a big change in term of architecture ?". To answer let's take a look at all the Quake versions from 1996 to 1997:

A lot of executables were produced and every time the code had to be forked or tweaked via preprocessor #ifdef. It was a mess and the way to solve this was to:

The following drawing summarize the new approach:





The two major improvements are:


Those two changes make the codebase extremely elegant and more readable than Quake 1 which was suffering from code entropy.

From an implementation perspective, the DLL projects must expose only one method GetRefAPI for the renderers and GetGameAPI for the game (Take a look at the .def file in the "Resource Files" folder):

reg_gl/Resource Files/reg_soft.def 



    EXPORTS
        GetGameAPI

When the kernel wants to load a module, it loads the DLL into the process space, retrieves GetRefAPI address with GetProcAddress, receive the functions pointers it needs and that's it.

Trivia: When playing locally, the communication Client <-> Server is not performed via sockets. Instead commands are deposed in a "loopback" buffer via NET_SendLoopPacket on the client portion of the code. The server then reconstruct a command from the same buffer using NET_GetLoopPacket.

Random trivia: Ever saw this picture and wondered what kind of monster screen was John Carmack using circa 1996:



It was a 28" InterView 28hd96 monitor manufactured by Intergraph. The beast was capable of a resolution of 1920x1080, quite impressive in 1995 (details here (mirror)).




A youtube video for your nostalgia: Workstations from Intergraph Computer Systems.

EDIT : Seems this article inspired someone at geek.com since they just wrote an article "John Carmack coded Quake on a 28-inch 16:9 1080p monitor in 1995" (mirror). Thanks for crediting me.


EDIT : Seems John Carmack was still using this screen during the development of Doom 3:



Rendition

The software renderer (ref_soft) and the hardware accelerated renderer (ref_gl), modules are so big that they have their own page:


Again, the really cool thing here is that the kernel has no idea what renderer is plugged: It just calls a function pointer in a structure. The rendition pipeline is hence totally abstracted: Who needs C++ ?

Trivia : id software still uses the same coordinate system from 1992 Wolfenstein 3D (as of Doom3 this was still true). It is important to know that if you try to read the renderer source code:

With id's system:

OpenGL's coordinate system:


Hence in the OpenGL renderer the GL_MODELVIEW matrix is setup each frame to "correct" this in the R_SetupGL method (glLoadIdentity + glRotatef).


Dynamic Linking

The kernel/module interactions were too much data: dynamic linking has its own page here.


Modding: gamex86.dll

This part of the project was not very exciting to read but abandoning Quake-C for compiled module provide two good things and one very bad.

Bad :

Good :

Trivia : Ironically id software switched back to a virtual machine (QVM) for game, IA and modding in Quake3.



My quake2

I modified Quake2 source a little bit during my hacking session, I highly recommend to add a DOS console so you can see your printf outputs live instead of having to pause the game and look at the Quake console.:

It is quite easy to add a DOS style console to a Win32 window:



    // sys_win.c

    int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow)
    {
	    
	   AllocConsole();
	   freopen("conin$","r",stdin);
	   freopen("conout$","w",stdout);
	   freopen("conout$","w",stderr);
	   consoleHandle = GetConsoleWindow();
	   MoveWindow(consoleHandle,1,1,680,480,1);
	   printf("[sys_win.c] Console initialized.\n");
	    
     
	   ...   
	   
    }

Since I was running Windows on a Mac with Parallels it was uneasy to hit "printscreen" while the game was running. I hardcoded the '*' from the keypad to produce the same:



    // keys.c
    
    if (key == '*')
    {
        if (down)  //Avoid auto-repeat !!
            Cmd_ExecuteString("screenshot");
    }


Finally I added a lot of comments and diagrams. Here is "my" full source code:



Notes : If you start working on this source you need to compile the sub-project libpng first otherwise you will get an error message at runtime: "Couldn't fall back to software refresh!". This is very easy to fix here is the solution i posted on reddit:




   I ran into this issue a month ago and you are right it is a DLL loading error and it
   is very easy to fix. You see quake2 kernel loads some dlls using win32 API: LoadLibrary:
    
    If the DLL is not exactly what it was expecting or if the DLL dependencies cannot be resolved
     it will fail silently instead of displaying the error message. So:
     
     - Make sure you are linking all 5 projects with the same runtime library by right clicking on each project -> properties -> C/C++: 
     Check that "runtime library" = Multi-threaded Debug DLL (with configuration "Debug", otherwise use release).
     
     If you are using the quake2 release from id software it should fix the issue.
     If you are using my version: I added the engine capability to output PNG screenshots, 
     so you also need to build libpng and libz (it is in a subdirectory). Make sure your select the Debug DLL configuration. 
     Once built don't forget to place the libpng and zlib dlls in the same folder as quake2.exe.
     
     Done ;) !



Memory managment


Doom and Quake1 had their own memory manager called "Zone Memory Allocation": A big malloc was done at startup and the memory block was managed via linked list. Memory Zone could be tagged so a certain category of memory could be freed very fast.

The Zone Memory Allocator(common.c: Z_Malloc, Z_Free, Z_TagMalloc , Z_FreeTags) is still here in Quake2 but it is pretty much useless:

It is still pretty usefull to measure memory consumption thanks to the size attribute in the header inserted before each memory chunks allocated: 


  
    #define    Z_MAGIC    0x1d1d


    typedef struct zhead_s
    {
	    
    struct   zhead_s    *prev, *next;
    short    magic;
    short    tag;			// for group free
    int      size;
    
    } zhead_t;


The Surface caching system has its own memory manager. The amount of memory allocated depends on the resolution with a bizarre formula that has the merit to avoid trashing very efficiently:


      Surface caching inital malloc:
      ==============================
      
        size = SURFCACHE_SIZE_AT_320X240;  //1024*768

        pix = vid.width*vid.height;	
        	
        if (pix > 64000)				
           size += (pix-64000)*3;





The "Hunk allocator" that is used for resource loading (images, sounds and textures). It is actually pretty cool and try to use virtualAlloc and align with a pagesize (8KB even tough Win98 was using 4KB ?! WTF ?!).

To finish there are a also lot of FIFO stacks (for spans storing among other things), despite the obvious limited capability they work very well.



Memory management: Alignment trick

Since Quake2 still does manipulate a lot of raw pointers there is a nice trick to align a pointer on 32bits (or align on 8KB to minimize PAGE_FAULT...even though windows 98 used 4KB pages).

Page alignment (on 8KB): 

    
    
     int roundUpToPageSize(int size)
     {
          size = (size + 8191) & ~8191; 
          return size;
     
     }

Memory alignment (on 4B): 

    
   
    
     memLoc = (memLoc + 3) & ~3;                         //Aligning on 4 bytes address.



Console subsystem

Quake2 kernel features a powerful console system that relies heavily on linked-lists and linear search.

Three objects types:

From a code perspective, each object type has a linked list: 

	 
	     
    cmd_function_t    *cmd_functions     // A linked list, each element contains a string name and a function pointer: void (*)() .
	      
	      
    cvar_t            *cvar_vars         // A linked list, each element contains a string name and a string value.
	      
	      
    cmdalias_t        *cmd_alias         // A linked list, each element contains a string name and a string alias.

Every time a line is entered in the console, it is scanned,expanded (completed via alias and cvar matches) and broken into tokens that are stored in two global variables: cmd_argc and cmd_argv: 

	    
	    
    static   int       cmd_argc;                     
    static   char     *cmd_argv[MAX_STRING_TOKENS];


Example:

Each token identified in the buffer is memcpyed to a malloced location pointed by an cmd_argv entry. The process is quite inefficient, showing that this subsystem received little attention. This is totally justified by the way: it is rarely used and has little impact hence was not worth the effort. A better approach would have been an in-place patching of the original string, writing pointer value for each token:





Once token are in the argument array, cmd_argv[0] is checked in a very slow and linearly way against all functions declared in the function linked list. If a match exist, the function pointer is called.

If no match exist the alias linked list is checked linearly in order to to check if it is a function call. If the alias did replace a function call, it is called.

Finally if nothing worked, Quake2 treats it like a variable declaration (or update if the variable is already in the linked list).

A lot of linear search in linked list is happening here, a hashmap would have been ideal to reach a O(n) complexity instead of O(n²).

Parsing trivia 1 : ASCII table were cleverly organized: When parsing a string for tokens, you can skip a separators and white space only testing if the character i is inferior to ' ' (space).

		
		
    char* returnNextToken(char* string)
    {
        while (string && *string < ' ')
            string++;
						    
        return string;
    }

Parsing trivia 2 : ASCII table were super cleverly organized: You can convert a char c to an integer as follow:
int value = c - '0' ;

		
		
    int charToInt(char v)
    {
        return  v  - '0' ;
    }


Cvar value caching:

Since searching for a Cvar (Cvar_Get) memory location in this system is O(n²) (linear search + strcmp on each entry) the renderers cache the cvar memory location:

	    

    //Caching variable
    cvar_t		*crosshair;
	    
    // During engine init step, this create 
    // and return the memory location of the Cvar.
    
    crosshair = Cvar_Get ("crosshair", "0", CVAR_ARCHIVE);    //THIS IS SLOOOOW 
    
    
    //At runtime, in the renderer.
    void SCR_DrawCrosshair (void)
    {                          
	      
        if (!crosshair->value)                                 //THIS IS FAST   
            return;
    }

The value can then be accessed in O(1).



Anti Badguys systems

A few mecanisms were inserted to prevent cheating:



In-house assembly


Like every version of quake, some useful functions were optimized with assembly (there is no yet trace of the famous "Fast Inverse Square Root", this was in Quake3).

Fast Absolute Value on a 32bits float (most compiler do it automatically now):



    float Q_fabs (float f)
    {
        int tmp = * ( int * ) &f;
        tmp &= 0x7FFFFFFF;
        return * ( float * ) &tmp;
    }


Fast Float to Integer 



    __declspec( naked ) long Q_ftol( float f )
    {
        static int tmp;
        __asm fld dword ptr [esp+4]
        __asm fistp tmp
        __asm mov eax, tmp
        __asm ret
    }



Code Statistics

Code analysis by Cloc shows a total of 138,240 lines of code. As usual this number is NOT representative of the effort since a lot was discarded during the iterative engine version cycle but I think it is a good indicator of the overall complexity of the engine. 



    $ cloc quake2-3.21/
         338 text files.
         319 unique files.
          34 files ignored.

          
    http://cloc.sourceforge.net v 1.53  T=3.0 s (96.0 files/s, 64515.7 lines/s)
    
    -------------------------------------------------------------------------------
    Language                     files          blank        comment           code
    -------------------------------------------------------------------------------
    C                              181          24072          19652         107757
    C/C++ Header                    72           2493           2521          14825
    Assembly                        22           2235           2170           8331
    Objective C                      6           1029            606           4290
    make                             2            436             67           1739
    HTML                             1              3              0           1240
    Bourne Shell                     2             17              6             54
    Teamcenter def                   2              0              0              4
    -------------------------------------------------------------------------------
    SUM:                           288          30285          25022         138240
    -------------------------------------------------------------------------------


Note : All of the assembly was for the handcrafted software renderer.

Recommended tools for Quake2 hacking session


Recommended readings

It seems that I keep on recommending the same books :/ !



Good times

 

@